Communications of the ACM
Breaking Bottlenecks
A new algorithm spreads information (red) much more efficiently in networks characterized by sparse connections between densely interlinked clusters.
Christine Daniloff
As sensors that do things like detect touch and motion in cell phones get smaller, cheaper and more reliable, computer manufacturers are beginning to take seriously the decade-old idea of "smart dust"—networks of tiny wireless devices that permeate the environment, monitoring everything from the structural integrity of buildings and bridges to the activity of live volcanoes. In order for such networks to make collective decisions, however—to, say, recognize that a volcano is getting restless—they need to integrate information gathered by hundreds or thousands of devices.
But networks of cheap sensors scattered in punishing and protean environments are prone to "bottlenecks," regions of sparse connectivity that all transmitted data must pass through in order to reach the whole network.
At the 2011 ACM-SIAM Symposium on Discrete Algorithms, which took place in New Orleans the weekend of Jan. 9, Keren Censor-Hillel, a postdoc at MIT’s Computer Science and Artificial Intelligence Laboratory, and Hadas Shachnai of Technion–Israel Institute of Technology presented a new algorithm that handles bottlenecks much more effectively than its predecessors.
From MIT News Office
View Full Article
No entries found