论文部分内容阅读
摘 要 为了求解多约束下最小代价组播路由问题，提出基于链路编码的差分进化组播路由算法，为了加快收敛速度，算法引入一种新的变异策略。仿真实验结果表明该算法与其他算法相比具有相对较好的性能。
关键词 Qos；组播路由；差分进化算法；链路编码；变异策略
中图分类号：TN911 文献标识码：A 文章编号：1671-7597（2013）20-0054-02
近年来，随着高速通信网络的发展，多媒体会议、视频点播、多人游戏等多媒体业务被越来越广泛的应用。组播技术是基于这种点对多点通信的最有效的传输技术，能够提供满足服务质量（Qos）的组播传输技术成为当前研究的热点。组播路由是其中的关键技术，在数学上可归结为Steiner tree问题，1992年，Kompella就已证明具有两个或多个不相关加性约束的Qos组播路由是NP-Complete问题。国内外的学者提出了很多有效的算法求解Qos组播路由问题。
文献[1]-[3]采用了智能算法中应用最广的遗传算法，但文献[1]使用n×n的一位二进制编码方式，这种编码增加了算法复杂度，运行效率低；文献[2]采用Prufer编码机制，仍然有很多局限性；文献[3]采用树编码方式，可以避免编码空间与解空间的转换，但是比较死板。文献[4]采用差分进化算法，提出了一种新的编码方式，即路径编码，其交叉、变异以路径为基础进行，个体变化范围小，难以扩展多样性。文献[5]-[6]采用蚁群算法，直接在网络路径上搜索，无需编码，有很大的优势，但蚁群算法初始时信息量小，收敛速度慢，后期又容易陷入早熟收敛，难以寻到最优解。另外还有其他的文献采用克隆选择算法、人工鱼群算法、微粒群算法、禁忌搜索等智能算法。
本文采用差分进化算法求解Qos组播路由问题。差分进化（Differential Evolution，DE）算法是Ken Price和Rainer Storn于1995年提出的一種基于群体的随机搜索算法，它的主要原理与遗传算法相似，进化流程为变异、交叉、选择，变异操作与遗传算法不同，不是基于随机点的变异，而是基于个体间的差异进行变异，这样能有效利用群体的分布特性，提高个体的多样性，在全局范围内进行搜索；交叉操作也是在两个个体间进行交叉，交叉个体根据概率因子选择某个个体的分量作为自己的分量；选择操作采用的是贪婪策略，即对变异交叉后的个体与原个体比较，选择适应度大的作为新个体进入到下一代。差分进化算法因其操作简单、收敛速度快、使用参数少、鲁棒性强，受到越来越多的学者的关注。鉴于以上提到的诸多优良特性，针对Qos组播路由问题，本文提出了差分进化组播路由算法，算法采用基于链路的编码方式，更适应Qos网络的特点，另外，在变异操作中，提出了一种基于k-最优个体的变异方式。算法实现简单、收敛速度快、全局收敛。
1 Qos组播路由问题
Qos组播路由的目的就是在网络中建立组播树，要求从源结点出发，遍历所有的目的结点，满足包括时延、时延抖动、带宽、丢包率等服务质量要求，达到花费最小或达到特定的服务水平。在研究组播路由时，为了方便，一般把通信网络抽象为一个无向加权的连通图。
网络模型用加权图表示，其中是结点集合，是结点之间的双向链路集合，如图1所示。
对于任一结点，可以定义其上的四种Qos度量参数：时延函数、时延抖动函数、包丢失率函数、代价函数；对于中的任意链路，也有四种Qos度量参数：时延函数、时延抖动函数、带宽函数、代价函数。
假设数据是由源结点传送到一组目的结点集，。定义一棵包含源结点与目的结点的组播树，其中，，并且，在组播树中存在源结点到任一目的结点（）的路径。则在组播树T上有如下关系：
1）+
2）+
3）
4）
5）+
Qos组播路由核心问题就是构造一棵包含源结点与所有目的结点的组播树，要求满足以上各种参数约束，并且费用最小。即：
2 差分进化组播路由算法设计
2.1 个体编码
对整个网络进行精简，去掉不满足带宽约束的边，得到。假设有个结点，在网络中随机构造一棵包含所有结点的生成树，生成树的链路集合作为差分进化的个体，，其中为个体的一个分量，，。生成树的构造方法如下：
1）初始时将源节点加入生成树。
2）随机选择一条链路（其中在当前生成树中，不在当前生成树中）加入，并将也加入。
3）重复执行2）步，直到所有的节点都加入到生成树为止。
2.2 适应度函数的计算
在计算个体适应度前先对生成树进行剪枝操作：
1）遍历生成树的所有叶子结点，若其不是目的节点，则从生成树中删除，并删除与之有关的链路。
2）重复执行，直到所有的叶子节点都是目的节点为止。
剪枝完成后得到组播树，计算组播树的适应度值使用如下函数：
其中，
A、B、C分别为时延、时延抖动和丢包率在适应度函数中的权重系数，其值可以根据具体的应用来设定，在本文的仿真实验中，取值都为1。、、为对不满足约束的路径设定的惩罚系数，在本文的仿真实验中取值为0.5。
2.3 变异操作
变异操作中，选取三个个体向量根据如下公式进行变异，得到变异个体：
其中F为缩放因子，代表变异程度，取值范围为[0，1]。
常用的变异模式有两种：在DE/rand/1/bin模式中，用随机个体（）作为基准向量进行变异，这种方式探索能力强，但收敛速度慢；在DE/best/1/bin模式中，用本代最优个体做为基准向量进行变异，这种方式收敛速度快，但容易陷入局部最优。本文采用上述两种模式的一种居中模式DE/rand-k-best/1，用随机选取的k个个体中的最优个体作为基准向量，既能保持个体的多样性，又能拥有一定的收敛速度。多次实验表明，k在[3，0.3*NP]范围内取值效果最好。 2.4 杂交操作
变异个体和种群的目标个体根据以下公式进行杂交，产生杂交个体：
为了保证个体的进化，杂交个体至少有一个分量由变异个体提供，其他分量根据杂交概率因子CR决定具体哪位由或提供。其中rnds为随机产生的0～1之间的实数，CR是0～1之间的常数，ns是随机产生的维数索引号，其保证了至少有一位分量由变异个体提供。
本算法中具体实现方式为：首先根据随机索引号从变异个体生成树选取一条边，然后根据CR从变异个体生成树或目标个体生成树中逐次选取剩余的边，选取原则为：边的起始节点已在生成树中，而终止节点尚未在生成树中。
2.5 选择操作
选择操作采用的是贪婪策略，经变异及杂交后产生的个体与目标个体进行竞争：
f为适应度函数。
3 仿真实验与分析
实验采用广泛使用的8节点网络模型进行仿真，如图1所示。源节点s=1，目的节点集D={2，4，5，7}。图中每个顶点用四元组（d，dj，l，c）表示，其中的元素分别代表时延、时延抖动、丢包率和费用代价；每条边用四元组（d，dj，b，c）表示，b代表带宽，其他同上。
图 1 8节点网络拓扑图
实验中，种群规模设定为10，最大迭代次数为100。变异算子F=0.5、交叉算子CR=0.5，Qos参数约束量定为：时延约束DE=48、时延抖动约束DJ=8、带宽约束B=70、丢包率约束L=0.001。
本文实验在配置为Pentium Dual Core E6500和4G内存的微机下运行，采用的编程语言为VC++6.0，根据多次试验结果，获得的最佳组播树为。该组播树的最大时延delay=47，最大时延抖动delay_jitter=5，最大丢包率loss=0.0002101，总费用为43。
为了验证算法的性能，将本文算法与文献[1]提出的遗传算法、文献[4]提出的基本差分进化算法在同等的实验环境下进行了对比，得到的结果如图2、图3所示。
图2 3种算法的收敛性比较
图3 3种算法的运行时间比较
图2为3种算法在8节点网络图运行时收敛性的比较，可以看出，随着代数增加，本文算法以较快的速度收敛到最优解；图3为3种算法在随机生成的不同网络节点数的网络运行时间的比较，为了观察算法的整体性能，固定解的大小，使算法结果达到基本最优解时停下来，然后比较运行时间，可以看出，随着节点数的增多，本算法的运行时间并没有大幅度的增加，从而说明本算法效率较优。
4 结束语
本文对Qos组播路由模型和差分进化算法进行研究，提出了一种差分进化组播路由算法。算法采用了一种链路编码的方式，具有n个节点的生成树有n-1条链路，进化种群以生成树为个体，链路是组成个体的基本单元。同时在变异操作中，引入了一种DE/rand-k-best模式，将随机选择的k个个体中的最优个体作为基准向量，引导变异方向。仿真实验表明，本文算法具有较好的收敛性和效率。下一步的工作是研究参数的改变对算法的影响。
基金项目
国家自然科学基金项目（项目编号：40772196），河北省教育厅自然科学项目（项目编号：Z2012092）。
参考文献
[1]XIANG Fei，LUO Junzhou ， WU Jieyi ， et al.QoS routing based on genetic algorithm[J].Computer Communications ，1999，22 （15-16） ：1392-1399.
[2]刘莹，刘三阳.多媒体通信中带度约束的多播路由算法[J].计算机学报，2001，24（4）：62-65.
[3]王新红，王光兴.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报，2002，3（3）：112-117.
[4]孔笋，陈增强.基于差分进化的Qos组播路由算法[J].Proceeding of 29th China Control Conference July 29-31，2010，Beijing：5232-5237.
[5]HUANG Lin，HAN Haishan，HOU Jian.Multicast routing based on the ant system[J].Applied Mathematical Science，2007，1（57）：2827-2838.
[6]孙力娟，王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解[J].电子学报，2006，34（8）：1391-1395.
[7]STORN R，PRICE K.Differential evolution：a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11（4）：341-359.
[8]王力军，田静，李健.基于正交实验及双种蚁群的QoS组播路由算法[J].计算机系统应用，2011，20（6）：73-76.
作者簡介
李晰（1977-），女，河北深州人，讲师，硕士，研究方向：理论计算机科学，智能算法。
关键词 Qos；组播路由；差分进化算法；链路编码；变异策略
中图分类号：TN911 文献标识码：A 文章编号：1671-7597（2013）20-0054-02
近年来，随着高速通信网络的发展，多媒体会议、视频点播、多人游戏等多媒体业务被越来越广泛的应用。组播技术是基于这种点对多点通信的最有效的传输技术，能够提供满足服务质量（Qos）的组播传输技术成为当前研究的热点。组播路由是其中的关键技术，在数学上可归结为Steiner tree问题，1992年，Kompella就已证明具有两个或多个不相关加性约束的Qos组播路由是NP-Complete问题。国内外的学者提出了很多有效的算法求解Qos组播路由问题。
文献[1]-[3]采用了智能算法中应用最广的遗传算法，但文献[1]使用n×n的一位二进制编码方式，这种编码增加了算法复杂度，运行效率低；文献[2]采用Prufer编码机制，仍然有很多局限性；文献[3]采用树编码方式，可以避免编码空间与解空间的转换，但是比较死板。文献[4]采用差分进化算法，提出了一种新的编码方式，即路径编码，其交叉、变异以路径为基础进行，个体变化范围小，难以扩展多样性。文献[5]-[6]采用蚁群算法，直接在网络路径上搜索，无需编码，有很大的优势，但蚁群算法初始时信息量小，收敛速度慢，后期又容易陷入早熟收敛，难以寻到最优解。另外还有其他的文献采用克隆选择算法、人工鱼群算法、微粒群算法、禁忌搜索等智能算法。
本文采用差分进化算法求解Qos组播路由问题。差分进化（Differential Evolution，DE）算法是Ken Price和Rainer Storn于1995年提出的一種基于群体的随机搜索算法，它的主要原理与遗传算法相似，进化流程为变异、交叉、选择，变异操作与遗传算法不同，不是基于随机点的变异，而是基于个体间的差异进行变异，这样能有效利用群体的分布特性，提高个体的多样性，在全局范围内进行搜索；交叉操作也是在两个个体间进行交叉，交叉个体根据概率因子选择某个个体的分量作为自己的分量；选择操作采用的是贪婪策略，即对变异交叉后的个体与原个体比较，选择适应度大的作为新个体进入到下一代。差分进化算法因其操作简单、收敛速度快、使用参数少、鲁棒性强，受到越来越多的学者的关注。鉴于以上提到的诸多优良特性，针对Qos组播路由问题，本文提出了差分进化组播路由算法，算法采用基于链路的编码方式，更适应Qos网络的特点，另外，在变异操作中，提出了一种基于k-最优个体的变异方式。算法实现简单、收敛速度快、全局收敛。
1 Qos组播路由问题
Qos组播路由的目的就是在网络中建立组播树，要求从源结点出发，遍历所有的目的结点，满足包括时延、时延抖动、带宽、丢包率等服务质量要求，达到花费最小或达到特定的服务水平。在研究组播路由时，为了方便，一般把通信网络抽象为一个无向加权的连通图。
网络模型用加权图表示，其中是结点集合，是结点之间的双向链路集合，如图1所示。
对于任一结点，可以定义其上的四种Qos度量参数：时延函数、时延抖动函数、包丢失率函数、代价函数；对于中的任意链路，也有四种Qos度量参数：时延函数、时延抖动函数、带宽函数、代价函数。
假设数据是由源结点传送到一组目的结点集，。定义一棵包含源结点与目的结点的组播树，其中，，并且，在组播树中存在源结点到任一目的结点（）的路径。则在组播树T上有如下关系：
1）+
2）+
3）
4）
5）+
Qos组播路由核心问题就是构造一棵包含源结点与所有目的结点的组播树，要求满足以上各种参数约束，并且费用最小。即：
2 差分进化组播路由算法设计
2.1 个体编码
对整个网络进行精简，去掉不满足带宽约束的边，得到。假设有个结点，在网络中随机构造一棵包含所有结点的生成树，生成树的链路集合作为差分进化的个体，，其中为个体的一个分量，，。生成树的构造方法如下：
1）初始时将源节点加入生成树。
2）随机选择一条链路（其中在当前生成树中，不在当前生成树中）加入，并将也加入。
3）重复执行2）步，直到所有的节点都加入到生成树为止。
2.2 适应度函数的计算
在计算个体适应度前先对生成树进行剪枝操作：
1）遍历生成树的所有叶子结点，若其不是目的节点，则从生成树中删除，并删除与之有关的链路。
2）重复执行，直到所有的叶子节点都是目的节点为止。
剪枝完成后得到组播树，计算组播树的适应度值使用如下函数：
其中，
A、B、C分别为时延、时延抖动和丢包率在适应度函数中的权重系数，其值可以根据具体的应用来设定，在本文的仿真实验中，取值都为1。、、为对不满足约束的路径设定的惩罚系数，在本文的仿真实验中取值为0.5。
2.3 变异操作
变异操作中，选取三个个体向量根据如下公式进行变异，得到变异个体：
其中F为缩放因子，代表变异程度，取值范围为[0，1]。
常用的变异模式有两种：在DE/rand/1/bin模式中，用随机个体（）作为基准向量进行变异，这种方式探索能力强，但收敛速度慢；在DE/best/1/bin模式中，用本代最优个体做为基准向量进行变异，这种方式收敛速度快，但容易陷入局部最优。本文采用上述两种模式的一种居中模式DE/rand-k-best/1，用随机选取的k个个体中的最优个体作为基准向量，既能保持个体的多样性，又能拥有一定的收敛速度。多次实验表明，k在[3，0.3*NP]范围内取值效果最好。 2.4 杂交操作
变异个体和种群的目标个体根据以下公式进行杂交，产生杂交个体：
为了保证个体的进化，杂交个体至少有一个分量由变异个体提供，其他分量根据杂交概率因子CR决定具体哪位由或提供。其中rnds为随机产生的0～1之间的实数，CR是0～1之间的常数，ns是随机产生的维数索引号，其保证了至少有一位分量由变异个体提供。
本算法中具体实现方式为：首先根据随机索引号从变异个体生成树选取一条边，然后根据CR从变异个体生成树或目标个体生成树中逐次选取剩余的边，选取原则为：边的起始节点已在生成树中，而终止节点尚未在生成树中。
2.5 选择操作
选择操作采用的是贪婪策略，经变异及杂交后产生的个体与目标个体进行竞争：
f为适应度函数。
3 仿真实验与分析
实验采用广泛使用的8节点网络模型进行仿真，如图1所示。源节点s=1，目的节点集D={2，4，5，7}。图中每个顶点用四元组（d，dj，l，c）表示，其中的元素分别代表时延、时延抖动、丢包率和费用代价；每条边用四元组（d，dj，b，c）表示，b代表带宽，其他同上。
图 1 8节点网络拓扑图
实验中，种群规模设定为10，最大迭代次数为100。变异算子F=0.5、交叉算子CR=0.5，Qos参数约束量定为：时延约束DE=48、时延抖动约束DJ=8、带宽约束B=70、丢包率约束L=0.001。
本文实验在配置为Pentium Dual Core E6500和4G内存的微机下运行，采用的编程语言为VC++6.0，根据多次试验结果，获得的最佳组播树为。该组播树的最大时延delay=47，最大时延抖动delay_jitter=5，最大丢包率loss=0.0002101，总费用为43。
为了验证算法的性能，将本文算法与文献[1]提出的遗传算法、文献[4]提出的基本差分进化算法在同等的实验环境下进行了对比，得到的结果如图2、图3所示。
图2 3种算法的收敛性比较
图3 3种算法的运行时间比较
图2为3种算法在8节点网络图运行时收敛性的比较，可以看出，随着代数增加，本文算法以较快的速度收敛到最优解；图3为3种算法在随机生成的不同网络节点数的网络运行时间的比较，为了观察算法的整体性能，固定解的大小，使算法结果达到基本最优解时停下来，然后比较运行时间，可以看出，随着节点数的增多，本算法的运行时间并没有大幅度的增加，从而说明本算法效率较优。
4 结束语
本文对Qos组播路由模型和差分进化算法进行研究，提出了一种差分进化组播路由算法。算法采用了一种链路编码的方式，具有n个节点的生成树有n-1条链路，进化种群以生成树为个体，链路是组成个体的基本单元。同时在变异操作中，引入了一种DE/rand-k-best模式，将随机选择的k个个体中的最优个体作为基准向量，引导变异方向。仿真实验表明，本文算法具有较好的收敛性和效率。下一步的工作是研究参数的改变对算法的影响。
基金项目
国家自然科学基金项目（项目编号：40772196），河北省教育厅自然科学项目（项目编号：Z2012092）。
参考文献
[1]XIANG Fei，LUO Junzhou ， WU Jieyi ， et al.QoS routing based on genetic algorithm[J].Computer Communications ，1999，22 （15-16） ：1392-1399.
[2]刘莹，刘三阳.多媒体通信中带度约束的多播路由算法[J].计算机学报，2001，24（4）：62-65.
[3]王新红，王光兴.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报，2002，3（3）：112-117.
[4]孔笋，陈增强.基于差分进化的Qos组播路由算法[J].Proceeding of 29th China Control Conference July 29-31，2010，Beijing：5232-5237.
[5]HUANG Lin，HAN Haishan，HOU Jian.Multicast routing based on the ant system[J].Applied Mathematical Science，2007，1（57）：2827-2838.
[6]孙力娟，王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解[J].电子学报，2006，34（8）：1391-1395.
[7]STORN R，PRICE K.Differential evolution：a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11（4）：341-359.
[8]王力军，田静，李健.基于正交实验及双种蚁群的QoS组播路由算法[J].计算机系统应用，2011，20（6）：73-76.
作者簡介
李晰（1977-），女，河北深州人，讲师，硕士，研究方向：理论计算机科学，智能算法。