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. |
|
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. |
