Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks
Files
Publication or External Link
Date
Advisor
Citation
DRUM DOI
Abstract
We present the first distributed algorithms for computing connected
dominating sets (CDS) for ad hoc networks that break the linear-time
barrier. We present two algorithms which require O(Delta log^2(n))
and O(log^2(n)) running time respectively, where Delta is the
maximum node degree and 'n' is the size of the network. This is a
substantial improvement over existing implementations, all of which
require Omega(n) running time.
A basic primitive which underlies our first algorithm is Distance-2 coloring of the network. This primitive arises naturally in many applications such as broadcast scheduling and channel assignment. Minimizing the number of colors used in the coloring is very desirable for these applications, but this is known to be NP-hard. We present a fast distributed implementation of D2-coloring for ad hoc networks which is guaranteed to use at most O(1) times the number of colors required by the optimal algorithm.
Our algorithms are geared towards constructing Well Connected Dominating Sets (WCDS) which have certain powerful and useful structural properties such as low size, low stretch and low degree. In this work, we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of WCDS with other ideas to obtain the following interesting applications: * An online distributed algorithm for collision-free, low latency, low redundancy and high throughput broadcasting. * Distributed capacity preserving backbones for unicast routing and scheduling.
Throughout this work, our focus is on obtaining distributed algorithms
for ad hoc wireless networks with "provably good analytical
we also explore the rich connections between WCDS and routing in ad hoc
networks. Specifically, we combine the properties of WCDS with other
ideas to obtain the following interesting applications:
* An online distributed algorithm for collision-free, low latency,
low redundancy and high throughput broadcasting.
* Distributed capacity preserving backbones for unicast routing
and scheduling.
Throughout this work, our focus is on obtaining distributed algorithms
for ad hoc wireless networks with "provably good analytical