Performance studies of wireless multihop networks

Abstract

Wireless multihop networks represent a fundamental step in the evolution of wireless communications, a step that has proven challenging. Such networks give rise to a wide range of novel performance and design problems, most of which are of a geometric nature. This dissertation addresses a selection of such problems.

The first part of this thesis presents studies in which the network nodes are assumed to receive signals sufficiently clearly only from within some fixed range of operation. Using this simple model, the first two problems addressed are to predict the probabilities that a network with randomly placed nodes is connected or completely covers a given target domain, respectively. These problems are equivalent to determining the probability distribution of the minimal range providing connectivity or coverage. Algorithms for determining these threshold ranges for a given set of network nodes are developed. Because of the complex nature of these problems in finite settings, they are both approached by empirically modeling the convergence of these distributions to their known asymptotic limits. Next, a novel optimization problem is presented, in which the task is to make a given disconnected network into a connected one by adding a minimal number of additional nodes to the network, and heuristic algorithms are proposed for this problem.

In the second part, these networks are studied in the context of a more realistic model in which the condition for successful communication between network nodes is expressed as an explicit minimum value for the received signal-to-noise-and-interference ratio. The notion of the threshold range for connectivity is first generalized to this network model. Because connectivity is now affected by medium access control (MAC), two alternative MAC schemes are considered. Finally, an infinite random network employing slotted Aloha is studied under this model. Since the probability of successful reception in a random time slot is a function of the locations of other nodes, this temporal probability is a random variable with its own probability distribution over different node configurations. Numerical approximations for evaluating both the mean and the tail probability of this distribution are developed. The accuracy of these approximations can be improved indefinitely, at the cost of numerical computations.