Skip to main content
Prof Do Young Eun

Super-diffusive Behavior of Mobile Nodes

Motivating Example

Mobility is the most important component in mobile ad-hoc networks (MANETs) and delay-tolerant networks (DTNs). To observe key characteristics in mobile traces and use sound mobility models that can capture these properties are critical for network performance evaluations. We observe the super-diffusive behavior in all mobile traces, and suggest to use a mobility model that can capture this characteristic properly.   

The following figures show sample trajectories of real mobility trace and from some synthetic models. These provide us a strong motivation that mobile nodes follow super-diffusive movement patterns.

As shown above, there exists “statistical similarity” between the real trace and a synthetically generated trajectory from a super-diffusive model (e.g., Levy Walk). The power-law step-length distribution used in Figure (c) generates occasional very-long jumps followed by many small steps with random orientations.

Super-diffusive behavior

  • Mean Square Displacement (MSD):  One way to characterize the movement of a mobile node is to measure how far it is away from its current position after time t. This ‘diffusive’ behavior or the rate at which the mobile node spreads out can be described by the mean square displacement (MSD). If we define  to be the position of the mobile node at time t, then the MSD becomes ,i.e., the second moment of the displacement  between the current position at time t and the position at 0. MSD is a useful metric that can capture diffusive patterns in mobile nodes.
  • Super-diffusive pattern: For a class of isotropic random walks with finite step-length variance, the MSD will grow linearly with t, i.e., . On the other hand, when the step-length variance is infinite such as Levy walks, the mobile node tends to spread out faster than  since much longer step-lengths appear more often. In this case, , where , in general and this behavior is called ‘super-diffusion’.  

The figure on the right shows the MSD of human mobile node on a log-log scale. For different human movement methods, MSD increases faster than linear () in all cases, which implies super-diffusive behavior.

NCSU (North Carolina State University) GPS trace

The NCSU GPS traces were collected at NCSU campus. One student carried a GPS device (Garmin eTrex Legend Cx) to collect the GPS traces. This device can record the x, y co-ordinates of a mobile user’s position, angle and velocity every second, where the resolution for the location is less than 3-5 meters with 95% accuracy. It however cannot record the trajectory when the mobile user is inside a building or under a tunnel where GPS signal is weak. 

  • Trace Format
        <index><date><time><am/pm><altitude><speed><angle><x, y co-ordinates>

NCSU GPS traces are now available !   Click here to download GPS Traces

Effect of diffusive property on network performance

The figure on your right shows the effect of different diffusive behaviors of mobile nodes on network performance under the epidemic routing protocol. For underlying mobility models, a class of Levy walk models with different m for the step-length distribution are chosen to reflect different diffusive behaviors. For a class of Levy walk models, step-length density is characterized by

where  is required for any valid probability density function.

As shown in the figure, varying degrees of diffusive behavior (parameterized by m) result in widely different network performance. We see that faster diffusive behavior of mobile nodes (smaller m) gives higher delivery ratio under the same transmission range. This result implies that diffusive behavior of mobile nodes, if not properly captured, may result in misleading conclusion in performance study of network protocols.

Publications