1、第一頁，共27頁。目錄1、泛洪路由(Flooding)2、Gossiping路由協(xié)議3 3、SPINSPIN協(xié)議協(xié)議4、DD定向擴(kuò)散路由協(xié)議5、Rumor 路由協(xié)議6 6、GPSRGPSR路由協(xié)議路由協(xié)議7 7、LEACHLEACH路由協(xié)議路由協(xié)議第二頁，共27頁。路由協(xié)議是路由協(xié)議是WSN的關(guān)鍵技術(shù)之一，它負(fù)責(zé)將數(shù)據(jù)分組從源節(jié)的關(guān)鍵技術(shù)之一，它負(fù)責(zé)將數(shù)據(jù)分組從源節(jié)點(diǎn)通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。點(diǎn)通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。 主要包括兩個(gè)方面的功能：主要包括兩個(gè)方面的功能： 尋找源節(jié)點(diǎn)和目的節(jié)點(diǎn)的優(yōu)化路徑尋找源節(jié)點(diǎn)和目的節(jié)點(diǎn)的優(yōu)化路徑 將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)第三頁

2、，共27頁。 一節(jié)點(diǎn)S希望發(fā)送一塊數(shù)據(jù)給節(jié)點(diǎn)D，節(jié)點(diǎn)S首先通過網(wǎng)絡(luò)將數(shù)據(jù)副本傳送給它的每一個(gè)鄰居節(jié)點(diǎn)，每一個(gè)鄰居節(jié)點(diǎn)又將其傳輸給各自的每一個(gè)鄰居節(jié)點(diǎn)，除了剛剛給它們發(fā)送數(shù)據(jù)副本的節(jié)點(diǎn)S外。如此繼續(xù)下去，直到將數(shù)據(jù)傳輸?shù)侥繕?biāo)節(jié)點(diǎn)D為止或者為該數(shù)據(jù)所設(shè)定的生命期限（在傳感器網(wǎng)絡(luò)里面通常定義為最大跳數(shù)）變?yōu)榱銥橹够蛘咚泄?jié)點(diǎn)擁有此數(shù)據(jù)副本為止。第四頁，共27頁。第五頁，共27頁。洪泛路由（Flooding）的優(yōu)點(diǎn)： 實(shí)現(xiàn)簡(jiǎn)單 不需要為保持網(wǎng)絡(luò)拓?fù)湫畔⒑蛯?shí)現(xiàn)復(fù)雜的路由發(fā)現(xiàn)算法而消耗計(jì)算資源 適用于健壯性要求高的場(chǎng)合。第六頁，共27頁。洪泛路由（Flooding）的不足： 存在信息爆炸(Implosio

3、n)問題，即出現(xiàn)一個(gè)節(jié)點(diǎn)可能得到一個(gè)數(shù)據(jù)多個(gè)副本的現(xiàn)象 出現(xiàn)部分重疊(Overlap)現(xiàn)象，如果處于同一觀測(cè)環(huán)境的兩個(gè)相鄰?fù)悅鞲衅鞴?jié)點(diǎn) 同時(shí)對(duì)一個(gè)事件作出反應(yīng)，二者采集的數(shù)據(jù)性質(zhì)相同，數(shù)值相近，那么，這兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)將收到雙份數(shù)據(jù)副本 盲目使用資源，即擴(kuò)散法不考慮各節(jié)點(diǎn)能量可用狀況因而無法作出相應(yīng)的自適應(yīng)路由選擇。第七頁，共27頁。洪泛路由（Flooding）的應(yīng)用情況：網(wǎng)絡(luò)資源過于浪費(fèi)，實(shí)際很少直接采用具有極好的健壯性，可用于軍事應(yīng)用作為衡量標(biāo)準(zhǔn)評(píng)價(jià)其它路由算法第八頁，共27頁。 Gossiping協(xié)議是對(duì)Flooding協(xié)議的改進(jìn),節(jié)點(diǎn)將產(chǎn)生或收到的數(shù)據(jù)隨機(jī)轉(zhuǎn)發(fā)給一個(gè)或者若干個(gè)相鄰節(jié)

4、點(diǎn),避免了內(nèi)爆,但增加了時(shí)延，且無法避免重疊問題。第九頁，共27頁。SPIN（sensor protocol for information via negotiation)a.為了避免出現(xiàn)擴(kuò)散法的信息爆炸問題和部為了避免出現(xiàn)擴(kuò)散法的信息爆炸問題和部分重疊現(xiàn)象，傳感器節(jié)點(diǎn)在傳送數(shù)據(jù)之前分重疊現(xiàn)象，傳感器節(jié)點(diǎn)在傳送數(shù)據(jù)之前彼此進(jìn)行協(xié)商，協(xié)商制度可確保傳輸有用彼此進(jìn)行協(xié)商，協(xié)商制度可確保傳輸有用數(shù)據(jù)。數(shù)據(jù)。第十頁，共27頁。b.節(jié)點(diǎn)間通過發(fā)送元數(shù)據(jù)，而不是采集的整個(gè)數(shù)據(jù)進(jìn)行協(xié)商。c.在傳輸或接收數(shù)據(jù)之前，每個(gè)節(jié)點(diǎn)都必須檢查各自可用的能量狀況，如果處于低能量水平，必須中斷一些操作。第十一頁，共27頁

5、。d. SPIN有3種數(shù)據(jù)包類型，即ADV、REQ和DATA.節(jié)點(diǎn)用ADV宣布有數(shù)據(jù)發(fā)送，用REQ請(qǐng)求希望接收數(shù)據(jù)，用DATA封裝數(shù)據(jù) ADV：用于新數(shù)據(jù)廣播。 REQ：用于請(qǐng)求發(fā)送數(shù)據(jù)。 DATA：包含附上元數(shù)據(jù)頭(meta-data header)的傳感器采集的數(shù)據(jù)的數(shù)據(jù)包SPIN-PP采用點(diǎn)到點(diǎn)的通信模式，并假定兩節(jié)點(diǎn)間的通信不受其他節(jié)點(diǎn)的干擾，分組不會(huì)丟失，功率沒有任何限制。第十二頁，共27頁。第十三頁，共27頁。SPIN協(xié)議的優(yōu)點(diǎn)：1、小ADV消息減輕了內(nèi)爆問題;2、通過數(shù)據(jù)命名解決了交疊問題；3、節(jié)點(diǎn)根據(jù)自身資源和應(yīng)用信息決定是否進(jìn)行ADV通告，避免了資源利用盲目問 題，有效地節(jié)約

6、了能量。第十四頁，共27頁。 SPIN協(xié)議的不足： 在傳輸新數(shù)據(jù)的過程中，直接向鄰居節(jié)點(diǎn)廣播ADV數(shù)據(jù)包，而沒有考慮其所有鄰居節(jié)點(diǎn)由于自身能量的原因，不愿承擔(dān)起轉(zhuǎn)發(fā)新數(shù)據(jù)的功能，則新數(shù)據(jù)無法傳輸，將會(huì)出現(xiàn)“數(shù)據(jù)盲點(diǎn)”，進(jìn)而影響整個(gè)網(wǎng)絡(luò)信息的收集。第十五頁，共27頁。 在Directed Diffusion中，可以對(duì)路徑進(jìn)行修復(fù)。在建立多條數(shù)據(jù)源到Sink節(jié)點(diǎn)的路徑之后，Sink節(jié)點(diǎn)可以選擇增強(qiáng)其中的一條路徑用于數(shù)據(jù)的傳輸，而同時(shí)保持另外一條低速數(shù)據(jù)傳輸?shù)穆窂健?當(dāng)高速路徑，也就是經(jīng)過增強(qiáng)的路徑出現(xiàn)故障時(shí)，Sink節(jié)點(diǎn)可以增強(qiáng)低速路徑，保證源節(jié)點(diǎn)到Sink節(jié)點(diǎn)的數(shù)據(jù)傳輸。第十六頁，共27頁。1、

7、采用多路徑、采用多路徑,健壯性好健壯性好;2、節(jié)點(diǎn)只需要和鄰居節(jié)點(diǎn)通信，因而不需要全局的地址機(jī)制，、節(jié)點(diǎn)只需要和鄰居節(jié)點(diǎn)通信，因而不需要全局的地址機(jī)制，使用查詢驅(qū)動(dòng)機(jī)制按使用查詢驅(qū)動(dòng)機(jī)制按 需建立路由需建立路由,避免了保存全網(wǎng)信息；避免了保存全網(wǎng)信息；3、每個(gè)節(jié)點(diǎn)都可以進(jìn)行數(shù)據(jù)融合操作，能減少數(shù)據(jù)通信量，節(jié)省能、每個(gè)節(jié)點(diǎn)都可以進(jìn)行數(shù)據(jù)融合操作，能減少數(shù)據(jù)通信量，節(jié)省能量消耗；量消耗；4、sink點(diǎn)根據(jù)實(shí)際情況采取增強(qiáng)或減弱方式能有效利用能量；點(diǎn)根據(jù)實(shí)際情況采取增強(qiáng)或減弱方式能有效利用能量；5、節(jié)點(diǎn)不需要維護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，數(shù)據(jù)的發(fā)送是基于需求的，因此、節(jié)點(diǎn)不需要維護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，數(shù)據(jù)的發(fā)送是

8、基于需求的，因此它是一個(gè)非常節(jié)能的路由協(xié)議。它是一個(gè)非常節(jié)能的路由協(xié)議。第十七頁，共27頁。1、基于查詢驅(qū)動(dòng)模型的，不適用于環(huán)境監(jiān)測(cè)的、基于查詢驅(qū)動(dòng)模型的，不適用于環(huán)境監(jiān)測(cè)的WSN；2、Gradient的建立開銷很大的建立開銷很大,不適合多不適合多sink點(diǎn)網(wǎng)絡(luò)；點(diǎn)網(wǎng)絡(luò)；3、數(shù)據(jù)聚合過程采用時(shí)間同步技術(shù)、數(shù)據(jù)聚合過程采用時(shí)間同步技術(shù),會(huì)帶來較大開銷和會(huì)帶來較大開銷和時(shí)延；時(shí)延；4、不同的應(yīng)用中需要定義不同的命名方案，也就是、不同的應(yīng)用中需要定義不同的命名方案，也就是對(duì)，從而限制了它的應(yīng)用。對(duì)，從而限制了它的應(yīng)用。第十八頁，共27頁。 Rumor Routing是在Directed Diffus

9、ion的基礎(chǔ)上演化而來的。通常情況下，Directed Diffusion協(xié)議需要向整個(gè)網(wǎng)絡(luò)廣播興趣，而在某些應(yīng)用中，只有少量的數(shù)據(jù)需要從源節(jié)點(diǎn)傳遞到Sink節(jié)點(diǎn)。在這種情況下，沒有必要向整個(gè)網(wǎng)絡(luò)廣播興趣。當(dāng)WSN中的事件（對(duì)應(yīng)著數(shù)據(jù)的傳遞）數(shù)量很少，而查詢（對(duì)應(yīng)著興趣的廣播）數(shù)量很多的時(shí)候，可以采用廣播事件的方法，以節(jié)省能量的消耗。Rumor Routing是一個(gè)介于事件廣播（向整個(gè)網(wǎng)絡(luò)廣播事件）和興趣廣播（向整個(gè)網(wǎng)絡(luò)廣播興趣）之間的一種路由協(xié)議在多sink點(diǎn)、查詢請(qǐng)求數(shù)目很大、網(wǎng)絡(luò)事件很少的情況下，Rumor協(xié)議較為有效。 但如果事件非常多,維護(hù)事件表和收發(fā)Agent帶來的開銷會(huì)很大。第十

10、九頁，共27頁。 GPSR(Greedy Perimeter Stateless Routing) GPSR協(xié)議核心思想：協(xié)議核心思想：GPSR協(xié)議是一個(gè)典型的基協(xié)議是一個(gè)典型的基于位置的路由協(xié)議。使用于位置的路由協(xié)議。使用GPSR協(xié)議，網(wǎng)絡(luò)節(jié)點(diǎn)都協(xié)議，網(wǎng)絡(luò)節(jié)點(diǎn)都知道自身地理位置并被統(tǒng)一編址，各節(jié)點(diǎn)利用貪心知道自身地理位置并被統(tǒng)一編址，各節(jié)點(diǎn)利用貪心算法盡量沿直線轉(zhuǎn)發(fā)數(shù)據(jù)。產(chǎn)生或收到數(shù)據(jù)的節(jié)點(diǎn)算法盡量沿直線轉(zhuǎn)發(fā)數(shù)據(jù)。產(chǎn)生或收到數(shù)據(jù)的節(jié)點(diǎn)向以歐氏距離計(jì)算最靠近目的節(jié)點(diǎn)的鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)向以歐氏距離計(jì)算最靠近目的節(jié)點(diǎn)的鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，但由于數(shù)據(jù)會(huì)到達(dá)沒有比該節(jié)點(diǎn)更接近目的點(diǎn)據(jù)，但由于數(shù)據(jù)會(huì)到達(dá)沒有比該

11、節(jié)點(diǎn)更接近目的點(diǎn)的區(qū)域的區(qū)域(稱為空洞稱為空洞)，導(dǎo)致數(shù)據(jù)無法傳輸，當(dāng)出現(xiàn)這，導(dǎo)致數(shù)據(jù)無法傳輸，當(dāng)出現(xiàn)這種情況時(shí)，空洞周圍的節(jié)點(diǎn)能夠探測(cè)到，并利用右種情況時(shí)，空洞周圍的節(jié)點(diǎn)能夠探測(cè)到，并利用右手法則沿空洞周圍傳輸來解決此問題。手法則沿空洞周圍傳輸來解決此問題。第二十頁，共27頁。1、避免了在節(jié)點(diǎn)中建立、維護(hù)、存儲(chǔ)路由表，、避免了在節(jié)點(diǎn)中建立、維護(hù)、存儲(chǔ)路由表，只依賴直接鄰節(jié)點(diǎn)進(jìn)行路由選擇，幾乎是只依賴直接鄰節(jié)點(diǎn)進(jìn)行路由選擇，幾乎是一個(gè)無狀態(tài)的協(xié)議；一個(gè)無狀態(tài)的協(xié)議；2、使用接近于最短歐氏距離的路由，數(shù)據(jù)傳、使用接近于最短歐氏距離的路由，數(shù)據(jù)傳輸時(shí)延小輸時(shí)延小;并能保證只要網(wǎng)絡(luò)連通性不被破并能保

12、證只要網(wǎng)絡(luò)連通性不被破壞，一定能夠發(fā)現(xiàn)可達(dá)路由。壞，一定能夠發(fā)現(xiàn)可達(dá)路由。 第二十一頁，共27頁。1、當(dāng)網(wǎng)絡(luò)中、當(dāng)網(wǎng)絡(luò)中sink點(diǎn)和源節(jié)點(diǎn)分別集中在兩個(gè)點(diǎn)和源節(jié)點(diǎn)分別集中在兩個(gè)區(qū)域時(shí)，由于通信量不平衡易導(dǎo)致部分區(qū)域時(shí)，由于通信量不平衡易導(dǎo)致部分 節(jié)節(jié)點(diǎn)失效，從而破壞網(wǎng)絡(luò)連通性；點(diǎn)失效，從而破壞網(wǎng)絡(luò)連通性；2、需要、需要GPS定位系統(tǒng)或其他定位方法協(xié)助計(jì)定位系統(tǒng)或其他定位方法協(xié)助計(jì)算節(jié)點(diǎn)位置信息。算節(jié)點(diǎn)位置信息。第二十二頁，共27頁。Low-Energy Adaptive Clustering Hierarchy1、LEACH協(xié)議分為兩個(gè)階段操作，即類準(zhǔn)備階段協(xié)議分為兩個(gè)階段操作，即類準(zhǔn)備階段(

13、set-up phase)和就緒階段和就緒階段(ready phase)。為了使能耗最。為了使能耗最小化，就緒階段持續(xù)的時(shí)間比類準(zhǔn)備階段長(zhǎng)。類準(zhǔn)備階小化，就緒階段持續(xù)的時(shí)間比類準(zhǔn)備階段長(zhǎng)。類準(zhǔn)備階段和就緒階段所持續(xù)的時(shí)間總和稱為一輪段和就緒階段所持續(xù)的時(shí)間總和稱為一輪(round)2、在類準(zhǔn)備階段，、在類準(zhǔn)備階段，LEACH協(xié)議隨機(jī)選擇一個(gè)傳感器節(jié)點(diǎn)協(xié)議隨機(jī)選擇一個(gè)傳感器節(jié)點(diǎn)作為類頭節(jié)點(diǎn)作為類頭節(jié)點(diǎn)(cluster head node)，隨機(jī)性確保類頭，隨機(jī)性確保類頭與基站之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹(jǐn)偟剿袀髋c基站之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹(jǐn)偟剿袀鞲衅鞴?jié)點(diǎn)。感器節(jié)點(diǎn)。第二十三頁，

14、共27頁。3、具體的選擇辦法是：一個(gè)傳感器節(jié)點(diǎn)隨機(jī)選擇、具體的選擇辦法是：一個(gè)傳感器節(jié)點(diǎn)隨機(jī)選擇 0和和1之間的之間的一個(gè)值，如果選定的值小于某一個(gè)閾值一個(gè)值，如果選定的值小于某一個(gè)閾值T(n)，那么這個(gè)節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)成為類頭節(jié)點(diǎn)。成為類頭節(jié)點(diǎn)。T(n)值按右邊公式計(jì)算值按右邊公式計(jì)算N：網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的總數(shù)；：網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的總數(shù)；p：一輪中網(wǎng)絡(luò)的類頭節(jié)點(diǎn)數(shù)；：一輪中網(wǎng)絡(luò)的類頭節(jié)點(diǎn)數(shù)；r：己完成的輪數(shù)；：己完成的輪數(shù)；Gr：在剩余的：在剩余的N/k-r個(gè)回合中未成為類頭節(jié)點(diǎn)的傳感器節(jié)點(diǎn)組個(gè)回合中未成為類頭節(jié)點(diǎn)的傳感器節(jié)點(diǎn)組成的集合；成的集合；第二十四頁，共27頁。4、在類頭節(jié)點(diǎn)選定后

15、，該類頭節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中、在類頭節(jié)點(diǎn)選定后，該類頭節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行廣播，廣播數(shù)據(jù)包含有該節(jié)所有節(jié)點(diǎn)進(jìn)行廣播，廣播數(shù)據(jù)包含有該節(jié)點(diǎn)成為類頭節(jié)點(diǎn)的信息。一旦傳感器節(jié)點(diǎn)點(diǎn)成為類頭節(jié)點(diǎn)的信息。一旦傳感器節(jié)點(diǎn)收到廣播數(shù)據(jù)包，根據(jù)接收到的各個(gè)類頭收到廣播數(shù)據(jù)包，根據(jù)接收到的各個(gè)類頭節(jié)點(diǎn)廣播信號(hào)強(qiáng)度，該節(jié)點(diǎn)選擇信號(hào)強(qiáng)度節(jié)點(diǎn)廣播信號(hào)強(qiáng)度，該節(jié)點(diǎn)選擇信號(hào)強(qiáng)度最大的類頭節(jié)點(diǎn)加入，向其發(fā)送成為其成最大的類頭節(jié)點(diǎn)加入，向其發(fā)送成為其成員的數(shù)據(jù)包。類形成后，類頭節(jié)點(diǎn)采用員的數(shù)據(jù)包。類形成后，類頭節(jié)點(diǎn)采用TDMA策略分配通道使用權(quán)給類內(nèi)節(jié)點(diǎn)。策略分配通道使用權(quán)給類內(nèi)節(jié)點(diǎn)。第二十五頁，共27頁。5、一旦處于就緒階段，類頭節(jié)點(diǎn)開始接收類、一旦處于就緒階段，類頭節(jié)點(diǎn)開始接收類內(nèi)各節(jié)點(diǎn)采集的數(shù)據(jù)，然后采用數(shù)據(jù)融合內(nèi)各節(jié)點(diǎn)采集的數(shù)據(jù)，然后采用數(shù)據(jù)融合和數(shù)據(jù)壓縮等技術(shù)進(jìn)行匯聚，將整合后的和數(shù)據(jù)壓縮等技術(shù)進(jìn)行匯聚，將整合后