一种基于两跳邻居信息的贪婪地理路由算法  

A Greedy Geographic Routing Algorithm Based on 2-Hop Neighbors

作　　者：王建新[1] 赵湘宁[1] 刘辉宇[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《电子学报》2008年第10期1903-1909,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60673164);湖南省杰出青年基金(No.06JJ10009);高等学校博士学科点专项科研基金(No.20060533057);973前期研究专项(No.2008CB317107);新世纪优秀人才支持计划(No.NECT-05-0683)

摘　　要：基于地理信息的路由算法由于其高效、低路由开销和良好的可扩展性等特点,在无线传感器网络中得到比较广泛的应用.许多采用贪婪策略作为其基本数据转发机制的地理路由算法都不可避免会遇到路由空洞现象.针对这个问题,本文提出了一种基于掌握两跳邻居节点位置信息的贪婪地理路由算法——Greedy-2算法.该算法能够使节点提前意识到路由空洞的存在,从而尽可能使数据包及时绕开空洞边界节点,减少路由空洞发生的概率,提高分组到达率.对于Greedy-2算法仍然遭遇路由空洞现象的情况,文章提出了一种基于两跳邻居信息的平面化算法PATN,该算法不需要增加额外的平面化开销,即可将网络平面化以采取边缘恢复机制,在UDG网络中保证数据可靠传输.仿真结果表明,与基于一跳邻居节点位置信息的贪婪算法相比,Greedy-2算法可以明显减少路由空洞现象发生的次数,在分组到达率和数据传送的路由跳数方面都有着更好的性能.Greedy-2算法与PATN规则结合后的GPSR-2算法也比GP-SR算法有着更优化的路由跳数.Geographic muting is widely used in wireless sensor networks due to its great efficiency, low muting overhead and good scalability. However, the problem that most of the geographic muting algorithms which adopt greedy algorithm as their basic routing strategies have to face is the ＇muting void phenomena＇. Aiming at this problem, this paper presents a new geographic routing algorithm, Greedy algorithm based on the geographic information of 2-hop neighbors （Greedy-2）. Greedy-2 algorithm makes nodes be aware of the existence of voids before the packet reaches a region where the Greedy forwarding fails, so that the packet can bypass the dead-end node ahead of time to reduce the probability of encountering the routing voids. PATN, a Planarization Algorithrn based on Two-hop Neighbors, is also introduced. PATN ensures the success of perimeter muting through the planarization without extra overhead, and guarantees delivery in UDG networks when Greedy-2 algorithm fails. Extensive simulation further shows that Greedy-2 algorithm can significantly decrease the muting void phenomena. It obtains better performance than Greedy algorithm based on 1-hop neighbors in aspects of the packet delivery rate and the length of routing path. GPSR-2, which combines Greedy-2 and PATN algorithms,has less average length of routing path than GPSR.

关 键 词：无线传感器网络 地理路由 贪婪算法 两跳邻居信息 路由空洞 平面化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]