Approximation algorithms for longest-lived directional multicast communications in WANETs

Song Guo; Oliver Yang; Victor Leung

doi:10.1145/1288107.1288133

Approximation algorithms for longest-lived directional multicast communications in WANETs

Song Guo, Oliver Yang, Victor Leung

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

13 Citations (Scopus)

Abstract

Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.

Original language	English
Title of host publication	MobiHoc'07
Subtitle of host publication	Proceedings of the Eighth ACM International Symposium on Mobile Ad Hoc Networking and Computing
Pages	190-198
Number of pages	9
DOIs	https://doi.org/10.1145/1288107.1288133
Publication status	Published - 1 Dec 2007
Externally published	Yes
Event	MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing - Montreal, QC, Canada Duration: 9 Sept 2007 → 14 Sept 2007

Conference

Conference	MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing
Country/Territory	Canada
City	Montreal, QC
Period	9/09/07 → 14/09/07

Keywords

Approximation algorithm
Directional antenna
Maximum-lifetime routing
Multicast tree
Wireless ad hoc networks

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

More information

10.1145/1288107.1288133

Cite this

@inproceedings{975676ff99784689ad9c7e9f7ff7535f,

title = "Approximation algorithms for longest-lived directional multicast communications in WANETs",

abstract = "Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.",

keywords = "Approximation algorithm, Directional antenna, Maximum-lifetime routing, Multicast tree, Wireless ad hoc networks",

author = "Song Guo and Oliver Yang and Victor Leung",

year = "2007",

month = dec,

day = "1",

doi = "10.1145/1288107.1288133",

language = "English",

isbn = "9781595936844",

pages = "190--198",

booktitle = "MobiHoc'07",

note = "MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing ; Conference date: 09-09-2007 Through 14-09-2007",

}

Guo, S, Yang, O & Leung, V 2007, Approximation algorithms for longest-lived directional multicast communications in WANETs. in MobiHoc'07: Proceedings of the Eighth ACM International Symposium on Mobile Ad Hoc Networking and Computing. pp. 190-198, MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Montreal, QC, Canada, 9/09/07. https://doi.org/10.1145/1288107.1288133

Approximation algorithms for longest-lived directional multicast communications in WANETs. / Guo, Song; Yang, Oliver; Leung, Victor.
MobiHoc'07: Proceedings of the Eighth ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2007. p. 190-198.

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

TY - GEN

T1 - Approximation algorithms for longest-lived directional multicast communications in WANETs

AU - Guo, Song

AU - Yang, Oliver

AU - Leung, Victor

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.

AB - Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.

KW - Approximation algorithm

KW - Directional antenna

KW - Maximum-lifetime routing

KW - Multicast tree

KW - Wireless ad hoc networks

UR - http://www.scopus.com/inward/record.url?scp=37849046975&partnerID=8YFLogxK

U2 - 10.1145/1288107.1288133

DO - 10.1145/1288107.1288133

M3 - Conference article published in proceeding or book

SN - 9781595936844

SP - 190

EP - 198

BT - MobiHoc'07

T2 - MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing

Y2 - 9 September 2007 through 14 September 2007

ER -

Approximation algorithms for longest-lived directional multicast communications in WANETs

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this