张卿祎¹, 王兴伟², 黄敏³
1.东北大学 计算机科学与工程学院，辽宁 沈阳 110169;
2.东北大学 软件学院，辽宁 沈阳 110169;
3.东北大学 信息科学与工程学院，辽宁 沈阳 110819
收稿日期: 2015-10-28
基金项目: 国家杰出青年科学基金资助项目 (61225012，71325002)；国家自然科学基金资助项目 (61572123)；教育部高等学校博士学科点专项科研基金优先发展领域资助课题 (20120042130003)。
作者简介: 张卿祎 (1990-)，男，山西太原人, 东北大学博士研究生;
王兴伟 (1968-)，男，辽宁盖州人，东北大学教授，博士生导师;
黄敏 (1968-)，女，福建长乐人，东北大学教授，博士生导师。

摘要: 由于网络的异构性、移动性和不稳定性等特点导致网络在发生故障时连接的可靠性变差，不能满足用户服务质量 (quality of service，QoS) 需求，因此网络需要具有保证QoS的容错路由能力.为此提出基于粒子群优化 (particle swarm optimization，PSO) 和模拟退火 (simulated annealing，SA) 混合优化的容错QoS路由机制.考虑到网络环境的动态性，引入模糊数学和概率论定量刻画网络模型，采用共享风险链路组 (shared risk link group，SRLG) 分离和共享通路的预防式保护策略建立备份路径，使其端到端可靠性、代价和路径QoS评价值达到最优.仿真结果表明，所提出的容错路由机制具有良好的路由有效性、故障恢复率和资源利用率，是可行和有效的.
关键词：容错路由服务质量共享风险链路组粒子群优化模拟退火
An Intelligent Fault-Tolerant QoS Routing Mechanism Based on PSO and SA Hybrid Optimization
ZHANG Qing-yi¹, WANG Xing-wei², HUANG Min³
1.School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2.School of Software, Northeastern University, Shenyang 110169, China;
3.School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: WANG Xing-wei. E-mail:wangxw@mail.neu.edu.cn
Abstract: Network is vulnerable when failures happen due to its heterogeneity, mobility and instability, at the same time reliability and user QoS (quality of service) cannot be guaranteed. Therefore fault tolerance needs to be improved to guarantee the reliability of QoS routing. For this purpose, an intelligent fault-tolerant QoS routing mechanism was proposed based on PSO (particle swarm optimization) and SA (simulated annealing). Considering the network dynamics, network model was quantitatively described by introducing knowledge of fuzzy mathematics and probability theory. The SRLG (shared risk link group) disjoint and preventive shared-path protective strategy were adopted to find backup path, which optimized end-to-end reliability, cost and QoS parameters. Simulation results indicate that the proposed mechanism has good performance on the percentage of route validity, fault-restoring ratio and resource utilization and thus is feasible and effective.
Key Words: fault-tolerant routingquality of service (QoS)shared risk link groupparticle swarm optimizationsimulated annealing
各种新型网络应用的出现丰富并改善着人类的生活.虽然通信技术和计算机网络的发展为新型应用提供了有力支持，但是由于目前网络的异构性、移动性、不稳定性等特点，导致网络在发生故障时用户的连接可靠性得不到保证.而且新型应用对网络QoS的要求越来越高，客观上要求网络提高容错能力并兼顾QoS保证^[1].容错QoS路由是有效方法之一.
容错路由是保证连接可靠性的重要方法，通常分为预防式和反应式两类.由于反应式策略的时间代价高，不能很好地满足用户QoS需求，因此，本文采用预防式策略，并通过共享路径保护和SRLG分离的策略一定程度上弥补预防式策略备份资源利用率低的缺陷.
实际通信中，由于网络参数是动态变化的，用户对QoS的需求难以定量地准确表达，且链路状态的测量也是不精确的^[2].因此，本文通过采用模糊数学相关方法定量地描述不精确的网络参数和用户相关QoS需求.
容错QoS路由问题是多约束下求解可行路径的问题，属于NP完全问题，而用于解决此类问题的启发式算法往往具有很大的局限性.因此，本文采用结合PSO算法的全局寻优能力和SA算法较强跳出局部最优解能力的PSOSA智能优化算法解决此问题，该混合优化算法已被成功应用，具有较好的性能.
文献[3]提出划分网络失效独立恢复域的方法，保证域内恢复时间的上限.文献[4]提出共享备份路径恢复机制，分离的备份路径可共享同一链路上的带宽.文献[5]用模拟退火构造备份路由表来恢复网络中单链路故障.该方案只将故障点和受影响的邻居节点上的流量转移到备份路径上.文献[6]提出一种可调生存性生成树的机制来解决网络失效问题，该机制可量化任意生成树的生存性来提供灵活的路由选择，并同时考虑树的QoS.文献[7]提出基于快速生成树重连接的以太网生成树，使用部分空间保护机制来提供不同的保护性，使用备份带宽来保护小部分链路，具有更少的信令开销、更快的恢复和更少的重路由次数.文献[8]使用通道和多址技术解决网络双链路或单节点失效.文献[9]提出概率相关失效的最小化链路失效的跨层模型.通过该模型，网络可以量化备份路径的可靠性，并基于此选择多个可靠备份路径来保证通信.文献[10]提出基于虚拟网络的容错机制，建立物理网络和虚拟网络映射关系，并通过机会弹性嵌入的方法反应式地保护虚拟链路.
从上述研究工作可以看出，已有研究成果很少兼顾容错和QoS双重需要，并且没有考虑路由信息的模糊性.为此，本文在满足用户QoS条件的前提下综合考虑了路由信息的模糊性、备份资源利用率和故障恢复率.
1 问题描述1.1 网络模型与用户需求将真实的网络拓扑抽象成一个无向连通图G=(V, E)，V是节点集合，E是链路集合^[11].对于E中的每条链路e_l，设其可用带宽为[Bw_L, Bw_H]、延迟为[Del_L, Del_H]、出错率为[Los_L, Los_H].用户QoS路由连接请求包括：带宽需求[bw_rq_L, bw_rq_H]、延迟约束[del_rq_L, del_rq_H]、出错率约束[los_rq_L, los_rq_H].
1.2 链路参数与路径QoS评价链路e_l能够满足用户带宽需求bw的概率S_B^l(bw) 和延迟约束del的概率S_D^l(del) 分别用式 (1)，式 (2) 描述.

(1)

(2)

其中k＞0，ε＞0且ε<<1.式 (2) 表明链路能够提供带宽bw的概率与带宽值负相关.
将占用的实际带宽定义为UBw^l，其中l∈P，P为路径，B_L是瓶颈带宽，值为Min_l∈P(UBw^l).实际占用带宽g_B^P定义如式 (3)，式 (4)：

(3)

(4)

其中：f_B^P(UBw^l) 表示用户在瓶颈带宽为UBw^l时的满意度函数；S_B^l(UBw^l) 表示链路能够保证提供带宽UBw^l的概率；路径P可以满足用户带宽需求的概率为P上各个链路能够保证提供带宽的概率的乘积.
同样，设用户使用路径P上的各段链路l的延迟取值区间为[Del_L^l, Del_H^l]，令，，则路径P端到端延迟取值区间为[D_L, D_H].故P上端到端延迟的概率g_D^P定义如下：

(5)

(6)

其中，f_D^P(del) 表示端到端延迟为del时的满意度函数.链路延迟计算定义为对路径延迟值在变化区间积分.
对于链路e_l满足出错率约束los的概率S_L^l(los) 的定义以及路径P的出错率评价函数g_L^P(los) 的定义与延迟约束相关定义类似，只需将del用los替换即可.最后定义端到端路径的QoS评价函数：

(7)

其中：α_B，α_D和α_L分别代表带宽、延迟和出错率所占的权重；0≤α_B, α_D, α_L≤1，α_B+α_D+α_L=1.本文将出错率的权重设为1/2，带宽和延迟的权重各为1/4.
1.3 SRLG分离的路径保护SRLG是指共享同一失效风险物理资源的一组链路.每个SRLG全局唯一，每条链路可能属于一个或多个SRLG.对于预防式容错QoS路由机制而言，若工作路径wp_n和保护路径bp_n同时失效 (n为编号)，则故障无法恢复.本文仅考虑单SRLG故障的情况.
基于SRLG分离的路径保护是在源和目的之间找到1条工作路径和1条不经过同一SRLG的保护路径. SRLG条件故障概率定义为

(8)

其中CP (srlg) 表示当SRLG故障时，共享该SRLG的2条链路l_i和l_j同时失效的概率.若连接可靠性要求 (即路径可靠度) 为RD，则wp_n和bp_n同时失效的概率应小于1－RD，即这2条路径需满足式 (9) 条件：

(9)

其中，CSIS是wp_n和bp_n共享的SRLG的集合.若对于wp_n中每个srlg有CP (srlg)＜(1－RD)/P (wp_n failure)，则称此srlg为不需要被保护的SRLG；否则，称此srlg是需要被保护的SRLG (protected-SRLG，PSRLG)，找到的保护路径须PSRLG分离.
1.4 优化模型优化目标是以用户QoS需求为前提，使端到端可靠性、代价和QoS评价值达到最优目标值.链路代价函数c′_l定义如下：

(10)

其中：p_l为预留的备份资源；r_l为剩余资源；tp_l为恢复单SRLG故障所需的保护路由资源最大值；c_l为基本代价.优化目标及约束如式 (11)~式 (16) 所示：

(11)

(12)

(13)

(14)

(15)

(16)

2 算法设计2.1 解的表达和初始解的生成PSOSA算法的每一个解为一条路径，采用向量表示：P(i)=(e₁, e₂, …, e_len)，e为链路，所有链路组成从源到目的的一条路径.采用随机路径算法生成初始解.
2.2 适值函数从工作和保护路径对中选择一对使端到端可靠性、代价和QoS评价值达到最优的路径作为本次循环的当前最优解.所以，适值函数定义为

(17)

其中JP为跳数.式 (17) 表示适值越小，路径质量越高.
2.3 路由容错质量评价通过算法寻找到的同一连接请求的主从路径对需要符合下述两个条件：
1) 工作路径和保护路径需PSRLG分离；
2) 共享保护资源的工作路径间需PSRLG分离.
2.4 初始温度选择及退温函数选择初始温度采用公式t₀=kδ确定，k=10, 20, 100, …等试验值；δ=f_max－f_min，f_max和f_min分别为初始解中最大和最小的目标函数值.
将粒子群变换的新解作为模拟退火算法等温过程的初始解.收敛准则采用Metropolis准则，其中，适值函数 (17) 即为能量函数.退温函数选用常用的t_k+1=α·t_k形式，其中α=0.9.
2.5 粒子飞行速度和位置更新i时刻粒子当前位置用X(i)=(e₁ⁱ, e₂ⁱ, e₃ⁱ, …, e_lenⁱ) 表示，迭代更新后的粒子位置用X(j)=(e₁^j, e₂^j, e₃^j, …, e_len^j) 表示，粒子飞行速度为v(i)，于是有

(18)

(19)

将v(i) 定义为一组变换：

(20)

变换Ψ_k将X(i) 中的一个分量 (1条边) 变成X(j) 中的对应分量.其中式 (18) 表示将粒子位置“先作v(i) 变换，再作v(j) 变换”.式 (19) 表示其逆向操作.
设粒子id在时刻i的位置为X_id(i)，速度为v_id(i)，则下一时刻i+1的位置可以表示为

(21)

(22)

式 (22) 中，从初始时刻到i时，id历经过的最佳位置为P_id(i)，P_gd(i) 为全局最优位置. w，c₁，c₂是对应的偏差权重系数. c₁×rand ()₁和c₂×rand ()₂分别表示位置变换P_id(i)－X_id(i) 和P_gd(i)－X_gd(i) 发生的概率.其中，一般取w由大到小递减变化，变化范围0.9到1.2，表示PSO算法从广泛到局部精细搜索变化.加速常数c₁和c₂取值为2，rand () 是随机数生成器 (0到1).
2.6 工作流程??算法PSOSA.
输入:
G=(V, E), bw_req_L, del_req_H, los_req_H, k, α, t₀, NC_max, RD, SRLG－list
输出:wp, bp
1.??Initialize particle swarm P by Stochastic Path Method; /*Include N particles*/
2.??For 1 to i do
3.???While P_i can’t satisfy the s.t.(14)~(16)do
4.???Regenerate P_i by Stochastic Path Method;
5.??End while
6.??Calculate the fitness value of P_i by (17);
7.?End for
8.?Select P_i with min fitness value as P_gd;
9.?While do
10.???Generate the SIS of P_gd; /*SIS is srlg set of a path*/
11.???For 1 to j do
12.????If CP (srlg_j)≥(1－RD)/P(P_gd failure)then add srlg_j into SIS_d; /*SIS_d is srlg set that must be disjoint*/
13.??End for
14.???Calculate the subgraph G’by delete the SIS_d;
15.??Find the suboptimal P′_gd in G’;
16.??If Sig of Al.2==0 then wp←P_gd; bp←P′_gd; Update SRLG－list;
17.??If NC＞NC_max then Reject Request;
18.????Calculate the new position and new velocity by (21)，(22) of each P_i;
19.??? While P_i can't satisfy the s.t.(14)~(16) do
20.????Regenerate P_i;
21.???End while
22.??Update the P_gd with smaller fitness value;
23.???While 1 to i do
24.????If ΔE＜0 of P_i then update the P_i;
25.????Continue
26.???Accept the P_i by Metropolis Criterion;
27.???End while
28.??Annealing by t_k+1=α·t_k;
29.?End while
30.?Return wp←P_gd; bp←P′_gd; Update SRLG－list
算法1~8行的作用是生成满足约束的初始粒子群，并选出当前全局最优粒子；9~16行的作用是为不满足可靠度要求的工作路径生成备份路径，并输出符合容错质量评价条件的主从路径；算法18~22行的作用是计算粒子更新后的新速度及新位置，选择满足约束条件的新粒子；算法23~27行的作用是更新满足约束条件的新粒子的适应值，并根据Metropolis准则判断是否接受；算法28行的作用是进行退温.
3 性能评价基于NS2平台在4个实际的网络拓扑 (NSFNet、CERNET2、CERNET和GEANT) 上对本文设计的机制 (PSOSA) 进行仿真实验，并与采用基于多Agent进化算法的机制 (Multi-Agent)，文献[8]提出的机制 (FRuT) 和文献[12]提出的机制 (DRLR) 进行对比分析.
NS2平台的相关仿真参数如表 1所示.每个SRLG的条件故障概率随机从10%，20%，50%选择.请求到达速率和持续时间分别服从对应参数的泊松分布和指数分布.
表 1(Table 1)

表 1 仿真参数设置Table 1 Simulation parameters 参数名称 值 请求到达速率 β(泊松分布均值) 持续时间 1/μ(指数分布均值) 总负载 β/μ 通信时间/s 2 记录间隔/s 0.01 模拟连接次数 106

表 1 仿真参数设置 Table 1 Simulation parameters

4种机制的路由成功率对比如图 1所示.结果表明对于网络参数的动态性，PSOSA和Multi-Agent有较强的适应性，FRuT只考虑双链路失效，而DRLR考虑单链路失效且没有考虑网络参数的动态变化问题，因而性能较差.
图 1(Fig. 1)

图 1 路由成功率的比较Fig.1 Comparison of percentage of route validity

图 2给出在CERNET拓扑上4种机制平均资源占用量的对比.结果表明随着负载的增加，4种机制平均资源占用量逐渐减小，资源利用率都逐渐增高，但增高速率PSOSA较DRLR有较大提升.这是因为PSOSA采用共享通路的保护策略，全局优化了资源配置，使其没有更多的冗余预留.因为Multi-Agent算法缺乏全局信息，依赖Agent的自治行为实现进化，容易陷入局部最优解，所以增高速率不如PSOSA.而FRuT虽然同样采用共享通路的保护策略，但其多址技术增加了资源预留.
图 2(Fig. 2)

图 2 平均资源占用量随负载变化的情况Fig.2 Resource utilization per connection with load changes

4种机制的故障恢复率比较如图 3所示.结果表明PSOSA在4个拓扑中的故障恢复率性能在小型拓扑上较优，而在较大型的拓扑上和Multi-Agent相差无几.因PSOSA可以处理单SRLG故障，容错能力较DRLR大大提高.而由于FRuT可以处理单节点故障，所以FRuT稍逊于PSOSA.
图 3(Fig. 3)

图 3 故障恢复率的对比Fig.3 Comparison of fault-restoring ratio

为了验证拓扑结构对算法的影响，在给定的4个拓扑上运行4个算法. 图 4对比了4个算法在不同拓扑上获得最优解所需的平均迭代次数. 图 5对比了4个算法相应的平均运行时间.结果表明4个算法对于网络规模变化是敏感的，迭代次数和运行时间都会相应增加.在拓扑规模和复杂度较小的网络中，平均迭代次数相差无几，但是PSOSA在平均运行时间上性能较Multi-Agent算法有较大提升，这是因为PSOSA只需要根据已有的信息进行分量的替换，而Multi-Agent算法中复杂的繁殖过程增加了时间开销.虽然在算法性能层面本文PSOSA的表现与FRuT和DRLR相比提升不明显，但是提高了容错率、资源利用率和故障恢复率.
图 4(Fig. 4)

图 4 容错算法达到最优解的迭代次数对比Fig.4 Comparison of iterations when fault-tolerant algorithm achieves optimal solution

图 5(Fig. 5)

图 5 容错算法运行时间对比Fig.5 Comparison of runtime for fault-tolerate algorithms

4 结语本文采用模糊数学分析方法，定量刻画动态、不精确网络的环境，采用SRLG模型和共享路径保护提高预防式容错策略的资源利用率，提出一种优化的网络容错QoS路由模型，并结合PSOSA混合优化算法解决了预防式多约束下容错QoS路由问题.仿真结果表明，本文的机制可以在允许时间范围内找到优化的主从路径，具有较好的性能.今后的研究重点是如何使网络模型更加客观合理和如何使算法更加高效.
参考文献

[1]	Wang X W, Cheng H, Huang M. Multi-robot navigation based QoS routing in self-organizing networks[J].Engineering Applications of Artificial Intelligence , 2013, 26(1): 262–272.DOI:10.1016/j.engappai.2012.01.008
[2]	王兴伟, 王军伟, 黄敏. 基于狩猎搜索的可信QoS路由算法[J].东北大学学报 (自然科学版), 2012, 33(10): 1385–1389. ( Wang Xing-wei, Wang Jun-wei, Huang Min. Hunting search based trustworthy QoS routing algorithm[J].Journal of Northeastern University (Natural Science) , 2012, 33(10): 1385–1389.)
[3]	Kuperman G, Modiano E.Network protection with guaranteed recovery times using recovery domains [C]//Proceedings of IEEE INFOCOM.Piscataway:IEEE, 2013:692-700.
[4]	Kodialam M, Lakshman T V, Orlin J B. End-to-end re-storable oblivious routing of hose model traffic[J].IEEE/ACM Transactions on Networking , 2011, 19(4): 1223–1236.DOI:10.1109/TNET.2011.2121918
[5]	Tseng P K, Chung W H. Joint coverage and link utilization for fast IP local protection[J].Computer Networks , 2012, 56(15): 3385–3400.DOI:10.1016/j.comnet.2012.06.017
[6]	Yallouz J, Rottenstreich O, Orda A.Tunable survivable spanning trees [C]//Proceedings of ACM SIGMETRICS.New York:ACM, 2014:315-327.
[7]	Shan D M, Kee C C, Gurusamy M, et al. Partial spatial protection for provisioning differentiated reliability in FSTR-based Metro Ethernet networks[J].Computer Networks , 2013, 57(1): 46–60.DOI:10.1016/j.comnet.2012.08.016
[8]	Kini S, Ramasubramanian S, Kvalbein A, et al. Fast recovery from dual-link or single-node failures in IP networks using tunneling[J].IEEE/ACM Transactions on Networking , 2010, 18(6): 1988–1999.DOI:10.1109/TNET.2010.2055887
[9]	Zheng Q, Cao G H, Porta T L, et al. Cross-layer approach for minimizing routing disruption in IP networks[J].IEEE Transactions on Parallel and Distributed Systems , 2014, 25(7): 1659–1669.DOI:10.1109/TPDS.2013.157
[10]	Oliveira R R, Marcon D S, Bays L R, et al. Opportunistic resilience embedding (ORE):toward cost-efficient resilient virtual networks[J].Computer Networks , 2015, 89.
[11]	谢小民, 王兴伟, 温占考, 等. 一种面向认知网络的QoS路由协议[J].计算机学报, 2013, 36(9): 1807–1815. ( Xie Xiao-min, Wang Xing-wei, Wen Zhan-kao, et al. A QoS routing protocol for cognitive network[J].Chinese Journal of Computers , 2013, 36(9): 1807–1815.)
[12]	Kodialam M, Lakshman T V.Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information [C]//Proceedings of IEEE INFOCOM.Piscataway:IEEE, 2001:376-385.