兼顧帶寬和開銷的網(wǎng)絡(luò)最優(yōu)路徑算法?

馬慧慧 盧 昱 陳興凱

（1.軍械工程學院信息工程系 石家莊 050003）（2.軍械工程學院裝備指揮與管理系 石家莊 050003）

1 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，人們對于大數(shù)據(jù)量傳輸?shù)男枨蟪掷m(xù)增加，迫使研究者不斷尋求新的解決辦法來滿足這種需求。最優(yōu)路徑問題是網(wǎng)絡(luò)分析的關(guān)鍵課題，是網(wǎng)絡(luò)優(yōu)化問題的一個重要分支。在復雜的網(wǎng)絡(luò)中尋找最優(yōu)路徑，能夠有效提高網(wǎng)絡(luò)數(shù)據(jù)的傳輸性能，從而為用戶提供更好的QoS保障［1］。最短路徑問題已經(jīng)有了很長的研究歷史，且算法理論也在不斷取得進步，著名的最短路徑算法有Di?jkstra 算法［2］、Bellman-Ford 算法［3］、Floyd 算法［4～5］、SPFA 算法［6］等。

帶寬（Bandwidth）和開銷（cost）是衡量網(wǎng)絡(luò)中一條通道性能的重要指標。帶寬是指在單位時間內(nèi)能傳輸?shù)臄?shù)據(jù)量。開銷是指對網(wǎng)絡(luò)進行路由管理而產(chǎn)生的代價的度量信息，比如延遲、鏈路狀況、跳數(shù)等。在網(wǎng)路選擇中，人們希望獲得的路徑開銷更小而帶寬更大，但在路由計算時，卻往往將兩者分開來考慮。現(xiàn)在針對于最優(yōu)路徑的研究，大多是以這兩個中的某一個作為參量來進行計算的。文獻［1］從保證通道帶寬入手，研究了基于端到端的最優(yōu)化流量控制。文獻［8］提出的尋找最大帶寬路徑對算法同樣是以帶寬作為選路的依據(jù)。文獻［9～11］則是以尋求最小的開銷作為目標，研究了適應于實際需求的Dijkstra算法優(yōu)化策略。多參數(shù)約束的路由問題大多數(shù)都是NPC（NP-Complete）問題，文獻［12］指出帶寬和延遲、代價、延遲抖動、丟失率之一結(jié)合的兩參數(shù)路由問題是多參數(shù)路由中僅有的非NPC問題。

一條路徑的帶寬決定了吞吐量的大小，開銷決定了數(shù)據(jù)流傳輸?shù)臅r延。單純以最小開銷或最大帶寬作為依據(jù)而構(gòu)建的路徑往往不是最優(yōu)路徑。最短路徑開銷最小卻難以獲得最大帶寬，而帶寬最大路徑又不能保證開銷最小，這都會成為數(shù)據(jù)流在這條路徑上傳輸性能的短板。為了使所選路徑具有最佳傳輸性能，本文兼顧帶寬和開銷，對經(jīng)典的Dijkstra算法進行了合理化改進。

2 算法設(shè)計

2.1 Dijkstra算法介紹

Dijkstra算法是求單源最短路徑的經(jīng)典算法［13］。它采用標記法按照路徑長度遞增的順序?qū)ふ易疃搪窂剑紫葟脑袋c開始，找出長度最短的一條路徑及節(jié)點，然后從新節(jié)點出發(fā)，通過迭代得到從源點到其余各節(jié)點的最短路徑［9］。

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

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

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

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

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

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

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

2.2 問題描述及參量設(shè)置

2.2.1 問題描述

假設(shè)存在圖1所示的無向加權(quán)網(wǎng)絡(luò)G=(V，E)，V表示G中節(jié)點的集合，E表示G中的邊的集合，|V|=n，| E |=m。G中的節(jié)點用vi(i=1，2，3，…，n)來表示，圖中已經(jīng)給出了源節(jié)點vs和目的節(jié)點vt。如果兩個節(jié)點之間有物理連接，則稱這兩個節(jié)點之間存在一條邊，每條邊eij=[vi，vj]存在一對參數(shù)，該邊的開銷 h(eij)和帶寬 b(eij)，記為（h(eij)，b(eij)）。 G 中的一條路徑表示為 P={v1，v2，v3，…，vr}，(r≤n)。定義路徑P的開銷為P中包含的所有邊的和值；路徑P的帶寬為P中所有邊帶寬的最小值［15］。

圖1 加權(quán)網(wǎng)絡(luò)圖

使用Dijkstra算法在該網(wǎng)絡(luò)中來尋找最短路徑，僅僅利用了了每條邊兩個參數(shù)中的一個參數(shù)，即開銷h(eij)，使得路徑上的所有邊的開銷之和最小。使用Dijkstra算法解算出的最短路徑樹如圖2所示，源節(jié)點vs到樹中的任意節(jié)點都有唯一一條最短路徑，當然指定的目的節(jié)點vt到源節(jié)點vs的最短路徑也就找到了。

圖2 使用Dijkstra算法計算的最短路徑樹

表1顯示了從vs到vt所有可能路徑的帶寬，從表中可以看出，Dijkstra算法找出的最短路徑P={vs，v1，vt}雖然開銷最小，但它的帶寬不是所有路徑中最大的。帶寬最大的路徑是第2、第3條路徑，但是它的開銷也不是最小的。僅以一個參量作為選路依據(jù)，難免會使另一個參量成為制約通道性能的制約因素，成為數(shù)據(jù)傳輸?shù)摹捌款i”。因此需要一個更加合理的參量，能夠兼顧帶寬和開銷兩個參量，綜合性地描述一條邊的性能。依據(jù)新的參量計算出的路徑，可能不是開銷最小的，也不是帶寬最大的，但是能使其傳輸性能在網(wǎng)絡(luò)中更加優(yōu)化。

表1 vs到vt所有可能路徑的帶寬

2.2.2 參量設(shè)置

按照上節(jié)中對新參量的期望，我們進行如下定義：

定義1 加權(quán)無向網(wǎng)絡(luò)G=(V，E)中兩個節(jié)點形成的邊eij=[vi，vj]含有帶寬和開銷兩個參數(shù)，把開銷和帶寬的比值稱為這條邊的優(yōu)秀值，即

f(eij)反映了一條邊的質(zhì)量的好壞。帶寬和開銷在選路中是兩個互相矛盾的參量。我們在選擇路徑時總是希望一條邊的帶寬越大越好，開銷越小越好，f(eij)值越小，說明這條邊的質(zhì)量越好，在路徑計算時選擇這條邊的概率就越大［16］。為了使帶寬和開銷在數(shù)值上具有可比性，對兩個參量進行歸一化處理。用 h(eij)/∑h(eij)來代替 h(eij)，用h(eij)/∑h(eij)來代替b(eij)，其中∑h(eij)表示網(wǎng)絡(luò)G中所有的邊開銷的總和，∑b(eij)表示網(wǎng)絡(luò)G中所有的邊帶寬的總和。歸一化消除了兩個參量單位上的不統(tǒng)一，f(eij)成為一個只有數(shù)值沒有單位的參量，它的表達式變成

2.3 算法實現(xiàn)

該算法是在Dijkstra最短路徑算法的基礎(chǔ)上，以邊的“優(yōu)秀值”作為新的度量，尋找源節(jié)點vs到目的節(jié)點vt的“度量最小的路徑”［17］。算法過程分為三個階段。

第一階段：進行初始化操作。根據(jù)網(wǎng)絡(luò)G中邊的參數(shù) (h(eij)，b(eij))以及公式 f(eij)=計算出每條邊的“優(yōu)秀值”作為尋路的新的度量。

第二階段：構(gòu)建“最優(yōu)路徑樹”，實質(zhì)上是對Di?jkstra最短路徑算法的改進。將網(wǎng)絡(luò)G中所有節(jié)點分為兩個集合T和S。T是最優(yōu)路徑樹中的節(jié)點集合，S是待判斷的節(jié)點集合。對于已經(jīng)加入到樹T 中的節(jié)點 vj賦予3個參數(shù) (dj，bj，pj)，dj是從源節(jié)點vs到節(jié)點vj的最短路徑開銷，bj是源節(jié)點vs到節(jié)點vj所形成路徑的帶寬，pj代表節(jié)點vj在最短路徑中的父親節(jié)點。每一次迭代過程都尋找當前節(jié)點vr到源節(jié)點vs的最優(yōu)路徑，并將vr添加到樹中，記錄vr的3個參數(shù)，直到所有節(jié)點或目的節(jié)點被包含到“最優(yōu)路徑樹”當中為止。

第三階段：路徑建立過程?！白顑?yōu)路徑樹”計算完成后，所有節(jié)點3個參數(shù)(dj，bj，pj)都被記錄了下來。利用這些參數(shù)，反向?qū)ふ夷骋还?jié)點的父親節(jié)點，能夠從目的節(jié)點vt反向一步一步構(gòu)建起到起點節(jié)點vs的路徑，并且獲知該路徑的開銷帶寬信息［18］。算法1詳細描述了該算法的實現(xiàn)過程：

算法1

Input：網(wǎng)絡(luò)G，源節(jié)點vs和目的節(jié)點vt；

Output：從vs到vt的最優(yōu)路徑 P

1.for alle∈Edo

2.計算 f(e)=(h ( e)/∑h(e))/(b ( e)/∑b(e))

3.end for

4.for allv∈Vdo

5. d(v)=∞，b(v)=-∞，p(v)=[.]

6.end for

7.addvstoT ，d(vs)=0，b(vs)=∞，p(vs)=0，f(ess)=0

8.do｛

9. for allvi∈Tdo

10. for allvj∈Sdo

11. 計算 f(esj)=f(esi)+f(eij)

12. f(esk)=min[f(esj)]

13. d(vk)=d(vi)+h(eik) ， b(vk)=min[b(vi)，b(eik)] ，p(vk)=vi

14. addvktoT，i=k

15. end for

16. end for

17.｝while(T=V or vs∈ T)

18.addvttoP

19.whilevt≠vsdo

20. p(vt)=vr

21. adderttoP

22. vt=vr

23.end while

根據(jù)新的度量值計算形成的最優(yōu)路徑樹如圖3所示，與圖2所示的根據(jù)開銷計算的最短路徑樹結(jié)果有所不同。由圖2得到的最短路徑是[vs，v1，vt]，開銷值為15，路徑的最大帶寬值為4；由圖 3 得到的最優(yōu)路徑是 [vs，v2，v3，v4，vt]，開銷值為20，路徑最大帶寬為5。使用優(yōu)化之后的算法得到的路徑開銷雖然不是最小，但是在路徑的最大帶寬上較之前相比有提升。雖然這個例子只是為了說明算法優(yōu)化之后的運算效果，節(jié)點數(shù)目比較少難免可能出現(xiàn)路徑開銷和最大帶寬都降低的極端情況。但在實際網(wǎng)絡(luò)中，當節(jié)點數(shù)目達到一定數(shù)量的時候，才能夠統(tǒng)計意義上來講，優(yōu)化后的算法能夠達到開銷和帶寬的平衡。

圖3 最優(yōu)路徑樹

3 實驗驗證

為了證明本文提出的改進算法的正確性，用程序代碼分別實現(xiàn)了3個算法。生成N個點作為網(wǎng)絡(luò)節(jié)點，N取［100，1000］，取樣間隔為100。以矩陣的形式表示各節(jié)點之間的連接關(guān)系以及開銷、帶寬兩個參數(shù)，用兩個矩陣來描述一個網(wǎng)絡(luò)。矩陣一，描述開銷，隨機生成［30，80］中的任意數(shù)值，有數(shù)值代表兩個節(jié)點之間有連接，兩個節(jié)點之間沒有連接則數(shù)值為無窮大（實際上就是系統(tǒng)最大值）；矩陣二，描述帶寬，與開銷矩陣所表示的節(jié)點連接關(guān)系一一對應，帶寬值隨機生成［15，85］中的任意值，兩個節(jié)點之間沒有連接的帶寬值為0。在網(wǎng)絡(luò)中指定源節(jié)點vs和目的節(jié)點vt，用3種算法分別計算出對應路徑，統(tǒng)計在不同節(jié)點數(shù)目下3中算法運行完成所需要的時間以及獲得路徑的開銷和帶寬值，以此來比較3種算法的性能。

圖4 3種算法的模擬測試結(jié)果

從實驗結(jié)果中來看，圖3（a）顯示3種算法的運行時間相當，這是因為3種算法的核心都是Dijkstra算法，具有相同的時間復雜度，因此實驗結(jié)果與預期是相符的。圖3（b）比較的是3種算法計算出的路徑的開銷狀況，最小開銷算法以開銷作為選路依據(jù)，所以路徑的開銷值能夠維持在一個比較小的水平上；兼顧帶寬和開銷算法以最小開銷算法作為藍本，融入了帶寬因素，與最小開銷算法數(shù)值相當；最大帶寬算法目的是獲得最大帶寬路徑，完全不考慮開銷的影響，因此所計算出的路徑開銷最大。圖3（c）比較的是三種算法計算出的路徑的帶寬狀況，最大帶寬算法以帶寬作為選路依據(jù)，計算出的路徑具有最大帶寬，相比之下最小開銷算法和兼顧算法計算的路徑帶寬值較小，但是就整體趨勢而言，兼顧算法所得帶寬仍比只以獲得最小開銷的算法獲得的帶寬大，由此證明引入帶寬因素提高了算法性能。兼顧帶寬和開銷的最優(yōu)路徑算法相比其他兩種算法而言是具有一定優(yōu)勢的。

4 結(jié)語

關(guān)于路由算法的研究大多是以路徑的開銷或帶寬作為考察依據(jù)的，但是選路中無論是以開銷優(yōu)先還是帶寬優(yōu)先，都會造成對另一個參數(shù)的忽略，難以獲得最“優(yōu)”的路徑。路徑的開銷和帶寬都影響著網(wǎng)絡(luò)數(shù)據(jù)的傳輸性能，因此我們更希望算法能夠計算出開銷和帶寬都比較好的路徑。

本文以上述觀點作為指導思想，研究了一種能夠兼顧帶寬和開銷的路由算法。選擇路由算法中經(jīng)典的Dijkstra算法作為改進的對象，對權(quán)值進行重新定義，以開銷和帶寬的比值作為新的權(quán)值，再用Dijkstra算法計算出權(quán)值最小的路徑。通過理論研究和實驗驗證，證明了改進后的算法在時間復雜度上與傳統(tǒng)算法相當，在保證開銷仍然較小的情況下，帶寬性能有所提高。這一研究對于多因素影響的路由問題提供了一種解決思想，對于平衡多種選路參量，獲得最佳網(wǎng)絡(luò)傳輸性能具有重要意義。