An optimal algorithm for solving partial target coverage problem in wireless sensor networks
An optimal algorithm for solving partial target coverage problem in wireless sensor networks
复制标题
DOI：
10.1002/wcm.1173
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Yu Gu;Yusheng Ji;Jie Li;Bao-hua Zhao
中科院分区：
文献类型：
--
作者：
Yu Gu;Yusheng Ji;Jie Li;Bao-hua Zhao
本文研究了一种新颖的覆盖模型下无线传感器网络中的部分目标覆盖问题。以往文献中关于目标覆盖问题最常用的方法是将连续时间划分为不同长度的离散时隙，每个时隙由一个传感器子集主导，同时将所有其他传感器设置为睡眠状态以节省能量。然而，该方法存在计算复杂度高和没有性能限制等缺点。我们证明了部分目标覆盖问题可以在多项式时间内得到最优解决。首先，我们构建了一个线性规划公式，该公式考虑了传感器覆盖目标所花费的总时间，以获得寿命上限。根据先前公式中得出的信息，我们开发了一种传感器分配算法，以寻求满足寿命上限的最佳调度。提供了最优性的正式证明。我们将所提出的算法与著名的列生成算法进行了比较，结果表明所提出的算法在计算时间方面显着提高了性能。我们进行了实验来研究不同网络参数对网络寿命的影响，其结果使我们得出了一些有趣的见解。版权所有 © 2011 约翰·威利父子有限公司
This paper deals with the partial target coverage problem in wireless sensor networks under a novel coverage model. The most commonly used method in previous literature on the target coverage problem is to divide continuous time into discrete slots of different lengths, each of which is dominated by a subset of sensors while setting all the other sensors into the sleep state to save energy. This method, however, suffers from shortcomings such as high computational complexity and no performance bound. We showed that the partial target coverage problem can be optimally solved in polynomial time. First, we built a linear programming formulation, which considers the total time that a sensor spends on covering targets, in order to obtain a lifetime upper bound. Based on the information derived in previous formulation, we developed a sensor assignment algorithm to seek an optimal schedule meeting the lifetime upper bound. A formal proof of optimality was provided. We compared the proposed algorithm with the well-known column generation algorithm and showed that the proposed algorithm significantly improves performance in terms of computational time. Experiments were conducted to study the impact of different network parameters on the network lifetime, and their results led us to several interesting insights. Copyright © 2011 John Wiley & Sons, Ltd.