Survey on Energy Efficient Clustering in Wireless Sensor Network

Survey on Energy Efficient Clustering in Wireless Sensor Network

Soumyadeep Dutta Infosys Limited M.Tech [I.T]

West Bengal University of Technology Kolkata, India

Abstract: – Wireless Sensor Network has become progressively more demanding and has found their way into a variety of ways of application in real world. Wireless Sensor Network (WSN) consists of several small nodes called sensor, each capable of sensing, computing and transmitting of sensed real world information. As sensor nodes rely on the non-rechargeable energy source i.e. Small Battery, so energy consumption is a big issue here. Clustering is proved to be a good way to manage energy decapitation of WSN.

INTRODUCTION:

Wireless Sensor Network consists of several small nodes each capable of sensing data from environment, compute them and transmit the data. Each sensor network has a Base Station (BS) to which all the sensed data should be sent. Sensors can be deployed randomly or in a pre-deterministic way. Wireless Sensor Network is highly relevant in modern area of application like Military Surveillance, Medical Monitoring, Communicational Purpose, and Environmental Surveillance.

The sensor nodes consist of non-rechargeable battery, i.e. limited power source. So a power saving scenario is highly relevant in WSN to increase the Network Lifetime. Network Lifetime can be computed as the time of the Node Liveliness in the WSN from the time of its deployment.

Clustering is one of the popular processes of energy consumption. In clustering, the sensor nodes are divided in several Clusters. Each Cluster has one Cluster Head and some Member Nodes. Member nodes send their Sensed Data to respective Cluster Head. Cluster Head collects all the data, aggregates them and then sends it to Base Station. Each Cluster Head depreciate energy at a high rate than normal sensor nodes. Making Cluster Heads dynamic make a possible solution to this situation.

CLUSTERING ALGORITHM:

LEACH [1] is one of the Very Basic Protocol of Clustering in WSN. Leach, stands for Least Energy Adaptive Clustering Hierarchy, is a Hierarchical Protocol for Homogeneous Network. Sensor nodes are here all of same type, deployed randomly over the sensing region. The initial Cluster Head probability p is set be a small percentage of total Sensor Nodes. LEACH is working like that in a round- Each sensor node is assigned a random number between 0 and 1.

We take a threshold value

T(n)=p/(1-r*mod(1/p)) if iG , G is the set of node that has not been cluster head in last 1/p rounds.

=0, else

Each node having random number value < threshold, is selected as a Cluster Head in the current round r. After the nodes have been selected as Cluster Head they send a Broadcast Message over the network. Each node that are not Cluster head, select its Cluster head based on the received signal strength from the Cluster Head. After all nodes select its corresponding cluster heads, they send their data over a TDMA time schedule to their respective Cluster Heads. After Cluster Head collects all the data from its cluster member, it aggregates the data and sends it to the Base Station.

HEED [2] is another popular clustering algorithm in Wireless Sensor Network for heterogeneous nodes. Nodes are not of all same type, i.e. having different energy level. In HEED, the clustering parameters are Residual Energy as well as Intra Cluster Communication Cost. We calculate a predefined cluster head probability Pc as a minimal percentage of total nodes. Before executing heed, each node compute its CH probability Pch=Pc*Eresidual/Emax. HEED protocol at a round r-

Each uncovered node (node with no CH) wants to become a CH with probability Pch. This probability value should not go beyond a threshold value Pmin. Every uncovered node computes its broadcast cost with its neighbor in the cluster range. It then broadcast its Pch and Cost to all the neighbor nodes within cluster range and joins the tentative cluster head set Sch. After r round, Sch includes the {cluster heads in step (r-1) U new heads selected in step r}. Each uncovered node selects its cluster head with minimum cost from Sch. Each node then doubles its Pch and goes to next round. If the Pch of any node reaches 1, it set its status as Final_CH, else it remains as Tentative_CH. If anode completes executing HEED without selecting any Final_CH cluster head, it announces itself as uncovered and makes its status as Final_CH. A Tentative_CH can be a normal node if it finds another cluster head with lower cost in later iteration.

To provide a more balancing and fully distributed clustering mechanism Mao Ye et al. proposed [3] EECS (Energy Efficient Clustering Scheme) algorithm, a modification of LEACH protocol. In EECS, the mechanism is working in 3 phases. In network deployment phase each node computes each distance from the received signal strength of Hello message, broadcasted from base station. In cluster head selection, nodes with probability less than threshold value select as candidate node. Each candidate node checks if there

is any candidate node within its compete_radius with more residual energy. If yes, it stops receiving any competition message. Else it will elect as HEAD node at end. In the third phase each normal node select its own cluster head based on a weighted function cost (j,i) for the plain node S(j) to make a decision.

Cost(j,i)=w*f(d(Pj,CHi))+(1-w)*g(d(CHi,BS)); S(j) selects the min{cost} to join.

In the equation, f and g are two normalized functions for the distance d(Pj,CHi) and d(CHi,BS) respectively.

f= d(Pj,CHi)/df_max and g=(d(CHi,BS)-dg_min)/( dg_max- dg_min);where df_max is the maximum distance between all cluster heads CHj and a node Pj ; dg_max=max distance between all cluster head and base station and dg_min=min distance between all cluster head and base station. These cost factors make a well balance between load distribution and energy efficiency.

To make LEACH algorithm applicable with Heterogeneous network, Georgios Smaragdakis et al. proposed [4] SEP [Stable Election Protocol]. In SEP, network is assumed to consist of n nodes among which m percent are advance nodes containing a time more energy than normal node. The threshold value is defined differently for cluster head for normal node and for advance node. The weighted value for normal node and advance node is respectively-

Pnrm = Popt/ (1+a*m) Padv=Popt*(1+a)/(1+a*m)

So the threshold has been changed to for normal node T(n)=Pnrm /(1-r*mod(Pnrm)) and for advance node it become T(n)=Padv/(1-r*mod(Padv))

Rest of the procedure is same as LEACH.

In SEP, the Cluster Head selection procedure is random, causing the probability of choosing a low energy node as Cluster Head, thus resulting a quick die out. To overcome this problem, Li Qing et al. proposed [5] DEEC (Distributed Energy efficient Clustering) Protocol. In DEEC, cluster heads are being selected based on the nodes residual energy and the total network energy. The node with high residual energy has a higher probability to become cluster head. The weighted probability of normal node and advance node has become respectively

Pnrm= [Popt*E(i)/(1+a*m).EA] and Padv= [{Popt*E(i)*(1+a)}/(1+a*m).EA] ,where EA is the average energy of the network and E(i) is the energy of node i. The threshold is set as T(n)-

T(n)= p/(1-r*mod(1/p)) if iG , G is the set of node that has not been cluster head in last 1/p rounds.

=0, else

Where p(i)=Pnrm node is normal node and p(i)= Padv node is advance

Rest of the procedure is same as LEACH.

In DEEC, as nodes with more energy is beng selected as cluster head more so it cause the quick death of advance node. To solve this problem, Brahim Elbhiri et al proposed

[6] DDEEC (Developed Distributed Energy efficient Clustering) for heterogeneous network. The network is assumed to consist of n nodes among which m percent are advance nodes containing a time more energy than normal node. EA is the average energy of the network and E(i) is

the energy of node i. Now they set an energy threshold THrev=b*Eo where b [0,1] and Eo is the initial energy. The weighted probability is stated is DDEEC as- P(i)=[Popt*E(i)/(1+a*m).EA] for normal node if E(i)> THrev

P(i)=[c*{Popt*E(i)*(1+a)}/(1+a*m).EA] for advance node if E(i)> THrev

P(i)= [c*{Popt*E(i)*(1+a)}/(1+a*m).EA] for any node if E(i)<= THrev where, c is a real positive variable. . The threshold is set as T(n)-

T(n)=p/(1-r*mod(1/p)) if iG , G is the set of node that has not been cluster head in last 1/p rounds.

=0, else

The rest of the process is same as LEACH.

DEEC protocol deals with 2 level heterogeneous network

i.e. normal nodes and advance nodes. To match it with three level heterogeneity, Parul Saini et al proposed [7] EDEEC (Enhanced Distributed Energy Efficient Clustering). The network is assumed consisting of N nodes, among which m percent are advance node. Among this m percent advance node, mo percent consists of b times energy of normal energy , called SUPER NODES and (1-mo)*m percent of nodes consist of a times energy than normal nodes, called ADVANCE NODES. EA is the average energy of the network and E(i) is the energy of node i. The weighted probability is stated is EDEEC as- P(i)=[Popt*E(i)/((1+m*(a+mo*b))*EA)] if S(i) is normal node

P(i)=[Popt*(1+a)*E(i)/((1+m*(a+mo*b))*EA)] if S(i) is advance node P(i)=[Popt*(1+b)*E(i)/((1+m*(a+mo*b))*EA)] if S(i) is super node

The threshold is set as T(n)-

T(n)= p/(1-r*mod(1/p)) if iG , G is the set of node that has not been cluster head in last 1/p rounds.

=0, else

The rest of the process is same as LEACH.

Another recent improvement over SEP protocol is made by Said Benkirane et al [8], the authors proposed DB-SEP (Distance Based Stable Election Protocol) for heterogeneous network. In sensor network, energy consumption is done proportionally to the power of the distance between sender and receiver. So a CH far from Base Station consumes much more energy than a CH near Base Station. Thus after some rounds there is a huge energy difference between node near BS with nodes far from BS. To solve this problem, the authors proposed new probability factors based on distance. Di is the distance between node i and base station and Davg is the average distance between node and base station. The network is assumed to consist of n nodes among which m percent are advance nodes containing a time more energy than normal node.

Now, if Di<=Davg then The weighted value for normal node and advance node is respectively-

Pnrm = {Popt*(1-(Di / Davg))}/ (1+a*m) and Padv=

{Popt*(1+a) *(1-(Di / Davg))}/ (1+a*m)

Else, Pnrm = Popt/ (1+a*m) Padv=Popt*(1+a)/ (1+a*m)

Davg is calculated as the sum of average distance between node and respective cluster head (dtoCH) and the average distance between cluster head and base station.

Cluster head is being selected on a threshold value. Each node select its nearest cluster head and sends data to it. After receiving all the data from the cluster member nodes, CH performs data aggregation function and sends it to base station.

In [9], Jau Yang Chang et al. proposed a new way of uniform clustering by K-means algorithm. In LEACH, the distribution of cluster heads is random; and each node selects its cluster head based on minimum distance. But this random placement of CH nodes causes more energy consumption. So authors propose an uniform way of placing cluster head.

K means algorithm is used to find k no of clusters. The optimal no of clusters are set as K= [(sqrt (n/2*))*(sqrt (Efs/Emp))*(M/ ((dBS) ^2))]. First the Center location for all sensor nodes are calculated;

i.e. by doing average of all X and Y coordinates. The average X and Y coordinate Cx and Cy is calculated as the average of sum of all X and Y coordinates. Now we calculate R as the average distance between all nodes and the initial central point (Cx , Cy). The locations of initial mean of point mi(mix, miy)for the cluster I is calculated as-

mix =R*cos((360/k)*(i-1)*(/180))+Cx miy =R*sin((360/k)*(i-1)*(/180))+Cy K is the number of cluster and i=1,2,..k.

Now, all the nodes select their cluster head based on the minimum distance from them. After the clusters are formed, the average coordinate of all nodes within a cluster is selected and select as new as new mean of the cluster. If in that position there is no node, the node with the minimum distance from that point is selected as new mean point. Now all the nodes measure their distance from those new means and restructure their cluster formation. Repeating this process finally makes uniform cluster formation. Now the last means are selected as cluster-head. Respective nodes of a cluster send their data to the cluster head and cluster head sends it to base station.

Zhiping Fan et al. proposed a Clustering algorithm, [10] EACA (Energy Aware Clustering Algorithm) a modification over LEACH protocol applied in heterogeneous network. In EACA, the clustering parameters are Current Energy of a Node and Its connectivity. Current Energy is the amount of energy a node has, and node with high current energy got a higher probability of being CH. The second parameter is Node Degree, deg; deg of a node is computed as the no of

neighbor nodes. Based on the two factors, the weight of a node I, Wi is computed as-

Wi =* Eresidual/Emax + (1-)*degi

is a Weighted Factor whose value is [0,1] based on the application. The node with largest Wi is has the highest probability to be a Cluster Head.

First each node computes its Eresidual, degi and Wi; then it broadcast it to its cluster neighbors. Every node receives a neighbor_message contains the neighbor id, their residual energy and weight. The node with the maximum weight is selected as the Cluster Head. Node selected as cluster head broadcast a CH_Message. Non Cluster Head nodes join their respective cluster heads.

CONCLUSION:

To summarize over these protocols we have seen several clustering methods. In LEACH, the cluster head selection procedure is random and it is applicable over homogenous network. HEED protocol is implemented over Heterogeneous network. In EECS, the cluster head selection is based on the residual energy of node and the cluster formation is based on a weighted cost depends on the distance between cluster head to sink and cluster head to node. SEP protocol was implemented to make a modification over LEACH protocol for 2 level heterogeneous network. DEEC comes in front with the idea of making cluster head based on the residual energy to make the cluster head lifetime more prolonged. Enhanced DEEC makes it possible to apply the DEEC protocol over 3 level heterogeneity i.e. Normal Node, Advance Node and Super Node. As in DEEC, advance node are having a more probability of being cluster head and thus deplete much faster, Developed DEEC modifies DEEC protocol by selecting the cluster head condition combined with a threshold value. In DB-SEP protocol, the distance between node and base station is used as a parameter for selecting the cluster head; so nodes nearer the base station have high probability of cluster head and thus they stay active for longer time. The EACA algorithm counts both node connectivity and residual energy as the parameter of selecting cluster head, thus covering most of the node with a proper energy balance. Another method have been studied,

i.e. the clustering based on K means method, thus dividing the network in uniform size of clusters to make a proper balance between energy consumption and load balancing. Thus, all the clustering protocols pplied several methods to find an efficient way for energy conservation. Making these algorithms energy efficient results a more prolonged network lifetime and increment in network performance.

REFERENCES

1. Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences 2000

2. Ossama Younis and Sonia Fahmy, HEED: A Hybrid, Energy- Efficient, Distributed Clustering Approach for Ad-hoc Sensor Networks, IEEE 2004

3. Mao Ye, Chengfa Li, Guihai Chen and Jie Wu, EECS: An Energy Efficient Clustering Scheme in Wireless Sensor Networks, IEEE 2005

4. G. Smaragdakis, I. Matta, A. Bestavros, SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks, Second International Workshop on Sensor and Actor Network Protocols and Applications, 2004

5. Li Qing, Qingxin Zhu, Mingwen Wang, Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks, Computer Communications 2006

6. Brahim Elbhiri, Saadane Rachid, Sanaa El fkihi, Driss Aboutajdine, Developed Distributed Energy-Efficient Clustering (DDEEC) for heterogeneous wireless sensor networks, IEEE 2010

7. Parul Saini, Ajay.K.Sharma, E-DEEC- Enhanced Distributed Energy Efficient Clustering Scheme for heterogeneous WSN, IEEE 2010

8. Said Benkirane, Abderrahim Benihssane, M.Lahcen Hasnaoui, Sidi Mohamed Ben, Distance-based Stable Election Protocol (DB-SEP) for Heterogeneous Wireless Sensor Network, International Journal of Computer Applications (0975 8887),Volume 58 No.16,

   November 2012

9. Jau-Yang Chang, Pei-Hao Ju, An efficient cluster-based power saving scheme for wireless sensor networks, SPRINGER 2012

10. Zhiping FAN, Zhengzhe JIN, Dongqing XIE, An Energy-Aware Clustering Algorithm in Wireless Sensor Networks, Electrical Review, ISSN 0033-2097, R. 89 NR 1b/2013