OЦЕНКА НАДЕЖНОСТИ СЕТИ МЕТОДОМ МОНТЕ-КАРЛО С ИСПОЛЬЗОВАНИЕМ ЕЕ РАЗЛОЖЕНИЯ ПО ТОЧКЕ СОЧЛЕНЕНИЯ

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

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

1.  Жуковский М.Е., Райгородский А. М. Случайные графы: модели и предельные характеристики // Успехи математических наук. 2015. Т. 70, № 1 (421). С. 35-88.
2.  Мочалов В. А., Мочалова А. В. Применение экспертных систем для расчета вероятности связности между узлами графа // Гибридные и синергетические интеллектуальные системы: материалы V Всероссийской Поспеловской конференции с международным участием. Под ред. А. В. Колесникова. 2020. С. 226-235.
3.  Colbourn Ch. J. The combinatorics of network reliability. N. Y.: Oxford Univ. Press, 1987. P. 160.
4.  Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. Т. 6. С. 10-17.
5.  Родионов А. С. Можно ли добиться дальнейшего ускорения расчета характеристик связности случайного графа? // Проблемы информатики. 2022. № 4(57). С. 39-52.
6.  Батенков А. А., Батенков К. А., Фокин А. Б. Вероятность связности телекоммуникационной сети на основе приведения нескольких событий несвязности к объединению независимых событий // Информационно-управляющие системы. 2021. № 6. С. 53-63. DOI: 10.31799/1684-8853-2021-653-63.
7.  Slyke R. V., Frank Н. Network reliability analysis. Part I // Networks. 1972. V. 1. P. 279-290.
8.  Cancela H., Urquhart M.E. Adapting RVR simulation techniques for residual connectedness network reliability models // IEEE Trans. Computers. 2002. V. 51, № 4. P. 439-443.
9.  Botev Z.I., Kroese D.P. Efficient Monte Carlo simulation via the generalized splitting method // Statistics and Computing. 2012. V. 22, № 1. P. 1-16.
10.  Мигов Д. А., Винс Д. В. Параллельная реализация и имитационное моделирование оценки надежности сети методом Монте-Карло // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2019. № 47. С. 66-74. DOI: 10.17223/19988605/47/8.
11.  Мигов Д. А. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. № 47. С. 62-86. DOI: 10.17223/20710410/47/6.
12.  Burgos J.M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discrete Applied Mathematics. 2016. V. 198. P. 91-100.