Simulation of DTN nodes' mobility using least action principle for locations selection

Abstract

Three modifications of mobility model of DTN's nodes are presented. These modifications are based on the Levy mobility model. Flight length of DTN nodes inside some locations (hot spots) is a random value with the Levy probability distribution function. Between locations the nodes can move differently. In the first modification nodes walk between different locations randomly; in the second modification nodes walk between locations using the least action principle; and in the third modification each node chooses the next location according to a limiting number of possible visits. These modifications are implemented in the Omnet++ simulation environment. This paper presents an experimental results of DTN nodes' movements modeling, and comparison of these results with real nodes movements data.

Keywords

• mobility model
• Levy probability distribution function
• selfsimilarity
• OMNET++

1. Introduction

MANET is a continuously self-configuring, infrastructure-less network of mobile devices connected without wires. Each device can move independently in any direction, so it often breaks off and establish connection. Delay-Tolerant Networking (DTN) is an approach for constructing of network architecture for heterogeneous network that may lack continuous network connectivity. In this context, delay means time loosing occurred in transitive nodes or generated by low channel bandwidth.

For the aim of routing on the network layer, it used special protocols oriented on dynamic networks: reactive (AODV, DSR, etc.) and proactive (OLSR, etc.). Preferences for a particular type of protocols may be given only in view of real situation and velocity of subscribers. People often carries wireless devices, so understanding human mobility patterns contributes for more accurate performance modeling and for more predictable protocols used for these networks.

Widely used mobility models in research of the computer networking are random waypoint [ 1 ], random walk models [ 2 ], such as model of Brownian motion or Markovian mobility [ 3 ]. These models are simple enough for theoretical treatment and, at the same time, are simple for emulating in the simulation environment in a scalable manner. However, the adequacy and accuracy of these mobility models is still the subject of research, and the problem of building adequate mobility models is very important and urgent.

In this paper we construct the modification of mobility model Truncated Levy Walk [ 4 ] and study the effectiveness of each movement simulation model.

2. Levy mobility model

To analyze the performance of mobile networks, as mentioned above, different mobility patterns are used. In the proposed mobility model, well-known Levy Mobility Model [ 7 ] plays an important role, so further we shortly remind a mathematical description of this model and an application to the people mobility.

Let a flight be the longest straight transition of node from one location to another without changing direction or pause. The path, built of successive movements will be called route.

To simulate the mobility on a confined area a truncated distribution (TLW – Truncated Levy Walk), based on a truncated Pareto distribution for the length of the movement and pause time interval is often used [ 5, 6 ]. This truncated distribution is used instead of simple Levy distribution, based on a normal distribution of Pareto. The Levy distribution itself with the normalizing factor c and the exponent  in terms of the Fourier transform looks as [ 5 ]: f X (x)  1  exp itx  ct   dt . (1) 2 

In the model it is assumed that the node performs its flights based on a given distribution function for the length of Levy flight and for the duration of the pause following the jump, with coefficients c , and c , , respectively – these are parameters of the model. It needs to define these settings for simulations, because they will fit the artificial route closer to the real one in a statistical manner.

As shown in [ 5 ], the average speed of movement of people is not constant, and can be expressed by the following relationship between the duration of the flight and its length: t f  kl1 , 0    1, where k and  some constants, l – flight length, t f – time duration of flight.

2.1. Levy walks for short distances and flights between locations

Real traces are recorded using GPS sensors carried by the participants of the experiment. Some of these data is available in [ 8 ]. The data in these traces are a set of records "time – place position". As mentioned in [ 5, 6, 9 ], the processing of these data shows that the Levy mobility model describes well the movements of people only for short distances. (2)

According to [ 9 ], we also call waypoint a circle of radius R = 5 m, in which a person holds on more than T = 30 sec. The position of a waypoint is a position of the center of this circle. Waypoints are determined from the real traces of people.

This "aggregating" procedure produces a consistent set of waypoints for a more precise definition of the relocation fact of one person. So all positions in the circle for the specified time threshold are took as a point at which person spent time. The radius and the threshold time are determined based on a typical user behavior. After that, there is determined the visited location – rectangular clusters combine similar points. Locations are transitive closure of points placed from each other at a distance of 100 m. These locations outline typical regions of the cluster of users. From real source traces, numerical estimates of the probability distribution function for the length between waypoints in the same location and pause time in them are obtained. Parameters c , and c , are determined from this distributions. These parameters will be used to simulate the users’ movements within a single location.

Our mobility model (in all modifications), organized as follows: the movement of the node begins at a random location and hold on there according to the Levy mobility model until the next flight gets out the node of the location. After that, the cornering procedure tries to keep the node inside location by changing direction of the flight. This cornering procedure is carried out in a way saved flight length to not spoil it’s probability distribution function. If this procedure failed, then node selects the next location.

In the first modification of the model next location is selected in a random manner and each location can be selected only once. p j  kV V '

1 diak ,

2.2. Levy mobility model with the LATP algorithm

These movements are fully consistent with the previous movements, in terms of generation regular flights and pauses, but differs in terms of the choice of another location.

Movements of people depend on the selection of the next waypoint. Many factors play a role in this choice. Everyone has different factors and personal situation, so it is almost impossible to get an algorithm that takes into account all of these factors. Work [ 9 ] shows the selection of the next location is strongly dependents on the current location. The principle of least action of Maupertuis in this case may provide some explanation: people tend to perform actions that require the least effort. Due to this it is possible to introduce an algorithm which reflects this trend to select the next location (out of the previously known set), depending on the distance to it. This algorithm is called Least Action Trip Planning (LATP).

We describe this algorithm below. While the current location is i , the set of all locations is V , then the probability of selecting the next location with number j is calculated as follows:

1 diaj (3) real variable with values in the range 0;  , and V ' – a set of locations from V , that have already visited.

2.3. Levy mobility model with the LATP algorithm and possible plural visits of location

This version is almost completely corresponds to the previous model, except for the possibility to choose of previously visited location. Experimental analysis of userproduced traces in [ 8 ] shown that people are also returning to the previously visited location. That was not considered in the model [ 9 ]. So, in our third modification, the number of visits of all previously defined locations obtained from real traces is used to provide simulation with this information. All traces are analyzed before simulation and compiled a histogram frequency of visits for each location.

3. Modeling

For experimental studies of these modifications of the mobility model, they have been implemented in the simulation environment OMNeT ++ using INET framework. The simulation results are artificially generated traces of human mobility. They pass through the same analysis as the real traces to obtain numerical estimates of the probability distribution function of the flight lengths and pauses. Below we present some results of experiments based on real traces of KAIST’s and NCSU’s campuses [ 8 ].

The simulation parameters are: and for the flight length, and for the pause time. Duration of simulation is 2 days of model time (or 172800 model seconds). The area of simulation is the same as for the original traces.

The results of the simulation of our first modification for the complementary cumulative distribution function can be seen on the Figure 1. By definition, cumulative distribution function has form: F  x  P  X  x  1 F  x .

The results of the simulation of Levy mobility with LATP algorithm (our second modification) for complementary cumulative distribution function (4) are shown on Figure 2.

Figure 2 shows that the overall shape of the graphs became much closer than on Figure 1, which indicates that the second modification of the mobility model closer captures the statistical features. However quantitative differences remain. As you can see, part of the graph, which corresponds to movements between locations has been improved, and it indicates the advantages of the LATP algorithm.

The results of the simulation of Levy mobility model with LATP algorithm and possible plural visits of location (our third modification) are shown on Figure 3.

Figure 3 shows the shapes of the graphs even closer, compared with the previous model modifications. It indicates a best adequacy of this last model modification.

4. Conclusion

Three modification of mobility model of nodes are implemented: TLW mobility model using just information about crowd of people on the real terrain (visited locations), and then the same model with an LATP algorithm for selection of a next location, and the same model with the LATP algorithm with possible plural visits of location. The comparison of the simulation results with the real traces are presented.

Presented model with its all modifications are easy to implement and should be more efficient than other popular models (e.g. [ 6 ]). We plan to develop a better selection algorithm for the next location by using information about the history of the movements of a real people. As we hope, this will bring the simulation even closer to the real life.

References

1. Bettstetter C , Resta G , Santi P. The node distribution of the random waypoint mobility model for wireless ad hoc networks . IEEE Transactions on Mobile Computing , 2003 ; 2 ( 3 ): 257 - 269 .

2. Camp T , Boleng J , Davies V. A survey of mobility models for ad hoc network research . Wireless Communications and Mobile Computing , 2002 ; 2 ( 5 ): 483 - 502 .

3. Bettstetter C . Mobility modeling in wireless networks: Categorization, smooth movement, and border effects . Mobile Computing and Communications Review , 2001 ; 5 ( 3 ): 55 - 66 .

4. Privalov AYu , Tsarev AA . The DTN nodes' mobility model based on Levy distribution function. Advanced information technologies . Samara: Publisher Samara Scientific Center RAS , 2015 ; 2 : 30 - 34 .

5. Rhee I , Shin M , Hong S , Lee K , Kim SJ , Chong S. On the Levy-Walk Nature of Human Mobility . IEEE/ACM Transactions on Networking, 2011 ; 19 ( 3 ): 630 - 643 .

6. Lee K , Hong S , Kim SJ , Rhee I , Chong S. SLAW : Self-Similar Least -Action Human Walk . IEEE/ACM Transactions on Networking, 2012 ; 20 ( 2 ): 515 - 529 .

7. Shlesinger MF , Zaslavsky GM , Klafter J. Levy dynamics of enhanced diffusion: Application to turbulence . Physical Review Letters , 1987 ; 58 : 1100 - 1103 .

8. Kotz D. Community Resource for Archiving Wireless Data at Dartmouth . Dartmouth College. Source: <http://www.crawdad.org/index.html>.

9. Lee K , Hong S , Kim SJ , Rhee I , Chong S. Demystifying Levy Walk Patterns in Human Walks . NCSU/CSC: Technical Reports , 2008 .