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

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

2、到目的節(jié)點(diǎn)的通信路由， 并且所尋找到的路由還應(yīng)具有避免網(wǎng)絡(luò)擁塞、 均衡網(wǎng)絡(luò)流量的性能。一般不考慮或極少考慮節(jié)點(diǎn)能量的消耗。第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議3 3在WSN中， 各節(jié)點(diǎn)的能量是有限的。 節(jié)點(diǎn)的能量消耗完， 一般無法補(bǔ)充， 該節(jié)點(diǎn)隨之死亡。 因此， WSN的路由需要考慮節(jié)點(diǎn)的能量消耗問題， 使節(jié)點(diǎn)能量的消耗盡量要小。 另外， WSN中的節(jié)點(diǎn)數(shù)量往往很大， 各節(jié)點(diǎn)一般無法獲得整個(gè)網(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具有很強(qiáng)的應(yīng)用相關(guān)性。 由

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

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

5、能是采集的同一個(gè)信息， 因此會(huì)出現(xiàn)數(shù)據(jù)的冗余的現(xiàn)象， 需要在轉(zhuǎn)發(fā)節(jié)點(diǎn)進(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é)點(diǎn)一般采用隨機(jī)部署的方式獲取有關(guān)監(jiān)測區(qū)域的感知數(shù)據(jù)。 整個(gè)系統(tǒng)更關(guān)心的是感知數(shù)據(jù)， 而不是具體哪個(gè)節(jié)點(diǎn)獲取的信息， 因而WSN信息的獲得不依賴于節(jié)點(diǎn)的地址信息， 而是局部區(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、找到一個(gè)路由機(jī)制能適合所有的應(yīng)用目的和應(yīng)用環(huán)境， 這是WSN應(yīng)用相關(guān)性的一個(gè)體現(xiàn)。 這就要求應(yīng)用者應(yīng)從實(shí)際出發(fā)， 結(jié)合具體的應(yīng)用需求， 設(shè)計(jì)與之適應(yīng)的特定路由機(jī)制。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議10 1013.1.2 WSN路由協(xié)議的性能指標(biāo)及分類路由協(xié)議的性能指標(biāo)及分類1. 性能指標(biāo)WSN路由協(xié)議的設(shè)計(jì)目標(biāo)是： 延長網(wǎng)絡(luò)生命周期， 提高路由的容錯(cuò)能力， 形成可靠的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制。 評(píng)價(jià)一個(gè)WSN路由協(xié)議設(shè)計(jì)的性能指標(biāo)一般包括WSN的生命周期、 傳輸延遲、 魯棒性、 可擴(kuò)展性等。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議11 11（3） 魯棒性。 一個(gè)系統(tǒng)的魯棒性是指該系統(tǒng)在一定的參數(shù)攝動(dòng)（變化）下

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、 Geographic Forwarding, SNGF)，用來選擇滿足傳輸速率要求的下一跳節(jié)點(diǎn)。 第13章無線傳感器網(wǎng)絡(luò)的路由協(xié)議8484第三部分為鄰居反饋機(jī)制(Neighborhood Feedback Loop, NFL)， 是當(dāng)SNGF路由算法中找不到滿足傳輸速率要求的下一跳節(jié)點(diǎn)時(shí)采取的補(bǔ)償機(jī)制。 第四部分為反向壓力路由變更機(jī)制， 用來避免擁塞和路由空洞。 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. 延遲估計(jì)機(jī)制在SPEED協(xié)議中， 節(jié)點(diǎn)

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

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

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

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