Male frog calls answer network node problem

How can network nodes be coloured with the least possible number of colours without two consecutive nodes being the same colour? A team of researchers have found a solution with the help of some special tree frogs.

Male Japanese tree frogs (Hyla japonica) 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.

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 females 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”.

In the same way, the researchers have devised an algorithm 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.

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 wireless networks 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, of course, frogs.