TY - GEN
T1 - Minimum Energy-Cost Broadcast Routingeying in Ad Hoc Wireless Networks
AU - Li, Deying
AU - Liu, Hai
AU - Jia, Xiaohua
PY - 2003
Y1 - 2003
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.
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.
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
M3 - 32_Refereed conference paper (with ISBN/ISSN)
VL - 1
SP - 367
EP - 371
BT - GLOBECOM - IEEE Global Telecommunications Conference
T2 - IEEE Global Telecommunications Conference GLOBECOM'03
Y2 - 1 December 2003 through 5 December 2003
ER -