论文研究-改进蚂蚁算法在网络流量平衡中的研究.pdf

所需积分/C币:9 2019-07-22 18:52:24 325KB .PDF
收藏 收藏
举报

在分析了当前蚂蚁算法实现网络流量负载重配置的基础上,提出了新的网络链路资源分配策略及改进算法,利用蚂蚁具有找到最短路径及不同种类蚂蚁互相排斥的这一天然特性,很容易在最短路由和链路负载之间取得折中。仿真结果表明,改进的蚂蚁算法对业务请求越是频繁的情况,其负载平衡度和业务到达率越优于其他算法。
3114· 计算机应用研究 资源。 ∑.qi(1) 如图I所示。假设选路因子为8时为最佳路径配置,那 ( 么,蚂蚁随机选择具有8的选路囚子的边的概率最大,这时,由 有选路因子 于新増蚂蚁外激素的累计増加较大,该边的选路因子将増大。 按以上慨率分布,此后的蚂蚁选择该路径的概率将降低,而具 (1)=(2) (17) 有高端区域选路因子的边由于其被选概率较低,而外激素挥发 显然最佳选路因子为γ:(o)。概率样本点转换系数为 相对较大,使其选路因子向最佳位置8靠近。低端区域则因外 激素挥发较少且其相对被选概率增加,这时,该路的外激素强 Yis yi(to) 度将有所增加亦向最佳位置8靠拢。因此,原来较为空闲的则t时刻节点处i边对应选路样本点为 路径的利用率增加,从而缓解了原来最佳路径的拥挤。按照以 X=(int)(A×y2(t)) 上动态过程,系统资源得到了较好的平衡利用。 入选路原则为:若X(t)= bison(n,P)(“=”指最接近), 2.2全局配置 则选择i边(i∈A,) 在动态网络中,从某一节点定期向其他可行路径释放人工2.4算法步骤 蚂蚁,该人工蚂蚁按一般排队原则行进,当到达下节点,再向 a)随机构造网络拓扑G(N,L),生成邻接知阵,释放人工 其他可行分立释放同类人工蚂蚁,如此进行下去对整个网絡逻蚂蚁,搜索网络并进行初始化配置,初始化外激素增加量Q挥 辑拓扑进行搜索,如图2所示。当蚂蚁到达目的点后原路返发系数、选路随机常数、人工蚂蚁释放时间密度,业务产生时 回,并对逻辑路径进行重配置蚂蚁在选路原则上趋向于当前空密度(服从均匀分布)等常量。 配置。这种搜索方式找出当前的最佳可行路径,并排除故障路 b)按时间、空间、数量隨机产生业务,不同种类蚂蚁分别 径,保证了一般业务的畅性,并按最佳路径行进。该人工蚂代表网络中各节点对之间的业务。 蚁的存活无关紧要,且其对系统资源占用较低,对系统增加的 c)对网络中行活的每只蚂蚁L,以式(17)进行路由选择 额外开销很小。 并爬行到下一节点。如果它已经到达目的点位置或将无路可 0.35 0.30 走,则立即死亡。对G中相应边的信息素进行更新,更新规则 0.25 0.20 满足 0.15 q(t)=∫mpQd+p(to) 0.05 0.00 6810 其中:(#(t)=m(t)·Q。若t时刻有m个A“用i边,否 图1不同值下的二项分布B(10,p)图2人工蚂蚁释放 则,Q(t)=0。 图2中,A“为从源点s到宿点e的分支业务。当某分支业 d)如算法运行结果已经收敛或网络负载平衡度低于门限 务成功到达后,即转换为定向业务,并原路返回,且配置所经过 值,则对网络节点重新配置,算法结束;否则,=t+1。 路线的外激素强度 e)如果t时刻对应的时间小于t,转c);否则,转b) 2.3数学推导 3仿真及数值分析 与对应的成力到达并转换成为定向业务A"对应,设分支 本文采用文献[12]网终进行仿真分析。其网络物理逻辑拓 业务X“到达e点后所需时程为,则配置强度为=1,∈扑如图3所示,其中节点间用双向链路连接;各节点对间的距离如 矩阵所示,如果两节点间无直达路径,则令其距离为 (λ"可到达路径,并按先后排序),显然,有最佳激素强度为 并记配置时间为。引用外激素分泌强度Q及挥发 203-11-1-1-1-1 30-132-1-1 因子p,记t时刻节点j处边上业务A“的外激素强度为q 1-1-102-113-1 41320-1-124 (1),显然q(10)=q“。对t时刻有 5-12-1-10-141 (1)=J0p2d+p(to) (14) 1 1 0 其中:Q(t)=m(t)·Q,若t时刻有m个A“占用i边,否则, -1-1-1324101 设一般业务按二项分布B(n,P)随机选路,则最高概率出 图3网络物理拓扑及其邻接矩阵 现值为 为了衡量木文算法性能,对本文算法(算法3)及算法1和 均进行了仿真实验和对比。 pmax n 首先,利用释放人⊥蚂蚁(分支业务)模块对系统进行仿 计算:时刻j节点i边对A"的吸引力为 真初始化,设置一般业务的可行路径并排除障停节点;然后,在 (15)物理系统(物理拓扑、业务产生等)相同的情況下,按三种算法 分别进行仿真运行。各业务均模拟实际情况,按时间步(含排 其中:A;为所有可选边的集合。 队等候、路径长短或容量)行走(传输)。 排斥力为 系统中一般业务按时问、空间、数量随机(均匀分布)产 第8期 李世畅,等:改进妈蚁算法在网络流量平衡中的研究 3115 生,并遵循一定的密度(浓度以密度因子表示,密度因子越大,时程到达,因此,此时算法3最优;而从负载平衡度来看,算法 业务密度越大)。实验发现,三种算法在不冋的业务密度下,3最低,表明资源分配较均衡。可见,在业务密度较大的情况 其性能上各有优劣。当业务密度较大时,算法3表现岀较好的下,由于存在拥塞问题,应当强调资源均衡。由于算法2考虑 性能。 了均衡资源这一点,因此该算法亦有较高的到达率,但由于其 下面给岀两种业务密度的系统模型,并各自进行1012次收敛速度较慢及静态选路的原因,其资源均衡性、业务到达率 实验,比较如下各量,以评价各算法的性能 业务传输时间均不如算法1优越。 a)网络负载平衡度。按式(3)定义,反映某一时刻系统资 源占用均衡状况 4结束语 b)时间(步)归一化因子。系统中各成功到达业务实际传 本文原有蚂蚁算法在解决网络链路资源分配问题上作了 输时间总和与所有这些业务按最少传输时间传输所用时间总进一步的改进,改进的算法为链路负载问题提出了一种新的解 和之比。显然,该因子越小,系统利用趁合理。 决)法,通过使用群体影响作用代替传统数学方法来解决优化 e)到达率。到某一时刻,系统中成功到达业务量与业务问题,利用蚂蚁寻找食物或蚁穴时具有找到最短路径的特性, 总量之比,是各算法优劣的最直接反映 把它应用于基于网络负载平衡求解,即蚂蚁选择路径时,选择 模型1(密庋因子:4.8)实验结果如图46所示。 某条路径的概率是由路由上同类蚂蚁的分泌物和总的分泌物 强度折中决定的。这样,算法的实质就是保持负载分布的平衡 性,同时也要使业务对间的路由尽量短。由于算法1和2缺乏 全局的考虑以及以因子进行选路,因而并没有实现真正意义上 高,尽数81012024改表81012的动态选路。在此本算法通过设置全局人工蚂蚁对全网络进 024 算法2-▲算法3 图4网络负载平衡度 图时间闻出化因手行优化并在选路上引人随机选路实现了真正的动态选路。最 比较(模型1) 比较(模型1) 后通过实验仿真验证了此算法的有效性,得到了较好的结果。 进一步工作将包括参数的选取准则、算法的实用范围、系统评估 等的进一步深入研究,如何将本文的新思路拓宽运用等。 丽0.9 参考文献 [1 DORICO M. Ant colony optimization theory a survey[ J. Theoretic 2 次数 Computer Science, 2005, 344(2): 243-278 算法1-—-算法2算法3 [2] VARELA N. Ant-colony-optimization for virtual wave length path rou 图6业务到达率比较(模型1) ting and wavelet length allocation C//Proe of Congress on Evolu- 模型2(密度因子:7.0)实验结果如图79所示 tionary Compulation. 1999 [3 DORIGO M. Ant colony system: a cooperative learning appmach to 副您计 the traveling salesman problem.J.. IEEE Trans on Evolutionary Computation, 1997, 1(1): 53-66 [4 KAWAMURA H, YAMAMOTO M, SUZUKI K, et al. Multiple ant 68101 24681012 colonies algorithm based on colony level interactions[ J_. IEICE 次数 次数 ,算法1-普算法2一算法3 ·算法1---算法2一算法3 Trans on Fundamentals, 2000, E83(2): 371-379 图7网络负载平衡度 图8时间归一化因子 [5 GUTJAHR W. ACO algorithms with guaranteed convergence to the op 比较(模型2) 比较(模型2) timal solution[ J]. Information Processing Letters, 2002, 8(2) 0.88 45-153 0.86 084 [6 SUGAWARA K. Foraging behavior of multi-robot system and emer- 0.82 :…: gence of swarm intelligence[C]//Proe of IEEE Conference on Sys- 0.8 0.78 tems, Man, and Cybernetics. 1999: 257-262 076 0.74 [7 SIM K, SUN W. A ant colony opt imization for routing and load-bala 024681012 cing: survey and new directions [ J]. IEEE Trans on System 次数 ··算法1-鲁-算法2一▲算法3 Man, Cybernetics,2003,33(5):560-572 图9业务到达率比较(模型2) [8 FU.JINOKI H, CHRISTENSEN K J. A routing algorithm for dynamic 对模型1,由图46可见,在密度因子为4.8的情况下,算法 multicast trees with end-to-end path length control[ J- Compute 1和3有较高的到达率,说明在业务密度较小的情况下,算法 Communications,2000,23(2):101-114 [9 HAMID S. Swarm intelligence based class ifiers [J] Journal of the 13较优;从时间归一化因子来看,算法3最低,说明各业务均 Franklin Institute, 2007, 344(5): 362-376 按最短时程到达,因此,此时算法3最优;而从负载平衡度来101DAss, KONAR A. A swam intelligence approach to the sy nthesis o 看,算法2最低,表明资源分配较均衡,但由于过分强调均衡而 two-dimensional IIR filters[J. Engineering Applications of Artifi- cial Intelligence, 2007, 20(8): 1086-1096 影响了业务传输时间。可见,在业务密度较小的情况下,应当1. AN Xiu-mei. P routing architecture and algorithm based on end _us 强调趋向最短路径,此时不存在拥塞问题。算法3较优于1是 ers contrcl[ J. Journal of Software, 2003, 14(5): 1023-1028 因为它较早收敛的缘故,从曲线的走势亦可让实这一点。 [12 ZHANG Zhi-zhong, HE Rong-xi, ZHANG Yun-lin, et aL. Ant-based 对模型2,由图79可见,在密度因子为7.0的情况下,算法 dynamie logical topologies reconfiguration for WDM networks Journal of Communication, 2001, 22(11): 42-48 3有较高的到达率,说明在业务密度较大的情况下,算法3较 13ˉ沈恒范.概率论与教理统汁教程[M.北京:高等教育出版社 优;从时间归一化囚子来看,算法3最低,说明各业务均按最短 2001:54-63

...展开详情
试读 4P 论文研究-改进蚂蚁算法在网络流量平衡中的研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-改进蚂蚁算法在网络流量平衡中的研究.pdf 9积分/C币 立即下载
    1/4
    论文研究-改进蚂蚁算法在网络流量平衡中的研究.pdf第1页
    论文研究-改进蚂蚁算法在网络流量平衡中的研究.pdf第2页

    试读已结束,剩余2页未读...

    9积分/C币 立即下载 >