A little history

It is one hundred years since the first experiments using radio as a means of communication.

To most people, the inventor of radio (or wireless telegraphy, as it was then called) was the Italian, Guglielmo Marconi (1874-1937). As so often with important discoveries, the groundwork was laid by several people over a period of years. In this case, Heinrich Hertz (1857-1894) and Oliver Lodge (1851-1940) had managed to transmit radio waves in laboratory experiments in the late 1880s and early 1890s, but failed to exploit the practical consequences.

Hertz did not even live to see the full impact of his work, but he does have his name remembered in the units of frequency; and the family received further recognition later, when his nephew Gustav Hertz (1887-1975) won the Nobel Prize for Physics in 1925.

Marconi certainly realised the possibilities for the new technology. In September 1899, he generated considerable excitement by equipping ships to provide progress reports on the race for yachting's America's Cup. In 1901, he managed to send a signal across the Atlantic. These early transmissions were in Morse code rather than speech, but that followed in due course.

Marconi continued to set new distance records, culminating in sending a message from England to Australia in 1918. He was able to achieve such large distances by exploiting the way that radio waves propagate in the upper atmosphere, so "bending" them around the Earth's surface. But please don't talk about sending messages over the "airwaves" - radio waves are part of the electromagnetic spectrum and need no air or anything else to carry them!

Most of the early applications were to shipping, and later to aviation, once passenger flight became common. However, it was not long before the possibilities for entertainment broadcasts were realised. In 1916, David Sarnaff, an employee of the American Marconi Company, suggested a "radio music box", in terms that will be instantly recognisable:

... this device must be arranged to receive on several wavelengths with the throw of a switch or the pressing of a button. The radio music box can be supplied with amplifying tubes and a loudspeaking telephone, all of which can be neatly mounted in a box.

Radio was now well established and quickly becoming indispensable.

A little physics

Let's have a closer look at the electromagnetic spectrum:

Electromagnetic waves have a frequency $f$ (measured in Hertz, usually abbreviated to Hz) and a wavelength $\lambda$. The equation relating them is \begin{equation*} c=f\lambda \end{equation*} where $c$ is the speed of light, approximately $3\times 10^8 ms^{-1}$. Since $c$ is constant, low frequencies correspond to long wavelengths and vice-versa. If we lay out the spectrum with low frequencies at the bottom, then visible light is somewhere in the middle: above are ultraviolet, X-rays and gamma-rays; below are infrared, microwaves and radio waves. \par We think of these waves as being very different, because we use them for different purposes - after all, it would be rather dangerous to try to send messages to each other via gamma-rays! However, they are all described by the same mathematical theory, developed in the 19th century by James Clerk Maxwell and others. \par The waves used for communication are those below visible light in the spectrum - not just those that textbooks call radio waves, but microwaves and infrared too: in other words anything with a wavelength longer than about $10^{-6}$ metres, or equivalently a frequency lower than about $3\times 10^{14}$ Hz. The longest useful wavelengths are about 10,000 metres, meaning the usable spectrum covers about ten orders of magnitude!

Particular wavelengths are suited to particular applications. Very roughly, long wavelengths are better suited to applications that require transmission over large distances. For this reason, applications of infrared waves are currently somewhat limited, but an important one to those who like the easy life is in remote controllers for TV sets. Microwaves are used mainly for point-to-point transmission, in which radio makes an efficient alternative to laying a wire or cable between two points. The lower frequencies making up "traditional" radio waves are used for radio and TV broadcasting, air and sea navigation, meteorology, paging, mobile telephones and various other private uses.

How do radio waves carry speech, TV pictures or other data? In engineering-speak, information is "modulated" on to a "carrier" wave. The carrier is a pure sine wave, with some fixed frequency and amplitude. The modulation makes slight changes in some property of the wave, depending on the information to be transmitted. For example, in long or medium wave radio (more usefully called AM, for Amplitude Modulation), it is fluctuations in amplitude that are used, on carrier waves of a few hundred kilohertz (kHz); FM (Frequency Modulated) radio uses fluctuations of frequency and carrier waves of around 100 megahertz (MHz).

Mathematicians prefer to think about the so-called Fourier decomposition of the radio signal, which indicates how the radio signal is made up of a mixture of different frequencies. An unmodulated wave has just a single frequency, namely that of the carrier, but any modulation scheme will cause the signal to be slightly "spread out" around the carrier frequency. In other words, the information is actually transmitted on a small range of frequencies, which make up a radio "channel". Think of the channel as a pipe; its width is called the "bandwidth". Wide pipes can carry more information than narrow pipes. Speech can be transmitted using bandwidths of 4-5 kHz; AM radio in the United Kingdom has a bandwidth of 9kHz; FM radio has a bandwidth of 50kHz (and correspondingly higher sound quality); (analogue) TV channels are much wider, at 5MHz, since video contains more information than audio.

A little politics

To accommodate many users simultaneously in the spectrum, we would like to give them all their own channel, but there simply are not enough channels to go round. As early as 1925, Herbert Hoover, then US Secretary of Commerce, was concerned that there was no more spectrum available (and that was before the invention of television!). Fortunately, he was pessimistic. Advances in radio equipment have meant that we can now use higher frequencies than in the 1920s, and use them more efficiently. Nevertheless, in the late 1990s, even arch-optimists would concede that the spectrum is now acutely congested.

Congestion in the spectrum means it is increasingly difficult to avoid the radio interference caused when two people, geographically nearby, try to use the same channel for different purposes. There can also be interference caused by signals "spilling over" into adjacent channels, although this is generally less of a problem. After the invention of radio, it was quickly realised that international cooperation was needed to help reduce interference. The first conference on regulation of the spectrum was held in Berlin in 1903. Spectrum regulation is now a crucial activity all over the world, with international coordination being provided by the International Telecommunications Union, based in Geneva.

In the UK, our interests are looked after by the Radiocommunications Agency, an executive agency of the Department for Trade and Industry. Their web site gives a good feel for the many issues involved in managing the spectrum.

A little mathematics

That's enough history, physics and politics. How can mathematics help? The crucial notion is the radio channel. It means we are not concerned with a continuous range of frequency, but with a discrete set of channels at regularly spaced intervals. To make a mathematical description, we therefore use discrete mathematics, where the techniques are very different from those of continuous mathematics.

The problem of deciding which radio channels to use at different locations is usually called the channel assignment problem. A possible mathematical description is the following. Construct a "graph" (nothing to do with the graphs that have pairs of axes) by having a "node" for each radio transmitter, and joining two nodes with an "edge" if the two corresponding transmitters would interfere if they were assigned the same channel. We now have to assign channels to nodes so that any nodes that are "adjacent", that is joined by an edge, get different channels. Then there will be no interference. To conserve spectrum, we also want to use as few different channels as possible.

Mathematically, this is the famous graph-colouring problem (at least it is if we think of channels being represented by different colours). We need to colour each node in the graph so that any two nodes which are joined by an edge have different colours, using as few colours overall as possible. A problem for which the minimum number of colours is four is shown in figure 2.

Graph-colouring has had a long and often controversial history, largely as a result of attempts to prove the map-colouring theorem, which says that in the special case when edges never cross, no more than four colours are required. However, in the channel assignment setting, this special case does not generally apply.

A little computer science

How hard is the graph-colouring problem? Answer: very hard, in the sense that it takes a lot of computer time to solve. The business of classifying problems according to how long they take to solve is relatively recent, tied in with the development of computer science as an academic discipline. We can think of problems being solved by various different methods, or algorithms, implemented in practice by turning them into computer programs.

The running time, $T$, of an algorithm, generally depends on the size of the problem we are trying to solve. For channel assignment, the size of a problem might be measured by the number of transmitters, $n$ say. Then $T$ is really a function of $n$, written $T\left(n\right)$. To rule out any ambiguity caused by variations in the intrinsic speed of computer processors, $T\left(n\right)$ is taken to measure the number of steps in the calculation, not the actual elapsed time. We are interested in how $T\left(n\right)$ increases as $n$ gets large. For channel assignment, we would like to get up to a few hundred transmitters at least.

Graph-colouring is hard because all known algorithms take a time at least exponential in $n$, meaning $T\left(n\right)$ increases like $\alpha^{n}$ for some constant $\alpha$. This is bad news. In contrast, a polynomial time algorithm $T\left(n\right)$, increasing like $n^k$ for some constant $k$, would be considered good news. \par As an illustration suppose we compare the functions $n^6$ (polynomial) and $2^n$ (exponential) for $n$ between 2 and 50. Using a logarithmic scale, these are shown in figure 3. Up to ${n=29}$ the polynomial algorithm is slower, but beyond that point it really comes into its own. Suppose we had a computer that could perform $10^9$ steps per second, and we were prepared to wait a whole day for the calculation to complete (this represents a fast computer and a lot of patience on our part). Then the polynomial algorithm would be able to deal with problems up to ${n=210}$; the exponential algorithm would only get up to ${n=46}$. If we wanted to deal with ${n=250}$, which would still be a modest channel assignment problem, the polynomial algorithm would take a little under 3 days, and the exponential algorithm more than $10^{58}$ years! Compare this with the age of the universe, which is about $10^{9}$ years, and you can see why the fact that all algorithms for graph-colouring are exponential is such bad news.

In fact, it has not been conclusively proved that there is no prospect of ever having a polynomial algorithm for graph-colouring (or a whole host of other similar problems). It may be simply that no-one has been clever enough yet to find one, but in the meantime we have to deal with the situation as best we can. The technical name for this important unsolved question, probably the most important in the whole of theoretical computer science, is the P/NP problem. For more information, see Computers and Intractability by M.R.Garey and D.S.Johnson (Freeman, 1979).

Examples of channel assignment

The practical implications for channel assignment are that we cannot give absolute guarantees to use as little spectrum as possible. But in many cases it is possible to show that assignments obtained in polynomial time are close to optimal, in the sense that they use only a few channels more than the absolute minimum, even though that value remains unknown.

Another ray of hope is that even though there is no algorithm that takes polynomial time on every graph-colouring problem, perhaps the story is different when restricting attention to those problems that arise from channel assignment problems. The graphs that arise are somehow determined by the physical laws governing radio signal propagation, but it is not yet understood exactly what the link is or how to exploit it effectively when designing algorithms.

As an example of what can happen in restricted cases, suppose the graph corresponds to a regular layout of transmitters, so each one is at the centre of a hexagonal "cell" (figure 4). The distance between neighbouring transmitters is defined to be 1 unit. Suppose that to avoid interference, the channels assigned to transmitters at or closer than 3 units must be different, and also that the channels assigned to transmitters strictly closer than 2 units must be at least 2 apart (this last condition is an added ingredient, to control "spill-over" interference between adjacent channels). Then the minimum number of channels is 12, as shown in the figure. Try to

• convince yourself that these conditions are satisfied;

• find the pattern in the assignment (the pink region should help);

• convince yourself that the pattern could be repeated indefinitely;

• show that no fewer than 12 channels will do (again, the pink region is the key).

So far, no mention has been made of how assignments might change with time, but many modern radio systems are highly dynamic. So, while BBC Radio 1 transmits on the same channel from one day to the next, perhaps being moved every few years and only then after plenty of warning, mobile telephones, for example, are assigned a new channel every time a call is made. The channel chosen is generally different every time. The calculation of optimal dynamic assignments is even less well understood than for fixed systems.

Some systems split channels into bundles, reserved for particular transmitters. The bundles are constructed so that interference never occurs. These channels then act like conventional telephone lines; if all are busy then the call is blocked. The probability of being blocked is given by the famous Erlang formula (see Call routing in telephone networks by Richard Gibbens and Stephen Turner, PASS Maths Issue 2).

Other strategies allow a much more flexible assignment, but then regular checks are needed to avoid interference. For a "live" demonstration of dynamic channel assignment, using a technique called reinforcement learning, try the Java simulation written by Satinder Singh of the University of Colorado.

Related reading

Hedy Lamarr

The military need to keep changing the frequencies of their transmissions to avoid interception by the enemy. Hedy Lemarr, an actress in 1930s and 40s films, invented a "frequency-hopping" method which kept the opposition on their toes, and is now also used in wireless data transfers between computers.

---

About the author

Dr. Robert Leese is a tutor in Mathematics at St Catherine's College, The University of Oxford, and has collaborated for several years with the UK Radiocommunications Agency on problems in radio channel assignment.