TLW (Truncated Levy Walk) Mobility Model

We report that human walks performed in outdoor settings of tens of kilometers resemble a truncated form of Levy walks commonly observed in animals such as monkeys, birds and jackals. Our study is based on about one thousand hours of GPS traces involving over 100 volunteers in various outdoor settings including two different university campuses, a metropolitan area, a theme park and a state fair. We show that many statistical features of human walks follow truncated power-law, showing evidence of scale-freedom and do not conform to the central limit theorem. These traits are similar to those of Levy walks. None of commonly used mobility models for mobile networks captures these properties. Based on these findings, we construct a Truncated Levy Walk (TLW) mobility model which is versatile enough in emulating diverse statistical patterns of human walks observed in our traces [Chaintreau 06]. The model is also used to recreate similar inter-contact time distributions which show dichotomy observed in previous human mobility studies [Karagiannis 06]. Our network simulation indicates that the Levy walk features are important in characterizing the performance of mobile network routing performance.

Positioning

Our TLW model is a random equivalent mobility model for human walks. We say it is equivalent model since it can describe some important characteristics of human walks e.g. flight length, pause time and inter-contact time (ICT) even though our model is a type of random models.

Trace data gathering

We gather almost 200 real daily human trace data of 100 volunteers from 5 different sites (2006~2008). The sites include two university campuses (NCSU and KAIST), New York City, Disney World (Florida, US), and North Carolina state fair which is like a small theme park. Garmin GPS 60CSx handheld receivers are used for data collection which are WAAS (Wide Area Augmentation System) capable with a position accuracy of better than three meters 95 percent of the time, in North America. The GPS receivers take reading of their current positions at every 10 seconds and record them into a daily track log. We extract flight length and pause time data from the collected data.

Figure. Sample traces gathered in Disney world

Data analysis method

We use MLE (Maximum Likelihood Estimation) and Akaike test to fit flight length and pause time data. The following figures show the flight length and pause time distributions follow truncated forms of Levy distribution. For detailed information on MLE, Akaike test and the analysis results, please refer to Analysis method.

Figure. Flight lengths and pause times can be best described by truncated Pareto distributions

We consider that a participant has a pause if the distance that he has moved during a 30 second period is less than r meters. A flight is defined to be a longest straight line trip from one location to another that a mobile user makes without a directional change or pause. But it is not straightforward to extract flight information from a trace because people hardly move in a straight line. Combined with GPS errors, this human “errors” make it difficult to analyze flight data. To reduce noise due to these factors, we use three different methods, namely rectangular, angle and pause-based models. For the definitions of each model, refer to our paper, [Rhee 08]. The above figures come from 30-degree angle model.

Characteristics of Human walks

Heavy tailed flight lengths and pause times

The flight length and pause time distributions of human walks follow truncated power law distributions. For the fight length distribution, first we show a visual evidence of Levy walk patterns. The following figures show typical trace patterns generated by Levy walk and sample traces measured in our five sites. Levy walks consist of many short flights and exceptionally long flights that eliminate the effect of such short flights. All the figures below show such characteristics.

Figure. Trace patterns of Levy walk show clustering properties. Small jumps make clusters and the clusters are connected by long jumps. Every trace from five sites show similar clustering properties.

Super-diffusive nature

The mean squared displacement (MSD), which is defined to be the variance of the probability distribution, is proportional to t. It is a manifestation of the central limit theorem (CLT) as the sum of flight lengths follows a Gaussian distribution. However, when flight lengths do not have a characteristic scale - in other words, their second moment is not finite, the mobile users are making Levy walks and may undergo atypical diffusion.

The following figures show the MSD of flight lengths measured from five sites. We can see that up to about 30 minutes, our participants make super-diffusion (γ > 1.2) and after that, they make sub-diffusion (γ < 0.9). Truncated Levy walks are known to have this pattern of MSD [Maruyama 03].

TLW model description

Humans hardly move in random manners but we could extract some Levy walk patterns from our trace data. Using these results, we made a Truncated Levy Walk (TLW) model which has the following characteristics.

• Flight lengths follow a truncated power law

• Pause times follow a truncated power law

• Turning angles follow a uniform distribution
• Velocity increases as flight lengths increase

Inter Contact Time

It is known that the ICT distribution of human walks exhibits a power-law tendency up to some time after which it shows exponential decay [Karagiannis 06]. We confirm the same tendency from the ICT distribution generated from our TLW model exhibiting a good fit to empirical ICT distributions. The following figure shows that the ICT distribution generated by our TLW model can fit the ICT distribution result from the UCSD WiFi? data set [Mcnett 05] really well. For the detailed simulation setups, please refer to our paper, [Rhee 08].

Figure. Truncated Pareto distribution shows the best fit to the ICT distribution from empirical contact data collected in UCSD

Although there could be other types of mobility patterns that could generate the same ICT distributions as UCSD’s, this result allows us to conjecture that the actual mobility that generates these characteristics in these settings is more closely modeled by Levy walks than Brownian Motion (BM). Furthermore, the ICT distribution patterns of various mobility models are closely related to their diffusion rates. In Random Way Point (RWP) model, the mobility is the most diffusive and in BM it is the least. In TLW, the diffusivity is in-between and with smaller value of α it becomes more diffusive. The more diffusive the mobility is, the shorter tail its ICT distribution becomes.

Figure. ICT distributions generated by various mobility models. As the ratio of long jumps increases, the tails boceome shorter.

Another important fact for ICT distribution is that the ICT distribution which shows dichotomy can also be best fitted by truncated power law. The reason is the power law form of ICT distribution generated by short flights is truncated due to the existence of long jumps. We perform MLE and Akaike test to visually and quantitatively check the best fitted ICT distribution. From the results we can see that the ICT distribution is best fitted by truncated power law. The ICT distribution generated by our TLW model is also best fitted by truncated power law. For the detailed explanation for the MLE and Akaike test, refer to Akaike test. In this test, the best fitting distribution is the one giving the minimum Akaike's Information Criteria (AIC) value or Akaike Weight (AW) closest 1.

Figure. The ICT distribution measured from the UCSD data set can be best fitted by a truncated Pareto distribution

Routing performance

To see the effect of Levy walk features on routing performance, we simulate one of the most widely studied DTN routing algorithms called two-hop relay routing [Grossglauser 02] where a source node sends a message to the first node it meets and then that first node acts as a relay and delivers the message when it contacts the destination node of the message. We run the protocol under various mobility models including RWP, BM and TLW with various α values (small values induce heavier tails in flight distributions).

Figure. Routing delays according to two hop relay model under various mobility models. The left one shows that the tail length of the routing delay distributions rely on the diffusivity of underlying mobility models. The figure at the right shows normalized 99% quantile delay with multiple relays.

The closed form of routing delay according to two hop relay algorithm can be described by Inspection paradox [Bremaud 99]. Let's say the period between the time that the message has originated and the time that the message is delivered to the relay node is the first contact time (FCT) to a relay and the period after that to the time the message is delivered to the destination is the remaining inter-contact time (RICT) between the relay and destination. In a dense network, FCT is typically negligible and RICT dominates the message delay. As we know the ICT distribution follows truncated power law, it can be represented as follows.

X denotes ICT. Then by Inspection paradox, the distribution of routing delay, Z, can be represented as follows. Since we are assuming dense enough network, Z has approximately same distribution as the remaining ICT, Y. For detailed development, please refer to our paper, [Hong 08].

The expectation of routing delay, E(Z), can be represented as follows.

We simulate a multi-copy protocol where the source distributes the message to the first m relays that it contacts. The routing delay is the time till any copy of the message is delivered to the destination. The above figure shows the 99% quantile delays of the same models normalized by their corresponding one-relay delays as we add more relays. As expected, in BM, the delay does not improve so much as the number of relays increases, since every relay takes long time to meet the destination. However, it is interesting to note that all our Levy walk models including the one with α = 1.5 which shows fairly similar delay patterns as BM for one relay case, show almost the same improvement ratio as RWP as we add more relays. This implies that while in RWP, most nodes travel long distances frequently, in Levy walks, although not all nodes make such long trips, there exist with high probability some nodes within the mobility range of the source nodes that make such long trips. This contributes to the great reduction of the delays even with a small number of relays.

Reference

[Bremaud 99] P.Bremaud. Markov Chains, Gibbs Field, Monte Carlo Simulation and Queues. Springer-Verlag, 1999.
[Chaintreau 06] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, Impact of human mobility on the design of opportunistic forwarding algorithms, IEEE INFOCOM 2006, Barcelona, Spain, April 2006.
[Grossglauser 02] M. Grossglauser and D. N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Trans. on Networking, vol. 10, no. 4, pp. 477–486, 2002.
[Hong 08] Seongik Hong, Injong Rhee, Seong Joon Kim, Kyunghan Lee and Song Chong, Routing Performance Analysis of Human-Driven Delay Tolerant Networks using the Truncated Levy Walk Model, ACM SIGMOBILE International Workshop on Mobility Models for Networking Research (Colocated with MobiHoc 08), Hong Kong, 2008 PDF
[Karagiannis 06] T. Karagiannis, J.-Y. L. Boudec, and M. Vojnovic. Power law and exponential decay of inter contact times between mobile devices. ACM Mobicom, Montreal, Canada, 2007.
[Maruyama 03] Y. Maruyama and J. Murakami, Truncated levy walk of a nanocluster bound weakly to an atomically flat surface: Crossover from superdiffusion to normal diffusion, Physical Review B, vol. 67, no. 8, 2003.
[Mcnett 05] M. McNett and G. M. Voelker, Access and mobility of wireless pda users, SIGMOBILE Mob. Comput. Commun. Rev., vol. 9, no. 2, pp. 40–55, 2005.
[Rhee 08] Injong Rhee, Minsu Shin, Seongik Hong, Kyunghan Lee and S. Chong, On the levy walk nature of human mobility, IEEE INFOCOM, 2008. PDF PPT

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

Conferences & Workshops

• Minsu Shin, Seongik Hong and Injong Rhee, DTN Routing Strategies using Optimal Search Patterns, ACM MobiCom Workshop on Challenged Networks (CHANTS), 2008, PDF
• Seongik Hong, Injong Rhee, Seong Joon Kim, Kyunghan Lee and Song Chong, Routing Performance Analysis of Human-Driven Delay Tolerant Networks using the Truncated Levy Walk Model, ACM SIGMOBILE International Workshop on Mobility Models for Networking Research (Colocated with MobiHoc 08), Hong Kong, 2008 PDF
• Injong Rhee, Minsu Shin, Seongik Hong, Kyunghan Lee and Song Chong, On the Levy-walk Nature of Human Mobility, INFOCOM, Arizona, USA, 2008 PDF PPT
• Injong Rhee, Minsu Shin, Seongik Hong, Kyunghan Lee and Song Chong, Human Mobility Patterns and Their Impact on Delay Tolerant Networks, ACM HotNets? IV, 2007 PDF

Technical Reports

• Injong Rhee, Minsu Shin, Seongik Hong, Kyunghan Lee and Song Chong, On the Levy-walk Nature of Human Mobility: Do Humans Walk like Monkeys?, Technical Report, Computer Science Department, North Carolina State University, 2007 . PDF
• Diffusion Regimes of Levy Walk, Technical Memo, Computer Science Department, North Carolina State University, 2007 . PDF