Theoretical Treatment of Target Coverage in Wireless Sensor Networks

• Published in: Journal of computer science and technology 2011, Vol.26 (1), p.117-129
• Main Author: 谷雨 赵保华 计宇生 李颉
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Artificial Intelligence; Computer Science; Computer simulation; Data Structures and Information Theory; Discretization; Gaps; Heuristic; Heuristic methods; Information Systems Applications (incl.Internet); Integer programming; Linear programming; Mathematical models; Networks; Optimization; R&D; Regular Paper; Research & development; Sensors; Software Engineering; Studies; Theory of Computation; Wireless networks; Wireless sensor networks; 启发式算法; 周期模式; 大肠杆菌; 无线传感器网络; 时间离散; 求解过程; 生命周期; 覆盖率
• ISSN: 1000-9000; 1860-4749
• DOI: 10.1007/s11390-011-9419-4

The target coverage is an important yet challenging problem in wireless sensor networks, especially when both coverage and energy constraints should be taken into account. Due to its nonlinear nature, previous studies of this problem have mainly focused on heuristic algorithms; the theoretical bound remains unknown. Moreover, the most popular method used in the previous literature, i.e., discretization of continuous time, has yet to be justified. This paper fills in these gaps with two theoretical results. The first one is a formal justification for the method. We use a simple example to illustrate the procedure of transforming a solution in time domain into a corresponding solution in the pattern domain with the same network lifetime and obtain two key observations. After that, we formally prove these two observations and use them as the basis to justify the method. The second result is an algorithm that can guarantee the network lifetime to be at least （1 - ε） of the optimal network lifetime, where ε can be made arbitrarily small depending on the required precision. The algorithm is based on the column generation （CG） theory, which decomposes the original problem into two sub-problems and iteratively solves them in a way that approaches the optimal solution. Moreover, we developed several constructive approaches to further optimize the algorithm. Numerical results verify the efficiency of our CG-based algorithm.