In general, a Wireless Sensor Network consists of thousands of sensors that are smaller in size, low rate, low computational ability and small memory constraint. These nodes are able to gather the data from surroundings, storing and processing the gathered data and interacting and collaborating within the network [1]. The sensor networks have limited and non-rechargeable energy resources, so the energy effectiveness is one of the challenging factors to extend the lifetime of sensors, which affect the lifetime of overall sensor networks significantly.

Sensor nodes can be grouped into clusters to utilize the energy efficiently and increase the network lifetime. In clustering, each cluster has a Cluster Head (CH) and the number of Cluster Members (CM) which can make communication only with CH in order to broadcast the data to the Base Station (BS). The role of CH is to collect the data from the CM and it forwards them to the BS and rotates the CH periodically to equalize the energy between the nodes. The CH spends extra energy for gathering data and rotating the CH periodically.

To increase the network lifetime and utilize the energy efficiently, the authors proposed and evaluated a Balanced Unequal Clustering Algorithm for addressing the hot spot problem and increasing the lifetime of the network. It is a distributed unequal clustering algorithm, where CHs are elected based on high residual energy of each sensor nodes and distance from the BS. It divides the nodes into unequal size clusters, and clusters nearer to the BS are lesser in size than those beyond away from the BS.

To conserve more energy for each sensor, the CHs are not elected periodically. It can be re-elected based on some constraints to avoid frequent re-election of CH. The proposed algorithm effectively balances the energy consumption among the sensor nodes and achieves a great improvement in network lifetime.

The rest of the paper is organized as follows: the first section consists of related work. Section 2 describes the proposed work, in section 3 the performance evaluation of proposed algorithm is discussed. The last section contains the conclusion of this paper.

This section briefly discusses some well-known clustering algorithms in WSN. HEED [2]is a distributed clustering algorithms where CHs transfer the data to the BS through multihop communication. It repeatedly chooses CHs based on the residual energy of each node. The hot spot problem is not addressed in HEED.

In LEACH [3], each node selects the CH independently with a probability. CH receives and gathers data from CMs and then sends them to the BS by single hop communication. The CH is rotated periodically to balance the energy consumption among the nodes.

PEGASIS [4] (Power Efficient Gather) is a greedy algorithm, used to chain the header. The CMs in each cluster transmits its data to the header and all the headers send the data to its leader node along the chain, finally the leader node transfers to the BS. The leader node is selected dynamically in the order of the remaining amount of energy.

An Unequal Cluster-based Routing protocol (UCR) [5] is intended for inter-cluster relay traffic, which considers the transaction between the energy cost of links and the nodes’ residual energy [8]. UCR does not require any Special location awareness capability. In real environment, inaccuracy will occur due to the noise.

An Energy-driven Unequal Clustering protocol [6] (EDUC) uses unequal competition ranges to construct clusters of unequal size [10]. Each node behaves as CH only once throughout the network’s lifetime. Thus, EDUC reduces cost and achieves more energy efficiently and balances the energy consumptions between nodes within the cluster.

Energy-efficient Event Driven Clustering (EDC) [7] algorithm can select the CH based on the residual energy of each node which is sensed when an event is occurred. They switched to the active state when several components are in the sleeping state. This approach can maintain the sensor nodes with lower residual energy out of being used up quickly.

Adaptive and Energy Efficient Clustering Algorithm for Event-Driven Application in Wireless Sensor Networks (AEEC) [8], high residual energy sensor nodes have chances to be selected as CH. The energy of each sensor nodes must be distributed evenly among the sensor nodes to extend the network lifetime and a little set of sensor nodes will not be exhausted out very quickly.

PEACH (Proxy-Enabled Adaptive Clustering Hierarchy) [9] forms clusters without additional overhead and supports for multihop communication. It is suitable for both location aware and unaware WSN. The proxy node approach is used to solve the problem of CH having low energy for transferring a data by replacing the CH using the proxy node.

Energy-Driven Adaptive Clustering Hierarchy (EDACH) [10] is an enhanced version of LEACH and PEACH. It increases the network lifetime and constructing more number of clusters in the region relatively distant from the BS. It still employs the same proxy node approach as in PEACH to solve the problem of cluster-head having insufficient energy for carrying out the duty of cluster-head. If a cluster encounters a problematic cluster-head, then a proxy is selected to operate in replacement of the original cluster-head.

TEEN [11] divides the clusters into second level CH and use the hard threshold and soft threshold to detect the unexpected changes in the environment. The hard and soft thresholds are trying to reduce the number of transmissions to increase the network lifetime. It is proper for critical applications and inappropriate when the user requires the data periodically.

All the above proposed algorithms spend more energy while rotating the CH periodically and gathering data from its CMs. Some algorithm provides the solution for mitigating the hotspot problem and some algorithm concentrated to increase the efficiency of network life time, but both are not addressed together. This paper mitigates the hot spot issue by forming an unequal cluster and increase the lifetime of sensor networks by reducing the number of re-clustering and data gathering in CH.

2.1 Proposed Algorithm

To avoid the energy hole problem, the proposed algorithm constructs unequal size clusters and clusters nearer to the BS are smaller in size. The CH can be re-elected when the energy level of current CH reaches its predefined threshold value which reduces the frequent re-election of CH to increase the lifetime of sensor nodes. In addition, to preserve some more energy, data from the sensor nodes are directly transferred to the nearest CHs which forward them to the BS to avoid data gathering in the CH.

2.2 Network Model

The proposed algorithm considers a set of sensor nodes that are evenly distributed in square field area. The network model is given in Figure 1. BS is placed at the centre of the area. Sensor nodes and the BS are all immobile after deployment. Sensors are homogeneous and assign a unique ID for each node. If the transmission power is given, a distance from one node to another node is calculated based on the received signal strength. The radio energy dissipation model [12] is used to transmit k bit message over a distance d:

(1)

Where E_elec denotes the electronic energy and the ratio of €fs and €mp is constants, that denotes the amplifier energy to keep the suitable signal to noise ratio. To receive the message, the energy spent for the radio is.

(2)

After the deployment of sensor nodes, the BS broadcasts ADV-Msg to all nodes within the radio signal r, to calculate the remoteness from BS to node itself corresponding to the received signal power. To produce an unequal cluster, each node has to compute its own competition radius. The radius of the cluster is defined as following:

(3)

Where d_max and d_min denotes upper limit and lower limit between sensor nodes and BS, d(si, BS) is the distance between si and the BS, c is a constant coefficient between 0 and 1, R^oc is the highest competition radius which is assigned previously.

Each node broadcasts HELLO-Msg to its neighbor within the range of d_max and collects the information such as node ID, residual energy and number of neighbor nodes.

After receiving the HELLO-Msg from the neighbor, it calculates the average residual energy of the sensor node as follows:

(4)

Where s_i represents one of the neighbor nodes, si E_r specifies the residual energy of s_i, and d is the number of  neighbor nodes. Node s_i is selected as CH if it has the highest residual energy among all neighboring nodes, and broadcast a HEAD-Msg to its neighbor within the range of d_max . Each node chooses the nearby CH and sends the JOIN-Msg which contains the node id and its residual energy. The pseudo code of selecting a CH is:

Algorithm 1:

cluster-head selection
Begin
Status=unknown
t=waiting time to broadcast CH message
r=radio signal
while (status=unknown) do
broadcast ADV_msg within r
compute R_c competition radius
broadcast HELLO_Msg from node i to neighbor node j
collect neighbor node information
update it in neighbor node table
calculate average residual energy
if (E_i >E_j ) then
broadcast HEAD_Msg(ID=i, d, E,NN)
exit
if (current time>t) then
if (HEAD_Msg receives from node i from node j) then
status=unknown
else
continue
endif
else
status=header
broadcast HEAD_Msg to its neighbor
send JOIN_Msg from node j to node k
endif
if status=header then
receive JOIN_Msg from its neighbor node
set status=member
endif
endwhile
end

After the CH is initialized, set minimum residual energy as a threshold value RE_min . Broadcast THRE-Msg to all the CH for re-electing the CH. When the CH reaches threshold value, then the CH can be re-elected. The pseudo code of reelection of CH is:

Algorithm 2:

Re-election of CH
RE_min =minimum residual energy
Broadcast THRE-Msg(ID,E ) message to all the CHs min
RE=current CH residual energy
While (RE > RE_min ) do
Call the cluster setup procedure
Reselect the CH
End while
End

Once the cluster formation is finished, data transmission begins. In some proposed algorithms [3-11], the CHs summarizes the data from its CM and forwards the data to the BS in multihop communication. In this paper, the incoming data is forwarded to the nearest CH instead of forwarding to the CMs to avoid data gathering. Each CH chooses a next CH to forward its data from its nearest neighborhood CHs. The pseudo code for choosing the nearest CH for data forwarding is:

Algorithm 3:

Choosing nearest CH for data Transmission
DTHR=min
Si=CH
d=distance from s_i to BS
if (d <  DTHR ) then
s_i directly communicate with BS
else
repeat
s_i selects s_j from its neighbor
if(s_j=CH of neighbor cluster)
Forward the data from s_i to s_j
endif
While (s_j =CH)
Endif

The distance from the CH to the BS is less than the assigned threshold value, then the CH directly communicates with the BS, Otherwise choose the relay node s_j for forwarding a data to BS. If s_j is a CH, then forward the data, otherwise, repeat the steps to select the CH as a node with high residual energy among the neighborhood CH.

Each CH consumes some energy for selecting a relay node to forward the data to the BS. The formula for calculating the energy consumption for choosing the next hop as CH is.

(5)

Where d (s_i,BS) is the distance from the current CH si to the BS. s_j is the next hop for si. d (s_i,s_j) is the distance from current CH to the next CH s_j .

Figure 1. Network Model

In this section, the performance evaluation of Proposed Algorithm is compared with HEED and LEACH. In HEED, CHs transfer the data to the BS through multihop communication. It repeatedly chooses CHs based on the residual energy of each node. The hot spot problem is not addressed in HEED. So balancing the energy consumption is difficult. In LEACH, the energy consumption is more because of the cluster head that transmits their data using single hop communication to the BS. Since the distribution of CH is uncontrolled there are significant changes in the energy consumption of CH. Proposed Algorithm generate more clusters than HEED and LEACH.

The simulation is designed and implemented in NS 2.34 in order to examine the energy efficiency and network lifetime of the proposed algorithm. The parameters used in the simulation are shown in Table 1. Let us assume a homogeneous Wireless Sensor Network with 250 nodes deployed evenly in a square field. The BS is positioned at the midpoint of the simulation area. The 0 and the maximum value are assigned for the X and Y coordinates of each sensor nodes. The authors evaluate the performance of our algorithm with HEED and LEACH. There are five metrics chosen for comparison: Residual Energy of each node, CH re-election, Network lifetime, Packet Delivery Ratio, Energy Consumption.

Table 1. Parameters used for simulation

Figure 2 shows that proposed algorithm avoids the hot spot issue by increasing the number of clusters nearer to the BS when increasing the number of nodes in sensor fields.

Figure 2. Number of Clsuters formed in HEED, LEACH and Proposed

Figure 3 shows the number of CH re-elected with respect to the number of nodes. The initial energy of each node is assigned as 2 Joule. The minimum energy is 0.2. The CH reelection is reduced when comparing with HEED and LEACH. This will preserve some more energy to increase the network lifetime.

Figure 3. Number of CH re-elected per round

3.1 Network Lifetime

Figure 4 clearly shows that the nodes nearer to the BS die much faster than the nodes farther away from the BS. Compared to HEED, our proposed algorithm increases the network lifetime of each node nearer to the BS by increasing the number of nodes closer to the BS and it will avoid the node from dying earlier.

Figure 4. Number of Alive nodes over time

3.2 Energy consumption

The graph for energy consumption vs. number of nodes of the proposed algorithm and existing algorithms HEED and LEACH is shown in Figure 5. The total energy consumption includes energy consumption in transferring and receiving a packet in a given time. The transmission consumes greater energy than reception for transferring data packets while calculating total energy consumption in our simulation. The sensor nodes in HEED and LEACH consume more energy to communicate with the BS because of the longer distance between sensor nodes and the BS. However, in the proposed algorithm, the number of clusters nearer to the BS are more than HEED and LEACH. The total energy consumption of HEED, LEACH and Proposed Algorithm algorithms increases when number of nodes or traffic load increases. However, performance of the Proposed Algorithm is improved than HEED and LEACH for different number of nodes.

Figure 5. Energy Consumption using HEED, LEACH and Proposed

3.3 Packet Delivery ratio

Packet delivery ratio is the proportion of the total amount of packets reaching the receiver and the amount of packets transferred by the source. Mathematically we can define as

(6)

Figure 6 gives the percentage of packets delivered for each round using Proposed Algorithm, HEED and LEACH algorithms for WSNs. Figure 6 illustrates that the proposed Algorithm provides high packet delivery ratio compared with HEED and LEACH algorithm. Table 2 shows the performance metrics comparison among the three protocols.

Figure 6. Packet Delivery Ratio of HEED, LEACH and Proposed.

Table 2. Performance Metrics comparison among three protocols

The authors have proposed a Triggering Energy Efficient Clustering scheme, which selects the CH with high residual energy and number of neighbor nodes. The CH uses uneven competition ranges to construct clusters of unequal sizes to mitigate the energy hole problem and the clusters nearer to the BS are smaller in size in order to increase the network lifetime. The CH can be re-elected based on the predefined threshold value to preserve more energy and it reduces the frequent re-election of CH. Thus, the proposed Algorithm minimizes the energy consumptions among the nodes and increases the network lifetime of the networks to a great extent when compared with HEED and LEACH. In future, the authors will implement the fault tolerance mechanism for the proposed algorithm.