Frog Calls Inspire New Wireless Network Algorithm

The ‘desynchronized’ calls of the Japanese tree frog have inspired the development of an artificial intelligence algorithm
The ‘desynchronized’ calls of the Japanese tree frog have inspired the development of an artificial intelligence algorithm. Courtesy of Tanaka Juuyoh
How can network nodes be colored with the least possible number of colors without two consecutive nodes being the same color? 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 recognize where it originates 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 'desynchronize' 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 organizing this "desynchronization," the mechanism may be considered as an example of natural self-organization," explains Christian Blum. With the help of his colleague Hugo Hernández, such behavior provided inspiration for "solving the so-called 'graph coloring problem' in an even and distributed way."

A graph is a set of connected nodes. As in the case of the frog's desynchronized 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 algorithm for assigning colors to network nodes ensuring that each pair of connected nodes is not the same color. The end goal is to generate a valid solution that uses the least amount of colors.

Application to WiFi connections

As Blum outlines, "this type of graph coloring is the formalization of a problem that arises in many areas of the real world, such as the optimization 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 behavior of animal societies, such as ant colonies, flocks of birds, shoals of fish and, in this case, frogs.

Citation: 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.