Эффективно вычислимые оценки надежности монотонных систем

Методы исследования.11.

Обзор литературы.11.

Структура и объем диссертации

13.

Краткое описание результатов диссертации.13.

Теоретическая и практическая ценность работы.15.

Аппробация, благодарности.16.

1 О теории надежности монотонных систем 18.

1.1 Математическая модель надежности монотонных систем. 18.

1.1.1 Монотонная система. Минимальные пути и минимальные разрезы. .18.

1.1.2 Случайная монотонная система и ее надежность. 21.

1.2 Методы вычисления надежности монотонных систем .24.

1.2.1 Перебор состояний.24.

1.2.2 Перебор минимальных путей или минимальных разрезов 24.

1.2.3 Метод непересекающихся произведений.26.

1.2.4 Факторизационный метод.29.

1.3 Оценки надежности монотонных систем.30.

1.3.1 Общие замечания.30.

1.3.2 Оценки включения-исключения.32.

1.3.3 Упаковочные оценки.32.

1.3.4 Развязочные оценки.33.

1.4 Выводы.38.

2 Построение новых оценок. Разностно-развязочные оценки надежности монотонных систем 39.

2.1 Формула надежности в терминах непересекающихся произведений .39.

2.2 Разностно-развязочные оценки.42.

2.3 Разностно-развязочно-упаковочные оценки.46.

2.3.1 Теоретическое сравнение с оценками Оксли — Уэлша для случайной изотропной монотонной системы.46.

2.3.2 Достижимость.48.

2.4 Эффективно вычислимые квазиупаковочные оценки надежности монотонных систем.51.

2.5 Пример. Сравнение оценок на мостиковой структуре .54.

2.6 Выводы.60.

3 Эффективно вычислимые оценки надежности информационных сетей 62.

3.1 Математическая модель надежности информационных сетей. 62.

3.2 О связи характеристик надежности неориентированных и ориентированных сетей.63.

3.3 Вычислительная сложность проблем анализа характеристик надежности информационных сетей .66.

3.4 Квазиупаковочные оценки терминальной надежности информационных сетей.68.

3.5 Квазиупаковочные оценки вероятности связности информационных сетей.71.

3.6 Квазиупаковочные оценки двухполюсной надежности информационных сетей.73.

3.7 Выводы.80.

4 Численное исследование оценок надежности монотонных систем 82.

4.1 Общие замечания.82.

4.2 Структура и описание алгоритмов и программных модулей.. 83.

4.3 Результаты тестирования для различных видов монотонных систем.87.

4.4 Выводы.102.

Заключение

103.

Приложение 105.

Список литературы

130.

Акты о внедрении 139.

Список сокращений мс — монотонная система.

ТКБ — теорема о клаттерной бифуркации.

РРУ — разностно-развязочно-упаковочные (оценки).

РРА — разностно-развязочно-антиблокирующие (оценки).

РР2 — разностно-развязочные (оценки) второго порядка.

У — упаковочные (оценки).

РУ — развязочно-упаковочные (оценки).

РА — развязочно-антиблокирующие (оценки).

ОУ — (оценки) Оксли — Уэлша.

ЭП — (оценки) Эзари — Прошана.

Б.В.Гнеденко так характеризует в [4] теорию надежности: «Общая научная дисциплина, изучающая методы и приемы, которых следует придерживаться при проектировании, изготовлении и эксплуатации изделий для обеспечения максимальной эффективности в процессе использования, а также разрабатывающая общие методы расчета качеств устройств по известным качествам соответствующих их частей называется теорией надежности» .

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

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

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

При анализе надежности систем обычно применяются дискретные вероятностные модели надежности из-за неспособности как моделирования механизма ошибок компонент системы (параметры повреждения компонент оцениваются на опытных данных), так и трудности вычисления надежности систем (см. раздел 3.3).

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

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

Готовность используется в контексте систем поддающихся ремонту. В этом случае состояние компоненты чередуется между работоспособным и отказавшим (и подвергающимся ремонту). Готовность (состояние устойчивости) компоненты определяется как предел вероятности того, что компонента работает во время t при t —> оо. Если поведение компоненты подчиняется предположениям чередующегося процесса восстановления (см. [35]), то готовность равна среднему времени отказа, деленному на сумму средних времен отказа и восстановления.

Определение надежности компоненты не влечет за собой рассмотрения ремонта. Указывается некая длина t времени и надежность компоненты определяется как вероятность того, что компонента не отказывает до времени t.

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

В [16, Гл. 4 Терминология. Общие понятия и эффективность, стр.168], говорится: «Живучесть — способность системы сопрягать свойства, необходимые для выполнения требуемых функций, при наличии воздействий, не предусмотренных условиями нормальной эксплуатации» .

В [13] говорится, что «В случае появления произвольных разрушающих воздействий говорят о „уязвимости“ или о „живучести“ информационных систем. Под „живучестью“ информационных систем можно понимать способность информационных систем поддерживать определенный уровень обслуживания при ухудшении показателей работоспособности ее компонент на некоторую величину». В [13] рассматривается также и детерминированная модель надежности/живучести, отсылая к вероятностным моделям к [6]. В [86] в качестве мер уязвимости рассматривается реберная связность сети, или двухполюсная реберная связность (см. также [37]).

Случайная монотонная система — одна из простейших моделей надежности составных технических систем, в частности, сетей передачи информации.

В этой модели предполагается, что работоспособность системы определяется исключительно знанием того, какие компоненты работают (отказали).

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

Термин «монотонная» объясняется тем, что система не перестает быть работоспособной, когда какие-либо отказавшие ее компоненты заменяются на исправные (восстанавливаются), или что-то же самое, если монотонная система не исправна, и какие-либо ее компоненты ее отказывают, то она остается неисправной.

В теории надежности монотонных систем большое внимание уделяется построению оценок надежности. Существует целый ряд оценок.

Особое место среди них занимают оценки надежности монотонной системы общего вида (с произвольным клаттером и произвольной надежностью компонент).

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

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

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

Предмет исследования.

Предметом исследования являются анализ существующих и разработка новых оценок надежности монотонных систем общего вида.

Цель диссертационной работы.

Цель диссертационной работы заключается в анализе, разработке и выборе эффективных методов оценки надежности монотонных систем. В рамках настоящей цели основные задачи диссертационной работы можно сформулировать следующим образом:

— анализ известных оценок надежности монотонных систем общего вида;

— построение новых, эффективно вычислимых, оценок надежности монотонных систем общего вида и сравнение их с существующими оценками этого типа;

— построение новых, эффективно вычислимых, оценок характеристик надежности сетевых систем;

— разработка алгоритмов и программных модулей, для исследования оценок надежности монотонных систем общего вида;

— сравнительный экспериментальный анализ оценок надежности монотонных систем общего вида и качественный вывод.

Актуальность темы

.

Потребность в оценках надежности монотонных систем общего вида обусловлена следующими причинами:

1. Монотонная система общего вида является весьма распространенным объектом. Легко убедиться в том, что не любой клаттер является клат-тером сети. Например, уже клаттер {{1, 2}, {2, 3}, {3,4}} не является клаттером двухполюсных путей или разрезов в сети. Это — простейший пример (к — 2, п = 3) так называемой последовательной системы «к из п», состоящей из п компонент 1, 2,., п и исправной тогда и только тогда, когда исправны все элементы какого либо набора из следующего семейства наборов.

1, 2, {2,3, .,& + 1},., {п — & + 1,., п}}.

Эта, и более общие монотонные системы, не являются системой сетевого типа.

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

2. Оценки надежности используются в статистических методах аппроксимации надежности для ограничения выборочного пространства. Например, доказательство эффективной аппроксимации (с заданной точностью) вероятности связности [56] использует ряд ее полиномиально вычислимых оценок.

3. Проблема синтеза надежной топологии сетей [42] принципиально связана с вычислением характеристик надежности для огромного количества потенциально возможных структур сети.

Установлено, что точное вычисление каждой характеристики надежности сети — $Р-полная проблема (понятие jjP-полноты и ее связь с NP-полнотой см. например, в [50]. Качественно fjP-полные проблемы есть проблемы подсчета, связанные с iVP-полными задачами, например, это проблема подсчета числа гамильтоновых циклов. Такие задачи по меньшей мере также трудны, как TVP-полные задачи, т.к. знание числа решений проблемы распознавания легко решает вопрос существования).

Эта алгоритмическая трудность в еще большей степени усиливает потребность в эффективном оценивании характеристик надежности сети. Ч. Калберн пишет [40]: «главная мотивация — это развитие инструмен-тариев для процесса синтеза сети. В этом контексте существующие оценки уже позволяют различать между плохими и хорошими топологиями, хотя, они недостаточно хороши в настоящее время, чтобы различать топологии, близкие по надежности.» .

Методы исследования.

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

Обзор литературы.

Простая, но очень общая, модель надежности есть случайная монотонная система.

Теория надежности таких систем началась с работы Ф. Мура и К. Шенонна [63] (русский перевод [14]). В ней получены некоторые результаты, касающиеся надежности двухполюсной сети, состоящей из независимых и равнона-дежных компонент — реле (случай, когда все элементы равнонадежны называют изотропным).

В 61-м году В. Бирнбаум, Д. Эзари, С. Саундерс в [38] обобщили результаты Ф. Мура и К. Шенонна на то, что они назвали когерентной системой. Сейчас вместо термина «когерентная» используется термин «монотонная» .

В 63-м году Д. Эзари Ф.Прошан в [48] рассмотрели случай монотонной системы, чьи компоненты независимы, но обладают, вообще говоря, разной надежностью, и получили первые нетривиальные оценки надежности таких систем. Почти вся литература по теории надежности цитирует эти оценки.

Анализу надежности сетей с рекурентной структурой посвящены работы В. А. Гадасина и И. А. Ушакова [3,26]. Отражение широкого спектра проблем надежности нашло в справочнике «Надежность технических систем», английское издание которого вышло под названием «Handbook of Reliability Engineering» (под ред. И.А.Ушакова) в 1994 г. [17].

С 79-го года надежность монотонной системы стала изучаться в теории перколяции под названием «вероятность клаттерной перколяции». Ок-сли, Уэлш, МакДиармид получили некоторые результаты, см. [69,70,61,62]. В частности, Оксли и Уэлш получили нижнюю оценку надежности монотонной системы для изотропного случая.

Введенное в 97-м году В. П. Полесским в [21] (и получившее обобщение в [22]) преобразование развязывания клаттеров и его теорема о клаттерной бифуркации позволила получить серию новых («развязочно-антиблокирующих») оценок и дать общие принципы построения развязочных оценок в дальнейшем.

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

В настоящий момент проблемам структурной надежности посвящено значительное число работ (см. например [23,15,5,27,25]). Среди отечественных, отметим работы Б. В. Гнеденко, А. Д. Соловьева, И. Г. Коваленко, Г. А.Маргули-са, В. П. Полесского, В. Е. Степанова, А. К. Кельманса, М. В. Ломоносова, В. А. Гадасина, И. А. Ушакова, В. А. Богатырева, Б. П. Филина. Среди зарубежных, отметим работы Р. Барлоу, Ф. Прошана, С. Росса, Дж. Оксли, Д. Уэлша, К. МакДи-армида, Ч. Калберна, Р. Вуда, Д. Шира, Б. Болобаша, Д. Каргера, А. Сатинара-яна и др.

Структура и объем диссертации

.

Диссертация состоит из введения, четырех глав, заключения, изложенных на 141 странице, содержит 16 рисунков, 8 таблиц и списка цитируемой литературы из 98 наименований.

Основные результаты диссертации можно резюмировать следующим образом:

1. Предложена и реализована новая идея использования структурной информации о разности членов клаттера для построения новых оценок надежности монотонной системы общего вида. Построено несколько видов таких «разностно-развязочных» оценок. Доказана достижимость разностно-развязочно упаковочных оценок.

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

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

4. Разработаны программные модули для основных методов оценивания монотонных систем общего видаприведены примеры работы алгоритмов и программ.

5. Проведены численные сравнения оценок надежности монотонных систем (оценок Эзари-Прошана, развязочно-антиблокирующих оценок, разностно-развязочно упаковочных оценок, оценок Оксли-Уэлша). Результаты сравнения свидетельствуют о превосходстве развязочно-антиблокирующих оценок над оценками Эзари-Прошана, разностно-развязочно упаковочных над упаковочными оценками и оценками Оксли-Уэлша. Среди оценок Эзари-Прошана, развязочно-антиблокирующих оценок и разностно-развязочно упаковочных оценок, тотального преимущества одних оценок над остальными нет.

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

Заключение

.