◆石曦彤

（四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 四川 610065）

1 引言

隨著無線通信技術(shù)的迅速發(fā)展，移動P2P 作為一種新型覆蓋網(wǎng)絡(luò)技術(shù)也在不斷發(fā)展中。移動P2P 網(wǎng)絡(luò)中節(jié)點(diǎn)的地位是對等的，每個節(jié)點(diǎn)既是資源下載者，也是資源提供者，這種資源共享模式解決了傳統(tǒng)C/S 模式下服務(wù)器性能瓶頸的問題，更能充分利用網(wǎng)絡(luò)中節(jié)點(diǎn)的計(jì)算資源?，F(xiàn)有的移動P2P 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分為集中式、完全分布式（結(jié)構(gòu)化和非結(jié)構(gòu)化）、混合式三種類型[1]。

集中式P2P 網(wǎng)絡(luò)以目錄服務(wù)器為中心形成星形結(jié)構(gòu)，維護(hù)簡單且搜索效率高，但同時也容易造成單點(diǎn)故障、訪問的“熱點(diǎn)”現(xiàn)象等問題，同時網(wǎng)絡(luò)缺乏可擴(kuò)展性。

完全分布式結(jié)構(gòu)化P2P 網(wǎng)絡(luò)，又稱為DHT 網(wǎng)絡(luò)，在完全分布式結(jié)構(gòu)化網(wǎng)絡(luò)中引入了分布式散列表（Distributed Hash Table，DHT）技術(shù)，經(jīng)典的DHT 算法有Chord[2]、Pastry[3]和Kademlia[4]等。DHT 網(wǎng)絡(luò)的優(yōu)點(diǎn)是采用了確定性拓?fù)浣Y(jié)構(gòu)，能夠精確地定位資源。缺點(diǎn)是DHT 的維護(hù)機(jī)制比較復(fù)雜，尤其是當(dāng)節(jié)點(diǎn)頻繁加入、退出網(wǎng)絡(luò)時造成的網(wǎng)絡(luò)波動會極大增加系統(tǒng)的維護(hù)代價(jià)。完全分布式非結(jié)構(gòu)化網(wǎng)絡(luò)采用完全隨機(jī)的組織結(jié)構(gòu)，優(yōu)點(diǎn)是所有節(jié)點(diǎn)是完全對等的，所以網(wǎng)絡(luò)的可擴(kuò)展性和容錯性較強(qiáng)。缺點(diǎn)是由于采用泛洪式的消息傳播方式增加了網(wǎng)絡(luò)的負(fù)載。

混合式P2P 網(wǎng)絡(luò)結(jié)合了集中式和完全分布式兩種方式，把移動節(jié)點(diǎn)分成多個域，每個域內(nèi)有一個超級節(jié)點(diǎn)，功能是存儲普通節(jié)點(diǎn)信息、內(nèi)容管理和與有線P2P 網(wǎng)絡(luò)的通信，普通節(jié)點(diǎn)發(fā)出文件查詢請求之后，該請求在超級節(jié)點(diǎn)間進(jìn)行轉(zhuǎn)發(fā)，之后該節(jié)點(diǎn)獲得一個反饋結(jié)果列表，然后選擇與之進(jìn)行交易的節(jié)點(diǎn)。

本文提出一種基于節(jié)點(diǎn)興趣的移動P2P 網(wǎng)絡(luò)動態(tài)分組算法，其基本思想是：考慮到相同興趣的節(jié)點(diǎn)間交易概率比較大，另外，移動P2P 網(wǎng)絡(luò)是一種覆蓋網(wǎng)絡(luò)，其在設(shè)計(jì)之初并未考慮到與物理網(wǎng)絡(luò)的結(jié)合，導(dǎo)致邏輯拓?fù)浣Y(jié)構(gòu)與物理拓?fù)浣Y(jié)構(gòu)不匹配，相鄰節(jié)點(diǎn)間的信息延遲較大，故根據(jù)節(jié)點(diǎn)間的興趣相似度、資源相似度以及物理距離對節(jié)點(diǎn)進(jìn)行動態(tài)分組，從而提高整個網(wǎng)絡(luò)的資源共享效率。

2 相關(guān)工作

2.1 節(jié)點(diǎn)聚類方式

聚類是指將物理或抽象的對象集合分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。為了提高移動P2P 網(wǎng)絡(luò)的資源共享效率及安全性，研究者提出了許多移動P2P 網(wǎng)絡(luò)的分組算法。曹曉梅等人[5]提出一種改進(jìn)的分組P2P 信任模型，該模型利用模糊推理規(guī)則結(jié)合信任值和貢獻(xiàn)值，將網(wǎng)絡(luò)中節(jié)點(diǎn)劃分為若干不同等級的小組，通過小組等級限制節(jié)點(diǎn)的資源訪問權(quán)限，實(shí)驗(yàn)表明該模型能有效抑制惡意節(jié)點(diǎn)的攻擊。為了提高移動P2P 網(wǎng)絡(luò)的覆蓋層拓?fù)浞€(wěn)定性，宋人杰等人[6]提出了一種基于節(jié)點(diǎn)移動特性的移動P2P 網(wǎng)絡(luò)分簇算法，實(shí)驗(yàn)表明該算法使簇內(nèi)節(jié)點(diǎn)能夠最大程度地保持覆蓋層拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性。

2.2 超級節(jié)點(diǎn)選取方式

文獻(xiàn)[7]通過分析影響超級節(jié)點(diǎn)選取的各種因素，將這些因素分為效益型屬性和成本型屬性，建立超級節(jié)點(diǎn)選取的帶約束多目標(biāo)優(yōu)化模型，利用免疫克隆算法對超級節(jié)點(diǎn)選取問題進(jìn)行求解。文獻(xiàn)[8]選取服務(wù)能力強(qiáng)和節(jié)點(diǎn)活躍度高的節(jié)點(diǎn)作為超級節(jié)點(diǎn)，主要考慮的影響因素有CPU 速度、帶寬大小和內(nèi)存容量以及節(jié)點(diǎn)單位時間的貢獻(xiàn)度。文獻(xiàn)[9]提出了一種基于信任模式的P2P 超級節(jié)點(diǎn)選取機(jī)制，主要思想是通過計(jì)算節(jié)點(diǎn)的總體信任度作為評選超級節(jié)點(diǎn)的一項(xiàng)重要指標(biāo)，在選取超級節(jié)點(diǎn)時采用閾值過濾算法從普通節(jié)點(diǎn)中篩選備選超級節(jié)點(diǎn)集合，然后再從備選超級節(jié)點(diǎn)集合中選取最優(yōu)的節(jié)點(diǎn)作為超級節(jié)點(diǎn)。王秀娟等人[10]提出一種基于區(qū)域劃分的超級節(jié)點(diǎn)選取機(jī)制，將P2P 網(wǎng)絡(luò)中的節(jié)點(diǎn)按照物理位置劃分成若干區(qū)域，保證區(qū)域內(nèi)節(jié)點(diǎn)在物理位置上是相近的。

3 基于節(jié)點(diǎn)興趣的動態(tài)分組算法

本文提出一種移動P2P 網(wǎng)絡(luò)中基于節(jié)點(diǎn)興趣的動態(tài)分組算法，首先根據(jù)資源類型的個數(shù)，將移動P2P 覆蓋網(wǎng)絡(luò)劃分為若干個組，動態(tài)分組的依據(jù)是網(wǎng)絡(luò)中節(jié)點(diǎn)的興趣相似度，資源相似度、節(jié)點(diǎn)的移動特性以及節(jié)點(diǎn)的物理位置因素，然后根據(jù)交易信息動態(tài)的更新分組。

3.1 節(jié)點(diǎn)角色

（1）超級節(jié)點(diǎn)

超級節(jié)點(diǎn)具有更高的計(jì)算能力和穩(wěn)定性，其維護(hù)一個組中所有節(jié)點(diǎn)的文件列表和不同組節(jié)點(diǎn)之間交易的事務(wù)信息，文件列表記錄了組內(nèi)所有節(jié)點(diǎn)的文件，當(dāng)一個節(jié)點(diǎn)請求一些文件時，它可以將請求發(fā)送給超級節(jié)點(diǎn)，超級節(jié)點(diǎn)告訴請求者哪個組成員擁有請求的文件。

（2）普通節(jié)點(diǎn)

不是超級節(jié)點(diǎn)的節(jié)點(diǎn)，它可以向其他節(jié)點(diǎn)請求資源，也可以為其他節(jié)點(diǎn)提供資源。普通節(jié)點(diǎn)在每次事務(wù)后將事務(wù)信息發(fā)送給對應(yīng)的超級節(jié)點(diǎn)。

3.2 節(jié)點(diǎn)管理

（1）節(jié)點(diǎn)加入

當(dāng)一個新節(jié)點(diǎn)加入網(wǎng)絡(luò)時，根據(jù)興趣相似節(jié)點(diǎn)間交易概率比較大的思想，首先計(jì)算該新節(jié)點(diǎn)與所有超級節(jié)點(diǎn)的興趣相似度，使節(jié)點(diǎn)能夠加入到與其興趣相似度較高的組中；然后考慮到一個組內(nèi)的節(jié)點(diǎn)之間擁有的資源重疊較少時能更好地為其他節(jié)點(diǎn)提供分享資源，故通過計(jì)算節(jié)點(diǎn)間的資源相似度，使分組后組內(nèi)節(jié)點(diǎn)資源盡可能更豐富；最后計(jì)算該新節(jié)點(diǎn)與所有超級節(jié)點(diǎn)的物理距離，使其能被添加到距離相對近的組中。

（2）普通節(jié)點(diǎn)離開

當(dāng)一個普通節(jié)點(diǎn)離開網(wǎng)絡(luò)時，節(jié)點(diǎn)向同一組中的其他節(jié)點(diǎn)廣播離開的消息。同一組中的其他節(jié)點(diǎn)更新鄰居的信息并重新計(jì)算信任值。同時，組中的超級節(jié)點(diǎn)更新路由表和文件列表。

圖1 動態(tài)分組示意圖

（3）超級節(jié)點(diǎn)離開

當(dāng)一個超級節(jié)點(diǎn)離開網(wǎng)絡(luò)時，首先要求超級節(jié)點(diǎn)廣播其離開消息，然后根據(jù)超級節(jié)點(diǎn)選擇機(jī)制重新選擇新的超級節(jié)點(diǎn)。一旦確定了新的超級節(jié)點(diǎn)，組的所有文件列表和節(jié)點(diǎn)間交易的事務(wù)信息都將傳輸?shù)叫碌某壒?jié)點(diǎn)。新的超級節(jié)點(diǎn)響應(yīng)它從原超級節(jié)點(diǎn)接收到的信息。然后，原超級節(jié)點(diǎn)退出網(wǎng)絡(luò)。

3.3 動態(tài)分組流程

在移動 P2P 網(wǎng)絡(luò)中，資源節(jié)點(diǎn)i的興趣集Ipi表示為：Ipi = {a1,a2,…al}，l 為文件類型個數(shù)，對于第k個興趣ak ∈{0,1}，表示節(jié)點(diǎn)i是否擁有至少一個該類型的文件，若擁有則ak =1，否則ak =0。資源節(jié)點(diǎn)j的興趣集Ipj表示為：Ipj ={b1,b2,…bl}，l 為文件類型個數(shù)，對于第k個興趣bk ∈{0,1}，表示節(jié)點(diǎn)j是否擁有至少一個該類型的文件，若擁有則bk = 1，否則bk =0。節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的興趣相似度ISimi,j計(jì)算如下：

式中，si,j表示Ipi和Ipj中對應(yīng)位置的值相同的個數(shù)，l 表示文件類型總數(shù)。

資源節(jié)點(diǎn)i所擁有的文件集Fpi表示為：Fpi ={f1,f2,…fn}，n為節(jié)點(diǎn)i所擁有的文件資源個數(shù)。資源節(jié)點(diǎn)j所擁有的文件集Fpj表示為：Fpj ={f1,f2,…fm}，m為節(jié)點(diǎn)j所擁有的文件資源個數(shù)。節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的資源相似度FSimi,j計(jì)算如下：

在初始階段，因?yàn)閘 是節(jié)點(diǎn)興趣集中的類型數(shù)，故選擇l 個節(jié)點(diǎn)作為初始中心節(jié)點(diǎn)。然后，得到l 個中心節(jié)點(diǎn)和l 個對應(yīng)的初始群。為改善移動P2P 網(wǎng)絡(luò)中邏輯拓?fù)浣Y(jié)構(gòu)與物理拓?fù)浣Y(jié)構(gòu)不匹配而帶來的P2P 節(jié)點(diǎn)間的延遲增大的問題，故在分組時還需考慮節(jié)點(diǎn)之間的物理位置，使各組內(nèi)節(jié)點(diǎn)盡量靠近，在新節(jié)點(diǎn)加入時，通過向各中心節(jié)點(diǎn)發(fā)送探測消息，獲得往返時延值RTT。

給定一個節(jié)點(diǎn)，我們可以通過公式（3）分別計(jì)算它與l 個中心節(jié)點(diǎn)的綜合分組考量值。

式中，δ1、δ2和δ3分別為節(jié)點(diǎn)興趣相似度、資源相似度和物理距離的權(quán)重，且δ1+δ2+δ3 =1，如果給定節(jié)點(diǎn)和中心節(jié)點(diǎn)之間的分組考量值最終得分最大，則將給定節(jié)點(diǎn)添加到中心節(jié)點(diǎn)的組中。通過重復(fù)此過程，將所有節(jié)點(diǎn)添加到相應(yīng)的組中。之后，我們使用K-means[11]中采用的方法更新每組的中心點(diǎn)。然后，通過計(jì)算節(jié)點(diǎn)與更新中心節(jié)點(diǎn)的相似度，得到l 個新的節(jié)點(diǎn)群。如果每個組中的節(jié)點(diǎn)停止更改，則終止此進(jìn)程。

在網(wǎng)絡(luò)交易階段，如果節(jié)點(diǎn)成功收到請求的文件，則更新該節(jié)點(diǎn)擁有的文件集。若系統(tǒng)中的事務(wù)成功交易率小于閾值θ，或者網(wǎng)絡(luò)中節(jié)點(diǎn)加入/離開的比例大于閾值?，則重新進(jìn)行動態(tài)分組。

3.4 超級節(jié)點(diǎn)選取機(jī)制

在資源搜索時，為了減少響應(yīng)時間，提高搜索效率，查詢信息請求應(yīng)該發(fā)送給性能和穩(wěn)定性相對較高的節(jié)點(diǎn)，即超級節(jié)點(diǎn)。本文在選擇超級節(jié)點(diǎn)時把節(jié)點(diǎn)的能力因素作為主要參考指標(biāo)，主要考慮的性能指標(biāo)參數(shù)有：在線時間（OT）、CPU 的有效處理能力（Speed）、帶寬（BW）、存儲空間（Memory）。用Ability變量來表示節(jié)點(diǎn)的能力值，節(jié)點(diǎn)的Ability值越大，則表示該節(jié)點(diǎn)處理能力越強(qiáng)。節(jié)點(diǎn)i的Ability值計(jì)算公式如下：

其中，OTmin表示超級節(jié)點(diǎn)的最短在線時間，單位是秒；Speedmin表示超級節(jié)點(diǎn)的最小有效處理能力，單位是MIPS；BWmin表示超級節(jié)點(diǎn)的最小帶寬，單位是kpbs；Memorymin表示最小存儲空間，單位是GB。

另外在選取超級節(jié)點(diǎn)時還考慮了節(jié)點(diǎn)對系統(tǒng)的貢獻(xiàn)度，即主動提供的資源數(shù)、成功轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的請求消息數(shù)。為每個節(jié)點(diǎn)定義一個貢獻(xiàn)度變量Contribution，計(jì)算公式如下：

其中Fupload表示表示在時間T內(nèi)節(jié)點(diǎn)成功上傳的文件數(shù)，F(xiàn)forward表示節(jié)點(diǎn)成功轉(zhuǎn)發(fā)的消息數(shù)，即間接為系統(tǒng)做出的貢獻(xiàn)，T表示系統(tǒng)運(yùn)行的時間周期。

節(jié)點(diǎn)i的Utility值計(jì)算公式如下：

其中，γ1和γ2分別為節(jié)點(diǎn)能力值和貢獻(xiàn)值的權(quán)重，且γ1+γ2 =1。系統(tǒng)中的每個節(jié)點(diǎn)都有其對應(yīng)的Utility值，周期性地對它們的Utility值進(jìn)行評估，擁有最大Utility值的節(jié)點(diǎn)將成為本分組中的超級節(jié)點(diǎn)。

4 實(shí)驗(yàn)與分析

本文仿真基于 PeerSim1.0.5 仿真系統(tǒng)，PeerSim 支持2 種仿真模式，即 Cycle-based 模式和傳統(tǒng)的 Event-based 模式，Cycle-based 擁有更好的伸縮性及性能，本文采用Cycle-based 模式進(jìn)行仿真，對傳統(tǒng)的半分布式移動P2P 網(wǎng)絡(luò)和基于節(jié)點(diǎn)興趣的動態(tài)分組算法的移動P2P 網(wǎng)絡(luò)進(jìn)行信息檢索延遲的比較。

具體仿真環(huán)境為：節(jié)點(diǎn)總數(shù)為250 個，文件個數(shù)為1000 個，文件種類為8 個，文件在各節(jié)點(diǎn)均勻隨機(jī)分布。其他仿真參數(shù)如表1 所示：

表1 仿真參數(shù)

數(shù)軸中橫坐標(biāo)代表請求次數(shù)，縱坐標(biāo)代表網(wǎng)絡(luò)延時（從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的所有路徑延時之和）。實(shí)驗(yàn)結(jié)果如圖2、3 所示。

圖2 請求次數(shù)從0 到500 時的信息檢索時延

圖3 請求次數(shù)從0 到1000 時的信息檢索時延

由以上仿真結(jié)果可以看出，基于節(jié)點(diǎn)興趣的動態(tài)分組算法的轉(zhuǎn)發(fā)延時比傳統(tǒng)半分布式的延時低30%～40%左右，所以基于節(jié)點(diǎn)興趣的動態(tài)分組算法能夠一定程度地降低網(wǎng)絡(luò)的信息檢索延遲，提高資源檢索的效率，并且具有較好的可擴(kuò)展性。

5 結(jié)束語

為了提高移動P2P 網(wǎng)絡(luò)的資源共享效率，本文根據(jù)興趣相似節(jié)點(diǎn)間交易概率比較大的思想，提出一種基于節(jié)點(diǎn)興趣的動態(tài)分組算法，并在分組時考慮到節(jié)點(diǎn)擁有的資源類型及節(jié)點(diǎn)間的物理位置，從仿真實(shí)驗(yàn)可以得出此算法能夠降低節(jié)點(diǎn)間通信延時，提高移動P2P 網(wǎng)絡(luò)中的文件共享效率，并具有一定的擴(kuò)展性。