# Efficient and Secure Top-k Query Processing on Hybrid Sensed Data

Authors: Haiqin Wu; Liangmin Wang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

The ubiquity of mobile devices equipped with various sensors has promoted the advent of a novel data sensing paradigm. Based on the traditional static sensing mode, the mobile sensing (sensor) nodes collaboratively collect data with the static sensor nodes. This large volume of hybrid sensed data is then sent to the storage nodes for flexible management and top-k query services. One crucial security issue is that the compromised storage node may falsify or drop some data during the query processing, which returns fake or incorrect result to the query users. In this paper, we propose an efficient and verifiable scheme (EVTopk) for secure top-k query processing on hybrid sensed data, which is suitable for the tiered hybrid sensing network where mobile nodes exist. The basic idea is to bind each data record, generated by static or mobile sensing nodes, with the corresponding location where it is sensed. Then some verification information is created sequentially, which is submitted along with the encrypted locations and hybrid sensed data for user’s verification. The security and efficiency of EVTopk are thoroughly analyzed in theory and evaluated in our experiments, respectively.


---

## Body

## 1. Introduction

Nowadays, the proliferation of mobile devices (e.g., smart-phones), embedded with powerful sensors, has witnessed a revolution in the data sensing paradigm of tiered sensor networks. Traditionally, the two-tiered sensor network [1–3] consists of many energy constrained static (or fixed) sensor nodes and some resource abundant storage nodes at the lower and upper level, respectively. By contrast, the novel sensing paradigm relies on both static sensor nodes and mobile devices (regarded as mobile sensing or sensor nodes) to jointly monitor data about surroundings. It brings great benefits especially to some application-specific scenarios, such as traffic monitoring in smart city. The mobile phones or the vehicles, as the mobile sensing nodes, can monitor traffic conditions in the area where the fixed traffic sensors are not covered. Apparently, the introduction of mobile sensing nodes provides more comprehensive information and reduces the cost for deploying static sensors. Moreover, the energy consumption of static sensors is well balanced.The storage nodes, acting as the data center, are responsible for storing the hybrid sensed data and providing assorted query services for network user (query user). In particular, one important type of queries is represented by top-k query, which asks for k highest (or lowest) data records in a specific region during a specified time slot. Continue with the above example of traffic monitoring, the traffic department can retrieve the 10 most crowded roads (according to the traffic flow) in a city from 8 AM to 9 AM by issuing top-10 query.However, the security issue still remains as a critical concern for pragmatic top-k query, since the storage nodes manage large volume of data and are vulnerable to various attacks. For instance, the compromised storage node may falsify or drop some data during the query processing, which returns fake or incorrect result to the query users. To solve this problem, some verification schemes [4–8] for secure top-k query in tiered sensor networks were proposed in previous researches, which aims to enable the query user to verify the authenticity and correctness of query results. Specifically, Dai et al. [4, 5] generated verification information by chaining the ordered and adjacent data records. Similarly, Zhang et al. [7] bound adjacent data records and some auxiliary ID lists with message authentication code (MAC). Unfortunately, these solutions are only suitable for the static tiered sensor network, as it is assumed that the query users and storage node know the mapping between the nodes’ locations and their corresponding IDs. Clearly, this assumption does not hold in our application scenario, where mobile sensing nodes exist at the lower sensing level. More specifically, different from the static sensor nodes, the mobile sensing nodes generate data at different locations and the compromised storage node may replace the data records sensed in the query region with others sensed outside the region. This attack is difficult to be detected with existing verification methods for static sensor nodes.In this paper, we propose an efficient and verifiable scheme for secure top-k query processing (EVTopk) on hybrid sensed data, which enables the query user to efficiently verify the authenticity and correctness of the query result in our novel tiered sensing network. Our specific contributions are summarized as follows:(i)
We formulate a novel tiered sensing network model (tiered hybrid sensing network) on the basis of the traditional tiered sensor network, where mobile sensing nodes jointly collect data records with static sensor nodes at the lower level.(ii)
To achieve EVTopk, we give a concrete sequence relationship based method by binding each data record with its corresponding sensing location. Moreover, the data records generated by mobile nodes are returned in different formations according to their sensing locations, which enables the query user to detect any inauthentic or incorrect result.(iii)
We present the theoretical analysis and conduct extensive experiments to show the security and efficiency of our proposed scheme.The rest of the paper is organized as follows. In Section2, we review related work, followed by a preliminary of system model and problem formulation in Section 3. Section 4 presents our efficient and verifiable top-k query scheme EVTopk and the theoretical analysis in terms of security and communication overhead. In Section 5, extensive experiments are conducted and the simulation results are analyzed in detail. Finally, we conclude this paper with directions for future work in Section 6.


## 2. Related Work

Recently, due to the advantages of better scalability and capacity, the two-tiered wireless sensor network (TWSN) has drawn increasing attention among researchers. In TWSN, the storage nodes are more vulnerable to be compromised by attackers for their important role in data storage and query management, which brings two challenging security issues: data privacy and data integrity (query integrity).Many privacy preserving methods [9–12] were proposed to prevent the compromised storage nodes from knowing the sensitive information of data collected by sensor nodes and/or the queries issued by users. Peng et al. [10] proposed a Bloom filter based scheme for secure top-k query; moreover, the author adopted an obfuscation coding method to hide the real data distribution and query preference. In [12], a secure top-k query method, called PCTopk, was proposed to preserve the data privacy and query correctness simultaneously. However, this line of work is orthogonal to ours, as in this paper, we only focus on the security property of the query results instead of the privacy concerns, because the hybrid sensed data are not sensitive and are accessible to the public in our scenario.For another line of research, considerable attentions have been paid to ensuring the query integrity (both the authenticity and correctness of the query result), such as verifiable range query [13, 14], secure kNN query [15, 16], and top-k query in different network environments. Three schemes were first proposed by Zhang et al. [2] to verify the fine-grained top-k query result in two-tiered sensor network, which were further improved in [7] to deal with various attacks launched by compromised storage nodes and/or sensor nodes. However, in addition to returning one verification message for each unqualified sensor node, this scheme requires the sensor nodes to exchange their highest scores with other nodes, which results in a large communication overhead. The same problem also exists in [17], for each sensor node needs to send the node IDs and hashes of their neighbors. Additionally, more than k data records are returned to the query user due to the existence of dummy readings. In addition, Dai et al. [4, 5] proposed an efficient verifiable top-k query (EVTQ) by chaining ordered and adjacent data records. Although the scheme is feasible to verify the query result, the storage node needs to send multiple verification messages for those unqualified sensor nodes. As an improvement, He et al. [8] proposed an efficient top-k query processing with integrity verification (ETQ-RIV), in which sensor nodes are not required to submit information about neighbors and only one verification message is returned for all unqualified sensor nodes. Therefore, the query communication cost is significantly reduced. However, all the schemes above only consider the static sensor nodes and are not suitable for our network model where mobile sensing nodes exist. Recently, Liu et al. [18] first proposed a novel verifiable scheme named VTMSN for top-k query in tiered mobile sensor networks, which is the most relevant work to ours. Besides the location information of each data record, both the static and mobile nodes also require to send the encrypted chaining locations to the storage node, some of which are then sent to the query users for verification. Unfortunately, large extra communication cost is incurred since the static nodes send many redundant locations. Moreover, it is assumed that all the sensor nodes switch their state between static and mobile state periodically, which is a little different from our scenario.


## 3. Preliminary

In this section, we introduce our system, attack model, and design goals and briefly state the problems investigated in this paper.


### 3.1. System Model

In this paper, our system model is based on the two-tiered sensor network, which consists of sensor nodes and storage nodes at the lower level and upper level, respectively. Different from the traditional two-tiered sensor networks, we introduce mobile sensing (sensor) nodes in the lower level. As shown in Figure1, in each sensing cell at the sensing level, some mobile sensor nodes (e.g., mobile vehicles in the smart city) also exist for cooperative sensing with the resource-constrained static sensor nodes. Obviously, this novel sensing paradigm can relieve the energy consumption of the static nodes. In addition to the hybrid sensor nodes, each sensing cell contains a storage node, which is responsible for collecting the hybrid sensed data and answering various query requests from the external query users. Specifically, the query users at the user level can issue a top-k query and obtain the query results via an on-demand wireless link.Figure 1
System architecture.For ease of presentation, we assume that the whole network is partitioned into many sensing cells according to the real geographic location. As introduced above, each cell consists of many fixed (static) sensor nodes, mobile sensor nodes, and a storage node. In particular, similar to [18], we assume that the mobile nodes only move in its affiliated sensing cell. During the sensing period, the mobile nodes move and stop regularly to save their energy, and we suppose that the sensed data are only generated when the mobile nodes stop moving. In other words, a data record generated by the mobile node corresponds to the specific location where it is sensed. In particular, some localization techniques [19–21] are available to estimate the location of static or mobile nodes. At the end of each sensing time slot, the static and mobile sensor nodes send their hybrid sensed data to their corresponding storage node.


### 3.2. Attack Model

Compared with the sensor node, the storage node with large volume of sensed data is more vulnerable to attacks. Hence, in this paper, we mainly solve the security problem of compromised storage node that may return fake or incorrect query results to the query users. In particular, the following attacks are mainly considered in our model.(i)
Replacement attack: the compromised storage node may replace some qualified top-k query results with other unqualified data records or those even not generated by the sensor nodes. More specifically, since the mobile nodes generate data records at different locations, the compromised storage node may replace the data records sensed in the query region with those sensed by the same mobile node at other locations.(ii)
Deletion attack: the compromised storage node may drop some qualified data records generated in the query region and return the incomplete results to query users.


### 3.3. Design Goals

In terms of the aforementioned attacks, our design goal is to enable the query users to verify the authenticity and correctness of the query results returned by the storage node. In addition, the query and verification efficiency should also be guaranteed. In general, our method is aimed to achieve the following security goals and performance guarantee.(i)
Authenticity: all the k data records in the result set, returned by the storage node, are generated by the static sensor nodes or mobile sensor nodes which have ever moved in the query region.(ii)
Correctness: all the k data records in the result set are in the query region, and they have the highest k scores among the data records sensed in the query region.(iii)
Efficiency: since the communication cost plays a significant role in the energy consumption of the whole network, the two security goals above should be achieved with as little communication overhead as possible.


### 3.4. Problem Statement

Without loss of generality, we only focus on top-k query processing that covers one sensing cell for simplicity, which consists of N sensor nodes {Si}i=1N (including static and mobile sensor nodes) and a storage node. Moreover, we assume that the query user can distinguish the static nodes from mobile nodes by their IDs. Suppose that each sensor node Si∈{Si}i=1N senses ni data records, denoted by Di={Di,j}j=1ni, during each time slot t. In particular, the location of generating each record Di,j is denoted by li,j. Obviously, if Si is a static sensor node, li,j is the same for each j∈{1,ni}. At the end of slot t, the storage node can receive ∑i=1N‍ni data records (D=⋃i=1NDi). Note that the sensed data records may have multiple attributes (e.g., temperature, humidity), since the sensor nodes are usually embedded with multiple sensors.As presented in [7], we assume that each record Di,j∈Di can be scored by some public scoring functions [22] according to the specific query application. Let f(·) denote a specified increasing scoring function, and then the score of data record Di,j can be denoted by di,j=f(Di,j). For simplicity, we only consider the scalar sensed data and the situation where Di,j and Di,j′ show partial order is not considered in this paper. Therefore, if Di,j≤Di,j′, which means each attribute value in Di,j is smaller than or equal to that in Di,j′, then we have di,j≤di,j′. In other words, if Di,j and Di,j′ are both generated in the query region and Di,j is in the top-k query result, so does Di,j′.Furthermore, we formulate the top-k query as Qt=〈Cq,Rq,t,k〉, where Cq and Rq denote the ID of the query sensing cell and geographic query region, respectively; t and k are the number of query time slot and desired data records. Given the query request Qt, the issue investigated in this paper is how to enable the query user to efficiently verify the authenticity and correctness of the query result, as we described in Section 3.3.To make our description clear, the major notations used in this paper is summarized in Notation Settings.


## 3.1. System Model

In this paper, our system model is based on the two-tiered sensor network, which consists of sensor nodes and storage nodes at the lower level and upper level, respectively. Different from the traditional two-tiered sensor networks, we introduce mobile sensing (sensor) nodes in the lower level. As shown in Figure1, in each sensing cell at the sensing level, some mobile sensor nodes (e.g., mobile vehicles in the smart city) also exist for cooperative sensing with the resource-constrained static sensor nodes. Obviously, this novel sensing paradigm can relieve the energy consumption of the static nodes. In addition to the hybrid sensor nodes, each sensing cell contains a storage node, which is responsible for collecting the hybrid sensed data and answering various query requests from the external query users. Specifically, the query users at the user level can issue a top-k query and obtain the query results via an on-demand wireless link.Figure 1
System architecture.For ease of presentation, we assume that the whole network is partitioned into many sensing cells according to the real geographic location. As introduced above, each cell consists of many fixed (static) sensor nodes, mobile sensor nodes, and a storage node. In particular, similar to [18], we assume that the mobile nodes only move in its affiliated sensing cell. During the sensing period, the mobile nodes move and stop regularly to save their energy, and we suppose that the sensed data are only generated when the mobile nodes stop moving. In other words, a data record generated by the mobile node corresponds to the specific location where it is sensed. In particular, some localization techniques [19–21] are available to estimate the location of static or mobile nodes. At the end of each sensing time slot, the static and mobile sensor nodes send their hybrid sensed data to their corresponding storage node.


## 3.2. Attack Model

Compared with the sensor node, the storage node with large volume of sensed data is more vulnerable to attacks. Hence, in this paper, we mainly solve the security problem of compromised storage node that may return fake or incorrect query results to the query users. In particular, the following attacks are mainly considered in our model.(i)
Replacement attack: the compromised storage node may replace some qualified top-k query results with other unqualified data records or those even not generated by the sensor nodes. More specifically, since the mobile nodes generate data records at different locations, the compromised storage node may replace the data records sensed in the query region with those sensed by the same mobile node at other locations.(ii)
Deletion attack: the compromised storage node may drop some qualified data records generated in the query region and return the incomplete results to query users.


## 3.3. Design Goals

In terms of the aforementioned attacks, our design goal is to enable the query users to verify the authenticity and correctness of the query results returned by the storage node. In addition, the query and verification efficiency should also be guaranteed. In general, our method is aimed to achieve the following security goals and performance guarantee.(i)
Authenticity: all the k data records in the result set, returned by the storage node, are generated by the static sensor nodes or mobile sensor nodes which have ever moved in the query region.(ii)
Correctness: all the k data records in the result set are in the query region, and they have the highest k scores among the data records sensed in the query region.(iii)
Efficiency: since the communication cost plays a significant role in the energy consumption of the whole network, the two security goals above should be achieved with as little communication overhead as possible.


## 3.4. Problem Statement

Without loss of generality, we only focus on top-k query processing that covers one sensing cell for simplicity, which consists of N sensor nodes {Si}i=1N (including static and mobile sensor nodes) and a storage node. Moreover, we assume that the query user can distinguish the static nodes from mobile nodes by their IDs. Suppose that each sensor node Si∈{Si}i=1N senses ni data records, denoted by Di={Di,j}j=1ni, during each time slot t. In particular, the location of generating each record Di,j is denoted by li,j. Obviously, if Si is a static sensor node, li,j is the same for each j∈{1,ni}. At the end of slot t, the storage node can receive ∑i=1N‍ni data records (D=⋃i=1NDi). Note that the sensed data records may have multiple attributes (e.g., temperature, humidity), since the sensor nodes are usually embedded with multiple sensors.As presented in [7], we assume that each record Di,j∈Di can be scored by some public scoring functions [22] according to the specific query application. Let f(·) denote a specified increasing scoring function, and then the score of data record Di,j can be denoted by di,j=f(Di,j). For simplicity, we only consider the scalar sensed data and the situation where Di,j and Di,j′ show partial order is not considered in this paper. Therefore, if Di,j≤Di,j′, which means each attribute value in Di,j is smaller than or equal to that in Di,j′, then we have di,j≤di,j′. In other words, if Di,j and Di,j′ are both generated in the query region and Di,j is in the top-k query result, so does Di,j′.Furthermore, we formulate the top-k query as Qt=〈Cq,Rq,t,k〉, where Cq and Rq denote the ID of the query sensing cell and geographic query region, respectively; t and k are the number of query time slot and desired data records. Given the query request Qt, the issue investigated in this paper is how to enable the query user to efficiently verify the authenticity and correctness of the query result, as we described in Section 3.3.To make our description clear, the major notations used in this paper is summarized in Notation Settings.


## 4. Secure Top-k Query Processing

In this section, we propose a novel verifiable top-k query scheme EVTopk to efficiently verify the authenticity and correctness of top-k query result over the hybrid sensed data. We mainly describe our detailed scheme in Section 4.1, and the security analysis against the compromised storage node is presented in Section 4.2.


### 4.1. Manipulations at Three Levels

In this section, we describe the data preprocessing, top-k query processing, and query verification at the sensing, storage, and user level, respectively. The details are as follows.


#### 4.1.1. Data Preprocessing at Sensing Level

In addition to submitting the sensed data, the sensor nodes require to send some additional information to the storage node, and some of them are then returned to the query users for query verification. Specifically, we generate the verification information by chaining ordered hybrid data records of each sensor node via a cryptographic hash function. Note that, to perform effective query verification for mobile sensor nodes, we bind each data record with its corresponding sensing location.Consider the sensor nodeSi as an example; first, Si sorts its sensed data records Di during each time slot in the descending order according to records’ scores. We assume that the scores of data records in Di differ from each other, which indicates that a unique correct query result exists for top-k query. Suppose that an ordered list 〈Di,1,Di,2,…,Di,ni〉 is generated such that di,1>di,2>⋯>di,ni. In addition, similar to [7], we assume that Si shares a distinct key Ki,t with the query user during time slot t, which is used to encrypt the location information and compute the hash message authentication code (HMAC) as verification information. Initially, Si is preloaded with Ki,0. At the end of time t≥1, the time slot key Ki,t is updated with H(Ki,t-1) [7], where H(·) denotes a hash function. Note that, to provide stronger security, it is necessary to update the encryption key in each time slot. According to the sequence of the ordered data records, Si then chains adjacent data scores by recursively computing(1)vi,j=HMACKi,tvi,j+1∥li,j∥di,j1≤j≤ni,HMACKi,tt∥ij=ni+1,where HMACKi,t(·) denotes the hash message authentication code keyed with Ki,t and ∥ refers to the concatenation. Note that, if Si is a static node, we have li,j=li,1 for j∈[2,ni]. We hereafter use li,1 to denote the location of static node Si for simplicity. Moreover, if ni=0, we set vi,1=HMACKi,t(t∥i).LetEKi,t(·) denote the symmetric encryption function (in this paper, we use AES to encrypt the location information for its better performance especially in dealing with large volume of data) with key Ki,t; subsequently, each sensor node Si∈{Si}i=1N submits the following information Ψi to the storage node. Specifically, if Si is a static node, the information is as follows:(2)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1,Di,1,…,Di,ni,vi,1,…,vi,nini>0.While ifSi is a mobile node, the information is(3)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1∥⋯∥li,ni,Di,1,…,Di,ni,vi,1,…,vi,nini>0.Note that, different from [2, 7], we assume that the location information of each sensor node is unknown to the storage node and query users in advance. Therefore, it is necessary to send some location information to the storage node in this phase. After receiving the message Ψi, the storage node will store the corresponding information of Si, including its data records Di={Di,j}j=1ni, the encrypted sensing locations EKi,t(li,1∥⋯∥li,ni) and the verification information vi,1,…,vi,ni.


#### 4.1.2. Top-k Query Processing at Storage Level

The storage node, after receiving a top-k query Qt=〈Cq,Rq,t,k〉 from the query user, will first locate the query cell Cq and its corresponding query region Rq. It is worth noting that Rq may completely cover multiple static sensor nodes or partially cover multiple mobile sensor nodes during time slot t, as mobile nodes may move out of Rq during this time slot. Let It denote the set of static or mobile sensor nodes in Rq, and we call the set of its corresponding data records a candidate set, which is denoted by Ct. Note that some data records in Ct may be not in the query region.Subsequently, the storage node retrieves the highestk data records RSt in Ct with their sensing locations in Rq, among which the lowest record score is denoted by τ. In particular, for each Si∈It, we assume that there are γi data records with their scores not lower than τ. Accordingly, we have 0≤γi≤ni and k≤∑Si∈It‍γi≤|Ct|, as some mobile sensor nodes may generate data records outside Rq but with their scores higher than τ. Moreover, all these data records are in the candidate set Ct. For each Di,j∈Ct, we make the following definition.(4)Ti=Di,jli,j∈Rq,di,jo.w,which means if the data record Di,j is generated in Rq, Ti,j equals Di,j. Otherwise, it equals the score of Di,j. Then the query user can simply identify if the data records are in Rq according to their data format (here referring to the data dimensions). For each candidate Si∈It, the storage node returns the following information Ri to the query user.IfSi is a static sensor node, the information is(5)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1,Di,1,…,Di,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1,Di,1,…,Di,γi,vi,1ni=γi≥1.IfSi is a mobile sensor node, the information is(6)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1∥⋯∥li,ni,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,vi,1ni=γi≥1.While for eachSi∉It, the information is(7)Ri=i,EKi,tli,1Siis  static,i,EKi,tli,1∥⋯∥li,nio.w.As we can see, for the sensor nodes inIt, besides the qualified top-k data records in RSt, the storage node requires to return the data scores that are higher than τ but are generated outside Rq, so that the query user can recompute vi,1 with (1). While for the sensor nodes outside the query region, they only need to return the node IDs and their encrypted location information (7) to the query user for verification.


#### 4.1.3. Result Verification at User Level

Now we discuss how the user verifies the authenticity and correctness of the query result, as we mentioned in Section3.3. For each information Ri received from the storage node, the query user will defer to the following verification steps.(1)
First, the user determines which of the above casesRi belongs to according to its message format. More specifically, the user can distinguish (5) from (6) according to the first part (i.e., node’s ID), since it is assumed that users can identify the static nodes by IDs in Section 3.4. In addition, as we can see, the information in (7) only contains two parts (ID and at least 20-bit encrypted location), while the information in (5) or (6) contains at least two parts (ID and 160-bit verification information, as well as other data). Accordingly, the user can determine if Ri belongs to (7) easily. Ultimately, if Ri satisfies none of cases, the query result will be declined, or the verification is continued.(2)
Authenticity verification. IfRi satisfies any case in (5) or (6), which means Si∈It. The query user first computes the scores of all the returned data records according to the public function f(·) and then decrypts the encrypted locations; finally, he can derive vi,1 using (1). For example, if the user receives Ri=〈i,EKi,t(li,1),Di,1,…,Di,γi,vi,1〉 in (5), which indicates ni=γi, he can first compute di,1,…,di,γi with f(·) and then get the location li,1 after decryption. To derive vi,1, vi,γi+1=HMACKi,t(t∥i) is first computed by (1) (the second case). Then similarly, the user can compute vi,γi=HMACKi,t(vi,γi+1∥li,γi∥di,γi) (the first case in (1)). Note that here li,γi=li,γi-1=⋯=li,1 for static node Si. Sequentially, vi,γi-1,…,vi,2 can be computed iteratively. At last, the user can compute vi,1=HMACKi,t(vi,2∥li,1∥di,1). If vi,1 is equal to the last field of Ri (i.e., returned vi,1), the user considers the data records and scores in Ri authentic. Moreover, the query result RSt is regarded as authentic if Ri passes the authenticity verification for each Si∈It.(3)
Correctness verification. For eachRi satisfying the format in (7), which means Si is not covered by Rq, the query user first decrypts the encrypted location information with Ki,t. Subsequently, he checks if all the locations (li,1,…,li,ni) are outside Rq. Similarly, for each Ri satisfying the format in (5) or (6), the user decrypts the location information to check if all the locations of returned data records are within Rq. If so, he continues the following verification.
(i)
The user further identifies there are totalk POIs records in RSt with their locations in Rq and determines the lowest data scores τ.(ii)
For each data scoredi,j(j∈[1,γi]) returned in Ri, the user checks if di,j>τ and li,j is outside Rq. Moreover, he checks whether di,ri+1<τ is satisfied.If the above three steps above are all passed, the user considers the query resultRSt authentic and correct. Consider an example where the query user asks for top-4 data records in cell 1. Suppose that the query region in cell 1 covers one static sensor node S1 and two mobile nodes S2 and S3. For simplicity, we assume that n1=n2=n3=4, and τ=30 in top-4 records. Moreover, γ1, γ2, and γ3 are assumed to be 2, 3, and 0, respectively. Specially, suppose that D2,2, sensed by S2, is outside the query region but its score is higher than τ. Since γ2<n2, the fourth case in (6) should be returned. We have T2,1=D2,1, T2,2=d2,2, and T2,3=D2,3; hence R2=〈2,EK2,t(l2,1∥⋯∥l2,4),D2,1,d2,2,D2,3,d2,4,v2,5,v2,1〉. Similarly, S1 follows the fourth case in (5) and the storage node returns R1=〈1,EK1,t(l1,1),D1,1,D1,2,d1,3,v1,4,v1,1〉. S3 satisfies the third case in (6) and R3=〈3,EK3,t(l3,1∥⋯∥l3,4),d3,1,v3,2,v3,1〉 is returned to the user. Obviously, we have RSt={D1,1,D1,2,D2,1,D2,3}. Based on the returned information, the user can deduce {vi,1}i=13 with (1). If they are consistent with the last field of R1, R2, and R3 respectively, the query result is considered authentic. Subsequently, the user decrypts the location information and checks if all the data records in RSt are within Rq. In addition, he checks whether d1,3<30 and d2,2>30 but l2,2 is outside Rq, d2,4<30, and d3,1<30. If so, the query result is considered correct.


### 4.2. Performance Analysis

#### 4.2.1. Detection of the Replacement Attack

Theorem 1.
EVTopk can detect any replacement attacks launched only by a compromised storage node.Proof.
Recall that, in Section3.2, the compromised storage node may perform replacement attack in two ways. First, it may replace some qualified data records sensed by some node (e.g., Si) with other unqualified data records sensed by Si or some other sensor nodes (e.g., Sj). Second, the compromised storage node may replace some qualified data records with others not generated by the sensor nodes at all, which means some data records with high scores are forged.
Assume thatSi contributes μi data records to RSt during time slot t. If Si is a static sensor node, we have μi=γi; otherwise, μi≤γi is satisfied for mobile nodes, as some data records with scores higher than τ but not in Rq are not qualified for the query result. For the first attack method, if a qualified data record Di,m of static node Si is replaced by an unqualified record Di,m+1, it is easy to be detected in step (2) since the ordered data scores are chained together with HMAC, while for the mobile node Si, if a qualified data record Di,m is replaced by di,m, which implies Di,m is not in Rq. Although it can pass the authentication verification in step (2), the correctness check in step (3) can detect this attack by decrypting the encrypted location. Observe that li,m is in Rq, leading to a contradiction with the above implication. On the other hand, if a qualified data record Di,m is replaced by an unqualified record Dj,m+1 sensed by Sj, it is impossible to deduce the same vi,1 as computed by Si. Hence, this attack can be detected in step (2).
As for the second attack method, if some data records of either static or mobile nodes are forged, it will fail the authentication verification since the compromised storage node cannot generate corresponding verification information without knowingKi,t.


#### 4.2.2. Detection of the Deletion Attack

Theorem 2.
EVTopk can detect any deletion attacks launched only by a compromised storage node.Proof.
If the compromised storage node drops part of the qualified data records sensed by a static node (e.g., Si), it will fail the authentication verification as the adjacent data scores are chained with HMAC. Similarly, if all the qualified data records of Si are dropped, it is easy to be detected during the authentication verification because the storage node still requires to return the maximum data score di,γi+1 and verification information vi,γi+2, which obviously cannot derive the same vi,1 as computed by Si.
While for a mobile nodeSj, if part of its qualified data records is dropped, it may pass the authentication verification but will fail the correctness check in step (3). Assume that Rj=〈Dj,1,dj,2,Dj,3,dj,4,vj,5,vj,1〉 is supposed to be returned to the user, which indicates that Dj,1 and Dj,3 are two qualified data records, and dj,2 is higher than τ but outside Rq. If the compromised storage node drops Dj,3 and returns Dj,1, dj,2, vj,3, and vj,1 to the user, the user can derive the correct vj,1 based on the first three item Dj,1, dj,2, and vj,3. However, the format indicates that Dj,1 is a qualified record and dj,2 is lower than τ, which contradicts with the fact that dj,2 is higher than τ. Similar to the static node, if all the qualified data records of Sj are dropped, it is easy to be detected during the authentication verification.


#### 4.2.3. Communication Cost among Three Levels

Assuming that the length of encrypted data is the same as that of its corresponding plaintext. LetLid, Lloc⁡, Lscore, and Lh denote the bit-lengths of a sensor node’s ID, location, score, and each HMAC, respectively. Moreover, let L be the average number of hops between a sensor and a storage node. Additionally, suppose that there are N1(S1,S2,…,SN1) static sensor nodes and N2=N-N1(SN1+1,SN1+2,…,SN) mobile nodes in a query cell. For ease of presentation, we assume that each sensor node Si,i∈[1,N] generate ni=n data records during slot t. Then we have the following theorems.Theorem 3.
Without considering the transmission of some fundamental information, the extra communication cost between the sensing and the storage level in EVTopk is given by(8)Css=N2n+N1·Lloc+Nn·Lh·L.Proof.
As shown in Section4.1.1, since the node IDs, time slot, and sensed data records are the fundamental information to be sent to the storage node, we omit the cost for transmitting them for clarity.
For each static nodeSi,i∈[1,N1], it requires to send encrypted location EKi,t(li,1) and n verification information vi,1,…,vi,n to the storage node. Note that the length of encrypted data is the same as that of its corresponding plaintext. Thus, the additional communication cost incurred by the static node is(9)Cstatic=Lloc⁡+nLh·N1·L.While for each mobile node Si,i∈[N1+1,N], it requires to send encrypted location EKi,t(li,1∥⋯∥li,n) and n verification information vi,1,…,vi,n to the storage node. Thus, the additional communication cost incurred by the mobile node is(10)Cmobile=nLloc⁡+Lh·N2·L.
Hence, by integrating (9) and (10), we have(11)Css=Cstatic+Cmobile=Lloc⁡+nLh·N1·L+nLloc⁡+Lh·N2·L=N2n+N1·Lloc⁡+Nn·Lh·L.Letδq denote the number of qualified sensor nodes that contribute their records to RSt; specifically, δq contains δs and δm static and mobile nodes, respectively. Then the number of the unqualified sensor nodes is N-δq, which contains N1-δs static nodes and N2-δm mobile nodes, respectively.Theorem 4.
Without considering the transmission of qualified data records and its corresponding node IDs, the maximum extra communication cost between storage node and query user in EVTopk is given by(12)CSU≤NLid+N2n+N1Lloc+N2n+N-δmLscore+2NLh.Proof.
As shown in (5), for δs qualified static nodes, it will additionally incur Cqs=(Lid+Lloc⁡+Lscore+2Lh)·δs communication overhead at most (the forth case), while for δm qualified mobile nodes, at most Cqm=(Lid+nLloc⁡+(n-1)·Lscore+2Lh)·δm communication cost will be additionally incurred (in the fourth case, n-2 data records with scores higher than τ are outside Rq; i.e., only one qualified data record is returned for each qualified mobile node). Similarly, for N1-δs unqualified static nodes, it will additionally incur Cus=(Lid+Lloc⁡+Lscore+2Lh)·(N1-δs) communication cost at most (the third case), while for N2-δm unqualified mobile nodes, at most Cus=(Lid+nLloc⁡+nLscore+2Lh)·(N2-δm) communication overhead is additionally incurred (in the fourth case, all the data records with scores higher than τ are outside Rq). As a result, the communication overhead between storage node and the query user follows that(13)CSU≤Cqs+Cqm+Cus+Cum=Lid+Lloc⁡+Lscore+2Lh·δs+Lid+nLloc⁡+n-1·Lscore+2Lh·δm+Lid+Lloc⁡+Lscore+2Lh·N1-δs+Lid+nLloc⁡+nLscore+2Lh·N2-δm=NLid+N2n+N1Lloc⁡+N2n+N-δmLscore+2NLh.


## 4.1. Manipulations at Three Levels

In this section, we describe the data preprocessing, top-k query processing, and query verification at the sensing, storage, and user level, respectively. The details are as follows.


### 4.1.1. Data Preprocessing at Sensing Level

In addition to submitting the sensed data, the sensor nodes require to send some additional information to the storage node, and some of them are then returned to the query users for query verification. Specifically, we generate the verification information by chaining ordered hybrid data records of each sensor node via a cryptographic hash function. Note that, to perform effective query verification for mobile sensor nodes, we bind each data record with its corresponding sensing location.Consider the sensor nodeSi as an example; first, Si sorts its sensed data records Di during each time slot in the descending order according to records’ scores. We assume that the scores of data records in Di differ from each other, which indicates that a unique correct query result exists for top-k query. Suppose that an ordered list 〈Di,1,Di,2,…,Di,ni〉 is generated such that di,1>di,2>⋯>di,ni. In addition, similar to [7], we assume that Si shares a distinct key Ki,t with the query user during time slot t, which is used to encrypt the location information and compute the hash message authentication code (HMAC) as verification information. Initially, Si is preloaded with Ki,0. At the end of time t≥1, the time slot key Ki,t is updated with H(Ki,t-1) [7], where H(·) denotes a hash function. Note that, to provide stronger security, it is necessary to update the encryption key in each time slot. According to the sequence of the ordered data records, Si then chains adjacent data scores by recursively computing(1)vi,j=HMACKi,tvi,j+1∥li,j∥di,j1≤j≤ni,HMACKi,tt∥ij=ni+1,where HMACKi,t(·) denotes the hash message authentication code keyed with Ki,t and ∥ refers to the concatenation. Note that, if Si is a static node, we have li,j=li,1 for j∈[2,ni]. We hereafter use li,1 to denote the location of static node Si for simplicity. Moreover, if ni=0, we set vi,1=HMACKi,t(t∥i).LetEKi,t(·) denote the symmetric encryption function (in this paper, we use AES to encrypt the location information for its better performance especially in dealing with large volume of data) with key Ki,t; subsequently, each sensor node Si∈{Si}i=1N submits the following information Ψi to the storage node. Specifically, if Si is a static node, the information is as follows:(2)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1,Di,1,…,Di,ni,vi,1,…,vi,nini>0.While ifSi is a mobile node, the information is(3)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1∥⋯∥li,ni,Di,1,…,Di,ni,vi,1,…,vi,nini>0.Note that, different from [2, 7], we assume that the location information of each sensor node is unknown to the storage node and query users in advance. Therefore, it is necessary to send some location information to the storage node in this phase. After receiving the message Ψi, the storage node will store the corresponding information of Si, including its data records Di={Di,j}j=1ni, the encrypted sensing locations EKi,t(li,1∥⋯∥li,ni) and the verification information vi,1,…,vi,ni.


### 4.1.2. Top-k Query Processing at Storage Level

The storage node, after receiving a top-k query Qt=〈Cq,Rq,t,k〉 from the query user, will first locate the query cell Cq and its corresponding query region Rq. It is worth noting that Rq may completely cover multiple static sensor nodes or partially cover multiple mobile sensor nodes during time slot t, as mobile nodes may move out of Rq during this time slot. Let It denote the set of static or mobile sensor nodes in Rq, and we call the set of its corresponding data records a candidate set, which is denoted by Ct. Note that some data records in Ct may be not in the query region.Subsequently, the storage node retrieves the highestk data records RSt in Ct with their sensing locations in Rq, among which the lowest record score is denoted by τ. In particular, for each Si∈It, we assume that there are γi data records with their scores not lower than τ. Accordingly, we have 0≤γi≤ni and k≤∑Si∈It‍γi≤|Ct|, as some mobile sensor nodes may generate data records outside Rq but with their scores higher than τ. Moreover, all these data records are in the candidate set Ct. For each Di,j∈Ct, we make the following definition.(4)Ti=Di,jli,j∈Rq,di,jo.w,which means if the data record Di,j is generated in Rq, Ti,j equals Di,j. Otherwise, it equals the score of Di,j. Then the query user can simply identify if the data records are in Rq according to their data format (here referring to the data dimensions). For each candidate Si∈It, the storage node returns the following information Ri to the query user.IfSi is a static sensor node, the information is(5)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1,Di,1,…,Di,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1,Di,1,…,Di,γi,vi,1ni=γi≥1.IfSi is a mobile sensor node, the information is(6)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1∥⋯∥li,ni,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,vi,1ni=γi≥1.While for eachSi∉It, the information is(7)Ri=i,EKi,tli,1Siis  static,i,EKi,tli,1∥⋯∥li,nio.w.As we can see, for the sensor nodes inIt, besides the qualified top-k data records in RSt, the storage node requires to return the data scores that are higher than τ but are generated outside Rq, so that the query user can recompute vi,1 with (1). While for the sensor nodes outside the query region, they only need to return the node IDs and their encrypted location information (7) to the query user for verification.


### 4.1.3. Result Verification at User Level

Now we discuss how the user verifies the authenticity and correctness of the query result, as we mentioned in Section3.3. For each information Ri received from the storage node, the query user will defer to the following verification steps.(1)
First, the user determines which of the above casesRi belongs to according to its message format. More specifically, the user can distinguish (5) from (6) according to the first part (i.e., node’s ID), since it is assumed that users can identify the static nodes by IDs in Section 3.4. In addition, as we can see, the information in (7) only contains two parts (ID and at least 20-bit encrypted location), while the information in (5) or (6) contains at least two parts (ID and 160-bit verification information, as well as other data). Accordingly, the user can determine if Ri belongs to (7) easily. Ultimately, if Ri satisfies none of cases, the query result will be declined, or the verification is continued.(2)
Authenticity verification. IfRi satisfies any case in (5) or (6), which means Si∈It. The query user first computes the scores of all the returned data records according to the public function f(·) and then decrypts the encrypted locations; finally, he can derive vi,1 using (1). For example, if the user receives Ri=〈i,EKi,t(li,1),Di,1,…,Di,γi,vi,1〉 in (5), which indicates ni=γi, he can first compute di,1,…,di,γi with f(·) and then get the location li,1 after decryption. To derive vi,1, vi,γi+1=HMACKi,t(t∥i) is first computed by (1) (the second case). Then similarly, the user can compute vi,γi=HMACKi,t(vi,γi+1∥li,γi∥di,γi) (the first case in (1)). Note that here li,γi=li,γi-1=⋯=li,1 for static node Si. Sequentially, vi,γi-1,…,vi,2 can be computed iteratively. At last, the user can compute vi,1=HMACKi,t(vi,2∥li,1∥di,1). If vi,1 is equal to the last field of Ri (i.e., returned vi,1), the user considers the data records and scores in Ri authentic. Moreover, the query result RSt is regarded as authentic if Ri passes the authenticity verification for each Si∈It.(3)
Correctness verification. For eachRi satisfying the format in (7), which means Si is not covered by Rq, the query user first decrypts the encrypted location information with Ki,t. Subsequently, he checks if all the locations (li,1,…,li,ni) are outside Rq. Similarly, for each Ri satisfying the format in (5) or (6), the user decrypts the location information to check if all the locations of returned data records are within Rq. If so, he continues the following verification.
(i)
The user further identifies there are totalk POIs records in RSt with their locations in Rq and determines the lowest data scores τ.(ii)
For each data scoredi,j(j∈[1,γi]) returned in Ri, the user checks if di,j>τ and li,j is outside Rq. Moreover, he checks whether di,ri+1<τ is satisfied.If the above three steps above are all passed, the user considers the query resultRSt authentic and correct. Consider an example where the query user asks for top-4 data records in cell 1. Suppose that the query region in cell 1 covers one static sensor node S1 and two mobile nodes S2 and S3. For simplicity, we assume that n1=n2=n3=4, and τ=30 in top-4 records. Moreover, γ1, γ2, and γ3 are assumed to be 2, 3, and 0, respectively. Specially, suppose that D2,2, sensed by S2, is outside the query region but its score is higher than τ. Since γ2<n2, the fourth case in (6) should be returned. We have T2,1=D2,1, T2,2=d2,2, and T2,3=D2,3; hence R2=〈2,EK2,t(l2,1∥⋯∥l2,4),D2,1,d2,2,D2,3,d2,4,v2,5,v2,1〉. Similarly, S1 follows the fourth case in (5) and the storage node returns R1=〈1,EK1,t(l1,1),D1,1,D1,2,d1,3,v1,4,v1,1〉. S3 satisfies the third case in (6) and R3=〈3,EK3,t(l3,1∥⋯∥l3,4),d3,1,v3,2,v3,1〉 is returned to the user. Obviously, we have RSt={D1,1,D1,2,D2,1,D2,3}. Based on the returned information, the user can deduce {vi,1}i=13 with (1). If they are consistent with the last field of R1, R2, and R3 respectively, the query result is considered authentic. Subsequently, the user decrypts the location information and checks if all the data records in RSt are within Rq. In addition, he checks whether d1,3<30 and d2,2>30 but l2,2 is outside Rq, d2,4<30, and d3,1<30. If so, the query result is considered correct.


## 4.1.1. Data Preprocessing at Sensing Level

In addition to submitting the sensed data, the sensor nodes require to send some additional information to the storage node, and some of them are then returned to the query users for query verification. Specifically, we generate the verification information by chaining ordered hybrid data records of each sensor node via a cryptographic hash function. Note that, to perform effective query verification for mobile sensor nodes, we bind each data record with its corresponding sensing location.Consider the sensor nodeSi as an example; first, Si sorts its sensed data records Di during each time slot in the descending order according to records’ scores. We assume that the scores of data records in Di differ from each other, which indicates that a unique correct query result exists for top-k query. Suppose that an ordered list 〈Di,1,Di,2,…,Di,ni〉 is generated such that di,1>di,2>⋯>di,ni. In addition, similar to [7], we assume that Si shares a distinct key Ki,t with the query user during time slot t, which is used to encrypt the location information and compute the hash message authentication code (HMAC) as verification information. Initially, Si is preloaded with Ki,0. At the end of time t≥1, the time slot key Ki,t is updated with H(Ki,t-1) [7], where H(·) denotes a hash function. Note that, to provide stronger security, it is necessary to update the encryption key in each time slot. According to the sequence of the ordered data records, Si then chains adjacent data scores by recursively computing(1)vi,j=HMACKi,tvi,j+1∥li,j∥di,j1≤j≤ni,HMACKi,tt∥ij=ni+1,where HMACKi,t(·) denotes the hash message authentication code keyed with Ki,t and ∥ refers to the concatenation. Note that, if Si is a static node, we have li,j=li,1 for j∈[2,ni]. We hereafter use li,1 to denote the location of static node Si for simplicity. Moreover, if ni=0, we set vi,1=HMACKi,t(t∥i).LetEKi,t(·) denote the symmetric encryption function (in this paper, we use AES to encrypt the location information for its better performance especially in dealing with large volume of data) with key Ki,t; subsequently, each sensor node Si∈{Si}i=1N submits the following information Ψi to the storage node. Specifically, if Si is a static node, the information is as follows:(2)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1,Di,1,…,Di,ni,vi,1,…,vi,nini>0.While ifSi is a mobile node, the information is(3)Ψi=i,t,vi,1ni=0,i,t,EKi,tli,1∥⋯∥li,ni,Di,1,…,Di,ni,vi,1,…,vi,nini>0.Note that, different from [2, 7], we assume that the location information of each sensor node is unknown to the storage node and query users in advance. Therefore, it is necessary to send some location information to the storage node in this phase. After receiving the message Ψi, the storage node will store the corresponding information of Si, including its data records Di={Di,j}j=1ni, the encrypted sensing locations EKi,t(li,1∥⋯∥li,ni) and the verification information vi,1,…,vi,ni.


## 4.1.2. Top-k Query Processing at Storage Level

The storage node, after receiving a top-k query Qt=〈Cq,Rq,t,k〉 from the query user, will first locate the query cell Cq and its corresponding query region Rq. It is worth noting that Rq may completely cover multiple static sensor nodes or partially cover multiple mobile sensor nodes during time slot t, as mobile nodes may move out of Rq during this time slot. Let It denote the set of static or mobile sensor nodes in Rq, and we call the set of its corresponding data records a candidate set, which is denoted by Ct. Note that some data records in Ct may be not in the query region.Subsequently, the storage node retrieves the highestk data records RSt in Ct with their sensing locations in Rq, among which the lowest record score is denoted by τ. In particular, for each Si∈It, we assume that there are γi data records with their scores not lower than τ. Accordingly, we have 0≤γi≤ni and k≤∑Si∈It‍γi≤|Ct|, as some mobile sensor nodes may generate data records outside Rq but with their scores higher than τ. Moreover, all these data records are in the candidate set Ct. For each Di,j∈Ct, we make the following definition.(4)Ti=Di,jli,j∈Rq,di,jo.w,which means if the data record Di,j is generated in Rq, Ti,j equals Di,j. Otherwise, it equals the score of Di,j. Then the query user can simply identify if the data records are in Rq according to their data format (here referring to the data dimensions). For each candidate Si∈It, the storage node returns the following information Ri to the query user.IfSi is a static sensor node, the information is(5)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1,Di,1,…,Di,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1,Di,1,…,Di,γi,vi,1ni=γi≥1.IfSi is a mobile sensor node, the information is(6)Ri=i,vi,1ni=γi=0,i,EKi,tli,1,di,1,vi,1ni=1,γi=0,i,EKi,tli,1∥⋯∥li,ni,di,1,vi,2,vi,1ni≥2,γi=0,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,di,γi+1,vi,γi+2,vi,1ni≥2,0<γi<ni,i,EKi,tli,1∥⋯∥li,ni,Ti,1,…,Ti,γi,vi,1ni=γi≥1.While for eachSi∉It, the information is(7)Ri=i,EKi,tli,1Siis  static,i,EKi,tli,1∥⋯∥li,nio.w.As we can see, for the sensor nodes inIt, besides the qualified top-k data records in RSt, the storage node requires to return the data scores that are higher than τ but are generated outside Rq, so that the query user can recompute vi,1 with (1). While for the sensor nodes outside the query region, they only need to return the node IDs and their encrypted location information (7) to the query user for verification.


## 4.1.3. Result Verification at User Level

Now we discuss how the user verifies the authenticity and correctness of the query result, as we mentioned in Section3.3. For each information Ri received from the storage node, the query user will defer to the following verification steps.(1)
First, the user determines which of the above casesRi belongs to according to its message format. More specifically, the user can distinguish (5) from (6) according to the first part (i.e., node’s ID), since it is assumed that users can identify the static nodes by IDs in Section 3.4. In addition, as we can see, the information in (7) only contains two parts (ID and at least 20-bit encrypted location), while the information in (5) or (6) contains at least two parts (ID and 160-bit verification information, as well as other data). Accordingly, the user can determine if Ri belongs to (7) easily. Ultimately, if Ri satisfies none of cases, the query result will be declined, or the verification is continued.(2)
Authenticity verification. IfRi satisfies any case in (5) or (6), which means Si∈It. The query user first computes the scores of all the returned data records according to the public function f(·) and then decrypts the encrypted locations; finally, he can derive vi,1 using (1). For example, if the user receives Ri=〈i,EKi,t(li,1),Di,1,…,Di,γi,vi,1〉 in (5), which indicates ni=γi, he can first compute di,1,…,di,γi with f(·) and then get the location li,1 after decryption. To derive vi,1, vi,γi+1=HMACKi,t(t∥i) is first computed by (1) (the second case). Then similarly, the user can compute vi,γi=HMACKi,t(vi,γi+1∥li,γi∥di,γi) (the first case in (1)). Note that here li,γi=li,γi-1=⋯=li,1 for static node Si. Sequentially, vi,γi-1,…,vi,2 can be computed iteratively. At last, the user can compute vi,1=HMACKi,t(vi,2∥li,1∥di,1). If vi,1 is equal to the last field of Ri (i.e., returned vi,1), the user considers the data records and scores in Ri authentic. Moreover, the query result RSt is regarded as authentic if Ri passes the authenticity verification for each Si∈It.(3)
Correctness verification. For eachRi satisfying the format in (7), which means Si is not covered by Rq, the query user first decrypts the encrypted location information with Ki,t. Subsequently, he checks if all the locations (li,1,…,li,ni) are outside Rq. Similarly, for each Ri satisfying the format in (5) or (6), the user decrypts the location information to check if all the locations of returned data records are within Rq. If so, he continues the following verification.
(i)
The user further identifies there are totalk POIs records in RSt with their locations in Rq and determines the lowest data scores τ.(ii)
For each data scoredi,j(j∈[1,γi]) returned in Ri, the user checks if di,j>τ and li,j is outside Rq. Moreover, he checks whether di,ri+1<τ is satisfied.If the above three steps above are all passed, the user considers the query resultRSt authentic and correct. Consider an example where the query user asks for top-4 data records in cell 1. Suppose that the query region in cell 1 covers one static sensor node S1 and two mobile nodes S2 and S3. For simplicity, we assume that n1=n2=n3=4, and τ=30 in top-4 records. Moreover, γ1, γ2, and γ3 are assumed to be 2, 3, and 0, respectively. Specially, suppose that D2,2, sensed by S2, is outside the query region but its score is higher than τ. Since γ2<n2, the fourth case in (6) should be returned. We have T2,1=D2,1, T2,2=d2,2, and T2,3=D2,3; hence R2=〈2,EK2,t(l2,1∥⋯∥l2,4),D2,1,d2,2,D2,3,d2,4,v2,5,v2,1〉. Similarly, S1 follows the fourth case in (5) and the storage node returns R1=〈1,EK1,t(l1,1),D1,1,D1,2,d1,3,v1,4,v1,1〉. S3 satisfies the third case in (6) and R3=〈3,EK3,t(l3,1∥⋯∥l3,4),d3,1,v3,2,v3,1〉 is returned to the user. Obviously, we have RSt={D1,1,D1,2,D2,1,D2,3}. Based on the returned information, the user can deduce {vi,1}i=13 with (1). If they are consistent with the last field of R1, R2, and R3 respectively, the query result is considered authentic. Subsequently, the user decrypts the location information and checks if all the data records in RSt are within Rq. In addition, he checks whether d1,3<30 and d2,2>30 but l2,2 is outside Rq, d2,4<30, and d3,1<30. If so, the query result is considered correct.


## 4.2. Performance Analysis

### 4.2.1. Detection of the Replacement Attack

Theorem 1.
EVTopk can detect any replacement attacks launched only by a compromised storage node.Proof.
Recall that, in Section3.2, the compromised storage node may perform replacement attack in two ways. First, it may replace some qualified data records sensed by some node (e.g., Si) with other unqualified data records sensed by Si or some other sensor nodes (e.g., Sj). Second, the compromised storage node may replace some qualified data records with others not generated by the sensor nodes at all, which means some data records with high scores are forged.
Assume thatSi contributes μi data records to RSt during time slot t. If Si is a static sensor node, we have μi=γi; otherwise, μi≤γi is satisfied for mobile nodes, as some data records with scores higher than τ but not in Rq are not qualified for the query result. For the first attack method, if a qualified data record Di,m of static node Si is replaced by an unqualified record Di,m+1, it is easy to be detected in step (2) since the ordered data scores are chained together with HMAC, while for the mobile node Si, if a qualified data record Di,m is replaced by di,m, which implies Di,m is not in Rq. Although it can pass the authentication verification in step (2), the correctness check in step (3) can detect this attack by decrypting the encrypted location. Observe that li,m is in Rq, leading to a contradiction with the above implication. On the other hand, if a qualified data record Di,m is replaced by an unqualified record Dj,m+1 sensed by Sj, it is impossible to deduce the same vi,1 as computed by Si. Hence, this attack can be detected in step (2).
As for the second attack method, if some data records of either static or mobile nodes are forged, it will fail the authentication verification since the compromised storage node cannot generate corresponding verification information without knowingKi,t.


### 4.2.2. Detection of the Deletion Attack

Theorem 2.
EVTopk can detect any deletion attacks launched only by a compromised storage node.Proof.
If the compromised storage node drops part of the qualified data records sensed by a static node (e.g., Si), it will fail the authentication verification as the adjacent data scores are chained with HMAC. Similarly, if all the qualified data records of Si are dropped, it is easy to be detected during the authentication verification because the storage node still requires to return the maximum data score di,γi+1 and verification information vi,γi+2, which obviously cannot derive the same vi,1 as computed by Si.
While for a mobile nodeSj, if part of its qualified data records is dropped, it may pass the authentication verification but will fail the correctness check in step (3). Assume that Rj=〈Dj,1,dj,2,Dj,3,dj,4,vj,5,vj,1〉 is supposed to be returned to the user, which indicates that Dj,1 and Dj,3 are two qualified data records, and dj,2 is higher than τ but outside Rq. If the compromised storage node drops Dj,3 and returns Dj,1, dj,2, vj,3, and vj,1 to the user, the user can derive the correct vj,1 based on the first three item Dj,1, dj,2, and vj,3. However, the format indicates that Dj,1 is a qualified record and dj,2 is lower than τ, which contradicts with the fact that dj,2 is higher than τ. Similar to the static node, if all the qualified data records of Sj are dropped, it is easy to be detected during the authentication verification.


### 4.2.3. Communication Cost among Three Levels

Assuming that the length of encrypted data is the same as that of its corresponding plaintext. LetLid, Lloc⁡, Lscore, and Lh denote the bit-lengths of a sensor node’s ID, location, score, and each HMAC, respectively. Moreover, let L be the average number of hops between a sensor and a storage node. Additionally, suppose that there are N1(S1,S2,…,SN1) static sensor nodes and N2=N-N1(SN1+1,SN1+2,…,SN) mobile nodes in a query cell. For ease of presentation, we assume that each sensor node Si,i∈[1,N] generate ni=n data records during slot t. Then we have the following theorems.Theorem 3.
Without considering the transmission of some fundamental information, the extra communication cost between the sensing and the storage level in EVTopk is given by(8)Css=N2n+N1·Lloc+Nn·Lh·L.Proof.
As shown in Section4.1.1, since the node IDs, time slot, and sensed data records are the fundamental information to be sent to the storage node, we omit the cost for transmitting them for clarity.
For each static nodeSi,i∈[1,N1], it requires to send encrypted location EKi,t(li,1) and n verification information vi,1,…,vi,n to the storage node. Note that the length of encrypted data is the same as that of its corresponding plaintext. Thus, the additional communication cost incurred by the static node is(9)Cstatic=Lloc⁡+nLh·N1·L.While for each mobile node Si,i∈[N1+1,N], it requires to send encrypted location EKi,t(li,1∥⋯∥li,n) and n verification information vi,1,…,vi,n to the storage node. Thus, the additional communication cost incurred by the mobile node is(10)Cmobile=nLloc⁡+Lh·N2·L.
Hence, by integrating (9) and (10), we have(11)Css=Cstatic+Cmobile=Lloc⁡+nLh·N1·L+nLloc⁡+Lh·N2·L=N2n+N1·Lloc⁡+Nn·Lh·L.Letδq denote the number of qualified sensor nodes that contribute their records to RSt; specifically, δq contains δs and δm static and mobile nodes, respectively. Then the number of the unqualified sensor nodes is N-δq, which contains N1-δs static nodes and N2-δm mobile nodes, respectively.Theorem 4.
Without considering the transmission of qualified data records and its corresponding node IDs, the maximum extra communication cost between storage node and query user in EVTopk is given by(12)CSU≤NLid+N2n+N1Lloc+N2n+N-δmLscore+2NLh.Proof.
As shown in (5), for δs qualified static nodes, it will additionally incur Cqs=(Lid+Lloc⁡+Lscore+2Lh)·δs communication overhead at most (the forth case), while for δm qualified mobile nodes, at most Cqm=(Lid+nLloc⁡+(n-1)·Lscore+2Lh)·δm communication cost will be additionally incurred (in the fourth case, n-2 data records with scores higher than τ are outside Rq; i.e., only one qualified data record is returned for each qualified mobile node). Similarly, for N1-δs unqualified static nodes, it will additionally incur Cus=(Lid+Lloc⁡+Lscore+2Lh)·(N1-δs) communication cost at most (the third case), while for N2-δm unqualified mobile nodes, at most Cus=(Lid+nLloc⁡+nLscore+2Lh)·(N2-δm) communication overhead is additionally incurred (in the fourth case, all the data records with scores higher than τ are outside Rq). As a result, the communication overhead between storage node and the query user follows that(13)CSU≤Cqs+Cqm+Cus+Cum=Lid+Lloc⁡+Lscore+2Lh·δs+Lid+nLloc⁡+n-1·Lscore+2Lh·δm+Lid+Lloc⁡+Lscore+2Lh·N1-δs+Lid+nLloc⁡+nLscore+2Lh·N2-δm=NLid+N2n+N1Lloc⁡+N2n+N-δmLscore+2NLh.


## 4.2.1. Detection of the Replacement Attack

Theorem 1.
EVTopk can detect any replacement attacks launched only by a compromised storage node.Proof.
Recall that, in Section3.2, the compromised storage node may perform replacement attack in two ways. First, it may replace some qualified data records sensed by some node (e.g., Si) with other unqualified data records sensed by Si or some other sensor nodes (e.g., Sj). Second, the compromised storage node may replace some qualified data records with others not generated by the sensor nodes at all, which means some data records with high scores are forged.
Assume thatSi contributes μi data records to RSt during time slot t. If Si is a static sensor node, we have μi=γi; otherwise, μi≤γi is satisfied for mobile nodes, as some data records with scores higher than τ but not in Rq are not qualified for the query result. For the first attack method, if a qualified data record Di,m of static node Si is replaced by an unqualified record Di,m+1, it is easy to be detected in step (2) since the ordered data scores are chained together with HMAC, while for the mobile node Si, if a qualified data record Di,m is replaced by di,m, which implies Di,m is not in Rq. Although it can pass the authentication verification in step (2), the correctness check in step (3) can detect this attack by decrypting the encrypted location. Observe that li,m is in Rq, leading to a contradiction with the above implication. On the other hand, if a qualified data record Di,m is replaced by an unqualified record Dj,m+1 sensed by Sj, it is impossible to deduce the same vi,1 as computed by Si. Hence, this attack can be detected in step (2).
As for the second attack method, if some data records of either static or mobile nodes are forged, it will fail the authentication verification since the compromised storage node cannot generate corresponding verification information without knowingKi,t.


## 4.2.2. Detection of the Deletion Attack

Theorem 2.
EVTopk can detect any deletion attacks launched only by a compromised storage node.Proof.
If the compromised storage node drops part of the qualified data records sensed by a static node (e.g., Si), it will fail the authentication verification as the adjacent data scores are chained with HMAC. Similarly, if all the qualified data records of Si are dropped, it is easy to be detected during the authentication verification because the storage node still requires to return the maximum data score di,γi+1 and verification information vi,γi+2, which obviously cannot derive the same vi,1 as computed by Si.
While for a mobile nodeSj, if part of its qualified data records is dropped, it may pass the authentication verification but will fail the correctness check in step (3). Assume that Rj=〈Dj,1,dj,2,Dj,3,dj,4,vj,5,vj,1〉 is supposed to be returned to the user, which indicates that Dj,1 and Dj,3 are two qualified data records, and dj,2 is higher than τ but outside Rq. If the compromised storage node drops Dj,3 and returns Dj,1, dj,2, vj,3, and vj,1 to the user, the user can derive the correct vj,1 based on the first three item Dj,1, dj,2, and vj,3. However, the format indicates that Dj,1 is a qualified record and dj,2 is lower than τ, which contradicts with the fact that dj,2 is higher than τ. Similar to the static node, if all the qualified data records of Sj are dropped, it is easy to be detected during the authentication verification.


## 4.2.3. Communication Cost among Three Levels

Assuming that the length of encrypted data is the same as that of its corresponding plaintext. LetLid, Lloc⁡, Lscore, and Lh denote the bit-lengths of a sensor node’s ID, location, score, and each HMAC, respectively. Moreover, let L be the average number of hops between a sensor and a storage node. Additionally, suppose that there are N1(S1,S2,…,SN1) static sensor nodes and N2=N-N1(SN1+1,SN1+2,…,SN) mobile nodes in a query cell. For ease of presentation, we assume that each sensor node Si,i∈[1,N] generate ni=n data records during slot t. Then we have the following theorems.Theorem 3.
Without considering the transmission of some fundamental information, the extra communication cost between the sensing and the storage level in EVTopk is given by(8)Css=N2n+N1·Lloc+Nn·Lh·L.Proof.
As shown in Section4.1.1, since the node IDs, time slot, and sensed data records are the fundamental information to be sent to the storage node, we omit the cost for transmitting them for clarity.
For each static nodeSi,i∈[1,N1], it requires to send encrypted location EKi,t(li,1) and n verification information vi,1,…,vi,n to the storage node. Note that the length of encrypted data is the same as that of its corresponding plaintext. Thus, the additional communication cost incurred by the static node is(9)Cstatic=Lloc⁡+nLh·N1·L.While for each mobile node Si,i∈[N1+1,N], it requires to send encrypted location EKi,t(li,1∥⋯∥li,n) and n verification information vi,1,…,vi,n to the storage node. Thus, the additional communication cost incurred by the mobile node is(10)Cmobile=nLloc⁡+Lh·N2·L.
Hence, by integrating (9) and (10), we have(11)Css=Cstatic+Cmobile=Lloc⁡+nLh·N1·L+nLloc⁡+Lh·N2·L=N2n+N1·Lloc⁡+Nn·Lh·L.Letδq denote the number of qualified sensor nodes that contribute their records to RSt; specifically, δq contains δs and δm static and mobile nodes, respectively. Then the number of the unqualified sensor nodes is N-δq, which contains N1-δs static nodes and N2-δm mobile nodes, respectively.Theorem 4.
Without considering the transmission of qualified data records and its corresponding node IDs, the maximum extra communication cost between storage node and query user in EVTopk is given by(12)CSU≤NLid+N2n+N1Lloc+N2n+N-δmLscore+2NLh.Proof.
As shown in (5), for δs qualified static nodes, it will additionally incur Cqs=(Lid+Lloc⁡+Lscore+2Lh)·δs communication overhead at most (the forth case), while for δm qualified mobile nodes, at most Cqm=(Lid+nLloc⁡+(n-1)·Lscore+2Lh)·δm communication cost will be additionally incurred (in the fourth case, n-2 data records with scores higher than τ are outside Rq; i.e., only one qualified data record is returned for each qualified mobile node). Similarly, for N1-δs unqualified static nodes, it will additionally incur Cus=(Lid+Lloc⁡+Lscore+2Lh)·(N1-δs) communication cost at most (the third case), while for N2-δm unqualified mobile nodes, at most Cus=(Lid+nLloc⁡+nLscore+2Lh)·(N2-δm) communication overhead is additionally incurred (in the fourth case, all the data records with scores higher than τ are outside Rq). As a result, the communication overhead between storage node and the query user follows that(13)CSU≤Cqs+Cqm+Cus+Cum=Lid+Lloc⁡+Lscore+2Lh·δs+Lid+nLloc⁡+n-1·Lscore+2Lh·δm+Lid+Lloc⁡+Lscore+2Lh·N1-δs+Lid+nLloc⁡+nLscore+2Lh·N2-δm=NLid+N2n+N1Lloc⁡+N2n+N-δmLscore+2NLh.


## 5. Simulation Results

In this section, we mainly evaluate the efficiency of our proposed scheme EVTopk and validate the theoretical results we discussed in Section4 using experimental simulations on a synthetic dataset. Our simulations are implemented on Matlab. More specifically, we assume a sensing cell of 1000 m × 1000 m with 500 randomly distributed sensor nodes and a storage node at the center, in which static and mobile nodes account for 50%, respectively, and the mobile nodes move in a random waypoint model. Without loss of generality, we suppose that each static or mobile sensor node generates 10 data records during the time slot, and the packets are transmitted without collision and error. Table 1 presents the default parameter settings in our experiments, unless stated otherwise.Table 1
Default simulation settings.
Para. Val. N 500 n 10 k 50 r 100 Lid 16 L l o c 20 L h 160 Lscore 20Specifically, we use 160-bit HMAC-SHA1 to compute the verification information for each sensor node, and the default query region in the cell is 400 m × 400 m. The main performance metrics used to evaluate our proposed scheme include the aforementioned two aspects: the communication cost between the sensing and storage level, as well as that between the storage and user level. It is worth noting that these metrics are not compared with those in other schemes as none of them are fit for our network model where both static and mobile nodes exist. To avoid the accidental error, in all sets of experiments, our scheme is measured on an average of 100 random simulations.


### 5.1. Communication Cost between Sensing and Storage Level

Figure2 shows the simulation and theoretical results of the communication cost between the sensing and storage level with varying N, which is the total number of sensor nodes in the query cell. It is clear that our simulation result matches the analytical result closely. More specifically, the communication cost increases linearly as N goes from 200 to 800. The reason is that more static or mobile sensor nodes require to send the location and verification information to the storage node with increasing N. Specially, due to the mobility of mobile nodes, they need to send encrypted concatenate locations, as shown in (3), which results in more communication cost than static nodes. Moreover, the actual hops between a mobile sensor and a storage node may be more than the average hops which we considered in Theorem 3. Therefore, the simulation result incurs slightly more communication cost than that in theory.Figure 2
Impact ofN on the sensing-storage communication cost.Figure3 shows the impact of n, the number of data records generated by each node per slot, on the sensing-storage communication cost in both our simulation and theoretical analysis. Similarly, we can observe that the simulation and theoretical results closely match as n increases, and the sensing-storage communication cost of them both grows linearly with n. The reason is that more location and verification information need be sent to the storage node for each static or mobile node. Moreover, our simulation exhibits slightly more expensive cost due to the same reason as we analyzed above.Figure 3
Impact ofn on the sensing-storage communication cost.


### 5.2. Communication Cost between Storage and User Level

As for the communication cost between storage and user level, since we only give the theoretical bound instead of the detailed cost in Theorem4, we do not compare the theoretical and simulation results of our scheme in this section. Figure 4 illustrates the impact of k on the storage-user communication cost where the query region Rq = 400 m × 400 m, 500 m × 500 m, and 600 m × 600 m, respectively.Figure 4
Impact ofk and Rq on the storage-user communication cost.As we can see, on one hand, with the increasing number ofk, the communication cost grows slowly for a fixed query region. On the other hand, if k keeps unchanged, the larger query region is, the more expensive cost will be incurred. The reason is that more verification information about qualified or unqualified sensor nodes is transmitted to the query user as k or Rq increases. More specifically, if k keeps unchanged, more static or mobile nodes are unqualified with the extension of Rq and hence incurs more verification information about unqualified nodes. In contrast, if k increases, there may be more qualified sensor nodes in a given query region and hence incurs more verification information about qualified nodes. Note that the impact of k is much smaller than that of Rq on the storage-user communication cost, due to the fact that unqualified nodes incur more cost than the qualified nodes. Moreover, it is not required to send the verification information for each qualified data record.In addition, Figure5 depicts the impact of N and n on the storage-user communication cost. Similarly, the communication cost between the storage and user level increases linearly with N, which is consistent with the theoretical bound given in Theorem 4. This is because the query region will get denser as N grows in a given query cell, and more verification information about unqualified sensor nodes needs to be sent to the query user. In contrast, with the increasing number of n, more location information about mobile nodes need be transmitted and thus leads to the larger communication cost.Figure 5
Impact ofN and n on the storage-user communication cost.


## 5.1. Communication Cost between Sensing and Storage Level

Figure2 shows the simulation and theoretical results of the communication cost between the sensing and storage level with varying N, which is the total number of sensor nodes in the query cell. It is clear that our simulation result matches the analytical result closely. More specifically, the communication cost increases linearly as N goes from 200 to 800. The reason is that more static or mobile sensor nodes require to send the location and verification information to the storage node with increasing N. Specially, due to the mobility of mobile nodes, they need to send encrypted concatenate locations, as shown in (3), which results in more communication cost than static nodes. Moreover, the actual hops between a mobile sensor and a storage node may be more than the average hops which we considered in Theorem 3. Therefore, the simulation result incurs slightly more communication cost than that in theory.Figure 2
Impact ofN on the sensing-storage communication cost.Figure3 shows the impact of n, the number of data records generated by each node per slot, on the sensing-storage communication cost in both our simulation and theoretical analysis. Similarly, we can observe that the simulation and theoretical results closely match as n increases, and the sensing-storage communication cost of them both grows linearly with n. The reason is that more location and verification information need be sent to the storage node for each static or mobile node. Moreover, our simulation exhibits slightly more expensive cost due to the same reason as we analyzed above.Figure 3
Impact ofn on the sensing-storage communication cost.


## 5.2. Communication Cost between Storage and User Level

As for the communication cost between storage and user level, since we only give the theoretical bound instead of the detailed cost in Theorem4, we do not compare the theoretical and simulation results of our scheme in this section. Figure 4 illustrates the impact of k on the storage-user communication cost where the query region Rq = 400 m × 400 m, 500 m × 500 m, and 600 m × 600 m, respectively.Figure 4
Impact ofk and Rq on the storage-user communication cost.As we can see, on one hand, with the increasing number ofk, the communication cost grows slowly for a fixed query region. On the other hand, if k keeps unchanged, the larger query region is, the more expensive cost will be incurred. The reason is that more verification information about qualified or unqualified sensor nodes is transmitted to the query user as k or Rq increases. More specifically, if k keeps unchanged, more static or mobile nodes are unqualified with the extension of Rq and hence incurs more verification information about unqualified nodes. In contrast, if k increases, there may be more qualified sensor nodes in a given query region and hence incurs more verification information about qualified nodes. Note that the impact of k is much smaller than that of Rq on the storage-user communication cost, due to the fact that unqualified nodes incur more cost than the qualified nodes. Moreover, it is not required to send the verification information for each qualified data record.In addition, Figure5 depicts the impact of N and n on the storage-user communication cost. Similarly, the communication cost between the storage and user level increases linearly with N, which is consistent with the theoretical bound given in Theorem 4. This is because the query region will get denser as N grows in a given query cell, and more verification information about unqualified sensor nodes needs to be sent to the query user. In contrast, with the increasing number of n, more location information about mobile nodes need be transmitted and thus leads to the larger communication cost.Figure 5
Impact ofN and n on the storage-user communication cost.


## 6. Conclusion

In this paper, we study the secure top-k query processing in a novel sensing paradigm, where hybrid sensed data are generated by both static and mobile sensor nodes. To tackle the security threats posed by the compromised storage node, we propose an efficient and verifiable scheme that enables the query user to efficiently verify the authenticity and correctness of the query result. A novel data binding method is designed to generate the verification information, with which the storage node is not required to return verification information for each qualified data record. Theoretical analysis and simulation results demonstrate the security and efficiency of our scheme. Our future work is to investigate privacy preserving top-k query processing with integrity verification on the hybrid sensed data in tiered hybrid sensing network.



---

*Source: 1685054-2016-12-08.xml*