長 崎 大 学 工 学 部研 究 報 告 第
31
巻 第57
号 平 成1
3年55
分散協調型の故障診断 と秩序再構成
溝口 博三* ･下川 俊彦**
吉田 紀彦***
De c e n t r a l i z e dCo o p e r a t i v eFa u l t Di a g n o s i sa n dSy s t e mRe o r g a n i z a t i o n
by
Hi r omiM i zoguchi * ,Tos hi hi koShi mokawa
**,Nor i hi koYos hi da * * *
Fa ul tdi a gnos i sa ndr e c ov e r yi nd e c e nt r a l i z e dc o op er a t i v es ys t e mss u c ha smu l t i ‑ a ge n ts ys t e msa L r edi f f e r e ntf romt he on e si nc e nt r a li z e ds ys t ems .Thes e l fdi a gnos i sofas ys t e m i sa c t u a l l yi nt e gr a t i onofmu t ua ldi a g no s csoft h es ys t e m c ompon e n t s , a ndt h er e c ov e r yl Sa c t ua ll ys el fr e or ga ni z a t i onoft h es ys t e m.Thi spa p erp
res e n t s a na ppr oa c ht owa D dt h i s s or tofdi a g nos i sa ndr e c ov e r ya ppl yi ngat h e or yofdi s t r ibu t e dn e t wor kdi a g nos i s ,a ndi t si mpl e me n t a t iona nds ome e mpi r ic a le va lu a t i on.
1 .は じめに
自律分散協訴系 は ,卑近な比喰で言 えE 淵 の集団の ように ,冗長性 を内在す ることか ら耐故障性 に優れ る ことが ,集 中系に比較 しての重要 な便位性の一つ と言 われている. しか しなが ら,系全休が構成要素の協調 と秩序 によって構成 されているか らには ,障害の性質 によっては単一構成要素の故障で も系全体 に影響 を及 ぼす可能性 がやは り残 っている.すなわち,構成要素 の停止障害 に対 しては他の構成要素が自律的に処理 を 代行 して系全体の秩序 が再構成 され るので頑健である が ,一方 ,コ ミッシ ョン障害 など誤 った要素間通信 を 誘発す る障害 に対 しては ,他の構成要素 もそれに影響 を受 けるため ,系全体の故障 に繋 が りえる.そのよ う な系 を復旧 させ るためには ,故障要素の同定 とその隔 離 ない し修復 が必要 となる.そこで我 々は ,自律分散 協調系における村政降任の向上 に向けた考察 を進めて いる.
一般 に集 中系における耐故障性の向上 には ,監視機 を付加 して自己診断 を行 う,系 を多重化 してバ ックア ップす る,などの方策が とられ る. これ に対 して上記 のよ うな自律分散協調系では ,その冗長性 を有効 に活
用すべ く,構成要素の相互診断 と相互バ ックア ップに よって耐故障性 を向上 させ ることが必要 となる.分散 ネッ トワーク診断の分野では ,すでにその よ うな相
互診断の理論 モデルについて研究 が進んでいるが ,それ を実際の 自律分散協訴系に応用 しようとす るに際 して は ,故障の検出 ･同定 ･隔離 ･復旧に関す る具体的な 方式 を考案 し,それ を中央集権制御 な しに行 う機構 を 構築 しなければな らない. さらに ,自律分散協調系 は 動的であるのが普通であ り,系内の構成要素の集合 も 動的に変化 しえる.そこで ,系の その よ うな動的変化 にも追従 しえる機構である必要 がある.
本論文では以下 ,第 2 章で分散 ネ ッ トワーク診断の 理論 モデル について概要 をごく簡単 にまとめ る.次 い で第 3 章で ,それ を自律分散協窮系に適用す る際に必 要 となる故障の検出 ･同定 ･隔離 ･復旧の方式 につ い て述べ る.第 4 章ではプロ トタイプの設計 ,そ して第 5 章で ごく簡単な例題 による実験 を示す.第 6 章 は検 討 とまとめである.
2. ネ ッ トワーク鯵断理輪
構成要素間の相互診断 に基づ く分散 ネ ッ トワーク診
平成 1 3 年 4 月20 日受理
* 三菱電機 ( Mi t s ubi s hiEl e c t r icCo r p)
…
九州大学大学院 システ ム情報科学研究院 ( Gr a dua t eSc hoolofI nf or ma t i onSc i enc ea ndEI c c t r iC a l Eng ine e r ing , Kyus huUA i v e r s i t y)
* = 情報 システム工学科 ( De p art me ntofCompu t c ra ndl nf omut iOnSc i e nc e s )
5 6 溝口 博三 ･下川 俊彦 ･吉田 紀彦
断理論 として , P r e pa r a t a ,Me t z ea ndCh i e nの PMC モ デルがある 【 1 】 . これは ,ある要素 による別の要素の 検査について,正常な要素による検査は信頼で きるが 異常 な要素による検査は信頼で きないとい う前提の下 で ,最高 t 個 までの多重永久故障 を許す内か ら少なく とも 1 つの故障要素 を検出可能 な t 重故障逐次診断可 能系 ,および全ての故障要素 を同時に検出可能 な t 重 故障同時診断可能系 を定式化 した ものである.このモ デルは故障状態が時間的に変化 しない永久故障 を対象 としているが,診断可能 な系の必要十分条件 ,検査結 果集合 ( 症候群)からの故障要素の同定などについて ,
多 くの研究がな されている.
より一般 には ,故障状態が時間的に変化す る間欠故 障 も考 えなければな らない.そこでは正常要素か ら永 久故辞要素への検査のみが信頼で き,間欠故障要素に 対す る複数回の診断はその度 に結果が異なる恐れがあ り,間欠故障要素に対す る社数の正常要素か らの診断 は結果が一致 しない恐れがある.系内の故障要素 を正 常 と判定す ることを ｢ 不完全 な｣診断 ,正常要素 を故 障 を判定す ることを ｢ 不正確 な｣診断 と呼ぶが,間欠 故障の存在 は不完全な診断 を引 き起 こす. これは原理 的に避 けられない.そこで ,間欠故障 を含む系におい て少 な くとも正確 な診断 を保証す る故障診断が , 〟 r ‑ 自己診断可能系 【 2
],I / r / r 一 自己診断可能系 【 3],t k/ T 一 自 己診断可能系 【 4 】などとして定式化 されている.なお , ここで t は故障要素数の最大値 ,r は間欠故障要素数 の最大値 を表す.
これ らを捲 まえて ,香田 らは間欠故梓 も含む自己診 断 可 能 系 の 効 率 的 な構 成 方 法 を ｢高 度 構 造 化 系 ( hi gh l ys t r uc t u J d s ys t e m) ｣ として定式化 した 【 5 , 6 , 7, 81 . これ をご く簡潔 に説明す る.
分散 ネ ッ トワーク診断の理論では,構成要素 を節点 V,要素 Vか ら別の要素 uへの診断 を弧 e =( V,u) で表 し,系 を節点 と弧の集合か らなるグラフ G=【 V,E】( Ⅴ
= I v l ,E = t e I ) で表す.Fi g. 1に図示す るように ( 円が
Fi g.1 .Subs ys t e mH( Ⅴ; I , V)i nHi g hl ySt r uc t t mdSys t e m･
要 素 ,矢 印 が検 査 ),あ る要 素 を核 の被 検 査 要 素 ( ke me lun i t ) として長 さ 1 の検査列 を V本 ,長 さ2 の 検査列 を p本持つ ようなグラフを,副系 ( s u bs ys t e m) H( V; I ,V)と呼ぶ.ここで ,系内の全ての要素 Vが副 系 H を持つ時 ,その系 を高度構造化系 と呼ぶ.
高度構造化系においては,次の定理が証明 されてい る.
( 1 )系 G の全ての副系 H について下式が成 り立つな ら ば ,G は t 重故障同時診断可能系である
(Lx ｣は x を 越 えない最大の盤数).
p+L v/ 2 ｣ ≧t
( 2 ) 系 G の全ての副系 H について下式が成 り立つなら ば ,G は t / r h一自己診断可能系である.
p+L ( V‑ 1 ) r 2 ｣≧t+m in ( r , J C+ I )
さらに ,上記それぞれの定理 を満たす系について , 検査数 を最小 にす る症候群解析法 も構築 されている.
例 えば前者 については ,o( L EI ) の検査数で解析可能 な 系が構成で きる.
3. 自律分散協7I 系への適用
前章で概要 を簡単に説明 した診断理論 は,系内の故 障要素の同定 を可能 にす る条件 ,および同定手順の構 成法 を論 じている.分散協調的な故障診断の中核 とな るべ きものではあるが,これ を実際の自律分散協訴系 の故障診断および修復 に応用す るには,様々な処理 を 補 う必要 がある.それ らの処理 は系の助的構成に対応
し,かつ 中央集権制御 を排 したものでなければな らな い.それ らを,要素間の監視 ･検査 ,故障の検出 ･同 定 ･隔離 ･復旧のそれぞれについて ,席に述べる.
( 1 )要素間の相互監視 ･検査
構成要素 は ( 広い意味での)通信 によって互いに監 視 ･検査 を行 う.要素間の故障検出は,通常の故障検 出と同様 に ,停止障害 とオ ミッシ ョン障害については 通信の タイムアウ ト検査によって ,コ ミッシ ョン障害 については通信応答の正当性検査によって行 う.要素 間の通信路の故障検出 も,これに準ず る ( ただ し,監 視側要素が故障 している可能性 もある).
一般に,系がその構成要素について全対全の直接の 通信路 を有す るとは限 らない.一方 ,他 と通信路 を有 しない孤立 した構成要素 ( 秤)の存在 を考慮す る必要 はない.ここでは,全ての要素か ら他の全ての要素 に 直頼 ･間接の通信路 を経由 して到達可能で あるとす る.ただ し,通信路の故障に も対応す るためには,逮 信路 も冗長でなければな らない.
動的系 において ,新たな要素 が加入す る場合 には ,
通常処理 に必要 な通信路 を既存の要素 との間に確立す
分散協調型の故障診断 と秩序再構成
ることになるが,これに併せて相互監視 ･検査の通信 路 も確立す る.新たな要素の存在は,通信路 を経由 し て系内の全ての要素 に伝 えられ る.
( 2 ) 故障要素の同定
相互監視によって故障 ( の可能性)の検出 された要 素 につ いて ,それ を核要素 と して副系
Hを構成 し, 故障診断の手順 を遂行す る.ここで満た されているべ
き条件 は ,詳細 は割愛す るが ,系内の全要素数 を
n, 最大多重故障要素数 を t として ,下式で表 され る.
n>2t+1
しか しなが ら,一般 に動的系では要素の増減がありえ るため ,n が既知 とは限 らない.その場合には れの下 限 を仮定 して ,検査可能 な最大多重故障要素数 を決定 す る.ただ し個 々の副系 につ いては ,実際の p と V の値 か ら検査可能な最大多重故障数が決 まる.
ここでの最大 の問題 は ,｢誰 が｣副 系 を琴計 して
｢ 誰 が｣患果 を解析す るかであり,理論 モデルでは全 く考慮 されていない.仮 にこれ らの処理の中央集権制 御 を許容す る して も,その中枢要素の故障には対応で きない. これ らの処理 を自律分散協訴的に行 うには , 原理的には,全ての要素に全ての要素の存在 と通信関 係 ,すなわち系全体の トポロジーを把握 させておいて , 同一の処理 を行わせ ることになる.故障要素には正 し い処理 を期待す ることがで きないが
,nと t の間の上 記の関係か ら,多数決的に正 しい処理の結果 を得 るこ とがで きる.以上の方策は要件 として非常に厳 しい も のであって ,厳密 に任意の時点で保証す ることはで き ず ,通信量 も多大 になるが ,現時点ではこの方策 をと る.
( 3) 故障要素の隔離 と系の復旧
一般 に.自律分散協訴系では,一部の構成要素が機 能 を停止 して も,他の要素が自律的に処理 を代行 して 系全体の秩序 が再構成 され るように構築 されている.
裏返す と,そのように構築 されているのが自律分散協 調系である.そこで ,故障要素 については,それを他 の要素か ら隔離す ることによって ,系 を復旧す ること がで きる.これは,従来の静的冗長系や動的冗長系 と は,類似す る例 も考 えられ るが,種類 を異にす る冗長 系である.具体的には,故障要素の存在 を系内の全て の ( 正常)要素が互いに通知 し,この通知 を受 け取 っ た要素 は故障要素 との通信 を速断す る.
このような秩序再構成 における問題 として ,第 1 に , 系内の要素 を幾つ まで隔離 して も正常に再構成 しえる かは ,自律分散協調系の構成に依存す る.第 2 に,系 が均質 ,すなわち全て同種の要素か ら構成 されている 場合 には議論はまだ容易であるが ,非均質 ,すなわち
57
異種の要素が混在 している場合には,これ もその自律 分散協調系の性質に依存す る.
一方で ,その要素の故障が修復可能 な ものであるな らば ,その要素に異常であることを知 らしめて修復 を 試み させ るべ きである.すなわち,要素は自分が異常 である皆の通知 を他か ら受け取 ったならば ( それは自 分だけでは判断で きないので),自己 を修復す る可能 性 を探 るべ きである. しか しなが ら,修復可能か否か は故障の性質に依存するので ,ここでは当該要素に異 常であることを知 らしめるところまで しか考 えない.
4. 故障鯵断 と修復の具体的機構
前章で考察 と検討 を行 った基本方式に基づいて ,故 障診断 ･修復機構 を,具体的に次の手順 を実行す るも の として捕集す る.
( 1 )系に新たに加入 した要素 は ,既存の要素 との間に 通常処理に必要な通信路 を確立す るとともに,監視 ･ 被監視の相互関係 を確立 し,同時に系の トポロジーを 取得す る.一方 ,新たな要素の加入は ,系内の全ての 要素に通知 される.なお ,全ての要素は他のいずれか
か ら監視 されなければな らない.監視す る側の要素は, 通信の正当性 とタイムアウ トを適宜監視す る.
( 2) 自らが検査す る要素集合の内に異常 な もの を発見 した要素 は ,その存在 を系内の他の要素 に通知す る.
各要素は,その通知 された要素 を核 とす副系 を設計す る. (それ らの要素 その ものが異常でなければ)設計 され る副系は同一の ものになるので ,それに従 って各 要素は必要 に応 じて副系に参加 し,系全体 として副系 を構築す る.必要 なだけの 叶 と Vが確保で きない場 合 には ,診断は失敗 となる ( 最低の t = lを満たすに
は,p=1または V=2が必要).
( 3) 副系 に参加 した要素は ,各々の検査結果 を系内の 他の要素に通知す る.各要素は ,その症候群 を解析 し て故障要素 を同定す る.ここで も ( それ らの要素 その
ものが異常でなければ)解析結果は同一の ものになる ので ,それ に従 って系全体 として故障要素 を同定す
る.
( 4) 正常 な要素 は故障 と同定 された要素にその旨 を通 知 し,自己修復 を期待す る.通知 を受 けた要素は自己 修復 を試み ,可能であればその旨を返答する.自己修 復が不可能 だった場合には ,正常な要素は故障要素 と の通信路 を速断 し,故障要素 を隔離 して系全体の秩序
を再構成す る.
5. 実験 と評価
前章 までで述べた故障診断 ･復旧機構の動作 を検証
58 沸 t j 博三 ･下川 俊彦 ･吉田 紀彦
す る実巌例 として ,非常 に単純 な次の問題 を取 り上 げ て結果 を示す 【 9, 1 0】 .
自律的円環構成系
この系では ,構成要素 どうLが互 いに情報 を交換 し つつ ,中央集権制御 な しに自律的に ,無秩序 な初期状 態 か ら円周 とい う秩序的な形 を形成す る. ミルウォー キー大の鈴木によって考案 された分散 アル ゴ リズムで あり,その株安 は次の通 りである.
各要素 は次の情報および機能 を持つ.
･最終的に構成 され る円の直径 を知 っている.
･自分 と他の要素 との距離 を算出す る機能 を持つ.
そ して ,次の処理 を行 う.
( 1 )自分 と他 の要素 との距離 か ら,最 も近 い要素 と最 も遠い要素 を知 る.
(2)
