TY - GEN

T1 - Energy efficient broadcast in multiradio multichannel wireless networks

AU - Ma, Changcun

AU - Li, Deying

AU - Du, Hongwei

AU - Ma, Huan

AU - Wang, Yuexuan

AU - Lee, Wonjun

PY - 2012

Y1 - 2012

N2 - The broadcast is a fundamental operation in computer and communication networks. We study broadcast in multiradio multichannel multi-hop wireless networks. Suppose through configuration, each node is already assigned with a transmission power level and a set of radio channels for receiving and forwarding data. Our problem is to select a forward scheme for broadcasting from a given source node and to minimize total energy consumption. This is a known NP-hard minimization problem. In this paper, we construct a polynomial-time (1.35 + ε)(1+ln(n-1))-approximation algorithm where n is the number of nodes in given network and ε is any positive constant. We also show that there is no polynomial-time (ρ ln n)-approximation for 0 < ρ < 1 unless NP ⊆ DTIME(n O(log log n)).

AB - The broadcast is a fundamental operation in computer and communication networks. We study broadcast in multiradio multichannel multi-hop wireless networks. Suppose through configuration, each node is already assigned with a transmission power level and a set of radio channels for receiving and forwarding data. Our problem is to select a forward scheme for broadcasting from a given source node and to minimize total energy consumption. This is a known NP-hard minimization problem. In this paper, we construct a polynomial-time (1.35 + ε)(1+ln(n-1))-approximation algorithm where n is the number of nodes in given network and ε is any positive constant. We also show that there is no polynomial-time (ρ ln n)-approximation for 0 < ρ < 1 unless NP ⊆ DTIME(n O(log log n)).

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

U2 - 10.1109/INFCOM.2012.6195566

DO - 10.1109/INFCOM.2012.6195566

M3 - Conference contribution

AN - SCOPUS:84861636730

SN - 9781467307758

T3 - Proceedings - IEEE INFOCOM

SP - 1907

EP - 1915

BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012

T2 - IEEE Conference on Computer Communications, INFOCOM 2012

Y2 - 25 March 2012 through 30 March 2012

ER -