蟻群算法原理與應(yīng)用(參考版)
2025-05-17 06:21本頁面
【正文】 59 211112111111 , 0()0 L A NNNdij ijijjiNNdij ijijjiFFFF L C Pi f ZF H Zothe rw i seZ L D P??????????????? ? ??????其 中 表 示 內(nèi) 節(jié) 點(diǎn) 的 端 到 端 時(shí) 延 限 制60 參考文獻(xiàn) ? Zhang S B, Liu Z M. A QoS routing algorithm based on ant algorithm. Proceedings of the IEEE ICC, 2021,5:15811585 ? 張素兵 , 劉澤民 . 基于螞蟻算法的分級 QoS 路由調(diào)度方法 . 北京郵電大學(xué)學(xué)報(bào) . 2021, 23(4):1115 61 ? /aai2021 –課件 –論文 。 57 分級路由實(shí)例 ? 尋找 → – 首先確定出 level1路由： x→ b→ c或 x→ a→ c – 假定選 x→ a→ c, 則可得出三個(gè)源一目的對 : ? (, ) ? (, ) ? (, ) – 同時(shí)啟動(dòng)三個(gè)蟻群算法計(jì)算出滿足要求的路由鏈路 ? (→ → ), (→ ), ( → → → ) – 根據(jù)此結(jié)果，可擴(kuò)展出最終路由 ? → → → → → → → ) – 若此路由滿足要求就結(jié)束；否則，重新選定 level1路由，進(jìn)行新的選路。 56 算法構(gòu)造 (2) ? (4)根據(jù)此路由，確定每個(gè) level1節(jié)點(diǎn)內(nèi)的源一目的節(jié)點(diǎn)，作為蟻群算法的輸入，同時(shí)調(diào)用蟻群算法進(jìn)行選路 (稱為 level0路由 )，并記錄結(jié)果。 ? (2)根據(jù)呼叫的源一目的節(jié)點(diǎn)，確定此源一目的節(jié)點(diǎn)是否在同一級內(nèi)：若在 (如→ )，直接在相應(yīng)級 x內(nèi)調(diào)用蟻群算法進(jìn)行選路 (1evel0路由 )；若不在同一級內(nèi)，則執(zhí)行第 (3)步。 ? 在大多數(shù)應(yīng)用中，時(shí)延要求是最為重要的，為了方便起見，這里在研究 QoS路由時(shí)僅考慮時(shí)延限制。 52 分級 QoS螞蟻路由算法 ? 當(dāng)前的大多數(shù)大型網(wǎng)絡(luò) , 包括 Inter, 都使用分級選路方式 . 它的基本思想是 : 路由器被分成多個(gè)邏輯組 , 每個(gè)組又可以包含更小的組 . ? 計(jì)算機(jī)網(wǎng)絡(luò)分簇結(jié)構(gòu)特點(diǎn) –網(wǎng)絡(luò)管理 –路由計(jì)算 –資源利用 – Ad hoc網(wǎng)絡(luò) 53 ? 考慮一個(gè)二級網(wǎng)絡(luò)。 ? (6)選擇建立了最小費(fèi)用并滿足 QoS限制的路由的螞蟻，然后使用全局更新規(guī)則對該螞蟻所選的路由的各路徑上的信息素進(jìn)行更新。當(dāng)某只螞蟻成功地完成路由選擇后，該螞蟻所選路由各路徑上的信息素根據(jù)局部更新規(guī)則進(jìn)行更新。 50 平面 QoS螞蟻路由算法具體步驟 (2) ? (4)從蟻巢開始放出 m只螞蟻去尋找食物源，在第一個(gè)時(shí)間單位，每只螞蟻從節(jié)點(diǎn)集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，然后各螞蟻通過重復(fù)應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則來選擇各自的路徑。 ? (2)刪除帶寬小于需求帶寬的鏈路，把網(wǎng)絡(luò)濾成一個(gè)新的簡單網(wǎng)絡(luò)。 ? 通過上述定義可見，如果所選路由的總費(fèi)用最小，同時(shí) QoS限制也滿足要求，那么最優(yōu)螞蟻所選路由的各鏈路上的信息素應(yīng)該增加更多。 ? where, 0 α1 1 . The purpose of the rule is to search the globally best resolution. 111( , , ) ( 1 ) ( , , ) ( 1 )( , , ) ( 1 ) ( , , ) ( 2 )p h e r o i r s p h e r o i r s Fp h e r o i r s p h e r o i r s???? ? ???45 ? 為定義限制函數(shù) F，引入幾個(gè)符號定義： 1 i f n od e is t he n od e in the t h a nt s e l e c t e d r ou t e0 othe r w i se1 i f l i nk f r om n od e to no de is t he l i nk o f the t h a nt se l e c t e d r ou t e0 othe r w i se, , : the a virirsr s r s r sriNrsPiL B L C L D?? ????? ???a i l a bl e b a nd w i dth. c ost a nd d e l a y of t he l i nk f r om nod e t o no de 。 ? where, 0α0 1, cons is a constant. Adjusting the amount of pheromone by the rule can make the desirability of edges change dynamically. In this way, ants will make a better use of pheromone information。 42 ? where, q is a random number uniformly distributed in [0,1], qo a constant satisfying [0,1]。 –局部信息素更新規(guī)則。同時(shí)，假定 B(l)表示鏈路 l的可用帶寬，對于一個(gè)路由請求 w，路由算法如果能夠找到一條具有小費(fèi)用的路徑，同時(shí)滿足如下 4個(gè)條件，則此路由請求 w就可接受。 ? 平面 QoS路由 –所有路由器都在同一級內(nèi)， –以前對 QoS路由的研究大多采用平面網(wǎng)絡(luò)， ? 分級 QoS路由 –基本思想：將路由器分成多個(gè)邏輯組，每個(gè)組又可包含更小的組。傳統(tǒng)的路由算法很難有效地解決 NPC問題，因此一些學(xué)者基于蟻群算法提出了許多行之
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1