由于以因特網為代表的大型通信網絡，如：生物細胞蛋白質交互作用網、科學家合作網、航空運輸網等許多現實中的網絡都被證明具有小世界網絡特點及無標度(scale-free)的連接特性，復雜網絡的構造及其動力學機制的研究問題日益引起人們的關注。對于以交流為目的的網絡來說，人們最為關心的是如何實現無擁塞的信息交互，所以在scale-free這種基本連接結構之上的網絡中信息流傳輸問題也逐漸成為研究的熱點。
為實現高效的信息傳輸，已經有許多研究都致力于提出更好的路由策略。有些文章提出了根據全局拓撲連接信息進行路由選擇判斷的機制。這對于試驗性質的中小型網絡或許適用，但對于類似因特網規(guī)模的網絡或者高動態(tài)性的連接結構不斷變化的無線網絡而言，這種路由策略所需的巨大的計算量以及能量消耗是不可能得到滿足的。
因此人們開始關注局部路由策略。隨機游走策略是最原始的局部路由策略，但是由于隨機游走的方法過于簡單，在網絡中實際效果很差。王文旭等人提出一種局部路由策略，發(fā)送節(jié)點根據鄰居節(jié)點的連結度和策略指定的度指數計算轉發(fā)概率，做出路由選擇，由于其策略固定偏好因子進行路由選擇，所以稱之為靜態(tài)偏好局部路由策略。
本文的局部路由策略設定了發(fā)送方根據鄰居節(jié)點動態(tài)變化的負載與固定的發(fā)送能力的關系，自適應地調整各個鄰居節(jié)點的偏好因子。首先，使網絡信息流量適度地向度大的節(jié)點集中，增大了對度大節(jié)點的利用率，從而有效地減少了網絡中信息包的平均傳輸時延；其次，在業(yè)務增大時進行分流，避免部分度大節(jié)點的過飽和帶來整個網絡的擁塞，盡量做到充分利用所有節(jié)點的發(fā)送能力，提高網絡容量。
1 模型及定義
為了不失一般性選擇由Barabdsi與Albert提出的B—A模型作為網絡基本構造，模型產生方法與文獻相同，其節(jié)點的度分布具有冪率特性，即p(k)～k-y，y=3。
由于在無標度網絡中，度大的節(jié)點具有較大的介數，是連接各節(jié)點對的最短路徑集中通過的關鍵節(jié)點，所以應該盡量使用度大的節(jié)點進行通信，便于迅速查找目的地(后文稱scale-free網絡中度較大的節(jié)點為hub節(jié)點)；而當業(yè)務加重時，為了避免在hub節(jié)點處造成擁塞，應該適當的分流。因此在信息包產生速率不高且所有節(jié)點均未飽和時，應該使得度大的節(jié)點具有較大地接收信息包的偏好概率；而在度大的節(jié)點飽和后，就根據其負載狀況減小其接受概率，把業(yè)務流轉移至負載輕尚空余有發(fā)送能力未被利用的節(jié)點。
業(yè)務傳輸過程定義如下：
(1)每一時刻開始有R個信息包生成于網絡中，即此時信息包產生速率為R，隨機地為每個新產生的包選擇源節(jié)點和目的節(jié)點。
(2)每一個節(jié)點均具有無限大的存儲空間容納信息包，信息包隊列服從先進先出的原則，節(jié)點i的發(fā)送能力固定為節(jié)點連結度ki。
(3)網絡中所有節(jié)點同時為其緩存內將要發(fā)送的每個信息包分別進行下一跳目的地的搜索并發(fā)送。如果信息包的目的節(jié)點是當前節(jié)點的鄰居節(jié)點，則直接把這個包發(fā)往其目的節(jié)點，并從網絡中消除該信息包。否則，就在所有鄰居節(jié)點中進行偏好選擇，把信息包發(fā)往鄰居節(jié)點i的概率是：
式中：ki是節(jié)點i的度；ai是節(jié)點i的自適應可調選擇指數(后稱偏好因子)，在初始時刻所有節(jié)點的偏好因子都是0。分母是對發(fā)送方的所有鄰居點求和。
(4)更新網絡中所有節(jié)點的偏好因子。自適應變化過程如下：當節(jié)點i時刻存儲的信息包隊列長度小于其發(fā)送能力ki時，其偏好因子ai就增大一個步長λ；反之，當節(jié)點i時刻存儲的隊列長度超過其發(fā)送能力ki時，其偏好因子ai就減小一個步長λ。同時為偏好因子設定上下限amax(>0)，amin(
設定界限amax，amin的原因是考慮到當偏好因子增長的過大時，度大節(jié)點的偏好概率會遠遠大于度較小的節(jié)點，信息包會全部盡量涌向度較大的節(jié)點，向度小節(jié)點轉移的概率極低，不利于在整個網絡內搜索目的節(jié)點，所以要為ai設定上限amax；而偏好因子如果變?yōu)檩^小的負值，就意味著信息會盡量選擇度小的末梢點作為傳輸對象，完全避開hub節(jié)點將導致信息包傳輸時延大大增加，所以也要為ai設定下限amin。
2 路由方法分析
考察scale-free網絡路由策略性能的最主要指標是網絡容量，通常用網絡不擁塞時可以達到的最大信息包產生速率Rc(又稱臨界速率)來衡量。
在任一信息包產生速率下，如果只是每次進入部分節(jié)點的信息包隊列長度超過了節(jié)點發(fā)送能力，使信息包堆積，導致了擁塞的發(fā)生(后文稱之為節(jié)點過飽和)，那么只需把這部分業(yè)務轉移到尚未飽和的節(jié)點中去，就可以緩解這種局部負載過重帶來的擁塞，并且可以進一步擴大產生速率。只有當全部節(jié)點均達到了飽和，整個網絡擁塞的發(fā)生才是無可避免的。所以目的就是避免局部節(jié)點擁堵帶來網絡擁塞，盡量提高網絡容量，最后全部節(jié)點可以同步地達到飽和狀態(tài)。
設定節(jié)點發(fā)送能力等于其連接度，首先使度大節(jié)點有較大的偏好概率，以大業(yè)務流進入速率把負載優(yōu)先分配給度大的節(jié)點進行存儲轉發(fā)，搜索目的地；當度大節(jié)點的負載等于甚至超過發(fā)送能力(后文稱之為飽和)后，自適應地調整其信息進入速率，把業(yè)務向尚未飽和的度較小的節(jié)點轉移，避免度大的節(jié)點過早進入擁塞狀態(tài)。
注意到在本策略定義的自適應傳輸機制下，l(ki)的長度從0開始逐漸增長，當l(ki)≤ki時，每次發(fā)送完成后不會有信息包在節(jié)點內滯留，所以節(jié)點處于未飽和平穩(wěn)狀態(tài)；反之，若l(ki)>ki，信息包會不斷在節(jié)點堆積，節(jié)點就處在過飽和擁塞狀態(tài)。所以稱l(k)=k為節(jié)點未飽和與過飽和的相分界線。
在自適應策略下，選取任何非負的偏好因子上限amax都能得到相同的最大網絡容量Rc_max。這是因為自適應策略根據節(jié)點的負載與發(fā)送能力的關系不斷變化偏好因子ai，進而調整信息流的進入速率，不斷向未飽和的節(jié)點分流信息包，從而使信息包不會在飽和節(jié)點處不斷積累增加，避免節(jié)點達到過飽和造成全局擁塞。未飽和節(jié)點，由于隊列長度一直滿足l(ki)≤ki，其偏好因子ai均會隨時間不斷增長，直至等于其上限amax，不會減小；達到相分界線的飽和節(jié)點，其偏好因子不再保持等于上限amax，而是隨負載的變化波動。在自適應調整偏好因子的反饋作用下，飽和節(jié)點的信息包進入速率將基本等于發(fā)送能力，即平均隊列長度穩(wěn)定在相分界線l(ki)=ki上，由于相分界線斜率為1，參考式(1)，得出飽和節(jié)點的偏好因子接近于0。同時考慮到，當所有節(jié)點都達到飽和，偏好因子ai均接近于0時，網絡達到最大容量。因此在任何偏好因子的界限amax下，網絡均有惟一相同的最大容量Rc_max。
圖1反映的是不同發(fā)送速率下，節(jié)點平均隊列長度的變化情況。圖中粗直線代表的就是相分界線。節(jié)點均未飽和時，反映在圖中就是l(ki)未接觸相分界線，此時l(ki)服從式(1)。隨著R增加，部分節(jié)點接觸相分界線后開始進入飽和狀態(tài)，l(ki)也開始分為兩段。度較大的一部分飽和節(jié)點的平均隊列長度與相分界線完全重合，平均隊列長度變?yōu)閘(ki)=ki；另一部分節(jié)點未達到飽和狀態(tài)，平均隊列長度保持原來的斜率，即
隨著R的增加，l(ki)與相分界線重合部分增加。當所有節(jié)點均達到飽和，即l(ki)與相分界線完全重合時，所有節(jié)點的偏好因子的均值均達到0，網絡達到最大容量，此時的R就是最大臨界發(fā)送速率Rc。
3 仿真結果
首先觀察采用自適應策略后網絡容量的變化情況。為了精確地找出臨界發(fā)送速率，利用了以下序參量：
式中：△Np=N(t+△t)-N(t)是一段時間△t內網絡總包數的變化；＜＞意味著選取足夠多的時間段計算得出的平均值；η(R)可以視為網絡內總包數的變化率。
圖2反映靜態(tài)局部路由策略和本文提出的自適應局部路由策略不同R對應的η變化。ai=0，0．4，0．8代表在靜態(tài)偏好局部路由策略下，網絡中所有節(jié)點的優(yōu)化因子的選擇情況。amax=0．4，amin=-0．4；amax=0．8，amin=-0．8；amax=1，amin=-1代表在自適應局部路由策略下優(yōu)化因子上下限選擇情況。從η的數值變化可以看到，在靜態(tài)偏好局部路由策略下，只有在選取ai=0時，具有最大的臨界發(fā)送速率，固定優(yōu)化因子ai為其他值時所得到的Rc均無法達到這一最大值。按照本文提出的自適應局部路由策略，在為ai選取不同的amax，amin的時候，均超過靜態(tài)策略的Rc可以獲得相同的最大Rc_max。
反映網絡路由策略效能的另一個重要指標就是信息包的平均傳輸時延。圖3反映的是采用自適應路由策略、靜態(tài)偏好路由策略，以及王文旭等提出的結合動態(tài)和靜態(tài)信息的路由策略得到的不同平均傳輸時延。
圖3中，β=-3代表結合動態(tài)和靜態(tài)信息的局部路由策略，及其關鍵參數的選取情況，具體可參見文獻。ai=0代表在靜態(tài)偏好局部路由策略，amax=0.4，amin=-0．4，amax=1，amin=-1，amax=1．5，amin=-1．5，分別代表在本文提出的局部路由策略下網絡中所有節(jié)點的優(yōu)化因子的上下限?？梢钥吹?，結合動態(tài)和靜態(tài)信息的局部路由策略在R較小時可以保持較低的傳輸時延，但是隨著發(fā)送速率的增加，平均傳輸時延也迅速增大。靜態(tài)路由策略(ai=0時)的傳輸時延在接近臨界發(fā)送速率前隨發(fā)送速率逐漸增大。
從圖3可以看到，本文提出的自適應局部路由策略的平均傳輸時延受到不同的amax的影響。在接近臨界狀態(tài)時采用本文策略的平均傳輸時延明顯小于原有策略。
4 結語
本文提出了一種自適應的無標度網絡上的局部路由策略。每個節(jié)點的轉發(fā)概率由節(jié)點度k及偏好因子a共同決定。偏好因子a值根據每個節(jié)點自身的緩存平均隊列長度自適應變化，當節(jié)點緩存平均隊列長度大于發(fā)送能力(等于節(jié)點度k)時，a增加；反之，則減小。a的上下限amax，amin可調，并且互為相反數。當網絡中所有節(jié)點均未飽和時，不同度節(jié)點的偏好因子基本都達到上限amax；當部分節(jié)點達到飽和時，這些節(jié)點的偏好因子顯示出a=0的統(tǒng)計特性，其余節(jié)點的偏好因子仍基本保持為amax。這使得一方面無論網絡業(yè)務輕重時，都可以保證網絡信息流量優(yōu)先地向hub節(jié)點集中，連接度大的節(jié)點得到充分的利用；另一方面能夠使節(jié)點發(fā)送能力得到恰當的使用而不會達到“過飽和”狀態(tài)，自適應地避免擁塞的發(fā)生。仿真結果表明，為偏好因子選擇不同的上下限時，本策略都能使所有節(jié)點同步飽和，以達到網絡的最大臨界發(fā)送速率；基于對hub節(jié)點的適度優(yōu)先利用，本文提出的自適應局部路由策略，可以獲得比靜態(tài)偏好局部路由策略、結合動態(tài)和靜態(tài)信息的局部路由策略更小的平均信息包傳輸時延。
。
