认知无线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