Energy Balanced Shortest Path Routing for Wireless Sensor Networks

Energy Balanced Shortest Path Routing for Wireless Sensor Networks

Ms. P.Krishnaveni M.E Asst. Professor, Dept of CSE

Sethu Institute of Technology, Virudhunagar District, Tamil Nadu

Ms.S.Seeni Sumaya Nasrin

M.E Final Year, Dept of CSE

Sethu Institute of Technology, Virudhunagar District, Tamil Nadu

ABSTRACT

Energy is one of the most critical resources for battery-powered WSNs. There are numerous energy- aware routing protocols have been proposed, many of them mainly concentrate on energy efficiency. Our design focuses on routing that balances the energy consumption, and forward the packet toward the sink through dense energy areas so as to protect the nodes with relatively low residual energy. We propose an energy balanced routing protocol to balance trade off between energy consumption and efficiency. The routing algorithm is not practical with energy density field since it would suffer from the serious problem of routing loops. To address this problem loop elimination mechanism is used and they are integrated with energy balanced routing and also shortest path algorithm to find the optimized path with high energy. Our experimental results show that there are significant improvements in energy balance, network lifetime, coverage ratio, and throughput as compared to the commonly used energy-efficient routing algorithm.

Keywords- wireless sensor Networks, energy efficient routing, balancing energy consumption.

1. INTRODUCTION

   ireless Sensor Networks are deployed to carry out Wvarious applications, such as Environ-mental monitoring, industrial control and disaster recovery.It is well known that energy is one of the most critical resources for battery-powered WSNs. To extend the network lifetime as long as possible, energy efficiency becomes one of the basic tenets in

   the WSN protocol design. In order to use the limited energy available at sensor nodes more efficiently, most existing routing schemes attempt to find the minimum energy path to the sink to optimize energy usage at nodes. Experiments performed as part of previous research show that nodes closer to the sink tend to deplete their energy faster than the others. This uneven energy depletion dramatically reduces the network lifetime and decreases the coverage ratio. Furthermore, results in point out that by the time the nodes one hop away from the sink exhaust their energy, there is still up to 93 percent of initial energy left at the nodes farther away. Such imbalance of energy consumption imbalance is definitely undesirable for the long-term health of the network. If the sensor nodes consume their energy more evenly, the connectivity between them and the sink can be maintained for a longer time.

   Three main reasons that can cause an imbalance in energy distribution:

   1. Topology. The topology of the initial deployment limits the number of paths along which the data packets can flow.

   2. Application. The applications themselves will determine the location and the rate at which the nodes generate data. The area generating more data and the path forwarding more packets may suffer a faster energy depletion.

   3. Routing. Most energy-efficient routing protocols always choose a static optimal path to minimize energy consumption, which readily results in energy imbalance since the energy at the nodes on the optimal path is quickly depleted

      Five possible solutions to balance energy consumption:

      1. Deployment optimization. The original node distribution is to maximize network lifetime according to the traffic pattern in applications, which can solve the problem of mismatch between topology and

      2. Application. For example, we need to deploy more nodes in the heavy-loaded areas and paths. In addition, the areas closer to the sink should be covered with higher energy density (ED), since the closer to the sink a node is, the more packets does it have to relay.

      3. Topology control. The basic idea is that, instead of transmitting at maximum power, nodes collaboratively adjust their transmission power and form a proper network topology to balance energy consumption. The investigations in [7], [8], and [9] fall into this category.

      4. Mobile sink/relay nodes. Mobile sink and relay nodes can achieve a balanced energy consumption by relieving heavily loaded areas or paths in a way dual to the optimizationdeployment .However, additional mechanisms need to be devised to support node mobility. The solutions following this paradigm can be found in [10], [11], and [12].

      5. Data aggregation. Data from different sources are aggregated by exploiting redundancy with the objective of minimizing energy consumption in transmissions. The work in [13], [14], and

         [15] explores the possibility of avoiding energy holes in data-gathering sensor networks through traffic compression and data aggregation.

      6. Energy-balanced routing. Under a designated topology, employing an energy- balanced routing protocol (EBRP) may be a feasible approach to prolong the network lifetime, yet maintaining the network connectivity. To the best of our knowledge, only little work takes energy consumption balance into account while designing routing algorithms.

2. RELATED WORK

   As mentioned, numerous literatures focus on energy efficient routing protocols whose target is to find an optimal path to minimize energy consumption in the whole WSN.[2] proposed for selection of data transmission route that is able to solve this problem. This method is based on

   learning automata. The merit of this algorithm this method has been very effective in increasing of remaining energy and it increases network lifetime . The limitation of this algorithm is it suffers from delay in delivering the data.

   [3] proposed Adaptive Fusion Steiner Tree algorithm for energy efficient data gathering. The merits involved in this algorithm is it optimize the cost for data transmission and fusion. The limitation of this algorithm is it does not provide security in transmission of data.[4] a swarm intelligence based energy balance routing scheme SEB. SEB addresses the routing problem, especially focuses on extending the lifetime of wireless sensor networks, in which sensor nodes are battery powered. Based on the assumptions in our model, SEB estimates the weights of sensor nodes dynamically. By using swarm intelligence technique, SEB chooses a neighbor node as next hop only considering its local information of neighbor nodes. Consequently, SEB can balance residual energy of sensor nodes evenly according to their weights as much as possible. Compared with the existing algorithm such as GPSR, our simulation results show that SEB is robust and achieves longer network lifetime. [5] proposed a generalized fuzzy logic based approach for energy- aware routing in wireless sensor networks. This generalized approach is soft and tunable and hence it can accommodate sensor networks comprising of different types of sensor nodes having different energy metric. It has been demonstrated the reliability and efficiency of this approach. [6] an energy efficient spanning tree (EESR) based multi- hop routing in a homogeneous network that maximizes the network lifetime. In future, we will also investigate to maximize network lifetime for heterogeneous network where sensed data are not correlated and aggregation is not possible. [7] proposed a novel mechanism to enable a better load balancing for single-source and multiple-source scenarios. It demonstrates that by using the proposed methodology, the network lifetime can be prolonged between 30 % and 40% using EFR using LA-MPR I.

   [8] a localized zone based routing scheme that combines ideas of corona based network partition and mixed routing strategy with data aggregation. The merits of this algorithm is it improves the lifetime of the network. The limitation of this

   algorithm is the nodes in corona with different distribution ratio leads to complexity.

3. BASIC ROUTING ALGORITHM

In this section, we present the basic idea underlying the proposed EBRP scheme. For better understanding, let us first introduce some definitions and terminologies.

1. Definitions

   Network partition. The nodes in a WSN may fail to operate for some reasons, when the network may split into two or more disconnected partitions. This phenomenon is called network partition which may deteriorate or even nullify the usefulness and effectiveness of the whole network. Therefore,it is crucial to avoid the network partition. In this work, we focus on balancing energy consumption to avoid the network partition caused by energy exhaustion due to excessive and unbalanced usage.

   Neighbor. All the nodes in the radio coverage disk of node i except for i itself are its neighbors, denoted by nbr(i).

   Depth. The depth of a node is the number of hops along the shortest path from the sink.

   Energy density. The energy density of a point in the network is defined as the ratio of the sum of residual energy of the nodes within the radio coverage disk to the area of the radio coverage disk.

   Fig.1. Energy Consumption Imbalance Topology

2. Motivation

   For routing protocol design in WSNs, the energy balance and energy efficiency should be two different technical goals, since they will lead to routing algorithms with different attributes. Let us use a

   simple example to demonstrate what uneven energy depletion results in and how the proposed scheme EBRP works to balance energy consumption. One small part of a wireless sensor network is illustrated in Fig. 1a. (Note that there may be many sensor nodes on the right side of the sink; also for a clear description, we manually split the visible field into four areas.). Assume an event occurs in area 1, which is far away from the sink. Most existing energy- efficient routing protocols are prone to choose the shortest path because there are only 2 hops to reach the sink and the energy consumption is minimized.

   Unfortunately, node 1 in area 2

   runs out of its energy quickly because it has to relay too many packets from area 1 and area 4 Whenever this occurs, there will be a few living nodes in area 2, thus the network connectivity is affected, and area 4 could be partitioned from the rest of the network because node 1 has exhausted its battery power. How to protect area 2? more precisely how to balance energy consumption between area 2 and the other areas? As the energy density of area 2 is as high as the other areas, EBRP would choose the same route as most energy-efficient routing algorithms. After some time, however, when the residual energy on the nodes in area 2 becomes lower than

   that on the nodes in the other areas, EBRP could route the packets from area 1 through area 3 where there are more nodes and energy before the energy on the nodes in area 2 is exhausted. Thus, area 2 is protected properly. By this way, both energy efficiency and energy balance are taken into account, thus achieving a compromise

3. Design of EBRP

   The details on the design and implementation of EBRP are described below.

   1. Control Message

      EBRP defines two types of control messages. One is the normal updated message and the other fields carry the information used by EBRP, including depth, energy density, and residual energy. Another is a special message whose type field is 01 without other payloads, and used to confirm routing loops. It is called Check-Loop-Packet (CLP).

   2. Depth

      In the beginning, the depth of all nodes are initialized to 0xff, except for the sink whose default depth is 0.

      Fig. 2. Pseudocodes of EBRP algorithm. (Function calculateEnergy- Density() calculates and returns the energy density of local node; Distance() returns the distance of the neighbor; updateRoutingTable() updates the routing table; and setLocalDepth() sets the depth of the local node).

      .

   3. Energy and Energy Density

      The EBRP needs to know the residual energy on the local node, We can log the actions that the local node has performed to estimate the consumed energy using proper battery model.

   4. Distance

      The distance between two neighbors can be easily obtained by several techniques. The distance used in EBRP may be approximate since it is enough to distinguish relatively far or near from the local node.

   5. Time to Update

      EBRP only exchanges routing messages with its direct neighbors. To keep the update pace, EBRP defines a maximum updating interval (MUI) and a least updating interval (LUI) between two successive update messages. MUI is always larger than LUI. The update messages should be delivered between a LUI and a MUI since the last one. If there

      are no messages from a neighbor during two MUIs intervals, this neighbor is considered dead, and EBRP will recalculate the depth and other values. EBRP will send an update message when any one of the following events occurs. 1. MUI timer expires. 2. Energy consumption exceeds a certain threshold.

1. LOOP DETECTION AND ELIMINATION

   When EBRP algorithm route packets to the sink node the routing loops may appear. In order to eliminate the routing loops, there is a mechanism to detect and eliminate loops.

   1. Loop Detection

      Tracing the paths along which the packets move and monitoring the events occurring in the networks, we find that the routing loops caused by EBRP.

      Fig 3 Types of Routing Loops

      There are three types of loop. They are,

      1. One-hop-loop. One-hop-loop occurs between a local node and its parent. In Fig. 3, two nodes in area 3 select each other as their parents, which is a typical one-hop-loop. This loop can be easily detected by checking the source address embedded in the header of received packets.

      2. Origin-loop. The distinct feature of this routing loop is that it must involve one or more sampling nodes. Therefore, we call it origin-loop. This loop chain itself may be one-hop or multihop. In Fig. 3, three nodes in area 4 form an origin-loop chain back- toback. This loop can be detected by checking the origin address carried in the header of packets. The origin address of a packet is ID of the node generating this packet.

      3. Queue-loop. This is a special multihop loop chain. It does not involve any sampling nodes; all nodes consisting of the loop chain are relaying nodes. In one routing loop falling into this category appears in area 1. They cannot be properly detected by checking both origin and source addresses. However, we can still identify it. Because packets cannot go out of this routing loop, the queue of the nodes in the chain will grow drastically. This phenomenon will be an obvious symptom of this loop occurring. Thus, we call it queue-loop.

   2. Loop Elimination

      Once the routing loops are confirmed, it will be straightforward to eliminate them by cutting off the loop chain. EBRP does it by cutting the links belonging to the loop chain.

2. VALIDATION

   In the simulation experiments, a simple linear energy consumption model is used. The energy consumed by sending or receiving a packet is a monotonically increasing function of the lasting time. We assume that the length of all the packets is the same, thus the energy consumed by sending or receiving a packet is a constant value. Since sending a packet always needs more energy than receiving ones. To evaluate the performance of the routing protool.separately, it is feasible to orthogonalize the network layer and the MAC layer.

   1. Performance Metrics

      To make a comprehensive performance evaluation, we first define several measurable metrics.

      1. Energy Imbalance Factor (EIF). We define this metric to quantify the energy balance characteristic of the routing protocol

      2. Portion of Active Nodes (PAN) and Packets Delivery Ratio (PDR). We can use PAN a metric to evaluate the influence of energy consumption on the performance.

      3. Network lifetime. The network lifetime of a sensor network is defined as the time when the first energy exhausted node (First Dead Node,

         FDN) appears. The network lifetime is

         closely related to the network partition and network coverage ratio. If nodes begin to die, the probability of network partition increases.

      4. Functional lifetime. The functional lifetime of a task is defined as the amount of time that the task is perfectly carried out.

      5. Functional Throughput (FT). Functional throughput is defined as the number of packets received by the sink during the functional lifetime.

      6. Energy Consumption per Received Packet (ECRP).The average consumed energy per packet received by the sink during the network lifetime or the functional lifetime reflects the energy efficiency of the protocol.

3. INTEGRATED PERFOMANCE EVALUTION

   1. Simulation setup

      We conduct the simulation experiments using a 17 x 17 grid network (totally 289 nodes, each residing on the intersection point of 17 rows and 17 columns) to validate and evaluate the performance of our EBRP and EBRP with shortest path algorithm.

   2. Simulation Results

      The Routing protocol will always choose the shortest path to send the packet but it will dissipate the energy of the nodes. The EBRP will choose another path through other areas with more energy once it finds out that the energy density in this area is lower than that in other areas nearby. Therefore, EBRP can improve the energy consumption balance across the network and prolong the network lifetime as well as the functional lifetime. The new algorithm with shortest path routing chooses the path which contains high energy density and also the optimal shortest path to reach the destination node by the way it reduces the end to end delay when compared to the old algorithms.

      Figures 4 to 7 show the performance comparision for the different metrics. We can see that the new algorithm out performs the EBRP in all metrics.

      Functional throughput. Prolonging the functional lifetime always means increasing the throughput. It is specified in Fig 6.

      Energy efficiency. The shortest path algorithmcan save more energy. The average energy consumed per received packet is presented in Fig. 7.

      PAN and PDR. Fig. 7 and Fig 5 gives the portion of living nodes along time.

      Fig 4: Comparision between proposed algorithm and existing algorithm( average end to end delay per packet )

      Fig 5: Comparision between proposed algorithm and existing algorithm( Packet Delivery Ratio )

      Fig 6: Comparision between proposed algorithm and existing algorithm( Functional throughput)

      Fig 7: Comparision between proposed algorithm and existing algorithm ( Portion of active nodes)

      Fig 7: Comparision between proposed algorithm and existing algorithm (Energy dissipated )

4. CONCLUSION

Energy is one of the most critical resources for WSNs. The uneven energy depletion often results in network partition and low coverage ratio, which deteriorate the performance.

This paper focuses on routing that balances the energy consumption. Its main contributions are: 1) Sending packets through dense energy areas 2) Classify the routing loops and devise an enhanced mechanism to detect and eliminate loops.3) Choosing the shortest path to the sink. Our simulation results show that the proposed solution EBRP makes significant improvements in energy consumption balance, network lifetime, and throughput and Delay as compared to the commonly used existing EBRP algorithm. We will continue our investigation in this challenging direction as part of our future work.

REFERENCES

1. Fengyuan Ren , Jiao zhang, Tao He EBRP:Energy Balanced Routing Protocol for Data Gathering in Wireless sensor Networks IEEE Trans. Parallel And Distributed System, vol 22, No 12, Dec 2011

2. Anfeng Liu, Zhongming zhen andxuemin,Secure and Energy efficient disjoint multi-path routing for WSNsProc. IEEE Trans. Parallel and Distributed Systems, vol. 22, no. 12, pp. 2108-2125, Dec. 2011

3. Haibo zhang and Hong shen , Energy Efficient Beaconless geographic routing for WSNs IEEE Trans. Parallel and Distributed Systems, vol. 19, no.7,pp. 995-1008, 2010

4. Haibo zhang and Hong shen, Balancing Energy Consumption to Maximize Network Lifetime in Data gathering Sensor NetworksACM Trans.Sensor Networks,vol. 5, no. 2, pp. 1-25, 2009

5. Hong Luo, Luo.J, Liu.Y, Adaptive Data fusion For Energy efficient routing in WSNs Proc.

   IEEEINFOCOM,2006

6. Elham Hajian and Kamal Jamshidi and Ali Bohlooli ,Improve Energy Efficiency Routiug in WSN by using Automata Computer Comm., vol. 29,nos. 13/14, pp. 2482-2493, 2005

7. D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks,Proc. ACM/IEEE

   MobiCom, pp. 263-270, 1999.

8. J. Evans, D. Raychaudhuri, and S. Paul, Overview of Wireless, Mobile and Sensor Networks in GENI, GENI Design Document 06-14, Wireless Working Group, http://www.geni.net/documents. html, 2006.

9. S. Olariu and I. Stojmenovi_c, Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting, Proc. IEEE INFOCOM, 2006.

10. A. Wadaa, S. Olariu, L. Wilson, K. Jones, and

M. Eltoweissy, On Training a Sensor Networks, Proc. Parallel and Distributed Processing Symp., 2003.

Authors:

Mrs.P.Krishnaveni working as an Assistant Professor in the department of Computer Science and Engineering in Sethu Institute of Technology, Virudhunagar Dist. She has attended National and International conferences.

Ms.S.Seeni Sumaya Nasrin studied her

B.E. (Computer Science and Engineering) from Sethu Institute of Technology, Kariapatti and pursuing her M.E (Computer Science and Engineering) in Sethu Institute of Technology,Virudhunagar. Her research area includes Networking. She has presented a paper in National conference.