TY - GEN

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

AU - Ta, Xiaoyuan

AU - Mao, Guoqiang

AU - Anderson, Brian D.O.

PY - 2009

Y1 - 2009

N2 - In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in wireless multi-hop networks in Rd (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.

AB - In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in wireless multi-hop networks in Rd (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.

UR - http://www.scopus.com/inward/record.url?scp=70349663854&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2009.5062186

DO - 10.1109/INFCOM.2009.5062186

M3 - Conference contribution

SN - 978-1-4244-3512-8

T3 - Proceedings - IEEE INFOCOM

SP - 2556

EP - 2560

BT - IEEE INFOCOM 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 28th Conference on Computer Communications, IEEE INFOCOM 2009

Y2 - 19 April 2009 through 25 April 2009

ER -