無(wú)線傳感器網(wǎng)絡(luò)第二章

1、第2章,無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)、覆蓋與連接,2.1網(wǎng)絡(luò)結(jié)構(gòu)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),1. 平面網(wǎng)絡(luò)結(jié)構(gòu) 如圖2-1所示，平面網(wǎng)絡(luò)結(jié)構(gòu)是無(wú)線傳感器網(wǎng)絡(luò)中最簡(jiǎn)單的一種拓?fù)浣Y(jié)構(gòu)，所有節(jié)點(diǎn)為對(duì)等結(jié)構(gòu)，具有完全一致的功能特性，也就是說(shuō)每個(gè)節(jié)點(diǎn)均包含相同的MAC、路由、管理和安全等協(xié)議。這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單，易維護(hù)，具有較好的健壯性，事實(shí)上就是一種Ad Hoc網(wǎng)絡(luò)結(jié)構(gòu)形式。由于沒(méi)有中心管理節(jié)點(diǎn)，故采用自組織協(xié)同算法形成網(wǎng)絡(luò)，其組網(wǎng)算法比較復(fù)

2、雜。,,2. 分級(jí)網(wǎng)絡(luò)結(jié)構(gòu),如圖2-2所示，分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)(也叫層次網(wǎng)絡(luò)結(jié)構(gòu))是無(wú)線傳感器網(wǎng)絡(luò)中平面網(wǎng)絡(luò)結(jié)構(gòu)的一種擴(kuò)展拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)分為上層和下層兩個(gè)部分：上層為中心骨干節(jié)點(diǎn)；下層為一般傳感器節(jié)點(diǎn)。,,3. 混合網(wǎng)絡(luò)結(jié)構(gòu),如圖2-3所示，混合網(wǎng)絡(luò)結(jié)構(gòu)是無(wú)線傳感器網(wǎng)絡(luò)中平面網(wǎng)絡(luò)結(jié)構(gòu)和分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)的一種混合拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)骨干節(jié)點(diǎn)之間及一般傳感器節(jié)點(diǎn)之間都采用平面網(wǎng)絡(luò)結(jié)構(gòu)，而網(wǎng)絡(luò)骨干節(jié)點(diǎn)和一般傳感器節(jié)點(diǎn)之間采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)。,,4. Mesh

3、網(wǎng)絡(luò)結(jié)構(gòu),Mesh網(wǎng)絡(luò)結(jié)構(gòu)是一種新型的無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)，從結(jié)構(gòu)來(lái)看，Mesh網(wǎng)絡(luò)是規(guī)則分布的網(wǎng)絡(luò)，不同于完全連接的網(wǎng)絡(luò)結(jié)構(gòu)，如圖2-4所示。通常只允許和節(jié)點(diǎn)最近的鄰居通信，如圖2-5所示。網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)一般都是相同，因此Mesh網(wǎng)絡(luò)也稱(chēng)為對(duì)等網(wǎng)。,,,如圖2-6所示，采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)技術(shù)可使Mesh網(wǎng)絡(luò)路由設(shè)計(jì)要簡(jiǎn)單得多，由于一些數(shù)據(jù)處理可以在每個(gè)分級(jí)的層次里面完成，因而比較適合于無(wú)線傳感器網(wǎng)絡(luò)的分布式信號(hào)處埋和決策。,4. Mes

4、h網(wǎng)絡(luò)結(jié)構(gòu),2.2 無(wú)線傳感器網(wǎng)絡(luò)覆蓋,2.2.1無(wú)線傳感網(wǎng)絡(luò)覆蓋問(wèn)題 覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)配置首先面臨的基本問(wèn)題，因?yàn)閭鞲衅鞴?jié)點(diǎn)可能任意分布在配置區(qū)域，它反映了一個(gè)無(wú)線傳感器網(wǎng)絡(luò)某區(qū)域被監(jiān)測(cè)和跟蹤的狀況。 在現(xiàn)有的研究成果當(dāng)中，很多都是致力于解決傳感器網(wǎng)絡(luò)的部署和監(jiān)測(cè)及覆蓋與連接的關(guān)系等方面問(wèn)題。另外，也有一些研究致力于特定的應(yīng)用需求，但其核心思想都是與覆蓋問(wèn)題有關(guān)的。,無(wú)線傳感器網(wǎng)絡(luò)覆蓋相關(guān)的

5、兩個(gè)計(jì)算幾何問(wèn)題。 第一個(gè)就是藝術(shù)館問(wèn)題(Art Gallery Problem)。設(shè)想藝術(shù)館的業(yè)主想在館內(nèi)放置照相機(jī)，以便能夠預(yù)防小偷盜竊。關(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)視到。假定相機(jī)可以有3600的視角而且可以極大速度旋轉(zhuǎn)，相機(jī)可以監(jiān)視任何位置，視線不受影響。,1. 無(wú)線傳感器網(wǎng)絡(luò)覆蓋理論基礎(chǔ),問(wèn)題優(yōu)化要實(shí)現(xiàn)的目

6、標(biāo)就是所需相機(jī)的數(shù)目應(yīng)該最小化，在這個(gè)問(wèn)題當(dāng)中，藝術(shù)館通常建模成一個(gè)二維平面的簡(jiǎn)單多邊形。如圖2-7所示是將一個(gè)簡(jiǎn)單多邊形用三角測(cè)量法拆分的例子，放置兩個(gè)監(jiān)視相機(jī)足以覆蓋整個(gè)藝術(shù)館。盡管這個(gè)問(wèn)題在二維平面可以得到最優(yōu)解，然而擴(kuò)展到三維空間，這個(gè)問(wèn)題就變成了NP-hard問(wèn)題了。 圖2-7多邊形的三角測(cè)量法及監(jiān)視相機(jī)的位置配置,,1. 無(wú)線傳感器網(wǎng)絡(luò)覆蓋理論基礎(chǔ),

7、另外一個(gè)與無(wú)線傳感器網(wǎng)絡(luò)覆蓋相關(guān)的幾何問(wèn)題是圓覆蓋問(wèn)題，即在一個(gè)平面上最多需要排列多少個(gè)相同大小的圓，才使其能夠完全覆蓋整個(gè)平面。換個(gè)角度說(shuō)，也就是給定了圓的數(shù)目，如何使得圓的半徑最小。A．Heppes和J．B．M．Melissen實(shí)現(xiàn)了矩形平面的圓最優(yōu)覆蓋問(wèn)題，分為最多用5個(gè)圓和7個(gè)圓來(lái)完成覆蓋兩種情況。如圖2-8所示給出了一個(gè)7個(gè)圓最優(yōu)覆蓋的一個(gè)例子。 圖2-8用7個(gè)圓實(shí)現(xiàn)最優(yōu)覆蓋的樣例,,1. 無(wú)

8、線傳感器網(wǎng)絡(luò)覆蓋理論基礎(chǔ),2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,Andrew Howard等專(zhuān)門(mén)針對(duì)移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)提出了一種增量自我配置的貪婪算法(Creedy and Incremental Self-deployment Algolithm)。算法的基本思想就是每次配置一個(gè)節(jié)點(diǎn)到未知區(qū)域，每個(gè)加入的節(jié)點(diǎn)都充分利用先前配置的節(jié)點(diǎn)收集到的信息來(lái)確定其最佳目標(biāo)位置。算法設(shè)計(jì)的目的就是使網(wǎng)絡(luò)的覆蓋最大化，而同時(shí)又確保節(jié)點(diǎn)彼此保持視距通信，

9、即本地化。 該算法的核心就是貪婪和增量，該算法的復(fù)雜度為 ，其中n 為配置的傳感器節(jié)點(diǎn)數(shù)目。,,A．Howard等提出了基于電勢(shì)場(chǎng)技術(shù)的未知環(huán)境移動(dòng)傳感器網(wǎng)絡(luò)的部署配置方法，網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)可以隨意擴(kuò)展，使得網(wǎng)絡(luò)覆蓋最大化。算法的基本思想就是將傳感器節(jié)點(diǎn)當(dāng)做假想的物粒子，且受到勢(shì)力場(chǎng)的勢(shì)力。勢(shì)力壓迫節(jié)點(diǎn)彼此之間和障礙物之間發(fā)生作用力。通過(guò)節(jié)點(diǎn)的初始簡(jiǎn)易配置快速地在整個(gè)網(wǎng)絡(luò)擴(kuò)散，從而最大化網(wǎng)絡(luò)的覆蓋。

10、該算法的核心就是利用了電勢(shì)場(chǎng)技術(shù)，該算法具有較高的魯棒性和擴(kuò)展性。,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,Huang和Tseng提出了一種基于傳感器數(shù)目的多項(xiàng)式時(shí)間算法，將覆蓋問(wèn)題抽象表述為一個(gè)決策問(wèn)題，并驗(yàn)證了一個(gè)傳感器配置是否提供了k 階覆蓋。該算法的目標(biāo)就是確定無(wú)線傳感器網(wǎng)絡(luò)服務(wù)區(qū)域中的每個(gè)點(diǎn)是否至少被k 個(gè)傳感器節(jié)點(diǎn)監(jiān)視覆蓋。,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,Gupta提出的算法是通過(guò)選擇連接的傳感器節(jié)點(diǎn)路徑來(lái)得到最大化的網(wǎng)絡(luò)覆蓋效

11、果。該算法同時(shí)屬于連接性覆蓋中的連接路徑覆蓋及確定性區(qū)域，點(diǎn)覆蓋類(lèi)型。當(dāng)基站或匯聚中心向無(wú)線傳感器網(wǎng)絡(luò)發(fā)送一個(gè)感應(yīng)區(qū)域查詢(xún)消息時(shí)，連接傳感器覆蓋的目標(biāo)是選擇最小的連接傳感器節(jié)點(diǎn)集合并充分覆蓋無(wú)線傳感器網(wǎng)絡(luò)區(qū)域。 Gupta分別給出了集中與分布式兩種貪婪算法。,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,如圖2-9所示為該貪婪算法執(zhí)行的方式，在如圖2-9(a)所示中，貪婪算法會(huì)選擇路徑P2，得到如圖2-9(b)所示，這是由于在所

12、有備選路徑中選擇B3和B4組成的路徑P2可以覆蓋更多未覆蓋子區(qū)域。 圖2-9連接傳感器網(wǎng)絡(luò)覆蓋的貪婪算法,,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,該連接傳感器網(wǎng)絡(luò)覆蓋的貪婪算法的主要思想是：首先從M 中最新加入的候選節(jié)點(diǎn)開(kāi)始執(zhí)行，在一定范圍內(nèi)廣播候選路徑查找消息，收到候選路徑查找消息的節(jié)點(diǎn)判斷自身是否為候選節(jié)點(diǎn)，如果是，則以單播方式返回發(fā)起者一個(gè)候選路徑響應(yīng)消息。發(fā)起者選擇可以最大化增加覆蓋區(qū)域的候選

13、路徑，更新各參數(shù)，算法繼續(xù)執(zhí)行，直到網(wǎng)絡(luò)查詢(xún)區(qū)域可完全被更新后的M 所覆蓋。,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,無(wú)線傳感器網(wǎng)絡(luò)覆蓋的一般準(zhǔn)則：如已知傳感器節(jié)點(diǎn)的通信距離，可以通過(guò)提出的方法得知所需配置的節(jié)點(diǎn)數(shù)，然后選擇適當(dāng)?shù)母兄采w半徑；同樣如已確定傳感器感知覆蓋半徑，可先計(jì)算出布置的節(jié)點(diǎn)數(shù)，然后選擇合適的通信距離或調(diào)整控制傳感器節(jié)點(diǎn)功率大??；如通信距離和感知覆蓋半徑都確定的情況下，只有增加或減少節(jié)點(diǎn)數(shù)來(lái)滿(mǎn)足給定的最低連接可靠性和成本設(shè)計(jì)要

14、求。,2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,如圖2-10所示給出了一個(gè)無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法和協(xié)議分類(lèi)。,圖2-10無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法和協(xié)議分類(lèi),2．無(wú)線傳感器網(wǎng)絡(luò)覆蓋的計(jì)算,2.2.2無(wú)線傳感網(wǎng)絡(luò)區(qū)域覆蓋,覆蓋問(wèn)題中區(qū)域覆蓋的研究最為廣泛，其主要目的是最大化無(wú)線傳感網(wǎng)絡(luò)覆蓋(監(jiān)測(cè))范圍。圖2-11a為采用隨機(jī)布置策略時(shí)正方形區(qū)域內(nèi)的無(wú)線傳感節(jié)點(diǎn)分布情況。圖中，相互連接的黑色節(jié)點(diǎn)即為當(dāng)前網(wǎng)絡(luò)中的激活節(jié)點(diǎn)。在實(shí)際工作中，無(wú)線傳感節(jié)點(diǎn)的工作狀態(tài)

15、由預(yù)先編制的動(dòng)態(tài)能量管理策略決定。,,1. 能效性隨機(jī)覆蓋方法,無(wú)線傳感網(wǎng)絡(luò)的能效性設(shè)計(jì)能夠延長(zhǎng)無(wú)線傳感網(wǎng)絡(luò)壽命，滿(mǎn)足無(wú)線傳感網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)能耗的限制。通過(guò)規(guī)劃各節(jié)點(diǎn)工作狀態(tài)，在同一時(shí)間段中僅讓部分節(jié)點(diǎn)激活而讓其余冗余節(jié)點(diǎn)盡可能長(zhǎng)時(shí)間的處于休眠狀態(tài)，以節(jié)約網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命。 在設(shè)計(jì)這些機(jī)制的時(shí)候應(yīng)當(dāng)著重考慮以下問(wèn)題： (1)節(jié)點(diǎn)是否進(jìn)入休眠狀態(tài)應(yīng)當(dāng)遵循何種規(guī)則? (2)節(jié)點(diǎn)何時(shí)需要做出決定?

16、 (3)節(jié)點(diǎn)在休眠狀態(tài)需要停留多長(zhǎng)時(shí)間?,目前無(wú)線傳感網(wǎng)絡(luò)覆蓋問(wèn)題的研究通常考慮網(wǎng)絡(luò)隨機(jī)初始化布置時(shí)各節(jié)點(diǎn)的位置和工作狀態(tài)的優(yōu)化問(wèn)題，其目標(biāo)是通過(guò)控制各節(jié)點(diǎn)的位置和工作狀態(tài)提高無(wú)線傳感網(wǎng)絡(luò)的覆蓋和能效性。 由于無(wú)線傳感網(wǎng)絡(luò)中布置的節(jié)點(diǎn)數(shù)量遠(yuǎn)大于監(jiān)測(cè)所需的數(shù)量，因此部分覆蓋算法中將無(wú)線傳感節(jié)點(diǎn)分為若干個(gè)分散集合，每個(gè)集合都可以完整地覆蓋整個(gè)被監(jiān)測(cè)區(qū)域。在監(jiān)測(cè)過(guò)程中，同時(shí)間段內(nèi)有且僅有一個(gè)集合處于工作狀態(tài)，其

17、它集合則進(jìn)入低功耗的休眠狀態(tài)。各集合通過(guò)輪休節(jié)約網(wǎng)絡(luò)能耗。由此可知，通過(guò)最大化可用集合的數(shù)量，可以延長(zhǎng)各節(jié)點(diǎn)切換到工作狀態(tài)的時(shí)間，從而延長(zhǎng)網(wǎng)絡(luò)壽命。,1. 能效性隨機(jī)覆蓋方法,除了將節(jié)點(diǎn)劃分為不同集合外，還可以把測(cè)量區(qū)域劃分成許多地域的集合，使每個(gè)地域集合中的任何一點(diǎn)都被同一個(gè)傳感節(jié)點(diǎn)集合所覆蓋。采用最大約束-最小約束算法能有效計(jì)算這些分散的覆蓋區(qū)域，選擇覆蓋臨界區(qū)域的傳感節(jié)點(diǎn)，并為傳感節(jié)點(diǎn)的布置提供被測(cè)區(qū)域的先驗(yàn)知識(shí)，讓傳感節(jié)點(diǎn)能夠密

18、集布置于未覆蓋區(qū)域，提高網(wǎng)絡(luò)覆蓋率。同時(shí)，還可以通過(guò)非輪值檢測(cè)規(guī)則檢查各節(jié)點(diǎn)監(jiān)測(cè)區(qū)域是否與其周?chē)?jié)點(diǎn)感知區(qū)域相重合，如重合則讓其中部分節(jié)點(diǎn)處于休眠狀態(tài)，這樣也可以有效減少網(wǎng)絡(luò)中工作節(jié)點(diǎn)的數(shù)量，提高網(wǎng)絡(luò)能效性。,1. 能效性隨機(jī)覆蓋方法,基于探針的能效性無(wú)線傳感網(wǎng)絡(luò)動(dòng)態(tài)能量管理策略是另一種常見(jiàn)的無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化方法。該方法首先假設(shè)所有節(jié)點(diǎn)具有相同的感知區(qū)域。在網(wǎng)絡(luò)工作過(guò)程中，每個(gè)無(wú)線傳感節(jié)點(diǎn)將向距離小于r 的所有節(jié)點(diǎn)發(fā)送一條探針消息P

19、RB，所有工作節(jié)點(diǎn)在接收到該消息后返回一條PRB-RPY消息。如果發(fā)出指令的節(jié)點(diǎn)收到至少一條回復(fù)，則節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。范圍r 的選擇由期望工作節(jié)點(diǎn)密度和期望覆蓋冗余度決定。,1. 能效性隨機(jī)覆蓋方法,2. 連接性隨機(jī)覆蓋方法,除了網(wǎng)絡(luò)能效性外，無(wú)線傳感網(wǎng)絡(luò)的連接性也是網(wǎng)絡(luò)性能的重要評(píng)價(jià)指標(biāo)。當(dāng)任一激活節(jié)點(diǎn)都能與其余激活節(jié)點(diǎn)通信時(shí)，網(wǎng)絡(luò)則處于連通狀態(tài)。當(dāng)節(jié)點(diǎn)布置完畢后，網(wǎng)絡(luò)中的節(jié)點(diǎn)必須能夠相互連通，獲取的信息才可以返回接收器或控制器中。保

20、證監(jiān)測(cè)區(qū)域的覆蓋性和節(jié)點(diǎn)的有效連通性對(duì)于確保網(wǎng)絡(luò)測(cè)量性能而言都是十分重要的。以下將介紹幾種用于提高無(wú)線傳感網(wǎng)絡(luò)連接性的隨機(jī)覆蓋方法。,基于以上原理，這里介紹一種分布式最優(yōu)地理密度控制算法(OGDC，Optimal Geographical Density Control)。該算法假設(shè)在任何時(shí)刻，節(jié)點(diǎn)可能處于以下3個(gè)狀態(tài)中的一種：未決定、開(kāi)和關(guān)。網(wǎng)絡(luò)初始化時(shí)，隨機(jī)激活若干個(gè)無(wú)線傳感節(jié)點(diǎn)。而后這些節(jié)點(diǎn)將在網(wǎng)絡(luò)中廣播“能源開(kāi)”的信息，同時(shí)將其

21、自身狀態(tài)設(shè)置為開(kāi)。所傳遞的信息包含兩部分：①發(fā)送者的位置；②下一個(gè)工作節(jié)點(diǎn)的位置與方向。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都保留鄰近節(jié)點(diǎn)的信息列表。,2. 連接性隨機(jī)覆蓋方法,覆蓋結(jié)構(gòu)協(xié)議(CCP，Coverage Configuration Protocol)是另一種用于優(yōu)化網(wǎng)絡(luò)連接性的網(wǎng)絡(luò)協(xié)議。該協(xié)議能動(dòng)態(tài)組織網(wǎng)絡(luò)，為各類(lèi)應(yīng)用提供不同的覆蓋度。為提高算法運(yùn)算速度，每個(gè)節(jié)點(diǎn)都包含周?chē)?jié)點(diǎn)的信息列表，并周期性的發(fā)送信息以廣播自身的位置和狀態(tài)。,2. 連接性

22、隨機(jī)覆蓋方法,兩種算法相結(jié)合后的混合網(wǎng)絡(luò)動(dòng)態(tài)能量管理策略步驟為： ①當(dāng)節(jié)點(diǎn)同時(shí)滿(mǎn)足SPAN和CCP的評(píng)價(jià)標(biāo)準(zhǔn)時(shí)，它由休眠狀態(tài)轉(zhuǎn)變?yōu)榧せ顮顟B(tài)； ②當(dāng)節(jié)點(diǎn)既不滿(mǎn)足SPAN又不滿(mǎn)足CCP評(píng)價(jià)標(biāo)準(zhǔn)時(shí)，節(jié)點(diǎn)由激活狀態(tài)變?yōu)樾菝郀顟B(tài)。 這種混合網(wǎng)絡(luò)動(dòng)態(tài)能量管理策略既能夠通過(guò)CCP方法實(shí)現(xiàn)k覆蓋，又能在SPAN方法的支持下保證單點(diǎn)連接?；贜S-2的仿真結(jié)果顯示，該混合算法在覆蓋比例、工作節(jié)點(diǎn)數(shù)量、系統(tǒng)工作時(shí)間等指標(biāo)

23、上都具有很好的優(yōu)化效果。,2. 連接性隨機(jī)覆蓋方法,2.2.3無(wú)線傳感網(wǎng)絡(luò)的點(diǎn)覆蓋,1．邊界覆蓋模型I當(dāng)前研究的邊界覆蓋問(wèn)題包含兩種邊界覆蓋模型。第一種模型為：在一個(gè)區(qū)域中布置了無(wú)線傳感節(jié)點(diǎn)，已知一個(gè)要穿過(guò)該區(qū)域物體的起始和終止位置，測(cè)定該物體的最大突破路徑(MBP，Maximal Breach Palh)和最大支持路徑(MSP，Maximal Support Path)。MBP和MSP分別與最差和最優(yōu)覆蓋相關(guān)，分別對(duì)應(yīng)于使路

24、徑中的每個(gè)點(diǎn)與最近的無(wú)線傳感節(jié)點(diǎn)之間的距離最大(最小)的情況。實(shí)驗(yàn)證明，MBP位于Voronoi圖線上，MSP位于Delaunay三角測(cè)量線上。,2．邊界覆蓋模型Ⅱ,第二種邊界覆蓋問(wèn)題模型是基于目標(biāo)暴露的模型。該模型假設(shè)當(dāng)測(cè)量距離增加時(shí)無(wú)線傳感器節(jié)點(diǎn)的測(cè)量精度隨之下降，除此之外，測(cè)量時(shí)間(即目標(biāo)暴露時(shí)間)也是一個(gè)很重要的因素。通常測(cè)量時(shí)間越長(zhǎng)，對(duì)應(yīng)的測(cè)量精度也越高。無(wú)線傳感器節(jié)點(diǎn)的二維感知模型可定義為：

25、 (2-1) 式中，d (s，p)為傳感節(jié)點(diǎn)s與點(diǎn)p間的歐式距離； 和k是傳感節(jié)點(diǎn)的相關(guān)參數(shù)。,,,,2.2.5無(wú)線傳感器網(wǎng)絡(luò)覆蓋能效評(píng)價(jià)指標(biāo),1．無(wú)線傳感網(wǎng)絡(luò)的覆蓋指標(biāo)由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)布置的固有冗余性，網(wǎng)絡(luò)覆蓋評(píng)價(jià)采用了可靠度的概念。對(duì)一定區(qū)域，若在t時(shí)刻處于n個(gè)節(jié)點(diǎn)測(cè)量范圍內(nèi)，該區(qū)域綜合可靠度表示為 　　　　　　　　　

26、 (2-4) 式中，ri (t)表示第i個(gè)節(jié)點(diǎn)的測(cè)量可靠度。,,2．無(wú)線傳感器網(wǎng)絡(luò)的能耗指標(biāo),無(wú)線信號(hào)在傳播過(guò)程中隨著傳播距離增加而發(fā)生衰減，采用自由空間模型計(jì)算傳播損耗如下： 　　　　　　　　　　 (2-5) 式中，Lp為路徑損耗；D為傳播距離；為信號(hào)波長(zhǎng)。針對(duì)無(wú)線信號(hào)傳播過(guò)程，假設(shè)無(wú)線傳感器網(wǎng)絡(luò)通信能耗模型為：運(yùn)行發(fā)送器或接收器

27、的無(wú)線花費(fèi)為Eelec=50nJ/bit，發(fā)送放大器實(shí)現(xiàn)容許放大倍率的無(wú)線花費(fèi)為Eamp=100pJ/bit m-2。二維空間內(nèi)，坐標(biāo)分別為(xi，yi)、(xj，yj)的無(wú)線傳感節(jié)點(diǎn)i、j，通信時(shí)信號(hào)傳播距離計(jì)算如下： (2-6),,,若節(jié)點(diǎn)i向j發(fā)送長(zhǎng)度為k bit的數(shù)據(jù)包，則節(jié)點(diǎn)i能耗為：　　　　　

28、 (2-7)節(jié)點(diǎn)j接收此數(shù)據(jù)包的能耗為： 　　　　　　　　　　　　 (2-8) 節(jié)點(diǎn)i與j節(jié)點(diǎn)，進(jìn)行一次數(shù)據(jù)包傳輸所消耗的總能量為：　 　　　　　　　　　 (2-9) 式(2-9)說(shuō)明兩節(jié)點(diǎn)相距較遠(yuǎn)時(shí)，直接傳輸數(shù)據(jù)會(huì)消耗較大能量，采用多跳通信則可節(jié)省能量。,,,,2．

29、無(wú)線傳感器網(wǎng)絡(luò)的能耗指標(biāo),2.3無(wú)線傳感網(wǎng)絡(luò)連接可靠性,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析 對(duì)于無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)，通常會(huì)遇到兩個(gè)關(guān)鍵問(wèn)題：①在給定布置區(qū)域大小和節(jié)點(diǎn)無(wú)線收發(fā)距離(即通信半徑R)的條件下，究竟要布置多少個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)才能連通一個(gè)網(wǎng)絡(luò)，且連接的可靠性能滿(mǎn)足多大的需求；②給定節(jié)點(diǎn)感知覆蓋距離(即感知距離半徑)的條件下，如何布置節(jié)點(diǎn)才能實(shí)現(xiàn)對(duì)給定區(qū)域的有效覆蓋和監(jiān)測(cè)。,無(wú)線傳感器網(wǎng)絡(luò)連接可靠性是一個(gè)穩(wěn)定運(yùn)行的

30、無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)必須面臨的基本問(wèn)題，通常有兩種主要的理論研究方法和途徑：一種是基于圖的連接性；另外一種是基于擴(kuò)散理論的連接性。通常無(wú)線傳感器網(wǎng)絡(luò)用連接概率來(lái)表示網(wǎng)絡(luò)的連接性，而用每個(gè)節(jié)點(diǎn)鄰居數(shù)不低于某個(gè)特定值來(lái)表示網(wǎng)絡(luò)的連接可靠性需求。這里定義網(wǎng)絡(luò)連接度為在其通信傳輸距離范圍內(nèi)的平均鄰居節(jié)點(diǎn)數(shù)，鄰居節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)連接度越強(qiáng)。網(wǎng)絡(luò)的連接性是和網(wǎng)絡(luò)連接度成某種分布關(guān)系的。網(wǎng)絡(luò)連接度CD (Connection Degree)參數(shù)可

31、反映網(wǎng)絡(luò)的連接性。,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析,為簡(jiǎn)化模型，假設(shè)無(wú)線傳感器網(wǎng)絡(luò)是采用全向天線情況下的同構(gòu)網(wǎng)絡(luò)，傳輸通信半徑為R，感知覆蓋距離半徑為R’，實(shí)際網(wǎng)絡(luò)配置區(qū)域?yàn)榈木匦螏顓^(qū)域，這樣CD就集中反映了傳感器節(jié)點(diǎn)數(shù)n、實(shí)際物理布置區(qū)域大小以及每個(gè)節(jié)點(diǎn)的無(wú)線傳輸通信半徑R三種因素的相互關(guān)系，D表示節(jié)點(diǎn)密度，L和W分別表示矩形域的長(zhǎng)和寬。,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析,值得注意的是，無(wú)線網(wǎng)絡(luò)特有的隱藏或暴露終端問(wèn)題產(chǎn)生

32、的節(jié)點(diǎn)干擾距離半徑R’(感知距離半徑)通常滿(mǎn)足條件R<R’<2R，如公式2-10所示。網(wǎng)絡(luò)連接度和同頻干擾會(huì)隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加而增強(qiáng)，同樣增大通信距離范圍或減小網(wǎng)絡(luò)布置區(qū)域大小也會(huì)增大網(wǎng)絡(luò)連接度和同頻干擾。因此，選擇適當(dāng)?shù)木W(wǎng)絡(luò)連接度對(duì)網(wǎng)絡(luò)性能有著重要的意義。 (2-10),,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析,影響無(wú)線傳感器網(wǎng)

33、絡(luò)可靠連接的另一個(gè)重要參數(shù)為網(wǎng)絡(luò)的冗余度。不考慮鏈路相互干擾等情況，冗余度K越高，網(wǎng)絡(luò)的連接性越強(qiáng)。從幾何拓?fù)鋵W(xué)觀點(diǎn)，定義網(wǎng)絡(luò)的冗余度是指在無(wú)窮維節(jié)點(diǎn)陣列空間連接的鏈路節(jié)點(diǎn)比。 如圖2-23所示，圖2-23(a)中表示連接性最弱的冗余度K=1，例如一個(gè)環(huán)狀或線性網(wǎng)絡(luò)。網(wǎng)格網(wǎng)絡(luò)冗余度可以是K=1.5，2，3，4等，如圖2-13(b)～(e)所示。,,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析,通過(guò)網(wǎng)格擴(kuò)散(Percolation)

34、方法給出了冗余度如何影響連接性的一個(gè)很有效的估計(jì)?？紤]包含100個(gè)節(jié)點(diǎn)的對(duì)稱(chēng)拓?fù)渚W(wǎng)絡(luò)。暫不管擴(kuò)散的方向和路徑如何，僅考慮最大連接節(jié)點(diǎn)數(shù)目所占比例Cmax與單個(gè)鏈路故障概率Pd的關(guān)系，在給定某個(gè)冗余度K，如K=1，2，3和4，可以得到Cmax與單個(gè)鏈路故障概率Pd之間的變化關(guān)系，如圖2-14所示。,,2.3.1無(wú)線傳感網(wǎng)絡(luò)連接可靠性分析,2.3.2基于概率和圖論的連接可靠性,在圖論中，通常根據(jù)圖頂點(diǎn)之間的邊的連接情況，將圖分為有向圖和無(wú)向

35、圖兩種。無(wú)向圖是指在圖的頂點(diǎn)與頂點(diǎn)之間存在的邊是無(wú)向邊。由于網(wǎng)絡(luò)拓?fù)涞牟淮_定性，可將無(wú)線傳感器網(wǎng)絡(luò)抽象成一個(gè)隨機(jī)的無(wú)向圖Gp(n)，其中n為圖中的頂點(diǎn)數(shù)(表示傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù))，p為任意兩個(gè)節(jié)點(diǎn)之間的連接概率。在隨機(jī)無(wú)向圖Gp(n)中，鏈路之間的連接是相互獨(dú)立的事件。節(jié)點(diǎn)的度定義為與節(jié)點(diǎn)直接相連接的節(jié)點(diǎn)數(shù)目，即節(jié)點(diǎn)的直接鄰居數(shù)。圖Gp(n)中，節(jié)點(diǎn)的度服從二項(xiàng)分布：

36、 (2-11) 式中，z為平均節(jié)點(diǎn)度，即z=E[d]=(n-1)p；右式為節(jié)點(diǎn)數(shù)n較大時(shí)的泊松近似結(jié)果。,,2.3.3基于擴(kuò)散理論的連接可靠性,如圖2-15所示，這是由許多正方形格子組成的區(qū)域Z2，每個(gè)格子隨機(jī)被小圓點(diǎn)填充占據(jù)，格子被占據(jù)的概率為p，這樣整個(gè)區(qū)域會(huì)形成許多格子簇(Cluster)。簇是由相鄰的被小圓點(diǎn)占據(jù)的格子組成的，相鄰的格子之間有一條公共邊。擴(kuò)散理論(Percolation)就是對(duì)簇的數(shù)目和特性進(jìn)行研究的

37、理論。,,關(guān)于擴(kuò)散理論有以下兩個(gè)理論模型。1．?dāng)U散理論中的布爾模型節(jié)點(diǎn)按照泊松點(diǎn)過(guò)程分布。當(dāng)兩個(gè)節(jié)點(diǎn)間的距離小于等于發(fā)射半徑時(shí)，能夠相互連接。因此，在一維網(wǎng)絡(luò)中，如泊松點(diǎn)過(guò)程為半徑為r/2的圓的中心，兩節(jié)點(diǎn)間的距離按指數(shù)分布，則不存在擴(kuò)散現(xiàn)象。,2.3.3基于擴(kuò)散理論的連接可靠性,當(dāng)給定r和時(shí)，距離為x的兩節(jié)點(diǎn)連接的概率為:

38、 (2-13) 從式(2-13)可知，隨著x增加，兩節(jié)點(diǎn)間的連接概率按指數(shù)規(guī)律下降。如果在二維網(wǎng)絡(luò)中有下面的定理：定理3：對(duì)于給定的r，存在臨界的節(jié)點(diǎn)密度 ，且當(dāng)節(jié)點(diǎn)密度 時(shí)，網(wǎng)絡(luò)由無(wú)限個(gè)有限簇組成，即網(wǎng)絡(luò)不連接；當(dāng)節(jié)點(diǎn)密度 時(shí)，網(wǎng)絡(luò)由唯

39、一的無(wú)限簇組成，則網(wǎng)絡(luò)全連接。,,,,,1．?dāng)U散理論中的布爾模型,擴(kuò)散理論中信噪比圖模型STIRG (Signal To Interference Radio Graph)定義為：如果節(jié)點(diǎn)j收到從節(jié)點(diǎn)i發(fā)送的信號(hào)信噪比大于某個(gè)門(mén)限制 ，則節(jié)點(diǎn)j將能接收到從節(jié)點(diǎn)i發(fā)送來(lái)的數(shù)據(jù)： (2-14) 式中， 為干擾因子，N0為熱

40、噪聲。,2．?dāng)U散理論中的STIRG模型,當(dāng) 時(shí)，即無(wú)干擾情況下，節(jié)點(diǎn)能與某一固定范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信(與節(jié)點(diǎn)發(fā)射功率有關(guān))，則存在臨界節(jié)點(diǎn)密度 (與布爾模型相同)。 當(dāng) 時(shí)，由于存在干擾，網(wǎng)絡(luò)圖中會(huì)形成許多節(jié)點(diǎn)數(shù)目較少的簇，從而導(dǎo)致網(wǎng)絡(luò)不連接或連接較差。因此干擾因子 存在臨界值 。當(dāng) ，則可能存在擴(kuò)散現(xiàn)象；當(dāng) 時(shí)，無(wú)論節(jié)點(diǎn)密度如何，網(wǎng)絡(luò)中不存在擴(kuò)散現(xiàn)象，即網(wǎng)絡(luò)不連接。,