An improved distributed algorithm for connected dominating sets in wireless ad hoc networks

Hui Liu, Yi Pan, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

The idea of virtual backbone routing has been proposed for efficient routing among a set of mobile nodes in wireless ad hoc networks. Virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is a NP-hard problem. We propose a distributed, 3-phase protocol for calculating the CDS in this paper. Our new protocol largely reduces the number of nodes in CDS compared with Wu and Li's method, while message and time complexities of our approach remain almost the same as those of Wu and Li's method. We conduct extensive simulations and show our protocol can consistently outperform Wu and Li's method. The correctness of our protocol is proved through theoretical analysis.
Original languageEnglish
Pages (from-to)340-351
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3358
Publication statusPublished - 1 Dec 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this