A Survey on Energy Efficient Routing Protocols for Wireless Sensor Networks
Muhammad Asad

Department of Computer Science
COMSATS INSTITUTE OF INFORMATION TECHNOLOGY, WAH CANT Abstract: To tackle the limited life-time issue of Wireless Sensor Networks (WSNs) is a very key research domain in order to design, development and implementation of energy effective algorithms. So, the major concern of researcher is energy efficiency in wireless sensor networks. WSNs acknowledged magnificent consideration from both industry and academic because of assure numerous latent applications in military and civilian areas. WSN consists of sensor nodes sensing the data, communication capabilities and data processing. Network can be deployed in the area of interest and collaborate to complete a task. WSN has multiple exclusive characteristics, such as memory constraints, computation, stern power, asymmetric data transmission, higher unreliability of sensor nodes and denser node deployment and presents several new challenges for the ultimate application and development of WSNs. In exacting, sensor nodes are operates without attendance and battery powered for a long period of time. In order to recharge or change these batteries of sensor nodes are quite difficult or impossible in most of the cases. In this regard, energy efficient routing protocols in wireless sensor networks are essential for exceeding the network lifetime of sensors. In this paper I present a comparatively survey of few prominent energy efficient routing protocols proposed in the literature for wireless sensor networks. I analyze and compare them by different approaches by using significant metrics. And finally, conclude and summarize the paper by some possible future direction.

LEACH (Low-Energy Adaptive Clustering Hierarchy)

Low Energy Adaptive Clustering Hierarchy ("LEACH") was proposed by W. R. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, is a TDMA-based MAC protocol which is integrated with clustering and a simple routing protocol in wireless sensor networks (WSNs). The goal of LEACH is to lower the energy consumption required to create and maintain clusters in order to improve the life time of a wireless sensor network. This WSN is considered to be a dynamic clustering method. LEACH has two phases the set-up phase and the steady-state phase   The Set-Up Phase ▪ Where cluster-heads are chosen The Steady-State ▪ The cluster-head is maintained ▪ When data is transmitted between nodes

The LEACH Network is made up of nodes, some of which are called cluster-heads The job of the cluster-head is to collect data from their surrounding nodes and pass it on to the base station; LEACH is dynamic because the job of cluster-head rotates Sensors elect themselves to be local cluster-heads at any given time with a certain probability. These cluster-head nodes broadcast their status to the other sensors in the network. Each sensor node determines to which cluster it wants to belong by choosing the cluster-head that requires the minimum communication energy. Once all the nodes organized into cluster, each clusterhead scheduled for the nodes in its cluster. After a various experiments with a different thresholds and found that no matter how much energy each node is given, it takes approximately 8 times longer for the first node to die and approximately 3 times longer for the last node to die in LEACH as it does in any of the other protocol. The operation of LEACH is broken up into the rounds, where each round begins with a set-up phase. When clusters are being created, each node decides whether or not to become a clusterhead for the current round. The decision is based on the suggested percentage of cluster heads for the network and the number of times the node has been a cluster-head so far. 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 cluster-head for the current round. The threshold is set as: ������ (������) = ������ (������) = 0
������ 1−������∗(������ ������������������ ������ −1)

If ������ ɛ G Otherwise

Where n is a random number between 0 and 1, P is the cluster head probability and G is the set of nodes that weren’t cluster heads in the previous rounds. After the phase is complete, each non-cluster head node decides the cluster to which it will belong for this round. This decision is based on the received signal strength of the advertisement. LEACH-centralized (LEACH-C) is similar to LEACH in operation except cluster formation. In LEACH-C, the cluster head selection is carried out at BS. During the setup phase, BS receives from other nodes information about their current locations and remaining energy levels. BS uses the remaining energy level to determine the candidate set for cluster head node. The average node energy is computed and the node has remaining energy falling below this value will be removed from the candidate set.
LEACH forms clusters by using a distributed protocol, in which nodes by self made an autonomous decision with virtually no centralized control. Leach-c designed a layout a cluster formation algorithm by this we now have a particular variety of clusters,, while in just about every round. In addition, in case nodes starts with equal energy, our goal is to try to evenly distribute the energy load among all the nodes in the network consequently that we now have absolutely no overly-utilized nodes that will will come to an end of energy prior to the some others. Being a cluster head node is really a lot additional energy extensive compared to being a non-cluster head node, this requires that all node get their turn as cluster head. Each sensor node elects itself to be a cluster head at the beginning level of round r+1 ( starts at time t ) with probability Pi(t). Pi(t) is chosen such that the expected number of cluster head nodes for this round is k. Thus, if there are N nodes in the network
������

������ [ #������������] = ∑ ������������ (������) ∗ 1 = ������
������ =0

(1)

Ensuring that all nodes are cluster heads the same number of times requires each node to be a cluster head once in N/k rounds on average. If is the indicator function determining whether or not node i has been a cluster head in the most recent ( r mod (N/k) ) rounds (i.e., Ci(t) =0 if node i has been a cluster head and one otherwise), then each node should choose to become a cluster head at round r with probability
������ ������������ (������) = { ; ������������(������) = 1 ������ ������ − ������ ∗ (������������������������ ������ ������������ (������) = {0 ; ������������ (������) = 0
Only nodes which have not really recently been cluster head, as well as that most probably convey more power available compared to nodes which have just perform particular energy-intensive function, can become cluster head from round r+1. The actual anticipated quantity of nodes which have not really already been cluster heads within the very first round is N - k * r. Following N/k models, just about all nodes are required to possess already been cluster heads as soon as, subsequent that they all are permitted carry out this within the next series associated with rounds. Because Ci(t) is one that node is actually qualified to become a cluster head at time t as well as absolutely no or else, ∑ ������ ������������ (������) the term signifies the entire quantity of nodes which are qualified to become a cluster heads from time t as ������=1 well as absolutely no.

(2)

������

������ [∑ ������������(������)] = ������ − ������ ∗ ( ������ ������������������
������=1

������ ) ������

(3)

This ensures that the energy at all nodes are approximately equal to each other after every N/k rounds . Using (2) and (3), the expected number of cluster heads per round is
������

������ [ #������������] = ∑ ������������ (������) ∗ 1
������ =0

= ( ������ − ������ ∗ ( ������ ������������������

������ ������

)) ∗

������ ������−������∗( ������ ������������������
������ ������

)

= ������

(4)

This possibility with regard to being a cluster head is actually in line with the presumption that nodes begin with the same quantity of energy, which just about all nodes possess information in order to deliver data throughout everybody in the cluster. In the clusters every nodes possess various levels of energy, the nodes along with mu ch more energy ought to be cluster head more often compared to nodes with less energy, to ensure that all nodes die at approximately the same time. This is often accomplished through environment the actual likelihood to become the cluster head like a perform of the node's energy in accordance with the actual combination energy left within the network, rather than the amount of time the node may be a cluster head, Thus ������������ (������) = min { ������������(������) ������, 1 } ������������������������������������(������)
������

(5)

Where ������������(������) is the current energy of the node ������ and

������������������������ ������������ (������) = ∑ ������������(������ )
������=1

(6)

Using these probabilities, the nodes with higher energy are more likely to become cluster heads than nodes with less energy. The expected number of cluster head nodes is
������

������ [ #������������] = ∑ ������������ (������) ∗ 1 = (
������ =1

������1 (������ ) ������������������������������������

+ ………+

������������ (������) ������������������������������������

) ������ = ������,

(7)

Set-Up Phase:  Advertisement (I am a Cluster-Head)  Cluster Set-Up (I am in your Cluster)  Schedule Creation (This is your slot) Steady-State Phase:       Data Transmission using TDMA Everyone uses the same channel Different clusters use different CDMA codes Code chosen in random Cluster-Head communicate with Sink Can be extended to Hierarchical Clustering

Limitations of LEACH:     “Hot Spot” Problem (Nodes on a path from an event-congested area to the sink may drain) Inadequate for Time-Critical Applications Stationary Sink – Maybe Unpractical Basic Algorithm assumes any node can communicate with sink – limited scale PEGASIS (Power-Efficient Gathering in Sensor Information Systems)
Power Efficient Gathering in Sensor Information System (PEGASIS), proposed by Lindseyet al. PEGASIS is an improvement over LEACH. Basic idea of PEGASIS is designed for each and every node to simply communicate with their close neighbors and take turn for being a leader regarding communication with the base station. Locations of sensor nodes located randomly, and every sensor node provides the potential of information detection, wireless communication, information blend and also position of node. Energy load is distributed uniformly among the sensor nodes in the whole network. PEGASIS used a greedy algorithm, organized in chained form of nodes which can be consummate by themselves or assigned by the base station and broadcast to every sensor node. If the chain is formed by nodes themselves then the nodes gets the location information of all nodes in the network first and work out on the chain by using the greedy algorithm. When the chain formation process is executing, it is assumed that all nodes in the network have global knowledge and then greedy algorithm will working. The construction of chain is begin from the farthest node from the base station and the nearest neighbor of this node will be the next in the chain. If the node dies in the chain, then the chain will bypass this node and construct again with the same method by using the same greedy algorithm. In each round of PEGASIS the data is gathered from sensors and transmit using chain. Node receives sensed data from their neighbor accumulate with its own data and transmit it to the next neighbor. The data is finally received by the base station from the leader at random position by moving from node to node. It is important that a leader die at random location, the idea behind is that death of nodes at different location is to improve the health of the network.

Limitations of PEGASIS:  Stationary Nodes  Global Information Limited Scale:  Information travels nodes by nodes  Assumes any node can communicate with base station TEEN (Threshold sensitive Energy Efficient sensor Network protocol) Threshold sensitive Energy Efficient sensor Network protocol (TEEN), proposed by anjeshwar and agarwal. TEEN is a hierarchical protocol, the objective of TEEN is to manage the sudden changes in the sensed aspect such as humidity. Protocol used the data symmetric approach by combining the hierarchical technique. Nodes in the network sense the environment

constantly, but the consumption of energy in this protocol will be less than the proactive network, because transmission of data is frequent and less. A two threshold levels are built, hard threshold and soft threshold and a 2-tier clustering topology is defined. The former threshold is often a threshold value for the sensed attribute. It's the overall worth from the attribute above that, the node sensing this threshold value must have to start its transmission and report to its CH. The last threshold is a little modify from the threshold value of sensed attribute that triggers the node to modify in its transmitter as well as transmit.
In TEEN, a CH transmits it's associates both a hard threshold and a soft threshold. So the particular hard threshold makes an attempt to relieve information communications by simply making it possible for the particular nodes in order to send only if the particular sensed attribute will in range. The soft threshold additionally minimizes information communication could have normally taken place when there is the little or no change within the sensed attribute. On the expense associated with energy consumption, a smaller value in the soft threshold yields much more exact facts in the network, therefore users can easily command the particular trade-off in between energy efficiency as well as information accuracy and reliability with the parameter realignment. Furthermore, the particular soft threshold is usually different plus the users can change the fresh variables seeing that essential from just about every cluster modify time.

Limitations of TEEN:  “Hot Spot” Problem  Cluster-Heads need to listen constantly  Wasted time-slots  Can’t distinguish dead nodes  Other LEACH problems…

APTEEN
(The Adaptive Threshold sensitive Energy Efficient sensor Network protocol)
The Adaptive Threshold sensitive Energy Efficient sensor Network protocol (APTEEN), introduced by Manjeshwar and Agrawal, is an extension to TEEN and aims at both transmitting periodic data and reacting to time critical events. APTEEN, on the other hand, is a hybrid protocol that changes the periodicity or threshold values used in TEEN according to the requirement of users and the type of the application. APTEEN is based on a query system which allows three types of queries: historical, on-time, and persistent which can be used in a hybrid network. Moreover, QoS requirements are introduced for the on-time queries and minimum delay is achieved by a TDMA schedule with a special time slot assignment manner. The distinctive feature of APTEEN is to switch between proactive and reactive modes to transmit data. All nodes sense the environment continuously, but only those nodes which sense a data value at or beyond the hard threshold permit transmitting. Once a node senses a value at or beyond the hard threshold, it transmits data. If a node does not send data for a time period equal to the count time, it must sense and transmit the data again. In APTEEN, each CH aggregates the data from the MNs within its cluster and transmits the aggregated data to the

BS. During the process of data aggregation, it is assumed that the data received from the corresponding MNs are sufficiently correlated, thus it reduces a large amount of redundancy of the data to be transmitted to the BS. Moreover, a modified TDMA schedule is used to implement the hybrid network by assigning each node in the cluster a transmission slot. Additionally, APTEEN offers a lot of flexibility by allowing the user to set the CT interval and the threshold values for energy consumption can be controlled by changing the CT as well as the threshold values. Limitations of APTEEN:  LEACH Problems; “Hot Spot” Problem (Nodes on a path from an event-congested area to the sink may drain) – Inadequate for Time-Critical Applications – Stationary Sink – Maybe Unpractical – Basic Algorithm assumes any node can communicate with sink – limited scale Complex Logic; – Additional overhead and complexity of cluster construction in multiple levels – Additional complexity required to implement the threshold functions and the count time –



SEP (Stable Election Protocol)
A Stable Election Protocol (SEP) (G. Smaragdakis et al, 2004) is improved version of LEACH protocol. Main aim of it was used heterogeneous sensor in wireless sensor networks. This protocol have operation like LEACH but with this difference that, in SEP protocol sensors have two different level of energy. SEP based on weighted election probabilities of each node to become cluster head according to their respective energy. This approach ensures that the cluster head election is randomly selected and distributed based on the fraction of energy of each node assuring a uniform use of the nodes energy. In SEP, two types of nodes (normal and advanced) are considered. It is based on weighted election probabilities of each node to become cluster head according to the remaining energy in each node. This prolongs the stability period i.e. the time interval before the death of the first node. Advantage:  SEP does not require any global knowledge of energy at every election round. Drawback:  The drawback of SEP method is that the election of the cluster heads among the two type of nodes is not dynamic, which results that the nodes that are far away from the powerful nodes will die first

Classification of Different Clustering Protocols in WSNs
Clustering Routing Protocols LEACH PEGASIS variable TEEN fixed APTEEN variable SEP variable

Variability of variable Cluster Count Uniformity of even Cluster Sizes Clustering Characteristics Intra-Cluster Routing Inter-Cluster Routing Existence Singlehop singlehop Clusterhead Based

even

even

even

even

multihop singlehop no-cluster headbased
N/A

singlehop multihop clusterhead based

singlehop multihop clusterhead based

multi-hop

single-hop

Clusterhead based

Difference of Homogeneous Capabilities Cluster-Head Charateristics Mobility Role Stationary Relay Aggregation

homogeneous homeogeneous homogeneous

N/A N/A

stationary

stationary

stationary relay aggregation distributed

relay relay aggregation aggregation

Control Manner Execution Nature Clustering Process Convergence Time Parameters For CH selection Proactivity

Distributed Distributed Distributed distributed

Probabilistic Probabilistic Probabilistic probabilistic

probabilistic

constant

constant

constant

Constant

constant

adaptive

adaptive adaptive

adaptive

adaptive

proactive

proactive

reactive

proactive reactive lifetime extension

proactive

Objectives

load Balancing

load lifetime Balancing extension

Prolongs stability

Entire Proceeding Of the Algorithm

Algorithm

Cluster data data data Construction transmission transmission transmission

cluster construction

Comparison of Different Clustering Protocols in WSN’s
Protocol Name LEACH PEGASIS TEEN APTEEN SEP DEEC Energy Efficiency Very low Low Very high Moderate Moderate Very high Cluster Stability Moderate Low High Very low High High Scalability Very low Very low Low Low Moderate Moderate Delivery Delay Very small Very large Small Small Small Very small Load Balancing Moderate Moderate Good Moderate Moderate Good Algorithm Complexity Low High High Very high High High

Performance Comparison:
 Leach vs Previous Protocol:

Figure: System lifetime using direct transmission, MTE routing, static clustering, and LEACH with 0.5 J/node.



LEACH vs PEGASIS:

Figure: Performance results for a 50m x 50m network with initial energy .25J/node.

 Leach vs TEEN and APTEEN:
Comparison of the no. of nodes alive for LEACH, APTEEN and TEEN

Figure: Comparison of average energy dissipation for LEACH, APTEEN and TEEN

 LEACH vs SEP and DEEC:

Figure: Energy dissipation diagram of LEACH, SEP and DEEC

Conclusion
In this survey paper I discussed a lot of conventional protocols and their modification which includes energy efficiency with the importance of energy efficient routing protocols. I conclude that there is not a single protocol which can give the best performance in WSNs. I have also discussed the factors that can be improved to increase the routing efficiency. Performance of the protocol varies according to the variation in the network parameters. Sometimes the mobility of the node of the network is high sometimes energy of the node is our prime concern, We have discussed that in which type of network environment these protocols will perform better and for which type of networks these are not suitable. The comparisons of these energy efficient protocols have been shown in this survey report. We have tried to present almost all possible approaches of energy efficient routing protocols.

References:
[1]Heinzelman, Wendi Rabiner, Anantha Chandrakasan, and Hari Balakrishnan. "Energyefficient communication protocol for wireless microsensor networks." System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on. IEEE, 2000. [2]Raghavendra, Cauligi S. "PEGASIS: Power-Efficient Gathering in Sensor Information Systems Stephanie Lindsey." work 310: 336-1686. [3]Manjeshwar, Arati, and Dharma P. Agrawal. "APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks." ipdps. Vol. 2. 2002. [4]Liu, Xuxun. "A survey on clustering routing protocols in wireless sensor networks." Sensors 12.8 (2012): 11113-11153. [5]Akkaya, Kemal, and Mohamed Younis. "A survey on routing protocols for wireless sensor networks." Ad hoc networks 3.3 (2005): 325-349. [6]Saini, Parul, and Ajay K. Sharma. "E-DEEC-enhanced distributed energy efficient clustering scheme for heterogeneous WSN." Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on. IEEE, 2010. [7]Sharma, Tripti, Brijesh Kumar, and Geetam Singh Tomar. "Performance Comparision of LEACH, SEP and DEEC Protocol in Wireless Sensor Network." Proceedings of International Journal of Advances in Computer Networks and its security (2012). [8]Abad, Mortaza Fahimi Khaton, and Mohammad All Jabraeil Jamali. "Modify LEACH algorithm for wireless sensor network." ternational Journal of Computer Science Issues 8.5 (2011): 219-224.