Database Reference
In-Depth Information
sibly putting constraints on the clustering. Fault-tolerance deals with
the failure of network components and can be achieved by redundancy,
rotating roles of network components as well as re-clustering.
As a survey article by Abbasi and Younis [1] shows, the clustering
algorithms for sensor nodes are quite diverse and hard to categorize.
Moreover, there already exist more algorithms than can suciently be
presented here, even in summary. Therefore, we decided to focus on only
two algorithms in more detail. The algorithms were chosen as examples
for demonstrating how the same network topology can be achieved by
entirely different means and with different running times. At the end of
this section, the reader is then pointed to further algorithms.
2.1.1 Hierarchical control clustering.
The clustering scheme
introduced by Banerjee and Khuller [7] forms a hierarchical multi-hop
network topology, where the number of layers is determined automati-
cally. The original problem statement is that given an undirected graph
G
=(
V,E
) and a positive integer
k
with 1
≤
k
≤|
V
|
, for each connected
component clusters
V
1
,...,V
l
with
V
i
⊆
V
should be found such that
(1) all vertices are part of a cluster, (2) all subgraphs induced by
V
i
are
connected, (3) cluster size is bounded by
k
<
2
k
,(4)twoclusters
should only have few common vertices and (5) each vertex belongs to a
constant number of clusters. After demonstrating that requirement (5)
could be violated in general graphs, the problem is restricted to
bounded
disk graphs
, as they are usually given in WSNs. For
R
min
and
R
max
being
the minimum and maximum transmission radius over all nodes, (
u,v
)is
an edge in
G
if and only if
R
min
≤|
V
i
|
R
max
. The algorithm then
guarantees that no node is a member of more than
O
(log(
R
max
/R
min
))
clusters. Furthermore, to fulfill requirement (4), it is necessary to allow
a single cluster in
G
to have a size smaller than
k
.
The distributed algorithm consists of two phases:
cluster creation
and
cluster maintenance
. The cluster formation process can be started by
an arbitrary node in the network, which becomes the root node of a
Breadth-First-Search (BFS) tree. The initiator with the least node ID
takes precedence. Every
t
units of time, each node
u
broadcasts a
tree
discovery
message to nodes that are in its transmission radius. The mes-
sage contains a source ID, parent ID (initially not set), the ID of the root
node, a sequence number and the shortest (known) hop-distance to the
root,
r
. A node
v
will make
u
its parent and update its hop-distance
if the route through
u
to
r
is shorter. The root ID and sequence num-
ber are used to distinguish between multiple instances of the cluster
creation phase. Next, for
cluster formation
, the sent messages are ex-
tended by additional fields representing
subtree size
and
node adjacency
.
≤
d
(
u,v
)
≤
