Stochastic Aspects of Range- and Frequency-Assignment Problems in Wireless Networks

Summary Whether or not two nodes in a wireless network can communicate with each other depends on the distance between them and the transmission power of the nodes. In range-assignment problems one is given the locations of the nodes of the network, and the goal is to assign a range (i.e., transmission power) to each node such that the resulting network has certain desired properties, while minimizing a given cost function. A related problem is the frequency-assignment problem, where one has to assign frequencies to base stations in such a way that users can always communicate with at least one base station whose frequency is different from the frequencies of other base stations within range (so that there is no interference).
While these problems are typically investigated in a deterministic setting, they also raise many exciting stochastic questions. For example, suppose that the nodes are distributed randomly within some region, what can we say about the expected cost of an optimal range assignment? Or about the expected number of frequencies needed in a conflict-free assignment? And what happens when communication links can fail with a certain probability?

Note: there is also a companion project dealing with algorithmic aspects of range- and frequency-assignment problems.

Supervisors Johan van Leeuwaarden (TU Eindhoven) and Mark de Berg (TU Eindhoven)
Location Eindhoven University of Technology (TU/e)