DocumentCode :
856209
Title :
Impact of sensing coverage on greedy geographic routing algorithms
Author :
Xing, Guoliang ; Lu, Chenyang ; Pless, Robert ; Huang, Qingfeng
Author_Institution :
Dept. of Comput. Sci. & Eng., Washington Univ., St. Louis, MO, USA
Volume :
17
Issue :
4
fYear :
2006
fDate :
4/1/2006 12:00:00 AM
Firstpage :
348
Lastpage :
360
Abstract :
Greedy geographic routing is an attractive localized routing scheme for wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our analysis and simulation results demonstrate that an existing geographic routing algorithm, greedy forwarding (GF), can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under GF. We also propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that achieves path dilation lower than 4.62 in sensing-covered networks as long as the communication range is at least twice the sensing range. Furthermore, we extend GF and BVGF to achieve provable performance bounds in terms of total number of transmissions and reliability in lossy networks.
Keywords :
greedy algorithms; telecommunication network routing; wireless sensor networks; Bounded Voronoi Greedy Forwarding; greedy geographic routing algorithms; localized routing scheme; network dilation; sensing-covered networks; wireless sensor networks; Algorithm design and analysis; Analytical models; Network topology; Performance loss; Routing; Scalability; Surveillance; Telecommunication network reliability; Upper bound; Wireless sensor networks; Sensor networks; coverage; geographic routing; greedy routing; wireless communication.;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2006.48
Filename :
1603518
Link To Document :
بازگشت