复杂网络可靠性研究

1、复杂(fz)网络可靠性研究国防科技大学信息系统与管理(gunl)学院 谭跃进1共一百四十一页我们被网络包围着，几乎所有(suyu)的复杂系统都可以抽象成网络模型，这些网络往往具有大量的节点，节点之间有着复杂的连接关系。2共一百四十一页报告(bogo)内容复杂网络可靠性概述指标体系与模型(mxng)复杂网络可靠性的有关研究内容网络可靠性研究方法论3共一百四十一页报告(bogo)内容复杂(fz)网络可靠性概述指标体系与模型复杂网络可靠性的有关研究内容网络可靠性研究的方法论4共一百四十一页1 复杂(fz)网络可靠性概述无标度网络(wnglu)的双重性复杂网络抗毁性举例复杂网络可靠性定义5共一百四十一

2、页无标度(bio d)网络的双重性无标度网络定义1998年，印第安纳州圣母(shngm)大学物理学教授巴拉巴斯及其同事在对万维网拓扑结构进行研究时发现，考察的情况比随机网络所描述的要复杂，即钟形曲线的连接平均数或标度不见了，它所产生的是一条不断递减的曲线。巴拉巴斯把具有这种性质的网络称之为无标度网络（scale-free networks）。 无标度网络的双重性生机勃勃：无标度网络在随机打击下，生机勃勃，抗毁能力很强脆 弱：在智能打击下，无标度网络显得异常脆弱6共一百四十一页无标度(bio d)网络的双重性巴拉巴斯等人把无标度网络置于两种类型的打击之下（随机打击、智能打击）。在前一种打击中，他

3、们随机地攻击了个别的节点，在后一种中，则仅仅拿掉了这些活动中心网络中四通八达的节点。在随机打击下，随机网络很容易遭受伤害。由于越来越多的节点被摧毁，所以从一个(y )节点到达另外一个(y )所需的步骤数量稳步增加。与此形成对照，无标度网络在这种打击面前则生机勃勃，抗毁能力很强。在智能打击下，随机网络的衰败方式与在随机打击下相同。但无标度网络一旦5的活动中心被去除，穿越网络所需的步骤数量就增加一倍。巴拉巴斯说：“这表明无标度网络总的来说很容易受到智能打击伤害。”7共一百四十一页复杂网络(wnglu)抗毁性举例之一美加电网的大崩溃事故已经过去一年了，或许瞬间的黑暗并没有使远在亚洲的我们感受到纽约人

4、的惊栗，但是网络中无意或有意生成的安全隐患却令人无法逃避。面对与生活日渐亲密的网络，我们不禁要问： “网络到底(do d)有多可靠？” 8共一百四十一页复杂(fz)网络抗毁性举例之一北美电力网是一个由大型发电厂为集散节点，以主干电力网相互连接起来的类似无标度网络的高度集群电网。由于他们使用的是同步交流电网，只要一家电厂出事，频率异动就会瞬间波及全网。美加电网的崩溃清楚地解释了“集群现象”，并且极其吻合无标度网络理论对集散节点的定义和因此而形成的对于网络安全特性的估计。虽然所有对电力网络的研究(ynji)工作还不能确定美加电网就是一种“无标度网络”，但有一点已经明确，那就是电力网是一个复杂的网络

5、系统，对网络中一定数量集散节点的蓄意攻击，就能破坏整个网络的正常运行，而且如果这些集散节点之间的松散联系一旦相互影响、交叉感染，整个网络的安全性就将大大降低。9共一百四十一页复杂网络(wnglu)抗毁性举例之二反映在互联网中，我们几乎都使用着微软的Windows开放式操作平台，针对单一安全漏洞的病毒就足以感染大部分网络连接，几位美国网络安全专家在最近的一份联合(linh)报告中极力呼吁，过分依赖微软软件可能导致“大规模、雪崩式故障”。 10共一百四十一页复杂(fz)网络抗毁性举例之三网络抗毁性分析的一个重要实例是食物链网络。对于(duy)食物链网络，由于规模限制，食物链网络的度分布没有得到最终

6、研究结果，度分布存在幂律分布、均匀分布、以及指数分布等多种形式。在这样的网络上，如果发生个别物种的衰落或死亡会对整体生态系统产生什么影响呢？11共一百四十一页复杂网络(wnglu)抗毁性举例之四野战地域通信网是由25-30个干线节点组成的拓扑结构为栅格状的大型(dxng)无线通信系统，为陆军作战部队之间的信息传递提供迅速、安全和可靠的通信。综合保障网络是为了保障战争、抗洪抢险等重大行动所需，以物资贮存点等保障实体为依托，把各种保障资源按一定的要求和原则合理部署，在空间上形成网络化布局的保障体系。在这个体系中，仓库、医院、工厂、供应站等构成保障实体，铁路、公路、水路、管线、航线等构成连接网络的纽

7、带，在网络中运行的有信息、物资、人员、技术实体等。相对于日常通信、运输等问题，这些军用网络更强调网络在恶劣环境下的抗毁能力。12共一百四十一页复杂网络(wnglu)可靠性定义复杂网络的可靠性、抗毁性研究一直是一个十分棘手的问题，这主要归根于一直以来我们对复杂网络的拓扑结构知之甚少，甚至(shnzh)有很大偏差。以往的复杂网络抗毁性模型都是建立在随机网络模型上的，在抗毁性分析中我们也仅考虑随机打击。最新的研究表明不同拓扑结构的网络对这两种损伤的抗毁性存在很大差异。这使得我们不得不重新回过头来研究复杂网络的可靠性、抗毁性。什么样的拓扑结构可靠性更好？抗毁性更强？13共一百四十一页复杂网络(wngl

8、u)可靠性定义 （复杂）网络可靠性： 是指网络系统在规定条件下和规定时间内完成规定功能的能力，可靠(kko)性的概率度量称为可靠(kko)度。这个定义包含了五个方面的内容 :对象、条件、时间、功能和能力。14共一百四十一页报告(bogo)内容复杂网络可靠性概述指标体系与模型(mxng)复杂网络可靠性的有关研究内容网络可靠性研究的方法论15共一百四十一页2 指标体系与模型(mxng)网络可靠性指标体系网络抗毁性评估(pn )模型网络抗毁性优化设计模型16共一百四十一页网络可靠性研究(ynji)的层面及任务研究层面研究任务测度指标网络拓扑层研究拓扑结构的可靠性及网络组织的要求和改进措施抗毁性、生存

9、性网络设备层研究通信设备终端到终端的可靠性及整个网络系统设备的可靠性设备可靠性网络路由层分析网络路由算法的效率、流量控制、路由管理网络运行层研究网络环境和网络异常故障的规律对网络可靠性的影响可用性网络业务层分析网络业务能力及服务质量，对网络的性能可靠性进行综合评价完成性、有效性网络管理层研究网络维护和管理体系及提高维护管理水平的措施17共一百四十一页网络(wnglu)的效能分析网络系统效能定义：系统在规定的条件下，满足给定的定量特征和服务要求的能力。它是系统可用性、可信性及固有能力的综合反映。效能分析的主要思想：无论何时，一旦需要使用某个系统，它就应该处于能正常工作的准备状态（A），并要求它在

10、执行(zhxng)任务过程中具有可信性（D），同时，还必须具有完成预定任务的能力（C）。也即要求系统“招之即来、来之能战、战之能胜”。18共一百四十一页效能(xionng)分析模型E=ADC A：可用性向量 D：可信性矩阵(j zhn) C：品质因素向量19共一百四十一页网络的效能(xionng)分析效能分析可用性可信性品质因素可靠性维修性保障性抗毁性生存性有效性安全性可靠性连通性信息时延信息的丢失率话务的呼损率网络的容量拥塞测度与控制20共一百四十一页可用性可用性也称完好性，它是效能研究的目的，是衡量网络处于可工作状态的程度。这种程度往往决定于网络的可靠性、维修性和保障性。网络的可用性问题是

11、研究在一定的网络拓扑结构(jigu)下，根据网络中各种部件（节点和边）处于不同工作状态的概率，给出网络在开始执行任务时的系统状态和特性。21共一百四十一页可信性可信性是研究(ynji)网络效能问题的关键。可信性是指在人为或自然的破坏作用下，网络在规定的条件下和规定的时间内生存的能力。由网络的可信性定义中分离出研究有关网络可信性问题的基本概念有：抗毁性、生存性、有效性、安全性、可靠性（狭义）。22共一百四十一页网络(wnglu)的抗毁性（Invulnerability） 网络(wnglu)在人为破坏作用下的可靠性，它假定“破坏者具有关于网络(wnglu)结构的全部资料，并采用一种确定的破坏策略”

12、。对于一个网络，网络的抗毁性是指至少需要破坏几个节点或几条链路才能中断部分节点之间的通信，即指出破坏一个网络的困难程度。抗毁性通过两个可靠性的确定测度粘聚度和连通度来表示。 23共一百四十一页抗毁性（李德毅院士(yunsh)）“系统在受到敌方物理破坏或火力攻击环境(hunjng)下，在规定时间内，完成规定功能的能力”。换个角度看，这个定义实际是在说：因系统中的部件（如部分信道或部分设备）受损失效，系统结构发生变化或者重组后完成规定功能的能力。24共一百四十一页抗干扰性（李德毅院士(yunsh)）系统在受到敌方电磁干扰和攻击环境下，在规定时间内，完成规定功能的能力。换个角度看，这个定义实际是在说

13、：系统中的部件在电磁攻击环境下，其能力在不同程度上失效，性能指标在量的方面下降。但由于系统具有结构上的容错性，能在一定程度上承受(chngshu)环境的恶化。 25共一百四十一页粘聚度（Cohesion） 对于一个连通网络(wnglu)，定义CHij为断开一对节点（i，j）之间所有通路所需去掉的最少链路数，则网络的粘聚度为：粘聚度对应着网络的最小链路割集。 26共一百四十一页连通(lintng)度（Connectivity） 对于一个连通网络，定义CNij为断开一对节点（i，j）之间所有通路(tngl)所需去掉的最少节点数，则网络的连通度为：连通度对应着网络的最小节点割集。27共一百四十一页粘

14、聚度、连通(lintng)度的缺陷要使一个网络解体，至少需要去掉CH条链路或者CN个节点。这种解体，可能把一个网络分解为两个或多个子网络，也可能把一个节点从网络中分离出来。对于网络业务(yw)来说，前者比后者带来更严重的后果。 28共一百四十一页粘聚度和连通(lintng)度（Boesch等 ）在通信网中，为了把一个具有(jyu)m个节点的子网络从通信网中分离出来所需去掉的最少链路数NL(m)或最少节点数NN(m)，显然： 29共一百四十一页粘聚度和连通(lintng)度（Wilkov ）如果考虑网络传输(chun sh)的时延，对于一个网络直径为k的通信网，为使网络直径k超过阀值km时必须去

15、掉的最少链路数DL(k，km)或最少节点数DN(k，km)。 30共一百四十一页抗毁性小结(xioji)网络的抗毁性是从图论的概念中提出来的，在通信网的可靠性分析中得到广泛应用。抗毁性从网络连通性的角度描述网络拓扑结构对通信网可靠性的影响(yngxing)，它是可靠性的一种确定性测度。对于军用通信网来说，网络的抗毁性无疑是一项重要的指标。网络抗毁性的实质是研究网络的拓扑结构的可靠性，是网络可靠性的一种静态指标。抗毁性包括节点连通度、节点粘聚度、网络设备地域分散密集度、敌方对网络的结构掌握程度情况和敌方的攻击力量等，可以利用可信性指标体系，通过层次分析法等综合计算方法进行计算。31共一百四十一页

16、网络(wnglu)的生存性（Survivability） 基于网络连通性的概率测度。网络在随机破坏作用下的网络可靠性。在军用环境中，随机性破坏表现为“破坏者只有(zhyu)关于网络结构的部分资料，在采用一种随机的破坏策略” ；在商用环境中，随机性破坏则表现为网络部件（节点和链路）的自然失效。网络的生存性由可靠性的概率测度连通概率来表示。32共一百四十一页几种(j zhn)连通概率端到端的连通概率。Baran：在遭受破坏后幸存下来的网络中，选出一个最大的连通子网络，其节点数的平均值（对所有样本作平均）占原网络节点数的百分率，即为通信网的连通概率。Frank：在遭受破坏后幸存下来的网络中，任意选取

17、一个节点，所有能与它相连通的节点数占原网络节点数的百分率。整个(zhngg)网络构成一个连通网络的概率。 33共一百四十一页生存性小结(xioji)网络生存性是基于概率论和图论的知识提出来的，它描述(mio sh)了随机性破坏（主要是网络部件的自然失效）以及网络拓扑结构对网络可靠性的影响。生存性是网络可靠性研究的重要内容之一，它是网络运行过程中的网络连通度的量度，它包括节点连通度、节点粘聚度、业务性能等，这些测度指标只能通过对具体网络运行破坏发生时统计得到或通过计算机仿真实验得到。34共一百四十一页网络(wnglu)的有效性（Availability） 有效性也称为完成性基于(jy)网络业务性

18、能的可靠性测度网络在部件失效下满足业务性能要求的程度包括网络的吞吐量、传输时延等35共一百四十一页几种(j zhn)有效性指标Baiberis等：加权的端到端连通概率。Barberis等：网络的吞吐量超过一个(y )给定阀值的概率。Park等：网络的一个中心节点到其他节点的传输时延不超过给定阀值的概率。 Bonaventura等：对于线路交换网和报文交换网的网络有效性指标。 36共一百四十一页安全性为减少敌方对网络的确定性破坏，研究网络中的信息抗搜索、抗截取、抗定向(dn xin)分析、抗欺骗的能力以及网络保密能力。安全性是基于事故的角度（也即遭受破坏，产生意外事件）研究网络的风险和危害防御问

19、题。37共一百四十一页可靠性（狭义(xiy)）研究自身软、硬件故障及非有意干扰情况下，网络(wnglu)在规定的条件下和规定的时间内维持正常工作的能力。狭义可靠性指标可以根据传统的可靠性串并联系统算法来计算。整个网络系统设备的可靠性则由终端到终端的可靠性综合求出。38共一百四十一页网络的品质(pnzh)因素网络的品质因素是表征网络在已知使用环境和网络状态下主要性能特征的度量。（能力）用户方面：信息时延、信息的丢失率、话务的呼损率，等网络管理者方面：网络的容量、拥塞测度与控制、在最大通信距离上通信网络各种状态下的连通概率等。（网络的结构）网络品质因素在执行(zhxng)任务的过程中，随着网络的使

20、用环境和所处的不同“任务剖面”的变化而变化。39共一百四十一页网络(wnglu)可靠性的测度指标体系网络可靠性整体(zhngt)指标网络抗毁性网络生存性网络有效性网络设备可靠性路由选择效率网络管理效率连通度粘聚度分散度攻击度连通度粘聚度业务性吞吐量延时传输效率路由选择流量控制故障恢复业务管理系统管理40共一百四十一页网络的效能(xionng)分析效能(xionng)分析可用性可信性品质因素可靠性维修性保障性抗毁性生存性有效性安全性可靠性连通性信息时延信息的丢失率话务的呼损率网络的容量拥塞测度与控制41共一百四十一页网络(wnglu)可靠性的测度指标体系网络可靠性整体(zhngt)指标网络抗毁性

21、网络生存性网络有效性网络设备可靠性路由选择效率网络管理效率连通度粘聚度分散度攻击度连通度粘聚度业务性吞吐量延时传输效率路由选择流量控制故障恢复业务管理系统管理DC42共一百四十一页2 指标体系与模型(mxng)网络可靠性指标体系网络抗毁性评估模型(mxng)网络抗毁性优化设计模型43共一百四十一页 网络抗毁性评估最终(zu zhn)体现为抗毁性指标的评估。指标的评估需要通过建立抗毁性模型来完成，研究方法主要分为：解析法仿真法抗毁性评估(pn )模型解析法是根据描述系统抗毁性指标与给定条件之间的函数关系的解析表达式来计算指标值的。使用解析法时，通过分析模型的解或研究模型的解的形态，可以比较准确地

22、获得系统状态变化信息。缺点是考虑因素少，要进行假设和简化，除了一些理想的和极简单的情况，只在严格限定的假设条件下才有效。对于大型复杂系统可靠性研究，有时难以建立解析模型。仿真法就是用抽象的、数学的或其他形式的仿真模型代替实际系统在计算机上进行试验。通过仿真可以模拟系统运行，分析特性状态变化情况，评价系统抗毁性指标。计算机仿真在网络系统抗毁性研究领域有十分重要的应用前景。44共一百四十一页解析(ji x)模型 对于一部分网络抗毁性指标，可以(ky)采用解析法来进行分析与评估。将解析法用于抗毁性指标研究，需要进行抗毁性解析建模，主要包括：逻辑框图模型网络模型Markov过程模型 其它模型45共一百

23、四十一页解析模型(mxng)举例C3I系统可靠性、抗毁性和抗干扰性的统一评测模型(mxng)野战地域通信网的可靠性评估模型C4I系统抗毁生存能力的分析模型46共一百四十一页综合(zngh)电子信息系统基本概念C2：Command +Control 指挥控制（50年代）C3：C2+Communication 指挥、控制和通信(tng xn)（60年代）C3I：C3+ Intelligence 指挥、控制、通信和情报（70年代）C4I：C3I+Computer 指挥、控制、通信、计算机和情报（80年代）C4ISR：C4I+Surveillance Reconnaissance 指挥控制、通信、计算

24、机、情报、监视 和侦察（90年代）47共一百四十一页C3I系统(xtng)的统一评测模型一般地说 ，C3I系统由于规模大、组成设备多、结构复杂 ，全系统中的单元故障时有发生。我们很难简单地说这样一个大系统是正常还是失效。全系统绝对正常的平均无故障时间几乎失去意义。因此 ，人们更关注该系统能在多大程度上保持其规定功能(gngnng)的能力。因此可用模糊语言值来表达“系统能在多大程度上保持其规定功能的能力” 。这种模糊语言值方法常常比精确数值方法甚至更确切、更本质、更高效。48共一百四十一页C3I系统(xtng)的统一评测模型引入模糊可靠性的方法，将系统完成任务能力分成了五个等级作为模糊子集，即无

25、任何故障、有弱故障、有故障但能维持、故障达到(d do)临界、致命故障。其次考虑系统的六个主要功能，建立六维雷达图，将雷达图的实际面积和额定面积之比作为基础变量，用隶属云方法建立了模糊评估模型。49共一百四十一页系统(xtng)完成任务能力的等级分类系统无任何(rnh)故障:保持系统全部功能正常的能力。系统有弱故障：保持系统主要功能正常的能力。系统有故障，但尚能维持：保持系统基本功能正常的能力 。故障已达到临界，再严重则不能容忍：保持系统最低功能正常的能力；系统出现了致命故障：系统失去最低功能 ，即系统失效 。50共一百四十一页C3I系统(xtng)功能雷达图信息获取功能信息传输功能信息处理功

26、能辅助决策功能人机交互功能安全保密功能51共一百四十一页解析(ji x)模型举例C3I系统可靠性、抗毁性和抗干扰性的统一评测模型野战地域通信网的可靠性评估(pn )模型C4I系统抗毁生存能力的分析模型52共一百四十一页野战地域通信网的可靠性评估(pn )模型野战地域通信网是由25-30个干线节点组成的拓扑(tu p)结构为栅格状的大型无线通信系统，为陆军作战部队之间的信息传递提供迅速、安全和可靠的通信。野战地域网在初始铺设开通前必须根据网络可靠性和抗毁性要求进行网络拓扑结构设计，同时网络开通工作后，由于战场环境的特殊性，网络节点、链路的工作状况将发生变化，导致网络拓扑结构发生变化，使得网络可靠

27、性、抗毁性以及服务性能下降，为此必须依据一种快速的网络可靠性评价方法实现网络拓扑结构的重组设计。53共一百四十一页网络(wnglu)跳面节点网络G(N，E)为一大型网络，任意节点对之间都有一定跳数的距离，称与某节点具有相同跳数距离的所有节点为该节点具有该跳数的跳面节点。这样就可以把某节点与其他(qt)所有节点之间的可靠性转化为到其所有跳面节点之间的可靠性。这样就避开了大量迂回路由对可靠性影响的细节，只考虑迂回路由影响的效果。54共一百四十一页野战地域通信网的可靠性评估(pn )模型网络(wnglu)G(N，E)的可靠性RG为网络节点到任意跳面节点可靠性的平均值。 其中ri为第i个节点到其所有节

28、点的可靠性，M为最大跳距。55共一百四十一页解析模型(mxng)举例C3I系统可靠性、抗毁性和抗干扰性的统一(tngy)评测模型野战地域通信网的可靠性评估模型C4I系统抗毁生存能力的分析模型56共一百四十一页C4I系统(xtng)抗毁生存能力的分析模型抗毁生存能力是C4I系统(xtng)的一个重要指标，主要是指系统(xtng)在敌方各种软硬件打击下的抗毁能力、对抗能力、环境适应能力和系统(xtng)生存能力。系统抗毁生存能力定义为：系统中出现确定性和随机性故障时，系统维持或恢复其性能到一个可接受程度的能力。 57共一百四十一页C4I系统(xtng)抗毁生存能力的分析模型假设系统为一个网络G(V

29、，L)，其中V为节点(ji din)集合，L为链路集合，每个节点和链路都有一个正常工作的概率，系统中传递的信息量用节点间传送的分组集合dij表示。选取被系统有效传输的比值为系统的抗毁生存能力： 其中dijk表示通过第k条路径，在i及j节点之间传送的分组。其中P(k)表示第k条路径的生存概率。58共一百四十一页仿真(fn zhn)模型举例Petri网模型(mxng)GOOPN模型建模仿真环境OPMSE59共一百四十一页Petri网模型(mxng)Petri网是进行离散事件动态系统建模与仿真分析的有力工具，描述和分析离散事件动态系统的一种模型工具，它不仅能够描述同步、并发、资源争用等特性，本身也含

30、有自控制机制，因此适合网络系统描述与建模的需要。但通常的Petri网的描述能力仍然有限 ，对复杂系统建模时 ，容易造成状态组合(zh)爆炸现象。60共一百四十一页GOOPN模型(mxng)国防科大武小悦教授提出了一种用于分析通信网可靠性的扩展(kuzhn)的、面向对象的Petri网模型GOOPN(Generalized Object Oriented Petri Net)，并给出了进行可靠性建模分析的工具。该模型可以统一处理通信网络的连通可靠性问题，可以较好地适应系统要素的变化 。61共一百四十一页建模仿真(fn zhn)环境OPMSE国防科技大学信息系统与管理学院开发了基于对象Petri网的

31、建模仿真环境OPMSE。该环境不仅可用于C4ISR系统的动态建模，还可以对建立的模型进行仿真实验，统计运行数据并计算仿真结果(ji gu)。OPMSE的典型应用领域是通信网的分析，已被用于C4ISR系统分析与设计、效能评价等方面。 62共一百四十一页2 指标体系与模型(mxng)网络可靠性指标体系网络抗毁性评估模型(mxng)网络抗毁性优化设计模型63共一百四十一页抗毁性优化设计(shj)模型 抗毁性的优化设计模型以抗毁性评估模型为基础，其主要(zhyo)目标是以最小的费用获得最大的抗毁性，主要(zhyo)包括三个层次：拓扑结构的优化设计，链路容量的优化设计，路由的优化设计。目前的抗毁性优化设

32、计模型集中于拓扑结构的优化，主要(zhyo)讨论了两个方面的问题：在满足网络连通性的要求下，使得总费用最少在给定费用的前提下，使得网络的连通性最大64共一百四十一页迂回路径法基于跳面节点的优化设计(shj)模型容量分配优化设计模型迂回路径法：在考虑没有信道直接相连节点(ji din)对之间的端对端信息的基础上，由大到小增加信道，每增加一条信道进行一次仿真，试验得出系统的抗毁生存能力，直到达到满意的抗毁生存能力为止。基于跳面节点的优化设计模型是在基于跳面节点的的可靠性评估模型和代价模型基础上，对网络拓扑结构进行优化、在固定网络拓扑结构的基础上，对可靠性指标进行优化分配。容量分配优化设计模型分别讨

33、论了在给定总的费用条件下，使得网络可靠性最大的网络链路容量分配优化设计问题；以及在给定了网络可靠性指标的前提下，使得网络费用最小的链路容量分配优化设计问题。优化设计模型举例65共一百四十一页抗毁性优化设计(shj)小结抗毁性优化设计基本上都采用这样一种思路：以抗毁性评估模型为基础(jch)，应用仿真方法采取不同的策略进行“尝试”，直到得到较好的抗毁性。当前研究主要集中于网络抗毁性模型的建立，而对网络拓扑结构自身性质的研究较少，这是抗毁性研究的一个薄弱点。 66共一百四十一页报告(bogo)内容复杂网络可靠性概述指标体系与模型(mxng)复杂网络可靠性的有关研究内容网络可靠性研究的方法论67共一

34、百四十一页3 复杂网络可靠性的有关研究(ynji)内容指标体系研究网络拓扑结构对抗毁性的影响分析网络抗毁性评估方法研究复杂网络的健康(jinkng)监控技术研究68共一百四十一页指标体系研究(ynji)思路网络功能网络构成影响因素复杂网络复杂网络可靠性定义指标体系建立原则现有及新指标研究连通性单元、载体任务完成类指标间相互关系研究复杂网络可靠性指标体系69共一百四十一页3 复杂网络(wnglu)可靠性的有关研究内容指标体系研究(ynji)网络拓扑结构对抗毁性的影响分析网络抗毁性评估方法研究复杂网络的健康监控技术研究70共一百四十一页拓扑结构对抗(dukng)毁性的影响分析复杂网络(wnglu)

35、研究内容有：研究各种网络的结构找出结构和功能的联系设计出更优越的网络71共一百四十一页拓扑(tu p)结构对抗毁性的影响分析随机网络(wnglu)与无标度网络(wnglu)的抗毁性网络结构熵与抗毁性抗毁性研究中节点重要性评估方法72共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性 许多复杂系统的容错性达到了令人惊讶程度。例如，简单生物体在激烈的药物(yow)或者环境影响下生长、发展、再生，其容错性归因于新陈代谢网络下潜在的鲁棒性。复杂通信网络也显示了很好的鲁棒性：虽然其主要部分会有故障，但是局部失效很难导致失去全局网络传输信息的能力。无标度网络显示出很强的容错性（在非常高

36、的自身失效条件下，节点连接也不受影响）。然而在这些网络中容错的代价太高，只要选择切除少数扮演重要角色的节点，整个网络就几乎崩溃。2000年Reka Albert等对这种特性进行了研究。73共一百四十一页随机(su j)网络与无标度网络的抗毁性考察两类网络：随机网络：连接度分布是一条钟型曲线，P(k)在处取得最大值，每个节点有近似相同(xin tn)的连接数 ；无标度网络：连接度分布是一条递减的曲线，满足幂次定律，网络中有少量核心节点。74共一百四十一页随机(su j)网络与无标度网络的抗毁性75共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性网络的连接可以通过平均最短距离

37、d来描述。 d刻画(khu)了两个节点相互通信的能力。拥有大量节点的网络也能有很小的平均最短距离；例如万维网，拥有 个节点，平均最短距离大约是19；社会网拥有600万个节点，平均最短距离大约是6。76共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性将随机网络和无标度网络同时(tngsh)置于两种打击之下：随机打击（failure):以一定比例 f 随机移除节点智能打击（attack):按照连接度从高到低次序移除节点77共一百四十一页随机(su j)网络与无标度网络的抗毁性左图显示了两种网络在不同打击(dj)下，d随f变化图。两种网络都包含10000个节点和20000个连接

38、。78共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性图b.在因特网上随机损毁(方块)或者受到攻击(圆)d的变化，样本来自于网络应用研究国家实验室收集的包含(bohn)6209个节点和12200个连接的拓扑图形。79共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性在上随机打击(方块(fn kui)或者受到智能攻击(六边形)后d的变化图。80共一百四十一页随机网络(wnglu)与无标度网络(wnglu)的抗毁性结论：生机勃勃：无标度网络在随机打击下，生机 勃勃，抗御能力很强。脆 弱：在智能性的打击下，无标度网络 显得(xin de)异常脆弱。81共一百

39、四十一页拓扑(tu p)结构对抗毁性的影响分析随机网络与无标度网络的抗毁性网络结构熵与抗毁性抗毁性研究(ynji)中节点重要性评估方法82共一百四十一页网络结构熵与抗毁性在现实生活中，我们遇到的网络往往是介于随机网络与无标度网络之间的。它们既不是完全随机的，连接度分布也不一定严格满足幂分布。从网络拓扑结构的一般属性出发，研究各种属性对抗毁性的影响(yngxing)，这将是复杂网络抗毁性研究的一条有效的新途径。 83共一百四十一页网络结构熵与抗毁性从本质上讲，复杂网络的无标度性就是一种非同质性，是网络涌现出的一种“序”。在无标度网络中存在极少数具有大量连接的“核心节点”（Hub-node）和大量

40、具有少量连接的“末梢(msho)节点”。这样的网络是不均匀的，或者是“非同质的”，表现在连接度分布上就是连接度分布曲线是不断递减的。84共一百四十一页网络结构熵与抗毁性怎么定量地刻画复杂网络这种非同质性呢？在现实世界的复杂网络中，连接度分布曲线是一条相当不规则的曲线，可能并不是一条严格递减的曲线，即使是一条递减的曲线，通过拟合得出的曲线参数也是非常不精确的，而且(r qi)计算复杂。85共一百四十一页网络结构熵与抗毁性熵最初是作为一个热力学概念而引入的，作为系统无序的度量，熵由于其独特的内涵和渗透力被广泛应用。近来，熵作为描述(mio sh)复杂系统结构的物理量，在复杂系统理论中受到越来越多的

41、关注，成为研究复杂系统的一个重要工具。熵的宏观意义是系统能量分布均匀性的一种量度，可以表示物体所处状态是否稳定及系统变化的方向，能量分布越均匀，熵越大；反之，则熵越小。 86共一百四十一页网络结构熵与抗毁性我们定义： 为第i个节点的重要度，其中N为网络中节点数目，ki为第个节点的连接度。熵是“无序”的度量。如果网络是随机连接的，各个节点的重要度大致相当，那么我们认为网络是“无序的”。反之，如果网络是无标度的，网络中有少量“核心节点”和大量“末梢(msho)节点”，节点的重要度存在差异，我们认为这种网络是“有序的”。87共一百四十一页网络结构熵与抗毁性我们定义： 为网络结构熵，其中N为网络中节点

42、(ji din)数目。当网络完全均匀，即Ii=1/N 时，E取最大值。当网络中所有节点都与某一个中心节点相连，网络最不均匀，网络结构熵最小。 88共一百四十一页网络结构熵与抗毁性为排出(pi ch)节点数目对的影响，需要将网络结构熵进行归一化。定义称 为网络的标准结构熵，其中N为网络中节点数目。89共一百四十一页网络结构熵与抗毁性用网络结构熵研究复杂网络的非同质性，并不是说用网络结构熵取代连接度分布。网络结构熵与连接度分布的关系，就如同随机变量(su j bin lin)的数字特征与其概率分布函数的关系，两者是互为补充的。网络结构熵是由连接度分布确定的，网络结构熵可以更加精确简洁的度量复杂网络

43、的非同质性。网络结构熵与抗毁性有关系。90共一百四十一页拓扑结构对抗(dukng)毁性的影响分析随机网络与无标度网络的抗毁性网络结构熵与抗毁性抗毁性研究中节点(ji din)重要性评估方法91共一百四十一页抗毁性研究(ynji)中节点重要性评估方法无标度网络中一个很重要的概念就是“核心节点”，那么哪些节点是“核心节点”呢？通过节点重要性的评估找出那些重要的核心节点，一方面我们可以重点保护这些“核心节点”来提高整个网络的可靠性，另外一方面我们也可以攻击这些“薄弱环节”达到摧毁整个网络的目的，比如阻截(zji)电脑病毒的传播。92共一百四十一页抗毁性研究中节点重要性评估(pn )方法很多时候我们都

44、把节点的度数作为节点重要性的衡量标准，认为与节点相连的边越多则该节点越重要，显然(xinrn)这种评估方法具有片面性，有些关键节点并不一定具有较大的度数。为了解决这个问题，我们提出了基于凝聚度的节点收缩方法来评估网络中的节点重要度。93共一百四十一页节点(ji din)收缩方法节点vi收缩是指将与节点vi相连接的ki个节点都与节点vi短接，即用一个新节点vi 代替这ki+1个节点，原先与它们(t men)关联的边现在都与新节点关联。相当于节点vi将它周围的ki个节点“凝聚成了一个节点”。如果节点vi是一个很重要的“核心节点”，那么将它收缩后整个网络将更好的凝聚在一起。94共一百四十一页 节点收

45、缩(shu su)方法vi95共一百四十一页节点收缩(shu su)方法vi96共一百四十一页节点(ji din)收缩方法vi新节点(ji din)vi97共一百四十一页网络(wnglu)凝聚度网络凝聚程度(chngd)的衡量标准节点之间的平均最短路径(l)网络中的节点数目(n)网络凝聚度定义节点数与平均最短路径乘积的倒数 98共一百四十一页网络(wnglu)凝聚度定义定义为网络凝聚度，其中 代表节点(ji din)i和j之间的最短距离。 显然 ，当网络中只有一个节点时，取最大值1。99共一百四十一页抗毁性研究中节点重要性评估(pn )方法 节点收缩后得到的网络凝聚度取决于两个因素：节点的度数

46、。相同条件下，如果节点的度数越大，则将该节点收缩以后网络中节点和边的数目就越少，网络的凝聚度就越大，该节点越重要。节点在网络中的位置。如果节点处于(chy)“要塞”位置，很多节点对之间的最短路径都要经过该节点，那么当把收缩以后将大大减少网络的平均最短距离，从而获得较大的网络凝聚度。 100共一百四十一页评估(pn )实例 某网络拓扑结构图 101共一百四十一页评估(pn )实例节点收缩(shu su)后的图。其中(a)为节点v3收缩(shu su)后的图，(b)为节点v2或v4收缩(shu su)后的图，(c)为节点v1或v5收缩(shu su)后的图。102共一百四十一页评估(pn )结果节

47、点节点重要度v10.510.50.33330.3333v2v5v3v4103共一百四十一页3 复杂网络可靠性的有关(yugun)研究内容指标体系研究网络拓扑结构(jigu)对抗毁性的影响分析网络抗毁性评估方法研究复杂网络的健康监控技术研究104共一百四十一页网络抗毁性评估(pn )方法研究用离散动态系统的建模思想研究复杂网络(wnglu)的抗毁性对抗环境下抗毁性评估方法研究抗毁性评估的仿真分析方法研究105共一百四十一页复杂网络(wnglu)的离散动态系统特性系统行为动态性的特点网络系统处于不断的变化、发展之中系统行为的时间离散性系统行为的事件离散性在网络系统运行中，部件（包括节点和链路）的失

48、效(sh xio)，以及由此引起的系统状态的变化，在对抗环境下，系统所遭受的冲击等都是一系列的离散事件。106共一百四十一页网络系统抗毁性评估的主要(zhyo)方法Markov模型排队(pi du)论模型Petri网模型其它模型107共一百四十一页网络(wnglu)抗毁性评估方法研究用离散动态系统(xtng)的建模思想研究复杂网络的抗毁性对抗环境下抗毁性评估方法研究抗毁性评估的仿真分析方法研究108共一百四十一页对抗(dukng)环境下抗毁性评估方法研究对抗环境的描述(mio sh)建立对抗模型模型的验证、分析模型的求解109共一百四十一页综合电子(dinz)信息系统战场抗毁性110共一百四十

49、一页模型(mxng)假设敌方(d fn)的攻击是分波进行的，其攻击波的到达服从泊松分布每波次轰炸机所发射的导弹数为服从离散均匀分布的随机变量当军指挥所A被破坏后，由师指挥所B（一师）担任指挥任务当军指挥所A完好时，通信网生存的条件是在B、C1、C2、C3中至少三个保持完好；当A被破坏时，通信网生存的条件是在B、C1、C2、C3中至少保持包括B在内的三个师指挥所保持完好经过每发次导弹打击后军指挥所的生存概率为PA经过每发次打击后师指挥所B的生存概率为PB经过每发次打击后师指挥所C1、C2、C3的生存概率为PC111共一百四十一页模型(mxng)求解单元的战场(zhnchng)抗毁性分析112共一

50、百四十一页模型(mxng)求解系统的战场抗毁性分析(fnx)当军指挥所完好时 当军指挥所被破坏时 113共一百四十一页网络抗毁性评估(pn )方法研究用离散动态系统的建模思想研究复杂网络的抗毁性对抗环境下抗毁性评估(pn )方法研究抗毁性评估的仿真分析方法研究114共一百四十一页抗毁性评估(pn )的仿真分析方法研究现有仿真平台分析对抗环境(hunjng)下，仿真平台的建立仿真模型的V.V&A分析仿真结果分析115共一百四十一页抗毁性仿真(fn zhn)示例做一些试探性研究复杂(fz)网络在SWARM上仿真的可行性检验简单的假设评估系统在特定条件下的抗毁能力116共一百四十一页仿真环境(hun

51、jng)描述二维平面(pngmin)仿真节点用Agent表示随机性连接或择优连接117共一百四十一页仿真(fn zhn)参数及设定节点数量节点连接(linji)边数无向边打击半径打击频率118共一百四十一页打击(dj)模式设定模式1：打击整个区域(qy)内的所有节点模式2：打击固定区域内的所有节点模式3：打击变动区域内的所有节点119共一百四十一页仿真(fn zhn)结果模式1下，节点被打击成孤立(gl)节点，节点的颜色由蓝色变成红色120共一百四十一页仿真(fn zhn)结果模式(msh)2打击示意图121共一百四十一页仿真(fn zhn)结果模式(msh)3打击示意图122共一百四十一页仿

52、真(fn zhn)结果随机(su j)连接和择优连接下的节点度分布图（累计分布）123共一百四十一页不同打击(dj)模式下的打击(dj)效果分析在模式1下，要打击（223）次才能(cinng)使孤立节点数占总节点数的一半 124共一百四十一页不同打击模式(msh)下的打击效果分析在打击模式2下，不可能使孤立(gl)节点数占到总节点数的一半 125共一百四十一页不同打击模式下的打击效果(xiogu)分析在模式3下，要打击43次才能(cinng)使孤立节点数占总节点数一半 126共一百四十一页随机(su j)打击与智能打击的打击效果对比分析随机打击(dj)要(22-3)次，智能打击(dj)要(93)次127共一百四十一页战术(zhnsh)机动的抗毁效果分析在打击模式3下，不采用战术(zhnsh)机动时的打击次数为43。128共一百四十一页战术(zh