EMQP: An Energy-Efficient Privacy-Preserving MAX/MIN Query Processing in Tiered Wireless Sensor Networks

Abstract

We consider a hybrid two-tiered sensor network consisting of regular resource-limited sensor nodes and powerful master nodes with abundant resources. In the architecture, master nodes take charge of storing data collected by sensor nodes and processing queries from the base station. Due to the important role of master nodes, they might easily become the target for the adversary to compromise in an untrusted or hostile circumstance. A compromised master node may leak sensitive data in its storage to the adversary, which breaches the data privacy. This paper proposes EMQP, a novel and energy-efficient privacy-preserving MAX/MIN query protocol which is capable of preventing adversaries from obtaining sensitive data collected by sensor nodes. To preserve privacy, the 0-1 encoding verification, keyed-hash message authentication coding, and symmetric encryption are applied to achieve the secret comparison of data items without knowing their real values. On the basis of secret comparison mechanism, the data submission and query processing protocols are proposed to describe the details of EMQP. And the analyses on privacy protection and energy consumption are also given. Moreover, a hash-based optimization method is presented to save more energy of the resource-limited sensor nodes. The simulation result shows that EMQP is more efficient than the current work in energy consumption.

1. Introduction

Wireless sensor networks (WSNs) have been widely used in a variety of important areas, such as environment sensing, battlefield monitoring, and volcanic eruption predication. In this paper, we consider a two-tiered wireless sensor network (two-tiered WSNs) [1, 2] as shown in Figure 1, which consists of a large number of sensor nodes at the lower tier and relatively fewer master nodes at the upper tier. Sensor nodes are resource limited (computation, storage, energy, etc.) and take charge of collecting data and periodically submitting it to a nearby master node for storage, while master nodes have rich resources, and answer for the ad hoc data queries from the base station which are issued via an on-demand wireless (e.g., satellite) link. It is necessary to maintain such in-network data storage and query processing in remote and tough environments, where it is infeasible or difficult to keep connection between the sensor networks and the base station with the high-speed and always-on manner. The two-tiered architecture is also known to be indispensable for increasing network capacity and scalability, reducing system complexity, and prolonging network lifetime.

Figure 1

A two-tiered sensor network architecture.

As master nodes are responsible for data storage and query answering in networks, they are much more attractive and vulnerable to adversaries in a hostile environment. Once a master node is compromised, serious threats could be brought out. For example, adversaries could use compromised master nodes to steal information about patients in a human health monitoring sensor network, leading to the privacy breach of patients. It is a challenge for master nodes to process queries in such an environment with privacy, since they have to gain information about the collected data items for query result computing, which is conflictive with the privacy preserving objective.

Data query is an important operation for events monitoring or data analysis in sensors networks. Recently, privacy-preserving range query [3–8] and data aggregation [9–12] have been well addressed, however, research efforts on MAX/MIN query are limited, which is to query the maximum or minimum value in an interested area. In this paper, we focus on the MAX/MIN queries, which are important in many applications. For example, the MAX/MIN query can be applied to monitor the forest fires according to the maximum temperature acquiring.

To the best of our knowledge, only [13] proposed a preliminary solution to privacy-preserving MAX/MIN query in two-tiered WSNs, but it is still with the problem of inefficient energy consumption. This paper proposes an energy-efficient privacy-preserving MAX/MIN query processing (EMQP) for two-tiered WSNs. The basic idea is that sensor nodes first encode their collected data and send them to their nearby master nodes for storage, for the convenience that the master nodes can correctly process MAX/MIN queries over encoded data without knowing their real values. An adversary cannot steal any data items or query results in the master nodes, even when they were compromised. The main contribution of our work is that we introduce 0-1 encoding verification scheme to achieve the secret comparison between the collected data items, without knowing their real values. Based on that method, we propose a novel privacy-preserving MAX/MIN query protocol. To reduce the energy consumption of sensor nodes, we also give a hash-based optimization method, which demonstrates a significant energy-saving benefit. We evaluate EMQP by comprehensive simulation, and the results indicate that EMQP has a good performance compared with other methods.

The rest of this paper is organized as follows. Section 2 gives a brief review of the related work. Section 3 describes the models and the problem statement. In Section 4, we present the details of our energy-efficient privacy-preserving MAX/MIN query protocol. Section 5 gives an optimization for saving energy of sensor nodes. We evaluate the performance of our approach in Section 6 and conclude this paper in Section 7.

2. Related Work

Data storage models for sensor networks have drawn much attention in existing research work. In [14, 15], a novel data storage system is proposed by introducing an intermediate tier between the base station and sensor nodes, which can provide abundant storage for data caching and an efficient access to the data collected by sensor networks for query processing. We consider the same system model in this paper, in which some master nodes are deployed as the intermediate tier for data storage and query answering. In practice, several products of master nodes have been manufactured and are commercially available, such as StarGate [16] and RISE [17].

Recently, verifiable privacy-preserving range query in two-tiered WSNs has been widely studied [3–8], aiming to protect the privacy and integrity of range queries. Hacigümüş et al.firstly proposed a bucket partitioning [18] based scheme [3, 4], whose basic idea is to divide the domain of collected data values into multiple continuous but no overlapping buckets. In each epoch of time, sensor nodes collect data items, put them into corresponding buckets, encrypt them together in each bucket, and then send the ciphertext along with the corresponding bucket ID to a nearby master node. For each bucket without data items, an encoding number will be generated and transmitted to a nearby master node, which can be used by the base station to verify that the bucket is empty. When the base station executes a range query, it first generates the smallest set of bucket IDs covering the range in the query and then sends the ID set as the query to master nodes. Upon receiving the bucket IDs, the master nodes return the corresponding ciphertext in all those buckets. The base station can then decrypt the ciphertext to get the query result and verify its integrity by encoding numbers. Shi et al. proposed an optimized version [5, 6] of integrity verification scheme of [3, 4], with the objective to reduce the communication cost of sensor nodes. Since all the works in [3–6] are based on the bucket partitioning scheme, there is an inherited drawback that the bucket partitioning allows compromised master nodes to obtain a reasonable estimation on the real values of both data items and queried ranges [19]. To solve data estimation problem, Chen and Liu proposed a secure and efficient range query processing protocol, SafeQ [7, 8], which is based on Prefix Membership Verification (PMV) [20, 21] and neighborhood chains. The PMV scheme can be used to check a data item x whether it is in a range $[a, b]$ without knowing the real values of x, a and b, while the neighborhood chains mechanism can be used to detect the falsifies or forges of query results. Using such PMV and neighborhood chains, SafeQ can correctly process range queries in privacy and integrity preserving circumstance.

For privacy-preserving MAX/MIN query in two-tiered WSNs, only [13] has presented a preliminary solution. In [13], the same PMV scheme as in [7, 8] is used to privately compute the maximum or minimum data item. However, it still has a problem of inefficient energy consumption of sensor nodes. This paper will propose an energy-efficient privacy-preserving MAX/MIN query, the evaluation results of which indicate that it has a better performance than [13] in energy consumption of sensor nodes.

3. Models and Problem Statement

3.1. Network Model

We consider a similar two-tiered sensor networks model as in [3–8]. As shown in Figure 1, the network is partitioned into multiple cells, each containing several sensor nodes and a master node. The two types of nodes are different in resource owning. In particular, the master nodes are powerful devices and have abundant resource in energy, storage, and computation, while the sensor nodes are cheap sensing devices with limited resource. Each sensor node periodically transmits its collected data to its nearby master node in the same cell. The base station is in charge of converting users' questions into queries and then disseminating the queries to the corresponding master nodes, which process the queries based on their stored data items and return the query results to the base station via an upper-tier multihop network formed by the resource-rich master nodes and an on-demand wireless (e.g., satellite) link between some master nodes and the base station.

As in [3–8], we assume that master nodes and sensor nodes know their respective locations and affiliated cells. The time is assumed to be divided into epochs. At the end of each epoch, each sensor node submits all its collected data items to the affiliated master node in its cell.

3.2. MAX/MIN Query Model

A MAX/MIN query is an operation to obtain the maximum or minimum value from an interested area. For simplicity, the following atomic MAX/MIN query will be considered, which is denoted as a four-element tuple:

\begin{matrix} Q^{t} = (φ, t, C, Γ^{t}), \end{matrix}

(1)

where

φ \in {MAX, MIN}

indicates the query type, t and C are the queried epoch number and cell ID, and

Γ^{t}

denotes the set of queried sensor nodes IDs which indicate a query region in C. Other complicated MAX/MIN queries that contain multiple epochs, cells, and/or query regions can be easily decomposed into multiple atomic ones. For example, there is a network consisting of 3 cells and 21 sensors as shown in Figure 2. The complicated MAX query “obtaining the maximum value of the rectangle region in epoch t” can be decomposed into 3 atomic MAX queries, such as

Q_{1}^{t} = (MAX, t, C_{1}, {1, 4, 6, 11})

Q_{2}^{t} = (MAX, t, C_{2}, {8, 9, 12})

, and

Q_{3}^{t} = (MAX, t, C_{3}, {16, 20})

. And the query result of the above complicated MAX query is the maximum of the results of

Q_{1}^{t}

Q_{2}^{t}

, and

Q_{3}^{t}

. In this paper, we take atomic MAX/MIN query as an abbreviation, “MAX/MIN query”, for simplicity.

Figure 2

A complicated MAX query example.

Since each master takes charge of a unique cell, the adversary will not gain more from the collaboration of multiple honest-but-curious masters. The subsequent discussion in this paper focuses on a cell C consisting of a master M and n sensor nodes ${s_{1}, s_{2}, \dots, s_{n}}$ whose IDs constitute the set $Γ = {1, 2, \dots, n}$ . Each sensor node probes several data items during each epoch t. We just concentrate on the MAX query processing schemes, while the MIN query is similar and easy to implement.

3.3. Threat Model and Problem Statement

In two-tiered WSNs, the master nodes are too attractive to be easily under attacks from adversaries, since they not only store all the data items collected by sensor nodes, but also take charge of processing queries received from the base station. We assume that the sensor nodes and the base station are trusted but the master nodes. And we adopt the same honest-but-curious threat model as [13], where master nodes may try to breach privacy to obtain sensitive data items but faithfully obey protocols during query processing.

In this paper, we focus on how to provide data privacy preservation and efficient query processing schemes for MAX/MIN queries, while confronting the honest-but-curious master nodes. In addition, we will use the metric of energy consumption of sensor nodes, which directly affects the lift time of the whole networks, to evaluate the performance of our proposed schemes.

4. 0-1 Encoding-Verification-Based MAX/MIN Query Processing

To preserve privacy, it seems natural to have sensor nodes encrypting their collected data items; however, the key challenge is how the master nodes process MAX/MIN queries over encrypted data without knowing their real values.

The basic idea for preserving privacy MAX/MIN query is as follows. We assume that each senor $s_{i}$ in a network and the base station share a secret key $k_{i}$ . For the N data items that $s_{i}$ collects in epoch t, $s_{i}$ first encrypts the maximum or minimum data item $d_{i}$ using key $k_{i}$ , the result of which is denoted as ${(d_{i})}_{k i}$ . For computation efficiency, we use symmetric encryption like DES, IDEA, and so forth. Then, $s_{i}$ applies an encoding function ℜ to $d_{i}$ and obtains $ℜ (d_{i})$ . And $s_{i}$ submits the encrypted and encoded data to its closest master node M. When M performs a MAX/MIN query, a secret comparing function ℑ will be used for query processing over encrypted and encoded data. The functions ℜ and ℑ satisfy the following conditions: (1) given $ℜ (d_{i})$ and ${(d_{i})}_{k i}$ , it is computationally infeasible for the master node to compute $d_{i}$ . (2) Given two data items x and y, $x \leq y$ if and only if $ℑ (x, y)$ is not null. The former condition guarantees data privacy, while the later allows the master node to determine the very encrypted data containing the maximum or minimum without knowing the real values of the collected.

4.1. 0-1 Encoding Verification

0-1 encoding verification was first introduced by Lin and Tzeng in [22] for solving the millionaires' problem [23], which is to find the richest from several millionaires without leaking the sensitive personal information of their properties.

Definition 1.

Let $x = b_{1} b_{2} \dots b_{w - 1} b_{w} \in {0,1}^{w}$ be a binary string of length w. The 0-encoding and 1-encoding are the sets $E^{0} (x)$ and $E^{1} (x)$ of binary strings, such that

\begin{matrix} E^{0} (x) = {b_{1} b_{2} \dots b_{i - 1} 1 ∣ b_{i} = 0 \land 1 \leq i \leq w}, \\ E^{1} (x) = {b_{1} b_{2} \dots b_{i} ∣ b_{i} = 1 \land 1 \leq i \leq w} . \end{matrix}

(2)

According to Definition 1, we can get the properties as follows: (1)

$1 \leq | E^{0} (x) | \leq w$ , $1 \leq | E^{1} (x) | \leq w$ , and $| E^{0} (x) | + | E^{1} (x) | = w$ .

(2)

$E^{0} (x) \cap E^{1} (x) = ⌀$ .

Theorem 2.

For two numbers x and y, if they are encoded into $E^{1} (x)$ and $E^{0} (y)$ , one can see that (1)

$x > y \Leftrightarrow E^{1} (x) \cap E^{0} (y) \neq ⌀$ .

(2)

$x \leq y \Leftrightarrow E^{1} (x) \cap E^{0} (y) = ⌀$ .

The proof of Theorem 2 refers to [22]. In order to verify whether a number x is not greater than the other number y using Theorem 2, we can convert x and y to $E^{1} (x)$ and $E^{0} (y)$ ; thus, $x \leq y$ if and only if $E^{1} (x) \cap E^{0} (y) = ⌀$ , otherwise $x > y$ .

To verify whether $E^{1} (x) \cap E^{0} (y)$ is null or not, the operation of verifying the equalization of two binary strings is needed. For simplicity, we convert each 0-encoding or 1-encoding binary string to a corresponding unique number using a numeralization function 𝒩, which should satisfy the following properties: (1) for any 0-encoding or 1-encoding binary string p, $𝒩 (p)$ is also a binary string; (2) for any two 0-encoding or 1-encoding binary strings p and q, $p = q$ if and only if $𝒩 (p) = 𝒩 (q)$ . There are many ways to construct 𝒩. We use a similar numeralization function as [24]. Given a binary string $b_{1} b_{2} \dots b_{w - 1} b_{w}$ of w bits, we insert 1 before $b_{1}$ . For example, 0101 is converted to 10101. Given a set of 0-encoding or 1-encoding binary strings P, we denote by $𝒩 (P)$ the resulting set of numericalized binary strings. Therefore, $x \leq y$ if and only if $𝒩 (E^{1} (x)) \cap 𝒩 (E^{0} (y)) = ⌀$ , and $x > y$ if and only if $𝒩 (E^{1} (x)) \cap 𝒩 (E^{0} (y)) \neq ⌀$ . Figure 3 shows the process of verifying $9 > 4$ .

Figure 3

0-1 encoding verification.

4.2. Data Submission Protocol

The data submission protocol (DSP) is concerned with how a sensor node transmits its collected data items to the master node M. For each sensor node $s_{i}$ in C, after collecting the N data items ${d_{i}^{1}, d_{i}^{2}, . . ., d_{i}^{N}}$ in epoch t, $s_{i}$ performs the following steps. (1)

Compute the maximum of ${d_{i}^{1}, d_{i}^{2}, . . ., d_{i}^{N}}$ , which is denoted as $d_{i} = \max {d_{i}^{1}, d_{i}^{2}, . . ., d_{i}^{N}}$ .

(2)

Convert $d_{i}$ to $E^{0} (d_{i})$ and $E^{1} (d_{i})$ and compute $𝒩 (E^{0} (d_{i}))$ and $𝒩 (E^{1} (d_{i})$ ) by the numeralization function 𝒩.

(3)

Compute the keyed-hash message authentication code (HMAC) [25] of each data item in $𝒩 (E^{0} (d_{i}))$ and $𝒩 (E^{1} (d_{i}))$ using key g, which is shared by all sensor nodes in C, but M knows nothing about it. An HMAC function using key g, denoted as $HMA C_{g}$ , satisfies the one-wayness and the collision resistance properties. (The one-wayness property of HMAC means that, given $HMA C_{g} (x)$ , it is computationally infeasible to compute x and g, while the collision resistance property means that it is also computationally infeasible to find two different data items x and y such that $HMA C_{g} (x) = HMA C_{g} (y) .)$ Given a set of numbers S, we use $HMA C_{g} (S)$ to represent the resulting set after applying $HMA C_{g}$ to every numbers in S. In summary, this step computes $HMA C_{g} (𝒩 (E^{0} (d_{i})))$ and $HMA C_{g} (N (E^{1} (d_{i})))$ .

(4)

Encrypt $d_{i}$ to ${(d_{i})}_{k i}$ using key $k_{i}$ which is shared with the base station.

(5)

Submit the following message to M:

\begin{array}{l} s_{i} ⟶ M : 〈 i, t, {(d_{i})}_{k i}, HMA C_{g} (𝒩 (E^{0} (d_{i}))), \\ HMA C_{g} (𝒩 (E^{1} (d_{i}))) 〉 . \end{array}

(3)

The above steps indicate that the aforementioned encoding function ℜ is defined as follows:

\begin{array}{l} ℜ (d_{i}) = {HMA C_{g} (𝒩 (E^{0} (d_{i}))), \\ HMA C_{g} (𝒩 (E^{1} (d_{i})))} . \end{array}

(4)

We name

ℜ (d_{i})

as comparison factors (c-factors) of

d_{i}

, which will be used for the secret comparing in the next section.

Since the HMAC function is with one-wayness and collision resistance properties, and sensor nodes only share the secret key with the base station, given $ℜ (d_{i})$ and ${(d_{i})}_{k i}$ , it is computationally infeasible for the master node to obtain the value of $d_{i}$ . Therefore, we can see that the DSP can preserve data privacy from the master node.

4.3. Query Processing Protocol

The query processing protocol (QPP) is concerned with how the master node M executes a query and returns response to the base station. When M receives a query $Q^{t} = (MAX, t, C, Γ^{t})$ from the base station, M processes $Q^{t}$ on its stored data ${{(d_{i})}_{k i}, HMA C_{g} (𝒩 (E^{0} (d_{i}))), HMA C_{g} (𝒩 (E^{1} (d_{i}))) ∣ i \in Γ^{t}}$ , which is received from sensor nodes in epoch t.

Lemma 3.

Given two data items x and y with corresponding 0-1 encoding c-factors, $H M A C_{g} (𝒩 (E^{1} (x)))$ and $H M A C_{g} (𝒩 (E^{0} (y)))$ , one has (1)

$x > y \Leftrightarrow H M A C_{g} (𝒩 (E^{1} (x))) \cap H M A C_{g} (𝒩 (E^{0} (y))) \neq ⌀$ ,

(2)

$x \leq y \Leftrightarrow H M A C_{g} (𝒩 (E^{1} (x))) \cap H M A C_{g} (𝒩 (E^{0} (y))) = ⌀$ .

We omit its proof here since it can be easily derived from the collision resistance property of $HMAC$ and Theorem 2.

Lemma 3 shows that the aforementioned secret comparing function ℑ is defined as follows, where $ℑ (x, y) = ⌀$ means $x \leq y$ otherwise $x > y$ ,

\begin{array}{l} ℑ (x, y) = H M A C_{g} (𝒩 (E^{1} (x))) \\ \cap H M A C_{g} (𝒩 (E^{0} (y))) . \end{array}

(5)

Theorem 4.

Given n data items $D = {d_{1}, d_{2}, \dots, d_{n}}$ , $d_{i} \in D$ is the maximum of D if and only if the following condition satisfied:

\begin{array}{l} \forall d_{j} \in D \land d_{j} \neq d_{i} (H M A C_{g} (𝒩 (E^{1} (d_{j}))) \\ \cap H M A C_{g} (𝒩 (E^{0} (d_{i}))) = ⌀) . \end{array}

(6)

Proof.

Suppose that the above condition is satisfied, for each $d_{j} \in D$ and $d_{j} \neq d_{i}$ , we have $HMA C_{g} (𝒩 (E^{1} (d_{j}))) \cap HMA C_{g} (𝒩 (E^{0} (d_{i}))) = ⌀$ , and then $d_{j} \leq d_{i}$ can be derived due to Lemma 3. Therefore, we can see that $d_{i}$ is not smaller than any other data items in D, which means that $d_{i}$ is the maximum of D.

On the basis of Theorem 4, the master node M performs the following steps to implement query processing.

(1)

Load ${HMA C_{g} (𝒩 (E^{0} (d_{i}))), HMA C_{g} (𝒩 (E^{1} (d_{i}))) ∣ i \in Γ^{t}}$ received from the queried sensor nodes whose IDs belong to $Γ^{t}$ in epoch t.

(2)

Find the encrypted data ${(d_{i})}_{k i}$ whose corresponding c-factors satisfying the condition of Theorem 4 and transmit the following response message to the base station:

\begin{matrix} M ⟶ base station : 〈 i, {(d_{i})}_{k i} 〉 . \end{matrix}

(7)

Upon receiving the above message, the base station loads the secret key $k_{i}$ shared with $s_{i}$ and then decrypts ${(d_{i})}_{k i}$ to obtain the query result $d_{i}$ , which is the maximum of the data item collected by the queried sensor nodes in epoch t.

4.4. Privacy Protection Analysis

As the privacy protection is the focus in this paper, we propose the privacy analysis about EMQP on the following two aspects.

(1) Privacy of Collected Data. According to the data submission protocol, the submitted information from each sensor node to the affiliated master node is not plaintext but encrypted and HMAC data. Since the HMAC function is with one-wayness and collision resistance properties, and sensor nodes only share the secret key with the base station, given $ℜ (d_{i})$ and ${(d_{i})}_{k i}$ , it is computationally infeasible for master nodes to obtain the value of $d_{i}$ . Thus, the difficulty for master node to breach privacy is equal with cracking encryption and HMAC. Therefore, we have that EMQP can protect collected data items from master nodes.

(2) Privacy of Query Result. The query processing protocol shows that the master node can use the secret comparing function to obtain the query result, which is the maximum or minimum of data items collected by the queried sensor nodes. Because the secret comparing is built upon the HMAC data items and the collected data items are all encrypted for master node storage, it is also computationally infeasible for master nodes to obtain the value of the query result without keys. As a consequence, we have that EMQP is capable of preserving query result from master nodes.

Since [13] also uses similar HMAC and encryption to protect privacy, the capability of privacy preservation is the same between our work and [13].

4.5. Energy Consumption Analysis

In two-tiered WSNs, sensor nodes have limited energy resource while master nodes are abundant in energy. Therefore, the life time of network is mainly determined by the energy consumption of sensor nodes. In this section, we discuss the energy consumption of sensor nodes in our proposed schemes.

We assume that (1) a cell C have of n sensor nodes; (2) each epoch number and node ID are of $l_{t}$ and $l_{i d}$ bits; (3) the average hops between a sensor node and M is L; (4) each collected data item is of w bits; (5) each encrypted and HMAC data item is of $l_{c}$ and τ bits; (6) the energy consumed by encrypting and HMAC computing a data item are $e_{c}$ and $e_{h}$ ; (7) the energy consumed by transmitting and receiving a data item are $e_{t}$ and $e_{r}$ .

The total energy consumption of sensor nodes is composed of two aspects, one is communication cost including sending and receiving messages and the other is computation cost such as encryption and HMAC computing. We use $E_{total}$ , $E_{s r}$ , and $E_{c}$ to represent the total, communication, and computation energy consumption of the sensor nodes, then we have

\begin{matrix} E_{total} = E_{s r} + E_{c} . \end{matrix}

(8)

As shown in DSP, each sensor node will encrypt the maximum or minimum of its collected data in an epoch and generate its 0-encoding and 1-encoding c-factors having w HMAC data items in total. The encrypted data and c-factors will both be transmitted to M. Then, we have

\begin{matrix} E_{s r} = n \cdot (l_{i d} + l_{t} + w \cdot τ + l_{c}) \cdot (L \cdot e_{t} + (L - 1) \cdot e_{r}), \\ E_{c} = n \cdot e_{c} + n \cdot w \cdot e_{h} . \end{matrix}

(9)

According to (8), (9), we have

\begin{array}{l} E_{total} = n \cdot (l_{i d} + l_{t} + w \cdot τ + l_{c}) \cdot (L \cdot e_{t} + (L - 1) \cdot e_{r}) \\ + n \cdot e_{c} + n \cdot w \cdot e_{h} . \end{array}

(10)

In [13], for each senor node $s_{i}$ and the local maximum or minimum data item $d_{i}$ collected by $s_{i}$ in epoch t, $s_{i}$ will first generate the HMAC computed and numericalized prefix families of $d_{i}$ and $[d_{i}, d_{top}]$ , which are denoted as F and S. Here, the $d_{top}$ is a very large number that is greater than any collected data items. Then $s_{i}$ encrypts $d_{i}$ , and the encrypted data will be transmitted to its closest master node along with the HMAC data sets F and S. According to [13], if $d_{i}$ is of w bits, then F has $w + 1$ HMAC data items and S has j HMAC data items, where $1 \leq j \leq 2 w - 2$ . So the lower bound of transmitted HMAC data items is $w + 2$ , while the upper bound is $3 w - 1$ . Since each sensor node computes and transmits the same encrypted data but more HMAC data items, [13] will consume more energy in sensor nodes comparing with our scheme. We will evaluate their energy consumptions in Section 6.

5. Energy Optimization

The above query scheme will consume much energy in sensor nodes because each sensor node needs to submit c-factors which consist of multiple HMAC data, and each HMAC data may have several bits such as 128 bits with HMAC-MD5 [26] or 160 bits with HMAC-SHA1 [27]. In this section, we focus on the c-factor compressing method with the basic idea to compress the HMAC data of c-factors, which can significantly reduce the communication cost in sensor nodes. As a result, the energy consumption of sensor nodes will be decreased and the lifetime will be promoted.

Assume that each HMAC data have τ bits and are randomly distributed in $I_{H} = {0, 1, \dots, 2^{τ} - 1}$ . We use a simple hash function ℋ to compress the HMAC data, which is defined as follows, where $x \in I_{H}$ and $μ < τ$ ,

\begin{matrix} ℋ (x) = x \mod (2^{μ} - 1) . \end{matrix}

(11)

After applying ℋ, each HMAC data of a c-factor can be converted to a fewer-bits number, which is called cHMAC data and is randomly distributed in $I_{C} = {0, 1, \dots, 2^{μ} - 1}$ because of the random distribution of HMAC data in $I_{H}$ , such that the c-factor is compressed. Given a set of HMAC data X, we use $ℋ (X) = {ℋ (x_{i}) ∣ x_{i} \in X}$ to represent the resulting set of cHMAC data after applying ℋ to every items in X.

If the HMAC data is replaced with the corresponding cHMAC data in (5), we can get a similar secret comparing function $ℑ^{'}$ as follows, where x and y are two collected data items:

\begin{array}{l} ℑ^{'} (x, y) = ℋ ({HMAC}_{g} (𝒩 (E^{1} (x)))) \\ \cap ℋ ({HMAC}_{g} (𝒩 (E^{0} (y)))) . \end{array}

(12)

Lemma 5.

For two data items x and y, one has (1)

If $ℑ^{'} (x, y) = ⌀$ , then $x \leq y$ must be true.

(2)

If $ℑ^{'} (x, y) \neq ⌀$ , then $x > y$ may be true but with a certain false positive.

Proof.

For any $x_{1}$ , $x_{2} \in I_{H}$ , if $x_{1} = x_{2}$ , there must be $ℋ (x_{1}) = ℋ (x_{2})$ , but if $x_{1} \neq x_{2}$ , there still may be $ℋ (x_{1}) = ℋ (x_{2})$ when $x_{1}$ and $x_{2}$ modules $2^{μ} - 1$ are equal, which is named collision. The above facts imply that, for any two HMAC data sets X and Y, if $X \cap Y \neq ⌀$ then $ℋ (X) \cap ℋ (Y) \neq ⌀$ , otherwise we may still have $ℋ (X) \cap ℋ (Y) \neq ⌀$ . Therefore, if $ℋ (X) \cap ℋ (Y) \neq ⌀$ , we may have $X \cap Y \neq ⌀$ hold, otherwise $X \cap Y = ⌀$ must be true. Assuming that Xand Yare the c-factors of x and y where $X = {HMAC}_{g} (𝒩 (E^{1} (x)))$ and $Y = {HMAC}_{g} (𝒩 (E^{0} (y)))$ , if $ℑ^{'} (x, y) = ℋ (X) \cap ℋ (Y) = ⌀$ , then we have $X \cap Y = ⌀$ which implies $x \leq y$ according to Lemma 3. But if $ℑ^{'} (x, y) = ℋ (X) \cap ℋ (Y) \neq ⌀$ , then we may have $X \cap Y \neq ⌀$ which implies $x > y$ may be true.

As shown in Lemma 5 and its proof, there could have false positive in secret comparing while using the compressed c-factors, which is represented as the probability of a false decision in data comparison. And only if $X \cap Y = ⌀$ but $ℋ (X) \cap ℋ (Y) \neq ⌀$ holds, the false decision is to be emerged. We denote the maximum false positive rate as Pr. In practical, if Pr is low enough, the c-factor compressing method is still acceptable. In the subsequent of this section, we will give the analysis of Pr in comparing two data items by Lemma 5.

We assume that each collected data item is of w bits, X and Y are the c-factors of data items x and y where $X = HMA C_{g} (𝒩 (E^{1} (x)))$ and $Y = HMA C_{g} (𝒩 (E^{0} (y)))$ , and $X \cap Y = ⌀$ . Apparently, the more HMAC data that X and Y have, the higher probability that $ℋ (X) \cap ℋ (Y) \neq ⌀$ emerges. Therefore, we assume that X and Y both have w HMAC data items, which is the upper bound of the quantity of HMAC data that each c-factor has, $X = {x_{1}, x_{2}, \dots, x_{w}}$ and $Y = {y_{1}, y_{2}, \dots, y_{w}}$ . For each cHMAC data $x \in I_{c}$ , there are at least $⌊ 2^{τ} / (2^{μ} - 1) ⌋$ HMAC data items in $I_{H}$ whose results equal x when module $2^{μ} - 1$ , such as x, $x + (2^{μ} + 1)$ , $x + 2^{*} (2^{μ} + 1)$ . Supposing $ℋ (X)$ has δ cHMAC data items where $0 < δ \leq w$ , there will be a set C having $⌊ 2^{τ} / (2^{μ} - 1) ⌋ \cdot δ$ HMAC data items, which satisfies $ℋ (c_{i}) \in ℋ (X)$ for each $c_{i} \in C$ . Therefore, for each $y_{i} \in Y$ , the probability of $ℋ (y_{i}) \notin ℋ (X)$ is equal with $y_{i} \notin C$ , which is $1 - ⌊ 2^{τ} / (2^{μ} - 1) ⌋ \cdot δ / 2^{τ}$ , and only if $ℋ (y_{i}) \notin ℋ (X)$ then $ℋ (X) \cap ℋ (Y) = ⌀$ , otherwise we have $ℋ (X) \cap ℋ (Y) \neq ⌀$ with the probability $1 - {(1 - ⌊ 2^{τ} / (2^{μ} - 1) ⌋ \cdot δ / 2^{τ})}^{w}$ . It is apparent that the probability will reach the maximum when $δ = w$ . As a result, we have

\begin{matrix} Pr = 1 - {(1 - \frac{⌊ 2^{τ} / (2^{μ} - 1) ⌋ \cdot w}{2^{τ}})}^{w} . \end{matrix}

(13)

If the 128-bit HMAC-MD5 is used $(τ = 128)$ , we have the results of the impact of w and μ on Pr as shown in Figure 4, which indicate that Pr could be very low if an appropriate μ is chosen. For instance, assuming that $w = 16$ and $μ = 24$ , then we have $Pr = 1.53 * 10^{- 5}$ . Obviously, such low false positive rate rarely affects the result of secret comparing.

Figure 4

Impacts of w and μ on Pr.

6. Performance Evaluation

To evaluate the performance of our proposed EMQP and the current work [13], which is denoted as PMQP, we implement both schemes and perform energy consumption comparison on the simulator of [28] with the same data set as [13] which is from Intel Lab [29]. We use PMQP(bot) and PMQP(top) to represent the lower and upper bounds of energy consumption of PMQP, and EMQP(bas) and EMQP(opt) to represent energy consumption of EMQP before and after hash-based optimization. We carry out evaluations on a MAX query in a cell with n sensor nodes and a master node, and we consider the following two aspects: firstly, the total energy consumption $E_{total}$ of sensor nodes in EMQP and PMQP will be given, while the communication and computation energy cost $E_{s r}$ and $E_{c}$ in EMQP(opt) will be secondly measured as EMQP(opt) is the most energy-saving scheme.

The evaluations are conducted on a PC with a P4 3.0 GHz CPU and 512 MB memory running Ubuntu operating system. The placement of sensors nodes of a cell follows a uniform distribution over a two-dimensional region covering a $100 \times 100$ m² area, and the radius of sensor communication is assumed as 10 m. According to [30], the energy consumed by transmitting and receiving 1-bit data in wireless communication are computed as follows: $e_{t} = α + γ \times d^{n}$ and $e_{r} = β$ , where d is the distance to which a bit is being transmitted, m is the path loss index, α and β capture the energy dissipated by the communication electronics, and γ represents the energy radiated by the power-amp. In our simulation, the values for these parameters as in [30] are adopted as follows: $γ = 10$ pJ/bit/m², $α = 45$ nJ/bit, $β = 135$ nJ/bit, and $m = 2$ . In addition, we assume that the energy of encrypting a data item is adopted as $e_{c} = 8.92$ μJ which is from [31], where using RC4 for encryption in TelosB, and the energy of HMAC computing a data item is assumed to be equal with encryption for simplicity. Other default parameters are summarized in Table 1.

Table 1

Default evaluation parameters.

Para.	n	w	$l_{id}$	$l_{t}$	$l_{c}$	τ	μ
Val.	480	10 bits	32 bits	32 bits	128 bits	128 bits	24 bits

In each measurement, we randomly distribute the sensor nodes and generate 20 networks with different topologies which are represented by different network IDs. The total energy including communication and computation costs of each measurement is the average of 20 networks.

(1) Energy Consumption versus Network ID. Figure 5(a) shows that $E_{total}$ of EMQP and PMQP are both uniformly distributed in different networks, but $E_{total}$ of EMQP is obviously lower than PMQP. In detail, compared with the lower bound of PMQP, the EMQP before optimization saves about 15% energy in average, and about 75% is saved after optimization. The main reason is that PMQP needs to submit and compute more HMAC data than EMQP, and the optimization of EMQP converts every HMAC data to a lower-bits cHMAC data, which significantly reduces the communication cost.

Figure 5

Impact of network ID on energy consumption.

Figure 5(b) indicates that $E_{s r}$ and $E_{c}$ in the optimized EMQP are also both uniformly distributed, but $E_{s r}$ is much higher than $E_{c}$ . The energy consumption is almost entirely covered by communication that consumes more than 99% energy in total consumption.

(2) Energy Consumption versus n and w. Figures 6(a) and 7(a) both show that $E_{total}$ of EMQP and PMQP are both increased as n and w increasing, but $E_{total}$ of EMQP is always lower than PMQP. In detail, the EMQP before and after optimization save about 12% and 76% energy in average. The reason is similar with (1) in this section. Although $E_{s r}$ and $E_{c}$ in the optimized EMQP are both increased as n and w increasing, such increments are both very inconspicuous as shown in Figures 6(b) and 7(b), since the computation only covers little part (no more than 1%) in total energy consumption.

Figure 6

Impact of n on energy consumption.

Figure 7

Impact of w on energy consumption.

According to the above evaluations, we can conclude that our proposed EMQP are more energy efficient than the current PMQP. Particularly, the optimized EMQP has a significant saving (about 75%) in energy consumption even compared with the lower bound of PMQP. And communication costs much more energy than computation (more than 99%).

7. Conclusion

As the wireless sensor networks are deployed and used in many important areas, preserving the privacy of sensitive collected data items during query processing is a critical problem in sensor network applications. In this paper, we propose EMQP, a novel and energy-efficient protocol for handling privacy-preserving MAX/MIN queries in two-tiered sensor networks. To implement privacy-preserving MAX/MIN query processing without exposing the real value of collected data to master nodes, the technique of 0-1 encoding verification and encryption are applied. Furthermore, we also give a hash-based optimization for saving more energy of the resource-limited sensor nodes. The result of our evaluations shows that the proposed EMQP has a better performance than the current work in energy consumption. Under our optimized circumstance, in comparison with the lower bound of the current work, the EMQP has a significant improvement in energy saving. Last but not least, communication costs much more than computation in all consumptions.

Footnotes

Acknowledgments

This research is supported by the National Key Basic Research Program (973 Program) of China under the Grant no. 2011CB302903, the National Natural Science Foundation of China under the Grants nos. 61272084, 61202004, 61201163, and 61202353, the Specialized Research Fund for the Doctoral Program of Higher Education under the Grant nos. 20113223110003 and 20093223120001, the Key Project of Natural Science Research of Jiangsu University under the Grant no. 11KJA520002, and the Natural Science Foundation of Jiangsu Province under the Grants nos. BK2011754 and BK2011072, the Introduction of Talent Research Foundation of Nanjing University of Posts and Telecommunications under the Grant no. NY211043, and the Priority Academic Program Development Foundation of Jiangsu Higher Education Institutions (Information and Communication yx002001).

References

Gnawali

Jang

K.-Y.

Paek

Vieira

Govindan

Greenstein

Joki

Estrin

Kohler

The tenet architecture for tiered sensor networks

Proceedings of the 4th ACM International Conference on Embedded Networked Sensor Systems (SenSys '06)

November 2006

New York, NY, USA

ACM

153 166

2-s2.0-34547484870

10.1145/1182807.1182823

Desnoyers

Ganesan

Shenoy

TSAR: a two tier sensor storage architecture using inteval skip graphs

Proceedings of the 3rd ACM Conference on Embedded Networked Sensor Systems (SenSys '05)

2005

San Diego, Calif, USA

39 50

Sheng

Verifiable privacy-preserving range query in two-tiered sensor networks

Proceedings of the 27th IEEE International Conference on Computer Communications

2008

Piscataway, NJ, USA

IEEE

46 50

Sheng

Verifiable privacy-preserving sensor network storage for range query

IEEE Transactions on Mobile Computing 2011 10 9 1312 1326

2-s2.0-79960757672

10.1109/TMC.2010.236

Shi

Zhang

Secure range queries in tiered sensor networks

Proceedings of the IEEE 28th Conference on Computer Communications (INFOCOM '09)

April 2009

Piscataway, NJ, USA

IEEE

945 953

2-s2.0-70349690087

10.1109/INFCOM.2009.5062005

Shi

Zhang

A spatiotemporal approach for secure range queries in tiered sensor networks

IEEE Transactions on Wireless Communications 2011 10 1 264 273

2-s2.0-78651506283

10.1109/TWC.2010.102210.100548

Chen

Liu

A. X.

SafeQ: secure and efficient query processing in sensor networks

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '10)

March 2010

Piscataway, NJ, USA

IEEE

2-s2.0-77953310348

10.1109/INFCOM.2010.5462094

Chen

Liu

A. X.

Privacy and integrity preserving range queries in sensor networks

IEEE/ACM Transactions on Networking 2012 20 6 1774 1787

2-s2.0-84857953077

10.1109/TNET.2012.2188540

Yoon

Kim

Y. K.

Chang

J. W.

A new data aggregation scheme to support energy efficiency and privacy preservation for wireless sensor networks

International Journal of Security and its Applications 2013 7 1 129 142

10.

Chen

Yang

Chen

An algorithm for data aggregation scheduling with long-lifetime and low-latency in wireless sensor networks

International Journal of Future Generation Communication and Networking 2012 5 4 141 152

11.

Yang

Precision-enhanced and encryption-mixed privacy-preserving data aggregation in wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 12

427275

10.1155/2013/427275

12.

Chen

C.-M.

Lin

Y.-H.

Lin

Y.-C.

Sun

H.-M.

RCDA: recoverable concealed data aggregation for data integrity in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2012 23 4 727 734

2-s2.0-84858081248

10.1109/TPDS.2011.219

13.

Yao

Xiong

Park

J. H.

Liu

Privacy-preserving max/min query in two-tiered wireless sensor networks

Computers and Mathematics with Applications 2012 65 9 1318 1325

2-s2.0-84857344399

10.1016/j.camwa.2012.02.003

14.

Ratnasamy

Karp

Shenker

Estrin

Govindan

Yin

Data-centric storage in sensornets with GHT, a geographic Hash Table

Mobile Networks and Applications 2003 8 4 427 442

2-s2.0-0042564491

10.1023/A:1024591915518

15.

Desnoyers

Ganesan

PRESTO: a predictive storage architecture for sensor networks

Proceedings of the 10th Workshop on Hot Topics in Operating Systems

2005

Santa Fe, NM, USA

1 6

16.

Stargate Gateway(sp400), http://www.xbow.com/

17.

Rise Project, http://www.cs.ucr.edu/~rise/

18.

Hacigümüş

Iyer

Mehrotra

Executing SQL over encrypted data in the database-service-provider model

Proceedings of the ACM SIGMOD International Conference on Managment of Data

June 2002

New York, NY, USA

216 227

2-s2.0-0036361105

19.

Hore

Mehrotra

Tsudik

A privacy-preserving index for range queries

Proceeding of 30th Very Large Data Bases Conference (VLDB '04)

2004

720 731

20.

Cheng

Yang

Wong

S. H. Y.

Zerfos

Design and implementation of cross-domain cooperative firewall

Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP '07)

October 2007

Piscataway, NJ, USA

IEEE

284 293

2-s2.0-48349089344

10.1109/ICNP.2007.4375859

21.

Liu

A. X.

Chen

Collaborative enforcement of firewall policies in virtual private networks

Proceedings of the 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

August 2008

New York, NY, USA

ACM

95 104

2-s2.0-57549111039

22.

Lin

H. Y.

Tzeng

W. G.

An efficient solution to the millionaires' problem based on homomorphic encryption

Proceedings of the 3rd International Conference on Applied Cryptography and Network Security

2005

New York, NY, USA

97 134

23.

Yao

A. C.

Protocols for secure computations

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science

1982

Chicago, Ill, USA

160 164

24.

Chang

Y.-K.

Fast binary and multiway prefix searches for packet forwarding

Computer Networks 2007 51 3 588 605

2-s2.0-33751232321

10.1016/j.comnet.2006.05.005

25.

Krawczyk

Canetti

Bellare

HMAC: keyed-hashing for message authentication

1997 RFC 2104

Reston, Va, USA

Internet Society

26.

Rivest

The MD5 message-digest algorithm

1992 RFC 1321

Reston, Va, USA

Internet Society

27.

Eastlake

Jones

US secure hash algorithm 1 (SHA1)

2001 RFC 3174

Reston, Va, USA

Internet Society

28.

Coman

Sander

Nascimento

M. A.

Adaptive processing of historical spatial range queries in peer-to-peer sensor networks

Distributed and Parallel Databases 2007 22 2-3 133 163

2-s2.0-36249023789

10.1007/s10619-007-7018-8

29.

Samuel M. Intel lab data, http://db.csail.mit.edu/labdata/labdata.html

30.

Rappaport

Wireless Communications: Principles and Practice 1996

Upper Saddle River, NJ, USA

Prentice-Hall

31.

Groat

M. M.

Hey

Forrest

KIPDA: K-indistinguishable privacy-preserving data aggregation in wireless sensor networks

Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM '11)

April 2011

Piscataway, NJ, USA

IEEE

2024 2032

2-s2.0-79960854358

10.1109/INFCOM.2011.5935010