認知無線Mesh網絡中基于WTA的多約束QoS組播路由算法

謝紅，常遠，解武

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

?

認知無線Mesh網絡中基于WTA的多約束QoS組播路由算法

謝紅，常遠，解武

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

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

關鍵詞：認知無線Mesh網絡；多約束QoS組播路由算法；蟻群算法；初始種群

常遠(1989-)，女，碩士.

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

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

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

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

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

1.1WTA模型

(1)

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

1.2.1 集火射擊的初始子群

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

(2)

1.2.2 分火射擊的初始子群

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

(3)

1.2.3 混合射擊的初始種群

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

(4)

(5)

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

2.1蟻群算法

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

2.2蟻群算法的模型

蟻群算法通常通過以下幾步完成尋優過程：

1) 蟻群的初始化

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

2) 路徑的選擇

(6)

(7)

3) 信息素的更新策略

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

(8)

(9)

(10)

3網絡模型與問題的提出

3.1網絡模型

QoS的作用在于將網絡帶寬、延遲、抖動、開銷等QoS指標用于顯示網絡在數據傳輸等過程中的狀態，以及面對網絡的多突發情況甚至崩潰時所體現出來的性能。結合考慮網絡各節點特性以及QoS的衡量標準等各方面因素，將認知無線Mesh網絡模型定義為有向圖G=(V,E)，其中V表示網絡中所有聯通的網絡節點的集合，E表示所有相鄰節點的相連鏈路的集合，在這里我們定義Rs表示無線網絡節點的輻射范圍，di,j表示位于i，j的兩節點之間的物理距離，其間存在鏈路ei,j,若存在di,j≤Rs，則ei,j∈E，且規定每兩節點之間最多存在一條鏈路。對任意節點vi∈V都存在一個通信距離TR，通常情況下有3Rs>IR>Rs，在文中，沒有特殊說明的情況下，設定IR=2Rs。任意節點vi∈V存在一個可用信道集合Ni，而Ni，j表示vi、vj的共用信道集合，定義一個鏈路沖突集合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。網絡有向圖中的源節點s、d∈V，而s到d的所有的路徑集合記為P，任何一條p∈P的路徑，其邊集定義為E(p),節點集定義為N(p),則對于這樣的網絡構架下的QoS參數定義如下：

1) 網絡時延

(11)

2) 網絡帶寬

(12)

3)丟包率

(13)

4) 網絡開銷

(14)

5) 延時抖動

(15)

而在滿足以下3點通信要求，網絡節點之間才能通信：

1)網路節點vi、vj的可用信道集合中存在即將通信的此通信信道，即Ni∩Nj≠；

2) 有可用的認知射頻接口處于空閑狀態；

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

3.2問題的提出

基于認知無線Mesh網絡的QoS組播路由算法的實現過程關鍵在于構建相應的QoS約束的組播樹。定義集合D={D1,D2,…,Dm}為組播路由的目的節點集合；定義S為組播路由的源節點；根據網絡無向圖的定義：G=(V,E)，定義組播樹為T=(VT，ET)，定義PT=(S,Di)為組播過程中從源節點到節點Di的路徑，用dE表示無線鏈路E上的網絡延遲，用BE表示無線鏈路E上的網絡帶寬，用CE表示網絡開銷。

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

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

(16)

文中的目的是在延遲最小化的前提下，通過對算法的相關改進均衡組播樹開銷和帶寬約束，從而使整個無線網絡系統能夠在網絡業務與無線用戶終端的交互在QoS的保障下完成數據業務交互。

4改進策略

4.1基于蟻群參數因子的動態調整

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

(17)

(18)

(19)

4.2信息素濃度的動態調整

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

(20)

4.3初始種群的調整

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

(21)

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

避免這一現象的產生，以減少尋優效率過低的發生。由以上可以得知：q1

4.4改進蟻群算法的方案描述

2) 清空禁忌列表，迭代次數NC自動增加，螞蟻群體位于源節點，將源節點置于禁忌表中。

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

5) 判斷可選節點的集合是否為空，若是則轉移到上一步，否則根據式(8)對信息素進行動態更新。

6) 求此次迭代得到的最優解，按照式(20)對信息素進行動態更新。

7) 判斷所有螞蟻是否已經都進入此次循環，若是則進行下一步，否則返回步驟3)。

8) 若得到的最優路徑長度Lmin小于信息素濃度最大路徑Lmax則按照式(17)～(19)對期望影響因子β、信息素影響因子α以及信息素揮發系數ρ進行動態更新并繼續下一步，否則直接進行下一步。

9) 將此次迭代得到的最優解及之間得到的最優解進行比對，若此次最優解質量不如以往則對其進行更新。

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

11) 輸出最優解及其相關信息，算法結束。

5性能仿真及結果分析

實驗采用MATLAB R2010a軟件進行仿真，在Intel(R) Celeron(R) CPU 2.60 GHz，2 GB內存，Windows Xp統的計算機上運行。采用蟻群算法和基于文中改進策略的蟻群算法的仿真對本實驗進行仿真對比。本次實驗的網絡拓撲結構如圖1所示。

圖1　無線網絡拓撲結構圖

表1　 網絡鏈路參數表

而文中所要求的是滿足網絡的帶寬約束的情況下考察算法的其他網絡特性。因而經過精簡之后，得到的網絡結構圖如圖2所示。

圖2　精簡后的無線網絡拓撲

網絡拓撲精簡后，下面對蟻群算法各個參數的初始化設置進行擇優選擇：

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

而文獻[17]給出了信息素揮發系數ρ、自適應調整信息素影響因子α和期望影響因子β的分析的討論，得到的結論是，為兼顧全局的搜索能力和收斂速度。選擇τmin=10，τmax=100，ρmin=0.1，ρmax=0.9，αmin=1，αmax=5，βmin=1，βmax=5，α=1，β=2，ρ=0.6，τ=20。

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

通過對改進前后算法在QoS各個指標上的對比得到了以下3組以QoS參數指標為測量目標的對比圖。

圖3　組播樹費用在算法改進前后的對比

圖4　延時在算法改進前后的對比

圖5　帶寬在算法改進前后的對比

6結束語

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

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

參考文獻:

[1]徐慧. 粒子群優化算法改進及其在煤層氣產能預測中的

應用研究[D]. 北京:中國礦業大學, 2013: 11-45.

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

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

[4]羅辭勇, 盧斌, 劉飛. 一種求解TSP初始化種群問題的鄰域法[J]. 重慶大學學報,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]. 計算機仿真, 2012, 29(1): 131-134.

[14]陳建良, 朱偉興. 蟻群算法優化模糊規則 [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]. 南京: 南京航空航天大學, 2005: 9-20.

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

網絡出版地址：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

通信作者：常遠，E-mail：466959339@qq.com.

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

基金項目：黑龍江省自然科學基金資助項目(F201339).

收稿日期：2014-12-07.網絡出版日期：2015-12-06.

中圖分類號：TN911

文獻標志碼：A

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

doi:10.11991/yykj.201412008