On Graphs Supporting Greedy Forwarding for Directional Wireless Networks
Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can the authors add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network.