4th International ICST Conference on Security and Privacy in Communication Networks

Research Article

Securely Computing an Approximate Median in Wireless Sensor Networks

  • @INPROCEEDINGS{10.1145/1460877.1460885,
        author={Sankardas Roy and Mauro Conti and Sanjeev Setia and Sushil Jajodia},
        title={Securely Computing an Approximate Median in Wireless Sensor Networks},
        proceedings={4th International ICST Conference on Security and Privacy in Communication Networks},
        publisher={ACM},
        proceedings_a={SECURECOMM},
        year={2008},
        month={9},
        keywords={Sensor Network Security Data Aggregation Hierarchical Aggregation Attack-Resilient},
        doi={10.1145/1460877.1460885}
    }
    
  • Sankardas Roy
    Mauro Conti
    Sanjeev Setia
    Sushil Jajodia
    Year: 2008
    Securely Computing an Approximate Median in Wireless Sensor Networks
    SECURECOMM
    ACM
    DOI: 10.1145/1460877.1460885
Sankardas Roy1,*, Mauro Conti2,*, Sanjeev Setia3,*, Sushil Jajodia1,*
  • 1: Center for Secure Information Systems, George Mason University, Fairfax, VA, USA - 22030
  • 2: Center for Secure Information Systems, George Mason University, Fairfax, VA, USA - 22030 ,Dipartimento di Informatica, Università di Roma “La Sapienza”, 00198 Roma, Italy
  • 3: Department of Computer Science, George Mason University, Fairfax, VA, USA - 22030
*Contact email: sroy1@gmu.edu, conti@di.uniroma1.it, setia@gmu.edu, jajodia@gmu.edu

Abstract

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.