A probabilistic method for cooperative hierarchical aggregation of data in VANETs

We propose an algorithm for the hierarchical aggregation of observations in dissemination-based, distributed traffic information systems. Instead of transmitting observed parameters directly, we propose soft-state sketches—an extension of Flajolet–Martin sketches—as a probabilistic approximation. This data representation is duplicate insensitive, a trait that overcomes two central problems of existing aggregation schemes for VANET applications. First, when multiple aggregates of observations for the same area are available, it is possible to combine them into an aggregate containing all information from the original aggregates. This is fundamentally different from existing approaches where typically one of the aggregates is selected for further use while the rest is discarded. Second, any observation or aggregate can be included into higher-level aggregates, regardless if it has already been previously—directly or indirectly—added. Those characteristics result in a very flexible aggregate construction and a high quality of the aggregates. We demonstrate these traits of our approach by a simulation study.