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

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

關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；多路徑路由；路由機制

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

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

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

1 多路徑路由協(xié)議介紹

1.１ SPIN協(xié)議［16］

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

圖1 SPIN路由建立與數(shù)據(jù)傳輸三步驟

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

1.２ Flooding協(xié)議［3］

Flooding協(xié)議是最為經(jīng)典和簡單的傳統(tǒng)網(wǎng)絡(luò)路由協(xié)議。節(jié)點產(chǎn)生或收到數(shù)據(jù)后，向鄰居節(jié)點廣播，直到數(shù)據(jù)包過期或到達目的節(jié)點；數(shù)據(jù)會經(jīng)過多條路徑到達目的節(jié)點。該協(xié)議本身算法簡單，容易實現(xiàn)，各節(jié)點不需要維護路由信息，協(xié)議健壯性強，但有內(nèi)爆和重疊問題，擴展性能很差。

1.3 ＤＤ協(xié)議［１7］

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

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

1.4 TBF協(xié)議［18］

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

1.5 SAR協(xié)議［19］

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

圖3 TBF協(xié)議沿任意路徑傳播數(shù)據(jù)示意圖

1.６ TORA協(xié)議［20］

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

圖4 TORA路由建立過程

1.７ ＳＭＲ［21］協(xié)議

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

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

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

1.８ MSR協(xié)議［10］

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

1.9 能量多路徑協(xié)議［22，23］

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

2 無線自組傳感網(wǎng)絡(luò)多路徑路由協(xié)議比較

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

3 多路徑路由研究思路及發(fā)展趨勢

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

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