Home | English | | | UGC | RGC
  Launching Theme-based Research
  The Legacy of Meritocracy:
Peking University Undergraduates,
  Negotiating with Media Globalization:
The Impact of China's Accession to the WTO on Its Media and Telecommunications Industries
  Neuroimaging studies of reading disability in Chinese children
  Random Geometric Graphs and Their Applications
  Paleoenvironmental Interpretation of the Olorgesailie Formation, Kenya Rift Valley
  A Study on the Collaborative Virtual
Geographic Environment (CVGE) for Simulating Air Pollution in Pearl River Delta (PRD) Region






A wireless sensor networks (WSN) consists of sensor nodes with limited computation and communication capabilities, as illustrated in Figure 1. In most practical applications of WSNs, the wireless sensors are deployed in a large volume. The sheer large number of sensors deployed coupled with the potential harsh environment often hinders or completely eliminates the possibility of strategic device placement, and consequently random deployment is often the only viable option. For all these applications, it is natural to represent the sensors by a finite random point process over the deployment region-typically a uniform point process or a Poisson point process. WSNs over finite random point processes are modeled by various types of random geometric graphs depending on the probabilistic behavior to be studied. The probabilistic studies of these random geometric graphs are notoriously difficult in general due to the local dependence of the edges and the complicated boundary effect. In this project, we have completed the random geometric studies for the following three specific parameters:

Critical Transmission Radius for Greedy
Forward Routing:
Greedy forwarding routing (GFR) in WSNs is a localized geographic routing in which each node discards a packet if none of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination of the packet. Assume all nodes have the same transmission radii. The critical transmission radius (CTR) for GFR is the smallest transmission radius which ensures that the greedy forwarding routing can deliver any packet from its source to its destination. The study of the CTR of a finite Poisson point process dates back to 1984, and its asymptotic distribution has remained a major open problem for 25 years. After making a series of efforts in recent years, we finally obtained its precise asymptotic distribution in 2009.

Maximum Edge Length of Proximity Graphs: Relative neighborhood graph (RNG) and Gabriel graph (GG) are two proximity graphs with many applications in localized topology control and geographic routing in WSNs. Their maximum edge lengths represent the requirement on the maximum transmission radius of the sensor nodes by the applications. In this project, we successfully derived the precise asymptotic distributions of the maximum edge lengths of the RNG and GG on a finite Poisson point process.

Figure 1: An illustration of wireless sensor network
Source: http://www.dei.unipd.it/~schenato/pics/SensorNet

Scan Statistics and Their Applications: The maximum (respectively, minimum) scan statistic of a WSN with respect to a scanning set is the largest (respectively, least) number of sensors that can be covered by a copy of the scanning set. The scan statistics is a powerful analytic tool with many applications. In this project, we derived the asymptotics of WSNs, and applied them to derive tight asymptotically almost sure bounds on important topological parameters including the maximum degree, minimum degree, clique number, and chromatic number.

The above research discoveries provide deep insight into the asymptotic behaviors of large-scale randomly deployed wireless sensor networks. They also have broader range of applications in epidemiology, astronomy, geology, and many others. The new problem-solving techniques introduced in our research are also expected to be useful for the random geometric studies of other problems.

Prof. Foong Yao
Department of Computer Science
City University of Hong Kong