4. Giant Component in Large Wireless Networks

In this chapter, we study the giant component, the largest component containing a nonvanishing fraction of nodes, in large wireless networks in both one-dimensional and two-dimensional space. Specifically, consider a network with a total of n nodes randomly, independently, and uniformly distributed in a unit interval or unit square. For one-dimensional networks, 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 then investigated, which is distinctly different from its two-dimensional counterpart. For two-dimensional networks, 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 → ∞. Using the result, we show that significant energy savings can be achieved if we only require a large percentage of nodes (e.g., 95%, 99%) to be connected rather than requiring all nodes to be connected. That is, with a slightly relaxed requirement on connectivity, substantial energy savings can be achieved for a large network. For one-dimensional space, we study the network assuming the unit disk connection model. For two-dimensional space, we first consider the unit disk connection model and then discuss how results obtained assuming the unit disk connection model can be extended to more general connection models.