Minimum latency data aggregation in the physical interference model

作者：An Min Kyung; Lam Nhat X; Huynh Dung T^*; Nguyen Trac N

来源：Computer Communications, 2012, 35(18): 2175-2186.

DOI：10.1016/j.comcom.2012.08.015

• Data aggregation
• Inapproximability
• NP-hardness
• Signal-to-interference-noise-ratio
• Approximation algorithm

Data aggregation has been the focus of many researchers as one of the most important applications in Wireless Sensor Networks. A main issue of data aggregation is how to construct efficient schedules by which data can be aggregated without any interference. The problem of constructing minimum latency data aggregation schedules (MLAS) has been extensively studied in the literature although most of existing works use the graph-based interference model. %26lt;br%26gt;In this paper, we study the MLAS problem in the more realistic physical model known as signal-to-interference-noise-ratio (SINR). We first derive an Omega(log n) approximation lower bound for the MLAS problem in the metric SINR model. We also prove the NP-hardness of the decision version of MLAS in the geometric SINR model. This is a significant contribution as these results have not been obtained before for the SINR model. In addition, we propose two constant factor approximation algorithms whose latency is bounded by O(Delta + R) for the dual power model, where A is the maximum node degree of a network and R is the network radius. Finally we study the performance of the algorithms through simulation.

• 出版日期2012-11-1