ON SOME CURRENT RESULTS OF GRAPH THEORY FOR AD-HOC NETWORKS
Keywords:
Wireless networks, ad-hoc networks, graph theory, sensor networksAbstract
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
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.
