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

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

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

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

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

5、兩個計算幾何問題。 第一個就是藝術(shù)館問題(Art Gallery Problem)。設(shè)想藝術(shù)館的業(yè)主想在館內(nèi)放置照相機，以便能夠預(yù)防小偷盜竊。關(guān)于實現(xiàn)這個想法存在兩個問題需要回答：首先就是到底需要多少臺相機；其次，這些相機應(yīng)當(dāng)放置在哪些地方才能保證館內(nèi)每個點至少被一臺相機監(jiān)視到。假定相機可以有3600的視角而且可以極大速度旋轉(zhuǎn)，相機可以監(jiān)視任何位置，視線不受影響。,1. 無線傳感器網(wǎng)絡(luò)覆蓋理論基礎(chǔ),問題優(yōu)化要實現(xiàn)的目

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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