Making sense of sensors

As sensor technology has exploded, fundamental questions about how tointegrate information from many sensors have come to the forefront.In particular, national security measures increasingly depend onsensor technology to detect, for example, radiological or biologicalhazards, hidden mines and munitions, or specific individuals in acrowd. Mathematics, especially the area of topology, provides a wayof addressing such questions.

A forest ranger helicopter flies over a forest,scattering sensors that can relay temperature data to the rangerstation. To ensure minimal environmental impact with maximumrobustness, the sensors are very simple: they are basically tiny,sturdy thermometers. After the sensors are scattered, they might bemoved further by winds, rains, rivers, or even animals. Is there away to take the local information sent by the sensor network and turnit into global information about the existence and location of firesin the forest” In particular, without knowing the exact locations ofthe sensors, can one nevertheless glean information about the coveragearea of the sensor network”

As sensor technology has exploded, such fundamental questions havecome to the forefront in many areas. In particular, national securitymeasures increasingly depend on sensor technology to detect, forexample, radiological or biological hazards, hidden mines andmunitions, or specific individuals in a crowd. Mathematics,especially the area of topology, provides a way of addressing suchquestions.

The January 2007 issue of the Notices of the AMS will carry thearticle “Homological Sensor Networks” by Vin de Silva and RobertGhrist. The article describes new results by the authors, whichdemonstrate how homology theory provides fundamental insights usefulin analyzing sensor networks.

Suppose you have a network of sensors, each with a unique ID,scattered around a two-dimensional domain D—for example, D could bea region of forest, an open field, or a portion of the ocean floor.The sensors have a “broadcast radius”, within which they can detectthe identity of any other sensor, and a “cover radius”, within whichthe sensors perform their sensing tasks. You can think of each sensoras surrounded by a disk whose radius is the coverage radius. Theunion of these disks is the “sensor cover”. A basic question is, Doesthe sensor cover contain D”

Topology, which is the study of shapes, is well suited to attackingthis question. In particular, homology theory provides a way ofdetecting whether shapes contain holes. De Silva and Ghrist were ableto use homology theory to pinpoint some simple topological conditionsthat, if met by the sensor network, guarantee that the sensor covercontains the whole domain D without holes. What is striking aboutthis result is that it provides information about the sensor coverwithout requiring knowledge of the exact locations of the sensors.Only the broadcast and cover radii are needed.

De Silva and Ghrist also adapted the above result to networks wherethe sensors are going on- and off-line periodically, so that holesopen up and close in the sensor cover. Can an “evader” move throughthe sensor network, taking advantages of holes that open up in orderto slip through undetected” The authors present topologicalconditions on the sensor network that guarantee that the evader willbe caught, regardless of the evader’s speed or cunning.

“It seems counterintuitive that one can provide rigorous answers for anetwork with neither localization capabilities nor distancemeasurements,” the authors remark. “A topologist is not surprisedthat such coarse data can be integrated into a global picture. Someengineers are.” De Silva and Ghrist call for mathematicians andengineers to collaborate on the design of effective sensor networks.

Ghrist is building such collaborations as a lead investigator for aresearch project called SToMP, short for “Sensor Topology & MinimalPlanning.” Funded by the Defense Advanced Research Projects Agency(DARPA), the $7.98 million project will run over four years. SToMPwill support research at Ghrist’s home institution, the University ofIllinois at Urbana-Champaign, as well as at Bell Labs/Lucent, ArizonaState University, Rochester University, Carnegie-Mellon University,Melbourne University, the University of Pennsylvania, and theUniversity of Chicago.

Leave a Comment