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 Theta(n)). Furthermore, all remaining components will be of size O (log(2) n). 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.
LOW DEGREE CONNECTIVITY OF AD-HOC NETWORKS VIA PERCOLATION / DE SANTIS, Emilio; Fabrizio, Grandoni; Panconesi, Alessandro. - In: ADVANCES IN APPLIED PROBABILITY. - ISSN 0001-8678. - STAMPA. - 42:2(2010), pp. 559-576. [10.1239/aap/1275055242]
LOW DEGREE CONNECTIVITY OF AD-HOC NETWORKS VIA PERCOLATION
DE SANTIS, Emilio;PANCONESI, Alessandro
2010
Abstract
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 Theta(n)). Furthermore, all remaining components will be of size O (log(2) n). 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.