基于有限状态机的空间信息网络故障自检测算法

蒋　媛，李　宁，王发鹏，王　聪

(解放军理工大学 通信工程学院， 江苏 南京 210007)



基于有限状态机的空间信息网络故障自检测算法

蒋媛，李宁，王发鹏，王聪

(解放军理工大学 通信工程学院， 江苏 南京 210007)

讨论了空间信息网(SIN)未来发展趋势并提出了一种新的故障自检测方法。目前关于空间信息网络的研究十分有限，尤其是故障检测方面。针对空间信息网络发展趋势介绍了一种新的空间信息网络体系结构并对该体系结构特点进行了详细的分析，在此基础上提出了一种基于有限状态机的故障自检测算法。该算法通过创建一个故障探测器使得各卫星节点之间可以通过信息交互完成故障检测任务。通过故障检测器，各状态之间有条件的转移最终得到检测结果。每个卫星节点都参与检测器的状态转移过程达到自检测的目的。利用MATLAB仿真工具对算法进行仿真，结果显示所提算法具有较好的性能。

自检测；空间信息网络；有限状态机；故障检测

0　引　言

空间信息网络[1-2]极大地扩大了观测范围，通过卫星和深空平台实现了不间断的信息获取[3]。与目前单个卫星观测相比，空间信息网络具有更好的信息探测和传输能力。一般来讲，空间信息网络是一个复杂的异构网络，它以卫星网络为骨干网囊括了卫星、飞行器、地面站以及各种具有空间通信能力的接入终端[4]。空间信息网仍然是一个比较新的概念，关于它的研究不多，尤其是故障诊断方面。与无线传感器网络不同的是，空间信息网因其具有较大的覆盖范围、灵活的组网方式、不受环境限制等特点[5]，其故障检测更为困难。文献[6]提出了一种新的基于包分组丢失的路由策略。路由维护策略通过交替发送高和低优先级的数据包区分丢包的原因。路由维护机制根据不同的原因来设计相应的方法。文献[7]在空间信息网络环境下提出了一种分布式的基于簇和容错拓扑控制算法来构造一个更有效率和耐故障的拓扑。文献[8]提出了一种基于簇的算法，该算法介绍了一种基于层次分析法(Analytic Hierarchy Process AHP)的决策模型来选择簇头,然后形成重叠的k跳的簇。动态的自我维护机制以节点的移动性和集群均衡为考量。除了簇的合并/分区处理, 关系管理和信息周期的自适应调整使用移动代理以招聘的方式迁移和复制簇头节点的功能。

然而，随着空间信息网络的发展，网络拓扑结构变得越来越复杂。2013年美国国家航空航天局NASA建立小型航天器技术项目[9](Small Spacecraft Technology Program SSTP)研究越过低轨卫星使用小型飞船完成任务。因此，除了已有的卫星以外未来将有更多的小型卫星加入到空间信息网络的系统中。而随着这些小型卫星的加入，现有的故障诊断算法已无法满足服务需求。鉴于这个情况本文介绍了一种新的空间信息网的系统模型，并对该系统进行了具体的分析。在此基础上，还提出了一种改进的适用于新模型下的故障检测算法[10-11]。小型卫星一般在完成既定任务后即坠毁，在轨时间很短。因此对于网络链路故障诊断算法而言极易造成错误的判断。本文提出的算法中首先对所检测的卫星节点进行在轨时间与设计运行时间的比较判断。如果在轨时间已经超出设计的周期时间则认为所探测的卫星节点已不存在不判错，反之则进入主算法。对于在运行周期内的卫星节点，我们设计故障探测器(fault detector)发动所有相关节点一起加入到检测过程中。故障探测器可以将故障检测过程转化为状态的转移。每个卫星节点根据本地信息更新探测器的状态并传递探测器的类型和新的状态到下一个节点直至到达一个稳定的状态。这里所谓的稳定状态即为最终状态，我们可以从最终状态判断出故障检测结果。利用仿真工具MATLAB 2010对所提算法进行仿真，从仿真结果来看，本文所提算法具有较好的性能。

1　系统模型

图1所示为空间信息网网络结构图。从图可以明显看出，空间信息网是一个分层的结构[12-13]，可以大致分为骨干网域、接入网域和用户网域。其中骨干网域由高、中、低轨卫星组成是空间信息网络系统的核心。骨干网域负责信息的采集、传输和简单的信息处理。接入网域由小型航天器和飞行器组成，负责不同接入终端和业务流的接入。用户网域由具有空间通信能力的用户终端组成。与之前所提的空间信息网络结构模型不同，该网络模型最大的特点是加入了小型航天器。而随着小型航天器的加入，空间信息网络变得更为复杂多变，在原有的基础上又有了新的特点。

图1　空间信息网网络结构

1.1小型航天器

NASA在2014年的一份题为“Small Spacecraft Technology State of the Art”的报告中对小型航天器技术领域目前的研究进展和发展前景进行了总结。从报告可以看出，未来小型航天器将成为研究热点，而目前所得的成果也表示小型航天器在未来空间通信中将发挥重要作用。多数小型航天器的任务是搜集科学的数据并传输给地面研究人员。因此小型航天器的加入使得空间信息网络的服务质量得到很大的提升。

1.2网络特征

1.2.1复杂性

空间信息网[14]包括了从深空到地面的所有通信设备。其中不仅包含了这些通信设备还包括了它们所组成的通信系统，更不用说这些设备中还包括了所有的卫星，因此空间信息网的复杂性也是前所未有的。这些通信实体互相协作组成了一个有效的大规模的网络系统。因为这些原因，与任何以往的网络系统不同，空间信息网的复杂性可想而知。正是因为如此，空间信息网的故障诊断也比其他任何网络系统更为复杂和困难。

1.2.2动态性

众所周知，由于卫星和飞行器的存在空间信息网的网络拓扑结构变化剧烈。节点位置随着时间推移而移动，更有甚者，每个节点都按照自己的轨迹运行，轨迹之间还存在重叠部分。节点的移动性增加了网络系统的动态性，这样一个动态的拓扑结构又大大增加了空间信息网链路故障诊断的研究困难。卫星之间的链接也会随着卫星位置移动消失或者重新出现。更糟糕的是，随着小型航天器的加入，由于其工作周期较短，完成既定任务后即坠毁，导致网络拓扑变化更为频繁。针对这个特点，需要对故障检测算法进行调整以适用于新的网络环境。

1.2.3分层结构

从图1可以很清楚地知道这是一个分层结构。不同层次的节点具有不同的功能和性质，不同的服务请求分配到不同的节点。因此空间信息网可以分成若干任务域，每个任务域之间可能遵循不同的网络协议，任务域之间通过卫星节点进行通信。长通信距离，长时延和任意约定的网络结构使得空间信息网的进展缓慢。未来小型飞行器的研究将成为趋势。可想而知，空间信息网络将愈加复杂多变。但是无论空间信息网络变得多么复杂，有一点我们可以肯定的是它的分层结构基本不会改变。

2　故障自检测算法

图2所示为整个算法的流程图。正如前面所提到的，本文所提算法主要关注于小型航天器短工作周期的问题上。假定节点A探测到它与B节点间的链路A-->B包重发率异常高。首先，需对B节点做出一个判断，判断它是否在其工作周期内。若它的实际工作时长已经超出设计周期则认为该节点已完成既定任务消失，不判错返回“no error”，更新网络拓扑。若B节点在其工作周期内则进入故障检测算法。

图2　故障自检测算法流程

图3为部分网络拓扑图，A向B发包，{Ci}表示可以与A和B通信的邻居。当A探测到它与B之间的链路A-->B 的包重发率异常高，所以A创建一个探测器M，M= (E,S,S0,f,F)。其中E表示输入信息，S表示所有状态集，S0是初始状态Start，f表示状态转移条件函数，F是所有可接受状态集，即最终的Accept状态集。图4中所示，Si为状态集S中的参数，每条弧线代表从一个状态转移到另一个可能的状态，弧线上的注释代表两个状态之间转移的条件。注意，其中有些状态如S3，S4等有自循环的条件。环形所示的状态代表Accept状态，从Accept状态我们可以得到故障检测的最终结果。

图3　部分网络拓扑图

图4　状态转移图

以图4中所示为例，A创建一个探测器处于初始状态Start。在A创建的这个探测器中，Start状态表示A发现它到B的链路存在故障。于是A向它的邻居节点广播目前的状态和探测器的类型。两种类型的节点可能收到A发出的信息，一种是B节点另一种是可以与它们通信的邻居节点{Ci}。

根据B节点和邻居节点{Ci}的本地信息可以进行状态间有条件地转移。如果B收到来自A的Start状态，B根据本地信息检查之前是否有收到来自A的相同的信息。由于记录所有重复信息较为浪费资源，因此文中算法以B是否能够收到来自A的信息作为检测标准。如果B收到来自A的信息并返回一个反馈给A但是仍然收到来自A的相同的信息，意味着A能够向B发包但是无法接收来自B的包。反之则表示B无法接收来自A的数据包。在图4中分别用B-/->A和A-/->B来表示这两种情况。根据B的信息Start状态可以转移到S1状态或S2状态。以文中图4图中虚线转移线为例，B无法接收来自A的数据包所以B转移到S2状态。S2状态根据邻居节点{Ci}的信息进行状态转移。如果Ci能够与B正常通信，表明是A-->B间的链路发生故障导致A与B间丢包率异常高。因此根据{Ci}的信息可以转移到一个可接受状态LA->B，这个状态即表示A到B的链路发生故障。若Ci也无法与B正常通信，S2状态转移到S7状态。S7状态为一个具有自循环的状态，当Ci-/->B时将不断检测直至检测到一个Ci能够与B通信，即存在Ci满足Ci-->B则转移到可接受状态LA->B。若所有Ci都无法与B通信，则NUM转移到BC状态。BC状态表示B节点很可能拥塞。这里我们设置一个状态自循环的门限值，而由于门限值的存在算法可能存在误差，但是若检测所有邻居节点{Ci}极大地增加了算法运行时间和复杂度。因此，如何正确地选取门限值和正确率的折衷也是我们要考虑的问题。

3　仿真结果及分析

在MATLAB2010环境下对本文提出的算法进行仿真。前面我们提到的，我们将对每个检测节点先进行工作周期的判断，因此每个节点结构设置为6个参数，即X= {LA,LB,T,t,RA,RB}。其中LA存储该节点与A节点当前的链接关系，类似的LB存储该节点与B节点当前的链接关系。T表示该节点设计周期，t表示该节点在轨时间。RA,RB分别表示该节点与A、B节点的拓扑关系。因此，可以开始仿真本文提出的算法。当t>T时，表示探测节点在轨时间已经超出设计时间，不判错返回“no error”。反之则进入主算法。通过节点中LA,LB的信息可以获得节点间链接关系即算法中的转移条件，RA,RB可以获得寻找{Ci}的信息。对算法进行仿真比较可以得出如下结果。

表1所示为进行门限选取仿真[15]时所需数据。首先需要知道门限的选取对正判率的结果是否会产生影响。这里的门限是指上文中提到的具有自循环的状态在相应的转移条件下需进行的自检次数，即需要寻找多少个Ci才能合理地在正判率和算法复杂度之间寻求折衷。门限中包含越多Ci的可能状态时，算法的正确率越高。每个门限在同意故障下运行故障检测算法1 000次，所得结果如图5所示。从图可知，在355个节点的网络规模下算法总体正判率较高达到90%以上，门限值越大正确率越高。当门限值为5时，正判率高达99%以上。当门限值为7时，算法正判率接近100%。

表1　门限选取仿真参数

图5　正判率与门限

表2为网络规模仿真数据。为了维持正确率和计算量的平衡，门限值设为5。图6为仿真结果，可以明显看出当网络规模增加时正确率下降。节点数小于600时，正确率在95%以上，但是当网络规模达到700个节点时降为81.2%。甚至当网络规模达到1 000个节点时，正确率降到了73.6%。

表2　网络规模仿真参数

图6　正判率与网络规模

图7所示为不同网络规模和门限值情况下正确率的曲线图。由图可知，正确率随着网络规模的增加而降低，随着门限值的增加而增高。当网络规模到达1 000个节点时，若门限值仍设为5正确率低于75%，而通过增加门限值的方法可以提高正确率。如图，当门限值设为7时，正确率可以增加到80%以上。但是，同时增加了相应的计算量。如何自适应选取合适的门限值将是下一步需要解决的问题。

图7　正判率与影响因子

4　结　语

本文介绍了一种新的空间信息网络模型并对其进行了详尽的分析。其次在该模型下提出了一种基于有限状态机的故障自检测算法。通过创建一个故障探测器使得各卫星节点之间可以通过信息交互完成故障检测任务。从仿真结果来看，本文提出的算法在空间信息网络环境下具有较好的性能。然而算法中门限值为固定值，在不同网络规模下性能差异较大。因此，下一步可以针对如何根据网络规模的变化自适应地设置门限值进行研究。

[1]DAI Kun and ZHU Chang-ming. A New Architecture Design of Space Information Networks[C].2012 Sixth International Conference on Internet Computing for Science and Engineering, Henan: IEEE, 2012:217-220.

[2]WAGN K, ZHAO Z W and YAO L. An Agile Reconfigurable Key Distribution Scheme in Space Information Network[C].2007 Second IEEE Conference on Industrial Electronics and Applications, Harbin: IEEE,2007:2742-2747.

[3]JIANG Chun-xiao, WANG Xue-xia, WANG Jian, et al. Security in Space Information Networks[P].Communications Magazine, IEEE,2015, 53(8): 82-88.

[4]REN Fang, FAN Jiu-lun. An Adaptive Distributed Certificate Management Scheme for Space Information Network[P].Information Security,IET,2013,7(4):318-326.

[5]万鹏,王瑞军,黄薇等.空间信息传输TCP扩展协议研究与性能分析[J].飞行器测控学报, 2010，29(03):11-16.

WAN Peng, WANG Rui-jun, HUANG Wei, et al. Analysis of the Performance of TCP and Its Extension Protocol for Space Communication[J].Journal of Spacecraft TT&C Technology,2010,29(03):11-16.

[6]LIU Jun, HAN Huan, GENG Rong, et al. Route Maintenance Strategy based on the Packet Lost Distinguish for Space Information Networks[C].2012 International Conference on Computer Science and Service System, Nanjing: IEEE, 2012:1063-1065.

[7]YE Ning, ZHU Zhi-liang, LIU Jun, et al. Distributed Cluster-based Fault-Tolerant Topology Control for Space Information Networks[C].2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Huangshan: IEEE, 2010: 210-217.

[8]YE Ning, ZHU Zhi-liang, LIU Jun, et al. A Self-Maintenance Clustering Algorithm based on Decision Model for Space Information Networks[C].Proceedings of ICCTA 2009, Beijing:IEEE,2009:816-820.

[9]http://www.nasa.gov/sites/default/files/files/Small_Spacecraft_Technology_State_of_the_Art_2 014.pdf.

[10]LIU Ke-bin, MA Qiang, ZHAO Xi-bin, et al. Self-Diagnosis for Large-Scale Wireless Sensor Networks[C].IEEE INFOCOM 2011, Shanghai: IEEE, 2011:1539-1547.

[11]LIU Ke-bin, MA Qiang, GONG Wei, et al. Self-Diagnosis for Detecting System Failures in Large-Scale Wireless Sensor Networks[J].IEEE Transactions on Wireless Communications, 2014:13(10): 5535 -5545.

[12]Durresi A, Dash D, Anderson B L,et al. Routing of Real-Time Traffic in a Transformational Communications Architecture[C].2004 IEEE Aerospace Conference Proceedings 2004:2:1086-1104.

[13]Kimura K, Inagaki K, Double Layered Inclined Orbit Constellation for Advanced Satellite Communications Network[J]. IEICE Transaction on Communication, 1997:8(1):93-102.

[14]Fraire J A and Finochietto J M. Design Challenges in Contact Plans for Disruption-Tolerant Satellite Networks[J]. IEEE Communications Magazine, 2015:53(5):163-169.

[15]马淑丽,赵建平. WSN中基于最佳指数的加权DV-Hop算法[J]. 通信技术, 2015, 48(10):1147-1151.

MA Shu-li, ZHAO Jian-ping. Weighted DV-Hop Algorithm based on Optimal Index in WSN [J]. Communications Technology, 2015，48(10): 1147-1151.

蒋媛(1991—)，女，硕士研究生，主要研究方向为空间信息网络，故障诊断算法，压缩感知；

李宁(1967—)，男，副教授，硕士生导师，主要研究方向为ad hoc网络技术，移动通信；

王发鹏(1991—)，男，硕士研究生，主要研究方向为ad hoc网络技术，车联网，压缩感知；

王聪(1975—)，男，博士，副教授，硕士生导师，主要研究方向为计算机网络。

SIN Fault Self-Diagnosis Algorithm based on Finite-State Machine

JIANG Yuan, LI Ning, WANG Fa-peng, WANG Cong

(Institute of Communication Engineering,PLA University of Science and Technology,Nanjing Jiangsu 210003,China)

Future development trend of SIN (Space Information Network) is discussed, and a novel fault self-diagnosis method proposed.Nowadays limited research is focused on SIN,particularly in the field of fault diagnosis.In connection with the development tendency of SIN, a novel SIN architecture is introduced,and its characteristics also analyzed in detail. In light of this, a fault self-diagnosis algorithm based on finite-state machine is proposed. This algorithm,with a newly-designed fault detector,enables various satellites nodes to complete fault detection via information interaction. Through fault detectors, conditional transfer of between the states is done,and the detection result finally acquired. Each satellite would participate in state transition process of the detectors and complete the self-diagnosis. MATLAB simulation indicates that the mentioned algorithm enjoys fairly good performance.

self-diagnosis; SIN; finite-state machine; fault diagnosis

10.3969/j.issn.1002-0802.2016.03.016

2015-11-01；

2016-02-04Received date:2015-11-01；Revised date：2016-02-04

TP393

A

1002-0802(2016)03-0335-05