Fast distributed dominating set based routing in large scale MANETs

Wassim El-Hajj, Zouheir Trabelsi, Dionysios Kountanis

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


Hierarchical routing techniques have long been known to increase network scalability by constructing a virtual backbone. Even though MANETs have no physical backbone, a virtual backbone can be constructed by finding a connected dominating set (CDS) in the network graph. Many centralized as well as distributed algorithms have been designed to find a CDS in a graph (network). Theoretically, any centralized algorithm can be implemented in a distributed fashion, with the tradeoff of higher protocol overhead. Because centralized approaches do not scale well and because distributed approaches are more practical especially in MANETs, we propose a fast distributed connected dominating set (FDDS) construction in MANETs. FDDS has message and time complexity of O(n) and O(Δ2), where n is the number of nodes in the network and Δ is the maximum node degree. According to our knowledge, FDDS achieves the best message and time complexity combinations among the previously suggested approaches. Moreover, FDDS constructs a reliable virtual backbone that takes into account (1) node's limited energy, (2) node's mobility, and (3) node's traffic pattern. Our simulation study shows that FDDS achieves a very low network stretch. Also, when the network size is large, FDDS constructs a backbone with size smaller than other well known schemes found in the literature.

Original languageEnglish
Pages (from-to)2880-2891
Number of pages12
JournalComputer Communications
Issue number14-15
Publication statusPublished - Oct 15 2007


  • Dominating set
  • Energy efficiency
  • MANETs
  • Virtual backbone

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Fast distributed dominating set based routing in large scale MANETs'. Together they form a unique fingerprint.

Cite this