Algorithms for 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 there are already several results on those problems, there are still many challenges, for example incorporating external factors (obstacles) and dealing effectively with moving stations or users. The goal of this project is to develop new exact and/or approximation algorithms for these problems, and prove hardness and combinatorial results.

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

Supervisors Mark de Berg (TU Eindhoven) and Gerhard Woeginger (TU Eindhoven)
PhD Student Aleksandar Markovic
Location Eindhoven University of Technology (TU/e)