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

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

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

3、網(wǎng)絡(luò)。因?yàn)椋?. 監(jiān)視器可以看到無(wú)窮遠(yuǎn)的地方只要沒(méi)有障礙物阻擋，但是 傳感器節(jié)點(diǎn)存在最大感應(yīng)范圍；2. 無(wú)線傳感器網(wǎng)路沒(méi)有類(lèi)似監(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)覆蓋，這種模型也被稱(chēng) 為0-1模型。其數(shù)學(xué)表達(dá)式為_(kāi) l,d(i, j) W r卩門(mén)(O,d(i, j) rb.概率感知模型概率感知模型中，目標(biāo)被感知的概率不再是常數(shù)，而是由目標(biāo)到節(jié)點(diǎn)間距、節(jié)點(diǎn)物理特性等諸多因素決定的

4、變量。在節(jié)點(diǎn)i不存在鄰居節(jié)點(diǎn)的前提下，節(jié)點(diǎn)i對(duì)檢測(cè)區(qū)域內(nèi)目標(biāo)j的感知概率有以下三種定義形式:l,d(i,j) W riPij = 1 e a r,ri r21 + Qd(i,j)廣O,d(i, j),d(i, j) r其中d(ij)為節(jié)點(diǎn)i到目標(biāo)j之間的歐式距離，Q和B是和 傳感器物理特性有關(guān)的類(lèi)型參數(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)對(duì)目標(biāo)的感知是相互獨(dú)立的，那么M中任意節(jié)點(diǎn)j的感知概率

5、為N1 - (1 - Pkj)k=l3覆蓋算法分類(lèi)a. 節(jié)點(diǎn)部署方式分類(lèi)按照無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的不同配置方式(即節(jié)點(diǎn)否需要知道自 身位置信息)，可以將無(wú)線傳感器網(wǎng)絡(luò)的覆蓋算法分為確定性覆蓋、 隨機(jī)覆蓋兩大類(lèi)。(1) 確定性覆蓋這是已知節(jié)點(diǎn)位置的無(wú)線傳感器網(wǎng)絡(luò)要完成目標(biāo)區(qū)域或目標(biāo)點(diǎn) 的覆蓋。(2) 隨機(jī)覆蓋隨機(jī)覆蓋考慮在網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)隨機(jī)分布且位置未知的條件 下，完成對(duì)監(jiān)測(cè)區(qū)域的覆蓋任務(wù)。)b. 覆蓋目標(biāo)分類(lèi)根據(jù)無(wú)線傳感器網(wǎng)絡(luò)不同的應(yīng)用，覆蓋需求通常不同。根據(jù)覆蓋 目標(biāo)不同，目前覆蓋算法可以分為面覆蓋、點(diǎn)覆蓋及柵欄覆蓋。仃)面覆蓋目標(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ā)位置和離開(kāi)位置的路徑，使這樣的路徑能在 不同模型定義下提供對(duì)目標(biāo)的不同傳感質(zhì)量。根據(jù)目標(biāo)穿越網(wǎng)絡(luò)時(shí)所用的不同模型，柵欄覆蓋可以分為最壞 與最佳情況覆蓋以及暴露覆蓋。最壞情況是指考察所有路徑中不被傳感器節(jié)點(diǎn)檢測(cè)的概率最小 情況；最佳情況是指考察所有路徑中被傳感器節(jié)點(diǎn)檢測(cè)的概率最大情 況；暴露穿越同時(shí)考慮了目標(biāo)暴露的時(shí)間因素和傳感器節(jié)點(diǎn)對(duì)于目 標(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)采用布爾覆 蓋模型，并使用能量矢量來(lái)表示格點(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ò) 資源受限無(wú)法達(dá)到格點(diǎn)完全覆蓋時(shí)，需要根據(jù)配置代價(jià)上限進(jìn)行相關(guān) 的節(jié)點(diǎn)布置。O傳感器卩點(diǎn) O格恵基于網(wǎng)格的覆蓋定位傳感器配置算法設(shè)計(jì)了一種模擬退火算法 來(lái)最小化距離錯(cuò)誤。首先假設(shè)每個(gè)格點(diǎn)都配置有傳感器，然后循環(huán)執(zhí)行以下過(guò)程，試 圖刪除一個(gè)傳感器節(jié)點(diǎn)，然后進(jìn)行配置代價(jià)評(píng)價(jià)，如果評(píng)價(jià)不通過(guò)， 就將該節(jié)點(diǎn)移到另外一個(gè)隨機(jī)選擇的位置，然后再進(jìn)行配置代價(jià)評(píng) 價(jià)。循環(huán)得到優(yōu)化值

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

9、C3和C4組成的路經(jīng)采用輪換活躍和休眠節(jié)點(diǎn)的覆蓋協(xié)議可以有效延長(zhǎng)網(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è)問(wèn)題，如果鄰居節(jié)點(diǎn)同時(shí)檢查到自身的傳 感任務(wù)可由對(duì)方完成，并同進(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)了不能檢測(cè)的陰影區(qū)域，即盲點(diǎn)。退避機(jī)制。每一個(gè)節(jié)點(diǎn)在隨機(jī)產(chǎn)生的時(shí)間之后再檢查工作。為了進(jìn)一步避免盲點(diǎn)的出現(xiàn)，每個(gè)節(jié)點(diǎn)在進(jìn)入休眠狀態(tài)之前還將 等待一定的時(shí)間來(lái)監(jiān)聽(tīng)鄰居節(jié)點(diǎn)的狀態(tài)更新。d.最壞情況覆蓋方法最壞情況覆蓋屬于確定性網(wǎng)絡(luò)路徑/目標(biāo)覆蓋和柵欄覆蓋類(lèi)型， 算法考慮如何對(duì)穿越網(wǎng)絡(luò)的目標(biāo)或其所在路徑上的各店進(jìn)行感應(yīng)與 追蹤，體現(xiàn)了一種網(wǎng)絡(luò)覆蓋性質(zhì)。這里我們定義最大突破路徑，分別使得路徑上的點(diǎn)到周?chē)鷤鞲衅?的最小距離最大化。顯然，這條路徑代表了無(wú)線傳感器網(wǎng)絡(luò)最壞（不 被檢測(cè)的概率最小）。文中分別采用計(jì)算幾何中的Vornoi圖與Delaunay三角形來(lái)完成 最

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

12、評(píng)價(jià)采用了可靠度的概念，對(duì)一定區(qū)域，若在t時(shí)刻處于n個(gè)節(jié)點(diǎn)測(cè)量范圍內(nèi)，該區(qū)域綜合可靠度表示為陀） = 1-H（1-廠i（）i=l待測(cè)區(qū)域中所有綜合可靠度大于測(cè)量可靠性要求的區(qū)域成為有效測(cè)量區(qū)域。將有效測(cè)量區(qū)域面積占待測(cè)總面積的比例定義為覆蓋指標(biāo)Cob.無(wú)線傳感器網(wǎng)絡(luò)的能耗指標(biāo)無(wú)線信號(hào)在傳播過(guò)程中隨著傳播距離增加而發(fā)生衰減，釆用自由 空間模型計(jì)算傳播損耗如下:式中，Lp為路徑損耗，D為傳播距離。假設(shè)無(wú)線傳感器網(wǎng)絡(luò)通信能耗模型為:運(yùn)行發(fā)送器或者接收器的無(wú)線花費(fèi)為Eelec二50nj/b ,發(fā)送放大器容許放大倍率的無(wú)線花費(fèi)為Eamp = 100pj/b o二維空間內(nèi)，坐標(biāo)分別為（Xi,yi）,（xj

13、,y、j）的無(wú)線傳感器節(jié)點(diǎn)i, j,通信時(shí)信號(hào)傳播距離計(jì)算如下：若節(jié)點(diǎn)i向節(jié)點(diǎn)j發(fā)送長(zhǎng)度為kb的數(shù)據(jù)包，則節(jié)點(diǎn)i能耗為:Etx(K d) = ETx-eLec(k) + Tx-amp =Eggck + Eampkdj節(jié)點(diǎn)j接收此數(shù)據(jù)包傳輸所消耗的能耗是ERx (k) = Erx 一 eiec(k) = elec所消耗的總能量是Eij(k) = k(Eeiec + Eamp硝）無(wú)線傳感器網(wǎng)絡(luò)的覆蓋能效優(yōu)化可以擴(kuò)大無(wú)線傳感器網(wǎng)絡(luò)的有 效測(cè)量區(qū)域面積，從而提高網(wǎng)絡(luò)整體測(cè)量性能。節(jié)點(diǎn)通信范圍通常遠(yuǎn) 大于其感知范圍，且儲(chǔ)存能量有限，因此提高能效性成為無(wú)線傳感器 網(wǎng)絡(luò)測(cè)量的關(guān)鍵。無(wú)線傳感器節(jié)點(diǎn)的通信能耗與測(cè)量和數(shù)據(jù)處理能耗 相比髙許多，通信能耗的優(yōu)化對(duì)提高無(wú)線傳感器網(wǎng)絡(luò)能效十分重要。6. 總結(jié)覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)配置首先面臨的基本