1、 無線傳感器網絡的路由協議路由協議概述無線傳感器網絡的路由協議路由協議主要任務是確保數據由確保數據由源節點準確高效地傳輸到目的節點源節點準確高效地傳輸到目的節點，即尋找數據的尋找數據的最優路徑最優路徑以及沿最優路徑發送數據沿最優路徑發送數據。能耗：能耗：WSN中，路由協議的制定受能耗的限制。鄰居發現過程：鄰居節點間交換信息會消耗能量，交換數據越大，能耗越大。處理過程：數據傳輸過程的計算和通信會消耗能量，通信的能耗大于計算。可擴展性可擴展性：路由協議需能滿足網絡拓撲形態的變化，即使發生變化，節點也能有效把握網絡傳輸路徑情況。編址：編址：用戶對來自多個節點的整合后信息感興趣，而非單個節點，因此唯一

2、編址方式不適合WSN健壯性健壯性：防止由于部分節點故障失效造成的信息丟失，以及信道不穩定造成的信息受損和丟失。路由協議概述拓撲拓撲：路由協議需能適應WSN的拓撲變化。預訂拓撲：節點相對固定，可實現高效路由協議。隨機拓撲：網絡自組織，可利用拓撲發現作為路由計算的前提，路由協議也需適應節點或觀測目標的移動。設計目的設計目的：網絡的目的(上層應用)的不同導致路由協議原則的不同。路由協議概述WSN路由協議的分類能量感知路由WSN網絡是能量受限的網絡，節省能量是路由設計需考慮的重要因素。能量路由是WSN最基本的路由協議之一能量路由是根據節點可用能量(Power Available，PA)或傳輸路徑上的能

3、量需求(E)，選擇數據的轉發路徑。節點可用能量就是節點當前的剩余能量。基本能量路由能量感知路由基本能量路由路徑1：源BA目標， PA=4，E=3；路徑2：源CBA目標， PA=6，E=6；路徑3：源D目標， PA=3，E=4；路徑4：源FE目標， PA=5，E=6。最大PA路由：路徑2最小能耗路由：路徑1最少條數路由：路徑3最大平均路由：路徑4能量感知路由能量多徑路由能量多徑路由基本思想能量多徑路由基本思想在源節點和目標節點之間建立多條數據傳輸路徑根據每條路徑上節點的剩余能量和傳輸消耗的能量來給每條路徑賦予一定的選擇概率依概率在多條路徑中選擇傳輸路徑，均衡消耗節點能量，延長網絡生存期傳統能量路

4、由頻繁通過某一路徑傳輸數據，易導致該路徑上節點能量消耗過快，節點提早失效。能量感知路由能量多徑路由路徑建立路徑建立n建立從源節點到目的節點的多條路徑n計算出各條路徑的選擇概率主要過程數據傳輸數據傳輸n對于接收到的每組數據，節點根據概率從所有下一跳節點中選擇一個節點路由維護路由維護n周期性從目的節點到源節點進行洪泛查詢以維護路徑的有效性和活躍性能量感知路由能量多徑路由路徑建立具體過程目的節點目的節點向鄰居廣播路徑建立消息鄰居鄰居收到消息，如處于目的節點和源處于目的節點和源節點節點之間則轉發，否則丟棄如節點決定轉發(加入路由集合)，則更新轉發消息更新轉發消息中的代價值中的代價值如選擇某一鄰居代價代

5、價太高太高，則放棄選擇路由集合中的節點計算下一跳各選擇的概率，概率與代概率與代價成反比價成反比節點根據選擇概率選擇概率和能量消耗和能量消耗計算自己到目的節點的傳輸代價泛洪是一種傳統的路由技術。泛洪算法的主要思想是由某節點發起數據廣播，然后任意一個收到廣播的節點都無條件將該數據包廣播出去，每一節點都重復這樣的過程直到數據遍歷全網或者達到規定的最大跳數。數據包像洪水一樣漫過所有地方，因此稱為洪泛協議。算法不用維護網絡拓撲結構和路由計算，實現簡單。但是最主要的是內爆和重疊以及資源盲點等。洪泛 (Flooding)協議以數據為中心的路由協議洪泛 (Flooding)協議以數據為中心的路由協議內爆現象內

6、爆現象：洪泛機制允許大量冗余消息，節點會收到來自多個鄰居節點轉發的相同消息。重疊現象重疊現象：監測同一區域的節點容易產生相同的信息，造成傳播過程中的信息冗余，消耗大量能量。 謠言協議是對洪泛協議的改進。 當節點收到數據包時，只將數據包隨機轉發給與其相鄰的節點的某一個節點或幾個，而不是所有節點。選定的鄰居也采用同樣的辦法轉發下去。 優點：降低數據轉發重疊的可能性，減少內爆現象的發生。 缺點：點到點的時延較大隨機轉發某一個節點的方向并不一定在距離目的節點更近的方向上，易造成數據超時或者跳數己達最大，導致遞送失敗。開始的短時間內發送速率很大，隨著數據的發送，速度明顯降低。謠言 (Gossiping)

7、協議以數據為中心的路由協議SPIN協議以數據為中心的路由協議信息協商傳感器信息協商傳感器(SPIN)協議協議是 最基本的一類WSN路由協議，是對Flooding協議的改進。考慮到WSN的數據冗余，臨近節點所感知的數據具有相似性，通過協商和能量自適應來減少數據傳輸量，解決洪泛協議存在的不足。SPIN協議采用了兩種機制： 在數據發送前通過協商確定是否發送在數據發送前通過協商確定是否發送 節點監測自己的能量并進行能量感知決策節點監測自己的能量并進行能量感知決策SPIN協議假定兩點間的通信不受到其他節點的干擾，分組不會丟失，功耗無限制進。SPIN協議包括三種類型的消息：廣告消息廣告消息(Adverti

8、se,ADV)、請求發請求發送消息送消息(Request,REQ)、數據消息數據消息(Data transfer,DATA)SPIN協議以數據為中心的路由協議三次握手三次握手機制(點對點模式，即SPIN-PP)節點A向鄰居B發送ADV，ADV消息對DATA消息進行了描述。如果B對DATA消息感興趣，則發送REQ消息給A節點。A收到REQ后，將DATA消息發送給B節點。SPIN協議以數據為中心的路由協議三次握手三次握手機制(點對多點模式)節點B向多個鄰居節點發送ADV。有部分收到ADV的節點對DATA感興趣，回復REQ。B節點向回復REQ的節點發送DATA。SPIN協議以數據為中心的路由協議SP

9、IN-EC機制(在SPIN基礎上加入能量感知功能)當一個節點的可用能量低于閾值，該節點不參與DATA消息的轉發。低能量節點只接收消息。通過減少參與轉發活動，能耗可降低10%。SPIN協議以數據為中心的路由協議SPIN-BC機制當一個節點發送REQ時，其他節點可以聽到此與DATA有關的REQ，則放棄此次發送REQ等待DATA消息。源節點收到REQ，會將DATA廣播出去，感興趣的節點可以收到這個DATA。SPIN-RL機制如一節點對DATA感興趣，但由于信道錯誤等原因，未收到DATA消息。該節點可以向其他可能收到DATA消息的鄰居節點發起傳輸請求，獲得DATA消息。n優點優點解決了內爆問題和部分解

10、決了重疊問題不需要進行路由維護對網絡拓撲變化不敏感，可用于移動WSNn缺點缺點本質上SPIN還是向全網擴散新消息，開銷比較大 當多個節點向同一個節點同時發送REQ時，需要退避算法 SPIN協議以數據為中心的路由協議定向擴散協議以數據為中心的路由協議定向擴散定向擴散( (Directed Diffusion) )協議協議：匯聚節點匯聚節點接到上層應用的查詢任務后，將興趣消息通過洪泛方式周期性地廣播廣播出去，即告訴其他節點我要收集什么興趣。在傳輸過程中建立從數據源節點到匯聚節點的傳輸梯度。在區域內“興趣”匹配節點沿著梯度方向通過路徑傳送數據到匯聚節點。n四個階段：興趣擴散興趣擴散（采用泛洪）；梯度

11、建立梯度建立（反向建立）；強化路徑強化路徑（匯聚節點會收到多條路徑，選最優路徑，進行加強，以后的數據按照加強路徑傳送）數據傳輸數據傳輸n匯聚節點匯聚節點向全網查詢興趣興趣，鄰居節點鄰居節點更新自己的興趣緩存興趣緩存，并且轉發n興趣緩存中的條目(興趣表項)時間戳：指示接收到相關興趣消息的最近時間梯度：當前節點從哪個鄰居收到興趣消息以及相應的數據傳輸率 持續時間：該興趣消息的有效期定向擴散協議以數據為中心的路由協議路徑增強路徑增強:在多條對應的梯度路徑中，匯聚節點可以對某一條路徑經行梯度增強。沿這條路徑再次發送興趣消息當前節點選定下一跳，興趣消息只會發送給選定的下一跳節點逐跳傳導下去，即形成一條專

12、門的路徑定向擴散協議以數據為中心的路由協議反向路徑增強反向路徑增強:如之前的某條路徑遭到破環，匯聚節點需“增強”另一條路徑就可以改變數據的路由向之前的路徑發送反向增強消息，抑制節點使用之前路徑傳輸數據GBR路由(Gradient-Based Routing)協議：梯度域擴展（傳感器節點到Sink節點的跳數信息、無線鏈路評估信息）EAR(Energy Aware Routing)路由協議：建立路由過程中加入能量評估機制；路由路徑的能量開銷大于某一閾值不采用；CADR路由(Constrained Anisotropic Diffusion routing)協議：興趣消息往指定方向發送定向擴散協議以

13、數據為中心的路由協議定向擴散協議以數據為中心的路由協議n優點優點數據中心路由，定義不同任務類型/目標區域消息；路徑加強機制可顯著提高數據傳輸的速率；周期性路由：能量的均衡消耗；n缺點缺點周期性的洪泛機制-能量和時間開銷都比較大；Sink周期性廣播，不適用于大規模網絡 節點需要維護一個興趣消息列表，代價較大；分層路由協議分層路由基本思想分層路由基本思想網絡劃分為多個簇，每個簇由簇頭和簇成員組成簇頭組成更高一級的網絡，簇頭管理簇內節點，收集融合簇內信息簇頭節點間還可以再次分簇分層結構擴展性較好，適合大規模網絡使用扁平結構路由協議容易使匯聚節點及周圍形成性能瓶頸，加重這些節點能量消耗，縮短網絡生命周

14、期。LEACH協議分層路由協議LEACH協議是最早最基本的一種分層路由算法，主要考慮簇內節點能耗使用Leach協議后，形成兩級星形結構簇頭作為一定區域所有節點的代理，負責和Sink的通信簇頭節點可以對所轄區域節點數據進行融合，減少網絡中傳輸的數據；簇內節點與簇頭距離近，使用小功率與簇頭節點通信，功耗小簇頭消耗大量能量，所以定期選舉簇頭，簇頭選舉算法的設計，要求保證公平性LEACH協議分層路由協議網絡按照周期工作，每個周期分為兩個階段：簇頭建立階段： 節點運行算法，確定本次自己是否成為簇頭（選簇）； 簇頭節點廣播自己成為簇頭的事實； 其他非簇頭節點按照信號強弱選擇應該加入的簇頭，并通知該簇頭節點

15、； 簇頭節點按照TDMA的調度，給依附于他的節點分配時隙；穩定工作階段： 節點在分配給他的時隙上發送數據；LEACH協議分層路由協議穩定工作階段： 只有簇頭節點一直保持活躍狀態 簇成員節點按需要保持活躍或者在不發送數據時進入睡眠狀態穩定工作狀態結束后，所有節點進入下一周期，重新建立簇并通信n優點優點每個節點都有機會擔任簇頭，能耗平均消耗；優化了傳輸數據所需能量；優化了網絡中的數據量（簇頭數據融合）；延長了網絡壽命；n缺點缺點節點硬件需要支持射頻功率自適應調整；無法保證簇頭節點能遍及整個網絡；分簇與簇頭選舉 要公平LEACH協議分層路由協議PEGASIS協議分層路由協議PEGASIS協議是對于L

16、EACH的一種改進，節點間不再組成簇，而是組成鏈PEGASIS協議基本原理： 1.假定傳感器節點是同構和相對靜止的 2.節點通過發送能量遞減的測試信號，確定相鄰節點的位置 3.進而了解網絡的全局信息 4.節點選擇其最近的鄰居作為鏈上的下一跳 5.節點只需維護自己上一跳和下一跳的鄰居信息PEGASIS協議分層路由協議鏈上的通信按照節點順序進行，下一跳節點匯聚來自上一跳的數據，直到鏈頭匯聚了鏈上所有節點的數據鏈頭節點通過傳遞令牌來控制節點間的通信次序PEGASIS協議分層路由協議n優點優點不需要周期性選舉簇頭節點；采用最佳鏈路進行數據傳輸；采用數據融合技術，減少了整體數據的發送和接收；降低能耗，相

17、對LEACH協議降低50%75%；延長網絡壽命。n缺點缺點節點維護位置信息需要額外資源；鏈頭通信量大，其失效會導致路由失敗；成鏈算法要求節點知道其他節點位置，開銷較大；如果鏈過長，傳輸時延會增大。TEEN協議分層路由協議TEEN協議按照分層結構組織節點，利用過濾方式減少數據傳輸量，即用來提供基于事件的數據傳遞。TEEN協議基本原理： 1.采用與LEACH協議相同的聚簇方式，但簇頭根據與匯聚節點的距離形成層次結構 2.聚簇完成后，匯聚節點通過簇頭向全網廣播兩個閾值(即硬閾值和軟閾值)以過濾數據的傳輸 3.在節點第一次監測到數據超過硬閾值時，節點向簇頭上報數據，并將當前監測數據保存為監測值(SV)

18、 4.此后只有當監測到的數據大于硬閾值而與SV之差不小于軟閾值時，節點才向簇頭上報數據，并更新SVTEEN協議分層路由協議硬閾值規定了什么情況下需要傳輸數據，即事件。軟閾值設置了事件發生時數據的傳輸頻率。通過引入兩個閾值限制，TEEN協議大幅減少了數據傳輸的次數。TEEN協議分層路由協議n優點優點通過硬閾值和軟閾值減少了數據傳輸量；多層次型簇頭結構不要求節點具有大功率通信能力；能耗低，適用于事件響應型應用。n缺點缺點如某節點的監測數據始終未達到硬閾值，則無法獲得該節點任何數據，也無法掌握該節點狀況，是否失效； 不適用于需周期性采樣的應用。GEAR協議基于地理位置的路由協議GEAR協議中，已知目

19、標區域的位置信息，節點知道自身位置信息和可用的能量信息。GEAR協議基本原理： 1.查詢消息到達目標區域的路徑：節點選擇傳輸代價最小的鄰居作為下一跳并轉發數據 2.查詢命令到達事件區域后，采用遞歸轉發或受限洪泛方式進行傳輸 3.節點會更新傳輸代價GEAR協議基于地理位置的路由協議節點利用貪心算法貪心算法選擇鄰居節點到達指定區域的代價估計代價： C(Ni ,R)=Distance( Ni , R) + (1)Left_Enery(Ni )實際代價：C(Ni ,R)=Enery_Cost(Ni ,R)+(1)Left_Enery(Ni ) Ni為有轉發需求的節點的鄰居節點，R為目標區域的中心位置。當N不知道Ni的實際代價時使用估計代價。GEAR協議基于地理位置的路由協議在遞歸轉發方式中，目標區域分成4個子區域，將查詢命令轉發至子區域中心子區域再次劃分并進行轉發，知道子區域只剩下一個節點，則該節點收到查詢命令后不再轉發GEAR協議基于地理位置的路由協議n路由