路/圈上的扫描覆盖问题

发布时间：2021-07-06 00:57

　　无线传感网络的覆盖问题在组合优化和复杂性理论中是一个非常经典的NP-困难问题,而由它发展而来的扫描覆盖问题在最近越来越受到大家关注,并且在实际中也是有着非常广泛的应用背景。对于扫描覆盖问题,是给定一系列在度量空间中的目标点,派遣移动传感器收集目标点信息,而每个目标点4)要求在每个时间周期₄)内至少被收集到一次。本文研究限制在路上和圈上的扫描覆盖问题。对于在路上的扫描覆盖问题:当移动传感器有相同的速度时,对于最小化移动传感器个数问题,我们提出了一种贪心算法来求精确解;对于最小化扫描周期问题、总行驶距离问题、总能量消耗问题,我们都通过对应的动态规划算法求其精确解。当移动传感器有常数个不同的速度时,对于上述问题我们分别给出了2近似、2近似、2近似和4近似算法。当每个静止点有一个处理时间限制并且每个移动传感器有一个总工作时间限制时,假定静止点的扫描周期无穷大,对于处理时间一致的情况,我们给出了线性时间的精确算法;对于处理时间不一致的情况,我们证明了它的-困难性,并且给出了有近似比保证的近似算法。对于在圈上的扫描覆盖问题,当每个静止点有一个处理时间限制并且每个移动传感器有一... 

【文章来源】：浙江师范大学浙江省

【文章页数】：49 页

【学位级别】：硕士

【部分图文】：

上方的图片展示算法4.1得到的近似解和最优解下移动传感器的平均使用个510152025timeforoptimalsolution(s)0.050.170.512.62126.52


本文编号：3267189