SLAW (Self-similar Least Action Walk)

We report that bursty hot spot sizes are a key factor in causing the heavy-tail distribution of flights in human walks. The data analysis based on GPS traces of human walks reveals that the sizes of a few extremely large hot spots are dominating the mean size of hot spots and they cause the bursty (i.e., long-range dependent) dispersion of visit points where people make a stop. On top of bursty visit points, humans perform a distance-optimizing algorithm to plan their trips much like a heuristic to the traveling salesman problem. These factors in combination make human walks to have a heavy-tailed flight distribution. The above findings enable the construction of a simple human mobility model that taking as input the degree of burstiness in visit point dispersion, can naturally emulate hot spots as well as a heavy-tail flight distribution, both known to be important in measuring the realistic performance of mobile networks.

Positioning

As we have developed TLW mobility model but the main weakness of this model is that mobile nodes in it behave randomly. But in this work, through empirical data analysis we demonstrate that people hardly move randomly and the visit points where people make a stop show self-similarity. Based on these observations we make a context based Levy Walk model, which we call SLAW (Self-similar Least Action Walk) .

Self-similar visit points (Hot spots)

We define a visit point to be the GPS location where a participant stays more than 30 seconds within a circle of 5 meter radius of that location. For each site, we plot the visit points registered by every walk trace of that site. We call these points aggregated visit points. The figures below plots the aggregated visit points of KAIST while we zoom in to smaller areas (denoted by small boxes) in the map. The visit points are in clusters with different sizes. A cluster in a big scale is divided into a few clusters in smaller scales, which is a visual evidence of self-similarity (scale freedom).

• Visual evidence

Figure. Area with a side of 4800/1200/300 m

• Hurst parameter

Hurst parameter is one of the quantitative criteria to decide the self-similarity of sample data set. The data set are said to be bursty or long range dependent (and therefore, self-similar) if the Hurst parameter is in between 0.5 and 1. The figure below shows the Hurst parameter values in each site and. All the values in both 1-D and 2-D are higher than 0.5.

Self-similar visit points (Individual trace)

We also observe that the visit points registered in each individual trace are bursty. For each trace, we perform the aggregated variance test on its visit points. The following figure shows the Hurst parameter values of individual traces from the KAIST site. Their H values are slightly less than those from the aggregated visit points shown above, confirming that burstiness gets intensified as individually bursty traces are superimposed together.

For the Hurst parameter values of visit points of individuals from other sites, please refer to our technical report [Lee 08].

Aggregated/Normalized Variance

To measure the burstiness in the dispersion of visit points, we divide the site map into a grid of unit squares (initially of 5 by 5 meters). We count all the visit points within each square and then normalize the count by the area of the square. We measure the variance in these normalized count samples and call it aggregated variance. If there exists a long-range dependency in the samples, the aggregated variance should not decay faster than -1 in a log-log scale as we increase the size of the square. The figure below illustrates the method. We divide the area by non-overlapping d by d squares, and count the number of visit points registered in each square and then normalize the sampled count by the size of the unit square. We compute the normalized variance as we increase d.

The normalized variance is defined to be Var(X/E[X] ) where X is the number of visit points assigned to a segment. It can be proven that normalized variance is equivalent to aggregated variance.

Least Action Trip Planning

Given a set of visit points, how do humans plan their trips around these visit points to form a heavy-tail distribution of flights? Maupertuis' principle of least action [Maupertuis 44] provides some clues to this phenomenon: humans tend to make actions that require the least amount of effort. Based on the observation, we devise a path selection algorithm as follows.

With a set to 1.5 or 3, the difference in the sums of flights from the simulation and the real traces is always between 1% to 11%, and the CCDFs of flights also match extremely well. For the detailed results, refer to our technical report [Lee 08].

Bursty Spot Generation Model

Our data analysis indicates that bursty visit points and distance-based trip planning over those visit points are the keys in generating a heavy-tail flight distribution observed in human walk traces. This observation greatly simplifies the construction of a human walk model that can emulate both hot spot and flight statistics found in real traces. The figure below describes the scheme for generating SLAW traces.

The figure below shows the sample synthetic visit points (right) that has the same normalized variance as the original visit points (left) in the NCSU site. For the detailed procedure of making synthetic maps and sample synthetic maps for other sites, please refer to our technical report [Lee 08].

Routing Performance

We run the four DTN routing algorithms in the NCSU site. Several significant observations can be made about the difference in the routing performance when different routing protocols and mobility models are used. (1) Overall, the average routing performance of various protocols under SLAW is much shorter than RWP and TLW and among SLAW, larger a values give longer routing delays. Our measurement study indicates that human walks have a within a range of [1:3]. So SLAW(0) tends to overestimate the routing delays compared to SLAW(3). For detailed results, please refer to our technical report [Lee 08].

Reference

[Lee 08] Kyunghan Lee, Seongik Hong, Seong Joon Kim, Injong Rhee and Song Chong, Demystifying Levy Walk Patterns in Human Walks, Technical Report, 2008, PDF
[Maupertuis 44] P. L. M. de Maupertuis. ccord de differentes lois de la nature qui avaient jusqu'ici paru incompatibles. Mem. As. Sc., page 417, 1744.

Download

Not yet publicly available.

Members

Faculty

• Injong Rhee (NCSU)

Postdoctoral Fellows

• Seong Joon Kim (NCSU)
• Minsu Shin (Currently at Hanaro Telecom, Korea)

Ph.D Students

• Seongik Hong (NCSU)

Cooperating Members

Faculty

• Song Chong (KAIST)

Ph.D Students

• Kyunghan Lee (KAIST)

Publications

Papers

• Kyunghan Lee, Seongik Hong, Seong Joon Kim, Injong Rhee and Song Chong, SLAW: A Mobility Model for Human Walks, INFOCOM, Rio de Janeiro, Brazil, 2009, PDF

Technical Reports

• Kyunghan Lee, Seongik Hong, Seong Joon Kim, Injong Rhee and Song Chong, Demystifying Levy Walk Patterns in Human Walks, Technical Report, 2008, PDF