Orthogonal rendezvous routing protocol for wireless mesh networks

ABSTRACT

Routing in multi-hop wireless networks involves the indirection from a persistent name (or ID) to a locator. Concepts such as coordinate space embedding help reduce the number and dynamism complexity of bindings and state needed for this indirection. Routing protocols which do not use such concepts often tend to flood packets during route discovery or dissemination, and hence have limited scalability. In this paper, we introduce Orthogonal Rendezvous Routing Protocol (ORRP) for meshed wireless networks. ORRP is a lightweight-but-scalable routing protocol utilizing directional communications (such as directional antennas or free-space-optical transceivers) to relax information requirements such as coordinate space embedding and node localization. The ORRP source and ORRP destination send route discovery and route dissemination packets respectively in locally-chosen orthogonal directions. Connectivity happens when these paths intersect (i.e., rendezvous). We show that ORRP achieves connectivity with high probability even in sparse networks with voids. ORRP scales well without imposing DHT-like graph structures (eg: trees, rings, torus etc). The total state information required is O(N^3/2 for N-node networks, and the state is uniformly distributed. ORRP does not resort to flooding either in route discovery or dissemination. The price paid by ORRP is suboptimality in terms of path stretch compared to the shortest path; however we characterize the average penalty and find that it is not severe.

REFERENCES

• 1: Bow-nan Cheng , Murat Yuksel , Shivkumar Kalyanaraman, Orthogonal Rendezvous Routing Protocol for Wireless Mesh Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.106-115, November 12-15, 2006 [doi>10.1109/ICNP.2006.320204]
• 2: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 3: 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]
• 4: 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]
• 5: Dragos Niculescu , Badri Nath, Trajectory based forwarding and its applications, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939012]
• 6: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 7: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 8: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 9: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 10: W. T. Tsai , C. V. Ramamoorthy , W. K. Tsai , O. Nishiguchi, An Adaptive Hierarchical Routing Protocol, IEEE Transactions on Computers, v.38 n.8, p.1059-1075, August 1989 [doi>10.1109/12.30862]
• 11: R. R. Choudhury and N. Vaidya, "Impact of directional antennas on ad hoc routing," presented at the 8th Int. Conf. Personal Wireless Communication (PWC), Venice, Italy, Sep. 2003.
• 12: Ram Ramanathan, On the performance of ad hoc networks with beamforming antennas, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501430]
• 13: Su Yi , Yong Pei , Shivkumar Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778429]
• 14: M. Yuksel, J. Akella, S. Kalyanaraman, and P. Dutta, "Free-space-optical mobile ad hoc networks: auto-configurable building blocks," ACM/Springer Wireless Networks, 2008, to be published.
• 15: David Braginsky , Deborah Estrin, Rumor routing algorthim for 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.570742]
• 16: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 17: D. Niculescu and B. Nath, "Ad hoc positioning system (APS) using AoA," presented at the IEEE INFOCOM, San Francisco, CA, 2003.
• 18: M. Gerla, X. Hong, and G. Pei, "Landmark routing for large ad hoc wireless networks," in Proc. IEEE GLOBECOM, Nov. 2000, pp. 1702-1706.
• 19: ns-2--The Network Simulator. [Online]. Available: http://www.isi. edu/nsnam/ns
• 20: MuniWireless. [Online]. Available: http://www.muniwireless.com/
• 21: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 22: S. M. Das, H. Pucha, and Y. C. Hu, "Performance comparison of scalable location services for geographic ad hoc routing," presented at the IEEE INFOCOM, Miami, FL, 2005.
• 23: T. Clausen and P. Jacquet, "OLSR," RFC 3626, Oct. 2003 [Online]. Available: http://ietf.org/rfc/rfc3626.txt
• 24: B. Chen and R. Morris, "L+: scalable landmark routing and address lookup for multi-hop wireless networks," MIT LCS, Cambridge, MA, Tech. Rep. 837, Mar. 2002.
• 25: Menghow Lim , Julian Chesterfield , Jon Crowcroft, Landmark Guided Forwarding, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.169-178, November 06-09, 2005 [doi>10.1109/ICNP.2005.21]
• 26: Z. Haas, J. Pearlman, and P. Samar, "The zone routing protocol (ZRP) for ad hoc networks," IETF Internet Draft, Jul. 2002.
• 27: Matthew Caesar , Miguel Castro , Edmund B. Nightingale , Greg O'Shea , Antony Rowstron, Virtual ring routing: network routing inspired by DHTs, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 28: Himabindu Pucha , Saumitra M. Das , Y. Charlie Hu, Imposed Route Reuse in Ad Hoc Network Routing Protocols Using Structured Peer-to-Peer Overlay Routing, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1452-1467, December 2006 [doi>10.1109/TPDS.2006.174]
• 29: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 30: R. R. Choudhury and N. Vaidya, "Performance of ad hoc routing using directional antennas," Ad Hoc Networks, vol. 3, no. 2, pp. 157-173, Mar. 2005.
• 31: 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, p.147-158, November 06-09, 2005 [doi>10.1109/ICNP.2005.32]
• 32: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 33: Romit Roy Choudhury , Xue Yang , Ram Ramanathan , Nitin H. Vaidya, Using directional antennas for medium access control in ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570653]
• 34: Masanori Sekido , Masanori Takata , Masaki Bandai , Takashi Watanabe, Directional NAV Indicators and Orthogonal Routing for Smart Antenna Based Ad Hoc Networks, Proceedings of the Second International Workshop on Wireless Ad Hoc Networking, p.871-877, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.59]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Performance

Keywords:
directional antennas, free-space-optics, wireless mesh, wireless routing protocol