|dc.description.abstract||This thesis concerns mathematical models of wireless communication networks, in particular
ad-hoc networks and 802:11 WLANs. In ad-hoc mode each of these devices may
function as a sender, a relay or a receiver. Each device may only communicate with other
devices within its transmission range. We use graph models for the relationship between
any two devices: a node stands for a device, and an edge for a communication link, or
sometimes an interference relationship. The number of edges incident on a node is the
degree of this node. When considering geometric graphs, the coordinates of a node give
the geographical position of a node.
One of the important properties of a communication graph is its connectedness |
whether all nodes can reach all other nodes. We use the term connectivity, the probability
of graphs being connected given the number of nodes and the transmission range to measure
the connectedness of a wireless network. Connectedness is an important prerequisite for
all communication networks which communication between nodes. This is especially true
for wireless ad-hoc networks, where communication relies on the contact among nodes and
Another important property of an interference graph is its chromatic number | the
minimum number of colours needed so that no adjacent nodes are assigned the same colour.
Here adjacent nodes share an edge; adjacent edges share at least one node; and colours
are used to identify di erent frequencies. This gives the minimum number of frequencies
a network needs in order to attain zero interference. This problem can be solved as an
optimization problem deterministically, but is algorithmically NP-hard. Hence, nding
good asymptotic approximations for this value becomes important.
Random geometric graphs describe an ensemble of graphs which share common features.
In this thesis, node positions follow a Poisson point process or a binomial point
process. We use probability theory to study the connectedness of random graphs and
random geometric graphs, which is the fraction of connected graphs among many graph
samples. This probability is closely related to the property of minimum node degree being
at least unity. The chromatic number is closely related to the maximum degree as n ! 1;
the chromatic number converges to maximum degree when graph is sparse. We test existing
theorems and improve the existing ones when possible. These motivated me to study
the degree of random (geometric) graph models.
We study using deterministic methods some degree-related problems for Erda}os-R enyi
random graphs G(n; p) and random geometric graphs G(n; r). I provide both theoretical
analysis and accurate simulation results. The results lead to a study of dependence or
non-dependence in the joint distribution of the degrees of neighbouring nodes.
We study the probability of no node being isolated in G(n; p), that is, minimum node
degree being at least unity. By making the assumption of non-dependence of node degree,
we derive two asymptotics for this probability. The probability of no node being isolated is
an approximation to the probability of the graph being connected. By making an analogy
to G(n; p), we study this problem for G(n; r), which is a more realistic model for wireless
networks. Experiment shows that this asymptotic result also works well for small graphs.
We wish to nd the relationship between these basic features the above two important
problems of wireless networks: the probability of a network being connected and the
minimum number of channels a network needs in order to minimize interference.
Inspired by the problem of maximum degree in random graphs, we study the problem
of the maximum of a set of Poisson random variables and binomial random variables,
which leads to two accurate formulae for the mode of the maximum for general random
geometric graphs and for sparse random graphs. To our knowledge, these are the best
results for sparse random geometric graphs in the literature so far. By approximating
the node degrees as independent Poisson or binomial variables, we apply the result to the
problem of maximum degree in general and sparse G(n; r), and derived much more accurate
results than in the existing literature. Combining the limit theorem from Penrose and our
work, we provide good approximations for the mode of the clique number and chromatic
number in sparse G(n; r). Again these results are much more accurate than existing ones.
This has implications for the interference minimization of WLANs.
Finally, we apply our asymptotic result based on Poisson distribution for the chromatic
number of random geometric graph to the interference minimization problem in IEEE
802:11b/g WLAN. Experiments based on the real planned position of the APs in WLANs
show that our asymptotic results estimate the minimum number of channels needed accurately.
This also means that sparse random geometric graphs are good models for interference
minimization problem of WLANs. We discuss the interference minimization
problem in single radio and multi-radio wireless networking scenarios. We study branchand-
bound algorithms for these scenarios by selecting di erent constraint functions and