基于網絡編碼的無線網絡路由協議

巖 延 張寶賢 馬 建

摘要:基于機會的網絡編碼方法(COPE)研究網絡編碼在無線環境中的協議層面上具體實現的問題,但COPE被動地等待編碼機會的出現。為了更大限度的提高網絡編碼的性能,需要將網絡編碼與無線路由協議相結合來在無線節點上創造出更多的編碼機會以減少總的傳輸次數,以有效的提升網絡的吞吐量。當前的編碼感知路由算法主要包括基于Markovian路由度量的路由協議、編碼感知機會路由協議(CORE)、分布式編碼感知路由協議(DCAR)、速率匹配的編碼感知多路徑路由協議(RCR)、編碼感知多路徑路由協議(CAMP)等。無線網絡內的編碼感知路由領域中新型路由度量和跨層設計等問題還需要進一步研究。

關鍵詞:無線網絡;網絡編碼;單播路由;編碼感知路由

Abstract: Cope, an opportunistic network coding mechanism, investigates how to implement network coding in a wireless network. However, Cope passively waits for the appearance of network coding opportunities. To further improve the performance of network coding, integration of network coding and wireless routing protocol is required to greatly improve the throughput of wireless networks by creating more coding opportunities at wireless nodes. In this article, we introduce typical coding-aware wireless routing protocols, which mainly include Markovian metric based routing protocol, coding-aware opportunistic routing mechanism CORE, Distributed Coding-Aware Routing (DCAR), Rate-Adaptive Coding-Aware Multiple Path Routing (RCR), and Coding-Aware Multi-Path Routing (CAMP). Some problems like selection of new routing metric and cross layer design still require further investigation to enable efficient coding-aware routing.

Key words: wireless networks; network coding; unicast routing; coding-aware routing.

網絡編碼(NC)使得網絡節點既實現路由功能又實現編碼功能,已被證明是可以逼近網絡容量理論傳輸極限的有效方法[1]。2000年,R.Ahlswede等人發表了文章“Network information flow”[2]證明了組播網絡在網絡編碼傳輸模式下可以達到極大流容量理論上限。網絡編碼剛提出的幾年,研究工作主要集中在網絡編碼的理論以及構造和應用等方面。從2005年后,許多國外學者開始研究無線網絡中的網絡編碼,然而網絡編碼在無線網絡(包括無線自組織網絡、無線Mesh網絡、無線傳感器網絡)的研究和應用還處于起步的階段。

無線網絡與有線網絡中的網絡編碼的理論和應用有著顯著的差別,這主要是由無線網絡的結構特征決定的。同時無線網絡環境也是網絡編碼非常適宜的一個應用領域。因為無線鏈路的不可靠性和物理層廣播特性非常適合使用編碼的方法。相對于傳統網絡編碼機制來說,無線網絡中的網絡編碼尤其能夠增加單播流的吞吐量,這也是無線網絡中的網絡編碼與傳統網絡編碼主要區別之一,這同樣得益于無線介質的廣播特性。圖1所示為一無線網絡中3節點使用網絡編碼進行通信的例子:節點A、節點B相互傳遞信息p1、p2。圖1中的箭頭代表無線鏈路。圖1(a)采用傳統的無線通信方式,這樣需要4次傳輸來完成報文的交換。但是如果利用無線介質的廣播特性,將p1和p2作異或運算后直接轉發出去,則在節點B處,根據接收到的信息可恢復出p1來;同理,在節點A處也可以恢復出信息p2來。因此采用了網絡編碼技術后(見圖1(b)),只需要使用3次傳輸就可以實現傳統方式的所有通信要求。

基于上述思想,Katti等提出基于機會的網絡編碼方法(COPE)[3],COPE是首次研究網絡編碼在無線環境中的協議層面上具體實現的問題。COPE協議使用機會監聽以及接收報告來獲取鄰居節點所存儲的報文信息。在得到所有鄰居節點所存儲的報文信息后,每個節點獨立的利用本地信息決定哪些數據包需要進行編碼以及如何進行編碼,以最大化一次傳輸中所能夠發送的報文數量。通過COPE,無線網絡的吞吐量可以得到有效的提高。

1 無線網絡中的編碼感知路由協議

當前的無線網絡中的網絡編碼協議,如COPE等方案多半被動的等待編碼機會的出現,這種被動的策略很大程度上限制了網絡編碼提高網絡吞吐量的能力。為了更大限度的提高網絡編碼的性能,需要更有效的方案來在無線節點上創造出更多的編碼機會以減少總的傳輸次數,以有效的提升網絡的吞吐量。

從COPE協議中可以看出,節點上的編碼機會多少主要是由節點附近的流模式所決定的。路由協議的主要功能就是完成網絡流的路由和尋址。因此如果將無線網絡路由機制與網絡編碼機制進行有效的結合,設計出編碼感知的無線自組織網絡路由協議,為節點創造出更多的編碼機會,就能有效的提高網絡的吞吐量。如圖2所示,有兩個網絡流,分別為從A到E以及從F到A。如果采用傳統的最短路徑路由機制,則兩個流的路徑分別為A→B→C→E以及F→D→B→A。網絡中沒有編碼機會。如果從F到A的路徑變為F→E→C→B→A,雖然比最短路徑多了一跳。但是在節點C和B出創造出了編碼機會,從而有效的提升了網絡的吞吐量。

下面將分別介紹采用不同策略進行編碼感知路由的協議,著重介紹各協議的主要工作機制,并討論它們的優缺點。

無線自組織網絡中的編碼感知路由主要可以分為兩大類:集中式和分布式。

1.1 集中式算法

Sengupta等人[4]首次從理論分析的角度給出了COPE類型的網絡編碼機制在無線網絡中所能帶來的吞吐量提升。方案通過線性優化的方式給出了如何計算任意無線多跳網絡拓撲以及任意多并發單播流量模式下的網絡吞吐量,同時研究了無線路由選擇與編碼機會多少的折中,即將網絡中并發的多個單播流以“靠近的路由方式”路由以獲得更多編碼機會,還是以“遠離的路由方式”方式路由以減少無線干擾。同時考慮節點間無線廣播傳輸的調度,以適應無線發送/傳輸的多樣性以及鏈路間的干擾。模擬結果顯示如果路由能夠感知編碼機會的存在,則網絡的吞吐量能夠比單純的應用COPE類型的網絡編碼得到顯著的提高。

Ni等人[5]從另一個角度對編碼感知的路由協議對網絡的吞吐量所帶來的提升做出了理論上的分析。協議定義了期望的編碼傳輸數目(ECX)。與傳統無線網絡路由協議所采用的度量,如跳數、期望傳輸數目(ETX)[6]等不同,ECX定義了兩個節點通過一個中間節點采用網絡編碼機制后成功交換報文所需的傳輸次數。在定義了ECX后,協議將編碼感知的路由問題轉化為一個線性優化的問題。模擬結果同樣顯示編碼感知的路由可以有效提升網絡的吞吐量。

1.2 分布式算法

集中式算法能夠從全局對算法進行優化,然而算法的復雜度較高、需要的網絡信息量大,不適用動態無線網絡(包括網絡動態和流量動態)。在分布式的編碼感知路由算法中,每個節點都獨立地根據自己保存的網絡狀態信息作出路由決定,因而具有較低的協議開銷以及復雜度,更適用于動態無線網絡。

(1)基于Markovian的路由度量

Wu[7]提出了基于Markovian的路由度量來進行編碼感知的路由。Markovian度量指出在某鏈路上發送報文的代價,可能會依賴于該報文的前一跳節點,因此能夠有效地衡量出使用網絡編碼的情況下某條路徑的路由代價。但是,Markovian度量的主要問題在于,它只能發現某條鏈路上是否存在編碼機會,而不能發現該鏈路上編碼機會的多少,因此可能無法找出編碼機會最多的路徑。

(2)分布式編碼感知路由協議

分布式編碼感知路由協議(DCAR)[8]能夠找出源和目的節點間的潛在路徑,并能找出這些路徑上的所有潛在網絡編碼機會而不僅是兩跳拓撲內的編碼機會。源節點首先發送路徑請求(RREQ)消息,RREQ消息所經過的所有節點都將其一跳鄰居記錄在RREQ消息中的“誰能監聽”節點列表中。目的節點接收到RREQ消息后,向源節點返回路徑回復(RREP)消息。中間節點接收到RREP消息后,根據“誰能監聽”信息檢查此流能否與現有經過該節點的流進行編碼。當RREP消息返回到源節點后,源節點根據RREP消息中包含的潛在編碼機會作出路由選擇,找出所有具有潛在網絡編碼機會的路徑。然而編碼機會最多的路徑不一定能夠帶來最好的性能,該路徑可能過長,或者已經嚴重擁塞。某些不具備編碼機會的路徑可能反而具有較高的吞吐量。DCAR綜合考慮了編碼機會,擁塞等因素,定義了新的編碼感知度量(CRM)用于衡量某條路徑上期望的傳輸次數。將CRM與路由發現過程相結合,DCAR能夠找出能夠有效提升網絡吞吐量的路由。

(3)速率匹配的編碼感知多路徑路由協議

當前的大多數的網絡編碼方案都假定參與編碼不同的流之間的速率是一致的,而沒有考慮速率不同的流之間的網絡編碼問題。文獻[9]提出了速率匹配的編碼感知多路徑路由協議(RCR)。該協議能夠將一個流分割成多個流以便于有效的實現流之間的速率匹配,從而有效地提升網絡編碼的效率。同時當前大多數無線網絡中的路由協議都選擇基于無線鏈路狀態的度量,但是對于網絡編碼來說,基于鏈路狀態的度量并不一定是最佳的選擇。因此,RCR定義了多個基于節點的路由度量,分別用于衡量某路徑的編碼機會的多少,路徑的匹配編碼速率以及該路徑的擁塞避免速率。

在路由發現階段,源節點向網絡中廣播RREQ消息,當RREQ經過網絡中的中間節點時,節點將該節點的路由度量記錄在RREQ消息中。目的節點收到多個RREQ消息后,分別計算出不同路徑的所需傳輸數目,流量匹配速率以及擁塞避免速率。目的節點根據這些度量選擇路徑,并對不同的路徑分配速率,并沿著選擇的路徑返回RREP消息。源節點接收到RREP消息后,根據不同路徑分配的速率在多個路徑對流進行傳輸。

(4)編碼感知多路徑路由協議

編碼感知多路徑路由協議(CAMP)[10]同樣利用多路徑以及分流來增大網絡中的編碼機會。CAMP協議提出了一種新的路徑轉換增益,用于衡量路由應該轉換至哪條路徑以帶來較多的增益。在路由發現階段,CAMP依據ETX信息,為源節點找出多個可用的路徑。每個路徑的中間節點都緩存多個可能的路由候選者,為將來的路徑轉換做好準備。在報文轉發的過程中,CAMP動態的將缺省路徑轉換至新的能夠最大化編碼增益以及路徑轉換增益的路徑上。CAMP的問題在于其所尋找的多路徑需要在一定范圍內互相臨近,以便于中間節點能夠轉換路徑,因此不能完全利用多路徑的多樣性。

(5)編碼感知機會路由協議

雖然上述協議都不同程度地實現了編碼感知的路由,但是,上述協議都基于傳統的最短路徑路由,每個節點的下一跳都是預先確定的,這對于信道并不可靠的無線網絡來說可能會導致報文的多次重傳。

機會路由作為新的研究熱點,已經被證明能夠有效地提高無線網絡的吞吐量。機會路由同樣利用了無線傳輸媒介的廣播特性,每個節點維護一個轉發節點集合作為可能的下一跳,具有最優路由的節點的成為實際的下一跳節點。機會路由大大降低了報文丟失和重傳的機率,同時利用那些離目的節點較近但是信道情況較差的無線鏈路,能夠有效地降低傳輸次數。

編碼感知機會路由(CORE)[11]協議有效的結合了流間網絡編碼與機會路由。在某個節點發出報文之前,節點首先選擇轉發集作為可能的下一跳。轉發集中的所有節點都獨立計算本次傳輸的編碼機會,并根據其編碼機會的多少來進行衡量其發送的優先級。每個節點維護一個定時器,編碼機會較多的節點定時器觸發較早。當定時器觸發時,節點進行傳輸。如果節點監聽到了該報文被其他節點傳輸,則取消定時器。CORE可以同時得到網絡編碼和機會路由對無線網絡所帶來的增益。試驗結果顯示,CORE可以有效提升網絡的吞吐量。

(6)MAC無關機會路由

MAC無關機會路由(MORE)[12]將流內隨機網絡編碼與機會路由相結合。當源節點發送數據時,將所要發送的原始數據分成批,例如把每K個包作為一批。源節點將每一批數據包做隨機線性編碼后,不停地廣播出去,每個分組攜帶其編碼向量。中間轉發節點只接受創新數據包(Innovative數據包),即:收到一個包后,首先判斷它與本地已經收到的屬于該批的數據包是否線性獨立,如果線性獨立則將新數據包存入緩存,否則丟棄該包。當收到屬于同一批次的K個Innovative數據包后,目的節點就可以恢復出原始K個數據包,并向源節點回送ACK包。源節點收到ACK后,進行下一批數據包的發送。試驗結果顯示,與ExOR相比,MORE可以大大提高分組成功投遞率。

(7)最優化多路徑網絡編碼協議

最優化多路徑網絡編碼協議(OMNC)[13]將線性隨機編碼,速率控制與機會路由協議相結合以增大網絡中的編碼增益。OMNC以基于優化的方式控制編碼報文在易丟失的無線環境中的傳輸。利用媒體訪問控制(MAC)協議的廣播特性,使得一次傳輸能夠被多個下游節點所監聽。利用隨機網絡編碼的特性,OMNC能夠保證單播傳輸的可靠性而不需要鏈路層的重傳機制。

與MORE協議相似,在OMNC中,端到端的傳輸是由編碼報文在多個機會的路徑上所完成的。然而與MORE不同,OMNC將每個節點的編碼以及廣播速率與其信道狀態相匹配,以有效的避免擁塞,更好利用路徑的多樣性,減少冗余報文的傳輸。只要網絡中的節點能夠進行線性編解碼操作,OMNC就能很好的提升易丟失無線網絡的吞吐量。

(8)區域聯合編碼與傳輸調度算法

傳統網絡編碼機制著眼于最大化單次傳輸內所包含的報文個數來最大化無線網絡的吞吐量。然而,這種從單個節點的角度來最大化網絡編碼增益的做法,實際上卻有可能損害整個網絡的編碼增益。如果每個節點能夠考慮到鄰居節點的編碼增益進行編碼傳輸的話,整個網絡的編碼增益有可能得到進一步提升。在區域聯合編碼與傳輸調度算法(PACE)[14]中,節點每次轉發都著眼于提升節點附近區域中的整體編碼增益,同時使用編碼感知的傳輸調度來保證編碼機會的實現。PACE使用區域編碼增益作為節點傳輸的優先級,以此為優先級來對傳輸進行調度,保證臨近節點的最佳傳輸順序以最大化區域的網絡編碼增益,同時有效的減輕碰撞的發生,有效的提升網絡性能。

2 結束語

本文綜述了已有編碼感知路由協議的基本思想和主要協議。已有工作顯示,網絡編碼感知的路由協議能夠顯著提高包括Ad Hoc網絡、無線傳感器網絡和無線Mesh網絡等在內的無線多跳網絡的性能。但作為一個無線網絡領域的新技術,無線網絡內的編碼感知路由領域還有很多問題需要進一步研究。

(1)新型路由度量

路由度量對路由協議的性能具有重要影響。已有編碼感知路由協議主要以編碼機會的多少、ETX、地理距離、擁塞程度等作為主要度量來設計編碼感知的路由協議。引入新的路由度量有可能提出更有效的編碼感知路由協議。

(2)跨層設計

現有的編碼感知路由協議主要著重于路由層的協議設計。除此之外,MAC層的接入,高丟失無線信道所帶來的重傳等也是影響網絡編碼性能的重要因素。綜合考慮上述因素以及應用的特點,進行編碼感知跨層研究,對無線網絡中的網絡編碼性能將起到較好的促進作用。結合編碼感知鏈路調度的網絡編碼感知路由能夠極大地提高網絡性能,值得進一步深入研究。

3 參考文獻

[1] ELIAS P, FEINSTEIN A, SHANNON C. A note on the maximum flow through a network[J]. IEEE Transactions on Information Theory, 1956,2(4): 117-119.

[2] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4):1204-1216.

[3] KATTI S, RAHUL H, HU W, et al. XORs in the air: Practical wireless network coding[C]// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep 11-15, 2006, Pisa, Italy. New York, NY,USA:ACM,2006:243-254.

[4] SENGUPTA S, RAYANCHU S, BANERJEE S. An analysis of wireless network coding for unicast sessions: The case for coding-aware routing[C]// Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM07), May 6-12,2007, Anchorage, AK,USA. Piscataway, NJ, USA:IEEE, 2007:1028-1036.

[5] NI B, SANTHAPURI N, ZHONG Z, et al. Routing with opportunistically coded exchanges in wireless mesh networks[C]//Proceedings of the 2nd IEEE Workshop on Wireless Mesh Networks (WiMesh'06),Sep 25,2006, Reston, VA, USA. Piscataway, NJ, USA:IEEE, 2006: 157-159.

[6] De COUTO D S J, AGUAYO D, BICKET J, et al. A high-throughput path metric for multi-hop wireless routing[C]// Proceedings of 9th Annual International Conference on Mobile Computing and Networking, Sep 14-19,2003,San Diego,CA,USA.New York, NY,USA:ACM, 2003:419-434.

[7] WU Y, DAS S M, CHANDRA R. Routing with a Markovian metric to promote local mixing[C]// Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM07),May 6-12,2007, Anchorage, AK,USA. Piscataway, NJ,USA:IEEE, 2007: 2381-2385.

[8] LE J, LUI J C S, CHIU D M. DCAR: Distributed coding-aware routing in wireless networks[C]// Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS08), Jun 17-20,2008, Beijing, China. Piscataway, NJ,USA:IEEE, 2008: 462-469.

[9] YAN Y, ZHAO Z, ZHANG B, et al. Rate-adaptive coding-aware multiple path routing for wireless mesh networks[C]//Proceedings of IEEE Global Telecommunications Conference (GLOBECOM'08),Nov 30-Dec 4,2008, New Orleans, LA,USA. Piscataway, NJ,USA: IEEE,2008: 543-547.

[10] HAN S, ZHONG Z, LI H, et al. Coding-aware multi-path routing in multi-hop wireless networks[C]// Proceedings of the 27th Performance, Computing, and Communications Conference(IPCCC08),Dec 7-9,2008, Austin,TX,USA.Los Alamitos, CA,USA:IEEE Computer Society, 2008:93-100.

[11] YAN Y, ZHANG B, MOUFLAH H T, et al. Practical coding-aware mechanism for opportunistic routing in wireless mesh networks[C]// Proceedings of IEEE International Conference on Communications(ICC08),May 19-23,2008, Beijing, China.Piscataway, NJ,USA:IEEE,2008: 2871-2876.

[12] CHACHULSKI S, JENNINGS M, KATTI S, et al. Trading structure for randomness in wireless opportunistic routing[C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 07), Aug 27-31, 2007, Kyoto, Japan. New York, NY,USA:ACM, 2007: 169-180.

[13] ZHANG X, LI B. Optimized multipath network coding in lossy wireless networks[C]// Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS08), Jun 17-20,2008, Beijing, China. Piscataway, NJ,USA:IEEE ,2008: 243-250.

[14] YAN Y, ZHAO Z, ZHANG B, et al. Mechanism for maximizing area-centric coding gains in wireless multihop networks[C]// Proceedings of IEEE International Conference on Communications (ICC09),Jun 14-18,2009, Dresden, Germany. Piscataway, NJ,USA: IEEE,2009.

收稿日期:2009-07-30

巖延,中科院計算技術研究所博士生,主要研究領域為無線傳感器網絡、無線網絡、網絡編碼。已發表學術論文8篇。

張寶賢,中科院研究生院泛在與傳感網研究中心教授、博士生導師,主要研究領域為無線傳感網、無線網絡。已主持國家重大專項、國家高技術研究發展計劃“863”、自然基金等課題10項,發表論文70余篇。

馬建,諾基亞(中國)研發中心首席科學家、博士,主要研究領域包括傳感器網絡、泛在網絡、4G核心網及協議和移動計算等。已發表150篇學術論文,擁有6項國際專利。