# EPCT: An Efficient Privacy-Preserving and Collusion-Resisting Top-k Query Processing in WSNs

Authors: Qian Zhou; Hua Dai; Jianguo Zhou; Rongqi Qi; Geng Yang; Xun Yi
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Data privacy threat arises during providing top-k query processing in the wireless sensor networks. This article presents an efficient privacy-preserving and collusion-resisting top-k(EPCT) query processing protocol. A minimized candidate encrypted dataset determination model is first designed, which is the foundation of EPCT. The model guides the idea of query processing and guarantees the correctness of the protocol. The symmetric encryption with different private key in each sensor is deployed to protect the privacy of sensory data even a few sensors in the networks have been colluding with adversaries. Based on the above model and security setting, two phases of interactions between the interested sensors and the sink are designed to implement the secure query processing protocol. The security analysis shows that the proposed protocol is capable of providing secure top-k queries in the manner of privacy protection and anticollusion, whereas the experimental result indicates that the protocol outperforms the existing works on communication overhead.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs), as one of the important technologies in the Internet of Things (IoT), have been widely deployed to provide practical solutions in various applications, such as environment monitoring, military target sensing, and smart home application. Meanwhile, data privacy leakage in WSNs is becoming the main obstruction, which slows down its further development. For example, in the scenario of a smart home application, videos or pictures collected by wireless IP-cameras could be eavesdropped for illegal profit. As a result, privacy protection on sensitive data is a critical issue that must be addressed in WSNs.In WSNs, the top-k query is one of the critical operations in data aggregation for sensor monitoring process. The top-k query requests the k lowest or highest data items collected from IoT sensors in WSNs. For example, “collecting the 10 lowest humidity data in forest area A-Z in last 2 hours” is an example of top-k query, which can be performed for fire monitoring. Our aim of this work is to design a secure top-k query approach with privacy-preserving and collusion-resisting manners.This article presents an efficient privacy-preserving and collusion-resisting top-k query processing protocol (EPCT) in WSNs. We first propose a minimized candidate encrypted dataset determination model, which is the foundation of our proposed protocol. It guides the idea of query processing and guarantees the correctness of the protocol. There are two phases of interactions between the queried sensors and the sink in EPCT. In the first phase, when the queried sensors receive a top-k query from the sink, they first use their own private keys to encode the maximum of the collected data in the interested time slot, respectively, and then, they submit the encrypted data to the sink. In the second phase, the sink decrypts the received ciphertext and calculates the candidate sensors; after that, it unicastly informs the candidate sensors to submit the rest candidate data. Once the sink obtains enough data from the candidate sensors, the final result of the query is determined. The security analysis and performance evaluation indicate that the proposed approach EPCT has the ability of protecting data privacy and performing efficiently in transmission overhead.The main contributions of this article are listed as follows:(i)
We present a minimized candidate encrypted dataset determination model, which is the foundation of our proposed scheme. It guides the idea of query processing and guarantees the correctness of the protocol.(ii)
We present a novel privacy-preserving and collusion-resisting top-k query processing protocol, which consists of two phases of secure interactions between the queried nodes and the sink. We also analyse the correctness, security, and transmission overhead of the proposed method.(iii)
We perform evaluations on the transmission overhead of the proposed protocol and the existing works. The experimental result shows the advantages of the proposed scheme in transmission overhead.The remainder of this article is organized as follows. Section2 discusses the related work. Section 3 introduces the network model, query model, threat model, and the problem description. Section 4 proposes the minimized candidate encrypted dataset determination model. Section 5 presents the top-k query processing protocol and the analysis of this protocol. Section 6 presents the performance evaluation of query protocols on communication cost, and Section 7 gives a conclusion of this article.


## 2. Related Work

Secure data queries (such as top-k query, range query, and MAX/MIN query) are critical operations for sensor monitoring and data collection in security-sensitive environment. There are a lot of works [1–24] focusing confidentiality, integrity, and completeness when performing data queries.Kui et al. [3] utilize the pairwise-key and order-preserving symmetric encryption and the together to protect the privacy of data in top-k queries in two-tiered WSNs. Peng et al. [4] encoded both sensory data and top-k query commands, and storage nodes are designed to be able to correctly perform top-k queries over those encoded data. Li et al. [6] use pseudorandom hash function with bloom filter and partition algorithm to protect data privacy and integrity for top-k queries, respectively. Tsou et al. [7] constructed a layered authentication tree by an order-preserving symmetric encryption and used it to verify the completeness of query results. Zhang et al. [12] designed a renormalized arithmetic coding method such that storage nodes can calculate exact top-k query results without knowing real values of data, and they proposed a verification scheme to detect compromised storage nodes. Peng et al. [13] encoded top-k queries by threshold-based scheme and proposed a secure protocol that storage nodes can calculate query results over encrypted sensory data. Xingpo et al. [14] proposed secure top-k query protocol with privacy and integrity preservation by deploying the secure data preprocessing in sensor nodes. Wu and Wang [17] bound the collected sensory data with the corresponding locations to achieve secure top-k query processing on hybrid sensory data. Liu et al. [18] proposed a verifiable top-k query protocol on two-tiered mobile sensor network, which adopts the distinct symmetric data encryption and maps real nodes into virtual nodes. These methods are designed for two-tiered WSNs, which adopt resource-rich storage nodes in traditional multihop WSNs. The different network architecture makes them not suitable for addressing secure top-k queries in traditional multihop WSNs.In traditional multihop WSNs, the earlier studies [19, 25–29] proposed various top-k query schemes but without concerning any security issues. Huang et al. [30] designed a privacy-protection top-k query algorithm using a filter and a data distribution table. The algorithm adopts conic section function to protect the privacy of the sensory data. But, the algorithm is vulnerable when collusion attacks happen. It is because all sensor nodes share the same secure keys and functions. If a sensor node colludes with adversaries, these secure keys and functions will be disclosed, and the adversaries could obtain the private data of other innocent sensors. In our previous work [31], we gave the first solution providing the privacy-protecting and anticollusion top-k query processing scheme in wireless sensor networks. It adopts the bloom filter and HMAC when performing interactions between nodes and the sink to achieve secure top-k query processing. However, there is some space for transmission overhead saving because of the redundant data submission and the false positive of bloom filter. This article presents an efficient and secure top-k query processing protocol, which can address the above problems.Additionally, some previous studies have focused on the privacy-preserving range queries [8, 11, 32] and MAX/MIN queries [15, 16] in WSNs. Because the query types are different, the ideas of these works cannot be applied to achieve the secure top-k queries in WSNs.


## 3. Problem Description

### 3.1. Network Model

The architecture adopted is shown in Figure1. The network routing topology is structured as a tree, which is following TAG protocol [33]. Assuming that in our scenario, n sensors S=s1,s2,…,sn are deployed and a sink. Sensor nodes are sensory devices with limited resources in energy, storage, and computation. They are in charge of collecting data items from their neighboring areas and then submitting the collected data to the sink through the tree route. The sink is a resourceful device, which executes query commands from users and returns query results to users. When receiving a query command, the sink cooperates with those queried sensors in S to process queries according to predeployed protocols. After the sink obtains the query result, it returns the result to the upper-level users.Figure 1
A example of tree routing topology.


### 3.2. Top-k Query Model

A top-k query is a data aggregation operation to get k highest or lowest sensory data from queried sensors. It is denoted as a triple Queryt=t,S,k where t is the queried time slot identity, S is the set of interested sensors, and k is the number of interested data items. For example, t,s1,s2,…,s12,3 is a top-3 query to obtain the 3 highest or lowest data items during sensors s1,s2,…,s12 in the time slot t.Each sensorsi∈S is assumed to collect N data items in a time slot, which is denoted as Di=di,1,di,2,…,di,N, and each data item collected by a sensor is assumed to have an unique score. The uniqueness of collected data items can be achieved by integrating the data collecting time and the sensor identity into the data item score calculation. It ensures the uniqueness and correctness of a top-k query result.


### 3.3. Threat Model

The honest-but-curious threat model [9] is adopted in this article. The sink is trustful while sensors could collude with adversaries to leak out their collected or forwarded data. But the sensors that has been attacked still perform the pre-deployed protocols and cooperate with other innocent (noncompromised) sensors to process query commands. We have to note that the innocent sensors are the majority in WSNs; otherwise, the network will be useless.The goal of the proposed secure top-k query protocol is described as follows:(1)
A sensor only owns the data collected by itself, and the data can be shared with the sink. It has no idea of the data collected by other sensors even when they are colluding with the adversaries.(2)
Query results can only be obtained by the sink, but the adversaries have no idea of them even when there are a few compromised sensors colluding with the adversaries.(3)
Thek data items obtained by the sink are the k highest or lowest data items collected by the queried sensors, which means that the query result is correct.Because sensors have limited energy, the network lifetime is usually determined by the energy consumption of the sensors. Reference [33] shows that sensors consume most energy in data transmission. Thus, the transmission overhead of network is an important metric for performance evaluation. We will perform the evaluation on this metric in Section 6.


## 3.1. Network Model

The architecture adopted is shown in Figure1. The network routing topology is structured as a tree, which is following TAG protocol [33]. Assuming that in our scenario, n sensors S=s1,s2,…,sn are deployed and a sink. Sensor nodes are sensory devices with limited resources in energy, storage, and computation. They are in charge of collecting data items from their neighboring areas and then submitting the collected data to the sink through the tree route. The sink is a resourceful device, which executes query commands from users and returns query results to users. When receiving a query command, the sink cooperates with those queried sensors in S to process queries according to predeployed protocols. After the sink obtains the query result, it returns the result to the upper-level users.Figure 1
A example of tree routing topology.


## 3.2. Top-k Query Model

A top-k query is a data aggregation operation to get k highest or lowest sensory data from queried sensors. It is denoted as a triple Queryt=t,S,k where t is the queried time slot identity, S is the set of interested sensors, and k is the number of interested data items. For example, t,s1,s2,…,s12,3 is a top-3 query to obtain the 3 highest or lowest data items during sensors s1,s2,…,s12 in the time slot t.Each sensorsi∈S is assumed to collect N data items in a time slot, which is denoted as Di=di,1,di,2,…,di,N, and each data item collected by a sensor is assumed to have an unique score. The uniqueness of collected data items can be achieved by integrating the data collecting time and the sensor identity into the data item score calculation. It ensures the uniqueness and correctness of a top-k query result.


## 3.3. Threat Model

The honest-but-curious threat model [9] is adopted in this article. The sink is trustful while sensors could collude with adversaries to leak out their collected or forwarded data. But the sensors that has been attacked still perform the pre-deployed protocols and cooperate with other innocent (noncompromised) sensors to process query commands. We have to note that the innocent sensors are the majority in WSNs; otherwise, the network will be useless.The goal of the proposed secure top-k query protocol is described as follows:(1)
A sensor only owns the data collected by itself, and the data can be shared with the sink. It has no idea of the data collected by other sensors even when they are colluding with the adversaries.(2)
Query results can only be obtained by the sink, but the adversaries have no idea of them even when there are a few compromised sensors colluding with the adversaries.(3)
Thek data items obtained by the sink are the k highest or lowest data items collected by the queried sensors, which means that the query result is correct.Because sensors have limited energy, the network lifetime is usually determined by the energy consumption of the sensors. Reference [33] shows that sensors consume most energy in data transmission. Thus, the transmission overhead of network is an important metric for performance evaluation. We will perform the evaluation on this metric in Section 6.


## 4. Minimized Candidate Encrypted Dataset Determination Model

Based on the idea making, the proposed protocol efficient in transmission overhead. We propose the minimized candidate encrypted dataset determination model in this session.


### 4.1. Minimized Candidate Sensor Set

LetQueryt=t,S,k be a query command, and each sensor si∈S collects N data items in a time slot, the set of collected data of all sensors in S is D=di,j|si∈S∧1≤j≤N.Definition 1.
For a top-k query, the query result Rt is a dataset having the k largest data items of D. LRt is denoted as the lower bound of Rt, which is the minimum of Rt.Definition 2.
For a sensorsi∈S, the in-node-maximum of si is the maximum data item.
For example, if the collected data ofsi are Di=di,1,di,2,…,di,N and di,1>di,2>⋯>di,N, then di,1 is the in-node-maximum of si.Definition 3.
For a top-k query, we define Φ is a sensor set consisting of k sensors whose in-node-maximums are the k largest in-node-maximums of sensors in S, that is(1)Φ⊆S∧Φ=k∧∀si∈Φ,sj∈S−Φ⟶di,1>dj,1.Lemma 1.
LRt≥mindi,1|si⊆ΦProof.
According to Definition1, LRt is the lower bound of Rt, which is the kth largest data of D. Because Φ=k, there are k in-node-maximums of sensors of Φ, that is, di,1|si∈Φ=k. Thus, mindi,1|si∈Φ is the kth largest data of di,1|si∈Φ, where min∗ represents the minimum of a dataset. Because di,1|si∈Φ⊆D, we have that LRt≥mindi,1|si∈Φ holds.Lemma 2.
Φ is the candidate sensor set of a query, which means that all data in the query result Rt are contributed by sensors of Φ, that is,(2)Rt⊆∪si∈ΦDi.Proof.
We give the proof by contradiction. We are assuming that there is at least one data ofRt, which is not contributed by a sensor of Φ. It means that ∃xx∈Rt∧x∈Dj, where x is collected by sj and sj is not in Φ, i.e., sj∈S−Φ. We are assuming that x is the lth largest data of D. Then, we can deduce two results: 1. 1≤l≤k holds because of x∈Rt and Rt=k. 2. According to the definition of Φ, for ∀y∈di,1|si∈Φ, because x is assumed to be collected by sj∈S−Φ, we have y>dj,1≥x, where dj,1 is the in-node-maximum of sj. Additionally, there are k in-node-maximums contributed by sensors in Φ, i.e., di,1si∈Φ|=k. Therefore, we can deduce that l>k holds. Obviously, there are contradictions between 1 and 2. As a result, we deduce that Lemma 2 holds.
Lemma2 It indicates that all sensors in Φ are candidate sensors, which contribute the query result. In addition, Φ is also the minimized candidate sensor set, and we prove it in Lemma 3.Lemma 3.
Φ is the minimized candidate sensor set that contribute the query result Rt.Proof.
To prove this lemma, we have to prove the following two observations.Observation 1.
For∀dj,h∈Dj where ∀sj∈S−Φ, LRt>dj,h holds.Observation 2.
Any sensor deletion fromΦ could incur the incompleteness of query result. If and only if the two observations hold simultaneously, then we can deduce that Φ is the minimized candidate sensor set that contribute the query result.Proof to Observation 1.
According to Definition3, for ∀si∈Φ and ∀sj∈S−Φ, di,1 and dj,1 are their in-node-maximums and di,1>dj,1 holds. Because dj,1 is the in-node-maximum of sj, di,1≥dj,h holds where dj,h∈Dj. Thus, di,1>dj,h holds. In addition, because si could be any sensor of Φ, we can deduce that mindi,1|si∈Φ>dj,h. At last, Lemma 1 indicates that LRt≥mindi,1|si∈Φ; therefore, LRt>dj,h holds, and the first observation is proved.Proof to Observation 2.
To prove the second observation, we just need to prove that, for any sensor ofΦ, its collected data could belong to the query result Rt. If it is true, then deleting any sensor from Φ could cause the incompleteness of Rt. We are assuming that the collected data of sensors of Φ satisfy: ∀di,jsi∈Φ∧2≤j≤N⟶di,j<mindp,1∣sp∈Φ. Because Φ=k, the top-k query result Rt is determined and Rt=dp,1|sp∈Φ. It means that the in-node-maximums of all sensors of Φ are just the elements of Rt. It is obvious that, in such circumstance, deleting any sensor from Φ will incur the incompleteness of Rt. Therefore, the second observation is proved.
According to the proofs, the above two observations both hold. Thus,Φ is the minimized candidate sensor set that contribute the query result.


### 4.2. Minimized Candidate Encrypted Dataset

To protect data privacy, each sensor owns its private key only by itself. When a query is started, sensors first encrypt the qualified data by their keys and then submit the encrypted data to sink. For sensorsi, we are assuming its key is gi, which is only shared by si and sink. The encrypted data of di,j is denoted as di,jgi.Definition 4.
(minimized candidate encrypted dataset). For a top-k query, the minimized candidate encrypted dataset, denoted as Γ, is contributed by sensors of Φ and consists of the minimum number of encrypted data that have the encrypted query result in it.
We are assuming that the candidate sensors areΦ=s1,s2,…,sk and their in-node-maximums are d1,1,d2,1,…,dk,1, respectively, where d1,1>d2,1>⋯>dk,1. For any sensor si∈Φ, its collected data items are di,1,di,2,…,di,N, where di,1>di,2>⋯>di,N. Thus, the calculation of Γ is given as follows:(3)Γ=∪si∈ΦΓi,where(4)Γi=di,jgi|1≤j≤k−i+1,N≥k−i+1,di,jgi|1≤j≤N,N<k−i+1.
We give an example to describe the minimized candidate encrypted dataset. As shown in Figure2, we are assuming that there are 5 nodes s1,s2,s3,s4,s5, and each sensor has collected 4 data items. Their in-node-maximums satisfy d1,1>d2,1>⋯>d5,1. For sensor si, its collected data satisfy di,1>di,2>di,3>di,4. According to Definition 4, the minimized candidate encrypted datasets when k = 3 and k = 5 are shown in the dotted-lined area and solid-lined area, respectively.Figure 2
Minimized candidate encrypted datasets whenk = 3 and 5.Lemma 4.
Γ is the minimized candidate encrypted dataset that has the encrypted query result.Proof.
To prove this lemma, the following two observations need to be proved.Observation 3.
For anydi,jgi∉Γ, which is generated by si, LRt>di,j holds.Observation 4.
Any encrypted data deletion fromΓ could incur the incompleteness of query result. If and only if the two observations hold simultaneously, then we can deduce that Γ is the minimized candidate encrypted dataset that has the encrypted query result.Proof of Observation 1.
For sensorsi, it has two alternative cases, which are si∉Φ or si∈Φ. We give the proofs in such two cases:(i)
Case I:si∉Φ. According to Lemma 3, Φ is the minimized candidate sensor set that contribute the query result Rt. Because si∉Φ, we have di,j∉Rt, where di,j∈Dj and then LRt>di,j is deduced.(ii)
Case II:si∈Φ. Because di,jgi∉Γ, k−i+2≤j≤N is deduced according to equation (4). In the calculation of Γ, d1,1>d2,1>⋯>di,1>⋯>dk,1 and di,1>di,2>⋯>di,j>⋯>di,N are the given assumption. Thus, there are at least k,=i+j−2 data larger than di,j. According to k−i+2≤j≤N and k′=i+j−2, then we have k≤k′≤i+N−2. It means that there are at least k data larger than di,j. Definition 1 shows that the query result Rt has the k largest data, so the minimum of Rt is obviously larger than di,j, that is, LRt>di,j. The deductions in two cases both lead to the same result LRt>di,j, and the first observation is proved.Proof of Observation 2.
To prove the second observation, we just need to prove that, for anydi,jgi∈Γ, the corresponding plaintext data di,j could belong to Rt. If it is true, then deleting any encrypted data from Γ could cause the incompleteness of Rt. According to the assumptions of the calculation of Γ that the minimized candidate sensor set is Φ=s1,s2,…,sk, where their in-node-maximums satisfy d1,1>d2,1>⋯>dk,1 and the collected data of any si∈Φ satisfy di,1>di,2>⋯>di,N, for the data di,j and C=d1,1,d2,1,…,di−1,1,di,1,di,2,…,di,j−1, each data in C is larger than di,j and C=i+j−2. If the following equation holds, then di,j is the i+j−2th largest data.(5)∀dp,qdp,qgp∈Γ∧dp,q∉C⟶dp,q<di,j.
According to the calculation ofΓ in equations (3) and (4), we have j≤k−i+1, then C≤k−1 holds. It means that di,j is at least the kth largest data when equation (5) hold. In such scenario, di,j always belongs to Rt. Therefore, we have that deleting any encrypted data from Γ could cause the incompleteness of Rt. Observation 2 is proved.
According to the above proofs, two observations both hold. Thus,Γ is the minimized candidate encrypted dataset that has the encrypted query result. Lemma 4 is proved.
Lemma4 It indicates that Γ is the minimized candidate encrypted dataset that has the encrypted query result. It is a key to achieve efficient privacy-preserving query processing method.


## 4.1. Minimized Candidate Sensor Set

LetQueryt=t,S,k be a query command, and each sensor si∈S collects N data items in a time slot, the set of collected data of all sensors in S is D=di,j|si∈S∧1≤j≤N.Definition 1.
For a top-k query, the query result Rt is a dataset having the k largest data items of D. LRt is denoted as the lower bound of Rt, which is the minimum of Rt.Definition 2.
For a sensorsi∈S, the in-node-maximum of si is the maximum data item.
For example, if the collected data ofsi are Di=di,1,di,2,…,di,N and di,1>di,2>⋯>di,N, then di,1 is the in-node-maximum of si.Definition 3.
For a top-k query, we define Φ is a sensor set consisting of k sensors whose in-node-maximums are the k largest in-node-maximums of sensors in S, that is(1)Φ⊆S∧Φ=k∧∀si∈Φ,sj∈S−Φ⟶di,1>dj,1.Lemma 1.
LRt≥mindi,1|si⊆ΦProof.
According to Definition1, LRt is the lower bound of Rt, which is the kth largest data of D. Because Φ=k, there are k in-node-maximums of sensors of Φ, that is, di,1|si∈Φ=k. Thus, mindi,1|si∈Φ is the kth largest data of di,1|si∈Φ, where min∗ represents the minimum of a dataset. Because di,1|si∈Φ⊆D, we have that LRt≥mindi,1|si∈Φ holds.Lemma 2.
Φ is the candidate sensor set of a query, which means that all data in the query result Rt are contributed by sensors of Φ, that is,(2)Rt⊆∪si∈ΦDi.Proof.
We give the proof by contradiction. We are assuming that there is at least one data ofRt, which is not contributed by a sensor of Φ. It means that ∃xx∈Rt∧x∈Dj, where x is collected by sj and sj is not in Φ, i.e., sj∈S−Φ. We are assuming that x is the lth largest data of D. Then, we can deduce two results: 1. 1≤l≤k holds because of x∈Rt and Rt=k. 2. According to the definition of Φ, for ∀y∈di,1|si∈Φ, because x is assumed to be collected by sj∈S−Φ, we have y>dj,1≥x, where dj,1 is the in-node-maximum of sj. Additionally, there are k in-node-maximums contributed by sensors in Φ, i.e., di,1si∈Φ|=k. Therefore, we can deduce that l>k holds. Obviously, there are contradictions between 1 and 2. As a result, we deduce that Lemma 2 holds.
Lemma2 It indicates that all sensors in Φ are candidate sensors, which contribute the query result. In addition, Φ is also the minimized candidate sensor set, and we prove it in Lemma 3.Lemma 3.
Φ is the minimized candidate sensor set that contribute the query result Rt.Proof.
To prove this lemma, we have to prove the following two observations.Observation 1.
For∀dj,h∈Dj where ∀sj∈S−Φ, LRt>dj,h holds.Observation 2.
Any sensor deletion fromΦ could incur the incompleteness of query result. If and only if the two observations hold simultaneously, then we can deduce that Φ is the minimized candidate sensor set that contribute the query result.Proof to Observation 1.
According to Definition3, for ∀si∈Φ and ∀sj∈S−Φ, di,1 and dj,1 are their in-node-maximums and di,1>dj,1 holds. Because dj,1 is the in-node-maximum of sj, di,1≥dj,h holds where dj,h∈Dj. Thus, di,1>dj,h holds. In addition, because si could be any sensor of Φ, we can deduce that mindi,1|si∈Φ>dj,h. At last, Lemma 1 indicates that LRt≥mindi,1|si∈Φ; therefore, LRt>dj,h holds, and the first observation is proved.Proof to Observation 2.
To prove the second observation, we just need to prove that, for any sensor ofΦ, its collected data could belong to the query result Rt. If it is true, then deleting any sensor from Φ could cause the incompleteness of Rt. We are assuming that the collected data of sensors of Φ satisfy: ∀di,jsi∈Φ∧2≤j≤N⟶di,j<mindp,1∣sp∈Φ. Because Φ=k, the top-k query result Rt is determined and Rt=dp,1|sp∈Φ. It means that the in-node-maximums of all sensors of Φ are just the elements of Rt. It is obvious that, in such circumstance, deleting any sensor from Φ will incur the incompleteness of Rt. Therefore, the second observation is proved.
According to the proofs, the above two observations both hold. Thus,Φ is the minimized candidate sensor set that contribute the query result.


## 4.2. Minimized Candidate Encrypted Dataset

To protect data privacy, each sensor owns its private key only by itself. When a query is started, sensors first encrypt the qualified data by their keys and then submit the encrypted data to sink. For sensorsi, we are assuming its key is gi, which is only shared by si and sink. The encrypted data of di,j is denoted as di,jgi.Definition 4.
(minimized candidate encrypted dataset). For a top-k query, the minimized candidate encrypted dataset, denoted as Γ, is contributed by sensors of Φ and consists of the minimum number of encrypted data that have the encrypted query result in it.
We are assuming that the candidate sensors areΦ=s1,s2,…,sk and their in-node-maximums are d1,1,d2,1,…,dk,1, respectively, where d1,1>d2,1>⋯>dk,1. For any sensor si∈Φ, its collected data items are di,1,di,2,…,di,N, where di,1>di,2>⋯>di,N. Thus, the calculation of Γ is given as follows:(3)Γ=∪si∈ΦΓi,where(4)Γi=di,jgi|1≤j≤k−i+1,N≥k−i+1,di,jgi|1≤j≤N,N<k−i+1.
We give an example to describe the minimized candidate encrypted dataset. As shown in Figure2, we are assuming that there are 5 nodes s1,s2,s3,s4,s5, and each sensor has collected 4 data items. Their in-node-maximums satisfy d1,1>d2,1>⋯>d5,1. For sensor si, its collected data satisfy di,1>di,2>di,3>di,4. According to Definition 4, the minimized candidate encrypted datasets when k = 3 and k = 5 are shown in the dotted-lined area and solid-lined area, respectively.Figure 2
Minimized candidate encrypted datasets whenk = 3 and 5.Lemma 4.
Γ is the minimized candidate encrypted dataset that has the encrypted query result.Proof.
To prove this lemma, the following two observations need to be proved.Observation 3.
For anydi,jgi∉Γ, which is generated by si, LRt>di,j holds.Observation 4.
Any encrypted data deletion fromΓ could incur the incompleteness of query result. If and only if the two observations hold simultaneously, then we can deduce that Γ is the minimized candidate encrypted dataset that has the encrypted query result.Proof of Observation 1.
For sensorsi, it has two alternative cases, which are si∉Φ or si∈Φ. We give the proofs in such two cases:(i)
Case I:si∉Φ. According to Lemma 3, Φ is the minimized candidate sensor set that contribute the query result Rt. Because si∉Φ, we have di,j∉Rt, where di,j∈Dj and then LRt>di,j is deduced.(ii)
Case II:si∈Φ. Because di,jgi∉Γ, k−i+2≤j≤N is deduced according to equation (4). In the calculation of Γ, d1,1>d2,1>⋯>di,1>⋯>dk,1 and di,1>di,2>⋯>di,j>⋯>di,N are the given assumption. Thus, there are at least k,=i+j−2 data larger than di,j. According to k−i+2≤j≤N and k′=i+j−2, then we have k≤k′≤i+N−2. It means that there are at least k data larger than di,j. Definition 1 shows that the query result Rt has the k largest data, so the minimum of Rt is obviously larger than di,j, that is, LRt>di,j. The deductions in two cases both lead to the same result LRt>di,j, and the first observation is proved.Proof of Observation 2.
To prove the second observation, we just need to prove that, for anydi,jgi∈Γ, the corresponding plaintext data di,j could belong to Rt. If it is true, then deleting any encrypted data from Γ could cause the incompleteness of Rt. According to the assumptions of the calculation of Γ that the minimized candidate sensor set is Φ=s1,s2,…,sk, where their in-node-maximums satisfy d1,1>d2,1>⋯>dk,1 and the collected data of any si∈Φ satisfy di,1>di,2>⋯>di,N, for the data di,j and C=d1,1,d2,1,…,di−1,1,di,1,di,2,…,di,j−1, each data in C is larger than di,j and C=i+j−2. If the following equation holds, then di,j is the i+j−2th largest data.(5)∀dp,qdp,qgp∈Γ∧dp,q∉C⟶dp,q<di,j.
According to the calculation ofΓ in equations (3) and (4), we have j≤k−i+1, then C≤k−1 holds. It means that di,j is at least the kth largest data when equation (5) hold. In such scenario, di,j always belongs to Rt. Therefore, we have that deleting any encrypted data from Γ could cause the incompleteness of Rt. Observation 2 is proved.
According to the above proofs, two observations both hold. Thus,Γ is the minimized candidate encrypted dataset that has the encrypted query result. Lemma 4 is proved.
Lemma4 It indicates that Γ is the minimized candidate encrypted dataset that has the encrypted query result. It is a key to achieve efficient privacy-preserving query processing method.


## 5. Top-k Query Processing

At first, an efficient privacy-preserving and collusion-resisting top-k (EPCT) query scheme is introduced here. Then, the correctness and security analysis, and performance of the proposed EPCT protocol will be presented.


### 5.1. Query Processing Protocol

The queried nodes and the sink are involved as the cooperators in this EPCT protocol. To perform the protocol, sensors and the sink are firstly settled with keys in the network deployment. Each sensor is deployed a private key, and it only shares the key with the sink. The sink owns keys of all sensors, whereas sensors have no idea of each other’s keys. The protocol has two phases, shown in Figure3. The command is broadcasted to sensors in S, before the sink receives a top-k query Queryt=t,S,k in the first phase from the user. Once the sensor si gets Queryt, it transmits the encrypted in-node-maximum in the queried time slot t to the sink. As the first phase ends, the second phase begins. In the second phase, the minimized candidate sensor set is determined according to the maximum values of the queried sensors. Then, the sink transmits the second phase data request command to those candidate sensors. After each candidate sensor submits the qualified encrypted data, the sink obtains the minimized candidate encrypted dataset, and then, it will get the final query result after decryption. The processing of the top-k query Queryt is finished.Figure 3
EPCT protocol query process.The detailed procedures of the query processing protocol are shown in Protocol 1.Protocol 1. EPCT protocol is shown as follows:(1)
Phase 1:(1)
As a queryQueryt=t,S,k is running, the first phase starts to process. Sink broadcasts Queryt through all the networks and initials the dataset Γ=∅. Then, it waits till the first phase responses from the queried nodes in the networks.(2)
For each nodesi∈S, si encrypts its in-node-maximum di,1 by using its private key gi, after si gets the Queryt. Then, si generates the encrypted data di,1gi, submitting the message as follows to the sink.(6)si⟶sink:t,idsi,di,1gi(2)
Phase 2:(1)
As the submitted message from a queried sensorsi∈S arrives, t,idsi,di,1gi, the sink decrypts di,1gi with the shared private key gi and gets the plaintext in-node-maximum of si. si obtains all the decrypted in-node-maximums of the nodes in S, di,1|si∈S, before it determines the top-k data. If the determined top-k data are d1,1,d2,1,…,dk,1 where d1,1>d2,1>⋯>dk,1 and the corresponding sensor list according to the decent sequence of data are Φ=s1,s2,…,sk. According to Lemma 3, Φ are the set of minimized candidate sensors. Then, the sink appends d1,1,d2,1,…,dk,1 into Γ and transmits the following messages to the k-1 candidate nodes in Φ−sk in unicast mode.(7)sink⟶si:t,k−igi,∀si∈Φ−sk.(2)
For each candidate nodesi∈Φ−sk, as the message t,k−igi arrives, si decrypts the ciphertext and gets the plaintext number k−i. Then, si encrypts k−i collected data items and sends them to the sink, e.g.,(8)si⟶sink:t,idsi,LRi,where(9)LRi=di,jgi|2≤j≤k−i+1,N≥k−i+1,di,jgi|2≤j≤N,N<k−i+1.(3)
The sink obtains the messaget,i,LRi transmitted by the candidate node si∈Φ−sk in the second phase, before the ciphertext of the message is decrypted. The plaintext data after decryption are denoted as DecLRi,gi and appended into Γ. After all messages submitted from the candidate nodes are processed, the minimized candidate encrypted dataset Γ is determined, where(10)Γ=∪si∈Φdi,1∪DecLRi,gi.(4)
The sink gets the top-k data of Γ, which is the exact query result Rt.(11)Rt⊆Γ∧Rt=k∧∀x∈Rt,y∈Γ−Rt⟶x>y.As presented in Protocol 1, the query commandQueryt arrives from the user in the first phase, before the sink broadcasts it through the whole network. As a queried sensor knows Queryt, it encodes the in-node-maximum before transmitting the encrypted data to the sink, where the received ciphertext is decrypted to obtain the in-node-maximums of the queried sensors in the second phase. Afterwards, the sink uses the in-node-maximums to determine the candidate sensor set Φ−sk, and then, it unicasts each candidate sensor in Φ−sk to start the second phase. Once a candidate sensor receives the unicast message, it submits the rest data in ciphertext according to the request to the sink. As the sink obtains all the needed data from candidate nodes, the query result is determined in the end.


### 5.2. Protocol Analysis

#### 5.2.1. Correctness Analysis

In the proposed EPCT protocol, when a user starts a query commandQueryt, the sink will know the minimized candidate encrypted dataset Γ after interactions of the sink and sensors within two phases. Γ is consisting of the coded data items of query result. According to Lemma 4, for any di,jgi∉Γ, di,jgi does not belong to the query result Rt, definitely. Additionally, Γ is the minimized candidate encrypted dataset that contains the encrypted query result. Any encrypted data deletion from Γ could incur the incompleteness of query result. As Γ received by the sink, it can get the query result by obtaining the top-k data from Γ. Therefore, our proposed scheme is capable of guaranteeing the correctness of top-k query result.


#### 5.2.2. Security Analysis

The security analysis is conducted here for the privacy of the collected data and the query results. With the cooperation of the sink and the sensors in EPCT in these two phases, each node is deployed with a private key, which is only shared with the sink. The collected data of sensors only exists in data submission from sensors to the sink. When a top-k query is started, two phases of query processing are performed. In the first phase, each sensor performs a symmetric encryption to encrypt its in-node-maximum and then transmits it to the sink. Secondly, candidate nodes are unicastly informed by the sink. They encrypted a fixed number of collected data according to the request and then sends the enciphered date to the sink node. Clearly, the data collected and transmitted through the network are all in the form of ciphertext. Every node in WSN owns a unique private key, so it can only get access to the data it collected. However, it fails to know the data collected by other sensors because of the computational infeasibility of symmetric encryption. Even a few nodes probably are attacked and colluded with adversaries, they can only snoop the collected data of those colluded sensors, but they have no idea of the collected data of innocent sensors. Besides, due to the query result is decrypted and computed in the sink and sensor nodes only process the encrypted data for the query, it is hard for the attackers to know the plaintext query result even if a few compromised sensors are colluded with them. Therefore, this proposed EPCT is a privacy-preserving and anticollusion top-k query processing protocol, which can protect the privacy of collected data of sensors even a few compromised sensors are in collusion with the adversaries, which can protect the privacy of collected data from adversaries even a few compromised sensors are in collusion with the adversaries.


#### 5.2.3. Communication Cost Analysis

In WSNs, sensors have limited energy resource, and the energy are mainly consumed by communication. During the top-k query procedures, the communication cost of the network is mainly caused by transmission overhead of sensors. The parameters used in sensor networks are introduced in Table 1.Table 1
Parameters description.
ParaDescriptionlidThe space size of a sensor IDltThe space size of a time-slotlcThe space size of a coded data itemlqThe space size of a query commandLThe average path length from sensors to the sinkWe are assuming that the transmission overhead of phase 1 and phase 2 areC1 and C2, respectively. According to the proposed EPCT protocol, all sensors participate in phase 1, whereas only the candidate sensors participate in phase 2. Then, we obtain(12)C1=n⋅lq+n⋅lid+lt+lc⋅L,C2=k−1⋅lt+lc⋅L+∑i=1k−1lid+lt+i⋅lc⋅L=k−1⋅lid⋅L+k−1⋅lid+lt⋅L+k⋅k−12⋅lc⋅L=k−1⋅lid+2lt+lc⋅L+k⋅k−12⋅lc⋅LThe total communication overhead of the whole network is computed as follows:(13)Ctotal=C1+C2=n⋅lq+n+k−1⋅lid+lt+lc⋅L+k−1⋅lt⋅L+k⋅k−12⋅lc⋅L.


## 5.1. Query Processing Protocol

The queried nodes and the sink are involved as the cooperators in this EPCT protocol. To perform the protocol, sensors and the sink are firstly settled with keys in the network deployment. Each sensor is deployed a private key, and it only shares the key with the sink. The sink owns keys of all sensors, whereas sensors have no idea of each other’s keys. The protocol has two phases, shown in Figure3. The command is broadcasted to sensors in S, before the sink receives a top-k query Queryt=t,S,k in the first phase from the user. Once the sensor si gets Queryt, it transmits the encrypted in-node-maximum in the queried time slot t to the sink. As the first phase ends, the second phase begins. In the second phase, the minimized candidate sensor set is determined according to the maximum values of the queried sensors. Then, the sink transmits the second phase data request command to those candidate sensors. After each candidate sensor submits the qualified encrypted data, the sink obtains the minimized candidate encrypted dataset, and then, it will get the final query result after decryption. The processing of the top-k query Queryt is finished.Figure 3
EPCT protocol query process.The detailed procedures of the query processing protocol are shown in Protocol 1.Protocol 1. EPCT protocol is shown as follows:(1)
Phase 1:(1)
As a queryQueryt=t,S,k is running, the first phase starts to process. Sink broadcasts Queryt through all the networks and initials the dataset Γ=∅. Then, it waits till the first phase responses from the queried nodes in the networks.(2)
For each nodesi∈S, si encrypts its in-node-maximum di,1 by using its private key gi, after si gets the Queryt. Then, si generates the encrypted data di,1gi, submitting the message as follows to the sink.(6)si⟶sink:t,idsi,di,1gi(2)
Phase 2:(1)
As the submitted message from a queried sensorsi∈S arrives, t,idsi,di,1gi, the sink decrypts di,1gi with the shared private key gi and gets the plaintext in-node-maximum of si. si obtains all the decrypted in-node-maximums of the nodes in S, di,1|si∈S, before it determines the top-k data. If the determined top-k data are d1,1,d2,1,…,dk,1 where d1,1>d2,1>⋯>dk,1 and the corresponding sensor list according to the decent sequence of data are Φ=s1,s2,…,sk. According to Lemma 3, Φ are the set of minimized candidate sensors. Then, the sink appends d1,1,d2,1,…,dk,1 into Γ and transmits the following messages to the k-1 candidate nodes in Φ−sk in unicast mode.(7)sink⟶si:t,k−igi,∀si∈Φ−sk.(2)
For each candidate nodesi∈Φ−sk, as the message t,k−igi arrives, si decrypts the ciphertext and gets the plaintext number k−i. Then, si encrypts k−i collected data items and sends them to the sink, e.g.,(8)si⟶sink:t,idsi,LRi,where(9)LRi=di,jgi|2≤j≤k−i+1,N≥k−i+1,di,jgi|2≤j≤N,N<k−i+1.(3)
The sink obtains the messaget,i,LRi transmitted by the candidate node si∈Φ−sk in the second phase, before the ciphertext of the message is decrypted. The plaintext data after decryption are denoted as DecLRi,gi and appended into Γ. After all messages submitted from the candidate nodes are processed, the minimized candidate encrypted dataset Γ is determined, where(10)Γ=∪si∈Φdi,1∪DecLRi,gi.(4)
The sink gets the top-k data of Γ, which is the exact query result Rt.(11)Rt⊆Γ∧Rt=k∧∀x∈Rt,y∈Γ−Rt⟶x>y.As presented in Protocol 1, the query commandQueryt arrives from the user in the first phase, before the sink broadcasts it through the whole network. As a queried sensor knows Queryt, it encodes the in-node-maximum before transmitting the encrypted data to the sink, where the received ciphertext is decrypted to obtain the in-node-maximums of the queried sensors in the second phase. Afterwards, the sink uses the in-node-maximums to determine the candidate sensor set Φ−sk, and then, it unicasts each candidate sensor in Φ−sk to start the second phase. Once a candidate sensor receives the unicast message, it submits the rest data in ciphertext according to the request to the sink. As the sink obtains all the needed data from candidate nodes, the query result is determined in the end.


## 5.2. Protocol Analysis

### 5.2.1. Correctness Analysis

In the proposed EPCT protocol, when a user starts a query commandQueryt, the sink will know the minimized candidate encrypted dataset Γ after interactions of the sink and sensors within two phases. Γ is consisting of the coded data items of query result. According to Lemma 4, for any di,jgi∉Γ, di,jgi does not belong to the query result Rt, definitely. Additionally, Γ is the minimized candidate encrypted dataset that contains the encrypted query result. Any encrypted data deletion from Γ could incur the incompleteness of query result. As Γ received by the sink, it can get the query result by obtaining the top-k data from Γ. Therefore, our proposed scheme is capable of guaranteeing the correctness of top-k query result.


### 5.2.2. Security Analysis

The security analysis is conducted here for the privacy of the collected data and the query results. With the cooperation of the sink and the sensors in EPCT in these two phases, each node is deployed with a private key, which is only shared with the sink. The collected data of sensors only exists in data submission from sensors to the sink. When a top-k query is started, two phases of query processing are performed. In the first phase, each sensor performs a symmetric encryption to encrypt its in-node-maximum and then transmits it to the sink. Secondly, candidate nodes are unicastly informed by the sink. They encrypted a fixed number of collected data according to the request and then sends the enciphered date to the sink node. Clearly, the data collected and transmitted through the network are all in the form of ciphertext. Every node in WSN owns a unique private key, so it can only get access to the data it collected. However, it fails to know the data collected by other sensors because of the computational infeasibility of symmetric encryption. Even a few nodes probably are attacked and colluded with adversaries, they can only snoop the collected data of those colluded sensors, but they have no idea of the collected data of innocent sensors. Besides, due to the query result is decrypted and computed in the sink and sensor nodes only process the encrypted data for the query, it is hard for the attackers to know the plaintext query result even if a few compromised sensors are colluded with them. Therefore, this proposed EPCT is a privacy-preserving and anticollusion top-k query processing protocol, which can protect the privacy of collected data of sensors even a few compromised sensors are in collusion with the adversaries, which can protect the privacy of collected data from adversaries even a few compromised sensors are in collusion with the adversaries.


### 5.2.3. Communication Cost Analysis

In WSNs, sensors have limited energy resource, and the energy are mainly consumed by communication. During the top-k query procedures, the communication cost of the network is mainly caused by transmission overhead of sensors. The parameters used in sensor networks are introduced in Table 1.Table 1
Parameters description.
ParaDescriptionlidThe space size of a sensor IDltThe space size of a time-slotlcThe space size of a coded data itemlqThe space size of a query commandLThe average path length from sensors to the sinkWe are assuming that the transmission overhead of phase 1 and phase 2 areC1 and C2, respectively. According to the proposed EPCT protocol, all sensors participate in phase 1, whereas only the candidate sensors participate in phase 2. Then, we obtain(12)C1=n⋅lq+n⋅lid+lt+lc⋅L,C2=k−1⋅lt+lc⋅L+∑i=1k−1lid+lt+i⋅lc⋅L=k−1⋅lid⋅L+k−1⋅lid+lt⋅L+k⋅k−12⋅lc⋅L=k−1⋅lid+2lt+lc⋅L+k⋅k−12⋅lc⋅LThe total communication overhead of the whole network is computed as follows:(13)Ctotal=C1+C2=n⋅lq+n+k−1⋅lid+lt+lc⋅L+k−1⋅lt⋅L+k⋅k−12⋅lc⋅L.


## 5.2.1. Correctness Analysis

In the proposed EPCT protocol, when a user starts a query commandQueryt, the sink will know the minimized candidate encrypted dataset Γ after interactions of the sink and sensors within two phases. Γ is consisting of the coded data items of query result. According to Lemma 4, for any di,jgi∉Γ, di,jgi does not belong to the query result Rt, definitely. Additionally, Γ is the minimized candidate encrypted dataset that contains the encrypted query result. Any encrypted data deletion from Γ could incur the incompleteness of query result. As Γ received by the sink, it can get the query result by obtaining the top-k data from Γ. Therefore, our proposed scheme is capable of guaranteeing the correctness of top-k query result.


## 5.2.2. Security Analysis

The security analysis is conducted here for the privacy of the collected data and the query results. With the cooperation of the sink and the sensors in EPCT in these two phases, each node is deployed with a private key, which is only shared with the sink. The collected data of sensors only exists in data submission from sensors to the sink. When a top-k query is started, two phases of query processing are performed. In the first phase, each sensor performs a symmetric encryption to encrypt its in-node-maximum and then transmits it to the sink. Secondly, candidate nodes are unicastly informed by the sink. They encrypted a fixed number of collected data according to the request and then sends the enciphered date to the sink node. Clearly, the data collected and transmitted through the network are all in the form of ciphertext. Every node in WSN owns a unique private key, so it can only get access to the data it collected. However, it fails to know the data collected by other sensors because of the computational infeasibility of symmetric encryption. Even a few nodes probably are attacked and colluded with adversaries, they can only snoop the collected data of those colluded sensors, but they have no idea of the collected data of innocent sensors. Besides, due to the query result is decrypted and computed in the sink and sensor nodes only process the encrypted data for the query, it is hard for the attackers to know the plaintext query result even if a few compromised sensors are colluded with them. Therefore, this proposed EPCT is a privacy-preserving and anticollusion top-k query processing protocol, which can protect the privacy of collected data of sensors even a few compromised sensors are in collusion with the adversaries, which can protect the privacy of collected data from adversaries even a few compromised sensors are in collusion with the adversaries.


## 5.2.3. Communication Cost Analysis

In WSNs, sensors have limited energy resource, and the energy are mainly consumed by communication. During the top-k query procedures, the communication cost of the network is mainly caused by transmission overhead of sensors. The parameters used in sensor networks are introduced in Table 1.Table 1
Parameters description.
ParaDescriptionlidThe space size of a sensor IDltThe space size of a time-slotlcThe space size of a coded data itemlqThe space size of a query commandLThe average path length from sensors to the sinkWe are assuming that the transmission overhead of phase 1 and phase 2 areC1 and C2, respectively. According to the proposed EPCT protocol, all sensors participate in phase 1, whereas only the candidate sensors participate in phase 2. Then, we obtain(12)C1=n⋅lq+n⋅lid+lt+lc⋅L,C2=k−1⋅lt+lc⋅L+∑i=1k−1lid+lt+i⋅lc⋅L=k−1⋅lid⋅L+k−1⋅lid+lt⋅L+k⋅k−12⋅lc⋅L=k−1⋅lid+2lt+lc⋅L+k⋅k−12⋅lc⋅LThe total communication overhead of the whole network is computed as follows:(13)Ctotal=C1+C2=n⋅lq+n+k−1⋅lid+lt+lc⋅L+k−1⋅lt⋅L+k⋅k−12⋅lc⋅L.


## 6. Performance Evaluation

Based on the improved simulator of [34], we implement three protocols, EPCT, PCTQ [31], and a naive protocol (Naive). For Naive scheme, each node queried firstly encodes its k highest data items and then submits them to the sink. After the sink gets all the ciphertext from sensors, it decrypts them to obtain the final query result. The performance is evaluated by the communication overhead in WSNs.This experiment is conducted on a PC with an AMD R5-3600 (6 cores 12 threads 4.2 Ghz) CPU and 32 GB RAM, running 64-bit win 10 professional OS and Java JDK 1.8. In the simulation, we generate 10 networks with random topologies, and each network is distinguished by different network IDs. In each network, sensors are randomly distributed in area covering a 200× 200 m2, and the communicating radius of a sensor is 6 m. The collected data of sensors are randomly generated in each time slot. The network communication cost Ctotal is measured by computing the average result of these 10 networks. The default settings of other parameters are shown in Table 2.(1)
Ctotal versus Network ID. Figure 4 presents that the transmission overhead of these methods are distributed uniformly in different networks. Naive has much higher cost compared with PCTQ and EPCT. Statistically, the communication overhead of EPCT is averagely 89.06% and 43.23% lower than that of Naive and PCTQ, respectively.(2)
Ctotal versus lc. Figure 5 shows that the communication overhead of EPCT, PCTQ, and Naive increases as the space size of an encrypted data item lc increases. The reason is that the transmission overhead of three approaches are all in proportion to the space size of an encrypted data item. The growth rates of communication overhead in EPCT and PCTQ are smaller than that in Naive. Statistically, EPCT reduces about 89.14% and 38.32% transmission overhead than Naive and PCTQ, respectively.(3)
Ctotal versus n. Figure 6 presents that the communication overhead of three schemes grows as the number of sensors n increases. The reason is that the more sensors are queried, the more data are transmitted in the network, i.e., the higher communication costs. Moreover, the curves in Figure 6 tell that the growth rate of transmission overhead in Naive is significantly higher than that in PCTQ and EPCT. Statistically, EPCT saves about 89.51% and 42.00% communication overhead than Naive and PCTQ, respectively.(4)
Ctotal versus k. As shown in Figure 7, the transmission overhead of three methods all increases as the number of requested data items k increases. It is that when k increases, more data items are requested in all three protocols. The growth rates of communication cost in PCTQ and EPCT are both lower than that in Naive. Specifically, EPCT saves about 93.44% and 44.57% on average than Naive and PCTQ in communication cost.Table 2
Default settings of parameters.
ParameternklidlqltlcValue500104 byte8 byte4 byte16 byteFigure 4
Ctotal vs. Network ID.Figure 5
Ctotal vs. l.c.Figure 6
Ctotal vs. n.Figure 7
Ctotal vs. k.According to the results of Figures4–7, the transmission overhead of EPCT is the lowest in three protocols, whereas the overhead of Naive is much higher than the others. Because in EPCT and PCTQ, transmission only caused by candidate sensors need to, whereas in Naive scheme, all sensors are participated in transmission. Specifically, there are k⋅k+1/2, at least k2, and n⋅k encrypted data items are submitted from sensors to the sink in EPCT, PCTQ, and Naive, respectively. As a result, according to the above evaluations, compared with the PCTQ and Naive protocol, it has been shown that the proposed EPCT has less network communication cost and more efficient.


## 7. Conclusion

Data privacy threat arises during providing top-k query processing in the wireless sensor networks. To address this issue, we proposed a novel and efficient top-k query processing approach, which is capable of privacy protection and anticollusion. We fist present a minimized candidate encrypted dataset determination model, which is the foundation of the protocol. The model guides the idea of query processing and guarantees the correctness of the protocol. The symmetric encryption with different private keys in each node is employed for data privacy and even to prevent the attackers from colluding with a few nodes. Based on the above model and security setting, two phases of secure interactions between queried nodes and the sink are designed to implement the query processing protocol. The security analysis shows that our scheme is capable of providing privacy-protecting and collusion-resisting top-k queries, whereas the experimental result indicates that our approach is efficient by evaluating the network communication.



---

*Source: 6234409-2021-11-15.xml*