基于遗传算法的多媒体组播路由问题解决方法

EgyptianInformatics Journal（2011）12，107开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章基于遗传算法艾哈迈德·尤尼斯埃及Sohag大学理学院计算机科学系收稿日期：2010年11月7日;接受日期：2011年2011年7月20日在线提供摘要许多多媒体通信应用需要一个信源通过通信网络向多个目的地发送多媒体信息。为了支持这些应用，有必要确定一棵代价最小的组播树，将源节点连接到目的地节点受到多媒体通信的延迟约束。这个问题被称为多媒体组播路由，并已被证明是NP完全的。提出了一种求解多媒体组播路由的遗传算法，该算法在带宽和时延约束下寻找低代价组播树。在该算法中，从源节点到目的节点的k条最短路径用于基因型表示。仿真结果表明，该算法能够找到较好的解，收敛速度快，可靠性高。它可以满足多媒体通信网络的实时性要求。随着网络节点数量的增加，算法的可扩展性和性能也相当令人鼓舞。©2011计算机和信息学院，开罗大学。由爱思唯尔公司制作和主持All rights reserved.1. 介绍多媒体数据的多播传输是一种重要的业务电子邮件地址：a_y_hamed@yahoo.com1110-8665© 2011计算机和信息学院，开罗大学。制作和主办Elsevier B.V.保留所有权利。开罗大学计算机和信息系负责同行审查。doi：10.1016/j.eij.2011.04.004制作和主办：Elsevier由网络层提供;事实上，它允许运营商在许多情况下节省大量的网络资源。受益于多播传输的最重要的应用之一是视频剪辑流，其中相同的内容通常同时发送给互联网上的数百万用户。另一个应用是IPTV，它将在未来几年内由大多数ISP提供商发布。但还有许多其他的例子。实现组播服务时的一个重要问题是组播树的设计，它不仅影响组播服务的质量，而且还应考虑网络利用率。解决这个问题的第一个作品涉及一个单一的关键词多媒体通信;组播路由;组播树;遗传算法;带宽和时延公司简介命名法NEUe（i，j）PTBC（e）该组节点该组通信链路该组目的节点从节点ieN到节点jeN的链路从源到目的节点的最短路径组播树E的带宽E的成本D（e）延迟ePop_size人口数Maxgen最大世代数G一Ge染色体的根人口帐户世代108 A. Younes组播会话，并集中在最小化每个单树的传输成本。许多启发式算法已经被提出来解决NP完全无约束的情况[1，2]，称为Steiner树问题。其他作品，如[3-由于在现实世界中，多个组播会话同时发生，一个新的和更复杂的优化问题，lem需要表示：组组播路由问题，其中包括在研究的最佳组合树的多个会话并发。到目前为止，只有少数论文发表在这个主题[6特别是，Chen等人[8]使用整数编程方法，仅考虑具有相同带宽要求的会话。他们定义了多播打包问题，其中网络试图同时容纳所有多播组，同时避免高吞吐量链路上的瓶颈（即，最小化在多播组之间共享的最大拥塞链路）。最大拥塞的最小化是以增加一些组播树的大小为代价的，这反过来又影响了延迟。通过向最佳填充配方的目标函数添加惩罚项来解决这种权衡。惩罚项是从每个多播会话获得的最优树的大小的膨胀量的函数，该最优树独立于其他多播会话，即，孤立地。由于优化问题的数学规划公式在计算上是难以处理的，他们求助于次优解。他们的启发式方法旨在减少链路的共享，同时确保多播树的大小永远不会超过孤立多播组的最佳树大小的α倍。利用割平面不等式和分枝-割算法计算每个组的最优组播树。随后，Wang等人[9]考虑了在容量受限约束下具有多个多播会话的多播路由问题（没有对延迟进行分析）。为了解决这个问题，他们提出了两种启发式算法：基于Steiner树的算法和基于割集的算法。如果服务的可用带宽刚好足够，即使解决方案存在，这些算法也可能无法找到解决方案他们的启发式利用一个简单的距离为基础的成本函数。在过去的几年中，遗传算法（GA）在解决网络领域的复杂问题方面越来越受到关注，如网络设计[10]和单播路由[11]。Hwang等人提出了一种求解无约束组播路由问题的遗传算法[12]Bhattacharya et al.[13]，而Chen等人[14]以及Hamdan和El-Hawary[15]在考虑为单个多播会话中的实时应用提供Randaccio和Atzori[16]提出了一种基于遗传算法的组组播路由晨和孙[17]提出了一种新的基于遗传算法的组播路由优化算法，该算法在带宽和时延约束下寻找低代价组播树本文基于遗传算法，设计了一种具有带宽和时延约束的组播路由优化算法，该算法适用于参数不确定的网络。重点是确定从源到一组目的地的组播路由，具有严格的端到端延迟要求和最小可用带宽。本文的目标是开发一种算法，以找出与带宽和延迟的约束，同时优化端到端的延迟和带宽提供的QoS保证的组播路由。随着网络节点数量的增加，该算法的可扩展性和性能也相当令人鼓舞。本文的结构如下。问题描述和公式在第2节中给出。第3节介绍了遗传算法及其算子。第4节介绍了所提出的算法。在第5节中给出了两个例子，第一个例子有八个节点，并将我们算法的结果与[17]的结果进行比较。第二个例子有20个节点。第六节是结论。2. 问题描述网络通常表示为加权有向图G=（N，E），其中N表示节点集合，E表示连接节点的通信链路集合 |N|和| 分 别表 示网 络 中节 点 和链 路的 数 量[17] 。 | denote thenumber of nodes and links in the network, respectively [17].研究了从一个源节点到多个目的节点的具有带宽和时延约束的多播路由问题。 设Xn0;u1;u2;... ;u mN是多播树的从源到目的地节点的集合。其中n0是源节点，并且U={u1，u2，... ，um}记录一组目的地节点。多播树T=（NT，ET），其中NT<$N，ET<$E，T[17]中存在从源节点n0到每个目的节点deU的路径PT（n0，d）。e（i，j）是从节点i e N到节点j e N的链路。三个非负实数值函数与每个链路e（e∈E）相关联：成本C（e）、延迟D（e）和可用带宽B（e）。链路成本函数C（e）可以是货币成本或必须优化的资源利用的任何度量。链路延迟D（e）被认为是交换、排队XX不不.X！基于遗传算法的带带宽和时延约束的组播路由传输和传播延迟。链路带宽B（e）是物理或逻辑链路的剩余带宽。链路延迟和带宽函数D（e）和B（e）定义了必须约束的标准。路径PT的成本被定义为该路径中所有链路的成本之和，可以由下式给出：联系我们Ce1e2PT树T的总成本被定义为该树中所有链路的成本之和，并且可以由下式给出：联系我们C e2e2ET路径P（n，d）的总延迟简单地是利用文献[18]中求k条最短路径的算法，证明从源节点到各目的节点的候选路径集。遗传算法的染色体由一系列长度为m的整数排队组成，染色体的基因是n到ui之间k条最短路径中的路径种群中的每个染色体表示一棵组播树。显然，染色体代表多播路由问题的候选解决方案，因为它保证了源节点和任何目的地节点之间的路径。由于节点n0和ui之间有许多路径，使得染色体的编码空间可能变大，从而降低了解的收敛性。现在，对于每个目的地节点deU，通过k最短路由算法，[17]通过找出所有的路径可以提高编码空间沿PT（n0，d）的所有链路的延迟：X联系我们e2 PT n0; d其满足来自源节点N0带宽约束去-多播树的时延T是从源节点n0到每个目的节点deU的路径上的时延的最大值。DT最大值DPT;d2U4e2 PT n0; d路径PT（n0，d）的带宽被定义为沿着路径的任何链路处的BPBe;e2P53.2. 初始种群根据以下步骤生成初始种群：● 步骤1：通过假设U ={u1，u2，. . .. ，Pk}，（k是ui中最短路径的个数）表示一组最短路径从源节点到目的地节点ui，并且Pi=树T的带宽被定义为沿着树的任何链路处的最小BTBe; e2 ET6假设组播树的最小带宽约束为B，最大时延约束为D，给定组播需求R，则带宽时延约束组播路由问题是寻找一棵组播树T，满足：1. 带宽约束：B（T）= B。2. 延迟约束：D（T）= D。假设S（R）是集合并且满足上述条件，则所需的组播树T为：CTCTs; Ts2 SR3. 提出的遗传算法遗传算法作为一种功能强大、应用广泛的随机搜索和优化技术，是当今最在所提出的遗传算法中，我们考虑了四个组成部分：（1）编码方法，它是程序解的遗传表示（基因型）。(2)一种创建染色体初始种群的方法，（3）目标函数（4）在繁殖过程中改变后代遗传组成3.1. 编码方法假设n0是源节点，并且U ={u1，u2，. ，um}表示目的地节点的集合，最小带宽约束，{n0，n1，. ，u i}是节点的集合。 然后，通过从每个ui，{i=1，. ，m}，我们可以在初始群体中产生如下形式的染色体：其中g1，g2，g3，. ，g，m表示满足nodn0和ui之间的带宽约束的m条最短路径中的那些。(See 图第一章G1G2G3........Gmn0，ni，nj，………………………………n0，ni，nj，......................................n0，ni，nj，n0，ni，nj，………………………………n0，ni，nj，12.Kum…………………………12.Ku212.Ku1节点间满足带宽约束的K条最短路径n0和ui目的地节点。图1染色体表示。De;d2 U3终端节点DeU和组成路由集作为候选遗传算法编码空间的路径集P110 A. Younes步骤2：重复生成pop_size染色体数。G1G2G3Gi........GKGm3.3. 目标函数假设组播树的最小带宽约束为B，最大延迟约束为D，给定组播需求R，则带宽延迟约束组播路由问题是找到满足以下条件的组播树T：1. 带宽约束：B（T）P B。2. 延迟约束：D（T）6 D。假设S（R）是集合并且满足上面的条件，那么，我们找到的多播树T是：CTC Ts; Ts2SR7也就是说：找到G的子网络T（N）=（NT，ET，CT），使得：– N NT– 存在从源节点到每个目的节点的路径;– TNe2ETCe图3突变操作。交叉操作产生的后代如图所示。 二、3.4.2.变异操作变异操作是在逐位的基础上执行的。在所提出的方法中，如果变异率（Pm）被验证，则执行变异操作。在这种方法中，突变率Pm将为0.2，并且是随机估计的。随机选择要突变的点。通过突变产生的后代显示在图1中。3.第三章。4. 该算法用BorlandC++ Ver. 5.2和操作系统Windows XP。该算法的步骤如下：算法13.4. 遗传算子3.4.1. 交叉操作交叉操作用于通过一个切割点从两个亲本繁殖一个子代。如果验证交叉比（Pc=0.95），则将执行交叉操作。随机选择切割点。交叉操作执行如下：步骤1：从当前种群中随机选择两条染色体。步骤2：随机选择切割点第三：a. 通过提取第一条染色体的组成部分（从第一个基因到切割点）并填充到孩子身上。b. 此外，将第二个染色体的组成部分（从切割点+1到最后一个基因）和填充到孩子身上。切割点母孩子5. 实验结果本节通过将上述算法应用于以下两个示例来显示其有效性：5.1. 第一示例母图2交叉操作。这个例子通过使用来自[17]的具有八个节点的网络来展示上述算法。每个链接由一个三重组（B，D，C）表示，随机给出其值，如表1和图2所示。 四、遗传算法在组播路由中的应用pop_size，maxgen，Pm，Pc，no，目的地节点U，B步骤：1. 按照第3.2节生成初始种群2. gen< $13. While（gen6 maxgen）do4. P<$15. While（p6pop_size）做6. 遗传操作6.1. 获取新种群6.2. 从亲本群体中选择两条染色体6.3. 根据Pc应用交叉（PcP0.9）6.4. 根据Pm参数（Pm60. 2）对新的子节点进行变异7. 计算新的子节点的延迟和成本（D（T）C（T）），（3）和（1）分别8. 如果（D（T）=D），则将此子项另存为候选解决方案。9. P<$p+1如果结束，则结束g1g 2g 3g 4.●●●●G1G2G3G4....GiGJGmG1G2G3G4…GiGJGmG1G2G3G4....GKGlGm7–812261234871235486712354867基于遗传算法的带带宽和时延约束的组播路由表1给定网络的带宽、延迟和成本（图1） 4）。链路B带宽D延迟C费用1–215361–310151–513341–68362–413262–815283–412344–610364–79134–893465–612266–71024图5所提出的遗传算法得到的组播树。图4网络拓扑结构。图6由[17]获得的组播树。表2从源节点1到每个目的地节点的候选路径集合例如1。目的节点最短路径41287641341564124156782451512465128765134657134287134671246712871567156428781564281342813467815678128124678112 A. Younes图7给定网络的带宽值。图8延迟矩阵。图9成本矩阵。110171320816414116719129基于遗传算法的带带宽和时延约束的组播路由图1020个节点的组播树。假设源节点是节点1，目的地节点是{4，5，7，8}，如图4所示。通过使用算法[18]来找到具有最小带宽约束B =10的k条最短路径，我们可以找到从源节点1到每个目的地节点的候选路由集，如表2所示。该 算 法 的 参 数 设 置 为 pop_size= 20 ， Pm=0.2 ，Pc=0.9，maxgen= 600.带宽B=10，延迟D=7。因此，上述网络的所需多播树如图11所示。 5，成本44。图17示出了由[17]获得的多播树。第六章通过比较图5中给出的由所提出的遗传算法获得的组播树和图5中给出的由遗传算法[17]获得的另一个组播树。6、我们注意到以下几点：1. [17]得到的树中路径1 fi3fi4fi8的带宽B根据等式9等于9。（5）不等于所施加的10。2. 路径1fi 2不是真的，因为节点2不代表-重新发送目标节点。因此，基于所施加的参数，由[17]5.2. 二示例这个例子通过使用来自[18]的具有20个节点的网络来展示上述算法。每个链接由一个三元组（B，D，C）表示，随机给出其值，并在以下矩阵中显示（图1和2）。7-9）。源节点n0为节点1，目的节点集合U={9，11，12，14，16，17，19，20}，最小带宽约束B=12。通过参考文献[18]中的k条最短路径算法，我们可以找到从源节点1到每个目的节点的候选路由集，如表3所示。算法中的参数设置：pop_size= 20，Pm= 0.2，Pc= 0.9，maxgen = 600。源节点n0是1号节点和目的节点是U={9，11，12，14，16，17，19，20}，D=11，我们找到如图10所示的多播树，成本=122。表3示例2的从源节点1到每个目的节点的候选路径集合。目的地最短路径节点911316479117842161379113162479117864791137911784791178416137911786416137911117864161111784216111137416111131611117841611117847131611113742161111786421611121178612113746121131624861211784612113164612113748612113164861211316246121411316468141131624681411316481411374814113746814117814113162481416117842161178641611784161178647131611374161137421611786421611784713161131617117113164681711316481711374817113162481711374681719117814191137481419113164814191137468141911316246814192011020114 A. Younes6.结论和今后的工作提出了一种基于带宽和时延约束的多播路由遗传算法该算法使用第k个最短路径算法[18]来构造路由集。通过找出从源节点到目的节点的所有满足带宽约束的路由，将路由集组成遗传算法编码空间的候选路由集，可以改进编码空间该算法通过启发式的交叉和变异操作，保证和加快了最优解的搜索能力，并使解具有全局收敛性。将上述算法的结果与文献[17]中的算法进行比较，发现文献[17]中的算法所得到的组播树是不正确的。第二个实例的实验结果表明，该算法对大规模的组播路由有一定的效果计算机网络。该算法可应用于多约束附录A. 附录表3.引用[1] Shaanxi A ， Lu S ， Shin K. 本 地 化 组 播 路 由 。 在 ： IEEEGlobecom' 95会议录; 1996。p. 1352-6。[2] 德雷克·多拉塔·E，霍加迪·斯特凡.关于终端Steiner树问题的近似算法89.第八十九章：一个女人[3] 贾X。广域网中多媒体应用的延迟受限多播路由分布式算法。IEEE/ACM跨网络1995;6：828[4] 郑建，洪世，许宏。一种适用于延迟敏感应用的快速多播路由算法。见：Globecom' 97会议记录; 1997年。p. 1898-1902年。[5] [10]杨文军，王文军，王文军.基于遗传算法的多QoS约束的高效组播路由。J Comput Commun 2007;30（16）.[6] 王丙，赖乙，杨R.“多媒体流的最佳多播”。计算机操作研究1999;26：461[7] 作者：Zhang H，Jiang H，Jiang T.基于组播树的多点对多点全广播通信路由。IEICE Trans Commun 1995;E78-B：720[8] ChenS，Gunluko，YenerB. 多个布局问题。IEEE/ACM跨网络2000;8：311-8.[9] 王春，梁春，杨瑞.多组组播打包的启发式算法。计算机操作研究2002;29：905-24.[10] 作者：A.基于遗传算法的组播业务网络容量分配。IEEECommun Lett 2004;8（6）：403-5.[11] Ahn CW，Ramakrishna RS.最短路径路由问题的遗传算法及种群规模。IEEE Trans Evolut Comput 2002;6（6）：403[12] 黄瑞红，杜伟英，杨胜春。基于遗传算法的多播路由。JInform Sci Eng 2000;16：885-901.[13] [10]杨文，李文，李文.基于遗传算法的多播网络有效出路方案。在：IEEE个人无线通信国际会议（ICPWC 2005）; 2005年1月。p. 500-4[14] 陈丽，杨志，徐志.一种求解多播路由树的度时延约束遗传算法。In：The Fourth International Conference on Computer andInformation Technology（CIT）; September 2004. p. 1033-8[15] 李文，李文，等.基于遗传算法的多播路由算法研究.北京：高等教育出版社，2001.加拿大会议选举计算工程2004;4：2363[16] Randaccio LS，Atzori Luigi.一种基于遗传算法的组多播路由方法。J Network 2006;1（4）;Waxman BM.多点连接的路由。IEEE J Select Areas Commun1988;6（9）：1617[17] 陈华孙宝林基于遗传算法的带宽和时延约束多播路由优化算法。《通讯计算机杂志》2005;2（5）[ISSN：1548-7709，USA，May，（Serial No.6）].[18] 尤尼斯河用遗传算法求网络中的k条最短路。Egypt Inform J2010;11（2）.