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 we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also suboptimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases.