IJE TRANSACTIONS A: Basics Vol. 22, No. 4 (November 2009) 317-332   

downloaded Downloaded: 177   viewed Viewed: 1774

D. Bhardwaj
Department of Computer Science, GLA Institute of Technology and Management
P.O. Box 281406, Mathura, India

S.K. Jain and Manu Pratap Singh*
Department of Computer Science, ICIS, Dr. B.R. Ambedkar University
P.O. Box Agra-282002, Uttar Pradesh, India
sandeepzen@yahoo.co.in - manu_p_singh@hotmail.com

* Corresponding Author
( Received: September 18, 2008 – Accepted in Revised Form: February 19, 2009 )

Abstract    In this paper it is tried to estimate the reliability of a fully connected network of some unreliable nodes and unreliable connections (edges) between them. The proliferation of electronic messaging has been witnessed during the last few years. The acute problem of node failure and connection failure is frequently encountered in communication through various types of networks. We know that a network can be defined as an undirected graph N(V,E). It is believed that in a network the nodes as well as the connections can fail and hence can cause unsuccessful communication. So, it is important to estimate the network reliability to encounter the network failure. Various tools have been used to estimate the reliability of various types of networks. In this paper we are considering the approach of neuro optimization for estimating the network reliability. We use the simulation annealing to estimate the probabilities of various nodes in the network and Hopfield model to calculate the energies of these nodes at various thermal equilibriums. The state of the minimum energy represents the maximum reliability state of the network.


Keywords    Network Reliability, Neural Optimization, Simulated Annealing, Hopfield Model


چکیده    در اين مقاله تلاش شده تا قابليت اطمينان يک شبکه کاملاً پيوسته که شامل تعدادي گره غيرقابل اطمينان و اتصالات (لبه هاي) غيرقابل اطمينان بين اين گره ها مي باشد، تخمين زده شود. در سال هاي اخير، شاهد افزايش سريع ارسال پيام هاي الکترونيکي بوده ايم. درشبکه هاي مختلف، مشکل حاد افت گره ها و افت اتصالات به دفعات اتفاق افتاده است. مي دانيم که يک شبکه را مي توان به صورت نمودار غيرمستقيم N(V,E) تعريف کرد. تصور بر اين است که در يک شبکه، گره ها هم مانند اتصالات مي توانند دچار افت شوند و در نتيجه باعث ارتباط ناموفق گردند. لذا مهم است که قابليت اطمينان شبکه در مواجهه با افت شبکه تخمين زده شود. روش هاي مختلفي براي تخمين قابليت اطمينان انواع مختلف شبکه ها به کار برده شده است. در اين مقاله، ما رويکرد بهينه سازي عصبي را براي تخمين قابليت اطمينان شبکه به کار برده ايم. ما از شبيه سازي حرارتي براي تخمين احتمال انواع گره در شبکه استفاده کرده ايم و براي محاسبه انرژي اين گره ها در موازنه هاي حرارتي مختلف، مدل هوپ فيلد را به کار گرفته ايم. وضعيتِ داراي کمترين انرژي ممکن، بالاترين قابليت اطمينان شبکه را دارد.


1. Hui, K.P.,“Network Reliability Estimation”, Ph.D. Dissertation, Faculty of Engineering, Computer and Mathematical Science, University of Adelaide, Adelaide, Australia, (2005).

2. Boudali, H. and Dugan, J.B., “A Discrete Time Bayesian Network Reliability Modeling and Analysis Frame Work”, Reliability and System Safety, Vol. 3, No. 87, (2005), 337-349.

3. Lomonosov, M. and Shpungin, Y., “Combinatorics of Reliability Monte Carlo”, Random Structures and Algorithms, Vol. 4, No. 14, (1999), 329-343.

4. Barlow, R. E., “A survey of Network Reliability and Domination Theory”, Operation Research, Vol. 32, (1984), 478-492.

5. Ball, M.O., Complexity of Network Reliability Computation”, Networks, Vol. 10, (1980), 153-165.

6. Barlow, R.E. and Proschan, F., “Statistical Theory of Reliability and Life Testing”, Holt, Rinehart and Winston, Concord, CA, U.S.A., (1975).

7. Colbourn, C.J., “The Combinatorics of Network Reliabilty”, Oxford University Press, New York, U.S.A., (1987).

8. Colbourn, C.J., Satyanarayana, A., Suffel, C. and Sutner, K., “Computing Residual Connectedness Reliability for Restricted Networks”, Discrete Applied Mathematics, Vol. 44, (1993), 221-232.

9. Lucia, I.P., “Implementation of Factoring Algorithm For Reliability Evaluation of Undirected Networks”, IEEE, Transaction on Reliability, Vol. 37, (1988), 462-468.

10. Easton, M.C. and Wong, C.K., “Sequential Destruction Method for Monte Carlo Evaluation of System Reliability”, IEEE Transaction on Reliability, Vol. R-29, (1980), 27-32.

11. Elperin, T., Gertsbakh, I. and Lomonosov, M., “Estimation of Network Reliability using Graph Evolution Models”, IEEE Transactions on Reliability, Vol. 5 No. 40, (1991), 572-581.

12. Elperin, T., Gertsbakh, I. and Lomonosov, M., “An Evolution Model for Monte Carlo Estimation of Equilibrium Network Renewal Parameters”,Probability in the Engineering and Informational Sciences, Vol. 6, (1992), 457-469.

13. Fishman, G.S., “A Monte Carlo Sampling Plan for Estimating Network Reliability”, Operations Research, Vol. 34, (1986), 581-592.

14. Fishman, G.S., “A Monte Carlo Sampling Plan for Estimating Reliability Parameters and Related Functions”, Networks, Vol. 17, (1987), (169-186).

15. Hui, K.P., Bean, N., Kraetzl, M. and Kroese, D.P., “The Tree Cut and Merge Algorithm for Estimation of Network Reliability”, Probability in the Engineering and Informational Sciences, Vol. 1, 17, (2003), 24-25.

16. Kumamoto, H., Kazuo, T., Koichi, I. and Henley, E.J., “State Transition Monte Carlo for Evaluating Large, Repairable Systems”, IEEE Trans. Reliability, Vol. R-29, (1980), 376-380.

17. Lomonosov, M., “On Monte Carlo Estimates in Network Reliability”, Probability in the Engineering and Information Sciences, Vol. 8, (1994), 245-264.

18. Shpungin, Y., “Combinatorial and Computational Aspects of Monte Carlo Estimation of Network Reliability”, PhD. Dissertation, Dept. of Mathematics and Computer Science, Ben Gurion University of the Negev, New York, U.S.A., (1996).

19. Gertsbakh, and Shpungin, Y., “Combinatorial Approaches to Monte Carlo Estimation of Network Lifetime Distribution”, Appl. Stochastic Models Bus. Ind., Vol. 20, (2004), 49-57.

20. Shpungin, Y., “Combinatorial Approach to Reliability Evaluation of Network with Unreliable Nodes and Unreliable Edges”, International Journal of Computer Science, Vol. 3, No. 1, (2006), 177-182.

21. Yegnanrayana, B., “Artificial Neural Network”, Ed. 2, Prentice-Hall of India (P) Ltd., New Delhi, India, (1999), 149-196.

22. Peterson, C. and Soderberg, B., “Neural Optimization”, in the Hand Book of Brain Theory and Neural Network, Cambridge, MA, MIT Press, U.S.A., (1995), 617-621.

23. Hertz, J.A., Krogh, A. and Palmer, R.G., “Introduction to the Theory of Neural Computation”, Addission-Wesley, New York, U.S.A., (1991).

24. Muller, B. and Reinhard, J., “Neural Networks: An Introduction, Physics of Neural Networks”, Springer-Verlag, New York, U.S.A., (1991).

25. Ratana, C.S. and Smith, A.E., “Estimating All Terminal Network Reliability Using Neural Network”, Computer and Operation Research, Vol. 29, No. 7, (2002), 849-868.

26. Hopfield, J.J. and Tank, D.W., “Neural Computation of Decisions in Optimization Problems”, Biological Cybernetics, Vol. 52, No. 3 (1985), 141-152.

27. Yuille, A.L., “Constrained Optimization and the Elastic Net”, In the Hand Book of Brain Theory and Neural Networks, Cambridge, MA: MIT Press, U.S.A., (1995), 250-255.

28. Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., “Optimization by Simulated Annealing”, Science, Vol. 220, (1983), 671-680.

29. Peterson, C. and Anderson, J. R., “A Mean-Field Theory Learning Algorithm for Neural Networks”, Complex System, Vol. 1, (1987), 995-1019.

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir