基於距離完全蟻群算法的多播路由方法

2023-06-10 19:24:26 2

專利名稱：基於距離完全蟻群算法的多播路由方法
技術領域：
本發明屬於計算機網絡通信中的路由技術，具體涉及一種運用蟻群算法的 多播路由方法。 技術背景隨著計算機網絡和通信技術的發展，出現了諸如多媒體會議、遠程教學、 視頻點播、協同工作等服務。多播技術就是一種點到多點的通訊方式。概括來 說，多播路由問題可以敘述為在一個特定的網絡中，根據某項標準尋找從源節 點到多個目標節點的信息傳送路徑。若把網絡視作連通的帶權無向網絡，將網 絡節點和相關連結抽象為對應的圖節點和邊，並根據網絡連結對網絡資源的消 耗定義圖中各邊的權重。求解多播路由，就是尋找一條涵蓋源節點和所有目標 節點，符合約束條件並且消耗最小的最優路徑。事實上，不帶約束的多播路由 問題等價於在圖中生成Steiner樹的問題，該問題已被證明是一個NP-難問題。 解決Steiner樹問題的經典算法包括Takahashi和Matsuyama提出的MPH算法 [l]， Kou、 Markousky和Berman提出的KMB算法[2]， Rayward-Smith提出的 RS算法等C3]。 Leung等人將遺傳算法運用到多播路由問題的求解中，並得到了 較好的結果[4]。在自然界中，單個螞蟻的能力幾乎是可以忽略的，但是作為一個整體時， 蟻群卻是一個高度結構化的群體。雖然螞蟻沒有像視覺和聽覺一樣的直接的交 流工具，但它們可以釋放一種特殊的分泌物——信息素來進行交流，通過這種 信息素蟻群可以很快的在蟻巢和食物之間找到一條最短的路徑。由於蟻群算法 本身具有的正反饋性、並行性、強收斂性以及魯棒性，使得其在組合優化問題 中有很好的表現，如旅行商問題、調度問題、二次分配問題等。與其它的元啟 髮式算法相比，蟻群算法具有較強的全局搜索能力和尋優能力，解的質量穩定 並具有更高的搜索效率。 參考文獻[1] Takahashi H., Matsuyama A.: An approximate solution for the Steiner problem in graphs. Math Japonica， 1980， 24: p. 573-577.[2] Kou L.， Markowsky G" Berman L: A fast algorithm for Steiner tress. Acta Information, 1981， 15: p. 141-145.[3] Rayward-Smith V.丄The computation of nearly minimal Steiner tress in graphs. Int. J. Math. Ed. Sci. Technol., 1983， 14(1): p. 15-23.[4] Y. Leung, G. Li, and Z. B. Xu: A genetic algorithm for the multiple destination routing problems. IEEE Trans, on Evolutionary Computation, vol. 2， no. 4， pp. 150-161, November 1998.

發明內容
本發明運用蟻群算法求解無約束的多播路由問題，基於蟻群系統的結構提 出了一種距離完全蟻群算法來搜索網絡中最低費用的多播樹。算法的具體步驟 包括(1) 運用Floyd算法建立多播路由網絡的距離完全圖。(2) 初始化算法的各個參數。設定距離完全圖每條邊上的信息素的初始值為其中7;是根據確定的冗餘檢測修正方法得到的樹的費用。(3) 隨機選擇一個目標節點讓螞蟻A:開始搜索。螞蟻將會根據狀態轉移規則以一定的概率選擇下一個節點y'，其公式如下.—Jarg maxre0t{[rO))].|>7( )]},如果《2《07=<U 否則其中，/是螞蟻當前所在節點，0,是當前螞蟻還未曾訪問過的節點的集合，《是 均勻分布在區間[O， l]中的隨機變量，《。(03dl)是一個參數。r(/，"表示連接 節點/和r的邊上的信息素取值。;/(/，r)表示從節點/選擇節點r的啟發式信息值。 選擇完成後，對螞蟻經過的邊進行局部信息素的更新。局部信息素的更新將會 分兩步執行， 一個是邏輯邊上的信息素更新，另一個是真實邊上的信息素更新。 螞蟻A不斷重複以上選擇過程，直到它經過所有所有的目標節點，從而得到一棵螞蟻構造的多播樹。(4) 對螞蟻構造的多播樹執行冗餘檢測和修正。首先，對訪問過的節點執 行Prim算法。如果得到的最小生成樹的費用低於螞蟻構造的樹，螞蟻得到的解 就會被最小生成樹代替。然後，檢査無用的中間節點，將那些只有一個輸出端 的中間節點刪除。以上兩個步驟不斷重複，直到生成的樹不能再優化為止。(5) 重複步驟(3)和(4)直到所有螞蟻都完成解的構造。(6) 對歷史最優的多播樹進行全局信息素的更新。在最優生成樹的真實邊 上的信息素如下更新y') = (1 _ P)+A r其中A2^1/ry， r^,為最優生成樹的總的費用。在最優生成樹的邏輯邊上的信息素也同樣需要更新。假設節點/和_/之間選 定的真實路徑為("。，a, "2，...， )，其中"。=/， ^"'。 ^為路徑中邊的數量。 則，邏輯邊(i，力上新的信息素等於(7) 重複步驟(3)至(6)直到滿足算法的終止條件。不同於其它用於求解多播路由問題的蟻群算法，發明的方法是是從一個隨 機選擇的目標節點開始搜索的，並且運用的Prim的最小生成樹算法來構造多播 樹。螞蟻可以確定地選擇下一個節點，也可以用一定的概率去選擇。當一隻螞 蟻完成搜索後，運用Prim算法和冗餘檢測修正方法對螞蟻得到的解進行檢驗和 修正以求得到更好的結果。在網絡中的信息素將通過局部和全局信息素更新機 制進行更新。本發明的另一個創新之處在於，在啟發式信息中通過一個參數//對 目標節點的選取賦予一定的傾向性。運用適當的啟發式方法和參數設定增加了 目標節點(包括源節點)的選擇概率。與同類型的算法相比，發明的算法可以 更加快速地解決多播路由問題。


圖l多播路由網絡示意2多播路由網絡構造距離完全圖的方法示意3邏輯邊的擴展示意4距離完全蟻群算法的總體流程圖
具體實施例方式以下結合附圖進一步對發明的方法進行描述。一個網絡圖可以用G-(^，^，Q)表示，其中^表示網絡中節點的集合，￡c 表示連接節點的邊的集合，Q表示約束條件。如果問題是不帶約束的，則0 = 0。 在多播路由問題中^被分為三個子集^， ^和^，其中^是源節點的集合，^ 是目標節點的集合，^是中間節點的集合。通過每個屬於五e的邊e都有一個費 用c(O。如果Fo中的節點沒有邊連接，則設定相對應的費用為oo。多播路由問 題就是要尋找一棵連接^和^中的所有節點，費用最少並且符合Q中的約束條 件的樹。用公式來表達，就是尋找一棵樹『=(Fs + ^ + ^， A)，其中^f^， ^G&，使min2^c0)， r滿足Q中的約束條件圖1為一個多播路由的例子，在圖中有十二個節點和一些邊。灰色實心的 節點l是源節點，黑色實心節點2， 6，和ll是目標節點。問題是要找到一棵連 接所有目標節點和源節點，並且費用最小的樹。圖中連接節點2， 1， 5， 6， 7， 11的黑色邊就構成了問題的一個解。由於本發明考慮的是不帶約束的多播路由問題，所以可以將源節點和目標 節點統一考慮，因此將^和^合併成為^。多播路由的網絡並不是一個完全連接的圖，也就是說一些節點並不是由單 獨的邊直接連接的。而在一個網絡的距離完全圖中，任意兩個節點都是邏輯連 接的，並且連接的費用是最小的。由於發明的蟻群算法是基於距離完全圖的， 因此首先必須建立多播路由網絡的距離完全圖。其中一種生成距離完全圖的經典算法是Floyd算法，它的偽代碼如下 輸入C x [^I:多播路由網絡的費用矩陣 輸出D^[^]:距離完全圖的費用矩陣0一"[ ]:在距離完全圖中從節點i到J的下一個中間節點偽代碼For f:=0 to w-1Foiv':=0 to "畫l《= If Ctf = ooOj/:=-l;Else。i/ :=刀End If End For End For〃如果在節點i和J之間沒有邊連接〃保存從節點i開始的下一個中間節點For A::=0to w誦lFor /:=0 to w-1F017 Oto w-1If / and cf汰+ c4j < A4/d汰+ ^;0"=0&; 〃記錄新的中間節點 End If End For End For End For在輸入的費用矩陣C^中，q表示連接節點/和y(/,戶0，l,.』-l)的邊的費用。 如果邊不存在，則q為oo。輸出包含兩個矩陣，其一是生成的距離完全圖的費用矩陣D"xw，其中 表示從節點Z'到節點/的邏輯邊的最低費用。另一個是O"x ，其中^記錄從節點z'到節點y的邏輯邊的下一個中間節點。圖2為一個六節點的拓撲結構示例。在圖中的實線為兩個節點間存在的真實的邊，旁邊的數字代表著這條邊相對應的費用。可以看到節點a和b並不是直接相連的，但它們 之間可以通過節點c和d相連。算法可以將圖2中的左圖轉化為右邊的距離完全圖，其中增加了連接a和b的最小費用邏輯邊(虛線)。從a到b的最短路徑是經過C的，因此4b的費用為2.5， Oab的取值為C。由於網絡圖是無向的，因 此Oba的取值也是C。對於節點a和d，雖然它們是直接相連的，但卻存在一個更 短的通過節點e和f的路徑，因此《d = dda =1.5, oad = e, oda = f。當"-l^l時Floyd算法的時間複雜度為0("3)。實際上，在一個真實的網絡 中需要基於路由表上所提供的信息來建立距離完全圖。 一旦距離完全圖建立完 畢，它就不需要改變直到網絡的拓撲結構發生了變化。當距離完全圖建立好後， 就可以運用蟻群算法建立多播樹了。發明的距離完全蟻群算法的結構是基於建立最小生成樹的Prim算法的。假設S是空的節點集合，F是一個無向連接圖中的節點的集合。Prim算法 將節點/添加到S中，如果^S， 7er-S，而且邊(/,力有最低費用。當5 =廠時， 算法將終止。在發明的方法中，選擇下一個節點的標準並不是簡單的基於邊的 費用，而是基於信息素和啟發式信息的乘積。設邊O',力的信息素和啟發式信息的乘積表示為力(/,力，其中r(z'，力表示 信息素的取值，7a力表示啟發式信息的取值。在發明的方法中，啟發式信息的 設置為formula see original document page 9否則其中A = max(l V1 |VG ,| VD |/| VG I)和a = min(l V1 |VG ,| VD |/| VG I)分別表示目標 節點和中間節點的加強率，〃 =/iD= max(l F, l V1 |VG ,| VD |/| VG I)|)稱為目標節點和 中間節點的加強比例。4是距離完全圖中連接節點z'和/的邏輯邊的費用。/7是 一個正常數。運用以上的啟發式方法使得算法更傾向於選擇目標節點。當不同的邊有一 樣的費用時，貪婪操作更傾向於選擇^中的節點。基於以上所介紹的Prim算法和啟發式信息的設置，運用蟻群對網絡進行搜 索。發明的距離完全蟻群算法是一種運作於距離完全圖上的，基於蟻群算法框 架的帶概率的Prim算法。其包含以下步驟(l)初始化formula see original document page 10將螞蟻A放置於隨機選擇的目標節點/上，讓它開始搜索。 (2)路徑的構建螞蟻將會根據狀態轉移規則以一定的概率選擇下一個節點J，其公式如下arg max,/， 否則其中，/是螞蟻當前所在節點，0,是當前螞蟻還未曾訪問過的節點的集合，g是均勻分布在區間[O， l]中的隨機變量，《o (O^^l)是一個參數。r(z))表示連接 節點Z和r的邊上的信息素取值。/70))表示從節點/選擇節點r的啟發式信息值。 由於已經預先建立了距離完全圖，因此任意兩個節點都是邏輯相連的。如果隨 機產生的《小於⑨，螞蟻就會選擇信息素和啟發式信息乘積最大的未訪問節點。 否則，螞蟻將按照一個稱為隨機比例規則的概率行為選擇規則，來決定下一個 節點，螞蟻選擇節點/的概率為，如果風o, 否則(3)邊的擴展和局部信息素更新-當一隻螞蟻完成解的構建後，它所訪問過的邊上的信息素將會被降低。這 是為了防止大量的螞蟻選擇相同的路徑，使得其它螞蟻能夠分散地搜索整個網 絡。局部信息素的更新將會分兩步執行， 一個是邏輯邊上的信息素更新，另一 個是真實邊上的信息素更新。邊(/，力上的信息素根據以下公式進行更新力=(1 — P). r(/，力+ p. rmin 其中/ (戶e(0，l])是信息素的蒸發率。7^是每個邊上的信息素的下限。由於 ra_/)2rmin ，更新後的信息素小於或者等於原來的取值。當下一個節點j'選擇完成後，螞蟻就會從節點z'移動到節點乂。由於螞蟻是 在距離完全圖中移動的，因此邏輯邊(/，力可以擴展為真實路徑仏 .，0。",…，力。 例如，如圖3所示需要更新邏輯邊(1,6)的信息素，而邏輯邊(1,6)可以表示為路 徑{1，2，3,4,5,6}，所有相關的邊(1,2)， (1，3)， (1,4)， (1， 5)， (1,6)， (2,3), (2,4)， (2,5)， (2， 6)， (3， 4)， (3,5)， (3,6)， (4,5)， (4,6)， (5， 6)，以及它們的對稱邊(例如(2， l))上的信息素都會根據公式進行更新。局部信息素更 新後，在附近區域的信息素濃度將降低。(4) 檢查螞蟻是否完成構建所有螞蟻經過的節點和邏輯路徑擴展後經過的節點都被當作已訪問的節 點。螞蟻完成構建的結束條件為它訪問過所有的源節點和目標節點。如果結束 條件未滿足，則回到步驟二繼續搜索。否則，就認為螞蟻完成了多播樹的構造。(5) 冗餘檢測修正當螞蟻完成連接源節點和目標節點的多播樹的構造後，必須對這個樹進行 冗餘檢測。首先，對訪問過的節點執行Prim算法。如果得到的最小生成樹的費用低於 螞蟻構造的樹，螞蟻得到的解就會被最小生成樹代替。然後，檢查無用的中間節點，將那些只有一個輸出端的中間節點刪除。 以上兩個步驟不斷重複，直到生成的樹不能再優化為止。 冗餘的檢測和修正也可以作為多播路由問題的一種確定性算法。將^中的 所有節點作為輸入，樹可以逐漸地被修正，得到的結果仍然是最小生成樹而且 是問題的一個可行解。雖然這種方法不能夠得到最好的樹，但是卻可以根據其 結果來初始化信息素。於是，在每條邊上的信息素的初始值設定為其中t;是根據確定的冗餘檢測修正方法得到的樹的費用。(6) 全局信息素更新當m只螞蟻都完成了樹的構造後，對歷史最優的生成樹執行全局信息素的 更新。在最優生成樹的真實邊上的信息素如下更新r 0', _/ ) = (1 - / ) r(z',力+ . A r 其中At^1/7L,， 7L,為最優生成樹的總的費用。在最優生成樹的邏輯邊上的信息素也同樣需要更新。假設節點z'和y之間選 定的真實路徑為("。，A, "2，...， ~)，其中"。=/，^為路徑中邊的數量。 則，邏輯邊(z'，力上新的信息素等於formula see original document page 12隻有最優生成樹中的真實邊和邏輯邊上的信息素被加強，得到信息素加強 的邊會吸引更多的螞蟻去利用它們。(7)重複步驟(1)至(6)直到滿足結束條件。 距離完全蟻群算法的總體流程圖如圖4所示。為了驗證算法的有效性，以OR庫中b組的Steiner問題為例，對發明的距 離完全蟻群算法和Leung的遺傳算法進行比較。發明的算法的具體參數設置為 《。=0.9， z -O.l， 7min=r。， m = 100， - = 2。 Leung提出的遺傳算法在所有問 題上都能100%地求得最優解，而本文提出的算法除了 Steinb13問題外，對於其 它問題也能100%得到最優解。但本文提出的算法在四個循環內就能解決大部分 的問題，因此求解速度優於遺傳算法。從測試結果中可以看出，發明的距離完 全蟻群算法可以更加快速地解決多播路由問題。
權利要求
1、一種基於距離完全蟻群算法的多播路由方法，其特徵在於，該方法包括以下步驟(1)運用Floyd算法建立多播路由網絡的距離完全圖。(2)初始化算法的各個參數。設定距離完全圖每條邊上的信息素的初始值為 τ0＝1/(|VG|·Ts)其中Ts是根據確定的冗餘檢測修正方法得到的樹的費用。(3)隨機選擇一個目標節點讓螞蟻k開始搜索。螞蟻將會根據狀態轉移規則以一定的概率選擇下一個節點j，其公式如下其中，i是螞蟻當前所在節點，Θk是當前螞蟻還未曾訪問過的節點的集合，q是均勻分布在區間
中的隨機變量，q0(0≤q0≤1)是一個參數。τ(i，r)表示連接節點i和r的邊上的信息素取值。η(i，r)表示從節點i選擇節點r的啟發式信息值。選擇完成後，對螞蟻經過的邊進行局部信息素的更新。局部信息素的更新將會分兩步執行，一個是邏輯邊上的信息素更新，另一個是真實邊上的信息素更新。螞蟻k不斷重複以上選擇過程，直到它經過所有所有的目標節點，從而得到一棵螞蟻構造的多播樹。(4)對螞蟻構造的多播樹執行冗餘檢測和修正。首先，對訪問過的節點執行Prim算法。如果得到的最小生成樹的費用低於螞蟻構造的樹，螞蟻得到的解就會被最小生成樹代替。然後，檢查無用的中間節點，將那些只有一個輸出端的中間節點刪除。以上兩個步驟不斷重複，直到生成的樹不能再優化為止。(5)重複步驟(3)和(4)直到所有螞蟻都完成解的構造。(6)對歷史最優的多播樹進行全局信息素的更新。在最優生成樹的真實邊上的信息素如下更新 τ(i，j)＝(1-ρ)·τ(i，j)+ρ·Δτ其中Δτ＝1/Tbest，Tbest為最優生成樹的總的費用。在最優生成樹的邏輯邊上的信息素也同樣需要更新。假設節點i和j之間選定的真實路徑為(a0，a1，a2，...，aψ)，其中a0＝i，aψ＝j。ψ為路徑中邊的數量。則，邏輯邊(i，j)上新的信息素等於
2、 基於權利要求1所述的一種基於距離完全蟻群算法的多播路由方法，其 特徵在於發明的方法是從一個隨機選擇的目標節點開始搜索的，並且運用的 Prim的最小生成樹算法來構造多播樹。
3、 基於權利要求l所述的一種基於距離完全蟻群算法的多播路由方法，其 特徵在於當一隻螞蟻完成搜索後，運用Prim算法和冗餘檢測修正方法對螞蟻得 到的解進行檢驗和修正以求得到更好的結果。
4、 基於權利要求1所述的一種基於距離完全蟻群算法的多播路由方法，其 特徵在於在啟發式信息中通過一個參數/z對目標節點的選取賦予一定的傾向 性。
全文摘要
本發明公開了一種基於距離完全蟻群算法的多播路由方法。首先，為多播路由網絡建立距離完全圖。然後，基於蟻群算法和Prim算法帶隨機性地構造多播樹。其中，啟發式信息的設置使得算法更傾向於選擇目標節點。對生成的多播樹進行冗餘檢測和修正並執行局部信息素的更新。最後，當所有螞蟻都完成解的構造後，執行全局信息素的更新，對歷史最優樹上的邊進行信息素的加強。仿真測試結果，以及與同類型算法的比較顯示，本發明的距離完全蟻群算法可以更加快速地解決多播路由問題。
文檔編號H04L12/56GK101237408SQ20081002647
公開日2008年8月6日 申請日期2008年2月27日 優先權日2008年2月27日
發明者軍 張, 胡曉敏, 韜 黃 申請人:中山大學