学术讲座:Greedy routing algorithms via virtual coordinates

**Time:** 9:00-11:00 am, May 4, 2014

**Location:** Room 106, PKU-ICST Building.

**Title:** Greedy routing algorithms via virtual coordinates

**Speaker:** Huaming Zhang, Associate Professor in University of Alabama in Huntsville

**Abstract:**

Routing is one of the most important algorithmic problems in networking. Geometric routing is a newer approach for solving network routing problems. This scheme uses geometric coordinates of network nodes to compute the routing paths. The simplest geometric routing is greedy routing: a network node simply forwards messages to a neighbor that is closer to the destination. Greedy routing is simple, but also has serious drawbacks. For example, for a star-shaped network with a center node and six leaf nodes, greedy routing fails when routing a message from an original leaf node to a destination leaf node, due to the fact that the center node is no closer to the destination leaf node than the original leaf node. To solve these problems, an elegant solution was proposed by Rao et al. Instead of using the real geometric coordinates, one could first use graph drawing techniques to compute coordinates for the nodes in the network. The drawing coordinates are used as the virtual coordinates for the nodes. Then geometric routing algorithms rely on the virtual coordinates to compute routes. In this talk, we are going to survey several recent results on greedy routing algorithms via virtual coordinates and present one of them in more detail.

**Short Bio.**

Dr. Zhang earned his Ph.D. degree in Computer Science and Engineering from SUNY at Buffalo in 2005. After graduating from Buffalo, he joined the Computer Science Department at the University of Alabama in Huntsville. Now, he is an associate professor in UAH. He has published over 40 journal articles and conference papers, with a focus on computational geometry. His research has been supported by the National Science Foundation.

上一篇 下一篇