嵌入式无线自组织网络中对广播消息的转发的管理方法

摘要

本发明公开了一种嵌入式无线自组织网络中对广播消息的转发的管理方法，包括，当无线自组织网络节点接收到广播信息时，提取广播信息中的广播发送节点的邻居列表N1；提取本节点1跳邻居列表N2；将邻居列表N1和本节点1跳邻居列表N2进行对比并取交集，将交集中包含的节点按照节点的序列号进行排序，形成虚拟序列；接收到广播信息的无线自组织网络节点判断接收的广播信息是否是从源节点发出的广播，如果是从源节点发出的广播则按照上述虚拟序列依次转发广播，如果不是从源节点发出的广播则等待固定时间间隙后再按照上述虚拟序列依次发送广播。满足在无线多跳网络中实现稳定可靠的广播通信的要求。

说明书

技术领域

本发明涉及通信领域，具体地，涉及一种嵌入式无线自组织网络中对广播消息的转发的管理方法。

背景技术

无线自组织网络是一种建立在无中心架构上的自适应网络。它的特点是节点间的通信完全是自我管理，并且不存在中心管理单元。其原因在于各节点的分布是随机无序的，当节点间的物理距离超过有效点对点通信距离时，即使存在中心控制单元也无法直接进行管理。因此，无线自组织网络中的节点通常是自我管理信息收发过程。由于无线信号在空中传播，不同的信号有可能在空中碰撞，产生冲突，严重的时候接收机甚至无法还原有效信号，导致接收失败。这种情况在广播消息的传播过程中比较明显。常用的无线通信可以分为单播，组播和广播。组播是广播消息的一种特例。因为广播的目的是为了将消息传播到网络中的每个节点，接收到广播消息的节点将进行广播转发。如果没有有效的规划，将会在网络内形成广播风暴，产生严重阻塞。相比较而言，单播虽然也会产生冲突，但是单播消息只在指定的节点之间进行通信，全网冲突的机会相对较低。

采用不同的无线技术，冲突的方式和几率也会有不同，其中以采用FDMA方式进行通信的设备遇到的情况最为普遍。经常被用来建立无线自组织网络的无线技术包括，但不局限于，蓝牙，WIFI,IEEE802.15.4等标准。其中，蓝牙技术采用跳频的方式（1600跳/秒），在传输过程中数据的每一部分可能在不同的相对窄带（1MHz）的84MHz频率带中发送。通过事先分配的方式，蓝牙设备互相干扰的几率被降到很低的程度，但是这个方式依赖于主设备的存在，即蓝牙所采用的主从工作模式。因此蓝牙很少被用来作为大范围组网的无线技术。WIFI技术采用直接扩频（DSS）FDMA的工作方式，将无线频率划分为不同的相对较宽的信道（20/22MHz）。互通的节点必须工作在相同的信道上，并且在通讯过程中不会切换到其他信道。当有多个设备同时发起通信时，信道不够就会产生无线冲突（信号干扰）。在单播通信进行时，WIFI技术采用载波侦听和退避的算法来减轻冲突的影响。当有数据发送时，设备先检测当前信道的繁忙程度，如果有其他信号或者能量被探测到，则采用随机后退的方式等待下一次机会。IEEE802.15.4也使用FDMA工作方式，并且采用和WIFI技术类似的算法来避免冲突。

在完全随机的情况下，这种方式可以允许独立的节点在有通信需求时使用竞争的方式来接入无线媒介，以获得最快速的响应。并且在通信不成功，比如载波侦听时候遇到信道繁忙，或者通信没有收到预期的应答时候，节点可以通过后退来退避繁忙，或者重新发送来确保数据的成功传递。但是在广播的情况下，由于网络内太多的不确定性，重发机制一般不会采用。当数据包被广播出去后，发送节点没有可靠的手段来确认消息是否被成功投递。

虽然无线广播有以上所述的局限性，但是在无线自组织网络中，因为缺乏有效的中心管理单元，很多机制的实现仍旧依赖于广播方式，比如路由生成过程中，为了从互不相连的节点群中定位出从源节点到目的节点的有效路径，广播通常被使用来询问和返回路由信息。为了使广播消息能够顺利达到目的地，并且考虑到广播会带来大量的转发工作，因此最有效的方式并不是类似于单播通信使用的竞争方法，而是尽可能地使广播的转发有序进行。

如图1演示的无线多跳网络中的广播情况中，不同的方框代表不同的节点，连线上的数字表示第几次广播（转发）。假设节点1发出广播后，标记为1的连线表示该广播第一次发送会分别到达节点2，4，9。以节点2为例，当收到广播消息后，节点2需要转发广播，形成到达节点8和5的2次转发（标记为2的从节点2出发的连线）。对节点9来说，也会形成到达节点3和5的2次转发。其他节点会进行类似转广播的过程，直到网络中所有节点都收到信息。这里的问题在于，因为节点2和9是同时收到节点1发出的广播，如果同时进行2次转发广播，将会使得信号在节点5重叠，导致节点5接收失败。

虽然有一些广播优化的算法，比如OLSR路由协议中MPR节点的选择，可以在达到相同效果的前提下降低转发广播的节点数量，但同样需要基于广播通信的顺利进行。

发明内容

本发明的目的在于，针对上述问题，提出一种嵌入式无线自组织网络中对广播消息的转发的管理方法，以实现无线多跳网络中广播通信稳定可靠的优点。

为实现上述目的，本发明采用的技术方案是：

一种嵌入式无线自组织网络中对广播消息的转发的管理方法，在无线自组织网络节点的两跳范围邻居列表和节点间天然形成的顺序关系能够使用的条件下，

包括以下步骤：

步骤1、当无线自组织网络节点接收到广播信息时，提取广播信息中的广播发送节点的邻居列表N1；

步骤2、提取本节点1跳邻居列表N2，本节点即上述步骤1中接收到广播信息的无线自组织网络节点；

步骤3、将上述步骤1中的广播发送节点的邻居列表N1和步骤2中的本节点1跳邻居列表N2进行对比并取交集，将交集中包含的节点按照节点的序列号进行排序，形成虚拟序列；

步骤4、接收到广播信息的无线自组织网络节点判断接收的广播信息是否是从源节点发出的广播，如果是从源节点发出的广播则按照上述虚拟序列依次转发广播，如果不是从源节点发出的广播则等待固定时间间隙后再按照上述虚拟序列依次发送广播。

优选的上述步骤3中的虚拟序列是按照节点序列号由小到大进行排列的。

优选的上述步骤3中的虚拟序列是按照节点序列号由大到小进行排列的。

优选的上述步骤4中，如果不是从源节点发出的广播则等待固定时间间隙后再按照上述虚拟序列依次发送广播中的固定时间，该固定时间要允许本节点的大多数邻居节点完成当前批次的广播转发。

一种嵌入式无线自组织网络中对广播消息的转发的管理方法，基于DSP实现，即每个无线自组织网络节点上均设置DSP，DSP作为信号的调制解调模块，当DSP对接收的广播信息完成数据解码后，如果检查到该帧是广播帧，则立刻进入虚拟排序算法，虚拟排序算法为基于本发明技术方案的嵌入式无线自组织网络中对广播消息的转发的管理方法的算法，DSP接收的广播信息经解码和帧还原处理后上报上层协议，上层协议在解析完成后，如果决定进行数据转发，则直接交回DSP，在虚拟排序算法拟定的时间点转发广播，由于DSP本身具有存储能力，上层协议定期将节点的两跳范围内的邻居节点信息更新到DSP的存储空间。

本发明的技术方案具有以下有益效果：

本发明的技术方案，通过对发送节点的邻居列表N1和节点1跳邻居列表N2进行对比，得出交集，并对交集进行排序后，按照排序依次转发广播信息，避免节点接收广播信息时的冲突，从而不依赖任何中心管理手段，只在单个节点上运行的管理，就能帮助节点有序管理广播转发次序，以实现无线多跳网络中稳定可靠的广播（转广播）通信。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为现有技术中无线多跳网络中的广播的示意图；

图2为两跳范围邻居列表形成过程示意图；

图3为依据本发明所述的管理方法形成的转发广播的虚拟排序示意图；

图4为发明所述的管理方法的具体实施示意图；

图5为本发明所述的管理方法的流程图；

图6为本发明所述的管理方法在DSP上的实现的原理框图。

具体实施方式

以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

在经常使用的无线多跳网络协议中会使用周期性发送本地广播消息的方式来表明节点的有效存在性，这个消息被统称为“HELLO”消息。为了控制广播消息对网络的阻塞，HELLO消息不会被转广播。通过在HELLO消息中携带节点的邻居信息，并和其它节点进行交换，可以建立一跳和两跳邻居列表。图2演示了无线多跳网络中节点如何建立两跳范围内的邻居列表。

图2中，节点5发送HELLO消息，节点3和节点4收到后会将节点5作为1跳邻居。同样，节点3，4和节点6发送HELLO消息后，相应的节点会把发送HELLO消息的节点作为1跳邻居。以节点3为例，可以形成1跳邻居列表，其中包括4,5,6节点。当HELLO消息不断交换后，每个节点开始完善自己的1跳邻居列表，并且把该邻居列表附加到自身发出的HELLO消息中。当其他节点接收到扩展的HELLO消息后，可以生成与自身相距2跳的邻居列表。以节点4为例，通过收集1跳范围内的HELLO消息，节点4随后产生的HELLO消息可以加入自己的1跳邻居，包括1,2,7,3,5,6。当节点3收到节点4的扩展HELLO消息后，将节点1，2，7，3，5，6和自己的1跳邻居做比较，过滤掉重复节点4,5,6，就可以生成2跳邻居列表，7,2,1，并且总结出这些2跳邻居需要通过节点4才可以到达。

图2中节点3的邻居列表如表一所示：

表一、节点3的邻居列表：

。

图2中节点4的邻居列表如表二所示：

表二、节点4的邻居列表：

。

由于大多数无线通信中节点的标记是使用规定长度的比特位来表示的，使得节点的身份标识可以用数字来表示。以IEEE802.15.4技术作为参考，节点的网络地址使用2个字节（16个比特位）来表示，地址范围从0到65,535。因此，任意节点之间必然可以利用地址的大小来产生相对关系。利用数字大小，每个节点可以针对所侦听到的邻居节点做出排序，排序规则可以是任何方式。比如按照从小到大的原则，在图2中，节点3可以在1跳邻居中排列出3，4，5，6的顺序。

当两跳范围的邻居列表和节点间天然形成的顺序关系这两种信息可以使用时，广播转发就可以采用本发明所提出的方法来规范。

如图5所示，一种嵌入式无线自组织网络中对广播消息的转发的管理方法，包括，步骤1、当无线自组织网络节点接收到广播信息时，提取广播信息中的广播发送节点的邻居列表N1；

步骤2、提取本节点1跳邻居列表N2，本节点即上述步骤1中接收到广播信息的无线自组织网络节点；

步骤3、将上述步骤1中的广播发送节点的邻居列表N1和步骤2中的本节点1跳邻居列表N2进行对比并取交集，将交集中包含的节点按照节点的序列号进行排序，形成虚拟序列；虚拟序列包含当前节点；

步骤4、接收到广播信息的无线自组织网络节点判断接收的广播信息是否是从源节点发出的广播，如果是从源节点发出的广播则按照上述虚拟序列依次转发广播，如果不是从源节点发出的广播则等待固定时间间隙后再按照上述虚拟序列依次发送广播。

优选的上述步骤3中的虚拟序列是按照节点序列号由小到大进行排列的。

优选的上述步骤3中的虚拟序列是按照节点序列号由大到小进行排列的。

优选的上述步骤4中，如果不是从源节点发出的广播则等待固定时间间隙后再按照上述虚拟序列依次发送广播中的固定时间，该固定时间要允许本节点的大多数邻居节点完成当前批次的广播转发。

在无线自组织网络中，当节点接收到广播消息时，为了准备转发广播，会根据之前已经获得的两跳邻居信息来推断可能会进行转发广播的节点。然后系统会对推断出的潜在转发节点进行排序，使用节点自身序列号作为排序依据，推断出虚拟转发次序。虚拟转发次序代表了节点转发广播的顺序，其中包括当前节点。在其他节点转发时，当前节点保持安静。当轮到当前节点时，进行转广播。根据之后提供的算法，每个节点都能推断出相对一致的虚拟转发次序，并在当前节点轮到转发时候才进行广播转发，以此尽可能避免冲突。如图3所示。

假设节点2,3,4已经总结出邻居列表。以节点2为例，当节点1发起第一次广播后，节点2推断出邻居节点3和4也会进行转发广播（图中为广播2），并形成虚拟转发次序2,3,4。这里以节点的序列号按照从小到大的规则排序，并规定序列号越小，转发优先次序越高。因此，节点2会第一个进行转发。同理，在节点4上也生成相同的转发次序2,3,4。因为序列号4在转发次序中为最大，所以节点4主动等待两个转发时间间隔，以确保节点2和节点3的转广播可以被其他节点顺利接收。当等待过两个转发间隔，虚拟序列轮到节点4的时候，节点4进行转发广播。

如图4所示，假设所有节点已经完成2跳邻居表的建立，并且广播消息由节点6发起。经过第一次广播后，到达节点5,2,4,10。

节点5：在2跳邻居列表建立时，节点5也同时获知节点6的邻居信息。因为广播消息是从节点6发出的，通过对比节点6的邻居信息，筛选出节点10，4，2，5为受影响节点。因为这些节点是节点6的邻居节点，它们可以收到广播消息，并可能做出进行转发的决定，进一步影响节点5的转发。考虑到真正会影响到节点5转发广播的节点是节点5的一跳邻居节点，因此，节点5将自己的邻居节点，也就是6,2,1和之前的结果进行比较。节点6先被排除，因为这是广播的发起者。节点1因为不在节点6的邻居列表里，所以不会收到节点6的广播，也可以排除。节点2既是节点6的邻居，也是节点5的邻居，可以确定如果节点2转发广播，将有可能和节点5冲突。

节点2：和节点5的分析过程类似，节点2先筛选出节点6的邻居节点，10，4，2，5。节点2的1跳邻居节点包括1,5,6,7,8,9。因为节点1,9,7,8不是节点6的邻居节点，所以它们不会为当前收到的广播消息进行转发。因为节点10,4不是节点2的1跳邻居节点，所以节点2也可以忽略这两个节点。因此，节点2需要顾及到的会相互影响的节点为5。

由此，节点5和节点2分别推测出对针对转发广播2（用数字2标记的箭头），有两个节点会互相影响。由于节点自身的标记5和2已经具备相对大小关系，节点2会在较早的时间间隙开始转发。节点5会故意推迟转发，以和节点2错开对空间的占用。

同时接收到广播1的节点还有4，根据以上描述的推断方法，节点4没有找到会互相影响的转发节点，因此可以在任何时候进行转广播。

类似的，节点1收到节点2转发广播后，通过分析节点2的邻居（也就是通过节点2获得的关于节点1的2跳邻居）和节点1自己的1跳邻居，可以判断出节点5,9会和自己产生转发冲突。而节点9可以分析出，只有节点1会在自己转发广播时候产生冲突。

需要注意的是，节点1分析从节点2收到的广播时，通过分析数据包中常带的跳数信息，会发现这是该广播的第二次发送（标记为2的箭头），为了确保其他进行第二次广播的节点能顺利完成发送，节点1需要主动延迟一段时间进入第三次转发过程（标记为3的箭头），同理，节点9也需要推迟一段时间。这个时间间隔可以是固定间隔，以保证节点1和节点9的第三次转发广播进程处在相同的时间起点。因为节点1和节点9是在相同的时间收到节点2的广播，因此这个同时进行相同长度的延迟是可以实现的。对于节点1来说，它遵循的发送顺序为1,5,9。而对于节点9来说，它遵循的发送顺序为1,9。虽然从排列的次序来比较，5和9会在同一时刻，但实际情况中很少或者不会冲突，因为：

（1）本例中节点5和9处在不同的物理位置。相同时间开始发送数据不会互相影响。

（2）如果节点5和9处在相近的位置，节点9在总结邻居节点时会把节点5包括进去，从而推断出和节点1一样的发送顺序：1,5,9，广播冲突仍旧可以避免。

在本例中，节点5的转发进程在第二次转发广播中完成（标记为2的箭头），因此节点5并不会真正参加第三次转发。

另外，以图4为例，节点9可能会收到从节点1或者节点2发来的广播，并进入第三次或者第四次转发过程（标记为3(4)的箭头）。节点3和节点7也会有类似的情况。在实际应用中，因为这是相同的广播内容，上层协议会自动过滤，所以只会出现一次转发广播。

当节点收到广播消息后：

分析该广播的发送（转发）者信息，并从本地信息中获取该发送（转发）者的邻居信息N1。同时将本节点的1跳范围内的邻居节点N2信息提取出来。

比较两组邻居节点信息，提取重合的节点。

将重合节点以及本节点进行排序，使用节点自身的序列号，可以按照从小到大，或者从大到小规则，并且指定序列号越小（或者越大）的节点有更高的发送优先权。序列可以用{node1,node2,…nodeN}来表示。

判断广播消息的来源。如果是从源节点发出的广播，立刻按照排定的虚拟次序进行等待，直到当前节点可以进行广播。如果不是从源节点发出的广播，等待固定周期Tbackoff后开始按照排定次序进行转发。Tbackoff的长度可以由用户指定，原则上要允许大多数邻居节点完成当前批次的广播转发。

当在虚拟队列中排在当前节点之前的节点被认为已经完成广播发送后，当前节点开始转发广播。

本发明提出的虚拟广播排序方法涉及到排序和等待时间的问题，即每次虚拟队列的等待开始时间要尽可能同步。对于一个节点来说，最合适的开始排序算法的时间点是当前广播信息接收完成时。一般的无线系统会把从无线电收到的消息存储在缓存中，在合适的时候，比如中断发生时，才汇报给上层系统，由此会带来一定的延迟。考虑到算法会需要一些存储空间和变量的使用，并且在接收完数据后就开始排序过程，因此提出在数字信号处理模块（DSP）中实现。即每个节点上均设置DSP芯片，DSP作为信号的调制解调模块。如图6所示，当DSP完成数据解码后，如果检查到该帧是广播帧，可以立刻进入虚拟排序算法。上层协议在解析完成后，如果决定进行数据转发，则直接交回DSP，在排序算法拟定的时间点进行转广播。由于DSP本身具有存储能力，上层协议只需定期将节点的2跳范围内的邻居节点信息更新到DSP的存储空间，就可以完成预定任务。

最后应说明的是：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。