Applications of Energy Aware Routing Protocols in WSN

G.Sumalatha¹ and P. Anil Kumar²

¹Assistant professor of CSE,Vignan’s Lara Institute. Of Technology. and Science, A.P.,India,

²Assistant professor of CSE, Narasaraopeta Engineering College, A.P.,India

 

Corresponding author email: sumalathagopathoti@gmail.com

DOI : http://dx.doi.org/10.13005/ojcst/901.05

ABSTRACT:

In this paper we have reviewed application of energy aware routing protocols like LEACH, LEACH-C, PEGASIS, BCDCP, ENPC-NPSO, ANPC etc In WSN sensors are randomly deployed in the sensor field which brings the coverage problem. Hence energy and coverage problem are very scarce resources for such sensor systems and has to be managed wisely in order to extend the life of the sensors and maximizing coverage for the duration of a particular mission. In past a lot of cluster based algorithm and techniques were used. In this paper we also find out all type of PSO based algorithm, their application and limitation over present techniques to overcome the problems of low energy and coverage of sensor range.

KEYWORDS: Wireless sensor networks; energy efficient clustering; LEACH; energy efficient algorithms; PSO algorithm

Copy the following to cite this article: Sumalatha G, Kumar P. A. Applications of Energy Aware Routing Protocols in WSN. Orient.J. Comp. Sci. and Technol;9(1)

Copy the following to cite this URL: Sumalatha G, Kumar P. A. Applications of Energy Aware Routing Protocols in WSN. Orient. J. Comp. Sci. and Technol;9(1). Available from: http://www.computerscijournal.org/?p=3568

Introduction

Advances in sensor technology, low-power electronics, and low-power radio frequency (RF) design have enabled the development of small, relatively inexpensive and low-power sensors, called micro sensors that can be connected via a wireless network. These wireless micro sensor networks represent a new paradigm for extracting data from the environment and enable the reliable monitoring of a variety of environments for applications that include surveillance, machine failure diagnosis, and chemical/biological detection. An important challenge in the design of these networks is that two key resources (communication bandwidth and energy) are significantly more limited than in a tethered network environment. These constraints require innovative design techniques to use the available bandwidth and energy efficiently. Energy usage is an important issue in the design of WSNs which typically depends on portable energy sources like batteries for power .WSNs is large scale networks of small embedded devices, each with sensing, computation and communication capabilities. They have been widely discussed in recent years. Micro-Electro-Mechanical System [MEMS] sensor technology has facilitated the development of smart sensors, these smart sensors nodes are small devices with limited power, processing and computation resources. Smart sensors are power constrained devices that have one or more sensors, memory unit, processor, power supply and actuator. In WSNs, sensor nodes have constrained in term of processing power, communication bandwidth, and storage space which required very efficient resource utilization. In WSNs the sensor nodes are often grouped into individual disjoint sets called a cluster, clustering is used in WSNs, as it provides network scalability, resource sharing and efficient use of constrained resources that gives network topology stability and energy saving attributes. Clustering schemes offer reduced communication overheads, and efficient resource allocations thus decreasing the overall energy consumption and reducing the interferences among sensor nodes. A large number of clusters will congest the area with small size clusters and a very small number of clusters will exhaust the cluster head with large amount of messages transmitted from cluster members.

Hierarichal Routing Protocals

Leach [Low Energy Adaptive Clustering Hierarchy]

Several protocols have been proposed in literature, with the objective of maximizing the sensor network lifetime by adopting cluster-based network architectures. One of the well known clustering protocols called LEACH [Low Energy Adaptive Clustering Hierarchy]. LEACH is a cluster-based protocol that includes distributed cluster formation in which the nodes elect themselves as cluster heads with some probability. The algorithm is run periodically and the probability of becoming a cluster head for each period is chosen to ensure that every node becomes a cluster head at least once within 1/P rounds, where P is the predetermined percentage of cluster heads. LEACH organizes its operation into rounds, where each round consists of a setup phase where clusters are formed and a steady state phase that consists of data communication process. LEACH provides significant energy savings and prolonged network lifetime over conventional multi hop routing schemes, such as the Minimum Transmission Energy (MTE) routing protocol.

Leach-c

However, LEACH does not guarantee that the desired number of cluster heads is selected and cluster heads are not evenly positioned across the network. A further improvement of this protocol known as LEACH-C. In LEACH-C, the cluster formation is done at the beginning of each round using a centralized algorithm by the base station. The base station uses the information received from each node during the setup phase to find a predetermined number of cluster heads and configures the network into clusters. The cluster groupings are then chosen to minimize the energy required for non-cluster head nodes to transmit their data to their respective cluster heads. Results in[4] have shown that the overall performance of LEACH-C is better than LEACH due to improved cluster formation by the base station. Moreover, the number of cluster heads in each round of LEACH-C is equal to the desired optimal value, whereas for LEACH the number of cluster heads varies from round to round due to the lack of global coordination among   nodes.

Power-Efficient Gathering in Sensor Information Systems [PEGASIS]

Another clustering protocol which aims to enhance the network lifetime is (PEGASIS). Power-Efficient Gathering in Sensor Information Systems (PEGASIS) uses a greedy algorithm to organize nodes into a chain, so that each node transmits and receives from only one of its neighbors. In each round, a randomly chosen node from the chain will transmit the aggregated data to the base station and reduce the number of nodes that communicate directly with the base station.

Base station Controlled Dynamic Protocol [BCDCP]

An approach called Base station Controlled Dynamic Protocol (BCDCP) is proposed which produces clusters of equal size to avoid cluster head overload and to ensure similar power dissipation of nodes.

Efficient Node Partition Clustering protocol using Niching Particle Swarm Optimization (ENPC-NPSO):

Niching is an important multimodal optimization technique. This protocol partitions the network efficiently and generates cluster heads (CHs) based on the sensor network’s state information, such as reserved energy, location of nodes, etc. The protocol accords the idea of energy efficient with application-specific data fusion to obtain good performance in terms of system lifetime, data delivery and application-perceived quality.

An Adaptive Node Partition Clustering Protocol (ANPC):

This protocol executes in period. In this protocol each partition optimally chooses the Cluster head (CH). The CH acts as local control center to transmit the data within the cluster. We use the candidate cluster head to get its member nodes information about current energy and location through a piggy backing manner.

Hybrid energy-efficient distributed clustering algorithm (HEED)

In each round, HEED selects CHs according to the residual energy of each node and nodes proximity to their neighbors. By iterations and competition, HEED ensures only one CH within a certain range, so uniform CHs distribution is achieved across the network. HEED effectively prolongs network lifetime and is suitable for situations where each node has different initial energy.

Particle Swarm Optimization [PSO]

PSO is originally attributed to Kennedy, Eberhart and Shi and was first intended for simulating social behavior, as a stylized representation of the movement of organisms in a bird flock or fish school. In computer science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. PSO optimizes a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle’s position and velocity. Each particle’s movement is influenced by its local best known position and is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

Main Theory [1]

The PSO algorithm is an evolutionary computing technique, modeled after the social behavior of a flock of birds . In the context of PSO, a swarm refers to a number of potential solutions to the optimization problem, where each potential solution is referred to as a particle. The aim of the PSO is to find the particle position that results in the best evaluation of a given fitness function. In the initialization process of PSO, each particle is given initial parameters randomly and is „flown‟ through the multi-dimensional search space. During each generation, each particle uses the information about its previous best individual position and global best position to maximize the probability of moving towards a better solution space that will result in a better fitness.

=×−1 +1 ∅1 −−1 +2 ∅2(−−1 ) …………………………………………… (1)

Table 1: List of variables used in PSO equations   Click here to View table

 

Figure 1   Click here to View figure

 

Particle Swarm Optimization Algorithm for Cluster Setup

The operation of our protocol is based on a centralized control algorithm that is implemented at the base station, which is a node with a large amount of energy supply. The proposed protocol operates in rounds, where each round begins with a setup phase at which clusters are formed. This is followed by a steady state phase in which we used a similar approach as in. At the starting of each setup phase, all nodes send information about their current energy status and locations to the base station. Based on this information, the base station computes the average energy level of all nodes. To ensure that only nodes with a sufficient energy are selected as cluster heads, the nodes with an energy level above the average are eligible to be a cluster head candidate for this round. Next, the base station runs the PSO algorithm to determine the best K cluster heads that can minimize the cost function, as defined by:

Cos =×1+(1−)×2………………… (2)

1==1,2,..,∀∈,(,,)/ , . (3)

2= ()=1 / (,)=1 ………………. (4)

where f1 is the maximum average Euclidean distance of nodes to their associated cluster heads and Cp,k is the number of nodes that belong to cluster Ck of particle p. Function f2 is the ratio of total initial energy of all nodes ni, i=1,2,…,N in the network with the total current energy of the cluster heads candidates in the current round. The constant β is a user defined constant used to weigh the contribution of each of the sub-objectives. The fitness function defined above has the objective of simultaneously minimizing the intra-cluster.

Distance between nodes and their cluster heads, as quantified by f1; and also of optimizing the energy efficiency of the network as quantified by f2. According to the cost function defined above, a small value of f1and f2 suggests compact clusters with the optimum set of nodes that have sufficient energy to perform the cluster head tasks. Fig. 1 shows the flowchart of PSO algorithm applied during the cluster setup phase. For a sensor network with N nodes and K predetermined number of clusters, the network can be clustered as follows:

Types of PSO-Clustering

A. PSO-C: Centralized-PSO

Authors proposed centralized-PSO algorithms, in which the nodes which have energy above average energy resource are elected as the cluster heads. In this authors also compare this algorithm with LEACH protocol and with LEACH-C. Simulation results show that PSO outperform to LEACH and LEACH-C in term of network life time and throughput etc. It also outperforms GA and K-means based clustering algorithms.

B. MST-PSO: Minimum Spanning Tree-PSO

Authors proposed a minimum spanning tree-PSO based clustering algorithm of the weighted graph of the WSNs. The optimized route between the nodes and its cluster heads is searched from the entire optimal tree on the basis of energy consumption. Election of cluster head is based on the energy available to nodes and Euclidean distance to its neighbor node in the optimal tree. Others have concluded that network life time does not depend on the base station location or residual energy of the node. Once the topology decided to then network life time becomes almost settled. Author’s shows two techniques for improving network life time: reduce the startup energy consumption of the transmitter and receiver, and optimized the network topology.

Distributed PSO

PSO control algorithm try to minimize radio power while ensuring connectivity of the network. In this paper author proposed an important metric for a sensor network topology that involve consideration of hidden nodes and asymmetric links. It minimizes the number of hidden nodes and asymmetric links at the expense of increasing the transmit power of a subset of the nodes may in fact increase the longevity of the sensor network. Author explores a distributed evolutionary approach to optimize this new metric. Author generates topologies with fewer hidden nodes and asymmetric links than a comparable algorithm and presents some results that indicate that his topologies deliver more data and last longer.

Niching   PSO

This algorithm locates multiple solutions. The process of finding multiple solutions is referred to as speciation. Niching algorithms model yet another natural process, where large numbers of individuals compete for the use of limited resources on physical environment. Nieces   represent one solution to the problem, while a species refers to the group of individuals. In a conventional PSO, a swarm consists of m particles flying at a certain speed in a D -dimension search space, During searching, each particle considers its personal best position and the position of best particle from its neighborhood  So each particle searches around (or towards) a region defined by its personal best position and the neighborhood best position.

Comparison of Hierarchical protocols

Comparison of various hierarchical routing protocols is given in the following table. They were compared based on cluster-head formation, energy consumption, and lifetime

Protocol	Cluster-head Formation	Energy Consumption	Life Time
LEACH	Nodes itself selects as cluster heads with some probability	High	Poor
LEACH-C	Base station itself forms pre defined number of cluster heads	High	Poor
PEGASIS	It uses greedy algorithm to organize the nodes in to chains	High	Poor
BCDCP	Clusters are of equal size to avoid cluster head overload.	High	Poor
ENPC-NPSO	cluster heads are formed on network state information	Low	High
ANPC	Each partition optimally chooses the Cluster head (CH)	Low	High
HEED	HEED chooses CHs according to the residual energy and nodes proximity	High	High

 

Conclusion

From the literature review of PSO and other cluster based algorithm we have a lot of advantages of PSO over other algorithm. Since with PSO we can add more application of other algorithm such as power gathering and least spanning tree. By these applications we can improve the efficiency of WSN and also reduce the power delay of the information and increase the range of sensor nodes.

References

1. W. R Heinzelman, A. P Chandrakasan, and H. Balakrishnan,(2000), “Energy efficient communication protocol for wireless micro sensor networks,” in Proceedings of the 33rd Hawaii International Conference on System Sciences.
2. W. B Heinzelman, A. P Chandrakasan, and H. Balakrishnan,(2002), “An application-specific protocol architecture for wireless micro sensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-70.
   CrossRef
3. J. Tillet, R. Rao, and F. Sahin,(2002) “Cluster-head identification in ad hoc sensor networks using particle swarm optimization,” IEEE International Conference on Personal Wireless Communications, pp. 201-205.
   CrossRef
4. S. Guru, S. Halgamuge and S. Fernando “Particle swarm optimizers for cluster formation in wireless sensor networks”. In IEEE International Conference on sensor, 319–324
5. N.M.A. Latiff, C.C. Tsimenidis, and B.S Sheriff (2008) “Energy-aware clustering for wireless sensor networks using particle swarm optimization”. In IEEE International Conference on mobile radio communication, 1–5.
6. X. Co, H. Zhang, J. Shi, and G.Cui “Cluster heads election analysis for multi-hop wireless sensor networks based on weighted graph and particle swarm optimization”. In IEEE fourth International Conference on computing, 7, 599–603.
   CrossRef

---

This work is licensed under a Creative Commons Attribution 4.0 International License.