Verifiable Top- k Query Processing in Tiered Mobile Sensor Networks

Abstract

Verifiable top-k query processing in tiered sensor networks, which refers to verifying the authenticity and the completeness of top-k query results received by the network owner in tiered sensor networks, has received attention in very recent years. However, the existing solutions of this problem are only fit for static sensor network. In this paper, we try to solve the problem in a tiered mobile sensor network model, where not only static sensor nodes but also mobile sensor nodes existed. Based on the tiered mobile sensor network model, we propose a novel verifiable scheme named VTMSN for fine-grained top-k queries. The main idea of VTMSN is as follows: it maps each of the positions where sensor nodes are in a static state to a virtual node and then establishes relationships among data items of each virtual node with their score orders, which are encrypted along with the scores of the data items and the time epochs using the distinct symmetric keys kept by each sensor node and the network owner. Both theory analysis and simulation results show the efficiency and the security of VTMSN.

1. Introduction

More and more attention has been paid to two-tiered sensor networks in recent years [1–3]. A two-tiered sensor network, which is shown in Figure 1, consists of a lot of resource constrained sensor nodes at the lower level and some master nodes with relatively abundant resource at the upper level. The main tasks of the sensor nodes are to monitor the surroundings and generate sensing data, while the main tasks of the master nodes are to collect the sensing data from the sensor nodes and answer queries from the network owner. This two-tiered architecture is known to improve the scalability and capacity of the sensor networks. Besides, it is also able to reduce system complexity and prolong the network lifetime [3].

Figure 1

A traditional tiered sensor network model.

In this paper, we present a new sensor network model named TMSN (tired mobile sensor network) based on the two-tiered network architecture, which is shown in Figure 2. The difference between TMSN and the traditional two-tiered sensor network model is that mobile sensor nodes existed at the lower level of TMSN while all sensor nodes are static in the latter case. There are many advantages when mobile sensor nodes are introduced into the two-tiered network architecture. As an example, moving some of the mobile sensor nodes to heavy traffic regions can help balance the energy consumption of the sensor nodes at the lower level of TMSN. Another example is target coverage [4]. Some of targets in a tiered sensor network may lose coverage because of the early death of some sensor nodes or bad initial deployment of the sensor nodes. If some mobile sensor nodes exist, they can move to the position where dead nodes are located or to some other places by well designing [5].

Figure 2

A tired mobile sensor network (TMSN) model.

Top-k query is an important kind of queries in sensor networks. To obtain the top k data items from all the data items generated by the sensor nodes in the interested region, the network owner first sends a top-k query to each of the master nodes whose cells are intersected with the interested region. Each of the master nodes processes the top-k query locally and finds out the top-k query result in the intersected region in its own cell. Then the master nodes send their own query results to the network owner. Finally, the network owner finds out the final top-k query result according to the data received from the master nodes.

Nowadays, the security of top-k queries in tired sensor networks is under threat. If the master nodes are compromised, they may tamper the query results and return incomplete and/or false top-k query results to the network owner. Moreover, although introducing mobile sensor nodes into tiered sensor network architecture can bring many advantages, it also brings some challenges. One of the challenges is that the data items generated by the same sensor node may be generated at different locations, and the compromised master node may take place the data items generated in the query region with the data items generated by the same sensor node in other places. This is hard to be detected using the existing security verification method in tired sensor networks.

To verify the authentication and the completeness of the top-k query results received by the network owner in TMSN, we propose a novel verification scheme, which is called VTMSN. We assume that each sensor node in TMSN has two states: a mobile state and a static state, and they only generate sensing data when they are in a static state. The main technique of VTMSN is that it maps each of the positions where mobile sensor nodes are in a static state to a virtual static node. Thus, a mobile sensor node becomes one or many static sensor node/nodes for a given time interval. Then, with some modifications, schemes used in static tired sensor networks to verify the authentication and the completeness of the top-k query results received by the network owner can be used in TMSN.

In summary, the main contributions of this paper are listed as follows:

• (i)

We present a new sensor network model named TMSN based on the two-tiered network architecture, where mobile sensor nodes are introduced into the lower tier of the architecture.

(ii)

We investigate the problem of verifiable fine-grained top-k queries in TMSN for the first time and propose an effective verification scheme called VTMSN to verify the authentication and the completeness of the top-k query results.

(iii)

Theory analysis and extensive experiment have been conducted to show the efficiency and feasibility of our scheme VTMSN.

The rest of this paper is organized as follows. Section 2 presents the related work; Section 3 presents the network and attack models; Section 4 presents the notations, some definitions, and the problem statement; in Section 5, we provide the novel verification scheme VTMSN as well as the analysis of its detection probability and energy efficiency; the simulation results and their analysis are given in Section 6; Section 7 makes a conclusion.

2. Related Work

Many schemes and protocols are developed to secure query processing in two-tiered sensor networks. Some of them are proposed for range queries [6]. Range queries ask for data within one or multiple attributes falling into specified ranges, and they are different from top-k queries, which aim at finding k data items with peak values among all the data items generated in the query region. Some other papers focus on the problem of securing top-k queries [3, 7–10]. Zhang et al. [3] proposed three schemes, which are the closest work to ours, to solve the problem of verifiable fine-grained top-k queries in two-tiered sensor networks. All of them are only fit for static tiered sensor networks, because it is assumed that the network owner knows the mapping between sensor node IDs and their respective geographic locations. This assumption can not hold in TMSN because of the mobile sensor nodes.

There are also some works for mobile sensor networks or for mobile target detection in sensor networks [11]. Good schemes [4, 12, 13] are proposed to solve many kinds of coverage problems in mobile sensor networks; [14–17] are dedicated in localization in mobile sensor networks; routing protocols are studied in mobile sensor networks in [18–20]; an efficient framework for in-network data replication and acquisition in mobile sensor networks are proposed in [21]. In [22], mobility management of mobile sensors was discussed for the purposes of forming a better wireless sensor network. In [23], low cost data gathering using mobile hybrid sensor networks is achieved. In [24], a group-based discovery mechanism was proposed to reduce the discovery delay in low-duty-cycle mobile sensor networks. To the best of our knowledge, no work has been done considering mobile sensor nodes in tiered sensor networks at present.

3. Network and Attack Models

3.1. TMSN Model

Similar to the traditional tiered sensor networks, TMSN also contains two levels. At the lower level, there are a lot of resource-constrained sensor nodes, which are deployed into many cells. At the upper level, there are some master nodes with relatively abundant resource, each of which is responsible for one cell of sensor nodes at the lower level. We assume that time is divided into epochs, which is the same with [3]. At the end of each epoch, each sensor node sends all of its data generated during the epoch to its corresponding master node. After collecting the data from sensor nodes, master nodes can answer top-k queries from the external network owner. The network owner can communicate with some of the master nodes via an on-demand wireless (e.g., satellite) link, which is relatively low-rate. We assume that each sensor node communicates with its neighboring sensor nodes with short-range radios while master nodes can communicate with their neighboring master nodes through relatively high-rate, long-range radios.

The significant difference between TMSN and the traditional tiered sensor networks is that mobile sensor nodes existed in TMSN while all sensor nodes are static in the latter case. The manner of mobility for a sensor node can be divided into two kinds: controllable mobility and uncontrollable mobility. In this paper, we assume the mobility behaviors of sensor nodes are controllable. Specifically, we assume that each sensor node only moves in its own cell. The sensor nodes do not always move because their energy is limited. They will stop moving and monitor the surroundings to meet the demand of applications. When a sensor node stops at some place, the first thing it does is to estimate its position. We assume that some localization techniques in mobile sensor networks such as [14–17] are adopted to help the sensor nodes estimate their current locations. Thus, each sensor node in TMSN has two states: a mobile state and a static state. We assume that all sensor nodes generate sensing data only when they are in a static state, and we consider it a reasonable assumption because data items often need to be bound up with the locations where they are generated. Besides, we assume that all mobile sensor nodes will stop moving at the end of each epoch and assist other sensor nodes to route their data to the corresponding master nodes in the cell.

3.2. Adversary Model

Our attack model is similar as [3]. Specifically, we assume that both master nodes and sensor nodes can be compromised, and the sensor nodes that are not compromised are the majority. Adversaries may insert forged data to query results and/or return incomplete query results to the network owner through the compromised master nodes. We do not require the confidentiality of the top-k query results as in [3], but we do require the authenticity and completeness of top-k results. Because each master node in TMSN is in charge of one cell and each sensor node corresponds to one master node, an attacker who wants to break the authenticity and/or completeness of top-k query results in one cell can not get help from the compromised nodes in other cells. Thus we only focus on a cell C consisting of N sensor nodes, which are denoted by ${\{S_i\}}_{i=\mathrm{1}}^N$ , and one compromised master node $\mathcal{M}$ in this paper.

4. Definitions, Notations, and Problem Statement

In this section, we present some definitions and important notations used throughout the paper as well as the problem investigated in this paper.

4.1. Definitions and Notations

We first list some definitions used in this paper as follows.

Definition 1 (virtual node).

A virtual node is a position where a real sensor node is in a static state, and it only exists in the epoch/epochs when the sensor node is in a static state at the position.

Definition 2 (mother node and child node).

A mother node is a real sensor node, and the child nodes of the mother node are virtual nodes generated by the same mother node.

Definition 3 (queried sensor node).

If at least one child node of a sensor node is in the query region of a top-k query during the interested time epoch, the sensor node is called queried sensor node for the query.

Definition 4 (qualified and unqualified data item).

If a data item is among the top k data items generated in the query region of a top-k query during the interested time epoch, the data item is qualified for the query. Otherwise it is unqualified for the query.

Definition 5 (qualified and unqualified virtual node).

If at least one qualified data item is generated on a virtual node for a top-k query, the virtual node is called a qualified virtual node for the query. Otherwise it is called an unqualified virtual node for the query.

Now we present the notations used in this paper. Assume that, during epoch t, each node $S_i\in {\{S_i\}}_{i=\mathrm{1}}^N$ generates ${\lambda }_i^t$ virtual nodes, which are denoted by $\mathrm{V}\mathrm{N}{\mathrm{D}}_i={\{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\}}_{j=\mathrm{1}}^{{\lambda }_i^t}$ , and ${\mu }_i^j$ data items denoted by $D_i^j=\{D_{i,h}^j{\}}_{h=\mathrm{1}}^{{\mu }_i^j}$ are generated on each virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{V}\mathrm{N}{\mathrm{D}}_i$ . Each data item $D_{i,h}^j\in D_i^j$ can be scored by some public scoring functions, such as the one in [25]. Let $f(·)$ denote a good public scoring function and let $d_{i,h}^j$ denote the score of $D_{i,h}^j$ . Then we have $d_{i,h}^j=f(D_{i,h}^j)$ . In [3], if a data item is smaller than or equal to another data item, the score of the former data item is also smaller than or equal to the score of the latter data item. In this paper, we release this assumption and just assume that different data items have different data scores. $\mathcal{W}$ in this paper denotes the network owner. ${\mathcal{I}}_t={\{i\}}_{i=1}^N$ is used to denote the ID set of all the sensor nodes in cell C, and $\mathcal{V}{\mathcal{I}}_t^i={\{(i,j)\}}_{j=\mathrm{1}}^{{\lambda }_i^t}$ denotes the ID set of the child nodes of sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ).

We use $Q_t=〈C,t,k,QR〉$ to denote a primitive top-k query in TMSN, where C denotes a cell ID, t is the epoch number, k is the desired number of data items with peak values, and $QR$ is the query region. We use ${\mathcal{R}}_{Qt}$ to denote the query result of $Q_t$ . In this paper, we only pay attention to the primitive queries, because more complicated queries can be decomposed into multiple primitive ones easily.

4.2. Problem Statement

In this subsection, we present the problem and some metrics that we use to evaluate the performance of the verification scheme proposed in this paper.

Given a query $Q_t=〈C,t,k,QR〉$ , the problem we are interested in this paper is how to verify the authenticity and completeness of ${\mathcal{R}}_{Qt}$ in TMSN, where the authenticity of ${\mathcal{R}}_{Qt}$ means that all data items in ${\mathcal{R}}_{Qt}$ are indeed generated on virtual nodes in $QR$ during epoch t, and the completeness of ${\mathcal{R}}_{Qt}$ means that ${\mathcal{R}}_{Qt}$ indeed contains the top k data items among all the candidates.

One of the performance metrics used in this paper is $P_{\mathrm{d}\mathrm{e}\mathrm{t}}$ , which denotes the probability that an incomplete and/or forged top-k query result is detected [3]. Maximizing the lifetime of sensor networks is an important target for many protocols in sensor networks [26, 27]. Generally speaking, communication consumes most of the energy. If the communication cost is decreased, the lifetime of the sensor networks can increase significantly. Thus, the performance metrics used in this paper also include the following.

(i) $C_{v\mathit{\text{-}}sm}$ : In-Cell Communication Cost. It is the energy consumption in bits incurred by transmitting and receiving the verification information generated by the sensor nodes in cell C per epoch. We also assume that the energy consumption of transmitting and receiving every bit across each hop is the same as [3].

(ii) $C_{v\mathit{\text{-}}mw}$ : Query Communication Cost. It is the energy consumption in bits incurred by sending and receiving the verification information between $\mathcal{M}$ and $\mathcal{W}$ to reply to a top-k query. It may need to travel multiple master nodes and the on-demand wireless link for $\mathcal{M}$ to connect $\mathcal{W}$ . For simplicity, we consider the route connecting $\mathcal{M}$ to $\mathcal{W}$ a virtual hop. The energy consumption of transmitting one bit across a virtual hop is different from that between neighboring sensor nodes.

(iii) $R_{vs}$ : Ratio of Cost. It is the ratio of the cost of transmitting and receiving verification information to that of transmitting and receiving data items, which are not verification information.

5. Verifiable Top-k Queries in TMSN

In this section, we first propose a novel scheme named VTMSN for verifiable top-k queries in TMSN. For clarity, we ignore compromised sensor nodes temporarily in Section 5.1. Then $P_{\mathrm{d}\mathrm{e}\mathrm{t}}$ , $C_{v\mathit{\text{-}}sm}$ , and $C_{v\mathit{\text{-}}mw}$ are analyzed in Section 5.2. Finally, the impact of compromised sensor nodes is discussed in Section 5.3.

5.1. VTMSN: A Novel Verification Scheme in TMSN

VTMSN enables completeness verification by establishing relationships between every two ordered neighboring data items of each virtual node with their orders, which are encrypted along with the time epoch numbers and the virtual node IDs by the symmetric keys shared by sensor nodes and the network owner $\mathcal{W}$ . For each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ), we assume that a distinct symmetric key $K_i$ between $S_i$ and $\mathcal{W}$ is preloaded on it. To achieve forward-secure authenticity, $K_i$ can be epoch-based as in [7–9]. VTMSN enables authenticity verification by taking the scores of data items encrypted with the distinct keys as the verification information. Recall that different data items have different data scores, each of which is very short in length. Thus, if we create verification information by encrypting the scores, it can not only make the authenticity of top-k query results verifiable but also shrink the amount of verification information. Specifically, VTMSN includes the following four stages.

5.1.1. Data Preparation

At the end of each epoch, each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ) prepares the data generated during the epoch and some necessary verification information, which will be sent to the master node $\mathcal{M}$ . Let ${\mathrm{I}\mathrm{N}\mathrm{F}\mathrm{O}}_i^j$ denote the information that $S_i$ prepares for its child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , let $\mathrm{l}\mathrm{o}{\mathrm{c}}_i^j$ denote the location of virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , and let $E_{Ki}\{\ast \}$ denote the encryption operation with key $K_i$ . Then, according to different values of ${\mu }_i^j$ , the content of ${\mathrm{I}\mathrm{N}\mathrm{F}\mathrm{O}}_i^j$ is also different, and it is shown as follows:

• (i)

if ${\mu }_i^j=\mathrm{0}$ ,

$$\begin{array}{cc}& {\mathrm{I}\mathrm{N}\mathrm{F}\mathrm{O}}_i^j=〈\mathrm{l}\mathrm{o}{\mathrm{c}}_i^j,E_{Ki}\left\{t\parallel j\right\}〉;\end{array}$$

(1)

(ii)

if ${\mu }_i^j\ne 0$ ,

$$\begin{array}{cc}& {\mathrm{I}\mathrm{N}\mathrm{F}\mathrm{O}}_i^j=〈\mathrm{l}\mathrm{o}{\mathrm{c}}_i^j,E_{Ki}\left\{{\mu }_i^j\parallel t\parallel j\right\},D_{i,\mathrm{1}}^j,E_{Ki}\left\{\mathrm{1}\parallel t\parallel d_{i,\mathrm{1}}^j\parallel j\right\},D_{i,\mathrm{2}}^j,E_{Ki}\left\{\mathrm{2}\parallel t\parallel d_{i,\mathrm{2}}^j\parallel j\right\},\dots ,D_{i,{\mu }_i^j-\mathrm{1}}^j,E_{Ki}\left\{\left({\mu }_i^j-\mathrm{1}\right)\parallel t\parallel d_{i,{\mu }_i^j-\mathrm{1}}^j\parallel j\right\},D_{i,{\mu }_i^j}^j,E_{Ki}\left\{{\mu }_i^j\parallel t\parallel d_{i,{\mu }_i^j}^j\parallel j\right\}〉,\end{array}$$

(2)

where term $E_{Ki}\{{\mu }_i^j\parallel t\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^j\}$ is needed for verification when ${\mu }_i^j<k$ and all data items of $S_i$ are qualified data items. It is used to determine whether the data are dropped by the master node $\mathcal{M}$ or not in such a case.

5.1.2. Data Submission

After preparing the information for each virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ) sends a message, which includes the information prepared for each child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ ( $\forall \mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{V}\mathrm{N}{\mathrm{D}}_i$ ) of node $S_i$ , to master $\mathcal{M}$ . Specifically, the message is as follows:

$$\begin{array}{cc}& S_i⟶\mathcal{M}\text{:}〈i,E_{Ki}\left\{t\parallel 1\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{1}}\parallel 2\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{2}}\parallel \cdots \parallel {\lambda }_i^t\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{{\lambda }_i^t}\right\},\mathrm{I}\mathrm{N}\mathrm{F}{\mathrm{O}}_i^{\mathrm{1}},\mathrm{I}\mathrm{N}\mathrm{F}{\mathrm{O}}_i^{\mathrm{2}},\dots ,\mathrm{I}\mathrm{N}\mathrm{F}{\mathrm{O}}_i^{{\lambda }_i^t}〉.\end{array}$$

(3)

When the message is received by $\mathcal{M}$ , the data items and verification information included in the message will be stored on $\mathcal{M}$ .

5.1.3. Query Processing

When a top-k query primitive $Q_t=〈C,t,k,{QR}_t〉$ is received by the master node $\mathcal{M}$ in cell C, $\mathcal{M}$ first locates the top k data items among all data items generated in $Q{R}_t$ during epoch t and then sends them along with some verification information to $\mathcal{W}$ . Suppose that there are totally m queried sensor nodes which are denoted as $\mathrm{Q}\mathrm{S}{\mathrm{N}}_t={\{S_{x_a}\}}_{a=\mathrm{1}}^m$ for $Q_t$ , and each sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ has ${\omega }_i^t$ child nodes which are denoted as $\mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t={\{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{y_b}\}}_{b=\mathrm{1}}^{{\omega }_i^t}$ in $Q{R}_t$ during epoch t, where the combination $(i,y_b)$ is the ID of the virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{y_b}$ . Let $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ denote the information included in the query result for child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t$ of sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ and let $n_i^j$ denote the number of qualified data items generated by $S_i$ on virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t$ during epoch t. Then, the content of $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ is as follows:

• (i)

If $n_i^j={\mu }_i^j=0$ ,

$$\begin{array}{cc}& \mathrm{R}\mathrm{S}{\mathrm{T}}_i^j=〈E_{Ki}\left\{t\parallel j\right\}〉.\end{array}$$

(4)

(ii)

If $n_i^j=0$ , ${\mu }_i^j>0$ ,

$$\begin{array}{cc}& \mathrm{R}\mathrm{S}{\mathrm{T}}_i^j=〈E_{Ki}\left\{\mathrm{1}\parallel t\parallel d_{i,\mathrm{1}}^j\parallel j\right\}〉.\end{array}$$

(5)

(iii)

If $0<n_i^j={\mu }_i^j<k$ ,

$$\begin{array}{cc}& \mathrm{R}\mathrm{S}{\mathrm{T}}_i^j=〈E_{Ki}\left\{{\mu }_i^j\parallel t\parallel j\right\},D_{i,\mathrm{1}}^j,E_{Ki}\left\{\mathrm{1}\parallel t\parallel d_{i,\mathrm{1}}^j\parallel j\right\},D_{i,\mathrm{2}}^j,E_{Ki}\left\{\mathrm{2}\parallel t\parallel d_{i,\mathrm{2}}^j\parallel j\right\},\dots ,D_{i,{\mu }_i^j-\mathrm{1}}^j,E_{Ki}\left\{\left({\mu }_i^j-\mathrm{1}\right)\parallel t\parallel d_{i,{\mu }_i^j-\mathrm{1}}^j\parallel j\right\},D_{i,{\mu }_i^j}^j,E_{Ki}\left\{{\mu }_i^j\parallel t\parallel d_{i,{\mu }_i^j}^j\parallel j\right\}〉.\end{array}$$

(6)

(iv)

If $n_i^j=k$ and ${\mu }_i^j\ge k$ ,

$$\begin{array}{cc}& \mathrm{R}\mathrm{S}{\mathrm{T}}_i^j=〈D_{i,\mathrm{1}}^j,E_{Ki}\left\{\mathrm{1}\parallel t\parallel d_{i,\mathrm{1}}^j\parallel j\right\},D_{i,\mathrm{2}}^j,E_{Ki}\left\{\mathrm{2}\parallel t\parallel d_{i,\mathrm{2}}^j\parallel j\right\},\dots ,D_{i,k-\mathrm{1}}^j,E_{Ki}\left\{\left(k-\mathrm{1}\right)\parallel t\parallel d_{i,k-\mathrm{1}}^j\parallel j\right\},D_{i,k}^j,E_{Ki}\left\{k\parallel t\parallel d_{i,k}^j\parallel j\right\}〉.\end{array}$$

(7)

(v)

If $0<n_i^j<k$ and ${\mu }_i^j>n_i^j$ ,

$$\begin{array}{cc}& \mathrm{R}\mathrm{S}{\mathrm{T}}_i^j=〈D_{i,\mathrm{1}}^j,E_{Ki}\left\{\mathrm{1}\parallel t\parallel d_{i,\mathrm{1}}^j\parallel j\right\},D_{i,\mathrm{2}}^j,E_{Ki}\left\{\mathrm{2}\parallel t\parallel d_{i,\mathrm{2}}^j\parallel j\right\},\dots ,D_{i,n_i^j-\mathrm{1}}^j,E_{Ki}\left\{\left(n_i^j-\mathrm{1}\right)\parallel t\parallel d_{i,n_i^j-\mathrm{1}}^j\parallel j\right\},D_{i,n_i^j}^j,E_{Ki}\left\{n_i^j\parallel t\parallel d_{i,n_i^j}^j\parallel j\right\},E_{Ki}\left\{\left(n_i^j+\mathrm{1}\right)\parallel t\parallel d_{i,n_i^j+\mathrm{1}}^j\parallel j\right\}〉.\end{array}$$

(8)

After $\mathcal{M}$ prepares $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ for each child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t$ of each sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ , $\mathcal{M}$ checks whether it has answered a query whose interested time epoch is the same as that of $Q_t$ . If $\mathcal{M}$ has not answered such a query, it returns the following information for each $S_i$ , $\forall i\in {\mathcal{I}}_t$ :

• (i)

  If $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ , the information is

  $$\begin{array}{cc}& \mathcal{M}⟶\mathcal{W}\text{:}〈i,E_{Ki}\left\{t\parallel \mathrm{1}\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{1}}\parallel \mathrm{2}\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{2}}\parallel \cdots \parallel {\lambda }_i^t\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{{\lambda }_i^t}\right\},{\left\{\mathrm{R}\mathrm{S}{\mathrm{T}}_i^{y_b}\right\}}_{b=\mathrm{1}}^{{\omega }_i^t}〉,\end{array}$$

  (9)

•  

  where $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^{y_b}$ denotes the information included in the query result for child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{y_b}\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t$ of sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ .

• (ii)

  If $S_i\notin \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ , the information is

  $$\begin{array}{cc}& \mathcal{M}⟶\mathcal{W}\text{:}〈i,\hspace{0.17em}\hspace{0.17em}{E}_{Ki}\left\{t\parallel \mathrm{1}\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{1}}\parallel \mathrm{2}\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{2}}\parallel \cdots \parallel {\lambda }_i^t\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{{\lambda }_i^t}\right\}〉.\end{array}$$

  (10)

If $\mathcal{M}$ has answered a top-k query whose interested time epoch is the same as that of $Q_t$ , it does not need to return the location information for virtual nodes formed during epoch t, because the network owner can find this information from the history query records. Thus, $\mathcal{M}$ only needs to return the following information to $\mathcal{W}$ for each $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ in this case:

$$\begin{array}{cc}& \mathcal{M}⟶\mathcal{W}\text{:}〈i,\hspace{0.17em}\hspace{0.17em}{\left\{\mathrm{R}\mathrm{S}{\mathrm{T}}_i^{y_b}\right\}}_{b=\mathrm{1}}^{{\omega }_i^t}〉.\end{array}$$

(11)

In fact, the amount of information in ${\mathcal{R}}_{Qt}$ can be further shrunk when $Q_t$ is not the first top-k query whose interested time epoch is t. As an example, if $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ is in $Q{R}_t$ and it has no qualified data item for query $Q_t$ , ${\mathcal{R}}_{Qt}$ should include term $E_{Ki}\{t\parallel j\}$ . However, if the same case has appeared for a former query whose interested time epoch is also t, term $E_{Ki}\{t\parallel j\}$ does not need to be included in ${\mathcal{R}}_{Qt}$ because it has been sent to the network owner before.

5.1.4. Verification

When receiving a top-k query result ${\mathcal{R}}_{Qt}$ , the network owner checks the authenticity of ${\mathcal{R}}_{Qt}$ in the following way. For each data item $D_{i,h}^j$ in ${\mathcal{R}}_{Qt}$ , the network owner decrypts term $E_{Ki}\{h\parallel t\parallel d_{i,h}^j\parallel j\}$ following $D_{i,h}^j$ in ${\mathcal{R}}_{Qt}$ and checks whether $d_{i,h}^j$ got from term $E_{Ki}\{h\parallel t\parallel d_{i,h}^j\parallel j\}$ is equal to $f(D_{i,h}^j)$ , where $f(\ast )$ is a public scoring function [4]. If they are equal, data items in ${\mathcal{R}}_{Qt}$ are authentic; otherwise they are not. The principle is that different data items have different scores [3], and if a compromised master node modifies $D_{i,h}^j$ , it should also modify $d_{i,h}^j$ in term $E_{Ki}\{h\parallel t\parallel d_{i,h}^j\parallel j\}$ . However, it can not do this because it does not know the key $K_i$ .

Completeness verification of ${\mathcal{R}}_{Qt}$ is a little complicated. The first step to verify the completeness of ${\mathcal{R}}_{Qt}$ is to check whether each sensor node $S_i$ in cell C has sent term $E_{Ki}\{t\parallel 1\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{1}}\parallel 2\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{\mathrm{2}}\parallel \cdots \parallel {\lambda }_i^t\parallel \mathrm{l}\mathrm{o}{\mathrm{c}}_i^{{\lambda }_i^t}\}$ to the network owner. If any sensor node has not sent it, ${\mathcal{R}}_{Qt}$ is considered incomplete. The second step is to check whether term $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ for each child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^j$ of each sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ has been sent to the network owner. If at least one of them has not been sent to the network owner, ${\mathcal{R}}_{Qt}$ is considered incomplete. The last step is to verify the completeness of each $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ in ${\mathcal{R}}_{Qt}$ . If they are all verified to be complete, ${\mathcal{R}}_{Qt}$ is considered complete; otherwise it is not. Details of completeness verification of each $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ are given in Algorithm 1, where $d_{\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{t}}$ is the smallest data score in ${\mathcal{R}}_{Qt}$ .

Algorithm 1: Completeness verification of ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$ .

Input: top-k query $Q_t=〈C,t,k,{QR}_t〉$ , ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$ , $d_{\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{t}}$

Output: completeness

(1) completeness = true

(2) if  ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$   includes  ${\gamma }_i^j$ ( ${\gamma }_i^j$ ≠ 0) data items denoted by  ${{\left\{\right.D}_{i,h}^j\left.\right\}}_{h=\mathrm{1}}^{{\gamma }_i^j}\hspace{0.17em}\left\{\right.$

(3)   Decrypt each term $E_{Ki}\left\{\right.h\parallel t\parallel d_{i,h}^j\parallel j\left.\right\}$ following each data item $D_{i,h}^j\in {{\left\{\right.D}_{i,h}^j\left.\right\}}_{h=\mathrm{1}}^{{\gamma }_i^j}$ with $K_i$

(4)  if (the orders got from each term $E_{Ki}\left\{\right.h\parallel t\parallel d_{i,h}^j\parallel j\left.\right\}$ are not consecutive from 1 to  ${\gamma }_i^j$ )

(5)     $\left\{completeness=false\right\}$

(6)  if term $E_{Ki}\left\{\right.{\mu }_i^j\parallel t\parallel j\left.\right\}$   is in  ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j\hspace{0.17em}\left\{\right.$

(7)   if ${\mu }_i^j$ ≠ ${\gamma }_i^j\hspace{0.17em}\hspace{0.17em}\left\{completeness=false\right\}$

(8)  }else{

   if term $E_{Ki}\left\{\right.({\gamma }_i^j+1)\parallel t\parallel d_{i,{\gamma }_i^j+1}^j\parallel j\left.\right\}$   is in  ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j\hspace{0.17em}\left\{\right.$

(9)   if  $d_{i,{\gamma }_i^j+\mathrm{1}}^j\ge d_{\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{t}}\hspace{0.17em}\hspace{0.17em}\left\{completeness=false\right\}$

(10)     }else{ if  ${\gamma }_i^j\ne k\hspace{0.17em}\hspace{0.17em}\left\{completeness=false\right\}$

(11)     }

(12)  }

(13) }else if no  data item is in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j\hspace{0.17em}\left\{\right.$

(14)   if (both term $E_{Ki}\left\{\right.t\parallel j\left.\right\}$ and $E_{Ki}\left\{\right.1\parallel t\parallel d_{i,1}^j\parallel j\left.\right\}$   are not in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$ ) or

     (( $E_{Ki}\left\{\right.1\parallel t\parallel d_{i,1}^j\parallel j\left.\right\}$   is in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$ ) and ( $d_{i,\mathrm{1}}^j\ge d_{\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{t}}$ ))

(15)      {completeness = false}

(16) }

(17) if  (not all the encrypted terms in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$   can be decrypted by the same symmetric key) or

  (not all the values of j in the encrypted terms in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$ are the same) or (at least one time epoch

  number in the encrypted terms in ${\mathrm{R}\mathrm{S}{\mathrm{T}}_i}^j$   is not equal to t)

(18)    $\left\{compleeness=false\right\}$

(19) return completeness.

In Algorithm 1, lines (1)–(16) can verify the completeness of $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ under the condition that the data items and their corresponding verification information in $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ are not replaced by those of other virtual nodes. Lines (17)-(18) are added to tear off this constraint condition.

5.2. Performance Analysis of VTMSN

Theorem 6.

As long as none of the queried sensor nodes is compromised, a compromised master node can not insert forged data into query results without being detected by VTMSN.

Proof.

This theorem is actually proved in the verification stage in Section 4.1.

Theorem 7.

As long as none of the queried sensor nodes is compromised, a compromised master node can not replace data items generated during the interested time epoch with data items generated in some other time epochs without being detected by VTMSN.

Proof.

Each encrypted term in top-k query results contains an epoch number t in VTMSN. Thus, it is easy to detect such behaviors by checking the time epoch numbers in the encrypted terms.

Theorem 8.

As long as none of the queried sensor nodes is compromised, a compromised master node can not replace qualified data items with unqualified data items generated during the same epoch without being detected by VTMSN.

Proof.

It is clear that the corresponding verification information should also be replaced if some data items are replaced. Then, the following two propositions prove that Theorem 8 holds.

• (1)

The compromised master node can not replace qualified data items with unqualified data items of the same virtual node without being detected by VTMSN. This is because the orders in the encrypted terms following the data items will not be consecutive if such behavior is made.

(2)

The compromised master node can not replace qualified data items with unqualified data items of some other virtual nodes without being detected by VTMSN. The verification information of a virtual node in the query region can not be totally replaced with those of another virtual node because each virtual node in the query region is asked to include its verification information in the query result. Besides, if some qualified data items of a virtual node are replaced with unqualified data items of some other virtual nodes, either the encrypted terms for the same virtual node in the query result can not be decrypted by the same key or the values of j got from each encrypted term following each data item of the same virtual node in the query result are not the same. According to Algorithm 1, both cases can be detected by VTMSN.

Theorem 9.

As long as none of the queried sensor nodes is compromised, VTMSN can detect any incomplete top-k query result with probability $P_{det}=1$ .

Proof.

There are totally two methods for $\mathcal{M}$ to break the completeness of top-k query results. The first method is to replace the qualified data items with some unqualified data items, and the second method is to drop part or all of the qualified data items without replacing them with unqualified data items. According to Theorems 7 and 8, it can be detected with $P_{\mathrm{d}\mathrm{e}\mathrm{t}}=1$ if $\mathcal{M}$ adopts the first method. Then we prove that it can also be detected by VTMSN with probability $P_{\mathrm{d}\mathrm{e}\mathrm{t}}=1$ if $\mathcal{M}$ adopts the second method. For each qualified virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , if $\mathcal{M}$ drops part of the qualified data items of $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , $\mathcal{M}$ must drop all the last ${\sigma }_i^j$ ( $0<{\sigma }_i^j<n_i^j$ ) qualified data items and all the unqualified data items of $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ in order to make the orders of the left data items consecutive. Then term $E_{Ki}\{{\mu }_i^j\parallel t\parallel j\}$ or $E_{Ki}\{\chi \parallel t\parallel d_{i,\chi }^j\parallel j\}$ must be left in the query result, where $\chi =n_i^j-{\sigma }_i^j+1$ ; otherwise $\mathrm{R}\mathrm{S}{\mathrm{T}}_i^j$ will be considered incomplete according to Algorithm 1. If term $E_{Ki}\{{\mu }_i^j\parallel t\parallel j\}$ is left in the query result, ${\mu }_i^j$ got from $E_{Ki}\{{\mu }_i^j\parallel t\parallel j\}$ must not be equal to the number of data items of $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ left in the query result. If term $E_{Ki}\{\chi \parallel t\parallel d_{i,\chi }^j\parallel j\}$ is left in the query result, $d_{i,\chi }^j$ got from term $E_{Ki}\{\chi \parallel t\parallel d_{i,\chi }^j\parallel j\}$ must be not smaller than the smallest data score of the data items in the query result. According to Algorithm 1, the query result can be considered incomplete in both cases. If $\mathcal{M}$ drops all qualified data items of $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ , the incomplete query result can also be detected because $\mathcal{M}$ can not generate a legal term $E_{Ki}\{t\parallel j\}$ or $E_{Ki}\{1\parallel t\parallel d_{i,1}^j\parallel j\}$ without knowing $K_i$ . Thus, any incomplete query result can be detected as long as none of the queried sensor nodes is compromised.

Next, we will analyze the in-cell communication cost $C_{v\text{-}sm}$ of VTMSN. Note that all information in the message sent from each sensor node to $\mathcal{M}$ is the verification information except data items. In this paper, we assume that the length of the data after they are encrypted is the same as that before they are encrypted. We use ${\zeta }_i^t$ to denote the number of child nodes, which have data items in epoch t, of each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ). Then the number of child nodes, which do not have data items in epoch t, of sensor node $S_i$ is ${\lambda }_i^t-{\zeta }_i^t$ . The meanings of some other parameters are listed in Table 1.

Table 1

Parameters and their meanings.

Para.	Meaning
$$l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}$$	Length in bits of an order number
$$l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}$$	Length in bits of an epoch number
$$l_{\mathrm{l}\mathrm{o}\mathrm{c}}$$	Length in bits of each location
$$l_{\mathrm{i}\mathrm{d}}$$	Length in bits of an ID number
$$l_{\mathrm{n}\mathrm{u}\mathrm{m}}$$	Length in bits of number of data items
$$l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}$$	Length in bits of a data score

For a child node, which does not have data item in time epoch t, of sensor node $S_i$ , the length of verification information per epoch in bits is

$$\begin{array}{cc}& L_i^{\lambda -\zeta }=l_{\mathrm{l}\mathrm{o}\mathrm{c}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{i}\mathrm{d}}.\end{array}$$

(12)

Let $T_{\mathrm{a}\mathrm{v}\mathrm{g}}$ denote the average time for a sensor node to be in a static state per epoch and let $f_d$ denote the average data generating frequency of each sensor node. The average number of data items that are generated on a child node in one epoch is

$$\begin{array}{cc}& \mu =f_d\ast T_{\mathrm{a}\mathrm{v}\mathrm{g}}.\end{array}$$

(13)

Then, for a child node that has data items in time epoch t of sensor node $S_i$ , the length of verification information in bits per epoch is

$$\begin{array}{cc}& L_i^{\zeta }=l_{\mathrm{l}\mathrm{o}\mathrm{c}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{n}\mathrm{u}\mathrm{m}}+\mu \ast \left(l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}+l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}\right).\end{array}$$

(14)

For each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ), it also has to take some locations and IDs of its child nodes as the verification information. Thus, the length of verification information prepared by each sensor node $S_i$ ( $\forall i\in {\mathcal{I}}_t$ ) in bits per epoch is

$$\begin{array}{cc}& L_{S_i}=l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+{\lambda }_i^t\ast \left(l_{\mathrm{l}\mathrm{o}\mathrm{c}}+l_{\mathrm{i}\mathrm{d}}\right)+\left({\lambda }_i^t-{\zeta }_i^t\right)\ast L_i^{\lambda -\zeta }+{\zeta }_i^t\ast L_i^{\zeta }.\end{array}$$

(15)

Let $h_i$ denote the hop counts from $S_i$ to $\mathcal{M}$ along the shortest path at the end of epoch t. Then the in-cell communication cost $C_{v\text{-}sm}^{S_i}$ in bits incurred by sending the verification information generated by $S_i$ to $\mathcal{M}$ is

$$\begin{array}{cc}& C_{v\text{-}sm}^{S_i}=L_{S_i}\ast h_i.\end{array}$$

(16)

Then we have

$$\begin{array}{cc}& C_{v\text{-}sm}={\displaystyle \sum }_{i=\mathrm{1}}^N\mathrm{2}\ast C_{v\text{-}sm}^{S_i}.\end{array}$$

(17)

In this paper, we assume that the energy consumption incurred by sending and receiving one bit of data is the same as in [3]. So in formula (17), the total energy consumption is doubled.

Suppose that a query $Q_t=〈C,t,k,Q{R}_t〉$ is received by $\mathcal{M}$ . We then derive the query communication cost $C_{v\mathit{\text{-}}mw}$ incurred by VTMSN. First, the query communication cost in bits incurred by sending the verification information from $\mathcal{M}$ to $\mathcal{W}$ for each virtual node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ that is located in $Q{R}_t$ is

$$\begin{array}{cc}& C_{v\text{-}sm}^{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j}=\left\{\begin{array}{cc}{l}_{\mathrm{i}\mathrm{d}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}\hfill & \left(n_i^j={\mu }_i^j=\mathrm{0}\right)\hfill \\ l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}\hfill & \left(n_i^j=\mathrm{0},\hspace{0.17em}\hspace{0.17em}{\mu }_i^j>\mathrm{0}\right)\hfill \\ l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{n}\mathrm{u}\mathrm{m}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+{\mu }_i^j\left(l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}+l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}+l_{\mathrm{i}\mathrm{d}}\right)\hfill & \left(\mathrm{0}<n_i^j={\mu }_i^j<k\right)\hfill \\ k\left(l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}+l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}+l_{\mathrm{i}\mathrm{d}}\right)\hfill & \left(n_i^j=k\right)\hfill \\ \left(n_i^j+\mathrm{1}\right)\left(l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}+l_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}+l_{\mathrm{i}\mathrm{d}}\right)\hfill & \left(\mathrm{1}\le n_i^j<k,\hspace{0.17em}\hspace{0.17em}{\mu }_i^j>n_i^j\right),\hfill \end{array}\right.\end{array}$$

(18)

where ${\mu }_i^j$ is the total number of data items generated by sensor node $S_i$ on its child node $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^j$ during time epoch t and $n_i^j$ is the number of qualified data items among the ${\mu }_i^j$ data items.

Let $C_{v\text{-}mw}^{S_i}$ denote query communication cost in bits incurred by sending the verification information generated by $S_i$ from $\mathcal{M}$ to $\mathcal{W}$ . Then, if $\mathcal{M}$ has not answered a top-k query whose interested time epoch is the same as that of $Q_t$ , the following two cases should be considered.

• (i)

The first case is that $S_i$ is not a queried sensor node; then

$$\begin{array}{cc}& C_{v\text{-}mw}^{S_i}=l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+{\lambda }_i^t\ast \left(l_{\mathrm{l}\mathrm{o}\mathrm{c}}+l_{\mathrm{i}\mathrm{d}}\right).\end{array}$$

(19)

(ii)

The second case is that $S_i$ has ${\omega }_i^t$ ( ${\omega }_i^t\ne 0$ ) child nodes located in $Q{R}_t$ ; then we have

$$\begin{array}{cc}& C_{v\text{-}mw}^{S_i}=l_{\mathrm{i}\mathrm{d}}+l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}+{\lambda }_i^t\ast \left(l_{\mathrm{l}\mathrm{o}\mathrm{c}}+l_{\mathrm{i}\mathrm{d}}\right)+{\displaystyle \sum }_{a=\mathrm{1}}^{{\omega }_i^t}{C}_{v\text{-}sm}^{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{x_a}},\end{array}$$

(20)

where $C_{v\text{-}sm}^{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{x_a}}$ is the query cost for $\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{x_a}\in \mathrm{Q}\mathrm{V}{\mathrm{N}}_i^t$ and ${\omega }_i^t$ is the number of child nodes of sensor node $S_i\in \mathrm{Q}\mathrm{S}{\mathrm{N}}_t$ .

If $\mathcal{M}$ has answered a top-k query whose interested time epoch is the same as that of $Q_t$ , the location information of each virtual node does not need to be sent to the network owner any more. Moreover, we further shrink the amount of information in top-k query results by excluding the information that has been sent to the network owner. Thus, if $S_i$ is a queried sensor node for $Q_t$ , the following inequality holds:

$$\begin{array}{cc}& C_{v\text{-}mw}^{S_i}\le l_{\mathrm{i}\mathrm{d}}+{\displaystyle \sum }_{a=\mathrm{1}}^{{\omega }_i^t}{C}_{v\text{-}sm}^{\mathrm{v}\mathrm{n}{\mathrm{d}}_i^{x_a}}.\end{array}$$

(21)

If sensor node $S_i$ is not a queried sensor node for $Q_t$ , then

$$\begin{array}{cc}& C_{v\text{-}mw}^{S_i}=\mathrm{0}.\end{array}$$

(22)

Then we have

$$\begin{array}{cc}& C_{v\text{-}mw}\le {\displaystyle \sum }_{i=\mathrm{1}}^N\mathrm{2}\ast C_{v\text{-}mw}^{S_i}.\end{array}$$

(23)

Similarly, we assume that the energy consumption incurred by sending and receiving one bit of data is the same across the on-demand wireless link. Thus, $C_{v\text{-}mw}$ is doubled in (23).

5.3. Impact of Compromising Some Sensor Nodes

In above sections, we never consider the case that some sensor nodes are compromised. Thus we now further analyze the impact of compromised sensor nodes. If some sensor nodes are compromised, the following two kinds of attack may be launched.

(1) The compromised sensor nodes may collaborate with $\mathcal{M}$ to help it escape the detection. The impact of this behavior depends on $P_c$ , which is the probability that at least one queried sensor node is compromised. In [3], it is known that if sensor nodes are static and uniformly distributed, the probability that at least one compromised node is in the query region is $\mathrm{1}-{\prod }_{i=\mathrm{1}}^c(\mathrm{1}-\min \{\mathrm{1},\delta /\left(N-i+\mathrm{1}\right)\})$ , where c is the number of compromised nodes in a cell and δ is the number of sensor nodes in the query region. Thus, in TMSN, if one sensor node generates b virtual nodes on average in one epoch and all virtual nodes uniformly distributed, we have

$$\begin{array}{cc}& P_c=\mathrm{1}-{\displaystyle \prod }_{i=\mathrm{1}}^{c\ast b}\left(\mathrm{1}-\min \left\{\mathrm{1},\frac{\delta }{N\ast b-i+\mathrm{1}}\right\}\right),\end{array}$$

(24)

where δ denotes the number of virtual nodes in the query region in one epoch and c denotes the number of compromised sensor nodes in a cell. If a queried sensor node is compromised, its forged data can not be detected by $\mathcal{W}$ using existing methods including ours.

However, some countermeasures can be adopted to solve this problem. One countermeasure is to shrink the query region, so that $P_c$ can be decreased; another countermeasure is to monitor the frequency for a sensor node to generate data items with peak values. If a sensor node generates data items with extremely high values on some of its child nodes frequently, the sensor node can be suspected as being compromised, and then some tools like software attestation [28] can be used to testify its hypotheses.

(2) If $\mathcal{M}$ is not compromised, the compromised sensor nodes may generate some verification information encrypted using the incorrect keys to make $\mathcal{W}$ take $\mathcal{M}$ as being compromised. One countermeasure against this attack is to digitally sign every message transmitted and received. Because of limited space, we do not describe this method in detail, and more details can be found in [3].

6. Performance Evaluation

In this section, we evaluate the efficiency of VTMSN and illustrate the impact of some factors on the metrics presented in Section 4. We use OMNET++ as our simulator. In our simulation model, we assume the size of a cell in TMSN is 400 m × 400 m. In each cell, 500 sensor nodes are deployed randomly. They switch their states between mobile state and static state periodically. Some other default parameters are listed in Table 2, where R is the communication radius of each sensor node, $T_s$ denotes the average time period for a sensor node to keep static, and $T_m$ denotes the average time period for a sensor node to keep mobile. We will make a special declaration if some parameters are changed in the simulation. We also assume collision-free and error-free packet transmissions as in [3]. For ease of presentation, when we say verification information for data items, we refer to the encrypted term following each data item in the query result, and we call the left verification information the verification information for virtual nodes in the following of this paper.

Table 2

Default evaluation parameters.

Para.	Val.
$$l_D$$	400
$$f_d$$	10
$$l_{\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{h}}$$	10
R	50 m
$$f_q$$	100
$$l_{\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}}$$	20
$$l_{\mathrm{i}\mathrm{d}}$$	10
$$T_m$$	10
$$l_{\mathrm{n}\mathrm{u}\mathrm{m}}$$	10
k	10
$$T_s$$	10
$$T_e$$	50

6.1. The Results of $C_{v\text{-}sm}$ and the Corresponding $R_{vs}$

To evaluate the performance of $C_{v\text{-}sm}$ and the corresponding $R_{vs}$ objectively, we run the simulation for consecutive 100 epochs and take the average values of $C_{v\text{-}sm}$ and $R_{vs}$ in one epoch as the final results, which are illustrated as follows.

6.1.1. Impact of Parameters $T_m$ , $T_s$ , and $T_e$

Figure 3 shows that $C_{v\text{-}sm}$ becomes larger and larger as $T_e$ increases. The reason is obvious: the larger $T_e$ is, the more the data items are, and more verification information is needed. However, Figure 4 shows that the corresponding $R_{vs}$ does not change too much as $T_e$ increases. This indicates that the ratio of the increasing rate of verification information to that of data items keeps relatively stable as $T_e$ increases.

Figure 3

Impact of parameters $T_m$ , $T_s$ , and $T_e$ on $C_{v\text{-}sm}$ .

Figure 4

Impact of parameters $T_m$ , $T_s$ , and $T_e$ on $R_{vs}$ corresponding to $C_{v\text{-}sm}$ .

From Figure 3, we can also find that the longer the total time for sensor nodes to be in a static state in one epoch is, the larger $C_{v\text{-}sm}$ is, because sensor nodes generate data items only when they are in a static state. Moreover, when $T_m$ and $T_s$ are equal, the smaller $T_m$ and $T_s$ are, the more the verification information is needed, because more virtual nodes are formed when $T_m$ and $T_s$ are smaller and the amount of data items is almost the same when $T_m$ and $T_s$ are equal. It is also the reason why $R_{vs}$ is much larger than that in the other two cases in Figure 4 when $T_m$ and $T_s$ are set to 2 s.

Now we explain why $R_{vs}$ with $T_m=2$  s and $T_s=10$  s is almost equal to or sometimes a little larger than $R_{vs}$ with $T_m=10$  s and $T_s=10$  s in Figure 4. First, sensor nodes in the former case generate more data items than those in the latter case. If the numbers of virtual nodes are the same for the two cases, the more the data items are generated, the smaller $R_{vs}$ is. Of course, $R_{vs}$ should be bigger than the ratio of cost of transmitting the verification information for data items to the cost of transmitting data items. Thus, if the number of virtual nodes is the same, $R_{vs}$ in the former case should be much smaller than that in the latter case. However, virtual nodes formed in the former case are many more than those formed in the latter case. Thus, much more verification information for virtual nodes is needed in the former case. Taken altogether, $R_{vs}$ in the former case is almost equal to or sometimes a little larger than that in the latter case.

6.1.2. Impact of Parameter $f_d$

From Figure 5, we can see that the larger $f_d$ is, the larger $C_{v\text{-}sm}$ is. The reason is clear: more data items need more verification information in VTMSN. Figure 6 shows the simulation results of the corresponding $R_{vs}$ . We can see that the larger $f_d$ is, the smaller $R_{vs}$ is. The reason is that larger $f_d$ leads to more data items generated in a given time period, and the more the data items are generated, the closer $R_{vs}$ is to the ratio of the amount of verification information for data items to the amount of the data items. However, because there is an encrypted term following each data item in VTMSN, $R_{vs}$ can not be smaller than the ratio of the length of each verification term following each data item to the length of each data item. That is why $R_{vs}$ decreases slower and slower as $f_d$ increases in Figure 6.

Figure 5

Impact of parameter $f_d$ on $C_{v\text{-}sm}$ .

Figure 6

Impact of parameter $f_d$ on $R_v$ corresponding to $C_{v\text{-}sm}$ .

6.2. The Results of $C_{v\text{-}mw}$ and the Corresponding $R_{vs}$

In this subsection, we evaluate the performance of our verification scheme VTMSN on $C_{v\text{-}mw}$ and its corresponding $R_{vs}$ with different parameter configurations. The results are as follows.

6.2.1. Impact of Parameters $QR$ and k

Figure 7 shows the impact of the query region $QR$ and parameter k on $C_{v\text{-}mw}$ in VTMSN. We can see that the larger $QR$ and k are, the larger $C_{v\text{-}mw}$ is, because larger $QR$ and k bring more virtual nodes and data items which need more verification information.

Figure 7

Impact of parameters $QR$ and k on $C_{v\mathit{\text{-}}mw}$ .

Figure 8 shows the impact of $QR$ and k on $R_{vs}$ corresponding to $C_{v\text{-}mw}$ of VTMSN. We can see that if parameter k does not change, the larger $QR$ is, the larger $R_{vs}$ is. Recall that $R_{vs}$ here is the ratio of $C_{v\text{-}mw}$ to the energy consumption in bits incurred by sending and receiving the top k data items. Thus, if k does not change, the larger $C_{v\text{-}mw}$ is, the larger $R_{vs}$ is. On the other hand, we can also see from Figure 8 that, with the same $QR$ , the larger k is, the smaller $R_{vs}$ is. This can be explained easily according to the definition of $R_{vs}$ . In Figure 8, $R_{vs}$ decreases slower and slower as k increases. The reason is that there is an encrypted term $E_{Ki}\{\ast \}$ following each data item as the verification information for data items in VTMSN, and $R_{vs}$ can not be smaller than the ratio of the length of the term $E_{Ki}\{\ast \}$ to the length of a data item.

Figure 8

Impact of parameters $QR$ and k on $R_{vs}$ corresponding to $C_{v\mathit{\text{-}}mw}$ .

6.2.2. Impact of Parameters $T_m$ , $T_s$ , and v

Figures 9 and 10 show the impact of moving period $T_m$ , static period $T_s$ , and the moving speed v of a sensor node on $C_{v\text{-}mw}$ and its corresponding $R_{vs}$ , respectively. It is clear that both $C_{v\text{-}mw}$ and its corresponding $R_{vs}$ are not influenced by the speed of sensor nodes too much.

Figure 9

Impact of parameters $T_m$ , $T_s$ , and v on $C_{v\text{-}mw}$ .

Figure 10

Impact of parameters $T_m$ , $T_s$ , and v on $R_{vs}$ corresponding to $C_{v\text{-}mw}$ .

In theory, with the same other parameters, the more the times for sensor nodes to switch their states in one epoch are, the larger $C_{v\text{-}mw}$ is, because more virtual nodes will be generated in the query region and they need more verification information. Figure 9 illustrates this. As an example, when $T_m=2$  s, $T_s=2$  s, and $T_e=50$  s, each sensor node switches its state for 24 times, while there are only 4 times for a sensor node to switch its state when $T_m=10$  s, $T_s=10$  s, and $T_e=50$  s. Figure 9 shows that $C_{v\text{-}mw}$ in the former case is larger than that in the latter case. The corresponding $R_{vs}$ in Figure 10 is in conformity with $C_{v\text{-}mw}$ in Figure 9. The reason is that the value of parameter k is the same, which means the amount of data items sent from $\mathcal{M}$ to $\mathcal{W}$ is the same in this test, and the value of $R_{vs}$ depends on the value of $C_{v\text{-}mw}$ totally according to the meaning of $R_{vs}$ .

6.2.3. Impact of Parameter $f_q$

Figures 11 and 12 show the impact of query frequency $f_q$ on $C_{v\text{-}mw}$ and its corresponding $R_{vs}$ , respectively, where the abscissas denote the number of queries issued by the network owner in one epoch. We can see that both $C_{v\text{-}mw}$ and its corresponding $R_{vs}$ decrease as $f_q$ increases. The reason is that the locations of virtual nodes need to be sent to the network owner only when the data generated during the epoch when the virtual nodes existed are queried for the first time. Besides, if a virtual node does not have any qualified data for a query, it needs to send the verification information to the network owner only when it is in the query region for the first time. Thus, as the number of queries increases in one epoch, the probability that a virtual node need not have to have the verification information of itself in the query result increases. Thus, the average value of $C_{v\text{-}mw}$ for each query decreases. Besides, according to the definition of $R_{vs}$ , with the same k, $R_{vs}$ decreases as $C_{v\text{-}mw}$ decreases.

Figure 11

Impact of parameter $f_q$ on $C_{v\text{-}mw}$ .

Figure 12

Impact of parameter $f_q$ on $R_{vs}$ corresponding to $C_{v\text{-}mw}$ .

7. Conclusion

In this paper, we present a tiered mobile sensor network model named TMSN for the first time and propose an effective verification scheme called VTMSN to verify the authentication and the completeness of the top-k query results received by the network owner in TMSN. The proposed scheme achieves the goal of making the network owner verify the authenticity and completeness of top-k query results in TMSN with high probability and good efficiency via the mechanisms of virtual node mapping and data binding. Theory analysis shows that VTMSN can detect any forged and/or incomplete top-k query result with probability that $P_{\mathrm{d}\mathrm{e}\mathrm{t}}=1$ when none of the queried sensor nodes is compromised. We have conducted extensive experiments with different parameter configurations, and the simulation results show that VTMSN is effective and feasible.