第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 AntNet的多路径QoS路由算法研究 朱尚明，高大启 华东理工大学信息科学与工程学院，上海200237) 摘要：以AnNεt算法为基础，介绍了蚁群网络路由的问题模型和数据结构，通过引入QoS约束机制，提出了一种基 于AnNet的多路径QoS路由算法.该算法采用具有带宽和时延QoS约束的新规则进行节点选择，并利用改进的节点 信息更新规则以及根据路由表中概率值随机地选择相邻节点转发数据包.性能分析和模拟结果显示，基于AnNεt的 多路径Qo$路由算法具有较快的收敛速度和较好的鲁棒性，能够自适应网络状态的动态变化，同时考虑了QoS约束 和负载平衡问题」 关键词：蚂蚁网络；多路径路由；QoS服务质量约束 中图分类号：TP393文献标识码：A文章编号：1673-4785(2008)04034906 A multipa th QoS routing algorithm ba sed on Ant Net ZHU Shangm ing,GAO Da-qi (School of nfomation Science and Engineering.East China University of Science and Technobgy,Shanghai 200237,China) Abstract:This paper exam ines a mathematical model and data structure or a multipath QoS routing algorithm based on the AnNet algorithm The proposed algorithm selects nodes with a new rule considering both bandwidth and tme-delay QoS constraints Then it transfers data packets using the mproved updating rule for nodal infomation and random ly chooses neighboring nodes to transfer data packets according to probabilities in the routing table Per fomance analysis and siulation results show that the multpath QoS routing algorithm based on AnNet converges faster and is more robust than other algorithms It can automatically adapt to dynam ic variations in netork status while taking into account QoS constraints and bad balancing Keywords:AnNet multpath routing QoS;constraint on service quality 蚁群(ant colny,AC)算法是由意大利学者M 适应路由.实验表明，AnNet路由算法和其他路由 Dorigo?等人于20世纪90年代初提出的一种新型的 算法（如OSPF、SPF等）相比具有一定的优势).本 模拟进化算法).蚁群算法从生物学和仿生学角 文将以AnNet算法为基础，介绍蚁群网络路由的问 度出发，模拟蚂蚁从蚁巢寻找到食物源的最优路径 题模型和数据结构，对其进行改进，引入Qo$约束 的自然行为，通过由候选解组成的群体的进化过程 机制，提出一种基于AnNet的多路径QoS路由算 来寻求最优解」 法，并对其性能进行分析 蚁群算法作为一种求解复杂组合优化问题的计 算智能方法，可以用于求解网络路由问题，近年来国 1问题模型和数据结构 内外学者先后提出了很多方案31，其中以GDi 11问题模型 Cao和M.Dorigo提出的蚂蚁网络(AnNet)为典型 AnNet本质上是一个基于移动Agent的系统， 代表B).AnNet算法通过2类基于移动A gent的前 算法中构造了2类结构基本相同的人工蚂蚁：前行 行蚂蚁和后行蚂蚁共同合作，动态地达到网络的自 蚂蚁Fan和后行蚂蚁Bmt其中Fn表示从源节点到 目的节点的人工蚂蚁，在其向目的节点前进的过程 收稿日期：200708-20 基金项目：因家自然科学基金资助项目(60373073). 中收集信息；Bm表示从目的节点返回源节点的人工 通信作者：朱尚明.Email zhusn@ecust edu cn 蚂蚁，在返回途中根据F收集的信息进行路由表 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 AntNet的多路径 QoS路由算法研究 朱尚明 , 高大启 (华东理工大学 信息科学与工程学院 , 上海 200237) 摘 要 :以 AntNet算法为基础 ,介绍了蚁群网络路由的问题模型和数据结构 ,通过引入 QoS约束机制 ,提出了一种基 于 AntNet的多路径 QoS路由算法. 该算法采用具有带宽和时延 QoS约束的新规则进行节点选择 ,并利用改进的节点 信息更新规则以及根据路由表中概率值随机地选择相邻节点转发数据包. 性能分析和模拟结果显示 ,基于 AntNet的 多路径 QoS路由算法具有较快的收敛速度和较好的鲁棒性 ,能够自适应网络状态的动态变化 ,同时考虑了 QoS约束 和负载平衡问题. 关键词 :蚂蚁网络 ;多路径路由 ; QoS;服务质量约束 中图分类号 : TP393 文献标识码 : A 文章编号 : 167324785 (2008) 0420349206 A multipath QoS routing algor ithm based on Ant Net ZHU Shang2m ing, GAO Da2qi (School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China) Abstract: This paper exam ines a mathematicalmodel and data structure for a multipath QoS routing algorithm based on the AntNet algorithm. The p roposed algorithm selects nodes with a new rule considering both bandwidth and time2delay QoS constraints. Then it transfers data packets using the imp roved updating rule for nodal information and random ly chooses neighboring nodes to transfer data packets according to p robabilities in the routing table. Per2 formance analysis and simulation results show that the multipath QoS routing algorithm based on AntNet converges faster and is more robust than other algorithm s. It can automatically adap t to dynam ic variations in network status while taking into account QoS constraints and load balancing. Keywords:AntNet; multipath routing; QoS; constraint on service quality 收稿日期 : 2007208220. 基金项目 :国家自然科学基金资助项目 (60373073). 通信作者 :朱尚明. E2mail: zhusm@ecust. edu. cn. 蚁群 ( ant colony, AC)算法是由意大利学者 M. Dorigo等人于 20世纪 90年代初提出的一种新型的 模拟进化算法 [ 122 ] . 蚁群算法从生物学和仿生学角 度出发 ,模拟蚂蚁从蚁巢寻找到食物源的最优路径 的自然行为 ,通过由候选解组成的群体的进化过程 来寻求最优解. 蚁群算法作为一种求解复杂组合优化问题的计 算智能方法 ,可以用于求解网络路由问题 ,近年来国 内外学者先后提出了很多方案 [ 3210 ] ,其中以 G. D i Caro和 M. Dorigo提出的蚂蚁网络 (AntNet)为典型 代表 [ 3 ] . AntNet算法通过 2类基于移动 Agent的前 行蚂蚁和后行蚂蚁共同合作 ,动态地达到网络的自 适应路由. 实验表明 , AntNet路由算法和其他路由 算法 (如 OSPF、SPF等 )相比具有一定的优势 [ 4 ] . 本 文将以 AntNet算法为基础 ,介绍蚁群网络路由的问 题模型和数据结构 ,对其进行改进 ,引入 QoS约束 机制 ,提出一种基于 AntNet的多路径 QoS路由算 法 ,并对其性能进行分析. 1 问题模型和数据结构 1. 1 问题模型 AntNet本质上是一个基于移动 Agent的系统 , 算法中构造了 2类结构基本相同的人工蚂蚁 :前行 蚂蚁 Fant和后行蚂蚁 Bant . 其中 Fant表示从源节点到 目的节点的人工蚂蚁 ,在其向目的节点前进的过程 中收集信息; Bant表示从目的节点返回源节点的人工 蚂蚁 ,在返回途中根据 Fant收集的信息进行路由表
·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卷
第4期 朱尚明，等：AnNet的多路径QoS路由算法研究 ·351· 现象，本算法采用具有带宽和时延Q0S约束、并考 进行规一化处理 虑相应链路队列状态的新规则进行节点选择.另外， 增强因子∈0,1，并按式10)进行动态计算： 还采用了改进的节点信息更新规则，以及根据路由 festg 【p-et r=a 表中概率值随机地选择相邻节点进行数据包转发来 4.d +61e-+( 提高算法的性能， 10) 在节点k首先计算一个新的满足带宽约束要 式中：G和Q为权重系数，.为前行蚂蚁新近记录 求的邻居集合Nk,节点k与N.中的每个节点v的 的从当前节点k到目的节点d的时延，e是在观察 链路1(k的带宽都大于等于所需的最小带宽B。, 窗口W。内向目的节点d前行过程中所经历的最小 即 时间，是根据置信水平所确定的时延置信区间的 Nk=fry∈N,bandw idth(ky≥Ba.(6) 上限，并由式11)进行动态计算： 式中：N:=(ne ighbors(k).然后再根据相应链路队 11) 列状态和概率表进行节点选择，选择规则描述如下： p=。+ 1-Y J Wms I 1)如果N中一个可行的相邻节点就是目的节点 式中：Y为置信水平，Wmx伪为观察窗口的大小 d则蚂蚁将无条件选择这个相邻节点：2)如果N4 后向蚂蚁根据前向蚂蚁得到的时延值的“好坏 中存在以前所有蚂蚁都没走过的相邻节点，则按式 程度对概率表进行更新，式(10)的第1项反映了 (7)计算新概率P,并在其中按概率P'的最大值 当前的时延值与最小时延值的比率，第2项反映了 随机地选择：3)如果N,中的相邻节点都有以前的 当前的时延值与最小时延的置信区间的相关度.当 蚂蚁访问过，在尽量不选本身蚂蚁走过的节点的前 的值不稳定时，的值不能完全反映网络的时延 提下，则在按式(7)计算新概率P4,并在其中按概 特性，因此本算法做了如下处理：使用压缩公式 率P的最大值随机地选择 (12)来增加或减少的值.这样处理使好的程度” 越大的时延值对路由表概率值的影响越大，而“好 P= Pu +al 1+a(INk|-1) j∈Nk: 的程度越小的时延值对概率值影响越小 7) 4 1 =1- 0≤↓∈1 s(x) ,x∈0,11，a∈R, 1 +e (12) 式中：！称为启发式校正系数，与当前节点k的相邻 str) s1》 节点的缓冲区状态成比例，9表示节点k与相邻 节点的链路队列长度，α是链路队列状态与路由 式中：)为压缩函数，成确定了压缩函数和相 概率的权重因子，用于衡量启发式校正系数↓与路 邻节点Nk的个数的相关度，a为压缩系数，应为一 由表中所存储的概率值P相比的重要性.显然，等 个大于1的正实数 待队列越长的链路，被选择的概率就越小.ā的最佳 232时延表的更新 取值由于不同的问题特性而有所变化，如果取值太 对于当前节点k其时延表按式(13)、(14)进行 小，的作用就体现不出来：如果太大，所得到的路 更新： 由表会出现振荡，这两者都会使得性能降低」 μa-μa+n.d-μa), (13 23节点信息更新规则 2←0房+n1(.4-442.0. (14) 231路由表更新规则 式中：μ为从本节点到目的节点d的时延平均值， 对于当前节点k其路由概率表更新的规则为： o为时延方差，n为权重参数，它反映了最近的几 如果相邻节点是后行蚂蚁过来的节点，那么下一节点 个样本对这个整体均值和方差的影响，通常与有 的概率值按式(8)进行增加，否则按式9)进行减少. 效采样窗口W的关系可以表示为W≈5(6八 Pid +Pid +r(1-Pu), (8) 24数据包路由和多路径选择 Pa←PH-P知，j卡ij∈N (9) 从源节点向目的节点发送路由数据包时，使用 式中：节点是后向蚂蚁过来的节点，节点是当前 和前行蚂蚁不同的路由表.为了满足时延约束，在对 节点的相邻节点，Nk为当前节点的相邻节点集合，d 数据包根据路由表中概率值随机地选择相邻节点 是目的节点，为增强因子.每一步计算之后，都要时，首先比较相邻节点到目的节点的时延均值 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
现象 ,本算法采用具有带宽和时延 QoS约束、并考 虑相应链路队列状态的新规则进行节点选择. 另外 , 还采用了改进的节点信息更新规则 ,以及根据路由 表中概率值随机地选择相邻节点进行数据包转发来 提高算法的性能. 在节点 k,首先计算一个新的满足带宽约束要 求的邻居集合 N ′k ,节点 k与 N ′k 中的每个节点 v的 链路 l( k, v)的带宽都大于等于所需的最小带宽 B0 , 即 N ′k = { v: v ∈Nk , bandw idth ( k, v) ≥B0 }. (6) 式中 :Nk = { neighbors( k) }. 然后再根据相应链路队 列状态和概率表进行节点选择 ,选择规则描述如下 : 1) 如果 N ′k 中一个可行的相邻节点就是目的节点 d,则蚂蚁将无条件选择这个相邻节点; 2) 如果 N ′k 中存在以前所有蚂蚁都没走过的相邻节点 ,则按式 (7)计算新概率 P′jd ,并在其中按概率 P′jd的最大值 随机地选择; 3) 如果 N ′k 中的相邻节点都有以前的 蚂蚁访问过 ,在尽量不选本身蚂蚁走过的节点的前 提下 ,则在按式 ( 7)计算新概率 P′jd ,并在其中按概 率 P′jd的最大值随机地选择. P′jd = Pjd +αlj 1 +α( | N ′k | - 1) , j ∈N ′k ; lj = 1 - qj ∑ |N ′k | j′ qj′ , 0 ≤ lj ∈ 1. (7) 式中 : lj称为启发式校正系数 ,与当前节点 k的相邻 节点 j的缓冲区状态成比例 , qj 表示节点 k与相邻 节点 j的链路队列长度 ,α是链路队列状态与路由 概率的权重因子 ,用于衡量启发式校正系数 lj 与路 由表中所存储的概率值 Pjd相比的重要性. 显然 ,等 待队列越长的链路 ,被选择的概率就越小.α的最佳 取值由于不同的问题特性而有所变化 ,如果取值太 小 , lj 的作用就体现不出来;如果太大 ,所得到的路 由表会出现振荡 ,这两者都会使得性能降低. 2. 3 节点信息更新规则 2. 3. 1 路由表更新规则 对于当前节点 k,其路由概率表更新的规则为: 如果相邻节点是后行蚂蚁过来的节点 ,那么下一节点 的概率值按式 (8)进行增加,否则按式 (9)进行减少. Pid ← Pid + r(1 - Pid ) , (8) Pjd ← Pjd - rPjd , j ≠ i, j ∈Nk . (9) 式中 :节点 i是后向蚂蚁过来的节点 ,节点 j是当前 节点的相邻节点 , Nk 为当前节点的相邻节点集合 , d 是目的节点 , r为增强因子. 每一步计算之后 ,都要 进行规一化处理. 增强因子 r∈(0, 1 ],并按式 (10)进行动态计算: r = c1 tbestd tt- d + c2 tsup - tbestd ( tsup - tbestd ) + ( tk - d - tbe std ) . (10) 式中 : c1 和 c2 为权重系数 , tk - d为前行蚂蚁新近记录 的从当前节点 k到目的节点 d的时延 , tbestd是在观察 窗口 W d 内向目的节点 d前行过程中所经历的最小 时间 , tsup是根据置信水平所确定的时延置信区间的 上限 ,并由式 (11)进行动态计算 : tsup =μd + σd 1 - γ | Wmax | . (11) 式中 :γ为置信水平 , |Wmax |为观察窗口的大小. 后向蚂蚁根据前向蚂蚁得到的时延值的“好坏 程度 ”对概率表进行更新 ,式 ( 10)的第 1项反映了 当前的时延值与最小时延值的比率 ,第 2项反映了 当前的时延值与最小时延的置信区间的相关度. 当 tk - d的值不稳定时 , r的值不能完全反映网络的时延 特性 ,因此本算法做了如下处理 : 使用压缩公式 (12)来增加或减少 r的值. 这样处理使“好的程度 ” 越大的时延值对路由表概率值的影响越大 ,而“好 的程度越小 ”的时延值对概率值影响越小. s( x) = 1 1 + e a x|N k | , x ∈ (0, 1 ], a ∈ R + , r ← s( r) s(1) . (12) 式中 : s ( x)为压缩函数 , a |Nk | 确定了压缩函数和相 邻节点 Nk 的个数的相关度 , a为压缩系数 ,应为一 个大于 1的正实数. 2. 3. 2 时延表的更新 对于当前节点 k,其时延表按式 (13)、(14)进行 更新 : μd ←μd +η( tk - d - μd ) , (13) σ2 d ←σ2 d +η( ( tk - d - μd ) 2 - σ2 d ). (14) 式中 :μd 为从本节点到目的节点 d的时延平均值 , σ2 d 为时延方差 ,η为权重参数 ,它反映了最近的几 个样本对这个整体均值和方差的影响 ,通常 η与有 效采样窗口 W 的关系可以表示为 |W |≈ 5 (δ/η). 2. 4 数据包路由和多路径选择 从源节点向目的节点发送路由数据包时 ,使用 和前行蚂蚁不同的路由表. 为了满足时延约束 ,在对 数据包根据路由表中概率值随机地选择相邻节点 时 ,首先比较相邻节点到目的节点的时延均值 μd , 第 4期 朱尚明 ,等 : AntNet的多路径 QoS路由算法研究 · 153 ·
·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卷
第4期 朱尚明，等：AnNe的多路径QoS路由算法研究 ·353 大小服从负指数分布.算法运行时的各种参数设置 0.30 Diikstra(N-50) 如表1所示 0.25 Dijkstra(N=25) AntNet(N=50) 表1算法运行时的各种参数设置 28 --AntNet(N=25) Table 1 Various parameters n smul tions 0.102 Name and smbol Values 0.05 前行蚂蚁初始大小bit 192 0234567890i1234 Hops 后行蚂蚁大小/bit 500 先验因子p 15 图1 AnNet算法在N=50,p=02和N=25.p=02时 路径跳数的概率密度函数 新样本权重n 01 Fig 1 PDF of the hopcount of AnNet algorithm paths 观察窗口大小W 50 orN=50,p=02andN=25,p=02 队列长度权重a 02 0.30 -Dijkstra(p=0.1) 最小时延比率权重G 07 0.25 -Dijkstra(p=0.2) 0.20 -AntNet(p=0.1) 时延置信区间权重G -AntNet(p=0.2) 03 克015 0.101 压缩系数a N为 0.05 强化系数B 3 012345678910i24 Hops 置信区间Y 095 图2AnNe算法在N=25,p=01和N=25.p=02时 最小可用带宽B。Mbps 4 路径跳数的概率密度函数 最大累积时延D。ms 2 Fig 2 PDF of the hopcount of AnNet algprithm paths 6rN=25,p=01andN=25,p=02 数据包到达时间均值ms 125 0.25 数据包生存时间加s 10 0.20 Diikstra --AntNet(B=3) 数据包大小均值/bt 4096 0.15 -AntNet(B=1) -AntNet(B=100) 图I~3分别给出了基于AnNet的路由算法和 0.05 Dijkstra最短路径算法的关于路径跳数的概率密度 012345678910121314 函数(probability density function,.PDF),可以看出， Hops 基于AnNet的路由算法都可以达到较好的收敛性】 图3 AnNet算法在B=1、3和100时 图1所示的模拟实验中，在链路选择概率p不 路径跳数的概率密度函数 变的情况下，比较节点个数N不同时对算法的影 Fig 3 PDF of the hopcount of AnNet algorithm paths 响，设置了N=50、p=02和N=25、p=02等2种 6rB=1,3and100 场景.可以看出，在节点规模较小时，基于AnNet的 景.可以看出，在节点规模一定时，如果链路选择概 路由算法的表现出来的性能也较好，基本接近D认k 率增大或减小)，由于可供路由的链路随之增大 stra最短路径算法.在N=50、p=Q2时，Dijkstra算 域减小)，2种算法所选择路径的跳数会相应变小 法和AnNet算法路径跳数的均值分别为360和 5.27,而在N=25、p=02时，Dijkstra算法和AnNet 或变大).在N=25、p=Q1时，Dijkstra算法和 算法路径跳数的均值则为3.02和341 AnNet算法路径跳数的均值分别为3.53和3.71， 图2所示的模拟实验中，在节点个数N不变的 而在N=25、p=Q2时，Dijkstra算法和AnNet算法 路径跳数的均值则为302和3.41 情况下，比较链路选择概率p不同时对算法的影响， 设置了N=25、p=01和N=25、p=02等2种场 图3所示的模拟实验中，在节点个数N和链路 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
大小服从负指数分布. 算法运行时的各种参数设置 如表 1所示. 表 1 算法运行时的各种参数设置 Table 1 Var ious param eters in sim ula tion s Name and simbol Values 前行蚂蚁初始大小 /bit 192 后行蚂蚁大小 /bit 500 先验因子 ρ 1. 5 新样本权重 η 0. 1 观察窗口大小 W 50 队列长度权重 α 0. 2 最小时延比率权重 c1 0. 7 时延置信区间权重 c2 0. 3 压缩系数 a N ×p 强化系数 β 3 置信区间 γ 0. 95 最小可用带宽 B0 /Mbp s 4 最大累积时延 D0 /ms 2 数据包到达时间均值 /ms 12. 5 数据包生存时间 /m s 10 数据包大小均值 / bit 4 096 图 1～3分别给出了基于 AntNet的路由算法和 D ijkstra最短路径算法的关于路径跳数的概率密度 函数 (p robability density function, PDF) ,可以看出 , 基于 AntNet的路由算法都可以达到较好的收敛性. 图 1所示的模拟实验中 ,在链路选择概率 p不 变的情况下 , 比较节点个数 N 不同时对算法的影 响 ,设置了 N = 50、p = 0. 2和 N = 25、p = 0. 2等 2种 场景. 可以看出 ,在节点规模较小时 ,基于 AntNet的 路由算法的表现出来的性能也较好 ,基本接近 D ijk2 stra最短路径算法. 在 N = 50、p = 0. 2时 , D ijkstra算 法和 AntNet算法路径跳数的均值分别为 3. 60和 5. 27,而在 N = 25、p = 0. 2时 , D ijkstra算法和 AntNet 算法路径跳数的均值则为 3. 02和 3. 41. 图 2所示的模拟实验中 ,在节点个数 N 不变的 情况下 ,比较链路选择概率 p不同时对算法的影响 , 设置了 N = 25、p = 0. 1和 N = 25、p = 0. 2等 2种场 图 1 AntNet算法在 N = 50, p = 0. 2和 N = 25, p = 0. 2时 路径跳数的概率密度函数 Fig. 1 PDF of the hopcount of AntNet algorithm paths for N = 50, p = 0. 2 and N = 25, p = 0. 2 图 2 AntNet算法在 N = 25, p = 0. 1和 N = 25, p = 0. 2时 路径跳数的概率密度函数 Fig. 2 PDF of the hopcount of AntNet algorithm paths for N = 25, p = 0. 1 and N = 25, p = 0. 2 图 3 AntNet算法在 β= 1、3和 100时 路径跳数的概率密度函数 Fig. 3 PDF of the hopcount of AntNet algorithm paths forβ= 1, 3 and 100 景. 可以看出 ,在节点规模一定时 ,如果链路选择概 率增大 (或减小 ) , 由于可供路由的链路随之增大 (或减小 ) , 2种算法所选择路径的跳数会相应变小 (或变大 ). 在 N = 25、p = 0. 1 时 , D ijkstra 算法和 AntNet算法路径跳数的均值分别为 3. 53和 3. 71, 而在 N = 25、p = 0. 2时 , D ijkstra算法和 AntNet算法 路径跳数的均值则为 3. 02和 3. 41. 图 3所示的模拟实验中 ,在节点个数 N 和链路 第 4期 朱尚明 ,等 : AntNet的多路径 QoS路由算法研究 · 353 ·
·354· 智能系统学报 第3卷 选择概率不变的情况下，比较强化系数B不同时 Computer Communications and Netorks Las Vegas,NV, 对算法的影响.从图中可以看出，在网络规模一定 US4,2000 时，B的变化对算法性能的影响不大，说明该算法具 [7王利，郭巧，基于理性的蚁群自适应路由[J]通 有较好的鲁棒性.B值较大时，AnNet算法的性能更 信学报，2005,26(1)：6-10 WANG Li,GO Qiaa Rationality-based AnNet self-adap- 接近Dijkstra最短路径算法，这和前面的分析是一 tive routing [J ]Joumal on Communications,2005,26 致的.在N=25、p=Q2的情况下，Dijkstra算法和 (1):6-10 AnNe算法在B=1、3和I00时路径跳数的均值分 [8]吕勇，赵光宙，苏凡军.基于蚁群算法的自适应动态 别为353、3.80、3.71和3.59. 路由算法[J]浙江大学学报工学版)，2005,39(10)： 4结束语 1537-1540 LUYong.ZHAO Guang hou,SU Fanjun Adaptive dynam- 采用蚁群优化算法来搜集网络最新信息，可以 ic routing algorithm based on AnNet algprithm [J ]Joumal 自适应网络状态的动态变化.通过改进选择策略，动 of Zhejiang University (Engineering Science),2005,39 态更新路由表项和节点状态信息，可以解决网络的 (10):1537-1540 负载均衡问题，提高了网络性能.基于AnNet的多 [9卢正鼎，刘会明，基于蚁群算法的理性自适应路由研究 路径QoS路由算法具有较快的收敛速度和较好的 [J]计算机工程与科学，2006,28(12)：15-18 鲁棒性，同时考虑了满足Qo$约束和负载平衡等问 LU Zhengding,LU Hum ing Research of rationally adap- tive routing based on ant colony algorithm s[J].Computer 题.基于蚁群算法来求解网络路由问题的研究，尚处 Engineering Science,2006,28(12):15-18 于刚刚起步阶段，其作为一种智能计算方法，具有很 [I0潘达儒，袁艳波.一种基于AnNet改进的QoS路由算 好的发展前景 法[J]小型微型计算机系统，2006,27(7)：1169- 参考文献： 1174 PAN Daru,YUAN Yanbo mproved QoS routing algorith [1 ]DOR IGO M.Optm ization leaming and natural algrithm based on the AnNet[J]MiniM icro Systems,2006,27 [D].Vatican:Politecnico diMilano,1992 (7):1169-1174 [2 ]DOR IGO M,MAN IEZZO V,COLORNIA.The ant sys 作者简介 tem:optm ization by a cobny of cooperating Agents [J 朱尚明，男，1969年生，副教授，主 IEEE Transactions on Systems,Man,and Cybemetics Part 要研究方向为计算机网络、多媒体通信 B,1996.26(1):29-41 和智能理论，发表学术论文40余篇，出 [3]CARO G,DOR IGO M.AnNet distributed stigmergetic 版著作3部. control for communications netorks[J ]Joumal of Artifi- cial Intelligence Research,1998(9):317-365 [4]DH LLON S S,M IEGHEM P V.Perfomance analysis of the AnNet algorithm [J ]Computer Netorks,2007(51): 高大启，男，1957年生，教授，博士 2104-2125 生导师，主要研究方向为模式识别、神 [5 ]BARAN B.mp roved AnNet routing[J ]ACM SIGCOMM 经网络、计算机嗅觉和信号处理，学科 Computer Communication Review,2001,31(2):42-48. 带头人，先后主持了10多项科研项目， [6 ]BARA N B,SOSA R.A new app roach for AnNet routing 发表学术论文100余篇，其中被SCLEI [C]//Proceedings ofN inth Intemational Conference on 和STP等收录近60篇。 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
选择概率 p不变的情况下 ,比较强化系数 β不同时 对算法的影响. 从图中可以看出 , 在网络规模一定 时 ,β的变化对算法性能的影响不大 ,说明该算法具 有较好的鲁棒性.β值较大时 , AntNet算法的性能更 接近 D ijkstra最短路径算法 ,这和前面的分析是一 致的. 在 N = 25、p = 0. 2的情况下 , D ijkstra算法和 AntNet算法在 β = 1、3和 100时路径跳数的均值分 别为 3. 53、3. 80、3. 71和 3. 59. 4 结束语 采用蚁群优化算法来搜集网络最新信息 ,可以 自适应网络状态的动态变化. 通过改进选择策略 ,动 态更新路由表项和节点状态信息 ,可以解决网络的 负载均衡问题 ,提高了网络性能. 基于 AntNet的多 路径 QoS路由算法具有较快的收敛速度和较好的 鲁棒性 ,同时考虑了满足 QoS约束和负载平衡等问 题. 基于蚁群算法来求解网络路由问题的研究 ,尚处 于刚刚起步阶段 ,其作为一种智能计算方法 ,具有很 好的发展前景. 参考文献 : [ 1 ] DOR IGO M. Op timization learning and natural algorithm [D ]. Vatican: Politecnico diM ilano, 1992. [ 2 ]DOR IGO M, MAN IEZZO V, COLORN I A. The ant sys2 tem: op tim ization by a colony of cooperating Agents[ J ]. IEEE Transactions on System s, Man, and Cybernetics Part B, 1996, 26 (1) : 29241. [ 3 ] CARO G, DOR IGO M. AntNet: distributed stigmergetic control for communications networks[J ]. Journal of A rtifi2 cial Intelligence Research, 1998 (9) : 3 l72365. [ 4 ] DH ILLON S S, M IEGHEM P V. Performance analysis of the AntNet algorithm [J ]. Computer Networks, 2007 (51) : 210422125. [ 5 ]BAR#N B. Imp roved AntNet routing[J ]. ACM SIGCOMM Computer Communication Review, 2001, 31 (2) : 42248. [ 6 ]BARA N B, SOSA R. A new app roach for AntNet routing [C ] / / Proceedings of N inth International Conference on Computer Communications and Networks. Las Vegas, NV, USA, 2000. [ 7 ]王 利 , 郭 巧. 基于理性的蚁群自适应路由 [J ]. 通 信学报 , 2005, 26 (1) : 6210. WANG L i, GUO Q iao. Rationality2based AntNet self2adap2 tive routing [ J ]. Journal on Communications, 2005, 26 (1) : 6210. [ 8 ]吕 勇 , 赵光宙 , 苏凡军. 基于蚁群算法的自适应动态 路由算法 [J ]. 浙江大学学报 (工学版 ) , 2005, 39 (10) : 153721540. LΒ Yong, ZHAO Guangzhou, SU Fanjun. Adap tive dynam2 ic routing algorithm based on AntNet algorithm [J ]. Journal of Zhejiang University ( Engineering Science ) , 2005, 39 (10) : 153721540. [ 9 ]卢正鼎 , 刘会明. 基于蚁群算法的理性自适应路由研究 [J ]. 计算机工程与科学 , 2006, 28 (12) : 15218. LU Zhengding, L IU Huim ing. Research of rationally adap2 tive routing based on ant colony algorithm s[ J ]. Computer Engineering & Science, 2006, 28 (12) : 15218. [ 10 ]潘达儒 , 袁艳波. 一种基于 AntNet改进的 QoS路由算 法 [J ]. 小型微型计算机系统 , 2006, 27 ( 7 ) : 11692 1174. PAN Daru, YUAN Yanbo. Imp roved QoS routing algorithm based on the AntNet[J ]. M ini2M icro System s, 2006, 27 (7) : 116921174. 作者简介 : 朱尚明 ,男 , 1969年生 ,副教授 ,主 要研究方向为计算机网络、多媒体通信 和智能理论 ,发表学术论文 40余篇 ,出 版著作 3部. 高大启 ,男 , 1957年生 ,教授 ,博士 生导师 ,主要研究方向为模式识别、神 经网络、计算机嗅觉和信号处理 ,学科 带头人 ,先后主持了 10多项科研项目 , 发表学术论文 100余篇 ,其中被 SCI、EI 和 ISTP等收录近 60篇. · 453 · 智 能 系 统 学 报 第 3卷