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

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

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

Ni為有轉發需求的節點的鄰居節點，R為目標區域的中心位置。當N不知道Ni的實際代價時使用估計代價。

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

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

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

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