Percolation Theory and Large-Scale Wireless Networks: Connectivity, Transmission Delay, and Network

SPEAKER: Professor Edmund Yeh
Department of Electrical Engineering
Yale UniversityFriday, September 19, 2008
10:00-11:30 am
EEB 248ABSTRACT: The mathematical theory of percolation has become a valuable tool for the analysis of large-scale wireless networks deployed in challenging environments. In this talk, we present some recent results on connectivity, transmission delay, and network resilience from a percolation-based perspective.We first study a model for wireless networks where each link in a random geometric graph is active or inactive according to a Markov on-off process. In this case, we show the existence of a phase transition where the dynamic network is either percolated for all time (supercritical) or the network is percolated at no time (subcritical). Due to the dynamic on-off behavior of links, a delay is incurred for information dissemination even when propagation delay is ignored. We show that this transmission delay scales linearly with the Euclidean distance between the sender and the receiver when the network is in the subcritical phase, and the delay scales sub-linearly with the distance if the network is in the supercritical phase. More interestingly, we show that these results can be used to study information dissemination in wireless networks with mobile nodes. Using a new analysis which maps a network of mobile nodes to a network of stationary nodes with dynamic links, we show that messages can be disseminated to all nodes in a mobile network even when the network is not percolated at any fixed instant.Finally, we study the problem of wireless network resilience to node failures from a percolation-based perspective. In practical wireless networks, it is often the case that nodes with larger degrees (i.e., more neighbors) are more likely to fail. We model this phenomenon as a degree-dependent site percolation process on random geometric graphs. We obtain analytical conditions for the existence of phase transitions within this model. Furthermore, in networks carrying traffic load, the failure of one node can result in redistribution of the load onto other nearby nodes. If these nodes fail due to excessive load, then this process can result in cascading failure. We analyze this cascading failure problem, and show that it is equivalent to a degree-dependent site percolation on random geometric graphs. We obtain analytical conditions for cascades in this model.Joint work with Zhenning Kong, Yale University.BIOGRAPHY: Edmund Yeh received his B.S. in Electrical Engineering with Distinction from Stanford University in 1994, his M.Phil in Engineering from the University of Cambridge in 1995, and his Ph.D. in Electrical Engineering and Computer Science from MIT in 2001. Since 2001, he has been on the faculty at Yale University, where he is currently an Associate Professor of Electrical Engineering (with joint appointments in Computer Science and Statistics).HOST: Prof. Michael Neely, mjneely@usc.edu

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

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos