The Algorithms of Ants Applied to IoT Connectivity
Emmett Coin shares how the 'random walk' ant approach, studied by a group at MIT, could lead to more efficient and effective networking of IoT devices.
Join the DZone community and get the full member experience.Join For Free
Social insects of the order Hymenoptera, which includes honeybees and ants, need to coordinate large numbers of individuals. They require a reliable and robust communication network in order to accomplish things as a group. As it turns out, they use a method that's not too different from a Monte Carlo approach: They just walk around randomly until they bump into each other! Actually with honeybees it's a little more complicated because they operate in three dimensions, but with ants it's 2-D all the way since all of the work in a colony is accomplished by walking on surfaces.
It turns out that you can learn quite a bit about local density (and even local dimensions) by noting how often you bump into another individual who is also walking around randomly. Biologists have long understood that the simple brains of ants couldn't be doing very much more than counting encounters. This new study analyzes and quantifies the behavior in a very rigorous way.
This formal study comes from MIT's Computer Science and Artificial Intelligence Laboratory and it shows that many seemingly inconsequential encounters in the environment converge quite quickly to a scaler value that is proportional to the density of individuals. And it converges at the speed of our fastest known algorithms. It seems likely that with our growing world of less than brilliant devices (all those IoT sensors) "bumping" into each other (albeit with Wi-Fi or Bluetooth) we should be able to use these "ant" algorithms to our advantage.
"It's intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density," says Cameron Musco, an MIT graduate student in electrical engineering and computer science. "What we're doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate."
Wandering in the Wilderness
In this paper Musco, NEC Professor of Software Science and Engineering Nancy Lynch, and Hsin-Hao Su, a postdoc in Lynch's group model the system of communication on a simple grid upon which the ants can randomly wander. And the only skill required of the ant is the ability to somehow encode a parameter that is proportional to the count of their encounters. The interesting discovery is that the random walk approach is essentially just as efficient as a random sampling approach. But the added power of the random walk is that it doesn't require a priori knowledge about the other individuals in the network. So if we wanted to use this technique in a human social network, we could wander the connections of the network and tally parameters that we find at each encounter (e.g. political affiliation?) and get a good estimate of of the density of a particular political party. In order to do a random sampling, you would need a database of all of the individuals that included a data field for their political affiliation. That database may not exist.
In the context of IoT, and the very small range of individual devices, it is unlikely that there is a conventional database of all of the parameters of all of the devices. In fact, they are being added and removed continually. All we can know is that there are connections to other relatively close devices. But it is possible to send a query from device to device on a random walk and get a reasonable answer.
If you read this far, then you're probably wondering how a random walk avoids bumping into the same individuals. And intuitively you would assume that those repeat encounters would over inflate the density of the local region you are wandering around. Well, so did the researchers, and they discovered that intuition can often be very wrong. If they removed the repeat encounters the algorithm converged on the wrong answer. They explained the rationale for counting all encounters (repeats or not) as a result of not being able to penetrate the dense circle of near individuals and encounter all of the individuals even in the far reaches of the locale. To me it seemed like the ants behaved like molecules on their individual random walks and just like molecules in a gas in a container, even a small corner of the container feels the "pressure" of the density that exists across the container: Encountering the same individuals repeatedly is a manifestation of the "pressure" that is farther away. It seems obvious once you think about it.
Elegance and Simplicity
As usual, nature finds the simplest, least expensive, most robust solution to the problem at hand. I'm sure we've only scratched the surface of the secrets of the "hive mind" of social insects. I'm sure we have much more to learn from these "super organisms." It makes me feel a bit like Hari Selden.
More detailed information can be found here.
The full academic paper "Ant-Inspired Density Estimation via Random Walks," which describes all of the mathematics in great detail, can be found here.
And finally, just for fun, here are some links to more articles about ad hoc networks.
Opinions expressed by DZone contributors are their own.