《复杂网络抗毁性优化算法的设计与实现》由会员分享，可在线阅读，更多相关《复杂网络抗毁性优化算法的设计与实现（18页珍藏版）》请在金锄头文库上搜索。
1、复杂网络抗毁性优化算法的设计与实现复杂网络抗毁性优化算法的设计与实现冯颜冯颜冯颜冯颜 张琨张琨张琨张琨 黄奉孝黄奉孝黄奉孝黄奉孝 邹勇鑫邹勇鑫邹勇鑫邹勇鑫南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院目目 录录 引引引引 言言言言1 复杂网络抗毁性优化算法复杂网络抗毁性优化算法复杂网络抗毁性优化算法复杂网络抗毁性优化算法2 算法分析与实现算法分析与实现算法分析与实现算法分析与实现3 实实实实 例例例例 分分分分 析析析析4南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院1. 引引 言言v 研究意义研究意义研究意义研究意义 无尺度
2、网络的双重特性：无尺度网络的双重特性：无尺度网络的双重特性：无尺度网络的双重特性： 对对对对随机失效随机失效随机失效随机失效的鲁棒性的鲁棒性的鲁棒性的鲁棒性& &对对对对选择性攻击选择性攻击选择性攻击选择性攻击的脆弱性的脆弱性的脆弱性的脆弱性 复杂网络抗毁性优化算法的设计与实现对提高现实世界复杂网络抗毁性优化算法的设计与实现对提高现实世界复杂网络抗毁性优化算法的设计与实现对提高现实世界复杂网络抗毁性优化算法的设计与实现对提高现实世界中各种网络的抗毁性有着更为重要的应用价值。中各种网络的抗毁性有着更为重要的应用价值。中各种网络的抗毁性有着更为重要的应用价值。中各种网络的抗毁性有着更为重要的应用价
3、值。v两个关键技术两个关键技术两个关键技术两个关键技术 一、生成高度为一、生成高度为一、生成高度为一、生成高度为K/2K/2K/2K/2的最小生成树：的最小生成树：的最小生成树：的最小生成树： 满足网络的节点间跳数不大于满足网络的节点间跳数不大于满足网络的节点间跳数不大于满足网络的节点间跳数不大于K K K K的要求；的要求；的要求；的要求； 二、对高度为二、对高度为二、对高度为二、对高度为K/2K/2K/2K/2的最小生成树进行优化：的最小生成树进行优化：的最小生成树进行优化：的最小生成树进行优化： 满足连通度为满足连通度为满足连通度为满足连通度为2 2 2 2的要求。的要求。的要求。的要求
4、。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院1. 引引 言言 在现实应用中，几乎所有的复杂系统都可以抽象为复杂在现实应用中，几乎所有的复杂系统都可以抽象为复杂在现实应用中，几乎所有的复杂系统都可以抽象为复杂在现实应用中，几乎所有的复杂系统都可以抽象为复杂网络模型。网络模型。网络模型。网络模型。 随着复杂网络的小世界效应及无标度特性的发现，复杂随着复杂网络的小世界效应及无标度特性的发现，复杂随着复杂网络的小世界效应及无标度特性的发现，复杂随着复杂网络的小世界效应及无标度特性的发现，复杂网络研究逐渐成为多个学科共同关注的前沿热点。网络研究逐渐成为多个学科共同关注的前沿热点。网
5、络研究逐渐成为多个学科共同关注的前沿热点。网络研究逐渐成为多个学科共同关注的前沿热点。 一旦网络的某个关键节点发生故障，将会给网络的用户一旦网络的某个关键节点发生故障，将会给网络的用户一旦网络的某个关键节点发生故障，将会给网络的用户一旦网络的某个关键节点发生故障，将会给网络的用户带来不便，有时甚至会导致非常严重的后果。带来不便，有时甚至会导致非常严重的后果。带来不便，有时甚至会导致非常严重的后果。带来不便，有时甚至会导致非常严重的后果。 为了使在蓄意破坏的情况下，网络故障带给用户的损失为了使在蓄意破坏的情况下，网络故障带给用户的损失为了使在蓄意破坏的情况下，网络故障带给用户的损失为了使在蓄意破
6、坏的情况下，网络故障带给用户的损失减到最小，必须采取一定的措施使网络在发生故障后能减到最小，必须采取一定的措施使网络在发生故障后能减到最小，必须采取一定的措施使网络在发生故障后能减到最小，必须采取一定的措施使网络在发生故障后能够继续提供一定的服务。够继续提供一定的服务。够继续提供一定的服务。够继续提供一定的服务。1. 引 言南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院2. 复杂网络抗毁性优化算法复杂网络抗毁性优化算法v 2.1 2.1 抗毁性优化算法设计目标抗毁性优化算法设计目标抗毁性优化算法设计目标抗毁性优化算法设计目标 主要手段：主要手段：主要手段：主要手段：在网络中增
7、加在网络中增加在网络中增加在网络中增加足够多足够多足够多足够多的备份链路和备份设备。的备份链路和备份设备。的备份链路和备份设备。的备份链路和备份设备。 设计目标：设计目标：设计目标：设计目标：忽略网络带宽的因素，用最少的成本建设一忽略网络带宽的因素，用最少的成本建设一忽略网络带宽的因素，用最少的成本建设一忽略网络带宽的因素，用最少的成本建设一个最小连通度为个最小连通度为个最小连通度为个最小连通度为2 2的网络。该网络中任意一条传输链路中的网络。该网络中任意一条传输链路中的网络。该网络中任意一条传输链路中的网络。该网络中任意一条传输链路中断后，任意两个节点间的最大跳数仍不超过断后，任意两个节点间
8、的最大跳数仍不超过断后，任意两个节点间的最大跳数仍不超过断后，任意两个节点间的最大跳数仍不超过K K。 图论表示：图论表示：图论表示：图论表示：给定的无向图给定的无向图给定的无向图给定的无向图G(VG(V，E)E)以及每条边的开销以及每条边的开销以及每条边的开销以及每条边的开销CeCe，寻找一个最小连通度为，寻找一个最小连通度为，寻找一个最小连通度为，寻找一个最小连通度为2 2的最小开销子图；去除子图中的最小开销子图；去除子图中的最小开销子图；去除子图中的最小开销子图；去除子图中任意一条边后，子图中任意两个节点间的跳数不大于任意一条边后，子图中任意两个节点间的跳数不大于任意一条边后，子图中任意
9、两个节点间的跳数不大于任意一条边后，子图中任意两个节点间的跳数不大于K K。 目前在国内这类算法主要有刘丽娟提出的优化目前在国内这类算法主要有刘丽娟提出的优化目前在国内这类算法主要有刘丽娟提出的优化目前在国内这类算法主要有刘丽娟提出的优化IEIE模型算模型算模型算模型算法、法、法、法、WangWang等提出的熵优化模型算法以及刘啸林提出的等提出的熵优化模型算法以及刘啸林提出的等提出的熵优化模型算法以及刘啸林提出的等提出的熵优化模型算法以及刘啸林提出的基于生成树优化算法等。基于生成树优化算法等。基于生成树优化算法等。基于生成树优化算法等。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技
10、术学院2. 复杂网络抗毁性优化算法复杂网络抗毁性优化算法v 2.2 2.2 算法思想算法思想算法思想算法思想 考虑实际的建网开销和网络使用过程情况，抗毁性优化考虑实际的建网开销和网络使用过程情况，抗毁性优化考虑实际的建网开销和网络使用过程情况，抗毁性优化考虑实际的建网开销和网络使用过程情况，抗毁性优化后的网络应至少符合以下四点要求：后的网络应至少符合以下四点要求：后的网络应至少符合以下四点要求：后的网络应至少符合以下四点要求： （1 1）连通度为）连通度为）连通度为）连通度为2 2； （2 2）网络的节点间跳数不能大于）网络的节点间跳数不能大于）网络的节点间跳数不能大于）网络的节点间跳数不能大
11、于KK值；值；值；值； （3 3）建网总开销值相对较小；）建网总开销值相对较小；）建网总开销值相对较小；）建网总开销值相对较小； （4 4）网络实际使用时，与网络的一个节点）网络实际使用时，与网络的一个节点）网络实际使用时，与网络的一个节点）网络实际使用时，与网络的一个节点v vi i相连的一条相连的一条相连的一条相连的一条边故障后，需通过另一条边即备份链路进行通信，以保边故障后，需通过另一条边即备份链路进行通信，以保边故障后，需通过另一条边即备份链路进行通信，以保边故障后，需通过另一条边即备份链路进行通信，以保持网络正常工作；同时还需要保证其他各点到持网络正常工作；同时还需要保证其他各点到持
12、网络正常工作；同时还需要保证其他各点到持网络正常工作；同时还需要保证其他各点到v vi i的开销的开销的开销的开销和相对较小。和相对较小。和相对较小。和相对较小。 基于上述四点要求，算法涉及的相关定义如下：基于上述四点要求，算法涉及的相关定义如下：基于上述四点要求，算法涉及的相关定义如下：基于上述四点要求，算法涉及的相关定义如下：南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院2. 复杂网络抗毁性优化算法复杂网络抗毁性优化算法 定义定义定义定义1 1 网络拓扑结构：网络拓扑结构：网络拓扑结构：网络拓扑结构：用邻接矩阵表示的无向图用邻接矩阵表示的无向图用邻接矩阵表示的无向图用邻接
13、矩阵表示的无向图G G( (V V，E E) )；顶点集合顶点集合顶点集合顶点集合V=V=( (v v1 1, , v v2 2, , , v vn n) )，边集合，边集合，边集合，边集合e=e=( (e e1 1, , e e2 2, , , e en n ) ) ，e eij ij=v= ； 定义定义定义定义2 2 旁亲父节点：旁亲父节点：旁亲父节点：旁亲父节点：比节点比节点比节点比节点v vi i的层次值小（即级别比的层次值小（即级别比的层次值小（即级别比的层次值小（即级别比v vi i高），且不在同一条枝上的所有其高），且不在同一条枝上的所有其高），且不在同一条枝上的所有其高），且不
14、在同一条枝上的所有其他节点。例如图他节点。例如图他节点。例如图他节点。例如图1(b)1(b)中节点中节点中节点中节点v v3 3的旁亲父节点为的旁亲父节点为的旁亲父节点为的旁亲父节点为v v0 0，v v1 1，v v5 5。 定义定义定义定义3 3 最佳生成树：最佳生成树：最佳生成树：最佳生成树： 满足高度为满足高度为满足高度为满足高度为K/2K/2，且开销和相对最小的生成树。，且开销和相对最小的生成树。，且开销和相对最小的生成树。，且开销和相对最小的生成树。图图1 (a) 给给定一个无向定一个无向图图 (b) 根根为为v6时时的最小生成的最小生成树树南京理工大学计算机科学与技术学院南京理工
15、大学计算机科学与技术学院2. 复杂网络抗毁性优化算法复杂网络抗毁性优化算法 定义定义定义定义4 4 节点节点节点节点v vi i的层次的层次的层次的层次Q Qi i： 生成树的根定义为第生成树的根定义为第生成树的根定义为第生成树的根定义为第0 0层，与根节点直接连接的节点定义为第层，与根节点直接连接的节点定义为第层，与根节点直接连接的节点定义为第层，与根节点直接连接的节点定义为第l l层，层，层，层，依此类推生成树的叶子节点为第依此类推生成树的叶子节点为第依此类推生成树的叶子节点为第依此类推生成树的叶子节点为第D D层层层层Q Qd d。对节点的优化又分为下述两种情况：对节点的优化又分为下述两
16、种情况：对节点的优化又分为下述两种情况：对节点的优化又分为下述两种情况： (1) (1) 对叶子节点对叶子节点对叶子节点对叶子节点v vd d进行优化进行优化进行优化进行优化，增加边增加边增加边增加边e edjdj，节点，节点，节点，节点v vj j要满足下述条件要满足下述条件要满足下述条件要满足下述条件: : 节点节点节点节点v vj j的层次的层次的层次的层次Q Qj j D-1 D-1； 节点节点节点节点v vj j与与与与v vd d的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点v v0
17、0，或，或，或，或v vj j就是就是就是就是根节点根节点根节点根节点v v0 0 。 (2) (2) 对非叶子节点对非叶子节点对非叶子节点对非叶子节点v vi i进行优化进行优化进行优化进行优化，增加边增加边增加边增加边e edjdj，节点，节点，节点，节点v vj j要满足下述条件要满足下述条件要满足下述条件要满足下述条件: : 若节点若节点若节点若节点v vi i的层次的层次的层次的层次Q Qi i k k，那么节点，那么节点，那么节点，那么节点v vj j的层次的层次的层次的层次Q Qj j k k，此条件保证不会，此条件保证不会，此条件保证不会，此条件保证不会由于与节点由于与节点由于
18、与节点由于与节点v vj j的连接而导致跳数超限；的连接而导致跳数超限；的连接而导致跳数超限；的连接而导致跳数超限； 节点节点节点节点v vj j与与与与v vi i的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点的公共父节点只有一个，而且仅是根节点v v0 0，或，或，或，或v vj j就是就是就是就是根节点根节点根节点根节点v v0 0。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院2. 复杂网络抗毁性优化算法复杂网络抗毁性优化算法 定义定义定义定义5 5 网络开销和网络开销和网络开销和网络开销和addCosta
19、ddCost( (G G) )：带权无向图带权无向图带权无向图带权无向图GG的各边权值总和。如图的各边权值总和。如图的各边权值总和。如图的各边权值总和。如图1(a)1(a)所代表的网络开销和为所代表的网络开销和为所代表的网络开销和为所代表的网络开销和为1919。 定义定义定义定义6 6 节点节点节点节点v vi i的开销和的开销和的开销和的开销和addCostaddCost( (v vi i) )：网络中所有其他节点到网络中所有其他节点到网络中所有其他节点到网络中所有其他节点到v vi i节点的链路开销之和。节点的链路开销之和。节点的链路开销之和。节点的链路开销之和。例如，例如，addCost
20、(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21 定义定义定义定义7 7 换路换路换路换路：当层次值当层次值当层次值当层次值Q Qi i K K/2/2的节点与其父节点的连接断开时，从原无向图中重的节点与其父节点的连接断开时，从原无向图中重的节点与其父节点的连接断开时，从原无向图中重的节点与其父节点的连接断开时，从原无向图中重新选择一条边并连接，使得节点新选择一条边并连接，使得节点新选择一条边并连接，使得节点新选择一条边并连接，使得节点v vi i在新图中的层次值在新图中的层次值在新图中的层次值在新图中的层次值Q Qi i 1, 1, K K/2/2，
21、并且保证这条新的边是权值相对最小的一条。并且保证这条新的边是权值相对最小的一条。并且保证这条新的边是权值相对最小的一条。并且保证这条新的边是权值相对最小的一条。图图1 (b) 根根为为v6时时的最小生成的最小生成树树 图图2 换换路后得到的路后得到的图图南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院3. 算法分析与实现算法分析与实现v3.1 3.1 求最佳生成树的三种求法求最佳生成树的三种求法求最佳生成树的三种求法求最佳生成树的三种求法 ( (1) 1) “ “修改过的修改过的修改过的修改过的primprim算法算法算法算法” ”算法思想：算法思想：算法思想：算法思想：在在在
22、在primprim生成树的每步过程中判断加入的节点生成树的每步过程中判断加入的节点生成树的每步过程中判断加入的节点生成树的每步过程中判断加入的节点的层次，如果大于的层次，如果大于的层次，如果大于的层次，如果大于K/2K/2就停止此步，通过其他的相对最小的就停止此步，通过其他的相对最小的就停止此步，通过其他的相对最小的就停止此步，通过其他的相对最小的边连接此节点，并继续判断，直到结束。边连接此节点，并继续判断，直到结束。边连接此节点，并继续判断，直到结束。边连接此节点，并继续判断，直到结束。时间复杂度时间复杂度时间复杂度时间复杂度：O O( (N N N N N N N N 2 2 2 2) )
23、 (2) (2) “ “primprim算法试探算法试探算法试探算法试探+ +换路换路换路换路” ”的方法的方法的方法的方法” ”算法思想：算法思想：算法思想：算法思想：对给出的一个完全图对给出的一个完全图对给出的一个完全图对给出的一个完全图MGMG，每个节点都作为根，每个节点都作为根，每个节点都作为根，每个节点都作为根执行执行执行执行primprim算法进行试探，找到使生成树高度达到最小的那算法进行试探，找到使生成树高度达到最小的那算法进行试探，找到使生成树高度达到最小的那算法进行试探，找到使生成树高度达到最小的那个根节点。找到此根节点后，对此生成树中高度大于个根节点。找到此根节点后，对此生
24、成树中高度大于个根节点。找到此根节点后，对此生成树中高度大于个根节点。找到此根节点后，对此生成树中高度大于K K/2/2的的的的节点进行节点进行节点进行节点进行“ “换路换路换路换路” ”。时间复杂度时间复杂度时间复杂度时间复杂度：O O( (N N N N N N N N 2 2 2 2) )。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院3. 算法分析与实现算法分析与实现v3.1 3.1 求最佳生成树的三种求法求最佳生成树的三种求法求最佳生成树的三种求法求最佳生成树的三种求法 (3) (3) “ “一次一次一次一次prim+prim+换路换路换路换路” ”的方法的方法的方
25、法的方法” ”算法思想：算法思想：算法思想：算法思想：对一个给出的完全图对一个给出的完全图对一个给出的完全图对一个给出的完全图MGMG，任意选取一个节，任意选取一个节，任意选取一个节，任意选取一个节点作为根，执行点作为根，执行点作为根，执行点作为根，执行primprim算法求最小生成树，然后扭转此树，算法求最小生成树，然后扭转此树，算法求最小生成树，然后扭转此树，算法求最小生成树，然后扭转此树，找到使得生成树高度达到最小的那个根节点。寻根前后树找到使得生成树高度达到最小的那个根节点。寻根前后树找到使得生成树高度达到最小的那个根节点。寻根前后树找到使得生成树高度达到最小的那个根节点。寻根前后树的
26、拓扑结构是不变的。的拓扑结构是不变的。的拓扑结构是不变的。的拓扑结构是不变的。时间复杂度时间复杂度时间复杂度时间复杂度：O O( (N N N N 2 2 2 2) ) 通过时间复杂度的比较，本文采用第三种方法。通过时间复杂度的比较，本文采用第三种方法。通过时间复杂度的比较，本文采用第三种方法。通过时间复杂度的比较，本文采用第三种方法。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院3. 算法分析与实现算法分析与实现v3.2 3.2 生成树节点的优化生成树节点的优化生成树节点的优化生成树节点的优化得到高度为得到高度为得到高度为得到高度为K/2K/2的的的的“ “最佳生成树之后最
27、佳生成树之后最佳生成树之后最佳生成树之后” ”，针对，针对，针对，针对KK是奇数或偶数两种情是奇数或偶数两种情是奇数或偶数两种情是奇数或偶数两种情况对节点进行优化：况对节点进行优化：况对节点进行优化：况对节点进行优化： K K为偶数为偶数为偶数为偶数(1) (1) 对叶子节点对叶子节点对叶子节点对叶子节点v vi i的优化方法：的优化方法：的优化方法：的优化方法：从旁亲父节点集合中选择一个最优的从旁亲父节点集合中选择一个最优的从旁亲父节点集合中选择一个最优的从旁亲父节点集合中选择一个最优的v vj j节点节点节点节点( (开销值最小开销值最小开销值最小开销值最小) )，增加边增加边增加边增加边
28、e eij ij ；(2) (2) 对非叶子节点对非叶子节点对非叶子节点对非叶子节点v vi i的优化方法：的优化方法：的优化方法：的优化方法：从相同层次值或层次值小于自己的旁枝节点集合中选择一个最优的从相同层次值或层次值小于自己的旁枝节点集合中选择一个最优的从相同层次值或层次值小于自己的旁枝节点集合中选择一个最优的从相同层次值或层次值小于自己的旁枝节点集合中选择一个最优的v vj j节点，节点，节点，节点，增加边增加边增加边增加边e eij ij 。 K K为奇数为奇数为奇数为奇数从同级别（即高度相同）或比自己级别高（节点层次值小于自己）从同级别（即高度相同）或比自己级别高（节点层次值小于自
29、己）从同级别（即高度相同）或比自己级别高（节点层次值小于自己）从同级别（即高度相同）或比自己级别高（节点层次值小于自己）的节点集合中选择一个最优的的节点集合中选择一个最优的的节点集合中选择一个最优的的节点集合中选择一个最优的v vj j节点，节点，节点，节点，增加边增加边增加边增加边e eij ij 。根节点无需优化，实际网络中对重要的根节点进行信息备份即可。根节点无需优化，实际网络中对重要的根节点进行信息备份即可。根节点无需优化，实际网络中对重要的根节点进行信息备份即可。根节点无需优化，实际网络中对重要的根节点进行信息备份即可。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院
30、3. 算法分析与实现算法分析与实现v3.3 3.3 两种优化参数的方法及比较两种优化参数的方法及比较两种优化参数的方法及比较两种优化参数的方法及比较在节点优化算法过程中，本文给出两种从备选节点集合在节点优化算法过程中，本文给出两种从备选节点集合在节点优化算法过程中，本文给出两种从备选节点集合在节点优化算法过程中，本文给出两种从备选节点集合 v vj j 中寻找最中寻找最中寻找最中寻找最优备份链路的方法。两种方法的区别在于选取备份链路时界定优备份链路的方法。两种方法的区别在于选取备份链路时界定优备份链路的方法。两种方法的区别在于选取备份链路时界定优备份链路的方法。两种方法的区别在于选取备份链路时
31、界定“ “最优最优最优最优” ”的标准不同，也具有不同的实际意义。的标准不同，也具有不同的实际意义。的标准不同，也具有不同的实际意义。的标准不同，也具有不同的实际意义。 根据根据根据根据“ “最小开销值最小开销值最小开销值最小开销值” ”这种方法很简单，且目的性很明确，直接比较这种方法很简单，且目的性很明确，直接比较这种方法很简单，且目的性很明确，直接比较这种方法很简单，且目的性很明确，直接比较v vi i与与与与备选节点集合备选节点集合备选节点集合备选节点集合 v vj j 中的各个节点之间链路的开销，选取最小的那条链路作为备份。中的各个节点之间链路的开销，选取最小的那条链路作为备份。中的各
32、个节点之间链路的开销，选取最小的那条链路作为备份。中的各个节点之间链路的开销，选取最小的那条链路作为备份。优点：优点：优点：优点：实现简单；实现简单；实现简单；实现简单；缺点：缺点：缺点：缺点：只能保证建网的初始开销较小，没有完全考虑链路出现故障只能保证建网的初始开销较小，没有完全考虑链路出现故障只能保证建网的初始开销较小，没有完全考虑链路出现故障只能保证建网的初始开销较小，没有完全考虑链路出现故障后的实际情况。后的实际情况。后的实际情况。后的实际情况。 根据根据根据根据“ “节点节点节点节点v vi i的开销和的开销和的开销和的开销和” ”用用用用“ “节点节点节点节点v vi i的开销和的
33、开销和的开销和的开销和” ”来评估来评估来评估来评估v vj j节点，这个值越小越好，根据这个值节点，这个值越小越好，根据这个值节点，这个值越小越好，根据这个值节点，这个值越小越好，根据这个值选择出最佳的那个选择出最佳的那个选择出最佳的那个选择出最佳的那个v vj j。优点：优点：优点：优点：网络不仅在建网初期开销值较小，而且在网络出现故障时，网络不仅在建网初期开销值较小，而且在网络出现故障时，网络不仅在建网初期开销值较小，而且在网络出现故障时，网络不仅在建网初期开销值较小，而且在网络出现故障时，仍能通过最节省开销的备份链路，维护网络的正常工作。仍能通过最节省开销的备份链路，维护网络的正常工作
34、。仍能通过最节省开销的备份链路，维护网络的正常工作。仍能通过最节省开销的备份链路，维护网络的正常工作。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院4.实例分析实例分析v原始网络原始网络原始网络原始网络以一个节点数为以一个节点数为以一个节点数为以一个节点数为9 9的带权无向图为例，开销矩阵如表的带权无向图为例，开销矩阵如表的带权无向图为例，开销矩阵如表的带权无向图为例，开销矩阵如表1 1；优化目标：优化目标：优化目标：优化目标：K K=4=4，寻找一个最小连通度为，寻找一个最小连通度为，寻找一个最小连通度为，寻找一个最小连通度为2 2的最小开销子图，同时在的最小开销子图，同时
35、在的最小开销子图，同时在的最小开销子图，同时在去除子图中任意一条边后，子图中任意两个节点间的跳数不大于去除子图中任意一条边后，子图中任意两个节点间的跳数不大于去除子图中任意一条边后，子图中任意两个节点间的跳数不大于去除子图中任意一条边后，子图中任意两个节点间的跳数不大于4 4。v0v1v2v3v4v5v6v7v8v0025157448v12063129105v2560257645v31320610783v4515604362v57271040258v6496732047v74104865409v8855328790表表1 网网络络的开的开销销矩矩阵阵南京理工大学计算机科学与技术学院南京理工大学
36、计算机科学与技术学院4.实例分析实例分析v三种方法求最佳生成树三种方法求最佳生成树三种方法求最佳生成树三种方法求最佳生成树图图3 三种方法求最佳生成三种方法求最佳生成树树(a) 修改过的修改过的prim算法算法 (b) 最佳根节点为最佳根节点为v0(c) 换路后的生成树换路后的生成树南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院4.实例分析实例分析v用两种参数优化生成树用两种参数优化生成树用两种参数优化生成树用两种参数优化生成树图图4 用两种参数用两种参数优优化生成化生成树树(a) 根据根据“最小开销值最小开销值”选择备份链路选择备份链路(b) 根据根据“节点节点vi的开销和
37、的开销和” 选择备份链路选择备份链路南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院结结 束束 语语 本文用最少的成本建设了一个连通度为本文用最少的成本建设了一个连通度为本文用最少的成本建设了一个连通度为本文用最少的成本建设了一个连通度为2 2 2 2的网络，并且的网络，并且的网络，并且的网络，并且保证当网络中一条传输链路中断后，任意两个节点间的保证当网络中一条传输链路中断后，任意两个节点间的保证当网络中一条传输链路中断后，任意两个节点间的保证当网络中一条传输链路中断后，任意两个节点间的最大跳数不超过最大跳数不超过最大跳数不超过最大跳数不超过K K K K。该算法在对大中型网络
38、的规划设计。该算法在对大中型网络的规划设计。该算法在对大中型网络的规划设计。该算法在对大中型网络的规划设计或者优化扩容时具有一定的实际应用价值。或者优化扩容时具有一定的实际应用价值。或者优化扩容时具有一定的实际应用价值。或者优化扩容时具有一定的实际应用价值。 现有对节点失效的研究中，很少考虑节点本身具有一定现有对节点失效的研究中，很少考虑节点本身具有一定现有对节点失效的研究中，很少考虑节点本身具有一定现有对节点失效的研究中，很少考虑节点本身具有一定的主动防御能力和自我修复能力。本课题组下一步的工的主动防御能力和自我修复能力。本课题组下一步的工的主动防御能力和自我修复能力。本课题组下一步的工的主动防御能力和自我修复能力。本课题组下一步的工作将从此方向展开。作将从此方向展开。作将从此方向展开。作将从此方向展开。
