, 杨青文1, 王金涛2, 刘华伟1 1. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;
2. 沈阳航空航天大学 民用航空学院, 辽宁 沈阳 110135
收稿日期：2020-04-26
基金项目：国家自然科学基金资助项目(61671141)。
作者简介：刘军(1969-), 男, 辽宁沈阳人, 东北大学副教授。
摘要：由于空间网络的高动态性及资源受限等原因, 其可靠性面临严峻考验, 亟需一种合理的风险评估及性能恢复方案.针对空间信息网的弹性恢复策略, 采用基于改进遗传算法的恢复策略确定受损元件的修复顺序, 以加快弹性恢复; 采用网络拓扑控制方法, 弱化受损关键节点的重要程度, 降低网络弹性损失.实验仿真了不同恢复资源数量下采用不同恢复策略的网络弹性损失, 结果表明两种方案分别在恢复资源受限及恢复资源匮乏的情况下具有较好的恢复性能.
关键词：空间信息网弹性优化恢复性遗传算法
Spatial Information Network Restoration Strategy Based on Improved Genetic Algorithm
LIU Jun1
, YANG Qing-wen1, WANG Jin-tao2, LIU Hua-wei1 1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2. Civil Aviation College, Shenyang Aerospace University, Shenyang 110135, China
Corresponding author: LIU Jun, E-mail: liujun@cse.neu.edu.cn.
Abstract: Due to the high dynamics and limited resources of space network, its reliability is faced with severely tested, and a reasonable risk assessment and performance recovery plan was urgently needed. For the elastic recovery strategy of spatial information network, the repair order of damaged components was determined by the recovery strategy based on the improved genetic algorithm, so as to speed up the elastic recovery. The network topology control method was adopted to reduce the importance of damaged key nodes and the loss of network elasticity. The experiment simulates the loss of network resilience with different recovery strategies under different amounts of recovery resources. The results show that the two schemes have better recovery performances when recovery resources are limited and scarce.
Key words: spatial information networkresilienceoptimizationrestorationgenetic algorithm
空间信息网依靠卫星组网及各种先进星上通信技术, 将负载各种功能设备(如传感器、深空探测设备等)并具有通信能力的空间站、卫星及地面基站有机连接在一起[1], 通过卫星之间转发或反射实现星间、星地互连和信息交换, 构成了能够对多源信息实时获取、处理和转发的天地一体化分布式信息网络[2-4].
由于太空环境恶劣、天基信息网络中资源受限, 再加上各种人为破坏行为或意外情况的发生, 不可避免出现元件损坏的情况; 另外, 随着一体化的推进, 单节点的损坏有可能导致整体网络性能急剧下降[5].因此, 增强抗风险能力, 并快速恢复受损网络的性能对于空间信息网至关重要.
弹性是一种常见的系统抗风险指标, 广泛应用于各个领域.相比于鲁棒性、可靠性等指标, 弹性评估着重考虑系统在遭受危害时的脆弱程度, 以及由受损状态逐渐恢复性能这一整个过程.针对空间信息网可能遭受的各种危害情况, 弹性分析能更加直观地反映出系统在遭受危害时的性能损失及性能恢复能力[6].早在2010年, 美国就提出将“弹性”作为太空体系构建的一个基本原则, 并深入研究[7]; 如今, 弹性对于空间信息网自适应理论具有十分重要的意义[8-9].当前国内外关于系统的弹性评估有很多较为成熟的研究: Pettit等[10]在研究供应链的稳定性时, 从脆弱性和恢复性两方面出发, 由影响脆弱性的7个因素和影响承受恢复能力的14个因素对供应链系统进行弹性综合评估; Khaled等[11]提出了一种用于评估铁路基础设施组成部件重要性的数学模型, 其通过对部件中断增加的延迟来评估部件的重要性, 对于关键部件进行优先保护或增加必要的冗余来提高铁路网弹性; 张妍平等[12]对海洋石油水下防喷器组供电与控制系统进行弹性评估, 通过动态贝叶斯网络模拟可靠性退化与恢复过程, 使弹性评估的定量化结果更加准确; Paul等[13]在电力系统抗灾能力的研究中, 引入“弹性五边形”, 提出了一种天气和时间相关的蒙特卡罗模拟方法, 用以估计严重风暴期间受损风力发电机的数量, 并量化了风力发电机的恢复能力; Ahmadiana等[14]提出了一种评估和提高网络弹性的定量方法, 使用弹性系数最小的组件代表网络整体弹性; Zhang[15]提出了一种通过节点和连边衡量网络弹性的方法, 使用负载状况和负载的传输速率来描述网络状态, 采用加权的方法计算整个网络的弹性指标, 最后通过调整网络负载的方法增强网络整体弹性.
空间信息网是一种移动自组织网络, 使用无线通信的同时还具有拓扑时变、资源受限等特性, 使得传统的恢复方案难以达到理想的效果.因此, 本文针对空间信息网恢复资源受限的特点, 根据不同的资源状况, 提出了一种基于改进遗传算法确定受损元件恢复顺序的恢复策略, 以及网络拓扑控制的优化方案, 以快速恢复空间信息网各方面的性能, 降低弹性损失.
1 系统模型及问题描述建立了空间信息网的网络模型, 以便进行弹性恢复阶段的优化和性能评估.由于空间信息网的结构复杂, 处理数据较多, 为了简化计算、方便研究, 分别将节点和链路以集合的形式表示, 用G表示网络的拓扑图, 即G=(V, E), 其中V为节点集合{ν1, ν2, ν3, …, νn}, E为链路连通性集合{a11, a12, a13, …, ann}.令A表示n×n的邻接矩阵:
 | (1) |
 | (2) |
节点νi直接连接节点Bi的集合称为邻居节点, 令di表示节点νi的度数(即di等于νi的相邻节点数).将Dn定义为由每个节点的度数组成的对角矩阵:
 | (3) |
 | (4) |
 | (5) |
 | 图 1 空间信息网弹性评估的恢复阶段Fig.1 Recovery phase of spatial information network elasticity assessment |
式中: TP(t)和P(t)分别是遭受攻击前后的性能曲线; t1是开始恢复的时间; T是性能完全恢复的时间.弹性损失RL越小, 说明该受损网络的弹性恢复性能越好.
2 网络恢复策略及恢复性阶段评估空间信息网作为一种移动自组织网络, 在组网灵活、应用广泛的同时也存在着拓扑时变、资源与安全受限等特征, 给受损元件的修复带来了极大挑战.针对以上问题, 空间信息网的恢复策略需要满足以下要求: 能够适应不同的恢复资源状况, 在恢复资源严重匮乏的情况下依然能够使网络恢复到一定性能; 要尽可能快速修复重要节点, 以满足大量、紧急的业务需求.针对恢复资源有限的情况, 提出了一种使用改进的遗传算法确定元件恢复顺序的恢复策略, 优先进行重要节点的修复, 快速恢复网络性能; 针对资源严重匮乏的情况, 提出了空间信息网的拓扑控制优化方案, 弱化关键节点的重要性, 从而有效降低弹性损失; 提出了空间信息网弹性恢复能力的评估指标, 以对方案的性能作出评价.
2.1 改进的遗传算法确定元件恢复顺序遗传算法(genetic algorithm, GA)[16-17]模拟了自然界中生物种群的遗传和进化过程, 是一种自适应全局搜索最优算法.传统遗传算法利用N个随机生成的初始序列个体来模拟进化过程, 每个个体被编码为基因型的字符串.由于使用随机序列作为初始解, 算法具有很大的不确定性, 难以收敛到全局最优解.因此, 对遗传算法进行如下改进: 考虑到网络拓扑对网络整体性能的重要性, 在恢复受损元件时可以结合网络拓扑指标来优化受损元件恢复顺序, 将基于拓扑指标(度数、介数、加权度、连通性等指标)的一些受损元件进行降序排列, 并将其视为恢复序列, 产生的N个个体作为第一代遗传算法的初始种群.然后, 评估其相对于整个种群的相对适合度值, 通过选择算子、交叉算子和变异算子产生后代.算法1的具体步骤如下.
算法1:改进遗传算法确定元件恢复顺序.
输入: 受损元件编码集S和网络拓扑, 最大迭代次数M
输出: 最佳恢复序列P
1. ?t=0, P(t)=sort S by topology Index;
2. ?while(t < M)
3. ??while
4. ???i=arg maxj∈P(t)\P(t+1)(Pj);
5. ???P(t+1)=P(t)∪{i};
6. ??end while
7. ??sum=0, ε=Random(0, 1), O=?;
8. ??for each j in P(t)\P(t+1)
9. ???sum=sum+Pj;
10. ????O=O∪{j};
11. ????if(sum>ε) P(t+1)∪O;
12. ????if(|P(t+1)|≥|P(t)|)break;
13. ???end for
14. ???for each pair in pairs(P(t+1))
15. ????if(Random(0, 1) < Pc)
16. ?????Hybridize(pair);
17. ??????if(Random(0, 1) < Pm) Mutate(pair);
18. ????end if
19. ???end for
20. ???t=t+1;
21. ??end while
22. ??P=arg maxj∈P(t)(Pj);
23. ??return P
1) 将受损元件进行编号, 以恢复顺序进行排列组成基因型.设初始群体的长度为N, 进化迭代计数器t=0, 最大进化迭代次数为M, 用P(t)代表t时刻的全部基因型集合.
2) 根据空间信息网性能指标, 计算恢复过程中P(t)中每个基因型的弹性损失RL, 并将其按升序排列.由适应度函数f(i)=max(a－bi, 1)定义基因型的适应度值:
 | (6) |
3) 用选择算子根据Pi选择优良的基因型.从排序后的P(t)中从后向前选取比例为λ的基因型直接作为下一代保存, 对应伪代码中3~6行.采用轮盘赌选择技术选择占比例1－λ的基因: 令sum={P1, P1+P2, …, P1+P2+…+PN}, 随机选择[0, 1]之间的数字ε, 将sum中的每个元素依次与ε进行比较, 选择首次超过ε的元素与其对应的基因型.重复这个过程直到达到足够的下一代基因型, 对应伪代码中7~13行.
4) 使用交叉算子产生新的个体.将选取的基因型两两随机进行组合, 对于每一对基因型, 以交叉概率Pc(取0.80~0.95)按照交叉算子规则进行交叉: 随机选择切割点将父代基因型切割为两个子串; 两个后代分别从两个父代继承较长的子串, 并按照另一个父代中出现的基因顺序替换较短子字符串的基因, 如图 2所示.
图 2(Fig. 2)
 | 图 2 交叉产生后代Fig.2 Cross to generate the offspring |
5) 在每一个后代的基因型中, 随机选择两个基因以变异概率Pm(取0.005~0.01)进行替换, 如图 3所示.群体P(t)经过了上述三步遗传算子操作后得到下一代群体P(t+1).
图 3(Fig. 3)
 | 图 3 后代基因型变异Fig.3 Genomic variants of offspring |
交叉和变异过程对应伪代码14~19行, 在伪代码中进行了简写, 具体过程如4)，5)所示.
6) 如果达到最大进化迭代次数M, 输出P(t)中适应度最高的字符串基因, 否则回到第二步继续迭代.
基于上述过程, 设每一代的个体数量为50, 最大迭代代数为100, 交叉概率为0.8, 变异概率为0.01, 以及直接选作下一代的基因型比例λ=4%.最后一代中, 具有最小弹性损失的基因型即最佳恢复顺序的受损元件序列.在空间信息网中, 该算法由恢复资源调度中心或地面控制中心进行计算, 以求得全局最优的恢复策略.
2.2 网络拓扑控制优化在空间信息网中, 由于维护成本高、修理难度大, 卫星节点可能时常处于资源严重匮乏的状态.当受损元件的数量与恢复资源的数量的比值超过一定值μ(本文取μ=5)时, 认为恢复资源严重匮乏, 此时受损元件的修复速度非常缓慢, 需要很长时间才能使网络恢复到初始性能, 造成较大的弹性损失.而通过拓扑控制, 可以在受到破坏后实现分区网络的互连, 弱化受损关键点的重要性, 从而降低网络弹性损失.这里提出了三种本地化的拓扑改进方案, 以提高网络的弹性: ①本地全网状策略(local full mesh, LFM); ②基于随机选择的最少链路数策略(least number of links with random selection, LNLRS); ③基于最少链路成本的最少链路数策略(least number of links with least cost, LNLLC)[18].
1) 本地全网状策略(LFM)调整受损关键点所有邻居节点的传输功率使得所有成对的邻居节点之间都能够直接通信.关键节点A周边的本地全网方案如图 4所示, 当节点度为4的关键节点A受损时, 增加其邻居节点的传输功率, 使原来不直接相连的本地节点也能够直接连接, 从而降低了由于节点A的损坏导致的网络性能下降.
图 4(Fig. 4)
 | 图 4 关键节点A周边的本地全网方案Fig.4 Local network solution around key node A (a)—关键节点A；(b)—节点A的LFM方案. |
2) 最少链路(LNL)方案在关键节点损坏时, 以最少的备用链路数减少对网络的影响.LNL算法首先搜集关键节点周围的网络链路信息, 并计算关键节点故障时本地网络划分的集群数, 从而得出需要增加多少附加链路.关键节点A的最少链路方案如图 5所示, 当关键节点A有故障时, 本地网络划分为3个群集(NCL=3).需要考虑的是如何选取链路才能使网络的恢复性能最好, 这里提出两种方案来产生所需链路的最小数量[19].
图 5(Fig. 5)
 | 图 5 关键节点A的最少链路方案Fig.5 LNL scheme of local key node A (a)—关键节点A；(b)—LNLRS方案；(c)—LNLLC方案. |
第一种方案是使用基于随机选择的最少链路数策略(LNLRS).在关键节点受损时, 首先选择一对未连接的邻居节点建立备用链路, 如果该链路能够减少本地网络中的群集数则选定该链路, 否则丢弃该链路.继续执行该过程直至受损后本地网络的群集数变为1.LNLRS的优点是几乎不需要了解拓扑, 由于随机选择, 因此在解决方案中也可能会选择能耗高的链路.
第二种方案是基于最少链路成本的最少链路数策略(LNLLC).令Cij表示节点对i和j之间的链路成本, 在空间信息网中, 随着距离的增加, 发射功率和传播时延也相应增加, 故可等于节点对之间的距离d(i, j).在关键节点受损时, LNLLC方法在不相连的群集中选择距离最短的节点对建立备用链路.节点位置可以通过卫星定位技术[20]获得.除了距离成本, 也可以选择其他成本度量, 例如延迟、信噪比、比特误码率等.
2.3 空间信息网的恢复性评估本文为评估空间信息网的弹性恢复能力制定了三个指标: 网络连通度、数据传输时延效率和数据成功传输效率.连通度恢复是对空间信息网拓扑恢复能力的评估, 反映其受损后的拓扑恢复性能, 定义如下:
 |
 | (7) |
数据传输时延效率恢复通过量化节点间数据传输时延效率, 反映空间信息网通信传输能力方面的恢复性能:
 | (8) |
数据成功传输效率恢复通过计算节点间数据成功传输的效率反映空间信息网的通信传输可靠性的恢复性能:
 | (9) |
上述三个指标分别在网络连通度、传输时延、误码率三个方面对空间信息网的恢复性能做出了评估, 以此可以在不同的恢复资源数量下对不同的恢复策略的弹性恢复能力做出比较, 以选出性能最佳的恢复方案.
3 算法仿真与分析本文使用NS2进行仿真实验.设网络中节点个数为100, 给定了固定的攻击强度AS(设受损元件的数量与攻击强度成正相关)为0.1的基于随机故障的攻击策略, 并选取数据传输时延效率作为网络的性能指标, 对不同恢复资源数量下采用不同恢复策略的弹性损失情况进行了仿真.假设每个恢复资源只能恢复一个受损元件, 则这里的恢复资源即单位时间恢复的受损元件数.
1) 改进遗传算法与传统遗传算法对比: 改进遗传算法和传统遗传算法对弹性损失的影响如图 6所示.分别采用改进遗传算法和传统遗传算法确定受损元件的恢复顺序, 可以看出, 随着恢复资源数量的增多, 空间信息网的弹性损失逐渐减小, 最后趋于稳定.而结合网络拓扑指标改进的遗传算法的恢复策略的弹性恢复性能更加显著.同样以网络连通度和数据成功传输效率为评估网络性能指标时, 也会产生类似的结果.
图 6(Fig. 6)
 | 图 6 改进遗传算法和传统遗传算法对弹性损失比的影响Fig.6 Impact of improved genetic algorithm and traditional genetic algorithm on elastic loss ratio |
2) 拓扑控制优化方案仿真分析: 三种拓扑控制优化方案对弹性损失的影响如图 7所示, 可以看出三种策略在不同恢复资源数量下的弹性损失RL基本保持不变.其中, LNLLC策略的弹性恢复性能最好，这是因为LNLLC不仅使用最少的备用链路来达成本地全连通, 同时也考虑了每条链路的距离成本, 因此相对其他两种方案的时延效率损失最低.
图 7(Fig. 7)
 | 图 7 三种修复方案对弹性损失比的影响Fig.7 Impact of three repair schemes on elastic loss ratio |
3) 恢复性能评估分析: 同时修复受损元件, 通过改进的遗传算法确定受损元件的恢复顺序, 基于关键点的拓扑控制优化策略(这里选取LNLLC策略), 在不同恢复资源数量的情况下进行仿真, 弹性损失情况如图 8所示.可以看出, 随着恢复资源数量的增加, 拓扑优化策略的弹性损失基本不变, 在恢复资源数量为0~3时该方案恢复性能最好，在恢复资源数量为0~9时, 由于不足以对受损元件进行同时修复, 同时修复策略的弹性损失很大, 而在恢复资源数量大于10时, 修复资源充足, 同时修复策略的弹性损失最小; 改进遗传算法策略的弹性损失随着恢复资源数量的增加逐渐降低, 在恢复资源数量为4~9时该方案恢复性能最好.
图 8(Fig. 8)
 | 图 8 恢复资源数量为0~14时不同修复策略的弹性损失比Fig.8 The elastic loss ratio of different repair strategies when the number of recovery resources is 0 to 14 |
4 结论1) 本文建立了空间信息网的网络模型, 对空间信息网元件遭受损坏后的弹性恢复阶段进行了研究, 提出了一种基于改进遗传算法的恢复策略, 并对受损后的网络拓扑控制进行了优化.
2) 在不同恢复资源数量的场景下, 对同时修复策略、基于改进的遗传算法的修复策略和基于关键点的拓扑优化策略(LNLLC策略)进行了比较, 得出了不同恢复资源数量下的最佳恢复策略: 同时修复策略在恢复资源充足的情况下弹性恢复性能最好；在恢复资源有限的情况下, 基于改进的遗传算法的修复策略的弹性恢复性能最好；在恢复资源匮乏的情况下, 拓扑优化控制策略的弹性恢复性能最好.
参考文献
| [1] | Yu Q, Wang J, Bai L. Architecture and critical technologies of space information networks[J]. Journal of Communications and Information Networks, 2016, 1(3): 1-9. DOI:10.1007/BF03391565 |
| [2] | 刘立祥. 天地一体化信息网络的体系结构与协议分析[J]. 重庆邮电大学学报(自然科学版), 2018, 30(1): 9-21. (Liu Li-xiang. Analysis of architecture and protocol of space-ground integrated information network[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2018, 30(1): 9-21.) |
| [3] | Du J, Jiang C, Guo Q, et al. Cooperative earth observation through complex space information networks[J]. IEEE Wireless Communications, 2016, 23(2): 136-144. DOI:10.1109/MWC.2016.7462495 |
| [4] | 吴曼青, 吴巍, 周彬, 等. 天地一体化信息网络总体架构设想[J]. 卫星与网络, 2016(3): 30-36. (Wu Man-qing, Wu Wei, Zhou Bin, et al. The overall framework of the integrated information network[J]. Satellite & Network, 2016(3): 30-36.) |
| [5] | 李张元, 赵忠文, 杨苗本. 基于复杂网络的空间信息网脆弱性研究综述[J]. 兵器装备工程学报, 2018, 39(6): 159-164. (Li Zhang-yuan, Zhao Zhong-wen, Yang Miao-ben. Literature review on vulnerability of space information network based on complex networks[J]. Journal of Ordnance Equipment Engineering, 2018, 39(6): 159-164.) |
| [6] | 汉京滨, 张雅声, 汤亚锋, 等. 卫星通信系统弹性评估指标体系研究[C]// 第六届中国指挥控制大会论文集(下册). 北京: 中国指挥与控制学会, 2018: 364-368. (Han Jing-bin, Zhang Ya-sheng, Tang Ya-feng, et al. Research on the resilience assessment index system of satellite communication system[C]// Proceedings of the 6th China Command and Control Conference. Beijing: China Command and Control Society, 2018: 364-368. ) |
| [7] | 汤亚锋, 徐艳丽, 李纪莲. 太空体系弹性评估方法综述[J]. 装备学院学报, 2017, 28(3): 74-80. (Tang Ya-feng, Xu Yan-li, Li Ji-lian. A summary of space system resilience assessment methods[J]. Journal of Equipment Academy, 2017, 28(3): 74-80.) |
| [8] | Zhang X, Miller-Hooks E, Denny K. Assessing the role of network topology in transportation network resilience[J]. Journal of Transport Geography, 2015, 46: 35-45. DOI:10.1016/j.jtrangeo.2015.05.006 |
| [9] | Lam C Y. Resilience of logistics network: analysis and design[C]// 2016 World Congress on Industrial Control Systems Security(WCICSS). London, 2016: 1-5. |
| [10] | Pettit T J, Croxton K L, Fiksel J. Ensuring supply chain resilience: development and implementation of an assessment tool[J]. Journal of Business Logistics, 2013, 34(1): 46-76. DOI:10.1111/jbl.12009 |
| [11] | Khaled A, Jin M, Clarke D, et al. Train design and routing optimization for evaluating criticality of freight railroad infrastructures[J]. Transportation Research Part B: Methodological, 2015, 71: 71-84. DOI:10.1016/j.trb.2014.10.002 |
| [12] | 张妍平, 蔡宝平, 刘永红, 等. 海洋石油水下防喷器组供电与控制系统宏观弹性评估方法研究[C]// 中国海洋工程学会. 第十九届中国海洋(岸)工程学术讨论会论文集(上). 重庆: 中国海洋学会海洋工程分会, 2019: 360-366. (Zhang Yan-ping, Cai Bao-ping, Liu Yong-hong, et al. Study on macro elasticity evaluation method for power supply and control system of offshore oil subsea BOP stack[C]// Proceedings of the 19th China Ocean(Shore)Engineering Symposium. Chongqing: Marine Engineering Branch of Chinese Society of Oceanography, 2019: 360-366. ) |
| [13] | Pual S, Rather Z. Quantification of wind farm operational and infrastructure resilience[C]// 2018 IEEE PES Innovative Smart Grid Technologies Conference Europe(ISGT-Europe). Sarajevo: IEEE, 2018: 1-5. |
| [14] | Ahmadiana N, Lim G J, Cho J, et al. A quantitative approach for assessment and improvement of network resilience[J]. Reliability Engineering and System Safety, 2020[2020-04-26]. https://doi.org/10.1016/j.ress.2020.106977. |
| [15] | Zhang C, Xu X, Dui H. Resilience measure of network systems by node and edge indicators[J]. Reliability Engineering and System Safety, 2020[2020-04-26]. https://doi.org/10.1016/j.ress.2020.107035. |
| [16] | Kumar M, Husian M, Upreti N, et al. Genetic algorithm: review and application[J]. International Journal of Information Technology and Knowledge Management, 2010, 2(2): 451-454. |
| [17] | Gen M, Cheng R, Lin L. Network models and optimization: multiobjective genetic algorithm approach[M]. London: Springer Science & Business Media, 2008. |
| [18] | Guan Q, Yu F R, Jiang S, et al. Topology control in mobile ad hoc networks with cooperative communications[J]. IEEE Wireless Communications, 2012, 19(2): 74-79. DOI:10.1109/MWC.2012.6189416 |
| [19] | Guan Q, Yu F, Jiang S, et al. Joint topology control and authentication design in mobile ad hoc networks with cooperative communications[J]. IEEE Transactions on Vehicular Technology, 2012, 61(6): 2674-2685. DOI:10.1109/TVT.2012.2196061 |
| [20] | Godsil C, Royle G. Algebraic graph theory[M]. New York: Springer Science & Business Media, 2013. |
