# Frog calls inspire a new algorithm for wireless networks

##### July 17, 2012, Spanish Foundation for Science and Technology (FECYT)

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

#### Engineer says new study forces researchers to rethink how elderly break their bones

January 23, 2018

To better understand why many elderly people are prone to break a bone in a fall (known as bone fragility fractures), perhaps doctors and researchers should look at the human skeleton in much the same way civil engineers ...

#### Research determines integration of plug-in electric vehicles should play a big role in future electric system planning

January 23, 2018

An influx of plug-in electric vehicles (PEVs) charging without coordination could prove challenging to the nation's electric grid, according to research conducted by the U.S. Department of Energy's National Renewable Energy ...

#### AI can read! Tech firms race to smarten up thinking machines

January 23, 2018

Seven years ago, a computer beat two human quizmasters on a "Jeopardy" challenge. Ever since, the tech industry has been training its machines to make them even better at amassing knowledge and answering questions.

#### Apple says delayed HomePod speaker ready to go

January 23, 2018

Apple said Tuesday its HomePod speaker, the digital assistant device challenging rivals from Amazon and Google, was now ready after a delay of several months.

#### Drones learn to navigate autonomously by imitating cars and bicycles

January 23, 2018

All today's commercial drones use GPS, which works fine above building roofs and in high altitudes. But what, when the drones have to navigate autonomously at low altitude among tall buildings or in the dense, unstructured ...

#### Intel halts chip flaw fix due to problem with patches

January 23, 2018

Intel on Monday called for a halt in deployment of patches for a troubling vulnerability in its computer chips because they could cause "unpredictable" problems in affected devices.