On the Properties of Giant Component in Wireless Multi-Hop Networks

In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in wireless multi-hop networks in R^d (d =1, 2). We assume that n nodes are randomly, in dependently and uniformly distributed in [0, 1]^d, and each node has a uniform transmission range of r = r(n) and any two nodes can communicate directly with each other iff their Euclidean distance is at most r. For d = 1, we derive a closed-form analytical formula for calculating the probability of having a giant component of order above pn with any fixed 0.5 < p ≤ 1. The asymptotic behavior of one dimensional network having a giant component is investigated based on the derived result, which is distinctly different from its two dimensional counterpart. For d = 2, we derive an asymptotic analytical upper bound on the minimum transmission range at which the probability of having a giant component of order above qn for any fixed 0 < q < 1 tends to one as n → ∞. Based on the result, we show that significant energy savings can be achieved if we only require a large percentage of nodes (e.g. 95%)tobe connected rather than requiring all nodes to be connected. The results of this paper are of practical significance in the design and analysis of wireless ad hoc networks and sensor networks.