sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-436Research ArticleСтатьиМетоды ускорения расчёта надёжности сетей с ограничением на диаметрMethods of speeding up calculation of diameter constraint network reliabilityМиговД. А.MigovD. ..mdinka@rav.sscc.ruНестеровС. Н.NesterovS. ..cepeгa_666@inbox.ruРодионовА. С.RodionovA. ..alrod@sscc.ruИнститут вычислительной математики и математической геофизики СО РАНRussian FederationНовосибирский государственный университетRussian FederationСибГУТИRussian Federation201426102022014956Copyright © Мигов Д.А., Нестеров С.Н., Родионов А.С., 20222022Мигов Д.А., Нестеров С.Н., Родионов А.С.Migov D..., Nesterov S..., Rodionov A...Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/436

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

Calculating diameter constraint network reliability is NP-hard problem. The methods for edge reduction and special ordering of edges while calculating the reliability index by the well-known factoring method are proposed. Experiments show a considerable speeding up of diameter constraint network reliability computations.

надёжность сетислучайный графдиаметр сетиnetwork reliaЬilityrandom graphdiameter constraintReferencesColbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.Colbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks. 1983. V. 13. P. 107-120.Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks. 1983. V. 13. P. 107-120.Won J.-M., Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE transactions on reliability. 2010. V. 59,  3. P. 551 562.Won J.-M., Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE transactions on reliability. 2010. V. 59,  3. P. 551 562.Rodionov A., Migov D., Rodionova O. Improvements in the ef ciency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, 2. P. 460-465.Rodionov A., Migov D., Rodionova O. Improvements in the ef ciency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, 2. P. 460-465.Родионов А.С. К вопросу ускорения расчёта коэффициентов полинома надёжности случайного графа // Автоматика и телемеханика. 2011. N 7. С. 134-146.Родионов А.С. К вопросу ускорения расчёта коэффициентов полинома надёжности случайного графа // Автоматика и телемеханика. 2011. N 7. С. 134-146.Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотика вероятности связности графа с низконадёжными рёбрами // Прикладная дискретная математика. 2013. N 1(19). С. 93- 98.Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотика вероятности связности графа с низконадёжными рёбрами // Прикладная дискретная математика. 2013. N 1(19). С. 93- 98.Нечунаева К.А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. N 2. С. 18-26.Нечунаева К.А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. N 2. С. 18-26.Shakhov V., Choo H. Reliability of wireless sensor network with sleeping nodes // Lecture Notes in Computer Science. 2007. V. 4490. P. 530-533.Shakhov V., Choo H. Reliability of wireless sensor network with sleeping nodes // Lecture Notes in Computer Science. 2007. V. 4490. P. 530-533.Shakhov V. Рrotecting Wireless Sensor Networks from Energy Exhausting Attacks // Lecture Notes in Computer Science. 2013. V. 7971. Р. 184-193.Shakhov V. Рrotecting Wireless Sensor Networks from Energy Exhausting Attacks // Lecture Notes in Computer Science. 2013. V. 7971. Р. 184-193.Cancela H., Petingi L. Diameter constrained network reliability: exact evaluation by factorization and bounds // Proc. Int. Conf. on Industrial Logistics. Japan, 2001. P. 359-356.Cancela H., Petingi L. Diameter constrained network reliability: exact evaluation by factorization and bounds // Proc. Int. Conf. on Industrial Logistics. Japan, 2001. P. 359-356.Мигов Д.А. Расчёт надёжности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. N 7. С. 69-74.Мигов Д.А. Расчёт надёжности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. N 7. С. 69-74.Migov D., Rodionov A. Decomposing graph with 2-node cuts for diameter constrained network reliability calculation // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013). Kota Kinabalu, Malaysia, 2013. ACM New York, USA. Article No. 39. 6 p.Migov D., Rodionov A. Decomposing graph with 2-node cuts for diameter constrained network reliability calculation // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013). Kota Kinabalu, Malaysia, 2013. ACM New York, USA. Article No. 39. 6 p.http://www.extremetech.com/computing/ 98283-the-next-internet-a-quest-for-speed/2http://www.extremetech.com/computing/ 98283-the-next-internet-a-quest-for-speed/2

The authors declare that there are no conflicts of interest present.