1 SEP:A Stable Election Protocol for clustered heterogeneous wireless sensor networks
G EORGIOS S MARAGDAKIS I BRAHIM M ATTA A ZER B ESTAVROS
Computer Science Department
Boston University
gsmaragd,matta,best@https://www.doczj.com/doc/b48548025.html,
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?eld are known.We show that the behavior of such sensor networks becomes very unstable once the?rst 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?rst 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.I NTRODUCTION
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 dif?cult 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 https://www.doczj.com/doc/b48548025.html,ing Direct Transmission(DT),sensor nodes transmit directly to the sink,as a result nodes that are far away from the sink would die?rst[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 re?ects 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?eld will not be monitored for a signi?cant part of the lifetime of the network,and as a result the sensing process of the?eld 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 bene?t 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
1We also study the case of uniformly distributing such extra energy over all nodes.In practice,however,it maybe dif?cult 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 bene?cial.
2
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?eld (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?eld are known.We also assume that the nodes are uniformly distributed over the?eld 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?rst 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 de?nes 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.H ETEROGENEOUS WSN M ODEL
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
nodes,and the rest as nodes.We assume that all nodes are distributed uniformly over the sensor?eld.
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 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?eld have the same initial energy,the LEACH
protocol guarantees that everyone of them will become a
cluster head exactly once every rounds.Throughout this paper we refer to this number of rounds,,as epoch of the clustered sensor network.
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 and in order to maintain a steady number of cluster
heads per round,the probability of nodes 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 independently choosing a random number in[0,1].If the random number is less than a threshold then the node
becomes a cluster head in the current round.The threshold is
set as:
if
otherwise
(1)
where is the current round number(starting from round 0.)The election probability of nodes to become cluster heads increases in each round in the same epoch and becomes equal to in the last round of the epoch.Note that by round we de?ne 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?eld 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?eld.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 Figure1,in order to achieve an acceptable Signal-to-Noise Ratio(SNR)in transmitting an bit message over a distance
3
Fig.1.Radio Energy Dissipation Model.
,the energy expended by the radio is given by:
if
if
where is the energy dissipated per bit to run the
transmitter or the receiver circuit,and depend on
the transmitter ampli?er model we use,and is the distance
between the sender and the receiver.By equating the two expressions at,we have.To receive an bit message the radio expends. Assume an area square meters over which nodes are uniformly distributed.For simplicity,assume the sink is located in the center of the?eld,and that the distance
of any node to the sink or its cluster head is.Thus,the
energy dissipated in the cluster head node during a round is
given by the following formula:
where is the number of clusters,is the processing
(data aggregation)cost of a bit per report to the sink,and
is the average distance between the cluster head and
the sink.The energy used in a non-cluster head node is equal
to:
where is the average distance between a cluster
member and its cluster head.Assuming that the nodes are
uniformly distributed,it can be shown that:
where is the node distribution.
The energy dissipated in a cluster per round is given by: The total energy dissipated in the network is equal to:
By differentiating with respect to and equating
to zero,the optimal number of constructed clusters can be
found:2
(2)
because the average distance from a cluster head to the sink is given by[7]:
2It is interesting to notice that the optimal number of clusters is independent of the dimensions of the?eld and only depends on the number of nodes.
If the distance of a signi?cant percentage of nodes to the sink is greater than then,following the same analysis[4] we obtain:
(3) The optimal probability of a node to become a cluster head, ,can be computed as follows:
(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 con?rm this observation in our case where the sink is located in the center of the sensor?eld.
III.P ERFORMANCE M EASURES
We de?ne 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?rst sensor node.
We also refer to this period as“stable region.”
Instability Period:is the time interval from the death of the?rst 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 re?ects 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 re?ects 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?eld 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.
4
network when all the nodes are alive;(bottom)A snapshot of the network when some nodes are dead.
IV.H ETEROGENEOUS-OBLIVIOUS P ROTOCOLS
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 that the?rst node dies on average in a round that is close to the round when the?rst node 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?rst
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 con?rmed 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.
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?eld.
Let us assume a heterogeneous()sensor
network in an sensor?eld,as shown in Fig-
ure2(top).For this setting we can compute from Equation(2)
the optimal number of clusters per round,.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 V oronoi cell will report to the cluster
head of this cell;see Figure2(middle).
At some point in time the?rst node dies;see Fig-
ure2(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?eld is over less
nodes than intended to be.
The only guarantee is that there will be at least one cluster
head per epoch(cf.Equation1).As a result in the worst case,
in only one round per epoch all alive nodes will report to the
sink.3The 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 signi?cant 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?rst 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.
5 when the system operates in the unstable region,if the
density of the sensor network is large,the probability that
large number of nodes be elected as cluster heads is
for a signi?cant part of the unstable region(as long as
population of the nodes has not decreased signi?cantly.)
this case,even though the system is unstable in this
we still have a relatively reliable clustering(sensing)
The same can be noticed even if the spatial density is low
the is large.On the other hand,LEACH in the presence
node heterogeneity yields a large unstable region.The
is that although all advanced nodes are left equipped
almost the same energy,the cluster head election process
unstable and as a result,most of the time no cluster head
elected and these advanced nodes are idle.
In the next section,we introduce our new
aware SEP protocol whose goal is to increase the stable
and as a result decrease the unstable region and improve quality of the feedback of wireless clustered sensor networks, in the presence of heterogeneous nodes.
V.O UR SEP P ROTOCOL
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 is the initial energy of each normal sensor.The energy of each advanced node is then.The total(initial) energy of the new heterogeneous setting is equal to:
So,the total energy of the system is increased by a factor of .The?rst 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
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 times,if(i)each normal node becomes a cluster head once every rounds per epoch;(ii)each advanced node becomes a cluster head exactly times every 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 then the energy is not well distributed and the average Fig.3.
number of cluster heads per round per epoch will be less than
.This problem can be reduced to a problem of optimal
threshold setting(cf.Equation1),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 becomes
a cluster head once every rounds per epoch, and each advanced node becomes a cluster head
times every 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 signi?cant number of cases where this number can not be maintained per round per epoch with probability1.A worst-case scenario could be the following.Suppose that every normal node becomes a cluster head once within the?rst rounds of 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 1for the next rounds of the epoch.But the threshold is increasing with the number of rounds within each epoch and becomes equal to1only in the last round (when all the remaining nodes become cluster heads with probability1.)So the above constraint of cluster heads in each round is violated.Figure3shows 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.
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
6
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 de?ne as the weighted election probability for normal nodes,and the weighted election probability for the advanced nodes.
Virtually there are 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(because each virtual node has the initial energy of a normal node.)The weighed probabilities for normal and advanced nodes are,respectively:
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 de?ne as the threshold for normal nodes,and the threshold for advanced nodes.
Thus,for normal nodes,we have:
if
otherwise
(5)
where is the current round,is the set of normal nodes that have not become cluster heads within the last rounds of the epoch,and is the threshold applied to a population of(normal)nodes.This guarantees that each normal node will become a cluster head exactly once every rounds per epoch,and that the average number of cluster heads that are normal nodes per round per epoch is equal to.
Similarly,for advanced nodes,we have:
if
otherwise
(6)
where is the set of advanced nodes that have not become cluster heads within the last rounds of the epoch,and is the threshold applied to a population of (advanced)nodes.This guarantees that each advanced node will become a cluster head exactly once every
rounds.Let us de?ne 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 sub-epochs and as a result,each advanced node becomes a cluster head exactly 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.
x=0x=1x=2x=3x=4x=5x=7
x=6x=9
x=8
x’=0x’=1
sub-epoch
epoch
heterogeneous epoch
sub-epoch sub-epoch sub-epoch
x’=13x’=15
x’=14
x’=10x’=12
x’=9x’=11
x’=7x’=8
x’=6
x’=5
x’=4
x’=3
x’=2
Fig.4.A numerical example for a heterogeneous network with parameters and,and.We de?ne
,and,where is the current round.
Thus the average total number of cluster heads per round per heterogeneous epoch is equal to:
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?eld(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?eld 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,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 of the nodes are advanced nodes(
)and equipped with more energy that other(normal) nodes().Consider a population of a sensor network in an?eld of nodes.The for this setting is approximately equal to(using Equation4).For simplicity let us set.This means that on average, nodes must become cluster heads per round.
If we consider a homogeneous scenario where each node has initial energy equal to the energy of a normal node, then the epoch would be equal to rounds.In our heterogeneous case,the extended heterogeneous epoch is equal to rounds,and each sub-epoch is
7
Fig.5.
heterogeneity:(top)and,and(bottom)and .
equal to rounds,as illustrated in Figure4. On average,normal nodes become cluster heads per round,and each one of them becomes a cluster head exactly once within rounds(one heterogeneous epoch.)Furthermore,on average,advanced nodes become cluster heads per round.The total number of sensors that become cluster heads(both normal and advanced) is equal to,which is the desired number.Moreover each advanced sensor becomes a cluster head exactly once every sub-epoch and becomes a cluster head times within a heterogeneous epoch,i.e.each advanced node becomes a cluster head times within a heterogeneous epoch.
VI.S IMULATION R ESULTS
We simulate a clustered wireless sensor network in a ?eld with dimensions.The total number of sensors.The nodes,both normal and advanced,are randomly(uniformly)distributed over the?eld.This means that the horizontal and vertical coordinates of each sensor are randomly selected between 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(the setting of Figure2.)The initial energy of a normal node is set to—Although this value is arbitrary for the
Transmitter/Receiver Electronics
Data Aggregation
Transmit Ampli?er
if
Transmit Ampli?er
if
TABLE I
R ADIO CHARACTERISTICS USED IN OUR SIMULATIONS. 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 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 de?ned in Section III.We also examine the sensitivity of SEP to the degree of heterogeneity in the network.We?rst 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?eld.
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-ure5(top)for and.We observe that LEACH takes some advantage of the presence of heterogeneity (advanced nodes),as the?rst node dies after a signi?cantly higher number of rounds(i.e.longer stability period)compared to the homogeneous case().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 signi?cant 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.
8
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.
We repeat the same experiment,but now the heterogeneity parameters are set to and,however remains constant.Our simulation results are shown in Figure 5(bottom).Although the length of the stability region(until the ?rst node dies)is pretty stable,LEACH takes more advantage of the presence of heterogeneity manifested in a higher number of advanced nodes.
In Figure6,a detailed view of the behavior of LEACH is illustrated,for different distributions of heterogeneity.In Figure6(a),the number of alive nodes is shown for the scenarios()and().LEACH fails to take full advantage of the heterogeneity(extra energy) as in both scenarios,the?rst node dies almost at the same round.Moreover,the normal nodes die in both cases very fast (Figure6(c))and as a result the sensing?eld becomes sparse very fast.On the other hand,advanced nodes die in a very slow fashion(Figure6(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 Figure6(b),when a signi?cant 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 to1)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?eld.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.) Figure7(top)shows results for the case of and .It is obvious that the stable region of SEP is extended compared to that of LEACH(by8%),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.
Figure7(bottom)shows results for the case of and .Now SEP takes full advantage of heterogeneity(extra
9
and for most of the unstable region.This means that because SEP guarantees cluster heads in more rounds then these cluster heads will report to the sink.It is also worth noticing that the throughput of SEP is greater than that of FAIR during the stable region and very close to that of FAIR at the start of the unstable region.Moreover,the same results are observed in Figure8(middle)for the throughput of nodes to their cluster heads,as the cluster heads in the case of SEP are elected in a relatively more stable fashion during the unstable period.As Fig.8.
ence of heterogeneity with and:(top)Cluster heads to sink;(middle)Nodes to their cluster heads;and(bottom)Total for the whole network.
a result the overall throughput of SEP is greater than that of LEACH and FAIR during the stable region and close to that of FAIR during the unstable region,as Figure8(bottom)shows.
10
D.Sensitivity of SEP
We study here the sensitivity of our SEP protocol,in
of the length of the stability period,by varying and
Figure9(top)shows the length of the stability region
.We found that the performance does not depend on
individual values of and but rather on their product,
represents the total amount of extra initial energy brought
advanced nodes.Figure9(middle)shows the percentage
in the length of the stability region over the case of
and,i.e.without the added energy of advanced
Figure9(bottom)shows the percentage gain in the length
the stability region of one protocol over another.
We observe that,as expected,the stability period
FAIR increases linearly with.On the other hand,
stability period under SEP and LEACH increases faster
then more slowly beyond a“knee”point.Moreover,as far
the ef?cient use of extra energy,the percentage gain in
stability period is maximized under SEP for most values
.In all cases SEP outperforms LEACH.
Interestingly,both SEP and LEACH outperforms FAIR
small amount of heterogeneity(or a small number of
nodes)—SEP outperforms FAIR by up to18%(when
=0.2),and LEACH outperforms FAIR by up to11%
=0.2).This is because these advanced nodes
uniformly distributed over the sensor?eld,and when
elect themselves as cluster heads,their“extra”energy
consumed more judiciously than if some of this extra
was distributed to all nodes(as in FAIR)which are
farther away from the sink.This gain over FAIR
vanishes when it becomes more bene?cial to distribute
extra energy to the fewer normal nodes.
We also notice that the gain of SEP over LEACH
as increases—SEP outperforms LEACH by up to
when=0.9.The gain of LEACH over FAIR drops
faster than that of SEP after the“knee”point.This
that the management of the extra energy of advanced
can become dif?cult,more so for LEACH than for our
protocol.
Our observations on the performance of SEP also hold
larger scale networks,where the distance between a
percentage of sensors and the sink is more than.Due
space limitation we only show Figure10as a
result.
VII.R ELATED W ORK
In addition to related work cited throughout the paper,
this section we review speci?c prior studies that dealt with
heterogeneity in energy of sensor nodes.
The?rst work that questioned the behavior of protocols in the presence of heterogeneity in clustered wireless sensor networks was[8].In this work Heinzelman analyzed a method to elect cluster heads according to the energy left in each node.The drawback of this method is that this decision was made per round and assumed that the total energy left in the network was known.The assumption of global knowledge of the energy left in the whole network makes this method dif?cult to implement.Even a centralized approach of this Fig.9.
geneity in small-scale networks.
method would be very complicated and very slow,as the feedback should be reliably delivered to each sensor in every round.
In[10],Duarte-Melo and Liu examined the performance and energy consumption of wireless sensor networks,in a?eld
11
Fig.10.
heterogeneity in large-scale networks(nodes in an
?eld.)
where there are two types of sensors.They consider nodes that are fewer but more powerful that belong to an overlay.All the other nodes have to report to these overlay nodes,and the overlay nodes aggregate the data and send it to the sink.The drawback of this method is that there is no dynamic election of the cluster heads among the two types of nodes,and as a result nodes that are far away from the powerful nodes will die ?rst.The authors estimate the optimal percentage of powerful nodes in the?eld,but this result is very dif?cult to use when heterogeneity is a result of operation of the sensor network and not a choice of optimal setting.
In[5],Mhatre and Rosenberg presented a cost-based com-parative study of homogeneous and heterogeneous clustered wireless sensor networks.They proposed a method to estimate the optimal distribution among different types of sensors,but again this result is hard to use if the heterogeneity is due to the operation of the network.They also studied the case of multi-hop routing within each cluster(called M-LEACH).Again the drawback of the method is that only powerful nodes can become cluster heads(even though not all powerful nodes are used in each round.)Furthermore,M-LEACH is valid under many assumptions and only when the population of the nodes is very large.
Other power-aware routing schemes[11],[12]assume that the exact position of each node is known a priori(e.g.each node is equipped with GPS,which increases the cost per node),and that initially,nodes are homogeneous.Such strong assumptions and especially centralized solutions[12],may not be applicable for low-cost,large-scale networks.
VIII.C ONCLUSIONS AND F UTURE W ORK
We proposed SEP(Stable Election Protocol)so every sensor node in a heterogeneous two-level hierarchical network inde-pendently elects itself as a cluster head based on its initial energy relative to that of other nodes.Unlike[8],we do not require any global knowledge of energy at every election round.Unlike[10],[5],SEP is dynamic in that we do not
any prior distribution of the different levels of energy the sensor nodes.Furthermore,our analysis of SEP is not asymptotic,i.e.the analysis applies equally well to small-networks.Finally SEP is scalable as it does not require knowledge of the exact position of each node in the?eld. We are currently extending SEP to deal with clustered networks with more than two levels of hierarchy and than two types of nodes.We are also implementing SEP Berkeley/Crossbow motes and examining deployment issues dynamic updates of weighted election probabilities on current heterogeneity conditions as well as the of SEP with MAC protocols that can provide low-information about the distribution of energy in the vicinity each node[13].
SEP code and research results are publicly available at
.
IX.A CKNOWLEDGMENTS
We are grateful to Wendi Heinzelman for answering ques-tions about LEACH,and to Kanishka Gupta for his feedback on earlier versions of this paper.
R EFERENCES
[1]I.Akyildiz,W.Su,Y.Sankarasubramaniam,and E.Cayirci,“A survey
on sensor networks,”IEEE Communications Magazine,vol.40,no.8, pp.102–114,August2002.
[2]T.J.Shepard,“A channel access scheme for large dense packet radio
networks,”in Proccedings of ACM SIGCOMM,September1996,pp.
219–230.
[3]W.R.Heinzelman,A.P.Chandrakasan,and H.Balakrishnan,“Energy-
ef?cient communication protocol for wireless microsensor networks,”
in Proceedings of the33rd Hawaii International Conference on System Sciences(HICSS-33),January2000.
[4]——,“An application-speci?c protocol architecture for wireless mi-
crosensor networks,”IEEE Transactions on Wireless Communications, vol.1,no.4,pp.660–670,October2002.
[5]V.Mhatre and C.Rosenberg,“Homogeneous vs.heterogeneous clustered
sensor networks:A comparative study,”in Proceedings of2004IEEE International Conference on Communications(ICC2004),June2004.
[6]S.Bandyopadhyay and E.J.Coyle,“An energy ef?cient hierarchical
clustering algorithm for wireless sensor networks,”in Proceedings of INFOCOM2003,April2003.
[7]——,“Minimizing communication costs in hierarchically-clustered net-
works of wireless sensors,”Computer Networks,vol.44,no.1,pp.1–16, January2004.
[8]W.R.Heinzelman,“Application-Speci?c Protocol Architectures for
Wireless Networks,”Ph.D.thesis,Massachusetts Institute of Technology, 2000.
[9] C.-Y.Wan,A.T.Campbell,and L.Krishnamurthy,“PSFQ:a reliable
transport protocol for wireless sensor networks,”in Proceedings of the 1st ACM international workshop on Wireless Sensor Networks and Applications(WSNA’02),July2002,pp.1–11.
[10] E.J.Duarte-Melo and M.Liu,“Analysis of energy consumption and
lifetime of heterogeneous wireless sensor networks,”in Proceedings of Global Telecommunications Conference(GLOBECOM2002).IEEE, November2002,pp.21–25.
[11]K.Kalpakis,K.Dasgupta,and P.Namjoshi,“Ef?cient algorithms for
maximum lifetime data gathering and aggregation in wireless sensor networks,”Computer Networks,vol.42,no.6,pp.697–716,2003. [12]H.O.Tan and I.Korpeoglu,“Power ef?cient data gathering and
aggregation in wireless sensor networks,”SIGMOD Record,vol.32, no.4,pp.66–71,2003.
[13]W.S.Conner,J.Chhabra,M.Yarvis,and L.Krishnamurthy,“Ex-
perimental evaluation of synchronization and topology control for in-building sensor network applications,”in Proceedings of the2nd ACM international conference on Wireless Sensor Networks and Applica-tions(WSNA’03),September2003,pp.38–49.
SIP协议学习总结 1、SIP协议定义 SIP（Session Initiation Protocol，即初始会话协议）是IETF提出的基于文本编码的IP电话/多媒体会议协议。用于建立、修改并终止多媒体会话。SIP 协议可用于发起会话，也可以用于邀请成员加入已经用其它方式建立的会话。多媒体会话可以是点到点的话音通信或视频通信，也可以是多点参与的话音或视频会议等。SIP协议透明地支持名字映射和重定向服务，便于实现ISDN，智能网以及个人移动业务。SIP协议可以用多点控制单元（MCU）或全互连的方式代替组播发起多方呼叫。与PSTN相连的IP电话网关也可以用SIP协议来建立普通电话用户之间的呼叫。 SIP协议在IETF多媒体数据及控制体系协议栈结构的位置 H.323SIP RTSP RSVP RTCP H.263 etc. RTP TCP UDP IP PPP Sonet AAL3/4AAL5 ATM Ethernet PPP V.34 SIP协议支持多媒体通信的五个方面： ◆用户定位：确定用于通信的终端系统； ◆用户能力：确定通信媒体和媒体的使用参数； ◆用户有效性：确定被叫加入通信的意愿； ◆会话建立：建立主叫和被叫的呼叫参数； ◆会话管理：包括呼叫转移和呼叫终止； SIP协议的结构 SIP是一个分层的协议，也就是说SIP协议由一组相当无关的处理层次组成，这些层次之间只有松散的关系。 SIP最底层的是它的语法和编码层。编码方式是采用扩展的Backus-Naur Form grammar (BNF范式)。 第二层是传输层。它定义了一个客户端发送请求和接收应答的方式，以及一 个服务器接收请求和发送应答的方式。所有的SIP要素都包含一个通讯层。 第三层是事务层。事务是SIP的基本组成部分。一个事务是UAC向UAS发送的一个请求以及UAS向UAC发送的一系列应答。事务层处理应用服务层的重发，匹配请求的应答，以及应用服务层的超时。任何一个用户代理客户端完成的事情都是
多媒体通信协议 实验报告 实验成绩
多媒体通信协议实验报告 实验一颜色 一、实验目的 了解颜色的表示方法。 二、实验原理 1. RGB表示法 人们在生活中，用红、橙、黄、绿、青、蓝和紫等名词来描述彩色的大致范围。如果再进一步细分，红色则有深红、浅红、大红、粉红等。即使这样细分，仍然不能把颜色表达得十分准确。根据德国科学家格拉兹曼所总结的法则，任何一种彩色都可由另外的不多于三种的其他彩色按不同的比例合成。这意味着，如果选定了三种人所共知的标准基色(标准基色必须是独立的，即其中一种不能由其他两种产生)，那么任何一种彩色，可以用合成这一彩色所需要的3种基色的数量来表示。例如，选择波长分别为700nm、546:1nm和435:8nm的红、绿、蓝光作为基色，用不同比例的三基色光可以配出任何一种彩色。三种光的能量之和决定了合成光的亮度，而三种光强之间的比例关系决定了合成光的色调(颜色)和饱和度(颜色深浅)。一个任意光(A)和三基色光之间的关系可以写成下式(A) = ra(R) + ga(G) + ba(B) (1)式中带有括号的大写字母只代表某种光，如(R)只代表红光，并不具有数量和量纲的含义，数量由它们各自的系数代表。式(1)表明，在基色光(R)、(G)和(B)选定以后，任何一种彩色(A)都可以用三个相应的数ra、ga和ba来表示。这事实上已经解决了用数学的方法严格地定义彩色的问题。但是在实际的应用中发现，这样的三个数有时相互之间在数量上可以相差个数量级，以至于有的数值小到在进行色度计算时可以忽略，而它在光的合成中却起着明显作用，又不能忽略。解决这一问题的办法，是用合成某种标准白光(如等能白光)所对应的三个系数值，分别作为三种基色光的1个计量单位。以此计量单位度量的任意彩色(A) 的三个系数称为三色系数，用R、G、B表示。 2. matlab的imshow()函数 imshow()是matlab图像处理工具箱中用于显示图像的函数。imshow()函数有几种用法，其中一种用法是imshow(RGB)参数RGB是一个m _ n _ 3的矩阵，矩阵中的每个元素是0 _ 1之间的小数。