無線傳感器網(wǎng)絡 WSN第2章 路由協(xié)議

1、無線傳感器網(wǎng)絡第二章 路由協(xié)議無線傳感器網(wǎng)絡概述（什么是路由協(xié)議）概述（什么是路由協(xié)議） 路由協(xié)議負責將數(shù)據(jù)分組從源節(jié)點通過路由協(xié)議負責將數(shù)據(jù)分組從源節(jié)點通過網(wǎng)絡轉(zhuǎn)發(fā)到目的節(jié)點，它主要包括兩個網(wǎng)絡轉(zhuǎn)發(fā)到目的節(jié)點，它主要包括兩個方面的功能：方面的功能： 尋找源節(jié)點和目的節(jié)點間的優(yōu)化路徑尋找源節(jié)點和目的節(jié)點間的優(yōu)化路徑（確定最佳路徑）（確定最佳路徑） 將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)（數(shù)據(jù)交換）（數(shù)據(jù)交換） 無線傳感器網(wǎng)絡ad hocad hoc、 無線局域網(wǎng)等傳統(tǒng)無線無線局域網(wǎng)等傳統(tǒng)無線網(wǎng)絡特點網(wǎng)絡特點 ad hoc、 無線局域網(wǎng)等傳統(tǒng)無線網(wǎng)絡的首無線局域網(wǎng)等傳統(tǒng)無線

2、網(wǎng)絡的首要目標是提供高服務質(zhì)量和公平高效地利要目標是提供高服務質(zhì)量和公平高效地利用網(wǎng)絡帶寬，用網(wǎng)絡帶寬， 這些網(wǎng)絡路由協(xié)議的主要任這些網(wǎng)絡路由協(xié)議的主要任務是尋找源節(jié)點到目的節(jié)點間通信延遲小務是尋找源節(jié)點到目的節(jié)點間通信延遲小的路徑，同時提高整個網(wǎng)絡的利用率，的路徑，同時提高整個網(wǎng)絡的利用率， 避避免產(chǎn)生通信擁塞并均衡網(wǎng)絡流量等，免產(chǎn)生通信擁塞并均衡網(wǎng)絡流量等， 而能而能量消耗問題不是這類網(wǎng)絡考慮的重點。量消耗問題不是這類網(wǎng)絡考慮的重點。無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡路由協(xié)議特點 傳感器網(wǎng)絡具有很強的應用相關性，不同傳感器網(wǎng)絡具有很強的應用相關性，不同應用中的路由協(xié)議可能差別很大，沒有一應用中的

3、路由協(xié)議可能差別很大，沒有一個通用的路由協(xié)議。此外，傳感器網(wǎng)絡的個通用的路由協(xié)議。此外，傳感器網(wǎng)絡的路由機制還經(jīng)常與數(shù)據(jù)融合技術聯(lián)系在一路由機制還經(jīng)常與數(shù)據(jù)融合技術聯(lián)系在一起，通過減少通信量而節(jié)省能量。因此，起，通過減少通信量而節(jié)省能量。因此，傳統(tǒng)無線網(wǎng)絡的路由協(xié)議不適應于無線傳傳統(tǒng)無線網(wǎng)絡的路由協(xié)議不適應于無線傳感器網(wǎng)絡。感器網(wǎng)絡。 在無線傳感器網(wǎng)絡中，節(jié)點能量有限且一在無線傳感器網(wǎng)絡中，節(jié)點能量有限且一般沒有能量補充，般沒有能量補充， 因此路由協(xié)議需要高效因此路由協(xié)議需要高效利用能量，同時傳感器網(wǎng)絡節(jié)點數(shù)目往往利用能量，同時傳感器網(wǎng)絡節(jié)點數(shù)目往往很大，節(jié)點只能獲取局部拓撲結(jié)構(gòu)信息，很大，節(jié)

4、點只能獲取局部拓撲結(jié)構(gòu)信息，路由協(xié)議要能在局部網(wǎng)絡信息的基礎上選路由協(xié)議要能在局部網(wǎng)絡信息的基礎上選擇合適的路徑。擇合適的路徑。無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡的路由協(xié)議特點 （1） 能量優(yōu)先。能量優(yōu)先。 傳統(tǒng)路由協(xié)議在選擇傳統(tǒng)路由協(xié)議在選擇最優(yōu)路徑時，最優(yōu)路徑時， 很少考慮節(jié)點的能量消耗很少考慮節(jié)點的能量消耗問題。問題。 而無線傳感器網(wǎng)絡中節(jié)點的能量而無線傳感器網(wǎng)絡中節(jié)點的能量有限，有限， 延長整個網(wǎng)絡的生存期成為傳感延長整個網(wǎng)絡的生存期成為傳感器網(wǎng)絡路由協(xié)議設計的重要目器網(wǎng)絡路由協(xié)議設計的重要目 標，標， 因因此需要考慮節(jié)點的能量消耗以及網(wǎng)絡能此需要考慮節(jié)點的能量消耗以及網(wǎng)絡能量均衡使用的問題

5、。量均衡使用的問題。無線傳感器網(wǎng)絡 （2） 基于局部拓撲信息。基于局部拓撲信息。 無線傳感器無線傳感器網(wǎng)絡為了節(jié)省通信能量，網(wǎng)絡為了節(jié)省通信能量， 通常采用多跳通常采用多跳的通信模式，的通信模式， 而節(jié)點有限的存儲資源和而節(jié)點有限的存儲資源和計算資源，計算資源， 使得節(jié)點不能存儲大量的使得節(jié)點不能存儲大量的由信息，由信息， 不能進行太復雜的路由計算。不能進行太復雜的路由計算。 在節(jié)點只能獲取局部拓撲信息和資源有在節(jié)點只能獲取局部拓撲信息和資源有限的情下，限的情下， 如何實現(xiàn)簡單高效的路由機如何實現(xiàn)簡單高效的路由機制是無線傳感器網(wǎng)絡的一個基本問題。制是無線傳感器網(wǎng)絡的一個基本問題。無線傳感器網(wǎng)絡

6、 （3） 以數(shù)據(jù)為中心。以數(shù)據(jù)為中心。 傳統(tǒng)的路由協(xié)議通常傳統(tǒng)的路由協(xié)議通常以地址作為節(jié)點的標識和路由的依據(jù)，無線傳以地址作為節(jié)點的標識和路由的依據(jù)，無線傳感器網(wǎng)絡中大量節(jié)點隨機部署，感器網(wǎng)絡中大量節(jié)點隨機部署， 所關注的是所關注的是監(jiān)測區(qū)域的感知數(shù)據(jù)，監(jiān)測區(qū)域的感知數(shù)據(jù)， 而不是具體哪節(jié)點獲而不是具體哪節(jié)點獲取的信息，取的信息， 不依賴于全網(wǎng)惟一的標識。不依賴于全網(wǎng)惟一的標識。 傳感傳感器網(wǎng)絡通常包含多個傳感器節(jié)點到數(shù)匯聚節(jié)點器網(wǎng)絡通常包含多個傳感器節(jié)點到數(shù)匯聚節(jié)點的數(shù)據(jù)流，的數(shù)據(jù)流， 按照對感知數(shù)據(jù)的需求、數(shù)據(jù)通按照對感知數(shù)據(jù)的需求、數(shù)據(jù)通信模式和流向等，信模式和流向等， 以數(shù)據(jù)為中心成消

7、息的轉(zhuǎn)以數(shù)據(jù)為中心成消息的轉(zhuǎn)發(fā)路徑。發(fā)路徑。無線傳感器網(wǎng)絡 （4） 應用相關。傳感器網(wǎng)絡的應用環(huán)境應用相關。傳感器網(wǎng)絡的應用環(huán)境千差萬別，千差萬別， 數(shù)據(jù)通信模式不同，數(shù)據(jù)通信模式不同， 沒有一個沒有一個路由機制適合所有的應用，路由機制適合所有的應用， 這是傳感器網(wǎng)這是傳感器網(wǎng)絡應用相關性的一個體現(xiàn)。絡應用相關性的一個體現(xiàn)。 設計者需要針設計者需要針對每一個具體應用的需求，對每一個具體應用的需求， 設計與之適應設計與之適應的特定路由機制。的特定路由機制。無線傳感器網(wǎng)絡傳感器網(wǎng)絡路由機制要求： （1） 能量高效。能量高效。 （2） 可擴展性?？蓴U展性。 （3） 魯棒性。魯棒性。 （4） 快速收斂

8、性?？焖偈諗啃?。無線傳感器網(wǎng)絡路由協(xié)議分類 （1） 能量感知路由協(xié)議。能量感知路由協(xié)議。 高效利用網(wǎng)絡能高效利用網(wǎng)絡能量是傳感器網(wǎng)絡路由協(xié)議的一個顯著特征，早量是傳感器網(wǎng)絡路由協(xié)議的一個顯著特征，早期提出的一些傳感器網(wǎng)絡路由協(xié)議往往僅考慮期提出的一些傳感器網(wǎng)絡路由協(xié)議往往僅考慮了能量因素。了能量因素。 為了強調(diào)高效利用能量的重要為了強調(diào)高效利用能量的重要性，性， 在此將它們劃分為能量感知路由協(xié)議。在此將它們劃分為能量感知路由協(xié)議。 能量感知路由協(xié)議從數(shù)據(jù)傳輸中的能量消耗出能量感知路由協(xié)議從數(shù)據(jù)傳輸中的能量消耗出發(fā)，發(fā)， 討論最優(yōu)能量消耗路徑以及最長網(wǎng)絡生討論最優(yōu)能量消耗路徑以及最長網(wǎng)絡生存期等

9、問題。存期等問題。無線傳感器網(wǎng)絡 （2） 基于查詢的路由協(xié)議?；诓樵兊穆酚蓞f(xié)議。 在諸如環(huán)境檢測、在諸如環(huán)境檢測、戰(zhàn)場評估等應用中，戰(zhàn)場評估等應用中， 需要不斷查詢傳感器節(jié)點采集需要不斷查詢傳感器節(jié)點采集的數(shù)據(jù)，的數(shù)據(jù)， 匯聚節(jié)點（查詢節(jié)點）匯聚節(jié)點（查詢節(jié)點） 發(fā)出任務查詢命，發(fā)出任務查詢命， 傳感器節(jié)點向查詢節(jié)點報告采集的數(shù)據(jù)。傳感器節(jié)點向查詢節(jié)點報告采集的數(shù)據(jù)。 在這類應在這類應用中，通信流量主要是查詢節(jié)點和傳感器節(jié)點之間用中，通信流量主要是查詢節(jié)點和傳感器節(jié)點之間的命令和數(shù)據(jù)傳輸，的命令和數(shù)據(jù)傳輸， 同時傳感器節(jié)點的采樣信息在同時傳感器節(jié)點的采樣信息在傳輸路徑上通常要進行數(shù)據(jù)融合，傳

10、輸路徑上通常要進行數(shù)據(jù)融合， 通過減少通信流通過減少通信流量來節(jié)省能量。量來節(jié)省能量。無線傳感器網(wǎng)絡 （3） 地理位置路由協(xié)議。地理位置路由協(xié)議。 在諸如目標跟蹤在諸如目標跟蹤類應用中，類應用中， 往往需要喚醒距離跟蹤目標最近往往需要喚醒距離跟蹤目標最近的傳感器節(jié)點，的傳感器節(jié)點， 以得到關于目標的更精確位以得到關于目標的更精確位置等相關信息。置等相關信息。 在這類應用在這類應用 中，中， 通常需要通常需要知道目的節(jié)點的精確或者大致地理位置。知道目的節(jié)點的精確或者大致地理位置。 把把節(jié)點的位置信息作為路由選擇的依據(jù)，節(jié)點的位置信息作為路由選擇的依據(jù)， 不僅不僅能夠完成節(jié)點路由功能，還可以降低系

11、統(tǒng)專能夠完成節(jié)點路由功能，還可以降低系統(tǒng)專門維護路由協(xié)議的能耗。門維護路由協(xié)議的能耗。無線傳感器網(wǎng)絡 （4） 可靠的路由協(xié)議。無線傳感器網(wǎng)絡的可靠的路由協(xié)議。無線傳感器網(wǎng)絡的某些應用對通信的服務質(zhì)量有較高要求，某些應用對通信的服務質(zhì)量有較高要求， 如如可靠性和實時性等?？煽啃院蛯崟r性等。 而在無線傳感器網(wǎng)絡中，而在無線傳感器網(wǎng)絡中， 鏈路的穩(wěn)定性難以保證，鏈路的穩(wěn)定性難以保證， 通信信道質(zhì)量比較通信信道質(zhì)量比較低，低， 拓撲變化比較頻繁，拓撲變化比較頻繁， 要實現(xiàn)服務質(zhì)量保要實現(xiàn)服務質(zhì)量保證，證， 需要設計相應的可靠的路由協(xié)議。需要設計相應的可靠的路由協(xié)議。無線傳感器網(wǎng)絡能量感知路由 能量路由

12、是最早提出的傳感器網(wǎng)能量路由是最早提出的傳感器網(wǎng)路路由機制之一，路路由機制之一， 它根據(jù)節(jié)點的它根據(jù)節(jié)點的可用能量（可用能量（power available，PA） 或傳輸路徑上的能量需求，或傳輸路徑上的能量需求， 選擇數(shù)據(jù)的轉(zhuǎn)發(fā)路徑。選擇數(shù)據(jù)的轉(zhuǎn)發(fā)路徑。 節(jié)點可用節(jié)點可用能量就是節(jié)點當前的剩余能量。能量就是節(jié)點當前的剩余能量。 圖圖 2-1 所示的網(wǎng)絡中，所示的網(wǎng)絡中， 大寫字大寫字母表示節(jié)點，母表示節(jié)點， 如節(jié)點如節(jié)點 A， 節(jié)點節(jié)點右側(cè)括號內(nèi)的數(shù)字表示節(jié)點的可右側(cè)括號內(nèi)的數(shù)字表示節(jié)點的可用能量。用能量。 圖中的雙向線表示節(jié)點圖中的雙向線表示節(jié)點之間的通信鏈路，之間的通信鏈路， 鏈路上的數(shù)

13、字鏈路上的數(shù)字表示在該鏈路上發(fā)送數(shù)據(jù)消耗的表示在該鏈路上發(fā)送數(shù)據(jù)消耗的能量。能量。 源節(jié)點是一般功能的傳感源節(jié)點是一般功能的傳感器節(jié)點，器節(jié)點， 完成數(shù)據(jù)采集工作。完成數(shù)據(jù)采集工作。 匯聚節(jié)點是數(shù)據(jù)發(fā)送的目標節(jié)點。匯聚節(jié)點是數(shù)據(jù)發(fā)送的目標節(jié)點。無線傳感器網(wǎng)絡 能量路由策略主要有以下幾種：能量路由策略主要有以下幾種：（1） 最大最大 PA 路由：路由： 從數(shù)據(jù)源到匯聚節(jié)點的所從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取節(jié)點有路徑中選取節(jié)點 PA 之和最大的路徑。之和最大的路徑。 （2） 最小能量消耗路由：最小能量消耗路由： 從數(shù)據(jù)源到匯聚節(jié)點從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取節(jié)點耗能之和最少的路徑。的所有

14、路徑中選取節(jié)點耗能之和最少的路徑。 （3） 最少跳數(shù)路由：最少跳數(shù)路由： 選取從數(shù)據(jù)源到匯聚節(jié)點選取從數(shù)據(jù)源到匯聚節(jié)點跳數(shù)最少的路徑。跳數(shù)最少的路徑。 （4） 最大最小最大最小 PA 節(jié)點路由：每條路徑上有多節(jié)點路由：每條路徑上有多個節(jié)點，且節(jié)點的可用能量不同，個節(jié)點，且節(jié)點的可用能量不同， 從中選取每條從中選取每條路徑中可用能量最小的節(jié)點來表示這條路徑的可用路徑中可用能量最小的節(jié)點來表示這條路徑的可用能量。能量。無線傳感器網(wǎng)絡能量多路徑路由 傳統(tǒng)網(wǎng)絡的路由機制往往選擇源節(jié)點到目的節(jié)點之傳統(tǒng)網(wǎng)絡的路由機制往往選擇源節(jié)點到目的節(jié)點之間跳數(shù)最小的路徑傳輸數(shù)據(jù)，間跳數(shù)最小的路徑傳輸數(shù)據(jù)， 但在無線傳

15、感器網(wǎng)絡但在無線傳感器網(wǎng)絡中，中， 如果頻繁使用同一條路徑傳輸數(shù)據(jù)，如果頻繁使用同一條路徑傳輸數(shù)據(jù)， 就會造就會造成該路徑上的節(jié)點因能量消耗過快而過早失效，成該路徑上的節(jié)點因能量消耗過快而過早失效， 從從而使整個網(wǎng)絡分割成互不相連的孤立部分，而使整個網(wǎng)絡分割成互不相連的孤立部分， 減少了減少了整個網(wǎng)絡的生存期。整個網(wǎng)絡的生存期。 為此，為此，RahulC. Shah 等人提等人提出了一種能量多路徑路由機制。出了一種能量多路徑路由機制。 該機制在源節(jié)點和目的節(jié)點之間建立多條路徑，該機制在源節(jié)點和目的節(jié)點之間建立多條路徑， 根根據(jù)路徑上節(jié)點的通信能量消耗以及節(jié)點的剩余能量據(jù)路徑上節(jié)點的通信能量消耗

16、以及節(jié)點的剩余能量情況，情況， 給每條路徑賦予一定的選擇概率，給每條路徑賦予一定的選擇概率， 使得數(shù)使得數(shù)據(jù)傳輸均衡消耗整個網(wǎng)絡的能量，據(jù)傳輸均衡消耗整個網(wǎng)絡的能量， 延長整個網(wǎng)絡的延長整個網(wǎng)絡的生存期。生存期。無線傳感器網(wǎng)絡 能量多路徑路由協(xié)議包括路徑建立、數(shù)據(jù)傳播和路能量多路徑路由協(xié)議包括路徑建立、數(shù)據(jù)傳播和路由維護三個過程。由維護三個過程。 路徑建立過程是該協(xié)議的重點內(nèi)容。路徑建立過程是該協(xié)議的重點內(nèi)容。 每個節(jié)點需每個節(jié)點需要知道到達目的節(jié)點的所有下一跳節(jié)點，要知道到達目的節(jié)點的所有下一跳節(jié)點， 并計算選并計算選擇每個下一跳節(jié)點傳輸數(shù)據(jù)的概率。擇每個下一跳節(jié)點傳輸數(shù)據(jù)的概率。 概率的選

17、擇是概率的選擇是根據(jù)節(jié)點到目的節(jié)點的通信代價來計算的，根據(jù)節(jié)點到目的節(jié)點的通信代價來計算的， 在下面在下面的描述中用的描述中用 Cost（Ni） 表示節(jié)點表示節(jié)點 i 到目的節(jié)點的到目的節(jié)點的通信代價。通信代價。 因為每個節(jié)點到達目的節(jié)點的路徑很多，因為每個節(jié)點到達目的節(jié)點的路徑很多， 所以這個代價值是各個路徑的加權(quán)平均值。所以這個代價值是各個路徑的加權(quán)平均值。 能量多能量多路徑路由的主要過程描述如下：路徑路由的主要過程描述如下：無線傳感器網(wǎng)絡 （1） 目的節(jié)點向鄰居節(jié)點廣播路徑建立消息，目的節(jié)點向鄰居節(jié)點廣播路徑建立消息， 啟啟動路徑建立過程。動路徑建立過程。 路徑建立消息中包含一個代價域，

18、路徑建立消息中包含一個代價域， 表示發(fā)出該消息的節(jié)點到目的節(jié)點路徑上的能量信表示發(fā)出該消息的節(jié)點到目的節(jié)點路徑上的能量信息，息， 初始值設置為零。初始值設置為零。 （2） 當節(jié)點收到鄰居節(jié)點發(fā)送的路徑建立消息時，當節(jié)點收到鄰居節(jié)點發(fā)送的路徑建立消息時， 相對發(fā)送該消息的鄰居節(jié)點，相對發(fā)送該消息的鄰居節(jié)點， 只有當自己距源節(jié)點只有當自己距源節(jié)點更近，更近， 而且距目的節(jié)點更遠的情況下，而且距目的節(jié)點更遠的情況下， 才需要轉(zhuǎn)發(fā)才需要轉(zhuǎn)發(fā)該消息，該消息， 否則將丟棄該消息。否則將丟棄該消息。無線傳感器網(wǎng)絡 （3） 如果節(jié)點決定轉(zhuǎn)發(fā)路徑建立消息，如果節(jié)點決定轉(zhuǎn)發(fā)路徑建立消息， 需需要計算新的代價值來替

19、換原來的代價值。當路要計算新的代價值來替換原來的代價值。當路徑建立消息從節(jié)點徑建立消息從節(jié)點 Ni 發(fā)送到節(jié)點發(fā)送到節(jié)點 Nj時，時， 該該路徑的通信代價值為節(jié)點路徑的通信代價值為節(jié)點 i 的代價值加上兩個的代價值加上兩個節(jié)點間的通信能量消耗，節(jié)點間的通信能量消耗， 即：即：),()(,ijiNjNiNNMetricNCostC無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡其中a為大于1的系統(tǒng)參數(shù)。無線傳感器網(wǎng)絡 （5）節(jié)點為路由表中每個下一跳節(jié)點什算）節(jié)點為路由表中每個下一跳節(jié)點什算選擇概率，節(jié)點選擇概率與能量消耗成反比。選擇概率，節(jié)點選擇概率與能量消耗成反比。節(jié)點節(jié)點Ni使用如下公式計算選擇節(jié)點使用如下公式

20、計算選擇節(jié)點Ni的概率：的概率：無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡 RahulC Shah提出的能量多路徑路由綜合提出的能量多路徑路由綜合考慮了通信路徑上的消耗能量和剩余能量考慮了通信路徑上的消耗能量和剩余能量，節(jié)點根據(jù)概率在路由表中選擇一個節(jié)點，節(jié)點根據(jù)概率在路由表中選擇一個節(jié)點作為路由的下一跳節(jié)點。由于這個概率是作為路由的下一跳節(jié)點。由于這個概率是與能量相關的，可以將通信能耗分散到多與能量相關的，可以將通信能耗分散到多條路徑上，從百可實現(xiàn)整個網(wǎng)絡的能量干條路徑上，從百可實現(xiàn)整個網(wǎng)絡的能量干穩(wěn)降級，最大限度地延長網(wǎng)絡的生存期穩(wěn)降級，最大限度地延長網(wǎng)絡的生存期。無線傳感器網(wǎng)絡基于查詢的路由基于查詢的

21、路由無線傳感器網(wǎng)絡 定向擴散（定向擴散（directed diffusion，DD） 是一種基于是一種基于查詢的路由機制。查詢的路由機制。 匯聚節(jié)點通過興趣消息（匯聚節(jié)點通過興趣消息（interest） 發(fā)出查詢?nèi)蝿?，采用洪泛方式傳播興趣消息到整個區(qū)發(fā)出查詢?nèi)蝿?，采用洪泛方式傳播興趣消息到整個區(qū)域或部分區(qū)域內(nèi)的所有傳感器節(jié)點。域或部分區(qū)域內(nèi)的所有傳感器節(jié)點。 興趣消息用來表興趣消息用來表示查詢的任務，表達網(wǎng)絡用戶對監(jiān)測區(qū)域內(nèi)感興趣的示查詢的任務，表達網(wǎng)絡用戶對監(jiān)測區(qū)域內(nèi)感興趣的信信息，息， 例如監(jiān)測區(qū)域內(nèi)的溫度、濕度和光照等環(huán)境信息。例如監(jiān)測區(qū)域內(nèi)的溫度、濕度和光照等環(huán)境信息。 在興趣消息的傳

22、播過程中，在興趣消息的傳播過程中， 協(xié)議逐跳地在每個傳感器協(xié)議逐跳地在每個傳感器節(jié)點上建立反向的從數(shù)據(jù)源到匯聚節(jié)點的數(shù)據(jù)傳輸梯節(jié)點上建立反向的從數(shù)據(jù)源到匯聚節(jié)點的數(shù)據(jù)傳輸梯度（度（gradient）。傳感器節(jié)點將采集到的數(shù)據(jù)沿著梯）。傳感器節(jié)點將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點。度方向傳送到匯聚節(jié)點。無線傳感器網(wǎng)絡 定向擴散路由機制可以分為周期性的興趣擴散、定向擴散路由機制可以分為周期性的興趣擴散、 梯度建立以及路徑加強三個階段。圖梯度建立以及路徑加強三個階段。圖 2-2 顯顯示了這三個階段的數(shù)據(jù)傳播路徑和方向。示了這三個階段的數(shù)據(jù)傳播路徑和方向。無線傳感器網(wǎng)絡DD協(xié)議內(nèi)容：協(xié)議內(nèi)容：節(jié)

23、點用一組節(jié)點用一組來命名它所生成的數(shù)據(jù)。來命名它所生成的數(shù)據(jù)。1.建立路由時，建立路由時，sink(匯聚節(jié)點）匯聚節(jié)點）flooding(廣播）包含屬性列表、上報間隔、持續(xù)時間、廣播）包含屬性列表、上報間隔、持續(xù)時間、地理區(qū)域等地理區(qū)域等 信息的查詢請求信息的查詢請求Interest （該過程本質(zhì)上是設置一個監(jiān)測任務，（該過程本質(zhì)上是設置一個監(jiān)測任務，通過分配不同屬性通過分配不同屬性 值來表示不同任務的描述符）。值來表示不同任務的描述符）。2.每個傳感器節(jié)點在收到嗜好（每個傳感器節(jié)點在收到嗜好（Interest）后保存在各自的）后保存在各自的Cache中。每個嗜好項中。每個嗜好項 (inter

24、est entry)包含一個時間標簽域包含一個時間標簽域(timestamp field)和若干個梯度域和若干個梯度域(gradient field， 按成本最小化和能量自適應原則引導數(shù)據(jù)擴散的方向按成本最小化和能量自適應原則引導數(shù)據(jù)擴散的方向)。3.當一個嗜好傳遍整個網(wǎng)絡后，從源節(jié)點當一個嗜好傳遍整個網(wǎng)絡后，從源節(jié)點(即嗜好所在區(qū)域的傳感器節(jié)點即嗜好所在區(qū)域的傳感器節(jié)點)到到sink節(jié)點節(jié)點 或基站之間的梯度就建立起來了?；蚧局g的梯度就建立起來了。4.一旦源節(jié)點采集到嗜好所需的數(shù)據(jù)，那么源節(jié)點沿著該嗜好的梯度路徑傳輸數(shù)據(jù)到一旦源節(jié)點采集到嗜好所需的數(shù)據(jù)，那么源節(jié)點沿著該嗜好的梯度路徑傳輸

25、數(shù)據(jù)到 sink節(jié)點或基站。其中，源節(jié)點采集的數(shù)據(jù)首先在本地采用數(shù)據(jù)融合技術進行整合，節(jié)點或基站。其中，源節(jié)點采集的數(shù)據(jù)首先在本地采用數(shù)據(jù)融合技術進行整合， 然后在網(wǎng)上傳輸。然后在網(wǎng)上傳輸。右圖描述右圖描述DD路由路由協(xié)議的工作原理協(xié)議的工作原理無線傳感器網(wǎng)絡在在Directed Diffusion中，可以對路徑進行修復。在建立多條數(shù)據(jù)源到中，可以對路徑進行修復。在建立多條數(shù)據(jù)源到Sink節(jié)點的路節(jié)點的路徑之后，徑之后，(探測梯度探測梯度)Sink節(jié)點可以選擇增強其中的一條路徑用于數(shù)據(jù)的傳輸，而同時保持另外節(jié)點可以選擇增強其中的一條路徑用于數(shù)據(jù)的傳輸，而同時保持另外一條低速數(shù)據(jù)傳輸?shù)穆窂揭粭l低

26、速數(shù)據(jù)傳輸?shù)穆窂剑〝?shù)據(jù)梯度）（數(shù)據(jù)梯度）。當高速路徑，也就是經(jīng)過增強的路徑出現(xiàn)故障時，。當高速路徑，也就是經(jīng)過增強的路徑出現(xiàn)故障時，Sink節(jié)點可以增強低速路徑，保證源節(jié)點到節(jié)點可以增強低速路徑，保證源節(jié)點到Sink節(jié)點的數(shù)據(jù)傳輸。雖然保持低速路徑的節(jié)點的數(shù)據(jù)傳輸。雖然保持低速路徑的過程需要消耗一些能量，但是在故障時，可以節(jié)省很多能量開銷。對于故障比較頻過程需要消耗一些能量，但是在故障時，可以節(jié)省很多能量開銷。對于故障比較頻繁的網(wǎng)絡，保持一條低速路徑是很有好處的。繁的網(wǎng)絡，保持一條低速路徑是很有好處的。DD路由協(xié)議的優(yōu)點：路由協(xié)議的優(yōu)點：1.采用多路徑采用多路徑,健壯性好健壯性好;2.節(jié)點只需

27、要和鄰居節(jié)點通信，因而不需要全局的地址機制，使用查詢驅(qū)動機制按節(jié)點只需要和鄰居節(jié)點通信，因而不需要全局的地址機制，使用查詢驅(qū)動機制按 需建立路由需建立路由,避免了保存全網(wǎng)信息；避免了保存全網(wǎng)信息；3.每個節(jié)點都可以進行數(shù)據(jù)融合操作，能減少數(shù)據(jù)通信量，節(jié)省能量消耗；每個節(jié)點都可以進行數(shù)據(jù)融合操作，能減少數(shù)據(jù)通信量，節(jié)省能量消耗；4.sink點根據(jù)實際情況采取增強或減弱方式能有效利用能量；點根據(jù)實際情況采取增強或減弱方式能有效利用能量；5.節(jié)點不需要維護網(wǎng)絡的拓撲結(jié)構(gòu)，數(shù)據(jù)的發(fā)送是基于需求的，因此它是一個非常節(jié)點不需要維護網(wǎng)絡的拓撲結(jié)構(gòu)，數(shù)據(jù)的發(fā)送是基于需求的，因此它是一個非常 節(jié)能的路由協(xié)議。節(jié)

28、能的路由協(xié)議。DD路由協(xié)議的缺點：路由協(xié)議的缺點：1.基于查詢驅(qū)動模型的，不適用于環(huán)境監(jiān)測的基于查詢驅(qū)動模型的，不適用于環(huán)境監(jiān)測的WSN；2.Gradient的建立開銷很大的建立開銷很大,不適合多不適合多sink點網(wǎng)絡；點網(wǎng)絡；3.數(shù)據(jù)聚合過程采用時間同步技術數(shù)據(jù)聚合過程采用時間同步技術,會帶來較大開銷和時延；會帶來較大開銷和時延；4.不同的應用中需要定義不同的命名方案，也就是不同的應用中需要定義不同的命名方案，也就是對，從而限制了它對，從而限制了它 的應用。的應用。無線傳感器網(wǎng)絡Rumor 路由協(xié)議（謠傳路由）：路由協(xié)議（謠傳路由）：Rumor Routing是在是在Directed Dif

29、fusion的基礎上演化而來的。通常情況下，的基礎上演化而來的。通常情況下，Directed Diffusion協(xié)議需要向整個網(wǎng)絡廣播興趣，而在某些應用中，只有少量的協(xié)議需要向整個網(wǎng)絡廣播興趣，而在某些應用中，只有少量的數(shù)據(jù)需要從源節(jié)點傳遞到數(shù)據(jù)需要從源節(jié)點傳遞到Sink節(jié)點。在這種情況下，沒有必要向整個網(wǎng)絡廣播興節(jié)點。在這種情況下，沒有必要向整個網(wǎng)絡廣播興趣。當趣。當WSN中的事件（對應著數(shù)據(jù)的傳遞）數(shù)量很少，而查詢（對應著興趣的廣中的事件（對應著數(shù)據(jù)的傳遞）數(shù)量很少，而查詢（對應著興趣的廣播）數(shù)量很多的時候，可以采用廣播事件的方法，以節(jié)省能量的消耗。播）數(shù)量很多的時候，可以采用廣播事件的方

30、法，以節(jié)省能量的消耗。Rumor Routing是一個介于事件廣播（向整個網(wǎng)絡廣播事件）和興趣廣播（向整個網(wǎng)絡廣是一個介于事件廣播（向整個網(wǎng)絡廣播事件）和興趣廣播（向整個網(wǎng)絡廣播興趣）之間的一種路由協(xié)議播興趣）之間的一種路由協(xié)議Rumor Routing核心思想：核心思想：1.借鑒了歐氏平面圖上任意兩條曲線交叉幾率很大的思想借鑒了歐氏平面圖上任意兩條曲線交叉幾率很大的思想2.當節(jié)點監(jiān)測到事件后將其保存，并創(chuàng)建稱為當節(jié)點監(jiān)測到事件后將其保存，并創(chuàng)建稱為Agent的生命周期較長的包括事件和的生命周期較長的包括事件和 源節(jié)點信息的數(shù)據(jù)包，將其按一條或多條隨機路徑在網(wǎng)絡中轉(zhuǎn)發(fā)源節(jié)點信息的數(shù)據(jù)包，將其按

31、一條或多條隨機路徑在網(wǎng)絡中轉(zhuǎn)發(fā)3.收到收到Agent的節(jié)點根據(jù)事件和源節(jié)點信息建立反向路徑，并將的節(jié)點根據(jù)事件和源節(jié)點信息建立反向路徑，并將Agent再次隨機發(fā)再次隨機發(fā) 送到相鄰節(jié)點，并可在再次發(fā)送前在送到相鄰節(jié)點，并可在再次發(fā)送前在Agent中增加其已知的事件信息中增加其已知的事件信息4.sink點的查詢請求也沿著一條隨機路徑轉(zhuǎn)發(fā)點的查詢請求也沿著一條隨機路徑轉(zhuǎn)發(fā),當兩路徑交叉時則路由建立當兩路徑交叉時則路由建立5.如不交叉如不交叉,sink點可點可flooding查詢請求查詢請求無線傳感器網(wǎng)絡 Rumor協(xié)議中Agent傳播和Agent路徑與查詢路徑的交叉在多在多sink點、查詢請求數(shù)目

32、很大、網(wǎng)絡事件很少的情況下，點、查詢請求數(shù)目很大、網(wǎng)絡事件很少的情況下，Rumor協(xié)議較為有效協(xié)議較為有效.但如果事件非常多但如果事件非常多,維護事件表和收發(fā)維護事件表和收發(fā)Agent帶來的開銷會很大帶來的開銷會很大。無線傳感器網(wǎng)絡地理位置路由無線傳感器網(wǎng)絡 在傳感器網(wǎng)絡中，節(jié)點通常需要獲取它的在傳感器網(wǎng)絡中，節(jié)點通常需要獲取它的位置信息，這樣它采集的數(shù)據(jù)才有意義。位置信息，這樣它采集的數(shù)據(jù)才有意義。如在森林防火的應用中，消防人員不僅要如在森林防火的應用中，消防人員不僅要知道森林中發(fā)生火災事件，而且還要知道知道森林中發(fā)生火災事件，而且還要知道火災的具體位置。地理位置路由假設節(jié)點火災的具體位置。

33、地理位置路由假設節(jié)點知道自己的地理位置信息，以及目的節(jié)點知道自己的地理位置信息，以及目的節(jié)點或者目的區(qū)域的地理位置，利用這些地理或者目的區(qū)域的地理位置，利用這些地理位置信息作為路由選擇的依據(jù)，節(jié)點按照位置信息作為路由選擇的依據(jù)，節(jié)點按照一定策略轉(zhuǎn)發(fā)數(shù)據(jù)到目的節(jié)點。地理位置一定策略轉(zhuǎn)發(fā)數(shù)據(jù)到目的節(jié)點。地理位置的精確度和代價相關，在不同的應用中會的精確度和代價相關，在不同的應用中會選擇不同精確度的位置信息來實現(xiàn)數(shù)據(jù)的選擇不同精確度的位置信息來實現(xiàn)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。路由轉(zhuǎn)發(fā)。無線傳感器網(wǎng)絡 GEAR ： GEAR路由協(xié)議路由協(xié)議Geographic and Energy Aware Routing無線

34、傳感器網(wǎng)絡GEAR GEAR ： GEAR GEAR路由協(xié)議路由協(xié)議Geographic and Energy Aware RoutingGeographic and Energy Aware Routing 應用建立到特定區(qū)域的路由建立到特定區(qū)域的路由查詢工作方式查詢工作方式 前提已知目標區(qū)域的位置信息已知目標區(qū)域的位置信息節(jié)點知道自己位置信息和剩余能量節(jié)點知道自己位置信息和剩余能量節(jié)點間無線鏈路是對稱的節(jié)點間無線鏈路是對稱的無線傳感器網(wǎng)絡GEAR路由過程 分兩個階段：查詢消息到達目的區(qū)域的路徑查詢消息在目標區(qū)域的傳播 選路依據(jù)節(jié)點到查詢區(qū)域通信能量能耗節(jié)點本身的剩余能量最小代價節(jié)點為轉(zhuǎn)發(fā)節(jié)

35、點無線傳感器網(wǎng)絡GEAR路由過程無線傳感器網(wǎng)絡GEAR路由過程 查詢在監(jiān)測區(qū)域內(nèi)傳送：洪泛方式，迭代地理轉(zhuǎn)發(fā) 將目標區(qū)域分解為若干子區(qū)域、向子區(qū)域的中心位置轉(zhuǎn)發(fā)無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡無線傳感器網(wǎng)絡GEM 路由 GEM（graphembedding）路由是一種適用于數(shù)據(jù)中心存儲方式的地理路由。無線傳感器網(wǎng)絡傳感器網(wǎng)絡存儲監(jiān)測數(shù)據(jù)方式 本地存儲（localstorage） 外部存儲（externalstorage） 數(shù)據(jù)中心存儲（data-centricstorage）無線傳感器網(wǎng)絡本地存儲方式 在本地存儲方式中，節(jié)點首先將監(jiān)測數(shù)據(jù)保存在在本地存儲方式中，節(jié)點首先將監(jiān)測數(shù)據(jù)保存在本地存儲器中

36、，并在收到查詢命令后，將相關數(shù)本地存儲器中，并在收到查詢命令后，將相關數(shù)據(jù)發(fā)送給匯聚節(jié)點。據(jù)發(fā)送給匯聚節(jié)點。 本地存儲方式中，網(wǎng)絡傳輸?shù)臄?shù)據(jù)都是匯聚節(jié)點本地存儲方式中，網(wǎng)絡傳輸?shù)臄?shù)據(jù)都是匯聚節(jié)點感興趣的數(shù)據(jù)，網(wǎng)絡傳輸效率高，但是需要每個感興趣的數(shù)據(jù)，網(wǎng)絡傳輸效率高，但是需要每個節(jié)點都具有相對較大的存儲空間，數(shù)據(jù)融合只能節(jié)點都具有相對較大的存儲空間，數(shù)據(jù)融合只能在傳輸過程中進行，并且匯聚節(jié)點需要經(jīng)過較長在傳輸過程中進行，并且匯聚節(jié)點需要經(jīng)過較長的延遲后才能獲得查詢數(shù)據(jù)。的延遲后才能獲得查詢數(shù)據(jù)。無線傳感器網(wǎng)絡外部存儲方式 在外部存儲方式下，節(jié)點在獲得監(jiān)測數(shù)據(jù)后，不在外部存儲方式下，節(jié)點在獲得監(jiān)測

37、數(shù)據(jù)后，不論匯聚節(jié)點目前是否對該數(shù)據(jù)感興趣，都主動地論匯聚節(jié)點目前是否對該數(shù)據(jù)感興趣，都主動地把數(shù)據(jù)發(fā)送給匯聚節(jié)點。把數(shù)據(jù)發(fā)送給匯聚節(jié)點。 外部存儲方式中，節(jié)點將采集數(shù)據(jù)及時傳輸給匯外部存儲方式中，節(jié)點將采集數(shù)據(jù)及時傳輸給匯聚節(jié)點，可以提高傳感器網(wǎng)絡對突發(fā)事件的反應聚節(jié)點，可以提高傳感器網(wǎng)絡對突發(fā)事件的反應速度，但是監(jiān)測數(shù)據(jù)不斷發(fā)送給匯聚節(jié)點，一方速度，但是監(jiān)測數(shù)據(jù)不斷發(fā)送給匯聚節(jié)點，一方面由于有些數(shù)據(jù)不是匯聚節(jié)點感興趣的，造成了面由于有些數(shù)據(jù)不是匯聚節(jié)點感興趣的，造成了網(wǎng)絡能量的浪費；另一方面容易使得匯聚節(jié)點附網(wǎng)絡能量的浪費；另一方面容易使得匯聚節(jié)點附近形成網(wǎng)絡熱點，降低傳感器網(wǎng)絡的吞吐率。

38、近形成網(wǎng)絡熱點，降低傳感器網(wǎng)絡的吞吐率。無線傳感器網(wǎng)絡數(shù)據(jù)中心存儲方式 在數(shù)據(jù)中心存儲方式下，首先對可能的監(jiān)測事件進行命名，在數(shù)據(jù)中心存儲方式下，首先對可能的監(jiān)測事件進行命名，然后按照一定的策略將每一個事件映射到一個地理位置上，然后按照一定的策略將每一個事件映射到一個地理位置上，距離這個位置最近的節(jié)點作為該事件的負責節(jié)點。節(jié)點在距離這個位置最近的節(jié)點作為該事件的負責節(jié)點。節(jié)點在監(jiān)測到事件后，把相關數(shù)據(jù)發(fā)送到映射位置。負責節(jié)點接監(jiān)測到事件后，把相關數(shù)據(jù)發(fā)送到映射位置。負責節(jié)點接收數(shù)據(jù)，進行數(shù)據(jù)融合并存儲在本地。收數(shù)據(jù)，進行數(shù)據(jù)融合并存儲在本地。 數(shù)據(jù)中心存儲方式在網(wǎng)絡中選擇不同的負責節(jié)點實現(xiàn)不同

39、數(shù)據(jù)中心存儲方式在網(wǎng)絡中選擇不同的負責節(jié)點實現(xiàn)不同事件監(jiān)測數(shù)據(jù)的融合和存儲，是介于本地存儲和外部存儲事件監(jiān)測數(shù)據(jù)的融合和存儲，是介于本地存儲和外部存儲的之間的一種方式，在查詢延遲、能量消耗和存儲空間等的之間的一種方式，在查詢延遲、能量消耗和存儲空間等多項指標間進行折中。由于傳感器網(wǎng)絡處理的事件往往有多項指標間進行折中。由于傳感器網(wǎng)絡處理的事件往往有多種，數(shù)據(jù)中心存儲方式能夠?qū)⒕W(wǎng)絡通信流量、處理流量多種，數(shù)據(jù)中心存儲方式能夠?qū)⒕W(wǎng)絡通信流量、處理流量和存儲流量在網(wǎng)絡中均勻分攤，從而有效避免了網(wǎng)絡熱點和存儲流量在網(wǎng)絡中均勻分攤，從而有效避免了網(wǎng)絡熱點的產(chǎn)生。的產(chǎn)生。無線傳感器網(wǎng)絡GEM 路由 GEM

40、（graphembedding）路由是一種適用于）路由是一種適用于數(shù)據(jù)中心存儲方式的地理路由。數(shù)據(jù)中心存儲方式的地理路由。 GEM路由的基本思想是建立一個虛擬極坐標系統(tǒng)路由的基本思想是建立一個虛擬極坐標系統(tǒng)（virtualpolarcoordinatesystem，VPCS），），用來表示實際的網(wǎng)絡拓撲結(jié)構(gòu)。網(wǎng)絡中的節(jié)點形用來表示實際的網(wǎng)絡拓撲結(jié)構(gòu)。網(wǎng)絡中的節(jié)點形成一個以匯聚節(jié)點為根的帶環(huán)樹（成一個以匯聚節(jié)點為根的帶環(huán)樹（ringedree），），每個節(jié)點用到樹根的跳數(shù)距離和角度范圍來表示，每個節(jié)點用到樹根的跳數(shù)距離和角度范圍來表示，節(jié)點間的數(shù)據(jù)路由通過這個帶環(huán)樹實現(xiàn)。節(jié)點間的數(shù)據(jù)路由通過這個

41、帶環(huán)樹實現(xiàn)。無線傳感器網(wǎng)絡虛擬極坐標系統(tǒng) 第一步： 生成樹型結(jié)構(gòu)。 第二步： 反饋子樹大小。 第三步： 確定虛擬角度范圍。無線傳感器網(wǎng)絡對網(wǎng)絡拓撲變化的適應 除了匯聚節(jié)點外每個節(jié)點只有一個父節(jié)點； 每個節(jié)點的跳數(shù)值為父節(jié)點的跳數(shù)值加 1； 每個節(jié)點的角度范圍是父節(jié)點的角度范圍的子集； 每個節(jié)點的子節(jié)點角度范圍不相交。無線傳感器網(wǎng)絡基于虛擬極坐標系統(tǒng)的路由算法無線傳感器網(wǎng)絡邊界定位的地理路由 在傳感器網(wǎng)絡的實際應用中，在傳感器網(wǎng)絡的實際應用中， 如果每個節(jié)點都需要知道如果每個節(jié)點都需要知道自己的精確位置信息，自己的精確位置信息， 那么路由代價比較大。那么路由代價比較大。 地理位置地理位置路由研究

42、中的一個重要方向就是如何在保證路由正確性的路由研究中的一個重要方向就是如何在保證路由正確性的前提下，前提下， 盡量減少需要精確位置信息的節(jié)點數(shù)目，盡量減少需要精確位置信息的節(jié)點數(shù)目， 以及以及路由機制對節(jié)點精確位置信息的依賴。路由機制對節(jié)點精確位置信息的依賴。 文獻文獻13提出了一種只需要少數(shù)節(jié)點精確位置信息就提出了一種只需要少數(shù)節(jié)點精確位置信息就可以進行正確路由的地理路由機制。可以進行正確路由的地理路由機制。 其基本思想是首先其基本思想是首先通過網(wǎng)絡中知道自身位置信息的節(jié)點確定一個全局坐標系，通過網(wǎng)絡中知道自身位置信息的節(jié)點確定一個全局坐標系， 然后確定其他節(jié)點在這個坐標系中的位置，然后確定

43、其他節(jié)點在這個坐標系中的位置， 最后根據(jù)節(jié)最后根據(jù)節(jié)點在坐標系中的位置進行數(shù)據(jù)路由。知道自身位置信息的點在坐標系中的位置進行數(shù)據(jù)路由。知道自身位置信息的節(jié)點通常是網(wǎng)絡中較為特殊的信標節(jié)點。節(jié)點通常是網(wǎng)絡中較為特殊的信標節(jié)點。 當所有節(jié)點的坐標位置信息確定后，當所有節(jié)點的坐標位置信息確定后， 協(xié)議使用貪婪算法協(xié)議使用貪婪算法選擇路由。選擇路由。 因此，因此， 協(xié)議的關鍵部分是利用信標節(jié)點確定協(xié)議的關鍵部分是利用信標節(jié)點確定全局坐標系以及確定其他節(jié)點在坐標系中的位置。全局坐標系以及確定其他節(jié)點在坐標系中的位置。 文獻文獻13給出了下面三種策略。給出了下面三種策略。無線傳感器網(wǎng)絡邊界節(jié)點均為信標節(jié)點

44、無線傳感器網(wǎng)絡使用兩個信標節(jié)點 在邊界節(jié)點均為信標節(jié)點策略中在邊界節(jié)點均為信標節(jié)點策略中 , 仍然需要網(wǎng)絡邊界上仍然需要網(wǎng)絡邊界上所有節(jié)點都知道自己的精確地理位置所有節(jié)點都知道自己的精確地理位置 , 網(wǎng)絡部署的成本仍網(wǎng)絡部署的成本仍然很高。本策略只使用兩個信標節(jié)點然很高。本策略只使用兩個信標節(jié)點 , 而而 不再不再 需要需要 所所有邊有邊 界節(jié)界節(jié) 點的精點的精 確位確位 置信息置信息 , 從而大大減少了網(wǎng)絡部從而大大減少了網(wǎng)絡部署的成本。署的成本。 在該策略中在該策略中 , 仍然將節(jié)點分為邊界節(jié)點和仍然將節(jié)點分為邊界節(jié)點和 非邊界非邊界 節(jié)點。節(jié)點。 邊界節(jié)邊界節(jié) 點只點只 知道自知道自 己

45、處己處 于網(wǎng)絡的邊緣于網(wǎng)絡的邊緣 , 但不知道自己但不知道自己的精確位置信息。該策略的精確位置信息。該策略 首先首先 通過通過 邊界節(jié)邊界節(jié) 點間點間 的信息的信息 交換交換 機制建立全局坐標系機制建立全局坐標系 , 然后引入兩個然后引入兩個 beacon 節(jié)點節(jié)點以以 減少減少 全局全局 坐標系坐標系 的誤的誤 差差 , 最后按最后按 照前照前 述方法計算述方法計算非邊界節(jié)點在全局坐標系中的位置。非邊界節(jié)點在全局坐標系中的位置。無線傳感器網(wǎng)絡使用一個信標節(jié)點 上述策略中假設節(jié)點知道自己是邊界節(jié)點上述策略中假設節(jié)點知道自己是邊界節(jié)點 , 實際網(wǎng)絡中節(jié)點的部署具有隨機性實際網(wǎng)絡中節(jié)點的部署具有隨

46、機性 , 不能不能確定自己是否為實際的網(wǎng)絡邊界節(jié)點。本確定自己是否為實際的網(wǎng)絡邊界節(jié)點。本策略策略 利用利用 一個一個 信標節(jié)信標節(jié) 點確點確 定一組定一組 邊界邊界 節(jié)點節(jié)點 , 然后采用上面第二種策略介紹的算然后采用上面第二種策略介紹的算法確定全局法確定全局 坐標系坐標系 并計并計 算節(jié)點算節(jié)點 在坐在坐 標標系系 中的位中的位 置信置信 息。息。無線傳感器網(wǎng)絡特點 與與 G EAR 路由相比路由相比 , 邊界定位的路邊界定位的路 由機由機 制只制只需需 要很要很 少節(jié)少節(jié) 點知道點知道 精確精確 的位的位 置置 信息信息 , 減少減少了對傳感器節(jié)點的功能要求了對傳感器節(jié)點的功能要求 ,

47、降低了傳感器降低了傳感器 網(wǎng)絡網(wǎng)絡的的 部署部署 成本。但成本。但 為了為了 確定全確定全 局坐局坐 標系和節(jié)點標系和節(jié)點在坐標系中的位置信息在坐標系中的位置信息 , 節(jié)點需要進行節(jié)點需要進行 大量大量 的的信息信息 交換交換 , 通通 信開信開 銷很大。銷很大。 此外此外 , 由于算法由于算法采用了迭代采用了迭代 過過 程程 確定確定 節(jié)節(jié) 點點 的的 位位 置置 , 計計 算算 出出 的的 節(jié)點節(jié)點 位位 置置 精精 度度 和迭和迭 代代 次次 數(shù)數(shù) 相相 關。關。與與G E M 路由相比路由相比 , 邊界定位路由建立的全局邊界定位路由建立的全局坐標系坐標系 更加接更加接 近節(jié)點近節(jié)點 實

48、際實際 位置位置 , 且對且對 于網(wǎng)于網(wǎng) 絡絡拓撲的變化調(diào)整比較簡單。拓撲的變化調(diào)整比較簡單。無線傳感器網(wǎng)絡可靠路由協(xié)議 某些傳感器網(wǎng)絡應用對于數(shù)據(jù)傳輸?shù)目煽磕承﹤鞲衅骶W(wǎng)絡應用對于數(shù)據(jù)傳輸?shù)目煽?性提性提 出了出了 比比較高較高 的要的要 求求 , 因此傳因此傳 感器感器 網(wǎng)絡路由中的一個重要方面網(wǎng)絡路由中的一個重要方面是研究可靠路由協(xié)議。傳感器節(jié)點由于有限能量供應和工是研究可靠路由協(xié)議。傳感器節(jié)點由于有限能量供應和工作環(huán)境惡劣經(jīng)常面臨失效問題作環(huán)境惡劣經(jīng)常面臨失效問題 , 這為研究適合于傳感器網(wǎng)這為研究適合于傳感器網(wǎng)絡的可靠路由協(xié)議增加了困難。絡的可靠路由協(xié)議增加了困難。 目前目前 , 研究

49、人員提出的可靠路由協(xié)研究人員提出的可靠路由協(xié) 議主議主 要從要從 兩個方兩個方 面考面考 慮慮 : 一是利一是利 用節(jié)用節(jié) 點的點的 冗冗 余性提供多條路徑以保證余性提供多條路徑以保證通信可靠通信可靠 性性 ; 二是建二是建 立對立對 傳輸傳輸 可靠性可靠性 的估的估 計機制計機制 , 從從 而保而保 證每證每 跳傳輸?shù)目煽啃?。另外跳傳輸?shù)目煽啃?。另?, 某些傳感器網(wǎng)絡某些傳感器網(wǎng)絡應用需要應用需要 節(jié)點間節(jié)點間 通信通信 具有具有 一定的一定的 實時實時 性。性。無線傳感器網(wǎng)絡基于不相交路徑的多路徑路由機制 在傳感器網(wǎng)絡中在傳感器網(wǎng)絡中 , 引入多路徑路由是為了提高引入多路徑路由是為了提高

50、 數(shù)據(jù)數(shù)據(jù) 傳輸傳輸 的可靠的可靠 性和性和 實現(xiàn)網(wǎng)實現(xiàn)網(wǎng) 絡負絡負 載平衡。在載平衡。在多路徑路由中多路徑路由中 , 如何建立數(shù)據(jù)源節(jié)點到如何建立數(shù)據(jù)源節(jié)點到 匯聚節(jié)匯聚節(jié) 點的點的 多條多條 路徑是路徑是 首要首要 問題。在問題。在 定向擴散路由定向擴散路由中中 , 當有數(shù)據(jù)查詢需要時當有數(shù)據(jù)查詢需要時 , 匯聚節(jié)點匯聚節(jié)點 首先通首先通 過過洪洪 泛興趣泛興趣 消息消息 形成形成 傳輸梯傳輸梯 度度 , 然后建立數(shù)據(jù)然后建立數(shù)據(jù)源節(jié)點到匯聚節(jié)點的多條路徑源節(jié)點到匯聚節(jié)點的多條路徑 , 最后通過最后通過 路徑路徑 加強加強 消息選消息選 擇一擇一 條主路條主路 徑傳徑傳 輸數(shù)據(jù)。當主路輸數(shù)

51、據(jù)。當主路徑失敗時徑失敗時 , 定向擴散路由需要使用周期性低速率定向擴散路由需要使用周期性低速率的洪泛過程重新建立主路徑。的洪泛過程重新建立主路徑。無線傳感器網(wǎng)絡局部不相交路徑的構(gòu)建無線傳感器網(wǎng)絡纏繞多路徑無線傳感器網(wǎng)絡ReInForM 路由 在傳感器網(wǎng)絡在傳感器網(wǎng)絡 中中 , 傳傳 感感 器器 節(jié)節(jié) 點點 是是 數(shù)數(shù) 據(jù)據(jù) 源源 , 把把 監(jiān)測監(jiān)測 數(shù)數(shù) 據(jù)據(jù) 發(fā)發(fā) 送送 給給 匯匯 聚聚 節(jié)節(jié) 點。點。 ReInForM( Reliable Information Forwarding using Multiple paths) 路由從數(shù)路由從數(shù)據(jù)源節(jié)點據(jù)源節(jié)點 開始開始 , 考慮可靠性需

52、求、考慮可靠性需求、 信道質(zhì)量信道質(zhì)量以及傳感器節(jié)點到匯聚節(jié)點以及傳感器節(jié)點到匯聚節(jié)點 的跳的跳 數(shù)數(shù) , 決定需決定需 要的要的 傳輸傳輸 路徑數(shù)路徑數(shù) 目目 , 以及下一跳節(jié)點數(shù)目和以及下一跳節(jié)點數(shù)目和相應的節(jié)點相應的節(jié)點 , 實現(xiàn)滿足可靠要求的數(shù)據(jù)傳輸。實現(xiàn)滿足可靠要求的數(shù)據(jù)傳輸。無線傳感器網(wǎng)絡SPEED 協(xié)議 在有些傳感器網(wǎng)絡應用中在有些傳感器網(wǎng)絡應用中 , 匯聚節(jié)點需要根據(jù)采集數(shù)據(jù)實匯聚節(jié)點需要根據(jù)采集數(shù)據(jù)實時作出反應時作出反應 , 因此傳感器節(jié)點到匯聚節(jié)點的因此傳感器節(jié)點到匯聚節(jié)點的 數(shù)據(jù)數(shù)據(jù) 通通 道要道要 保保 持持 一一 定的定的 傳傳 輸輸 速速 率。率。SP EE D 協(xié)

53、議協(xié)議 33 是是 一一 個個 實實 時路時路 由由 協(xié)議協(xié)議 , 在一定程度上實現(xiàn)了端到端的傳在一定程度上實現(xiàn)了端到端的傳輸速率保證、網(wǎng)絡擁塞控制以及負載平衡機制。為實現(xiàn)上輸速率保證、網(wǎng)絡擁塞控制以及負載平衡機制。為實現(xiàn)上述目標述目標 , SP E ED 協(xié)議首先交換節(jié)協(xié)議首先交換節(jié) 點的點的 傳輸傳輸 延遲延遲 , 以以 得到得到 網(wǎng)網(wǎng) 絡負絡負 載情載情 況況 ; 然后節(jié)點利用局部地理信息和傳然后節(jié)點利用局部地理信息和傳輸速率信息作出路由決輸速率信息作出路由決 定定 , 同時通過鄰居反饋機制保證網(wǎng)同時通過鄰居反饋機制保證網(wǎng)絡傳輸速率在一個全局定義的傳輸速率閾值之上。節(jié)點還絡傳輸速率在一個

54、全局定義的傳輸速率閾值之上。節(jié)點還通過反向壓力路由變更機制避開延遲太大的鏈路和路由空通過反向壓力路由變更機制避開延遲太大的鏈路和路由空洞。洞。無線傳感器網(wǎng)絡SPEED 協(xié)議框架 (1) 延遲估計機制延遲估計機制 , 用來得到網(wǎng)絡的負載情況用來得到網(wǎng)絡的負載情況 , 判斷網(wǎng)絡是判斷網(wǎng)絡是否發(fā)生擁塞否發(fā)生擁塞 ; ( 2) SNGF 算法算法 ( stateless non-deterministic geogr aphic forwa rding , SN GF ) , 用來選擇滿足傳輸速率要用來選擇滿足傳輸速率要求的下一跳節(jié)點求的下一跳節(jié)點 ; ( 3 ) 鄰居反饋策略鄰居反饋策略 ( nei

55、gh borhood feedback loop , NF L) , 是當是當 SNG F 路由算法中找不到滿足傳輸速率要求的下路由算法中找不到滿足傳輸速率要求的下一跳節(jié)點時采取的補償機制一跳節(jié)點時采取的補償機制 ; ( 4) 反向壓力路由變更機制反向壓力路由變更機制 , 用來避免擁塞和路由空洞。用來避免擁塞和路由空洞。無線傳感器網(wǎng)絡. 延遲估計 在在 SPE ED 協(xié)議中協(xié)議中 , 節(jié)點記節(jié)點記 錄錄 到到 鄰鄰 居居 節(jié)點節(jié)點 的的 通通 信信 延延 遲遲 , 用用 來來 表示表示 網(wǎng)網(wǎng) 絡絡 局局 部部 的通的通 信信 負載。這里的通信延遲主要是指發(fā)送延遲負載。這里的通信延遲主要是指發(fā)送

56、延遲 , 而而忽略傳輸延遲。在帶寬有限的網(wǎng)絡條件下忽略傳輸延遲。在帶寬有限的網(wǎng)絡條件下 , 如果用專門分組探測節(jié)點間的如果用專門分組探測節(jié)點間的通信延遲通信延遲 , 開銷比較大。開銷比較大。SP E ED 協(xié)議采用數(shù)據(jù)包捎帶協(xié)議采用數(shù)據(jù)包捎帶 的方法的方法,得到節(jié)得到節(jié)點之間的通信延遲點之間的通信延遲 , 具體過程如下具體過程如下 :發(fā)發(fā) 送節(jié)點送節(jié)點 給數(shù)給數(shù) 據(jù)分組據(jù)分組 加上加上 時時 間間 戳戳 ; 接接 收收 節(jié)節(jié) 點點 計計 算從算從 收收 到到 數(shù)數(shù) 據(jù)據(jù) 分分 組組 到到 發(fā)出發(fā)出 ACK 的時的時 間間間間 隔隔 , 并并將將 其作其作 為一個為一個 字段字段 加入加入 AC

57、K 報文報文 ; 發(fā)發(fā) 送節(jié)送節(jié) 點收到點收到 ACK 后后 , 從收發(fā)從收發(fā) 時間時間 差中差中 減去接減去接 收節(jié)收節(jié) 點的處點的處 理理 時時 間間 , 得得 到到 一一 跳跳 的的 通通 信信 延延 遲遲 。在在 更更 新新 記記 錄錄 的的 延延 遲遲 值值 時時 , 綜綜 合合 考慮新計算的考慮新計算的 延遲值和原來記錄延遲值和原來記錄的延遲值的延遲值, 更更 新的延遲值是二者的指數(shù)加新的延遲值是二者的指數(shù)加 權(quán)平均權(quán)平均( exponen tial weighted moving average, EWMA )。 節(jié)點節(jié)點 將計將計 算出的通信算出的通信 延遲通延遲通 告鄰告鄰

58、居居 節(jié)節(jié) 點。假點。假 設節(jié)設節(jié) 點點 A 計算計算 出出 到到 節(jié)節(jié) 點點 B 的的 通通 信信 延延 遲遲 , 并并 將將 這這 個個 通通 信信 延延 遲遲 通通 告告 其其 鄰鄰 居居 節(jié)節(jié) 點點C, 則則 C 可可 以不以不 必計算必計算 到節(jié)到節(jié) 點點 B 的通信的通信 延遲延遲 , 而使用而使用 A 發(fā)送發(fā)送 來的來的 通信延通信延 遲直遲直 接與接與 節(jié)點節(jié)點 B通通 信。信。無線傳感器網(wǎng)絡SNGF 算法 節(jié)點將鄰居節(jié)點分為兩類節(jié)點將鄰居節(jié)點分為兩類 : 比自己距離目比自己距離目標區(qū)域更近的節(jié)點和比自己標區(qū)域更近的節(jié)點和比自己 距離目距離目 標區(qū)域標區(qū)域更遠的節(jié)點。前者稱為候

59、選轉(zhuǎn)發(fā)節(jié)點集合更遠的節(jié)點。前者稱為候選轉(zhuǎn)發(fā)節(jié)點集合 ( for warding candidate set , F CS ) 。節(jié)點節(jié)點 計算到其計算到其 F CS 集合中的每個節(jié)點的集合中的每個節(jié)點的傳輸傳輸 速率。速率。 傳輸速傳輸速 率定率定 義為節(jié)義為節(jié) 點間點間 的的距距 離除以離除以 節(jié)點節(jié)點 間間 通信延遲。通信延遲。無線傳感器網(wǎng)絡SNGF 算法 如果節(jié)點的如果節(jié)點的 F CS 集合為空集合為空 , 意味著意味著 分分組組 走到了走到了 路由路由 空洞空洞 中。這中。這 時節(jié)時節(jié) 點將點將 丟丟 棄分棄分 組組 ,并使用下一節(jié)介紹的反向壓并使用下一節(jié)介紹的反向壓 力信力信 標標

60、( backpr es sure beacon) 消消 息息 通告通告 上一上一 跳節(jié)跳節(jié) 點點 , 以以 避免分組再走到這個路避免分組再走到這個路由空洞中。由空洞中。無線傳感器網(wǎng)絡SNGF 算法 根據(jù)傳根據(jù)傳 輸速率是輸速率是 否滿足否滿足 預定的傳預定的傳 輸速率閾輸速率閾 值值 , F CS 集合集合 中的節(jié)中的節(jié) 點又分為點又分為 兩類兩類 : 大于速率閾大于速率閾值的鄰居節(jié)點和小于值的鄰居節(jié)點和小于 速率閾速率閾 值的值的 鄰居節(jié)鄰居節(jié) 點。點。若若 FCS 集合集合 中有中有 節(jié)點的節(jié)點的 傳輸傳輸 速速 率大于速率率大于速率閾值閾值 , 則在這些節(jié)點則在這些節(jié)點 中按中按 照照