發(fā)布時間：2021-07-06 00:57

　　無線傳感網(wǎng)絡的覆蓋問題在組合優(yōu)化和復雜性理論中是一個非常經(jīng)典的NP-困難問題,而由它發(fā)展而來的掃描覆蓋問題在最近越來越受到大家關注,并且在實際中也是有著非常廣泛的應用背景。對于掃描覆蓋問題,是給定一系列在度量空間中的目標點,派遣移動傳感器收集目標點信息,而每個目標點4)要求在每個時間周期₄)內至少被收集到一次。本文研究限制在路上和圈上的掃描覆蓋問題。對于在路上的掃描覆蓋問題:當移動傳感器有相同的速度時,對于最小化移動傳感器個數(shù)問題,我們提出了一種貪心算法來求精確解;對于最小化掃描周期問題、總行駛距離問題、總能量消耗問題,我們都通過對應的動態(tài)規(guī)劃算法求其精確解。當移動傳感器有常數(shù)個不同的速度時,對于上述問題我們分別給出了2近似、2近似、2近似和4近似算法。當每個靜止點有一個處理時間限制并且每個移動傳感器有一個總工作時間限制時,假定靜止點的掃描周期無窮大,對于處理時間一致的情況,我們給出了線性時間的精確算法;對于處理時間不一致的情況,我們證明了它的-困難性,并且給出了有近似比保證的近似算法。對于在圈上的掃描覆蓋問題,當每個靜止點有一個處理時間限制并且每個移動傳感器有一... 

【文章來源】：浙江師范大學浙江省

【文章頁數(shù)】：49 頁

【學位級別】：碩士

【部分圖文】：

上方的圖片展示算法4.1得到的近似解和最優(yōu)解下移動傳感器的平均使用個510152025timeforoptimalsolution(s)0.050.170.512.62126.52


本文編號：3267189