Wireless Sensor Network (WSN) comprises of sensor nodes that communicate over a common wireless channel via wireless links in an adhoc manner for the purpose of data collection. These are self-configuring and dynamic networks in which the nodes are free to move. The wireless sensor networks form a subset of Ad-hoc networks where each node is equipped to work on their own without routers to process their packets to their destination. These nodes communicate with each other to reach a common goal such as collection of information. Though the WSN forms a subset of Ad-hoc networks, the protocols designed for ad-hoc networks cannot be used directly for the WSN (Sharma & Mittal, 2013). This is due to two reasons. Firstly, the number of nodes in a WSN is very large and thus requires more scalable solution than ad-hoc networks. Secondly, the nodes in WSN have limited energy capability and recharging the nodes is impractical considering the factors of large numbers and the deployment area. Hence, the energy consumption becomes an important criterion in every aspect of Wireless Sensor Network (Mamalis, Gavalas, Konstantopoulos, & Pantziou, 2009).

A typical wireless sensor network comprises of nodes that are deployed randomly and work in cooperation with each other to gather information. They sense the environment and communicate this information to a primary data collection centre called Base Station via wireless links. The base station is a central data centre, where all the data is stored after collection from the network and can be accessed by the outside world. The sensor nodes are called motes that are the individual computers, which act as a node in the network. Each mote consists of a microprocessor, sensors, transceiver, and batteries (Culler-Mayeno, 2006). The sensors are used to collect data, which is temporarily stored in memory and then transmitted to base station. Motes communicate with each other and the base station using radio transmitters and receivers.

It is necessary for WSNs to operate unattended in difficult terrain, which cannot be accessed easily or human intervention is not feasible or cannot be managed efficiently. Also, the WSNs have an inherent ability to overcome a node failure, by simply using another routing path (Nack, 2010). So even if a node gets destroyed, the network does not have a catastrophic failure. The constrained power supply for nodes posess a variety of limitations, such as the network lifetime, cost for transmission to large distances, etc. Also, the cost involved in replacement of nodes is high as the deployment is generally done by using uncontrolled means such as dropping from helicopters, etc. (Mamalis et al., 2009) and the number of nodes are large, generally few hundreds. Clustering or grouping of nodes offers a good solution for prolonging the network lifetime. Clustering partitions the whole network into fragments where each fragment is used to represent an area. Each cluster has its own leader called a Cluster Head (CH) and the members are called Sensor Nodes (SN). The cluster head acts as a local coordinator and gathers the information from the cluster which is then communicated to the data processing centre. The two main operations per formed by CH are data aggregation and communication with the base station. The nodes in the cluster convey the information when data arrives, to its nearby Cluster Head nodes, rest of the time the sensor nodes may be in passive state. The cluster head acts as a communication centre, so the battery of the cluster head is reduced very fast (Jadidoleslamy, 2013). Thus, various algorithms have been developed for the selection of cluster heads. The clustering algorithm describes how the cluster formation process takes place and how the cluster head is selected among all the nodes.

Hybrid Energy Efficient Distributed Clustering (HEED) is a clustering algorithm, which aims at ensuring extended life time and reduced power consumption (Younis & Fahmy, 2004). The selection of Cluster Head is based on the highest residual energy and the node proximity to its neighbours. In this paper, a new algorithm is presented which changes the initialisation stage of the HEED algorithm. It performs better when compared to HEED in case of heterogeneous node batteries. It also enhances the average energy of each node in the network and reduces the number of dead nodes in the network. More precisely, the authors propose to apply the clustering process in the neighbourhood area of each node and selection of Cluster Head is based on the highest residual energy. The results of the proposed algorithm are compared with LEACH and HEED. It outperforms these clustering algorithms when the average energy of each node and number of dead nodes are considered as it improves the average energy in the network with decreasing the number of dead nodes in the network.

The main contribution of this paper is as follows:

• The HEED clustering algorithm has been explored for performance improvements with an in-depth discussion of the case for heterogeneous node batteries.
• A new model of clustering is proposed which extends the network lifetime and optimises the selection of cluster heads for HEED clustering algorithm.

Wireless Sensor Networks have found hundreds of applications to simplify the monitoring process in complex areas. The prime concern for WSNs is the energy consumption as the increase in network lifetime depends mainly on minimising the energy consumption in sensor nodes. Thus, conserving and minimising the energy consumption is of utmost importance. The clustering algorithms form an integral part in Wireless Sensor Networks with the challenge of designing algorithms with minimum energy dissipation. There are various applications associated with these schemes, such as reducing the size of routing table, stable network topology, only the CHs need to maintain the route information, lowering energy consumption, and so on. Thus, looking at the benefits of clustering algorithms for these networks, it was found that these could be further explored even if a lot of work has been done before. Analysing the existing algorithms gives an insight on how new clustering algorithms can be produced or how the existing algorithms can be made more efficient in order to provide better functionality to the WSN. The new proposed algorithm is based on an existing algorithm called HEED with certain changes for performance improvements.

A lot of clustering algorithms are available for WSNs. In the following, some of the relevant and important clustering algorithms are discussed. Baker and Ephremides (1981) discussed the problem of organizing a set of nodes into a connected network, which is reliable and can be maintained in node motion or node failure without the use of any central controller. They proposed an algorithm called Linked Cluster Algorithm (LCA) which tries to maximize the network connectivity.

Amis, Prakash, Vuong, and Huynh (2000) proposed a new distributed clustering algorithm in which no node is more than d hops away from the cluster head and is called Max- Min D-Cluster formation. The earlier heuristic algorithms used only 1-hop distance which may not be possible in certain cases.

Chatterjee, Das, and Turgut (2002) considered the problem of setting up of clusters due to mobility of nodes. They proposed an on-demand distributed clustering algorithm called Weighted Clustering Algorithm (WCA), which takes into consideration various parameters such as transmission power, mobility, battery, etc., and a predefined threshold for bounding the maximum number of nodes in a cluster.

Heinzelman, Chandrakasan, and Balakrishnan (2002) developed an application specific algorithm that performs much better and gives a hierarchical structure to the network. They have proposed a robust algorithm called Low-Energy Adaptive Clustering Hierarchy (LEACH) that is both energy efficient and has a low latency. The algorithm combines the idea of energy-efficient clusters and data aggregation to achieve good performance for network's lifetime. Loscri, Morabito, and Marano (2005) explored the LEACH protocol and proposed an extension to it. The authors have proposed an algorithm by building a two-level hierarchy to achieve better power saving. The algorithm is called Two-Level LEACH (TL-LEACH).

Younis and Fahmy (2004) have discussed that an effective topology control can help in clustering in WSNs. They proposed a distributed clustering approach which do not make any assumptions about the infrastructure or about node capabilities and is called HEED (Hybrid Energy- Efficient Distributed clustering). It selects cluster heads periodically based on the residual energy of each node and node degree. Kour and Sharma (2010) analysed the impact of heterogeneity in terms of node energy in HEED clustering algorithm (Younis & Fahmy, 2004). They concluded that heterogeneous node batteries can improve the network lifetime.

Lindsey and Raghavendra (2002) proposed an algorithm which is based on the greedy approach called Power Efficient Gathering in Sensor Information Systems (PEGASIS). This algorithm is useful in scenario where data collection is required which is not time sensitive.

Li, Ye, Chen, and Wu (2005) have discussed about the hotspots problem in multi-hop Wireless Sensor Networks. To overcome this problem, they have proposed an Energy- Efficient Unequal Clustering (EEUC) mechanism for data gathering in wireless sensor networks and are done periodically. The algorithm partitions the nodes into clusters of unequal size.

Selvi and Manoharan (2014) discussed about the energy hole problem and imbalance of energy consumptions among the nodes due to periodic re-election of CH. They proposed a distributed unequal clustering algorithm, where the election of CHs is based on high residual energy and the distance from the BS. The algorithm partitions the network into unequal size clusters as in EEUC. To conserve more energy for each sensor, the CHs are not elected periodically, but re-election takes place when the residual energy of any CH reaches the threshold; the least residual energy of a node when the election took place.

In (Aierken, Gagliardi, Mostarda, & Ullah, 2015), the authors present a rotated unequal clustering protocol (RUHEED), which combines the benefits of unequal clustering and HEED. The CHs are elected according to HEED, but the cluster radius is decided by using the unequal clustering as in (Li et al., 2005).

Usha and Sankarram (2014) presented a survey of the various descendents of LEACH clustering algorithm for WSNs in 2014. The main challenges for clustering algorithms, their advantages, and disadvantages were discussed.

The authors have summarised a total of ten descendents of LEACH, namely E-LEACH, TL-LEACH, MLEACH, V-LEACH, LEACH-C, TB-LEACH, LEACH-MOBILE, LEACH-ET, LEACH-B, and LEACH-A. They also have compared these clustering algorithms with the basic LEACH implementation. The authors in (Al-Baz & El-Sayed, 2018), proposed a new algorithm called node ranked-LEACH as an improvement to existing LEACH protocol. They inferred that the proposed algorithm gives a good performance in terms of energy consumption and network lifetime in comparison to existing versions of LEACH algorithm.

In (Reddy & Devi, 2018), the authors have compared DEEC, DDEEC, TDEEC, EDEEC, BEENISH, Level-5, and Level- 6 protocols on the basis of their stability period, network lifetime, and the throughput in heterogeneous networks. They concluded that Level-5 performs the best in terms of stability and throughput while in case of network lifetime, level-6 is the most efficient one.

With the proposed algorithm, the authors have explored HEED for further improvements. Due to the chronological order, they first provide an insight into HEED and afterwards discuss the enhancements offered by the proposed model.

3.1 Hybrid Energy-Efficient Distributed Clustering

It uses the residual energy and the communication costs for electing the cluster heads. The operation of HEED is divided into three phases, namely initialization phase, iterative phase, and the final phase. In the initial phase of HEED, each node listens and broadcasts its cost to its neighbours and computes an initial probability (CHprob) of becoming a cluster head. The initial probability of becoming a CH is computed as given in (Younis & Fahmy, 2004) is below:

(1)

where CH_prob is the initial probability of becoming CH, C_prob is an initial percentage of cluster heads among all N nodes and has no direct impact on the final clusters. It is used to limit the initial CHs announcements to the sensor nodes. E_residual is the total energy left in a node, and the E_max refers to fully charged battery, which is the maximum initial energy of the node. The CH_prob is not allowed to fall below a certain threshold p_min, which is selected to be inversely proportional to E_max.

In the iterative phase or the main processing phase of HEED, each node executes this phase till either its probability (CH_prob) to become CH reaches 1 or it listens from a tentative CH or a final CH. A tentative CH is a sensor node which is elected in random election and whose CH is less than 1. A tentative CH_prob can change its status to a regular node in later iteration if it listens from a lower cost CH. A final CH is a node which has attained CH as 1. prob Finally, each node doubles its CH value and goes to the prob next iteration in this phase. This phase is executed for a number of iterations N_iter.

In the final phase, each node finds the CH to whom it can transmit to with the least cost. If a node hears from no CH, the node elects itself to be a new CH and then sends a broadcast message to its neighbours to inform them about being elected as a CH.

HEED also uses a secondary parameter called Intra- Communication Cost for CH election. Generally, a node in WSN has a few transmission power levels. Larger the power level, larger is the distance that can be covered in transmission. In other words, greater transmission power level corresponds to the greater coverage area of the node. The cluster radius or coverage is defined by the transmission power level used for intra-cluster announcements during clustering. HEED uses intra-cluster communication cost for deciding the CH in case of multiple candidates in the same cluster range. The node with the lower intra communication cost is preferred.

If the power level is fixed for all nodes for intra-cluster communication, then the cost can be computed using the node degree. If there is a need to distribute load among cluster heads, then the cost is proportional to node degree while for creating dense clusters, then the cost is considered proportional to 1/node degree. In other words, a node joins a cluster head with minimum degree to distribute cluster head load or the one with maximum degree to create dense clusters.

3.2 Proposed Algorithm

The proposed algorithm improves the performance of the network when heterogeneous node batteries are used. It also improves computation cost in HEED by eliminating the division operation in computing the initial probability (CH_prob) to become CH in the initialisation phase. As the division operation is costlier than the other operations, thus eliminating it can reduce the computation cost involved in the initialization phase. Also, when the initial probability to become CH is computed for each round of election of Cluster head in HEED, the maximum energy for each node is constant and thus it does not have a direct impact on election of final clusters. It is only used to bound the CH_prob to range (0, 1). They have computed the likelihood (CH_likelihood) of a node to become a Cluster head is described below:

(2)

where the symbols have their usual meaning. Using the above equation (2), the likelihood CH_likelihood computed is directly proportional to the residual energy of the node. It is analogous to the CH_prob used in HEED. The CH_likelihood for a node with higher residual energy has a greater value than the nodes with lesser residual energy. Therefore, the chance of a node to become a CH is higher for the nodes with higher residual energy. Like in HEED, the CH_likelihood is not allowed to fall below a certain threshold p_min for terminating the algorithm in N_iter= O(1) time.

When the heterogeneous node batteries are used in HEED, due to the presence of different E_max for different nodes, the CH_prob is not equivalent. The node with greater residual energy with larger battery may have same probability (CH_prob) to become a CH with the node with lesser residual energy with smaller battery. For example, consider the case when we have two types of node batteries (say 2 J and 3 J) in the network and the initial percentage (C_prob) of CHs is 5%. Consider any two nodes with fully charged batteries: 2 J and 3 J and their respective residual energies: 1 J and 1.5 J. The CH_prob as computed by equation (1) for HEED is 0.025 for both nodes, but the residual energy of the second node is greater than the first node. Now consider the same case in the proposed algorithm, the likelihood (CH_likelihood) to become CH for the nodes as computed by equation (2) is given as: 0.05 and 0.075. Thus, the chance of the second node to become a CH is greater and so is its residual energy. Hence, the results for proposed algorithm are better when compared to HEED.

There is another change made in traditional HEED in this algorithm. In the proposed model, the set of tentative Cluster Head (SCH) is evaluated for the neighbourhood of a node only, i.e. the tentative CHs are added to the set if it lies in the cluster radius of a node. In other words, the set SCH may contain different nodes in different portion of the area, where the deployment is made. This is done as maintaining the global information of the set of tentative Cluster Heads SCH may results in greater number of transmission messages and thus causing dissipation of noticeable energy which decreases the network lifetime.

The proposed algorithm also reduces the number of communication messages that are sent in the network as some of the statements in traditional HEED were redundant, so they are eliminated in the model. Thus, lesser number of CH (final and tentative) announcements is made, which reduces the energy consumption in the network as energy is consumed for both the transmission and reception of messages. The pseudocode for the proposed algorithm is given in Figure 1. It is similar to the algorithm given by (Younis & Fahmy, 2004) and it includes the changes that are made for the proposed model.

Figure 1. Pseudo Code for Proposed Algorithm

The algorithm proceeds in three stages, namely the initialization stage, processing stage, and the finalization stage. At the end of each TCP, each node is either a CH, or a regular node that belongs to exactly one cluster.

In the initialization stage, each node computes its neighbourhood set S_nbr. Once the neighbourhood is computed, the cost of the node is broadcasted to neighbourhood for finding the intra-cluster communication costs. Once initialization is completed, the nodes begin with the processing stage and repeat till the node is uncovered or becomes a final cluster head (final_CH). When a node listens to the cluster head announcement made by any of its neighbour, it quits the election procedure and wait till all nodes complete the processing stage. If a node i becomes a tent_CH, it finds the set SCH which consists of all the tent_CH in the neighbourhood S_nbr of the node i and the node itself. If the node i does not have the least_cost, then it quits the election and consider itself covered. Otherwise, it waits to become a final_CH till its CH_likelihood becomes equal to the E_max of the node. Similarly, a normal node becomes a final_CH when its likelihood CH_likelihood becomes equal to likelihood E_max of the node. Note that each node has its own E_max value. The tentative CH is selected randomly, but this randomness is also based on its probability (CH_likelihood) to become a CH.

In the finalization stage, each normal node chooses the least cost CH. If a node listens from no final_CH then the node becomes a final_CH itself and broadcast its status to its neighbourhood S_nbr.

The proposed clustering algorithm is simulated in MATLAB (MATLAB, 2015). MATLAB is chosen due to its high ability in mathematical calculation and results visualization. The simulations are done by using a field of dimension 100 by 100 meters and by considering 300 sensor nodes, which are uniformly distributed in the field. Sensor nodes have heterogeneous node batteries. Each experiment consists of 5000 rounds of clustering process. The average energy of each node and number are dead nodes per round are considered with intra communication cost as node degree and 1/node degree. The simulation parameters are those used in (Younis & Fahmy, 2004) and are summarised in Table 1.

Table 1. Simulation Parameters

4.1 Network Model

It is assumed that a set of sensors nodes are dispersed on a rectangular field with the following assumptions about the network:

• The network comprises of heterogeneous node batteries, i.e. type I (=2 J) and type II (=3 J).
• The type of node battery is selected randomly.
• All the nodes have same data communication and processing capabilities
• A unique ID is associated with each node for the purpose of identification
• Nodes can transmit at various power levels depending on the distance of the receivers
• Nodes are quasi-stationary that is they remain almost stationary Nodes are uniformly distributed in the area.

The Base Station is located away from the sensing field at (50,175) and is stationary. We use the network operation model that is presented in (Younis & Fahmy, 2004). There are a number of rounds. A round begins by triggering the election of cluster heads and followed by the formation phases. When the clusters formation is successful, the network starts a data exchange phase. This includes intra-cluster communication cost, where each sensor node sends one message to its CH and inter-cluster communication, where each aggregated data is sent by the CH to the BS. The network structure is shown in Figure 2, where the black node represents the node with 2J battery and blue node represents a node with 3 J battery.

Figure 2. Network Grid of 100 x 100 m with 300 nodes and a Base Station

The radio model employed uses both the free space and the multi-path channel model and assumes errorfree communication links. The area under simulation is 100 by 100 metres. The base station is located at (50,175). To run the transceiver circuitry each node spends E_elec= 50 nJ/bit while the energy spent by the amplifier E_amp is dependent on the distance d between the sender and the receiver. For d < d_o (d_o =75 m), the free space model is used for which E_amp = E_fs = 10 pJ/bit/m² while for d > d_o, a multipath model is used where E_amp = E_mp = 0.0013 pJ/bit/m⁴. The energy dissipated in transmission ETX to send an n-bit packet can be calculated by using the following formula (for details refer (Heinzelman et al., 2002)):

(3)

where d is the distance of the receiver and K = 2 for the free space model and K = 4 for the multipath model. The amount of energy dissipated for reception ERX for receiving an n-bits of a message can calculated as follows (for details refer (Heinzelman et al., 2002)):

(4)

where n refers to the number of bits to receive and E_elec is the energy dissipated to run the transceiver circuitry.

4.2 Results

Figure 3 shows the number of dead nodes in the network in each round. We can clearly see that the number of dead nodes per round is less for the proposed algorithm. The number of dead nodes allows us to record the time last node dies in the network and the network ceases to exist.

Figure 3. Number of Dead Nodes for Network Grid of 100 x100 m with 300 Nodes and Clustering Radius 50 m

Number of dead nodes also gives an insight on how many nodes were still present to perform the operation of monitoring in the network when some of them were dead. If a node is still present in close proximity to the dead node, the network would not miss on monitoring any useful information and thus, the proposed algorithm outperforms the other clustering algorithms as the number of dead nodes were reduced w.r.t each round.

Likewise, the average energy of each node essentially gives a model of the total energy in the network. It represents a value that is most common in the network. Benefit of using this measure is that it is based on energy of all the nodes and is determinate. Secondly, it gives a value as stable as possible. Thus, it can be used to represent the state of the network at any time. Figure 4 compares the average energy of each node in HEED, proposed algorithm (HEED with Improvements) and LEACH for a competition radius of 50 m. The average energy of each node in the proposed algorithm is slightly better in later rounds and the same can be seen in Figure 5. It is taken at 150% magnification of the same graph. Also, similar results were obtained for Wireless Sensor Network with homogenous node batteries for the proposed algorithm.

Figure 4. Comparison of Average Energy of each node in HEED, LEACH, and Proposed Algorithm

Figure 5. Comparison of Average Energy of each node in HEED and Proposed Algorithm

Wireless Sensor Networks are powered by batteries of limited capacity and this remains the main challenge in the design of algorithms for WSN. In this paper, the authors have proposed a WSN clustering algorithm that is based on an existing algorithm called Hybrid Energy Efficient Distributed Clustering (HEED), which selects CHs based on the residual energy and node degree. The proposed algorithm selects a Cluster Head based on its residual energy so the nodes with higher residual energy are more likely to become a Cluster Head in case of heterogeneous node batteries, which was not correctly analysed in HEED. It improves the performance of HEED with various changes in initialization stage, processing stage and by considering multiple candidates only in the neighbourhood of the node. It outperforms HEED and LEACH clustering protocols when the average energy of node and number of dead nodes per round are considered as it improves the average energy in the network with decreasing the number of dead nodes in the network. In future work, they plan to further investigate the performance of this algorithm by varying the competition radius, network grid size, and number of nodes.