一種基于非線性長度的多約束路由算法
2008-12-31 00:00:00劉永廣葉梧馮穗力
計算機應用研究 2008年11期
(1.華南理工大學 電子與信息學院， 廣州 510640；2.廣東輕工職業技術學院 管理系， 廣州 510300)
摘要：滿足多個約束的QoS路由問題已經被證明是NP完全問題。在分析了多種路由算法的基礎上，設計了一種高效的多約束路由算法。該算法采用非線性路徑長度計算方法。為提高算法的成功率，在節點的松弛過程中設計了節點動態路徑長度計算，允許節點作多次松弛。為提高算法的執行效率，在節點正向松弛和反向估計過程中引入了受控路徑的思想，使算法得到了優化。大量仿真表明，該算法在最短路徑獲取和路由發現成功率方面都有高效的表現。
關鍵詞：服務質量路由；多約束；非線性路徑長度
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2008)11-3408-04
Algorithm for multi-constrained routing based on nonlinear path length
LIU Yong-guang1，2，YE Wu1， FENG Sui-li1
(1.School of Electronic Information Engineering， South China University of Technology， Guangzhou 510640， China；2.Dept. of Management， Guangdong Industry Technical College， Guangzhou 510300， China)Abstract:The problem of finding a path that satisfies multiple constraints has been proved a NP-complete problem.Based on the analysis of some algorithms in this field，proposed an efficient multi-constrained routing algorithm.The new algorithm adopted the idea of nonlinear path length. In order to improve the success ratio，designed a dynamic path selection method for nodes， which demanded that nodes be relaxed for more times.For the reason of improving algorithm efficiently，addedthe concept of dominated path to the process of selecting more weights sum for path calculation. Large simulations prove that the new algorithm has high efficiency in success ratio and finding the shorter path.
Key words:QoS routing; multi-constrained; nonlinear path length
0引言
在下一代通信網絡中，隨著網絡業務的多樣化和復雜化，如何為不同業務需求提供不同的服務質量保證是下一代網絡能否順利實施的關鍵性因素。因此，對滿足多種度量的QoS路由算法研究一直是一個具有挑戰性的熱點領域，文獻[1]對當前的研究進展作了總結性論述。基于QoS的多約束路由問題通常分為兩類：a)鏈路約束。它可以轉換為整個路徑上瓶頸鏈路的約束，如帶寬。b）路徑約束。它是對組成端到端路徑上所有鏈路的約束。依據文獻[2]的分類，該類約束還可以分為加性約束和乘性約束，前者如延遲、抖動、花費、跳數等，后者如可靠性、包丟失率等。對于鏈路約束，可以通過剪枝法預先去除不符合要求的鏈路，從而保證在剩余子圖中求得滿足約束條件的鏈路。本文研究的是路徑約束，而且僅限于加性約束，且滿足多個約束（約束個數K≥2）的情況。
對于在一個圖中尋找滿足多個約束條件的最優路徑問題，已經被證明是一個NP完全問題[3]。對于這樣的NP完全問題，提出了一些啟發式算法。Iwata等人[4]提出了一個多項式時間算法來解決多約束路徑問題。該算法首先基于一個QoS度量求出一條（或多條）最短路徑；然后檢查該條路徑是否滿足其他約束條件。如果條件不滿足，使用另外的一個度量。重復以上過程，直到發現一條滿足條件的路徑或者所有的度量都被嘗試到。這種算法的最大問題是對于單個的一個度量產生的最短路徑，無法保證其滿足其他度量產生的約束。但是，如果所有的鏈路權重是正相關的，如一個權重變小，其他的權重隨之變小，這種情況下該算法的表現最好。SAMCRA（self-adaptive multiple constraints routing algorithm）[5]是一個確切算法，TAMCRA（tunable accuracy multiple constrained routing algorithm）[6]是一個啟發式算法。這兩個算法都基于非線性路徑長度和k-shortest最短路徑方法。對于TAMCRA算法來說，由于k是固定的，該算法的復雜度是多項式時間的。但是對于確切算法SAMCRA來說，在最壞情況下k值會呈指數增長，所以k值的大小對該算法的復雜度起著決定性的影響，一個大的k值將使該算法失去使用價值。SAMCRA算法可以保證如果存在可行路徑，就能發現一條滿足約束條件的路徑。在這個過程中，該算法根據非支配思想來自適應動態調整每個節點需要存儲的路徑數量，并分配相應的存儲空間。而在TAMCRA算法中，k值是預先定義好的，空間也按照k值預先分配。Korkmaz等人[7]提出了一種隨機啟發式算法來解決多約束路徑問題。該算法的核心思想是算法在搜索路徑的執行過程中作出隨機決策，從而避免一些無法預料的陷阱。H_MCOP是Korkmaz等人[8]提出的一種啟發式算法，該算法試圖采用非線性路徑長度來發現滿足約束的路徑。此外，該算法還試圖同時找到一條路徑長度最短的路徑。Yuan和Liu[9，10]提出的極限路徑啟發式算法是一個擴展的Bellman-Ford算法，并在算法中引入了TAMCRA算法的基本思想。Liu等人考慮不僅發現一條而是發現k條滿足約束路徑的算法，他們提出了一個稱為A*剪枝的確切算法[11]。該算法采用了Jaffe的路徑長度，如果存在k條可行的路徑，該算法獲得滿足約束的那些路徑。
目前這些算法各有優缺點，但是都具有較大的局限性：a）算法復雜且計算復雜度較高；b）算法性能表現不盡如人意，算法成功率較低且路徑長度優化不理想；c）算法針對某些特殊情況，普適性較差。本文提出的啟發式算法，為降低算法的時間復雜度，在路徑計算方法上采用了H_MCOP算法的方法，但是在節點松弛過程中提出了多選擇計算長度的方法，有效地提高了算法的精確性。
為提高算法的執行效率，在節點的松弛過程中又引入了受控路徑的思想，使算法的運行效率更高。
1算法理論基礎
11多約束路徑（multi-constrained path，MCP）
定義1如果用圖G(V，E)來表示一個網絡拓撲。其中：V是網絡節點的集合；E是連接邊的集合。每一個連接(i， j)∈E都具有K個加性權重wk（k=1，2，…，K），且wk≥0。給定K個約束ck（k=1，2，…，K），多約束路徑（MCP）問題就是從源節點s到目的節點t找一條路徑p，使p滿足以下條件：
wk(p)=(i， j)∈pwk(i， j)≤ck；k=1，2，…，K（1）
在源與目的節點之間可能存在滿足多約束條件的多條路徑，該路徑都是MCP的解。也就是說對于一個給定的MCP問題，可能存在多個滿足條件的解。然而對于這個解集，關鍵是要找到一條最優的路徑，這就歸結為一個多約束優化路徑問題。
定義2如果用圖G(V，E)來表示一個網絡拓撲。其中：V是網絡節點的集合；E是連接邊的集合。每一個連接(i， j)∈E都具有K個加性權重wk（k=1，2，…，K），且wk≥0。定義一個路徑長度標準l(p)，多約束優化路徑（multi-constrained optimal path，MCOP）問題就是從源節點s到目的節點t找一條路徑p，使p在滿足式（1）的條件下，最小化路徑長度標準，使l(p)≤l(p′)。其中p′為所有滿足式（1）的路徑集合。MCP和MCOP都是QoS路由中要解決的問題。
12多約束路徑的長度
如定義2所描述，為了在MCP解集中得到一條最優路徑，需要定義一個路徑長度標準來對這些路徑進行評估。對于這樣的路徑長度，目前提出的有兩類：線性路徑長度和非線性路徑長度。
Jaffe[12]提出了一種線性路徑長度，其定義如下：
l(p)=Ki=1diwi(p)=d×w(p)，di＞0（2）
由于該長度定義的是一個線性長度，可以基于這個長度標準使用Dijkstra算法求得最短路徑。采用這種線性長度進行搜索，當di=1/ci時達到最優[6]。但是所獲得最短路徑不一定能滿足所有的約束條件。為了使這種長度最短的路徑更好地滿足約束條件，引入了非線性路徑長度[6]：
lq(p)=Ki=1（wi(p)/ci）q1/q（3）
特別地，當q→∞時：
l∞(p)=max1≤i≤K[(wi(p)/ci]（4）
這種非線性路徑長度的應用，縮小了解空間的搜索范圍。根據文獻[6]的論述，使用式（4），位于約束區域內的路徑長度一定小于位于約束區域外的約束長度。因此，如果求得的最短路徑長度位于約束區域外，一定不會存在滿足所有約束的路徑。這也就把尋找滿足多約束的路徑問題轉換為尋找滿足式（4）的最短路徑問題。但對于這種非線性路徑長度，卻無法用Dijkstra算法來求解，因為這種非線性路徑長度不具有可加性，必須采用其他的啟發式算法。
13受控路徑
定義3對于兩條路徑p和p′，如果對于所有的1≤i≤K，都有wi(p)＜wi(p′)，則稱路徑p′受控于路徑p。如果在搜索過程中發現一條路徑p′受控于另一條路徑p，那么就可以舍棄p′，尤其在使用k-shortest算法時。這樣就可以有效地減少節點內儲存的路徑個數，提高算法的執行效率。
2新算法設計
21新算法思想
在上述多種算法中，H_MCOP是綜合性能最好的一個算法。該算法實現簡單，在不采用堆排序的情況下時間復雜度為Dijkstra算法的K倍，并且在節點數較多（n≥200）時，可以達到95%的路由成功率。因此，本文的研究就建立在該算法的基礎上，尋求性能更好的啟發式算法。
首先通過一個例子來看該算法存在的問題，如圖1所示。
計算從源節點0到目的節點6的一條路徑，要求滿足兩個約束都是10，則很容易得出采用文獻[8]中算法得到的路徑為0→3→6，非線性路徑長度0.7。但是可以看到路徑0→2→3→4→6也能滿足約束，且其非線性路徑長度為0.6，是一條更優的路徑。研究發現，產生上述缺陷的一個重要原因是節點3進行路徑長度計算時始終采用的是一個由節點6產生的逆向權和41，但是節點3還有兩個后繼節點。在逆向過程中盡管它們到節點3的路徑不是線性最短路徑，但在正向非線性過程中，節點3到它們的路徑是最短路徑的一部分卻是有可能的。為此，在正向計算中，應該把這兩個節點對節點3產生的逆向權和也考慮在內。這樣，當節點3的前驅節點松弛到節點3時，就不僅要計算逆向最短路徑提供的逆向權和，還要計算非最短路徑提供的逆向權和，并在所有計算產生的路徑長度中選擇最小的長度。如此考慮，就會給被松弛的節點在松弛方向上作更多的考慮和選擇。
盡管如此，并不是一個節點所有的后繼節點產生的逆向權和都要記錄在該節點內。為了提高算法的效率，在算法設計上引入了逆向受控路徑思想，也就是那些逆向受控的路徑產生的逆向權和不會參與到非線性路徑的計算中。在圖1中可以看到，節點6在節點3產生的逆向權和是41，已經加入到松弛計算中。節點4在節點3處產生的逆向權和是12+12=24。由于該數據和前一個路徑產生的數據比較起來不滿足受控路徑的條件，也把該數據加入到路徑計算中。同理可知，節點5在節點3處產生的逆向權和是22+21=43。可以看到，該路徑是受控于節點6到節點3這條路徑的，就不會參與松弛計算。通過這種方法，可以有效減少參與計算的路徑數目，從而提高算法的效率。
在其他啟發式算法和Dijkstra算法中，每個節點都只是松弛一次。但在本文的算法中，由于節點松弛過程中有多個逆向權和參與了計算，松弛過的節點保存的路徑長度不一定是最短路徑長度。為此，算法中允許節點重復松弛，只要通過節點的最短路徑比原來減少，該節點就要重新參與松弛，如節點3、4都會被松弛兩次。
最后，在正向計算過程中也引入了受控路徑的思想。當一個節點松弛到它的后繼節點時，如果該節點到其后繼節點的實際路徑受控于其他節點到其后繼節點的實際路徑，則到該后繼節點的松弛過程就不再進行，這樣也可以有效地提高程序的運行效率。
22新算法（N_MCOP）描述
在第1行對表1中所列出的參數進行了初始化，并完成逆向標號過程[8]。在第2行中通過判斷S2是否為空來決定算法是否退出。第3行與Dijkstra算法一樣，選擇在S2中且到源節點路徑最短的節點進行松弛，選擇完畢后松弛該節點（第6行）。
節點的松弛過程如下：
其中：第1~5行判斷是否要把松弛到的節點產生的逆向權和插入到隊列中；第7行的計算根據式(4)來進行，此處路徑長度l∞(p)=max1≤k≤K{[Gk(u)+Rk(u)]/ck}，并且多個Rk參與了計算；第9~12行更新松弛到的節點路徑長度和參數。
向節點內插入Rk的過程如下：
其中：在第1行中首先判斷該路徑是否逆向受控，如果是則不再插入；然后第4行判斷其是否控制節點內已存儲路徑，如果是則從節點內刪除這些路徑的Rk；最后，第7、8行向節點內插入該Rk。
3算法仿真
通過仿真對新算法N_MCOP和H_MCOP算法進行比較，對算法的性能進行評估。
31仿真模型
目前相關仿真中對于網絡拓撲的建模還沒有統一的標準，文獻[13]中給出了一些常用的模型。在本算法的仿真中，采用了隨機圖的拓撲結構。該圖的生成是基于Waxman提出的一個網絡模型[14]。在該模型中，通過均勻分布，在一個矩形區域內隨機地產生需要的節點數，節點之間存在連接的概率用式（5）來表示：
P(u，v)=β exp[-d(u，v)/（Lα）]（5）
其中：d(u，v)為節點u與節點v之間的距離；L為所有節點間的最大長度；α、β是(0，1]的數。
隨機圖權重的產生方法參考了文獻[8]，對于每個有連接的邊使用了兩個不相關的權重：w1(u，v)~uniform(1，100)和w2(u，v)~uniform(1，200）。根據邊的權重，產生如下兩個隨機的路徑約束：c1~uniform(0.8×w1(p2)，12×w1(p2))和c2~uniform(0.8×w2(p1)，12×w2(p1))。其中：p1、p2是分別以w1和w2作為權重采用Dijkstra算法求得的最短路徑；w1(p2)指的是在p2這條路徑上權重w1的和；w2(p1)指的是在p1這條路徑上權重w2的和。
32仿真方法
在本仿真中，主要考察兩個性能指標：a）路由成功次數。在給定的請求次數中，算法能夠成功找到滿足約束路徑的次數。b）路徑長度。在滿足約束的情況下，算法尋路成功獲得的非線性路徑長度。
在仿真中通過式（5）產生10個網絡圖，對每一個圖按照以上的方法產生兩個約束，并產生1 000個隨機源與目的間的請求。圖2是在不同的節點下兩種算法成功次數的一個比較。由曲線可以看出，新算法的成功率得到提高。圖3統計了N_MCOP和H_MCOP算法在滿足約束的條件下獲得的平均路徑長度。從圖中可以看到，新算法的最短路徑長度要小于H_MCOP算法。圖4和5是分別在有150個節點和300個節點條件的拓撲網絡結構中，在多于兩個約束條件下對兩個算法成功率的比較。從兩幅圖可以看出，與圖2中兩個約束的比較相似，在更多約束條件下，隨著節點數的增加，成功率提高。此外，隨著約束條件的增加，算法的成功率下降。
4算法性能分析
假設拓撲圖中有n個節點，則非k-shortest的H_MCOP算法在不使用堆排序的情況下時間復雜度為O(Kn2)。由于新算法允許節點作重復松弛，無法準確得知算法的執行次數，在對新算法的性能評估方面，主要通過對仿真數據進行定量分析來獲得性能評估。
表2的數據是通過對10個拓撲圖、每個圖產生1 000次請求、利用新算法計算產生的結果。從表的每節點平均參與松弛的次數可以看到，在節點數目增加了30倍的情況下，每個節點參與松弛的次數變化緩慢，基本接近1。這說明盡管增加了節點的重復松弛，但算法的平均時間復雜度與原算法基本相同。同時，節點參與松弛的最大次數在節點數達到200后基本趨于穩定，穩定在5次左右。從該表可以看到，每個節點的平均度數增加很快，但是每個節點存放Rk的隊列長度卻遠遠小于節點的度數，且增長緩慢，這說明受控路徑算法發揮了很好的作用。此外，在節點數增加到200以后，盡管度數增長很快，但是最大隊列長度卻基本穩定。如果把節點數量（NodeNum）和平均隊列長度(q_len)采用最小二乘法擬合成一條直線，則直線方程為q_len=0.002NodeNum+1312 2，得到平均需要增加的存儲空間為(0.002NodeNum+1312 2)NodeNum個隊列元素單位，如果考慮最壞情況，則需要(10~11)NodeNum個隊列元素單位，是算法性能改進后所額外付出的代價。
表2新算法在不同節點數圖中的運行參數
節點數量每節點的平均度數每節點平均參與松弛的次數
節點參與松弛最大次數節點存放Rk的平均隊列長度節點存放Rk的最大隊列長度
5結束語
通過前面的論述可看到，本文提出的N_MCOP算法在節點松弛計算上作了有效的設計，使算法平均時間復雜度在沒有顯著增加的情況下，算法的性能得到提高。本文在算法中采用了受控路徑的思想，使得新算法性能明顯優化。盡管如此，對新算法的研究還有許多工作要做，如研究算法在最復雜的二維柵格拓撲結構下的性能表現，以及算法性能的進一步改進方案。
參考文獻：
［1］
MASIP-BRUIN X，YANNUZZI M，DOMINGO-PASCUAL J，et al.Research challenges in QoS routing[J].Computer Communications，2006，29(5):563-581.
[2]FU Y，CHENG X，TANG Y.Optimization theory and method[M].Chengdu:Press of UESTC，1996.
[3]WANG Zheng，CROWCROFT J.Quality-of-service routing for suppor-ting multimedia applications[J].IEEE Journal Select Areas Commun，1996，14(7):1228-1234.
[4]IWATA A，IZMAILOV R，LEE D S，et al.ATM routing algorithms with multiple QoS requirements for multimedia internetworking[J].IEICE Trans and Communications，1996，E79-B(8):999-1006.
[5]MIEGHEM P van，KUIPERS F A.Concepts of exact QoS routing algorithms[J].IEEE/ACM Trans on Networking，2004，12(5):851-864.
[6]DeNEVE H，MIEGHEM P van.TAMCRA:a tunable accuracy multiple constraints routing algorithm[J].Computer Communications，2000，23(7):667-679.
[7]KORKMAZ T，KRUNZ M.A randomized algorithm for finding a path subject to multiple QoS requirements[J].Computer Networks，2001，36(2-3): 251-268.
[8]KORKMAZ T，KRUNZ M.Multi-constrained optimal path selection[C]//Proc of IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:834-843.
[9]YUAN Xin，LIU Xing-ming.Heuristic algorithms for multi-constrained quality of service routing[C]//Proc of the 20th Annual Joint Conference on IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:844-853.
[10]YUAN Xin.Heuristic algorithms for multiconstrained quality-of-ser-vice routing[J].IEEE/ACM Trans on Networking，2002，10(2):244-256.
[11]LIU Gang，RAMAKRISHNAN K G.A* prune:an algorithm for fin-dingk-shortest paths subject to multiple constraints[C]//Proc of the 20th Annual Joint Conference on IEEE INFOCOM 2001.Anchorage，AK:[s.n.]，2001:743-749.
[12]JAFFE J M.Algorithms for finding paths with multiple constraints[J].Networks，1984，14(5):95-116.
[13]ZEGURA E W，CALVERT K L，BHATLACHARJEE S.How to model an internetwork[C]//Proc ofIEEE INFOCOM’96.Los Alamitos:[s.n.]，1996:594-602.
[14]WAXMAN B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications，1988，6(9):1617-1622.
