Chris Karlof, Yaping Li and Joseph Polastre

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1233
March 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1233.pdf

Wireless sensor networks for environmental monitoring and distributed control will be deployed on a large scale in the near future. Due to the low per-node cost, these networks are expected to be both large and dense. However, because of the limited computation, storage, and power available to each node, conventional ad-hoc routing techniques are not feasible in this domain, and more novel routing algorithms are required. Despite the need for a simpler approach, routing in sensor networks still needs to be both robust to failures and secure against compromised and malicious nodes. We propose ARRIVE, a probabilistic algorithm that leverages the high node density and the inherent broadcast medium found in sensor networks to achieve routing robust to both link failures and patterned node failures without resorting to periodic flooding of the network. Our algorithm is based on a tree-like topology rooted at the sink of the network, and nodes use localized observed behavior of the surrounding nodes to make probabilistic decisions for forwarding packets. We have found that ARRIVE adapts to large patterned failures within a relatively short period of time at the cost of only moderate increases in overall power consumption and source-to-sink latency.

BibTeX citation:

@techreport{Karlof:CSD-03-1233,
    Author = {Karlof, Chris and Li, Yaping and Polastre, Joseph},
    Title = {ARRIVE: Algorithm for Robust Routing in Volatile Environments},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5220.html},
    Number = {UCB/CSD-03-1233},
    Abstract = {Wireless sensor networks for environmental monitoring and distributed control will be deployed on a large scale in the near future. Due to the low per-node cost, these networks are expected to be both large and dense. However, because of the limited computation, storage, and power available to each node, conventional ad-hoc routing techniques are not feasible in this domain, and more novel routing algorithms are required. Despite the need for a simpler approach, routing in sensor networks still needs to be both robust to failures and secure against compromised and malicious nodes. We propose ARRIVE, a probabilistic algorithm that leverages the high node density and the inherent broadcast medium found in sensor networks to achieve routing robust to both link failures and patterned node failures without resorting to periodic flooding of the network. Our algorithm is based on a tree-like topology rooted at the sink of the network, and nodes use localized observed behavior of the surrounding nodes to make probabilistic decisions for forwarding packets. We have found that ARRIVE adapts to large patterned failures within a relatively short period of time at the cost of only moderate increases in overall power consumption and source-to-sink latency.}
}

EndNote citation:

%0 Report
%A Karlof, Chris
%A Li, Yaping
%A Polastre, Joseph
%T ARRIVE: Algorithm for Robust Routing in Volatile Environments
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1233
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5220.html
%F Karlof:CSD-03-1233