最小化移动传感器最大迁移距离的快速栅栏覆盖算法

摘要 栅栏覆盖是当前无线传感器网络研究的一个重要研究热点.给定一个移动传感器集合与传感器的初始位置和半径，最小化最大传感器移动距离的栅栏覆盖问题的目标是计算这些传感器的新位置，使得给定的栅栏能够被完全覆盖且传感器移动距离的最大值达到最小.对于传感器感知范围不同的情况，该问题已被证明多项式时间可解.设计了一个基于贪心策略的算法，计算了所有传感器在栅栏上可达的覆盖最左端点与最右端点，并依据这两个端点从左到右选择覆盖栅栏的传感器.本文证明该算法可在O（nlognlog(M+dmax)）时间返回最优解，其中为栅栏长度，dmax为传感器到栅栏的最大距离.最后，通过实验对比了所设计算法与已有算法的实际性能.实验表明，本文算法的解与最优解一致，并且运行时间优于已有算法