基于線性網(wǎng)絡(luò)編碼技術(shù)的網(wǎng)絡(luò)編碼研究

賈詩煒

【摘 要】網(wǎng)絡(luò)技術(shù)的興起改變了科技發(fā)展的可能路徑，為新的編碼技術(shù)的存在提供了可靠的發(fā)展模式。網(wǎng)絡(luò)編碼之所以方興未艾，就是因為網(wǎng)絡(luò)優(yōu)于傳統(tǒng)編碼載體的特質(zhì)。通過對網(wǎng)絡(luò)編碼的分析描述，以線性網(wǎng)絡(luò)技術(shù)為基礎(chǔ)，剖析網(wǎng)絡(luò)編碼的可能性和可行性。實踐表明，網(wǎng)絡(luò)編碼是當前多學(xué)科綜合發(fā)展的成果，代表了未來編碼技術(shù)的新發(fā)展方向。本文試就基于線性網(wǎng)絡(luò)編碼技術(shù)的網(wǎng)絡(luò)編碼技術(shù)進行淺要分析。

【關(guān)鍵詞】線性網(wǎng)絡(luò)編碼；網(wǎng)絡(luò)編碼

【中圖分類號】TN919.3+1【文獻標識碼】A【文章編號】1672-5158（2013）07-0096-01

1、引言

網(wǎng)絡(luò)編碼是一種基于網(wǎng)絡(luò)本身而誕生的編碼技術(shù)，這種技術(shù)出現(xiàn)的初衷是為了解決日益擁堵的互聯(lián)網(wǎng)流通問題。人類信息時代的開啟，使互聯(lián)網(wǎng)成為改變?nèi)祟惿鐣罘e極的動力之一。但互聯(lián)網(wǎng)的使用和發(fā)展受到客觀環(huán)境的限制，包括硬件和軟件在內(nèi)的客觀工具的完備與否，都決定了互聯(lián)網(wǎng)能在多大程度上發(fā)揮作用。自本世紀初開始，陸續(xù)有學(xué)者提出了網(wǎng)絡(luò)編碼的理念，希望通過網(wǎng)絡(luò)編碼的方式解決互聯(lián)網(wǎng)擁堵的問題，提高互聯(lián)網(wǎng)使用效率。這一概念的提出，立刻引起諸多學(xué)者和科研機構(gòu)的高度關(guān)注。目前通過網(wǎng)絡(luò)編碼技術(shù)解決互聯(lián)網(wǎng)擁堵問題已經(jīng)成為國內(nèi)外學(xué)界的共識，國外多所著名大學(xué)或是科研機構(gòu)都已展開了網(wǎng)絡(luò)編碼的開拓性研究，如MIT、哈佛大學(xué)、多倫多大學(xué)和微軟實驗室等。

2、網(wǎng)絡(luò)編碼研究現(xiàn)狀

早在上世紀五十年代，就有學(xué)者提出，通信網(wǎng)絡(luò)端對端的最大信息流是由網(wǎng)絡(luò)有向圖的最小分割決定的，但傳統(tǒng)路由器的存儲轉(zhuǎn)發(fā)模式難以達到最大流最小分割定理的上界。根據(jù)傳統(tǒng)的理論，網(wǎng)絡(luò)節(jié)點只是對收到的信息進行存儲和轉(zhuǎn)發(fā)，扮演著轉(zhuǎn)發(fā)器的角色，但是從信息理論的觀點來說，沒有理由讓節(jié)點只能進行存儲轉(zhuǎn)發(fā)，可以讓節(jié)點對多條輸入邊上收到的信息進行一定的線性或非線性操作（編碼），然后再發(fā)送出去，這樣起著編碼器的作用，網(wǎng)絡(luò)編碼正是由此思想產(chǎn)生的，在接收節(jié)點上，通過一定的運算，譯出信源所發(fā)的信息。

本世紀初，學(xué)者R.Ahlswdee 等人發(fā)表的一篇名為“網(wǎng)絡(luò)信息流”的文章中提出了網(wǎng)絡(luò)編碼的概念，作者提出，對于已知的網(wǎng)絡(luò)流圖，從發(fā)點到收點的流量的最大值小于或等于任何一個割切的容量，而網(wǎng)絡(luò)編碼提出了一個組播傳輸，信源為S，接收節(jié)點集合為無窮，那么可達最高組播速率C。而如果采用傳統(tǒng)傳輸方法，可能無法達到最高組播速率。事實上，近年來對于網(wǎng)絡(luò)編碼的實證性研究也充分證明了這一點，這也從另一個方面佐證了網(wǎng)絡(luò)編碼在客觀上的可行性。此外，在R Ahlswede 等人提出網(wǎng)絡(luò)編碼這一概念不久，又有學(xué)者證明了目前的網(wǎng)絡(luò)編碼技術(shù)已經(jīng)能夠達到網(wǎng)絡(luò)組播的條件，同時，還用實驗證明了存在著基于網(wǎng)絡(luò)特性的組播方式的線性網(wǎng)絡(luò)編碼。隨后的研究深入到了隨機網(wǎng)絡(luò)編碼的研究中，Medard等人曾提出如拓展網(wǎng)絡(luò)編碼使用范圍的想法，并通過代數(shù)計算框架給出了可行的路徑。而隨機網(wǎng)絡(luò)編碼的出現(xiàn)則更將非線性研究和網(wǎng)絡(luò)編碼研究融為一體，提高了網(wǎng)絡(luò)編碼研究的理論深度[1]。

目前，對網(wǎng)絡(luò)編碼的研究主要以國外的科研機構(gòu)和大學(xué)研究機構(gòu)為主導(dǎo)，其研究領(lǐng)域已經(jīng)足夠深入，研究框架得到了初步的建立，國內(nèi)對于網(wǎng)絡(luò)編碼的研究尚處于起步階段，在實際運用中也不是很多。

3 、基于線性網(wǎng)絡(luò)編碼技術(shù)的網(wǎng)絡(luò)編碼研究

網(wǎng)絡(luò)編碼之所以得到眾多學(xué)者和科研機構(gòu)的高度關(guān)注，不僅在于其手段和理念上的程度比較新，更體現(xiàn)在其獨特的功用上。一般來說，通過網(wǎng)絡(luò)編碼技術(shù)，科研使組播傳輸速率達到最大，從而拓展了網(wǎng)絡(luò)容量的上限，這對于目前擁堵的互聯(lián)網(wǎng)通道而言是極為重要的；其次，它還可以節(jié)省網(wǎng)絡(luò)帶寬資源消耗，正是通過線性編碼技術(shù)，提高了網(wǎng)絡(luò)節(jié)點的使用效率和功用，減少了網(wǎng)絡(luò)資源的消耗；另外，網(wǎng)絡(luò)編碼技術(shù)還能均衡網(wǎng)絡(luò)負載，平衡繁忙的網(wǎng)絡(luò)線路與相對寬 松的網(wǎng)絡(luò)線路之間的差異，提高網(wǎng)絡(luò)的魯棒性。

3.1 網(wǎng)絡(luò)編碼的分類

網(wǎng)絡(luò)編碼可以分為線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼兩種，前者是研究的重心。在組播和非組播網(wǎng)絡(luò)傳播體系中，網(wǎng)絡(luò)編碼也有不錯的應(yīng)用。組播傳輸技術(shù)指在發(fā)送者和每一接收者之間實現(xiàn)點對多點網(wǎng)絡(luò)連接，如果一個發(fā)送者同時給多個的接收者傳輸相同的數(shù)據(jù)，也只需復(fù)制一份的相同數(shù)據(jù)包，它提高了數(shù)據(jù)傳送效率，網(wǎng)絡(luò)編碼與組播傳輸技術(shù)的綜合，減少了骨干網(wǎng)絡(luò)出現(xiàn)擁塞的可能性。目前，在組播網(wǎng)絡(luò)傳輸中使用的網(wǎng)絡(luò)編碼技術(shù)一般有代數(shù)構(gòu)造方式和多項式時間算法兩種處理方法，在實際運算中我們需要根據(jù)實際情況而定[2]。

3.2 基于現(xiàn)行網(wǎng)絡(luò)編碼技術(shù)的網(wǎng)絡(luò)編碼

（1）線性網(wǎng)絡(luò)編碼原理

網(wǎng)絡(luò)編碼技術(shù)看似復(fù)雜，其原理其實不難，以線性網(wǎng)絡(luò)編碼的編碼譯碼原理為例，其基本思想就是在編碼時根據(jù)每個節(jié)點的每個相鄰鏈路對的局部編碼標量，得到每個節(jié)點的局部編碼矩陣，將局部編碼標量和局部編碼矩陣的線性組合，得到關(guān)于每條鏈路的全局編碼向量，在此基礎(chǔ)上，得到實行網(wǎng)絡(luò)編碼后各條連接線路的具體編碼信息。在譯碼時，需要考慮的是譯碼矩陣，這需要將所有節(jié)點受到的全部信息加衣匯總，并對信息進行分析處理，從而譯出信源節(jié)點所存儲和收發(fā)的全部信息。綜上所述，線性編碼的思路其實還是比較簡潔的，一般只要確定了局部編譯矩陣，便可以確定全局編碼向量，然后通過對破譯矩陣的運用，剖析信源節(jié)點發(fā)出的信息，從而實現(xiàn)網(wǎng)絡(luò)通信中信息的收發(fā)。線性網(wǎng)絡(luò)編碼技術(shù)提高了網(wǎng)絡(luò)運行的安全性，提高了網(wǎng)絡(luò)的總體容量，具有較高的可行性。

（2）網(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個標準基的線性組合的，所以，向量空間vs*n的每個列向量均是s個標準基的線性組合，所以vs*n的秩為s。在有向無環(huán)網(wǎng)絡(luò)中，對于非信源節(jié)點T，當其最大數(shù)據(jù)流大于等于網(wǎng)絡(luò)信息輸入信息量時，其所有輸入鏈路全局編碼向量所生成的向量空間的秩為網(wǎng)絡(luò)輸入信息量，即向量空間中線性無關(guān)的全局編碼向量的個數(shù)為網(wǎng)絡(luò)信息輸入量。

4、結(jié)束語

網(wǎng)絡(luò)編碼是近年來興起的一個新的研究領(lǐng)域，由于其在解決網(wǎng)絡(luò)擁堵，克服傳統(tǒng)網(wǎng)絡(luò)傳輸模式方面具有較高的優(yōu)越性，正在引起人們越來越多的重視。但隨著對網(wǎng)絡(luò)編碼研究的深入，一些問題也隨著浮出水面，需要得到重視并有待進一步解決。其中包括了網(wǎng)絡(luò)編碼在傳輸速率、負載消耗、負載均衡、魯棒性等方面帶來的收益需要進行更加深入的研究，而且網(wǎng)絡(luò)編碼需要網(wǎng)絡(luò)路由器具有編碼功能，且現(xiàn)有路由算法、傳輸協(xié)議等需要改變和更新；此外，基于網(wǎng)絡(luò)編碼的差錯控制是一種新的差錯控制思想，可以為將來的研究提供更多的借鑒。在可以預(yù)見的將來，網(wǎng)絡(luò)編碼必然是一種能得到廣泛應(yīng)用與推廣的互聯(lián)網(wǎng)革新力量，將會對整個網(wǎng)絡(luò)世界的發(fā)展產(chǎn)生深遠的影響。

參考文獻

[1] 吳艷，楊有龍，劉三陽.基于網(wǎng)絡(luò)流矩陣求解網(wǎng)絡(luò)最大流[J].系統(tǒng)工程，2007

[2] 謝政，李建平.網(wǎng)路算法與復(fù)雜性理論[M].國防科技大學(xué)出版社，1995