TY - JOUR

T1 - On the Phase Transition Width of K-Connectivity in Wireless Multihop Networks

AU - Ta, Xiaoyuan

AU - Mao, Guoqiang

AU - Anderson, Brian D.O.

PY - 2009/7

Y1 - 2009/7

N2 - In this paper, we study the phase transition behavior of k-connectivity (k=1,2,\ldots) in wireless multihop networks where a total of n nodes are randomly and independently distributed following a uniform distribution in the unit cube [0,1]d (d=1,2,3), and each node has a uniform transmission range r(n). It has been shown that the phase transition of k-connectivity becomes sharper as the total number of nodes n increases. In this paper, we investigate how fast such phase transition happens and derive a generic analytical formula for the phase transition width of k-connectivity for large enough n and for any fixed positive integer k in d-dimensional space by resorting to a Poisson approximation for the node placement. This result also applies to mobile networks where nodes always move randomly and independently. Our simulations show that to achieve a good accuracy, n should be larger than 200 when k=1 and d=1; and n should be larger than 600 when k ≤ 3 and d=2, 3. The results in this paper are important for understanding the phase transition phenomenon; and it also provides valuable insight into the design of wireless multihop networks and the understanding of its characteristics.

AB - In this paper, we study the phase transition behavior of k-connectivity (k=1,2,\ldots) in wireless multihop networks where a total of n nodes are randomly and independently distributed following a uniform distribution in the unit cube [0,1]d (d=1,2,3), and each node has a uniform transmission range r(n). It has been shown that the phase transition of k-connectivity becomes sharper as the total number of nodes n increases. In this paper, we investigate how fast such phase transition happens and derive a generic analytical formula for the phase transition width of k-connectivity for large enough n and for any fixed positive integer k in d-dimensional space by resorting to a Poisson approximation for the node placement. This result also applies to mobile networks where nodes always move randomly and independently. Our simulations show that to achieve a good accuracy, n should be larger than 200 when k=1 and d=1; and n should be larger than 600 when k ≤ 3 and d=2, 3. The results in this paper are important for understanding the phase transition phenomenon; and it also provides valuable insight into the design of wireless multihop networks and the understanding of its characteristics.

KW - Average node degree

KW - Connectivity

KW - K-connectivity

KW - Phase transition width

KW - Random geometric graph

KW - Transmission range

KW - Wireless multihop networks

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

U2 - 10.1109/TMC.2008.170

DO - 10.1109/TMC.2008.170

M3 - Article

SN - 1536-1233

VL - 8

SP - 936

EP - 949

JO - IEEE Transactions on Mobile Computing

JF - IEEE Transactions on Mobile Computing

IS - 7

ER -