| Presentation | 2012-10-31 A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks Jinhee CHUN, Akiyoshi SHIOURA, TIEN Truong MINH, Takeshi TOKUYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 it is closed under convex linear combination of objective functions. 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 discuss comparison of these methods. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | COMP2012-34 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2012/10/24(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Jinhee CHUN |
| 1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Akiyoshi SHIOURA |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | TIEN Truong MINH |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 4th Author's Name | Takeshi TOKUYAMA |
| 4th Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| Date | 2012-10-31 |
| Paper # | COMP2012-34 |
| Volume (vol) | vol.112 |
| Number (no) | 272 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |