移動P2P中多次網絡編碼反饋調節方案

張國印，樊旭，高偉，王向輝

(哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001)

隨著無線通信技術的迅速發展和移動終端處理能力的逐漸增強，為滿足日益增大的移動網絡信息服務需求，出現了結合移動網絡環境與P2P系統的移動對等網絡(mobile peer-to-peer network，MP2P)［1］。移動網絡具有網絡拓撲結構不斷變化及節點自身資源受限的特點，如何實現高效、穩定的數據分發成為MP2P網絡領域的重要研究內容［2］.

多跳網絡拓撲結構與異步分塊數據分發機制可有效抵制MP2P網絡節點的快速移動與頻繁的加入退出所帶來的數據塊分布不斷變化［3］。異步分塊數據分發方案無須在源節點與接收節點間建立直接連接，源節點只需將數據片段緩存給中間節點，接收節點再從中間節點下載請求的數據。但數據分塊在降低網絡擾動帶來負面影響的同時也帶來稀缺數據問題。

隨機網絡編碼中，中間節點不僅可以進行存儲轉發操作還可以用隨機生成的編碼向量對收到的數據進行線性組合，隨機網絡編碼最大化了有向無環網絡中組播會話的網絡信息流速率［4］。由于編碼過程混合了不同數據流使數據間差異變小，因此網絡編碼技術在提高網絡吞吐量的同時又可以改善稀缺數據帶來的負面影響，已被廣泛的應用于移動網絡或P2P系統中［5-7］。王蕾等將改進的部分網絡編碼方案應用于無線傳感器網絡中用來提高網絡效率并減少能量消耗［5］;GUO B等提出了多跳網絡中節點的編碼條件，并以此找出信源和信宿節點之間的潛在路徑和潛在網絡編碼機會［6］。LI Baochun等的研究表明在P2P系統中應用網絡編碼會對網絡各方面性能均有提升［7］。

移動P2P拓撲的不斷變化增加了下載節點的請求次數，現有的移動網絡采用完全的網絡編碼方案對數據進行單次編碼，每一次網絡編碼操作均將多個源數據塊編碼成一個編碼塊，因此單次編碼不可避免地減少了流經編碼節點的線性無關數據的數量，所以在移動P2P這種高動態網絡環境中會增加網絡延遲。在移動對等網絡分層的網絡結構的基礎上提出了一種多次網絡編碼反饋調節(feedback adjustment for multiple network coding，FAMNC)數據傳輸方案。

1 多次網絡編碼

1.1 網絡編碼過程

設單源組播網絡用有向無環圖G=(V，E)表示，其中V為節點集，E?V×V×Z為有向邊集。s∈V為源節點，T?V為宿點集，T={t1，t2，…，tN}。節點v∈V的輸入信道集為ΓIn(v)={d:head(d)=v}，輸出信道集為ΓOut(v)={e:tail(e)=v}，其中d，e∈E。

在P2P文件分發系統中，源節點將大小為F字節的文件廣播給每一個參與節點。源節點在廣播前將文件分割成M塊，每塊的大小為k=F/Mbyte。參與文件分發的節點被隨機的組織成一個對等覆蓋網進行數據塊交換。每個節點與周圍一定數量的節點建立連接，稱這些節點為鄰居。假設每個節點建立連接的鄰居節點數滿足統一分布，并可以隨著時間改變。數據傳輸只發生在節點與其鄰居節點之間。

應用基于分段的網絡編碼中，初始的M個數據塊被劃分成G段，每段包含m塊，稱為段大小。僅對段內數據塊應用隨機線性網絡編碼。假設第i段有原始塊，那么從這個段得到的一個編碼塊b是在有限域GF(2q)上的線性組合。編碼操作并不限于源節點，如果一個節點(包括源節點)有第i段中的l(l≤m)個編碼塊，當這個節點向其他節點傳輸數據時，它在GF(2q)隨機地選擇一組數構成局部編碼向量，并對它所擁有的第i段內的所有數據塊進行編碼，生成大小仍為k字節的編碼塊x，x=編碼原始數據塊生成x的全局編碼向量嵌在每一個編碼塊的頭部。只要一個節點收到第i段中的m個線性無關的編碼塊，便可利用高斯消去法將第i段解碼。

1.2 多次網絡編碼

下載節點所接收到的同一段內線性無關的編碼塊的數量決定了節點能否對該段解碼，鄰居節點間交換編碼塊的速度決定了節點的下載時間。為增加編碼機會，編碼節點在進行編碼操作之前會進行等待，只有在節點緩存區數據量滿足一定條件時才會進行編碼。等待編碼的過程對已有數據進行重復編碼提供了機會，為了增加編碼節點下游網絡中數據量，減少下載時間，所以在已有單次編碼基礎上提出多次網絡編碼。

定義1 基于分段的網絡編碼中，編碼節點v∈V隨機生成k組局部編碼向量m1，m2，…，mk，將已有的l個屬于同一代的數據塊，編碼成k(2≤k＜l)個線性無關的編碼塊轉發給下游節點的過程稱為多次網絡編碼。

由定義1，編碼節點v生成k組局部編碼向量，對收到的數據進行多次編碼，因此有

定理1 節點v的下游節點集Λout(v)中，若存在i(i＞2) 個節點v1，v2，…，vi滿足c(vi)＜h，則節點v進行多次網絡編碼可減少轉發次數。

證明:若存在節點vi∈Λout(v)，使得c(vi)＜h，則其上游節點必須多次轉發數據vi才能達到解碼條件，且轉發次數不小于h－c(vi)。

不采用多次網絡編碼時，當Λout(v)中有i個節點滿足c(vi)＜h時，其上游節點要轉發次數 α∈

多次網絡編碼節點生成的編碼塊線性無關，因此轉發 β=max{h－c(vi)}次可使vi達到解碼條件，因此α＞β。

2 MNC反饋調節方案

2.1 編碼節點模型

為實現不同網絡狀態下編碼方案的轉換，本文采用的編碼節點模型如圖1所示，該圖所表示的是三輸入單輸出編碼節點。圖中實線代表數據傳輸鏈路，是上游節點發送給下游節點的通路。虛線代表控制信息鏈路，是超級節點與編碼節點進行信息交換與調節控制的通路。3個數據緩存區b1、b2、b3分別存儲對應輸入鏈路發送來的數據塊。用⊕表示網絡編碼操作，此處雖然用⊕表示操作但并不意味著必須使用異或方式進行編碼，可使用任一種滿足假設的編碼方案。b0表示輸出緩存，用于存儲待發送的編碼數據塊。

圖1 編碼節點模型Fig.1 Model of encoding node

2.2 網絡模型

網絡拓撲結構是提高內容分發效率的基礎，網絡結構是否合理將會直接影響網絡效率。常見P2P網絡模型有3種:集中式P2P網絡模型、純P2P網絡模型和分層式P2P網絡模型。對具有高動態性的移動網絡而言，松散的非結構化網絡框架設計會降低信息傳輸的準確率;而結構化的框架設計又會因節點頻繁的加入、離開導致巨大的路由更新開銷。分層式P2P網絡模型結合了前2種模型的優點，對整個移動P2P網絡結構的設計和節點處理能力的分配都進行了優化。本文將移動網絡中的節點劃分為由超級節點層與普通節點層組成的2層網絡，以超級節點為中心將網絡劃分為多個子網，各子網相對獨立，當節點動態加入網絡、完成下載或者能量耗盡動態離開網絡時，只對其所在子網的路由表有影響，不會對其他子網產生影響。

用計算能力(C)、內存大小(M)、剩余能量(P)、在網時間(T)4項指標表示將節點的綜合能力(A)，記A=α1C+α2M+α3P+α4T，其中。根據A值的大小將節點分為超級節點Si和普通節點層中的轉發節點Oi與編碼節點Ci。

超級節點負責子網內成員的管理和子網間的查詢任務，在資源共享方面所有節點地位相同，超級節點上存儲了同一子網內其他節點的信息，當請求在同子網節點間得不到響應時，發現算法會在超級節點之間轉發請求，超級節點再將查詢請求轉發給適當的普通節點，這樣在超級節點之間就構成了一個高速轉發層。編碼節點主要是對接收到的數據塊進行編碼，增加系統中編碼塊的分布，從而促進塊的多樣性，避免稀缺塊問題。轉發節點負責網絡中數據的存儲及轉發。普通節點層不區分普通節點與編碼節點，默認為普通節點為進行0次編碼的編碼節點，即超級節點調節普通節點的編碼次數由0到多次。

當有新的節點動態加入網絡時，可以先按請求資源的類型進行分類查找，即找到含有這類資源的最近的超級節點，然后加入該超級節點所管理的子網，并隨即選擇其鄰居節點，超級節點也會根據新加入節點的信息更新其管理的路由表。當網絡中的節點由于完成下載任務或者生存期耗盡而離開網絡時，超級節點會通知其鄰居節點，并更新其路由表。

2.3 反饋調節方案

移動P2P網絡中的編碼節點不能及時獲得鄰居節點的詳細情況，所以無法確定恰當的編碼次數。過多或過少的編碼次數都會因增加能量消耗或增加轉發次數而降低網絡效率。為使編碼節點選擇適當的編碼次數，采用反饋機制對節點的編碼狀態進行即時調節。編碼節點與接收節點將運行情況反饋給超級節點，超級節點做出判斷，對編碼節點所采用的編碼方案進行調整，保證整個系統處于最優狀態。編碼節點數據處理流程如圖2所示。此外，轉發節點和編碼節點之間的轉化與節點編碼次數是由超級節點觸發的，超級節點會周期性的檢查子網內節點的狀態，當數據分發效率較低時，就會選擇性能較強的普通節點轉化為編碼節點。

定義2 網絡中編碼節點v執行編碼操作次數與收到的數據塊總數的比值稱為該節點的編碼容忍率，記為，全局編碼容忍率則記為

圖2 編碼節點信息處理流程Fig.2 Data processing flow of encoding node

定義3 網絡中下載節點成功下載網絡中數據塊的次數與請求下載數據塊總數的比值稱為成功請求率，記為

定理2 成功請求率與編碼容忍率成負相關。

證明:節點成功接收到的數據塊總量由發送次數與接收節點數量決定，即

由式(1)、(3)可以得出:

由式(2)、(4)可以得出:

由式(5)可以得出結論:在其他條件不變的情況下，編碼容忍率降低則網絡的成功請求率升高，反之，編碼容忍率升高則網絡的成功請求率降低。

定理3 采用負反饋調節機制可以使成功請求率D在閾值D0附近一個狹小范圍內變動，且當D=D0時，方案傳輸延遲最低。

證明:基于FAMNC的循環性，當網絡中成功請求率D≥D0時，將減少編碼次數。一旦成功請求率D≤D0時，將增加編碼次數。循環執行一段時間后，網絡中塊的分布將達到相對穩定且均衡的狀態，成功請求率D在閾值D0附近一個狹小范圍內變動，并且全網轉發次數最少。

下面證明當D=D0時，方案傳輸延遲最低。在數據分發系統中采用網絡編碼方法，方案傳輸延遲包括請求延遲與編碼延遲2部分。

請求延遲為分發率的函數DR=f(D)且，編碼延遲為編碼容忍率的函數DC=g(R)且，根據定理2可知

因此，隨著網絡中編碼次數的增加，成功請求率D會得到提高，反之成功請求會降低。而網絡編碼次數的增加會帶來更多的傳輸延遲，因此隨著成功請求率D的提高，傳輸延遲也會增加。

根據定理2、3可以構建負反饋模型。調節功能因子T設計為

反饋調節的多次網絡編碼策略可具體描述如下:

1)設成功請求率理想閾值為D0。

2)初始狀態下，全部節點均處于單次編碼狀態，則可以根據式(2)計算網絡中的成功請求率D。

當實際成功請求率較低時即D≤D0，此時，網絡中數據請求成功率過低。子網內接收數據量較多且沒有進行多次編碼節點將被超級節點開啟多次編碼功能，超級節點增加子網內節點的編碼次數，子網內線性響應請求數據量升高，網絡的成功請求率將升高。

當實際成功請求率較高時即D≥D0，此時，網絡中節點編碼次數過高。超級節點降低子網內編碼次數過多節點的編碼次數，網絡的成功請求率將降低。

3 仿真實驗與結果分析

為驗證本文提出的方案在移動P2P中的性能，通過Matlab實現了一個由離散事件驅動的實驗環境并與分段網絡編碼方案和基準方案泛洪(flooding)方案進行性能比較。3種方案均采用同步方式運行，通過最常用的統計數據分發所需的周期數的方法來評價不同方案的下載時間。只對比方案的數據分發效率而不考慮其他代價是不全面的，因此本文進一步比較了不同方案所產生的能量消耗。

3.1 數據分發效率

3種方案均在網絡層進行操作，因此忽略鏈路層和物理層的實現細節，覆蓋層為分層的移動P2P。節點數定為200。節點移動模型為 Random Waypoint［8］。部分實驗參數如表1所示。

本文提出的FAMNC方案，與NC方案與Flooding方案的數據分發時間對比曲線如圖3所示。

從圖3可知，3種方案數據分發進度基本保持線性增長趨勢。Flooding方案初期效率明顯，中期穩定，后期速度有放緩趨勢。FAMNC在整個數據分發過程基本保持一定分發速率，網絡擾動對其影響不大;最終完成數據分發的時間比Flooding方案稍長。NC方案一開始就明顯慢于Flooding方案與FAMNC方案，在數據分發完成50%后又受網絡擾動影響，分發效率再次減緩。

表1 仿真參數Table 1 Simulation parameters

圖3 數據分發效率對比Fig.3 Data distribution rate comparison

3.2 能量消耗

本節通過統計來比較3種方案所帶來的能量消耗。設定節點發送功率為0.6 W，接收0.2 W，編碼功率為0.05 W［9-10］，其余實驗參數與表1參數值相同。參量消耗對比圖如圖4所示。

圖4 能量消耗對比Fig.4 Energy consumption comparison

從圖4可知，3種方案所帶來的能量消耗差異明顯。NC方案能量消耗前期增長緩慢，穩定狀態能量消耗較低。FAMNC方案前期增長迅速，并以較大的波動穩定在均值，比NC方案略低處。Flooding方案快速達到穩定狀態，以較小的波動在高能量消耗狀態進行數據分發。

3.3 實驗分析

綜合對比數據分發率與能量消耗2個方面的實驗結果可以看出，FAMNC方案在移動P2P數據分發中表現出了良好的性能。以低于Flooding方案15%左右的能量消耗達到了相接近的數據分發效率。由于FAMNC是在網絡編碼的基礎上進行的改進，使數據塊間的線性相關概率極低，保證了每次轉發的有效性。而Flooding方案的轉發方式使鄰居節點間存儲了大量的線性相關的數據塊，導致后期無法進行有效的數據交換。

此外，FAMNC方案的數據分發效率與能量消耗兩個指標均優于NC方案。NC方案中編碼節點沒有根據網絡狀態做出相應的調節，而是以固定的方式進行單次編碼，浪費了為下游節點提供更多數據的機會，降低了網絡整體的數據分發速度。

4 結束語

為提高移動對等網數據分發效率，提出了FAMNC數據分發方案。該方案通過超級節點分析反饋信息，實現對編碼節點的調控。實驗結果表明，在相同的網絡環境，FAMNC方案的數據分發效率明優于NC方案，接近了Flooding方案的分發效率。FAMNC的能量消耗始終低于Flooding方案，并略優于現有NC方案。在以后的研究中，需要考慮編碼節點間的配合以減少重復編碼現象，進一步降低能量消耗。

［1］歐中洪，宋美娜，戰曉蘇，等.移動對等網關鍵技術［J］.軟件學報，2008，19(2):404-418.OU Zhonghong，SONG Meina，ZHAN Xiaosu，et al.Key techniques for mobile peer-to-peer networks［J］.Journal of Software，2008，19(2):404-418.

［2］李偉，徐正全，楊鑄.應用于移動互聯網的peer-to-peer關鍵技術［J］.軟件學報，2009，20(8):2199-2213.LI Wei，XU Zhengquan，YANG Zhu.Peer-to-peer key technologies in mobile internet［J］.Journal of Software，2009，20(8):2199-2213.

［3］賈美娟，郭方方，王慧強，等.分層超級節點的MP2P資源分發［J］.哈爾濱工程大學學報，2012，33(10):1278-1282.JIA Meijuan，GUO Fangfang，WANG Huiqiang，et al.MP2P resource distribution of a layered super node［J］.Journal of Harbin Engineering University，2012，33(10):1278-1282.

［4］HO T，MEDARD M，SHI J，et al.On randomized network coding［C］//41st Annu Allerton Conf Communication，Control，and Computing.Monticello，USA，2005:1-10.

［5］王蕾，張國印，馬春光，等.傳感網絡中以能量為中心的部分網絡編碼方案［J］.北京郵電大學學報，2012，35(4):107-111.WANG Lei，ZHANG Guoyin，MA Ghunguang，et al.Partial network coding scheme based on energy in WSN［J］.Journal of Beijing University of Posts and Telecommunications，2012，35(4):107-111.

［6］GOU B，LI H.Analysis of general network coding conditions and design of a free-ride orienter routing mertid［J］.IEEE Transactions on Vehicular Technology，2011，60(4):1714-1727.

［7］LI Baochun，NIU Di.Random network coding in peer-topeer networks:from theory to practice［J］.Proceedings of the IEEE，2011，99(3):513-523.

［8］JOHNSON D B，MALTZ D A.Dynamic source routing in Ad Hoc wireless networks［J］.Mobile Computing，1996，353:153-181.

［9］TAI H T，CHONG E T，SEI P L.Maximum energy level Ad Hoc distance vector scheme for energy efficient Ad Hoc networks routing［C］//IEEE 9th Malaysia International Conference on Communications.Kuala Lumpur，Malaysia，2009:423-428.

［10］XIAO Keyin，ZHANG Yide，FENG Gang，et al.eCOPE:energy efficient network coding scheme in multi-rate wireless networks［C］//IEEE Wireless Communications and Networking Conference.Shanghai，China，2013:18-23.