基于可變權(quán)值的動(dòng)態(tài)最短路徑算法?

汪曉潔，湯建國，李娟

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

2 IDEWSPT算法

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

2.1 術(shù)語定義

為了方便描述，引入以下符號(hào)：

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

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

（3）D(i)為節(jié)點(diǎn)i在SPT中的最短路徑值，它代表從根節(jié)點(diǎn)到節(jié)點(diǎn)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對(duì)于有向鏈路e：i→j；

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

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

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

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

2.2 算法描述

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

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

假設(shè)網(wǎng)絡(luò)拓?fù)銰=(V，E，W)，根據(jù)此拓?fù)鋱D使用靜態(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é)點(diǎn)的D(v)值依次選擇v；

選擇鏈路e，E(e)=v，S(e)/∈sub(j)，and minimum{w(e)}//即e是所有以E(e)為終節(jié)點(diǎn)，S(e)為源節(jié)點(diǎn)的鏈路中權(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é)點(diǎn)，?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é)點(diǎn)為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é)點(diǎn)為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è)有一個(gè)邊的權(quán)重發(fā)生變化，Q表示最短路徑要變化的節(jié)點(diǎn)的集合，Tp是Q中節(jié)點(diǎn)的數(shù)目，參數(shù)Q和Tp只依賴網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和初始SPT.Dmax表示和一個(gè)更新節(jié)點(diǎn)相連的鏈路數(shù)目的最大值.

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

4 仿真實(shí)驗(yàn)

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

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

在這個(gè)仿真模型中，K定義為0.8，N的范圍定義為100～1000，L根據(jù)節(jié)點(diǎn)的平均度數(shù)D決定.根據(jù)拓?fù)渲邪墓?jié)點(diǎn)數(shù)目的不同，我們?cè)O(shè)定D為7，最大不超過10.

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

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

實(shí)驗(yàn)2本實(shí)驗(yàn)比較節(jié)點(diǎn)規(guī)模為100～1000時(shí)，IDEW-SPT算法和[12]算法更新SPT時(shí)節(jié)點(diǎn)更新的總次數(shù)，即所有節(jié)點(diǎn)更新次數(shù)之和.假設(shè)一個(gè)節(jié)點(diǎn)在更新過程中達(dá)到最后狀態(tài)時(shí)更新的次數(shù)為3，則節(jié)點(diǎn)更新總次數(shù)增加3.根據(jù)產(chǎn)生的拓?fù)湟约白兓抡娼Y(jié)果如圖2所示.

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

5 結(jié)論

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

圖1 算法的時(shí)間開銷

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