Message ferry route design for sparse ad hoc networks with mobile nodes

ABSTRACT

Message ferrying is a networking paradigm where a special node, called a message ferry, facilitates the connectivity in a mobile ad hoc network where the nodes are sparsely deployed. One of the key challenges under this paradigm is the design of ferry routes to achieve certain properties of end-to-end connectivity, such as, delay and message loss among the nodes in the ad hoc network. This is a difficult problem when the nodes in the network move arbitrarily. As we cannot be certain of the location of the nodes, we cannot design a route where the ferry can contact the nodes with certainty. Due to this difficulty, prior work has either considered ferry route design for ad hoc networks where the nodes are stationary, or where the nodes and the ferry move pro-actively in order to meet at certain locations. Such systems either require long-range radio or disrupt nodes' mobility patterns which can be dictated by non-communication tasks. We present a message ferry route design algorithm that we call the Optimized Way-points, or OPWP, that generates a ferry route which assures good performance without requiring any online collaboration between the nodes and the ferry. The OPWP ferry route comprises a set of way-points and waiting times at these way-points, that are chosen carefully based on the node mobility model. Each time that the ferry traverses this route, it contacts each mobile node with a certain minimum probability. The node-ferry contact probability in turn determines the frequency of node-ferry contacts and the properties of end-to-end delay. We show that OPWP consistently outperforms other naive ferry routing approaches.

REFERENCES

• 1: Allan Beaufour , Martin Leopold , Philippe Bonnet, Smart-tag based data dissemination, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570749]
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Zong Da Chen , H.T. Kung , Dario Vlah, Ad hoc relay wireless networks over moving vehicles on highways, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501451]
• 4: W. Cook, D. Applegate, R. Bixby, and V. Chvatal. Concorde: A code for solution of Travelling Salesman Problem. http://www.tsp.gatech.edu/
• 5: James A. Davis , Andrew H. Fagg , Brian N. Levine, Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks, Proceedings of the 5th IEEE International Symposium on Wearable Computers, p.141, October 08-09, 2001
• 6: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 7: Y. Gu, D. Bozdag, E. Ekici, F. Ozguner, and C. Lee. Partitioning Based Mobile Element Scheduling in Wireless Sensor Networks. In. proc. Second Annual IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON) 2005.
• 8: R. Jain, A. Durresi, G. Babic. Throughput Fairness Index: An Explanation. ATM Forum/99-0045, Feb. 1999. http://www.cse.wustl.edu/ jain/atmf/a99-0045.htm
• 9: Ravi Jain , Dan Lelescu , Mahadevan Balakrishnan, Model T: an empirical model for user registration patterns in a campus wireless LAN, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080848]
• 10: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 11: Sushant Jain , Michael Demmer , Rabin Patra , Kevin Fall, Using redundancy to cope with failures in a delay tolerant network, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 12: D. Johnson and D. Maltz. Dynamic Source Routing in Ad hoc Wireless Networks. In proc. ACM SIGCOMM. 1996.
• 13: Aman Kansal , Arun A. Somasundara , David D. Jea , Mani B. Srivastava , Deborah Estrin, Intelligent fluid infrastructure for embedded networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990080]
• 14: Jérémie Leguay , Timur Friedman , Vania Conan, DTN routing in a mobility pattern space, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.276-283, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080146]
• 15: K. K. Leung. and M. Eisenberg. A Single-Server Queue with Vacations and Gated Time-Limited Service. IEEE Transactions on Communication. Vol. 38. No. 9. Sept. 1990.
• 16: Q. Li, and D. Rus. Sending Messages to Mobile Users in Disconnected Ad hoc Wireless Networks. In. proc. 4th ACM/IEEE Internation Conference on Mobile Computing and Networking (Mobicom'98). Nov. 1998.
• 17: J. Luo, and J. Hubaux. Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks. In. proc. IEEE Infocom, 2005.
• 18: S. Merugu, M. Ammar and E. Zegura. Routing in Space and Time in Networks with Predictable Mobility, Technical report: GIT-CC-04-07. College of Computing, Georgia Institute of Technology. 2004.
• 19: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 20: 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
• 21: R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks. Elsevier Ad Hoc Networks Journal, vol. 1, issues 2-3, Sept. 2003, pp. 215-233.
• 22: Arun A. Somasundara , Aditya Ramamoorthy , Mani B. Srivastava, Mobile Element Scheduling for Efficient Data Collection in Wireless Sensor Networks with Dynamic Deadlines, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.296-305, December 05-08, 2004 [doi>10.1109/REAL.2004.31]
• 23: Tara Small , Zygmunt J. Haas, The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way), Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778443]
• 24: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 25: M. Tariq. Interarrival Times for the Random Waypoint Model are Exponentially Distributed. http://www.cc.gatech.edu/ mtariq/pub/notes/rwp-interarrivals.pdf
• 26: A. Vahdat and D. Becker. Epidemic Routing for Partically-Connected Ad hoc Networks. Technical Report. Duke University. 2000.
• 27: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 28: J. Yoon, M. Liu, B. Noble. Random Waypoint Considered Harmful. In. proc. IEEE Infocom 2003, San Franciso, CA.
• 29: Wenrui Zhao , Mostafa H. Ammar, Message Ferrying: Proactive Routing in Highly-Partitioned Wireless Ad Hoc Networks, Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03), p.308, May 28-30, 2003
• 30: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 31: W. Zhao, M. Ammar, and E. Zegura, Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network. In proc. IEEE Infocom 2005. Mar, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
delay & disruption tolerant networks, mobile ad hoc networks, mobility models, sparse networks