The purpose of a point-to-multipoint radio access system (PMP-system) is to supply wireless access to voice/data communication networks. Base stations form the access points to the network. Costumer terminals are linked to base stations by means of radio signals, where some specific part of the radio frequency spectrum has to be used to maintain the links. In contrast to cellular phone networks, each costumer is provided a fixed antenna and is assigned to a certain sector of a base station. A central problem is that a link connecting a costumer terminal and a base station may be subject to interference from another link, provided that the same frequency is used. To guarantee an interference-free communication, two frequency assignment problems have to be solved when operating a PMP-system, namely, the bandwidth allocation and the broadcast channel assignment. The bandwidth allocation is the problem of assigning a frequency interval within the available radio frequency spectrum to each costumer (link). The goal is to identify span-minimal frequency plans, taking into account the individual communication demand of each costumer and several technical and legal restrictions. The bandwidth allocation can be modeled as an interval coloring problem on weighted graphs: the nodes represent costumer terminals (links), the node weights reflect the communication demands, and the edges indicate potential interference between the links. Interval coloring problems are NP-hard in general and cannot be approximated in polynomial time with a guaranteed quality. We have focused on developing several fast heuristics: primal start and improvement heuristics to compute frequency plans with low span and a dual heuristic to determine a lower bound on the minimal span. Upper and lower bounds together allow to estimate the quality of the primal solution. For small and medium-sized problems, a span-minimal solution could be achieved by using the primal heuristics. For all test instances provided by BOSCH Telecom, the maximal gap between the lower bound and the span of a computed primal solution was less than 15%. The broadcast channel problem consists in assigning one further (unit demand) channel to each sector of a base station. This channel is required for signaling purposes between the base station and the customer terminals within its sectors. The goal is to provide a broadcast channel to each sector without causing interference among the sectors such that a minimal number of channels is used. The broadcast channel problem corresponds to coloring the graph with all sectors as nodes and edges that represent the potential interference. Coloring problems are also NP-hard in general and cannot be approximated in polynomial time with a guaranteed quality. Since the relevant problem sizes are anticipated to be small, a complete enumeration scheme has been implemented. In fact, the enumeration process may be aborted prematurely by setting time bounds. Within less than one minute, however, all of the test instances supplied by BOSCH Telecom were solved to optimality.
