On multi-path routing for reliable communications in failure interdependent complex networks
- PDF / 610,849 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 143 Views
On multi-path routing for reliable communications in failure interdependent complex networks Zishen Yang1 · Wei Wang1 · Donghyun Kim2 Accepted: 16 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper studies several new multiple routing path computation problems in failureinterdependent complex networks such as smart grid communication network, each of which exhibits unique failure interdependency. Despite the difference of the formulation of the problems, we show that each of the problems can be reduced to another within polynomial time, and therefore they are equivalent in terms of hardness. Then, we show that they are not only N P-hard, but also cannot be approximated within a certain bound unless P = N P. Besides, we show that their decision versions to determine if there exist two failure independent paths between two given end nodes are still N P-complete. Finally, a series of heuristic algorithms are proposed to deal with the daunting hardness of the problems. Most importantly, this paper opens a new series of research problems with daunting complexity based on important real world applications. Keywords Smart grid communication network · Multi-path routing · Maximum non-disrupting paths problem · N P-hard · Hardness of approximation
1 Introduction Smart grid is an automated modern power supply network, which collects the realtime knowledge of the electricity producers and consumers, as well as of the status of
Support by National Natural Science Foundation of China under Grant No. 11971376. The preliminary version of this paper has been appeared in Proceedings of The 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017).
B
Wei Wang [email protected]
1
School of Mathematics and Statistics, Xi’an Jiaotong University, No. 28 Xianning West Road, Xi’an 710049, People’s Republic of China
2
Department of Computer Science, Georgia State University, 33 Gilmer Street, Atlanta, GA 30302-3965, USA
123
Journal of Combinatorial Optimization
power delivery infrastructure itself and exploits such knowledge to improve the overall efficiency, reliability, sustainability, and the economics of the production and the distribution of electricity (U.S. Department of Energy 2012). To achieve the real-time data collection throughout the system, smart grid is equipped with a communication network, which is tightly coupled with its power supply network. It is known that communication reliability, i.e. on-time message delivery, is a highly critical issue of smart grid communication network. In order for communications in a smart grid communication network to be reliable, a message sent from a source to a destination has to be delivered on time. A message in smart grid communication network is delivered from a source to a destination throughout multiple routers as is like the other traditional multi-hop routing networks. In network theory, the process of identifying the best possible message routing path from the source to the d
Data Loading...
