Provenance Compression Based On Path Index Differences In Wireless Sensor Networks

In wireless sensor networks(WSNs for short),provenance records the history of data acquisition,processing and transmission,etc.Provenance is critical for assessing the trustworthiness of data acquired and forwarded by sensors,and detecting early signs of attacks,etc.However,the provenance size expands rapidly with increases in the number of packet transmission hops.Due to energy and bandwidth limitations of WSNs,the entire provenance cannot be transmitted directly.To address such issues and transmit provenance as compact as possible,many efficient techniques for provenance encoding have been proposed.Among the existing provenance schemes,the dictionary based provenance scheme has the highest compression rate.However,the major drawback of the dictionary based provenance scheme is that the scheme is sensitive to the WSN's topology,which limits its application scenarios.In order to address such an issue,a provenance scheme based on path index and differences between paths is proposed in this paper.In the scheme,starting from each data source node,establish a backbone path along the direction of the gradient towards the BS.Then use “Truncation Hamming Distance” method proposed by us to remove duplicated backbone paths and the ones with high similarity.And build dictionaries for the left backbone paths after deduplication.When a new packet path appears,no dictionary is created for it.Instead,a similarity comparison method based on SimHash is used to retrieve a path which has the highest similarity with the new one in the dictionary.When the most similar path is found,the new path is represented by using the index of the most similar path and the differences between them.Through simulation and testbed experiments,we show that our scheme not only can effectively overcome the sensitive problem caused by network topology changes,but also can achieve a higher compression ratio.