# On Graphs Supporting Greedy Forwarding for Directional Wireless Networks

Si, Weisheng; Scholz, Bernhard; Gudmundsson, (Hans) Joachim; Mao, Guoqiang; Boreli, Roksana; Zomaya, Albert

2012-06-19

Conference Material

IEEE International Conference on Communications (ICC)

Ottawa, Canada

1-6

Greedy forwarding is an efficient and scalable routing algorithm for wireless networks. To make greedy forwarding succeed on a network, many research efforts assign virtual coordinates to nodes in the network to obtain a greedy embedding. 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 to add point-to-point links among them, such that greedy forwarding succeeds on the resulting network topology and this topology contains the minimum number of links. 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 investigates properties of the graphs that support greedy forwarding, and then solves the above problem with an optimal solution by Integer Linear Programming and also a suboptimal polynomial-time algorithm with an approximation factor of 3. Finally, this paper compares the results of the polynomial-time algorithm and the optimal solution, showing that the polynomial-time algorithm can actually generate less than 1.1 times the number of links found by the optimal solution in most cases.

topology control; geographic routing; greedy forwarding; nearest neighbor graphs; directional wireless networks

nicta:5216

Si, Weisheng; Scholz, Bernhard; Gudmundsson, (Hans) Joachim; Mao, Guoqiang; Boreli, Roksana; Zomaya, Albert. On Graphs Supporting Greedy Forwarding for Directional Wireless Networks.[Conference Material]. 2012-06-19. <a href="http://hdl.handle.net/102.100.100/100425?index=1" target="_blank">http://hdl.handle.net/102.100.100/100425?index=1</a>

Loading citation data...

Citation counts

(Requires subscription to view)