一种基于信标的地理信息位置路由协议的改进

摘要：空洞问题一直是无线传感器网络中基于地理信息位置路由协议研究的一个热点。文章对ITGR算法提出了改进措施，通过逆路由路径方向寻找新的信标节点更新ITGR算法中的信标节点，从而扩大ITGR算法的目标阴影区域范围，减少算法绕空洞时迂回路径的长度。OMNeT++4．0仿真表明，改进算法可以降低ITGR算法绕空洞的路由路径的平均跳数和长度。
关键词：无线传感网络；路由协议；地理信息位置路由；信标

0 引言
    近年来，随着低功耗、微型化GPS的发展，以及三边测量等定位技术的日趋成熟，使得基于地理信息位置的路由算法日益成为研究的热点。而且在无线传感网络中，很多应用都与节点的位置信息有关，甚至某些应用必须知道节点的位置信息后，传感器节点采集的信息才有真正的价值和意义。例如，在环境监测中，需要知道被监测点的位置信息；在森林火灾监测和煤矿安全事故监测中，需要知道发生险情的位置信息；在跨海大桥桥梁安全监测中，桥梁摆动的幅度需要精确知道其位置偏移信息。以地理信息位置为导向的路由同时具有很强的路由导向性。以往传统的路由需要存储大量的路由表或者在整个网络内泛洪路由请求数据包来寻找数据包发送的路径，而基于地理信息的位置路由，可以缩减路由请求的泛洪区域，甚至取消泛洪，大大降低整个网络的能耗、拥塞，使得网络的生存时间得以提高、网络的规模得以提升。

1 相关算法研究
    在基于地理信息位置路由算法依靠单跳邻居节点和目标节点的位置信息来确定路由，路由选择比本节点更接近于目标节点的邻居节点作为下一跳节点。但当网络中存在空洞的时候，该种贪婪算法有可能失效。对此，很多文章提出绕过空洞的解决方法，这些算法大体可以分为三类：局部泛洪机制、消息回退机制和面路由机制。其中以GPSR算法应用最为基础和广泛。
    GPSR算法结合了贪婪转发路由和周边路由，源节点先用贪婪转发策略发送数据包，当数据包到达局部最小节点时，算法进入周边模式，即节点采用右手法则选择下一跳节点。在周边模式中如果一个节点到目标节点的距离小于局部最小节点到目标节点的距离，则在此算法由周边模式恢复到贪婪算法模式中，依次重复直到到达目标节点。
    虽然当源节点和目标节点存在连接的时候，GPSR算法总能保证数据包的发送，但GPSR算法存在三角路由问题和盲目路由问题。对此GLR算法将算法由周边模式恢复到贪婪转发模式的节点称为信标节点(landmark)，源节点在知道到达目标节点的信标节点位置信息后，可以直接将数据发送到目标节点而不经过局部最小节点，从而优化三角路由问题。同时信标节点的发现过程采用前向发现与后向发现相结合的方式，避免盲目路由问题时数据包绕整个网络转发的情况。
    相对于GLR一个目标节点对应一个信标缓存的情况，ITGR算法提出目标阴影区域的概念。通过一次信标发现过程，发现到目标节点路径上的信标节点和局部最小节点后；通过源节点、局部最小节点、信标节点的平面直线方程不等式组划定目标节点阴影区域的范围，一个信标节点对应目标阴影区域范围内的所有节点。ITGR算法大大降低信标缓存的大小，并且减少信标发现过程，降低了控制开销。

2 基于信标的地理信息位置路由协议的改进
    本文在ITGR算法基础上提出信标后退算法，试图扩大目标节点的阴影区域，让一次信标发现过程发现更大的目标节点阴影区域，让更多的节点使用信标节点作为间接目标节点转发数据，并减少算法进入周边模式的次数，缩短路由路径。

    下面我们通过举例来说明如何扩大目标节点阴影区域范围。在图1中，S为源节点，D为目标节点，阴影区域为VOID区域(由于阴影区域中存在障碍物等原因，网络无法通过此区域通信)，P为局部最小节点，B1为ITGR算法的信标节点，实线为源节点S按照ITGR算法发送数据包到目标节点D的路径，虚线为更新信标节点后的路径。
    ITGR和GLR算法中定义信标节点为路由算法由周边模式恢复到贪婪转发模式的节点。假设用DISTANCE(X，Y)来代表X与Y点之间的距离，B代表信标节点，则信标节点B满足公式(1)。由图1可以发现，不仅仅在信标节点B满足公式(1)，按照数据包所走的路径往后推，E、C、N、B2点都满足公式(1)，直到到达M点，M点并不满足公式(1)。所以在B2同时满足公式(2)与公式(3)
    DISTANCE(B，D)<DISTANCE(P，D)……(1)
    DISTANCE(N，D)<DISTANCE(B，D)……(2)
    DISTANCE(B，D)<DISTANCE(M，D)……(3)
    因此我们可以在ITGR发现信标节点的路径上逆向寻找第一个DISTANCE(X，Y)的峰值，并将其称为新信标节点。当知道更新过信标节点后，下次S点再发送数据包到D时，直接将数据包发送给B2，然后由B2转发给D点。从图1中可见，未更新信标节点前，数据包发送路径为实线代表的路径，共16跳；更新过信标节点后，数据包发送的路径为虚线所代表的路径，共12跳。可见更新过信标节点后，可以节省路由跳数。采用ITGR算法，S点第二次向D点发送数据时，先将数据发送给间接目标节点B1点，但在使用贪婪算法向B1点发送数据的时候，到达Z点遇到空洞问题，此时Z点使用周边模式向B1转发数据包。而如果采用了更新信标算法，S点第二次向D点发送数据的时候直接将数据包发送给B2，此时，路由路径不需要进入周边算法模式，从S到B2和B2到D点都可以直接使用贪婪算法转发。

    假设X为射线SB2上的一点，Y为射线SB1上的一点，Z为射线SP上的一点。则ITGR算法中目标节点阴影区域为YB2PZ，如图2中的斜线区域；更新信标节点后，目标节点阴影区域为XB2PZ，如图中的网状区域。由图2可见区域XB2PZ比区域YB2PZ更大，说明采用新信标节点可以扩大目标节点阴影区域范围。

    改进后的路由算法描述如下：源节点向目标节点发送数据时，按照ITGR算法将数据包转发到B1点，在B1点按照ITGR算法数据发送模式由周边算法模式恢复到贪婪算法模式中。我们在此加入LBD(landmark backward discovery)算法，即信标节点后向推移算法。根据ITGR算法，路由模式mode在B1点将变为GREEDY，此时节点将采用LBD算法转发数据，算法伪代码如表1所示。LBD首先判断信标节点的上一跳节点是否比信标节点到目标节点的距离更远。如果不是，则直接继续按ITGR原来算法运行；如果是，则更改数据包模式并将数据包发送给上一跳节点，然后按照左手法则依次向回查找距离目标节点，直到查找到新的信标节点或者回传数据包到局部最小节点。

3 仿真结果
    本文使用离散仿真器OMNeT++4．0对ITGR算法和更新信标后的ITGR+LBD算法进行仿真对比。整个实验网络为1500m×2000m，网络内随机分布200到400个节点，每次仿真增加50个节点，节点保持静止状态，网络中间存在一个900m×200m的空洞，空洞上方的一个源节点向空洞下方的10个目标节点各发送10次数据。

    仿真主要测量平均路由跳数和路由路径平均长度，仿真结果如图3和图4所示。由图3可见更新信标节点后，平均路由跳数最少减少9.4 6％，最多减少21．92％，平均减少15．18％。由图4可见，更新信标节点后，路由路径平均长度最少减少6．46％，路由路径平均长度最多减少15．72％，平均减少11．03％。采用ITGR算法第二次向目标节点发送数据的时候首先使用贪婪算法转发到信标节点。但当网络中存在窄带型空洞的时候，使用贪婪算法向信标节点转发数据有可能重新遇见空洞，造成迂回路径。而采用新的信标节点后，由于新的信标节点一般位于窄带型空洞的两端，所以有效地减少了向信标节点发送数据的时候重新遇见空洞的问题，缩短了路由路径长度。另外当后移了信标节点后扩大了目标节点阴影区域，使得更多的目标节点可以使用已发现的信标节点，避免了二次重复信标发现。仿真实验结果证明了采用新的信标节点后，可以降低路由路径的平均跳数和路由路径的长度。

4 结论
    本文提出一种ITGR的改进算法，通过逆着到目标节点的路由路径方向选择新的中信标节点，可以扩大ITGR算法中目标节点阴影区域范围，减少算法进入周边模式的次数，改进的算法既能有效地绕过空洞，又能有效地缩短绕空洞时路由路径的迂回长度。仿真实验表明，当网络中存在窄带型空洞时，更新信标节点可以有效降低ITGR算法的路由跳数并缩短路由路径的长度。