基于網(wǎng)絡(luò)編碼的多信源組播通信系統(tǒng)，包括源代碼，原理圖等(一)

　　摘要

　　網(wǎng)絡(luò)編碼改變了傳統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)上路由器交換和交換機(jī)對(duì)信息流“存儲(chǔ)—轉(zhuǎn)發(fā)”的模式，提出網(wǎng)絡(luò)路由交換節(jié)點(diǎn)對(duì)輸入的信息流編碼后再發(fā)送，并在接收器上進(jìn)行解碼，從而還原信息。隨著網(wǎng)絡(luò)編碼理論的日益發(fā)展和完善，其應(yīng)用的研究也越來越受到重視。

　　本文首先介紹網(wǎng)絡(luò)編碼理論的基本概念，回顧了近年來網(wǎng)絡(luò)編碼的研究動(dòng)態(tài)。接著指出研究多信源網(wǎng)絡(luò)編碼組播通信的重要性，在使用NetFPGA開發(fā)平臺(tái)的基礎(chǔ)上，提出網(wǎng)絡(luò)編碼組播通信系統(tǒng)及其整體設(shè)計(jì)方案。在方案中重點(diǎn)介紹了硬件系統(tǒng)中采用的編碼策略—隨機(jī)線性編碼，解碼策略、算法以及通信協(xié)議，同時(shí)介紹了系統(tǒng)的軟硬件接口和軟件作用。最后，給出了編碼路由器、轉(zhuǎn)發(fā)路由器以及解碼路由器三個(gè)系統(tǒng)的詳細(xì)設(shè)計(jì)方案，方案中主要包括單元模塊圖，每個(gè)模塊的主要功能與結(jié)構(gòu)，數(shù)據(jù)處理流程及算法說明，輸入輸出信號(hào)及說明、關(guān)鍵時(shí)序或狀態(tài)。

　　由于本系統(tǒng)的主要功能是由硬件實(shí)現(xiàn)，所以和傳統(tǒng)組播通信網(wǎng)絡(luò)相比，具有時(shí)延小，沒有了調(diào)度和排隊(duì)時(shí)間，使得網(wǎng)絡(luò)中鏈路負(fù)載更均衡，體現(xiàn)出了網(wǎng)絡(luò)編碼的優(yōu)勢。

　　1 網(wǎng)絡(luò)編碼理論及相關(guān)研究應(yīng)用背景

　　1.1網(wǎng)絡(luò)編碼理論產(chǎn)生背景和基本概念

　　60年前C.E.Shannon發(fā)表“通信數(shù)學(xué)原理“解決了信道容量極限問題。2000年誕生的網(wǎng)絡(luò)編碼(Network Coding:NC)是繼此后的一個(gè)全新突破，它解決了網(wǎng)絡(luò)通信中單/多源對(duì)多接收點(diǎn)組/廣播如何達(dá)到網(wǎng)絡(luò)容量極限的問題。傳統(tǒng)網(wǎng)絡(luò)通信節(jié)點(diǎn)上的路由交換機(jī)只完成存儲(chǔ)轉(zhuǎn)發(fā)功能。NC指出如果允許路由交換機(jī)對(duì)輸入信息流進(jìn)行編碼再發(fā)送，使得網(wǎng)絡(luò)節(jié)點(diǎn)既實(shí)現(xiàn)路由功能又實(shí)現(xiàn)編碼功能。在這種全新的體系結(jié)構(gòu)下,網(wǎng)絡(luò)性能可以達(dá)到最大流傳輸?shù)睦碚摌O限[1][2]。

　　2000年，以香港中文大學(xué)信息工程系為主的研究人員針對(duì)通訊網(wǎng)絡(luò)的瓶頸問題，提出了一種看似瘋狂的想法，這種具有革命潛力的方法名為網(wǎng)絡(luò)編碼，以網(wǎng)絡(luò)編碼器取代路由器;原本只是單純的傳送信息的路由器，換成編碼器之后，傳送的卻是有關(guān)信息的證據(jù)，而不是信息本身;當(dāng)接收器收到證據(jù)時(shí)，即可結(jié)合各項(xiàng)線索，推導(dǎo)出原始信息。[3]

　　《科學(xué)美國人》雜志(Scientific American Magazine)2007年6月，以“Breaking Network Logjams”(打破網(wǎng)絡(luò)僵局)為題刊登了MIT科學(xué)家詳細(xì)介紹了7年前誕生于香港中文大學(xué)的網(wǎng)絡(luò)編碼理論[4]。其中指出，網(wǎng)絡(luò)編碼是繼60年前C.E.Shannon發(fā)表“通信的數(shù)學(xué)原理”后，網(wǎng)絡(luò)通信理論的一個(gè)全新突破。C.E.Shannon解決了點(diǎn)對(duì)點(diǎn)信道的容量極限問題，而NC解決了如何達(dá)到單源對(duì)多點(diǎn)及多源對(duì)多點(diǎn)的網(wǎng)絡(luò)通信容量極限的問題[4]。傳統(tǒng)網(wǎng)絡(luò)通信理論把信息流當(dāng)成管道中流動(dòng)的水，是不可壓縮的;故傳統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)上的路由交換機(jī)只是完成存儲(chǔ)轉(zhuǎn)發(fā)功能。NC理論的劃時(shí)代意義在于：提出網(wǎng)絡(luò)路由交換節(jié)點(diǎn)對(duì)輸入的信息流進(jìn)行編碼再發(fā)送，可進(jìn)一步提升網(wǎng)絡(luò)吞吐量!從而改變了比特不能再被壓縮的經(jīng)典結(jié)論，指出網(wǎng)絡(luò)信息流可以被壓縮。

　　網(wǎng)絡(luò)編碼最簡單的概念來自‘蝴蝶網(wǎng)’，如圖1.1-1所示：

　　圖1.1-1 網(wǎng)絡(luò)編碼的基本原理

　　上圖所示的網(wǎng)絡(luò)中，源節(jié)點(diǎn)S1想把信息流ai傳送給R1和R2。另一方面，源節(jié)點(diǎn)S2也希望在相同時(shí)間、以相同速度，把信息流bi傳送給同樣的接收節(jié)點(diǎn)R1和R2。假設(shè)每個(gè)路徑每秒可攜帶一個(gè)位元，而且只能順著箭號(hào)所指的方向前進(jìn)。如果路由器只傳輸其所接收到的信息，那么中間鏈路將是個(gè)瓶頸，因?yàn)槊棵肟偣步邮盏蕉辉馁Y料，但其容量只有一位元，路由器每秒只能傳送一位元資料給中間鏈路，這種瓶頸會(huì)造成可怕的塞車。相反，如果把一般的路由器換成編碼器，它可以把兩個(gè)信息通過異或或者線性組合運(yùn)算成單一位元輸送給中間鏈路，并且發(fā)送ai+bi (或者ai和bi的任意線性組合)，這樣就輕而易舉地解決了塞車問題[3][5]。

　　網(wǎng)絡(luò)編碼另一個(gè)與路由系統(tǒng)不同之處在于，充分利用網(wǎng)絡(luò)資源。圖1中，S1透過路徑S1R1把a(bǔ)i傳給R1，S2透過路徑S2R2把bi傳給R2，這在路由系統(tǒng)中是不會(huì)使用到的。節(jié)點(diǎn)R1接收到ai，并且根據(jù)每次編碼器運(yùn)算結(jié)果，輸入到與編碼器使用的相同函數(shù)(異或或者線性組合)內(nèi)，推導(dǎo)出bi。節(jié)點(diǎn)R2解出ai也是同樣的道理。重復(fù)對(duì)每個(gè)位元字串進(jìn)行相同的流程，最后就能得出兩個(gè)原始信息。

　　可見，有了網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)的運(yùn)作可望變得更有效率(不需要增加硬件設(shè)備或頻寬，就可以提高網(wǎng)絡(luò)吞吐量)，可以改善網(wǎng)絡(luò)的負(fù)載均衡，節(jié)省網(wǎng)絡(luò)帶寬消耗，節(jié)省無線網(wǎng)絡(luò)的能量消耗，提高了網(wǎng)絡(luò)的魯棒性，同時(shí)對(duì)于具有鏈路時(shí)延的網(wǎng)絡(luò)，相對(duì)于路由方式，通過網(wǎng)絡(luò)編碼進(jìn)行多播傳輸時(shí)可以獲得較小的傳播時(shí)延[6][7]。

　　隨后，李碩彥等在證明了在足夠大的有限域內(nèi)，通過節(jié)點(diǎn)內(nèi)進(jìn)行線性網(wǎng)絡(luò)編碼(Linear Network Coding： LNC)就可以達(dá)到網(wǎng)絡(luò)組播，廣播等的理論上限[8]。在線性范圍內(nèi)解決達(dá)到理論上界的問題為NC進(jìn)入實(shí)際應(yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)。隨后，Yueng，李碩彥[9]等出版了國際上第一本網(wǎng)絡(luò)編碼理論專著“Network Coding Theory”。

　　Koetter等[10]于2003年提出將NC問題與多項(xiàng)式方程建立數(shù)學(xué)聯(lián)系，使得討論NC問題又多了一種有力的數(shù)學(xué)工具代數(shù)理論;LNC針對(duì)于已經(jīng)了解整個(gè)網(wǎng)絡(luò)拓?fù)錉顩r的情況下，經(jīng)過網(wǎng)絡(luò)路由設(shè)定，通過確定的矩陣計(jì)算公式對(duì)報(bào)文進(jìn)行編解碼，實(shí)現(xiàn)簡單，但適應(yīng)性和容錯(cuò)性較差。論文[11]中提出隨機(jī)網(wǎng)絡(luò)編碼概念(Random Network Coding：RNC)，與線性編碼結(jié)合在一起，使得分布式的、簡單實(shí)用的網(wǎng)絡(luò)編碼體系形成。隨機(jī)線性網(wǎng)絡(luò)編碼是一種分布式算法，編碼在有限域上進(jìn)行，系數(shù)隨機(jī)選取，其靈活性遠(yuǎn)大于LNC。

　　下面給出一個(gè)不僅NC提高多播網(wǎng)絡(luò)吞吐量，而且顯著改善網(wǎng)絡(luò)負(fù)載均衡的例子。圖1.1-2(a)顯示了網(wǎng)絡(luò)的容量，所有的邊的容量都是2。在這個(gè)例子中，最大流是4。圖2(b), (c)和(d)分別顯示了單會(huì)話IP組播，多會(huì)話IP組播和基于網(wǎng)絡(luò)編碼的組播的分配樹。在圖2(b)中，發(fā)送端通過一個(gè)組播分配樹同時(shí)向接收端R1, R2和R3發(fā)送了兩個(gè)比特a，b。在圖2(c)中，組播會(huì)話1，2和3分別向接收者發(fā)送了比特a，b和c。需要指出的是多會(huì)話IP組播所有的會(huì)話不是擁有同一個(gè)分配樹。在圖2(d)中，發(fā)送端同時(shí)向接收端R1, R2和R3發(fā)送了四個(gè)比特a，b，c和d[12]。

　　所有的組播技術(shù)中網(wǎng)絡(luò)編碼可以達(dá)到最高的吞吐量，因?yàn)樗梢宰畲罅靼l(fā)送信息。我們看到在圖2(b), (c)和(d)中在單位時(shí)間內(nèi)接收端分別接收到2，3和4比特。因此在這個(gè)例子中，基于網(wǎng)絡(luò)編碼的組播的吞吐量是單會(huì)話IP組播的2倍，多會(huì)話IP組播的1.3倍。

　　通過比較基于網(wǎng)絡(luò)編碼的組播和現(xiàn)在的組播來研究負(fù)載均衡的影響。假定基于網(wǎng)絡(luò)編碼的組播使用圖2(d)例子中的容量的一半。在這種情況下，單會(huì)話IP組播和網(wǎng)絡(luò)編碼都在單位時(shí)間內(nèi)向所有的接收端發(fā)送了2比特。在圖2(b)中，通過了網(wǎng)絡(luò)中9條鏈路(總共發(fā)送10比特)中的5條來傳輸2比特，另外4條沒有使用。另一方面，當(dāng)網(wǎng)絡(luò)編碼使用時(shí)，2( d) 通過了9條鏈路(總共發(fā)送9比特)來傳輸2比特。于是通過應(yīng)用網(wǎng)絡(luò)編碼，流量負(fù)載可以分散在整個(gè)網(wǎng)絡(luò)上。

　　(a)鏈接容量 (b)單會(huì)話的IP組播

　　(c)多會(huì)話的IP組播 (d)網(wǎng)絡(luò)編碼組播

　　圖1.1-2 網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)容量，同時(shí)均衡了網(wǎng)絡(luò)流量

　　1.2國內(nèi)外研究動(dòng)態(tài)與現(xiàn)狀

　　網(wǎng)絡(luò)編碼自誕生以來，普及性的急速增長就連其奠基者也始料未及。從2005年開始每年一次的NetCod workshop 得到了Microsoft, Qualcomm等機(jī)構(gòu)的資助。短短幾年，發(fā)表了幾百篇學(xué)術(shù)論文。這個(gè)嶄新的領(lǐng)域?qū)υS多相關(guān)學(xué)科產(chǎn)生了深遠(yuǎn)的影響，NC的理論研究范圍包括信息論及通信的幾乎每個(gè)領(lǐng)域，如線性編碼，非線性編碼，隨機(jī)編碼，靜態(tài)碼，卷積碼，群碼，Alphabet碼，碼構(gòu)建，算法協(xié)議，有環(huán)網(wǎng)絡(luò)，無向網(wǎng)絡(luò)，鏈路失效及其網(wǎng)絡(luò)管理，分離理論，錯(cuò)誤檢測和糾錯(cuò)碼，密碼學(xué)，多信源編碼，多-單播編碼, Cost Criteria, 非均勻需求,關(guān)聯(lián)信源編碼，最大流/刮集界，疊加編碼，網(wǎng)絡(luò)互連，路由尋找，無線及衛(wèi)星網(wǎng)絡(luò)，Ad hoc網(wǎng)絡(luò)，傳感網(wǎng)絡(luò)，數(shù)據(jù)存儲(chǔ)及分布，矩陣?yán)碚摚瑥?fù)雜性理論，圖論，隨機(jī)圖論，樹裝箱(Tree Packing)，多種物流(Multicommodity flow)，游戲理論，矩陣胚理論(Matriod theory)，信息論不等式，排隊(duì)論分析，率失真(rate-distortion)可逆網(wǎng)絡(luò)，多用戶信道，聯(lián)合網(wǎng)絡(luò)信道編碼，P2P網(wǎng)絡(luò)等[13]。

　　國外多所著名大學(xué)如普林斯頓大學(xué)、麻省理工、瑞士EPFL 學(xué)院等和多家IT 公司的研究中心,包括微軟研究院、貝爾實(shí)驗(yàn)室、AT &T 的香農(nóng)信息實(shí)驗(yàn)室等都在積極開展對(duì)網(wǎng)絡(luò)編碼理論和應(yīng)用的研究。與此同時(shí)，網(wǎng)絡(luò)編碼的實(shí)際應(yīng)用問題被提到技術(shù)研究的前線。從2005年第一屆Net Cod國際會(huì)議上就明確將NC在現(xiàn)實(shí)通信中的應(yīng)用作為研究的重點(diǎn)。微軟公司是最早開展網(wǎng)絡(luò)編碼應(yīng)用研究的公司[14]，Microsoft公司已經(jīng)采用網(wǎng)絡(luò)編碼作為其下一代網(wǎng)絡(luò)內(nèi)容發(fā)布平臺(tái)Avalanche的核心技術(shù)。

不僅國外，近兩年來國內(nèi)學(xué)者也開始研究網(wǎng)絡(luò)編碼。清華大學(xué)[15]，西安電子科大、及電子科技大學(xué)[16]，北京郵電大學(xué)[17]均投