APPLIED MATH SEMINAR

Name:   Edmund Yeh, Electrical Engineering, Yale University

Title:     "Percolation Theory and Large-Scale Wireless Networks: Critical Density,

Transmission Delay, and Network Resilience"

When/where: Tuesday, June 3rd, 4:15 p.m., AKW 200

 

Abstract:          

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.  First, we investigate the fundamental problem of characterizing the critical density for d-dimensional Poisson random geometric graphs in continuum percolation theory. By using a probabilistic analysis which incorporates the clustering effect in random geometric graphs, we develop a new class of analytical lower bounds for the critical density. These analytical lower bounds are the tightest known to date, and reveal a deep underlying relationship between clustering effects and percolation phenomena.

 

Next, we study connectivity and transmission delay in wireless networks with unreliable links from a percolation-based perspective. We first examine static models, where each link of the network is functional (active) with some probability, independently of all other links.  We obtain analytical upper and lower bounds on the critical density for phase transition in this model. We then examine dynamic models, where each link is active or inactive according to a Markov on-off process. We show that a phase transition also exists in such dynamic networks, and the critical density for this model is the same as the one for static networks (with the same stationary distribution). Furthermore, due to the dynamic behavior of links, a delay is incurred for any transmission 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.

 

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. In particular, 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 failures problem in large-scale wireless networks, 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).