Методы ускорения расчёта надёжности сетей с ограничением на диаметр
Аннотация
Расчёт надёжности сети с ограничением на диаметр является 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 ef ciency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, 2. P. 460-465.
5. Родионов А.С. К вопросу ускорения расчёта коэффициентов полинома надёжности случайного графа // Автоматика и телемеханика. 2011. N 7. С. 134-146.
6. Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотика вероятности связности графа с низконадёжными рёбрами // Прикладная дискретная математика. 2013. N 1(19). С. 93- 98.
7. Нечунаева К.А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. N 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. Рrotecting Wireless Sensor Networks from Energy Exhausting Attacks // Lecture Notes in Computer Science. 2013. V. 7971. Р. 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. N 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
Рецензия
Для цитирования:
Мигов Д.А., Нестеров С.Н., Родионов А.С. Методы ускорения расчёта надёжности сетей с ограничением на диаметр. Вестник СибГУТИ. 2014;(1):49-56.
For citation:
Migov D..., Nesterov S..., Rodionov A... Methods of speeding up calculation of diameter constraint network reliability. The Herald of the Siberian State University of Telecommunications and Information Science. 2014;(1):49-56. (In Russ.)
Просмотров:
192
Послать статью по эл. почте 