基于線性網絡編碼技術的網絡編碼研究

賈詩煒

【摘 要】網絡技術的興起改變了科技發展的可能路徑，為新的編碼技術的存在提供了可靠的發展模式。網絡編碼之所以方興未艾，就是因為網絡優于傳統編碼載體的特質。通過對網絡編碼的分析描述，以線性網絡技術為基礎，剖析網絡編碼的可能性和可行性。實踐表明，網絡編碼是當前多學科綜合發展的成果，代表了未來編碼技術的新發展方向。本文試就基于線性網絡編碼技術的網絡編碼技術進行淺要分析。

【關鍵詞】線性網絡編碼；網絡編碼

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

1、引言

網絡編碼是一種基于網絡本身而誕生的編碼技術，這種技術出現的初衷是為了解決日益擁堵的互聯網流通問題。人類信息時代的開啟，使互聯網成為改變人類社會最積極的動力之一。但互聯網的使用和發展受到客觀環境的限制，包括硬件和軟件在內的客觀工具的完備與否，都決定了互聯網能在多大程度上發揮作用。自本世紀初開始，陸續有學者提出了網絡編碼的理念，希望通過網絡編碼的方式解決互聯網擁堵的問題，提高互聯網使用效率。這一概念的提出，立刻引起諸多學者和科研機構的高度關注。目前通過網絡編碼技術解決互聯網擁堵問題已經成為國內外學界的共識，國外多所著名大學或是科研機構都已展開了網絡編碼的開拓性研究，如MIT、哈佛大學、多倫多大學和微軟實驗室等。

2、網絡編碼研究現狀

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

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

目前，對網絡編碼的研究主要以國外的科研機構和大學研究機構為主導，其研究領域已經足夠深入，研究框架得到了初步的建立，國內對于網絡編碼的研究尚處于起步階段，在實際運用中也不是很多。

3 、基于線性網絡編碼技術的網絡編碼研究

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

3.1 網絡編碼的分類

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

3.2 基于現行網絡編碼技術的網絡編碼

（1）線性網絡編碼原理

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

（2）網絡編碼的線性多播性質

在向量空間的一組元素，如果其中沒有向量可表示成有限個其他向量的線性組合，則稱為線性無關，反之稱為線性相關。有向無環網絡中，對于任何非信源節點T，輸入鏈路為n，均存在由其所有輸入鏈路d的全局編碼向量fS*1集合組成的向量空間vs*n。若n≥s，則vs*n秩的最大值為s。已知全局編碼向量均是從s個標準基的線性組合的，所以，向量空間vs*n的每個列向量均是s個標準基的線性組合，所以vs*n的秩為s。在有向無環網絡中，對于非信源節點T，當其最大數據流大于等于網絡信息輸入信息量時，其所有輸入鏈路全局編碼向量所生成的向量空間的秩為網絡輸入信息量，即向量空間中線性無關的全局編碼向量的個數為網絡信息輸入量。

4、結束語

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

參考文獻

[1] 吳艷，楊有龍，劉三陽.基于網絡流矩陣求解網絡最大流[J].系統工程，2007

[2] 謝政，李建平.網路算法與復雜性理論[M].國防科技大學出版社，1995