An Efficient Energy Balanced Clustering and Routing Protocol for Wireless Sensor Network

An Efficient Energy Balanced Clustering and Routing Protocol for Wireless Sensor Network

Shankar Sarji P

1. ech (Computer Science & Eng) Sahyadri College of Engineering and Management

   Mangalore, Karnataka, India

   Arya Mohan

   Asst. Professor (Information Science & Eng) Sahyadri College of Engineering and Management Mangalore, Karnataka, India

   Abstract–Wireless Sensor Networks (WSN) consists of hundreds of resource constrained sensor nodes. WSN nodes cooperatively monitor various environmental and physical conditions. WSN has gained one of the interested areas in the field of research from last few years. WSN uses various nodes for the communication. To enhance the lifetime of the whole networks energy reduction is the necessary consideration for design and analyze of the clustering and routing protocols. In this paper we present a study of various protocols which are used to enhance energy efficiency of the WSN such as LEACH (Low Energy Adaptive Clustering hierarchy), HEED (Hybrid Energy-Efficient Distributed Clustering), and CEBCRA (Cost Based Energy Balanced Clustering and Routing Algorithm). Finally we conclude this paper with future research and challenges.

   Key words Wireless Sensor Network; clustering; Network lifetime; Energy Efficient.

   1. INTRODUCTION

      With the faster growing in electronics industry, small inexpensive battery-powered wireless sensors have made an impact on the communications with the physical world.

      WSN consists of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations [1]. The development of WSN was originally motivated by military applications for battlefield surveillance. Thereafter, WSN works are used in many civilian application areas, including environment and habitat monitoring, health care applications, home automation, and traffic control. Each sensor node is battery powered and equipped with integrated sensors, data processing capabilities and short-range radio communications [2]. This network contains a large number of nodes which sense data from an impossibly inaccessible area and send their reports towards a processing centre which is called "sink". Since, sensor nodes are power-constrained devices, frequent and long-distance transmissions should be kept to minimum in order to prolong the network lifetime. Thus, direct communications between nodes and the base station are not encouraged. Because the large part of energy in the network is consumed in wireless communication in a WSN, several communication protocols have been proposed to realize power-efficient

      communication in these networks. One effective approach is to divide the network into several clusters. In a cluster based WSN, the sensor nodes are efficiently grouped into distinct clusters with a single leader for each cluster called cluster head (CH) (Fig.1). CHs are either selected among normal sensor nodes or in some case some high energy nodes called gateways are deployed as CHs [3]. Each sensor node belongs to one and only one cluster and communicates with its CH. All sensor nodes sense the local data and send it to its CH. Once the CHs receive the data from all their corresponding member sensor nodes, they perform data aggregation and send the processed data to the sink through other CHs. In case, CHs are selected from normal sensor nodes, they can die quickly due to the extra work load for data aggregation and data forwarding due their limited energy [3]. Moreover, the CHs, which are close to the base station or on some energy efficient path, are inevitably used as a relay node to forward the packet to the base station and thereby drain their energy very quickly. Therefore, selection of CHs with cluster setup and the routing need to be properly addressed for balancing the energy consumption of the CHs to improve the network lifetime.

      Following are the key features of a sensor network [4]:

      1. Enhance network lifetime.

      2. Balance energy efficiency.

      3. Data in sensor network are bound either downstream to nodes from a sink or upstream to a sink from nodes.

      Base Station Cluster Head Sensor Node

      Fig. 1: A Wireless Sensor Network Model

   2. LEACH

      LEACH is one of the generic clustering based routing protocol it minimizes the energy consumption in sensor network. LEACH uses random distribution for the energy load between the sensors in the network. LEACH is a self organizing clustering routing protocol for wireless sensor network. In LEACH, nodes are organized as local clusters where one node acts as the cluster head or base station. If we choose the cluster head as priori and fixed it throughout for the system lifetime it is easy to see that the unlucky sensors chosen to be cluster heads would die quickly ending the useful time of all other nodes belonging to those clusters. In LEACH, it includes the randomized rotation of the maximum energy cluster head position that it rotates between the various sensors in a way so the energy of a single node should not be exhaust. LEACH performs local data fusion to compress the amount of data which is sent from the clusters to the base station to reduce the energy dissipation and enhance the lifetime of the system.

      1. Leach Algorithm

         The operation of LEACH is made into rounds, where each round begins with a set up or advertisement phase to organize the clusters; it is followed by the steady state phase to transmit the data to the base station [5]. To minimize the overhead the steady state phase is long as compared to the set up phase.

         1. Advertisement Phase

            When clusters are being created, each node decides whether or not to become a CH for the current round or not. This decision is based on the suggested percentage of CHs for the network and the number of times the node has been a CH. This decision is made by the node n choosing a random number between 0 and 1.If the number is less than a threshold T(n),the node becomes a CH for the current round. The threshold is set as:

         2. Cluster Set up Phase

            When each node has decided to which cluster head node it belongs, it must inform the cluster head node that it is a member of the cluster head node. Each node transmits this information back to the cluster head node using the CSMA MAC protocol. All the nodes must keep their receivers on.

         3. Schedule Creation

            The cluster head node receives all the messages for the nodes that would like to be included in the cluster. Based on the number of nodes in the cluster, the cluster head nodes creates a schedule which inform each node when it can transmit the data, it is known as the TDMA schedule.

         4. Data communication

            After creating clusters and its arrangement by the TDMA schedule, data communication begins. Assuming all nodes have data to transmit and they transmit the data to the cluster head on their scheduled time. This communication uses a minimal amount of energy. The cluster head node must keep their receivers on to receive the data from the nodes in the cluster. When all data has been received cluster head node performs signal giving out functions to compress the data into a single signal. Then the composite signal has sent to the base station.

   3. HEED

      HEED is a multi-hop clustering algorithm for WSN, the main focus is on efficient clustering by proper selection of CHs based on the physical distance between nodes [6].

      Objctives of HEED are

      • Distribute energy consumption to prolong network lifetime;

      • Minimize energy during the CH selection phase;

      • Minimize the control overhead of the network.

      1. HEED parameters for CH selection

         Step 1: The residual energy of each node is used to

         T (n)

         P if

         1

         n G

         probabilistically choose the initial set of CHs. This parameter is commonly used in many other

         1 P (r mod )

         P

         0 othrwise

         Where P=desired percentage of cluster heads, r=current round and G is the set of nodes that have not been cluster heads in the last 1/P rounds. Using this threshold each node will be a cluster head at some point within 1/P rounds. The nodes that are cluster head in round 0 cannot be cluster head for the next 1/P rounds, since there are fewer nodes that are eligible to become the cluster heads. Each node that has elected a cluster head for the current round broadcast an advertisement message to the rest of the nodes. For this advertisement phase, the cluster heads use a CSMA MAC protocol. The non cluster head nodes keep their receivers to hear the advertisement of all the cluster head nodes. After the completion of this phase, each non cluster head node decides the cluster to which it will belong for this round.

         clustering schemes.

         Step 2: Intra-Cluster Communication Cost is used by nodes to determine the cluster to join. This is especially useful if a given node falls within the range of more than one CH. In HEED it is important to identify what the range of a node is in terms of its power level as a given node will have multiple discrete transmission power levels. The power level used by a node for intracluster announcements and during clustering is referred to as cluster power level [6]. Low cluster power levels promote an increase in spatial reuse [6] while high cluster power levels are required for intercluster communication as they span two or more cluster areas. Therefore, when choosing a cluster, a node will communicate with the CH that yields the lowest intra-cluster communication cost. The intra-cluster communication cost is measured using the Average Minimum Reachability Power (AMRP) measurement [6]. The AMRP is the average of all

         minimum power levels required for each node within a cluster range R to communicate effectively with the CH i. The AMRP of a node i then becomes a measure of the expected intra-cluster communication energy if this node is elevated to CH. Utilizing AMRP as a second parameter in CH selection is more efficient then a node selecting the nearest CH [7].

      2. Advantages

         • HEED distribution of energy extends the lifetime of the nodes within the network thus stabilizing the neighboring node.

         • Does not require special node capabilities, such as location-awareness.

         • The algorithm guarantees that every sensor is part of just one cluster, and the cluster heads are well- distributed.

         • HEED are that nodes only require local (neighborhood) information to form the clusters

         • Neighbour(Si) denotes the set of all sensor nodes that are within communication range of Si. Therefore, Neighbour(S1) = {Sj | Sj Com(Si) /\ Sj

           {S -Si}}

           Algorithm: Broadcast Nodes, Selection of CH and Transfer Data to BaseStation

           Input: Residual energy i.e., EResidual(Si)

           Output: Si as CH and Transfer Data to BaseStation

           Step 1: Si send the broadcast message to all sensor nodes to neighbours to neighbours with incremented hopcount

           Step 2: If current hopcount < previous hopcount Update hopcount select new shortest path

           Else

           Discard the message

           Step 3: calculate the Si energy weight

      3. Disadvantages

         • The random selection of the cluster heads may

           W (Si ) E

           Re sidual

           (Si )

           ERe sidual(Si )

           Neighbour (Si )

           cause higher communication overhead for:

           • The ordinary member nodes in communicating with their corresponding cluster head

           • Cluster heads in establishing the communication among them, or

           • Between a cluster head and a base station.

         • The periodic cluster head rotation or election needs extra energy to rebuild clusters.

   4. CEBCRA

      CEBCRA is distributed algorithm which consists of three phases namely Broadcast node, CH selection and Data Transfer. The algorithm is fully based on the local information of a sensor node such as residual energy, number of neighbours and their distances [3]. CEBCRA selects CHs amongst the normal sensor node using a weight function of the residual energy and the number of neighbours of a sensor node. Then all non-CH sensor nodes join a CH, which has maximum cost value within its communication range. The cost function is the composite measure of residual energy of the CH, its distance to base station and also the distance from the sensor node to the CH. For multi-hop routing, a CH needs to relay the data to the BS through other CHs. Therefore, the other CHs are treated as relay nodes. So, a CH needs to find the best neighbour CH (relay node) for data routing such that energy consumption is minimum. In the proposed work, the best neighbour relay node is selected by measuring the cost of each path towards BS.

      The associated terminologies and notations are as follows.

      • The set of sensor nodes is denoted by S = {S1, S2

        …Sn}.

      • CH = {CH1, CH2, CH3…} denotes the set of elected cluster heads (CHs) from the normal sensor nodes.

      • EResidualSi denotes the residual energy of sensor node Si

        Step 4: Si elects himself as CH

        Fetch the neighbours energy weight If self Si weight < neighbours weight

        Send cluster formation list

        Send join request to as more weight as its neighbour

        Else

        Fetch neighbours process

        Send join request to neighbours Declare as CH

        Step 5: Transfer data to base station through nodes If node as CH

        Get routing table

        Find path to next shortest CH Send data to base station

        Else

        Forward to CH

        Find path to next shortest CH Send data to base station

   5. CONCLUSION

From the last few years, the routing protocol in WSN has become one of the research field. There are number of research achievements which have been existed in this field. In this paper, we made a great deal of analysis and research and present the study of cluster based routing protocol in WSN such as LEACH, HEED and CEBCRA. The CEBCRA

routing protocol provides improvement over LEACH and HEED to achieve the longer network lifetime. There are still more issues and challenges which need to be solved in the sensor networks. The main issues are:-

• Security:- how to secure the WSN and guarantee the data which have transmitted and about eavesdroppers.

• Effectiveness:- how to effectively utilize the bandwidth and energy for specific application.

REFERENCES

1. F. Akyidiz, Y. Sankarasubramaniam W. Su, and E. Cayirci, "A survey on sensor networks", IEEE Communication Magzine, pp 102-114. 2002.

2. Sonam Palden Barfunga and Prativa Rai, Energy Efficient Cluster Based Routing Protocol for Wireless Sensor Networks, International Conference on Computer and Communication Engineering, pp. 603-607, 2012.

3. Pratyay Kuila and Prasanta K. Jana, An Energy Balanced Distributed Clustering and Routing Algorithm for Wireless Sensor Networks, IEEE International Conference on Parallel, Distributed and Grid Computing, pp. 220-225,2012.

4. Neha Jain, Energy Efficient And Cluster Based Routing Protocol for Wireless Sensor Network: A Review, International Journal of Advance Technology & Engineering Research, pp. 22-24, 2011.

5. Qian Lao and Hao Zhu, An Energy Balanced Clustering Algorithm Based on LEACH Protocol, International Conference On Systems Engineering and Modeling, pp. 72-77, 2013.

6. D. J. Dechene, A. El Jardali, M. Luccini and A. Sauer. A Survey of Clustering Algorithms for Wireless Sensor Networks, Department of Electrical and Computer Engineering, The University Of Western Ontario London, Ontario, Canada.

7. Ossama Younis and Sonia Fahmy, Distributed Clustering in Ad- hoc Sensor Networks: A Hybrid, Energy-Efficient Approach, Department of Computer Sciences, Purdue University 250 N. University Street, West Lafayette, IN 479072066, USA.