適用于無向網(wǎng)絡(luò)的動(dòng)態(tài)Dijkstra算法優(yōu)化

， ，

(1.軍械工程學(xué)院 信息工程系，石家莊 050003； 2.軍械工程學(xué)院 裝備指揮與管理系，石家莊 050003)

0 引言

路由算法是網(wǎng)絡(luò)研究中的關(guān)鍵問題[1-2]。為了減小數(shù)據(jù)在傳輸過程中的開銷，通常尋找節(jié)點(diǎn)之間的最短路徑。E.Dijkstra提出經(jīng)典的最短路徑算法[3]，以一個(gè)節(jié)點(diǎn)為根，形成最短路徑樹(SPT，Shortest Path Tree)，適用于尋找單節(jié)點(diǎn)到網(wǎng)絡(luò)中任意節(jié)點(diǎn)的最短路徑。在實(shí)際的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會(huì)因?yàn)楦鞣N原因發(fā)生改變，例如鏈路失效、節(jié)點(diǎn)宕機(jī)、新節(jié)點(diǎn)加入等。在網(wǎng)絡(luò)模型中，拓?fù)浣Y(jié)構(gòu)的變化一般總結(jié)為以下4種情況：邊的權(quán)值增大或減小、節(jié)點(diǎn)增加或刪除[4-5]。當(dāng)網(wǎng)絡(luò)拓?fù)湫》秶l(fā)生變化時(shí)，通過Dijkstra算法從根節(jié)點(diǎn)開始重構(gòu)SPT，能夠解決這個(gè)問題。但是這種靜態(tài)的算法重構(gòu)SPT會(huì)造成大量不必要的開銷，因?yàn)樾》秶負(fù)浒l(fā)生變化，有許多節(jié)點(diǎn)在最短路徑樹中的位置是不發(fā)生改變的。

為了優(yōu)化算法性能，提出了動(dòng)態(tài)Dijkstra算法[6]。動(dòng)態(tài)Dijkstra算法的核心思想是盡可能保持現(xiàn)有SPT的結(jié)構(gòu)，縮小需要重新計(jì)算的節(jié)點(diǎn)的范圍，降低更新SPT過程的復(fù)雜程度。文獻(xiàn)[7]最早提出動(dòng)態(tài)更新最短路徑樹算法(DSPT)，但是算法所劃定的更新范圍仍有冗余。NSPT算法[8]，Ball-and-String算法[9-10]是比較高效的動(dòng)態(tài)算法，解決了有邊的權(quán)重增大減小的狀況。文獻(xiàn)[11]提出了多條邊發(fā)生變化時(shí)的解決方法。這些算法基于的網(wǎng)絡(luò)模型大多是有向網(wǎng)絡(luò)模型，但在實(shí)際計(jì)算機(jī)網(wǎng)絡(luò)中，一般是數(shù)據(jù)正反向都能傳遞的無向網(wǎng)絡(luò)。在無向網(wǎng)絡(luò)模型中，兩個(gè)節(jié)點(diǎn)只有連接關(guān)系而無先后順序，因此在算法中無法利用節(jié)點(diǎn)先后連接參數(shù)。文獻(xiàn)[12]提出了較為成熟動(dòng)態(tài)算法的思想，討論了在網(wǎng)絡(luò)中一條邊權(quán)值變化的SPT更新算法。但是該算法適用于有向網(wǎng)絡(luò)模型，同時(shí)對(duì)于所處理的節(jié)點(diǎn)范圍沒有進(jìn)行必要的篩選，還是有部分冗余計(jì)算。本文在此基礎(chǔ)上提出了適用于無向網(wǎng)絡(luò)的動(dòng)態(tài)更新SPT算法，優(yōu)化了受影響節(jié)點(diǎn)的篩選機(jī)制，進(jìn)一步縮小了節(jié)點(diǎn)更新范圍。

1 Dijkstra算法基本原理

Dijkstra算法是求單源最短路徑的經(jīng)典算法。它采用標(biāo)記法按照路徑長度遞增的順序?qū)ふ易疃搪窂剑紫葟脑袋c(diǎn)開始，找出長度最短的一條路徑及節(jié)點(diǎn)，然后從新節(jié)點(diǎn)出發(fā)，通過迭代得到從源點(diǎn)到其余各節(jié)點(diǎn)的最短路徑[13]。為了跟后來所研究的動(dòng)態(tài)Dijkstra算法形成對(duì)應(yīng)，把經(jīng)典的Dijkstra算法稱作靜態(tài)Dijkstra算法。

Dijkstra算法的基本過程[14]如下：在整個(gè)網(wǎng)絡(luò)中設(shè)置兩個(gè)集合，集合T是經(jīng)過計(jì)算加入到最短路徑樹中的節(jié)點(diǎn)，集合S是還未加入到最短路徑樹中的節(jié)點(diǎn)。假設(shè)每個(gè)節(jié)點(diǎn)vj都有一對(duì)參數(shù)(dj,pj)，dj是從源節(jié)點(diǎn)vs到節(jié)點(diǎn)vj的最短路徑長度，pj代表節(jié)點(diǎn)vj在最短路徑中的父親節(jié)點(diǎn)。

步驟一：初始化，T=φ，S包含了網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。設(shè)置所有節(jié)點(diǎn)dj=∞，pj=[.]

步驟二：將源節(jié)點(diǎn)vs加入集合T，并從S中刪除，設(shè)置ds=0，ps∈φ。

步驟三：檢驗(yàn)集合T中的所有節(jié)點(diǎn)vi到的S中節(jié)點(diǎn)vj的距離lij，其中vi到vj必須是直接連接的，中間無其他節(jié)點(diǎn)。設(shè)置dj=min[dj,di+lij]。

步驟四：選取dj最小的節(jié)點(diǎn)vj，將其從集合S中刪除，并加入到集合T中去，該節(jié)點(diǎn)成為最短路徑樹中的一個(gè)新節(jié)點(diǎn)。

步驟五：找到新節(jié)點(diǎn)vj的父親節(jié)點(diǎn)pj，并記錄該節(jié)點(diǎn)的兩個(gè)參數(shù)(dj,pj)。

步驟六：重復(fù)步驟三到步驟五的過程，直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)全部加入到集合T中，此時(shí)集合S=φ，完成整個(gè)過程。

2 算法設(shè)計(jì)

2.1 參量設(shè)置

假設(shè)存在加權(quán)無向網(wǎng)絡(luò)G=(V,E)，V表示節(jié)點(diǎn)的集合，E表示邊的集合，|V|=n，|E|=m。G中的節(jié)點(diǎn)用v來表示，用下標(biāo)加以區(qū)分。e代表兩個(gè)有直接連接的節(jié)點(diǎn)之間的邊，權(quán)值用w(e)表示。從根節(jié)點(diǎn)的整個(gè)網(wǎng)絡(luò)的最短路徑樹表示為SPT(Shortest Path Tree)，d(v)表示從根節(jié)點(diǎn)到節(jié)點(diǎn)v的最短路徑長度，p(v)表示節(jié)點(diǎn)v的在SPT中的父親節(jié)點(diǎn)，T(v)表示在SPT中以v為根節(jié)點(diǎn)的子最短路徑樹的節(jié)點(diǎn)的集合。對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)設(shè)置一個(gè)狀態(tài)參量Sta(v)，當(dāng)Sta(v)=1表示節(jié)點(diǎn)v在SPT′(更新后的SPT)中的位置已經(jīng)固定，不再需要處理；Sta(v)=0表示節(jié)點(diǎn)的位置仍需要更新。設(shè)置一個(gè)集合Q，存儲(chǔ)等待處理的節(jié)點(diǎn)及節(jié)點(diǎn)d(v)的變化量。該算法討論的是無向網(wǎng)路，必要時(shí)用[vi,vj]來表示兩個(gè)節(jié)點(diǎn)及所形成的邊。vi、vj的先后順序與表示的結(jié)果無關(guān)，也就是說[vi,vj]和[vj,vi]實(shí)際上表示的是同一條邊。相比于有向網(wǎng)絡(luò)，無向網(wǎng)絡(luò)需要解決的問題更復(fù)雜一些。

2.2 算法描述

假設(shè)在網(wǎng)絡(luò)G中，關(guān)于根節(jié)點(diǎn)vs的SPT已經(jīng)構(gòu)造完成。當(dāng)檢測到有一條邊e0的權(quán)值發(fā)生變化時(shí)，需要首先確定SPT受影響的范圍[15]。算法是分成權(quán)值增大和權(quán)值減小兩種情況進(jìn)行處理的。

情況一：權(quán)值增大時(shí)。如果權(quán)值增大的邊不是SPT中的邊(例如圖1中的[v5,v6])，由于各節(jié)點(diǎn)的最短路徑長度(d值)已經(jīng)是當(dāng)前最小的，非SPT中的邊權(quán)值增大不會(huì)改變各節(jié)點(diǎn)到根節(jié)點(diǎn)的d值，因此這種情況下不會(huì)影響SPT結(jié)構(gòu)。如果SPT中的一條邊的權(quán)值增大，假設(shè)圖1中，邊[v2,v6]的權(quán)值由3變?yōu)?0，增加了7，這將導(dǎo)致以v6為根節(jié)點(diǎn)的子樹(T(v6))中的節(jié)點(diǎn)到vs的距離都會(huì)增加，此時(shí)在網(wǎng)絡(luò)中的位置不一定是路徑最短的位置，因此需要對(duì)這些節(jié)點(diǎn)的位置進(jìn)行調(diào)整。邊[v2,v6]權(quán)值增加后影響到的節(jié)點(diǎn)范圍在圖中用虛線圈出。將T(v6)中的節(jié)點(diǎn)的d值全都增加7，并把它們的Sta(v)參數(shù)置為0，表示節(jié)點(diǎn)位置等待更新；原SPT中的其他節(jié)點(diǎn)Sta(v)置為1，表示節(jié)點(diǎn)位置已經(jīng)固定。

圖1 使用Dijkstra算法計(jì)算的最短路徑樹

所有與待更新節(jié)點(diǎn)相連的節(jié)點(diǎn)都有可能成為新的父親節(jié)點(diǎn)，在文獻(xiàn)[12]的算法中，把所有的連接邊都納入到了判斷范圍之內(nèi)，但實(shí)際仍有部分是無需考慮的。與待更新節(jié)點(diǎn)相連的邊有三種類型，以v9為例：(a)與T(v6)之外的節(jié)點(diǎn)相連的邊，例如[v5,v9]；(b)與T(v6)內(nèi)節(jié)點(diǎn)相連但不屬于T(v6)的邊，例如[v10,v9]；(c)與T(v6)內(nèi)節(jié)點(diǎn)相連但且屬于T(v6)的邊，例如[v6,v9][v9,v12]。其中c類邊不納入考慮范圍是顯然的；b類邊，兩個(gè)節(jié)點(diǎn)的d值加上了相同的增量，不會(huì)改變待更新節(jié)點(diǎn)的父親節(jié)點(diǎn)；只有a類邊存在改變待更新節(jié)點(diǎn)最短路徑的可能。因此在下一步操作之前可以首先把b、c類邊排除，達(dá)到縮減計(jì)算范圍的目的。該部分判定過程對(duì)應(yīng)于算法1中的第8行偽代碼。在a類邊中，計(jì)算邊的對(duì)應(yīng)節(jié)點(diǎn)的最短路徑值與該邊權(quán)值之和，如果小于待更新節(jié)點(diǎn)的最短路徑值，則將這個(gè)待更新節(jié)點(diǎn)以及對(duì)應(yīng)的邊、節(jié)點(diǎn)加入到集合Q中，并將這個(gè)差值δ(vj)=d(vi)+w(e)-d(vj)記錄下來。表1顯示了圖1中首先加入到Q中的項(xiàng)。

表1 父親節(jié)點(diǎn)可能改變的節(jié)點(diǎn)及對(duì)應(yīng)邊和增量

從集合Q中選取δ(vj)最小的一組數(shù)據(jù)，對(duì)應(yīng)的邊的另一個(gè)節(jié)點(diǎn)vi就是該節(jié)點(diǎn)vj的新父親節(jié)點(diǎn)。將以vj為根節(jié)點(diǎn)子樹中的所有節(jié)點(diǎn)的最短路徑值加上該增量值(負(fù)值)，狀態(tài)參量修改為1，刪除集合Q中所有跟這些節(jié)點(diǎn)有關(guān)的項(xiàng)。

定理1：跟隨vj加入到新SPT中的T(vi)子樹中的節(jié)點(diǎn)，處于當(dāng)前的最短路徑。

證明1：對(duì)T(vj)中的任意節(jié)點(diǎn)vt，假設(shè)存在vx使得d(vx)+w([vx,vt])

圖2 使用動(dòng)態(tài)Dijkstra算法更新后的樹

由于更新節(jié)點(diǎn)最短路徑值d的減小，會(huì)使與之相連的節(jié)點(diǎn)的父親節(jié)點(diǎn)發(fā)生改變，因此需要將d(vi)+w(e)-d(vj)<0的節(jié)點(diǎn)對(duì)應(yīng)的項(xiàng)加入到集合Q中去，重復(fù)更新過程。直到Q變成空集為止，退出循環(huán)，整個(gè)更新過程結(jié)束。該部分算法的偽碼描述見算法1，更新之后的SPT如圖2所示。

算法1:權(quán)值增大的SPT更新算法。Input:網(wǎng)絡(luò)G,根節(jié)點(diǎn)vs,邊e的權(quán)值從w(e)變?yōu)閣′(e);Output:以vs為根節(jié)點(diǎn)的新SPT′1)Initialize SPT from G2)wait until one edge e0=[vi,vj]:w(e0)→w′(e0)3)if w′(e0)-w(e0)>0,then4)if e0?E(SPT) 不處理 //不是SPT上的邊無影響,不處理5)else if e0∈E(SPT)6)初始化. δ=w′(e0)-w(e0);?v∈V(SPT)設(shè)置為Sta(v)=1; 若vi=p(vj),?v∈T(vj),d(v)=d(v)+δ,Sta(v)=07)end8)for all e=[vi,vj]∧Sta(vi)=1∧Sta(vj)=0 do9)if δ(vj)=d(vi)+w(e)-d(vj)<0 then10)add {vi,vj,δ(vj)} to Q11)end if12)end for13)end if14)while Q≠?15){vi,vj,δ(vj)}←minQ,修改p(vj)=vi16)for all v∈T(vj) do17)修改d(v)=d(v)+δ(vj),Sta(v)=1,delete ?v∈T(vj) from Q18)end for19)for all e=[vi,vj]∧Sta(vi)=1∧Sta(vj)=0 do20)if δ(vj)=d(vi)+w(e)-d(vj)<0 and {vi,vj,δ(vj)}?Q do21)add {vi,vj,δ(vj)} to Q22)end if23)end for24)end while

情況二：權(quán)值減小時(shí)。與情況一類似，權(quán)值減小的邊出現(xiàn)的情況有兩種，或不屬于SPT中的邊，或?qū)儆赟PT中的邊。這兩種情況都有可能造成SPT結(jié)構(gòu)的變化，因此邊的權(quán)值減小受到影響節(jié)點(diǎn)的情況相對(duì)更復(fù)雜。

對(duì)于不屬于SPT中的邊權(quán)值減小，首先比較這條邊對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)最短路徑值的大小，d值比較小的節(jié)點(diǎn)可能成為比較大的節(jié)點(diǎn)的新父親節(jié)點(diǎn)。具體能否構(gòu)成此影響，還要看“準(zhǔn)父親節(jié)點(diǎn)”的d值與邊的新權(quán)值之和跟另一個(gè)節(jié)點(diǎn)d值的大小關(guān)系。如果“準(zhǔn)父親節(jié)點(diǎn)”的d值與邊的新權(quán)值之和比較小，則修改另一個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)，以此節(jié)點(diǎn)為根的子樹中的節(jié)點(diǎn)是此次受到影響的范圍；如果“準(zhǔn)父親節(jié)點(diǎn)”的d值與邊的新權(quán)值之和比較大，那么此次權(quán)值的變更對(duì)SPT沒有影響。

對(duì)于屬于SPT中的邊權(quán)值減小，需要首先判斷這條邊的兩個(gè)節(jié)點(diǎn)在樹中的父子關(guān)系，找到子節(jié)點(diǎn)，以子節(jié)點(diǎn)為根的子樹中的節(jié)點(diǎn)到根節(jié)點(diǎn)的最短距離d會(huì)因此變得更小，因此這仍是SPT的一部分。網(wǎng)絡(luò)中的其他節(jié)點(diǎn)的最短路徑會(huì)有一種向這部分節(jié)點(diǎn)“聚集”的趨勢(shì)，因此剩下的節(jié)點(diǎn)即是此次權(quán)值變更受到影響的節(jié)點(diǎn)范圍。算法的其他處理過程與情況一類似，在這里不再過多描述。該部分算法的初始化部分的偽碼描述見算法2。

算法2:權(quán)值減小的SPT更新算法。1) /?w′(e0)-w(e0)<0?/2)if e0?E(SPT)3)若d(vi)d(vj) 不處理 //未改變SPT5)else6)修改p(vj)=vi,計(jì)算δ(vj)=d(vi)+w′(e)-d(vj)7)初始化. ?v∈V(SPT)設(shè)置為Sta(v)=0; ?v∈T(vj),d(v)=d(v)+δ(vj),Sta(v)=18)end9)else if e0∈E(SPT)10)若p(vj)=vi,計(jì)算δ=w′(e0)-w(e0)11)初始化. ?v∈V(SPT)設(shè)置為Sta(v)=0; ?v∈T(vj),d(v)=d(v)+δ,Sta(v)=112)end

3 實(shí)驗(yàn)驗(yàn)證與分析

為了驗(yàn)證算法的正確性，本節(jié)進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)運(yùn)行主機(jī)配置為：CPU主頻3.20 GHz，內(nèi)存大小為4 GB，操做系統(tǒng)為Windows 7旗艦版。設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N的無向網(wǎng)絡(luò)，N取[100,1000]，步長值為100。賦予網(wǎng)絡(luò)連接邊以及邊的權(quán)值，設(shè)置節(jié)點(diǎn)的平均度為5，權(quán)值范圍為[20,80]。首先根據(jù)生成的網(wǎng)絡(luò)計(jì)算出SPT,隨機(jī)選擇一條邊的改變權(quán)值，考查靜態(tài)Dijkstra算法和本文提出的動(dòng)態(tài) Dijkstra算法在更新SPT所需要的時(shí)間。鑒于當(dāng)權(quán)值增大和權(quán)值減小時(shí)算法的處理過程有所差異，所以在實(shí)驗(yàn)中也分兩種情況分別進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖3圖4所示。

圖3顯示了當(dāng)一條邊的權(quán)值增大時(shí)，在不同網(wǎng)絡(luò)規(guī)模下，靜態(tài)Dijkstra算法和動(dòng)態(tài)Dijkstra算法更新SPT所需要的時(shí)間；圖4顯示了當(dāng)一條邊的權(quán)值減小時(shí)，在不同網(wǎng)絡(luò)規(guī)模下，靜態(tài)Dijkstra算法和動(dòng)態(tài)Dijkstra算法更新SPT所需要的時(shí)間。兩種情況下動(dòng)態(tài)算法都比靜態(tài)算法的時(shí)間開銷要小，能在相對(duì)短的時(shí)間內(nèi)更新SPT，體現(xiàn)出了更好的性能。結(jié)合圖3圖4來看，在節(jié)點(diǎn)數(shù)目相同時(shí)，權(quán)值增大和減小靜態(tài)Dijkstra算法更新SPT所用的時(shí)間幾乎一樣，這是因?yàn)楫?dāng)檢測到有邊的權(quán)值發(fā)生變化時(shí)，靜態(tài)Dijkstra算法都是從根節(jié)點(diǎn)開始更新SPT；兩種情況下動(dòng)態(tài)Dijkstra算法的變化趨勢(shì)幾乎一樣，因?yàn)閮刹糠炙惴ǖ臅r(shí)間復(fù)雜度比較接近。

圖3 權(quán)值增大時(shí)更新SPT的時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

圖4 權(quán)值減小時(shí)更新SPT的時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

4 結(jié)束語

當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)或邊發(fā)生變動(dòng)時(shí)，動(dòng)態(tài)路由算法盡可能地對(duì)已有的最短路徑樹做最小改動(dòng)來保持SPT 的穩(wěn)定，節(jié)省了計(jì)算時(shí)間，比靜態(tài)算法更具有優(yōu)勢(shì)。本文提出了適用于無向網(wǎng)絡(luò)的Dijkstra動(dòng)態(tài)算法，并對(duì)算法中節(jié)點(diǎn)的更新范圍作了進(jìn)一步優(yōu)化，證明了改進(jìn)的合理性。最后通過實(shí)驗(yàn)，比較了當(dāng)網(wǎng)絡(luò)中的一條邊的權(quán)值變化時(shí)，動(dòng)態(tài)算法和靜態(tài)算法更新SPT所需的時(shí)間，驗(yàn)證了所提出算法的可行性和優(yōu)越性。文章只提出了邊的權(quán)值發(fā)生變化的有關(guān)算法，在下一步研究中，將對(duì)節(jié)點(diǎn)增刪以及多邊、多節(jié)點(diǎn)變化的情況進(jìn)行討論，并進(jìn)一步通過實(shí)驗(yàn)來驗(yàn)證所得出的結(jié)論。