Comparison of Energy Efficient Clustering Protocols for Heterogeneous Wireless Sensor Networks

Comparison of Energy Efficient Clustering Protocols for Heterogeneous Wireless Sensor Networks

Monica R Mundada

Research Scholar,

Dr M G R Educational and Research Institute University, Chennai, India.

(Guide)

Amit Navindgi Department of Computer Science and Engineering, MSRIT, Bangalore, India.

Nishanth Thimmegowda School of Computer Science, McGill University, Montreal, Canada.

Abstract

Wireless sensor networks are on the rise in real- time deployment and also a major field to work on for the research and development teams. These networks consist of a number of sensor nodes that sense various parameters such as temperature, pressure, etc from an environment they are deployed in, perform data aggregation and send the data to the user application that makes use of it to detect the conditions in that environment. However there is one factor that decides the use of WSN: the energy. Since each sensor node needs to perform actions of collecting, aggregating and transferring of data they need some source of energy to drive the network. Currently they derive their energy from the batteries which can provide limited amount of energy. Hence various energy efficient routing protocols have been proposed which help in minimum energy consumption ensuring longer stability period which in turn increases the lifetime of the network. In this paper, we compute the average energy of a WSN after every logical round of operation for our protocol – HEEPSCC and compare it with two well known heterogeneous protocols namely- SEP and EECS. A heterogeneous WSN is one where every node has different amount of energy associated with it before being deployed in a network. Simulations using MATLAB prove that HEEPSCC protocol causes less energy consumption among the three at the end of the considered number of logical operations.

Keywords

Heterogeneous wireless sensor network, concentric clustering, combined rating, cluster head, advanced node, SEP, EECS, HEEPSCC.

Introduction

Wireless Sensor Networks consists of a number of sensor nodes that are deployed in an environment to monitor physical conditions. The WSNs are used in various applications such as battlefield surveillance, industrial process monitoring, aircraft, health management system, environmental monitoring and in agricultural applications as well [1]. Each sensor has three operations to perform – data sensing, data processing and data transmission. The user application collects this data to monitor the changes in an environment and take necessary actions. The sensors are powered by limited battery power and hence the lifetime of a network solely depends on this power source [2]. Since the nodes are tiny only small sources of energy can be connected to them. Small batteries serve this purpose but the energy of the network will cease to zero after certain number of logical operations and hence the lifetime of the network decreases. The greater the distance between node and the sink, where data is to be sent, more is the energy dissipated. Clustering technique has been used to mitigate this problem. In clustering, various nodes are grouped into clusters with each cluster having a cluster head [3]. Each round is categorized by the two activities : Selection of cluster head and data transmission. Both of these operations happen in a unit of time called as the round time. The "round time" definition is very abstract so that it can be flexible to be deployed in application where different round time is desired. In our implementation, the data transmission phase begins immediately after the selection of cluster head. During the deployment of the sensor, the WSN nodes can be configured in such a way so that after a certain period of time, the nodes start to report back or after each interval of time the selection of cluster head task may happen depending upon the application field. Theoretically, in one round, CH is selected once and all nodes transmit data once. The time-period interval of the "round" is left to the

discretion of the application. The cluster head acts as the local sink for the nodes in its cluster [4]. Nodes send data to its cluster head which then transfers the data to the user application. There are two clustering schemes namely homogeneous clustering scheme and heterogeneous clustering scheme. The clustering technique used in homogeneous sensor networks where all the nodes have same initial energy is called homogeneous clustering scheme whereas the one applied in heterogeneous sensor networks where the nodes have different energy values is called heterogeneous clustering scheme. The protocols for data routing used in homogeneous clustering schemes such as LEACH[5], PEGASIS[6], TEEN[7], APTEEN[8], etc do not work well for the heterogeneous networks. Hence there is a need for heterogeneous aware protocols for efficient use of energy and thus increase network lifetime. Several such protocols have been proposed among which we compare the average energy of the network for three of them namely SEP, EECS and HEEPSCC. We conclude with the help of simulation results that HEEPSCC has the highest average energy of the remaining nodes in a network for the number of rounds considered among the three.

Related Work

Stable Election Protocol (SEP) was a path breaking protocol which increased the stability time of a network [9]. Stability time is the time taken for the first node to die in the network. SEP is a heterogeneity-aware protocol. It does not require energy knowledge sharing in the overall network but is based on assigning weighted election probabilities of each node to be elected as cluster head according to their respective energy. By using this approach, authors ensure that the cluster head is randomly selected based on the fraction of energy of each node; this assures that each nodes energy is uniformly used. In SEP two types of nodes, normal and advanced, are considered. It is based on weighted election probabilities of each node to become cluster head according to the remaining energy in each node. This prolongs the stability period i.e. the time interval before the death of the first node. The problem that arises with the heterogeneity-oblivious protocols is that if the same threshold is set for both normal and advanced nodes then there is no guarantee that the number of cluster heads per round per epoch will be n × popt. SEP uses the following characteristic parameters of heterogeneity, namely the fraction of advanced nodes (m) and the additional energy factor between advanced and normal nodes (). SEP talks about

the fairness constraint on energy consumption i.e. advanced node get the chances to become the CH more often than the normal nodes. The solution of SEP is more applicable compared to any solution which assumes that each node knows the total energy of the network in order to adapt its election probability to become a cluster head according to its remaining energy. In this approach, a weight is assigned to the optimal probability popt. This weight must be equal to the initial energy of each node divided by the initial energy of the normal node. Let pnrm and padv be the weighted election probability for normal nodes and the advanced nodes respectively. In order to maintain the minimum energy consumption, the average number of cluster heads per round per epoch must be constant and equal to n×popt. Virtually, there are n·(1+·m) nodes with energy equal to the initial energy of a normal node. In the heterogeneous scenario, the average number of cluster heads per round per epoch is equal to n·(1 + ·m)·pnrm. The weighed probabilities fornormal and advanced nodes are, respectively: With help of these weighted probabilities thresholds for normal nodes and advanced node can be calculated. In most rounds, no cluster head is selected by SEP. In such rounds where no CH is selected, the data packets for normal nodes and the advanced nodes respectively. In order to maintain the minimum energy consumption, the average number of cluster heads per round per epoch must be constant and equal to n×popt. Virtually, there are n·(1+·m) nodes with energy equal to the initial energy of a normal node. In the heterogeneous scenario, the average number of cluster heads per round per epoch is equal to n·(1 + ·m)·pnrm. With help of these weighted probabilities thresholds for normal nodes and advanced node can be calculated. In most rounds, no cluster head is selected by SEP. In such rounds where no CH is selected, the data packets cannot be transmitted to the base station. This is a great disadvantage to the reliable transmission in the networks, especially for some important real-time transmission tasks.

Energy Efficient Clustered Scheme (EECS) [10] is another protocol based on clustering technique for heterogeneous sensor networks. It is similar to LEACH [5] and was proven to 135% more efficient. It divides the network field into clusters with each cluster having a cluster head. It has two phases – cluster head selection phase and cluster formation phase. It chooses cluster heads such that they are spread uniformly with more residual energy while balancing the load among them. In the cluster head selection phase after each cluster is selected based on the residual energy, the normal

nodes choose their cluster head based on two distance factors: d(Pj, CHi) and d(CHi, BS). The normal nodes select their cluster based on the weighted function

cost(i, j) = w x f( d(Pj, CHi)) + (1-w) x g(d(CHi, BS)), where f and g are two normalized functions shown below

RE is the residual energy and D the distance between nodes. The one with highest CR is selected to be the cluster head. Finally the data transmission takes place with data routing from sensor nodes to their cluster head and finally to the base station. The use K-theorem ensures that lifetime of the network is increased as the only the cluster heads with maximum residual energy

,

=

, _

=

perform data processing from the nodes in its

_

_

_min

cluster and transmission of data to the base station over minimum distance. The authors of [11] proved that the number of dead nodes is less in case of

Where df_max = exp(max{d(Pj, CHi)}) , dg_max = max{d(CHi, BS)} and dg_min = min{d(CHi, BS)}.

As stated above, EECS produces a uniform distribution of cluster heads across the sensor network using local radio communication with little overhead. It comes with advantages of fully distributed, low control overhead and load balanced clustering mechanism. The disadvantage of this protocol is that the communication between cluster head and base station is direct i.e. a single hop transmission and hence if the distance between them is greater more amount of energy is dissipated and causes lower network lifetime.

Hybrid Energy Efficient Protocol for Stable Concentric Clustering (HEEPSCC) was proposed

[11] to provide longer stability period and increased network lifetime by improving energy efficiency. It proceeds in three stages – concentric cluster formation, cluster head selection and data transmission. In the concentric cluster formation stage the base station sends out 'hello' packets to all the nodes in the network. The nodes with higher energy, the advances nodes respond back with a message containing its distance from the base station. The base station upon receiving this forms a cluster around this node and this process is continued for the next advance nodes such that concentric clusters for each advanced node is formed with the base station at the common centre. The annulus i.e. the area between each concentric circle forms one circle. In the following stage of selecting a cluster head K-theorem is used. According to the theorem the advanced node sends out a k-value to all the nodes initially to determine the nearest nodes so as to choose a cluster head with minimum distance and maximum residual energy. Then all the sensor nodes send the nearest k number of nodes and their distance is calculated based on the time of reception of the return signal. The advanced node then selects a candidate set of nodes among which one will be the head and asks

them to send their combined rating which is calculated using the equation CR = RE/D2 where

HEEPSCC than in SEP and EECS and hence concluded HEEPSCC to be more efficient than SEP and EECS. We prove this again using average energy of the network as the parameter and specify the conditions that are well suited for the three protocols to be used. The K-theorem which forms the core of this protocol to select the cluster head consists of following steps:

Step 1: The advanced node sets the value of k for each round for each cluster depending upon node density. It broadcasts the value of k to all the nodes in its cluster. The value of k is used to determine the k nearest number of nodes to it.

Step 2: All the sensor nodes in the cluster send the k number of nearest neighbors to the advanced node. The distance to the node can be calculated based on the time for the return signal received.

Step 3: The advanced node select candidate set of cluster heads i.e. Ci for each cluster in the network. The value of ki is always equal to the number of candidate cluster heads in a cluster i.e. C.

Step 4: The advanced node requests each node in the candidate set of cluster heads in the respective cluster to send their combined rating (CR).

Step 5: Each candidate cluster head node calculate its own combined rating based on two factors namely residual energy (RE) and distance to coordinator node (D). The exact relation of calculating combined rating is described in equation.

Step 6: The coordinator node selects a node as cluster head among candidate set of cluster heads for each cluster based on combined rating. The node with the highest combined rating is elected as cluster head. Hence, higher the combined rating, higher the chances of it becoming the cluster head in the respective cluster.

Results and Discussion

Several assumptions and dependencies were made regarding the structure of the network and the node attributes. The first most is that the network consists of densely populated nodes which are immobile once deployed. The sensor nodes are manually deployed by the user on a geographical area at specific location and they cannot be recharged i.e. the energy of the node cannot be increased once deployed. It is also assumed that there exists only one base station with infinite energy to which the data is forwarded by the nodes. A node is capable of directly communicating with the base station or with any other node using its unique ID to distinguish itself from others and finally the base station is located at the geometric edge of the network.

Table 1: Simulation parameters

Parameter	Value
Area	200 × 100
Base Station	(0, 0)
Initial Energy	5 J
Eelec fs mp	50 nJ/bit 10 pJ/bit/m2 .0013 pJ/bit/m4

The following results were obtained when the three protocols – HEEPSCC, EECS and SEP were simulated using MATLAB v7.6. The network size is increased in steps of 50 so that justifiable results are obtained for a fixed number of rounds. The nodes are considered to be stationary once they are deployed in an environment. The number of rounds was fixed to 800 to observe the difference in the values more accurately as the energy ceases t zero and are closely follow each other for large number of rounds. Different sizes of networks are considered in drawing the conclusion.

Figure 1: Comparisons in network with 100 nodes

As can be observed from the graph in figure 1 above the average energy of the network at the end of 800 rounds is higher in HEPPSCC than in SEP and EECS. To be precise the values found were to be 4.8, 3.4 and 3.2 in HEEPSCC, EECS and SEP

respectively. It can be concluded that HEEPSCC is 41% and 50% more efficient than EECS and SEP respectively. This is expected as the numbers of nodes that die are less in case of HEEPSCC as proven in [11].

Figure 2: Comparisons in a network with 150 nodes In this case, observed in figure 2, the average

of the network remains high when deployed with HEEPSCC than with SEP and EECS. Considering the values 4.86, 3.06 and 2.95 for HEEPSCC, EECS and SEP found at the end of 800 rounds HEEPSCC was found to be 59% and 64% more efficient than EECS and SEP respectively.

Figure 3: Comparisons in network with 200 nodes In this case too, similar results were observed

with the values of average energy of the network as 4.54, 2.95 and 2.80 in HEEPSCC, EECS and SEP

respectively as calculated from figure 3. Hence in a network of 200 nodes HEEPSCC is 53% and 62% more efficient than EECS and SEP respectively. It can be seen that the average energy of SEP is almost equal to EECS since the number dead nodes are almost equal.

Figure 4: Comparison in a network with 250 nodes

As the number of nodes or the size of the network increases the throughput of SEP is steady and more than EECS in this case but HEEPSCC beats both of them when average energy of the nodes alive is considered. The exact value of average energy from figure 4 was found to be 4.31,

2.68 and 2.75 in HEEPSCC, EECS and SEP respectively. Therefore HEEPSCC is 60% and 56% more efficient than EECS and SEP respectively.

Figure 5: Comparisons in a network with 300 nodes In the final graph obtained as shown in figure

5, the average energy of the network using EECS drops below and keeps reducing faster than SEP as the size of the network increases. The value was found to be 4.31 in HEEPSCC, 2.68 in EECS and

2.75 in SEP. Since the number of nodes dead is considerably less in HEEPSCC most of the nodes are alive and constitute towards the average energy. HEEPSCC performs well in this case too with efficiency being 68% and 49% more compared to EECS and SEP respectively.

Conclusion

The results obtained above are coherent with that achieved in [11]. Since the average energy is least for EECS for larger size of the network, it has more number of dead nodes as observed in [11] as well. The reason for fixing total number of rounds to 800 is that the number of nodes that die becomes more and more as the number of operations or rounds are increased and since energy ceases to zero in any protocol in such case effective comparisons cannot be made between protocols. The energy dissipation calculations start right from the round one and since the initial energy of each node was assigned to be less there is a difference in the average energy at the start depending on the number of dead nodes. The K-theorem proposed in HEEPSCC was more efficient than EECS and SEP in saving energy by selecting a cluster head so that it is at a minimum distance from the sink and therefore less energy is dissipated in transmitting the data. The above results were expected as the HEEPSCC was proven more efficient than the other two using number of dead nodes factor. It complements the results for the case of average energy as less number of dead nodes means more residual energy and hence greater average energy of the network. We observed that SEP was the most stable in throughput among all the three as suggested in [9]. This is because under SEP, the advanced node follows the death of normal nodes as the weighted probability of electing cluster heads causes the energy of each node to be consumed in proportion to the node's initial energy. But HEEPSCC, with maximum average energy remaining at the end of all the operations, is most suitable for environments where data sensing takes place for a limited time and high accuracy is needed as is required in military applications where changes occur rapidly lasting for a short time and data sensing needs to be done precisely and quickly with minimum energy consumption.

References

1. J. Hill, R. Szewczyk, A, Woo, S. Hollar, D. Culler, and K. Pister, System Architecture Directions for Networked Sensors, ASPLOS, November 2000.

2. Oliveira, Luis M. L.; de Sousa, Amaro F.; Rodrigues, Joel J. P. C. ,Issue Routing and mobility approaches in IPv6 over LoWPAN mesh networks, International Journal of Communication Systems, NOVEMBER 2011,Volume 24,Issue 11,pages 1445-1466.

3. Y.T. Hou, Y. Shi and H.D. Sherali, .On energy provisioning and relay node placement for wireless sensor networks, IEEE Transactions on Wireless Communications 4 (5), 2005, 2579.2590

4. K. Akkaya and M. Younis, .A survey on routing protocols for wireless sensor networks., Elsevier Journal of Ad Hoc Networks 3 (3), 2005, 325.349.

[5]. W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-efficient Communication Protocol for Wireless Micro sensor Networks, in IEEE Computer Society Proceedings of the Thirty Third Hawaii International Conference on System Sciences (HICSS '00), Washington, DC, USA, Jan. 2000,

vol. 8, pp. 8020.

1. S. Lindsey and C.S. Raghavendra, PEGASIS: power efficient gathering in sensor information systems Proceedings of the IEEE Aerospace Conference, BigSky, Montana, March 2002.

2. A.Manjeshwar and D.P. Agrawal, TEEN : a protocol for enhanced efficiency in wireless sensor networks, Proceedings of the first international Workshop on parallel and distributed computing issues in wireless networks and Mobile Computing, San Francisco, CA, April 2001.

3. A.Manjeshwar and D.P. Agrawal, APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive information retrieval in Wireless Sensor Networks, Parallel and Distributed Processing Symposium. Proceedings International, IPDPS 2002, 2002, 195-202.

[9]. Georgios Smaragdakis, Ibrahim Matta and Azer Bestavros. SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks. Second International Workshop on Sensor and Actor Network Protocols and Applications, (SANPA 2004)

[10]. Mao Ye, Chengfa Li, Guihai Chen and Jie Wu. "An Energy Efficient clustering Scheme in wireless sensor networks" in Proceedings of the 24th IEEE International Performance, Computing and Communications Conference (IPCCC 05), pp. 535540, April 2005

[11]. Monica R Mundada, Nishanth Thimmegowda, Thippesh K S, Avinash S, T Bhuvaneswari and Cyril Raj. Hybrid Energy Efficient Protocol for Stable Concentric Clustering in Heterogeneous Wireless Sensor Networks, International Journal of Computer Applications(0975-8887), Volume 73 No.2, July 2013.

[12]. Md. G Rashed, M. H Kabir and S E Ullah. WEP: An energy efficient protocol for cluster based heterogeneous sensor network". International Journal of Distributed and Parallel Systems, Vol. 2 No. 2 March 2011.

[13]. R Sheikhpour, S Jabbehdari and A Khadem- Zadeh. Comparison of energy efficient clustering protocols in heterogeneous wireless sensor networks", International Journal of Advanced Science and Technology, Vol. 36, November, 2011.

[14]. Dilip Kumar, T C Aseri and R B Patel" EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor network", Computer Communications, Vol. 2, Issue 4, 4 March 2009.

[15]. S B Alla, A Ezzati and A Mohsen. Hierarchical adaptive balanced routing protocol for energy efficiency in heterogeneous wireless sensor networks" Energy Efficiency – The innovative ways of smarter energy, the future towards modern utilities. October 1, 2012.

[16]. Rudranath Mitra and Diya Nandy. A survey on clustering techniques for wireless networks" International Journal of Research in Computer Science. Volume 2 Issue 4

[17]. Md I Hossain, M. M Rahman, T K Godder and T Khatun. "Improving energy efficient clustering method for wireless sensor network" I.J Information Technology and Computer Science" published online August 2013 in MECS

[18]. A K Tripathy and Suchismita Chinara. "Comparison of residual energy based clustering algorithms for wireless sensor networks". ISRN Sensor Networks. Volume 2012, Article ID 375026.