Algorithms

Closest Point of Approach detection

Each individual sensor consolidates the sensor readings into a single closes point of approach time stamp for each vehicle that is detected. This is done through a combination of high-pass, and low-pass filtering of the raw magnetic readings.

Vehicle Velocity Estimation

The collection of closest point of approach time stamps are used to calculate the velocity of the object moving through the sensor field. The time stamps are combined with a position estimation vector which contains the approximate location of each of the sensor nodes. A linear regression is the performed on the data to fit a constant velocity trajectory to the sensor data.

The slope of the regression line is proportional to the velocity of the car and the intercept of the line is the time that the car passed.

Sensor Location Update

In order to update the location of the individual sensors, a the linear regression is used to determine the relative positioning of the individual sensor nodes. Over time, the position estimation vector will be updated to reflect reality. The initial position estimation vector is set to place each node 10 feet apart -- the average spacing of motes dropped from the plane.

Depicted is the adjustment of positions for motes 4 and 5 in the sensor network. Each node is simply nudged in the direction that would reduce the difference between the measured data and the linear regression.

Jason and Steve prepare the mote dropper for a launch.The motes know the order that they will be dropped in, and use that for an initial guess at their relative locations, which they update as they get more track information.

Software

Multi-hop Messaging

Time Synchronization

It is imperative that the sensor readings from the distributed sensors can be aligned in time with respect to each other. In order to accomplish this, the sensor network has a distributed clocking mechanism which keeps all node in sync with an accuracy of 1/32 of a second. This is accomplished by having each node periodically broadcast out its version of the current time. All nodes that hear the broadcast make sure that their clocks are at least caught up to the time that was broadcast. If any node has fallen behind, then it will advance its clock. This algorithm allows the entire network to synchronize itself on the clock of the fastest node. This mechanism can be used to achieve high levels of synchronization because there is very little jitter in the transmission time of the update broadcasts.

Sensor Data Acquisition and Filtering

Each axis of the magnetometers are read 32 times per second. The sensor readings are then placed into a IFR low pass filter in order to remove noise introduced by the sampling process. This filter takes the from of FILTER_VAL = (FILTER_VAL * 7 + READING)/8. Then a second filter process is run to get a lower bound on the frequency of the readings. Here, SECOND_FILTER_VAL = (SECOND_FILTER_VAL * 7 + FILTER_VAL/8. Finally, the absolute value of the difference of these two values is filtered to determine the rate of change in the frequency band being selected. If this third filter value exceeds at threshold, then we assume declare that a vechile has been detected. Here is an excerpt of the C code that is doing the filtering.

ch->first = ch->first - (ch->first >> 3);
ch->first += ch->reading;
ch->second = ch->second - (ch-> second >> 3);
ch->second += ch->first >> 3;
ch->diff = ch->diff - (ch-> diff >> 3);
tmp = ch-> first - ch-> second ;
if(tmp < 0) tmp = -tmp;
ch-> diff += tmp;

Collaborative Signal Processing

In order to determine velocity and direction of the detected vehicles, the individual sensors must collaborate. A magnetic anomaly alone does not give us any velocity information. However, by combining the sensor readings from several nodes, we are able to determine the velocity of the vehicle.

Position Estimate Update

Query Response

The vehicle detection information that is calculated by the sensor network is stored inside the network until an opportunity arises to transfer that information back to the base station. To achieve this, each node remembers the velocity vector information that is calculated in a local EE prom. At a later time it will report that information in response to a query on the network. In our demonstration, the query originates from a mote attached to the UAV as it flies over. As the plane passes over the sensor network, it issues queries to the sensor nodes asking for a report of the vehicles that have been detected. At this time the sensor nodes stream the data out of their EE proms and up to the mote on the plane. The same process is used as the plane passes over the base station. In this case the base station issues the query while the plane responds. I short, the plane flies over the sensor network and picks up the data. It then flies over the base station and deposits the data.

Code Size and Component Graph

Here is a graph of the TinyOS components that went into this application.

And we still had 80 bytes of program memory left!