觀測永久丟失下隨機離散事件系統故障預測的驗證算法

摘 要： 針對隨機離散事件系統在故障預測時可能出現系統觀測永久丟失，導致預測不準確的問題，提出一種觀測永久丟失下故障預測驗證的算法。首先對觀測永久丟失的隨機離散事件系統的U-可預測性進行了形式化。其次使用隨機預測器構造了一個隨機離散事件系統的U-預測器，實現了系統的故障預測。基于U-預測器，提出了隨機離散事件系統U-可預測性的充分必要條件及驗證算法，并且引入成對的方式，明顯地改進了該驗證算法的復雜度。仿真結果表明，該驗證算法使得觀測永久丟失下系統故障預測準確。最后，實例說明觀測永久丟失下故障預測驗證算法的應用。結果表明，該驗證算法相比現有同類驗證算法應用范圍更廣，驗證結果更精確。

關鍵詞： 離散事件系統； 故障預測； 隨機自動機； 觀測丟失

中圖分類號： TP301"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-019-0106-07

doi：10.19734/j.issn.1001-3695.2021.06.0247

Verification algorithm for fault prediction of stochastic discrete-event

systems under permanent loss of observations

Liao Hui， Liu Fuchun

（School of Computers， Guangdong University of Technology， Guangzhou 510006， China）

Abstract： Aiming at the problem of permanent loss of system observations during the fault prediction of stochastic discrete-event systems（SDESs），resulting in inaccurate predictions，this paper proposed an algorithm for verification of fault prediction under permanent loss of observations.Firstly，it formalized the notion of U-predictability of SDESs under permanent loss of observations.Secondly，it constructed a U-predictor from the given system using stochastic predictors to perform fault prediction of SDESs.Based on the U-predictor，it proposed a necessary and sufficient condition and an algorithm for verifying U-predictability of SDESs，and the introduction of a pairwise approach significantly improved the complexity of the verification algorithm.Simulation results show that the verification algorithm made the fault prediction of the system accurate under permanent loss of observations.Finally，an example illustrates the application of fault prediction verification algorithm under permanent loss of observations.Compared with the existing similar algorithm，the verification algorithm has a wider range of applications and the verification results are more accurate.

Key words： discrete-event systems； fault prediction； stochastic automata； loss of observations

0 引言

離散事件系統是一種離散狀態、事件驅動的動態系統，其狀態演變完全取決于在可能不規則的時間間隔上發生的物理事件，已應用于計算機系統、數據庫系統、通信系統和制造系統等領域［1］。相比于離散事件系統故障診斷側重于在故障發生后進行檢測故障，故障預測的目標是在故障發生之前預測未來將發生的故障，以便采取一些保護措施，避免故障對系統造成損失。近年來，離散事件系統故障預測的研究引起了國內外專家學者的廣泛關注。

Genc等人［2］研究了部分可觀測離散事件系統的故障預測問題，詳細闡述了故障事件的可預測性與文獻［3］定義的可診斷性之間關系的結論，并提出了兩個故障可預測性的充分必要條件，其中一個條件是基于診斷器進行在線預測，另一個條件是基于驗證器實行離線驗證。文獻［4］考慮離散事件系統的模式故障預測問題，從單個故障事件擴展到可能導致系統故障的有序重要事件組成的序列模式。Takai［5］研究了一組部分可觀測的離散事件系統的魯棒故障預測，即真實的系統模型事先是未知的，構造了一個預測器，對于所有可能的系統模型，其可以在故障發生前預測任意故障。文獻［6～9］研究了分布式離散事件系統的故障預測問題，檢測信息可能分布在許多物理上分離的站點中，各地站點都有各自的局部預測器，僅能觀測到部分系統行為，分布式故障預測通過所有局部預測器來實現故障預測。

在現實離散事件系統中，系統行為是隨機的，隨機自動機是經典離散事件系統模型的一種更準確的方式，附加了概率結構用來評估每個事件發生的可能性。隨機自動機的故障診斷、安全故障診斷、模式故障診斷、魯棒故障診斷、可檢測性、故障預測和可靠故障預測已被廣泛研究［10～19］。

在實際系統中，不確定性是不可避免的，所以不確定性是離散事件系統分析的一個重要方面。離散事件系統中研究的不確定性主要包含了系統模型不確定性和傳感器故障情況下的不確定性。對于系統模型的不確定性，最初研究了魯棒的監督控制問題［20］。Takai［21］研究了模型不確定性的魯棒故障診斷問題。Takai［5］提出了一個魯棒故障預測方法以處理系統模型不確定性的故障預測問題。對于傳感器故障情況下的不確定性，文獻［22，23］研究了觀測間歇性丟失和觀測永久丟失的離散事件系統魯棒診斷問題。在經典離散事件系統的預測問題中也考慮了觀測丟失造成的影響［24］。

上述文獻都是考慮經典離散事件系統。本文研究隨機離散事件系統（stochastic discrete-event system，SDES）在觀測永久丟失下的故障預測問題。先形式化SDES在觀測永久丟失下的故障可預測性的概念。再通過構造的U-預測器，提出一個SDES的U-可預測性驗證的充分必要條件及驗證算法，并給出一種算法復雜度有所改進的SDES的U-可預測性的驗證方法，使得該驗證算法的復雜度在系統所有可能的可觀測事件集的數量上是多項式的，在系統的狀態和事件的數量上是指數級的。最后，以計算機網絡集群系統為例，說明U-可預測性驗證算法的應用。

本文觀測永久丟失下SDES的故障預測的方法與文獻［5，7，19，24，25］不同。Liu［7］研究分布式經典DES的故障協同預測，對于任意故障串，至少一個站點可以預測故障的發生。Takai［5］討論模型不確定的經典DES的魯棒故障預測，所有可能的系統模型可以預測出任意故障的發生。Xiao等人［24］考慮經典DES觀測丟失下的故障預測問題，通過給系統的每個觀測丟失的事件添加一個不可觀轉移的方法生成一個擴展的自動機，研究擴展自動機的故障預測問題。然而，文獻［5，7，24］都是考慮經典DES，本文系統模型是隨機自動機。Liao等人［19］考慮了分布式SDES的r-可靠協同預測問題，假設隨機離散事件系統有n個局部站點，即使n-r個局部站點失效，至少有n-r+1個站點預測出故障的發生。金衍偉等人［25］研究分布式SDES的模式故障預測問題，模式故障是由多個事件組成的事件串，對于任意模式故障串，至少一個站點可以預測模式故障的發生。但是文獻［5，7，19，25］考慮系統事件的觀測都是未丟失的，本文研究觀測永久丟失下SDES的故障預測，系統真實的可觀測事件集事先是未知的，其屬于一組可能的可觀測事件集，可表述為研究具有一組可能的可觀測事件集的SDES的故障預測問題。文獻［25］基于協同預測器的驗證算法，其協同預測器沒有體現概率特性，系統的可預測性等價于特定可達狀態的存在。而本文的U-預測器是由隨機預測器構造而成，隨機預測器具有概率的屬性，所以U-預測器也附加了概率結構，系統的可預測性驗證取決于特定環的存在。

6 結束語

本文研究了隨機離散事件系統在觀測永久丟失下的故障預測問題。對觀測永久丟失的隨機離散事件系統的可預測性進行形式化。通過構造U-預測器，提出在觀測永久丟失下隨機離散事件系統U-可預測性驗證的充分必要條件及驗證算法，使用成對的驗證方法改進了U-可預測性驗證算法的復雜度，將該驗證算法應用于計算機網絡集群系統，相比文獻［25］的驗證算法，本文驗證算法應用范圍更廣，驗證結果更精確。在此研究的基礎上，可以進一步考慮隨機離散事件系統對觀測永久丟失的模式故障預測和模糊離散事件系統［26～28］ 對觀測永久丟失的故障預測等問題，在后續的研究中將探討這些問題。

參考文獻：

［1］Cassandras C G，Lafortune S.Introduction to discrete event systems［M］.2nd ed.New York：Springer，2008：35-48.

［2］Genc S，Lafortune S.Predictability of event occurrences in partially-observed discrete-event systems［J］.Automatica，2009，45（2）：301-311.

［3］Sampath M，Sengupta R，Lafortune S，et al.Diagnosability of discrete-event systems［J］.IEEE Trans on Automatic Control，1995，40（9）：1555-1575.

［4］Jéron T，Marchand H，Genc S，et al.Predictability of sequence patterns in discrete event systems［J］.IFAC Proceedings Volumes，2008，41（2）：537-543.

［5］Takai S.Robust prognosability for a set of partially observed discrete event systems［J］.Automatica，2015，51（1）：123-130.

［6］Kumar R，Takai S.Decentralized prognosis of failures in discrete event systems［J］.IEEE Trans on Automatic Control，2010，55（1）：48-59.

［7］Liu Fuchun.Predictability of failure event occurrences in decentralized discrete-event systems and polynomial-time verification［J］.IEEE Trans on Automation Science and Engineering，2019，16（1）：498-504.

［8］Yin Xiang，Li Zhaojian.Decentralized fault prognosis of discrete-event systems using state-estimate-based protocols［J］.IEEE Trans on Cybernetics，2019，49（4）：1302-1313.

［9］Takai S，Kumar R.Distributed failure prognosis of discrete event systems with bounded-delay communications［J］.IEEE Trans on Automatic Control，2012，57（5）：1259-1265.

［10］Thorsley D，Teneketzis D.Diagnosability of stochastic discrete event systems［J］.IEEE Trans on Automatic Control，2005，50（4）：476-492.

［11］Liu Fuchun，Qiu Daowen，Xing Hongyan，et al.Decentralized diagnosis of stochastic discrete event systems［J］.IEEE Trans on Automatic Control，2008，53（2）：535-546.

［12］Athanasopoulou E，Li Lingxi，Hadjicostis C N.Maximum likelihood failure diagnosis in finite state machines under unreliable observations［J］.IEEE Trans on Automatic Control，2010，55（3）：579-593.

［13］Liu Fuchun，Qiu Daowen.Safe diagnosability of stochastic discrete event systems［J］.IEEE Trans on Automatic Control，2008，53（5）：1291-1296.

［14］Geng Xuena，Ouyang Dantong，Jiang Zhengang.Pattern diagnosis for stochastic discrete event systems［J］.Engineering Applications of Artificial Intelligence，2020，87：103305.

［15］Yin Xiang，Chen Jun，Li Zhaojian，et al.Robust fault diagnosis of stochastic discrete event systems［J］.IEEE Trans on Automatic Control，2019，64（10）：4237-4244.

［16］Yin Xiang.Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures［J］.Automatica，2017，80：127-134.

［17］Keroglou C，Hadjicostis C N.Detectability in stochastic discrete event systems［J］.System amp; Control Letter，2015，84：21-26.

［18］Chen Jun，Kumar R.Stochastic failure prognosability of discrete event systems［J］.IEEE Trans on Automatic Control，2015，60（6）：1570-1581.

［19］Liao Hui，Liu Fuchun，Zhao Rui.Reliable co-prognosability of decentralized stochastic discrete-event systems and a polynomial-time verification［J/OL］.IEEE Trans on Cybernetics.（2021-02-10）.https：//doi.org/10.1109/TCYB.2021.3051260.

［20］Takai S.Robust supervisory control of a class of timed discrete event systems under partial observation［J］.System amp; Control Letters，2000，39（4）：267-273.

［21］Takai S.Verification of robust diagnosability for partially observed discrete event systems［J］.Automatica，2012，48（8）：1913-1919.

［22］Carvalho L K，Basilio J C，Moreira M V.Robust diagnosis of discrete event systems against intermittent loss of observations［J］.Automatica，2012，48（9）：2068-2078.

［23］Carvalho L K，Moreira M V，Basilio J C，et al.Robust diagnosis of discrete-event systems against permanent loss of observations［J］.Automatica，2013，49（1）：223-231.

［24］Xiao Cuntao，Liu Fuchun.Robust fault prognosis of discrete event systems against loss of observations［J/OL］.IEEE Trans on Automation Science and Engineering.（2021-01-18）.https：//doi.org/10.1109/TASE.2021.3049400.

［25］金衍偉，劉富春，趙銳，等.分布式隨機離散事件系統的模式故障預測［J/OL］.控制理論與應用. （2021-05-27）.http：//kns.cnki.net/kcms/ detail/44.1240.TP.20210525.1715.038.html. （Jin Yanwei，Liu Fuchun，Zhao Rui，et al.Coprognosability of pattern fault for decentralized stochastic discrete event systems［J/OL］.Control Theory amp; Applications.（2021-05-27）.http：//kns.cnki.net/kcms/detail/44.1240.TP.20210525.1715.038.html.）

［26］Liu Fuchun，Qiu Daowen.Diagnosability of fuzzy discrete-event systems：a fuzzy approach［J］.IEEE Trans on Fuzzy Systems，2009，17（2）：372-384.

［27］劉富春，嚴飛，趙銳，等.模糊離散事件系統基于驗證器的模式故障診斷［J］.控制與決策，2020，35（6）：1403-1408. （Liu Fuchun，Yan Fei，Zhao Rui，et al.Verifier-based pattern diagnosis of fuzzy discrete-event system［J］.Control and Decision，2020，35（6）：1403-1408.）

［28］謝仁可，劉富春，趙銳，等.分布式模糊離散事件系統的故障預測［J］.控制理論與應用，2020，37（8）：1808-1814. （Xie Renke，Liu Fuchun，Zhao Rui，et al.Fault prognosis of decentralized fuzzy discrete-event systems［J］.Control Theory amp; Applications，2020，37（8）：1808-1814.）