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

摘要：空洞问题一直是无线传感器网络中基于地理信息位置路由协议研究的一个热点。文章对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)