Project 3-1: Information Aggregation and Diffusion Under Mobility

Principal Investigator: Leonidas Guibas (Stanford University)

Getting the information you need, when you need it, in a usable form, is a persistent challenge to effective military operations. Great strides have been made in linking individual sensors (including the human variety) into wireless networks, but the sheer amount of raw data transmitted over a large network makes it impossible for users to take in, much less interpret and use, most of the data coming in. Situational awareness demands that incoming data be timely, relevant, and interpreted in order to make quick, effective decisions. Ideally, network users should be able to respond proactively as situations arise in their areas of operation, rather than responding reactively to information that has been routed and processed through a central command.

High-performance computing (HPC) is being explored as a means of designing and optimizing large-scale simulations of communications networks, allowing developers to try out many configurations and choose the most efficient one for a given purpose. HPC resources can also be incorporated into real-world communications networks to optimize deployment and performance. Data collected during actual network operations are streamed to HPC servers at the periphery of the network for use in fine-tuning the network and adapting to changes in the environment and traffic load distributions as they occur.

Leonidas Guibas, a professor of computer science at Stanford University, is leading a group of Stanford researchers in providing low-latency, highly-specific sensor network data delivery to mobile users, in the support of live operations and live network configuration and analysis. Collaborators on this project include Phil Levis (assistant professor of computer science and electrical engineering), HyungJune Lee (graduate student, electrical engineering), Nikola Milosavljevic (graduate student, computer science), and Brano Kusy (postdoctoral associate in computer science). The group also envisions a social-network style user collaboration to aid in the interpretation of sensor data through multi-user data annotations and recommendations.

Mobile Users
In today’s sensor networks, the users don’t sit still—this is one factor that limits the performance of these networks. Existing network protocols perform progressively less well as users become more mobile, to the point where a network may be unable to find a route to a highly mobile user. Data may be sent to the wrong location or not arrive at all, congestion can develop as a result of inefficient routing, or data may need to be transmitted more than once. Any of these factors can slow the overall travel time between sender and receiver (increased latency, in the language of network designers) and waste precious network resources, such as bandwidth and battery power.

When a user (human or data-processing sensor node—a “data sink”) moves, the routing data structure must be updated, and data packets en route to the sink must be re-routed to the new location. A brute-force way to accomplish this is to distribute all the data packets all over a network cluster (cluster-wide flooding). This method is resource-intensive, to say the least. Timely prediction of the data sink’s next communication neighbor, as the sink moves around, makes more efficient use of network resources. Guibas’ group is currently exploring RSSI-based neighbor prediction techniques. (RSSI, Received Signal Strength Indication, is a measurement of the power present in a received radio signal.)

In particular, they are examining locally weighted linear regression, Gaussian process regression, and discrete path selection after global topology discovery, based on training sample sets.

Travel Time
Latency, the time it takes for a signal to travel from the sender to the receiver, depends not only on the distance traveled, but also the number of nodes along the way, the bandwidth of the communications channels, and the level of network traffic. The Stanford group is working to reduce the distance that signals must travel along low-bandwidth ZigBee links by first routing data from the originating sensor to clusterheads, which cooperate to find a cluster where the data sink is located and deliver data to this cluster over high-bandwidth Wifi links. Data packets again travel along ZigBee links in the final part of the route.

Routing data from its source to a clusterhead is straightforward from the networking point of view—any collection tree protocol works fine. However, there are several alternatives for transmitting data from a clusterhead to a sink. Guibas’ group is currently exploring cluster-wide flooding, point-to-point routing, route-to-sink along collection tree, and sink-centered collection tree approaches.

Relevant Data
Because sensors collect large amounts of data, even when nothing interesting is happening most of the time, some level of data filtering is necessary at the sensor level. The team is looking into techniques for coarsely classifying raw data streams (human, vehicle, explosion), to find abstract classifiers of data streams (flow of people, occupancy metric), and to collaboratively detect events (shot, alarm, loss of contact, wrong way motion). Clusterhead nodes can provide higher level data classification and additional reliability by fusing data from multiple sensors (total building occupancy, homing in on a shooter’s location).

Information brokerage is the technique of matching sensor data to a user’s interests. Even if most of the irrelevant sensor data are filtered out at the sensor or clusterhead level, constraints on sensor node resources do not permit high-level data interpretation. Humans can aid in the interpretation of sensor data, especially data that they can easily comprehend (images, video, or audio), but limitations on the amounts of data that can be sent over a sensor network requires that most data remain at the node. Selected data are sent to the user for interpretation, in most cases, when the user is geographically close to the sensor. Tags or labels (data annotations) can be added to aid in interpreting data, which are then transported in a compact fashion throughout the network.

Directing Traffic
If too many nodes in the network are firing (performing an action) all at once, the result can resemble rush hour in midtown Manhattan—it takes longer to transmit a signal from sensor to user, and it is much more likely for a signal to be misrouted or lost. For a network to perform efficiently, each node must fire when its neighbor is not firing. Ideally, a fast, lightweight, distributed protocol would coordinate neighboring nodes using only local connectivity information, adding a minimum of overhead in the form of communication and computation.

Desynchronization applications provide periodic resource sharing, allocate tasks among nodes, and spread the sensing burden evenly among nearby nodes to avoid redundant data collection. Each node’s on/off schedule is coordinated with its neighbor, thus lessening the chance of a collision between data packets.

The researchers use a technique in which the nodes in the network select a random firing interval. Nodes “listen” during their proposed interval and check to see if any neighbor has also claimed that interval. If the node detects no conflict, it claims that firing interval by oscillating at a common frequency, and it always fires during that chosen interval. If there is a conflict, the node selects a new trial interval with a randomized choice. This repeats until all nodes have settled on suitable firing intervals.

Power and Portability
In this context, the term “lightweight” refers to protocols and methods that maintain the longevity of the network by minimizing energy use and communicating only when necessary—radio communications are by far the most energy-consuming network operations. In a more literal sense, lightweight network nodes must be small enough to be carried by soldiers (along with their other gear) in an adversarial environment.

The nodes must rely on portable power sources, usually batteries. When a battery dies, the node dies with it. Guibas notes, “such a death can be more detrimental than just the loss of the data and sensing capabilities of the node involved; a node failure can limit the bandwidth or even disconnect the network, with more severe global consequences.”

Progress to Date
The research group is analyzing distance-sensitive algorithms for information brokerage using both theory and HPC simulation. They are investigating localized information aggregation, algorithmic enhancements to adapt all the protocols to changing environmental conditions and to user mobility patterns, and exploitation of HPC resources for network design, data mining, and network adaptation.

So far, the group has evaluated options for wireless node hardware, sensor boards for the nodes, and operating systems and programming languages. They are formulating basic information brokerage architecture and scenarios, and they are designing and implementing a simulator, with the intention of making it stable and scalable.

Later, they will design and simulate basic information brokerage mechanisms. They will develop and test low-latency information delivery techniques (routing with load balance) for static and mobile destinations. They will implement signal compression on mote (sensor node) hardware and methods for browsing remote sensor data. They will complete a stable and scalable simulator, and they will implement and demonstrate a small test-bed with real nodes.

As the project progresses, the research team will explore basic algorithmic trade-offs in information storage vs. ease of access, and they will design the architecture of a “data annotation and recommendation” system for mobile users.

Source: AHPCRC Bulletin, Vol. 1, Issue 2 (2008)