李軍,張國(guó)印,王向輝
(1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001;2.安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,安徽 安慶246133)
隨著手機(jī)的普及以及平板電腦、智能手機(jī)等移動(dòng)互聯(lián)網(wǎng)絡(luò)終端設(shè)備的流行,在移動(dòng)網(wǎng)絡(luò)中應(yīng)用P2P技術(shù)開(kāi)始得到重視。由于移動(dòng)網(wǎng)絡(luò)的特殊性,使得互聯(lián)網(wǎng)上的很多成熟技術(shù)無(wú)法直接應(yīng)用于移動(dòng)網(wǎng)絡(luò)。因此,移動(dòng)對(duì)等網(wǎng)絡(luò)的研究還主要集中在核心機(jī)制研究上。在移動(dòng)對(duì)等網(wǎng)絡(luò)的諸多問(wèn)題中,覆蓋網(wǎng)的構(gòu)造是一個(gè)關(guān)鍵性的問(wèn)題。覆蓋網(wǎng)的結(jié)構(gòu)直接決定了移動(dòng)P2P系統(tǒng)的可擴(kuò)展性、魯棒性、安全性和抗擾動(dòng)性。在面向移動(dòng)自組網(wǎng)的移動(dòng)對(duì)等覆蓋網(wǎng)構(gòu)造算法中,使用跨層方法的占了絕大多數(shù)[1-4]。該方法能夠提高查詢成功率,涉及到具體的網(wǎng)絡(luò)層路由協(xié)議和MAC層協(xié)議,通用性較差。原型改進(jìn)方法能夠應(yīng)用于不同的底層網(wǎng)絡(luò),可以利用原有相對(duì)比較成熟的路由協(xié)議、資源查詢算法等,并方便移動(dòng)對(duì)等網(wǎng)絡(luò)和傳統(tǒng)P2P網(wǎng)絡(luò)的互聯(lián)[5-8]。但這種方法必然要遵循已有的框架進(jìn)行改造,從而限制了算法的改進(jìn)范圍。利用博弈論的方法是通過(guò)定義一個(gè)節(jié)點(diǎn)間的博弈來(lái)構(gòu)建一個(gè)達(dá)到預(yù)期目標(biāo)的覆蓋網(wǎng),生成的覆蓋網(wǎng)對(duì)于預(yù)期目標(biāo)來(lái)說(shuō)能夠接近最優(yōu),但不是十分穩(wěn)定,對(duì)于擾動(dòng)的適應(yīng)性也較差[9-10]。本文為了構(gòu)建高效抗擾動(dòng)的移動(dòng)對(duì)等覆蓋網(wǎng),首先提出了一個(gè)基于k-派系社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)洳⒃O(shè)計(jì)了多種抗擾動(dòng)機(jī)制,然后對(duì)其數(shù)據(jù)分發(fā)機(jī)制進(jìn)行了研究,通過(guò)動(dòng)態(tài)調(diào)整不同節(jié)點(diǎn)的數(shù)據(jù)分發(fā)概率來(lái)提高數(shù)據(jù)分發(fā)效率,最后提出了一個(gè)三維的移動(dòng)對(duì)等覆蓋網(wǎng)性能評(píng)估模型,并根據(jù)這一模型對(duì)多個(gè)覆蓋網(wǎng)進(jìn)行了性能評(píng)估。
針對(duì)復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的檢測(cè)和發(fā)現(xiàn)已經(jīng)提出了多種算法,但對(duì)于社區(qū)結(jié)構(gòu)的構(gòu)造算法還較少見(jiàn)。通過(guò)構(gòu)建具有k-派系社區(qū)結(jié)構(gòu)的覆蓋網(wǎng),可以保證該網(wǎng)絡(luò)具有較高的聚集系數(shù)和較短的平均路徑長(zhǎng)度,從而使其表現(xiàn)出小世界特征[11-12]。
每一個(gè)節(jié)點(diǎn)在加入覆蓋網(wǎng)時(shí)進(jìn)行初始化,其數(shù)據(jù)結(jié)構(gòu)包括跳數(shù)值、初始狀態(tài)值、動(dòng)態(tài)狀態(tài)值等,并建立3個(gè)空列表,第1個(gè)是鄰居節(jié)點(diǎn)列表,第2個(gè)是資源共享索引列表,最后一個(gè)是外聯(lián)節(jié)點(diǎn)列表。其中,最先加入網(wǎng)絡(luò)的節(jié)點(diǎn)稱之為中心節(jié)點(diǎn),跳數(shù)為0,鄰居節(jié)點(diǎn)列表中包含其他派系節(jié)點(diǎn)的節(jié)點(diǎn)稱之為外聯(lián)節(jié)點(diǎn)。根據(jù)自身的處理能力和網(wǎng)絡(luò)帶寬等情況計(jì)算節(jié)點(diǎn)初始狀態(tài)值S:
式中:c為節(jié)點(diǎn)運(yùn)算能力值,m為節(jié)點(diǎn)存儲(chǔ)能力值,d為節(jié)點(diǎn)當(dāng)前電量,b為節(jié)點(diǎn)當(dāng)前網(wǎng)絡(luò)帶寬,α、β、γ、δ為權(quán)值,α+β+γ=1,0≤S<1。
計(jì)算節(jié)點(diǎn)的動(dòng)態(tài)狀態(tài)值Sr:
式中:j為節(jié)點(diǎn)跳數(shù)。
每個(gè)節(jié)點(diǎn)只屬于一個(gè)k-派系?;趉-派系社區(qū)結(jié)構(gòu)的覆蓋網(wǎng)結(jié)構(gòu)示意圖如圖1所示。
圖1 基于k-派系的移動(dòng)對(duì)等覆蓋網(wǎng)拓?fù)浣Y(jié)構(gòu)圖Fig.1 Topology of k-clique based mobile P2P overlay
圖1中1~10號(hào)節(jié)點(diǎn)由1個(gè)3-派系組成,11至17號(hào)節(jié)點(diǎn)構(gòu)成了一個(gè)2-派系。黑色節(jié)點(diǎn)為中心節(jié)點(diǎn),灰色節(jié)點(diǎn)為外聯(lián)節(jié)點(diǎn)。實(shí)線表示派系節(jié)點(diǎn)內(nèi)鏈接,虛線表示相鄰派系節(jié)點(diǎn)間鏈接。
本文提出的移動(dòng)對(duì)等覆蓋網(wǎng)絡(luò)首先采取數(shù)據(jù)冗余策略,將單個(gè)節(jié)點(diǎn)的資源索引列表復(fù)制給同派系的多個(gè)節(jié)點(diǎn)進(jìn)行存儲(chǔ),從而降低單個(gè)節(jié)點(diǎn)失效給系統(tǒng)造成的影響。過(guò)度數(shù)據(jù)冗余或者不當(dāng)?shù)臄?shù)據(jù)復(fù)制策略,有可能造成系統(tǒng)崩潰,尤其對(duì)于移動(dòng)網(wǎng)絡(luò)節(jié)點(diǎn)來(lái)說(shuō),網(wǎng)絡(luò)帶寬在很多情況下無(wú)法支持大量數(shù)據(jù)進(jìn)行節(jié)點(diǎn)間的復(fù)制。為此,本文提出了適合移動(dòng)網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)機(jī)制,并在特定范圍內(nèi)對(duì)資源索引列表而不是資源本身進(jìn)行復(fù)制,以降低網(wǎng)絡(luò)負(fù)載。
其次,采用路由表修復(fù)技術(shù)來(lái)保證路由的有效性。采用心跳機(jī)制周期性地探測(cè)鄰居節(jié)點(diǎn),當(dāng)節(jié)點(diǎn)心跳數(shù)在規(guī)定時(shí)間內(nèi)不再增加時(shí)即判定其已經(jīng)失效,從而主動(dòng)發(fā)現(xiàn)失效節(jié)點(diǎn)并修復(fù)路由表。
最后,采用拓?fù)浣Y(jié)構(gòu)自適應(yīng)來(lái)提高抗擾動(dòng)能力。當(dāng)某個(gè)節(jié)點(diǎn)退出或失效時(shí),覆蓋網(wǎng)網(wǎng)絡(luò)拓?fù)渥詣?dòng)進(jìn)行修改,從而提高網(wǎng)絡(luò)的抗擾動(dòng)能力。同時(shí),通過(guò)主動(dòng)外聯(lián)過(guò)程和被動(dòng)外聯(lián)過(guò)程保持本派系節(jié)點(diǎn)與其他派系的鏈接,確保網(wǎng)絡(luò)的連通性。
擾動(dòng)情況下移動(dòng)對(duì)等覆蓋網(wǎng)的性能評(píng)估可以通過(guò)本文提出的三維評(píng)價(jià)模型來(lái)進(jìn)行。該模型中的第1個(gè)維度包含移動(dòng)對(duì)等覆蓋網(wǎng)中影響擾動(dòng)的直接因素,主要指擾動(dòng)模型及其參數(shù),擾動(dòng)模型有指數(shù)分布擾動(dòng)模型、重尾分布擾動(dòng)模型、Pareto分布擾動(dòng)模型、KAD擾動(dòng)模型等;第2個(gè)維度包含移動(dòng)對(duì)等覆蓋網(wǎng)中影響擾動(dòng)的間接因素,如節(jié)點(diǎn)的數(shù)量、節(jié)點(diǎn)的移動(dòng)速度和節(jié)點(diǎn)的移動(dòng)模型等。節(jié)點(diǎn)的移動(dòng)模型可分為個(gè)體移動(dòng)模型和群體移動(dòng)模型,個(gè)體移動(dòng)模型中使用最多的是隨機(jī)路點(diǎn)移動(dòng)模型;最后一個(gè)維度主要包含擾動(dòng)情況下移動(dòng)對(duì)等覆蓋網(wǎng)的性能評(píng)價(jià)指標(biāo),如資源查找成功率、資源平均查詢時(shí)間和網(wǎng)絡(luò)負(fù)載等。
為了驗(yàn)證本文提出的覆蓋網(wǎng)在移動(dòng)網(wǎng)絡(luò)中的性能,在Peerfactsim模擬器[14]上對(duì)該網(wǎng)絡(luò)進(jìn)行模擬,并命名為KCCO(k-clique community overlay)。Peerfactsim模擬器是德國(guó)大學(xué)達(dá)姆施塔特技術(shù)大學(xué)利用Java語(yǔ)言開(kāi)發(fā)的開(kāi)源P2P網(wǎng)絡(luò)模擬實(shí)驗(yàn)平臺(tái),具有通過(guò)離散事件觸發(fā)的特點(diǎn)。實(shí)驗(yàn)中通過(guò)設(shè)定節(jié)點(diǎn)擾動(dòng)模型來(lái)模擬網(wǎng)絡(luò)的擾動(dòng)情況,并改變節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)平均移動(dòng)速度等參數(shù)來(lái)得到覆蓋網(wǎng)的查詢成功率和平均查詢時(shí)間。
底層網(wǎng)絡(luò)采用移動(dòng)自組網(wǎng),節(jié)點(diǎn)活動(dòng)面積為1 000 m×1 000 m。每個(gè)節(jié)點(diǎn)的無(wú)線傳輸距離設(shè)置為240 m,信道容量設(shè)為2 Mb/s,節(jié)點(diǎn)的移動(dòng)模型采用隨機(jī)路點(diǎn)移動(dòng)模型,節(jié)點(diǎn)的移動(dòng)速度設(shè)置為1~10 m/s。節(jié)點(diǎn)擾動(dòng)模型設(shè)為指數(shù)擾動(dòng)模型。節(jié)點(diǎn)資源分布模型為zipf分布,系數(shù)設(shè)為0.7。
為了評(píng)估擾動(dòng)情況下移動(dòng)對(duì)等覆蓋網(wǎng)的性能,本文選擇了另外2種覆蓋網(wǎng)進(jìn)行對(duì)比。其中一個(gè)是GIA,它為了提高Gnutella的可擴(kuò)展性,通過(guò)滿意度參數(shù)使有更高能力的節(jié)點(diǎn)接受更多的鄰居節(jié)點(diǎn)和查詢請(qǐng)求,實(shí)現(xiàn)負(fù)載均衡并提高查找效率[13];另一個(gè)覆蓋網(wǎng)M-GIA是專為移動(dòng)網(wǎng)絡(luò)設(shè)計(jì)的改進(jìn)GIA模型,它改變了節(jié)點(diǎn)ID的生成規(guī)則并增加了位置信息,通過(guò)節(jié)點(diǎn)ID來(lái)計(jì)算2個(gè)節(jié)點(diǎn)之間的距離[1]。M-GIA中的每一個(gè)節(jié)點(diǎn)根據(jù)滿意度和與請(qǐng)求節(jié)點(diǎn)的距離來(lái)共同決定是否接受一個(gè)新的鄰居節(jié)點(diǎn)。
實(shí)驗(yàn)中所評(píng)估的3種覆蓋網(wǎng)具有一部分共同的參數(shù),其參數(shù)名稱及參數(shù)值如表1所示。此外,MGIA中的權(quán)值α和β分別設(shè)為0.5和0.5。KCCO中每一個(gè)k-派系的k值都設(shè)為5。
表1GIA、M-GIA、KCCO共同實(shí)驗(yàn)參數(shù)配置表Table 1 GIA,M-GIA,and KCCO's common experimental parameter settings
指數(shù)擾動(dòng)模型的一個(gè)主要參數(shù)是平均會(huì)話時(shí)長(zhǎng),默認(rèn)值設(shè)為60 min。對(duì)于3種覆蓋網(wǎng)來(lái)說(shuō),默認(rèn)的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)是600個(gè),默認(rèn)的平均節(jié)點(diǎn)移動(dòng)速度是6 m/s。接下來(lái)通過(guò)改變上述3個(gè)參數(shù)中的任意一個(gè)參數(shù),而將其他2個(gè)參數(shù)設(shè)為默認(rèn)值的方法來(lái)評(píng)估3種覆蓋網(wǎng)的性能。
首先將平均會(huì)話時(shí)長(zhǎng)設(shè)為60 min,平均節(jié)點(diǎn)移動(dòng)速度設(shè)為6 m/s,將節(jié)點(diǎn)數(shù)目從200增加到1 000分別進(jìn)行模擬實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖2所示。從圖2可以看出,當(dāng)節(jié)點(diǎn)數(shù)量少于800時(shí),KCCO具有最短的平均查詢時(shí)間,但是當(dāng)節(jié)點(diǎn)數(shù)超過(guò)800時(shí),它成了耗時(shí)最長(zhǎng)的一個(gè)。M-GIA在節(jié)點(diǎn)數(shù)目較少的情況下平均查詢時(shí)間高于GIA,但隨著節(jié)點(diǎn)數(shù)目的增加,其平均查詢時(shí)間逐漸接近并最終低于GIA。
圖2 不同節(jié)點(diǎn)數(shù)目下的平均查詢時(shí)間Fig.2 Average query delay with different numbers of nodes
在不同節(jié)點(diǎn)數(shù)目下的查詢成功率如圖3所示。無(wú)論節(jié)點(diǎn)數(shù)量是多少,與其他2種網(wǎng)絡(luò)相比,KCCO均能取得較高的查詢成功率,始終保持在其他2種覆蓋網(wǎng)的一倍以上。當(dāng)節(jié)點(diǎn)數(shù)少于600時(shí),M-GIA比GIA取得了更高的查詢成功率。隨著節(jié)點(diǎn)數(shù)量的增長(zhǎng),3種覆蓋網(wǎng)均表現(xiàn)出平均查詢時(shí)間增長(zhǎng)而查詢成功率下降的情況。
圖3 不同節(jié)點(diǎn)數(shù)目下的查詢成功率Fig.3 Query success rate with different numbers of nodes
其次將平均會(huì)話時(shí)長(zhǎng)設(shè)為60 min,節(jié)點(diǎn)數(shù)目設(shè)為600,將節(jié)點(diǎn)平均移動(dòng)速度從1 m/s增加到10 m/s分別進(jìn)行模擬實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖4所示。
圖4 不同節(jié)點(diǎn)移動(dòng)速度下的平均查詢時(shí)間Fig.4 Average query delay with different moving speeds of nodes
KCCO的平均查詢時(shí)間最短,隨著節(jié)點(diǎn)移動(dòng)速度的增加有所增加。當(dāng)節(jié)點(diǎn)平均移動(dòng)速度較慢時(shí),GIA要好于M-GIA,反之則不如M-GIA。不同節(jié)點(diǎn)平均移動(dòng)速度下的查詢成功率如圖5所示。KCCO的查詢成功率始終遠(yuǎn)遠(yuǎn)高于其他2種覆蓋網(wǎng),當(dāng)節(jié)點(diǎn)移動(dòng)速度較高時(shí)略有下降。M-GIA和GIA各有優(yōu)劣,多數(shù)情況下M-GIA的查詢成功率略高于GIA。
圖5 不同節(jié)點(diǎn)移動(dòng)速度下的查詢成功率Fig.5 Query success rate with different moving speeds of nodes
最后將節(jié)點(diǎn)數(shù)目設(shè)為600,節(jié)點(diǎn)移動(dòng)速度設(shè)為6 m/s,將平均會(huì)話時(shí)長(zhǎng)從6 min增加到60 min分別進(jìn)行模擬實(shí)驗(yàn)。不同平均會(huì)話時(shí)長(zhǎng)下的平均查詢時(shí)間如圖6所示。隨著平均會(huì)話時(shí)長(zhǎng)的增長(zhǎng),3種網(wǎng)絡(luò)的平均查詢時(shí)間反而增加。M-GIA的平均查詢時(shí)間在絕大多數(shù)情況下都是最長(zhǎng)的。
圖6 不同平均會(huì)話時(shí)長(zhǎng)下的平均查詢時(shí)間Fig.6 Average query delay with different mean session lengths
不同平均會(huì)話時(shí)長(zhǎng)下的查詢成功率如圖7所示。當(dāng)網(wǎng)絡(luò)的平均會(huì)話時(shí)長(zhǎng)延長(zhǎng)時(shí),KCCO的查詢成功率快速增加,而其他2種覆蓋網(wǎng)的查詢成功率基本保持不變,KCCO在擾動(dòng)劇烈的情況下仍然保持了較高的查詢成功率。
圖7 不同平均會(huì)話時(shí)長(zhǎng)下的查詢成功率Fig.7 Query success rate with different mean session lengths
3種覆蓋網(wǎng)在所有情況下的平均查詢時(shí)間相差不是很大,GIA與M-GIA在所有情況下的查詢成功率比較相近。表2和表3為3種覆蓋網(wǎng)在不同參數(shù)下的平均查詢時(shí)間和查詢成功率的比較。可以看到KCCO的平均查詢時(shí)間是最短的,M-GIA的平均查詢時(shí)間最長(zhǎng)。KCCO的查詢成功率明顯高于其他2種覆蓋網(wǎng),M-GIA的查詢成功率在節(jié)點(diǎn)數(shù)目變化時(shí)高于GIA。
表2 3種對(duì)等覆蓋網(wǎng)在不同參數(shù)下的平均查詢時(shí)間比較Table 2 Average query delay comparison of three overlays
表3 3種對(duì)等覆蓋網(wǎng)在不同參數(shù)下的查詢成功率比較Table 3 Query success rate comparison of three overlays
本文提出了一種基于k-派系社區(qū)結(jié)構(gòu)的移動(dòng)對(duì)等覆蓋網(wǎng)KCCO,通過(guò)構(gòu)造一個(gè)具有多個(gè)不同k-派系結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)?,并結(jié)合數(shù)據(jù)冗余、主動(dòng)路由修復(fù)和拓?fù)浣Y(jié)構(gòu)自適應(yīng)等多種機(jī)制來(lái)提高覆蓋網(wǎng)的性能,增強(qiáng)抗擾動(dòng)能力。提出一種三維的移動(dòng)對(duì)等覆蓋網(wǎng)性能評(píng)估模型,包含了移動(dòng)性和擾動(dòng)性等多個(gè)移動(dòng)對(duì)等網(wǎng)絡(luò)的特性,并在此基礎(chǔ)上對(duì)多個(gè)覆蓋網(wǎng)在擾動(dòng)情況下移動(dòng)網(wǎng)絡(luò)中的性能進(jìn)行了比較分析。評(píng)估結(jié)果顯示,本文提出的移動(dòng)對(duì)等覆蓋網(wǎng)KCCO在擾動(dòng)情況下顯著提高了資源查詢成功率,縮短了平均查詢時(shí)間。
[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ù)度的無(wú)線P2P覆蓋網(wǎng)[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,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.