無線傳感網(wǎng)絡第七章

1、第7章,無線傳感器網(wǎng)絡的路由協(xié)議,7.1 路由協(xié)議概述,7.1.1無線傳感器網(wǎng)絡路由協(xié)議的考慮因素 設計無線傳感器網(wǎng)絡的路由要考慮的因素很多，大致分為以下兩種類型。 (1)網(wǎng)絡特征：無線傳感器網(wǎng)絡具有與眾不同的特征，應用于路由協(xié)議設計時，主要應該考慮能量損耗、節(jié)點部署和網(wǎng)絡拓撲變化。(2)數(shù)據(jù)傳輸特征：無線傳感器網(wǎng)絡的數(shù)據(jù)采集和傳輸要求與其他網(wǎng)絡不同，因此路由協(xié)議設計時也需要加以區(qū)別，主要考慮數(shù)據(jù)傳輸方式、無線傳輸手

2、段以及數(shù)據(jù)融合技術等。,7.1.2路由的過程,無線傳感器網(wǎng)絡的路由過程主要分為以下4個步驟： ①某一個設備發(fā)出路由請求命令幀，啟動路由發(fā)現(xiàn)過程； ②對應的接收設備收到該命令后，回復應答命令幀； ③對潛在的各條路徑開銷(跳轉次數(shù)、延遲時間)，進行評估比較； ④將評估確定之后的最佳路由記錄添加到此路徑上各個設備的路由表中。,7.1.3無線傳感器網(wǎng)絡路由協(xié)議分類方法,1．按源節(jié)點獲取路徑的方法主動路由

3、協(xié)議、按需路由協(xié)議 、混合路由協(xié)議2．按節(jié)點參與通信的方式直接通信路由協(xié)議、平面路由協(xié)議、層次路由協(xié)議3．按路由的發(fā)現(xiàn)過程 以位置信息為中心的路由協(xié)議、以數(shù)據(jù)為中心的路由協(xié)議4．按路由選擇是否考慮服務質量(QoS)約束 保證QoS的路由協(xié)議是指在路由建立時，考慮時延、丟包率等QoS參數(shù)，從多條可行的路由中選擇一條最適合QoS應用要求的路由；或者根據(jù)業(yè)務類型，保證滿足不同業(yè)務需求的QoS路由協(xié)議。,7.2 平面路由協(xié)議

4、7.2.1 Flooding and Grossing協(xié)議,1. 洪泛路由協(xié)議洪泛路由協(xié)議(Flooding Protocol)是一種最早的路由協(xié)議，接收到消息的節(jié)點以廣播的轉發(fā)報文給所有的鄰居節(jié)點， (如圖7-1,2所示)。,2. 閑聊法閑聊法(Grossing)是洪泛法的改進版本。如圖7-3所示,洪泛路由協(xié)議,洪泛路由算法是一個簡單有效的路由算法，其基本思想是每個節(jié)點都是用廣播轉發(fā)收到的數(shù)據(jù)分組，若收到重復分組則進行丟

5、棄處理。洪泛協(xié)議會導致數(shù)據(jù)分組以源節(jié)點為中心進行擴散，為了不造成大面積的擴散占用過多的網(wǎng)絡資源以及使擴散收斂，需要設定合適的TTL值（IP包被路由器丟棄之前允許通過的最大網(wǎng)段數(shù)量），保證數(shù)據(jù)分組只經過有限跳路由；此外為了進行重復分組檢測，每個節(jié)點需要維護一個數(shù)據(jù)分組序號SEQ和一張路由表，源節(jié)點每發(fā)送一個數(shù)據(jù)分組則將SEQ增1，并將該SEQ添加到數(shù)據(jù)分組的IP頭部，其余節(jié)點收到數(shù)據(jù)分組后會將該SEQ記錄到路由表并根據(jù)該SEQ進行重復分

6、組檢測。,洪泛路由協(xié)議,洪泛算法最大的問題是會產生大量的重復分組，占用網(wǎng)絡資源，使路由器和鏈路的資源過于浪費，以致效率很低。但是洪泛路由算法是一個最簡單和最可靠的路由算法，在節(jié)點運動劇烈、進出網(wǎng)絡頻繁變化的場景下，全網(wǎng)洪泛是有效的方式，其具有極好的健壯性，可用于軍事應用，也可以作為衡量標準評價其他的路由算法。,Grossing（閑聊）路由協(xié)議,Grossing（閑聊）路由協(xié)議在Flooding協(xié)議的基礎上進行了改進，節(jié)點對于產生或收到的

7、數(shù)據(jù)并不是無條件轉發(fā)，而是隨機轉發(fā)，因此在一定程度上解決了Flooding協(xié)議廣播風暴的問題。但是隨機轉發(fā)數(shù)據(jù)增加了信息傳輸?shù)钠骄鶗r延，導致傳輸速度變慢，并且無法解決部分交疊和盲目利用資源問題。,7.2.2 SPIN協(xié)議,基于協(xié)商機制的傳感器網(wǎng)絡SPIN協(xié)議(Sensor Protocols for Information via Negotiation)是一種以數(shù)據(jù)為中心的白適應通信方式，使用3種類型的信息進行通信，即ADV、REQ和

8、DATA信息。圖7-4表示了SPIN協(xié)議的工作過程。,SPIN協(xié)議的缺點是沒有考慮節(jié)能和多種信道條件下的數(shù)據(jù)傳輸問題。因此，后續(xù)又出現(xiàn)了SPIN-PP (Point to Point，點到點的通信模式)、SPIN-EC (Energy Control，點到點模式下的節(jié)能路由)、SPIN-RL (Route Lossy，點到點通信中的信道衰減模式)、SPIN-BC (Broadcast Channel，廣播信道模式)等在SPIN基礎上改進

9、的路由協(xié)議。,7.2.3 SAR、DD和MCFA協(xié)議,1．SAR協(xié)議順序分配路由SAR協(xié)議(Sequential Assignment Routing)是第一個具有QoS意識的路由協(xié)議。該協(xié)議通過構建以Sink的單跳鄰居節(jié)點為根節(jié)點的多播樹來實現(xiàn)傳感器節(jié)點到Sink節(jié)點的多跳路徑。2．DD協(xié)議定向擴散路由DD協(xié)議(Directed Diffusion)是一種以數(shù)據(jù)為中心的信息傳播協(xié)議，與已有的路由算法有著截然不同的實現(xiàn)機制

10、。3．MCFA協(xié)議 最小開銷前行算法MCFA協(xié)議(Minimum Cost For warding Algorithm for Large Sensor Networks)充分利用了傳感器網(wǎng)絡中的數(shù)據(jù)傳輸不對稱的特點，即大多的數(shù)據(jù)流都是從傳感器節(jié)點向Sink節(jié)點的方向傳輸。,7.2.3 SAR、DD和MCFA協(xié)議,1．SAR協(xié)議順序分配路由SAR協(xié)議(Sequential Assignment Routing)是

11、第一個具有QoS意識的路由協(xié)議。該協(xié)議通過構建以Sink的單跳鄰居節(jié)點為根節(jié)點的多播樹來實現(xiàn)傳感器節(jié)點到Sink節(jié)點的多跳路徑。2．DD協(xié)議定向擴散路由DD協(xié)議(Directed Diffusion)是一種以數(shù)據(jù)為中心的信息傳播協(xié)議，與已有的路由算法有著截然不同的實現(xiàn)機制。3．MCFA協(xié)議 最小開銷前行算法MCFA協(xié)議(Minimum Cost For warding Algorithm for Large S

12、ensor Networks)充分利用了傳感器網(wǎng)絡中的數(shù)據(jù)傳輸不對稱的特點，即大多的數(shù)據(jù)流都是從傳感器節(jié)點向Sink節(jié)點的方向傳輸。,7.3 層次路由協(xié)議,7.3.1 LEACH 低功耗自適應聚類分級LEACH協(xié)議(LOW Energy Adaptive Clustering Hierarchy)是無線傳感器網(wǎng)絡中最早提出的分層路由算法。LEACH可以將網(wǎng)絡整體生存時間延長15％，其基本思想是通過隨機循環(huán)地選擇簇頭節(jié)點將整個網(wǎng)

13、絡的能量負載平均分配到每個傳感器節(jié)點中，從而降低網(wǎng)絡能源消耗，提高網(wǎng)絡整體生存時間。,7.3 層次路由協(xié)議,LEACH在運行過程中不斷的循環(huán)執(zhí)行簇的重構過程，每個簇重構過程可以用回合的概念來描述。每個回合可以分成兩個階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。為了節(jié)省資源開銷，穩(wěn)定階段的持續(xù)時間要大于建立階段的持續(xù)時間。簇的建立過程可分成4個階段：簇頭節(jié)點的選擇、簇頭節(jié)點的廣播、簇頭節(jié)點的建立和調度機制的生成。簇頭節(jié)點的選擇依據(jù)網(wǎng)絡中所需

14、要的簇頭節(jié)點總數(shù)和迄今為止每個節(jié)點已成為簇頭節(jié)點的次數(shù)來決定。具體的選擇辦法是：每個傳感器節(jié)點隨機選擇0-1之間的一個值。如果選定的值小于某一個閾值，那么這個節(jié)點成為簇頭節(jié)點。選定簇頭節(jié)點后，通過廣播告知整個網(wǎng)絡。網(wǎng)絡中的其他節(jié)點根據(jù)接收信息的信號強度決定從屬的簇，并通知相應的簇頭節(jié)點，完成簇的建立。最后，簇頭節(jié)點采用TDMA方式為簇中每個節(jié)點分配向其傳遞數(shù)據(jù)的時間點。穩(wěn)定階段中，傳感器節(jié)點將采集的數(shù)據(jù)傳送到簇頭節(jié)點。簇頭節(jié)點對簇中

15、所有節(jié)點所采集的數(shù)據(jù)進行信息融合后再傳送給匯聚節(jié)點，這是一種較少通信業(yè)務量的合理工作模型。穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡重新進入簇的建立階段，進行下一回合的簇重構，不斷循環(huán)，每個簇采用不同的CDMA代碼進行通信來減少其他簇內節(jié)點的干擾。,LEACH協(xié)議特點,1 為了減少傳送到匯聚節(jié)點的信息數(shù)量，簇首節(jié)點負責融合來自簇內不同源節(jié)點所產生的數(shù)據(jù)，并將融合后的數(shù)據(jù)發(fā)送到匯聚點。2 LEACH采用基于TDMA/CDMA的MAC層機制來減少簇內和

16、簇間的沖突。3 由于數(shù)據(jù)采集是集中的和周期性的，因此該協(xié)議非常適合于要求連續(xù)監(jiān)控的應用系統(tǒng)。4 對于終端使用者來說，由于它并不需要立即得到所有的數(shù)據(jù)，因此協(xié)議不需要周期性的傳輸數(shù)據(jù)，這樣可以達到限制傳感器節(jié)點能量消耗的目的。5 在給定的時間間隔后，協(xié)議重新選舉簇首節(jié)點，以保證無線傳感器網(wǎng)絡獲取統(tǒng)一的能量分布。,LEACH局限性,1 由于LEACH假定所有節(jié)點能夠與匯聚節(jié)點直接通信，并且每個節(jié)點都具備支持不同MAC協(xié)議的計算能力，因

17、此該協(xié)議不適合在大規(guī)模的無線傳感器網(wǎng)絡中應用。2 協(xié)議沒有說明簇頭節(jié)點的數(shù)目怎么分布才能及于整個網(wǎng)絡。因此，很可能出現(xiàn)被選的簇頭節(jié)點集中在網(wǎng)絡某一區(qū)域的現(xiàn)象，這樣就會使得一些節(jié)點的周圍沒有任何簇頭節(jié)點。3 由于LEACH假定在最初的簇頭選擇回合中，所有的節(jié)點都攜帶相同的能量，并且每個成為簇頭的節(jié)點都消耗大致相同的能量。因此，協(xié)議不適合節(jié)點能量不均衡的網(wǎng)絡。,7.3.2 PEGASIS,高能效采集傳感器信息系統(tǒng)PEGASIS協(xié)議(Po

18、wer　Efficient Gathering in Sensor Information Systems)是在LEACH協(xié)議上提出的一種改進路由算法。PEGASIS路由協(xié)議在網(wǎng)絡中選擇一個節(jié)點作為起始節(jié)點建立一條最優(yōu)回路鏈，起始節(jié)點將數(shù)據(jù)融合后的數(shù)據(jù)信息發(fā)送給Sink節(jié)點。由于起始節(jié)點的負載較重，PEGASIS采用了全網(wǎng)節(jié)點輪流作為回路鏈起始節(jié)點的方式來進行均衡。 該路由協(xié)議中使用了貪婪算法(Greedy Algorit

19、hm)來形成鏈，如圖7-5所示。在每一輪通信之前才形成鏈。為確保每個節(jié)點都有其相鄰節(jié)點，從離基站最遠的節(jié)點開始構建，鏈中鄰居節(jié)點的距離會逐漸增大，因為已經在鏈中的節(jié)點不能被再次訪，當其中一個節(jié)點失效時，鏈必須重構。,7.3.3 TEEN,閾值敏感的高效傳感器網(wǎng)絡TEEN協(xié)議(Threshold Sensitive Energy Efficient Sensor Network)，是一個基于簇群的路由協(xié)議，也是由LEACH發(fā)展而來，在這個

20、協(xié)議中定義了硬門限和軟門限兩個概念。 這個算法適用于實時性要求較高的應用場合，用戶可以及時獲取感興趣的信息。由于感應數(shù)據(jù)所耗能量比傳輸數(shù)據(jù)所耗能量要少得多，雖然節(jié)點一直處于感應狀態(tài)，但是由于減少了很多不必要的數(shù)據(jù)傳輸，因此相對來說還是節(jié)能的。該協(xié)議也有一些不足之處： ①門限值達不到，節(jié)點就永遠不會和簇頭節(jié)點通信，用戶就無法從網(wǎng)絡得到任何數(shù)據(jù)，即使節(jié)點已經死亡，用戶也不知情； ②TDMA機制的運用保證了群

21、中不會出現(xiàn)數(shù)據(jù)沖撞的情況，但是如果一個節(jié)點沒有數(shù)據(jù)要發(fā)送的話，屬于它的時隙就浪費掉了，而其他節(jié)點卻還在等待自己的時隙，這樣會向系統(tǒng)中引入過多的時延，不適于實時性要求太高的場合； ③沒有相應的機制去區(qū)分那些沒有感應到足夠大變化的節(jié)點和處于關閉狀態(tài)的節(jié)點。群頭節(jié)點的接收機要時刻處于激活狀態(tài)，以便接收任何時候由成員節(jié)點傳來的數(shù)據(jù)，在某種程度上增加了簇頭節(jié)點的負擔。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,1．APTEEN

22、APTEEN (Adaptive Periodic TEEN)協(xié)議是對TEEN的擴展，它是一種結合響應型和主動型傳感器網(wǎng)絡策略的混合型網(wǎng)絡路由協(xié)議，可以根據(jù)用戶需要和應用類型來設定協(xié)議的周期性和相關閥值，即可以周期性采集數(shù)據(jù)又可以對突發(fā)事件作出快速反應。APTEEN在TEEN的基礎上定義了一個計數(shù)時間，當節(jié)點從上一次發(fā)送數(shù)據(jù)開始經歷這個計數(shù)時間還沒有發(fā)送數(shù)據(jù)，那么不管當前的數(shù)據(jù)是否滿足軟、硬門限的要求都會發(fā)送這個數(shù)據(jù)。APTEEN

23、可以通過改變計數(shù)時間來控制能量消耗。,2．TTDD 雙列數(shù)據(jù)分發(fā)TTDD(TWO-Tier Data Dissemination)，協(xié)議假設節(jié)點靜態(tài)，且各節(jié)點的位置信息已知。網(wǎng)絡中可以存在多個Sink節(jié)點，Sink節(jié)點可以在網(wǎng)絡中任意移動。網(wǎng)絡中的節(jié)點以虛擬柵格的形式劃分為若干區(qū)域，當監(jiān)測區(qū)域發(fā)生事件，附近的多個節(jié)點將選擇一個節(jié)點觸發(fā)數(shù)據(jù)上報消息。發(fā)送數(shù)據(jù)上報消息的簇頭節(jié)點將上報報文發(fā)送給柵格外的其他4個柵格的鄰接節(jié)點，由鄰接

24、節(jié)點轉發(fā)給該柵格的另外3個鄰接節(jié)點，最后將上報的數(shù)據(jù)報文發(fā)送到每一個柵格。這樣無論Sink節(jié)點移動到網(wǎng)絡中的任何地方，都能夠從距離最近的節(jié)點上收到上報的數(shù)據(jù)報文。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,3．EARSN 簇頭固定的分簇結構路由協(xié)議EARSN (Energy Aware Routing for Cluster Based Sensor Network)是基于三層體系結構的路由協(xié)議。該協(xié)議要求網(wǎng)絡運行前

25、由終端用戶將傳感器節(jié)點劃分成簇，并通知每個簇頭節(jié)點的ID標識和簇內所分配節(jié)點的位置信息。傳感器節(jié)點可以以活動方式和備用的低能源方式兩種方式運行，并可以感知、轉發(fā)、感知并轉發(fā)和休眠4種方式之一存在。與其他路由協(xié)議不同的是，該協(xié)議的簇頭不受能量的限制。它作為網(wǎng)絡的中心管理者，可以監(jiān)控節(jié)點的能量變化，決定并維護傳感器的4種狀態(tài)。算法依據(jù)兩個節(jié)點間的能量消耗、延遲最優(yōu)化等性能指標計算路徑代價函數(shù)。簇頭節(jié)點利用代價函數(shù)作為鏈路成本，選擇最小成本的

26、路徑作為節(jié)點與其通信的最優(yōu)路徑。經仿真分析，該協(xié)議在運行過程中具有很好的節(jié)能性、較高的吞吐量和較低的通信延遲。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,表7-1為各種協(xié)議之間的簡單對比，主要從移動性、能量需求、路徑長度、擴展性、路由狀態(tài)復雜度、計算和通信所需開銷、數(shù)據(jù)融合技術等多方面進行了分析比較。,7.3.5 平面路由協(xié)議和層次路由協(xié)議比較,總體來看，由于網(wǎng)絡結構的不同，平面路由和層次路由體現(xiàn)出了以下幾處差異。 ①

27、移動性 ②能量使用 ③路由選擇 ④可拓展性 ⑤開銷,7.3.5 平面路由協(xié)議和層次路由協(xié)議比較,7.4 能量感知路由,7.4.1 能量消耗源 1．通信相關的能量消耗 通信相關的能耗包括對傳輸器、中轉器和接收器的使用。 2．計算相關的能量消耗 計算相關的能耗主要涉及協(xié)議的處理，主要包括對CPU、主要存儲器、一個很小的外設、磁盤或其他一些組成部分的使用。同樣的，數(shù)

28、據(jù)壓縮技術在減少數(shù)據(jù)包長度的同時也因為計算量的增大而增加了能量消耗。,7.4.2能量路由,在如圖7-6所示的網(wǎng)絡中，源節(jié)點是一般功能的傳感器節(jié)點，完成數(shù)據(jù)采集工作。匯聚節(jié)點是數(shù)據(jù)發(fā)送的目標節(jié)點。大寫字母表示節(jié)點，如節(jié)點A，節(jié)點右側括號內的數(shù)字表示節(jié)點的可用能量。圖中的雙向線表示節(jié)點之間的通信鏈路，鏈路上的數(shù)字表示在該鏈路上發(fā)送數(shù)據(jù)消耗的能量。在圖中，從源節(jié)點到匯聚節(jié)點的可能路徑有4條。,,路徑1：源節(jié)點—B—A—匯聚節(jié)點，路徑上所有節(jié)

29、點PA之和為4，在該路徑上發(fā)送分組需要的能量之和為3； 路徑2：源節(jié)點—C—B—A—匯聚節(jié)點，路徑上所有節(jié)點PA之和為6，在該路徑上發(fā)送分組需要的能量之和為6； 路徑3：源節(jié)點—D—匯聚節(jié)點，路徑上所有節(jié)點PA之和為3，在該路上發(fā)送分組需要的能量之和為4； 路徑4：源節(jié)點—F—E—匯聚節(jié)點，路徑上所有節(jié)點PA之和為5，在該路徑上發(fā)送分組需要的能量之和為6。 能量路由選擇策略主要有以下幾種：最大可用能量路由

30、、最小能量消耗路由、最少跳數(shù)路由和最大最小PA節(jié)點路由。,7.4.3能量多路徑路由,能量多路徑路由的主要流程描述如下： (1)發(fā)起路徑建立 (2)判斷是否轉發(fā)路徑建立消息 (3)計算能量代價 (4)節(jié)點加入路徑條件 (5)節(jié)點選擇概率計算 (6)代價平均值計算,7.5基于查詢的路由,基于查詢的路由協(xié)議，在需要不斷查詢傳感器節(jié)點采集的數(shù)據(jù)

31、的應用中，通信流量主要產生于查詢節(jié)點和傳感器節(jié)點之間的命令和數(shù)據(jù)傳輸，同時傳感器節(jié)點的采樣信息在傳輸路徑上通常要進行數(shù)據(jù)融合，通過減少通信流量來節(jié)省能量。,7.5.1定向擴散路由,定向擴散(Directed Diffusion，DD)是一種基于查詢的路由機制，是專門為無線傳感器網(wǎng)絡設計的。 定向擴散路由機制包括周期性的興趣擴散、梯度建立、數(shù)據(jù)傳播、路徑加強等階段 。 1．興趣擴散階段 2．梯度建立階段

32、 3．數(shù)據(jù)傳播階段 4．路徑加強階段,DD路由算法,該算法實現(xiàn)的過程包括三個階段：興趣擴散，梯度建立以及路徑加強 ?！　∨d趣擴散：Sink節(jié)點查詢興趣消息，興趣消息采用泛洪的方法傳播到網(wǎng)絡，來通知整個網(wǎng)絡中的其他節(jié)點它需要的信息。 　　梯度建立：在興趣消息擴散的同時相應的路由路經也建立完成。有“興趣消息”相關數(shù)據(jù)的普通節(jié)點將自己采集的數(shù)據(jù)通過建立好的路徑傳送到Sink節(jié)點。 

33、　　路徑加強：最后sink節(jié)點選擇一條最優(yōu)路徑作為強化路徑。優(yōu)點： 　　數(shù)據(jù)中心路由，定義不同任務類型/目標區(qū)域消息； 　　路徑加強機制可顯著提高數(shù)據(jù)傳輸?shù)乃俾剩?#160;　　周期性路由：能量的均衡消耗； 缺點： 　　周期性的洪泛機制---能量和時間開銷都比較大； 　　節(jié)點需要維護一個興趣消息列表，代價較大； 　　不能用于大規(guī)模的網(wǎng)絡以及網(wǎng)絡拓撲結構不斷變化的

34、網(wǎng)絡。,7.5.2謠傳路由,謠傳路由(Rumor Routing)，其路由的建立是由Sink節(jié)點和源節(jié)點共同發(fā)起并完成的。謠傳路由的原理如圖7-8所示。,謠傳路由協(xié)議的執(zhí)行過程如下： ①每個傳感器節(jié)點維護一個鄰居列表和一個事件列表。 ②當傳感器節(jié)點在本地檢測到一個事件時，就在事件列表中增加一個表項，設置相關的事件名稱、跳數(shù)等，同時根據(jù)一定的概率產生一個代理消息。代理消息是一個包含生命期等事件信息的分組，用來攜帶相關的信息

35、通告給它傳輸經過的每一個傳感器節(jié)點。,③網(wǎng)絡的任何節(jié)點都可以對一個特定的事件生成查詢消息。 ④若查詢消息和代理消息的路徑出現(xiàn)交叉的情況，交叉節(jié)點會沿著查詢消息的反方向將事件信息傳送到查詢節(jié)點。如果查詢節(jié)點在一段時間內沒有收到事件消息，就認為查詢消息并沒有到達事件區(qū)域，可以選擇重傳、放棄或洪泛查詢,7.6地理位置路由7.6.1 GEAR路由,1.GEAR路由的基本思想GEAR采用查詢驅動數(shù)據(jù)傳送模式，根據(jù)事件區(qū)域的地理位置

36、信息，建立基站或者匯聚節(jié)點到事件區(qū)域的優(yōu)化路徑。,2.GEAR中查詢消息的傳播 (1) 查詢消息傳送到事件區(qū)域 GEAR路由用實際代價(1earned cost)和估計代價(estimated cost)兩種代價值來表示路徑代價。GEAR通過如圖7-9所示的方式來解決通信空洞問題，從而使路由進行下去。,(2) 查詢消息在事件區(qū)域內傳播當查詢命令被轉發(fā)進入事件區(qū)域后，大多數(shù)情況下采用遞歸的、基于地理信息的轉發(fā)方式在事件區(qū)域

37、內發(fā)布查詢命令。如圖7-10所示。,,2.GEAR中查詢消息的傳播,(3)GEAR路由的性能 GEAR路由定義估計路由代價為節(jié)點到事件區(qū)域的距離和節(jié)點剩余能量，并利用捎帶機制獲取實際路由代價，進行數(shù)據(jù)傳輸?shù)穆窂絻?yōu)化，從而形成能量高效的數(shù)據(jù)傳輸路徑。GEAR路由采用的貪婪算法是一個局部最優(yōu)的算法，適合無線傳感器網(wǎng)絡中節(jié)點只知道局部拓撲信息的情況，其缺點是由于缺乏足夠的拓撲信息，路由過程中可能遇到路由空洞，反而降低了路由效率。,7

38、.6.2 GAF路由,地域自適應保真算法GAF (Geographic Adaptive Fidelity)是基于有限能量和位置信息的路由算法，,GAF算法的執(zhí)行過程包括兩個階段。 第一階段是虛擬網(wǎng)格的劃分。根據(jù)節(jié)點的位置信息和通信半徑，將網(wǎng)絡區(qū)域劃分成若二干虛擬網(wǎng)格，保證相鄰單元格中的任意兩個節(jié)點都能夠直接通信。假設節(jié)點已知整個監(jiān)測區(qū)域的位置信息和本身的位置信息，節(jié)點可以通過計算得知自己屬于哪個網(wǎng)格。 第二階段是虛擬網(wǎng)

39、格中簇頭節(jié)點的選擇。節(jié)點周期性地進入睡眠和工作狀態(tài)，從睡眠狀態(tài)喚醒之后與本單元其他節(jié)點交換信息，以確定自己是否需要成為簇頭節(jié)點。,每個節(jié)點處于發(fā)現(xiàn)(discovery)、活動(active)以及睡眠(sleeping)3種狀態(tài)，如圖7-13所示。,7.6.3 GPSR路由,GPSR (Greedy Perimeter Stateless Routing)路由協(xié)議是貪婪算法(Greedy)和圖形算法的結合，它不需要維護路由表，是一種無狀態(tài)

40、的路由協(xié)議。 GPSR協(xié)議具有貪婪轉發(fā)((Greedy Forwarding)和周界轉發(fā)(Perimeters Forwarding)兩種分組轉發(fā)方式。1. 貪婪轉發(fā)算法 貪婪轉發(fā)算法是一種基于地理信息的路由算法。貪婪轉發(fā)算法的前提是每個分組都已包含其目的節(jié)點位置或目標區(qū)域位置，每個節(jié)點都已知自己及自接鄰節(jié)點的位置。 貪婪轉發(fā)算法總是朝距離目的節(jié)點最近的鄰節(jié)點轉發(fā)分組，如圖7-14所示。,2．周界轉發(fā)

41、 如圖7-15所示，采用周界轉發(fā)方式時，通常采用右手規(guī)則確定轉發(fā)的路徑。,,7.6.3 GPSR路由,圖7-16給出了右手規(guī)則的基本原理。當一個數(shù)據(jù)分組從節(jié)點x到達節(jié)點y時，它經過下一邊時以y為頂點，沿(y,x)逆時針方向上的第一條鏈路，如圖所示的為(y,z)，后續(xù)的同樣依照此規(guī)則來確定，直到數(shù)據(jù)到達目的節(jié)點為止。 GPSR路由協(xié)議同時采用了貪婪算法和周界轉發(fā)來對數(shù)據(jù)分組進行傳送。在完整的拓撲圖中采用貪婪轉發(fā)，當貪婪轉

42、發(fā)找不到下一跳節(jié)點時，則在平面圖中采用周界轉發(fā)決定數(shù)據(jù)分組的下一跳。,7.6.4 GEM和MECN路由,1．GEM路由 GEM (Graph Embedding)路由協(xié)議是一種適用于數(shù)據(jù)中心存儲(Data Centric Storage)方式的基于位置的路由協(xié)議。其基本思想是建立一個虛擬極坐標系統(tǒng)，用來表示實際的網(wǎng)絡拓撲結構。,2.MECN路由 MECN (Minimum Energy Communication N

43、etwork)和SMECN (Small MECN) 協(xié)議的主要思想是構建子網(wǎng)，每個子網(wǎng)有一個主站(Master Site)，相當于層次路由中的簇頭節(jié)點，要求子網(wǎng)內部所含節(jié)點數(shù)目少并且任意兩個節(jié)點之間傳輸數(shù)據(jù)都消耗更少的能量。,MECN的實現(xiàn)分兩個階段完成。 (1)第一階段：獲取位置信息，由節(jié)點內部的計算來構建包含所有發(fā)送節(jié)點外圍的外圍圖； (2)第二階段：在外圍圖中搜索最優(yōu)路徑，采用以能量消耗作為度量代價的分布式最短路

44、徑算法來實現(xiàn)。,7.7 可靠路由協(xié)議7.7.1不相交多路徑路由機制,不相交多路徑的建立過程如圖7-17所示，其基本思想是：首先由匯聚節(jié)點發(fā)出主路徑增強消息，建立一條由匯聚節(jié)點到源節(jié)點的主路徑P，如圖7-17(a)所示；然后進行備用路徑的建立。匯聚節(jié)點向其次優(yōu)節(jié)點A發(fā)出次優(yōu)路徑增強消息，節(jié)點A再將該消息發(fā)給自己的最優(yōu)節(jié)點B。,纏繞多路徑的建立如圖7-18所示。理想的纏繞多路徑由一組纏繞路徑構成，如圖7-18(a)所示，在主路徑上的每個節(jié)

45、點都能找到一條不包括本身的從源節(jié)點到目的節(jié)點的最優(yōu)路徑(實際上是次優(yōu)路徑)。而局部纏繞多路徑則是經過運算后有可能在某些主路徑的節(jié)點處找不到能繞過該節(jié)點的理想路徑，如圖7-18(b)所示。,纏繞多路徑可以克服主路徑E單個節(jié)點失敗的問題。 纏繞多路徑的建立如圖7-18所示。理想的纏繞多路徑由一組纏繞路徑構成，如圖7-18(a)所示，在主路徑上的每個節(jié)點都能找到一條不包括本身的從源節(jié)點到目的節(jié)點的最優(yōu)路徑(實際上是次優(yōu)路徑)。而局部纏繞多路

46、徑則是經過運算后有可能在某些主路徑的節(jié)點處找不到能繞過該節(jié)點的理想路徑，如圖7-18(b)所示。,,7.7.1不相交多路徑路由機制,7.7.2 ReInForM路由,可靠多路徑信息轉發(fā)ReInForM (Reliable Information Forwarding using Multiple paths)路由在數(shù)據(jù)傳輸方面從數(shù)據(jù)源節(jié)點開始，把監(jiān)測數(shù)據(jù)發(fā)送給匯聚節(jié)點，考慮信道質量以及傳感器節(jié)點到匯聚節(jié)點的跳數(shù)，決定需要的傳輸路徑數(shù)目，

47、以及下一跳節(jié)點數(shù)目和相應的節(jié)點，具有滿足可靠性要求的優(yōu)點。ReInForM路由考慮不同的傳輸可靠性要求，選擇最優(yōu)的路徑進行數(shù)據(jù)傳輸。 ReInForM路由的形成主要包括3個步驟： 1、計算傳輸路徑數(shù)； 2、下一跳節(jié)點選擇和路徑分配； 3、鄰居節(jié)點重新計算路徑。,7.7.3 SPEED協(xié)議,SPEED協(xié)議首先在相鄰節(jié)點之間交換傳輸延遲，以得到網(wǎng)絡負載情況然后節(jié)點利用局部地理信息和傳輸速

48、率信息選擇下一跳的節(jié)點。同時通過鄰居反饋機制保證網(wǎng)絡傳輸暢通，并且通過反向壓力路由變更機制避開延遲太大的鏈路和路由空洞。,包括7部分：SPEED接口(SPEED API)、鄰居信標交換(Neighborhood Beacon Exchange)、延遲估計(Delay Estimation Scheme)、無狀態(tài)的非確定的地理轉發(fā)算法(Stateless Non Deterministic Geographic Forwarding，SN

49、GF)、鄰居反饋策略(Neighborhood Feedback Loop，NFL)、反向壓力重路由(Backpressure Rerouting)和最后一跳的處理(Last mile processing)，各部分之間的關系如圖7-19所示。,7.8路由協(xié)議自主切換,一個路由服務的通信模型如圖7-20所示。,,南加州大學的Y.He等人提出了一個可編程的傳感器網(wǎng)絡框架，如圖7-21所示，,在路由服務選擇協(xié)議的過程中，定義了3種組件用以描