《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 一種無標(biāo)度網(wǎng)絡(luò)上的局部路由策略
一種無標(biāo)度網(wǎng)絡(luò)上的局部路由策略
Icbuy
Icbuy
摘要:   由于以因特網(wǎng)為代表的大型通信網(wǎng)絡(luò),如:生物細(xì)胞蛋白質(zhì)交互作用網(wǎng)、科學(xué)家合作網(wǎng)、航空運(yùn)輸網(wǎng)等許多現(xiàn)實(shí)中的網(wǎng)絡(luò)都被證明具有小世界網(wǎng)絡(luò)特點(diǎn)及無標(biāo)度(scale-free)的連接特性,復(fù)雜網(wǎng)絡(luò)的構(gòu)造及其動(dòng)力學(xué)機(jī)制的研究問題日益引起人們的關(guān)注。對于以交流為目的的網(wǎng)絡(luò)來說,人們最為關(guān)心的是如何實(shí)現(xiàn)無擁塞的信息交互,所以在scale-free這種基本連接結(jié)構(gòu)之上的網(wǎng)絡(luò)中信息流傳輸問題也逐漸成為研究的熱點(diǎn)。
Abstract:
Key words :
  0 引言

  由于以因特網(wǎng)為代表的大型通信網(wǎng)絡(luò),如:生物細(xì)胞蛋白質(zhì)交互作用網(wǎng)、科學(xué)家合作網(wǎng)、航空運(yùn)輸網(wǎng)等許多現(xiàn)實(shí)中的網(wǎng)絡(luò)都被證明具有小世界網(wǎng)絡(luò)特點(diǎn)及無標(biāo)度(scale-free)的連接特性,復(fù)雜網(wǎng)絡(luò)的構(gòu)造及其動(dòng)力學(xué)機(jī)制的研究問題日益引起人們的關(guān)注。對于以交流為目的的網(wǎng)絡(luò)來說,人們最為關(guān)心的是如何實(shí)現(xiàn)無擁塞的信息交互,所以在scale-free這種基本連接結(jié)構(gòu)之上的網(wǎng)絡(luò)中信息流傳輸問題也逐漸成為研究的熱點(diǎn)。

  為實(shí)現(xiàn)高效的信息傳輸,已經(jīng)有許多研究都致力于提出更好的路由策略。有些文章提出了根據(jù)全局拓?fù)溥B接信息進(jìn)行路由選擇判斷的機(jī)制。這對于試驗(yàn)性質(zhì)的中小型網(wǎng)絡(luò)或許適用,但對于類似因特網(wǎng)規(guī)模的網(wǎng)絡(luò)或者高動(dòng)態(tài)性的連接結(jié)構(gòu)不斷變化的無線網(wǎng)絡(luò)而言,這種路由策略所需的巨大的計(jì)算量以及能量消耗是不可能得到滿足的。

  因此人們開始關(guān)注局部路由策略。隨機(jī)游走策略是最原始的局部路由策略,但是由于隨機(jī)游走的方法過于簡單,在網(wǎng)絡(luò)中實(shí)際效果很差。王文旭等人提出一種局部路由策略,發(fā)送節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的連結(jié)度和策略指定的度指數(shù)計(jì)算轉(zhuǎn)發(fā)概率,做出路由選擇,由于其策略固定偏好因子進(jìn)行路由選擇,所以稱之為靜態(tài)偏好局部路由策略。

  本文的局部路由策略設(shè)定了發(fā)送方根據(jù)鄰居節(jié)點(diǎn)動(dòng)態(tài)變化的負(fù)載與固定的發(fā)送能力的關(guān)系,自適應(yīng)地調(diào)整各個(gè)鄰居節(jié)點(diǎn)的偏好因子。首先,使網(wǎng)絡(luò)信息流量適度地向度大的節(jié)點(diǎn)集中,增大了對度大節(jié)點(diǎn)的利用率,從而有效地減少了網(wǎng)絡(luò)中信息包的平均傳輸時(shí)延;其次,在業(yè)務(wù)增大時(shí)進(jìn)行分流,避免部分度大節(jié)點(diǎn)的過飽和帶來整個(gè)網(wǎng)絡(luò)的擁塞,盡量做到充分利用所有節(jié)點(diǎn)的發(fā)送能力,提高網(wǎng)絡(luò)容量。

  1 模型及定義

  為了不失一般性選擇由Barabdsi與Albert提出的B—A模型作為網(wǎng)絡(luò)基本構(gòu)造,模型產(chǎn)生方法與文獻(xiàn)相同,其節(jié)點(diǎn)的度分布具有冪率特性,即p(k)~k-y,y=3。

  由于在無標(biāo)度網(wǎng)絡(luò)中,度大的節(jié)點(diǎn)具有較大的介數(shù),是連接各節(jié)點(diǎn)對的最短路徑集中通過的關(guān)鍵節(jié)點(diǎn),所以應(yīng)該盡量使用度大的節(jié)點(diǎn)進(jìn)行通信,便于迅速查找目的地(后文稱scale-free網(wǎng)絡(luò)中度較大的節(jié)點(diǎn)為hub節(jié)點(diǎn));而當(dāng)業(yè)務(wù)加重時(shí),為了避免在hub節(jié)點(diǎn)處造成擁塞,應(yīng)該適當(dāng)?shù)姆至鳌R虼嗽谛畔a(chǎn)生速率不高且所有節(jié)點(diǎn)均未飽和時(shí),應(yīng)該使得度大的節(jié)點(diǎn)具有較大地接收信息包的偏好概率;而在度大的節(jié)點(diǎn)飽和后,就根據(jù)其負(fù)載狀況減小其接受概率,把業(yè)務(wù)流轉(zhuǎn)移至負(fù)載輕尚空余有發(fā)送能力未被利用的節(jié)點(diǎn)。

  業(yè)務(wù)傳輸過程定義如下:

  (1)每一時(shí)刻開始有R個(gè)信息包生成于網(wǎng)絡(luò)中,即此時(shí)信息包產(chǎn)生速率為R,隨機(jī)地為每個(gè)新產(chǎn)生的包選擇源節(jié)點(diǎn)和目的節(jié)點(diǎn)。

  (2)每一個(gè)節(jié)點(diǎn)均具有無限大的存儲空間容納信息包,信息包隊(duì)列服從先進(jìn)先出的原則,節(jié)點(diǎn)i的發(fā)送能力固定為節(jié)點(diǎn)連結(jié)度ki。

  (3)網(wǎng)絡(luò)中所有節(jié)點(diǎn)同時(shí)為其緩存內(nèi)將要發(fā)送的每個(gè)信息包分別進(jìn)行下一跳目的地的搜索并發(fā)送。如果信息包的目的節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn),則直接把這個(gè)包發(fā)往其目的節(jié)點(diǎn),并從網(wǎng)絡(luò)中消除該信息包。否則,就在所有鄰居節(jié)點(diǎn)中進(jìn)行偏好選擇,把信息包發(fā)往鄰居節(jié)點(diǎn)i的概率是:

a.jpg

  式中:ki是節(jié)點(diǎn)i的度;ai是節(jié)點(diǎn)i的自適應(yīng)可調(diào)選擇指數(shù)(后稱偏好因子),在初始時(shí)刻所有節(jié)點(diǎn)的偏好因子都是0。分母是對發(fā)送方的所有鄰居點(diǎn)求和。

  (4)更新網(wǎng)絡(luò)中所有節(jié)點(diǎn)的偏好因子。自適應(yīng)變化過程如下:當(dāng)節(jié)點(diǎn)i時(shí)刻存儲的信息包隊(duì)列長度小于其發(fā)送能力ki時(shí),其偏好因子ai就增大一個(gè)步長λ;反之,當(dāng)節(jié)點(diǎn)i時(shí)刻存儲的隊(duì)列長度超過其發(fā)送能力ki時(shí),其偏好因子ai就減小一個(gè)步長λ。同時(shí)為偏好因子設(shè)定上下限amax(>0),amin(  在每一時(shí)刻都順序執(zhí)行步驟(1)~(4)完成業(yè)務(wù)傳輸。

  設(shè)定界限amax,amin的原因是考慮到當(dāng)偏好因子增長的過大時(shí),度大節(jié)點(diǎn)的偏好概率會遠(yuǎn)遠(yuǎn)大于度較小的節(jié)點(diǎn),信息包會全部盡量涌向度較大的節(jié)點(diǎn),向度小節(jié)點(diǎn)轉(zhuǎn)移的概率極低,不利于在整個(gè)網(wǎng)絡(luò)內(nèi)搜索目的節(jié)點(diǎn),所以要為ai設(shè)定上限amax;而偏好因子如果變?yōu)檩^小的負(fù)值,就意味著信息會盡量選擇度小的末梢點(diǎn)作為傳輸對象,完全避開hub節(jié)點(diǎn)將導(dǎo)致信息包傳輸時(shí)延大大增加,所以也要為ai設(shè)定下限amin。

  2 路由方法分析

  考察scale-free網(wǎng)絡(luò)路由策略性能的最主要指標(biāo)是網(wǎng)絡(luò)容量,通常用網(wǎng)絡(luò)不擁塞時(shí)可以達(dá)到的最大信息包產(chǎn)生速率Rc(又稱臨界速率)來衡量。

  在任一信息包產(chǎn)生速率下,如果只是每次進(jìn)入部分節(jié)點(diǎn)的信息包隊(duì)列長度超過了節(jié)點(diǎn)發(fā)送能力,使信息包堆積,導(dǎo)致了擁塞的發(fā)生(后文稱之為節(jié)點(diǎn)過飽和),那么只需把這部分業(yè)務(wù)轉(zhuǎn)移到尚未飽和的節(jié)點(diǎn)中去,就可以緩解這種局部負(fù)載過重帶來的擁塞,并且可以進(jìn)一步擴(kuò)大產(chǎn)生速率。只有當(dāng)全部節(jié)點(diǎn)均達(dá)到了飽和,整個(gè)網(wǎng)絡(luò)擁塞的發(fā)生才是無可避免的。所以目的就是避免局部節(jié)點(diǎn)擁堵帶來網(wǎng)絡(luò)擁塞,盡量提高網(wǎng)絡(luò)容量,最后全部節(jié)點(diǎn)可以同步地達(dá)到飽和狀態(tài)。

  設(shè)定節(jié)點(diǎn)發(fā)送能力等于其連接度,首先使度大節(jié)點(diǎn)有較大的偏好概率,以大業(yè)務(wù)流進(jìn)入速率把負(fù)載優(yōu)先分配給度大的節(jié)點(diǎn)進(jìn)行存儲轉(zhuǎn)發(fā),搜索目的地;當(dāng)度大節(jié)點(diǎn)的負(fù)載等于甚至超過發(fā)送能力(后文稱之為飽和)后,自適應(yīng)地調(diào)整其信息進(jìn)入速率,把業(yè)務(wù)向尚未飽和的度較小的節(jié)點(diǎn)轉(zhuǎn)移,避免度大的節(jié)點(diǎn)過早進(jìn)入擁塞狀態(tài)。

  注意到在本策略定義的自適應(yīng)傳輸機(jī)制下,l(ki)的長度從0開始逐漸增長,當(dāng)l(ki)≤ki時(shí),每次發(fā)送完成后不會有信息包在節(jié)點(diǎn)內(nèi)滯留,所以節(jié)點(diǎn)處于未飽和平穩(wěn)狀態(tài);反之,若l(ki)>ki,信息包會不斷在節(jié)點(diǎn)堆積,節(jié)點(diǎn)就處在過飽和擁塞狀態(tài)。所以稱l(k)=k為節(jié)點(diǎn)未飽和與過飽和的相分界線。

  在自適應(yīng)策略下,選取任何非負(fù)的偏好因子上限amax都能得到相同的最大網(wǎng)絡(luò)容量Rc_max。這是因?yàn)樽赃m應(yīng)策略根據(jù)節(jié)點(diǎn)的負(fù)載與發(fā)送能力的關(guān)系不斷變化偏好因子ai,進(jìn)而調(diào)整信息流的進(jìn)入速率,不斷向未飽和的節(jié)點(diǎn)分流信息包,從而使信息包不會在飽和節(jié)點(diǎn)處不斷積累增加,避免節(jié)點(diǎn)達(dá)到過飽和造成全局擁塞。未飽和節(jié)點(diǎn),由于隊(duì)列長度一直滿足l(ki)≤ki,其偏好因子ai均會隨時(shí)間不斷增長,直至等于其上限amax,不會減??;達(dá)到相分界線的飽和節(jié)點(diǎn),其偏好因子不再保持等于上限amax,而是隨負(fù)載的變化波動(dòng)。在自適應(yīng)調(diào)整偏好因子的反饋?zhàn)饔孟拢柡凸?jié)點(diǎn)的信息包進(jìn)入速率將基本等于發(fā)送能力,即平均隊(duì)列長度穩(wěn)定在相分界線l(ki)=ki上,由于相分界線斜率為1,參考式(1),得出飽和節(jié)點(diǎn)的偏好因子接近于0。同時(shí)考慮到,當(dāng)所有節(jié)點(diǎn)都達(dá)到飽和,偏好因子ai均接近于0時(shí),網(wǎng)絡(luò)達(dá)到最大容量。因此在任何偏好因子的界限amax下,網(wǎng)絡(luò)均有惟一相同的最大容量Rc_max。

  圖1反映的是不同發(fā)送速率下,節(jié)點(diǎn)平均隊(duì)列長度的變化情況。圖中粗直線代表的就是相分界線。節(jié)點(diǎn)均未飽和時(shí),反映在圖中就是l(ki)未接觸相分界線,此時(shí)l(ki)服從式(1)。隨著R增加,部分節(jié)點(diǎn)接觸相分界線后開始進(jìn)入飽和狀態(tài),l(ki)也開始分為兩段。度較大的一部分飽和節(jié)點(diǎn)的平均隊(duì)列長度與相分界線完全重合,平均隊(duì)列長度變?yōu)閘(ki)=ki;另一部分節(jié)點(diǎn)未達(dá)到飽和狀態(tài),平均隊(duì)列長度保持原來的斜率,即b.jpg。

c.jpg

  隨著R的增加,l(ki)與相分界線重合部分增加。當(dāng)所有節(jié)點(diǎn)均達(dá)到飽和,即l(ki)與相分界線完全重合時(shí),所有節(jié)點(diǎn)的偏好因子的均值均達(dá)到0,網(wǎng)絡(luò)達(dá)到最大容量,此時(shí)的R就是最大臨界發(fā)送速率Rc。

  3 仿真結(jié)果

  首先觀察采用自適應(yīng)策略后網(wǎng)絡(luò)容量的變化情況。為了精確地找出臨界發(fā)送速率,利用了以下序參量:

d.jpg

  式中:△Np=N(t+△t)-N(t)是一段時(shí)間△t內(nèi)網(wǎng)絡(luò)總包數(shù)的變化;<>意味著選取足夠多的時(shí)間段計(jì)算得出的平均值;η(R)可以視為網(wǎng)絡(luò)內(nèi)總包數(shù)的變化率。

  圖2反映靜態(tài)局部路由策略和本文提出的自適應(yīng)局部路由策略不同R對應(yīng)的η變化。ai=0,0.4,0.8代表在靜態(tài)偏好局部路由策略下,網(wǎng)絡(luò)中所有節(jié)點(diǎn)的優(yōu)化因子的選擇情況。amax=0.4,amin=-0.4;amax=0.8,amin=-0.8;amax=1,amin=-1代表在自適應(yīng)局部路由策略下優(yōu)化因子上下限選擇情況。從η的數(shù)值變化可以看到,在靜態(tài)偏好局部路由策略下,只有在選取ai=0時(shí),具有最大的臨界發(fā)送速率,固定優(yōu)化因子ai為其他值時(shí)所得到的Rc均無法達(dá)到這一最大值。按照本文提出的自適應(yīng)局部路由策略,在為ai選取不同的amax,amin的時(shí)候,均超過靜態(tài)策略的Rc可以獲得相同的最大Rc_max。

e.jpg

  反映網(wǎng)絡(luò)路由策略效能的另一個(gè)重要指標(biāo)就是信息包的平均傳輸時(shí)延。圖3反映的是采用自適應(yīng)路由策略、靜態(tài)偏好路由策略,以及王文旭等提出的結(jié)合動(dòng)態(tài)和靜態(tài)信息的路由策略得到的不同平均傳輸時(shí)延。

  圖3中,β=-3代表結(jié)合動(dòng)態(tài)和靜態(tài)信息的局部路由策略,及其關(guān)鍵參數(shù)的選取情況,具體可參見文獻(xiàn)。ai=0代表在靜態(tài)偏好局部路由策略,amax=0.4,amin=-0.4,amax=1,amin=-1,amax=1.5,amin=-1.5,分別代表在本文提出的局部路由策略下網(wǎng)絡(luò)中所有節(jié)點(diǎn)的優(yōu)化因子的上下限。可以看到,結(jié)合動(dòng)態(tài)和靜態(tài)信息的局部路由策略在R較小時(shí)可以保持較低的傳輸時(shí)延,但是隨著發(fā)送速率的增加,平均傳輸時(shí)延也迅速增大。靜態(tài)路由策略(ai=0時(shí))的傳輸時(shí)延在接近臨界發(fā)送速率前隨發(fā)送速率逐漸增大。

f.jpg

  從圖3可以看到,本文提出的自適應(yīng)局部路由策略的平均傳輸時(shí)延受到不同的amax的影響。在接近臨界狀態(tài)時(shí)采用本文策略的平均傳輸時(shí)延明顯小于原有策略。

  4 結(jié)語

  本文提出了一種自適應(yīng)的無標(biāo)度網(wǎng)絡(luò)上的局部路由策略。每個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率由節(jié)點(diǎn)度k及偏好因子a共同決定。偏好因子a值根據(jù)每個(gè)節(jié)點(diǎn)自身的緩存平均隊(duì)列長度自適應(yīng)變化,當(dāng)節(jié)點(diǎn)緩存平均隊(duì)列長度大于發(fā)送能力(等于節(jié)點(diǎn)度k)時(shí),a增加;反之,則減小。a的上下限amax,amin可調(diào),并且互為相反數(shù)。當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)均未飽和時(shí),不同度節(jié)點(diǎn)的偏好因子基本都達(dá)到上限amax;當(dāng)部分節(jié)點(diǎn)達(dá)到飽和時(shí),這些節(jié)點(diǎn)的偏好因子顯示出a=0的統(tǒng)計(jì)特性,其余節(jié)點(diǎn)的偏好因子仍基本保持為amax。這使得一方面無論網(wǎng)絡(luò)業(yè)務(wù)輕重時(shí),都可以保證網(wǎng)絡(luò)信息流量優(yōu)先地向hub節(jié)點(diǎn)集中,連接度大的節(jié)點(diǎn)得到充分的利用;另一方面能夠使節(jié)點(diǎn)發(fā)送能力得到恰當(dāng)?shù)氖褂枚粫_(dá)到“過飽和”狀態(tài),自適應(yīng)地避免擁塞的發(fā)生。仿真結(jié)果表明,為偏好因子選擇不同的上下限時(shí),本策略都能使所有節(jié)點(diǎn)同步飽和,以達(dá)到網(wǎng)絡(luò)的最大臨界發(fā)送速率;基于對hub節(jié)點(diǎn)的適度優(yōu)先利用,本文提出的自適應(yīng)局部路由策略,可以獲得比靜態(tài)偏好局部路由策略、結(jié)合動(dòng)態(tài)和靜態(tài)信息的局部路由策略更小的平均信息包傳輸時(shí)延。




 

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。