劉永廣

（廣東輕工職業(yè)技術(shù)學(xué)院，廣東廣州510300）

1.網(wǎng)絡(luò)編碼的基本概念

近幾年出現(xiàn)的網(wǎng)絡(luò)編碼理論[1]可以顯著地增加網(wǎng)絡(luò)容量和可靠性，網(wǎng)絡(luò)編碼徹底改變了通信網(wǎng)絡(luò)中信息處理和傳輸?shù)姆绞?，是信息理論研究領(lǐng)域的重大突破，已經(jīng)引起學(xué)術(shù)界廣泛關(guān)注和重視。網(wǎng)絡(luò)編碼的本質(zhì)是利用節(jié)點的計算能力提高鏈路帶寬的利用率，圖1的蝴蝶網(wǎng)絡(luò)闡述了網(wǎng)絡(luò)編碼的基本原理。

圖1 網(wǎng)絡(luò)編碼的原理

圖中s是信源，x、y是信宿，各邊的帶寬均為1bit/單位時間，現(xiàn)要將2bit數(shù)據(jù)a和b同時從s傳到x和y。可以看出s與x和y之間均分別存在兩條獨(dú)立路徑，若采用傳統(tǒng)路由方法，由于兩組路徑存在共有鏈路wz，a和b不能同時在鏈路wz上傳輸，則s到x和y的最大信息流速率為1.5bit/單位時間。若采用網(wǎng)絡(luò)編碼方法，在節(jié)點w上對a、b執(zhí)行異或操作并轉(zhuǎn)發(fā)，則節(jié)點x可以通過a⊕b⊕a的計算解出b，同理y也可以解出a，從而使s到x、y的信息流速率達(dá)到2bit/單位時間，帶寬利用率提高33%。

可見，網(wǎng)絡(luò)編碼的核心思想是：具備編碼條件的網(wǎng)絡(luò)節(jié)點對接收到的信息進(jìn)行一定方式的編碼處理，然后傳送下一級的網(wǎng)絡(luò)節(jié)點，最后，在信宿節(jié)點通過逆過程的操作，即可譯出信源發(fā)送的原始信息。

2.常用的網(wǎng)絡(luò)編碼算法

2.1 確定性網(wǎng)絡(luò)編碼

文獻(xiàn)[2]首次針對組播網(wǎng)絡(luò)提出了確定性分布式網(wǎng)絡(luò)編碼算法，其核心思想是將網(wǎng)絡(luò)拓?fù)浞纸獬啥鄠€子樹，并保證每個子樹的編碼矢量屬于其父樹編碼矢量的擴(kuò)張空間，且任意兩個子樹的共有信宿的編碼矢量均線性無關(guān)，該方法具有良好的可擴(kuò)展性。

2.2 隨機(jī)性網(wǎng)絡(luò)編碼

Ho等人給出了一種隨機(jī)系數(shù)的分布式網(wǎng)絡(luò)編碼算法[3]，其隨機(jī)系數(shù)從有限域中均勻隨機(jī)選取，該方法對線性相關(guān)的信源具有信息壓縮作用，適用于鏈路動態(tài)變化的場景，當(dāng)給定的字母表足夠大時能漸進(jìn)達(dá)到最大組播速率，具有很強(qiáng)的實用性。

2.3 啟發(fā)式網(wǎng)絡(luò)編碼

P.Sander等人提出了一種能夠在多項式時間實現(xiàn)的集中式算法[4]，該算法是線性網(wǎng)絡(luò)編碼的快速實現(xiàn)，其目標(biāo)是在盡可能小的有限域上快速地尋找編碼向量，該算法首次將計算復(fù)雜性局限在多項式范圍內(nèi)，極大提高了網(wǎng)絡(luò)編碼的實用性。該算法主要包括三個步驟：（1）構(gòu)造信源S至各個信宿節(jié)點t的路徑簇；（2）將路徑簇上的鏈路按照拓?fù)渑判颍唬?）依次尋找各個鏈路的全局編碼向量，使得各個路徑簇上最新鏈路的編碼向量能夠形成一個基，以此確保最終形成的轉(zhuǎn)移矩陣滿秩。

2.4 優(yōu)化網(wǎng)絡(luò)編碼

由于網(wǎng)絡(luò)編碼涉及信息緩存和矩陣運(yùn)算，其額外開銷比傳統(tǒng)路由傳輸要大，因此降低網(wǎng)絡(luò)編碼的復(fù)雜性，對網(wǎng)絡(luò)編碼算法進(jìn)行優(yōu)化，具有重要的意義。目前的主要解決方案有基于簡單網(wǎng)絡(luò)的解決方案[5]，基于信息流分解的解決方案[6]，基于最小代價函數(shù)的解決方案[7]等。這些算法分別從編碼構(gòu)造、編碼操作數(shù)以及有限域大小等方面去進(jìn)行優(yōu)化。

3.基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)Q oS性能分析

網(wǎng)絡(luò)的QoS參數(shù)主要有：網(wǎng)絡(luò)時延、吞吐量、帶寬、安全性等方面，在這一部分，將通過仿真分析幾種網(wǎng)絡(luò)編碼算法對QoS參數(shù)的影響。

3.1 仿真環(huán)境

仿真環(huán)境中共布置100個節(jié)點，仿真拓?fù)湟约肮?jié)點之間的連接關(guān)系采用Waxman[8]拓?fù)淠Ｐ?，首先在仿真的?jié)點中基于均勻分布隨機(jī)產(chǎn)生一個源節(jié)點和多個目的節(jié)點，其次找到從源節(jié)點到多個目的節(jié)點的最小割集，最后選擇網(wǎng)絡(luò)編碼算法進(jìn)行編碼處理，本仿真中采用的網(wǎng)絡(luò)編碼算法都是二維結(jié)構(gòu)，即均采用兩個編碼系數(shù)，在節(jié)點交匯處進(jìn)行編碼，然后再轉(zhuǎn)發(fā)出去，仿真主要研究和比較延遲和吞吐量兩個QoS參數(shù)，仿真在QualNet 5.0下完成。

3.2 仿真結(jié)果及分析

本次仿真分別比較了優(yōu)化網(wǎng)絡(luò)編碼（Optimal）、啟發(fā)式網(wǎng)絡(luò)編碼（Heuristic）、隨機(jī)性網(wǎng)絡(luò)編碼（Random）和確定性網(wǎng)絡(luò)編碼（Deterministic）四種網(wǎng)絡(luò)編碼算法在網(wǎng)絡(luò)吞吐量和延遲方面的表現(xiàn)。

圖2是四個算法在吞吐量方面的表現(xiàn)，由于優(yōu)化編碼算法采取了優(yōu)化策略，獲得的網(wǎng)絡(luò)吞吐量最大，而啟發(fā)式算法側(cè)重于速度的要求，網(wǎng)絡(luò)吞吐量較低。

圖2 網(wǎng)絡(luò)吞吐量比較

圖3是四個算法在延遲方面的比較，由圖中可以看出優(yōu)化網(wǎng)絡(luò)編碼盡管吞吐量大，但是所付出的延遲也比較大，而其它幾種算法在延遲方面的表現(xiàn)就比較理想，尤其是啟發(fā)式算法，大部分情況下保持一個比較低的延遲。

4.結(jié)論

本文分析了幾種網(wǎng)絡(luò)編碼中的常用算法，并對幾種編碼算法在提高QoS性能方面的表現(xiàn)進(jìn)行了仿真研究，仿真表明優(yōu)化算法在網(wǎng)絡(luò)吞吐量方面有良好的表現(xiàn)，而啟發(fā)式算法則在低延遲方面更具優(yōu)勢。

圖3 網(wǎng)絡(luò)延遲的比較

[1]Li S-Y R，Yeung R W.Linear networking[J].IEEE Trans.Inform.Theory，2000.

[2]Fragouli C，Soljanin E.Decentralized network coding[C].IEEE Information Theory Workshop，San Antonio，Texas，2004.

[3]Ho T，Karger D R，Edard M M，et al.The benefits of coding over routing in a randomized setting[C].IEEE Int’l Symp on Information Theory(ISIT)，Pacifica Yokohama，2003.

[4]Sanders P，Egner S，Tolhuizen L.Polynomial time algorithm for network information flow[C].Proceedings of 15th ACM Symposium on Parallel Algorithms and Architectures，2003.

[5]Jaggi s，Chou P A，Jain K.Low compIexity algebraic network codes[C].Proceedings of.ISIT，2003.

[6]Fragouli C，Soljanin E.Information flow decomposition for networkcoding[J].Information Theory，IEEE Transactions，March 2006.52(3)：829-848.

[7]Lun D，Medard M.Ho T，et la.Network coding with a cost criterion[C].International symposium on Information Theory and its Applications(ISITA)，Oct，2004.

[8]Waxman B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications，1988，6(9)：1617-1622.