《基于理性的蚁群自适应路由》由会员分享，可在线阅读，更多相关《基于理性的蚁群自适应路由（26页珍藏版）》请在金锄头文库上搜索。
1、基于理性的蚁群自适应路由北京理工大学北京理工大学 网络信息中心网络信息中心郭郭 巧巧基于移动Agent的路由管理 当前的路由 非自适应的：预先设计、启动下载、过程不变，适合 小规模、简单网络 自适应的：随网络拓扑、通信量的变化而变化 矢量路由选择：没有考虑带宽，RIP 链路状态路由选择：主流，OSPF 采用移动Agent实现路由管理的优点 纯分布式效果，适合负载均衡 智能注入方便灵活，可以达到自适应效果，实现路由 管理 蚂蚁觅食机理基于移动Agent的路由管理 蚁群自适应路由现状 ARS：调节正反馈、负反馈启发因子 ARH和ARHnr ：用于移动自组网 ABC：解决电信线路交换网络的负载 AS
2、GA：遗传算法特征，解决点到点、点到多点的线路 交换网络的路由问题 SynthECA：ASGA延伸到故障诊断 AntNet：AntNet-CL和AntNet-CO 结论：刚刚起步，前景光明 基于移动Agent的路由管理 主要思想 两类网络蚂蚁，前行蚂蚁和后行蚂蚁。 各网络节点以一定间隔按照本节点的网络状况随机地选择目的节 点发送前行蚂蚁； 前行蚂蚁与数据包处在相同优先级的转发队列中，用于收集节点 间的延迟； 到达目的节点后，前行蚂蚁死亡，同时产生一个结构内容完全相 同的后行蚂蚁，后行蚂蚁按前行蚂蚁的路线原路返回； 处理后行蚂蚁的队列优先级较高，能够快速的将前行蚂蚁收集的 网络状态信息返回给各网
3、络节点； 网络节点通过后行蚂蚁携带网络状态信息计算路由概率表，增大 较好路径上的概率，减少较差路径的选择概率，指示数据选择下 一跳的节点。 大量随机分布的前行蚂蚁和后行蚂蚁共同合作，完成总体目标， 实现网络的自适应路由。 AntNet算法 网络性能比较(摘自Ginanni Di Caro 2002,5 博士论文)AntNet算法UPRP RAntNet设计思想蚂蚁选路的改进：AntNet依赖概率表,没有主 动性，可以添加避选规则和直选规则 控制蚂蚁年龄：保证蚂蚁身上的信息足够新， 控制系统内蚂蚁数量 利用先验信息：缩短路由表的收敛时间 结论：注入理性策略，实现基于理性的蚂蚁自 适应路由。基于理
4、性的蚁群自适应路由算法 RAntNet 数据结构 蚂蚁身上的数据结构：记忆栈Ssd(k)，记录了经过的 网络节点标识k和从源点到此节点的巡行时间tk 网络节点的数据结构 ： 一个巡行时间统计序表Mk ：(d, d2, Wd) 一个路由表Tk ：向量-距离方式存储概率Pnd RAntNet算法描述 步骤一：路由表初始化 原则：充分利用网络节点局部的先验信息。 说明：是我们提出的路由表先验因子，代表概率增减 量与原概率的权重，|Nk|代表该网络节点的邻居个数 RAntNet算法过程描述 步骤二：前行蚂蚁的发射 原则：各网络节点周期地产生指向各个目的节点的前 行蚂蚁，发向哪个节点的数据报文越多，选择
5、发向该 节点的蚂蚁就越多。 说明：目的节点的选择概率pd通过本地流量模型确定 。其中，fsd表示从源节点s到目的节点d的字节数。RAntNet算法过程描述 步骤三：前行蚂蚁数据收集 随数据包流动的前行蚂蚁在向目的节点旅行过程中， 收集每一个访问节点地址和到此节点的巡行时间，写 入蚂蚁自身携带的记忆栈Ssd(k) RAntNet算法过程描述RAntNet算法过程描述 步骤四：前行蚂蚁选路规则 a) 如果一个可行的邻居节点就是目的节点，蚂蚁将无条件选择这 个邻居节点； b)如果存在以前所有蚂蚁都没走过的邻居节点，则在其中按概率 Pnd的最大值随机地选择； c)如果邻居节点都有以前的蚂蚁访问过，在尽
6、量不选本身蚂蚁走过 的节点的前提下，如果没有发生如微小随机扰动，则按概率Pnd的 最大值随机地选择； d)如果在c)步骤中产生了微小扰动，则蚂蚁不按概率表指示而是随 机选择下一跳节点 说明：为随机扰动阀限。Pnd表示归一化后的路由概率，它考虑 进了相应链路的队列状态。qn表示当前节点k与邻居节点n的链路队 列长度，是链路队列状态与路由概率的权重因子。ln解释为相应链 路的当前队列状态权重因子，显然，等待队列越长的链路，被选 择的概率就越小。 步骤五：前行蚂蚁携带信息的废弃原则 删除回环路由信息 控制蚂蚁生命 说明：其中， 为跳数极限因子表示能够允许的蚂蚁 跳数和网络节点总数间的比例关系。L为蚂
7、蚁生命时间 和H为蚂蚁跳数。Lmax表示蚂蚁的估计寿命极限，N为 网络节点总数。RAntNet算法过程描述RAntNet算法过程描述 步骤六：后行蚂蚁的产生 前行蚂蚁到达目的地后死亡，同时产生一只与 前行蚂蚁结构和内容完全相同的后行蚂蚁。 后行蚂蚁利用记忆栈中的信息，沿前行蚂蚁的 路线原路返回。 后行蚂蚁链路队列的处理优先级更高，目的是 将收集的路由信息快速传播回去，即时地更新 各节点的路由表。 RAntNet算法过程描述 步骤七：路由表和巡行时间统计序表的更新 原则 后行蚂蚁每到达一个节点k，都要更新路由表Tk和巡行时间 统计序表Mk。 更新的内容包括每一个子路径上的经过节点k的所有表项 ，
8、其中 kSkd, kd。 只有当蚂蚁子路经上的巡行时间Okd满足一定置信要求时， 路由表Tk和巡行时间统计序表Mk才能得以更新，更新的内容 包括经过节点k的所有表项，统计性能不好的旅行时间信息 将被丢弃。更新的参考依据如下，其中I是的置信区间。 RAntNet算法过程描述 步骤七：路由表和巡行时间统计表更新方式 路由表的更新:先按照下式，然后做一次强化调整g(x)=xm, m1，然后对路由表做归一化处理。其中，Pfd表示目的地 为d时选择邻居节点f的概率，Pnd表示目的地为d邻居 节点没有选择f而选择其它节点n的概率，r为动态增强因子 。 巡行时间统计序表的更新:如下，参数权重最近的几个样本
9、对整体均值的影响，|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类采用
10、指针方式为其它类共享调用 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即
11、(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基本算法结果 作比较，一方面是为验证R
12、AntNet的有效性，另一方面也 是为优选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添加理性策略，赋予蚂蚁自主决断能力 充分利用先验信息 结论：减少蚂蚁数量，提高了蚂蚁的使用效率 ，提高整体网络性能小节谢 谢！
