Efficient Geometric Routing in Three Dimensional Ad Hoc Networks
Efficient Geometric Routing in Three Dimensional Ad Hoc Networks
复制标题
DOI：
10.1109/infcom.2009.5062225
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Cong Liu;Jie Wu
中科院分区：
文献类型：
--
作者：
Cong Liu;Jie Wu
高效的几何路由算法已经在二维ad hoc网络或简单的2D网络中得到了广泛的研究。这些算法是有效的，并且已被证明是最坏情况下的最佳局部路由算法。然而，很少有现有的工作集中在3D网络中的有效的几何路由，由于缺乏一个有效的方法来限制搜索，一旦贪婪路由算法遇到局部最小值，如在2D网络中的面路由。在本文中，我们解决的问题，有效的几何路由在3D网络。我们提出了路由的船体，一个3D模拟面路由，并提出了第一个3D部分单位Delaunay三角剖分（PUDT）算法将整个网络空间划分为一些封闭的子空间。所提出的贪婪-船体-贪婪（GHG）路由是有效的，因为它将局部最小值恢复过程从整个网络限制到仅一个子空间的表面结构（船体）。
Efficient geometric routing algorithms have been studied extensively in two-dimensional ad hoc networks, or simply 2D networks. These algorithms are efficient and they have been proven to be the worst-case optimal, localized routing algorithms. However, few prior works have focused on efficient geometric routing in 3D networks due to the lack of an efficient method to limit the search once the greedy routing algorithm encounters a local-minimum, like face routing in 2D networks. In this paper, we tackle the problem of efficient geometric routing in 3D networks. We propose routing on hulls, a 3D analogue to face routing, and present the first 3D partial unit Delaunay triangulation (PUDT) algorithm to divide the entire network space into a number of closed subspaces. The proposed greedy- hull-greedy (GHG) routing is efficient because it bounds the local- minimum recovery process from the whole network to the surface structure (hull) of only one of the subspaces.