Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

The Effect of Link Churn on Wireless Routing

Stephen Dawson-Haggerty, Jorge Ortiz, Xiaofan Fred Jiang and David E. Culler

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-109
August 29, 2008

http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-109.pdf

In this paper, we examine the spatiotemporal dynamics of wireless links and evaluate their effect on routing. We ran several experiments using a testbed consisting of 57 MicaZ motes, and collected data on link behavior over one entire day. We use this data to observe the overall network connectivity over time and space. We are able to examine in detail the choice of neighbors and routes using several link selection mechanisms, both statically and over time. We are able to verify the hairy-edge hypothesis, which states that the most important links for routing are the most difficult to predict. In order to do so, we develop precise definitions of important and unpredictable links. We also find it possible to remove these intermediate links from consideration and still have a very rich set of links to route over, while suffering from fewer difficult-to-predict links. Also, we explore the tradeoff between statically defining routes as opposed to a dynamic protocol. We find that while it is not possible to remove all temporal variations from the network, their impact can be significantly reduced through the use of local redundancy. Finally, we present a survey of how several existing routing protocols fit into the framework developed in the body of the paper.


BibTeX citation:

@techreport{Dawson-Haggerty:EECS-2008-109,
    Author = {Dawson-Haggerty, Stephen and Ortiz, Jorge and Jiang, Xiaofan Fred and Culler, David E.},
    Title = {The Effect of Link Churn on Wireless Routing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2008},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-109.html},
    Number = {UCB/EECS-2008-109},
    Abstract = {In this paper, we examine the spatiotemporal dynamics of
wireless links and evaluate their effect on routing. We ran
several experiments using a testbed consisting of 57 MicaZ
motes, and collected data on link behavior over one entire
day. We use this data to observe the overall network connectivity over time and space. We are able to examine in
detail the choice of neighbors and routes using several link selection mechanisms, both statically and over time.

We are able to verify the hairy-edge hypothesis, which
states that the most important links for routing are the most difficult to predict. In order to do so, we develop precise definitions of important and unpredictable links. We also find it possible to remove these intermediate links from consideration and still have a very rich set of links to route over, while suffering from fewer difficult-to-predict links. Also, we explore the tradeoff between statically defining routes as opposed to a dynamic protocol. We find that while it is not possible to remove all temporal variations from the network, their impact can be significantly reduced through the use of local redundancy. Finally, we present a survey of how several existing routing protocols fit into the framework developed in the body of the paper.}
}

EndNote citation:

%0 Report
%A Dawson-Haggerty, Stephen
%A Ortiz, Jorge
%A Jiang, Xiaofan Fred
%A Culler, David E.
%T The Effect of Link Churn on Wireless Routing
%I EECS Department, University of California, Berkeley
%D 2008
%8 August 29
%@ UCB/EECS-2008-109
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-109.html
%F Dawson-Haggerty:EECS-2008-109