一種遵循冪率分布的網絡拓撲生成算法ＰＬＯＤ⁺

摘要:拓撲建模是進行網絡性能研究的基礎#65377;PLOD是一種基于冪率的網絡拓撲生成算法，但該算法不能保證生成拓撲圖的連通性，且存在“出度貸款過剩”現象#65377;對PLOD算法進行了改進，在節點連接時添加了連通性檢測，并對出度大的節點實行優先連接，較好地解決了PLOD算法存在的問題#65377;實驗結果表明了PLOD+算法的可行性和有效性#65377;

關鍵詞:拓撲建模;冪率;出度貸款過剩;PLOD+

中圖分類號:TP393;TP301.6文獻標志碼:A

文章編號:1001-3695(2007)04-0315-03

隨著網絡規模的快速增長和復雜度的不斷提高，對其相關技術的研究也越來越多#65377;在網絡性能研究中，拓撲建模是一項很重要的技術，其研究內容可歸結為:如何生成更具代表性#65380;與現實網絡(如Internet)更接近的網絡拓撲結構，供網絡性能仿真實驗使用#65377;

對拓撲建模的研究最早出現在20世紀的五六十年代#65377;那時研究人員對拓撲結構的研究缺乏實際數據的支持，更多的是靠預測#65380;假設#65377;他們認為網絡中的節點是“平等”的，把大型的復雜網絡看成是隨機網絡#65377;1988年，Waxman提出了Waxman模型^[3]，這種隨機網絡拓撲模型在很長的時間里被大家所使用#65377;Waxman模型的優點是簡單#65380;易于實現，缺點是只適用于小型網絡的抽象表示(如ARPANET)，而在大型網絡面前則顯得無能為力#65377;1996年，Doar提出了Tiers模型^[4]，Zegura等人提出了Transitsub模型^[5]#65377;這些模型均屬于層次型的網絡拓撲模型#65377;其中Transitsub模型在最近的網絡仿真實驗中得到了大量的應用#65377;近幾年，Faloutsos等人發現大型網絡拓撲結構中存在著冪率(PowerLaw)^[1，2]#65377;冪率的發現將拓撲建模與生物學#65380;社會學中的復雜網絡聯系起來，使其成為無尺度(Scalefree)網絡^[6]的一個實例#65377;2000年以來，科研人員開發了一些遵循冪率的拓撲生成算法，如 PLOD^[7]#65380;PLRG^[8]#65380;Inet^[10]等#65377;研究表明，這些算法比起以前的一些拓撲生成算法(如Waxman^[3]#65380;Tiers^[4]等)性能有了很大的提高，獲得了與實際網絡更大的相似度#65377;但PLOD算法生成的網絡拓撲圖的連通性得不到保證#65377;另外，上述算法在拓撲生成時只抓住了冪率規則，而沒能結合網絡的宏觀結構信息(如網絡的層次性等)#65377;

1PLOD(PowerLaw OutDegree)算法

1.1冪率(PowerLaw)的形式化描述

1999年，Faloutsos等人對大量的Internet測量數據進行了分析，發現Internet拓撲結構中存在著四條冪率^[1]#65377;在冪率發現以前，大多網絡模型在對網絡進行描述時用的是線性表示法#65377;實驗證明，僅僅用一些線性關系來描述大型網絡是很困難的，所得出的網絡拓撲也與實際網絡相去甚遠#65377;冪率首次用指數形式來探求大型網絡的內在規律，獲得了與實際網絡更大的相似度#65377;以下對冪率作一些具體的介紹#65377;

冪率1(等級指數R)節點的出度dv與該節點等級rv的R次冪成比例(rv是節點按出度降序排列序列中的索引值)，表示為

dv∝rvR(1)

有兩個推論:

(1)dv=1/NRr1R(2)

其中，N為網絡中總的節點數;

(2)E =1/2(R+1)(1-1/NR+1)N(3)

其中，E為網絡中總的邊數#65377;

冪率2(出度指數O)出度頻率fd與該出度d的O次冪成比例(Fd={v│v∈V且dv=d}其中V表示網絡中全體節點v的集合 )，表示為 

fd∝dO(4)

冪率3(Hopplot指數H)在跳數h遠小于網絡直徑δ時，h跳內節點對的數量與h的H次冪成比例(P(h)是節點對的總數)， 表示為

P(h)∝hH ，h<<δ(5)

有兩個推論:

(1)P(h)=ChHh<<δ N2H≥δ(6)

其中，N為網絡中總的節點數;

(2)N(h)=P(h)/N-1=C/N hH-1h<<δ(7)

冪率4(特征指數E)特征值λi與其次序i的E次冪成比例(i為特征值按降序排列的序號)，表示為 

λi∝iE(8)

冪率的發現在拓撲建模領域意義重大#65377;它說明在大型復雜網絡(如Internet)中，節點間既不是像Waxman^[3]所說的完全隨機，也不像Tiers^[4]模型那樣等級森嚴，而是存在著少數集散節點#65377;這些集散節點擁有很高的出度，在網絡拓撲結構中起支配作用#65377;

1.2PLOD算法簡介

PLOD算法是一種遵循冪率的拓撲圖生成算法#65377;它是由Palmer等人于2000年提出來的#65377;PLOD是針對四條冪率中的冪率2(即出度指數)而設計的，它的最大特點是利用冪率來定義拓撲圖的構造#65377;與早期的拓撲生成算法相比，PLOD更好地反映了大型網絡的總體結構和內在規律，更適合于大型網絡的模擬和仿真#65377;在一個表示網絡的拓撲圖中，節點的出度是一種非常直觀#65380;明了的節點屬性#65377;在實際的拓撲生成過程中，節點的出度也比較容易控制#65377;其算法步驟如圖1所示#65377;

1.3PLOD存在的缺陷

PLOD生成的網絡拓撲的連通性差#65377;在進行網絡研究時，計算機網絡可以表示為一個連通的無向圖G=(V，E)，非連通的網絡不能作為網絡研究的仿真環境#65377;實驗證明，在大型網絡的拓撲圖中，往往只有大部分節點(90%~95%)是連通的^[8]#65377;根據上文介紹的PLOD的算法流程，往往會使生成的拓撲圖的連通性得不到保證#65377;

PLOD會造成一些集散節點的出度貸款過剩#65377;首先PLOD根據出度指數分布為各個節點分配一個出度貸款，然后隨機找出節點對，將這個節點對連接，并將各自的Credit減1#65377;然而，在具體的拓撲生成過程中，節點間的Credit差異很大:在一個大型網絡中，絕大部分節點的出度都是小于(或等于)5的，但是也存在著極少數的集散節點，它們的出度非常大#65377;若將Credit很大的節點和Credit很小的節點放在一起，完全隨機地抽取的話，會造成在生成一定數量的連接后，大多數Credit小的節點的Credit已全部分配完畢，而少數Credit很大的節點的剩余Credit分配不出去了#65377;因為PLOD是禁止自循環連接和相同節點對間的反復連接的，所以這些Credit很大的節點就出現了出度貸款(Credit)過剩的現象#65377;以下將通過實驗來進一步闡述上述問題#65377;

本文使用的平臺是Microsoft Visual C++ 6.0#65377;因為在生成的拓撲圖中節點的出度越大，出度貸款過剩的現象就越明顯，所以為了簡便，在實驗中只考察網絡拓撲中出度最大的節點的Credit的分配情況#65377;結果如圖2所示#65377;從圖中可看出，PLOD生成的不同規模的拓撲圖中，出度最大的那個節點往往存在出度貸款過剩的現象#65377;

2PLOD+算法

2.1PLOD+的設計思想

拓撲圖的連通性得不到保證，圖中的一些集散節點會出現出度貸款過剩現象，正是由于這些缺點，PLOD在模擬大型網絡中效果總是不能令人滿意#65377;本文針對PLOD的這些缺點，進行了兩方面的改進:①在節點連接時添加了連通性檢測，從而保證了生成的拓撲圖是全連通的;②在節點對連接的過程中加入了概率判斷，對出度大的節點實行優先連接，這樣的話可以很好地解決出度貸款過剩的現象#65377;

PLOD+算法在進行節點間的連接時，采用了類似于Prim算法的步驟，從而保證生成的拓撲圖是全連通的#65377;具體的做法是:首先生成一個很小的連通域G′=(V， E)，然后隨機尋找非連通域里的節點u，將它與連通域里的節點v連接，并將u并入連通域的點集V內#65377;從而連通域的范圍逐漸擴大，最后將拓撲圖中所有節點納入連通域，形成一個連通分量，即整個拓撲圖是全連通的#65377; 

PLOD按照冪率2給每個節點分配了出度貸款之后，便隨機選取一對節點，若它們的Credit有剩余就將這對節點連接#65377;這樣做雖然簡單#65380;易于實現，但容易造成一些集散節點的Credit過剩的現象#65377;PLOD+在節點間的連接時實行優先連接，即剩余Credit大的節點對可以獲得較大的連接概率#65377;其中節點的剩余Credit定義為C#65377;

C = CM-CD(9)

C表示節點的剩余Credit，CM表示節點分配的初始Credit，CD表示節點已使用的Credit#65377;

在PLOD+算法中，先選取A#65380;B兩點，若A#65380;B兩點間不存在連接，且A#65380;B都有Credit剩余，則A#65380;B兩點間的連接概率P與A#65380;B兩點的剩余Credit之和線性相關#65377;

P=(CA+CB)/∑Ni=1Ci(10)

其中，CA和CB分別表示A和B的剩余Credit，∑Ni=1Ci表示圖中各節點的剩余Credit的總數#65377;

這樣，PLOD+通過連接概率p來對剩余Credit大的節點實行優先連接，有效地解決了Credit過剩的現象#65377;

2.2PLOD+算法

PLOD+是基于PLOD的改進#65377;其各參數的含義如表1所示#65377;

3試驗仿真

為了驗證PLOD+的正確性，本文對PLOD+進行了仿真試驗，并對其進行分析#65377;首先，分別測試了PLOD+#65380;Waxman^[3]#65380;Tiers^[4]對冪率的滿足情況#65377;冪率是反映大型網絡的內在分布規律的，所以若試驗選取的節點數很少(如節點數≤100)，則節點的冪率分布規律將幾乎失去意義#65377;在對PLOD+的仿真試驗中，節點規模選取N=1000，M=1.42×N，α=0.75，β=300^[9]，對這組輸入參數生成五次拓撲圖，然后取平均值進行分析#65377;為了節約空間，只考慮冪率1和冪率2的滿足情況#65377;結果如圖3#65380;4所示#65377;從圖中可以看出，PLOD+能夠較好地滿足冪率分布，而Waxman模型#65380;Tiers模型生成的網絡拓撲不能滿足冪率分布規律#65377;即PLOD+更適合對大型網絡的建模#65377;

為了測試PLOD+在解決Credit過剩方面的性能，本文用PLOD+生成了不同規模的網絡模型(其中參數與圖1相同)#65377;每組輸入參數生成五次拓撲圖，然后取平均值進行分析#65377;測試結果如圖5所示#65377;從圖5中可以看出，PLOD+生成的網絡拓撲中出度最大的節點的Credit得到了比較充分的分配，即PLOD+較好地解決了PLOD中的Credit過剩的問題#65377;

4結束語

目前，網絡拓撲圖作為一種數據輸入，廣泛地應用于各種網絡仿真軟件中#65377;本文提出了一種新的拓撲生成算法PLOD+#65377;試驗證明，該算法能很好地遵循冪率分布規律，且解決了原先的PLOD算法中存在的出度貸款過剩等問題#65377;

如何描述一個大型復雜網絡(如Internet)的特征仍然是一個開放性的問題^[11]#65377;本文的下一步工作將涉及下面幾個問題:①拓撲建模是否可以加入一個時間刻度(Timescale)，用來模擬網絡隨時間變化的動態性變化;②大型復雜網絡僅靠冪率分布來刻畫有時并不夠，是否可以將其他網絡參數和冪率結合在一起，更好地刻畫大型復雜網絡;③基于冪率分布的拓撲圖是否具有層次性，是否可把層次性與冪率分布特性結合起來，進行拓撲建模;④是否可建立基于QoS約束的大型網絡拓撲模型，更好地模擬真實的網絡#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。