\documentstyle
[12pt]
{article}

%\long\def\skip#1{\relax}
\def\e{\varepsilon} 
\def\a{\alpha}
\def\b{\beta}
\def\l{\lambda}
\def\s{\sigma}
\def\ph{\varphi}
\def\ra{\rightarrow}
\def\Z{{\bf Z}}
\def\N{{\bf N}}
\def\R{{\bf R}}
\def\Rplus{\R^+}
\def\RO{\R^{\geq 0}}
\def\mod{\;\mbox{\rm mod}}
\def\qed{$\Box$\par\bigskip\noindent}
\def\xx{\overline{x}}
\newtheorem{th}{THEOREM}
\newtheorem{lem}{LEMMA}
\newtheorem{conj}{CONJECTURE}

\title{Optimising the signal-to-noise ratio} 
\author{N.~L.~Biggs \qquad D.~G.~Fon-Der-Flaass
\thanks{Supported by the U.K. Radiocommunications Agency}
\\Centre for Discrete and Applied Mathematics
\\London School of Economics
\\Houghton St. London WC2A 2AE, U.K.}

\date{}

\begin{document}

\maketitle

%\begin{abstract}

%\end{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
\cite{FaSoft}.

One parameter that contributes to the specification of an instance of the
problem is the signal-to-noise ratio (SNR). Recently some experimental work
\cite{RH} 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.

\bigskip
We begin by giving a mathematical formulation of the SNR problem.

Let $T$ be a set of transmitters located on the plane. Each transmitter
$t\in T$ has power $p(t)$, and is located on the plane at the coordinates
$\xx(t)$. Calculating the strength of a signal from a given transmitter is
another non-trivial practical problem. Here we assume that the strength
depends only on the distance to the transmitter, and on the power of the
transmitter;
%
\begin{equation}\label{SIGeq}
S_t(\xx_0)=p(t)N(|\xx_0-\xx(t)|)
\end{equation}
%
for some function $N(d)$ (we shall call it {\em propagation function})
tending to zero with $d\ra\infty$. It is often assumed in practice that
$N(d)=d^{-\a}$, where $\a$ is a constant. The value of $\a$ may vary;
usually $2<\a<4$.

In real life situations, the strength of the signal may fall at different
rates in different directions, and it may depend on the frequency of the
signal as well. Also, the picture may be different for different locations
of the transmitter.

Suppose that each transmitter is assigned a transmitting frequency (or {\em
channel}) $c(t)$. The signal-to noise ratio (SNR) at a given point $\xx_0$
is calculated in two steps. First, the tuning frequency is chosen as the
frequency of that transmitter $t_0$ whose signal at the point is the
strongest.

After choosing the tuning frequency $c_0=c(t_0)$, one calculates the SNR by
the formula
%
\begin{equation}\label{SNReq}
SNR(\xx_0)=\frac{S_{t_0}(\xx_0)}
                  {\sum_{t\neq t_0}e^{-\b|c_0-c(t)|}S_t(\xx_0)};
\end{equation}
%
where $\b$ is another experimentally determined constant.

Now we can formulate the problem. We are given: the set $T$ of transmitters
located at points $\xx(t)$ and of powers $p(t)$; a region $\Omega$ of
possible locations of receivers; the minimum allowed value $R$ of the
signal-to-noise ratio. We must find a channel assignment $c$ for which the
SNR at every point in $\Omega$ is at least $R$, and which minimizes the
span of frequencies, that is $$\max_{t\in T}c(t)-\min_{t\in T}c(t).$$

We shall denote by $V(t)$ the region in which the signal from $t$ is the
strongest; in our model (in which the propagation law does not depend on
the frequency) $V(t)$ does not depend on the chosen channel assignment.

If $\xx_0$ lies on the boundary between several regions $V(t)$ then it may
tune to either of the corresponding transmitters; in this case we shall use
the notation $SNR(\xx_0,c_0)$ where $c_0$ is the chosen tuning frequency.

In what follows we assume that all transmitters are of equal power;
$(\forall t\in T)\;p(t)=p$; and also that the region $\Omega$ is the whole
of the plane.

Then the regions $V(t)$ form the Voronoi partition of the plane with
respect to the set $T$: each $V(t)$ consists of those points which are
closer to $t$ than to any other $t'\in T$, because $S_t(x_0)$ depends only
on $|x_0-\xx(t)|$. Therefore each $V(t)$ is a convex polygon the edges of
which are straight line intervals lying on perpendicular bisectors of
certain pairs of transmitter locations.

The first problem we encounter is, given a channel assignment $c$, find the
point with the worst signal-to-noise ratio.

\begin{th}\label{th1}
Suppose that the propagation function $N(d)$ satisfies the following
condition:

$(*)$\quad The derivative $(\log N(d))'=N'(d)/N(d)$ increases
monotonically.

Then for any set $T$ of transmitters of equal power, and for any channel
assignment $c:T\ra\R$, the signal-to-noise ratio can achieve its minimum
only on the boundary of some region $V(t)$.
\end{th}

PROOF.\quad 
Instead of minimizing signal-to-noise ratio, we shall consider the
equivalent problem of maximizing noise-to-signal ratio (NSR).

Let $V=V(t_0)$, and $\xx\in V$ be an arbitrary interior point. By equations
(\ref{SNReq}) and (\ref{SIGeq}), NSR at the point $\xx$ is given by the
formula
%
\begin{equation}\label{NSReq}
NSR(\xx)=\sum_{t\neq t_0}\lambda(t)\frac{N(|\xx-\xx(t)|)}{N(|\xx-\xx(t_0)|)}
\end{equation}
%
where the factors $\lambda(t)=e^{-\b|c(t_0)-c(t)|}>0$ do not depend on the
position of $\xx$ within $V(t_0)$.

We shall show that NSR increases when $\xx$ is moved radially from $t_0$
towards the boundary of $V$; moreover, that every summand in the formula
(\ref{NSReq}) increases.

Let $r=|\xx-\xx(t)|$, $r_0=|\xx-\xx(t_0)|$. Since $\xx\in V$, we have
$r>r_0$. We need to determine the sign of the derivative of
$$\frac{N(|\xx-\xx(t)|)}{N(|\xx-\xx(t_0)|)}$$ 
in the direction of the vector $\xx-\xx(t_0)$. Let $\ph$ be the angle
between the vectors $\xx-\xx(t_0)$ and $\xx-\xx(t)$. Then the derivative is
equal to
$$\frac{N'(r)N(r_0)\cos\ph-N(r)N'(r_0)}{N(r_0)^2}=$$
$$=\frac{(\log N(r))'\cos\ph-(\log N(r_0))'}{N(r_0)/N(r)}.$$
Both derivatives in the numerator are negative; so, if $\cos\ph\leq 0$ then
the expression is obviously positive. On the other hand, if $\cos\ph>0$
then the expression is positive because of $(*)$. The theorem is proved.
\qed

In particular, condition $(*)$ of this Theorem is satisfied for any
function $N(d)=d^{-\a}$, $\a>0$. Also, $(*)$ implies that $N$ is strictly
convex on $(0,\infty)$, i.e. that its first derivative increases
monotonically.

In the case when, as it is in practical problems, the region $\Omega$ is
bounded, the theorem can still be applied; neither its formulation nor the
proof need to be changed. Indeed, the boundary of $\Omega$ is partitioned
into parts of the boundaries of adjacent Voronoi regions; and the theorem
implies that the minimum of SNR is achieved either on the edges of Voronoi
diagram or on the boundary of $\Omega$.
 
\begin{thebibliography}{9}
\bibitem{FaSoft} S.~Hurley, D.H.~Smith, S.U.~Thiel. Fasoft: A system for
discrete channel frequency assignment. 
{\em Radio Science}, 32(5), 1997, 1921--1939.

\bibitem{RH} J.~Bater, P.~Jeavons, D.~Cohen, N.~Dunkin. Are there Effective
Frequency Separation Constraints for FAPs with Irregular Tx Placements?. 
{\em Royal Holloway Technical Report}, 1998.
\end{thebibliography}
\end{document}
