Extended multipoint relays to determine connected dominating sets in MANETs

Jie Wu, Wei Lou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

24 Citations (Scopus)

Abstract

MPR (multipoint relays) provides a localized and optimized way of broadcasting messages in a mobile ad hoc network (MANET). Using 2-hop neighborhood information, each node determines a small set of forward neighbors to relay messages. Selected forward nodes form a connected dominating set (CDS) to ensure full coverage. Adjih, Jacquet, and Viennot later proposed a novel localized algorithm to construct a small CDS based on the original MPR without any broadcast information. Such an approach is called source-independent or broadcast-independent. In this paper, we provide several extensions of the source-independent MPR to generate a smaller CDS using 3-hop neighborhood information to cover each node's 2-hop neighbor set. In addition, we extend the notion of coverage in the original MPR. We show that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR. The effectiveness of our approach is confirmed through a simulation study.
Original languageEnglish
Title of host publication2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004
Pages621-630
Number of pages10
Publication statusPublished - 1 Dec 2004
Event2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004 - Santa Clara, CA, United States
Duration: 4 Oct 20047 Oct 2004

Conference

Conference2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004
CountryUnited States
CitySanta Clara, CA
Period4/10/047/10/04

Keywords

  • Broadcasting
  • Connected dominating set (CDS)
  • Mobile ad hoc networks (MANETs)
  • Multipoint relays

ASJC Scopus subject areas

  • Engineering(all)

Cite this