今天的互聯(lián)網(wǎng)信息就像高速路上的汽車或管道中的水流一樣被傳輸著，日益增長的網(wǎng)絡(luò)帶寬需求和不可靠網(wǎng)絡(luò)的QOS需求，已成為制約網(wǎng)絡(luò)發(fā)展的瓶頸。為擴大網(wǎng)絡(luò)覆蓋范圍和提高系統(tǒng)容量，采用網(wǎng)絡(luò)編碼技術(shù)實現(xiàn)網(wǎng)絡(luò)的最大流傳輸，已被國際學(xué)術(shù)界認(rèn)定為解決網(wǎng)絡(luò)問題的重要手段，并成為網(wǎng)絡(luò)理論研究的熱點問題之一。

　　摘要：描述了網(wǎng)絡(luò)編碼的研究現(xiàn)狀和存在的問題，通過分析線性網(wǎng)絡(luò)編碼技術(shù)的編碼和譯碼原理證明了網(wǎng)絡(luò)編碼的可行性，并基于線性代數(shù)理論論證了線性網(wǎng)絡(luò)編碼的最基本性質(zhì)-線性多播性。提出網(wǎng)絡(luò)編碼技術(shù)是一門“混合”的技術(shù)，未來網(wǎng)絡(luò)編碼技術(shù)將結(jié)合計算機網(wǎng)絡(luò)技術(shù)，信息論和編碼技術(shù)，密碼學(xué)理論等不斷發(fā)展和深入。

　　關(guān)鍵詞：網(wǎng)絡(luò)編碼,可行性,線性多播性,混合

　　1網(wǎng)絡(luò)編碼研究現(xiàn)狀和存在的問題

　　上個世紀(jì)50年代香農(nóng)就提出：通信網(wǎng)絡(luò)端對端的最大信息流是由網(wǎng)絡(luò)有向圖的最小分割決定的，但傳統(tǒng)路由器的存儲轉(zhuǎn)發(fā)模式難以達(dá)到最大流最小分割定理的上界。2000年，香港中文大學(xué)R.Ahlswdee等人在發(fā)表的論文NetworkInformationFlow中首次提出了網(wǎng)絡(luò)編碼[9]，并根據(jù)信息論嚴(yán)格證明了網(wǎng)絡(luò)編碼允許中間節(jié)點對接收到的信息進(jìn)行編碼并轉(zhuǎn)發(fā)，接收節(jié)點通過相應(yīng)的解碼獲得原始信息，這樣可以達(dá)到通信網(wǎng)絡(luò)的容量上界，從而最大限度利用網(wǎng)絡(luò)資源。網(wǎng)絡(luò)編碼的提出從本質(zhì)上打破了通信網(wǎng)絡(luò)中傳統(tǒng)的信息處理方式，是通信網(wǎng)絡(luò)研究中一個重要的里程碑事件。近年來，網(wǎng)絡(luò)編碼理論的研究已取得重要發(fā)展，同時在應(yīng)用基礎(chǔ)和工程實踐方面的研究也正在全方面展開。2003年，SYR.Li等人證明了使用線性網(wǎng)絡(luò)編碼已經(jīng)能足夠達(dá)到網(wǎng)絡(luò)多播容量。KoetterR等人提出了網(wǎng)絡(luò)編碼的代數(shù)框架，并證明了存在滿足多播流量的線性不變編碼。這兩位學(xué)者的工作為網(wǎng)絡(luò)編碼的發(fā)展準(zhǔn)備了必要的理論條件。隨機網(wǎng)絡(luò)編碼是由HoT、Medard等人在2003年提出的，它的提出拓寬了網(wǎng)絡(luò)編碼的適用場景，使得網(wǎng)絡(luò)編碼不再局限于確定的網(wǎng)絡(luò)拓?fù)浜图�中式算法。CaiNing利用分布式網(wǎng)絡(luò)編碼來糾正網(wǎng)絡(luò)中的差錯，并論述了網(wǎng)絡(luò)編碼在安全方面的應(yīng)用，為網(wǎng)絡(luò)編碼增加了新的應(yīng)用領(lǐng)域。國外多所著名大學(xué)如麻省理工學(xué)院、多倫多大學(xué)、瑞士EPFL學(xué)院等，以及多家知名IT研究機構(gòu)包括微軟研究院、貝爾實驗室等，都在積極開展網(wǎng)絡(luò)編碼理論和應(yīng)用的研究，而國內(nèi)針對編碼的研究尚處于起步階段。

　　目前，網(wǎng)絡(luò)編碼的理論研究尚處于初步階段，實際應(yīng)用也遠(yuǎn)未挖掘出其真正潛力，還有大量的難題有待解決。①即便網(wǎng)絡(luò)編碼可以提高通過率，能使問題得到有效解決，但是要確定存在合適的邊函數(shù)卻是件不容易的事情。還存在網(wǎng)絡(luò)什么時候傳輸?shù)倪吅瘮?shù)有用，有多少信息需要通過這種方式傳送等問題。②在許多實際的網(wǎng)絡(luò)中，并不一定是有向或無環(huán)的。對于有環(huán)網(wǎng)絡(luò)構(gòu)造的編碼是時變的，這在實際中很少應(yīng)用。并沒有證明有環(huán)網(wǎng)中最佳時不變碼的存在。③多源網(wǎng)絡(luò)編碼構(gòu)造問題。④目前許多的有效編碼算法都只限于應(yīng)用到組播的情況，缺少一般性。⑤網(wǎng)絡(luò)安全與網(wǎng)絡(luò)管理的應(yīng)用。

　　2網(wǎng)絡(luò)編碼技術(shù)概述

　　網(wǎng)絡(luò)編碼的概念源于2000年AhlswedeR，CaiN，SYR.Li，R.W.Yeung發(fā)表的論文《NetworkInformationFlow》，其最初的思想即允許網(wǎng)絡(luò)的中間節(jié)點參與編譯碼。網(wǎng)絡(luò)編碼采用存儲-編譯碼-轉(zhuǎn)發(fā)的方式，可達(dá)到網(wǎng)絡(luò)的多播容量[6]。網(wǎng)絡(luò)編碼的實質(zhì)：①信息流被壓縮或被編碼；②網(wǎng)絡(luò)編碼是通過計算（編碼）提升吞吐量。（網(wǎng)絡(luò)吞吐量：是指在沒有幀丟失的情況下，設(shè)備能夠接受的最大速率。吞吐量的單位以比特/秒或字節(jié)/秒表示。）網(wǎng)絡(luò)編碼理論也稱為網(wǎng)絡(luò)信息流理論，屬于網(wǎng)絡(luò)信息論的重要分支。經(jīng)典信息論的編碼通常是信源編碼和信道編碼，而網(wǎng)絡(luò)編碼與其有本質(zhì)上的不同。網(wǎng)絡(luò)編碼除考慮信源和信宿節(jié)點的編碼外，中間節(jié)點也參與編碼，并且網(wǎng)絡(luò)編碼能從整體上提高網(wǎng)絡(luò)吞吐量，提升通信系統(tǒng)的有效性。

　　網(wǎng)絡(luò)編碼理論指出網(wǎng)絡(luò)信息流可以被壓縮，從而進(jìn)一步提升網(wǎng)絡(luò)吞吐量。并且信息流仍然滿足守恒定理，雖然信息內(nèi)容被處理，但處理前后信息是不增也不減的。

　　其中，線性網(wǎng)絡(luò)編碼是研究較早，也是較為成熟的一類。有向無環(huán)網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼稱為線性網(wǎng)絡(luò)編碼。蒲保興等詳細(xì)分析了線性網(wǎng)絡(luò)編碼的計算時延與關(guān)鍵參量之間的關(guān)系[5]。

　　3線性網(wǎng)絡(luò)編碼的編碼譯碼原理及其可行性

　　線性網(wǎng)絡(luò)編碼中的核心是確定兩個重要參數(shù)，即局部編碼矩陣和全局編碼向量。

　　定義1線性網(wǎng)絡(luò)編碼的局部編碼矩陣[8]

　　有向無環(huán)網(wǎng)絡(luò)中，已知F為有限域（具有有限個元素的域），s（向量矩陣維數(shù)）為正數(shù)。對于任何節(jié)點T，其線性網(wǎng)絡(luò)編碼的局部編碼矩陣為：

　　KT=[kd，e]d∈In（T），e∈Out（T）

　　式中，In（T）是節(jié)點T所有輸入鏈路的集合，Out（T）為節(jié)點T所有輸出鏈路的集合，|In（T）|表示節(jié)點T輸入鏈路的個數(shù)，|Out（T）|表示節(jié)點T輸出鏈路的個數(shù)。KT矩陣是維數(shù)等于|In（T）|×|Out（T）|的矩陣。kd，e表示節(jié)點T的每個相鄰鏈路對（d，e）的局部編碼標(biāo)量，取值于有限域F。

　　對于信源節(jié)點由于沒有輸入鏈路，一般假設(shè)產(chǎn)生s維信號的信源節(jié)點存在s條輸入鏈路，由于這s條鏈路實際并不存在，所以稱為虛擬鏈路。

　　定義2線性網(wǎng)絡(luò)編碼的全局編碼向量

　　式中，fd為輸入鏈路d的全局編碼向量，fe稱為輸出鏈路e的全局編碼向量。全局編碼的是維數(shù)等于s*1的列向量，標(biāo)記網(wǎng)絡(luò)輸入信號量為s。該迭代公式的初始條件是信源節(jié)點的s維虛擬鏈路的全局編碼向量，它是從向量空間上選擇的一個s維的標(biāo)準(zhǔn)基。

　　定義3線性網(wǎng)絡(luò)編碼中全局編碼向量與鏈路上傳輸信息的關(guān)系

　　me=x·fe

　　式中，x為信源節(jié)點產(chǎn)生的所有信息行向量，維數(shù)為1*s。fe為鏈路e上的全局編碼向量，me為鏈路e上傳輸?shù)男畔ⅰＭㄟ^線性編碼后每條鏈路上傳輸?shù)氖顷P(guān)于輸入信號的線性表達(dá)量。

　　定義4線性多播的譯碼矩陣D

　　[fe]e∈In（T）·D=Is

　　式中，maxflow（T）是針對任何滿足maxflow（T）≥s的節(jié)點T，[fe]e∈In（T）為節(jié)點T所有輸入鏈路的全局編碼向量并列放置一起所組成的矩陣，Is為s×s維的單位矩陣。

　　將節(jié)點T收到的所有消息（可用消息矩陣x·[fe]e∈In（T）表示）乘以譯碼矩陣D，即可譯碼出信源節(jié)點S所發(fā)出的信息。

　　線性網(wǎng)絡(luò)編碼的編碼和譯碼原理，其基本思想是，編碼時，根據(jù)每個節(jié)點的每個相鄰鏈路對的局部編碼標(biāo)量，得到每個節(jié)點的局部編碼矩陣。將局部編碼標(biāo)量和局部編碼矩陣的線性組合，得到關(guān)于每條鏈路的全局編碼向量。于是得到通過編碼后每條鏈路的實際傳輸信息。譯碼時，由定義4得到譯碼矩陣D，將信宿節(jié)點收到的所有消息乘以D，即可譯碼出信源節(jié)點所發(fā)出的所有信息。

　　可見，線性編碼的基本思路簡潔，當(dāng)局部編碼矩陣確定后，可以惟一確定全局編碼向量，并可通過譯碼矩陣得到其信源信息，并易于在網(wǎng)絡(luò)通信中實現(xiàn)，保證了在網(wǎng)絡(luò)中信息的安全，提高了吞吐量，由此網(wǎng)絡(luò)編碼是可行的。

　　4網(wǎng)絡(luò)編碼的線性多播性質(zhì)

　　在向量空間的一組元素，如果其中沒有向量可表示成有限個其他向量的線性組合，則稱為線性無關(guān)，反之稱為線性相關(guān)。

　　有向無環(huán)網(wǎng)絡(luò)中，對于任何非信源節(jié)點T，輸入鏈路為n，均存在由其所有輸入鏈路d的全局編碼向量fS*1集合組成的向量空間vs*n。若n≥s，則vs*n秩的最大值為s。已知全局編碼向量均是從s個標(biāo)準(zhǔn)基的線性組合的，所以，向量空間vs*n的每個列向量均是s個標(biāo)準(zhǔn)基的線性組合，所以vs*n的秩為s。

　　在有向無環(huán)網(wǎng)絡(luò)中，對于非信源節(jié)點T，當(dāng)其最大數(shù)據(jù)流大于等于網(wǎng)絡(luò)信息輸入信息量時，其所有輸入鏈路全局編碼向量所生成的向量空間的秩為網(wǎng)絡(luò)輸入信息量，即向量空間中線性無關(guān)的全局編碼向量的個數(shù)為網(wǎng)絡(luò)信息輸入量。所以，信源節(jié)點發(fā)出的信息量為w，則非信源節(jié)點最多收到信源發(fā)出的w個信息。對滿足輸入鏈路大于w的節(jié)點，則能同時接收到信源發(fā)出的所有信息。在路由的情況這是不可能的，這是網(wǎng)絡(luò)編碼性能優(yōu)于路由的本質(zhì)原因。

　　有向無環(huán)網(wǎng)絡(luò)中，對于任何非信源節(jié)點T，存在其所有輸入鏈路e的全局編碼列向量fe的集合所生成的向量空間ve。對于滿足輸入最大流量大于等于網(wǎng)絡(luò)輸入信息量的非信源節(jié)點T，均有

　　dim（ve）=網(wǎng)絡(luò)輸入信息量

　　則此時的線性網(wǎng)絡(luò)編碼稱為線性多播。在有向無環(huán)網(wǎng)絡(luò)中，線性多播是其最基本的特點。

　　5結(jié)束語

　　在有向無環(huán)網(wǎng)絡(luò)中，由于不存在環(huán)，所以我們可以“由上至下”從信源節(jié)點至信宿節(jié)點順序地線性編碼傳輸信息，增強了信息傳輸安全性，提高了網(wǎng)絡(luò)吞吐量。在此，我們詳細(xì)描述了網(wǎng)絡(luò)編碼技術(shù)的現(xiàn)狀和存在的問題，并通過線性網(wǎng)絡(luò)編碼技術(shù)論證了網(wǎng)絡(luò)編碼是一門可行的網(wǎng)絡(luò)技術(shù)，而且，從線性代數(shù)理論基礎(chǔ)上證明了網(wǎng)絡(luò)編碼存在線性多播性。

　　有向無環(huán)網(wǎng)絡(luò)編碼理論的研究是網(wǎng)絡(luò)編碼技術(shù)不可或缺的內(nèi)容。未來網(wǎng)絡(luò)編碼技術(shù)的發(fā)展將結(jié)合計算機網(wǎng)絡(luò)技術(shù)，信息論和編碼技術(shù)，密碼學(xué)理論等知識，并結(jié)合現(xiàn)代技術(shù)如透明計算，云計算等不斷發(fā)展和深入。

　　參考文獻(xiàn)：

　　[1]謝堅戈，袁濤，王曉靈等.網(wǎng)絡(luò)編碼調(diào)度策略的研究[J].電視技術(shù)，

　　2012.36（3）.

　　[2]XiaYin，ZhangTiyuan，HuangJiaqingJ.Newalgorithmfor

　　variable-ratelinearbroadcastnetworkcoding.Cent.SouthUniv[J].Technol，2011.18：1193-1199

　　[3]蒲保興，楊路明，王偉平.線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴展[J].軟件學(xué)報，

　　2011.22（3）：558-571

　　[4]司菁菁.線性網(wǎng)絡(luò)編碼的類型保持轉(zhuǎn)換矩陣[J].計算機工程與應(yīng)用，

　　2011.47（7）.

　　[5]蒲保興，王偉平.線性網(wǎng)絡(luò)編碼運算代價的估算與分析[J].通信學(xué)報，

　　2011.32（5）.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiwangluolw/27303.html