РАСЧЕТ НАДЕЖНОСТИ ПРОТЯЖЕННЫХ ТРЕХСВЯЗНЫХ СЕТЕЙ

Рассматривается задача расчета вероятности связности протяженных сетей с ненадежными каналами связи. Точный расчет данного показателя — NP-трудная задача, что делает его затруднительным для сетей реальной размерности.

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

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

Работа выполнена в рамках проекта № 0251-2021-0005 ПФИ ИВМиМГ СО РАН

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

1. Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характери­стики // Успехи математических наук. 2015. Т. 70. № 1 (421). С. 35-88.
2. Мочалов В.А., Мочалова А.В. Применение экспертных систем для расчета вероятности связности между узлами графа //В сборнике: Гибридные и синергетические интеллектуальные системы. Материалы V Всероссийской Поспеловской конференции с международным участием. Под редакцией А.В. Колесникова. 2020. С. 226-235.
3. Родионов А.С. Можно ли добиться дальнейшего ускорения расчета характеристик связно­сти случайного графа? // Проблемы информатики. 2022. № 4 (57). С. 39-52.
4. Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. T. 8. № 3. P. 410-421.
5. Rodionova O.K., Rodionov A.S., Choo H. Network probabilistic connectivity: exact calculation with use of chains // Lecture Notes in Computer Science. 2004. T. 3045. C. 315-324.
6. Satyanarayana A., Wood R.K. A linear-time algorithm for computing K—terminal reliability in series-parallel networks // SIAM. J. Comput. 1985. T. 14. P. 818-883.
7. D. Migov, O. Rodionova, A. Rodionov, H. Choo. Network probabilistic connectivity: using node cuts // Springer Lecture Notes in Computer Science (in EUC Workshops). Vol. 4097, 2006, p. 702-709.
8. Тарханова О.Ю., Шахов В.В. К вопросу оценки эффективности беспроводных сенсорных сетей // Проблемы информатики. 2020. № 1 (46). С. 35-65.
9. Фархадов М.П.О., Блинова О.В., Васьковский С.В. Оценка надежности системы связи с подвижными узлами // Датчики и системы. 2018. V^s 5 (225). С. 3-8.
10. Шахов В.В., Чен X., Юргенсон А.Н., Лошкарев А.В. К вопросу оценки надежности ли­нейных беспроводных сенсорных сетей // Проблемы информатики. 2022. № 4 (57). С. 120-128.
11. N. Mohamed, J. Al-Jaroodi, I. Jawhar and S. Lazarova-Molnar. Failure impact on coverage in linear wireless sensor networks // 2013 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), Toronto, ON, Canada. IEEE Press, 2013. P. 188-195.
12. Мигов. Д.А. Диссертация на соискание ученой степени кандидата физико-математических наук «Расчёт вероятности связности случайного графа с применением сечений». Новосибирск: ИВМиМГ СО РАН. 2008. 97 С.
13. Мигов Д.А. Использование вершинных разрезов для точного вычисления вероятности связности сети // Труды Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Павлодар, 20-22 сентября 2006 года) - Том II - С. 51-58.
14. Page L.B., Perry J.E. A Practical Implementation of the Factoring Theorem for Network Reliability // IEEE transactions on reliability. 1988. Vol. 37, n. 3. P. 259-267.
15. Мигов Д.А. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. No.47. С. 62-86. DOL 10.17223/20710410/47/6.
16. Burgos J.M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discrete Applied Mathematics. 2016. V. 198. P. 91-100.