Abstract
In this paper we analyze connectivity issues in one-dimensional ad hoc networks. Starting with a deterministic channel model, we show how an equivalent GI|D|∞ queueing model may be used to address network connectivity. In this way, we obtain exact results for the coverage probability, the node isolation probability and the connectivity distance for various node placement statistics. We then show how a GI|G|∞ model may be used to study broadcast percolation problems in ad hoc networks with general node placement in the presence of fading channels. In particular, we obtain explicit results for the case of nodes distributed according to a Poisson distribution operating in a fading/shadowing environment. In the latter case, heavy traffic theorems are applied to derive the critical transmission power for connectivity and broadcast percolation distance in highly dense networks. The impact of signal processing schemes able to exploit the diversity provided by small-scale fading by means of multiple antennas is considered. The analysis is then extended to the case of unreliable ad hoc networks, with an in-depth discussion of asymptotic results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Gupta and P. R. Kumar, “Critical power for asymptotic connectivity,” in Proc. of IEEE CDC, Tampa, USA, 1998.
P. Santi and D. M. Blough, “The critical transmitting range for connectivity in sparse wireless ad hoc networks,” IEEE Trans. on Mob. Comp., vol. 2, no. 1, pp. 25–39, Jan—Mar 2003.
O. Dousse, P. Thiran, and M. Hasler, “Connectivity in ad—hoc and hybrid networks,” in Proc. of IEEE INFOCOM, New York, USA, 2002.
O. Dousse, F. Baccelli, and P. Thiran, “Impact of interferences on connectivity in ad—hoc networks,” in Proc. of IEEE INFOCOM, San Francisco, USA, 2003.
P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. on Inf. Th., vol. 46, no. 2, pp. 388–404, Mar. 2000.
A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah, “Throughput-delay trade-off in wireless networks,” in Proc. of IEEE INFOCOM, Hong Kong, 2004.
S. R. Kulkarni and P. Viswanath, “A deterministic approach to throughput scaling in wireless networks.” IEEE Trans. on Inf. Th., vol. 50, no. 6, pp. 1041–1049, Jun. 2004.
A. Rajeswaran and R. Negi, “Capacity of power constrained ad-hoc networks,” in Proc. of IEEE INFOCOM, Hong Kong, 2004.
A. Jovicic, P. Viswanath, and S. R. Kulkarni, “Upper bounds to transport capacity of wireless networks,” IEEE Trans. on Inf. Th., vol. 50, no. 11, pp. 2555–2565, Nov. 2004.
M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, “On the throughput capacity of random wireless networks,” 2004, subm. for publ.
O. Dousse and P. Thiran, “Connectivity vs capacity in dense ad hoc networks,” in Proc. of IEEE INFOCOM, Hong Kong, 2004.
M. Desai and D. Manjunath, “On the connectivity in finite ad hoc networks,” IEEE Comm. Lett., vol. 6, no. 10, pp. 437–439, Oct 2002.
P. Panchapakesan and D. Manjunath, “On the transmission range in dense ad hoc radio networks,” in Proc. of SPCOM, Bangalore, India, 2001.
R. Hekmat and P. Van Mieghem, “Study of connectivity in wireless ad—hoc networks with an improved radio model,” in Proc. of WiOpt, Cambridge, UK, 2004.
M. Franceschetti, L. Booth, J. Bruck, M.Cook, and R. Meester, “Continuum percolation with unreliable and spread out connections,” Journal of Statistical Physics, vol. 118, no. 3/4, pp. 721–734, Feb. 2005.
D. Miorandi and E. Altman, “Coverage and connectivity of ad-hoc networks in presence of channel randomness,” INRIA, Tech. Rep. RR5377, 2004. [Online]. Available: http://www.inria.fr/rrrt/rr-5377.html
P. Santi, “The critical transmitting range for connectivity in mobile ad hoc networks,” IEEE Trans. on Mob. Comp., vol. 4, no. 2, pp. 310–317, Mar. 2005.
P. Hall, Introduction to the theory of coverage processes. New York: J. Wiley and sons, 1988.
S. Shakkottai, R. Srikant, and N. B. Shroff, “Unreliable sensor grids: coverage, connectivity and diameter,” in Proc. of IEEE INFOCOM, San Francisco, CA, 2003.
L. Liu and D.-H. Shi, “Busy period in GIX|G|∟,” J. Appl. Prob., vol. 33, pp. 815–829, 1996.
J. Abate, G. L. Choudhury, and W. Whitt, “An introduction to numerical transform inversion and its application to probability models,” in Computational Probability, W. Grassman, Ed. Boston: Kluwer, 1999, pp. 257–323.
W. Stadje, “The busy period of the queueing system M|G|∟,” J. Appl. Prob., vol. 22, pp. 697–704, 1985.
P. Hall, “Heavy traffic approximations for busy period in an M|G|∟ queue,” Stochastic Processes and their Applications, vol. 19, pp. 259–269, 1985.
Y.-C. Cheng and T. G. Robertazzi, “Critical connectivity phenomena in multihop radio models,” IEEE Trans.Comm., vol. 37, no. 7, pp. 770–777, Jul 1989.
F. Baccelli and P. Bremaud, Elements of Queueing Theory. Berlin: Springer—Verlag, 1994.
L. Hanzo, C. H. Wong, and M. S. Yee, Adaptive Wireless Transceivers. New York: John Wiley and Sons, 2002.
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products. Orlando: Academic Press, 1983.
T. S. Rappaport, Wireless Communications. Upper Saddle River, New Jersey: Prentice Hall, 1999.
C. Bettstetter and C. Hartmann, “Connectivity of wireless multihop networks in a shadow fading environment,” in Proc. of ACM MSWiM, San Diego, CA, 2003.
D. Stoyan, Comparison Methods for Queues and Other Stochasti Models. New York: John Wiley & Sons, 1983.
S. M. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J. Sel. Areas on Comm., vol. 16, no. 8, pp. 1451–1458, Oct. 1998.
E. Altman, “On stochastic recursive equations and infinite server queues,” in Proc. of IEEE INFOCOM, Miami, 2005.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the EURO NGI Network of Excellence. The work of D. Miorandi was partially supported by Fond. A. Gini. This work has been done while D. Miorandi, at that time with University of Padova (Italy), was visiting the MAESTRO project at INRIA Sophia Antipolis.
Daniele Miorandi received his “Laurea” (summa cum laude) and Ph.D. degrees from Univ. of Padova (Italy) in 2001 and 2005, respectively. He currently holds a post-doc position at CREATE-NET, Trento (Italy). In 2003/04 he spent 12 months of his doctoral thesis visiting the MAESTRO team at INRIA Sophia Antipolis (France). His research interests include stochastic modelling, performance evaluation and protocols design for wireless networks.
Eitan Altman received the B.Sc. degree in electrical engineering (1984), the B.A. degree in physics (1984) and the Ph.D. degree in electrical engineering (1990), all from the Technion-Israel Institute, Haifa. In (1990) he further received his B.Mus. degree in music composition in Tel-Aviv university. Since 1990, he has been with INRIA (National research institute in informatics and control) in Sophia-Antipolis, France. His current research interests include performance evaluation and control of telecommunication networks and in particular congestion control, wireless communications and networking games. He is in the editorial board of several scientific journals: Stochastic Models, JEDC, COMNET, SIAM SICON and WINET. He has been the (co)chairman of the program committee of several international conferences and workshops (on game theory, networking games and mobile networks). More informaion can be found at http://www.inria.fr/mistral/personnel/Eitan.Altman/me.html
Rights and permissions
About this article
Cite this article
Miorandi, D., Altman, E. Connectivity in one-dimensional ad hoc networks: A queueing theoretical approach. Wireless Netw 12, 573–587 (2006). https://doi.org/10.1007/s11276-006-6536-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11276-006-6536-z