袁永瓊
(中國電子科技集團公司第二十研究所,西安 710068)
無線多跳網(wǎng)絡(luò)路由協(xié)議設(shè)計面臨巨大挑戰(zhàn),主要由以下幾個因素引起:(1)網(wǎng)絡(luò)帶寬資源有限;(2)信道衰落導致無線鏈路不可靠[1];(3)無線媒介是廣播共享信道,當多個數(shù)據(jù)鏈流并發(fā)傳輸可能導致信道存在嚴重的競爭和沖突。
傳統(tǒng)無線網(wǎng)絡(luò)路由協(xié)議的設(shè)計,通常沿襲有線網(wǎng)絡(luò)路由協(xié)議的設(shè)計思想,將無線鏈路抽象為點對點的有線鏈路后,尋找源和目的節(jié)點對之間以某種度量作為依據(jù)的最佳路徑,比如說跳數(shù)最短路徑、最小代價路徑或者高吞吐量路徑。這種抽象也忽略了無線傳輸獨特的廣播特性和空間多用戶分集增益,在有線網(wǎng)絡(luò)環(huán)境中能夠工作的很好的路由協(xié)議,對于無線有損信道不一定是最佳選擇。
近年來研究工作者提出了許多新興的技術(shù),如機會路由[2]-[5],網(wǎng)絡(luò)編碼[6]-[11],充分利用無線信道的廣播特性提高網(wǎng)絡(luò)的吞吐量。由于機會路由路徑的分集特性,將流間網(wǎng)絡(luò)編碼與動態(tài)選擇路徑的機會路由相結(jié)合,以流間網(wǎng)絡(luò)編碼感知的方式選擇機會轉(zhuǎn)發(fā)路徑,可有效地創(chuàng)造編碼機會,以提高鏈路帶寬利用率和網(wǎng)絡(luò)的吞吐量。論文正是基于該思想,提出一種基于流間網(wǎng)絡(luò)編碼的機會路由機制(ORNC,Opportunistic Routing with inter-flow Network Coding),并通過網(wǎng)絡(luò)仿真驗證了其有效性。
機會路由中的兩個關(guān)鍵問題是:如何選擇候選節(jié)點及其優(yōu)先級順序,以及如何協(xié)調(diào)避免重復分組的發(fā)送。機會路由ExOR協(xié)議[2]允許將所有靠近目的節(jié)點的節(jié)點作為候選轉(zhuǎn)發(fā)節(jié)點,通過復雜的協(xié)調(diào)調(diào)度策略來避免重復轉(zhuǎn)發(fā)。Bhorkar等人提出的d-AdaptOR[4]是一種分布式自適應(yīng)機會路由協(xié)議。在缺乏信道統(tǒng)計特性和網(wǎng)絡(luò)拓撲信息時,以期望的平均每個分組的報酬為度量標準,選擇到目的端的最優(yōu)機會路徑。ORCD[5]采用類似d-AdaptOR的路由策略,只是選擇最佳轉(zhuǎn)發(fā)節(jié)點的依據(jù)不同。ORCD結(jié)合最短路徑和背壓路由,提出了一種擁塞分集的機會路由策略。為了避免復雜的協(xié)調(diào)機制,作為ExOR的增強版,MORE[9]是一種獨立于MAC的機會路由協(xié)議。MORE在機會路由中應(yīng)用隨機線性網(wǎng)絡(luò)編碼,避免了由中間節(jié)點復雜地協(xié)調(diào)由哪一個節(jié)點繼續(xù)轉(zhuǎn)發(fā)分組。OMNC[10]將隨機線性編碼、速率控制、MAC廣播約束與機會路由協(xié)議相結(jié)合以提高網(wǎng)絡(luò)的吞吐量。針對 COPE[8]協(xié)議消極編碼的問題,Yan等人提出CORE[11]協(xié)議,將流間網(wǎng)絡(luò)編碼和機會路由相結(jié)合,在無線網(wǎng)絡(luò)中創(chuàng)造更多的編碼機會,提高網(wǎng)絡(luò)吞吐量。
在無線多跳網(wǎng)絡(luò)中聯(lián)合流間網(wǎng)絡(luò)編碼和機會路由,本文提出一種基于流間網(wǎng)絡(luò)編碼的機會路由(ORNC , Opportunistic Routing with inter-flow Network Coding)算法。在分組的轉(zhuǎn)發(fā)過程中,以流間網(wǎng)絡(luò)編碼感知的方式選擇下一跳機會轉(zhuǎn)發(fā)節(jié)點,積極創(chuàng)造網(wǎng)絡(luò)編碼機會,通過自定義機會轉(zhuǎn)發(fā)效能函數(shù)的計算結(jié)果來選擇每一跳的最佳轉(zhuǎn)發(fā)節(jié)點,降低分組轉(zhuǎn)發(fā)次數(shù),提高鏈路利用率。轉(zhuǎn)發(fā)效能函數(shù)考慮以下情況:當存在網(wǎng)絡(luò)編碼機會的時候,綜合評估網(wǎng)絡(luò)編碼機會和到目的節(jié)點的距離;當沒有網(wǎng)絡(luò)編碼機會時考慮背壓信息和最短路徑以平衡網(wǎng)絡(luò)負載,避免網(wǎng)絡(luò)擁塞。
圖1 ORNC的運行過程
在 ORNC機會路由協(xié)議設(shè)計中面臨的主要挑戰(zhàn)是如何選擇下一跳轉(zhuǎn)發(fā)節(jié)點和如何有效避免轉(zhuǎn)發(fā)重復分組。
ORNC的路由決策是根據(jù)分組的實時接收情況以及編碼機會逐跳選擇下一跳轉(zhuǎn)發(fā)節(jié)點。在避免轉(zhuǎn)發(fā)重復分組方面,與 d-AdaptOR[4]相似,ORNC通過控制分組的交互,選擇和通知下一跳節(jié)點,可以有效避免重復分組的轉(zhuǎn)發(fā)。ORNC是一種低復雜度,分布式實現(xiàn)的算法。ORNC的運行主要包含以下四個階段,具體如圖1所示。
在 ORNC算法中,下一跳候選轉(zhuǎn)發(fā)節(jié)點集選擇和最佳轉(zhuǎn)發(fā)節(jié)點選擇策略是兩個核心部分。在分別詳細介紹這兩部分之前,首先將本文用到的符號進行定義,如表1所示。
表1 ORNC算法-符號說明
ORNC以ETX度量轉(zhuǎn)發(fā)節(jié)點到目的節(jié)點的距離為依據(jù)選擇候選轉(zhuǎn)發(fā)節(jié)點。在ORNC中,節(jié)點r能夠被節(jié)點i選中作為流c的下一跳候選轉(zhuǎn)發(fā)節(jié)點集的成員,則節(jié)點r應(yīng)該滿足以下條件:節(jié)點r是i的鄰居節(jié)點且比節(jié)點i到達目的節(jié)點的距離更近,即r∈N(i)且 E TX (r,d)< E TX(i,d)。候選轉(zhuǎn)發(fā)節(jié)點集包含最短路徑上的節(jié)點。
當節(jié)點準備發(fā)送一個分組的時候,報頭中額外附加上候選轉(zhuǎn)發(fā)節(jié)點集中的節(jié)點,這些節(jié)點在控制包頭中的位置按路由度量的ETX值由小到大排列。
最佳轉(zhuǎn)發(fā)節(jié)點的選擇是 ORNC的一個關(guān)鍵問題。ORNC根據(jù)候選轉(zhuǎn)發(fā)節(jié)點的分組實時接收情況及該節(jié)點的機會轉(zhuǎn)發(fā)效能評估的反饋信息做出路由決策,逐跳選擇下一跳的最佳轉(zhuǎn)發(fā)節(jié)點。節(jié)點i為分組pi選擇下一跳的最佳轉(zhuǎn)發(fā)節(jié)點的過程包含兩步:(a)轉(zhuǎn)發(fā)效能評估。機會候選轉(zhuǎn)發(fā)節(jié)點集中的節(jié)點計算機會轉(zhuǎn)發(fā)效能并將信息附加在 ACK分組中發(fā)送給節(jié)點i;(b)最佳轉(zhuǎn)發(fā)節(jié)點選擇。節(jié)點i根據(jù)機會轉(zhuǎn)發(fā)效能的計算結(jié)果選擇取得最大轉(zhuǎn)發(fā)效能的節(jié)點繼續(xù)轉(zhuǎn)發(fā)分組。
(a)轉(zhuǎn)發(fā)效能評估
在 ORNC中,定義了轉(zhuǎn)發(fā)效能函數(shù)來評價節(jié)點的機會轉(zhuǎn)發(fā)效能。機會轉(zhuǎn)發(fā)效能函數(shù)綜合考慮網(wǎng)絡(luò)編碼機會和以ETX度量[1]的到目的節(jié)點的距離。下面給出編碼收益和機會轉(zhuǎn)發(fā)效能函數(shù)的定義。
下面詳細說明當一個分組候選集中的節(jié)點收到該分組時,如何計算轉(zhuǎn)發(fā)效能。
首先,簡要描述一下 ORNC的編碼條件。ORNC采用異或(XOR)[8]運算作為網(wǎng)絡(luò)編碼的實現(xiàn)方式。由于下一跳轉(zhuǎn)發(fā)節(jié)點有多個候選節(jié)點,ORNC的編碼條件是確保所有參與編碼的分組的下一跳候選節(jié)點集中,至少有一個節(jié)點可以通過解碼運算從編碼分組中得到所需的原始分組。具體如下:假設(shè)節(jié)點j的輸出隊列里有k(k>1)個屬于不同數(shù)據(jù)流的分組,用符號p1,p2,… ,pk表示,對于任何一個分組Pt,如果其候選節(jié)點集里至少有一個節(jié)點已經(jīng)獲得除Pt以外的k-1個分組,則節(jié)點j將這些分組進行編碼后得到分組。
按照上述編碼條件,節(jié)點j可以決定新收到的分組Pt是否能與隊列中的其它分組進行編碼。如何選擇哪些分組進行編碼是一個非常復雜的問題。例如,流1可以和流2編碼,流2可以和流3編碼,但是流1不能與流3編碼,問題是選擇哪兩個流的分組進行編碼可以獲得更好的編碼收益?論文旨在最大化網(wǎng)絡(luò)的鏈路利用率,找到可以獲得最大收益的能夠一起編碼的的分組可以歸納為一個最大clique 問題[12]-[13],是一個NP完全問題。這里,論文僅考慮當前收到的原始分組與緩存中其它分組進行編碼的情況。分兩種情況考慮:①分組Pt能夠與輸出隊列中的分組進行編碼,則sPt=1;②分組Pt不能與任何分組進行編碼,則sPt=0。下面闡述如何計算編碼收益。
論文采用NS2網(wǎng)絡(luò)仿真平臺評估ORNC的性能,并與COPE[8],DSDV[16]傳輸方案進行了比較。試驗中參數(shù)設(shè)置如下:900m*900m的矩形網(wǎng)絡(luò)環(huán)境,包含60個節(jié)點,MAC層采用IEEE 802.11 DCF,信道容量為1Mb/s。數(shù)據(jù)流設(shè)定為15個連接,并采用恒定比特速率業(yè)務(wù)流業(yè)務(wù) CBR,有效載荷為1000B。隨機選取每個CBR業(yè)務(wù)流的源和目的節(jié)點對,之后在單次仿真模擬運行過程中保持不變。
數(shù)據(jù)流以平均n秒為間隔產(chǎn)生數(shù)據(jù)分組,在前1分鐘內(nèi),數(shù)據(jù)流隨機開始。實驗評價的性能指標包括:
(1)網(wǎng)絡(luò)吞吐量:單位時間內(nèi)所有數(shù)據(jù)流的平均聚合吞吐量;
(2)編碼率:網(wǎng)絡(luò)傳輸?shù)木幋a分組的數(shù)量與總的發(fā)送分組的數(shù)量的比值。
圖2顯示了隨著分組到達平均間隔變化的性能仿真曲線。隨著網(wǎng)絡(luò)負載的增加,三種傳輸方案下的網(wǎng)絡(luò)都經(jīng)歷了從空閑到嚴重擁塞的過程。當網(wǎng)絡(luò)負載較低時,網(wǎng)絡(luò)流時間間隔大于等于0.5時,所有方案的性能表現(xiàn)相似,網(wǎng)絡(luò)吞吐量和分組送達率曲線幾乎重合。這種情況下網(wǎng)絡(luò)比較空閑,不必對分組采用網(wǎng)絡(luò)編碼即可傳輸,這樣可降低轉(zhuǎn)發(fā)的復雜度以及存儲開銷。隨著網(wǎng)絡(luò)流時間間隔的減小,網(wǎng)絡(luò)負載加重,DSDV的吞吐量逐漸下降,但是由于編碼機會的增多,ORNC和COPE的吞吐量卻呈上升趨勢,當流時間間隔減少至0.35時達到COPE的吞吐量峰值,相比之下ORNC的峰值是在0.3左右。此后隨著流繼續(xù)增加導致網(wǎng)絡(luò)擁塞,吞吐量反而有所減小,編碼率略有降低。整個過程在大多數(shù)情況下ORNC的性能優(yōu)于其他對比方案。在吞吐量方面,相對COPE,ORNC最高能提升17.4%。這是因為,由于流數(shù)量的增加,相比 COPE,ORNC結(jié)合機會轉(zhuǎn)發(fā)和網(wǎng)絡(luò)編碼能創(chuàng)造更多編碼機會,有效提升了吞吐量。但當網(wǎng)絡(luò)擁塞嚴重時,所有方案的性能都逐漸下降。
圖2 仿真性能結(jié)果
結(jié)合網(wǎng)絡(luò)編碼和機會路由的優(yōu)勢,本文提出一種無線多跳網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的機會路由(ORNC)算法。在ORNC中,以網(wǎng)絡(luò)編碼感知的方式選擇機會路徑。分組轉(zhuǎn)發(fā)過程中,根據(jù)分組的實時接收情況和機會轉(zhuǎn)發(fā)效用函數(shù)選擇下一跳最佳轉(zhuǎn)發(fā)節(jié)點。機會轉(zhuǎn)發(fā)效用函數(shù)綜合考慮了網(wǎng)絡(luò)編碼收益和到目的節(jié)點的距離。當存在網(wǎng)絡(luò)編碼機會時,可以有效減少期望的轉(zhuǎn)發(fā)次數(shù),提高網(wǎng)絡(luò)吞吐量。仿真結(jié)果驗證了ORNC能夠有效提高網(wǎng)絡(luò)的吞吐量。
[1]D.D.Couto,D.Aguayo,J.Bicket,and R.Morris.A High-Throughput Path Metric for Multi-Hop Wireless Routing[C].in Proc.ACM MobiCom,2003:134 - 146.
[2]S.Biswas and R.Morris.ExOR:Opportunistic Multi-hop Routing for Wireless Networks[J].ACM SIGCOMM Computer Communication Review,2005,35(4):133-144.
[3]D.Koutsonikolas,C.-C.Wang,and Y.C.Hu.CCACK:efficient network coding based opportunistic routing through cumulative coded acknowledgments[C].In Proc.of IEEE INFOCOM,2010:2919 - 2927.
[4]Bhorkar,A.A.,M.Naghshvar,et al.Adaptive Opportunistic Routing for Wireless Ad Hoc Networks [J].IEEE/ACM Transactions on Networking,2011,20(1):243-256.
[5]Mohammad Naghshvar and Tara Javidi.Opportunistic Routing with Congestion Diversity in Wireless Multi-hop Networks [J].IEEE INFOCOM,2010:496 - 500.
[6]Ahlswede R,Cai N,Li S R,et al.Network information flow [J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
[7]C.Fragouli,J-Y Le Boudec,and J.Widmer.Network coding:an instant primer[J].ACM SIGCOMM Computer Communication Review,2006,36(1):63-68.
[8]Katti S,Rahul H,Hu W,et al.Xors in the air:Practical Wireless Network Coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.
[9]S.Chachulski,M.Jennings,S.Katti,D.Katabi.Trading Structure for Randomness in Wireless Opportunistic Routing[C].in Proc.ACM SIGCOMM’07,2007:169-180.
[10]X.Zhang,B.Li.Optimized multipath network coding in lossy wireless networks [J].IEEE Journal on Selected Areas in Communications,2009,27(5):622-634.
[11]Yan Y,Zhang BX,Zheng J,Ma J.CORE:A coding-aware opportunistic routing mechanism for wireless mesh networks [J].IEEE Wireless Communications,2010,17(3):96-103.
[12]Le J,Lui J C S,and Chiu D.DCAR:Distributed Coding-Aware Routing in Wireless Networks [J].IEEE Transactions on,Mobile Computing,2010,9(4):596-608.
[13]R.M.Karp.Reducibility among Combinatorial Problems[J].Complexity of Computer Computations,,1972:85-103.
[14]M.Neely and R.Urgaonkar.Opportunism,backpressure,and stochastic optimization with the wireless broadcast advantage[C].IEEE SSC,Jan 2008:2152-2158
[15]S.Moeller ,A.Sridharan ,B.Krishnamachari and O.Gnawali.Routing without routes:The backpressure collection protocol[C].In proceedings of 9th ACM/IEEE international conference of Information Processing in Sensor Networks,2010:279 - 290.
[16]C.E.Perkins and P.Bhagwat.Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers [J].ACM SIGCOM Computer Communication Review,1994,24(4):234-244.