Events Calendar

Greedy Routing with Guaranteed Delivery Using Ricci Flows

Dr. Jie Gao
Assistant Professor, Department of Computer Science,
Stony Brook UniversityAbstract: Greedy forwarding with geographical locations in a wireless sensor
network may fail at a local minimum. In this paper we propose to use conformal
mapping to compute a new embedding of the sensor nodes in the plane such that
greedy forwarding with the virtual coordinates guarantees delivery. In
particular, we extract a planar triangulation of the sensor network with nontriangular
faces as holes, by either using the nodes location or using a
landmark‐based scheme without node location. The conformal map is computed with
Ricci flow such that all the non‐triangular faces are mapped to perfect circles.
Thus greedy forwarding will never get stuck at an intermediate node. The
computation of the conformal map and the virtual coordinates is performed at a
preprocessing phase and can be implemented by local gossip‐style computation. The
method applies to both unit disk graph models and quasi‐unit disk graph models.
Simulation results are presented for these scenarios.
This is joint work with Rik Sarkar, Xiaotian Yin, Feng Luo and Xianfeng David Gu.
Bio: Jie Gao is currently an assistant professor at Department of Computer
Science, Stony Brook University. She received Ph.D from Computer Science
department, Stanford University in 2004 and B.S. from the special class for the
gifted young, University of Science and Technology of China in 1999. She works on
algorithms, sensor networks, and computational geometry. She received NSF CAREER
award in 2006 and she is an associate editor of ACM Transaction on Sensor
Networks.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Shane Goodoff