A Survey of Message Diffusion Protocols in Mobile Ad Hoc Networks
---
paper_title: Mobile ad-hoc networking

paper_content:

Mobile ad-hoc networks are multihop wireless networks. Wireless communications and the lack of fixed infrastructure generate new research problems compared with fixed multihop networks: Dynamic topologies. Because nodes can move arbitrarily, the network topology, which is typically multihop, can change randomly and rapidly; Bandwidth-constrained, variable capacity, possibly asymmetric links. Wireless links will continue to have significantly lower capacity than wired links and hence congestion is more problematic. Energy-constrained operation. Some, or all nodes in a Mobile ad-hoc network may rely on batteries for energy. For these nodes, power conservation is a critical design criterion. Wireless vulnerabilities and limited physical security. Mobile wireless networks are generally more prone to information and physical security threats than are fixed, hardwired nets. Network technologies for single-hop wireless networks are becoming to appear on the market. The IEEE 802.11 standard is a good platform to implement a one level multi-hop architecture because of its extreme. The Hiperlan standard is the ETSI standard for wireless LANs. Bluetooth technology is an open specification (supported by several hundreds of IT companies) for wireless communication of data and voice. Soon, mobile ad-hoc networks that cover areas of several square kilometres could be built from WLAN technologies such as IEEE 802.11. Furthermore, wireless-network technologies are the building blocks to construct multi-hop mobile ad-hoc networks. In the IETF, the Mobile Ad-hoc NETwork (MANET) working group was set up for developing and evolving mobile ad-hoc network routing specification(s) and introduce them to the Internet Standards track. The goal is to support networks scaling up to hundreds of routers. The step toward a large network (larger than thousand nodes) consisting of nodes with limited resources is not straightforward and presents many challenges that are still to be solved in areas such as: highcapacity wireless technologies, configuration management, addressing, routing, location management, interoperability, and security. The minitrack presents six papers related to the design, modeling and performance evaluation of architectures and
---
paper_title: MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks

paper_content:

Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.
---
paper_title: A delay-tolerant network architecture for challenged internets

paper_content:

The highly successful architecture and protocols of today's Internet may operate poorly in environments characterized by very long delay paths and frequent network partitions. These problems are exacerbated by end nodes with limited power or memory resources. Often deployed in mobile and extreme environments lacking continuous connectivity, many such networks have their own specialized protocols, and do not utilize IP. To achieve interoperability between them, we propose a network architecture and application interface structured around optionally-reliable asynchronous message forwarding, with limited expectations of end-to-end connectivity and node resources. The architecture operates as an overlay above the transport layers of the networks it interconnects, and provides key services such as in-network data storage and retransmission, interoperable naming, authenticated forwarding and a coarse-grained class of service.
---
paper_title: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet

paper_content:

Over the past decade, mobile computing and wireless communication have become increasingly important drivers of many new computing applications. The field of wireless sensor networks particularly focuses on applications involving autonomous use of compute, sensing, and wireless communication devices for both scientific and commercial purposes. This paper examines the research decisions and design tradeoffs that arise when applying wireless peer-to-peer networking techniques in a mobile sensor network designed to support wildlife tracking for biology research.The ZebraNet system includes custom tracking collars (nodes) carried by animals under study across a large, wild area; the collars operate as a peer-to-peer network to deliver logged data back to researchers. The collars include global positioning system (GPS), Flash memory, wireless transceivers, and a small CPU; essentially each node is a small, wireless computing device. Since there is no cellular service or broadcast communication covering the region where animals are studied, ad hoc, peer-to-peer routing is needed. Although numerous ad hoc protocols exist, additional challenges arise because the researchers themselves are mobile and thus there is no fixed base station towards which to aim data. Overall, our goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate. We plan to deploy a 30-node ZebraNet system at the Mpala Research Centre in central Kenya. More broadly, we believe that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications.
---
paper_title: Comparison of broadcasting techniques for mobile ad hoc networks

paper_content:

Network wide broadcasting in Mobile Ad Hoc Networks provides important control and route establishment functionality for a number of unicast and multicast protocols. Considering its wide use as a building block for other network layer protocols, the MANET community needs to standardize a single methodology that efficiently delivers a packet from one node to all other network nodes. Despite a considerable number of proposed broadcasting schemes, no comprehensive comparative analysis has been previously done. This paper provides such analysis by classifying existing broadcasting schemes into categories and simulating a subset of each, thus supplying a condensed but comprehensive side by side comparison.The simulations are designed to pinpoint, in each, specific failures to network conditions that are relevant to MANETs, e.g., bandwidth congestion and dynamic topologies. In addition, protocol extensions using adaptive responses to network conditions are proposed, implemented and analyzed for one broadcasting scheme that performs well in the comparative study.
---
paper_title: The broadcast storm problem in a mobile ad hoc network

paper_content:

Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach.
---
paper_title: Intelligent broadcasting in mobile ad hoc networks: Three classes of adaptive protocols

paper_content:

Because adaptability greatly improves the performance of a broadcast protocol, we identify three ways in which machine learning can be applied to broadcasting in a mobile ad hoc network (MANET). We chose broadcasting because it functions as a foundation of MANET communication. Unicast, multicast, and geocast protocols utilize broadcasting as a building block, providing important control and route establishment functionality. Therefore, any improvements to the process of broadcasting can be immediately realized by higher-level MANET functionality and applications. While efficient broadcast protocols have been proposed, no single broadcasting protocol works well in all possible MANET conditions. Furthermore, protocols tend to fail catastrophically in severe network environments. Our three classes of adaptive protocols are pure machine learning, intra-protocol learning, and inter-protocol learning. In the pure machine learning approach, we exhibit a new approach to the design of a broadcast protocol: the decision of whether to rebroadcast a packet is cast as a classification problem. Each mobile node (MN) builds a classifier and trains it on data collected from the network environment. Using intra-protocol learning, each MN consults a simple machine model for the optimal value of one of its free parameters. Lastly, in inter-protocol learning, MNs learn to switch between different broadcasting protocols based on network conditions. For each class of learning method, we create a prototypical protocol and examine its performance in simulation.
---
paper_title: On calculating connected dominating set for efficient routing in ad hoc wireless networks

paper_content:

Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad-hoc wireless networks. Routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, we propose a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances. Our simulation results show that the proposed approach outperforms a classical algorithm. Our approach can be potentially used in designing efficient routing algorithms based on a connected dominating set.
---
paper_title: Broadcasting in Ad Hoc Networks Based on Self-Pruning

paper_content:

We propose a general framework for broadcasting in ad hoc networks through self-pruning. The approach is based on selecting a small subset of hosts (also called nodes) to form a forward node set on carry out a broadcast process. Each node, upon receiving a broadcast packet, determines whether to forward the packet or not based on two neighborhood coverage conditions proposed in this paper. These coverage conditions depend on neighbor connectivity and history of visited nodes, and in general, resort to global network information. Using local information such as k-hop neighborhood information, the forward node set is selected through a distributed and local pruning process. The forward node set can be constructed and maintained through either a proactive process (i.e., "up-to-date") or a reactive process (i.e., "on-the-fly"). Several existing broadcast algorithms can be viewed as special cases of the coverage conditions with k-hop neighborhood information. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the coverage conditions, and self-pruning based on 2- or 3-hop neighborhood information is relatively more cost-effective.
---
paper_title: Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks

paper_content:

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.
---
paper_title: AHBP: An efficient broadcast protocol for mobile Ad hoc networks

paper_content:

Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to large networks. This paper presents the Ad Hoc Broadcast Protocol (AHBP) and its performance is discussed. In the protocol, messages are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network. AHBP can efficiently reduce the redundant messages which make flooding-like protocols perform badly in large dense networks. Simulations are conducted to determine the performance characteristics of the protocol. The simulation results have shown excellent reduction of broadcast redundancy with AHBP. It also contributes to a reduced level of broadcast collision and congestion.
---
paper_title: Performance analysis of broadcast protocols in ad hoc networks based on self-pruning

paper_content:

Self-pruning is an effective scheme for efficient broadcasting in ad hoc wireless networks. In a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. In a static network with an ideal MAC layer, only a subset of nodes forward the broadcast packet and still guarantee the complete network delivery. Various protocols have been proposed with different self-pruning conditions. Recently, a generic self-pruning protocol was proposed by Wu and Dai (2003), which combines the strength of previous conditions and is more effective. In this paper, we first propose an enhanced version of the generic protocol, which is more elegant in interpreting existing protocols and has a simpler correctness proof. Then, we evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world". Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks.
---
paper_title: The broadcast storm problem in a mobile ad hoc network

paper_content:

Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach.
---
paper_title: Adaptive protocols for information dissemination in wireless sensor networks

paper_content:

In this paper, we present a family of adaptive protocols, called SPIN (Sensor Protocols for Information via Negotiation), that efficiently disseminates information among sensors in an energy-constrained wireless sensor network. Nodes running a SPIN communication protocol name their data using high-level data descriptors, called meta-data. They use meta-data negotiations to eliminate the transmission of redundant data throughout the network. In addition, SPIN nodes can base their communication decisions both upon application-specific knowledge of the data and upon knowledge of the resources that are available to them. This allows the sensors to efficiently distribute data given a limited energy supply. We simulate and analyze the performance of two specific SPIN protocols, comparing them to other possible approaches and a theoretically optimal protocol. We find that the SPIN protocols can deliver 60% more data for a given amount of energy than conventional approaches. We also find that, in terms of dissemination rate and energy usage, the SPlN protocols perform close to the theoretical optimum.
---
paper_title: On calculating connected dominating set for efficient routing in ad hoc wireless networks

paper_content:

Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad-hoc wireless networks. Routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, we propose a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances. Our simulation results show that the proposed approach outperforms a classical algorithm. Our approach can be potentially used in designing efficient routing algorithms based on a connected dominating set.
---
paper_title: The broadcast storm problem in a mobile ad hoc network

paper_content:

Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach.
---
paper_title: Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network

paper_content:

In a multihop mobile ad hoc network, broadcasting is an elementary operation to support many applications. Previously, it is shown that naively broadcasting by flooding may cause serious redundancy, contention, and collision in the network, which we refer to as the broadcast storm problem. Several threshold-based schemes are shown to perform better than flooding in that work. However, how to choose thresholds also poses a dilemma between reachability and efficiency under different host densities. In this paper, we propose several adaptive schemes, which can dynamically adjust thresholds based on local connectivity information. Simulation results show that these adaptive schemes can offer better reachability as well as efficiency as compared to the previous results.
---
paper_title: Comparison of broadcasting techniques for mobile ad hoc networks

paper_content:

Network wide broadcasting in Mobile Ad Hoc Networks provides important control and route establishment functionality for a number of unicast and multicast protocols. Considering its wide use as a building block for other network layer protocols, the MANET community needs to standardize a single methodology that efficiently delivers a packet from one node to all other network nodes. Despite a considerable number of proposed broadcasting schemes, no comprehensive comparative analysis has been previously done. This paper provides such analysis by classifying existing broadcasting schemes into categories and simulating a subset of each, thus supplying a condensed but comprehensive side by side comparison.The simulations are designed to pinpoint, in each, specific failures to network conditions that are relevant to MANETs, e.g., bandwidth congestion and dynamic topologies. In addition, protocol extensions using adaptive responses to network conditions are proposed, implemented and analyzed for one broadcasting scheme that performs well in the comparative study.
---
paper_title: On the reduction of broadcast redundancy in mobile ad hoc networks

paper_content:

Flooding in mobile ad hoc networks has poor scalability as it leads to serious redundancy, contention and collision. In this paper, we propose an efficient approach to reduce the broadcast redundancy. In our approach, local topology information and the statistical information about the duplicate broadcasts are utilized to avoid unnecessary rebroadcasts. Simulation is conducted to compare the performance of our approach and flooding. The simulation results demonstrate the advantages of our approach. It can greatly reduce the redundant messages, thus saving much network bandwidth and energy. It can also enhance the reliability of broadcasting. It can be used in static or mobile wireless networks to implement scalable broadcast or multicast communications.
---
paper_title: Broadcasting in Ad Hoc Networks Based on Self-Pruning

paper_content:

We propose a general framework for broadcasting in ad hoc networks through self-pruning. The approach is based on selecting a small subset of hosts (also called nodes) to form a forward node set on carry out a broadcast process. Each node, upon receiving a broadcast packet, determines whether to forward the packet or not based on two neighborhood coverage conditions proposed in this paper. These coverage conditions depend on neighbor connectivity and history of visited nodes, and in general, resort to global network information. Using local information such as k-hop neighborhood information, the forward node set is selected through a distributed and local pruning process. The forward node set can be constructed and maintained through either a proactive process (i.e., "up-to-date") or a reactive process (i.e., "on-the-fly"). Several existing broadcast algorithms can be viewed as special cases of the coverage conditions with k-hop neighborhood information. Simulation results show that new algorithms, which are more efficient than existing ones, can be derived from the coverage conditions, and self-pruning based on 2- or 3-hop neighborhood information is relatively more cost-effective.
---
paper_title: Efficient flooding in ad hoc networks: a comparative performance study

paper_content:

The blind flooding can become very inefficient because of redundant, "superfluous" forwarding. In fact, superfluous flooding increases link overhead and wireless medium congestion. In a large network, with heavy load, this extra overhead can have severe impact on performance and should be eliminated. Efficient flooding schemes to choose a dominant set of nodes have been recently proposed in ad hoc networks. In this paper, we compare the performance of a set of representative schemes via simulation using as criteria the flooding efficiency and the delivery ratio.
---
paper_title: Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks

paper_content:

In this paper we discuss the mechanism of multipoint relays (MPRs) to efficiently do the flooding of broadcast messages in the mobile wireless networks. Multipoint relaying is a technique to reduce the number of redundant re-transmissions while diffusing a broadcast message in the network. We discuss the principle and the functioning of MPRs, and propose a heuristic to select these MPRs in a mobile wireless environment. We also analyze the complexity of this heuristic and prove that the computation of a multipoin- t relay set with minimal size is NP-complete. Finally, we present some simulation results to show the efficiency of multipoint relays.
---
paper_title: Stochastic Flooding Broadcast Protocols in Mobile Wireless Networks

paper_content:

In wireless communication environment, the information broadcast based on the flooding protocol leads to an overload of network bandwidth (each mobile node has to send the broadcasted message). So, each node has to obtain medium access and transmit its data. However, in dense network (e.g. more than 15 nodes per communication space) the collision probability (in MAC layer) is very high and the number of lost packets is then important. In this paper, we propose some improvements of the flooding protocols that aim to efficiently broadcast a given information through the whole network. These variants are based on stochastic approach and decrease the number of emitted packets and hence, the medium occupation.
---
paper_title: Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks

paper_content:

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.
---
paper_title: AHBP: An efficient broadcast protocol for mobile Ad hoc networks

paper_content:

Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to large networks. This paper presents the Ad Hoc Broadcast Protocol (AHBP) and its performance is discussed. In the protocol, messages are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network. AHBP can efficiently reduce the redundant messages which make flooding-like protocols perform badly in large dense networks. Simulations are conducted to determine the performance characteristics of the protocol. The simulation results have shown excellent reduction of broadcast redundancy with AHBP. It also contributes to a reduced level of broadcast collision and congestion.
---
paper_title: Performance analysis of broadcast protocols in ad hoc networks based on self-pruning

paper_content:

Self-pruning is an effective scheme for efficient broadcasting in ad hoc wireless networks. In a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. In a static network with an ideal MAC layer, only a subset of nodes forward the broadcast packet and still guarantee the complete network delivery. Various protocols have been proposed with different self-pruning conditions. Recently, a generic self-pruning protocol was proposed by Wu and Dai (2003), which combines the strength of previous conditions and is more effective. In this paper, we first propose an enhanced version of the generic protocol, which is more elegant in interpreting existing protocols and has a simpler correctness proof. Then, we evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world". Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks.
---
paper_title: Investigating data broadcast performance in mobile ad-hoc networks

paper_content:

We investigate broadcasting in mobile ad-hoc networks (MANETs). We define broadcasting as being the process of delivering one packet, originated at one node, to (ideally) all other nodes in the MANET. We present specific problems related to broadcasting in MANETs, as well as four broadcast protocols aimed at providing MANET-wide broadcast. Further, three protocol-independent modifications are presented. One aimed at ensuring that a broadcast packet traverses at least the "shortest path" to its destinations, and two aimed at increasing the fraction of nodes which receive a broadcast packet. Through simulation studies, we evaluate the performance characteristics of the broadcast protocols and generic modifications under different conditions.
---
paper_title: Hypergossiping: A generalized broadcast strategy for mobile ad hoc networks

paper_content:

Broadcasting is a commonly used communication primitive needed by many applications and protocols in mobile ad hoc networks (MANET). Unfortunately, most broadcast solutions are tailored to one class of MANETs with respect to node density and node mobility and are unlikely to operate well in other classes. In this paper, we introduce hypergossiping, a novel adaptive broadcast algorithm that combines two strategies. Hypergossiping uses adaptive gossiping to efficiently distribute messages within single network partitions and implements an efficient heuristic to distribute them across partitions. Simulation results in ns-2 show that hypergossiping operates well for a broad range of MANETs with respect to node densities, mobility levels and network loads.
---
paper_title: Optimized Flooding Protocol for Ad hoc Networks

paper_content:

Flooding provides important control and route establishment functionality for a number of unicast and multicast protocols in Mobile Ad Hoc Networks. Considering its wide use as a building block for other network layer protocols, the flooding methodology should deliver a packet from one node to all other network nodes using as few messages as possible. In this paper, we propose the Optimized Flooding Protocol (OFP), based on a variation of The Covering Problem that is encountered in geometry, to minimize the unnecessary transmissions drastically and still be able to cover the whole region. OFP does not need hello messages and hence OFP saves a significant amount of wireless bandwidth and incurs lesser overhead. We present simulation results to show the efficiency of OFP in both ideal cases and randomly distributed networks. Moreover, OFP is scalable with respect to density; in fact OFP requires lesser number of transmissions at higher densities. OFP is also resilient to transmission errors.
---
paper_title: The case for technology in developing regions

paper_content:

Alongside good governance, technology is considered among the greatest enablers for improved quality of life. However, the majority of its benefits have been concentrated in industrialized nations and therefore limited to a fraction of the world's population. We believe that technology has a large role to play in developing regions, that "First World" technology to date has been a poor fit in these areas, and that there is thus a need for technology research for developing regions. Despite the relative infancy of technology studies in developing regions, anecdotal evidence suggests that access to technology has a beneficial economic impact. Cellular telephony is probably the most visible application, but there are many others, some of which we cover in this article. The World Bank's infoDev site catalogs hundreds of information and communications technologies (ICT) projects, albeit not all successful. Most of these projects use existing off-the-shelf technology designed for the industrialized world. Although it is clear that there are large differences in assumptions related to cost, power, and usage, there has been little work on how technology needs in developing regions differ from those of industrialized nations. We argue that Western market forces continue to meet the needs of developing regions accidentally at best.
---
paper_title: A delay-tolerant network architecture for challenged internets

paper_content:

The highly successful architecture and protocols of today's Internet may operate poorly in environments characterized by very long delay paths and frequent network partitions. These problems are exacerbated by end nodes with limited power or memory resources. Often deployed in mobile and extreme environments lacking continuous connectivity, many such networks have their own specialized protocols, and do not utilize IP. To achieve interoperability between them, we propose a network architecture and application interface structured around optionally-reliable asynchronous message forwarding, with limited expectations of end-to-end connectivity and node resources. The architecture operates as an overlay above the transport layers of the networks it interconnects, and provides key services such as in-network data storage and retransmission, interoperable naming, authenticated forwarding and a coarse-grained class of service.
---
paper_title: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet

paper_content:

Over the past decade, mobile computing and wireless communication have become increasingly important drivers of many new computing applications. The field of wireless sensor networks particularly focuses on applications involving autonomous use of compute, sensing, and wireless communication devices for both scientific and commercial purposes. This paper examines the research decisions and design tradeoffs that arise when applying wireless peer-to-peer networking techniques in a mobile sensor network designed to support wildlife tracking for biology research.The ZebraNet system includes custom tracking collars (nodes) carried by animals under study across a large, wild area; the collars operate as a peer-to-peer network to deliver logged data back to researchers. The collars include global positioning system (GPS), Flash memory, wireless transceivers, and a small CPU; essentially each node is a small, wireless computing device. Since there is no cellular service or broadcast communication covering the region where animals are studied, ad hoc, peer-to-peer routing is needed. Although numerous ad hoc protocols exist, additional challenges arise because the researchers themselves are mobile and thus there is no fixed base station towards which to aim data. Overall, our goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate. We plan to deploy a 30-node ZebraNet system at the Mpala Research Centre in central Kenya. More broadly, we believe that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications.
---
paper_title: Drive-thru Internet: IEEE 802.11b for "automobile" users

paper_content:

This paper reports on measurement results for the use of IEEE 802.11 networks in drive-thru scenarios: we have measured transmission characteristics for sending and receiving high data volumes using UDP and TCP in vehicles moving at different speeds that pass one or more IEEE 802.11 access points at the roadside. We discuss possibilities and limitations for the use of scattered WLAN cells by devices in fast moving vehicles and provide an analysis of the performance that can he expected for the communication in such scenarios. Based on these observations, we discuss implications for higher-layer protocols and applications.
---
paper_title: Routing in a delay tolerant network

paper_content:

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.
---
paper_title: Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks

paper_content:

An ad hoc network allows devices with wireless interfaces to communicate with each other without any pre-installed infrastructure. Due to node mobility, limited radio power, node failure and wide deployment area, ad hoc networks are often vulnerable to network partitioning. A number of examples are in battlefield, disaster recovery and wide area surveillance. Unfortunately, most existing ad hoc routing protocols will fail to deliver messages under these circumstances since no route to the destination exists. In this work we propose the Message Ferrying or MF scheme that provides efficient data delivery in disconnected ad hoc networks. In the MF scheme, nodes move proactively to send or receive messages. By introducing non-randomness in a node's proactive movement and exploiting such nonrandomness to deliver messages, the MF scheme improves data delivery performance in a disconnected network. In this paper, we propose the basic design of the MF scheme and develop a general framework to classify variations of MF systems. We also study ferry route design problem in stationary node case which is shown to be NP-hard and provide an efficient algorithm to compute ferry route.
---
paper_title: A message ferrying approach for data delivery in sparse mobile ad hoc networks

paper_content:

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.
---
paper_title: MV routing and capacity building in disruption tolerant networks

paper_content:

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.
---
paper_title: Controlling the mobility of multiple data transport ferries in a delay-tolerant network

paper_content:

As technology rapidly progresses, more devices will combine both communication and mobility capabilities. With mobility in devices, we envision a new class of proactive networks that are able to adapt themselves, via physical movement, to meet the needs of applications. To fully realize these opportunities, effective control of device mobility and the interaction between devices is needed. In this paper, we consider the message ferrying (MF) scheme which exploits controlled mobility to transport data in delay-tolerant networks, where end-to-end paths may not exist between nodes. In the MF scheme, a set of special mobile nodes called message ferries are responsible for carrying data for nodes in the network. We study the use of multiple ferries in such networks, which may be necessary to address performance and robustness concerns. We focus on the design of ferry routes. With the possibilities of interaction between ferries, the route design problem is challenging. We present algorithms to calculate routes such that the traffic demand is met and the data delivery delay is minimized. We evaluate these algorithms under a variety of network conditions via simulations. Our goal is to guide the design of MF systems and understand the tradeoff between the incurred cost of multiple ferries and the improved performance. We show that the performance scales well with the number of ferries in terms of throughput, delay and resource requirements in both ferries and nodes.
---
paper_title: Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks

paper_content:

The decreasing size and cost of wearable computers and mobile sensors is presenting new challenges and opportunities for deploying networks. Existing network routing protocols provide reliable communication between nodes and allow for mobility and even ad-hoc deployment. They rely, however on the assumption of a dense scattering of nodes and end-to-end connectivity in the network. In this paper we address routing support for ad-hoc, wireless networks under conditions of sporadic connectivity and ever-present network partitions. This work proposes a general framework of agent movement and communication in which mobile computers physically carry packets across network partitions. We then propose algorithms that exploit the relative position of stationary devices and non-randonmess in the movement of mobile agents in the network. The learned structure of the network is used to inform an adaptive routing strategy With a simulation, we evaluate these algorithms and their ability to route packets efficiently through a highly-partitioned network.
---
paper_title: Exploiting social interactions in mobile systems

paper_content:

The popularity of handheld devices has created a flurry of research activity into new protocols and applications that can handle and exploit the defining characteristic of this new environment - user mobility. In addition to mobility, another defining characteristic of mobile systems is user social interaction. This paper investigates how mobile systems could exploit people's social interactions to improve these systems' performance and query hit rate. For this, we build a trace-driven simulator that enables us to re-create the behavior of mobile systems in a social environment. We use our simulator to study three diverse mobile systems: DTN routing protocols, firewalls preventing a worm infection, and a mobile P2P file-sharing system. In each of these three cases, we find that mobile systems can benefit substantially from exploiting social information.
---
paper_title: Evaluating Mobility Pattern Space Routing for DTNs

paper_content:

Because a delay tolerant network (DTN) can often be partitioned, routing is a challenge. However, routing benefits considerably if one can take advantage of knowledge concerning node mobility. This paper addresses this problem with a generic algorithm based on the use of a high-dimensional Euclidean space, that we call MobySpace, constructed upon nodes' mobility patterns. We provide here an analysis and a large scale evaluation of this routing scheme in the context of ambient networking by replaying real mobility traces. The specific MobySpace evaluated is based on the frequency of visits of nodes to each possible location. We show that routing based on MobySpace can achieve good performance compared to that of a number of standard algorithms, especially for nodes that are present in the network a large portion of the time. We determine that the degree of homogeneity of node mobility patterns has a high impact on routing. And finally, we study the ability of nodes to learn their own mobility patterns.
---
paper_title: Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks

paper_content:

Mobile wireless ad hoc and sensor networks can be permanently partitioned in many interesting scenarios. This implies that instantaneous end-to-end routes do not exist. Nevertheless, when nodes are mobile, it is possible to forward messages to their destinations through mobility. We observe that in many practical settings, spatial node distributions are very heterogeneous and possess concentration points of high node density. The locations of these concentration points and the flow of nodes between them tend to be stable over time. This motivates a novel mobility model, where nodes move randomly between stable islands of connectivity, where they are likely to encounter other nodes, while connectivity is very limited outside these islands. Our goal is to exploit such a stable topology of concentration points by developing algorithms that allow nodes to collaborate to discover this topology and to use it for efficient mobility forwarding. We achieve this without any external signals to nodes, such as geographic positions or fixed beacons; instead, we rely only on the evolution of the set of neighbors of each node. We propose an algorithm for this collaborative graph discovery problem and show that the inferred topology can greatly improve the efficiency of mobility forwarding. Using both synthetic and data-driven mobility models we show through simulations that our approach achieves end-to-end delays comparable to those of epidemic approaches, while requiring a significantly lower transmission overhead
---
paper_title: Learning to predict by the methods of temporal differences

paper_content:

This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.
---
paper_title: Practical routing in delay-tolerant networks

paper_content:

Delay-tolerant networks (DTNs) have the potential to connect devices and areas of the world that are under-served by current networks. A critical challenge for DTNs is determining routes through the network without ever having an end-to-end connection, or even knowing which "routers" will be connected at any given time. Prior approaches have focused either on epidemic message replication or on knowledge of the connectivity schedule. The epidemic approach of replicating messages to all nodes is expensive and does not appear to scale well with increasing load. It can, however, operate without any prior network configuration. The alternatives, by requiring a priori connectivity knowledge, appear infeasible for a self-configuring network.In this paper we present a practical routing protocol that only uses observed information about the network. We designed a metric that estimates how long a message will have to wait before it can be transferred to the next hop. The topology is distributed using a link-state routing protocol, where the link-state packets are "flooded" using epidemic routing. The routing is recomputed when connections are established. Messages are exchanged if the topology suggests that a connected node is "closer" than the current node.We demonstrate through simulation that our protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires a significantly smaller quantity of buffer, suggesting that our approach will scale with the number of messages in the network, where replication approaches may not.
---
paper_title: Epidemic Routing for Partially-Connected Ad Hoc Networks

paper_content:

Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one another 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 messages 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.
---
paper_title: Probabilistic routing in intermittently connected networks

paper_content:

We consider the problem of routing in intermittently connected networks. In such networks there is no guarantee that a fully connected path between source and destination exist at any time, rendering traditional routing protocols unable to deliver messages between hosts. We propose a probabilistic routing protocol for such networks.
---
paper_title: Routing in a delay tolerant network

paper_content:

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.
---
paper_title: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet

paper_content:

Over the past decade, mobile computing and wireless communication have become increasingly important drivers of many new computing applications. The field of wireless sensor networks particularly focuses on applications involving autonomous use of compute, sensing, and wireless communication devices for both scientific and commercial purposes. This paper examines the research decisions and design tradeoffs that arise when applying wireless peer-to-peer networking techniques in a mobile sensor network designed to support wildlife tracking for biology research.The ZebraNet system includes custom tracking collars (nodes) carried by animals under study across a large, wild area; the collars operate as a peer-to-peer network to deliver logged data back to researchers. The collars include global positioning system (GPS), Flash memory, wireless transceivers, and a small CPU; essentially each node is a small, wireless computing device. Since there is no cellular service or broadcast communication covering the region where animals are studied, ad hoc, peer-to-peer routing is needed. Although numerous ad hoc protocols exist, additional challenges arise because the researchers themselves are mobile and thus there is no fixed base station towards which to aim data. Overall, our goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate. We plan to deploy a 30-node ZebraNet system at the Mpala Research Centre in central Kenya. More broadly, we believe that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications.
---
paper_title: Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks

paper_content:

The decreasing size and cost of wearable computers and mobile sensors is presenting new challenges and opportunities for deploying networks. Existing network routing protocols provide reliable communication between nodes and allow for mobility and even ad-hoc deployment. They rely, however on the assumption of a dense scattering of nodes and end-to-end connectivity in the network. In this paper we address routing support for ad-hoc, wireless networks under conditions of sporadic connectivity and ever-present network partitions. This work proposes a general framework of agent movement and communication in which mobile computers physically carry packets across network partitions. We then propose algorithms that exploit the relative position of stationary devices and non-randonmess in the movement of mobile agents in the network. The learned structure of the network is used to inform an adaptive routing strategy With a simulation, we evaluate these algorithms and their ability to route packets efficiently through a highly-partitioned network.
---
paper_title: Simple Models for the Performance Evaluation of a Class of Two-Hop Relay Protocols

paper_content:

We evaluate the performance of a class of two-hop relay protocols for mobile ad hoc networks. The interest is on the multicopy two-hop relay (MTR) protocol, where the source may generate multiple copies of a packet and use relay nodes to deliver the packet (or a copy) to its destination, and on the two-hop relay protocol with erasure coding. Performance metrics of interest are the time to deliver a single packet to its destination, the number of copies of the packet at delivery instant, and the total number of copies that the source generates. The packet copies at relay nodes have limited lifetime (time-to-live TTL). Via a Markovian analysis, the three performance metrics of the MTR protocol are obtained in closed-from in the case where the number of the copies in the network is limited. Also, we develop an approximation analysis in the case where the inter-meeting times between nodes are arbitrarily distributed and the TTLs of the copies are constant and all equal. In particular, we show that exponential intermeeting times yield stochastically smaller delivery delays than hyper-exponential inter-meeting times, and that exponential TTLs yield stochastically larger delivery delays than constant TTLs. Finally, we characterize the delivery delay and the number of transmissions in the two-hop relay protocol with erasure coding and compare this scheme with the multicopy scheme.
---
paper_title: Performance Modeling of Epidemic Routing

paper_content:

In this paper, we develop a rigorous, unified framework based on ordinary differential equations (ODEs) to study epidemic routing and its variations. These ODEs can be derived as limits of Markovian models under a natural scaling as the number of nodes increases. While an analytical study of Markovian models is quite complex and numerical solution impractical for large networks, the corresponding ODE models yield closed-form expressions for several performance metrics of interest, and a numerical solution complexity that does not increase with the number of nodes. Using this ODE approach, we investigate how resources such as buffer space and the number of copies made for a packet can be traded for faster delivery, illustrating the differences among various forwarding and recovery schemes considered. We perform model validations through simulation studies. Finally we consider the effect of buffer management by complementing the forwarding models with Markovian and fluid buffer models.
---
paper_title: Performance of Ad Hoc Networks with Two-Hop Relay Routing and Limited Packet Lifetime

paper_content:

Considered is a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing protocol. Packets at relay nodes are assumed to have a limited lifetime in the network. All nodes are moving inside a bounded region according to some random mobility model. Both closed-form expressions, and asymptotic results are provided for the packet delivery delay and the energy needed to transmit a packet from the source to its destination. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), numerical results for the two-hop relay protocols are reported, and the performance of the two-hop routing and of the epidemic routing protocols are compared.
---
paper_title: Mobility increases the capacity of ad-hoc wireless networks

paper_content:

The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.
---
paper_title: Epidemic Routing for Partially-Connected Ad Hoc Networks

paper_content:

Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one another 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 messages 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.
---
paper_title: Delay and resource analysis in MANETs in presence of throwboxes

paper_content:

This paper addresses the delay analysis and resource consumption in mobile ad hoc networks (MANETs) equipped with throwboxes. Throwboxes are stationary, wireless devices that act as relays, and that are deployed to increase the connectivity between mobile nodes. Our objective is to quantify the impact of adding throwboxes on the performance of two routing protocols, namely the Multicopy Two-hop Routing protocol and the Epidemic Routing protocol, in the cases where the throwboxes are fully disconnected or mesh connected. To this end, we use a Markovian model where the successive meeting times between any pair of mobile nodes (resp. any mobile node and any throwbox) are represented by a Poisson process with intensity @l (resp. @m). We derive closed-form expressions for the distribution of the delivery delay of a packet and for the distribution of the total number of copies of a packet that are generated, the latter metric reflecting the overhead induced by the routing protocol. These results are then compared to simulation results. Through a mean-field approach we also provide asymptotic results when the number of nodes (mobile nodes and/or throwboxes) is large.
---
paper_title: Spray and wait: an efficient routing scheme for intermittently connected mobile networks

paper_content:

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.
---
paper_title: Simple Models for the Performance Evaluation of a Class of Two-Hop Relay Protocols

paper_content:

We evaluate the performance of a class of two-hop relay protocols for mobile ad hoc networks. The interest is on the multicopy two-hop relay (MTR) protocol, where the source may generate multiple copies of a packet and use relay nodes to deliver the packet (or a copy) to its destination, and on the two-hop relay protocol with erasure coding. Performance metrics of interest are the time to deliver a single packet to its destination, the number of copies of the packet at delivery instant, and the total number of copies that the source generates. The packet copies at relay nodes have limited lifetime (time-to-live TTL). Via a Markovian analysis, the three performance metrics of the MTR protocol are obtained in closed-from in the case where the number of the copies in the network is limited. Also, we develop an approximation analysis in the case where the inter-meeting times between nodes are arbitrarily distributed and the TTLs of the copies are constant and all equal. In particular, we show that exponential intermeeting times yield stochastically smaller delivery delays than hyper-exponential inter-meeting times, and that exponential TTLs yield stochastically larger delivery delays than constant TTLs. Finally, we characterize the delivery delay and the number of transmissions in the two-hop relay protocol with erasure coding and compare this scheme with the multicopy scheme.
---
paper_title: Digital fountains: a survey and look forward

paper_content:

We survey constructions and applications of digital fountains, an abstraction of erasure coding for network communication. Digital fountains effectively change the standard paradigm where a user receives an ordered stream of packets to one where a user must simply receive enough packets in order to obtain the desired data. Obviating the need for ordered data simplifies data delivery, especially when the data is large or is to be distributed to a large number of users. We also examine barriers to the adoption of digital fountains and discuss whether they can be overcome.
---
paper_title: Network coding for efficient communication in extreme networks

paper_content:

Some forms of ad-hoc networks need to operate in extremely performance-challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes "meet" only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing.We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead.
---
paper_title: Erasure-coding based routing for opportunistic networks

paper_content:

Routing in Delay Tolerant Networks (DTN) with unpredictable node mobility is a challenging problem because disconnections are prevalent and lack of knowledge about network dynamics hinders good decision making. Current approaches are primarily based on redundant transmissions. They have either high overhead due to excessive transmissions or long delays due to the possibility of making wrong choices when forwarding a few redundant copies. In this paper, we propose a novel forwarding algorithm based on the idea of erasure codes. Erasure coding allows use of a large number of relays while maintaining a constant overhead, which results in fewer cases of long delays.We use simulation to compare the routing performance of using erasure codes in DTN with four other categories of forwarding algorithms proposed in the literature. Our simulations are based on a real-world mobility trace collected in a large outdoor wild-life environment. The results show that the erasure-coding based algorithm provides the best worst-case delay performance with a fixed amount of overhead. We also present a simple analytical model to capture the delay characteristics of erasure-coding based forwarding, which provides insights on the potential of our approach.
---
paper_title: Using redundancy to cope with failures in a delay tolerant network

paper_content:

We consider the problem of routing in a delay tolerant network (DTN) in the presence of path failures. Previous work on DTN routing has focused on using precisely known network dynamics, which does not account for message losses due to link failures, buffer overruns, path selection errors, unscheduled delays, or other problems. We show how to split, replicate, and erasure code message fragments over multiple delivery paths to optimize the probability of successful message delivery. We provide a formulation of this problem and solve it for two cases: a 0/1 (Bernoulli) path delivery model where messages are either fully lost or delivered, and a Gaussian path delivery model where only a fraction of a message may be delivered. Ideas from the modern portfolio theory literature are borrowed to solve the underlying optimization problem. Our approach is directly relevant to solving similar problems that arise in replica placement in distributed file systems and virtual node placement in DHTs. In three different simulated DTN scenarios covering a wide range of applications, we show the effectiveness of our approach in handling failures.
---
paper_title: On calculating connected dominating set for efficient routing in ad hoc wireless networks

paper_content:

Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad-hoc wireless networks. Routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, we propose a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances. Our simulation results show that the proposed approach outperforms a classical algorithm. Our approach can be potentially used in designing efficient routing algorithms based on a connected dominating set.
---
paper_title: Simple Models for the Performance Evaluation of a Class of Two-Hop Relay Protocols

paper_content:

We evaluate the performance of a class of two-hop relay protocols for mobile ad hoc networks. The interest is on the multicopy two-hop relay (MTR) protocol, where the source may generate multiple copies of a packet and use relay nodes to deliver the packet (or a copy) to its destination, and on the two-hop relay protocol with erasure coding. Performance metrics of interest are the time to deliver a single packet to its destination, the number of copies of the packet at delivery instant, and the total number of copies that the source generates. The packet copies at relay nodes have limited lifetime (time-to-live TTL). Via a Markovian analysis, the three performance metrics of the MTR protocol are obtained in closed-from in the case where the number of the copies in the network is limited. Also, we develop an approximation analysis in the case where the inter-meeting times between nodes are arbitrarily distributed and the TTLs of the copies are constant and all equal. In particular, we show that exponential intermeeting times yield stochastically smaller delivery delays than hyper-exponential inter-meeting times, and that exponential TTLs yield stochastically larger delivery delays than constant TTLs. Finally, we characterize the delivery delay and the number of transmissions in the two-hop relay protocol with erasure coding and compare this scheme with the multicopy scheme.
---
paper_title: Performance Modeling of Epidemic Routing

paper_content:

In this paper, we develop a rigorous, unified framework based on ordinary differential equations (ODEs) to study epidemic routing and its variations. These ODEs can be derived as limits of Markovian models under a natural scaling as the number of nodes increases. While an analytical study of Markovian models is quite complex and numerical solution impractical for large networks, the corresponding ODE models yield closed-form expressions for several performance metrics of interest, and a numerical solution complexity that does not increase with the number of nodes. Using this ODE approach, we investigate how resources such as buffer space and the number of copies made for a packet can be traded for faster delivery, illustrating the differences among various forwarding and recovery schemes considered. We perform model validations through simulation studies. Finally we consider the effect of buffer management by complementing the forwarding models with Markovian and fluid buffer models.
---
paper_title: Capacity and delay tradeoffs for ad hoc mobile networks

paper_content:

We consider the throughput/delay tradeoffs for scheduling data transmissions in a mobile ad hoc network. To reduce delays in the network, each user sends redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified independent and identically distributed (i.i.d.) mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity-achieving algorithm is a modified version of the Grossglauser-Tse two-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay/rate/spl ges/O(N). Two protocols that use redundancy and operate near the boundary of this curve are developed, with delays of O(/spl radic/N) and O(log(N)), respectively. Networks with non-i.i.d. mobility are also considered and shown through simulation to closely match the performance of i.i.d. systems in the O(/spl radic/N) delay regime.
---
paper_title: Performance of Ad Hoc Networks with Two-Hop Relay Routing and Limited Packet Lifetime

paper_content:

Considered is a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing protocol. Packets at relay nodes are assumed to have a limited lifetime in the network. All nodes are moving inside a bounded region according to some random mobility model. Both closed-form expressions, and asymptotic results are provided for the packet delivery delay and the energy needed to transmit a packet from the source to its destination. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), numerical results for the two-hop relay protocols are reported, and the performance of the two-hop routing and of the epidemic routing protocols are compared.
---
paper_title: Mobility increases the capacity of ad-hoc wireless networks

paper_content:

The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.
---
paper_title: The capacity of wireless networks

paper_content:

When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput /spl lambda/(n) obtainable by each node for a randomly chosen destination is /spl Theta/(W//spl radic/(nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is /spl Theta/(W/spl radic/An) bit-meters per second. Thus even under optimal circumstances, the throughput is only /spl Theta/(W//spl radic/n) bits per second for each node for a destination nonvanishingly far away. Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions. Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity. Splitting the channel into several subchannels does not change any of the results. Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance.
---
paper_title: Properties of random direction models

paper_content:

A number of mobility models have been proposed for the purpose of either analyzing or simulating the movement of users in a mobile wireless network. Two of the more popular are the random waypoint and the random direction models. The random waypoint model is physically appealing but difficult to understand. Although the random direction model is less appealing physically, it is much easier to understand. User speeds are easily calculated, unlike for the waypoint model, and, as we observe, user positions and directions are uniformly distributed. The contribution of this paper is to establish this last property for a rich class of random direction models that allow future movements to depend on past movements. To this end, we consider finite oneand two-dimensional spaces. We consider two variations, the random direction model with wrap around and with reflection. We establish a simple relationship between these two models and, for both, show that positions and directions are uniformly distributed for a class of Markov movement models regardless of initial position. In addition, we establish a sample path property for both models, namely that any piecewise linear movement applied to a user preserves the uniform distribution of position and direction provided that users were initially uniformly throughout the space with equal likelihood of being pointed in any direction.
---
paper_title: An epidemic model for information diffusion in MANETs

paper_content:

Choosing appropriate information dissemination strategies is crucial in mobile ad hoc networks (MANET) due to the frequent topology changes. Flooding-based approaches like diffusion have a strong similarity with epidemic spreading of diseases. Applying epidemiological models to information diffusion allows the evaluation of such strategies depending on the MANET characteristics, e.g. the node density. In order to choose appropriate strategies at run time, the model should be easily evaluated.In this paper, an epidemic model is developed for a simple information diffusion algorithm based on simulation results. We analytically investigate the impact of node density on information diffusion. The analytical model allows the evaluation at runtime, even on devices with restricted resources, and thus enables mobile nodes to dynamically adapt their diffusion strategies depending on the local node density.
---
paper_title: Unit Disk Graph Recognition is NP-Hard

paper_content:

Unit disk graphs are the intersection graphs of unit diameter closed disks in the plane. This paper reduces SATISFIABILITY to the problem of recognizing unit disk graphs. Equivalently, it shows that determining if a graph has sphericity 2 or less, even if the graph is planar or is known to have sphericity at most 3, is NP-hard. We show how this reduction can be extended to 3 dimensions, thereby showing that unit sphere graph recognition, or determining if a graph has sphericity 3 or less, is also NP-hard. We conjecture that K-sphericity is NP-hard for all fixed K greater than 1.
---
paper_title: Delay and resource analysis in MANETs in presence of throwboxes

paper_content:

This paper addresses the delay analysis and resource consumption in mobile ad hoc networks (MANETs) equipped with throwboxes. Throwboxes are stationary, wireless devices that act as relays, and that are deployed to increase the connectivity between mobile nodes. Our objective is to quantify the impact of adding throwboxes on the performance of two routing protocols, namely the Multicopy Two-hop Routing protocol and the Epidemic Routing protocol, in the cases where the throwboxes are fully disconnected or mesh connected. To this end, we use a Markovian model where the successive meeting times between any pair of mobile nodes (resp. any mobile node and any throwbox) are represented by a Poisson process with intensity @l (resp. @m). We derive closed-form expressions for the distribution of the delivery delay of a packet and for the distribution of the total number of copies of a packet that are generated, the latter metric reflecting the overhead induced by the routing protocol. These results are then compared to simulation results. Through a mean-field approach we also provide asymptotic results when the number of nodes (mobile nodes and/or throwboxes) is large.
---
paper_title: Delay and Capacity Trade-Offs in Mobile Ad Hoc Networks: A Global Perspective

paper_content:

Since the original work of Grossglauser and Tse, which showed that mobility can increase the capacity of an ad hoc network, there has been a lot of interest in characterizing the delay-capacity relationship in ad hoc networks. Various mobility models have been studied in the literature, and the delay-capacity relationships under those models have been characterized. The results indicate that there are trade-offs between the delay and capacity, and that the nature of these trade-offs is strongly influenced by the choice of the mobility model. Some questions that arise are: (i) How representative are these mobility models studied in the literature? (ii) Can the delay-capacity relationship be significantly different under some other "reasonable" mobility model? (iii) What sort of delay-capacity trade-off are we likely to see in a real world scenario? In this paper, we take the first step toward answering some of these questions. In particular, we analyze, among others, the mobility models studied in recent related works, under a unified framework. We relate the nature of delay-capacity trade-off to the nature of node motion, thereby providing a better understanding of the delay-capacity relationship in ad hoc networks in comparison to earlier works.
---
paper_title: Optimal delay-power tradeoff in sparse delay tolerant networks: a preliminary study

paper_content:

In this paper we present a first attempt to study analytically the tradeoff between delivery delay and resource consumption for epidemic routing in Delay Tolerant Networks. We assume that the nodes cooperate in order to minimize a common cost equal to a weighted sum of the packet delivery delay and the total number of copies, which is strongly related to the power consumption. In this framework we determine the best policy each node should deploy in a very simple scenario where all the nodes have perfect knowledge of the system status. The result is used as an ideal reference to evaluate the performance of some heuristics proposed, investigating potential performance improvements and configuration criteria.
---
paper_title: Geometry based heuristics for unit disk graphs

paper_content:

Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and to intersection graphs of higher dimensional regular objects.
---
paper_title: Sharp thresholds For monotone properties in random geometric graphs

paper_content:

Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in [0,1]d. We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.
---
paper_title: Spray and wait: an efficient routing scheme for intermittently connected mobile networks

paper_content:

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.
---
paper_title: Impact of mobility on the performance of relaying in ad hoc networks - Extended version

paper_content:

We consider a mobile ad hoc network consisting of three types of nodes: source, destination, and relay nodes. All the nodes are moving over a bounded region with possibly different mobility patterns. We introduce and study the notion of relay throughput, i.e. the maximum rate at which a node can relay data from the source to the destination. Our findings include the results that (a) the relay throughput depends on the node mobility pattern only via its (stationary) node position distribution, and (b) that a node mobility pattern that results in a uniform steady-state distribution for all nodes achieves the lowest relay throughput. Random waypoint and random direction mobility models in both one and in two dimensions are studied and approximate simple expressions for the relay throughput are provided. Finally, the behavior of the relay buffer occupancy is examined for the random walk and random direction mobility models. For both models, the explicit form of the mean buffer is provided in the heavy-traffic case.
---
paper_title: Throughput-delay trade-off in wireless networks

paper_content:

Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in a wireless network when the nodes are fixed, and showed that the throughput per source-destination pair is /spl otimes/(1//spl radic/nlogn). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant or /spl otimes/(1) throughput scaling per source-destination pair. The focus of this paper is on characterizing the delay and determining the throughput-delay trade-off in such fixed and mobile ad hoc networks. For the Gupta-Kumar fixed network model, we show that the optimal throughput-delay trade-off is given by D(n) = /spl otimes/(nT(n)), where T(n) and D(n) are the throughput and delay respectively. For the Grossglauser-Tse mobile network model, we show that the delay scales as /spl otimes/(n/sup 1/2//v(n)), where v(n) is the velocity of the mobile nodes. We then describe a scheme that achieves the optimal order of delay for any given throughput. The scheme varies (i) the number of hops, (ii) the transmission range and (iii) the degree of node mobility to achieve the optimal throughput-delay trade-off. The scheme produces a range of models that capture the Gupta-Kumar model at one extreme and the Grossglauser-Tse model at the other. In the course of our work, we recover previous results of Gupta and Kumar, and Grossglauser and Tse using simpler techniques, which might be of a separate interest.
---
paper_title: Resource and performance tradeoffs in delay-tolerant wireless networks

paper_content:

Wireless and mobile network technologies often impose severe limitations on the availability of resources, resulting in poor and often unsatisfactory performance of the commonly used wireless networking protocols. For instance, power and memory/storage constraints of miniaturized network nodes reduce the throughput capacity and increase the network latency. Through various approaches and technological advances, researchers attempt to somehow compensate for such hardware limitations. However, this is not always necessary. Sometimes, the required performance of such networks does not need to adhere to the level of services that would be required for performance-critical applications. For example, for some applications of sensor networks, minimal latency is not a critical factor and it could be traded off for a more limited resource, such as energy or throughput. Such networks are termed delay-tolerant networks. Thus, to reduce the energy expenditure, transmission range of such sensor nodes would be quite short, leading to network topologies in which the average number of neighbors of the network nodes is very small. If the sensor nodes are mobile, then most of the time a node has no neighbors; only infrequently another node migrates into its neighborhood. This means that the classical networking approach of store-and-forward would not work well, as there is nearly never an intact path between a source and a destination. Several routing protocols have been proposed for this type of networking environment, one example is the Shared Wireless Infostation Model (SWIM), where a packet propagates through the network by being copied (rather than forwarded) from a node to a node, as links are sporadically created. The goal is that one of the copies of the packet reaches the destination. SWIM is an example of the way that non-critical performance could be traded off for insufficient resources, such as the tradeoffs between energy, delay, storage, capacity, and processing complexity. In this paper, we examine some of these tradeoffs, exposing the ways in which resources could be saved by compromising on the level of performance, as to satisfy the particular limitations of network technologies.
---

<format>
Title: A Survey of Message Diffusion Protocols in Mobile Ad Hoc Networks

Section 1: INTRODUCTION
Description 1: Provide a background on Mobile Ad hoc Networks (MANETs), outline the challenges of message diffusion in such networks, and set the context for the survey.

Section 2: BROADCAST AND DISSEMINATION PROTOCOLS
Description 2: Discuss broadcast diffusion techniques, categorizing them by the type of information used, strategy, and media access. Provide an overview of key protocols within each category.

Section 3: ROUTING APPROACHES FOR INTERMITTENTLY CONNECTED NETWORKS
Description 3: Survey routing approaches for networks with intermittent connectivity, such as Delay Tolerant Networks (DTNs). Classify the approaches based on the degree of knowledge nodes have about their future contact opportunities, including scheduled-contact, controlled-contact, predicted-contact, and opportunistic-contact based routing.

Section 4: MODELLING APPROACHES
Description 4: Detail various modeling techniques for evaluating the performance, robustness, and resource consumption of message diffusion protocols in MANETs. Discuss key performance metrics and trade-offs.

Section 5: CONCLUSION
Description 5: Summarize the key findings of the survey, highlight the distinctions between different diffusion techniques, and outline promising research directions.

Section 6: ACKNOWLEDGMENTS
Description 6: Acknowledge contributions and support from individuals, institutions, and funding sources for the research.
</format>
