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

賈詩(shī)煒

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

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

【中圖分類號(hào)】TN919.3+1【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1672-5158（2013）07-0096-01

1、引言

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

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

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

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

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

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

網(wǎng)絡(luò)編碼之所以得到眾多學(xué)者和科研機(jī)構(gòu)的高度關(guān)注，不僅在于其手段和理念上的程度比較新，更體現(xiàn)在其獨(dú)特的功用上。一般來(lái)說(shuō)，通過網(wǎng)絡(luò)編碼技術(shù)，科研使組播傳輸速率達(dá)到最大，從而拓展了網(wǎng)絡(luò)容量的上限，這對(duì)于目前擁堵的互聯(lián)網(wǎng)通道而言是極為重要的；其次，它還可以節(jié)省網(wǎng)絡(luò)帶寬資源消耗，正是通過線性編碼技術(shù)，提高了網(wǎng)絡(luò)節(jié)點(diǎn)的使用效率和功用，減少了網(wǎng)絡(luò)資源的消耗；另外，網(wǎng)絡(luò)編碼技術(shù)還能均衡網(wǎng)絡(luò)負(fù)載，平衡繁忙的網(wǎng)絡(luò)線路與相對(duì)寬 松的網(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ò)編碼也有不錯(cuò)的應(yīng)用。組播傳輸技術(shù)指在發(fā)送者和每一接收者之間實(shí)現(xiàn)點(diǎn)對(duì)多點(diǎn)網(wǎng)絡(luò)連接，如果一個(gè)發(fā)送者同時(shí)給多個(gè)的接收者傳輸相同的數(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)造方式和多項(xiàng)式時(shí)間算法兩種處理方法，在實(shí)際運(yùn)算中我們需要根據(jù)實(shí)際情況而定[2]。

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

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

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

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

在向量空間的一組元素，如果其中沒有向量可表示成有限個(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ò)信息輸入量。

4、結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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