=Paper=
{{Paper
|id=Vol-1490/paper25
|storemode=property
|title=Simulation of DTN nodes' mobility using least action principle for locations selection
|pdfUrl=https://ceur-ws.org/Vol-1490/paper25.pdf
|volume=Vol-1490
}}
==Simulation of DTN nodes' mobility using least action principle for locations selection==
https://ceur-ws.org/Vol-1490/paper25.pdf
Mathematical Modeling
Simulation of DTN nodes' mobility using least action
principle for locations selection
Privalov A.Yu., Tsarev A.A.
Samara State Aerospace University
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, self-
similarity, OMNET++.
Citation: Privalov A.Yu., Tsarev A.A. Simulation of DTN nodes' mobility
using least action principle for locations selection. Proceedings of Information
Technology and Nanotechnology (ITNT-2015), CEUR Workshop Proceedings,
2015; 1490: 219-226. DOI: 10.18287/1613-0073-2015-1490-219-226
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
219
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
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
2
exp itx ct dt . (1)
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 , (2)
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.
220
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
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.
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 dija
pj , (3)
k V V '
1 dika
221
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
where d ij – the Euclidean distance from the location i to j , parameter a –a fixed
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 user-
produced 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 . (4)
Figure 1 shows that the general shape of the graphs are pretty close, which
indicates the adequacy of this model, although at some distances quantitative
differences are considerable (in our paper [4] one can find the results for this
modification without cornering procedure). The initial parts of the graphs (up to 16
meters – a mark 4 on a logarithmic axis) correspond to movements inside a location
according to the Levy mobility model. The rest of the charts – is mainly movements
between locations.
222
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
а)
b)
Fig. 1. – The CCDF (4) in the logarithmic coordinate axes for the real and the simulated traces
on the KAIST’s territory (a) and on the NCSU’s territory (b)
223
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
а)
b)
Fig. 2. – The CCDF (4) in the logarithmic coordinate axes for the real and the simulated traces
on the KASIT’s territory (a) and on the NCSU’s territory (b)
224
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
а)
b)
Fig. 3. – The CCDF (4) in the logarithmic coordinate axes for the real and the simulated traces
on the KAIST’s territory (a) and on the NCSU’s territory (b)
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.
225
Information Technology and Nanotechnology (ITNT-2015)
Mathematical Modeling Privalov A.Yu., Tsarev A.A. Simulation of DTN…
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: .
9. Lee K, Hong S, Kim SJ, Rhee I, Chong S. Demystifying Levy Walk Patterns in Human
Walks. NCSU/CSC: Technical Reports, 2008.
226
Information Technology and Nanotechnology (ITNT-2015)