ON SOME CURRENT RESULTS OF GRAPH THEORY FOR AD-HOC NETWORKS

Authors

  • GIUSEPPE DE MARCO Department of Communication and Information Engineering, Fukuoka Institute of Technology (FIT), 3-30-1 Wajiro-higashi, Higashi-ku, Fukuoka 811-0295, Japan
  • LEONARD BAROLLI Department of Communication and Information Engineering, Fukuoka Institute of Technology (FIT), 3-30-1 Wajiro-higashi, Higashi-ku, Fukuoka 811-0295, Japan

Keywords:

Wireless networks, ad-hoc networks, graph theory, sensor networks

Abstract

The goal of this paper is twofold. Firstly, we present results from graph-theory which can be used to understand the fundamental properties of ad-hoc networks and wireless sensor networks. Graph-theory is a well studied branch of discrete mathematics, and it has been applied in many knowledge fields, e.g. social network, Internet tomography and epidemiology. We review literature results from the point of view of the designer of an ad-hoc network, who must set simulation parameters in order to predict the behaviour of the real network. Secondly, we study the impact of the asymmetries of radio links on the connectivity properties of an ad-hoc network. To the best knowledge of the author, this further hypothesys has been addressed in the case of geometric random graph only, but not for radio models with randomnesses. As expected, we found that randomness in the radio model directly affects the distribution of the asymmetries and the connectivity properties. This result can be very useful in the understanding of more complicated aspects of ad-hoc nets, like routing and coordinated wake-up in power saving techniques.

 

Downloads

Download data is not yet available.

References

M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs,

and Mathematical Tables. Dover Publications, 1970.

R. Albert and A.-L. Barab´asi. Statistical mechanics of complex networks. Reviews of Modern

Physics, 74:47–97, 2002.

C. Bettstetter. Failure-resilient ad hoc and sensor networks in a shadow fading environment. In

Proceedings IEEE/IFIP Intern. Conf. on Dependable Systems and Networks (DSN), Workshop on

Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS), page 900,

June 2004.

B. Bollobas. Random Graph. Academic Press, 1985.

I. Carreras, I. Chlamtac, H. Woesner, and C. Kiraly. Bionets: Bio-inspired next generation networks.

In Lecture Notes in Computer Science, volume 3457, pages 245 – 252, July 2005.

A. Cerpa, J. L. Wong, L. Kuang, M. Potkonjak, and Deborah Estrin. Statistical model of lossy

links in wireless sensor networks. In ACM/IEEE Fourth International Conference on Information

Processing in Sensor Networks (IPSN05), pages 81–88, April 2005.

S.N. Dorogovtsev and J.F.F. Mendes. Evolution of Networks: From Biological Nets to the Internet

and WWW. Oxford University Press, Oxford, January 2003.

P. Erd¨os and A. R´eny. On the evolution of random graphs. Pubblication of the Mathematical

Institute of the Hungarian Academy of Science, 5:17–61, 1960.

E. N. Gilbert. Random plane networks. Journal of SIAM, 9(4):533–543, December 1961.

P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks.

Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming,

pages 547–566, 1998.

R. Hekmat and P. Van Mieghem. Study of connectivity in wireless ad-hoc networks with an

improved radio model. In Proceedings of the Second Workshop on Modeling and Optimization in

Mobile, Ad Hoc and Wireless Networks (WiOpt’04).

D. M. Johnson, A. L. Dulmage, and N. S. Mendelsohn. Connectivity and reducibility of graph.

Canad. J. Math., 14:529–539, 1962.

D. Miorandi and E. Altman. Coverage and connectivity of ad hoc networks in presence of channel

randomness. In Proceedings of IEEE INFOCOM 2005, volume 1, pages 491–502, 2005.

Bojan Mohar. The laplacian spectrum of graphs, volume 2 of Graph Theory, Combinatorics, and

Applications. Wiley, 1991.

T. Moscibroda and R. Wattenhofer. The complexity of connectivity in wireless networks. In

Proceedings of INFOCOM 2006, 2006.

M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distribution

and their applications. Phys. Rev., 2001.

J. Orriss and S. K. Barton. Probability distributions for the number of radio tranceivers which

can communicate with one another. IEEE Transaction on Communications, 51(4):676–681, April

M. D. Penrose. On k-connectivity for a geometric random graph. Random Structures and Algorithms,

:145–164, 1999.

M. D. Penrose. Random Geometric Graphs. Oxford University Press, Oxford, UK, 2003.

A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Transactions

on Mathematical Software, 16(4):303–324, 1990.

T.S. Rappaport. Wireless Communications. Prentice Hall PTR, 2001.

G. W.-Allen, G. Tewari, A. Patel, M. Welsh, and R. Nagpal. Firefly-inspired sensor network

synchronicity with realistic radio effects. In SenSys ’05: Proceedings of the 3rd international

conference on embedded networked sensor systems, pages 142–153, New York, NY, USA, 2005.

ACM Press.

Q. Zhao and L. Tong. Energy efficiency of large-scale wireless networks: Proactive versus reactive

networking. IEEE Journal on Selected Areas in Communications, 23(5):1100–1112, May 2005.

Downloads

Published

2006-05-23

Issue

Section

Articles

Most read articles by the same author(s)

1 2 > >>