Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We lay down the foundations of a new approach for the scalable analysis of ad hoc networks, with special regard to the properties of the random network topology. The proposed methodology is rooted in the theory of random graphs, but we significantly extend the conventional random graph model, as in its original form it would be too "sterile" to capture realistic ad hoc networks. We analyze some fundamental properties of the proposed new, general model and demonstrate that it is capable of solving analysis/design problems which would otherwise be difficult to capture.

REFERENCES

• 1: M.J.B. Appel and R.P. Russo, "The Maximum Vertex Degree of a Graph on Uniform Points in {0,1}d", Adv. Appl. Prob., 29(1997), pp. 567-581.
• 2: S. Basagni, I. Chlamtac, A. Faragó, V.R. Syrotiuk and R. Talebi, "Route Selection in Mobile Multimedia Ad Hoc Networks", Sixth IEEE International Workshop on Mobile Multimedia Communications (MOMUC'99), San Diego, CA, Nov. 15--17, 1999.
• 3: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 4: B. Bollob´s, Random Graphs, Academic Press, London, UK, 1985.
• 5: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 6: A. Faragó, "Almost Surely Almost ExactOptimization in Random Graphs", Technical Report, Dept. of Comp. Sci., The University of Texas at Dallas, Oct 2000.
• 7: Alan Frieze , Colin McDiarmid, Algorithmic theory of random graphs, Random Structures & Algorithms, v.10 n.1-2, p.5-42, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.0.CO;2-Z]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 10: P. Jacquet and A. Laouiti, "Analysis of Mobile Ad Hoc Network Routing Protocols in Random Graph Models", MOBICOM'2000 (See also INRIA Research Report #3835).
• 11: S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley-Interscience, 2000.
• 12: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 13: Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, Cornell University, Ithaca, NY, 1999
• 14: A.B. McDonald and T. Znati, "A Path Availability Model for Wireless Ad-Hoc Networks", IEEE Wrireless Communications and Networking Conference (WCNC'99), New Orleans, LA, Sep. 21-24, 1999.
• 15: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 16: T.K. Philips, S.S. Panwar and A.N. Tantawi, "Connectivity Properties of a Packet Radio Model", IEEE Trans. Inf. Theory, 35(1989), pp. 1044--1046.
• 17: Ellen W. Zegura , Kenneth L. Calvert , Michael J. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.770-783, Dec. 1997 [doi>10.1109/90.650138]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Design, Theory

Keywords:
ad hoc network, random graph model, random network topology