物聯(lián)網(wǎng)講座05-WSN路由協(xié)議

物聯(lián)網(wǎng)技術概論內(nèi)容提綱1WSN路由協(xié)議概要2WSN路由協(xié)議分類3WSN協(xié)議的主要最新成果物聯(lián)網(wǎng)技術概論1WSN路由協(xié)議概要物聯(lián)網(wǎng)技術概論1WSN路由協(xié)議概要作用：路由協(xié)議負責將數(shù)據(jù)從源節(jié)點(S)通過網(wǎng)絡轉(zhuǎn)發(fā)到目的節(jié)點(D)。功能：尋找源節(jié)點和目的節(jié)點的優(yōu)化路徑：公平高效、低延遲、避免擁塞、均衡網(wǎng)絡流量；將數(shù)據(jù)協(xié)議沿著路由協(xié)議正確轉(zhuǎn)發(fā)；設計目標滿足應用需求低網(wǎng)絡開銷資源利用的整體有效性網(wǎng)絡高吞吐率節(jié)約能量物聯(lián)網(wǎng)技術概論WSN網(wǎng)絡特點特點自組織的網(wǎng)絡（隨機部署）數(shù)據(jù)的冗余性（多節(jié)點監(jiān)測同一事件）基于局部拓撲信息（硬件限制）網(wǎng)絡功能（數(shù)據(jù)收集）數(shù)據(jù)為中心物聯(lián)網(wǎng)技術概論WSN路由協(xié)議設計要求無線傳感網(wǎng)絡具有很強的應用相關性，所以路由協(xié)議沒有一個通用的萬能的協(xié)議，應根據(jù)具體應用來選擇路由協(xié)議。要求 能量高效（協(xié)議簡單&節(jié)省能量&均衡消耗）可擴展性（網(wǎng)絡范圍&節(jié)點密度）魯棒性（節(jié)點變化&拓撲變化）快速收斂性靈活性物聯(lián)網(wǎng)技術概論WSN路由協(xié)議關鍵技術考慮網(wǎng)絡和節(jié)點能量優(yōu)化（硬件限制）具有高可擴展性（網(wǎng)絡規(guī)模&自組織）

適應強網(wǎng)絡拓撲變化（節(jié)點移動&無線信道）傳感器網(wǎng)絡路由中使用數(shù)據(jù)融合技術（數(shù)據(jù)為中心）傳感器網(wǎng)絡中流量分布不對稱（數(shù)據(jù)收集網(wǎng)絡&多源單Sink)物聯(lián)網(wǎng)技術概論WSN路由協(xié)議的挑戰(zhàn)自組織布撒（Adhocdeployment）能量消耗（Energyconsumption）路由精度（Routingaccuracy）計算能力（Computationcapabilities）通信能力（Communicationtolerance）容錯能力（Faulttolerance）可擴展性（Scalability）控制負載（Controloverhead）物聯(lián)網(wǎng)技術概論路由的性質(zhì)a)單播b)廣播c)多播d)任播e)k-任播物聯(lián)網(wǎng)技術概論2WSN路由協(xié)議分類物聯(lián)網(wǎng)技術概論WSN路由協(xié)議分類從具體應用出發(fā)，進行分類，大致可分類四類：能量感知路由協(xié)議基于查詢的路由協(xié)議地理位置路由協(xié)議Qos路由協(xié)議物聯(lián)網(wǎng)技術概論能量感知路由協(xié)議物聯(lián)網(wǎng)技術概論能量感知路由特點：從數(shù)據(jù)傳輸中的能量消耗出發(fā)，討論最優(yōu)能量消耗路徑以及最長網(wǎng)絡生存周期。路由方式：根據(jù)節(jié)點的可用能量（PA，poweravailable）或傳輸路徑上的能量需求，進行數(shù)據(jù)的轉(zhuǎn)發(fā)。節(jié)點的可用能量就是剩余能量。物聯(lián)網(wǎng)技術概論能量路由算法示意圖匯聚節(jié)點源節(jié)點a1=1a2=1a3=2a4=2a6=2a10=2a7=1a8=2a9=1a5=2A(PA=2)B(PA=2)C(PA=2)D(PA=3)E(PA=1)F(PA=4)路徑1：源-B-A-SINK，所有節(jié)點的PA之和為4，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為3;路徑2：源-C-B-A-SINK,所有節(jié)點的PA之和為6，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為6;路徑3：源-D-SINK,所有節(jié)點的PA之和為3，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為4;路徑4：源-F-E-SINK,所有節(jié)點的PA之和為5，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為6；物聯(lián)網(wǎng)技術概論路由策略分析路由策略：最大PA路由：路徑2的PA之和最大，但包含了路徑1，不是最優(yōu)解，應選擇路徑4。最小能量消耗路由：路徑1能量消耗最小。最少跳數(shù)路由：選擇從源到匯聚節(jié)點的最小跳數(shù)路徑，選擇路徑3最大最小PA節(jié)點路由：路徑上每個節(jié)點的可用能量不同，從中選取每條路徑中最小能量的節(jié)點表示這條路徑的可用能量，最大最小路徑就是選擇可用能量最大的路徑。物聯(lián)網(wǎng)技術概論能量路由算法分析較好的解決了能量均衡問題，延長了網(wǎng)絡生存周期。算法的收斂性較好網(wǎng)絡負載未必均衡節(jié)點需要知道全局網(wǎng)絡信息，但WSN資源約束，節(jié)點只能獲得局部網(wǎng)絡信息。物聯(lián)網(wǎng)技術概論能量多路徑路由（1）傳統(tǒng)網(wǎng)絡的路由機制往往選擇從源到目的節(jié)點之間跳數(shù)最小的路徑，但是再WSN中，頻繁的使用同一條路徑傳輸數(shù)據(jù)，就會造成該路徑上的節(jié)點因能量消耗過快而過早失效，從而使網(wǎng)絡分割成互不相連的孤立部分，減少了網(wǎng)絡生存期。能量多路徑路由在源節(jié)點和目的節(jié)點之間建立多條路徑，根據(jù)路徑上節(jié)點的通信消耗及節(jié)點剩余能量情況，給每條路徑賦予一定概率，使數(shù)據(jù)傳輸均衡消耗網(wǎng)絡能量。物聯(lián)網(wǎng)技術概論能量多路徑路由（2）能量多路徑路由包括路徑建立、數(shù)據(jù)傳播和路由維護三個過程。每個節(jié)點需要知道到達目的節(jié)點的所有下一跳節(jié)點，并計算選擇每個下一跳節(jié)點的概率。概率的選擇根據(jù)節(jié)點到目的節(jié)點的通信代價來計算的，用Cost(Ni)表示節(jié)點i到目的節(jié)點的通信代價。節(jié)點到目的節(jié)點的路徑很多，這個代價值是加權(quán)平均值物聯(lián)網(wǎng)技術概論能量多路徑路由（3）過程描述如下：1）目的節(jié)點向鄰居節(jié)點廣播路徑建立消息，啟動路徑建立過程。路徑建立消息中包含一個代價域，表示發(fā)出該消息的節(jié)點到目的節(jié)點路徑上的能量信息，初始值為0.2）當節(jié)點收到鄰居節(jié)點的路徑建立消息時，相對發(fā)送該消息的鄰居節(jié)點，只有當自己距源節(jié)點更近，而且距目的節(jié)點更遠的情況下，才需要轉(zhuǎn)發(fā)該消息，否則丟棄該消息。3）如果節(jié)點決定轉(zhuǎn)發(fā)該消息，需要重新計算代價值替代原來的代價值。當路徑建立消息從節(jié)點Ni到節(jié)點Nj時，該路徑的通信代價為節(jié)點Ni的代價值加上兩個節(jié)點間的通信代價，即：物聯(lián)網(wǎng)技術概論能量多路徑路由（4）4)節(jié)點要放棄代價太大的路徑，節(jié)點Nj將節(jié)點Ni加入本地路由表FTj的條件是：5）節(jié)點為路由表中每個下一跳節(jié)點計算選擇概率，節(jié)點的選擇概率與能量消耗成反比。節(jié)點Nj選擇公式如下：6）節(jié)點根據(jù)路由表中每項的能量代價和下一跳節(jié)點選擇概率計算本身到目的節(jié)點代價Cost(Nj)。Cost(Nj)定義為經(jīng)由路由表中節(jié)點到達目的節(jié)點代價的平均值，即：物聯(lián)網(wǎng)技術概論能量多路徑路由性能分析將通信代價分散到多跳路徑上，實現(xiàn)整個網(wǎng)絡的能量平穩(wěn)降級，最大限度的延長網(wǎng)絡生存周期。維護代價太高，需要周期性的從目的節(jié)點到源節(jié)點實施洪泛查詢來維持所有路徑的活動性。擴展性不好，不適宜節(jié)點動態(tài)加入和離去。物聯(lián)網(wǎng)技術概論基于查詢的路由定向擴散路由（directeddiffusion,DD)謠傳路由（rumorrouting)物聯(lián)網(wǎng)技術概論定向擴散路由匯聚節(jié)點通過興趣消息發(fā)出查詢?nèi)蝿?，采用洪泛方式傳播興趣消息到整個區(qū)域或部分區(qū)域內(nèi)的所有傳感器節(jié)點。興趣消息采用表示查詢的任務，表達網(wǎng)絡用戶對監(jiān)測區(qū)域內(nèi)感興趣的信息，例如監(jiān)測區(qū)域的溫度、濕度等。在興趣消息的傳播過程中，協(xié)議逐跳地在每個傳感器節(jié)點上建立反向的從數(shù)據(jù)源到匯聚節(jié)點的數(shù)據(jù)傳輸梯度(gradient)。傳感器節(jié)點將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點。物聯(lián)網(wǎng)技術概論定向擴散路由Sink節(jié)點向全網(wǎng)查詢興趣M建立源節(jié)點和Sink間路徑興趣在全網(wǎng)中擴散對每一個活動任務，Sink周期進行查詢鄰居更新自己的興趣消息，并且轉(zhuǎn)發(fā)興趣消息中的條目時間戳：指示接收到相關興趣消息的最近時間若干梯度域：每個梯度和其鄰居節(jié)點相關聯(lián)每個梯度中含有一個指定的數(shù)據(jù)傳輸率持續(xù)時間：該興趣消息的有效期物聯(lián)網(wǎng)技術概論定向擴散路由查詢消息的傳播—建立數(shù)據(jù)的傳輸梯度匯聚節(jié)點發(fā)送查詢消息興趣消息：任務性質(zhì)、數(shù)據(jù)采集/發(fā)送速率、時間戳等中間節(jié)點：記錄轉(zhuǎn)發(fā)梯度：表示了數(shù)據(jù)的傳輸方向定向擴散路由路徑增強---匯聚節(jié)點在收到許多低速率數(shù)據(jù)后，向數(shù)據(jù)到達最快的鄰居節(jié)點發(fā)送增強消息，增強消息表示匯聚節(jié)點要求高速率的發(fā)送數(shù)據(jù)，相應鄰居節(jié)點按照同樣的方式，一次傳遞增強信息給其鄰居節(jié)點，直到到達數(shù)據(jù)源，據(jù)此構(gòu)建數(shù)據(jù)發(fā)送的主路徑。DD適用持續(xù)性查詢的應用而不適用于一次性查詢的應用，代價較大。物聯(lián)網(wǎng)技術概論物聯(lián)網(wǎng)技術概論定向擴散路由協(xié)議-路徑修復加強路徑上的節(jié)點可以觸發(fā)和啟動路徑的加強過程新路徑C和源節(jié)點之間路徑斷裂物聯(lián)網(wǎng)技術概論定向擴散路由協(xié)議分析優(yōu)點數(shù)據(jù)中心路由，定義不同任務類型/目標區(qū)域消息；路徑加強機制可顯著提高數(shù)據(jù)傳輸?shù)乃俾?；周期性路由：能量的均衡消耗；缺點周期性的洪泛機制---能量和時間開銷都比較大；節(jié)點需要維護一個興趣消息列表，代價較大；物聯(lián)網(wǎng)技術概論DD協(xié)議族GBR路由(Gradient-BasedRouting)協(xié)議：梯度域擴展（傳感器節(jié)點到Sink節(jié)點的跳數(shù)信息、無線鏈路評估信息）EAR(EnergyAwareRouting)路由協(xié)議建立路由過程中加入能量評估機制；路由路徑的能量開銷大于某一閾值不采用；CADR路由(ConstrainedAnisotropicDiffusionrouting)協(xié)議興趣消息往指定方向發(fā)送物聯(lián)網(wǎng)技術概論謠傳路由傳感器節(jié)點采用代理消息，代理消息沿隨機路徑向外擴散傳播，匯聚節(jié)點發(fā)送的查詢消息也隨機在網(wǎng)絡中傳播。物聯(lián)網(wǎng)技術概論謠傳路由工作原理1）每個傳感器節(jié)點維護一個鄰居列表和一個事件列表；事件列表包括事件名稱、跳數(shù)等，同時根據(jù)一定的概率產(chǎn)生一個代理消息。2）收到代理消息的節(jié)點，將代理消息和事件列表的表項做比較，根據(jù)跳數(shù)值決定更新代理消息或事件列表的表項。如本地事件列表無此表項，則將生存期減1，再隨機轉(zhuǎn)發(fā)。3）任何節(jié)點可以產(chǎn)生查詢消息4）查詢消息路徑和代理消息路徑的交叉節(jié)點沿查詢消息反向路徑建立連接。物聯(lián)網(wǎng)技術概論謠傳路由分析通過消息生存期解決環(huán)路問題。避免了洪泛方式，減小了網(wǎng)絡開銷隨機性強，不能做到優(yōu)化路由。物聯(lián)網(wǎng)技術概論地理位置路由物聯(lián)網(wǎng)技術概論地理位置路由在一些傳感器網(wǎng)絡的應用中，不光要知道網(wǎng)絡中產(chǎn)生的事件，還需要知道事件產(chǎn)生的位置。如在森林防火中，不光需要知道發(fā)生了火災，還需要知道在哪發(fā)生了火災。地理位置路由假設節(jié)點知道自己的地理位置信息，以及目的節(jié)點和目的區(qū)域的地理位置信息。以地理位置信息作為路由依據(jù)。地理位置的精確度和代價相關，在不同的應用中會選擇不同精確的位置信息來實現(xiàn)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議應用建立到特定區(qū)域的路由查詢工作方式前提已知目標區(qū)域的位置信息節(jié)點知道自己位置信息和剩余能量節(jié)點直到鄰居節(jié)點的位置信息和剩余能量節(jié)點間無線鏈路是對稱的物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議分兩個階段：查詢消息到達目的區(qū)域的路徑查詢消息在目標區(qū)域的傳播選路依據(jù)節(jié)點到查詢區(qū)域通信能量能耗節(jié)點本身的剩余能量最小代價節(jié)點為轉(zhuǎn)發(fā)節(jié)點物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議查詢命令傳送到目標區(qū)域貪婪算法－選擇鄰居節(jié)點到達指定區(qū)域的代價估計代價：

F(Ni,R)=α?Distance(Ni,R)+(1?α)?Left_Enery(Ni)實際代價：F(Ni,R)=α?Enery_Cost(Ni,R)+(1?α)?Left_Enery(Ni)歸一化處理

Ni為有轉(zhuǎn)發(fā)需求的節(jié)點的鄰居節(jié)點，R為目標區(qū)域的中心位置。當N不知道Ni的實際代價時使用估計代價。

物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議查詢在監(jiān)測區(qū)域內(nèi)傳送：洪泛方式，迭代地理轉(zhuǎn)發(fā)將目標區(qū)域分解為若干子區(qū)域、向子區(qū)域的中心位置轉(zhuǎn)發(fā)）物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議-路由空洞問題路由空洞：鄰居節(jié)點傳輸代價都比本地節(jié)點大處理辦法：選擇鄰居節(jié)點中代價最小的作為轉(zhuǎn)發(fā)節(jié)點；修改本地節(jié)點的轉(zhuǎn)發(fā)代價；

F(N,R)=F(Nmin,R)+C(N,Nmin)，C(N,Nmin)表示將數(shù)據(jù)包從N傳送到Nmin的代價物聯(lián)網(wǎng)技術概論GEAR路由協(xié)議-路由空洞KLTFGHIJABCDES物聯(lián)網(wǎng)技術概論GEAR路由評價優(yōu)點利用了位置信息，避免了查詢消息的Flooding；考慮了消耗的能量和節(jié)點剩余能量，均衡消息；路徑選擇可達到局部最優(yōu)；迭代地理轉(zhuǎn)發(fā)對洪泛機制的補充；缺點可能出現(xiàn)路由空洞（局部信息）-兩跳信息；不適合在移動WSN使用物聯(lián)網(wǎng)技術概論GPSR路由協(xié)議GPSR（greedyperimeterstatelessrouting）這是一個典型的基于位置的路由協(xié)議.使用GPSR協(xié)議,網(wǎng)絡節(jié)點都知道自身地理位置并被統(tǒng)一編址,各節(jié)點利用貪婪算法盡量沿直線轉(zhuǎn)發(fā)數(shù)據(jù).GPSR路由協(xié)議當節(jié)點S需要向節(jié)點D轉(zhuǎn)發(fā)數(shù)據(jù)分組的時候，它首先在自己的所有鄰居節(jié)點中選擇一個距節(jié)點D最近的節(jié)點作為數(shù)據(jù)分組的下一跳，然后將數(shù)據(jù)傳送給它。該過程一直重復，直到數(shù)據(jù)分組到達目的節(jié)點D或某個最佳節(jié)點。利用節(jié)點的地理位置信息轉(zhuǎn)發(fā)節(jié)點選?。哼x擇鄰居節(jié)點中離目的節(jié)點更近的點作為轉(zhuǎn)發(fā)節(jié)點物聯(lián)網(wǎng)技術概論物聯(lián)網(wǎng)技術概論局部優(yōu)化問題存在x到D的路徑x的鄰居w,y離D的距離比x大解決方法：邊界轉(zhuǎn)發(fā)物聯(lián)網(wǎng)技術概論邊界轉(zhuǎn)發(fā)平面圖：二維空間結(jié)構(gòu)；平面圖中任意兩條邊都只相交于頂點；GPSR算法中構(gòu)造平面圖的方法是刪除網(wǎng)絡拓撲圖中交叉的邊算法：RNG(RelativeNeighborhoodGraph)GG(GabrielGraph)物聯(lián)網(wǎng)技術概論平面圖講解下面的(a)、(b)、(c)、(d)為四個平面圖.數(shù)一數(shù),每個平面圖各有多少個頂點?多少條邊?它們分別圍成了多少個區(qū)域（內(nèi)部）?請將結(jié)果填入下表(按填好的樣子做).(2)觀察表格，推斷一個平面圖的頂點數(shù)、邊數(shù)、區(qū)域數(shù)之間有什么關系？

3)現(xiàn)已知某個平面圖有999個頂點，且圍成了999個內(nèi)部區(qū)域，試根據(jù)以上關系確定這個圖有多少條邊.平面圖的判斷平面圖判斷公式：（歐拉公式）面+定點-邊=2物聯(lián)網(wǎng)技術概論物聯(lián)網(wǎng)技術概論RNG節(jié)點u，v之間存在邊的條件是對于任意一個節(jié)點w，u到v的距離要小于或等于u到w或是v到w的距離的最大值，用下式表示：

物聯(lián)網(wǎng)技術概論GG節(jié)點u，v之間存在邊的條件是在以d(u，v)為直徑的圓中沒有其它節(jié)點，用下式表示：物聯(lián)網(wǎng)技術概論物聯(lián)網(wǎng)技術概論邊界轉(zhuǎn)發(fā)時的右手法則一個數(shù)據(jù)分組從節(jié)點y到達節(jié)點x；下一條邊的選擇：下一邊是以x為定點，沿(x，y)順時針方向上的第一條邊，圖中為(x，z)后續(xù)各邊同樣依次法則確定物聯(lián)網(wǎng)技術概論Face平面圖的邊將整個圖分成許多小的互補重疊的有界多邊形和一些無界區(qū)域，這些有界多邊形和無界區(qū)域統(tǒng)稱為face。其中，有界區(qū)域稱為內(nèi)部face，無界區(qū)域稱為外部face。途中xD通過3個有界face和一個無界face。物聯(lián)網(wǎng)技術概論邊界轉(zhuǎn)發(fā)數(shù)據(jù)包在x點進入邊界轉(zhuǎn)發(fā)模式，通過face邊界向目的節(jié)點D轉(zhuǎn)發(fā)，這些face都被xD穿越；轉(zhuǎn)發(fā)邊的選擇采用右手法則，初始邊為xD；數(shù)據(jù)包在同一個face中轉(zhuǎn)發(fā)時采用右手法則，當碰到與xD相交的邊時，進行face切換，進入下一個face；物聯(lián)網(wǎng)技術概論GPSR協(xié)議評價優(yōu)點采用局部最優(yōu)的貪婪算法，不需要維護網(wǎng)絡拓撲，路由開銷?。豢蛇m用于靜態(tài)和移動的WSN網(wǎng)絡；缺點需要地理位置信息的支持；需要維護鄰居節(jié)點位置信息；物聯(lián)網(wǎng)技術概論基于Qos的路由物聯(lián)網(wǎng)技術概論基于Qos的路由無線傳感網(wǎng)絡的某些應用對通信的服務質(zhì)量有較高要求，如高可靠性和實時性等；而由于網(wǎng)絡鏈路的穩(wěn)定性難以保證，通信信道質(zhì)量比較低，拓撲變化比較頻繁，要在無線傳感網(wǎng)絡中實現(xiàn)一定服務質(zhì)量的保證，需要設計基于Qos的路由協(xié)議?；诓幌嘟宦窂降亩嗦窂铰酚蓹C制SPEED協(xié)議物聯(lián)網(wǎng)技術概論基于不相交路徑的多路徑路由機制在WSN中，引入多路徑路由是為了提高數(shù)據(jù)傳輸?shù)目煽啃院蛯崿F(xiàn)網(wǎng)絡負載平衡。在多徑路由中，首要的問題是解決如何建立源到目的地址的多跳路徑。主要思想：首先建立主路徑，再建立多跳備用路徑。數(shù)據(jù)從主路徑傳輸，同時利用備用路徑低速傳輸數(shù)據(jù)維護路由有效性。物聯(lián)網(wǎng)技術概論基于不相交路徑的多路徑路由機制物聯(lián)網(wǎng)技術概論纏繞多路徑局部纏繞多路徑：主路徑上的每一個節(jié)點（除兩頭節(jié)點外）都發(fā)送備用路徑增強消息給自己的次優(yōu)節(jié)點A，A尋找自己的最優(yōu)節(jié)點B，如果B不再主路徑上將繼續(xù)向自己的最優(yōu)路徑轉(zhuǎn)發(fā)，直到與主路徑相交。Speed協(xié)議物聯(lián)網(wǎng)技術概論物聯(lián)網(wǎng)技術概論SPEED協(xié)議SPEED是一個實時路由協(xié)議，在一定程度上實現(xiàn)了端到端的傳輸速率保證、網(wǎng)絡擁塞控制以及負載平衡機制。首先要求節(jié)點交換節(jié)點的傳輸延遲，以得到負載情況；然后利用局部地理信息和傳輸速率作出路由決定，同時通過鄰居反饋機制保證網(wǎng)絡傳輸速率在一個全局定義的傳輸速率閥值之上。物