Query Privacy Preserving for Data Aggregation in Wireless Sensor Networks

Abstract

Wireless Sensor Networks (WSNs) are increasingly involved in many applications. However, communication overhead and energy efficiency of sensor nodes are the major concerns in WSNs. In addition, the broadcast communication mode of WSNs makes the network vulnerable to privacy disclosure when the sensor nodes are subject to malicious behaviours. Based on the abovementioned issues, we present a Queries Privacy Preserving mechanism for Data Aggregation (QPPDA) which may reduce energy consumption by allowing multiple queries to be aggregated into a single packet and preserve data privacy effectively by employing a privacy homomorphic encryption scheme. The performance evaluations obtained from the theoretical analysis and the experimental simulation show that our mechanism can reduce the communication overhead of the network and protect the private data from being compromised.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

As a novel and modern technique, Wireless Sensor Networks (WSNs) have been introduced into a variety of scenarios such as medical applications [1], smart homes [2, 3] autonomous vehicles [4], traffic administration [5] and military battlefields [6]. A WSN is composed of hundreds or thousands of tiny resource-constrained sensor nodes which are generally deployed in an unattended even hostile area. These nodes are difficult to be replaced or recharged. This prevents WSNs from being applied into more critical applications, especially in scenarios where the long lifetime and the high quality services are needed. It is important that traffic and computation overhead should be kept as low as possible to extend the lifetime of WSNs. The Data Aggregation (DA) [7–13] technique is one of the most effective ways for the network to save energy and improve efficiency. It can reduce the quantity of information transmission through aggregating the data from different nodes, decreasing redundancy, and achieving the goal of prolonging the lifetime of the network. Unfortunately, DA is vulnerable to some attacks. Taking the aggregation node as an instance, it is an intermediate tier between sensor nodes and Base Station (BS). The main roles of aggregation nodes are to store the sensing data and reply the queries received from BS. If most of the aggregation nodes have been compromised successfully, the data of whole network may be revealed and tampered with easily. This may result in serious threat or economic loss, even the damage to the safety of state property. Therefore, the Security Data Aggregation (SDA) plays an important role in the critical application of WSNs.

Privacy Preserving (PP) has attracted much attention in many fields, such as smart grid [14], Internet of Things [15, 16], edge computing [17], social network [18] and other application scenarios [19–21]. PP can also protect the privacy of sensing data when DA is adopted in a WSN, and some interesting schemes have been proposed in recent years [22–25]. However, these solutions cannot guarantee the data integrity. Although the schemes discussed in [26–28] exploited the issue of data integrity, they may cause the leakage of concealed data due to the decryption at the aggregation nodes. A proposed scheme in [29] attempted to bridge the gap between PP and data integrity through integrating an encryption algorithm with an MAC authentication mechanism, but it has the risk of putting a heavy computation burden on sensor nodes.

In general, BS has two ways to collect information in a WSN. One is that BS sends a query and the nodes reply accordingly. The other is that the nodes periodically report information to the BS. We focus on the former one in this paper for the reason that the latter one consumes more resources in transmission replies which is inconsistent with our intention of saving energy. The data query has been widely exploited in the current studies. For example, the maximum/minimum query was used to monitor a patient and identify the maximum or minimum value of an indicator which could be regarded as a symbol to determine whether the patient is in a good state or not [30]. Up to now, the single query with PP, such as range query [31], verifiable top-k query [32], and location query [33], has been well addressed. However, the single query method cannot meet the requirements of application when it is introduced into a large-scale network. Therefore, how to enrich the function of query becomes an urgent research challenge. As one of the reasonable solutions, the multiple queries mechanism has been proposed in which many queries can be executed simultaneously [34]. However, the multiple query mechanism with PP is an emerging direction, and many valuable issues need to be solved in the future.

To address the abovementioned issues, we propose a Queries Privacy Preserving mechanism for Data Aggregation (QPPDA) in this paper. The goal of our work is to bridge the gap between PP and energy consumption, and the following techniques are adopted. Firstly, the multiple queries are aggregated into a single packet in order to reduce energy consumption. Then, a homomorphic encryption scheme is carried out, and the confidentiality of private data is ensured. Next, the data for different queries in a single aggregated packet can be distinguished from each other in the decryption of the aggregated data at BS. Compared with the single query, QPPDA may greatly decrease the communication and computation overhead. The main contributions of this paper are as follows.

(i)

Improvement of Gridding Technology. The high computation complexity of cell limits the application of the grid technique. We break this restriction through improving the relative location algorithm in grid topology. As a result, the computation complexity is decreased, and the relative location provides an efficient way to maintain a dynamic WSN.

(ii)

Effective Privacy Preserving. Privacy is easily destroyed by an attacker for a WSN usually deployed in an unattended even hostile environment. The elliptic curve encryption combined with the homomorphic algorithm is adopted to effectively protect the private data from being compromised.

(iii)

Efficient Reply. Sending multiple replies individually leads to the wastage of network resources. Through aggregating the multiple queries into a single packet, the performances of WSN are promoted in terms of energy consumption and lifetime.

The rest of the paper is organized as follows. Section 2 introduces related work. Section 3 discusses the topology construction of the network. Section 4 elaborates our scheme in detail. Section 5 evaluates the performance of QPPDA. We conclude this paper in Section 6.

2. Related Work

2.1. Grid Topology

The connectivity is one of the key issues in WSNs, and many valuable solutions have been proposed to deal with this challenge. A grid-based SDA scheme was proposed in [35]. The whole network was divided into some nonoverlapping virtual cells which were small enough to ensure that the radio coverage of a node can cover its surrounding cells, namely, each node in a cell can directly communicate with the nodes in the neighbouring cells. In [36], the nodes were divided into groups according to their geographic locations with only one node reserved in each group which can connect to the backbone network. In this way, the proposed scheme in [36] not only ensures the connectivity of nodes, but also speeds up the convergence rate of the network. Although the connectivity of the network is guaranteed, the grid topology causes a higher computational complexity than tree or cluster topology.

2.2. Privacy Preserving

As to PP, some cryptographic schemes have been adopted to carry out the hop-by-hop encryption [37]. He et al. presented an Integrity-protecting Private Data Aggregation scheme (IPDA) [38], which is an improvement on the Cluster-based Private Data Aggregation (CPDA) [22]. Both IPDA and CPDA achieve privacy preserving through the technique of data slicing and assembling which ensures integrity by constructing two disjointed aggregation trees. However, the disjointed aggregation trees are computation- and communication-consuming and inapplicable to resource-constrained WSNs. As far as the hop-by-hop scheme is concerned, data privacy cannot be guaranteed because the ciphertext must be decrypted in the intermediate nodes when DA technique is applied. Therefore, the end-to-end scheme is a desirable choice in a network with DA. In [30, 31], the nodes directly sent the encrypted data to the BS without the decryption operation involved in the intermediate nodes. Castelluccia et al. [39] proposed a simple and provable secure additive homomorphic stream which permitted the efficient aggregation of encrypted data. Girao et al. [40] discussed a mechanism which can conceal the sensing data and the aggregation data in an end-to-end manner. Though these schemes are efficient in preserving data privacy of DA, they cannot prevent the private data from being eavesdropped by their neighbours. Compared with [40], the Integrity Protecting Hierarchical Concealed Data Aggregation (IPHCDA) for WSNs ensured that no private data of a sensor node were released to any other nodes under the support of asymmetric cryptography [41]. It employed the elliptic curve-based Privacy Homomorphic (PH) and allowed the concealed aggregation data to be encrypted with different keys. The scheme includes the following steps.

 

Step 1: generate key pairs according to the point on the elliptic curve $\left(p_u,p_r\right)$.

 

Step 2: encrypt $m$ using $c=g^m+h^r$, where $+$ is the addition operation of elliptic curve points, $r$ is a random number, and $g^m$ and $h^r$ are the scalar multiplication of elliptic curve points.

 

Step 3: perform the DA. Two ciphertexts $\left(c_1=g^{m_1}+h^{r_1},c_2=g^{m_2}+h^{r_2}\right)$ are fused to a single ciphertext $c\prime =c_1+c_2=g^{m_1+m_2}+h^{r_1+r_2}$.

 

Step 4: decrypt a ciphertext using the private key $p_r$ at BS.

2.3. Query Privacy Preserving

The contributions presented in [42–44] investigated the privacy schemes of single query when attackers attempted to tamper with or eavesdrop on the private information of nodes. Papadopoulos et al. proposed a privacy-preserving scheme of range query [42] based on the bucketing technique [45], in which the domain of data values was divided into multiple buckets, and the time was divided into slots as well. In each time slot, data items collected by a sensor node were classified into different buckets with different IDs. If BS wants to perform a range query, it does not send the range directly. Instead, the bucket with various IDs that covers the required range is sent to the storage nodes. However, the bucket partitioning technique cannot prevent a compromised storage node from carrying out malicious activities in a WSN. Faced with this challenge, the proposed scheme in [46] discussed the privacy of query by encoding the sensing data. However, it needs high computation overhead and communication cost. To the best of our knowledge, rare contribution is found in investigating the privacy preserving of multiple queries with DA.

Different from the abovementioned approaches, QPPDA has the advantages of decreasing the resource consumption and protecting the private data from being compromised simultaneously.

3. Network Model

3.1. Sensor Networks and Data Aggregation Model

A sensor network is modelled to a grid which is divided into many cells with each one containing a number of sensor nodes. There are three types of nodes in a network: BS, Aggregation Node (AN), and Member Node (MN). It is assumed that BS is trusted and has unlimited energy, computing resource, and storage capacity. MN collects the sensing data and sends them to AN. And AN is responsible for forwarding the query sent by BS and aggregating the data of MNs. The network size is $N$ which means that there are $N$ nodes in a WSN. The sensor nodes are organized into a grid structure as shown in Figure 1. Notice that we adopt the three-dimensional model rather than other two dimensional models in most of the related works with grid topology. This model may expand the application scenario of QPPDA, and it can be used in many complex natural environments.

[figure omitted; refer to PDF]

Let $D=\left\{d_1,d_2,\dots ,d_N\right\}$ be raw data gathered at MNs. The set of sensing data, $D$, can be transmitted to BS hop-by-hop. However, transmitting all the raw data to BS may result in a huge burden on the bandwidth and high energy consumption. Therefore, DA is a favorite technique to decrease the occupancy of resources.

A data aggregation function is defined as $y\left(t\right)=f\left(d_1\left(t\right),d_2\left(t\right),\dots ,d_N\left(t\right)\right)$ at time $t$, where $f$ represents the aggregation function which may be addition, average, min, max, and count. We focus on addition aggregation functions in our model $f\left(t\right)={\displaystyle {\sum }_{i=1}^N{d}_i\left(t\right)}$. It should be noticed that the addition aggregation function is not too restrictive because many other functions such as average and count which can be deduced from the addition function.

3.2. Threat Model

When queries are initialized, BS broadcasts them to the whole network. The nodes which meet the requirements of the queries send their reply data to AN, and the data are sensitive to the malicious activates if the security mechanism is absent. We adopt the well-known “honest but curious” threat model [47], in which the adversaries attempt to break the privacy but faithfully follow the protocol specification during the process of DA. Meanwhile, adversaries can overhear the original data of sensors through eavesdropping on the wireless link. In addition, a few nodes may collude with each other to violate the data privacy of the overall network.

4. Privacy Data Aggregation Protocol

We present a privacy data aggregation protocol called Queries Privacy Protection for Data Aggregation (QPPDA) which involves three phases: the grid division, the key generation, and the query processing. Firstly, a network is divided into adjacent virtual cells, and the nodes within neighbouring cells can directly communicate with each other. Secondly, the corresponding key for each type of query is generated in order to guarantee the data privacy. Finally, the nodes aggregate multiple replies into a single packet which is transmitted to BS hop-by-hop.

4.1. Grid Division

The grid division phase is responsible for the construction of the network structure. In the Geographical Adaptive Fidelity (GAF) algorithm, a network area was divided into grid topology which consisted of many contiguous cells according to the geographic information and the radio coverage of nodes [46]. In order to make GAF suitable for the WSNs in practice, some improvements of GAF were proposed, and a relative position was adopted to obtain the grid information [48]. However, some valuable issues, such as data privacy and accuracy, are left for future study.

We define all the cells that have a common edge as the neighboring cells. In the division process, it should be determined that all the nodes of a cell can directly communicate with the nodes in the neighboring cells. Thus, equation (1) needs to be satisfied.$$\begin{array}{}\text{(1)}& r^2+{\left(2r\right)}^2+{\left(2r\right)}^2\le R^2⟶9r^2\le R^2⟶r\le \frac{1}{3}R,\end{array}$$where $r$ denotes the side length of the cell and $R$ is the communication radius of the node.

The relationship between $r$ and $R$ can be shown as Figure 2. We take the following steps to divide a grid into adjacent cells. Firstly, BS broadcasts its location, $L_{bs}\left(x_{bs},y_{bs},z_{bs}\right)$, and the side length $r$ of each cell to all the nodes in a WSN. Node $i\left(x_i,y_i,z_i\right)$ can calculate the coordinate of cell $G_i\left(g\left(x_i\right),g\left(y_i\right),g\left(z_i\right)\right)$ and determine which cell node $i$ belongs to using the following equation:$$\begin{array}{}\text{(2)}& \left\{\begin{array}{c}g\left(x_i\right)=⌈\frac{\left(x_i-x_{bs}\right)}{r}⌉,\\ g\left(y_i\right)=⌈\frac{\left(y_i-y_{bs}\right)}{r}⌉,\\ g\left(z_i\right)=⌈\frac{\left(z_i-z_{bs}\right)}{r}⌉.\end{array}\right.\end{array}$$

[figure omitted; refer to PDF]

Now, we use a simple example to explain why we use the top integral instead of the bottom integral when the cell coordinate is determined in equation (2). Assume that the coordinate of node $i$ is (9, 11, 10) and that of BS is (0, 0, 0), respectively. The side length $r$ is 4, as shown in Figure 3. We firstly calculate the cell where node $i$ stays using the top integral according to equation (2) $g\left(x\right)=\left(9-0\right)/4=3$, $g\left(y\right)=\left(11-0\right)/4=3$, $g\left(z\right)=\left(10-0\right)/4=3$. Therefore, node $i$ is inside $G_i$(3, 3, 3). On the contrary, we can obtain $G_i$ is (2, 2, 2) using the bottom integral. It can be seen from Figure 3 that $G_i$(3, 3, 3) is the desired one.

[figure omitted; refer to PDF]

The pseudocode of the grid division is listed in Algorithm 1. $N$ nodes compute their coordinates from Line 1 to Line 10, and the computation complexity of grid division is $O\left(N\right)$.

Algorithm 1: The grid division.

 

Input: The side length of cell, $r$; The communication radius, $R$; The position of BS, $L_{bs}\left(x_{bs},y_{bs},z_{bs}\right)$; The position of a node, $i\left(x_i,y_i,z_i\right)$.

 

Output: the nodes belong to the cells, $G=\left\{G_1,G_2,\dots ,G_N\right\}$.

(1)

Begin

(2)

 BS broadcasts $L_{bs}$

(3)

For ($i=1;i\le N;i++$)

(4)

 If node $i$ receives $L_{bs}$ then

(5)

  Calculate $G_i\left(g\left(x_i\right),g\left(y_i\right),g\left(z_i\right)\right)$ according to equation (2)

(6)

  $\left\{\begin{array}{c}g\left(x\right)=\lceil \left(x_i-x_{bs}\right)/r\rceil ,\\ g\left(y\right)=\lceil \left(y_i-y_{bs}\right)/r\rceil ,\\ g\left(z\right)=\lceil \left(z_i-z_{bs}\right)/r\rceil .\end{array}\right.$

(7)

  Obtain the position $G\left(g\left(x_i\right),g\left(y_i\right),g\left(z_i\right)\right)$;

(8)

 End If

(9)

End For

(10)

Return Cell information of all nodes, $G=\left\{G_1,G_2,\dots ,G_N\right\}$.

(11)

End

After the grid is divided into cells, some sensor nodes (ANs) in different cells are selected and organized into an aggregation tree rooted at BS. In a cell, the member nodes send the data to AN, and AN sends the aggregation results to BS hop-by-hop along the aggregation tree. Figure 4 demonstrates the aggregation tree and the data aggregation in a cell, respectively.

[figure omitted; refer to PDF]

4.2. Key Generation

We introduce the homomorphic encryption scheme based on the elliptic curve [14] into QPPDA, which can protect private data from being revealed. The encryption method assigns different keys to the concealed data acquired from different nodes, and BS can correctly distinguish them in the aggregation process [41].

Assume that $k$ types of query are supported by a network. Therefore, $k$ public and private key pairs are required. We take the following steps to generate the key pairs.

Given a parameter $\tau$, we define an algorithm $\Psi \left(\tau \right)$ to output a tuple ($q_1,q_2,\dots ,q_{k+1},E$), where $E$ is a set of elliptic curve points that form a cyclic group. The order of E is $n$ where $n=q_1\times q_2\times \cdots \times q_{k+1}$. $\Psi \left(\tau \right)$ works as follows.

(i)

Generate $k+1$ random $\tau$-bit primes ($q_1,q_2,\dots ,q_{k+1},E$) and set $n=q_1\times q_2\times \cdots \times q_{k+1}$

(ii)

Generate a set of elliptic curve points $E$

(iii)

Output the security elements ()

The points $\left({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{k+1},\beta \right)$ are randomly chosen, and the order of these points are $n$. Then, we calculate $\gamma$ as$$\begin{array}{}\text{(3)}& \gamma ={\alpha }_{k+1}^{{\displaystyle {\prod }_{r=1}^k{q}_r}}.\end{array}$$

The order of $\gamma$ is $q_{k+1}$. Next, $k$ public keys are computed for $k$ queries according to the following equation:$$\begin{array}{c}\text{(4)}& h_j={\beta }_j^{\delta },\delta ={\displaystyle \prod _{r=1,r\ne j}^{k+1}{q}_r},\\ j=\mathrm{1,2},\dots ,k,\end{array}$$where the order of $h_j$ is $q_j$. Finally, we establish the public key set $P_{uk}=\left\{n,E,h_1,h_2,\dots ,h_k,\beta ,\gamma \right\}$ and the private key set $P_{rk}=\left\{q_1,q_2,\dots ,q_{k+1}\right\}$. Therefore, the $j$th key pair, ($P_{uj},P_{rj}$) is generated for the $j$th query.

The key generation is illustrated in Algorithm 2 where Lines 4 to 6 obtain a tuple by the elliptic curve algorithm, and Lines 7 to 15 display the process of producing keys. $N$ nodes execute the elliptic curve algorithm to generate key pairs for $k$ queries with the complexity of $O\left(N^2\right)$.

Algorithm 2: The key generation.

 

Input: security parameter, $\tau$; query types, $k$.

 

Output: key sets ($P_{uk},P_{rk}$).

(1)

Begin

(2)

 Generate a tuple $\left(\cdot \right)$

(3)

 Find $k+1$ random $\tau$-bit primes $\left\{q_1,q_2,\dots ,q_{k+1}\right\}$

(4)

 Let $n=q_1\times q_2\times \cdots \times q_{k+1}$

(5)

 Find a set of elliptic curve points $E$

(6)

 Generate a tuple ($q_1,q_2,\dots ,q_{k+1},E$)

(7)

 For node $\left(i=1;i<=N;i++\right)$

(8)

  Choose points $\left({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{k+1},\beta \right)$ from $E$

(9)

  $\gamma ={\alpha }_{k+1}{\displaystyle {\prod }_{r=1}^k{q}_r}$

(10)

  For query ($j=1;j<=k;j++$)

(11)

   $h_j={\beta }_j^{\delta }$, $\delta ={\displaystyle {\prod }_{r=1,r\ne j}^{k+1}{q}_r}$, $j=\mathrm{1,2},\dots ,k$

(12)

   $p{k}_j\in P_{uk}=\left\{n,E,h_1,h_2,\dots ,h_k,\beta ,\gamma \right\}$

(13)

   $p{r}_j\in P_{rk}=\left\{q_1,q_2,\dots ,q_{k+1}\right\}$

(14)

  End For

(15)

 End For

(16)

 Return ($P_{uk},P_{rk}$).

(17)

End

4.3. Query Processing

After the aggregator receives a request of query from BS, it broadcasts $Q=\left(\text{type}=p,\text{epoch}=t,\text{time}=T\right)$ to node $i\left(i=\mathrm{1,2},\dots ,N\right)$, where $p$ and $t$ represent the types of queries and the query epoch, respectively. $T$ denotes the time that AN spends on replying to BS. Four steps should be taken to process the query: the data collection, the data encryption, the data aggregation, and the data decryption.

4.3.1. Data Collection

After receiving the queries, the nodes collect the sensing data $d_i\in \left\{\mathrm{0,1},\dots ,D\right\}$ where $D$ is the maximum value of $d_i$ according to the query types.

4.3.2. Data Encryption

The nodes encrypt data using the public key and the encryption process is as follows.

 

Step 1: a node chooses a random number $r$ from $\left\{\mathrm{0,1},\dots ,N-1\right\}$.

 

Step 2: node $i$ selects a key according to the type of query. If the type of query is $x$, that is $p=x$, the public key is $P_{uk}=P_{ux}=\left(n,E,g,h_x\right)$, where $h_x=u^{q^{j+1}}$.

 

Step 3: Node $i$ computes the ciphertext $C_i^x=f\left(d_i\right)=\left(g^{d_i}+h_x^{r_x}\right)$.

4.3.3. Data Aggregation

Let $d_x$ denote the reply message of the $x$th query. Consequently, $k$ ciphertexts in node $i$ (aggregator) are aggregated into a ciphertext of $C_i^{\prime }$ using the following equation:$$\begin{array}{}\text{(5)}& C_i^{\prime }=f\left({\displaystyle \sum _{x=1}^k{d}_x}\right)={\displaystyle \sum _{x=1}^k{g}^{d_x}}+h_x^{r_x}=g^{{\displaystyle {\sum }_{x=1}^k{d}_x}}+h_x^{{\displaystyle {\sum }_{x=1}^k{r}_x}}.\end{array}$$

4.3.4. Data Decryption

During the decryption, BS is able to decrypt the data of each query separately from the aggregated ciphertext $C_i^{\prime }$. To decrypt a ciphertext $C_i^x$, BS needs to obtain the plaintext from equation (6) using the private key $q_x$.$$\begin{array}{}\text{(6)}& d_x={\log }_{g^{q_x}}{\left(C_i^x\right)}^{q_x}.\end{array}$$

The pseudocode of query processing is shown in Algorithm 3. Lines 1 to 10 describe the data collection, the data encryption, and the data aggregation in detail. Lines 11 to 16 delineate the process of separating the decryption data at BS with the complexity of $O\left(N\right)$.

Algorithm 3: The query processing.

 

Input: query $Q=\left(\text{type}=p,\text{epoch}=t,\text{time}=T\right)$.

 

Output: decrypted data of each query $x$, $d_x$.

(1)

Begin

(2)

 For node ($i=1;i\le N;i++$)

(3)

  If ($p==x$) Then

(4)

   Collect the data $d_i\in \left\{\mathrm{0,1}\dots ,M\right\}$;

(5)

   Choose a random number $r$ from $\left\{\mathrm{0,1},\dots ,N-1\right\}$;

(6)

   Select a key $P_{ux}=\left(n,E,g,h_x\right)$;

(7)

   Encrypt the data, $C_i^x=f\left(d\right)=\left(g^d+h_x^{r_x}\right)$;

(8)

   Aggregate the data, $C_i^{\prime }=f\left({\displaystyle {\sum }_{x=1}^k{d}_x}\right)=g^{{\displaystyle {\sum }_{x=1}^k{d}_x}}+h_x^{{\displaystyle {\sum }_{x=1}^k{r}_x}}$;

(9)

  End If

(10)

 End For

(11)

 For ($i=1;i\le x;i++$) at BS

(12)

  Decrypt the data, $d_x={\log }_{g^{q_x}}{\left(C_i^x\right)}^{q_x}$;

(13)

 End If

(14)

 Return $\left\{d_1,d_2,\dots ,d_x\right\}$

(15)

End

5. Performance Analysis and Simulation Experiment

We evaluated the performance of QPPDA in terms of privacy preservation, communication efficiency, and computation overhead through theoretical analysis and simulation experiment. QPPDA was implemented using MATLAB. A WSN with 600 nodes was considered, and these nodes were randomly deployed in a 400 m $\ast$ 400 m area. The transmission range of the sensor node was 50 m.

5.1. Privacy-Preservation Analysis

We analyze the privacy preservation performance of QPPDA when a node is compromised by physical attack. If an adversary compromises an AN, it can perform an unauthorized aggregation and send false aggregation results to BS. However, due to the asymmetry of public key, an adversary cannot gain any additional information related to the data aggregation. Hence, the compromised node may affect the data integrity but not the data confidentiality in QPPDA.

Through the analysis, we can conclude that the privacy can be revealed because of the leakage of keys. Assume that $p_{\text{ovk}}$ and $p_{\text{ovr}}$ are the probabilities of the key and the random number which are broken, respectively. Therefore, the probability of information leakage is $p={\left(p_{\text{ovk}}\times p_{\text{ovr}}\right)}^k$. Figure 5 demonstrates the privacy performance of different types of the queries. We may find that the exposure probability of privacy is less than 0.45% even if the reveal probability of key is 0.4. Besides, the more frequently the queries are sent, the better the data confidentiality will be. This proves that QPPDA can effectively preserve the data privacy.

[figure omitted; refer to PDF]

5.2. Energy Consumption

In our experiments, we considered the efficiency of communication and computation and adopted the typical data query schemes, the single query [42] and the Slice-Mix-AggRegaTe (SMART) [22], as the benchmarks to verify the energy consumption of QPPDA.

5.2.1. Communication Overhead

Communication overhead is mainly derived from data transmission, e.g., a node transmits its sensing data to AN or BS in a WSN. For node $i$, the length of data is $l_{ci}$ bits and the average number of hops between any two nodes is $L$. Thus, the communication overhead of a cell with $k$ queries can be computed as$$\begin{array}{}\text{(7)}& C_{TK}={\displaystyle \sum }_{i=1}^N{l}_{ci}L.\end{array}$$

The overhead of a single query comes from sending the encrypted data and HMACs. The HAMCs of node $i$ is $l_{hi}$ bits and the data is $l_{ci}$ bits. Then, the overhead of a cell with $k$ single queries are formalized as$$\begin{array}{}\text{(8)}& C_{Ts}={\displaystyle \sum }_{i=1}^N\left[\left(3l_{ci}-1\right)l_{hi}+l_{ci}\right]Lk.\end{array}$$

In SMART, each node divides its sensing data into three slices, two of which are sent to the neighboring nodes and one is preserved by itself. Assume that a node receives $n$ slices from other nodes. Therefore, the overhead with $k$ queries can be described as$$\begin{array}{}\text{(9)}& C_{T\text{smart}}={\displaystyle \sum }_{i=1}^N\left(\frac{2}{3}+\frac{n}{3}\right)l_{ci}LK.\end{array}$$

Figure 6 shows the communication consumption of QPPDA, Single query, and SMART, where SMART-$n$ denotes that a node receives $n$ slices. A conclusion can be drawn from Figure 6 that the communication overhead of QPPDA is much less than that of SMART-$n$ or Single query. QPPDA is one of the most efficient schemes in decreasing the communication overhead.

[figure omitted; refer to PDF]

5.2.2. Computation Cost

Single query converts the query scope to a prefix format before the data are transmitted. The number of binary prefix is nearly $\left(2l_{ci}-2\right)$, and there are exactly $\left(l_{ci}+1\right)$ prefixes. Therefore, the node needs to perform about $\left(2l_{ci}-2\right)\ast \left(l_{ci}+1\right)$ comparisons, and the computation complexity of query is $O\left(w^{2}Nk\right)$ in the worst case. The computation overhead of QPPDA comes from data encryption, and its computation complexity is $O\left(l_{ci}{N}^2\right)$ according to Algorithm 2. Data mixing is the prime computational consumption in SMART, which is $O\left(N\right)$. Consequently, it is observed that the computation consumption of single query is higher than that of QPPDA and SMART when the number of nodes is fixed in a WSN according to Figure 7. It should be noticed that the computation overhead of SMART is less than that of QPPDA when one slice mechanism (SMART-1) is adopted. However, one slice SMART may result in a lower security level compared with QPPDA. Therefore, our scheme is a better tradeoff between security and computation complexity.

[figure omitted; refer to PDF]

5.3. Aggregation Accuracy

The accuracy is defined as the ratio between the collected summation by the data aggregation and the real summation of all individual sensor nodes in [22]. Figure 8 illustrates the accuracy of QPPDA, Single query, and SMART with respect to different query times in our simulation. From Figure 8, we can observe that the accuracy of QPPDA improves as the times of query increase. Two reasons contribute to this which have already been analyzed in [8]: (i) with a longer time interval, the data messages to be sent within this duration will have less chance to collide; (ii) with a longer time interval, the data messages will have a better chance of being delivered before the deadline.

[figure omitted; refer to PDF]

Besides, we can observe that QPPDA has a better accuracy than single query and SMART. It has been demonstrated that the communication overhead of QPPDA is reduced significantly, and the amount of transmission of QPPDA is much less than that of single query and SMART in Section 5.2.1. Therefore, the chance of collision and packet loss are also decreased, which leads to an improvement in aggregation accuracy.

6. Conclusion

The energy consumption and data privacy are two important concerns in WSNs. The limited energy of sensor nodes may shorten the lifetime of network, and the nodes are often deployed in dangerous areas where the data privacy may be more likely to be destroyed easier than in the cable network. Faced with these challenges, we present a query privacy protection mechanism for data aggregation which can reduce energy consumption and preserve the data privacy as well. Experimental results show that our scheme can guarantee the data privacy, decrease the system overhead, and improve the accuracy of data aggregation. For the future work, we will focus on other aggregation functions, such as mean, max, and counter except the additive aggregation. The privacy of QPPDA is closely related to the number of keys, and it is a challenging work to promote the security of QPPDA without the complex key distribution so as to save energy and decrease the requirement of storage. In addition, tree or cluster topology will be discussed in our subsequent study in order to expand the application scenarios of our scheme.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant nos. 61672321, 61832012, 61771289, and 61373027 and the Shandong Graduate Education Quality Improvement Plan SDYY17138.

References

[1] A. B. García-Hernando, J. F. Martínez-Ortega, J. M. López-Navarro, A. Prayati, L. Redondo-López, WSN Application Scenarios: Problem Solving for Wireless Sensor Networks, 2008.

[2] W. Huiyong, W. Jingyang, H. Min, "Building a smart home system with WSN and service robot," Proceedings of the 5th International Conference on Measuring Technology and Mechatronics Automation, pp. 353-356, DOI: 10.1109/icmtma.2013.90, .

[3] T. Song, R. Li, B. Mei, J. Yu, X. Xing, X. Cheng, "A privacy preserving communication protocol for IoT applications in smart homes," IEEE Internet of Things Journal, vol. 4 no. 12, pp. 1844-1852, DOI: 10.1109/jiot.2017.2707489, 2017.

[4] J. Wang, Z. Cai, J. Yu, "Achieving personalized k-anonymity based content privacy for autonomous vehicles in CPS," IEEE Transactions on Industrial Informatics,DOI: 10.1109/TII.2019.2950057, 2019.

[5] Z. Cai, X. Zheng, J. Yu, "A differential-private framework for urban traffic flows estimation via taxi companies," IEEE Transactions on Industrial Informatics, vol. 15 no. 12, pp. 6492-6499, DOI: 10.1109/tii.2019.2911697, 2019.

[6] M. Hussain, P. Khan, K. K. Sup, "WSN research activities for military application," Proceedings of the 11th International Conference on Advanced Communication Technology, pp. 271-274, .

[7] S. Ozdemir, Y. Xiao, "Secure data aggregation in wireless sensor networks: a comprehensive overview," Computer Networks, vol. 53 no. 12, pp. 2022-2037, DOI: 10.1016/j.comnet.2009.02.023, 2009.

[8] B. Sujatha, C. T. Jilo, C. S. Rao, "Energy-efficient data route-in-network aggregation with secure eedrina," Proceedings of the International Conference on Computational Intelligence and Data Engineering,DOI: 10.1007/978-981-10-6319-0_1, .

[9] E. Choudhari, K. D. Bodhe, S. M. Mundada, "Secure data aggregation in wsn using iterative filtering algorithm," Proceedings of the International Conference on Innovative Mechanisms for Industry Applications,DOI: 10.1109/icimia.2017.7975603, .

[10] H. Wang, Z. Wang, J. Domingo-Ferrer, "Anonymous and secure aggregation scheme in fog-based public cloud computing," Future Generation Computer Systems, vol. 78, pp. 712-719, DOI: 10.1016/j.future.2017.02.032, 2018.

[11] H. Wang, D. He, J. Yu, Z. Wang, "Incentive and unconditionally anonymous identity-based public provable data possession," IEEE Transactions on Services Computing, vol. 12 no. 5, pp. 824-835, DOI: 10.1109/tsc.2016.2633260, 2019.

[12] H. Wang, Q. Wang, D. He, "Blockchain-based private provable data possession," IEEE Transactions on Dependable and Secure Computing,DOI: 10.1109/TDSC.2019.2949809, 2019.

[13] H. Wang, D. He, A. Fu, Q. Li, Q. Wang, "Provable data possession with outsourced data transfer," IEEE Transactions on Services Computing,DOI: 10.1109/TSC.2019.2892095, 2019.

[14] D. He, S. Zeadally, H. Wang, Q. Liu, "Lightweight data aggregation scheme against internal attackers in smart grid using elliptic curve cryptography," Wireless Communications and Mobile Computing, vol. 2017,DOI: 10.1155/2017/3194845, 2017.

[15] H. Yan, C. Yong, Y. Lu, "Re-ADP: real-time data aggregation with adaptive-event differential privacy for fog computing," Wireless Communications and Mobile Computing, vol. 2018,DOI: 10.1155/2018/6285719, 2018.

[16] Y. Pu, J. Luo, C. Hu, "Two secure privacy-preserving data aggregation schemes for IoT," Wireless Communications and Mobile Computing, vol. 2019,DOI: 10.1155/2019/3985232, 2019.

[17] Y. Xiao, Y. Jia, C. Liu, X. Cheng, J. Yu, W. Lv, "Edge computing security: state of the art and challenges," Proceedings of the IEEE, vol. 107 no. 8, pp. 1608-1631, DOI: 10.1109/jproc.2019.2918437, 2019.

[18] Z. He, Z. Cai, J. Yu, "Latent-data privacy preserving with customized data utility for social network data," IEEE Transactions on Vehicular Technology, vol. 67 no. 1, pp. 665-673, DOI: 10.1109/tvt.2017.2738018, 2018.

[19] X. Liu, J. Yu, F. Li, W. Lv, Y. Wang, X. Cheng, "Data aggregation in wireless sensor networks: from the perspective of security," IEEE Internet of Things Journal,DOI: 10.1109/JIOT.2019.2957396, 2019.

[20] L. Ni, C. Li, X. Wang, H. Jiang, J. Yu, "DP-MCDBSCAN: differential privacy preserving multi-core DBSCAN clustering for network user data," IEEE Access, vol. 6, pp. 21053-21063, DOI: 10.1109/access.2018.2824798, 2018.

[21] W. Li, C. Hu, T. Song, J. Yu, X. Xing, Z. Cai, "Privacy-preserving data collection in context-aware applications," Proceedings of IEEE Symposium on Privacy-Aware Computing (PAC), pp. 75-85, DOI: 10.1109/pac.2018.00014, .

[22] W. He, X. Liu, H. Nguyen, K. Nahrstedt, T. Abdelzaher, "PDA: privacy-preserving data aggregation in wireless sensor networks," Proceedings of the 26th International Conference on Computer Communications, pp. 2045-2053, DOI: 10.1109/infcom.2007.237, .

[23] T. Jung, X. Mao, X. Li, S.-J. Tang, W. Gong, L. Zhang, "Privacy-preserving data aggregation without secure channel: multivariate polynomial evaluation," Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 2734-2742, DOI: 10.1109/infcom.2013.6567071, .

[24] K. Xing, Z. Wan, P. Hu, "Mutual privacy-preserving regression modeling in participatory sensing," Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 3039-3047, DOI: 10.1109/infcom.2013.6567116, .

[25] G. Yang, S. Li, X. Xu, H. Dai, Z. Yang, "Precision-enhanced and encryption-mixed privacy-preserving data aggregation in wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 9 no. 4,DOI: 10.1155/2013/427275, 2013.

[26] Y. Yang, X. Wang, S. Zhu, G. Cao, "SDAP: a secure hop-by-hop data aggregation protocol for sensor network," Proceedings of 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 356-367, .

[27] K. B. Frikken, K. Kauffman, K. Steele, "General secure sensor aggregation in the presence of malicious nodes," Proceedings of the 27th International Proceedings on Data Engineering, pp. 506-516, DOI: 10.1109/icde.2011.5767849, .

[28] L. Zhu, Z. Yang, M. Li, D. Liu, "An efficient data aggregation protocol concentrated on data integrity in wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 9 no. 5,DOI: 10.1155/2013/256852, 2013.

[29] Q. Zhou, G. Yang, L. He, "An efficient secure data aggregation based on homomorphic primitives in wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 10 no. 1,DOI: 10.1155/2014/962925, 2014.

[30] H. Dai, X. Qin, L. Liu, Y.-M. Ji, X. Fu, Y. Sun, "Z-O encoding based privacy-preserving max/min query protocol in two-tiered wireless sensor networks," Journal of Electronics Information Technology, vol. 35 no. 4, pp. 970-976, 2013.

[31] T. Wang, L. Qin, L. Liang, "Privacy-preserving range query in two-tiered wireless sensor networks," Journal of Beijing University of Posts Telecommunications, vol. 37 no. 2, pp. 104-108, 2014.

[32] S. Shekhar, H. Xiong, Top-K Query, 2008.

[33] D. Song, M. Song, K. Park, "A privacy-preserving spatial index for spatial query processing," Wireless Communications and Mobile Computing, vol. 2018,DOI: 10.1155/2018/2067047, 2018.

[34] E. G. Prathima, T. S. Prakash, K. R. Venugopal, S. S. Iyengar, L. M. Patnaik, "SDAMQ: secure data aggregation for multiple queries in wireless sensor networks," Procedia Computer Science, vol. 89, pp. 283-292, DOI: 10.1016/j.procs.2016.06.060, 2016.

[35] Y. Xu, J. Heidemann, D. Estrin, "Geography-informed energy conservation for ad-hoc routing," Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 70-84, DOI: 10.1145/381677.381685, .

[36] X. Luo, Y. Yan, S. Li, X. Guan, "Topology control based on optimally rigid graph in wireless sensor networks," Computer Networks, vol. 57 no. 4, pp. 1037-1047, DOI: 10.1016/j.comnet.2012.12.002, 2013.

[37] H. Li, K. Lin, K. Li, Energy-efficient and High-Accuracy Secure Data Aggregation in Wireless Sensor Networks, 2011.

[38] W. He, H. Nguyen, X. Liuy, K. Nahrstedt, T. Abdelzaher, "iPDA: an integrity-protecting private data aggregation scheme for wireless sensor networks," Proceedings of the International Conference on Military Communications,DOI: 10.1109/milcom.2008.4753645, .

[39] C. Castelluccia, E. Mykletun, G. Tsudik, "Efficient aggregation of encrypted data in wireless sensor networks," Proceedings of International Conference on Mobile and Ubiquitous Systems, pp. 109-117, .

[40] J. Girao, D. Westhoff, M. Schneider, "CDA: concealed data aggregation for reverse multicast traffic in wireless sensor networks," Proceedings on the International Conference on Communications, pp. 3044-3049, DOI: 10.1109/icc.2005.1494953, .

[41] S. Ozdemir, Y. Xiao, "Integrity protecting hierarchical concealed data aggregation for wireless sensor networks," Computer Networks, vol. 55 no. 8, pp. 1735-1746, DOI: 10.1016/j.comnet.2011.01.006, 2011.

[42] S. Papadopoulos, A. Kiayias, D. Papadias, "Exact in-network aggregation with integrity and confidentiality," IEEE Transactions on Knowledge and Data Engineering, vol. 24 no. 10, pp. 1760-1773, DOI: 10.1109/tkde.2012.64, 2012.

[43] C. Castelluccia, A. C.-F. Chan, E. Mykletun, G. Tsudik, "Efficient and provably secure aggregation of encrypted data in wireless sensor networks," ACM Transactions on Sensor Networks, vol. 5 no. 3,DOI: 10.1145/1525856.1525858, 2009.

[44] B. Sheng, Q. Li, "Verifiable privacy-preserving range query in two-tiered sensor networks," Proceedings of International Conference on Computer Communications, pp. 46-50, DOI: 10.1109/infocom.2008.18, .

[45] J. Shi, R. Zhang, Y. Zhang, "Secure range queries in tiered sensor networks," Proceedings of the International Conference on Information Communications, pp. 945-953, DOI: 10.1109/infcom.2009.5062005, .

[46] F. Chen, A. Liu, "SafeQ: secure and efficient query processing in sensor networks," Proceedings of the International Conference on Information Communications, pp. 2642-2650, DOI: 10.1109/infcom.2010.5462094, .

[47] O. Goldreich, Foundations of Cryptography: Basic Applications, 2004.

[48] X. Dong, "Secure data aggregation approach based on monitoring in wireless sensor networks," China Communications, vol. 3 no. 3, pp. 101-148, 2012.