14-06-2009, 12:53 AM
Routing Protocol Enhancement for handling
Node Mobility in Wireless Sensor Networks
G. Santhosh Kumar
1
, Vinu Paul M V
2
, G. Athithan
3
and K Poulose Jacob
4
1,4
Department of Computer Science, Cochin University of Science and Technology, Cochin -682 022,
Kerala, INDIA. Email: {san, kpj}[at]cusat.ac.in
2,3
Centre for AI and Robotics, DRDO, Bangalore-560 093, INDIA
Email: {vinumanayil, athithan.g}[at]gmail.com
Authorized licensed use limited to: COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY. Downloaded on February 7, 2009 at 06:47 from IEEE Xplore. Restrictions apply.Page 2
Phase of clusters within a round, it performs poorly with
serious data loss in the environment of node mobility.
The enhancement to LEACH to support mobility is
addressed in LEACH-Mobile, in short LEACH-M [6]. The
basic idea in LEACH-M is to confirm whether a mobile sensor
node is able to communicate with a specific cluster head or
not. This is implemented by transmitting a message, which
requests for data transmission back to mobile sensor node
from cluster head within a time slot allocated in TDMA
schedule of a wireless sensor cluster. If the mobile sensor node
does not receive the data transmission from cluster head
within an allocated time slot according to TDMA schedule, it
sends a join-request message at next TDMA time slot
allocated. Then it decides the cluster to which it will belong
for this moment by receiving cluster join-ack messages back
from specific cluster heads. The LEACH-M protocol achieves
definite improvement in data transfer success rates as mobile
nodes increase compared to the non-mobility centric LEACH
protocol.
LEACH-M handles node mobility well, if the cluster heads
are more or less stationary. But it is not true in all the cases, as
the cluster head election happens from the same set of mobile
nodes. Also the cluster head rotation is purely random and
depends on the number of times the node was a cluster head in
earlier rounds of TDMA, which is exactly the same way as in
basic LEACH protocol. But as the cluster head keeps moving
before the rotation happens, cluster itself gets disturbed and an
enormous amount of packet loss may occur until the formation
of the next new cluster under a new head.
In this paper we propose an improvement to the LEACH-
M protocol, which is suitable for mobile wireless sensor
networks. The basic idea of this LEACH-Mobile-Enhanced
(LEACH-ME) protocol is to make sure as much as possible
that the cluster heads are from the group of mobile nodes
having minimum node mobility or they are in a group motion
with the other cluster members (as in RPGM model [7]). With
the modified cluster heads election process, the proposed
protocol makes sure that the clusters are disturbed minimally
in the event of movement of cluster heads.
II. LEACH-MOBILE-ENHANCED P
ROTOCOL
A. LEACH Routing Phases
The LEACH operations are mainly in two major phases -
Set-up phase and Steady-state phase. Set-up phase is the initial
one and this is the phase where all cluster formation takes
place. This phase is relatively short compared to the steady-
state phase. In this phase, one of the basic ideas in LEACH-
ME is to confirm the election of specific cluster heads which
either have no node movement or minimum relative node
movement.
In the steady-state phase, the cluster head and non-cluster
head nodes receive a particular message at a given time slot
according to TDMA time schedule of sensor cluster, and then
reorganize the cluster with minimum energy consumption.
The steady state phase does the actual data transfer between
the sensing node and the sink.
B. Cluster Head Election and Maintenance in LEACH-M
LEACH-M uses the same set-up procedure used in the basic
LEACH protocol. In LEACH, the nodes organize themselves
into local clusters, with one node acting as the local base
station or cluster-head. If the cluster heads are chosen a priori
and fixed throughout the system lifetime, as in conventional
clustering algorithms, it is easy to see that these sensors
chosen to be cluster-heads would die quickly due to
overloading, ending the useful lifetime of all nodes belonging
to those clusters. Thus LEACH includes randomized rotation
of the high-energy cluster-head position such that it rotates
among the various sensors in order not to drain the battery of a
single sensor. In addition, LEACH performs local data fusion
to compress the amount of data being sent from the clusters
to the base station, further reducing energy dissipation and
enhancing system lifetime.
Sensors elect themselves to be local cluster-heads at any
given time with a certain probability. These cluster head nodes
broadcast their status to other sensors in the network. Each
sensor node determines to which cluster it wants to belong by
choosing the cluster-head that requires the minimum
communication energy
2
. Once all the nodes are organized into
clusters, each cluster-head creates a schedule for the nodes in
its cluster. This allows the radio components of each non-
cluster-head node to be turned off at all times except during its
transmit time, thus minimizing the energy dissipated in the
individual sensors.
C. Cluster Head Election and Maintenance in LEACH-ME
In LEACH the election and cluster head rotation makes sure
that the cluster heads do not die due to prolonged extra work.
This is done by the random rotation of the cluster head duty
across the nodes in the cluster by considering the energy level
of the nodes. In view of mobility centric environment, the
election of a cluster or the job rotation of the cluster head on
purely energy level, without considering the node mobility can
cause serious problem. A node with sufficiently rich energy
level, taking over the duty of cluster head possessing high
mobility, may move out of the cluster, causing the cluster to
become headless. The situation causes the cluster to go for a
new cluster head. But again the mobility of the nodes is not
considered causing the same process to repeat.
To cope with the situation of cluster head going out of reach
due to mobility, the head rotation process needs to consider
the nodeâ„¢s mobility. The nodes need to maintain certain
additional information to make room for handling mobility.
Following are some of the information the node should
maintain [8]:
¢
Role: to indicate if the sensor is acting as a Cluster head CH
(value=1) or as a participating node (value=0) in the zone
¢
Mobility Factor: calculated based on the number of times
that a node changes from one cluster to another or on the
basis of remoteness.
¢
Members List: if the node is a cluster head, a list which
contains references to the nodes associated with its Cluster.
¢
TDMA Schedule: Time slot information, when data need to
be collected from the sensor nodes by the cluster head.
Authorized licensed use limited to: COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY. Downloaded on February 7, 2009 at 06:47 from IEEE Xplore. Restrictions apply.Page 3
The node needs to maintain all these four information, in
which the mobility factor is the one with prime importance for
the election of cluster head. There are different approaches to
calculate mobility factor. One approach is to calculate the
transitions the node makes across the cluster and the other one
is through the concept of remoteness proposed in [9]. In our
proposed scheme we primarily focus on the second method for
the cluster head election.
1) Mobility factor based on transition count
The node associated to a cluster in motion may break its
association to the cluster head and create a new association
with a new cluster head in its new territory. The mobility
factor is calculated based on the number of times the node
moves from one cluster to another.
2) Mobility factor through the Concept of Remoteness
Mobility measure should have a linear relationship with link
change rate. If all the nodes in the cluster are in group motion
like in RPGM [7], even though the nodes are in motion, the
average page link change is minimal, maintaining high spatial
dependency. The node movement in such scenarios doesnâ„¢t
make any breakage of association with the cluster head. So
remoteness can be treated as a measure of mobility factor.
Let
1
,...
3,
2,
1,
0
),
(
-
=
N
i
t
n
i
, where N is the number of
nodes, represents the location vector of node i at time t
and
|)
(
)(
|
)(
t
n
t
n
t
d
i
j
ij
-
=
, the distance from node i to j at time
t. Then the remoteness from node i to node j at time t
is
))
(
(
)(
t
d
F
t
R
ij
ji
=
, where F is the function of remoteness.
For a simple choice of F as identity function, the remoteness is
just the distance between the nodes.
As a node moves relative to the other nodes, remoteness
remains proportionate to its previous values. But as the node
moves in a manner, in which its speed and angular deviation
from the current state are not predictable, remoteness changes
in time. Thus the definition of relative mobility measure in
terms of remoteness of a node as a function of time with
respect to its immediate neighbors is
?
-
=
'
-
=
1
0
|)
(
|
1
1
)(
N
j
ij
i
t
d
N
t
M
(1)
In order to calculate d
ij
(t), from i
th
node to all its j
th
neighboring nodes, the broadcast medium may be used. In
LEACH protocol all nodes in a cluster are time synchronized
with the cluster head. The TDMA schedule issued by the
cluster head are complied by the nodes. Each node uses its
time slot given by the schedule to communicate to the cluster
head. To reduce energy consumption during the other time
slots not intended for a node, the node goes to sleep mode.
Therefore even though a node is in the radio range of its
neighboring nodes, it can not hear the information sent by its
immediate neighbors. In order for nodes to hear
simultaneously, the cluster head gives an extra time slot as
shown in Figure 1.
During the period of extra time slot, called ACTIVE slot, all
nodes need to send their broadcast IDs. As all nodes are time
synchronized with cluster head and use radio propagation, the
node i can make use of the ID broadcast of all the nodes it
hears and calculate d
ij
(t).
Let beacon sent by a neighboring node was at the start of
ACTIVE time slot t
1
and received at time t
2
. The distance d
ij
(t)
= Radio velocity * |t
2
-t
1
| .
Figure.1 TDMA time slots in LEACH-ME protocol
Upon receiving the information from all the nodes, itâ„¢s
possible to calculate the mobility factor for N neighbors
through equation (1). The node with least mobility factor is
considered for the next cluster head, provided the energy level
of that node is not below the threshold. Also the transition
count for the node is checked to be minimal among all of its
neighbors.
The method is explained in steps as given below. We denote
{a} as the normal node, c as the cluster head. The following
steps illustrate cluster head election process.
1. Cluster head c sends ACTIVE message to all its
cluster members to wake up simultaneously.
ACTIVE: c ? {a}: wake up
2. Upon receiving the ACTIVE message, all cluster
members broadcast their IDs with time-stamp. All
cluster member nodes set time-out to receive
broadcast of their entire neighboring node IDs. The
ID_broadcast helps individual node to know its
neighbors.
ID_broadcast:{a} ? NEIGHBORS: know_neighbors
3. Once the broadcast ID timer expires, each node
calculates the remoteness based on the IDs received
and the time at which the IDs are received. The
calculated remoteness information is broadcast by
each node. The process helps to know the remoteness
of neighbors of each other.
remoteness: {a} ? NEIGHBORS :know_remoteness
4. Once all the remoteness values of neighbors are
received nodes can go for cluster head election,
where the node with minimal mobility factor is
elected as cluster head, provided its energy level is
not below the threshold.
It should be noted that the cluster head election need not
be done at every TDMA time slot. ACTIVE time slot can be
introduced periodically after a certain number of regular
TDMA periods. The periodicity can be decided based on the
active mobility of the nodes. Initial creation of clusters is
based on certain random selection. The number of cluster
heads is based on a suggested percentage of cluster heads for
the network. Normal figure is 5% of the total number of
nodes. In view of mobility, the figure can go high depending
on the spatial dependency factor and the speed with which the
nodes move. A probable figure could be of the order of 5 -15
% of the total number of nodes.
D. Steady State phase in LEACH-ME
In the set-up phase of LEACH, the clusters are organized
and cluster heads are elected. Configuration formed in the set-
up phase is used to transfer monitored data to the base station
during the steady state phase. Because of that, it can not
accommodate the alteration of cluster by mobile sensor nodes
Slot
0
Slot
1
Slot
2
¦¦¦
Slot
N-1
ACTIVE
Authorized licensed use limited to: COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY. Downloaded on February 7, 2009 at 06:47 from IEEE Xplore. Restrictions apply.Page 4
during the steady-state phase. It is possible to resolve this
problem by a simple and traditional method that adds
membership declaration of mobile nodes to typical LEACH
protocol. In LEACH-M scheme, the non-cluster head nodes
instead of sending the data to the cluster head in their allotted
time slot in the TDMA schedule wait for a request
(REQ_Data) from the cluster head to send data.
In the vicinity of mobility it may happen that the REQ_Data
sent to a particular node by the cluster head is not received by
the node, since it is moved to a new location which is not in
the radio range of its current cluster head. After sending the
REQ_Data, if no response is obtained from the node before
the frame slot allotted for that node, the node will be marked
as mobile-suspect. If the same thing repeats for the next time
slot allotted for the same node, then the suspect node is
declared as mobile and the frame slot for that node is deleted
from the TDMA schedule.
On the other hand, if the node doesnâ„¢t receive any
REQ_Data from the cluster head when it is awake, it marks
itself as suspect of non-member of cluster. During the next
frame slot allotted to this node, if the same thing repeats, then
it takes the decision that it is not a member of the cluster.
Figure.2 Message sequences for cluster join of a mobile node
Once a node becomes a non-member in any of the cluster, it
looks for a cluster to join by sending a broadcast JOIN_REQ.
The cluster head hearing the JOIN_REQ allots a time slot in
its TDMA schedule and broadcasts it to all the node members
including the new member. Upon receiving the new TDMA
schedule the mobile node now becomes part of the cluster and
uses the new cluster schedule. The sequence of messages are
shown in Figure 2
III. RADIO MODEL FOR LEACH-ME
The first order radio model [5] used in LEACH and
LEACH-M is used for LEACH-ME, where radio dissipates
bit
nanoJoule
E
elec
/
50
=
to drive the transmitter and the
transmit-amplifier dissipates
2
/
/
100
m
bit
picoJoule
elec
=
e
. It is
assumed that radio can be turned on or off as and when
required, to save energy. Also the radio spends the minimum
energy required to reach the destination. The transmission cost
of LEACH-M is different from LEACH-ME because of the
additional effort to calculate the remoteness at the ACTIVE
slot.
Assuming k-bit message is sent on normal and k
active
is sent
on ACTIVE slot, transmission and receiving cost for a
distance of d for k-bit can be calculated as follows
Transmitting cost for LEACH-M:
)
,
(
)
(
)
,
(
d
k
E
k
E
d
k
E
amp
Tx
elec
Tx
Tx
-
-
+
=
(2)
2
*
*
*
d
k
k
E
elec
elec
e
+
=
(3)
For N nodes in the cluster, the total transmission cost per
TDMA cycle is:
2
1
*
*
*
*)
1
(
)
,
(
i
N
i
elec
elec
cluster
Tx
d
k
k
E
N
d
k
E
?
=
-
+
-
=
e
(4)
Transmitting cost of LEACH-ME per TDMA cycle is
transmitting cost of LEACH-M per TDMA cycle added with
active slot cost.
?
=
-
+
-
=
N
i
i
elec
elec
cluster
Tx
d
k
k
E
N
d
k
E
1
2
*
*
*
*)
1
(
)
,
(
e
?
=
+
-
+
N
i
i
active
elec
active
elec
d
k
k
E
N
1
2
*
*
*
2
*
*)
1
(2
e
(5)
In active slots the k-active bits need to be sent twice, one
for ID transmission and other for remoteness transmission.
The extra energy dissipated is in the ACTIVE slots to achieve
awareness of the remoteness to elect cluster head. The number
of bits in active frame is assumed to be less than that of the
data frame bits.
Reception cost will be same in LEACH-M and LEACH-
ME
Reception cost:
)
(
)
(
k
E
k
E
elec
Rx
Rx
-
=
(6)
k
E
k
E
elec
Rx
*
)
( =
(7)
The radio channel is assumed to be symmetric for given
signal to noise ratio.
IV. E
XPERIMENTAL
R
ESULTS
To evaluate the performance of LEACH-ME, we simulated
LEACH-M and LEACH-ME using 100 random nodes with
topology for a 100m x 100m network region. The base Station
is located at (50, 50) in the center of the 100m x 100m field.
We simulated the wireless sensor network to get the number
of data packets that are successful in reaching the base station.
The simulation is run by changing the mobility factor for
LEACH-M and LEACH-ME. We also simulated the amount
of energy dissipations for the data packets transmitted.
Figure 3 shows the average successful communication rate
for various mobility factors. At low mobility, the performance
of LEACH-M and LEACH-ME are comparable. But as the
mobility increases, there is a definite improvement in average
successful communication rate in LEACH-ME. As is obvious
Authorized licensed use limited to: COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY. Downloaded on February 7, 2009 at 06:47 from IEEE Xplore. Restrictions apply.Page 5
from figure 4, at the mobility factor of 4.0 the successful
communication rate is 16%, which is better than the LEACH-
M. On the other hand the amount of energy dissipation as well
as computational overhead increases as mobility increases.
This is obvious from figure 5 and figure 6. At very high
mobility (mobility factor 4 and above), the overhead of
LEACH-ME is 22% more than that of the overhead of
LEACH-M
Figure 3 Average successful Communications of Leach-M and LEACH-ME
for various mobility factors
Figure 4 Performance of LEACH-ME over LEACH-M protocol.
Figure 5 Computational overhead by the LEACH-M and LEACH-ME
protocol against the mobility factor
Figure 6 Energy overhead of LEACH-M and LEACH-ME protocols against
the mobility factor
V. C
ONCLUSION
In this paper, we describe how the LEACH protocol can be
enhanced to handle mobility modulation. The paper makes use
of the proposals in LEACH-M protocol where nodes isolated
due to mobility from the cluster are reconnected to a new
cluster through appropriate mechanism. The proposed
LEACH-ME protocol follows the same reconnection
mechanism for the isolated node. It uses the concept of
remoteness for electing the cluster head.
The simulation experiment shows that the proposed
enhanced protocol outperforms LEACH-M in average
successful communication rate by a reasonable margin, at very
high mobility. It is also clear that to achieve the level of extra
performance, energy dissipation needs to be sacrificed at a
tolerable level.
A
CKNOWLEDGMENT
The authors would like to thank Mr. A.V. Sahadevan for his
contribution to the original proposal that led to this paper and
for his initial comments on the manuscript.
Authorized licensed use limited to: COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY. Downloaded on February 7, 2009 at 06:47 from IEEE Xplore. Restrictions apply.Page 6
R
EFERENCES
[1] F Akylidiz, W. Su, Y Sankarasubramanyam, and E. Cayirci, Wireless
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
[3] D. Ganesan, B. Krishnamurthy, A.Woo, D. Culler, D. Estrin, and S.
Wicker. An empirical study of epidemic algorithms in large scale
multihop wireless networks, Technical Report IntelIRP-TR-02-003,
Intel Research, March 2002.
[4] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly resilient,
energy efficient multi path routing in wireless sensor networks, MC2R,
1(2), 2002.
[5]
W.
Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-
efficient routing protocols for wireless microsensor networks, in Proc.
33rd Hawaii Int. Conf. System Sciences (HICSS), Maui, HI, 2000.
[6] Do-Seong Kim, Yeong-Jee Chung, Self-Organization Routing Protocol
Supporting Mobile Nodes for Wireless Sensor Network, Proceedings of
the First International Multi-Symposiums on Computer and
Computational Sciences (IMSCCS'06), 2006
[7] 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.
[8] Liliana M. Arboleda C.and Nidal Nasser, Cluster-based Routing
Protocol for Mobile Sensor Networks, QShineâ„¢06, The Third
International Conference on Quality of Service in Heterogeneous
Wired/Wireless Networks, August 7“9, 2006, Waterloo, Ontario,
Canada © 2006 ACM 1-59593-472-3/06/08
[9] B. J. Kwak, N. O. Song, and L. E. Miller, "A Canonical Measure of
Mobility for Mobile Ad Hoc Networks",Proceedings IEEE MILCOM
2003, Boston, 13-16 October 200
