基于距离完全蚁群算法的多播路由方法

摘要

本发明公开了一种基于距离完全蚁群算法的多播路由方法。首先，为多播路由网络建立距离完全图。然后，基于蚁群算法和Prim算法带随机性地构造多播树。其中，启发式信息的设置使得算法更倾向于选择目标节点。对生成的多播树进行冗余检测和修正并执行局部信息素的更新。最后，当所有蚂蚁都完成解的构造后，执行全局信息素的更新，对历史最优树上的边进行信息素的加强。仿真测试结果，以及与同类型算法的比较显示，本发明的距离完全蚁群算法可以更加快速地解决多播路由问题。

主权项

1、一种基于距离完全蚁群算法的多播路由方法，其特征在于，该方法包括以下步骤：(1)运用Floyd算法建立多播路由网络的距离完全图。(2)初始化算法的各个参数。设定距离完全图每条边上的信息素的初始值为                  τ₀＝1/(|V_G|·T_s)其中T_s是根据确定的冗余检测修正方法得到的树的费用。(3)随机选择一个目标节点让蚂蚁k开始搜索。蚂蚁将会根据状态转移规则以一定的概率选择下一个节点j，其公式如下其中，i是蚂蚁当前所在节点，Θ_k是当前蚂蚁还未曾访问过的节点的集合，q是均匀分布在区间[0，1]中的随机变量，q₀(0≤q₀≤1)是一个参数。τ(i，r)表示连接节点i和r的边上的信息素取值。η(i，r)表示从节点i选择节点r的启发式信息值。选择完成后，对蚂蚁经过的边进行局部信息素的更新。局部信息素的更新将会分两步执行，一个是逻辑边上的信息素更新，另一个是真实边上的信息素更新。蚂蚁k不断重复以上选择过程，直到它经过所有所有的目标节点，从而得到一棵蚂蚁构造的多播树。(4)对蚂蚁构造的多播树执行冗余检测和修正。首先，对访问过的节点执行Prim算法。如果得到的最小生成树的费用低于蚂蚁构造的树，蚂蚁得到的解就会被最小生成树代替。然后，检查无用的中间节点，将那些只有一个输出端的中间节点删除。以上两个步骤不断重复，直到生成的树不能再优化为止。(5)重复步骤(3)和(4)直到所有蚂蚁都完成解的构造。(6)对历史最优的多播树进行全局信息素的更新。在最优生成树的真实边上的信息素如下更新                 τ(i，j)＝(1-ρ)·τ(i，j)+ρ·Δτ其中Δτ＝1/T_best，T_best为最优生成树的总的费用。在最优生成树的逻辑边上的信息素也同样需要更新。假设节点i和j之间选定的真实路径为(a₀，a₁，a₂，...，a_ψ)，其中a₀＝i，a_ψ＝j。ψ为路径中边的数量。则，逻辑边(i，j)上新的信息素等于$\tau (i,j)=\frac{{\Sigma }_{l=0}^{\psi -1}\tau (a_l,a_{l+1})}{\psi }$(7)重复步骤(3)至(6)直到满足算法的终止条件。