SLAW (Self-similar Least Action Walk)

Lately various measurement studies of human walk traces have discovered several significant statistical patterns of human mobility. Namely these include truncated power-law distributions of flights, pause-times and inter-contact times, fractal way-points, and heterogeneously defined areas of individual mobility. We present a new mobility model called SLAW (Self-similar Least Action Walk) that can produce synthetic walk traces containing all these features. 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 waypoints where people make a stop. On top of bursty waypoints, 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 waypoint 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.

Key words Human movement Pattern, Human Mobility model, Self-similarity, Power law, Levy Walk, Delay Tolerant Network, DTN routing algorithm, Inter contact time, Inter meeting time, routing performance, Expected Contact Time (ECT)

Positioning/Characteristics

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 waypoints 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 waypoints (Hot spots)

We define a waypoint 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 waypoints registered by every walk trace of that site. We call these points aggregated waypoints. The figures below plots the aggregated waypoints of KAIST while we zoom in to smaller areas (denoted by small boxes) in the map. The waypoints 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 waypoints (Individual trace)

We also observe that the waypoints registered in each individual trace are bursty. For each trace, we perform the aggregated variance test on its waypoints. 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 waypoints shown above, confirming that burstiness gets intensified as individually bursty traces are superimposed together.

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

Aggregated/Normalized Variance

To measure the burstiness in the dispersion of waypoints, we divide the site map into a grid of unit squares (initially of 5 by 5 meters). We count all the waypoints 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 waypoints 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 waypoints assigned to a segment. It can be proven that normalized variance is equivalent to aggregated variance.

Least Action Trip Planning

Given a set of waypoints, how do humans plan their trips around these waypoints 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].

Waypoint Map Generation

Our data analysis indicates that bursty waypoints and distance-based trip planning over those waypoints 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 waypoints (right) that has the same normalized variance as the original waypoints (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].

Publications

Conferences & Workshops

• 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

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.