Database Reference
In-Depth Information
where
R
is the cluster range (the farthest distance nodes can be from
their cluster heads) and
E
initial
(
s
)and
E
residiual
(
s
) are the initial and
residual energy of node
s
respectively. The average number of neighbor-
ing nodes can be shown to be at most six [21]. Intra-cluster commu-
nication will be at minimum when the transmission graph contains the
shortest paths between all pairs of nodes in the cluster.
The protocol starts with each node
u
broadcasting its (
x,y
)coordi-
nates, establishing its local neighborhood
N
α,c
(
u
), calculating its weight
W
(
s
) and broadcasting it. A node
s
sets
level
(
s
)=
1, indicating that
it hasn't joined any cluster yet. In the
cluster generation
phase, the
following procedure is repeated for a fixed number of six iterations. Let
i
be the iteration number. A node
s
first checks if it is assigned to a
cluster. If not, it will become a temporary cluster head if its weight
is largest among it neighbors, otherwise the neighbor with the largest
weight is chosen as a temporary head for
s
. The ID of the temporary
head is broadcasted to all neighbors of
s
. A node becomes a real cluster
head only if a percentage of (6
−
i
)
/
6 nodes elect the node as their tem-
porary cluster head. In this case, the information is broadcasted to all
neighbors, including the (
x,y
) coordinates, and the level of
s
is set to
0. There are three cases in which a node doesn't become a cluster head,
but a child node:
−
1When
level
(
s
)=
1, node
s
receives a broadcast message from
its neighbor
n
, including the (
x,y
) coordinates of its cluster head
h
n
.If
−
<R
,
s
chooses
h
n
as its cluster head.
level
(
s
):=
level
(
n
) + 1 and the distance of
s
from its cluster head is set to
||
||
sh
n
||
sn
||
+
||
nh
h
||
.
2If
s
receives a message from neighbor
n
and
level
(
s
)
1, node
s
has already chosen its cluster head. If
n
is assigned to a different
cluster head
h
n
whose distance from
s
is in cluster range
R
and the
previously calculated distance to its current cluster head is greater
than
=
−
,then
h
becomes the new cluster head of
s
and
level
(
s
):=
level
(
n
)+1.
||
sn
||
+
||
nh
n
||
3If
s
receives a message from neighbor
n
,
level
(
s
)
1andthe
cluster heads of
s
and
n
are the same, it is checked whether the
distance of node
s
to its neighbor
n
is less than the previously
calculated distance. If it is,
s
will choose
n
as its parent and set
level
(
s
) and the new distance as in the second case.
=
−
For finalization, the cluster generation is run a last (seventh) time.
Afterwards, each node is either a cluster head or a child node.