基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法
基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法
【技术领域】
[0001] 本发明设及无线自组网领域，具体是基于蓝牙技术的手机自组通信网络CelWet 的组网和路由算法。
【背景技术】
[0002] 目前，关于无线自组网的研究很多，比如《Ad-Hoc网络路由协议的改进研究和无线 Me sh网络路由技术研究》中介绍了很多的算法，其中就有DSDV、0LSR、DSR、A0VD、T0RA、LAR、 GRSR等。但是，运些算法均存在一些劣势，比如DSDV和化SR算法，它们基于表驱动路由，需要 在每个节点维护整个网络的路由，当网络越来越大的时候，每个节点的表的大小就会越来 越大，在维护运张表的时候，也需要向网络中的节点发送自己的节点信息，增加了网络的负 担，很可能导致拥塞。又比如DSR、A0VD、T0RA算法，运Ξ个协议都是需要在传送数据时，启动 路由发现的过程，然后找到一条路径，接着按照运个路径发送数据，运样的一个过程，网络 拓扑图变化很快的时候，路由维护的开销很大，并且数据包的到达率也很低。再比如GRSR算 法，它完全基于位置，选择离目的节点更近的节点作为下一跳的节点，运个也是需要维护节 点的位置信息，该协议也会洪泛发送自身节点信息，并且该协议可能导致当前节点无法找 到比自身节点更加靠近目的节点的下一跳。
【发明内容】
[0003] 本发明的目的在于提供一种基于蓝牙技术的手机自组通信网络CelWet的组网和 路由算法，解决目前的无线Mesh化t路由算法存在路由维护开销大、数据包到达率较低的问 题，同时还可能存在造成网络负担较大、网络拥堵的问题。
[0004] 本发明的目的通过下述技术方案实现：基于蓝牙技术的手机自组通信网络 Ce 1 INet的组网和路由算法，包括W下步骤：
[0005] (a)组网阶段:将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居 节点；
[0006] (b)更新阶段:实时更新当前节点的contact 1 i S t中各个邻居节点的信息；
[0007] (C)发送阶段:当前节点将普通数据包或者系统数据包发送至下一节点；
[000引（d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据 包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包；
[0009] 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是， 则本节点处理该数据包，并且不进行数据转发；
[0010] 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是 否大于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发；
[0011] (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。
[0012] 进一步地，作为优选方案，所述组网阶段的具体过程为：
[0013] (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节 点会根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表 示该节点可W加入该蓝牙网络，并根据收到的确认消息更新该节点的contact 1 i St，发送确 认消息的节点同时也更新自己的contactlist;
[0014] (a2)如果该节点收到的是拒绝消息，则组网失败。
[0015] 进一步地，作为优选方案，所述更新阶段的具体过程为：
[0016] 当某一节点启动时，该节点周期性地向其contactlist中的各个节点发送屯、跳消 息，根据各个节点是否做出回复来更新本节点contactlist中各个节点的状态；
[0017] 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点；
[0018] 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。
[0019] 进一步地，作为优选方案，所述发送阶段包括普通数据包发送和系统数据包发送， 所述普通数据包的发送过程为：
[0020] (cll)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制 并发送消息；
[0021] (C12)如果是转发的，则直接发送；
[0022] 所述系统消息的发送过程为：
[0023] (C21)从节点中取出该系统消息，并直接发送。
[0024] 进一步地，作为优选方案，所述路由阶段中，节点进行路由转发的具体过程为：
[0025] (dl)获取数据包已经排除的节点集；
[0026] (d2)通过该节点的contactlist获得该节点的邻居节点集，并根据已经排除的节 点集，从邻居节点集中筛选出未被排除的节点；
[0027] (d3)把运些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新 的数据包转发给刚刚未被排除的节点集中的所有节点。
[0028] 进一步地，作为优选方案，所述步骤(d3)中，将未被排除的节点加入到待转发数据 包中的具体过程为：
[0029] ((131)当有节点想加入到￡：成〇111:;[叫中时，把该节点插入到1]136的口所指向的位置， 此时1]136的口自动向后移动一个位置，当InsedP到达末尾时，则重新指向ExRouting的第一 个位置;其中，ExRout ing和1]13純1口是待发数据包中的两个字段，ExRout ing是指在数据包 中已排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置；
[0030] (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
[0031] 本发明具有W下有益效果：
[0032] (1)本发明通过采用特殊的路由方式，在数据包发送过程中，实现了路由路径的动 态生成，同时，通过数据包记录路由经过的所有节点，节点收到数据包时就不再向已收到该 数据包的节点转发，避免了数据包在某个节点上重复地路由，从而极大地降低了路由选择 的时间，也减轻了由于重复发送数据包造成的网络负担。
[0033] (2)本发明在组网和路由选择时，只需要维护每个节点的邻居节点信息，无需在任 何节点处维护整个网络的所有节点信息，从而降低了节点维护的时间，也避免了储存大量 节点信息造成的手机内存不足等问题。
【附图说明】
[0034] 图1为与hand化ake协议对应的线程的流程图；
[0035] 图2为与heartbeat协议对应的线程的流程图；
[0036] 图3为与sencLSyn协议对应的线程的流程图；
[0037] 图4为与sencLSys协议对应的线程的流程图；
[0038] 图5为与receive_msg协议对应的线程的流程图；
[0039] 图6为路由过程的流程图；
[0040] 图7为que巧线程与其它线程的关系图；
[0041 ]图8为heartbeat线程与其它线程的关系图；
[0042] 图9为service线程与其它线程的关系图；
[0043] 图10为组网和路由过程示意图。
【具体实施方式】
[0044] 下面结合实施例对本发明作进一步的详细说明，但本发明的实施方式不仅限于 此。W下提到的节点与本发明要表达的手机端是一个概念，两者只是不同层面的不同叫法 而已。
[0045] 实施例：
[0046] 本实施例所述的基于蓝牙技术的手机自组通信网络Cell化t的组网和路由算法， 包括W下步骤：
[0047] (a)组网阶段:将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居 节点；
[0048] (b)更新阶段:实时更新当前节点的contact 1 i S t中各个邻居节点的信息；
[0049] (C)发送阶段：当前节点将普通数据包或者系统数据包发送至下一节点，系统数据 包是指入网和屯、跳相关的数据包，入网和屯、跳相关的数据包与后面要提到的handshake协 议(握手协议)和heartbeat协议（屯、跳协议)相关，普通数据包是指系统数据包W外的数据 包，比如普通文本信息，系统信息等；
[0050] (d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据 包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包；
[0051] 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是， 则本节点处理该数据包，并且不进行数据转发；
[0052] 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是 否大于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发；
[0053] (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。
[0054] 具体地，组网阶段的具体过程为：
[0055] (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节 点会根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表 示该节点可W加入该蓝牙网络，并根据收到的确认消息更新该节点的contact 1 i St，发送确 认消息的节点同时也更新自己的contactlist;
[0056] (a2)如果该节点收到的是拒绝消息，则组网失败。
[0057] 具体地，更新阶段的具体过程为：
[005引当某一节点启动时，该节点周期性地向其contactlist中的各个节点发送屯、跳消 息，根据各个节点是否做出回复来更新本节点contactlist中各个节点的状态；；
[0059] 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点；
[0060] 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。
[0061] 具体地，发送阶段包括普通数据包发送和系统数据包发送，所述普通数据包的发 送过程为：
[0062] (cll)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制 并发送消息；
[0063] (C12)如果是转发的，则直接发送；
[0064] 所述系统消息 的发送过程为：
[0065] (C21)从节点中取出该系统消息，并直接发送。
[0066] 具体地，所述路由阶段中，节点进行路由转发的具体过程为：
[0067] (dl)获取数据包已经排除的节点集；
[006引（d2)通过该节点的contactlist获得该节点的邻居节点集，并根据已经排除的节 点集，从邻居节点集中筛选出未被排除的节点；
[0069] (d3)把运些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新 的数据包转发给刚刚未被排除的节点集中的所有节点。
[0070] 具体地，步骤(d3)中，将未被排除的节点加入到待转发数据包中的具体过程为： [0071 ] ((131)当有节点想加入到￡：成〇111:;[叫中时，把该节点插入到1]136的口所指向的位置， 此时1]136的口自动向后移动一个位置，当InsedP到达末尾时，则重新指向ExRouting的第一 个位置;其中，ExRout ing和1]13純1口是待发数据包中的两个字段，ExRout ing是指在数据包 中已排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置；
[0072] (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
[0073] 下面用一个具体的实施例来说明本发明的实现过程，具体如下：
[0074] 首先，为了实现手机终端(节点）之间数据的传输，我们对节点之间的数据格式进 行明确的约定。Ce 1 INet的数据格式如表1。
[00巧]表1 Mesh化t数据格式
[0076]
[0077] 其中；
[0078] (1 )Type表示消息类型，占用IByte，可W如下取值：
[00巧]a)0000 0001 = SYN，普通消息
[0080] b)0000 0010 =皿，屯、跳消息
[0081] c)0000 0011=如ery，que;ry消息
[0082] d)0000 0100=ACK，对普通消息的确认消息
[0083] e)0000 0101=HBACK，对屯、跳消息的确认消息
[0084] f)0000 0110 = QACK，对que巧消息的确认消息
[0085] g)0000 0111= NQACK，对que巧消息的拒绝消息
[0086] (2)NetID表示的是网络号，占用IB^e，当有节点尝试接入某个网络时，该网络中 的节点收到如e巧信号时根据其化om_ID判断回复QACK还是NQACK;
[0087] (3)From_ID和To_ID分别表示消息的源端和目的端，根据手机固有的SequenceNO. 和用户输入的NickName确定，SN为12位的十进制数，NickName不超过20个字母，所WFrom_ ID 占用 32Byte;
[0088] (4)Seq_N0表示的是消息序列号，占用2Β^θ，其中65535,即mi mi mi mi 表示消息传输结束；
[0089] (5)ACK_N0表示当前消息是对上一个序列号为ACK_N0的消息的确定，占用2B^e;
[0090] (6)TTL表示的是消息在网络中存活的最长"时间"，用跳数衡量，是为了防止某一 个消息在网络中绕圈，占用IByte;
[0091 ] (7)化eckSum表示该消息的校验和，当消息初始化时，根据消息头计算得出，当收 到消息时再次根据消息头计算新的化ekSum，比较二者，若匹配则表示该传输没有错误，否 则表示传输出错。占用2Byte;
[0092] (8)InsertP表示应该更新的ExRouting的位置
[0093] (9)Content表示消息体，真正的数据信息放入其中，规定消息最大长度不超过 128Byte；
[0094] (10)ExRouting，B|3Exclude Routing,表示该消息已经通过的路由W及这些路由 的临近节点，相当于一个集合，该字段的长度足W容纳20个终端ID，即640Byte。
[0095] 另外，为了保证网络中各个手机终端(节点）能够实现可靠的数据传输，除了规定 的数据格式，还需要一定的协议作保障，如计算机网络中的TCP/IP协议。本发明的Cell化t 也有一套自己的协议作支持，包括hand化ake协议、headbeat协议、receive_msg协议、 sentSyn协议、semLSys协议和routing协议，其中协议都会设及到具体的消息格式和不同 的线程做处理，同时还会在每个手机终端维护一个contactList表，该表中存放的是当前手 机终端的邻居节点（即可W让消息直接到达的节点）。
[0096] (一化 andShake 协议
[0097] handshake协议主要解决的是当终端尝试接入网络时的问题。当终端尝试接入网 络时，它会向周围的网络发送QueiT消息，当收到对QueiT消息的确认消息即QACK消息时表 示该终端可W加入已有网络，根据收到的QACK消息更新当前终端的contactList。
[0098] (1)与hand化ake协议对应的消息格式如表2所示，
[0099] 表2如e巧消息格式 rnmnl
[0101] (2)与hand化ake协议对应的线程的流程图如图1所示。
[0102] (二化 ea;rtbeat 协议
[0103] headbeat协议主要解决的问题是实时更新contactList表中的各个节点的信息。 当手机终端启动时，手机终端将周期性地向其contactList表中的各个节点发送皿消息，然 后根据运些节点的响应情况动态更新contactList表。
[0104]与heartbeat协议对应消息的格式如表3所示，
[01化]表3皿消息格式 [0106]
[0107] (1)与heartbeat协议对应线程heartbeat线程的流程图如图2所示。
[010 引（S)send_Syn 协议
[0109] sen tSyn协议主要解决的是发送普通文本消息的问题，当终端的Send_Syn中有待 发送的数据时，与sencLSyn协议对应的sencLSyn线程将发送消息，并且该线程会根据所发 送消息的类型采取不同策略。
[0110] (1)与send_Syn协议对应的send_Syn线程的流程图如图3所示。
[0111] (四）send_Sys 协议
[0112] sentSys协议主要解决的是发送QueiT消息和皿消息的问题，当终端的Send_Sys 中有待发送的数据时，与sencLSys协议对应的sencLSys线程将发送消息，并且该线程会根 据所发送消息的类型采取不同策略。
[0113] (1)与send_Sys协议对应的send_Sys线程的流程图如图4所示。
[0114] (五)receive_msg 协议
[0115] receive_msg协议主要解决的是接收消息的问题，主要是根据收到的不同消息类 型作相应的响应动作，与receive_msg协议对应的receive_msg线程负责接收消息的一系列 动作。
[0116] (l)receive_msg线程的流程图如图5所示。
[0117] (六);routing 协议 [011引 1.概述
[0119] 该部分描述了 Cell化t路由协议，制定了在Cell化t网络中数据包的转发规则。此 协议的运用是在基于蓝牙或WLAN数据传输上的，也就是数据包的传输是利用蓝牙或WLAN进 行的，而在每个节点上应用本节所描述的协议进行数据转发。
[0120] 2.限制条件
[0121] 蓝牙：一种支持设备短距离通信的无线电技术，目前最远的传输距离能扩大到 100m。
[0122] WLAN:利用无线技术在空中传输数据、话音和视频信号。目前的传输距离也达到了 100m。
[0123] 邻居节点最大个数:每个节点允许有自己的一些邻居节点，但是每个节点只能容 纳最多20个邻居节点。
[0124] 目地节点:数据包最终要传输到的节点。
[01巧]数据包了化:数据包最多在网络中经过20hop。
[01%]已处理数据包表中数据存活时间：最大不能超过8s。
[0127] 3.协议描述
[012引 （1)路由过程
[0129]在整个CelWet网络中，每个节点都承担着数据接收和数据转发的功能。每个节点 维护两张表，一张是通过化artBeat机制维护邻居节点表(参见表4)，允许最大的节点数是 20个;另外一张表是已处理数据包表(参见表5)，一条记录允许的最大时间8秒。
[0130] 一个节点收到另外一个节点转发来的数据包时，首先通过已处理数据包表查看是 否已经处理过该数据包，如果已经处理过，则丢弃该数据包，否则进行下一步。
[0131] 如果没有处理过该数据包，则查看该数据包的转发目的地是否是本节点，如果是 则本节点处理该数据包，并且不进行数据转发;如果该数据包的转发目的地不是本节点，贝U 查看数据包中的TTL的值是否大于20，大于20就直接丢弃该数据包，否则本节点进行路由转 发。
[0132] 如果一个节点进行路由转发，首先根据数据包里的ExRouting字段获得该数据包 已经排除的节点集(排除的节点是指该数据包在W后转发的过程中，不会转发给已经排除 的节点），接着从邻居节点表中获得该节点的邻居节点集，然后在邻居节点集中根据已经排 除的节点集筛选出未被排除的节点，把运些未被排除的节点加入到待转发数据包的 ExRouting字段中，加入后，就把修改的数据包转发给刚刚未被排除的节点集中的所有节 点。相关流程可参见图6。
[0133] (2)邻居节点表
[0134] 表4邻居节点表
[0135]
[0136] 如果节点经过化op就能把数据传递给对方，则双方互称为邻居节点。运张表允许 的最大记录数是20。
[0137] 如果是一个节点想要加入一个网络，当发送que巧消息后，收到QACK消息回复后， 则把回复消息的节点加入邻居节点表。
[0138] 如果一个网络中节点 收到另一个想要加入网络节点发出的quen^消息后，如果同 意加入，则把该节点加入自己的邻居节点表中。
[0139] 用heart beat来维护邻居节点表。
[0140] (3)已处理数据包表
[0141] 表5已处理数据包表
[0142]
[0143] 当数据包的目的地是本节点或本节点对该数据包进行了转发，则把数据包的相关 信息记录在已处理数据包表中。一条记录存在的最大时间为8秒，如果超过了该时间，则把 该记录移除。
[0144] (4化xRouting字段节点加入过程
[0145] 在数据包中，有两个字段，分别是ExRouting和InsedPsEsRouting是指在数据包 中已经排除的节点列表；InsertP是指下一个节点加入到ExRouting中的位置。当有节点想 加入到ExRouting时，就把该节点插入到Ins&rtP所指向的位置，此时InsedP自动向后移动 一个位置，当InsedP到达末尾时，则会重新指向ExRouting的第一个位置。
[0146] 如果要加入的节点在Exrouting已经存在时，则该节点不会再次加入。
[0147] (5)路由实现 [014引①线程
[0149] 路由协议由Ξ个线程组成，一个线程是routing用来路由，一个线程是heart beat 线程用来维护邻居节点表，一个线程是check_pack_time用来维护已处理数据包表。
[0150] 当receive_msg线程收到一个要路由的数据包，则通知路由线程routing,并把数 据包传递给routing线程，如果需要转发该数据包，则routing线程通知send_msg线程，把新 的数据包传递给sencLmsg线程。
[0151] CellNet中各个线程完成不同的功能，除了 W上提到的线程外，CellNet中还有一 个线程用于上层APP的消息请求一一service线程。为了使各个线程能够有效的协作， Cel INet 在主线程中创建Send_Syn、Send_Sys、Msg_Queue、40(_如6116、HBACK_Queue、QACK_ Queue、ContactList等资源，从而使得线程之间能够有效的交互数据。其中，
[0152] (l)Send_Syn用于存放将要发送的文本消息；
[0153] (2)Send_Sys用于存放系统消息，如皿消息和如eiy消息；
[0154] (3)Msg_Queue用于存放收到的普通消息；
[01W] (4)ACK_Queue用于存放对普通消息确认的消息；
[0156] (5)HBACK_Queue用于存放皿消息的回复消息；
[0157] (6) QACK_Queue用于存放如eiy消息的回复消息。
[015引（二)线程间关系概要如表6，
[0159]表6线程关系 「01601
[0161] ~(l)query线程与其它线程的关系如图7所示，
[0162] 线程执行的逻辑顺序如下：
[0163] ① query线程将待发送的如日巧消息放入Send_Queue中，然后等待该消息的QACK消 息；
[0164] ②send_msg线程从Send_Queue取出待发送的如eiy消息、发送；
[01化]③receive_msg线程将受到的QACK消息放入QACK_Queue中；
[0166] ④query线程将对如eiT消息确认的QACK消息从QACK_Queue中取出、更新当前终端 的 contactList表。
[0167] (2化eadbeat线程与其它线程的关系如图8所示，
[0168] 线程的逻辑执行顺序如下：
[0169] ① heartbeat线程将皿小放入SemLQueue中，然后等待对运些消息响应的HBACK_ 如eue消息；
[0170] ②send_msg线程从Send_Queue中取出皿消息、发送；
[0171 ] ③receive_msg线程将收到的HBACK消息放入HBACK_Queue中；
[0172] ④heartbeat线程从HBACK_Queue中取出对皿响应的HBACK消息、更新contactList 表。
[0173] (3)service线程与其它线程的关系如图9所示，
[0174] 上层应用直接通过调用service线程提供的服务，把待发送的消息放入Send, 如eue中，并把Msg_Queue中的消息取出。
[0175] 如图10所示，A节点为起始节点，B节点为目的节点，A节点向下一节点发送数据包， 下一节点在接收数据包时，首先通过自身的已处理数据包表来判断该数据包是否被本节点 处理过，如果未被处理过，则查看该数据包的转发目的地是否为本节点，如果不是，则更新 该数据包中的发送节点并转发给运些发送节点，直到最后数据包转发到目的节点B，从而实 现了数据包在发送过程中动态生成整个路由路径A^B。
[0176] 本发明已经通过上述实施例进行了说明，但应当理解的是，上述实施例只是用于 举例和说明的目的，而非意在将本发明限制于所描述的实施例范围内。此外，本领域技术人 员可W理解的是，本发明并不局限于上述实施例，根据本发明的教导还可W做出更多种的 变型和修改，运些变型和修改均落在本发明所要求保护的范围W内。
【主权项】
1. 基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法，其特征在于:包括以 下步骤： (a) 组网阶段:将节点接入到蓝牙网络中，并更新该节点的contact1ist中的邻居节点； (b) 更新阶段:实时更新当前节点的contact1ist中各个邻居节点的信息； (c) 发送阶段:当前节点将普通数据包或者系统数据包发送至下一节点； (d) 路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据包表 来查看该数据包是否已经处理过，如果是，则丢弃该数据包； 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是，则本 节点处理该数据包，并且不进行数据转发； 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是否大 于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发； (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。2. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述组网阶段的具体过程为： (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节点会 根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表示该 节点可以加入该蓝牙网络，并根据收到的确认消息更新该节点的contact1ist，发送确认消 息的节点同时也更新自己的contact1ist; (a2)如果该节点收到的是拒绝消息，则组网失败。3. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述更新阶段的具体过程为： 当某一节点启动时，该节点周期性地向其contact1ist中的各个节点发送心跳消息，根 据各个节点是否做出回复来更新本节点contact1ist中各个节点的状态； 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点； 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。4. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述发送阶段包括普通数据包发送和系统数据包发送，所述普通数据包的 发送过程为： (cl1)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制并发 送消息； (cl2)如果是转发的，则直接发送； 所述系统消息的发送过程为： (c21)从节点中取出该系统消息，并直接发送。5. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述路由阶段中，节点进行路由转发的具体过程为： (d1)获取数据包已经排除的节点集； (d2)通过该节点的contact1ist获得该节点的邻居节点集，并根据已经排除的节点集， 从邻居节点集中筛选出未被排除的节点； (d3)把这些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新的数 据包转发给刚刚未被排除的节点集中的所有节点。6.根据权利要求5所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述步骤(d3)中，将未被排除的节点加入到待转发数据包中的具体过程 为： (d31)当有节点想加入到ExRouting中时，把该节点插入到InsertP所指向的位置，此时InsertP自动向后移动一个位置，当InsertP到达末尾时，贝lj重新指向ExRouting的第一个位 置;其中，ExRouting和InsertP是待发数据包中的两个字段，ExRouting是指在数据包中已 排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置； (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
【专利摘要】基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法，包括以下步骤：(a)组网阶段：将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居节点；(b)更新阶段：实时更新当前节点的contactlist中各个邻居节点的信息；(c)发送阶段：当前节点将普通文本消息或者系统消息发送至下一节点；(d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包，反之则进行下一步；(e)接收阶段：下一节点根据收到的不同消息类型，作出相应的响应动作。本发明采用上述方法，能够减小路由开销，减轻网络负担，避免网络拥堵。
【IPC分类】H04W4/00, H04W40/04
【公开号】CN105491508
【申请号】CN201510381635
【发明人】汤羽
【申请人】汤羽
【公开日】2016年4月13日
【申请日】2015年6月30日
【技术领域】
[0001] 本发明设及无线自组网领域，具体是基于蓝牙技术的手机自组通信网络CelWet 的组网和路由算法。
【背景技术】
[0002] 目前，关于无线自组网的研究很多，比如《Ad-Hoc网络路由协议的改进研究和无线 Me sh网络路由技术研究》中介绍了很多的算法，其中就有DSDV、0LSR、DSR、A0VD、T0RA、LAR、 GRSR等。但是，运些算法均存在一些劣势，比如DSDV和化SR算法，它们基于表驱动路由，需要 在每个节点维护整个网络的路由，当网络越来越大的时候，每个节点的表的大小就会越来 越大，在维护运张表的时候，也需要向网络中的节点发送自己的节点信息，增加了网络的负 担，很可能导致拥塞。又比如DSR、A0VD、T0RA算法，运Ξ个协议都是需要在传送数据时，启动 路由发现的过程，然后找到一条路径，接着按照运个路径发送数据，运样的一个过程，网络 拓扑图变化很快的时候，路由维护的开销很大，并且数据包的到达率也很低。再比如GRSR算 法，它完全基于位置，选择离目的节点更近的节点作为下一跳的节点，运个也是需要维护节 点的位置信息，该协议也会洪泛发送自身节点信息，并且该协议可能导致当前节点无法找 到比自身节点更加靠近目的节点的下一跳。
【发明内容】
[0003] 本发明的目的在于提供一种基于蓝牙技术的手机自组通信网络CelWet的组网和 路由算法，解决目前的无线Mesh化t路由算法存在路由维护开销大、数据包到达率较低的问 题，同时还可能存在造成网络负担较大、网络拥堵的问题。
[0004] 本发明的目的通过下述技术方案实现：基于蓝牙技术的手机自组通信网络 Ce 1 INet的组网和路由算法，包括W下步骤：
[0005] (a)组网阶段:将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居 节点；
[0006] (b)更新阶段:实时更新当前节点的contact 1 i S t中各个邻居节点的信息；
[0007] (C)发送阶段:当前节点将普通数据包或者系统数据包发送至下一节点；
[000引（d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据 包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包；
[0009] 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是， 则本节点处理该数据包，并且不进行数据转发；
[0010] 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是 否大于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发；
[0011] (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。
[0012] 进一步地，作为优选方案，所述组网阶段的具体过程为：
[0013] (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节 点会根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表 示该节点可W加入该蓝牙网络，并根据收到的确认消息更新该节点的contact 1 i St，发送确 认消息的节点同时也更新自己的contactlist;
[0014] (a2)如果该节点收到的是拒绝消息，则组网失败。
[0015] 进一步地，作为优选方案，所述更新阶段的具体过程为：
[0016] 当某一节点启动时，该节点周期性地向其contactlist中的各个节点发送屯、跳消 息，根据各个节点是否做出回复来更新本节点contactlist中各个节点的状态；
[0017] 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点；
[0018] 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。
[0019] 进一步地，作为优选方案，所述发送阶段包括普通数据包发送和系统数据包发送， 所述普通数据包的发送过程为：
[0020] (cll)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制 并发送消息；
[0021] (C12)如果是转发的，则直接发送；
[0022] 所述系统消息的发送过程为：
[0023] (C21)从节点中取出该系统消息，并直接发送。
[0024] 进一步地，作为优选方案，所述路由阶段中，节点进行路由转发的具体过程为：
[0025] (dl)获取数据包已经排除的节点集；
[0026] (d2)通过该节点的contactlist获得该节点的邻居节点集，并根据已经排除的节 点集，从邻居节点集中筛选出未被排除的节点；
[0027] (d3)把运些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新 的数据包转发给刚刚未被排除的节点集中的所有节点。
[0028] 进一步地，作为优选方案，所述步骤(d3)中，将未被排除的节点加入到待转发数据 包中的具体过程为：
[0029] ((131)当有节点想加入到￡：成〇111:;[叫中时，把该节点插入到1]136的口所指向的位置， 此时1]136的口自动向后移动一个位置，当InsedP到达末尾时，则重新指向ExRouting的第一 个位置;其中，ExRout ing和1]13純1口是待发数据包中的两个字段，ExRout ing是指在数据包 中已排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置；
[0030] (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
[0031] 本发明具有W下有益效果：
[0032] (1)本发明通过采用特殊的路由方式，在数据包发送过程中，实现了路由路径的动 态生成，同时，通过数据包记录路由经过的所有节点，节点收到数据包时就不再向已收到该 数据包的节点转发，避免了数据包在某个节点上重复地路由，从而极大地降低了路由选择 的时间，也减轻了由于重复发送数据包造成的网络负担。
[0033] (2)本发明在组网和路由选择时，只需要维护每个节点的邻居节点信息，无需在任 何节点处维护整个网络的所有节点信息，从而降低了节点维护的时间，也避免了储存大量 节点信息造成的手机内存不足等问题。
【附图说明】
[0034] 图1为与hand化ake协议对应的线程的流程图；
[0035] 图2为与heartbeat协议对应的线程的流程图；
[0036] 图3为与sencLSyn协议对应的线程的流程图；
[0037] 图4为与sencLSys协议对应的线程的流程图；
[0038] 图5为与receive_msg协议对应的线程的流程图；
[0039] 图6为路由过程的流程图；
[0040] 图7为que巧线程与其它线程的关系图；
[0041 ]图8为heartbeat线程与其它线程的关系图；
[0042] 图9为service线程与其它线程的关系图；
[0043] 图10为组网和路由过程示意图。
【具体实施方式】
[0044] 下面结合实施例对本发明作进一步的详细说明，但本发明的实施方式不仅限于 此。W下提到的节点与本发明要表达的手机端是一个概念，两者只是不同层面的不同叫法 而已。
[0045] 实施例：
[0046] 本实施例所述的基于蓝牙技术的手机自组通信网络Cell化t的组网和路由算法， 包括W下步骤：
[0047] (a)组网阶段:将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居 节点；
[0048] (b)更新阶段:实时更新当前节点的contact 1 i S t中各个邻居节点的信息；
[0049] (C)发送阶段：当前节点将普通数据包或者系统数据包发送至下一节点，系统数据 包是指入网和屯、跳相关的数据包，入网和屯、跳相关的数据包与后面要提到的handshake协 议(握手协议)和heartbeat协议（屯、跳协议)相关，普通数据包是指系统数据包W外的数据 包，比如普通文本信息，系统信息等；
[0050] (d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据 包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包；
[0051] 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是， 则本节点处理该数据包，并且不进行数据转发；
[0052] 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是 否大于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发；
[0053] (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。
[0054] 具体地，组网阶段的具体过程为：
[0055] (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节 点会根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表 示该节点可W加入该蓝牙网络，并根据收到的确认消息更新该节点的contact 1 i St，发送确 认消息的节点同时也更新自己的contactlist;
[0056] (a2)如果该节点收到的是拒绝消息，则组网失败。
[0057] 具体地，更新阶段的具体过程为：
[005引当某一节点启动时，该节点周期性地向其contactlist中的各个节点发送屯、跳消 息，根据各个节点是否做出回复来更新本节点contactlist中各个节点的状态；；
[0059] 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点；
[0060] 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。
[0061] 具体地，发送阶段包括普通数据包发送和系统数据包发送，所述普通数据包的发 送过程为：
[0062] (cll)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制 并发送消息；
[0063] (C12)如果是转发的，则直接发送；
[0064] 所述系统消息 的发送过程为：
[0065] (C21)从节点中取出该系统消息，并直接发送。
[0066] 具体地，所述路由阶段中，节点进行路由转发的具体过程为：
[0067] (dl)获取数据包已经排除的节点集；
[006引（d2)通过该节点的contactlist获得该节点的邻居节点集，并根据已经排除的节 点集，从邻居节点集中筛选出未被排除的节点；
[0069] (d3)把运些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新 的数据包转发给刚刚未被排除的节点集中的所有节点。
[0070] 具体地，步骤(d3)中，将未被排除的节点加入到待转发数据包中的具体过程为： [0071 ] ((131)当有节点想加入到￡：成〇111:;[叫中时，把该节点插入到1]136的口所指向的位置， 此时1]136的口自动向后移动一个位置，当InsedP到达末尾时，则重新指向ExRouting的第一 个位置;其中，ExRout ing和1]13純1口是待发数据包中的两个字段，ExRout ing是指在数据包 中已排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置；
[0072] (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
[0073] 下面用一个具体的实施例来说明本发明的实现过程，具体如下：
[0074] 首先，为了实现手机终端(节点）之间数据的传输，我们对节点之间的数据格式进 行明确的约定。Ce 1 INet的数据格式如表1。
[00巧]表1 Mesh化t数据格式
[0076]
[0077] 其中；
[0078] (1 )Type表示消息类型，占用IByte，可W如下取值：
[00巧]a)0000 0001 = SYN，普通消息
[0080] b)0000 0010 =皿，屯、跳消息
[0081] c)0000 0011=如ery，que;ry消息
[0082] d)0000 0100=ACK，对普通消息的确认消息
[0083] e)0000 0101=HBACK，对屯、跳消息的确认消息
[0084] f)0000 0110 = QACK，对que巧消息的确认消息
[0085] g)0000 0111= NQACK，对que巧消息的拒绝消息
[0086] (2)NetID表示的是网络号，占用IB^e，当有节点尝试接入某个网络时，该网络中 的节点收到如e巧信号时根据其化om_ID判断回复QACK还是NQACK;
[0087] (3)From_ID和To_ID分别表示消息的源端和目的端，根据手机固有的SequenceNO. 和用户输入的NickName确定，SN为12位的十进制数，NickName不超过20个字母，所WFrom_ ID 占用 32Byte;
[0088] (4)Seq_N0表示的是消息序列号，占用2Β^θ，其中65535,即mi mi mi mi 表示消息传输结束；
[0089] (5)ACK_N0表示当前消息是对上一个序列号为ACK_N0的消息的确定，占用2B^e;
[0090] (6)TTL表示的是消息在网络中存活的最长"时间"，用跳数衡量，是为了防止某一 个消息在网络中绕圈，占用IByte;
[0091 ] (7)化eckSum表示该消息的校验和，当消息初始化时，根据消息头计算得出，当收 到消息时再次根据消息头计算新的化ekSum，比较二者，若匹配则表示该传输没有错误，否 则表示传输出错。占用2Byte;
[0092] (8)InsertP表示应该更新的ExRouting的位置
[0093] (9)Content表示消息体，真正的数据信息放入其中，规定消息最大长度不超过 128Byte；
[0094] (10)ExRouting，B|3Exclude Routing,表示该消息已经通过的路由W及这些路由 的临近节点，相当于一个集合，该字段的长度足W容纳20个终端ID，即640Byte。
[0095] 另外，为了保证网络中各个手机终端(节点）能够实现可靠的数据传输，除了规定 的数据格式，还需要一定的协议作保障，如计算机网络中的TCP/IP协议。本发明的Cell化t 也有一套自己的协议作支持，包括hand化ake协议、headbeat协议、receive_msg协议、 sentSyn协议、semLSys协议和routing协议，其中协议都会设及到具体的消息格式和不同 的线程做处理，同时还会在每个手机终端维护一个contactList表，该表中存放的是当前手 机终端的邻居节点（即可W让消息直接到达的节点）。
[0096] (一化 andShake 协议
[0097] handshake协议主要解决的是当终端尝试接入网络时的问题。当终端尝试接入网 络时，它会向周围的网络发送QueiT消息，当收到对QueiT消息的确认消息即QACK消息时表 示该终端可W加入已有网络，根据收到的QACK消息更新当前终端的contactList。
[0098] (1)与hand化ake协议对应的消息格式如表2所示，
[0099] 表2如e巧消息格式 rnmnl
[0101] (2)与hand化ake协议对应的线程的流程图如图1所示。
[0102] (二化 ea;rtbeat 协议
[0103] headbeat协议主要解决的问题是实时更新contactList表中的各个节点的信息。 当手机终端启动时，手机终端将周期性地向其contactList表中的各个节点发送皿消息，然 后根据运些节点的响应情况动态更新contactList表。
[0104]与heartbeat协议对应消息的格式如表3所示，
[01化]表3皿消息格式 [0106]
[0107] (1)与heartbeat协议对应线程heartbeat线程的流程图如图2所示。
[010 引（S)send_Syn 协议
[0109] sen tSyn协议主要解决的是发送普通文本消息的问题，当终端的Send_Syn中有待 发送的数据时，与sencLSyn协议对应的sencLSyn线程将发送消息，并且该线程会根据所发 送消息的类型采取不同策略。
[0110] (1)与send_Syn协议对应的send_Syn线程的流程图如图3所示。
[0111] (四）send_Sys 协议
[0112] sentSys协议主要解决的是发送QueiT消息和皿消息的问题，当终端的Send_Sys 中有待发送的数据时，与sencLSys协议对应的sencLSys线程将发送消息，并且该线程会根 据所发送消息的类型采取不同策略。
[0113] (1)与send_Sys协议对应的send_Sys线程的流程图如图4所示。
[0114] (五)receive_msg 协议
[0115] receive_msg协议主要解决的是接收消息的问题，主要是根据收到的不同消息类 型作相应的响应动作，与receive_msg协议对应的receive_msg线程负责接收消息的一系列 动作。
[0116] (l)receive_msg线程的流程图如图5所示。
[0117] (六);routing 协议 [011引 1.概述
[0119] 该部分描述了 Cell化t路由协议，制定了在Cell化t网络中数据包的转发规则。此 协议的运用是在基于蓝牙或WLAN数据传输上的，也就是数据包的传输是利用蓝牙或WLAN进 行的，而在每个节点上应用本节所描述的协议进行数据转发。
[0120] 2.限制条件
[0121] 蓝牙：一种支持设备短距离通信的无线电技术，目前最远的传输距离能扩大到 100m。
[0122] WLAN:利用无线技术在空中传输数据、话音和视频信号。目前的传输距离也达到了 100m。
[0123] 邻居节点最大个数:每个节点允许有自己的一些邻居节点，但是每个节点只能容 纳最多20个邻居节点。
[0124] 目地节点:数据包最终要传输到的节点。
[01巧]数据包了化:数据包最多在网络中经过20hop。
[01%]已处理数据包表中数据存活时间：最大不能超过8s。
[0127] 3.协议描述
[012引 （1)路由过程
[0129]在整个CelWet网络中，每个节点都承担着数据接收和数据转发的功能。每个节点 维护两张表，一张是通过化artBeat机制维护邻居节点表(参见表4)，允许最大的节点数是 20个;另外一张表是已处理数据包表(参见表5)，一条记录允许的最大时间8秒。
[0130] 一个节点收到另外一个节点转发来的数据包时，首先通过已处理数据包表查看是 否已经处理过该数据包，如果已经处理过，则丢弃该数据包，否则进行下一步。
[0131] 如果没有处理过该数据包，则查看该数据包的转发目的地是否是本节点，如果是 则本节点处理该数据包，并且不进行数据转发;如果该数据包的转发目的地不是本节点，贝U 查看数据包中的TTL的值是否大于20，大于20就直接丢弃该数据包，否则本节点进行路由转 发。
[0132] 如果一个节点进行路由转发，首先根据数据包里的ExRouting字段获得该数据包 已经排除的节点集(排除的节点是指该数据包在W后转发的过程中，不会转发给已经排除 的节点），接着从邻居节点表中获得该节点的邻居节点集，然后在邻居节点集中根据已经排 除的节点集筛选出未被排除的节点，把运些未被排除的节点加入到待转发数据包的 ExRouting字段中，加入后，就把修改的数据包转发给刚刚未被排除的节点集中的所有节 点。相关流程可参见图6。
[0133] (2)邻居节点表
[0134] 表4邻居节点表
[0135]
[0136] 如果节点经过化op就能把数据传递给对方，则双方互称为邻居节点。运张表允许 的最大记录数是20。
[0137] 如果是一个节点想要加入一个网络，当发送que巧消息后，收到QACK消息回复后， 则把回复消息的节点加入邻居节点表。
[0138] 如果一个网络中节点 收到另一个想要加入网络节点发出的quen^消息后，如果同 意加入，则把该节点加入自己的邻居节点表中。
[0139] 用heart beat来维护邻居节点表。
[0140] (3)已处理数据包表
[0141] 表5已处理数据包表
[0142]
[0143] 当数据包的目的地是本节点或本节点对该数据包进行了转发，则把数据包的相关 信息记录在已处理数据包表中。一条记录存在的最大时间为8秒，如果超过了该时间，则把 该记录移除。
[0144] (4化xRouting字段节点加入过程
[0145] 在数据包中，有两个字段，分别是ExRouting和InsedPsEsRouting是指在数据包 中已经排除的节点列表；InsertP是指下一个节点加入到ExRouting中的位置。当有节点想 加入到ExRouting时，就把该节点插入到Ins&rtP所指向的位置，此时InsedP自动向后移动 一个位置，当InsedP到达末尾时，则会重新指向ExRouting的第一个位置。
[0146] 如果要加入的节点在Exrouting已经存在时，则该节点不会再次加入。
[0147] (5)路由实现 [014引①线程
[0149] 路由协议由Ξ个线程组成，一个线程是routing用来路由，一个线程是heart beat 线程用来维护邻居节点表，一个线程是check_pack_time用来维护已处理数据包表。
[0150] 当receive_msg线程收到一个要路由的数据包，则通知路由线程routing,并把数 据包传递给routing线程，如果需要转发该数据包，则routing线程通知send_msg线程，把新 的数据包传递给sencLmsg线程。
[0151] CellNet中各个线程完成不同的功能，除了 W上提到的线程外，CellNet中还有一 个线程用于上层APP的消息请求一一service线程。为了使各个线程能够有效的协作， Cel INet 在主线程中创建Send_Syn、Send_Sys、Msg_Queue、40(_如6116、HBACK_Queue、QACK_ Queue、ContactList等资源，从而使得线程之间能够有效的交互数据。其中，
[0152] (l)Send_Syn用于存放将要发送的文本消息；
[0153] (2)Send_Sys用于存放系统消息，如皿消息和如eiy消息；
[0154] (3)Msg_Queue用于存放收到的普通消息；
[01W] (4)ACK_Queue用于存放对普通消息确认的消息；
[0156] (5)HBACK_Queue用于存放皿消息的回复消息；
[0157] (6) QACK_Queue用于存放如eiy消息的回复消息。
[015引（二)线程间关系概要如表6，
[0159]表6线程关系 「01601
[0161] ~(l)query线程与其它线程的关系如图7所示，
[0162] 线程执行的逻辑顺序如下：
[0163] ① query线程将待发送的如日巧消息放入Send_Queue中，然后等待该消息的QACK消 息；
[0164] ②send_msg线程从Send_Queue取出待发送的如eiy消息、发送；
[01化]③receive_msg线程将受到的QACK消息放入QACK_Queue中；
[0166] ④query线程将对如eiT消息确认的QACK消息从QACK_Queue中取出、更新当前终端 的 contactList表。
[0167] (2化eadbeat线程与其它线程的关系如图8所示，
[0168] 线程的逻辑执行顺序如下：
[0169] ① heartbeat线程将皿小放入SemLQueue中，然后等待对运些消息响应的HBACK_ 如eue消息；
[0170] ②send_msg线程从Send_Queue中取出皿消息、发送；
[0171 ] ③receive_msg线程将收到的HBACK消息放入HBACK_Queue中；
[0172] ④heartbeat线程从HBACK_Queue中取出对皿响应的HBACK消息、更新contactList 表。
[0173] (3)service线程与其它线程的关系如图9所示，
[0174] 上层应用直接通过调用service线程提供的服务，把待发送的消息放入Send, 如eue中，并把Msg_Queue中的消息取出。
[0175] 如图10所示，A节点为起始节点，B节点为目的节点，A节点向下一节点发送数据包， 下一节点在接收数据包时，首先通过自身的已处理数据包表来判断该数据包是否被本节点 处理过，如果未被处理过，则查看该数据包的转发目的地是否为本节点，如果不是，则更新 该数据包中的发送节点并转发给运些发送节点，直到最后数据包转发到目的节点B，从而实 现了数据包在发送过程中动态生成整个路由路径A^B。
[0176] 本发明已经通过上述实施例进行了说明，但应当理解的是，上述实施例只是用于 举例和说明的目的，而非意在将本发明限制于所描述的实施例范围内。此外，本领域技术人 员可W理解的是，本发明并不局限于上述实施例，根据本发明的教导还可W做出更多种的 变型和修改，运些变型和修改均落在本发明所要求保护的范围W内。
【主权项】
1. 基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法，其特征在于:包括以 下步骤： (a) 组网阶段:将节点接入到蓝牙网络中，并更新该节点的contact1ist中的邻居节点； (b) 更新阶段:实时更新当前节点的contact1ist中各个邻居节点的信息； (c) 发送阶段:当前节点将普通数据包或者系统数据包发送至下一节点； (d) 路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据包表 来查看该数据包是否已经处理过，如果是，则丢弃该数据包； 如果该数据包未被处理过，则查看该数据包的转发目的地是否为本节点，如果是，则本 节点处理该数据包，并且不进行数据转发； 如果该数据包的转发目的地不是本节点，则查看数据包中的消息存活时间TTL是否大 于20hop，如果TTL大于20hop，则直接丢弃该数据包，否则本节点进行路由转发； (e)接收阶段:下一节点根据收到的数据包类型，作出相应的响应动作。2. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述组网阶段的具体过程为： (al)当有节点尝试接入蓝牙网络时，该节点会发出请求信号，该蓝牙网络中的节点会 根据收到请求信号而回复确认消息或拒绝消息；如果该节点收到的是确认消息，则表示该 节点可以加入该蓝牙网络，并根据收到的确认消息更新该节点的contact1ist，发送确认消 息的节点同时也更新自己的contact1ist; (a2)如果该节点收到的是拒绝消息，则组网失败。3. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述更新阶段的具体过程为： 当某一节点启动时，该节点周期性地向其contact1ist中的各个节点发送心跳消息，根 据各个节点是否做出回复来更新本节点contact1ist中各个节点的状态； 如果一个节点回复确认信息，则继续将该节点视为本节点的邻居节点； 如果一个节点不回复确认消息，则将该节点从本节点的邻居节点集中删除。4. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述发送阶段包括普通数据包发送和系统数据包发送，所述普通数据包的 发送过程为： (cl1)判断普通数据包的源地址，如果是源地址和本地地址相同，则增加重发机制并发 送消息； (cl2)如果是转发的，则直接发送； 所述系统消息的发送过程为： (c21)从节点中取出该系统消息，并直接发送。5. 根据权利要求1所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述路由阶段中，节点进行路由转发的具体过程为： (d1)获取数据包已经排除的节点集； (d2)通过该节点的contact1ist获得该节点的邻居节点集，并根据已经排除的节点集， 从邻居节点集中筛选出未被排除的节点； (d3)把这些未被排除的节点加入到待转发数据包中，得到新的数据包，然后把新的数 据包转发给刚刚未被排除的节点集中的所有节点。6.根据权利要求5所述的基于蓝牙技术的手机自组通信网络CellNet的组网和路由算 法，其特征在于:所述步骤(d3)中，将未被排除的节点加入到待转发数据包中的具体过程 为： (d31)当有节点想加入到ExRouting中时，把该节点插入到InsertP所指向的位置，此时InsertP自动向后移动一个位置，当InsertP到达末尾时，贝lj重新指向ExRouting的第一个位 置;其中，ExRouting和InsertP是待发数据包中的两个字段，ExRouting是指在数据包中已 排除的节点列表;InsertP是指下一个节点加入到ExRouting中的位置； (d32)当要加入的节点已存在ExRouting中时，则该节点不会再次加入。
【专利摘要】基于蓝牙技术的手机自组通信网络CellNet的组网和路由算法，包括以下步骤：(a)组网阶段：将节点接入到蓝牙网络中，并更新该节点的contactlist中的邻居节点；(b)更新阶段：实时更新当前节点的contactlist中各个邻居节点的信息；(c)发送阶段：当前节点将普通文本消息或者系统消息发送至下一节点；(d)路由阶段：当一个节点接收到另一个节点转发来的数据包时，通过已处理数据包表来查看该数据包是否已经处理过，如果是，则丢弃该数据包，反之则进行下一步；(e)接收阶段：下一节点根据收到的不同消息类型，作出相应的响应动作。本发明采用上述方法，能够减小路由开销，减轻网络负担，避免网络拥堵。
【IPC分类】H04W4/00, H04W40/04
【公开号】CN105491508
【申请号】CN201510381635
【发明人】汤羽
【申请人】汤羽
【公开日】2016年4月13日
【申请日】2015年6月30日
最新回复(0)