抗擾動移動對等覆蓋網(wǎng)的構(gòu)建及性能評價

李軍，張國印，王向輝

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

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

1 基于k-派系的網(wǎng)絡拓撲結(jié)構(gòu)

針對復雜網(wǎng)絡中社區(qū)結(jié)構(gòu)的檢測和發(fā)現(xiàn)已經(jīng)提出了多種算法，但對于社區(qū)結(jié)構(gòu)的構(gòu)造算法還較少見。通過構(gòu)建具有k-派系社區(qū)結(jié)構(gòu)的覆蓋網(wǎng)，可以保證該網(wǎng)絡具有較高的聚集系數(shù)和較短的平均路徑長度，從而使其表現(xiàn)出小世界特征［11-12］。

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

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

計算節(jié)點的動態(tài)狀態(tài)值Sr:

式中:j為節(jié)點跳數(shù)。

每個節(jié)點只屬于一個k-派系。基于k-派系社區(qū)結(jié)構(gòu)的覆蓋網(wǎng)結(jié)構(gòu)示意圖如圖1所示。

圖1 基于k-派系的移動對等覆蓋網(wǎng)拓撲結(jié)構(gòu)圖Fig.1 Topology of k-clique based mobile P2P overlay

圖1中1～10號節(jié)點由1個3-派系組成，11至17號節(jié)點構(gòu)成了一個2-派系。黑色節(jié)點為中心節(jié)點，灰色節(jié)點為外聯(lián)節(jié)點。實線表示派系節(jié)點內(nèi)鏈接，虛線表示相鄰派系節(jié)點間鏈接。

2 抗擾動機制

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

其次，采用路由表修復技術(shù)來保證路由的有效性。采用心跳機制周期性地探測鄰居節(jié)點，當節(jié)點心跳數(shù)在規(guī)定時間內(nèi)不再增加時即判定其已經(jīng)失效，從而主動發(fā)現(xiàn)失效節(jié)點并修復路由表。

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

3 性能評價模型

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

4 性能評估實驗

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

4.1 模擬實驗設置

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

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

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

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

4.2 模擬實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 實驗結(jié)果評價

3種覆蓋網(wǎng)在所有情況下的平均查詢時間相差不是很大，GIA與M-GIA在所有情況下的查詢成功率比較相近。表2和表3為3種覆蓋網(wǎng)在不同參數(shù)下的平均查詢時間和查詢成功率的比較。可以看到KCCO的平均查詢時間是最短的，M-GIA的平均查詢時間最長。KCCO的查詢成功率明顯高于其他2種覆蓋網(wǎng)，M-GIA的查詢成功率在節(jié)點數(shù)目變化時高于GIA。

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

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

5 結(jié)束語

本文提出了一種基于k-派系社區(qū)結(jié)構(gòu)的移動對等覆蓋網(wǎng)KCCO，通過構(gòu)造一個具有多個不同k-派系結(jié)構(gòu)的網(wǎng)絡拓撲，并結(jié)合數(shù)據(jù)冗余、主動路由修復和拓撲結(jié)構(gòu)自適應等多種機制來提高覆蓋網(wǎng)的性能，增強抗擾動能力。提出一種三維的移動對等覆蓋網(wǎng)性能評估模型，包含了移動性和擾動性等多個移動對等網(wǎng)絡的特性，并在此基礎(chǔ)上對多個覆蓋網(wǎng)在擾動情況下移動網(wǎng)絡中的性能進行了比較分析。評估結(jié)果顯示，本文提出的移動對等覆蓋網(wǎng)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］彭利民，肖文俊.一種具有常數(shù)度的無線P2P覆蓋網(wǎng)［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.