基于蚂蚁算法的移动IP路由选择方法

基于蚂蚁算法的移动IP路由选择方法 2 1群 欢 梁杨 ( 530022; 1. 广西壮族自治区无线电监测站 ,广西 南宁 )530022 2. 广西无线电办公室 ,广西 南宁 摘 要 : 利用“信息素 ”来取代网络节点中的路由选择表 ,把移动 IP网络和蚂蚁算法联系起来 ,研究 将蚂蚁算法用于求解移动 IP路由选择当中的最短路径 。实验表明 , 基于蚂蚁算法的移动 IP 路由选择在网络节点数量较多时比基于遗传算法的移动 IP路由选择在查找性能上更忧 。 关键词 : 移动 IP;蚂蚁算法 ;路由选择 ( ) 中图分类号 : TP393 文献标识码 : A 文章编号 : 1003 - 7551 200604 - 0014 - 03 1 引言 在过去十几年尤其是近几年 ,以互联网为代表的信息网络给人们的生活带来了巨大的变化。通过互联网 , 人们能够及时地了解世界各地的新闻 ,方便地获得许多有用信息 , 互联网已经成为很多人日常活动不可或缺 的部分 ,由于目前主要以固定接入方式使用互联网 ,但人们可能经常处在运动中 ,而不是整天呆在固定的办公 室内 ,需要在任何地点任何时候都能获得互联网服务 。大量移动设备的用户希望在移动过程中保持互联网接 入和连续通信 ,获得如固定接入一样的网络服务质量。移动 IP 就是在原来 IP 的基础上为了支持节点移[ 1 ] 动而提出的解决方案 。但移动 IP技术与传统 IP 技术不同 ,传统 IP 技术中 , IP 主机使用固定的 IP 地址和 [ 2 ] Socke t端口号进行相互通信 ,通信期间它们的 IP地址和 Socke t端口号必须保持不变 ,否则通信将无法继续 。 移动主机在两个不同子网之间移动时将产生切换 ,切换会导致移动主机在一定时间之内不能发送和接收数据分组 ,通信对端和移动主机之间的通信暂时会中断。目前已经有很多工作 ,如 : 文献 [ 3 ] [ 4 ] ,研究如何达 到平滑切换或无缝切换 ,取得了很好的效果。在移动网络中 ,网络拓扑变化快 ,要保证用户业务不受影响 ,必须 在最短时间内找到最短路径路由 ,因此我们的研究重点就是查找最短路由 。 移动 IP是目前通信的新方式 ,而在移动 IP通信中 ,其最基本的问题就是 IP 主机在通信期间可能需要移 动 ,因此 IP地址可能会经常发生变化 。而在传统的 IP技术中 , IP地址的变化必将导致 IP通信的中断。因此 , 一方面希望移动的 IP主机保持原来的 IP地址不变 ,以方便其他主机与移动主机的通信 ,另一方面又希望根据 当前所在的网络 ,及时更新 IP地址进行通信。移动 IPv6 就是能够透明地支持 IP主机的移动性 ,在 IP主机移 动的过程中 ,能够始终用原来的 IP地址即归属地址来与移动 IP 主机通信。移动主机在两个不同子网之间移 动时将产生切换 ,如何最大限度保证用户业务在切换中不受影响 ,快速的重新建立连接是关键 ,这涉及查找最 短路由 ,这是一个 N P难问题。解决 N P难问题最好的方法就是采用启发式算法 ,比如 :遗传算法、蚂蚁算法 、模 拟退火法等 。目前有一些工作在研究使用遗传算法解决移动 IP 路由问题 ,并取得了很大的进展 ,但是由于遗 传算法在使用选择、交叉和变异算子上并没有确切的标准 ,易受局部最优解影响 ,所以在解决普遍问题时不能 很好的解决移动 IP在任何情况下的路由选择 。因此我们提出用蚂蚁算法这种根据蚂蚁寻路原理而产生的启 发式算法来解决移动 IP路由选择 。 2 蚂蚁算法 [ 5 ] 蚂蚁算法是意大利学者 M. Do rigo等于 1991年提出的 , 它主要是通过蚂蚁觅食过程群体之间的信息传 ( ) 的概念 ,因此亦称蚂蚁系统 an t system , A S,人工蚂蚁与天然蚂蚁的区别是人工蚂蚁具有记忆功能。 ( )蚂蚁算法有如下特点 : 1 其原理是一种正反馈机制或称增强型学习系统 ,它通过信息素的不断更新达到 ( )最终收敛于最优路径上 ; 2 它是一种通用型随机优化方法 ,但人工蚂蚁决不是对实际蚂蚁的一种简单模拟 , ( )( ) 它融进了人类的智能 ; 3 它是一种分布式的优化方法 ,不仅适合串行计算机 ,而且适合并行计算机 ; 4 它是 一种全局优化的方法 ,不仅可用于求解单目标优化问题 ,而且可用于求解多目标优化问题。 3 基于蚂蚁算法的移动 IP路由选择 3. 1 算法的基本思想 本算法基本思想是通过在源节点周期性地向目的节点发送蚂蚁 ,蚂蚁按照其前方各路径上所存在的分泌 物强度进行路径选择 ;并对其所经过的路径上的分泌物强度进行局部调整 。当蚂蚁运动到目的节点时 ,利用全 局刷新公式刷新路径上所有链路的信息素强度 。经过一段时间后 ,当大部分的蚂蚁都选择同一条路由 ,则说明 找到了全局最优解。 3. 2 算法描述 ( ) 1 为了把移动 IP网络和蚂蚁算法联系起来 ,利用“信息素表 ”来取代网络节点中的路由选择表 ,如表 1 所示。表中的 n 为某节点可以选择的目的节点数 , m 为该节点的相邻节点数。“信息素表 ”给出了以某个节点 为目的节点时选择下一节点的概率 。表中的概率值按照某种规则周期性地刷新 。 表 1 信息素路由选择表 相临节点目的节点 A B K D PPP111 12 1m D PPP221 22 2m D PPP nn1 n2 nm ( ) 2 当一只蚂蚁在某个节点面临多个支路选择的时 , 通过路径转移规则使其能够以较大概率选择信息素 [ 6 ] () 浓度较高的支路 信息素浓度由信息素表中的数值来表示 。路径转移规则定义如下 : ( ) ( ) 设 q?[ 0, 1 ]是一个常数 , Pu, v是蚂蚁 k 在节点 u 选择 v作为下一跳的概率 , Pherom one u, v是链路 0 k ( )u, v的信息素浓度 , N 是蚂蚁未访问过且与相邻的节点集合。设 q是在 [ 0, 1 ]上按照均匀分布产生的一个随 机变量 , 若 q?q则蚂蚁按照最大信息素为原则选择下一跳 , 即 : 0 1, 若 pherom one [ u, v ] = m ax{ pherom one [ u, j ] } , v, j?N ( ) Pu, v= k 0, 其他 若 q > q则按照一定概率来选择下一跳 , 即 : 0 pherom one [ u, v ] / ? pherom one [ u, j ] i, j?N( ) Pu, v= k 0, 其他 ( ) 3 当蚂蚁经过某个链路时 , 链路上的信息素将根据局部调整规则进行调整 。局部调整规则为 : pherom one ( ρ) ΔρΔ[ u, v ] = 1 - pherom one [ u, v ] +。其中 , 0 << 1, 为信息素强度挥发系数 ;为自定义的可调整的参数, 用 来调整信息素浓度 , 指导后续蚂蚁选择局部更优的路径 , 避免陷入局部优化。 ( ) 4 当蚂蚁到达目的节点时 , 利用全局刷新公式刷新路径上所有链路的信息素强度 。全局刷新公式为 : ( ρ) Δ( ) 1 - pherom one [ u, v ] +p, u, v?Rpherom one [ u, v ] = ( ρ) 1 - pherom one [ u, v ], 其他 Δ) ( 其中 ,p = 1 / 链路的传输延迟 ; R 为蚂蚁从源节点到目的节点所经过的路径。 ( )5 蚂蚁按原路返回入口 , 得到最优路由。 15 3. 3 实验和分析 设定移动网络拓扑如图 1 所示 ,初始时共有 9 个网络节点 ,由于 ( ) ( ) 在移动 Ip v6中已经取消了外地代理 FA ,因此只有家乡代理 HA , ()() 移动主机 MH 和组播路由器 MR 。另一方面 ,网络节点会随着实 验的不断增加 ,用于测试算法在动态变化的环境下的运算效率。 根据经验值 ,设定每次放 10 只蚂蚁 ,路径转移规则 q= 0. 6, 信 0 ρΔ 息素强度挥发系数 = 0. 25,p = 0. 2, 各个节点信息素初始化是在路 由表的基础之上加入经验修正值来完成 ,这里不具体列出。我们使 用 C #. N e t编程 ,在 W indow s环境下将基于蚂蚁算法的移动 IP 路由 ()选择算法 简称蚂蚁算法 与文献 [ 7 ]的基于遗传算法的移动 IP优化 ()路由算法 简称为遗传算法 进行模拟比较 ,结果如图 3所示 : 从图 2可以看出 ,基于蚂蚁算法的移动 IP路由选择算法在节点 ( ) 较少 < 45 时其收敛的速度并比不基于遗传算法的移动 IP 优化路 图 1 移动网络拓扑由算法快 ,主要原因在于蚂蚁算法存在初期信息素匮乏的缺点 ,算法 开始阶段需花费一些时间聚集信息素 ,因此 求解速度较慢。但在求 ( 解网络节点很多 > ) 45 的移动 IP路由选择时 ,由于聚集信息素 的时间占整个求解最优路径时间的比重降 低 ,当路径上的信息素逐渐聚集起来以后 , 蚂蚁算法就能快速地求解最优路径的了 ,算 实验比较结果 图 2 法的收敛时间也比基于遗传算法的移动 IP 优化路由算法短。 4 总结 移动主机在不同子网之间移动时将产生切换 ,切换会导致移动主机在一定时间之内不能发送和接收数据分组 ,通信对端和移动主机之间的通信暂时会中断 。目前已经有很多工作在研究如何达到平滑切换 ,取得了一 些成果。我们提出采用蚂蚁算法来解决 ,实验表明 ,我们的算法是有效的。 参 考 文 献 [ 1 ]孙利民 、阚志刚 、郑健平等. 移动 IP技术 [ 1 ]. 北京 :电子工业出版社 , 2003. 23 - 26. [ 2 ] H inden R , D ee ring S. IP ve rsion 6 add re ssing a rch itec tu re [ R ]. R FC 1884 IETF, 1995, 89 - 92. [ 3 ]W ong KD , H ung YW , D u tta A , Young K. Pe rfo rm ance of IP m ic ro2mob ility m anagem en t schem e s u sing ho st ba sed rou ting[ C ]. P ro () ceed ings of the W ire le ss Pe rsona lM u ltim ed ia Comm un ica tion s W PMC2001. 2001. 773. 789. h ttp: / /www. c s. co lum b ia. edu / ,du tta /re sea rch /wpm c. p df. [ 4 ] Camp be ll A T, Gom ez J , Kim S, W an CY, Tu ranyi ZR , V a lko A G. Comp a rison of IP m ic romob ility p ro toco ls[ J ]. IEEE W ire le ss ( ) Comm un ica tion s, 2002, 9 1: 72. 82. [ 5 ] Co lon i A , Do rigo M , M an iezzo V. D istribu ted Op tim iza tion by A n t Co lon ie s[ C ]. P roceed ings 0f 1 st Eu rop ean Conf . A ritific ia l life. Pan s , F rance : E lsevie r , 1991. [ 6 ]W u Q inghong , Zhang J ihu i , Xu X inhe. A n an t co lony a lgo rithm w ith m u ta tion fea tu re s[ J ]. Jou rna l of Comp u te r R e sea rch and D e ( ) ( ) ve lopm en t in Ch ine se, 1999 , 36 10: 1240 - 1245. () ( ) [ 7 ]杨建军 、王勇 、陈抗生. 移动 IP中基于遗传算法的优化路由算法 [ J ]. 浙江大学学报 工学版 , 2004, 38 11 : 45 - 47.