第13章-物聯(lián)網(wǎng)通信技術(shù)(曾憲武)LXX20147

1、第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議1 1 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議13.1WSN路由協(xié)議的特點和性能指標(biāo)本路由協(xié)議的特點和性能指標(biāo)本13.2能量感知路由能量感知路由13.3查詢路由查詢路由13.4地理位置路由地理位置路由13.5可靠路由協(xié)議可靠路由協(xié)議本章小結(jié)本章小結(jié)第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2 213.1 WSN路由協(xié)議的特點和性能指標(biāo)路由協(xié)議的特點和性能指標(biāo)13.1.1 WSN路由協(xié)議的特點路由協(xié)議的特點對于一般的無線網(wǎng)絡(luò)， WSN路由協(xié)議主要用于提供較高的服務(wù)質(zhì)量， 均等、 高效地利用網(wǎng)絡(luò)帶寬傳送數(shù)據(jù)。 因此， 網(wǎng)絡(luò)路由協(xié)議的主要任務(wù)是尋找一條高質(zhì)量的、 帶寬利用率高的源節(jié)點

2、到目的節(jié)點的通信路由， 并且所尋找到的路由還應(yīng)具有避免網(wǎng)絡(luò)擁塞、 均衡網(wǎng)絡(luò)流量的性能。一般不考慮或極少考慮節(jié)點能量的消耗。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3 3在WSN中， 各節(jié)點的能量是有限的。 節(jié)點的能量消耗完， 一般無法補充， 該節(jié)點隨之死亡。 因此， WSN的路由需要考慮節(jié)點的能量消耗問題， 使節(jié)點能量的消耗盡量要小。 另外， WSN中的節(jié)點數(shù)量往往很大， 各節(jié)點一般無法獲得整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息， 只能得到局部拓?fù)浣Y(jié)構(gòu)信息， 因此， WSN的路由協(xié)議應(yīng)在有限的局部網(wǎng)絡(luò)拓?fù)湫畔⒌幕A(chǔ)上選擇合適的數(shù)據(jù)傳輸路徑。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4 4還有， WSN具有很強的應(yīng)用相關(guān)性。 由

3、于不同應(yīng)用所采用的路由協(xié)議可能差別很大， 因此無法采用一個通用的路由協(xié)議來滿足其應(yīng)用相關(guān)性的要求。 此外， WSN中的節(jié)點在通信時還需進(jìn)行數(shù)據(jù)融合， 以減少通信負(fù)荷， 節(jié)省傳輸能量。 與一般傳統(tǒng)無線網(wǎng)絡(luò)的路由協(xié)議相比， WSN路由協(xié)議具有以下特點： 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5 5（1） 節(jié)點的能量消耗小且均衡。 由于WSN中的節(jié)點能量有限， 且一般無法補充。 當(dāng)WSN中的某些節(jié)點由于能量的耗盡而死亡時， 可能導(dǎo)致整個網(wǎng)絡(luò)無法運行， 以致死亡。 因此， 盡量減小節(jié)點能量的消耗， 使整個WSN中所有節(jié)點盡可能均衡地消耗能量（也就是盡量減少某些節(jié)點的能量消耗過快， 而其他節(jié)點的能量消耗過慢）

4、， 從而延長整個網(wǎng)絡(luò)的生存期， 這是WSN路由協(xié)議設(shè)計的重要目標(biāo)。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6 6（2） 網(wǎng)絡(luò)拓?fù)湫畔ⅰ?計算資源有限。 WSN為了節(jié)省通信時節(jié)點的能量， 通常采用多跳的通信模式。 另外， 由于WSN的節(jié)點是低成本的， 不具有較高的存儲能力和計算能力， 也無法存儲太多包括拓?fù)浣Y(jié)構(gòu)在內(nèi)的網(wǎng)絡(luò)信息， 節(jié)點所存儲的拓?fù)湫畔⑹蔷植康摹?因此， 節(jié)點無法進(jìn)行太復(fù)雜的計算， 得到全局優(yōu)化路由。 為此， 如何實現(xiàn)簡單有效的路由機制就成為WSN的基本問題。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7 7（3） 以數(shù)據(jù)為核心。 WSN中的節(jié)點采集的數(shù)據(jù)， 將向匯聚節(jié)點傳輸。 轉(zhuǎn)發(fā)節(jié)點所轉(zhuǎn)發(fā)的數(shù)據(jù)很可

5、能是采集的同一個信息， 因此會出現(xiàn)數(shù)據(jù)的冗余的現(xiàn)象， 需要在轉(zhuǎn)發(fā)節(jié)點進(jìn)行數(shù)據(jù)融合， 以降低數(shù)據(jù)的冗余率， 減少轉(zhuǎn)發(fā)的數(shù)據(jù)量， 從而降低能耗。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8 8另外， WSN的網(wǎng)絡(luò)規(guī)模較大， WSN的節(jié)點一般采用隨機部署的方式獲取有關(guān)監(jiān)測區(qū)域的感知數(shù)據(jù)。 整個系統(tǒng)更關(guān)心的是感知數(shù)據(jù)， 而不是具體哪個節(jié)點獲取的信息， 因而WSN信息的獲得不依賴于節(jié)點的地址信息， 而是局部區(qū)域內(nèi)所感知的信息。 所以WSN的通信協(xié)議是以數(shù)據(jù)為中心的。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議9 9（4） 與應(yīng)用密切相關(guān)。 由于WSN應(yīng)用目的不同、 應(yīng)用環(huán)境也不同， 這就決定了WSN模式的不同， 因此無法

6、找到一個路由機制能適合所有的應(yīng)用目的和應(yīng)用環(huán)境， 這是WSN應(yīng)用相關(guān)性的一個體現(xiàn)。 這就要求應(yīng)用者應(yīng)從實際出發(fā)， 結(jié)合具體的應(yīng)用需求， 設(shè)計與之適應(yīng)的特定路由機制。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議10 1013.1.2 WSN路由協(xié)議的性能指標(biāo)及分類路由協(xié)議的性能指標(biāo)及分類1. 性能指標(biāo)WSN路由協(xié)議的設(shè)計目標(biāo)是： 延長網(wǎng)絡(luò)生命周期， 提高路由的容錯能力， 形成可靠的數(shù)據(jù)轉(zhuǎn)發(fā)機制。 評價一個WSN路由協(xié)議設(shè)計的性能指標(biāo)一般包括WSN的生命周期、 傳輸延遲、 魯棒性、 可擴展性等。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議11 11（3） 魯棒性。 一個系統(tǒng)的魯棒性是指該系統(tǒng)在一定的參數(shù)攝動（變化）下

7、， 能維持系統(tǒng)性能穩(wěn)定的能力。 WSN的路由算法應(yīng)具備自適應(yīng)性和容錯性， 在部分節(jié)點因為能源耗盡或受環(huán)境干擾而死亡或失效的情況下， 整個WSN能正常運行。 （4） 可擴展性。WSN應(yīng)該能夠方便地進(jìn)行規(guī)模擴展。 節(jié)點的加入和退出都將導(dǎo)致網(wǎng)絡(luò)規(guī)模的變動， 優(yōu)良的路由協(xié)議應(yīng)該體現(xiàn)很好的擴展性， 節(jié)點數(shù)量的變動不至于影響網(wǎng)絡(luò)的性能和通信質(zhì)量。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議12 122. WSN路由協(xié)議的分類從具體應(yīng)用的角度出發(fā)， 根據(jù)不同應(yīng)用對WSN各種特性的敏感度不同， 可將路由協(xié)議分為四種類型： （1） 能量感知型。能量感知型路由協(xié)議從數(shù)據(jù)傳輸中的能量消耗出發(fā)， 討論最優(yōu)能量消耗路徑以及最長網(wǎng)絡(luò)

8、生存時間等問題。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議13 13（2） 查詢型。 在諸如環(huán)境檢測、 戰(zhàn)場評估等應(yīng)用中， 需要不斷查詢傳感器節(jié)點采集的數(shù)據(jù)， 查詢節(jié)點（匯聚節(jié)點）發(fā)出查詢命令， 傳感器節(jié)點向查詢節(jié)點報告采集的數(shù)據(jù)。 在這類應(yīng)用中， 通信流量主要是查詢節(jié)點和傳感器節(jié)點之間的命令和數(shù)據(jù)傳輸， 同時傳感器節(jié)點的采集信息在傳輸路徑上通常要進(jìn)行數(shù)據(jù)融合， 以減少通信負(fù)荷， 節(jié)省能量。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議14 14（3） 地理位置型。 在諸如目標(biāo)跟蹤類應(yīng)用中， 往往需要喚醒距離跟蹤目標(biāo)最近的傳感器節(jié)點， 以得到關(guān)于目標(biāo)的精確位置等相關(guān)信息。 在這類應(yīng)用中， 通常需要知道目的節(jié)點的精確

9、或者大致地理位置。 把節(jié)點的位置信息作為路由選擇的依據(jù)， 不僅能夠完成節(jié)點路由功能， 還可以降低系統(tǒng)專門維護路由協(xié)議的能耗。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議15 15（4） 可靠型。 WSN的某些應(yīng)用對通信的服務(wù)質(zhì)量有較高要求， 如可靠性和實時性等。 在WSN中， 鏈路的穩(wěn)定性難以保證， 通信信道質(zhì)量比較低， 拓?fù)渥兓容^頻繁， 要保證服務(wù)質(zhì)量， 需要設(shè)計相應(yīng)的可靠的路由協(xié)議。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議16 1613.2 能量感知路由能量感知路由 13.2.1 能量路由能量路由能量路由是根據(jù)節(jié)點的可用能量(Power Available, PA)或傳輸路徑上的能量需求， 選擇數(shù)據(jù)的轉(zhuǎn)

10、發(fā)路徑。 節(jié)點可用能量就是節(jié)點當(dāng)前的剩余能量。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議17 17圖13.2.1中的大寫字母表示節(jié)點， 字母右側(cè)括號內(nèi)的數(shù)字表示節(jié)點可用能量， 雙向線表示節(jié)點之間的通信鏈路，鏈路上的數(shù)字表示在該鏈路上發(fā)送數(shù)據(jù)所消耗的能量。 源節(jié)點是具有數(shù)據(jù)采集功能的一般性節(jié)點， 匯聚節(jié)點是數(shù)據(jù)傳送到達(dá)的目標(biāo)節(jié)點。 從圖13.2.1可以得到如表13.2.1所示的從源節(jié)點到匯聚節(jié)點的傳輸路徑。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議18 18圖13.2.1 一個WSN能量路由算法示意圖第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議19 19第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2020能量路由策略主要包括以下幾點：

11、 （1） 最大可用能量(PA)路由。路由策略： 從源節(jié)點到匯聚節(jié)點的所有路徑中選取節(jié)點可用能量PA之和最大的路徑。 在圖13.2.1中路徑2的PA之和最大（PA=6）， 但路徑2包含了路徑1， 因此該路徑不是高效的路徑， 從而被排除。 于是， 只有選擇路徑4（PA=5）作為最大可用能量(PA)路由。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議21 21（2） 最小能量消耗路由。 路由策略： 從源節(jié)點到匯聚節(jié)點的所有路徑中， 選取節(jié)點耗能之和最小的路徑。 在圖13.2.1中， 由于路徑1所消耗的能量最小， 僅為3， 所以選擇路徑1作為最小能量消耗路由。 （3） 最少跳數(shù)路由。路由策略： 選取從源節(jié)點到匯聚節(jié)

12、點間跳數(shù)最少的路徑。 在圖13.2.1中， 由于路徑3僅有1跳， 所以選擇路徑3作為最少跳數(shù)路由。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2222（4） 最大最小PA節(jié)點路由。路由策略：每條路徑上有多個節(jié)點， 且節(jié)點的可用能量不同， 從中選取每條路徑中可用能量最小的節(jié)點來表示這條路徑的可用能量， 并且選擇可用能量最大的路徑為最大最小PA節(jié)點路由。 在圖13.2.1中， 路徑1的最小PA節(jié)點為PA=2， 路徑2的最小PA節(jié)點為PA=2， 路徑3中最小PA節(jié)點為PA=3， 路徑4中最小PA節(jié)點為PA(E)=1。 4條路徑中PA最大的為路徑3，所以選擇路徑3作為最大最小PA節(jié)點路由。 最大最小PA節(jié)點路由

13、策略就是選擇路徑可用能量最大的路徑。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議232313.2.2 能量多路徑路由能量多路徑路由傳統(tǒng)網(wǎng)絡(luò)的路由機制往往選擇源節(jié)點到目的節(jié)點之間跳數(shù)最小的路徑來傳輸數(shù)據(jù)。 但在WSN中， 如果多次使用同一條路徑傳輸數(shù)據(jù)， 就會造成該路徑上的節(jié)點因能量消耗過快而過早死亡， 從而造成整個網(wǎng)絡(luò)的分割現(xiàn)象。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2424WSN可分割成互不相連的幾個孤立部分， 以縮短整個網(wǎng)絡(luò)的生命周期。 為此， 可采用能量多路徑路由機制來解決該問題。 這種機制是在源節(jié)點和目的節(jié)點之間建立多條路徑， 根據(jù)路徑上節(jié)點的通信能量消耗以及節(jié)點的剩余能量情況， 給每條路徑賦予一定

14、的選擇概率， 使得數(shù)據(jù)傳輸均衡消耗整個網(wǎng)絡(luò)的能量， 從而延長整個網(wǎng)絡(luò)的生命周期。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2525能量多路徑路由協(xié)議由路徑建立、 數(shù)據(jù)傳輸和路由維護三個過程構(gòu)成。 其中， 路徑建立過程是該協(xié)議的重點內(nèi)容。 在能量多路徑機制中， 每個節(jié)點需要知道到達(dá)目的節(jié)點的所有下一跳節(jié)點， 并計算選擇每個下一跳節(jié)點傳輸數(shù)據(jù)的概率。 概率的選擇是根據(jù)節(jié)點到目的節(jié)點的通信代價來計算的， 可用Cost(Ni)來表示節(jié)點i到目的節(jié)點的通信代價。 由于每個節(jié)點到達(dá)目的節(jié)點的路徑很多， 所以這個代價值是各個路徑的加權(quán)平均值。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2626能量多路徑路由的主要算法描述如下：

15、 （1） 啟動路徑建立。 目的節(jié)點向鄰居節(jié)點廣播路徑建立消息， 啟動路徑建立過程。 路徑建立消息中包含一個代價域， 表示發(fā)出該消息的節(jié)點到目的節(jié)點路徑上的能量信息， 初始值設(shè)置為零。 （2） 確定消息轉(zhuǎn)發(fā)。 當(dāng)節(jié)點收到相鄰節(jié)點發(fā)送的路徑建立消息時， 相對發(fā)送該消息的相鄰節(jié)點只有當(dāng)自己距源節(jié)點更近， 而距離目標(biāo)節(jié)點更遠(yuǎn)的情況下， 才需要轉(zhuǎn)發(fā)該消息， 否則將丟棄該消息。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2727（3） 計算信能量消耗。 如果該節(jié)點決定轉(zhuǎn)發(fā)路徑建立消息， 那么需要計算新的代價值來替換原來的代價值。 當(dāng)路徑建立消息從節(jié)點Ni發(fā)送到節(jié)點Nj時， 該路徑的通信值為節(jié)點i的代價值加上兩個節(jié)點間

16、通信能量消耗， 即(13.2.1)式中， CNj, Ni表示節(jié)點Nj發(fā)送數(shù)據(jù)經(jīng)節(jié)點Ni路徑到達(dá)目的節(jié)點的代價， Metric(Nj, Ni)表示節(jié)點Nj到節(jié)點Ni的通信能量消耗， 可用下式計算：第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2828式中， eij表示節(jié)點Nj和節(jié)點Ni直接通信的能量消耗，Ri表示節(jié)點Ni剩余能量， 、 為常數(shù)。 這個度量綜合考慮了節(jié)點的能量消耗以及節(jié)點的剩余能量。 (13.2.2)第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議2929（4） 計算與添加本地路由表。 節(jié)點要放棄能量消耗代價很大的路徑。 節(jié)點 j 將節(jié)點i加入到本地路由表FTj中的條件為(13.2.3)式中， 為大于1的系統(tǒng)參

17、數(shù)。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3030（5） 計算下一跳選擇概率。 節(jié)點對路由表中每個下一跳計算選擇概率， 節(jié)點選擇概率與能量消耗成反比。 節(jié)點Nj采用下式計算選擇節(jié)點Ni的概率：（13.2.4）第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議31 31（6） 計算能量代價及廣播消息。 節(jié)點根據(jù)路由表中每項的能量代價和下一跳節(jié)點選擇概率計算本節(jié)點到目的節(jié)點的代價Cost（Nj）， 它被定義為經(jīng)由路由表中節(jié)點到達(dá)目的節(jié)點的代價的平均值， 即節(jié)點Nj將用Cost(Nj)值替換消息中原有的代價值， 然后向相鄰節(jié)點廣播該路由建立消息。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3232 13.3 查查 詢詢 路路 由由

18、13.3.1 定向擴散路由定向擴散路由定向擴散(Directed Diffusion, DD)路由是一種查詢機制的路由。 匯聚節(jié)點以興趣消息(Interest Information)向WSN發(fā)布查詢?nèi)蝿?wù)。 興趣消息的傳送采用洪泛方式傳播到整個區(qū)域或部分區(qū)域內(nèi)的所有傳感器節(jié)點處。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3333興趣消息表示查詢?nèi)蝿?wù)， 并發(fā)送網(wǎng)絡(luò)用戶對監(jiān)測區(qū)域內(nèi)感興趣的信息， 例如監(jiān)測區(qū)域內(nèi)的環(huán)境信息。 在興趣消息的傳播過程中， 協(xié)議逐跳地在每個傳感器節(jié)點上建立反向的從源節(jié)點到匯聚節(jié)點的數(shù)據(jù)傳輸梯度(Gradient)。 傳感器節(jié)點將采集到的數(shù)據(jù)沿著梯度方向傳送給匯聚節(jié)點。 定向擴散路

19、由機制可以分為興趣擴散、 梯度建立以及路徑加強三個階段， 如圖13.3.1所示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3434圖13.3.1 定向擴散路由機制第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議35351. 興趣擴散階段在興趣擴散階段， 匯聚節(jié)點周期性地向相鄰節(jié)點廣播興趣消息。 興趣消息中含有任務(wù)類型、 目標(biāo)區(qū)域、 數(shù)據(jù)發(fā)送速率、 時間戳等參數(shù)。 每個節(jié)點在本地保存一個興趣列表， 對于每個興趣， 列表中都有一表項， 用來記錄發(fā)送該興趣消息的鄰居節(jié)點、 數(shù)據(jù)發(fā)送速率和時間戳等與任務(wù)相關(guān)的信息， 以建立該節(jié)點向匯聚節(jié)點傳遞數(shù)據(jù)的梯度關(guān)系。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3636每個興趣可能對應(yīng)多個相鄰節(jié)點

20、， 每個相鄰節(jié)點對應(yīng)一個梯度信息。 通過定義不同的梯度相關(guān)參數(shù)， 可以滿足不同的應(yīng)用需求。 每個表項還有一個字段， 用來表示該表項的有效時間值， 若超過這個時間值， 節(jié)點將刪除這個表項。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3737當(dāng)節(jié)點收到相鄰節(jié)點的興趣消息時， 首先檢查興趣列表中是否存有參數(shù)類型與剛收到的興趣消息相同的表項， 且該表項對應(yīng)的發(fā)送節(jié)點是該相鄰節(jié)點， 如果有對應(yīng)的表項， 就更新表項的有效時間值； 如果只是參數(shù)類型相同， 但不包含發(fā)送該興趣消息的相鄰節(jié)點， 就在相應(yīng)表項中添加這個相鄰節(jié)點； 對于任何其他情況， 都需要建立一個新表項來記錄這個新的興趣消息。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)

21、議38382. 梯度建立階段當(dāng)傳感器節(jié)點采集到與興趣匹配的數(shù)據(jù)時， 會把數(shù)據(jù)發(fā)送到梯度上的相鄰節(jié)點， 并按照梯度上的數(shù)據(jù)傳輸速率設(shè)定傳感器模塊傳輸數(shù)據(jù)的速率。 由于可能從多個相鄰節(jié)點收到興趣消息， 節(jié)點向多個相鄰節(jié)點發(fā)送數(shù)據(jù)， 匯聚節(jié)點可能收到經(jīng)過多個路徑的相同數(shù)據(jù)。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3939中間節(jié)點收到其他節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)后， 首先查詢興趣列表的表項， 如果沒有匹配的興趣表項就丟棄數(shù)據(jù)； 如果存在相應(yīng)的興趣表項， 則檢查這個興趣對應(yīng)的數(shù)據(jù)緩沖池(Data Cache)。 數(shù)據(jù)緩沖池用來保存最近轉(zhuǎn)發(fā)的數(shù)據(jù)。 如果在數(shù)據(jù)緩沖池中有與接收到的數(shù)據(jù)匹配的副本， 就說明已經(jīng)轉(zhuǎn)發(fā)這個數(shù)據(jù)。

22、 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4040為避免出現(xiàn)傳輸回環(huán)， 應(yīng)丟棄這個數(shù)據(jù)； 否則， 檢查該興趣表項中相鄰節(jié)點的信息， 如果設(shè)置的相鄰節(jié)點的數(shù)據(jù)傳輸速率大于等于接收的數(shù)據(jù)傳輸速率， 則全部轉(zhuǎn)發(fā)接收的數(shù)據(jù)； 如果設(shè)置的相鄰節(jié)點的數(shù)據(jù)傳輸速率小于接收的數(shù)據(jù)傳輸速率， 則按照比例轉(zhuǎn)發(fā)。 對于轉(zhuǎn)發(fā)的數(shù)據(jù)， 數(shù)據(jù)緩沖池保留一個副本， 并記錄轉(zhuǎn)發(fā)時間。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議41 413. 路徑加強階段定向擴散路由機制以正向加強機制來優(yōu)化路徑， 并根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓薷臄?shù)據(jù)轉(zhuǎn)發(fā)的梯度關(guān)系。 興趣擴散階段是為了建立源節(jié)點到匯聚節(jié)點的數(shù)據(jù)傳輸路徑， 數(shù)據(jù)源節(jié)點以較低的速率采集和發(fā)送數(shù)據(jù)， 這個階

23、段建立的梯度稱為探測梯度(Probe Gradient)。 匯聚節(jié)點在收到從源節(jié)點發(fā)來的數(shù)據(jù)后， 啟動建立源節(jié)點的加強路徑， 后續(xù)數(shù)據(jù)將沿著加強路徑以較高的數(shù)據(jù)傳輸速率進(jìn)行傳輸。 加強后的梯度稱為數(shù)據(jù)梯度(Data Gradient)。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4242如果用傳輸延遲作為路由加強的標(biāo)準(zhǔn)， 則匯聚節(jié)點首先選擇發(fā)送來最新數(shù)據(jù)的相鄰節(jié)點作為加強路徑的下一跳節(jié)點， 并向該相鄰節(jié)點發(fā)送路徑加強消息。 路徑加強消息中包含新設(shè)定的較高的發(fā)送數(shù)據(jù)傳輸速率值。 相鄰節(jié)點收到該消息后， 經(jīng)過分析確定該消息描述的是一個已有的興趣消息， 僅是為了增加數(shù)據(jù)傳輸速率， 于是斷定這是一條路徑加強消息

24、， 從而更新相應(yīng)興趣表項得到相鄰節(jié)點的數(shù)據(jù)傳輸速率。 同時， 按照同樣的規(guī)則選擇加強路徑下一跳的相鄰節(jié)點第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4343路由加強的標(biāo)準(zhǔn)不是唯一的。 可以選擇在一定時間內(nèi)發(fā)送數(shù)據(jù)最多的節(jié)點作為路徑加強的下一跳節(jié)點， 也可以選擇數(shù)據(jù)傳輸最穩(wěn)定的節(jié)點作為路徑加強的下一跳節(jié)點。 加強路徑上的節(jié)點如果發(fā)現(xiàn)下一跳節(jié)點的傳輸數(shù)據(jù)速率明顯減小， 或者收到來自其他節(jié)點的新位置估計，推斷加強路徑的下一跳節(jié)點可能失效， 就需要使用上述的路徑加強機制重新確定下一跳節(jié)點。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議444413.3.2 謠傳路由謠傳路由在數(shù)據(jù)傳輸量較少或者已知事件區(qū)域的情況下， 如果采用定

25、向擴散路由， 則需采用查詢消息的洪泛傳播和路徑增強機制， WSN才能確定一條優(yōu)化的數(shù)據(jù)傳輸路徑。 因此， 在這種情況下， 路由效率不高， 而需采用其他高效率的路由機制。 謠傳路由(Rumor Routing)較適合于這類數(shù)據(jù)量傳輸較小的情況。 謠傳路由機制采用了查詢消息的單播隨機轉(zhuǎn)發(fā)方式， 避免了洪泛方式建立轉(zhuǎn)發(fā)路徑帶來的開銷過大問題。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4545謠傳路由機制的基本思想是： 事件區(qū)域中的傳感器節(jié)點產(chǎn)生代理(Agent)消息， 代理消息沿隨機路徑向外擴散傳播， 同時匯聚節(jié)點發(fā)送的查詢消息也沿隨機路徑在WSN中傳播。 當(dāng)代理消息和查詢消息的傳輸路徑交叉在一起時， 就會

26、形成一條匯聚節(jié)點到事件區(qū)域的完整路徑。謠傳路由機制的原理如圖13.3.2所示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4646圖圖13.3.2 謠傳路由機制原理圖謠傳路由機制原理圖第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4747謠傳路由的建立經(jīng)過以下幾個過程： （1） 相鄰節(jié)點列表與事件列表的維護。 每個傳感器節(jié)點維護一個相鄰WSN節(jié)點列表和一個事件列表。 事件列表的每個表項都記錄事件相關(guān)的信息， 主要包括事件名稱、 事件區(qū)域的跳數(shù)、 事件區(qū)域的下一跳相鄰節(jié)點等信息。 當(dāng)傳感器節(jié)點在本地監(jiān)測到一個事件發(fā)生時， 在事件列表中增加一個表項， 用來設(shè)置事件名稱、 跳數(shù)（此時跳數(shù)為零）等， 同時根據(jù)一定的概率產(chǎn)生一

27、個代理消息。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4848（2） 代理消息的傳輸。 代理消息中包含了與生命期等事件相關(guān)的分組信息， 將攜帶的事件信息通告給傳輸中經(jīng)過的每個傳感器節(jié)點。 對于收到代理消息的節(jié)點， 首先檢查事件列表中是否有與該事件相關(guān)的表項， 如果列表中存在相關(guān)表項， 就比較代理消息和表項中的跳數(shù)值， 如果該節(jié)點中列表的跳數(shù)值小， 就更新表項中的跳數(shù)值， 否則更新代理消息中的跳數(shù)值。 如果事件列表中沒有該事件相關(guān)的表項， 就增加一個表項來記錄代理消息攜帶的事件信息。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議4949（3） 查詢消息的轉(zhuǎn)發(fā)。 WSN的任何節(jié)點都可能生成一個對特定事件的查詢消息。

28、如果節(jié)點的事件列表中保存有該事件的相關(guān)表項， 說明該節(jié)點在到達(dá)事件區(qū)域的路徑上， 它沿著這條路徑轉(zhuǎn)發(fā)查詢消息， 否則， 節(jié)點隨機選擇相鄰節(jié)點轉(zhuǎn)發(fā)查詢消息。 查詢消息經(jīng)過的節(jié)點按照同樣方式轉(zhuǎn)發(fā)， 并記錄查詢消息中的相關(guān)信息， 形成查詢消息的路徑。 查詢消息也具有一定的生命期， 以解決環(huán)路問題。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5050（4） 謠傳路由的形成。 如果查詢消息和代理消息的路徑交叉， 交叉節(jié)點就會沿查詢消息的反向路徑將事件信息傳送到咨詢節(jié)點， 并形成謠傳路由。 如果查詢節(jié)點在一段時間內(nèi)沒有收到事件消息， 就認(rèn)為查詢消息沒有到達(dá)事件區(qū)域， 可以選擇重傳、 放棄或者洪泛查詢消息的方法。 由

29、于洪泛查詢機制的代價過高， 一般作為最后的選擇。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議51 5113.4 地理位置路由地理位置路由在WSN中， 節(jié)點通常需要獲取自身的位置信息， 這樣它采集的數(shù)據(jù)才有意義。 地理位置路由假設(shè)節(jié)點知道自己的地理位置信息， 以及目的節(jié)點或者目的區(qū)域的地理位置。 WSN利用這些地理位置信息作為路由選擇的依據(jù)， 節(jié)點按照一定策略轉(zhuǎn)發(fā)數(shù)據(jù)到目的節(jié)點。 地理位置的精確度和代價相關(guān)， 在不同的應(yīng)用中會選擇不同精確度的位置信息來實現(xiàn)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5252GEAR(Geographical and Energy Aware Routing)路由是根據(jù)

30、事件區(qū)域的地理位置信息， 建立匯聚節(jié)點到事件區(qū)域的優(yōu)化路徑的。 該機制可避免洪泛傳播方式帶來較大的路由建立的開銷， 降低節(jié)點的能量消耗。 GEAR路由假設(shè)已知事件區(qū)域的位置信息， 每個節(jié)點知道自己的位置信息和剩余能量信息， 并通過一個簡單的Hello消息交換機制知道所有相鄰節(jié)點的位置信息和剩余能量信息。 在GEAR路由中， 節(jié)點間的通信鏈路是對稱的。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5353 GEAR路由中， 查詢消息傳播分為兩個階段。 第一階段， 匯聚節(jié)點發(fā)出查詢命令， 并根據(jù)事件區(qū)域的地理位置將查詢命令傳送到區(qū)域內(nèi)距匯聚節(jié)點最近的節(jié)點； 第二階段， 該節(jié)點將查詢命令傳輸?shù)絽^(qū)域內(nèi)的其他所有節(jié)

31、點， 監(jiān)測數(shù)據(jù)沿查詢消息的反向路徑向匯聚節(jié)點傳送。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議54541. 查詢消息傳送到事件區(qū)域GEAR路由用實際代價(Learned Cost)和估計代價(Estimate Cost)兩種代價值表示路徑代價。 當(dāng)路徑未建立時， 中間節(jié)點使用估計代價來決定下一跳節(jié)點。 估計代價定義為歸一化的節(jié)點到事件區(qū)域的通信所消耗的能量和節(jié)點的剩余能量之和。 節(jié)點到事件區(qū)域的距離用節(jié)點到事件區(qū)域幾何中心的距離來表示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5555由于所有節(jié)點均知道自己的位置和事件區(qū)域的位置， 因而所有節(jié)點都能夠計算出自己到事件區(qū)域幾何中心的距離。節(jié)點計算自身到事件區(qū)域估計

32、代價值為c（N， R）=d（N， R）+（1）e（N）（13.4.1)式中， c(N, R)為節(jié)點N到事件區(qū)域R的估計代價， d(N, R)為節(jié)點N到事件區(qū)域R的距離， e(N)為節(jié)點N的剩余能量， 為比例參數(shù)。 d(N, R)和e(N)均為歸一化后的值。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5656查詢信息到達(dá)事件區(qū)域后， 事件區(qū)域內(nèi)的節(jié)點沿查詢路徑的反方向傳輸監(jiān)測數(shù)據(jù)， 該數(shù)據(jù)攜帶每跳節(jié)點到事件區(qū)域的實際能量消耗值。 對于數(shù)據(jù)傳輸所經(jīng)過的各節(jié)點， 節(jié)點首先記錄攜帶的能量代價， 然后對所記錄的能量代價進(jìn)行更新（即消息中的能量代價+本節(jié)點發(fā)送該數(shù)據(jù)到下一跳節(jié)點的能量消耗）， 將更新后的能量消耗值連

33、同其他數(shù)據(jù)轉(zhuǎn)發(fā)出去。 節(jié)點下一次轉(zhuǎn)發(fā)查詢消息時， 用剛才記錄的與事件區(qū)域通信消耗的實際能量代價代替式(13.4.1)中的d(N, R)， 計算其到匯聚節(jié)點的實際代價值。 節(jié)點用調(diào)整后的實際代價選擇到達(dá)事件區(qū)域的優(yōu)化路徑。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5757以匯聚節(jié)點開始的路徑建立過程一般采用貪婪算法。 節(jié)點在相鄰節(jié)點中選擇到事件區(qū)域路由代價最小的節(jié)點作為下一跳節(jié)點， 并將自己的路由代價設(shè)為下一跳節(jié)點的路由代價加上與該節(jié)點一跳通信的代價。 如果節(jié)點的所有相鄰節(jié)點到事件區(qū)域的路由代價都比自己的大， 則陷入了路由空洞(Routing Void)， 如圖13.4.1所示。第13章無線傳感器網(wǎng)絡(luò)的

34、路由協(xié)議5858圖13.4.1中， S為匯聚節(jié)點， T為目的節(jié)點， M7、 M8、 M9為死亡（失效）節(jié)點。 節(jié)點M3是S的相鄰節(jié)點中到目的節(jié)點的路由代價最小的節(jié)點， 但節(jié)點M3的所有相鄰節(jié)點到目的節(jié)點T的路由代價都比M3到T的路由代價要大， 并且M7、M8、 M9為死亡（失效）節(jié)點， 這就造成了路由空洞。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議5959圖13.4.1 路由空洞情況示意第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6060解決的方法為： M3選取路由代價最小的鄰居節(jié)點M2作為下一跳節(jié)點， 并將自己的代價值設(shè)置為M2節(jié)點的路由代價加上M3節(jié)點到M2節(jié)點的下一跳的路由代價。 同時， 節(jié)點M3將這個新的

35、代價值通知匯聚節(jié)點S， S再轉(zhuǎn)發(fā)查詢命令給節(jié)點T時， 選擇節(jié)點M2作為下一跳節(jié)點， 而不選擇節(jié)點M3。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議61 612. 查詢消息在事件區(qū)域內(nèi)傳播當(dāng)查詢命令傳送到事件區(qū)域后， 可以洪泛方式傳播到事件區(qū)域內(nèi)的所有節(jié)點。 但當(dāng)WSN節(jié)點密度較大時， 洪泛方式的能量開銷比較大， 這時可以采用迭代地理轉(zhuǎn)發(fā)機制， 如圖13.4.2所示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6262圖13.4.2 區(qū)域內(nèi)的迭代地理轉(zhuǎn)發(fā)示意圖第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6363事件區(qū)域內(nèi)首先收到查詢命令的節(jié)點， 將事件區(qū)域分為若干子區(qū)域， 并向所有子區(qū)域的中心位置轉(zhuǎn)發(fā)查詢命令， 在每個子區(qū)域中

36、， 靠近區(qū)域中心的節(jié)點(如圖13.4.2中的 Ni)接收查詢命令， 并將自己所在的子區(qū)域再劃分為若干個子區(qū)域后向各個子區(qū)域中心轉(zhuǎn)發(fā)查詢命令。 該消息傳播過程是一個迭代過程， 當(dāng)節(jié)點發(fā)現(xiàn)自己是某個子區(qū)域內(nèi)唯一的節(jié)點或某個子區(qū)域沒有節(jié)點存在時， 停止向這個子區(qū)域發(fā)送查詢命令。 當(dāng)所有子區(qū)域轉(zhuǎn)發(fā)過程全部結(jié)束時， 整個迭代過程終止。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6464當(dāng)事件區(qū)域節(jié)點數(shù)較多時， 迭代地理轉(zhuǎn)發(fā)的消息轉(zhuǎn)發(fā)次數(shù)少， 而節(jié)點較少時使用洪泛策略的路由效率高。 GEAR路由可以使用如下方法在兩種機制中作選擇： 當(dāng)查詢命令到達(dá)區(qū)域內(nèi)的第一個節(jié)點時， 如果該節(jié)點的相鄰節(jié)點數(shù)量大于一個預(yù)設(shè)的閾值，

37、則使用迭代地理轉(zhuǎn)發(fā)機制， 否則使用洪泛機制。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議656513.5 可靠路由協(xié)議可靠路由協(xié)議13.5.1 不相交的多路徑路由機制不相交的多路徑路由機制不相交多路徑是指從源節(jié)點到目的節(jié)點之間任意兩條路徑都沒有相交的節(jié)點。 其建立過程如圖13.5.1所示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6666圖13.5.1 不相交多路徑的建立示例第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6767 匯聚節(jié)點首先通過主路徑增強消息來建立主路徑， 然后發(fā)送次優(yōu)路徑增強消息給次優(yōu)點節(jié)點A， 節(jié)點A再選擇自己的最優(yōu)節(jié)點B， 將次優(yōu)路徑增強信息傳遞下去。 如果B在主路徑上， 則B發(fā)回否定增強消息給A，

38、A向次優(yōu)節(jié)點傳遞次優(yōu)路徑增強信息； 如果B不在主路徑上， 則B繼續(xù)傳遞次優(yōu)路徑增強信息， 直到構(gòu)造出一條次優(yōu)路徑。 按照同樣的方式， 可繼續(xù)構(gòu)造下一條次優(yōu)路徑。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6868在不相交多路徑中， 備用路徑可能比主路徑長得多， 為此引入了纏繞多路徑(Braid Multipath)的概念。 纏繞多路徑可以克服主路徑上單個節(jié)點死亡（失效）問題。 理想的纏繞多路徑是由一組纏繞路徑形成的。 一條纏繞路徑對應(yīng)于主路徑上的一個節(jié)點， 在網(wǎng)絡(luò)不包括這些節(jié)點時， 形成了從源節(jié)點到目的節(jié)點的優(yōu)化備用路徑。 纏繞路徑可作為主路徑的一條備用路徑， 而主路徑上的每個節(jié)點都有一條對應(yīng)的纏繞路徑，

39、 這些纏繞路徑構(gòu)成了從源節(jié)點到目的節(jié)點的纏繞多路徑。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議6969在理想纏繞多路徑中， 節(jié)點需要知道全局網(wǎng)絡(luò)拓?fù)洹?對于局部纏繞多路徑， 具有如下生成算法： （1） 建立主路徑。 （2） 發(fā)送備用路徑增強消息。 在建立主路徑后， 主路徑上的每個節(jié)點（除了源端和靠近源端的節(jié)點以外）都要發(fā)送備用路徑增強消息給自己的次優(yōu)節(jié)點（記為A）， 次優(yōu)節(jié)點A再尋找其最優(yōu)節(jié)點（記為B）， 傳播該備用路徑增強消息。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7070（3） 否定增強， 并繼續(xù)構(gòu)造。 如果B在主路徑上， 則B發(fā)回否定增強消息給A， A向次優(yōu)節(jié)點傳遞次優(yōu)路徑增強信息； 如果B不在主路徑

40、上， 則B繼續(xù)傳遞次優(yōu)路徑增強信息， 直到構(gòu)造出一條次優(yōu)路徑。 按照同樣的方式， 繼續(xù)構(gòu)造下一條次優(yōu)路徑。 備用路徑之間具有不同的優(yōu)先級。 當(dāng)主路徑失效時， 次優(yōu)路徑將被激活成為新的主路徑。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議71 7113.5.2 ReInForM路由路由ReInForM(Reliable Information Forwarding Multiple Path)路由是從數(shù)據(jù)源節(jié)點開始考慮的， 即考慮可靠性需求、 信道質(zhì)量以及WSN節(jié)點到匯聚節(jié)點的跳數(shù)， 來決定需要的傳輸路徑數(shù)目， 以及下一跳節(jié)點數(shù)目和相應(yīng)的節(jié)點， 從而實現(xiàn)滿足可靠要求的數(shù)據(jù)傳輸。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)

41、議7272ReInForM路由機制的基本思路是： 首先， 源節(jié)點根據(jù)傳輸?shù)目煽啃砸笥嬎阈枰膫鬏斅窂綌?shù)目； 其次， 在相鄰節(jié)點中選擇若干節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點， 并給每個節(jié)點按照一定比例分配路徑數(shù)目； 然后， 源節(jié)點將分配的路徑數(shù)目作為數(shù)據(jù)報頭中的一個字段發(fā)送給鄰居節(jié)點。 鄰居節(jié)點在接收到源節(jié)點的數(shù)據(jù)后， 將自己作為數(shù)據(jù)的源節(jié)點并重復(fù)上述數(shù)據(jù)源節(jié)點的選路過程。 以下介紹其實現(xiàn)過程。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議73731. 主路徑的建立根據(jù)路由策略， 選擇路由算法， 建立源節(jié)點到目的節(jié)點的主路徑。在ReInForM路由中， 定義了一個可靠性參數(shù)rs, 0rs1。 該參數(shù)表示系統(tǒng)要求的源節(jié)

42、點發(fā)送數(shù)據(jù)分組到匯聚節(jié)點的成功概率。 每個節(jié)點都知道自己到鄰居節(jié)點的信道質(zhì)量， 用信道差錯率es表示， 0es1， 并假設(shè)每個節(jié)點到其所有相鄰節(jié)點的信道質(zhì)量都相同。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7474傳感器節(jié)點通過如下機制知道自己到匯聚節(jié)點的跳數(shù)hs： 匯聚節(jié)點周期性地廣播路由更新消息， 其中包括一個到匯聚節(jié)點跳數(shù)的域， 節(jié)點收到路由更新消息后， 將消息中的到匯聚節(jié)點跳數(shù)加1， 并廣播這個消息。 這樣， 每個節(jié)點都能知道自己到達(dá)匯聚節(jié)點的跳數(shù)以及其相鄰節(jié)點到達(dá)匯聚節(jié)點的跳數(shù)。 源節(jié)點根據(jù)參數(shù)rs、 es和hs就可決定需要多少條傳輸路徑才能保證數(shù)據(jù)分組可靠地到達(dá)匯聚節(jié)點。 第13章無線傳感

43、器網(wǎng)絡(luò)的路由協(xié)議7575由于es為一條傳輸鏈路的錯誤率， 對于源節(jié)點， 經(jīng)過hs跳后數(shù)據(jù)分組到達(dá)匯聚節(jié)點的概率為(1es)hs， 經(jīng)過P條路徑后數(shù)據(jù)分組不能到達(dá)匯聚節(jié)點的概率為1(1es)hsP=1rs， 于是(13.5.1)如果需要的成功傳輸?shù)穆窂綌?shù)P大于源節(jié)點的相鄰節(jié)點數(shù)目， 則需要某些相鄰節(jié)點發(fā)送多份數(shù)據(jù)拷貝來滿足可靠性要求。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議76762. 下一跳節(jié)點的選擇和路徑分配當(dāng)源節(jié)點計算出需要的轉(zhuǎn)發(fā)路徑數(shù)后， 就需在相鄰節(jié)點中選擇下一跳的節(jié)點， 并對其分配相應(yīng)的轉(zhuǎn)發(fā)路徑。 根據(jù)源節(jié)點到匯聚節(jié)點的跳數(shù)， 可將相鄰節(jié)點分為三類： 與自己到達(dá)匯聚節(jié)點跳數(shù)相同的節(jié)點； 比

44、自己到達(dá)匯聚節(jié)點跳數(shù)少一個的節(jié)點； 以及比自己到達(dá)匯聚節(jié)點跳數(shù)多一個的節(jié)點， 分別用H0、 H、 H+表示。 源節(jié)點首先在H中選擇一個作為默認(rèn)的下一跳節(jié)點， 默認(rèn)的下一跳節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組的概率為1。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7777由于源節(jié)點到默認(rèn)下一跳節(jié)點的數(shù)據(jù)分組發(fā)送成功率為1es， 這條路程相當(dāng)于1es條成功轉(zhuǎn)發(fā)路徑。 如果1es大于或等于按照式(13.5.1)計算得到的路徑數(shù)， 則表明源節(jié)點只需要默認(rèn)下一跳節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組就能夠滿足可靠性要求； 否則， 還需要額外的轉(zhuǎn)發(fā)節(jié)點， 需要的額外路徑數(shù)為(13.5.2)第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7878額外路徑應(yīng)優(yōu)先從H中選取。

45、只有當(dāng)按照式(13.5.2)計算的P大于H 時， 需要從H0中選取節(jié)點。 只有當(dāng)P大于(H +H ）時， 才需要從H+中選取。 被選中的節(jié)點都要為源節(jié)點創(chuàng)建足夠的路徑數(shù)， 以確保所有選中節(jié)點能夠提供路徑總數(shù)為P。 我們可用PH 、 PH0和PH+分別表示從H0、 H 和H+所選擇的節(jié)點作為下一跳為源節(jié)點創(chuàng)建的路徑數(shù)目。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議7979設(shè)H0、H和H+中所選擇的節(jié)點數(shù)目分別為NH、 NH0和NH+， 于是有(13.5.3)PH、 PH0和PH+按照如下比例進(jìn)行分配： (13.5.4)第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議80803. 相鄰節(jié)點的路徑重新計算源節(jié)點s在發(fā)送的數(shù)據(jù)

46、分組頭部加上PH、 es和hs這三個參數(shù)。相鄰節(jié)點i在收到分組后， 按照與路徑數(shù)相同的概率決定是否轉(zhuǎn)發(fā)分組。 如果確定轉(zhuǎn)發(fā)該分組， 則節(jié)點i將自己作為源節(jié)點， 并按照式(13.5.2)， 用本節(jié)點的ri、 ei和hi重新計算所需的路徑數(shù)。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議81 81這里的ri是節(jié)點i為了保證s指定的可靠性而重新計算出的可靠性值， 按照下式計算：ri=1(1(1ei)hi1)PH(13.5.5)式中， (1ei)hi1表示從節(jié)點i成功傳送數(shù)據(jù)分組到匯聚節(jié)點的概率， (1(1ei)hi1)PH表示從所有的P條路徑都不能成功傳送數(shù)據(jù)分組到匯聚節(jié)點的概率。 第13章無線傳感器網(wǎng)絡(luò)的路由

47、協(xié)議828213.5.3 SPEED協(xié)議協(xié)議SPEED協(xié)議為一個實時路由協(xié)議， 可在一定程度上保證端到端的傳輸速率、 網(wǎng)絡(luò)擁塞控制以及負(fù)載平衡。 為實現(xiàn)實時性目標(biāo)， SPEED協(xié)議首先交換節(jié)點的傳輸延遲， 以得到網(wǎng)絡(luò)負(fù)載情況； 然后節(jié)點利用局部地理信息和傳輸速率信息進(jìn)行路由決策， 同時又通過相鄰節(jié)點的反饋機制以保證網(wǎng)絡(luò)傳輸速率不低于一個全局定義的閾值。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8383 SPEED協(xié)議主要由以下幾部分組成： 第一部分為延遲估計機制， 該機制用來估計WSN的負(fù)載情況， 并判斷WSN是否發(fā)生擁塞。 第二部分為SNGF算法(Stateless Nondeterministic

48、 Geographic Forwarding, SNGF)，用來選擇滿足傳輸速率要求的下一跳節(jié)點。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8484第三部分為鄰居反饋機制(Neighborhood Feedback Loop, NFL)， 是當(dāng)SNGF路由算法中找不到滿足傳輸速率要求的下一跳節(jié)點時采取的補償機制。 第四部分為反向壓力路由變更機制， 用來避免擁塞和路由空洞。 SPEED協(xié)議中各部分之間的關(guān)系如圖13.5.2所示。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8585圖13.5.2 SPEED協(xié)議框架及組成部分間的關(guān)系第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議86861. 延遲估計機制在SPEED協(xié)議中， 節(jié)點

49、記錄了其到達(dá)相鄰節(jié)點的通信延遲， 用來表示W(wǎng)SN局部的通信負(fù)載。 通信延遲主要是指在忽略傳輸延遲的情況下的發(fā)送延遲。 在帶寬有限的條件下， 如果用專門分組監(jiān)測節(jié)點間的通信延遲， 則開銷比較大。 SPEED協(xié)議采用數(shù)據(jù)包捎帶的方法得到節(jié)點之間的延遲估計機制， 其算法如下： 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8787發(fā)送節(jié)點給數(shù)據(jù)分組加上時間戳， 接收節(jié)點計算從收到數(shù)據(jù)分組到發(fā)出ACK的時間間隔， 并將其作為一個字段加入ACK報文， 發(fā)送節(jié)點收到ACK后， 從收發(fā)時間差中減去接收節(jié)點的處理時間， 得到一跳的通信延遲。 在更新記錄的延遲值時， 綜合考慮新計算的延遲值和原來記錄的延遲值， 更新的延遲值是

50、二者的指數(shù)加權(quán)平均。 節(jié)點將計算出的通信延遲通告相鄰節(jié)點。 假設(shè)節(jié)點A計算出到節(jié)點B的通信延遲， 并將這個通信延遲通告其相鄰節(jié)點C， 則節(jié)點C可以不必計算到節(jié)點B的通信延遲， 而使用節(jié)點A發(fā)送來的通信延遲直接與節(jié)點B通信。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議88882. SNGF算法節(jié)點將相鄰節(jié)點分為兩類： 比自己距離目標(biāo)區(qū)域近的節(jié)點和比自己距離目標(biāo)區(qū)域遠(yuǎn)的節(jié)點， 前者稱為候選轉(zhuǎn)發(fā)節(jié)點集合(Forwarding Candidate Set， FCS)。 節(jié)點計算到其FCS集合中的每個節(jié)點的傳輸速率。 傳輸速率定義為節(jié)點間的距離除以節(jié)點間的通信延遲。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8989如果節(jié)

51、點的FCS集合為空， 意味著分組走到了路由空洞中。 這時節(jié)點將丟棄分組， 并使用反向壓力信標(biāo)(Backpressure Beacon)消息告訴上一跳節(jié)點， 以避免分組再次走到這個路由空洞中。 根據(jù)傳輸速率是否滿足預(yù)定的傳輸速率閾值， FCS集合中的節(jié)點又分為兩類： 大于速率閾值的和小于速率閾值的相鄰節(jié)點。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議9090如果在FCS集合中， 節(jié)點的傳輸速率大于閾值， 則在這些節(jié)點中按一定概率分布選擇下一跳節(jié)點。 節(jié)點的傳輸速率越大， 被選中的概率就越大。 若FCS集合中所有節(jié)點的傳輸速率都小于閾值， 則采用NFL算法， 計算一個轉(zhuǎn)發(fā)概率， 并按照該概率轉(zhuǎn)發(fā)分組。 如果

52、決定轉(zhuǎn)發(fā)分組， FCS內(nèi)的節(jié)點就按照一定的概率分布選擇下一跳節(jié)點。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議91 913. 鄰居反饋機制為了保證節(jié)點間的數(shù)據(jù)傳輸滿足一定的傳輸速率要求， 引入NFL機制。 在NFL機制中，數(shù)據(jù)丟失和低于傳輸速率閾值的傳送都視為傳輸差錯。 MAC層收集差錯信息， 并把到相鄰節(jié)點的傳輸差錯率通告給轉(zhuǎn)發(fā)比例控制器(Relay Ratio Controller)， 轉(zhuǎn)發(fā)比例控制器根據(jù)這些差錯率計算出轉(zhuǎn)發(fā)概率， 供SNGF路由算法做出選路決定。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議9292滿足傳輸速率閾值的數(shù)據(jù)按照SNGF算法決定的路由傳輸出去， 而不滿足傳輸速率閾值的數(shù)據(jù)傳輸由鄰居NFL計算轉(zhuǎn)發(fā)概率。 該轉(zhuǎn)發(fā)概率表示網(wǎng)絡(luò)能夠滿足傳輸速率要求的程度， 因此節(jié)點按照這個概率進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議9393節(jié)點查看FCS集合中的節(jié)點時， 如果存在節(jié)點的傳輸差錯率為零， 則表明存在滿足傳輸速率要求的節(jié)點， 因而設(shè)轉(zhuǎn)發(fā)概率為1。 如果FCS集合中所有節(jié)點的傳輸差錯率都大于零， 則按照下式計算轉(zhuǎn)發(fā)概率：(13.5.6)式中， ei表示到FCS