一种基于混合蚂蚁算法的QoS多播路由的方法

摘要

本发明提供一种基于混合蚂蚁算法的QoS多播路由的方法，初期采用遗传算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解。用遗传算法（见右式1）：在规定的迭代次数以内求出最优解或次优解；用蚂蚁算法为信息路由表tabu赋值；比较所有蚂蚁走过的路径，选出F_K最小的作为这次周游的最优路径，由下式计算Δτ_ij（见右式2）：进行信息素的全局更新，只有最优路径上的边信息素增加；输出最优解的路径，直到每个目的节点都已经经过为止。

主权项

1.一种基于混合蚂蚁算法的QoS多播路由的方法，在NS2平台下实现，包括单播和多播路由方法，其特征在于：多播路由的方法是：1)初始化网络节点，给出每条存在的边的时延和费用的值： $D\left(T\right)=\max \underset{(i,j)\in p(s,\mathrm{di})}{\Sigma }d(i,j)<\Delta ,C\left(T\right)=\min \underset{(i,j)\in T}{\Sigma }c(i,j),$式中：T代表多播树，i.j代表节点，Δ为设定值；t＝0；//t是时间计数器，NC＝0；//NC是为循环控制器；2)用下式遗传算法在规定的迭代次数以内求出最优解或次优解： ${\tau }_G={\tau }_C*f_1\left(T\right)={\tau }_C/(\underset{(i,j)\in \mathrm{bestT}}{\Sigma }c(i,j)*\underset{(i,j)\in \mathrm{bestT}}{\Sigma }d(i,j))$式中τ代表某一位置的信息素，G代表i、j等节点构成的拓扑；3)为信息路由表tabu赋值：(A)赋初值s＝0式中s是tabu表的索引，tabu表是用来保存到t时刻为止到达的节点，tabu_k(s)表示在当前路由选择中第k个蚂蚁访问的第s个节点；(B)根据下式按照概率P_ij^k选择下一个节点j； $p_{\mathrm{ij}}^k=\left\{\begin{array}{cc}\frac{{\left[{\tau }_{\mathrm{ij}}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }}{{\Sigma }_{j\in U}{\left[{\tau }_{\mathrm{ij}}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }},& j\in U\\ 0& j\notin U\end{array}\right.$//式中τ_ij(t)指t时刻(i，j)边上信息素的浓度，//U＝{0，1...，n-1}-tabu^k表示第k个蚂蚁下一步可以选择的节点，//α表示信息启发因子，β表示期望启发因子，//η_ij为启发因子，取η_ij＝1/c_ij*d_ij，为下一个节点j以及边(i，j)的时延和费用约束，计算出移到节点j之后的时延和费用的值，与时延约束Δ和费用约束C(T)比较，若超过约束值则重新选择节点，若无满足约束条件的路径可选，蚂蚁死亡；否则移动第k个蚂蚁到节点j；将节点j插入到tabu_k(s)；重复本步直到tabu列表中包括所有目的节点；4)比较所有蚂蚁走过的路径，选出F_K最小的作为这次周游的最优路径；for(k＝1；k＜＝m；++)，其中F_K+＝F_ij；//F_k为路径所有边适应度之和，F_ij为边(i，j)的适度度}，按照下式计算Δτ_ij：//Δτ_ij为最优蚂蚁在这次周游中在(i，j)边上留下的信息素的量，Q为开始时给出的一个常数初值，F_K这里的值为这次周游最佳的路径中所有节点和边的时延和费用的和的积，为 $\underset{(i,j)\in \mathrm{best}}{\Sigma }c{(i,j)}^{*}\underset{(i,j)\in \mathrm{best}}{\Sigma }d(i,j);$5)进行信息素的全局更新，只有最优路径上的边信息素增加；6)输出最优解的路径，直到每个目的节点都已经经过为止。