動態構造特征可調節的小世界Ｐ２Ｐ網絡
2009-01-01 00:00:00王向輝張國印
計算機應用研究 2009年2期
(哈爾濱工程大學計算機科學與技術學院， 哈爾濱 150001)
摘 要：
P2P網絡是一個動態網絡，靜態模型并不適用于構造P2P網絡。針對目前的動態模型都存在一定局限性，不能夠根據需要調節不同的網絡特征，提出一種新的小世界P2P網絡的動態構造方法。該方法能夠利用構造參數調節網絡的平均度數、聚類系數和平均路徑長度。仿真實驗表明，隨網絡規模擴大網絡持續維持良好的小世界特征，且構造參數能夠有效地調節網絡的小世界特征。
關鍵詞：小世界模型;對等網;動態構造
中圖分類號：TP393 文獻標志碼：A
文章編號：1001-3695(2009)02-0690-03
Dynamic structuring small world P2P networks of character adjustable
WANG Xiang-hui， ZHANG Guo-yin
(College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China)
Abstract:In the dynamic model， the numbers of nodes in network increase over time， and network maintain the small-world features. Due to the P2P network is a dynamic network， static model does not apply to P2P network structure， but dynamic model have some limitations that they do not adjust the different network features according to requirement. The paper presented a new dynamic structure method of small-world P2P network， which could use structure parameter to adjust the average degree， cluster coefficient and average path length of network. Simulation results show that， with the network scale expansion the network maintain small-world features， and structural parameters can effectively regulate the small world network features.
Key words：small world model; P2P network; dynamic structuring
0 引言
小世界現象源于社會學領域的六度分隔（six degrees of separation）理論[1]，即平均通過六個熟人就可以把世界上任意的兩個人聯系起來。Watts等人[2]根據六度分隔假設，提出了小世界（small world）理論。在實際存在的復雜網絡系統中大量存在小世界網絡，這些網絡節點之間的平均距離都很小，但網絡的聚集程度都很高，如電力網、蠕蟲病毒傳播網、通信網絡等。對小世界網絡的研究，有利于分析現實世界疾病傳播原理，改造現有的通信網絡和計算機網絡，控制計算機病毒傳播。
利用小世界理論構造的P2P網絡具有較低的平均度數、較小的平均路徑長度和較大的聚類系數等優點，有利于提高網絡的路由效率，實現負載均衡、增強網絡的容錯能力。因此利用小世界理論構造P2P網絡已成為學術界的研究熱點，國內外已經出現大量的研究成果[3~7]。
在小世界網絡構造方面，主要存以下兩種構造方式：a)靜態模型，是在網絡中的節點數量固定的情況下構造小世界網絡，不適用于P2P網絡的動態環境；b)動態模型，隨節點加入網絡過程中構造小世界網絡，適用于P2P網絡的動態環境，但目前現有的構造方法對網絡的小世界特征調節能力不佳，無法根據具體環境構造出不同傾向性的小世界P2P網絡。
本文提出了一種動態構造環形小世界P2P網絡的方法，能夠在網絡規模不斷擴大的過程中維持網絡的小世界特征，并能夠利用遠端節點參數和近端節點參數調節網絡的平均度數、聚類系數和平均路徑長度。
1 構造模型
在網絡模型中，初始存在m+1個節點，每個節點有m條邊與其他節點相連。新節點根據節點標志符（identifier，ID）加入環型網絡中，并與m個近端節點和w個遠端節點相連。其中：近端節點是在ID空間中距離新加入節點最近的節點，m通常為偶數，且一般在新節點兩側各選擇m/2個節點；遠端節點指不是新節點和m個近端節點以外的節點，w遠端節點的選擇以完全隨機的方式，因此所有遠端節點具有相同的命中概率。如圖1所示，網絡的初始節點數量為3，新節點加入網絡后，產生兩個近端節點鏈接（實線）和一個遠端節點鏈接（虛線）。
在動態模型中，網絡中節點數量隨時間增加，如果令每個時間間隔網絡中的節點數量增加1，那么當網絡中的總節點數量為N時，網絡存在的時間為N-m-1。因此，網絡節點總數N可以描述網絡的大小，也可以描述網絡存在的時間。
2 小世界特征分析
2. 1 度數
當網絡節點數量為N時，令G∧(k，N)表示在N時刻度為k的節點數量。新節點加入網絡時k=m+w，因此所有在k＜m+w的情況下，G∧(k，N)=0。
在N時刻度數為k=m+w的節點加入，如果其中的一個邊連接到已存在的節點i上，則ki→ki+1。因為隨機產生的新節點均勻地分布在整個環上，且新節點在選擇遠端節點時也是完全隨機的，所以環上的所有節點具有(m+w)/N的幾率被新節點連接，即已存在節點的度增加1的可能性為(m+w)/N。G表示G的平均值情況，可得
G(k，N+1)=(1-(m+w)/N)G(k，N)+[(m+w)/N]×
G(k-1，N)+δk，m+w(1)
式（1）等號右邊第一部分表示從N時刻到N+1時刻，度數保持k不變的節點數量；等號右邊第二部分表示從N時刻到N+1時刻，度數從k-1增加到k的節點數量；第三部分δkm是克羅內克符號函數，表示增加一個度數m+w的新節點。
δk，m+w=0， k≠m+w1， k=m+w
(2)
用H(k，N)表示在N時刻度數為k的節點比例，令H(k，N)=G(k，N)/N，且令H(k)是H(k，N)獨立于N的表示，則
H(k)=[(m+w)/(m+w+1)]H(k-1)+δk，m+w/（m+w+1）
(3)
解式（3）遞推關系式得
H(k)=[1/（m+w+1）][(m+w）/（m+w+1）]k-m-w， k≥m+w
0， k＜m+w
(4)
在N時刻，節點的平均度數計算公式為
〈k〉lim N→∞=∑∞k=m+wkH(k)=2(m+w)
(5)
在N時刻，每增加一個節點，將增加m+w條邊，每條邊兩個頂點，因此將給網絡增加的度數為2(m+w)。
2. 2 聚類系數
在動態模型中，分析m和w對網絡聚類系數影響是非常困難的，但根據聚類系數的定義[2]，網絡的聚類系數是所有節點聚類系數的平均值，可以在N時刻選擇新加入網絡的節點i，分析m和w對新節點i的節點聚類系數Ci的影響。假設m和w都較小，且m< Ci=（Umm+Umw+Uww）/w+w 2 (6) 其中：Umm表示m個近端節點之間實際存在邊的數量；Uww表示w個遠端節點之間實際存在邊的數量；Umw表示m個近端節點和w個遠端節點之間實際存在邊的數量。因為m和w都較小，且m< Umm≥U′mm=∑m/2l=1(m-l-1)=m(3m-6)/8 (7) 將式（7）帶入（6）可得 Ci≥(3m-6)/[4(1+w/m)(1+w/m-1/m)] (8) 從式（8）可知，w與Ci成反比例關系，而m與Ci成正比例關系，即當一個新節點加入網絡時，增加m有助于提高網絡的聚類系數。m和w對整個網絡聚類系數的影響，將在仿真實驗中進行分析。 2. 3 平均路徑長度 動態網絡中新節點的加入類似于隨機網絡，因此難以計算確切的網絡平均路徑長度，但可以給出網絡平均路徑長度的上限。首先用d(i，j)表示節點i和節點j之間的最短路徑長度，因此在N時刻，網絡的總路徑長度為 σ(N)=∑0≤i＜j≤N-1d(i，j) (9) 根據平均路徑長度定義[2]，平均路徑長度可以表示為 L(N)=2σ(N)/[N(N-1)](10) 在N+1時刻一個新節點加入網絡，σ′(N)是N+1時刻原有的N個節點的總路徑長度，因為新連接的產生會一定程度地減少原有節點之間的路徑總長度，所以σ′(N)≤σ(N)。可得到下面的不等式 σ(N+1)=σ′(N)+∑N-1i=0d(i，N)≤σ(N)+∑N-1i=0d(i，N) (11) 其中:∑N-1i=0d(i，N)是N+1時刻新加入節點到原有N個節點的路徑長度總和。在N+1時刻，新節點與m+w個原有節點產生連接，令這些原有節點分別為v1，v2，v3，…，vm+w，令D(i，v)=min{d(i，v1 )，…，d(i，vm+w)}，則 ∑N-1i=0d(i，N)=∑N-1i=0[D(i，v)+1]=N+∑N-1i=0D(i，v) (12) 所以 σ(N+1)≤σ(N)+N+∑N-1i=0D(i，v) (13) 令v1，v2，v3，…，vm+w收縮到一點v，因此v到v1，v2，v3，…，vm+w之間任意一個節點的路徑長度為0，即d(v，v1)=…=d(v，vm+w)=0，則D(i，v)=d(i，v)，式（13）可以寫為 σ(N+1)≤σ(N)+N+∑i∈Γd(i，v) (14) 其中：Γ={0，1，2…，N-1}-{v1，v2，…，vm+w}； ∑i∈Γd(i，v)是節點w到網絡中其他N-w-m個節點的路徑長度之和。此時的網絡大小為N-m-w+1，因此利用式（10）可以計算出∑i∈Γd(i，v)的近似值： ∑i∈Γd(i，v)≈(N-m-w)L(N-m-w+1)=2σ(N-m-w+1)/ （N-m-w+1） (15) 將式（15）帶入（14），可得 σ(N+1)≤σ(N)+N+2σ(N-m-w+1)/（N-m-w+1） (16) 將式（16）作為等式進行計算，可得 σ(N)≈N2(ln N-α) (17) 其中：α是一個常數。再將式（17）帶入（10）得 L(N)=2(ln N-α)/（1-1/N） (18) 根據式（18）可知，隨著網絡尺寸N的增大，網絡的平均路徑長度L(N)以對數形式緩慢增長。平均路徑長度增長緩慢主要原因有以下兩點：a)w個遠端節點。遠端節點不僅減少了原節點與遠端節點之間的路徑長度，而且同時減少了原節點附近節點與遠端節點附近節點之間的路徑長度。b)新節點會連接m個近端節點。隨著網絡節點數量的增加，原有的m個近端節點中部分節點會逐漸成為遠端節點，降低網絡的平均路徑長度。 3 仿真實驗 在模擬實驗中，網絡中初始節點數量為4，每個單位時間一個節點加入網絡，網絡的節點數量為N，近端節點數量為m，遠端節點數量為w。 實驗分為兩個階段：第一階段是當N=1 000時，分析不同m和w對網絡的平均度數、聚類系數和平均路徑長度的調節能力，并確定第二階段實驗的m和w值；第二階段首先驗證特定的m和w下的網絡度數分布情況，然后分析網絡聚類系數、平均路徑長度和平均度數隨節點數量N增加的變化情況。 3. 1 特征調節實驗 如圖2所示，當節點數量N=1 000時，網絡的平均度數與m、w成正比例關系，平均度數隨m和w的增大線性增加。從圖中的等高線可知，增加m比增加w更容易提高網絡的平均度數。圖3表明聚類系數與m成正比，與w成反比例；且當m為特定值時，聚類系數隨w增大迅速減小。 為了分析m和w應保持何種關系才能夠使網絡具有較大的聚類系數，將m/(w+1)作為橫坐標，將聚類系數值作為縱坐標，將圖3中所有數據映射到新坐標系中。如圖4所示，聚類系數值隨m/(w+1)分布，且多數節點分布在m/(w+1)∈[0，10]內；m/(w+1)越大，聚類系數越大，當m/(w+1)≥5時，聚類系數大于0.4；圖頂端曲線是w=0時，不同m下的聚類系數值，可見w=0時網絡聚類系數最大。在第二階段選擇m、w的值時，為了保證網絡呈現較大的網絡聚類系數的小世界特征，m/(w+1)的比值應大于等于5，即m/(w+1)≥5。 圖5表明了平均路徑長度與m、w關系：平均路徑長度與m和w均成反比例關系，即平均路徑長度隨m和w的增加而減小；根據圖中的等高線可知，增加w比增加m更加有利于降低網絡的平均路徑長度。 第一階段實驗說明，在動態構造的小世界P2P網絡里，通過調節m和w的值，可使網絡呈現不同的網絡特征。 3. 2 特征呈現實驗 在第二階段實驗中，根據第一階段的分析結果，同時考慮到節點的實際負載能力，選擇m=8和w=1作為第二階段的實驗參數。首先驗證當N=1 000時的網絡度數分布情況，然后分析在N增加時，網絡平均度數、聚類系數和平均路徑長度的變化情況。 圖6是當節點數量N=1 000的網絡度數分布情況圖。其中實心圓點表示根據式（4）計算的理論值，空心圓點表示實驗值，實驗值曲線與理論值曲線基本重合；同時節點度數主要分布在[10，20]，僅有低于1%的節點具有較高的度數。 將節點數量N以200為步長從200增加到2 000，分別考察網絡的平均度數、聚類系數和平均路徑長度的變化情況。 如圖7所示，實心圓點表示根據式（5）計算的理論值，空心圓點表示實驗值，實驗值曲線在節點數量N增大的過程中，逐漸趨近于理論值曲線，與式（5）的N→∞的約束條件相吻合。同時也說明，網絡節點的平均度數不隨節點數量增加而增加；在網絡節點數量較大的情況下，節點的平均度數仍然較小。 圖8中的實驗曲線在一個狹小的范圍內波動，說明網絡的聚類系數不隨節點數量增加而變大；在網絡節點數量較大的情況下，網絡的聚類系數仍可控制在一個可以接受的范圍之內。 如圖9所示，實心圓點表示根據式（18）計算的理論值，其中α=3；空心圓點表示實驗值，實驗值曲線在節點數量N增大的過程中，基本在理論值曲線下方。實驗值曲線說明，網絡的平均路徑長度隨節點數量增加以ln N的比例增加。 4 結束語 本文提出了一種動態構造小世界P2P網絡的新方法，網絡能夠隨節點數量的增加過程中持續維持小世界特征，表現在如下三個方面:a）較小平均度數，〈k〉=O(1)。網絡的平均度數不隨N而變換，而是趨近于恒定的理論值。b）較小平均路徑長度，L~lnN。c）聚類系數，C=O(1)。網絡的聚類系數不隨N而變換，而是在一個較小的范圍內波動。同時，小世界網絡能夠通過參數調節平均度數、平均路徑長度和聚類系數等網絡的小世界特征，有助于增強小世界P2P網絡不同應用中的適用性。 參考文獻： [1]MILGRAM S. The small world problem[J]. Psychol Today， 1967， 2:60-67. [2]WATTS D J， STROGATZ S H. Collective dynamics of small-world networks[J]. Nature， 1998， 393(4):440-442. [3]湯大權，賀明科，孟慶崧.基于冪律分布和小世界特性的無結構P2P網絡中搜索方法研究[J].計算機研究與發展，2007， 44(9): 1566-1571. [4]周晉，路海明，李衍達.用small-world設計無組織P2P系統的路由算法[J].軟件學報， 2004，15(6):915-923. [5]ZHANG Hui， GOELA， GOVINDAN R. Using the small-world model to improve Freenet performance[C]//Proc of IEEE INFOCOM. New York: Elsevier and North-Holl， 2004:555-574. [6]MERUGU S， SHASHIDHAR S， ZEGURA E. Adding structure to unstructured peer-to-peer networks: the use of small-world graphs[J]. Parallel Distributed Compute， 2005， 65(2):142-153. [7]HUI K Y K， LUI J C S， YAU D K Y . Small-world overlay P2P networks: construction management and handling of dynamic flash crowds[J]. Computer Networks， 2006，50(15):2727-2746. [8]NEWMAN M E J， WATTS D J. Scaling and percolation in the small-world network model[J]. Physical Review， 1999，60(6): 7332-7342. [9]OZIK J， HUNT B R， OTT E. Growing networks with geographical attachment preference: emergence of small-worlds[J]. Physical Review， 2004，69(2):1081-1085. [10]ZHANG Zhong-zhi， ZHOU Shui-geng， SHEN Z， et al. Form regular to growing small-world networks[J]. Physical A， 2007， 385(2): 765-772.
