劉永廣, 張 劍, 陳瑞昭, 姚若河

(1.中國電子科技集團(tuán)第七研究所，廣東廣州 510310； 2.華南理工大學(xué)電子與信息學(xué)院，廣東廣州 510641； 3.廣東輕工職業(yè)技術(shù)學(xué)院，廣東廣州 510300)

一種基于網(wǎng)絡(luò)編碼的Ad Hoc網(wǎng)絡(luò)多路徑源選路由算法

劉永廣1,2,3, 張 劍1, 陳瑞昭3, 姚若河2

(1.中國電子科技集團(tuán)第七研究所，廣東廣州 510310； 2.華南理工大學(xué)電子與信息學(xué)院，廣東廣州 510641； 3.廣東輕工職業(yè)技術(shù)學(xué)院，廣東廣州 510300)

根據(jù)Ad Hoc網(wǎng)絡(luò)的特性，提出了一個基于網(wǎng)絡(luò)編碼的多路徑源選路由算法. 算法借鑒了COPE的思想，實現(xiàn)上通過在中間節(jié)點緩存短路徑，對具有編碼機(jī)會的中間節(jié)點進(jìn)行標(biāo)注，從而獲得具有最大編碼機(jī)會的多條路徑. 由于網(wǎng)絡(luò)編碼可以減少數(shù)據(jù)傳輸?shù)拇螖?shù)，因此可以有效地提高信道的利用率. NS2環(huán)境下的仿真表明，新算法能夠有效地平衡網(wǎng)絡(luò)負(fù)載，提高網(wǎng)絡(luò)的吞吐量.

網(wǎng)絡(luò)編碼； 多路徑； 路由

移動Ad Hoc網(wǎng)絡(luò)在軍事、緊急救援和移動辦公等領(lǐng)域具有廣泛的應(yīng)用前景，由于網(wǎng)絡(luò)節(jié)點的移動性，導(dǎo)致整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨之動態(tài)變化，因而Ad Hoc網(wǎng)絡(luò)路由是一個關(guān)鍵問題. 現(xiàn)行的路由算法大多是按需單路徑路由協(xié)議，如DSR[1]、AODV[2]等. 這些算法基本上都采用單路徑方式傳送數(shù)據(jù)，控制包開銷和網(wǎng)絡(luò)延遲較大，當(dāng)負(fù)載較大時，將面臨網(wǎng)絡(luò)擁塞的問題.

針對以上協(xié)議的問題，提出了一些多路徑路由算法. 文獻(xiàn)[3]提出維護(hù)備用路徑，當(dāng)主路徑失敗時利用備份路徑來傳輸，并不是真正意義上的并行多路徑傳輸. 文獻(xiàn)[4]的多路徑源路由協(xié)議MSR提出了一個基于啟發(fā)的加權(quán)輪詢多路徑調(diào)度機(jī)制來分布負(fù)載，但沒有提供其性能分析模型. 分裂多路徑協(xié)議SMR[5]算法對DSR協(xié)議進(jìn)行了改進(jìn)，著重建立和維護(hù)最大數(shù)目的多條不相交路徑，該算法能有效地提高網(wǎng)絡(luò)的吞吐量，但是由于選擇幾條固定的路徑，容易使其中的某些路徑成為交集而變?yōu)槠款i鏈路. 文獻(xiàn)[6]-[10]均采用了文獻(xiàn)[5]的思路，所不同的只是不相交路徑的發(fā)現(xiàn)算法和分流算法. 比如，文獻(xiàn)[6]提出了一種多樣性的注入方法來發(fā)現(xiàn)非交叉路徑， 而文獻(xiàn)[7]通過改進(jìn)的最短路徑算法找到幾條源到目的端的鏈路不相交最短路徑，文獻(xiàn)[10]則通過計算網(wǎng)路最大流來計算多條節(jié)點不相交路徑.

以上提出的協(xié)議和算法各有優(yōu)缺點，這些算法都需要研究路由的發(fā)現(xiàn)機(jī)制、數(shù)據(jù)的多路徑發(fā)送方法以及提取高效的路徑集等問題. 而本文拋棄了以前的思路，在多路徑傳輸上采用了網(wǎng)絡(luò)編碼技術(shù)，優(yōu)先考慮網(wǎng)絡(luò)編碼機(jī)會較多的路徑，減少數(shù)據(jù)傳送的次數(shù)，達(dá)到了節(jié)省網(wǎng)絡(luò)帶寬、提高網(wǎng)絡(luò)性能的目的.

1 網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼理論最早由AHLSWEDE等人[11]開始研究，他們提出，通過使用網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)的組播能力可以達(dá)到組播樹的最大流最小割流量，而這種網(wǎng)絡(luò)吞吐量是常規(guī)路由無法達(dá)到的. KATTI 等人[12]成功地把網(wǎng)絡(luò)編碼思想引入到無線多跳單播網(wǎng)絡(luò)中來，并提出一個應(yīng)用于實際系統(tǒng)的網(wǎng)絡(luò)編碼算法COPE，該算法利用無線網(wǎng)絡(luò)中單個節(jié)點發(fā)送數(shù)據(jù)時能夠被所有鄰居節(jié)點感知的特點，在兩跳范圍內(nèi)進(jìn)行網(wǎng)絡(luò)編碼，達(dá)到了提高系統(tǒng)吞吐量的目的. 一個典型的應(yīng)用如圖1所示，在該圖中節(jié)點1通過節(jié)點2向節(jié)點3傳送數(shù)據(jù)x1，而節(jié)點3通過節(jié)點2向節(jié)點1傳送數(shù)據(jù)x2，節(jié)點2在沒有采用網(wǎng)絡(luò)編碼的情況下需要分別向節(jié)點1和節(jié)點2傳送x2和x1，總共需要傳送2次，但是，如果在節(jié)點2處對x1和x2進(jìn)行了網(wǎng)絡(luò)編碼，也就是把兩組數(shù)據(jù)做異或運算并廣播出去，則只需傳送一次數(shù)據(jù)，節(jié)點1和節(jié)點2接收到數(shù)據(jù)后分別和本節(jié)點緩存的x1和x2異或，則可得到各自需要的數(shù)據(jù)x2和x1.

圖1 無線網(wǎng)絡(luò)編碼Fig.1 Wireless network coding

本文提出的基于網(wǎng)絡(luò)編碼的多路徑源選路由(MSRBNC)算法就是基于以上無線網(wǎng)絡(luò)編碼思想，從源端找k條到目的端具有最大編碼機(jī)會的路徑，并分別在這些路徑上進(jìn)行傳輸.

2 基于網(wǎng)絡(luò)編碼的多路徑源選路由算法

根據(jù)以上的結(jié)論，設(shè)計了一種多路徑源選路由算法，該算法在源和目的節(jié)點的多條路徑上進(jìn)行數(shù)據(jù)傳輸，路徑選擇遵循編碼機(jī)會多的路徑優(yōu)先選擇的原則. 以下是該算法的主要過程描述.

2.1路由發(fā)現(xiàn)

當(dāng)源節(jié)點需要選擇到達(dá)目的節(jié)點的路由時，和DSR協(xié)議一樣，由源節(jié)點發(fā)起路由請求(ROUTE_REQUEST)廣播報文. 該報文中包括一個唯一標(biāo)識源節(jié)點的ID號和路由請求序列號. 在本算法中，為了讓源端獲得多條路徑，采用了文獻(xiàn)[5]中間節(jié)點處理路由請求的方法，具體處理過程如圖2所示.

當(dāng)目的節(jié)點收到一個路由請求報文時，就要回復(fù)一個路由應(yīng)答(ROUTE_REPLY)報文，由于在路由發(fā)現(xiàn)過程中存在多個到達(dá)的請求報文，所以對同一個源請求可能發(fā)送多個ROUTE_REPLY報文. 考慮到路由信息的開銷，在協(xié)議中規(guī)定對同一源節(jié)點的同一請求，回復(fù)報文數(shù)量不多于N條. 如果回復(fù)數(shù)目已經(jīng)達(dá)到N條，則再到達(dá)的路由請求報文就會被丟棄.

ROUTE_REPLY報文是實現(xiàn)網(wǎng)絡(luò)編碼感知的關(guān)鍵，ROUTE_REPLY報文中增加一個稱為“編碼機(jī)會”的字段CO，在每個節(jié)點中都緩存一個類似圖1所示的短路徑組，記錄可能會經(jīng)過該節(jié)點和其鄰居節(jié)點的流，中間節(jié)點收到ROUTE_REPLY報文時的處理過程如圖3所示. 源節(jié)點收到一個ROUTE_REPLY報文后，如果緩存中有等待要發(fā)送的數(shù)據(jù)，則立即發(fā)送緩存中的數(shù)據(jù).

2.2路由和短路徑維護(hù)

對于單條路徑的維護(hù)，如果一個節(jié)點不能夠成功地把數(shù)據(jù)轉(zhuǎn)發(fā)給下一跳,那么該節(jié)點就會認(rèn)為該條路徑在此處發(fā)生了斷鏈，該節(jié)點就會產(chǎn)生一個路由錯誤 (ROUTE_ERROR)報文， ROUTE_ERROR報文經(jīng)過的中間節(jié)點就會從短路徑緩存中找到該報文中含有的短路徑，并從緩存中刪除. 源節(jié)點收到該路由錯誤報文后，會從路由緩存中刪掉所有使用斷鏈鏈路的路徑. 此外，考慮到短路徑其實也是一種鄰居關(guān)系，如果節(jié)點在移動過程中鄰居關(guān)系發(fā)生了變化，比如一個節(jié)點的某個鄰居消失了，則也要查找短路徑緩存中是否有和該鄰居有關(guān)的短路徑存在，如果存在，則從緩存中刪除該條短路徑.

2.3路徑選擇和數(shù)據(jù)傳輸

當(dāng)有數(shù)據(jù)要發(fā)送到目的節(jié)點時，首先查找路由緩存尋找到達(dá)目的節(jié)點的路由，如果沒有到目的節(jié)點的路由，則啟動2.1節(jié)中的路由發(fā)現(xiàn)過程. 如果路由存在，算法從路由緩存中的N條路徑中找到k條CO最大的路徑來傳送數(shù)據(jù). 算法采用了每包分流的方法，數(shù)據(jù)到達(dá)目的節(jié)點后再重組遞交. 中間節(jié)點收到數(shù)據(jù)后，如果該節(jié)點在報文中被標(biāo)注為具有編碼機(jī)會，則報文在該節(jié)點中緩存t時間，如果在這t時間內(nèi)有機(jī)會編碼，則編碼后發(fā)送，否則直接發(fā)送. 如果該節(jié)點沒有被標(biāo)注為具有編碼機(jī)會，則收到數(shù)據(jù)后直接轉(zhuǎn)發(fā).

圖2 中間節(jié)點收到ROUTE_REQUEST報文的處理過程Fig.2 Process of receiving ROUTE_REQUEST packet at media node

圖3 中間節(jié)點收到ROUTE_REPLY報文的處理過程Fig.3 Process of receiving ROUTE_REPLY packet at media node

3 仿真和性能分析

3.1仿真環(huán)境和算法參數(shù)

這一部分將通過仿真對算法的性能和參數(shù)進(jìn)行分析. 所有的仿真都在NS-2.31仿真環(huán)境下進(jìn)行，每個節(jié)點的傳輸半徑約250 m，Mac層使用IEEE 802.11 DCF，信道帶寬2 Mbps,節(jié)點移動方式采用Random Waypoint模型. 目的節(jié)點回復(fù)最大路由個數(shù)N=6，源節(jié)點選擇傳輸路徑個數(shù)k=2，有編碼機(jī)會的中間節(jié)點等待編碼時間t=2 ms.

3.2性能評估

在性能評估方面，通過和單路徑源選路由算法DSR[1]、多路徑無編碼源選路由算法SMR-1[5]進(jìn)行比較來考察算法的性能. 采用的仿真場景如表1所示，仿真中節(jié)點數(shù)36個，暫停1 s，每個場景產(chǎn)生18個CBR流，發(fā)送速率每個流每秒1個報文，報文大小512個字節(jié).

表1 性能仿真場景

圖4是3個算法在端到端吞吐量上的比較，由圖可以看出，在節(jié)點處于靜止或者半靜止?fàn)顟B(tài)下(場景0)，3個算法都能獲得很大的吞吐量，其中MSRBNC的吞吐量最大，SMR最小，但是非常接近. 在這種低速或者半靜止網(wǎng)絡(luò)中，由于節(jié)點之間的位置相對固定，路由緩存中的路徑始終處于有效狀態(tài)，大大減少了路由請求報文和路由回復(fù)報文的數(shù)量. 在這種情況下，網(wǎng)絡(luò)的主要額外開銷是數(shù)據(jù)報文的報頭開銷，DSR協(xié)議流狀態(tài)(Flow State)的采用，使得數(shù)據(jù)報頭開銷大幅度減小，有效數(shù)據(jù)吞吐量增加. 而MSRBNC由于要在有編碼機(jī)會的節(jié)點處延遲等待編碼，其延遲最大.

隨著節(jié)點移動性的增加，DSR協(xié)議由于僅保留一條路徑，路由和流路徑的重新建立使數(shù)據(jù)在源端緩存時間加長，所以吞吐量急劇下降，且圖5中的延遲增長很快，最后達(dá)到17 s左右，基本上是SMR和MSRBNC的兩倍多. 相反，2個多路徑算法由于同時采用多條路徑傳輸，所以控制報文導(dǎo)致的額外開銷要小得多. 本文的MSRBNC算法由于進(jìn)行了網(wǎng)絡(luò)編碼，節(jié)省了傳輸次數(shù)，從而節(jié)省了帶寬，總體端到端吞吐量最大. 另外，場景4在移動速度比較高的情況下MSRBNC存儲的短路徑很容易失效，編碼機(jī)會就比較少，沒有編碼機(jī)會的MSRBNC算法就退化為SMR算法，只是由于中間節(jié)點的編碼等待導(dǎo)致延遲增大.

圖4 不同算法端到端吞吐量的比較

Fig.4 Comparison of end-to-end throughput between different algorithms

圖5 不同算法端到端平均延遲的比較

Fig.5 Comparison of end-to-end delay between different algorithms

在場景2下對每個節(jié)點轉(zhuǎn)發(fā)的報文數(shù)量(不包括控制報文)進(jìn)行了統(tǒng)計，數(shù)據(jù)的統(tǒng)計結(jié)果如表2所示. 由表2可以看到，DSR協(xié)議在該場景下轉(zhuǎn)發(fā)的數(shù)據(jù)報文數(shù)量最大，但端到端吞吐量卻不大. 在負(fù)載均衡方面，本文算法標(biāo)準(zhǔn)差最小、均衡性最好,提高了網(wǎng)絡(luò)資源的利用率.

表2 轉(zhuǎn)發(fā)數(shù)據(jù)報文數(shù)量統(tǒng)計

4 結(jié)論

本文提出了一種基于網(wǎng)絡(luò)編碼的多路徑源選路由算法，算法利用了中間節(jié)點的編碼機(jī)會，達(dá)到了節(jié)約網(wǎng)絡(luò)資源，提高吞吐量的目的. 如何評估編碼帶來的延遲和編碼帶來的轉(zhuǎn)發(fā)次數(shù)減少增益之間的關(guān)系，并從理論和實踐上對路徑的選擇做出指導(dǎo)，是進(jìn)一步需要研究的方向.

[1] JOHNSON D, MALTZ D A. The Dynamic Source Routing Protocol (DSR) for mobile Ad Hoc networks for IPv4[EB/OL]. IETF mobile Ad Hoc Networks Working Group, 2007(4):1-107.[2009-10-08]. http:∥www.ietf.org/rfc/rfc4728.txt.

[2] PERKINS C E, ROYER E M. Ad Hoc On-Demand Distance Vector (AODV) routing [EB/OL].IETF mobile Ad Hoc Networks Working Group,2003(7):1-37.[2009-10-08]. http:∥www.ietf.org/rfc/rfc3561.txt.

[3] NASIPURI A, DAS S R. On-Demand multi-path routing for mobile Ad Hoc networks[C]∥IEEE ICCCN’99. Boston, USA, 1999: 64-70.

[4] WANG L, ZHANG L F, SHU Y T, et al. Multipath source routing in wireless Ad Hoc networks [C]∥Canadian Conf On Electrical and Computer Engineering. Edmonton, Canada, 2000:479-483.

[5] LEE S J, GERLA M. Split multipath routing with maximally disjoint paths in Ad Hoc networks[C]∥IEEE ICC 2001. Helsinki, Finland, 2001:3201-3205.

[6] PEARLMAN M R, HAAS Z J, SHOLANDER P, et al. On the impact of alternate path routing for load balancing in mobile Ad Hoc networks[C]∥ACM MobilHoc, 2000. Chicago,USA, 2000:3-10.

[7] SOHN S, MARK B L, BRASSIL J T. Congestion-triggered multipath routing based on shortest path information[C]∥IEEE Int Conference on Computer Communications and Networks (ICCCN). Arlington, USA， 2006:191-196.

[8] BANNER R, ORDA A. Multipath routing algorithms for congestion minimization[J]. IEEE/ACM Transactions on Networking, 2007,15(2): 413-424.

[9] LIU M, XU Z Y, YANG J L, et al. Collision-Constrained minimum energy node-disjoint multipath routing in Ad Hoc networks[C]∥Wireless Communications, Networking and Mobile Computing (WiCom 2006). WuHan, China, 2006: 1-5.

[10] 陳躍泉,郭曉峰,曾慶凱,等.AMR:一個基于網(wǎng)絡(luò)最大流的Ad-Hoc多路徑路由算法[J].電子學(xué)報,2004,32(8):1297-1301.

CHEN Yuequan, GUO Xiaofeng, ZENG Qingkai, et al. AMR: A multipath routing algorithm based on maximum flow in Ad-Hoc networks [J].Acta Electronic Sinica,2004, 32(8):1297-1301.

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

[12] KATTI S, RAHUL H, KATABI D, et al. XORs in the Air: Practical Wireless Network Coding[C]∥ACM Sigcomm 2006. Pisa, Italy, 2006:243-254.

Keywords： network coding; multi-path; routing

【責(zé)任編輯 莊曉瓊】

AMULTI-PATHSOURCEROUTINGALGORITHMFORAdHocNETWORKSBASEDONNETWORKCODING

LIU Yongguang1,2,3， ZHANG Jian1， CHEN Ruizhao3， YAO Ruohe2

(1. NO.7 Research Institute, China Electronics Technology Group Corporation, Guangzhou 510310, China;2. Institute of Electronics & Telecommunications, South China University of Technology, Guangzhou 510641, China;3. Guangdong Industry Technical College, Guangzhou 510300, China)

According to the characters of Ad Hoc networks, a multi-path source routing algorithm based on network coding is presented. The algorithm refers the idea of COPE. In realization, the multiple paths having maximum coding opportunity are found by caching short paths in medium nodes and labeling the medium nodes which have coding opportunity. Because network coding reduces data’s transmission time, the algorithm can improve channel utilization effectively. Simulations under NS2 environment show that the new algorithm has better performance in balancing the network load and improving network throughput.

2010-01-25

劉永廣(1972—)，男，河北石家莊人，博士，廣東輕工職業(yè)技術(shù)學(xué)院高級工程師，主要研究方向：信息網(wǎng)絡(luò)理論與技術(shù)、路由算法及優(yōu)化等,Email: Liu.yongguang@gmail.com.

1000-5463(2010)03-0042-05

TP393

A