Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Algorithms for the Ring Star Problem Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network

verfasst von : Zishen Yang, Donghyun Kim, Wei Wang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper introduces six new failure-independent multi-path computation problems in complex networks such as smart grid communication network, each of which comes with unique failure interdependency assumptions. 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 \(\mathcal {NP}\)-hard, but also cannot be approximated within a certain bound unless \(\mathcal {P}=\mathcal {NP}\). Besides, we show that their decision problem versions to determine if there exist two failure independent paths between two given end nodes are still \(\mathcal {NP}\)-complete. As a result, this paper opens a new series of research problems with daunting complexity based on important real world applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Touring Convex Polygons in Polygonal Domain Fences
Nächstes Kapitel An Improved Branching Algorithm for (n, 3)-MaxSAT Based on Refined Observations
Literatur
1.
United States Department of Energy. Smart Grid/Department of Energy. Accessed 18 June 2012
2.
Ishida, K., Kakuda, Y., Kikuno, T.: A routing protocol for finding two node-disjoint paths in computer networks. In: Proceedings of International Conference on Network Protocols (ICNP), pp. 340–347 (1992)
3.
Nikolopoulos, S.D., Pitsillides, A., Tipper, D.: Addressing network survivability issues by finding the \(K\)-best paths through a trellis graph. In: Proceedings of the 16th IEEE International Conference on Computer Communications (INFOCOM) (1997)
4.
Wang, J., Yang, M., Qi, X., Cook, R.: Dual-homing multicast protection. In: Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), pp. 1123–1127 (2004)
5.
Wang, J., Yang, M., Yang, B., Zheng, S.Q.: Dual-homing based scalable partial multicast protection. IEEE Trans. Comput. (TC) 55(9), 1130–1141 (2006)CrossRef
6.
Yang, B., Zheng, S.Q., Katukam, S.: Finding two disjoint paths in a network with min-min objective function. In: Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 75–80 (2003)
7.
Yang, B., Zheng, S.Q., Lu, E.: Finding two disjoint paths in a network with normalized \(\mathit{\alpha }^{+}\)-MIN-SUM objective function. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 954–963. Springer, Heidelberg (2005). https://​doi.​org/​10.​1007/​11602613_​95 CrossRef
8.
Yang, B., Zheng, S.Q., Lu, E.: Finding two disjoint paths in a network with normalized \(\alpha ^-\)-MIN-SUM objective function. In: Proceeding of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS) (2005)
9.
Yang, B., Zheng, S.Q., Lu, E.: Finding two disjoint paths in a network with minsum-minmin objective function. In: Proceedings of the 2007 International Conference on Foundations of Computer Science (FCS) (2007)
10.
Yang, M., Wang, J., Qi, X., Jiang, Y.: On finding the best partial multicast protection tree under dual-homing architecture. In: Proceedings of the Workshop on High Performance Switching and Routing (HPSR) (2005)
11.
Chen, X., Dinh, H., Wang, B.: Cascading failures in smart grid - benefits of distributed generation. In: Proceedings of the 1st International Conference Smart Grid Communications (SmartGridComm) (2010)
12.
Ruj, S., Pal, A.: Analyzing cascading failures in smart grids under random and targeted attacks. In: Proceedings of the 28th IEEE International Conference on Advanced Information Networking and Applications (AINA) (2014)
13.
Huang, Z., Wang, C., Stojmenovic, M., Nayak, A.: Balancing system survivability and cost of smart grid via modeling cascading failures. IEEE Trans. Emerg. Topics Comput. (TETC) 1(1), 45–56 (2013)CrossRef
14.
Nguyen, D.T., Shen, Y., Thai, M.T.: Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans. Smart Grid (TSG) 4(1), 151–159 (2013)
15.
Hayashi, M., Abe, T.: Network Reliability. IEICE, Tokyo (2010). (in Japanese)
16.
Grubesic, T.H., O’Kelly, M.E., Murray, A.T.: A geographic perspective on commercial internet survivability. Telematics Inform. 20, 51–69 (2003)CrossRef
17.
Liew, S.C., Lu, K.W.: A framework for characterizing disaster-based network survivability. IEEE J. Sel. Areas Commun. (JSAC) 12(1), 52–58 (1994)CrossRef
18.
19.
Wu, W., Moran, B., Manton, J., Zukerman, M.: Topology design of undersea cables considering survivability under major disasters. In: Proceedings of the IEEE 23rd International Conference on Advanced Information Networking and Applications (WAINA) (2009)
20.
Sen, A., Shen, B.H., Zhou, L., Hao, B.: Fault-tolerance in sensor networks: a new evaluation metric. In: Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM) (2006)
21.
Neumayer, S., Efrat, A., Modiano, E.: Geographic max-flow and min-cut under a circular disk failure model. In: Proceedings of the 31st IEEE International Conference on Computer Communications (INFOCOM) (2012)
22.
Zhang, X., Perrig, A.: Correlation-resilient path selection in multi-path routing. In: Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (2010)
23.
Hong, Y., Kim, D., Li, D., Guo, L., Son, J., Tokuta, A.O.: Two new multi-path routing algorithms for fault-tolerant communications in smart grid. Ad Hoc Netw. (ADHOC) 22, 3–12 (2014)CrossRef
24.
25.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)MATH
26.
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of 38th ACM Symposium on Theory of Computing, pp. 681–690 (2006)
Metadaten
Titel
On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network
verfasst von
Zishen Yang
Donghyun Kim
Wei Wang
Copyright-Jahr
2017
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-71147-8_6