Binary waypoint geographical routing in wireless mesh networks

ABSTRACT

We propose Binary Waypoint Routing, a novel geographical routing protocol for wireless mesh networks. Its idea is to learn and maintain source routes to a small number of nodes called binary waypoints that are placed in subspaces constructed as a result of binary space partitioning. A source node sends a packet to a waypoint for a given destination and intermediate nodes try to adapt the packet route by aiming at waypoints that are closer to the destination. Our simulation results show that the proposed scheme achieves high packet delivery rate with a traffic pattern similar to the Optimal Shortest Path Routing.

REFERENCES

• 1: 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]
• 2: Srdjan Čapkun , Maher Hamdi , Jean-Pierre Hubaux, GPS-free Positioning in Mobile Ad Hoc Networks, Cluster Computing, v.5 n.2, p.157-167, April 2002 [doi>10.1023/A:1013933626682]
• 3: Niklas Carlsson , Derek L. Eager, Non-Euclidian geographic routing in wireless networks, Ad Hoc Networks, v.5 n.7, p.1173-1193, September, 2007 [doi>10.1016/j.adhoc.2006.07.001]
• 4: P. Casari, M. Nati, C. Petrioli, and M. Zorzi. Efficient Non Planar Routing Around Dead-Ends in Sparse Topologies Using Random Forwarding. In Proc. of ICC, Glasgow, UK, June 2007.
• 5: Swades De , Antonio Caruso , Tamalika Chaira , Stefano Chessa, Bounds on hop distance in greedy routing approach in wireless ad hoc networks, International Journal of Wireless and Mobile Computing, v.1 n.2, p.131-140, February 2006 [doi>10.1504/IJWMC.2006.012472]
• 6: H. Frey. Scalable Geographic Routing Algorithms for Wireless Ad-Hoc Networks. IEEE Network, July/August 2004.
• 7: K. Gabriel and R. Sokal. A New Statistical Approach to Geographic Variation Analysis. Systematic Zoology, 18:259--278, 1969.
• 8: Peng He , Jiandong Li , Lei Zhou, A Novel Geographic Routing Algorithm for Ad Hoc Networks Based on Localized Delaunay Triangulation, Proceedings of the 20th International Conference on Advanced Information Networking and Applications - Volume 1 (AINA'06), p.49-54, April 18-20, 2006 [doi>10.1109/AINA.2006.45]
• 9: 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]
• 10: Young-Jin Kim Ramesh Govindan , Brad Karp , Scott Shenker, Lazy cross-link removal for geographic routing, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182819]
• 11: 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]
• 12: E. Schiller, P. Starzetz, F. Theoleyre, and A. Duda. Properties of Greedy Geographical Routing in Spontaneous Wireless Mesh Networks. In Proc. IEEE GLOBECOM, 2007.
• 13: 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:
Performance

Keywords:
geographical routing, wireless mesh networks