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

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

網(wǎng)絡(luò)編碼理論也稱為網(wǎng)絡(luò)信息流理論，屬于網(wǎng)絡(luò)信息論的重要分支。經(jīng)典信息論的編碼通常是信源編碼和信道編碼，而網(wǎng)絡(luò)編碼與其有本質(zhì)上的不同。網(wǎng)絡(luò)編碼除考慮信源和信宿節(jié)點(diǎn)的編碼外，中間節(jié)點(diǎn)也參與編碼，并且網(wǎng)絡(luò)編碼能從整體上提高網(wǎng)絡(luò)吞吐量，提升通信系統(tǒng)的有效性。

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

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

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

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

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

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

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

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

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

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

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

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

me=x·fe

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

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

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] 蒲保興，楊路明，王偉平.線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴(kuò)展[J].軟件學(xué)報(bào)，

2011.22（3）：558-571

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

2011.47（7）.

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

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] 周偉偉.線性網(wǎng)絡(luò)編碼研究[J].通信技術(shù)，2008.41（2）.