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

【文章來(lái)源】：浙江師范大學(xué)浙江省

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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


本文編號(hào)：3267189