Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-98-16 August 1998

Abstract

A long-term aim of current research into the frequency assignment problem is to identify features that would enable us to classify instances of the problem in terms of certain easily-computed parameters. Although there are good mathematical reasons why this may be impossible in full generality, experimental evidence is emerging which suggests that instances which occur in practice may be amenable to such classification [1].

One parameter that contributes to the specification of an instance of the problem is the signal-to-noise ratio (SNR). Recently some experimental work [2] has been done on the question of finding the minimum SNR for randomly-generated arrays of transmitters. The results suggest that, for a given configuration, the minima occur on the boundaries of what is known as the Voronoi partition. When the number of transmitters is small, and they are 'regularly-spaced', it is intuitively clear that a result of this kind should hold. But it is possible to conceive configurations in which one powerful transmitter causes complex variations in the SNR within the neighbourhood of a cluster of less powerful transmitters. The question is further complicated by the practical difficulty of specifying an exact propagation law for radio waves under operational conditions.

In this paper we shall state general conditions under which it can be proved that the minima of the signal-to-noise ratio must lie on the boundaries of the Voronoi partition. This result is significant for two reasons.

1. The complexity of calculating the minimum in any specific instance is reduced by an order of magnitude.

2. Because the propagation law cannot be specified exactly, it is useful to have results that hold under general conditions, valid in a wide range of practical situations.

These facts imply that the classification of a specific problem on the basis of the SNR can be done effectively, but without unnecessary assumptions about the details.

A compressed (gzip) PostScript file (37 kB) with the full contents of this report can be downloaded by clicking here.
The LaTeX file (9 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-98-16, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html