基于P2P網(wǎng)絡的可靠網(wǎng)絡編碼多路徑協(xié)議研究

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

關鍵詞:網(wǎng)絡編碼 對等互聯(lián)網(wǎng)絡 NC-RMPP

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

1 引言

對等互聯(lián)網(wǎng)絡(Peer-to-peer Network，P2P)中的很多應用，如視頻對話、在線文件傳輸?shù)龋瑢νㄐ趴煽啃院蛯崟r性有很高要求，在P2P網(wǎng)絡中，傳輸鏈路的穩(wěn)定性無法始終保障，有時通信質量低下，網(wǎng)絡拓撲結構變化也較頻繁，網(wǎng)絡節(jié)點本身計算能力有限，P2P網(wǎng)絡中的數(shù)據(jù)傳輸可靠性保障一直是努力解決的難題[1]。

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

2 網(wǎng)絡編碼可靠傳輸機制

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

(1)

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

3 網(wǎng)絡編碼性能分析

3.1 關鍵參數(shù)分析

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

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

3.2 路徑數(shù)的理論分析

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

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

4 NC-RMPP路由實現(xiàn)

4.1 計算傳輸所需路徑數(shù)

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

4.2 源節(jié)點發(fā)送數(shù)據(jù)

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

4.3 選擇下一跳節(jié)點和路徑數(shù)分配

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

(2)

5 算法性能分析

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

5.1 實驗仿真平臺

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

5.2 可靠度和冗余度

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

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

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

6 結語

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

參考文獻

[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] 楊林，鄭剛.一種集成網(wǎng)絡編碼的低軌衛(wèi)星網(wǎng)絡多徑路由算法[J].中南大學學報(自然科學版)，2007，38(5):950～955.

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

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