POS: A Practical Order Statistics Service for Wireless Sensor Networks

Wireless sensor networks are being deployed to monitor a wide range of environments. Since energy efficiency is critical in these deployments, previous work proposed in-network aggregation and approximation techniques to reduce the energy consumed collecting data. In-network aggregation can be used to compute statistics such as max, min, and average accurately and energy-efficiently, but it does not work well for order statistics such as median. Current approximation techniques to compute order statistics cannot deliver both good accuracy and energy efficiency. This is unfortunate because order statistics are more resilient to faulty sensor readings than max, min, or average. We present the design and implementation of POS, an innetwork service that computes accurate order statistics energy efficiently. POS returns a stream of periodic samples from any order statistic. It initially computes the value of the order statistic and then periodically runs a validation protocol to determine whether the value is still valid. If not, it uses an optimized binary search to determine the new value and then resumes periodic validation. POS uses in-network aggregation and transmission suppression to reduce communication complexity. Results from both experiments on a mote testbed and simulations show that POS can compute order statistics accurately while consuming less energy than the best techniques to compute averages in common cases.