一種無標(biāo)度網(wǎng)絡(luò)上的局部路由策略

摘要：提出了一種無標(biāo)度(scale-free)網(wǎng)絡(luò)上的局部路由策略。每個節(jié)點根據(jù)其當(dāng)前負(fù)載與自身發(fā)送能力(設(shè)為等于節(jié)點度)的關(guān)系，自適應(yīng)調(diào)整其接收鄰居節(jié)點信息包的概率。此概率與每個節(jié)點度的a次方成正比，a是可自適應(yīng)變化的偏好因子，由節(jié)點度以及負(fù)載聯(lián)合決定。當(dāng)節(jié)點負(fù)載小于發(fā)送能力時，增大其偏好因子；反之，則減小。這樣使得整個網(wǎng)絡(luò)業(yè)務(wù)量較小時，可以優(yōu)先把業(yè)務(wù)轉(zhuǎn)發(fā)往度較大的節(jié)點，從而更快到達(dá)目的地；而業(yè)務(wù)量較大時，度大以及度小節(jié)點的發(fā)送能力均能得到充分利用，從而提高了整個網(wǎng)絡(luò)的業(yè)務(wù)承載能力。仿真結(jié)果表明，該策略有效地提高了網(wǎng)絡(luò)容量，并且降低了網(wǎng)絡(luò)中信息包的平均傳輸時延。
關(guān)鍵詞：無標(biāo)度網(wǎng)絡(luò)；自適應(yīng)；偏好概率；網(wǎng)絡(luò)容量；路由策略

0 引言
由于以因特網(wǎng)為代表的大型通信網(wǎng)絡(luò)，如：生物細(xì)胞蛋白質(zhì)交互作用網(wǎng)、科學(xué)家合作網(wǎng)、航空運輸網(wǎng)等許多現(xiàn)實中的網(wǎng)絡(luò)都被證明具有小世界網(wǎng)絡(luò)特點及無標(biāo)度(scale-free)的連接特性，復(fù)雜網(wǎng)絡(luò)的構(gòu)造及其動力學(xué)機制的研究問題日益引起人們的關(guān)注。對于以交流為目的的網(wǎng)絡(luò)來說，人們最為關(guān)心的是如何實現(xiàn)無擁塞的信息交互，所以在scale-free這種基本連接結(jié)構(gòu)之上的網(wǎng)絡(luò)中信息流傳輸問題也逐漸成為研究的熱點。
為實現(xiàn)高效的信息傳輸，已經(jīng)有許多研究都致力于提出更好的路由策略。有些文章提出了根據(jù)全局拓?fù)溥B接信息進行路由選擇判斷的機制。這對于試驗性質(zhì)的中小型網(wǎng)絡(luò)或許適用，但對于類似因特網(wǎng)規(guī)模的網(wǎng)絡(luò)或者高動態(tài)性的連接結(jié)構(gòu)不斷變化的無線網(wǎng)絡(luò)而言，這種路由策略所需的巨大的計算量以及能量消耗是不可能得到滿足的。
因此人們開始關(guān)注局部路由策略。隨機游走策略是最原始的局部路由策略，但是由于隨機游走的方法過于簡單，在網(wǎng)絡(luò)中實際效果很差。王文旭等人提出一種局部路由策略，發(fā)送節(jié)點根據(jù)鄰居節(jié)點的連結(jié)度和策略指定的度指數(shù)計算轉(zhuǎn)發(fā)概率，做出路由選擇，由于其策略固定偏好因子進行路由選擇，所以稱之為靜態(tài)偏好局部路由策略。
本文的局部路由策略設(shè)定了發(fā)送方根據(jù)鄰居節(jié)點動態(tài)變化的負(fù)載與固定的發(fā)送能力的關(guān)系，自適應(yīng)地調(diào)整各個鄰居節(jié)點的偏好因子。首先，使網(wǎng)絡(luò)信息流量適度地向度大的節(jié)點集中，增大了對度大節(jié)點的利用率，從而有效地減少了網(wǎng)絡(luò)中信息包的平均傳輸時延；其次，在業(yè)務(wù)增大時進行分流，避免部分度大節(jié)點的過飽和帶來整個網(wǎng)絡(luò)的擁塞，盡量做到充分利用所有節(jié)點的發(fā)送能力，提高網(wǎng)絡(luò)容量。

1 模型及定義
為了不失一般性選擇由Barabdsi與Albert提出的B—A模型作為網(wǎng)絡(luò)基本構(gòu)造，模型產(chǎn)生方法與文獻相同，其節(jié)點的度分布具有冪率特性，即p(k)～k-y，y=3。
由于在無標(biāo)度網(wǎng)絡(luò)中，度大的節(jié)點具有較大的介數(shù)，是連接各節(jié)點對的最短路徑集中通過的關(guān)鍵節(jié)點，所以應(yīng)該盡量使用度大的節(jié)點進行通信，便于迅速查找目的地(后文稱scale-free網(wǎng)絡(luò)中度較大的節(jié)點為hub節(jié)點)；而當(dāng)業(yè)務(wù)加重時，為了避免在hub節(jié)點處造成擁塞，應(yīng)該適當(dāng)?shù)姆至鳌Ｒ虼嗽谛畔a(chǎn)生速率不高且所有節(jié)點均未飽和時，應(yīng)該使得度大的節(jié)點具有較大地接收信息包的偏好概率；而在度大的節(jié)點飽和后，就根據(jù)其負(fù)載狀況減小其接受概率，把業(yè)務(wù)流轉(zhuǎn)移至負(fù)載輕尚空余有發(fā)送能力未被利用的節(jié)點。
業(yè)務(wù)傳輸過程定義如下：
(1)每一時刻開始有R個信息包生成于網(wǎng)絡(luò)中，即此時信息包產(chǎn)生速率為R，隨機地為每個新產(chǎn)生的包選擇源節(jié)點和目的節(jié)點。
(2)每一個節(jié)點均具有無限大的存儲空間容納信息包，信息包隊列服從先進先出的原則，節(jié)點i的發(fā)送能力固定為節(jié)點連結(jié)度ki。
(3)網(wǎng)絡(luò)中所有節(jié)點同時為其緩存內(nèi)將要發(fā)送的每個信息包分別進行下一跳目的地的搜索并發(fā)送。如果信息包的目的節(jié)點是當(dāng)前節(jié)點的鄰居節(jié)點，則直接把這個包發(fā)往其目的節(jié)點，并從網(wǎng)絡(luò)中消除該信息包。否則，就在所有鄰居節(jié)點中進行偏好選擇，把信息包發(fā)往鄰居節(jié)點i的概率是：

式中：ki是節(jié)點i的度；ai是節(jié)點i的自適應(yīng)可調(diào)選擇指數(shù)(后稱偏好因子)，在初始時刻所有節(jié)點的偏好因子都是0。分母是對發(fā)送方的所有鄰居點求和。
(4)更新網(wǎng)絡(luò)中所有節(jié)點的偏好因子。自適應(yīng)變化過程如下：當(dāng)節(jié)點i時刻存儲的信息包隊列長度小于其發(fā)送能力ki時，其偏好因子ai就增大一個步長λ；反之，當(dāng)節(jié)點i時刻存儲的隊列長度超過其發(fā)送能力ki時，其偏好因子ai就減小一個步長λ。同時為偏好因子設(shè)定上下限amax(>0)，amin(O)，ai的增長或減小不可以越過界限，并且選取amax=-amin。。為了使具有不同負(fù)載節(jié)點的偏好概率之間有明顯的區(qū)分，偏好因子的變化步長λ可以取作amax的1／20～1／100之間。
在每一時刻都順序執(zhí)行步驟(1)～(4)完成業(yè)務(wù)傳輸。
設(shè)定界限amax，amin的原因是考慮到當(dāng)偏好因子增長的過大時，度大節(jié)點的偏好概率會遠(yuǎn)遠(yuǎn)大于度較小的節(jié)點，信息包會全部盡量涌向度較大的節(jié)點，向度小節(jié)點轉(zhuǎn)移的概率極低，不利于在整個網(wǎng)絡(luò)內(nèi)搜索目的節(jié)點，所以要為ai設(shè)定上限amax；而偏好因子如果變?yōu)檩^小的負(fù)值，就意味著信息會盡量選擇度小的末梢點作為傳輸對象，完全避開hub節(jié)點將導(dǎo)致信息包傳輸時延大大增加，所以也要為ai設(shè)定下限amin。