When nodes in a mobile network cluster together or move according to common external factors (e.g., cars that follow the road network), the resulting contact patterns become correlated. In this work we address the question of modelling such correlated mobility movements for the analysis of intermittently connected networks. We propose to use the concept of node colouring time to characterise dynamic node contact patterns. We analyse how this model compares to existing work, and demonstrate how to extract the relevant data from actual trace files. Moreover, we show how this information can be used to derive the latency distribution of DTN routing protocols. Our model achieves a very good fit to simulated results based on real vehicular mobility traces, whereas models which assumes independent contacts do not.
There is a rich body of work discussing detailed analytic models for latency and delivery ratio in delay-tolerant networks. The work ranges from experimentally grounded papers aiming to find models and frameworks that fit to observed data to more abstract models dealing with asymptotic bounds on information propagation. Many of these approaches are based on or inspired by epidemiological models @cite_25 . We have previously characterised the worst-case latency of broadcast for such networks using expander graph techniques @cite_15 . In a preliminary version of this paper we developed the basic framework for deriving the latency of ideal epidemic routing @cite_11 . This paper extends the latter work by incorporating an analysis of multi-copy routing as well as presenting a more rigrorous matematical basis with a hierarchy of connectivity models.
@cite_15 @cite_25 @cite_11
2151343869 1489677252
Worst-case latency is an important characteristic of information dissemination protocols. However, in sparse mobile ad hoc networks where end-to-end connectivity cannot be achieved and store-carry-forward algorithms are needed, such worst-case analyses have not been possible to perform on real mobility traces due to lack of suitable models. We propose a new metric called delay expansion that reflects connectivity and reachability properties of intermittently connected networks. Using the delay expansion, we show how bounds on worst-case latency can be derived for a general class of broadcast protocols and a wide range of real mobility patterns. The paper includes theoretical results that show how worst-case latency can be related with delay expansion for a given mobility scenario, as well as simulations to validate the theoretical model. Given a mobility pattern that entails intermittent wireless ad hoc connectivity, what is the best message delivery ratio and latency that can be achieved for a delay-tolerant routing protocol? We address this question by introducing a general scheme for deriving the routing latency distribution for a given mobility trace. Prior work on determining latency distributions has focused on models where the node mobility is characterised by independent contacts between nodes. We demonstrate through simulations with synthetic and real data traces that such models fail to predict the routing latency for cases with heterogeneous and correlated mobility. We demonstrate that our approach, which is based on characterising mobility through a colouring process, achieves a very good fit to simulated results also for such complex mobility patterns.