TY - GEN
T1 - Delivery guarantee of greedy routing in three dimensional wireless networks
AU - Wang, Yu
AU - Yi, Chih Wei
AU - Li, Fan
PY - 2008
Y1 - 2008
N2 - In this paper, we investigate how to design greedy routing to guarantee packet delivery in a three-dimensional (3D) network. In 2D networks, many position-based routing protocols apply face routing on planar routing structure as a backup method to guarantee packet delivery when greedy routing fails at local minimum. However, in 3D networks, no planar topology can be constructed anymore. Even worse, a recent result [6] showed that there is no deterministic localized routing algorithm that guarantees the delivery of packets in 3D networks. Therefore, we propose to set up the transmission radius large enough to eliminate local minimum in the 3D network. In particular, we study the asymptotic critical transmission radius for greedy routing to ensure the packet delivery in randomly deployed 3D networks. Using similar techniques in [12], we theoretically prove that for a 3D network, formed by nodes that are produced by a Poisson point process of density n over a convex compact region of unit volume, 3√3β0 ln n/4πn is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for 3D greedy routing, where β0 = 3.2. We also conduct extensive simulations to confirm our theoretical results.
AB - In this paper, we investigate how to design greedy routing to guarantee packet delivery in a three-dimensional (3D) network. In 2D networks, many position-based routing protocols apply face routing on planar routing structure as a backup method to guarantee packet delivery when greedy routing fails at local minimum. However, in 3D networks, no planar topology can be constructed anymore. Even worse, a recent result [6] showed that there is no deterministic localized routing algorithm that guarantees the delivery of packets in 3D networks. Therefore, we propose to set up the transmission radius large enough to eliminate local minimum in the 3D network. In particular, we study the asymptotic critical transmission radius for greedy routing to ensure the packet delivery in randomly deployed 3D networks. Using similar techniques in [12], we theoretically prove that for a 3D network, formed by nodes that are produced by a Poisson point process of density n over a convex compact region of unit volume, 3√3β0 ln n/4πn is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for 3D greedy routing, where β0 = 3.2. We also conduct extensive simulations to confirm our theoretical results.
UR - https://www.scopus.com/pages/publications/56749178746
U2 - 10.1007/978-3-540-88582-5_4
DO - 10.1007/978-3-540-88582-5_4
M3 - Conference contribution
AN - SCOPUS:56749178746
SN - 3540885811
SN - 9783540885818
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 4
EP - 16
BT - Wireless Algorithms, Systems, and Applications - Third International Conference, WASA 2008, Proceedings
PB - Springer Verlag
T2 - 3rd International Conference on Wireless Algorithms, Systems, and Applications, WASA 2008
Y2 - 26 October 2008 through 28 October 2008
ER -