一种轨道交通网络中有限资源情况下的保护资源分配方法

技术领域

本发明属于轨道交通技术领域，特别是一种轨道交通网络中有限资源情况下的保护资源分配方法。

背景技术

网络中一旦有节点发生故障，会对整个网络的运行产生巨大的影响。为了应对特定节点故障对整体网络的损毁，可以给相应节点增加额外的节点容量。网络中每个节点的重要度是不同的，有的节点因为处在网络中比较重要的位置，在相继故障中更容易被损毁。然而基础建设中经费预算是有限的，即总体的资源总量是一定的，那么怎么分配这些资源就成了一个重要的问题。

截至目前，已经有不少研究人员利用复杂网络理论，对广义的城市公共交通网络进行了实证研究,应用方面有文献1(Amaral L AN,Scala A,Barthelemy M,et al.Classesof behavior of small world networks[J].Proceedings of the National Academy ofSciences,USA,1997(21):11149-11152)航空航天网络、文献2(Sen P,Dasgupta S,Chatterjee A,et a1.Small-world properties of the Indian railway network[J].Phys.Rev.E,2003,67:036106)部分线路铁路网络、文献3(Latora V,Marchiori M.Is theBoston subway a small world network[J].Physica A,2002,314:109-ll3)城市地下交通网络和文献4(Sienkiewicz J,Holyst J A.Statistical analysis of 22publictransport networks in Poland[J].Phys.Rev.E,2005,72:046127)城市地面公交网络等。经过一系列的研究发现，我们得到结论，这些网络的度分布基本上服从指数分布或幂率分布。但是目前的这些研究主要是从网络拓扑结构角度出发来进行静态特征的分析，对轨道交通加权网络的研究开展很少.虽然文献5(Chen Y Z,Li N,He D R.A study on someurban bus transport networks[J].Physica A,2007,376:747-754)把站点间直达的公交线路数定义为权重，但是归根到底还是没有超出静态网络结构的研究范畴。

发明内容

本发明的目的在于提供一种提高轨道交通网络鲁棒性的有限资源分配情况下的节点保护策略。将网络中的节点按不同的节点重要度排序，给节点重要度高的节点分配更多的资源，来减少相继故障过程中的节点损毁率，从而提高轨道交通网络的鲁棒性。

实现本发明目的的技术解决方案为：一种轨道交通网络中有限资源情况下的保护资源分配方法，所述方法包括以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；

步骤3，为网络中的节点分配保护资源；

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

进一步地，步骤1所述根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载，具体包括：

步骤1-1，将交通网络中的站点抽象为网络中的节点，将交通网络中两个节点之间的连边抽象为网络节点之间的边；

给定一个无向有权网络G＝(V，E)，其中V表示节点，E表示节点之间的边，网络中的节点总数N

步骤1-2，计算每个节点的初始流量即初始负载：

式中，L

步骤1-3，计算每个节点的初始最大负载：

C

式中，C

步骤1-4，计算两个节点之间连边的权重：

式中，e

步骤1-5，设置节点连边的权重阈值T。

进一步地，步骤2所述对轨道交通网络模型中的节点进行重要度降序排列，具体包括：

步骤2-1，建立空的存放失效节点的集合Ω；

步骤2-2，移除网络中负载最大的节点，并将该节点流量分给周围的邻居节点，引发相继故障；

步骤2-3，将边权重大于T的节点视为失效节点，存入集合Ω中，并将失效节点从网络中移除，将流量分给周围节点；

步骤2-4，重复执行步骤2-3进行多次迭代，将失效节点依次存入集合Ω中，直至网络中边权重、节点负载均不再发生变化。

进一步地，步骤3所述为网络中的节点分配保护资源，具体包括：

步骤3-1，设定可供分配的保护资源总数为Z；

步骤3-2，从失效节点中随机选取F轮失效节点进行保护，按照步骤2得到的重要度顺序，对失效节点进行资源分配，具体分配方式为：

式中，

进一步地，步骤4所述移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化，具体包括：

步骤4-1，构建一个空的失效节点集合Ω'；将网络中未分配资源之前的最大负载对应的节点作为初始移除节点，将其视为失效节点；并加入失效节点集合Ω'中；

步骤4-2，移除集合Ω'中的失效节点，并更新周围节点的边权重；

步骤4-3，比较网络中每个节点当前的负载L

步骤4-4，更新网络中的边权重；

步骤4-5，针对网络中的每个边权重，判断是否满足e

一种轨道交通网络中有限资源情况下的保护资源分配系统，所述系统包括：

第一模块，用于根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

第二模块，用于对轨道交通网络模型中的节点进行重要度降序排列；

第三模块，用于为网络中的节点分配保护资源；

第四模块，用于移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行计算机程序时实现以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；

步骤3，为网络中的节点分配保护资源；

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；

步骤3，为网络中的节点分配保护资源；

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

本发明与现有技术相比，其显著优点为：

(1)相较于普通的轨道交通模型，本发明提出的权重计算方式更真实的反应了轨道交通网络在实际运营中的场景，减少了相继故障发生后网络中节点的失效率。

(2)相较于平均分配和按特征向量中心性分配方式，本发明提出的分配方式更有针对性的将资源分配给需要资源的节点，提高了网络的鲁棒性。

下面结合附图对本发明作进一步详细描述。

附图说明

图1为本发明有限资源情况下的节点保护策略流程示意图。

图2为本发明实施例中网络有效节点比随迭代次数变化示意图。

图3为本发明实施例中网络最大连通片占比随迭代次数变化示意图。

具体实施方式

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

需要说明，若本发明实施例中有涉及“第一”、“第二”等的描述，则该“第一”、“第二”等的描述仅用于描述目的，而不能理解为指示或暗示其相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。另外，各个实施例之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本发明要求的保护范围之内。

一种轨道交通网络中有限资源情况下的保护资源分配方法，所述方法包括以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；具体包括：

步骤1-1，将交通网络中的站点抽象为网络中的节点，将交通网络中两个节点之间的连边抽象为网络节点之间的边；

给定一个无向有权网络G＝(V，E)，其中V表示节点，E表示节点之间的边，网络中的节点总数N

步骤1-2，计算每个节点的初始流量即初始负载：

式中，L

步骤1-3，计算每个节点的初始最大负载：

C

式中，C

式中，e

步骤1-5，设置节点连边的权重阈值T。

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；具体包括：

步骤2-1，建立空的存放失效节点的集合Ω；

步骤2-2，移除网络中负载最大的节点，并将该节点流量分给周围的邻居节点，引发相继故障；

步骤2-3，将边权重大于T的节点视为失效节点，存入集合Ω中，并将失效节点从网络中移除，将流量分给周围节点；

步骤2-4，重复执行步骤2-3进行多次迭代，将失效节点依次存入集合Ω中，直至网络中边权重、节点负载均不再发生变化。

步骤3，为网络中的节点分配保护资源；具体包括：

步骤3-1，设定可供分配的保护资源总数为Z；

步骤3-2，从失效节点中随机选取F轮失效节点进行保护，按照步骤2得到的重要度顺序，对失效节点进行资源分配(按节点损毁顺序分配资源时，同一轮损毁的节点分配的资源数相等)，具体分配方式为：

式中，

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。具体包括：

步骤4-1，构建一个空的失效节点集合Ω'；将网络中未分配资源之前的最大负载对应的节点作为初始移除节点，将其视为失效节点；并加入失效节点集合Ω'中；

步骤4-2，移除集合Ω'中的失效节点，并更新周围节点的边权重；

步骤4-3，比较网络中每个节点当前的负载L

步骤4-4，更新网络中的边权重；

步骤4-5，针对网络中的每个边权重，判断是否满足e

本发明提供了一种轨道交通网络中有限资源情况下的保护资源分配系统，所述系统包括：

第一模块，用于根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

第二模块，用于对轨道交通网络模型中的节点进行重要度降序排列；

第三模块，用于为网络中的节点分配保护资源；

第四模块，用于移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

关于轨道交通网络中有限资源情况下的保护资源分配系统的具体限定可以参见上文中对于轨道交通网络中有限资源情况下的保护资源分配方法的限定，在此不再赘述。上述轨道交通网络中有限资源情况下的保护资源分配系统中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。

本发明提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行计算机程序时实现以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；

步骤3，为网络中的节点分配保护资源；

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

关于每一步的具体限定可以参见上文中对于轨道交通网络中有限资源情况下的保护资源分配方法的限定，在此不再赘述。

本发明提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现以下步骤：

步骤1，根据真实交通网络数据构建加权无向网络作为轨道交通网络模型，并计算网络初始负载；

步骤2，对轨道交通网络模型中的节点进行重要度降序排列；

步骤3，为网络中的节点分配保护资源；

步骤4，移除网络中的节点，对网络进行攻击，直至网络中边权重、节点负载均不再发生变化。

关于每一步的具体限定可以参见上文中对于轨道交通网络中有限资源情况下的保护资源分配方法的限定，在此不再赘述。

下面结合具体示例对本发明进行进一步验证分析。

本示例中的数据来源于网站，公布了北京市轨道站点信息，其中包含北京地铁的线路名称、车站名称、行车方向。将车站名称用数字表示，可以得到一共有342个不同的站点，因此初始时N＝342，e

分别通过平均分配资源方式、特征向量中心性大小分配资源方式以及本发明的资源分配方式进行实验，根据图2所示实验结果可以看出，本发明模型的相继故障在经历了12次迭代后基本完成，因此将权重阈值T设置为12，资源Z取100。为了保证结果的准确性，防止无关变量对实验造成影响，本次实验中三种不同的保护情况下添加保护资源的节点数目均为10。为了进一步控制实验变量，统一移除的是网络中特征向量中心性最高的节点。

根据图3实验结果显示，随着迭代次数的增加，处于可连通区域的节点数在逐渐下降。按损毁顺序分配资源的网络在第11次迭代中到达稳定，且最后的可连通区域占比最大，保护效果最理想；按节点中心性分配资源的节点在第12次迭代时达到稳定，最后的可连通区域稍小于按节点损毁顺序分配资源的网络；而平均分配保护资源的网络在第13次迭代时才达到稳定，网络的可连通区域占比最小，保护效果较差。

经过一系列的实验，可以发现平均分配保护资源对网络鲁棒性的提高最小，另外两种分配方式均能有效提高网络鲁棒性，而本发明按节点损毁顺序分配保护资源的方式更能有效的提高网络鲁棒性。

以上显示和描述了本发明的基本原理、主要特征及优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。