第3章WSN拓?fù)浣Y(jié)構(gòu)、覆蓋技術(shù)

1、第第3 3章章WSN 拓?fù)淇刂婆c覆蓋技術(shù)掌握WSN拓?fù)浣Y(jié)構(gòu)的分類了解WSN拓?fù)淇刂屏私釽SN功率控制掌握層次性拓?fù)浣Y(jié)構(gòu)控制方法了解啟發(fā)機(jī)制了解覆蓋理論基礎(chǔ)了解傳感器網(wǎng)絡(luò)的覆蓋控制3.13.1網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是組織無線傳感器節(jié)點(diǎn)的組網(wǎng)技術(shù)，有多種形態(tài)和組網(wǎng)方式。按照其組網(wǎng)形態(tài)和方式分，有集中式、分布式和混合式。無線傳感器網(wǎng)絡(luò)的集中式結(jié)構(gòu)類似移動(dòng)通信的蜂窩結(jié)構(gòu)，集中管理；無線傳感器網(wǎng)絡(luò)的分布式結(jié)構(gòu)，類似Ad Hoc網(wǎng)絡(luò)結(jié)構(gòu)，可自組織網(wǎng)絡(luò)接入連接，分布管理；無線傳感器網(wǎng)絡(luò)的混合式結(jié)構(gòu)包括集中式和分布式結(jié)構(gòu)的組合。按照節(jié)點(diǎn)功能及結(jié)構(gòu)層次分，無線傳感器網(wǎng)絡(luò)通常可分為平

2、面網(wǎng)絡(luò)結(jié)構(gòu)、分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)、混合網(wǎng)絡(luò)結(jié)構(gòu)，以及Mesh網(wǎng)絡(luò)結(jié)構(gòu)3.1.1平面網(wǎng)絡(luò)結(jié)構(gòu)平面網(wǎng)絡(luò)結(jié)構(gòu)如圖3-1所示，平面網(wǎng)絡(luò)結(jié)構(gòu)是無線傳感器網(wǎng)絡(luò)中最簡(jiǎn)單的一種拓?fù)浣Y(jié)構(gòu)，具有如下特點(diǎn)：（1）所有節(jié)點(diǎn)為對(duì)等結(jié)構(gòu)；（2）這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單，易維護(hù)，具有較好的健壯性，（3）由于沒有中心管理節(jié)點(diǎn)3.1.2 3.1.2 分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)分級(jí)網(wǎng)絡(luò)結(jié)構(gòu) 如圖如圖3-23-2是分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)是分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)( (也叫層次網(wǎng)絡(luò)結(jié)構(gòu)也叫層次網(wǎng)絡(luò)結(jié)構(gòu)) )： 特點(diǎn)：網(wǎng)絡(luò)分為上層和下層兩個(gè)部分，上層為中心骨干節(jié)點(diǎn)，下層為特點(diǎn)：網(wǎng)絡(luò)分為上層和下層兩個(gè)部分，上層為中心骨干節(jié)點(diǎn)，下層為一般傳感器節(jié)點(diǎn)。一般傳感器節(jié)點(diǎn)。 3.1.3 3.1

3、.3 混合網(wǎng)絡(luò)結(jié)構(gòu)混合網(wǎng)絡(luò)結(jié)構(gòu) 如圖如圖3-33-3是混合網(wǎng)絡(luò)結(jié)構(gòu)：是混合網(wǎng)絡(luò)結(jié)構(gòu)： 特點(diǎn)是：特點(diǎn)是： 1 1，網(wǎng)絡(luò)骨干節(jié)點(diǎn)之間及一般傳感器節(jié)點(diǎn)之間都采用平面網(wǎng)絡(luò)結(jié)構(gòu)；，網(wǎng)絡(luò)骨干節(jié)點(diǎn)之間及一般傳感器節(jié)點(diǎn)之間都采用平面網(wǎng)絡(luò)結(jié)構(gòu)； 2 2，網(wǎng)絡(luò)骨干節(jié)點(diǎn)和一般傳感器節(jié)點(diǎn)之間采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)。，網(wǎng)絡(luò)骨干節(jié)點(diǎn)和一般傳感器節(jié)點(diǎn)之間采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)。 3.1.4 Mesh3.1.4 Mesh網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu) 從結(jié)構(gòu)來看，從結(jié)構(gòu)來看，MeshMesh網(wǎng)絡(luò)是規(guī)則分布的網(wǎng)絡(luò)。網(wǎng)絡(luò)是規(guī)則分布的網(wǎng)絡(luò)。 如圖如圖3-43-4所示，通常只允許和節(jié)點(diǎn)最近的鄰居通信；所示，通常只允許和節(jié)點(diǎn)最近的鄰居通信； 如圖如圖3-53-

4、5所示，網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)一般都是相同，因此所示，網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)一般都是相同，因此MeshMesh網(wǎng)絡(luò)也稱為對(duì)等網(wǎng)。網(wǎng)絡(luò)也稱為對(duì)等網(wǎng)。 MeshMesh網(wǎng)絡(luò)結(jié)構(gòu)最大的優(yōu)點(diǎn)：網(wǎng)絡(luò)結(jié)構(gòu)最大的優(yōu)點(diǎn)：是盡管所有節(jié)點(diǎn)都是對(duì)等的地位，且具有是盡管所有節(jié)點(diǎn)都是對(duì)等的地位，且具有相同的計(jì)算和通信傳輸功能。相同的計(jì)算和通信傳輸功能。 如圖如圖3-63-6所示，采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)技術(shù)可使所示，采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)技術(shù)可使MeshMesh網(wǎng)絡(luò)路由設(shè)計(jì)要簡(jiǎn)單得多，由網(wǎng)絡(luò)路由設(shè)計(jì)要簡(jiǎn)單得多，由于一些數(shù)據(jù)處理可以在每個(gè)分級(jí)的層次里面完成，因而比較適合于無線傳感于一些數(shù)據(jù)處理可以在每個(gè)分級(jí)的層次里面完成，因而比較適合于無線傳感器網(wǎng)絡(luò)

5、的分布式信號(hào)處埋和決策。器網(wǎng)絡(luò)的分布式信號(hào)處埋和決策。3.1.4 Mesh3.1.4 Mesh網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)從技術(shù)上來看，基于從技術(shù)上來看，基于MeshMesh網(wǎng)絡(luò)結(jié)構(gòu)的無線傳感器具有以下網(wǎng)絡(luò)結(jié)構(gòu)的無線傳感器具有以下特點(diǎn)特點(diǎn)。(1)(1)由無線節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)：這種類型的網(wǎng)絡(luò)節(jié)點(diǎn)是由一個(gè)傳感器或執(zhí)行器構(gòu)成且由無線節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)：這種類型的網(wǎng)絡(luò)節(jié)點(diǎn)是由一個(gè)傳感器或執(zhí)行器構(gòu)成且連接到一個(gè)雙向無線收發(fā)器上；連接到一個(gè)雙向無線收發(fā)器上；(2)(2)節(jié)點(diǎn)按照節(jié)點(diǎn)按照MeshMesh拓?fù)浣Y(jié)構(gòu)部署，網(wǎng)內(nèi)每個(gè)節(jié)點(diǎn)至少可以和一個(gè)其它節(jié)點(diǎn)通信；拓?fù)浣Y(jié)構(gòu)部署，網(wǎng)內(nèi)每個(gè)節(jié)點(diǎn)至少可以和一個(gè)其它節(jié)點(diǎn)通信；(3)(3)支持多跳

6、路由：支持多跳路由：(4)(4)功耗限制和移動(dòng)性取決于節(jié)點(diǎn)類型及應(yīng)用的特點(diǎn)。功耗限制和移動(dòng)性取決于節(jié)點(diǎn)類型及應(yīng)用的特點(diǎn)。(5)(5)存在多種網(wǎng)絡(luò)接入方式，可以通過星型、存在多種網(wǎng)絡(luò)接入方式，可以通過星型、MeshMesh等節(jié)點(diǎn)方式和其它網(wǎng)絡(luò)集成。等節(jié)點(diǎn)方式和其它網(wǎng)絡(luò)集成。3.1.4 Mesh3.1.4 Mesh網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)3.2拓?fù)淇刂仆負(fù)淇刂?.2.1概述概述 拓?fù)淇刂萍夹g(shù)是無線傳感器網(wǎng)絡(luò)中的基本問題。動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu)是無線傳感器網(wǎng)絡(luò)最大特點(diǎn)之一，因此拓?fù)淇刂撇呗栽跓o線傳感器網(wǎng)絡(luò)中有著重要的意義，它為路由協(xié)議、MAC協(xié)議、數(shù)據(jù)融合、時(shí)間同步和目標(biāo)定位等很多方面奠定了基礎(chǔ)。 MAC層可以

7、提供給拓?fù)淇刂扑惴ㄠ従影l(fā)現(xiàn)等消息，如圖3-7所示。3.2.2拓?fù)淇刂频囊饬x拓?fù)淇刂频囊饬x研究具有十分重要的意義，主要表現(xiàn)在以下五個(gè)方面：(1)網(wǎng)絡(luò)壽命，(2)減少節(jié)點(diǎn)通信負(fù)載，提高通信效率，(3)輔助路由協(xié)議，(4)數(shù)據(jù)融合策略選擇，(5)節(jié)點(diǎn)冗余3.2.3拓?fù)淇刂圃O(shè)計(jì)目標(biāo)n拓?fù)淇刂浦幸话阋紤]的設(shè)計(jì)目標(biāo)有如下幾個(gè)方面。n1.覆蓋n2.連通n3.網(wǎng)絡(luò)生命期n4.吞吐能力n5.干擾和競(jìng)爭(zhēng)n6.網(wǎng)絡(luò)延遲n7.拓?fù)湫再|(zhì)3.3功率控制n傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)射功率的控制也稱功率分配問題。n1.基于節(jié)點(diǎn)度的功率控制n2.基于方向的功率控制n3.基于鄰近圖的功率控制n 4. XTC算法3.4 層次性拓?fù)浣Y(jié)構(gòu)控

8、制方法n層次型拓?fù)浣Y(jié)構(gòu)具有很多優(yōu)點(diǎn)，例如，由簇頭節(jié)點(diǎn)擔(dān)負(fù)數(shù)據(jù)融合的任務(wù)，減少了數(shù)據(jù)通信量；分簇式的拓?fù)浣Y(jié)構(gòu)有利于分布式算法的應(yīng)用，適合大規(guī)模部署的網(wǎng)絡(luò)；由于大部分節(jié)點(diǎn)在相當(dāng)長(zhǎng)的時(shí)間內(nèi)關(guān)閉通信模塊，所以顯著地延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間等。n1. LEACH算法 if 11( mod)( ) otherwise0pnGprT np 2. GAT算法nGAT算法是一種依據(jù)節(jié)點(diǎn)的地理位置進(jìn)行分簇，并對(duì)簇內(nèi)的節(jié)點(diǎn)選擇性的進(jìn)行休眠的路由算法。其核心思想是：在各數(shù)據(jù)源到數(shù)據(jù)目的地之問存在有效通路的前提下，盡量減少參與數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)數(shù)，從而減少用于數(shù)據(jù)包偵聽和接收的能量開銷。它將無線傳感器網(wǎng)絡(luò)劃分成若干個(gè)單元格(

9、簇)，各單元格內(nèi)任意一個(gè)節(jié)點(diǎn)都可以被選為代表，代替本單元格內(nèi)所有其他節(jié)點(diǎn)完成數(shù)據(jù)包向相鄰單元格的轉(zhuǎn)發(fā)。被選中的節(jié)點(diǎn)成為本單元格的簇頭節(jié)點(diǎn)；其他節(jié)點(diǎn)都進(jìn)行休眠，不發(fā)送、接收和偵聽數(shù)據(jù)包。n GAT算法通常分為虛擬單元格的劃分和虛擬單元格中簇頭節(jié)點(diǎn)的選擇兩個(gè)階段。n(1)虛擬單元格的劃分。n(2)虛擬單元格中的簇頭節(jié)點(diǎn)的選擇。3.5啟發(fā)機(jī)制n在傳感器網(wǎng)絡(luò)的拓?fù)淇刂扑惴ㄖ?，除了傳統(tǒng)的功率控制和層次型拓?fù)淇刂苾蓚€(gè)方面之外，也提出了啟發(fā)式的節(jié)點(diǎn)喚醒和休眠機(jī)制。該機(jī)制能夠使節(jié)點(diǎn)在沒有事件發(fā)生時(shí)設(shè)置通信模塊為睡眠狀態(tài)，而在有事件發(fā)生時(shí)及時(shí)自動(dòng)醒來并喚醒鄰居節(jié)點(diǎn)，形成數(shù)據(jù)轉(zhuǎn)發(fā)的拓?fù)浣Y(jié)構(gòu)。n1. STEM算法n

10、STEM(sparse Topology and Energy Management)算法是一種低占空比的節(jié)點(diǎn)喚醒機(jī)制。該算法采用雙信道，即監(jiān)聽信道和數(shù)據(jù)通信信道。具體地講，STEM算法又分為STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。n在STEM-B算法中，當(dāng)一個(gè)節(jié)點(diǎn)想給另外一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，它作為主動(dòng)節(jié)點(diǎn)先發(fā)送一串喚醒包。目標(biāo)節(jié)點(diǎn)在收到喚醒包后，發(fā)送應(yīng)答信號(hào)并自動(dòng)進(jìn)入數(shù)據(jù)接收狀態(tài)。主動(dòng)節(jié)點(diǎn)接收到應(yīng)答信號(hào)后，進(jìn)入數(shù)據(jù)發(fā)送階段。n 在STEM-T算法中，節(jié)點(diǎn)周期性地進(jìn)入偵聽階段，探測(cè)是否有鄰居節(jié)點(diǎn)要發(fā)送數(shù)據(jù)；當(dāng)一個(gè)節(jié)點(diǎn)想與某個(gè)鄰居節(jié)點(diǎn)進(jìn)行通信時(shí)，它就發(fā)

11、送一連串的喚醒包，發(fā)送喚醒包的時(shí)間長(zhǎng)度必須大于偵聽的時(shí)間間隔，可以確保鄰居節(jié)點(diǎn)能夠收到喚醒包，緊接著節(jié)點(diǎn)就直接發(fā)送數(shù)據(jù)包。所以STEM-T比STEM-B更簡(jiǎn)單實(shí)用。nSTEM算法適用于類似環(huán)境監(jiān)測(cè)或者突發(fā)事件監(jiān)測(cè)等應(yīng)用，經(jīng)實(shí)驗(yàn)證明，節(jié)點(diǎn)喚醒速度可以滿足應(yīng)用的需要。但是在STEM算法中，節(jié)點(diǎn)的睡眠周期、部署密度以及網(wǎng)絡(luò)的傳輸延遲之間有著密切的關(guān)系，要針對(duì)具體的應(yīng)用要求進(jìn)行調(diào)整。2. ASCENT算法n運(yùn)行ASCENT算法的網(wǎng)絡(luò)包括觸發(fā)、建立和穩(wěn)定三個(gè)主要階段。觸發(fā)階段如圖3-12(a)所示，在匯聚節(jié)點(diǎn)與數(shù)據(jù)源節(jié)點(diǎn)不能正常通信時(shí)，匯聚節(jié)點(diǎn)向它的鄰居節(jié)點(diǎn)發(fā)出求助信息；建立階段如圖3-12(b)所示，

12、當(dāng)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的求助消息時(shí)，通過一定的算法決定自己是否成為活動(dòng)節(jié)點(diǎn)，如果成為活動(dòng)節(jié)點(diǎn)，就向鄰居節(jié)點(diǎn)發(fā)送通告消息，同時(shí)這個(gè)消息是鄰居節(jié)點(diǎn)判斷自身是否成為活動(dòng)節(jié)點(diǎn)的因素之一；穩(wěn)定階段如圖3-12(c)所示，數(shù)據(jù)源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)間的通信恢復(fù)正常，網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)個(gè)數(shù)保持穩(wěn)定，從而達(dá)到穩(wěn)定狀態(tài)3.6 覆蓋3.6.1覆蓋理論基礎(chǔ) 覆蓋問題是無線傳感器網(wǎng)絡(luò)配置首先面臨的基本問題，因?yàn)閭鞲衅鞴?jié)點(diǎn)可能任意分布在配置區(qū)域，它反映了一個(gè)無線傳感器網(wǎng)絡(luò)某區(qū)域被監(jiān)測(cè)和跟蹤的狀況。 在現(xiàn)有的研究成果當(dāng)中，很多都是致力于解決傳感器網(wǎng)絡(luò)的部署和監(jiān)測(cè)及覆蓋與連接的關(guān)系等方面問題。另外，也有一些研究致力于特定的應(yīng)用需求，但其

13、核心思想都是與覆蓋問題有關(guān)的。 無線傳感器網(wǎng)絡(luò)覆蓋相關(guān)的兩個(gè)計(jì)算幾何問題,(三角形、圓)。 第一個(gè)就是藝術(shù)館問題(Art Gallery Problem)。設(shè)想藝術(shù)館的業(yè)主想在館內(nèi)放置照相機(jī)，以便能夠預(yù)防小偷盜竊。關(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)視到。假定相機(jī)可以有 的視角而且可以極大速度旋轉(zhuǎn)，相機(jī)可以監(jiān)視任何位置，視線不受影響。3.6.1覆蓋理論基礎(chǔ)0360問題優(yōu)化要實(shí)現(xiàn)的目標(biāo)就是所需相機(jī)的數(shù)目應(yīng)該最小化，在這個(gè)問題當(dāng)中，藝術(shù)館通常建模成一個(gè)二維平面的簡(jiǎn)單多邊形。一個(gè)簡(jiǎn)單的解決辦法就是將多邊形

14、分成不重疊的三角形，每個(gè)三角形里面放置一個(gè)相機(jī)。通過三角測(cè)量法將多邊形分成若干個(gè)三角形，這樣可以實(shí)現(xiàn)任何一個(gè)多邊形都可被 個(gè)相機(jī)所監(jiān)視到，這里 n 表示多邊形所包含的三角形的數(shù)目。這也是最糟糕情況下的最佳結(jié)果。3.6.1覆蓋理論基礎(chǔ) /3n如圖3-7所示是將一個(gè)簡(jiǎn)單多邊形用三角測(cè)量法拆分的例子，放置兩個(gè)監(jiān)視相機(jī)足以覆蓋整個(gè)藝術(shù)館。盡管這個(gè)問題在二維平面可以得到最優(yōu)解，然而擴(kuò)展到三維空間，這個(gè)問題就變成了NP-hard問題了。 圖3-7多邊形的三角測(cè)量法及監(jiān)視相機(jī)的位置配置NP-hard問題: NP是指非確定性多項(xiàng)式（non-deterministic polynomial，縮寫NP）。所謂的非

15、確定性是指，可用一定數(shù)量的運(yùn)算去解決多項(xiàng)式時(shí)間內(nèi)可解決的問題。NP 問題通俗來說是其解的正確性能夠被“很容易檢查”的問題，這里“很容易檢查”指的是存在一個(gè)多項(xiàng)式檢查算法。相應(yīng)的，若NP中所有問題到某一個(gè)問題是圖靈可歸約的，則該問題為NP困難問題3.6.1覆蓋理論基礎(chǔ) 另外一個(gè)與無線傳感器網(wǎng)絡(luò)覆蓋相關(guān)的幾何問題是圓覆蓋問題，即在一個(gè)平面上最多需要排列多少個(gè)相同大小的圓，才使其能夠完全覆蓋整個(gè)平面。換個(gè)角度說，也就是給定了圓的數(shù)目，如何使得圓的半徑最小。AHeppes和JBMMelissen實(shí)現(xiàn)了矩形平面的圓最優(yōu)覆蓋問題，分為最多用5個(gè)圓和7個(gè)圓來完成覆蓋兩種情況。如圖3-8所示給出了一個(gè)7個(gè)圓最

16、優(yōu)覆蓋的一個(gè)例子。 圖3-8用7個(gè)圓實(shí)現(xiàn)最優(yōu)覆蓋的樣例3.6.1覆蓋理論基礎(chǔ)無線傳感器網(wǎng)絡(luò)的覆蓋問題在本質(zhì)上和上面的幾何計(jì)算問題是一致的：需要知道是否某個(gè)特定的區(qū)域被充分覆蓋和完全處于監(jiān)視之下。就成本而言，配置的傳感器節(jié)點(diǎn)的數(shù)量是非常重要的。在典型的無線傳感器網(wǎng)絡(luò)應(yīng)用當(dāng)中，放置或配置一些傳感器節(jié)點(diǎn)來監(jiān)視一個(gè)區(qū)域或點(diǎn)集。3.6.1覆蓋理論基礎(chǔ) 確定性配置和非確定性的配置(隨機(jī)配置)1.一些應(yīng)用中可以選擇傳感器配置場(chǎng)地，如定點(diǎn)部署和配置，這種方式稱為確定性配置；2.而另外一些應(yīng)用(如敵方區(qū)域或非常惡劣等人員不能到達(dá)的環(huán)境)，只能通過隨機(jī)部署(如空投撒播方式)足夠多的傳感器節(jié)點(diǎn)到監(jiān)視區(qū)域，希望空投后

17、未遭破壞的傳感器足以監(jiān)視目標(biāo)區(qū)域，這種方式稱為非確定性的配置或隨機(jī)配置。如果可以選取部署場(chǎng)地，可采用確定性的傳感器配置方法；否則，該配置就是隨機(jī)配置。3.6.1覆蓋理論基礎(chǔ) 在上面兩種配置情況下，都希望部署的傳感器集合能夠彼此通信，或者直接或者間接通過多跳方式通信。 因此，除了要覆蓋感應(yīng)的區(qū)域或點(diǎn)集外，通常需要配置的傳感器集合能夠形成一個(gè)互聯(lián)的網(wǎng)絡(luò)。就連接特性而言，需要知道傳感器的通信半徑，其連接覆蓋的充分必要條件，滿足定理1。定理1：當(dāng)傳感器的密度(即單位區(qū)域的傳感器數(shù)目)為有限時(shí)，是覆蓋包含連接性的充分必要條件。3.6.1覆蓋理論基礎(chǔ) X.Wang等人也證明了在 k 階覆蓋(每個(gè)點(diǎn)至少被

18、k 個(gè)傳感器覆蓋)和 k 階連接性(配置傳感器的通信圖是k階連接的)情況下的一個(gè)類似的結(jié)論，滿足定理2。 定理2：當(dāng)，一個(gè)凸區(qū)域的 k 階覆蓋必定包含了k 階連接性。 注意到kl的k階覆蓋提供了一定的容錯(cuò)度，能夠監(jiān)視所有的點(diǎn)，只要不多于k-1個(gè)傳感器故障或失效。凸區(qū)域:就是凸的區(qū)域。凸從幾何上看就是圖形是往外凸的，沒有凹進(jìn)去的地方。代數(shù)上是這樣定義的：集合中任取兩個(gè)點(diǎn)a，b，有t*a+(1t)*b仍屬于這個(gè)集合，其中0t1。這個(gè)表達(dá)式的意思就是連接兩個(gè)點(diǎn)a b的直線段還在集合中。這是凸的意思。區(qū)域就是連通的開集，也可以等價(jià)的說是道路連通的開集。所謂道路連通也很好理解，就是集合中的任意兩個(gè)點(diǎn)有一

19、條道路連接它們。3.6.1覆蓋理論基礎(chǔ)與覆蓋問題直接相關(guān)的是傳感器節(jié)點(diǎn)的感知模型。目前，無線傳感器網(wǎng)絡(luò)主要有兩種基本感知模型。1布爾感知模型 2概率感知模型3.6.2覆蓋感知模型3.6.3覆蓋算法分類n1節(jié)點(diǎn)部署方式分類n 按照無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的不同配置方式(即節(jié)點(diǎn)是否需要知道自身位置信息)，可以將無線傳感器網(wǎng)絡(luò)的覆蓋算法分為確定性覆蓋、隨機(jī)覆蓋兩大類。n (1)確定性覆蓋n (2)隨機(jī)覆蓋n2覆蓋目標(biāo)分類n 根據(jù)無線傳感器網(wǎng)絡(luò)不同的應(yīng)用，覆蓋需求通常不同。根據(jù)覆蓋目標(biāo)不同，目前覆蓋算法可以分為面覆蓋、點(diǎn)覆蓋及柵欄覆蓋。n (1)面覆蓋n (2)點(diǎn)覆蓋n (3)柵欄覆蓋3.6.4典型覆蓋算法

20、n1基于網(wǎng)格的覆蓋定位傳感器配置算法n2圓周覆蓋3.6.4典型覆蓋算法3連通傳感器覆蓋 4輪換活躍/休眠節(jié)點(diǎn)的Self-Scheduling覆蓋協(xié)議3.6.4典型覆蓋算法5最壞與最佳情況覆蓋6暴露穿越覆蓋3.6.5覆蓋能效評(píng)價(jià)指標(biāo)1 1無線傳感網(wǎng)絡(luò)的覆蓋指標(biāo)無線傳感網(wǎng)絡(luò)的覆蓋指標(biāo)由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)布置的固有冗余性，網(wǎng)絡(luò)覆蓋評(píng)價(jià)采用了可靠由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)布置的固有冗余性，網(wǎng)絡(luò)覆蓋評(píng)價(jià)采用了可靠度的概念。對(duì)一定區(qū)域，若在度的概念。對(duì)一定區(qū)域，若在t t時(shí)刻處于時(shí)刻處于n n個(gè)節(jié)點(diǎn)測(cè)量范圍內(nèi)，該區(qū)域綜合個(gè)節(jié)點(diǎn)測(cè)量范圍內(nèi)，該區(qū)域綜合可靠度可靠度表示為表示為 (2-4)(2-4) 式中，式

21、中，r ri (i (t t) )表示第表示第i i個(gè)節(jié)點(diǎn)的測(cè)量可靠度。個(gè)節(jié)點(diǎn)的測(cè)量可靠度。 待測(cè)區(qū)域中待測(cè)區(qū)域中所有綜合可靠度所有綜合可靠度大于測(cè)量可靠性要求的區(qū)域稱為大于測(cè)量可靠性要求的區(qū)域稱為有效測(cè)量區(qū)域有效測(cè)量區(qū)域。用。用解析方法計(jì)算解析方法計(jì)算隨機(jī)布置無線傳感網(wǎng)絡(luò)的有效測(cè)量區(qū)域非常復(fù)雜，因此采用隨機(jī)布置無線傳感網(wǎng)絡(luò)的有效測(cè)量區(qū)域非常復(fù)雜，因此采用數(shù)數(shù)值計(jì)算方法值計(jì)算方法，將待測(cè)區(qū)域網(wǎng)格化，單元格簡(jiǎn)化為點(diǎn)，計(jì)算各點(diǎn)的綜合可靠度，統(tǒng)，將待測(cè)區(qū)域網(wǎng)格化，單元格簡(jiǎn)化為點(diǎn)，計(jì)算各點(diǎn)的綜合可靠度，統(tǒng)計(jì)滿足測(cè)量可靠度要求的單元格面積，得到有效測(cè)量區(qū)域面積數(shù)值解。將有效測(cè)計(jì)滿足測(cè)量可靠度要求的單元格

22、面積，得到有效測(cè)量區(qū)域面積數(shù)值解。將有效測(cè)量區(qū)域面積占待測(cè)總面積的比例定義為覆蓋指標(biāo)量區(qū)域面積占待測(cè)總面積的比例定義為覆蓋指標(biāo)C C。1( )1(1( )niiR tr t 2無線傳感器網(wǎng)絡(luò)的能耗指標(biāo)n無線信號(hào)在傳播過程中隨著無線信號(hào)在傳播過程中隨著傳播距離增加而發(fā)生衰減傳播距離增加而發(fā)生衰減，采用自由空間模，采用自由空間模型型計(jì)算傳播損耗計(jì)算傳播損耗如下：如下： (2-5)(2-5) 式中，式中，L Lp p為路徑損耗；為路徑損耗；D D為傳播距離；為信號(hào)波長(zhǎng)。為傳播距離；為信號(hào)波長(zhǎng)。n針對(duì)無線信號(hào)傳播過程，假設(shè)無線傳感器網(wǎng)絡(luò)通信能耗模型為：運(yùn)行發(fā)針對(duì)無線信號(hào)傳播過程，假設(shè)無線傳感器網(wǎng)絡(luò)通信

23、能耗模型為：運(yùn)行發(fā)送器或接收器的無線花費(fèi)為送器或接收器的無線花費(fèi)為E Eelec=50nJ/bitelec=50nJ/bit，發(fā)送放大器實(shí)現(xiàn)容許放大，發(fā)送放大器實(shí)現(xiàn)容許放大倍率的無線花費(fèi)為倍率的無線花費(fèi)為E Eamp=100pJ/bit mamp=100pJ/bit m-2-2。n二維空間內(nèi)，坐標(biāo)分別為二維空間內(nèi)，坐標(biāo)分別為( (x xi i，y yi i) )、( (x xj j，y yj j) )的無線傳感節(jié)點(diǎn)的無線傳感節(jié)點(diǎn)i i、j j，通信，通信時(shí)信號(hào)時(shí)信號(hào)傳播距離傳播距離計(jì)算如下：計(jì)算如下： (2-6) (2-6) 2()4pLD22()()i jijijdxxyyn若節(jié)點(diǎn)若節(jié)點(diǎn)i i向向j j發(fā)送發(fā)送長(zhǎng)度