# STQ-SCS: An Efficient and Secure Scheme for Fine-Grained Spatial-Temporal Top-k Query in Fog-Based Mobile Sensor-Cloud Systems

Authors: Jie Min; Junbin Liang; Xingpo Ma; Hongling Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the emergence of the fog computing and the sensor-cloud computing paradigms, end users can retrieve the desired sensory data generated by any wireless sensor network (WSN) in a fog-based sensor-cloud system transparently. However, the fog nodes and the cloud servers may suffer from many kinds of attacks on the Internet and become semitrusted, which threatens the security of query processing in the system. In this paper, we investigated the problem of secure, fine-grained spatial-temporal Top-k query in fog-based mobile sensor-cloud systems (FMSCSs) and proposed a novel scheme named STQ-SCS to tackle the problem based on the virtual grid construction and the size-order encryption-binding techniques. STQ-SCS can preserve the privacy of the sensed data items and their scores and make end users verify the completeness of the query results of fine-grained spatial-temporal Top-k queries with a 100% successful rate even if the fog nodes and the cloud servers are not totally trustworthy. Besides the good security performance, simulation results indicate that STQ-SCS is also an efficient scheme that incurs a much lower communication cost than the state-of-the-art schemes on securing fine-grained spatial-temporal Top-k query in FMSCSs.


---

## Body

## 1. Introduction

As one important component of Internet of Things (IoT) [1], wireless sensor networks (WSNs) [2] can be used in many application scenarios and are still being studied [3] by many researchers even though extensive research has been carried out on WSNs for the past two decades. However, traditional WSNs are usually single-user centric [4], where a user deploys and owns its own WSN and another party is not able to access the sensed data generated by such a WSN. To remedy this shortcoming, researchers have conceived a new paradigm, namely, the sensor-cloud paradigm [5–7], in recent years. A typical sensor-cloud model is shown in Figure 1(a), where the sensor-cloud architecture serves as the intermediate stratum between the end users and the physical sensor nodes [4]. However, early sensor-cloud architectures are still not perfect, and they encounter many new challenges, such as providing real-times services and efficiently managing the physical sensor nodes. In [8], a new sensor-cloud architecture, namely, the fog-based sensor-cloud framework, was proposed, and the basic model of the fog-based sensor-cloud framework is shown in Figure 1(b). The main difference between early sensor-cloud architectures and the fog-based sensor-cloud framework is that the latter has a fog layer while the former does not have. The fog layer is mainly composed of fog nodes, which can fuse and store the collected sensed data, respond to real-time applications, and efficiently manage the physical sensor nodes [8]. In the fog-based sensor-cloud framework, end users can not only retrieve the sensed data items, which they are interested in directly from the nearby fog nodes, but also obtain the shared sensed data from the cloud by sending queries to the cloud if there are no data which they want in the near fog nodes.Figure 1
The sensor-cloud architecture (generally, there are more than 2 WSNs in real applications, and we just use 2 WSNs as representatives). (a) Common sensor-cloud architecture. (b) Fog-based sensor-cloud architecture.
(a)(b)Although the fog-based sensor-cloud framework brings a lot of benefits as described in [8], it encounters many potential security threats. The fog nodes may be captured by the nearby attackers or may suffer from the attacks arising from the cloud. In other words, the fog nodes may become untrusted [9, 10] under such attacks. Meanwhile, the application servers in the cloud are facing many kinds of attacks, and some of the cloud servers may also not be trustworthy [11–13]. Under this background, how to ensure the integrity and the confidentiality of the sensed data items retrieved by the end users in the fog-based sensor-cloud systems is a thorny-and-burning problem. Such a problem is much more challenging in fog-based mobile sensor-cloud systems (FMSCSs), where the sensor nodes are mobile, considering that the sensed data retrieved by end users must satisfy the spatial-temporal requirements of the queries launched by end users.In this paper, we focus on fine-grained spatial-temporal Top-k queries and make efforts to tackle the abovementioned problem. The concept of fine-grained spatial-temporal Top-k queries is defined in Definition 1 in Section 3. In a word, a fine-grained spatial-temporal Top-k query refers to a query that tries to find out the top k sensed data items generated in a specific time interval and a specific region of a specific WSN deployment field. To our best knowledge, there is no work studying the problem of secure fine-grained spatial-temporal Top-k query in fog-based sensor-cloud systems at present. In brief, the main contributions of this paper are twofold:(i)
It studies the problem of secure fine-grained spatial-temporal Top-k query in FMSCSs and proposes a novel scheme named STQ-SCS to ensure the integrity and confidentiality of the sensed data items retrieved by end users. It provides sound theoretical analysis on the security of STQ-SCS. According to the analysis, STQ-SCS is not only able to preserve the privacy of the sensed data items retrieved by end users but also detect the incomplete query results successfully for fine-grained spatial-temporal Top-k query under the security model presented in this paper.(ii)
Extensive simulations were conducted in the paper, and the results show that STQ-SCS is much more efficient than the related state-of-the-art schemes.The remainder of this paper is organized as follows. Section2 summaries the related schemes; Section 3 describes the system model, the security model, the definitions of some terminologies, and the problem statement; Section 4 presents the proposed scheme STQ-SCS in detail; Section 5 analyzes the security of STQ-SCS; In Section 6, STQ-SCS is compared with the related state-of-the-art schemes through extensive simulations; Section 7 provides performance evaluation. Section 8 concludes this study.


## 2. Related Works

Since there is no work about secure fine-grained spatial-temporal Top-k query in FMSCSs at present, we mainly investigate the related works in Cloud Computing, Two-tiered Wireless Sensor Networks (TWSNs), and Two-tiered Mobile Wireless Sensor Networks (TMWSNs) in this section.


### 2.1. Securing Top-k Queries in Cloud Computing

Top-k queries in the cloud are generally securely processed based on the data that are outsourced on cloud servers by the same data owner. In Cloud Computing, the data owner knows all its outsourced data and thus can construct the encrypted data structure, such as EHL [14], the binary heap [15], or other tree-like structures [16–18], based on the whole data set to facilitate Top-k query without losing data privacy, while in FMSCSs, expect for the fog nodes that are considered as not fully trusted, each sensor node just knows only a small part of the whole data generated by the WSN where it is located, and it thus cannot construct the encrypted data structure of the whole data before outsourcing its data to a fog node or the cloud.Moreover, existing schemes proposed for secure Top-k query in Cloud Computing are based on the strong processing ability and rich resources of the cloud servers, and they never consider the resource-limited sensor nodes which are also weak in computing. Thus, they are not fit for FMSCSs.


### 2.2. Securing Top-k Queries in TWSNs

The study of securing Top-k queries in TWSNs was originally launched by the authors in [19], where three schemes are proposed to preserve the completeness of the Top-k query results in TWSNs. The three schemes were proposed based on the MAC (Message Authentication Code) technique, which requires each sensed data item to be attached with an MAC as its proof data. Then, many other schemes that use a similar technique appeared, such as those in [19–24]. However, the MAC-based technique is relatively less efficient because attaching an MAC to each sensed data item brings large quantity of extra data since a MAC takes almost 40% of the volume of a sensed data item according to [19].Besides the MAC-based technique, some other methods were also proposed to ensure the privacy of the sensed data and the completeness of the Top-k query results in TWSNs, such as inserting digital watermarks or dummy readings into the normal ones [25] and constructing data aggregation trees [26, 27]. However, inserting digital watermarks or dummy readings into the measure data makes it hard and complicated for the users to extract the normal readings from the hybrid ones, and it also brings a lot of redundant data, which further leads to the increase of the communication cost of both the sensor nodes and fog nodes.What is more, one of the most important common points of these schemes is that they are all proposed for TWSNs where nodes are static [28], and they cannot perfectly treat the security threats faced by spatial-temporal Top-k query in FMSCSs, where attackers can launch much more covert attacks. When a mobile sensor node travels from the queried region to other regions or vice versa in the queried time interval, some sensed data generated by the sensor node may be in the queried region, and others may not. Obviously, the sensed data generated out of the queried region by the traveling sensor node are not the qualified ones that satisfy the requirements of the spatial-temporal Top-k query. However, few securing Top-k query schemes proposed in TWSNs consider this, which leaves leaks for the attackers to launch new kinds of covert attacks. For example, the attackers may replace the data items that are generated in the queried region by a sensor node with those produced out of the queried region by the same sensor node.


### 2.3. Securing Top-k Queries in TMWSNs

The first work on securing Top-k queries in TMWSNs was done by Liu et al. in 2015 [29], when they presented a novel network architecture, namely, TMWSNs, and proposed a scheme VTMSN to ensure the completeness of spatial-temporal Top-k query in TMWSNs. The main techniques used in VTMSN are symmetric encryption and information binding. Specifically, it binds the score of each sensed data item with its corresponding generation time, location, and value ranking order by concatenating and encrypting them with the kept symmetric key. Although VTMSN increases the difficulty for the attackers to undermine the completeness of the query results because of the binding relationships, it still has shortcomings. One is that it cannot preserve the privacy of the sensed data items since it leaves the data items disclosed to the fog nodes for ease of Top-k query processing on them; another one is that there should be a large volume of location data transported together with the sensed readings, which greatly increases the communication cost of the sensor nodes and fog nodes.To overcome the latter shortcoming of VTMSN, Wu et al. proposed a scheme named EVTopk [30] in 2016. EVTopk achieves completeness preservation of the Top-k query results by using the HMAC (Hash Message Authentication Code), which is formed by making hashing and encryption operations on the concatenated items including the score, the location, and the neighboring HMAC. However, since each sensed data item should be attached with an HMAC in EVTopk, the HMACs account for a large proportion of the data reports of the sensor nodes and the query results. Moreover, EVTopk is not able to achieve data privacy preservation either. In [31], a comparative study was made on the two schemes, EVTopk and VTMSN. To further decrease the volume of the proof data in the data reports and the query results, in 2018, a scheme named VIP-TQ was proposed to preserve the integrity of the query results for spatial-temporal Top-k query in TMWSNs. In VIP-TQ, sensed data are bound together with their location as well as their neighboring data score using pairwise-key-based encryption. Although the binding can effectively prevent the compromised fog nodes from undermining the integrity of the Top-k query results, it leaves the scores of the sensed data disclosed to the storage nodes, which increases the risk of divulging the privacy of the sensed data. In the same year, Ma et al. proposed two other schemes, namely, SSSTQ1 and SSSTQ2 [32], for securing spatial-temporal Top-k in TMWSNs. However, a large number of original locations associated with the sensed data items are added into the data reports and the query results for integrity verification, which heavily increases the communication cost of the systems.In summary, although there are many schemes related to secure Top-k query in existing works, they either have obvious shortcomings or cannot be used in FMSCS, which motivates us to do further work in this paper.


## 2.1. Securing Top-k Queries in Cloud Computing

Top-k queries in the cloud are generally securely processed based on the data that are outsourced on cloud servers by the same data owner. In Cloud Computing, the data owner knows all its outsourced data and thus can construct the encrypted data structure, such as EHL [14], the binary heap [15], or other tree-like structures [16–18], based on the whole data set to facilitate Top-k query without losing data privacy, while in FMSCSs, expect for the fog nodes that are considered as not fully trusted, each sensor node just knows only a small part of the whole data generated by the WSN where it is located, and it thus cannot construct the encrypted data structure of the whole data before outsourcing its data to a fog node or the cloud.Moreover, existing schemes proposed for secure Top-k query in Cloud Computing are based on the strong processing ability and rich resources of the cloud servers, and they never consider the resource-limited sensor nodes which are also weak in computing. Thus, they are not fit for FMSCSs.


## 2.2. Securing Top-k Queries in TWSNs

The study of securing Top-k queries in TWSNs was originally launched by the authors in [19], where three schemes are proposed to preserve the completeness of the Top-k query results in TWSNs. The three schemes were proposed based on the MAC (Message Authentication Code) technique, which requires each sensed data item to be attached with an MAC as its proof data. Then, many other schemes that use a similar technique appeared, such as those in [19–24]. However, the MAC-based technique is relatively less efficient because attaching an MAC to each sensed data item brings large quantity of extra data since a MAC takes almost 40% of the volume of a sensed data item according to [19].Besides the MAC-based technique, some other methods were also proposed to ensure the privacy of the sensed data and the completeness of the Top-k query results in TWSNs, such as inserting digital watermarks or dummy readings into the normal ones [25] and constructing data aggregation trees [26, 27]. However, inserting digital watermarks or dummy readings into the measure data makes it hard and complicated for the users to extract the normal readings from the hybrid ones, and it also brings a lot of redundant data, which further leads to the increase of the communication cost of both the sensor nodes and fog nodes.What is more, one of the most important common points of these schemes is that they are all proposed for TWSNs where nodes are static [28], and they cannot perfectly treat the security threats faced by spatial-temporal Top-k query in FMSCSs, where attackers can launch much more covert attacks. When a mobile sensor node travels from the queried region to other regions or vice versa in the queried time interval, some sensed data generated by the sensor node may be in the queried region, and others may not. Obviously, the sensed data generated out of the queried region by the traveling sensor node are not the qualified ones that satisfy the requirements of the spatial-temporal Top-k query. However, few securing Top-k query schemes proposed in TWSNs consider this, which leaves leaks for the attackers to launch new kinds of covert attacks. For example, the attackers may replace the data items that are generated in the queried region by a sensor node with those produced out of the queried region by the same sensor node.


## 2.3. Securing Top-k Queries in TMWSNs

The first work on securing Top-k queries in TMWSNs was done by Liu et al. in 2015 [29], when they presented a novel network architecture, namely, TMWSNs, and proposed a scheme VTMSN to ensure the completeness of spatial-temporal Top-k query in TMWSNs. The main techniques used in VTMSN are symmetric encryption and information binding. Specifically, it binds the score of each sensed data item with its corresponding generation time, location, and value ranking order by concatenating and encrypting them with the kept symmetric key. Although VTMSN increases the difficulty for the attackers to undermine the completeness of the query results because of the binding relationships, it still has shortcomings. One is that it cannot preserve the privacy of the sensed data items since it leaves the data items disclosed to the fog nodes for ease of Top-k query processing on them; another one is that there should be a large volume of location data transported together with the sensed readings, which greatly increases the communication cost of the sensor nodes and fog nodes.To overcome the latter shortcoming of VTMSN, Wu et al. proposed a scheme named EVTopk [30] in 2016. EVTopk achieves completeness preservation of the Top-k query results by using the HMAC (Hash Message Authentication Code), which is formed by making hashing and encryption operations on the concatenated items including the score, the location, and the neighboring HMAC. However, since each sensed data item should be attached with an HMAC in EVTopk, the HMACs account for a large proportion of the data reports of the sensor nodes and the query results. Moreover, EVTopk is not able to achieve data privacy preservation either. In [31], a comparative study was made on the two schemes, EVTopk and VTMSN. To further decrease the volume of the proof data in the data reports and the query results, in 2018, a scheme named VIP-TQ was proposed to preserve the integrity of the query results for spatial-temporal Top-k query in TMWSNs. In VIP-TQ, sensed data are bound together with their location as well as their neighboring data score using pairwise-key-based encryption. Although the binding can effectively prevent the compromised fog nodes from undermining the integrity of the Top-k query results, it leaves the scores of the sensed data disclosed to the storage nodes, which increases the risk of divulging the privacy of the sensed data. In the same year, Ma et al. proposed two other schemes, namely, SSSTQ1 and SSSTQ2 [32], for securing spatial-temporal Top-k in TMWSNs. However, a large number of original locations associated with the sensed data items are added into the data reports and the query results for integrity verification, which heavily increases the communication cost of the systems.In summary, although there are many schemes related to secure Top-k query in existing works, they either have obvious shortcomings or cannot be used in FMSCS, which motivates us to do further work in this paper.


## 3. Models, Notations, and Problem Statement

### 3.1. System Model

The system model of FMSCSs is shown in Figure2. In the model, TA is short for trusted authority [33], which is a trustworthy party. TA is used to authenticate the identity of end users and MWSNOs (Mobile Wireless Sensor Network Owners) and distribute the secret keys to them. Each fog node in the fog layer connects and manages one MWSN (Mobile Wireless Sensor Network), and each MWSN is assumed to be composed of N mobile sensor nodes and is owned by a MWSNO. Specifically, the main responsibility of each fog node is as follows: (1) Collecting, processing, and storing the sensed data items updated by the sensor nodes in its corresponding WSN; (2) managing the mobile sensor nodes in its corresponding MWSN; and (3) responding to the queries that may be sent from the Cloud or the end users directly. End users can retrieve the desired data by launching and sending queries to the cloud or the fog nodes directly if they are not far from the fog nodes. If a cloud server receives a query from some end user, it first determines the fog node, which satisfies the region requirement of the query, and then sends the query to the fog node; if a fog node receives a query, it processes the query locally and sends the query result to the party (the cloud or the end user) who has sent the query.Figure 2
System model of FMSCSs.The mobile sensor nodes in WSNs periodically upload their sensed data to the corresponding fog nodes in the fog layer. We divide time into epochs, and take the time length of each epoch as the period for each sensor node to upload its sensed data items. We assume that mobile sensor nodes in each WSN do not move all the time. They stay at some target locations for certain time intervals when they reach the positions, and go on moving to other target locations if it is necessary. Moreover, we assume that the mobile sensor nodes only generate sensed data items when they are staying at their target locations. Besides, it is assumed that each mobile sensor node just moves within the WSN field where it is located, since it will cost a lot of energy for the sensor nodes to move among different WSN-deployed fields.In this paper, we use the setDi,j,1t,Di,j,2t,…,Di,j,μi,jt−1t,Di,j,μi,jtt to denote the sensed data items generated by sensor node Si at its jth target location in the tth epoch Tt, where μi,jt is the total number of the sensed data items generated by Si at its jth target location in Tt. For any sensed data item Di,j,xt, its corresponding data score di,j,xt can be worked out using a public scoring function f∗ [19], namely, di,j,xt=fDi,j,xt. Without loss of generality, we assume different sensed data items have distinct scores [19]. Moreover, in order to facilitate presentation, we assume that the ranking orders of the sensed data items generated by any sensor node at a target location are consistent with their subscript digital numbers. For example, there is Di,j,1t<Di,j,2t<⋯<Di,j,μi,jt−1t<Di,j,μi,jtt, where i and j are the node ID and the target location ID of Si, respectively. The specific meanings of the notations used in this paper are listed in Table 1.Table 1
Notations and their meanings.
NotationsMeaningsSiThe sensor node whose ID isi0<i≤NNTotal number of sensor nodes in one MWSNTtThetth epochλitTotal number of target locations ofSi in TtLoci,jtThejth target location of Si during Ttμi,jtTotal data item numbers ofSi generated at Loci,jt in Ttni,jtTotal number of qualified Top-k data items generated by Si at Loci,jt in TtQtA spatial-temporal Top-k queryRtThe query result ofQtIQtThe ID ofQtIMWSNThe ID of an MWSNQRIMWSNThe queried region in an MWSN whose ID isIMWSNKeyiThe pairwise key which is distributed to sensor nodeSiRTSitThe data report generated bySi in TtEKeyi∗Symmetric encrypting operation withKeyi based on [34]EOPE∗Encrypting operation based on the OPE encryption scheme [35]RSTSitThe processed result ofRTSitΩiTotal number of the queried locations encrypted inRSTSitγi,jtTotal number of the sensed data items encrypted inDPPi,jtRtpkSet of the qualified Top-k data items extracted from Rt


### 3.2. Definitions

In this section, we introduce the definitions of some terminologies used in this paper. Specifically, we define the terminologies used in this paper as follows:(i)
Fine-grained spatial-temporal Top-k query: it is the query which tries to find out the top k sensed data items that have the biggest (or the smallest) scores among all the sensed data items generated in QRIMWSN in Tt, where QRIMWSN is a subregion of the deployment field of the MWSN whose ID is IMWSN. The meta-language of a fine-grained spatial-temporal Top-k query Qt in FMSCSs is shown in the following equation:(1)Qt=IQt,Tt,k,IMWSN,QRIMWSN.(ii)
Queried node and queried location: given a spatial-temporal Top-k query Qt=IQt,Tt,k,IMWSN,QRIMWSN, if a target location of any mobile sensor node falls in QRIMWSN in Tt, the target location is one of the queried locations of Qt; if at least one of the target locations of a mobile sensor node is one of the queried locations of Qt, the sensor node is called a queried node of Qt.(iii)
Qualified Top-k data items: given a spatial-temporal Top-k query Qt=IQt,Tt,k,IMWSN,QRIMWSN, if a sensed data item Dqualifiedt satisfies the following two conditions, it is called the qualified Top-k data item of Qt: (1) Dqualifiedt was generated in QRIMWSN and Tt; (2) among all the sensed data items generated in Tt and Tt, there are at least NQt−k data items whose scores are smaller (or bigger) than the score of Dqualifiedt, where NQt refers to the total number of the sensed data items generated in QRIMWSN and Tt.(iv)
Data-proof PacketDPPi,jt: for any target location Loci,jt0<j≤λit of any mobile sensor node Si1≤i≤N, Data-proof Packet DPPi,jt refers to the subreport produced by Si for the sensed data generated at Loci,jt during Tt. Specifically, DPPi,jt consists of the pairwise-key-encrypted sensed data items and the OPE-encrypted scores (“OPE” is short for “order-preserving encryption” [35]) as well as some proof information generated by Si at Loci,jt during Tt. More specific contents of DPPi,jt will be described in Algorithm 1 in Section 4.Algorithm 1: Secure data preprocessing on Si0<i≤N.
Ensure: target location set Loci,1t,Loci,2t,…,Loci,λit−1t,Loci,λitt; all the sensed data items generated by Si in Tt; the pairwise key Keyi; the master key used for OPE;Require:RTSit;(1)
Compute the score of each sensed data item using the public scoring function;(2)
forj=1 to λitdo(3)
ifμi,jt=0then(4)
SetDPPi,jt to Loci,jt,EKeyi0,Loci,jt;(5)
end if(6)
ifμi,jt=1then(7)
SetDPPi,jt to Loci,jt,EKeyi1,Loci,jt,EKeyidi,j,1t,Loci,jt, EOPEdi,j,1t,EKeyiDi,j,1t,Loci,jt;(8)
end if(9)
ifμi,jt>1then(10)
Sort the sensed data items generated bySi at Loci,jt in Tt according to their scores;(11)
SetDPPi,jt to Loci,jt,EKeyiμi,jt,Loci,jt,EKeyidi,j,1t,Loci,jt,EOPEdi,j,1t,EKeyi1,Di,j,1t, Loci,jt,…,EOPEdi,j,μi,jt−1t,EKeyiμi,jt−1, Di,j,μi,jt−1t,Loci,jt,EOPEdi,j,μi,jtt, EKeyiDi,j,μi,jtt,Loci,jt;(12)
end if(13)
end for(14)
SetRTSit to i,t,Ekeyi,tLoci,1t,Loci,2t,…,, Loci,λit−1t,Loci,λitt,DPPi,1t,DPPi,2t,…,, DPPi,λit−1t,DPPi,λitt(15)
ReturnRTSit.


### 3.3. Security Model

In FMSCSs, fog nodes and the cloud servers are assumed to be untrusted, while most of the mobile sensor nodes and TA are trustworthy. We assume that the untrusted fog nodes and cloud servers are not only curious but also malicious. Specifically, a curious fog node or cloud server will try to disclose the sensed data items as well as the data scores computed based on the public scoring function, and a malicious fog node or cloud server will do its best to undermine the completeness of the results of the fine-grained spatial-temporal Top-k queries. To execute a malicious attack, an untrusted fog node may put none or only part of the qualified top k data items into the Top-k query result, and it may also put some fabricated data items and/or the unqualified-but-real ones into the query result when processing a spatial-temporal Top-k query. For example, suppose the complete query result should be D1t,D2t,D3t. Then, an incomplete query result may be D1t or D1t,D4t,Dfabricatedt, where D4t is a real but unqualified sensed data item and Dfabricatedt is a fabricated data item. An untrusted cloud server may also make some wrong deletions or replacements to undermine the integrity of the query results before it transmits the query results to end users.In our security model, the privacy of the sensed data items, which are generated by the mobile sensor nodes in FMSCSs, and their corresponding scores should be protected. Other information, such as spatial-temporal Top-k query and the generation locations of the sensed data items, will be leaked to fog nodes. It is hard to enable fog nodes to process spatial-temporal Top-k query smoothly and successfully without such leaks. Fortunately, the leaked information brings little threat to the safety of the systems. Moreover, we assume each mobile sensor node is assumed to be equipped with the tamper-proof hardware, with the help of which the adversaries cannot disclose the encryption materials stored in the hardware even if they capture the sensor nodes [24].


### 3.4. Problem Statement and Design Goal

Under the system and the security models described above, the problem tackled in this paper can be presented as follows: how to make the end users in FMSCSs obtain the query results of the fine-grained spatial-temporal Top-k queries launched by them without disclosing the sensor data items and their corresponding scores to the fog nodes and the cloud servers and verify the completeness of the corresponding query result correctly and efficiently. Our design goal is to propose a novel scheme that enables efficient privacy-preservation and integrity-verifiable query processing for fine-grained spatial-temporal Top-k query in FMSCSs. Specifically, three objects as follows should be achieved:(i)
The privacy preservation goal: our proposed scheme should preserve the privacy of the sensed data items and their scores collected from the mobile sensor nodes.(ii)
The integrity verification goal: our proposed scheme should enable end users to verify the completeness of spatial-temporal Top-k query results, no matter what attacking means introduced in the security model are adopted.(iii)
The efficiency goal: our proposed scheme should be effective in communication and computation. It should greatly decrease the additional communication cost of the sensor nodes, since the sensor nodes are energy-limited. Here, the additional communication cost mainly refers to the cost of transmitting the proof data that are used to verify the completeness of the query results.


## 3.1. System Model

The system model of FMSCSs is shown in Figure2. In the model, TA is short for trusted authority [33], which is a trustworthy party. TA is used to authenticate the identity of end users and MWSNOs (Mobile Wireless Sensor Network Owners) and distribute the secret keys to them. Each fog node in the fog layer connects and manages one MWSN (Mobile Wireless Sensor Network), and each MWSN is assumed to be composed of N mobile sensor nodes and is owned by a MWSNO. Specifically, the main responsibility of each fog node is as follows: (1) Collecting, processing, and storing the sensed data items updated by the sensor nodes in its corresponding WSN; (2) managing the mobile sensor nodes in its corresponding MWSN; and (3) responding to the queries that may be sent from the Cloud or the end users directly. End users can retrieve the desired data by launching and sending queries to the cloud or the fog nodes directly if they are not far from the fog nodes. If a cloud server receives a query from some end user, it first determines the fog node, which satisfies the region requirement of the query, and then sends the query to the fog node; if a fog node receives a query, it processes the query locally and sends the query result to the party (the cloud or the end user) who has sent the query.Figure 2
System model of FMSCSs.The mobile sensor nodes in WSNs periodically upload their sensed data to the corresponding fog nodes in the fog layer. We divide time into epochs, and take the time length of each epoch as the period for each sensor node to upload its sensed data items. We assume that mobile sensor nodes in each WSN do not move all the time. They stay at some target locations for certain time intervals when they reach the positions, and go on moving to other target locations if it is necessary. Moreover, we assume that the mobile sensor nodes only generate sensed data items when they are staying at their target locations. Besides, it is assumed that each mobile sensor node just moves within the WSN field where it is located, since it will cost a lot of energy for the sensor nodes to move among different WSN-deployed fields.In this paper, we use the setDi,j,1t,Di,j,2t,…,Di,j,μi,jt−1t,Di,j,μi,jtt to denote the sensed data items generated by sensor node Si at its jth target location in the tth epoch Tt, where μi,jt is the total number of the sensed data items generated by Si at its jth target location in Tt. For any sensed data item Di,j,xt, its corresponding data score di,j,xt can be worked out using a public scoring function f∗ [19], namely, di,j,xt=fDi,j,xt. Without loss of generality, we assume different sensed data items have distinct scores [19]. Moreover, in order to facilitate presentation, we assume that the ranking orders of the sensed data items generated by any sensor node at a target location are consistent with their subscript digital numbers. For example, there is Di,j,1t<Di,j,2t<⋯<Di,j,μi,jt−1t<Di,j,μi,jtt, where i and j are the node ID and the target location ID of Si, respectively. The specific meanings of the notations used in this paper are listed in Table 1.Table 1
Notations and their meanings.
NotationsMeaningsSiThe sensor node whose ID isi0<i≤NNTotal number of sensor nodes in one MWSNTtThetth epochλitTotal number of target locations ofSi in TtLoci,jtThejth target location of Si during Ttμi,jtTotal data item numbers ofSi generated at Loci,jt in Ttni,jtTotal number of qualified Top-k data items generated by Si at Loci,jt in TtQtA spatial-temporal Top-k queryRtThe query result ofQtIQtThe ID ofQtIMWSNThe ID of an MWSNQRIMWSNThe queried region in an MWSN whose ID isIMWSNKeyiThe pairwise key which is distributed to sensor nodeSiRTSitThe data report generated bySi in TtEKeyi∗Symmetric encrypting operation withKeyi based on [34]EOPE∗Encrypting operation based on the OPE encryption scheme [35]RSTSitThe processed result ofRTSitΩiTotal number of the queried locations encrypted inRSTSitγi,jtTotal number of the sensed data items encrypted inDPPi,jtRtpkSet of the qualified Top-k data items extracted from Rt


## 3.2. Definitions

In this section, we introduce the definitions of some terminologies used in this paper. Specifically, we define the terminologies used in this paper as follows:(i)
Fine-grained spatial-temporal Top-k query: it is the query which tries to find out the top k sensed data items that have the biggest (or the smallest) scores among all the sensed data items generated in QRIMWSN in Tt, where QRIMWSN is a subregion of the deployment field of the MWSN whose ID is IMWSN. The meta-language of a fine-grained spatial-temporal Top-k query Qt in FMSCSs is shown in the following equation:(1)Qt=IQt,Tt,k,IMWSN,QRIMWSN.(ii)
Queried node and queried location: given a spatial-temporal Top-k query Qt=IQt,Tt,k,IMWSN,QRIMWSN, if a target location of any mobile sensor node falls in QRIMWSN in Tt, the target location is one of the queried locations of Qt; if at least one of the target locations of a mobile sensor node is one of the queried locations of Qt, the sensor node is called a queried node of Qt.(iii)
Qualified Top-k data items: given a spatial-temporal Top-k query Qt=IQt,Tt,k,IMWSN,QRIMWSN, if a sensed data item Dqualifiedt satisfies the following two conditions, it is called the qualified Top-k data item of Qt: (1) Dqualifiedt was generated in QRIMWSN and Tt; (2) among all the sensed data items generated in Tt and Tt, there are at least NQt−k data items whose scores are smaller (or bigger) than the score of Dqualifiedt, where NQt refers to the total number of the sensed data items generated in QRIMWSN and Tt.(iv)
Data-proof PacketDPPi,jt: for any target location Loci,jt0<j≤λit of any mobile sensor node Si1≤i≤N, Data-proof Packet DPPi,jt refers to the subreport produced by Si for the sensed data generated at Loci,jt during Tt. Specifically, DPPi,jt consists of the pairwise-key-encrypted sensed data items and the OPE-encrypted scores (“OPE” is short for “order-preserving encryption” [35]) as well as some proof information generated by Si at Loci,jt during Tt. More specific contents of DPPi,jt will be described in Algorithm 1 in Section 4.Algorithm 1: Secure data preprocessing on Si0<i≤N.
Ensure: target location set Loci,1t,Loci,2t,…,Loci,λit−1t,Loci,λitt; all the sensed data items generated by Si in Tt; the pairwise key Keyi; the master key used for OPE;Require:RTSit;(1)
Compute the score of each sensed data item using the public scoring function;(2)
forj=1 to λitdo(3)
ifμi,jt=0then(4)
SetDPPi,jt to Loci,jt,EKeyi0,Loci,jt;(5)
end if(6)
ifμi,jt=1then(7)
SetDPPi,jt to Loci,jt,EKeyi1,Loci,jt,EKeyidi,j,1t,Loci,jt, EOPEdi,j,1t,EKeyiDi,j,1t,Loci,jt;(8)
end if(9)
ifμi,jt>1then(10)
Sort the sensed data items generated bySi at Loci,jt in Tt according to their scores;(11)
SetDPPi,jt to Loci,jt,EKeyiμi,jt,Loci,jt,EKeyidi,j,1t,Loci,jt,EOPEdi,j,1t,EKeyi1,Di,j,1t, Loci,jt,…,EOPEdi,j,μi,jt−1t,EKeyiμi,jt−1, Di,j,μi,jt−1t,Loci,jt,EOPEdi,j,μi,jtt, EKeyiDi,j,μi,jtt,Loci,jt;(12)
end if(13)
end for(14)
SetRTSit to i,t,Ekeyi,tLoci,1t,Loci,2t,…,, Loci,λit−1t,Loci,λitt,DPPi,1t,DPPi,2t,…,, DPPi,λit−1t,DPPi,λitt(15)
ReturnRTSit.


## 3.3. Security Model

In FMSCSs, fog nodes and the cloud servers are assumed to be untrusted, while most of the mobile sensor nodes and TA are trustworthy. We assume that the untrusted fog nodes and cloud servers are not only curious but also malicious. Specifically, a curious fog node or cloud server will try to disclose the sensed data items as well as the data scores computed based on the public scoring function, and a malicious fog node or cloud server will do its best to undermine the completeness of the results of the fine-grained spatial-temporal Top-k queries. To execute a malicious attack, an untrusted fog node may put none or only part of the qualified top k data items into the Top-k query result, and it may also put some fabricated data items and/or the unqualified-but-real ones into the query result when processing a spatial-temporal Top-k query. For example, suppose the complete query result should be D1t,D2t,D3t. Then, an incomplete query result may be D1t or D1t,D4t,Dfabricatedt, where D4t is a real but unqualified sensed data item and Dfabricatedt is a fabricated data item. An untrusted cloud server may also make some wrong deletions or replacements to undermine the integrity of the query results before it transmits the query results to end users.In our security model, the privacy of the sensed data items, which are generated by the mobile sensor nodes in FMSCSs, and their corresponding scores should be protected. Other information, such as spatial-temporal Top-k query and the generation locations of the sensed data items, will be leaked to fog nodes. It is hard to enable fog nodes to process spatial-temporal Top-k query smoothly and successfully without such leaks. Fortunately, the leaked information brings little threat to the safety of the systems. Moreover, we assume each mobile sensor node is assumed to be equipped with the tamper-proof hardware, with the help of which the adversaries cannot disclose the encryption materials stored in the hardware even if they capture the sensor nodes [24].


## 3.4. Problem Statement and Design Goal

Under the system and the security models described above, the problem tackled in this paper can be presented as follows: how to make the end users in FMSCSs obtain the query results of the fine-grained spatial-temporal Top-k queries launched by them without disclosing the sensor data items and their corresponding scores to the fog nodes and the cloud servers and verify the completeness of the corresponding query result correctly and efficiently. Our design goal is to propose a novel scheme that enables efficient privacy-preservation and integrity-verifiable query processing for fine-grained spatial-temporal Top-k query in FMSCSs. Specifically, three objects as follows should be achieved:(i)
The privacy preservation goal: our proposed scheme should preserve the privacy of the sensed data items and their scores collected from the mobile sensor nodes.(ii)
The integrity verification goal: our proposed scheme should enable end users to verify the completeness of spatial-temporal Top-k query results, no matter what attacking means introduced in the security model are adopted.(iii)
The efficiency goal: our proposed scheme should be effective in communication and computation. It should greatly decrease the additional communication cost of the sensor nodes, since the sensor nodes are energy-limited. Here, the additional communication cost mainly refers to the cost of transmitting the proof data that are used to verify the completeness of the query results.


## 4. Our Scheme STQ-SCS

This section presents our scheme STQ-SCS. We first make a high-level description of the scheme as follows. At first, each MWSNO obtains the secret keys from TA and preload the keys to its own MWSN. Then, using the secret keys, each sensor node encrypts its own sensed data items and the scores, and uploads the encrypted data items and their scores to the corresponding fog node. If an end user wants to retrieve the query result of a fine-grained spatial-temporal Top-k query, it sends the query to the cloud server or to the fog node directly if it is near the fog node of the target MWSN. If a cloud server receives the query, it first determines which fog node should be the target node of the query, and then sends the query to the target fog node. If the target fog node receives the query, it will work out all the qualified Top-k data items, put them into the query result packet, and send them to the cloud server or to the end user directly if the query is received by the fog node from the end user. If a cloud server receives the query result from the fog node, it will transmit the query result to the end user who is the launcher of the query.As a whole, STQ-SCS can be mainly divided into five parts: (1) secret key distribution; (2) virtual-location construction; (3) secure data preprocessing; (4) secure spatial-temporal Top-k query processing; (5) completeness verification of the query results. In the following sections, the five parts of STQ-SCS are described in great detail.


### 4.1. Secret Key Distribution

In STQ-SCS, all secret keys used in FMSCSs are distributed by TA. To obtain the secret keys, each MWSNO sends a key-request message, which contains its own public key, the ID of its own MWSN, the IDs of the mobile sensor nodes in the MWSN, and some authentication information, to TA. After authenticating the identity of the MWSNO using some existing authentication method such as UAP-BCIoT [36], TA knows whether the MWSNO has the authority to obtain the secret keys or not. If TA determines to send the keys to the MWSNO, TA distributes a master key for the MWSN and a pairwise key for each mobile sensor node in the MWSN, encrypts them using the public key of the MWSNO, and then sends them to the MWSNO. The pairwise keys are generated based on the method in [34], while the master key is generated according to the scheme in [35]. Using the similar way, legal end users can also obtain the keys of each mobile sensor node in any MWSN from TA.In our scheme, two encryption methods are leveraged to encrypt the sensed data items and their scores: one is the latest order preservation encryption (OPE) scheme [35] and the other one is the pairwise-key-based encryption [34]. The former is used to encrypt the scores of the sensed data items using the master keys, while the latter is used to encrypt the sensed data items and the proof data, such as the target locations of the sensor nodes and the ranking orders of the sensed data items, using the pairwise keys. Section 4.3 will describe this in detail.


### 4.2. Construction of the Virtual Grids

In STQ-SCS, the sensor deployment field is divided into many virtual grids. Each virtual grid should be as small as possible so that the central location of the grid can be approximately taken as the location of every point in the grid in real applications. Then, we design an ID distribution law for the virtual grids. Based on the law, the real locations of each mobile sensor node can be worked out easily if the IDs of the virtual grids where it has moved to are known.Specifically, the ID distribution law is described as follows. Suppose the FMSCSs-deployed field is aL∗L square rectangle. STQ-SCS divides the rectangle into η=L/ζ2 small virtual grids, where ζ is a small digital number that can divide the length L with no remainder. Clearly, the smaller ζ is, the larger η is. Then, each virtual grid is given an ID, which is a sequence number ranging from 1 to η. The virtual grids in the first row at the upper side of the rectangle are given the IDs 1, 2, 3, …, L/ζ−1, and L/ζ, respectively, from the left to the right in order; the IDs L/ζ+1, L/ζ+2, …, 2∗L/ζ−1, and 2∗L/ζ are assigned to those in the second row orderly;…; those in the last row have the IDs η−L/ζ+1, η−L/ζ+2, …, η−1, and η, respectively.Using such an ID distribution law, each sensor node first works out the IDs of the virtual grid where it has moved to, and then takes the IDs as the coordinate values of its target locations.


### 4.3. Secure Data Preprocessing

This section describes how each sensor node generates its data report, which will be uploaded to the corresponding fog node at the end of each epoch, based on its own sensed data items under the privacy-and-integrity preservation requirements. Specifically, for any sensor nodeSi0<i≤N, the procedure of data report generation in STQ-SCS is shown in Algorithm 1.In the protocol,Si firstly computes the score of each sensed data item generated by itself based on the public scoring function; then, it works out DPPi,jt0<j≤λit for each of its target locations which it has been moved to during epoch Tt. To do this, three cases are considered: μi,jt=0, μi,jt=1, and μi,jt>1. If μi,jt=0, DPPi,jt should include EKeyi0,Loci,jt to show that no sensed data were generated by Si at Loci,jt in epoch Tt, where EKeyi∗ is a symmetric encrypting operation with Keyi based on [34]; if μi,jt=1, DPPi,jt should contain EKeyi0,Loci,jt to indicate that only one sensed data item was generated by Si at Loci,jt in epoch Tt, and it also needs to include both the pairwise-key-encrypted score and the OPE-encrypted score of the only data item. The former will be used as part of the proof information for integrity verification, and the latter will be used by fog nodes to process spatial-temporal Top-k query smoothly. The only sensed data item should also be encoded using the pairwise key and included in DPPi,jt. If μi,jt>1, the contents of DPPi,jt are a little complex. Specifically, it contains not only the OPE-encrypted scores and the pairwise-key-encrypted data items and scores but also the chaining relationships of the ranked sensed data items. The chaining relationships, which are used to prevent the adversaries from destroying the integrity of the Top-k query results by dropping part of the qualified Top-k data items, are achieved by encrypting each sensed data item together with its ranking order number, which is called the sequence number in the following of this paper, using the pairwise key Keyi. Moreover, each sensed data item is bond together with its corresponding target location to further strengthen the integrity preservation of the Top-k query results. The final output RTSit in Algorithm 1 is the very data report which will be uploaded to the corresponding fog node of Si.


### 4.4. Secure Spatial-Temporal Top-k Query Processing

This section presents how a fine-grained spatial-temporal Top-k query is processed in FMSCSs in our proposed scheme STQ-SCS. When a cloud server receives a fine-grained spatial-temporal Top-k query from an end user, it first finds out the destination of the query according to the mapping relationships between the MWSN IDs and the fog nodes (Information about the mapping relationships is assumed to be stored in the cloud server). Then, the cloud server sends the query to the target fog node. When the target fog node receives the query, it processes the query according to Algorithm 2. After that, it sends the processing result back to the cloud server. If the query is sent from an end user, the fog node will send the query result back to the end user directly.Algorithm 2: Secure spatial-temporal Top-k query processing on the target fog node.
Ensure:RTS1t,RTS2t,…,RTSN−1t,RTSNt; Qt=IQt,Tt,k,IMWSN,QRIMWSN;Require:Rt;(1)
fori=1 to Ndo(2)
ni=0;(3)
forj=1 to λitdo(4)
ifLoci,jt is in QRIMWSNthen(5)
putDPPi,jt into set Θ;(6)
ni=ni+1;(7)
end if(8)
end for(9)
end for(10)
Find out the pairwise-key-encrypted qualified Top-k data items among all the pairwise-key-encrypted data items in set Θ according to their corresponding OPE-encrypted scores;(11)
Calculateni,jt for each i∈1,N and j∈1,λit;(12)
fori=1 to Ndo(13)
ifni=0then(14)
SetRSTSi to i,t,Ekeyi,tLoci,1t,Loci,2t,…,Loci,λt−1t,Loci,λtt(15)
else(16)
forj=1 to nido(17)
ifμi,xjt=0then(18)
SetDPPi,xjt to EKeyi0,Loci,xjt;(19)
end if(20)
ifni,xjt=0,μi,xjt>0then(21)
setDPPi,xjt to EKeyidi,xj,1t,Loci,xjt;(22)
end if(23)
if0<ni,xjt=μi,xjt≤kthen(24)
ifni,xjt=1then(25)
SetDPPi,xjt to EKeyi1,Loci,xjt,EKeyiDi,xj,1t,Loci,xjt;(26)
end if(27)
ifni,xjt>1then(28)
setDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt, EKeyi1,Di,xj,1t,Loci,xjt,…,EKeyiμi,xjt−1,Di,xj,μi,xjt−1t,Loci,xjt, EKeyiDi,xj,μi,xjtt,Loci,xjt;(29)
end if(30)
end if(31)
if0<ni,xjt≤k,μi,xjt>ni,xjtthen(32)
ifμi,xjt=nxi,t+1then(33)
SetDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt,EKeyi1,Di,xj,1t,Loci,xjt,…, EKeyini,xjt,Di,xj,ni,xjtt,Loci,xjt, EKeyiDi,xj,μi,xjtt,Loci,xjt;(34)
end if(35)
ifμi,xjt>ni,xjt+1then(36)
setDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt, EKeyi1,Di,xj,1t,Loci,xjt,…,EKeyini,xjt,Di,xj,ni,xjtt,Loci,xjt,EKeyini,xjt+1,Di,xj,ni,xjt+1t,Loci,xjt;(37)
end if(38)
end if(39)
end for(40)
SetRSTSit to i,t,EKeyiLoci,1t,Loci,2t,…,Loci,λit−1t,Loci,λitt,DPPi,x1t,DPPi,x2t,…,DPPi,xni−1t,DPPi,xnit;(41)
end if(42)
end for(43)
Return setIQt,RSTS1t,RSTS2t,…,RSTSN−1t,RSTSNt.In Algorithm2, the fog node first processes every data report uploaded by the sensor nodes in MWSN IMWSN and then packets all the processing results of the data reports collected in the queried MWSN to form the final query result of the spatial-temporal Top-k query. Specifically, lines 1–9 aim to find out the number of locations that fall in QRIMWSN of each sensor node in MWSN IMWSN and the corresponding Data−proofPackets generated at those locations; from lines 12 to 42, there is a big “for” loop, which is used to process every report generated in MWSN IMWSN in Tt. Line 14 shows the processing result of RTSit considering the case that no target location of Si falls in QRIMWSN in Tt; lines 16–39 describe the procedure of processing RTSit considering the case that there is at least one location of Si that falls in QRIMWSN in Tt. In the abovementioned latter case, all the Data−proofPackets that correspond to the target locations located in QRIMWSN are processed based on the exact values of μi,xjt and/or ni,xjt, where μi,xjt and ni,xjt denote the total data number and the qualified data number, respectively, corresponding to the location Loci,xjt, which is supposed to be in the queried region QRIMWSN. During the procedure of processing the Data−proofPackets, the OPE-encrypted items are all removed from the original Data−proofPackets since the only use of them is to make fog nodes find out the qualified Top-k data items encrypted with the pairwise keys. Moreover, all the unqualified data items except for the one which follows the last qualified Top-k data item in each Data−proofPackets are also removed from each original Data−proofPackets, and the reserved one will be used for completeness verification of the spatial-temporal Top-k query results.


### 4.5. Completeness Verification of the Query Results

The procedure for an end user to verify the completeness of the Top-k query result Rt is presented in Algorithm 3, the output of which is the value of the Boolean variable completeness. If completeness is false, Rt is considered as incomplete; otherwise, Rt is complete and the final Rtpk in Algorithm 3 is composed of all the qualified Top-k data items corresponding to the fine-grained spatial-temporal Top-k query Qt.Algorithm 3: Completeness verification of the query result Rt.
Ensure:Rt=IQt,RSTS1t,RSTS2t,…,RSTSN−1t,RSTSNt; Qt=IQt,Tt,k,IMWSN,QRIMWSN; Key1t,Key2t,…,KeyN−1t,KeyNt.Require:Completeness.(1)
Rtpk=∅; VnonTop=∅; Completeness=true;(2)
fori=1 to Ndo(3)
ifRSTSit∉Rt‖ (RSTSit contains no pairwise-key-encrypted target locations) then(4)
SetCompleteness=false; return Completeness;(5)
end if(6)
Decrypt all the ciphertext inRSTSit with Keyi;(7)
if The end user cannot decrypt the ciphertext normally then(8)
Completeness=false; return Completeness;(9)
end if(10)
Calculate the value ofΩi which is the total number of the queried locations in RSTSit;(11)
forj=1 to Ωido(12)
ifDPPi,xjt is not originally in RSTSitDPPi,xjt is a Data-proof Packet corresponding to Loci,xjt which is in QRIMWSNthen(13)
Completeness=false; return Completeness;(14)
end if(15)
Calculate the value ofγi,xjt which is the total number of the sensed data items in DPPi,xjt;(16)
ifγi,xjt=0then(17)
ifEKeyidi,xj,1t,Loci,xjt is originally in DPPi,xjt in Rtthen(18)
VnonTop=VnonTop∪di,xj,1t;(19)
Continue;(20)
else ifEKeyi0,Loci,xjt is originally in DPPi,xjt in Rtthen(21)
Continue;(22)
else(23)
Completeness=false; return Completeness;(24)
end if(25)
end if(26)
ifγi,xjt=1then(27)
ifDPPi,xjt≠EKeyi1,Loci,xjt,EKeyiDi,xj,1t,Loci,xjtthen(28)
Completeness=false; return Completeness;(29)
end if(30)
Rtpk=Rtpk∪Di,xj,1t;(31)
Continue;(32)
end if(33)
if (ni,xjt is not included in DPPi,xjt in Rt) ‖ (no sensed data item in DPPi,xjt is encrypted with a sequence number) ‖ (the sequence numbers encrypted in DPPi,xjt are not sorted in ascending order from 1) ‖ (any sensed data item encrypted in DPPi,xjt is not originally encrypted with Loci,xjt) ‖ (EKeyiμi,xjt,Loci,xjt is not originally included in DPPi,xjt) then(34)
Completeness=false; return Completeness;(35)
end if(36)
ifni,xjt = γi,xjtthen(37)
ifγi,xjt≠μi,xjtthen(38)
Completeness=false; return Completeness;(39)
else(40)
Rtpk=Rtpk∪Di,xj,1t,Di,xj,2t,…,Di,xj,γi,xjtt;(41)
end if(42)
else ifni,xjt = γi,xjt−1then(43)
if (EKeyiDi,xj,μi,xjtt,Loci,xjt is included in DPPi,xjt) && γi,xjt≠μi,xjtthen(44)
Completeness=false; return Completeness;(45)
end if(46)
Rtpk=Rtpk∪Di,xj,1t,Di,xj,2t,…,Di,xj,ni,xjtt;(47)
VnonTop=VnonTop∪fDi,xj,γi,xjtt;(48)
else(49)
Completeness=false; return Completeness;(50)
end if(51)
end for(52)
end for(53)
ifVnonTop=∅‖SIZERtpk≠kthen(54)
Completeness=false; return Completeness;(55)
end if(56)
iffMINRtpk<MAXVnonTopthen(57)
Completeness=false; return Completeness;(58)
end if(59)
ReturnCompleteness.The main idea of Algorithm3 to verify the completeness of Rt is to find out the minimal data score of the qualified Top-k data items and the maximal score of the unqualified ones generated in the queried region from Rt, and compare them with each other. Normally, the former should be bigger than the latter if the query aims to find out the biggest top k data items. If this condition does not hold in Rt, Rt is considered incomplete. However, it is not correct yet to declare that Rt is complete even if such a condition holds in Rt. Before doing such a comparison, it is necessary to check whether each sensor report was processed properly by the compromised fog node (lines 2–53 in Algorithm 3) based on the proof information included in Rt. To achieve this, each Data−proofPacket in Rt should be checked. When checking the Data−proofPackets, three cases need to be considered, namely, γi,xjt=0 (lines 16–25), γi,xjt=1 (lines 26–32), and γi,xjt>1 (lines 33–51). If γi,xjt=0, either Si did not generate any data items at Loci,xjt in Tt or no data item generated by Si at Loci,xjt in Tt is the qualified Top-k data item. Thus, in such a case, either EKeyidi,xj,1t,Loci,xjt or EKeyi0,Loci,xjt should be originally included in DPPi,xjt in Rt. If γi,xjt=1, the data item included in DPPi,xjt should be a qualified Top-k data item according to lines 24–26 in Algorithm 2. If γi,xjt>1, according to lines 27–38 in Algorithm 2, the fog node must have made some illegal query-processing operations if any of the following cases happens (lines 33–35 in Algorithm 3): (a) ni,xjtis not included in DPPi,xjt in Rt; (b) no sensed data item in DPPi,xjt is encrypted with a sequence number; (c) the sequence numbers encrypted in DPPi,xjt are not sorted in ascending order from 1; (d) any sensed data item encrypted in DPPi,xjt is not originally encrypted with Loci,xjt; and (e) EKeyiμi,xjt,Loci,xjt is not originally included in DPPi,xjt. Moreover, in the case that γi,xjt>1, γi,xjt should be equal to either ni,xjt or ni,xjt+1 according to lines 27–38 in Algorithm 2 where ni,xjt is included in Rt. Thus, in lines 36–50 in Algorithm 3, the abovementioned two cases are considered, respectively, to detect the integrity of Rt.


## 4.1. Secret Key Distribution

In STQ-SCS, all secret keys used in FMSCSs are distributed by TA. To obtain the secret keys, each MWSNO sends a key-request message, which contains its own public key, the ID of its own MWSN, the IDs of the mobile sensor nodes in the MWSN, and some authentication information, to TA. After authenticating the identity of the MWSNO using some existing authentication method such as UAP-BCIoT [36], TA knows whether the MWSNO has the authority to obtain the secret keys or not. If TA determines to send the keys to the MWSNO, TA distributes a master key for the MWSN and a pairwise key for each mobile sensor node in the MWSN, encrypts them using the public key of the MWSNO, and then sends them to the MWSNO. The pairwise keys are generated based on the method in [34], while the master key is generated according to the scheme in [35]. Using the similar way, legal end users can also obtain the keys of each mobile sensor node in any MWSN from TA.In our scheme, two encryption methods are leveraged to encrypt the sensed data items and their scores: one is the latest order preservation encryption (OPE) scheme [35] and the other one is the pairwise-key-based encryption [34]. The former is used to encrypt the scores of the sensed data items using the master keys, while the latter is used to encrypt the sensed data items and the proof data, such as the target locations of the sensor nodes and the ranking orders of the sensed data items, using the pairwise keys. Section 4.3 will describe this in detail.


## 4.2. Construction of the Virtual Grids

In STQ-SCS, the sensor deployment field is divided into many virtual grids. Each virtual grid should be as small as possible so that the central location of the grid can be approximately taken as the location of every point in the grid in real applications. Then, we design an ID distribution law for the virtual grids. Based on the law, the real locations of each mobile sensor node can be worked out easily if the IDs of the virtual grids where it has moved to are known.Specifically, the ID distribution law is described as follows. Suppose the FMSCSs-deployed field is aL∗L square rectangle. STQ-SCS divides the rectangle into η=L/ζ2 small virtual grids, where ζ is a small digital number that can divide the length L with no remainder. Clearly, the smaller ζ is, the larger η is. Then, each virtual grid is given an ID, which is a sequence number ranging from 1 to η. The virtual grids in the first row at the upper side of the rectangle are given the IDs 1, 2, 3, …, L/ζ−1, and L/ζ, respectively, from the left to the right in order; the IDs L/ζ+1, L/ζ+2, …, 2∗L/ζ−1, and 2∗L/ζ are assigned to those in the second row orderly;…; those in the last row have the IDs η−L/ζ+1, η−L/ζ+2, …, η−1, and η, respectively.Using such an ID distribution law, each sensor node first works out the IDs of the virtual grid where it has moved to, and then takes the IDs as the coordinate values of its target locations.


## 4.3. Secure Data Preprocessing

This section describes how each sensor node generates its data report, which will be uploaded to the corresponding fog node at the end of each epoch, based on its own sensed data items under the privacy-and-integrity preservation requirements. Specifically, for any sensor nodeSi0<i≤N, the procedure of data report generation in STQ-SCS is shown in Algorithm 1.In the protocol,Si firstly computes the score of each sensed data item generated by itself based on the public scoring function; then, it works out DPPi,jt0<j≤λit for each of its target locations which it has been moved to during epoch Tt. To do this, three cases are considered: μi,jt=0, μi,jt=1, and μi,jt>1. If μi,jt=0, DPPi,jt should include EKeyi0,Loci,jt to show that no sensed data were generated by Si at Loci,jt in epoch Tt, where EKeyi∗ is a symmetric encrypting operation with Keyi based on [34]; if μi,jt=1, DPPi,jt should contain EKeyi0,Loci,jt to indicate that only one sensed data item was generated by Si at Loci,jt in epoch Tt, and it also needs to include both the pairwise-key-encrypted score and the OPE-encrypted score of the only data item. The former will be used as part of the proof information for integrity verification, and the latter will be used by fog nodes to process spatial-temporal Top-k query smoothly. The only sensed data item should also be encoded using the pairwise key and included in DPPi,jt. If μi,jt>1, the contents of DPPi,jt are a little complex. Specifically, it contains not only the OPE-encrypted scores and the pairwise-key-encrypted data items and scores but also the chaining relationships of the ranked sensed data items. The chaining relationships, which are used to prevent the adversaries from destroying the integrity of the Top-k query results by dropping part of the qualified Top-k data items, are achieved by encrypting each sensed data item together with its ranking order number, which is called the sequence number in the following of this paper, using the pairwise key Keyi. Moreover, each sensed data item is bond together with its corresponding target location to further strengthen the integrity preservation of the Top-k query results. The final output RTSit in Algorithm 1 is the very data report which will be uploaded to the corresponding fog node of Si.


## 4.4. Secure Spatial-Temporal Top-k Query Processing

This section presents how a fine-grained spatial-temporal Top-k query is processed in FMSCSs in our proposed scheme STQ-SCS. When a cloud server receives a fine-grained spatial-temporal Top-k query from an end user, it first finds out the destination of the query according to the mapping relationships between the MWSN IDs and the fog nodes (Information about the mapping relationships is assumed to be stored in the cloud server). Then, the cloud server sends the query to the target fog node. When the target fog node receives the query, it processes the query according to Algorithm 2. After that, it sends the processing result back to the cloud server. If the query is sent from an end user, the fog node will send the query result back to the end user directly.Algorithm 2: Secure spatial-temporal Top-k query processing on the target fog node.
Ensure:RTS1t,RTS2t,…,RTSN−1t,RTSNt; Qt=IQt,Tt,k,IMWSN,QRIMWSN;Require:Rt;(1)
fori=1 to Ndo(2)
ni=0;(3)
forj=1 to λitdo(4)
ifLoci,jt is in QRIMWSNthen(5)
putDPPi,jt into set Θ;(6)
ni=ni+1;(7)
end if(8)
end for(9)
end for(10)
Find out the pairwise-key-encrypted qualified Top-k data items among all the pairwise-key-encrypted data items in set Θ according to their corresponding OPE-encrypted scores;(11)
Calculateni,jt for each i∈1,N and j∈1,λit;(12)
fori=1 to Ndo(13)
ifni=0then(14)
SetRSTSi to i,t,Ekeyi,tLoci,1t,Loci,2t,…,Loci,λt−1t,Loci,λtt(15)
else(16)
forj=1 to nido(17)
ifμi,xjt=0then(18)
SetDPPi,xjt to EKeyi0,Loci,xjt;(19)
end if(20)
ifni,xjt=0,μi,xjt>0then(21)
setDPPi,xjt to EKeyidi,xj,1t,Loci,xjt;(22)
end if(23)
if0<ni,xjt=μi,xjt≤kthen(24)
ifni,xjt=1then(25)
SetDPPi,xjt to EKeyi1,Loci,xjt,EKeyiDi,xj,1t,Loci,xjt;(26)
end if(27)
ifni,xjt>1then(28)
setDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt, EKeyi1,Di,xj,1t,Loci,xjt,…,EKeyiμi,xjt−1,Di,xj,μi,xjt−1t,Loci,xjt, EKeyiDi,xj,μi,xjtt,Loci,xjt;(29)
end if(30)
end if(31)
if0<ni,xjt≤k,μi,xjt>ni,xjtthen(32)
ifμi,xjt=nxi,t+1then(33)
SetDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt,EKeyi1,Di,xj,1t,Loci,xjt,…, EKeyini,xjt,Di,xj,ni,xjtt,Loci,xjt, EKeyiDi,xj,μi,xjtt,Loci,xjt;(34)
end if(35)
ifμi,xjt>ni,xjt+1then(36)
setDPPi,xjt to ni,xjt,EKeyiμi,xjt,Loci,xjt, EKeyi1,Di,xj,1t,Loci,xjt,…,EKeyini,xjt,Di,xj,ni,xjtt,Loci,xjt,EKeyini,xjt+1,Di,xj,ni,xjt+1t,Loci,xjt;(37)
end if(38)
end if(39)
end for(40)
SetRSTSit to i,t,EKeyiLoci,1t,Loci,2t,…,Loci,λit−1t,Loci,λitt,DPPi,x1t,DPPi,x2t,…,DPPi,xni−1t,DPPi,xnit;(41)
end if(42)
end for(43)
Return setIQt,RSTS1t,RSTS2t,…,RSTSN−1t,RSTSNt.In Algorithm2, the fog node first processes every data report uploaded by the sensor nodes in MWSN IMWSN and then packets all the processing results of the data reports collected in the queried MWSN to form the final query result of the spatial-temporal Top-k query. Specifically, lines 1–9 aim to find out the number of locations that fall in QRIMWSN of each sensor node in MWSN IMWSN and the corresponding Data−proofPackets generated at those locations; from lines 12 to 42, there is a big “for” loop, which is used to process every report generated in MWSN IMWSN in Tt. Line 14 shows the processing result of RTSit considering the case that no target location of Si falls in QRIMWSN in Tt; lines 16–39 describe the procedure of processing RTSit considering the case that there is at least one location of Si that falls in QRIMWSN in Tt. In the abovementioned latter case, all the Data−proofPackets that correspond to the target locations located in QRIMWSN are processed based on the exact values of μi,xjt and/or ni,xjt, where μi,xjt and ni,xjt denote the total data number and the qualified data number, respectively, corresponding to the location Loci,xjt, which is supposed to be in the queried region QRIMWSN. During the procedure of processing the Data−proofPackets, the OPE-encrypted items are all removed from the original Data−proofPackets since the only use of them is to make fog nodes find out the qualified Top-k data items encrypted with the pairwise keys. Moreover, all the unqualified data items except for the one which follows the last qualified Top-k data item in each Data−proofPackets are also removed from each original Data−proofPackets, and the reserved one will be used for completeness verification of the spatial-temporal Top-k query results.


## 4.5. Completeness Verification of the Query Results

The procedure for an end user to verify the completeness of the Top-k query result Rt is presented in Algorithm 3, the output of which is the value of the Boolean variable completeness. If completeness is false, Rt is considered as incomplete; otherwise, Rt is complete and the final Rtpk in Algorithm 3 is composed of all the qualified Top-k data items corresponding to the fine-grained spatial-temporal Top-k query Qt.Algorithm 3: Completeness verification of the query result Rt.
Ensure:Rt=IQt,RSTS1t,RSTS2t,…,RSTSN−1t,RSTSNt; Qt=IQt,Tt,k,IMWSN,QRIMWSN; Key1t,Key2t,…,KeyN−1t,KeyNt.Require:Completeness.(1)
Rtpk=∅; VnonTop=∅; Completeness=true;(2)
fori=1 to Ndo(3)
ifRSTSit∉Rt‖ (RSTSit contains no pairwise-key-encrypted target locations) then(4)
SetCompleteness=false; return Completeness;(5)
end if(6)
Decrypt all the ciphertext inRSTSit with Keyi;(7)
if The end user cannot decrypt the ciphertext normally then(8)
Completeness=false; return Completeness;(9)
end if(10)
Calculate the value ofΩi which is the total number of the queried locations in RSTSit;(11)
forj=1 to Ωido(12)
ifDPPi,xjt is not originally in RSTSitDPPi,xjt is a Data-proof Packet corresponding to Loci,xjt which is in QRIMWSNthen(13)
Completeness=false; return Completeness;(14)
end if(15)
Calculate the value ofγi,xjt which is the total number of the sensed data items in DPPi,xjt;(16)
ifγi,xjt=0then(17)
ifEKeyidi,xj,1t,Loci,xjt is originally in DPPi,xjt in Rtthen(18)
VnonTop=VnonTop∪di,xj,1t;(19)
Continue;(20)
else ifEKeyi0,Loci,xjt is originally in DPPi,xjt in Rtthen(21)
Continue;(22)
else(23)
Completeness=false; return Completeness;(24)
end if(25)
end if(26)
ifγi,xjt=1then(27)
ifDPPi,xjt≠EKeyi1,Loci,xjt,EKeyiDi,xj,1t,Loci,xjtthen(28)
Completeness=false; return Completeness;(29)
end if(30)
Rtpk=Rtpk∪Di,xj,1t;(31)
Continue;(32)
end if(33)
if (ni,xjt is not included in DPPi,xjt in Rt) ‖ (no sensed data item in DPPi,xjt is encrypted with a sequence number) ‖ (the sequence numbers encrypted in DPPi,xjt are not sorted in ascending order from 1) ‖ (any sensed data item encrypted in DPPi,xjt is not originally encrypted with Loci,xjt) ‖ (EKeyiμi,xjt,Loci,xjt is not originally included in DPPi,xjt) then(34)
Completeness=false; return Completeness;(35)
end if(36)
ifni,xjt = γi,xjtthen(37)
ifγi,xjt≠μi,xjtthen(38)
Completeness=false; return Completeness;(39)
else(40)
Rtpk=Rtpk∪Di,xj,1t,Di,xj,2t,…,Di,xj,γi,xjtt;(41)
end if(42)
else ifni,xjt = γi,xjt−1then(43)
if (EKeyiDi,xj,μi,xjtt,Loci,xjt is included in DPPi,xjt) && γi,xjt≠μi,xjtthen(44)
Completeness=false; return Completeness;(45)
end if(46)
Rtpk=Rtpk∪Di,xj,1t,Di,xj,2t,…,Di,xj,ni,xjtt;(47)
VnonTop=VnonTop∪fDi,xj,γi,xjtt;(48)
else(49)
Completeness=false; return Completeness;(50)
end if(51)
end for(52)
end for(53)
ifVnonTop=∅‖SIZERtpk≠kthen(54)
Completeness=false; return Completeness;(55)
end if(56)
iffMINRtpk<MAXVnonTopthen(57)
Completeness=false; return Completeness;(58)
end if(59)
ReturnCompleteness.The main idea of Algorithm3 to verify the completeness of Rt is to find out the minimal data score of the qualified Top-k data items and the maximal score of the unqualified ones generated in the queried region from Rt, and compare them with each other. Normally, the former should be bigger than the latter if the query aims to find out the biggest top k data items. If this condition does not hold in Rt, Rt is considered incomplete. However, it is not correct yet to declare that Rt is complete even if such a condition holds in Rt. Before doing such a comparison, it is necessary to check whether each sensor report was processed properly by the compromised fog node (lines 2–53 in Algorithm 3) based on the proof information included in Rt. To achieve this, each Data−proofPacket in Rt should be checked. When checking the Data−proofPackets, three cases need to be considered, namely, γi,xjt=0 (lines 16–25), γi,xjt=1 (lines 26–32), and γi,xjt>1 (lines 33–51). If γi,xjt=0, either Si did not generate any data items at Loci,xjt in Tt or no data item generated by Si at Loci,xjt in Tt is the qualified Top-k data item. Thus, in such a case, either EKeyidi,xj,1t,Loci,xjt or EKeyi0,Loci,xjt should be originally included in DPPi,xjt in Rt. If γi,xjt=1, the data item included in DPPi,xjt should be a qualified Top-k data item according to lines 24–26 in Algorithm 2. If γi,xjt>1, according to lines 27–38 in Algorithm 2, the fog node must have made some illegal query-processing operations if any of the following cases happens (lines 33–35 in Algorithm 3): (a) ni,xjtis not included in DPPi,xjt in Rt; (b) no sensed data item in DPPi,xjt is encrypted with a sequence number; (c) the sequence numbers encrypted in DPPi,xjt are not sorted in ascending order from 1; (d) any sensed data item encrypted in DPPi,xjt is not originally encrypted with Loci,xjt; and (e) EKeyiμi,xjt,Loci,xjt is not originally included in DPPi,xjt. Moreover, in the case that γi,xjt>1, γi,xjt should be equal to either ni,xjt or ni,xjt+1 according to lines 27–38 in Algorithm 2 where ni,xjt is included in Rt. Thus, in lines 36–50 in Algorithm 3, the abovementioned two cases are considered, respectively, to detect the integrity of Rt.


## 5. Security Analysis

### 5.1. Analysis of STQ-SCS on Privacy Preservation

Theorem 1.
Our scheme STQ-SCS is able to preserve the privacy of both the sensed data items and its scores for fine-grained spatial-temporal Top-k query in FMSCSs under the security model presented in this paper.Proof.
According to Algorithm1, before being uploaded to fog nodes, all sensed data items are encrypted with the pairwise keys and all the data scores are encrypted with the master keys [35] by the sensor nodes in FMSCSs. Meanwhile, all the encryption keys should only be obtained from TA after authentication according to the key-distribution method used in STQ-SCS, and the fog nodes and the cloud servers are not able to obtain the keys and thus cannot disclose the values of the sensed data items and their scores. Since the cloud servers and the fog nodes are assumed to be curious and/or malicious while other parties in FMSCSs are assumed to be trustworthy in our security model, the privacy of the sensed data items and their scores can be preserved for fine-grained spatial-temporal Top-k query in FMSCSs using our scheme STQ-SCS.


### 5.2. Analysis of STQ-SCS on Completeness Verification

Theorem 2.
Suppose a queried nodeSi∀i∈1,N generated μi,jtμi,jt>0 data items at a queried location Loci,jt∀j∈1,λit in epoch Tt, where there are ni,jt0<ni,jt≤k qualified Top-k data items. If at least one of those qualified Top-k data items is dropped from DPPi,jt∀i∈1,N,∀j∈1,λit in the query result Rt of Qt=IQt,Tt,k,IMWSN,QRIMWSN by the fog node or the cloud server which generates and/or transmits Rt, the incomplete Rt must be detected by end users with a 100% successful rate based on our scheme STQ-SCS.Proof.
Since the fog node or the cloud server does not knowKeyi, if it inserts the sensed data items that are encrypted with some other keys rather than Keyi into DPPi,jt∀i∈1,N,∀j∈1,λit, the incomplete Rt must be detected by the end user according to lines 6–9 in Algorithm 3. Moreover, according to lines 33–35 in Algorithm 3, Rt must be also considered as incomplete if the fog node or the cloud server puts any encrypted data item, which was generated by Si in Tt at some other location rather than Loci,jt, into DPPi,jt. Thus, in the following of this proof, we need only to consider the situation that all the encrypted sensed data items left in DPPi,jt after being processed by the fog node are the real ones which were generated by Si∀i∈1,N at Loci,jt in Tt (but some or all of them may not be the qualified ones). Then, if at least one qualified sensed data items generated by Si at Loci,jt in Tt is discarded by the fog node or the cloud server, one of the following two cases must appear: (1) the fog node or the cloud server has dropped all the sensed data items from DPPi,jt when producing or transmitting Rt and (2) the fog node or the cloud server has just discarded only a part of the sensed data items from DPPi,jt, and the discarded data items contain some qualified one/ones.
First of all, consider the case that the fog node or the cloud server has deleted all the sensed data items fromDPPi,jt. In this case, the fog node or the cloud server should leave EKeyidi,j,1t,Loci,jt in DPPi,jt in RSTSit of Rt to avoid being detected according to lines 16–25 in Algorithm 3 because it cannot generate the legal encryption item EKeyi0,Loci,jt. Then, di,j,1t should be put into VnonTop according to lines 17–18 in Algorithm 3, and some real but unqualified sensed data items generated in QRIMWSN and Tt must be put into Rtpk to make the number of the elements in Rtpk equal to k according to lines 53–55 in Algorithm 3. If the discarded sensed data items contain some qualified one/ones, di,j,1t must be the score of a qualified Top-k data item. Then, fMINRtpk must be smaller than MAXVnonTop because the score of any qualified Top-k data item must be bigger than that of any real but unqualified one generated in QRIMWSN and Tt assuming all data scores are distinct. Thus, according to lines 56–58 in Algorithm 3, the incomplete Rt must be detected by the end user.
Then, consider the case that the fog node or the cloud server has just deleted a part of the sensed data items fromDPPi,jt, and the deleted data items contain some qualified one/ones. In this case, two situations should be discussed. One is that all the sensed data items encrypted with sequence order numbers are deleted from, while the other is that at least one sensed data item encrypted with a sequence number is left in DPPi,jt after being processed. In the first situation, EKeyiDi,j,μi,jtt,Loci,jt must be left in DPPi,jt after being processed, and there must be DPPi,xjt≠EKeyi1,Loci,jt,EKeyiDi,j,1t,Loci,jt since μi,jt≠1 in this situation and EKeyi1,Loci,jt must not be included in DPPi,jt. According to lines 26–29 in Algorithm 3, the incomplete Rt must be detected by the end user. Then, consider the second situation. To make the sequence numbers encrypted with the sensed data items in DPPi,jt in RSTSit of Rt ascends from 1 orderly (Lines 33–35 in Algorithm 3), the fog node or the cloud server must delete all the sensed data items in one of the sets Φ1,Φ2,Φ3,Φ4, and Φ5 from DPPi,jt. The five sets are shown in equation (2), where 1<w<μi,jt−1.(2)Φ1=Di,j,wt,Di,j,w+1t,…,Di,j,μi,jt−1t,Φ2=Di,j,μi,jt−1t,Φ3=Di,j,wt,Di,j,w+1t,…,Di,j,μi,jtt,Φ4=Di,j,μi,jt−1t,Di,j,μi,jtt,Φ5=Di,j,μi,jtt.
If the fog node or the cloud server discards the sensed data items/item in setΦ1 or Φ2 from DPPi,jt when processing DPPi,jt, EKeyiDi,j,μi,jtt,Loci,jt and EKeyi1,Di,j,1t,Loci,jt must be left in DPPi,jt after being processed, which means that γi,jt is bigger than 1. According to lines 36–50 in Algorithm 3, the fog node has to either set ni,jt to γi,jt or γi,jt−1 in DPPi,jt in RSTSit of Rt to prevent the incomplete Rt from being detected. Even though, the incomplete Rt must also be detected by the end user according to lines 36–38 and 42–45 in Algorithm 3 because γi,jt must not be equal to μi,jt in this case and EKeyiDi,xj,μi,jtt,Loci,jt is included in DPPi,jt at the same time.
If the fog node or the cloud server deletes the sensed data items/item in setΦ3, Φ4, or Φ5 from DPPi,jt, the encryption item EKeyiγi,jt,Di,j,γi,jtt,Loci,jt should be left in DPPi,jt. Then, if γi,jt=1, the incomplete Rt must be detected by the end user according to lines 26–29; if γi,jt>1, since γi,jt≠μi,jt in this case, the fog node or the cloud server has to set ni,jt to γi,jt−1 in DPPi,jt in RSTSit of Rt to make the incomplete Rt free from being detected according to lines 36–50 in Algorithm 3. Then, fDi,j,γi,jtt will be put into set VnonTop according to lines 42–47 in Algorithm 3. Because some dropped sensed data item/items is/are qualified Top-k data item/items, Di,j,γi,jtt must also be a qualified Top-k data item. Since the number of the sensed data items in Rtpk should be k, some real but unqualified Top-k data items whose scores are smaller than fDi,j,γi,jtt must be put into set Rtpk. Thus, there must be fMINRtpk<MAXVnonTop, and the incomplete Rt must be detected by the end user according to lines 56–58 in Algorithm 3.
Thus, if the fog node drops at least one qualified sensed data items fromDPPi,jt, the end user in FMSCSs is able to detect the incomplete Rt with a successful rate of 100% based on STQ-SCS, and Theorem 2 holds.Theorem 3.
Under the security model presented in this paper, any end user in FMSCSs can detect the incomplete query results of fine-grained spatial-temporal Top-k queries with a 100% successful rate based on our scheme STQ-SCS.Proof.
According to the security model, untrusted parties (the fog nodes and the cloud servers) cannot fabricate the pairwise-key-encrypted sensed data items, which cannot be detected by end users, because the untrusted parties cannot obtain the legal pairwise keys. Thus, for any fine-grained spatial-temporal Top-k query Qt, if its query result Rt is incomplete, at least one qualified sensed data item must be discarded by the fog node or the cloud server when producing and/or transmitting Rt. In other words, there must be at least one queried sensor node Si∀i∈1,N whose corresponding Data−proofPacketDPPi,jt at location Loci,jt∀j∈1,λit satisfies the following condition: at least one qualified sensed data item was deleted from DPPi,jt by the fog node or the cloud server when producing and/or transmitting Rt. Then, according to Theorem 2, the incomplete Rt must be detected by the end user in FMSCSs based on our scheme STQ-SCS. Thus, Theorem 3 holds.


## 5.1. Analysis of STQ-SCS on Privacy Preservation

Theorem 1.
Our scheme STQ-SCS is able to preserve the privacy of both the sensed data items and its scores for fine-grained spatial-temporal Top-k query in FMSCSs under the security model presented in this paper.Proof.
According to Algorithm1, before being uploaded to fog nodes, all sensed data items are encrypted with the pairwise keys and all the data scores are encrypted with the master keys [35] by the sensor nodes in FMSCSs. Meanwhile, all the encryption keys should only be obtained from TA after authentication according to the key-distribution method used in STQ-SCS, and the fog nodes and the cloud servers are not able to obtain the keys and thus cannot disclose the values of the sensed data items and their scores. Since the cloud servers and the fog nodes are assumed to be curious and/or malicious while other parties in FMSCSs are assumed to be trustworthy in our security model, the privacy of the sensed data items and their scores can be preserved for fine-grained spatial-temporal Top-k query in FMSCSs using our scheme STQ-SCS.


## 5.2. Analysis of STQ-SCS on Completeness Verification

Theorem 2.
Suppose a queried nodeSi∀i∈1,N generated μi,jtμi,jt>0 data items at a queried location Loci,jt∀j∈1,λit in epoch Tt, where there are ni,jt0<ni,jt≤k qualified Top-k data items. If at least one of those qualified Top-k data items is dropped from DPPi,jt∀i∈1,N,∀j∈1,λit in the query result Rt of Qt=IQt,Tt,k,IMWSN,QRIMWSN by the fog node or the cloud server which generates and/or transmits Rt, the incomplete Rt must be detected by end users with a 100% successful rate based on our scheme STQ-SCS.Proof.
Since the fog node or the cloud server does not knowKeyi, if it inserts the sensed data items that are encrypted with some other keys rather than Keyi into DPPi,jt∀i∈1,N,∀j∈1,λit, the incomplete Rt must be detected by the end user according to lines 6–9 in Algorithm 3. Moreover, according to lines 33–35 in Algorithm 3, Rt must be also considered as incomplete if the fog node or the cloud server puts any encrypted data item, which was generated by Si in Tt at some other location rather than Loci,jt, into DPPi,jt. Thus, in the following of this proof, we need only to consider the situation that all the encrypted sensed data items left in DPPi,jt after being processed by the fog node are the real ones which were generated by Si∀i∈1,N at Loci,jt in Tt (but some or all of them may not be the qualified ones). Then, if at least one qualified sensed data items generated by Si at Loci,jt in Tt is discarded by the fog node or the cloud server, one of the following two cases must appear: (1) the fog node or the cloud server has dropped all the sensed data items from DPPi,jt when producing or transmitting Rt and (2) the fog node or the cloud server has just discarded only a part of the sensed data items from DPPi,jt, and the discarded data items contain some qualified one/ones.
First of all, consider the case that the fog node or the cloud server has deleted all the sensed data items fromDPPi,jt. In this case, the fog node or the cloud server should leave EKeyidi,j,1t,Loci,jt in DPPi,jt in RSTSit of Rt to avoid being detected according to lines 16–25 in Algorithm 3 because it cannot generate the legal encryption item EKeyi0,Loci,jt. Then, di,j,1t should be put into VnonTop according to lines 17–18 in Algorithm 3, and some real but unqualified sensed data items generated in QRIMWSN and Tt must be put into Rtpk to make the number of the elements in Rtpk equal to k according to lines 53–55 in Algorithm 3. If the discarded sensed data items contain some qualified one/ones, di,j,1t must be the score of a qualified Top-k data item. Then, fMINRtpk must be smaller than MAXVnonTop because the score of any qualified Top-k data item must be bigger than that of any real but unqualified one generated in QRIMWSN and Tt assuming all data scores are distinct. Thus, according to lines 56–58 in Algorithm 3, the incomplete Rt must be detected by the end user.
Then, consider the case that the fog node or the cloud server has just deleted a part of the sensed data items fromDPPi,jt, and the deleted data items contain some qualified one/ones. In this case, two situations should be discussed. One is that all the sensed data items encrypted with sequence order numbers are deleted from, while the other is that at least one sensed data item encrypted with a sequence number is left in DPPi,jt after being processed. In the first situation, EKeyiDi,j,μi,jtt,Loci,jt must be left in DPPi,jt after being processed, and there must be DPPi,xjt≠EKeyi1,Loci,jt,EKeyiDi,j,1t,Loci,jt since μi,jt≠1 in this situation and EKeyi1,Loci,jt must not be included in DPPi,jt. According to lines 26–29 in Algorithm 3, the incomplete Rt must be detected by the end user. Then, consider the second situation. To make the sequence numbers encrypted with the sensed data items in DPPi,jt in RSTSit of Rt ascends from 1 orderly (Lines 33–35 in Algorithm 3), the fog node or the cloud server must delete all the sensed data items in one of the sets Φ1,Φ2,Φ3,Φ4, and Φ5 from DPPi,jt. The five sets are shown in equation (2), where 1<w<μi,jt−1.(2)Φ1=Di,j,wt,Di,j,w+1t,…,Di,j,μi,jt−1t,Φ2=Di,j,μi,jt−1t,Φ3=Di,j,wt,Di,j,w+1t,…,Di,j,μi,jtt,Φ4=Di,j,μi,jt−1t,Di,j,μi,jtt,Φ5=Di,j,μi,jtt.
If the fog node or the cloud server discards the sensed data items/item in setΦ1 or Φ2 from DPPi,jt when processing DPPi,jt, EKeyiDi,j,μi,jtt,Loci,jt and EKeyi1,Di,j,1t,Loci,jt must be left in DPPi,jt after being processed, which means that γi,jt is bigger than 1. According to lines 36–50 in Algorithm 3, the fog node has to either set ni,jt to γi,jt or γi,jt−1 in DPPi,jt in RSTSit of Rt to prevent the incomplete Rt from being detected. Even though, the incomplete Rt must also be detected by the end user according to lines 36–38 and 42–45 in Algorithm 3 because γi,jt must not be equal to μi,jt in this case and EKeyiDi,xj,μi,jtt,Loci,jt is included in DPPi,jt at the same time.
If the fog node or the cloud server deletes the sensed data items/item in setΦ3, Φ4, or Φ5 from DPPi,jt, the encryption item EKeyiγi,jt,Di,j,γi,jtt,Loci,jt should be left in DPPi,jt. Then, if γi,jt=1, the incomplete Rt must be detected by the end user according to lines 26–29; if γi,jt>1, since γi,jt≠μi,jt in this case, the fog node or the cloud server has to set ni,jt to γi,jt−1 in DPPi,jt in RSTSit of Rt to make the incomplete Rt free from being detected according to lines 36–50 in Algorithm 3. Then, fDi,j,γi,jtt will be put into set VnonTop according to lines 42–47 in Algorithm 3. Because some dropped sensed data item/items is/are qualified Top-k data item/items, Di,j,γi,jtt must also be a qualified Top-k data item. Since the number of the sensed data items in Rtpk should be k, some real but unqualified Top-k data items whose scores are smaller than fDi,j,γi,jtt must be put into set Rtpk. Thus, there must be fMINRtpk<MAXVnonTop, and the incomplete Rt must be detected by the end user according to lines 56–58 in Algorithm 3.
Thus, if the fog node drops at least one qualified sensed data items fromDPPi,jt, the end user in FMSCSs is able to detect the incomplete Rt with a successful rate of 100% based on STQ-SCS, and Theorem 2 holds.Theorem 3.
Under the security model presented in this paper, any end user in FMSCSs can detect the incomplete query results of fine-grained spatial-temporal Top-k queries with a 100% successful rate based on our scheme STQ-SCS.Proof.
According to the security model, untrusted parties (the fog nodes and the cloud servers) cannot fabricate the pairwise-key-encrypted sensed data items, which cannot be detected by end users, because the untrusted parties cannot obtain the legal pairwise keys. Thus, for any fine-grained spatial-temporal Top-k query Qt, if its query result Rt is incomplete, at least one qualified sensed data item must be discarded by the fog node or the cloud server when producing and/or transmitting Rt. In other words, there must be at least one queried sensor node Si∀i∈1,N whose corresponding Data−proofPacketDPPi,jt at location Loci,jt∀j∈1,λit satisfies the following condition: at least one qualified sensed data item was deleted from DPPi,jt by the fog node or the cloud server when producing and/or transmitting Rt. Then, according to Theorem 2, the incomplete Rt must be detected by the end user in FMSCSs based on our scheme STQ-SCS. Thus, Theorem 3 holds.


## 6. Computation Complexity Analysis

This section analyzes the computation complexity of the three schemes presented above.Firstly, the computation complexity of Algorithm1 is analyzed as follows. Since most of the statements in Algorithm 1 are the loop body of the “for” loop statements in Algorithm 1, the computation complexity of Algorithm 1 should be that the loop numbers multiply the computation complexity of the loop body. In the loop body, there are only three conditional statements. Thus, the computation complexity of the loop body depends on the pairwise-key encryption methods used in STQ-SCS and the total length of the data that need to be encrypted as well as the computation complexity of OPE. Although different pairwise-key cryptography methods, such as [34, 37], may have different computation complexities, they are considered lightweight generally and fit for the resource-limited sensor nodes [38, 39], let alone the fog nodes which are much more powerful than the sensor nodes. Moreover, OPE also has low computation complexity according to [35]. For each DPPi,jt0<i≤N,0<j≤μi,jt, the length of the data that need to be encrypted varies according to μi,jt, which symbolizes the total number of the sensed data items generated by Si at Loci,jt in Tt. Let lD and ld denote the bit length of a sensed data item and that of a data score, respectively, ln symbolizes not only the bit length of a sequence number but also that of μi,jt, lLoc refers to the bit length of a virtual location, and li,jOPE and li,jPW denote the bit length of the data that need to be encrypted using OPE and that of those encoded adopting the pairwise-key encryption method, respectively, in DPPi,jt. Then, the values of li,jOPE and li,jPW can be worked out using equations (3) and (4), respectively, according to Algorithm 1.(3)li,jOPE=0,ifμi,jt=0,ld,ifμi,jt=1,μi,jt×ld,ifμi,jt≥2,(4)li,jPW=ln+lLoc,ifμi,jt=0,ln+ld+lD+3lLoc,ifμi,jt=1,ln+lD+lLocμi,jt+ld+2lLoc,ifμi,jt≥2.Secondly, pay attention to Algorithm2. The computation complexity of lines 1–9 is O∑i=1Nλit; the computation complexity of line 10 depends on the adopted sorting algorithm and the total number of sensed data items generated in Tt and QRIMWSN; that of line 11 is O∑i=1Nλit; that of lines 12–43 in Algorithm 2 is ON in the best case (e.g., ni is always 0 for each i∈1,N) and is O∑i=1Nni in the worst case (e.g., ni is not equal to 0 for each i∈1,N).Finally, it is the turn of Algorithm3, which mainly consists of one outer “for” loop whose loop body contains an inner “for” loop. In the loop body of the outer loop, the computation complexity of line 6 is the highest among all the statements that are in the loop body of the outer loop and out of the inner loop. If decrypting one encryption item EKeyi∗ is taken as one operation, the operation number of line 6 should be ni+1 according to line 40 in Algorithm 2. Then, the computation complexity of Algorithm 3 should be O∑i=1Nni+1+Ωi.


## 7. Performance Evaluation

In this section, we evaluate the performances of our proposed scheme STQ-SCS through extensive simulations taking OMNET++ as the simulation tool.


### 7.1. Metrics and Experimental Setup

The performance of STQ-SCS on energy efficiency is evaluated mainly by testing the additional communication cost, which is brought by transmitting the proof data, because other data such as the sensed data items always need to be transmitted no matter what kind of methods are used to ensure the security of the query. Specifically, the metrics used in our simulations are listed as follows.(i)
Additional communication cost in an MWSNCMWSN: total energy consumed by transmitting all the proof data produced in an MWSN and an epoch to the fog node in the MWSN. Since the sensor nodes are energy-limited, the additional energy cost brought by transmitting the proof data from each MWSN to its corresponding fog node should be given more attention to.(ii)
Proof-data ratioRvs: the ratio of CMWSN to Creports. Here, Creports refers to the total energy consumed by transmitting all the reports generated in an MWSN and an epoch to the fog node connecting to the MWSN, where the data reports include both the sensed data items and the proof data generated by all the sensor nodes in the MWSN and the epoch.The parameters used in our simulation and their own default values are shown in Table2, where the default values of some parameters are set by referencing [19]. In fact, static sensor nodes are also allowed to exist in FMSCSs. In the simulation, we adjust the ratio of the mobile sensor nodes to the total ones in the systems by changing the value of rmobile.Table 2
Default parameter settings.
ParametersDefault valueN300T (length of each epoch)100 sTmobile (period for a sensor node to keep moving)5 sTstatic (period for a sensor node to keep static)5 smspeed (moving speed of each mobile sensor node)5 m/srmobile (ratio of the mobile sensor nodes to the total ones)100%MWSNsize (size of the deployment field of each MWSN)400×400 m2R (communication radius of each sensor node)50 mrD (data generation rate of each sensor node)2 item(s)qperiod (period for the end user to launch a query)5 sqradius (radius of the queried region which is a circle)50 mlD (length of a sensed data item)400 bitsld (length of a data score)20 bitsln (length of a sequence number)10 bitslid (length of an ID number)10 bitslt (length of a time data)32 bitslLoc (length of each two-dimensional location)128 bitslVLoc (length of each virtual location)16 bitsesend (cost of sending one bit data)1 mJereceive (cost of receiving one bit data)1 mJ


### 7.2. Simulation Results

This section presents the simulation results ofCMWSN and Rvs with different settings of rD, N, and rmobile, respectively. We compare our scheme with VTMSN [29] and SSSTQ1 [32] in this section. VTMSN, which was proposed in 2015, is the earliest work on securing spatial-temporal Top-k query in FMSCSs, while SSSTQ1 can be considered as the state-of-the-art scheme proposed for securing spatial-temporal Top-k query in FMSCSs. Figure 3 shows the simulation results of CMWSN under different settings of rD, N, and rmobile, and Figure 4 illustrates the simulation results of Rvs with different settings of rD, N, and rmobile, respectively. From Figure 3, we can see that the CMWSN lines of STQ-SCS are all lower than those of VTMSN and SSSTQ1. This indicates that our proposed scheme STQ-SCS is more energy-efficient than the other two schemes. The CMWSN lines in Figures 3(a) and 3(b) are on an upward trend because the quantity of sensed data items rises as rD or N becomes larger and larger, which causes the increase of the proof data, while those in Figure 3(c) are on a downward trend as rmobile rises from 0 to 1 because the sensor nodes are assumed to generate sensed data items only when they are static or arrive at their target locations and the quantity of the sensed data items and the corresponding proof data must decrease when more sensor nodes are set to be mobile.Figure 3
CMWSN with different settings of rD (a), N (b), and rmobile (c).
(a)(b)(c)Figure 4
Rvs with different settings of rD (a), N (b), and rmobile (c).
(a)(b)(c)Thanks to the technology of virtual-location construction proposed in this paper, fewer bits of location information are included in the proof data in STQ-SCS than the other two schemes, which decrease the ratio of the proof data to the whole data including both sensed data items and their proof. From Figure4, we can see that the values of Rvs of STQ-SCS are all under 12% which is within the acceptable range in real applications and also lower than those of the other two schemes.


## 7.1. Metrics and Experimental Setup

The performance of STQ-SCS on energy efficiency is evaluated mainly by testing the additional communication cost, which is brought by transmitting the proof data, because other data such as the sensed data items always need to be transmitted no matter what kind of methods are used to ensure the security of the query. Specifically, the metrics used in our simulations are listed as follows.(i)
Additional communication cost in an MWSNCMWSN: total energy consumed by transmitting all the proof data produced in an MWSN and an epoch to the fog node in the MWSN. Since the sensor nodes are energy-limited, the additional energy cost brought by transmitting the proof data from each MWSN to its corresponding fog node should be given more attention to.(ii)
Proof-data ratioRvs: the ratio of CMWSN to Creports. Here, Creports refers to the total energy consumed by transmitting all the reports generated in an MWSN and an epoch to the fog node connecting to the MWSN, where the data reports include both the sensed data items and the proof data generated by all the sensor nodes in the MWSN and the epoch.The parameters used in our simulation and their own default values are shown in Table2, where the default values of some parameters are set by referencing [19]. In fact, static sensor nodes are also allowed to exist in FMSCSs. In the simulation, we adjust the ratio of the mobile sensor nodes to the total ones in the systems by changing the value of rmobile.Table 2
Default parameter settings.
ParametersDefault valueN300T (length of each epoch)100 sTmobile (period for a sensor node to keep moving)5 sTstatic (period for a sensor node to keep static)5 smspeed (moving speed of each mobile sensor node)5 m/srmobile (ratio of the mobile sensor nodes to the total ones)100%MWSNsize (size of the deployment field of each MWSN)400×400 m2R (communication radius of each sensor node)50 mrD (data generation rate of each sensor node)2 item(s)qperiod (period for the end user to launch a query)5 sqradius (radius of the queried region which is a circle)50 mlD (length of a sensed data item)400 bitsld (length of a data score)20 bitsln (length of a sequence number)10 bitslid (length of an ID number)10 bitslt (length of a time data)32 bitslLoc (length of each two-dimensional location)128 bitslVLoc (length of each virtual location)16 bitsesend (cost of sending one bit data)1 mJereceive (cost of receiving one bit data)1 mJ


## 7.2. Simulation Results

This section presents the simulation results ofCMWSN and Rvs with different settings of rD, N, and rmobile, respectively. We compare our scheme with VTMSN [29] and SSSTQ1 [32] in this section. VTMSN, which was proposed in 2015, is the earliest work on securing spatial-temporal Top-k query in FMSCSs, while SSSTQ1 can be considered as the state-of-the-art scheme proposed for securing spatial-temporal Top-k query in FMSCSs. Figure 3 shows the simulation results of CMWSN under different settings of rD, N, and rmobile, and Figure 4 illustrates the simulation results of Rvs with different settings of rD, N, and rmobile, respectively. From Figure 3, we can see that the CMWSN lines of STQ-SCS are all lower than those of VTMSN and SSSTQ1. This indicates that our proposed scheme STQ-SCS is more energy-efficient than the other two schemes. The CMWSN lines in Figures 3(a) and 3(b) are on an upward trend because the quantity of sensed data items rises as rD or N becomes larger and larger, which causes the increase of the proof data, while those in Figure 3(c) are on a downward trend as rmobile rises from 0 to 1 because the sensor nodes are assumed to generate sensed data items only when they are static or arrive at their target locations and the quantity of the sensed data items and the corresponding proof data must decrease when more sensor nodes are set to be mobile.Figure 3
CMWSN with different settings of rD (a), N (b), and rmobile (c).
(a)(b)(c)Figure 4
Rvs with different settings of rD (a), N (b), and rmobile (c).
(a)(b)(c)Thanks to the technology of virtual-location construction proposed in this paper, fewer bits of location information are included in the proof data in STQ-SCS than the other two schemes, which decrease the ratio of the proof data to the whole data including both sensed data items and their proof. From Figure4, we can see that the values of Rvs of STQ-SCS are all under 12% which is within the acceptable range in real applications and also lower than those of the other two schemes.


## 8. Conclusions

This paper presents a privacy-preservation and integrity-verification scheme named STQ-SCS for fine-grained spatial-temporal Top-k query in FMSCSs. Thorough security analysis shows that STQ-SCS can make the end users in FMSCSs obtain the query results of fine-grained spatial-temporal Top-k queries without disclosing the privacy of both the sensed data items and their scores, considering that the fog nodes and the cloud servers are not trustworthy. Meanwhile, the security analysis also shows that, under the security model described in this paper, the end users in FMSCSs can detect the incomplete Top-k query results with a 100% successful rate based on our scheme STQ-SCS. Simulation results demonstrate that STQ-SCS is much more efficient than the related state-of-the-art schemes, and can be well used in FMSCSs in real applications.



---

*Source: 9939796-2021-05-29.xml*