Sharp thresholds for relative neighborhood graphs in wireless Ad Hoc networks
- 5 February 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Wireless Communications
- Vol. 9 (2) , 614-623
Abstract
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 ¿ 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 ß ¿(1n n/¿n) for any fixed ß > ß0 and at least ß ¿(1n n/¿n) for any fixed ß < ß0. This implies that the threshold width of the critical transmission radius is o (¿(1n n/n)). In addition, we also prove that for any constant ¿, the expected number of RNG edges whose lengths are not less than ß0 ¿(1n n+¿)/¿n is asymptotically equal to ß02/2 e-¿.Keywords
This publication has 13 references indexed in Scilit:
- Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks2006
- On the Spanning Ratio of Gabriel Graphs and beta-SkeletonsSIAM Journal on Discrete Mathematics, 2006
- Geometrically aware communication in random wireless networks2004
- Sharp thresholds For monotone properties in random geometric graphs2004
- Routing with Guaranteed Delivery in Ad Hoc Wireless NetworksWireless Networks, 2001
- GPSR2000
- The longest edge of the random minimal spanning treeThe Annals of Applied Probability, 1997
- The limit distribution of the largest nearest-neighbour link in the unit d-cubeJournal of Applied Probability, 1989
- Connectivity properties of a packet radio network modelIEEE Transactions on Information Theory, 1989
- The relative neighbourhood graph of a finite planar setPattern Recognition, 1980