A distributed algorithm for the dead end problem of location based routing in sensor networks

作     者：Zou, L Lu, M Xiong, ZX 

作者机构：Texas A&M Univ Dept Elect Engn College Stn TX 77843 USA 

出 版 物：《IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY》 (IEEE Trans. Veh. Technol.)

年 卷 期：2005年第54卷第4期

页      面：1509-1522页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0823[工学-交通运输工程] 

主　　题：distributed algorithm graph theory protocols routing sensor networks shortest path topology 

摘      要：The dead end problem in greedy forwarding is an important issue of location based routing in sensor networks. It occurs when a message falls into a local minimum using greedy forwarding. Current solutions to this problem are insufficient in either eliminating traffic/path memorization or finding satisfactory short paths. In this paper, we propose a novel algorithm, called partial-partition avoiding geographic routing (PAGER), to solve the problem. The basic idea of PAGER is to divide a sensor network graph into functional subgraphs and provide each sensor node with message forwarding directions based on these subgraphs. PAGER results in loop free short paths without memorization of traffics/paths in sensor nodes. It does not require planarization of the underlying network graph. Further, the mobility adaptability of PAGER makes it suitable for use in mobile sensor networks with frequent topology changes. We implement the PAGER algorithm in two protocols and evaluate them in sensor networks with different parameters. Experimental results show the advantage of PAGER in the context of sensor networks.