L. Buttyán, P. Schaffer, I. Vajda|
RANBAR: RANSAC-Based Resilient Aggregation in Sensor Networks
In Proceedings of the Fourth ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN), 2006, ACM Press, October.
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 algo- rithm 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 algo- rithm 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 dis- tortion 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 distor- tion, especially for high attack strengths.