Communications of the ACM
Exploring Networks Efficiently
Analysis of ant colony behavior could yield better algorithms for network communication, say researchers in the Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory.
Credit: Christine Daniloff/MIT
Researchers from the Massachusetts Institute of Technology's (MIT) Computer Science and Artificial Intelligence Laboratory will present work at the upcoming ACM Symposium on Principles of Distributed Computing (PODC 2016) conference in Chicago hypothesizing that the study of ant colony behavior could lead to improved network communication algorithms.
The research is based on the theory that ants use the frequency with which they bump into other ants while randomly exploring their surroundings as a foundation for population-density estimates.
MIT graduate student Cameron Musco and colleagues use a graph of an ant's environment to outline the insect's "random walk," comparing it to random sampling. They found both methods' accuracy gets better with each additional sample while also converging on true population density at similar speeds.
Their analytic techniques are applicable to any graph, including one that describes which members of a social network are linked, or which devices in an ad hoc network are within vicinity of each other. Provided two random walks originating from the same node are likely to branch out in different directions, random walks remain virtually as proficient as random sampling, according to the researchers.
In addition, an analysis of random walks executed by a single explorer found pooling observations from many explorers would converge on an accurate estimate faster.
From MIT News
View Full Article
Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA
No entries found