How Well Do Yao Graph and Theta Graph Support Greedy Forwarding?

Speaker: Weisheng Si

Affiliation: University of Western Sydney

Time: Monday 29/09/2014 from 14:00 to 15:00

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

Abstract: Greedy Forwarding algorithm is a widely-used routing algorithm for wireless networks. However, it can fail if the wireless network topologies contain voids, where a packet cannot be moved closer to destination. Since Yao graph and Theta graph are two types of geometric graphs exploited to construct wireless network topologies, this paper firstly studied whether these two types of graphs can contain voids, showing that when the number of cones in a Yao graph or Theta graph is less than six, Yao graph and Theta graph can have voids, and when the number of cones equals or exceeds six, Yao graph and Theta graph are free of voids. Secondly, this paper experimented on how well Greedy Forwarding is supported on Yao graphs and Theta graphs in terms of stretch, i.e., the ratio between the path length found by Greedy Forwarding and the shortest path length in a graph. The experiments also included comparison with the stretch on Delaunay triangulation, another well-known geometric graph exploited in constructing wireless networks. Overall, our experiments revealed several interesting results.

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.