一種無標度網絡上的局部路由策略

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

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

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

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