INTRODUCTION
Recent advances in wireless communication and electronics have enabled the
development of lowcost, lowpower, multifunctional sensors that are small
in size and able to communicate untethered within a short distance. In order
to achieve energy efficiency and increase network scalability, sensor nodes
can be organized into clusters. Communication within a cluster as well as communication
between different clusters can be organized as a combination of onehop and
multihop communication. In onehop communication, every sensor node can directly
reach the sink node, while in multihop communication, nodes have limited transmission
range and therefore are forced to route their data over several hops until the
data reach the sink node. In both models, there is an unavoidable problem of
unbalanced energy dissipation among different nodes, leading to the situation
where some nodes lose energy at a higher rate and die much faster than others,
possibly reducing sensing coverage and leading to network partitioning. For
singlehop communication, the nodes furthest away from the sink node are the
most critical nodes, while in multihop communication, the nodes closets to
the sink node are burdened with a heavy relay traffic load and die first, i.e.,
the hot spot problem (Perillo et al., 2005).
LEACH (Heinzelman et al., 2002) is a wellknown
hierarchical architecture routing algorithm, which uses randomization to rotate
the Cluster Heads (CHs) and achieves significant improvement compared to direct
approach. However, this approach allows only onehop clusters to be formed and
the hot spot problem does not be considered. Li and Mohapatra
(2005) presented a mathematical model to analyze hot spot problem and characterize
energy hole problem in Wireless Sensor Networks (WSNs). Based on a traffic perspective,
this analytical model examines the validity of several possible schemes aiming
to mitigate or solve the energy hole problem. It is observed that in a uniformly
distributed sensor networks, clustering deployment and data compression have
a positive effect. Olariu and Stojmenovic (2006) presented
the first theoretical work to analyze avoidance of the energy hole problem and
it has been proven that the unbalanced energy depletion is intrinsic and no
routing strategy can avoid under some specific conditions in this study. Perillo
et al. (2004) formulated the transmission range distribution optimization
problem and derived a linear programming model to obtain the maximizing WSNs
lifetime. EEUC (Li et al., 2005) use the competition
radius to produce the unequal clustering, but this mechanism does not consider
density of sensors deployed that might cause much workload on CHs and too much
communication overhead. Soro and Heinzelman (2005) proposed
an unequal clustering size mode for network organization. However, it shows
somewhat an unrealistic architecture since they assume that CHs with super power
are deployed or move to the best position where minimizes energy consumption.
It also considers only 2 layers, which means scalability is not in concern.
In this study, a novel EnergyBalancing Unequal Clustering Protocol (EBUCP)
for WSNs is proposed. In EBUCP, the entire network has been divided into
some layers and clusters from probability view. The number of clusters
closer to the sink node is bigger than those farther away from sink node.
However, the number of nodes in each cluster closer to the sink node is
smaller than those farther away from sink node. Thus inner CHs can reduce
the energy consumption within a cluster and preserve more energy for intercluster
data relaying. In order to balance the energy dissipation in every layer,
the reasonable ratios of distribution density among layers are derived
according to energybalancing principle. Therefore, the energy consumption
in every layer is nearly equal after such a deployment and the hot spot
problem can be effectively mitigated by this way. Finally, an energyefficient
data transmission mechanism is presented on basis of unequal clustering
algorithm and energybalancing layered algorithm. Theoretical analysis
and simulation studies show that EBUCP outperforms in terms of balancing
energy dissipation among sensor nodes and enlarging the lifetime of networks
than EEUC and LEACH.
EBUCP: AN ENERGYBALANCING UNEQUAL CLUSTERING PROTOCOL
Network model: All the nodes are assumed to be deployed in a circular
area with a radius of R. The only sink is located at the center of the
area. This represents a layered network where every layer contains a particular
number of clusters, as shown in Fig. 1.
All the sensor nodes are homogeneous and have an ID number and the ith
corona is denoted by layer L_{i}. The maximum layer number is
k and the width of each layer is r. For sake of simplicity, each sensor
node is assumed to generate and send h bits of data per unit time. Nodes
belonging to layer {L_{i}i≠ k} will forward both the data
generated by them and the data generated by nodes from layers {L_{j}(i+1)≤j≤k}.
The nodes in the outermost, L_{k}, need not forward any data.
The model for energy dissipation is taken from LEACH, where, for our multihop
forwarding scheme we assume a free space propagation channel model. The
energy spent for transmission of a hbit packet over distance d is:

Fig. 1: 
A circular area consisting of coronas 
E_{tx} (h, d) = h(e_{1}+e_{2}d^{2}) 
(1) 
And the energy spent on receiving a hbit packet is:
E_{rx} (h, d) = he_{1} 
(2) 
The electronics energy, e_{1}, depends on factors such as the
digital coding, modulation, filtering and spreading of the signal. The
amplifier energy, e_{2}, depends on the distance to the receiver
and the acceptable biterror rate.
Unequal clustering algorithm: At network deployment stage, sink node
broadcasts a hello message to all sensor nodes. Through the Received Signal
Strength Indication (RSSI), each node can compute the approximate distance to
the sink and the layer number of node belonging according to algorithm which
is proposed by De et al. (2006). After the computation,
each sensor sends its corresponding level number to the sink node. The sink
knows the maximum layer number k and broadcasts it to all sensor nodes.
The key idea of clustering algorithm is to utilize clusters of unequal
sizes to mitigate the hot spot problem. Layers are assigned different
probabilities according to the distance from sink node and the layers
closer to the sink node have greater probabilities than those farther
away from sink node. Low probability indicates small number of CHs, which
also means that each CH will occupy a huge cluster area with probably
many nonCH nodes. Therefore, it is fair that closer sensor nodes get
higher probability to be chosen as CHs in the perspective of balanced
energy dissipation through the whole network. In order to balance energy
depletion among nodes, the CH selection in every layer is primarily based
on the residual energy of tentative cluster heads. The node i’s probability
of becoming a CH p_{i} will be computed as follows:
where, p_{max} is the node’s probability of becoming a CH in
first layer, p_{min} is the node’s probability in the kth layer,
j represents node i’s layer number.
In our algorithm, let p_{max} = 1, That is, nodes in first layer
all become CHs as they have direct transmission to sink node with small
amount of energy and fully devote to heavy relaying traffic. The pseudocode
for an arbitrary node i at the cluster head selecting stage is given in
Fig. 2.
Each node in every layer become a tentative CH with the same probability
p_{i} which is defined by Eq. 3. Other nodes
keep sleeping until the CH selection stage ends. Each tentative CH maintains
a set S_{CH} of its adjacent tentative CHs. Tentative head q is
an adjacent node i if q is in i’s intracluster transmission range and
two nodes are in the same layer. In lines 45 of Fig. 2,
each tentative CH broadcast a CompeteCH_msg which contains its id, layer_id
and residual energy. After the construction of S_{CH} has been
finished in lines 78, each tentative CH checks its S_{CH} and
makes a decision whether it can become a CH in lines 919. Before deciding
what its role is going to be, i needs to know what each node q in its
S_{CH} such that q.E_{current}>i.E_{current}
has decided for itself. In lines 1012, once node i finds that its residual
energy is more than all the nodes in its S_{CH}, it will win the
competition and broadcast a FinalCH_msg to inform its adjacent tentative
CHs. In lines 1315, if qis in i’s S_{CH} and i receives a FinalCH_msg
from q, i will give up the competition immediately and inform all nodes
in its S_{CH} by broadcast a QuitEle_msg. In lines 1619, if i
receives a QuitEle_msg from q and q belongs to i.S_{CH}, i will
remove q from its S_{CH}.

Fig. 2: 
Cluster head competitive algorithm 
After CHs have been selected, each CH broadcasts a CH_ADV_msg across
the network field. Each ordinary node chooses its closest CH with the
largest received signal strength and then informs the CH by sending a
JOIN_CLUSTER_msg.
Energybalancing layered algorithm: The energy balancing in every
layer is considered in this subsection. In order to measure the data aggregation
by CH within a cluster, all CHs are assumed to equally compress the data,
where this efficiency is expressed by the aggregation coefficient α
and energy dissipation for unit data aggregation is e_{3}. If
let N_{i} and ρ_{1} denote the number and distribution
density of layer L_{i}, respectively. The total energy consumption
in each layer can be calculated. According to the above assumptions and
network model, the outermost layer L_{k} only needs to forward
data generated by themselves. Thus energy dissipation per unit time of
each CH in outermost layer L_{k} is:
Equation 4 shows that the smaller α is, the higher
efficiency of data aggregation by CH is. The energy dissipation per unit
time of each nonCH in outermost layer L_{k} is:
Thus, the energy consumption per unit time of all nodes in L_{k}
is:
All the CHs in other layers have to transmit data generated by them as
well as data originated from outer layers. Therefore, the energy consumption
per unit time of all nodes in L_{i} (1≤i≤k) is:
Ideally, when the energy consumption of all the layers is equal, the
network lifetime and the energy efficiency are maximized, That is,
E_{1} = E_{2} =
E_{3} …. = E_{k} 
(8) 
If let
Then we can obtain:
Let S_{i} stand for the area of layer L_{i}. Then the
node density is given by
By Eq. 10 and 11, the ratio between
the node densities of L_{i} and L_{i1} is obtained as:
Thus, if distribution densities of nodes between L_{k} and L_{k1}
is deployed by Eq. 12, energy consumption of two layers
is balanced. If let
Then,
After iterative calculating, we can obtain the ratios of ρ_{k},
ρ_{k1}, … ρ_{i} … ρ_{2}, ρ_{1}.
The nodes’ distribution densities of whole network under energybalancing
is achieved when the ρ_{k} is determined. Therefore, the
more uniform energy dissipation and the longer lifetime of networks are
obtained by this energybalancing layered algorithm.

Fig. 3: 
Intercluster data transmission algorithm 
Data transmission mechanism: The data transmission mechanism of
EBUCP is based on unequal clustering algorithm and energybalancing layered
algorithm. Firstly, sensor nodes can be deployed according to the distribution
density based on the results derived in the previous section. Then, nodes
use the unequal clustering algorithm to compete CH. When CHs deliver their
data to the sink node, each CH first aggregates the data from its cluster
members and then sends the packets to the sink node via a multihop path
through other intermediate CHs. Thus the data transmission of whole network
includes intercluster and intracluster data transmission. The organization
of intracluster data transmission is similar to LEACH after clusters
have been set up, so it was omitted in this section. The pseudocode of
the intercluster algorithm for CHi is presented in Fig.
3. In order to gain balanced energy depletion among the CHs, the CH
i selects one relay CH with maximum energy resource. When selecting the
relay CH with maximum residual energy, the CHi has to exchange energy
information with all candidate relay CHs in lines 710 of Fig.
3. If there is more than one candidate with the same maximum residual
energy, choose one of them randomly. After the CH i selects the relay
CH, it forwards data of its own as well as those from the upper layer
CHs in lines 1119. And the selected relay CH will repeat this process
until the data arrive at sink node.
Analysis of EBUCP complexity: The EBUCP is composed of CH competitive
algorithm, energybalancing layered algorithm and intercluster data transmission
mechanism. Since energybalancing layered algorithm can be calculated
by sink n ode, we only consider the clustering algorithm and intercluster
data transmission algorithm. According to previous sections, both algorithm
are messagedriven, thus we discuss its message complexity. For CH competitive
algorithm, N_{i}xp_{i} tentative CHs are produced in every
layer and each of them broadcasts a CompeteCH_msg. Then each of them makes
a decision by broadcasting a FinalCH_msg to act as a final CH, or a QuitEle_msg
to act as an ordinary node. Suppose s CHs are selected, they send out
s CH_ADV_msg and then (N_{i}s) ordinary nodes transmit (N_{i}s)
JOIN_CLUSTER_msg. Thus the messages add up to 2N_{i}xp_{i}+s+N_{i}s
= (2p_{i}+1)N_{i}, i.e., O (N_{i}). The intercluster
data transmission mechanism mainly includes energy inquiring message and
data forwarding message. The message complexity of both is O (N_{i}^{2}).
Therefore, the complexity of EBUCP is O(N_{1}^{2}).
SIMULATION RESULTS
Here, the performance of the EBUCP protocol with simulations is evaluated.
Lifetime is the criterion for evaluating the performance of WSNs. In the simulation,
we measure the lifetime in terms of the round when the first node dies (Chang
and Tassiulas, 2004). For simplicity, an ideal MAC layer and errorfree
communication links are assumed. The simulation parameters for our proposed
protocol are given in Table 1. The experiments described in
this part have been conducted with the aid of a well known simulation tool,
Ns2. The parameters and characteristics of our architecture are first observed
and then the performance of proposed idea is examined comparing with the EEUC
and LEACH.
The value of k verification: The suitable number of layers is
important to the energy consumption. Too big or too small value of k will
decrease the lifetime of network. From Fig. 4, the value
of k is 7 which is suitable for the range of 68.
Impact of node number of the first layer: In order to investigate
the impact of node number of the first layer, its range is varied from
8 to 52 and the aggregation coefficient (α = 0.1, 05, 1) is adopted
as shown in Fig. 5. Figure 5 shows
that the rounds of lifetime increase almost proportionally for EBUCP
as the number of nodes in the first layer increases. With more CHs closer
to the sink node, the lifetime of the network improves significantly.
In addition, when CH forward 10% of the cluster load (α = 0.1), the
maximum rounds of lifetime is increased by 12 times than α = 0.5.
Table 1: 
Parameters of simulations 


Fig. 4: 
The value of k verification 

Fig. 5: 
Impact of node number of the first layer 
Energy efficiency: In this subsection, the performance of EBUCP,
EEUC and LEACH in terms of network lifetime are compared. From Fig.
6ad, the ratio of alive nodes of EBUCP is much bigger than LEACH
and EEUC when CHs forward different ratio of the cluster load (α
= 0.1, 0.2, 0.7, 1.0). Compared with the EBUCP and EEUC, CHs in LEACH
sends their packets to the sink node via single hop and the energy consumption
is much higher. In EBUCP and EEUC, CHs transmit their data to the sink
node via multihop, thus a considerable amount of energy is saved. By node
distribution of energy balancing in each layer, the energy dissipation
of EBUCP is more uniform than EEUC and LEACH. On average, EBUCP achieves
a 3354% improvement in network lifetime against EEUC and LEACH depending
on the aggregation efficiency.

Fig. 6: 
Performance comparison, (a) α = 0.1, (b) α
= 0.3, (c) α = 0.7 and (d) α = 1 
CONCLUSION
The hot spot problem appears when employing the multihop routing in a clustering
approach. To address the problem, a novel energybalancing unequal clustering
protocol for WSNs has been introduced. An unequal clustering algorithm from
probability view is presented and clusters closer to the sink node have smaller
sizes than those farther away from the sink node. Thus CHs closer to the sink
node can preserve some energy for the purpose of intercluster data forwarding.
Then, the balance of energy consumption among layers is analyzed and an energybalancing
layered algorithm is proposed. Based on the above, the data transmission mechanism
is discussed. By unequal clustering and node distribution of energy balancing,
EBUCP ensures more balanced energy consumption as well as network lifetime
than previous researches. Simulation results show that EBUCP significantly
improves the network lifetime over LEACH and EEUC.
To ease the analysis of EBUCP, several simplifying assumptions that
have been made in this study will be addressed in further research. For
example, the effect of errors and collisions and eventbased networks
where the data generation rate at each node is a function of phenomena
in the environment rather than constant at each node will be considered
in EBUCP.
ACKNOWLEDGMENTS
This research was financially supported by National Natural Science Fund
of China with grant No. 60472074 and China’s Next Generation Internet
Demonstration Project with grant No.CNGI0421D.