路由算法的設(shè)計與優(yōu)化

馮曉東， 梁紅碩

(1.中國人民解放軍總參謀部信息化部 駐石家莊地區(qū)軍事代表室， 河北 石家莊 050081；2.石家莊職業(yè)技術(shù)學(xué)院 信息工程系，河北 石家莊 050081)

?

路由算法的設(shè)計與優(yōu)化

馮曉東1， 梁紅碩2

(1.中國人民解放軍總參謀部信息化部 駐石家莊地區(qū)軍事代表室， 河北 石家莊 050081；2.石家莊職業(yè)技術(shù)學(xué)院 信息工程系，河北 石家莊 050081)

應(yīng)用迪杰斯特拉算法和弗洛伊德算法進行路由鏈路設(shè)計時，可以找到最短路徑，但可能引起網(wǎng)絡(luò)負(fù)載的不均衡.在考慮網(wǎng)絡(luò)綜合性能的基礎(chǔ)上，對這兩種算法增加鏈路或在生成鏈路時加入節(jié)點度的限制，可實現(xiàn)路由算法的優(yōu)化，減少網(wǎng)絡(luò)負(fù)載不均衡情況的發(fā)生.

路由算法；迪杰斯特拉算法；弗洛伊德算法

對路由算法的設(shè)計，起源于圖論中最短路徑的求解.在圖論中，考慮的基本元素是節(jié)點和各節(jié)點之間線路的權(quán)值.求解最短路徑的過程類似于交通系統(tǒng)中的道路查詢，即從某地經(jīng)由哪條路線到達某地的路線最短，最短路徑亦由此得名.應(yīng)用迪杰斯特拉算法和弗洛伊德算法可實現(xiàn)路由鏈路設(shè)計，找到最短路徑，但其均可能引起網(wǎng)絡(luò)負(fù)載的不均衡，因此，本文對這兩種算法進行了改進，在考慮網(wǎng)絡(luò)綜合性能的基礎(chǔ)上增加約束條件，以達到優(yōu)化算法的目的.

1 應(yīng)用迪杰斯特拉(Dijkstra)算法實現(xiàn)鏈路設(shè)計

求解最短路徑的算法最先是從求解某一個節(jié)點到達其他所有節(jié)點的最短路徑開始的，這就是迪杰斯特拉算法.它考慮按照路徑長度遞增的次序產(chǎn)生最短路徑.首先，構(gòu)造一個已求得最短路徑的節(jié)點的集合S，開始時S中只有一個初始節(jié)點；其次，找到從S中的節(jié)點到其他所有節(jié)點路徑最短的節(jié)點，并加入到S中，再對所有節(jié)點進行循環(huán).當(dāng)所有節(jié)點都加入到集合S中時，就認(rèn)為找到了從初始節(jié)點到其他所有節(jié)點的最短路徑.

假設(shè)圖G中有n個節(jié)點，分別是V0到Vn，數(shù)組D存放圖中從初始節(jié)點V0到Vw的距離，arc存放圖中Vi到Vj的距離，動態(tài)數(shù)組LinkS用于按序存放每一個加入到集合S中的節(jié)點的下標(biāo).初始時，這些距離都是兩個節(jié)點間的直接距離.經(jīng)過迪杰斯特拉算法后，數(shù)組D存放初始節(jié)點V0到圖中其他n-1個節(jié)點間的最短距離，而從初始節(jié)點V0出發(fā)所找到的最短路徑則存放在LinkS數(shù)組中.

迪杰斯特拉算法包含內(nèi)外兩重循環(huán).內(nèi)層第一個循環(huán)用于找到從集合S中的某個節(jié)點到其他所有節(jié)點的最短路徑，并將找到的節(jié)點加入集合S中；內(nèi)層第二個循環(huán)用于找到某個節(jié)點，并加入集合S后修改節(jié)點間的最短距離，存入數(shù)組D.外層循環(huán)則表示要經(jīng)過n次才能將所有節(jié)點都加入到集合S中.對于有n個節(jié)點的圖，此算法的時間復(fù)雜度為O(n2).但此算法并不能直接應(yīng)用于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生成，通過對此算法再加一層循環(huán)，即對所有的節(jié)點執(zhí)行此算法，才能得到網(wǎng)絡(luò)中任一節(jié)點到其他節(jié)點的最短路徑.應(yīng)用這個算法，要對原算法中的幾項變量進行調(diào)整，如數(shù)組D要改為二維數(shù)組，存放任意兩節(jié)點間的最短距離；動態(tài)數(shù)組LinkS也要改為二維數(shù)組，其中，第一維用于表示選擇哪個節(jié)點作為初始節(jié)點，第二維則仍是動態(tài)數(shù)組，用于存放從初始節(jié)點出發(fā)找到的最短路徑.此算法是在原算法外增加一層循環(huán)，因此時間復(fù)雜度為O(n3).

此算法所找到的最短路徑集合存放在LinkS數(shù)組中.實際程序中通常要模擬畫出拓?fù)浣Y(jié)構(gòu).此時，只要對此LinkS數(shù)組進行一個循環(huán)，取出任意兩個相連的節(jié)點分別作為一條鏈路的起始節(jié)點和終止節(jié)點，并添加到鏈路數(shù)組中，同時注意不要出現(xiàn)鏈路重復(fù)，即可用此鏈路數(shù)組畫出拓?fù)鋱D.

2 應(yīng)用弗洛伊德(Floyd)算法實現(xiàn)鏈路設(shè)計

求解任意兩個節(jié)點之間的最短路徑問題，可以通過修改迪杰斯特拉算法實現(xiàn)，而弗洛伊德算法則專門用于解決這一問題.弗洛伊德算法用于直接求解圖中任意兩個節(jié)點間的最短路徑.此算法形式上比迪杰斯特拉算法簡單，但是算法的時間復(fù)雜度相同.其基本思想是：對于任意兩個節(jié)點Vi和Vj之間的距離D，在其余的n-2個節(jié)點中選取一個節(jié)點Vw，比較D和D+D的大小，若Vi通過Vw到達Vj的距離更短，則令最短路徑數(shù)組P得到w，同時更新D的值，然后再分別對(Vi，Vw)和(Vw，Vj)進行相同的操作.這樣，就能夠找到任意兩個節(jié)點間的最短距離，并存放于二維數(shù)組D中，同時，將最短路徑存放于二維數(shù)組P中.

在實際繪制拓?fù)鋱D時，此算法還需進一步處理，即由數(shù)組P得到所有的鏈路數(shù)組.這是一個遞歸求解的過程，鏈路數(shù)組為節(jié)點的動態(tài)數(shù)組，存放于Link中.其算法流程如圖1所示.其中，Link.Insert(a,i,j)表示將a插入Link數(shù)組的i，j之間.

圖1 弗洛伊德(Floyd)算法鏈路

3 路由算法的優(yōu)化

在網(wǎng)絡(luò)規(guī)劃系統(tǒng)中，路由算法的求解不能單純以生成鏈路的速度作為評價指標(biāo)，因為在實際的網(wǎng)絡(luò)中，各種性能參數(shù)的存在會對網(wǎng)絡(luò)拓?fù)涞男阅茉斐珊艽蟮挠绊?如果簡單地以路徑生成算法的速度作為拓?fù)渖傻闹饕罁?jù)，實際得到的鏈路性能反而可能下降.因此，要對算法進行一定的改進，在考慮網(wǎng)絡(luò)綜合性能的基礎(chǔ)上對算法加上約束條件.如，在一個擁有80個節(jié)點的網(wǎng)絡(luò)中，假設(shè)節(jié)點A正好處于網(wǎng)絡(luò)的中央，那么根據(jù)常規(guī)的路由算法，生成的鏈路很可能都要經(jīng)過節(jié)點A，如果節(jié)點C經(jīng)過節(jié)點A到達節(jié)點B，同時節(jié)點D通過節(jié)點A到達節(jié)點E.在這種情況下，如果用戶在節(jié)點C與B，D與E之間都配送大量的業(yè)務(wù)數(shù)據(jù)，則這些業(yè)務(wù)數(shù)據(jù)都要流經(jīng)節(jié)點A.如果除節(jié)點A外的79個節(jié)點間的業(yè)務(wù)數(shù)據(jù)都要流經(jīng)節(jié)點A，對節(jié)點A會是非常大的負(fù)擔(dān).同時，網(wǎng)絡(luò)中的邊緣節(jié)點相關(guān)的業(yè)務(wù)鏈路可能只有一兩條，那么在這些邊緣節(jié)點上，資源就會造成很大的浪費.所以單純地追求網(wǎng)絡(luò)節(jié)點間的最短路徑是不可取的.

解決這一問題，有兩種思路.第一種是增加鏈路.例如，讓節(jié)點C和節(jié)點B直接連通，當(dāng)經(jīng)過節(jié)點A的業(yè)務(wù)量過大時，在配送節(jié)點C與B之間的業(yè)務(wù)時，直接在節(jié)點C與B之間增設(shè)鏈路.而這是以增加硬件設(shè)施為基礎(chǔ)的.從軟件設(shè)計的角度看，相關(guān)的處理代碼要放到業(yè)務(wù)層.第二種思路是在生成鏈路時加入節(jié)點度的限制，即對任意一個節(jié)點，要對它所關(guān)聯(lián)的鏈路數(shù)量設(shè)置約束條件.對于迪杰斯特拉算法，節(jié)點度的限制應(yīng)該加在獲取鏈路的代碼中，即在數(shù)組Link中加入一個節(jié)點對(i，j)之前先對數(shù)組Link進行搜索.假如節(jié)點度限制最大為5，如果在Link中已經(jīng)存在的節(jié)點對中的i或j已經(jīng)出現(xiàn)了5次，則此節(jié)點對不加入鏈路中.對于弗洛伊德算法，加入約束條件的方式和迪杰斯特拉算法相似，但是判斷條件簡單.在向Link數(shù)組中加入某個節(jié)點s時，首先對Link數(shù)組進行搜索，看s出現(xiàn)的次數(shù)是否達到了5次，如果出現(xiàn)5次就不再添加.算法如圖2所示.

節(jié)點度的增加會帶來算法時間復(fù)雜度的消耗，尤其會使網(wǎng)絡(luò)拓?fù)渲腥我鈨蓚€節(jié)點間的路徑不一定最短.但是，這一代價所換來的好處是可以確保網(wǎng)絡(luò)負(fù)載均衡，提高網(wǎng)絡(luò)的整體性能.

圖2 在弗洛伊德算法中增加約束條件的算法鏈路

[1]萬健.NoC路由算法設(shè)計與實現(xiàn).南京：南京大學(xué)，2011.

[2]杜加琴.片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)設(shè)計和路由算法研究.合肥：安徽大學(xué)，2012.

責(zé)任編輯：金 欣

Design and optimization of routing algorithm

FENG Xiao-dong1， LIANG Hong-shuo2

(1.Information Department，General Staff Headquarters PLA，Shijiazhuang，Hebei 050081，China;2.Department of Information Technology，Shijiazhuang Vocational Technology Institute，Shijiazhuang，Hebei 050081,China)

The routing links by Dijkstra and Floyd algorithm may facilitate the designing，but may also cause uneven loads on the network.Considering the comprehensive performance and reduction of imbalance of the network，we add nodes to the two algorithm links.

routing algorithm; Dijkstra; Floyd algorithm

2015-10-19

馮曉東(1976-)，男，河北石家莊人，中國人民解放軍總參謀部信息化部工程師.

1009-4873(2015)06-0043-03

TP393.027

A