On the performance of greedy forwarding on Yao and Theta graphs

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.