Technology research generally takes on
familiar forms - trying to improve processor speed by increasing the
number of transistors or by using new materials, developing better
computer models to predict behavior, or honing millions of lines of
code. But inspiration can and does come from anywhere, and one emerging
form of research hopes to apply decidedly non-digital solutions to our
digital world.
Nature-inspired computing aims to solve technical
problems by using biologically rooted solutions. This doesn't mean
using a running hamster to turn a wheel to power a mobile phone, but
rather deriving algorithms from natural functions and using them to
answer technical questions. BTexact Technologies, the research arm of
British Telecom, is a leader in the field, and has found a novel
approach to tackle a huge computational problem in mobile
networks.
Coloring the Map
In
a mobile phone network, handsets communicate with base stations via
radio. Each operator's band of spectrum is split up into a number
of different channels so that many users can make calls at any given
time. Each user's call takes up one channel, so users can't
hear simultaneous calls on other channels. Two users can use the same
channel, though, given that they're far enough apart
geographically. Network operators must configure the base stations in
their network so that each has enough channels (and therefore capacity)
to meet demand, while also making sure neighboring stations aren't
using the same channels, causing interference and overlapping
calls.
Mobile operators currently use "static"
allocation plans. This means that channels are allocated to stations
according to a specific plan, and remain that way until the plan is
review and allocations changed. Plans are typically formed by reviewing
usage statistics, subscriber demographics and call locations, then the
data fed into a computer that comes up with a plan, not unlike a
schoolchild coloring in a map, being careful not to put two areas of the
same color (or same channel) next to each other. But keep in mind that
the computer doesn't have the benefit of the 64-color deluxe
Crayola crayon box; spectrum is a finite resource and each base station
must use several channels, not just one.
This current plan has a
few disadvantages - first off, its static nature means that it
can't adapt to changes in network traffic and usage, even if those
changes are predictable. Also, a centralized model such as this depends
on the decision-maker being fed accurate and up-to-date information.
This means the operator must collect, maintain, and ensure the accuracy
of its data, and even then resolving which base stations are far enough
apart is difficult, requiring a combination of measurements and complex
radio wave propagation models.
Dynamic allocation is clearly
much more attractive - it can reduce the number of blocked calls and
engaged channels by simply redistributing existing capacity, making the
network much more efficient in real-time. This means the network can
quickly realign itself to deal with "scheduled" changes in
network needs, such as increased demand along motorways and in
transportation centers during commuter rush hours, or during outdoor
sporting events or concerts.
But it also means the network can
quickly deal with "unscheduled" spikes in demand. Imagine
there's a car accident on the motorway in a rural area that stops
or delays traffic - the number of call attempts will increase with
people phoning ahead to say they'll be late, or simply chatting to
kill time in a traffic jam. With a static allocation plan, a rural
station along a motorway would likely not be allocated sufficient
channels to handle such call volume, resulting in many calls being
unable to get through. But a dynamic plan would recognize the increased
call volume and assign more capacity to the relevant base
stations.
Waiter, There's a Fly In MyPhone
Richard Tateson, a researcher in
BTexact's Future Technologies Group, was sitting in a seminar
discussing this very situation and some different techniques to solve
it. It struck him that a letting the stations figure the allocation out
among themselves would be an ideal solution.
This line of
thinking wasn't new to the mobile telecom industry, but Tateson
wasn't to know that. He'd been hired by BT as part of an
"Artificial Life" group examining nature-inspired computing
ideas, and had a PhD from Cambridge in zoology, not network engineering.
His specialized PhD work was in fruit fly (Drosophilia) development, and
he realized that a process called lateral (or mutual) inhibition could
be applied to the problem.
Mutual inhibition goes on a various
stages of animal development. When a fruit fly's exoskeleton is
developing, parts of it will grow into sensors formed from short
bristles attached to nerve cells, while other parts grow into a
protective, insensitive exoskeleton. It's important that the
bristles be evenly spread out across the surface of the fly; it's
particularly important that two bristles not grow in adjacent cells.
The cells themselves work out the correct pattern during the
fly's growth by "arguing" among each other by way of
cellular secretions. They all send secretions that act as inhibitory
signals to their neighbors autonomously, using information from its own
little environment, gathered by listening to its neighbors - the more
loudly an individual cell hears its neighbors saying they want to make
bristles, the quieter it is.
High levels of the signal in two
or more neighboring cells create an unstable condition, and of course,
nature tends to move towards the more stable situation, where only one
of the cells continues to generate high levels of the signal.
Ultimately, most cells are inhibited, but a few win out and make
bristles.
Tateson thought the base station programming problem
could be approached in a similar vein: "It seemed to me that the
choice of which channel to use (in the base station) was analogous to
the choice of which cell fate to choose (by the cells in a fruit
fly)," he said. "So I wrote a simulation program to show that
this type of problem could indeed be solved by using the distributed
'fruit fly' algorithm."
Fly Me tothe Moon
In this inspired-inspired solution, base
stations (which are equated to the cells) are given the ability to
choose the channels they will use. They then "argue" with
their neighbors for each channel, and the louder its neighbors argue for
a channel, the less it will press for it. While in the beginning, all
the base stations have a roughly equal claim to all the channels, as
time goes on, a station will drop its claim to certain channels and
increase its preference for a few specific channels. Neighboring base
stations won't use the same channels; just as neighboring cells
won't both develop bristles.
"As far as this specific
method goes, the biggest potential for advantages in a functioning
network come from the distributed and dynamic approach to solving the
problem," Tateson says. "Nature-inspired techniques map on to
these well, and in this case have provided an example which allowed
rapid prototyping of a functioning simulation. Nature has given us the
application, is you like, and we have to see the analogy and apply
it."
This dynamic solution updates in real time. As network
demand changes, the channel usage by different base stations will
change. When demand falls in one area, a station can give up channels;
when demand increases in an area, a station can grab more channels and
increase its capacity. Likewise, if a station fails, it will simply give
up its channels instead of hanging on to channels that cannot be used by
other stations in the area, and if a new station is added, it negotiates
with other stations in the area for channels. But perhaps the most
important aspect of the solution is that as the network grows, the
allocation problem and the time required to solve it does
not.
"Dynamic problem-solving allows the network to shift
its resources to where they're needed most - which means there
should be fewer blocked calls," Tateson adds. "Distributed
problem-solving allows the network to continue to function efficiently
as it changes in an unplanned way without any need to update a central
'brain' about the state of every base
station."
Learning FromNature
This type of autonomous system may find a
multitude of other applications. One would be to incorporate it into
computer security systems - each computer would send out certain signals
to its neighbors if all systems are running normally and there are no
problems. Then, if there is a break-in attempt or other security event,
or the signal stopped altogether, other computers on the network would
raise their "vigilance" against attacks.
But one
problem with such autonomous systems is that people are not often
comfortable relinquishing so much control to machines. "One
drawback of nature-inspired solutions in general is that they are often
hard to engineer or control centrally - they are best applied to
problems where 'traditional' engineered solutions struggle or
fail," Tateson says. "This really just is the other side of
the coin - you are getting autonomous, embedded system management, and
to get this you have to relinquish some
control."
Carlo
Longino is a freelance writer based in Austin, Texas. His
previous experience includes work for The Wall Street Journal, Dow
Jones Newswires, and Hoover's Online.