Sharp thresholds for relative neighborhood graphs in wireless Ad Hoc networks

Tsi-Ui Ik*, Peng Jun Wan, Lixin Wang, Chao Min Su

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


In wireless ad hoc networks, relative neighborhood graphs (RNGs) are widely used for topology control. If every node has the same transmission radius, then an RNG can be locally constructed by using only one hop information if the transmission radius is set no less than the largest edge length of the RNG. The largest RNG edge length is called the critical transmission radius for the RNG. In this paper, we consider the RNG over a Poisson point process with mean density n in a unit-area disk. Let β0 = √1/(2/3 - √3/2π) ≈ 1.6. We show that the largest RNG edge length is asymptotically almost surely at most β√lnn/πn for any fixed β > β0 and at least β√lnn/πn for any fixed β < β0. This implies that the threshold width of the critical transmission radius is o(√lnn/n). In addition, we also prove that for any constant ξ, the expected number of RNG edges whose lengths are not less than β0√lnn+ξ/πn is asymptotically equal to β02/2 e

Original languageEnglish
Article number5403542
Pages (from-to)614-623
Number of pages10
JournalIEEE Transactions on Wireless Communications
Issue number2
StatePublished - 1 Feb 2010


  • Critical transmission radii
  • Poisson point processes
  • Relative neighborhood graphs
  • Thresholds
  • Wireless ad hoc networks

Fingerprint Dive into the research topics of 'Sharp thresholds for relative neighborhood graphs in wireless Ad Hoc networks'. Together they form a unique fingerprint.

Cite this