Improving the Energy Efficiency of a Cluster Head Election for Wireless Sensor Networks

Abstract

Sensor Networks can perceive the extensive area by applying many sensor nodes because the size of sensor nodes is relatively small and cheap. Sensor nodes can transfer multi-hop data to sink nodes which are far away than sending and receiving distance. Generally sensor nodes are composed of a large size so it is difficult that much capacity is loaded on nodes. Many routing methods are proposed in order to raise energy efficiency in sensor networks field. There is a routing method based on structure as a composing method of network by cluster. Cluster technology consisting and maintaining network topology based on cluster is mostly studied in routing protocol. There are demerits that LEACH, EACHS shall be rest energy of all nodes and HEED does not guarantee the number of cluster head. Proposed energy efficiency of selected cluster head guarantees the number of cluster head which is a demerit of HEED and minimizes the node of DEAD.

1. Introduction

USN (Ubiquitous Sensor Network) is an information infrastructure in which every person can access to the recognition, storage, manufacture, and fusion from collected context information of various sensor nodes anywhere and anytime. In other words, USN is an important technology to actualize the era of ubiquitous and many researches have been studied continuously. And regarding to this development of ubiquitous system, the needs of a sensor network technology for cushier collection on require data have been came to the fore.

Sensor networks can perceive the extensive area by application of many sensor nodes as the size of sensor nodes is small and cheap. Also, the sensor network generally consisted with sensor nodes that are deployed in jurisdiction area to identify any phenomenon and to transmit the recognized and generated data from the sensor nodes, and a wireless transceiver is used. However, as it has short distance in transmission between the sensor nodes and sink node that is placed in distance, a sensor should be arranged for identification function as well as retransmit function to transmit the data. Generally, it is difficult to store large amount of energy as sensor nodes are formed into very small nodes. In addition, thousands of nodes do not have capability to charge itself in sensor network, so when many nodes have energy depletion there are difficulties for replacement on each node.

The lifetime of sensor node depends on each sensor's energy consumption so if possible, it is aimed to save energy consumption to extend the lifetime of the entire network. In the field of sensor network, many routing technologies have been proposed to improve the energy-efficient of the sensor node. Among many methods, a structure-based routing technology is formed on network using cluster.

Many cluster technologies have been studied to configure and maintain the cluster-based network topology in routing protocol [1]. As energy efficiency is important for the clustering technology in wireless sensor network, this technique transmits sink by combining the cluster head node and the date of cluster member nodes to reduce the amount of communication between nodes. And inside cluster, by adjusting the schedule of the cluster head under TDMA (Time Division Multiple Access) schedules will extend the sleep type of the node.

In clustering algorithm, every node must belong to a cluster head or to only one cluster after clustering [2]. To minimize the energy consumption, energy of the sensor network node needs to be used more efficiently. The energy efficiency of selected cluster head guarantees the number of cluster head and made the initial energy of the node to a variable to signify common node and advance node. This paper studied the among advance nodes, allowing variation in the initial energy ratio to minimize the DEAD nodes. The paper is organized as follows:

• (1)

Introduction,

(2)

Cluster Head Selection Algorithm,

(3)

Suggesting Methods and Simulation,

(4)

Conclusions.

2. Cluster Head Selection Algorithm

The sensor used in wireless sensor network usually operates in a tough environment where people cannot approach or even in dangerous places and many sensor nodes are installed to form a sensor network. Moreover, the energy consumption and data processing capability of sensor nodes are limited. Flat routing protocol and hierarchical routing protocol are applied. Then after receiving data from its joint nodes without any calculating delivers them to gateway. And its gateway transmits them to base station after doing necessary works and calculations. Discusses RCFT (Reclustering Formation Technique) which selects randomly cluster heads at first, then reselects cluster heads considering the numbers of hops between each cluster heads, and the numbers of hops of cluster nodes farthest away from the cluster heads. After selecting cluster heads, RCFT reorganizes cluster which is to be fixed till the termination of network's life-span. After broadcasting the broadcast message, the sensor nodes selected as the first cluster heads wait for response for a while, and when response is received, they inspect whether the responses are identical with ones from the same sensor nodes, which responded before. If the response is the first time, they record the response of head with most small numbers of hops and also record the information of the sensor node with the most counting values among the responses on sensor nodes. If there are over two of the sensor nodes having the most counting values, the information of sensor node, which responded at the last, is to be recorded as it means that the sensor node, which responded at the last, is the farthest away. A cell based clustering algorithm in Large Wireless Sensor Networks was proposed in. The target field is divided into small nonoverlapping cells. Sensor node set in each cell is a cluster. The size of cell is well selected so that any node in adjacent cell can communicate with each other. An improved leach protocol was proposed where the cluster contains CH (responsible only for sending data that is received from the cluster members to the BS), sub-CH (the node that will become a CH of the cluster in case of CH dies), and cluster nodes (gather data from environment and send it to the CH). Besides having a CH in the cluster, there is a sub-CH that takes the role of the CH when the CH dies earlier than the other nodes in the cluster because of its operation of receiving, sending, and overhearing. It will become useless because the data gathered by cluster nodes will never reach the base station. However, as these techniques have limited energy it is more efficient than selecting a cluster head. First of all, take a close look on LEACH (Low Energy Adaptive Clustering Hierarchy) in algorithm for a cluster head selection.

2.1. LEACH (Low Energy Adaptive Clustering Hierarchy)

The application field of sensor network is the environment observation and location tracing. In such an environment, the end user does not need any repeated data as each node of the data is not related to each other. The role of LEACH (Low Energy Adaptive Clustering Hierarchy) is to merge repeated date by cluster head and sent to sink. Hence, any repeated data is not sent to the sink.

The LEACH assumptions are as follows.

• (i)

All nodes have enough energy to send data to the sink and can adjust transmission energy.

(ii)

All nodes have data to send at any time and close nodes have data associated with each other.

The main objective of routing protocol for routing is transferring data from transmit node to object node and finding the most suitable path with accuracy. Thus, with limited shared resources, energy consumption needs to be minimized on transmission bandwidth in the network overhead or between the nodes. For this matter, the sensor network avoids duplication of data among the adjacent sensor nodes by clustering, simplify routing and energy consumption can be managed efficiently. The clustering technology is a similar data collection process by forming local clusters in the adjacent area. The sensor network using LEACH protocol consisted with numerous clusters and each cluster is organized as upper layer node called cluster heads or normal nodes.

LEACH makes even energy consumption between the nodes in the network. And to do so, the cluster head (CH) is randomly replaced on the probability based. At the start of each round, probability value of $P_i(t)$ decides whether to work as cluster head. The number of cluster head k of $P_i(t)$ value on each round, in other words, when N is the total number of nodes in network based on the number of clusters, (1) is given as below. On average, each node should be set as the cluster head once every $N/k$ in order to guarantee the same number of cluster head in every node: $$\begin{array}{cc}& B_{\left[\text{CH}\right]}={\displaystyle \sum }_{i=\mathrm{1}}^N{P}_i\left(t\right)\times \mathrm{1}=k.\end{array}$$ (1)

From the selection process of the cluster in LEACH protocol, each node follows (2) to obtain the selected probability of the cluster head, where $C_i(t)$ is a control function, and when during recent $r\mathrm{mod}(N/k)$ round has cluster head in relevant node is then, 0, if not 1. In consequence, if it had been head for at least once, there is no chance to be selected again during the recent $r\mathrm{mod}(N/k)$ round: $$\begin{array}{cc}& P_i\left(t\right)=\{\begin{array}{cc}\frac{K}{N-k*(r\mathrm{mod}\left(N/k\right))},\hfill & C_i\left(t\right)=\mathrm{1}\hfill \\ \mathrm{0},\hfill & C_i\left(t\right)=\mathrm{0},\hfill \end{array}\end{array}$$ (2) and according to (2), I stands for the node identifier, t is the time, N is the total number of nodes, k is the number of clusters, and r represents the round. The head node selection gives equal probability from random nodes during one round as it excludes the nodes that have been selected in the previous round. Therefore, in the increase of rounds, the value of $P_i(t)$ simply rises. And since this pattern is iterated every $N/k$ , all nodes have equal probability of being selected to be the head node.

The probability function of (2) allows selecting more often nodes that have not been chosen as the cluster node in latest time. Where the node which has not been selected in the recent time it comprises more energy. All nodes are assumed to transmit data at any time. Due to the probability function of (3), this additional probability function is considered in which a node with greater energy is to be selected more frequently as the cluster head: $$\begin{array}{cc}& P_i\left(t\right)=\min \left\{\frac{E_i\left(t\right)}{E_{\text{total}}\left(t\right)}k,\mathrm{1}\right\},\end{array}$$ (3) where $E_{\text{total}}(t)$ represents the sum of the current energy on all nodes and $E_i(t)$ represents the current energy of node I. By applying this probability function, node with greater energy is to be selected as the cluster.

2.2. EACHS (Energy Adaptive Cluster Head Selection for Wireless Sensor Networks)

LEACH's cluster head selection algorithm has the disadvantage and EACHS supplemented them. And it had six features [3].

• (i)

Arrange the sink apart from the sensor nodes.

(ii)

Sensor nodes are the same type of nodes and consume energy.

(iii)

Sensor nodes have no mobility.

(iv)

Sensor nodes do not have their own location information.

(v)

All sensor nodes can reach the sink.

(vi)

Symmetric radio channel is used.

EACHS did not consider the weakness of LEACH which is the communication distance between the nodes. The cluster heads or normal nodes that are far apart from the sink or the cluster head consume larger energy to transmit the data due to the distance and so it shortens the life expectancy of network.

The cluster head selection algorithm in LEACH does not select the cluster head by considering the energy of nodes. Thus, the entire network nodes do not have equal balance on the energy consumption. In order to evenly balance the energy consumption on nodes, EACHS selects the residual energy of the node as the cluster head: $$\begin{array}{cc}& T\left(n\right)=\frac{p}{\mathrm{1}-p\left(\left(r+\mathrm{1}\right)\mathrm{mod}\left(\mathrm{1}/p\right)\right)}\left[\frac{E_{r\_\text{residual}}-E_{r\_\text{dissipate}}}{E_{r\_\text{average}}-E_{r\_\text{dissipate}}}\right].\end{array}$$ (4)

The cluster head will be selected from the distributed nodes by the probability function of (4). $E_{r\_\text{residual}}$ is the residual energy of the node and $E_{r\_\text{average}}$ is the average energy of all the nodes.

If there are larger numbers of residual energy of nodes, it has higher probability to be selected as the cluster head by (4). Assign parameter $E_{r\_\text{dissipate}}$ and if the energy consumption is greater in the final round it has higher possibility to be a cluster head and if the energy consumption is smaller in the final round, it has lower possibility to be a cluster head.

2.3. HEED (A Hybrid Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks)

HEED (A Hybrid Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks) has a complement the shortcomings of the cluster head election algorithm in LEACH. HEED has the following features.

• (i)

Sensor nodes are the same type of nodes and consume energy.

(ii)

Sensor nodes have no mobility.

(iii)

Sensor nodes do not have their own location information.

LEACH requires identifying all the nodes; however, HEED does not require recognizing every node. It utilizes their own to be selected as a cluster head: $$\begin{array}{cc}& {\text{CH}}_{\text{prob}}=C_{\text{prob}}\times \frac{E_{\text{residual}}}{E_{\max }}.\end{array}$$ (5)

The cluster head will be selected from the distributed nodes by the probability function of (5). From the above equation, $C_{\text{prob}}$ represents the comprised ratio of the cluster head in entire network, $E_{\max }$ is the initial energy of the nodes, and $E_{\text{residual}}$ is the residual energy of the node.

3. Suggesting Methods and Simulation

LEACH has the fixed function to select a cluster head so that all energy nodes have equal consumption and only the cluster head has imbalanced energy consumption due to the transmission of date or message to the sink.

EACHS has a disadvantage that it requires to identify residual of all the nodes, where HEED uses own nodes to be the cluster head and cannot grantee the number of the cluster. Therefore, the proposed algorithm is aimed to guarantee the number of the cluster head and minimize the DEAD nodes.

The proposed algorithm as a function of the initial energy value is to ensure the number of cluster head nodes and minimize DEAD nodes. The sensor nodes are made as normal nodes and advance nodes called (a), which have the greater energy consisted than the normal nodes. In addition, there is an initial energy ratio and these nodes have greater energy consisted up to ratio value of (m) between the advance nodes. In the following experiment is the comparison of nodes in the cluster heads and DEAD nodes by varying the advance node (a) and the initial energy ration (m).

The distance restraint and situation defense occur in actual communication situation. For this issue when comparing between the given value with the same initial energy and changed value in the initial energy, more cluster heads are guaranteed and have higher possibility to be selected when the initial energy value is changed. In this paper, the proposed method is to minimize DEAD node and guarantee the number of cluster head. To ensure the proposed method, previously suggested model of energy consumption is used to compare and used MATLAB to simulate.

The energy model is considered for transmitting and receiving one of data in accordance with LEACH energy model. Assume that the distance between a transmitter and a receiver is d in energy model [4]. The energy consumption model used in our work is similar to the energy model proposed by [4] and is as show in the Figure 1. (Figure 1 shows a model of energy consumption).

Figure 1

Radio energy model.

If d is larger than $d_0$ , the multipath model (with less path coefficient 4) is used; otherwise open space model (with less path coefficient 2) is used. Therefore, to transceiver energy between L and B in bit message, $E_{\text{Tx}}(l·d)$ and $E_{\text{Rx}}$ are the energy consumption in transmission and reception as in (6) $$\begin{array}{cc}& E_{\text{Tx}}\left(l·d\right)=f\left(x\right)=\{\begin{array}{cc}L·E_{\text{elec}}+L·E_{\text{fs}}·d^{\mathrm{2}},\hfill & d\le d_{\mathrm{0}}\hfill \\ L·E_{\text{elec}}+L·E_{\text{amp}}·d^{\mathrm{4}},\hfill & d>\mathrm{0}\hfill \end{array}\\ E_{\text{Rx}}=L·E_{\text{elec}},\end{array}$$ (6) where $E_{\text{elec}}$ is the energy spent to operate the transceiver circuit and which depends on factors such as the digital coding, modulation, filtering, and spreading of the signal. Amplifier energy, $\mathrm{\hspace{0.17em}\hspace{0.17em}}{E}_{\text{amp}}·d^{\mathrm{4}}$ or $E_{\text{fs}}·d^{\mathrm{2}}$ are the energy expenditure of transmitting one bit data to achieve an acceptable bit error rate and is dependent on the distance of transmission in case of free space model and multipath fading model. In simple term, this depends on the distance to the receiver and the acceptable bit error rate. Value of threshold distance $d_0$ is given by $d_0=\sqrt{E_{\text{fs}}/E_{\text{amp}}}$ .

In (7), $E_{\text{CH}}$ and $E_{\text{nonCH}}$ are the energy consumption of a cluster head nodes and noncluster head nodes during a round: $$\begin{array}{cc}& E_{\text{CH}}=\left(\frac{n}{k}-\mathrm{1}\right){LE}_{\text{elec}}+\frac{n}{k}{LE}_{\text{DA}}+{LE}_{\text{elec}}+{LE}_{\text{amp}}{d}^{\mathrm{4}\text{BS}}\\ E_{\text{nonCH}}={LE}_{\text{elec}}+{LE}_{\text{fs}}{d}^{\mathrm{2}\text{CH}}.\end{array}$$ (7)

Equation (8) is the energy consumption of both, in a cluster head nodes and noncluster head nodes in cluster: $$\begin{array}{cc}& E_{\text{cluster}}=E_{\text{CH}}+\left(\frac{n}{k}-\mathrm{1}\right)·E_{\text{nonCH}}.\end{array}$$ (8)

Therefore, all the energy consumed in the network is as follows: $$\begin{array}{cc}& E_{\text{total}}=L\left\{\mathrm{2}n{E}_{\text{elec}}+{nE}_{\text{DA}}+E_{\text{fs}}\left({kd}^{\mathrm{2}\text{BS}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{nd}^{\mathrm{2}\text{CH}}\right)\right\}.\end{array}$$ (9)

The variables of the energy consumption model in sensor network are in Table 1.

Table 1

Sensor Networks, energy consumption model variables.

Variable	Instruction
L	Bit message
$E_{\text{DA}}$	Aggreation
$d_0$	Distance threshold value
k	Number of cluster heads
$E_{\text{elec}}$	Circuit energy consumption
$E_{\text{fs}}$	Free space loss
$E_{\text{amp}}$	Multirouting loss
n	Number of node types

Compare the number of the proposed cluster heads and LEACH; then to minimize the DEAD nodes, Table 2 used variables.

Table 2

Simulation variable.

Variable	Value
Number of nodes	100
M	100 m * 100 m
SINK	(50, 50) m
Initial energy	0.5 J
Message length	4000 bit
P	0.1
$E_{\text{fs}}$	10 pJ/bit/m2
$E_{\text{amp}}$	0.0013 pJ/bit/m4
$E_{\text{elec}}$	50 nJ/bit
$E_{\text{DA}}$	50 nJ/bit

Where the initial energy is different, changes of ratio in advance nodes to make it even and guarantee the number of a cluster heads as well as comparing with DEAD nodes and compared data is as Table 3. Table 3 displays the picture shown in Figure 2. (Figure 2 shows the DEAD node in accordance with initial variation of the initial energy).

Table 3

The advance node the initial energy change.

	First DEAD node found	DEAD node 50%	DEAD node 100%
$m=\mathit{0.1}$ ,   $a=1$	969	1241	4311
$m=\mathit{0.1}$ ,   $a=2$	969	1241	6368
$m=\mathit{0.1}$ ,   $a=3$	969	1241	8944

Figure 2

The advance node the initial energy change.

According to the comparison result, the round where the first DEAD node is found was not that higher number of the initial energy does not show slower detection on the DEAD node. Nevertheless, it can be slower where it detects 100% on the DEAD nodes. The following DEAD node comparison is completed in the same environment but in varies on the initial energy by changing the ratio of advance nodes in Table 4. Table 4 displays the picture shown in Figure 3. (Figure 3 shows the DEAD node in accordance with initial variation ratio of the initial energy.)

Table 4

The initial advance node rate of energy change.

	First DEAD node found	DEAD node 50%	DEAD node 100%
$m=\mathit{0.1}$ ,   $a=2$	969	1241	6368
$m=\mathit{0.2}$ ,   $a=2$	1051	1273	X
$m=\mathit{0.3}$ ,   $a=2$	969	1325	X

Figure 3

The initial advance node rate of energy change.

After the trial, the experiment held in the same condition until the round of 9999. In Table 3, it showed the DEAD nodes with 100%; however in Table 4, the DEAD nodes were not found at all. As a result it proved that rather than varying the initial energy of the node, the changes on the initial energy ratio of nodes have higher probability to extend the life expectancy on network.

LEACH had fixed function equation to select the cluster head and that has imbalanced energy consumption. When the cluster head has been selected, high energy consumption takes to transmit the data or message to the sink. For this reason, the DEAD nodes will occur quickly. As a result, changing the initial energy than it is to change the ratio of the initial energy can extend the life of the network.

4. Conclusion

The cluster-based wireless sensor network to configure and maintain the network topology in the routing scheme and the cluster are used also to configure the network LEACH, EACHS, HEED methods are observed. LEACH had fixed function equation to select the cluster head and that has imbalanced energy consumption. EACHS has a disadvantage that requires identifying the residual energy of nodes and HEED has defect that it cannot guarantee the number of the cluster head. Due to these problems, imbalanced energy consumption has occurred and the DEAD nodes were found quickly. In this paper, by selecting the cluster head more efficiently in wireless sensor network to guarantee the number of the cluster head and with varying the initial energy it presents the normal nodes and advance nodes. Through the simulation it confirmed that to minimize the DEAD node is by varying the initial energy ratio among the advance nodes. In simulation, comparing between when it has the same value of the initial energy and when it has various value of the initial energy, the result verified that when it has various value of the initial energy more cluster heads were selected by the initial energy variable. In addition to the changes of the initial energy, the initial energy ratio has been changed. For that consequence, 100% of the DEAD nodes were found when varying the initial energy at 9999 rounds. Nevertheless, when changing the initial energy ratio, there were no DEAD nodes with 100%. This proved that changing the initial energy ratio is efficient in wireless sensor network field. Therefore, this proposed method can extend the life expectancy of the entire network.