基于NFV的QoS多源多播蚁群优化算法

黄闻天，孙士民,2，张新潮，徐爱鑫，汪晓凡

（1.天津工业大学计算机科学与技术学院，天津 300387；2.天津市自主智能技术与系统重点实验室，天津 300387）

0 引言

多源多播网络即是通过一组源节点向一组目的地传送相同内容的一种通信方式。同时，随着网络功能虚拟化（NFV）的快速发展与应用，大量的虚拟网络功能节点（VNF）分布在多播网络中，为网络应用提供不同层级的多样化服务。因此，多源多播网络与网络功能虚拟化（NFV）的结合迎来了全新的挑战。NFV网络要求在网络信号传输到目的节点前需要按顺序遍历一些布置了虚拟网络功能（VNF）的节点，通过这些节点上分布的网络功能的按顺序结合完成指定的网络功能［1］。因为其将部分运算功能分布在网络节点上，所以NFV网络的QoS需求也越来越丰富。而QoS路由算法也能够合理分配网络吞吐量、优化网络资源配置，结合所布置功能实现网络全局资源利用率优化［2］，这使得对构建含QoS的支持网络功能虚拟化多源多播优化网络的研究成了当务之急。

本文将虚拟源节点算法与蚁群算法相结合，提出了一种基于蚁群优化的QoS多源多播路由算法Ant based Multi-Source Multicast Tree Construction（AQoSMMTC），可以有效地构建多源多播网络并对其进行优化。而针对其与NFV相结合的问题，本文提出一种基于VNF节点选择的改进的蚁群算法VNF based Multi-Source Multicast Tree Construction（VQoSMMTC）来对多源组播树进行求解，在追求路径代价优化的同时对VNF节点位置进行了选择。

1 算法思路

1.1 蚁群优化算法

蚁群算法［3］是意大利学者M.Dorigo等人提出来的，通过模拟自然界蚂蚁群觅食寻径来求解相似寻优问题。主要内容为蚂蚁在觅食和返巢的过程中拥有选择最短路径的能力，其能力来源于蚂蚁会在行走的路径上留下自己的信息素（pheromone）。信息素会随着时间挥发，其他蚂蚁对路径上的信息素进行识别，并在行动时按照信息素浓度随机选择路线。路线选择的概率与其信息素浓度成正比。较短的路线往返时间更短，往返次数更多，从而拥有较强的信息素浓度。会对觅食路径选择形成一种正反馈并通过这种方式挑选最佳路径［4］。

1.2 通过蚁群优化算法解决含Qo S的多源多播问题

多源多播问题是指对给定的一组目的地和一组源构建网络拓扑。与单源多播的最小生成树相比，多源多播问题是旨在构造一个最小成本的森林（MCF）［5］，即众多最小生成树的集合，它确保每个目的节点通过林中的一条路径只连接到一个源。这是一个NP完全问题［6］。

在多源多播网络中，可以通过蚁群算法与虚拟源节点法［7］相结合来解决多源多播问题。首先构建一个虚拟源节点，使得其对所有源节点的距离为0，所有蚂蚁都从此虚拟源节点释放，所有蚂蚁也都对此虚拟源节点返回，将源节点视为普通中继节点。此方法的多播目标树即可视为从虚拟源节点开始的单源多播最小斯坦纳树。其次待循环完成后将虚拟源节点摘除，留下源集合中被使用的节点就是蚁群优化后的多源多播树。在蚁群算法寻找多播树的过程中，对蚂蚁的每一次寻路都进行一次QoS判定，自动避开不满足要求的路径选择即可完成满足QoS需求的多播树的构建，如图1所示。

图1 通过添加虚拟源的蚁群算法解决多源多播问题

1.3 基于改进蚁群算法的支持NFV多源多播路由算法（VQo SMMTC）

改进的蚁群系统算法在对信息素的设置上增加了正向信息素和反向信息素。在蚂蚁进行正向搜索时遵循正向信息素，每当到达所有目标节点后再从目标节点释放蚂蚁根据反向信息素进行反向搜索直到回到虚拟源节点（反向信息素初始值与第一次正向信息素相同）。当蚂蚁完成一次搜索循环后，检查是否发现当前最佳树（目标节点到虚拟源节点距离最短），若发现则对反向信息素进行全局更新，之后继续进行循环直到到达终止条件。

在支持NFV的多源多播树的构建中，由于每一组流量的传输都需要按顺序经过一些特定的VNF节点。改进的蚁群算法在反向循环的过程中添加了VNF节点的寻找功能。在反向寻路的过程中按顺序寻找VNF节点的布置位置，每寻找一个VNF功能节点则对下一步能到达的节点进行该VNF功能布置代价计算，将布置代价计入链路代价中，从而对传输代价和布置代价一同进行优化。使得每一个目的节点都有完整的VNF传输链（SFC）［8］，并且获得基于总代价最小的优化树，算法示意如图2所示。

图2 基于NFV的改进蚁群算法多源多播树

2 算法实现

2.1 基于蚁群优化的Qo S多源多播路由算法（AQo SMMTC）

2.1.1 蚁群算法蚂蚁转移规则伪代码

算法1蚂蚁转移规则

需求:无向图G=（V,E）,信息素表（Phero-mone list）,开始节点N,禁忌表,q0，邻居节点集合（P（neighber））

将禁忌表中节点从信息素表中删除

q=rand（0,1）

if q≤q0

Target=arg max（P（neighber））

else

for neighber∈Phero-mone list

P（N,neighber）=P（neighber）/SUM（P）

if

（P（N,neighber）>R）

Target=min（neighber）

end if

end for

end if

将N加入禁忌表

Next skip=Target

start node=Next skip

输出:Next skip

End

2.1.2 基于蚁群算法的多源多播树构建伪代码

算法2基于蚁群算法的多源多播树构建

需求:无向图G=（V,E）,信息素表,禁忌表,t目标节点集合{D},源节点集合{S},蚂蚁数量M,循环次数It.

将S0加入图G,Distance（S0,{S}）=0

for i=0:It

m=0

for Di∈{D}

for m≤M以出发节点为S0执行算法1

if Target=Di

Record［path（Di）,cost（Di）］

为path（Di）进行局部信息素更新

else back to do

end if

end for

Best_path（Di）=arg min（cost（Di））

end for

tree={path（Di）},record cost（tree）

Best_tree=arg min（cost（tree））

对Best_tree进行全局信息素更新

更新信息素表

end for

输出:Best_tree

End

2.2 基于改进蚁群算法的支持NFV多源多播路由算法（VQo SMMTC）

2.2.1 改进的蚁群算法蚂蚁转移规则伪代码

算法3改进的蚁群算法转移规则

需求:无向图G=（V,E）,信息素概率表,出发点N,禁忌表,q0，当前需要布置的VNF功能VNFnode（n），QoS标准

Start：将禁忌表中节点从信息素概率表中删除

q=rand（0,1）

if q≤q0

Target=arg max（P（neighber））

else

for neighber∈Phero-mone list

P（N,neighber）=P（neighber）/SUM（P）

if（P（N,neighber）>R）

Target=min（neighber）

end if

end for

end if

If Target符合QoS标准且未被部署其他VNF功能

将N加入禁忌表

Next skip=Target

VNFnode（n）=Target

n-1

start node=Next skip

Else

将Target加入禁忌表

start node=N

重新开始循环

输出:Next skip

End

2.2.2 基于改进的蚁群算法的多源多播树构建伪代码

算法4基于NFV的改进蚁群算法多源多播树构建方法

需求:无向图G=（V,E）,正向信息素表，反向信息素表，禁忌表,目标节点集合{D},源节点集{S},蚂蚁数量M,最大循环次数It.

将S0添加入图G中,Distance（S0,{S}）=0

for i=0:It

m=0

for m≤M从S0开始根据算法1进行循环

if Target=Di

记录［path（Di,Cost（Di）］

对path（Di）进行局部信息素更新

else back to do

end if

end for

for m≤M=从{Di}开始根据反向信息素表及算法3进行循环

if Target=S0

记录［path（Di）,Cost（Di）］

对path（Di）进行局部信息素更新

else back to do

end if

end for

Best_path（Di）=arg min（Cost（Di））

tree={path（Di）}］

end for

计算树的代价Cost（tree）

Best_tree=arg min（Cost（tree））

进行全局信息素更新

更新反向信息素概率表

end for

输出:最佳树，VNF节点位置

end

3 实验与仿真

本实验采用Matlab仿真工具对AQoSMMTC算法与VQoSMMTC进行模拟仿真，并且测试性能与分析数据与MMForest路由算法［9］、MCF路由算法［5］进行实验对比。由于上述算法采用的机制、原理各不相同，为确保实验的准确性、完整性，将仿真实验设置为采用同一传统树形网络拓扑结构、相同的节点链路参数，网络节点分布范围为10000×10000，节点数量为100个，邻居节点距离为200，所有实验所用节点均从此100个节点中挑选。

对QoS约束条件设定为带宽（bandwidth）=100，时延（delay）=80 ms，丢包率（packet_loss_rate）=0.05。在试验前对网络中所有邻居节点间链路QoS属性使用伪随机算法进行设置，确保不满足要求链路出现概率小于等于1%。

3.1 不同网络规模下构建的多源多播树总代价

本次实验对不同网络规模下多源多播树的总代价进行对比，设置源数量为5，网络规模即节点数由23到73。

实验结果如图3所示，AQoSMMCT算法专注于最优树的寻找，所以其结果优于其他对比算法。而VQoSMMCT算法则在构建多播树的同时对VNF节点进行寻找，故其总代价略大于AQoSMMCT算法与MMForest算法基本持平。

图3 不同网络规模下多播树的代价

3.2 给定最优树下算法成功率

根据先前网络规则构建一个简单VNF功能网络，并添加干扰节点构建一个网络规模为20的测试网络，该网络的最佳多播树如图4所示。

图4 已标出最佳多播树的测试网络

使用结合RMTC［9］的MMForest算法［6］和VQoSMMTC算法对该网络求解。对比所得到的结果是否于最佳多播树相等，从而确定算法的成功与否。本次实验采取不同的最大迭代次数进行对比，每一组进行100次独立实验，成功得到最佳多播树的次数即为算法的成功率，如图5所示。

图5 不同迭代次数下算法的成功率

从实验结果不难看出，VQoSMMTC算法的成功率明显优于结合RMTC的MMForest算法，随着最大迭代次数的增加，算法的成功率趋于稳定。

4 结语

本文基于蚁群算法和虚拟源节点算法提出了基于蚁群优化的QoS多源多播路由算法。为了解决传统的多播路由算法与NFV边缘计算等网络功能部署方法相结合的问题，提出了支持NFV的QoS多源多播路由算法。实验结果表明，在含QoS的多源多播树的构建上本文提出的两种多源多播算法均可成功构建符合QoS需求的多源多播树，并且树的总代价优于许多已有的多源多播树构建算法。并且在对VNF节点布置的计算上能结合节点功能与网络状况构建多源多播树。