汪曉潔，湯建國，李娟

(新疆財經(jīng)大學(xué)計算機科學(xué)與工程學(xué)院，新疆烏魯木齊830012)

0 引言

現(xiàn)今的網(wǎng)絡(luò)對信息的交換速度有著很高的要求，在路由區(qū)域（routing area）不斷變大的情況下，它需要路由更新的速度變得更快.基于鏈路狀態(tài)的路由協(xié)議在網(wǎng)絡(luò)中使用非常廣泛，例如，Open Shortest Path First[1]（OSPF）和Intermediate System-to-Intermediate System[2]（IS-IS），運行鏈路狀態(tài)路由協(xié)議的路由器以自己為根節(jié)點根據(jù)網(wǎng)絡(luò)拓撲計算一棵最短路徑樹，并利用該最短路徑樹計算路由.因此，當網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生改變時最短路徑樹的更新效率將直接影響路由的更新速度.

當網(wǎng)絡(luò)拓撲變化時，需要重新計算SPT.根據(jù)靜態(tài)Dijkstra[3]算法，當網(wǎng)絡(luò)拓撲變化相對于整個網(wǎng)絡(luò)的拓撲數(shù)量較小時，變化拓撲對已有的SPT影響較小.如果幾條鏈路的改變就導(dǎo)致重新計算整個最短路徑樹，進而更新路由表，則會導(dǎo)致大量不必要的重復(fù)計算，使靜態(tài)Dijkstra算法變得效率很低.因此，動態(tài)更新SPT可以降低計算的復(fù)雜性減少冗余的更新，這對網(wǎng)絡(luò)性能的提高具有重要意義.

動態(tài)最短路徑更新算法可以分為半動態(tài)最短路徑算法和全動態(tài)最短路徑算法[4].半動態(tài)最短路徑算法或者處理邊權(quán)值變大，或者處理邊權(quán)值減校 全動態(tài)最短路徑算法則對邊權(quán)值變大或變小均能處理.本文則關(guān)注全動態(tài)最短路徑算法.

1 相關(guān)工作

目前，人們在這方面已經(jīng)做了大量的研究，為了降低計算時間[5]，提出了一種權(quán)重變化圖G*，它利用有向邊和變化節(jié)點的位置生成，G?為網(wǎng)絡(luò)拓撲的子圖，通過G?可以限制更新節(jié)點和鏈路的范圍，從而達到減少冗余更新的目的[6].提出了處理網(wǎng)絡(luò)拓撲圖中邊權(quán)值減小的MaxR、MinD算法，相比較[4]算法，MaxR和MinD算法具有更高的效率.[5，6]這些算法在一定程度上都可以減少SPT的計算時間，但它們都存在冗余計算的問題.[7]提出了路徑節(jié)點驅(qū)動的思想，并提出了基于路徑節(jié)點驅(qū)動的LCSPT算法.[8]說明了網(wǎng)絡(luò)是依賴于時間變化的、動態(tài)的，證明了動態(tài)網(wǎng)絡(luò)的最短路徑問題為NP難，并在此基礎(chǔ)上提出了基于穩(wěn)定區(qū)間的近似算法.[9]從遺傳算法的角度考慮更新SPT.[10]研究了動態(tài)多節(jié)點的刪除對最短路徑更新的影響，提出了MRDA-SPT算法.[11]提出了一種基于脈沖耦合神經(jīng)網(wǎng)絡(luò)的模型M-PCNNs來解決最短路徑問題.

[12]提出的動態(tài)更新DUSPT算法只關(guān)注部分的節(jié)點和鏈路，他將節(jié)點的更新范圍局限在權(quán)值變化的終節(jié)點的子孫節(jié)點和以這些子孫節(jié)點為源節(jié)點的節(jié)點上，此算法不需要對所有的節(jié)點和鏈路重新計算SPT，減少了計算時間，但此算法并未考慮權(quán)值變化時，變化鏈路在拓撲中的位置，節(jié)點的更新范圍會變大，增加的迭代更新會造成大量的冗余計算.

本文通過深入分析，進一步改善了動態(tài)更新SPT的算法，提出了全動態(tài)更新IDEWSPT算法，該算法可同時針對權(quán)值增大和減小進行處理，不僅可以有效減少計算復(fù)雜度還可以減少大量的冗余計算.通過仿真實驗驗證了本算法的正確性、有效性，并具有更好的性能.

2 IDEWSPT算法

下面給出相關(guān)符號和定義，以及IDEW-SPT算法的描述，最后給出IDEW-SPT算法的復(fù)雜度分析.

2.1 術(shù)語定義

為了方便描述，引入以下符號：

（1）定義網(wǎng)絡(luò)拓撲圖G=(V，E，W)，其中V是網(wǎng)絡(luò)中節(jié)點的集合，E是網(wǎng)絡(luò)中鏈路的集合，W是拓撲圖中鏈路的權(quán)重，并規(guī)定拓撲圖中不含負權(quán)邊；

（2）W(e)代表鏈路e的權(quán)重，且e∈E，表示鏈路e更新后的權(quán)重；

（3）D(i)為節(jié)點i在SPT中的最短路徑值，它代表從根節(jié)點到節(jié)點i的所有鏈路權(quán)重的相加和；

（4）Sou-outend(N)={e|S(e)∈N，E(e)/∈N}；

（5）End-outsou(N)={e|S(e)/∈N，E(e)∈N}.

定義1對于有向鏈路e：i→j；

（1）i稱為鏈路e的源節(jié)點，記為S(e)；

（2）j稱為鏈路e的終節(jié)點，記為E(e)；

（3）若e∈SPT，且i是e的源節(jié)點，j是e的終節(jié)點，則節(jié)點i稱為j的父節(jié)點，記為P(j)，即P(j)=i.

定義2節(jié)點i的子孫節(jié)點是從節(jié)點i通過SPT中的邊可達的所有節(jié)點的集合，且包括i節(jié)點本身，記為sub(i).

2.2 算法描述

為了減少計算時間，SPT的計算過程根據(jù)鏈路的變化分為兩大部分，鏈路權(quán)重增大和權(quán)重減小.SPT中某條鏈路e的權(quán)重變大時，只有集合sub(E(e))的節(jié)點和這些節(jié)點相關(guān)的鏈路才可能發(fā)生變化，其他的節(jié)點和鏈路不會發(fā)生任何變化.IDEW-SPT算法只考慮這些節(jié)點和鏈路.當SPT中某條鏈路e的權(quán)重減小時，集合sub(E(e))中的節(jié)點的最短路徑值減少d=w(e)?w(e)，如果節(jié)點的最短路徑值發(fā)生改變，則重新選擇的最短路徑一定會經(jīng)過e.

在IDEW-SPT算法中，N為節(jié)點集合，包含所有需要更新的節(jié)點，每個N中的節(jié)點有一個M.v.inc屬性，代表v節(jié)點的所有入邊中權(quán)重的最小增量值.L為鏈路集合，存儲所有變化的鏈路，每個元素e有一個min-inc屬性，代表節(jié)點E(e)最短路徑的增加值，且可為負值.當有鏈路需要加入集合L時，執(zhí)行入隊操作L（e，min-inc），出隊操作Sel-min（L）將選擇L中min-inc最小的鏈路，并將該鏈路從L中移除.

假設(shè)網(wǎng)絡(luò)拓撲G=(V，E，W)，根據(jù)此拓撲圖使用靜態(tài)Dijkstra算法構(gòu)造SPT.

有一條鏈路e：i→j的權(quán)重從w(e)變?yōu)?/p>

If，and eSPT，

d，執(zhí)行權(quán)值增大，End If；

Ife∈SPT，執(zhí)行權(quán)值減小-1；else執(zhí)行權(quán)值減小-2，End If；

End If

權(quán)值增大

將j加入N，N.j.inc=d，L(e，d)；

for?v∈sub(j)，按N中節(jié)點的D(v)值依次選擇v；

選擇鏈路e，E(e)=v，S(e)/∈sub(j)，and minimum{w(e)}//即e是所有以E(e)為終節(jié)點，S(e)為源節(jié)點的鏈路中權(quán)重最小的一條鏈路；

min-inc=D(S(e))+w(e)?D(E(e))，

If min-inc

L(e，min-inc)，N.v.inc=min-inc，End If；

chi是v在SPT中的直接相連的子節(jié)點，?chi，將chi加入N，N.chi.inc=N.v.inc；

End For；

whileL?；

Sel-min(L)→{e1，min-inc}，P(E(e1))=S(e1)；

?v∈sub(E(e1))andv∈N，D(v)=D(v)+min-inc；

從L中移除終節(jié)點為sub(E(e1))的鏈路，從N中移除Sub(E(e1))；

?e∈Sor-outend{sub(E(e1))}ande∈End-outsor{N}，

min-inc=D(S(e))+w(e)?D(E(e))；

If min-inc

N.E(e).inc=min-inc，L(e，min-inc)，End If；

End While，執(zhí)行步驟1；

權(quán)值減小-1

?v∈sub(j)，D(v)=D(v)+d；

for?e，S(e)∈sub(j)，?E(e)選擇w(e)的值最小的邊；

min-inc=D(S(e))+w(e)?D(E(e))；

If min-inc<0，

D(E(e))=D(S(e))+w(e)，P(E(e))=S(e)，min-inc=D(v)?D(E(e))，End If；?v∈(sub(E(e))-E(e))，IfD(v)-min-inc≤D(v)，

D(v)=D(v)-min-inc，End If；

End For

執(zhí)行步驟1；

權(quán)值減小-2

?v∈sub(j)，D(v)=D(v)+d；

?e，S(e)∈sub(j)，?E(e)選擇w(e)的值最小的邊；

min-inc=D(S(e))+w(e)?D(E(e))；

If min-inc<0，

L(e，min-inc)，End If；

While

Sel-min(L)→{e1，min-inc}，P(E(e1))=S(e1)；

?v∈sub(E(e1))，IfD(v)＋min-inc≤D(v)，

D(v)=D(v)＋min-inc，End If；

從L中移除終節(jié)點為sub(E(e1))的鏈路；

?e∈Sor-outend(sub(E(e1)))，?E(e)選擇w(e)的值最小的邊；

min-inc=D(S(e))+w(e)?D(E(e))，

If min-inc<0，L(e，min-inc)，End If；

End while，執(zhí)行步驟1；

3 算法復(fù)雜度分析

假設(shè)有一個邊的權(quán)重發(fā)生變化，Q表示最短路徑要變化的節(jié)點的集合，Tp是Q中節(jié)點的數(shù)目，參數(shù)Q和Tp只依賴網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和初始SPT.Dmax表示和一個更新節(jié)點相連的鏈路數(shù)目的最大值.

算法復(fù)雜度為O(T2p+T2p Dmax).考慮當鏈路的權(quán)重變大的情況，執(zhí)行一次Sel-min()將花費O(Tp)的時間用于線性數(shù)組的查找，并且有Tp次這樣的迭代.一個父節(jié)點更新時，有|sub(v)|次子節(jié)點的更新，|sub(v)|≤Tp，父節(jié)點更新的迭代次數(shù)不超過Tp，則有.假設(shè)一條鏈路的更新需要花費O(1)的時間，則所有和更新節(jié)點關(guān)聯(lián)的鏈路更新需要O(T2p Dmax).所以算法運行的總時間為O

4 仿真實驗

本節(jié)采用文獻[11]仿真模型來驗證IDEW-SPT算法的正確性和有效性.隨機產(chǎn)生網(wǎng)絡(luò)拓撲圖，所有節(jié)點隨機分布在500*500的平面區(qū)域內(nèi)，任意節(jié)點間存在邊的概率由下式(1)確定:

其中d是節(jié)點間的歐幾里得距離，如果任意兩點間距離在l以內(nèi)，則它們之間存在連接的概率為k，否則，根據(jù)節(jié)點間的距離它們之間存在連接的可能性會呈指數(shù)性下降.每條邊的權(quán)重取值范圍為1～100.l定義為：N為網(wǎng)絡(luò)拓撲中節(jié)點的個數(shù).

在這個仿真模型中，K定義為0.8，N的范圍定義為100～1000，L根據(jù)節(jié)點的平均度數(shù)D決定.根據(jù)拓撲中包含的節(jié)點數(shù)目的不同，我們設(shè)定D為7，最大不超過10.

仿真具體由兩個實驗完成.實驗時，分別在節(jié)點規(guī)模為100～1000時進行測試，相同的節(jié)點規(guī)模測試10次，求其平均值作為實驗值.實驗1比較邊權(quán)值變化時IDEW-SPT算法和[12]算法在更新SPT時花費時間的不同.實驗2比較邊權(quán)值變化時IDEW-SPT算法和[12]算法更新SPT時更新節(jié)點的總次數(shù).具體實驗如下：

實驗1由于每一次更新SPT的時間非常短，因此實驗中給出的數(shù)據(jù)是1萬次更新時間的總和，時間單位為ms.根據(jù)產(chǎn)生的拓撲以及變化，采用[12]算法和IDEW-SPT算法更新已有SPT，仿真結(jié)果如圖1所示.其中黑線為IDEW-SPT算法花費的時間，藍線為[12]算法花費的時間.根據(jù)圖1可知，[12]算法更新1萬次用時在30ms到40ms之間，而IDEW-SPT算法在15ms到32ms之間.由實驗數(shù)據(jù)可以得出，在邊權(quán)值變化時，更新1萬次花費的時間總和IDEW-SPT算法比[12]算法平均少38%.

實驗2本實驗比較節(jié)點規(guī)模為100～1000時，IDEW-SPT算法和[12]算法更新SPT時節(jié)點更新的總次數(shù)，即所有節(jié)點更新次數(shù)之和.假設(shè)一個節(jié)點在更新過程中達到最后狀態(tài)時更新的次數(shù)為3，則節(jié)點更新總次數(shù)增加3.根據(jù)產(chǎn)生的拓撲以及變化，仿真結(jié)果如圖2所示.

根據(jù)圖2可知，在邊權(quán)值變化時，更新節(jié)點的總次數(shù)IDEW-SPT算法比[12]算法平均少31%.

5 結(jié)論

本文通過深入分析，提出一種基于可變權(quán)值的全動態(tài)最短路徑算法.該算法根據(jù)初始SPT中的信息，結(jié)合變化鏈路在拓撲中的位置，將需要更新的節(jié)點和鏈路控制在較小的范圍內(nèi)，僅考慮和計算在更新過程中會發(fā)生變化的節(jié)點和鏈路，在保證節(jié)點最短路徑計算正確的情況下，有效的降低了冗余計算，減少了更新時間.

圖1 算法的時間開銷

圖2 算法的更新節(jié)點總次數(shù)