The Connectivity of Finite Random Geometric Graphs

By

Dr. Chi-kin Chau
Croucher Foundation Research Fellow, Electrical and Electronic Department
University College London
 

Date: May 30, 2008 (Friday)

Time: 2:30pm - 3:30pm

Venue: Rm. 1009 William MW Mong Engineering Building, CUHK

Abstract :

In wireless communications and networking theory, a well-known theorem by Gupta and Kumar states the asymptotic behaviour of connectivity for large random geometric graphs, which has been an important theoretical result in the literature since then. However, it appears insufficient to resolve several practically important problems. For instance, what is the minimum transmission radius that can guarantee the connectivity of a randomly deployed wireless network with a finite fixed number of nodes to attain a certain probability? This talk introduces some recent results that relate Gupta-Kumar theorem in finite random geometric graphs. Particularly, it presents relatively accurate approximation formulas of the connectivity of finite random geometric graphs, and discusses the practical ramifications in wireless communications and networking.

Biography :

Chi-Kin Chau is currently with Electrical and Electronic Department, University College London, as a Croucher Foundation research fellow. He is also a visiting scholar at Computer Laboratory, University of Cambridge. He received a Ph.D. from University of Cambridge, and a B.Eng. in Information Engineering from the Chinese University of Hong Kong.