Methods of speeding up calculation of diameter constraint network reliability
Abstract
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.
About the Authors
D. .. Migov
Институт вычислительной математики и математической геофизики СО РАН
Russian Federation
Russian Federation
S. .. Nesterov
Новосибирский государственный университет
Russian Federation
Russian Federation
A. .. Rodionov
СибГУТИ
Russian Federation
Russian Federation
References
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
Review
For citations:
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.)
Views:
196
Email this article 