基于網絡編碼的網絡Q oS性能分析

劉永廣

（廣東輕工職業技術學院，廣東廣州510300）

1.網絡編碼的基本概念

近幾年出現的網絡編碼理論[1]可以顯著地增加網絡容量和可靠性，網絡編碼徹底改變了通信網絡中信息處理和傳輸的方式，是信息理論研究領域的重大突破，已經引起學術界廣泛關注和重視。網絡編碼的本質是利用節點的計算能力提高鏈路帶寬的利用率，圖1的蝴蝶網絡闡述了網絡編碼的基本原理。

圖1 網絡編碼的原理

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

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

2.常用的網絡編碼算法

2.1 確定性網絡編碼

文獻[2]首次針對組播網絡提出了確定性分布式網絡編碼算法，其核心思想是將網絡拓撲分解成多個子樹，并保證每個子樹的編碼矢量屬于其父樹編碼矢量的擴張空間，且任意兩個子樹的共有信宿的編碼矢量均線性無關，該方法具有良好的可擴展性。

2.2 隨機性網絡編碼

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

2.3 啟發式網絡編碼

P.Sander等人提出了一種能夠在多項式時間實現的集中式算法[4]，該算法是線性網絡編碼的快速實現，其目標是在盡可能小的有限域上快速地尋找編碼向量，該算法首次將計算復雜性局限在多項式范圍內，極大提高了網絡編碼的實用性。該算法主要包括三個步驟：（1）構造信源S至各個信宿節點t的路徑簇；（2）將路徑簇上的鏈路按照拓撲排序；（3）依次尋找各個鏈路的全局編碼向量，使得各個路徑簇上最新鏈路的編碼向量能夠形成一個基，以此確保最終形成的轉移矩陣滿秩。

2.4 優化網絡編碼

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

3.基于網絡編碼的網絡Q oS性能分析

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

3.1 仿真環境

仿真環境中共布置100個節點，仿真拓撲以及節點之間的連接關系采用Waxman[8]拓撲模型，首先在仿真的節點中基于均勻分布隨機產生一個源節點和多個目的節點，其次找到從源節點到多個目的節點的最小割集，最后選擇網絡編碼算法進行編碼處理，本仿真中采用的網絡編碼算法都是二維結構，即均采用兩個編碼系數，在節點交匯處進行編碼，然后再轉發出去，仿真主要研究和比較延遲和吞吐量兩個QoS參數，仿真在QualNet 5.0下完成。

3.2 仿真結果及分析

本次仿真分別比較了優化網絡編碼（Optimal）、啟發式網絡編碼（Heuristic）、隨機性網絡編碼（Random）和確定性網絡編碼（Deterministic）四種網絡編碼算法在網絡吞吐量和延遲方面的表現。

圖2是四個算法在吞吐量方面的表現，由于優化編碼算法采取了優化策略，獲得的網絡吞吐量最大，而啟發式算法側重于速度的要求，網絡吞吐量較低。

圖2 網絡吞吐量比較

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

4.結論

本文分析了幾種網絡編碼中的常用算法，并對幾種編碼算法在提高QoS性能方面的表現進行了仿真研究，仿真表明優化算法在網絡吞吐量方面有良好的表現，而啟發式算法則在低延遲方面更具優勢。

圖3 網絡延遲的比較

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