Abstract

Reliability calculation of large scale MANETs is an NP computational problem, and this complexity can be reduced by identifying critical nodes in a network. The identification of critical nodes itself is a computationally hard problem. The present work provides an empirical Algorithm for detecting critical nodes in a MANET which is computationally efficient than the already existing detection methods. The algorithm proposed for critical node detection is based on the pattern a critical node may exhibit uniquely in a connection matrix.

References

• Majid Ahmad and Durgesh Kumar Mishra. Article: A Reliability Calculations Model for Large-Scale MANETs. International Journal of Computer Applications 59(9):17-21, December 2012.
• Michaël Hauspie. Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad hoc Networks, in: "Proc. 3rd IFIP Mediterranean Ad Hoc Networking Workshop (MED-HOC-NET 2004), Bodrum,Turkey",2004.
• M. Jorgic, I. Stojmenovic, M. Hauspie, and D. Simplot-Ryl. Localized algorithms for detection of critical nodes
• and links for connectivity in ad hoc networks. 3rd IFIP MED-HOC-NET Workshop, 2004.
• A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos. Detecting critical nodes in sparse graphs. Comput. Oper. Res. , 36(7):2193-2200, 2009.
• M. Duque-Anton, F. Bruyaux, P. Semal, Measuring the survivability of a network: connectivity and rest-connectivity, European Transaction of Telecomunications, 11, 2, 149-159, 2000.
• Hung M. Dao, Silio, C. B. , Jr. , "Ring-network with a constrained number of consecutively-bypassed stations", Reliability, IEEE Transactions on, On page(s): 35 - 43 Volume: 47, Issue: 1, Mar 1998
• D. Goyal and J. Caffery, Partitioning avoidance in mobile ad hoc networks using network survivability concepts, Proc. IEEE Int. Symp. Computers and Communications ISCC, Taormina, Italy, July 2002, 553-558.
• M. O. Ball "The complexity of network reliability computations", Networks, vol. 10, pp. 153 -165 1980
• Wei-Chang Yen, "A Simple Heuristic Algorithm for Generating All Minimal Paths", Reliability, IEEE Transactions on, On page(s): 488 - 494 Volume: 56, Issue: 3, Sept. 2007
• Park, K. S. , Cho, B. C. , "RAPID: Recursive Algorithmic PIvotal Decomposition program for complex structural reliability analysis", Reliability, IEEE Transactions on, On page(s): 50 - 53 Vol: 37, Issue: 1, 1988
• Cancela, H. , El Khadiri, M. , "The recursive variance-reduction simulation algorithm for network reliability evaluation", Reliability, IEEE Transactions on, On page(s): 207 - 212 Volume: 52, Issue: 2, June 2003
• Jane, C. -C. , Lin, J. -S. , Yuan, J. , "Reliability evaluation of a limited-flow network in terms of minimal cutsets", Reliability, IEEE Transactions on, On page(s): 354 - 361, 368 Volume: 42, Issue: 3, Sep 1993
• Hardy, G. , Lucet, C. , Limnios, N. , "K-Terminal Network Reliability Measures With Binary Decision Diagrams", Reliability, IEEE Transactions on, On page(s): 506 - 515 Volume: 56, Issue: 3, Sept. 2007
• ]Fu-Min Yeh, Shyue-Kung Lu, Sy-Yen Kuo, "OBDD-based evaluation of k-terminal network reliability", Reliability, IEEE Transactions on, On page(s): 443 - 451 Volume: 51, Issue: 4, Dec 2002
• Hsu, S. J. , Yuang, M. C. , "Efficient computation of terminal-pair reliability using triangle reduction in network management", Communications, 1998. ICC 98. Conference Record. 1998 IEEE International Conference on, On page(s): 281 - 285 vol. 1 Volume: 1, 7-11 Jun 1998
• Sy-Yen Kuo, Shyue-Kung Lu, Fu-Min Yeh, "Determining terminal-pair reliability based on edge expansion diagrams using OBDD", Reliability, IEEE Transactions on, On page(s): 234 - 246 Volume: 48, Issue: 3, Sep 1999
• Chin-Chia Jane; Yih-Wenn Laih; , "Computing Multi-State Two-Terminal Reliability Through Critical Arc States That Interrupt Demand," Reliability, IEEE Transactions on , vol. 59, no. 2, pp. 338-345, June 2010
• Bowman, M. , Debray, S. K. , and Peterson, L. L. 1993. Reasoning about naming systems. .
• Ding, W. and Marchionini, G. 1997 A Study on Video Browsing Strategies. Technical Report. University of Maryland at College Park.
• Fröhlich, B. and Plate, J. 2000. The cubic mouse: a new device for three-dimensional input. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems
• Tavel, P. 2007 Modeling and Simulation Design. AK Peters Ltd.
• Sannella, M. J. 1994 Constraint Satisfaction and Debugging for Interactive User Interfaces. Doctoral Thesis. UMI Order Number: UMI Order No. GAX95-09398. , University of Washington.
• Forman, G. 2003. An extensive empirical study of feature selection metrics for text classification. J. Mach. Learn. Res. 3 (Mar. 2003), 1289-1305.
• Brown, L. D. , Hua, H. , and Gao, C. 2003. A widget framework for augmented interaction in SCAPE.
• Y. T. Yu, M. F. Lau, "A comparison of MC/DC, MUMCUT and several other coverage criteria for logical decisions", Journal of Systems and Software, 2005, in press.
• Spector, A. Z. 1989. Achieving application requirements. In Distributed Systems, S. Mullender.