一种基于路由邻居表建立无线传感器网络路由的方法

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明进一步详细说明。

本发明的核心思想是：通过使用路由邻居表来保存网络局部的拓扑信息和链路信息，基于贪婪算法的思想，通过路由邻居表中的信息计算局部最优的解，通过局部最优解获得全局的最优路由路径。

所述路由邻居表是一个记录本地节点邻居节点信息的表格，每个表项对应一个邻居节点，它主要包括四个域：邻居节点ID号、本地节点和邻居节点之间链路质量信息、邻居节点的梯度和邻居节点的出度。

所述网络中的每个节点会周期性的广播路由维护包，这些路由维护包主要包含以下信息：

发送节点的梯度信息；

发送节点的路由邻居表中保存的所有邻居节点的ID号；

发送节点的出度信息。

每个收到该路由维护包的节点(包括sink节点)，首先检查自己的路由邻居表中每个表项的邻居节点ID号域，如果某个表项中保存的ID号和发送该路由维护包的节点的ID匹配，那表示发送路由维护包的节点已经在本地节点登记过了。这种情况下需要对匹配的表项进行更新工作，本地节点检查路由维护包中捎带的发送节点的邻居节点ID号信息，如果本地节点的ID号在发送路由维护包的节点的邻居表中，表示发送路由维护包的节点收到过本地节点发送的路由维护包，这表示本地节点和发送路由维护包的节点之间的无线链路是对称的，可以将对应表项中的“本地节点和邻居节点之间链路质量信息”域标识为对称；如果本地节点的ID号不在发送路由维护包的节点的邻居表中，则将“本地节点和邻居节点之间链路质量的信息”域标识为非对称。

当收到该路由维护包的节点在自己的路由邻居表中找不到和发送该路由维护包的节点的ID相匹配的表项时，需要进行登记操作，这种情况下本地节点在自己的路由邻居表中找到一个空的表项，将发送该路由维护包的节点的ID号记录在该表项的“邻居节点ID号”域中，“本地节点和邻居节点之间链路质量信息”域的计算采用和上面一样的方法。

上述计算“本地节点和邻居节点之间链路质量信息”域的值的方法，称为链路对称性检查。这个检查是很必要的，无线信道和有线信道有很大的不同，那就是非对称性。如图1所示，图1为本发明提供的物理链路非对称性描述的示意图。A节点在B节点的通信范围内，但是B节点不在A节点的通信范围内。造成这种不对称现象的原因很多，可能是硬件上的问题，比如两者的天线的灵敏度不一样；可能是能量的问题，电量多的节点通信范围要大一些；还有可能是位置的原因，同一个节点放在桌子上的通信距离肯定要比放在地板上的要大。不管是那种原因，总之在无线链路中，链路的非对称性是一个很普遍的现象，在工程实现中需要考虑清楚。将链路的对称性作为路由算法的一个参数可以提高路由的稳定性，增强网络的可靠性。

上面介绍了路由邻居表中的“邻居节点ID号”域和“本地节点和邻居节点之间链路质量信息”域的维护过程，接下来介绍“邻居节点的梯度”域的维护过程以及它的作用。这里所述的梯度本质上是传感器节点到sink节点的跳数，如图2所示，图2为本发明提供的网络梯度描述的示意图。网络中的sink节点的梯度保持为0，其它的传感器节点初始的时候梯度设置为无穷大(可以用一个很大的整数代替)，表示不能直接和sink节点通信。

每个路由维护包都会捎带发送节点的梯度信息，接收到路由维护包的节点首先通过链路对称性检查获得本地节点和发送节点之间的链路质量信息，并且对相应的邻居表项的“邻居节点ID号”域和“本地节点和邻居节点之间链路质量信息”域进行维护，同时将路由维护包捎带的节点梯度信息记录到“邻居节点的梯度”域中。

到此只是完成了简单的邻居节点梯度的维护工作，还需要使用收到的路由维护包进行进一步的计算，以更新本地节点的梯度值。如果发送路由维护包的节点梯度值比本地节点的梯度值小，并且差值大于1，同时两者的链路也是对称的，那表示本地节点的梯度需要重新计算。比如在网络刚开始运行的时候，sink周围的节点收到了sink的路由维护包，此时本地节点的梯度为无穷大，发送路由维护包的节点的梯度为0，如果两者的链路是对称的，那么本地节点可以将自己的梯度改为1。梯度为1的节点如果再次收到sink节点的路由维护包，这时即使两者之间的链路是对称的，也不进行梯度的更新，因为梯度的差值不大于1。但是如果一个梯度为2的节点移动到了sink的一跳范围内，当其收到sink的路由维护包后，如果检查发现链路是对称的，那么它就将自己的梯度改为1。基本的计算公式是：

if Degree_receiver-Degree_sender＞1 then Degree_receiver＝Degree_sender+1

上述公式成立的条件是发送(sender)路由维护包的节点和接收(receiver)节点之间的链路是对称的，Degree_receiver表示接收节点(即本地节点)的梯度，Degree_sender表示发送路由维护包的节点的梯度。

如果发送(sender)路由维护包的节点和接收(receiver)节点之间的链路是不对称或者不满足梯度差大于1的条件，那么就不进行本地节点的梯度更新工作。

上面介绍的是网络中的节点通过接收路由维护包维护自己的在网络中的梯度的方法。梯度是本发明提出的路由算法中支持网络运行的一个最基本的参数，数据按照梯度从高到低向sink节点扩散。梯度的维护在整个网络的生存期中都在进行，由于无线信道的不稳定、信道干扰以及节点的失效等原因会造成网络拓扑的改变，这些会引起节点梯度的改变。现在需要讨论的一个问题是节点的采用更新后的梯度的时机问题。由于路由维护包是周期发送的，如果接收节点在收到每个路由包后就修改节点的梯度值，那么周围邻居节点保存的就是该节点过期的梯度值，比较恰当的做法是在节点广播自己的路由信息的时候同时启用更新后的梯度值。

下面介绍如何维护路由邻居表中的“邻居节点的出度”域，“邻居节点的出度”域的参数值可以直接从路由维护包中的“发送节点出度信息”中获得。这里说明节点的出度的概念，所谓节点的出度是借用网络图论中的概念，用有向图中节点的射出线的条数表示该节点转发数据的能力。

每个节点都可能有一个或多个邻居节点可以作为数据包的下一跳转发节点，这种节点越多，在有向图中可以表示为从该节点引出的线条越多，这表示该节点出度越大，节点的数据转发能力越强。当一个节点发送路由维护包的时候，它会查找路由邻居表，那些梯度比自己小，而且和自己之间的无线链路状况为对称的节点都可以当作其下一跳转发节点，这样的节点有几个就表示本节点的出度是多少，这个数据作为“发送节点出度信息”被放在路由维护包中。这里节点的出度信息也是一个比较重要的参数，通过它每个节点可以评估两条范围的链路状况，而单单使用梯度和链路对称信息只能评估一跳范围的链路状况，这样也可以提高路由算法的稳定性。

上面的部分介绍了路由邻居表的结构，以及如何通过路由维护包来建立和维护路由邻居表，下面介绍使用路由邻居表中的数据来建立路由的算法。路由邻居表可以提供一个节点周围的所有邻居节点的4项信息：邻居节点ID号；本地节点和邻居节点之间链路质量信息；邻居节点的梯度；邻居节点的出度，路由算法使用这4项数据计算一个节点的最佳下一跳转发节点的ID。每个节点收到邻居节点发送来的路由维护包后，首先进行路由邻居表的维护工作，维护结束以后会启动路由算法从更新后的路由邻居表中计算最佳的下一跳转发节点ID，计算过程如下：

1)、本地节点查询自己的路由邻居表中的“邻居节点的梯度”域和“地节点和邻居节点之间链路质量信息”域，将那些梯度值比自己的小，而且链路为对称的邻居节点作为潜在的下一跳节点；

2)、比较这些潜在的中继节点的节点出度(通过查找路由邻居表的“邻居节点的出度”域可以获得)，将节点出度最大的哪个节点作为最优的下一跳节点。

当然这个选择最优下一跳的算法sink节点不需要运行。当节点需要转发数据的时候，它就会选取最优的下一跳节点作为数据包的下一个目的地，并且采用单播的方式来将数据包转发给该最优下一跳节点，同时采用ACK握手信号来保证数据可靠的传输。由于最优下一跳节点的梯度都比本地节点的梯度小，数据就会从高梯度节点流向低梯度节点，最终汇聚到sink节点。这个过程基本上是一个查表和比较的过程，计算量很小，很适合无线传感器网络的特点。

由于无线信道的不稳定性、节点移动以及节点失效等原因，上面描述的路由算法建立的路由路径可能会发生中断的。如图3所示，图3为本发明提供的路由路径断裂时采取的泛洪广播中继方法的示意图。A为数据源，A根据自己的路由邻居表计算得到B为自己的最佳下一跳节点，同样B通过计算得到C为自己的最佳下一跳的节点，当数据包到达C以后，可能C计算出来自己的最佳下一跳节点是D。但是，此时由于一些原因，比如D节点缓存区已满，不能接收数据或者是由于一些障碍物的影响，造成从C到D的链路小通，那么C节点处的链路就中断了。

这种情况下，传统的方法有两种：C节点丢弃该数据或者C节点缓存该数据知道找到合适的下一条节点。前一种方法会造成较大的丢包率，后一种方法会影响网络对紧急数据的响应速度，这都不是和本发明要达到的高效、可靠和实时性的要求。

本发明中采用的是另外的一种方法。这种方法注意到当网络发生链路中断的时候，尽管通过基于路由邻居表的路由算法找不到可靠的下一条，但是并不表示该节点就和sink节点隔离了，可以让和自己同一梯度的节点或梯度比自己低但是互相之间的链路不对称的节点来转发该数据包，这样可以绕开发生链路断裂的区域。

节点采用这种转发方式的时候，采用广播方式，这种方式下不需要接收到的节点发送ACK握手信号，是一种无保证的数据转发方式。这种处理方法在可靠性和响应时间上面做了一个折中，而且由于广播采用的是一对多的方式，可靠性会有所保证。

这种在发生路由算法失效时采用的广播中继的方法是对路由算法的一个很重要的补充。收到以广播方式转发的数据的节点，首先检查自己是否符合接收该数据包的条件(要求其梯度不能大于发送该数据包的节点的梯度)，如果不符合就直接将数据包丢弃，如果符合就需要转发该数据包，在转发时节点首先根据路由邻居表来选择最优下一跳节点，如果在该点路由算法也失败了，那么该节点就会再次采用广播的方式转发该数据包。广播中继的方法是路由算法的一个很重要的辅助，是实现网络的可靠性、稳定性和实时性的一个重要的保障。

采用广播中继的一个最大的缺点就是会带来大量数据包的冗余，这在网络不稳定的时候特别严重，而且大量的冗余数据包会在网络中引起广播风暴，进一步的降低网络的性能，本发发明中采取了3种方法来消除这些不利的因素对网络的影响：

1)、使用梯度来减少转发节点的个数；

当节点采用广播的方式发送数据后，收到该数据包的节点先要检查发包节点的梯度是否不小于自己的梯度指，如果是的话，那么接收该数据包并且转发，否则丢弃该数据包。

2)、使用转发登记表避免转发同一个数据包；

每个节点将接收过的数据包记录下来，如果再次接收到同一个数据包，可以拦截掉，不转发。

3)、采用相关策略丢弃缓存的转发数据包。

由于无线通信信道的特点，每个节点在发送数据的时候，在其广播域内的节点都会收到该数据包，在mac层开辟了一个特别通道，通过该通道可以接收到周围节点发送的所有的数据包。如果有一个节点发送了一个数据包，而这个数据包和本地节点缓存队列中的某个数据包相同，那么本地节点将缓存队列中的该数据包丢弃。

通过上述这3种机制，可以很好的减少广播数据包，有效的避免广播风暴。

本发明提出的路由方法是一个混合型的路由方法，包括使用路由邻居表建立最优路径以及当发生由前者建立的路由路径发生断裂的时候采取的广播中继方法，这种混合型的路由方法可以很好应用到大规模的网络中，并且能够很好的保证可靠性和实时性，同时可以支持节点的移动。整个发明分为两个部分：

1)、基于路由邻居表建立最优路径。基于路由邻居表建立最优路径是本发明的核心，它基于局部优化的思想采用贪婪算法为每个节点选择最优的下一跳节点作为备用的数据中继节点。通过路由邻居表建立的路径可以实现数据包从源到sink的传输，同时配合使用MAC层的ACK机制，实现数据包的可靠的传输。由于节点定期的发送路由维护包，节点可以跟踪网络拓扑的改变，因此本发明提出的路由算法适用于节点低速移动的传感器网络，而且由于采用了局部优化的方法，不需要维护网络的全局拓扑，减少了大量路由的开销，降低了功耗。当节点需要发送数据的时候可以马上找到可靠的下一跳中继转发节点，无需寻找路由的阶段，提高了网络的实时响应速度。本发明提出的路由算法可以适应任何规模的网络，唯一的限制是节点的地址空间以及带宽。

2)、广播中继的辅助方法。广播中继是1)的一个辅助，当1)的方法失败以后，节点会自动地启用广播中继的方法，这样可以达到低延时，高可靠性的目的。这个辅助是必须的，是网络可靠性的一个重要的保障。

基于上述本发明的实现原理，以下结合具体的方法流程图进一步详细介绍本发明提供的这种基于路由邻居表建立无线传感器网络路由的方法。

如图4所示，图4为本发明提供的基于路由邻居表建立无线传感器网络路由的方法流程图，该方法包括以下步骤：

步骤401：节点接收到路由维护包后维护和更新自身的路由邻居表，在更新后的路由邻居表中选择梯度值比自己小且链路对称的邻居节点；

步骤402：节点比较所述选择的邻居节点的出度，将出度值最大的邻居节点作为最优的下一跳节点；

步骤403：节点建立自身与所述最优的下一跳节点之间的路由。

上述步骤401中所述节点接收到路由维护包后维护和更新自身的路由邻居表包括：节点接收到路由维护包后，检查自身路由邻居表中的邻居节点ID号域，如果发送该路由维护包的节点的ID号包含在所述邻居节点ID号域中，则更新自身路由邻居表中的本地节点和邻居节点之间链路质量信息域；否则，进行登记操作，将发送该路由维护包的节点的ID号记录在自身路由邻居表邻居节点ID号域的一个空表项中，并更新自身路由邻居表中的本地节点和邻居节点之间链路质量信息域。

上述更新自身路由邻居表中的本地节点和邻居节点之间链路质量信息域包括：节点检查路由维护包中携带的发送路由维护包的节点的路由邻居表，如果节点自身的ID号包含在所述发送路由维护包的节点的邻居表中，则该节点和发送路由维护包的节点之间的无线链路是对称的，将对应表项中的本地节点和邻居节点之间链路质量信息域标识为对称；否则，将本地节点和邻居节点之间链路质量的信息域标识为非对称。

上述节点接收到路由维护包后维护和更新自身的路由邻居表进一步包括：节点将路由维护包携带的节点梯度信息记录到邻居节点的梯度域中，并判断发送路由维护包的节点与自身是否对称，且判断自身梯度值与发送路由维护包节点梯度值的梯度差是否大于1，如果同时满足上述两个条件，则更新节点自身的梯度值，将自身的梯度值更新为发送路由维护包节点梯度值加1。

上述节点接收到路由维护包后维护和更新自身的路由邻居表进一步包括：接收到路由维护包的节点从接收的路由维护包的发送节点出度信息中获取发送节点的出度，将获取的发送节点的出度记录到路由邻居表的邻居节点出度域中。

如果节点建立的路由发生中断，则该方法在步骤403之后进一步包括：监测到链路中断的节点采用广播方式转发数据包，接收到以广播方式转发的数据包的第三节点继续转发接收到的数据包。

上述接收到以广播方式转发的数据包的第三节点继续转发接收到的数据包包括：接收到以广播方式转发的数据包的第三节点检查自身梯度值是否小于等于发送该数据包的节点的梯度值，如果是，则转发该数据包；否则，丢弃该数据包。

上述第三节点在转发该数据包时，首先根据路由邻居表来选择最优下一跳节点，如果在该点路由算法也失败了，则第三节点就会再次采用广播的方式转发该数据包。

上述采用广播的方式转发数据包进一步包括：接收到以广播方式转发的数据包的节点检查自身梯度值是否小于等于发送该数据包的节点的梯度值，如果是，则转发该数据包；否则，丢弃该数据包；和/或

节点将接收过的数据包记录下来，如果再次接收到同一个数据包，则拦截掉，不转发；和/或

节点发送一个数据包后，如果该发送的数据包与该节点缓存队列中的某个数据包相同，则该节点丢弃自身缓存队列中与所述发送数据包相同的数据包。

基于图4所述的基于路由邻居表建立无线传感器网络路由的方法流程图，以下结合具体的实施例对本发明基于路由邻居表建立无线传感器网络路由的方法进一步详细说明。

实施例

本发明提供的是一种基于路由邻居表建立无线传感器网络路由的方法，只需要将运行该协议的节点随机洒布在关心的区域，节点即可以自动运行力议，建立网络。

需要注意的是，这些洒布在一个区域内的节点的ID号不能相同，同时要保证网络的信息量不能超过节点支持的有效带宽，这可以通过限制节点数目来实现。当这些工作完成以后就可以在sink节点接收各个节点的数据了。

在本实施例中，以图2中描述的8个节点组成的网络来详细介绍网络路由方法的运行过程：

1、将所有的8个节点打开，sink节点放在指定的位置(一般是用户控制室)，其它的7个节点随机的洒布在sink周围，最终的结果如图2所示，A、B在sink的通信范围内，C在A的通信范围内，D在B的通信范围内，E在C的通信范围内，F、G在D的通信范围内。

2、这8个节点各自周期性的发送路由维护包，收到路由包的节点按照前面讲过的原理来进行路由邻居表的维护，比如sink第一次收到A的路由维护包后将A登记在自己的路由邻居表中，这之后当A收到了sink的路由维护包，链路检查判断后确认链路是对称的，那么A就将自己的梯度设为1，B也经过同样的过程将自己的梯度设为1。A第一次收到C的路由维护包以后，也将C登记到自己的路由邻居表中，这之后，当C收到A的路由包维护包以后，链路检查判断后确认链路是对称的，那么C就将自己的梯度设为2。同样的过程，最终可以建立如图2所示的网络，节点的梯度和路由邻居表也就建立起来。

3、使用路由邻居表中的信息，运行路由算法，获得最优的下一跳，数据包按照计算后的到的下一跳节点好进行转发。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。