一种基于计算智能的组播路由算法

刘　杰，王　振，冯志先，杜军平

(1. 中国电子科技集团公司第三十研究所，四川 成都 610041；2.国家国防科技工业局信息中心， 北京100039;

3.北京邮电大学 计算机学院，北京 100876)

摘　要：在通信网络中，多约束组播通信是提高网络运行效率和服务质量的重要途径。一些启发式的算法已经被用来解决多约束条件下的组播路由问题，如模拟退火算法，遗传算法，蚁群算法和粒子群优化算法等。然而，这些算法在求解多约束组播路由问题时存在收敛速度低和计算复杂度高的问题。萤火虫群优化(GSO)算法是一种近期在计算智能领域出现的卓越算法，它可以在一定程度上解决多约束组播树生成过程中收敛速度低和计算复杂度高的问题。提出了一种基于GSO的多约束组播树生成算法(GSO-MCM)。该算法可有效生成满足多约束要求的组播路由树。仿真结果表明提出的GSO-MCM算法在求解和收敛速度，以及网络规模适应性方面均有良好的性能。

关键词：多约束；组播路由；萤火虫群优化；计算智能

doi:10.3969/j.issn.1002-0802.2015.06.014

一种基于计算智能的组播路由算法

刘杰1，王振2，冯志先1，杜军平3

(1. 中国电子科技集团公司第三十研究所，四川 成都 610041；2.国家国防科技工业局信息中心， 北京100039;

3.北京邮电大学 计算机学院，北京 100876)

摘要：在通信网络中，多约束组播通信是提高网络运行效率和服务质量的重要途径。一些启发式的算法已经被用来解决多约束条件下的组播路由问题，如模拟退火算法，遗传算法，蚁群算法和粒子群优化算法等。然而，这些算法在求解多约束组播路由问题时存在收敛速度低和计算复杂度高的问题。萤火虫群优化(GSO)算法是一种近期在计算智能领域出现的卓越算法，它可以在一定程度上解决多约束组播树生成过程中收敛速度低和计算复杂度高的问题。提出了一种基于GSO的多约束组播树生成算法(GSO-MCM)。该算法可有效生成满足多约束要求的组播路由树。仿真结果表明提出的GSO-MCM算法在求解和收敛速度，以及网络规模适应性方面均有良好的性能。

关键词：多约束；组播路由；萤火虫群优化；计算智能

doi:10.3969/j.issn.1002-0802.2015.06.014

收稿日期：2015-01-21；修回日期：2015-04-30Received date:2015-01-21；Revised date：2015-04-30

中图分类号：TP393

文献标志码：码：A

文章编号：号：1002-0802(2015)06-0699-06

Abstract：In communication networks, the multi-constraint multicast communication is an important way to improve the efficiency of network operation and QoS(Quality of Service). Some heuristic algorithms are applied to solving multicast routing problem under multiple constraints, such as simulated annealing, genetic algorithm, ant colony algorithm and particle swarm optimization algorithm. However, problems of low convergence rate and high computational complexity still exist in these algorithms when solving multi-constraint multicast routing problems. GSO (Glowworm Swarm Optimization) algorithm is a promising algorithm recently emerging in the area of computational intelligence, and it can overcome the above deficiencies to some extent. Meanwhile,GSO-MCM algorithm based on GSO is proposed to efficiently generate multicast routing tree and meet multi-constraint requirements. Simulation result shows that GSO-MCM algorithm enjoys good performance in solution, rate of convergence and adaptability of network size.

作者简介：

Multicast Routing Algorithm based on Computational Intelligence

LIU Jie1,WANG Zhen2,FENG Zhi-xian1,DU Jun-ping3

(1.No.30 Institute of CETC, Chengdu Sichuan 610041,China；

2.Information Center of State Administration of Science Technology and Industry for National Defense,Beijing 100039,China;

3.School of Computer, Beijing University of Posts and Telecommunications,Beijing 100876,China)

Key words：multi-constraint, multicast routing, GSO, computational intelligence

0引言

随着网络和多媒体技术的飞速发展，网络多媒体服务，如计算机会议，远程教育，协同工作已逐渐成为互联网活动的主流。组播通信相比于单播通信，在多点数据传输方面更为有效[1]。组播通信的关键是要建立组播路由。不同于单播通信，组播通信需要生成组播树[2]。

现有的研究表明，有很多方法可以解决无约束的组播路由问题，如Dijkstra算法和Steiner树方法[3]。然而，这些传统的方法却不能解决多约束条件下的组播路由问题[4]。组播问题通常对服务质量(QoS)有着严格的要求，其参数包括带宽、时延及时延抖动等。因此，如何快速建立组播路由并满足服务质量的要求是一项重要而紧迫的研究课题。

解决多约束组播路由问题的关键是生成可满足多约束条件的组播树，但求解一棵最优组播树已经被证明是一个NP完全问题[5]。所以，通常采用启发式算法来求解。目前，多约束组播路由问题已经引起了广泛的关注，许多研究人员通过使用不同的启发式算法来解决该问题[6-7]。

目前，主要使用启发式算法来解决多约束组播路由问题，如模拟退火算法、遗传算法、蚁群算法、粒子群优化算法等[8-9]。然而，这些算法在求解多约束组播路由问题时存在收敛速度慢和计算复杂度高的问题[10]。萤火虫群优化(GSO)算法[11]是一种近期在智能计算领域出现的卓越算法，与上述启发式算法相比，它具有更快的收敛速度和较低的计算复杂度[12-14]。本文提出了一种基于GSO的多约束组播树生成的算法(GSO-MCM)，该算法可以有效地生成组播路由树，尽可能满足多约束条件。

本文的贡献包括：①提出了一种基于萤火虫群优化算法的多约束组播树生成算法GSO-MCM；②建立与QoS评价尺度相对应的约束条件和开销函数(涉及时延、时延抖动、吞吐量和分组丢失率)。在提出的GSO-MCM算法中，设计了一个去除环路的功能，该功能使组播树编码方法具有更好的适用性。与其他启发式算法相比，GSO-MCM算法能够在组播树迭代生成过程中更快地满足网络多约束条件。通过一个具有200个节点的网络拓扑仿真实验，验证了GSO-MCM算法的有效性。

本文的结构如下：首先介绍了多约束组播路由问题的背景。然后介绍了提出的GSO-MCM算法的细节。接着给出了GSO-MCM的仿真分析。最后总结了全文，并为今后的工作提供了有价值的建议。

1GSO-MCM算法

对于建立一棵受多种约束条件限制的组播树来说，应该花费最小的成本并达到一定的服务质量。同时，多约束条件下的网络模型有许多参数和可用路径，使得组播树生成算法可能生成满足多个QoS指标的组播路由树。在QoS指标中，时延、延迟抖动、吞吐量和丢包率分别由Dereq、DJreq、Threq、PLRreq来表示。

建立组播路由树的传统解决方法是从组播源节点找到到每个目的节点的路径集合，然后将这些路径合并为一棵组播树[15]。然而，上述方法效率较低且计算复杂度高。为了克服这些缺点，本文提出了一种基于萤火虫群优化的组播路由树生成算法。

萤火虫群优化算法(GSO)是一种新型的群智能优化算法。该算法模拟萤火虫的自然发光特性，通过比较目的荧光值大小的方式实现信息交换。该算法具有参数少的特点，从而使操作更简单和稳定性更加。

(1)组播树编码

首先，对组播树进行编码来作为GSO算法搜索空间中的个体。这里，需要考虑到编码和解码的适用性。关键是要避免的组播树中的环路。给定一棵组播树X，具体的编码方法如下所示：

X=(Prior1,Prior2,…,Priorn)

(1)

式中，X为一棵组播树，Priori表示第i个节点的先验节点。对于不属于组播树节点的先验节点，统一用“0”来表示。源节点的先验节点是其本身。

组播树编码方法的具体流程如下所述：

步骤1：初始化一棵空的组播树X=(01,02,…,0n)。

步骤2：将源节点的先验节点设置为其本身，即X=(01,02,…,Ss,…,0n)。

步骤3：从目的节点集合中随机选择一个目的节点作为当前节点。

步骤4：从与当前节点有连接关系的节点集合中删除最近后继节点。则可以生成当前节点的先验节点集合。

步骤5：从当前节点的先验节点集合中随机选择一个节点作为当前节点的一个先验节点。然后将选择的先验节点设置为当前节点。

步骤6：如果当前节点的先验节点集合为空，即为“0”，转步骤4，否则转步骤7。

步骤7：如果所有目的节点的先验节点集合为空，即为“0”，转步骤8，否则转步骤3。

步骤8：输出该组播树的编码。

组播树编码方法的流程图如图1所示。

图1组播树编码方法的流程

(2)组播树的合并

在传统的GSO算法中，萤火虫i移动到萤火虫j是依据下式完成的：

(2)

式中，i表示要发生位置移动的个体，j表示按照概率大小选择的荧光素值高的个体，即个体i逐渐靠近的目标个体，s表示移动步长，xi(t)表示个体i移动前的位置，xi(t+1)表示个体i移动后的位置。

在多约束条件下QoS组播树生成过程中，我们对式(2)进行改造，使其能适应组播树的生成。在GSO-MCM中，萤火虫i移动到萤火虫j依据下式完成：

Xi(t+1)=Xi(t)⊕Xj(t)

(3)

式中，算子⊕定义如下：组播树xi(t)和xj(t)合并为一棵新的组播树。但是在合并过程中可能会产生环路。为了消除这些环路，新生成的组播树需要利用前面提出的组播树编码方法再编码一次。具体伪代码如下：

fori=1 to length(E) //E 表示目标节点集合

current= E(i);

while current≠S //当前节点不等于源节点

if(count_prior(E(i))>1) // count_prior表示先验节点的数量

current=random_select(E(i)); //随机选择一个先验节点作为当前节点

else

current= prior(E(i));

end

end

end

经过上述去环路处理后，新生成的组播树xi(t+1)就可以去除环路。

(3)GSO-MCM的动态决策范围和邻居点集合

为了解决多约束条件下的组播路由问题，还需要对GSO算法的动态决策范围和邻居点集合进行改造。

关于动态决策范围，由于在组播树中动态决策范围rs是固定的。所以在GSO-MCM中不用进行rs的更新。此外，GSO-MCM中rs的度量单位不是一般的距离，而是组播树个体之间的相似度。该相似度定义为组播树个体之间相同先验节点的数量。一般情况下，rs的大小被设定为全网络范围的一半。

关于个体的邻居点定义如下：

Ni(t)={j:same(xj(t),xi(t))>rs;li(t)

(4)

式(4)中，lj(t)表示个体j的荧光素值，li(t)表示个体i的荧光素值，式(4)所示个体i的邻居点j的含义是i和j之间的相似度大于rs，且个体j的荧光素值要高于个体i的荧光素值。

(4)GSO-MCM算法的具体流程

步骤1：初始化阶段。

输入针对不同业务类型的网络拓扑结构G。在路由优化目标函数的可行域内随机设置N个萤火虫个体。这些萤火虫个体拥有相同的初始荧光素值l0和相同的初始动态决策域值r0。初始化移动步长s，邻居点数量阈值nt，荧光素消失率ρ，荧光素更新率γ，萤火虫感应范围rs，最大迭代次数t，以及组播树路由优化中的约束条件Dereq、DJreq、Threq、PLRreq。

步骤2：预探测阶段。

不满足组播树丢包率约束条件的节点将会被删掉，与这些节点相连的边也会被删掉。同时，不满足时延、时延抖动和吞吐量的边也会被删掉。

步骤3：更新萤火虫i的荧光素值。

步骤4：搜索萤火虫i的邻居。

步骤5：决定萤火虫i的移动方向。

步骤6：更新萤火虫i的位置。

步骤7：若达到了给定的精度或达到了算法迭代的次数，则算法停止。否则转入步骤3。

GSO-MCM算法的流程图如图2所示。

图2　组播树编码方法的流程

多约束组播树生成算法的时间复杂度如下。假定目的地节点的数目是n，以及链接的数量是v。在组播树编码步骤中，时间复杂度为O(nv2)。在组播树合并步骤中，重新编码需要消除环路，所以复杂度为O(nv2)。它还需要将边加入到组播树中，这样网络中的所有节点都被访问，所以时间复杂度为O(v)。在迭代过程中，假设迭代次数为k。因此，整个生成过程的时间复杂度为O(knv2+kv)。

2仿真结果和分析

本文提出的算法通过Visual C++ 6.0实现，仿真实验运行在配置有英特尔双核2 GHz、2 GB内存和Windows XP操作系统的机器上。在实验中使用的网络拓扑是根据文献[16]的方法随机产生的。本文使用一个包含200个节点的拓扑结构。组播组目的节点的比例介于10%和30%。最大端到端时延设置为120 ms，延迟抖动设置为60 ms，运行程序100次，得到仿真实验的平均结果。

在仿真实验部分，使用收敛速度和组播树的开销作为评价标准。收敛速度包含两个部分：收敛时间和收敛概率。组播树开销是4个约束条件(Dereq,DJreq,Threq,PLRreq))的组合。组播树开销的计算式如下：

(5)

在仿真实验及实际应用中，荧光素值与开销函数值呈反比例关系，其计算式如下：

li=1/cost(t)

(6)

GSO-MCM算法的参数设置如表1所示。

表1　GSO-MCM算法的参数设置

本文将GSO-MCM与本领域著名的几种算法进行比较，如基于粒子群优化的组播(PSO)、基于模拟退火的组播(SA)、基于多目标蚁群的组播(MOACS)、基于最大最小蚁群的组播(MMS)和基于树的蚁群优化(NACO)等[1]。图3显示了不同网络拓扑规模下上述各算法的收敛时间的比较结果。

图3不同拓扑规模下各算法收敛时间的比较

从图3 中可以看出GSO-MCM具有最佳的收敛时间。但是，当网络节点的规模很小的时候，相比较算法的收敛时间的差异都很小。节点数量越多，GSO-MCM算法比其他算法的收敛时间越好。可能的原因是：①NACO、PSO、SA、MOACS和MMS算法对一些特殊的组播组节点有特殊的规则，且在初始阶段会花费大量时间；②在发现从源节点到每个目的节点的路径之后，有一个路径合并的操作，这将导致NACO、PSO、SA、MOACS和MMS算法的收敛时间过高；③拓扑规模的增加，使得NACO、PSO、SA、MOACS和MMS算法在算法收敛上可能会花费更多的时间，因为为了找到从源节点到目的节点的路径，需要访问更多的网络节点。

通过实验发现，不仅是拓扑规模，目的地节点的数目也要影响算法的性能。为了测试这种影响，在仿真实验中选择具有200个节点的拓扑结构中的2%到 30%的节点作为组播组成员。图4显示了不同比例的组播组成员节点组播树开销的结果比较。

图4　不同组播组成员比例的组播树开销比较

从图4中可以看出当组播组节点的比例为4%以下时，GSO-MCM算法的开销与其他相比较的算法性能相近。然而，随着组播组节点的比例增大到4%以上后，GSO-MCM算法的性能大幅提高。这是由于当组播组节点的比例很小时，组播树可能近似从源节点到每个目的节点的单播路由。因此，当组播组节点的比例为4%以下时NACO、PSO、SA、MOACS和MMS算法的性能也很好。然而，当组播组节点的比例增加时，与其他算法相比GSO-MCM算法可以快速改善组播树的开销性能。

在时间复杂度比较方面，PSO、SA、MOACS和MMS算法的时间复杂度为O(nv3)， NACO算法的时间复杂度为O(nv2)[1]。这表明，本文提出的GSO-MCM算法具有比PSO、SA、MOACS和MMS算法更好的时间复杂度和与NACO算法相同的时间复杂度。

在仿真实验设置中，每个链路的时延测量值是0 ms和30 ms。时延约束被设置为300 ms和时延抖动设置为70 ms。图5表明当迭代的最大次数变化时平均收敛概率的差异。从图5中可以看出，对于该实验设置的具有200个节点的网络拓扑来说，迭代的次数在15以下时算法就可以收敛。也就是说，当迭代次数的最大值被设置为15时，算法的收敛概率是1。

图5　迭代次数变化时平均收敛概率的差异

在仿真实验中还考虑了网络拓扑规模和迭代次数之间的关系。经过反复实验，GSO-MCM算法的平均迭代次数为12。仿真结果如图6所示。从图6中可以看出尽管GSO-MCM算法能够收敛，但迭代次数会随着拓扑规模的增长而增长，同时迭代次数的平均值趋向于以线性的方式增加。

图6网络拓扑规模和迭代次数的关系

3结语

本文提出了一种基于GSO的多约束组播树生成算法(GSO-MCM)。该算法通过将萤火虫群优化算法进行改造，使其适用于多约束条件下的组播树生成过程，并通过组播树合并和环路消除等方式提高组播树的生成性能。通过与一些其他著名的基于智能计算的启发式的组播树生成算法在收敛时间、网络拓扑规模、组播组节点比例等指标下进行比较，来验证该算法的有效性。仿真结果表明本文提出的GSO-MCM算法在搜索速度和有效性方面有着明显的性能优势。进一步，对于下一代网络的组播路由协议来说[17]，该算法在实用性和适应性方面均有着巨大的潜力。

参考文献：

[1]Avokh A,Mirjalily G. Load-Balanced Multicast Tree Routing in Multi-Channel Multi-Radio Wireless Mesh Networks Using a New Cost Function [J]. Wireless Personal Communications, 2013, 69(1): 75-106.

[2]LI F, FANG Y, HU F, et al. Load-Aware Multicast Routing in Multi-Radio Multi-Channel Wireless Mesh Networks [J]. Computer Networks,2011,55(9):2150-2167.

[3]ZHAO L, Al-Dubai A Y, MIN G. GLBM: A New QoS Aware Multicast Scheme for Wireless Mesh Networks [J]. Journal of Systems and Software, 2010, 8(3): 1318-1326.

[4]Lim S, Ko Y, Kim C, et al. Design and Implementation of Multicasting in Multi-Channel Multi-Interface Wireless Mesh Networks [J]. Wireless Networks, 2011, 17(4): 955-992.

[5]Kakhbod A, Teneketzis D. An Efficient Game Form for Multi-Rate Multicast Service Provisioning [J]. IEEE Journalon Selected Areas in Communications, 2012, 30(11): 2093-2104.

[6]Koutsonikolas D, HU Y C, WANG C C. Pacifier: High-Throughput, Reliable Multicast Without Cryingbabies in Wireless Mesh Networks [J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1375-1388.

[7]Galvez J J, Ruiz P M, Skarmeta A F G. Responsive On-Line Gateway Load-Balancing for Wireless Mesh Networks [J]. Ad Hoc Networks, 2012, 10(1): 46-61.

[8]CHENG H, YANG S. Joint QoS Multicast Routing and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks Using Intelligent Computational Methods [J]. Applied Soft Computing, 2011, 11(2): 1953-1964.

[9]Jahanshahi M, Dehghan M, Meybodi M R. A Mathematical Formulation for Joint Channel Assignment and Multicast Routing in Multi-Channel Multi-Radio Wireless Mesh Networks [J]. Journal of Network and Computer Applications, 2011,34(6):1869-1882.

[10]TU W, Sreenan C J, CHOU C T, et al. Resource-Aware Video Multicasting via Access Gateways in Wireless Mesh Networks [J]. IEEE Transactions on Mobile Computing, 2012, 11(6): 881-895.

[11]Krishnanand K N. Glowworm Swarm Optimization: A Multimodal Function Optimization Paradigm with Applications to Multiple Signal Source Localization Tasks[D]. Department of Aerospace Engineering, Indian Institute of Science,2007.

[12]Jangha Kang, Kyungchul Park, Sungsoo Park. Optimal Multicast Route Packing [J]. European Journal of Operational Research, 2009(196): 351-359.

[13]Krishnanand K N, Ghose D. Glowworm Swarm Optimization for Multimodal Search Spaces [J]. Handbook of Swarm Intelligence, 2010(1): 451-467.

[14]Krishnanand K N, Ghose D. Glowworm Swarm Optimization: A New method for Optimizing Intelligence Multi-modal Functions [J]. International Journal of Computational Studies, 2009, 1(1):93-119.

[15]ZENG G, WANG B, DING Y, et al. Efficient Multicast Algorithms for Multi-Channel Wireless Mesh Networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(1): 86-99.

[16]Ansari N, Cheng G, Wang N. Routing-Oriented Update Scheme (ROSE) for Link State Updating [J]. IEEE Transactions on Communications, 2008(56): 948-956.

[17]李纪舟, 路璐, 郭利民. 空间互联网技术发展现状及趋势[J]. 通信技术, 2015，47(01):1-7.

LI Ji-zhou, LU Lu, GUO Li-min. Technology Development Review and Trend of Space Internet. Communications Technology, 2015，47(01):1-7.

刘杰(1984—)，男，博士，工程师，主要研究方向为机器学习、智能通信技术；

王振(1982—)，男，硕士，工程师，主要研究方向为信息管理与信息系统；

冯志先(1981—)，男，硕士，工程师，主要研究方向为战术通信网络、软件工程；

杜军平(1963—)，女，博士，教授，博导，主要研究方向为计算机应用、人工智能理论与技术。