An integrity-preserving technique for range queries over data streams in two-tier sensor networks

Two-tier sensor networks enable energy and computation saving due to the introduction of non-constrained storage nodes acting as intermediates between the sensors, which provide data, and the sink, which needs to access these data by submitting queries to the storage nodes. However, the storage nodes maintain a lot of data coming from different sensors and represent a single point of failure targeted by the attackers. In this scenario, robust guarantees about the integrity of the query result (i.e., completeness, freshness, and correctness) should be provided. This is a very well-known problem, traditionally faced through Merkle-Hash-Tree-based data structures. This paper presents a technique more efficient than the state-of-the-art methods for data insertions and deletions, supporting range queries over even non-temporal dimensions. Thus, the proposed solution appears suitable to the considered scenario, in which data can be updated with high frequency and insertions and deletions are executed by constrained devices.