14-06-2009, 12:49 AM
Impact of Node Mobility on Routing Protocols for Wireless Sensor Networks
G. Santhosh Kumar, M.V. Vinu Paul and K. Poulose Jacob
Abstractâ€
1
Wireless sensor networks monitor their
surrounding environment for the occurrence of some
anticipated phenomenon. Most of the research related to
sensor networks considers the static deployment of sensor
nodes. Mobility of sensor node can be considered as an
extra dimension of complexity, which poses interesting
and challenging problems. Node mobility is a very
important aspect in the design of effective routing
algorithm for mobile wireless networks. In this work we
intent to present the impact of different mobility models
on the performance of the wireless sensor networks.
Routing characteristics of various routing protocols for
ad-hoc network were studied considering different
mobility models. Performance metrics such as end-to-end
delay, throughput and routing load were considered and
their variations in the case of mobility models like
Freeway, RPGM were studied. This work will be useful to
figure out the characteristics of routing protocols
depending on the mobility patterns of sensors.
Index Terms†Wireless Sensor Network, Ad-Hoc
Network, Mobility Model, Routing Protocol
I. I
NRODUCTION
W
ireless
sensor
networks
[1,2]
are
promising
unprecedented levels of access to information about the
physical world, in real time. Many areas of human activity
are starting to see the benefits of utilizing sensor networks.
Some of the real deployments include UC Berkleyâ„¢s Smart
Dust, MIT™s µ-Adaptive Multi-domain Power aware Sensors
and UCLAâ„¢s Wireless Integrated Sensor Networks. In almost
all such cases, sensor networks are statically deployed. In
static networks, the mobility of sensors, users and the
monitored phenomenon is totally ignored. The next
evolutionary step for sensor networks is to handle mobility in
all its forms. One motivating example could be a network of
environmental monitoring sensors, mounted on vehicles used
to monitor current pollution levels in a city. In this example,
the sensors are moving, the sensed phenomenon is moving
and users of the network moves as well.
The dynamic nature of mobile wireless sensor networks
introduces unique challenges in aspects like data
Department of Computer Science, Cochin University of Science and
Technology, Cochin, Kerala, India.
an,kpj[at]cusat.ac.in, vinu[at]cair.res.inmanagement, accuracy and precision, coverage, routing
protocols, security, software support. Many of the above
mentioned problems related to a static deployment of the
sensors are well addressed by the researchers. One of the
most important constrains on sensor nodes is the route
enabling when the nodes keep moving. It has been reported
that the clustering mechanisms and hierarchical routing make
huge improvement in sensor networks in terms of energy
consumption and efficient data gathering [3,4]. Such
improvement is due to the structure of the network, assumed
before the deployment of the sensor nodes. Once the network
becomes dynamic we do not have the freedom to pre-assume
such structures. The conventional routing protocols for static
sensor networks are to be optimized once we introduce
mobility. To study the performance of routing protocols
under such conditions, we have to consider the mobility
patterns of the entire network.
This paper attempts to examine the performance issues
specially on routing associated with mobility in WSN. The
paper is organized as follows, Section II discuss description
of routing protocols used in ad-hoc environment. Section III
describes various mobility models used in common practice.
Section IV details simulation model used for the performance
study and the succeeding section V follows the detailed
experiments used for the performance comparison of various
protocols. Finally Section VI contains the conclusion.
II. R
OUTING
P
ROTOCOLS
Mainly ad-hoc routing protocols are divided into two
categories:
a. Table-driven routing protocols: In table driven routing
protocols, each node maintain the route table, which
contains consistent and up-to-date routing information
about all nodes in the network.
b. On-Demand routing protocols: In on-demand routing
protocols, whenever a source wants to send to a
destination node, it first finds the path to the destination
using route discovery mechanism. Routing overhead is
less and it is suitable for networks where frequency of
communication is very less.
A number of routing protocols like Destination-
Sequenced Distance-Vector (DSDV), Dynamic Source
Routing (DSR), Ad Hoc On-Demand Distance VectorPage 2
International Conference on Sensors and Related Networks
481
Routing (AODV), and Temporally Ordered Routing
Algorithm (TORA) are normally used in ad hoc networks.
A. Destination-sequenced distance-vector routing
The Destination-Sequenced Distance-Vector (DSDV) [5]
routing algorithm is built on top of Bellman-Ford routing
algorithm. The main achievement of the algorithm was to
solve the routing loop problem. In DSDV algorithm, every
mobile station has to maintain a routing table, which lists all
available destinations, the number of hops to reach the
destination and the sequence number assigned by the
destination node. The sequence number is used to distinguish
old routes from new ones and thus avoid the formation of
loops. The stations periodically transmit its routing table to
its immediate neighbors. Transmission of routing table can be
sporadic, if there is a significant change has occurred in its
table from the last update sent. So, the update is both time-
driven and event-driven. The Routing information is
distributed between nodes by sending full dumps infrequently
and smaller incremental updates more frequently. A full
dump sends the complete routing table information to the
neighbors whereas in an incremental update, entries which
posses the metric change is send across to the neighbor.
Thus, the incremental update reduces the routing traffic a lot.
But in view of mobility, node dynamics cause incremental
packets to grow big so full dumps will be more frequent in
use.
B. Dynamic source routing
The distinguishing features of DSR [6] are low network
overhead, requires no extra infrastructure for administration
and the use of source routing. By source routing, implies that
the sender had full knowledge of the complete hop-by-hop
route information to the destination. The protocol is
composed of the two main mechanisms of Route Discovery
and Route Maintenance. Normally routes are stored in a route
cache of each node. When a node would like to communicate
to a destination, first it checks for the route for that particular
destination in the route cache. If yes, the packets are sent
with source route header information to the destination. In
the other case, the route is not available at the route cache;
initiate the route discovery mechanism to get the route first.
Route discovery mechanism, floods the network with route
request (RREQ) packets. RREQ, packets received by the
neighbors, checks for the route to destination in its route
cache. If it is not in cache rebroadcasts it, otherwise the node
replies to the originator with a route reply (RREP) packet.
Since RREQ and RREP packets both are source routed,
original source can able to obtain the route and add to its
route cache. In any case the page link on a source route is broken;
the source node is notified with a route error (RERR) packet.
Once the RERR is received, the source removes the route
from its cache and route discovery process is reinitiated.
DSR being a reactive routing protocol have no need to
periodically flood the network for updating the routing tables
like table-driven routing protocols do. Intermediate nodes are
able to utilize the route cache information efficiently to
reduce the control overhead
C. Ad-hoc on-demand distance vector (AODV) routing
AODV [7] offers quick adaptation to dynamic link
conditions, low resource constrain and low network
utilization. The protocol adapts the similar route discovery
mechanism as in DSR. However, route maintenance in
AODV adapts table driven mechanism, keeps only single
route for each node irrespective of multiple route in route
cache maintained in DSR protocol.
AODV relies on
sequence number based mechanism to keep track of the
freshness of the route entry also to avoid route loops. All the
routing packets carry these sequence numbers. Also AODV
maintains timer-based state information of various states in
each node. Whenever a route entry is not used for long time
the entry will be erased from the route table. Nodes keeps
monitor the page link status of next hope of all the active routes. In
case of any page link break is identified, RERR packets are sent to
notify the other nodes. In contrast to DSR, route error packets
in AODV are intended to inform all sources in the subnet
using the page link when a failure occurs.
III. M
OBILITY
M
ODELS
There is much attention currently focused on the
development and evaluation of wireless routing protocols for
wireless sensor networks. Most of this evaluation has been
performed with the aid of various network simulators (such
as ns-2 and others) and synthetic models for mobility and
data patterns. These models can have a great effect upon the
results of the simulation, and thus, the valuation of these
protocols. Some of the models, which are in consideration for
our work, are listed below.
A. Random waypoint (RW) model
The Random Waypoint model [8] [9] is most commonly
used mobility model in research community. This model is
an extension of Random walk. In this model node starts its
journey from a point, chooses a velocity between [0, V_Max]
towards an intermediate destination, which is chosen in a
random manner. It stays at the intermediate location for a
specified period called pause period. At the end pause
period the node propagation proceed to the new random
destination with a new chosen velocity. In the current
network simulator (ns-2) distribution, the implementation of
this mobility model is incorporated.Page 3
Impact of Node Mobility on Routing Protocols for Wireless Sensor Networks
482
B. Reference point group mobility (RPGM) model
The main use RPGM [10] is in military battlefield
communication. In this mode, each group has a logical center
called group leader. The group leaderâ„¢s motion determines
the behavior of group motion. Initially, each member of the
group is uniformly distributed where group leader also is a
part of that. Each group will have a reference point. At each
instant, nodes in the group are randomly placed at the
neighborhood of the reference point of that group. The speed
and direction variations of each node are derived by
randomly deviating from that of the group leader.
Important Characteristics: Each node deviate its speed
and direction from that of the leader can be characterized as
follows:
1) Velocity {member} (t) = Velocity {leader} (t) + random
() * SDR * Max_speed
2) Angle {member} (t) = Angle {leader} (t) + random () *
ADR * Max_angle
Where 0 <= SDR, ADR <= 1. SDR is the Speed
Deviation Ratio and ADR is the Angle Deviation Ratio. SDR
and ADR are used to control the deviation of the velocity
(magnitude and direction) of group members from that of the
leader. Since the group leader mainly decides the mobility of
group members, group mobility pattern is expected to have
high spatial dependence for small values of SDR and ADR.
C. Freeway mobility (FW) model
The FW [11] model emulates the motion behavior of
mobile nodes on a freeway. It can be very well used in
exchanging traffic status or tracking a vehicle on a freeway.
Important Characteristics: In this model we use maps.
There are several freeways on the map and each freeway has
lanes in both directions. The differences between Random
Waypoint and Freeway are the following:
1) Each mobile node is restricted to its lane on the freeway.
2) The velocity of mobile node is temporally dependent on
its previous velocity. Formally,
vec{Velocity{i}}(t+1) = vec{Velocity{i}}(t) + random()
* vec{a{i}}(t)
3) If two mobile nodes on the same freeway lane are within
the Safety Distance (SD), the velocity of the following
node cannot exceed the velocity of preceding node.
Formally,
for all {i}, for all {j},for all{t}
if D{i,j}(t) < Safety_Distance, then vec{Velovity{i}}(t) <
vec{Velocity{j}}(t), if j is ahead of i in its lane.
Due to the above relationships, the Freeway mobility
pattern is expected to have spatial dependence and high
temporal dependence. It also imposes strict geographic
restrictions on the node movement by not allowing a node to
change its lane.
D. Manhattan mobility (MH) model
The Manhattan model [11] [12], the mobile nodes are
allowed to move along the grids of horizontal and vertical
streets on the map. It can be useful in modeling movement in
an urban area where a pervasive computing service between
portable devices is provided.
Important Characteristics: Maps are used in this model
too. However, the map is composed of a number of
horizontal and vertical streets. The mobile node is allowed to
move along the grid of horizontal and vertical streets on the
map. At an intersection of a horizontal and a vertical street,
the mobile node can turn left, right or go straight with certain
probability. Except the above difference, the inter-node and
intra-node relationships involved in the Manhattan model are
very similar to the Freeway model. Thus, the Manhattan
mobility model is also expected to have high spatial
dependence and high temporal dependence. It too imposes
geographic restrictions on node mobility. However, it differs
from the Freeway model in giving a node some freedom to
change its direction.
The general metric that differentiate one mobility model
from one another are
1. Velocity of specified node at a particular instant of time t.
2. Speed of specified node at a particular time t.
3. Angle made by Velocity vector at time t with the X-axis.
4. Acceleration vector of node at time t.
5. X, Y, Z co-ordinate of node at time t.
6. Distance between nodes two nodes at time t.
7. Transmission range of a mobile node.
8. Number of mobile nodes.
9. Degree of Spatial Dependence: It is extent to which the
velocities of two neighboring nodes are similar.
10.Degree of Temporal Dependence: It is the extent of
similarity of the velocities of a node at two time slots that
are not too far apart. It is a function of the acceleration of
the mobile node and the geographic restrictions.
IV. S
IMULATION
M
ODEL
Routing protocols can be evaluated in two ways. First one
is to use the real hardware itself for evaluation. Since it
requires adequate recourse to be procured to build setup, uses
of simulation-based methods are popular in lab environment.
In both cases, the performance metrics as well as the network
context are equally important. In this paper we use the
simulation-based approach in which the network parameters
must be stated first.
Simulation model based on NS-2 [13] is used here for
evaluation. Support for simulating multi-hop wireless
networks complaint with physical, data link, and medium
access control (MAC) layer, modeled with NS-2. IEEEPage 4
International Conference on Sensors and Related Networks
483
802.11 for wireless LANs is used as the MAC layer protocol.
An un-slotted carrier sense multiple access (CSMA)
technique with collision avoidance (CSMA/CA) is used to
transmit the data packets. The radio model uses
characteristics similar to a commercial radio interface, bit
rate of 2 Mb/s and a nominal radio range of 150 m. The
protocols maintain a send buffer of 50 packets. It contains all
data packets waiting for a route, such as packets for which
route discovery has started, but no reply has arrived yet. To
prevent buffering of packets indefinitely, packets are dropped
if they wait in the send buffer for more than 60 s. All packets
(both data and routing) sent by the routing layer are queued
at the interface queue until the MAC layer can transmit them.
The interface queue has a maximum size of 50 packets and is
maintained as a priority queue with two priorities each served
in FIFO order. Routing packets get higher priority than data
packets.
Continuous bit rate (CBR) traffic sources are used. The
source-destination pairs are spread randomly over the
network. Only 512-byte data packets are used. The number
of source-destination pairs and the packet-sending rate in
each pair is varied to change the offered load in the network.
The mobility models are simulated using the tool
IMPORTANT [14], which generates the scenarios that can
directly call from NS-2 script. The field configurations used
is 1000 m × 1000 m field with a maximum of 40 nodes.
Here, each packet starts its journey from a random location to
a base station with chosen scenario. Once the destination is
reached, another random source is targeted. Simulations are
run for 850 simulated seconds. Identical traffic scenarios are
used across protocols to gather fair results.
Most of the analysis is done using Trace graph [15], a
network trace file analyzer used for network simulator ns-2
trace processing. Because of the use of MATLAB libraries by
the Trace Graph, it gives pretty good graphical analysis.
V. E
XPERIMENTS
Our main focus is given to study whether mobility affects
protocol performance or not. We have evaluated the
performance of DSR, AODV and DSDV across deferent set
of mobility models and observed that the mobility models
may drastically affect protocol performance.
End-to-end delay, throughput and Normalized routing
load are taken as the main metrics for study of performance.
End-to-end delay and throughput have the meaning, which is
same as in networking scenario. Normalized routing load
[16] is the ratio of number of routing packets sends to the
number of data packets received at the destination. This ratio
evaluates the efficiency of routing in terms of extra load
introduces to the network in view of mobility.
The end-to-end delay variations against throughput for
various mobility models are studied first. Fig. 1 shows the
variations for various routing protocols using mobility model
as Freeway. In DSDV, the delay increases almost linearly
with throughput increment except for very low and very high
throughput. Traces are obtained fixing the parameters as
number of nodes to 10 and speed used is 10 m/s. All the
nodes are communicating to a base station. In AODV and
DSR for low throughput the delay increases steeply. But for
medium range of throughput it linearly decreases. Relative
ranking of AODV and DSR seems to be comparable in
freeway model.
RPGM mobility model the delay variation shown for
various rooting protocols is shown in Fig. 2. In DSR for
RPGM mobility model, the delay remains almost same for
entire throughput range except for low throughput, offering a
steady performance irrespective of variations. Also it out
performs very well the other protocols AODV and DSR. In
AODV, for middle range of throughput the performance is
comparable as like in Freeway. In DSR the delay dip rate is
negligibly small compared to AODV.
0
2
4
6
8
0
0.1
0.2
0.3
0.4
Throughput × 10
5
E
n
d
t
o
E
n
d
D
e
la
y
in
m
S
e
c
DSDV
AODV
DSR
Fig. 1. End-to-End delay variations against throughput in Freeway
mobility model
0
2
4
6
8
0
1
2
3
Throughput × 10
5
E
n
d
t
o
E
n
d
D
e
la
y
in
m
S
e
c
DSDV
AODV
DSR
Fig. 2. End-to-End delay variations against throughput in RPGM
mobility model
In Manhattan mobility model the delay variation shown
for various routing protocols is shown in Fig 3. In this
mobility model, DSR performs worst compared to other two
mobility models.Page 5
Impact of Node Mobility on Routing Protocols for Wireless Sensor Networks
484
0
2
4
6
8
0
0.1
0.2
0.3
0.4
Throughput × 10
5
E
n
d
t
o
E
n
d
D
e
l
a
y
in
m
S
e
c
DSDV
AODV
DSR
Fig. 3. End-to-End delay variations against throughput in
Manhattan mobility model
10
15
20
25
30
35
40
45
0
100
200
300
400
500
600
Maximumnumber of Nodes
A
v
e
r
a
g
e
D
e
la
y
in
m
S
e
c
DSDV
AODV
DSR
Fig. 4. Delay variation against the number of nodes
in Freeway model
In, all the three mobility models, the AODV and DSR
routing are seems to be comparable, whereas DSDV protocol
is very much dependent on the mobility pattern. Since it is
proactive table driven category, mobility variations can easily
affect routing performances.
The variation of end-to-end delay against node size for
Freeway mobility model is shown in fig. 4. It is observed that
as the number of nodes increases the AODV and DSDV
performs worst compared to DSR. In DSDV, the node
number increment will increase overhead of routing
messages. In DSR, since it is on demand, may not cause the
any drastic end-to-end delay variations. The speed
maintained as 10 m/s for all trace.
In RPGM routing protocol make use of the relative
properties of the group action. The delay is almost
comparable for medium range of number of nodes per group,
whereas the routing suffers for lower range in DSDV. As
observed from fig. 5, DSDV make use of multi hoping very
well. As the group crowd reduces, node degree affecting the
routing. The parameters maintained constant for the plot are
speed deviation 0.1, angle deviation 0.2 and the number of
group as one.
10
15
20
25
30
35
40
45
0.1
0.2
0.3
0.4
0.5
Number of nodes per group
A
v
e
r
a
g
e
D
e
l
a
y
i
n
S
e
c
DSDV
AODV
DSR
Fig. 5. Delay variation against the number of nodes in RPGM
model
Normalized routing load against the speed variation is
shown in Fig 6. Routing overhead is less in DSR in
comparison with AODV. Since the DSDV offers relatively
very high routing loads (30 times more than that of AODV),
it is not taken it for consideration. The very high overhead in
DSDV is because of flooding of routing packets across the
nodes periodically. But in all the cases mobility increases the
routing load over head.
10
15
20
25
30
35
40
0
0.2
0.4
0.6
0.8
1
Speed in M/Sec
N
o
r
m
a
l
i
z
e
d
R
o
u
t
i
n
g
L
o
a
d
DSR
AODV
Fig. 6. Normalized routing load against Speed variations for
freeway model
Routing load variations with respect to the mobile node
size can be another point of interest. As shown in Fig. 7,
routing load shoots in DSDV as the node number increases.
In DSR offers good performance, than that of AODV. But as
the node number increases AODV out performs DSR. Even
though all of them make use of multi-hoping, fact that in
DSDV doesnâ„¢t get performance like DSR may be of extra
overhead of messaging overrides multi-hoping.
In all cases, DSR demonstrates significantly lower routing
load than AODV and DSDV with the factor increasing with
growing node number.
The various studies on routing protocol for various
mobility models concluded to the followingPage 6
International Conference on Sensors and Related Networks
485
10
20
30
40
0
50
100
150
200
250
Number of nodes
N
o
r
m
a
l
i
z
e
d
R
o
u
t
i
n
g
l
o
a
d
DSR
AODV
DSDV
Fig. 7. Normalized routing load against number of mobile nodes for
freeway model
a. End-to-End Delay Comparison: DSDV and DSR offers
similar fractions for Freeway and Manhattan mobility
models, whereas in RPGM, DSR offers a flat
performance irrespective of throughput variations at the
base station.
b. Average Delay with respect to no. of nodes: In Freeway
DSR out performs AODV and DSDV. But all three
routing protocols show the trend that delay increases with
the factor of increasing node size. In RPGM AODV and
DSDV out perform DSR at large node size.
c. Normalized Routing Load in view of speed: Change in
speed of mobile node, DSDV is performing worst,
beyond the scope, offering very high routing overhead
compared to the other two
d. Routing load in view of node size: Once again DSDV
performs worst. AODV out performs DSR at higher node
size.
VI. C
ONCLUSION
In this paper, we analyzed the impact of mobility pattern
on routing performance of mobile sensor network in a
systematic manner using simulated environment. In our
study, we observe that the mobility pattern does influence the
performance of routing protocols. This conclusion is
consistent with the similar studies going on in this area. This
study that compared different routing protocols, there is no
clear winner among the protocols in our case, and since
different mobility patterns seem to give different
performance rankings of the protocols. Use of test-suite of
mobility models incorporated from IMPORTANT helps a lot
to simulate the scenarios. We, continuing the work on this
area to get the optimized version of ad-hoc routing protocols
well suited for mobile WSNs.
A
CKNOWLEDGMENT
The authors would like to thank Dr G Athithan for his
significant contribution to the original proposal that led to the
creation of this project, and Mr. Jiby J Puthiyedam for his
comments on the first draft of this document.
R
EFERENCES
[1]
F Akylidiz, W. Su, Y Sankarasubramanyam, and E. Cayirci, Wireles
Sensor Network: a survey, Computer Networks, Vol. 38 N0. 4,
2002, pp. 393-422
[2]
Carlos de Morrais Codeiro, Dhrarma Prakash Agarwal AD-HOC
AND SENSOR NETWORKS Theory and Applications I
st
Edition,
World Scientific Publishing Co. Pte. Ltd., Singapore 2006, pp. 19-79
[3]
Wendi Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan,
Energy-Efficient
Communication
Protocols
for
Wireless
Microsensor Networks, Proc. Hawaaian Int'l Conf. on Systems
Science Maui, Hawaii, 2000.
[4]
G. Santhosh Kumar, Lino Abraham Varghese,V. Damodaran, B.
Kannan and K. Poulose Jacob, An energy efficient tree based
adaptive routing protocol for WSNs Proc. on the Ist International
Conference on Information Processing (ICIP 2007), Bangalore,
India, August 2007.
[5]
C. Perkins, P. Bhagwat,, Destination Sequenced Distance Vector
(DSDV), Internet Draft, IETF MANET Working Group, November
2001
[6]
J. G. Jetcheva, Y. Hu, D. Johnson, D. Maltz, The Dynamic Source
Routing Protocol for Mobile Adhoc Networks (DSR), Internet
Draft, IETF MANET working group, November 2001.
[7]
S. Das, C. Perkins, E. Royer, Ad-hoc On Demand Distance Vector
Routing (AODV), Internet “ Draft, IETF MANET Working Group,
November 2001.
[8]
Depanshu Shukla, Sridhar Iyer, Mobility Models In Ad - hoc
Networks, KReSIT, IIT Bombay, Nov 2001
[9]
Tracy Camp, Jeff Boleng and Vanessa Davies. A Survey of Mobility
Models for Ad Hoc Networks Research. Wireless Communications
and Mobile Computing. Volume 2, Number 5. 2002.
[10] Xiaoyan Hong, Mario Gerla, Guangyu Pei and Ching- Chuan Chiang.
A Group Mobility Model for Ad Hoc Wireless Networks. ACM
International Workshop on Modeling and Simulation of Wireless and
Mobile Systems (MSWiM). August 1999.
[11] User Manual for important Mobility Tool Generator in NS-2
Simulator. http://nile.usc.edu/important/software.htm, Release Date
February 2004
[12] T. Camp, J. Boleng, and V. Davies, A Survey of Mobility Models
for AdHoc Network Research, Wireless Communications Mobile
Computing (WCMC): Special Issues on Mobile Ad Hoc Networking:
Research, Trends, and Applications, vol. 2, no. 5, pp. 483“502, 2002.
[13] NS-2, Network Simulator,. http://isi.edu/nsnam/ns/.
[14] F. Bai, N.Sadagopan, and A. Helmy, IMPORTANT: A framework
to systematically analyze the impact of mobility on performance of
routing protocols for adhoc networks, in Proc. of IEEE INFOCOM,
Apr. 2003.
[15] Jaroslaw malek, Kamil Nowek TRACE GRATH Data presentation
system for Network Simulator NS-2 in ISAT (Information System
Architecture and Technology) Conference 2003.
[16] Shyam Lal, Vrinda Gupta, Simulation of DSDV, AODV and DSR
Routing Protocols In Ad-hoc Network, Proc. of ICEMC
2
,
Bangalore, India, August 2007
