Secure data provenance compression using arithmetic coding in wireless sensor networks

Since data are originated and processed by multiple agents in wireless sensor networks, data provenance plays an important role for assuring data trustworthiness. However, the size of the provenance tends to increase at a higher rate as it is transmitted from the source to the base station and is processed by many intermediate nodes. Due to bandwidth and energy limitations of wireless sensor networks, such increasing of provenance size slows down the network and depletes the energy of sensor nodes. Therefore, compression of data provenance is an essential requirement. Existing lossy compression schemes based on Bloom filters or probabilistic packet marking approaches have high error rates in provenance-recovery. In this paper, we address this problem and propose a distributed and lossless arithmetic coding based compression technique which achieves a compression ratio higher than that of existing techniques and also close to Shannon´s entropy bound. Unlike other provenance schemes, the most interesting characteristic of our scheme is that the provenance size is not directly proportional to the number of hops, but to the occurrence probabilities of the nodes that are on a packet´s path. We also ensure the confidentiality, integrity, and freshness of provenance to prevent malicious nodes from compromising the security of data provenance. Finally, the simulation and testbed results provide a strong evidence for the claims in the paper.