A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks
A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks
复制标题
DOI：
10.1007/978-3-642-36092-3_7
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Jinhee Chun;A. Shioura;Truong Minh Tien;T. Tokuyama
中科院分区：
文献类型：
--
作者：
Jinhee Chun;A. Shioura;Truong Minh Tien;T. Tokuyama
我们给出了一个统一的观点，贪婪的几何路由算法在ad hoc网络。为此，我们首先提出了一种一般形式的贪婪路由算法，使用一类目标函数，这是不变的一致变换下的点集。我们表明，几个已知的贪婪路由算法，如贪婪路由，罗盘路由，和中点路由可以被视为广义贪婪路由算法的特殊情况。此外，受贪婪路由统一观点的启发，我们提出了三种新的贪婪路由算法。然后，我们推导出一个充分条件，我们的广义贪婪路由算法，以保证每个Delaunay图上的数据包传输。这个条件使得检查给定的路由算法是否保证数据包的传递变得容易，并且它在目标函数的凸线性组合下是封闭的。结果表明，贪婪路由算法、中点路由算法和本文提出的三种新的贪婪路由算法满足充分条件，即，它们保证在Delaunay图上的分组传递。我们还讨论了这些方法的优点和缺点。
We give a unified view to greedy geometric routing algorithms in ad hoc networks. For this, we first present a general form of greedy routing algorithm using a class of objective functions which are invariant under congruent transformations of a point set. We show that several known greedy routing algorithms such as Greedy Routing, Compass Routing, and Midpoint Routing can be regarded as special cases of the generalized greedy routing algorithm. In addition, inspired by the unified view of greedy routing, we propose three new greedy routing algorithms. We then derive a sufficient condition for our generalized greedy routing algorithm to guarantee packet delivery on every Delaunay graph. This condition makes it easier to check whether a given routing algorithm guarantees packet delivery, and it is closed under convex linear combination of objective functions. It is shown that Greedy Routing, Midpoint Routing, and the three new greedy routing algorithms proposed in this paper satisfy the sufficient condition, i.e., they guarantee packet delivery on Delaunay graphs. We also discuss merits and demerits of these methods.