DISTRIBUTED DATA MINING IN SENSOR NETWORKS - Managing and Mining Sensor Data - page 213

battery-operated sensors may run out of energy and harsh environmental
conditions can damage network components. In these scenarios, algo-
rithms are needed that cluster sensor nodes and determine cluster heads
dynamically, forming the infrastructure in an ad-hoc manner. Also, they
must be able to reconfigure the network when necessary.
Clustering algorithms that have been developed for WSNs mainly
differ in their assumptions on the given network components , the desired
topology ,andinthe goals they try to achieve. These in turn influence
the used methodologies and running times.
Regarding network components , clustering can become more constraint
in heterogenous networks where cluster heads have a higher capacity
than sensor nodes. Here, the available number of high capacity compo-
nents will determine the maximum number of cluster heads and therefore
the number of clusters. Moreover, if communication costs between clus-
ter heads and sensor nodes are to be minimized, a stationary location
of cluster heads will lead to a static assignment of sensors to clusters,
except for cases where cluster heads fail and the network needs to be
reconfigured. In comparison, in more homogenous networks, also reg-
ular sensor nodes can become cluster heads. Clustering algorithms for
these networks are usually more dynamic, as they need to continuously
balance the energy consumption across all nodes, based on their resid-
ual energy. Several algorithms achieve this, for instance, by a regular
rotation of cluster heads.
The required topology is largely dependent on the given distances be-
tween sensor nodes, cluster heads and base stations. Depending on the
placement of nodes, the network topologies that need to be considered
can reach from fixed 1-hop [33] over fixed k -hop [64] to fully adaptive
architectures [21]. An important objective is that network components
remain connected, i.e. that sensor nodes are able to reach their cluster
heads and that cluster heads can reach a base station. Other objectives
like minimizing the intra-cluster energy-consumption may need to be
trade-off against the goal of components staying connected, for exam-
ple in cases where an energy-optimal cluster head could no longer reach
its base station. Taking into account several — possibly contradicting
— quality criteria thus turns clustering in WSNs into a multi-objective
optimization problem.
The main goals that cluster algorithms for WSNs try to achieve are
maximal network longevity, connectivity and fault-tolerance. Extend-
ing the operational life-time of a WSN requires load-balancing strategies
that prevent premature exhaustion of subsets of sensor nodes and cluster
heads. The goal of maintaining connectivity is concerned with ensuring
that the most important network components can reach each other, pos-