基于網(wǎng)絡(luò)編碼的無線路由技術(shù)研究進展

摘 要：網(wǎng)絡(luò)編碼是近年來通信領(lǐng)域所取得的重大進展之一，其核心思想是網(wǎng)絡(luò)節(jié)點對于接收的分組不是采取的傳統(tǒng)的存儲-轉(zhuǎn)發(fā)的簡單路由方式，而是存儲-編碼處理-轉(zhuǎn)發(fā)的方式。網(wǎng)絡(luò)編碼已被證明是改善無線網(wǎng)絡(luò)性能特別是吞吐量性能方面的下一代關(guān)鍵技術(shù)之一，特別適合戰(zhàn)場環(huán)境下廣播和組播信息的高效傳輸。本文綜述了近年來基于網(wǎng)絡(luò)編碼的無線路由技術(shù)的相關(guān)研究進展，分析了現(xiàn)有研究的局限性與不足，并對下一步研究方向進行了展望。

關(guān)鍵詞：無線網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；吞吐量

A Survey of Network Coding in Wireless

Networks Routing Protocols on Throughput Gains

HUANG Qingshan1 YANG Linhai1 QU Yuben2 DONG Chao2（1.Unit 75310，PLA，Wuhan 430073，China；

2.Department of Telecommunications Engineering ICE，PLAUST，Nanjing 211107，China）

Abstract：The Network Coding is one of the most important progress in recently years in field of communications. The core idea of Network Coding is that every node in a network doesn't function as a switch which just forwards the packets after it has received several packets， but it has the ability to code packets before forwarding. The Network Coding has been proved as one of the key technologies to improve the performance of wireless networks especially for the transmission of broadcast or multicast information in tactical environment..This paper focuses on latest research results of network coding which combined with network layer in wireless networks to increase throughput gains.In conclusion，the shortages of existing researches are pointed out，and some suggestions for future research work are proposed.

Key words：wireless networks；network coding；throughput

近年來，網(wǎng)絡(luò)編碼被認為是能極大提升網(wǎng)絡(luò)性能特別是網(wǎng)絡(luò)吞吐量的很重要的一種手段。相比有線網(wǎng)絡(luò)，無線網(wǎng)絡(luò)的鏈路廣播特性和鏈路的不確定性將使得網(wǎng)絡(luò)中存在大量的冗余分組，在應(yīng)用傳統(tǒng)路由方式的無線網(wǎng)絡(luò)協(xié)議下這些分組是直接丟棄的，這無疑浪費了有限的無線信道資源，而采用網(wǎng)絡(luò)編碼的方式后，節(jié)點可以利用這些冗余的分組進行編碼或者解碼，從而獲得自己所需要的信息，網(wǎng)絡(luò)編碼的方式合理利用了無線廣播信道所帶來的冗余分組，從改善無線網(wǎng)絡(luò)的性能這方面來說無線網(wǎng)絡(luò)更適合應(yīng)用網(wǎng)絡(luò)編碼。無線網(wǎng)絡(luò)節(jié)點通過對接收到的數(shù)據(jù)分組進行編碼處理再轉(zhuǎn)發(fā)，使得單次傳播的信息量增加，進一步提高了無線鏈路的容量，也提升了網(wǎng)絡(luò)吞吐量。在無線網(wǎng)絡(luò)中傳統(tǒng)路由技術(shù)，跨層設(shè)計等無法解決的問題在應(yīng)用網(wǎng)絡(luò)編碼后得到較好解決，網(wǎng)絡(luò)的吞吐量尤其是組播的吞吐量得到極大提升[1，2，3，4]。尤其是在戰(zhàn)場通信領(lǐng)域，由于存在大量戰(zhàn)場廣播和組播信息（如態(tài)勢共享，命令通告等），從直觀上完全可以借助網(wǎng)絡(luò)編碼技術(shù)大幅度提高這些信息的傳輸效率，從而給現(xiàn)有戰(zhàn)場通信網(wǎng)絡(luò)設(shè)計帶來革命性的變化。因此網(wǎng)絡(luò)編碼在被提出之后就引起了國內(nèi)外廣泛的關(guān)注，成為了當(dāng)前相關(guān)領(lǐng)域的研究熱點。涌現(xiàn)出一大批研究成果。

網(wǎng)絡(luò)編碼從自提出伊始就跟網(wǎng)絡(luò)層尤其是路由技術(shù)緊緊的結(jié)合在一起，傳統(tǒng)路由方式其實就是網(wǎng)絡(luò)編碼的一種特例。按照參與編碼的數(shù)據(jù)分組是否屬于同一個網(wǎng)絡(luò)流，大體可以將網(wǎng)絡(luò)編碼分為流內(nèi)網(wǎng)絡(luò)編碼，流間網(wǎng)絡(luò)編碼兩大類。相應(yīng)也分別有基于流內(nèi)網(wǎng)絡(luò)編碼的路由技術(shù)和基于流間編碼的路由技術(shù)。我們將分別在第2、第3節(jié)中總結(jié)介紹相關(guān)的研究進展。

本文較全面地綜述了近年來網(wǎng)絡(luò)編碼與無線路由技術(shù)相結(jié)合取得的一系列研究成果，分析了現(xiàn)有研究的局限性與不足之處，并對下一步可能的研究方向作了展望。

1 基于流內(nèi)網(wǎng)絡(luò)編碼的路由技術(shù)研究

1.1 流內(nèi)網(wǎng)絡(luò)編碼原理研究

網(wǎng)絡(luò)編碼提出的初衷是為使多播傳輸達到由最大流最小割定理[5]確定的最大理論傳輸容量，從而能取得較路由多播更好的網(wǎng)絡(luò)吞吐量。Koetter等人[6]研究了建立在路由之上的網(wǎng)絡(luò)編碼代數(shù)結(jié)構(gòu)，并首先建立了線性網(wǎng)絡(luò)編碼問題的代數(shù)理論框架，給出了一種具有指數(shù)復(fù)雜度的編碼構(gòu)造算法。隨后Jaggi等人[7]將構(gòu)造線性網(wǎng)絡(luò)編碼的算法復(fù)雜度降低到了多項式時間復(fù)雜度。文獻[6]開啟了用代數(shù)分析研究線性網(wǎng)絡(luò)編碼之風(fēng)，應(yīng)用比較成熟的圖論、矩陣分析等理論去分析網(wǎng)絡(luò)編碼對網(wǎng)絡(luò)的性能改善。但是以上的編碼方案均是集中式的，需要完全知道全網(wǎng)拓撲信息，而在實際網(wǎng)絡(luò)環(huán)境中，特別是無線網(wǎng)絡(luò)的網(wǎng)絡(luò)拓撲會經(jīng)常動態(tài)性變化，這樣導(dǎo)致應(yīng)用集中式網(wǎng)絡(luò)編碼帶來的吞吐量增益可能還不如直接采用傳統(tǒng)路由方式。于是Ho等人[8]提出了一種完全分布式的，編碼系數(shù)隨機的線性編碼構(gòu)造方法，即本地節(jié)點的輸出信息是輸入信息和本地產(chǎn)生信息的線性組合，并證明了當(dāng)有限域足夠大時能任意趨近最大組播速率，具有很強的實用性。Ho等人[3，9]還在此基礎(chǔ)上應(yīng)用矩陣行列式分析方法研究了這種分布式的隨機系數(shù)線性編碼的存在性，給出了一個編碼成功概率的下界，并指出相關(guān)的編碼失敗概率的上界隨著有限域的增大呈指數(shù)級下降。這些理論上的研究成果尤其是隨機線性網(wǎng)絡(luò)編碼的理論結(jié)果給網(wǎng)絡(luò)編碼在實際網(wǎng)絡(luò)場景的應(yīng)用奠定了堅實的理論基礎(chǔ)。

1.2 基于流內(nèi)網(wǎng)絡(luò)編碼的路由協(xié)議研究

S.Biswas等人在[10]中提出了機會路由的概念，機會路由有效地利用了無線網(wǎng)絡(luò)物理層媒介廣播特性，在機會路由協(xié)議中，在某個發(fā)送節(jié)點傳送范圍內(nèi)的所有節(jié)點都能收到它發(fā)送的數(shù)據(jù)包，然后所有收到數(shù)據(jù)包的節(jié)點能夠協(xié)助發(fā)送節(jié)點將數(shù)據(jù)包發(fā)送到目的節(jié)點。機會路由協(xié)議需要保持兩方面的平衡：一方面，在發(fā)送節(jié)點傳輸范圍內(nèi)的所有節(jié)點可能都會收到它發(fā)送的數(shù)據(jù)包的多個復(fù)制品，這就需要避免轉(zhuǎn)發(fā)過多重復(fù)的包，因此參加轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點不可過多；另一方面，如果轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點太少，可能數(shù)據(jù)包沒法最終傳送到目的節(jié)點。為此，文獻[10]設(shè)計了一個數(shù)據(jù)包調(diào)度算法，通過大量的控制消息來達到平衡這兩方面的目的，但是本算法過于復(fù)雜，在實際網(wǎng)絡(luò)環(huán)境中可用性不大。Park等人于2006年提出了基于網(wǎng)絡(luò)編碼的Ad Hoc網(wǎng)絡(luò)組播協(xié)議CodeCast[11]，它采用的基本思想是源節(jié)點將要發(fā)送的數(shù)據(jù)分組隨機線性組合后發(fā)送出去而不是發(fā)送原始數(shù)據(jù)分組本身，因此有效避免了同一數(shù)據(jù)分組的重復(fù)發(fā)送問題。CodeCast充分利用了無線網(wǎng)絡(luò)的路徑多樣性，相比傳統(tǒng)的組播方式可以獲得更好性能。實驗結(jié)果表明，CodeCast的數(shù)據(jù)分組交付率接近100%，開銷比傳統(tǒng)的組播方式減少了50%。CodeCast的不足是其轉(zhuǎn)發(fā)策略中缺乏對網(wǎng)絡(luò)的擁塞狀態(tài)以及可用資源的分配考慮；此外，網(wǎng)絡(luò)編碼的引入使得其端到端時延明顯高于傳統(tǒng)的組播方式，不適用于對時延敏感，周期較長的周期性短報文業(yè)務(wù)，如戰(zhàn)場態(tài)勢感知業(yè)務(wù)。在機會路由的思想上，Chachulski等人于2007年提出了MORE[12]，將隨機線性網(wǎng)絡(luò)編碼應(yīng)用在機會路由中，大大降低了[10]中數(shù)據(jù)包調(diào)度算法的復(fù)雜性。MORE的主要思想是節(jié)點對收到的多個數(shù)據(jù)包進行隨機線性組合再轉(zhuǎn)發(fā)出去，只要目的節(jié)點接收到足夠多的線性無關(guān)的數(shù)據(jù)包的線性組合，就可以通過解方程組的思想將所需要的信息提取出來。MORE協(xié)議屬于流內(nèi)網(wǎng)絡(luò)編碼協(xié)議，發(fā)送節(jié)點需要將要發(fā)送的數(shù)據(jù)流分成多個小段，然后對這些在同一個小段的多個數(shù)據(jù)包進行編碼組合，雖然MORE利用網(wǎng)絡(luò)編碼降低了調(diào)度算法的復(fù)雜性，提高了網(wǎng)絡(luò)的吞吐量，但是對于多個段的調(diào)度也是一個很復(fù)雜的問題：什么時候節(jié)點知道某段里面的數(shù)據(jù)包全部被目的節(jié)點接收到而開始下一段的編碼發(fā)送呢？MORE實際上采用的是一種類似于TCP傳輸中“停-等”協(xié)議的思想，只有收到前一階段的確認后，才開始下一階段的傳輸，當(dāng)然，如果源節(jié)點等的時間太長，會嚴重浪費帶寬。于是，在2008年Lin等人[13]中對此加以改進，提出了CodeOR，源節(jié)點以流水線的方式將多個段的數(shù)據(jù)包編碼發(fā)送，只要收到較近的節(jié)點回復(fù)的確認源節(jié)點就馬上開始下一段的處理。但是CodeOR的復(fù)雜性和MORE的一樣很高。進一步受TCP傳輸方式的啟發(fā)，Lin等人在2009年又提出了SlideOR[14]，它借鑒了滑動窗口傳輸?shù)乃枷?，把要發(fā)送的預(yù)編碼的數(shù)據(jù)包按一定順序放在一個滑動窗口中，某個時刻窗口中的數(shù)據(jù)包即為馬上要編碼的數(shù)據(jù)包。SlideOR拋棄了之前分段編碼的方式，通過窗口的不斷滑動，使得不同時刻發(fā)送的編碼的數(shù)據(jù)包能夠互相有利于目的節(jié)點的解碼，大大降低了之前協(xié)議的控制開銷，通過實驗和仿真表明SlideOR[14]相比MORE[12]，CodeOR[13]吞吐量提升了很多，而且協(xié)議簡單，易于實現(xiàn)。

2 基于流間網(wǎng)絡(luò)編碼的路由技術(shù)研究

2006年Katti等人設(shè)計了針對無線mesh網(wǎng)的基于機會路由的網(wǎng)絡(luò)編碼協(xié)議COPE[15]，而且給出了具體的設(shè)計方案[16]，COPE協(xié)議的基本思想是利用了無線鏈路的物理層廣播特性，將分別屬于經(jīng)過同一節(jié)點的兩條反向數(shù)據(jù)流的數(shù)據(jù)包采用最簡單的異或線性編碼（XOR）后發(fā)送，通過機會偵聽和機會編碼兩大機制，節(jié)點利用本地信息以及偵聽附近節(jié)點決定要進行編碼的數(shù)據(jù)包，增加了編碼機會，接收節(jié)點收到混合的數(shù)據(jù)包后利用本地信息解碼后得到自己需要的數(shù)據(jù)包。COPE第一次研究了無線網(wǎng)絡(luò)編碼在實際網(wǎng)絡(luò)環(huán)境的協(xié)議設(shè)計層面上的問題，首次用實驗檢驗了網(wǎng)絡(luò)編碼對實際無線網(wǎng)絡(luò)性能的影響，實驗結(jié)果表明COPE協(xié)議即使在網(wǎng)絡(luò)需求未知或者網(wǎng)絡(luò)流量劇增，或者發(fā)送接收方動態(tài)變化的情況下，COPE協(xié)議仍能有效地減少網(wǎng)絡(luò)中數(shù)據(jù)包的發(fā)送量，從而使得無線Mesh網(wǎng)中多路單播流吞吐量增加。但是COPE協(xié)議需要本地節(jié)點存儲一定的數(shù)據(jù)包并進行編碼，這對節(jié)點的存儲能力要求較高，而且它只考慮了多個數(shù)據(jù)流從不同節(jié)點經(jīng)過一個中間節(jié)點時，中間節(jié)點進行偵聽并進行編碼工作，對編碼機會的把握要求較高，具有一定的局限性。Jin等人[17]提出了編碼感知路由等方法來獲得更多的編碼機會來提高吞吐量。另外，Koutsonikolas等人[18]驗證了一般網(wǎng)絡(luò)模型下無線網(wǎng)絡(luò)編碼的吞吐量增益，并證明其增益是極其有限的，而COPE等的增益依賴于網(wǎng)絡(luò)拓撲，流模型，負載等因素，無線網(wǎng)絡(luò)編碼的吞吐量增益與流的長短和多少都有著緊密的聯(lián)系。S Rayanchu等[19]基于COPE的無線網(wǎng)絡(luò)進行了更深入的理論分析，給出了一般網(wǎng)絡(luò)拓撲中，分析了多條并發(fā)單播數(shù)據(jù)流時網(wǎng)絡(luò)編碼性能增益的理論框架并指出編碼機會感知的路由優(yōu)于傳統(tǒng)的路由。隨后Kai Fan等人[20]針對COPE可能會導(dǎo)致負載不均衡進行了性能改進，[21]設(shè)計了實用性更強的基于無線網(wǎng)絡(luò)編碼的按需路由協(xié)議OCR，進一步提高了無線Mesh網(wǎng)絡(luò)吞吐量。

由于流間網(wǎng)絡(luò)編碼涉及到多源組播的問題，而多源組播網(wǎng)絡(luò)編碼的理論基本上只停留在針對特定拓撲的特定算法的水平上，不適合在拓撲動態(tài)變化的無線網(wǎng)絡(luò)中應(yīng)用，而且流間網(wǎng)絡(luò)編碼還涉及到節(jié)點之間協(xié)同等問題，因此目前的無線網(wǎng)絡(luò)流間網(wǎng)絡(luò)編碼關(guān)于吞吐量增益的研究基本上都是建立在COPE[15]的基礎(chǔ)上，研究還有待進一步深入。

3 總結(jié)與展望

網(wǎng)絡(luò)編碼作為通信領(lǐng)域的一種新生產(chǎn)物，通過近幾年的發(fā)展在無線路由協(xié)議研究領(lǐng)域已經(jīng)取得了一些突破性的成果，但是仍然具有一些不足與局限性：

1）網(wǎng)絡(luò)編碼的理論發(fā)展還有待進一步完善，目前只有針對單源組播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼的研究比較完善，其他形式的網(wǎng)絡(luò)編碼如多源組播網(wǎng)絡(luò)和非組播網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼理論研究也需進一步的研究。另外，非線性網(wǎng)絡(luò)編碼和非確定性網(wǎng)絡(luò)編碼等研究還處在基礎(chǔ)研究階段。

2）目前無線網(wǎng)絡(luò)編碼的很多研究都是針對特定拓撲，特定場景的，雖然取得了很好的吞吐量增益，但是實際的無線網(wǎng)絡(luò)環(huán)境中的拓撲是動態(tài)變化的，場景不是固定的，這樣導(dǎo)致很多研究成果可能無法在實際環(huán)境推廣應(yīng)用，因此需要更加實用化的研究成果，特別是針對戰(zhàn)場通信的研究。

當(dāng)然，作為一種新興技術(shù)，網(wǎng)絡(luò)編碼從產(chǎn)生到豐富完善是一個很漫長的過程，需要研究者共同努力。針對上述問題以及現(xiàn)有研究難點，未來研究的重點可能有以下幾個方向：

1）網(wǎng)絡(luò)編碼的理論尤其是關(guān)于多源組播網(wǎng)絡(luò)編碼的理論研究將是一個亟需解決的問題，因為多源組播在戰(zhàn)場一級網(wǎng)絡(luò)通信中是應(yīng)用最多的。

2）在無線網(wǎng)絡(luò)中跨層設(shè)計網(wǎng)絡(luò)編碼，將網(wǎng)絡(luò)編碼與路由技術(shù)，物理層，MAC的結(jié)合，利用跨層信息的交互來進行網(wǎng)絡(luò)編碼將是未來發(fā)展的一個趨勢。

3）網(wǎng)絡(luò)編碼中的優(yōu)化問題。如何設(shè)計復(fù)雜度低，開銷小的網(wǎng)絡(luò)編碼也是未來的一個主要研究發(fā)展方向。

[參考文獻]

[1]R.Ahlswede，N.Cai，S.R.Li，and R.W.Yeung.Network information flow[J].IEEE Transactions on Information Theory，July 2000.

[2]S Y R Li，R W Yeung，N Cai.Linear network coding.IEEE Trans Info Theory [J].2003，49（2）：371～381.

[3]Tracey Ho，Ralf Koetter，Muriel Medard，David R.Karger and Michelle Effros.The Benefits of Coding over Routing in a Randomized Setting[C].ISIT 2003.

[4]Ho T，Leong B，Médard M，et al.On the utility of network coding in dynamic environments[C].In：Proc.Int’l Workshop on Wireless Ad-hoc Networks （IWWAN），June 2004.

[5]B.Bollobas，Graph Theory，An Introductory Course[M].New York： Springer-Verlag，1979.

[6]Ralf Koetter and Muriel Medard.An Algebraic Approach to Network Coding[J].IEEE/ACM Trans.on Networking， 2003，11（5）：782-795.

[7]Sidharth Jaggi，Peter Sanders，Philip A.Chou，Michelle Effros， Sebastian Egner，Kamal Jain， and Ludo M.G.M.Tolhuizen. Polynomial Time Algorithms for Multicast Network Code Construction[J].IEEE Transactions on Information Theroy， 2005，51（6）：1973-1982.

[8]Tracey Ho，Muriel Medard，Ralf Koetter， David R.Karger， Michelle Effros，Jun Shi，and Ben Leong，A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory， 52（10）：4413-4430， October 2006.

[9]Tracey Ho，David R.Karger，Muriel Medard and Ralf Koetter. Nerwork Coding from a Network Flow Perspective[C].ISIT 2003.

[10]S.Biswas and R.Morris，ExOR：Opportunistic Multi-Hop Routing for Wireless Networks[C]，in Proc.of ACM SIGCOMM，2005.

[11]Joon-sang Park，M.Gerla，D.S.Lun，Yungjung Yi，M.Medard. CodeCast：A Network-Coding-Based AD Hoc Multicast Protocol. Wireless Communication[C]，IEEE Volume 13，Issue 5，October 2006 Page（S）：76-81.

[12]S.Chachulski，M.Jennings，S.Katti，and D.Katabi，Trading Structure for Randomness in Wireless Opportunistic Routing[C].in Proc.of ACM SIGCOMM，2007.

[13]Y.Lin，B.Li，and B.Liang，CodeOR： Opportunistic Routing in Wireless Mesh Networks with Segmented Network Coding[C].in Proc.of IEEE ICNP，2008.

[14]Y.Lin，B.Liang，and B.Li，SlideOR：Online Opportunistic Network Coding in Wireless Mesh Networks[C/OL]，http：//iqua.ece.toronto.edu/papers/slideor.pdf，ECE，University of Toronto，Tech.Rep， December 2009.

[15]Katti S，Rahul H， Katabi D，et al.XORs in the air：Practical wireless network coding[C].SIGCOMM，2006.

[16]Katti S，Hu W J，Medard M.The importance of being opportunistic：Practical network coding for wireless environments[C].Proceeding of the Annual Allerton Conference on Communication，Control，and Computing，Monticello，2005.

[17]Jin Zhang，Qian Zhang.Cooperative Network Coding-Aware Routing for Multi-Rate Wireless Networks[C].In Proc.of IEEE INFOCOM，2009.

[18]D.Koutsonikolas，et al.，An Empirical Study of Performance Benefits of Network Coding in Multihop Wireless Networks[C]. Proc.of IEEE INFOCOM，2009.

[19]S Rayanchu，S Sengupta，S Banerjee，et al.An Analysis of Wireless Network Coding for Unicast Sessions：The Case for Coding-Aware Routing[C].The 26th Annual IEEE Conf on Computer Communications（INFOCOM 2007），Anchorage，AK，USA，2007.

[20]Fan Kai，Wei Xi，Long Dong-yang.A load-balanced route selection for network coding in wireless mesh networks[C].IEEE ICC，2009.

[21]樊凱，李令雄，龍冬陽.無線mesh網(wǎng)中網(wǎng)絡(luò)編碼感知的按需無線路由協(xié)議的研究[J].通信學(xué)報，2009，30（1）：128-134.

[22]熊志強，黃佳慶，劉威，楊宗凱.無線網(wǎng)絡(luò)編碼綜述[J].計算機科學(xué) 2007，34（3）：6-16.

[23]黃政，王新.網(wǎng)絡(luò)編碼中的優(yōu)化問題研究[J].軟件學(xué)報，2009， 20（5）：1349-1361.

[24]夏卓群，陳志剛，沈小建，趙明.無線Mesh網(wǎng)中網(wǎng)絡(luò)編碼的研究進展[J].計算機工程與應(yīng)用，2010，46（12）：1-4.

[25]楊林，鄭剛，胡曉惠.網(wǎng)絡(luò)編碼的研究進展.計算機研究與發(fā)展[J].2008，45（3）：400-407.