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

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

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

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

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