基于隨機(jī)圖的復(fù)雜網(wǎng)絡(luò)建模方法研究

李 姝，邵志香，于金剛

1(沈陽(yáng)理工大學(xué) 裝備工程學(xué)院，沈陽(yáng) 110159)2(頁(yè)巖油氣富集機(jī)理與有效開(kāi)發(fā)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101)3(中國(guó)石化石油工程技術(shù)研究院，北京 100101)4(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所，沈陽(yáng) 110168)

E-mail：lishucx@163.com

1 引 言

近年來(lái)，復(fù)雜網(wǎng)絡(luò)系統(tǒng)的研究在不同領(lǐng)域發(fā)揮著越來(lái)越重要的作用.隨著計(jì)算機(jī)與互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，建立一個(gè)滿足接近于真實(shí)互聯(lián)網(wǎng)通信需求及最短通信鏈路的復(fù)雜網(wǎng)絡(luò)模型，以此為基礎(chǔ)進(jìn)行復(fù)雜網(wǎng)絡(luò)的研究是十分有意義的.由于復(fù)雜網(wǎng)絡(luò)分布錯(cuò)綜復(fù)雜，且網(wǎng)絡(luò)傳輸中受網(wǎng)絡(luò)承載量及傳輸質(zhì)量等諸多因素的限制，雖然表面上復(fù)雜網(wǎng)絡(luò)的傳輸路徑是隨機(jī)的，但這并不意味著復(fù)雜網(wǎng)絡(luò)毫無(wú)規(guī)律可循.有研究表明，很多網(wǎng)絡(luò)具有小世界性質(zhì)[1，2]，即從原點(diǎn)節(jié)點(diǎn)到目的節(jié)點(diǎn)的訪問(wèn)路徑存在一條“相對(duì)固定”的最短通信鏈路.這里的“相對(duì)固定”是根據(jù)一定的發(fā)生概率而言的，即從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信鏈路是存在一定的訪問(wèn)概率的，這說(shuō)明人們?cè)L問(wèn)某個(gè)站點(diǎn)或者服務(wù)器的通信鏈路也是相對(duì)固定的[3，4].

根據(jù)上述研究，有研究者提出利用隨機(jī)圖理論可以生成與真實(shí)網(wǎng)絡(luò)訪問(wèn)拓?fù)浣Y(jié)構(gòu)具有高相似度的隨機(jī)圖網(wǎng)絡(luò)模型，能夠更好的模擬與研究復(fù)雜網(wǎng)絡(luò)的通信[5，6].基于此，本文在隨機(jī)圖理論的基礎(chǔ)上，提出了基于隨機(jī)圖的樹(shù)型網(wǎng)絡(luò)仿真模型k-RGN，該網(wǎng)絡(luò)模型是一種充分考慮連接鏈路權(quán)重，且服從指數(shù)分布的隨機(jī)網(wǎng)絡(luò)模型.通過(guò)網(wǎng)絡(luò)模型的對(duì)比實(shí)驗(yàn)，驗(yàn)證了k-RGN隨機(jī)網(wǎng)絡(luò)模型在帶寬、丟包率、時(shí)延、時(shí)延抖動(dòng)、跳數(shù)等多參數(shù)指標(biāo)規(guī)劃中，具有最優(yōu)的網(wǎng)絡(luò)性能.

2 隨機(jī)圖理論與隨機(jī)圖模型

設(shè)某個(gè)概率空間中的每一節(jié)點(diǎn)都看作是一個(gè)圖，則稱這些圖為隨機(jī)圖[7，8].其中隨機(jī)圖Gp(n)定義：概率空間由V={1，2，…，n}為節(jié)點(diǎn)的n個(gè)圖集組成.其中n個(gè)節(jié)點(diǎn)是可區(qū)別的，即每個(gè)圖被認(rèn)為是不同的圖，出現(xiàn)概率p滿足0

隨機(jī)圖Gp(n)最廣泛的應(yīng)用之一是建立隨機(jī)網(wǎng)絡(luò)，研究者們一直以來(lái)致力于研究出一種被廣泛用來(lái)生成復(fù)雜網(wǎng)絡(luò)的隨機(jī)圖模型方法，達(dá)到生成具有指定度序列[9]或者具有指定冪律分布的復(fù)雜網(wǎng)絡(luò).用隨機(jī)圖生成隨機(jī)網(wǎng)絡(luò)模型，其建模方法如下[10，11]：

給隨機(jī)圖Gp(n)中的每個(gè)節(jié)點(diǎn)都附加一個(gè)頂點(diǎn)權(quán)重w，則節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在一條邊的概率為:

(1)

將頂點(diǎn)賦予權(quán)重，可以使得隨機(jī)圖模型更好的適應(yīng)于網(wǎng)絡(luò)的實(shí)際分布.節(jié)點(diǎn)的權(quán)重越大，表明該節(jié)點(diǎn)與其他節(jié)點(diǎn)相連的概率就越大，我們通過(guò)選取合適的節(jié)點(diǎn)權(quán)重，來(lái)構(gòu)建一個(gè)更貼近于實(shí)際網(wǎng)絡(luò)的隨機(jī)模型.假設(shè)我們構(gòu)造了一個(gè)包含兩種不同類型節(jié)點(diǎn)的網(wǎng)絡(luò)，第一類節(jié)點(diǎn)的權(quán)重為w1，第二類節(jié)點(diǎn)的權(quán)重記作w2，n1與n2分別表示第一類節(jié)點(diǎn)與第二類節(jié)點(diǎn)的個(gè)數(shù).即：

ln=n1w1+n2w2

(2)

(3)

由式(3)可知，第一類型節(jié)點(diǎn)的期望度數(shù)趨近于w1.同理可推，第二類節(jié)點(diǎn)的期望度數(shù)趨近于w2.

由上可知，基于隨機(jī)圖的網(wǎng)絡(luò)結(jié)構(gòu)高度依賴于頂點(diǎn)權(quán)重，在實(shí)際網(wǎng)絡(luò)中，頂點(diǎn)的權(quán)重可以設(shè)置固定值，或更加復(fù)雜的隨機(jī)變量序列.為了研究頂點(diǎn)權(quán)重的經(jīng)驗(yàn)性質(zhì)，我們定義頂點(diǎn)權(quán)重的經(jīng)驗(yàn)分布函數(shù)：

(4)

可以將Fn(x)看成隨機(jī)選取節(jié)點(diǎn)權(quán)重的分布函數(shù)，在應(yīng)用中，通常假設(shè)頂點(diǎn)權(quán)重服從正則化條件.

3 基于隨機(jī)圖的k-叉樹(shù)網(wǎng)絡(luò)模型

根據(jù)隨機(jī)圖理論在隨機(jī)網(wǎng)絡(luò)中的建模可知，雖然隨機(jī)網(wǎng)絡(luò)模型與物理上的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并不一致，但它與實(shí)際的網(wǎng)絡(luò)訪問(wèn)結(jié)構(gòu)或者路由連接鏈路可以有很好的吻合.然而，隨著隨機(jī)圖理論應(yīng)用于通信網(wǎng)絡(luò)建模的研究深入，有研究表明[12-14]，廣義隨機(jī)網(wǎng)絡(luò)模型只適合于普通簡(jiǎn)單規(guī)模的網(wǎng)絡(luò)訪問(wèn)模型，對(duì)于大型復(fù)雜通信網(wǎng)絡(luò)，其網(wǎng)絡(luò)模型表現(xiàn)并不理想.

鑒于此，本文在隨機(jī)圖理論的基礎(chǔ)上，提出一種基于隨機(jī)圖的k-叉樹(shù)網(wǎng)絡(luò)模型(k-RGN)，使得隨機(jī)圖Gp(n)的網(wǎng)絡(luò)模型服從于指數(shù)分布，進(jìn)而適用于大型復(fù)雜通信網(wǎng)絡(luò)結(jié)構(gòu)；此外，k-RGN網(wǎng)絡(luò)模型充分考慮連接鏈路的權(quán)重問(wèn)題，使隨機(jī)網(wǎng)絡(luò)模型更適用于實(shí)際網(wǎng)絡(luò)訪問(wèn)需求和最短訪問(wèn)路徑的復(fù)雜網(wǎng)絡(luò).

設(shè)一棵k叉樹(shù)由一個(gè)源點(diǎn)和N個(gè)節(jié)點(diǎn)組成，樹(shù)深度D等于從源點(diǎn)到節(jié)點(diǎn)的跳數(shù)，m為隨機(jī)選取的遍歷節(jié)點(diǎn)個(gè)數(shù)，k為樹(shù)的分枝數(shù)，k叉樹(shù)網(wǎng)絡(luò)模型如圖1所示.在一棵k叉樹(shù)中，節(jié)點(diǎn)的總數(shù)滿足下式：

(5)

由公式(5)可知，N服從于kD，記N～kD.

我的爸爸還是一個(gè)幽默搞笑的人。有一次，他無(wú)意間撈到了一只青蛙，“看！這只青……”他剛說(shuō)到這里，那只青蛙就回頭看了看他，“撲通”一聲跳進(jìn)了水里，弄得他滿臉都是泥水，就像是一只“大青蛙”。我看了一眼被泥水濺成“大花臉”的爸爸，“撲哧”一聲笑了出來(lái)。

圖1 k-叉樹(shù)網(wǎng)絡(luò)模型k=2，N=21，D=4Fig.1 k-tree network model k=2，N=21，D=4

建立k-RGN網(wǎng)絡(luò)模型，需要考慮兩點(diǎn)問(wèn)題：1)隨機(jī)圖網(wǎng)絡(luò)的連通性，即隨機(jī)生成樹(shù)應(yīng)遍歷所有節(jié)點(diǎn)，并且確保每個(gè)節(jié)點(diǎn)都是雙連通的；2)隨機(jī)鏈路的產(chǎn)生，即我們?nèi)绾巫尞a(chǎn)生的隨機(jī)網(wǎng)絡(luò)更接近于真實(shí)網(wǎng)絡(luò)的連接狀況.具體步驟如下：

1)產(chǎn)生隨機(jī)節(jié)點(diǎn).首先建立笛卡爾坐標(biāo)系xoy，將坐標(biāo)系以整數(shù)最小單位劃分成網(wǎng)格(可以將網(wǎng)格單位設(shè)為1)，利用整數(shù)隨機(jī)發(fā)生器產(chǎn)生隨機(jī)節(jié)點(diǎn)，使隨機(jī)節(jié)點(diǎn)均落在網(wǎng)絡(luò)上；然后分別檢查產(chǎn)生節(jié)點(diǎn)的橫縱坐標(biāo)間距，刪除掉間距小于5的隨機(jī)節(jié)點(diǎn)，并重新生成節(jié)點(diǎn)，直至滿足間距為止；

2)產(chǎn)生隨機(jī)鏈路.網(wǎng)絡(luò)的隨機(jī)節(jié)點(diǎn)產(chǎn)生后，接下來(lái)在這些節(jié)點(diǎn)中建立隨機(jī)鏈路，這里的“隨機(jī)鏈路”并非是完全的隨機(jī)，這里我們模擬與實(shí)際網(wǎng)絡(luò)訪問(wèn)鏈路最接近的連接方式，構(gòu)建一個(gè)連通的隨機(jī)網(wǎng)絡(luò).

在實(shí)際的網(wǎng)絡(luò)通信中，通常是節(jié)點(diǎn)間距離越大，節(jié)點(diǎn)間建立連接的可能性越小，但我們并不能簡(jiǎn)單地以距離作為節(jié)點(diǎn)間連接的依據(jù)，這與實(shí)際需求中的網(wǎng)絡(luò)通訊結(jié)構(gòu)并非一致.本文基于隨機(jī)圖理論，將節(jié)點(diǎn)間的距離設(shè)為連接權(quán)重，并帶入節(jié)點(diǎn)間存在鏈路的概率P中.連接概率P與節(jié)點(diǎn)間的距離有關(guān)，建立節(jié)點(diǎn)間連接概率P函數(shù)如下：

(6)

P(u，v)是節(jié)點(diǎn)u和節(jié)點(diǎn)v之間存在連接的概率，d(u，v)是它們之間的距離，L是網(wǎng)絡(luò)節(jié)點(diǎn)間可能的最大距離之和，權(quán)重參數(shù)w是控制遠(yuǎn)程連接和本地連接所占的比重，長(zhǎng)連接的比重越大，w取值越大.值得說(shuō)明，參數(shù)w應(yīng)該服從公式(4)經(jīng)驗(yàn)分布函數(shù)Fn(x)，這里為方便計(jì)算，我們?cè)O(shè)w取值為0到1.參數(shù)γ調(diào)節(jié)網(wǎng)絡(luò)的平均節(jié)點(diǎn)度數(shù)，γ越大，網(wǎng)絡(luò)平均節(jié)點(diǎn)度數(shù)越多.

3)檢查網(wǎng)絡(luò)連通性.使用式(6)產(chǎn)生的隨機(jī)網(wǎng)絡(luò)在大量節(jié)點(diǎn)時(shí)，不能保證網(wǎng)絡(luò)的連通性.為了糾正網(wǎng)絡(luò)的非連通性，我們?cè)贆z查網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的連接度數(shù)，如節(jié)點(diǎn)的連接度數(shù)為1時(shí)，將該節(jié)點(diǎn)與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)隨機(jī)產(chǎn)生一條鏈路.經(jīng)過(guò)反復(fù)處理，產(chǎn)生的隨機(jī)網(wǎng)絡(luò)一定是有雙連接的連通網(wǎng)絡(luò).

圖2 k-RGN網(wǎng)絡(luò)模型Gp(20)Fig.2 k-RGN network model Gp(20)

實(shí)驗(yàn)選取200*200的笛卡爾坐標(biāo)，橫、縱坐標(biāo)的隨機(jī)數(shù)在0到200之間產(chǎn)生，坐標(biāo)軸最小刻度單位為1.設(shè)隨機(jī)網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)N=20，權(quán)重參數(shù)w=0.16，調(diào)節(jié)系數(shù)γ=3.7.實(shí)驗(yàn)任意選取節(jié)點(diǎn)u和節(jié)點(diǎn)v，根據(jù)公式(6)計(jì)算它們之間可能存在連接的概率P(u，v)，在0到Rmax之間產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)Ri，如果隨機(jī)數(shù)Ri的概率Pi滿足于公式(7)，則節(jié)點(diǎn)u和節(jié)點(diǎn)v之間存在連接，否則不存在連接.反復(fù)隨機(jī)選取各節(jié)點(diǎn)，產(chǎn)生隨機(jī)連接.每當(dāng)增加一條連接時(shí)，需要進(jìn)行判斷是否達(dá)到了平均節(jié)點(diǎn)度數(shù)，若己經(jīng)達(dá)到，則停止.如圖2所示選取節(jié)點(diǎn)數(shù)為20個(gè)時(shí)，產(chǎn)生的隨機(jī)網(wǎng)絡(luò)模型.

Pi=Ri/Rmax

(7)

4 隨機(jī)圖k-RGN網(wǎng)絡(luò)模型的網(wǎng)絡(luò)性能分析

本文基于隨機(jī)圖原理，建立了k-RGN網(wǎng)絡(luò)仿真模型，其研究意義在于預(yù)測(cè)k-RGN網(wǎng)絡(luò)仿真模型在實(shí)際通信的復(fù)雜網(wǎng)絡(luò)中所表現(xiàn)的連接狀況及網(wǎng)絡(luò)性能，為拓展復(fù)雜網(wǎng)絡(luò)理論研究和驗(yàn)證實(shí)際應(yīng)用效果提供依據(jù).通常用以描述網(wǎng)絡(luò)綜合性能的指標(biāo)包括：帶寬、時(shí)延、時(shí)延抖動(dòng)、丟包率和跳數(shù)等.

時(shí)延是指一個(gè)報(bào)文或分組從一個(gè)網(wǎng)絡(luò)的一端傳到另一端所需要的時(shí)間，時(shí)延等于發(fā)送時(shí)延，處理時(shí)延，傳播時(shí)延與排隊(duì)時(shí)延之和.這里我們只計(jì)算傳播時(shí)延，即從一個(gè)節(jié)點(diǎn)進(jìn)入下一節(jié)點(diǎn)所需的時(shí)間間隔.設(shè)tij是i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)之間的時(shí)延.

時(shí)延抖動(dòng)是指信息通過(guò)節(jié)點(diǎn)的最大與最小時(shí)間延遲差.設(shè)sij是i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)之間的時(shí)延抖動(dòng).

丟包率是指在鏈路的傳輸過(guò)程中所丟失的包數(shù)與傳輸包的總數(shù)之比，它體現(xiàn)鏈路的可靠性.設(shè)lij是i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)之間的丟包率.

跳數(shù)是指路徑所經(jīng)過(guò)的鏈路數(shù)(即從原點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)).設(shè)hij是i節(jié)點(diǎn)到第j節(jié)點(diǎn)之間的跳數(shù).

在k-RGN網(wǎng)絡(luò)模型中，從節(jié)點(diǎn)i到節(jié)點(diǎn)j假設(shè)存在k條鏈路，則從節(jié)點(diǎn)i到節(jié)點(diǎn)j的總帶寬為：

(8)

從節(jié)點(diǎn)i到節(jié)點(diǎn)j的總時(shí)延為：

(9)

從節(jié)點(diǎn)i到節(jié)點(diǎn)j的總時(shí)延抖動(dòng)為：

(10)

從節(jié)點(diǎn)i到節(jié)點(diǎn)j的總丟包率為：

(11)

從節(jié)點(diǎn)i到節(jié)點(diǎn)j的總跳數(shù)率為：

(12)

實(shí)驗(yàn)在最短路徑算法(Dijkstra算法)生成的網(wǎng)絡(luò)模型，與基于隨機(jī)圖的k-RGN網(wǎng)絡(luò)模型中進(jìn)行，比較這兩種網(wǎng)絡(luò)模型的網(wǎng)絡(luò)性能.實(shí)驗(yàn)分別選取，節(jié)點(diǎn)數(shù)n=20，60，100.對(duì)選取的各個(gè)節(jié)點(diǎn)數(shù)所限定產(chǎn)生的網(wǎng)絡(luò)規(guī)模分別為3*n個(gè)網(wǎng)絡(luò)連接單元.實(shí)驗(yàn)分別選取0.1*n組，0.2*n組，0.3*n組隨機(jī)節(jié)點(diǎn)進(jìn)行通信仿真，每組網(wǎng)絡(luò)獨(dú)立重復(fù)試驗(yàn)20次，最后求取各參數(shù)均值.選取節(jié)點(diǎn)個(gè)數(shù)100時(shí)，網(wǎng)絡(luò)性能參數(shù)對(duì)比如表1所示.

表1 節(jié)點(diǎn)數(shù)100兩種模型的網(wǎng)絡(luò)性能參數(shù)對(duì)比Table 1 Comparison of network performance parametersat 100 nodes

通過(guò)對(duì)比試驗(yàn)可知，在實(shí)驗(yàn)選取節(jié)點(diǎn)個(gè)數(shù)為100個(gè)時(shí)，基于隨機(jī)圖的k-RGN的網(wǎng)絡(luò)仿真模型的網(wǎng)絡(luò)平均帶寬、時(shí)延、抖動(dòng)時(shí)延、丟包率、跳數(shù)等性能參數(shù)均優(yōu)于由Dijkstra算法生成的網(wǎng)絡(luò)模型.實(shí)驗(yàn)結(jié)果說(shuō)明，基于隨機(jī)圖的k-RGN的網(wǎng)絡(luò)仿真模型在多個(gè)網(wǎng)絡(luò)通信節(jié)點(diǎn)數(shù)的復(fù)雜網(wǎng)絡(luò)中，仍然表現(xiàn)出較好的網(wǎng)絡(luò)綜合性能.

5 結(jié) 論

本文在隨機(jī)圖理論的基礎(chǔ)上，結(jié)合k-叉樹(shù)模型提出了基于隨機(jī)圖的樹(shù)型網(wǎng)絡(luò)仿真模型k-RGN.該網(wǎng)絡(luò)模型是通過(guò)引入連接權(quán)重w，將復(fù)雜網(wǎng)絡(luò)模型更接近于實(shí)際網(wǎng)絡(luò)訪問(wèn)的通信鏈路；此外k-RGN網(wǎng)絡(luò)仿真模型是服從指數(shù)分布的隨機(jī)網(wǎng)絡(luò)模型，其網(wǎng)絡(luò)節(jié)點(diǎn)度值符合平均值為np的泊松分布，且存在最短的連接鏈路d.最后通過(guò)模型的對(duì)比實(shí)驗(yàn)分析，驗(yàn)證了k-RGN隨機(jī)網(wǎng)絡(luò)模型在平均帶寬、丟包率、時(shí)延、時(shí)延抖動(dòng)、跳數(shù)等多參數(shù)指標(biāo)規(guī)劃中，均優(yōu)于普通路由算法建立的網(wǎng)絡(luò)模型.基于隨機(jī)圖k-RGN網(wǎng)絡(luò)模型具有很好的網(wǎng)絡(luò)綜合性能，適用于復(fù)雜網(wǎng)絡(luò)建模.