第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
SEP协议原文.pdf
1
SEP: A Stable Election Protocol for clustered
heterogeneous wireless sensor networks
GEORGIOS SMARAGDAKIS
IBRAHIM MATTA
AZER BESTAVROS
Computer Science Department
Boston University
fgsmaragd, matta, bestg@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
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].
that
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
1We 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.
Perhaps the most important issue is that heterogeneity of
nodes, in terms of their energy, is simply a result of the
network operation as it evolves. For example, nodes could,
over time, expend different amounts of energy due to the radio
communication characteristics, random events such as short-
term link failures or morphological characteristics of the field
(e.g. uneven terrain.)
Our Contribution: In this paper we assume that the sink is
not energy limited (at least in comparison with the energy
of other sensor nodes) and that the coordinates of the sink
and the dimensions of the field are known. We also assume
that the nodes are uniformly distributed over the field and
they are not mobile. Under this model, we propose a new
protocol, we call SEP, for electing cluster heads in a distributed
fashion in two-level hierarchical wireless sensor networks.
Unlike prior work (reviewed throughout
the paper and in
Section VII), SEP is heterogeneous-aware, in the sense that
election probabilities are weighted by the initial energy of
a node relative to that of other nodes in the network. This
prolongs 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. We show by simulation that SEP provides longer
stability period and higher average throughput than current
clustering heterogeneous-oblivious protocols. We also study
the sensitivity of our SEP protocol to heterogeneity parameters
capturing energy imbalance in the network. We show that SEP
is more resilient than LEACH in judiciously consuming the
extra energy of advanced (more powerful) nodes—SEP yields
longer stability period for higher values of extra energy.
Paper Organization: The rest of the paper is organized
as follows. Section II provides the model of our setting.
Section III defines our performance measures. In Section IV
we address the problem of heterogeneity in clustered wireless
sensor networks, and in Section V we provide our solution
to the problem. Section VI presents simulation results. We
review related work in Section VII. Section VIII concludes
with directions for future work.
II. HETEROGENEOUS WSN MODEL
In this section we describe our model of a wireless sensor
network with nodes heterogeneous in their initial amount of
energy. We particularly present the setting, the energy model,
and how the optimal number of clusters can be computed.
Let us assume the case where a percentage of the population
of sensor nodes is equipped with more energy resources than
the rest of the nodes. Let be the fraction of the total number
of nodes , which are equipped with times more energy than
the others. We refer to these powerful nodes as advaced
nodes, and the rest 1 as a nodes. We assume
that all nodes are distributed uniformly over the sensor field.
A. Clustering Hierarchy
We consider a sensor network that is hierarchically clus-
tered. The LEACH (Low Energy Adaptive Clustering Hier-
archy) protocol [3] maintains such clustering hierarchy. In
LEACH, the clusters are re-established in each “round.” New
2
cluster heads are elected in each round and as a result the
load is well distributed and balanced among the nodes of the
network. Moreover each node transmits to the closest cluster
head so as to split the communication cost to the sink (which
is tens of times greater than the processing and operation cost.)
Only the cluster head has to report to the sink and may expend
a large amount of energy, but this happens periodically for
each node. In LEACH there is an optimal percentage
(determined a priori) of nodes that has to become cluster heads
in each round assuming uniform distribution of nodes in space
[3], [4], [6], [7].
If the nodes are homogeneous, which means that all the
nodes in the field have the same initial energy, the LEACH
protocol guarantees that everyone of them will become a
rounds. Throughout this
cluster head exactly once every
, as epoch of the
paper we refer to this number of rounds,
clustered sensor network.
1
1
Initially each node can become a cluster head with a
probability . On average, nodes must become
cluster heads per round per epoch. Nodes that are elected to
be cluster heads in the current round can no longer become
cluster heads in the same epoch. The non-elected nodes belong
to the set G and in order to maintain a steady number of cluster
heads per round, the probability of nodes 2 G to become a
cluster head increases after each round in the same epoch. The
decision is made at the beginning of each round by each node
2 G independently choosing a random number in [0,1]. If
the random number is less than a threshold T then the node
becomes a cluster head in the current round. The threshold is
set as:
T =
1 d
0
1
if 2 G
otherwise
(1)
where is the current round number (starting from round
0.) The election probability of nodes 2 G to become cluster
heads increases in each round in the same epoch and becomes
equal to 1 in the last round of the epoch. Note that by round
we define a time interval where all cluster members have to
transmit to their cluster head once. We show in this paper
how the election process of cluster heads should be adapted
appropriately to deal with heterogeneous nodes, which means
that not all the nodes in the field have the same initial energy.
B. Optimal Clustering
Previous work have studied either by simulation [3], [4] or
analytically [6], [7] the optimal probability of a node being
elected as a cluster head as a function of spatial density when
nodes are uniformly distributed over the sensor field. This clus-
tering is optimal in the sense that energy consumption is well
distributed over all sensors and the total energy consumption
is minimum. Such optimal clustering highly depends on the
energy model we use. For the purpose of this study we use
similar energy model and analysis as proposed in [4].
According to the radio energy dissipation model illustrated
in Figure 1, in order to achieve an acceptable Signal-to-Noise
Ratio (SNR) in transmitting an bit message over a distance
d
E (L,d)
Tx
L bit
packet
Transmit
Electronics
Eelec
L
Tx Amplifier
ν
Ldε
E (L)
Rx
Receive
Electronics
EelecL
L bit
packet
Fig. 1. Radio Energy Dissipation Model.
d, the energy expended by the radio is given by:
ET x; d = Eeec f d2
Eeec d4
if d d0
if d > d0
where Eeec is the energy dissipated per bit
to run the
transmitter or the receiver circuit, f and depend on
the transmitter amplifier model we use, and d is the distance
between the sender and the receiver. By equating the two
. To receive an
expressions at d = d0, we have d0 = f
bit message the radio expends ERx = Eeec.
Assume an area A = square meters over which
nodes are uniformly distributed. For simplicity, assume the
sink is located in the center of the field, and that the distance
of any node to the sink or its cluster head is d0. Thus, the
energy dissipated in the cluster head node during a round is
given by the following formula:
k
EC =
k EDA Eeec f d2
1 Eeec
BS
where k is the number of clusters, EDA is the processing
(data aggregation) cost of a bit per report to the sink, and
dBS is the average distance between the cluster head and
the sink. The energy used in a non-cluster head node is equal
to:
EC = Eeec f d2
C
where dC is the average distance between a cluster
member and its cluster head. Assuming that the nodes are
uniformly distributed, it can be shown that:
d2
C =Z x=xax
x=0
Z y=yax
y=0
x2 y2x; ydxdy =
2
2k
where x; y is the node distribution.
The energy dissipated in a cluster per round is given by:
Ec e EC
k EC
The total energy dissipated in the network is equal to:
E = 2Eeec EDA f kd2
By differentiating E with respect
to k and equating
to zero, the optimal number of constructed clusters can be
found:2
C
BS d2
k =
2
dBS
=
2
2
0:765
(2)
because the average distance from a cluster head to the sink
is given by [7]:
dBS =ZAx2 y2 1
A
dA = 0:765
2
2It is interesting to notice that the optimal number of clusters is independent
of the dimensions of the field and only depends on the number of nodes .
If the distance of a significant percentage of nodes to the
sink is greater than d0 then, following the same analysis [4]
we obtain:
3
k =
2 f
d2
BS
(3)
The optimal probability of a node to become a cluster head,
, can be computed as follows:
=
k
(4)
The optimal construction of clusters (which is equivalent to
the setting of the optimal probability for a node to become a
cluster head) is very important. In [3], the authors showed
that if the clusters are not constructed in an optimal way,
the total consumed energy of the sensor network per round
is increased exponentially either when the number of clusters
that are created is greater or especially when the number of
the constructed clusters is less than the optimal number of
clusters. Our simulation results confirm this observation in our
case where the sink is located in the center of the sensor field.
III. PERFORMANCE MEASURES
We define here the measures we use in this paper to evaluate
the performance of clustering protocols.
Stability Period: is the time interval from the start of
network operation until the death of the first sensor node.
We also refer to this period as “stable region.”
Instability Period: is the time interval from the death of
the first node until the death of the last sensor node. We
also refer to this period as “unstable region.”
Network lifetime: is the time interval from the start of
operation (of the sensor network) until the death of the
last alive node.
Number of cluster heads per round: This instantaneous
measure reflects the number of nodes which would send
directly to the sink information aggregated from their
cluster members.
Number of alive (total, advanced and normal) nodes
per round: This instantaneous measure reflects the total
number of nodes and that of each type that have not yet
expended all of their energy.
Throughput: We measure the total rate of data sent over
the network, the rate of data sent from cluster heads to
the sink as well as the rate of data sent from the nodes
to their cluster heads.
Clearly, the larger the stable region and the smaller the
unstable region are, the better the reliability of the clustering
process of the sensor network is. On the other hand, there is
a tradeoff between reliability and the lifetime of the system.
Until
the death of the last node we can still have some
feedback about the sensor field even though this feedback may
not be reliable. The unreliability of the feedback stems from
the fact that there is no guarantee that there is at least one
cluster head per round during the last rounds of the operation.
In our model, the absence of a cluster head in an area prevents
any reporting about that area to the sink. The throughput
measure captures the rate of such data reporting to the sink.
Advanced Node
SINK
Normal Node
4
would die in the homogeneous case wherein each node is
equipped with the same energy as that of a normal node
in the heterogeneous case. Furthermore, we expect the first
dead node to be a normal node. We also expect that in the
following rounds the probability of a normal node to die is
greater than the probability of an advanced node to die. During
the last rounds only advanced nodes would be alive. Our
expectations are confirmed by simulation results in Section
VI. We next demonstrate how such heterogeneous-oblivious
clustering protocol fails to maintain the stability of the system,
especially when nodes are heterogeneous. This motivates our
proposed SEP protocol presented in Section V.
10
20
30
40
50
60
70
80
90
100
A. Instability of Heterogeneous-oblivious Protocols
In this section we discuss the instability of heterogeneous-
oblivious protocols, such as LEACH, once some nodes die. In
this case, the process of optimal construction of clusters fails
since the spatial density deviates from the assumed uniform
distribution of nodes over the sensor field.
Let us assume a heterogeneous ( = 0:2; = 1) sensor
network in an 100 100 sensor field, as shown in Fig-
ure 2(top). For this setting we can compute from Equation (2)
the optimal number of clusters per round, k = 10. We
denote with Æ a normal node, with an advanced node,
with a dead node, with a cluster head, and with the
sink. As long as all the nodes are alive, the nodes that are
included in the same Voronoi cell will report to the cluster
head of this cell; see Figure 2(middle).
At some point
in time the first node dies; see Fig-
ure 2(bottom). After that point
the population of sensors
decreases as nodes die randomly. The population reduction
introduces instability in the sensor network and the cluster
head election process becomes unreliable. This is because
the value of is optimal only when the population of
the network is constant and equal to the initial population
(). When the population of the nodes starts decreasing, the
number of elected cluster heads per round becomes unstable
(lower than intended) and as a result there is no guarantee that
a constant number of cluster heads (equal to ) will be
elected per round per epoch. Moreover because there are less
alive nodes, the sampling (sensing) of the field is over less
nodes than intended to be.
The only guarantee is that there will be at least one cluster
head per epoch (cf. Equation 1). As a result in the worst case,
in only one round per epoch all alive nodes will report to the
sink.3 The impact (quality) of these reports highly depends
on the application. For some applications even this minimal
reporting is a valuable feedback, for others it is not. Clearly
minimal reporting translates to significant under-utilization of
the resources and the bandwidth of the application.
LEACH guarantees that in the homogeneous case the unsta-
ble region will be short. After the death of the first node, all the
remaining nodes are expected to die on average within a small
number of rounds as a consequence of the uniformly remaining
energy due to the well distributed energy consumption. Even
3This assumes every alive node is within communication range of a cluster
head.
100
90
80
70
60
50
40
30
20
10
0
0
100
90
80
70
60
50
40
30
20
10
0
0
100
90
80
70
60
50
40
30
20
10
0
0
10
20
30
40
50
60
70
80
90
100
10
20
30
40
50
60
70
80
90
100
(top) A wireless sensor network; (middle) A snapshot of the
Fig. 2.
network when all the nodes are alive; (bottom) A snapshot of the
network when some nodes are dead.
IV. HETEROGENEOUS-OBLIVIOUS PROTOCOLS
The original version of LEACH does not take into con-
sideration the heterogeneity of nodes in terms of their initial
energy, and as a result the consumption of energy resources
of the sensor network is not optimized in the presence of such
heterogeneity. The reason is that LEACH depends only on the
spatial density of the sensor network.
Using LEACH in the presence of heterogeneity, and assum-
ing both normal and advanced nodes are uniformly distributed
in space, we expect
the first node dies on average
in a round that is close to the round when the first node
that
when the system operates in the unstable region, if the spatial
density of the sensor network is large, the probability that a
large number of nodes be elected as cluster heads is significant
for a significant part of the unstable region (as long as the
population of the nodes has not decreased significantly.) In
this case, even though the system is unstable in this region,
we still have a relatively reliable clustering (sensing) process.
The same can be noticed even if the spatial density is low but
the is large. On the other hand, LEACH in the presence of
node heterogeneity yields a large unstable region. The reason
is that although all advanced nodes are left equipped with
almost the same energy, the cluster head election process is
unstable and as a result, most of the time no cluster head is
elected and these advanced nodes are idle.
In the next section, we introduce our new heterogeneous-
aware SEP protocol whose goal is to increase the stable region
and as a result decrease the unstable region and improve the
quality of the feedback of wireless clustered sensor networks,
in the presence of heterogeneous nodes.
V. OUR SEP PROTOCOL
In this section we describe SEP, which improves the stable
region of the clustering hierarchy process using the charac-
teristic parameters of heterogeneity, namely the fraction of
advanced nodes () and the additional energy factor between
advanced and normal nodes ().
In order to prolong the stable region, SEP attempts to
maintain the constraint of well balanced energy consumption.
Intuitively, advanced nodes have to become cluster heads
more often than the normal nodes, which is equivalent to a
fairness constraint on energy consumption. Note that the new
heterogeneous setting (with advanced and normal nodes) has
no effect on the spatial density of the network so the a priori
setting of , from Equation (4), does not change. On the
other hand, the total energy of the system changes. Suppose
that E is the initial energy of each normal sensor. The energy
of each advanced node is then E 1 . The total (initial)
energy of the new heterogeneous setting is equal to:
1 E E 1 = E 1
So, the total energy of the system is increased by a factor of
1 . The first improvement to the existing LEACH is to
increase the epoch of the sensor network in proportion to the
energy increment. In order to optimize the stable region of the
system, the new epoch must become equal to 1
1
because the system has times more energy and virtually
more nodes (with the same energy as the normal nodes.)
We can now increase the stable region of the sensor network
by 1 times, if (i) each normal node becomes a cluster
head once every 1
1 rounds per epoch; (ii) each
advanced node becomes a cluster head exactly 1 times
every 1
1 rounds per epoch; and (iii) the average
number of cluster heads per round per epoch is equal to
(since the spatial density does not change.) Constraint (ii)
is very strict—If at the end of each epoch the number of times
that an advanced sensor has become a cluster head is not equal
to 1 then the energy is not well distributed and the average
5
number of alive nodes per round
LEACH m=0.2 α=3
solution without Sub−Epochs m=0.2 α=3
SEP m=0.2 α=3
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
s
e
d
o
n
e
v
i
l
a
f
o
r
e
b
m
u
n
100
90
80
70
60
50
40
30
20
10
0
0
Fig. 3. Performance of the na¨ıve solution.
number of cluster heads per round per epoch will be less than
. This problem can be reduced to a problem of optimal
threshold T setting (cf. Equation 1), with the constraint that
each node has to become a cluster head as many times as its
initial energy divided by the energy of a normal node.
A. The Problem of Maintaining Well Distributed Energy
Consumption Constraints in the Stable Period
If the same threshold is set for both normal and advanced
nodes with the difference that each normal node 2 G becomes
a cluster head once every 1
1 rounds per epoch,
and each advanced node 2 G becomes a cluster head 1
times every 1
1 rounds per epoch, then there is no
guarantee that the number of cluster heads per round per epoch
will be . The reason is that there is a significant number
of cases where this number can not be maintained per round
per epoch with probability 1. A worst-case scenario could
be the following. Suppose that every normal node becomes
1 rounds of
a cluster head once within the first
the epoch. In order to maintain the well distributed energy
consumption constraint, all the remaining nodes, which are
advanced nodes, have to become cluster heads with probability
1 rounds of the epoch. But the
1 for the next
threshold T is increasing with the number of rounds within
each epoch and becomes equal to 1 only in the last round
(when all the remaining nodes become cluster heads with
probability 1.) So the above constraint of cluster heads
in each round is violated. Figure 3 shows that the performance
of this na¨ıve solution is very close to that of LEACH. In the
next subsection, we introduce SEP where the extra energy of
advanced nodes is forced to be expended within subepochs of
the original epoch.
1
1
B. Guaranteed Well Distributed Energy Consumption
Constraints in the Stable Period
In this section we propose a solution, we call SEP (Stable
Election Protocol), which is based on the initial energy of
the nodes. This solution is more applicable compared to any
solution which assumes that each node knows the total energy
of the network and then adapts its election probability to
become a cluster head according to its remaining energy [8].
Our approach is to assign a weight to the optimal probability
. This weight must be equal to the initial energy of each
node divided by the initial energy of the normal node. Let us
define as the weighted election probability for normal
nodes, and adv the weighted election probability for the
advanced nodes.
Virtually there are 1 nodes with energy equal
to the initial energy of a normal node. In order to maintain the
minimum energy consumption in each round within an epoch,
the average number of cluster heads per round per epoch must
be constant and equal to . In the heterogeneous scenario
the average number of cluster heads per round per epoch is
equal to 1 (because each virtual node has
the initial energy of a normal node.) The weighed probabilities
for normal and advanced nodes are, respectively:
=
1
adv =
1
1
In Equation (1), we replace by the weighted probabil-
ities to obtain the threshold that is used to elect the cluster
head in each round. We define as T the threshold for
normal nodes, and T adv the threshold for advanced nodes.
Thus, for normal nodes, we have:
T =
1 d
0
1
if 2 G0
otherwise
(5)
where is the current round, G0
is the set of normal
nodes that have not become cluster heads within the last
rounds of the epoch, and T is the threshold applied to
a population of 1 (normal) nodes. This guarantees
that each normal node will become a cluster head exactly once
every 1
1 rounds per epoch, and that the average
number of cluster heads that are normal nodes per round per
epoch is equal to 1 .
1
Similarly, for advanced nodes, we have:
T adv =
adv
1adv d
0
1
adv
if adv 2 G00
otherwise
(6)
1
adv
where G00 is the set of advanced nodes that have not become
rounds of the epoch, and
cluster heads within the last
T adv is the threshold applied to a population of
(advanced) nodes. This guarantees that each advanced node
1
will become a cluster head exactly once every
1
rounds. Let us define this period as sub-epoch. It is clear
that each epoch (let us refer to this epoch as “heterogeneous
epoch” in our heterogeneous setting) has 1 sub-epochs
and as a result, each advanced node becomes a cluster head
exactly 1 times within a heterogeneous epoch. The average
number of cluster heads that are advanced nodes per round per
heterogeneous epoch (and sub-epoch) is equal to adv.
1
x=0 x=1 x=2
x=3
x=4
x=5
epoch
x=6
x=7
x=8
x=9
x’=0
x’=2
x’=1
sub-epoch
x’=3
x’=4
x’=7 x’=8
x’=5
x’=6
sub-epoch
x’=10
x’=9
sub-epoch
heterogeneous epoch
x’=11
x’=12
x’=14
x’=13
sub-epoch
6
x’=15
Fig. 4. A numerical example for a heterogeneous network with
parameters = 0:2 and = 3, and = 0:1. We define
, where is the
x = d
current round.
, and x0 = d
1
1
Thus the average total number of cluster heads per round
per heterogeneous epoch is equal to:
1 adv =
which is the desired number of cluster heads per round
per epoch. We next discuss the implementation of our SEP
protocol.
C. SEP Deployment
As mentioned in Section I, the heterogeneity in the energy
of nodes could result from normal network operation. For
example, nodes could, over time, expend different amounts of
energy due to the radio communication characteristics, random
events such as short-term link failures or morphological char-
acteristics of the field (e.g. uneven terrain.) To deal with such
heterogeneity, our SEP protocol could be triggered whenever
a certain energy threshold is exceeded at one or more nodes.
Non-cluster heads could periodically attach their remaining
energy to the messages they send during the handshaking
process with their cluster heads, and the cluster heads could
send this information to the sink. The sink can check the
heterogeneity in the field by examining whether one or a
certain number of nodes reach this energy threshold. If so,
then the sink could broadcast to cluster heads in that round
the values for and adv, in turn cluster heads unicast
these values to nodes in their clusters according to the energy
each one has attached earlier during the handshaking process.
If some of the nodes already in use have not been pro-
grammed with this capability, a reliable transport protocol,
such as the one proposed in [9], could be used to program such
sensors. Evaluating the overhead of such SEP deployment is
a subject of our on-going work.
D. Numerical Example
Assume that 20 of the nodes are advanced nodes ( =
0:2) and equipped with 300 more energy that other (normal)
nodes ( = 3). Consider a population of a sensor network in
an 100 100 field of 100 nodes. The for this setting
is approximately equal to 0:104325 (using Equation 4). For
simplicity let us set = 0:1. This means that on average,
10 nodes must become cluster heads per round.
If we consider a homogeneous scenario where each node
to the energy of a normal node,
has initial energy equal
= 10 rounds. In
then the epoch would be equal to
our heterogeneous case, the extended heterogeneous epoch is
equal to 1
= 16 rounds, and each sub-epoch is
= 1
1
s
e
d
o
n
e
v
i
l
a
f
o
r
e
b
m
u
n
s
e
d
o
n
e
v
i
l
a
f
o
r
e
b
m
u
n
100
90
80
70
60
50
40
30
20
10
0
0
100
90
80
70
60
50
40
30
20
10
0
0
number of alive nodes per round
LEACH m=0 α=0
LEACH m=0.1 α=2
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
number of alive nodes per round
LEACH m=0 α=0
LEACH m=0.2 α=1
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
Fig. 5. Number of alive nodes using LEACH in the presence of
heterogeneity: (top) = 0:1 and = 2, and (bottom) = 0:2 and
= 1.
1
1
equal to
1 = 4 rounds, as illustrated in Figure 4.
On average, 1 = 5 normal nodes become
cluster heads per round, and each one of them becomes a
cluster head exactly once within 16 rounds (one heterogeneous
epoch.) Furthermore, on average, adv = 5 advanced
nodes become cluster heads per round. The total number of
sensors that become cluster heads (both normal and advanced)
is equal to 10, which is the desired number. Moreover each
advanced sensor becomes a cluster head exactly once every
sub-epoch and becomes a cluster head 1 times within
a heterogeneous epoch, i.e. each advanced node becomes a
cluster head 4 times within a heterogeneous epoch.
VI. SIMULATION RESULTS
We simulate a clustered wireless sensor network in a
field with dimensions 100 100. The total number of
sensors = 100. The nodes, both normal and advanced, are
randomly (uniformly) distributed over the field. This means
that the horizontal and vertical coordinates of each sensor are
randomly selected between 0 and the maximum value of the
dimension. The sink is in the center and so, the maximum
distance of any node from the sink is approximately 70 (the
setting of Figure 2.) The initial energy of a normal node is set
to E0 = 0:5 e—Although this value is arbitrary for the
7
eai
Transmitter/Receiver Electronics
Data Aggregation
Transmit Amplifier
if dBS d0
Transmit Amplifier
if dBS d0
Eegy Diiaed
Eeec = 50=bi
EDA = 5=bi=e
f = 10=bi=2
= 0:0013=bi=4
RADIO CHARACTERISTICS USED IN OUR SIMULATIONS.
TABLE I
purpose of this study, this does not affect the behavior of our
SEP protocol. The radio characteristics used in our simulations
are summarized in Table I. The size of the message that nodes
send to their cluster heads as well as the size of the (aggregate)
message that a cluster head sends to the sink is set to 4000
bits.
In the next subsections we simulate the heterogeneous-
oblivious LEACH and our SEP protocol, in the presence of
heterogeneity in the initial energy of nodes. We evaluate the
behavior of both protocols in terms of the performance mea-
sures defined in Section III. We also examine the sensitivity
of SEP to the degree of heterogeneity in the network. We first
summarize our general observations:
In a wireless sensor network of heterogeneous nodes,
LEACH goes to unstable operation sooner as it is very
sensitive to such heterogeneity.
Our SEP protocol successfully extends the stable region
by being aware of heterogeneity through assigning prob-
abilities of cluster-head election weighted by the relative
initial energy of nodes.
Due to extended stability,
the throughput of SEP is
also higher than that of current (heterogeneous-oblivious)
clustering protocols.
The performance of SEP is observed to be close to that
of an ideal upper bound obtained by distributing the
additional energy of advanced nodes uniformly over all
nodes in the sensor field.
SEP is more resilient than LEACH in judiciously con-
suming the extra energy of advanced nodes—SEP yields
longer stability region for higher values of extra energy.
A. Results for LEACH
The results of our LEACH simulations are shown in Fig-
ure 5(top) for = 0:1 and = 2. We observe that
LEACH takes some advantage of the presence of heterogeneity
(advanced nodes), as the first node dies after a significantly
higher number of rounds (i.e. longer stability period) compared
to the homogeneous case ( = = 0). The lifetime of
the network is increased, but as we will show later this does
not mean that the nodes transmit (i.e. the throughput may be
low.) The reason is that after the death of a significant number
of nodes, the cluster head election process becomes unstable
and as a result less nodes become cluster heads. Even worse,
during the last rounds, there are only few rounds where more
than one cluster head are elected.4
4For both LEACH and SEP, the length of the stable region obtained from
independent simulation runs (i.e. starting from different random number seeds)
is pretty stable for the same values of and .
100
90
80
70
60
50
40
30
20
10
0
0
100
90
80
70
60
50
40
30
20
10
0
0
s
e
d
o
n
e
v
i
l
a
f
o
r
e
b
m
u
n
s
e
d
o
n
l
a
m
r
o
N
e
v
i
l
a
f
o
r
e
b
m
u
n
number of alive nodes per round
LEACH m=0 α=0
LEACH m=0.2 α=1
LEACH m=0.2 α=3
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
(a)
number of alive Normal nodes per round
LEACH m=0 α=0
LEACH m=0.2 α=1
LEACH m=0.2 α=3
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
h
c
o
p
e
r
e
p
d
n
u
o
r
r
e
p
s
d
a
e
h
r
e
t
s
u
c
f
l
o
r
e
b
m
u
n
e
g
a
r
e
v
a
s
e
d
o
n
d
e
c
n
a
v
d
A
e
v
i
l
a
f
o
r
e
b
m
u
n
10
9
8
7
6
5
4
3
2
1
0
0
20
18
16
14
12
10
8
6
4
2
0
0
8
average number of cluster heads per round per epoch
LEACH m=0 α=0
LEACH m=0.2 α=1
LEACH m=0.2 α=3
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
(b)
number of alive Advanced nodes per round
LEACH m=0 α=0
LEACH m=0.2 α=1
LEACH m=0.2 α=3
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
number of rounds
Fig. 6. LEACH behavior in the presence of heterogeneity: (a) Alive nodes per round; (b) Average number of cluster heads per round;
(c) Alive normal nodes per round; (d) Alive advanced nodes per round.
(c)
(d)
We repeat the same experiment, but now the heterogeneity
parameters are set to = 0:2 and = 1, however
remains constant. Our simulation results are shown in Figure
5(bottom). Although the length of the stability region (until the
first node dies) is pretty stable, LEACH takes more advantage
of the presence of heterogeneity manifested in a higher number
of advanced nodes.
In Figure 6, a detailed view of the behavior of LEACH
is illustrated, for different distributions of heterogeneity. In
Figure 6(a),
the number of alive nodes is shown for the
scenarios ( = 0:2; = 1) and ( = 0:2; = 3). LEACH
fails to take full advantage of the heterogeneity (extra energy)
as in both scenarios, the first node dies almost at the same
round. Moreover, the normal nodes die in both cases very fast
(Figure 6(c)) and as a result the sensing field becomes sparse
very fast. On the other hand, advanced nodes die in a very
slow fashion (Figure 6(d)), because they are not elected very
often as cluster heads after the death of the normal nodes (and
thus they do not transmit most of the time)—this is because
the election process for cluster heads has become unstable
and the number of cluster heads elected are less than the
optimal number. Furthermore, as shown in Figure 6(b), when
a significant number of normal nodes are dead the average
number of cluster heads per round per epoch is less than one.
This means that in most of the rounds there is no cluster head,
so in our model the remaining nodes can not report their values
to the sink.
B. Results for SEP
In this subsection we compare the performance of our SEP
protocol to 1) LEACH in the same heterogeneous setting, and
2) LEACH where the extra initial energy of advanced nodes
is uniformly distributed over all nodes in the sensor field. This
latter setting turns out to provide the highest throughput during
the unstable region—we henceforth refer to it as FAIR (for the
“fair” distribution of extra energy over existing nodes.)
Figure 7(top) shows results for the case of = 0:2 and
= 1. It is obvious that the stable region of SEP is extended
compared to that of LEACH (by 8%), even though the gain
is not very large. Moreover, the unstable region of SEP is
shorter than that of LEACH. What is more important to notice
is that the stable region of SEP is even greater than FAIR.
Furthermore the unstable region of SEP is slightly larger than
that of FAIR, and the number of alive nodes per round in SEP
is very close to that of FAIR.
Figure 7(bottom) shows results for the case of = 0:2 and
= 3. Now SEP takes full advantage of heterogeneity (extra
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
