Density-based anycast: a robust routing strategy for wireless ad hoc networks

ABSTRACT

Existing anycast routing protocols solely route packets to the closest group member. In this paper, we introduce density-based anycast routing, a new anycast routing paradigm particularly suitable for wireless ad hoc networks. Instead of routing packets merely on proximity information to the closest member, density-based anycast routing considers the number of available anycast group members for its routing decision. We present a unified model based on potential fields that allows for instantiation of pure proximity-based, pure density-based, as well as hybrid routing strategies. We implement anycast using this model and simulate the performance of the different approaches for mobile as well as static ad hoc networks with frequent link failures. Our results show that the best performance lies in a tradeoff between proximity and density. In this combined routing strategy, the packet delivery ratio is considerably higher and the path length remains almost as low than with traditional shortest-path anycast routing.

REFERENCES

• 1: C. Partridge , T. Mendez , W. Milliken, Host Anycasting Service, RFC Editor, 1993
• 2: T. Hardie, Distributing Authoritative Name Servers via Shared Unicast Addresses, RFC Editor, 2002
• 3: D. Kim , D. Meyer , H. Kilmer , D. Farinacci, Anycast Rendevous Point (RP) mechanism using Protocol Independent Multicast (PIM) and Multicast Source Discovery Protocol (MSDP), RFC Editor, 2003
• 4: J. Moy, "OSPF Version 2," IETF, RFC 2328, 1998.
• 5: V. Park and J. Macker, "Anycast routing for mobile services," in Conf. Information Sciences and Systems (CISS), Baltimore, MD, Mar. 1999.
• 6: G. Malkin, "RIP Version 2," IETF, RFC 2453, 1998.
• 7: V. Park and S. Corson, "Temporally-Ordered Routing Algorithm (TORA)," IETF Internet Draft, 2001.
• 8: J. Wang, Y. Zheng, and W. Jia, "An AODV-based anycast protocol in mobile ad hoc network," in IEEE Int. Symp. Personal, Indoor and Mobile Radio Communications, Beijing, China, Sep. 2003.
• 9: C. Intanagonwiwat and D. D. Lucia, "The sink-based anycast routing protocol for ad hoc wireless sensor networks," Computer Sci. Dept., Univ. Southern California (USC), Los Angeles, CA, 99-698, 1999.
• 10: J. Wang, Y. Zheng, and W. Jia, "A-DSR: A DSR-based anycast protocol for IPv6 flow in mobile ad hoc networks," in IEEE Veh. Technol. Conf., Orlando, FL, Oct. 2003.
• 11: U. C. Kozat and L. Tassiulas, "Network layer support for service discovery in mobile ad hoc networks," in IEEE INFOCOM, San Francisco, CA, Apr. 2003.
• 12: E. W. Dijkstra, "A note on two problems in connexion with graphs," Num. Math., vol. 1, pp. 269-271, 1959.
• 13: V. Lenders, M. May, and B. Plattner, "Density-based vs. proximity-based anycast routing for mobile networks," in IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 14: D. Johnson and D. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, T. Imelinsky and H. Korth, Eds. Norwell, MA: Kluwer Academic, 1996, vol. 353, pp. 153-181.
• 15: Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, July-September 2003 [doi>10.1109/TMC.2003.1233531]
• 16: W. Navid and T. Camp, "Stationary distributions for the random waypoint model," IEEE Trans. Mobile Comput., vol. 3, no. 1, pp. 99-108, Jan. 2004.
• 17: T. Camp, J. Boleng, and V. Davies, "A survey of mobility models for ad hoc network research," Wireless Commun. Mobile Computing (WCMC), vol. 2, pp. 483-502, 2002.
• 18: T. Lin, S. F. Midkiff, and J. S. Park, "Mobility versus link stability in simulation of mobile ad hoc networks," in Commun. Networks and Distrib. Syst. Modeling and Simulation Conf. Proc., 2003, pp. 3-8.
• 19: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 20: IETF, S. Deering and R. Hinden, "IP Version 6 addressing architecture," RFC 2373, 1998.
• 21: Dina Katabi , John Wroclawski, A framework for scalable global IP-anycast (GIA), Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.3-15, August 28-September 01, 2000, Stockholm, Sweden
• 22: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: Hitesh Ballani , Paul Francis, Towards a global IP anycast service, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 24: V. D. Park and J. P. Macker, "Anycast routing for mobile networking," in Proc. MILCOM, Atlantic City, NJ, Nov. 1999.
• 25: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 26: Anindya Basu , Alvin Lin , Sharad Ramanathan, Routing using potentials: a dynamic traffic-aware routing algorithm, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863962]
• 27: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 28: Jabed Faruque , Ahmed Helmy, RUGGED: RoUting on finGerprint Gradients in sEnsor Networks, Proceedings of the The IEEE/ACS International Conference on Pervasive Services, p.179-188, July 19-23, 2004 [doi>10.1109/ICPS.2004.27]
• 29: S. Toumpis and L. Tassiulas, "Packetostatics: Deployement of massively dense sensor networks as an electrostatic problem," in IEEE INFOCOM , Miami, FL, Mar. 2005.
• 30: Qun Li , Michael De Rosa , Daniela Rus, Distributed algorithms for guiding navigation across a sensor network, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939017]
• 31: V. Lenders, M. May, and B. Plattner, "Service discovery in mobile ad hoc networks: A field theoretic approach," J. Pervasive and Mobile Comput., vol. 1, no. 3, Sep. 2005.

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: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Performance

Keywords:
anycast, mobile communication, protocols, routing, wireless communication