An Overview of a Method for Increasing Performance and Energy Efficiency of Topology Aware Routing Protocol in Wireless Sensor Networks

An Overview of a Method for Increasing Performance and Energy Efficiency of Topology Aware Routing Protocol in Wireless Sensor Networks

S. G. Santhi Dr. K. Venkatachalapathy

Assistant professor Professor

Department of Computer Science & Engineering FEAT, Annamalai University

Abstract—

This paper presents a review of topology aware routing protocol for wireless sensor networks which includes the greedy forwarding method, its limitations and methods to overcome these limitations. Accurate location availability is an important criterion in any location-based routing protocol of WSN. Also energy efficiency is required for increased lifetime of a network. In this paper we propose an efficient Topology Aware Routing protocol (TAR) that efficiently encodes a network topology into a low- dimensional virtual coordinate space where hop distances between pair wise nodes are preserved. Further, we improve the routing quality by embedding a network topology based on the metric of expected transmission count (ETX). Experiments are conducted using the Network Simulator and routing success ratio is found in terms of Packet Delivery Ratio.

Keywords— Sensor Networks, Topology, Greedy forwarding, TAR protocol, ETX, Energy efficiency, Routing.

1. INTRODUCTION

   Routing in WSN has been studied vastly over many years till now. They have been characterized based on the network structure of the nodes or their protocol operation ranging from flat based routing, hierarchical routing to multipath based routing including energy aware and location based algorithms. This is due to the inherent characteristics of the sensor networks and large deployment of sensor nodes. Location based methods such as topology aware routing protocols contain greedy forwarding technique in which the node sends the packet to the neighbor that is assumed closest to the final destination. Location information, in the form of coordinates, is exchanged between the nodes. Also the location information can be derived from specific devices such as GPS or can be modeled by virtual coordinates. In this paper we will see the new protocol that works on the limitations of these previous protocols that is based on topology awareness to improve the performance of routing in WSN and also make it energy efficient. This can be an efficient, low-overhead method of data delivery if it is reasonable to assume (i) sufficient network density, (ii) accurate localization and (iii) high link reliability independent of distance within the physical radio range.

   This paper is organized as follows. In Section II, we review related works. Section III presents a methodology for Greedy Perimeter Stateless Routing. Section IV proposes the modules descriptions and concept to analyze the problem in greedy forwarding algorithm by Topology Aware Routing protocol. Section V presents the simulation results and observation ways to improve the routing quality and performance evaluation based on some metrics. In Section VI concludes this paper.

2. LITERATURE SURVEY

   Geographic routing [1] is adopted for information delivery in wireless ad-hoc and sensor networks where the location information of the nodes is available and needs to know only the location information of their direct neighbors in order to forward packets and hence the state

   stored is minimized. Further, such protocols conserve energy and bandwidth since discovery floods and state propagation is not required beyond a single hop.

   Several recent experimental studies [2] on wireless ad-hoc and sensor networks have shown that wireless links can be highly unreliable and that this must be explicitly taken into account when considering higher-layer protocols.

   The existence [3] of unreliable links exposes a key weakness in greedy forwarding that we refer to as the weakest link problem. These weak links would result in a high rate of packet drops, resulting in drastic reduction of delivery rate or increased energy wastage if retransmissions are employed.

   If the forwarding mechanism [4] attempts to maximize per-hop reliability by forwarding only to close neighbors with good links, it may cover only a small geographic distance at each hop, which would also result in greater energy expenditure due to the need for more transmission hops for each packet to reach the destination. To solve this issue a new metric is used, which is the number of expected transmissions (ETX).

   The expected transmission count metric (ETX),

   [5] which finds high-throughput paths on multi- hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path.

   To help packets get out of the stuck nodes, a distributed algorithm Bound Hole is developed, to find the boundary of the hole, i.e. a closed cycle with no self-intersections that bounds a closed region. The holes are defined as the regions of the network with boundaries consisting of all the stuck nodes. Thus, a hole is delimited by its boundary nodes.

3. METHODOLOGY

   Greedy Perimeter Stateless Routing (GPSR)

   GPSR makes greedy forwarding decisions using only information about a routers immediate neighbor in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. GPSR scales better in per-router state than shortest-path and ad-hoc routing protocols as the number of network destinations increases. To counter this problem it has been suggested that the packet should be forwarded to the node with the least backward (negative) progress if no nodes can be found in the forward direction.

   The main objective of this paper is to improve point to point performance of wireless sensor networks and to select high quality link routing path using ETX. It addresses the local minimum problem in greedy forwarding using VCS by reducing the needs of resorting in recovery schemes. It proposes a Topology Aware Routing (TAR) algorithm is proposed that guides the GF along the near-optimal paths in terms of global metrics. The topology awareness is achieved via constructing a virtual coordinate space (VCS) where the geometric distance between two arbitrary nodes reflects the actual distance in corresponding global metric space. We reduce the dimensionality of the VCS by introducing a multidimensional scaling (MDS) approach. We further embed a WSN into a Euclidean space where the geometric distance between two arbitrary nodes is proportional to the number of expected transmissions (ETX) for a packet to be successfully delivered between the two nodes. The routing path with the shortest ETX distance is the optimal one because packets can be successfully delivered with the fewest number of transmissions including retransmissions. The concept of ETX, which finds high-throughput paths for multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. TAR routing algorithm adopts the metric of ETX instead of that of minimum hop count and achieves high performance.

   The main contribution of this paper is to provide energy for sensor nodes. As the sensor nodes are battery limited nodes, sensors energy will deplete soon by performing its operation allthe time. It is necessary to preserve sensors energy in order to increase the lifetime of sensor nodes. A node will forward its packet to the next hop if the next hop is having the sufficient amount of energy to forward the data thereby providing uninterrupted data transmission. The contributed mechanism selects the node as a router that has the maximum energy and the least hop-distance. It uses the formula to select the optimum route.

   The formula is based on the hop distance and the Energy of the node.

   á = Energy of the node / Hop distance

   The node with highest alpha will be elected as a router.

4. MODULE DESCRIPTIONS

   1. Greedy Forwarding Algorithm

      In this scenario we introduce a new Virtual Coordinate System (called VCS) to support geographic routing which defines coordinates exclusively based on hop distances.

      Fig.1. Block diagram of greedy forwarding

      In Greedy forwarding, packets are marked by their originator with their destinations locations. As a result, a forwarding node can make a locally optimal, greedy choice in choosing a packets next hop. An example of greedy next hop choice appears in Fig.2. Here, x receives a packet destined for D. The Xs radio range is denoted by the dotted circle about x, and the arc with radius equal to the distance between you and D is shown as the dashed arc about D. x forwards the packet to y, as the distance between

      y and D is less than that between D and any of the xs other neighbors. This greedy forwarding process repeats, until the packet reaches D. A simple beaconing algorithm provides all nodes with their neighbors positions: periodically, each node transmits a beacon to the broadcast MAC address, containing only its own identifier (e.g., IP address) and position.

      Fig.2. Greedy Forwarding

      In the Fig.2, x selects a next hop from its neighbor (y) which is closer to the destination and forwards its data. The greedy forwarding great advantage is its reliance only on knowledge of the forwarding nodes immediate neighbors. The state required is negligible and dependent on the density of nodes in the wireless network, not the total number of destinations in the network.

   2. Local Minimum Problem

      Greedy forwarding is the process of forwarding the data through the nodes having the positive progress towards the destination and over the optimal path (least number of hops from source to destination). In addition, the route can be computed when needed, eliminating the overhead for updating the routing table. GR protocols apply the GF algorithm on node locations. A distribution of wireless sensor nodes in a square field is shown in Fig.3. When packets of node S need to be greedily forwarded to destination D, node S is unable to find a neighbor that is closer than itself to the destination D and hence the algorithm is trapped in a local minimum. As a result, packets cannot be delivered to the destination.

      Fig. 3.

      Local Minimum Problem

   3. Topology Aware Routing Protocol [TAR]

      GF can guarantee delivery and achieve the same routing performance as shortest path routing if hop distances between pair wise nodes can be precisely recovered from their local routing states. A naive approach is to maintain per-destination status in each node. The per- destination states maintained by node i in a network of size N can be viewed as a N- dimensional virtual coordinate

      xi = [xi1; xi2; . . . ; xiN ]^T ;

      Where xij is the hop distance from node i to j.

      Based on the per-destination states, the hop distance between any pair of nodes m and d can be easily obtained as xmd, which provides sufficient support for GF to follow the path of the least hops. High routing performance can be easily achieved based on the N-dimensional per- destination states. The challenge is how to achieve high routing performance based on smaller routing states. Using smaller routing states might cause the GF to converge to a local minimum, which is referred to as the local minimum problem.

      For example, instead of keeping hop distances to all nodes in a network, a node can construct its virtual coordinate based on its minimum hop counts from some selected nodes, which are called anchors. As the number of anchors increases, the VCS is expanded and a node would have a higher chance to find a neighbor that is one hop closer to the destination. Fig.5. shows that the local minimum problem cannot be completely addressed by using a small number of anchors. When packets are delivered to node M, it cannot find any neighbor that is closer than itself to destination D. Although node N has a shorter hop distance than node M, it has a longer geometric distance in the VCS. The problem of local minimum vanishes if we use all the nodes as anchors. However, the size of the virtual coordinates would be too large (i.e., N dimensional in a network of N nodes). A viable solution is to loss-lessly compress the N- dimensional per-destination states to low- dimensional routing states from which hop

      distances between pair-wise nodes can be precisely recovered

   4. Improving Routing Quality

      By Using ETX

      The end-to-end routing performance of GF is improved by embedding a WSN into a Euclidean space where two nodes geometric distance in the space is proportional to the number of expected transmissions for a packet to be successfully delivered between the two nodes. The ETX between two immediate nodes i and j is defined as

      ETX(i, j) = 1 / (1 – Pij)(1 – Pji),

      where Pij is the packet loss ratio from node i to j. Suppose two nodes x1 and xn has the routing path l comprising intermediate nodes x2, x3, . . .

      , xn-1. We have the ETX of the routing path l as ETX (l) = (i=1 to n-1) ETX (xi, xi+1):

      The routing path with the shortest ETX

      distance is the optimal one because packets can be successfully delivered with the fewest number of transmissions including retransmissions.

      In order to help greedy forwarding to find the routing path with the shortest ETX distance, each anchor initiates a flooding of a beacon message with initial ETX of zero. A multipoint relay is responsible for forwarding ETX distances calculated by itself and its one-hop neighbors. A multipoint relay thus needs to collect ETX distances of its one-hop neighbors before its broadcast. With these ETX distances to all anchors, we apply the same method introduced before to embed a network to the Euclidean space based on the ETX distances.

   5. Performance Evaluation

      The performance of the proposed protocol is compared with the existing topology based routing protocol AODV. The performance of the protocol is evaluated by conducting simulation experiments. Some of the performance evaluation metrics are described below:

      Packet Delivery Ratio:

      PDR is the proportion to the total amount of packets reached the receiver and amount of packet sent by the source. The high mobility of nodes causes PDR to decrease.

      PDR (%) = No. of packets successfully

      Delivered to destination No. of packets generated by

      Source node

      Routing Success Ratio:

      The routing success ratio, which is defined as the percentage that a packet can be delivered by the GF from the source to the destination, is used to measure the effectiveness of the routing protocol, in terms of Packet delivery ratio.

      End To End Delay:

      End-to-End delay is the time taken for a packet to reach the destination from the source node.

      End to End (Delay of each entities data packet)

      Delay (ms) =

      Total number of delivered data

      packets

      Path Length:

      Path length is the number of hops required to send the packet from source to destination.

5. SIMULATION RESUTS AND OBSERVATION

   Generated data Packets	1760
   Received data Packets	1760
   Packet Delivery Ratio	100%
   Totally Dropped Packets	0
   Routing Overhead	5950
   Forwarded Packets	134
   Average End-to-End Delay per packet	3.79595

   Generated data Packets	1760
   Received data Packets	1760
   Packet Delivery Ratio	100%
   Totally Dropped Packets	0
   Routing Overhead	5950
   Forwarded Packets	134
   Average End-to-End Delay per packet	3.79595

   TABLE 1: SHOWS PROPOSED ROUTING PROTOCOL

   Using GF there is no need to store a large-size routing table in a node and the route can be computed when needed, eliminating the overhead for updating the routing table. By dimensionality reduction a node only needs to maintain a small set of immediate neighbors low-dimensional virtual coordinates instead of maintaining a large number of routing entries. Compared with table-driven shortest path routing, the overhead is lower because hop distances to a set of selected anchors are measured instead of gathering hop distances to all nodes in the network.

   Fig 4 shows proposed routing protocol: Routing Success Ratio

   Fig 5. Comparative graph, routing success ratio

   Fig 5 shows proposed routing produces the higher routing ratio than existing greedy forwarding routing protocol.

   Fig 6. Energy Consumption of energy inefficient node

   Fig 6. shows Energy consumption of the node . Proposed protocol consumes less energy than existing greedy forwarding routing protocol.

6. CONCLUSION

   In this paper, the routing performance of the greedy forwarding technique is improved by addressing the local minimum problem incurred in geographic routing using greedy forwarding. The local minimum problem is solved by embedding a network topology to a low- dimensional Euclidean space where hop distances between pairwise nodes can be recovered from node virtual coordinates. Based on accurate hop distance comparison between neighboring nodes, the greedy forwarding can find the shortest path between two nodes. The quality of the routing is improved by embedding a network topology to a Euclidean space where the ETX can be recovered from node virtual coordinates. Guided by the ETX distance, the greedy forwarding can find the optimal path of the fewest transmissions. Proposed protocol provided better routing success ratio which is evaluated in terms of packet delivery ratio.

7. REFERENCES

1. D.S.J.D. Couto, D. Aguayo, J. Bicket, and R Morris, A High- Throughput Path Metric for Multi-Hop Wireless Routing, Proc. MobiCom, pp. 134-146, 2003.

2. A. Caruso, S. Chessa, S. De, and A. Urpi, GPS Free Coordinate Assignment and

   Routing in Wireless Sensor Networks, Proc. IEEE INFOCOM, pp. 150- 160, 2005.

3. B. Karp and H.T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proc. MobiCom, 2000.

4. F. Kuhn, R. Wattenhofer, Y. Zhang, and Zollinger, Geometric Ad-Hoc Routing: Of Theory and Practice, Proc. Ann. Symp. Principles of Distributed Computing , 2003.

5. H. Frey and I. Stojmenovic, On Delivery Guarantees of Face and Combined Greedy-Face Routing in Ad Hoc and Sensor Networks, Proc. MobiCom, pp. 390-401, 2006.

6. Q. Fang, J. Gao, And L.J. Guibas, Locating And Bypassing Holes In Sensor Networks, Mobile Networks And Applications, Vol. 11, No. 2, Pp. 187-200, 2006. 562 Ieee Transactions On Parallel And Distributed Systems, Vol. 23, No. 3, March 2012