引入拥挤度概念的蜂群算法与网络组播路由研究*

吴宗月，樊丽娟，王文国

(曲阜师范大学 信息科学与工程学院，山东 日照276826)

引入拥挤度概念的蜂群算法与网络组播路由研究*

吴宗月，樊丽娟，王文国

(曲阜师范大学 信息科学与工程学院，山东 日照276826)

计算机网络中的QoS组播路由选择是一个NP完全问题，采用改进的人工蜂群算法对其进行优化。当采蜜蜂进行邻域搜索时，引入拥挤度参数可以对其数量进行调控，避免过多的采蜜蜂在同一蜜源附近搜索；当拥挤度高时则增加侦查蜂的数量，从而有效提高算法的全局搜索能力。算法通过人工蜂群遍历所有满足时延、延迟抖动、带宽、丢包率等约束条件下的可能路径，进而选择组播路由的最佳方案。对于静态网络拓扑的仿真实验表明，上述改进算法的收敛性能明显优于基本蜂群算法。

人工蜂群算法；QoS；拥挤度；组播路由

随着人们对端到端通信以及点到多点通信需求的不断增加，用户对通信的QoS(QualityofService) 要求越来越高，因此网络需要更好的QoS路由策略以满足这一趋势。这就要求网络在同时考虑时延、延迟抖动、带宽、丢包率等多个约束条件下解决最佳路由问题，而其本质是一个多目标优化问题，其解集满足Pareto最优。

基于对昆虫类社会性行为的研究，人们发现这些群体突出的特点是自组织及分布式运行，能够有效应对外界不断变化的环境。自然启发式算法借鉴了生物系统的这些行为特点，这类算法包括遗传算法、神经网络算法、蚁群算法、粒子群算法、萤火虫算法等[1-3]。群体智能是人工智能的一部分，主要研究个体在种群分散系统中的分工合作行为。例如人工蜂群可以通过相互协作求解复杂的组合优化问题[4]。

为了解决原始人工蜂群算法中执行效率低和收敛速度慢的缺点[5]，引入了拥挤度概念对其进行改进。当采蜜蜂进行邻域搜索时，通过一个拥挤度参数对采蜜蜂进行数量调控，避免过多的采蜜蜂在同一蜜源附近搜索；当拥挤度较高时，适当增加侦查蜂的数量，从而有效提高算法的全局搜索能力，特别是加快算法后期的收敛。

本文把上述改进的蜂群算法应用于解决计算机网络的QoS组播路由问题，且通过仿真实验证实了其可行性和有效性。

1 基本蜂群算法

人工蜂群算法是由Karaboga在2005年提出的一种群体、智能算法，是模拟蜂群寻找更优食物源的仿生优化模型。该模型定义了三种蜜蜂：侦查蜂、采蜜蜂和观察蜂，其工作模式为：采蜜蜂招募观察蜂去食物源附近采蜜，当蜜源开采到一定程度就会放弃开采；侦查蜂负责发现新的食物源，其评估因素包含蜜源的丰富程度、开采的难易程度等多个方面；采蜜蜂存储着有关当前蜜源的相关信息如食物源的距离、方向、丰富程度等，并在蜂巢分享给观察蜂；观察蜂在蜂巢中等待采蜜蜂分享蜜源信息，根据这些信息决定是否去开采食物源。

人工蜂群算法的主要流程如下：

(1)初始化蜜源信息。

(2)侦查蜂评估蜜源的优劣程度。

(3)重复以下四个步骤：

①采蜜峰确定食物源的位置并进行邻域搜索存储食物源信息；

②观察蜂根据采蜜蜂提供的信息以一定的概率选择食物源；

③侦查蜂在解空间区域不断搜索，试图发现新的食物源；

④保存到目前为止的最佳食物源信息。

(4)若满足某种约束条件则终止算法。

这里假定蜜蜂的数量与食物源的数量相等，记为N。

在初始化阶段，人工蜂群算法按照如下公式随机生成N个解决方案：

(1)

采蜜蜂会计算每种解决方案的适应度，然后每个蜜蜂在当前位置按式(2)进行邻域搜索产生新的解决方案：

(2)

适应度的计算公式是：

(3)

其中fiti是第i个位置的适应度。

观察蜂的任务主要是根据采蜜蜂提供的食物源相关信息，以一定的概率选择食物源。

食物源被选择的概率如下：

(4)

对于观察蜂来说，它们使用轮盘赌选择法挑选食物源。观察蜂选定食物源之后，开始并行执行任务。在其选定的蜜源附近进行邻域搜索，如果食物源的适应度一直没有提高，达到预先设定的循环次数Limit的食物源就会被放弃。放弃蜜源后的采蜜峰变成侦查蜂，开始在整个解空间中随机搜索新的解决方案，搜索到蜜源之后侦查蜂又转变成采蜜蜂执行任务。

最后，系统存储到目前为止适应度最佳的蜜源，然后重复搜索过程直至终止条件满足，比如到达预先设定的最大周期数，或者搜索结果偏差小于预先设定阈值等。

2 改进的蜂群算法与QoS组播路由选择

2.1 蜂群算法的改进

在上述基本人工蜂群算法的搜索机制中，适应度高的食物源附近会有大量的采蜜峰进行邻域搜索，而局部汇聚大量蜜蜂将导致其他区域的搜索能力下降，其结果会降低该算法的收敛速度和搜索效率。

如图1所示，假设x1是采蜜蜂的当前位置，而算法在执行搜索过程中，一个新的蜜源可能会在x1的邻域空间出现。如图中的x2是一个局部的最优值，但是算法在执行的过程中会在x1附近不断发现比x1优秀的解，从而吸引大量的采蜜蜂在临近区域搜索，这样算法会在局部最优位置的邻域空间来回摆动，容易陷入局部收敛。采蜜蜂的大量聚集必然会影响到x3、x4等优秀蜜源的发现效率，导致算法运行后期的收敛速度相对较慢。为了避免这种不利情况出现，引入“拥挤度”这一概念来限制采蜜蜂的数量：当拥挤度低时，蜂群不需要进行任何的调整，当拥挤度高时，适当减少采蜜蜂的数量，同时增加侦查蜂的数量来扩大对解空间的全局搜索，这样就能在一定程度上帮助算法避免早熟现象，同时在后期提高算法的收敛速度。

图1 一种假设的蜜源分布情况

定义crowd为拥挤度参数，表示解空间中采蜜蜂与其邻域空间中的其他个体之间的接近程度，crowd的值越大表示该区域内的采蜜蜂越少。

(5)

观察蜂选择食物源的概率相应修改为:

(6)

此外，原始人工蜂群算法初始化时蜜蜂的群体会被分为采蜜峰和观察蜂，观察蜂在蜂巢中被动等待采蜜峰带回的蜜源信息。本文的另一项改进是假设蜂群中侦查蜂一直存在，一般使其比例保持在蜂群总数的5%～10%，这样会迫使部分观察蜂转变为侦查蜂，以便继续保持对解空间的不断搜索。

2.2QoS组播路由问题

用赋权图G=(V, E)来模拟网络,其中V为图中所有网络节点组成的集合，E为网络中链路的集合。s∈V为源节点，d∈{V-{s}}为目的节点。对网络中的每个节点n∈V定义四种函数：代价函数Cost(n)，丢包率函数PL(n)，延时抖动函数Delay_Jitter(n)，时延函数Delay(n)。对每条链路e∈E也定义四种函数：代价函数Cost(e), 带宽函数BandWidth(e), 延时抖动函数Delay_jitter(e), 时延函数Delay(e)。

对于源节点s, 目的节点d, 每个QoS参数须满足以下约束：

(7)

(8)

(9)

BandWidth(p(s,d))=Min(BandWidth(e))

(10)

(11)

确定QoS路由算法的理想路径可以转化为在源节点s和目的节点d之间寻找一条满足以下条件的路径：

Delay(p(s,d))≤D

BandWidth(p(s,d))≥B

Delay_Jitter(p(s,d))≤DJ

PL(p(s,d))≤PL

Min(Cost(p(s,d)))

其中D为时延，B为带宽，DJ为延时抖动，PL为丢包率。

从源节点到目的节点得到的路径记为kpath，其适应度计算函数记为fitk，本文适应值采用越小越优的原则，fitk函数计算得到的不符合服务质量各约束条件的解记为劣质解，定义如下：

fitk=Cost(kpath)*ΦD(Delay(kpath)-D)*ΦDJ(Delay_Jitter(kpath)-D)*ΦPL(PL(kpath)-D)

(12)

(13)

(14)

(15)

其中RD，RDJ，RPL均为惩罚系数且大于1，本文算法中取2。fitk越小，对应解越优。

算法流程如下：

(1)初始化相关参数。设置蜂群数量N,最大搜索次数Limit,迭代次数iter, 最大迭代次数maxCycle,源节点s，目的节点d， 各边约束参数(C,B,DJ,D), 各顶点约束参数(C,PL,DJ,D)的值。

(2)使用Dijkstra第K条最短路径算法确定从源节点到目的节点的若干路径，构建非劣解集。

(3)采蜜蜂根据公式(2)，在非劣解集中进行邻域搜索，通过公式(10)计算适应度并根据贪婪策略保留更优的解。

(4)观察蜂根据公式(3)随机选择蜜源开采。

(5)若蜜源在Limit次数内没有得到改善，则采蜜蜂变为侦查蜂在解空间内进行全局搜索，否则返回第三步。

(6)算法执行至最大迭代次数或满足误差要求，输出最优路径并停止算法。

3 仿真实验与结果分析

本文采用MATLAB平台, 在Intel(R)PentiumE6500 2.93GHzCPU、2GB内存、Windows7 操作系统下进行了仿真实验。应用Salam随机生成算法生成网络拓扑如图2所示。

图2 网络拓扑图

仿真实验网络的相关参数选择如表1所示。

表1 网络相关参数

基本蜂群算法与改进蜂群算法的实验结果总结如表2和表3所示。实验结果表明，改进的人工蜂群算法在执行效率和收敛速度上明显优于基本型蜂群算法。

表2 基本蜂群算法实验数据

表3 改进的蜂群算法实验数据

4 结论

本文对基本人工蜂群算法引入了拥挤度概念加以改进。当采蜜蜂在进行邻域搜索时，拥挤度参数可以对采蜜蜂进行数量限制，避免过多的采蜜蜂在同一蜜源附近搜索，拥挤度高时增加侦查蜂的数量，从而有效提高了全局搜索能力并且加快了算法后期的收敛速度。通过应用改进的蜂群算法对网络QoS组播路由问题进行仿真实验，结果证明其在静态网络中性能表现优异，但是在动态网络实验中尚表现不佳。下一步将着力于解决动态网络优化问题。

[1]WangZheng,CROWCROFTJ.Quality-of-serviceforroutingsupportingmultimediaapplications[J].IEEEJournalofSelectedAreasinCommunications, 1996,14(7):1228-1234.

[2] 刘洋,王文国.差异化密集蚁群算法与网络QoS路由选择[J].通信技术,2015,48(8):949-953.

[3] 杨原.基于群智能优化算法的QoS组播路由算法研究[D].西安:西安科技大学,2014.

[4]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].TR06.KayseriErciyesUniversity, 2005.

[5]SAXENAS,SHARMAK,SHIWANIS,etal.Bestartificialbeecolonyusingstructuredswarm[C].Gurgaon:ProceedingsofIEEEInternationalAdvancedComputingConference,2014:1354-1360.

The research on the concept drifting based on three-way decision rough set

WuZongyue,FanLijuan,WangWenguo,

(DepartmentofInformationScience&Engineering,QufuNormalUniversity,Rizhao276826,China)

QoSmulticastroutingincomputernetworksisaNPcompleteproblem.Animprovedartificialbeecolony(ABC)algorithmwiththeconceptofcongestionwillbestudiedandusedtotackletheprobleminthispaper.Theproposedcongestionconceptisusedmainlyforemployedbees,andfunctionswhenmanyemployedbeessearchinginadjacentdomainstendtoaffecteachother;itwilladjustnumberofemployedbeesworkinginthesameareaandincreasethenumberofscouts,thereforeenhancesglobalsearchingabilityofthealgorithm.SimulationtestsonmulticastQoSroutingprocesswithstaticnetworktopologyshowthattheimprovedABCprocedureoutperformsthebasicalgorithminbothexecutionefficiencyandspeedofconvergence.

artificialbeecolonyalgorithm;QoS;Congestion;multicastrouting

TP

ADOI： 10.19358/j.issn.1674- 7720.2016.22.016

吴宗月，樊丽娟，王文国. 引入拥挤度概念的蜂群算法与网络组播路由研究[J].微型机与应用，2016,35(22)：61-64.

0 引言

国家人事部高层次留学人员回国工作资助项目(200461)

2016-07-28)

吴宗月(1990-)，男，硕士研究生，主要研究方向:计算机网络。

樊丽娟(1990-)，女，硕士研究生，主要研究方向:计算机网络。

王文国(1960-)，男，博士，教授，主要研究方向:网络与信息安全。