On greedy geographic routing algorithms in sensing-covered networks

ABSTRACT

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks that provide sensing coverage over a geographic area (e.g., surveillance or object tracking systems). Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms 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 greedy geographic routing algorithms. Furthermore, we propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4:62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: F. Baccelli, K. Tchoumatchenko, and S. Zuyev. Markov paths on the poisson-delaunay graph with applications to routing in mobile networks. Advances Appl. Probability, 32:1--18, 2000.
• 3: Prosenjit Bose , Pat Morin, Online Routing in Triangulations, Proceedings of the 10th International Symposium on Algorithms and Computation, p.113-122, December 16-18, 1999
• 4: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 5: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 6: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 7: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 8: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for target detection, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570745]
• 9: Crossbow. Mica/mica2 wireless measurement system datasheet. 2003.
• 10: David P. Dobkin , Steven J. Friedman , Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs, Discrete & Computational Geometry, v.5 n.4, p.399-407, Jul. 1990 [doi>10.1007/BF02187801]
• 11: M. Duarte and Y.-H. Hu. Distance based decision fusion in a distributed wireless sensor network. In The 2nd International Workshop on Information Processing in Sensor Networks (IPSN 2003), Palo Alto, CA, April 22-23 2003.
• 12: D. Eppstein. Spanning trees and spanners. Technical Report ICS-TR-96-16, 1996.
• 13: G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI Research Report ISU/RR-87-180, Inst. for Scientific Information, Mar, 1987.
• 14: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 15: G. L. Goodman. Detection and classification for unattended ground sensors. In R. Evans, L. White, D. McMichael, and L. Sciacca, editors, Proceedings of Information Decision and Control 99, pages 419--424, Adelaide, Australia, February 1999. Institute of Electrical and Electronic Engineers, Inc.
• 16: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 17: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 18: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 19: D. Li, K. Wong, Y. H. Hu, and A. Sayeed. Detection, classification and tracking of targets in distributed sensor networks. IEEE Signal Processing Magazine, 19(2), Mar. 2002.
• 20: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 21: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of a planar spanner and routing for ad hoc wireless networks. In Proc. of IEEE INFOCOM 2002, June 2002.
• 22: M. Mauve, J. Widmer, and H. Hartenstein. A survey on position-based routing in mobile ad hoc networks. IEEE Network Magazine, 15(6):30--39, 2001.
• 23: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In INFOCOM, pages 1380--1387, 2001.
• 24: R. Ramanathan and R. Hain. Topology control of multihop wireless networks using transmit power adjustment. In INFOCOM (2), pages 404--413, 2000.
• 25: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 26: Sensoria. sgate datasheet. 2003.
• 27: SonicWall. Long range wireless card datasheet. 2003.
• 28: Ivan Stojmenovic , Xu Lin, Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1023-1032, October 2001 [doi>10.1109/71.963415]
• 29: H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.
• 30: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 31: Pramod K. Varshney, Distributed Detection and Data Fusion, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 32: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 33: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed topology control for wireless multihop ad-hoc networks. In INFOCOM, pages 1388--1397, 2001.
• 34: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958498]
• 35: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 36: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Performance, Theory

Keywords:
ad-hoc networks, coverage, geographic routing, geometric routing, sensor networks, wireless communications