资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
基于理性的蚁群自适应路由北京理工大学北京理工大学 网络信息中心网络信息中心郭郭 巧巧基于移动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算法UPRP RAntNet设计思想蚂蚁选路的改进:AntNet依赖概率表,没有主 动性,可以添加避选规则和直选规则 控制蚂蚁年龄:保证蚂蚁身上的信息足够新, 控制系统内蚂蚁数量 利用先验信息:缩短路由表的收敛时间 结论:注入理性策略,实现基于理性的蚂蚁自 适应路由。基于理性的蚁群自适应路由算法 RAntNet 数据结构 蚂蚁身上的数据结构:记忆栈Ssd(k),记录了经过的 网络节点标识k和从源点到此节点的巡行时间tk 网络节点的数据结构 : 一个巡行时间统计序表Mk :(d, d2, Wd) 一个路由表Tk :向量-距离方式存储概率Pnd RAntNet算法描述 步骤一:路由表初始化 原则:充分利用网络节点局部的先验信息。 说明:是我们提出的路由表先验因子,代表概率增减 量与原概率的权重,|Nk|代表该网络节点的邻居个数 RAntNet算法过程描述 步骤二:前行蚂蚁的发射 原则:各网络节点周期地产生指向各个目的节点的前 行蚂蚁,发向哪个节点的数据报文越多,选择发向该 节点的蚂蚁就越多。 说明:目的节点的选择概率pd通过本地流量模型确定 。其中,fsd表示从源节点s到目的节点d的字节数。RAntNet算法过程描述 步骤三:前行蚂蚁数据收集 随数据包流动的前行蚂蚁在向目的节点旅行过程中, 收集每一个访问节点地址和到此节点的巡行时间,写 入蚂蚁自身携带的记忆栈Ssd(k) RAntNet算法过程描述RAntNet算法过程描述 步骤四:前行蚂蚁选路规则 a) 如果一个可行的邻居节点就是目的节点,蚂蚁将无条件选择这 个邻居节点; b)如果存在以前所有蚂蚁都没走过的邻居节点,则在其中按概率 Pnd的最大值随机地选择; c)如果邻居节点都有以前的蚂蚁访问过,在尽量不选本身蚂蚁走过 的节点的前提下,如果没有发生如微小随机扰动,则按概率Pnd的 最大值随机地选择; d)如果在c)步骤中产生了微小扰动,则蚂蚁不按概率表指示而是随 机选择下一跳节点 说明:为随机扰动阀限。Pnd表示归一化后的路由概率,它考虑 进了相应链路的队列状态。qn表示当前节点k与邻居节点n的链路队 列长度,是链路队列状态与路由概率的权重因子。ln解释为相应链 路的当前队列状态权重因子,显然,等待队列越长的链路,被选 择的概率就越小。 步骤五:前行蚂蚁携带信息的废弃原则 删除回环路由信息 控制蚂蚁生命 说明:其中, 为跳数极限因子表示能够允许的蚂蚁 跳数和网络节点总数间的比例关系。L为蚂蚁生命时间 和H为蚂蚁跳数。Lmax表示蚂蚁的估计寿命极限,N为 网络节点总数。RAntNet算法过程描述RAntNet算法过程描述 步骤六:后行蚂蚁的产生 前行蚂蚁到达目的地后死亡,同时产生一只与 前行蚂蚁结构和内容完全相同的后行蚂蚁。 后行蚂蚁利用记忆栈中的信息,沿前行蚂蚁的 路线原路返回。 后行蚂蚁链路队列的处理优先级更高,目的是 将收集的路由信息快速传播回去,即时地更新 各节点的路由表。 RAntNet算法过程描述 步骤七:路由表和巡行时间统计序表的更新 原则 后行蚂蚁每到达一个节点k,都要更新路由表Tk和巡行时间 统计序表Mk。 更新的内容包括每一个子路径上的经过节点k的所有表项 ,其中 kSkd, kd。 只有当蚂蚁子路经上的巡行时间Okd满足一定置信要求时, 路由表Tk和巡行时间统计序表Mk才能得以更新,更新的内容 包括经过节点k的所有表项,统计性能不好的旅行时间信息 将被丢弃。更新的参考依据如下,其中I是的置信区间。 RAntNet算法过程描述 步骤七:路由表和巡行时间统计表更新方式 路由表的更新:先按照下式,然后做一次强化调整g(x)=xm, m1,然后对路由表做归一化处理。其中,Pfd表示目的地 为d时选择邻居节点f的概率,Pnd表示目的地为d邻居 节点没有选择f而选择其它节点n的概率,r为动态增强因子 。 巡行时间统计序表的更新:如下,参数权重最近的几个样本 对整体均值的影响,|W|为有效采样窗口,|W|5(/), 为有效窗口系数。 网络模拟平台: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%包的延迟 蚂蚁数量 蚂蚁寿命 数据包的正确传送率 多目标优化问题 评价指标测试的流量模型=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,收敛时间为500,运行时间 1000,HS=4,热区开启时间500,HS_MPIA=0.05, 两种算法中=1.0和=1.5,限定AntNet算法和RAntNet 算法中蚂蚁发射间隔分别为0.2和0.24 基于理性的蚁群自适应路由RAntNet 反应式Agent -慎思型Agent添加理性策略,赋予蚂蚁自主决断能力 充分利用先验信息 结论:减少蚂蚁数量,提高了蚂蚁的使用效率 ,提高整体网络性能小节谢 谢!
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号