Minimum Latency Data Aggregation In The Physical Interference Model

摘要

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. In this paper, we study the MLAS problem in the more realistic physical model known as Signal-to-Interference-Noise-Ratio (SINR) where few works exist and algorithms that guarantee theoretical performances are scarce [17, 16]. We first derive an Q (log n) approximation lower bound for the MLAS problem in the metric SINR model. We also prove the NP-completeness 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 a constant factor approximation algorithm whose latency is bounded by O( Δ + R) for the dual power model, where Δ is the maximum node degree of a network and R is the network radius. Finally we study the performance of the algorithms through simulation.