Delay-Tolerant Networks (DTNs) have emerged as an exciting research area with a number of useful applications. Most of these applications would benefit greatly by a reduction in the message delivery delay experienced in the network. The delay performance of DTNs is adversely affected by contention, especially severe in the presence of higher traffic rates and node densities. Many-to-Many (M2M) communication can handle this contention much better than traditional one-to- one communication employing CSMA. In this paper, for the first time, we analytically model the expected delivery delay of a DTN employing epidemic routing and M2M communication. The accuracy of our model is demonstrated by matching the analytical results against those from simulations. We also show using simulations that M2M communication significantly improves the delay performance (with respect to one-to-one CSMA) for high contention scenarios. We believe our work will enable the effective application of M2M communication to reduce delivery delays in DTNs.
This paper considers (p, q )-Epidemic Routing, a class of store-carry-forward routing schemes, for sparsely populated mobile ad hoc networks. Our forwarding scheme includes Two-Hop Forwarding and the conventional Epidemic Routing as special cases. In such forwarding schemes, the original packet is copied many times and its packet copies spread over the network. Therefore those packet copies should be deleted after a packet reaches the destination. We analyze the performance of (p, q)-Epidemic Routing with VACCINE recovery scheme. Unlike most of the existing studies, we discuss the performance of (p, q)-Epidemic Routing in depth, taking account of the recovery process that deletes unnecessary packets from the network. 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. Epidemic routing has been proposed as a robust transmission scheme for sparse mobile ad hoc networks. Under the assumption of no contention, epidemic routing has the minimum end-to-end delay amongst all the routing schemes proposed for such networks. The assumption of no contention was justified by arguing that since the network is sparse, there will be very few simultaneous transmissions. Some recent papers have shown through simulations that this argument is not correct and that contention cannot be ignored while analyzing the performance of routing schemes, even in sparse networks.Incorporating contention in the analysis has always been a hard problem and hence its effect has been studied mostly through simulations only. In this paper, we find analytical expressions for the delay performance of epidemic routing with contention. We include all the three main manifestations of contention, namely (i) the finite bandwidth of the link which limits the number of packets two nodes can exchange, (ii) the scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and (iii) the interference from transmissions outside the scheduling area. The accuracy of the analysis is verified via simulations. 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. A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. But the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior. Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from the source to the destination. There are many real networks that follow this model, for example, wildlife tracking sensor networks, military networks, vehicular ad hoc networks, etc. In this context, conventional routing schemes fail, because they try to establish complete end-to-end paths, before any data is sent. 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 reduce the overhead of flooding-based schemes have often been plagued by large delays. With this in mind, we introduce a new family routing schemes that "spray" a few message copies into the network, and then route each copy independently towards the destination. We show that, if carefully designed, spray routing not only performs significantly fewer transmissions per message, but also has lower average delivery delays than existing schemes; furthermore, it is highly scalable and retains good performance under a large range of scenarios. Finally, we use our theoretical framework proposed in our 2004 paper to analyze the performance of spray routing. We also use this theory to show how to choose the number of copies to be sprayed and how to optimally distribute these copies to relays.