# An Efficient Top-k Query Processing with Result Integrity Verification in Two-Tiered Wireless Sensor Networks

Authors: Ruiliang He; Hua Dai; Geng Yang; Taochun Wang; Jingjing Bao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In two-tiered wireless sensor networks, storage nodes take charge of both storing the sensing data items and processing the query request issued by the base station. Due to their important role, storage nodes are more attractive to adversaries in a hostile environment. Once a storage node is compromised, attackers may falsify or abandon the data when answering the query issued by the base station, which will make the base station get incorrect or incomplete result. This paper proposes an efficient top-k query processing scheme with result integrity verification named as ETQ-RIV in two-tiered sensor networks. According to the basic idea that sensor nodes submit some encoded message containing the sequence relationship as proof information for verification along with their collected sensing data items, a data binding and collecting protocol and a verifiable query response protocol are proposed and described in detail. Detailed quantitative analysis and evaluation experiments show that ETQ-RIV performs better than the existing work in both communication cost and query result redundancy rate.


---

## Body

## 1. Introduction

Since the traditional multihop architecture is not suitable for large-scale wireless sensor networks (WSNs), a novel two-tiered architecture has been proposed. The two-tiered wireless sensor networks (TWSNs) introduce storage nodes that are abundant in energy, memory, and computing power to traditional multihop WSNs. In such a two-tiered architecture, the storage node serves as an intermediate tier between the base station and the sensor nodes, which is shown in Figure1. The whole network is partitioned into several cells, each of which consists of a storage node and some sensor nodes nearby. The sensing data are sent to and stored in the storage node in the same cell after being collected by the sensor nodes. After receiving the queries issued by the base station, the storage node processes the query over the data items that are received from the sensor nodes and then returns the query result to the base station. The two-tiered architecture is also known to be indispensable for increasing network capacity and scalability, reducing system complexity, and prolonging network lifetime [1–3].Figure 1
Network model of TWSN.In TWSNs, storage nodes not only store all the sensing data of all the sensor nodes in the same cell, but also respond to the query requests issued by the base station, which makes the storage nodes more attractive to adversaries. Once a storage node is compromised, attackers may falsify or abandon the data when the storage node is answering the query issued by the base station, which will make the base station get incorrect or incomplete result. In an application that depends on the query result, an incomplete result may lead to wrong decisions. Therefore, it is of great significance to construct a verifiable query processing scheme, by which authenticity and integrity of query results can be verified by the base station.Top-k query is frequently used in WSNs aiming at getting the k highest or lowest data in a specified region during a specified time epoch. For instance, “to get the 5 highest temperature data of the second warehouse from 12:00 to 13:00” is a typical top-k query that could be used as fire detection. This paper proposes an efficient top-k query processing scheme with result integrity verification in TWSNs, named asETQ-RIV, the basic idea of which is as follows. The sensor nodes submit some encoded message containing the sequence relationship along with their collected sensing data items to the storage nodes. When the base station issues queries, storage nodes send all the satisfied data items along with the encoded message as proof information to the base station. Then the base station can compute the result and verify the authenticity and integrity of it.ETQ-RIV is an improvement scheme of EVTQ proposed in our previous work [4]. The improvements are as follows.(i)
In the data collecting process, each sensor node does not need to submit the out-bound HMAC, which further reduces the in-cell communication.(ii)
With processing query, the storage node needs to send one HMAC for each unqualified sensor node in EVTQ. However, in ETQ-RIV, only one HMAC for all noncontributed sensor nodes is required, which will greatly reduce the query communication cost.The main contributions of this paper are as follows.(i)
We propose a sequence relationship encoding based method, which makes storage nodes unable to falsify or omit data items without being noticed.(ii)
We give the two concrete protocols, named asdata binding and collecting protocol andverifiable query response protocol, to achieveETQ-RIV, which make the base station capable of verifying the authenticity and integrity of the top-k query result.(iii)
We present the quantitative analysis of communication cost and redundancy rate ofETQ-RIV in detail and conduct experiments to evaluate the performance of this work compared to present methods.The rest of this paper is organized as follows. The related works are presented in Section2. Section 3 presents the preliminaries including related models, problem description, and performance evaluation index. Section 4 presents the two protocols proposed in this paper. Section 5 presents the theoretical analysis of the communication cost and redundancy rate. Section 6 presents the result and analysis of the simulation experiments. In last section, we make a conclusion for this paper.


## 2. Related Works

The traditional multihop model is not suitable for large scale wireless sensor networks; thus a novel two-tiered architecture was proposed, which is indispensable for increasing network capacity and scalability, reducing system complexity, and prolonging network lifetime [1–3].In TWSNs, the storage nodes play an important role and are more attractive to adversaries, which may bring serious data security problems. Therefore, data privacy and security have been widely discussed in recent research work.Attentions have been paid to secure top-k query processing in two-tiered sensor networks recently. A novel verifiable fine-grained top-k query processing scheme was proposed by Zhang et al. [5], which is the first work of verifiable top-k query scheme in two-tiered sensor networks. The basic idea of Zhang’s scheme is that each sensor node generateshashed message authentication code (HMAC) [6] for every three consecutive data items to make query results verifiable. However, the long bits of HMACs result in high cost of communications. Liao and Li proposed a secure top-k query scheme named PriSecTopk [7] based on order preserving encryption [8] and message authentication code (MAC) [9], which could not lower the communication cost either. Ma et al. proposed a novel fine-grained verification scheme for top-k queries named VSFTQ [10] which uses symmetric encryption instead of message authentication. VSFTQ reduces the communication cost to a certain extent. On the basis of Zhang’s scheme and Ma’s scheme, Dai et al. proposed an efficient verifiable top-k query processing scheme in our previous work [4], which has a better performance in communication cost. Yu et al. proposed a dummy reading-based anonymization framework [11, 12], under which the query results can be guaranteed by verifiable top-k query (VQ) schemes they proposed. However, the VQ scheme requires each sensor node to send the neighboring sensor node IDs and hashes corresponding to individual genuine encrypted readings, which may lead to high communication cost of sensor nodes. Moreover, to obtain the top-k query result, the storage node is required to submit a top-(η-1+k) query result due to the dummy readings, where η is a system parameter denoting the difference between the maximum and minimum encrypted readings within an epoch.There is a special kind of top-k query when k equals one, which is also known as max/min query. For max/min query processing, Yao et al. proposed a preliminary privacy-preserving scheme [13] based on prefix membership verification (PMV) mechanism [14, 15] to compute the maximum or minimum value over encrypted data items. Dai et al. proposed an energy-efficient privacy-preserving MAX/MIN query processing solution [16] based on 0-1 encoding technique [17] which has a better performance compared to [13].Besides top-k query, secure range query has been widely discussed recently [18–23]. The schemes proposed in [18–23] ask for data items falling into specified ranges without data privacy disclosure and make query result verifiable.


## 3. Models and Problem Statement

### 3.1. Models

In this paper we consider the two-tiered network model as shown in Figure1. The whole network is partitioned intocells, each of which consists of a storage node M and n homogeneous sensor nodes {s1,s2,…,sn}. M is abundant in resources such as energy, storage, and computation, which is in charge of not only storing of all sensing data collected by the sensor nodes in the same cell but processing and answering of the query request issued by the base station. Limited in resource, the sensor nodes just collect sensing data and transmit them to the storage node in the cell. As in [4], we take the assumption that storage nodes know the topological information of the whole cell, while a sensor node knows the locations of its neighboring nodes in one hop as well as the storage node’s location of affiliated cells. In addition, the base station knows the topological information of the whole network.In TWSN, a top-k query can be denoted as a three-element tuple Q=(c,t,k), where c represents the query region, t represents the time epoch of the query, and k is the quantity of required data items. For simplicity of description, we discuss the specific top-k query that covers only one cell in one time epoch. It is easy to extend the proposed method to achieve queries including multiple cells over multiple time epochs.


### 3.2. Problem Statement

The threat model considered in this paper is similar to [4]. We assume that an arbitrary number of storage nodes could be compromised and instructed to respond with falsified and/or incomplete data as a top-k query result to the base station. In TWSN, both sensor nodes and storage nodes could be compromised. In general, a sensor node only has very little information and the vast majority in the whole network are uncompromised ones. However, the storage node plays a more important role in the network, for it stores all data items collected in the whole cell. Once a storage node is compromised, the adversary may falsify or abandon the data when the storage node answering the query issued by the base station, which will make the base station get incorrect or incomplete result and mislead the user into making wrong decisions. Therefore, storage nodes tend to be more attractive and vulnerable to adversaries. Although a compromised storage node may lead to leakage of data privacy, it is not concerned in this paper. In practice, in some application of WSNs, it is the data integrity instead of data privacy that is more important. For instance, video surveillance in a sensor network for building security is known to adversaries thus requiring no privacy. Therefore, we focus on the verifiable top-k query in this paper.Given a top-k query Q=(c,t,k), we assume the storage node M returns a data set R as query result. The problem of interest is how the base station can verify whether R satisfies both theauthenticity andintegrity requirements, which means the following two rules must hold.(1)
Authenticity Rule. All data items in R are surely collected by sensor nodes in the query cell c during time epoch t.(2)
Integrity Rule. There are exactly k data items that are indeed the k highest data items among what are collected by sensor nodes in the query cell c during time epoch t, or equivalently(1)∀ri∈Rt∧∀dj∈Dt∖Rt⟶ri>dj,where Dt represents the data set consisting of all data items collected by sensor nodes in the query cell c during time epoch t.


### 3.3. Evaluation Metrics

In this paper, the following two metrics are used to evaluate the performance of the proposed scheme.(1)
Communication cost: including in-cell communication costCI and query processing communication cost CQ. CI represents the size in bits of data items transmitted from all the sensor nodes to the storage in a cell in the data binding and collecting procedure, while CQ stands for the size of data items transmitted from the storage node in the query cell to the base station during the verifiable query response procedure.(2)
Redundancy rate of query result: the proportion of the total size in bits of additional proof information used to enable verifiable top-k queries to the total size in bits of response message in final query result. This rate, denoted as γ, indicates the efficiency of the query processing. A lower redundancy rate means less additional communication cost required for verification. The redundancy rate will be calculated by the following equation:(2)γ=ls-lrls×100%,where ls is the size in bits of the total data items returned by the storage node, while lr is the total data size of final query result.


## 3.1. Models

In this paper we consider the two-tiered network model as shown in Figure1. The whole network is partitioned intocells, each of which consists of a storage node M and n homogeneous sensor nodes {s1,s2,…,sn}. M is abundant in resources such as energy, storage, and computation, which is in charge of not only storing of all sensing data collected by the sensor nodes in the same cell but processing and answering of the query request issued by the base station. Limited in resource, the sensor nodes just collect sensing data and transmit them to the storage node in the cell. As in [4], we take the assumption that storage nodes know the topological information of the whole cell, while a sensor node knows the locations of its neighboring nodes in one hop as well as the storage node’s location of affiliated cells. In addition, the base station knows the topological information of the whole network.In TWSN, a top-k query can be denoted as a three-element tuple Q=(c,t,k), where c represents the query region, t represents the time epoch of the query, and k is the quantity of required data items. For simplicity of description, we discuss the specific top-k query that covers only one cell in one time epoch. It is easy to extend the proposed method to achieve queries including multiple cells over multiple time epochs.


## 3.2. Problem Statement

The threat model considered in this paper is similar to [4]. We assume that an arbitrary number of storage nodes could be compromised and instructed to respond with falsified and/or incomplete data as a top-k query result to the base station. In TWSN, both sensor nodes and storage nodes could be compromised. In general, a sensor node only has very little information and the vast majority in the whole network are uncompromised ones. However, the storage node plays a more important role in the network, for it stores all data items collected in the whole cell. Once a storage node is compromised, the adversary may falsify or abandon the data when the storage node answering the query issued by the base station, which will make the base station get incorrect or incomplete result and mislead the user into making wrong decisions. Therefore, storage nodes tend to be more attractive and vulnerable to adversaries. Although a compromised storage node may lead to leakage of data privacy, it is not concerned in this paper. In practice, in some application of WSNs, it is the data integrity instead of data privacy that is more important. For instance, video surveillance in a sensor network for building security is known to adversaries thus requiring no privacy. Therefore, we focus on the verifiable top-k query in this paper.Given a top-k query Q=(c,t,k), we assume the storage node M returns a data set R as query result. The problem of interest is how the base station can verify whether R satisfies both theauthenticity andintegrity requirements, which means the following two rules must hold.(1)
Authenticity Rule. All data items in R are surely collected by sensor nodes in the query cell c during time epoch t.(2)
Integrity Rule. There are exactly k data items that are indeed the k highest data items among what are collected by sensor nodes in the query cell c during time epoch t, or equivalently(1)∀ri∈Rt∧∀dj∈Dt∖Rt⟶ri>dj,where Dt represents the data set consisting of all data items collected by sensor nodes in the query cell c during time epoch t.


## 3.3. Evaluation Metrics

In this paper, the following two metrics are used to evaluate the performance of the proposed scheme.(1)
Communication cost: including in-cell communication costCI and query processing communication cost CQ. CI represents the size in bits of data items transmitted from all the sensor nodes to the storage in a cell in the data binding and collecting procedure, while CQ stands for the size of data items transmitted from the storage node in the query cell to the base station during the verifiable query response procedure.(2)
Redundancy rate of query result: the proportion of the total size in bits of additional proof information used to enable verifiable top-k queries to the total size in bits of response message in final query result. This rate, denoted as γ, indicates the efficiency of the query processing. A lower redundancy rate means less additional communication cost required for verification. The redundancy rate will be calculated by the following equation:(2)γ=ls-lrls×100%,where ls is the size in bits of the total data items returned by the storage node, while lr is the total data size of final query result.


## 4. Verifiable Top-k Query Processing

### 4.1. Assumptions and Definition

Given a top-k query Qt=(c,t,k), we assume that the query covers just a cell c in a time epoch t, which we have mentioned in previous sections. There are n sensor nodes in the cell c, which can be denoted as Γ={s1,s2,…,sn}. Assume that an arbitrary sensor node si(1≤i≤n) collects N data items denoted as Di={di,1,di,2,…,di,N} in each time epoch and sorts them into descending order. si shares a secret key Ki with the base station, which is used to encode the proof information for each data item by a HMAC function.


### 4.2. Data Binding and Collecting Protocol

In each time epoch, sensor nodesi collects data and encodes them before sending to the storage node M in the same cell for storage. The detailed procedure is as follows.(1)
si sorts the N data items Di={di,1,di,2,…,di,N} that it collects in time epoch t. Without loss of generality, we assume di,1>di,2>⋯>di,N after being sorted.(2)
According to the sequence of the sensing data items,si computes the message verification code V(di,j) for each data item. V(di,j) of the jth data item di,j(1≤j≤N) can be computed as follows:(3)Vdi,j=HMACKit∥di,1∥di,2∥⋯∥di,j,where HMACKi(·) denotes encoding the corresponding data using a HMAC function with key Ki and ∥ is the concatenation operator.(3)
si constructs a data collecting message MSGC according to the following format and sends to the storage node M: (4)MSGC=idsi,t,di,1,Vdi,1,di,2,Vdi,2,…,di,N,Vdi,N.(4)
M receives and stores the data collecting message of si. We denote the data set consisting of all the data items from all the sensor nodes in the cell as (5)DSt=⋃si∈Γdi,1,…,di,N.


### 4.3. Verifiable Query Response Protocol

Query processing and verification requires collaboration of the base station and the storage node, which works as follows. According to the query issued by the base station, the storage nodeM processes this query and responds with the corresponding data items. At last, the base station computes the query result and verifies the authenticity and integrity of the result. The protocol is described in detail as follows.Phase 1 (query request transmission).
The base station sends the queryQt=(t,k,c) to M and waits for its feedback.Phase 2 (query message feedback).
(1) AfterQt has been received, M computes the k highest data items, denoted as topk(DSt), according to all the sensing data DSt which was sent during the time epoch t from the sensor nodes {s1,s2,…,sn} in cell C. topk(DSt) satisfies the following condition:(6)topkDSt=k∧∀di,djdi∈topkDSt∧dj∈DSt∖topkDSt⟶di>dj.
Assuming that there areδi data items sent by si within topk(DSt), that is to say, {di,1,di,2,…,di,δi}⊆ topk(DSt), then the following condition holds:(7)δi=Di∩topkDSt,0≤δi≤min⁡N,k.
(2)M constructs the following response message according to δi.(i)
Given a sensor nodesi where δi>0, we call it the contributed node, the response message of which is named as msg1si and it should be computed as(8)msg1si=idsi,di,1,…,di,δi+1,Vdi,δi+1,0<δi≤N-1,idsi,di,1,…,di,N,Vdi,N,δi=N,where di,δi+1 is the maximum data item collected by si that is not in topk(DSt) and we call it the out-bound of the si. If all the data items collected by si are in topk(DSt), its out-bound does not exist. Otherwise, there will be one and only one out-bound as for si.(ii)
We call the sensor node whereδi=0noncontributed node. There is only one response message msg0 for all noncontributed nodes which should be computed as(9)msg0=idsi,di,1∣δi=0∧si∈Γ,⨁δi=0∧si∈Γ⁡Vdi,1,where ⨁ is the exclusive or operator.
(3)M summarizes all the response message generated in step (2), constructs the query feedback message MSGQ, and sends it to the base station:(10)MSGQ=msg1si∣δi>0∧si∈Γ,msg0.Phase 3 (query result computation and verification).
(1) Upon receiving the query feedback message fromM, the base station will do the preprocessing to confirm all the message {msg1si∣δi>0∧si∈Γ} of each contributed node and the message msg0 of all noncontributed nodes.
(2) The base station sorts all data items in the response message and gets thek highest data items, which is the top-k query result. We denote the top-k query result by Rt, the minimum data item of which is denoted as min⁡(Rt).
(3) The base station checks whether the following conditions hold in sequence. If and only if all conditions are satisfied, the query resultRt is an authentic and complete result. Otherwise, the query result is abnormal.Condition 1.
All sensor ID in message{msg1si∣δi>0∧si∈Γ} and msg0 construct a set, named Ω, so that Ω={id(si)∣si∈Γ} holds.Condition 2.
Assume thatsi is an arbitrary sensor node that contributes data items to message {msg1(si)∣δi>0∧si∈Γ}, and the response message of si is idsi,di,1,di,2,…,di,μi,Hi, where di,1>di,2>⋯>di,μi. The base station then computes HMACKi(t∥di,1∥⋯∥di,μi), where Ki is a distinct key known only to si and the base station. Then one of the following two conditions must hold:(1)
μi=N∧Hi=Hki(t∥di,1∥⋯∥di,N∥Ψ)∧di,li≥min⁡(Rt);(2)
2≤μi<N∧Hi=Hki(t∥di,1∥⋯∥di,N∥Ψ)∧di,li.Condition 3.
Let{s1,s2,…,sp} be all the noncontributed nodes and their response message msg0 is ids1,d1,ids2,d2,…,id(sp),dp,H0, in which all the data items construct a set DS′={d1,d2,…,dp}. The base station computes HMACK1(t∥d1), HMACK2(t∥d2), …, HMACKp(t∥dp) using the key K1,K2,…,Kp shared with s1,s2,…,sp, respectively, and the following condition holds:(11)H0=⨁dj∈DS′⁡HMACKjt∥dj∧∀dj∈DS′⟶dj<min⁡Rt.
As described in previous two protocols, the sensing data items collected by a sensor node are sorted in descending order and encoded with a HMAC function. Each sensor node shares a secret key only with the base station, and the storage nodes know nothing about the keys. In such a case, it is computationally infeasible for the storage nodes to falsify the message verification code, as long as we choose a considerably complex HMAC algorithm such as SHA-1 [24]. Thus, it is impossible for storage nodes to falsify or conceal data items in the query result without being detected by the base station. Therefore, the scheme proposed in this paper enables authenticity and integrity verification of the top-k query result.


## 4.1. Assumptions and Definition

Given a top-k query Qt=(c,t,k), we assume that the query covers just a cell c in a time epoch t, which we have mentioned in previous sections. There are n sensor nodes in the cell c, which can be denoted as Γ={s1,s2,…,sn}. Assume that an arbitrary sensor node si(1≤i≤n) collects N data items denoted as Di={di,1,di,2,…,di,N} in each time epoch and sorts them into descending order. si shares a secret key Ki with the base station, which is used to encode the proof information for each data item by a HMAC function.


## 4.2. Data Binding and Collecting Protocol

In each time epoch, sensor nodesi collects data and encodes them before sending to the storage node M in the same cell for storage. The detailed procedure is as follows.(1)
si sorts the N data items Di={di,1,di,2,…,di,N} that it collects in time epoch t. Without loss of generality, we assume di,1>di,2>⋯>di,N after being sorted.(2)
According to the sequence of the sensing data items,si computes the message verification code V(di,j) for each data item. V(di,j) of the jth data item di,j(1≤j≤N) can be computed as follows:(3)Vdi,j=HMACKit∥di,1∥di,2∥⋯∥di,j,where HMACKi(·) denotes encoding the corresponding data using a HMAC function with key Ki and ∥ is the concatenation operator.(3)
si constructs a data collecting message MSGC according to the following format and sends to the storage node M: (4)MSGC=idsi,t,di,1,Vdi,1,di,2,Vdi,2,…,di,N,Vdi,N.(4)
M receives and stores the data collecting message of si. We denote the data set consisting of all the data items from all the sensor nodes in the cell as (5)DSt=⋃si∈Γdi,1,…,di,N.


## 4.3. Verifiable Query Response Protocol

Query processing and verification requires collaboration of the base station and the storage node, which works as follows. According to the query issued by the base station, the storage nodeM processes this query and responds with the corresponding data items. At last, the base station computes the query result and verifies the authenticity and integrity of the result. The protocol is described in detail as follows.Phase 1 (query request transmission).
The base station sends the queryQt=(t,k,c) to M and waits for its feedback.Phase 2 (query message feedback).
(1) AfterQt has been received, M computes the k highest data items, denoted as topk(DSt), according to all the sensing data DSt which was sent during the time epoch t from the sensor nodes {s1,s2,…,sn} in cell C. topk(DSt) satisfies the following condition:(6)topkDSt=k∧∀di,djdi∈topkDSt∧dj∈DSt∖topkDSt⟶di>dj.
Assuming that there areδi data items sent by si within topk(DSt), that is to say, {di,1,di,2,…,di,δi}⊆ topk(DSt), then the following condition holds:(7)δi=Di∩topkDSt,0≤δi≤min⁡N,k.
(2)M constructs the following response message according to δi.(i)
Given a sensor nodesi where δi>0, we call it the contributed node, the response message of which is named as msg1si and it should be computed as(8)msg1si=idsi,di,1,…,di,δi+1,Vdi,δi+1,0<δi≤N-1,idsi,di,1,…,di,N,Vdi,N,δi=N,where di,δi+1 is the maximum data item collected by si that is not in topk(DSt) and we call it the out-bound of the si. If all the data items collected by si are in topk(DSt), its out-bound does not exist. Otherwise, there will be one and only one out-bound as for si.(ii)
We call the sensor node whereδi=0noncontributed node. There is only one response message msg0 for all noncontributed nodes which should be computed as(9)msg0=idsi,di,1∣δi=0∧si∈Γ,⨁δi=0∧si∈Γ⁡Vdi,1,where ⨁ is the exclusive or operator.
(3)M summarizes all the response message generated in step (2), constructs the query feedback message MSGQ, and sends it to the base station:(10)MSGQ=msg1si∣δi>0∧si∈Γ,msg0.Phase 3 (query result computation and verification).
(1) Upon receiving the query feedback message fromM, the base station will do the preprocessing to confirm all the message {msg1si∣δi>0∧si∈Γ} of each contributed node and the message msg0 of all noncontributed nodes.
(2) The base station sorts all data items in the response message and gets thek highest data items, which is the top-k query result. We denote the top-k query result by Rt, the minimum data item of which is denoted as min⁡(Rt).
(3) The base station checks whether the following conditions hold in sequence. If and only if all conditions are satisfied, the query resultRt is an authentic and complete result. Otherwise, the query result is abnormal.Condition 1.
All sensor ID in message{msg1si∣δi>0∧si∈Γ} and msg0 construct a set, named Ω, so that Ω={id(si)∣si∈Γ} holds.Condition 2.
Assume thatsi is an arbitrary sensor node that contributes data items to message {msg1(si)∣δi>0∧si∈Γ}, and the response message of si is idsi,di,1,di,2,…,di,μi,Hi, where di,1>di,2>⋯>di,μi. The base station then computes HMACKi(t∥di,1∥⋯∥di,μi), where Ki is a distinct key known only to si and the base station. Then one of the following two conditions must hold:(1)
μi=N∧Hi=Hki(t∥di,1∥⋯∥di,N∥Ψ)∧di,li≥min⁡(Rt);(2)
2≤μi<N∧Hi=Hki(t∥di,1∥⋯∥di,N∥Ψ)∧di,li.Condition 3.
Let{s1,s2,…,sp} be all the noncontributed nodes and their response message msg0 is ids1,d1,ids2,d2,…,id(sp),dp,H0, in which all the data items construct a set DS′={d1,d2,…,dp}. The base station computes HMACK1(t∥d1), HMACK2(t∥d2), …, HMACKp(t∥dp) using the key K1,K2,…,Kp shared with s1,s2,…,sp, respectively, and the following condition holds:(11)H0=⨁dj∈DS′⁡HMACKjt∥dj∧∀dj∈DS′⟶dj<min⁡Rt.
As described in previous two protocols, the sensing data items collected by a sensor node are sorted in descending order and encoded with a HMAC function. Each sensor node shares a secret key only with the base station, and the storage nodes know nothing about the keys. In such a case, it is computationally infeasible for the storage nodes to falsify the message verification code, as long as we choose a considerably complex HMAC algorithm such as SHA-1 [24]. Thus, it is impossible for storage nodes to falsify or conceal data items in the query result without being detected by the base station. Therefore, the scheme proposed in this paper enables authenticity and integrity verification of the top-k query result.


## 5. Protocol Analysis

### 5.1. Communication Cost Analysis

Fromdata binding and collecting protocol andverifiable query response protocol we learn that there are two kinds of communication costs in two-tiered sensor networks, named asin-cell communication costCI andquery processing communication costCQ. Assume that there are n sensor nodes in a cell and each node ID has lid bits. Each sensor node collects N data items in every time epoch, each data item has ld bits, and each HMAC code number has lh bits. In addition, each time epoch number has lt bits. Assume that there are L hops between each sensor node and the storage node on average. We assume that there are μ contributed nodes andn-μ noncontributed nodes, and λ of the μ contributed nodes contributes all the N data items to the query result. Obviously, we have 0≤λ≤N and λ≤k hold. According to such two protocols, we have(12)CI=n·lid+lt+N·ld+lh·L,CQ=μ·lid+k+μ-λ·ld+μ·lh+n-μ·lid+n-μ·ld+lh=n·lid+n+k-λ·ld+μ+1·lh.


### 5.2. Redundancy Rate Analysis

We define the redundancy rateγ of query result as the proportion of the total size of additional proof information used for query result verification to the total size of response message in final query result. We take the same assumption as Section 5.1. According to our proposed protocols, we have(13)γ=CQ-μ·lid+k·ldCQ×100%=n-μ·lid+n-λ·ld+μ+1·lhn·lid+n+k-λ·ld+μ+1·lh×100%.


## 5.1. Communication Cost Analysis

Fromdata binding and collecting protocol andverifiable query response protocol we learn that there are two kinds of communication costs in two-tiered sensor networks, named asin-cell communication costCI andquery processing communication costCQ. Assume that there are n sensor nodes in a cell and each node ID has lid bits. Each sensor node collects N data items in every time epoch, each data item has ld bits, and each HMAC code number has lh bits. In addition, each time epoch number has lt bits. Assume that there are L hops between each sensor node and the storage node on average. We assume that there are μ contributed nodes andn-μ noncontributed nodes, and λ of the μ contributed nodes contributes all the N data items to the query result. Obviously, we have 0≤λ≤N and λ≤k hold. According to such two protocols, we have(12)CI=n·lid+lt+N·ld+lh·L,CQ=μ·lid+k+μ-λ·ld+μ·lh+n-μ·lid+n-μ·ld+lh=n·lid+n+k-λ·ld+μ+1·lh.


## 5.2. Redundancy Rate Analysis

We define the redundancy rateγ of query result as the proportion of the total size of additional proof information used for query result verification to the total size of response message in final query result. We take the same assumption as Section 5.1. According to our proposed protocols, we have(13)γ=CQ-μ·lid+k·ldCQ×100%=n-μ·lid+n-λ·ld+μ+1·lhn·lid+n+k-λ·ld+μ+1·lh×100%.


## 6. Performance Evaluation

In this section, we evaluate the performance of the scheme ETQ-RIV proposed in this paper and compare it with the schemes VSFTQ, EVTQ, and AD-VQ, which are proposed in [10], [4], and [11, 12], respectively. The four schemes VSFTQ, EVTQ, ETQ-RIV, and AD-VQ are implemented on the simulator of [25] with random sensor data items. We compare the in-cell communication cost CI, query processing communication cost CQ, and the query result redundancy rate γ of the four schemes, respectively. We also assume that the packet transmissions are both collision-free and error-free in our experiments.We take the assumption that we carry out the top-k query just in one cell with one storage node and n sensor nodes. The n sensor nodes are distributed uniformly over a two-dimensional region which covers an 80∗80 m2 area. Each sensor node collects N data items during each time epoch and its communication radius is 10 meters. The bit lengths of sensor node ID, time epoch number, sensing data item, and HMAC code are represented by lid, lt, ld, and lh, respectively. The default parameters are listed in Table 1, which are used in the evaluations unless otherwise specified.Table 1
Default evaluation parameters.
Para.
n
l
i
d (bit)
l
t (bit)
l
d (bit)
l
h (bit)
N
k
Val.
250
32
32
32
128
20
10In each measurement, we generate 20 different networks with different network IDs. In each network, the sensor nodes are distributed randomly with different topology. The measurement result is the average of 20 networks.


### 6.1. In-Cell Communication Cost Evaluation

With default parameters, we evaluate the in-cell communication costs of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ in different networks, the result of which is shown in Figure2(a). Figure 2(a) indicates that our proposed scheme ETQ-RIV takes a little less communication costs than VSFTQ and AD-VQ, while EVTQ takes the highest communication costs. Compared with EVTQ, AD-VQ, and VSFTQ, ETQ-RIV saves about 3.77%, 2.86%, and 0.97% of in-cell communication costs on average, respectively. The reason is that in each scheme sensor nodes are required to submit every data item along with some proof information. EVTQ, AD-VQ, and ETQ-RIV use HMAC as proof information. In EVTQ, each sensor node submits one more out-bound HMAC besides every data item’s proof information. In AD-VQ, each sensor requires submitting some information of neighboring nodes besides the HMAC information. In ETQ-RIV, the sensor nodes do not need the out-bound HMAC and neighboring nodes information, so ETQ-RIV performs better than EVTQ and AD-VQ. Different from the other three schemes, VSFTQ replaces the HMAC with symmetric encryption of data item’s order, score, and the time epoch as proof information. In our evaluation, the total bit length of proof information in VSFTQ is more than ETQ-RIV. As a result, ETQ-RIV performs better than VSFTQ.Figure 2
Evaluation results of in-cell communication costs.
(a)
C
I versus network ID
(b)
C
I versus nFigure2(b) indicates that the in-cell communication costs of the three schemes increase as the sensor node number n increases. ETQ-RIV has the best performance as before and saves about 3.77%, 2.86%, and 0.97% of in-cell communication costs on average compared with EVTQ, AD-VQ, and VSFTQ, respectively. The reason is same as the description in the previous section.


### 6.2. Query Communication Cost Evaluation

We evaluate top-k query communication costs of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ as n as well as k increases. Figure 3(a) indicates that the query communication costs of the four schemes all increase as n increases. The reason is obvious: the larger n, the more noncontributed sensor nodes, and the more verification information for noncontributed nodes required to be submitted. Figure 3(a) also shows that ETQ-RIV has the lowest query communication cost, followed by VSFTQ, EVTQ, and then AD-VQ. In detail, the query communication cost of ETQ-RIV is about 98.67% lower than AD-VQ, 64.30% lower than EVTQ, and 47.69% lower than VSFTQ. In AD-VQ, to obtain the top-k query result, the storage node is required to submit a top-(η-1+k) query result due to the dummy readings, where η is a system parameter denoting the difference between the maximum and minimum encrypted readings within an epoch. That is why AD-VQ has the highest query communication cost. In EVTQ, the storage node is required to send a HMAC as proof information for each unqualified sensor node that has no data item satisfying the query, so its query communication cost is high. In VSFTQ, the storage node needs to send symmetric encryption of data item’s order, score, and the time epoch as proof information, which takes more communication cost than ETQ-RIV. However, in ETQ-RIV, only one HMAC is needed for all noncontributed sensor nodes, which greatly reduces the query communication cost.Figure 3
Evaluation results of query communication costs.
(a)
C
Q versus n
(b)
C
Q versus kFigure3(b) shows that the query communication costs of the four schemes all increase as k increases, which is because the larger k, the more data items that need to be returned by the storage node. Similar to Figure 3(a), ETQ-RIV still has the lowest query communication cost, which is about 99.31% lower than AD-VQ, 51.70% lower than EVTQ, and 38.44% lower than VSFTQ. The reason is as mentioned before: only one HMAC is required for all noncontributed sensor nodes in ETQ-RIV.


### 6.3. Redundancy Rate Evaluation

We evaluate top-k query result redundancy rate of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ as k increases. Figure 4 indicates that the redundancy rates of the four schemes all decrease as k increases. Furthermore, AD-VQ has the highest redundancy rate followed by EVQT, VSFTQ, and ETQ-RIV. The redundancy rate of ETQ-RIV is about 12.68% lower than AD-VQ, 6.77% lower than EVTQ, and 5.19% lower than VSFTQ. The reason is as follows. A top-k query result can be divided into two parts: the satisfied data items of query result and the verification information. A larger k implies more satisfied data items and a lower redundancy rate. Compared with the other three schemes, only one HMAC is required for all noncontributed sensor nodes in ETQ-RIV, which makes the ETQ-RIV lowest redundancy rate.Figure 4
Evaluation results of query result redundancy rate.According to the above evaluations and analysis, we can conclude that our proposed ETQ-RIV has better performance than the existing works [4, 5, 7, 10–12] both in communication costs and redundancy rate.


## 6.1. In-Cell Communication Cost Evaluation

With default parameters, we evaluate the in-cell communication costs of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ in different networks, the result of which is shown in Figure2(a). Figure 2(a) indicates that our proposed scheme ETQ-RIV takes a little less communication costs than VSFTQ and AD-VQ, while EVTQ takes the highest communication costs. Compared with EVTQ, AD-VQ, and VSFTQ, ETQ-RIV saves about 3.77%, 2.86%, and 0.97% of in-cell communication costs on average, respectively. The reason is that in each scheme sensor nodes are required to submit every data item along with some proof information. EVTQ, AD-VQ, and ETQ-RIV use HMAC as proof information. In EVTQ, each sensor node submits one more out-bound HMAC besides every data item’s proof information. In AD-VQ, each sensor requires submitting some information of neighboring nodes besides the HMAC information. In ETQ-RIV, the sensor nodes do not need the out-bound HMAC and neighboring nodes information, so ETQ-RIV performs better than EVTQ and AD-VQ. Different from the other three schemes, VSFTQ replaces the HMAC with symmetric encryption of data item’s order, score, and the time epoch as proof information. In our evaluation, the total bit length of proof information in VSFTQ is more than ETQ-RIV. As a result, ETQ-RIV performs better than VSFTQ.Figure 2
Evaluation results of in-cell communication costs.
(a)
C
I versus network ID
(b)
C
I versus nFigure2(b) indicates that the in-cell communication costs of the three schemes increase as the sensor node number n increases. ETQ-RIV has the best performance as before and saves about 3.77%, 2.86%, and 0.97% of in-cell communication costs on average compared with EVTQ, AD-VQ, and VSFTQ, respectively. The reason is same as the description in the previous section.


## 6.2. Query Communication Cost Evaluation

We evaluate top-k query communication costs of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ as n as well as k increases. Figure 3(a) indicates that the query communication costs of the four schemes all increase as n increases. The reason is obvious: the larger n, the more noncontributed sensor nodes, and the more verification information for noncontributed nodes required to be submitted. Figure 3(a) also shows that ETQ-RIV has the lowest query communication cost, followed by VSFTQ, EVTQ, and then AD-VQ. In detail, the query communication cost of ETQ-RIV is about 98.67% lower than AD-VQ, 64.30% lower than EVTQ, and 47.69% lower than VSFTQ. In AD-VQ, to obtain the top-k query result, the storage node is required to submit a top-(η-1+k) query result due to the dummy readings, where η is a system parameter denoting the difference between the maximum and minimum encrypted readings within an epoch. That is why AD-VQ has the highest query communication cost. In EVTQ, the storage node is required to send a HMAC as proof information for each unqualified sensor node that has no data item satisfying the query, so its query communication cost is high. In VSFTQ, the storage node needs to send symmetric encryption of data item’s order, score, and the time epoch as proof information, which takes more communication cost than ETQ-RIV. However, in ETQ-RIV, only one HMAC is needed for all noncontributed sensor nodes, which greatly reduces the query communication cost.Figure 3
Evaluation results of query communication costs.
(a)
C
Q versus n
(b)
C
Q versus kFigure3(b) shows that the query communication costs of the four schemes all increase as k increases, which is because the larger k, the more data items that need to be returned by the storage node. Similar to Figure 3(a), ETQ-RIV still has the lowest query communication cost, which is about 99.31% lower than AD-VQ, 51.70% lower than EVTQ, and 38.44% lower than VSFTQ. The reason is as mentioned before: only one HMAC is required for all noncontributed sensor nodes in ETQ-RIV.


## 6.3. Redundancy Rate Evaluation

We evaluate top-k query result redundancy rate of VSFTQ, EVTQ, ETQ-RIV, and AD-VQ as k increases. Figure 4 indicates that the redundancy rates of the four schemes all decrease as k increases. Furthermore, AD-VQ has the highest redundancy rate followed by EVQT, VSFTQ, and ETQ-RIV. The redundancy rate of ETQ-RIV is about 12.68% lower than AD-VQ, 6.77% lower than EVTQ, and 5.19% lower than VSFTQ. The reason is as follows. A top-k query result can be divided into two parts: the satisfied data items of query result and the verification information. A larger k implies more satisfied data items and a lower redundancy rate. Compared with the other three schemes, only one HMAC is required for all noncontributed sensor nodes in ETQ-RIV, which makes the ETQ-RIV lowest redundancy rate.Figure 4
Evaluation results of query result redundancy rate.According to the above evaluations and analysis, we can conclude that our proposed ETQ-RIV has better performance than the existing works [4, 5, 7, 10–12] both in communication costs and redundancy rate.


## 7. Conclusions

In this paper, we focus on the problem of verifiable top-k query in two-tiered wireless sensor networks and propose an efficient top-k query processing scheme with result integrity verification which is denoted as ETQ-RIV. To make the query result verifiable, each sensor node should submit some encoded message containing the sequence relationship as proof information for verification along with their collected sensing data items. Evaluation results show that ETQ-RIV can decrease the redundancy rate of query result and thus decrease both in-cell and query communication costs and performs better than the existing works in communication costs.



---

*Source: 538482-2015-10-27.xml*