A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks

Jinhee CHUN  Akiyoshi SHIOURA  Truong MINH TIEN  Takeshi TOKUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1220-1230
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1220
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
geometric routing,  ad hoc network,  greedy routing,  Delaunay graph,  

Full Text: PDF(1.2MB)>>
Buy this Article

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.