Detection of Articulation Nodes in Mobile Ad Hoc Network Using Algebraic Graph Theory

International Journal of Computer Trends and Technology (IJCTT)          
© 2016 by IJCTT Journal
Volume-42 Number-1
Year of Publication : 2016
Authors : Mohit Jain, Satish Chand


Mohit Jain, Satish Chand  "Detection of Articulation Nodes in Mobile Ad Hoc Network Using Algebraic Graph Theory". International Journal of Computer Trends and Technology (IJCTT) V42(1):26-32, December 2016. ISSN:2231-2803. Published by Seventh Sense Research Group.

Abstract -
There are some points in a ad hoc network called as critical points whose failure results in partioning of the network in two or more components and makes the network disconnected and if the network become disconnected the data will not be sent to desired destination. It will lead to less throughout and delay of packets. To alleviate this problem , in this paper we proposed a new algorithm based on results from algebraic graph theory, that can find the weak points in the network for single and multiple failure cases. In addition this, the complexity of our algorithm is O(n2), which is better then previous algorithm deployed for finding critical nodes. Experimental results to evaluate the proposed algorithm to detect the nodes and links failure under network conditions are presented.

[1] S.S Basu and A.Chaudhari, “Self Adaptive Topology Management for Mobile Ad Hoc Network,” IE(I) Journal-ET vol 84,July 2003
[2] David B.Johnson and David A.Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,”, Computer Science Department , Carneige Mellon University,5000 Forbes Avenue, Pittsburg,PA 15,213-3891.
[3] J.Jublin and J.Tornow,”The DARPA Packet Radio Network Protocols,” Proc ,IEEE, vol.75, no.1,1987,pp.21-32.
[4] B.M. Leiner, D.L.Nielson, and F.A.Tobagi,eds.,Proceedings of the IEEE, Special issue on Packet Radio Networks,vol.75, Jan1987
[5] Z.J.Haas,M.Gerla,D.B.Johnson, C.E.Perkins,M.B. Pursley,M.Steenstrup, and C.-K. Toh,eds.,IEEE Journal on Sel. Areas in Comm,.Special issue on Wireless Ad Hoc Networks, vol17, August 1999.
[6] P.Kermani and N.H. Vaidya, eds.,IEEE Personal Communication, Special issue on Advances in Mobile Ad Hoc Networking, Feb 2001.
[7] C.E.Perkins,ed.,Ad Hoc Networking.Addison-Wesley,2001.
[8] Cheng ,Y.-C.and Robertazzi,T.G. ,” Critical connectivity phenomena in multihop radio models”,IEEE Trans.Communication,Vol 37,1989,pp 770-777
[9] Philips,T.K.,Panwar,S.S and Tantawi,A.N. ,”Connectivity properties of a packet radio network model”, IEEE Trans.Inform. Theory,Vol 35, 1989,pp 1044-1047
[10] Piret,P.,” On the connectivity of radio networks”, IEEE Trans.Inform.Theory,vol 37,1991,pp 1490-1492
[11] Gupta,P. and Kumar, P.R,”Critical power for asymptotic connectivity in wireless networks”, In McEneany ,W.M., Optimization and Applications,1998,pp.547-566.Birkhauser
[12] R.Meesterand,R.Roy,Continuum Percolation.Cambridge,Mass.:Cambridge University Press,1996
[13] Dousse,O.,Thiran,P.and Hasler,M.”Connectivity in ad hoc and hybrid networks,”In Proc.IEEEInfocom,New York,USA,June 2002, pp.1079-1088
[14] F.Xue, and P.R.Kumar,”The number of neighbors needed for connectivityof wireless networks”, Wireless Networks,Vol10(2), 2004, pp.161-181
[15] S.Khuller,”Approximation algorithms for finding highly connected subgraphs”,In D.S. Hochbaum, editor,Approximation algorithms for NP hard problems.PWS Publishing Co.,1996
[16] G.Ausiello,and P.Crescenzi, and G.Gambosi, and V.Kann, A.Marchetti- Spaccamela,andM.Protasi,”Complexityandapproximation:Co mbinatorialoptimization problems and their approximability properties”,Springer-Verlag,Berlin,1999.
[17] Chlamtac,I.andFargo,A.”A new approach to the design and analysis of peer to peermobilenetworks”, ACM/Kluwer Wireless Networks,vol5,1999,pp.149-156
[18] Santi,P.,Blough,D.M. and Vainstein,F.”A probabilistic analysis for the radio range assignmnet problem in ad hoc networks”,In proc ACM mobiHoc,Long Beach,USA,October 2001,pp.212-220.
[19] M.J.B.Appel and R.P.Russo,”The minimum vertex degree of a graph on uniform points in [0,1]d”, Adv in Applied Probability,vol29,1997,pp.582-594
[20] Krishnamachari,B.,Wicker,S.B.andBejar,R.,”Phase transition phenomenon in wireless ad hoc networks”,In proc.IEEE Globecom,San Antonio,USA,November 2001,pp.2921-2925
[21] Bettstetter,C.,”On the minimum node degree and connectivity of wireless multihop network”,In Proc .ACM MobiHoc,June 2002,pp.80-91.
[22] Bettsetter,C.,”On the connectivty of wireless multihop networks with homogeneous and inhomogeneous range assignmnet”,In Proc.IEEE VTC,Vancouver,Canada,September 2002,pp.1706-1710.
[23] Bettstetter,C. and Zangl,J.,”How to achieve a connected ad hoc network with homogeneous range assignmnet:an analytical study with considerationof border effects”,In Proc.IEEE Conf.on Mobile and WirelessCommunicationNetworks(MWCN),Stockholm,Swed en,September 2002,pp.125-129
[24] Bettstetter,C.,”On the connectivity of ad hoc networks,”The Computer journal,Special issue on mobile and pervasive computing,47(4):432-447,July 2004.
[25] Bettstetter,C,”Topology properties of ad hoc networks with random waypoint mobility”,In Proc.ACM MobiHoc,Annapolis,USA,June 2003,Short Paper
[26] Q.Ling and Z.Tian,”Minimum node degree and kconnectivity of a wireless multihop network in bounded area,”Proc .of IEEE Globecom,2007.
[27] H.Zang and J.C.Hou,”On the critical total power for asymptotic k-connectivity in wireless networks,”IEEE/ACM Transactions on Networking,April 2008.
[28] Santi,P.and Blough,D.M,”The critical transmitting range for connectivity in sparse wireless ad hoc networks”,IEEE Trans.Mobile Computing,vol2,2003,pp.25-39.
[29] Desai,M.and Manjunath,D.”On the connectivity in finite ad hoc networks”,In Proc IEEE Commun.Lett.,vol6,2002,pp.437-439
[30] Nakano,K.,Shirai,Y.,Sengoku,M.and Shinoda,S.”On connectivity and mobility in mobile multi hop wireless networks”,In Proc.IEEE VTC,Jeju,Korea,April 2003,pp.89- 98
[31] P.J.Wan and C.W.Yi,”Asymptotic critical transmission radius and critical neighbor number for k-connectivityin wireless ad hoc networks”,5th ACM Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc),2004.
[32] P.Panchapakesan and D.Manjunath,”On the transmission range in dense ad hoc radio networks”,Proc .IEEE SPCOM’01,2001.
[33] M.D.Penrose,”A strong law for the longest edge of the minimal spanning tree,”The Annals of Probability,vol27(1),1999,pp.246-260
[34] M.D.Penrose,”The longest edge of the random minimal spanning tree,”The Annals of Probability,vol15(2),1999,pp.340-361
[35] R.Ramanathan, and R.Rosales-Hain,”Topology Control of Multihop Wireless Networks using Transmit Power Adjustment”,Proc IEEE Infocom 2000,pp.404-413
[36] V.Rodolpu, and T.H.Meng,”Minimum energy mobile wireless networks”,IEEE J.Selected Areas in Comm.,vol17(8),August 1999,pp.1333-1344.
[37] L.Li,J.H.Halpern,P.Bahl,Y.Wang,andR.Wattenhofer,”Analysi s of a cone-based distributed topology control algorithm for wireless multi hop networks”.to appear in Proc.ACM Symp. On principles of Distributed Computing(PODC),August2001.
[38] R.Diestel,Graph theory,Springer,2nd ed..2000.
[39] B.Bollobas,Modern Graph Theory,Springer,1998.
[40] W.Feller,An Introduction to Probability theory and its Applications,John Wiley&Sons,New York,1950.
[41] S.Janson,T.Luczak,andA.Rucinski,RandomGraphs,JohnWile y&Sons,New York,2000.
[42] N.A.C.Cressie,Statistics for Spatial Data,John Wiley&Sons,1991.
[43] J.Diaz,M.D.Penrose,J.Petit,and M.Serna,”Convergence Theorems for SomeLayout Measures on Random Lattice and Random Geometric Graphs,”Combinatorics,Probability,andComputing,no.6,2000 ,pp.489-511.
[44] Miroslav Fiedler. A property of eigen vectorsof non negative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal,25(4): pp 619-633 ,1975.
[45] Network Simulator ,NS-2,homepage
[46] MATLAB and statistics toolbox release 2012b, The Math works Inc,Natick,Masschusetts ,United States.

Ad hoc networks, connectivity, topology control, critical transmitting range, node density, eigenvector, fiedler vector, Eigen values , laplacian matrix, articulation nodes.