基于網(wǎng)絡(luò )編碼的多信源組播通信系統,包括源代碼,原理圖等(一)
摘要
本文引用地址:http://dyxdggzs.com/article/201612/326829.htm網(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]均投
評論