网站首页  词典首页

请输入您要查询的论文：

　

标题 用于聚合组播的蚁群优化算法
范文 刘凤娇++蒋永志


摘 要：IP组播将数据传输至组成员时常遇到路由器为每棵组播树保存转发状态的扩展问题，聚合组播技术使得多个组播组共享一棵分布式树，可有效减少需要保存的组播转发状态。提出算法，为每棵组播树都赋予一个代价值，当最优解中聚合组播树数目相同时，可优先选择较小代价值。由于相关算法限定带宽浪费率范围，即限定可增加的节点数目，所以算法可在多项式时间内完成。使用最小集合覆盖思想，设计求解聚合组播问题蚁群优化算法，实验表明，此算法能取得较好优化效果。
关键词：聚合组播；蚁群优化；分布式；最小集合覆盖
DOIDOI：10.11907/rjdk.151446
中图分类号：TP312
文献标识码：A 文章编号文章编号：16727800（2015）009006803
0 引言
随着网络流媒体以及视频服务的广泛应用，IP组播技术发展迅速，网络中组播组数量增加将产生一系列问题。目前，IP组播使用树传递结构，在每一个分支节点进行数据包复制和转发，导致IP组播可以扩展至支持大规模的组播组。然而，树传递结构需要所有树节点保存每一个组的转发信息，转发信息随着组数增加而增加。随着组播日益广泛使用及组播组的增加，将需要越来越多的转发状态入口，尤其是在传输区域。由于每个包转发需要一个地址转发表，更多的转发入口则需要更多存储空间，必然导致转发过程变慢。将组播规模扩展至一个组多个成员，将导致组播组数量太大而产生的扩展问题。为解决此问题，一些专家曾提出多个组共享一棵分布式树的聚合组播技术[ 13 ]。聚合组播树查询是聚合组播的核心，该查询使用完全NP算法。可使用贪婪算法及局部优化算法解决上述问题。启发式算法也被用来解决上述问题[ 4 ][ 5 ]。上述算法的相同点是计算每个组所有潜在可候选分布式树，在某些场合下或许不可取，尤其是当带宽浪费率或分布式树价值太高时。为解决上述问题，本文采用最小集合覆盖思想，设计求解聚合组播问题的蚁群优化算法。实验表明，此算法能够取得较好的优化效果。
1 聚合组播简介
图1为一个分层的多个域互联的网络模型。将区域A看作是互联网服务提供商（Internet Service Provider）一个骨干网络，区域B，C，D，E和F都是用户端网络，共有3组播组G0（D1，B1，C1）、G1（F1，B1，C1）和G2（D1，B1）这3组播组分别对应子树（A1，Aa，Ab，A2，A3），（A1，Aa，Ab，A2，A3）和（A1，Aa，Ab，A2）。由于这3组播组在区域A内的子树部分相同，部分重叠，所以组G0（D1，B1，C1）、G1（F1，B1，C1）和G2（D1，B1）可以在区域A内使用相同组播地址，并且为这3组建立一棵可共享的组播树（A1，Aa，Ab，A2，A3），可共享的组播树被称为聚合组播树，该聚合组播树同时为这3个组播组传递组播数据。此时，核心路由器Aa和Ab只需要为这棵可共享的聚合组播树维护一个转发表项，不再需要为每一个组都存储一个转发表项，因此通过这种方式减少了路由器需要保存的转发表项数据，即减少需要保存的转发状态数。聚合组播示意图如图1所示。
图1 聚合组播示意
使用共同的聚合组播树传递数据，对组G0和G1是不错的方式，但是对组G2来说造成带宽资源浪费问题。这是因为在使用组播树（A1，Aa，Ab，A2，A3）为组G2传输信息时，信息沿路径Aa、A3传送到节点A3，但这对于组G2来说是多余。因此，聚合组播在减少转发表项的同时，也会带来一些额外带宽浪费，需要同时考虑状态的减少和带宽浪费率。针对一个多目标优化问题，本文主要解决给定聚合树数量，使带宽浪费率最小化。
网络模型和定义如下：
（1） 聚合度。
如果给定带宽浪费率阈值为Bth，那么当每组g使用一棵树T来传递数据时，需要满足带宽浪费率小于Bth值。由于允许满足带宽浪费率要求的多个组共同使用一棵聚合树，所以聚合树数目将少于组数。对一个给定的有Ng个组播组的集合，使用聚合组播算法，最终求得Nt棵聚合组播树，则算法聚合度可定义为：
AD=NgNt（1）
其中，Ng表示组播组数目，Nt表示聚合组播树数目。聚合度值越大，则聚合树数目越少，需要维持的转发状态数目也就越少。因此解决方案也就越好。
（2）带宽浪费率。
考虑一棵树T和一个组播组g，树的叶节点集合为leaf（T），组的组成员集合为mem（g）。在聚合组播技术中，当满足条件mem（g）leaf（T）时，组g可以使用树T来传递数据，此时带宽浪费率定义为：
δ（T，g）=|T|-|Tn（g）||Tn（g）|-1（2）
其中，T表示聚合组播树，|T|表示聚合组播树T上的节点数目，（|T|-1）表示聚合组播树T的代价值，|Tn（g）|表示组播组g的原始组播树的节点数目，δ（T，g）表示组g使用树T作为组播树的带宽浪费率。因此，如何从集合T（G）中找到合适的、数量最少的聚合组播树覆盖全部组播组是本文的核心。一个组播组集合和带宽浪费率的阈值。对于每个组播组，从集合T（G）中找到最少数量的聚合树来覆盖所有组播组，T（G）为所有候选组播树集合，因此求解聚合组播问题核心即为聚合树选择问题。
2 蚁群优化算法
本文引入蚁群优化算法，较好地解决了聚合组播问题。首先计算候选组播树集合，记集合G-T为{g1-t1，g2-t2，…，gm-tm}，其中gi-ti为从组gi中去掉和其对应的原始树ti上节点后剩余节点的集合；其次，分别计算对应于各组播组的原始树t1，t2，…，tm，将其加入集合T（g），并依据δ（T，g）分别计算出树t1，t2，…，tm最多可以增加多少节点，记为l，l=bth（t）*|t|；然后，再从集合G-T中选取节点总数小于或等于l的子集，扩展组播树以使该组播树能覆盖上述子集所对应的组播组，扩展后的组播树满足给定的带宽浪费率。所有原始组播树和扩展树构成整个问题的候选树集合。当l取值较大或网络规模较大时，为降低计算候选树的时间复杂度，可以增加一个条件：将可增加节点个数l限定在某个范围内，l最大取值为l=bth（t）×（|Tn（g）|-1），最小取值为
其中，Nk表示添加树ti前蚂蚁k的可行邻域，即所有能覆盖额外组播组的还未被选择组播树。
其中，一只蚂蚁构建解方法如下：
①计算候选组播树集合T（g），并进行初始化，所有组播组都被置上未被选择标志0；
②从候选组播树中随机选择一棵组播树，并将该组播树可以覆盖的组置选择标志1；
③计算剩余候选组播树中每棵组播树能够覆盖的额外组播组数，记为ej，并根据式（4）计算启发式信息，根据式（3）计算信息素；
④根据式（5）计算每棵组播树被选择的可能性，并随机选择一组播树加入候选组播树集合，将所选择的组播树覆盖的组播组置标志1；
⑤若还有未被置标志1的组，则转至步骤（3），否则算法结束。
2.4 信息素更新
每轮算法结束后，都会选择最少聚合树作为最优解，最优解都需要进行信息素更新，信息素更新规则为：
τi=（1-ρ）τi+∑dk=1Δτki（t）（6）
其中，d表示当前最优解中组播树的数量，只有当组播树包含在当前最优解中时，成分的信息素值才会增加。
Δτki（t）=1∑ni=1bi·yi，成分i是蚂蚁k的解sk中的元素0，其它 （7）
3 模拟
采用AT&T IP主干网络作为模拟网络用于本文实验，将随机权重节点模型用于分布式组播组成员中，模拟时间固定在600s。组播组的平均寿命影响组播组数量，
假设400s后组播状态是固定，则每10s采一次样。当模拟时间到达600s，共进行20次采样。分别计算聚合度和转发状态减少率，取平均值作为最后结果。最后，通过使用相同网络拓扑及相同时间比较蚁群优化算法和贪婪算法，如图5所示。可看出，
蚁群优化算法相比贪婪算法，可以得到更好的结果，并且随着网络规模的增长也可在多项式时间内完成。
4 结语
本文探讨用于减少转发状态的聚合组播，聚合组播树选择问题是一个NPC问题，因此提出启发式蚁群优化算法。模拟实验证明，在带宽浪费阈值不同情况下，该算法比贪婪算法效果更好。
图5 蚁群优化算法和贪婪算法的聚合度比较
参考文献参考文献：
[ 1 ] LI L，CUI JH，GERLAM.Tackling group-Tree matching in large scale group communications[A].Computer Networks，2007（51）：30693089.
[2] LI L，JH CUI，GERLA M.A scalable overlay multicast archtecture for largescale applications[A].IEEE Transactions on Parallel and Distributed System，2007（48）：449459.
[3] JH CUI，KIM J，DARIO M，et al.Aprotocol to improve the state scalability of source specific multicast [A].In IEEE Globecom，Taiwan，2002（12）：1721.
[4] WANG H，ZQ GE，CY YU，et al.A modified genetic algorithm for the optimization of aggregated multicast[A].in 11th International Conference on Advanced Communication Technology ，Korea，2009（20）：8388.
[5] WANG H， ZQ GE，FJ ZHU，et al.An immune algorithm for the optimization of aggregated multicast[A].In 11th International Conference on Advanced Communication Technology，Korea，2009（6）：786790.
责任编辑（责任编辑：孙 娟）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/2/5 22:50:26