System Model: PRESTO envisions a two-tier data management architecture comprising a number of sensor proxies, each controlling several tens of remote sensors (see Figure 1). Proxies at the upper tier are assumed to be rich in computational, communication, and storage resources and can use them continuously. The task of this tier is to gather data from the lower tier and answer queries posed by users or the application. A typical proxy configuration may be comprised of an Intel Stargate [21] node with multiple radios--an 802.11 radio that connects it to an IP network and a low-power 802.15.4 radio that connects it to sensors in the lower tier. Proxies are assumed to be tethered or powered by a solar cell. A typical deployment will consist of multiple geographically distributed proxies, each managing tens of sensors in its vicinity. In contrast, PRESTO sensors are assumed to be low-power nodes, such as Telos Motes [18], equipped with one or more sensors, a micro-controller, flash storage and a wireless radio. The task of this tier is to sense data, transmit it to proxies when appropriate, while archiving all data locally in flash storage. The primary constraint at this tier is energy--sensor nodes are assumed to be untethered, and hence battery-powered, with a limited lifetime. Sensors are assumed to be deployed in a multi-hop configuration and are aggressively duty-cycled; standard multi-hop routing and duty-cycled MAC protocols can be used for this purpose. Since communication is generally more expensive than processing or storage [5], PRESTO sensors attempt to trade communication for computation or storage, whenever possible.
System Operation: Assuming such an environment, each PRESTO
proxy constructs a model of the data observed at each sensor. The
model uses correlations in the past observations to predict the value
likely to be seen at any future instant 
. The model and its
parameters are transmitted to each sensor. The sensor then executes
the model as follows: at each sampling instant , the actual sensed
value is compared to the value predicted by the model. If the
difference between the two exceed a threshold, the model is deemed to
have ``failed'' to accurately predict that value and the sensed value
is pushed to the proxy. In contrast, if the difference between the two
is smaller than a threshold, then the model is assumed to be accurate
for that time instant. In this case, the sensor archives the data
locally in flash storage and does not transmit it to the proxy. Since
the model is also known to the proxy, the proxy can compute the
predicted value and use it as an approximation of the actual
observation when answering queries.
Thus, so long as the model accurately predicts observed values,
no communication is necessary between the sensor and the proxy; the
proxy continues to use the predictions to respond to
queries. Further, any deviations from the model are always reported to
the proxy and anomalous trends are quickly detected as a result.
Given such a model-driven push technique, a query arriving at the proxy is processed as follows. PRESTO assumes that each query specifies a tolerance on the error it is willing to accept. Our models are capable of generating a confidence interval for each predicted value. The PRESTO proxy compares the query error tolerance with the confidence intervals and uses the model predictions so long at the query error tolerance is not violated. If the query demands a higher precision, the proxy simply pulls the actual sensed values from the remote sensors and uses these values to process the query. Every prediction made by the model is cached at the proxy; the cache also contains all values that were either pushed or pulled from the remote sensors. This cached data is used to respond to historical queries so long as query precision is not violated, otherwise the corresponding data is pulled from the local archive at the sensors.
Since trends in sensed values may change over time, a model constructed using historical data may no longer reflect current trends. A novel aspect of PRESTO is that it updates the model parameters online so that the model can continue to reflect current observed trends. Upon receiving a certain number of updates from a sensor, the proxy uses these new values to refine the parameters of the model. These parameters are then conveyed back to the corresponding sensor, when then uses them to push subsequent values. Thus, our approach incorporates active feedback between the proxy and each sensor--the model parameters are used to determine which data values get pushed to the proxy, and the pushed values are used to compute the new parameters of the model. If the precision demanded by queries also changes over time, the thresholds used by sensors to determine which values should be pushed are also adapted accordingly--higher precision results in smaller thresholds. Next, we present the design of the PRESTO proxy and sensor in detail.
