Connectivity analysis of wireless ad-hoc networks

Abstract

Connectivity is one of the most fundamental properties of wireless

ad-hoc networks as most network functions are predicated upon the

network being connected. Although increasing node transmission power

will improve network connectivity, too large a power level is not

feasible as energy is a scarce resource in wireless ad-hoc networks.

Thus, it is crucial to identify the minimum node transmission power

that will ensure network connectivity with high probability.

It is known that there exists a critical level transmission power

such that a suitably larger power will ensure network connectivity

with high probability. A small variation across this threshold level

will lead to a sharp transition of the probability that the network

is connected. Thus, in order to precisely estimate the minimum node

transmission power, not only do we need to identify this critical

threshold, but also how fast this transition takes place. To

characterize the sharpness of transition, we define weak, strong and

very strong critical thresholds associated with increasing

transition speeds.

In this dissertation, we seek to estimate the minimum node

transmission power for large scale one-dimensional wireless ad-hoc

networks under the Geometric Random Graph (GRG) models. Unlike in

previous works where nodes are taken to be uniformly distributed, we

assume a more general node distribution. Using the methods of first

and second moments, we theoretically prove the existence of a very

strong critical threshold when the density function is everywhere

positive. On the other hand, only weak thresholds are shown to exist

when the density function contains vanishing densities.

We also study the connectivity of two-dimensional wireless ad-hoc

networks under the random connection model, which accounts for

statistical channel variations. With the help of the Stein-Chen

method, we derive a closed form formula for the limiting probability

that there are no isolated nodes under a very general assumption of

channel variations. The node transmission power to ensure the

absence of isolated nodes provides a tight lower bound on the

transmission power needed to ensure network connectivity.