Abstract-Disruption-Tolerant networks (DTNs) differ from other types of networks in that capacity is exclusively created by the movements of participants. This implies that understanding and influencing the participants' motions can have a significant impact on network performance. In this paper, we introduce the routing protocol MV, which learns structure in the movement patterns of network participants and uses it to enable informed message passing. We also propose the introduction of autonomous agents as additional participants in DTNs. These agents adapt their movements in response to variations in network capacity and demand. We use multi-objective control methods from robotics to generate motions capable of optimizing multiple network performance metrics simultaneously. We present experimental evidence that these strategies, individually and in conjunction, result In significant performance improvements in DTNs. Many routing protocols exist to support end-to-end messaging in ad hoc wireless networks [12], [17]. Such protocols assume an end-to-end connection through a contemporaneous set of links through intermediary peers. As a result, if a path between two peers in a network does not exist, communication is not possible. and the route creation process fails. To adapt to situations where simultaneous links in the network are not practical or possible, a growing body of work is exploring techniques for moving network traffic over asynchronous paths. Such networks have varied names: highly-partitioned networks 61, [lo], message ferrying [241, [25j, delay-tolerant networks [XI, and disruption-tolerant networks (.DTNs) [71. To enable end-to-end routing in a DTN (the term we choose for this paper), network participants (or peers) are relied upon to carry and deliver messages of others. Whenever two participants pass, they negotiate the exchange of messages. A message may be passed between a number of network participants before reaching its destination. The performance mevics of disruption-tolerant networks depend on the number of network participants, their storage capacity, communication capabilities, and movement patterns. In this paper, we focus on the performance factor unique to DTNs, namely the movement patterns of participants. We examine how movements can be exploited or controlld to improve performance in DTNs. Movements of network participants are classified according to two independent properties: their inherent structure and their adaptiveness to the demand in of participants' movement pattztns. the network (see Figure 1) . In this context, structure refers to periodic pattems in peers' movements that can be exploited to estimate the probability of delivery for a specific message and peer. For purposes of illustration, we relate this classification of participant's motion and associated routing protocols to everyday experience. The lower-left of the classification shown in Figure 1 corresponds to hitchhikers being picked up by randomly moving cars. In this scenario, cars move without periodicity and do not adapt to the route of the hitchhiker. The lower-right of the figure corresponds to public transport wirh fixed schedules. Independently operating taxicabs that pick up passengers in the street are represented in the top-left of the diagram. Finally, FedEx trucks are situated in the topright corner. Here, packages are transported, rather than people. FedEx trucks travel on structured daily routes, but only stop for scheduled pickups and deliveries, i.e., their route is adjusted in response to demand. From this description it is clear that performance metrics, such as bandwidth and latency. can be expected to improve toward the top-right of the diagram. To achieve these performance improvements, an increased amount of coordination among the network participants is required. Such coordination can exploit structure present in participant's motion patters to improve the efficiency of routing. A coordination of network participants 398 0-7803-
REF introduced the routing protocol MV, which learns structure in the movement patterns of network participants and uses it to enable informed message passing.
MV routing and capacity building in disruption tolerant networks
Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.
Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.
Computer Science