無線傳感器網絡路由協議研究進展

余 恒,王剛亮

三峽大學計算機與信息學院,湖北宜昌 443002

無線傳感器網絡路由協議研究進展

余 恒,王剛亮

三峽大學計算機與信息學院,湖北宜昌 443002

在無線傳感器網絡體系結構中，網絡層的路由技術至關重要。在介紹無線傳感器網絡的特點后，對現有的無線傳感器網絡路由協議進行了分類，然后著重分析了一些有代表性的路由協議的路由機制，并指出了這些協議的優缺點和應用范圍。最后結合該領域當前研究現狀，指出了路由協議未來的研究策略與發展趨勢。

無線傳感器網路；路由協議；路由分類；路由機制

0 引言

隨著微電子技術，無線通訊與傳感技術的發展，無線傳感器網絡[1]（Wireless Sensor Networks， WSNs）引起了人們廣泛的關注。WSNs是由部署在監測區域內的大量廉價微型傳感器節點組成，通過無線通訊方式形成的一個多跳的自組織的網絡系統。WSNs不需要固定網絡支持，在軍事國防，生物醫療，環境監測及智能家居等領域具有廣闊的應用前景[2]。

作為一種新型的無線自組網絡，無線傳感器網絡與傳統的移動自組織網絡（mobile Ad Hoc networks，MANET）有著明顯的差異，主要體現在：1）WSNs節點不移動或很少移動，而MANET節點移動性強；2）WSNs絡旨在收集信息，而MANET則傾向于分布式計算和端到端通信；3）WSNs節點的能量、存儲空間和計算能力有限；4）WSNs節點通訊高能耗，數據計算低能耗，節點會因能量耗盡而失效；5）WSNs節點數量更大，分布范圍更廣，節點沒有統一編址，節點之間通過廣播、多跳通信方式進行數據交換；6）WSNs節點產生的數據具有較大的冗余度；這些差異使得MANETs路由協議不適合直接運用到WSNs中，需要結合WSNs的特點對其進行改進，提出新的路由協議。本文對當前較為典型的路由協議進行了分類和總結，指出了路由協議將來發展的趨勢，目的在于為路由協議的進一步研究作參考。

1 傳感器網絡路由協議分類研究

近幾年，人們提出多種基于不同應用目標的路由協議，并根據不同的應用對路由進行了分類研究與比較[3，4]。無線傳感器網絡路由協議的研究最早從Flooding開始，逐漸得到關注。到目前為止，針對WSNs提出的具有代表性的路由協議有MDR、SAR、TBF、TEEN等。

為揭示協議特點，我們根據路由協議采用的路由結構、路由建立時機、數據傳輸模式等不同標準對其進行了分類。由于路由協議的研究人員組合多種策略來實現路由機制，故同一路由協議可分屬不同類別。

1.1 平面路由協議和層次路由協議

根據傳感器節點在路由過程中作用是否有差異、是否有層次結構，可以將路由協議分為平面路由協議和層次路由協議。

平面路由協議的優點是網絡中沒有特殊的節點，所有節點的地位是平等的，不存在等級和層次的差異。它們通過局部操作和信息反饋來生成路由，原則上不存在瓶頸問題。網絡流量均勻地分散在網絡中，路由算法易于實現，健壯性好。缺點是建立、維護路由的開銷大，數據傳輸跳數多，可擴展性小，在一定程度上限制了網絡的規模。

層次路由協議采用簇的概念對傳感器節點進行層次劃分。若干個相鄰節點構成一個簇，每一個簇有一個簇首。簇內通信由簇頭結點來完成。簇頭結點進行數據聚集和融合以減少傳輸的信息量，最后簇頭結點把融合的數據傳送給匯聚結點。層次路由擴展性好，適合大規模網絡，但簇的維護開銷大，且簇頭是路由的關鍵節點，其失效將導致路由失敗。

1.2 主動路由協議和被動路由協議

根據路由建立時機與數據發送的關系，可分為主動路由協議和被動路由協議。

主動路由協議，又稱表驅動的（table-driven）路由協議，它的路由發現策略與傳統路由協議類似，節點通過周期性地廣播路由信息分組，交換路由信息，主動發現路由。這一類的路由協議試圖在所有的網絡移動節點中維護一組到其他所有移動節點的一致的、實時的路由信息表。它的優點是當節點需要發送數據分組時，只要去往目的節點的路由存在，所需的延時很小。缺點是主動路由需要花費較大開銷，盡可能使得路由更新能夠緊隨當前拓撲結構的變化，浪費了一些資源來建立和重建那些根本沒有被使用的路由。而且，動態變化的拓撲結構可能使得這些路由更新變成過時信息，路由協議始終處于不收斂狀態。

被動路由協議也稱為按需（On Demand）路由協議。這種路由協議并不要求移動節點一直維護網絡的路由信息表，只有在節點需要某條路由時才動態的創建它。被動路由協議根據網絡分組的傳輸請求，被動地搜索從源節點到目的節點的路由。當沒有分組傳遞請求時，路由器處于靜默狀態，并不需要交換路由信息。拓撲結構和路由表內容按需建立，它可能僅僅是整個拓撲結構信息的一部分。它的優點是不需要周期性的路由信息廣播，節省了一定的網絡資源。缺點是發送數據分組時，如果沒有去往目的節點的路由，數據分組需要等待因路由發現引起的延時。

1.3 單路徑路由協議和多路徑路由協議

從路徑的表現形式上角度考慮，可分為單路徑路由協議和多路徑路由協議[5]。 單路徑路由節約存儲空間，數據通信量少；多路徑路由容錯性強，健壯性好，且可從眾多路由中選擇一條最優路由。

1.4 基于位置的路由協議和非基于位置的路由協議

根據是否以地理位置來標識目的地、路由計算中是否利用地理位置信息，可分為基于位置的路由協議和非基于位置的路由協議。有大量WSNs應用需要知道突發事件的地理位置，這是基于位置的路由協議的應用基礎，但需要GPS定位系統或者其他定位方法協助節點計算位置信息。

2 無線傳感器網絡路由協議分析

1）Flooding[6]：它是一個經典的傳統網絡路由協議，不要求維護網絡的拓撲結構和進行路由計算。在Flooding協議中，接收到數據的節點以廣播的方式向轉發分組，數據包直到過期或到達目的節點才停止傳播。該協議本身算法簡單，不需要維護路由信息，容易實現，但消息的“內爆”（implosion）和“重疊”（overlap）是其固有的缺陷。對此，S·hedetniemi等人提出了Gossiping策略，節點將產生或收到的數據隨機轉發，避免了內爆，但同時也增加了時延。

2）DD（Directed Diffusion）[7]：它是由加州大學洛杉磯分校計算機科學系的Deborah Estrin等人在DARPA的1997-98ISAT項目完成后提出的。這是一個基于數據的、查詢驅動的路由協議。DD路由機制分為周期性的興趣（Interest）擴散、梯度（gradient）建立和路徑加強三個階段。在興趣擴散階段，sink節點通過廣播興趣消息來尋找數據源。梯度建立階段，網絡中各節點對興趣消息進行緩存與合并，并創建包含上報率、下一條等信息的梯度，從而建立多條指向sink節點的路徑。路徑加強階段，sink節點會對最先收到消息的鄰節點發送路徑加強信息。接收到該信息的節點做路徑加強工作，源節點沿這個較高梯度的路徑發送數據。當主路徑失效時，其他發送梯度較小的路徑作為備用路徑，這種機制增強了路由的穩定性。然而，梯度建立的開銷很大，不適合多sink點網絡；數據聚合過程采用時間同步技術，會帶來較大開銷和時延。

3）MDR（Multi-path on-Demand Routing）：它是一種按需路由的多徑路由協議，僅在源節點和sink節點間有數據包傳輸才進行路由發現，建立新路徑，從而減少了通訊流量和能量損耗。MDR協議的路由機制包括路由請求和路由答復兩個過程。數據源先發送路由請求，向鄰居節點flooding短信息。當sink節點收到該信息后，馬上向轉發該路由請求消息的鄰節點返回路由答復信息，并且在數據包域中增加了一個跳數項，用來指示到目前為止它傳播的跳數。每個節點收到路由答復后增加一跳，繼續轉發給相應鄰節點直至到達數據源。它的建立過程如圖1所示。該協議健壯性好，即使網絡拓撲頻繁發生變化，數據依然能可靠地傳輸到目的地。由于發送端將源數據分裂成有冗余的子數據包后傳輸，這相對于發送相同的數據包副本減少了網絡數據流量，因而平衡了網絡的數據流量和可靠性，相應也提高了網絡的安全性。

圖1 MDR 路由建立過程

4）SAR（Sequential Assignment Routing）[8]： 它 是 1999年Katayoun Sohrabi等人在DARPA支持的一個研究中提出的一種保證QoS的路由協議。協議中sink節點的所有一跳鄰節點都以自己為根建立生成樹，其余各節點根據時延、丟包率等QoS參數來反向建立到sink節點的多條路徑。在選擇路徑時， SAR協議充分考慮了功耗和分組優先權等特殊要求，采用局部路徑恢復和多路徑備份策略，避免由于節點或鏈路失敗而引起的重新計算路由的開銷。

5）TinyOS Beaconing[9]：該協議路由算法較為簡單，路由建立前先對網絡中的所有節點進行編址。sink節點對其信號覆蓋范圍內的所有節點周期性廣播路由更新消息，接收到消息的節點將該sink點作為父節點保存到路由表中，然后在物理信道上廣播該消息。該路由機制適合小規模網絡，在較大網絡中將導致節點和sink點間跳數增加；廣播式路由更新消息消耗網絡能量；路徑建立只與接收到beaconing的時序有關，不進行任何優化，擴展性差；sink點周圍的節點由于過多地參與數據傳輸，耗能較多，容易失效。

6）SPIN（Sensor Protocols for Information via Negotiation）[10]：它是第一個基于數據協商的路由協議。SPIN路由建立基于三次握手過程：ADV→REQ→DATA。路由建立過程如圖2所示。節點產生或收到數據后，為避免盲目傳播，用包含元數據的ADV消息向鄰節點通告，需要數據的鄰節點用REQ消息提出請求，數據通過DATA消息發送到請求節點。該協議通過ADV消息和數據命名機制解決了Flooding協議中的內爆和重疊問題。與Flooding和Gossiping協議相比，該協議有效地節約了能量。但是它也有缺點：當產生或接收數據節點的所有鄰節點均不需要該數據時，將導致數據不能繼續轉發，會使較遠節點無法得到數據。當網絡中大多節點都是潛在sink點時，問題并不嚴重，但當sink點較少時，則是一個很嚴重的問題；而且當某sink點對任何數據都需要時，其周圍節點的能量容易耗盡。

圖2 SPIN路由建立過程

7）TBF（Trajectory Based Forwarding）：它是基于源站和位置的路由協議。與通常的源站路由協議不同，TBF協議在數據包頭中指定連續的傳輸軌道參數，中間各節點根據參數按貪心算法，計算出軌道最近的下一跳節點。通過指定不同的軌道參數，很容易實現多路徑傳播和廣播。由于是源站路由協議，數據包頭的路由信息開銷不會隨著網絡變大而增加，從而避免了傳統源站路由協議的缺點。但隨著網絡規模變大，路徑加長，網絡中節點進行計算的開銷也相應增加。

8）LEACH（Low Energy Adaptive Clustering Hierarchy）[11]：它是2000年麻省理工學院電子工程和計算機科學系的Wendi Heizelman等人為無線傳感器網絡專門設計的分簇路由協議。LEACH的基本思想：通過等概率地隨機循環選擇簇頭，將整個網絡的能量負載平均分配到每個傳感器節點，從而達到降低網絡能量耗費、延長網絡生命周期的目的。簇頭是周期性按輪隨機選舉的，每輪選舉方法是：在簇的建立階段，每個節點選取一個介于0和1之間的隨機數，如果這個數小于某個閾值，該節點成為簇頭；然后，簇頭向所有節點廣播自己成為簇頭的消息；每個節點根據接收到廣播信號的強弱來決定加入哪個簇，并回復該簇頭。在數據傳輸階段， 簇內的所有節點按照TDMA（時分復用）時隙向簇頭發送數據，簇頭將數據融合之后把結果發給基站。該協議采用隨機選舉簇頭的方式避免簇頭過分消耗能量，提高了網絡生存時間。簇間路由采用一跳通訊，雖然傳輸時延小，但節點的通訊能耗較高且擴展性差。

9）TEEN（Threshold Sensitive Energy Efficient Sensor Network Protocol）：它利用過濾方式來減少數據傳輸量。該協議采用與LEACH協議相同的聚簇方式，但簇頭根據與sink點距離的不同形成層次結構。TEEN定義了硬、軟兩個門限來過濾發送數據。只有滿足如下兩個條件的時候才能發送數據：當前數據的屬性值大于硬門限；當前數據的屬性值與上一次發送數據的屬性值之間的差距大于軟門限。該協議通過利用軟、硬門限減少了數據傳輸量。其缺點是：如果數據的屬性值一直達不到門限，節點不會發送數據，用戶將接收不到網絡的任何數據，并且不能得知所有節點是否死亡。

3 結論與展望

在無線傳感器網絡路由協議中，單路徑路由協議算法簡單，數據通信量少，有利于節省節點能量，但是其容錯性和健壯性差。多路徑路由協議在路由發現過程中得到多條不相關路徑，減少了路由發現次數，并增強了路由的穩定性。

平面路由協議健壯性好，但建立和維護路由的開銷大，數據傳輸跳數多，適合小規模網絡。層次路由協議擴展性好，其能量消耗比較均衡，但簇的維護開銷大。由于簇頭是路由的關鍵節點，其失效將導致路由失敗。

主動型路由協議需要定期更新路由，而響應性路由協議只有當網絡中有數據傳輸時才會建立和更新路由。如果網絡的數據傳輸量很大，主動型路由協議的路由開銷一般要比響應型路由協議小。

無線傳感器網絡由于能量限制、拓撲變化及帶寬限制，對路由算法要求非常高。目前傳感器網絡路由協議的研究重點主要集中在能量效率上，高效利用能量幾乎是設計的第一策略。設計兼有平面結構和分簇結構優點的新型數據傳輸模式，是目前研究的一個熱點。在某些基于簇的路由協議中，并沒有簇頭的概念，每個節點知道它將轉發的下一個節點，我們把這類協議叫做基于虛擬簇的平面路由協議。這類協議既能有效地管理網絡拓撲結構，又能有效地利用能量傳輸數據。此外，如何在簇內和簇間進行數據融合和處理，也很值得探索。

未來的研究中可能還需要解決由視頻和圖像傳感以及實時應用引起的QoS問題。能量感知的QoS分簇路由越來越受到重視，它將在目標的實時追蹤等方面得到應用，這就對帶寬保證和能量高效路徑的有效利用提出了嚴格要求。

[1]REN Fengyuan，HUANG Haining， LIN Chuang。 Wireless sensor networks[J].Journal of Software，2003，14(2)：1148-1157.

[2]MA Zuchang，SUN Yining， MEI Tao。 Survey on wireless sensors network[J].Journal of China Institute of Communications，2004(4)：114-124.

[3]FAN Xinyun，WANG Fubao，REN Fengyuan.Routing protocol for wireless sensor networks.Computer Automated Measurement & Control，2005(9)：1010-1013.

[4]CHEN Yuequan，GUO Xiaofeng，ZENG Qingka，iet al.Multipath routing research in mobile ad hoc networks[J].Computer Science，2005，32(6)：33-36.

[5]TANG Yong，ZHOU Mingtian，ZHANG Xin.Overview of routing protocols in wireless sensor networks[J].Journal of Software，2006，17(3)：410-421.

[6]Haas ZJ，Halpern JY，Li L.Gossip-Based ad hoc routing.In：Proc。of the IEEE INFOCOM。New York：IEEE Communications Society，2002：1707-1716.

[7]Intanagonwiwat C，Govindan R，Estrin D，iet al。 Directed diffusion for wireless sensor networking。IEEE/ACM Trans.on Networking，2003，11(1)：2-16.

[8]Sohrabi K，Gao J，Ailawadhi V，iet al。 Protocols for self-organization of a wireless sensor network.IEEE Personal Communications，2000，7(5)：16-27.

[9]Karlof C，Wagner D.Secure routing in sensor networks：attacks and countermeasures.Ad Hoc Networks，2003，1(1)：293-315.

[10]Kulik J，Heinzelman WR， Balakrishnan H. Negotiation based protocols for disseminating information in wireless sensor networks。Wireless Networks，2002，8(2-3)：169-185.

[11]Hu Junping，Jin Yuhui，Dou Liang.A Time-based Cluster-Head Selection Algorithm for LEACH.IEEE Symposium on Computers and Communications，2008：1172-1176.

TN8

A

1674-6708（2011）35-0173-03