TY - GEN
T1 - A unified view to greedy geometric routing algorithms in ad hoc networks
AU - Chun, Jinhee
AU - Shioura, Akiyoshi
AU - Tien, Truong Minh
AU - Tokuyama, Takeshi
PY - 2013
Y1 - 2013
N2 - The main aim of this paper is to give a unified view to greedy geometric routing algorithms in ad hoc networks. For this, we firstly 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 some 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 the class of objective functions with this condition is closed under convex combination. We show 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, and then compare the merits and demerits of these methods.
AB - The main aim of this paper is to give a unified view to greedy geometric routing algorithms in ad hoc networks. For this, we firstly 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 some 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 the class of objective functions with this condition is closed under convex combination. We show 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, and then compare the merits and demerits of these methods.
KW - ad hoc network
KW - Delaunay graph
KW - geometric routing
KW - greedy routing
UR - http://www.scopus.com/inward/record.url?scp=84872450858&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872450858&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36092-3_7
DO - 10.1007/978-3-642-36092-3_7
M3 - Conference contribution
AN - SCOPUS:84872450858
SN - 9783642360916
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 54
EP - 65
BT - Algorithms for Sensor Systems - 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Revised Selected Papers
PB - Springer Verlag
T2 - 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012
Y2 - 13 September 2012 through 14 September 2012
ER -