基于最短路徑長度的空間網(wǎng)絡(luò)路由*

林泓 夏永祥? 蔣路茸

1) (杭州電子科技大學(xué)通信工程學(xué)院,杭州 310018)

2) (浙江理工大學(xué)信息學(xué)院,杭州 310018)

1 引言

20 世紀(jì)50 年代末,Erd?s 與Rényi[1]提出的ER 隨機(jī)圖模型開辟了復(fù)雜網(wǎng)絡(luò)領(lǐng)域研究的先河.直至20 世紀(jì)末,小世界網(wǎng)絡(luò)[2]的提出與無標(biāo)度特性[3]的發(fā)現(xiàn),吸引了一大批科學(xué)家參與到復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)與動力學(xué)的研究之中.近十年來,復(fù)雜網(wǎng)絡(luò)成為生物技術(shù)、移動通信、交通運(yùn)輸、社會關(guān)系等多個不同領(lǐng)域的研究熱點(diǎn)[4-8],受到物理、數(shù)學(xué)、計(jì)算機(jī)、通信、社會學(xué)等領(lǐng)域?qū)W者的廣泛關(guān)注.實(shí)際生活中的Internet、移動通信網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)、電力網(wǎng)等都可以被抽象成復(fù)雜網(wǎng)絡(luò)進(jìn)行研究分析,而這類網(wǎng)絡(luò)的傳輸性能與人們的生活息息相關(guān).如何提升網(wǎng)絡(luò)的傳輸性能已經(jīng)成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域研究的熱門課題之一.網(wǎng)絡(luò)傳輸能力主要取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與路由方式,針對這兩方面的影響因素,一般有“硬策略”和“軟策略”兩種優(yōu)化方式[9],即優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與優(yōu)化路由方式.而在實(shí)際生活中,不少網(wǎng)絡(luò)的結(jié)構(gòu)已經(jīng)固定,修改其結(jié)構(gòu)需要承擔(dān)高昂的成本.因此,采用更加高效的路由策略來提升網(wǎng)絡(luò)傳輸性能更具有可行性.

傳統(tǒng)意義上的最短路徑的策略是目前應(yīng)用較為廣泛的一種路由方式,即負(fù)載從節(jié)點(diǎn)A通過最少的邊數(shù)傳輸?shù)焦?jié)點(diǎn)B,但是這種方式很容易在一些度值較大的節(jié)點(diǎn)處造成擁塞現(xiàn)象[10].因此,不少研究人員提出了更加高效的路由策略[10-20].Yan等[18]提出了一種“the efficient path”的路由策略,定義任意兩點(diǎn)i和j之間的路徑為L(P(i →j):β)=以 m in(L) 為目標(biāo)選擇路徑,通過繞 開度值較大的節(jié)點(diǎn)來減少發(fā)生擁塞的可能,大大提升網(wǎng)絡(luò)的傳輸性能.Huang 和Chow[19]提出了一種帶記憶信息的路由策略,節(jié)點(diǎn)記錄負(fù)載的傳輸來源,避免出現(xiàn)回溯現(xiàn)象,使得負(fù)載在兩個不同節(jié)點(diǎn)之間來回傳輸?shù)臋C(jī)會大大減少,有效地提高網(wǎng)絡(luò)吞吐量.Wang 等[20]提出了一種流量模型,負(fù)載從節(jié)點(diǎn)a傳輸?shù)焦?jié)點(diǎn)b,若節(jié)點(diǎn)a與b之間有邊連接,則負(fù)載可直接傳輸至目標(biāo)節(jié)點(diǎn)b;否則,將以Πi=的概率傳輸至a的某個鄰居節(jié)點(diǎn)i.

之前提出的各種路由策略主要是基于復(fù)雜網(wǎng)絡(luò)的拓?fù)?很少有研究考慮節(jié)點(diǎn)的空間位置.而事實(shí)上,由于空間網(wǎng)絡(luò)中的節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接受到實(shí)際位置的約束,與一般的復(fù)雜網(wǎng)絡(luò)在拓?fù)浣Y(jié)構(gòu)和魯棒性[21]等方面具有一定的差異性.在實(shí)際生活中,如航空網(wǎng)絡(luò)[22]、交通網(wǎng)絡(luò)[23]、無線傳感器網(wǎng)絡(luò)[24]、無人機(jī)網(wǎng)絡(luò)[25]等都受到空間位置的限制.由于這類空間網(wǎng)絡(luò)的特殊性,對其路由策略的研究具有很強(qiáng)的理論價值和現(xiàn)實(shí)意義.

本文提出一種基于最短路徑長度的空間路由方式,即負(fù)載從源節(jié)點(diǎn)沿著最短路徑長度的方向傳輸?shù)侥繕?biāo)節(jié)點(diǎn).Zhao 等[26]在2005 年發(fā)表的文章中指出,不同結(jié)構(gòu)的網(wǎng)絡(luò)出現(xiàn)擁塞現(xiàn)象的性能不相同.因此,本文考慮了空間勻質(zhì)網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)兩種情況,在隨機(jī)幾何圖[27]和LAEE (local-area and energy-efficient evolution)模型[28]上進(jìn)行了仿真模擬.仿真結(jié)果表明,本文提出的路由策略能夠有效提升網(wǎng)絡(luò)的傳輸性能,減少擁塞現(xiàn)象的發(fā)生.

2 空間網(wǎng)絡(luò)模型

2.1 LAEE 演化模型

研究發(fā)現(xiàn),很多實(shí)際網(wǎng)絡(luò)都遵循節(jié)點(diǎn)的度值呈冪律分布的無標(biāo)度特性,即P(k)∝k-γ,其中k表示節(jié)點(diǎn)的度,γ為常數(shù).為了探究本文提出的路由算法在異質(zhì)網(wǎng)絡(luò)上的適用性,采用Jiang 等[28]提出的具有無標(biāo)度特性的空間LAEE 演化模型.

該網(wǎng)絡(luò)的拓?fù)溲莼饕譃閮蓚€階段.在第1 階段,將N個節(jié)點(diǎn)隨機(jī)分布在1 × 1 的區(qū)域S內(nèi),每個節(jié)點(diǎn)傳輸和處理負(fù)載的能力都是相同的.此時所有節(jié)點(diǎn)都是孤立的,假設(shè)以節(jié)點(diǎn)i為圓心、r為半徑的連通區(qū)域內(nèi)所有節(jié)點(diǎn)為節(jié)點(diǎn)i的潛在鄰居,并定義最靠近原點(diǎn)O的節(jié)點(diǎn)為匯聚節(jié)點(diǎn).

在第2 階段,從匯聚節(jié)點(diǎn)開始進(jìn)行網(wǎng)絡(luò)的拓?fù)溲莼?

步驟1令匯聚節(jié)點(diǎn)與其通信半徑r內(nèi)的a0個潛在鄰居節(jié)點(diǎn)進(jìn)行連接,形成初始網(wǎng)絡(luò)T0.

步驟 2在時間步i,定義網(wǎng)絡(luò)Ti中具有最多孤立的潛在鄰居的節(jié)點(diǎn)為v,在其潛在鄰居中挑選一個節(jié)點(diǎn)ni加入到網(wǎng)絡(luò)Ti中.

步驟 3如圖1 所示,基于優(yōu)先連接的原則下,以Πi的連接概率選取網(wǎng)絡(luò)Ti中a個節(jié)點(diǎn)與節(jié)點(diǎn)ni進(jìn)行連接,并滿足a個節(jié)點(diǎn)均在節(jié)點(diǎn)ni的連通范圍內(nèi);若可選取的節(jié)點(diǎn)數(shù)小于a,則全部連接.連接概率Πi可通過下式求得:

其中,局部區(qū)域指以節(jié)點(diǎn)ni為圓心;r為半徑的連通范圍;kmax是默認(rèn)節(jié)點(diǎn)最大的度值;q是已經(jīng)達(dá)到kmax的節(jié)點(diǎn)的個數(shù);f(Ei) 是功能函數(shù),為了方便處理,這里取f(Ei)=1 .

步驟 4重復(fù)步驟2 和步驟 3,直至區(qū)域S內(nèi)的所有節(jié)點(diǎn)都被加入到網(wǎng)絡(luò)中.

從上述過程可以看出,在此模型中,雖然N個節(jié)點(diǎn)的位置開始就已經(jīng)確定了,但它們是一個一個加入到網(wǎng)絡(luò)中的,且它們的連邊是基于優(yōu)先連接的原則建立的,因此有少部分節(jié)點(diǎn)擁有大量的連接,而大多數(shù)節(jié)點(diǎn)的度則比較小.LAEE 網(wǎng)絡(luò)的度分布如圖2 所示.可以發(fā)現(xiàn)其度分布呈現(xiàn)冪律分布的特點(diǎn),是典型的異質(zhì)網(wǎng)絡(luò).

圖2 N=1500,〈 k〉 =8 時的LAEE 網(wǎng)絡(luò)的度分布Fig.2.Degree distribution of the LAEE network.N =1500,〈k〉=8.

2.2 隨機(jī)幾何圖模型

最簡單的空間網(wǎng)絡(luò)是隨機(jī)幾何圖模型[24].該模型主要分為以下3 個階段:

步驟1將N個節(jié)點(diǎn)隨機(jī)地分布在1 × 1 的區(qū)域S內(nèi).

步驟2 隨機(jī)選取一個節(jié)點(diǎn)i,以它為圓心,r為連通半徑,構(gòu)成一個圓形的連通區(qū)域.如圖3所示,節(jié)點(diǎn)i與其連通區(qū)域內(nèi)的全部節(jié)點(diǎn)建立連接.

圖3 節(jié)點(diǎn)i 與其連通區(qū)域內(nèi)的全部節(jié)點(diǎn)建立連接Fig.3.Node i connects all nodes in its connection area.

步驟3 重復(fù)步驟2,直至所有節(jié)點(diǎn)都與其連通半徑內(nèi)的所有節(jié)點(diǎn)建立連接.

2.3 改進(jìn)的隨機(jī)幾何圖模型

在節(jié)點(diǎn)數(shù)N與平均度〈k〉相同的情況下,隨機(jī)幾何圖模型的連通半徑要小于LAEE 演化模型.為了更公平地比較勻質(zhì)與異質(zhì)網(wǎng)絡(luò),我們希望兩個網(wǎng)絡(luò)模型中的連通半徑r相同.對此,本文在經(jīng)典的隨機(jī)幾何圖模型基礎(chǔ)上,提出一種改進(jìn)的隨機(jī)幾何圖模型.

網(wǎng)絡(luò)的生成如下所示:

步驟1將N個節(jié)點(diǎn)隨機(jī)的分布在 1×1 的區(qū)域S內(nèi).

步驟2隨機(jī)選取一個節(jié)點(diǎn)i,以節(jié)點(diǎn)i為圓心,r為連通半徑,構(gòu)成一個圓形的連通區(qū)域.如圖4 所示,定義連接概率p,節(jié)點(diǎn)i與其連通區(qū)域內(nèi)的節(jié)點(diǎn)以p概率建立連接.

圖4 節(jié)點(diǎn)i 與其連通范圍內(nèi)的節(jié)點(diǎn)以p 概率進(jìn)行連接Fig.4.Node i connects nodes within its connection range with probability p.

步驟3重復(fù)步驟2,直至所有節(jié)點(diǎn)都被遍歷到.

從上述過程可以看出,在改進(jìn)的隨機(jī)幾何圖模型中,每個節(jié)點(diǎn)的連接概率相同,不同節(jié)點(diǎn)之間不存在明顯的差異.該模型的度分布情況如圖5 所示.與LAEE 網(wǎng)絡(luò)相比,改進(jìn)的隨機(jī)幾何圖更接近勻質(zhì)網(wǎng)絡(luò).

圖5 N=1500,〈 k〉 =8 時改進(jìn)的隨機(jī)幾何圖的度分布Fig.5.Degree distribution of the improved random geometric graph.N=1500,〈 k〉=8.

3 路由策略

假設(shè)每個節(jié)點(diǎn)都具有相同的傳輸負(fù)載的能力.負(fù)載在網(wǎng)絡(luò)上的傳輸過程描述如下:在每一個時間步,網(wǎng)絡(luò)產(chǎn)生R個單位的負(fù)載,它們的源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)均隨機(jī)確定,根據(jù)路由策略由源節(jié)點(diǎn)向目的節(jié)點(diǎn)傳輸.每個節(jié)點(diǎn)在每個時間步中所能處理的最大負(fù)載量為C個單位的負(fù)載,為了便于問題的分析,假設(shè)C=1 .在每個時間步,負(fù)載只能向前傳輸一步,即從一個節(jié)點(diǎn)抵達(dá)至其鄰居節(jié)點(diǎn).當(dāng)負(fù)載到達(dá)目標(biāo)節(jié)點(diǎn)時,自動從網(wǎng)絡(luò)中刪除.用參數(shù)H(R)表示網(wǎng)絡(luò)的序參量[18]:

其中,ΔW=W(t+Δt)-W(t),Δt表示一個時間步的長度,W(t) 表示t時刻網(wǎng)絡(luò)中負(fù)載的總量.當(dāng)R較小時,所有的負(fù)載都能被及時處理,因此H(R)=0,這種狀態(tài)稱為自由流狀態(tài).如果R逐漸增大,使得在某個節(jié)點(diǎn)處每個時間步需要處理的負(fù)載量超過C,那么必然會有一部分負(fù)載無法被及時處理,此時H(R)＞0,即網(wǎng)絡(luò)出現(xiàn)擁塞現(xiàn)象.我們關(guān)心網(wǎng)絡(luò)從自由流狀態(tài)到擁塞狀態(tài)的相變點(diǎn)處的R值,稱為Rc,它表示網(wǎng)絡(luò)在不出現(xiàn)擁塞現(xiàn)象時最多能處理的負(fù)載量,即網(wǎng)絡(luò)的最大吞吐量.Rc的值一方面取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)具有不同的Rc;另一方面,Rc的值取決于所采用的路由方式.因此,本文將在具有不同拓?fù)浣Y(jié)構(gòu)的空間網(wǎng)絡(luò)模型下進(jìn)行仿真,并對比本文提出的路由方式與傳統(tǒng)的最少跳數(shù)路由方式.

3.1 傳統(tǒng)的最少跳數(shù)路由策略

在考慮負(fù)載傳輸時,經(jīng)常采用所謂的最短路徑路由.在一般的復(fù)雜網(wǎng)絡(luò)中,兩點(diǎn)之間的最短路徑通常指它們之間經(jīng)過最少連邊的路徑,即最少跳數(shù)路由.但是,在空間網(wǎng)絡(luò)中,所謂最短路徑可能有多種含義,例如跳數(shù)最少或者長度最短.為了不引起混淆,本文將通常意義下的最短路徑路由稱為“最少跳數(shù)路由”.

在采用最少跳數(shù)路由的情況下,可以用介數(shù)來描述各個節(jié)點(diǎn)的負(fù)載情況,任意一個節(jié)點(diǎn)v的介數(shù)表示如下[18]:

其中σst表示節(jié)點(diǎn)s到節(jié)點(diǎn)t的最少跳數(shù)路徑的數(shù)量,σst(v) 表示節(jié)點(diǎn)s到節(jié)點(diǎn)t的最少跳數(shù)路徑中經(jīng)過節(jié)點(diǎn)v的數(shù)量.當(dāng)R＜Rc時,網(wǎng)絡(luò)處于自由流狀態(tài),不會出現(xiàn)擁塞現(xiàn)象,單位時間到達(dá)節(jié)點(diǎn)v的負(fù)載為Rg(v)/[N(N -1)] ;當(dāng)R＞Rc時,網(wǎng)絡(luò)出現(xiàn)擁塞現(xiàn)象,假設(shè)在節(jié)點(diǎn)v處出現(xiàn)擁塞,此時Rg(v)/[N(N -1)]＞C.研究表明,擁塞最先發(fā)生在介數(shù)值最大的節(jié)點(diǎn)處.因此,Rc可表示為[18]

3.2 最短路徑長度路由策略

在空間網(wǎng)絡(luò)中,由于每個節(jié)點(diǎn)都有一個空間位置,因此每條連邊都有長度.簡單起見,考慮二維平面上的網(wǎng)絡(luò),那么對于連接節(jié)點(diǎn)i和j的連邊,其長度為

其中 (xi,yi) 與 (xj,yj) 分別為節(jié)點(diǎn)i和j的二維坐標(biāo).這樣,對于任意節(jié)點(diǎn)對 (s,t),可以定義它們之間的一條路徑的長度為這條路徑所經(jīng)過的所有連邊長度之和.即路徑

的長度為

在這些路徑中,長度最小的路徑被稱為最短長度路徑,而其長度被稱為最短路徑長度,采用最短長度路徑的路由策略稱為最短路徑長度路由.可以看到,這種路由策略只可能出現(xiàn)在空間網(wǎng)絡(luò)中,因?yàn)檫B邊長度乃至路徑長度的概念是建立在節(jié)點(diǎn)的空間坐標(biāo)基礎(chǔ)上的.

需要說明的是,采用最短路徑長度路由策略時,節(jié)點(diǎn)的介數(shù)仍可以采用類似(3)式的方法計(jì)算,但是式中的變量含義有所變化.具體地,σst表示節(jié)點(diǎn)s到節(jié)點(diǎn)t的具有最短長度的路徑的數(shù)量,σst(v)表示節(jié)點(diǎn)s到節(jié)點(diǎn)t的具有最短長度的路徑中經(jīng)過節(jié)點(diǎn)v的數(shù)量.

4 路由性能仿真及分析

為了檢驗(yàn)兩種路由策略的性能,采用前文提到的LAEE 演化模型和改進(jìn)的隨機(jī)幾何圖模型兩種空間網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn).其中,LAEE 演化模型產(chǎn)生具有無標(biāo)度特性的空間網(wǎng)絡(luò),是典型的異質(zhì)網(wǎng)絡(luò);而改進(jìn)的隨機(jī)幾何圖模型繼承了經(jīng)典隨機(jī)幾何圖模型的特點(diǎn),是典型的勻質(zhì)網(wǎng)絡(luò).

先將N個節(jié)點(diǎn)隨機(jī)地分布在1 × 1 的區(qū)域S內(nèi),由于空間位置的限制,節(jié)點(diǎn)i只能與以節(jié)點(diǎn)i為圓心,r為半徑的區(qū)域內(nèi)的潛在鄰居節(jié)點(diǎn)進(jìn)行連接.根據(jù)(5)式,可以計(jì)算出任意兩點(diǎn)之間的距離,找到節(jié)點(diǎn)i的所有潛在鄰居節(jié)點(diǎn),再根據(jù)LAEE與改進(jìn)的隨機(jī)幾何圖模型的生成規(guī)則,將節(jié)點(diǎn)i與其部分潛在鄰居節(jié)點(diǎn)連接,分別生成具有異質(zhì)與勻質(zhì)特性的空間網(wǎng)絡(luò).

對于網(wǎng)絡(luò)的任意節(jié)點(diǎn)對,其路徑可由(6)式來表示.在空間網(wǎng)絡(luò)的背景下,連邊被賦予了長度的屬性,通過(7)式可以得到任意節(jié)點(diǎn)對之間的路徑的長度,本文提出的最短路徑長度的路由正是基于(5)式—(7)式去尋找任意節(jié)點(diǎn)對 (s,t) 之間的最短長度的路徑,即 m inL(s →t) .傳統(tǒng)的最少跳數(shù)路由和最短路徑長度路由從不同角度刻畫了節(jié)點(diǎn)之間的“最短路徑”.接下來將通過仿真分析來比較兩種路由的性能,進(jìn)而確定那種路由效果更好.

首先對兩種路由策略下的拓?fù)渲笜?biāo)進(jìn)行分析.不同路由策略下平均路徑長度、平均跳數(shù)與節(jié)點(diǎn)數(shù)N的關(guān)系如圖6 和圖7 所示.可以看到,正如它們的名稱所示,最少跳數(shù)路由具有更小的平均跳數(shù),而最短路徑長度路由具有更小的平均路徑長度.比較兩種網(wǎng)絡(luò)可以發(fā)現(xiàn),結(jié)構(gòu)上異質(zhì)的LAEE網(wǎng)絡(luò)具有更短的平均路徑長度和更小的平均跳數(shù).這是因?yàn)長AEE 網(wǎng)絡(luò)中具有少量大度節(jié)點(diǎn),它們提供了傳輸?shù)慕輳?但是,在同一種網(wǎng)絡(luò)中,隨著節(jié)點(diǎn)數(shù)的增加,平均路徑長度略有減少,而平均跳數(shù)卻有所增加.這是因?yàn)樵诒ＷC平均度不變的前提下,隨著節(jié)點(diǎn)數(shù)的增加,連通半徑r是不斷減小的.這樣,平均來講,從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過的連邊數(shù)會增加.

圖6 平均度 〈 k〉=4 時,不同節(jié)點(diǎn)規(guī)模下兩種路由方式平均路徑長度的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.6.With the average degree 〈 k〉=4,the average path length under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

網(wǎng)絡(luò)最大吞吐量Rc與節(jié)點(diǎn)數(shù)N的關(guān)系如圖8所示.可以看出,無論在哪種網(wǎng)絡(luò)中,最短路徑長度路由都具有更大的Rc值,這說明采用最短路徑長度路由會有效提高空間網(wǎng)絡(luò)的吞吐量.當(dāng)然,如圖7 所示,最短路徑長度路由增加了平均跳數(shù),這將導(dǎo)致平均傳輸延時變長.也就是說,最短路徑長度路由提高空間網(wǎng)絡(luò)吞吐量是以增加傳輸延時為代價的.而比較兩種網(wǎng)絡(luò)發(fā)現(xiàn),結(jié)構(gòu)上異質(zhì)的LAEE 網(wǎng)絡(luò)具有更小的Rc值,這是因?yàn)楫愘|(zhì)網(wǎng)絡(luò)中的大度節(jié)點(diǎn)在提供傳輸捷徑的同時,不可避免地成為傳輸?shù)钠款i,制約了網(wǎng)絡(luò)的吞吐量.此外,網(wǎng)絡(luò)吞吐量隨著網(wǎng)絡(luò)規(guī)模增加而增大.

圖7 平均度 〈 k〉=4 時,不同節(jié)點(diǎn)規(guī)模下兩種路由方式平均跳數(shù)的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.7.With the average degree 〈 k〉=4,the average number of hops under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

圖8 平均度 〈 k〉=4 時,不同節(jié)點(diǎn)規(guī)模下兩種路由方式的網(wǎng)絡(luò)最大吞吐量 Rc 的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.8.With the average degree 〈 k〉=4 ,Rc under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

不同路由策略下平均路徑長度、平均跳數(shù)與平均度〈k〉的關(guān)系如圖9 和圖10 所示.與改變網(wǎng)絡(luò)規(guī)模類似,這里也可以看到,無論平均度如何變化,最少跳數(shù)路由總是具有更小的平均跳數(shù),而最短路徑長度路由總是具有更小的平均路徑長度.另一方面,隨著〈k〉的增加,網(wǎng)絡(luò)中的連邊數(shù)逐漸增加,各節(jié)點(diǎn)間路徑有了更多的選擇,因此傳輸?shù)穆窂介L度變短,平均跳數(shù)減小.

圖9 節(jié)點(diǎn)數(shù) N =1000 時,不同平均度下兩種路由方式平均路徑長度的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.9.With N=1000,the average path length under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

圖10 節(jié)點(diǎn)數(shù) N =1000 時,不同平均度下兩種路由方式平均跳數(shù)的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.10.With N=1000,the average number of hops under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

圖11 給出了網(wǎng)絡(luò)最大吞吐量Rc隨平均度〈k〉的變化情況.總體來看,最短路徑長度路由總是具有更大的Rc值.而隨著平均度的不斷增大,網(wǎng)絡(luò)連接越來越稠密,負(fù)載傳輸?shù)穆窂皆絹碓骄鶆虻胤植荚诰W(wǎng)絡(luò)中,結(jié)果是導(dǎo)致Rc值的迅速增加,即網(wǎng)絡(luò)吞吐量迅速變大.

圖11 節(jié)點(diǎn)數(shù) N =1000 時,不同平均度下兩種路由方式的網(wǎng)絡(luò)最大吞吐量 Rc 的比較 (a) LAEE 演化模型;(b)改進(jìn)的隨機(jī)幾何圖模型.圖中每個點(diǎn)是10 次仿真的平均值Fig.11.With N =1000 ,R c under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

圖12 和圖13 分別給出了兩種網(wǎng)絡(luò)在采用兩種路由策略時的介數(shù)分布.可以看出,無論哪種網(wǎng)絡(luò),采用最短路徑長度路由時的最大介數(shù)值都比采用最少跳數(shù)路由時的最大介數(shù)小.正是這個更小的最大介數(shù),導(dǎo)致最短路徑長度路由具有更大的Rc.那么,為什么最短路徑長度路由會導(dǎo)致更小的最大介數(shù)呢? 這是因?yàn)椴捎米疃搪窂介L度路由時,為了保證路徑長度盡可能短,所遵循的路徑更接近于直線,所以所謂網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的作用并不突出.相比之下,最少跳數(shù)路由追求更少的跳數(shù),網(wǎng)絡(luò)中少量關(guān)鍵節(jié)點(diǎn)往往起到中介的作用,匯聚了大量的路徑,導(dǎo)致最大介數(shù)更大.綜上所述,最短路徑長度路由能使網(wǎng)絡(luò)傳輸?shù)呢?fù)載得到更加合理的分布,從而使網(wǎng)絡(luò)具有更大的吞吐量,是一種更加有效的路由策略.

圖12 LAEE 演化模型中,節(jié)點(diǎn)數(shù)N=1000,〈 k〉=4 時的介數(shù)分布 (a)最少跳數(shù)路由;(b)最短路徑長度路由Fig.12.Betweenness distribution of the LAEE network with N=1000,〈 k〉 =4:(a) Least number of hops routing strategy;(b) shortest path length routing strategy.

圖13 改進(jìn)的隨機(jī)幾何圖模型中,節(jié)點(diǎn)數(shù)N=1000,〈 k〉 =4 時的介數(shù)分布 (a)最少跳數(shù)路由;(b)最短路徑長度路由Fig.13.Betweenness distribution of the improved random geometric graph with N=1000,〈 k〉 =4:(a) Least number of hops routing strategy;(b) shortest path length routing strategy.

5 結(jié)論

在空間網(wǎng)絡(luò)中,“最短路徑”可以有不同的解讀,傳統(tǒng)的最短路徑等效于跳數(shù)最少的路徑.而空間網(wǎng)絡(luò)中由于連邊具有長度屬性,最短路徑也可以理解為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過的所有連邊的長度之和(即路徑長度)最短.本文提出的最短路徑長度路由策略就是基于后者.通過在勻質(zhì)和異質(zhì)空間網(wǎng)絡(luò)上的仿真發(fā)現(xiàn),這種新路由策略能夠有效提升網(wǎng)絡(luò)最大吞吐量.本文提出的路由策略對現(xiàn)實(shí)生活中交通運(yùn)輸、無線通信網(wǎng)絡(luò)等都具有很好的借鑒意義.