Extended multipoint relays to determine connected dominating sets in MANETs

Jie Wu; Wei Lou

Extended multipoint relays to determine connected dominating sets in MANETs

Jie Wu
, Wei Lou

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

25 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 language	English
Title of host publication	2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004
Pages	621-630
Number of pages	10
Publication status	Published - 1 Dec 2004
Event	2004 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 2004 → 7 Oct 2004

Conference

Conference	2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004
Country/Territory	United States
City	Santa Clara, CA
Period	4/10/04 → 7/10/04

Keywords

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

ASJC Scopus subject areas

General Engineering

Cite this

@inproceedings{5be53b5de20d4be2ad742c95b776257c,

title = "Extended multipoint relays to determine connected dominating sets in MANETs",

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.",

keywords = "Broadcasting, Connected dominating set (CDS), Mobile ad hoc networks (MANETs), Multipoint relays",

author = "Jie Wu and Wei Lou",

year = "2004",

month = dec,

day = "1",

language = "English",

isbn = "0780387961",

pages = "621--630",

booktitle = "2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004",

note = "2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004 ; Conference date: 04-10-2004 Through 07-10-2004",

}

Wu, J & Lou, W 2004, Extended multipoint relays to determine connected dominating sets in MANETs. in 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004. pp. 621-630, 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004, Santa Clara, CA, United States, 4/10/04.

Extended multipoint relays to determine connected dominating sets in MANETs. / Wu, Jie; Lou, Wei.
2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004. 2004. p. 621-630.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Extended multipoint relays to determine connected dominating sets in MANETs

AU - Wu, Jie

AU - Lou, Wei

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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.

AB - 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.

KW - Broadcasting

KW - Connected dominating set (CDS)

KW - Mobile ad hoc networks (MANETs)

KW - Multipoint relays

UR - https://www.scopus.com/pages/publications/20344387830

M3 - Conference article published in proceeding or book

SN - 0780387961

SP - 621

EP - 630

BT - 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004

T2 - 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004

Y2 - 4 October 2004 through 7 October 2004

ER -

Extended multipoint relays to determine connected dominating sets in MANETs

Abstract

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this