Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования

Розглянуто мережу з ненадійними ребрами. Проводиться відновлення ребер, що відмовили. Функції розподілу часу безвідмовної роботи та відновлення ребер можуть бути загального вигляду. Запропоновано метод прискореного моделювання, який дозволяє будувати незміщені оцінки ймовірності відмови мережі (пере...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
1. Verfasser:	Кузнецов, Н.Ю.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207805
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования / Н.Ю. Кузнецов // Проблемы управления и информатики. — 2014. — № 3. — С. 61-73. — Бібліогр.: 31 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-207805
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-2078052025-10-15T00:01:54Z Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования Оцінка надійності відновлюваних (s–t)-мереж методом прискореного моделювання Evaluation of the reliability of repairable (s–t) networks by fast simulation method Кузнецов, Н.Ю. Методы обработки информации Розглянуто мережу з ненадійними ребрами. Проводиться відновлення ребер, що відмовили. Функції розподілу часу безвідмовної роботи та відновлення ребер можуть бути загального вигляду. Запропоновано метод прискореного моделювання, який дозволяє будувати незміщені оцінки ймовірності відмови мережі (переривання зв’язку між двома заданими вершинами s та t) у заданому проміжку часу. Знайдено умови, які гарантують обмеженість відносної похибки оцінки із зростанням надійності ребер. Чисельний приклад ілюструє ефективність запропонованого методу. A network with unreliable edges is considered. All failed edges can be repaired. Distribution functions of failure-free operation and repair time of edges are supposed to be of general type. A fast simulation method producing unbiased estimates for the network failure (interruption of connection between two given nodes s and t) in a given time interval is developed. It is proved that under some weak conditions an estimate has a bounded relative error with the increasing of edges reliability. Numerical example illustrates the efficiency of the method proposed. 2014 Article Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования / Н.Ю. Кузнецов // Проблемы управления и информатики. — 2014. — № 3. — С. 61-73. — Бібліогр.: 31 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207805 519.873 10.1615/JAutomatInfScien.v46.i5.10 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Кузнецов, Н.Ю. Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования Проблемы управления и информатики
description	Розглянуто мережу з ненадійними ребрами. Проводиться відновлення ребер, що відмовили. Функції розподілу часу безвідмовної роботи та відновлення ребер можуть бути загального вигляду. Запропоновано метод прискореного моделювання, який дозволяє будувати незміщені оцінки ймовірності відмови мережі (переривання зв’язку між двома заданими вершинами s та t) у заданому проміжку часу. Знайдено умови, які гарантують обмеженість відносної похибки оцінки із зростанням надійності ребер. Чисельний приклад ілюструє ефективність запропонованого методу.
format	Article
author	Кузнецов, Н.Ю.
author_facet	Кузнецов, Н.Ю.
author_sort	Кузнецов, Н.Ю.
title	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
title_short	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
title_full	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
title_fullStr	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
title_full_unstemmed	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
title_sort	оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207805
citation_txt	Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования / Н.Ю. Кузнецов // Проблемы управления и информатики. — 2014. — № 3. — С. 61-73. — Бібліогр.: 31 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT kuznecovnû ocenkanadežnostivosstanavlivaemyhstsetejmetodomuskorennogomodelirovaniâ AT kuznecovnû ocínkanadíjnostívídnovlûvanihstmerežmetodompriskorenogomodelûvannâ AT kuznecovnû evaluationofthereliabilityofrepairablestnetworksbyfastsimulationmethod
first_indexed	2025-11-25T05:12:39Z
last_indexed	2025-11-25T05:12:39Z
_version_	1849737939524780032
fulltext	© Н.Ю. КУЗНЕЦОВ, 2014 Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 61 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 519.873 Н.Ю. Кузнецов ОЦЕНКА НАДЕЖНОСТИ ВОССТАНАВЛИВАЕМЫХ (s–t)-СЕТЕЙ МЕТОДОМ УСКОРЕННОГО МОДЕЛИРОВАНИЯ Проблема надежного снабжения потребителей товаром имеет приоритетное значение для промышленности. Термин «товар» следует понимать в широком смысле. Это может быть газ, нефть, электроэнергия, информация и т.п. Передача происходит с помощью распределительных систем, которые имеют сетевую структуру. С точки зрения надежности наиболее важной их характеристикой яв- ляется вероятность отказа в заданном промежутке ],0[ T . В большинстве исследо- ваний [1–3] надежность элементов сети (вершины, ребра) характеризуется лишь вероятностью отказа, что соответствует случаю невосстанавливаемых элементов или стационарному режиму работы сети. Если же сеть функционирует в проме- жутке ],0[ T и неисправные элементы могут быть восстановлены, то имеем неста- ционарный случай, когда стандартные методы комбинаторики не позволяют дос- тичь желаемого результата. Более того, известно, что интенсивности отказа эле- ментов изменяются с течением времени (физические, химические реакции и другие причины). Поэтому нет оснований предполагать, что время безотказной работы элементов имеет экспоненциальное распределение. Это же замечание от- носится и ко времени восстановления элементов. Этот случай является наиболее сложным для исследования, поскольку поведение сети не может быть описано марковским или полумарковским процессом с конечным или счетным множест- вом состояний. Именно такая сеть исследуется в настоящей статье. В последние годы большое внимание уделялось развитию методов ускорен- ного моделирования. Потребность в создании специальных методов моделирова- ния возникла из-за главного недостатка стандартного метода Монте-Карло — не- ограниченно возрастающего времени моделирования при увеличении надежности системы. Резкого сокращения количества реализаций удается достичь за счет умелого сочетания аналитических формул, используемых для вычисления малых вероятностей, и статистического моделирования, позволяющего учесть основные особенности строения и функционирования систем. Разработано много подходов, направленных на уменьшение дисперсии оценок. Не вдаваясь в подробное описа- ние каждого метода, отметим основные направления исследований: аналитико- статистический метод [4–11], метод существенной выборки [12–17], метод рас- слоенной выборки [18, 19], метод MCMC (Markov Chain Monte Carlo) [20], метод ветвящихся траекторий [21], метод многоуровневого расщепления [22] и ряд дру- гих. Обзоры методов ускоренного моделирования вероятностей редких событий см. [23–25]. В настоящей статье общая идея ускоренного моделирования надежности не- марковских систем [10] используется для создания эффективного метода расчета надежности сети с высоконадежными восстанавливаемыми ребрами. Данный ме- 62 ISSN 0572-2691 тод позволяет получать несмещенные оценки. Найдены условия, гарантирующие ограниченность относительной погрешности оценок с возрастанием надежности ребер. Численный пример иллюстрирует эффективность метода. Постановка задачи Рассмотрим сеть, структуру которой задает граф ],,[ EVG  где V — конеч- ное множество вершин, а E — множество ребер: ,, Ewve  ., Vwv  Каждое ребро может быть как ориентированным, так и неориентированным. Это свойство за- дает функция ,1)(},1,0{:  ehEh если ребро  wve , является ориентирован- ным, и 0)( eh — если неориентированным. Последовательность ребер ,, 21  vv ,,,,, 132   nn vvvv  обладающих свойством Evv ii   ,1 или ,, 1 Evv ii   ,0),( 1 ii vvh ,,,2 ni  называется путем, ведущим из 1v в .nv Сеть содержит две выделенные вершины, имеющие стандартные обозначе- ния: s (source) и t (terminal). Предполагается, что для любой вершины ,sv  tv  существует путь, ведущий из s в t и проходящий через v. Вершины сети считают- ся абсолютно надежными и отказать не могут. В то же время могут отказать реб- ра. Задаются функции распределения )(xFe и )(xGe времени безотказной работы и восстановления ребра e соответственно. Восстановление начинается непосред- ственно в момент отказа. Сеть считается работоспособной, если существует путь исправных ребер, ведущий от источника s к вершине t. Подобные сети получили название (s– t)-сетей [26, 27]. Целью исследования является оценка вероятности )(TQ отказа сети в заданном интервале ).,0( T Нахождение минимальных отказовых сечений Рассматриваемая модель не может быть описана марковским или полумар- ковским процессом с конечным или счетным множеством состояний, что является принципиальным препятствием на пути использования аналитических методов, в частности асимптотических. С другой стороны, метод Монте-Карло является крайне неэффективным при исследовании высоконадежных сетей. Предлагаемый в настоящей статье метод ускоренного моделирования сочетает моделирование с аналитическим вычислением малых вероятностей. В его основе лежат идеи рабо- ты [10]. Для эффективного использования ускоренного моделирования необходимо располагать множеством минимальных сечений ребер (или наиболее вероятных се- чений). Множество ребер nee ,,1  называется сечением, если их одновременная неисправность влечет отказ сети. Сечение называется минимальным, если ни одно ребро нельзя из него удалить с сохранением отказа сети. Предложено несколько эффективных алгоритмов, позволяющих находить наи- более вероятные минимальные отказовые сечения [26–29]. Все они основаны на достаточно простой идее и отличаются лишь техникой реализации. Пусть A — некоторое подмножество вершин, обладающее следующими свойствами: a) AVtAs \,  ; б) для любого ,, svAv  существует путь из s в v, проходя- щий только по вершинам из множества A; в) для любого ,\ AVw ,tw  сущест- вует путь из w в t, проходящий только по вершинам из множества .\ AV Обозначим ,:,{ AvEwvC  :,{}\ EvwAVw   ,0),( vwh }\, AVwAv  множество ребер, соединяющих вершины из множеств A и .\ AV Очевидно, что C является минимальным сечением. Более того, различные множества A генерируют разные сечения C. Поэтому проблема нахождения всех минимальных сечений сводится к нахождению всех множеств A, обладающих указанными свойствами. В даль- нейшем используем следующий алгоритм нахождения минимальных сечений. Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 63 1. Полагаем }{sA  и строим сечение, порождаемое A : :,{  wsC }., Ews  Обозначим U множество, элементами которого будут подмножества из V. В кА- честве начального значения выберем }.{AU  Введем функцию }.1,0{: Uq Положим .1)( Aq 2. Последовательно выбираем все UA такие, что .1)( Aq Если таких A не существует, то все минимальные сечения построены и алгоритм окончен. В про- тивном случае выбираем A с указанным свойством и последовательно перебираем все множества },{eAA  где ребро  wve , удовлетворяет условиям ,, Ewv  ,Av AVw \ или ,, Evw  ,0),( vwh .\, AVwAv  3. Выбирая t в качестве начальной вершины, идем в направлении, противопо- ложном ориентации графа, и с запретом попадания в вершины множества .A Обо- значим B множество вершин, которые не удалось пройти. Очевидно, что .BA  4. Если ,UB то продолжаем перебор множеств A (см. шаг 2 алгоритма). Ес- ли же ,UB то включаем B в U и полагаем .1)( Bq При этом строим новое ми- нимальное сечение: :,{}\,:,{ EvwAVwAvEwvC   ,,0),( Avvwh  }.\ AVw 5. Если все ребра e были учтены при построении множеств ,A то полагаем 0)( Aq и продолжаем алгоритм с шага 2. Данный алгоритм позволяет находить все минимальные сечения. Их число может быть огромным. Поэтому на практике без особой потери точности исполь- зуют методы отсечения [30] маловероятных сечений. Этот подход будет продемон- стрирован на численном примере. Обозначим M множество минимальных сечений. Ускоренное моделирование вероятности Q(T) Поведение сети с точки зрения надежности описывается непрерывным спра- ва марковским процессом ,0),),();(())();(()(  tEettttt ee с начальным состоянием ,,0)0(,0)0( Eeee  где ,0)(  te если ребро e на- ходится в рабочем состоянии в момент t, и ,1)(  te если ребро находится на вос- становлении, )},( любого для)()(:sup{)( tztutuzt eee  — непрерыв- ное время пребывания ребра e в состоянии )(te к моменту t. Переменная )(t описывает качественное состояние системы с точки зрения надежности, а вектор )(t непрерывных дополнительных компонент задает пре- дысторию, что позволяет сделать процесс ,0),(  tt марковским. Обозначим S множество векторов ),,( Eee  где }.1,0{e Подмножество U состояний не- исправности системы задается следующим образом: }.1,1что такое,),,( сечение существует:),{( 1 kiMeeSEeU ieke   Обозначим ,0,)(  kk последовательные моменты, когда ребра меняют свои состояния (отказ или окончание восстановления). Пусть  )( )()( kk ),;();( )()()()( Eek e k e kk  — состояние марковского процесса в момент .)(k Начальное состояние процесса в момент 0)0(  задает вектор ;0( )0()0(  e ),0)0( Eee  . Вероятность )(TQ отказа сети вычисляется по формуле: }.,,,,{)( )()1()1()( 1 UUUTTQ nnn n      P (1) Пусть )(kt  и Ukk  )()( , , — некоторое состояние процесса. Обозна- чим );( )()( kkQ  вероятность отказа сети в ],( )( Tk при начальном состоянии 64 ISSN 0572-2691 )(k в момент .)(k Формула (1) может быть переписана как рекуррентное соот- ношение, более удобное при моделировании:                0: 1: 0 )( )( ,0: 0 )( )( )()( )( )()( )(1 )( )(1 )( );( k e k r k re r k rr r k rr err k rr r k rrkk G udG F udF Q                );( 0 1: 0: 0 )( )( )( )( )( )( )( )( )(1 )( )(1 )( ));(;( ud e r k rr r k rr k ee k eek k e k e k r F udF F zdF zezQ            );( 0 )( )( )( ,1: 0 )( )( )( )( , )(1 )( ));(;( )(1 )( ud k ee k eek err k rr r k rr k e k r G zdG zezQ G udG (2) где ),,(}},{\,,min{);( )()( EluueEluTud ll kk e  а ),,();( Elze ll  и ),,();( ** Elze ll  — состояния процесса непосредственно после отказа и восстановления ребра e соответственно: .0,0,1},{\,, **)()(**  eeee k lll k lll eElz (3) Несмотря на громоздкость, формула (2) имеет простую интерпретацию: zk  )( — первый после )(k момент изменения состояния сети (отказ или вос- становление), .)( Tzk  Ребра отказывают и восстанавливаются до тех пор, пока не откажет сеть. Если в некоторый момент произойдет отказ сети, ,),( * UEll  то полагаем .1));(;( )(  zezQ k Соотношение (2) лежит в основе рекуррентного алгоритма, позволяющего моделировать моменты отказа и восстановления ребер сети до тех пор, пока не произойдет ее отказ. Введем весовые множители, позволяющие оценить вклад в отказ сети каждого из возможных событий (отказ или восстановление ребер). Пусть ,),;()( Ttt  — произвольное состояние марковского процесса. Обо- значим )( некоторый положительный нормирующий множитель, который будет использован в следующем разделе для уменьшения дисперсии оценки. В качестве )( выбирается оценка вероятности монотонного отказа сети при начальном со- стоянии . При этом используется принцип монотонных отказов [31], согласно которому преимущественный вклад в отказ высоконадежной сети вносят моно- тонные траектории (число отказавших ребер монотонно возрастает). Предложен- ный в настоящем разделе алгоритм существенной выборки позволяет строить не- смещенные оценки вероятности )(TQ при любом выборе набора положительных )}.({  При определенном выборе )}({  (см. следующий раздел) относительная погрешность оценок будет оставаться ограниченной с ростом надежности ребер. Соотношение (2) может быть переписано в следующем виде:              1: 0 )( )( 0: 0 )( )( )()( )()( )(1 )( )(1 )( );( k r k r r k rr r k rr r k rr r k rrkk G udG F udF Q           0: )()()()( )()( )()( )( )( 1 ),;( ),;( ),;( k ee ekkk kk ekk juA uA uA Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 65       );( 0 )()()( )( )( )( )());(( )( ));(;( ud k ee k e k ee k eek k e FudF zdF zezQ       1: )()()()( )()( )( )( 1 ),;( ),;( k ee ekkk kk e juA uA , )());(( )( ));(;( );( 0 )()()( )( )( )(          ud k ee k e k ee k eek k e GudG zdG zezQ (4) где ),1},{\,0()(  er e jeErjj    Eee kk e kk uAuA : )()()()( ,),;(),;( (5) , )(1 )());(( )(),;( )( )()()( )()()()( k ee k ee k e k eeekkk e F FudF juA    если ,0)(  k e (6) , )(1 )());(( )(),;( )( )()()( )()()()( k ee k ee k e k eeekkk e G GudG juA    если .1)(  k e (7) Формулы (4)–(7) позволяют сформулировать общий алгоритм построения оценки вероятности )(TQ методом существенной выборки (строится оценка )(ˆ 1 TQ в одной реализации). 1. Положим 0k (счетчик числа изменений состояний сети в ]),0[ T , 0)0(  и зададим начальное состояние ).,0;0( )0()0()0( Errr  2. Предположим, что в момент )(k сеть перешла в состояние  )( )()( kk .),,;();( )()()()()( UEe kk e k e kk  Для каждого Er строим реализацию случайной величины r с функцией распределения , )(1 )()( )( )()( k rr k rr k rr F FxF   0x (если )0)(  k r или с функцией распределения , )(1 )()( )( )()( k rr k rr k rr G GxG   0x (если ).1)(  k r Пусть ., Erurr  3. Согласно (5)–(7) вычисляем ,),,;( )()( EeuA kk e  и ).,;( )()( kkuA  4. Моделируем случайную величину , которая принимает значение e с веро- ятностью ).,;(/),;( )()()()( kkkk e uAuA  Пусть .e 5. Если ,1)(  k e то а) вычисляем нормирующий множитель );(/),;( )()()()()1( ekkkk juAJ  б) моделируем случайную величину e с функцией распределения , )());(( )()( )()()( )()( k ee k e k ee k ee k ee GudG GxG   )];(,0[ )( udx k e  ; пусть ;ze  в) полагаем ,)()1( zkk   определяем новое состояние   )1()1( )( kk );( ze (см. (3)) и повторяем алгоритм с новым значением k с шага 2. Если же ,0)(  k e то а) вычисляем нормирующий множитель );(/),;( )()()()()1( ekkkk juAJ  66 ISSN 0572-2691 б) если ,)()( Uj ek  то: — моделируем случайную величину e с функцией распределения , )());(( )()( )()()( )()( k ee k e k ee k ee k ee FudF FxF   )];;(,0[ )( udx k e  пусть ;ze  — полагаем ,)()1( zkk   определяем новое состояние   )1()1( )( kk );(* ze (см. (3)) и повторяем алгоритм с новым значением k с шага 2; в) если же ,)()( Uj ek  то отказ ребра e приводит к отказу сети, алгоритм окончен и в качестве оценки )(ˆ 1 TQ выбираем .)(ˆ )()2()1( 1 kJJJTQ  (8) Справедливо следующее утверждение. Теорема 1. Для произвольного набора положительных чисел )}({  оценка )(ˆ 1 TQ является несмещенной, т.е. ).()(ˆ 1 TQTQ M Несмещенность оценки вытекает непосредственно из сформулированного ал- горитма и формул (4)–(8). Ограниченность относительной погрешности оценки Критерием устойчивости метода и высокой точности оценок, получаемых при исследовании сетей высокой надежности, принято считать относительную среднеквадратическую погрешность (ОСКП) .1)]([/)](ˆ[)(/)(ˆ)( 22 11  TQTQTQTQT MD Основной целью исследования является выбор весовых множителей )},({  гарантирующих ограниченность ОСКП с ростом надежности ребер сети. Именно это свойство свидетельствует об устойчивости метода моделирования к измене- нию надежности ребер. Вполне естественно считать, что время до отказа ребра существенно превосходит время его восстановления. Данную особенность вос- станавливаемых сетей формализуем следующим образом. Предположим, что функции распределения }),({ EexFe  могут быть пред- ставлены в виде: )()( )0( xFxF e ee   , где 0 — некоторый малый параметр, ,0i а )()0( xFe — функция распределения «умеренной» случайной величины. Воспользуемся условием, первоначально введенным в [19] (см. также [10]). Пусть функции }),({ )0( EexFe  являются абсолютно непрерывными с плотностями },),({ )0( Eexfe  удовлетворяющими следующему условию: существуют ,00  ,0i )2/,0( T и функции )(),( )2()1( xx ee  такие, что неравенство )()()( )2(1)0()1(1 xxfx eee ee   (9) выполнено для любых ),,0(,0 0 Tx причем .)(max,0)(infmin 0 )2()2()1( 0 )1(      T e Ee z z e TzEe duuduu (10) Условия (9) и (10) не являются ограничительными, большинство распределе- ний, используемых в теории надежности, удовлетворяет им (например, распреде- ления Эрланга и Вейбулла, гамма-распределение). Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 67 Структура сети с точки зрения надежности определяется множеством M мини- мальных отказовых сечений. Пусть SEee  ),( — произвольное состояние сети. Если существует сечение MeeC k  ),,( 1  такое, что ,1 ie ,,,1 ki  то в состоянии  сеть неисправна, т.е. ;U в этом случае полагаем .1)(  Пусть .\US Обозначим );(min)(,);( 1,0: CrrCr MCkii ee ie ii    , (11) и положим .)( )( r (12) Справедливо следующее утверждение. Теорема 2. Если плотности }),({ )0( Eexfe  удовлетворяют условиям (9), (10) и 0)}(1{min   e Ee Gg (13) для того же , что и в условии (10), то оценка ),(ˆ 1 TQ полученная методом уско- ренного моделирования, имеет ограниченную ОСКП, т.е. )1();()( OTT  при .0 Доказательство. Принимая во внимание то, что )()( )0( xfxf ee ee   , из не- равенств (9) и (10) следует, что для любого ],0[  Tx       x x x x eeee duufduufxFxF ee )()()()( )0( .)()( )1()1()1()1(       x x x x ee eeeeeee duuduu (14) Аналогично .)()()( 0 0 )2()0(     T T eee eeee duxfduufTF (15) Построим нижнюю оценку для ).(TQ Пусть ),0()0( Eee  — состояние сети, при котором все ребра находятся в исправном состоянии. Обозначим )0(C ),,( 1 kee  сечение, для которого    k i ee ii Crr 1 )0()0()0( );()( (см. (11)). Учитывая соотношения (13) и (14), получим нижнюю оценку для :)(TQ  },,2,,,,{)( 1111 kiTTQ ii eeeeee P ,)(][)()]()([ 0 1)1( 2 1 2 1          T e kk k i eee k TFgudFuFuFg k i ieie ii где }{ ie и }{ ie  — независимые случайные величины с функциями распределения )}({ xF ie и )}({ xG ie соответственно. Поскольку ,2/T то  )()( 11 ee FTF .11)1( ee   Следовательно, .][][)( )1()1( 1       kk ggTQ k i ieie (16) 68 ISSN 0572-2691 Построим верхнюю оценку для .)](ˆ[ 2 1 TQM Траектория процесса ),(t ,0t обрывающаяся в момент отказа сети, однозначно определяется случайной после- довательностью )},,,(,),,,(),,,{( )()()()1()1()1()0()0()0(   mmm  где }{ )(k — моменты изменения состояния сети (отказ или окончание восстановле- ния), )(k — состояние сети в момент ,0)(  k ,,, )1()0( UU   ,)( U  }{ )(km — номер ребра, вызвавшего изменение состояния сети в момент .)(k Предполагается, что ),0;0();( )0()0()0()0( Eeee  является фиксированным начальным состоянием, .0)0( m Заметим, что состояние );()( )()()()( kkkk  однозначно определяется подпоследовательностью ),,{( )0()0()( mk  )}.,(, )()( kk m Предположим, что подпоследовательность )(k является фиксиро- ванной, а следовательно, состояние )(k также известно. Обозначим  );,( )(kexD }\|,{ )()1()1( kkk emx   P совместное распределение двухмерной случайной величины ),,( )1()1(  kk m принимающей значения в .),( )( Ek  Обозначая , )(1 )( )(1 )( );( 1: )( )( 0: )( )( )( )()(        k r k r r k rr r k rr r k rr r k rrk G udG F udF ud где ),,( Eruu r  из (4) имеем       )( ),;( );();,( )()()( )()( 0 )( 0 )( ek e k kk kk j uA udexD  ),,,,;( ),;( ),;( )()()( )()( )()( uxH uA uA k e k e k ekk kk e     где , )());(( )(}}){\,,min{( ),,,;(,1 )()()( )()( )()()()( k ee k e k ee k eel k eek e k e k e k e FudF FeEluxF uxH    (17) если ,0)(  k e и , )());(( )(}}){\,,min{( ),,,;(,1 )()()( )()( )()()()( k ee k e k ee k eel k eek e k e k e k e GudG GeEluxG uxH    если .1)(  k e Обозначим               n ek e k kk kkn j uA udexD )( ),;( );();,( )()()( )()( 0 )( 0 )()(  .2,1),,,,;( ),;( ),;( )()()( )()( )()(     nuxH uA uA k e k e k ekk kk e (18) Из сформулированного в предыдущем разделе алгоритма следует, что        1 : 0 )0()1()1()( 1 )1()1( );,()](ˆ[ k UEm T nn mdDTQM Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 69       UEm T kkkn kk k mdD )1()1( )2(: )2()1()1()( );,(        UEm T kkkn kk k nmdD )()( )1(: )1()()()( .2,1),;,( (19) Данная формула имеет простую интерпретацию. Двухмерная функция )(D определяет совместное распределение номера ребра, вызывающего изменение со- стояния сети, и соответствующего момента этого изменения, при условии что из- вестна вся предыдущая траектория. Степень n оценки )(ˆ 1 TQ означает, что в этой же степени будут и все нормирующие множители. Рассмотрим произведение множителей , )( ),;(1 0 )()()( )()()( )1( )1(        k l ml m l lll k l l j uA W (20) где ),( )()( Eiuu l i l  — некоторые векторы с положительными компонентами. Поскольку ,1)( )()1()1( )( )(   k k mk m k j если ,)()1()1( )( )( Uj k k mk m k   то равенст- во (20) можно переписать в виде . )( ),;( ),;( 1 1 )()1()1( )()()( )0()0()0( )( )(        k l ml m l lll k l l j uA uAW (21) Заметим, что 0)0(  и ).,0;0( )0()0()0( Eeee  Поэтому из соотно- шений (5), (6), (12) и (15) вытекают неравенства      Eee jr Eee e e OTFjuA ee e : )2()( : )()0()0()0( )()()(),;( )( (22) равномерно относительно компонент вектора ,)0(u где ).( )0( r Более того, используя рекуррентные формулы, легко доказать, что ))((),;( )()()()( llll OuA  (23) равномерно относительно компонент вектора .)(lu Поскольку ,)()()1()1( )( )( lml m l l l j   то из (23) следует, что )1( )( ),;( )()1()1( )()()( )( )( O j uA l l ml m l lll     при .0 Поэтому существуют 01  и h такие, что h j uA l l ml m l lll     )( ),;( )()1()1( )()()( )( )( (24) равномерно относительно компонент вектора )(lu и ).,0( 1 Учитывая соот- ношения (19), (18), (21), (24), (17) и (20), получим ,)(),;()](ˆ[ 1 1)0()0()0(2 1     k k k TZhuATQM (25) 70 ISSN 0572-2691 где     UEm T k mdWTZ )1()1( : 0 )0()1()1( );,()(       UEm T kkk kk k mdW )1()1( )2(: )2()1()1( );,(        UEm T kkk kk k mdW )()( )1(: )1()()( ,);,(      0 0 )()()()( ,);(),,;();,( ii e i ee i uduxVexW  ,0:, )(1 )(}}){\,,min{( ),,;( )( )( )()( )()(     i ei ee i eel i eei e i ee i F FeEluxF uxV .1:, )(1 )(}}){\,,min{( ),,;( )( )( )()( )()(     i ei ee i eel i eei e i ee i G GeEluxG uxV Пусть },1,max{hh  }{min ee Ee   и ,1]/[ n где ][ обозначает целую часть. Формулу (25) можно переписать в виде                  nk k k n k k k TZhTZhuATQ 2 1 12 1 1)0()0()0(2 1 )()(),;()](ˆ[M .)]()([)(),;( 122 2 12 1 1)0()0()0(                 nk kk k n k k k TZTZhTZhuA (26) Величина )(2 TZ k — это вероятность отказа сети в промежутке ],,0[ T причем произошло ровно 2k изменений состояний сети. Необходимым условием наступле- ния указанного события является отказ по крайней мере k ребер. Вероятность отказа ребра (номер которого неизвестен) оценивается величиной ).(max TFe Ee Учитывая неравенство (15), имеем .][max)(max)( )2()2( 2 k k Ee k e Ee k eeTFTZ              Поэтому ).( 1 ][2 ][2)]()([ )2(2 )2(2 )2(2 122 2              o h h hTZTZh nn nk kk nk kk k (27) В то же время )()()()( 22 1 2212 1 2212 1 1 TQhTZhTZhTZh n k k nn k k nn k k k          . (28) Из соотношений (26), (22), (16), (27) и (28) следует, что 22 1 )]([/)](ˆ[ TQTQM )1(O при ,0 т.е. относительная погрешность остается ограниченной с воз- растанием надежности ребер сети. Теорема 2 доказана. Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 71 Численный пример Предложенный выше метод был использован для оценки вероятности отказа 12 сетей [26], состоящих из невосстанавливаемых ребер. Во всех случаях точное значение вероятности отказа попало в доверительный интервал, построенный с достоверностью 0,99 и относительной погрешностью 1 %. В настоящем разделе рассмотрим существенно более сложный случай восстанавливаемых ребер. Исследуется сеть (рисунок), состоящая из 200 вершин и 298 ребер (сеть 12 в [26]). Предположим, что )}({ xFe и )}({ xGe являются распределениями Вейбул- ла следующего вида: ,100,,1,)2,12(},)(exp{1)( 2  iiiexxFe ,99,,1,)22,2(,)12,12(},)(exp{1)( 2  iiieiiexxFe .},)10(exp{1)( 2 EexxGe  Предположим, что надежность сети исследуется в промежутке ],1,0[ т.е. .1T В качестве малого параметра  выберем ,4,3,2  nn . Общее количество минимальных сечений равно 10000. Некоторые сечения состоят только из двух ребер, однако есть сечения, содержащие 100 ребер. Следовательно, далеко не все сечения в одинаковой степени влияют на надежность сети. Время вычислений можно существенно сократить, если отсечь маловероятные сечения. В качестве критерия для отсечения маловероятных сечений выберем следующий. Пусть r — некоторое положительное число. Обозначим MM r )( подмножество сечений ,),,( 1 MeeC k   удовлетворяющих условию    k i ee r ii 1 . (29) Сечения, не удовлетворяющие (29), отбрасываются. Обозначим )(ˆ )( TQ r и )(ˆ )( Tr оценки вероятности отказа )(TQ и ОСКП ),(T полученные при за- данном уровне отсечения r с достоверностью 0,99 и относительной погрешно- стью 2 %. Обозначим также )(ˆ rN число реализаций алгоритма, необходимых для достижения указанной точности, а )(rM — число сечений во множестве .)(rM Результаты численного эксперимента представлены в таблице. Представленные в таблице численные данные показывают, что увеличение сечений со 103 до 301 не приводит к заметному увеличению точности оценок )(ˆ )( TQ r . Более того, ОСКП не только не возрастает, но даже слегка убывает с ростом надежности ребер сети, что полностью согласуется с утверждением тео- ремы 2. 1s 3 5 197 199 200t 198 2 4 6 … … 72 ISSN 0572-2691 Таблица  )(ˆ )( TQ r )(ˆ )( Tr )(ˆ rN 5,4r 103)( rM 5,5r 301)( rM 5,4r 103)( rM 5,5r 301)( rM 5,4r 103)( rM 5,5r 301)( rM 62 2,92  10 6 2,89 10 6 1,11 2,16 20280 77431 82 3,07  10 8 3,06  10 8 1,03 1,27 17426 26914 102 4,27  10 10 4,27  10 10 1,00 1,07 16701 19027 122 6,41 1210 6,44  10 12 1,00 1,01 16708 16958 Таким образом, предложенный в статье метод ускоренного моделирования является эффективным инструментом для оценки надежности восстанавливаемых сетей в самых общих предположениях относительно распределений длительно- стей безотказной работы и восстановления элементов. М.Ю. Кузнєцов ОЦІНКА НАДІЙНОСТІ ВІДНОВЛЮВАНИХ (s–t)-МЕРЕЖ МЕТОДОМ ПРИСКОРЕНОГО МОДЕЛЮВАННЯ Розглянуто мережу з ненадійними ребрами. Проводиться відновлення ребер, що відмовили. Функції розподілу часу безвідмовної роботи та відновлення ребер можуть бути загального вигляду. Запропоновано метод прискореного моделювання, який дозволяє будувати незміщені оцінки ймовірності відмови мережі (переривання зв’язку між двома заданими вершинами s та t) у заданому проміжку часу. Знайдено умови, які гарантують обмеженість відносної похибки оцінки із зростанням надійності ребер. Чисельний приклад ілюструє ефектив- ність запропонованого методу. N.Yu. Kuznetsov EVALUATION OF THE RELIABILITY OF REPAIRABLE (s–t) NETWORKS BY FAST SIMULATION METHOD A network with unreliable edges is considered. All failed edges can be repaired. Dis- tribution functions of failure-free operation and repair time of edges are supposed to be of general type. A fast simulation method producing unbiased estimates for the network failure (interruption of connection between two given nodes s and t) in a given time interval is developed. It is proved that under some weak conditions an estimate has a bounded relative error with the increasing of edges reliability. Nu- merical example illustrates the efficiency of the method proposed. 1. Bell M.G.H., Iida Y. The network reliability of transport. — New York : Emerald Group Publ. Lmt., 2003. — 438 p. 2. Gertsbakh I.B., Shpungin Y. Models of network reliability: analysis, combinatorics, and Monte Carlo. — Boca Raton : CRC Press, 2009. — 203 p. 3. Frenkel I.B., Karagrigoriou A., Lisnianski A., Kleyner A.V. Applied reliability engineering and risk analysis: probabilistic models and statistical inference. — New York : Wiley, 2013. — 448 p. 4. Коваленко И.Н. Анализ редких событий при оценке эффективности и надежности систем. — М. : Сов. радио, 1980. — 209 с. 5. Завадская Л.А. Оценка надежности системы с контролем и профилактикой аналитико-ста- тистическим методом // Кибернетика. — 1981. — № 2. — С. 56–59. 6. Коваленко И.H. К расчету характеристик высоконадежных систем аналитико-статисти- ческим методом // Электронное моделирование. — 1980. — 2, № 4. — С. 5–8. Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 3 73 7. Кузнецов H.Ю. Вычисление коэффициента оперативной готовности восстанавливаемой системы аналитико-статистическим методом // Кибернетика. — 1985. — № 5. — С. 95–101. 8. Коваленко И.H., Кузнецов Н.Ю. Методы расчета высоконадежных систем. — М.: Радио и связь, 1988. — 176 с. 9. Коваленко И.Н., Наконечный А.Н. Приближенный расчет и оптимизация надежности. — Киев : Hаук. думка, 1989. — 180 с. 10. Kuznetsov N.Yu. Fast simulation technique in reliability evaluation of Markovian and non- Markovian systems / Simulation and Optimization Methods in Risk and Reliability Theory. — New York : Nova Science Publishers, 2009. — P. 69–112. 11. Кузнецов H.Ю., Шумская А.А. Оценка опасности отказа резервированной системы методом ускоренного моделирования // Международный научно-технический журнал «Проблемы управления и информатики». — 2013. — № 3. — С. 50–62. 12. Glynn P.W., Iglehart D.L. Importance sampling for stochastic simulations // Manag. Science. — 1989. — 35, N 10. — P. 1367–1392. 13. Heidelberger P. Fast simulation of rare events in queueing and reliability models // ACM Trans. Modeling Comput. Simul. — 1995. — 5, N 1. — P. 43–85. 14. Juneja S., Shahabuddin P., Zajic T. Splitting-based importance-sampling algorithm for fast simu- lation of Markov reliability models with general repair-policies // IEEE Transactions on Reliab. — 2001. — 50, N 3. — P. 235–245. 15. Ермаков С.М. Метод существенной выборки для моделирования вероятностей умеренных и больших уклонений оценок и критериев // Теория вероятностей и ее применения. — 2006. — 51, № 2. — С. 319–332. 16. Smith P.J., Shafi M., Gao H. Quick simulation: a review of importance sampling techniques in communications systems // IEEE Selected Areas Commun. — 1997. — 15, N 4. — P. 597–613. 17. Li J., Mosleh A., Kang R. Likelihood ratio gradient estimation for dynamic reliability applications // Reliab. Engin. and System Safety. — 2011. — 96, N 12 — P. 1667–1679. 18. Fox B.L., Glynn P.W. Discrete-time conversion for simulating finite-horizon Markov processes // SIAM J. Appl. Math. — 1990. — 50, N 5. — P. 1457–1473. 19. Шумская А.А. Ускоренное моделирование коэффициента неготовности восстанавливаемой системы с ограниченной относительной погрешностью оценки // Кибернетика и системный анализ. — 2003. — № 3. — С. 45–58. 20. Jerrum M. The “Markov Chain Monte Carlo” method: analytical techniques and applications. — Edinburgh : Depart. Comp. Sci., Univ. of Edinburgh, 1995. — P. 191–207. 21. Ermakov S.M., Melas V.B. Design and analysis of simulation experiments. — Dordrecht : Kluwer Academic Publ., 1995. — 197 p. 22. Glasserman P., Heіdelberger Ph., Shahabuddіn P., Zajіc T. Multilevel splitting for estimating ra- re event probabilities // Oper. Research. — 1999. — 47, N 4. — P. 585–600. 23. Kovalenko I.N., Kuznetsov N.Yu., Pegg Ph.A. Mathematical theory of reliability of time depend- ent systems with practical applications. — Chichester : Wiley, 1997. — 303 p. 24. Lagnoux A. Rare event simulation // Probab. Eng. and Inf. Sci. — 2006. — 20, N 1. — P. 45–66. 25. Blanchet J., Lam H. Rare event simulation techniques // Proc. of the 2011 Winter Simulation Conference. — 2011. — P. 217–231. 26. Lin H.-Y., Kuo S.-Y., Yeh F.-M. Minimal cutset enumeration and network reliability evaluation by recursive merge and BDD // Proc. of the 8th IEEE Intern. Symp. on Computers and Communica- tions. — 2003. — P. 1341–1346. 27. Benaddy M., Wakrim M. Cutset enumerating and network reliability computing by a new recur- sive algorithm and inclusion exclusion principle // Intern. Journal of Computer Applications. — 2012. — 45, N 16. — P. 22–25. 28. A modified combined method for computing terminal-pair reliability in networks with unreliable nodes / Y. Chen, A.Q. Hu, K.W. Yip, X. Hu, Z.G. Zhong // Proc. of the 2nd Intern. Conf. on Ma- chine Learning and Cybernetics. — 2003. — P. 2426–2429. 29. Kuo S.-Y., Yeh F.-M., Lin H.-Y. Efficient and exact reliability evaluation for networks with imper- fect vertices // IEEE Trans. on Reliability. — 2007. — 56, N 2. — P. 288–300. 30. Hennings W., Kuznetsov N. FAMOCUTN & CUTQN: programs for fast analysis of large fault trees with replicated & negated gates // Ibid. — 1995. — 44, N 3.— P. 368–376. 31. Коваленко И.Н. Об оценке надежности сложных систем // Вопр. радиоэлектроники. — 1965. — 12, № 9 — С. 50–68. Получено 12.11.2013

Оценка надежности восстанавливаемых (s–t)-сетей методом ускоренного моделирования

Institution

Ähnliche Einträge