A Probabilistic Energy Efficient Routing Protocol for Asymmetric Sensor Networks

A Probabilistic Energy Efficient Routing Protocol for Asymmetric Sensor Networks

Pooja Varma P1*, Sajan Joy2*

1*PG Scholar, Dept. of Computer Science and Engineering

2*Assistant Professor, Dept. of Computer Science and Engineering TKM Institute of Technology

Kollam, India

Abstract Wireless sensor networks have got significant applications in military surveillance, health care, weather monitoring and in various civilian applications. The fundamental problem in wireless networks is the occurrence of unidirectional links which makes most of the existing protocols fail or operate with high overhead. The main objective of our paper is to devise a new energy aware routing protocol which works well on asymmetric links as well. The proposed algorithm is a cluster based protocol which groups the nodes into different clusters. The cluster head is elected based on the remaining energy of the nodes and the delivery probability. The reverse path for unidirectional links is determined using reverse path algorithm. The performance of the network can be improved with minimized energy consumption and reduced overhead. Simulation results show that the proposed system has got high delivery probability and improved performance compared to existing system.

Index Terms Wireless sensor networks, reverse path, clustering, asymmetry, energy aware routing.

1. INTRODUCTION

   Wireless sensor network consists of low power autonomous spatially distributed sensor nodes working together to achieve an assigned task. WSNs have got tremendous applications in military surveillance, health care, industrial as well as civilian purposes. The links in wireless networks are bidirectional where two neighboring nodes use the same path for communicating back and forth. Due to various factors asymmetry can occur in wireless networks leading to the occurrence of unidirectional link.

   The main factors causing unidirectional links: environmental conditions and barriers; nodes power down in order to save energy; devices transmitting with different powers causing asymmetric links; link failures. Most of the present routing protocols are designed for bidirectional links. They assume the links to be symmetric. Some of the protocols even avoid unidirectional links in their path.

   The performance of routing protocols in asymmetric sensor networks can be measured by various metrics, such as delivery rate, throughput, latency, overhead and so on. The key and influential metric is the delivery rate in ASNs. ASNs function as the networking foundation for the notification systems that are widely used in battle- fields, financial institutions, emergency services weather, government, education, health care, sports etc. The delivery

   rate determines the effectiveness of these applications. It also affects other metrics like throughput, latency, overhead, and energy, because they are counted based on the delivered packets.

   In this paper, we focus on new routing protocol that can guarantee the desired delivery rate with a high probability using minimum energy consumption. Achieving desired delivery rate in asymmetric sensor networks poses significant challenges. Firstly, the nodes relationships are complicated: Node A can directly transmit to B, but B may not be able to transmit to A directly. Second, because of unidirectional links, it is harder to get the feedback information such as delivery probability from a neighbor. Another problem is that, the path to send the message and the path to get the acknowledgement back may not be the same.

   A clustered architecture is introduced for WSNs where every node in the network is grouped into clusters. The cluster heads (CHs) are elected based on the remaining energy of the nodes and delivery probability. The protocol works well on asymmetric links also, since reverse path protocol is used to find the reverse path for unidirectional links. As energy aware routing is done, the proposed system has got high performance guarantee compared to existing systems. The life time of the sensor networks can be improved to a great extend through this work.

2. RELATED WORKS

   Routing protocols are mainly designed for efficient operation on bidirectional networks. These protocols totally fail or operate with high overhead and low throughput when asymmetry occurs. Link-state protocols such as OLSR (Optimal Link State Routing Protocol) maintain a view of the network topology at each node; nodes broadcast their views of the topology to their neighbors and in turn update their topology views based on their neighbors state. With a complete view of the network, route finding in asymmetric networks is easy. Practical implementations maintain partial views to reduce the message complexity; the partial views may not have sufficient information to handle unidirectional links.

   The proactive distance-vector protocols such as DSDV (Destination Sequence Distance Vector routing protocol) maintain a distance vector at each node which consists of

   the length and the first hop neighbor of the shortest path to other nodes. The protocols assume that symmetric links would fail in asymmetric networks.

   head selection is based on probability of ratio of residual energy and average energy of the network.

3. PROPOSED WORK

   In contrast to the above protocol specific solutions for handling asymmetric links, the BRA (Bidirectional Routing Abstraction) protocol proposed by Ramasubramanian and Mosse [1] has the advantage of making the underlying asymmetry transparent to the above routing protocols by building reverse paths for asymmetric links. Reverse Bellman Ford algorithm is used for finding reverse path between two end nodes. But in this work, the performance guarantee of the system is not addressed.

   A general framework protocol called RP (Reverse Path) that finds reverse paths for asymmetric links [6] to overcome the difficulty caused by them, and then design routing algorithms on the reverse paths to satisfy the performance requirements. Different from the distance- vector-based reverse path protocol, RP is a source-routing- based protocol to allow easier troubleshooting and network performance management. The first routing protocol built on RP that guarantees performance requirements for ASNs is ProHet (Probabilistic-based Protocol) [4] for networks formed by heterogeneous nodes with different transmission ranges. It is a reactive algorithm suitable for large and more dynamic networks. In [6], efficient proactive routing protocols LayHet (A Layer-based Protocol) and its upgraded version EgyHet (Energy based Protocol) are implemented for less dynamic networks such as sensor networks. In its preparation part, LayHet identifies nodes' layer numbers which embed shortest path information to guide routing in the right direction. In its routing part, to guarantee performance and save more energy, LayHet only allows a message holder to broadcast enough times so that at least one selected node will receive and forward the message. To further reduce energy consumption, LayHet is upgraded to EgyHet by considering the remaining energy of nodes when selecting forwarders.

   Heinzelman[12], introduced a hierarchical clustering algorithm for sensor networks, called Low Energy Adaptive Clustering Hierarchy (LEACH) for homogeneous wireless sensors networks. LEACH protocol is a cluster- based protocol that includes distributed cluster formation. It randomly selects a few sensor nodes as cluster heads and rotates this role to evenly distribute the energy load among the sensors in the network.

   1. Younis, et.al [9] proposed HEED (Hybid Energy- Efficient Distributed clustering), which select cluster heads periodically according to the node residual energy and a node proximity to its neighbors or node degree. G. Smaragdakis, I. Matta, A. Bestavros proposed SEP (Stable Election Protocol) [11] in which every sensor node in a heterogeneous network independently elects itself as a cluster head based on its initial energy relative to that of other nodes. Li Qing [7] proposed DEEC (Distributed energy efficient Clustering) algorithm in which cluster

      1. Clustering

         Clustering technique enables the sensor network to work more efficiently. It decreases the energy consumption of the sensor network and hence the lifetime of the network is improved. The main role of cluster head (CH) is to provide data communication between sensor nodes and the base station efficiently. So the cluster head should have high energy as compared to other nodes, as it also performs data aggregation. A best node should be elected as cluster head. A new clustering algorithm is proposed for the efficient handling of sensor nodes, which enhances the existing algorithms minimizing the chances of any weak node to become cluster head.

         Cluster head will be selected as the best node where the key parameters are remaining energy level, connectivity and delivery probability of node. The above parameters are required for calculating appropriate cluster head and are assigned weight so that overall weight of node is best representation of mobile node capabilities in the cluster.

         CH nodes aggregate the data (thus decreasing the total number of relayed packets) and transmit them to the base station (BS) either directly or through the intermediate communication with other CH nodes. However, because the CH nodes send all the time data to higher distances than the common (member) nodes, they naturally require more energy at higher rates. In order to balance the energy consumption among all the network nodes, cluster heads are re-elected periodically thus rotating the CH role among all the nodes in each cluster.

         Fig 1. Clustered Architecture of wireless sensor networks

      2. Reverse Path

         In asymmetric sensor networks, neighbor relationships of sensors are grouped into four categories: (1) in-out- neighbor; (2) in-neighbor; (3) out-neighbor; and (4) non- neighbor. For two nodes A and B, as shown in Fig. 1, if A –

         >B and B -> A, then A and B are in-out-neighbors of each other. If only A -> B (or B-> A), then A (or B) is the in- neighbor of B (or A), and B (or A) is the out-neighbor of A (or B). If neither A -> B nor B -> A, they are non-neighbors

         of each other. Also note that if A and B are each others in- out-neighbors, they are each other's in-neighbor and out- neighbor.

         Fig 2. Node neighbor relationship

      3. Delivery Probability

         The delivery probability of a node Pd is defined as the ratio of the number of packets successfully delivered by the node denoted by Nd and the number of packets forwarded by it, denoted by Nf . It can be expressed as:

         Pd = Nd/Nf (1)

         Nd and Nf for a node will be recorded in the routing process so that Pd can be calculated locally and timely. After few rounds of packet delivery, every nodes delivery probability will become stable. Thus, the network history is established.

         Algorithm 1: Energy aware clustering protocol

         1. Base station collects information about the location of all the nodes in the network. The network is virtually divided into different zones depending on density and geographical area of the network

         2. Cluster head(CH) selection

            • Arrange the nodes in each zone based on decreasing order of energy

            • Select the node with the maximum remaining energy and determine the probability, Pd

            • Compare it with the threshold probability,

              Pth

            • If Pd > Pth, the node is selected as cluster head

              Else

              Select the next node in the list and repeat the steps

         3. CH will send request to join message to all the other nodes in its vicinity

         4. The nodes which receive the joining request analyses the strength of the request signal. Signal strength of the CH request depends on the distance between CH and the node. Depending on the level of the signal each node sends an acknowledgement to the most preferred CH. Each CH waits for the joining request from the nearby nodes

         5. Check for unidirectional links and find reverse path using algorithm 2

         6. The CH prepares the schedule for sending data and sends it to its nodes

         7. The CH receives data from each node, compresses the data and sends it to the BS

         The threshold probability Pth depends on the node density and the minimum delivery probability of the whole network. Its value can be determined accurately after some initial rounds of packet exchanges.

      4. Cluster Head Re-election

         As cluster head has got more functions than normal nodes such as data reception, forwarding, maintaining routing table, the energy of cluster head depletes at a faster rate. Hence re-election of cluster heads are done. New CH is selected by checking the residual energy of existing CHs. If it is below a threshold level (T), new CH is to be selected. The new head should be a node that has not become cluster head for the past (1/p)-1 rounds, where p is the (1/no:of nodes in the zone).

      5. Energy Model

         It is assumed that the energy consumption of the sensor is due to transmission and reception. The energy consumed in transmitting one message of size k bits over a transmission distance d, is given by

         ETx(k,d) = k( Eelec +amp d ) (2)

         k is the length of message

         d is the distance between transmitter and receiver Eelec is the electronic energy

         amp is the transmitter amplifier

         is the path loss component (2< <4)

         The energy consumed during message reception is given by Erx = Eelec * k (3)

         Hence, the total energy consumption of a sensor node when it receives a message and forwards it over a distance d is given by,

         Et(d) = k( 2Eelec + d) (4)

      6. Reverse Path Protocol

   The detection of unidirectional links and finding reverse path is done using the reverse path protocol. Here every nodes will broadcast hello packets. If a node A receives Bs hello message but not an acknowledgement to its own hello message then A detects the presence of unidirectional link from B to A.

   Algorithm 2: Reverse Path Protocol

   1. Initialization

      1. Every node in the network broadcasts a Hello' message

      2. If two nodes A and B receive each other's Hello message and the corresponding Ack of the Hello message, then each adds the other to its in- out-neighbor list

      3. If A receives B's Hello message, but not the Ack to its own Hello message, then A knows that B is its in-neighbor and adds it to its in- neighbor list. Then, A will perform the next step to find a reverse routing path to B

   2. Node A tries to find a reverse routing path to each of its in-neighbors by broadcasting a Find message containing the source ID (A), the destination ID and an expiration length of 3 hops

   3. If another node C receives a Find message,

      1. If it is the destination marked in the message, it will

         1. Add the source node to its out-neighbor list

         2. Send the identified reverse routing path to the source node by a Path message containing the reverse route

      2. If it is not the destination node and the expiration length is greater than 0, the message will be rebroadcasted after the following modifications:

         1. Decrement the expiration length by one

         2. Append its own ID to the message

      3. In all other cases, it will drop the message

4. PERFORMANCE ANALYSI

   This section demonstrates the efficiency of the proposed protocol, Energy Efficient Clustering Protocol (EECP), compared to the existing ones. The proposed protocol provides a better performance for wireless sensor networks by improving the network lifetime to a greater extend. This means that the proposed routing algorithm makes the network perform in an efficient manner. The parameters used for performance evaluation are the total number of nodes and the size of the message. The graph plots the residual energy of the nodes in the network to that of the time of simulation. The nodes having more residual energy would increase the network lifetime.

   We assume a power consumption of 50 nJ/bit for each receive(ER) and transmit functions(ET) and also assume a 10 KB message is sent to cluster head by each member node

   per mS. Let us also assume that energy which is used by a CH to send the data to the base station after compression is 50% of the energy spent to receive the same volume of data from its member nodes

   The energy consumption can be calculated as

   EC = (ER× Data Packet × number of member nodes) + ET

   = (ER× Data Packet × number of member nodes)

   + (ER× Data Packet × number of member nodes)/2

   The delivery rate and energy consumption of EECP is compared with LEACH. From figure 3 and 4 it is clear that the delivery rate is higher and energy consumption is less for our protocol compared with the existing LEACH protocol.

   Fig 3. Comparison on delivery rate versus number of nodes

   Fig 4. Power consumption with respect to message size

5. CONCLUSION

In this paper we designed an energy aware clustering protocol that can guarantee performance in asymmetric sensor networks where two end nodes may not use the same path to communicate with each other. A reverse path protocol is used to find reverse path between two nodes connected by a unidirectional link thereby utilizing the asymmetric link. The selection of cluster head is based on the remaining energy and the delivery probability of the nodes. Simulation results show that the proposed protocol guarantees the desired delivery rate with minimum energy consumption, thus increasing the network lifetime.

REFERENCES

1. Ramasubramanian and D. Mosse, BRA: A bidirectional routing abstraction for asymmetric mobile ad hoc networks, IEEE/ACM Trans.Netw., vol. 16, no. 1, pp. 116_129, Feb. 2008.

2. X. Chen, Z. X. Dai, W. Z. Li, and H. C. Shi, A layer-based routing protocol for heterogeneous wireless sensor networks, in Proc. IEEE ICC, Jun. 2012, pp. 228_232.

3. M. K. Marina and S. R. Das, Routing performance in the presence of unidirectional links in multi hop wireless networks, in Proc. IEEE Symp. Mobile Ad Hoc Netw. Computer, Jun. 2002, pp. 85_97.

4. X. Chen, Z. X. Dai, W. Z. Li, Y. F. Hu, J. Wu, H. C. Shi, and S. L. Lu, Prohet: A probabilistic routing protocol with assured delivery rate in wireless heterogeneous sensor networks, IEEE Trans. Wireless Commun., vol. 12, no. 4, pp. 1524_1531, Apr. 2013.

5. S. Nesargi and R. Prakash, A tunneling approach to routing with unidirectional links in mobile ad hoc networks, in Proc. 9th ICCCN, Oct. 2000, pp. 522_527.

6. X. Chen, Z. X. Dai, W. Z. Li, H. C. Shi, Performance Guaranteed Routing Protocols for Asymmetric Sensor Networks, IEEE Transactions on Emerging Topics in Computing, Vol. 1, No. 1, July 2013, p. 111-120.

7. E. Duros,W. Dabbous, H. Izumiyama, N. Fujii, and Y. Zhang, A Link Layer Tunneling Mechanism for Unidirectional Links, New York NY, USA: RFC Editor, 2001.

8. Dilip Kumar, Trilok C. Aseri, R.B.Patel, EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks, ScienceDirect, Computer Communications, Volume 32, Issue 4, 4 March 2009, Pages 662-667

9. Younis, S Fahmy, HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Transactions on Mobile Computing, 2004, Volume 3,Issue 4, Pages 366-379

10. S Bandyopadhyay, EJ Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies (Volume:3 )

11. Smaragdakis, I. Matta, A. Bestavros, SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks, in: Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004), 2004

12. W.R. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, An application specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications 1 (4) (2002) 660670

13. Manjeshwar and D. P. Agarwal, "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," In 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001

14. S. Lindsey and C. S. Raghavendra, "PEGASIS: Power Efficient GAthering in Sensor Information Systems," in the Proceedings of the IEEE Aerospace Conference, Big Sky, Montana, March 2002