|
The Mathematics
of Radio Spectrum Management
|
Dr. R. A. Leese, St. Catherine's College, Oxford
The purpose of this report is to review the activity carried out since 1996 within a research program into the Mathematics of Radio Spectrum Management, funded by the Radiocommunications Agency through St. Catherine's College, Oxford. This section brie y describes the personnel involved in the spectrum management program in Oxford, together with the various grants that have supported them. (The Agency's funding of my own position has been the catalyst for wider research funding, mainly from the Engineering and Physical Science Research Council). Section 2 deals with the background to the problem, section 3 with the specific advances resulting from the Agency's funding, and section 4 with the prospects for further breakthroughs.
A list of the routes used for disseminations is attached as a separate document. References in the main text correspond to the numbering in section 3 of the dissemination list. Items [2], [3], [4], [10], [11] and [12] are contributions to radio conferences funded directly by the contract with St. Catherine's.
During the period of Agency funding, I have been the manager/supervisor for three separate research council grants:
The development of combinatorial approaches to the problems of radio channel assignment, EPSRC grant GR/K57701, 1995-98 (£162,427 for postdoctoral staff, costs, overheads and travel). This grant originally supported Jan van den Heuvel, who is now on the faculty at the London School of Economics, and subsequently supported Rebecca Gower. The final report has recently been submitted and assessed, with the highest grades being awarded for both scientific merit and management.
The researchers working in Oxford on spectrum management are currently: Prof. Dominic Welsh and Prof. Colin McDiarmid (both on the faculty), Stefanie Gerke (a research student, funded by the Agency), myself (funded by the Agency until 5th April 1999 and then by Smith Institute until 30th June 1999) and Frederic Havet (a postdoctoral researcher recently arrived to work on a project funded by British Telecom, but who has experience in radio channel assignment).
It has become clear over the past few years that there are signiffcant shortcomings in established methods for radio channel assignment, which raise questions in the wider eld of spectrum management. The broad aim of pursuing mathematical approaches has been to construct mathematical models that enable the calculation of better assignments, leading hopefully to an improved notion of spectrum effciency. There is a balance to strike between formulating models so as to capture the essential features of real systems, while keeping them suffciently simple so that their analysis is tractable. Models that are overly intricate may provide anecdotal evidence from computational work, but are less likely to generate a deeper, more general understanding of the principles behind good spectrum management. A separate, but equally important issue is how well the specification of a problem instance in any proposed model matches engineering practice. In other words, we ultimately want to take existing problems and find new ways of thinking about them. Regular discussions with the Agency have been vital in maintaining the appropriate focus for the research program.
The most useful mathematical model for generic assignment problems, which has withstood the test of many discussions with the Agency, has the following ingredients: a set of transmitter sites, Ti, each to be assigned a number of channels, mi, subject to constraints designed to avoid radio interference. The channels are identified by the integers 0, 1, 2, ..... The two most common constraint formulations are distance-based and frequency-based. In the former, constraints are specified by a sequence d0, d1, ...., in which dj is the minimum spatial separation allowed between two sites assigned channels j apart; in the latter, we have a sequence k1, k2, ..... , where ki is the minimum channel separation allowed between two channels assigned to sites a distance i apart. Distance-based constraints are more natural when the transmitters sites are embedded in a plane; frequency-based constraints are more natural when spatial distances are measured in an 'interference' graph, which has the transmitter sites as vertices and edges between those that interfere most strongly. Both formulations capture the necessary trade-off between spatial and frequency separations. The objective is to find the minimum span of any feasible assignment, i.e. the minimum difference between highest and lowest channels used.
Ideally one would like to calculate minimum spans with moderate computational effort and without error or uncertainty. However, the theory of computational complexity, which has been an active area of research in theoretical computer science since the 1970s, indicates that one cannot expect to solve problems of this type using any reasonable amount of computing effort. More precisely, all known algorithms (and there are good reasons to suppose that the same applies to all unknown algorithms, too) require a time that increases exponentially with the size of the problem. In the jargon of computational complexity, such problems are said to be NP-hard. In practice, one would be restricted to considering problems with just a few tens of assignments, much smaller than many real problems.
Faced with such an unpalatable prospect, there are three possible ways forward. First, one can try to design algorithms that run quickly but give only approximate solutions, in the form of assignments that have spans close to the minimum possible. Ideally, they would come with a guarantee attached, saying that the (unknown) true minimum had been exceeded by no more than some fixed fraction. The second possible approach, useful when assignment algorithms do not come with a built-in guarantee, is to design an independent procedure for calculating a lower bound on the minimum span. If some assignment algorithm produces a span S, and the lower bound calculation produces a value L, then S is no more than 100(S - L)/L % above the minimum possible. This approach has proved very useful, but has the shortcoming that if the difference between S and L is large, we do not know whether to look for improvements in the assignment or in the lower bound. The third approach is to lookforways of restricting the problem speciffcation in ways that maintain links with real-world application, but that allow either exact calculations of the minimum span, or else approximations with a definite guarantee where none existed previously. The following sections contain elements of all these possibilities.
At the start of the Agency contract with St. Catherine's
College, the research program concerned mainly problems on regular lattices. The
triangular lattice is of particular interest, since it corresponds to an efficient area
coverage using regular hexagons, as used in many spectrum planning exercises. A natural
problem, much harder than it first appears, is to assign a single channel at each site
subject to a pair of distance-based constraints (d0, d1
). A paper on this question has been published in the IEEE Transactions on Vehicular
Technology [7]. It uses a new algorithm, called SMR (Successive Maximal
Repetition), to construct assignments by periodic tiling. This work brought together and
extended several previous strands of work in the engineering literature.
More recently Colin McDiarmid has obtained more precise results [19]
in the limit of d0 and d1 becoming large. Mark
Shepherd refined the SMR algorithm in his DPhil thesis. There remain significant open
questions (see section 4.1 below). Nevertheless, evidence suggests that SMR achieves the
minimum span in about twice as many instances as the common method of assignments by
progression (in which there is a constant channel increment along each line of sites in
the lattice).
Exact results using frequency-based constraints seem more plentiful. Here three lattices have been studied in some detail: the one-dimensional lattice, the square lattice and the triangular lattice. Exact values for the minimum span have been obtained for two constraints (k1, k2) on all three lattices and additionally for (k1, k2, k3) in the case of the one-dimensional lattice. This work has recently appeared in the Journal of Graph Theory [13]. The best spans using assignments by progression for three constraints on the square and triangular lattices are also known, but not the minimum span over all assignments.
In addition to using frequency-based constraints in this work, two new modelling assumptions were made: first, spatial separations between transmitter sites were measured by graph distances in the lattice, rather than Euclidean distances in a planar embedding; secondly, the channels were taken to have a cyclic structure, meaning that the `highest' and `lowest' channels were considered adjacent. These modifications highlight the potential benefits of good mathematical modelling. Neither represents a severe departure from the underlying application (indeed, a cyclic channel structure is often implicitly assumed by engineers when multiple coverage is required), but together they allow for a deeper mathematical analysis than would otherwise be possible, leading to results that are easier to understand and use elsewhere.
A useful general feature of frequency-based constraints is that the minimum span is always a piecewise linear function of the constraint values (possibly rounded up if the linear function has fractional coeffcients). The same statement holds for the channels that make up an optimal assignment. For any given problem, the spectrum requirements can be presented in the form of a `phase diagram', showing how the minimum span depends on each of the constraint values. Each `piece' of the linear function corresponds to a separate region (or `phase') in the diagram. Such a picture can indicate where efforts should be directed to obtain reductions in the span. In effect the diagram summarizes results for a whole range of different constraints. Although these diagrams are intuitively appealing, they remain generally diffcult to calculate, mainly because it seems that the number of regions in a single diagram can be very large. The lattice problems mentioned above are a typical in this respect. As an exploration of what more complicated diagrams might look like, recent results have been obtained in collaboration with Steve Noble of Brunel University [22] for the minimum span on cycles with two constraints. Once again, modelling the channels in a cyclic way greatly aids theoretical progress.
In addition to their regular spatial structure, all the problems mentioned above require a single channel at each site. In the language of section 2 this means that mi = 1 for each site Ti. Such a restriction will rule out the study of many real problems. When general values of mi are allowed, which can be different at different sites, it seems much more diffcult to obtain exact values for the minimum span. Instead, it is better to aim for approximate values with attached guarantees. For example, on the triangular lattice with a single frequency-based constraint, Colin McDiarmid (in collaboration with Bruce Reed) has shown [8] how to calculate the minimum span to within a factor of about 4=3, i.e. no more than 33% excess. One might like tohave a factor closer to 1 in practice, but it is of fundamental signiffcance that a guarantee of any sort is possible. This problem is NP-hard even if each mi is restricted to be either 1 or 2. Colin together with his student, Stefanie Gerke, is continuing work with a similar avour, but concentrating on the case when the demands are large [24].
When dealing with explicit systems, instead of planning exercises, the problem is often fully irregular, meaning that, in addition to the demands varying from site to site, the interference constraints no longer describe a simple trade-off between spatial and spectral separations, for example because of irregular terrain. The constraints are then usually specified by a `constraint matrix'. The matrix entry cij is the minimum allowed channel separation between any pair of channels, one assigned to site Ti and the other to site Tj.
For fully irregular problems, the theory of computational complexity suggests that approximate results with no attached guarantee are the best one can hope for. However, in practice, it seems that algorithms can be designed that perform very well on many realistic problems, at least in cases where the performance can be verified through the existence of good lower bounds. In other words, real problems appear to have better computational characteristics that might initially be expected.
Under the Agency's contract with St. Catherine's College, a method has been developed [4,12] based on linear programming techniques. It composes an assignment from small patterns, known as `spectral blocks' and each covering just a few channels in the radio spectrum. The variables in this formulation correspond to the number of times each spectral block is used in the overall assignment. The method works especially well when the demands for spectrum are high, and in this sense it complements many existing approaches. The algorithm requires no fine-tuning and compares extremely well against the best meta-heuristic techniques. It is currently being used as the basis for a final-year undergraduate computing project [23], in which it is hoped to analyse a set of several hundred thousand different assignment problems constructed at random (see also section 4.3).
The following subsections briefly identify possible routes towards further understanding of channel assignment and spectrum management. Some are motivated by the outcome of the work described above, while others are questions that have been identified but not yet pursued. In his DPhil thesis, Mark Shepherd has included a useful chapter on open problems.
There is still no exact expression for the minimum span on the square and triangular lattices with two distance-based constraints. It is not known whether assignments with a periodic structure are suffcient, nor whether an optimal assignment must contain a tight constraint, i.e. two sites with the same channel at a distance d0 or two sites with adjacent channels at a distance d1 . Such questions might seem of purely academic interest, but it is worth remembering that regular problems are among the hardest for general algorithms to handle satisfactorily [12]. Answering these questions would give clues on designing better methods for irregular problems.
Even if problems have only mild irregularities they are often NP-hard, so that approximate algorithms must be considered. The range of problems for which a performance guarantee can be attached is at the moment rather small, but this is a relatively new part of the research program and deserves further attention. For such problems, one can try to show that the guarantee is the best possible, i.e. that there are problem instances for which the guarantee is stretched to its limit.
When no performance guarantee is available, there remains the option of calculating assignments with spans hopefully close to the minimum, supported by an independent lower bound. The quality of the result is now measured by the gap between the span of the explicit assignment and the lower bound. The smaller the gap, the better. The gap is determined in part by the quality of the algorithms employed, but a more fundamental challenge is to understand the effects of various features within the problem specification itself. Realistic problems often seem to produce smaller gaps than one might expect. In some cases, such as the standard `Philadelphia' benchmarks, the best algorithms have reduced the gap to zero, demonstrating optimality of the assignments. Keeping the algorithms fixed, the gap can be used to measure the dificulty of the problem. There is much evidence that in easy problems the span is determined somehow by local structure, such as a single site with very high demand or a cluster of sites with relatively high demands. This intuition is consistent with the experience that regular problems are hard. Further evidence is the observation that, when performance guarantees exist, the guarantee typically arises (in the language of graph theory) from bounding the ratio between the minimum span and the clique number; the latter corresponds to the `densest' local feature. To confirm and quantify such an intuition would be a major advance, likely to lead to new performance guarantees.
The previous subsection touched on the classification question, in the sense of determining what makes a particular problem easy or hard. More ambitiously, one might try to map out the whole problem space, identifying the easy regions and hard regions, and also the regions corresponding to real problems (which hopefully intersect largely with the easy regions). The dificulty of particular problems could then be estimated without running any assignment algorithms, by identifying where they lay in the problem space. A set of classification parameters, which could be easily calculated for any given problem instance, would be used as coordinates in the problem space. The best parameters would be those which were physically intuitive, which determined the span with high confidence, and which could naturally be used as `internal' parameters in assignment algorithms.
This approach is statistical in nature and very different from previous parts of the research programme. It aims not to give guarantees for the span, but confidence intervals in terms of the classification parameters. Problems would be considered easy if their corresponding confidence intervals were narrow, i.e. if the classification parameters gave a good approximation to the minimum span with high probability. An initial numerical investigation [23] is currently being carried out by Brian Bird, a final-year undergraduate in computation at St. Catherine's, as the project for his degree requirement. He is using a small number of parameters, capturing intuitive notions such as the distances over which constraints act and the random effects of terrain.
All the preceeding discussion has, either implicitly or explicitly, assumed binary constraints, in the sense that they each constrain the assignments that may be made at a pair of sites. Although this is established engineering practice, the physical laws of radio signal propagation suggest that a larger scope might be more appropriate. Using only binary constraints can force problems to be either underconstrained or overconstrained in comparison with the physical requirements. The former means that feasible assignments might not be acceptable in practice; the latter means that the feasible assignment with minimum span uses more channels than needed. The main advantages of binary constraints are that they obviate the need for an explicit treatment of propagation models, make theoretical advances more likely, and lead to faster algorithms.
A first investigation of the effects of dropping binary constraints appeared in [2], and since then the topic has been addressed mainly by other groups in the UK.
Evolving assignments fall into two broad categories: evolution as part of the natural system operation, and evolution as a result of system expansion. The first includes personal communications systems such as mobile telephony, in which demands for spectrum are made only over limited (usually short) timescales. It has not been part of the research program to date. The second corresponds to taking an existing system and adding new sites or new demands, which are then effectively present for all time. A first piece of work in this direction appeared in Mark Shepherd's thesis, and also in [18], where a one-dimensional lattice of potential transmitter sites was considered. The density of transmitters that can be assigned (all using the same channel) was calculated, assuming they are successively and randomly located at lattice sites so as to avoid interference. This is a discrete version of parking cars in an initially empty street.
This document lists the papers and presentations that have been used since 1996 to disseminate the results of the research program into radio channel assignment within the Mathematical Institute at the University of Oxford. It includes details of research seminars, conferences (on both the mathematical and engineering sides), book chapters and papers in academic journals. Where conference contributions were published in proceedings, they are included in section 3 rather than section 1.
There have been several dissemination activities not associated with particular pieces of research. Funding from the EPSRC/LMS Mathfit initiative was obtained to run a three-day workshop in Oxford in April 1997. Two sessions devoted to channel assignment have been organized at major international conferences: Rebecca Gower ran a session at the 10th Conference of ECMI (European Consortium for Mathematics in Industry), held in Gothenburg in June 1998, and Robert Leese ran an invited session at the 9th SIAM Conference on Discrete Mathematics, held in Toronto in July 1998. Robert also gave a series of 10 invited lectures on channel assignment to graduate students at the Technical University of Eindhoven in October 1998.
R. A. Leese
|
 |
