抗擾動移動對等覆蓋網的構建及性能評價

李軍，張國印，王向輝

(1.哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001;2.安慶師范學院 數學與計算科學學院，安徽 安慶246133)

隨著手機的普及以及平板電腦、智能手機等移動互聯網絡終端設備的流行，在移動網絡中應用P2P技術開始得到重視。由于移動網絡的特殊性，使得互聯網上的很多成熟技術無法直接應用于移動網絡。因此，移動對等網絡的研究還主要集中在核心機制研究上。在移動對等網絡的諸多問題中，覆蓋網的構造是一個關鍵性的問題。覆蓋網的結構直接決定了移動P2P系統的可擴展性、魯棒性、安全性和抗擾動性。在面向移動自組網的移動對等覆蓋網構造算法中，使用跨層方法的占了絕大多數［1-4］。該方法能夠提高查詢成功率，涉及到具體的網絡層路由協議和MAC層協議，通用性較差。原型改進方法能夠應用于不同的底層網絡，可以利用原有相對比較成熟的路由協議、資源查詢算法等，并方便移動對等網絡和傳統P2P網絡的互聯［5-8］。但這種方法必然要遵循已有的框架進行改造，從而限制了算法的改進范圍。利用博弈論的方法是通過定義一個節點間的博弈來構建一個達到預期目標的覆蓋網，生成的覆蓋網對于預期目標來說能夠接近最優，但不是十分穩定，對于擾動的適應性也較差［9-10］。本文為了構建高效抗擾動的移動對等覆蓋網，首先提出了一個基于k-派系社區結構的網絡拓撲并設計了多種抗擾動機制，然后對其數據分發機制進行了研究，通過動態調整不同節點的數據分發概率來提高數據分發效率，最后提出了一個三維的移動對等覆蓋網性能評估模型，并根據這一模型對多個覆蓋網進行了性能評估。

1 基于k-派系的網絡拓撲結構

針對復雜網絡中社區結構的檢測和發現已經提出了多種算法，但對于社區結構的構造算法還較少見。通過構建具有k-派系社區結構的覆蓋網，可以保證該網絡具有較高的聚集系數和較短的平均路徑長度，從而使其表現出小世界特征［11-12］。

每一個節點在加入覆蓋網時進行初始化，其數據結構包括跳數值、初始狀態值、動態狀態值等，并建立3個空列表，第1個是鄰居節點列表，第2個是資源共享索引列表，最后一個是外聯節點列表。其中，最先加入網絡的節點稱之為中心節點，跳數為0，鄰居節點列表中包含其他派系節點的節點稱之為外聯節點。根據自身的處理能力和網絡帶寬等情況計算節點初始狀態值S:

式中:c為節點運算能力值，m為節點存儲能力值，d為節點當前電量，b為節點當前網絡帶寬，α、β、γ、δ為權值，α+β+γ=1，0≤S＜1。

計算節點的動態狀態值Sr:

式中:j為節點跳數。

每個節點只屬于一個k-派系。基于k-派系社區結構的覆蓋網結構示意圖如圖1所示。

圖1 基于k-派系的移動對等覆蓋網拓撲結構圖Fig.1 Topology of k-clique based mobile P2P overlay

圖1中1～10號節點由1個3-派系組成，11至17號節點構成了一個2-派系。黑色節點為中心節點，灰色節點為外聯節點。實線表示派系節點內鏈接，虛線表示相鄰派系節點間鏈接。

2 抗擾動機制

本文提出的移動對等覆蓋網絡首先采取數據冗余策略，將單個節點的資源索引列表復制給同派系的多個節點進行存儲，從而降低單個節點失效給系統造成的影響。過度數據冗余或者不當的數據復制策略，有可能造成系統崩潰，尤其對于移動網絡節點來說，網絡帶寬在很多情況下無法支持大量數據進行節點間的復制。為此，本文提出了適合移動網絡的數據分發機制，并在特定范圍內對資源索引列表而不是資源本身進行復制，以降低網絡負載。

其次，采用路由表修復技術來保證路由的有效性。采用心跳機制周期性地探測鄰居節點，當節點心跳數在規定時間內不再增加時即判定其已經失效，從而主動發現失效節點并修復路由表。

最后，采用拓撲結構自適應來提高抗擾動能力。當某個節點退出或失效時，覆蓋網網絡拓撲自動進行修改，從而提高網絡的抗擾動能力。同時，通過主動外聯過程和被動外聯過程保持本派系節點與其他派系的鏈接，確保網絡的連通性。

3 性能評價模型

擾動情況下移動對等覆蓋網的性能評估可以通過本文提出的三維評價模型來進行。該模型中的第1個維度包含移動對等覆蓋網中影響擾動的直接因素，主要指擾動模型及其參數，擾動模型有指數分布擾動模型、重尾分布擾動模型、Pareto分布擾動模型、KAD擾動模型等;第2個維度包含移動對等覆蓋網中影響擾動的間接因素，如節點的數量、節點的移動速度和節點的移動模型等。節點的移動模型可分為個體移動模型和群體移動模型，個體移動模型中使用最多的是隨機路點移動模型;最后一個維度主要包含擾動情況下移動對等覆蓋網的性能評價指標，如資源查找成功率、資源平均查詢時間和網絡負載等。

4 性能評估實驗

為了驗證本文提出的覆蓋網在移動網絡中的性能，在Peerfactsim模擬器［14］上對該網絡進行模擬，并命名為KCCO(k-clique community overlay)。Peerfactsim模擬器是德國大學達姆施塔特技術大學利用Java語言開發的開源P2P網絡模擬實驗平臺，具有通過離散事件觸發的特點。實驗中通過設定節點擾動模型來模擬網絡的擾動情況，并改變節點數目和節點平均移動速度等參數來得到覆蓋網的查詢成功率和平均查詢時間。

4.1 模擬實驗設置

底層網絡采用移動自組網，節點活動面積為1 000 m×1 000 m。每個節點的無線傳輸距離設置為240 m，信道容量設為2 Mb/s，節點的移動模型采用隨機路點移動模型，節點的移動速度設置為1～10 m/s。節點擾動模型設為指數擾動模型。節點資源分布模型為zipf分布，系數設為0.7。

為了評估擾動情況下移動對等覆蓋網的性能，本文選擇了另外2種覆蓋網進行對比。其中一個是GIA，它為了提高Gnutella的可擴展性，通過滿意度參數使有更高能力的節點接受更多的鄰居節點和查詢請求，實現負載均衡并提高查找效率［13］;另一個覆蓋網M-GIA是專為移動網絡設計的改進GIA模型，它改變了節點ID的生成規則并增加了位置信息，通過節點ID來計算2個節點之間的距離［1］。M-GIA中的每一個節點根據滿意度和與請求節點的距離來共同決定是否接受一個新的鄰居節點。

實驗中所評估的3種覆蓋網具有一部分共同的參數，其參數名稱及參數值如表1所示。此外，MGIA中的權值α和β分別設為0.5和0.5。KCCO中每一個k-派系的k值都設為5。

表1GIA、M-GIA、KCCO共同實驗參數配置表Table 1 GIA，M-GIA，and KCCO's common experimental parameter settings

4.2 模擬實驗結果

指數擾動模型的一個主要參數是平均會話時長，默認值設為60 min。對于3種覆蓋網來說，默認的網絡節點數是600個，默認的平均節點移動速度是6 m/s。接下來通過改變上述3個參數中的任意一個參數，而將其他2個參數設為默認值的方法來評估3種覆蓋網的性能。

首先將平均會話時長設為60 min，平均節點移動速度設為6 m/s，將節點數目從200增加到1 000分別進行模擬實驗，實驗結果如圖2所示。從圖2可以看出，當節點數量少于800時，KCCO具有最短的平均查詢時間，但是當節點數超過800時，它成了耗時最長的一個。M-GIA在節點數目較少的情況下平均查詢時間高于GIA，但隨著節點數目的增加，其平均查詢時間逐漸接近并最終低于GIA。

圖2 不同節點數目下的平均查詢時間Fig.2 Average query delay with different numbers of nodes

在不同節點數目下的查詢成功率如圖3所示。無論節點數量是多少，與其他2種網絡相比，KCCO均能取得較高的查詢成功率，始終保持在其他2種覆蓋網的一倍以上。當節點數少于600時，M-GIA比GIA取得了更高的查詢成功率。隨著節點數量的增長，3種覆蓋網均表現出平均查詢時間增長而查詢成功率下降的情況。

圖3 不同節點數目下的查詢成功率Fig.3 Query success rate with different numbers of nodes

其次將平均會話時長設為60 min，節點數目設為600，將節點平均移動速度從1 m/s增加到10 m/s分別進行模擬實驗，實驗結果如圖4所示。

圖4 不同節點移動速度下的平均查詢時間Fig.4 Average query delay with different moving speeds of nodes

KCCO的平均查詢時間最短，隨著節點移動速度的增加有所增加。當節點平均移動速度較慢時，GIA要好于M-GIA，反之則不如M-GIA。不同節點平均移動速度下的查詢成功率如圖5所示。KCCO的查詢成功率始終遠遠高于其他2種覆蓋網，當節點移動速度較高時略有下降。M-GIA和GIA各有優劣，多數情況下M-GIA的查詢成功率略高于GIA。

圖5 不同節點移動速度下的查詢成功率Fig.5 Query success rate with different moving speeds of nodes

最后將節點數目設為600，節點移動速度設為6 m/s，將平均會話時長從6 min增加到60 min分別進行模擬實驗。不同平均會話時長下的平均查詢時間如圖6所示。隨著平均會話時長的增長，3種網絡的平均查詢時間反而增加。M-GIA的平均查詢時間在絕大多數情況下都是最長的。

圖6 不同平均會話時長下的平均查詢時間Fig.6 Average query delay with different mean session lengths

不同平均會話時長下的查詢成功率如圖7所示。當網絡的平均會話時長延長時，KCCO的查詢成功率快速增加，而其他2種覆蓋網的查詢成功率基本保持不變，KCCO在擾動劇烈的情況下仍然保持了較高的查詢成功率。

圖7 不同平均會話時長下的查詢成功率Fig.7 Query success rate with different mean session lengths

4.3 實驗結果評價

3種覆蓋網在所有情況下的平均查詢時間相差不是很大，GIA與M-GIA在所有情況下的查詢成功率比較相近。表2和表3為3種覆蓋網在不同參數下的平均查詢時間和查詢成功率的比較?？梢钥吹終CCO的平均查詢時間是最短的，M-GIA的平均查詢時間最長。KCCO的查詢成功率明顯高于其他2種覆蓋網，M-GIA的查詢成功率在節點數目變化時高于GIA。

表2 3種對等覆蓋網在不同參數下的平均查詢時間比較Table 2 Average query delay comparison of three overlays

表3 3種對等覆蓋網在不同參數下的查詢成功率比較Table 3 Query success rate comparison of three overlays

5 結束語

本文提出了一種基于k-派系社區結構的移動對等覆蓋網KCCO，通過構造一個具有多個不同k-派系結構的網絡拓撲，并結合數據冗余、主動路由修復和拓撲結構自適應等多種機制來提高覆蓋網的性能，增強抗擾動能力。提出一種三維的移動對等覆蓋網性能評估模型，包含了移動性和擾動性等多個移動對等網絡的特性，并在此基礎上對多個覆蓋網在擾動情況下移動網絡中的性能進行了比較分析。評估結果顯示，本文提出的移動對等覆蓋網KCCO在擾動情況下顯著提高了資源查詢成功率，縮短了平均查詢時間。

［1］HAN D D，ZHANG J.An optimized Gnutella-like P2P protocol in mobile networks［J］.Journal of Networks，2012，7(9):1464-1471.

［2］彭利民，肖文俊.一種具有常數度的無線P2P覆蓋網［J］.四川大學學報:工程科學版，2011，43(4):124-130.PENG Limin，XIAO Wenjun.A wireless P2P overlay network with constant degree［J］.Journal of Sichuan University:Engineering Science Edition，2011，43(4):124-130.

［3］MEI Jingqing，JI Hong，LI Yi.Query routing mismatch alleviation architecture for P2P file lookup in MANETs［J］.The Journal of China Universities of Posts and Telecommuni-cations，2011，18(4):111-117.

［4］ZHOU Hui，YANG Jie.Spiralchord:a space-filling curve based location awareness，cross-layering P2P file sharing system in WMNs［J］.The Journal of China Universities of Posts and Telecommunications，2012，19(3):44-53.

［5］GOUVAS P，BOURAS T.Ubi-chord:services provision in dynamic networks based on P2P protocols［C］//18th International Conference on Telecommunications.Ayia Napa，Cyprus，2011:375-380.

［6］MARIEM T，NAHIL T，TAREK B，et al.Enhanced backtracking Chord protocol for mobile Ad hoc networks［C］//International Conference on Communications and Information Technology.Hammamet，Tunisia，2012:191-195.

［7］CHANG Jianming，LIN Yihsuan，ISAAC Woungang，et al.MR-Chord:a scheme for enhancing Chord lookup accuracy and performance in mobile P2P network［C］//IEEE International Conference on Communications.Ottawa，Canada，2012:5408-5412.

［8］ZULHASNINE M，HUANG Changcheng，SRINIVASAN A.Towards an effective integration of cellular users to the structured peer-to-peer network［J］.Peer-to-Peer Networking and Applications，2012，5(2):178-192.

［9］MAWJI A，HASSANEIN H.P2P overlay topology control in MANETs［C］//IEEE International Symposium on A World of Wireless，Mobile and Multimedia Networks.Montreal，Canada，2010:1-9.

［10］MAWJI A，HASSANEIN H，ZHANG X Y.Peer-to-peer overlay topology control for mobile ad hoc networks［J］.Pervasive and Mobile Computing，2011，7(4):467-478.

［11］LUCE R D，PERRY A D.A method of matrix analysis of group structure［J］.Psychometrika，1949，14(2):95-116.

［12］LUCE R D.Connectivity and generalized cliques in sociometric group structure［J］.Psychometrika，1950，15(2):169-190.

［13］YATIN C，SYLVIA R，LEE B，et al.Making gnutellalike P2P systems scalable［C］//Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications.Karlsruhe，Germany，2003:407-418.

［14］DOMINIK S，CHRISTIAN G，JULIUS R，et al.PeerfactSim.KOM:a simulation framework for peer-to-peer systems［C］//The 2011 International Conference on High Performance Computing and Simulation.Istanbul，Turkey，2011:577-584.