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

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

關鍵詞： 網絡編碼； 可行性； 線性多播性； 混合

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2012）12-01-02

Research on network coding based on linear network coding technology

Li Ni， Yang Wangdong， Chen Qiang

（Department of Information Science and Engineering， Hunan City College， Yiyang， Hunan 413000， China）

Abstract： The status of the network coding research and the existing problems are described. The feasibility of network coding is proven through the analysis of linear network coding technology coding and decoding principle. The most basic property of the linear network coding-linear multicast property is demonstrated based on theory of linear algebra. Finally， the network coding technology is put forward as a \"hybrid\" technology. The network coding technology development will be combined with the computer network technology， information theory， coding technology and cryptography theory.

Key words： network coding； feasibility； linear multicast property； hybrid

0 引言

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

1 網絡編碼研究現狀和存在的問題

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

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

2 網絡編碼技術概述

網絡編碼的概念源于2000年Ahlswede R，Cai N，SYR.Li，R.W.Yeung發表的論文《Network Information Flow》，其最初的思想即允許網絡的中間節點參與編譯碼。網絡編碼采用存儲-編譯碼-轉發的方式，可達到網絡的多播容量[6]。網絡編碼的實質：①信息流被壓縮或被編碼；②網絡編碼是通過計算（編碼）提升吞吐量。（網絡吞吐量：是指在沒有幀丟失的情況下，設備能夠接受的最大速率。吞吐量的單位以比特/秒或字節/秒表示。）

網絡編碼理論也稱為網絡信息流理論，屬于網絡信息論的重要分支。經典信息論的編碼通常是信源編碼和信道編碼，而網絡編碼與其有本質上的不同。網絡編碼除考慮信源和信宿節點的編碼外，中間節點也參與編碼，并且網絡編碼能從整體上提高網絡吞吐量，提升通信系統的有效性。

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

其中，線性網絡編碼是研究較早，也是較為成熟的一類。有向無環網絡中的網絡編碼稱為線性網絡編碼。蒲保興等詳細分析了線性網絡編碼的計算時延與關鍵參量之間的關系[5]。

3 線性網絡編碼的編碼譯碼原理及其可行性

線性網絡編碼中的核心是確定兩個重要參數，即局部編碼矩陣和全局編碼向量。

定義1 線性網絡編碼的局部編碼矩陣[8]

有向無環網絡中，已知F為有限域（具有有限個元素的域），s（向量矩陣維數）為正數。對于任何節點T，其線性網絡編碼的局部編碼矩陣為：

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

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

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

定義2 線性網絡編碼的全局編碼向量

式中，fd為輸入鏈路d的全局編碼向量，fe稱為輸出鏈路e的全局編碼向量。全局編碼的是維數等于s*1的列向量，標記網絡輸入信號量為s。該迭代公式的初始條件是信源節點的s維虛擬鏈路的全局編碼向量，它是從向量空間上選擇的一個s維的標準基。

定義3 線性網絡編碼中全局編碼向量與鏈路上傳輸信息的關系

me=x·fe

式中，x為信源節點產生的所有信息行向量，維數為1*s。fe為鏈路e上的全局編碼向量，me為鏈路e上傳輸的信息。通過線性編碼后每條鏈路上傳輸的是關于輸入信號的線性表達量。

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

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

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

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

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

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

4 網絡編碼的線性多播性質

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

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

在有向無環網絡中，對于非信源節點T，當其最大數據流大于等于網絡信息輸入信息量時，其所有輸入鏈路全局編碼向量所生成的向量空間的秩為網絡輸入信息量，即向量空間中線性無關的全局編碼向量的個數為網絡信息輸入量。所以，信源節點發出的信息量為w，則非信源節點最多收到信源發出的w個信息。對滿足輸入鏈路大于w的節點，則能同時接收到信源發出的所有信息。在路由的情況這是不可能的，這是網絡編碼性能優于路由的本質原因。

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

dim（ve）=網絡輸入信息量

則此時的線性網絡編碼稱為線性多播。在有向無環網絡中，線性多播是其最基本的特點。

5 結束語

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

有向無環網絡編碼理論的研究是網絡編碼技術不可或缺的內容。未來網絡編碼技術的發展將結合計算機網絡技術，信息論和編碼技術，密碼學理論等知識，并結合現代技術如透明計算，云計算等不斷發展和深入。

參考文獻：

[1] 謝堅戈，袁濤，王曉靈等.網絡編碼調度策略的研究[J].電視技術，

2012.36（3）.

[2] Xia Yin， Zhang Tiyuan， Huang Jiaqing J .New algorithm for

variable-rate linear broadcast network coding. Cent. South Univ[J].Technol，2011.18：1193-1199

[3] 蒲保興，楊路明，王偉平.線性網絡編碼的導出與擴展[J].軟件學報，

2011.22（3）：558-571

[4] 司菁菁.線性網絡編碼的類型保持轉換矩陣[J].計算機工程與應用，

2011.47（7）.

[5] 蒲保興，王偉平.線性網絡編碼運算代價的估算與分析[J].通信學報，

2011.32（5）.

[6] Yeung R， Li S，Cai Nl.Network coding theory. foundation and

trends in communications and information theory[M]. Now Publishers，2006：11-55

[7] Tan M，Yeung R，Ho S.A unified framework for linear network

codes.Proceedings of the 4th Workshop on Network Coding Theory and Applications[C].Hong Kong，China，2008：132-136

[8] R.W.Yeung.Information Theory and Network Coding[M].Springer.

J31，2008.

[9] 周偉偉.線性網絡編碼研究[J].通信技術，2008.41（2）.