C. Wei et al. /Journal of Computational Information Systems 10: 10 (2014) 4475–4487 4477
LEACH [3] is a typical clustering protocol proposed for periodical data gathering applications in
WSNs. In LEACH, each node independently elects itself as a CH with a probability. CHs receive
and aggregate data from cluster memb ers and forward the aggregated data to the BS by single-hop
communication. In order to balance the energy depletion, the role of CH is periodically rotated
among the nodes. Researchers further improved LEACH and proposed some new algorithms such
as centralized algorithm LEACH-C [3], multi-level clustering algorithm EEMLC [9], algorithm
based on heterogeneous networks EEHC [10], and algorithm based on multihop communication
LEACH-M [11].
HEED [12] periodically selects CHs according to a hybrid of their residual energy and the
communication cost. It terminates the clustering process within a constant number of iterations,
and achieves fairly uniform distribution of CHs across the network. In [13], the authors propose
VCA, in which sensors vote for their neighbors to elect suitable CHs, and two strategies to balance
the intra-cluster workload among CHs. CAWT [14], which uses random waiting timer to generate
clusters, was a neighbor-based clustering algorithm. In CAWT, a sensor updates its neighbor
information by Hello message. And it decreases its waiting timer inversely proportional to the
number of neighbors. When a waiting timer is expired, a sensor declares itself to become a CH.
ACAWT [15], where the CHs are selected based on residual energy, has been proposed as an
enhanced CAWT scheme. If the energy of CH is falls below a threshold level, the reselection
process of CH is started. EADEEG [16] selects CHs based on the ratio between the average
residual energy of neighbor nodes and the residual energy of the node itself, which can achieve a
good CHs distribution and prolong the network lifetime.
Although the above even clustering schemes balance the average energy consumption among
different intra-cluster communications well, they ignore the energy balancing problem among CHs
in the inter-cluster communication. Some CHs farther away from the BS deplete more energy
with single-hop communication for long-distance transmission, and some CHs nearer the BS take
a heavier energy burden to relay data via multihop communication. To solve this problem, some
unequal clustering schemes have been proposed [17-23].
In EECS [17], a distance-based cluster formation method is proposed to produce clusters of
unequal sizes in single hop networks. Clusters farther away from the BS have smaller sizes,
thus some energy could be preserved for long-distance data transmission to the BS. Soro ad
Heinzelman [18] first investigate an unequal clustering method for the network that was organized
into heterogeneous clusters, where some more powerful nodes act as cluster heads to control the
network operation. This approach can be expanded to homogeneous sensor networks, however,
it was demonstrated only for a circular network with two-hop inter-cluster communication. Shu
et al. [19] study an optimization problem of balancing energy consumption among CHs which
is formulated as a signomial optimization problem. The study demonstrates the significance
of simultaneously considering the impacts of intra-cluster and inter-cluster traffic. In [20], the
authors propose an energy-efficient unequal clustering mechanism (EEUC) for periodical data
gathering applications in WSNs. It wisely organizes the network via unequal-clustering and
multi-hop routing. The competitive range is determined on the basis of relative value of maximum
distance between the sensors and the sink. The result is that clusters closer to the base station
are expected to have smaller cluster sizes, thus the CHs will consume lower energy during the
intra-cluster data processing, and can preserve some more energy for the inter-cluster relay traffic.
The authors in [21] present an analytical model of cluster size based on the distance between
the CH and the sink, and propose a simple clustering algorithm called LUCA, where each cluster