Two-terminal Reliability Analysis for Time-evolving and Predictable Delay-tolerant Networks

Author(s): Gaurav Khanna*, Sanjay K. Chaturvedi, Sieteng Soh

Journal Name: Recent Advances in Electrical & Electronic Engineering
Formerly Recent Patents on Electrical & Electronic Engineering

Volume 13 , Issue 2 , 2020

Become EABM
Become Reviewer
Call for Editor

Graphical Abstract:


Background: Several techniques are available to evaluate the two-terminal reliability (2TR) of static networks; however, the advent of dynamic networks in recent past, e.g., Delay Tolerant Networks (DTNs), has made this task extremely challenging due to their peculiar characteristics with an associated disruptive operational environment. Recently, a Cartesian product-based method has been proposed to enumerate time-stamped-minimal path sets (TS-MPS)-a precursor to compute the 2TR of such networks. However, it cannot be used to generate time-stamped-minimal cut sets (TS-MCS). TS-MCS cannot only be used as an alternative to generate 2TR but also to compute other unexplored reliability metrics in DTNs, e.g., the weakest link.

Objective: To propose a novel approach to enumerate both TS-MPS and TS-MCS of a dynamic network, thereby computing the 2TR of such networks.

Methods: The proposed technique converts the time aggregated graph model of a dynamic network into a Line Graph (LG) while maintaining the time-varying graph’s node reachability information. This LG is used thereafter to generate TS-MCS as well as TS-MPS to compute 2TR of the network.

Results: The DTN examples are presented to show the efficacy and salient features of our algorithm to obtain 2TR of such networks.

Conclusion: The terminologies and techniques used for studying/analyzing network reliability of static networks can be extended to dynamic networks as well, e.g., the notion of minimal path sets to TS-MPS or minimal cut sets to TS-MCS, to assess their network reliability-a potential area of furthering network reliability research.

Keywords: Delay tolerant networks, line graph, network reliability, sum-of-disjoint-products, time-aggregated graph, timestamped- minimal cut sets, time-stamped-minimal path sets.

G. Khanna, and S.K. Chaturvedi, "A comprehensive survey on multi-hop wireless networks: Milestones, changing trends and concomitant challenges", Wirel. Pers. Commun., vol. 101, no. 2, pp. 677-722, 2018.
S. Misra, B.K. Saha, and S. Pal, Opportunistic Mobile Networks., Cham: Springer International Publishing, 2016.
M.H. Eiza, and Q. Ni, "An evolving graph-based reliable routing scheme for VANETs", IEEE Trans. Vehi Technol., vol. 62, no. 4, pp. 1493-1504, 2013.
S.K. Chaturvedi, Network reliability: measures and evaluation..Hoboken,new Jersey: Salem, Massachusetts: John Wiley & Sons; Scrivener Publishing,, 2016
S.K. Chaturvedi, and K.B. Misra, "A hybrid method to evaluate reliability of complex networks", Int. J. Qual. Reliab. Manage., vol. 19, no. 8/9, pp. 1098-1112, 2002.
S. Soh, and S. Rai, "CAREL: Computer aided reliability evaluator for distributed computing networks", IEEE Trans. Parallel Distrib. Syst., vol. 2, no. 2, pp. 199-213, 1991.
D.R. Shier, and D.E. Whited, "Iterative algorithms for generating minimal cutsets in directed graphs", Networks, vol. 16, no. 2, pp. 133-147, 1986.
S.K. Chaturvedi, G. Khanna, and S. Soh, "Reliability evaluation of time evolving delay tolerant networks based on sum-of-disjoint products", Reliab. Eng. Syst. Saf., vol. 171, pp. 136-151, 2018.
S.K. Chaturvedi, and K.B. Misra, "An efficient multi-variable inversion algorithm for reliability evaluation of complex systems using path sets", Int. J. Reliab. Qual. Saf. Eng., vol. 09, no. 03, pp. 237-259, 2002.
O.S. Jasmon, and G.B. Kai, "A new technique in minimal path and cutset evaluation", IEEE Trans. Reliab., vol. R-34, no. 2, 1985.
B. Singh, "An algorithm for evaluating all the minimal cuts of a graph", Microelectron. Reliab., vol. 35, no. 5, pp. 865-867, 1995.
R. Mishra, and S.K. Chaturvedi, "A cutsets-based unified framework to evaluate network reliability measures", IEEE Trans. Reliab., vol. 58, no. 4, pp. 658-666, 2009.
S.H. Ahmad, "Simple enumeration of minimal cutsets of acyclic directed graph", IEEE Trans. Reliab., vol. 37, no. 5, pp. 484-487, 1988.
M. Samad, "An efficient algorithm for simultaneously deducing minimal paths as well as cuts of a communication network", Microelectron. Reliab., vol. 27, no. 3, pp. 437-441, 1987.
S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi, "An Algorithm to enumerate all cutsets of a graph in linear time per cutset", J. ACM,., vol. 27, no. 4, pp. 619-632, 1980.
Q. Liang, and E. Modiano, "Survivability in time-varying networks", IEEE Trans. Mobile Comput., vol. 16, no. 9, pp. 2668-2681, 2017.
S.K. Chaturvedi, and R. Mishra, "An efficient approach to enumerate cutsets arising in capacity related reliability evaluation", Qual. Technol. Quant. Manag., vol. 6, no. 1, pp. 43-54, 2009.
K.B. Misra, New Trends in System Reliability Evaluation., Elsevier Science Ltd., 1993.
N. Padmavathy, and S.K. Chaturvedi, "Evaluation of mobile ad hoc network reliability using propagation-based link reliability model", Reliab. Eng. Syst. Saf., vol. 115, pp. 1-9, 2013.
K.S. Meena, and T. Vasanthi, "Reliability analysis of mobile ad hoc networks using universal generating function: Reliability analysis of MANET using UGF", Qual. Reliab. Eng. Int., vol. 32, no. 1, pp. 111-122, 2016.
J. Li, L. Dueñas-Osorio, C. Chen, and C. Shi, "Connectivity reliability and topological controllability of infrastructure networks: A comparative assessment", Reliab. Eng. Syst. Saf., vol. 156, pp. 24-33, 2016.
X. Zhang, and S. Mahadevan, "A game theoretic approach to network reliability assessment", IEEE Trans. Reliab., vol. 66, no. 3, pp. 875-892, 2017.
C. Wang, L. Xing, A.E. Zonouz, V.M. Vokkarane, and Y.L. Sun, "Communication reliability analysis of wireless sensor networks using phased-mission model", Qual. Reliab. Eng. Int., vol. 33, no. 4, pp. 823-837, 2017.
J-M. Lu, F. Innal, X-Y. Wu, Y. Liu, and M.A. Lundteigen, "“Two-terminal reliability analysis for multi-phase communication networks”, Eksploat. Niezawodn. -", Maint. Reliab., vol. 18, no. 03, pp. 418-427, 2016.
J-H. Park, "Time-dependent reliability of wireless networks with dependent failures", Reliab. Eng. Syst. Saf., vol. 165, pp. 47-61, 2017.
J.L. Cook, and J.E. Ramirez-Marquez, "Mobility and reliability modeling for a mobile ad hoc network", IIE Trans., vol. 41, no. 1, pp. 23-31, 2008.
M. Huang, S. Chen, Y. Zhu, and Y. Wang, "Topology control for time-evolving and predictable delay-tolerant networks", IEEE Trans. Comput., vol. 62, no. 11, pp. 2308-2321, 2013.
F. Li, S. Chen, M. Huang, Z. Yin, C. Zhang, and Y. Wang, "Reliable topology design in time-evolving delay-tolerant networks with unreliable links", IEEE Trans. Mobile Comput., vol. 14, no. 6, pp. 1301-1314, 2015.
G. Baudic, T. Perennou, and E. Lochin, "Following the right path: Using traces for the study of DTNs", Comput. Commun., vol. 88, pp. 25-33, 2016.
N. Aschenbruck, A. Munjal, and T. Camp, "Trace-based mobility modeling for multi-hop wireless networks", Comput. Commun., vol. 34, no. 6, pp. 704-714, 2011.
T. Spyropoulos, R.N.B. Rais, T. Turletti, K. Obraczka, and A. Vasilakos, "Routing for disruption tolerant networks: Taxonomy and design", Wirel. Netw., vol. 16, no. 8, pp. 2349-2370, 2010.
P. Hui, J. Crowcroft, and E. Yoneki, "BUBBLE rap: Social-based forwarding in delay-tolerant networks", IEEE Trans. Mobile Comput., vol. 10, no. 11, pp. 1576-1589, 2011.
S. Iranmanesh, and K-W. Chin, "A novel mobility-based routing protocol for semi-predictable disruption tolerant networks", Int. J. Wirel. Inf. Netw., vol. 22, no. 2, pp. 138-146, 2015.
A. Sharma, and R. Kumar, Risk-energy aware service level agreement assessment for computing quickest path in computer networks. Int. J. Reliab. Saf., Vol. 13, no. ½, 2019.
F. Li, Z. Yin, S. Tang, Y. Cheng, and Y. Wang, "Optimization problems in throwbox-assisted delay tolerant networks: Which throwboxes to activate? How many active ones I need?", IEEE Trans. Comput., vol. 65, no. 5, pp. 1663-1670, 2016.

Rights & PermissionsPrintExport Cite as

Article Details

Year: 2020
Published on: 26 April, 2020
Page: [236 - 250]
Pages: 15
DOI: 10.2174/2213111607666190215121814
Price: $25

Article Metrics

PDF: 7