Abstract
Greedy Forwarding algorithm is a widely-used routing algorithm for wireless networks. However, it can fail if the wireless network topologies contain voids, where a packet cannot be moved closer to destination. Since Yao graph and Theta graph are two types of geometric graphs exploited to construct wireless network topologies, this paper firstly studied whether these two types of graphs can contain voids, showing that when the number of cones in a Yao graph or Theta graph is less than six, Yao graph and Theta graph can have voids, and when the number of cones equals or exceeds six, Yao graph and Theta graph are free of voids. Secondly, this paper experimented on how well Greedy Forwarding is supported on Yao graphs and Theta graphs in terms of stretch, i.e., the ratio between the path length found by Greedy Forwarding and the shortest path length in a graph. The experiments also included comparison with the stretch on Delaunay triangulation, another well-known geometric graph exploited in constructing wireless networks. Overall, our experiments revealed several interesting results.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of IEEE Global communications Conference (GLOBECOM 2014), Austin, Texas, U.S.A., 8-12 December 2014 |
| Publisher | IEEE |
| Pages | 76-81 |
| Number of pages | 6 |
| ISBN (Print) | 9781479935116 |
| Publication status | Published - 2014 |
| Event | IEEE Global Communications Conference - Duration: 8 Dec 2014 → … |
Conference
| Conference | IEEE Global Communications Conference |
|---|---|
| Period | 8/12/14 → … |
Keywords
- algorithms
- geometry
- graph theory
- wireless networks