1
SEP: A Stable Election Protocol for clustered
heterogeneous wireless sensor networks
GEORGIOS SMARAGDAKIS IBRAHIM MATTA AZER BESTAVROS
Computer Science Department
Boston University
f
gsmaragd, matta, best
g
@cs.bu.edu
Abstract— We study the impact of heterogeneity of nodes,
in terms of their energy, in wireless sensor networks that are
hierarchically clustered. In these networks some of the nodes
become cluster heads, aggregate the data of their cluster members
and transmit it to the sink. We assume that a percentage of the
population of sensor nodes is equipped with additional energy
resources—this is a source of heterogeneity which may result
from the initial setting or as the operation of the network evolves.
We also assume that the sensors are randomly (uniformly)
distributed and are not mobile, the coordinates of the sink and
the dimensions of the sensor field are known. We show that
the behavior of such sensor networks becomes very unstable
once the first node dies, especially in the presence of node
heterogeneity. Classical clustering protocols assume that all the
nodes are equipped with the same amount of energy and as a
result, they can not take full advantage of the presence of node
heterogeneity. We propose SEP, a heterogeneous-aware protocol
to prolong the time interval before the death of the first node (we
refer to as stability period), which is crucial for many applications
where the feedback from the sensor network must be reliable.
SEP is based on weighted election probabilities of each node
to become cluster head according to the remaining energy in
each node. We show by simulation that SEP always prolongs the
stability period compared to (and that the average throughput is
greater than) the one obtained using current clustering protocols.
We conclude by studying the sensitivity of our SEP protocol
to heterogeneity parameters capturing energy imbalance in the
network. We found that SEP yields longer stability region for
higher values of extra energy brought by more powerful nodes.
I. INTRODUCTION
Motivation: Wireless Sensor Networks are networks of tiny,
battery powered sensor nodes with limited on-board process-
ing, storage and radio capabilities [1]. Nodes sense and send
their reports toward a processing center which is called “sink.”
The design of protocols and applications for such networks
has to be energy aware in order to prolong the lifetime
of the network, because the replacement of the embedded
batteries is a very difficult process once these nodes have
been deployed. Classical approaches like Direct Transmission
and Minimum Transmission Energy [2] do not guarantee well
balanced distribution of the energy load among nodes of the
sensor network. Using Direct Transmission (DT), sensor nodes
transmit directly to the sink, as a result nodes that are far
away from the sink would die first [3]. On the other hand,
using Minimum Transmission Energy (MTE), data is routed
This work was supported in part by NSF grants ITR ANI-0205294, EIA-
0202067, ANI-0095988, and ANI-9986397.
over minimum-cost routes, where cost reflects the transmission
power expended. Under MTE, nodes that are near the sink act
as relays with higher probability than nodes that are far from
the sink. Thus nodes near the sink tend to die fast. Under both
DT and MTE, a part of the field will not be monitored for a
significant part of the lifetime of the network, and as a result
the sensing process of the field will be biased. A solution
proposed in [4], called LEACH, guarantees that the energy
load is well distributed by dynamically created clusters, using
cluster heads dynamically elected according to a priori optimal
probability. Cluster heads aggregate reports from their cluster
members before forwarding them to the sink. By rotating the
cluster-head role uniformly among all nodes, each node tends
to expend the same energy over time.
Most of the analytical results for LEACH-type schemes are
obtained assuming that the nodes of the sensor network are
equipped with the same amount of energy—this is the case
of homogeneous sensor networks. In this paper we study the
impact of heterogeneity in terms of node energy. We assume
that a percentage of the node population is equipped with
more energy than the rest of the nodes in the same network—
this is the case of heterogeneous sensor networks. We are
motivated by the fact that there are a lot of applications
that would highly benefit from understanding the impact of
such heterogeneity. One of these applications could be the
re-energization of sensor networks. As the lifetime of sensor
networks is limited there is a need to re-energize the sensor
network by adding more nodes. These nodes will be equipped
with more energy than the nodes that are already in use, which
creates heterogeneity in terms of node energy. Note that due
to practical/cost constraints it is not always possible to satisfy
the constraints for optimal distribution between different types
of nodes as proposed in [5].
There are also applications where the spatial density of sen-
sors is a constraint. Assuming that with the current technology
the cost of a sensor is tens of times greater than the cost of
embedded batteries, it will be valuable to examine whether the
lifetime of the network could be increased by simply distribut-
ing extra energy to some existing nodes without introducing
new nodes.
1
1
We also study the case of uniformly distributing such extra energy over
all nodes. In practice, however, it maybe difficult to achieve such uniform
distribution because extra energy could be expressed only in terms of discrete
battery units. Even if this is possible, we show in this paper that such fair
distribution of extra energy is not always beneficial.
