智能光網(wǎng)絡(luò)中選路算法的研究

摘 要：鑒于最大最小蟻群算法有很好的全局搜索能力，被廣泛應(yīng)用于智能光網(wǎng)絡(luò)的動(dòng)態(tài)選路。但是該算法存在著計(jì)算量大，收斂時(shí)間慢等缺陷。為了加快蟻群算法的收斂時(shí)間，這篇文章通過引進(jìn)，并且在TSP問題中進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明改進(jìn)型蟻群算法可以有效的提高蟻群算法的收斂時(shí)間。

關(guān)鍵字：智能光網(wǎng)絡(luò)路由；蟻群算法；TSP

智能光網(wǎng)絡(luò)憑借其可動(dòng)態(tài)分配帶寬、高效地支持大容量數(shù)據(jù)業(yè)務(wù)等優(yōu)良性能，成為了重要的通信傳輸技術(shù)。智能光網(wǎng)絡(luò)除了繼承了光傳送網(wǎng)的主要特點(diǎn)外，還具備以下優(yōu)點(diǎn)：可實(shí)現(xiàn)流量工程要求，具有靈活多樣的恢復(fù)能力，能很好地利用資源等。如果把智能光網(wǎng)絡(luò)中的所有設(shè)備都放在一個(gè)域中進(jìn)行管理，域中的每個(gè)節(jié)點(diǎn)就都需要維護(hù)一個(gè)非常龐大的數(shù)據(jù)庫信息。為解決此問題，多域智能光網(wǎng)絡(luò)應(yīng)運(yùn)而生，成為了未來傳送網(wǎng)規(guī)模化分布式管理的必然結(jié)果。本文主要針對多域光網(wǎng)絡(luò)中的關(guān)鍵技術(shù)-路由技術(shù)進(jìn)行研究。

1 智能光網(wǎng)絡(luò)中的路由算法

路由和波長分配指的是在給定一組光路連接請求、拓?fù)浯_定的情況下，尋找一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由，并為這些路由分配相應(yīng)的波長。

路由技術(shù)分為動(dòng)態(tài)路由技術(shù)和靜態(tài)路由技術(shù)。靜態(tài)路由是指光連接請求在全網(wǎng)的業(yè)務(wù)矩陣是已知的。靜態(tài)路由是在路由器中設(shè)置固定的路由。動(dòng)態(tài)路由是網(wǎng)絡(luò)中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由表的過程。

幾種常見的路由算法定義如下：

固定路由算法：各個(gè)節(jié)點(diǎn)之間的信息傳輸路徑是提前確定好的，每個(gè)節(jié)點(diǎn)僅需要將靜態(tài)路由信息存儲到其他節(jié)點(diǎn)，請求到達(dá)時(shí)，節(jié)點(diǎn)選擇默認(rèn)的到特定目的節(jié)點(diǎn)的路由。

固定備選路由算法：在固定路由算法的基礎(chǔ)上，按固定順序依次考慮一組備用路由的可用性。

自適應(yīng)路由算法：自適應(yīng)路由策略路徑不是提前固定的，而是根據(jù)當(dāng)前網(wǎng)絡(luò)鏈路狀態(tài)，動(dòng)態(tài)選擇一對節(jié)點(diǎn)之間的每條路由[2]。

本文對智能光網(wǎng)絡(luò)路由算法中的蟻群算法進(jìn)行了研究，針對該算法收斂性慢的問題進(jìn)行了改進(jìn)，提出了一種改進(jìn)型蟻群算法。

2 蟻群算法

20世紀(jì)90年代，意大利學(xué)者M(jìn).Dorigo， V.Maniezzo受到螞蟻集體尋找最短路徑覓食行為的啟發(fā)，首次提出了基于螞蟻種群的新型優(yōu)化算法，即蟻群算法[3]。該算法提出后，以此算法為基礎(chǔ)解決了一系列的組合優(yōu)化問題，如智能光網(wǎng)絡(luò)中的選路問題。

蟻群算法全局搜索能力非常好。但是，存在計(jì)算量大、收斂時(shí)間慢等缺陷。本文從蟻群算法的收斂速度出發(fā)，采用新的信息素更新策略對最大最小蟻群算法進(jìn)行了優(yōu)化。

2.1 基本蟻群算法數(shù)學(xué)模型

通過研究，螞蟻在從蟻穴到食物的過程中能夠在它經(jīng)過的路徑上釋放一種叫信息素的物質(zhì)。螞蟻在運(yùn)動(dòng)過程中能感知信息素的強(qiáng)度，從而實(shí)現(xiàn)信息的交流。算法中螞蟻工作方式如下：每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選路，通過局部和全局信息素更新找到最短路徑。

選路過程中，位于節(jié)點(diǎn)i的螞蟻用公式（1）來選擇下一節(jié)點(diǎn)j。

其中為全局信息素?fù)]發(fā)參數(shù)，與局部信息素?fù)]發(fā)參數(shù)值不相同，為一次迭代中找到的全局最優(yōu)路徑，稱之為迭代最優(yōu)路徑。

2.2 改進(jìn)型蟻群算法的基本原理

為了加快蟻群算法的收斂時(shí)間本文對基本蟻群算法的信息素更新公式做了改進(jìn)?；鞠伻核惴ㄖ校畔⑺卦隽颗c路徑長度呈線性關(guān)系，且變化較為平緩，不同長度路徑的信息素增量差別不大。針對該問題，本文提出了一種新的信息素更新策略見公式（6）。

改進(jìn)的信息素更新公式斜率大，不同長度路徑上的信息素增量的差異拉大，這樣不同長度的路徑通過信息素的累積就能更快的區(qū)分開來，從而更快的找到最優(yōu)路徑，收斂速度加快。

3 仿真與結(jié)果分析

本文分別對最大最小蟻群算法和改進(jìn)型蟻群算法，在TSP問題中進(jìn)行仿真。仿真拓?fù)錇閑il51。參數(shù)設(shè)置：m =70、=1、=4、Q =100。

圖2和圖3分別為加入最大最小信息素限制的基本蟻群算法和改進(jìn)型蟻群算法在eil51中的仿真結(jié)果。每幅圖中右圖L best2表示迭代的最優(yōu)路徑，L ave2表示迭代后各螞蟻尋路的平均值；對比兩圖，改進(jìn)型蟻群算法能夠更快地找到最優(yōu)路徑。

4 結(jié)語

本文首先對基本蟻群算法的原理進(jìn)行了介紹。然后，就基本蟻群算法收斂速度慢的問題，提出了一種改進(jìn)型蟻群算法。通過仿真驗(yàn)證了該改進(jìn)型算法的可行性。

參考文獻(xiàn)

[1].王玉亭. 智能光網(wǎng)絡(luò)層域路由算法的研究[D]. 北京：北京郵電大學(xué)，2012.

[2]. M Dorigo， G Di Caro. Ant algorithms for discrete opetimization[J]. Artificial Life， 1999， 5（3）： 137-172.

[3].M Dorigo， L M Gambardella. Ant colonies for the traveling salesman problem [J]. BioSystems， 1997， 36（43）： 73-81.

[4].陳昊. 蟻群優(yōu)化算法的原理及其應(yīng)用[J]. 湖北大學(xué)學(xué)報(bào)，2006，28（4）： 350-352.

[5].段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2005.

作者簡介

雷夢瑤（1991-），女，山西，碩士研究生，研究方向：多域智能光網(wǎng)絡(luò)路由與波長算法研究。