This paper: The Critical Transmitting Range for Connectivity in Sparce Wireless Ad Hoc Networks P. Santi, D. Blough, IEEE Trans on Mobile Computing, Vol.2,No.1,Jan-Mar 2003, is excellent.
It computes the asymptotic relation between the range r, the length l and the number n of nodes uniformly (randomly) distributed in a square area of side length l with connectivity range r. It establish the value for r for which the graph is connected with high probability, or disconnected with high probability.
The main result is: in one dimension, rn > 2l log(l) ensures connectivity, rn < (1-epsilon) l log(l) ensures disconnectivity.
In higher dimension (2 and 3), connectivity is assured for r^d n > k l^d log(l), with k a constant which depends on the dimension. If r^d n < l^2, then the graph is disconnected.
There is a gap in dimension 2 and 3 wrt the asymptotes. Also, paper conjectures that in dim 1, rn < 2l log(l) should ensure disconnectedness.
Most of the proofs come from a pigeon-hole argument, which is relatively simple and elegant.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment