認(rèn)知無線Mesh網(wǎng)絡(luò)中基于WTA的多約束QoS組播路由算法

謝紅，常遠(yuǎn)，解武

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱150001

?

認(rèn)知無線Mesh網(wǎng)絡(luò)中基于WTA的多約束QoS組播路由算法

謝紅，常遠(yuǎn)，解武

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱150001

摘要：針對(duì)認(rèn)知無線Mesh網(wǎng)絡(luò)傳統(tǒng)的多約束QoS組播路由算法一貫的進(jìn)行隨機(jī)初始化種群這一問題，在沒有增加智能算法的復(fù)雜度的同時(shí)，首次將武器-目標(biāo)分配問題(weapon to target allocation,WTA)應(yīng)用在群智能算法對(duì)初始種群的優(yōu)化上，基于蟻群算法，將集火射擊、分火射擊和混合射擊的思想加入到對(duì)初始種群的設(shè)計(jì)上，提出一種基于WTA的QoS組播路由優(yōu)化算法。其目標(biāo)是滿足無線組播業(yè)務(wù)的QoS約束且不增加算法復(fù)雜度的同時(shí)，結(jié)合蟻群的強(qiáng)魯棒性和并行性等性能優(yōu)勢。經(jīng)過實(shí)驗(yàn)驗(yàn)證，在網(wǎng)絡(luò)開銷和時(shí)延等方面的指標(biāo)具有很好改善。

關(guān)鍵詞：認(rèn)知無線Mesh網(wǎng)絡(luò)；多約束QoS組播路由算法；蟻群算法；初始種群

常遠(yuǎn)(1989-)，女，碩士.

繼Joseph MitolaⅢ博士和Ian F.Akyildiz博士提出認(rèn)知無線電概念和認(rèn)知無線網(wǎng)絡(luò)的概念，具有可融合多種異構(gòu)無線網(wǎng)絡(luò)、高吞吐率、高擴(kuò)展性和高可靠性的無線Mesh網(wǎng)絡(luò)(wireless mesh networks,WMN)在近幾年成為眾多學(xué)者研究的熱點(diǎn)。認(rèn)知無線Mesh網(wǎng)絡(luò)(cognitive wireless mesh networks,CWMN)是將認(rèn)無線電技術(shù)應(yīng)用于無線Mesh網(wǎng)絡(luò)中解決其頻譜缺乏的問題。作為下一代寬帶接入系統(tǒng)，CWMN擁有潛在的優(yōu)勢。Mesh路由器、Mesh網(wǎng)關(guān)、Mesh終端使用認(rèn)知無線電(cognitive radio,CR)技術(shù)。對(duì)于一個(gè)配備CR的Mesh節(jié)點(diǎn)(CR-Mesh路由器、CR-Mesh網(wǎng)關(guān)、CR-Mesh終端統(tǒng)稱CR-Mesh節(jié)點(diǎn)),它能夠感知主用戶(primary users，PU)未使用的頻譜,并動(dòng)態(tài)地接入到這些可用的頻譜。目前CWMN仍然處于早期的研究階段,面臨著許多開放性的挑戰(zhàn)。

服務(wù)質(zhì)量(quality of service，QoS)是一種安全機(jī)制，通過保證傳輸帶寬、降低數(shù)據(jù)丟包率以及時(shí)延抖動(dòng)等提高服務(wù)質(zhì)量。在資源有限的CWMN中，為保證不同業(yè)務(wù)的質(zhì)量，對(duì)QoS提出合理的要求是有必要的。

Xu[1]針對(duì)粒子群優(yōu)化算法的子維進(jìn)化問題，對(duì)進(jìn)化策略進(jìn)行維的層次化，即將整體的進(jìn)化策略改變?yōu)榫S的層次化進(jìn)化，同時(shí)對(duì)初始化種群中多樣性較差子維進(jìn)行重新初始化的操作，通過單峰函數(shù)和多峰函數(shù)的多重驗(yàn)證，該算法相比標(biāo)準(zhǔn)的粒子群優(yōu)化算法有較好的尋優(yōu)性能。Lei[2]采用混沌策略初始化種群，并利用取整運(yùn)算更新速度公式，之后通過適應(yīng)度方差和密度基因兩種策略測試出早熟現(xiàn)象的發(fā)生，并通過基因密度變異來重新初始化種群，提升全局多樣化。最后通過實(shí)驗(yàn)證明了新算法的可行性和有效性。Liu[3]針對(duì)初始化問題搭建基于的新的學(xué)習(xí)算法框架。在新的算法框架中，多個(gè)進(jìn)程并行完成整個(gè)循環(huán)。每個(gè)循環(huán)中由算法計(jì)算得到及隨機(jī)生成的位置較好的粒子將構(gòu)成一個(gè)完整的初始種群進(jìn)行下一個(gè)循環(huán)各PSO進(jìn)程。最終通過大量的實(shí)驗(yàn)證明，新算法不僅在多維優(yōu)化問題上具有良好的性能，還提升了算法優(yōu)化效果，具備靈活性和通用性。Luo[4]利用遺傳算法解決TSP問題時(shí)，為解決初始種群的敏感問題，利用鄰域法提出一種初始化種群方法，其主要思想是在選擇下一跳時(shí)在比最近城市稍遠(yuǎn)的范圍進(jìn)行隨機(jī)選取。利用通用的TSPLIB標(biāo)準(zhǔn)實(shí)例進(jìn)行驗(yàn)證，證明改進(jìn)后的算法比隨機(jī)產(chǎn)生的初始種群具有更好的多樣性，且最優(yōu)值的質(zhì)量也得到了改善，從而驗(yàn)證了改進(jìn)算法的有效性。

然而，現(xiàn)有的研究多數(shù)局限于對(duì)影響蟻群算法的兩個(gè)影響因子——信息素濃度和城市距離而進(jìn)行優(yōu)化，忽視了初始種群的質(zhì)量對(duì)算法后期運(yùn)行中的影響。在人工智能算法中一般采用隨機(jī)初始化，得到的初始種群中的粒子質(zhì)量參差不齊、最優(yōu)解可能在最開始就被排除掉了，且對(duì)于解決不同的具體問題區(qū)分度不大，很容易導(dǎo)致算法的早熟現(xiàn)象，尤其是蟻群這種局部搜索能力很強(qiáng)，但全局搜索能力有限的算法。因而文中基于CWMN利用WTA(weapon totarget allocation)的組播路由算法，以初始化種群為切入點(diǎn)的QoS優(yōu)化問題的研究為QoS問題的研究提供了新的思路。

1基于WTA模型的初始種群描述

1.1WTA模型

(1)

1.2 3種射擊方式的初始種群描述

1.2.1 集火射擊的初始子群

集火射擊是指多對(duì)一的射擊方式，是在客觀條件(如遠(yuǎn)程、命中率低)不利于射擊時(shí)所通常采用的方式。其初始子群個(gè)體數(shù)為n，表示方式如式(2)所示。

(2)

1.2.2 分火射擊的初始子群

分火射擊是指一對(duì)一的射擊方式，是在客觀條件(如近距離、命中率高等)利于射擊時(shí)通常所采用的射擊方式。其初始種群的個(gè)體數(shù)為|m-n|+1，其表示方式如式(3)所示：

(3)

1.2.3 混合射擊的初始種群

在實(shí)際情況中，一般是采用混合射擊的方式，文中采用了基于混合射擊方式的初始種群隨機(jī)產(chǎn)生方式。其表示方式如式(4)所示：

(4)

(5)

2問題描述以及智能算法描述

2.1蟻群算法

蟻群算法作為一種新興的群智能算法，因其特有的以信息素[5]變化帶來的正反饋特性、較強(qiáng)的魯棒性和局部搜索能力而成為各個(gè)領(lǐng)域的專家學(xué)者的研究焦點(diǎn)，并且廣泛應(yīng)用于指派問題[6]、流水線調(diào)度問題[7]、基于圖論的著色問題[8]、車載網(wǎng)絡(luò)的路徑規(guī)劃[9-11]、系統(tǒng)智能識(shí)別[12]、智能機(jī)器人的TSP規(guī)劃、故障識(shí)別檢測[13-16]等。但蟻群算法存在的一些不足也令學(xué)者們頭疼不已，算法的初期由于缺乏對(duì)目標(biāo)的具體信息，螞蟻用大量時(shí)間和混亂的信息分布進(jìn)行盲目搜索，導(dǎo)致前期的信息素分布混亂而分散，對(duì)尋優(yōu)可能產(chǎn)生誤導(dǎo)；不同的螞蟻對(duì)信息理解程度存在偏差，不能夠靈活變通，有時(shí)甚至?xí)虉?zhí)地去相信錯(cuò)誤的信息，導(dǎo)致了整個(gè)群體的收斂性很差；信息素的釋放量沒有區(qū)分度，導(dǎo)致了最優(yōu)路徑容易被埋沒在其他路徑中，影響整個(gè)算法的迭代速度。

2.2蟻群算法的模型

蟻群算法通常通過以下幾步完成尋優(yōu)過程：

1) 蟻群的初始化

設(shè)置最大迭代次數(shù)NC，并初始化螞蟻種群以及可選路徑上的信息素τi,j(0)，各路徑上的τi,j(0)最好設(shè)置成相等的值。清空各個(gè)螞蟻k的禁忌表tabuk。

2) 路徑的選擇

(6)

(7)

3) 信息素的更新策略

蟻群的協(xié)作有序在于，螞蟻在進(jìn)行獨(dú)立的搜索路徑時(shí)，與算法中的信息素的信息交互過程。單個(gè)螞蟻對(duì)于具體問題進(jìn)行單獨(dú)的求解，得到的最優(yōu)解添加到最終的解集，而通過對(duì)最終解集的對(duì)比求得最終的最優(yōu)解。在所有的求解過程中，每只螞蟻留下的信息素和其動(dòng)態(tài)變化又將成為下一只螞蟻尋優(yōu)的依據(jù)。因而對(duì)信息素的更新尤為重要，一般信息素的更新如式(8)～(10)。

(8)

(9)

(10)

3網(wǎng)絡(luò)模型與問題的提出

3.1網(wǎng)絡(luò)模型

QoS的作用在于將網(wǎng)絡(luò)帶寬、延遲、抖動(dòng)、開銷等QoS指標(biāo)用于顯示網(wǎng)絡(luò)在數(shù)據(jù)傳輸?shù)冗^程中的狀態(tài)，以及面對(duì)網(wǎng)絡(luò)的多突發(fā)情況甚至崩潰時(shí)所體現(xiàn)出來的性能。結(jié)合考慮網(wǎng)絡(luò)各節(jié)點(diǎn)特性以及QoS的衡量標(biāo)準(zhǔn)等各方面因素，將認(rèn)知無線Mesh網(wǎng)絡(luò)模型定義為有向圖G=(V,E)，其中V表示網(wǎng)絡(luò)中所有聯(lián)通的網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E表示所有相鄰節(jié)點(diǎn)的相連鏈路的集合，在這里我們定義Rs表示無線網(wǎng)絡(luò)節(jié)點(diǎn)的輻射范圍，di,j表示位于i，j的兩節(jié)點(diǎn)之間的物理距離，其間存在鏈路ei,j,若存在di,j≤Rs，則ei,j∈E，且規(guī)定每兩節(jié)點(diǎn)之間最多存在一條鏈路。對(duì)任意節(jié)點(diǎn)vi∈V都存在一個(gè)通信距離TR，通常情況下有3Rs>IR>Rs，在文中，沒有特殊說明的情況下，設(shè)定IR=2Rs。任意節(jié)點(diǎn)vi∈V存在一個(gè)可用信道集合Ni，而Ni，j表示vi、vj的共用信道集合，定義一個(gè)鏈路沖突集合I，其中的元素是ea,b、ec,d,(a,b,c,d∈V)，若ea,b、ec,d使用相同信道且鏈路存在(即ei,j∈E)，I(ea,b,ec,d)=1，否則I(ea,b,ec,d)=0。網(wǎng)絡(luò)有向圖中的源節(jié)點(diǎn)s、d∈V，而s到d的所有的路徑集合記為P，任何一條p∈P的路徑，其邊集定義為E(p),節(jié)點(diǎn)集定義為N(p),則對(duì)于這樣的網(wǎng)絡(luò)構(gòu)架下的QoS參數(shù)定義如下：

1) 網(wǎng)絡(luò)時(shí)延

(11)

2) 網(wǎng)絡(luò)帶寬

(12)

3)丟包率

(13)

4) 網(wǎng)絡(luò)開銷

(14)

5) 延時(shí)抖動(dòng)

(15)

而在滿足以下3點(diǎn)通信要求，網(wǎng)絡(luò)節(jié)點(diǎn)之間才能通信：

1)網(wǎng)路節(jié)點(diǎn)vi、vj的可用信道集合中存在即將通信的此通信信道，即Ni∩Nj≠；

2) 有可用的認(rèn)知射頻接口處于空閑狀態(tài)；

3) 通信距離滿足di,j≤Rs。

3.2問題的提出

基于認(rèn)知無線Mesh網(wǎng)絡(luò)的QoS組播路由算法的實(shí)現(xiàn)過程關(guān)鍵在于構(gòu)建相應(yīng)的QoS約束的組播樹。定義集合D={D1,D2,…,Dm}為組播路由的目的節(jié)點(diǎn)集合；定義S為組播路由的源節(jié)點(diǎn)；根據(jù)網(wǎng)絡(luò)無向圖的定義：G=(V,E)，定義組播樹為T=(VT，ET)，定義PT=(S,Di)為組播過程中從源節(jié)點(diǎn)到節(jié)點(diǎn)Di的路徑，用dE表示無線鏈路E上的網(wǎng)絡(luò)延遲，用BE表示無線鏈路E上的網(wǎng)絡(luò)帶寬，用CE表示網(wǎng)絡(luò)開銷。

在這里我們要明確判斷算法發(fā)生停滯的條件，定義每次迭代最優(yōu)路徑長度為Lmin，信息素濃度最大的路徑為Lmax,若Lmin

文中所要研究的問題可描述為：在認(rèn)知無線Mesh的組播業(yè)務(wù)傳輸過程中，給定無線網(wǎng)絡(luò)的范圍以及各QoS參數(shù)初始值，基于源節(jié)點(diǎn)、目的節(jié)點(diǎn)集合和QoS約束條件的組播樹建立，為每條同時(shí)滿足傳輸條件和QoS約束條件的組播可用鏈路分配相應(yīng)的信道，目標(biāo)是最大化帶寬的同時(shí)最小化網(wǎng)絡(luò)開銷和組播樹開銷。其優(yōu)化形式如式(16)所示。

(16)

文中的目的是在延遲最小化的前提下，通過對(duì)算法的相關(guān)改進(jìn)均衡組播樹開銷和帶寬約束，從而使整個(gè)無線網(wǎng)絡(luò)系統(tǒng)能夠在網(wǎng)絡(luò)業(yè)務(wù)與無線用戶終端的交互在QoS的保障下完成數(shù)據(jù)業(yè)務(wù)交互。

4改進(jìn)策略

4.1基于蟻群參數(shù)因子的動(dòng)態(tài)調(diào)整

文中借鑒已有的研究，對(duì)算法的全局搜索能力和收斂性起到關(guān)鍵作用的蟻群參數(shù)分別是信息素?fù)]發(fā)系數(shù)ρ、信息素影響因子α、期望影響因子β和信息素濃度τi,j，在算法進(jìn)行尋優(yōu)過程時(shí)，若各個(gè)相關(guān)參數(shù)能夠通過解的分布情況和判斷是否陷入局部最優(yōu)而進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整，從而在每一次循環(huán)中動(dòng)態(tài)微調(diào)的蟻群參數(shù)能夠引導(dǎo)螞蟻向最優(yōu)路徑靠攏并降低算法停滯發(fā)生的概率。算法中各個(gè)參數(shù)的動(dòng)態(tài)變化如式(17)～(19)所示。

(17)

(18)

(19)

4.2信息素濃度的動(dòng)態(tài)調(diào)整

文中利用最大最小蟻群算法[17]對(duì)信息素濃度的限定，規(guī)定限定范圍τi,j∈[τmin,τmax]，其對(duì)信息素濃度τi,j的動(dòng)態(tài)調(diào)整方式如式(20)所示：

(20)

4.3初始種群的調(diào)整

從經(jīng)驗(yàn)來看，實(shí)際情況中混合射擊方式的比重較大，而集火射擊方式的情況并不常見?？紤]到實(shí)際應(yīng)用的問題，對(duì)3種類型的初始種群進(jìn)行依概率采用?；谑?2)～(5)的描述，對(duì)改進(jìn)后的初始種群S描述如下：

(21)

式中：q1,q2,q3分別是3類初始種群的權(quán)重系數(shù)，體現(xiàn)了相關(guān)類型初始種群在算法中的相關(guān)性，q的值越大代表其相關(guān)性越大，對(duì)算法的影響也就越大。參照實(shí)際情況中集火射擊、分火射擊和混合射所占的比例，結(jié)合采用蟻群算法的QoS組播路由算法的實(shí)現(xiàn)過程：螞蟻在覓食過程中通常是一只螞蟻尋找單一食物，偶爾出現(xiàn)單只螞蟻找到多處食物，而多只螞蟻尋找單一食物不具備現(xiàn)實(shí)意義，且在算法中將

避免這一現(xiàn)象的產(chǎn)生，以減少尋優(yōu)效率過低的發(fā)生。由以上可以得知：q1

4.4改進(jìn)蟻群算法的方案描述

2) 清空禁忌列表，迭代次數(shù)NC自動(dòng)增加，螞蟻群體位于源節(jié)點(diǎn)，將源節(jié)點(diǎn)置于禁忌表中。

3) 螞蟻開始尋優(yōu)過程，k的值增加1。

5) 判斷可選節(jié)點(diǎn)的集合是否為空，若是則轉(zhuǎn)移到上一步，否則根據(jù)式(8)對(duì)信息素進(jìn)行動(dòng)態(tài)更新。

6) 求此次迭代得到的最優(yōu)解，按照式(20)對(duì)信息素進(jìn)行動(dòng)態(tài)更新。

7) 判斷所有螞蟻是否已經(jīng)都進(jìn)入此次循環(huán)，若是則進(jìn)行下一步，否則返回步驟3)。

8) 若得到的最優(yōu)路徑長度Lmin小于信息素濃度最大路徑Lmax則按照式(17)～(19)對(duì)期望影響因子β、信息素影響因子α以及信息素?fù)]發(fā)系數(shù)ρ進(jìn)行動(dòng)態(tài)更新并繼續(xù)下一步，否則直接進(jìn)行下一步。

9) 將此次迭代得到的最優(yōu)解及之間得到的最優(yōu)解進(jìn)行比對(duì)，若此次最優(yōu)解質(zhì)量不如以往則對(duì)其進(jìn)行更新。

10) 判斷迭代次數(shù)NC是否達(dá)到上限，或所有螞蟻選擇相同路徑，若是則進(jìn)行下一步，否則返回步驟2)。

11) 輸出最優(yōu)解及其相關(guān)信息，算法結(jié)束。

5性能仿真及結(jié)果分析

實(shí)驗(yàn)采用MATLAB R2010a軟件進(jìn)行仿真，在Intel(R) Celeron(R) CPU 2.60 GHz，2 GB內(nèi)存，Windows Xp統(tǒng)的計(jì)算機(jī)上運(yùn)行。采用蟻群算法和基于文中改進(jìn)策略的蟻群算法的仿真對(duì)本實(shí)驗(yàn)進(jìn)行仿真對(duì)比。本次實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1　無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

表1　 網(wǎng)絡(luò)鏈路參數(shù)表

而文中所要求的是滿足網(wǎng)絡(luò)的帶寬約束的情況下考察算法的其他網(wǎng)絡(luò)特性。因而經(jīng)過精簡之后，得到的網(wǎng)絡(luò)結(jié)構(gòu)圖如圖2所示。

圖2　精簡后的無線網(wǎng)絡(luò)拓?fù)?/p>

網(wǎng)絡(luò)拓?fù)渚喓?，下面?duì)蟻群算法各個(gè)參數(shù)的初始化設(shè)置進(jìn)行擇優(yōu)選擇：

根據(jù)已有的研究成果分析中可以得到，通過設(shè)定合理的實(shí)驗(yàn)參數(shù)能夠有效發(fā)揮算法的優(yōu)勢，在一群規(guī)模設(shè)置上，為避免過大規(guī)模造成的正反饋效應(yīng)減弱、迭代速度降低和過小規(guī)模帶來的尋優(yōu)能力和算法性能的降低，根據(jù)文獻(xiàn)[15]對(duì)蟻群規(guī)模n和問題規(guī)模問題m的討論，設(shè)定n=1.5 m。因而本次試驗(yàn)中設(shè)置節(jié)點(diǎn)規(guī)模m=30，螞蟻規(guī)模n=50。而文獻(xiàn)[16]中對(duì)Q值得討論可知，Q值為100時(shí)，既保證了算法群體的尋優(yōu)效率還保證了算法的穩(wěn)定性。

而文獻(xiàn)[17]給出了信息素?fù)]發(fā)系數(shù)ρ、自適應(yīng)調(diào)整信息素影響因子α和期望影響因子β的分析的討論，得到的結(jié)論是，為兼顧全局的搜索能力和收斂速度。選擇τmin=10，τmax=100，ρmin=0.1，ρmax=0.9，αmin=1，αmax=5，βmin=1，βmax=5，α=1，β=2，ρ=0.6，τ=20。

而QoS參數(shù)約束條件為：Bmin=70,Dmax=55,Lmax=10-3，DJmax=15。

通過對(duì)改進(jìn)前后算法在QoS各個(gè)指標(biāo)上的對(duì)比得到了以下3組以QoS參數(shù)指標(biāo)為測量目標(biāo)的對(duì)比圖。

圖3　組播樹費(fèi)用在算法改進(jìn)前后的對(duì)比

圖4　延時(shí)在算法改進(jìn)前后的對(duì)比

圖5　帶寬在算法改進(jìn)前后的對(duì)比

6結(jié)束語

通過以上的算法曲線對(duì)比圖可以看出：首先，由于初始種群的優(yōu)選減少了盲目尋路所消耗的費(fèi)用，從而改進(jìn)算法在組播費(fèi)用上從一開始就有了相當(dāng)大的改善，算法的多樣性也并沒有隨之降低，并且算法的費(fèi)用波動(dòng)得到了有效的控制，算法的穩(wěn)定性較好；其次，初始種群針對(duì)目的節(jié)點(diǎn)信息進(jìn)行指向性的初始化，使得算法在迭代進(jìn)行中有益的朝著目的節(jié)點(diǎn)前進(jìn)，使得前一代的信息素釋放情況對(duì)下一個(gè)迭代過程具有積極的指導(dǎo)作用，使得每一代的收斂速度有效提高，從而時(shí)延現(xiàn)象在算法改進(jìn)后得到的有效改善；最后，具有靶向性的初始化種群優(yōu)化策略，保障了無法避免的時(shí)延抖動(dòng)現(xiàn)象的網(wǎng)絡(luò)環(huán)境也能夠滿足語音視頻這類抖動(dòng)敏感的業(yè)務(wù)在低速率鏈路狀態(tài)時(shí)的順暢運(yùn)行。

因此，采用文中提出的基于蟻群算法的改進(jìn)算法在保證不增加算法復(fù)雜度的同時(shí)，提高初始種群的整體質(zhì)量，QoS指標(biāo)性能有了較顯著的提升，收斂速度也隨之加快，因而改進(jìn)是有效的。

參考文獻(xiàn):

[1]徐慧. 粒子群優(yōu)化算法改進(jìn)及其在煤層氣產(chǎn)能預(yù)測中的

應(yīng)用研究[D]. 北京:中國礦業(yè)大學(xué), 2013: 11-45.

[2]雷翻翻. 非線性規(guī)劃問題的粒子群優(yōu)化算法研究[D]. 銀川: 北方民族大學(xué), 2011: 09-25.

[3]劉東. 粒子群優(yōu)化算法及其工程應(yīng)用研究[D]. 重慶: 西南交通大學(xué), 2013: 36-50.

[4]羅辭勇, 盧斌, 劉飛. 一種求解TSP初始化種群問題的鄰域法[J]. 重慶大學(xué)學(xué)報(bào),2009, 32(11): 1311-1315.

[5]DORIGO M. Optimization,learning and natural algorithms[D]. Milano, Italy: PolitecnicodiMilano, 1992: 97-105.

[6]MANIEZZO V, COLORNIA, DORIGO M. The ant system applied to the quadratic assignment problem[J]. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(5): 769-778.

[7]COLORNI A, DORIGO M, MANIEZZO V, et al. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research, Statistics and Computer Science, 1994, 34(1): 39-53.

[8]COSTA D, HERTZA. Ants can colour graphs[J]. Journal of the Operational Research Society, 1997, 48(3): 295-305.

[9]BULLNHEIMER B, HARTL R F, STRAUSSC. An improved ant system algorithm for the vehicle routing problem[J]. Annals of Operations Research, 1999, 89: 319-328.

[10]SANTOS L, COUTINHO-RODRIGUES J, CURRENT J R. An improved ant colony optimization based algorithm for the capacitated arc routing problem[J]. Transportation Research Part B: Methodological, 2010, 44(2): 246-266.

[11]GAJPAL Y, ABAD P L. Multi-ant colony system (MACS) for a vehicle routingproblem with backhauls[J]. European Journal of Operational Research, 2009, 196(1): 102-117.

[12]HU Xiaomin, ZHANG Jun, LI Yun. Orthogonal methods based ant colony search for solving continuous optimization problems[J]. Journal of Computer Science & Technology, 2008, 23(1): 2-18.

[13]邢婭浪, 何鑫, 孫世宇. 基于改進(jìn)蟻群算法的模糊控制器優(yōu)化設(shè)計(jì)[J]. 計(jì)算機(jī)仿真, 2012, 29(1): 131-134.

[14]陳建良, 朱偉興. 蟻群算法優(yōu)化模糊規(guī)則 [J]. 計(jì)算機(jī)工程與用, 2007, 43(5): 113-115.

[15] STüTALE T, HOOS H H. Max-min ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

[16]段海濱. 蟻群算法及其在高性能電動(dòng)仿真轉(zhuǎn)臺(tái)參數(shù)優(yōu)化中的應(yīng)用研究[D]. 南京: 南京航空航天大學(xué), 2005: 9-20.

[17]王健安. 基于蟻群優(yōu)化算法的分布式多約束QoS路由算法研究[D]. 長春: 長春理工大學(xué), 2014: 26-28.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1191.U.20151206.1024.024.html

Multi-constraint QoS multicast routing algorithm based on the

WTA in the cognitive wireless mesh network

XIE Hong, CHANG Yuan, XIE Wu

College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001

Abstract：In view of the problem that cognitive wireless mesh network’s multi-constraint QoS multicast routing algorithm has always been the traditional random initialization of the population, this paper, on the premise of not increasing complexity of the intelligent algorithm, for the first time applies the Weapon To Target (WTA) allocation to the optimization of initial population in swarm intelligence algorithm. Based on the ant colony algorithm, WTA mixes the concentrated fire, distributed fire and mixed fire ideas to the design of the initial population. An QoS multicast routing optimization algorithm is proposed based on WTA. The aim is to meet the QoS constraints of wireless multicast service while not increasing complexity of the algorithm at the same time, in combination with strong robustness of ant colony and performance advantages such as parallelism. The experiment verifies that the algorithm has good improvement in aspects of network cost and delay index.

Keywords：cognitive wireless mesh network; multi-constraint QoS multicast routing algorithm; ant colony algorithm; initial population

通信作者：常遠(yuǎn)，E-mail：466959339@qq.com.

作者簡介：謝紅(1962-)，女，教授，博士生導(dǎo)師；

基金項(xiàng)目：黑龍江省自然科學(xué)基金資助項(xiàng)目(F201339).

收稿日期：2014-12-07.網(wǎng)絡(luò)出版日期：2015-12-06.

中圖分類號(hào)：TN911

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-671X(2015)02-045-07

doi:10.11991/yykj.201412008