Extended multipoint relays to determine connected dominating sets in MANETs

Jie Wu, Wei Lou, Fei Dai

Research output: Journal article publicationJournal articleAcademic researchpeer-review

106 Citations (Scopus)

Abstract

Multipoint relays (MPR) [18] provide a localized and optimized way of broadcasting messages in a mobile ad hoc network (MANET). Using partial 2-hop information, each node chooses a small set of forward neighbors to relay messages and this set covers the node's 2-hop neighbor set. These selected forward nodes form a connected dominating set (CDS) to ensure full coverage. Adjih et al. [1] later proposed a novel extension of MPR to construct a small CDS and it is source-independent. In this paper, we provide several extensions to generate a smaller CDS using complete 2-hop information to cover each node's 2-hop neighbor set. We extend the notion of coverage in the original MPR. We prove that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR. In addition, we show that the extended MPR has a constant global probabilistic approximation ratio, while no such ratio exists in the original MPR and its existing extensions. The effectiveness of our approach is confirmed through a simulation study.
Original languageEnglish
Pages (from-to)334-347
Number of pages14
JournalIEEE Transactions on Computers
Volume55
Issue number3
DOIs
Publication statusPublished - 1 Mar 2006

Keywords

  • Approximation ratio
  • Broadcasting
  • Connected dominating set (CDS)
  • Heuristic solutions
  • Mobile ad hoc networks (MANETS)
  • Multipoint relays (MPR)

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this