Analysis of K-Connected MANETs for QoS Multicasting using EDMSTs Based on Connectivity Index

Abstract

The survivability of the network is closely related to the connectivity of the network. For many network applications such as a sensor network/ad hoc network for battlefield monitoring or wild fire tracking etc., survivability is one of most important requirements, and therefore a number of related problems are proposed. In this paper we study the survivability with respect to multicast route failure tolerance in K-connected MANET. We analyze the key issues namely connectivity, route failure tolerance and energy of the network. These issues can optimize the design of the routing protocol by means of cross layer interaction across the layers of the network. This paper analyzes the K-connected MANET for various parameters namely connectivity, no. of links, no. of spanning trees, no. of EDMSTs using graph theory metric, connectivity index.

Reference

• R. Hekmat and P. Van Mieghem, “Study of Connectivity in Wireless Ad-hoc Networks with an Improved Radio Model”, Delft University of Technology, Netherlands, http://www.wmc.ewi.tudelft.nl/~ramin/publications/connect.pdf.
• Pasi Lassila et al, “Connectivity Properties of Random Waypoint Mobility Model for Ad Hoc Networks”, http://www.netlab.tkk.fi/tutkimus/ahras/publ/rwpconn-medhoc-crc.pdf.
• Christopher L. Barrett and D. Charles Engelhart, “Approximate Connectivity Graph Generation in Mobile Ad Hoc Radio Networks”, http://csl.cse.psu.edu/publications/ ss03.pdf.
• Laura Marie Feeney, “Introduction to MANET Routing”, Swedish Institute of Computer Science, http://www.nada. kth.se/kurser/kth/2D1490/05/lectures/feeney_mobile_adhoc _routing.pdf.
• Jon Kleinberg, “A First Random Graph Model”, http://www.cs.cornell.edu/courses/ cs6850/2008fa/random-graphs.pdf.
• Xiaowei Ying and Xintao Wu,”Graph Generation with Prescribed Feature Constraints”, Univ. of North Carolina, http://www.siam.org/ proceedings/ datamining /2009/ dm09_088_yingx.pdf.
• Fan Chung and Linyuan Lu, “The Average Distance in a Random Graph with Given Expected Degrees”, Internet Mathematics Vol. 1, No.1, pp. 91-114, http://www. internetmathematics.org/volumes/1/1/pp091_113.pdf.
• Brendan D. Mckay and Nicholas C. Wormald, Academy, Press, Inc 1990, http://cs.anu.edu.au/~bdm/papers /RandRegGen.pdf.
• K.V.R.H. Bharadwaj and V. Sunitha, “Application of Random Graph Theory and Percolation Theory in MANETs”, http://magnet.daiict.ac.in/ magnet_members/Btech/2004/ KVRHBharadwaj/report.pdf.
• Clement Fredembach and Graham D. Finlayson, ”Hamiltionian path based shadow removal”, School of Computing Sciences, University of East Anglia, Norwich.
• M. Didi Biha and A. R. Mahjoub, ”The k-edge connected subgraph problem I: Polytopes and critical extreme points”, Linear Algebra and its Applications, Vol. 381, PP. 117-139, April 2004, pp. 117-139.
• Angela Mestre and Centro de Fisica Teorica, “Generating connected and 2-edge connected graphs”, Journal of Graph Algorithms and Applications,http://jgaa.info/ Vol. 13, No. 2, PP. 251-281, 2009.
• Harold N. Gabow, “Approximating the Smallest k -Edge Connected Spanning Subgraph by LP-Rounding”, Published online in Wiley InterScience (www.interscience.wiley.com), Wiley Periodicals, Inc.
• Jorgen Bang Jensen and Stephan Thomasse, “Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs”, Department of Mathematics and Computer Science, University of Southern Denmark, Denmark.
• Andras Frank and Zoltan Kiraly,”Parity Constrained k-Edge-Connected Orientations”, Springer, Vol. 1610/1999.
• Bill Jackson and Kiyoshi Yoshimoto,”Spanning Even Subgraphs of 3-edge-connected Graphs”, University of London, March 2006.
• Maleq Khan, Gopal Pandurangan and V.S. Anil Kumar, ”A Simple Randomized Scheme for Constructing Low-Weight k-Connected Spanning Subgraphs with Applications to Distributed Algorithms”.
• FENG XUE and P.R. KUMAR, ”The Number of neighbors needed for connectivity of wireless Networks”, Wireless Networks, 169–181, 2004, Kluwer Academic Publishers.
• Maleq Khan, Gopal Pandurangan and V.S. Anil Kumar, ”A Simple Randomized Scheme for Constructing Low-Weight k-Connected Spanning Subgraphs with Applications to Distributed Algorithms”.
• Arun Kumar B. R, Lokanatha C. Reddy, Rajan and Prakash S. Hiremath, ” Route Failure Tolerant Multicast In Mobile Ad Hoc Networks Using Disjoint Minimum Spanning Trees”, the second IEEE ICCSIT 2009, Aug. 8 - 11, 2009, Beijing, China.
• F. Harary, Graph Theory, Narosa Publishing House.
• Patil et al, “Resource Allocation Using Multiple Edge-Sharing Multicast Trees”, Vehicular Technology, IEEE Transactions on Sept. 2008 Vol. 57, PP. 3178 – 3186.
• Arun Kumar B. R, Lokanatha C. Reddy, Prakash S. Hiremath and Rajeswari Sheshadri, ”K-Nodes Multicasting Minimum Cost Spanning Trees In Wireless Mobile Ad Hoc Network (MANET)”, International Journal of Computer Applications [IJCA],www.ijcaonline.org/archives/number4/110-225.
• Arun Kumar B. R, Lokanatha C. Reddy, and Prakash S. Hiremath, ”Route Failure Tolerant Multicast in Mobile Ad Hoc Networks Using Disjoint Minimum Spanning Trees Based on Connectivity Index with Bandwidth constraint”, IEEE 2nd International Conference on Advance Computing Conference, IACC 2010, Tharpur University, Patiala-147004, Punjab.
• Ken-ichi Kawarabayashi and Yusuke Kobayashi, “The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs”, http://www.siam.org/proceedings/soda /2010/SODA10_029_kawarabayashik.pdf.
• M.A.Rajan, M.Girish Chandra, Lokanatha C. Reddy and Prakash S. Hiremath, ”Topological and Energy Analysis of K– Connected MANETs: A Semi-Analytical Approach”, IJCSNS International Journal of Computer Science and Network Security, Vol.8, No.2, PP.199-207, Feb. 2008.

Index Terms

Key words