Sage Journals: Discover world-class research

Abstract

Existing clustering algorithms of data gathering in wireless sensor networks neglect the impact of event source on the data spatial correlation. In this article, we proposed a compressed sensing–based dynamic clustering algorithm centred on event source. The main challenges of the prescribed scheme are how to model the impact of event source on spatial correlation and how to obtain the location of event source. To solve both the problems, we first formulate the Euclidean distance spatial correlation model and employ joint sparsity model-1 to describe the impact on the spatial correlation caused by event source. Based on these models, we conceive an efficient clustering scheme, which exploits the compressive data for computing the location of event source and for dynamic clustering. Simulation results show that the proposed compressed sensing–based dynamic clustering algorithm centred on event source outperforms the existing data gathering algorithms in decreasing the communication cost, saving the network energy consumption as well as extending the network survival time under a same accuracy. Additionally, the three performance affecting factors, namely, the attenuation coefficient of event sources, the distance between event sources and the number of event sources, are investigated and provided for constituting the application condition of the compressed sensing–based dynamic clustering algorithm centred on event source. The proposed scheme is potential in large-scale wireless sensor networks such as sensor-based IoT application.

Keywords

Wireless sensor networks data gather compressed sensing event source Euclidean distance spatial correlation

Introduction

Considered as an essential bridge connecting with the physical world and human society, wireless sensor networks (WSNs) have been widely applied in medical, space exploration, military applications, smart home and environmental monitoring. However, the energy-efficiency problems of the sensor nodes, namely, the limited processing energy and the highly constrained energy resources, have always been a bottleneck hindering the further development of the network. Therefore, reducing the energy consumption and prolonging the lifetime expectation become challenges for the researchers in designing WSNs.^1,2

In WSNs, traditional data gathering employed multi-hop to forward the raw data to the sink node.^3,4 Thus, large number of redundant transmissions will be picked, leading to tremendous amount of energy waste. More explicitly, nodes which are closer to the sink take more forward tasks than the others, resulting in a rather faster energy consuming speed as well as the reduction of the whole network lifetime. To solve the problem, a promising technique called compressed sensing (CS) theory has brought a revolutionary breakthrough to the information processing field. This theory pointed out that for a compressible signal, a small collection of the linear projections is sufficient for the near perfect reconstruction.^5–8 Rabbat et al.⁹ introduced CS into the single-hop wireless network and compressed data successfully. In the study of Luo et al.¹⁰ and Wang et al.,¹¹ CS was applied in large-scale multi-hop WSNs, efficiently decreasing the communication cost and balancing the energy consumption among nodes. Compared with the existing traditional distributed source coding techniques such as Huffman coding, CS brings the benefit of simple compression at sensor nodes without excessive computational and control overheads, which is more feasible for the computation-limiting and energy-limiting nodes. In order to obtain deeper compressed data, researchers combine CS with routing protocol. Combining CS with power-efficient gathering in sensor information systems (PEGASIS) is one of the most popular routing protocols,¹² to reduce the energy consumption and evenly distribute the energy consumption loads, leading to an increase in network lifetime. However, compared with tree-typed routing, such as the minimum spanning tree, PEGASIS-based schemes minimized communication cost of each hop, rather than that of the whole link, resulting in a suboptimal performance. Furthermore, PEGASIS-based schemes suffer from poor robustness and fairly long latency of data gathering. CS combined with tree-type routing was investigated in the study of Luo et al.,^10,13 for the sake of minimizing the total forwarding energy consumption. But simply applying CS could not improve the throughput of the network. On the contrary, it increases the communication cost of the leaf nodes, as well as the intermediate nodes which are closer to the leaves. For this reason, hybrid CS scheme was proposed,¹⁴ in which only parent nodes with high communication load carried out compressing operation. However, the above studies focused only on plain network, when the network is large, conceiving hierarchical network structure via clustering would be more suitable for network management. Relying on the thought of Leach,¹⁵ CS-based data gathering routing scheme suitable for clustering structure was studied. The author first formulated an energy consumption model to obtain the optimal number of clusters and then designed an efficient deterministic dynamic clustering scheme, to guarantee all cluster heads uniformly distributed approximately. The proposed algorithm cluster-based compressive sensing data collection (CCS) in the study of Nguyen et al.¹⁶ combined CS and clustering utilizing block diagonal matrices (BDMs) as the measurement matrices. CCS discussed the optimal number of clusters for reaching the minimum power consumption and the effect of different sparsifying bases on the CS performance. Xie and Jia¹⁷ proposed a clustering method that used hybrid CS, the literature first proposed an analytical model that studied the relationship between the size of clusters and number of transmissions in the hybrid CS method. Nguyen¹⁸ combined random walk (RW) routing and CS to save energy and achieve longer network lifetime. The above-mentioned studies are constructive; however, it should be noted that all those algorithms neglect the event sources in WSNs. In fact, the event sources would deeply influence the data correlation. In addition, little attention has been devoted to the spatial correlation between sensor readings and the impact of event source on data correlation. Researchers^15–17 used the clustering routing, and they all discussed the optimal number of clusters and kept the fixed cluster number. However, if we take the event source into consideration, the optimal cluster number could be changed because of the impact caused by event sources. They all uniformly reconstructed data at sink finally although they used different gathering routing.

The performance of WSNs is significantly affected by spatial correlation.^19–22 Furthermore, there are some interested event sources impacting on the local spatial correlation of sensor readings, for example, temperature monitoring scenario, where sensors around an ignition point will have more correlated readings, while those nodes far away from the same point would have less correlated readings. Duarte et al.²³ presented two simple jointly sparse signals models, namely, Joint Sparse Model-1 (JSM-1) and Joint Sparse Model-2 (JSM-2), then they designed algorithms to recover multiple signals jointly. Based on JSM model,²⁴ the impact of event sources on data correlation was analysed, and the global factors is capable of increasing the common sparsity was further argued while decreasing the unique sparsity, which would result in a decrease in total sparsity and measurements. The authors clustered nodes via spatial correlation and optimal distance. Of particular note is that in the study of Wang et al.,²⁴ interested event sources were supposed to be uniformly distributed in the network which disagrees with the practice. A more reasonable way is to dynamically cluster the networks according to the location of event sources, as well as the compressing sensor readings within a cluster.

Tackling the above-mentioned challenges, in this article we propose an compressed sensing–based dynamic clustering algorithm centred on event source (CS-DCES) algorithm. The main contributions in this work are summarized as follows:

We focus on WSNs with event sources, which cause the different correlation of raw readings.

We analyse and model the impact of event source on spatial correlation through JSM-1. Distance-based attenuation coefficient matrix is proposed as sparse matrix.

We cluster the sensors centred on the event source. The location of event source could be calculated in each round of reconstruction so as to dynamically re-cluster.

We reconstruct signal within cluster so as to increase the correlations within cluster, while decreasing the measurements needed for accurate reconstruction of original signals.

The main challenges for CS-DCES are (1) how to obtain the location of event sources and (2) how to model the impact of event source on spatial correlation.

The rest of this article is organized as follows. Section ‘System model’ devotes to the system model. A cluster scheme based on spatial correlation model is given in section ‘Cluster scheme based on spatial correlation model’. In section ‘CS-DCES’, we present the CS-DCES algorithm. Simulation results and performance analysis are presented in section ‘Simulation and performance analysis’. Finally, we give our concluding remarks in section ‘Conclusion’.

System model

It is assumed that the WSNs are deployed in a square area with the boundary length of $a$ . We regularly divide the area into $N$ subregions with the assumption that there is only one node in each subregion. Each sensor sample can be considered as an element of compressible signal, then $N$ sensor readings in the same time instant can be denoted by a vector $X = (x_{1}, \dots, x_{N})^{T}$ , where $N$ is the number of sensors in the WSN. The vector $X$ can be transformed into a matrix $H = (h_{ij})_{\sqrt{N} \times \sqrt{N}}$

$\begin{matrix} X_{N \times 1} = (h_{11} \dots h_{1 \sqrt{N}}, \dots, h_{\sqrt{N} 1} \dots h_{\sqrt{N} \sqrt{N}})^{T} \end{matrix}$ (1)

where $h_{ij}$ denotes the sensor reading of subregion $(i, j)$ . Furthermore, the signal intensity of event source can be denoted by vector $V = (v_{1}, \dots, v_{N})^{T}$ , and the vector can be transformed by a matrix $G = (g_{ij})_{\sqrt{N} \times \sqrt{N}}$

$\begin{matrix} V_{N \times 1} = (g_{11} \dots g_{1 \sqrt{N}}, \dots, g_{\sqrt{N} 1} \dots g_{\sqrt{N} \sqrt{N}})^{T} \end{matrix}$ (2)

where $g_{ij}$ denotes the signal intensity of event source in subregion $(i, j)$ . More explicitly, $g_{ij} = 0$ denotes none event source situation.

In WSN, each sensor reading is the summation of signal intensity of event sources, which can be expressed as

$\begin{matrix} X_{N \times 1} = Ψ_{N \times N} V_{N \times 1} = (\begin{matrix} ψ_{11} & \dots & ψ_{1 N} \\ ⋮ & ⋮ \\ ψ_{N 1} & \dots & ψ_{NN} \end{matrix}) (\begin{matrix} g_{11} \\ ⋮ \\ g_{1 \sqrt{N}} \\ ⋮ \\ g_{\sqrt{N} 1} \\ ⋮ \\ g_{\sqrt{N} \sqrt{N}} \end{matrix}) \end{matrix}$ (3)

where $Ψ$ is a distance-based attenuation coefficient matrix. In this article, we exploit the spatial correlation model based on ED. More explicitly, $Ψ$ is defined as follows: assuming that $(x'_{i}, y'_{i})$ and $(x'_{j}, y'_{j})$ denote the location of node $i$ and node $j$ , the distance between those two nodes can be expressed as

$\begin{matrix} d_{ij} = \sqrt{{({x'}_{i} - x_{j}')}^{2} + {({y'}_{i} - y_{j}')}^{2}} \end{matrix}$ (4)

If there is an event source at node $i$ , $p_{i}$ and $p_{j}$ denote received power of node $i$ and node $j$ , respectively, the signal attenuation by ED can be depicted as

$\begin{matrix} P_{j} & = C_{1} \cdot P_{i} \cdot d_{ij}^{- n} \\ = C_{1} \cdot P_{i} \cdot {[\sqrt{{(x_{i}' - x_{j}')}^{2} + {(y_{i}' - y_{j}')}^{2}}]}^{- n} \end{matrix}$ (5)

where $C_{1}$ is a constant, and $n (n \in R^{+})$ denotes the coefficient of signal attenuation. Different n represents different types of event source. The spatial correlation of the two different sensor readings is inversely proportional to ED. The smaller the distance is, the more similar sensor readings are. We then obtain the distance attenuation coefficient matrix $Ψ$ as

$\begin{matrix} ψ_{ij} = ψ_{ji} = C_{1} \cdot {[\sqrt{{(x_{i}' - x_{j}')}^{2} + {(y_{i}' - y_{j}')}^{2}}]}^{- n} \end{matrix}$ (6)

In most of the practical WSNs application, monitoring areas are inaccessible because of their terrains and complex environments, such as the volcano monitoring and forest fire monitoring. It is difficult to regularly deploy network. Assuming that randomly deployed $N$ nodes are denoted by ${n_{1}, \dots, n_{N}}$ , the sparse sensor readings are denoted by $(x_{1}, \dots, x_{N})$ , then matrix $H = (h_{ij})_{\sqrt{N} \times \sqrt{N}}$ records those readings as

$\begin{matrix} X_{N \times 1} = (h_{11} \dots h_{1 \sqrt{N}}, \dots, h_{\sqrt{N} 1} \dots h_{\sqrt{N} \sqrt{N}})^{T} \end{matrix}$ (7)

Rows and columns of the matrix no longer denote the coordinates of nodes; here, the node can obtain its location via global positioning system (GPS) or other GPS-relative position algorithms.^25,26 Vector $V_{N \times 1}$ denotes the event source in WSNs as

$\begin{matrix} V_{N \times 1} = (g_{11} \dots g_{1 \sqrt{N}}, \dots, g_{\sqrt{N} 1} \dots g_{\sqrt{N} \sqrt{N}})^{T} \end{matrix}$ (8)

When there is an event source which is closest to node $n_{i}$ with signal intensity $p$ , we define

$\begin{matrix} g_{j} = {\begin{matrix} p & j = i \\ 0 & j \neq i \end{matrix} \end{matrix}$ (9)

If several equivalent nodes are apart from a same event source with the same shortest distance, randomly select node $i$ from those nodes and let $g_{i} = p$ . Meanwhile, if several event sources equivalently stay nearest from a same node $i$ , $g_{i}$ equals the sum of multiple event source intensity. Here, the intensity of each sensor reading is superposed by $S$ signals of event source as equation (3). According to the projection matrix $Φ$ ²⁷

$\begin{matrix} ϕ_{ij} = \sqrt{s} {\begin{matrix} + 1 & with prob . 1 / 2 s \\ 0 & with prob . 1 - 1 / s \\ - 1 & with prob . 1 / 2 s \end{matrix} \end{matrix}$ (10)

where $s$ is a variable controlling the sparse degree of the random matrix, and if $1 / s = \lg N / N$ , the expected number of nonzero items in each row of $Φ$ is $\lg N$ . In this article, we assume $1 / s = 1$ and $Φ$ is dense. Each sensor sends $M$ data packets, where $M$ is the required number of CS measurement to recover sensory data. The CS measurements of $X$ can be expressed as

$\begin{matrix} Y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{M} \end{matrix}) = Φ X = Φ Ψ V \end{matrix}$ (11)

where $Y$ is the CS measurement vector. In general, the number of event sources $S$ is much smaller than the number of nodes $N$ (i.e. $S << N$ ); therefore, the vector $V$ is sparse. According to the models, $Y$ can be calculated by event source vectors $V$ . Equation (11) satisfies the observation model of CS theory: the original signal $X$ can be reconstructed with an overwhelming probability from $M$ measurements by l₁-norm minimization through the model given by

$\begin{matrix} \hat{V} = \min ∥ V ∥_{l_{1}} \\ s . t . \hat{Y} = Φ X = Φ Ψ V \end{matrix}$ (12)

Then, according to equation (3), the whole sensor readings $\hat{X}$ in WSNs can be calculated after reconstructing the location of event source vector $\hat{V}$ . In the following analyses, we will first discuss a regular deployment which is a special case of random deployment and then present the random deployment.

Cluster scheme based on spatial correlation model

In large-scale WSNs, there is spatial correlation between sensor readings. We model and analyse the sensor readings according to the Joint Sparsity Model-1(JSM-1) of Gupta et al.²¹ We assume that there are $N_{0}$ nodes in WSNs, with $x_{j}$ denoting the reading of node $i$ . In JSM-1, the $x_{j}$ is expressed as

$x_{j} = z_{c} + z_{j}, j \in {1, \dots, N_{0}}$ (13)

$z_{c} = Φ θ_{c}, ∥ θ_{c} ∥_{0} = K_{c}$ (14)

$z_{j} = Φ θ_{j}, ∥ θ_{j} ∥_{0} = K_{j}, j \in {1, \dots, N_{0}}$ (15)

where $z_{c}$ is common to all $x_{j}$ , while $θ_{c}$ is the coefficient vector corresponding to the sparse basis and K_c-sparse. $z_{j}$ is the unique portions of $x_{j}$ , and $θ_{j}$ is the coefficient vector that corresponds to the same sparse basis and K_j-sparse. The condition guaranteeing the correctness of CS reconstruction in equation (12) is given by

$M \geq β \cdot K \cdot \lg N_{0}$ (16)

$K = K_{c} + K_{1} + \dots + K_{N_{0}} = K_{c} + \sum_{j = 1}^{N_{0}} K_{j}$ (17)

where $β$ is a small-value constant, $K$ is the summation of common sparsity $K_{c}$ and unique sparsity $\sum_{j = 1}^{N_{0}} K_{j}$ .

However, because of the complex network environment, there are some independent event sources which affect the spatial correlation of sensors readings in different areas. For example, consider the situation where a group of sensors measure the temperatures of outdoor locations. Global factors (such as the sun and prevailing winds) affect $z_{c}$ , which is equal to all sensors. Also there are local factors, such as animal, water or fires, affect $z_{j}$ . In traditional CS-based data gathering algorithm, $N$ sensor readings are regarded as an N-dimensional signal matrix and totally reconstructed at sink. In that case, $K_{c}$ reduces and $K_{j}$ increases; hence, the $K$ as well as the measurement $M$ increases.

For a small region, event source is a global factor which affects the surrounding sensors readings. The closer a node to the event source is, the more powerful its impact will be. Therefore, we propose a rule that nodes in the neighbourhood of an event source should be classified into one cluster. Assume that $N_{1}$ denotes the number of nodes in a cluster. If we cluster randomly and reconstruct based on the clusters, the total sparsity $K_{intra}$ in a cluster can be expressed as

$K_{intra} = K_{c} + K_{1} + \dots + K_{N_{1}} = K_{c} + \sum_{j = 1}^{N_{1}} K_{j}$ (18)

where $K_{c}$ is the total common sparsity of the cluster, while $\sum_{j = 1}^{N_{1}} K_{j}$ is the total unique sparsity of the cluster. If clusters are constructed based on nodes surrounding the same event resource, the readings of the cluster member nodes are affected by the same event source. As the high spatial correlation enables unique sparsity decrease and common sparsity increase, the total sparsity $K'_{intra}$ of a cluster can be rewritten expressed as

$K'_{intra} = K'_{c} + \sum_{j = 1}^{N_{1}} K'_{j}$ (19)

Of particular note in equation (19) that $K'_{c} > K_{c}$ , but $\sum_{j = 1}^{N_{1}} K'_{j} << \sum_{j = 1}^{N_{1}} K_{j}$ , therefore we have $K'_{intra} < K_{intra}$ . According to equation (16), if reconstructing is based on the clusters, the measurements $M$ will decrease under the same accuracy, resulting in a decrease in communication cost and an improvement in network lifetime.

CS-DCES

For WSNs with event sources we interest, a compressive sensing–based dynamic clustering algorithm is proposed, which centres on the event source according to system model and spatial correlation model. The CS-DCES algorithm is presented in Figure 1.

Figure 1.

Flow chart of CS-DCES.

The main part of CS-DCES will be detailed below:

Obtain the location of event sources. At the initialization process of the algorithm; it is assumed that there are some event sources, and sink has received the whole sensor readings $X_{tot}$ by either the non-CS or the CS one. Based on equation (3), the location vector of event source $V_{tot}$ can be expressed as

$V_{tot} = Ψ^{- 1} X_{tot}$ (20)

Clustering centred on event sources. According to the spatial correlation model, the sink informs the node which is closest to event sources to be the cluster head and then sends a random seed $ξ$ to each cluster head. If there is not only one node holding the former mentioned character, the sink randomly picks up a node from them and orders it to be the cluster head. The cluster heads broadcast their own information, and the rest nodes select the closest cluster head. With its own random seed $ξ$ , the cluster head i generates its projection matrix $Φ'$ combining with its own member node addresses. Figure 2 shows an example of cluster result. In network, there are three event sources and three cluster heads, the other nodes select the closest cluster head and form three clusters.

Gathering data within cluster. Assume that there are $N_{1}$ member nodes in a cluster and each member node sends their reading $X'_{N_{1} \times 1} = (x'_{1}, \dots, x'_{N_{1}})^{T}$ to its cluster head. When each cluster head has received its own member nodes readings, it carries out intra-cluster CS operation mentioned in Algorithm 1 (Table 1). From the description, it can be seen that there are no more great amounts of complex computations, and only some simple linear operations are processed at the cluster head. The measurement vector $Y'_{M_{1} \times 1} = (y'_{1}, \dots, y'_{M_{1}})^{T}$ is computed as soon as the head receiving its node readings.

Reconstruction. Once the sink receives the measurement vector $Y = {Y'_{1}, Y'_{2}, \dots, Y'_{S}}$ sent by the whole cluster heads, it regenerates projection matrix $Φ = {Φ_{1}, \dots, Φ_{S}}$ according to the known random seed $ξ$ and node addresses. Then, the sink restructures original signal of each cluster.

Dynamic re-clustering. The sink compares the latest reconstructed location vector ${\hat{V}}_{tot}$ with $V_{tot}$ and judges whether to re-cluster based on the error rule of $ε = | {\hat{V}}_{tot} - V_{tot} |$ . If $ε$ exceeds the predefined threshold $ζ$ , the sink reselects the closest node, which is also close to the new event source, as the new cluster head. In that way the sink re-clusters the nodes. An alternative way is to start a new round with the old scheme to gather data and restructure. Suppose $Ψ = {Ψ_{1}, \dots, Ψ_{S}}$ is sparse basis, the algorithm sink reconstructing the ith cluster data is shown in Algorithm 2 (Table 2).

Cluster head rotation. If the location of event sources is stabilized or the change is below threshold $ζ$ , then each node sends its residual energy to its cluster head at the end of the previous gathering round. The cluster head selects the maximum energy nodes, which have not been selected, as the new cluster head in the next round to distribute the energy consumption loads. Due to the unbalanced energy consumption, the cluster head rotation mechanism avoids WSNs from dying earlier.

Figure 2.

Network clustering diagram.

Table 1.

Algorithm 1.

Algorithm 1 Data compressing algorithm for cluster head in a cluster
Require: $x_{j}$ , $Ψ = (ψ)_{M \times N_{1}}$
Ensure: $Y'_{M \times 1}$
Steps:
1: When cluster head receives $x_{j}$ from its cluster child node and $A_{M \times N_{1}} = (a_{1}, \dots, a_{N_{1}})$
2: for i = 1:N₁
3: $a_{j} = x_{j} (ψ_{ij}, \dots, ψ_{Mj})^{T}$
4: end
6: for i = 1:M
7: $y'_{i} = \sum_{j = 1}^{N_{1}} A_{ij}$
8: end
9: Send $Y'_{M \times 1}$ to sink
10: end

Table 2.

Algorithm 2.

Algorithm 2 Sink restructures the data of $i^{th}$ cluster
Require: $Y$ , $Φ$ , $Ψ$ , $V_{tot}$ , $ζ$
Ensure: ${\hat{V}}_{tot}$ , ${\hat{X}}_{tot}$
Steps:
1: When Sink received $Y$ from its cluster heads then
2: for i = 1:S
3: ${\hat{V}}_{i} = \arg \min ∥ V_{i} ∥_{0}, s . t . {\hat{Y}}_{i} = Φ_{i} X'_{i} = Φ_{i} Ψ_{i} V_{i}$
4: end
5: ${\hat{V}}_{tot} = \sum_{i = 1}^{S} {\hat{V}}_{i}$
6: ${\hat{X}}_{tot} = Φ {\hat{V}}_{tot}$
7: end
8: $ε = \| {\hat{V}}_{tot} - V_{tot} \|$
9: if $ε > ζ$ then
10: change the cluster heads based on the new event source
11: else goto Algorithm 1
12: end
13: end

Simulation and performance analysis

In this section, we evaluate the performance of CS-DCES algorithm, and the simulation environment is MATLAB 2012b, 2.1 GHz CPU and 4G RAM. The simulation parameters are set as follows: 400 sensor nodes are deployed in the monitoring region with the boundary length of 20 m and S event sources existing. The sink with sustained power supply is located at $x = 20$ , $y = 50$ . It is assumed that the initial node energy is $E_{0} = 0.5 J$ , and the nodes are dead if the remaining power is less than 0. Additionally, we adopt the orthogonal matching pursuit (OMP) method as the reconstruction algorithm.

Traditional CS-based data gathering algorithm, such as compressive data gathering (CDG) of Luo et al.¹⁰ and efficient centralized dynamic clustering (ECDC) method of Wu et al.,¹⁵ view the sensor readings of the whole network as a single signal and completely reconstruct them at sink, while our proposed CS-DCES algorithm groups the nodes with high correlation and reconstructs sensor readings within a cluster individually. For convenience, we name the traditional algorithm as unified restructuring algorithm (CS-URA). The algorithm DCCS in the study of Nguyen et al.¹⁶ combined CS and clustering utilizing BDMs as the measurement matrices. The member nodes send measurements to cluster head directly, and the event sources were neglected in DCCS. The spatial-correlation-based compressive sensing routing (SCSR) algorithm of Wang et al.²⁴ considers the impact of event sources on the data spatial correlation but does not pay attention to the event source or its accurate location nor does its incidence. All those four algorithms, namely, CS-DCES, CS-URA, DCCS and SCSR, will be compared in detail.

The signal-to-noise (SNR) and network lifetime are adopted to evaluate the performance of these algorithms. The SNR can be defined as

$SNR = 10 \times \lg (\frac{∥ X ∥_{2}}{∥ X - \hat{X} ∥_{2}})$ (21)

where $\hat{X}$ is the reconstructed sparse signal of $X$ , while $∥ \cdot ∥_{2}$ denoting the minimization. It can be concluded from equation (21) that the smaller the SNR is, the better performance the algorithm will be. The final SNR result is the average of 1000 of simulations carried out under regularly and randomly deployed networks. Furthermore, the main factors influencing the CS-DCES algorithm are also analysed.

The energy consumption model is defined as¹⁵

$E_{Tx} (L, d) = E_{elec} \times L + ε_{amp} \times L \times d^{2}$ (22)

$E_{Rx} (L) = E_{elec} \times L$ (23)

where $E_{Tx} (L, d)$ represents the energy consumption for transmitting an $L - bit$ message, with $E_{Rx} (L)$ denoting the energy consumption for receiving an $L - bit$ message. $E_{elec}$ is the energy consumption for transmitting or receiving one bit message, and $ε_{amp}$ is the transmission amplifier. Table 3 shows the parameter setting.

Table 3.

Parameter setting.

	Parameters	Value
$N$	The total number of sensors	400
$E_{elec}$	The energy consumption for transmitting or receiving one bit message	50 nJ/bit
$ε_{amp}$	The transmission amplifier	10 pt/bit/m²
$L$	The length of data packet	8 bits
$E_{0}$	Initial node energy	0.5 J
$n$	Attenuation coefficient	4

Performance comparison

It is assumed that there are two event sources at location (x = 15, y = 5) and (x = 5, y = 15), with the attenuation coefficient factor n = 4. Figure 3 shows the SNR comparison results of four different data gathering algorithms. According to Figure 3, we can conclude that (1) with the increase in the measurements $M$ , the SNR increases and finally tends to be stable, but the network energy consumption sustained increases; (2) the SNR of CS-DCES outperforms CS-URA, SCSR and DCCS. The reason is that CS-DCES algorithm clusters nodes surrounding the event source and that the sensor readings within the cluster have high correlation. Therefore, compared with the other three algorithms, the sparsity of a cluster in CS-DCES is the lowest. Furthermore, CS-DCES uses fewer measurements while preserves the same reconstruction accuracy via reconstructing data within cluster. For example, when SNR = 27 dB, the number of measurements is 33, 32 and 23 for CS-URA, SCSR and DCCS, respectively, but the number of CS-DCES algorithm becomes 13, realizing a decrease at 60% compared with CS-URA.

Figure 3.

The relationship between reconstruction SNR and the number of measurements.

Figure 4 shows the relationship between the number of data gathering rounds $r$ and the number of dead sensor nodes, when the packet length is 8 bits and SNR = 27 dB. Simulation results indicate that energy efficiency of CS-DCES significantly outperforms both the other schemes. Moreover, the cluster head rotation mechanism enables almost all the sensor nodes dead in a short time interval, resulting in the CS-DCES distributing the loads among nodes more evenly. For example, the first sensor node is dead after gathering 445, 632 and 1732 rounds, while the whole nodes are dead after 674, 641 and 2073 rounds, which corresponds to CS-URA, SCSR and DCCS, respectively. However, in CS-DCES scheme, the first sensor node is dead after gathering 1892 rounds, while the whole nodes are dead after 2164 rounds. That is to say,the network lifetime is prolonged effectively.

Figure 4.

Network lifetime.

Locate the event source

Getting the location of event source plays a deterministic role on the efficiency of the CS-DCES algorithm. Both CS-URA and CS-DCES reconstruct the location of event sources under system models; however, CS-DCES is capable of making the same accuracy but using fewer measurements. We plot their performances in Figure 5 and the event source distribution map reconstructed by CS-DCES in Figure 6, respectively. It can be concluded that our proposed CS-DCES algorithm can accurately locate the event source and efficiently distinguish the change of locations, which guaranteeing the effectiveness of our algorithm.

Figure 5.

Reconstruction of event source position.

Figure 6.

Event source distribution map: (a) distribution of original event sources and (b) distribution of restructuring event sources.

Performance analysis

In our proposed CS-DCES scheme, there are three factors affecting the performance of the algorithm, namely, attenuation coefficient of event source $n$ , the distance between event sources $d$ and the number of event sources $S$ . In this section, we will investigate how those factors work thoroughly.

We carried out simulations with different attenuation coefficient $n$ (n = (2, 2.5, 3, 3.5, 4, 6, 8)) under two event sources at location (x = 1, y = 1) and (x = 20, y = 20). The simulation result is shown in Figure 7. It can be observed that CS-DCES achieves a higher SNR with fewer measurements $M$ in most cases except n = 2. This is because when n = 2, the effect scope of event sources is expanding, and the maximum SNR is rather low. Therefore, the CS-DCES algorithm does not satisfy the current scenario.

Figure 7.

Attenuation coefficient impact on performance.

We further compare the CS-URA algorithm with our CS-DCES when n = 2 in Figure 8. It can be seen that the accuracy of the CS-URA is lower than the CS-DCES when the measurement $M$ is small. With the increase in $M$ , the performance of two algorithms tend to be close to each other, especially when $M < 76$ . As $M \geq 76$ , the CS-URA outperforms the CS-DCES, which lies in that the CS-DCES clusters nodes affected by the same event source. Another observation can be drawn that as $n$ decreases, the independence of cluster in spatial correlation becomes weaker. In that case, part of the sensor readings in a cluster are mainly affected by their own event source, while the others are affected by multi-sources, thus the total sparsity of the cluster increases. As a result, the SNR becomes lower.

Figure 8.

Comparison of CS-DCES and CS-URA.

Second, we investigate how the distance $d$ between events affects the performance of the CS-DCES algorithm. We set the location of two events in three scenarios with different distances at (x = 3, y = 3) (x = 18, y = 18), (x = 7, y = 5) (x = 13, y = 19) and (x = 10, y = 9) (x = 9, y = 15). The simulation results are all shown in Figure 9. It can be observed that (1) when the distance $d$ is fixed, the SNR increases with $M$ but finally tends to be stable; (2) when d = 15.23 and d = 21.21, the SNR approaches to be 23 and 27 dB, respectively. However, when the event sources are much too close with d = 6.08, the CS-DCES algorithm is not effective. The reason can be explained as the large distance can weaken the interaction between different clusters, and the spatial correlation in a cluster is mainly affected by its own event source. Therefore, the cluster data become sparse, and fewer transmissions are needed.

Figure 9.

Event source distance impact on performance.

Finally, we evaluate the impact of the number of event sources $S$ . We consider three network topologies: (1) network with two event sources locate at (x = 5, y = 15) and (x = 15, y = 5); (2) network with three event sources locate at (x = 3, y = 3), (x = 18, y = 18) and (x = 15, y = 9); (3) network with four event sources locate at (x = 5, y = 5) (x = 5, y = 15) (x = 15, y = 5) and (x = 15, y = 15). For each topology, we set the attenuation coefficient n = 4. It can be seen from Figure 10 that the decrease in $S$ and large value of $d$ lead to a rather better performance. The reason is that when attenuation coefficient is constant, the $d$ decreases and the effect between each cluster increases with the increase in $S$ . Moreover, the performance of the algorithm still stands out even with increasing $S$ and rather long distance.

Figure 10.

Number of event sources impact on performance.

Randomly deployed networks

As a matter of fact, it is difficult to regularly deploy nodes in practice. Therefore, we add the CS-DCES simulation under random deployment. As shown in Figure 11, although the performance of CS-DCES becomes worse compared with regularly deploying, the performance curves of CS-DCES are still superior to the CS-URA ones with lower measurements, and they finally maintain consistent when the measurements increase. Furthermore, the number of measurements is 27 and 92 for CS-DCES and CS-URA when SNR = 24, respectively. Figure 12 indicates that the first sensor node is dead after gathering 242 rounds, while the whole nodes are dead after 320 rounds in CS-URA. However, in CS-DCES, the first sensor node is dead after gathering 1702 rounds and the whole nodes are dead after 1991 rounds, with effectively prolonging the lifetime.

Figure 11.

The relationship between reconstruction SNR and the number of measurements under random deployment.

Figure 12.

Network lifetime under random deployment.

Conclusion

In this article, a CS-DCES algorithm was proposed for data gathering in WSNs, which takes the event sources using compressive sensing and clustering strategy into consideration. To increase the data spatial correlation of a cluster, our proposed CS-DCES algorithm obtains the event sources locations and the dynamically cluster nodes from the location information, leading to a decrease in the unique sparsity, an increase in common sparsity and a reduction in the total sparsity and measurements of each data gathering. More explicitly, we employed the cluster head rotation mechanism to distribute the traffic load more evenly. Simulation results and analysis indicate that the proposed CS-DCES algorithm is capable of minimizing the network communication cost and achieving better balanced consumption throughout the network, while preserving relatively the same reconstruction accuracy under both regularly and randomly deploying nodes. The proposed scheme effectively prolongs the networks lifetime. Finally, we analysed three performance factors, namely, $n$ , $d$ and $S$ . Simulation results illustrate that as $n$ and $d$ increase, $S$ decreases, the CS-DCES achieves a same accuracy with fewer measurements.

In current scenario, we consider the wireless channel in WSNs completely reliable, which is assumed by many existing researches. However, the unreliable links in WSNs is common and the performance of CS-based data gathering scheme is sensitive to unreliable links. As to the future research, it is worthy investigating the application of CS to data gathering with unreliable link.

Footnotes

Handling Editor: George P Efthymoglou

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This paper is supported by the National Science and Technology Major Projects of China under grant nos 2014zx03006003 and 2016zx03001010,National Natural Science Foundation of China no. 61601516 and Anhui Provincial Natural Science Foundation,17080 85MF139.

References

Chong

Gaber

Krishnaswamy

et al . Energy-aware data processing techniques for wireless sensor networks: a review. In: Hameurlain

Küng

Wagner

(eds) Transactions on large-scale data-and knowledge-centered systems III, vol. 106. Berlin, Heidelberg: Springer, 2011, pp.117–137.

Srisooksai

Keamarungsi

Lamsrichan

et al . Practical data compression in wireless sensor networks: a survey. J Netw Comput Appl 2012; 35(1): 37–59.

Al-Karaki

Kamal

. Routing techniques in wireless sensor networks: a survey. IEEE Wirel Commun 2004; 11(6): 6–28.

Huang

Hua

. On energy for progressive and consensus estimation in multihop sensor networks. IEEE T Signal Proces 2011; 59(8): 3863–3875.

Davenport

Duarte

Eldar

et al . Introduction to compressed sensing, vol. 93, no. 1 (Lecture note). Cambridge: Cambridge University Press, 2011, p.2.

Donoho

. Compressed sensing. IEEE T Inform Theory 2006; 52(4): 1289–1306.

Baraniuk

. Compressive sensing. IEEE Signal Proc Mag 2007; 24(4): 118–121.

Candès

Wakin

. An introduction to compressive sampling. IEEE Signal Proc Mag 2008; 25(2): 21–30.

Rabbat

Haupt

Singh

et al . Decentralized compression and predistribution via randomized gossiping. In: Proceedings of the 5th international conference on information processing in sensor networks, Nashville, TN, 19–21 April 2006, pp.51–59. New York: ACM.

10.

Luo

Sun

et al . Compressive data gathering for large-scale wireless sensor networks. In: Proceedings of the 15th annual international conference on mobile computing and networking, Beijing, China, 20–25 September 2009, pp.145–156. New York: ACM.

11.

Wang

Tang

Yin

et al . Data gathering in wireless sensor networks through intelligent compressive sensing. In: Proceedings of the IEEE INFOCOM 2012, Orlando, FL, 25–30 March 2012, pp.603–611. New York: IEEE.

12.

Osamy

Salim

Aziz

. Efficient compressive sensing based technique for routing in wireless sensor networks. INFOCOMP J Comput Sci 2013; 12(1): 1–9.

13.

Luo

Sun

et al . Efficient measurement generation and pervasive sparsity for compressive data gathering. IEEE T Wirel Commun 2010; 9(12): 3728–3738.

14.

Luo

Xiang

Rosenberg

. Does compressed sensing improve the throughput of wireless sensor networks? In: Proceedings of the 2010 IEEE international conference on communications (ICC), Cape Town, South Africa, 23–27 May 2010, pp.1–6. New York: IEEE.

15.

Xiong

Huang

et al . An efficient compressive data gathering routing scheme for large-scale wireless sensor networks. Comput Electr Eng 2013; 39(6): 1935–1946.

16.

Nguyen

Teague

Rahnavard

. CCS: energy-efficient data collection in clustered wireless sensor networks utilizing block-wise compressive sensing. Comput Netw 2016; 106: 171–185.

17.

Xie

Jia

. Transmission-efficient clustering method for wireless sensor networks using compressive sensing. IEEE T Parall Distr 2014; 25(3): 806–815.

18.

Nguyen

. Minimizing energy consumption in random walk routing for Wireless Sensor Networks utilizing compressed sensing. In: Proceedings of the 2013 8th international conference on system of systems engineering, Maui, HI, 2–6 June 2013, pp.297–301. New York: IEEE.

19.

Pattem

Krishnamachari

Govindan

. The impact of spatial correlation on routing with compression in wireless sensor networks. ACM T Sensor Network 2008; 4(4): 24.

20.

Villas

Boukerche

De Oliveira

et al . A spatial correlation aware algorithm to perform efficient data collection in wireless sensor networks. Ad Hoc Netw 2014; 12(1): 69–85.

21.

Gupta

Misra

Garg

. Energy efficient data gathering using prediction-based filtering in wireless sensor networks. Int J Inform Comm Tech 2013; 5(1): 75–94.

22.

Villas

Boukerche

Guidoni

et al . An energy-aware spatio-temporal correlation mechanism to perform efficient data collection in wireless sensor networks. Comput Commun 2013; 36(9): 1054–1066.

23.

Duarte

Sarvotham

Wakin

et al . Joint sparsity models for distributed compressed sensing. In: Proceedings of the workshop on signal processing with adaptive sparse/structured representations, Rennes, 16–18 November 2005, vol. 3, pp.15–19. New York: IEEE.

24.

Wang

Zhang

. Spatial-correlation based compressive sensing routing algorithm in wireless sensor networks. J Inform Eng Univ 2015; 16: 418–423.

25.

Bulusu

Heidemann

Estrin

. GPS-less low-cost outdoor localization for very small devices. IEEE Pers Commun 2000; 7(5): 28–34.

26.

Girod

Estrin

. Robust range estimation using acoustic and multimodal sensing. In: Proceedings of the 2001 IEEE/RSJ international conference on intelligent robots and systems, Maui, HI, 29 October–3 November 2001, vol. 3, pp.1312–1320. New York: IEEE.

27.

Wang

Garofalakis

Ramchandran

. Distributed sparse random projections for refinable approximation. In: Proceedings of the 6th international conference on Information processing in sensor networks, Cambridge, MA, 25–27 April 2007, pp.331–339. New York: ACM.

Dynamic clustering and compressive data gathering algorithm for energy-efficient wireless sensor networks

Abstract

Keywords

Introduction

System model

Cluster scheme based on spatial correlation model

CS-DCES

Simulation and performance analysis

Performance comparison

Locate the event source

Performance analysis

Randomly deployed networks

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References