Science News - May 5, 2007

these topological tools to wireless sensor networks, Ghrist and his coverage but also describes the most economical collection of collaborators put simplices together into a theoretical shape, called triangles that covers the field. Only the sensors at the corners the Rips complex, that captures the intricacies of how the sensors of the triangles in that collection need operate. Any other sen-communicate with each other. sors are redundant and may be put in sleep mode, saving pre-

In the Rips complex, named after mathematician Eliyahu cious battery power.

Rips of the Hebrew University in Jerusalem, each sensor is rep- “This is a big deal because if you have millions of sensors, you resented by a corner point, and two points are connected by a want to conserve their batteries as long as you can,” Ghrist says. line if their sensors are within communication range of each If the network has small gaps in coverage, the homology com-other. putation flags the sensors that border the gaps. Engineers then

When three sensors are within range of each other, the Rips have various options, such as moving sensors into the gap or turn-complex includes a triangle with the three sensors at its corners. ing up the power of nearby sensors so that they each report on a Similarly, when four sensors are within range, the Rips complex larger area. “We can tell you exactly which sensors need to ramp includes a tetrahedron. More generally, when n sensors are within up power, and by how much, to guarantee that the holes are filled,” range, the complex includes an (n– 1)-dimensional simplex with Ghrist says.

those n corners. Unlike the Euler characteristic, In this way, the Rips complex con- homology is far from straightforward tains all the information about clus- to calculate. Ten years ago, Ghrist ters of sensors that can talk to each says, the homology calculations nec-other. Its topology, researchers are essary for large sensor networks finding, can uncover the hidden would have been impossible. How-structure of wireless sensor net- ever, with recent advances in homol-works. ogy algorithms and computer speed, a standard laptop can now compute TRIANGULAR COVERAGE Ghrist the homology of a network of 10,000 and his collaborator Vin de Silva of sensors in less than a second. Pomona College in Claremont, Calif., Ali Jadbabaie, an engineer at the have used the Rips complex to tackle a University of Pennsylvania in basicquestionaboutsensornetworks: Philadelphia, has recently taken If you scatter a bucket of smart-dust these homology algorithms a step particles over a field, how do you know farther. With his method, the sen-whether their combined sensory range sors themselves compute the net-covers the entire region? work’s homology by communicating Today, engineers typically deal with their neighbors, rather than by with this problem by equipping each relaying information to a base sta-sensor with a global-positioning tion. “This is part of a drive toward device that can report its location. more and more autonomy for sen-This approach works well for the sor networks,” he says. small-scale networks currently in Jadbabaie’s algorithm can even use, which might number a few hun- handle situations in which the sen-dred sensors. But developing minia- MINESWEEPER MATH — Eight neighbors count each sors’ positions are changing—if they ture global-positioning devices for land mine, so the sum of the counts, 32, divided by 8, yields are attached to animals, for instance, large-scale networks may be prohib- the number of land mines, 4. Real-world situations are or blown about by the wind. “We can itively expensive. more complex, with some objects getting counted by more verify on the fly, in real time, whether “We’re trying to prepare for the sensors than others are. But topological methods can you’re covering all the holes,” he says. day—and it’s coming very soon— make each object contribute equally to the total, leading The topological approach cur-when we have millions of sensors dis- to straightforward solutions of counting problems. rently makes several assumptions tributed,” Ghrist says. that don’t usually hold true in the Many sensor-network engineers, Ghrist says, have assumed physical world, cautions Gaurav Sukhatme, who studies sensor that it’s impossible to deduce the structure of a network with- networks at the University of Southern California in Los Angeles. out knowing where every sensor is. “If you don’t have the sen- For instance, the approach often assumes that a sensor detects a sors’ coordinates, at first, it doesn’t seem as if you can do much,” circular region with a sharp boundary. Real-world sensors are fre-Ghrist says. quently blocked by obstacles in some directions, and their sens-

Yet in the Dec. 1, 2006 International Journal of Robotics ing ranges tend to die off gradually rather than end abruptly. Research, Ghrist and de Silva showed how to use the homology of “That said, you have to begin somewhere,” Sukhatme says. “It’s the Rips complex to figure out whether a network has full cover- not unreasonable to start with these simplified models and then age. They needed to know only which sensors were within range chip away at the constraints to see which can be removed. I think of each other, not where each sensor was. it’s an incredibly promising start.”

For the purposes of network coverage of, say, a field of corn, the researchers considered the triangles of the Rips complex. Each triangle represents a patch of the field that is completely within range of the three sensors at the triangle’s corners. The researchers asked, “When the triangles are pieced together, does the resulting quilt cover the field or leave holes?”

E. ROELL

For a field whose perimeter is marked by sensors that are within range of their neighbors, Ghrist and de Silva have shown that unless the two-dimensional homology computation for the Rips complex comes out to zero, the triangles fully cover the field. In this case, the homology calculation not only guarantees

COUNTING GAMES Topology is also being applied to handle the data that sensor networks generate. For example, imagine that engineers are monitoring boat traffic because they want to know how many vessels are in a harbor at any moment. The engineers are using simple sensors that can keep track of how many, but not what kinds of, boats that they see. “If you’ve got two nearby sensors that each see three targets, you don’t know if they’re seeing the same three [boats] or, say, two the same and one different,” Ghrist says.