On the performance of greedy forwarding on Yao and Theta graphs
- Publication Type:
- Journal Article
- Citation:
- Journal of Parallel and Distributed Computing, 2018, 117 pp. 87 - 97
- Issue Date:
- 2018-07-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 1-s2.0-S0743731518300832-main.pdf | Published Version | 2.31 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2018 Elsevier Inc. Greedy Forwarding algorithm is an important geometric routing algorithm for wireless networks. However, it can fail if the network topologies contain voids, in which a packet cannot be moved closer to destination. Since Yao and Theta graphs are two types of geometric graphs exploited to construct wireless network topologies, this paper first gives theoretical results on whether these two types of graphs can contain voids with respect to their cone numbers. Then, this paper examines the performance of Greedy Forwarding on Yao and Theta graphs in terms of stretch (the ratio between the path length found by Greedy Forwarding and the shortest path length from a source to a destination). Both worst-case and average-case stretches are studied. For the worst case, this paper shows that the stretches of Greedy Forwarding on both Yao and Theta graphs do not have a constant upper bound (i.e., not competitive) in hop metric. For the average case, this paper studies the stretch experimentally by running Greedy Forwarding on a large number of Yao and Theta graphs with randomly generated node sets. The average-case stretches in both hop and Euclidean metrics are measured, and several interesting findings are revealed.
Please use this identifier to cite or link to this item: