Improved ALBA for Path Recovery Around Improved ALBA for Path Recovery Around

Improved ALBA for Path Recovery Around Improved ALBA for Path Recovery Around

Shwetha H M Karunavathi R. K.

M tech student(DEC),Dept. of ECE, Associate Prof., Dept. of ECE,

Bangalore Institute of Technology , Bangalore Institute of Technology ,

VTU, Bengaluru,Karnataka,India VTU, Bengaluru,Karnataka,India

AbstractThis paper presents improved ALBA, a protocol for path recovery and converge casting in wireless sensor networks. Existing ALBA protocol is unable to recover when any node in the connectivity path fails to work. Transmission of data stops when it encounters faulty node in the connectivity path. The Improved ALBA protocol provides efficient solution to this problem. It features the cross-layer integration of geographic routing with contention-based MAC for relay selection and load balancing , as well as a mechanism to detect and route around connectivity holes, provides alternate path for connecting source to destination in case of faulty node encountered within the path. It is localized, distributed and adapts efficiently to varying traffic and node deployments. Through extensive ns2-based simulations, we show that improved ALBA is an energy-efficient protocol that achieves remarkable performance in terms of packet delivery ratio, end-to-end latency and energy consumption in different scenarios, thus being more efficient compared to existing ALBA protocol.

KeywordsWireless Sensor Networks, path recovery, converge casting, cross-layer routing, connectivity holes, geographic routing, localization errors, delivery ratio, end to end latency, energy consumption.

1. INTRODUCTION

   A communication network is composed of nodes, each of which has computing power and can transmit and receive messages over communication links, wireless or cabled. The topology of the networks can vary from a simple star network to an advanced multi-hop wireless mesh network.

   A Wireless Sensor Network (WSN) consists of spatially distributed autonomous devices that co-operatively sense physical or environmental conditions, such as temperature, sound, vibration, pressure, motion, or pollutants at different locations. The sensor nodes are resource constrained in battery power, memory, communication and computational capabilities. WSNs have been used in applications such as environmental monitoring, military applications,

   critical infrastructure systems, communications, medical applications, etc (Fig 1).

   Fig 1: Applications of WSNs

   For the wireless networks, the communication requires traversal through multiple hopes. The sensor nodes perform their data collection duties unattended, and the corresponding packets are then transmitted to a data collection point (the sink) via multihop wireless routes. The packets are transmitted from source to destination through number of intermediate nodes.An important class of protocols is represented by geographic or location-based routing schemes, where a relay is greedily chosen based on the advancement it provides toward the sink. Being almost stateless, distributed and localized, geographic routing requires little computation and storage resources at the nodes and is therefore very attractive for WSN applications. Many geographic routing schemes, however, fail to fully address important design challenges, including

   1. routing around connectivity holes,

   2. resilience to localization errors, and

   3. efficient relay selection.

   Even in a fully connected topology, there may exist nodes (called dead ends) that have no neighbors that provide packet advancement towards the sink. Dead ends are, therefore, unable to forward the packets they generate or receive. These packets will never reach their destination and will eventually be discarded. In this paper, we propose an approach to the problem of routing around connectivity holes that works in any connected topology without the overhead and inaccuracies incurred by methods based on topology planarization.

   A cross-layer protocol, named ALBA for Adaptive Load-Balancing Algorithm, whose main ingredients

   (geographic routing, load balancing, contention based relay selection) are blended with a mechanism to route packets out and around connectivity ends. ALBA, results in an integrated solution for convergecasting in WSNs that, although connected, can be sparse and with connectivity holes.

   The transmission of packets from source to destination interrupts when any intermediate node in the connecting path exhibits malfunction. The existing protocol ALBA fails to execute in this case. If there is any faulty node among intermediate nodes, then the whole network fails to transmit packets which results in the failure of entire communication network. This is the disadvantage of ALBA protocol.

   The proposed Improved ALBA Protocol provides efficient solution for this problem. If there is any faulty intermediate node, then it provides alternate path for connecting source to destination. improved ALBA is an energy-efficient protocol that achieves remarkable performance in terms of packet delivery ratio, end-to-end latency and energy consumption in different scenarios, thus being more efficient compared to existing ALBA protocol.

   The paper is organized as follows: Section 2 reviews the state of the art on geographic routing and handling dead ends. Improved ALBA is described in detail in Section 3 (ALBA).Section 4 shows the results of an extensive ns2- based performance evaluation of our protocol. It includes a comparison of existing ALBA with improved ALBA protocol. Conclusions are provided in Section 5.

2. RELATED WORK

   According to its first and simplest formulation, geographic routing concerns forwarding a packet in the direction of its intended destination by providing maximum per-hop advancement [2], [3]. In dense networks, this greedy approach is quite successful, since nodes are likely to find a path toward the sink traversing a limited number of intermediate relays. Conversely, in sparse networks, packets may get stuck at dead ends, which are located along the edge of a connectivity hole, resulting in poor performance. In order to solve the problem of dead ends the basic greedy mechanism needs to be coupled with some other techniques for bypassing connectivity holes.

   Figure 2 depicts a situation where a node A has a packet to send to node D. Node S clearly is the node that provides the best advancement toward the sink. However, since S has no neighbor in the direction of D, the packet get stuck at S, and is discarded eventually . We observe that the packet could have reached its destination D if A would have sent it to B, which is on a path to D. Nodes such as S are termed dead ends.

   Fig 2 : Node S is a dead end

   A number of ideas have, therefore, been proposed to address the problem of routing around dead ends. WSN topologies are first planarized [4]. Geographic routing over planarized WSNs is then obtained by employing greedy routing as long as possible, resorting to planar routing only when required, for example, to get around connectivity holes. Heuristic rules are then defined for returning to greedy forwarding as soon as next-hop relays can be found greedily[5],[6]. Solutions based on planarization have several drawbacks. First of all, a spanner graph of the network topology needs to be built (and maintained in the presence of node dynamics), and this incurs non negligible overhead. Planar routing may then require the exploration of large spanners before being able to switch back to the more efficient greedy forwarding, thus imposing higher latencies [7]. Moreover, in ealistic settings, localization errors and nonideal signal propagation may lead to disconnected planar graphs or to topology graphs that are nonplanar. To make planarization work on real networks, a form of periodic signaling must be implemented to check that no links cross, as performed by the Cross-Link Detection Protocol (CLDP) [8]. However, this is a transmission intense solution for WSNs, which eventually affects the network performance.

   A different class of solutions for handling dead ends is based on embedding the network topology into coordinate spaces that decrease the probability of connectivity holes. This category includes algorithms using virtual coordinates [9], [10] and those that perform some sort of topology warping [11]. In the former case, the coordinates of each node are the vector of the hop distance between the node and each of a set of beacons. Greedy forwarding is typically performed over the virtual coordinates space. This decreases the occurrence of dead ends, but does not eliminate them. Topology warping schemes are based on iteratively updating the coordinates of each node based on the coordinates of its neighbors, so that greedy paths are more likely to exist. These approaches are referred to as geographic routing without location information, as they do not require accurate initial position estimates. Both methods, however, present a non-negligible probability that packets get stuck in dead ends.

   ALBA protocol [1] is the combination of geographic routing, load balancing, with a mechanism to route packets out and around dead ends. Source node is connected to the sink node through many intermediate nodes in the network. If there is any faulty intermediate node, then the network fails to transmit packets which results in the failure of connection path.

3. THE IMPROVED ADAPTIVE LOAD- BALANCING ALGORITHM

   ALBA, is a cross layer solution for converge casting in WSNs that integrates awake/asleep schedules, MAC, routing, traffic load balancing, and back-to-back packet transmissions. Nodes alternate between awake/asleep modes according to independent wake-up schedules with fixed duty cycle d. Packet forwarding is implemented by having the sender polling for availability its awake neighbors by broadcasting an RTS packet for jointly performing channel access and communicating relevant routing information (cross-layer approach). Available neighboring nodes respond with a clear-to-send (CTS) packet carrying information through which the sender can choose the best relay. Relay selection is performed by preferring neighbors offering good performance in forwarding packets. Positive geographic advancement toward the sink is used to discriminate among relays that have the same forwarding performance.

   Every prospective relay is characterized by two parameters: the queue priority index (QPI), and the geographic priority index (GPI). The QPI is calculated as follows: The requested number of packets to be transmitted in a burst (back-to-back transmissions) is NB, and the number of packets in the queue of an eligible relay is Q. The potential relay keeps a moving average M of the number of packets it was able to transmit back-to back, without errors, in the last -forwarding attempts.

   The QPI is then defined as min{[(Q+NB)/M],Nq} where Nq is the maximum allowed QPI. The QPI has been designed so that congested nodes (with a high queue occupancy Q) and bad forwarders (experiencing high packet transmission error, i.e., with a lower M) are less frequently chosen as relays. The selection of relays with low QPI, therefore, aims at decreasing latency at each hop by balancing the network load among good forwarders.

   Based on positioning information and on the knowledge of the location of the sink, each node also computes its GPI, which is the number of the geographic region of the forwarding area of the sender where a potential relay is located. The numbering of GPI regions ranges from 0 to Nr

   – 1. Numbers are assigned so that the higher the number of the region, the further from the sink are the nodes it contains, i.e., nodes in region 0 provide the maximum advancement toward the sink. An example of QPI and GPI assignment is provided in Fig. 3.

   Fig 3. Computing QPI and GPI values.

   The sender S is represented by a black circle, while crosses and white circles denote asleep and awake neighbors, respectively. Awake nodes are the only ones available at the time the RTS is broadcast. The forwarding area is colored light gray, and the GPI regions are delimited by arcs centered at the sink (not shown in the figure). In this example, the source S wants to send a burst of(NB/2) packets. Among the awake nodes, A has an empty queue, but also a bad forwarding record (M/1); hence, its

   QPI is 2. Nodes B and C have both (M/4). However, B has a smaller queue and therefore its QPI is 1, whereas that of C is 2. A sender node queries neighbors in increasing order of QPI. The sender performs channel sensing prior to packet transmission, to make collisions with ongoing handshakes unlikely. After channel sensing, the sender proceeds as depicted in Fig. 4.

   Fig 4. ALBA handshakes.

   It broadcasts a first RTS, asking eligible forwarders to compute their QPI and GPI, and inviting answers from nodes whose GPI is 1. The RTS contains all the information required by the relays to compute their QPI and GPI, namely, the location of the sender, the location of the sink, and the length of the data burst NB. Only nodes with GPI=1 are allowed to answer the first RTS with a CTS packet. If nobody answers, other RTS packets are broadcast calling for answers by nodes having an increasingly higher GPI. If a single node answers, it is immediately sent to the data packets, which it ACKs one by one. In case more nodes with the same requested GPI respond, ties are broken via the QPI. To select the node with the best QPI, a new RTS packet is broadcast calling

   for answers only from nodes whose QPI is 0, i.e., from nodes providing the highest advancement. If no nodes are found, successive RTS are broadcast calling for nodes with progressively higher QPI.

   Further ties from multiple nodes replying with the same (QPI,GPI) pair are broken by a binary splitting tree collision resolution mechanism. This relay selection process can fail in two cases: 1) If no node with any QPI is found, or 2) if the contention among nodes with the same QPI and GPI is not resolved within a maximum number of attempts NMaxAtt. Both situations cause the sender to back off. If the sender backs off more than NBoff times, the packet is discarded. Let us assume that node B is awake and that it is the only

   available relay whose GPI is 1 after the first RTS (upper part of Fig. 4; all other neighbors are asleep). Node B replies to S with a CTS and is selected as a relay. In the case when B is asleep (lower part of Fig. 4), only A, C, and D would be available. In this case, no node with GPI equal to 1 exists, so that the first RTS is not answered. Both A and C answer the second RTS, as both have the GPI equal to 2. The second phase (best QPI search) is then started, which terminates with the selection of node A, whose QPI is equal to 0.

   Once a relay is selected, a burst of data packets is sent (as many as the relay can queue, up to NB), and each packet is individually acknowledged. If the ACK for one of the packets is missing, the sender stops the transmission of the burst, rescheduling the unacknowledged packet and the following ones in the burst for a later time, after a back off period. The sender updates its expected maximum burst length M, by taking into account the number of correct packets that have been received (if errors occurred), or by optimistically assuming that a certain burst of length MB packets was received correctly, even if NB <MB (in case of no errors). MB is a tunable protocol parameter limiting the maximum number of packets that can be transmitted back to-back in a burst.

   Nodes that lost the contention overhear data transmissions, understand from th header that they have not been selected as relays, and go back to sleep. Similarly, the nodes that during a handshake realize that they will not be selected as relays go to sleep immediately.

   In Existing ALBA protocol, set of nodes are considered. Packets are transmitted from source to the destination through many intermediate nodes (Fig 5). It works well as long as intermediate nodes are awake and active.

   Fig 5:Route establishment

   The sensor nodes are resource constrained in battery power, memory, communication and computational capabilities. If any intermediate node fails during transmission, packets will be dropped(Fig 6). No transmission occurs from source to the sink.

   Fig 6 :Region with destroyed node

   Fig 7 : Path recovery

   Improved ALBA protocol overcomes this problem by choosing alternate path (Fig 7). Faulty intermediate node is left out, new active neighbor node is chosen. Now the connection path is created through new alternate node.New node is chosen among many neighbor nodes of faulty node based on ALBA.

4. PERFORMANCE EVALUATION

   Improved ALBA protocol has been implemented in the ns2 simulator. We consider networks with n nodes, where n ranges in {50,60,70,80}. The sensors are randomly and uniformly deployed in a square area of size 10*10 cm2.Nodes go to sleep and wake up modes according to independent awake-asleep schedules with a fixed duty cycle. Each packet is randomly and uniformly assigned to a source. The chosen source queues the assigned packets and transmits them as soon as possible. The packets are transmitted from source to destination through intermediate nodes. The maximum queue length per node is set to 20 packets. A newly generated packet is accepted by the source only if its buffer is not full.

   For the verification of ALBA protocol, a set of nodes are considered. Two nodes are chosen as Source and destination. Packets are transmitted from source to the destination through many intermediate nodes.

   If any intermediate node fails during the simulation, packets will be dropped at this particular point. No transmission occurs from source to the sink. Improved ALBA protocol overcomes this problem by choosing alternate path. Faulty intermediate node is left out and new active node is chosen.

   The following performance metrics are considered for evaluation and it is compared with the existing system:

   The energy consumption: defined as the average amount of energy spent by all nodes to successfully deliver a packet to the sink;

   The packet delivery ratio: defined as the fraction of packets that are successfully delivered to the sink;

   The end-to-end latency: defined as the time from packet generation to its delivery to the sink.

   The latter metric is computed only for successfully delivered packets.

   Fig 8.a Packet delivery ratio

   Fig 8.b Delay

   Fig 8.c Energy consumption

   Fig 8. Performance comparison of improved ALBA and existing ALBA in networks.

   We have verified through graphs that the improved ALBA protocol is very efficient when compared to existing ALBA protocol in the following metrics : packet delivery ratio, Delay and Energy consumption (Fig 8) .

   Improved ALBA achieves remarkable delivery ratio , latency and can greatly limit energy consumption, outperforming existing ALBA.

5. CONCLUSIONS

In this paper, we have proposed and investigated the performance of improved ALBA, a cross-layer scheme for path recovery and convergecasting in WSNs. Improved ALBA combines geographic routing, handling of dead ends, MAC, awake-asleep scheduling, back-to-back data packet transmission for achieving an energy-efficient data gathering mechanism, path recovery . To reduce end to-end latency and scale up to high traffic, improved ALBA relies on a cross-layer relay selection mechanism favoring nodes that can forward traffic more effectively and reliably, depending on traffic and link quality.The scheme designed is fully distributed, has low overhead, and makes it possible

to route packets around connectivity holes without resorting to the creation and maintenance of planar topology graphs. Results from an performance evaluation comparing improved ALBA and existing ALBA show that improved ALBA achieves remarkable delivery ratio and latency and can greatly limit energy consumption, outperforming existing ALBA considered in this study.

REFERENCES

1. Chiara Petrioli, Michele Zorzi, ALBA: Load Balancing Geographic Routing Around Connectivity Holes in Wireless Sensor Networks

   Ieee trans. 25, NO. 3, March 2014

2. H. Takagi and L. Kleinrock, Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals, IEEE Trans. Comm., vol. 32, no. 3, pp. 246-257, Mar. 1984.

3. S. Basagni, I. Chlamtac, V.R. Syrotiuk, and B.A. Woodward, A Distance Routing Effect Algorithm for Mobility (DREAM), Proc. ACM MobiCom, pp. 76-84, Oct. 1998.

4. J. Gao, L.J. Guibas, J. Hershberger, L. Zhang, and A. Zhu, Geometric Spanners for Mobile Networks, IEEE J. Selected Areas in Comm., vol. 23, no. 1, pp. 174-185, Jan. 2005.

5. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, Routing with Guaranteed Delivery in Ad Hoc Wireless Networks, ACM/ Kluwer Wireless Networks, vol. 7, no. 6, pp. 609-616, Nov. 2001.

6. L. Barrie`re, P. Fraigniaud, L. Narayanan, and J. Opatrny, Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges, J. Wireless Comm. and Mobile Computing, vol. 2, no. 3, pp. 141-153, 2001.

7. Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, On the Pitfalls of Geographic Routing, Proc. ACM Joint Workshop Foundations of Mobile Computing (DIALM-POMC 05), pp. 34-43, Sept. 2005.

8. Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, Geographic Routing Made Practical, Proc. Second Conf. Symp. Networked Systems Design and Implementation (NSDI 05), vol. 2, pp. 217- 230,May 2005.

9. 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, Mar. 2005.

10. Y. Zhao, Q. Zhang, Y. Chen, and W. Zhu, Hop ID Based Routing in Mobile Ad Hoc Networks, Proc. IEEE 13th Intl Conf. Network Protocols (ICNP 05), pp. 179-190, Nov. 2005.

11. A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, Geographic Routing without Locatio++n Information, Proc. ACM MobiCom, pp. 96-108, Sept. 2003.