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

Jinhee CHUN; Akiyoshi SHIOURA; Truong MINH TIEN; Takeshi TOKUYAMA

doi:10.1587/transfun.E97.A.1220

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

Jinhee CHUN, Akiyoshi SHIOURA, Truong MINH TIEN, Takeshi TOKUYAMA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1220-1230

Publication Date: 2014/06/01

Publicized

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)

Category

Authors

Jinhee CHUN
  Tohoku University
Akiyoshi SHIOURA
  Tohoku University,Kawarabayashi Large Graph Project
Truong MINH TIEN
  Tohoku University
Takeshi TOKUYAMA
  Tohoku University,Kawarabayashi Large Graph Project

Keyword

geometric routing, ad hoc network, greedy routing, Delaunay graph

Cite this

Copy

Jinhee CHUN, Akiyoshi SHIOURA, Truong MINH TIEN, Takeshi TOKUYAMA, "A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1220-1230, June 2014, doi: 10.1587/transfun.E97.A.1220.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1220/_p

Copy

@ARTICLE{e97-a_6_1220,
author={Jinhee CHUN, Akiyoshi SHIOURA, Truong MINH TIEN, Takeshi TOKUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks},
year={2014},
volume={E97-A},
number={6},
pages={1220-1230},
abstract={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.},
keywords={},
doi={10.1587/transfun.E97.A.1220},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1220
EP - 1230
AU - Jinhee CHUN
AU - Akiyoshi SHIOURA
AU - Truong MINH TIEN
AU - Takeshi TOKUYAMA
PY - 2014
DO - 10.1587/transfun.E97.A.1220
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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.
ER -