Accurate and Boundary Estimate of Communication Network Connectivity Probability Based on Model State Complete Enumeration Method
Keywords:
Network, Graph Structure, Probability of Connectedness, Model State Complete Enumeration Method, Boundary EvaluationAbstract
We consider one of communication network structure analysis and synthesis methods, based on the simplest approach to connectivity probability calculation – a method of full network typical state search. In this case, the typical states of the network are understood as the events of network graph connectivity and disconnection, which are simple graph chains and sections. Despite significant drawback of typical state enumeration method, which involves significant calculation complexity, it is quite popular at stage of debugging new analysis methods. In addition, on its basis it is possible to obtain boundary estimates of network connectivity probability. Thus, when calculating Asari–Proshana boundaries use full set of incoherent (top) and cohesive (bottom) communication network states. These boundaries are based on statement that network connectivity probability under same conditions is higher (lower) than that of network composed of independent disjoint (connected) subgraph complete set serial (parallel) connection. When calculating Litvak–Ushakov boundaries, only edge-disjoint sections (for upper) and connected subgraphs (for lower) are used, i.e. subsets of elements such that any element does not meet two-rods. This boundary takes into account the well-known natural monotonicity property, which is to reduce (increase) network reliability with decrease (increase) any element reliability. From a computational view point Asari–Proshana boundaries have huge drawback: they require references of all connected subgraphs to compute upper bounds and all minimal cuts for bottom, which in itself is non-trivial. Litvak–Ushakov boundaries are devoid of these drawback: by calculating them, we can stop at any searching step for variants of sets of independent connected and disconnected graph states.
References
2. Mussel C., Hopfensitz M., Kestler H.A. Boolnet package vignette. 2015. 49 p.
3. Teruggia R. Reliability Analysis of Probabilistic Networks: PhD Thesis. University of Turin. 2010. 241 p.
4. Dudnik B. Ya., Ovcharenko V. F. Nadezhnost' i zhivuchest' sistem svyazi [The reliability and survivability of communication systems]. M.: Radio i svyaz'. 1984. 216 p. (In Russ.).
5. Filin B P. Metody analiza strukturnoj nadezhnosti setej svyazi [Methods of analysis of structural reliability of communication networks]. M.: Radio i svyaz'. 1988. 208 p. (In Russ.).
6. Polovko A.M., Gurov S.V. Osnovy teorii nadezhnosti [Fundamentals of reliability theory]. BHV-Peterburg. 2006. 704 p. (In Russ.).
7. GOST R 53111–2008. Ustojchivost' funkcionirovaniya seti svyazi obshchego pol'zovaniya. Trebovaniya i metody proverki [Stability of the public communication network. Requirements and verification methods]. M.: Standardinform. 2009. 16 p. (In Russ.).
8. Oboskalov V.P. Structural reliability of electric power systems [Structural reliability of electric power systems]. Ekaterinburg: UrFU. 2012. 194 p. (In Russ.).
9. Batenkov K.A. [Numerical characteristics of the structures of communication networks]. Trudy SPIIRAN – Proceedings of SPIIRAS. 2017. vol. 4(53). pp. 5–28. (In Russ.).
10. Chaturvedi S.K. Network Reliability. Measures and Evaluation. John Wiley & Sons. 2016. 237 p.
11. Tutte W.T. Graph Theory. AddisonWesley Publishing Company. 1984. 333 p. (Russ. ed.: Tatt U. Teoriya grafov. M.: Mir. 1988. 424 p.).
12. Zhao J., Yagan O., Gligor V. On the Strengths of Connectivity and Robustness in General Random Intersection Graphs. 53rd IEEE Conference on Decision and Control. 2014. pp. 3661–3668.
13. Yagan O. Makowski A.M. Zero-one Laws for Connectivity in Random Key Graphs. IEEE Transactions on Information Theory. 2012. vol. 58. no. 5. pp. 2983–2999.
14. Zhao J., Yagan O., Gligor V. Connectivity in Secure Wireless Sensor Networks under Transmission Constraints. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing. 2014. pp. 1294–1301.
15. Nuñez A. et al. Detecting series periodicity with horizontal visibility graphs. International Journal of Bifurcation and Chaos. 2012. vol. 22. no. 07. pp. 1250160.
16. Zhang H.C. et al. Connection effect on amplitude death stability of multi-module floating airport. Ocean Engineering. 2017. vol. 129. pp. 46–56.
17. Batenkov K. A. Ustojchivost' setej svyazi [Network stability]. Akademiya FSO Rossii. 2017. 277 p. (In Russ.).
18. Brown J.I., Tufts J. On the roots of domination polynomials. Graphs and Combinatorics. 2014. vol. 30. no. 3. pp. 527–547.
19. Ushakov I.A. Kurs teorii nadezhnosti sistem [Course in the theory of reliability systems. M.: Drofa. 2008. 239 p. (In Russ.).
20. Pino W., Gomes T., Kooij R. A Comparison between Two All-Terminal Reliability Algorithms. Journal of Advances in Computer Networks. 2015. vol. 3. no. 4. pp. 284–290.
Published
How to Cite
Section
Copyright (c) 2019 Кирилл Александрович Батенков
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).