本发明公开了一种基于模拟退火算法的多自主体网络容侵能力评估方法，本发明将模拟退火技术应用于网络容侵能力评估领域，同时在传统的模拟退火方法上综合考虑了在网络健壮性计算子集对更新时引入了三种备选状态，使得子集对更新具有更大采样随机性。本发明具有克服大规模多自主体网络容侵能力评估因NP难问题而无法求解的优点。
1.一种基于模拟退火算法的多自主体网络容侵能力评估方法，其特征在于：包括以下步骤：
1)条件设置：采用图论中的节点表示多自主体，图论中的边表示自主体之间的通信链路；给定有向图D＝(V,E)，其中V为节点集合，E为边集；令A(D)为有向图D的邻接矩阵，再给定初始温度为T0，终止温度为Tf，降温温度为ΔT，迭代次数q，令实时温度Tt为初始温度T0；
设置初始健壮性数值为(rmin，smin)；令rmin＝min{δin(D)，[n/2]}，smin＝n，其中δin(D)表示有向图D的最小入度，n表示有向图中的节点个数；
2)获取初解：在节点集V中随机产生一对非空不相交子集对S1,S2，进行健壮性计算f(A(D)，S1，S2，rmin，smin)，得到子集对S1,S2满足的最优健壮性数值(r，s)；
3)产生新解：更新子集对S1,S2形成新的子集对S’1，S’2，再次进行健壮性计算f(A(D)，S’1，S’2，rmin，smin)，得到子集对S’1，S’2满足的最优健壮性数值(r’，s’)；
4)将初解与新解进行比较计算，记Δr＝(r’-r)×n+(s’-s)；假如新解优于初解，即Δr＜0，直接接受新解(S’1，S’2，r’，s’)；如果新解劣于初解，及Δr≥0，按照Metropolis准则接受新解(S’1，S’2，r’，s’)；
(4.2)假如exp(–Δr/Tt)>ξ，接受新解(S’1，S’2，r’，s’)；否则保持初解(S1，S2，r，s)；
5)(rmin，smin)数值更新：假如步骤4)中得到结果为新解，那么令rmin＝r’，smin＝s’；假如步骤4)中得到结果为初解，那么令rmin＝r，smin＝s；
6)当迭代次数达到设定上限时，实时温度降低ΔT，即Tt←Tt-ΔT，转步骤7)；否则转步骤2)；
7)当实时温度Tt大于算法终止温度Tf时，转步骤2)；否则运算结束。
2.根据权利要求1所述的一种基于模拟退火算法的多自主体网络容侵能力评估方法，其特征在于：步骤2)和3)子集对满足的最优健壮性计算方法包括：(2.1)已知n表示图D节点个数，令r＝rmin，s＝smin；
(2.2)假如健壮性值r＞0，则进行健壮性有效函数RobustHolds(A(D)，S1，S2，r，s)判定；
如果判定结果为真，那么当前健壮性数值(r，s)即为节点子集对S1,S2满足的最优健壮性值；
如果判定结果为假，则健壮性数值s减小1，值r不变；当值s减至0时，健壮性值r减小1，值s变为n；假如值r＝0，运算结束；
步骤(2.2)关于RobustHolds判定的方法主要包括以下步骤：(2.2.1)计算非空子集S1中有入度邻节点数大于等于r个的节点数，记k1；
(2.2.2)计算非空子集S2中有入度邻节点数大于等于r个的节点数，记k2；
(2.2.3)当k1＝S1或者k2＝S2或者(k1+k2)>＝s时，RobustHolds判定为真，否则判定为假。
3.根据权利要求1所述的一种基于模拟退火算法的多自主体网络容侵能力评估方法，其特征在于：步骤3)中，子集对S1和S2的更新方法包括：(3.1)初始化S1的邻居集合Sneighbors；
(3.2)生成随机数ξ∈U(0,1)；当随机数ξ小于1/3时，从S1中随机挑选一个节点替换为从Sneighbors中随机挑选出的一个节点；当随机数ξ大于等于1/3并且小于2/3时，从Sneighbors中随机挑选一个节点添加到集合S1中；当随机数ξ大于等于2/3并且小于1时，随机从S1中删除一个节点；
(3.3)从集合S1的差集进行采样获取新的S2集合。
一种基于模拟退火算法的多自主体网络容侵能力评估方法
技术领域
[0001] 本发明涉及网络容侵能力评估技术领域，特别是一种基于模拟退火算法的多自主体网络容侵能力评估方法。
背景技术
[0002] 多自主体系统是指具备感知、通信、计算和执行能力的多个自主体组成的大规模网络系统，被广泛用作分布式协同算法的实现载体。多自主体系统不仅具备一般分布式系统所具有的资源共享、协调性好、自主性强等优点，而且由于各个自主体通过协调合作能够解决大规模的复杂性问题，使其具备很强的鲁棒性与可靠性。然而近些年，随着网络安全风险日益突出，网络设计者在构建多自主体系统过程中对其网络容侵能力的评估也越来越重视。网络拓扑(r,s)-健壮性是目前一种衡量多自主体网络容侵能力的有效指标。
[0003] 现有的对网络拓扑健壮性评估方法如穷举、图构建、线性规划、函数关系等，对其(r,s)两个数值的评估，都是通过穷举和遍历算法来求得的，这类方法需要获取网络通信拓扑全局的链路信息。然而已有文献证明，对健壮性中的数值对(r,s)评估判定是一个NP难问题。因而上述传统方法仅适用于节点数目较少的小型多自主体网络，对于节点数目众多的大规模网络，均无法适用。
发明内容
[0004] 本发明为克服现有评估技术的不足，提供了一种较为简明、易于实现并且适用于节点数目众多的大规模多自主体系统的网络容侵能力评估方法。
[0005] 本发明解决其技术问题所采用的技术方案是：
[0006] 一种基于模拟退火算法的多自主体网络容侵能力评估方法，包括以下步骤：
[0007] 1)条件设置：采用图论中的节点表示多自主体，图论中的边表示自主体之间的通信链路；给定有向图D＝(V,E)，其中V为节点集合，E为边集；令A(D)为有向图D的邻接矩阵，再给定初始温度为T0，终止温度为Tf，降温温度为ΔT，迭代次数q，令实时温度Tt为初始温度T0；设置初始健壮性数值为(rmin，smin)；令rmin＝min{δin(D)，[n/2]}，smin＝n，其中δin(D)表示有向图D的最小入度，n表示有向图中的节点个数；
[0008] 2)获取初解：在节点集V中随机产生一对非空不相交子集对S1,S2，进行健壮性计算f(A(D)，S1，S2，rmin，smin)，得到子集对S1,S2满足的最优健壮性数值(r，s)；
[0009] 3)产生新解：更新子集对S1,S2形成新的子集对S’1，S’2，再次进行健壮性计算f(A(D)，S’1，S’2，rmin，smin)，得到子集对S’1，S’2满足的最优健壮性数值(r’，s’)；
[0010] 4)将初解与新解进行比较计算，记Δr＝(r’-r)×n+(s’-s)；假如新解优于初解，即Δr＜0，直接接受新解(S’1，S’2，r’，s’)；如果新解劣于初解，及Δr≥0，按照Metropolis准则接受新解(S’1，S’2，r’，s’)；
[0011] Metropolis准则包括以下步骤：
[0012] (4.1)生成随机数ξ∈U(0,1)；
[0013] (4.2)假如exp(–Δr/Tt)>ξ，接受新解(S’1，S’2，r’，s’)；否则保持初解(S1，S2，r，s)；
[0014] 5)(rmin，smin)数值更新：假如步骤4)中得到结果为新解，那么令rmin＝r’，smin＝s’；假如步骤4)中得到结果为初解，那么令rmin＝r，smin＝s；
[0015] 6)当迭代次数达到设定上限时，实时温度降低ΔT，即Tt←Tt-ΔT，转步骤7)；否则转步骤2)；
[0016] 7)当实时温度Tt大于算法终止温度Tf时，转步骤2)；否则运算结束。
[0017] 作为优选，步骤2)和3)子集对满足的最优健壮性计算方法包括：
[0018] (2.1)已知n表示图D节点个数，令r＝rmin，s＝smin；
[0019] (2.2)假如健壮性值r＞0，则进行健壮性有效函数RobustHolds(A(D)，S1，S2，r，s)判定；如果判定结果为真，那么当前健壮性数值(r，s)即为节点子集对S1,S2满足的最优健壮性值；如果判定结果为假，则健壮性数值s减小1，值r不变；当值s减至0时，健壮性值r减小1，值s变为n；假如值r＝0，运算结束；
[0020] 步骤(2.2)关于RobustHolds判定的方法主要包括以下步骤：
[0021] (2.2.1)计算非空子集S1中有入度邻节点数大于等于r个的节点数，记k1；
[0022] (2.2.2)计算非空子集S2中有入度邻节点数大于等于r个的节点数，记k2。
[0023] (2.2.3)当k1＝S1或者k2＝S2或者(k1+k2)>＝s时，RobustHolds判定为真，否则判定为假。
[0024] 作为优选，步骤3)中，子集对S1和S2的更新方法包括：
[0025] (3.1)初始化S1的邻居集合Sneighbors；
[0026] (3.2)生成随机数ξ∈U(0,1)；当随机数ξ小于1/3时，从S1中随机挑选一个节点替换为从Sneighbors中随机挑选出的一个节点；当随机数ξ大于等于1/3并且小于2/3时，从Sneighbors中随机挑选一个节点添加到集合S1中；当随机数ξ大于等于2/3并且小于1时，随机从S1中删除一个节点；
[0027] (3.3)从集合S1的差集进行采样获取新的S2集合。
[0028] 退火模拟法是一种求解近似最优解的方法，最早用于模拟物理学中金属融化的过程来寻找最优解，后来被广泛的应用于各个领域如旅行商问题，影响力最大化问题。
[0029] 本发明将模拟退火技术应用于网络容侵能力评估领域，同时在传统的模拟退火方法上综合考虑了在网络健壮性计算子集对更新时引入了三种备选状态，使得子集对更新具有更大采样随机性。
[0030] 本发明具有克服大规模多自主体网络容侵能力评估因NP难问题而无法求解的优点。
附图说明
[0031] 图1是本发明的流程图。
[0032] 图2是具体步骤的流程图。
具体实施方式
[0033] 下面结合说明书附图，进一步说明本发明：
[0034] 一种基于模拟退火算法的多自主体网络容侵能力评估方法，包括以下步骤：
[0035] 1)条件设置：为方便阐释本发明，借助数学图论来描述多自主体网络模型，用图论中的节点表示多自主体，图论中的边表示自主体之间的通信链路。给定有向图D＝(V,E)，其中V为节点集合，E为边集。令A(D)为有向图D的邻接矩阵，再给定初始温度为T0，终止温度为Tf，降温温度为ΔT，迭代次数q，令实时温度Tt为初始温度T0。设置初始健壮性数值为(rmin，smin)。令rmin＝min{δin(D)，[n/2]}，smin＝n，其中δin(D)表示有向图D的最小入度，n表示有向图中的节点个数。
[0036] 2)获取初解：在节点集V中随机产生一对非空不相交子集对S1,S2，进行健壮性计算f(A(D)，S1，S2，rmin，smin)，得到子集对S1,S2满足的最优健壮性数值(r，s)。
[0037] 3)产生新解：更新子集对S1,S2形成新的子集对S’1，S’2，再次进行健壮性计算f(A(D)，S’1，S’2，rmin，smin)，得到子集对S’1，S’2满足的最优健壮性数值(r’，s’)。
[0038] 4)将初解与新解进行比较计算，记Δr＝(r’-r)×n+(s’-s)。假如新解优于初解(Δr＜0)，直接接受新解(S’1，S’2，r’，s’)；如果新解劣于初解(Δr≥0)，按照Metropolis准则接受新解(S’1，S’2，r’，s’)。Metropolis准则包括以下步骤：
[0039] (4.1)生成随机数ξ∈U(0,1)。
[0040] (4.2)假如exp(–Δr/Tt)>ξ，接受新解(S’1，S’2，r’，s’)；否则保持初解(S1，S2，r，s)。
[0041] 5)(rmin，smin)数值更新：假如步骤4)中得到结果为新解，那么令rmin＝r’，smin＝s’；假如步骤4)中得到结果为初解，那么令rmin＝r，smin＝s。
[0042] 6)当迭代次数达到设定上限时，实时温度降低ΔT，即Tt←Tt-ΔT，转步骤6)；否则转步骤2)。
[0043] 7)当实时温度Tt大于算法终止温度Tf时，转步骤2)；否则运算结束。
[0044] 进一步，步骤2)和3)子集对满足的最优健壮性计算方法包括：
[0045] (2.1)已知n表示图D节点个数，令r＝rmin，s＝smin。
[0046] (2.2)假如健壮性值r＞0，则进行RobustHolds(A(D)，S1，S2，r，s)判定。如果判定结果为真，那么当前健壮性数值(r，s)即为节点子集对S1,S2满足的最优健壮性值；如果判定结果为假，则健壮性数值s减小1，值r不变。当值s减至0时，健壮性值r减小1，值s变为n。假如值r＝0，运算结束；
[0047] 步骤(2.2)关于RobustHolds判定的方法主要包括以下步骤：
[0048] (2.2.1)计算非空子集S1中有入度邻节点数大于等于r个的节点数，记k1。
[0049] (2.2.2)计算非空子集S2中有入度邻节点数大于等于r个的节点数，记k2。
[0050] (2.2.3)当k1＝S1或者k2＝S2或者(k1+k2)>＝s时，RobustHolds判定为真，否则判定为假。进一步，步骤3)中，子集对S1和S2的更新方法包括：
[0051] (3.1)初始化S1的邻居集合Sneighbors。
[0052] (3.2)生成随机数ξ∈U(0,1)。当随机数ξ小于1/3时，从S1中随机挑选一个节点替换为从Sneighbors中随机挑选出的一个节点；当随机数ξ大于等于1/3并且小于2/3时，从Sneighbors中随机挑选一个节点添加到集合S1中；当随机数ξ大于等于2/3并且小于1时，随机从S1中删除一个节点。
[0053] (3.3)从集合S1的差集进行采样获取新的S2集合。
[0054] 退火模拟法是一种求解近似最优解的方法，最早用于模拟物理学中金属融化的过程来寻找最优解，后来被广泛的应用于各个领域如旅行商问题，影响力最大化问题。本发明将模拟退火技术应用于网络容侵能力评估领域，同时在传统的模拟退火方法上综合考虑了在网络健壮性计算子集对更新时引入了三种备选状态，使得子集对更新具有更大采样随机性。
[0055] 本发明的具体实施方式中凡未涉到的说明属于本领域的公知技术，可参考公知技术加以实施。
[0056] 以上具体实施方式是对本发明提出的一种基于模拟退火算法的多自主体网络容侵能力评估方法技术思想的具体支持，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在本发明技术方案基础上所做的任何等同变化或等效的改动，均仍属于本发明技术方案保护的范围。
