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

摘 要：在研究目前存在的多徑路由協議特點及核心路由機制基礎上，總結了多路徑路由協議的特征，并對不同的多路徑路由相關項進行了比較。最后指出了多路徑路由的研究思路以及未來的發展趨勢。

關鍵詞：無線傳感網絡；多路徑路由；路由機制

中圖分類號：TP393.04文獻標志碼：A

文章編號：1001-3695(2007)06-0001-03

隨著微機電技術、傳感器技術、通信技術、嵌入式計算技術、分布式信息處理技術和網絡技術的發展，易分布、低功耗的無線自組傳感網絡研究在世界范圍內越來越受到重視，在軍事、商業及智能家具等領域具有廣闊的應用前景。無線自組傳感網絡通常由大量具有信息采集、數據處理和轉發路由功能的節點，通過無線多跳通信方式形成無線自組傳感網絡系統。與傳統網絡相比，其主要特征如下：①能量受限。網絡節點通常攜帶不能補充的有限能量。②無中心自組織。網絡中各節點是在隨機部署后，按照一定算法自動組織成面向應用的網絡。③拓撲動態變化。移動終端能以任意速度和移動模式移動，并可以隨時關閉電臺；加上天線類型的多種多樣、發動功率的變化、無線信道間的相互干擾、地形和天氣等綜合因素的影響，拓撲可能隨時發生變化。變化的方式及速度均難以預測，主要體現在節點和鏈路的狀態及分布變化上。無線自組傳感網絡有易部署、自組織、監測精度高、容錯性高、覆蓋區域大、可遠程監控等優點。其缺點是，能量受限、資源受限、拓撲變化頻繁等。因此，傳統的路由機制不適應無線傳感網絡，必須設計與之相應的路由協議。近幾年，人們提出多種基于不同應用目標的路由協議［1~3］，并根據不同的應用對路由進行了分類研究與比較［1，2，4］。但是，大部分協議均是基于單路徑的路由協議，如DSR［5］、AODV［6］等。單路徑路由傳輸數據時控制包的開銷和網絡延遲都較大。在負載較大時，將面臨網絡擁塞或節點能量快速消耗的問題。在視頻處理方面，傳輸延遲不能保證視頻服務質量。多路徑路由在這些方面均體現出單路徑路由難以實現的優勢。因此，多路徑路由算法的研究引起了人們的重視。一些多路徑路由協議是對單路徑路由協議的擴展，在單路徑路由機制基礎上增加多路徑處理機制。文獻［7］MDSDV是基于ＤＳＤＶ的多路徑路由。文獻［8，9］AOMDV是基于AODV的多路徑路由。文獻［10~12］是基于ＤＳＲ的路由協議，在路由發現過程中得到多條不相關路徑，減少了路由發現次數，并增強了路由的穩定性。目前人們對多路徑路由機制的研究正逐步深入。文獻［13］對不相交多路徑和纏繞多路徑路由在能量消耗、延遲等方面進行了分析比較。文獻［14］建立了多路徑路由分析模型，提出把總通信流量分流的策略，以提高網絡的網絡吞吐量、健壯性、穩定性，并分析鏈路斷鏈的概率。文獻［15］對基于多路徑路由的視頻流資源分配進行了研究。

1 多路徑路由協議介紹

1.１ SPIN協議［16］

Sensor Protocols for Information via Negotiation(SPIN)協議是第一個基于數據協商的路由協議。SPIN路由建立基于三次握手過程：ＡＤＶREQDATA；運行SPIN協議的節點稱為SPIN節點。ＳＰＩＮ節點在產生或收到數據后，對元數據進行命名，用包含元數據的ＡＤＶ消息向鄰節點進行通告。需要數據的鄰節點用REQ消息提出請求，數據通過ＤＡＴＡ消息發送到請求節點。路由建立過程如圖１所示。

圖1 SPIN路由建立與數據傳輸三步驟

SPIN協議的ADV消息減輕了內爆和數據重疊問題。SPIN協議節點可根據自身資源和數據信息決定是否進行ADV通告；與Flooding和Gossiping協議相比，有效地節約了能量［２］。但是它也有缺點：當產生或收到數據節點的所有鄰節點均不需要該數據時，將導致數據不能繼續轉發，會使較遠節點無法得到數據。

1.２ Flooding協議［3］

Flooding協議是最為經典和簡單的傳統網絡路由協議。節點產生或收到數據后，向鄰居節點廣播，直到數據包過期或到達目的節點；數據會經過多條路徑到達目的節點。該協議本身算法簡單，容易實現，各節點不需要維護路由信息，協議健壯性強，但有內爆和重疊問題，擴展性能很差。

1.3 ＤＤ協議［１7］

Directed Diffusion Protocol(DD)協議是一個基于數據查詢驅動的路由協議。匯聚節點通過興趣（Interest)消息發出查詢任務，采用洪泛方式傳播興趣消息，如溫度、震動、光線強度等消息。興趣傳播過程中，每個節點建立反射的從數據源到匯聚節點的數據傳輸梯度。路由機制分為興趣擴散、梯度建立及路徑加強三個階段，如圖２所示。圖2 DD協議簡單示意圖

興趣擴散階段，匯聚節點周期性地向鄰居節點廣播包含任務類型、目標區域、數據發送速率、時間戳等參數的興趣消息；接收消息的節點，緩存查詢信息，進行局部數據聚集。當接收到查詢信息時，若當前緩存沒有相同記錄，則加入新記錄；記錄中包含有鄰節點指定的數據發送率，即梯度。數據傳送階段，匯聚節點會對最先收到消息的鄰節點發送路徑加強信息；接收到加強路徑的節點做路徑加強工作，目標數據沿這個較高梯度的路徑發送數據；當主路徑失效時，其他發送梯度較小的路徑作為備用路徑。這種機制增強了路由的穩定性。

1.4 TBF協議［18］

Trajectory Based Forwarding(TBF)協議是基于源路由的路由協議。協議在數據包頭中指定連續的傳輸軌道參數，中間各節點根據參數按貪心算法，計算出軌道最近的節點下一跳節點。協議通過指定不同的軌道參數，實現多路徑傳播或廣播。由于是源路由協議，節點不需要緩存來存儲大量路由信息。與其他源路由協議不同，數據包頭中不是節點信息，包頭規模不會隨著網絡變大而增加，并可適應網絡的變化；但是中間各節點的計算量，會隨著網絡的擴大而相應增加。在ＧＰＳ系統的協助下，它可以沿任意方式傳播，如圖3所示。

1.5 SAR協議［19］

Sequential Assignment Routing(SAR)協議是WSNs中第一個保證ＱoＳ的主動路由協議［２，2０，2１］。匯聚節點的所有一跳鄰居節點都以自己為根創建生成樹；各節點根據時延、丟包率等ＱoＳ參數建立反向到匯聚節點的多條路由；發送數據時，選擇其中一條或多條路由進行傳輸。其優點是能夠提供ＱoＳ保證；缺點是大量的冗余路由信息消耗了存儲資源，路由信息的維護及計算也需要大量開銷。

圖3 TBF協議沿任意路徑傳播數據示意圖

1.６ TORA協議［20］

TemporallyOrdered Routing Algorithm(TORA)協議是在有向無環圖（ＤＡＧ）基礎上提出的一種按需路由協議，分為三個過程：①路由發現。與其他按需路由一樣，擴散路由請求分組；不同的是路由回答分組中，每個節點分配一個相對于源節點的高度值，源節點最高、目的節點最低，通過相鄰節點的比較，形成一條或多條路徑。②路由維護。修改相關節點的高度值和狀態表，建立新路由。路由建立過程如圖４所示。③路由刪除。刪除無效路由。TORA消除環路問題，并可提供多條路徑。

圖4 TORA路由建立過程

1.７ ＳＭＲ［21］協議

Split Multipath Routing(SMR)協議是按需源路由的多路徑路由協議。路由過程分為路由發現、路由維護。當源節點需要到目的節點路由而又沒有路由信息時，擴散Route Request(RREQ)消息到全網；中間節點不允許向源節點發送回復包，只是把自己的節點加入到路徑中。目的節點接收到從源節點發來的多條路徑消息時，向源節點回送包含整條路徑消息的Route Reply(RREP)包。協議的主要目的是建立最大不相交的多條路徑，以防止網絡擁塞，并有效地初始化可用的網絡資源。ＳＭＲ路由建立過程如圖５所示。

圖5 SMR路由請求及可用多路徑示意圖

ＳＭＲ協議在初始化路由請求時，由于采用洪泛方式，占用資源較多；由于采用資源路由方式，包頭信息占用了不少字節。但是，中間節點不用Cache，每個節點僅占用很少的存儲空間，并且此路由協議提供ＱoS支持。

1.８ MSR協議［10］

Multipath Source Routing(MSR)協議是根據ＲＴＴ對ＤＳＲ協議的路由發現和路由維護進行擴展以適應多路徑路由，在路由發現階段返回多條路徑。路由發現階段，在ＤＳＲ路由發現機制基礎上加入多路徑適應機制，并將發現的路由按唯一序號保存在路由緩沖中。多路徑路由機制中，路由獨立性是非常重要的屬性。ＭＳＲ路由中，源節點根據權重來選擇路徑以保證負載平衡。選擇計算公式為

1.9 能量多路徑協議［22，23］

能量多路徑路由（EAMR）［22］機制是在源/目的節點間建立多條路徑，在多條路徑上傳輸數據的多個拷貝或把數據分成多個相等部分并發傳輸，使得數據傳輸均衡消耗整個網絡的能量，延長整個網絡生存期。由于節點選擇概率是能量相關的，其將通信能量消耗分散到多條路徑上。EAMR協議可以實現整個網絡能量消耗均衡，最大限度地延長網絡生存期。MMER［23］協議以不相交多路徑數據傳輸方式，按全局能量最小化的路由機制設計路由，以達到均衡能量消耗及能量高效的目的。

2 無線自組傳感網絡多路徑路由協議比較

不同的多路徑路由協議機制不同，具體面向的應用也各有特點，難以進行比較。本文采用列表的形式，對一些多路徑路由協議進行總結與比較，如表1所示。

3 多路徑路由研究思路及發展趨勢

無線自組傳感網絡由于能量限制、拓撲變化及帶寬限制，對路由算法要求非常高。多路徑路由由于延遲小、負載均衡、吞吐量大等優點，逐漸引起人們的重視。多路徑路由主要分為兩類：①對單路徑路由的擴展。路由機制是在路由發現時，記錄多條路由作為當前路由的備選路由，當活動路由失效后，從多路徑中選擇一條繼續路由，不需要重新發起路由發現過程。②多路徑并行傳輸的多路徑路由。它是在多條路徑之間根據資源、跳數、延遲等策略，合理分配負載，以快速達到路由的目的。設計多路徑路由時，應考慮以下幾個方面：①算法盡量簡單。②路徑的規模不能過大。如果規模過大，就會造成系統資源緊張甚至過度消耗，導致網絡性能下降。③路由穩定性好。網絡拓撲本身就是變化的，如果路由不穩定，路由維護消耗大，路由效率反而會降低。④負載分配算法要合理。合理地分配系統資源，根據各路徑上資源情況分配負載，可以減少傳輸延遲，增加傳輸速率和系統吞吐量、均衡能量消耗，提高網絡壽命。因此，在研究多路徑路由協議時，根據不同應用，要綜合考慮以上幾種情況，還要結合當前路由技術中的數據跨層、數據融合、分簇和定位等，優化多路徑路由算法。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。