基于P2P網絡的可靠網絡編碼多路徑協議研究

摘 要:網絡編碼能夠保證傳輸可靠性，同時也能夠降低數據冗余度，并且能夠在對等互聯網絡中能夠發揮重要作用，本文針對傳統的可靠多路徑路由協議進行改進，提出可靠網絡編碼多路徑協議(NC-RMPP)，并對該協議在對等互聯網絡中的性能進行了詳細的實驗分析。

關鍵詞:網絡編碼 對等互聯網絡 NC-RMPP

中圖分類號:TP393文獻標識碼:A文章編號:1674-098X(2011)10(c)-0013-02

1 引言

對等互聯網絡(Peer-to-peer Network，P2P)中的很多應用，如視頻對話、在線文件傳輸等，對通信可靠性和實時性有很高要求，在P2P網絡中，傳輸鏈路的穩定性無法始終保障，有時通信質量低下，網絡拓撲結構變化也較頻繁，網絡節點本身計算能力有限，P2P網絡中的數據傳輸可靠性保障一直是努力解決的難題[1]。

隨機網絡編碼算法作為一種分布式網絡編碼方式，在編碼時不需要知曉整個網絡拓撲結構就能進行編碼。隨機網絡編碼適用隨機的網絡結構，對于網絡節點和鏈路時常變化的P2P網絡，該算法可利用網絡的適時容量來獲得網絡的最佳通信容量。

2 網絡編碼可靠傳輸機制

針對無環多播圖G=(V，E)，源節點S∈V，接收節點，令h為源節點和接收節點的最小割，用head(e)和end(e)表示一條邊e的起點和終點，設g(e)為邊e對應的全局編碼向量，接收節點t的h條輸入邊e1，…，eh對應的輸符號為:

(1)

要使接收節點恢復出信源符號x1，…， xh，只要全局編碼向量g(e)組成的矩陣Gt滿秩。當編碼符號域足夠大時，可以隨機選擇局部編碼向量，使得Gt滿秩。根據文獻[2]，如果一個符號域的大小為216，網絡中邊數量至少是|E|=28，對任何接收者Gt將有0.996的概率滿秩。

3 網絡編碼性能分析

3.1 關鍵參數分析

本文采用完全隨機選取線性編碼系數的分布式網絡編碼方式，在隨機編碼策略下，對于所有除了接收節點外的節點，在一個足夠大的有限域上隨機選擇它們輸入鏈路到輸出鏈路的映射。可以將該信息作為信源信息向量進行傳遞，這種分布式的網絡編碼不需知道整個網絡的拓撲結構就可進行編碼。

編碼有限域Fq的選取:編碼有限域的取值范圍決定編碼系數的線性無關概率，進而影響到隨機線性碼的解碼性能。q在不同的取值下產生的編碼系數的線性無關概率如（表l）所示。

3.2 路徑數的理論分析

在可靠網絡編碼多路徑協議(Reliable Multi-Path Protocol Using Network Coding，NC-RMPP)中，每次轉發都要考慮局部可靠性，則要求每一個節點轉發的數據分組頭部都要有一個路徑數的參數，下面將分析NC-RMPP中源節點的路徑數計算。

源節點將m個原始報文編成一組然后編碼成n個大小相等的新報文。m和n的設置關系到解碼能力和能量開銷，如果m太小網絡編碼的優勢就不能得到充分發揮;m太大將會占用太多的存儲空間，這在P2P網絡中是不實際的，一般數據包不會大于200字節。

4 NC-RMPP路由實現

4.1 計算傳輸所需路徑數

在NC-RMPP模型中，只有源節點和匯聚節點，源節點通過中間節點轉發數據分組到達匯聚節點，中間節點隨機分布，中間節點將根據規則分成節點集，有利于下一跳選擇。NC-RMPP路由的關鍵是保證每一跳傳輸都滿足可靠性。

4.2 源節點發送數據

NC-RMPP算法要求源節點在發送數據前對數據進行編碼，考慮源節點所需要發送的數據報文，按照報文產生的先后順序，將每m個數據報文編為一組，記為X1，X2，…，Xm，并賦予相同的組標識，組標識從0開始遞增，直到增加到上限后歸零。

4.3 選擇下一跳節點和路徑數分配

根據源節點鄰居節點到匯聚節點之間的跳數，源節點把鄰居節點分為三類:與自己到匯聚節點跳數等同節點，比自己到匯聚節點跳數少1的節點，以及比自己到匯聚節點多1的節點;這三類節點分別用H0、H-、H+表示，為了保證所有選中的鄰居節點能提供發送數據的M條路徑，鄰居節點要創建一定的路徑數。假設三類節點集合中，分別有K0、K-、K+個節點選中，并且需要為源節點創建的路徑數為P0、P-、P+，則有(2)的結果:

(2)

5 算法性能分析

NC-RMPP協議考慮逐跳的可靠性傳輸，并在路由中加入網絡編碼，通過編碼運算將多個數據沿著多條路徑傳輸，并在接收端容錯分析后，該協議提高了數據傳輸可靠性，均衡網絡負載，提高網絡的容錯性，節省節點的能量消耗。下面通過Matlab和OMNET++仿真比較分析了NC-RMPP協議在可靠度、冗余度及能量消耗的性能。

5.1 實驗仿真平臺

使用OMNET++建立一個網絡模型的步驟分為網絡描述、消息定義、模塊實現、系統配置4個步驟。在OMNET++中，在OMNET++中對消息的建模是通過建立msg文件，在文件中用OMNET++提供的一種類似于C++的語言描述消息中所包括的域，為了適應新的網絡環境的變化，OMNET++提供了一種配置文件的機制。

5.2 可靠度和冗余度

相同路徑數下NC-RMPP路由的可靠度優于傳統多路徑路由，在一定可靠度下，采用網絡編碼機制后需要的路徑數少于傳統的多路徑路由所需路徑數，在路徑數為16條的時候NC-RMPP路由就能保證以95%的可靠度傳輸，此時傳統多路徑路由需24條才能保證同樣可靠度。NC-RMPP路由并不要保證每個數據包都正確接收，接收節點只需接收到部分編碼包就可以正確的恢復出源數據，因此隨著期望可靠度越高，這兩種機制下成功交付需要的路徑數相差就越大，NC-RMPP路由所需的路徑數也將大大降低。

NC-RMPP路由可靠性機制體現傳輸路徑數的減少，這是因為算法中采用了網絡編碼技術，對收到的數據包進行編碼運算，而且在接收端解碼時允許部分信息丟失。當然影響路徑數的因素有很多，包括信道出錯率、網絡跳數、編碼報文數等，下面圖1中分別考慮到幾個參數的影響。

從(圖1)中看出設定的可靠度為0.8，源節點到匯聚節點的跳數為6跳，原始報文4個編為一組的情況下，誤碼率增大，兩種方式傳輸需要的路徑數也增大，這種趨勢當誤碼率較高時尤為明顯。而在同等條件下，NC-RMPP路由保證一定可靠度的傳輸所需的路徑數要低;在誤碼率較高時相差的路徑數會更加大，NC-RMPP路由在誤碼率較高時更能發揮優勢。

6 結語

本文在研究網絡編碼性能基礎上，提出一種新的NC-RMPP路由協議，該算法是基于網絡編碼的可靠多路徑路由協議，重點研究算法的設計實現過程，并通過定量定性分析該算法在P2P網絡上的性能優勢，不僅能夠提高數據傳輸可靠性，均衡負載，提高容錯性，通過減少數據傳輸路徑數，還大大降低了節點功耗，實現節能高效的新型可靠多路徑路由協議。

參考文獻

[1] Sen S，Wang J.Analyzing peer-to-peer traffic across large networks[J].IEEE/ACM Transactions on Networking，2004，12(2): 219～232.

[2] Philip A.Chou，Yunnan Wu，Kamal Jain.Practical network coding[C].In: 41st Annua Allerton Conference on Communication Control and Computing， Oct.2003，115～124.

[3] 楊林，鄭剛.一種集成網絡編碼的低軌衛星網絡多徑路由算法[J].中南大學學報(自然科學版)，2007，38(5):950～955.

[4] 張晶晶，何榮希，陳玉飛.無線傳感器網絡多徑路由協議綜述[J].計算機工程與設計，2007，28(22):5417～5419．

①作者簡介:管永剛(1984-)，男，本科，2006年畢業于淮陰工學院機械設計制造及其自動化專業，現工作于江蘇淮陰工學院人事處，助教職稱。