A message ferrying approach for data delivery in sparse mobile ad hoc networks

ABSTRACT

Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	DakNet project. http://web.media.mit.edu/char126 amir/daknet/.
	2	Mohiuddin Ahmed , Srikanth Krishnamurthy , Randy Katz , Son Dao, Trajectory control of mobile gateways for range extension in ad hoc networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.39 n.6, p.809-825, 21 August 2002 [doi>10.1016/S1389-1286(02)00249-9 ]
	3	N. Bansal and Z. Liu. Capacity, delay and mobility in wireless ad-hoc networks. In IEEE INFOCOM'2003, April 2003.
	4	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]
	5	J. Bentley. Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing, 4:387--411, 1992.
	6	Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
	7	Srdjan Capkun , Jean-Pierre Hubaux , Levente Buttyán, Mobility helps security in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778422]
	8	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]
	9	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
	10	Henri Dubois-Ferriere , Matthias Grossglauser , Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778446]
	11	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]
	12	D. Goodman, J. Borras, N. Mandayam, and R. Yates. INFOSTATIONS: A new system model for data and messaging services. In IEEE VTC'97, volume 2, pages 969--973, May 1997.
	13	M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In IEEE INFOCOM 2001, April 2001.
	14	M. Grossglauser and M. Vetterli. Locating nodes with EASE: Mobility diffusion of last encounters in ad hoc networks. In IEEE INFOCOM'2003, April 2003.
	15	P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46:388--404, March 2000.
	16	Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
	17	D. Johnson and D. Maltz. Dynamic source routing in ad-hoc wireless networks. In ACM SIGCOMM, August 1996.
	18	Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
	19	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]
	20	Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
	21	Qun Li , Daniela Rus, Sending messages to mobile users in disconnected ad-hoc wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.44-55, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345918]
	22	Robert Morris , John Jannotti , Frans Kaashoek , Jinyang Li , Douglas Decouto, CarNet: a scalable ad hoc wireless network system, Proceedings of the 9th workshop on ACM SIGOPS European workshop: beyond the PC: new challenges for the operating system, September 17-20, 2000, Kolding, Denmark [doi>10.1145/566726.566741]
	23	D. Nain, N. Petigara, and H. Balakrishnan. Integrated routing and storage for messaging applications in mobile ad hoc networks. In WiOpt 2003, March 2003.
	24	E. Perevalov and R. Blum. Delay limited capacity of ad hoc networks: Asymptotically optimal transmission and relaying strategy. In IEEE INFOCOM'2003, April 2003.
	25	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
	26	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
	27	R. Ramanathan and R. Hain. Topology control of multihop wireless networks using transmit power adjustment. In IEEE INFOCOM, 2000.
	28	Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
	29	R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In IEEE SNPA Workshop, 2003.
	30	R. Sivakumar, P. Sinha, and V. Bharghavan. CEDAR: a core-extraction distributed ad hoc routing algorithm. IEEE Journal on Selected Areas in Communications, 17:1454--1465, August 1999.
	31	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]
	32	William Su , Sung-Ju Lee , Mario Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management, v.11 n.1, p.3-30, January–February 2001 [doi>10.1002/nem.386 ]
	33	A. Vahdat and D. Becker. Epidemic routing for partially-connected ad hoc networks. Technical report, Duke University, 2000.
	34	R. Wattenhofer, L. Li, P. Bahl, and Y. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In IEEE INFOCOM 2001, April 2001.
	35	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