Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks
Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks
Files
Publication or External Link
Date
2004-02-25
Authors
Parthasarathy, Srinivasan
Gandhi, Rajiv
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