基于网格扫描的实现目标点覆盖的确定性传感器节点部署方法

　　无线传感器网络( Wireless Sensor Networks，WSNs) 是由部署在观测环境附近的大量微型低功耗的传感器节点组成的多跳网络系统，目的是实时检测、感知和采集各种对象的信息。这些信息通过无线方式发送，并以自组织的网络方式传送到用户终端，从而实现物理世界、计算世界以及人类社会的三元世界的联通。WSN 在军事国防、环境监测、生物医疗、智能家居、危险区域的远程监控等领域得到了广泛的应用，引起了学术界和工业界的高度重视[1-2]。

　　在构建无线传感器网络过程中，网络覆盖是最基本的问题之一[3]。根据覆盖对象，覆盖可分为区域性全覆盖[4]、关键点覆盖[5]、边界覆盖[6]、栅栏覆盖[7]等，根据部署方式可分为随机部署和确定性部署[8]。在人类很难到达的地区，如战场、森林等，多使用随机部署方式; 飞机抛洒大量节点到目标区域，节点自动组网[9]。在人类容易到达的地方如农田等，手工确定性部署节点能减少传感器节点数目，降低成本[5]。

　　近年来，众多学者对WSN 的覆盖问题进行了研究，取得了一定成果[10]。林祝亮等[11]在粒子进化的多粒子群算法的基础上，提出了一种无线传感器网络覆盖的优化策略，扩大了网络覆盖范围，延长了网络寿命。李明等[12]针对异构传感器网络节点的高密度部署和监测目标非均匀分布的情况，提出了一种基于模拟退火算法的成本最优化部署方法。Yan Ruoyu 等[13]通过网格扫描的再部署方法使用较少的传感器节点实现了较大的区域覆盖率。目前的覆盖技术研究多数集中在区域覆盖的随机部署[14-15]、确定性部署[16]以及目标覆盖的随机部署等方面[17]; 而针对目标覆盖的确定性部署问题却很少涉及。

　　目标覆盖的确定性部署，主要针对位置已知的离散目标点，寻找最少的传感器节点数及最佳的节点部署位置。当目标点分散或者对目标点的覆盖水平要求很高时，须在每个目标点处都放置一个感知节点，如监测目标点的温湿度[18]。但当目标点密度较大且对目标点覆盖水平要求不是很高时，一个节点可以同时覆盖多个目标点。何欣等[5]利用目标点的最多层交叠域和遗传算法，提出了一个面向目标覆盖的最优确定性部署方法; 该方法极大的降低了网络的部署成本，实现了目标覆盖的确定性部署;了网络的部署成本，实现了目标覆盖的确定性部署;但该方法也存在一些不足之处，最多层交叠域的计算复杂，而且遗传算法可能存在早熟问题。

　　本文提出了一种简单有效的基于网格扫描的目标点覆盖的确定性部署方法，首先把目标点所在区域划分为若干正方形网格，然后从中选择最合适的网格作为下一个节点的放置位置，直到覆盖所有目标点; 同时为了评价覆盖水平，本文引入了概率感知模型，更准确的表示节点对目标点的感知水平。文章第二部分详细介绍了基于网格扫描的目标点覆盖的确定性部署方法; 在第三部分，针对网格边长和概率感知模型的感知概率下限分别选取不同数值进行仿真实验，验证本文算法的有效性; 最后是论文的总结和结论。