無線傳感器網(wǎng)絡(luò)覆蓋技術(shù)

1、無線傳感器網(wǎng)絡(luò)覆蓋技術(shù)譚慧婷 150400241. 覆蓋技術(shù)理論基礎(chǔ) 覆蓋問題是無線傳感器網(wǎng)絡(luò)配置首先要面對的基本問題，它反映了一個(gè)無線傳感器網(wǎng)絡(luò)某區(qū)域被檢測和跟蹤的狀況?，F(xiàn)有的研究結(jié)果，很多都是致力于解決傳感器網(wǎng)絡(luò)的部署和檢測以及覆蓋與連接的關(guān)系等方面的問題。 覆蓋問題可以表述成不同的理論模型，甚至在平面幾何里就能找到相應(yīng)的解決方案。即使簡單地只從數(shù)學(xué)上來考慮，在部署傳感器節(jié)點(diǎn)的時(shí)候，我們必須知道怎樣用相同的節(jié)點(diǎn)數(shù)覆蓋盡可能大的區(qū)域。 為了對網(wǎng)絡(luò)的覆蓋問題先有一個(gè)初步的認(rèn)識(shí)，這里我們提出一個(gè)幾何問題-藝術(shù)館問題來理解。 假設(shè)藝術(shù)館的主人想在場館內(nèi)放置監(jiān)視器來防止盜竊。假定相機(jī)可以有360度的

2、視角而且可以極大速度旋轉(zhuǎn)，相機(jī)可以監(jiān)視任何位置，視線不受影響。 關(guān)于實(shí)現(xiàn)這個(gè)想法存在兩個(gè)問題需要回答：首先就是到底需要多少臺(tái)相機(jī)；其次，這些相機(jī)應(yīng)當(dāng)放置在哪些地方才能保證館內(nèi)每個(gè)點(diǎn)至少被一臺(tái)相機(jī)監(jiān)視到。 一個(gè)簡單的辦法就是將多邊形分成不重疊的三角形，每個(gè)三角形里面放置一個(gè)相機(jī)。通過這個(gè)方法，我們可以得到最佳分布應(yīng)該如下圖，放置兩個(gè)相機(jī)相機(jī)足以覆蓋整個(gè)藝術(shù)館。我們可以知道無線傳感器網(wǎng)絡(luò)的覆蓋問題在本職上和上面的幾何問題是一致的：需要知道是否某個(gè)區(qū)域被充分覆蓋以及完全處于監(jiān)視之下。 但我們也必須認(rèn)識(shí)到，幾何研究的結(jié)果為理解傳感器覆蓋問題提供了一個(gè)理論背景，但這樣的求解辦法是無法直接應(yīng)用到無線傳感器

3、網(wǎng)絡(luò)。因?yàn)椋?. 監(jiān)視器可以看到無窮遠(yuǎn)的地方只要沒有障礙物阻擋，但是傳感器節(jié)點(diǎn)存在最大感應(yīng)范圍；2. 無線傳感器網(wǎng)路沒有類似監(jiān)視器之間固定的基礎(chǔ)設(shè)施，其拓?fù)浣Y(jié)構(gòu)可能隨時(shí)變化。2.覆蓋的感知模型在討論節(jié)點(diǎn)如何布置之前，需要先知道傳感器節(jié)點(diǎn)的感知模型。目前主要是兩種。a.布爾感知模型布爾感知模型是以一個(gè)節(jié)點(diǎn)為圓心，以感知距離為半徑的圓形區(qū)域，只有落在該圓形區(qū)域內(nèi)的點(diǎn)才能被該節(jié)點(diǎn)覆蓋，這種模型也被稱為0-1模型。其數(shù)學(xué)表達(dá)式為pij=1,d(i,j)r0,d(i,j)>rb.概率感知模型概率感知模型中，目標(biāo)被感知的概率不再是常數(shù)，而是由目標(biāo)到節(jié)點(diǎn)間距、節(jié)點(diǎn)物理特性等諸多因素決定的變量。在節(jié)點(diǎn)i

4、不存在鄰居節(jié)點(diǎn)的前提下，節(jié)點(diǎn)i對檢測區(qū)域內(nèi)目標(biāo)j的感知概率有以下三種定義形式：pij=e-d(i,jpij=1,d(i,j)r1e-d(i,j)-r,r1<d(i,j)r20,d(i,j)>r2pij=11+d(i,j),d(i,j)r0,d(i,j)>r其中d(i,j)為節(jié)點(diǎn)i到目標(biāo)j之間的歐式距離，和是和傳感器物理特性有關(guān)的類型參數(shù)。從以上的3種形式可以看出，任一點(diǎn)的覆蓋概率是介于0和1之間的數(shù)。如果節(jié)點(diǎn)i存在N個(gè)鄰居節(jié)點(diǎn)，節(jié)點(diǎn)j落在和相鄰節(jié)點(diǎn)交疊傳感區(qū)域內(nèi)，節(jié)點(diǎn)j的感知概率便會(huì)受到節(jié)點(diǎn)i與相鄰節(jié)點(diǎn)共同影響。假設(shè)節(jié)點(diǎn)i與相鄰節(jié)點(diǎn)感知區(qū)域的重疊區(qū)域?yàn)镸，而且每個(gè)節(jié)點(diǎn)對目標(biāo)的

5、感知是相互獨(dú)立的，那么M中任意節(jié)點(diǎn)j的感知概率為3.覆蓋算法分類a節(jié)點(diǎn)部署方式分類 按照無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的不同配置方式(即節(jié)點(diǎn)否需要知道自身位置信息)，可以將無線傳感器網(wǎng)絡(luò)的覆蓋算法分為確定性覆蓋、隨機(jī)覆蓋兩大類。 (1)確定性覆蓋 這是已知節(jié)點(diǎn)位置的無線傳感器網(wǎng)絡(luò)要完成目標(biāo)區(qū)域或目標(biāo)點(diǎn)的覆蓋。 (2)隨機(jī)覆蓋 隨機(jī)覆蓋考慮在網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)隨機(jī)分布且位置未知的條件下，完成對監(jiān)測區(qū)域的覆蓋任務(wù)。b覆蓋目標(biāo)分類 根據(jù)無線傳感器網(wǎng)絡(luò)不同的應(yīng)用，覆蓋需求通常不同。根據(jù)覆蓋目標(biāo)不同，目前覆蓋算法可以分為面覆蓋、點(diǎn)覆蓋及柵欄覆蓋。 (1)面覆蓋 目標(biāo)是在大量冗余節(jié)點(diǎn)中尋找能覆蓋同樣區(qū)域大小并保證網(wǎng)絡(luò)連

6、通的最小節(jié)點(diǎn)集合。 (2)點(diǎn)覆蓋 覆蓋一些離散的目標(biāo)點(diǎn)，并使每一個(gè)目標(biāo)點(diǎn)至少能被一個(gè)節(jié)點(diǎn)覆蓋。 (3)柵欄覆蓋 目標(biāo)是找出連接出發(fā)位置和離開位置的路徑，使這樣的路徑能在不同模型定義下提供對目標(biāo)的不同傳感質(zhì)量。根據(jù)目標(biāo)穿越網(wǎng)絡(luò)時(shí)所用的不同模型，柵欄覆蓋可以分為最壞與最佳情況覆蓋以及暴露覆蓋。 最壞情況是指考察所有路徑中不被傳感器節(jié)點(diǎn)檢測的概率最小情況； 最佳情況是指考察所有路徑中被傳感器節(jié)點(diǎn)檢測的概率最大情況；暴露穿越同時(shí)考慮了目標(biāo)暴露的時(shí)間因素和傳感器節(jié)點(diǎn)對于目標(biāo)的感應(yīng)強(qiáng)度的因素，反映了運(yùn)動(dòng)目標(biāo)穿越網(wǎng)路區(qū)域的時(shí)間增加而感應(yīng)強(qiáng)度累加值增大的情況。4.經(jīng)典覆蓋算法a.基于網(wǎng)格的覆蓋定位傳感器配置算

7、法考慮傳感器節(jié)點(diǎn)及目標(biāo)點(diǎn)都采用網(wǎng)格形式配置，節(jié)點(diǎn)采用布爾覆蓋模型，并使用能量矢量來表示格點(diǎn)的覆蓋。如右圖，各格點(diǎn)都可至少被一個(gè)傳感器節(jié)點(diǎn)覆蓋，此時(shí)區(qū)域達(dá)到了完全覆蓋，例如格點(diǎn)位置8的能量矢量為（0,0,1,1,0,0）。當(dāng)網(wǎng)絡(luò)資源受限無法達(dá)到格點(diǎn)完全覆蓋時(shí)，需要根據(jù)配置代價(jià)上限進(jìn)行相關(guān)的節(jié)點(diǎn)布置?；诰W(wǎng)格的覆蓋定位傳感器配置算法設(shè)計(jì)了一種模擬退火算法來最小化距離錯(cuò)誤。首先假設(shè)每個(gè)格點(diǎn)都配置有傳感器，然后循環(huán)執(zhí)行以下過程，試圖刪除一個(gè)傳感器節(jié)點(diǎn)，然后進(jìn)行配置代價(jià)評價(jià)，如果評價(jià)不通過，就將該節(jié)點(diǎn)移到另外一個(gè)隨機(jī)選擇的位置，然后再進(jìn)行配置代價(jià)評價(jià)。循環(huán)得到優(yōu)化值同時(shí)保存新的配置節(jié)點(diǎn)情況。最后，改進(jìn)算

8、法停止執(zhí)行的準(zhǔn)則。在達(dá)到模擬退火算法的冷卻溫度時(shí)，優(yōu)化覆蓋識(shí)別的網(wǎng)絡(luò)配置方案也同時(shí)達(dá)到。b.分布式貪婪的連通傳感器覆蓋方法該算法屬于連通性覆蓋中的連通路徑覆蓋及確定性面點(diǎn)覆蓋類型。假設(shè)已選擇的傳感器節(jié)點(diǎn)集合為M,選擇與M有相交的傳感區(qū)域的節(jié)點(diǎn)稱為候選節(jié)點(diǎn)。集中式算法初始節(jié)點(diǎn)隨機(jī)選擇構(gòu)成M之后，在所有從初始節(jié)點(diǎn)集合出發(fā)到候選節(jié)點(diǎn)的路徑中選擇一條可以覆蓋更多未覆蓋子區(qū)域的路徑。將該路徑經(jīng)過的節(jié)點(diǎn)加入M，算法繼續(xù)執(zhí)行到網(wǎng)絡(luò)查詢區(qū)域可以完全被更新后的M覆蓋。如圖所示為該貪婪算法執(zhí)行的方式。在圖A中，貪婪算法會(huì)選擇路徑得到b，這是因?yàn)樵谒袀溥x路徑中，C3和C4組成的路經(jīng)P2可以覆蓋更多子區(qū)域。c.輪換

9、活躍/休眠節(jié)點(diǎn)的覆蓋方法采用輪換活躍和休眠節(jié)點(diǎn)的覆蓋協(xié)議可以有效延長網(wǎng)絡(luò)生存時(shí)間，該協(xié)議屬于確定性和節(jié)能覆蓋協(xié)議采用節(jié)點(diǎn)輪換工作機(jī)制，每個(gè)周期由一個(gè)Self-Scheduling階段和一個(gè)Working階段組成。在第一個(gè)階段，各節(jié)點(diǎn)首先向傳感半徑內(nèi)鄰居節(jié)點(diǎn)廣播通告消息，其中包括節(jié)點(diǎn)ID和位置。節(jié)點(diǎn)檢查自身傳感任務(wù)是否可以可由鄰居節(jié)點(diǎn)完成，可替代的節(jié)點(diǎn)返回一條狀態(tài)通告消息，之后進(jìn)入休眠狀態(tài)，需要繼續(xù)工作的節(jié)點(diǎn)執(zhí)行傳感任務(wù)。但是這種機(jī)制存在一個(gè)問題,如果鄰居節(jié)點(diǎn)同時(shí)檢查到自身的傳感任務(wù)可由對方完成，并同進(jìn)入休眠狀態(tài)，就會(huì)出現(xiàn)下圖所示的盲點(diǎn)。節(jié)點(diǎn)e和f的整個(gè)傳感區(qū)域都可以被相鄰的鄰居節(jié)點(diǎn)代替覆蓋，但

10、如果e和f進(jìn)入休眠狀態(tài)，就出現(xiàn)了不能檢測的陰影區(qū)域，即盲點(diǎn)。為了避免這種情況的發(fā)生，節(jié)點(diǎn)在第一個(gè)階段檢查之前執(zhí)行一個(gè)退避機(jī)制。每一個(gè)節(jié)點(diǎn)在隨機(jī)產(chǎn)生的時(shí)間之后再檢查工作。為了進(jìn)一步避免盲點(diǎn)的出現(xiàn)，每個(gè)節(jié)點(diǎn)在進(jìn)入休眠狀態(tài)之前還將等待一定的時(shí)間來監(jiān)聽鄰居節(jié)點(diǎn)的狀態(tài)更新。d.最壞情況覆蓋方法最壞情況覆蓋屬于確定性網(wǎng)絡(luò)路徑/目標(biāo)覆蓋和柵欄覆蓋類型，算法考慮如何對穿越網(wǎng)絡(luò)的目標(biāo)或其所在路徑上的各店進(jìn)行感應(yīng)與追蹤，體現(xiàn)了一種網(wǎng)絡(luò)覆蓋性質(zhì)。這里我們定義最大突破路徑，分別使得路徑上的點(diǎn)到周圍傳感器的最小距離最大化。顯然，這條路徑代表了無線傳感器網(wǎng)絡(luò)最壞（不被檢測的概率最?。?。文中分別采用計(jì)算幾何中的Vornoi

11、圖與Delaunay三角形來完成最大突破路徑的構(gòu)造和查找。其中， Vornoi圖是由所有Delaunay三角形邊上的垂直平分線形成的，Delaunay三角形各頂點(diǎn)為網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)，并滿足子三角形外接圓不包括其他節(jié)點(diǎn)，由于Vornoi圖中的線段具有到最近的傳感器節(jié)點(diǎn)距離最大的性質(zhì)，因此最大突破路徑一定是由Vornoi圖中的線段組成。5.覆蓋性能評價(jià)指標(biāo)假設(shè)無線傳感器網(wǎng)絡(luò)布置在二維平面空間內(nèi)，由移動(dòng)、固定兩種無線傳感器節(jié)點(diǎn)構(gòu)成，各節(jié)點(diǎn)具有相同的測量范圍、測量可信度和通信半徑。固定節(jié)點(diǎn)采用隨機(jī)布置方式，通過全球定位系統(tǒng)獲取自身位置信息，并在網(wǎng)絡(luò)中發(fā)布共享。a.無線傳感器網(wǎng)絡(luò)的覆蓋指標(biāo)由于節(jié)點(diǎn)布置的

12、固有冗余性，網(wǎng)絡(luò)覆蓋評價(jià)采用了可靠度的概念，對一定區(qū)域，若在t時(shí)刻處于n個(gè)節(jié)點(diǎn)測量范圍內(nèi)，該區(qū)域綜合可靠度表示為待測區(qū)域中所有綜合可靠度大于測量可靠性要求的區(qū)域成為有效測量區(qū)域。將有效測量區(qū)域面積占待測總面積的比例定義為覆蓋指標(biāo)C。b.無線傳感器網(wǎng)絡(luò)的能耗指標(biāo)無線信號在傳播過程中隨著傳播距離增加而發(fā)生衰減，采用自由空間模型計(jì)算傳播損耗如下：式中，LP為路徑損耗，D為傳播距離。假設(shè)無線傳感器網(wǎng)絡(luò)通信能耗模型為：運(yùn)行發(fā)送器或者接收器的無線花費(fèi)為Eelec=50nj/b ，發(fā)送放大器容許放大倍率的無線花費(fèi)為Eamp=100pj/b 。二維空間內(nèi)，坐標(biāo)分別為（xi,yi),xj,yj的無線傳感器節(jié)點(diǎn)i,j,通信時(shí)信號傳播距離計(jì)算如下：若節(jié)點(diǎn)i向節(jié)點(diǎn)j發(fā)送長度為kb的數(shù)據(jù)包，則節(jié)點(diǎn)i能耗為：節(jié)點(diǎn)j接收此數(shù)據(jù)包傳輸所消耗的能耗是所消耗的總能量是無線傳感器網(wǎng)絡(luò)的覆蓋能效優(yōu)化可以擴(kuò)大無線傳感器網(wǎng)絡(luò)的有效測量區(qū)域面積，從而提高網(wǎng)絡(luò)整體測量性能。節(jié)點(diǎn)通信范圍通常遠(yuǎn)大于其感知范圍，且儲(chǔ)存能量有限，因此提高能效性成為無線傳感器網(wǎng)絡(luò)測量的關(guān)鍵。無線傳感器節(jié)點(diǎn)的通信能耗與測量和數(shù)據(jù)處理能耗相比高許多，通信能耗的優(yōu)化對提高無線傳感器網(wǎng)絡(luò)能效十分重要。6.總結(jié)覆蓋問題是無線傳感器網(wǎng)絡(luò)配置首先面臨的基