距离限制下移动无线传感扫描覆盖问题的近似算法

发布时间：2021-09-15 22:21

　　无线传感网络中的覆盖问题一直在被探索和研究,近几年由于无人机的热潮,使得无线传感网络中的覆盖问题模型随着应用的变化也出现了相应的变化,即从要求对网络进行整体覆盖转变为要求对网络部分覆盖,从要求对网络长时覆盖转变为对网络周期性覆盖.伴随着无人机的热潮,实际应用中出现了许多移动无线传感器,相应的产生了扫描覆盖问题模型.无线传感网络中的移动无线传感器通常配有容量限制的电池设备,在下次充满电之前移动无线传感器的游走距离是有限的,基于这样的考虑本文定义了一系列距离限制下扫描覆盖问题.（1）距离限制下最少扫描覆盖问题是要找到最少数量的移动无线传感器及它们的路径规划,使得每一个静态传感器都能在每个需求时间段内至少被某一移动无线传感器访问一次,且每一个移动无线传感器在电量消耗完之前必须回到基站（假定每次充满电可游走的距离为D）.一个基站时,我们给出了一般图上的一个渐进αβ/β-2-近似算法和树状图上的2近似算法,其中α是旅行推销员问题的近似比,D/lmax,lmax是离基站最远点与基站间的距离;多个基站时,我们给出了 kγ-近似算法,其中γ是一个基站时的近似比.（2）给定移动无线传感器的数量,最小扫描... 

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

【文章页数】：49 页

【学位级别】：硕士

【部分图文】：

图３．１实线圈是利用划分哈密顿圈得到的／？－巡回．??

图３．２如何修改ＭｉｎＤＣＳＣｆ的最优解成为ＭｉｎＤＣＳＣｆ问题的可行解??区．ａＭｉｎＤ一优

图５．２来自最优ｒ－巡回中某一个的ｒ－巡回ｏｐ《ａ?＝?｛ｒ，ｐ，ｇ，ｒ｝．??


本文编号：3396917