Image Processing Reference
In-Depth Information
Network functioning is divided into two phases: the setup phase and the data communication
phase. During the former phase, cluster head selection, cluster setup, CH-to-CH path creation, and
the transmission schedule have to be computed and then communicated to each node. Selection of
the cluster heads is based on the residual energy of nodes. hese values are sent in the transmissions
of each node, so the BS always knows the energy status of each node. In order to identify a predefined
number of cluster heads,
N
CH
, and to group nodes in a way that minimizes energy consumption in
the data phase, an iterative cluster splitting algorithm is adopted, which first splits the network into
two clusters and then iteratively splits each cluster into subclusters, until the desired number of cluster
headsisobtained,inawaythatmaximizesthedistance between the cluster heads of different clusters.
Furthermore, the balanced clustering technique [Ghi] is adopted to achieve a fair load distribution.
The algorithm works in four steps. First, two nodes from the set of eligible cluster heads are chosen.
Second,theremainingnodesaregroupedwiththeclosestofthesetwogroups.hen,thetwogroups
arebalanced,sothattheirnumberofnodesisapproximatelythesame.Finally,thesetofeligible
clusterheadsissplitintotwosetsaccordingtothetwogroupscreated,andthenextiterationcan
begin.
DuringthesetupphaseroutingpathsarealsocomputedbytheBS.hesepathswillbeusedtoroute
data CH-to-CH toward the BS. Routing paths are selected by calculating the minimum spanning tree
in terms of energy consumption for each cluster head [She] and then randomly choosing the leader
node, i.e., the cluster head that transmits directly to the BS.
The last task of the BS during the setup phase is to calculate the TDMA schedule used to transmit
data.
Duringthedatacommunicationphaseeachnodewillusetheassignedtimeslottocommunicate
with the cluster head. As in LEACH, CDMA is used to limit interference between multiple clus-
ters. Data is gathered by the cluster head, aggregated, and then transmitted through the assigned
CH-to-CH path.
As the number of long-range communications is reduced with respect to LEACH, energy
efficiency is better. But it is also shown to be better than PEGASIS, as the (minimum energy) CH-to-
CH path computed by the BS is more energy-efficient than the greedy algorithm used by PEGASIS,
although in [Gua] it is shown that the BCDPC routing scheme is not always energy-efficient.
In addition (even if the authors do not explicitly address this feature), the use of a TDMA sched-
ule enables simple duty-cycle reduction by putting nodes to sleep when they do not need to be
active [Pot]. However, this protocol is fully centralized, so scalability may be a problem for large
WSNs, and the presence of a single leader as in PEGASIS may cause large delays.
7.5.3 Energy-Aware Routing Protocol in Cluster-Based Sensor Networks
A different approach to cluster-based WSNs was proposed in [You], in which cluster heads are
fixed, rather than elected in rotation, and called gateway nodes. Gateway nodes and sensor nodes are
not the same kinds of nodes, i.e., only sensor nodes are battery-powered and thus energy-constrained.
The main idea of this approach is to let gateway nodes be centralized network managers for nodes
belonging to their clusters. heir role is not only to collect data from sensor nodes, as they also per-
form sensor organization and network management depending on the mission and residual energy
of the node, so they have to set routes for data forwarding, monitor energy and latency throughout
the cluster, and arbitrate medium access between sensor nodes.
hisprotocolassumesthatbothsensornodesandgatewaysareinaixedposition(i.e.,nomobility)
and that each gateway is in the radio range of all the nodes in its cluster. Cluster formation is per-
formed before the network starts and, as gateway nodes are not energy-constrained, there is no need
to change them as in LEACH. However, the protocol itself does not describe the clustering algorithm
adopted. Sensor nodes are assumed to be capable of independently shutting down their transceivers
or their sensing circuitry and can operate in four different states.
