Nearly constant approximation for data aggregation scheduling in wireless sensor networks

Scott C.-H. Huang; Peng-Jun Wan; Chinh T. Vu; Yingshu Li; Frances Yao

doi:10.1109/INFCOM.2007.50

Nearly constant approximation for data aggregation scheduling in wireless sensor networks

Scott C.-H. Huang
, Peng-Jun Wan
, Chinh T. Vu
, Yingshu Li
, Frances Yao

Department of Computer Science

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

210 Citations (Scopus)

Abstract

Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Δ - 1)R, where A is the maximum degree and R is the network radius. Since both Δ and R could be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R + Δ - 18. Here Δ contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Δ is large. © 2007 IEEE

Original language	English
Title of host publication	IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
Publisher	IEEE
Pages	366-372
ISBN (Print)	978-1-4244-1046-0
DOIs	https://doi.org/10.1109/INFCOM.2007.50
Publication status	Published - 2007
Event	26th IEEE Conference on Computer Communications (INFOCOM 2007) - Anchorage Duration: 6 May 2007 → 12 May 2007

Publication series

Name	IEEE INFOCOM
ISSN (Print)	0743-166X

Conference

Conference	26th IEEE Conference on Computer Communications (INFOCOM 2007)
City	Anchorage
Period	6/05/07 → 12/05/07

Funding

This work was supported in part by the Research Grants Council of Hong Kong under Project Numbers CityU 1165/04E and CityU 122105 and by the National Science Foundation of the US under Grant Numbers 557904 and CCF-0545667

Research Keywords

MULTIHOP RADIO NETWORKS
BROADCAST PROBLEM

Access Output

10.1109/INFCOM.2007.50

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{8d5de9ccb7504fe1ac6beb265a5c4906,

title = "Nearly constant approximation for data aggregation scheduling in wireless sensor networks",

abstract = "Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Δ - 1)R, where A is the maximum degree and R is the network radius. Since both Δ and R could be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R + Δ - 18. Here Δ contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Δ is large. {\textcopyright} 2007 IEEE",

keywords = "MULTIHOP RADIO NETWORKS, BROADCAST PROBLEM",

author = "Huang, \{Scott C.-H.\} and Peng-Jun Wan and Vu, \{Chinh T.\} and Yingshu Li and Frances Yao",

year = "2007",

doi = "10.1109/INFCOM.2007.50",

language = "English",

isbn = "978-1-4244-1046-0",

series = "IEEE INFOCOM",

publisher = "IEEE",

pages = "366--372",

booktitle = "IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications",

address = "United States",

note = "26th IEEE Conference on Computer Communications (INFOCOM 2007) ; Conference date: 06-05-2007 Through 12-05-2007",

}

Huang, SC-H, Wan, P-J, Vu, CT, Li, Y & Yao, F 2007, Nearly constant approximation for data aggregation scheduling in wireless sensor networks. in IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. IEEE INFOCOM, IEEE, pp. 366-372, 26th IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, 6/05/07. https://doi.org/10.1109/INFCOM.2007.50

Nearly constant approximation for data aggregation scheduling in wireless sensor networks. / Huang, Scott C.-H.; Wan, Peng-Jun; Vu, Chinh T. et al.
IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. IEEE, 2007. p. 366-372 (IEEE INFOCOM).

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

TY - GEN

T1 - Nearly constant approximation for data aggregation scheduling in wireless sensor networks

AU - Huang, Scott C.-H.

AU - Wan, Peng-Jun

AU - Vu, Chinh T.

AU - Li, Yingshu

AU - Yao, Frances

PY - 2007

Y1 - 2007

N2 - Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Δ - 1)R, where A is the maximum degree and R is the network radius. Since both Δ and R could be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R + Δ - 18. Here Δ contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Δ is large. © 2007 IEEE

AB - Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Δ - 1)R, where A is the maximum degree and R is the network radius. Since both Δ and R could be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R + Δ - 18. Here Δ contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Δ is large. © 2007 IEEE

KW - MULTIHOP RADIO NETWORKS

KW - BROADCAST PROBLEM

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

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

U2 - 10.1109/INFCOM.2007.50

DO - 10.1109/INFCOM.2007.50

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

SN - 978-1-4244-1046-0

T3 - IEEE INFOCOM

SP - 366

EP - 372

BT - IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications

PB - IEEE

T2 - 26th IEEE Conference on Computer Communications (INFOCOM 2007)

Y2 - 6 May 2007 through 12 May 2007

ER -

Nearly constant approximation for data aggregation scheduling in wireless sensor networks

Abstract

Publication series

Conference

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this