An Efficient Dynamic Energy Aware Neighbor Oriented Clustering

Cheikh Sidy Mouhamed Cisse, Yaye Mbékhé Sarr, Cheikh Sarr

University of Thies, Thies, Senegal.

DOI: 10.4236/oalib.1104850                

Abstract

Network clustering consists of partitioning a large-scale network into clusters. In each cluster, we can identify a simple node and a particular node named cluster-head (CH). All simples nodes transmit their data to the cluster-head who aggregate them and send the packet to the sink. This technique reduces the amount of information and energy consumption. CHs are characterized by their high energy consumptions compared to other nodes. Thus, CH should be appropriately selected to preserve the overall network energy and then improve the lifetime. For this reason, we propose in this paper, a new routing protocol based on a hybrid metric called Dynamic Energy Aware Neighbor Oriented Clustering (DEANOC). This protocol elects a CH in each cluster of a network. The node with the highest residual energy, the closest to the station and less neighbor is chosen as CH. If the amount of energy of CHs is less than the threshold (TEN), the clustering algorithm is executed. Simulation results show that DEANOC improves the network lifetime and reduces the energy consumption compared to a similar protocol.

Keywords

WSN, Clustering, Energy Efficiency, Cluster Head, Network Lifetime, Neighbor, RSSI, Load Balancing

1. Introduction

In the last several years, wireless sensor network (WSN) has emerged as promising technology for next-generation networks with emergence of Internet of things (IoT). With the help of advances in technology research, WSNs are deployed in a broad range of applications in multiple domains. WSNs consist of a large number of sensor nodes deployed in an area [1] . A wireless sensor node is a small component, which measures physical parameters from the environment and transmits them to the Base Station (BS) through wireless medium. WSNs have critical applications in environmental monitoring, medical, industrial, military etc. Sensor nodes can be deployed in different ways: random, uniform, deterministic and mobile [2] . Sensors consist of low cost, low power small devices characterized by their limited energy, data processing and wireless communication capability.

In general, sensor nodes are equipped with a battery which is not rechargeable in most of the cases. The depletion of a battery node leads to the death of the sensor node. Therefore, energy resource becomes one of the major constraints in WSN. Communication between nodes is the major factor of power consumption. So researchers focused on finding energy efficient transmission scheme to allow WSN to operate for a relatively long time. Many solutions have been proposed in the literature to improve the network lifetime and reduce energy consumption. The concept of dividing the network geographical area into small zones has been presented implicitly as clustering in the literature [3] . Clustering has been widely investigated by the research community to achieve network scalability [4] . In cluster based design, sensors are grouped into clusters, each cluster has a cluster head (CH), which collects information from sensor nodes, processes the information and transmits them to the BS or the sink. Therefore, CH needs specific resources, and then it should be appropriately selected to fulfill its requirements.

Clustering in WSN faces multiple challenges, such as ensuring connectivity, computing the optimal cluster sizes and the number of clusters, selecting the CH node, setting inter-cluster and intra-cluster communication [5] . CH election is a critical step in clustering process, because of high energy demand and topology change of WSN. Inadequate choice of CH can lead to energy waste, lifetime degradation, packet losses, lack of scalability, and unbalanced power state. CHs are usually selected among high energy nodes and according to the number of clusters needed [6] . We propose a new cluster based protocol which selects CH node according to three criteria: (1) the residual energy, (2) the number of neighbor nodes and (3) the distance to the BS [7] . Continuous and simultaneous consideration of the aforementioned criteria is a tedious task. The eligibility of the selected CHs reduces as sensor nodes consume energy to transfer data via CHs. This leads to quicker depletion of CH energy and a cluster could get disconnected from the network. Therefore, the role of CHs also needs to be rotated among the nodes and this involves re-clustering of the network.

The rest of the paper is organized as follows. Section II reviews related work across clustering technique in WSN. In Section III, DEANOC protocol is presented. Section IV presents the simulation results and performance evaluation. Section V concludes the paper and presents future directions.

2. Related Work

In the context of routing in WSN, several contributions proved that cluster based or hierarchical protocols can greatly contribute to overall system scalability, lifetime, and energy efficiency [8] of WSN. This section makes a review of few highly cited hierarchical protocols:

2.1. Low Energy Adaptive Clustering Hierarchy (LEACH)

Heinzelman, et al. proposed the well-known clustering protocol called LEACH [9] . LEACH randomly selects nodes in the network and assigns them the role of CH. Subsequently, other nodes join the closer CHs and form the clusters. CHs collect and aggregate data from member nodes (MNs) of the cluster and send them to the BS to reduce the overall traffic transmitted to the BS. LEACH aims to reduce energy consumption and prolong network lifetime.

2.2. Hybrid Energy-Efficient Distributed (HEED)

O. Younis et al. [10] proposed HEED clustering protocol to enhance LEACH protocol by improving CH election during the set-up phase. HEED aims to achieve distributed cluster heads in the network and balanced clusters. HEED does not depend on topology, nor on the network size. It introduced two parameters during CH election: Residual energy and intra cluster communication “cost”.

Each node in the network computes its cost function to node degree or neighbors proximity and set its probability CH_prob to become a head according to equation (1).

$C{H}_{prob}=C_{prob}\times \frac{E_{residual}}{E_{max}}$ (1)

where, CH_prob is the percentage of required clusters, E_residual is the remaining energy of the node, E_max is the initial energy of the node corresponding to a fully charged battery. Nodes with highest remaining energy and least cost become heads. Nodes join CH with minimum cost.

HEED prolongs network lifetime compared to LEACH which randomly selects CHs and does not control cluster size, which may result in a faster death of some nodes. Authors in [10] show that HEED reduces energy consumption between 2× to 3× compared to LEACH. The CHs selected in HEED are well distributed across the network and, therefore, the communication cost is minimized.

2.3. Extended HEED (EHEED)

EHEED [16] proposed by Wang et al. enhance HEED protocol by integrating multi-hop technique. Energy consumption in a direct communication is proportional to the square of the distance between the sender and the receiver. Then during the transmission phase, after CHs finish collecting information from member nodes, the CH transmit data to the BS using multi-hop communication. EHEED is able to use any node, CH or non CH, as intermediate node to forward the collected data to the BS.

2.4. Rotated HEED (R-HEED)

R-HEED proposed in [17] , improve HEED protocol by introducing rotation of CH among cluster MNs. Instead of processing re-clustering after each round, nodes within the same cluster will continue rotating the CH role between them until the current CH’s residual energy goes under a specific threshold given by equation (2).

$\text{Thes}=\text{C*CHRE}$ (2)

where C is a constant between 0 and 1, CHRE is the residual energy of the CH node at the beginning of the last round

2.5. Load-Balancing Cluster Based Protocol (LCP)

Like LEACH and HEED, LCP [11] operates in two phases: setup and steady state phase. LCP operates like HEED protocol but instead of re-electing CH in each round, LCP rotates the CH among the MNs by selecting the node with the highest residual energy in every round. The first cluster which finishes his rotation, sends a re-clustering message to the BS and the network begins a new round.

LCP reduces the number of rounds, avoid multiple re-clustering processes and then saves the network energy rounds. Simulation results show that LCP improves HEED in terms of network lifetime.

3. DEANOC Design

In this section, we describe the proposed DEANOC protocol. Like LEACH [9] and HEED [10] , DEANOC operates into rounds and each round is executed in two phases: the setup phase and the steady phase. DEANOC introduces a metric that takes into account the distance of a node from the BS, the number of neighbors and the remaining energy to appropriately elect a CH.

3.1. DEANOC Setup Phase Description

First, all the nodes of the network discover their neighbors nodes using RSSI (Received Signal Strength Indication) (Algorithm 1). Figure 1 shows that each node u broadcasts a neighbor discovery message. If node v receives a neighbor discovery message from node u, it computes the distance that separate it with node u and if that distance is under the transmission range, v is a neighbor of u.

Figure 1. Neighbor discovery algorithm

where N(u) represent the set of neighbor nodes of u. The parameter N is the set of network nodes, d(u,v) is the distance between the node u and v. RSSI is the reception power used.

Figure 2 shows when all the nodes have discovered their neighbors, CHs are then elected according to the Algorithm 2. The lifetime of the network depend on the energy consumption. Nodes consume energy when transmitting, receiving or aggregating packets. Energy consumption is function of the distance to the receiver [18] . CHs consume more energy compared to MNs because they receive messages from all MNs, transmit aggregated packet to the distant BS, stay awake all along the round, while MNs are awake only during their transmission slot of time. To appropriately elect CH nodes, DEANOC takes into account the distance to the BS, the remaining energy, and the number of neighbors. Each node computes its metric and compares it to its neighbors’ metric. Nodes with higher energy and closer to the BS have more chance to be elected as a cluster head. The residual energy must be above a threshold T_EN, and the node with the smaller metric become CH.

m_u is the metric of node u and T_EN is the energy threshold. They are given respectively by Equation (3) and Equation (4).

$m_u=\alpha {\text{d}}_{\left(u,BS\right)}+\beta N_u-\gamma E_{ru}$ (3)

$T_{EN}=\frac{{\displaystyle \sum E_{ru}}}{{\displaystyle \sum n}}$ (4)

where, $\alpha +\beta +\gamma =1$ , T_EN is the average residual energy in the cluster and represent the average energy of cluster nodes.

3.2. DEANOC Steady Phase and Re-Clustering Process

After the cluster formation, the transmission phase begin. As in LEACH, member nodes send their data to the CH using TDMA. The CH aggregates collected

Figure 2. CH election algorithm

information and send it to the BS. Unlike LEACH, DEANOC does not immediately stop the round after the steady phase. It selects another nodes with high energy, over T_EN threshold, in the cluster to become cluster head. If there is no node with enough energy, the CH send a re-clustering message to the BS and another round begin. Figure 3 shows the re-clustering process.

DEANOC avoids to process a new round after transmission phase systematically, it rotates the CH role among nodes with adequate energy, and if any node responds to that criterion, it triggers re-clustering by sending a re-clustering message to the BS. This technique allows to reduce the number of rounds and save network energy.

4. Performance Evaluation

In this section, we evaluate the performance of DEANOC using Castalia-3.2 [14] running on top of OMNET++ [15] . Sensor nodes are randomly distributed in a variable region in the simulation. The number of nodes are varied from 100 to 350 nodes. A sensor node consumes 0.77 mW in the idle state, 35.46 mW in the reception state and 31.32 mW in the transmission state. In our experiments, the base station is kept fixed in the middle of the network. The size of the transmitted packets by the nodes to their CHs at each round is 200 bytes. The energy efficiency of our proposed mechanism is compared with LEACH, R-HEED and LCP. Table 1 shows the used parameters value.

Figure 3. Re-clustering procedure.

Table 1. Parameter settings.

4.1. Energy Consumption

In the first part of our experiment, we illustrate the results of residual energy for 100 to 500 nodes. This metric is obtained by the average energy remaining in all nodes at the round when the first node dies. Figure 4 shows that DEANOC consumes the least amount of energy compared with LEACH, R-HEED, and LCP.

4.2. Network Lifetime

In this second part of our simulation, we evaluate the performance of DEANOC regarding lifetime. Figure 5 shows the network lifetime as the time when all node die [12] . With 100 nodes, DEANOC extends the lifetime by 15%, 17%, and 38% respectively compared with R-HEED, LCP, and LEACH. The energy perform in Figure 1 justifies the positive results attained in this experiment.

In the rest of our experiment, we evaluate the network lifetime by running simulations with a varying number of nodes (100 - 350). The network lifetime metric is proportional to the energy consumption and depends on the field of application. Thus, in some applications, lifetime is defined as the time when the first, half, or last node dies [13] . Lifetime can be defined by until all nodes exhaust their energy. On others paper in the literature, the network is no operational when there is no connectivity between a percentage numbers of nodes [19] . Therefore, we evaluate the network lifetime by using three different metrics - First Node Die (FND), Half Node Die (HND), and Last Node Die (LND).

・ FND is defined as a time elapsed in rounds until the first node has consumed available energy.

・ HND is defined as a time elapsed in rounds until half of the nodes have consumed available energy.

・ LND is defined as a time elapsed in rounds until all of the nodes have exhausted available energy.

Figure 6 shows the lifetime of network until the first node dies. We observe clearly that with DEANOC, the network is more stable compared with R-HEED,

Figure 4. Average energy remaining.

LEACH and LCP. This happens due to the increased number of broadcast messages at the initialization phase for neighbor discovery.

Figure 4 shows that DEANOC has higher performance than LEACH, R-HEED and LCP in terms of network lifetime when HND occurs.

Figure 5 shows the time until the last node die in the network. With our proposition, the lifetime of nodes is longer than the others similar protocol. The positive results in DEANOC is confirmed by the result of Figure 1.

Therefore, it is clear that the network lifetime improves when the number of nodes increases in all protocols. Figures 6-8 shows that DEANOC is more efficient in terms of lifetime compared with others similar protocols. The role of cluster-head is assigned to rotating based on value of the node metric. In addition, if a node is cluster-head and its energy level is less than the threshold value (T_EN) during the round, the clustering procedure is executed in the cluster to

Figure 5. Network lifetime for 100 nodes.

Figure 6. Network lifetime in terms of First Node Die.

Figure 7. Network lifetime in terms of Half Node Die.

Figure 8. Network lifetime in terms of Last Node Die.

reelect another node with more energy such as cluster-head. This dynamic clustering technique reduces considerably the energy consumption of cluster heads. Consequently, global lifetime of network improves.

5. Conclusions and Future Work

In this paper, we propose a new clustering protocol for WSN. Our main contribution is to improve CH election by introducing a hybrid metric with three criteria: node residual energy, number of neighbor nodes and distance to the BS. The proposed algorithm exploits the RSSI value and the log-normal shadowing propagation model for neighbor discovery. DEANOC also balances energy consumption by dynamically rotating the role of a node depending on the residual energy. Simulation results show that DEANOC outperforms R-HEED and LCP in terms of network lifetime, and energy consumption.

In the future work, we will consider other QoS parameters like delay, latency, packet delivery ratio in cluster formation and data transmission to respond to some applications with specific needs like Wireless Multimedia sensor networks (WMSN).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Al-Karaki, J.N., Ul-Mustafa, R. and Kamal, A.E. (2004) Data Aggregation in Wireless Sensor Networks-Exact and Approximate Algorithms. Workshop on High Performance Switching and Routing, Phoenix, 19-21 April 2004, 241-245. https://doi.org/10.1109/HPSR.2004.1303478
[2]	Abbasi, A.A. and Younis, M. (2007) A Survey on Clustering Algorithms for Wireless Sensor Networks. Computer Communications, 30, 2826-2841. https://doi.org/10.1016/j.comcom.2007.05.024
[3]	Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 10.
[4]	Joa-Ng, M. and Lu, I.-T. (1999) A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile Ad Hoc Networks. IEEE Journal on Selected Areas in Communications, 17, 1415-1425. https://doi.org/10.1109/49.779923
[5]	Younis, H.O., Krunz, M. and Ramasubramanian, S. (2006) Node Clustering in Wireless Sensor Networks: Recent Developments and Deployment Challenges. IEEE Network, 20, 20-25. https://doi.org/10.1109/MNET.2006.1637928
[6]	Singh, S.K., Singh, M.P. and Singh, D.K. (2010) A Survey of Energy-Efficient Hierarchical Cluster-Based Routing in Wireless Sensor Networks. International Journal of Advanced Networking and Application, 2, 570-580.
[7]	Pantazis, N.A., Nikolidakis, S.A. and Vergados, D.D. (2013) Energy-Efficient Routing Protocols in Wireless Sensor Networks: A Survey. IEEE Communications Surveys & Tutorials, 15, 551-591. https://doi.org/10.1109/SURV.2012.062612.00084
[8]	Al-Karaki, J.N. and Kamal, A.E. (2005) Routing Techniques in Wireless Sensor Networks: A Survey.
[9]	Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, 4-7 January 2000, 10.
[10]	Younis, O. and Fahmy, S. (2004) HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks. IEEE Transactions on Mobile Computing, 3, 366-379. https://doi.org/10.1109/TMC.2004.41
[11]	Eshaftri, M., Al-Dubai, A.Y., Romdhani, I. and Yassien, M.B. (2015) A New Energy Efficient Cluster Based Protocol for Wireless Sensor Networks. Federated Conference on Computer Science and Information Systems, Lodz, 13-16 September 2015, 1209-1214. https://doi.org/10.15439/2015F193
[12]	Gerla, M. and Tsai, J.T.C. (1995) Multicluster Mobile Multimedia Radio Network. Wireless Networks, 1, 255-265. https://doi.org/10.1007/BF01200845
[13]	Aierken, N., Gagliardi, R., Mostarda and Ullah, Z. (2015) RUHEED Rotated Unequal Clustering Algorithm for Wireless Sensor Networks. IEEE 29th International Conference on Advanced Information Networking and Applications Workshops, Gwangju, 25-27 March 2015, 170-174. https://doi.org/10.1109/WAINA.2015.86
[14]	The Castalia Simulator for Wireless Sensor Network [Online]. https://sourceforge.net/projects/castalias/
[15]	OMNeT++Community (2001) OMNET++. http://www.omnetpp.org
[16]	Senouci, M.R., Mellouk, A., Senouci, H. and Aissani, A. (2012) Performance Evaluation of Network Lifetime Spatial-Temporal Distribution for WSN Routing Protocols. Journal of Network and Computer Applications, 35, 1317-1328. https://doi.org/10.1016/j.jnca.2012.01.016
[17]	Mardini, W., Yassein, M.B., Khamayseh, Y. and Ghaleb, B.A. (2014) Rotated Hybrid, Energy-Efficient and Distributed (R-HEED) Clustering Protocol in WSN. WSEAS Transactions on Communications, 13, 275-290.
[18]	Duarte-Melo, E.J. and Liu, M.Y. (2002) Analysis of Energy Consumption and Lifetime of Heterogeneous Wireless Sensor Networks. Global Telecommunications Conference, Vol. 1, 21-25.
[19]	Xu, Y., Heidemann, J. and Estrin, D. (2001) Geography-Informed Energy Conservation for Ad Hoc Routing. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, 16-21 July 2001, 70-84. https://doi.org/10.1145/381677.381685