An Algorithm for Balanced Cost Cluster-Heads Selection for Wireless Sensor Network

An Algorithm for Balanced Cost Cluster-Heads Selection for Wireless Sensor Network

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:

1. 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.

2. 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.

3. Residual energy of nodes has not considered during cluster head selection.

During the LEACH environment, sensor nodes drain out non-uniform 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. Fixed-LEACH is one solution to this problem. The number of cluster heads is fixed in Fixed- LEACH, but as the

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

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

1. 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.

   1. 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.

   2. 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

   3. 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 Fixed-LEACH.

   REFERENCES

   1. 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 Sciences-2000, pp. 3005-3014.

   2. 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.

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

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

   5. 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.

   6. 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, 7-9 April 2005, pp. 535-540.

   7. Otgonchimeg, B. and Kwon, Y.: EECED: Energy Efficient Clustering Algorithm for Event-Driven Wireless Sensor Networks, In Proceedings of the Fifth International Joint Conference on INC, IMS and IDC, 2009.

      Seoul, pp. 1758-1763.

   8. 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.

   9. Hansen, E., Neander, J., Nolin, M. and ,Bjrkman M.:

      Energy-Efficient Cluster Formation for Large Sensor Networks using a Minimum Separation Distance,

      Mlardalen Real-Time Research Centre, Mlardalen University, Sweden, 2006.

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

   11. 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. 21-24.

   12. Junping, H., Yuhui, J. and Liang, D.: A Time-based Cluster-Head Selection Algorithm for LEACH, IEEE Symposium on Computers and Communications, 2008. ISCC 2008, pp. 1172-1176.

   13. 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. 886-897.

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

   15. Handy, M. J., Haase, M. and Timmermann D.: Low energy adaptive clustering hierarchy with deterministic cluster-head selection, 4th International Workshop on Mobile and Wireless Communications Network, 2002, pp. 368-372.

   16. Tao, Y. and Zheng, Y. : The Combination of the Optimal Number of Cluster-Heads and Energy Adaptive Cluster-Head Selection Algorithm in Wireless Sensor Networks, In IEEE Transactions n Wireless Communications 1 (4) (2002), pp. 660-670.

   17. Kaur, T. and Baek, J. : A Strategic Deployment and Cluster-Header Selection for Wireless Sensor Networks, IEEE Transactions on Consumer Electronics, Vol. 55, No. 4, NOVEMBER 2009, pp. 1890-1897.

   18. Crosby, G. V.,Pissinou, .N. and Gadze, J. : A Framework for Trust-based 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).

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

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

2. : MCBT: Multi-Hop Cluster Based Stable Backbone Trees for Data Collection and Dissemination in WSNs, Sensors 2009,Vol.9, pp. 6028-6045.

1. 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.

2. Younis, O. and Fahmy, S.: Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach, In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), , Hong Kong, 2004.

3. 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. 2012-TEICC.