Distributed algorithms for connected domination in wireless networks

Rajiv Gandhi, Srinivasan Parthasarathy

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

We present fast distributed local control connected dominating set (CDS) algorithms for wireless ad hoc networks. We present two randomized distributed algorithms, CDSColor and CDSTop which take into account the effect of wireless interference and the consequent loss of messages during the execution of the algorithm. These algorithms produce a CDS of constant size and constant stretch ratio with high probability, and converge in polylogarithmic running time. Specifically, algorithm CDSColor requires the nodes to know (estimates of) the maximum degree Δ and the size of the network n and converges in O (Δ log2 n) time. Algorithm CDSTop requires the nodes to know their three-hop topology and (an estimate of) the network size n and converges in O (log2 n) time. To the best of our knowledge, these are the first distributed interference-aware CDS algorithms for wireless ad hoc networks which break the linear running-time barrier.

Original languageEnglish (US)
Pages (from-to)848-862
Number of pages15
JournalJournal of Parallel and Distributed Computing
Volume67
Issue number7
DOIs
StatePublished - Jul 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Keywords

  • Connected dominating set
  • Distributed algorithms
  • Interference
  • Wireless networks

Fingerprint

Dive into the research topics of 'Distributed algorithms for connected domination in wireless networks'. Together they form a unique fingerprint.

Cite this