Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T18:18:42.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Low degree connectivity of ad-hoc networks via percolation

Part of: Limit theorems Computer system organization Equilibrium statistical mechanics

Published online by Cambridge University Press:  01 July 2016

Emilio De Santis ,
Fabrizio Grandoni  and
Alessandro Panconesi
Emilio De Santis*
Affiliation:
Sapienza University of Rome
Fabrizio Grandoni*
Affiliation:
Sapienza University of Rome
Alessandro Panconesi*
Affiliation:
Sapienza University of Rome
*
∗ Postal address: Department of Mathematics, Sapienza University of Rome, Piazzale Aldo Moro 2, 00185 Rome, Italy. Email address: [email protected]
∗∗ Current address: DISP, Tor Vergata University of Rome, Via del Politecnico 1, 00191 Rome, Italy. Email address: [email protected]
∗∗∗ Postal address: Department of Computer Science, Sapienza University of Rome, Via Salaria 113, 00198 Rome, Italy. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider the following classical problem in ad-hoc networks. Suppose that n devices are distributed uniformly at random in a given region. Each device is allowed to choose its own transmission radius, and two devices can communicate if and only if they are within the transmission radius of each other. The aim is to (quickly) establish a connected network of low average and maximum degree. In this paper we present the first efficient distributed protocols that, in poly-logarithmically many rounds and with high probability, set up a connected network with O(1) average degree and O(log n) maximum degree. Our algorithms are based on the following result, which is a nontrivial consequence of classical percolation theory. Suppose that each device sets up its transmission radius in order to reach the K closest devices. There exists a universal constant K (independent of n) such that, with high probability, there will be a unique giant component (i.e. a connected component of size Θ(n)). Furthermore, all remaining components will be of size O(log2n). This leads to an efficient distributed probabilistic test for membership in the giant component, which can be used in a second phase to achieve full connectivity.

Keywords

Networksconnectivitypercolation

MSC classification

Primary: 68M10: Network design and communication 82B43: Percolation
Secondary: 60F10: Large deviations
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 42 , Issue 2 , June 2010 , pp. 559 - 576
Copyright
Copyright © Applied Probability Trust 2010 

Footnotes

A preliminary version of this work was published in Algorithms - ESA 2007 (Proc. 15th Annual Europ. Symp. Algorithms, 2007; Lecture Notes Comput. Sci. 4698), Springer, Berlin, pp. 206-217.

This work was done when the author was at the Department of Computer Science of Sapienza University.

References

Blough, D. M., Leoncini, M., Resta, G. and Santi, P. (2006). The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks. IEEE Trans. Mobile Computing 5, 1267–1282.Google Scholar
Clementi, A. E. F., Penna, P. and Silvestri, R. (2004). On the power assignment problem in radio networks. Mobile Networks Appl. 9, 125–140.Google Scholar
Deuschel, J.-D. and Pisztora, A. (1996). Surface order large deviations for high-density percolation. Prob. Theory Relat. Fields 104, 467–482.CrossRefGoogle Scholar
Grimmet, G. (1999). Percolation, 2nd edn. Springer, Berlin.CrossRefGoogle Scholar
Hou, T. and Li, V. (1986). Transmission range control in multihop packet radio networks. IEEE Trans. Commun. 34, 38–44.Google Scholar
Kleinrock, L. and Silvester, J. A. (1978). Optimum transmission radii for packet radio networks or why six is a magic number. In Proc. IEEE Nat. Telecommun. Conf. (Birmingham, AL, December 1978), pp. 431–435.Google Scholar
Kucera, L. (2005). Low degree connectivity in ad-hoc networks. In Algorithms – ESA 2005 (Proc. 13th Europ. Symp. Algorithms; Lecture Notes Comput. Sci. 3669), Springer, Berlin, pp. 203–214.Google Scholar
Liggett, T. M., Schonmann, R. H. and Stacey, A. M. (1997). Domination by product measures. Ann. Prob. 25, 71–95.Google Scholar
Ni, J. and Chandler, S. A. G. (1994). Connectivity properties of a random radio network. IEEE Proc. Commun. 141, 289–296.Google Scholar
Takagi, H. and Kleinrock, L. (1984). Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Commun. 32, 246–257.Google Scholar
Xue, F. and Kumar, P. R. (2004). The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10, 169–181.Google Scholar
Zhu, S. Setia, S. and Jajodia, S. LEAP: efficient security mechanisms for large-scale distributed sensor networks. In Proc. 10th ACM Conf. Comput. Commun. Security (Washington, DC, October 2003), ACM, New York, pp. 62–72.Google Scholar