PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Propagation Speed in Mobile and Delay Tolerant Networks

Philippe Jacquet, Bernard Mans, Georgios Rodolakis

arXiv:0903.1157v1cs.ITcs.NI

TL;DR

The paper addresses how quickly information can propagate in mobile and Delay Tolerant Networks when end-to-end paths may not exist. It uses analytical space-time journey models to derive routing-independent upper bounds, obtaining mobility- and density-dependent results in sparse two-dimensional networks and extending them to other dimensions. Simulations confirm the bounds in the studied scenarios.

  • Problem

    End-to-end paths may not exist in mobile and Delay Tolerant Networks, leaving the maximum achievable information propagation speed insufficiently characterized.

  • Method

    The paper uses analytical space-time journey models to upper-bound the optimal information propagation performance achievable by any routing algorithm.

  • Results

    In sparse two-dimensional networks, the paper derives mobility- and density-dependent propagation-speed upper bounds, generalizes them to one- and three-dimensional settings, and compares them with simulations.

  • Takeaways & Limitations

    The bounds provide a framework for understanding fundamental DTN performance limits and evaluating or optimizing specific routing scenarios.

Abstract

from arXiv · show

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, in two-dimensional networks, when nodes move at a maximum speed $v$ and their density $ν$ is small (the network is sparse and surely disconnected), we prove that the information propagation speed is upper bounded by ($1+O(ν^2))v$ in the random way-point model, while it is upper bounded by $O(\sqrt{ν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 one-dimensional and three-dimensional networks.

I. INTRODUCTION

The paper studies the maximum speed of information propagation in sparse, intermittently connected mobile networks, where journeys combine transmission and node carriage. It develops analytical upper bounds for finite networks across mobility and dimensionality models, and compares them with simulations.

  • Motivation: Information propagation is studied when end-to-end paths may not exist and communication routes arise through time and mobility.Sparse networks can remain disconnected, causing information to stall until mobility enables transfer between components.
  • Model and objective: The paper models a journey as alternating packet transmissions and node carriages connecting a source to a destination.The objective is to find the shortest such journey in time and use it to characterize propagation speed.
  • Research gap: The main focus is information propagation speed in mobile and intermittently connected networks, extending prior work on static wireless networks and disconnected mobile graphs.The paper specifically addresses precise upper bounds that remain missing for intermittently connected mobile networks.
  • Approach: The analysis integrates network topology through unit disk graphs for mobile nodes in finite square and multidimensional domains.This departs from an Erdős–Rényi model whose connections are independent of the actual network topology.
  • Validation: The theoretical bounds are compared with simulations to verify their accuracy across network and mobility parameters.The paper examines parameters including node density and direction-change rate.
  • Contributions: The paper derives upper bounds on optimal routing performance in finite two-dimensional networks, with propagation speed depending on node density and mobility.The results are generalized to bounded multidimensional networks.

II. MODEL AND OVERVIEW OF MAIN RESULTS IN TWO-DIMENSIONAL NETWORKS

The paper models sparse, intermittently connected two-dimensional mobile networks and derives generic upper bounds on information propagation speed. The bounds are specialized to mobility regimes, yielding finite speed estimates even under idealized instantaneous transmission assumptions.

  • Network model: The model considers n nodes in a square area A = L×L, with n and L tending to infinity while node density remains constant.
  • Mobility models: Nodes follow independent reflected trajectories with uniform speed and Poisson direction changes, spanning random-walk, Brownian, and random-waypoint-like limits.
  • Model assumptions: Instantaneous in-range transmission and no buffering or congestion isolate propagation limits imposed by mobility and topology.
  • Generic bound: The analysis derives a generic upper bound by identifying the smallest distance-over-time ratio for which journey probability becomes zero.
  • Density and scale: Above the analyzed density threshold, the upper bound becomes infinite, whereas below it the propagation speed quickly approaches a constant beyond distances larger than the radio range.
  • Mobility-specific results: In sparse two-dimensional networks, the bound is O(√(νv) v) for random walk and (1 + O(ν^2))v for the random-waypoint-like limit.

A. Methodology and Journey Analysis

The methodology represents beacon delivery as space-time journeys and analyzes their probability through relay sequences and segment decompositions. This supports asymptotic bounds while retaining the store-carry-forward structure of delay-tolerant routing.

  • Journey representation: A journey is a space-time trajectory of a beacon from source to destination, with transmissions and node-carried movements forming its path.
  • Journey representation: The analysis initially fixes the destination, models parallel broadcast journeys, and later notes that destination motion does not affect the results.
  • Journey representation: Journeys are restricted to simple paths that do not revisit a node, without changing arrival time because repeated-node journeys contain equivalent simple journeys.
  • Journey segmentation: Each journey is decomposed into emission and move-and-emit segments, with unitary emission vectors sufficient for fastest-journey analysis.
  • Relay sequences: The journey probability distribution depends only on the number of relay nodes, allowing node identities to be abstracted away.

C. Decomposition into Independent Segments

Successive journey segments are conditionally dependent because node movements influence meeting and emission probabilities. The paper replaces these dependencies with upper-bounding segment probabilities that factor into an independent journey model.

  • Dependence: The dependence arises because emission directions and meeting rates are linked to node movement directions and relative speeds.
  • Segment probabilities: The construction uses emission segments for immediate retransmission and move-and-emit segments for carrying the beacon before transmission.
  • Dependence: Direct journey decomposition into independent segments fails because successive emissions and movements have conditional probabilities.
  • Independent upper-bound model: The analysis upper-bounds conditional segment probabilities so that the resulting journey density factors into independent emission and move-and-emit segments.
  • Independent upper-bound model: For a fixed relay sequence, the upper-bound journey density is represented as a product of the probabilities of its segments.

D. Journey Laplace Transform

The paper applies Laplace transforms to the independent upper-bound journey model and combines fixed-length relay sequences with a Poisson generating function. This produces a transform for all journeys, enabling propagation-speed bounds from vanishing journey probability.

  • Transform construction: The Laplace transform maps each space-time journey segment sequence into an expectation under the upper-bound probability weight.
  • Transform construction: Independence makes the transform of a journey with k segments equal to a product of individual segment transforms, including the final motion segment.
  • All-journey aggregation: Because relay-sequence length is not fixed, a Poisson generating function aggregates transforms across all possible sequence lengths.
  • All-journey aggregation: The number of distinct relay sequences contributes the combinatorial factor n!/(n−k)! for sequences of size k.
  • All-journey aggregation: Combining segment transforms yields the generating function for the upper-bound journey Laplace transform.

E. Information Propagation Speed Analysis

The analysis bounds journey probabilities and derives information-propagation speed limits from their asymptotic behavior. It uses Poisson generating functions, depoissonization, and kernel singularities while accounting for node motion and boundary reflections.

  • The target is an upper bound on the density of journeys from z0 at time 0 to z1 at time t.
  • pn(z0, z1, t) ≤ p(n, z0, z1, t)(1 + o(1)) as n →∞.
  • The kernel K consists of pairs (ρ, θ) satisfying K(ρ, θ) = 0 and determines the asymptotic analysis.
  • qν(z0, z1, t) = O(exp(θ1t −|z|ρ0)) for all θ1 > θ0.This estimate is obtained as L →∞ with z0 and z1 fixed.
  • The propagation-speed upper bound follows from the time threshold where −ρ0|z| + θ0t = 0.
  • The analysis uses the maximum node speed v for upper bounds and finds mirror-image and destination-motion contributions negligible in the large-domain limit.

IV. SPARSE TWO-DIMENSIONAL NETWORKS

For sparse two-dimensional networks, the paper derives mobility-dependent propagation-speed bounds and extends the analytical framework from two dimensions to dimensions one through three. The random-walk bound decreases with density and direction-change rate, whereas the τ = 0 bound approaches node speed at low density.

  • Random walk: The random-walk propagation-speed upper bound is asymptotically O(√(νv) v) when node density is sparse.
  • Billiard limit: The τ = 0 propagation-speed upper bound is (1 + O(ν^2))v as ν →0.
  • Random walk: Information propagation speed decreases with the square root of node density ν and with more frequent direction changes.The square-root term is proportional to the expected number of neighbors met during a random step.
  • Billiard limit: The τ = 0 bound approaches the maximum node speed v rather than tending to zero as density decreases.
  • Multi-dimensional generalization: The generalized theorem assumes constant node density ν in domains of size A = L^D and uses maximum speed v and direction-change rate τ.
  • Scope boundary: Above density 1/V_D, the model’s propagation-speed upper bound is infinite, while a tighter one-dimensional analysis predicts exponential growth with density.

VI. SLOWNESS OF INFORMATION PROPAGATION PLOTS

The plots show theoretical lower bounds on slowness versus node density for τ = 0 and τ = 0.1 in one-, two-, and three-dimensional networks. They confirm the sparse-density asymptotics: τ = 0 approaches maximum node speed, while random-walk slowness becomes unbounded at low density.

  • The plots report theoretical lower bounds of slowness versus mobile node density ν for τ = 0 and τ = 0.1 across dimensions one through three.The numerical results use maximum node speed v = 1 ms−1.
  • In all dimensions, the τ = 0 low-density information-propagation speed approaches the maximum node speed.
  • For τ > 0, propagation slowness is unbounded at small node densities.
  • Model boundary: The model’s slowness lower bound reaches zero at ν = 1/V_D, but the actual slowness should remain non-zero beyond that density.
  • Two-dimensional behavior: In two dimensions, τ = 0 gives slowness 1 − O(ν^2), while random walk gives slowness O(1/√ν) as ν →0.

VII. SIMULATIONS

The simulations evaluate theoretical propagation-speed bounds across two mobility models and several node densities. Measurements converge to fixed slopes, and the theoretical slope remains a lower bound on slowness.

  • Simulation setup: The simulations use a unit-disk graph with 1 m radio range and mobile-node speed 1 m s^-1.They compare billiard random way-point mobility at τ = 0 with random walk mobility at τ = 0.1.
  • Simulation setup: The experiments vary density ν = 0.025, 0.05, and 0.1 using 80 × 80, 60 × 60, and 40 × 40 squares, respectively.
  • Results: Propagation-time measurements quickly converge to a straight line of fixed slope, implying a fixed information propagation speed.The inverse slope of the time-versus-distance plot gives propagation speed in m s^-1.
  • Results: The theoretical slope is clearly a lower bound on slowness, while the heuristic bound provides an accurate slope in the simulations.The theoretical slope is smaller because the proof uses an upper bound on journey probability density to establish rigorously valid bounds.
  • Scope: The paper provides theoretical upper bounds for finite two-dimensional and multidimensional DTNs and uses simulations to show their validity.The bounds are intended to clarify DTN performance limits and support evaluation or optimization of routing algorithms.
  • Future directions: Future work includes tighter bounds, alternative neighboring and mobility models, real-trace comparisons, and comparisons with common routing schemes.

APPENDIX

The appendix develops the analytical machinery for node encounters, motion segments, journey transforms, and multidimensional asymptotic analysis. It also establishes convergence properties needed for the bounds.

  • Encounter analysis: The encounter analysis computes how often one moving node enters another node’s unit-radius neighborhood from their relative motion.The calculation uses the projection of relative velocity onto the neighborhood-radius vector and the density of node presence.
  • Motion decomposition: A carry segment represents constant-speed motion until a direction change, with direction changes occurring at Poisson rate τ.The appendix expresses the carry-segment transform using the node speed and rate τ.
  • Motion decomposition: A node journey is modeled as a sequence of carry segments followed by a final segment ending when the destination receives the packet.The resulting generating-function identity corresponds to summing over arbitrary sequences of motion segments.
  • Asymptotic analysis: The appendix uses Cauchy integration and inverse-transform arguments to bound journey densities and analyze their asymptotic behavior.The multidimensional integration surface is adjusted to obtain absolute convergence under the stated conditions.
  • Multidimensional extension: Analytic properties of the kernel and modified Bessel functions determine the transform’s domain and support the multidimensional extension.
  • Asymptotic analysis: The analysis shows exponential decay with distance and establishes convergence of the relevant integrals for sufficiently large distance, including |z| > 2.

E. Contribution of Mirror Images

The mirror-image construction accounts for finite square-domain boundaries by adding reflected destinations to the journey-density expression. These additional terms do not change the asymptotic propagation-speed upper bound.

  • Mirror-image construction: The finite square domain is handled by adding periodic mirror images of the destination to the journey-density expression.The construction includes the three closest images and then sums over all periodic image positions.
  • Mirror-image construction: The dominant boundary corrections come from the three closest mirror-image sets in addition to the direct journey term.
  • Asymptotic effect: Because journey density decreases exponentially with distance, the nearest mirror-image contributions are exponentially suppressed according to their boundary distance.The additional factor is of order exp(θ1t − |z|ρ0 − x), where x is the node’s distance from the square boundary.
  • Moving destination: Allowing the destination to move adds an excursion transform to the fixed-destination transform.The new pole set is dominated by the original kernel set, so its contribution is exponentially negligible.
  • Moving destination: The moving-destination analysis shows that the asymptotic propagation-speed upper bound does not change as distance and time tend to infinity.
Loading 0903.1157v1…