 Open Access
 Total Downloads : 619
 Authors : Rachna Dasondhi, Megha Singh, Deepak Kulhare
 Paper ID : IJERTV1IS10526
 Volume & Issue : Volume 01, Issue 10 (December 2012)
 Published (First Online): 29122012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Algorithm for Balanced Cost ClusterHeads Selection for Wireless Sensor Network
Rachna Dasondhi M.Tech Student 
Megha Singh Assistant Professor CSE Dept. 
Deepak Kulhare Associate professor &HOD CSE 
CIIT Indore 
CIIT Indore 
CIIT Indore 
AbstractIn this paper we proposed a new technique or algorithm for selection of cluster head of LEACH routing protocol. The functionality of this proposed algorithm, it balances the energy consumption of every sensor node in wireless sensor network. After the implementation of the proposed algorithm it definitely improves the performance in terms of energy utilization. Individual cluster head node load is increases if it exist less than the optimum number of cluster head nodes. If fix the number of cluster heads and as the nodes choose the nearest cluster head for data transmission, the number of supported nodes may vary for different cluster head nodes. This leads to uneven load distribution among nodes in a Wireless Sensor Network (WSN).
Keywords: Energy Consumption, Centroid, Cluster Head Selection, Balanced Cost, Epoch, Wireless Sensor Network
I.INTRODUCTION
Low Energy Adaptation Clustering Hierarchy (LEACH) is widely used and demanding protocol of routing for wireless sensor network. In this protocol [1] arrangement of nodes is classified into different clusters. Few nodes are selected as cluster heads and other nodes use these cluster heads as routers to the sink. All the data processing such as data fusion and aggregation are performed at cluster head. Cluster heads change randomly over time in order to balance the energy dissipation of nodes. A node becomes a cluster head for the current round if the chosen random number is less than the following threshold,
Here r is current round, G is a number which decides eligibility to become cluster head and form a set of nodes that have not been cluster heads in the last 1/p rounds in one epoch and p is the desired percentage of cluster heads.
LEACH was the first protocol for balancing the energy consumption among nodes, although with some shortcomings:

Number of cluster head nodes are not constant in LEACH due to random selection. The different cluster numbers in each round will make the node numbers in every cluster different and uneven cluster numbers dissipate uneven energy in each round.

Probability function for becoming a cluster head is based on the assumption that all nodes have same initial energy. This is not true in case of heterogeneous network.

Residual energy of nodes has not considered during cluster head selection.
During the LEACH environment, sensor nodes drain out nonuniform energy due to different distances between sensor nodes and base station. In heterogeneous network, there may be two or more groups of nodes which have different initial energy. For both the cases nodes will have different amount of residual energy, then the nodes with more energy should be cluster heads more often than the nodes with less energy, to ensure that all nodes die approximately at the same time.
However, every round in LEACH will have the different cluster numbers, we have chosen p =
0.05 so in a 100 nodes topology, 5 nodes will become cluster head with highest frequency. Thus every round will have the different cluster head numbers. 3. After every epoch every node again become eligible to become cluster head as all the nodes would have become cluster head once in the current epoch. FixedLEACH is one solution to this problem. The number of cluster heads is fixed in Fixed LEACH, but as the
Heterogeneous topology assumed. 

Zytoune et al. [10],[11] 
When transmission energy is much higher than data aggregation and reception energy then probability of selection of cluster head should be function of distance of the node from the base station. 
TB LEACH[12] 
Nodes which have the shortest time interval will win the competition and become cluster heads ensuring that the partition of cluster is balance and uniform. 
Chen et al.[13] 
Impact of topology on the performance and energy efficiency in wireless sensor networks for source extraction, by illustrating the performance, energy efficiency, and lifetime of various sensor networks 
Huang et al. [14] 
Clustering by selecting only potential nodes as cluster head. 
Handy et al.[15] 
Every node becomes a clusterhead exactly once within one epoch. 
Tao et al.[16] 
Cluster head selection by combining the optimal number of clusterhead with residual energy of nodes. 
Kaur et al.[17] 
Strategic deployment for heterogeneous sensor nodes is proposed for lifetime maximization. 
Crosby et al.[18] 
Clustering by reducing the likelihood of malicious nodes from being selected as cluster heads. 
This Paper 
Cluster head selection depending on how many nodes were supported in previous round. 
nodes choose its nearest cluster head, the number of supported nodes is different for each cluster head. This leads the uneven energy dissipation among nodes. In this paper, we proposed a better solution compare to Fixed LEACH, It provide more balanced energy consumption in a WSN.
TABLE 1
DIFFERENT CLUSTERING ALGORITHM
Algorithm 
Clustering Rule 
LEACH [23] 
Random probabilistic clustering. 
LEACHC [24] 
Centralized clustering algorithm to produce better clusters. 
LEACHF [24] 
Clustering with fixed number of clusters. 
PEGASIS [3], [21] 
Each node communicates only with a close neighbor and takes turns transmitting to the base station, thus reducing the amount of energy spent per round. 
HEED [4], [22] 
Cluster heads are selected periodically according to a hybrid of the node residual energy and node proximity to its neighbors or node degree. Availability of multiple power levels in sensor nodes is assumed. 
TEEN [5] 
Total numbers of transmissions are reduced by allowing the nodes to transmit only when the sensed value less than a threshold value. 
EECS [6] 
Clustering based on residual energy through local radio communication while achieving better cluster head distribution. 
EECED [7] 
Nodes with more residual energy have more chances to be selected as cluster head. 
EEHC [8] 
Cluster head selection based on weighted election probabilities according to the residual energy in each node. 
II. EXISTING WORK
As long as LEACH there are so many algorithm are used for efficient energy utilization in Wireless Sensor Network for routing and energy balancing. Different algorithms and the criteria used to select the cluster head are given in Table

As we have used number of supprted nodes for clustering rule so we called it NLEACH. Most of the proposed algorithm is based on residual energy. Probability of nodes for being cluster head is varied using different parameters in these algorithms.

PROBLEM STATEMENT
Let a node identified as node 1 become a cluster head. It support N1 nodes for data transmission, then energy consumption of this node is
E1 =ETXamp(L, d1toch) + L.N1.(ERX + EDA) + ETXamp(L,
d1tobs)..(2)
In general, node i become a cluster head, and it support Ni nodes for data transmission then energy consumption of this nodes is
Ei =ETXamp(L, ditoch) + L.Ni.(ERX + EDA)
+ ETXamp(L, ditobs)..(3)
For a small area network, for a single node energy consumed in transmission of data from non cluster heads nodes to cluster heads is nearly same as energy consumed in transmission from cluster heads nodes to base station. It is with assumption that base station is located at the centroid of the deployed sensor nodes. So ETXamp is approximately same for both the nodes either for transmission from normal node to cluster head or for transmission from cluster head node to base station. If Ni is much larger than N1 then energy consumed in receiving and data aggregation play more important role compare to transmission of data.
Ei E1 =L. (Ni N1) . (ERX + EDA)
( 4)
So here main difference between nodes energy consumption is due to reception and data aggregation only.
If the optimum number of cluster is k then the average number of supported nodes by a cluster head is n/k for a particular round. The cluster number in some round may become less than k or in some round greater than k. If the cluster head nodes support more than n/k nodes i.e., then it spends more energy which it should be spent in n/k number of rounds. If cluster heads are more than k, then cluster head node support less than n/k nodes. Thus cluster heads spend less energy compared to others nodes in n/k number of rounds.
The different cluster numbers [19] in WSNs along with random choice of cluster heads will make the node numbers in every cluster different and leading to uneven energy dissipation for all nodes in each round. Therefore, We propose a new techniques which leads to dissipation of approximately 1 epoch energy on an average in each round.

PROPOSED ALGORITHM
Step 1: In first round of data transmission G is set to be 1 for all nodes.
Step 2: Operation for epoch is performed after every n/k rounds. The value of G is reduced by one to all the nodes which are having G 0.
Step 3: All the nodes which are having G < 0 are eligible to become cluster head.
Step 4: Now the nodes will become cluster head choosing a threshold Tn between 0 and 1 using equation 1.
Step 5: If a nodes become a cluster head, it supports N number of nodes. If this N is greater than Nave = n k , then this nodes is going to loose high amount of energy, and if N is lesser than Nave, then this node is going to save some energy compared to other nodes, which have already become cluster head or will become cluster head within n k rounds.
We add (k//n)*N to G when a node become cluster head. Thus value of G become proportional to N, if a node support large number of nodes then this will loose its
eligibility criterion for next few n/k rounds as this will not become eligible unless G 0 or if support lesser than Nave nodes then it remain eligible to become cluster head. Thus we develop algorithm that a node can spend only Nave energy in every n/k rounds.
Graphical view of LEACH and proposed algorithm is shown in Fig.1 and Fig.2 respectively in flowchart. We can compare both algorithms using this flowchart.
Fig.1 LEACH Algorithm Flowchart
Fig.2 Proposed Algorithm

CONCLUSIONS
In this paper we discuss brief about the LEACH protocol and the proposed energy efficient algorithm for wireless sensor network. The new parameters and assumption really improves the performance, throughput, capabilities and data overheads for routing. We apply this proposed algorithm for different topology. This application describe that proposed cluster head selection method is robust against topology change also. So this algorithm may be used for dynamic wireless sensor networks also. So proposed algorithm gives improved result as compare to the FixedLEACH.
REFERENCES

Heinzelman, W. R., Chandrakasan, A., and Balakrishnan, H. : Energy Efficient Communication Protocol for Wireless Microsensor Networks, In Proceedings of the 33rd Hawaii International Conference on System Sciences2000, pp. 30053014.

Heinzelman, W. R., Chandrakasan, A., and Balakrishnan, H. : An application specific protocol architecture for wireless microsensor networks, In IEEE Transactions on Wireless Communications 1 (4) (2002), pp. 660
670.

Lindsey, S. and Raghavendra, C. S.: PEGASIS: Power Efficient Gathering in Sensor Information Systems, in Proceedings of IEEE Aerospace Conference, Vol. 3, March, 2002.

Younis, O. and Fahmy, S.: HEED: A Hybrid, Energy Efficient, Distributed Clustering Approach for Adhoc Sensor Networks, IEEE Transactions on Mobile Computing, Volume 3 , Issue 4, October 2004, pp. 366 379.

Manjeshwar , A. and Agrawall, D.P.: TEEN : A Protocol for Enhanced Efficiency in Wireless Sensor Networks, In Proceedings of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, San Francisco, CA, April 2001.

Ye, M., Li, C., Chen, G. and Wu J.: EECS: An energy efficient clustering scheme in wireless sensor networks, 24th IEEE International Performance, Computing, and Communications Conference, 2005. IPCCC 2005, 79 April 2005, pp. 535540.

Otgonchimeg, B. and Kwon, Y.: EECED: Energy Efficient Clustering Algorithm for EventDriven Wireless Sensor Networks, In Proceedings of the Fifth International Joint Conference on INC, IMS and IDC, 2009.
Seoul, pp. 17581763.

Dilip, K., Trilok, C. A. and Patel, R. B.: EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks, Journal of Computer Communications, Vol.32 (2009) pp. 662667.

Hansen, E., Neander, J., Nolin, M. and ,Bjrkman M.:
EnergyEfficient Cluster Formation for Large Sensor Networks using a Minimum Separation Distance,
Mlardalen RealTime Research Centre, Mlardalen University, Sweden, 2006.

Zytoune, O., Aroussi, M. E., Rziza, M. and Aboutajdine, D.: Stochastic Low Energy Adaptive Clustering Hierarchy, ICGST CNIR, Volume (8), Issue (1), (2008), pp. 4751.

Zytoune, O., Fakhri, Y. and Aboutajdine, D. : A Balanced Cost Cluster Heads Selection Algorithm for Wireless Sensor Networks, International Journal of Computer Science Volume (4), Issue (1), (2009), pp. 2124.

Junping, H., Yuhui, J. and Liang, D.: A Timebased ClusterHead Selection Algorithm for LEACH, IEEE Symposium on Computers and Communications, 2008. ISCC 2008, pp. 11721176.

Chen, H., Tse, C. K. and Feng, J. : Impact of Topology on Performance and Energy Efficiency in Wireless Sensor Networks for Source Extraction, IEEE Transactions on Parallel and Distributed Systems, VOL. 20, NO. 6, JUNE 2009, pp. 886897.

Huang, H. and Wu, J. : A Probabilistic Clustering Algorithm in Wireless Sensor Networks, in IEEE VTC 2005Fall, September 2005, vol. 3, pp. 17961798.

Handy, M. J., Haase, M. and Timmermann D.: Low energy adaptive clustering hierarchy with deterministic clusterhead selection, 4th International Workshop on Mobile and Wireless Communications Network, 2002, pp. 368372.

Tao, Y. and Zheng, Y. : The Combination of the Optimal Number of ClusterHeads and Energy Adaptive ClusterHead Selection Algorithm in Wireless Sensor Networks, In IEEE Transactions n Wireless Communications 1 (4) (2002), pp. 660670.

Kaur, T. and Baek, J. : A Strategic Deployment and ClusterHeader Selection for Wireless Sensor Networks, IEEE Transactions on Consumer Electronics, Vol. 55, No. 4, NOVEMBER 2009, pp. 18901897.

Crosby, G. V.,Pissinou, .N. and Gadze, J. : A Framework for Trustbased Cluster Head Election in Wireless Sensor Networks, In the Proceedings of the Second IEEE Workshop on Dependability and Security in Sensor
Networks and Systems (DSSNS06).

Ci, S., Guizani, M. and Sharif, H. : Adaptive clustering in wireless sensor networks by mining sensor energy data, Elsevier: computer communications, 2007.

Shin, I., Kim, M., Mutka, M. W., Choo, H. and Lee, T.


: MCBT: MultiHop Cluster Based Stable Backbone Trees for Data Collection and Dissemination in WSNs, Sensors 2009,Vol.9, pp. 60286045.

Lindsey, S., Raghavendra, C. S. and Sivalingam, K.:
Data gathering in sensor networks using the energy*delay metric, In Proceedings of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing, April 2001.

Younis, O. and Fahmy, S.: Distributed clustering in adhoc sensor networks: A hybrid, energyefficient approach, In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), , Hong Kong, 2004.

Rachna Dasondhi, Megha Singh A Review of Research in LEACH Protocol of Wireless Sensor Network, In Proceedings of International Conference on
Technical and Executive Innovation in Computing and Communication 27,28 Dec. 2012TEICC.