故障診断システム

01kc053 栗田武
指導教員坂本直志

1. はじめに

　現在多くのディジタルシステム(digital system)が稼動をしている。これらのディジタルシステムは大小さまざまであり、全世界に広がる地球規模のものから個人が携帯できるとても小さな規模のものまで存在する。さらに最近ではLAN(Local Area Network)やWAN(Wide Area Network)、インターネット(Internet)などのコンピュータネットワークの研究開発が著しく進み、有線無線を問わずディジタルシステム同士を結ぶことが可能になった。それによって、さらに大きな規模のディジタルシステムを構築することが可能になった。しかし、それはディジタルシステムが複雑化することを意味している。また、欠陥や故障(fail)がないディジタルシステムを構築することはほとんど不可能である。複雑化したディジタルシステムにおける検査(test)は極めて困難である。大きな規模のディジタルシステムの検査パターンを作り出す複雑さは計り知れない。故障が発生すると、どこで故障が発生したのかを検出すること（故障検知）には高度なアルゴリズムを必要とする。
　本研究では、故障検知のしくみとしてユニット自身が故障を検知するような「自己故障診断モデル」と、複数のユニットからなるシステムにおいてユニット間のネットワークで故障を検出するPMCモデル[1]を対象とした。

　本論文では、2章で自己故障診断モデルについて述べる。3章で古典的な故障診断モデルPMCモデルについて述べる。4章では様々な故障診断へのアプローチについて述べる。そして5章では本論文のまとめを示す。

2. 自己故障診断モデル(検査ユニット＝被検査ユニット)

　この章では、コンピュータシステムを構築するユニット自身が"自分は故障しているかどうか"という自己故障診断ができるモデルを考える。これは人間にたとえると、具合が悪いとき自分に異常があると自分で判断できることである。しかし、これは実現することはできなかった。そこで実現化する際の問題点、課題を示していく。

　コンピュータシステムを故障診断を行う形式は以下のように大きく2つに分けることができる。

各ユニットが協調して故障診断を行う(検査ユニット≠被検査ユニット)
ユニット自身が故障診断を行う(検査ユニット＝被検査ユニット)

各ユニットが協調して故障診断を行うモデル

　1つ目の各ユニットが協調して故障診断を行うモデルを図1に示す。

図1．各ユニットが協調して故障診断を行うモデル

　このモデルは、検査ユニットと被検査ユニットが同じではない。システム中のユニットが互いに検査をして、最終的に多数決でどのユニットが故障しているのかという判断を行う。この協調して故障診断を行う方法は以前より研究されており、最も古典的な故障診断モデルは、Preparata,Metze,Chienが提案したPMCモデル[1]である。このモデルはグラフ理論を用いて表されており、コンピュータシステムの故障診断を数学的に解析することが可能になった。これにより、多くの研究が行われた。この解説は3章で行う。

ユニット自身が故障診断を行うモデル

　2つ目のユニット自身が故障診断を行うモデルを図2に示す。

図2．ユニット自身が故障診断を行うモデル

　このモデルは、検査ユニットと被検査ユニットが同じである。システム中のユニットが独立して存在し、自分自身を検査し、故障しているかを診断する。ユニットが正常であれば、自身が正常であると判定することができる。これはウィルス検知システムやハードディスク検査プログラムなどで実際にしばしば使われている。しかし、一般にユニットが故障していた場合、正確な診断を行うとは限らない。
　そこで、理論的に自己故障診断がどのようなものであるかを考えるため、次のような問題を考えた。

問題1 次の条件を満たすプログラムは存在するか

プログラム中の任意の1文字が変わった時

エラーが発生する
又は、Fを表示する

改善がない時、Tを表示する

　上記のプログラムを作成する前に、以下の図のようなモデルを考えた。

図3．ユニットが1つの正常信号と2つの故障信号を持った故障診断モデル

　このモデルは、正常であるならばTを出力し、故障しているならばFを出力する故障診断モデルである。そして、Fを出力する箇所が2つある。この1つのTと2つのFの検査信号いずれかの出力で故障診断を行う。
　ここで、ユニットが正常である場合はTを出力するだけなので、ユニットが故障している場合のみを考える。
　ユニットが故障している場合、一般にTもしくはFと出力されても信頼できない。しかし、Fが2つ存在していることによって、1つは正常でない場合の出力、もう1つはTもしくはFと出力される部分が改変された場合の出力を表すことができる。これにより、もし故障が発生し、検査を行う部分が正常に機能しなくなったとしても、その正常に機能しなくなったことを検知し、Fを出力することができる。したがって、正確な故障診断が可能になる。
　私はこのモデルをプログラミング言語Perlを用いて作成した。ここでは故障をプログラム中の1文字が改変されることとした。1文字が変化してもTや他の文字を出力をしないことや無限ループの処理にならないことが目標である。作成したプログラムは1文字変化してもFは表示された。しかし、実際のシステムにおいての故障はプログラムの1文字の変化であるとは限らない。今回作成したプログラムでは2文字以上の変化するなど、問題を広げると難しいことがわかった。特に、常に正常と表示してしまうくらいの故障を許すと、故障診断ができなくなる。つまり、故障の度合を制限しない限り、自己故障診断は不可能である。

3. PMCモデル

　この章ではPMCモデルの説明を行う。PMCモデルは、1967年にF.P.Preparata、G.Metze、R.T.Chienによって発表された[1]"On the Connection Assignment Problem of Diagnosable Systems"という論文で示された。[1]では以下のように述べている、

システムはnユニットに分割されており、1つのユニットは診断目的に対してさらに分割されることができないシステムの明確に識別できる部分である。

　これら分割されたユニットはまったく同じである必要はない。しかしそれらのユニットはほかのユニットを検査できる能力を持っていなければならない。そして検査ユニットは被検査ユニットを検査する。その検査結果は正常(0)または故障(1)の2値である。さらに検査する方向・配置が決まっていれば、検査結果は2値の重みを持った有向グラフG=(U,E)として表すことができる。このグラフではシステムの各ユニットu_iがノードとなる。u_iがu_jを検査するということはリンクb_ijとして表される。そしてb_ijがこのグラフのエッジ(u_i,u_j)となる。b_ijの重みをa_ijとすると、a_ij={0,1}となり、以下にそれぞれの場合を示す。

a_ij= 0 の場合: もしu_iが正常ならば、u_jは正常である。
a_ij= 1 の場合: もしu_iが正常ならば、u_jは故障である。

　両方の場合においてもu_iが正常でなければならない。もしu_iが故障しているならば、a_ijはu_jの状態に関係なく0と1の値の両方ともとりえる。このようなケースでは、検査結果は信頼できない。これを表と図で示すと次のようになる。

検査ユニット	被検査ユニット
検査ユニット	正常	故障
正常	`0`	`1`
故障	`x`	`x`

表1．PMCモデルにおける検査結果

図4．PMCモデルの検査結果のパターン

また、[1]では以下のように定義をしている。

定義3.1

検査結果a_ijの集合はシステムのシンドローム(syndrome)を示す。

ここで、シンドロームの例を示すため、以下の図を用いて説明を行う。

図5．5ユニットを持つシステム

図のように示されているような、検査リンクb₁₂ ,b₂₃ ,b₃₄ ,b₄₅ ,b₅₁ を持つユニットu₁ ,u₂ ,u₃ ,u₄ ,u₅ から成るシステムを考える。このシステムのシンドロームは、(a₁₂ ,a₂₃ ,a₃₄ ,a₄₅ ,a₅₁) のような5ビットベクトルで表される。a_ijの左から右への並べ方は図の検査リンクによって形作られたループの道順を反映することを意味する。
ここでu₁が故障しているとする。そのとき、

a₂₃ = a₃₄ = a₄₅ = 0
a₅₁ = 1

すなわち、u₅は正確に故障ユニットu₁を識別している。そして、

a₁₂ = x ,すなわち0 もしくは1

よって、u₁は正確にu₂を診断するかどうかわからない。
したがって、5つのユニットが故障していることに関するシンドロームは以下のようにたった1つ、もしくはその循環的並べ替えのシンドロームである。

x 0 0 0 1

上記のようにシステム中に1つの故障ユニットが存在する場合のシンドロームを作成することができた。次に2つの故障ユニットが存在する場合のシンドロームを作成することができるかどうかを考える。この問題は2つの方法として解釈されるあいまいな問題である。すなわち、故障ユニットの総数が2を超えない場合に

瞬時に2つの故障ユニットを探し当てる能力
少なくとも1つの故障ユニットを探し当てる能力

のように意味することができる。これら2つの解釈は、現実に2つの異なる状態を含んでいる。これら2つの状態は[1]で以下のように定義をしている。

定義3.2

故障ユニットの数がtを超えず存在するという条件で、システム中のすべての故障ユニットが識別されることができるならば、そのnユニットのシステムは同時t故障診断可能(one-step t-fault diagnosable)である。

定義3.3

故障ユニットのの数がtを超えず存在するという条件で、少なくとも1つの故障ユニットが識別されることができるならば、そのnユニットのシステムは逐次t故障診断可能(sequentially t-fault diagnosable)である。

このように2つの状態は厳密に定義された。そこでこの2つの状態をそれぞれ説明する。

同時`t`故障診断可能(one-step t-fault diagnosable)

　定義3.2より、同時t故障診断可能であるということは瞬時にt個の故障ユニットを探し当てることができるということである。このことが可能である総ユニット数n、最大故障ユニット数tシステムSを考える。[1]では以下のような定理を述べている。

定理3.4

システムSを同時t故障診断可能であるとする。そのとき、n≥2t+1ならば、同時t故障診断可能であるようなシステムSを形作る接続を提供することは常に可能である。

証明：
（十分条件）Sは最大t個の故障ユニットを持つので、正常ユニットはt+1個以上存在することになる。したがって、システムSが同時t故障診断可能であるならば、n≥2t+1である。
（必要条件）n>2t+1のユニットが任意の接続をしているSの場合を考える。さらにnが偶数か奇数の場合に分けて考える。まず偶数の場合、t₀≤tのとき、n=2t₀とする。このとき、システムSをt₀ユニットごとに分割する。これをP₁とP₂とする。P₁中のすべてのユニットは故障しているとし、P₂中のすべてのユニットは正常であるとする。このような状況では、P₂中のユニット間のすべてのリンクは値0を持ち、P₂中のユニットからP₁中のユニットを指すすべてのリンクは値1を持つ。しかし、P₁中のユニットはすべて故障しているため、どのような値を示すか確かではない。したがって、P₁中のユニット間のすべてのリンクは値0を持ち、P₁中のユニットからP₂中のユニットを指すすべてのリンクが値1を持つ可能性がある。次に奇数の場合、t₀≤tのとき、n=2t₀-1とする。このとき、システムSをt₀ユニットとt₀-1ユニットに分割する。偶数の場合と同様にそれぞれをP₁とP₂とする。ここでまた、偶数の場合と同様にP₁中のユニットはすべて故障しているので、P₂中のユニットを指すすべてのリンクは値1を持つ可能性がある。このような状況になるとP₁は正常ユニットの集合で、P₂は故障ユニットの集合であると、誤った診断をしてしまう可能性がある。したがって、SがP₁とP₂を区別することは常に可能ではない。よって、Sは同時t故障診断可能でない。n>2t+1の場合での矛盾を示せたので、n≥2t+1ならば、同時t故障診断可能である。
Q.E.D.

　定理3.4によって、n≥2t+1を満たすシステムSは瞬時にt個の故障ユニットを探し当てることができることが示された。次に特定の1つのユニットを検査するユニットの数の下限を調べる。[1]では以下のような定理を述べている。

定理3.5

同時t故障診断可能システムS内で、1つのユニットが少なくともt個のほかのユニットから検査される。

証明：
　システムSが同時t故障診断可能であるとき、k<tで、u₁,u₂,…,u_kはあるユニットu₀を検査するS内のすべてのユニットである。k<tなのでu₁,u₂,…,u_kがすべて故障しているケースが考えられる。それらの故障ユニットによって行われた検査結果は信頼性がない。よって、k≥tでなければならない、すなわち1つのユニットは少なくともt個のほかのユニットから検査されなければならない。
Q.E.D.

　次にシステムの設計について[1]では以下のように定義をしている。

定義3.6

システムSがj-i=δmで、mは値が1,2,…,tと仮定しているならば、u_iからu_jまでの検査リンクが存在しているとき、設計D_δtに属しているとする。

　ここで、設計D_δtの例を示す。
ユニット数n=6、最大故障ユニット数t=2、δ=1のとき、1つのユニットは次のユニットへの検査リンクとさらにその次のユニットへの検査リンクを持つことになる、すなわち検査ユニットがユニットu_iならば、被検査ユニットはu_i+1とu_i+2である。この設計されたシステムは以下の図に示す。

図6．6ユニットシステムの設計D₁₂

　さらに、ユニット数、最大故障ユニット数は上記の場合と同様で、δ=2のときを考える。この場合、1つのユニットは2つ先のユニットへの検査リンクとさらに4つ先のユニットへの検査リンクを持つことになる、すなわち検査ユニットがユニットu_iならば、被検査ユニットはu_i+2とu_i+4である。この設計されたシステムは以下の図に示す。

図7．5ユニットシステムの設計D₂₂

逐次`t`故障診断可能(sequentially t-fault diagnosable)

　定義3.3より、逐次t故障診断可能であるということは少なくとも1つの故障ユニットが識別されることができるということである。このような場合を考える理由は、同時t故障診断可能であるならば、n·tのリンクが必要であり、より少ない検査リンクが要求される場合があるためである。したがって、すべての逐次t故障診断可能システムに対して、n≥2t+1である。
　逐次t故障診断可能である場合の検査リンクの数は、[1]によって下記の定理で示される。

定理3.7

検査リンクの数がN=n+2t-2となる設計のクラスが存在するということは、逐次t故障診断可能である。

証明：
　すべてのiについてu_iからu_i+1までのリンクが存在するようなループ中のすべてのユニットu₀,u₁,…,u_n-1を接続する。次に集合{u₁,u₂,u₃…,u_n-2}から2t-2の部分集合S₁を選択し、S₁の各ユニットからu₀までのリンクを構築する。S₁とu_n-1からu₀の検査結果が0の信号の数をn₀、検査結果が1の信号の数をn₁とする。すると、以下のケースが考えられる。
ケース1：n₁>t
u₀が正常であるという仮定はn₁>tユニットが故障していることを意味する。しかし、これは故障最大ユニット数の仮定に反する。よって、u₀は故障している。
ケース2：n₁<t
u₀が故障しているという仮定はn₀>t-1を超えるユニットが故障していることを意味する。しかし、これも故障最大ユニット数の仮定に反する。よって、u₀は正常である。
ケース3：n₁=t
2tユニットの総数について、集合S^*=S₁∪u_n-1∪u₀を考える。
ケース3-1：u₀が故障していない。
u₀を含まない集合はn₁=t個の故障ユニットを含んでいる。
ケース3-2：u₀が故障している。
Sはu₀とn₀=t-1の故障ユニットを含んでいる。
両方のケースでは、集合はt個の故障ユニットを含む。集合S^*の中に含まれないSのすべてのユニットは故障していない、n≤2t+1だから少なくとも1つの正常ユニットを識別されることができるということを決定する。したがって、n₁=tは少なくとも1つの正常ユニットの存在と識別を意味している。
以上のことから、少なくとも1つの故障ユニットを見つけるには以下のようにする。ケース1ではすでに見つかっている。ケース2,3では1つの正常ユニットを見つけているので、矢印方向の中の検査リンクのループに沿って検査する。そのようにすれば、値1が現れた検査のユニットは故障していることがわかる。
この設計クラスに関してN=n+2t-2であることは、上記で述べたようにループ接続のリンク数はn、S₁の各ユニットからu₀までのリンク数は2t-2であり、両方の和である。
例：以下の図において、t=2,n=5について定理3.7に従って設計された逐次診断接続を示す。

図8．n=5,t=2の逐次診断接続の例

4. 様々な故障診断へのアプローチ

　前章で故障診断モデルのPMCモデルについて解説した。本章ではそれを踏まえ、現在までに行われてきた故障診断の様々なアプローチを解説する。

同時t故障診断(one-step t-fault diagnosable)

　[1]では同時t故障診断の必要条件を示した。そして、Hakimi and Amin[2]は同時t故障診断であるための必要十分条件を以下のように示した。

定理4.1

G(V,E)をn個のユニットのシステムとする。そのときSが同時t-故障診断可能である必要十分条件は以下の3つの条件を満足することである。

n≥2t+1

すべてのv∈Vに対して、d_in(v)∈t

0≤p<tの各々の整数p、そして|X|=n-2t+pの各々のX⊂Vに対して|ΓX|>p

ここでd_in(v)は、vに入る有向辺の数を示す。また、ΓXは、
ΓX=∪_v∈XΓv-X, Γv={v_i|(v,v_i)∈E} (X⊂V)
を意味する。

　また、香田[3]は上記とは異なった形で同時t-故障診断可能である必要十分条件を与え、故障ユニット数が丁度t個であるシンドロームに対してすべての故障ユニットを検出できるシステムを定義した。このシステムを丁度同時t-故障診断可能システム(exactly one-step t-fault diagnosable)とし、同時t-故障診断可能は丁度同時t-故障診断可能システムであることを示した。

逐次t故障診断(sequentially t-fault diagnosable)

　[1]では、必要条件として総ユニット数nが2t+1以上であることを示した。また、Russell and Kime[4]は逐次t故障診断の十分条件を与えたが、この十分条件はnが約t²/2以上のシステムについてしか適用できない。そして、香田[5]は条件付診断可能指数を用いて逐次t故障診断の十分条件を示した。さらに、Xu and Huang[6]は以下のように逐次t故障診断の定義と十分条件を示した。

定義4.2

t個故障によって形成された任意の与えられたシンドロームωについて、|∩_{F∈Ω_ω,t}|≥1もしくは、Ω_ω,t={ø}のとき、かつそのときに限り、システムSは逐次t故障診断である。

定理4.3

任意の空でない部分集合F⊂Vについて、そしてそれぞれのFのカバーπ[|F_i|≤t(i=1,2,…,r)でπ={F₁,F₂,…,F_r}]について、下記の条件の少なくとも1つが成り立つ、すなわち、

∩_1≤i≤rF_i≠ø

u∈V-Fとu∈Fのような1つの検査(u,v)が存在する

f(v)⊄f(u)とf(u)∪f(v)≠πのような(u,v)が存在する

このとき、かつこのときに限り、1つのシステムSは逐次t故障診断可能である。

間欠故障(intermittent fault)

　PMCモデルでの故障は時間的に状態の変化のない永久故障(permanent fault)である。間欠故障(intermittent fault)は故障状態が時間的に変化することや、検査が不完全な場合などを考慮した概念である。間欠故障ユニットが正常ユニットから検査される場合、その検査結果は検査のたびに変化する。さらに間欠故障ユニットが複数の正常ユニットがら検査されている場合、それらの検査結果は必ずしも一致しない。仮にシステム内の故障ユニットが正常と判定されたとすると、その診断は不完全(incomplete)である。また、正常ユニットを1つでも故障と判定すれば、その診断は不正確(incorrect)である。間欠故障の存在は診断を不完全なものにする可能性を意味している。
　不完全であっても不正確ではない（故障ユニットが正常と判定されることは許すが、正常ユニットを1つでも故障と判定することは許さない）診断特性を確保するため、間欠故障を含む故障診断(hybrid fault diagnosis)に対する診断可能性(diagnosability)が定義されている。それらの中で一般的なものは、t/r/τ-診断可能性(t/r/τ-diagnosability)と呼ばれている。ここでtはシステム内における永久故障ユニットと間欠故障ユニットとの和の最大値、rは間欠故障ユニット数の最大値(t≥r)を表している。τはシンドロームの空間(syndorome space)の大きさを表現し、故障ユニットの診断の際に有効である。

t/s-診断可能(t/s-diagnosable)

　[7]では、最大t個故障ユニットの集合が最大s個のユニットの集合内で識別されることができるならば、t/s-診断可能であるという。この診断は一部のユニットに不正確な診断されることを認める診断である。

t/k-診断(t/k-diagnosis)

　[8]では、最大kユニットは不正確に診断されると同時に、システム内のすべての故障ユニットtは識別されることを保証するならば、t/k-診断である。

適応型診断(Adaptive diagnosis)

　Nakajima[9]によって発表された。中央の検査ユニットが全ユニットの中から検査の順序を選ぶ。目標は一つの正常ユニットを識別することである。検査ユニットは前回の検査結果を基に次の検査を決定する。

分散診断(Distributed diagnosis)

　中央の検査ユニットはなく、検査を実行するユニットらによって診断を実現する。アルゴリズムは多くのまたはすべてのユニットにおいて同時に実行される。また、分散診断アルゴリズムの複雑性は検査や通信の相互接続に依存している。

5. おわりに

　本論文は、2章で故障ユニットが自分自身が故障しているかを診断することができるモデルについて述べた。3章で古典的な故障診断モデルPMCモデルについて述べた。4章では様々な故障診断へのアプローチについて述べた。

　本研究では、自己故障診断の可能性について検討し、次にシステムレベル診断について従来の研究結果をまとめた。
　故障診断はフォールトトレラントの一分野である。フォールトトレラントについてさらに詳しい説明はBarborak, Malek and Dahbura[10]によって行われている。現在、まだ研究の行われている分野であり、今後より深く検討していきたいと考えている。

参考文献

[1] F.P.Preparata, G.Metze, and R.T.Chien, "On the Connection Assignment Problem of Diagnosable Systems," IEEE Trans. Electronic Computers, vol.16, no.6, pp.848-854, Dec. 1967
[2] S.L.Hakimi and A.T.Amin, "Characterization of Connection Assignment of Diagnosable Systems," IEEE Trans. Computers, vol.23, no.1, pp.86-88, jan. 1974
[3] 香田　徹, "t重故障同時診断可能システム," 電子通信学会, vol.J61-D, no.9, pp.680-687, Sep. 1978
[4] J.D.Russell, C.R.Kime, "System fault diagnosis : closure and diagnosability with repair," IEEE Trans. Computers, vol.24, no.11, pp.1078- , 1975
[5] 香田　徹, "t重故障逐次診断可能システム," 電子通信学会, vol.J61-D, no.9, pp.688-694, Sep. 1978
[6] J.Xu and S.ze Huang, "Sequentially t-Diagnosable Systems: A Characterization and Its Applications," IEEE Trans. Computers, vol.44, no.2, pp.340-345, Feb. 1995
[7] A.D.Friedman, "A New Measure of Digital System Diagnosis," Proc.1975 int'l Symp. Fault-Tolerant Computing, pp.167-170, June 1993
[8] A.K.Somani and O.Peleg, "On Diagnosability of Large Fault Sets in Regular Topology-Based Computer Systems," IEEE Trans. Computers, vol.45, no.8, pp.892-903, Aug. 1996
[9] K.Nakajima, "A new approach to system diagnosis," In Proceedings of the 19th Allerton Conference on Communication. Control and Computing. Univ. of Ilinois, Urbana, Ill., pp.697-706, 1981
[10] M.Barborak, M.Malek, and A.Dahbura, "The Consensus Problem in Fault-Tolerant Computing," ACM Computing Surveys, vol.30, no.8, pp.171-220, June 1993
[11] T.Araki, Y.Shibata, "(t,k)-Diagnosable System: A Generalization of the PMC Models," IEEE Trans. Computers, vol.52, no.7, pp.971-975, July 2003
[12] 香田　徹, 吉田清明, 朱雀保正, 吉田紀彦, "マルチエージェントシステムにおける故障の分散的自己診断," MACC'97 1997
[13] K. Thulasiraman, "The Multilevel Paradigm for Distributed Fault Detection in Networks with Unreliable Processors," IEEE Circuits and Systems Society, 2003