MIT researchers: Network pros could learn a lot from ants
Source: Steven Depolo
How ants decide where to move their nests may hold lessons for computer scientists seeking efficient ways to gather data from distributed networks of sensors, according to MIT researchers.
It turns out that the frequency with which explorer ants bump into each other as they wander around looking for a new home for their colony is a pretty good indicator of how many other explorer ants are investigating the same site.
When enough convene in one area, the workers in the ant colony pick up the sedentary queen ant and carry her to the chosen location, says Cameron Musco, an MIT graduate student in electrical engineering and computer science and a co-author of a theoretical paper that examines the math behind why this behavior is an efficient way to estimate the density of a population.
Apparently their roaming and chance bumping into each other – which the researchers call random walks – helps give the ants a sense of whether a critical mass of their colleagues are also interested the new site, he says.
Musco and his colleagues imitated the ants’ behavior with a mathematical model of random walks in which an area is divided up into a grid of nodes, each node connected to a set of other nodes. In the random walk their model ants can move to any other node that is connected to the one where they are located, including the one they just left.
Relatively quickly, the frequency with which they run into other ants offers up a reliable estimate of how many other ants are in the area, according to the algorithm the team developed, he says.
This theory can be applied to ad hoc networks of sensors to efficiently gather data. For instance, sensors gathering data about humidity could pass a token to each other in a random-walk fashion and after a while one of the sensors could send back a tally of how many registered humidity breaking a certain threshold. That would give a reliable indication of whether humidity had reached a certain level in that area, he says.
Also, the method would require no central hub connecting all the sensors, streamlining the network and simplifying communication.
He says random walks can produce estimates about as accurate as random sampling, which is polling a set of randomly chosen nodes in a network. That makes the method useful in networks where it’s impossible to randomly sample because there is no comprehensive list of elements in the network.
For example, it could be used if someone wanted to find the political leanings of members of a social network for which there is no central list available, making it impossible to create a random sample, But a random walk could deliver the information by moving from an individual to that person’s contacts, to their contacts and so on, tallying how often they run into Democrats and Republicans.
Musco says his group at MIT’s Computer Science and Artificial Intelligence Laboratory try to find behaviors in biology that can be applied to computer science and vice versa. In this case the ants’ behavior has a useful application for computer scientists. The flip side is that the algorithm the researchers developed helps bolster biologists’ hypotheses about what explorer ants are up to when they move around seeking a new nesting site.
| }
|