This paper presents ALBA-R, a protocol for convergecasting in wireless sensor networks. ALBA-R features the cross-layer integration of geographic routing with contention-based MAC for relay selection and load balancing (ALBA), as well as a mechanism to detect and route around connectivity holes (Rainbow). ALBA and Rainbow (ALBA-R) together solve the problem of routing around a dead end without overhead-intensive techniques such as graph planarization and face routing. The protocol is localized and distributed, and adapts efficiently to varying traffic and node deployments.
We show that ALBA-R significantly outperforms other convergecasting protocols and solutions for dealing with connectivity holes, especially in critical traffic conditions and low-density networks. The performance of ALBA-R is also evaluated through experiments in an outdoor testbed of TinyOS motes. Our results show that ALBA-R is an energy-efficient protocol that achieves remarkable performance in terms of packet delivery ratio and end-to-end latency in different scenarios, thus being suitable for real network deployments.
Distributed sensing and seamless wireless data gathering are key ingredients of various monitoring applications implemented through the deployment of wireless sensor networks (WSNs). 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 (WSN routing or convergecasting). The majority of the research on protocol design for WSNs has focused on MAC and routing solutions. 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,
3) efficient relay selection.
Connectivity holes are inherently related to the way greedy forwarding works. Even in a fully connected topology, there may exist nodes (called dead ends) that have no neighbors that provide packet advancement toward 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. Many solutions have been proposed to alleviate the impact of dead ends. In particular, those that offer packet delivery guarantees are usually based on making the network topology graph planar, and on the use of face routing. However, planarization does not work well in the presence of localization errors and realistic radio propagation effects, as it depends on unrealistic representations of the network, such as a unit disk graph (UDG).
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. Specifically, we define 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 dead ends, the Rainbow protocol. The combination of the two protocols, called ALBA-R, results in an integrated solution for convergecasting in WSNs that, although connected, can be sparse and with connectivity holes.
The contributions we provide to WSN research with this paper include the following:
1. We enhance greedy geographic forwarding by considering congestion and packet advancement jointly when making routing decisions. The new relay selection scheme, which implements MAC and routing functions in a cross-layer fashion, achieves performance superior to existing protocols in terms of energy efficiency, packet delivery ratio (PDR), and latency.
2. The Rainbow mechanism allows ALBA-R to efficiently route packets out of and around dead ends. Rainbow is resilient to localization errors and to channel propagation impairments. It does not need the network topology to be planar, unlike previous routing protocols. It is, therefore, more general than face routing-based solutions and is able to guarantee packet delivery in realistic deployments.
3. Extensive ns2-based simulation experiments are performed that demonstrate how the unique features of ALBA-R determine its overall performance, and that show its superiority with respect to previous exemplary solutions for geographic-based and topology-based convergecasting, such as GeRaF and IRIS. We have also investigated the performance of Rainbow in sparse networks, where dead ends are likely to occur, with and without localization errors. We show that Rainbow is an effective distributed scheme for learning how to route packets around connectivity holes, achieving remarkable delivery ratio and latency performance. Our simulation results also show better performance than that of two recent proposals for routing around dead ends by Ru¨hrup and Stojmenovic.
4. The critical metrics of packet delivery ratio and endto- end (E2E) latency are further investigated through experiments in an outdoor 40-node testbed of TinyOS-based sensor nodes. Besides validating our simulation model, the obtained results confirm the effectiveness of ALBA-R in supporting long-lived and reliable wireless sensor networking in practice.
A succinct version of this paper has appeared in. The current version presents a considerably larger set of experiments and comparisons with previous solutions. Supplemental material, which can be found on the Computer Society Digital Library at 10.1109/TPDS.2013.60, provides proof of correctness of the Rainbow mechanism, further simulation experiments, and detailed results from testing the deployment of a 40-node network in a vineyard outside of Roma, Italy. Some results on ALBA resilience to localization errors have appeared in.