Energy efficient broadcast in multiradio multichannel wireless networks

Changcun Ma; Deying Li; Hongwei Du; Huan Ma; Yuexuan Wang; Wonjun Lee

doi:10.1109/INFCOM.2012.6195566

Energy efficient broadcast in multiradio multichannel wireless networks

Changcun Ma
, Deying Li^*
, Hongwei Du
, Huan Ma
, Yuexuan Wang
, Wonjun Lee

^*Corresponding author for this work

Tsinghua University
School of Information
Harbin Institute of Technology Shenzhen
Korea University

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

4 Scopus citations

Abstract

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)}).

Original language	English
Title of host publication	2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Pages	1907-1915
Number of pages	9
DOIs	https://doi.org/10.1109/INFCOM.2012.6195566
State	Published - 2012
Externally published	Yes
Event	IEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States Duration: 25 Mar 2012 → 30 Mar 2012

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X

Conference

Conference	IEEE Conference on Computer Communications, INFOCOM 2012
Country/Territory	United States
City	Orlando, FL
Period	25/03/12 → 30/03/12

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1109/INFCOM.2012.6195566

Cite this

@inproceedings{9c0196f362a940fcaf32ec0a873d804d,

title = "Energy efficient broadcast in multiradio multichannel wireless networks",

abstract = "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)).",

author = "Changcun Ma and Deying Li and Hongwei Du and Huan Ma and Yuexuan Wang and Wonjun Lee",

year = "2012",

doi = "10.1109/INFCOM.2012.6195566",

language = "英语",

isbn = "9781467307758",

series = "Proceedings - IEEE INFOCOM",

pages = "1907--1915",

booktitle = "2012 Proceedings IEEE INFOCOM, INFOCOM 2012",

note = "IEEE Conference on Computer Communications, INFOCOM 2012 ; Conference date: 25-03-2012 Through 30-03-2012",

}

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 - https://www.scopus.com/pages/publications/84861636730

U2 - 10.1109/INFCOM.2012.6195566

DO - 10.1109/INFCOM.2012.6195566

M3 - 会议稿件

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 -

Energy efficient broadcast in multiradio multichannel wireless networks

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this