Методы самодиагностирования

Размещено на http://www.allbest.ru/

Харьковский национальный университет радиоэлектроники

Методы самодиагностирования

Поповский В.В., Волотка В.С.

В современном информационном обществе телекоммуникационные сети являясь основой информационных сетей обладают все большей производительностью и надежностью. Использование различных процедур, обеспечивающих диагностирование типа SNMP, RMON и др. в значительной мере загружают эти сети

На системном уровне модели диагностики откатов [1] возникают из работы [2] и появляются из представления многопроцессорной вычислительной системы в виде некоторого множества модулей

элементы которого определяются глубиной диагностических процедур. Предполагается, что модули системы выполняют простейшие проверки (ПП) друг друга. В некоторой ПП модуль системы может быть либо проверяющим, либо проверяемым, но не может являться проверяемым и проверяющим одновременно. В различных ПП один и тот же модуль может быть одновременно проверяющим и проверяемым.

Проверяющий модуль подает на вход проверяемого тестовое воздействие, а с выхода проверяемого модуля снимает результаты тестирования, на основании которых принимает решение о техническом состоянии проверяемого им модуля. Решение, принятое промеряющим модулем, представляется булевой переменной , которая равна 0. Если проверяющий модуль , установил работоспособность проверяемого блока или равна 1, если промеряющий модуль установил отказ проверяемого блока .

Решение, принятое проверяющим модулем, зависит от его технического состояния. В РМС - модели (Parallel model combination) [2] предполaгается, что это решение совпадает с реальным техническим состоянием проверяемого модуля, если проверяющий модуль работоспособен. В случае отказа проверяющего модуля, решение, принятое им, может быть произвольным и искажать реальное состояние проверяемого модуля.

Упорядоченное множество решений, принятых всеми проверяющими модулями, образует синдром. Синдром дешифруется специальными безотказным устройством, которое не входит в состав модулей объекта диагностирования, а служит только для обнаружения отказавших модулей. Это устройство принято называть глобальным судьей [3].

Для определения условий дешифрации вводится параметр l - максимальное количество отказавших модулей объекта диагностирования [2]. Различают точную, приближенную и вероятностную дешифрацию синдрома. Точная дешифрация ставит целью однозначное обнаружение всех неисправных модулей при условии, что их число не превосходит значения lm, где m= |Q|. Приближенная дешифрация синдрома [4] предполагает определение некоторого подмножества Qc из s подозреваемых модулей, среди которых только l действительно отказали (m>c>z). Вероятностная дешифрация основывается на априорных вероятностях отказов модулей [5].

При заданном l выделяют параллельную и последовательную стратегии диагностирования [1]. Стратегия последовательного l-диагностирования основана на многократном повторении диагностических процедур, на каждом шаге которой обнаруживается хотя бы один отказавший модуль. Обнаруженные отказавшие модули заменяются на работоспособные, и процесс диагностирования повторяется. Поэтому последовательное l-диагностирование называют также l-диагностированием с заменой. Стратегия параллельного l-диагностирования или l -диагностирования без замены ставит целью обнаружение всех отказавших модулей за один шаг.

Практический интерес представляет определение условий локальной самодиагностируемости для полной решетки моделей диагностики отказов на системном уровне для случая точной дешифрации синдрома. Под локальной самодиагностируемостью будем понимать дешифрацию синдрома отдельно взятым модулем на основании результатов ПП, собранных этим модулем или модулями, имеющими с ним непосредственные связи. Модули, обладающие свойством локальной самодиагностируемости будем называть локальными судьями.

Множество ПП представляется взвешенным ориентированным графом B (Q, A) без петель, множество вершин которого совпадает с множеством модулей системы, а каждая дуга существует тогда и только тогда, когда вершимы , участвуют в выполнении одной и той же ПП. Направление дуги от вершины , к вершине означает, что вершина , проверяет вершину , а вес этой дуги (булева переменная ) представляет решение, принятое проверяющей вершиной.

Рассматриваются устойчивые отказы вершин, т е. каждая вершина при выполнении ПП может находиться в одном из двух состояний: работоспособном или отказавшем. Рассматривается только параллельное l-диагностирование.

Матрица весов дуг графа представляет синдром

Множество неисправных вершин графа coставляет образ неисправностей. Для всякого F справедливо: .

Под локальным арбитром понимается вершина способная определить хотя бы один элемент множества на основании весов исходящих путей c длиной 1.

Тогда под строгим локальным судьей понимается вершина , способная определить все элементы множества N на основании весов исходящих дуг.

Диагностическая модель описывается четверкой, определяющей правила порождения весов дуг [6,7]:

- решение, принимаемое работоспособной проверяющей вершиной о состоянии работоспособной проверяемой вершиной.

- решение, принимаемое работоспособной проверяющей вершиной о состоянии отказавшей проверяемой вершины:

- решение, принимаемое отказавшей и проверяющей вершиной о состоянии работоспособной проверяемой вершины:

- решение, принимаемое отказавшей проверяющей вершиной о состоянии отказавшей проверяемой вершины.

Очевидно, что ; . Предполагается, что ,, где символ "-" означает непредсказуемый (0 или 1) результат выполнения ПП. Например. PMC-модель [2] определяется четверкой 01--, a BGM-модель [8] cоответcтвенно четверкой 01-1. Рассмотрим эти модели более подробно.

1) По определению модель 0101 описывает идеальный случай выполнения ПП. Очевидно, что все m вершин графа являются строгими локальными судьями, поскольку веса каждой дуги, исходящей из проверяющей вершины, достоверно отражают состояние проверяемой вершины. Из этого следует, что в полносвязном графе всегда существует m строгих локальных судей.

2) Модель 0100 - всякая дуга с единичным весом существует тогда и только тогда, если она исходит из работоспособной вершины и входит в отказавшую вершину и, если из некоторой вершины исходит хотя бы одна дута с единичным весом, то все инцидентные ей исходящие дуги с пулевым весом однозначно определяют работоспособные вершины. Для существования строгого локального судьи необходимо выполнение условия . Если , то существует m-l строгих локальных судей.

3) Модель 010 решения, принимаемые проверяющими вершинами, в лучшем случае совпадают с решениями модели 0101, а в худшем - решениями модели 0100.

4) Модель 0111 - всякая дуга с нулевым весом существует тогда и только тогда, если обе вершины, ей инцидентные, работоспособны. Всякий простой путь с весами 01 входит в отказавшую вершину. Всякий простой путь с весами 10 исходит из отказавшей вершины.

5) Модель 01-1 (Bayesian Graphical Model - BGM) - решения, принимаемые проверяющими вершинами, в лучшем случае совпадают с решениями модели 0101, а в худшем решениями модели 0111.

6) Модель 0110 - отказавшая проверяющая вершина полностью искажает состояние проверяемой вершины, т.е. правила порождения весов дуг для этой модели описывают худший случай разметки моделей 01- -, 01-0, 011-.

7) Модель 01- (РМС) - в работах [9,10] рассматриваются базовые "треугольники диагностирования", т.е. пути вида и . Показано, что все остальные треугольники эквивалентны базовым с точностью до обозначения вершин. Показано, что для путей вида C₁ веса 001 пли 010 соответствуют отказавшей вершине i при любом состоянии вершин i и g. Для путей вида C₂ разметка 001 указывает на отказ вершины j, разметка 010 указывает на отказ вершины i, а разметка вида 100 - на отказ вершины g.

8) Модель 01-0 - хотя бы одна вершина, инцидентная любому пути вида С₁ с весами 001 или 010 и пути вида С₂ с весами 001, 010, 100 является локальным судьей.

9) Модель 011 - вершины, инцидентные любому пути вида C₁ с весами 001 или 010 и пути вида C₂ с весами 001, 010, 100 является локальным судьей.

локальный арбитр самодиагностируемость дешифрация

Заключение

Выявление в работе условия существования локальных и строгих локальных арбитров сведены в таблицу. Очевидно, что сложность дешифрации синдрома для строгих локальных арбитров можно оценить как . Анализ показал, что использование локальных арбитров для дешифрации синдрома позволяет снизить требование безотказности глобального арбитра, упростить и децентрализовать процедуры дешифрации синдрома.

Полученные в статье условия локальной самодиагностируемости для полной решетки моделей диагностики отказов на системном уровне для случая точной (t-diagnosable) дешифрации синдрома могут быть использованы для построения новых алгоритмов и процедур диагностики, самодиагностируемых и отказоустойчивых технических систем.

Библиографический список

1. Friedman A. System-Level Fault Diagnosis. / Friedman A. Simoncini L // Computer.-1980.-13, N 3.-p.47-33.

2. Preparata F.P. On the Connection Assignement Problem of diagnosible systems / Preparata F.P., Metze G., Chien R.T. // IEEE Trans, on Electronic Computers.-vol. EC-16, N 6.-1967-p 848-854.

3. Barborack M. The Consensus Problem in Fault-Tolerant Computing / Barborack M., Maiek M., Dahbura A. // ACM Computing Surveys.-vol 25, N 2, June 1993.-p 171-220.

4. Friedman A. A new measure of digital system diagnosis / Friedman A.// Dig. 1975 Int Symp. Of fault tolerant computating, IEEE, New York, June 1975.-p. 167-169.

5. Maheshwari S. On models for diagnosable systems and probabilistic fault diagnosis. / Maheshwari S., Hakimi S // EEE Trans. Computer/-1976.-vol. C-25,N 3.-p. 228-236.

6. Крамаренко М.Б Модели диагностирования отказов параллельной вычислительной системы / Крамаренко М.Б. // Электронное моделирование. 1989.- №3.-с. 60-65.

7. Гуляев В.А. Алгоритмы и методы организации процедур оперативного диагностирования в распределенных управляющих вычислительных системах. / Гуляев В.А., Крамаренко М.Б - Киев,1988.-55с. (Препр./ АН УССР. Ин-т проблем моделирования в энергетике;128).

8. Barsi F.A theory of diagnosability of diagital systems. / F. Barsi, F. Grandoni, P. Maestrini, // IEEE Trans Computers-1976,vol.C-25.-p.585-593.

9. Димитриев Ю.К. Эффективность локального самодиагностирования в вычислительных системах с циркулянтной диагностической структурой. / Димитриев Ю.К.// Математические основы надежности вычислительных и управляющих систем.2008.№2.-с.96-101.

10. Димитриев Ю.К. Условия локального самодиагностирования в вычислительных системах с циркулянтной структурой / Димитриев Ю.К., Задорожный А.Ф.// Вестник ТГУ. Приложение. 2007. №23.-с. 216-220.

Размещено на Allbest.ru