Abstract
Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one an- other without any pre-existing network infrastructure. Existing ad hoc routing protocols, while robust to rapidly changing network topology, assume the presence of a connected path from source to destination. Given power limitations, the advent of short-range wireless networks, and the wide physical conditions over which ad hoc networks must be deployed, in some scenarios it is likely that this assumption is invalid. In this work, we develop techniques to deliver messages in the case where there is never a connected path from source to destination or when a network partition exists at the time a message is originated. To this end, we introduce Epidemic Routing, where random pair-wise exchanges of mes- sages among mobile hosts ensure eventual message delivery. The goals of Epidemic Routing are to: i) maximize message delivery rate, ii) minimize message latency, and iii) minimize the total resources consumed in message delivery. Through an implementation in the Monarch simulator, we show that Epidemic Routing achieves eventual delivery of 100% of messages with reasonable aggregate resource consumption in a number of interesting scenarios.
1 Introduction
The advent of inexpensive wireless networking solutions has enabled a broad range of exciting new applica- tions. Wireless network adaptors in portable computing devices, such as cellular phones, personal digital as- sistants, and laptops, can enable ubiquitous access to global information resources. Challenges to achieving this vision include the need to have a wired base station in range of wireless hosts and the energy/expense of transmitting information across large distances. Ad hoc wireless networking addresses some of these challenges by allowing mobile hosts to communicate with one another with no pre-existing communication infrastructure. In ad hoc networks, arbitrary mobile hosts can be recruited to “fill the gap” by serving as in- termediate routers between two hosts that may otherwise not be in direct transmission range of one another. Recent work investigates route discovery and maintenance [6, 16, 19, 21, 25, 26, 27], minimizing power consumption [2, 32], and maintaining QoS guarantees [23, 30, 33] in ad hoc networks.
The common assumption behind existing ad hoc routing techniques is that there is always a connected path from source to destination. However, the advent of short-range wireless communication environments (e.g., Bluetooth [15] and BlueSky [3]) and the wide physical range and circumstances over which such networks are deployed means that this assumption is not always valid in realistic scenarios. Unfortunately, with current ad hoc routing protocols, packets are not delivered if a network partition exists between the source and the destination when a message is originated. Certain applications, such as real-time, constant bit rate communication may require a connected path for meaningful communication. However, a number of other application classes benefit from the eventual and timely delivery of messages, especially in the casewhere frequent and numerous network partitions would prevent messages from ever being delivered end to end. We describe a few of these applications below:
Mobile Sensor Networks: In this example, sensors with wireless connectivity are deployed over a geographic area [11, 17]. These sensors may be simple, e.g., used to detect motion, chemicals, tem- perature, or they may be more sophisticated, e.g., designed to record audio and video. Ideally, these sensors periodically transmit their findings to a base station, perhaps for analysis or permanent stor- age. These sensors may be small and have limited communication range, implying that they are not always able to establish a connected path (leveraging other sensors as routers) back to base stations. Such sensors may be mobile — for example, under their own power1 or because they are suspended in air/water — implying that individual sensors may periodically come into contact with one another through node mobility.
Smart Dust: Related to the previous example, a recent proposal [20] describes challenges in net- works comprised of Micro-electrical Mechanical Sensors (MEMS). Because of the power restrictions associated with their small size, these sensors might utilize optical connections for communication, requiring line of sight between each hop in a connected optical path from source to destination. Fre- quent physical obstructions may make the presence of such a “connected” line of sight path unlikely in some cases, though eventual pair-wise connectivity among MEMS is more likely if the MEMS are mobile.
Disaster Recovery/Military Deployment: In this example, people, in addition to sensors, are deployed over an area with limited wireless coverage (i.e., few, if any, base stations). For disaster recovery, field agents wish to communicate their findings regarding, for example, environmental hazards or survivors to other field agents as well as to a command post. Again, battery concerns and the wide physical dispersement of individual agents make it unlikely that full wireless connectivity can be continuously maintained among all mobile hosts.
DOWNLOAD...
Amin Vahdat and David Becker Department of Computer Science Duke University Durham, NC 27708 (vahdat,becker)@cs.duke.edu