We study the information propagation speed in multi-lane vehicle-to-vehicle networks such as roads or highways. We focus on the impact of time-varying radio ranges and of multiple lanes of vehicles, varying in speed and in density. We assess the existence of a vehicle density threshold under which information propagates on average at the fastest vehicle speed and above which information propagates dramatically faster. We first prove that no such phase transition occurs if there is only one lane, regardless of the density of vehicles, when one takes into account real-time radio communication range variations at the MAC layer. We then prove that, on the other hand, a phase transition exists as soon as there are multiple lanes with different vehicle speeds and appropriate densities. We characterize conditions under which the phase transition occurs and we derive bounds on the corresponding threshold as a simple relationship between the vehicle density on the fastest lane and the sum of densities on the other lanes. Our results intrinsically encompass a wide range of vehicular network scenarios, including one-way and two-way roads, as well as special cases such as road side units and/or parked cars being used as relays. We confirm our analytical results using simulations.

This paper presents a stochastic geometry model for the investigation of fundamental information theoretic limitations in wireless networks. We derive a new unified multi-parameter cut-set bound on the capacity of networks of arbitrary Poisson node density, size, power and bandwidth, under fast fading in a rich scattering environment. In other words, we upper-bound the optimal performance in terms of total communication rate, under any scheme, that can be achieved between a subset of network nodes (defined by the cut) with all the remaining nodes. Additionally, we identify four different operating regimes, depending on the magnitude of the long-range and short-range signal to noise ratios. Thus, we confirm previously known scaling laws (e.g., in bandwidth and/or power limited wireless networks), and we extend them with specific bounds. Finally, we use our results to provide specific numerical examples.

In this paper, we provide a full analysis of the information propagation speed in bidirectional vehicular delay tolerant networks such as roads or highways. The provided analysis shows that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increases quasi-exponentially when the vehicle density increases. We provide the exact expressions of the threshold and of the average information propagation speed near the threshold, in case of finite or infinite radio propagation speed. Furthermore, we investigate in detail the way information propagates under the threshold, and we prove that delay tolerant routing using cars moving on both directions provides a gain in propagation distance, which is bounded by a sublinear power law with respect to the elapsed time, in the referential of the moving cars. Combining these results, we thus obtain a complete picture of the way information propagates in vehicular networks on roads and highways, which may help designing and evaluating appropriate vehicular ad hoc networks routing protocols. We confirm our analytical results using simulations carried out in several environments (The One and Maple).

In this paper, we provide an analysis of the information propagation speed in bidirectional vehicular delay tolerant networks on highways. We show that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increase exponentially when vehicle density increases. We provide the exact expressions of the threshold and of the average propagation speed near the threshold. We show that under the threshold, the information propagates on a distance which is bounded by a sub-linear power law with respect to the elapsed time, in the referential of the moving cars. On the other hand, we show that information propagation speed grows quasi-exponentially with respect to vehicle densities in each direction of the highway, when the densities become large, above the threshold. We confirm our analytical results using simulations carried out in several environments.

We investigate the fundamental capacity limits of space-time journeys of information in mobile and Delay Tolerant Networks (DTNs), where information is either transmitted or carried by mobile nodes, using store-carry-forward routing. We define the capacity of a journey (i.e., a path in space and time, from a source to a destination) as the maximum amount of data that can be transferred from the source to the destination in the given journey. Combining a stochastic model (conveying all possible journeys) and an analysis of the durations of the nodes' encounters, we study the properties of journeys that maximize the space-time information propagation capacity, in bit-meters per second. More specifically, we provide theoretical lower and upper bounds on the information propagation speed, as a function of the journey capacity. In the particular case of random way-point-like models (i.e., when nodes move for a distance of the order of the network domain size before changing direction), we show that, for relatively large journey capacities, the information propagation speed is of the same order as the mobile node speed. This implies that, surprisingly, in sparse but large-scale mobile DTNs, the space-time information propagation capacity in bit-meters per second remains proportional to the mobile node speed and to the size of the transported data bundles, when the bundles are relatively large. We also verify that all our analytical bounds are accurate in several simulation scenarios.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and Delay Tolerant Networks (DTNs), where end-to-end multihop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility models to obtain specific analytical estimates. In particular, in 2-D networks, when nodes move at a maximum speed$v$and their density$\nu $is small (the network is sparse and asymptotically almost surely disconnected), we prove that the information propagation speed is upper bounded by$(1+O(\nu ^{2}))v$in random waypoint-like models, while it is upper bounded by$O(\sqrt {\nu v} v)$for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios. Finally, we generalize our results to 1-D and 3-D networks.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and delay tolerant networks (DTNs), where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility and graph models to obtain specific analytical estimates. In particular, when nodes move at speed v and their density v is small (the network is sparse and surely disconnected), we prove that the information propagation speed is upper bounded by (1 + O(v2))v in the random way-point model, while it is upper bounded by O(radic(vv)v) for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios.

We analyze the performance of epidemic routing in large-scale intermittently connected networks, under a random geometric graph model and for different mobility parameters (such as the random-waypoint, random walk and Brownian motion models). We derive a generic scaling law on the delay, which provides us with lower bounds: the average delay from a source to a destination and the average broadcast delay are both ¿ ((RN¿n)/vn), where n is the number of nodes in the network, vnthe maximum node speed, and Rnthe radio range.

Classical routing strategies for mobile ad hoc networks operate in a hop by hop "push mode" basis: packets are forwarded on pre-determined relay nodes, according to previously and independently established link performance metrics (e.g., using hellos or route discovery messages). Conversely, recent research has highlighted the interest in developing opportunistic routing schemes, operating in "pull mode": the next relay can be selected dynamically for each packet and each hop, on the basis of the actual network performance. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and the simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility and of random fading. Finally, we present numerical simulations that confirm the accuracy of our bounds.

Delay/disruption tolerant networks (DTNs) or intermittently connected mobile networks (ICNs) are mobile ad hoc networks where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. While most of the research is dedicated to the design of routing protocols, very few properties of such networks are known. In a recent paper [6], the authors provided analytical upper bounds for the information propagation speed in DTNs when they are modeled as two-dimensional Unit Disk Graphs. In this paper, we extend this study to other models by using analytical tools to derive theoretical upper-bounds of the information propagation speed. Firstly, we will present results for DTNs mapped in a space of dimension D, where D varies from 1 to 3. Secondly, we will depart from the Unit Disk Graph model to consider a more realistic model where a node captures a packet sent at distance r with probability p(r).

Classical routing strategies for mobile ad hoc networks forward packets on a pre-defined route (typically obtained by a shortest path routing protocol). Research has high-lighted the interest in developing opportunistic routing schemes, where the next relay is selected dynamically for each packet and each hop. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility. Finally, we present numerical simulations that confirm the accuracy of our bounds.

The network planning problem of placing replicated servers with QoS constraints is considered. Each server site may consist of multiple server types with varying capacities and each site can be placed in any location among those belonging to a given set. Each client can be served by more than one location as long as the round-trip delay of data requests satisfies predetermined upper bounds. Our main focus is to minimize the cost of using the servers and utilizing the link bandwidth, while serving requests according to their delay constraint. This is an NP-hard problem. A pseudopolynomial and a polynomial algorithm that provide guaranteed approximation factors with respect to the optimal for the problem at hand are presented