基于差分-精英蚁群的QoS组播路由优化算法

陈 树，许 博，徐保国

（江南大学物联网工程学院，江苏 无锡 214122）

基于差分-精英蚁群的QoS组播路由优化算法

陈 树，许 博，徐保国

（江南大学物联网工程学院，江苏 无锡 214122）

无线传感器网络通信链路在特定服务质量（QoS）下存在带宽和节点能量分配不均、延时较长，且对服务类型适应能力差等问题。为此，提出一种差分-精英蚁群算法。该算法通过差分进化算法对蚁群优化算法中的参数组合进行寻优，获得最优参数组合，并吸收了精英保存策略、蚁群排序的优点，增加算法收敛速度，利用QoS路由服务类型的特点设置目标函数。仿真结果表明，与基本蚁群算法相比，该算法能以较小的迭代次数收敛到最优解，获得系统最小熵。

蚁群算法；差分进化算法；精英保存；服务质量；熵

1 概述

无线传感器网络（Wireless Sensor Network，WSN）对性能要求不断提高，网络服务质量成为设计者必须考虑的重要因素，实质主要是从源端到目的端选择一条满足用户服务质量要求的最优路径。其本质为含多参、非线性约束的路径寻优算法问题。

目前，路径寻优研究方面，2013年，李擎等人［1］提出基于粒子群算法改进人工蚁群，优化蚁群算法的基本参数，在样本较多条件下大大减少了算法的时间成本。文献［2］提出基于差分进化优化服务质量（Quality of Service，QoS）组播路由，相比较遗传算法拥有更短的收敛时间。文献［3］提出在混合差分进化法中使用蚁群算法进行选择适当的突变运算，加速搜寻全局解。文献［4］将蚁群迭代中较好的蚂蚁通过正反馈来增加信息素浓度，来提高收敛速度，但同时也会增加陷入局部最优解的可能。文献［5］将遗传算法中排序概念扩展到精英机制当中，建立了改进蚁群算法模型，但是其蚁群参数仍依赖人工经验选取，限制了算法的泛化能力。

为此，本文在蚁群算法基础上，利用差分进化

算法对蚁群参数向量进行变异、交叉操作，获得蚁群最优参数解，在差分-蚁群基础上，优化信息素浓度更新方式，改良精英蚂蚁的奖惩机制以及排序策略，将不同QoS服务类型统一到系统熵模型当中，提出具有系统熵意识的差分-精英蚂蚁算法。

2 差分-精英蚁群算法

为了克服蚁群参数过于依赖人工经验缺陷，本文提出将差分进化算法引入蚁群系统，形成差分-蚁群，对由原始蚁群参数构成个体（α，β，ρ）进行优化选择，最终获得不同 WSN环境下的最优参数组合。

在差分-蚁群的基础上，本文对蚁群自身性能进行优化，主要表现为：（1）为获得快速收敛性，借鉴遗传算法中精英保存策略，将每次迭代时信息素按照一定准则排序，优先级较高的蚂蚁才可获得更多的信息素浓度，拥有最高信息素的蚂蚁成为本次迭代的精英蚂蚁；（2）排序策略中采用黄金分割优选法，并用自然对数的权系数递增方式平滑递增信息素；（3）将不同服务类型统一到系统熵（entropy）效用函数中，对任意服务类型在兼顾系统多决策变量指标要求下寻找系统最小熵。仿真结果表明，将提出的差分-精英蚂蚁系统应用于无线传感网QoS组播路径寻优当中，可以快速获取信息素浓度表征因子、带宽启发因子、延时启发因子最优矢量组合。在兼顾节点能耗、延时、带宽需求等关键信息量指标条件下，选择合适的熵权值系数，对 QoS服务类型使得WSN获得最小系统熵。

3 差分-蚁群算法实现

3.1 蚁群参数优化

差分进化算法基于优胜劣汰原则，是在连续空间随机搜索寻找最优解的智能优化算法，基本步骤包括变异、交叉和选择3种操作［6］。

3.1.1 优化步骤

差分进化算法优化蚁群参数步骤如下表示：

Step1 设置DE种群规模N、缩放因子F、交叉因子CR、最大迭代次数gmax。初始化种群：

其中，P0（X）表示第0代种群；表示第0代种群的第i个个体；gmax表示最大进化代数。

Step2 读取ACO适应度函数，进行个体评价并求最优解。

Step3 若达到终止条件（迭代次数到gmax，或者连续2个适应度函数值小于临界值）则算法终止，输出结果；否则转Step4。

Step4 根据下面的式（1）变异操作、式（2）交叉操作得到实验种群：

Step5 根据式（3）选择下一代的进化种群：

Step6 迭代计数器累加1，转到Step2。

3.1.2 优化效果

为了更好说明采用DE算法优化蚁群参数的优越性，读取文献［7］中国31个城市坐标数据，作为无线传感网拓扑结构的节点坐标，将本文提出的差分-精英蚁群优化（Difference-elite Ant Colony Optimization，DEACO）算法分别与基本蚁群优化算法［8］、基于遗传算法的蚁群求解算法［7］作对比。本文DE参数设置：种群规模N=20，缩放因子F=0.7，交叉因子CR= 0.8，最大迭代次数gmax=50。ACO参数设置：蚂蚁数m=13，常量Q=100，城市数量（节点个数）n=31，最大周游次数 Nc-max=200。实验环境为：内存2.0 GB，硬盘250 GB，Intel（R）Core（TM）2 Duo CPU，运行操作系统为Window s 7，使用Matlab2010编程。实验结果如表1所示。

表1 3种算法实验结果对比

从表1可以看出，DEACO算法经过23次进化迭代后，找到最优解，（α，β，ρ）=（1.185 2，6.391 5，0.750 1），最优路径长度13 092 km，比基本ACO算法路径长度少7 049 km，比文献［7］少3 356 km。实验结果表明，本文提出的DEACO算法大大降低了周游节点的长度，从而可以极大地减少网络延时与能耗，降低了网络成本。

为了更直观体现DEACO算法最优路径的情形，将采用最优（α，β，ρ）组合后得到的DEACO路径以及路径长度的收敛状况如图1所示。

图1 DEACO路径以及收敛状况

在说明了DEACO在蚁群参数自适应优化方面的优越性后，继续对算法进行优化，并在DEACO基础上得到了差分-精英系统。

3.2 精英保存策略

为保证系统能够最快收敛到全局最优解，吸收遗传算法中精英保存策略思想，当某路径信息素浓度大于信息素阈值时，信息素按照一定比率增加［9］。选择精英蚂蚁算法如下：

Step1 产生信息素阈值τon（θ），θ表示为第θ次迭代。τon（θ）=μ（τi，j（θ-1）），μ（·）为常系数连续函数。

Step2 将｛τi，j（θ）|（0＜i＜m，0＜j＜n）｝依次与信息素阈值 τon（θ）作比较，并找出满足条件的信息素集

Step4 边界判定：

本文提出的差分-精英蚁群系统将每只蚂蚁爬行距离按大小排序，按排名位次进行加权来释放信息素［10］。 更新规则策略如下：

同时对每轮周游后得到全局最优解的蚂蚁给予额外的信息素补偿：

其中，kr（0＜kr＜μ）为蚂蚁排名；κ为算法选取的蚂蚁数；L*是找到最优解长度。在一定范围内，精英蚂蚁数量与算法发现全局解具有正相关性。在超过一定范围后，由于搜索会过于快速地集中在极优解周围而导致整个系统早熟收敛。本文黄金分割取整κ：κ=ceil（0.618×m）。同时，不同于文献［11］信息素递增系数采用常比例（线性）的方式，本文根据式（5）按照自然对数的权系数递增，这种平缓的对数递增速率可以避免线性或指数性增长导致信息素陡增而陷入局部解。

4 蚂蚁的QoS熵意识

针对QoS 3种服务类型切换时调整参数存在较多的重复性工作问题，将3种服务类型统一到系统熵的效用函数上来。

依据QoS不同的服务，即音视频流服务（高带宽、耗能低、低延时），异常报警服务（低延时、耗能无要求），普通信息服务（带宽、耗能及时延要求都不高），将组播树带宽消耗w1（带宽指标）、节点剩余能量的均方差w2（耗能指标）、每轮迭代的延时w3（延时指标）作为信息量，根据不同的服务类型，为3个信息量设置不同的权系数，由此构建描述组播树稳定性好坏的表达式S，并称之为组播树的衍生熵。需

特别指出的是，w1，w2，w33个指标属于不同量纲，其数据归一化采用Z-score标准化算法，即：

其中，μ为均值；σ为标准差。

最终得到S表达式为：

其中，ki（i=1，2，3）为熵权值系数；表示w1，w2，w3的归一化数据。

针对不同的QoS服务类型，只需要修改相应权系数即可，在WSN不同的网络服务中具有较好的适应性。

5 仿真结果与分析

5.1 仿真环境

将本文提出的差分-精英蚂蚁算法应用于无线传感器网络QoS仿真实验，实验计算机系统环境与图1相同。实验中差分进化参数设置为：N=10，F= 0.8，CR=0.6，gmax=200；QoS蚁群参数设置：m= 13，Q=10，n=18，Nc-m ax=200。WSN网络18个节点由随机邻接矩阵产生，其基本参数采用系统默认设置，每个节点以及链路属性，由表2给出。链路延时邻接矩阵D、带宽邻接矩阵C均为由随机数产生的18阶方阵；除源节点外其他节点能量初始值为100 J，源节点1 000 J；衍生熵的权值系数设置为：k1=0.4，k2=0.3，k3=0.3。

表2 网络配置

5.2 实验结果

经过算法程序多次运行并选择最优解，得到实验仿真结果如图2所示。其中，图2（a）与图2（b）分别表示基本蚁群与差分精英蚁群；在带宽需求、延时上的对比仿真曲线；图2（c）表示由随机邻接矩阵生成的网络拓扑以及对应的组播路径；图2（d）表示衍生熵的收敛曲线。

图2 本文算法的网络性能仿真对比实验

在图2（a）中，基本蚁群对应的带宽需求在迭代到132次时收敛到稳定值（1.283 7），差分精英蚁群在迭代到 82次时收敛到稳定值（0.353 3）；在图2（b）中，基本蚁群对应的网络延时，在迭代到120次时收敛到稳定值（2.396 7），而差分精英蚁群在迭代到84次时，收敛到稳定值（1.410 8）。对比分析表明，相对于基本蚁群，差分精英蚁群能够以更少的迭代次数得到更好的优化值。图2（c）为随机邻接矩阵产生的网络拓扑，粗线表示在综合考虑带宽、时延、节点能量条件后，差分精英蚁群针对系统衍生熵优化后的组播路径。其原始随机网络拓扑结构生成，借鉴了最小距离均值聚类算法［12］。 图2（d）为本文提出的衍生熵收敛情况，在迭代到147次时，收敛到稳定值（0.418 1）。 6 结束语

本文针对无线传感器网络QoS路由优化问题，通过差分-蚁群获得系统最优参数组合，对比实验验证了其在优化参数、求取最佳路线上的优越性，给出差分-精英蚂蚁系统。仿真结果表明，将本文系统应用于无线传感网组播中，能够对任意QoS服务类型，以最小熵收敛到最优解，在降低网络延时以及带宽需求的同时，提高网络寿命与能量利用率。

［1］ 李 擎，张 超，陈 鹏，等.一种基于粒子群参数优化的改进蚁群算法［J］.控制与决策，2013，28（6）：873-878.

［2］ Akan O B，Akyildiz I F.Event-to-sink Reliable Transport in Wireless Sensor Networks［J］.IEEE/ACM Transactions on Networking，2005，13（5）：1003-1016.

［3］ 罗中良，易明珠，刘小勇.最优化问题的蚁群混合差分进化算法研究［J］.中山大学学报，2008，47（3）：33-36.

［4］ 郑卫国，田其冲，张 磊.基于信息素强度的改进蚁群算法［J］.计算机仿真，2010，27（7）：191-193.

［5］ 张家善，王志宏，陈应显.一种基于精英策略的改进蚁群算法及应用［J］.计算机系统应用，2012，21（10）：105-108.

［6］ Storm R，Price K.Differential Evolution——A Sim ple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］.Journal of Global Optimization，1997，11（4）：341-359.

［7］ 李明海，邢桂华.用MATLAB实现中国旅行商问题的求解［J］.微计算机应用，2004，25（2）：218-222.

［8］ 史 峰，王 辉.MATLAB智能算法30个案例分析［M］.北京：北京航空航天大学出版社，2011.

［9］ Marco D，Thomas S.Ant Colony Optimization［M］. London，UK：MIT Press，2004.

［10］ Dorigo M.A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：358-365.

［11］ Bullnheimer B，Hartl R F，Strauss C.A New Rank-based Version of the Ant System：A Computational Study［J］. Central European Journal for Operations Research and Economics，1999，7（1）：25-38.

［12］ 许 博，杨慧中.软测量建模中的数据校正［J］.河北科技大学学报，2012，33（6）：510-513.

编辑 刘 冰

QoS Multicast Routing Optimization Algorithm Based on Difference-elite Ant Colony

CHEN Shu，XU Bo，XU Baoguo

（College of Internet of Things Engineering，Jiangnan University，Wuxi214122，China）

For the communication link problem existing in Wireless Sensor Network（WSN），with the unequal distribution of bandwidth and nodes’energy，as well as longer delays and poor performance in adjustment with Quality of Service（QoS），this paper puts forward a difference-elite ant colony algorithm.The novel algorithm takes advantage of differential evolution algorithm to gain the combinatorial optimization in the ant colony algorithm，and the novel algorithm has the merit of elite preservation strategy，ant sort to improve convergence speed，and sets objective function based on QoS service types.Simulation results show that com pared with basic ant colony algorithm，the new algorithm can converge to the global optimal solution，and gains minimal entropy.

ant colony algorithm；differential evolution algorithm；elite preservation；Quality of Service（QoS）；entropyDO I：10.3969/j.issn.1000-3428.2015.10.022

陈 树，许 博，徐保国.基于差分-精英蚁群的 QoS组播路由优化算法［J］.计算机工程，2015，41（10）：117-120，125.

英文引用格式：Chen Shu，Xu Bo，Xu Baoguo.QoS Multicast Routing Optimization Algorithm Based on Difference-elite Ant Colony［J］.Com puter Engineering，2015，41（10）：117-120，125.

1000-3428（2015）10-0117-04

A

TN915

国家自然科学基金资助项目（21206053，21276111）；江苏省六大人才高峰基金资助项目（2012-W LW-006）。

陈 树（1969-），男，副教授，主研方向：无线传感器网络；许 博，硕士研究生；徐保国，教授。

2014-11-04

2014-12-03E-mail：15061805582@163.com