Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power

H. W. Du; Xiaohua Jia; X. D. Hu

doi:10.1109/ICCCAS.2005.1493418

Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power

H. W. Du
, Xiaohua Jia
, X. D. Hu^*

^*Corresponding author for this work

City University of Hong Kong
CAS - Institute of Applied Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. We assume that each node in the network has a set of discrete levels of transmission power and nodes are relatively static. The problem is, given a set of nodes in the Euclidean plane and a multicast request, to construct a multicast tree rooted at the source and including all destinations such that the total energy cost of the transmitting nodes in the tree is minimized. We first prove that this problem is NP-hard and unlikely has an approximation algorithm with a logarithmic performance ratio. We then propose two algorithms, one is based on the Steiner tree method and the other is based on connected dominating set method. Both algorithms have guaranteed performance ratios and outperform the existing method.

Original language	English
Title of host publication	2005 International Conference on Communications, Circuits and Systems - Proceedings
Pages	319-323
Number of pages	5
DOIs	https://doi.org/10.1109/ICCCAS.2005.1493418
State	Published - 2005
Externally published	Yes
Event	2005 International Conference on Communications, Circuits and Systems - Hong Kong, China Duration: 27 May 2005 → 30 May 2005

Publication series

Name	2005 International Conference on Communications, Circuits and Systems - Proceedings
Volume	1

Conference

Conference	2005 International Conference on Communications, Circuits and Systems
Country/Territory	China
City	Hong Kong
Period	27/05/05 → 30/05/05

Access to Document

10.1109/ICCCAS.2005.1493418

Cite this

Du, H. W., Jia, X., & Hu, X. D. (2005). Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power. In 2005 International Conference on Communications, Circuits and Systems - Proceedings (pp. 319-323). Article WC-44.O(#02_10_02) (2005 International Conference on Communications, Circuits and Systems - Proceedings; Vol. 1). https://doi.org/10.1109/ICCCAS.2005.1493418

@inproceedings{28b49bfd09dc445a9df57377909b299a,

title = "Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power",

abstract = "In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. We assume that each node in the network has a set of discrete levels of transmission power and nodes are relatively static. The problem is, given a set of nodes in the Euclidean plane and a multicast request, to construct a multicast tree rooted at the source and including all destinations such that the total energy cost of the transmitting nodes in the tree is minimized. We first prove that this problem is NP-hard and unlikely has an approximation algorithm with a logarithmic performance ratio. We then propose two algorithms, one is based on the Steiner tree method and the other is based on connected dominating set method. Both algorithms have guaranteed performance ratios and outperform the existing method.",

author = "Du, \{H. W.\} and Xiaohua Jia and Hu, \{X. D.\}",

year = "2005",

doi = "10.1109/ICCCAS.2005.1493418",

language = "英语",

isbn = "0780390156",

series = "2005 International Conference on Communications, Circuits and Systems - Proceedings",

pages = "319--323",

booktitle = "2005 International Conference on Communications, Circuits and Systems - Proceedings",

note = "2005 International Conference on Communications, Circuits and Systems ; Conference date: 27-05-2005 Through 30-05-2005",

}

Du, HW, Jia, X & Hu, XD 2005, Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power. in 2005 International Conference on Communications, Circuits and Systems - Proceedings., WC-44.O(#02_10_02), 2005 International Conference on Communications, Circuits and Systems - Proceedings, vol. 1, pp. 319-323, 2005 International Conference on Communications, Circuits and Systems, Hong Kong, China, 27/05/05. https://doi.org/10.1109/ICCCAS.2005.1493418

Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power. / Du, H. W.; Jia, Xiaohua; Hu, X. D.
2005 International Conference on Communications, Circuits and Systems - Proceedings. 2005. p. 319-323 WC-44.O(#02_10_02) (2005 International Conference on Communications, Circuits and Systems - Proceedings; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power

AU - Du, H. W.

AU - Jia, Xiaohua

AU - Hu, X. D.

PY - 2005

Y1 - 2005

N2 - In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. We assume that each node in the network has a set of discrete levels of transmission power and nodes are relatively static. The problem is, given a set of nodes in the Euclidean plane and a multicast request, to construct a multicast tree rooted at the source and including all destinations such that the total energy cost of the transmitting nodes in the tree is minimized. We first prove that this problem is NP-hard and unlikely has an approximation algorithm with a logarithmic performance ratio. We then propose two algorithms, one is based on the Steiner tree method and the other is based on connected dominating set method. Both algorithms have guaranteed performance ratios and outperform the existing method.

AB - In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. We assume that each node in the network has a set of discrete levels of transmission power and nodes are relatively static. The problem is, given a set of nodes in the Euclidean plane and a multicast request, to construct a multicast tree rooted at the source and including all destinations such that the total energy cost of the transmitting nodes in the tree is minimized. We first prove that this problem is NP-hard and unlikely has an approximation algorithm with a logarithmic performance ratio. We then propose two algorithms, one is based on the Steiner tree method and the other is based on connected dominating set method. Both algorithms have guaranteed performance ratios and outperform the existing method.

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

U2 - 10.1109/ICCCAS.2005.1493418

DO - 10.1109/ICCCAS.2005.1493418

M3 - 会议稿件

AN - SCOPUS:29844456774

SN - 0780390156

T3 - 2005 International Conference on Communications, Circuits and Systems - Proceedings

SP - 319

EP - 323

BT - 2005 International Conference on Communications, Circuits and Systems - Proceedings

T2 - 2005 International Conference on Communications, Circuits and Systems

Y2 - 27 May 2005 through 30 May 2005

ER -

Du HW, Jia X, Hu XD. Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power. In 2005 International Conference on Communications, Circuits and Systems - Proceedings. 2005. p. 319-323. WC-44.O(#02_10_02). (2005 International Conference on Communications, Circuits and Systems - Proceedings). doi: 10.1109/ICCCAS.2005.1493418

Energy efficient multicast routing in ad hoc wireless networks with discrete levels of transmission power

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this