基于FFO算法的QoS组播路由服务性能优化研究

崔玉胜

(闽南理工学院信息管理学院，福建石狮 362700)

0 引言

在网络业务中，组播路由问题是组播服务过程中的核心问题,QoS组播路由问题与服务质量的好坏息息相关[1-2].QoS是一种网络安全的有效保障机制，用于提供高质量的网络服务.在远程教育、网络会议等多媒体服务背景下，网络传输包括海量的视频动画、图像图形等大量数据，尽管在数据准确性和完整性的要求不及文件传输高，但在传输时的时延抖动、时延以及网络带宽等网络性能方面有更高的要求[3].同时FFO算法相较于其他进化算法在求解QoS组播路由问题上具有独特的优势.综上分析，本次研究提出了一种改进后的FFO算法进行QoS组播路由服务性能优化，通过对FFO算法局部搜索和全局搜索进行优化，从而对组播路由的带宽和时延进行优化.

1 基于FFO算法及其改进的QoS组播路由模型

1.1 QoS组播路由服务性能

图1 组播通信的数据包传递模式Fig.1 The Packet transfer mode of multicast communication

近年来，组播技术已经在诸多行业得到了广泛应用，随之而来的组播路由问题成为了学术界专家和学者的热烈关注的话题.相较于单播路由，组播路由具有确定的组播路由路径作为问题求解目标，其求解的核心是尽最大可能提高共用链路数量，降低组播数的总开销[4-5].不同之处在于组播路由在合成组播树时不能单纯使用多条点对点最短路径，尤其在多个QoS约束问题中，求解过程将会变得越来越复杂.组播通信能够有效避免单播通信在需要与多目标设备进行通信时出现的网络资源耗费过大的问题，数据包传递模式如图1所示.它是通过一个数据发送端口一次性地把同样的数据输送至到多个数据接收端，接收端口没有数量的要求，且同样的数据包在网络的一条链路中仅需拷贝一次[6].因此，在满足多目标需求的同时，也极大地减少了资源耗费和网络带宽，提升了数据在网络传输的效率.

如果出现网络拥堵或者过载的情况，QoS将会通过可度量的参数约束来保证网络服务质量[7-8].参数包括开销、时延、时延抖动、带宽、丢包率四种.QoS约束是在求解过程中，要求组播路由的时延等于或低于最高阈值、时延抖动等于或低于最高阈值、带宽等于或高于最低带宽阈值、丢包率等于或低于最高阈值[9-10].一般情况下，包括一种或多种可度量约束条件，此次研究讨论时延和带宽两个约束条件.目前最常使用的求解QoS组播路由问题的方法包括遗传算法(GA)、蚁群算法(ACO)、粒子群优化算法(PSO).

1.2 基于FFO算法及改进的组播路由数学模型

FFO算法是一种新型的进化算法，通过模拟果蝇在寻觅食物过程中的随机嗅觉搜索以及视觉定位行为而提出的.它是目前计算公式最简单、参数使用最少的进化算法，在神经网络和函数等领域已经取得了突出的成绩[11].其主要特点表现在以下三个方面.其一，该算法的步骤仅需要随机嗅觉搜索以及视觉两个步骤，具有实现简便、参数少、容易调节等特点.而遗传算法具有选择、交叉、变异等环节，蚁群算法有更新局部信息和全局信息、概率选路、等阶段；其二，该算法具有较高的收敛性，果蝇灵敏的随机嗅觉搜索行为和视觉定位行为分别导致算法的局部搜索能力全局和局部搜索能力强；其三，该算法非常适用于求解QoS组播路由问题，果蝇在现实空间中寻找事物的过程与QoS组播路由问题中寻找解空间一一对应[12].该算法局部搜索为随机嗅觉搜索和经过个体之间的信息交换，全局搜索通过个体之间的信息交换实现全局最优果蝇的视觉定位，并不断迭代更新最优果蝇的位置，直至完成最大迭代次数和满足目标精度[13].针对FFO算法在求解组播路由问题中存在的不足，尤其是在处理高维度的情况时的问题，本研究提出了一种改进后的FFO算法，即概率视觉定位果蝇优化算法(PVFFO).该算法的特性主要体现在以下三个方面.首先通过果蝇味道浓度判定函数寻找最优解，假定果蝇当前位置的组播树是Tf，f表示果蝇，位置表示为Lf，cost(e)表示链路的开销，e表示链路，则该果蝇味道浓度判定的函数为：

(1)

其次是随机嗅觉搜索的方案，拓扑结构的链路数量为K，链路的编号id表示0到K-1，假定果蝇在随机搜索以前的位置和随机搜索之后的位置分别为Lf=[lf,0,lf,1...lf,K-1]和，Lf'=[lf,0',lf,1'...lf,K-1'].在链路的编号随机选取κ个整数，整数集合表示为Z={z1,z2,..zκ}，位置更新公式表示为

(2)

其中随机嗅觉搜索步长参数为κ，取值在[0,K]之间，i∈{0,1,...,K-1}.该方案通过果蝇在空间维度中的位置取值进行0-1的取反操作实现随机嗅觉搜索.最后是概率视觉方案，在进化算法的迭代过程中，当代最优解是进行优化的重要环节，假定具有当代最高味道浓度值的果蝇为fb,n，迭代次数为n，某果蝇f视觉定位之前的位置表示为Lf=[lf,0,lf,1,...lf,K-1]，最优果蝇的位置表示为Ln=[ln,0,ln,1,...ln,K-1]，概率表示为：

(3)

图2 PVFFO算法流程图Fig.2 PVFFO algorithm flow chart

概率序列表示为[p0,p1...,pK-1],ψ为概率视觉定位灵敏度，取值大于0，rand()表示实数区间(0,1)的随机数.此方案以最优果蝇的位置为标准，当果蝇和最优位置不再同一个维度时，果蝇会以非常高的概率与最优位置的维度保持一致，从而起到比较好的视觉定位的效果[14-15].该算法的具体实现步骤为图3所示.其一获得组播服务请求的源节点、时延约束条件的阈值、网络拓扑信息、目的节点序列、带宽约束条件的阈值；其二，对最大迭代次数MAXGEN、果蝇的群体规模M，果蝇群体F={f1,f2,...,fM}进行初始化，初始化概率视觉定位灵敏度参数和初始状态的随机嗅觉搜索步长参数，初始化历史最优果蝇，0为历史最优果蝇的味道浓度值，迭代次数为0；其三，结合随机嗅觉搜索步长参数进行当代全部果蝇的嗅觉搜索；其四，使用味道浓度判定函数进行当代果蝇的味道浓度值计算；其五，找出当代果蝇中的最优个体和位置，并与历史最优浓度值进行比较，如果当代最优个体的味道浓度最大值相较于历史最优个体的味道浓度最大值，则历史最优个体的味道浓度值和位置被当代最优个体对应的浓度值和位置所取代；其六，结合概率视觉定位灵敏度参数进行当代全部果蝇概率视觉定位；其七，如果迭代次数小于最大迭代次数，继续进行第三步的操作，否则对最优果蝇个体的组播树进行输出，停止迭代.

PVFFO算法具有概率视觉定位灵敏度参数ψ和随机嗅觉搜索步长参数κ两个参数.前者主要用于限制局部搜索范围，后者主要对普通果蝇与当代最优果蝇之间距离进行控制[16].两种不同参数对组播树开销的影响统计如图4所示.两个参数的取值变化对求解的质量有非常显著的影响.因此，此次研究概率视觉定位灵敏度参数ψ和随机嗅觉搜索步长参数κ分别取3.6和6.

图3 4两种不同参数对组播树开销的影响统计Fig.3 Statistics of the tree cost impact of two different parameters on multicast tree

组播请求场景主要由网络拓扑、目的节点集、若干约束条件、组播源节点共同组成[17-18].其中节点个数、各链路属性、节点个数等信息构成了网络拓扑.研究通过MATLAB软件生成自定义拓扑，由于篇幅有限，仅展示6种组播场景的部分信息，如表2所示,组播树的带宽约束阈值和时延约束阈值分别为100 Mb/s和300 ms.

表1 6种组播场景的信息统计Tab.1 Information statistics of 6 multicast scenarios

2 仿真实验对比

此次研究在组播路由问题中求解带宽和时延等QoS约束条件分别进行8种场景的仿真实验，并采用新提出的PVFFO、FFO、GA、PSO、量子进化算法(QEA)、随机蛙跳算法(SFLA)、矢量引导蚁群优化算法(VGACO)等7种进化算法进行对比分析.为了保证实验结果的公平性，真实反映算法的性能优劣，实验假定6种场景中每种算法运行20次，所得到数据采用平均值，每种算法的子群规模为迭代次数都设置为100次，子群的数量均为20，每一代均有20个空间解.

实验引入t检验进行统计和分析，检测两组组播树开销，组播树的开销在均值的上下进行波动，满足正态分布规律.两组组播树的开销存在明显的区别，符号+表示前一组算法开销相对较小，求解算法的性能更佳，符号-表示后一组算法开销相对较小，求解算法的解的质量更佳.两组组播树的开销没有明显的区别，用～表示，两组算法的解质量一致.PVFFO算法和其他六种进化算法的t检测统计如表2所示.可以看出，PVOFF算法相较于其他六种算法，除在VGACO算法的个别场景之外，求解的质量均明显优于其他算法.

图4 7种算法在6种不同场景的收敛统计结果Fig.4 Statistical results of convergence of 7 algorithms in 6 different scenarios

收敛统计是指历史平均最优开销和迭代代数的次数关系的曲线.6种不同场景中7种算法收敛统计结果分别如下图4(a)、4(b)、4(c)、4(d)、4(e)、4(f)所示.依据收敛结果可以看出，7种进化算法在迭代次数为100时，平均历史组播树的开销值都趋向稳定.除了在场景6中，VGACO算法收敛在更高质量的解，其余5种场景中PVFFO算法均比其他算法收敛在更高质量的解.同时，在迭代进行到30代左右时，PVFFO算法仍然持续寻找高质量的解，而其他6种进化算法已经进行收敛最优解，且迭代次数的增加，PVFFO算法能够找到高质量的解.如图4(f)所示，PVFFO算法在迭代次数为80代时收敛至最优解，相应的组播开销为145.GA、FFO、PSO、SFLA、VGAFFO五种算法在迭代次数为30时均收敛达到最优解，再此后迭代过程中不需再寻找最优解.GEA算法在迭代次数为100时还未收敛至最优解.这表明该算法由于概率视觉定位方案的引入，具有非常高的全局搜索能力.

图5 7种算法在6种场景中的平均运行 时间和标准差统计Fig.5 Average running time and standard deviation statistics of the 7 algorithms in 6 scenarios

7种算法在6种场景中的20次运行的平均运行时间和标准差为下图5所示,结合图5可以看出，针对平均运行时间，在6种不同的场景中，和其他六种算法相比，PVFFO算法的平均的运行时间相差不多.而VGACO算法的运行时间最长.平均运行时间最短的算法是遗传算法，大约是PVFFO算法平均运行时间的一半，但是相差最大仅在1s左右，如果通过更高性能的机器进行检验，两种算法的运行时间的差异将会变小.在场景6中，VGAFFO算法的运行时间最长约为14 s，而其余六种算法的的运行时间均在2 s左右.同时相较于遗传算法，PVFFO算法收敛速度相对更快，且解的质量更高.标准差结果表明，PVFFO算法的标准差明显小于其他算法，综合分析，PVFFO算法实用性和稳定性更强.

图6 7种算法在6种场景的Box-plot统计结果Fig.6 Box-plot statistical results of 7 algorithms in 6 scenarios

本研究为了更直观反应不同算法的分布情况，采用箱线图进行观察.7种算法在六种不同场景的开销的箱线图分别如图6(a)、6(b)、6(c)、6(d)、6(e)、6(f)所示，简写成Box-plot统计.从图中可以看出，PVFFO算法在大多数的场景中的非异常数据区域和数据箱方块相对较小，该算法的数据非常集中.从图6(f)可以看出，PVFFO算法在该场景中产生异常数据最少且数据较为集中，但相较于其他六种算法，PVFFO算法具有明显的优势.中位数由高到低的排序依次为GA、PSO、FFO、QEA、SFLA、VGACO、PVFFO.PVFFO算法在个别场景中的异常数据较多，这也是因为数据过于集中，但与正常数据相比，其数量较小.

3 结论

组播业务被大量应用于网络服务并给消费者给来诸多的益处，如何计算QoS组播路由问题中最优解是当今相关专家和学者挑战性的话题.此次研究在分析QoS组播路由的服务性能和FFO算法的前提下，提出了一种基于FFO算法的QoS组播路由性能优化模型，通过随机嗅觉搜索和概率视觉灵敏性定位两种方案型优化.实验通过对比7种进化算法在六种不同场景中的收敛速度和运行时间以及求解质量，得出了PVFFO算法的有效性和准确性.相较于FFO、GA、PSO、QEA、SFLA、VGACO,PVFFO算法具有非常高的全局搜索能力，具有极高的收敛于最优解的能力，且最优解的质量明显由于其他进化算法.除VGACO算法在少数场景中优于PCFFO算法.此次研究在场景的选择上不具有广泛性，这是下一步研究的方向.