Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks

Deying Li; Hai Liu; Xiaohua Jia

doi:10.1109/GLOCOM.2003.1258263

Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks

Deying Li, Hai Liu, Xiaohua Jia

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms. © 2003 IEEE

Original language	English
Title of host publication	GLOBECOM '03 - IEEE Global Telecommunications Conference
Publisher	IEEE
Pages	367-371
Volume	1
ISBN (Print)	0-7803-7974-8
DOIs	https://doi.org/10.1109/GLOCOM.2003.1258263
Publication status	Published - Dec 2003
Event	2003 IEEE Global Telecommunications Conference (GLOBECOM'03) - San Francisco, CA, United States Duration: 1 Dec 2003 → 5 Dec 2003

Conference

Conference	2003 IEEE Global Telecommunications Conference (GLOBECOM'03)
Place	United States
City	San Francisco, CA
Period	1/12/03 → 5/12/03

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Access Output

10.1109/GLOCOM.2003.1258263

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{b047f274cb9245aab8a65c72ba748632,

title = "Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks",

abstract = "In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms. {\textcopyright} 2003 IEEE",

author = "Deying Li and Hai Liu and Xiaohua Jia",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 2003 IEEE Global Telecommunications Conference (GLOBECOM'03) ; Conference date: 01-12-2003 Through 05-12-2003",

year = "2003",

month = dec,

doi = "10.1109/GLOCOM.2003.1258263",

language = "English",

isbn = "0-7803-7974-8",

volume = "1",

pages = "367--371",

booktitle = "GLOBECOM '03 - IEEE Global Telecommunications Conference",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks

AU - Li, Deying

AU - Liu, Hai

AU - Jia, Xiaohua

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2003/12

Y1 - 2003/12

N2 - In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms. © 2003 IEEE

AB - In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms. © 2003 IEEE

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0842332521&origin=recordpage

U2 - 10.1109/GLOCOM.2003.1258263

DO - 10.1109/GLOCOM.2003.1258263

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 0-7803-7974-8

VL - 1

SP - 367

EP - 371

BT - GLOBECOM '03 - IEEE Global Telecommunications Conference

PB - IEEE

T2 - 2003 IEEE Global Telecommunications Conference (GLOBECOM'03)

Y2 - 1 December 2003 through 5 December 2003

ER -

Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks

Abstract

Conference

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this