·352· 智能系统学报 第3卷 只有时延均值小于容许累积时延D。的节点才有可 按原路返回到源节点s并根据所述的信息更新规则 能被选中.然后，对上述比较得到的数据包路由表通 对沿途各节点的信息进行更新.如果后向蚂蚁不能按 过式(15)的指数函数进行重映射，并在映射后重新 原路返回如出现链路故障等)，则将该蚂蚁丢弃 进行规一化处理。 5)对于被选择的链路，修正其剩余带宽，以实 g(x)=x,B≥1 (15) 现瓶颈链路上的多路径互不相交 式中：B为强化系数，B的值决定了数据包选择单路 6)对于多个多路径，上述步骤重复进行，直到 径路由还是多路径路由.B>1时，指数函数g(x)增 多路径集的个数达到一定的阈值m或满足要求的 强了高概率值部分，减弱了低概率值部分，避免了数 相邻节点集合为空」 据包选择概率过低的链路.B值较大时B》1).表示 7)每个网络节点得到一张具有多路径信息和 数据包仅能选择单一路径进行路由，B=1表示可以 选择下一节点的概率值的路由表，当有呼叫请求接 选择多路径路由，即使概率较低的链路也有可能被 入时，将对数据包选择一个路径并在该路径路由表 选中 中根据概率值随机地选择相邻节点进行转发」 为了改进网络性能，实现不相交多路径路由，在 3算法分析与模拟 此引入链路剩余带宽和在瓶颈链路上互不相交的多 路径的概念.对于AnNet算法选出的从源节点s到 31复杂度分析 达目的节点d的一条路径，将对构成该路径的每个 对于从给定的源节点到目的节点前行的单个蚂 链路的剩余带宽进行调整.为简单起见，在当前节点 蚁，由于前行时需要对每个节点的相邻节点计算转 k,可以在每次按概率表选路之后，通过式对节点k移概率，设前行蚂蚁的最大跳数为M,最坏情况下需 和相邻节点v之间的链路的剩余带宽进行修正.修要在所有M个节点上进行搜索和计算，其计算复杂 正之后，再根据式(6)计算一个新的满足带宽约束 度为OMNk).单个后行蚂蚁由于需要更新每个 要求的邻居集合N',这样便实现了瓶颈链路上的 节点的相邻节点路由表，最坏情况下也需要在所有 多路径互不相交： M个节点上进行计算和更新，其计算复杂度也是 bandwidth(k.v)=bandw idth(k v)-Bo O(M N). (16 显然，对于从给定的源节点到目的节点前行的 以上过程在每次执行AnNet寻路算法之前执 m个前行或后行蚂蚁，本算法最坏情况下的计算复 行一次，直到多路径集的个数达到一定的阈值或满 杂度为O(mM IN&).Dijkstra最短路径算法计算一 足要求的相邻节点集合为空 条路径的复杂度是OL+NbgW),其中L是网络中 25算法描述 链路的个数，N是网络中节点的个数.可以看出，当 基于AnNet的QoS路由算法的详细过程为 M和W.与节点个数N相比较小时，基于AnNet的 1)首先对路由表初始化，并以一定的间隔，从 路由算法和Dijkstra最短路径算法在计算复杂度上 每个节点s作为源节点)，随机选择一目的节点d, 是相当的 发送一个前行蚂蚁 32模拟结果 2)前行蚂蚁按节点选择规则选择下一节点，当 为了对基于AnNet的QoS路由算法的性能进 蚂蚁从节点到达下一节点时，它把链路1(i的 行分析，本文对算法进行了模拟实验.模拟实验首先 时延保存到记忆栈中，并把节点加入其节点集合 产生一个随机网络G。N),该网络由N个节点和以 中，节点跳数加1 概率p选择的独立链路构成.链路权重表示时延，统 3)如果前向蚂蚁在寻路过程中出现环路，则把 一分布在0,11，单位为ms每个链路的带宽容量为 该部分删除，并从出现环路的开始节点开始进行搜 8 Mbps 索.为防止前向蚂蚁无休止地进行循环，根据网络规 每次模拟都定义节点1为源节点，节点N为目 模设置一个蚂蚁的最大跳数，如果蚂蚁经过的跳数 的节点，并将模拟运行结果和Dijkstra最短路径算 大于这个最大值，则蚂蚁死亡，丢弃该蚂蚁 法进行比较.模拟时间分为训练和测试2部分，训练 4)前行蚂蚁到达目的节点d时，将产生一个后 时仅产生和传输网络蚂蚁，测试时网络蚂蚁和数据 行蚂蚁，并拷贝相应的信息到后行蚂蚁中，后行蚂蚁 包同时产生.数据包产生过程服从泊松分布，数据包 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net只有时延均值小于容许累积时延 D0 的节点才有可 能被选中. 然后 ,对上述比较得到的数据包路由表通 过式 (15)的指数函数进行重映射 ,并在映射后重新 进行规一化处理. g ( x) = x β ,β≥ 1. (15) 式中 :β为强化系数 ,β的值决定了数据包选择单路 径路由还是多路径路由.β> 1时 ,指数函数 g ( x)增 强了高概率值部分 ,减弱了低概率值部分 ,避免了数 据包选择概率过低的链路.β值较大时 (βµ 1) ,表示 数据包仅能选择单一路径进行路由 ,β= 1表示可以 选择多路径路由 ,即使概率较低的链路也有可能被 选中. 为了改进网络性能 ,实现不相交多路径路由 ,在 此引入链路剩余带宽和在瓶颈链路上互不相交的多 路径的概念. 对于 AntNet算法选出的从源节点 s到 达目的节点 d的一条路径 ,将对构成该路径的每个 链路的剩余带宽进行调整. 为简单起见 ,在当前节点 k,可以在每次按概率表选路之后 ,通过式对节点 k 和相邻节点 v之间的链路的剩余带宽进行修正. 修 正之后 ,再根据式 ( 6)计算一个新的满足带宽约束 要求的邻居集合 N ′k ,这样便实现了瓶颈链路上的 多路径互不相交 : bandwidth ( k, v) = bandwidth ( k, v) - B0 . (16) 以上过程在每次执行 AntNet寻路算法之前执 行一次 ,直到多路径集的个数达到一定的阈值或满 足要求的相邻节点集合为空. 2. 5 算法描述 基于 AntNet的 QoS路由算法的详细过程为 1) 首先对路由表初始化 ,并以一定的间隔 ,从 每个节点 s(作为源节点 ) ,随机选择一目的节点 d, 发送一个前行蚂蚁. 2) 前行蚂蚁按节点选择规则选择下一节点 ,当 蚂蚁从节点 i到达下一节点 j时 ,它把链路 l( i, j)的 时延保存到记忆栈中 ,并把节点 i加入其节点集合 中 ,节点跳数加 1. 3) 如果前向蚂蚁在寻路过程中出现环路 ,则把 该部分删除 ,并从出现环路的开始节点开始进行搜 索. 为防止前向蚂蚁无休止地进行循环 ,根据网络规 模设置一个蚂蚁的最大跳数 ,如果蚂蚁经过的跳数 大于这个最大值 ,则蚂蚁死亡 ,丢弃该蚂蚁. 4) 前行蚂蚁到达目的节点 d时,将产生一个后 行蚂蚁,并拷贝相应的信息到后行蚂蚁中 ,后行蚂蚁 按原路返回到源节点 s,并根据所述的信息更新规则 对沿途各节点的信息进行更新. 如果后向蚂蚁不能按 原路返回 (如出现链路故障等 ) ,则将该蚂蚁丢弃. 5) 对于被选择的链路 ,修正其剩余带宽 ,以实 现瓶颈链路上的多路径互不相交. 6) 对于多个多路径 ,上述步骤重复进行 ,直到 多路径集的个数达到一定的阈值 m 或满足要求的 相邻节点集合为空. 7) 每个网络节点得到一张具有多路径信息和 选择下一节点的概率值的路由表 ,当有呼叫请求接 入时 ,将对数据包选择一个路径并在该路径路由表 中根据概率值随机地选择相邻节点进行转发. 3 算法分析与模拟 3. 1 复杂度分析 对于从给定的源节点到目的节点前行的单个蚂 蚁 ,由于前行时需要对每个节点的相邻节点计算转 移概率 ,设前行蚂蚁的最大跳数为 M ,最坏情况下需 要在所有 M 个节点上进行搜索和计算 ,其计算复杂 度为 O (M |Nk | ). 单个后行蚂蚁由于需要更新每个 节点的相邻节点路由表 ,最坏情况下也需要在所有 M 个节点上进行计算和更新 , 其计算复杂度也是 O (M |Nk | ). 显然 ,对于从给定的源节点到目的节点前行的 m 个前行或后行蚂蚁 ,本算法最坏情况下的计算复 杂度为 O (mM |Nk | ). D ijkstra最短路径算法计算一 条路径的复杂度是 O (L +N logN ) ,其中 L 是网络中 链路的个数 , N 是网络中节点的个数. 可以看出 ,当 M 和 |Nk |与节点个数 N 相比较小时 ,基于 AntNet的 路由算法和 D ijkstra最短路径算法在计算复杂度上 是相当的. 3. 2 模拟结果 为了对基于 AntNet的 QoS路由算法的性能进 行分析 ,本文对算法进行了模拟实验. 模拟实验首先 产生一个随机网络 Gp (N ) ,该网络由 N 个节点和以 概率 p选择的独立链路构成. 链路权重表示时延 ,统 一分布在 (0, 1 ],单位为 m s,每个链路的带宽容量为 8 Mbp s. 每次模拟都定义节点 1为源节点 ,节点 N 为目 的节点 ,并将模拟运行结果和 D ijkstra最短路径算 法进行比较. 模拟时间分为训练和测试 2部分 ,训练 时仅产生和传输网络蚂蚁 ,测试时网络蚂蚁和数据 包同时产生. 数据包产生过程服从泊松分布 ,数据包 · 253 · 智 能 系 统 学 报 第 3卷