导语


观测网络的状态是我们探索和控制复杂系统动力学的基础，过去的十年里，网络控制的研究者已经有效解决了“确定系统是否可观测”这一问题，接下来的问题就是切实地设计和实现从有限的观测数据中推断状态的算法。而在大规模动态网络中，由于系统的高维特性，通常很难有足够的传感器节点，使得系统完全可观测。


近日，在《美国科学院院刊》（PNAS）上发表的“大规模网络功能可观测性与目标状态估计”一文中，作者提出了一种网络系统功能可观测性的图论方法，并设计了传感器布置和观测器设计的相关算法。文章表明，该方法可以使用最少传感器和计算信息，准确地估计大规模动态网络的目标状态。


研究领域：网络控制，可观测性，网络动力学，复杂网络

付宇德 | 作者

江水 | 审校

邓一雪 | 编辑



论文题目：Functional observability and target state estimation in large-scale networks

论文地址：https://www.pnas.org/content/119/1/e2113750119




1. 复杂动力系统的结构功能可观测性




以电网、神经网络和食物网等为代表的大规模复杂系统，通常可以被表示为一组相互关联的动力系统，这类复杂系统也被称为动力学网络（dynamical networks）。这类系统的动力学可以描述为如下的一组动力学方程：


对如上述系统，其输出可以完全反映系统状态的特性，称为可观测性（observability），即若可以根据控制输入u(t)和传感器的直接测量y(t)重构出x(t)的整个运动轨迹，则该动力系统完全可观测。从理论分析可以证明：当下述nq×n可观测矩阵O具有满秩时，该动力系统完全可观测：



观测上述动力学网络的状态，是人们探索和控制复杂自然、社会和技术系统的动力学的基础。尽管完全状态观测器在众多的工程应用中已取得了成功，如Luenberger观测器和Kalman滤波器等。但系统的高维性仍然是在大规模动态网络中直接运用这些方法的障碍，这需要不同的方法和新的技术来克服现有算法所缺乏的可拓展性。尤其在许多实际问题中，观测和估计整个高维系统的状态向量是不必要的，一般只需要关注感兴趣节点集合。该思想在各个领域得到了广泛的应用，如网络系统中的分散控制策略，即每个控制器只需要关注相应控制域中小部分节点的反馈信号。在该问题驱动下，学者提出了功能可观测性的定义：即使网络系统不完全可观测，函数观测器仍能够从有限的传感器中，重构出目标状态变量集合。

当前关于功能可观测性的研究，都是基于数值秩的条件，没有明确利用网络拓扑结构，因此，无法生成适用于大规模网络的可拓展算法。如图1所示，作者严格地建立了功能可观测性的图论条件（与基于秩的条件等价），图中蓝色节点为传感器集合，红色节点为目标集合，橙色节点为F0中非零元素确定的辅助节点最小集合。图1.A中F0的行数就是函数观测器的阶。图1.B给出了完全可观测系统的Luenberger观测器设计，其阶数为8。函数观测器可以通过更小的阶数r0=2来估计目标节点x10的状态。

图1. 动力系统的结构功能可观测性




2. 两个典型可观测性问题的算法设计




传感器可对系统特定变量及时测量。随着动态网络规模越来越大，无论是考虑成本还是从实际限制出发，对每一个状态变量都安装传感器是不现实的。因此，大规模网络中最少传感器布置问题对于大规模动态网络的控制是至关重要的，即如何确定一个最小的传感器集合，使得相应推断图中存在一条从每个目标节点到传感器节点的直接路径。

作者首先在有向小世界和无标度网络上实验（如图2.A），发现了相对少的目标节点保证系统功能可观测性所需要的传感器数量也较少，且二者之间的关系取决于网络结构。类似的结论也可以从真实世界网络上得到，这一方法可用于信息物理系统的潜在故障和网络攻击的监测和检测。

图2.大规模网络中传感器最小布置示意图

在确定传感器位置后，面临的是最小阶函数观测器的设计问题，即选择一个矩阵 F0来指导函数观测器的设计。同样在模型网络中，作者分别分析了最小函数观测器阶数和传感器节点数、目标节点数、网络规模等属性的关系（图3），发现与相应的Luenberger观测器相比，函数观测器的阶数要低得多。这也表明在大规模网络中设计和观测时，函数观测器能显著提高计算效率和可拓展性。

图3. 大规模网络的函数观测器设计

为了直观地展现函数观测器的设计效果，作者进一步比较了估计大规模网络的目标变量时函数观测器和Luenberger观测器的性能（图4）。结果表明函数观测器的计算优势使其在观测大规模网络时更具有优越性，特别是由于系统平衡或网络结构演变，希望对观测器进行持续重新设计的情形。

图4. 目标状态估计的观测器性能比较




3. 典型场景下的应用




针对上述理论与算法，作者在电网和航空网络两个不同的场景中开展应用研究，分别研究了欺骗攻击监测和流行病目标状态估计问题。

电网中两种常见的网络攻击类型，分别是以信号干扰为代表的拒绝服务型攻击和以数据损坏为代表的欺骗型攻击。根据攻击的具体情况，使用系统动力学和传输数据设计函数观测器，可以通过状态估计的方式恢复丢失数据。作者将电网动力学建模为耦合的一阶和二阶Kuramoto振荡器结构，并在IEEE-118电网数据中开展实验（图5）。研究证明，通过文章算法设计的函数观测器，结合交叉验证传输的测量数据，可以成功地检测到欺骗型网络攻击。此外，随着传感器数量的增加，函数观测器的尺寸比Luenberger观测器小得多，从而导致运行时间减少多达100倍。

图5. 电网中的欺骗攻击检测

同时，本文将研究应用于航空网络中新冠病毒的传播案例，其中假设疫情爆发于佛罗里达州迈阿密，其传播主要由国内航空运输引起，作者证明了通过该算法设计的函数观测器，可以用一组已进行充分检测的“传感器城市”中的已知病死率，估计一组监测不充分的“目标城市”中的感染人口。在这个应用中，函数观测器是在系统不完全可观测，但函数可测的情况下设计的。突出了文章方法的一个基本优势，即当传统的全状态估计器不适用时，函数观测器的设计仍然可以从稀疏的测量数据中给出系统状态的高质量估计。

图6. 航空网络中流行病的目标状态估计




4. 总结及展望




本文提出的方法，可以应用在基础设施和多智能体分散控制中的网络安全，不完全观测的流行病和生态系统管理状态估计，以及识别用于预后、诊断和治疗的生物标志物等领域。文章的结果提供了一个框架，在此框架下，可以通过间接测量来估计感兴趣的变量，而避免干扰系统功能和控制行为的变量。研究者还提供了一种替代方案，以降低实时反馈控制的基础设施、供应和技术网络中的传感、通信和数据处理相关的计算成本。

本文也引出了学者们未来研究中值得探讨的问题。首先，可以将基于图形理论的方法与机器学习技术相结合，从而实现数据驱动的状态估计。其次，文章的方法可以与系统通信层的协同设计相结合，进一步提高抵御攻击和故障的能力。再者，在考虑建模不确定性、测量噪声及舍入误差的情况下，文章方法还可以检验大规模系统中功能观测器的估计精度、收敛速度和稳定性。最后，文章的方法也可以扩展到更广义的非线性系统。



网络科学集智课堂第三期：

从数学建模到多学科应用


从现实社会的关系网到虚拟的互联网，从线下到线上，我们的生活始终没有脱离复杂网络。真实的复杂网络从其诞生开始就不断地演化着。网络节点不断地增加，节点之间的连接不断地增长。然而，复杂网络的形成机制是什么？具有什么样的演化规律？它们的演化机制对网络的功能和动力学行为有什么影响？为了回答这些问题，科学家们对复杂网络的探索从未停止。

网络科学是一个蓬勃发展的崭新交叉学科，可以看做复杂系统的骨架，核心是研究各种大型复杂网络之间的共性和处理它们的普适方法，其研究对于发展复杂系统的基本理论及构建产生了极大的推动作用。

网络科学的第三个十年，已经过去了几年。从国内外网络科学研究的发展趋势来看，各种各样的更复杂的网络模型和结构以及高阶相互作用动力学引起了人们的极大兴趣。为了回应这种迫切需求， 我们网络科学第三期课程将围绕复杂网络的数学建模与应用进行多角度的介绍。

集智学园特邀陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华加入打造第三期课程，欢迎你的加入。



详情请点击：
从数学建模到多学科应用——网络科学·集智课堂全新升级


推荐阅读



点击“阅读原文”，报名课程