Delivery Guarantee of Greedy Routing in Three Dimensional Wireless Networks

Abstract

In this paper, we investigate how to design greedy routing to guarantee packet delivery in a three-dimensional (313) 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 is process of density n over a convex compact region of unit volume, 3 root 3 beta(0)1n n/4 pi n is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for 3D greedy routing, where beta(0) = 3.2. We also conduct extensive simulations to confirm our theoretical results.