RANBAR: RANSAC-based resilient aggregation in sensor networks

ABSTRACT

We present a novel outlier elimination technique designed for sensor networks. This technique is called RANBAR and it is based on the RANSAC (RANdom SAmple Consensus) paradigm, which is well-known in computer vision and in automated cartography. The RANSAC paradigm gives us a hint on how to instantiate a model if there are a lot of compromised data elements.However,the paradigm does not specify an algorithm and it uses a guess for the number of compromised elements, which is not known in general in real life environments. We developed the RANBAR algorithm following this paradigm and we eliminated the need for the guess. Our RANBAR algorithm is therefore capable to handle a high percent of outlier measurement data by leaning on only one preassumption,namely that the sample is i.i.d. in the unattacked case. We implemented the algorithm in a simulation environment and we used it to filter out outlier elements from a sample before an aggregation procedure. The aggregation function that we used was the average. We show that the algorithm guarantees a small distortion on the output of the aggregator even if almost half of the sample is compromised. Compared to other resilient aggregation algorithms, like the trimmed average and the median, our RANBAR algorithm results in smaller distortion, especially for high attack strengths.

REFERENCES

• 1: David Wagner, Resilient aggregation in sensor networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029116]
• 2: Levente Buttyan , Peter Schaffer , Istvan Vajda, Resilient Aggregation with Attack Detection in Sensor Networks, Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, p.332, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.119]
• 3: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 4: Zang Li , Wade Trappe , Yanyong Zhang , Badri Nath, Robust statistical methods for securing wireless localization in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 5: V. Bychkovskiy, S. Megerian, D. Estrin, M. Potkonjak. A collaborative approach to in-place sensor calibration. In Proceedings of the Second International Workshop on Information Processing in Sensor Networks (IPSN)2003.
• 6: A. J. Lacey, N. Pinitkarn, N. A. Thacker.An Evaluation of the Performance of RANSAC Algorithms for Stereo Camera Calibration. In Proceedings of the British Machine Vision Conference (BMVC)2000.
• 7: O. Chum, J. Matas. Randomized RANSAC with T d,d test. In Proceedings of the 13th British Machine Vision Conference (BMVC)September 2002.
• 8: J. Yan, M. Pollefeys. Articulated Motion Segmentation Using RANSAC With Priors. In Proceedings of the ICCV Workshop on Dynamical Vision 2005.
• 9: M. Zuliani,C. S. Kenney, B. S. Manjunath. The MultiRANSAC Algorithm and its Application to Detect Planar Homographies. In Proceedings of the IEEE International Conference on Image Processing September 2005.
• 10: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 11: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 12: Madhukar Anand , Zachary Ives , Insup Lee, Quantifying eavesdropping vulnerability in sensor networks, Proceedings of the 2nd international workshop on Data management for sensor networks, August 30-30, 2005, Trondheim, Norway [doi>10.1145/1080885.1080887]
• 13: Lingxuan Hu , David Evans, Secure Aggregation for Wireless Networks, Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), p.384, January 27-31, 2003
• 14: Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958521]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Algorithms, Design, Security

Keywords:
outlier elimination, random sample consensus, resilient aggregation, sensor networks