Computer Science Research Seminar

11:15 AM, Wednesday, May 6, 2009

Prof. Jie Gao

Stony Brook University

Title: Fractional Cascading in Sensor Network Aggregation and Routing


In an ad hoc sensor network, the sensor nodes start with no knowledge of the network and a challenge is to decide how much should one sensor know about the others so as to facilitate network functions. We introduce the principle of "fractional cascading" in sensor network algorithm design -- each node knows more about nearby nodes and less about far away nodes and information naturally cascades with respect to distances. We apply this principle in two sensor network problems. In the first problem, we devise a spatial gossip algorithm to build multi-resolutional data representation with near linear total communication messages. In the second problem we develop compact routing tables with which a greedy algorithm discovers close to shortest path for any pairs of nodes. This work is collaborated with Rik Sarkar and Xianjin Zhu.


Jie Gao is currently an assistant professor at Department of Computer Science, Stony Brook University. She obtained her Ph.D degree in Computer Science from Stanford University in 2004, and her B.Sc degree from the Special Class for the Gifted Young at University of Science and Technology of China in 1999. Her research interests span algorithms, networking and computational geometry. Recently she works on wireless sensor networks. She received NSF CAREER award in 2006.