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

　　摘要

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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