Approximation algorithms for minimum latency data aggregation in wireless sensor networks with directional antenna

作者：Liu, Hui; Liu, Zewen; Li, Deying; Lu, Xianling; Du, Hongwei^*

来源：Theoretical Computer Science, 2013, 497: 139-153.

DOI：10.1016/j.tcs.2011.12.012

• Approximation algorithm
• Data aggregation
• Conflict-aware
• Directional antenna
• Wireless sensor network

Real-time data aggregation is one of the most important issues in wireless sensor networks. Using directional antenna to transmit data can save energy and reduce interference. In this paper, we study the minimum latency data aggregation problem with the given two directional antenna models (the steering beam and the switch beam) under protocol interference model. We propose an approximation directional data aggregation algorithm to schedule data transmissions under two directional antenna models, respectively. At last, we evaluate the proposed schedule algorithms through simulations, and simulation results show that the proposed schedule's latency is close to the depth of BFS tree, which is the lower bound of schedule latency, and the proposed schedules achieve extremely good performance.

• 出版日期2013-7-29
• 单位中国人民大学; 中国人民解放军信息工程大学; 南昌大学; 哈尔滨工业大学