Fundamental Results on Target Coverage Problem in Wireless Sensor Networks
Fundamental Results on Target Coverage Problem in Wireless Sensor Networks
复制标题
DOI：
10.1109/glocom.2009.5425300
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
Yu Gu;Yusheng Ji;Jie Li;Bao-hua Zhao
中科院分区：
文献类型：
--
作者：
Yu Gu;Yusheng Ji;Jie Li;Bao-hua Zhao
目标覆盖问题是无线传感器网络中最基本的挑战之一。由于问题的复杂性(依赖于时间的网络拓扑和覆盖约束)，以往的研究主要集中在启发式算法上，理论上的界是未知的。在本文中，我们的目标是通过提供基本结果来填补这一空白。首先，我们通过一个示例拓扑研究了一个问题在时间域中的性质，并建立了一个新的变换，在保持相同的网络寿命的情况下，将一个时间域问题与一个相应的空间域问题联系起来。基于这种变换，我们对问题进行了数学描述，并建立了一个基于列生成的算法，该算法将原始公式分解为两个子公式，并以接近最优解的方式迭代求解。我们证明了所提出的算法所能保证的网络寿命至少是最优值的(1-e)，其中e可以根据所要求的精度而任意减小。
The target coverage problem is one of the most fundamental challenges in wireless sensor networks. Due to the complexity of the problem (time-dependent network topology and coverage constraints), previous studies have mainly focused on heuristic algorithms and the theoretical bound remains unknown. In this paper, we aim to fill in this gap by providing fundamental results. First, we investigate the properties of a problem in time domain via an example topology and build a novel transformation to connect a problem in the time domain with a corresponding problem in the space domain while maintaining the same network lifetime. Based on this transformation, we mathematically formulate the problem and build a column-generation based algorithm, which decomposes the original formulation into two sub-formulations and iteratively solves them in a way that approaches the optimal solution. We prove that the network lifetime that can be guaranteed by the proposed algorithm is at least (1-e) of the optimum, where e can be made arbitrarily small depending on the required precision.