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

Publication Type:
Conference Proceeding
IEEE INFOCOM 2009, 2009, pp. 2556 - 2560
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013001578OK.pdf484.2 kB
Adobe PDF
In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in wireless multi-hop networks in d (d = 1, 2). We assume that n nodes are randomly, independently 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%) to be 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.
Please use this identifier to cite or link to this item: