Near optimal scheduling of data aggregation in wireless sensor networks

被引：38

作者：

Wang, Pei ^{[1
]}

He, Yuan ^{[2
]}

Huang, Liusheng ^{[1
]}

机构：

[1] Univ Sci & Technol China, Dept Comp Sci, Hefei, Peoples R China

[2] Hong Kong Univ Sci & Technol, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

AD HOC NETWORKS | 2013年 / 11卷 / 04期

关键词：

Wireless sensor networks; Data aggregation; Latency;

D O I：

10.1016/j.adhoc.2011.01.003

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

080201 [机械制造及其自动化];

摘要：

Due to to the large-scale ad hoc deployments and wireless interference, data aggregation is a fundamental but time consuming task in wireless sensor networks. This paper focuses on the latency of data aggregation. Previously, it has been proved that the problem of minimizing the latency of data aggregation is NP-hard [1]. Many approximate algorithms have been proposed to address this issue. Using maximum independent set and first-fit algorithms, in this study we design a scheduling algorithm, Peony-tree-based Data Aggregation (PDA), which has a latency bound of 15R + Delta - 15, where R is the network radius (measured in hops) and Delta is the maximum node degree. We theoretically analyze the performance of PDA based on different network models, and further evaluate it through extensive simulations. Both the analytical and simulation results demonstrate the advantages of PDA over the state-of-art algorithm in [2], which has a latency bound of 23R + Delta - 18. (c) 2011 Elsevier B.V. All rights reserved.

引用

页码：1287 / 1296

页数：10