On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks

ABSTRACT

It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variants which simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedyface routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.

REFERENCES

• 1: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 3: Susanta Datta , Ivan Stojmenovic , Jie Wu, Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Cluster Computing, v.5 n.2, p.169-178, April 2002 [doi>10.1023/A:1013985610753]
• 4: Gregory G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, Information Sciences Institute (ISI), 1987.
• 5: Hannes Frey and Ivan Stojmenovic. Geographic and energy aware routing in sensor networks. In Ivan Stojmenovic, editor, Handobook on Sensor Networks Wiley, 2005.
• 6: K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology 18:259--278, 1969.
• 7: 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]
• 8: Silvia Giordano and Ivan Stojmenovic. Position based routing algorithms for ad hoc networks: A taxonomy. In Xiuzhen Cheng, Xiao Huang, and Ding-Zhu Du, editors, Ad Hoc Wireless Networking pages 103--136. Kluwer, 2004.
• 9: THE CMU MONARCH GROUP. Wireless and mobility extensions to ns-2. http://www.monarch.cs.rice.edu.
• 10: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 11: 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]
• 12: Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker. Geographic routing made practical. In Proceedings of USENIX Symposium on Network Systems Design and Implementation Boston, Massachusetts, USA, May 2005.
• 13: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, On the pitfalls of geographic face routing, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080818]
• 14: Evangelos Kranakis, Harvinder Singh, and Jorge Urrutia. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99) pages 51--54, Vancouver, August 1999.
• 15: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 16: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 17: 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]
• 18: Ben Leong , Sayan Mitra , Barbara Liskov, Path Vector Face Routing: Geographic Routing with Local Face Information, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.147-158, November 06-09, 2005 [doi>10.1109/ICNP.2005.32]
• 19: Xiang-Yang Li, Gruia Calinescu, and Peng-Jun Wan. Distributed construction of a planar spanner and routing for ad hoc wireless networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM '02) volume 3, pages 1268--1277. IEEE Computer Society, June 23--27 2002.
• 20: Xiang-Yang Li , Ivan Stojmenovic , Yu Wang, Partial Delaunay Triangulation and Degree Limited Localized Bluetooth Scatternet Formation, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.350-361, April 2004 [doi>10.1109/TPDS.2004.1271184]
• 21: Ivan Stojmenović, Location updates for efficient routing in ad hoc networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 22: 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]
• 23: Ivan Stojmenovic , Xu Lin, Power-Aware Localized Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1122-1133, November 2001 [doi>10.1109/71.969123]
• 24: Hideaki Takagi and Leonard Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications 32(3):246--257, March 1984.
• 25: G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition 12(4):261--268, 1980.

INDEX TERMS

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

General Terms:
Algorithms, Reliability, Theory

Keywords:
ad hoc network, face routing, guaranteed delivery