第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 ·