The Cluster-Heads Selection Method considering Energy Balancing for Wireless Sensor Networks

Abstract

Wireless sensor networks (WSNs) are self-organizing networks in which sensor nodes with limited resource are scattered in an area of interest to gather information. WSNs need to have effective node's energy management methods for stable and seamless communication. As one of a number of good technical solutions, a clustering technique has been issued and proposed among researchers for reducing energy consumption in WSNs. Also, it can prevent the problem of data duplication by the sensor nodes. Generally, to reduce WSNs' energy consumption as much, cluster heads (CHs) are selected dynamically based on cluster rotation mechanism. However, the CH that is already previously selected could not be selected again unless the round process is over even though the node has more energy than others. Following this fact, in WSNs, there is a kind of irregular energy consumption status among sensor nodes because of CHs' overhead energy usages. To solve this problem, in WSN networks, any sensor node should be a candidate to be CH without any exception even if the node is already chosen before. Therefore, in this paper, we will establish and propose an energy balanced CH selection mechanism and the distribution of sensor node's energy consumption in WSNs for equal and stable energy management.

1. Introduction

In wireless sensor networks (WSNs), the large number of sensors is deployed over a wide range to inspect or measure their environmental performance. Generally, the major responsibility of these sensor nodes in WSN is to detect and collect WSN's environmental data and to send its data into WSN network's external end users. Because the sensor node in WSNs should be operated stably in the irregular deploying fields whose environment is so difficult to be approached or to be much dangerous, mostly, the unattended operation system which is automatically operated by itself without additional operator's action is needed on WSNs communication. To make our goal closer, trusted and stable WSNs operation works in irregular deploying environment, WSNs need to have the self-organizing mechanism which allows the node to implement its network topology by itself and also need the optimizing battery management mechanism. In particular, because the sensor nodes in WSNs have so limited power resources during the operation, the sensor nodes have to do low-powered communication as much [1]. So, following this fact, the issue, which is mostly concerned about in WSNs research area, is that how to manage sensor's energy resources efficiently. The maximum or largest energy consumption of nodes mostly occurred on WSN's sensed data transmission phrase. The sensed data which is detected by a certain node is equally the same thing as its neighbor nodes' one. Thus, WSNs need to have a data aggregation mechanism to prevent duplicated data [2–4]. Normally, a clustering technique is mentioned as one of the most typical data aggregation mechanisms in WSNs because it is possible to avoid duplicating data transmission among nodes by grouping the nodes, which detected similar events during transmission into local cluster [5–9]. To set local cluster as well, the cluster-head (CH) selection process should be preceded mostly. CH, typically, can be selected among deployed or separated nodes in WSNs. Unlike other local cluster's member nodes, CH has usually lots of energy consumption because of its additional energy usages, data aggregation collection. Thus, to migrate with this problem, WSNs need to have new CH rotational selection algorithm which concerns CH's irregular energy consumption problem.

Generally, CH selection algorithm leads WSNs to give their nodes almost equal opportunities to become CH by using mathematical probability process. Applying this concept, WSNs possibly do stable energy balancing during communication as well. But there is an operational limitation that WSNs must concern two measuring criteria during CH selection process, the energy consumption on data collection phrase and local cluster's size. Furthermore, since the process of nodes' battery residual value collection requires a lot of additional energy consumption, it is impossible to calculate an entire WSN network energy usage state to choose a suitable CH node. So, in WSNs, nodes must check their current energy states by themselves and choose a suitable CH based on their calculation analysis results as much. Therefore, in this paper, we propose the CH self-selection mechanism based on nodes' energy residual value comparison algorithm to migrate these problems.

2. Backgrounds

Many clustering algorithms have been proposed to select a suitable CH by many researchers. Among these algorithms, LEACH [10] is one of the most typical proposals that lead WSNs to disperse sensor nodes' energy problems as formed local cluster. To be detailed, this algorithm is able to solve nodes' energy traffic problem by pointing a certain CH out, with a certain numeric probability, per a certain round time, one time selection per one round. After forming local cluster, LEACH-C [10] puts CH on the center of local cluster to reduce the cost of energy transmission among member nodes. But this proposal requires additional energy cost to select a new CH and to track a new trajectory for finding out the geographical local information of local cluster. The major characteristic of deterministic cluster-head selection [11] is to calculate the level of nodes' remaining energy as the acceptable probability rate of CH selection. However, this mechanism requires additional energy consumption because all nodes should share their current energy states when CH selection process. Other CH selection proposals [12, 13] also have the same additional energy costs to select CH because of sharing nodes' current energy information. To overcome this limitation, all nodes have to apply probability to the CH selection-making process by estimating the probability as CH candidates like LEACH algorithm.

LEACH circulates a CH to distribute all sensor nodes' energy consumption and manages a local cluster by the CH.

LEACH circulates a CH to distribute all sensor nodes' energy consumption and manages a local cluster by the CH. It is composed of a “set-up” phase for clustering and “steady-state” for the time division multiple access (TDMA) frame. In accordance with (1), all sensor nodes can be elected as a CH using a threshold ( $T (n)$ ) in the “set-up” phase. A node with a lesser value than the threshold can be elected as a CH after it chooses a random value between “0” and “1.” The “G” means the set of nodes that can be selected as a CH. The “otherwise” means that node “i” has been a cluster head. Consider

\begin{matrix} T (i) = {\begin{cases} \frac{p}{1 - p * (r \mod (1 / p))}, & i \in G, \\ 0, & otherwise . \end{cases} \end{matrix}

(1)

In (2), “i” is the number of nodes, “p” is the ratio of CHs,“r” is the current round, and “G” is the set of nodes that are not selected as a CH. Each node can be selected as a CH once per 1/p rounds. A higher number of rounds mean that there is a higher probability that a node will be selected as a CH. After 1/p rounds, all nodes would be selected as a CH, by setting the threshold as “0.” But LEACH cannot guarantee equal clustering. This can cause an imbalance of a local cluster [11].

E_{i} (t)

is the current energy of node “i” with time “t,”

E_{total}

(t) is the total energy of all nodes with time “t,” and

P_{i} (t)

is the CH probability of node “i” with time “t”. Cosider

\begin{matrix} P_{i} (t) = \min {\frac{E_{i} (t)}{E_{total} (t)} p, 1} . \end{matrix}

(2)

This method is for energy distribution, as all sensor nodes would be selected as a CH after 1/p rounds. This helps nodes achieve efficient energy conservation, since nodes that have high residual energy are elected as CHs. However, it does not consider unequal energy consumption of nodes by unequal clusters. The elected CH is not reelected as the CH during 1/p rounds, although the node has more energy than the others in the cluster. For example, if there are N nodes, the number of CHs is N*p, k. The average number of nodes in a local cluster is N/k. We assume that the probability that a local cluster has N/k nodes is P. The probability should be P, 1/p to manage P from 1 round to 1/p rounds. But the probability is remote. Thus, a method to overcome unequal clustering is needed.

The soft-threshold method [14] is used to select adaptive cluster heads among normal sensor nodes by using a constant ε value. However, this technique does not have guaranteed equal energy consumption among nodes, because it does not consider the energy status of nodes, especially in CHs.

The energy adaptive cluster-head selection (EACHS) algorithm [15] compares the average energy of every node with its remaining energy and the energy consumed for data transfer from the former round. The selection probability of the CH increases if it has more energy and decreases if it has less energy; that is, the selection of the CH is based on the energy level. $E_{rest}$ is the rest energy of a node in this round, $E_{diss}$ is dissipation of a node in this round, and $E_{ave}$ is the average energy consumption of a node. Cosider

\begin{matrix} C H_{prob} = \frac{p}{1 - ((r + 1) \mod (1 / p))} \times [\frac{E_{resi} - E_{diss}}{E_{ave} - E_{diss}}] . \end{matrix}

(3)

However, as (1) shows, a node can be not selected if it was a CH in the same round. In addition, EACHS may consume additional energy to compare the threshold method, since it requires the exchange of information between nodes to calculate the average energy of nodes. This mechanism also need to calculation of the probability that a node could be selected as a CH. So, we present the new cluster head selection algorithm to solve three problems. First, it have to require noadditional energy consumption by exchanging energy condition information. Second, it can re-select a node as a CH though it was elected in current round. Finally, it can calculate the CH qualification by each node using remaining node energy.

3. (Energy Balanced Cluster-Heads Selection) EBCHS

The previous section showed that the energy gap between a CH and a member node is large due to the additional cost of the CHs. Generally, a member node simply detects changes in its surrounding environment and transmits the sensed data to a CH. The amount of aggregated data produced by a CH depends on the number of its member nodes. Thus, the energy consumption of a CH is higher than that of the other member nodes. To manage the energy balance between nodes, the WSNs require a novel CH selection algorithm that considers the energy status of the CHs. Our proposal is called the energy balanced cluster-heads selection (EBCHS) algorithm and it uses a threshold, $T (i)$ . As shown in (1), if r is 0, $r = 0$ , the probability of all sensor nodes, ${T (i)}_{r} = 0$ , is p because not all sensor nodes have been selected as a CH. The scattered nodes of WSNs are “N.” Thus, we revised this equation. Equations (4) and (5) are based on LEACH and EACHS. The purpose of proposed equation is guaranteed to prevent additional communication cost and reelect CH role before 1/p rounds. Energy consumption model is also based on LEACH algorithm and is referenced by [10].

Like (1), if $r > 0$ , the threshold value of a node selected as a CH can be reduced by the amount of energy consumed. This means that the consumption energy ratio, ${T (i)}_{r > 1}$ , can calculate the previous threshold value, ${T (i)}_{r - 1}$ , and the current threshold values, T(i). T(i) consists of two threshold values: ${T (i)}_{r_ch}$ , ${T (i)}_{r_mem}$ . ${T (i)}_{r_ch}$ is the amount of energy drain ratio of remaining energy in a CH, and ${T (i)}_{r_mem}$ is the amount of energy drain of remaining energy in a member node. $E_{mem_diss}$ is energy consumption of member nodes, $E_{ch_diss}$ is energy consumption of cluster heads, and $E_{remaning}$ is remaining energy of nodes. Cosider

\begin{matrix} T {(i)}_{r = 0} = {\begin{cases} \frac{p}{1 - p * (r \mod (1 / p))} = p, & i \in N \end{cases}, \end{matrix}

(4)

\begin{matrix} T {(i)}_{r > 1} = {\begin{cases} T {(i)}_{r - 1} - T {(i)}_{r_mem}, & T (i) > 0, \\ T {(i)}_{r - 1} + T {(i)}_{r_ch}, & T (i) \leq 1, \end{cases} \end{matrix}

(5)

\begin{matrix} T {(i)}_{r_mem} = \frac{E_{mem_diss}}{E_{remaining}}, \end{matrix}

(6)

\begin{matrix} T {(i)}_{r_ch} = \frac{E_{ch_diss}}{E_{remaining}} . \end{matrix}

(7)

When

{T (i)}_{r = 0}

, all nodes are selected as a CH at least once during 1/p rounds. In the next round of CH selection, the nodes' threshold value that is used with CH selection is different, as it is the CH energy consumed in its local cluster. This difference stems from the fact that the number of member nodes in local clusters varies. If a CH has fewer member nodes than the average number of member nodes, the threshold value is also lower. This means that the CH can be reselected during 1/p rounds. This will result in a better energy distribution for sensor networks and increased network lifetime.

4. Simulation Setup and Performance Analysis

4.1. Network Setup for Simulation

An ns2 [16, 17] simulator was used to evaluate the proposed algorithm. Ns2-allinone-2.27 was installed in cygwin of Windows XP SP3. The sensor network environment is as follows: a wireless channel, two ray ground radio-propagation model, physical wireless and MAC 802.15.4 protocol, Queue/DropTail/PriQueue, OmniAntenna, and LEACH routing protocol. The data referenced by the sensor network references was from a real sensor node, MiCaz, based on the 802.15.4 data packet [18]. This is a 29-byte packet. We configured the network size to be 100 m × 100 m. The number of sensor nodes was N. The number of CHs per round was 5% of the total number of nodes, as in LEACH. Thus, p is 5%, and the number of CHs per round is 15. We set the data packet size as 34 bytes, the header as 5 bytes, and the payload as 29 bytes. The sink node location is (0, 0). We assume that a node can transmit k (bits) data to a sink or neighbor node 10 m from a node.

4.2. Performance Analysis

We have to know the number of sensor nodes in the range of a 100 m × 100 m network, so that sensor nodes can communicate without generating an isolated node in the network; that is, we have to calculate the number of nodes needed to avoid generating an isolation node, when any node is put into the sensor network. An isolation node is not generated if we have about 100 nodes when the nodes are put into the network in a grid pattern. However, we have to determine an isolation node by the following experiment, when nodes are put into the network randomly. N, the number of sensor nodes in the network, is 300, 250, 200, 150, 100, and 50. Since each sensor node is placed in the network randomly, we can determine the number of isolation nodes, as shown in Figure 1, if the isolation node is defined as a node that is unable to communicate with any other node. The higher the number of sensor nodes, the fewer the number of isolation nodes. When N is 50, the network cannot function, because about 21 nodes, or 42% of all nodes, are isolated. When N is 150, about 3 nodes, or 2% of all nodes, are isolated. In that case, the network is not affected. However, over 300 sensor nodes are required for a normal network environment, since isolation nodes cannot connect to any CHs or neighbor nodes.

Figure 1

Average number of isolation nodes.

The proposed method, energy balanced cluster-heads selection (EBCHS), is nearly equivalent to the previous method, in the first clustering round. Therefore, we will compare the average energy consumption of nodes when $r > 1$ . We assume that “1” round time is the time to select a CH 20 times. Figure 2 compares the existing methods, LEACH and EACHS, which determine the regular size of a CH, as a regular probability p, and the proposed method EBCHS. In Figure 2, while a node selected as a CH cannot be reselected until the end of the round in the LEACH and EACHS methods, the node can be reselected in the EBCHS method, depending on its remaining energy. Therefore, the number of times that each node can be selected as a CH is different; that is, each node can only be selected as a CH five times during the 5*1/p rounds of the LEACH and EACHS methods. However, any node can be selected as a CH, even if a node was selected as a CH in a previous round of the EBCHS method. Thus, there is a wide variation in the number of times each node can be selected as a CH.

Figure 2

The number of cluster-heads counts per a node after 100 rounds.

However, even though a node selected as a CH executes additional work several times over in EBCHS, it is possible to distribute the energy of the CH, because a CH is selected depending on the residual energy. Figure 3 shows the maximum (0.00295 joule) and minimum (0.00143 joule) energy consumed in LEACH (50) and the maximum (0.00318 joule) and minimum (0.00068 joule) energy consumed in EACHS (50) after each algorithm was executed around 50 times. Both methods incur an energy difference between nodes, so it is hard to balance energy consumption between nodes. Conversely, in the proposed method, EBCHS (50), a maximum energy of 0.00270 joule and a minimum energy of 0.00172 joule are consumed; namely, EBCHS is better for dispersion of energy consumption. In addition, the maximum and minimum energies are less in EBCHS than in any other method on a round-by-round basis, so energy efficiency is managed equally. After 100 rounds, energy gap between nodes of EBCHS (100) is just 0.00085 joule. But energy gap of LEACH (100) is 0.00201 joule and EACHS (100) is 0.00272 joule. LEACH (50), EACHS (50), and EBCHS (50) are the energy status of nodes after round 50. In the same sense, LEACH (100), EACHS (100), and EBCHS (100) are energy status of nodes after round 100.

Figure 3

Energy consumption per a node after 50 and 100 rounds.

If the energy deviation between nodes is large, a node may be dead due to energy depletion. This can be checked by comparing the number of dead nodes, depending on the energy consumption at each round. In Figure 4, the first node dies at 357 in the case of LEACH. The round of (first node dead) FND is 379 in the case of EACHS. Conversely, the round of FND is 478 in the case of EBCHS. As Figure 4 shows, the round in which the number of dead nodes becomes 10% of all nodes is 432 in the LEACH, 432 in EACHS, and 507 in EBCHS. EBCHS has more rounds, until the number of dead nodes becomes 70% of all nodes. However, nodes are dead consistently after 490 rounds due to unequal energy consumption. Nevertheless, EBCHS consumes less CH energy and distributes less energy between nodes than do others, because at least 50% of nodes should be maintained to operate a network.

Figure 4

Increasing the number of dead nodes per a round.

EBCHS can have equal node energy consumption, because of the energy distribution of nodes through duplicate selection as a CH. Thus, the energy of each node is consumed at constant rate. On the other hand, in EACHS and LEACH, there is a high energy difference between the nodes and CHs, because these methods do not consider the energy consumption of the CHs. the first node dead (FND) round of EACHS and LEACH is shorter than that of EBCHS due to the huge energy consumption of the CHs. After FND, the energy consumption of the CHs is reduced, because they have fewer nodes than the number of nodes in EBCHS. Thus, as implied by Figure 4, the number of dead nodes in EACHS and LEACH increases more gradually than in EBCHS. However, based on the previous isolation node experiment, we know that the network status is normal when the number of nodes exceeds 150. Therefore, EBCHS can maintain a normal network better than other mechanisms by using a minimum of 530 rounds.

5. Conclusion

Clustering methods for wireless sensor networks have been proposed by many researchers. The energy consumption of CHs is higher than member nodes, as CHs incur an additional cost to manage, collect, and aggregate data from member nodes. It is necessary to distribute CH energy consumption using a CH election method. We achieved this by electing CHs according to the residual energy of sensor nodes. This was compared via simulations. The proposed method has a better distribution of energy consumption between nodes than the other methods, and the round in which the first node dies is later than that of LEACH and EACHS. More nodes are alive in stable networks.

Footnotes

Acknowledgment

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2013R1A1A2063180).

References

Tubaishat

Madria

Sensor networks: an overview

IEEE Potentials 2003 22 2 20 23

2-s2.0-4143104126

10.1109/MP.2003.1197877

Akylidiz

I. F.

Sankarasubanmaniam

Cayirci

A survey on sensor networks

Communication Magazine 2002 40 102 114

Wang

Xie

Yang

Data compression algorithm based on hierarchical cluster model for sensor networks

Proceedings of the 2nd International Conference on Future Generation Communication and Networking (FGCN '08)

December 2008

319 323

2-s2.0-62449316459

10.1109/FGCN.2008.96

Meng

Yang

Jeong

B.-S.

Lee

Y.-K.

Lee

Fan

Query aggregation in wireless sensor networks

International Journal of Multimedia and Ubiquitous Engineering 2008 3 1 19 26

2-s2.0-84255189935

Haider

Javed

M. Y.

Khattak

N. S.

Design and implementation of energy aware algorithm using greedy routing for sensor networks

International Journal of Security and Its Applications 2008 2 2 71 86

2-s2.0-84858270056

Nikdel

Kohshoori

M. S.

Jamei

S. M.

An intelligent and energy efficient area coverage protocol for wireless sensor networks

International Journal of Grid and Distributed Computing 2011 4 4 41 56

Sheikhpour

Jabbehdari

Khadem-Zadeh

Comparison of energy efficient clustering protocols in heterogeneous wireless sensor networks

International Journal of Advanced Science and Technology 2011 36 27 40

Akhtar

R. A.

Minhas

A. A.

Jabbar

Energy aware intra-cluster routing for wireless sensor networks

International Journal for Hybrid InFormation Technology 2010 3 1

Heizelman

W. R.

Asan

A. C.

Balakrishnan

Energy-efficient communication protocols for wireless sensor networks

Proceedings of the Hawaii International Conference on Systems Sciences

January 2000

10.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

11.

Handy

M. J.

Hasse

Timmermann

Low energy adaptive clustering hierarchy with deterministic cluster-head selection

Proceedings of the 4th International Workshop on Mobile and Wireless Communications Network

September 2002

9 11

12.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

13.

Ibriq

Mahgoud

Cluster-based routing in wireless sensor networks: issues and challenges

Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS ’04)

July 2004

759 766

14.

Rong

Bing

Lei

Jiawei

Soft threshold based cluster-head selection algorithm for wireless sensor networks

Proceedings of the 3rd International Conference on Sensor Technologies and Applications (SENSORCOMM '09)

June 2009

526 530

2-s2.0-70449498535

10.1109/SENSORCOMM.2009.88

15.

Liang

Energy adaptive cluster-head selection for wireless sensor networks

Proceedings of the 6th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT '05)

December 2005

634 638

2-s2.0-33745121848

10.1109/PDCAT.2005.134

16.

http://www.internetworkflow.com/downloads/ns2leach/ns-llinone-2.27.tar.gz

17.

MIT μAMPS project ns2 code extensions

http://www-mtl.mit.edu/research/icsystems/uamps/research/leach/leach_code.shtml

18.

Sanka

Konchady

Communication between wireless sensor devices and GNU radio

May 2009