Flyphones
By Carlo Longino, Tue May 27 00:00:00 GMT 2003

New research in the mobile industry grows out of a most unlikely inspiration.


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.