与传统的全向传感器不同,有向传感器可以切换到不同的方向,并且每个方向覆盖有限角度的感应范围.针对有向传感器网络的区域覆盖问题,研究了“最大有向区域覆盖”MDAC(maximum directional area coverage)问题,期望通过调度传感器的工作方向,最大化覆盖区域面积.首先给出了MDAC 的问题定义,使用整数线性规划描述MDAC 问题,并且证明其是NP 完全的.然后提出一种分布式贪心算法DGreedy(distributed greedy algorithm)解决MDAC 问题.在此基础上,通过计算可能的覆盖贡献比例来反映网络拓扑信息.还提出了一种增强的算法PGreedy(distributed probability-enhanced greedy algorithm)使覆盖区域更大.证明了所提算法的收敛性,并通过详细的模拟实验验证了其有效性.

Unlike the traditional omni-directional sensors that always have an omni-angle of sensing range, directional sensors may be able to switch to several directions and each direction has a limited angle of sensingrange. This paper studies a novel “area coverage by directional sensors” problem. It proposes the MaximumDirectional Area Coverage (MDAC) to maximize the covered area by scheduling the working directions of thesensors in the network. This paper proves the MDAC to be NP-complete and proposes two distributed schedulingalgorithms for the MDAC. The proposed algorithms are proved to terminate in finite time. Simulation results demonstrate the effectiveness of the two algorithms.

Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z213 (国家高技术研究发展计划(863))