On Graphs Supporting Greedy Forwarding for Directional Wireless Networks

Speaker: Weisheng Si

Affiliation: University of Western Sydney

Time: Monday 21/05/2012 from 14:00 to 15:00

Venue: Access Grid UWS. Presented from Penrith (Y239), accessible from Parramatta (EB.1.32) and Campbelltown (26.1.50).

Abstract: 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.

Biography: Weisheng Si is currently a lecturer in the School of Computing, Engineering and Mathematics, University of Western Sydney. Prior to this, he was a postdoctoral researcher at National ICT Australia (NICTA). He received his BS, MS, and PhD degrees in computer science from Peking University (China), University of Virginia (USA), and University of Sydney (Australia) respectively. His research interests include wireless networks, graph theory, web applications, and green networking.