一种评估网络系统抗干扰能力的方法

本发明提供了一种评估网络系统抗干扰能力的方法，属于复杂系统工程、安全科学与工 程、计算机算法、以及管理优化领域。

网络系统涉及现实生活的方方面面，其中既包括真实的物理网络，如公路网，又包括抽 象的虚拟网络，如决策树。所有网络系统的一个根本共同点就是：通过网络拓扑结构将原本 孤立的结点连接起来，从而在结点间建立各种的联系或关系，以便使所有结点作为一个整体 化的系统而共同实现特定的系统功能。例如，公路网的一个系统功能就是要实现任意两个城 镇间的可通达性；决策树的一个系统功能就是要实现在某种给定前提条件下完成某个任务的 方案设计。由于各种干扰因素(例如：随机自然灾害、人为蓄意攻击、系统组分功能故障， 等等)的存在，网络系统中链接和结点随时有被断开的可能性。当网络系统中的一些链接和 结点由于干扰因素而断开时，网络系统基于剩余的链接和结点是否还能确保既定系统功能的 实现了？要回答这个问题，就需要对网络系统的抗干扰能力进行评估。

目前对网络系统的抗干扰能力进行评估的常见思路有两大类。第一类评估思路的关注焦 点是：在干扰因素作用下，网络系统瓦解变成两个或以上互不相连的、独立的子网络系统的 可能性(例如，基于地震后的路网，是否有至少两个城镇，在它们之间不再存在任何路线可 以连通彼此；又如，在生产计划决策树中，在某些生产单元故障后，是否会导致系统无法再 生产出任何产品，即，无法从原料状态到达产品状态)。第二类评估思路的关注焦点是：在干 扰因素作用下，网络中结点间的最优联系或最优关系被破坏的可能性(例如，基于地震后的 路网，某两个城镇间的最短路径是否被破坏；又如，在生产计划决策树中，当某些生产单元 故障后，能带来最大利润的生产方案是否会不再可行)。

事实上，上述两大类网络系统抗干扰能力评估方法仅仅考虑了两种极端情况：要么网络 系统瓦解变成多个彼此独立的子网络系统，要么网络系统中的最优路线受到影响。然而，在 现实生活中，网络使用者或决策者所最关心的往往并不是这两种极端情况，而是如下一种更 普适的情况：在干扰因素作用下，网络系统是否还能确保实现某种指定的最低程度的系统功 能？例如，基于地震后的路网，是否还能保证在任何两个城镇间都有至少一条长度不大于某 个给定阈值的路线连接彼此(长度大于给定阈值的路线不能实现救灾物质的及时送达，因而 没有实质意义)；又如，在生产计划决策树中，当某些生产单元故障后，是否仍然存在一种可 行的生产方案能保证实现某个预定的利润水平(生产线的投资者并不会固执地非要最大利润 不可，而是只要能确保实现一定的投资回报率即可)。

显而易见，“网络系统是否还能确保实现某种指定的最低程度的系统功能”涵盖了“网络 系统是否会瓦解变成多个彼此独立的子网络系统”和“网络系统中的最优路线是否会受到影 响”这两种极端情况。所以说：“网络系统是否还能确保实现某种指定的最低程度的系统功能” 是一种对网络系统的抗干扰能力进行评估的普适化思路。按这一普适化思路对网络系统的抗 干扰能力进行评估非常符合现实需求(按两种极端思路进行评估的结果通常并不能很好满足 现实需求：因为网络系统瓦解一般是小概率事件，在日常生活中并不会经常发生，普通人考 虑这个问题有点杞人忧天；而最优路线受到影响一般是大概率事件，普通人都能接受“金无 足赤”这个道理，除非有强迫症的完美主义者)。

然而，现有的对网络系统的抗干扰能力进行评估的方法通常都是按两种极端思路之一来 设计的。按“网络系统是否还能确保实现某种指定的最低程度的系统功能”这一普适化思路 来对网络系统的抗干扰能力进行评估的方法还鲜有报道。

从定量计算分析的角度看，要按“网络系统是否还能确保实现某种指定的最低程度的系 统功能”这一普适化思路来评估网络系统的抗干扰能力，首先要必须能计算出路径长度满 足给定条件的所有(而不是其中一条或部分)路径，比如，路网中长度小于给定阈值的所有 路线，生产计划决策树中能够实现不少于给定阈值利润的所有生产方案。然而，出路径长 度满足给定条件的所有路径对现有的方法来说并不是一件容易的事，在数学模型上可以描述 成一个多到多(即：多个起点，多个终点)的前k条最优路径问题。绝大多数路径优化方法 仅仅考虑一到一(即：一个起点，一个终点)最优路径问题。现有的求解前k条最优路径问 题的方法通常是迭代求解一系列(数量通常非常庞大)一到一第一最优路径问题，求解过程 十分繁琐而低效，例如，针对一个起点终点对(以后通称为一个OD对)，需要基于前(k-1) 条最优路径重构一系列数量庞大的新网络，然后对每一个新网络求解第一最优路径，才能 出原网络中的第k最优路径。对于多到多问题，还需要对每一个OD对重复进行上述的繁琐求 解过程。当网络系统非常庞大时(即：有非常多的OD对)，要想快速有效地求解多到多的前 k条最优路径问题，现有的方法基本上是无能为力的。这也是为什么现有方法很少能按“网 络系统是否还能确保实现某种指定的最低程度的系统功能”这一普适化思路来评估网络系统 的抗干扰能力，即：因为现有方法无法有效求解出网络中长度小于给定阈值的所有路线。

文献[1]和文献[2]中新近报道了一种涟漪扩散算法，不需要其它现有方法中的迭代 重复操作，就能在一次性的运算中求解出针对一到一问题的前k条最优路径。本发明的方法 中将改进这种涟漪扩散算法，以便实现在一次性的运算中求解出多到多问题的所有前k条最 优路径。然后，本发明的方法将通过这些所有前k条最优路径出网络系统中路径长度满足 给定条件的所有路径，再分析这些满足给定条件的路径的结点和链接共享情况，就可以按“网 络系统是否还能确保实现某种指定的最低程度的系统功能”这一普适化思路来精确地定量评 估网络系统的抗干扰能力。

[1]Hu，X.B.，M.Wang，D.Hu，M.S.Leeson，E.L.Hines，and E.Di Paolo，“A Ripple-Spreading Algorithm for the k Shortest Paths Problem，”2012 the 3rd Global Congress on Intelligent Systems(GCIS 2012)，PP： 202-208，6-8 Nov 2012，Wuhan，China.

[2]Hu，X.B.，M.Wang，M.S.Leeson，E.L.Hines，and E.Di Paolo，“A Deterministic Agent-Based Path Optimization Method by Mimicking the Spreading of Ripples”，Evolutionary Computation，in press，20l6 (Open Access available online，doi：10.1162/EVCO_a_00156).

本发明的目的是要提供一种评估网络系统抗干扰能力的方法。以评估网络系统在各种干 扰因素作用下是否还能确保实现按满足相应预设值域条件的路径长度连接各个起点终点对 (即，OD对)的能力。本发明为解决上述问题，简而言之，本发明的方法首先将网络系统抗 干扰能力要求转化成对应各个OD对的路径长度预设值域，然后模拟自然界的涟漪扩散现象在 网络中开展一次性的涟漪扩散接力赛，以求出网络中各个OD对之间长度满足相应预设值域条 件的所有路径(不是按“网络系统中的最优路线是否会受到影响”这一极端思路只求OD对之 间的最短路径，也不是按“网络系统是否会瓦解变成多个彼此独立的子网络系统”这一极端 思路求OD对之间的所有路径)，最后统计分析所有这些长度满足相应预设值域条件的路径中 的结点和链接的共享情况，从而按“网络系统是否还能确保实现某种指定的最低程度的系统 功能”这一普适化思路来定量评估网络系统的抗干扰能力。

按“网络系统是否还能确保实现某种指定的最低程度的系统功能”这一普适化思路来定 量评估网络系统的抗干扰能力，可以描述成如下数学问题。

假设有一个网络系统(可以是现实物理网络系统，如：公路网，也可以是抽象虚拟网络 系统，如：决策树)，包含NN个结点和NE条链接。结点间的链接可由一个邻接矩阵A表示， 其中的元素A(i，j)＝1表示结点i到结点j之间存在一条链接；A(i，j)＝0则表示结点i到结 点j之间没有链接。假设结点i到结点j之间存在一条链接，则该链接的权重值可记为CE(i，j)。 链接的权重值CE(i，j)将用于计算路径的长度。假设P表示一条路径，路径P包含NL≥2个结 点，P(i)表示路径P的第i个结点，1≤i≤NL，1≤P(i)≤NN。用CP(P)表示路径P的长度，其 计算如下：

C P ( P ) = Σ i = 1 N L - 1 C E ( P ( i ) , P ( i + 1 ) ) . - - - ( 1 )

又假设网络系统中有NOD个起点终点对(即，OD对)。OD对表明了哪些结点对之间的连接 情况才是抗干扰能力评估所感兴趣的；换句话说，OD对以外的结点对之间的连接情况将不是 抗干扰能力评估的研究内容。对于一个有向网络(即，结点i到结点j之间的链接与结点j 到结点i之间的链接并不是一回事，比如，A(i，j)＝1并不代表A(j，i)＝1；显而易见，无向网 络只是有向网络的一种特例；所以针对有向网络的方法完全适用于无向网络)，总有：1≤NOD ≤NN×(NN-1)。记第s个OD对中的起点为Os，终点为Ds，1≤s≤NOD。

本发明的评估网络系统抗干扰能力的方法包括以下几个主要步骤：

(步骤1)确定网络系统中要研究的所有OD对。即，根据具体问题的要求，确定所有OD 对的数目NOD，以及第s个OD对中的起点Os和终点Ds，1≤s≤NOD。

(步骤2)将网络系统抗干扰能力要求转化成对应各个OD对的路径长度预设值域。即， 根据具体问题的抗干扰能力要求，对每一个OD对，分别指定一个相应的路径长度预设值域。 记第s个OD对的路径长度预设值域为[LPT(s，1)，LPT(s，2)]，1≤s≤NOD，其中LPT(s，1)为第s 个OD对定义了的满足要求的路径长度下限，LPT(s，2)则定义了满足要求的路径长度上限。一 般而言，不同的OD对可以有不同的路径长度预设值域，也可以有相同的路径长度预设值域， 这完全取决于具体问题的要求。

(步骤3)对每一个OD对，出满足路径长度预设值域条件的所有路经。即，对于第s 个OD对，1≤s≤NOD，出网络中所有满足以下条件的路径P：

P(1)＝Os，P(NL)＝Ds； (2)

LPT(s，1)＜CP(P)＜LPT(s，2)，或者LPT(s，1)≤CP(P)＜LPT(s，2)，

或者LPT(s，1)＜CP(P)≤LPT(s，2)，或者LPT(s，1)≤CP(P)≤LPT(s，2)。 (3)

其中条件(2)要求路径P的起点是Os，终点是Ds；条件(3)是对路径长度预设值域条件的 普适化定义，要求路径P的长度在第s个OD对的路径长度预设值域区间内；对于一个给定的 OD对而言，条件(3)的预设值域区间到底是开区间、左闭右开区间、左开右闭区间、还是 闭区间，取决于具体问题的要求；在同一个网络系统中，对于不同的OD对，条件(3)的预 设值域区间的开闭情况可以是各不相同的，这也取决于具体问题的要求；条件(3)的预设值 域区间可以没有下限，即，相当于LPT(s，1)＝-∞，这同样取决于具体问题的要求。显而易见： 如果对于任意OD对，都有LPT(s，1)＝-∞和LPT(s，2)＝∞，则就是按“网络系统是否会瓦解变成 多个彼此独立的子网络系统”这一极端思路在评估网络系统的抗干扰能力；而如果对于任意 OD对，都有LPT(s，1)＝LPT(s，2)＝CP(Ps*)，Ps*是第s个OD对之间的最短路径，则就是按“网络 系统中的最优路线是否会受到影响”这一极端思路在评估网络系统的抗干扰能力。

(步骤4)统计所有OD对之间满足相应路径长度预设值域条件的所有路经中的结点和链 接的共享情况。即，假设ΩP是满足路径长度预设值域条件的所有路经的集合，统计网络系统 中各个结点以中间点(而非起点或终点)出现在ΩP所含路径中的次数，记结点n在ΩP所含 路径中以中间点出现了总共BN(n)次，1≤n≤NN；同时，统计网络系统中各条链接出现在ΩP 所含路径中的次数，记链接m在ΩP所含路径中出现了总共BE(m)次，1≤m≤NE；此外，还可以 统计网络系统中各个结点以中间点出现在ΩP中第s个OD对的所有路径中的次数，记结点n 在ΩP中第s个OD对的所有路径中以中间点出现了总共BN-OD(s，n)次，1≤s≤NOD，1≤n≤NN； 再统计网络系统中各条链接出现在ΩP中第s个OD对的所有路径中的次数，记链接m在ΩP中 第s个OD对的所有路径中出现了总共BE-OD(s，m)次，1≤s≤NOD，1≤m≤NE。

(步骤5)基于ΩP，BN(n)，BN-OD(s，n)，BE(m)，和BE-OD(s，m)，分析各OD对之间满足相应 路径长度预设值域条件的所有路经在各种干扰因素作用下全部断开的可能性，其中， s＝1，…，NOD，n＝1，…，NN，m＝1，…，NE。分析方法和过程主要取决于具体问题的类型和特点。例 如，可以做如下分析：假设ΩP中总共含有NP条路径，那么理论上总有0≤BN(n)/NP≤1(前提 条件是：一条路径中不能包含重复的点)；如果BN(n)/NP≈1，则说明，绝大部分满足相应路 径长度预设值域条件的路经都通过结点n，因此，如果结点n被干扰的可能性很大的话，则 网络系统实现某种指定的最低程度的系统功能的能力就很低下；同理，如果BE(m)/NP≈1，而 链接m被干扰的可能性又很大的话，则网络系统实现某种指定的最低程度的系统功能的能力 也很低下。

上述(步骤3)中的路径长度预设值域条件(3)还可以采用多值域区间的形式。例如， 对于第s个OD对，1≤s≤NOD，满足网络系统抗干扰能力要求的路径P必须满足如下路径长度 预设值域条件：

LPT(s，1)≤CP(P)≤LPT(s，2)，并且LPT(s，3)≤CP(P)≤LPT(s，4)， (4)

其中，LPT(s，2)＜LPT(s，3)，则[LPT(s，1)，LPT(s，2)]为第s个OD对定义了第一个值域区间， [LPT(s，3)，LPT(s，4)]为第s个OD对定义了第二个值域区间。第s个OD对到底需要几个值域 区间，以及每个值域区间的开闭情况如何，都取决于具体问题的要求。

上述(步骤3)是本发明的方法的关键步骤，也是实现本发明的方法的难点所在。要实现 (步骤3)中求解所有OD对之间满足相应路径长度预设值域条件的所有路经(可等效为多到 多前k条最短路径问题)，理论上，可以通过不断地迭代和重复运行现有的求解一个OD对之 间的最短路径算法(即，求解一到一第1最短路径问题的算法)而达到目的，即：选取一个 OD对，基于原始网络求解该OD对之间的最短路径，为该OD对之间的第1最短路径；基于第 1最短路径，重构一系列新网络(每个新网络由原始网络删除第1最短路径中所含链接的一 种可能组合而得到)，对每一个新网络求解该OD对之间的最短路径，然后所有新网络中的最 短路径中的最短者，就是原始网络中该OD对之间的第2最短路径；如此不断迭代，就可根据 该OD对之间的前(k-1)条最短路径，而求解出该OD对之间的第k最短路径，k＞1(通常随着 k增大而需要重构的新网络的数量会非常大)；如果在迭代过程中的第k最短路径的长度第一 次大于与该OD对相对应的路径长度预设值域的上限，则迭代过程停止，而致此所求解出的前 k条最短路径中满足该OD对的路径长度预设值域条件的所有路径就是该OD对之间满足抗干 扰能力要求的路径；然后对每一个OD对重复上述迭代求解过程，以求出每一个OD对之间满足 相应路径长度预设值域条件的路径，从而出网络系统中满足抗干扰能力要求的所有路径。 但是，用上述这种不断迭代和重复的方法来实现本发明的方法的(步骤3)，是非常低效的， 尤其是当网络系统规模很大、同时OD对的数目又很多的时候，用上述不断迭代和重复的方法 求解网络系统中满足抗干扰能力要求的所有路径几乎是不现实的。

为了快速高效地完成(步骤3)，本发明的方法专门研发了一种涟漪扩散算法，通过模拟 自然界的涟漪扩散现象在原始网络中开展一次性的涟漪扩散接力赛(不需要迭代重构任何新 网络，也不需要重复开展涟漪扩散接力赛)，就可以求解出所有OD对之间满足相应路径长度 预设值域条件的所有路径。

传统的涟漪扩散算法求解一个OD对之间最短路径的基本思想是：一个初始涟漪以OD对 中的起点为波源沿起点的各条链接向外扩散；当一个涟漪到达一个结点时，会在该结点激发 出一个新涟漪，新涟漪以该结点为波源并沿该结点的各条链接继续向外扩散；所有涟漪具有 相同的扩散速度；当OD对中的终点第一次有涟漪到达时，到达涟漪所走过的路径就是OD对 之间的第1最短路径，而当OD对中的终点第k次有涟漪到达时，到达涟漪所走过的路径就是 OD对之间的第k最短路径。整个过程就象网络中的一场涟漪扩散接力赛：初始涟漪从起点出 发在网络中各结点逐次激发出新涟漪，所有涟漪竞相向终点扩散，看谁最先到达终点。

要想通过一次性的涟漪扩散接力赛来完成(步骤3)，本发明的方法对传统的涟漪扩散算 法进行了以下两点主要改进：第一，因为(步骤3)要解决的是一个多到多前k条最短路径 问题，所以每个OD对的起点都会各产生一个初始涟漪，即，涟漪扩散接力赛不是从一个初始 涟漪开始，而是从多个初始涟漪开始；第二，如果从一个初始涟漪逐次激发出的某个新涟漪 所对应的当前路径长度已经大于该初始涟漪波源结点所在的所有OD对所对应的路径长度预 设值域上限最大值，则该新涟漪将消亡，即，该新涟漪将停止扩散而不再被考虑。

具体而言，本发明的方法的(步骤3)所改进的涟漪扩散算法包括以下几个主要步骤：

(步骤1)指定一个涟漪扩散速度常量v，为保证算法的最优性，v需满足如下条件：

0＜v≤min(CE(i，j))， (5)

即，v必须不大于网络系统中最短的链接长度；一般推荐取v＝min(CE(i，j))。

(步骤2)设当前仿真时刻为t＝0；初始化当前涟漪数为NR＝0；对每一个作为起点在任意 OD对中出现过(不管出现多少次，只要出现过就行)的结点n，在该结点产生一个初始涟漪， NR＝NR+1，该初始涟漪的起点设为RO(NR)＝n，波源结点设为RE(NR)＝n，半径设为RR(NR)＝0，当前 路径长度设为RCPL(NR)＝0，涟漪状态设为RS(NR)＝1(1表示活跃，0表示不活跃)，涟漪路径长 度上限设为起点为结点n的所有OD对所对应的路径长度预设值域上限最大值，记作RMaxR(NR)。

(步骤3)只要NR个涟漪中至少有一个涟漪的状态为1(即，活跃)，则循环进行以下子 步骤：

(步骤3.1)令t＝t+1；

(步骤3.2)对任意活跃涟漪r，即，如果RS(r)＝1，则其涟漪半径增加为RR(r)＝RR(r)+v， 即，涟漪半径按一个时间单位的扩散距离增加长度；

(步骤3.3)对所有的结点和活跃涟漪执行如下条件操作：如果活跃涟漪r的波源结点与 结点n之间有链接，即，A(RE(r)，n)＝1，并且如果RR(r)≥CE(RE(r)，n)，即，涟漪r到达了结 点n，那么，在结点n产生一个新涟漪，令NR＝NR+1，新涟漪起点为RO(NR)＝RO(r)，波源结点为 RE(NR)＝n，半径为RR(NR)＝RR(r)-CE(RE(r)，n)，当前路径长度为RCPL(NR)＝RCPL(r)+CE(RE(r)，n)，涟 漪状态设为RS(NR)＝1，涟漪路径长度上限为RMaxR(NR)＝RMaxR(r)；

(步骤3.4)对任何一个活跃涟漪r，如果其半径不小于从结点RE(r)出发的所有链接的 长度的最大值，则该涟漪变为不活跃，即，RS(r)＝0；

(步骤3.5)对任何一个活跃涟漪r，如果其当前路径长度大于其涟漪路径长度上限，即， 如果RCPL(r)＞RMaxR(r)，则该涟漪变为不活跃，即，RS(r)＝0。

(步骤4)对每一个作为终点在任意OD对中出现过的结点n，检查该结点所产生过的所 有涟漪：假设涟漪r是结点n产生过的一个涟漪，即，假设RE(r)＝n，那么，比较涟漪r的当 前路径长度RCPL(r)与以RO(r)为起点、以n为终点的OD对的路径长度预设值域，即，判断涟 漪r的当前路径长度是否满足相应的路径长度预设值域条件，如果满足，则回溯涟漪r所走 过的路径，就是一条满足系统抗干扰能力要求的路径；通过回溯所有OD对的终点所产生的所 有满足条件的涟漪所走过的路径，就可以得到网络系统中满足抗干扰能力要求的所有路径。

本发明的评估网络系统抗干扰能力的方法可以采用各种恰当的数学表述形式(例如，网 络中的链接可以不用邻接矩阵A表示，而是采用链接向量表的数据结构；所使用的各个变量 符号本身不是必须的，核心是变量的意义以及对变量的操作计算过程，例如，本发明的方法 所提出的涟漪扩散算法的(步骤3.2)中更新涟漪半径，即，RR(r)＝RR(r)+v，可以用任意变 量符号来改写，如，W(m)＝W(m)+z，甚至不用“涟漪”和“半径”这些词汇字眼，而是抽象地 说成：向量RR的第r个元素RR(r)增加v，其效果是一样的；所使用的常数值不是必须的，例 如，算法中在表示涟漪r的状态时，用RS(r)＝1表示活跃而RS(r)＝0表示不活跃，其实1和0 这两个常数值完全不是必须的，只要能区分出活跃状态和不活跃状态，可以给RS(r)赋任何常 数值)。

本发明的方法的步骤划分也可以适当调整，例如：本发明的方法所提出的涟漪扩散算法 的(步骤3.1)和(步骤3.2)可以合并成一个子步骤；如果不需要明确提示或使用仿真时间 变量t，(步骤2)中可以不用初始化仿真时间变量t＝0，(步骤3.1)可以完全删除。

本发明的评估网络系统抗干扰能力的方法具有以下有益效果：本发明的方法避免了“网 络系统是否会瓦解变成多个彼此独立的子网络系统”和“网络系统中的最优路线是否会受到 影响”这两种极端思路的局限性(即，要么局限于网络崩溃这一日常生活中的小概率事件考 虑，要么局限于完美主义的牛角尖)，实现了按“网络系统是否还能确保实现某种指定的最低 程度的系统功能”这一普适化思路来评估网络系统的抗干扰能力，从而非常符合现实需求， 能为网络系统的设计者和使用者提供对日常生活中常见情景有实用价值的决策支持；本发明 的方法通过模拟自然界的涟漪扩散现象在网络中开展一次性的涟漪扩散接力赛，从而实现在 一次性的运算中快速有效地求解出网络中各个OD对之间长度满足相应预设值域条件的所有 路径；本发明的方法既可以用于现实物理网络的抗干扰能力评估问题(例如：交通网、电网、 通讯网，等等)，又可以用于抽象虚拟网络的抗干扰能力评估问题(例如：决策树、生态网、 食物链，等等)。

附图给出本发明的评估网络系统抗干扰能力的方法的示意图：

图1：本发明的评估网络系统抗干扰能力的方法的主要步骤示意图。

图2：本发明的评估网络系统抗干扰能力的方法中用以求解所有OD对之间满足系统抗干 扰能力要求的所有路径的涟漪扩散算法的主要步骤示意图。

图3：本发明的评估网络系统抗干扰能力的方法与传统的评估方法之间的差别的示例图。

下面结合附图，对本发明的一种评估网络系统抗干扰能力的方法为解决评估网络系统在 各种干扰因素作用下是否还能确保实现按满足相应预设值域条件的路径长度连接各个起点终 点对(即，OD对)的能力的问题所采用的优选方式做进一步说明。

图1给出了本发明的评估网络系统抗干扰能力的方法所包括的主要步骤：

(步骤1)根据具体问题的要求，确定网络系统中要研究的所有起点终点对。

(步骤2)将网络系统抗干扰能力要求转化成对应各个OD对的路径长度预设值域，即， 根据具体问题的抗干扰能力要求，对每一个OD对，分别指定一个相应的路径长度预设值域。

(步骤3)对每一个OD对，出满足相应路径长度预设值域条件的所有路经，即，对每 一个OD对，出路径长度大于或不小于相应路径长度预设值域下限，并且小于或不大于相应 路径长度预设值域上限的所有路径。

(步骤4)统计所有OD对之间满足相应路径长度预设值域条件的所有路经中的结点和链 接的共享情况，包括：统计满足相应路径长度预设值域条件的路经的总数；统计网络系统中 各个结点以中间点(而非起点或终点)出现在满足相应路径长度预设值域条件的路经中的次 数；统计网络系统中各条链接出现在满足相应路径长度预设值域条件的路经中的次数；统计 网络系统中各个结点以中间点出现在每一个OD对的满足相应路径长度预设值域条件的路经 中的次数；统计网络系统中各条链接出现在每一个OD对的满足相应路径长度预设值域条件的 路经中的次数。

(步骤5)基于(步骤4)所得到的统计数据，根据具体问题的类型和特点，分析各OD 对之间满足相应路径长度预设值域条件的所有路经在各种干扰因素作用下全部断开的可能 性。

本发明的方法中的(步骤3)是关键和难点所在，需要快速有效地求解出所有OD对之间 满足系统抗干扰能力要求的所有路径。为此，本发明的方法为(步骤3)进一步提出了一种 通过一次性运行就能到所有满足系统抗干扰能力要求的路径的涟漪扩散算法，图2给出了 该涟漪扩散算法所包括的主要步骤：

(步骤1)选定一个合适的涟漪扩散速度常量v。涟漪扩散算法中的所有涟漪都将按这一 相同的速度v进行扩散。需要强调的是：在某些具体网络问题中，不同链接所允许的速度可 能是不一样的，但这并不影响扩散速度常量v的使用，因为对于不同链接允许不同速度的网 络问题，先出所有链接所允许的最大速度，再按最大速度与各链接所允许速度的比值来相 应增大链接权重，例如，假设最大速度是链接A(i，j)的允许速度的3倍，则该链接的权重值 需要调整为CE(i，j)＝3×CE(i，j)，然后基于调整后所有链接的权重值再根据条件(5)来选定 扩散速度常量v。

(步骤2)设当前仿真时刻为t＝0；初始化当前涟漪数为NR＝0；对每一个作为起点在任意 OD对中出现过(不管出现多少次，只要出现过就行)的结点n，在该结点产生一个初始涟漪， NR＝NR+1，该初始涟漪的起点设为RO(NR)＝n，波源结点设为RE(NR)＝n，半径设为RR(NR)＝0，当前 路径长度设为RCPL(NR)＝0，涟漪状态设为RS(NR)＝1(1表示活跃，0表示不活跃)，涟漪路径长 度上限设为起点为结点n的所有OD对所对应的路径长度预设值域上限最大值，记作RMaxR(NR)。 需要强调的是：虽然本说明书里选用数值“1”表示涟漪状态为活跃，数值“0”表示涟漪状 态为不活跃，但是在具体应用本发明的方法时，可以灵活选用任何数值来标示区分涟漪是否 活跃。

(步骤3)检查所有NR个涟漪中是否还有活跃涟漪？只要NR个涟漪中至少有一个涟漪的 状态为活跃，则循环进行以下子步骤：

(步骤3.1)仿真时间t增加一个仿真时间单位，即，t＝t+1(需要指出的是：这里使用仿 真时间t是为了清楚地显示出涟漪扩散接力赛是一个随仿真时间而变化的动态过程，从而有 助于理解方法和调试程序；如果不需要明确提示仿真时间的变化，则可以不用仿真时间t而省 去这一子步骤)；

(步骤3.2)对任意活跃涟漪r，即，如果RS(r)＝1，则其涟漪半径增加为RR(r)＝RR(r)+v， 即，涟漪半径按一个仿真时间单位的扩散距离增加长度；

(步骤3.3)对所有的结点和活跃涟漪执行如下条件操作：如果活跃涟漪r的波源结点与 结点n之间有链接，即，A(RE(r)，n)＝1，并且如果RR(r)≥CE(RE(r)，n)，即，涟漪r到达了结 点n，那么，在结点n产生一个新涟漪，令NR＝NR+1，新涟漪起点为RO(NR)＝RO(r)，波源结点为 RE(NR)＝n，半径为RR(NR)＝RR(r)-CE(RE(r)，n)，当前路径长度为RCPL(NR)＝RCPL(r)+CE(RE(r)，n)，涟 漪状态设为RS(NR)＝1，涟漪路径长度上限为RMaxR(NR)＝RMaxR(r)；

(步骤3.4)对任何一个活跃涟漪r，如果其半径不小于从结点RE(r)出发的所有链接的 长度的最大值，则该涟漪变为不活跃，即，RS(r)＝0(将此类涟漪的状态改变设置为不活跃， 可以大大提高算法的运算速度，因为即便此类涟漪继续扩散，也不能激发出任何新涟漪，所以 如果继续对此类涟漪进行扩散运算将只是浪费计算硬件的计算资源)；

(步骤3.5)对任何一个活跃涟漪r，如果其当前路径长度大于其涟漪路径长度上限，即， 如果RCPL(r)＞RMaxR(r)，则该涟漪变为不活跃，即，RS(r)＝0(将此类涟漪的状态改变设置为不 活跃，也可以大大提高算法的运算速度，因为如果此类涟漪继续扩散，所到的新路径也只 会是不满足系统抗干扰能力要求的路径，对评估系统抗干扰能力没有额外价值，所以如果继 续对此类涟漪进行扩散运算将也只是浪费计算硬件的计算资源)。

(步骤4)对每一个作为终点在任意OD对中出现过的结点n，检查该结点所产生过的所 有涟漪：假设涟漪r是结点n产生过的一个涟漪，即，假设RE(r)＝n，那么，比较涟漪r的当 前路径长度RCPL(r)与以RO(r)为起点、以n为终点的OD对的路径长度预设值域，即，判断涟 漪r的当前路径长度是否满足相应的路径长度预设值域条件，如果满足，则回溯涟漪r所走 过的路径，就是一条满足系统抗干扰能力要求的路径；通过回溯所有OD对的终点所产生的所 有满足相应路径长度预设值域条件的涟漪所走过的路径，就可以得到网络系统中满足抗干扰 能力要求的所有路径。

图3给出了本发明的评估网络系统抗干扰能力的方法与传统的评估方法之间的差别的一 个简单示例。在图3的示例中，网络系统只有一个OD对，该OD对之间总共有5条路径。在 评估干扰因素对网络系统连通该OD对的能力的影响时，传统的评估方法要么按“网络系统是 否会瓦解变成多个彼此独立的子网络系统”这一极端思路进行，即，图3左边部分所示例的 极端情况1；要么按“网络系统中的最优路线是否会受到影响”这一极端思路进行，即，图3 右边部分所示例的极端情况2。按图3中极端情况1评估，需要分析干扰因素使该OD对之间 所有5条路径全部同时断开的可能性。按图3中极端情况2评估，需要分析干扰因素使该OD 对之间的最短路径断开的可能性。本发明的方法则是按普适情况进行评估网络系统的抗干扰 能力，需要分析干扰因素使该OD对之间所有长度小于某预设阈值的路径全部同时断开的可能 性，即，图3中间部分所示例的普适情况，需要分析干扰因素使该OD对之间的前3条最短路 径全部同时断开的可能性。进一步将图3的示例放在一个从起点赶往终点去开会的实际场景 中理解，极端情况1考虑的问题是：路网断开导致根本无法从起点到达终点的可能性；极端 情况2考虑的问题是：路网故障导致无法走最短路径从起点赶到终点的可能性；普适情况考 虑的问题是：路网故障导致无法从起点按时(例如：在上午10点钟以前)赶到终点的可能性。 现实生活中的参会者真正关心的是哪个问题呢？显然，是“能否按时赶到会场出席会议”的 问题。图3的示例说明，本发明的方法能够有效地解决现实生活中对网络系统抗干扰能力的 正真关切问题。