Frog calls inspire a new algorithm for wireless networks

Jul 17, 2012
The "desynchronized" calls of the Japanese tree frog has inspired the development of an artificial intelligence algorithm. Credit: Tanaka Juuyoh

Males of the Japanese tree frog have learnt not to use their calls at the same time so that the females can distinguish between them. Scientists at the Polytechnic University of Catalonia have used this form of calling behaviour to create an algorithm that assigns colours to network nodes – an operation that can be applied to developing efficient wireless networks.

How can be coloured with the least possible number of colours without two consecutive nodes being the same colour? A team of researchers at the Polytechnic University of Catalonia have found a solution to this mathematical problem with the help of some rather special colleagues: Japanese tree frogs (Hyla japonica).

These male amphibians use their calls to attract the female, who can recognise where it comes from and then locate the suitor. The problem arises when two males are too close to one another and they use their call at the same time. The become confused and are unable to determine the location of the call. Therefore, the males have had to learn how to 'desynchronise' their calls or, in other words, not call at the same time in order for a distinction to be made.

"Since there is no system of central control organising this "desynchronisation", the mechanism may be considered as an example of natural self-organisation," explains Christian Blum. With the help of his colleague Hugo Hernández, such behaviour provided inspiration for "solving the so-called 'graph colouring problem' in an even and distributed way."

A graph is a set of connected nodes. As in the case of the 's 'desynchronised calls', operating in a 'distributed' fashion implies that there is no other way of central control that helps to solve the problem with a global vision and all the information on the situation.

In the same way, the researchers have devised a new for assigning colours to network nodes ensuring that each pair of connected nodes is not the same colour. The end goal is to generate a valid solution that uses the least amount of colours.

Application to WiFi connections

As Blum outlines, "this type of graph colouring is the formalisation of a problem that arises in many areas of the real world, such as the optimisation of modern with no predetermined structure using techniques for reducing losses in information packages and energy efficiency improvement."

This study falls under the field of 'swarm intelligence', a branch of artificial intelligence that aims to design intelligent systems with multiple agents. This is inspired by the collective behaviour of animal societies such as ant colonies, flocks of birds, shoals of fish and frogs, as in this case.

Explore further: UT Dallas professor to develop framework to protect computers' cores

More information: Hugo Hernández y Christian Blum. "Distributed Graph Coloring: An Approach Based on the Calling Behavior of Japanese Tree Frogs". Swarm Intelligence 6 (2): 117-150, 2012. Doi: 10.1007/s11721-012-0067-2

add to favorites email to friend print save as pdf

Related Stories

Researchers boost efficiency of multi-hop wireless networks

Apr 19, 2012

Multi-hop wireless networks can provide data access for large and unconventional spaces, but they have long faced significant limits on the amount of data they can transmit. Now researchers from North Carolina State University ...

Frogs use calls to find mates with matching chromosomes

Dec 27, 2011

When it comes to love songs, female tree frogs are pretty picky. According to a new study from the University of Missouri, certain female tree frogs may be remarkably attuned to the songs of mates who share the same number ...

Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple ...

How quickly things spread

Feb 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information ...

Recommended for you

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

gwrede
not rated yet Jul 17, 2012
"Frog calls inspire a new algorithm"

And not a single word about the algorithm in the article.

More news stories

LinkedIn membership hits 300 million

The career-focused social network LinkedIn announced Friday it has 300 million members, with more than half the total outside the United States.

Researchers uncover likely creator of Bitcoin

The primary author of the celebrated Bitcoin paper, and therefore probable creator of Bitcoin, is most likely Nick Szabo, a blogger and former George Washington University law professor, according to students ...

Under some LED bulbs whites aren't 'whiter than white'

For years, companies have been adding whiteners to laundry detergent, paints, plastics, paper and fabrics to make whites look "whiter than white," but now, with a switch away from incandescent and fluorescent lighting, different ...

Magnitude-7.2 earthquake shakes Mexican capital

A powerful magnitude-7.2 earthquake shook central and southern Mexico on Friday, sending panicked people into the streets. Some walls cracked and fell, but there were no reports of major damage or casualties.

Plants with dormant seeds give rise to more species

Seeds that sprout as soon as they're planted may be good news for a garden. But wild plants need to be more careful. In the wild, a plant whose seeds sprouted at the first warm spell or rainy day would risk disaster. More ...

Researchers successfully clone adult human stem cells

(Phys.org) —An international team of researchers, led by Robert Lanza, of Advanced Cell Technology, has announced that they have performed the first successful cloning of adult human skin cells into stem ...