Randomized Approach for Target Coverage Scheduling in Directional Sensor Network
Randomized Approach for Target Coverage Scheduling in Directional Sensor Network
复制标题
DOI：
10.1007/978-3-540-72685-2_36
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
Jian Wang;Changyong Niu;R. Shen
中科院分区：
文献类型：
--
作者：
Jian Wang;Changyong Niu;R. Shen
近年来，方向传感器由于在制造、尺寸和成本的限制下更实用而被广泛部署。由这种定向传感器形成的网络的一个常见功能是连续地监视一组离散目标。大规模部署使传感器无法充电。通过大量的部署，选择传感器子集交替工作，以延长网络的生命周期是合理和必要的。这类问题已被证明是NP完全问题。本文用随机化算法近似求解网络生存期问题。通过构造表示覆盖所有目标的传感器活动子集的基本会话和线性规划，与以前的工作相比，在极短的时间内得到近似解。仿真结果验证了算法的有效性，并给出了合理的解释。
Recently directional sensors have been widely deployed as they are more practicable under constraints of manufacture, size and cost. One common functionality of networks formed by such directional sensors is to monitor a set of discrete targets continuously. Large scale deployment makes sensor recharge impossible. By abundant deployment, it is reasonable and necessary to select subsets of sensors to operate alternatively so as to prolong the network lifetime. Such problem has been proved to be NP-Complete. This paper approximates network lifetime problem by randomized algorithm. Through constructingelementary sessions, which denotes active subset of sensors covering all targets, and linear programming, the approximating solution is derived within extremely less duration comparing to previous works. Simulation results demonstrate the algorithm’s performance and sound explanation is also presented.