網(wǎng)絡(luò)編碼研究綜述摘要：網(wǎng)絡(luò)編碼是通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突破，它的核心思想是允許網(wǎng)絡(luò)節(jié)點對所傳輸?shù)男畔⑦M行編碼處理。它在提高網(wǎng)絡(luò)數(shù)據(jù)吞吐量即數(shù)據(jù)傳輸可靠性等方面擁有顯著的優(yōu)勢。本文介紹網(wǎng)絡(luò)編碼的基本原理以及主要優(yōu)缺點，對網(wǎng)絡(luò)編碼的研究進展進行分析，分析網(wǎng)絡(luò)編碼當前面臨的重要問題，以及解決網(wǎng)絡(luò)編碼問題可能采取的方法。關(guān)鍵詞：網(wǎng)絡(luò)編碼；隨機網(wǎng)絡(luò)編碼；網(wǎng)絡(luò)編碼機制引言 香港中文大學(xué)的R.Alshwede等在2000年的IEEE信息會議上發(fā)表的一篇著名論文[1]，該論文首次提出了網(wǎng)絡(luò)編碼(NetworkCoding)的概念，并從理論上證明了：如果允許網(wǎng)絡(luò)節(jié)點對傳輸?shù)男畔凑蘸线m的方式進行編碼處理，而不是局限于傳統(tǒng)的存儲和轉(zhuǎn)發(fā)，則基于該方式的網(wǎng)絡(luò)多播總能夠?qū)崿F(xiàn)理論上的最大傳輸容量。網(wǎng)絡(luò)節(jié)點對傳輸信息進行操作和處理的過程，就稱為網(wǎng)絡(luò)編碼。 網(wǎng)絡(luò)編碼的提出是網(wǎng)絡(luò)通信領(lǐng)域中的一項重要突破，自其被Ahlswede提出以來，已迅速發(fā)展成為一個重要的研究領(lǐng)域，對信息論、編碼、通信網(wǎng)絡(luò)、網(wǎng)絡(luò)交換理論、無線通信、計算機科學(xué)、密碼學(xué)、矩陣論等研究領(lǐng)域產(chǎn)生了深遠的影響，已成為當今最熱門的研究領(lǐng)域之一。網(wǎng)絡(luò)編碼是一種融合編碼和路由的信息交換技術(shù)。它的原理是，網(wǎng)絡(luò)中的節(jié)點對接收到的多個數(shù)據(jù)分組進行編碼融合，經(jīng)過編碼后的數(shù)據(jù)被中間節(jié)點以多播的方式進行轉(zhuǎn)發(fā)，目的結(jié)點可依據(jù)相應(yīng)的編碼系數(shù)進行解碼，從融合的數(shù)據(jù)中還原出原始的數(shù)據(jù)，網(wǎng)絡(luò)編碼通過允許網(wǎng)絡(luò)中間節(jié)點對不同數(shù)據(jù)流數(shù)據(jù)編碼獲得網(wǎng)絡(luò)最大流傳輸理論的上界，從而改變了傳統(tǒng)網(wǎng)絡(luò)節(jié)點智能從當存儲、轉(zhuǎn)發(fā)的角色。 網(wǎng)絡(luò)編碼已引起國內(nèi)外學(xué)者的廣泛關(guān)注，國外一些著名的院校和實驗室都對網(wǎng)絡(luò)編碼進行了研究，例如MIT、普林斯頓大學(xué)和微軟研究院等，它們的研究側(cè)重點在應(yīng)用網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)吞吐量及提高網(wǎng)絡(luò)能量利用率，以及編碼提高網(wǎng)絡(luò)傳輸?shù)目煽啃院桶踩缘确矫?。其中，前一個側(cè)重點的研究多集中在傳輸中編碼策略的研究[2-3]，而在提高數(shù)據(jù)傳輸?shù)目煽啃缘确矫娴难芯慷嗉性跀?shù)據(jù)的重傳策略方面[4]。國內(nèi)香港中文大學(xué)和西安電子科技大學(xué)等方面的學(xué)者對網(wǎng)絡(luò)編碼的研究做出了重要的貢獻，網(wǎng)絡(luò)編碼的思想是由楊偉豪和李碩彥首次提出。他們將網(wǎng)絡(luò)編碼應(yīng)用于檢測和糾正網(wǎng)絡(luò)錯誤的研究。楊偉豪和蔡寧[5]在經(jīng)典糾錯碼的基礎(chǔ)上引入了網(wǎng)絡(luò)糾錯碼的概念，通過引入空間域的冗余代替時間域的冗余來糾正網(wǎng)絡(luò)通信中的錯誤，將經(jīng)典糾錯碼的Hamming界、Singleton界和Gilbert-Vashamov界推廣到網(wǎng)絡(luò)編碼中。 本文對網(wǎng)絡(luò)編碼的基本概念和網(wǎng)絡(luò)編碼的研究現(xiàn)狀以及在研究中存在的問題進行描述和分析。網(wǎng)絡(luò)編碼的原理和優(yōu)缺點網(wǎng)絡(luò)編碼的原理在傳統(tǒng)的網(wǎng)絡(luò)中，節(jié)點僅對接收的數(shù)據(jù)進行存儲和轉(zhuǎn)發(fā)，難以達到網(wǎng)絡(luò)傳輸?shù)淖畲笸掏铝亢蛶捓寐?，若?shù)據(jù)傳輸路徑出現(xiàn)瓶頸鏈路，則網(wǎng)絡(luò)數(shù)據(jù)傳輸性能將受到限制。為此，引入網(wǎng)絡(luò)編碼技術(shù)，增加節(jié)點對數(shù)據(jù)的編碼運算能力，節(jié)約網(wǎng)絡(luò)鏈路的帶寬資源，減小網(wǎng)絡(luò)數(shù)據(jù)傳輸中瓶頸鏈路的影響。R.Alshwede等以著名的“蝴蝶網(wǎng)絡(luò)”模型為例，闡述了網(wǎng)絡(luò)編碼的基本原理。如圖1所示，“單信源二信宿”蝴蝶網(wǎng)絡(luò)，設(shè)各鏈路容量為1，S是信源節(jié)點，Y和Z是信宿節(jié)點，其余為中間節(jié)點。根據(jù)“最大流最小割”定理，該多播模型理論最大傳輸容量為2，即信宿Y和Z能夠同時接收信源S發(fā)出的2個單位的信息，也就是說能同時收到b1和b2。圖1(a)表示的是傳統(tǒng)的路由傳輸方式，假定節(jié)點W轉(zhuǎn)發(fā)信息b1,則鏈路WX、XY和XZ上傳輸?shù)男畔⒕鶠閎1，雖然信宿Z收到b1和b2，但是信宿Y時能收到b1，因此信宿Y和Z無法同時收到b1和b2，該多播不能實現(xiàn)最大容量傳輸。圖1(b)表示的是網(wǎng)絡(luò)編碼方法，節(jié)點W對收到的信息不再僅僅是存儲、轉(zhuǎn)發(fā)了，而是對收到的信息進行異或操作，然后將操作結(jié)果b1^b2轉(zhuǎn)發(fā)出去，經(jīng)過鏈路最終到達信宿Y和Z。信宿節(jié)點收到信息后進行解碼操作（對于Y節(jié)點，解碼操作為b1^（b1^b2））就能解出b1或b2，因此信宿Y和Z就能同時收到信源發(fā)出的b1和b2。因此基于網(wǎng)絡(luò)編碼的多播實現(xiàn)了理論上的最大傳輸容量。 由此知道，網(wǎng)絡(luò)編碼的核心思想是，具備編碼條件的網(wǎng)絡(luò)節(jié)點對收到的信息進行一定方式的處理，然后傳傳輸給下一級的網(wǎng)絡(luò)節(jié)點，如果收到信息的下一級網(wǎng)絡(luò)節(jié)點擁有編碼能力，同樣進行對信息編碼，如此一級級傳遞下去，直到所有經(jīng)過處理的信息都匯聚到信宿節(jié)點為止。最后在信宿節(jié)點通過逆過程的操作，即譯碼，解碼出信宿節(jié)點傳遞的原始信息。網(wǎng)絡(luò)編碼是發(fā)生在域Fq上的操作，如果域Fq無限大，則運用網(wǎng)絡(luò)編碼的多播傳輸能達到理論上的最大傳輸容量等于各信宿節(jié)點的最大流的最小值，即h=min{maxflow(ti)},ti∈T。圖1.單信源二信宿蝴蝶網(wǎng)絡(luò)網(wǎng)絡(luò)編碼的優(yōu)缺點1.2.1網(wǎng)絡(luò)編碼的優(yōu)點 提升網(wǎng)絡(luò)吞吐量是網(wǎng)絡(luò)編碼帶來的最大優(yōu)勢，而且理論證明，對于節(jié)點平均度數(shù)越大，網(wǎng)絡(luò)編碼在網(wǎng)絡(luò)吞吐量上的優(yōu)勢越明顯。如果Ω為信源節(jié)點的符號空間，|V|為通信網(wǎng)絡(luò)的節(jié)點數(shù)目，對于每條鏈路都是單位容量的通信網(wǎng)絡(luò)，基于網(wǎng)絡(luò)編碼的多播的吞吐量是路由多播的Ω倍[6]。 網(wǎng)絡(luò)編碼可有效利用除多播樹路徑外其它的網(wǎng)絡(luò)鏈路，可將網(wǎng)絡(luò)流量分布于更廣泛的網(wǎng)絡(luò)上，從而均衡網(wǎng)絡(luò)負載，有助于解決網(wǎng)絡(luò)擁塞等問題。提高網(wǎng)絡(luò)帶寬利用率是網(wǎng)絡(luò)編碼的另一個顯著的優(yōu)點。此外，通過網(wǎng)絡(luò)編碼，可以抵抗網(wǎng)絡(luò)鏈路和節(jié)點的非各態(tài)歷經(jīng)性失敗對網(wǎng)絡(luò)連接的影響，提高網(wǎng)絡(luò)連接的魯棒性，減少網(wǎng)絡(luò)管理的開銷。在無線網(wǎng)絡(luò)中，還能降低網(wǎng)絡(luò)傳輸能耗，增加網(wǎng)絡(luò)傳輸?shù)陌踩訹7]。1.2.2網(wǎng)絡(luò)編碼的缺點 雖然網(wǎng)絡(luò)編碼有很多的優(yōu)勢，但是網(wǎng)絡(luò)編碼在帶來優(yōu)勢的同時也有伴隨著一些不利因素，例如，網(wǎng)絡(luò)編碼增加了計算的復(fù)雜性，而且網(wǎng)路節(jié)點需要緩存足夠的輸入信息，因此編碼操作增加了網(wǎng)絡(luò)傳輸延時和節(jié)點的額外的輸入輸出功耗。在節(jié)點中進行編譯碼所耗費的時間也是不容忽視的問題，此外，應(yīng)用網(wǎng)絡(luò)編碼還存在同步問題，也就是說，信宿節(jié)點必須等待收到足夠的編碼信息，才能夠開始譯碼，同步問題給實時系統(tǒng)中應(yīng)用網(wǎng)絡(luò)編碼提出來挑戰(zhàn)。網(wǎng)絡(luò)編碼的研究進展分析2.1經(jīng)典網(wǎng)絡(luò)編碼的研究 目前，編碼機制的設(shè)計和優(yōu)化一直是網(wǎng)絡(luò)編碼研究的熱門方向。網(wǎng)絡(luò)編碼機制的研究主要集中在：確定性網(wǎng)絡(luò)編碼、隨機性網(wǎng)絡(luò)編碼和現(xiàn)存網(wǎng)絡(luò)編碼的優(yōu)化。對于確定性網(wǎng)絡(luò)編碼，編碼節(jié)點對接收的數(shù)據(jù)進行編碼組合的系數(shù)為固定量，而且編碼系數(shù)向量隨編碼數(shù)據(jù)在網(wǎng)絡(luò)中同時傳輸。確定性網(wǎng)絡(luò)編碼的優(yōu)點在于編碼系數(shù)穩(wěn)定，因此在網(wǎng)絡(luò)中傳輸編碼系數(shù)的信息量較少，減小網(wǎng)絡(luò)的開銷。但是由于信宿節(jié)點需要知道整個網(wǎng)絡(luò)的拓撲信息，因此網(wǎng)絡(luò)擴展性差，難以適應(yīng)現(xiàn)實中廣泛存在的分布式網(wǎng)絡(luò)環(huán)境。 因此，基于上述原因，Ho等[8]提出了隨機網(wǎng)絡(luò)編碼機制，即在編碼中，節(jié)點攜帶一個全局編碼向量，當編碼數(shù)據(jù)經(jīng)過每一個節(jié)點時，節(jié)點根據(jù)其編碼方式改變信息的同時改變編碼向量，信宿節(jié)點僅需接收到一定量的編碼數(shù)據(jù)即可解碼出原始數(shù)據(jù)，因此，信宿節(jié)點不需要知道整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。相對于確定性網(wǎng)絡(luò)編碼機制，隨機網(wǎng)絡(luò)編碼機制較為靈活，具有較強的實用性。 為了進一步改進網(wǎng)絡(luò)編碼機制，基于上述經(jīng)典性網(wǎng)絡(luò)編碼機制，研究者從不同角度提出了網(wǎng)絡(luò)編碼機制的優(yōu)化。一個代表性的研究表現(xiàn)為具有編碼參量動態(tài)調(diào)整的網(wǎng)絡(luò)編碼機制的改造。文獻[9]提出了數(shù)據(jù)分批編碼傳輸機制，解決了動態(tài)網(wǎng)絡(luò)環(huán)境中的編碼問題。實際網(wǎng)絡(luò)編碼機制的構(gòu)造和設(shè)計逐漸深入過渡到適合網(wǎng)絡(luò)具體特點方面的探討，在較大程度上促進了網(wǎng)絡(luò)編碼機制的研究發(fā)展。目前，網(wǎng)絡(luò)編碼研究一個亟待解決的問題是編碼機制的復(fù)雜性，這包括編碼機制產(chǎn)生的優(yōu)勢和其對網(wǎng)絡(luò)產(chǎn)生的負面效應(yīng)的平衡等重要問題。2.2基于網(wǎng)絡(luò)傳輸QOS的網(wǎng)絡(luò)編碼研究 在網(wǎng)絡(luò)傳輸中服務(wù)質(zhì)量是一個很重需要的性能指標，研究者從這一方面出發(fā)進一步對網(wǎng)絡(luò)編碼進行了研究。研究主要集中在一下兩個方面：(1)多速率網(wǎng)絡(luò)編碼機制：在多速率編碼機制中，來自不同鏈路且具有不同數(shù)據(jù)速率的數(shù)據(jù)在網(wǎng)絡(luò)編碼決策機制中被分析，以減少編碼對網(wǎng)絡(luò)中具有高數(shù)據(jù)傳輸速率數(shù)據(jù)的影響。文獻[10]提出基于Jaggi多項式算法的非源數(shù)據(jù)接收速率動態(tài)調(diào)整的機制，以及基于線性廣播算法和減矢量的變速率編碼機制。(2)基于網(wǎng)絡(luò)鏈路狀態(tài)和數(shù)據(jù)編碼傳播特點的網(wǎng)絡(luò)編碼機制：在現(xiàn)有的多數(shù)網(wǎng)絡(luò)編碼機制中，均假設(shè)網(wǎng)絡(luò)為無環(huán)結(jié)構(gòu)、鏈路數(shù)據(jù)傳輸不存在延時和丟失等情況，但是，眾所周知這是不符合實際網(wǎng)絡(luò)傳輸條件的，實際情況正好與此相反。對此，文獻[11]對網(wǎng)絡(luò)編解碼中數(shù)據(jù)的傳輸時延描述模型及相應(yīng)的解決策略，文獻[12]提出單跳網(wǎng)絡(luò)環(huán)境下不同要求數(shù)據(jù)的編碼調(diào)度問題，對網(wǎng)絡(luò)編碼中數(shù)據(jù)傳輸時延的解決具有一定的啟發(fā)性。2.3基于網(wǎng)絡(luò)傳輸安全性的網(wǎng)絡(luò)編碼研究 數(shù)據(jù)在網(wǎng)絡(luò)中傳輸?shù)陌踩砸恢笔侨藗冞M行網(wǎng)絡(luò)研究的熱點。雖然網(wǎng)絡(luò)數(shù)據(jù)在傳輸路徑上的中間節(jié)點經(jīng)過編碼后可能具有更高的安全性。但是，數(shù)據(jù)在中間節(jié)點進行編碼時也有可能別人利用，在中間節(jié)點處對數(shù)據(jù)進行更改，因此，提高網(wǎng)絡(luò)編碼過程中數(shù)據(jù)的安全性已經(jīng)成為網(wǎng)絡(luò)編碼研究的重要問題。網(wǎng)絡(luò)編碼中數(shù)據(jù)的安全性研究主要集中在2個方面：(1)網(wǎng)絡(luò)編碼中數(shù)據(jù)提供安全性保證，網(wǎng)絡(luò)編碼產(chǎn)生的信息分散性和編譯碼特性增加了信息被破譯的難度，即在網(wǎng)絡(luò)編碼中單個節(jié)點上很難解碼出經(jīng)過編碼混合機多徑傳輸后的編碼數(shù)據(jù)。(2)將現(xiàn)有網(wǎng)絡(luò)安全機制和網(wǎng)絡(luò)編碼機制進行結(jié)合是網(wǎng)絡(luò)編碼研究的的一個重要方向，在安全信令交換的基礎(chǔ)上進行數(shù)據(jù)的編碼操作，以提高編碼過程中數(shù)據(jù)的安全性。由此可知，在網(wǎng)絡(luò)編碼方案設(shè)計中，對不同編碼機制進行數(shù)據(jù)安全性的分析是網(wǎng)絡(luò)編碼當前研究的一個重要問題，對提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)陌踩跃哂兄匾饬x。2.4多源網(wǎng)絡(luò)編碼機制的研究 多源網(wǎng)絡(luò)編碼不是單源網(wǎng)絡(luò)編碼的簡單擴充。與單源網(wǎng)絡(luò)編碼研究的側(cè)重點不同，單源網(wǎng)絡(luò)編碼研究的目的在于使數(shù)據(jù)源節(jié)點以最大速率向所有信宿節(jié)點傳輸數(shù)據(jù)，而多源網(wǎng)絡(luò)編碼研究的側(cè)重點在于信息的可達速率域，其研究集中在3個方面：建立多源網(wǎng)絡(luò)編碼的構(gòu)造算法，算法分為多源多播和多源單播，主要解決不同數(shù)據(jù)源發(fā)送的數(shù)據(jù)在同一個網(wǎng)絡(luò)中相互影響的問題；另外兩個方面為多源網(wǎng)絡(luò)編碼和分布式信源編碼的聯(lián)合和分離問題，以及多源網(wǎng)絡(luò)編碼信息可達速率域問題這些問題包含相關(guān)源數(shù)據(jù)的壓縮機編碼的優(yōu)化問題。網(wǎng)絡(luò)編碼在實際應(yīng)用的研究目前，網(wǎng)絡(luò)編碼的研究仍主要局限在編碼理論方面，對于具體實現(xiàn)和實際應(yīng)用的研究仍然很少，這是網(wǎng)絡(luò)編碼研究面臨的一個主要問題。Chou等在文獻[13]中討論了網(wǎng)絡(luò)編碼在實際應(yīng)用中存在的問題及解決方案，Widmer等在文獻中討論了在特殊網(wǎng)絡(luò)環(huán)境下具有網(wǎng)絡(luò)編碼的可靠數(shù)據(jù)傳輸方案，同時，一些應(yīng)用網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)系統(tǒng)及圓形系統(tǒng)也被提出，主要為微軟公司開發(fā)的P2P雪崩軟件Avalanche和MIT應(yīng)用于無線局域網(wǎng)絡(luò)的COPE和MORE網(wǎng)絡(luò)編碼原型系統(tǒng)，這些原型系統(tǒng)均為網(wǎng)絡(luò)編碼的優(yōu)勢進行了實際網(wǎng)絡(luò)環(huán)境下的驗證。近年來，將網(wǎng)絡(luò)物理層技術(shù)與網(wǎng)絡(luò)高層的軟件技術(shù)進行結(jié)合是網(wǎng)絡(luò)發(fā)展的趨勢之一，網(wǎng)絡(luò)編碼的概念包含了物理層的編碼和網(wǎng)絡(luò)層的路由，并且可擴展到網(wǎng)絡(luò)層中，為網(wǎng)絡(luò)編碼的應(yīng)用研究提供了基礎(chǔ)。在網(wǎng)絡(luò)編碼的應(yīng)用研究中，MIT和微軟這兩個機構(gòu)的研究成果對網(wǎng)絡(luò)編碼的實現(xiàn)及應(yīng)用給出了開創(chuàng)性的探討，但網(wǎng)絡(luò)編碼在實際網(wǎng)絡(luò)中的部署及應(yīng)用仍處于起步階段，眾多問題仍需探討。要想將網(wǎng)絡(luò)編碼應(yīng)用到實際中，應(yīng)從一下兩個方面給予重視：(1)網(wǎng)絡(luò)編碼的機制應(yīng)盡量簡單化，盡管一些編碼機制在理論研究中具有較大的優(yōu)勢，但是由于過于復(fù)雜，例如二項式網(wǎng)絡(luò)編碼機制及有環(huán)網(wǎng)絡(luò)編碼機制等，不可能在實際中得到廣泛應(yīng)用。(2)網(wǎng)絡(luò)編碼機制需要對現(xiàn)有的路由器結(jié)構(gòu)進行改造以使其具有可以編碼機制，但是這是需要巨大的工程量，和花費大量的成本代價，很難實現(xiàn)。一種可行的方式是先對局部區(qū)域路由器進行改造，或在現(xiàn)存路由器中嵌入相應(yīng)的軟件模塊或附掛擴展外部設(shè)備，從而避免對現(xiàn)存網(wǎng)絡(luò)路由器大規(guī)模更替?？傊?，網(wǎng)絡(luò)編碼真正應(yīng)用到實際之中還有很長的路要走。結(jié)束語網(wǎng)絡(luò)編碼已經(jīng)滲透到計算機網(wǎng)絡(luò)，通信技術(shù)和分布式等各種信息技術(shù)領(lǐng)域中，網(wǎng)絡(luò)編碼被理解為具有通用性的原理。網(wǎng)絡(luò)編碼作為通信網(wǎng)絡(luò)中信息處理和傳輸理論研究的重大突破，具有重要的理論價值和廣闊的應(yīng)用前景，被認為是下一代網(wǎng)絡(luò)關(guān)鍵技術(shù)之一。隨著研究的不斷深入，相信網(wǎng)絡(luò)編碼技術(shù)一定會從理論過度到實際應(yīng)用，而且其應(yīng)用定會給人類的生活帶來不可估量的價值。參考文獻[1]RudolfAhlswede,NingCai,shuo-YenRobertLi,etal.Networkinformationflow[J].IEEETrans.Inform.Theory,2000,46(4):1204-1216.[2]LISY,YEUNGRW,CAIN.Linearnetworkcoding[J].IEEETransactionsonInformationTheory,2003,49(2):371-381.[3]KOETTERR,MEDARDM.Analgebraicapproachtonetworkcoding[J].IEEE/ACMTransactionsonNetworking,2003,11:782-795.[4]NGUYEND,NGUYENT,BOSEB.Wirelessbroadcastingusingnetworkcoding[R].OregonStateUniversity,2006.[5]YEUNGRW,CAIN.Networkerrorcorrection,PartI:Basicconceptsandupperbounds[J].CommunicationsinInformationandSystems,2006,6(1):19-36.[6]HoT,KargerD,MedardM,etal.Thebenfitsofcodingoverroutinginarandomizedsetting[C].IEEEInternationalSymposiumonInformationTheory,Yokhama,Japan,June,2003,442.[7]WuY,ChouPA,ZhangQ,etal.Networkplanninginwirelessadhocnetworksacross-layerapproach[J].IEEEJ.Sel.AreasCommun,2005,23(1):136-150.[8]HoT,MEDARDM,SHIJ,etal.Onrandomizednetworkcoding[C]///Procofthe41stAnnualAllertonConferenceonCommunicationControlandComputing,Monticello,USA,2003.[9]LIUH．TUX．Onefficientandreliablenetworkcodingpracticalenvironment[c]InternationalConferencemlCommunication，Ci