TY - GEN

T1 - Improved asymptotic bounds on critical transmission radius for greedy forward routing in wireless ad hoc networks

AU - Wang, Lixin

AU - İk, Tsì-Uí

AU - Yao, Frances

PY - 2008

Y1 - 2008

N2 - Consider a random wireless ad hoc network represented by a Poisson point process over a unit-area disk with mean n. Let σn denote its critical transmission radius for greedy forward routing, and β0 = 1/ (2/3 - √3/2π) ≈ 1.62. It was recently proved that for any constant ε > 0, it is asymptotically almost sure that (1 - ε) √β0 ln n/π n ≤ σn ≤ (1 + ε) √β0 ln n/π n. In this paper, we obtain tighter asymptotic bounds on σn. Specifically, we prove that for any constant c, the asymptotic probability of σn ≤ √β0 ln n+c/π n is at least 1 - (1/1/β0- 1/3 - β0/2)e-c and at most e -β0/2 e-c. Consequently, for any positive sequence (ξn : n ≥ 1) with ξn = o(ln n) and ξn → ∞, it is asymptotically almost sure that √β0 ln n-ξn/π n ≤ σn ≤ √β0 ln n+ξn/π n. We also conjecture that for any constant c, the asymptotic probability of σn ≤ √β0 ln n+c/π n is exactly exp (- (1/1/β 0-1/3 - β0/2) e-c).

AB - Consider a random wireless ad hoc network represented by a Poisson point process over a unit-area disk with mean n. Let σn denote its critical transmission radius for greedy forward routing, and β0 = 1/ (2/3 - √3/2π) ≈ 1.62. It was recently proved that for any constant ε > 0, it is asymptotically almost sure that (1 - ε) √β0 ln n/π n ≤ σn ≤ (1 + ε) √β0 ln n/π n. In this paper, we obtain tighter asymptotic bounds on σn. Specifically, we prove that for any constant c, the asymptotic probability of σn ≤ √β0 ln n+c/π n is at least 1 - (1/1/β0- 1/3 - β0/2)e-c and at most e -β0/2 e-c. Consequently, for any positive sequence (ξn : n ≥ 1) with ξn = o(ln n) and ξn → ∞, it is asymptotically almost sure that √β0 ln n-ξn/π n ≤ σn ≤ √β0 ln n+ξn/π n. We also conjecture that for any constant c, the asymptotic probability of σn ≤ √β0 ln n+c/π n is exactly exp (- (1/1/β 0-1/3 - β0/2) e-c).

KW - Greedy forward routing

KW - Random deployment

KW - Wireless ad hoc networks

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

U2 - 10.1145/1374618.1374637

DO - 10.1145/1374618.1374637

M3 - Conference contribution

AN - SCOPUS:57349102887

SN - 9781605580739

T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

SP - 131

EP - 137

BT - Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08

T2 - 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08

Y2 - 26 May 2008 through 30 May 2008

ER -