Ｑ：塑 Ｓｃｉｅｎｃｅ。ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｉｎｎｏｖａｔｉｏｎ Ｈｅｒａｌｄ Ｔ技术 基于蚁群优化的动态自适应拥塞避免路由算法 冯欣 杨华民 贺丽柏 尹方超 （长春理工大学计算机学院 吉林长春 １ ３００２２） 摘要：拥塞避免是控制网络拥塞的一种有效的方法。本文提出了一种基于蚁群优化的动态自适应拥塞避免路由算法，引入最大最小蚁 群模型（ＭＭＡＳ），在人工蚂蚁动态探索最优路径的同时，可以并存多条次优路径，算法引入了拥塞预誓机制，对链路的拥塞程度进行监控， 以避免陷入拥塞。仿真实验表明，该算法可以有效避免拥塞，提网络的传输速率和网络负载。 关键词：毁群优化 拥塞避免 负羲均 中图分类号：ＴＰ３９ ３．０１ 文献标识码：Ａ 文章编号：１ ６７４－－０９８Ｘ（２０１ ｏ）１ ２（ｃ）一００３２－ｏ１ 在还回源节点途中不仅更新目的节点 计算机网络的拓扑结构可以用加权有 ｓ的信息素表，还依次更新路径上各个中间 向图Ｇ（ｖ，Ｅ），其中Ｖ＝｛ＶＩ，Ｖ ．．，Ｖ ｝是Ｇ中节 节点的信息素表。本算法引入最大最小蚁 １网络模型 路将要发生拥塞时，即停止向该链路转发 数据包（不包括人工蚂蚁），避免链路拥塞； 人工蚂蚁则正常的探索最优路径，确保算 点的集合，代表网络中路由器的集合， 为 群模型（ＭＭＡＳ）和拥塞预警模型，可以使得 节点数；Ｅ＝ ，ｅ２，．．．，ｅ ｝为图Ｇ中边的集合， 算法能够同时探索到几条路径，通过概率 对应实际网络中节点间通信链路的集合， 选择及时的将流量分散到不同链路上，从 ｍ为Ｇ中的边数。为了简化网络模型，假设 而避免拥塞现象发生。 网络中任意两个节点间至少存在一条链路。 网络中所有节点都维护一个信息素表 ３算法改进 如表１所示。其中Ｍ为节点ｊ可以到达的 ３ １ ＭＭＡＳ模型 目的节点数，因为图Ｇ中任意两节均可达， 由于网络的动态特性，网络流量的随 故节点ｊ可能的目的节点是除自身外的所有 机性和突发性导致节点间的最优路径也会 节点。Ｌ为节点ｊ的邻居节点数。表ｌ给出了从 随之变化，算法中的人工蚂蚁难以快速的 节点ｊ到达某一目的节点时选择下一跳节点 跳出原有平衡，去探索到新出现的最优路 的概率，由动态规划原理可知，一条最佳路 径。为了克服这一现象，引入了ＭＭＡＳ模 径是由许多最优子路径组成，因此时延小、 型，该模型对算法做如下改进： 拥塞度低的链路应有更打的概率值。 （１）链路中最大选择概率。Ｂ 更 新链路信息素表时，如果信息素浓度增加 ２动态自适应拥塞避免算法 链路的选择概率Ｐ ｄ＞Ｐ。，其中Ｐｏ∈（Ｏ，１）， ２．１算法描述 则 仅更新时延估计表，而不更新信息 网络中的每个节点的维护自身的 素表。 信息素表和时延估计表，节点需按一定的 （２）采用新的链路方法： 速率发送人工探测蚂蚁，以便及时获取网 当目的节点为当期节点的邻居节点 络动态信息。算法中存在两种人工蚂蚁，前 时，则选择Ｆ４的节点为下一跳节点，否则， 向蚂蚁 ，和后向蚂蚁 。 表示由源 按如下公式选择链路； 节点发往目的节点的前向搜索蚂蚁， 数据包（包括人工蚂蚁）从当前节点ａ 表示由目的节点还回源节点的信息素更新 到达目的节点 选择下一跳节点为 蚂蚁。 ， ∈｛ｎｅｉｇｈｂｏｒｓ（ａ）｝的概率 网络中的节点Ｓ（Ｓ∈Ｖ）周期性的发送人 工蚂蚁 其目的节点ｄ（ｄ∈Ｍ）按平均概 ．：』ｌ¨ ，ｐ‘ 依路由表 计算，其它 率随机选出，我们把源节点为ｋ目的节点为 ｄ的前向蚂蚁记为 。 与普通的数 式中，Ｐ为（０，１）之间的随机数； 据包具有相同的优先级，按相同的路由规 Ｐ ∈（０，１），通过设置Ｐ 可以决定按信息素 则搜寻路径。 在寻路过程中，记录路径 表搜索还是探索链路； 。为节点ａ的邻居 上每条链路的等待时延和传输时延，当 节点数。 到达目的节点ｄ时， 蚂蚁以堆栈的 仿真实验表明：当Ｐ ０．９时，数据流 形式保存路径上的时延信息。 量集中到一条链路上，算法容易陷入局部 ２．２时延估计表的更新 最优；当Ｐ ０．７时，数据流量以接**均 为了更好的说明后向蚂蚁 的更新 概率分布到不同链路上，无法体现最优路 规则，假设蚂蚁 搜索到的路径为 径的优势；当０．７ Ｐ ０．９时，算法可以将 ａ ，Ｊ２，．．．， ，ｄ，节点ａ的时延估计表 流量合理的分散到各链路，并能在网络状 ，．．…和Ｄａ是评估路径ａ，＾，Ｊ ，．．．，＾，ｄ优劣性 态改变时及时的探索到新的最优链路。 的指标，为了让时延估计表 。和Ｄ 可以 ３．２拥塞预瞀模型 更好的反应从节点ａ到节点 所需动态时 链路的等待队列长度直接反应了链路 延，我们在更新 ａ和Ｄ 采用了一种均衡 的拥塞情况，算法中设置等待队列的上限 计算，可以有效的减少因概率选择带来的 阀值，可以准确预测到将要发生拥塞的链 不确定性影响。 路。拥塞预警模型： ２．３信息素表的更新 数据包（不包括人工蚂蚁）从当前节点 信息素增量的计算必须可以有效的反 口到达目的节点 选择下一跳节点为 应当前选择路径的优劣度，即那些链路时 ，Ｊ∈｛ｎｅｉｇｈｂｏｒｓ（ａ）｝的概率： 延（等待时延和传输时延之和）较小的链路 ＩＯ，Ｗ， Ｗ０ ＝ ．得到较大的信息素增量，而那些时延较大 Ｉ依路由表 ，计算，其它 的链路选择只能得到较小的信息素增量。 式中，ｗ，为链路．，的等待队列长度， 为了更加充分的利用 ．， 收集到的信息， ｗｎ为拥塞上限阀值。当节点预测到一条链 ３２ 科技创新导报Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｉｎｎｏｖａｔｉｏｎ Ｈｅｒａｌｄ 法可以及时探索到当前最优路径。 ４仿真实验结果及分析 仿真实验从两个方面评价路由算法： （１）平均时延，在一定的时段内，所有到达目 的节点的数据包的传输时延和等待时延的 均值；（２）平均队列长度，在某一时刻，所有 节点的队列（包括节点缓冲队列和链路等 待队列）长度的均值。 实验中采用的网络图由Ｗａｘｍａｎ随机 模型生成，图中，边的生成概率为： Ｐｅ（Ｕ，ｖ）＝ｈ．ｅｘｐ其中 （“，ｖ）表示节点 至节点１Ｃ一 ］ ，的几 何距离，Ｌ表示两节点间的最大距离，参数ｇ 用来控制随机图中短边和长边呈现的数量， 参数ｈ则用来控制随机图的平均度。为了简 化处理，实验中ａ（ｕ，ｖ）表示为数据包链路上 的传输时延，Ｌ为链路上的最大传输时延。 实验中，每个节点以泊松过程产生业 务流，每个业务流包含的数据包个数按负 指数分布，数据包发送间隔为０．０１Ｓ，数据包 拥有相同的大小和优先级，业务流到达平 均间隔为ｌ Ｓ，业务流包含的数据包数均值 初始为５Ｏ，按ｌ０／ｓ的步长增长。人工蚂蚁占 用的流量很小，实验中将此部分流量忽略， 实验节点每个仿真时间步为间隔发送一只 人工蚂蚁。在每次实验开始时，算法运行 １０００时间步来初始化节点信息素表。实验参 数设置为：各参数（ａ， ， ，￡，Ｐ。，Ｐｌ， ）设定 为（０．２，０．９，４，０．９，０．８，０．０５，５０），当网络负载 较轻时，ＡＤＲ算法和ＭＭＡＳ ＡＤＲ算法都能 较好性能，产生的平均时延和平均队列长 度没有太大差别，当网络负载逐渐增加时， 由于ＭＭＡＳ－ＡＤＲ算法加入了拥塞避免机 制，能够很好的避免拥塞，在平均时延和平 均队列长度上，ＭＭＡＳ—ＡＤＲ算法都要优于 ＡＤＲ算法。 ５结语 本文提出了一种基于蚁群优化的动态 自适应拥塞避免路由算法，算法通过引入 ＭＭＡＳ模型和拥塞预警模型，有效的避免 了传统蚁群算法容易陷入局部最优的缺 点，同时可以对拥塞程度大的链路发出预 警，可以很好的避免链路拥塞。仿真实验表 明，在高负载网络状况下，该算法可以有效 的避免拥塞，在平均时延和平均队列长度 上均要优于ＡＤＲ算法。
