Unbalanced Threshold Based Distributed Data Collection Scheme in Multisink Wireless Sensor Networks

Abstract

In multisink wireless sensor networks, synchronized data collection among multiple sinks is a significant and challenging task. In this paper, we propose an unbalanced threshold based distributed data collection scheme to reconstruct the synchronized sensed data of the whole sensor network in all sinks. The proposed scheme includes the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm and the distributed iterative hard thresholding algorithm. By computing unbalanced thresholds and pruning unnecessary element exchanging, each sink can synchronize the top- $\left|K\right|$ aggregated values efficiently via the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm. After that, the synchronized sensed data of the whole sensor network can be reconstructed through the distributed iterative hard thresholding algorithm in a distributed and cooperative manner. We show through experiments that the proposed scheme can reduce the interaction times and decrease the number of transmitted data and that of computed data compared to the existing schemes while maintaining the similar data reconstruction accuracy. The communication and computational performances of the proposed scheme are also analyzed in detail in the paper.

1. Introduction

Wireless sensor network (WSN) is an autonomous wireless network consisting of a large number of tiny, inexpensive, and spatially distributed wireless sensor nodes. It has emerged as one of the most promising technologies for the future [1]. The typical applications of WSN include environment monitoring, industrial process control, intelligent transportation, military surveillance, and health care monitoring [2].

However, wireless sensor nodes have severe resource constraints which include limited computational, memory, communication capacities and nonrenewable energy supply. Therefore, data collection schemes in wireless sensor network should be light weight and energy efficient. Two representative types of data collection schemes in wireless sensor networks are spatial-temporal correlation based data predication schemes [3–5] and distributed source coding schemes [6–8]. In the first type of data collection scheme, a series of spatial-temporal correlation based data prediction algorithms are adopted to prolong the system lifetime by enabling the sink to predict the sensed data based on some historical samples. In the second type of data collection scheme, distributed source coding techniques, such as Slepian-Wolf coding and Wyner-Ziv coding, are designed to compress the multiple correlated sensor data without the need of communication among sensor nodes. Nevertheless, the computational and communication cost of the above two types of data collection schemes are still high. Meanwhile, the parameters of predication model and the distributed coded data are still required to be computed and transmitted within the network frequently.

Recently, compressive sensing (CS) theory has attracted considerable attention in areas of signal processing, computer science, and applied mathematics [9]. It is based on the principle that a sparse signal can be reconstructed from far fewer samples than that required by the classic Shannon-Nyquist sampling theory. Through nonlinear optimization, we can recover many natural signals which can be represented by a few nonzero coefficients under a suitable basis [10]. The inherent characteristics, such as compressibility, robustness, versatility, and stability, have made compressive sensing theory widely applied to communication [11], photography [12], magnetic resonance imaging [13], astronomy [14], and so forth.

As for the data collection problem in wireless sensor networks, a number of compressive sensing based schemes have been proposed in the literature. In 2009, Luo et al. proposed the first complete compressive sensing based data gathering (CDG) scheme for large scale wireless sensor networks [15]. By adapting a weighted sum of all the readings along the routing tree, CDG scheme can achieve substantial communication cost reduction and balanced energy consumption simultaneously. In order to achieve both energy efficiency and recovery fidelity, Xiang et al. proposed the Compressive Data Aggregation (CDA) scheme in WSN [16]. After abstracting the minimum energy compressed data aggregation problem as a NP-completeness problem, they solve it using a mixed integer programming formulation method. Moreover, they also proposed the Dual-lEvel Compressed Aggregation (DECA) framework to recover the in-network aggregated data in the widespread monitoring area by utilizing both the low-rank nature of real-world events and the redundancy in sensed data [17]. By exploiting the spatial and temporal correlation among sensed data, Xu et al. proposed the Spatio-Temporal Hierarchical Data Aggregation Scheme Using Compressive Sensing (ST-HDACS) in [18]. After collecting the sensed data from a subset of randomly selected sensor nodes through a hierarchical routing structure, the fusion center recovers the whole sensed data by solving a matrix completing problem. Furthermore, Tang et al. proposed a robust compressive data gathering scheme to identify outlying sensor readings and derive the corresponding accurate values and further infer broken links in the sensor network [19]. Motivated by the fact that the variance among all the solutions of the blind iterative hard thresholding algorithm with different sparse level can indicate the best sparse level, Xiong and Tang proposed the blind 1-bit compressive sensing reconstruction algorithm for wireless sensor network [20]. Similar research works include the sparse random scheduling based data gathering scheme [21], the Resource Efficient Data Gathering (REDG) scheme [22], the Compressive Sensing Based Data Aggregation Scheme (CSDAS) [23], and the distributed multichain based compressive sensing scheme [24].

Although the above schemes can achieve energy-efficient data collection based on compressive sensing theory, they can only be applied to single-sink wireless sensor networks in a centralized manner. In the scenario of multisink wireless sensor networks, compressed data should be transmitted to one specific sink before executing the data reconstruction algorithm. Then, the recovered data should be distributed back to other sinks through unicast or broadcast messages. Obviously, this kind of centralized pattern is less energy efficient and time consuming. In this paper, we focus on designing compressive sensing based distributed data collection scheme for multisink wireless sensor networks. The proposed scheme includes two correlated algorithms: the unbalanced threshold based distributed top- $\left|K\right|$ algorithm and the distributed iterative hard thresholding algorithm. In the first algorithm, the largest K absolute aggregated values of a series of object-value pairs are queried in a distributed and energy efficient way. By computing unbalanced thresholds, a number of unnecessary object-value pairs exchanging are pruned in the query process. In the second algorithm, the iterative hard thresholding algorithm [25] is modified to fit the distributed environment. Meanwhile, the first algorithm is integrated into the second one as a subroutine to realize the $H_K()$ operator. Our experiment results indicate that the proposed scheme can reduce the interaction times and decrease the number of transmitted data and that of computed data compared to the existing schemes while maintaining the similar data reconstruction accuracy.

The contributions of this paper are threefold.

(1) We propose an unbalanced threshold based distributed data collection scheme in multisink wireless sensor networks based on compressive sensing theory. By decomposing the task of sparse data reconstruction into several correlated parts, all sinks can obtain the synchronized sensed data of the whole network in a distributed and cooperative manner.

(2) We propose an unbalanced threshold based distributed top- $\left|K\right|$ query algorithm to query the top- $\left|K\right|$ aggregated values required by the iterative hard thresholding algorithm in the distributed environment. By adopting unbalanced thresholds, the algorithm can avoid transmitting unnecessary object-value pairs among sinks. Furthermore, the correctness of the proposed algorithm is also proved in this paper.

(3) We analyze the data reconstruction performance, communication complexity, and computational complexity of the proposed scheme through experiments. Furthermore, we also compare the performance of the proposed scheme with existing compressive sensing based data collection schemes.

The rest of this paper is organized as follows. Section 2 introduces the basic principles of compressive sensing theory and the iterative hard thresholding algorithm. Sections 3 and 4 describe the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm and the distributed iterative hard thresholding algorithm, respectively. Section 5 presents the experimental results and analysis. Finally, Section 6 concludes this paper.

2. Preliminaries

Compressive sensing theory asserts that a sparse signal can be recovered from fewer linear and nonadaptive measurements than the number of samples required by Shannon-Nyquist Sampling Theorem. The compressive sampling process can be presented as

$$\begin{array}{cc}& y=\Phi f+z,\end{array}$$

(1)

where $f\in R^N$ is a K sparse unknown signal; that is, there are at most K nonzero elements in f. $\Phi \in R^{M\times N}$ is the measurement matrix, $z\in R^M$ is the unknown noise, and $y\in R^M$ is the measurement signal. Although most natural signals are not sparse directly, they can be transformed into sparse signals. In other words, a signal f can be represented as a sparse signal $x\in R^N$ under an orthonormal basis $\Psi \in R^{N\times N}$ ; that is, $f=\Psi x$ . Hence, (1) can be rewritten as

$$\begin{array}{cc}& y=\Phi f+z=\Phi \Psi x+z\end{array}$$

(2)

and matrix $A=\Phi \Psi$ is usually referred to as sensing matrix.

One of the most important properties of sensing matrix is the Restrict Isometry Property (RIP). Formally, a matrix A is said to satisfy the RIP of order K with a Restrict Isometry Constant (RIC) ${\delta }_K$ such that

$$\begin{array}{cc}& \left(\mathrm{1}-{\delta }_K\right){‖x‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖Ax‖}_{\mathrm{2}}^{\mathrm{2}}\le \left(\mathrm{1}+{\delta }_K\right){‖x‖}_{\mathrm{2}}^{\mathrm{2}}\end{array}$$

(3)

holds for all K sparse signal x. Baraniuk et al. have proved that a random matrix $A\in R^{M\times N}$ with i.i.d. entries followed by normal distribution $N(\mathrm{0,1}/M)$ satisfies the RIP with a high probability when $M\ge CK\log (N/K)$ and C is a constant [26].

The Basis Pursuit De-Noise (BPDN) [27] and the Least Absolute Shrinkage and Selection Operator (LASSO) [28] are two typical signal recovery frameworks which are wildly used in compressive sensing theory. In BPDN framework, the $l_1$ norm of the unknown signal is minimized under the constraint of limited energy of reconstruction error; that is,

$$\begin{array}{cc}& \underset{x}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{‖x‖}_{\mathrm{1}},\\ \text{s.t.}\hspace{1em}{‖Ax-y‖}_{\mathrm{2}}\le \epsilon .\end{array}$$

(4)

In contrast, the energy of reconstruction error is minimized in LASSO framework under the constraint of limited $l_1$ norm of the unknown signal x; that is,

$$\begin{array}{cc}& \underset{x}{\min }\hspace{1em}{‖\mathrm{A}x-y‖}_{\mathrm{2}}^{\mathrm{2}},\\ \text{s.t.}\hspace{1em}{‖x‖}_{\mathrm{1}}\le \eta .\end{array}$$

(5)

Essentially, the BPDN framework and LASSO framework can all be transformed into the following unconstraint regularized optimization framework:

$$\begin{array}{cc}& \underset{x}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\frac{\mathrm{1}}{\mathrm{2}}{‖Ax-y‖}_{\mathrm{2}}^{\mathrm{2}}+\tau {‖x‖}_{\mathrm{1}}.\end{array}$$

(6)

A number of data reconstruction algorithms have been proposed in the literature. In general, they can be classified into two categories: optimization algorithms and greedy algorithms. In the optimization algorithms, a number of convex optimization methods have been adopted to search the optimized solution of (6). Basis Pursuit (BP) algorithm [27], Interior Point (IP) algorithm [29], and homotopy algorithm [30] are representatives of this type of reconstruction algorithm. On the contrary, greedy algorithms iteratively select the support sets or the elements of the reconstructed signal based on certain greedy selection strategy. Orthogonal Matching Pursuit (OMP) algorithm [31], Regularized Orthogonal Matching Pursuit (ROMP) algorithm [32], Compressive Sampling Matching Pursuit (CoSmMP) algorithm [33], Subspace Matching Pursuit (SP) algorithm [34], iterative hard thresholding (IHT) algorithm [25], and Iterative Soft Thresholding (IST) algorithm [35] are representatives of greedy algorithm.

Among all proposed data reconstruction algorithms, the iterative hard thresholding algorithm is very easy to implement and can be relatively fast. Meanwhile, it also possesses strong theoretical recovery performance guarantees as convex optimization based algorithms. Essentially, it can be regarded as an iterative method

$$\begin{array}{cc}& x^{\left(t+\mathrm{1}\right)}=H_K\left(x^{\left(t\right)}+\mu A^T\left(y-A{x}^{\left(t\right)}\right)\right),\end{array}$$

(7)

where $H_K()$ is the hard thresholding operator that sets all but K largest elements in magnitude to zero and μ is the step size. Formally, we can represent the hard thresholding operator $H_K()$ as

$$\begin{array}{cc}& H_K{\left(x\right)}_i=\left\{\begin{array}{cc}{x}_i\hfill & x_i\in \left\{x_{\text{top-}\left|K\right|}\right\}\hfill \\ \mathrm{0}\hfill & x_i\notin \left\{x_{\text{top-}\left|K\right|}\right\},\hfill \end{array}\right.\end{array}$$

(8)

where $x_{\text{top-}\left|K\right|}$ represents the largest K elements of signal x in magnitude. We will propose a distributed implementation of hard thresholding operator $H_K()$ in next section and integrate it in the distributed iterative hard thresholding algorithm which is described in Section 4.

3. The Unbalanced Threshold Based Distributed Top- $\left|K\right|$ Query Algorithm

In recent years, top-K query, also known as ranking aware query, has received much attention in the areas of relational database system, content distribution network, multimedia retrieval system, and so forth. However, only monotonic aggregation functions can be applied to the top-K query. The largest K absolute elements query in the hard thresholding operator is nonmonotonic. Therefore, the proposed top-K query algorithms, such as thresholding algorithm (TA) [36] and three-phase uniform threshold (TPUT) algorithm [37], cannot be applied to the distributed IHT algorithm directly. We will describe our proposed unbalanced threshold based distributed top- $\left|K\right|$ query algorithm in detail in Section 3.1 and illustrate it with an example in Section 3.2.

3.1. Algorithm Design

We assume there are P nodes in the distributed system and each node is assigned with an ID. The node with the lowest ID is designated as the administrator node and other nodes are designated as the member nodes. Each node i maintains a descending ordered list $L_i$ of its object-value pairs $(O_j,V_i(j))$ where index j ranges from 1 to element number $N_i$ . Note that if an object does not appear in the list, its value is set to zero by default. We will select the largest K sums in magnitude of all the objects in the distributed system.

The core idea of the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm is to filter out unnecessary exchanging of elements among distributed nodes by adopting unbalanced thresholds. It includes three phases, that is, the unbalanced threshold computing phase, the candidate set computing phase, and the top- $\left|K\right|$ elements computing phase.

In the unbalanced threshold computing phase, each member node sends its first K positive elements and last K negative elements to the administrator node. Then, the administrator node can compute the partial sum $P(j)$ for every received element j according to

$$\begin{array}{cc}& P\left(j\right)={{\displaystyle \sum }}_{i=\mathrm{1}}^P{V}_i^{\prime }\left(j\right),\\ V_i^{\prime }\left(j\right)=\left\{\begin{array}{cc}{V}_i\left(j\right)\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}known}\hfill \\ \mathrm{0}\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}unknown}\hfill \end{array}\right.\end{array}$$

(9)

and select the Kth largest positive partial sum ${\stackrel{-}{\tau }}^{\mathrm{1}}$ and the Kth smallest negative partial sum ${\underset{\_}{\tau }}^{\mathrm{1}}$ . The partial sum $P(j)$ is used to estimate the sum of top- $\left|K\right|$ elements approximately. In order to deal with unbalanced value distribution among different nodes and avoid redundant element exchanging between administrator node and member nodes, we compute different thresholds for each node instead of fixing one identical threshold for all nodes. Based on the computed positive weight ${\stackrel{-}{\omega }}_i$ and negative weight ${\underset{\_}{\omega }}_i$ , the partial sums ${\stackrel{-}{\tau }}^{\mathrm{1}}$ and ${\underset{\_}{\tau }}^{\mathrm{1}}$ are divided into P different thresholds ${\stackrel{-}{T}}_i$ and ${\underset{\_}{T}}_i$ , respectively.

In the candidate set computing phase, each member node sends unsent object-value pairs $(O_j,V_i(j))$ to the administrator node when $V_i\left(j\right)\ge {\stackrel{-}{T}}_i^{\mathrm{1}}$ or $V_i\left(j\right)\le {\underset{\_}{T}}_i^{\mathrm{1}}$ . Then, the administrator node computes the partial sum according to (9) and selects the Kth largest positive partial sum ${\stackrel{-}{\tau }}^{\mathrm{2}}$ and Kth smallest negative partial sum ${\underset{\_}{\tau }}^{\mathrm{2}}$ once again. Furthermore, it computes the upper bound $U(j)$ and lower bound $L(j)$ of the whole sum for every received object j according to

$$\begin{array}{cc}& U\left(j\right)={{\displaystyle \sum }}_{i=\mathrm{1}}^P{\stackrel{-}{V}}_i\left(j\right),\\ {\stackrel{-}{V}}_i\left(j\right)=\left\{\begin{array}{cc}{V}_i\left(j\right)\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}known}\hfill \\ {\stackrel{-}{T}}_i\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}unknown},\hfill \end{array}\right.\end{array}$$

(10)

$$\begin{array}{cc}& L\left(j\right)={{\displaystyle \sum }}_{i=\mathrm{1}}^P{\underset{\_}{V}}_i\left(j\right),\\ {\underset{\_}{V}}_i\left(j\right)=\left\{\begin{array}{cc}{V}_i\left(j\right)\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}known}\hfill \\ {\underset{\_}{T}}_i\hfill & V_i\left(j\right)\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}unknown},\hfill \end{array}\right.\end{array}$$

(11)

respectively. The upper bound and lower bound are used to estimate the maximal range of each object. If $U\left(j\right)<{\stackrel{-}{\tau }}^{\mathrm{2}}$ or $L\left(j\right)>{\underset{\_}{\tau }}^{\mathrm{2}}$ , we can guarantee that the whole sum of object j

$$\begin{array}{cc}& W\left(j\right)={{\displaystyle \sum }}_{i=\mathrm{1}}^P{V}_i\left(j\right)\end{array}$$

(12)

is not in the set of top- $\left|K\right|$ aggregated sums. Hence, we can exclude object j from the candidate set Swith confidence.

In the top- $\left|K\right|$ elements computing phase, each member node sends unsent object-value pairs $(O_j,V_i(j))$ in candidate set S to the administrator node. Then, the administrator node can compute the whole sum for each object according to (12) and select the top- $\left|K\right|$ aggregated sums.

The pseudocode of the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm is presented in Algorithm 1.

Algorithm 1: The unbalanced threshold based distributed top- $|K|$ query algorithm.

Input: The descending list $L_i=\left\{\right.(O_j,V_i(j))\mid i\in \left\{\right.\mathrm{1},\dots ,P\left.\right\},j\in \left\{\right.\mathrm{1},\dots ,N_i\left.\right\}\left.\right\}$

Phase I: The unbalanced thresholds computing phase

If node i is administrator node Then

 Computes partial sums $P(j)$ for received elements according to (9);

 Let ${\stackrel{-}{\tau }}^{\mathrm{1}}=\min {\left\{\right.P_j\left.\right\}}_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}K}$ and ${\underset{\_}{\tau }}^{\mathrm{1}}=-\min {\left\{\right.-P_j\left.\right\}}_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}K}$ ;

 Computes weights ${\stackrel{-}{\omega }}_i={{\displaystyle \sum }}_{j=\mathrm{1}}^K{V}_i(j)/K$ and ${\underset{\_}{\omega }}_i={{\displaystyle \sum }}_{j=N_i-K+\mathrm{1}}^{N_i}{V}_i(j)/K$ ;

 Sends thresholds ${\stackrel{-}{T}}_i={\stackrel{-}{\tau }}^{\mathrm{1}}{\stackrel{-}{\omega }}_i/{{\displaystyle \sum }}_{i=\mathrm{1}}^P{\stackrel{-}{\omega }}_i$ and ${\underset{\_}{T}}_i={\underset{\_}{\tau }}^{\mathrm{1}}{\underset{\_}{\omega }}_i/{{\displaystyle \sum }}_{i=\mathrm{1}}^P{\underset{\_}{\omega }}_i$ to member nodes;

Else

 Sends $\left\{\right.(O_j,V_i(j))\mid j\in \left\{\right.\mathrm{1},\dots ,K\left.\right\}\cup \left\{\right.N_i-K+\mathrm{1},\dots ,N_i\left.\right\}\left.\right\}$ to administrator node;

Phase II: The candidate set computing phase

If node i is administrator node Then

 Computes partial sums $P(j)$ for received elements according to (9);

 Let ${\stackrel{-}{\tau }}^{\mathrm{2}}=\min {\left\{\right.P_j\left.\right\}}_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}K}$ and ${\underset{\_}{\tau }}^{\mathrm{2}}=-\min {\left\{\right.-P_j\left.\right\}}_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}K}$ ;

 Computes upper bounds $U(j)$ and lower bounds $L(j)$ of whole sums for received elements according to (10) and (11);

 Sends candidate set $S=\left\{\right.j\mid j\in \left\{\right.U(j)\ge {\stackrel{-}{\tau }}^{\mathrm{2}}\left.\right\}\cup \left\{\right.L(j)\le {\underset{\_}{\tau }}^{\mathrm{2}}\left.\right\}\left.\right\}$ to member nodes;

Else

 Sends unsent $\left\{\right.(O_j,V_i(j))\mid j\in \left\{\right.V_i(j)\ge {\stackrel{-}{T}}_i^{\mathrm{1}}\left.\right\}\cup \left\{\right.V_i(j)\le {\underset{\_}{T}}_i^{\mathrm{1}}\left.\right\}\left.\right\}$ to administrator node;

Phase III: The top- $|K|$ elements computing phase

If node i is administrator node Then

 Computes whole sums $W(j)$ for received elements according to (12);

 Let $S_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}|K|}=\left\{\right.(O_j,V(j))\mid j\in {\left\{\right.\left|\right.W_j\left.\right|\left.\right\}}_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}K}\left.\right\}$ ;

Else

 Sends unsent $\left\{\right.(O_j,V_i(j))\mid j\in S\left.\right\}$ to administrator node;

Output: The top- $|K|$ element set $S_{\mathrm{t}\mathrm{o}\mathrm{p}\text{-}|K|}$

Lemma 1.

The unbalanced thresholds computed in phase I can guarantee that the true top- $\left|K\right|$ objects are among the objects in phase II.

Proof.

Assume that $O_k$ is an object which is not sent to the administrator node in phase II. Then its value $V_i(k)$ in node i is less than ${\stackrel{-}{T}}_i$ and greater than ${\underset{\_}{T}}_i$ at the same time; that is, ${\underset{\_}{T}}_i<V_i(k)<{\stackrel{-}{T}}_i$ . Then the sum of object $O_k$ 's value can be bounded by

$$\begin{array}{cc}& {{\displaystyle \sum }}_{i=\mathrm{1}}^P{\underset{\_}{T}}_i<{{\displaystyle \sum }}_{i=\mathrm{1}}^P{V}_i\left(k\right)<{{\displaystyle \sum }}_{i=\mathrm{1}}^P{\stackrel{-}{T}}_i.\end{array}$$

(13)

Since ${\sum }_{i=\mathrm{1}}^P{\underset{\_}{T}}_i={\sum }_{i=\mathrm{1}}^P\left({\underset{\_}{\tau }}^{\mathrm{1}}{\underset{\_}{\omega }}_i/{\sum }_{i=\mathrm{1}}^P{\underset{\_}{\omega }}_i\right)={\underset{\_}{\tau }}^{\mathrm{1}}$ and ${\sum }_{i=\mathrm{1}}^P{\stackrel{-}{T}}_i={\sum }_{i=\mathrm{1}}^P\left({\stackrel{-}{\tau }}^{\mathrm{1}}{\stackrel{-}{\omega }}_i/{\sum }_{i=\mathrm{1}}^P{\stackrel{-}{\omega }}_i\right)={\stackrel{-}{\tau }}^{\mathrm{1}}$ , (13) can be rewritten as

$$\begin{array}{cc}& {\underset{\_}{\tau }}^{\mathrm{1}}<{{\displaystyle \sum }}_{i=\mathrm{1}}^P{V}_i\left(k\right)<{\stackrel{-}{\tau }}^{\mathrm{1}}.\end{array}$$

(14)

That is, object $O_k$ cannot be a top- $\left|K\right|$ object. Therefore, true top- $\left|K\right|$ objects must be among the objects in phase II.

Lemma 2.

The candidate set computed in phase II can guarantee that the true top- $\left|K\right|$ objects are among the objects in phase III.

Proof.

Assume that $O_k$ is an object which is not included in candidate set S in phase II. Then the sum of object $O_k$ 's value satisfies ${\sum }_{i=\mathrm{1}}^P{V}_i(k)<U(j)<{\stackrel{-}{\tau }}^{\mathrm{2}}$ and ${\sum }_{i=\mathrm{1}}^P{V}_i(k)>L(j)<{\underset{\_}{\tau }}^{\mathrm{2}}$ at the same time; that is,

$$\begin{array}{cc}& {\underset{\_}{\tau }}^{\mathrm{2}}<{{\displaystyle \sum }}_{i=\mathrm{1}}^P{V}_i\left(k\right)<{\stackrel{-}{\tau }}^{\mathrm{2}}.\end{array}$$

(15)

Since ${\stackrel{-}{\tau }}^{\mathrm{2}}$ and ${\underset{\_}{\tau }}^{\mathrm{2}}$ are the Kth largest positive partial sum and the Kth smallest negative partial sum, there are already K objects whose partial sums are greater than ${\stackrel{-}{\tau }}^{\mathrm{2}}$ and lesser than ${\underset{\_}{\tau }}^{\mathrm{2}}$ . That is, object $O_k$ cannot be a top- $\left|K\right|$ object. Therefore, true top- $\left|K\right|$ objects must be among the objects in phase III.

Theorem 3.

The unbalanced threshold based distributed top- $\left|K\right|$ query algorithm can obtain the largest K aggregated sums in magnitude of all objects in the distributed system.

Proof.

Through Lemmas 1 and 2, we can prove that true top- $\left|K\right|$ objects must be among the objects in phase III. Furthermore, the administrator node has obtained all the values for each object in the candidate set. Therefore, the proposed algorithm can obtain the largest K aggregated sums in magnitude of all objects in the distributed system.

3.2. Example

We will illustrate the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm with an example in this subsection. There are 3 nodes in the distributed system, one administrator node and two member nodes. The object-value pairs in each node are presented in Table 1.

Table 1

An example with 3 nodes.

Administrator node	Member node 1	Member node 2
( $O_5$ , 21)	( $O_4$ , 34)	( $O_5$ , 20)
( $O_2$ , 17)	( $O_5$ , 28)	( $O_4$ , 17)
( $O_4$ , 15)	( $O_2$ , 22)	( $O_3$ , 14)
( $O_3$ , 10)	( $O_3$ , 18)	( $O_2$ , 9)
( $O_6$ , 8)	( $O_7$ , 11)	( $O_7$ , 7)
( $O_7$ , 2)	( $O_6$ , 5)	( $O_0$ , 1)
( $O_0$ , −2)	( $O_0$ , −1)	( $O_6$ , −6)
( $O_1$ , −7)	( $O_9$ , −10)	( $O_8$ , −11)
( $O_8$ , −12)	( $O_1$ , −14)	( $O_1$ , −13)
( $O_9$ , −30)	( $O_8$ , −18)	( $O_9$ , −16)

In the unbalanced thresholds computing phase, member node 1 and member node 2 send $\{(O_4,34),(O_5,28),(O_1,-14),(O_8,-18)\}$ and $\{(O_5,20),(O_4,17),(O_1,-13),(O_9,-16)\}$ to administrator node, respectively. The administrator node then computes partial sums for all received elements according to (9). For object 5, partial sum $P(5)=69$ because $V_1(5)=21$ , $V_2(5)=28$ , and $V_3(5)=20$ are all known. For object 4, partial sum $P(4)=51$ because $V_2(4)=34$ , $V_3(4)=17$ are known but $V_1(4)$ is unknown ( $V_1(4)$ is located in neither the first 2 nor the last 2 cells in list $L_1$ ). Similarly, we can get $P(2)=17$ , $P(8)=-30$ , $P(9)=-46$ , and $P(1)=-27$ . Thus, the top-2 positive partial sum ${\stackrel{-}{\tau }}^{\mathrm{1}}=\mathrm{51}$ and the top-2 negative partial sum ${\underset{\_}{\tau }}^{\mathrm{1}}=-\mathrm{30}$ . According to Algorithm 1, the weights and thresholds for each node are ${\stackrel{-}{\omega }}_{\mathrm{1}}=\mathrm{19}$ , ${\stackrel{-}{\omega }}_{\mathrm{2}}=\mathrm{31}$ , ${\stackrel{-}{\omega }}_{\mathrm{3}}=\mathrm{18.5}$ , ${\underset{\_}{\omega }}_{\mathrm{1}}=-\mathrm{21}$ , ${\underset{\_}{\omega }}_{\mathrm{2}}=-\mathrm{16}$ , and ${\underset{\_}{\omega }}_{\mathrm{3}}=-\mathrm{14.5}$ and ${\stackrel{-}{\tau }}_{\mathrm{11}}=\mathrm{14.2}$ , ${\stackrel{-}{\tau }}_{\mathrm{12}}=\mathrm{23.0}$ , ${\stackrel{-}{\tau }}_{\mathrm{13}}=\mathrm{13.8}$ , ${\underset{\_}{\tau }}_{\mathrm{11}}=-\mathrm{12.2}$ , ${\underset{\_}{\tau }}_{\mathrm{12}}=-\mathrm{9.3}$ , and ${\underset{\_}{\tau }}_{\mathrm{13}}=-\mathrm{8.5}$ , respectively.

In the candidate set computing phase, member node 1 and member node 2 send $\{(O_9,-10)\}$ and $\{(O_3,14),(O_8,-11)\}$ to administrator node, respectively. The administrator node then computes partial sums according to (9) and gets $P(5)=69$ , $P(4)=66$ , $P(2)=17$ , $P(3)=14$ , $P(8)=-41$ , $P(9)=-56$ , and $P(1)=-27$ . The top-2 positive partial sum ${\stackrel{-}{\tau }}^{\mathrm{2}}$ and top-2 negative partial sum ${\underset{\_}{\tau }}^{\mathrm{2}}$ are updated to 66 and −56, respectively. The administrator node then computes upper bounds and lower bounds for each received element and gets $U(5)=L(5)=69$ , $U(4)=L(4)=66$ , $U(2)=53.8$ , $L(2)=-0.8$ , $U(3)=51.2$ , $L(3)=-7.5$ , $U(8)=L(8)=-41$ , $U(9)=L(9)=-56$ , $U(1)=-12.8$ , and $L(1)=-39.2$ . Therefore, the candidate set $S=\{5,4,8,9\}$ .

In the top- $\left|K\right|$ elements computing phase, no object-value pair is transmitted because all the object-value pairs in candidate set S are already known. Therefore, the interaction between administrator node and member nodes can be omitted and we can obtain the top-|2| query results $\{(5,69),(4,66)\}$ .

The total number of transmitted object-value pairs in our proposed unbalanced threshold based distributed top- $\left|K\right|$ query algorithm is 11 and twice interactions are required between each member node and administrator node. As for the modified TA based algorithm [38] and the modified TPUT based algorithm [39], the total number of transmitted object-value pairs is 16 and 14, respectively. Meanwhile, the interaction times of these two algorithms are 8 and 3, respectively. We can see that both the interaction times and the number of transmitted data of our proposed scheme are the least among these three algorithms. The performance comparison of these algorithms will be discussed in detail in Section 5.

4. The Distributed Iterative Hard Thresholding Algorithm

4.1. Network Model

We assume that P sinks and N sensor nodes are deployed randomly and uniformly in the surveillance area in the multisink wireless sensor network. Each sink is assigned with an ID ranging from 1 to P and each sensor node is assigned with an ID ranging from 1 to N. The sink with the lowest ID 1 is designated as administrator sink and other sinks are designated as member sinks. We assume that an effective multisink routing protocol, such as the dynamic traffic-aware routing protocol [40] or the scalable gradient-based routing protocol [41], is deployed in the network. Each sensor node can transmit its sensed data to the nearest sink in a multihop manner. The network model is shown in Figure 1.

Figure 1

The network model.

In wireless sensor networks, the spatial correlation among sensed data in the surveillance area implies that any sensed data $x\in R^N$ at a certain time point is of K sparsity. Each sink i takes $M_i$ samples of x using its subsensing matrix $A_i\in R^{M_i\times N}$ and gets $y_i\in R^{M_i\times \mathrm{1}}$ ; that is, $y_i=A_{i}x+z_i$ , where $z_i\in R^{M_i\times \mathrm{1}}$ is noise. Hence, the set of P sinks will obtain $M={\sum }_{i=\mathrm{1}}^P{M}_i$ samples $y=[y_{\mathrm{1}}^T,\dots ,y_P^T{]}^T\in R^{M\times \mathrm{1}}$ using the global sensing matrix $A=[A_{\mathrm{1}}^T,\dots ,A_P^T{]}^T\in R^{M\times N}$ . Therefore, the data collection and synchronization among multiple sinks can be ascribed to the compressive sensing problem (6). We will design a distributed iterative hard thresholding algorithm to recover the sensed data x at all sinks in a cooperative manner.

4.2. Algorithm Design

After setting the initial value of the sensed data $x^{(\mathrm{0})}$ and iteration time to $n\times \mathrm{1}$ zero vectors $\mathit{0}$ and 0, respectively, each sink computes the step size μ by

$$\begin{array}{cc}& \mu ={\left({\mu }_{MN}+{\sigma }_{MN}{F}^{-\mathrm{1}}\left(\mathrm{1}-\alpha \right)\right)}^{-\mathrm{1}/\mathrm{2}},\end{array}$$

(16)

where F is the cumulative distribution function of the Tracy-Widom law of order 1, $1-\alpha$ is the quantile, and parameters ${\mu }_{MN}$ and ${\sigma }_{MN}$ can be computed by

$$\begin{array}{cc}& {\mu }_{MN}={\left(\mathrm{1}+\sqrt{\frac{\left(N-\mathrm{1}\right)}{M}}\right)}^{\mathrm{2}},\\ {\sigma }_{MN}=\frac{\sqrt{M}+\sqrt{N-\mathrm{1}}}{M}{\left(\frac{\mathrm{1}}{\sqrt{M}}+\frac{\mathrm{1}}{\sqrt{N-\mathrm{1}}}\right)}^{\mathrm{1}/\mathrm{3}}.\end{array}$$

(17)

According to the random matrix theory, the step size μ is tight when the entries of sensing matrix A are drawn from normal distribution $N(\mathrm{0,1}/M)$ [39].

After that, each sink computes the intermediate result $z_i^{(t)}$ by

$$\begin{array}{cc}& z_i^{\left(t\right)}=\left\{\begin{array}{cc}{x}^{\left(t\right)}+\mu A_i^T\left(y_i-A_i{x}^{\left(t\right)}\right)\hfill & i=\mathrm{1}\hfill \\ \mu A_i^T\left(y_i-A_i{x}^{\left(t\right)}\right)\hfill & i\ne \mathrm{1}\hfill \end{array}\right.\end{array}$$

(18)

and executes top- $\left|K\right|$ query by running the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm. The administrator sink will obtain the $(t+1)$ th reconstructed result and distribute it to other sinks. The above iteration continues until the difference between two reconstructed results is less than the error threshold θ.

The pseudocode of the distributed iterative hard thresholding algorithm is presented in Algorithm 2.

Algorithm 2: The distributed iterative hard thresholding algorithm.

Input: Sparsity K, error threshold θ, sub-sensing matrix $A_i$ , samples $y_i$ , $i\in \left\{\right.\mathrm{1},\dots ,P\left.\right\}$

$x^{(\mathrm{0})}=\mathbf{0}$ ,   $t=\mathrm{0}$ ;

Computing step size μ according to (16);

Do

 All sinks compute $z_i^{(t)}$ according to (18);

 All sinks run Algorithm 1 and the administrator sink obtains $x^{(t+\mathrm{1})}$ ;

 The administrator sink distributes $x^{(t+\mathrm{1})}$ to other sinks;

While   ${‖x^{(t+\mathrm{1})}-x^{(t)}‖}_2<\theta$

Output: sensed data x

Since the distributed top- $\left|K\right|$ query

$$\begin{array}{cc}& H_K\left(x^{\left(t\right)}+{\displaystyle \sum }_{i=\mathrm{1}}^P\mu A_i^T\left(y_i-A_i{x}^{\left(t\right)}\right)\right)=H_K\left(x^{\left(t\right)}+\mu \left[A_{\mathrm{1}}^T,\dots ,A_P^T\right]\left(\left[\begin{array}{c}{y}_{\mathrm{1}}\\ ⋮\\ y_P\end{array}\right]-\left[\begin{array}{c}{A}_{\mathrm{1}}\\ ⋮\\ A_P\end{array}\right]x^{\left(t\right)}\right)\right)\end{array}$$

(19)

we can assure that the iterative computation in the distributed iterative hard thresholding algorithm equals that in the centralized iterative hard thresholding algorithm (7). Therefore, the recovered sensed data of these two algorithms are identical.

5. Experiment and Analysis

We evaluate the performance of our proposed unbalanced threshold based distributed data collection scheme in this section. The simulation is carried out using Matlab R2014b and Wislab simulator on a MacBook Pro laptop computer with dual core i7 CPU and 8 G memory. There are 50~200 wireless sensor nodes and 4~6 sinks randomly deployed in a 400 × 400 m² surveillance area. Multiple uncorrelated two-dimensional Gaussian distributions have been superposed to simulate the spatial correlated data sources. Note that the Gaussian random matrix is used as the measurement matrix.

We will investigate the data reconstruction accuracy, communication complexity, and computational complexity of our proposed scheme. The signal-to-noise ratio (SNR)

$$\begin{array}{cc}& \text{SNR}=\mathrm{20}\hspace{0.17em}{\log }_{\mathrm{10}}\left(\frac{x}{\left|x-\tilde{x}\right|}\right)\end{array}$$

(20)

is used to measure the data reconstruction accuracy, where x and $\tilde{x}$ are sensed data and reconstructed data, respectively. The number of transmitted data is the number of accumulated data involved in the communication between administrator sink and member sinks. The number of computed data is the number of accumulated data involved in the computation in administrator sink and member sinks. These two indicators are used to measure the communication complexity and computational complexity, respectively.

5.1. Performance Analysis

Figures 2, 3, and 4 show the SNR of reconstructed data, the number of transmitted data, and the number of computed data, respectively, at different data sampling rates. We can conclude that the data reconstruction performance improves with the increase on the data sampling rate. Meanwhile, the number of transmitted data and that of computed data increase too. The reason behind this rule lies in the fact that the increase on the data sampling rate would cause more data to be transmitted and computed. Therefore, the recovered sensed data will be more accurate.

Figure 2

The SNR of reconstructed data at different data sampling rates.

Figure 3

The number of transmitted data at different data sampling rates.

Figure 4

The number of computed data at different data sampling rates.

Figures 5, 6, and 7 show the SNR of reconstructed data, the number of transmitted data, and the number of computed data, respectively, in different surveillance scenarios. The number of uncorrelated two-dimensional Gaussian data sources ranges from 2 to 4. We can conclude that the data reconstruction performance degrades with the increase on the number of uncorrelated data sources. Meanwhile, the number of transmitted data and that of computed data increase at the same time. The reason behind this rule lies in the fact that the increase on the number of uncorrelated data sources leads to the increase on the sparsity of sensed data within the network. Therefore, the data reconstruction performance degrades and more data are required to be transmitted and computed.

Figure 5

The SNR of reconstructed data at different number of data sources.

Figure 6

The number of transmitted data at different number of data sources.

Figure 7

The number of computed data at different number of data sources.

Figures 8, 9, and 10 show the SNR of reconstructed data, the number of transmitted data, and the number of computed data, respectively, at different number of sinks. We can conclude that there are no remarkable differences among the data reconstruction performance with different number of sinks. However, the number of transmitted data and that of computed data increase with the increase of the number of sinks. The reason behind this rule lies in the fact that the increase on the number of sinks has no influence on the data reconstruction performance and only requires more data to be transmitted within the network and computed in the sinks.

Figure 8

The SNR of reconstructed data at different number of sinks.

Figure 9

The number of transmitted data at different number of sinks.

Figure 10

The number of computed data at different number of sinks.

5.2. Performance Comparison

We will compare the performance of our proposed scheme with the original iterative hard thresholding algorithm [25], the modified thresholding algorithm base iterative hard thresholding scheme [38], and the modified three-phase uniform threshold based iterative hard thresholding scheme [39] in this subsection. Here, the last two schemes are referred to as the modified TA based DIHT scheme and the modified TPUT based DIHT scheme, respectively.

Figure 11 shows the comparison of the SNR of these four schemes when the data sampling rate is 50%, the number of data sources is 3, and the number of sinks is 5. We can conclude that there are no remarkable differences among the data reconstruction performance of these schemes. In other words, they can provide the similar data recovery accuracy regardless of the centralized or distributed reconstruction pattern.

Figure 11

The SNR of reconstructed data of different schemes.

Figures 12 and 13 show the number of transmitted data and interaction times of these four schemes in the same experiment settings as in Figure 11. Since the iterative hard thresholding algorithm is a centralized data reconstruction algorithm, all data in the member sinks should be transmitted to the administrator sink for reconstruction and then the recovered data would be resent back to the member sinks for synchronization. Therefore, the number of transmitted data of the IHT algorithm is much higher than that of other three schemes although only one interaction is required.

Figure 12

The number of transmitted data of different schemes.

Figure 13

The iteration times of different schemes.

The interaction times of the modified TA based DIHT scheme dominate that of other three algorithms since only one object-value pair is queried in each interaction during the top- $\left|K\right|$ query process. Meanwhile, the number of transmitted data is relatively high since no efficient data pruning techniques are equipped in this algorithm.

Our proposed unbalanced threshold based distributed data collection scheme requires the fewest data transmission among these four schemes. By adopting unbalanced thresholds, it can adjust the query thresholds adaptively and avoid redundant transmissions between administrator sink and member sinks. Sometimes, all elements in the candidate set S can be obtained in advance in phase II instead of in phase III since reasonable thresholds are computed in the unbalanced threshold based distributed top- $\left|K\right|$ query algorithm. The example illustrated in Section 3.2 has shown this property. Therefore, the interaction times of our proposed scheme are slightly less than that of the modified TPUT based DIHT scheme. The price for the decrease in the number of transmitted data and interaction times is only the computation of unbalanced thresholds, which can be ignored by comparing with the communication energy consumption in wireless sensor nodes.

6. Conclusion

In this paper, we proposed the unbalanced threshold based distributed data collection scheme designed for multisink wireless sensor networks. All sinks can obtain the synchronized sensed data of the whole network through distributed sparse signal reconstruction. Meanwhile, we also designed a distributed top- $\left|K\right|$ query algorithm to reduce the number of transmitted data between administrator sink and member sinks by pruning unnecessary elements exchanging.

The data reconstruction accuracy, communication complexity, and computational complexity of the proposed scheme were analyzed in detail through experiments. Furthermore, we also compare the performance of the proposed scheme with existing centralized and distributed data collection schemes in wireless sensor networks. In the future, we would like to design efficient data collection schemes by utilizing the spatial and temporal correlations among sensed data simultaneously.