無(wú)線傳感器網(wǎng)絡(luò)中目標(biāo)覆蓋的研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)作為進(jìn)化計(jì)算體系新的研究熱點(diǎn)，已經(jīng)在諸多的領(lǐng)域，如國(guó)防安全、環(huán)境監(jiān)控、農(nóng)業(yè)、以及醫(yī)療等方面，起到了巨大的推動(dòng)作用。得益于它在物理世界與數(shù)字世界之間的交互能力，無(wú)線傳感器網(wǎng)絡(luò)可以幫助人們有效的觀測(cè)目標(biāo)、收集信息，并執(zhí)行用戶制定的策略或命令。此特性標(biāo)示著在目標(biāo)監(jiān)測(cè)的應(yīng)用場(chǎng)景如森林環(huán)境監(jiān)測(cè)或者敵對(duì)區(qū)域監(jiān)控中，傳感器網(wǎng)絡(luò)有著巨大應(yīng)用前景。然而，有鑒于此類系統(tǒng)的復(fù)雜度，其核心問(wèn)題：目標(biāo)覆蓋，沒(méi)有得到很好的解決，缺乏深度的理論分析。這

2、阻礙了傳感器網(wǎng)絡(luò)在監(jiān)測(cè)系統(tǒng)中的有效應(yīng)用。為了填補(bǔ)這方面研究的空白，本文將構(gòu)建一個(gè)普適性的優(yōu)化框架，以理論上的深度研究為基礎(chǔ)，建立一系列實(shí)際有效的節(jié)能算法，從而加速傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用中的發(fā)展。具體而言，本文的研究工作包括如下內(nèi)容：
　　 (1)針對(duì)同構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中的靜止目標(biāo)覆蓋問(wèn)題，提出了兩項(xiàng)理論研究成果。第一項(xiàng)成果為：借由松弛技術(shù)，建立了基于線性優(yōu)化模型的網(wǎng)絡(luò)生命周期上界優(yōu)化方程。此成果的意義在于提供了有效的算法性能比較基

3、準(zhǔn)，為發(fā)展高效算法，建立了理論基礎(chǔ)。第二項(xiàng)成果為基于列生產(chǎn)的有效算法，克服了前人文獻(xiàn)所提貪心算法、啟發(fā)式算法沒(méi)有性能保障的缺陷。
　　 具體而言，本章首先通過(guò)對(duì)覆蓋需求的松弛，基于線性優(yōu)化模型對(duì)問(wèn)題進(jìn)行了數(shù)學(xué)建模，從而建立了多項(xiàng)式時(shí)間復(fù)雜度的生命周期上界優(yōu)化方程。這個(gè)上界的意義在與提供了算法性能比較的基準(zhǔn)。為了克服覆蓋問(wèn)題的內(nèi)在復(fù)雜度，本章提出了一個(gè)基于列生產(chǎn)的有效算法。算法的核心思想在于“分治”與“迭代”，也即，將復(fù)雜的原問(wèn)題

4、分割為相對(duì)簡(jiǎn)單的兩個(gè)關(guān)聯(lián)子問(wèn)題，通過(guò)迭代循環(huán)求解子問(wèn)題來(lái)逼近最優(yōu)值。理論的分析證實(shí)了算法的有效性，而試驗(yàn)結(jié)果進(jìn)一步證實(shí)了，相較于前人文獻(xiàn)中的啟發(fā)式算法與貪心算法，本章提出的算法在迭代次數(shù)、求解時(shí)間、算法性能上，都有了顯著的提升。
　　 更重要的，本章展示了所提理論的可擴(kuò)展性與普適性：針對(duì)不同的目標(biāo)覆蓋問(wèn)題，通過(guò)簡(jiǎn)單調(diào)節(jié)優(yōu)化框架中的細(xì)節(jié)，產(chǎn)生有針對(duì)性的有效算法。
　　 (2)針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中靜態(tài)目標(biāo)的實(shí)時(shí)覆蓋問(wèn)題，

5、設(shè)計(jì)了基于跨層優(yōu)化的數(shù)學(xué)建模，并在此基礎(chǔ)上，提出了基于列生產(chǎn)的有效算法。為了探尋不同的網(wǎng)絡(luò)參數(shù)，如節(jié)點(diǎn)個(gè)數(shù)、目標(biāo)個(gè)數(shù)、覆蓋需求、傳輸半徑、傳感半徑等，對(duì)網(wǎng)絡(luò)生命周期的影響，本章設(shè)計(jì)了大量的試驗(yàn)。試驗(yàn)的結(jié)果揭示了一系列現(xiàn)象與規(guī)律，對(duì)實(shí)際建立監(jiān)測(cè)、覆蓋系統(tǒng)有著積極的指導(dǎo)作用。
　　 具體而言，本章考慮了在異構(gòu)無(wú)線傳感器中的目標(biāo)實(shí)時(shí)覆蓋問(wèn)題，其中不同的目標(biāo)需要被運(yùn)行在不同取樣率下的不同種類的節(jié)點(diǎn)所覆蓋。優(yōu)化的目的在與延伸網(wǎng)絡(luò)的生命周期

6、，同時(shí)要保證相異的覆蓋需求，即不同的目標(biāo)可能需要不同數(shù)目的，不同種類的，運(yùn)行于不同采樣率的節(jié)點(diǎn)。由于需要同時(shí)的考慮目標(biāo)覆蓋與數(shù)據(jù)路由問(wèn)題，問(wèn)題的復(fù)雜度較高。
　　 為了克服這兩種因素帶來(lái)的復(fù)合復(fù)雜度，本章建立了一個(gè)聯(lián)合優(yōu)化模型。這個(gè)普適的優(yōu)化模型允許目標(biāo)的覆蓋需求在不同層面上的變異。不但如此，它還抽象了不同類型節(jié)點(diǎn)的數(shù)據(jù)傳輸模型。進(jìn)一步的，為了有效的求解這個(gè)覆蓋優(yōu)化模型，對(duì)基礎(chǔ)的列生產(chǎn)算法進(jìn)行了進(jìn)一步的優(yōu)化。主要的想法在與：一列

7、相對(duì)于一個(gè)可行解；在每次的迭代中尋找一個(gè)擁有當(dāng)前最優(yōu)生命周期的解，并且判斷是否為最優(yōu)解，如果不是，則繼續(xù)在最有可能獲得最優(yōu)解的非整型解空間搜尋。為了加速迭代的收斂速度，提出了一個(gè)隨機(jī)算法來(lái)尋找初始的可行解。通過(guò)大量的實(shí)驗(yàn)，系統(tǒng)的考察了對(duì)可能影響網(wǎng)絡(luò)生命周期的因素，如取樣率、傳輸能量模型、通訊半徑、傳感半徑等，實(shí)際對(duì)網(wǎng)絡(luò)的影響。并揭示了一系列有趣的現(xiàn)象與規(guī)律，對(duì)實(shí)際建立監(jiān)測(cè)、覆蓋系統(tǒng)有著積極的指導(dǎo)作用。
　　 (3)提出了無(wú)線傳感

8、器網(wǎng)絡(luò)中靜態(tài)目標(biāo)的非整型覆蓋問(wèn)題，并利用此新覆蓋模型，設(shè)計(jì)了多項(xiàng)式時(shí)間復(fù)雜度的最優(yōu)算法，填補(bǔ)了理論研究的空白。通過(guò)理論分析與試驗(yàn)驗(yàn)證，證實(shí)了該算法在計(jì)算時(shí)間復(fù)雜度、算法性能上都顯著由于前人文獻(xiàn)中的啟發(fā)式算法。為了方便將該算法應(yīng)用到實(shí)際系統(tǒng)中，本章提出了該算法的分布式版本，并詳細(xì)說(shuō)明了實(shí)際實(shí)現(xiàn)的框架及細(xì)節(jié)。
　　 具體而言，通過(guò)對(duì)實(shí)際監(jiān)控系統(tǒng)模型的抽象，本章提出了一個(gè)新的非整型覆蓋模型：目標(biāo)其實(shí)并不需要在任何時(shí)刻都被某一個(gè)或者多個(gè)

9、節(jié)點(diǎn)所覆蓋，因?yàn)檫@會(huì)導(dǎo)致網(wǎng)絡(luò)的生命周期被某些瓶頸節(jié)點(diǎn)所制約。相對(duì)的，非整型的覆蓋，如80％的時(shí)間內(nèi)都被覆蓋，就已經(jīng)可以滿足覆蓋的要求。如采用前人工作最常用的建模策略：“連續(xù)時(shí)間離散化”，求解算法的計(jì)算復(fù)雜度較高，且性能保障。因此，本章針對(duì)非整型覆蓋模型，提出了一種全新的節(jié)點(diǎn)分配算法，可以保證在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解。為了驗(yàn)證算法的性能，本章將提出的算法與被廣泛使用的列生產(chǎn)算法想比較，證實(shí)了在計(jì)算時(shí)間、算法性能等參數(shù)上，本章所提算法顯著優(yōu)

10、于列生產(chǎn)算法。
　　 (4)針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)目標(biāo)跟蹤問(wèn)題，設(shè)計(jì)了一種全新的目標(biāo)位置預(yù)測(cè)模型，并建立了相應(yīng)的雙層的通訊協(xié)議。
　　 具體而言，本章為了有效的對(duì)無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域中出現(xiàn)的運(yùn)動(dòng)目標(biāo)節(jié)點(diǎn)進(jìn)行跟蹤，提出了一種新的目標(biāo)未來(lái)未知預(yù)測(cè)模型。通過(guò)綜合目標(biāo)在當(dāng)前時(shí)刻前的信息如移動(dòng)方向、移動(dòng)速度的基礎(chǔ)上，基于二維高斯分布，預(yù)測(cè)目標(biāo)未來(lái)可能出現(xiàn)的局域。為了保證基站與傳感器節(jié)點(diǎn)之間的穩(wěn)定的、實(shí)時(shí)的數(shù)據(jù)傳輸，本章設(shè)計(jì)了相