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

劉永廣

（廣東輕工職業(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é)點(diǎn)的計(jì)算能力提高鏈路帶寬的利用率，圖1的蝴蝶網(wǎng)絡(luò)闡述了網(wǎng)絡(luò)編碼的基本原理。

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

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

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

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

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

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

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

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

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

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

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

由于網(wǎng)絡(luò)編碼涉及信息緩存和矩陣運(yùn)算，其額外開(kāi)銷比傳統(tǒng)路由傳輸要大，因此降低網(wǎng)絡(luò)編碼的復(fù)雜性，對(duì)網(wǎng)絡(luò)編碼算法進(jìn)行優(yōu)化，具有重要的意義。目前的主要解決方案有基于簡(jiǎn)單網(wǎng)絡(luò)的解決方案[5]，基于信息流分解的解決方案[6]，基于最小代價(jià)函數(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ò)時(shí)延、吞吐量、帶寬、安全性等方面，在這一部分，將通過(guò)仿真分析幾種網(wǎng)絡(luò)編碼算法對(duì)QoS參數(shù)的影響。

3.1 仿真環(huán)境

仿真環(huán)境中共布置100個(gè)節(jié)點(diǎn)，仿真拓?fù)湟约肮?jié)點(diǎn)之間的連接關(guān)系采用Waxman[8]拓?fù)淠Ｐ?，首先在仿真的?jié)點(diǎn)中基于均勻分布隨機(jī)產(chǎn)生一個(gè)源節(jié)點(diǎn)和多個(gè)目的節(jié)點(diǎn)，其次找到從源節(jié)點(diǎn)到多個(gè)目的節(jié)點(diǎn)的最小割集，最后選擇網(wǎng)絡(luò)編碼算法進(jìn)行編碼處理，本仿真中采用的網(wǎng)絡(luò)編碼算法都是二維結(jié)構(gòu)，即均采用兩個(gè)編碼系數(shù)，在節(jié)點(diǎn)交匯處進(jìn)行編碼，然后再轉(zhuǎn)發(fā)出去，仿真主要研究和比較延遲和吞吐量?jī)蓚€(gè)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是四個(gè)算法在吞吐量方面的表現(xiàn)，由于優(yōu)化編碼算法采取了優(yōu)化策略，獲得的網(wǎng)絡(luò)吞吐量最大，而啟發(fā)式算法側(cè)重于速度的要求，網(wǎng)絡(luò)吞吐量較低。

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

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

4.結(jié)論

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

圖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.