Multiple round random ball placement: Power of second chance

In a pioneering work, Gupta and Kumar [8] studied the critical transmission range needed for the connectivity of random wireless networks. Their result implies that, given a square region of n×√ n, the asymptotic number of random nodes (each with transmis-sion range 1) needed to form a connected network is Θ(n lnn) with high probability. This result has been used as cornerstones in deriving a number of asymptotic bounds for random multi-hop wireless networks, such as network capacity [7, 10, 11, 14]. In this paper we show that the asymptotic number of nodes needed for connectivity can be significantly reduced to Θ(n ln lnn) if we are given a “second chance ” to deploy nodes. More generally, under some deployment assumption, if we can deploy nodes in k rounds (for a constant k) and the deployment of the ith round can utilize the information gathered from the previous i − 1 rounds, we show that the number of nodes needed to provide a connected network with high probability isΘ(n ln(k) n). (See Eq (1) for the definition of ln(k) n.) Similar results hold when we need deploy sensors such that the sensing regions of all sensors cover the region of interest