Distributed Computing Provides the Net(ted) Result

By Bryan George, Brian Flanagan, and Burhan Necioglu

In previous articles we have offered examples of netted sensors tracking pedestrians crossing a parking lot, terrorists breaching the border, and trucks rumbling over the desert. But just how do tiny low-powered sensors collaborate to detect, track, and identify targets? How do netted systems multiply the capabilities of individual sensors? How exactly does a netted sensor system differ from traditional distributed sensor systems?

Let's examine the last question first, because the answer will help us better understand the other questions: Traditional distributed sensor systems rely on a centralized computing model, in which sensors route information across a hub-and-spoke network to highly capable processing centers where information is fused, extracted, and disseminated. By contrast, netted sensors use a distributed computing model in which sensor nodes individually process data and pool their information with other nodes using machine-to-machine collaboration.

While offering many advantages in flexibility, adaptability, and resource consumption, the distributed computing model provides significant challenges for developers, since it requires complete integration with network, communications, information management, and resource management functions. MITRE's Netted Sensors Initiative is developing tools, techniques, and algorithms to address the difficult technical problems complete integration presents. Let's review some of them.

The Truck in the Desert

Suppose we use a scenario from a previous article ("Sensor Networks that 'Think'"), where a network of Tier 1 sensors with limited computational, communications, and power resources is attempting to track and identify a truck suspected of smuggling arms from Syria into Iraq. For the netted sensor system to succeed, the sensors will need to be capable of the following tasks:

· Become aware of their own positions so their estimates of the
truck's position are accurate
· Develop an understanding of the sensor network grid topology so they may better localize the truck
· Manage dynamic target information within the sensor network

To provide netted sensor systems with these capabilities MITRE is developing the necessary distributed algorithms.

You Are Here

For sensors to collaborate effectively, they need to know approximately where they are located, particularly in relation to each other. One way to solve this problem is to place global positioning system (GPS) receivers on every node. There are several drawbacks to this solution, however. Not only does it add to the cost, size, and power requirements of every sensor node, it doesn't work inside of buildings or other GPS-denied areas.

It's possible for nodes in a sensor network to self-localize by transmitting radio signals. The receiving nodes measure the time required for the message to travel from the transmitting node to the receiving node, a method of time measurement called Time Difference of Arrival (TDOA). Unfortunately, TDOA requires time synchronization capability well beyond that of small sensor nodes. Since the speed of sound is relatively slow, one way to achieve precise TDOA with relatively imprecise timing is to transmit an acoustic tone. This approach has very limited range, however, and fails in environments where echoes are present.

Employing a standard technique used in radar, MITRE has significantly improved acoustic TDOA performance by replacing the acoustic tone with a frequency modulated chirp. This solution results in increased range—greater than 25 meters—and more robust performance in both indoor and urban locations.

Topology 101

Once the location of each node is known, every device must learn the location of its neighbors; the network needs to discover its grid topology. MITRE's method for this employs a geometric structure called the Voronoi diagram. Basically, each node is pictured as surrounded by a polygon. Imagine them as bathroom tiles laid out on the floor. The pattern of the tiles (the Voronoi diagram) spells out for each node which other nodes lay within its "regions of influence."

Using MITRE's method, each node broadcasts its location coordinates while listening for the broadcasts from other sensors in the field. These broadcasts are repeated over and over as nodes test and eliminate nodes that are not their nearest neighbors. The Voronoi diagram is adjusted at each broadcast based on whether new estimates of node locations fall within an existing polygon. It's like moving your bathroom tiles around to obtain the right shape before finally gluing them into place.

Smile for the Cameras

Once the nodes know where they are and where all the other nodes are, the next step for the sensors is to collaborate to form a "picture" of the truck moving across their sensor field in the desert. A moving target in a netted sensor field has a distinctive footprint—a spatial and temporal signature distributed across a number of sensors. The netted sensor system needs to use this signature to determine whether it has spotted a truck or a big, noisy mule.

Our approach to forming a picture is based on the notion of dynamic distributed detection groups. At each node, an acoustic signal detector sends a detection message to its grid neighbors when it believes a signal is present. Once a certain number of nodes post detections, a detection group is declared and its status is broadcast throughout the field. To accommodate target movement through the field, a node will join an existing group if it's a neighbor of an existing group.

The Trouble with Tracking

Once the nodes agree they're all seeing a truck, they have to figure out where it's going. In theory, this can be accomplished by broadcasting time-stamped signal samples between group members and forming position estimates over time from this shared information. However, given the energy-constrained distributed computing abilities of a netted sensor system, this isn't as easy as it sounds. First, the amount of message traffic required to share amplitude information at rapid intervals quickly becomes prohibitive. For this reason, we compress amplitude information into signal frames that are shared among group members. Traffic isn't the only concern. In multi-hop networks, broadcast information is particularly subject to network latency. For this reason, buffering and synchronization of distributed operations is crucial to avoid information loss and timing errors. Then there is the likelihood information will be lost in the network, which forces us to introduce network error detection and correction mechanisms.

Once signal frames have been shared among group members, we perform coarse target localization. When coupled with an estimation error measure, the system can produce accurate estimates of target location and is able to differentiate easily between estimates associated with targets within the network and estimates produced by diffuse or external sources such as wind gusts or explosions.

It takes a lot of teamwork and ingenuity for a bunch of tiny sensors scattered in the desert to locate, identify, and track an armed smuggler's truck. But luckily, teamwork and ingenuity are two things both MITRE and the Netted Sensors Initiative possess in abundance.

For more information, please contact Bryan George, Brian Flanagan or Burhan Necioglu using the employee directory.

Solutions That Make a Difference.®
Copyright © 1997-2013, The MITRE Corporation. All rights reserved.
MITRE is a registered trademark of The MITRE Corporation.
Material on this site may be copied and distributed with permission only.

Privacy Policy | Contact Us