This is the post-print version. The original publication is available at https://doi.org/10.1109/WMNC.2013.6549017. (c) IFIP, 2013. This is the author's version of the work. It is posted here by permission of IFIP for your personal use. Not forredistribution. The definitive version was published in Proceedings of the 6th Joint IFIP Wireless and Mobile Networking Conference (WMNC 2013) Poster session.

Effect of Locality of Node Mobility
on Epidemic Broadcasting in DTNs
Kohei Watabe

Hiroyuki Osaki

Graduate School of Information Science and Technology, Osaka University
Suita-shi, Osaka 565–0871, Japan
Email: {k-watabe, oosaki}@ist.osaka-u.ac.jp
Abstract—In DTNs (Delay/Disruption-Tolerant Networks)
composed of mobile nodes, when the node movement has
spatial locality, the nodes repeatedly miss opportunities to forward messages to other nodes, thus lowering communication
performance. In this paper, we analyze the effect of localityof node mobility on message dissemination speed in epidemic
broadcasting. We represent the locality of node mobility using
the positional distribution of nodes in a stationary state, andwe present a method for deriving the ratio of infected nodes
from the positional distribution. Based on the results of anumerical experiment where the positional distribution ofnodes obeys a two-dimensional normal distribution, we showthat the message dissemination speed is heavily restrictedby the locality of node mobility. Moreover, we clarify thata heavy-tailed positional distribution leads to a low localityof node mobility and entails mostly unrestricted message
dissemination speed.

I.

I NTRODUCTION

DTNs (Delay/Disruption-Tolerant Networks), represented by MANET (Mobile Ad-Hoc NETwork), where
nodes are sparse, have attracted considerable attention.
DTNs realize communication under conditions where continuous end-to-end connection is not guaranteed, and they
are expected to realize promising applications in networks
in a disaster areas, military networks, inter-planetary networks, sensor networks, and so forth. Many algorithms forachieving efﬁcient communication in DTNs composed ofmobile devices have been proposed , and most of themcompensate for the lack of connectivity by implementing
store-and-carry message forwarding.
Among methods for one-to-all communication in DTNs
composed of mobile nodes, epidemic broadcasting allows
nodes carrying a message (infected nodes) to forward themessage when they enter the communication range ofother nodes. A message spreads among nodes forming
the network since all infected nodes forward messages
repeatedly. Various algorithms for epidemic broadcasting
are proposed in previous works (refer to [1] and references
therein), in which performance metrics such as message
delivery time, coverage and number of duplicate messages
are evaluated.
Generally, node mobility affects the communication
performance of DTNs, where nodes communicate throughepidemic broadcasting or other manner, and previous works
have conducted various evaluations regarding the effects
of node mobility. In [2, 1], message delivery time andthroughput are compared using various mobility models,

including ones imposing constraints on the mobility ofnodes, as in the case of vehicles on a road, in addition to
fundamental mobility models, such as the random waypoint
mobility model, the random direction mobility model andthe random walk mobility model. Moreover, [3, 4] evaluates the effect of the distribution of rectilinear moving
distance on message delivery time, buffer utilization andthroughput using a mobility model in which nodes repeatedly perform rectilinear motion and randomly change theirdirection. The effect of heterogeneity of node mobility on
message delivery time is also explored in [5].
As shown in Fig. 1, when nodes are likely to movearound a speciﬁc area in the ﬁeld, their trajectories do notintersect, and messages are difﬁcult to spread because thefrequency of contact between nodes is limited. However, in
performance evaluations in the previous works mentioned
above, the areas in which nodes can move are assumed
to be equal, and mobility models are limited to models
where the stationary positional distributions of nodes are
identical. In [2], where the movement of each node isassumed to be restricted to a grid, the stationary positional
distribution is the same for all nodes since they move under
the same restriction. Moreover, in the mobility models in[3, 4], nodes are uniformly distributed in the ﬁeld at a
steady state. When nodes forming a DTN are represented
by humans, node movement is centered at a certain pointin the ﬁeld since it is assumed that humans tend to movearound the base of their activity (e.g., their home or ofﬁce).
If we consider this characteristic of human mobility, models
in which node movement distribution in the ﬁeld is not
restricted do not necessarily reﬂect all the characteristics
of motion of mobile nodes. To our knowledge, thus far
there has been no research focusing on models with local
positional distributions of nodes for evaluating message
dissemination speed in epidemic broadcasting, although [6]has derived a scaling law of asymptotic throughput for
MANET. Therefore, it is important to evaluate message
dissemination speed under environments in which node
movement is restricted and nodes are distributed locallyin the ﬁeld.
In our study, we evaluate the effect of locality ofnode mobility on message dissemination speed in epidemic
broadcasting. First, we express the intensity of locality ofnode mobility through the shape of the positional distribution of nodes and clarify the relationship between positional
distribution and frequency of contact between nodes. In
this way, we derive a weighted adjacency matrix whoseLow locality of node mobility  

High locality of node mobility  
Track does notintersect each other, !
and there is nocontact opportunities.   

Node trajectory   
Field  

Mobile node  Fig. 1.

Intensity of locality of node mobility and contact frequency.

elements are the frequencies of contact between each pairof nodes, and map the problem of epidemic broadcastingfor mobile nodes to the problem of epidemics on a graph.
In this paper, we compare message dissemination speeds
for various intensities of the locality, where the positional
distribution of nodes follow a two-dimensional normal
distribution, by changing the standard deviation. Moreover,
we examine the effect of the tail behavior of the positional
distribution of nodes on message dissemination speed bycomparing the results obtained with a two-dimensional
normal distribution and a heavy-tailed two-dimensional
Cauchy distribution.
The rest of the paper is organized as follows. First,
in Section II, we present the analysis method used toevaluate the effect of locality of node mobility on message dissemination speed in DTNs employing epidemic
broadcasting. Next, in Section III, we present the resultsof numerical experiments in which we compare message
dissemination speeds for different intensities of the localityof node mobility. We conclude the paper and describe thedirection of future work in Section IV.
II.

A NALYSISIn the analytical model used in this paper, we express
the intensity of locality of node mobility using the shape of
the positional distribution of nodes. We assume that nodes
i (i = 1, 2, . . . , N ) have stationary motion patterns andtherefore follow a stationary positional distribution. Notethat we assume that the ﬁeld in which the nodes can moveis a two-dimensional space. The expression of locality ofnode mobility using positional distribution allows us toconsider a wide variety of motion patterns. We quantify theintensity of locality of node mobility as the expectation of
the distance L from the mean/mode point to the current
node position. Larger E[L] indicates a wider range of
motion of nodes and weaker locality of node mobility.
Each node has a communication range r, and a node cancommunicate only when it is within the communication
range of other nodes (in other words, only when nodes arein contact). An infected node forwards a message if it isin contact with a susceptible node. Note that we assume
that infected nodes forward the message instantly, and we
do not take message size into account.
To derive the message dissemination speed in epidemic
broadcasting, ﬁrst we derive the frequency of contact
between nodes from the stationary positional distribution of
the nodes. In DTNs, contact frequency strongly affects theperformance of epidemic broadcasting since infected nodes
forward and disseminate messages only when they are incontact with other nodes. Using the probability density
function (pdf) of the positional distribution of node i, we
can derive the total contact duration Ttotal per unit time
for nodes i and j as follows.
Z ∞Z ∞Z Z
Ttotal =pi (x, y)pj (z, w)dzdwdxdy
−∞ −∞
Rx,y
Z ∞Z ∞≅ r2 πpi (x, y)pj (x, y)dxdy.
(1)
−∞

−∞

where Rx,y denotes the inside area of a circle with a center(x, y) and a radius r, and the approximate equation holds
when r is sufﬁciently small. If we assume that contact
duration is independent of contact frequency per unit
time, we can derive the relation between the total contact
duration Ttotal per unit time and the contact frequency wi,jfor nodes i and j from the average contact duration Tcd .
wi,j =

Ttotal.
Tcd(2)

Samar et al. have investigated the duration of contact
between mobile nodes [7]. According to [7], we can obtain′
the average duration of contact Tcd(v) between a node withvelocity v and other nodes as follows by assuming thatthe velocity of other nodes obeys a uniform distribution
U (0, vmax ),
q
¯
¯
¯
¯
Z π
2
− v 2 sin2 φ ¯vmax + vmax
¯
r
′
¯
¯ dφ.
Tcd (v) =log ¯¯
2vmax 0v + v cos φ¯¯
If we assume that v also obeys a uniform distribution
U (0, vmax ), we can obtain Tcd as follows.
Z vmax
1
′
Tcd =
Tcd
(v)dv.
(3)
vmax 0As a result, we can derive the contact frequency for any
arbitrary node pair by substituting Eqs. (1) and (3) into
Eq. (2).
We can map the problem of epidemic broadcastingfor mobile nodes with a stationary positional distributionpi (x, y) to the problem of epidemics on a graph G associated with a weighted adjacency matrix with elements
wi,j since the rate at which an infected node i forwards a
message to susceptible node j is given as the frequency
of contact wi,j between nodes i and j. The weighted
adjacency matrix of graph G is0w2,1 · · · wN,1
0
wN,2 
 w1,2
A=
,
.
.. 
.
 ..
..
. 
w1,N

w2,N

...

0

where N denotes the number of nodes.
If the contact frequency is w for every node pair, thefollowing differential equation holds by letting I(t) denotes
the ratio of infected nodes at time t [8].
dI(t) = wI(t)(1 − I(t)).
dt

(4)

d	

Extending Eq. (4) by A, we can derive the following
difference equation regarding the probability πi (t) that anode i is an infected node.
π(t + ∆t) = (E − Π) A π(t)∆t + π(t),
π1 (t)π1 (t)0···π2 (t)
 π2 (t)  0π(t) = ..
 ...  , Π =  ...
.
πN (t)
00...

The ratio of infected nodes at time t is derived from π(t)as follows.
N(6)

Therefore, by solving numerically the difference equationin Eq. (5), we can obtain the ratio of infected nodes I(t)at time t, which indicates the message dissemination speedof epidemic broadcasting.
III.

N UMERICAL E XPERIMENT

Though our analysis method can apply to any positional distribution pi (x, y), we present numerical results inwhich the positional distribution follows a two-dimensional
normal distribution as one of the simplest possible cases.
We change the intensity of locality of node mobility by
manipulating the standard deviation of the normal distribution, and compare the resulting message dissemination
speed. We denote the pdf pi (x, y) of node i aspi (x, y) = √1e−(x−hx,i )2
2σ 2

·√

1

e−

(y−hy,i )2
2σ 2

, (7)
2πσ 2
2πσ 2
where σ and (hx,i , hy,i ) denote the standard deviation andcoordinates of the mean point of the normal distribution, respectively. A smaller standard deviation σ leads to stronger
locality of node mobility since the node movements are
conﬁned to a smaller area, and in this case the expectation
E[L] of the distance L from (hx,i , hy,i ) to the current node
position is smaller. When the positional distribution of node
i is given by Eq. (7), we can derive the total duration ofcontact Ttotal between nodes i and j as follows.
Ttotal =(hx,n+1, hy,n+1)	

nd	(hx,2, hy,2)	

(hx,n, hy,n)	

(hx,n+2, hy,n+2)	

(hx,2n, hy,2n)	

(5)


0
0 
.
.. 
. 
πN (t)1 X
πi (t).
I(t) =
N i=1(hx,1, hy,1)	

2
y,i −hy,j )r2 − (hx,i −hx,j )2 +(h
4σ 2
e
4σ 2

We consider the ratio of infected nodes at time t
in a DTN composed of N (= n × n) nodes with thecondition that the mean points (hx,i , hy,i ) line up alongn lines and n rows separated by a distance d which
form a two-dimensional lattice as shown in Fig. 2. We
denote the node infected at time 0 as node 0, and thereby
π(0) = (1, 0, . . . , 0).
We change the intensity of locality of node mobility
by setting the standard deviation σ to 100 [m], 200 [m],400 [m], 800 [m], 1600 [m], 3200 [m] and 6400 [m], andcalculate the time until 50% of the nodes have become
infected (50% delivery time) using Eqs. (5) and (6). We
show the results in Fig. 3. The remaining parameters aren = 10, d = 400 [m], r = 50 [m] and vmax = 8000 [m/h].
Figure 3 presents the results of a Monte Carlo simulation

d	

nd	

(hx,n(n-1)+1, hy,n(n-1)+1)	

(hx,n(n-1)+2, hy,n(n-1)+2)	
 (hx,nn, hy,nn)	

Fig. 2. Location of the mean points (hx,i , hy,i ) of positional distributions of nodes

in which an infected node forwards a message randomly inaccordance with the rate of link weights on a graph with aweighted adjacency matrix A. According to the ﬁgure, we
can conﬁrm that the 50% delivery time is extremely longin the case of σ = 100 [m]. The main reason for this is that
infected nodes not likely to move to areas in which othernodes are distributed since the locality of node mobility is
too strong. Similarly, the 50% delivery time is also longwhen σ is larger than 1600 [m]. The reason for this is theextremely weak locality of node mobility, as a result of
which each node covers a rather wide area, and thereby
many opportunities for establishing contact are lost.
Moreover, to investigate the effect of a heavy-tailed
positional distribution of nodes on message dissemination speed, we compare the results for a two-dimensional
Cauchy distribution with those for a two-dimensional
normal distribution. The tail behavior of the positional
distribution reﬂecting the motion patterns of nodes strongly
affects the expectation E[L] of the distance L from amean/mode point to the current node position. The Cauchy
distribution is well known as a heavy-tailed distribution [9],although its pdf is symmetric and bell-shaped, similarly tothe pdf of a normal distribution. Similarly to case of normal
distribution, we give the positional distribution pi (x, y) of
node i as follows.
γγ
pi (x, y) =. (8)π((x − hx,i )2 + γ 2 ) π((y − hy,i )2 + γ 2 )Note that γ and (hx,i , hy,i ) denote the scale parameter andthe coordinates of the mode point, respectively. When thepositional distribution of node i is given by Eq. (8), we
derive the total duration of contact Ttotal per unit time
between nodes i and j as follows.
Ttotal =4r2 γ 2.
π((hx,i − hx,j )2 + 4γ 2 )((hy,i − hy,j )2 + 4γ 2 )Figure. 4 shows a comparison of the 50% delivery
time for a Cauchy distribution (calculated by numericallysolving the difference equation in Eq. (5)) and that fora Monte Carlo simulation. To perform direct comparison with the results for a normal distribution, we adjust
the scale parameter γ such that xc and xn , satisfying
Fc (xc ) = 0.9 and Fn (xn ) = 0.9, take the same value,
where Fc (x) and Fn (x) denote the cumulative distributionfunctions of Cauchy and normal distributions. Therefore,
the area in which a node is distributed with probability 0.8(in other words, excluding the portions of the two tails of
the distribution corresponding to a probability of 0.1 each)is the same for both distributions. Note that the horizontal

60!
Results with Monte Carlo simulation!
Solution of difference equation!

80!

50% delivery time  

50% delivery time  

100!

60!
40!
20!
0!
100!

1000!
Standard deviation of position distribution of nodes  

50!
40!
30!
20!
10!
0!
100!

10000!

Results with Monte Carlo simulation!
Solution of difference equation!

1000!
10000!
Standard deviation of corrresponding normal distribution  Fig. 3. 50% delivery times for different two-dimensional normal distribu- Fig. 4. 50% delivery times when the positional distributions of nodes follow
tions used for the positional distributions of nodes.
a two-dimensional Cauchy distribution.

axis represents the standard deviation of the corresponding
normal distribution, and other parameters are the same asin the example of a normal distribution. By comparing
Fig. 3 with Fig. 4, we can conﬁrm that although the 50%
delivery time is long in the results of normal distribution
when σ = 100 [m], the corresponding result for a Cauchy
distribution is nearly the same as the results for Cauchy
distribution that are corresponding to σ = 200 [m] andσ = 400 [m]. The main reason for this result is thatcompared with case of a normal distribution, in the caseof a Cauchy distribution there is a high probability that anode contacts another node located far from it since thelatter distribution has a heavy tail and the locality of node
mobility is extremely weak.
The results for the examples mentioned above provide
helpful suggestions for designing DTNs. In our result whenσ = 100, heavy-tail of positional distribution reduces
the 50% delivery time to about 1/10. For a heavy-tailed
positional distribution of mobile nodes, we can expect thatmessages can be disseminated within a reasonable period oftime, even if the density of nodes is very low and the nodes
are located far apart. For instance, regarding real-world
human movement patterns, the distribution of the distances
to destinations is heavy-tailed [4], which suggests that thepositional distribution of nodes is heavy-tailed. Moreover,in scenarios where we can control the motion patternsof nodes (e.g., in sensor networks), fast delivery can beachieved by designing heavy-tailed positional distributions.
IV.

tailed positional distribution, messages can be disseminatedwithin a reasonable period of time even if the density ofnodes is low and they are located far from each other.
Although in this paper we focused on a method forderiving the ratio of infected nodes, a weighted adjacency
matrix A whose elements are the frequencies of contact
between nodes allows us to conduct various analyses. Epidemics on a graph have been studied in detail in a numberof previous works. For instance, an analysis of epidemic
thresholds has been conducted using the eigenvalues of an
adjacency matrix . In future work, we plan to utilize theseresults to analyze message dissemination in the case of
epidemic broadcasting in DTNs composed of mobile nodes.
ACKNOWLEDGMENT
This work was supported by JSPS Grant-in-Aid for
JSPS Fellows Grant Number 24 · 3184.
R EFERENCES
[1]

[2]

[3]

C ONCLUSION AND F UTURE W ORK

We evaluated the effect of locality of node mobility
on message dissemination speed in epidemic broadcasting.
We derived the contact frequency between node pairs
from the stationary positional distributions of nodes, andpresented a method for deriving the ratio of infected nodes.
Through numerical experiments, we investigated the casein which the positional distributions of nodes follow a
two-dimensional normal distribution, and showed that themessage dissemination speed is considerably lower when
the standard deviation of the normal distribution is small
and the locality of node mobility is strong. Moreover,
we compared the results for a two-dimensional normal
distribution and those for a heavy-tailed two-dimensional
Cauchy distribution, and showed that message dissemination speed is almost unrestricted when the stationary
positional distribution of nodes is heavy-tailed (entailingweak locality of node mobility). These results suggestthat when the motion patterns of nodes follow a heavy-

[4]

[5]

[6]

[7]

[8]

[9]

F. Giudici, E. Pagani, and G. P. Rossi, “Impact of Mobility on
Epidemic Broadcast in DTNs,” Wireless and Mobile Networking,vol. 284, pp. 421–434, 2008.
D. Raymond, I. Burbey, Y. Zhao, S. Midkiff, and C. P. Koelling,“Impact of Mobility Models on Simulated Ad Hoc Network Performance,” in Proc. International Symposium on Wireless Personal
Multimedia Communications (WPMC 2006), San Diego, CA, USA,
Jul. 2006, pp. 398–402.
U. Lee, S. Y. Oh, K.-W. Lee, and M. Gerla, “Scaling Properties of
Delay Tolerant Networks with Correlated Motion Patterns,” in Proc.
The 15th Annual International Conference on Mobile Computing
and Networking (MobiCom 2009) Workshop, Beijing, China, Sep.
2009, pp. 19–26.
I. Rhee, M. Shin, S. Hong, K. Lee, and S. Chong, “On the LevyWalk Nature of Human Mobility: Do Humans Walk Like Monkeys?”
IEEE/ACM Transactions on Networking, vol. 19, no. 3, pp. 630–643,
2011.
A. Picu and T. Spyropoulos, “An Analysis of the Information Spreading Delay in Heterogeneous Mobility DTNs,” Computer Engineeringand Networks Lab (TIK), Swiss Federal Institute of Technology(ETH) Zurich, Tech. Rep. 341, Dec. 2011.
M. Garetto, P. Giaccone, and E. Leonardi, “Capacity Scaling in
Ad Hoc Networks with Heterogeneous Mobile Nodes: The SuperCritical Regime,” IEEE/ACM Transactions on Networking, vol. 17,
no. 5, pp. 1522–1535, Oct. 2009.
P. Samar and S. B. Wicker, “Link Dynamics and Protocol Designin a Multihop Mobile Environment,” IEEE Transactions on Mobile
Computing, vol. 5, no. 9, pp. 1156–1172, Sep. 2006.
X. Zhang, G. Neglia, J. Kurose, and D. Towsley, “Performance Modeling of Epidemic Routing,” Computer Networks, vol. 51, no. 10, pp.
2867–2891, Jul. 2007.
N. L. Johnson, S. Kotz, and N. Balakrishnan, “Cauchy Distribution,”in Continuous Univariate Distributions, 1994, ch. 16, pp. 298–336.