>>>> Poster
As is it an essential feature, connectivity has received quite a lot of attention in the previous decade already, in the context of packet radio networks, and has gained renewed interest recently in the context of ad-hoc and sensor networks.
Most results apply to the full connectivity of a network made of a finite number of nodes. A recursive formula giving
the average number of hops between two connected nodes is found
in [2], whereas the probability that
a given number of nodes on a finite interval are all connected is computed in [3].
In the 2-dim. setting, relations between k-connectivity and the node degree are studied
in [4]. When the number of nodes N tend to infinity, and when the distance r below which nodes can connect decreases at a rate slower than sqrt(log(N)/N), Gupta and Kumar have proven that all nodes are almost surely connected [5].
We assume here that the number N of nodes is not fixed nor on a finite area, but that they are given as points of a Poisson process over the plane. We do not make assumptions on its intensity l, so that our results also apply to low density areas. Since the number of nodes is not bounded, some of them will be disconnected. The problem is then related to percolation theory[6, 7]. The percolation probability is the probability that an arbitrary node will belong to a cluster of infinite size (and thus that an arbitrary terminode can be connected to another terminode arbitrarily far away). Assuming that the radii r are constant and identical, the main results of percolation theory is that there exists a finite, positive value lc of l, under which the percolation probability is zero (sub-critical phase) and above which it is non zero (super-critical phase). In the sub-critical phase, all clusters are almost surely finite, and their size has is a random variable whose distribution has an exponentially decreasing tail. In the super-critical phase, the percolation probability usually increases quite rapidly with l.
The exact value of this probability is still an open problem, some bounds on the critical intensity lc below which it is zero have been obtained in [7, 8, 9]. Instead of varying l, we can also vary r: the phase transition occurs then at critical radius rc depending on l.
The structure of the graph G(l,r) derived from the Boolean model is shown below, for two different values of r. The first one is slightly lower than the critical value rc, whereas the second one is slightly larger. If you observe closely both figures, you will notice that only a few edges (in black on the second figure) have been created by a slight increase of the radius, but that these few edges connect most the colored clusters into one large cluster (theoretically of infinite size).
Because of this percolation phenomenon, there is no benefit in adding a sparse network of base stations in terms of connectivity in the super-critical case. In the sub-critical case, the benefit remains marginal, unless the nodes spatial distribution is close to 1-dimensional. The 1-dim case is indeed completely different: percolation never occurs for finite values of lr. As a result, long distance connectivity in multiple hops is impossible. This makes the introduction of a sparse network of base stations, say one base station every L distance units, very beneficial, even when r is much smaller than L. We have obtained analytical bounds on the probability that an arbitrary node remains unconnected in [1].
People
Publications
[1] O. Dousse, P. Thiran and M. Hasler, `Connectivity in ad-hoc and hybrid networks' in Proc. INFOCOM, New York, June 2002.
References
[2] Y.-C. Cheng and T. G. Robertazzi, `Critical Connectivity Phenomena in Multihop Radio Models,' in IEEE Trans. on Communications, pp. 770-777, vol. 37, July 1989.
[3] P. Santi and D. M. Blough, `An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks,' in Proc. IEEE DSN, Washington DC, pp. 89-98, June 2002. (PDF)
[4] C. Bettstetter, `On the Minimum Node Degree and Connectivity of a Wireless Multihop Network,' in Proc. MobiHoc, Lausanne, June 2002.
[5] P. Gupta and P. R. Kumar, `Critical Power for Asymptotic Connectivity in Wireless Networks,' pp. 547-566, in Stochastic Analysis, Control, Optimization and Applications : A Volume in Honor of W.H. Fleming.
Edited by W.M. McEneany, G. Yin, and Q. Zhang, Birkhauser, Boston, 1998. (PDF)
[6] G. Grimmett, Percolation, Springer, 1999.
[7] R. Meester and R. Roy, Continuum percolation,
Cambridge University Press, Cambridge, 1996.
[8] E. N. Gilbert, `Random plane networks,' SIAM J., vol 9, pp. 533-543, 1961.
[9] T.K. Philips, S.S. Panwar and A.N. Tantawi, `Connectivity Properties of a Packet Radio Network Model,' IEEE Transactions on Information Theory, Vol. 35, pp. 1044-1047, September 1989.
