# Frog calls inspire a new algorithm for wireless networks

##### July 17, 2012

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: Researchers boost efficiency of multi-hop wireless networks

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

## Related Stories

#### Researchers boost efficiency of multi-hop wireless networks

April 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

December 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 ...

#### A search engine for social networks based on the behavior of ants

June 4, 2012

Research at Carlos III University in Madrid is developing an algorithm, based on ants' behavior when they are searching for food, which accelerates the search for relationships among elements that are present in social networks.

#### Fundamental algorithm gets first improvement in 10 years

September 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 of introductory ...

February 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 could help ...

#### Variety is the spice of life: too many males, too little time...

April 23, 2008

Female Australian painted dragon lizards are polyandrous, that is, they mate with as many males as they can safely get access to. This promiscuous behaviour is often found in species where male quality is dubious and there ...

## Recommended for you

#### AT&T buying HBO and CNN owner Time Warner for \$85.4 billion

October 22, 2016

Grab some popcorn—AT&T wants to take you to the movies.

#### Ongoing cyber attack hits Twitter, Amazon, other top websites (Update)

October 21, 2016

Major internet services including Twitter, Spotify and Amazon suffered service interruptions and outages on Friday as a US internet provider came under sustained cyber attack.

#### 3-D printing and origami techniques combined in development of self-folding medical implants

October 21, 2016

Researchers at TU Delft have made flat surfaces that are 3-D printed and then 'taught' how to self- fold later. The materials are potentially very well suited for all kinds of medical implants. They report on their findings ...

#### From ancient fossils to future cars: Energy-efficient batteries from silicon in diatomaceous earth

October 21, 2016

Researchers at the University of California, Riverside's Bourns College of Engineering have developed an inexpensive, energy-efficient way to create silicon-based anodes for lithium-ion batteries from the fossilized remains ...

#### Scientists explore use of 3-D printing to speed up target production for testing material strength

October 21, 2016

Advanced 3-D printing promises to redefine manufacturing in critical industries such as aerospace, transportation and defense, and now, Lawrence Livermore National Laboratory is exploring the use of 3-D printing to achieve ...

#### Algorithm could help analyze fetal scans to determine whether interventions are warranted

October 21, 2016

Researchers from MIT, Boston Children's Hospital, and Massachusetts General Hospital have joined forces in an ambitious new project to use magnetic resonance imaging (MRI) to evaluate the health of fetuses.