In this paper we study mobile ad hoc wireless networks using the notion of evolving connectivity graphs. In such systems, the connectivity changes over time due to the intermittent contacts of mobile terminals. In particular, we are interested in studying the expected flooding time when full connectivity cannot be ensured at each point in time. Even in this case, due to finite contact times durations, connected components may appear in the connectivity graph. Hence, this represents the intermediate case between extreme cases of fully mobile ad hoc networks and fully static ad hoc networks. By using a generalization of edge-Markovian graphs, we extend the existing models based on sparse scenarios to this intermediate case and calculate the expected flooding time. We also propose bounds that have reduced computational complexity. Finally, numerical results validate our models.
@cite_6: We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p. Such evolving graph model is a wide generalization of time-independent dynamic random graphs [6] and will be called edge-Markovian dynamic graphs. We investigate the speed of information dissemination in such dynamic graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide: i) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial probability distribution. ii) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time does not asymptotically depend on the edge death-rate q.
Novel contributions: Customary models used in ad hoc networks consider either a fixed topology, i.e., the case of a static ad hoc network, or a fully disconnected network, i.e., the DTN case. The analysis proposed in this paper is able to explore the intermediate case when connectivity is still intermittent as assumed in DTNs, but, whenever a connected component is present, messages can span several hops with very small delay. Moreover, if compared to the analysis in @cite_6 , the continuous time model we employ has the key advantage that the closed forms and bounds proposed in this paper can be specialized to span different conditions of the sub-critical regime, depending on the ratio between the contact time duration and the intermeeting times.