Independent Sets and Graph Coloring with Applications to the Frequency Allocation Problem in Wireless Networks
Evi Papaioannou · 2004
The subject of this dissertation thesis is the study of issues arising in communication networks that utilize Frequency Division Multiplexing (FDM). We consider networks based on telecommunication infrastructure such as cellular mobile telephone networks and networks of autonomous transmitters, like ad hoc wireless networks. We represent these networks using graphs and model the corresponding communication problems as combinatorial optimization problems in such graphs. Our results include new on-line algorithms which outperform previously known algorithms as well as new lower bounds. In cellular networks, a geographical region is virtually divided into subregions called cells. Each cell is the calling area of a base station which enables wireless communication. Each base station is responsible for servicing users located within its range. Communication between two users of a cellular network involves in the first place communication between each user and the base station that services the cell where the user is located. Then, communication between the base stations must be established. Wireless communication between users and their base station is always involved, even when both of the users are located in the same cell or only one of them uses the cellular network and the other uses, for example, the standard telephone network. Two users located close to each other can simultaneously communicate with their base station via Frequency Division Multiplexing technology, using different frequencies. Usually, the use of the same frequency by users located in the same or adjacent cells causes signal interference, thus, making communication hard or impossible to establish. The basic cellular network model assumes base stations equipped with equivalent transmitters, uniformly distributed on the plane. Therefore, the plane is divided in cells of hexagon shape. In fact, cells can have irregular shape and it may be the case that the signal interference constraints regarding the reuse of frequencies by different users are even harder and more complicated. We