基于理性的蚁群自适应路由 (郭巧,北京理工大学)

基于理性的蚁群自适应路由 北京理工大学 网络信息中心 郭 巧 基于移动 Agent的路由管理 当前的路由 非自适应的：预先设计、启动下载、过程不变，适合小规模、简单网络 自适应的：随网络拓扑、通信量的变化而变化 矢量路由选择：没有考虑带宽， RIP 链路状态路由选择：主流， OSPF 采用移动 Agent实现路由管理的优点 纯分布式效果，适合负载均衡 智能注入方便灵活，可以达到自适应效果，实现路由管理 蚂蚁觅食机理 基于移动 Agent的路由管理 蚁群自适应路由现状 ARS： 调节正反馈、负反馈启发因子 ARH和 ARHnr ： 用于移动自组网 ABC： 解决电信线路交换网络的负载 ASGA： 遗传算法特征，解决点到点、点到多点的线路交换网络的路由问题 SynthECA： ASGA延伸到故障诊断 AntNet： AntNet-CL和 AntNet-CO 结论：刚刚起步，前景光明 基于移动 Agent的路由管理 主要思想 两类网络蚂蚁，前行蚂蚁和后行蚂蚁。 各网络节点以一定间隔按照本节点的网络状况随机地选择目的节点发送前行蚂蚁； 前行蚂蚁与数据包处在相同优先级的转发队列中，用于收集节点间的延迟； 到达目的节点后，前行蚂蚁死亡，同时产生一个结构内容完全相同的后行蚂蚁，后行蚂蚁按前行蚂蚁的路线原路返回； 处理后行蚂蚁的队列优先级较高，能够快速的将前行蚂蚁收集的网络状态信息返回给各网络节点； 网络节点通过后行蚂蚁携带网络状态信息计算路由概率表，增大较好路径上的概率，减少较差路径的选择概率，指示数据选择下一跳的节点。 大量随机分布的前行蚂蚁和后行蚂蚁共同合作，完成总体目标，实现网络的自适应路由。 AntNet算法 网络性能比较 (摘自 Ginanni Di Caro 2002,5 博士论文 ) AntNet算法 UP RP RAntNet设计思想 蚂蚁选路的改进： AntNet依赖概率表 ,没有主动性，可以添加避选规则和直选规则 控制蚂蚁年龄：保证蚂蚁身上的信息足够新，控制系统内蚂蚁数量 利用先验信息：缩短路由表的收敛时间 结论：注入理性策略，实现基于理性的蚂蚁自适应路由。 基于理性的蚁群自适应路由算法RAntNet 数据结构 蚂蚁身上的数据结构： 记忆栈 Ss d(k)， 记录了经过的网络节点标识 k和从源点到此节点的巡行时间 tk 网络节点的数据结构 ： 一个巡行时间统计序表 Mk ： (d, d2, Wd) 一个路由表 Tk ： 向量 -距离方式存储概率 Pnd RAntNet算法描述 1 , 1 , kndnP d N 步骤一： 路由表初始化 原则：充分利用网络节点局部的先验信息。 说明： 是我们提出的路由表先验因子，代表概率增减量与原概率的权重， |Nk|代表该网络节点的邻居个数 RAntNet算法过程描述 2211, , ,1, , , , 10 , , , , 11,kkk kkkndk kkkkkkn d n dn d n dPn d n dnd 步骤二： 前行蚂蚁的发射 原则：各网络节点周期地产生指向各个目的节点的前行蚂蚁，发向哪个节点的数据报文越多，选择发向该节点的蚂蚁就越多。 说明：目的节点的选择概率 pd通过本地流量模型确定。其中， fsd表示从源节点 s到目的节点 d的字节数。 RAntNet算法过程描述 1Nd s d s ddp f f 步骤三： 前行蚂蚁数据收集 随数据包流动的前行蚂蚁在向目的节点旅行过程中，收集每一个访问节点地址和到此节点的巡行时间，写入蚂蚁自身携带的记忆栈 Ss d(k) RAntNet算法过程描述 RAntNet算法过程描述 步骤四： 前行蚂蚁选路规则 a) 如果一个可行的邻居节点就是目的节点，蚂蚁将无条件选择这个邻居节点； b)如果存在以前所有蚂蚁都没走过的邻居节点，则在其中按概率Pnd的最大值随机地选择； c)如果邻居节点都有以前的蚂蚁访问过，在尽量不选本身蚂蚁走过的节点的前提下，如果没有发生如微小随机扰动，则按概率 Pnd的最大值随机地选择； d)如果在 c)步骤中产生了微小扰动，则蚂蚁不按概率表指示而是随机选择下一跳节点 说明： 为随机扰动阀限。 Pnd表示归一化后的路由概率，它考虑进了相应链路的队列状态。 qn表示当前节点 k与邻居节点 n的链路队列长度，是链路队列状态与路由概率的权重因子。 ln解释为相应链路的当前队列状态权重因子，显然，等待队列越长的链路，被选择的概率就越小。 ( 0 . 0 , 1 . 0 )u i f o r m 1 1 ( 1 )1kn d n d n kn n nnP P ll q q 步骤五：前行蚂蚁携带信息的废弃原则 删除回环路由信息 控制蚂蚁生命 说明： 其中， 为跳数极限因子表示能够允许的蚂蚁跳数和网络节点总数间的比例关系。 L为 蚂蚁生命时间和 H为蚂蚁 跳数。 Lmax表示蚂蚁的估计寿命极限， N为网络节点总数。 RAntNet算法过程描述 CL m a xLLHN RAntNet算法过程描述 步骤六：后行蚂蚁的产生 前行蚂蚁到达目的地后死亡，同时产生一只与前行蚂蚁结构和内容完全相同的后行蚂蚁。 后行蚂蚁利用记忆栈中的信息，沿前行蚂蚁的路线原路返回。 后行蚂蚁链路队列的处理优先级更高，目的是将收集的路由信息快速传播回去，即时地更新各节点的路由表。 RAntNet算法过程描述 步骤七：路由表和巡行时间统计序表的更新原则 后行蚂蚁每到达一个节点 k，都要更新路由表 Tk和巡行时间统计序表 Mk。 更新的内容包括每一个子路径上的经过节点 k的所有表项，其中 k Sk d, k d。 只有当蚂蚁子路经上的巡行时间 Ok d满足一定置信要求时，路由表 Tk和巡行时间统计序表 Mk才能得以更新，更新的内容包括经过节点 k的所有表项，统计性能不好的旅行时间信息将被丢弃。更新的参考依据如下，其中 I是 的置信区间。 ),( IO dk RAntNet算法过程描述 步骤七： 路由表和巡行时间统计表更新方式 路由表的更新 :先按照下式，然后做一次强化调整 g(x)=xm, m1，然后对路由表做归一化处理。其中， Pfd表示目的地为d时选择邻居节点 f的概率， Pnd表示目的地为 d邻居节点没有选择 f而选择其它节点 n的概率， r为动态增强因子。 2 2 2 2()( ( ) )d d k d dd d k d d d 巡行时间统计序表的更新 :如下，参数 权重最近的几个样本对整体均值的影响， |W|为有效采样窗口， |W| 5( / ),为有效窗口系数。 ( 1 ),f d f d f dn d n d n d kP P r PP P r P n n f 1s u p i n f12s u p i n f i n fi n f s u p( ), ( ) 1 e x p(1 )( ) ( )1,(1 )kb e s tb e s ts r ar s xsxIIWr c cT I I T II W IW 网络模拟平台： OMNet+ NS; OPENET;PARSEC;NetSim+;OMNet+ RAntNet算法实现 模型总体设计 AG(AntGenerator) AS(AntSink) AN(AntNest) DG(DataGenerator) DS(DataSink) RT(Router) ST(Statistics) GN(GenericNetworkNode) AntNeworkNode SpecialTopology Network 模块间的关联关系 采用 C+类独立构成 Statistics类和 Ant类采用指针方式为其它类共享调用 Statistics类提供统计函数库 Ant类负责构建蚂蚁的基本属性和行为能力 节点内的其它模块类之间采用消息驱动 RAntNet算法实现 日本电信主干网 NTTNet(6.5, 3.8, 57) 测试对象 57个节点 162条双向链路 带宽 6Mbit/sec 延迟大约在 1到5msec间不等 6.5跳数表征的最短路径均值 3.8表示以跳数表征的最短路径方差 吞吐率 置信度为 90%包的延迟 蚂蚁数量 蚂蚁寿命 数据包的正确传送率 多目标优化问题 评价指标 1 2 9 0 3 411 ( 0 1 , 1 , 2 , . . . , , 4 )P V A H P D P TniiiE k E k E k E kk k i n n m i nm a x m i nm a xm a x m i n, ( ),EEE i f B i g g e r I s B e t t e rEEEEE o t h e r w i s eEE 9 0 9 0P D P DP T P TP V P VA H A HECECECEC 测试的流量模型 =0.15， 有效窗口系数 =0.3， 意味着有效观测窗口为最近的 10个数据；数据置信水平大约在 0.95即 (1- )-1/2=1.72， m=1.2， c1=0.85， c2= 0.15， =0.45， a=2.0， 健康回环百分率 =30%。 建立拓扑的预留时间为 15 simsec； Hello消息和 HelloReply消息的响应超时都为 0.03simsec， 拓扑建立的重试次数为 5次 ， 模拟生成的报文长度为 512， 模拟生成的会话大小为 2130000；路由器的队列长度为 1000。 所有测试都是采用 OMNet+的 seedtool生成间隔 100000的10个均好性随机种子 ， 每次试验更换随机种子后独立运行 ，求 10次的平均值 。 我们将逐步添加改进策略后的算法与 AntNet基本算法结果作比较 ， 一方面是为验证 RAntNet的有效性 ， 另一方面也是为优选 RAntNet的参数提供依据 。 测试参数条件 试验结果与分析 添加 路由表先验因子 1.5 测试条件： AntNet和 RAntNet取 1.0， MPIA=0.005, MSIA=2.7，热区点取节点 4， HS_MPIA=0.005， 取 0.001 修改蚂蚁选路：直选规则和避选规则 试验结果与分析 RP测试条件 MPIA=0.003, MSIA=3.0，