CAMBRIDGE, Mass. -- Ad hoc networks -- communication networks set up on the fly by mobile sensors -- pose problems that ordinary office networks don't. Ad hoc networks are usually decentralized, meaning that no one node knows what the network as a whole looks like.
One of the questions raised by decentralized networks is how to relay messages so that they will reliably reach all the nodes, even when the network's shape is unknown. At the ACM-SIAM Symposium on Discrete Algorithms this month, Bernhard Haeupler, a graduate student in MIT's Department of Electrical Engineering and Computer Science, won one of two best-student-paper prizes for a new algorithm that answers that question.
Haeupler's algorithm is faster than previous algorithms. But its real interest, he believes, is that it's deterministic, meaning that it will provably relay messages to every node in a network. Previous algorithms, he explains, were probabilistic: No matter how long they were allowed to run, there would always be some minuscule chance that a message didn't reach some nodes.
"In the distributed community, solving problems without randomization is often a completely different problem, and deterministic algorithms are often drastically slower," Haeupler explains. "I don't think that anyone really believed that you can do anything deterministically in this setting."
If one node in a network maintains a map of the network as a whole, then it's relatively easy to devise a deterministic message-passing algorithm. But that kind of centralization is impractical in ad hoc networks, for several reasons: Ad hoc networks are often deployed in harsh environments, such as battle zones or the ocean's depths; a supervisor node could simply get knocked offline. Many ad hoc networks -- like networks of wirelessly connected cars, or networks of swarming robots investigating an oil leak -- are constantly changing, so a network map would quickly become obsolete. Finally, devices that form ad hoc networks usually run on batteries, so power is at a premium: Even if a supervisor node could keep up with the network's changing shape, doing so might drain its battery -- and those of the nodes feeding it information.
So researchers who study ad hoc networks are generally looking for distributed algorithms, in which all the nodes perform the same simple, local task, from which the desired global behavior emerges.
As is typical in the field, Haeupler envisions communication in the network as a game that proceeds in a series of rounds, where a round is the time required for two adjacent nodes to exchange information. In the basic version of his algorithm, each node begins by selecting one neighbor and exchanging information with it for one round. Then it selects a second node, and it exchanges information with both of the nodes it's selected for two rounds each.
At this point, the node will have received information that was forwarded by its neighbors. So when it selects a third node, it chooses one from which it hasn't heard either directly or indirectly. Then it sends all its information to all three nodes, for three rounds each. The algorithm continues in this manner, selecting new nodes from which it hasn't heard and incrementing the number of rounds it uses to send information to each of them. It continues this process until it has heard, either directly or indirectly, from all of its neighbors.
Haeupler showed that the largest number of neighbors that a node will ever need to select is equivalent to the logarithm, base two, of the number of nodes in the network. And in fact, he developed an even more efficient version of the algorithm, which reduces the number of rounds that a node must spend communicating with each of its neighbors, provided it addresses them in a prescribed order. "There are some indications that this might be as fast as you can do it, but I couldn't completely prove it," Haeupler adds.
Written by: Larry Hardesty, MIT News Office