無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進展

余 恒,王剛亮

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

無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進展

余 恒,王剛亮

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

在無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中，網(wǎng)絡(luò)層的路由技術(shù)至關(guān)重要。在介紹無線傳感器網(wǎng)絡(luò)的特點后，對現(xiàn)有的無線傳感器網(wǎng)絡(luò)路由協(xié)議進行了分類，然后著重分析了一些有代表性的路由協(xié)議的路由機制，并指出了這些協(xié)議的優(yōu)缺點和應(yīng)用范圍。最后結(jié)合該領(lǐng)域當前研究現(xiàn)狀，指出了路由協(xié)議未來的研究策略與發(fā)展趨勢。

無線傳感器網(wǎng)路；路由協(xié)議；路由分類；路由機制

0 引言

隨著微電子技術(shù)，無線通訊與傳感技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)[1]（Wireless Sensor Networks， WSNs）引起了人們廣泛的關(guān)注。WSNs是由部署在監(jiān)測區(qū)域內(nèi)的大量廉價微型傳感器節(jié)點組成，通過無線通訊方式形成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。WSNs不需要固定網(wǎng)絡(luò)支持，在軍事國防，生物醫(yī)療，環(huán)境監(jiān)測及智能家居等領(lǐng)域具有廣闊的應(yīng)用前景[2]。

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

1 傳感器網(wǎng)絡(luò)路由協(xié)議分類研究

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

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

1.1 平面路由協(xié)議和層次路由協(xié)議

根據(jù)傳感器節(jié)點在路由過程中作用是否有差異、是否有層次結(jié)構(gòu)，可以將路由協(xié)議分為平面路由協(xié)議和層次路由協(xié)議。

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

層次路由協(xié)議采用簇的概念對傳感器節(jié)點進行層次劃分。若干個相鄰節(jié)點構(gòu)成一個簇，每一個簇有一個簇首。簇內(nèi)通信由簇頭結(jié)點來完成。簇頭結(jié)點進行數(shù)據(jù)聚集和融合以減少傳輸?shù)男畔⒘?，最后簇頭結(jié)點把融合的數(shù)據(jù)傳送給匯聚結(jié)點。層次路由擴展性好，適合大規(guī)模網(wǎng)絡(luò)，但簇的維護開銷大，且簇頭是路由的關(guān)鍵節(jié)點，其失效將導(dǎo)致路由失敗。

1.2 主動路由協(xié)議和被動路由協(xié)議

根據(jù)路由建立時機與數(shù)據(jù)發(fā)送的關(guān)系，可分為主動路由協(xié)議和被動路由協(xié)議。

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

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

1.3 單路徑路由協(xié)議和多路徑路由協(xié)議

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

1.4 基于位置的路由協(xié)議和非基于位置的路由協(xié)議

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

2 無線傳感器網(wǎng)絡(luò)路由協(xié)議分析

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

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

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

圖1 MDR 路由建立過程

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

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

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

圖2 SPIN路由建立過程

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

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

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

3 結(jié)論與展望

在無線傳感器網(wǎng)絡(luò)路由協(xié)議中，單路徑路由協(xié)議算法簡單，數(shù)據(jù)通信量少，有利于節(jié)省節(jié)點能量，但是其容錯性和健壯性差。多路徑路由協(xié)議在路由發(fā)現(xiàn)過程中得到多條不相關(guān)路徑，減少了路由發(fā)現(xiàn)次數(shù)，并增強了路由的穩(wěn)定性。

平面路由協(xié)議健壯性好，但建立和維護路由的開銷大，數(shù)據(jù)傳輸跳數(shù)多，適合小規(guī)模網(wǎng)絡(luò)。層次路由協(xié)議擴展性好，其能量消耗比較均衡，但簇的維護開銷大。由于簇頭是路由的關(guān)鍵節(jié)點，其失效將導(dǎo)致路由失敗。

主動型路由協(xié)議需要定期更新路由，而響應(yīng)性路由協(xié)議只有當網(wǎng)絡(luò)中有數(shù)據(jù)傳輸時才會建立和更新路由。如果網(wǎng)絡(luò)的數(shù)據(jù)傳輸量很大，主動型路由協(xié)議的路由開銷一般要比響應(yīng)型路由協(xié)議小。

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

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

[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