Нестеров С.Н. Мигов Д.А.
Методы оценки надежности сетей с ограничением на диаметр
Докладчик: Нестеров С.Н.
Данная работа посвящена исследованию методов приближенного и точного расчета надежности сетей с ограничением на диаметр. Под надежностью понимается вероятность связности путем ограниченной длины для каждой пары узлов из заданного множества узлов. Как и для других показателей сетевой надежности, точный расчет рассматриваемого показателя является NP-трудной задачей [1]. Кроме этого, имеющиеся к настоящему моменту методы расчета надежности сетей с ограничением на диаметр не позволяют использовать какие-либо методы структурной редукции, что существенно усложняет расчет этого показателя. С другой стороны, один из последних результатов в области исследования методов расчета надежности – это метод последовательного уточнения границ надежности сети, позволяющий приостановить расчет при достижении одной из границ надежности заданного наперед значения [2,3]. Цель настоящей работы – разработка аналогичного алгоритма для случая с ограничением на диаметр сети, а также разработка методов ускорения при вычислении данного показателя.
В результате нами разработан алгоритм последовательного уточнения границ надежности сети для случая с ограничением на диаметр. Были также получены методы ускорения расчета: редукция цепей и оптимальный выбор ребра для ветвления. Полученные алгоритмы были протестированы на различных графах, в том числе на решетках, полных, и случайно сгенерированных графах. Результаты экспериментов подтвердили эффективность разработанных методов.
Работа поддержана РФФИ. Грант № 11-07-00183.
Литература
[1] Cancela H., Petingi L. Reliability of Communication Networks with Delay Constraints: Computational Complexity and Complete Topologies // Int. J. of Mathematics and Mathematical Sciences. 2004. Vol. 29. P. 1551-1562.
[2] Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Transactions on Reliability. September 2010. Vol 59, N 3. P. 551-562.
[3] Rodionov A.S, Migov D.A., Rodionova O.K. Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. June 2012. Vol. 61, N 2. P. 460-465.
| Тезисы доклада: | abstracts_175461_ru.pdf |
К списку докладов
