無線傳感器網(wǎng)絡的路由協(xié)議

無線傳感器網(wǎng)絡

的路由協(xié)議路由協(xié)議概述無線傳感器網(wǎng)絡的路由協(xié)議主要任務是確保數(shù)據(jù)由源節(jié)點準確高效地傳輸?shù)侥康墓?jié)點，即尋找數(shù)據(jù)的最優(yōu)路徑以及沿最優(yōu)路徑發(fā)送數(shù)據(jù)。能耗：WSN中，路由協(xié)議的制定受能耗的限制。鄰居發(fā)現(xiàn)過程：鄰居節(jié)點間交換信息會消耗能量，交換數(shù)據(jù)越大，能耗越大。處理過程：數(shù)據(jù)傳輸過程的計算和通信會消耗能量，通信的能耗大于計算?？蓴U展性：路由協(xié)議需能滿足網(wǎng)絡拓撲形態(tài)的變化，即使發(fā)生變化，節(jié)點也能有效把握網(wǎng)絡傳輸路徑情況。編址：用戶對來自多個節(jié)點的整合后信息感興趣，而非單個節(jié)點，因此唯一編址方式不適合WSN健壯性：防止由于部分節(jié)點故障失效造成的信息丟失，以及信道不穩(wěn)定造成的信息受損和丟失。路由協(xié)議概述拓撲：路由協(xié)議需能適應WSN的拓撲變化。預訂拓撲：節(jié)點相對固定，可實現(xiàn)高效路由協(xié)議。隨機拓撲：網(wǎng)絡自組織，可利用拓撲發(fā)現(xiàn)作為路由計算的前提，路由協(xié)議也需適應節(jié)點或觀測目標的移動。設計目的：網(wǎng)絡的目的(上層應用)的不同導致路由協(xié)議原則的不同。路由協(xié)議概述WSN路由協(xié)議的分類能量感知路由WSN網(wǎng)絡是能量受限的網(wǎng)絡，節(jié)省能量是路由設計需考慮的重要因素。能量路由是WSN最基本的路由協(xié)議之一能量路由是根據(jù)節(jié)點可用能量(PowerAvailable，PA)或傳輸路徑上的能量需求(E)，選擇數(shù)據(jù)的轉發(fā)路徑。節(jié)點可用能量就是節(jié)點當前的剩余能量。基本能量路由能量感知路由基本能量路由路徑1：源—B—A—目標，

PA=4，E=3；路徑2：源—C—B—A—目標，

PA=6，E=6；路徑3：源—D—目標，

PA=3，E=4；路徑4：源—F—E—目標，

PA=5，E=6。最大PA路由：路徑2最小能耗路由：路徑1最少條數(shù)路由：路徑3最大平均路由：路徑4能量感知路由能量多徑路由能量多徑路由基本思想在源節(jié)點和目標節(jié)點之間建立多條數(shù)據(jù)傳輸路徑根據(jù)每條路徑上節(jié)點的剩余能量和傳輸消耗的能量來給每條路徑賦予一定的選擇概率依概率在多條路徑中選擇傳輸路徑，均衡消耗節(jié)點能量，延長網(wǎng)絡生存期傳統(tǒng)能量路由頻繁通過某一路徑傳輸數(shù)據(jù)，易導致該路徑上節(jié)點能量消耗過快，節(jié)點提早失效。能量感知路由能量多徑路由路徑建立建立從源節(jié)點到目的節(jié)點的多條路徑計算出各條路徑的選擇概率主要過程數(shù)據(jù)傳輸對于接收到的每組數(shù)據(jù)，節(jié)點根據(jù)概率從所有下一跳節(jié)點中選擇一個節(jié)點路由維護周期性從目的節(jié)點到源節(jié)點進行洪泛查詢以維護路徑的有效性和活躍性能量感知路由能量多徑路由路徑建立具體過程目的節(jié)點向鄰居廣播路徑建立消息鄰居收到消息，如處于目的節(jié)點和源節(jié)點之間則轉發(fā)，否則丟棄如節(jié)點決定轉發(fā)(加入路由集合)，則更新轉發(fā)消息中的代價值如選擇某一鄰居代價太高，則放棄選擇路由集合中的節(jié)點計算下一跳各選擇的概率，概率與代價成反比節(jié)點根據(jù)選擇概率和能量消耗計算自己到目的節(jié)點的傳輸代價泛洪是一種傳統(tǒng)的路由技術。泛洪算法的主要思想是由某節(jié)點發(fā)起數(shù)據(jù)廣播，然后任意一個收到廣播的節(jié)點都無條件將該數(shù)據(jù)包廣播出去，每一節(jié)點都重復這樣的過程直到數(shù)據(jù)遍歷全網(wǎng)或者達到規(guī)定的最大跳數(shù)。數(shù)據(jù)包像洪水一樣漫過所有地方，因此稱為洪泛協(xié)議。算法不用維護網(wǎng)絡拓撲結構和路由計算，實現(xiàn)簡單。但是最主要的是內(nèi)爆和重疊以及資源盲點等。洪泛(Flooding)協(xié)議以數(shù)據(jù)為中心的路由協(xié)議洪泛(Flooding)協(xié)議以數(shù)據(jù)為中心的路由協(xié)議內(nèi)爆現(xiàn)象：洪泛機制允許大量冗余消息，節(jié)點會收到來自多個鄰居節(jié)點轉發(fā)的相同消息。重疊現(xiàn)象：監(jiān)測同一區(qū)域的節(jié)點容易產(chǎn)生相同的信息，造成傳播過程中的信息冗余，消耗大量能量。謠言協(xié)議是對洪泛協(xié)議的改進。當節(jié)點收到數(shù)據(jù)包時，只將數(shù)據(jù)包隨機轉發(fā)給與其相鄰的節(jié)點的某一個節(jié)點或幾個，而不是所有節(jié)點。選定的鄰居也采用同樣的辦法轉發(fā)下去。優(yōu)點：降低數(shù)據(jù)轉發(fā)重疊的可能性，減少內(nèi)爆現(xiàn)象的發(fā)生。缺點：點到點的時延較大隨機轉發(fā)某一個節(jié)點的方向并不一定在距離目的節(jié)點更近的方向上，易造成數(shù)據(jù)超時或者跳數(shù)己達最大，導致遞送失敗。開始的短時間內(nèi)發(fā)送速率很大，隨著數(shù)據(jù)的發(fā)送，速度明顯降低。謠言(Gossiping)協(xié)議以數(shù)據(jù)為中心的路由協(xié)議SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議信息協(xié)商傳感器(SPIN)協(xié)議是

最基本的一類WSN路由協(xié)議，是對Flooding協(xié)議的改進?？紤]到WSN的數(shù)據(jù)冗余，臨近節(jié)點所感知的數(shù)據(jù)具有相似性，通過協(xié)商和能量自適應來減少數(shù)據(jù)傳輸量，解決洪泛協(xié)議存在的不足。SPIN協(xié)議采用了兩種機制：

在數(shù)據(jù)發(fā)送前通過協(xié)商確定是否發(fā)送

節(jié)點監(jiān)測自己的能量并進行能量感知決策SPIN協(xié)議假定兩點間的通信不受到其他節(jié)點的干擾，分組不會丟失，功耗無限制進。SPIN協(xié)議包括三種類型的消息：廣告消息(Advertise,ADV)、請求發(fā)送消息(Request,REQ)、數(shù)據(jù)消息(Datatransfer,DATA)SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議三次握手機制(點對點模式，即SPIN-PP)節(jié)點A向鄰居B發(fā)送ADV，ADV消息對DATA消息進行了描述。如果B對DATA消息感興趣，則發(fā)送REQ消息給A節(jié)點。A收到REQ后，將DATA消息發(fā)送給B節(jié)點。SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議三次握手機制(點對多點模式)節(jié)點B向多個鄰居節(jié)點發(fā)送ADV。有部分收到ADV的節(jié)點對DATA感興趣，回復REQ。B節(jié)點向回復REQ的節(jié)點發(fā)送DATA。SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議SPIN-EC機制(在SPIN基礎上加入能量感知功能)當一個節(jié)點的可用能量低于閾值，該節(jié)點不參與DATA消息的轉發(fā)。低能量節(jié)點只接收消息。通過減少參與轉發(fā)活動，能耗可降低10%。SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議SPIN-BC機制當一個節(jié)點發(fā)送REQ時，其他節(jié)點可以聽到此與DATA有關的REQ，則放棄此次發(fā)送REQ等待DATA消息。源節(jié)點收到REQ，會將DATA廣播出去，感興趣的節(jié)點可以收到這個DATA。SPIN-RL機制如一節(jié)點對DATA感興趣，但由于信道錯誤等原因，未收到DATA消息。該節(jié)點可以向其他可能收到DATA消息的鄰居節(jié)點發(fā)起傳輸請求，獲得DATA消息。優(yōu)點解決了內(nèi)爆問題和部分解決了重疊問題不需要進行路由維護對網(wǎng)絡拓撲變化不敏感，可用于移動WSN缺點本質(zhì)上SPIN還是向全網(wǎng)擴散新消息，開銷比較大當多個節(jié)點向同一個節(jié)點同時發(fā)送REQ時，需要退避算法SPIN協(xié)議以數(shù)據(jù)為中心的路由協(xié)議定向擴散協(xié)議以數(shù)據(jù)為中心的路由協(xié)議定向擴散(DirectedDiffusion)協(xié)議：匯聚節(jié)點接到上層應用的查詢?nèi)蝿蘸?，將興趣消息通過洪泛方式周期性地廣播出去，即告訴其他節(jié)點我要收集什么興趣。在傳輸過程中建立從數(shù)據(jù)源節(jié)點到匯聚節(jié)點的傳輸梯度。在區(qū)域內(nèi)“興趣”匹配節(jié)點沿著梯度方向通過路徑傳送數(shù)據(jù)到匯聚節(jié)點。四個階段：興趣擴散（采用泛洪）；梯度建立（反向建立）；強化路徑（匯聚節(jié)點會收到多條路徑，選最優(yōu)路徑，進行加強，以后的數(shù)據(jù)按照加強路徑傳送）數(shù)據(jù)傳輸匯聚節(jié)點向全網(wǎng)查詢興趣，鄰居節(jié)點更新自己的興趣緩存，并且轉發(fā)興趣緩存中的條目(興趣表項)時間戳：指示接收到相關興趣消息的最近時間梯度：當前節(jié)點從哪個鄰居收到興趣消息以及相應的數(shù)據(jù)傳輸率持續(xù)時間：該興趣消息的有效期定向擴散協(xié)議以數(shù)據(jù)為中心的路由協(xié)議路徑增強:在多條對應的梯度路徑中，匯聚節(jié)點可以對某一條路徑經(jīng)行梯度增強。沿這條路徑再次發(fā)送興趣消息當前節(jié)點選定下一跳，興趣消息只會發(fā)送給選定的下一跳節(jié)點逐跳傳導下去，即形成一條專門的路徑定向擴散協(xié)議以數(shù)據(jù)為中心的路由協(xié)議反向路徑增強:如之前的某條路徑遭到破環(huán)，匯聚節(jié)點需“增強”另一條路徑就可以改變數(shù)據(jù)的路由向之前的路徑發(fā)送反向增強消息，抑制節(jié)點使用之前路徑傳輸數(shù)據(jù)GBR路由(Gradient-BasedRouting)協(xié)議：梯度域擴展（傳感器節(jié)點到Sink節(jié)點的跳數(shù)信息、無線鏈路評估信息）EAR(EnergyAwareRouting)路由協(xié)議：建立路由過程中加入能量評估機制；路由路徑的能量開銷大于某一閾值不采用；CADR路由(ConstrainedAnisotropicDiffusionrouting)協(xié)議：興趣消息往指定方向發(fā)送定向擴散協(xié)議以數(shù)據(jù)為中心的路由協(xié)議定向擴散協(xié)議以數(shù)據(jù)為中心的路由協(xié)議優(yōu)點數(shù)據(jù)中心路由，定義不同任務類型/目標區(qū)域消息；路徑加強機制可顯著提高數(shù)據(jù)傳輸?shù)乃俾剩恢芷谛月酚桑耗芰康木庀?；缺點周期性的洪泛機制---能量和時間開銷都比較大；Sink周期性廣播，不適用于大規(guī)模網(wǎng)絡節(jié)點需要維護一個興趣消息列表，代價較大；分層路由協(xié)議分層路由基本思想網(wǎng)絡劃分為多個簇，每個簇由簇頭和簇成員組成簇頭組成更高一級的網(wǎng)絡，簇頭管理簇內(nèi)節(jié)點，收集融合簇內(nèi)信息簇頭節(jié)點間還可以再次分簇分層結構擴展性較好，適合大規(guī)模網(wǎng)絡使用扁平結構路由協(xié)議容易使匯聚節(jié)點及周圍形成性能瓶頸，加重這些節(jié)點能量消耗，縮短網(wǎng)絡生命周期。LEACH協(xié)議分層路由協(xié)議LEACH協(xié)議是最早最基本的一種分層路由算法，主要考慮簇內(nèi)節(jié)點能耗使用Leach協(xié)議后，形成兩級星形結構簇頭作為一定區(qū)域所有節(jié)點的代理，負責和Sink的通信簇頭節(jié)點可以對所轄區(qū)域節(jié)點數(shù)據(jù)進行融合，減少網(wǎng)絡中傳輸?shù)臄?shù)據(jù)；簇內(nèi)節(jié)點與簇頭距離近，使用小功率與簇頭節(jié)點通信，功耗小簇頭消耗大量能量，所以定期選舉簇頭，簇頭選舉算法的設計，要求保證公平性LEACH協(xié)議分層路由協(xié)議網(wǎng)絡按照周期工作，每個周期分為兩個階段：簇頭建立階段：

節(jié)點運行算法，確定本次自己是否成為簇頭（選簇）；簇頭節(jié)點廣播自己成為簇頭的事實；其他非簇頭節(jié)點按照信號強弱選擇應該加入的簇頭，并通知該簇頭節(jié)點；簇頭節(jié)點按照TDMA的調(diào)度，給依附于他的節(jié)點分配時隙；穩(wěn)定工作階段：節(jié)點在分配給他的時隙上發(fā)送數(shù)據(jù)；LEACH協(xié)議分層路由協(xié)議穩(wěn)定工作階段：只有簇頭節(jié)點一直保持活躍狀態(tài)

簇成員節(jié)點按需要保持活躍或者在不發(fā)送數(shù)據(jù)時進入睡眠狀態(tài)穩(wěn)定工作狀態(tài)結束后，所有節(jié)點進入下一周期，重新建立簇并通信優(yōu)點每個節(jié)點都有機會擔任簇頭，能耗平均消耗；優(yōu)化了傳輸數(shù)據(jù)所需能量；優(yōu)化了網(wǎng)絡中的數(shù)據(jù)量（簇頭數(shù)據(jù)融合）；延長了網(wǎng)絡壽命；缺點節(jié)點硬件需要支持射頻功率自適應調(diào)整；無法保證簇頭節(jié)點能遍及整個網(wǎng)絡；分簇與簇頭選舉要公平LEACH協(xié)議分層路由協(xié)議PEGASIS協(xié)議分層路由協(xié)議PEGASIS協(xié)議是對于LEACH的一種改進，節(jié)點間不再組成簇，而是組成鏈PEGASIS協(xié)議基本原理：

1.假定傳感器節(jié)點是同構和相對靜止的

2.節(jié)點通過發(fā)送能量遞減的測試信號，確定相鄰節(jié)點的位置

3.進而了解網(wǎng)絡的全局信息

4.節(jié)點選擇其最近的鄰居作為鏈上的下一跳

5.節(jié)點只需維護自己上一跳和下一跳的鄰居信息PEGASIS協(xié)議分層路由協(xié)議鏈上的通信按照節(jié)點順序進行，下一跳節(jié)點匯聚來自上一跳的數(shù)據(jù)，直到鏈頭匯聚了鏈上所有節(jié)點的數(shù)據(jù)鏈頭節(jié)點通過傳遞令牌來控制節(jié)點間的通信次序PEGASIS協(xié)議分層路由協(xié)議優(yōu)點不需要周期性選舉簇頭節(jié)點；采用最佳鏈路進行數(shù)據(jù)傳輸；采用數(shù)據(jù)融合技術，減少了整體數(shù)據(jù)的發(fā)送和接收；降低能耗，相對LEACH協(xié)議降低50%～75%；延長網(wǎng)絡壽命。缺點節(jié)點維護位置信息需要額外資源；鏈頭通信量大，其失效會導致路由失??；成鏈算法要求節(jié)點知道其他節(jié)點位置，開銷較大；如果鏈過長，傳輸時延會增大。TEEN協(xié)議分層路由協(xié)議TEEN協(xié)議按照分層結構組織節(jié)點，利用過濾方式減少數(shù)據(jù)傳輸量，即用來提供基于事件的數(shù)據(jù)傳遞。TEEN協(xié)議基本原理：

1.采用與LEACH協(xié)議相同的聚簇方式，但簇頭根據(jù)與匯聚節(jié)點的距離形成層次結構

2.聚簇完成后，匯聚節(jié)點通過簇頭向全網(wǎng)廣播兩個閾值(即硬閾值和軟閾值)以過濾數(shù)據(jù)的傳輸

3.在節(jié)點第一次監(jiān)測到數(shù)據(jù)超過硬閾值時，節(jié)點向簇頭上報數(shù)據(jù)，并將當前監(jiān)測數(shù)據(jù)保存為監(jiān)測值(SV)

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

1.查詢消息到達目標區(qū)域的路徑：節(jié)點選擇傳輸代價最小的鄰居作為下一跳并轉發(fā)數(shù)據(jù)

2.查詢命令到達事件區(qū)域后，采用遞歸轉發(fā)或受限洪泛方式進行傳輸3.節(jié)點會更新傳輸代價GEAR協(xié)議基于地理位置的路由協(xié)議節(jié)點利用貪心算法選擇鄰居節(jié)點到達指定區(qū)域的代價估計代價：

C(Ni

,R)=α?Distance(Ni,R)+(1?α)?Left_Enery(Ni

)實際代價：C(Ni

,R)=α?Enery_Cost(Ni

,R)+(1?α)?Left_Enery(Ni)Ni為有轉發(fā)需求的節(jié)點的鄰居節(jié)點，R為目標區(qū)域的中心位置。當N不知道Ni的實際代價時使用估計代價。GEAR協(xié)議基于地理位置的路由協(xié)議在遞歸轉發(fā)方式中，目標區(qū)域分成4個子區(qū)域，將查詢命令轉發(fā)至子區(qū)域中心子區(qū)域再次劃分并進行轉發(fā)，知道子區(qū)域只剩下一個節(jié)點，則該節(jié)點收到查詢命令后不再轉發(fā)GEAR協(xié)議基于地理位置的路由協(xié)議路由空洞鄰居節(jié)點傳輸代價都比本地節(jié)點大；選擇鄰居節(jié)點中代價最小的作為轉發(fā)節(jié)點；修改本地節(jié)點的轉發(fā)代價；