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 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.
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.
<index><date><time><am/pm><altitude><speed><angle><x, y co-ordinates>
NCSU GPS traces are now available ! Click here to download GPS Traces
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 differentm 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 bym) 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.
Sungwon Kim, Chul-Ho Lee, and Do Young Eun, "Super-Diffusive Behavior of Mobile Nodes and its Impact on Routing Protocol Performance", IEEE Transactions on Mobile Computing, to appear
Sungwon Kim and Do Young Eun, "Impact of Super-Diffusive Behavior on Routing Performance in Delay Tolerant Networks," in IEEE International Conference on Communications (ICC), Beijing, China, May 2008
Sungwon Kim, Chul-Ho Lee, and Do Young Eun, "Super-diffusive Behavior of Mobile Nodes from GPS Traces", ACM Mobicom07, Student Poster, Montreal, Canada, Sept. 2007
Back to Top