Research On Secure And Effective Algorithms For Top-k Queries In Wireless Sensor Networks

Wireless Sensor Network (WSN) is an important part of the network of things. In recent years, people develop a noval two-tiered sensor network (TSN) model based on WSN. A TSN model consists of two levels. At the lower level, many resource-constrained sensor nodes formed Ad Hoc network, and some relatively resource-abundant storage nodes at the upper level formed MESH network. Data storage nodes are the key nodes in TSN. On the one hand, they collect all data items from the sensor nodes. On the other hand, they are responsible for responding to queries from the Sink node. Thus, in hostile environments, adversaries are more motivated to compromise the storage nodes to make some attacks.In WSN (TSN), there is an important kind of queries, which are Top-k queries. A Top-k query asks sensor nodes to return the largest or smallest k data items from a large data set where data items are generated by the sensor nodes. Because this kind of queries can extracte important data items from the large data set, they attract more and more attention from people. In recent years, people have made a lot of scientific studies on the problem of Top-k queries in wireless sensor networks, and have made some research results. However, some Top-k query problems, such as distance-constrained Top-k query and secure Top-k query, still need further study. This paper aims at solving those problems, and proposes some secure and effective Top-k query processing protocols in WSN (TSN). The main contributions of this paper are as follows.(1) In TSN, a novel authenticity and completeness verification scheme, which is named VSFTQ, for Top-k query is proposed. Firstly, VSFTQ encrypts the score of each data item using the symmetric keys kept by each sensor node and the Sink node, and takes the encrypted scores as the verification information of the data items. Sink can verify the authenticity of the Top-k query results by checking the consistency of the data items and the encrypted scores. Secondly, an order-based data binding method is proposed. In this method, the relationships among data items are established by encrypting the value order of each data item together with its score using the distinct symmetric keys kept by each sensor node and the Sink node. The data binding relationship can prevent the compromised storage nodes from dropping part or all of the qualified data items effectively. Based on the mechanisms mentioned above, we propose a verification algorithm, which is exacuted by the Sink node, to verify the authenticity and completeness of the Top-k query results. Both theoretical analysis and simulation results show that VSFTQ can not only detect forged and/or incomplete query results, but also significantly decrease the communication cost of transmitting the verification information compared with the best existing schemes.(2) In TSN, A novel safe Top-k query processing scheme named STQPS is proposed for data privacy and integrity protection. Firstly, two different encryption schemes, which are the OPSE (order-preserving symmetric encryption) scheme and the symmetric key encryption scheme, are adopted. The OPSE scheme can ensure that the encrypted data items still keep the same value orders as they are not encrypted. Thus, it can be used to encrypt the scores of the data items to facilitate Top-k query processing. Meanwhile, because the data items may be multi-dimensional, they need to be encypted using the symmetric key encryption scheme to protect their privacy. Secondly, to achieve data integrity protection, we propose a noval data binding mechanism, which achieves data binding by encrypting each data item together with the score of its succeeding data item. Because the value orders of the data items need not to be inserted into the verification information, this data binding mechanism can shrink the amout of verification information. Finally, based on the mechanism mentioned above, we propose a novel verification algorithm to verify the competeness of the Top-k query results. Theory analysis and simulation results show that, STQPS is not only secure but also much more effective than the best existing works on secure Top-k query processing in two-tiered sensor networks.(3) In TSN, two verifiable privacy-preserving Top-k query processing protocols, which surport node mobility, are proposed. When some mobile sensor nodes are existed in TSN, if the storage nodes are compromised, the Sink node can not make it clear which nodes have stopped in the query region during the interested time epoch because the sensor nodes can not communicate with the Sink node directly. Thus, it is difficult for the Sink node to verify the authenticity and completeness of Top-k query results. Firstly, we consider the case that the mobile sensor nodes just move in their own cells, and propose an integrity and privacy protection protocol, which is named VPPTQ-1, for Top-k queries. In VPPTQ-1, storage nodes are asked to return all the locations of all the sensor nodes in their own cells. To achieve the privacy of the locations, each sensor node encrypts its locations using the symmetric key shared by itself and the Sink node before it sends them to the storage nodes. Secondly, we consider the case that the mobile sensor nodes can move anywhere in the network field, and propose a location-binding-based secure Top-k query processing protocol, which is named VPPTQ-2. In VPPTQ-2, each sensor node binds its own data with the locations of some other sensor nodes that were once its neighbors. Because the probability that the neighbors of the mobile sensor nodes when they were static in the query region were also in the query region is high, this location binding mechanism can prevent the compromised storage nodes from dropping all the data items and verification information generated by some sensor nodes during the time period when they were static in the query region effectively. Theoretical analysis and simulation results show that the two protocols have high performance on security and energy efficiency.(4) In WSN, we propose a novel hexagon-division-based scheme named LAPDK to solve the distance-constrained Top-k query problem. The distance-constrained Top-k query problem is also called LAP(D, k) problem, and it requires that each of the Top-k query results must satisfy the following three conditions:a) The distance between two locations that correspond to any two data items in the query result must be bigger than D; b) The number of data items in the query result must not be bigger than k; c) The sum of all the data items in the query result is the biggest among all the data sets that satisfy the above two conditions. The LAP(D, k) problem has been approved to be NP hard. LAPDK is a heuristic method. Firstly, the sensing field is divided into hexagonal cells, and one sensor node in each cell is selected as the cluster head. Secondly, some data items from some of the cells are collected, and the approximate solution for the LAP(D, k) problem can be worked out using dynamic programming algorithm based on the collected data. Finally, we propose an optimization algorithm to optimize the approximate solution by making use of all the collected data. Simulation results show that LAPDK can decrease the communication cost of the sensor nodes greatly. Moreover, the approximate solution worked out by LAPDK is much closer to the optimal solution than "R-based" algorithm, which is the best algorithm on LAP(D, k) problem.In a word, this paper has made a further study on Top-k query in wireless sensor networks, and proposes several energy-effective and secure protocols for Top-k queries. Thus, it is very meaningful for theoretical study and practical applications.