Communications of the ACM
Frog Calls Inspire a New Algorithm For Wireless Networks
A Japanese tree frog whose behavior provided inspiration for solving the "graph-coloring problem" in an even and distributed way.
Credit: Kropsoq
Polytechnic University of Catalonia researchers have developed an algorithm based on the desynchronized form of calling used by Japanese tree frogs that assigns colors to network nodes, which can be applied to the development of more efficient wireless networks.
"Since there is no system of central control organizing this 'desynchronization,' the mechanism may be considered as an example of natural self-organization," says Polytechnic's Christian Blum.
He notes that this behavior provided inspiration for solving the "graph-coloring problem" in an even and distributed way. 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.
The algorithm assigns colors to network nodes and ensures that each pair of connected nodes is not the same color while generating a valid solution that uses the least amount of colors. "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," Blum says.
From Spanish Foundation for Science and Technology
View Full Article
Abstracts Copyright © 2012 Information Inc., Bethesda, Maryland, USA
No entries found