Making Sense of Sensors: The Mathematics of Detecting Intruders

December 7, 2006

Providence, RI:

A network of small, local sensors samples an environment at a set of nodes.
How can one answer global questions from this network of local data? Image by Robert Ghrist.

As sensor technology has exploded, such fundamental questions have come to the forefront in many areas. In particular, national security measures increasingly depend on sensor technology to detect, for example, radiological or biological hazards, hidden mines and munitions, or specific individuals in a crowd. Mathematics, especially the area of topology, provides a way of addressing such questions.

The January 2007 issue of the Notices of the AMS will carry the article "Homological Sensor Networks" by Vin de Silva and Robert Ghrist. The article describes new results by the authors, which demonstrate how homology theory provides fundamental insights useful in 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 be a region of forest, an open field, or a portion of the ocean floor. The sensors have a "broadcast radius", within which they can detect the identity of any other sensor, and a "cover radius", within which the sensors perform their sensing tasks. You can think of each sensor as surrounded by a disk whose radius is the coverage radius. The union of these disks is the "sensor cover". A basic question is, Does the sensor cover contain D ?

Topology, which is the study of shapes, is well suited to attacking this question. In particular, homology theory provides a way of detecting whether shapes contain holes. De Silva and Ghrist were able to use homology theory to pinpoint some simple topological conditions that, if met by the sensor network, guarantee that the sensor cover contains the whole domain D without holes. What is striking about this result is that it provides information about the sensor cover without 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 where the sensors are going on- and off-line periodically, so that holes open up and close in the sensor cover. Can an "evader" move through the sensor network, taking advantages of holes that open up in order to slip through undetected? The authors present topological conditions on the sensor network that guarantee that the evader will be caught, regardless of the evader's speed or cunning.

"It seems counterintuitive that one can provide rigorous answers for a network with neither localization capabilities nor distance measurements," the authors remark. "A topologist is not surprised that such coarse data can be integrated into a global picture. Some engineers are." De Silva and Ghrist call for mathematicians and engineers to collaborate on the design of effective sensor networks.

The article "Homological Sensor Networks," by de Silva and Ghrist, is available on the Notices web site at http://www.ams.org/notices/200701/fea-ghrist.pdf.

For further information, contact:

Professor Robert Ghrist
University of Illinois, Champaign-Urbana
Email: ghrist@math.uiuc.edu
Telephone: +1-217-714-2646

Professor Vin De Silva
Pomona College, Claremont, California
Email: vin.desilva@pomona.edu
Telephone: +1-909-607-8656

Public Awareness Office
American Mathematical Society
201 Charles St.
Providence, RI 02904
Email: paoffice@ams.org
Telephone: +1-401-455-4000
Fax: +1-401-331-3842

# # # #

Founded in 1888 to further mathematical research and scholarship, the 30,000-member American Mathematical Society fulfills its mission through programs and services that promote mathematical research and its uses, strengthen mathematical education, and foster awareness and appreciation of mathematics and its connections to other disciplines and to everyday life.