Просмотр статьи


Номер журнала: 2014.1

Заголовок статьи: Методы ускорения расчёта надёжности сетей с ограничением на диаметр

Резюме

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

Авторы

Д. А. Мигов, С. Н. Нестеров, А. С. Родионов

Библиография

1. Colbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987.
160 p.
2. Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks. 1983. V. 13. P. 107-120.
3. 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.
4. Rodionov A., Migov D., Rodionova O. Improvements in the efficiency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, № 2.
P. 460-465.
5. Родионов А.С. К вопросу ускорения расчёта коэффициентов полинома надёжности случайного графа // Автоматика и телемеханика. 2011. № 7. С. 134-146.
6. Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотика вероятности связности графа
с низконадёжными рёбрами // Прикладная дискретная математика. 2013. № 1(19). С. 93-98.
7. Нечунаева К.А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. № 2. С. 18-26.
8. Shakhov V., Choo H. Reliability of wireless sensor network with sleeping nodes // Lecture Notes in Computer Science. 2007. V. 4490. P. 530-533.
9. Shakhov V. Protecting Wireless Sensor Networks from Energy Exhausting Attacks // Lecture Notes in Computer Science. 2013. V. 7971. P. 184-193.
10. 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.
11. Мигов Д.А. Расчёт надёжности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. № 7. С. 69–74.
12. 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.
13. http://www.extremetech.com/computing/
98283-the-next-internet-a-quest-for-speed/2

Ключевые слова

надёжность сети, случайный граф, диаметр сети.

Скачать полный текст