Image Processing Reference
In-Depth Information
algorithm is to prolong the lifetime of a WSN. In HEED cluster-head selection is thus based on two
different parameters. The primary parameter is the residual energy of each node, while the second
parameter measures the intracluster communication cost, i.e., the number of neighbors. he idea is
to use the primary parameter to perform a probabilistic choice of an initial set of cluster heads, and
the second parameter to break ties between them, e.g., when a node is within the range of multi-
ple cluster heads. his is an iterative algorithm in which nodes change their probability of becoming
cluster-head CH
prob
at each iteration. his value is initially set to
E
residual
E
max
CH
prob
=
C
prob
×
(.)
where
C
prob
isaconstantthatlimitsinitialcluster-headcandidatures(buthasnodirectimpactonthe
final results)
E
residual
istheresidualenergyofthenode
E
max
is its maximum (initial) energy
When nodes elect themselves to become cluster heads, they send an announcement message and
then go into
tentative_CH
status if their CH
prob
is less than , or otherwise into
final_CH
status.
Nodes that receive an announcement consider themselves covered. At each iteration, each uncovered
node elects itself as a cluster head with a probability CH
prob
, then every node doubles its CH
prob
value. Each node selects the least-cost candidate as its cluster head. Nodes that complete the HEED
execution without selecting a cluster head in
final_CH
status consider themselves uncovered and elect
themselves cluster heads with
final_CH
status. A
tentative_CH
can also become a non-cluster-head
node if it finds a lower-cost cluster head.
This algorithm is proved to guarantee a bounded number of iterations before converging. he selec-
tion of cluster heads is energy-aware (so it selects better cluster heads than LEACH) and the clusters
obtained are balanced. However, HEED requires multiple iterations, so the overhead and power con-
sumptionduetonetworkmanagementisgreaterthaninLEACH.Nevertheless,simulationresults
show that the higher overhead is compensated for by the better cluster-head selection mechanism
and the final result is an increased network lifetime.
7.5.2.3 Maximum Energy Cluster-Head (MECH) Protocol
The MECH [Cha] protocol is an improvement on LEACH, in which the cluster setup phase takes
into consideration both the radio coverage and the number of nodes currently belonging to the clus-
ter. In this way, cluster placement over the network can be more uniform than with the distributed
LEACH approach. he MECH protocol features localized coordination and control for cluster setup,
while balancing and further reducing the overall dissipated energy. his can be achieved by address-
ing two shortcomings of LEACH. The first is the random election of cluster heads, which does not
allowthemtobeevenlydistributedovertheieldandthusbeconcentratedinasmallarea.Inthis
case, high-power transmissions may be needed to reach far cluster heads. he second problem is that
if a cluster head is far away from the sink node, direct transmission is not efficient (or not even possi-
ble). To overcome these drawbacks, a different cluster setup phase is proposed as well as a hierarchical
intercluster routing scheme.
Like the LEACH protocol, MECH also partitions time into rounds, each one divided into different
phases. During cluster initialization, each node broadcasts a hello message using a limited amount of
power. Nodes count their neighbors, and when the number reaches the predefined number of nodes
in a cluster
CN
(a global parameter of the WSN), the node broadcasts an ADV message that informs
neighborsthatitwillbetheclusterheadforthenextround.WhenanodereceivesanADV,aback-of
timer is started, and it does not send ADVs even if the
CN
value is reached. When this timer expires,
the node selects the cluster head with the highest signal strength and sends a message to inform
