基于免疫螞蟻算法的多約束QoS路由選擇算法

1、基于免疫螞蟻算法的多約束QoS路由選擇算法陳榮元（長沙交通學(xué)院計算機(jī)系，湖南 長沙 410076）摘要：本文針對多約束路由選擇問題，提出了一種新穎的免疫螞蟻算法。不失一般性，選擇費(fèi)用、帶寬、延時、丟失率和時延抖動為QoS參數(shù)，專門設(shè)計了該算法的實現(xiàn)步驟和流程圖。最后，實例表明所提出的算法是有效的。關(guān)鍵詞：QoS路由選擇；免疫螞蟻算法；費(fèi)用；時延；帶寬；丟失率A Multiple Constrained QoS Routing Based on Immune and ant AlgorithmCHEN Rongyuan（Dept.of Computer,Changsha Communicatio

2、n University,Changsha 410076 China）Abstract:The paper aims at the problem of QoS routing with multiple Constraint, presents a novel immune and ant algorithm .Without losing generality, cost, bandwidth, delay and loss rate are chosen as QoS parameters ,the concrete realization steps and steam chart w

3、ere designed. Finally, an example demonstrates that the algorithm is effective and efficient.Key words: QoS routing;immune-ant algorithm;cost;delay;bandwidth;loss rate1 引言QoS路由的主要目標(biāo)是為接入的業(yè)務(wù)選擇滿足服務(wù)質(zhì)量要求的傳輸路徑，同時保證整個網(wǎng)絡(luò)資源的有效利用。度量參數(shù)選擇問題、尋徑問題和路由信息不準(zhǔn)確問題是QoS路由中的幾個主要研究內(nèi)容。本文著重研究多約束QoS路由選擇問題。多約束QoS路由選擇是指在網(wǎng)絡(luò)中尋找一條滿

4、足傳輸帶寬、鏈路時延、時延抖動和信息丟失率等約束條件，并使通信費(fèi)用最小的路徑。多約束QoS路由選擇是一個NP完全問題11。遺傳算法5、Hopfield 神經(jīng)網(wǎng)絡(luò)方法689 、螞蟻算法1015、點(diǎn)火耦合神經(jīng)網(wǎng)絡(luò)方法12等都有人用來求解多約束QoS路由選擇問題。遺傳算法是一種啟發(fā)式隨機(jī)搜索算法，求解組合優(yōu)化問題時存在的主要問題是遺傳進(jìn)化的性能與遺傳算子以及適應(yīng)度函數(shù)的設(shè)計密切相關(guān)，遺傳進(jìn)化容易收斂到局部最優(yōu)。Hopfield網(wǎng)絡(luò)求解組合優(yōu)化問題近年來十分活躍，但其網(wǎng)絡(luò)能量函數(shù)的設(shè)計和網(wǎng)絡(luò)局部極小點(diǎn)的逃離等仍未得到很好解決；網(wǎng)絡(luò)的負(fù)梯度下降本質(zhì)上使得網(wǎng)絡(luò)收斂到局部最優(yōu)解。目前這方面的研究包括引入?yún)?shù)

5、Hopfield網(wǎng)絡(luò)和Hopfield網(wǎng)絡(luò)能量函數(shù)的改進(jìn)8 9。點(diǎn)火耦合神經(jīng)網(wǎng)絡(luò)方法12利用耦合神經(jīng)網(wǎng)絡(luò)方法的自動波生成和傳播特性求解QoS路由選擇問題收到了較好的效果。螞蟻算法1015是目前QoS路由中研究比較多的一種方法，由Dorigo等提出1314 ，該算法是一種分布式探測尋路方法，具有全局尋優(yōu)能力。缺點(diǎn)是算法中參數(shù)較多，選擇尚無理論指導(dǎo)，不能保證收斂于全局最優(yōu)。免疫網(wǎng)絡(luò)理論最初由Jerne提出16，在此基礎(chǔ)上提出了許多人工免疫工程方法，包括基于免疫系統(tǒng)而特別設(shè)計的解決約束、多模式和組合優(yōu)化問題的免疫計算方法17181920 ?；诿庖邔W(xué)的計算方法結(jié)合先驗知識和免疫系統(tǒng)適應(yīng)能力，提供了新

6、穎的解決復(fù)雜優(yōu)化問題的方法和能力。本文針對QoS路由選擇問題，提出了一種新的融合算法即免疫螞蟻算法。算法的基本思想是把待求解的問題對應(yīng)為抗原，問題的解對應(yīng)為抗體，利用螞蟻算法的全局尋優(yōu)能力和免疫算法的適應(yīng)能力求解組合優(yōu)化問題，實驗結(jié)果表明免疫螞蟻算法表現(xiàn)出了超越免疫算法和疫螞蟻算法的優(yōu)點(diǎn)，在考慮了五個路由限制的情況下，算法的效率得到了大幅度的提高。2 免疫算法原理1,2, 20免疫算法的一般框架流程如圖1所示。其中算法中的抗原通常是指目標(biāo)函數(shù)。算法中的抗體通常是指目標(biāo)函數(shù)的優(yōu)化解。算法步驟：1） 免疫細(xì)胞產(chǎn)生產(chǎn)生初始抗體：隨機(jī)產(chǎn)生N個個體或從記憶庫中提取N個個體構(gòu)成初始群體；2） 抗原與抗體相

7、遇分析問題：對問題及其解的特性進(jìn)行分析和了解，并設(shè)計解的合適表達(dá)形式；3） 抗體識別抗原對上述群體中各抗體進(jìn)行評價：通常采用基于個體濃度的適應(yīng)度評價策略；在自然免疫系統(tǒng)中，為保持抗體的多樣性，通常在鼓勵與抗原有高匹配度的抗體的同時，對濃度過高的抗體予以抑制。并且抗原與抗體的匹配不是完全匹配，而是部分匹配，從而保證任一種抗原都有至少一種抗體與之匹配。4） 抗體繁殖：基于上一步的計算結(jié)果對抗體群體進(jìn)行選擇、交叉、變異操作得到新群體。5） 判斷是否滿足結(jié)束條件。是，則結(jié)束；否，則繼續(xù)下一步操作。6） 轉(zhuǎn)去執(zhí)行第3）步。3 基于免疫螞蟻算法的QoS路由算法31問題描述網(wǎng)絡(luò)模型可以表示為賦權(quán)圖G=(V,

8、E)，其中V是圖中所有節(jié)點(diǎn)組成的集合，E是圖中所有邊的集合，每一條邊表示相鄰兩節(jié)點(diǎn)間的直達(dá)通信路徑 ，假定相鄰兩節(jié)點(diǎn)間最多僅有一條邊。 bandwidth(i)代表相鄰節(jié)點(diǎn)間的直通鏈路i的可用帶寬。對于一個路由請求R，路由算法如果能夠找到一條具有最小費(fèi)用的路徑L，同時滿足以下四個條件，L就被路由請求R就可接受。1 帶寬可用限制：, j 為L上的任意一條鏈路；2 端到端時延限制：，其中i為L上不包括起始節(jié)點(diǎn)的其他所有的節(jié)點(diǎn)，j為L上的任意一條鏈路； 3 端到端丟失率限制： , 其中i為L上不包括起始節(jié)點(diǎn)的其他所有的節(jié)點(diǎn)；4 端到端時延抖動限制：NDV(aim)jitter, NDV(aim)是在

9、目的節(jié)點(diǎn)的延時變化。其中bandwidth、delay、loss、和jitter分別代表QoS要求的帶寬、時延、丟失率和時延抖動限制。32采用免疫螞蟻算法的QoS路由從第二部分地區(qū)免疫算法的一般步驟的描述可以看出，免疫算法中有幾個關(guān)鍵點(diǎn)在具體實現(xiàn)時是要認(rèn)真考慮的，一是抗體和抗原的編碼形式；二是抗原與抗體的匹配規(guī)則；三是抗體的評價方法；四是新抗體的產(chǎn)生和新群體的形成規(guī)則；五是記憶庫的設(shè)計和使用。L(f、n1,n2,nk、a) cost delay loss jitter1、 抗體的編碼形式如下： 記為A(L(f、n1,n2nk、a)、cost、delay、loss、jitter)，其中L(f、n

10、1,n2nk、a)、cost、delay、loss、jitter分別表示路徑、抗體的實際費(fèi)用、時延、丟失率和時延抖動。from aim bandwidth delay loss jitter2、 抗原的編碼形式如下：記為R(from 、aim、bandwidth、delay、loss、jitter)表示，其中from 、aim，bandwidth、delay、loss、jitter分別表示路由請求的源節(jié)點(diǎn)、目的節(jié)點(diǎn)，所需帶寬和允許的最大延時、丟失率、時延抖動。3、 抗原與抗體的匹配規(guī)則：如抗體的L(f、n1,n2nk、a)是以抗原的from為起點(diǎn)aim為終點(diǎn)的不間斷的路徑，且滿足四個約束條件，

11、抗原與抗體就匹配規(guī);否則不匹配。4、 抗體的評價方法： 對于多個抗體（候選解），通常根據(jù)抗體和抗原間的親和力(applicability)的大小來判斷哪一個是最優(yōu)抗體（最優(yōu)解），本文中的親和力定義為： 其中：maxconst是一個比較大的常數(shù)， c、d、l、j是常數(shù)，在算法中，根據(jù)cost、delay、loss和jitter的相對重要性來選定它們的值。5、 新抗體的產(chǎn)生和新群體的形成規(guī)則：利用螞蟻算法產(chǎn)生一批新抗體，再把它們和局部記憶庫中的現(xiàn)有抗體一起進(jìn)行配對、交叉產(chǎn)生一批新抗體；最后從新產(chǎn)生和局部記憶庫中的抗體中選取applicability值大的一批作為新抗體群。6、 憶庫的設(shè)計和使用：算

12、法中采用兩個記憶庫（局部和全局記憶庫），局部記憶庫是存儲求解某個抗原過程中局部最優(yōu)抗體，規(guī)模為10；全局記憶庫是用來存儲針對某個抗原最終求得的最優(yōu)抗體，規(guī)模為5。7、抗體交叉規(guī)則：多個抗體隨機(jī)配對后,在一對抗體中尋找相同節(jié)點(diǎn)(源節(jié)點(diǎn)和目節(jié)點(diǎn)除外)，若有多個相同節(jié)點(diǎn)就隨機(jī)選一個作為交叉點(diǎn)。例：A（2、4、5、8）和B（2、3、4、8）是配對后的一個對抗體，我們選擇節(jié)點(diǎn)4為交叉點(diǎn)，交叉后得到兩個新抗體C（2、4、8）和D（2、3、4、5、8）。螞蟻算法3,4,10涉及到三種主要規(guī)則（狀態(tài)轉(zhuǎn)移，全局和局部信息素更新），文獻(xiàn)13已證明了同時采用全局和局部兩種更新規(guī)則可以取得更快的全局優(yōu)化結(jié)果，本文采用

13、兩種更新規(guī)則。三種規(guī)則定義如下：1狀態(tài)轉(zhuǎn)移規(guī)則：螞蟻在節(jié)點(diǎn)f處選擇節(jié)點(diǎn)t的概率 (2) 其中：i為所有與f存在直接邊的節(jié)點(diǎn)。 2局部信息更新規(guī)則： 其中a0,b0,const是常數(shù)3全局信息更新規(guī)則：其中：a1,b1是常數(shù)，price是最優(yōu)抗體和抗原的親和力算法中把網(wǎng)絡(luò)兩節(jié)點(diǎn)間直接存在的通路作為自我，也作為一個基因，為了提高效率，在程序開始前拒絕那些時延抖動不能滿足的請求；并過濾掉那些帶寬小于需求帶寬的邊，具體實現(xiàn)中是令這些邊的信息素為零；在針對某個抗原尋找抗體的過程中先不考慮延時、丟失率的限制，而是等找到抗體后再判斷新求得的抗體是否滿足要求。根據(jù)上述分析得到算法如下（算法流程見圖2）：1)

14、輸入請求：輸入請求R(from 、aim、bandwidth、delay、loss、jitter)；2) 否定選擇：判斷路由請求是不是自我（即檢查源目節(jié)點(diǎn)間是否存在直接通路），如是就作為一個初始抗體；3) 查詢記憶庫：檢查全局記憶庫中有無該請求，如有就作為一個初始抗體；4) 產(chǎn)生初始抗體：采用螞蟻算法結(jié)合路由請求（抗原），遵循狀態(tài)轉(zhuǎn)移規(guī)則產(chǎn)生一批初始抗體；按公式（3）進(jìn)行信息素更新；5) 抗體更新：利用螞蟻算法產(chǎn)生新抗體，并把它們和局部記憶庫中的現(xiàn)有抗體一起進(jìn)行配對、交叉產(chǎn)生新抗體；6) 計算親和力applicability和抗體選擇：按公式（1）計算各個抗體的親和力applicability

15、，選取一批較優(yōu)的存入局部記憶庫中；根據(jù)新入記憶庫的那些抗體按公式（4）進(jìn)行信息素更新；7) 如果滿足結(jié)束條件就輸出結(jié)果，最優(yōu)抗體取代全局記憶庫中最少被選為初始抗體的那個記憶細(xì)胞，結(jié)束循環(huán)；否則轉(zhuǎn)第5）步。4 實例仿真圖3是本文所采用的網(wǎng)絡(luò)拓?fù)?，圖中每個頂點(diǎn)用表示，其中的元素分別代表節(jié)點(diǎn)時延、節(jié)點(diǎn)丟失率和節(jié)點(diǎn)時延變化。每條邊用表示，其中的元素分別代表邊的費(fèi)用、帶寬和鏈路時延。假定有五個路由請求,它們QoS的參數(shù)見表1。為了使在保證滿足帶寬、時延、丟失率和丟失率的前提下，優(yōu)先使費(fèi)用達(dá)到最小，再盡量使時延、丟失率和時延變化最小，多次試算后，我們最終選取仿真參數(shù)為：a0=0.069, const=0.

16、3210, a1=2.210-7,b0=b1=0.05,maxconst=100000，c=1000,d=100,l=10,j=1。每條邊初始pheromone取為100，每一次迭代放出個螞蟻，獲得全局優(yōu)化結(jié)果如表1所示。此仿真的平均迭代10次就能得到最優(yōu)解，小于基于螞蟻算法的QoS路由調(diào)度方法迭代次數(shù)（134次）3和基于遺傳算法（GA）的QoS迭代次數(shù)（152次）5，更遠(yuǎn)遠(yuǎn)小于基于Hopfield神經(jīng)網(wǎng)絡(luò)的QoS路由選擇迭代次數(shù)（10941次）6。5 結(jié)論與分析本文提出了免疫螞蟻算法來解決QoS路由受限問題，在螞蟻算法處理QoS問題效率較高的基礎(chǔ)上，免疫算法把目標(biāo)函數(shù)和約束條件作為抗原，這就

17、能保證所生成的抗體直接與問題相聯(lián)系，收斂方向能得以控制，生成的抗體能有效排除抗原，也就相當(dāng)于求得了問題的最優(yōu)解。對與抗原親和力高的抗體進(jìn)行記憶，能促進(jìn)快速求解，即當(dāng)遇到同類抗原時，可以快速生成與之對應(yīng)的抗體。算法中的交差、變異操作增強(qiáng)了抗原識別、記憶功能和調(diào)節(jié)功能。本算法解決QoS問題達(dá)到了很高的效率，仿真也驗證了此算法的有效性。參考文獻(xiàn)：1 Watkins A, Boggess L. A New Classifier Based on Resource Limited Artificial Immune Systems. Proceedings of the 2002 Congress on

18、 Evolutionary Computation CEC2002 EC,1546-15512 Luo Wenjian and Cao Xianbin and Wang Xufa . An Immune Genetic Algorithm Based on Immune Regulation. Proceedings of the 2002 Congress on Evolutionary Computation CEC2002.801-8063 S. Zhang, Z. Liu. A QoS Routing Algorithm Based on Ant Algorithm. IEEE ICC

19、 2001, l(5):1581-15854 Isaacs J, Watkins R, Foo S. Evolving Ant Colony Systems in Hardware for Random Number Generation. Proceedings of the 2002 Congress on Evolutionary Computation CEC2002 EC,1450-14555 FENG X,LI J Z, WANG J V,et al. QoS routing based on genetic algorithmJ.Computer Communications,1

20、999,22 (15- 16):1392-1399.6 Chotpat P,Goutam C,Norio S. Neural network approach to multicast routing in real- time communication networksA. Proc International Conference on Network ProtocolsC,1995:332 3397 Kuntimad G,Rangnath H S. Perfect image segmentation using pulse coupled neural networksJ.IEEE

21、Trans Neural Networks,1999,10（3）:591-598.8 Hopfield J J.Tank D W. “Neural” computation of decisions in optimization problemsJ.Biological Cybernetics,1985,54（3）:141-152.9 Alexei N S. Parallel image processing with autowaves; segmentation and edge exaction EN/OL. 10 張素兵,呂國英,劉澤民,周正基于螞蟻算法的QoS路由調(diào)度方法電路與系統(tǒng)

22、學(xué)報，2000,5：1-511 XIAO XI-PENG,Lionel M Ni. Internet QoS : A Big PictureJ. IEEE Network, 1999,13(2):8-1812 張軍英,王德峰,石美紅.基于點(diǎn)火耦合神經(jīng)網(wǎng)絡(luò)的多約束QoS路由選擇算法.通信學(xué)報,2002,7：40-4713 Dorigo M,Gam bardella L M. Ant colony system:A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Trans.on Evplutionary Computation,1997,1(1):53-6614 Gianni Dicaro, Mario Dorigo. Ant-Net:Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research,1998,9:317-36515 R Schoonderwoerd,O Holland, J Bruten,L Rothkrant