An Energy Efficient Multi-level Uneven Grid based Clustering Routing Protocol in Wireless Sensor Networks

An Energy Efficient Multi-level Uneven Grid based Clustering Routing Protocol in Wireless Sensor Networks

Elvin Kuruvilla

Asst. Prof.,

Dept. of Computer Science & Engineering Vijnan Institute of Science & Technology Kerala, India

Sreeranjini Nandakumar

Asst. Prof.,

Dept. of Computer Science & Engineering Vijnan Institute of Science & Technology Kerala, India

Abstract Energy conservation of the sensor nodes is an important issue considered in the design of Wireless Sensor Network (WSN). So to extend the network lifetime several clustering approaches are used. Most of this clustering approaches facing hot spot problem. It is one of the key issues caused by the fact that the sensor nodes closer to the base station drain their energy quickly than other nodes as data of the entire network is forwarded to BS through them. In this paper, we are proposing an uneven multi-level grid clustering routing method to overcome the hot spot problem and to extend the network life time. Here this protocol divides the network into variable number of uneven grids based on the average energy level. At each period of time interval BS checks the average energy and sets the level of gridding. This method tries to set suitable number of grids based on current energy of network. It also guarantees suitable number of intermediary nodes to transmit the data to final destination; thereby reducing energy loss due to direct communication. The proposed protocol provides better solution to sudden energy hole creation and thereby improve network longevity.

Keywords Uneven-Gridding, Energy Efficiency, Energy Hole, Network Lifetime, Clustering

1. INTRODUCTION

   Wireless sensor networks became most rapidly emerging technologies in the research area which consists of low cost, small sized nodes with limited battery power. Developments in electronics and communication paved the way for drastic growth in this field [1]. Sensor nodes deployed in an area can be used for healthcare monitoring, structural analysis, natural calamities detection (earth quakes, tsunami detection etc.), war field surveillance, traffic monitoring etc [2]. The major issue related to sensor network is the energy conservation. It is infeasible to replace the battery once deployed. It affects the total working of network and we cant achieve the expected outcome, for which we had set up that network. Our aim is to maximize the battery life of each individual node and thereby increasing network lifetime.

   Major functions carried out in the network are: sensing, storing, communication and transmission. Among these steps, communication takes large amount of battery power. That is our major concern is to save the battery power. For this we have to reduce the communication overhead. Researchers are doing several experiments on this domain to mitigate the unnecessary communication and to increase the

   lifespan. There are several cases in which energy is wasted unnecessarily (eg: redundant broadcast of data) [3]. Such situations must be avoided and handled properly for smooth functioning of network.

   Routing is the process of transmitting the collected data from each sensor nodes to the BS. There are several approaches to route the packet to the destination. Hierarchical, flat based and location based routing protocols are major classification among them. Hierarchical routing protocols [4] are commonly used in most of the application as this method avoids the direct communication to BS. Here the entire network area is dived in to several clusters. For each cluster a CH will be selected which is responsible to hand over the sensed data from each cluster to the BS. Sensor nodes send their sensed data to corresponding CH during its allotted time slot. After collecting and aggregating the received data, it is the responsibility of CH to route the packet to BS where it get processed. The question is how effectively and efficiently this packet should rout. Many routing algorithms are put forward by many authors.

   Several applications require continues monitoring and sensing of data for a time period. In that case, it is not possible to recharge the battery periodically. What we can do is to maximize the battery life by suitably designing and developing routing mechanisms. Here we are trying to propose a new routing methodology which considers nodes energy level and network lifetime. In our paper, we divide the entire network in to several numbers of grids. This is determined based on the current average energy of nodes in the network. We then compare this value with a threshold; here we are comparing it with a factor of initial average energy and decides which level of gridding can be fixed. Based on the energy, the level of gridding varies that selects suitable number of grids for communication. Cluster head (CH) is selected for each grid to collect and forward data. The method support multihop communication which selects nearest node to pass the collected data to BS. As the energy decreases, the number of grids and intermediary nodes for communication increases. This helps to save the remaining energy by selecting most nearer nodes to relay packet. Distance between sender and receiver should get reduced in this approach.

   This paper is maintained as follows: Section II gives an overview of routing protocols so far developed, Section III illustrates system model, Section IV presents the proposed energy efficient routing protocol, and thereby conclusion with future enhancements in Section V.

2. RELATED WORK

   LEACH [5] proposed by W.Heinzelan et al. was the first clustering based routing protocol in which CHs are selected randomly. It doesnt guarantees uniform distribution of CHs and supports only single hop communication. Energy is not a factor in this approach where each node has equal probability to become CH. Once CH are selected, sensor nodes forwards the data to their head from which it is directly transmitted to the BS. Here nodes having lower energy may get selected as CH which will result is energy hole creation. Another improved version of LEACH is LEACH-C [6] in which BS decides which node to be act as CH. For this, every node will send its information including node id, energy and location. BS picks up some nodes as CHs after analyzing the energy level. Those nodes having energy greater than average network energy is selected as CH.

   LEACH-M [7] suggested by D.S. Kim, et al. put forwards LEACH based protocol extended with node mobility. But this method suffers high packet loss as the node keeps moving before selecting a new CH. A multi-hop LEACH [8] was proposed by Biradar et al. where an optimal multi-hop tree was created by connecting the selected CHs and BS. Data will be routed to the BS through the branches of tree which provides a feasible path. Farooq et al. [9] explains MR- LEACH in which the entire network is divided into several layers and for each layer a CH is selected. CH at the lower layer relay the packet to the CH at the higher layer to make the data reaches at destination.

   Mehdi Tarhani et al. illustrated SEECH [10] protocol which organizes the network into three layers consisting of relay nodes, normal nodes and CHs. This method selects a relay node to transmit the data from CH to BS rather than through intermediary CHs. The paper introduces a new idea to reduce the overhead of CH, but causes an additional overhead to maintain and elect relay nodes. An extra energy and communication cost is introduced in HEED [11], which suffers high message overhead and complexity.

   W. Mardini et al. put forward R-HEED [12] which mentions reforation of clusters based on some rules. Each cluster will be retained until it gets a reformation message; only CHs get rotated. Energy is not a parameter for CH selection. V-LEACH [13] elects a vice-CH which takes the role of CH when it is out of energy. It doesnt open an eye towards a solution in case of V-CH death. PEGASIS [14] suggested by S.Lindsey takes too much time for constructing chain to transfer the collected data from leader node to BS.

   EEM-LEACH [15] proposed by Ashlyn describes a routing protocol where nodes closer to BS communicate directly without involving to any cluster. Nodes in TEEN [16] suggested by A.Manjeshwar, et al. will reports data to the BS only when the sensed attribute reaches the threshold. But it is not reliable for periodic data collection. A solution to this

   problem is APTEEN [17] which can be used in any situation, either proactive or reactive conditions. Jung introduced CCS

   [18] that integrates clustering with PEGASIS approach. Here within each cluster a chain is formed and passes the data to the BS via leader nodes. The main disadvantage is that leader nodes are not selected based on residual energy. It causes uneven and unbalanced distribution of nodes.

   DHAC [19] maintains a resemblance matrix based on the information received from the neighboring nodes. It only requires single hop data for forming clusters. Method faces an overhead to maintain this matrix. TL-LEACH proposed by Loscrì et al. [20] generates a two-level tress structure with primary and secondary CHs. It tries to reduce the drawbacks of single hop communication. EECS suggested by Ye et al.

   1. needs a complete image of the network for implementing an energy efficient routing. BCDCP [22] is not suitable for larger communication as it supports only single hop data transmission. Protocols mentioned in papers [8], [23] improve the network lifetime as compared with single-hop transmission, but doesnt gave a solution to hot-spot problem.

      LPGCRA [24] proposed by Liu et al. addresses the hot spot problem suffer a major drawback that individual nodes consume more energy if the elected CH is far away. Grid based protocol GBR [25] suggested by Amrutha et al. elects nodes closer to the BS as CH. So, member nodes drain their energy at a very short time.

      In our proposed paper, we are trying to suggest a new routing method which considers energy conservation of individual nodes. For this we combine grid based and cluster based approach to implement an energy efficient network design. It selects varying number of grids and level of grids in each round based on the residual network energy. Not only the gridding, but also CH is selected based on energy. The method guarantees less transmission power needed for communication between nodes and a solution to the hot-spot problem.

3. SYSTEM MODEL

   In our proposed system model, sensor nodes N= {N1, N2 ,N3..Nn} are randomly deployed in a large sensing area where each Ni denotes i-th sensor node. Assumptions those we taken to consider while designing the new approach:

   • Nodes are of same type (homogeneous) with equal processing and storage capacity.

   • Each node has unique Id and has same initial energy.

   • Base Station (BS) is placed outside the deployment area and is static.

   • BS has knowledge on nodes Id, location and energy.

   • Once nodes are deployed, they are fixed and can adjust their transmission power based on the distance to the receiver.

   • BS is mounted with unlimited processing, computational and storage capability.

4. ENERGY EFFICIENT MULTILEVEL UNEVEN GRID BASED CLUSTERING PROTOCOL

   Our proposed method suggests a new approach to improve the lifetime of WSN which divides the entire network area in to several levels of grids. We suggest different level of

   gridding based on average energy of network. The method also incorporates clustering technique to collect and transfer the data to the BS. Hence we put forward an integrated gridding and clustering approach to mitigate the energy consumption and thereby increasing the network longevity.

   Features of this approach:

   • Guarantees uniform distribution cluster heads in each level of gridding.

   • Method uses centralized approach where BS decides level of gridding and CH.

   • Energy is taken as a parameter to decide level of gridding.

   • Reduces the energy required by each node to send data to the BS by choosing sufficient number of intermediary nodes.

   • Tries to provides a better solution to energy hole creation.

   • Not only level of gridding, but also CHs are selected based on distance and energy.

   • Guarantees that each node will be under one grid and one CH at a time.

   Steps to be carried out:

   1. Decide level of gridding and partition the network

   2. Select CH for each grid thus formed

   3. Collect the data from nodes and transmit to BS.

   Our paper mainly focused on the first step; that is how to determine the level of gridding and partition the network. In the proposed method, we divide the network area into horizontal levels of varying width based on the distance from the base station. It forms rectangular shaped grids of unequal size. For this we compare the current average energy with that of initial average energy. We can determine the level of gridding based on the deployment area. Here we are assuming four level gridding.

   After a certain period of time, the base station checks the current average energy of the network. It is then compared with threshold value (a factor of initial average energy); whether it is above threshold or below threshold or in between threshold and decides level of gridding. So, here we are taking current average energy as a parameter for uneven grid clustering, hence the size of the grid is based on the current average energy of the network.

   Algorithm1: Uneven_Gridclustering

   Input: X, Y co-ordinate of region, node id and location. Output: Grid formation.

   1. Initialize y=0,Ng=0,i=0

   2. Set width for partitioning x-axis as Wx

   3. while(y<Y)

   4. Initialize x=0

   5. Wg =Wx – y*r

      /*r denotes reduction rate*/

   6. while(x<X)

   7. x=x+Wx

   8. i=i+1

   1. Assign grid Id (Gid).

   2. if(y+Wg >Y)

   3. y=Y

   4. else

   5. y=y+Wg

   6. Ng=i

   In this work, a four level virtual grid formation is presented. The first level had shown in Fig 1, when the average energy of the network is greater than three-fourth of the initial average energy of the network.

   Fig 1. First level gridding

   Fig 2. Second level gridding

   In the second level shown in Fig 2, when the average energy of the network is between three-fourth and two-fourth of the initial energy. The third level is taken when the average energy of the network is between two-fourth and one-fourth of the initial energy, as show in Fig 3. Finally, the fourth level when the average energy of the network is less than one-fourth of the initial energy, as shown in Fig 4.

   Fig 3. Third level gridding

   Fig 4. Fourth level gridding

   After deciding the level of gridding, next step is to form CH for each grid. Here, we are using a simple method to determine CH.

   Algorithm2: CH_Selection

   Input: Node id and energy of each grid Output: CH for each grid

   1. Repeat the following steps for each Gid

   2. Calculate average energy(Eavg)

   3. for each nodes in Gid

   4. if(E(Ni)>Eavg)

   5. CH=Ni

   Here CH is selected based on energy comparison. Those nodes having higher energy in each grid will be selected as CH. Once cluster head is selected, it advertise that information to nearby nodes. On receiving this information, nodes nearer to he CH will send a join message and become a member under that CH. All the sensed data under each grid will be passed to that corresponding CH. After aggregating, each CH will forward collected data to BS.

   The method supports short distance communication which ensures less traffic to the nodes nearer to BS. Since the method purely based on energy, there is no chance for a node to get died quickly. We reduce the distance of communication by suitably selecting level of gridding. Since the number of intermediary nodes gets increased as the energy level decreases, the transmission power required by each individual node can be drastically reduced as the distance between nodes is very low. Fig 5 shows working of proposed model.

   Fig 5. Flow chart

   BS assigns a TDMA timeslot for each grid so that nodes under each grid will send data to their corresponding CH in its allotted time slot. CH aggregates the data received and transmit to BS via other intermediary CHs. CHs nearer to sender CHs are selected as relay nodes. Energy loss due to direct transmission can be avoided by this method. It guarantees sufficient number of intermediary CHs to forward the data towards BS. After a specific time period, BS again checks the average energy of the network and process continues.

5. CONCLUSION AND FUTURE WORKS Wireless sensor network used in wide variety of

   application is limited with battery power. The most challenging problem faced by researchers is to design and develop a suitable routing algorithm to save energy. Most of the papers suggest clustering approach where a CH is selected to collect and forward the data to BS.

   Here we are proposing a method which provides multiple level (multilevel) gridding which ensures lower energy consumption. The paper illustrates four level virtual grid formations which is done based on the average network energy. We are comparing the current average network energy with that of a factor of initial average energy of nodes and select a suitable grid level. Then for each grid, CH is selected based on residual energy. This approach provides uniform distribution of CHs and supports multi-hop communication. It minimizes the hot-spot problem by reducing the traffic. The protocol saves individual battery power of nodes by ensuring short distance communication. Here BS determines level of gridding and CH selection which significantly reduces the energy of nodes. The protocol utilizes the BSs energy to maximum extent thereby increasing network longevity.

   As future work, we can consider node density and transmission range of the nodes for the grid cluster formation.

6. REFERENCES

1. C.Perera, A. Zaslavsky, P. Christen, and D. Georgakopoulos,Context aware computing for the internet of things: A survey, IEEE Commun. Surv. Tutorials, vol. 16, no. 1, pp. 414-454, 2014.

2. Nikolaos A. Pantazis, Stefanos A. Nikolidakis and Dimitrios D. Vergados, "Energy-Efficient Routing Protocols in Wireless Sensor Networks: A Survey," IEEE Communications Surveys & Tutorial, vol 3, pp. 1-41, 2012.

3. Navdeep Kaur,Deepika Sharma and Prabhdeep Singh Classification of Hierarchical Routing Protocols in Wireless Sensor Network : A Survey International Journal of P2P Network Trends and Technology Volume 3 Issue 1-2013.

4. Khamfroush H., Saadat R., Khademzadeh A., Khamfroush K., Life time increase for wireless sensor networks using cluster based routing, International Association of Computer Science and InformationTechnology-Spring Conference(IACSITSC),2009, pp. 14- 18.

5. W.Heinzelman,A.Chandrakasan,H.Balakrishnan,Energy-Efficient Communication protocol for wireless microsensor networks,in the Proceedings of the 33rd International Conference on System Science(HICSS00), Hawaii, U.S.A., January 2000.

6. X. H. Wu, S. Wang, Performance comparison of LEACH and LEACH- C protocols by NS2, In Proceedings of 9th International Symposium on Distributed Computing and Applications to Business, Engineering and Science. Hong Kong, China, pp. 254-258, 2010

7. D. S. Kim and Y. J. Chung, "Self-organization routing protocol supporting mobile nodes for wireless sensor network," in Proc.First International Multi-Symposiums on Computer and Computational Sciences, Hangzhou, China, 2006.

8. R. V. Biradar, S. R. Sawant , R. R. Mudholkar and V. C. Patil, "Multihop routing in self-organizing wireless sensor networks", IJCSI International Journal of Computer Science, January 20 II, vol. 8, pp.155- 164.

9. O. Farooq, A. Dogar and G. Shah, "MR-LEACH: Multi-hop routing with low energy adaptive clustering hierarchy", 2010 IEEE 4th International Conference on Sensor Technologies and Applications, pp. 262-268.

10. M. Tarhani, Y. S. Kavian, and S. Siavoshi, SEECH: Scalable energy efficient clustering hierarchy protocol in wireless sensor networks, IEEE Sensors J., vol. 14, no. 11, pp. 39443954, Nov. 2014.

11. Younis, O.; Fahmy, S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad- hoc sensor networks. IEEE Trans. Mobile Comput. 2004, 3, 366379.

12. W. Mardini, M. B. Yassein, Y. Khamayseh, and B. a. Ghaleb, Rotated hybrid, energy-efficient and distributed (R-HEED) clustering protocol in WSN, WSEAS Trans. Comm , vol. 13, pp. 275-290, 2014.

13. Yassein, Improvement on LEACH Protocol of Wireless Sensor Network (VLEACH), Int. J. Digit. Content Technol. its Appl., vol. 3, no. 2, pp. 132136, 2009.

14. S. Lindsey, C.Raghavendra, PEGASIS: Power-Efficient Gathering in Sensor Information Systems, In Proc. IEEE Aerospace Conference, USA, Montana, Vol. 3, pp. 1125-1130, 2002.

15. A. Antoo, and R. Mohammed, "EEM-LEACH: Energy Efficient Multihop LEACH Routing Protocol for Clustered WSNs", IEEE International Conference on Control, Instmmentation, Communication and Computational Technologies (ICCICCT), 20 J 4, pp. 812-818.

16. A. Manjeshwar, D. Agrawal, TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks, In Proc. 15th InternationalParallel and Distributed Processing Symposium (IPDPS01) Workshops, USA, California, 2001, pp. 2009-2015.

17. Manjeshwar, A.; Agrawal, D. P. APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks. In Proceedings of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile computing, Lauderdale, FL, USA, 1519 April 2002; pp. 195 202.

18. Jung, S.; Han, Y.; Chung, T. The Concentric Clustering Scheme for Efficient EnergyConsumption in the PEGASIS; In Proceedings of the 9th International Conference on AdvancedCommunication Technology, Gangwon-Do, Kore ; pp. 260265, February 2007.

19. C. H. Lung, C. Zhou, Using Hierarchical Agglomerative Clusteringin Wireless Sensor Networks: An Energy-efficient and Flexible Approach,Ad Hoc Networks, 2010, Vol. 8, Issue 3, pp. 328-344.

20. Loscri, V.; Morabito, G.; Marano, S.; A Two-Level Hierarchy for Low- Energy Adaptive Clustering Hierarchy; In Proceedings of the 2nd IEEE Semiannual Vehicular TechnologyConference, Dallas, TX, USA; pp. 18091813; September 2005.

21. Ye, M.; Li, C.; Chen, G.; Wu, J. An energy efficient clustering scheme in wireless sensor networks. Ad Hoc Sens. Wirel. Netw. 2006, 3, 99 119.

22. Murugunathan, S.D.; Ma, D.C.F.; Bhasin, R.I.; Fapajuwo, A.O. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks. IEEE Radio Commun. 2005, 43, S8S13.

23. T. Qiang, W. Bingwen and D. Zhicheng, "MS-LEACH: A routing Protocol combining multi-hop transmissions and single-hop transmissions", IEEE Paciflc- Asia Conference on Circuits, Communications and System, 2009, pp. 107-110.

24. Liu, W. D., Wang, Z. D., Zhang, S., & Wang, "A low power grid-based cluster routing algorithm of wireless sensor ntworks", In Information technology and applications (IFITA), 2010, vol. I, pp. 227-229.

25. Amrutha K. M. , Ashwini P. , Raj D. K., Rani G. K., & Mundada, M. R., "Energy efficient clustering and grid based routing in wireless sensor networks.", In Proceedings of international conference on advances in computing, Springer India, 2012, pp. 69-74.

BIOGRAPHY

Elvin Kuruvilla: Assistant Professor in the Department of Computer Science and Engineering, Vijnan Institute of Science and Technology, Elanji, Kerala, India. His research interests are sensor networks, data mining and wireless communication.

Sreeranjini Nandakumar: Assistant Professor in the Department of Computer Science and Engineering, Vijnan Institute of Science and Technology, Elanji, Kerala, India. Her research interests are data mining, wireless sensor networks and soft computing.