Securely Computing an Approximate Median in Wireless Sensor Networks

Wireless Sensor Networks (WSNs) have proven to be useful in many applications, such as military surveillance and environment monitoring. To meet the severe energy constraints in WSNs, some researchers have proposed to use the in-network data aggregation technique (i.e., combining partial results at intermediate nodes during message routing), which significantly reduces the communication overhead. Given the lack of hardware support for tamper resistance and the unattended nature of sensor nodes, sensor network protocols need to be designed with security in mind. Recently, researchers proposed algorithms for securely computing a few aggregates, such as Sum (the sum of the sensed values), Count (number of nodes) and Average. However, to the best of our knowledge, there is no prior work which securely computes the Median, although the Median is considered to be an important aggregate. The contribution of this paper is twofold. We first propose a protocol to compute an approximate Median and verify if it has been falsified by an adversary. Then, we design an attack-resilient algorithm to compute the Median even in the presence of a few compromised nodes. We evaluate the performance and cost of our approach via both analysis and simulation. Our results show that our approach is scalable and efficient.