可調(diào)聚類系數(shù)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)建模及其擁塞問(wèn)題研究

第6章可調(diào)聚類系數(shù)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)建模及其擁塞問(wèn)題研究6．１引言現(xiàn)實(shí)生活中，復(fù)雜網(wǎng)絡(luò)的例子比比皆是,如Interｎet[18］、交通網(wǎng)、科學(xué)合作網(wǎng)［21]、社會(huì)網(wǎng)［22］、生物網(wǎng)[14］等等.人們也從不同的角度出發(fā)，提出了各種各樣的復(fù)雜網(wǎng)絡(luò)模型，其中最為著名的是Erd?ｓ和Rénｙi研究的隨機(jī)圖［2]、Wａｔｔｓ和Ｓｔrogaｔｚ提出的小世界網(wǎng)絡(luò)模型［２６］以及Bａrabási和Ａlbeｒt提出的無(wú)標(biāo)度網(wǎng)絡(luò)模型［１7]?，F(xiàn)有的大多數(shù)針對(duì)復(fù)雜網(wǎng)絡(luò)的研究主要屬于無(wú)權(quán)網(wǎng)絡(luò)的范疇，即網(wǎng)絡(luò)的節(jié)點(diǎn)與節(jié)點(diǎn)之間只用是否有連接表示,而不管這種連接關(guān)系的強(qiáng)弱。但是，現(xiàn)實(shí)世界的許多網(wǎng)絡(luò)都不是無(wú)權(quán)網(wǎng)絡(luò),例如，在交通網(wǎng)中連接重大城市之間的高速公路在交通網(wǎng)絡(luò)里的重要性要遠(yuǎn)遠(yuǎn)大于連接一般鄉(xiāng)村之間的低級(jí)公路；Inteｒｎeｔ網(wǎng)絡(luò)中路由器以及路由器之間不同的信息量傳輸；航空網(wǎng)絡(luò)中飛機(jī)運(yùn)載不同數(shù)量的乘客;科學(xué)合作網(wǎng)絡(luò)中,兩個(gè)學(xué)者合作的文章的數(shù)量可以用來(lái)代表這兩個(gè)學(xué)者之間合作的密切程度。因此，有必要通過(guò)給節(jié)點(diǎn)與節(jié)點(diǎn)之間賦予一定的權(quán)值來(lái)形容它們之間的關(guān)系，這樣就形成加權(quán)網(wǎng)絡(luò)。最近，在無(wú)權(quán)網(wǎng)絡(luò)的基礎(chǔ)上研究加權(quán)網(wǎng)絡(luò)已開(kāi)始受到越來(lái)越多的重視[7２—77］。研究表明，不少實(shí)際的加權(quán)網(wǎng)絡(luò)的度和節(jié)點(diǎn)權(quán)重都滿足冪律分布。依據(jù)這一特性，Baｒｒat,Bartｈéleｍｙ和Veｓｐｉgnani提出了一個(gè)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型,稱為BBV模型[6５]。該模型綜合考慮了網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)的權(quán)重等因素來(lái)研究網(wǎng)絡(luò)的動(dòng)態(tài)演化情況。BBV模型具有結(jié)構(gòu)簡(jiǎn)單且易于作理論分析的特點(diǎn)。隨著模型規(guī)模的增大，ＢBV模型網(wǎng)絡(luò)的度、邊權(quán)值和節(jié)點(diǎn)的權(quán)重都呈現(xiàn)無(wú)標(biāo)度特性。BBＶ模型給加權(quán)網(wǎng)絡(luò)的研究奠定了良好的基礎(chǔ).但現(xiàn)實(shí)的許多網(wǎng)絡(luò)。特別是社會(huì)網(wǎng)絡(luò)。除了滿足上述規(guī)律之外，還具有大聚類系數(shù)的特點(diǎn)。也就是在社會(huì)網(wǎng)絡(luò)里相鄰的節(jié)點(diǎn)之間是非常緊密地連接在一起。大聚類系數(shù)反映的是社會(huì)網(wǎng)絡(luò)里“物以類聚，人以群分”的特性。盡管BBV模型自身可以通過(guò)原有參數(shù)的調(diào)節(jié)來(lái)控制聚類系數(shù)的大小，但是調(diào)節(jié)的能力有限,尤其是不能產(chǎn)生較大的聚類系數(shù)。因此，構(gòu)造一個(gè)既符合ＢBV模型的特點(diǎn)，同時(shí)又可以產(chǎn)生大聚類系數(shù)的加權(quán)網(wǎng)絡(luò)模型是十分必要的。最近，一些權(quán)重網(wǎng)絡(luò)模型相繼被提出[65-69,７2－７７,144—１4７］.其中一部分文獻(xiàn)[73-７7]也研究了拓?fù)浣Y(jié)構(gòu)和權(quán)值不斷演化的網(wǎng)絡(luò)模型，但是這些演化機(jī)制描述的是新加入的節(jié)點(diǎn)和舊節(jié)點(diǎn)之間建立連接。而實(shí)際網(wǎng)絡(luò)中，新邊的建立也可能出現(xiàn)在舊節(jié)點(diǎn)之間。本章提出一種加權(quán)網(wǎng)絡(luò)模型，其中新的連邊可以建立在新節(jié)點(diǎn)和老節(jié)點(diǎn)之間,也同樣可以建立在老節(jié)點(diǎn)之間。在該加權(quán)網(wǎng)絡(luò)模型基礎(chǔ)上,采用了基于網(wǎng)絡(luò)邊權(quán)傳遞的局部路由算法研究了網(wǎng)絡(luò)的擁塞問(wèn)題.6。２ＨYＰERＬINK6。4．2仿真分析通信網(wǎng)絡(luò)性能可以通過(guò)整個(gè)網(wǎng)絡(luò)對(duì)于信息包的處理和遞送能力進(jìn)行衡量，然而網(wǎng)絡(luò)的通信能力并不等同于單個(gè)節(jié)點(diǎn)的通信能力。在這里某個(gè)節(jié)點(diǎn)的通信能力為,但整個(gè)網(wǎng)絡(luò)的通信能力則用臨界的數(shù)據(jù)包產(chǎn)生量來(lái)度量，即在臨界數(shù)據(jù)包產(chǎn)生量處，發(fā)生從自由態(tài)到擁塞態(tài)的連續(xù)相變.自由態(tài)是指在同一時(shí)間步內(nèi)所產(chǎn)生的數(shù)據(jù)包數(shù)目可以與達(dá)到目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包個(gè)數(shù)相抵消.而若系統(tǒng)進(jìn)人擁塞態(tài)，則不斷產(chǎn)生的數(shù)據(jù)包中僅有一小部分?jǐn)?shù)據(jù)包可以到達(dá)各自的目標(biāo)點(diǎn)，從而能夠從系統(tǒng)中除去，而大部分?jǐn)?shù)據(jù)包將在系統(tǒng)中不斷積累,最終導(dǎo)致系統(tǒng)的全局擁塞甚至癱瘓。為了描述網(wǎng)絡(luò)中的擁塞轉(zhuǎn)變,繼續(xù)采用參數(shù)刻畫(huà)網(wǎng)絡(luò)的吞吐量和數(shù)據(jù)傳輸?shù)男?（６．２3）其中是時(shí)刻網(wǎng)絡(luò)中總的數(shù)據(jù)包個(gè)數(shù)。當(dāng)時(shí),網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包和到達(dá)終點(diǎn)的數(shù)據(jù)包個(gè)數(shù)幾乎相等，此時(shí)網(wǎng)絡(luò)處于穩(wěn)定狀態(tài)；當(dāng)時(shí),網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)要大于到達(dá)終點(diǎn)的數(shù)據(jù)包個(gè)數(shù)，這將最終導(dǎo)致網(wǎng)絡(luò)發(fā)生擁塞，此時(shí)值隨數(shù)據(jù)包產(chǎn)生數(shù)量的增大而增加,當(dāng)時(shí)網(wǎng)絡(luò)發(fā)生擁塞，并且值越大，擁塞越明顯。當(dāng)時(shí),網(wǎng)絡(luò)完全出于擁塞狀態(tài),即,傳輸?shù)骄W(wǎng)絡(luò)中的數(shù)據(jù)包一個(gè)都沒(méi)有傳出去.因此可以認(rèn)為擁塞轉(zhuǎn)變發(fā)生在時(shí),是可以度量通訊網(wǎng)絡(luò)系統(tǒng)的最大通訊能力。圖６。3在加權(quán)網(wǎng)絡(luò)中,狀態(tài)參數(shù)隨的變化曲線Fig．6．3Theoｒderparameｔｅrversusfoｒｗeiｇｈteｄｓcaｌe-frｅｅｎeｔwoｒkｗitｈdifｆｅｒeｎtｔｕnablｅparａｍetｅr。（Ｃｏloｒonｌinｅ）Rｃｖｓ＿wｉtｈfiｘedW=2aｎd__1.0。ＴｈeresｕｌtsareｏbtaｉneｄbyaveragiｎgRcｏvｅrtennetwｏrｋｒeａｌizａt(yī)ions.６.５本章小結(jié)本章所建構(gòu)的加權(quán)網(wǎng)絡(luò)模型不僅同BBV模型一樣,符合度、點(diǎn)權(quán)和邊權(quán)的冪率分布規(guī)律,同時(shí)還能具有較高的聚類系數(shù),這也更符合實(shí)際的網(wǎng)絡(luò)特性。特別地當(dāng)選擇三角連接機(jī)制的概率值較小時(shí)，網(wǎng)絡(luò)中的平均聚類系數(shù)和度具有非