Yet topology, which pieces together the global structure of a space from local snapshots, is exactly what sensor-network engineers need, argues Robert Ghrist, a mathematician at the University of Illinois at Urbana-Champaign.
"Topology is good for finding hidden features inside a space that you can't see very well, that you don't have all the information about," Ghrist
Accordingly, to apply the power of these topological tools to wireless sensor networks, Ghrist
collaborators put simplices together into a theoretical shape, called the Rips complex, that captures the intricacies of how the sensors communicate with each other.
and his collaborator Vin de Silva of Pomona College in Claremont, Calif., have used the Rips complex to tackle a basic question about sensor networks: If you scatter a bucket of smart-dust particles over a field, how do you know whether their combined sensory range covers the entire region?
"We're trying to prepare for the day,and it's coming very soon,when we have millions of sensors distributed," Ghrist
Many sensor-network engineers, Ghrist
says, have assumed that it's impossible to deduce the structure of a network without knowing where every sensor is."If you don't have the sensors' coordinates, at first, it doesn't seem as if you can do much," Ghrist
Yet in the Dec. 1, 2006 International Journal of Robotics Research
and de Silva showed how to use the homology of the Rips complex to figure out whether a network has full coverage.
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 coverage but also describes the most economical collection of triangles that covers the field.Only the sensors at the corners of the triangles in that collection need operate.Any other sensors are redundant and may be put in sleep mode, saving precious battery power.
"This is a big deal because if you have millions of sensors, you want to conserve their batteries as long as you can," Ghrist
If the network has small gaps in coverage, the homology computation flags the sensors that border the gaps.Engineers then have various options, such as moving sensors into the gap
or turning up the power of nearby sensors so that they each report on a larger area."We can tell you exactly which sensors need to ramp up power, and by how much, to guarantee that the holes are filled," Ghrist
Unlike the Euler characteristic, homology is far from straightforward to calculate.Ten years ago, Ghrist
says, the homology calculations necessary for large sensor networks would have been impossible.
"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
likens the counting problem to that faced by players of Minesweeper, a popular computer game in which land mines are hidden in certain squares of a grid.
...Ghrist and Yuliy Baryshnikov of Bell Labs in Murray Hill, N.J., are using topological techniques to make inroads into this problem.
"Our results are extremely robust," Ghrist
says."We make very few assumptions about the system's capabilities."
Their theorem makes only one assumption about the targets: that the region from which a given target is visible is always a contractible shape, meaning that it could shrink to a single point without tearing or otherwise changing the shape's topology.
The trick to counting the targets is to figure out a way to integrate all the sensors' counts so that each target contributes equally to the total, just as each land mine contributes eight counts to the total in Minesweeper.Ghrist
and Baryshnikov find that this can be accomplished without knowing how the targets vary in size or shape.
The Euler characteristic holds the key.Any contractible shape, for instance, the area from which a boat is visible, has an Euler characteristic of 1.Thus, adding up all the Euler characteristics gives the total number of boats.At first glance, this may seem circular because the number of boats isn't known.
and Baryshnikov have shown that it's possible to calculate this sum using a variation of the Euler characteristic that counts the points, lines, and other simplices in the Rips complex not just once each but according to how many boats that each sensor can see.
"There's no complicated homology computation here," Ghrist
Sensor networks complicated enough to require topological analysis are right around the corner, Ghrist
"The field of sensor networks is changing very rapidly, with the kinds of stuff we're able to build growing at an exponential rate," he
...Robert GhristDepartment of Mathematics and Coordinates Science Laboratory