·350· 智能系统学报 第3卷 的更新 态数组存储了本地的流量统计，描绘了当前节点到 把通信网看成一个无向加权连通图GN,L), 其他目的节点的本地自适应拥塞状态模型.以节点 其中N为节点集合，L为图中连接2个节点的链路 k为例，Stat()=M.表示从当前节点k所观察到的 集合.不失一般性，假设在任意2个节点之间至多存 整个网络各个节点距离的统计模型.AnNet算法的 在一条链路，每条链路1∈L和一些QoS度量相关， M采用了时延统计表，它由三元组a,o,W)组 这些度量包括：时延、可用带宽、包丢失率、费用和抖 成.。和o表示了从当前节点到目的节点d所经 动等.简化起见，这里仅考虑带宽和时延约束 历的时间的均值和方差，W,是一个移动观察窗口， 为了利用蚂蚁进行路由选择，网络中每个节点 窗口大小表示了最近经过节点k的、以d为目的节 的路由表用信息素(phe romone)表来代替，表中的信 点的蚂蚁个数，用来计算行程的最少时间.时延统计 息素浓度是以概率值的形式表示.蚂蚁在一条路径 表M.的计算非常复杂，涉及的参数较多，本算法对 上前进时沿途释放信息素，在此相当于对节点信息 其进行了改进，引入压缩和强化机制，简化利用时延 素表中的相应条目进行更新.时延小、拥塞程度低的 来调整信息素的计算方法 链路应该具有更大的概率值， 假设P表示在当前节点k以d为目的节点时 2 AnNet的多路径QoS路由算法 选择下一个节点的概率，再假设N.为节点k的相 21路由表的初始化 邻节点集合，即Nk={neighbors(k},那么有 在AnNet算法中没有具体定义路由表的初始 ￡P=L.dE/LN☑ 1) 化方法.为了能够充分反映网络的初始拓扑状况，考 虑到要充分利用网络节点局部的信息，本算法按照 对于任意一条从源节点s到目的节点d的路径 式(4)对路由表进行初始化： p,设B。为从源节点s到目的节点d路由一个业务 1 P(N:-1) 流所需的最小带宽，D。为所容许的最大时延，则多 1N2 id∈Nk,j=t IN& 路径QoS路由可以表示为在源节点s到目的节点d 1 之间寻找多个路径，且每条路径满足： Pa 1N11N2 id∈N,j≠dINk|>上： m in/bandw idth(W,I∈p(sd)}≥Bo, (2 1 ∑delay(U≤Do j∈Nk,deNk 3) I Ne l' IEpis d) 12数据结构 (4) 为了实现寻路和更新路由表信息素表)，把蚂 式4)根据目的节点的不同类型邻接点、非邻接 蚁分成2类，一类是收集节点间时延和路径状态信 点而设置不同的初始概率值.其中P是提出的路由表 息的前行蚂蚁Fm,一类为进行路由表和状态信息 先验因子，代表概率增减量与原概率的权重，可以通过 更新的后行蚂蚁Bm2类蚂蚁具有相同的数据结 实验确定：W.代表该网络节点的邻居个数， 构，可以保存节点时延等信息， 22节点选择规则 蚂蚁的数据结构定义为一个数据表和一个堆栈 在基本的AnNet算法中，前行蚂蚁选择下一节 S(k),数据表包含了蚂蚁标识、源节点、目的节点 点是根据路由表（信息素表）中的概率值随机选择 以及经过的跳数，堆栈S()包含了依次经过的网 的，而数据流中数据包选择下一节点则采用比较本 络节点标识k从源节点s到此节点经历的时延 节点k的信息素表来选择下一个可能节点？即按 以及次序关系.蚂蚁F前行到节点k其S(k)包 式(5)选择概率值最大的相邻节点进行转发 含信息的形式为 p(k.v)=maxp (5) {(i,,(正，2，…(， 式中：d∈l,NJ,Nk=/neighbors(). 网络节点的数据结构主要由2个表构成：路由 这种设计首先没有考虑到带宽、费用等其他的 表R和节点状态数组Stat(1),Sat(2), Qo$约束，其次当系统稳定时，由于蚁群算法的正反 SatN).为了实现多路径路由，本算法对路由表进 馈自寻优能力，若网络中各链路时延不变，则经过一 行了改进，增加了一个路径标识B(i=1,2,m, 段时间后，几乎所有的蚂蚁都会选择相同的路径.当 表示从源节点s到目的节点d的多个路径.节点状 业务流量较大的时候就会发生拥塞.为了防止这种 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net的更新. 把通信网看成一个无向加权连通图 G (N, L ) , 其中 N 为节点集合 , L 为图中连接 2个节点的链路 集合. 不失一般性 ,假设在任意 2个节点之间至多存 在一条链路 ,每条链路 l∈L 和一些 QoS度量相关 , 这些度量包括 :时延、可用带宽、包丢失率、费用和抖 动等. 简化起见 ,这里仅考虑带宽和时延约束. 为了利用蚂蚁进行路由选择 ,网络中每个节点 的路由表用信息素 (pheromone)表来代替 ,表中的信 息素浓度是以概率值的形式表示. 蚂蚁在一条路径 上前进时沿途释放信息素 ,在此相当于对节点信息 素表中的相应条目进行更新. 时延小、拥塞程度低的 链路应该具有更大的概率值. 假设 Pjd表示在当前节点 k以 d为目的节点时 选择下一个节点 j的概率 ,再假设 Nk 为节点 k的相 邻节点集合 ,即 Nk = { neighbors( k) },那么有 j∈∑N k Pjd = 1, d ∈ [1, N ]. (1) 对于任意一条从源节点 s到目的节点 d的路径 p,设 B0 为从源节点 s到目的节点 d路由一个业务 流所需的最小带宽 , D0 为所容许的最大时延 ,则多 路径 QoS路由可以表示为在源节点 s到目的节点 d 之间寻找多个路径 ,且每条路径满足 : m in{ bandwidth ( l) , l ∈ p (s, d) } ≥B0 , (2) l∈∑p (s, d) delay( l) ≤D0 . (3) 1. 2 数据结构 为了实现寻路和更新路由表 (信息素表 ) ,把蚂 蚁分成 2类 ,一类是收集节点间时延和路径状态信 息的前行蚂蚁 Fant ,一类为进行路由表和状态信息 更新的后行蚂蚁 Bant . 2类蚂蚁具有相同的数据结 构 ,可以保存节点、时延等信息. 蚂蚁的数据结构定义为一个数据表和一个堆栈 Ss2d ( k) ,数据表包含了蚂蚁标识、源节点、目的节点 以及经过的跳数 ,堆栈 Ss2d ( k)包含了依次经过的网 络节点标识 k、从源节点 s到此节点经历的时延 tk 以及次序关系. 蚂蚁 Fant前行到节点 k,其 Ss2d ( k)包 含信息的形式为 { ( j1 , tj1 ) , ( j2 , tj2 ) , …, ( jk , tj k ) }. 网络节点的数据结构主要由 2个表构成 :路由 表 Rk 和节点状态数组 { Stat ( 1 ) , Stat ( 2 ) , …, Stat(N ) }. 为了实现多路径路由 ,本算法对路由表进 行了改进 ,增加了一个路径标识 pi ( i = 1, 2, …, m ) , 表示从源节点 s到目的节点 d的多个路径. 节点状 态数组存储了本地的流量统计 ,描绘了当前节点到 其他目的节点的本地自适应拥塞状态模型. 以节点 k为例 , Stat( k) =M k 表示从当前节点 k所观察到的 整个网络各个节点距离的统计模型. AntNet算法的 M k 采用了时延统计表 ,它由三元组 (μd , σ2 d , W d )组 成.μd 和 σ2 d 表示了从当前节点到目的节点 d所经 历的时间的均值和方差 , W d 是一个移动观察窗口 , 窗口大小表示了最近经过节点 k的、以 d为目的节 点的蚂蚁个数 ,用来计算行程的最少时间. 时延统计 表 M k 的计算非常复杂 ,涉及的参数较多 ,本算法对 其进行了改进 ,引入压缩和强化机制 ,简化利用时延 来调整信息素的计算方法. 2 AntNet的多路径 QoS路由算法 2. 1 路由表的初始化 在 AntNet算法中没有具体定义路由表的初始 化方法. 为了能够充分反映网络的初始拓扑状况 ,考 虑到要充分利用网络节点局部的信息 ,本算法按照 式 (4)对路由表进行初始化 : pjd = 1 | Nk | + ρ(| Nk | - 1) | Nk | 2 , j, d ∈Nk , j = d; 1 | Nk | - ρ | Nk | 2 , j, d ∈Nk , j≠ d, | Nk | > 1; 1 | Nk | ; j∈Nk , d Nk . (4) 式 (4)根据目的节点的不同类型 (邻接点、非邻接 点 )而设置不同的初始概率值. 其中ρ是提出的路由表 先验因子,代表概率增减量与原概率的权重,可以通过 实验确定; |Nk |代表该网络节点的邻居个数. 2. 2 节点选择规则 在基本的 AntNet算法中 ,前行蚂蚁选择下一节 点是根据路由表 (信息素表 )中的概率值随机选择 的 ,而数据流中数据包选择下一节点则采用比较本 节点 k的信息素表来选择下一个可能节点 v,即按 式 (5)选择概率值最大的相邻节点进行转发. p ( k, v) = max j∈N k Pjd . (5) 式中 : d∈[ 1, N ], Nk = { neighbors( k) }. 这种设计首先没有考虑到带宽、费用等其他的 QoS约束 ,其次当系统稳定时 ,由于蚁群算法的正反 馈自寻优能力 ,若网络中各链路时延不变 ,则经过一 段时间后 ,几乎所有的蚂蚁都会选择相同的路径. 当 业务流量较大的时候就会发生拥塞. 为了防止这种 · 053 · 智 能 系 统 学 报 第 3卷