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 | ||
| DOI : 10.14445/22312803/IJCTT-V42P105 |
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. www.ijcttjournal.org. 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.
References
[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
http://www.isi.edu/nsnam/ns/
[46] MATLAB and statistics toolbox release 2012b, The Math
works Inc,Natick,Masschusetts ,United States.
Keywords
Ad hoc networks, connectivity,
topology control, critical transmitting range, node
density, eigenvector, fiedler vector, Eigen values ,
laplacian matrix, articulation nodes.