# Edge Sensing-Enabled Multistage Hierarchical Clustering Deredundancy Algorithm in WSNs

Authors: Rongbo Zhu; Mai Yu; Yuanli Li; Jun Wang; Lu Liu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Due to the defects caused by limited energy, storage capacity, and computing ability, the increasing amount of sensing data has become a challenge in wireless sensor networks (WSNs). To decrease the additional power consumption and extend the lifetime of a WSN, a multistage hierarchical clustering deredundancy algorithm is proposed. In the first stage, a dual-metric distance is employed, and redundant nodes are preliminarily identified by the improvedk-means algorithm to obtain clusters of similar nodes. Then, a Gaussian hybrid clustering classification algorithm is presented to implement data similarity clustering for edge sensing data in the second stage. In the third stage, the clustered sensing data is randomly weighted to deduplicate the spatial correlation data. Detailed experimental results show that, compared with the existing schemes, the proposed deredundancy algorithm can achieve better performance in terms of redundant data ratio, energy consumption, and network lifetime.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are common in people’s lives and are widely used in various fields [1, 2]. WSNs are deployed in different areas to monitor environments and objects, such as temperature, humidity, and seismic events [3, 4]. To obtain accurate sensing data for events, a large number of sensors are utilized to collect the edge sensing data and transmit the data to an aggregation/sink node in a high-frequency manner. In general, edge sensing data have a high spatial-temporal correlation and contain considerable redundant information [5, 6]. Additionally, the transmission of redundant data leads to unnecessary energy consumption and bandwidth costs, which increase the overhead and decrease WSN lifetimes. Therefore, reducing redundant data and the transmission energy consumption to extend network lifetimes becomes a key issue in WSNs.To reduce redundant data effectively, the existing work concentrates on two aspects: optimizing sensing data and predicting sensing data. On the one hand, the former is aimed at reducing redundant sensing data with some optimized schemes. Considering the constrained resources in WSNs, a spatial-temporal correlation data reduction scheme was proposed to determine the optimal sampling strategy for the deployed sensor nodes (SNs) [7]; the strategy reduces the overall sampling/transmission rates while preserving the quality of the data. Considering that the data volume increases with unexpected ratios in WSNs, an integrated divide and conquer method with an enhanced k-means scheme was proposed [8], which removes redundant data from the collected measures. To save the limited energy of WSNs, a data transmission (Dat) protocol, which can reduce the data transmission cost inside each sensor node by removing redundant data to save energy while maintaining a suitable level of accuracy in the received readings at the sink, was presented [9]. To conserve energy and enhance the lifetime of a WSN, reducing the amount of data communicated by exploiting the temporal and spatial correlations of the sensed data is a suitable approach. An energy-efficient semantic clustering model was proposed to mitigate the high-energy consumption problem in a clustered WSN [10]. To reduce the energy consumed during data transmission, an adaptive data reduction method, which is based on a convex combination of two decoupled least-mean-square windowed filters, was proposed [11].On the other hand, the prediction-based scheme tries to reduce sensing data with forecasting schemes. To improve data processing efficiency, a distributed data prediction model based on least squares, which tries to use a data prediction-based filtering scheme, was proposed to decrease transmission data [12]. Alduais et al. [13] presented an updating frequency metric, which is defined as the frequency of updating the model reference parameters during data collection, to evaluate the performance of different multivariate data reduction models for WSNs. To schedule data communications between SNs and a sink to reduce power usage with the aim of maximizing the network lifetime, a prediction-based data communication scheme, which utilizes the hierarchical least-mean-square adaptive filter to predict the measured values both at the source and at the sink, was presented [14].Although the schemes mentioned above provide efficient solutions to reduce redundant sensing data in WSNs, the following defects still need to be addressed comprehensively. Firstly, a large range of edge sensing data and errors in local best values can lead to local characteristics being lost. Then, the errors of sensing data will result in a similarity threshold failure problem. And the existing distance-based correlation reducing redundant sensing data schemes, which only consider the spatial corrections of sensing event and omit the temporal correlations of sensing data, tend to degrade the accuracy of sensing data. Furthermore, prediction-based schemes require relatively long-term data sensing and processing abilities, which increase the burden of resource-limited sensors and decrease the lifetime of WSNs. Hence, it is necessary to consider both spatial and temporal correlations and location and data similarity clustering to decrease the sensing data transmission and processing. Focusing on the issue mentioned above, this paper explores the sensing data deredundancy problem to decrease energy consumption and extend the lifetime of a WSN.The main contributions of this paper are summarized as follows:(1)
A multistage hierarchical clustering similarity deredundancy (MHCSD) algorithm is proposed to reduce the power consumption and extend the lifetime of a WSN. MHCSD considers both spatial and temporal correlations and location and data similarity clustering to overcome the accuracy degradation of sensing data(2)
A dual-metric distance is employed in the first stage, and an improvedk-means algorithm is proposed to judge the similarity of nodes based on the dual-metric distance in sinks. A Gaussian hybrid clustering algorithm is presented to judge the similarity of edge sensing data within the same cluster and can improve the similarity accuracy and the deredundancy ratio. The clustered sensing data are randomly weighted to further deduplicate the spatial correlation data in the third stageThe remainder of this paper is organized as follows. Related work is explored in Section2. Section 3 presents the proposed multistage hierarchical clustering deredundancy algorithm in WSNs. Section 4 shows the experimental results, which verify the proposed scheme. The paper is concluded in Section 5 finally.


## 2. Related Work

Although a large amount of application-specific data are generated in WSNs, most of the sensing data detected by sensors are redundant. Processing and transmitting massive superfluous data can lead to additional power consumption and greatly decrease network lifetime [15, 16]. To improve data processing performance, a path merging protocol, which supports partial discrete wavelet transform-based compression schemes to reduce redundant data transmission in a significant manner through the appropriate aggregation of data packets from merging paths, was proposed in [17]. To manage energy-efficient data collections in WSNs, a data-aware energy conservation scheme and prediction-based data collection framework were proposed to reduce data transmission [18], where the inherent correlation between the consecutive observations of SNs and the data similarity measures between the neighboring SNs are utilized.Considering that the data volume in WSNs is quickly increasing, a hybrid-stream big data analytics model, which utilizes a multidimensional convolutional neural network (CNN), minimal correlation model, and minimal redundancy model to optimize data processing, is proposed to perform big data analysis [19]. To provide a complete description of an environment and make a robust decision, a redundancy removal strategy, which mines the spatial and temporal data from collected data to select the appropriate information before forwarding to a base station or a cluster head (CH) in a WSN, is proposed [20]. To avoid generating, transmitting, and storing unwanted data from redundant messages, an immunization-based redundancy elimination scheme, which independently selects the correct number of acknowledgment frames distributed to respond to variations in the amount of redundant data in a dynamic fashion, was proposed [21]. An image fusion method was proposed based on histogram similarity and multiview weighted sparse representations [22].By introducing histogram similarity, different weights are given to low-resolution high-frequency components and source image high-frequency components, and complementary information is effectively used. Diwakaran et al. [18] used the inherent correlations between the continuous observations of SNs and the data similarity measures of adjacent SNs to reduce data transmission. A new model based on monkey tree search behavior inspired by fauna was explored in [23], and the fuzzy reasoning mechanism was used to complete data collection and dissemination. Rida et al. [24] utilized data aggregation techniques based on the Euclidean distance to reduce similar data. Lin et al. [25] proposed a semantic data annotation method based on semantics. A data clustering method, which groups homogeneous data into clusters and then performs data reduction by selecting the average value of each cluster, was proposed based on histograms for data reduction [26].Additionally, to address the problem of redundant data collected by sensors, data aggregation and semaphore processing based on similar functions are applied in WSNs, and SNs are aggregated with a palm tree method [27]. Wan et al. [28] proposed a similar sensory data aggregation scheme based on fuzzy c-means. A spatial-temporal correlation search mechanism between SNs based on the Euclidean distance is proposed [29]. An energy-saving redundant traffic handling scheme, which utilizes short beacon information to process redundant packets generated in area-based routing, was presented in [30]. The parameter estimation problem was considered in [31], and two censoring algorithms were proposed to enable SNs to transmit sampled data based on local decision-making. The dual prediction scheme is used to reduce the transmission between cluster nodes and CHs, while the data compression scheme is used to reduce the traffic between CHs and sink nodes [32]. A low redundancy data acquisition scheme, which selects some nodes for data detection and transmits less data to CHs, was proposed based on matrix completion [33]. To reduce transmitted data, a differential data processing (DDP) method was proposed in [34].Although there are many effective deredundancy processing schemes in WSNs, the following limitations still need to be addressed. Data correlation analysis does not consider homologous data, which can result in a lower deredundancy ratio and loss of local characteristics. Furthermore, unconscionable deredundancy can degrade the accuracy of sensing data. Focusing on filling this gap, this paper proposes a multiphase hierarchical clustering similarity deredundancy algorithm to overcome the limitations mentioned above.


## 3. Proposed Scheme

### 3.1. System Model

There is a setS=s1,s2,⋯,sn composed of n SNs. And the edge sensor nodes will collect data. The system model is shown in Figure 1, and Table 1 lists the notation that we use in the paper.Figure 1
System model.Table 1
Notation.
SymbolDescriptionKNumber of similar clustersβThe effect ofDPi,j on the weight of Di,j, weight scaling factornNode sizemNumber of similar clustersK1Number of data similar clustersαiGaussian mixture coefficientzj1Gaussian mixture componentsγj1,iThe posterior probability of the Gaussian mixtureρj1Cluster markers of samplexj1tjμiThe average of the componentsρLagrange multiplierβiRandom weighting factoreMinimizing the squared error in clustering ofk-meansEelecPower consumption of a circuit for sending or receiving dataεmp,εfsEnergy consumption of signal amplifiersEPEnergy consumption per unit of dataDEi,jEuclidean distanceDPi,jPearson correlation distanceDi,jSpatial similarity distanceμ¯iThe mean of clusterCiℵn×n covariance matrixρj1Cluster markersDCi,j1tjThe random weighted deredundancy of sensing data inCi,j1The sink calculates the similar distances between nodes according to the coordinates of the nodes and divides the nodes intoK clusters according to the similar distances S=C1,C2,C3,⋯,CK, where Ci∩Cj=∅i≠j. CHi of each cluster collects the sensing data generated by the nodes in the cluster at time tj as set DCHhtj=x1tj,x2tj,⋯,xntj. Gaussian mixed clustering is adopted to classify the collected data into similar clusters and then classifies the nodes in the cluster as Ci=Ci,1,Ci,2,Ci,3,⋯,Ci,m, Ci,j=si,j,1,si,j,2,⋯,si,j,k, where 1≤i≤K,1≤j≤m.


### 3.2. Deredundancy Algorithm

The proposed MHCSD algorithm includes three stages: the local clustering stage, the similar data clustering stage, and the data deredundancy processing stage. In addition, the framework of MHCSD is shown in Figure2. In the first stage, the sink will perform the improved k-means clustering algorithm, which clusters similar nodes according to the spatial position coordinates of the nodes. Then, in the second stage, CHs adopt the Gaussian hybrid clustering algorithm to further seek similar clusters. In the third stage, based on the maximum time threshold, the SNs utilize an adaptive step length in the data deredundancy scheme (TCDA) to eliminate duplicate sensing data with spatial-temporal correlations.Figure 2
The framework of the proposed MHCSD.


#### 3.2.1. Similarity of SNs

In the first stage, the node similarity analysis is performed according to the node position coordinates in the sink. To delete duplicate edge sensing data effectively, local clustering needs a precise similarity measure among nodes and sensing data. Among various distance metrics, the Euclidean distance may be the most commonly used in data processing. However, the Euclidean distance only describes the amplitude difference between two eigenvectors, and the Euclidean distance of two feature vectors with different shapes may be smaller than that of feature vectors with similar shapes. To overcome the defect in the Euclidean distance, a dual-metric similarity distanceDi,j is employed:
(1)Di,j=DEi,j+βDPi,j,where DEi,j is the Euclidean distance, DPi,j is the Pearson correlation distance, and β is a scale factor that indicates the influence of DPi,j on the weight of Di,j. In addition, we have
(2)DEi,j=∑h=1hli,h−lj,h2,(3)DPi,j=121−∑h=1hli,h−l¯i,hlj,h−l¯j,h∑h=1hli,h−l¯i,h2∑h=1hlj,h−l¯j,h2.The dual-metric similarity distanceDi,jmeets three distance characteristics: positivity, symmetry, and reflexivity. In terms of Di,j, any active feature vector pair can be compared from both the amplitude of the Euclidean distance and the change in the shape of the related distance.ForS=s1,s2,⋯,sn, the spatial position coordinate li of node si is xi,yi. The sink performs the improved k-means algorithm as shown in Algorithm 1.Algorithm 1: ImpkMeans(L,K).
Input: L=l1,l2,⋯,ln;KOutput: Result of cluster division C=C1,C2,⋯,CKRandomly chosesKsample from L as initial mean vector μ1,μ2,⋯,μKRepeatCi⟵∅1≤i≤KForj⟵1,2,⋯,ndoSolving the distancelj and all kinds of μi1≤i≤K:Di,j⟵DEi,j+βDPi,jThe cluster marker oflj is determined according to the nearest mean vector:τj⟵argminiϵ1,2,⋯,KDi,jCτj⟵Cτj∪ljEnd ForFori⟵1,2,⋯,Kdoμi′⟵1/Ci∑l∈CilIfμi′≠μi thenμi′⟵μiElseKeeping the current mean vector not to changeEnd IfEnd ForUntil The current mean vectors are not updatedAccording to coordinate position setL=l1,l2,⋯,ln, n nodes are classified in K disjoint subsets Ci. C=C1,C2,⋯,CK and C1∪C2∪⋯∪CK=S, where Ci≠∅ and Ci∩Cj=∅, i≠j. In addition, the minimum squared error e is defined as
(4)e=∑i=1K∑l∈Cil−μ¯i22,whereμ¯i=1/Ci∑l∈Cil is the mean vector of cluster Ci.


#### 3.2.2. Similarity of Sensing Data

After clustering the similar nodes by the spatial positions in the first stage, to refine redundant judgments of nodes, the Gaussian hybrid clustering algorithm is adopted in the second stage and is shown in Algorithm2.Algorithm 2: GMMDCHhtj,K1.
Input: DCHhtj=x1tj,x2tj,⋯,xztj;K1Output: ResultC1=C1,1,C1,2,C1,3,⋯,C1,K1RepeatForj1⟵1,2,3,⋯,zdoAccording to (4.7) calculating the posterior probability generated by the mixed componentsxj1tj,γj1,i⟵pMzj1=i∣xj1tj1≤i≤K1End ForFori⟵1,2,3,⋯,K1 doμi′⟵∑j1=1mγj1,ixj1tj/∑j1=1mγj1,iℵi′⟵∑j1=1mγj1,ixj1tj−μi′xj1tj−μi′T/∑j1=1mγj1,iαi′⟵1/m∑j1=1mγj1,iEnd ForUpdate model parameters:αi,μi,ℵi∣1≤i≤K1⟵αi′,μi′,ℵi′∣1≤i≤K1Until Satisfy the stop conditionCi≠∅1≤i≤K1Forj1⟵1,2,3,⋯,z doAccording to (4.7) determining cluster marketsρj1of xj1tjC1,ρj1⟵C1,ρj1∪xj1tjEnd ForTo further analyze the similarity of the data collected simultaneously within clusterCi, the probabilistic model is used to analyze and describe the prototype data in Gaussian hybrid clustering. The cluster division is mainly determined by the posterior probability corresponding to the prototype. The Gaussian distribution is defined as the random variable x in the n-dimensional sample space X, and its probability density function px is defined as
(5)px=12πn/2ℵ1/2e−1/2x−μTℵ−1x−μ,where μ represents the n-dimensional mean vector and ℵ denotes the n×n covariance matrix. Since the Gaussian distribution is determined by the mean vector μ and the covariance matrix ℵ, for the convenience of description, the probability density function for the dependence of the Gaussian distribution on the corresponding parameters is expressed as px∣μ,ℵ. The Gaussian mixture distribution pM is
(6)pM=∑i=1K1αi∙px∣μi,ℵi,where μi and ℵi are the parameters of the ith Gaussian mixed component, αi>0 is the corresponding mixing coefficient, and ∑i=1K1αi=1. pM consists of K1 mixed components, and each mixed component corresponds to a Gaussian distribution.ForS composed of K clusters, data generated by a cluster can be expressed as a set X=X1,X2,⋯,Xn, and Xi=xit1,xit2,⋯,xit2, where 1≤i≤n is the set of time series generated by the sensor node si every T seconds. In the WSN, each CH continues to classify the correlated data of the nodes in the cluster, and through the Gaussian hybrid clustering algorithm, the data collection DCHhtj=x1tj,x2tj,⋯,xztj in similar clusters of the same spatial nodes is simultaneously divided into K1 clusters, where 1≤j&&1≤h≤K1.It is assumed that the random variablezj1∈1,2,⋯,K1 represents the Gaussian mixture component of the sensing data xj1tj of node j1. The prior probability Pzj1=i of zj1 corresponds to αii=1,2,⋯,K1. According to Bayes’ theorem, the posterior distribution of zj1 corresponds to
(7)pMzj1=i∣xj1tj=Pzj1=i∙pMxj1tj∣zj1=ipMxj1tj=αi∙pxj1tj∣μi,ℵi∑l=1kαl∙pxj1tj∣μl,ℵl.pMzj1=i∣xj1tj is expressed as sample xj1tj generated by the ith Gaussian mixture composition of the a posteriori probability, expressed as γj1ii=1,2,⋯,K1.After the Gaussian mixture distribution, the cluster becomes the sample setDCHhtj divided into K1 subclusters and expressed as set C=Ci,1,Ci,2,Ci,3,⋯,Ci,K10<i≤K1; the cluster markers ρj1 of each sample xj1tj are defined as follows:
(8)ρj1=γj1,ii∈1,2,⋯,3argmax.We can solve the parametersαi,μi,ℵi∣1≤i≤K1 as
(9)LLD=ln∏j1=1mpMxj1tj=∑j1=1mln∑i=1K1αi∙pxj1tj∣μi,ℵi.The expectation maximization algorithm is used for the iterative optimization solution. To maximize equation (8) by ∂LLD/∂μi=0, we use
(10)∑j1=1mαi∙pxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μi,ℵixj1tj−μi=0,and with γj1,i=pMzj1=i∣xj1tj, we can obtain
(11)μi=∑j1=1mγj1,ixj1tj∑j1=1mγj1,i,where μi is the mean of each mixed component and can be estimated by the weighted average of samples. The sample weight is the posterior probability γj1i of each sample belonging to the component. Similarly, from ∂LLD/∂ℵi=0, we can obtain
(12)ℵi=∑j1=1mγj1,ixj1tj−μixj1tj−μiT∑j1=1mγj1,i.For mixed coefficientαi, in addition to maximizing LLD, it needs to satisfy αi≥0 and ∑i=1K1αi=1.The Lagrange form ofLLD is
(13)LLD+ρ∑i=1K1αi−1,where ρ is the Lagrange multiplier. The derivative of equation (12) with respect to αi is 0, and
(14)∑j1=1mpxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μl,ℵl+ρ=0.Both sides are multiplied byαi, all of the components of the mixture are summed, ρ=−m, and
(15)αi=1m∑j1=1mγj1,i;namely, the mixing coefficient of each Gaussian component is determined by the average posterior probability of the sample.(1) Elimination of Similar Data. According to the result of cluster set C1=C1,1,C1,2,C1,3,⋯,C1,K1 in the second stage, the CH randomly weights the data generated by the nodes in the cluster with similar data simultaneously, and the TCDA algorithm is proposed to perform time-dependent deredundancy. CHs finally transmit the deredundant data DCi,j1tj to the sink, and we have
(16)DCi,j1tj=β1xwtj+β2xatj+⋯+βvxbtj,where β1,β2,⋯,βv are weighting factors; ∑j=1vβj=1; xwtj,xatj,⋯,xbtjare the sensing data generated from nodes sw,sa,⋯,sb at tj; and sw,sa,⋯,sb∈Cij1&&0<w,a,⋯,b≤n&&0<i≤K&&0<j1≤K1.


#### 3.2.3. HMDA Algorithm

To reduce redundant data in WSNs, a hybrid multistage deredundancy algorithm (HMDA), which combines MHCSD and TCDA to reduce redundant data comprehensively, is proposed based on spatial-temporal correlations, as shown in Algorithm3.Algorithm 3: HMDA(L,K,DCHhtj,K1).
Input:L;K; DCHhtj;K1Output: Deredundancy dataResut1=ImpkMeans(L,K)Rerult2=GMM(DCHhtj,K1)Result3 is that CH randomly weights the data generated by the nodes in the cluster with similar data.TCDA algorithm will process Result3 data.The MHCSD algorithm reduces redundancy in terms of spatial correlations, and the TCDA algorithm further reduces redundant data in terms of temporal correlations. TCDA fully considers the following factors in the process of deduplication: when the range of data variation is large, there is a large error in the local maximum or minimum value and a missing local eigenvalue, and when the data fluctuation is stable, the data similarity threshold cannot work effectively. Considering the ratio of deduplication, TCDA guarantees the timeliness of the sensing data with a maximum time threshold to prevent a failure in the data similarity threshold. Furthermore, an adaptive step size mechanism is proposed to reduce the complexity of calculation and energy consumption. Hence, HMDA reduces network energy consumption and extends the lifetime of a WSN simultaneously. In addition, the flow chart of HMDA is shown in Figure3.Figure 3
The flow chart of HMDA.


### 3.3. Performance Analysis

#### 3.3.1. Algorithm Complexity

In the first stage, the sink aggregates through all node positions, classifies all nodes, and assumes that model training requiresf1 cycles. In the first step, the position set and classification number K of n nodes are input, and the time complexity is On+1; in the second step, K samples are randomly selected as the initial mean vector, and the time complexity is OK; in the third step, the distance between each sample and K means is calculated, and the time complexity is Of1×n×K; in the fourth step, the mean vector is updated, and the time complexity is Of1×K×q&&1<q<n; in the fifth step, the cluster division results are output, and the time complexity is OK×q&&1<q<n. In the second stage, the CH performs a data similarity analysis of the cluster data generated at each moment, assuming that model training requires f2 cycles. The first step is to input the sensing data of z nodes and similarity number K1, and the time complexity is Oz+1; the second step is to calculate the posterior probability generated by each mixed component, and the time complexity is Of2×z; the third step is to calculate each model parameter, and the time complexity is Of2×K1; the fourth step is to calculate the cluster tag’s classification, and the calculation complexity is Oz×K1; the fifth step is to output K1 classification clusters, and the time complexity is Oz×K1. In the third stage, the CHs perform random weighted transmission to reduce redundant data in similar nodes, and the time complexity is Oz×K1.Hence, we can obtain that the complexity of the model scheme ismaxOf1×n×K,Of1×K×q,Of2×z,Of2×K1.


#### 3.3.2. Energy Consumption

Most of the energy in the sensor node is consumed by its transceiver module. The channel model of the transmitter has two kinds of free space models and multipath fading models, and the energy consumption is related not only to the amount of data but also to the transmission distanced. Therefore, the energy consumption ETXN,d of the node to send N-bit data is
(17)ETXN,d=N×Eelec+N×εmp×d4,d>d0,N×Eelec+N×εfs×d2,d≤d0,where Eelec represents the energy consumption of the circuit sending or receiving data and εmp and εfs, respectively, represent the energy consumption of the signal amplifier:
(18)d0=εfsεmp1/2.The energy consumptionERXN of the node receiving N-bit data is
(19)ERXN=N×Eelec.The energy consumption of nodes processingN-bit data is
(20)EPN=N×EP,where EP represents the energy consumption of processing unit data. The node’s remaining energy consumption Er is
(21)Er=E0−ETXN1,d+ERXN2+EPN3,where Er represents the remaining energy consumption of the node, E0 represents the initial energy, N1 represents the total amount of data transmitted, N2 represents the total amount of received data, and N3 represents the total amount of data processing.


## 3.1. System Model

There is a setS=s1,s2,⋯,sn composed of n SNs. And the edge sensor nodes will collect data. The system model is shown in Figure 1, and Table 1 lists the notation that we use in the paper.Figure 1
System model.Table 1
Notation.
SymbolDescriptionKNumber of similar clustersβThe effect ofDPi,j on the weight of Di,j, weight scaling factornNode sizemNumber of similar clustersK1Number of data similar clustersαiGaussian mixture coefficientzj1Gaussian mixture componentsγj1,iThe posterior probability of the Gaussian mixtureρj1Cluster markers of samplexj1tjμiThe average of the componentsρLagrange multiplierβiRandom weighting factoreMinimizing the squared error in clustering ofk-meansEelecPower consumption of a circuit for sending or receiving dataεmp,εfsEnergy consumption of signal amplifiersEPEnergy consumption per unit of dataDEi,jEuclidean distanceDPi,jPearson correlation distanceDi,jSpatial similarity distanceμ¯iThe mean of clusterCiℵn×n covariance matrixρj1Cluster markersDCi,j1tjThe random weighted deredundancy of sensing data inCi,j1The sink calculates the similar distances between nodes according to the coordinates of the nodes and divides the nodes intoK clusters according to the similar distances S=C1,C2,C3,⋯,CK, where Ci∩Cj=∅i≠j. CHi of each cluster collects the sensing data generated by the nodes in the cluster at time tj as set DCHhtj=x1tj,x2tj,⋯,xntj. Gaussian mixed clustering is adopted to classify the collected data into similar clusters and then classifies the nodes in the cluster as Ci=Ci,1,Ci,2,Ci,3,⋯,Ci,m, Ci,j=si,j,1,si,j,2,⋯,si,j,k, where 1≤i≤K,1≤j≤m.


## 3.2. Deredundancy Algorithm

The proposed MHCSD algorithm includes three stages: the local clustering stage, the similar data clustering stage, and the data deredundancy processing stage. In addition, the framework of MHCSD is shown in Figure2. In the first stage, the sink will perform the improved k-means clustering algorithm, which clusters similar nodes according to the spatial position coordinates of the nodes. Then, in the second stage, CHs adopt the Gaussian hybrid clustering algorithm to further seek similar clusters. In the third stage, based on the maximum time threshold, the SNs utilize an adaptive step length in the data deredundancy scheme (TCDA) to eliminate duplicate sensing data with spatial-temporal correlations.Figure 2
The framework of the proposed MHCSD.


### 3.2.1. Similarity of SNs

In the first stage, the node similarity analysis is performed according to the node position coordinates in the sink. To delete duplicate edge sensing data effectively, local clustering needs a precise similarity measure among nodes and sensing data. Among various distance metrics, the Euclidean distance may be the most commonly used in data processing. However, the Euclidean distance only describes the amplitude difference between two eigenvectors, and the Euclidean distance of two feature vectors with different shapes may be smaller than that of feature vectors with similar shapes. To overcome the defect in the Euclidean distance, a dual-metric similarity distanceDi,j is employed:
(1)Di,j=DEi,j+βDPi,j,where DEi,j is the Euclidean distance, DPi,j is the Pearson correlation distance, and β is a scale factor that indicates the influence of DPi,j on the weight of Di,j. In addition, we have
(2)DEi,j=∑h=1hli,h−lj,h2,(3)DPi,j=121−∑h=1hli,h−l¯i,hlj,h−l¯j,h∑h=1hli,h−l¯i,h2∑h=1hlj,h−l¯j,h2.The dual-metric similarity distanceDi,jmeets three distance characteristics: positivity, symmetry, and reflexivity. In terms of Di,j, any active feature vector pair can be compared from both the amplitude of the Euclidean distance and the change in the shape of the related distance.ForS=s1,s2,⋯,sn, the spatial position coordinate li of node si is xi,yi. The sink performs the improved k-means algorithm as shown in Algorithm 1.Algorithm 1: ImpkMeans(L,K).
Input: L=l1,l2,⋯,ln;KOutput: Result of cluster division C=C1,C2,⋯,CKRandomly chosesKsample from L as initial mean vector μ1,μ2,⋯,μKRepeatCi⟵∅1≤i≤KForj⟵1,2,⋯,ndoSolving the distancelj and all kinds of μi1≤i≤K:Di,j⟵DEi,j+βDPi,jThe cluster marker oflj is determined according to the nearest mean vector:τj⟵argminiϵ1,2,⋯,KDi,jCτj⟵Cτj∪ljEnd ForFori⟵1,2,⋯,Kdoμi′⟵1/Ci∑l∈CilIfμi′≠μi thenμi′⟵μiElseKeeping the current mean vector not to changeEnd IfEnd ForUntil The current mean vectors are not updatedAccording to coordinate position setL=l1,l2,⋯,ln, n nodes are classified in K disjoint subsets Ci. C=C1,C2,⋯,CK and C1∪C2∪⋯∪CK=S, where Ci≠∅ and Ci∩Cj=∅, i≠j. In addition, the minimum squared error e is defined as
(4)e=∑i=1K∑l∈Cil−μ¯i22,whereμ¯i=1/Ci∑l∈Cil is the mean vector of cluster Ci.


### 3.2.2. Similarity of Sensing Data

After clustering the similar nodes by the spatial positions in the first stage, to refine redundant judgments of nodes, the Gaussian hybrid clustering algorithm is adopted in the second stage and is shown in Algorithm2.Algorithm 2: GMMDCHhtj,K1.
Input: DCHhtj=x1tj,x2tj,⋯,xztj;K1Output: ResultC1=C1,1,C1,2,C1,3,⋯,C1,K1RepeatForj1⟵1,2,3,⋯,zdoAccording to (4.7) calculating the posterior probability generated by the mixed componentsxj1tj,γj1,i⟵pMzj1=i∣xj1tj1≤i≤K1End ForFori⟵1,2,3,⋯,K1 doμi′⟵∑j1=1mγj1,ixj1tj/∑j1=1mγj1,iℵi′⟵∑j1=1mγj1,ixj1tj−μi′xj1tj−μi′T/∑j1=1mγj1,iαi′⟵1/m∑j1=1mγj1,iEnd ForUpdate model parameters:αi,μi,ℵi∣1≤i≤K1⟵αi′,μi′,ℵi′∣1≤i≤K1Until Satisfy the stop conditionCi≠∅1≤i≤K1Forj1⟵1,2,3,⋯,z doAccording to (4.7) determining cluster marketsρj1of xj1tjC1,ρj1⟵C1,ρj1∪xj1tjEnd ForTo further analyze the similarity of the data collected simultaneously within clusterCi, the probabilistic model is used to analyze and describe the prototype data in Gaussian hybrid clustering. The cluster division is mainly determined by the posterior probability corresponding to the prototype. The Gaussian distribution is defined as the random variable x in the n-dimensional sample space X, and its probability density function px is defined as
(5)px=12πn/2ℵ1/2e−1/2x−μTℵ−1x−μ,where μ represents the n-dimensional mean vector and ℵ denotes the n×n covariance matrix. Since the Gaussian distribution is determined by the mean vector μ and the covariance matrix ℵ, for the convenience of description, the probability density function for the dependence of the Gaussian distribution on the corresponding parameters is expressed as px∣μ,ℵ. The Gaussian mixture distribution pM is
(6)pM=∑i=1K1αi∙px∣μi,ℵi,where μi and ℵi are the parameters of the ith Gaussian mixed component, αi>0 is the corresponding mixing coefficient, and ∑i=1K1αi=1. pM consists of K1 mixed components, and each mixed component corresponds to a Gaussian distribution.ForS composed of K clusters, data generated by a cluster can be expressed as a set X=X1,X2,⋯,Xn, and Xi=xit1,xit2,⋯,xit2, where 1≤i≤n is the set of time series generated by the sensor node si every T seconds. In the WSN, each CH continues to classify the correlated data of the nodes in the cluster, and through the Gaussian hybrid clustering algorithm, the data collection DCHhtj=x1tj,x2tj,⋯,xztj in similar clusters of the same spatial nodes is simultaneously divided into K1 clusters, where 1≤j&&1≤h≤K1.It is assumed that the random variablezj1∈1,2,⋯,K1 represents the Gaussian mixture component of the sensing data xj1tj of node j1. The prior probability Pzj1=i of zj1 corresponds to αii=1,2,⋯,K1. According to Bayes’ theorem, the posterior distribution of zj1 corresponds to
(7)pMzj1=i∣xj1tj=Pzj1=i∙pMxj1tj∣zj1=ipMxj1tj=αi∙pxj1tj∣μi,ℵi∑l=1kαl∙pxj1tj∣μl,ℵl.pMzj1=i∣xj1tj is expressed as sample xj1tj generated by the ith Gaussian mixture composition of the a posteriori probability, expressed as γj1ii=1,2,⋯,K1.After the Gaussian mixture distribution, the cluster becomes the sample setDCHhtj divided into K1 subclusters and expressed as set C=Ci,1,Ci,2,Ci,3,⋯,Ci,K10<i≤K1; the cluster markers ρj1 of each sample xj1tj are defined as follows:
(8)ρj1=γj1,ii∈1,2,⋯,3argmax.We can solve the parametersαi,μi,ℵi∣1≤i≤K1 as
(9)LLD=ln∏j1=1mpMxj1tj=∑j1=1mln∑i=1K1αi∙pxj1tj∣μi,ℵi.The expectation maximization algorithm is used for the iterative optimization solution. To maximize equation (8) by ∂LLD/∂μi=0, we use
(10)∑j1=1mαi∙pxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μi,ℵixj1tj−μi=0,and with γj1,i=pMzj1=i∣xj1tj, we can obtain
(11)μi=∑j1=1mγj1,ixj1tj∑j1=1mγj1,i,where μi is the mean of each mixed component and can be estimated by the weighted average of samples. The sample weight is the posterior probability γj1i of each sample belonging to the component. Similarly, from ∂LLD/∂ℵi=0, we can obtain
(12)ℵi=∑j1=1mγj1,ixj1tj−μixj1tj−μiT∑j1=1mγj1,i.For mixed coefficientαi, in addition to maximizing LLD, it needs to satisfy αi≥0 and ∑i=1K1αi=1.The Lagrange form ofLLD is
(13)LLD+ρ∑i=1K1αi−1,where ρ is the Lagrange multiplier. The derivative of equation (12) with respect to αi is 0, and
(14)∑j1=1mpxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μl,ℵl+ρ=0.Both sides are multiplied byαi, all of the components of the mixture are summed, ρ=−m, and
(15)αi=1m∑j1=1mγj1,i;namely, the mixing coefficient of each Gaussian component is determined by the average posterior probability of the sample.(1) Elimination of Similar Data. According to the result of cluster set C1=C1,1,C1,2,C1,3,⋯,C1,K1 in the second stage, the CH randomly weights the data generated by the nodes in the cluster with similar data simultaneously, and the TCDA algorithm is proposed to perform time-dependent deredundancy. CHs finally transmit the deredundant data DCi,j1tj to the sink, and we have
(16)DCi,j1tj=β1xwtj+β2xatj+⋯+βvxbtj,where β1,β2,⋯,βv are weighting factors; ∑j=1vβj=1; xwtj,xatj,⋯,xbtjare the sensing data generated from nodes sw,sa,⋯,sb at tj; and sw,sa,⋯,sb∈Cij1&&0<w,a,⋯,b≤n&&0<i≤K&&0<j1≤K1.


### 3.2.3. HMDA Algorithm

To reduce redundant data in WSNs, a hybrid multistage deredundancy algorithm (HMDA), which combines MHCSD and TCDA to reduce redundant data comprehensively, is proposed based on spatial-temporal correlations, as shown in Algorithm3.Algorithm 3: HMDA(L,K,DCHhtj,K1).
Input:L;K; DCHhtj;K1Output: Deredundancy dataResut1=ImpkMeans(L,K)Rerult2=GMM(DCHhtj,K1)Result3 is that CH randomly weights the data generated by the nodes in the cluster with similar data.TCDA algorithm will process Result3 data.The MHCSD algorithm reduces redundancy in terms of spatial correlations, and the TCDA algorithm further reduces redundant data in terms of temporal correlations. TCDA fully considers the following factors in the process of deduplication: when the range of data variation is large, there is a large error in the local maximum or minimum value and a missing local eigenvalue, and when the data fluctuation is stable, the data similarity threshold cannot work effectively. Considering the ratio of deduplication, TCDA guarantees the timeliness of the sensing data with a maximum time threshold to prevent a failure in the data similarity threshold. Furthermore, an adaptive step size mechanism is proposed to reduce the complexity of calculation and energy consumption. Hence, HMDA reduces network energy consumption and extends the lifetime of a WSN simultaneously. In addition, the flow chart of HMDA is shown in Figure3.Figure 3
The flow chart of HMDA.


## 3.2.1. Similarity of SNs

In the first stage, the node similarity analysis is performed according to the node position coordinates in the sink. To delete duplicate edge sensing data effectively, local clustering needs a precise similarity measure among nodes and sensing data. Among various distance metrics, the Euclidean distance may be the most commonly used in data processing. However, the Euclidean distance only describes the amplitude difference between two eigenvectors, and the Euclidean distance of two feature vectors with different shapes may be smaller than that of feature vectors with similar shapes. To overcome the defect in the Euclidean distance, a dual-metric similarity distanceDi,j is employed:
(1)Di,j=DEi,j+βDPi,j,where DEi,j is the Euclidean distance, DPi,j is the Pearson correlation distance, and β is a scale factor that indicates the influence of DPi,j on the weight of Di,j. In addition, we have
(2)DEi,j=∑h=1hli,h−lj,h2,(3)DPi,j=121−∑h=1hli,h−l¯i,hlj,h−l¯j,h∑h=1hli,h−l¯i,h2∑h=1hlj,h−l¯j,h2.The dual-metric similarity distanceDi,jmeets three distance characteristics: positivity, symmetry, and reflexivity. In terms of Di,j, any active feature vector pair can be compared from both the amplitude of the Euclidean distance and the change in the shape of the related distance.ForS=s1,s2,⋯,sn, the spatial position coordinate li of node si is xi,yi. The sink performs the improved k-means algorithm as shown in Algorithm 1.Algorithm 1: ImpkMeans(L,K).
Input: L=l1,l2,⋯,ln;KOutput: Result of cluster division C=C1,C2,⋯,CKRandomly chosesKsample from L as initial mean vector μ1,μ2,⋯,μKRepeatCi⟵∅1≤i≤KForj⟵1,2,⋯,ndoSolving the distancelj and all kinds of μi1≤i≤K:Di,j⟵DEi,j+βDPi,jThe cluster marker oflj is determined according to the nearest mean vector:τj⟵argminiϵ1,2,⋯,KDi,jCτj⟵Cτj∪ljEnd ForFori⟵1,2,⋯,Kdoμi′⟵1/Ci∑l∈CilIfμi′≠μi thenμi′⟵μiElseKeeping the current mean vector not to changeEnd IfEnd ForUntil The current mean vectors are not updatedAccording to coordinate position setL=l1,l2,⋯,ln, n nodes are classified in K disjoint subsets Ci. C=C1,C2,⋯,CK and C1∪C2∪⋯∪CK=S, where Ci≠∅ and Ci∩Cj=∅, i≠j. In addition, the minimum squared error e is defined as
(4)e=∑i=1K∑l∈Cil−μ¯i22,whereμ¯i=1/Ci∑l∈Cil is the mean vector of cluster Ci.


## 3.2.2. Similarity of Sensing Data

After clustering the similar nodes by the spatial positions in the first stage, to refine redundant judgments of nodes, the Gaussian hybrid clustering algorithm is adopted in the second stage and is shown in Algorithm2.Algorithm 2: GMMDCHhtj,K1.
Input: DCHhtj=x1tj,x2tj,⋯,xztj;K1Output: ResultC1=C1,1,C1,2,C1,3,⋯,C1,K1RepeatForj1⟵1,2,3,⋯,zdoAccording to (4.7) calculating the posterior probability generated by the mixed componentsxj1tj,γj1,i⟵pMzj1=i∣xj1tj1≤i≤K1End ForFori⟵1,2,3,⋯,K1 doμi′⟵∑j1=1mγj1,ixj1tj/∑j1=1mγj1,iℵi′⟵∑j1=1mγj1,ixj1tj−μi′xj1tj−μi′T/∑j1=1mγj1,iαi′⟵1/m∑j1=1mγj1,iEnd ForUpdate model parameters:αi,μi,ℵi∣1≤i≤K1⟵αi′,μi′,ℵi′∣1≤i≤K1Until Satisfy the stop conditionCi≠∅1≤i≤K1Forj1⟵1,2,3,⋯,z doAccording to (4.7) determining cluster marketsρj1of xj1tjC1,ρj1⟵C1,ρj1∪xj1tjEnd ForTo further analyze the similarity of the data collected simultaneously within clusterCi, the probabilistic model is used to analyze and describe the prototype data in Gaussian hybrid clustering. The cluster division is mainly determined by the posterior probability corresponding to the prototype. The Gaussian distribution is defined as the random variable x in the n-dimensional sample space X, and its probability density function px is defined as
(5)px=12πn/2ℵ1/2e−1/2x−μTℵ−1x−μ,where μ represents the n-dimensional mean vector and ℵ denotes the n×n covariance matrix. Since the Gaussian distribution is determined by the mean vector μ and the covariance matrix ℵ, for the convenience of description, the probability density function for the dependence of the Gaussian distribution on the corresponding parameters is expressed as px∣μ,ℵ. The Gaussian mixture distribution pM is
(6)pM=∑i=1K1αi∙px∣μi,ℵi,where μi and ℵi are the parameters of the ith Gaussian mixed component, αi>0 is the corresponding mixing coefficient, and ∑i=1K1αi=1. pM consists of K1 mixed components, and each mixed component corresponds to a Gaussian distribution.ForS composed of K clusters, data generated by a cluster can be expressed as a set X=X1,X2,⋯,Xn, and Xi=xit1,xit2,⋯,xit2, where 1≤i≤n is the set of time series generated by the sensor node si every T seconds. In the WSN, each CH continues to classify the correlated data of the nodes in the cluster, and through the Gaussian hybrid clustering algorithm, the data collection DCHhtj=x1tj,x2tj,⋯,xztj in similar clusters of the same spatial nodes is simultaneously divided into K1 clusters, where 1≤j&&1≤h≤K1.It is assumed that the random variablezj1∈1,2,⋯,K1 represents the Gaussian mixture component of the sensing data xj1tj of node j1. The prior probability Pzj1=i of zj1 corresponds to αii=1,2,⋯,K1. According to Bayes’ theorem, the posterior distribution of zj1 corresponds to
(7)pMzj1=i∣xj1tj=Pzj1=i∙pMxj1tj∣zj1=ipMxj1tj=αi∙pxj1tj∣μi,ℵi∑l=1kαl∙pxj1tj∣μl,ℵl.pMzj1=i∣xj1tj is expressed as sample xj1tj generated by the ith Gaussian mixture composition of the a posteriori probability, expressed as γj1ii=1,2,⋯,K1.After the Gaussian mixture distribution, the cluster becomes the sample setDCHhtj divided into K1 subclusters and expressed as set C=Ci,1,Ci,2,Ci,3,⋯,Ci,K10<i≤K1; the cluster markers ρj1 of each sample xj1tj are defined as follows:
(8)ρj1=γj1,ii∈1,2,⋯,3argmax.We can solve the parametersαi,μi,ℵi∣1≤i≤K1 as
(9)LLD=ln∏j1=1mpMxj1tj=∑j1=1mln∑i=1K1αi∙pxj1tj∣μi,ℵi.The expectation maximization algorithm is used for the iterative optimization solution. To maximize equation (8) by ∂LLD/∂μi=0, we use
(10)∑j1=1mαi∙pxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μi,ℵixj1tj−μi=0,and with γj1,i=pMzj1=i∣xj1tj, we can obtain
(11)μi=∑j1=1mγj1,ixj1tj∑j1=1mγj1,i,where μi is the mean of each mixed component and can be estimated by the weighted average of samples. The sample weight is the posterior probability γj1i of each sample belonging to the component. Similarly, from ∂LLD/∂ℵi=0, we can obtain
(12)ℵi=∑j1=1mγj1,ixj1tj−μixj1tj−μiT∑j1=1mγj1,i.For mixed coefficientαi, in addition to maximizing LLD, it needs to satisfy αi≥0 and ∑i=1K1αi=1.The Lagrange form ofLLD is
(13)LLD+ρ∑i=1K1αi−1,where ρ is the Lagrange multiplier. The derivative of equation (12) with respect to αi is 0, and
(14)∑j1=1mpxj1tj∣μi,ℵi∑l=1K1αl∙pxj1tj∣μl,ℵl+ρ=0.Both sides are multiplied byαi, all of the components of the mixture are summed, ρ=−m, and
(15)αi=1m∑j1=1mγj1,i;namely, the mixing coefficient of each Gaussian component is determined by the average posterior probability of the sample.(1) Elimination of Similar Data. According to the result of cluster set C1=C1,1,C1,2,C1,3,⋯,C1,K1 in the second stage, the CH randomly weights the data generated by the nodes in the cluster with similar data simultaneously, and the TCDA algorithm is proposed to perform time-dependent deredundancy. CHs finally transmit the deredundant data DCi,j1tj to the sink, and we have
(16)DCi,j1tj=β1xwtj+β2xatj+⋯+βvxbtj,where β1,β2,⋯,βv are weighting factors; ∑j=1vβj=1; xwtj,xatj,⋯,xbtjare the sensing data generated from nodes sw,sa,⋯,sb at tj; and sw,sa,⋯,sb∈Cij1&&0<w,a,⋯,b≤n&&0<i≤K&&0<j1≤K1.


## 3.2.3. HMDA Algorithm

To reduce redundant data in WSNs, a hybrid multistage deredundancy algorithm (HMDA), which combines MHCSD and TCDA to reduce redundant data comprehensively, is proposed based on spatial-temporal correlations, as shown in Algorithm3.Algorithm 3: HMDA(L,K,DCHhtj,K1).
Input:L;K; DCHhtj;K1Output: Deredundancy dataResut1=ImpkMeans(L,K)Rerult2=GMM(DCHhtj,K1)Result3 is that CH randomly weights the data generated by the nodes in the cluster with similar data.TCDA algorithm will process Result3 data.The MHCSD algorithm reduces redundancy in terms of spatial correlations, and the TCDA algorithm further reduces redundant data in terms of temporal correlations. TCDA fully considers the following factors in the process of deduplication: when the range of data variation is large, there is a large error in the local maximum or minimum value and a missing local eigenvalue, and when the data fluctuation is stable, the data similarity threshold cannot work effectively. Considering the ratio of deduplication, TCDA guarantees the timeliness of the sensing data with a maximum time threshold to prevent a failure in the data similarity threshold. Furthermore, an adaptive step size mechanism is proposed to reduce the complexity of calculation and energy consumption. Hence, HMDA reduces network energy consumption and extends the lifetime of a WSN simultaneously. In addition, the flow chart of HMDA is shown in Figure3.Figure 3
The flow chart of HMDA.


## 3.3. Performance Analysis

### 3.3.1. Algorithm Complexity

In the first stage, the sink aggregates through all node positions, classifies all nodes, and assumes that model training requiresf1 cycles. In the first step, the position set and classification number K of n nodes are input, and the time complexity is On+1; in the second step, K samples are randomly selected as the initial mean vector, and the time complexity is OK; in the third step, the distance between each sample and K means is calculated, and the time complexity is Of1×n×K; in the fourth step, the mean vector is updated, and the time complexity is Of1×K×q&&1<q<n; in the fifth step, the cluster division results are output, and the time complexity is OK×q&&1<q<n. In the second stage, the CH performs a data similarity analysis of the cluster data generated at each moment, assuming that model training requires f2 cycles. The first step is to input the sensing data of z nodes and similarity number K1, and the time complexity is Oz+1; the second step is to calculate the posterior probability generated by each mixed component, and the time complexity is Of2×z; the third step is to calculate each model parameter, and the time complexity is Of2×K1; the fourth step is to calculate the cluster tag’s classification, and the calculation complexity is Oz×K1; the fifth step is to output K1 classification clusters, and the time complexity is Oz×K1. In the third stage, the CHs perform random weighted transmission to reduce redundant data in similar nodes, and the time complexity is Oz×K1.Hence, we can obtain that the complexity of the model scheme ismaxOf1×n×K,Of1×K×q,Of2×z,Of2×K1.


### 3.3.2. Energy Consumption

Most of the energy in the sensor node is consumed by its transceiver module. The channel model of the transmitter has two kinds of free space models and multipath fading models, and the energy consumption is related not only to the amount of data but also to the transmission distanced. Therefore, the energy consumption ETXN,d of the node to send N-bit data is
(17)ETXN,d=N×Eelec+N×εmp×d4,d>d0,N×Eelec+N×εfs×d2,d≤d0,where Eelec represents the energy consumption of the circuit sending or receiving data and εmp and εfs, respectively, represent the energy consumption of the signal amplifier:
(18)d0=εfsεmp1/2.The energy consumptionERXN of the node receiving N-bit data is
(19)ERXN=N×Eelec.The energy consumption of nodes processingN-bit data is
(20)EPN=N×EP,where EP represents the energy consumption of processing unit data. The node’s remaining energy consumption Er is
(21)Er=E0−ETXN1,d+ERXN2+EPN3,where Er represents the remaining energy consumption of the node, E0 represents the initial energy, N1 represents the total amount of data transmitted, N2 represents the total amount of received data, and N3 represents the total amount of data processing.


## 3.3.1. Algorithm Complexity

In the first stage, the sink aggregates through all node positions, classifies all nodes, and assumes that model training requiresf1 cycles. In the first step, the position set and classification number K of n nodes are input, and the time complexity is On+1; in the second step, K samples are randomly selected as the initial mean vector, and the time complexity is OK; in the third step, the distance between each sample and K means is calculated, and the time complexity is Of1×n×K; in the fourth step, the mean vector is updated, and the time complexity is Of1×K×q&&1<q<n; in the fifth step, the cluster division results are output, and the time complexity is OK×q&&1<q<n. In the second stage, the CH performs a data similarity analysis of the cluster data generated at each moment, assuming that model training requires f2 cycles. The first step is to input the sensing data of z nodes and similarity number K1, and the time complexity is Oz+1; the second step is to calculate the posterior probability generated by each mixed component, and the time complexity is Of2×z; the third step is to calculate each model parameter, and the time complexity is Of2×K1; the fourth step is to calculate the cluster tag’s classification, and the calculation complexity is Oz×K1; the fifth step is to output K1 classification clusters, and the time complexity is Oz×K1. In the third stage, the CHs perform random weighted transmission to reduce redundant data in similar nodes, and the time complexity is Oz×K1.Hence, we can obtain that the complexity of the model scheme ismaxOf1×n×K,Of1×K×q,Of2×z,Of2×K1.


## 3.3.2. Energy Consumption

Most of the energy in the sensor node is consumed by its transceiver module. The channel model of the transmitter has two kinds of free space models and multipath fading models, and the energy consumption is related not only to the amount of data but also to the transmission distanced. Therefore, the energy consumption ETXN,d of the node to send N-bit data is
(17)ETXN,d=N×Eelec+N×εmp×d4,d>d0,N×Eelec+N×εfs×d2,d≤d0,where Eelec represents the energy consumption of the circuit sending or receiving data and εmp and εfs, respectively, represent the energy consumption of the signal amplifier:
(18)d0=εfsεmp1/2.The energy consumptionERXN of the node receiving N-bit data is
(19)ERXN=N×Eelec.The energy consumption of nodes processingN-bit data is
(20)EPN=N×EP,where EP represents the energy consumption of processing unit data. The node’s remaining energy consumption Er is
(21)Er=E0−ETXN1,d+ERXN2+EPN3,where Er represents the remaining energy consumption of the node, E0 represents the initial energy, N1 represents the total amount of data transmitted, N2 represents the total amount of received data, and N3 represents the total amount of data processing.


## 4. Experimental Results

### 4.1. Experimental Setup

To verify the effectiveness of the proposed method, the temperature sensing data from the Intel Berkeley Laboratory are used [35]; these data include 54 nodes, and each node collects sensing data every 0.5 minutes. The map is shown in Figure 4. To verify the deredundancy ratio of edge sensing data and the network lifetime, the data transmission model and node energy consumption model are adopted. The experiments consider the following metrics: the deredundancy ratio, the deredundancy error, the influence of the amount of similar data clusters K1 on the deredundancy ratio, and the energy consumption. The proposed HMDA will be compared with the TCDA, TSDA, and Dat algorithms [9]. The parameters and their values are shown in Table 2.Figure 4
The map of sensor nodes in the experiment.Table 2
Parameters of the experiments.
ParameterValueDurationFeb. 28~Apr. 5, 2004Area coverage42m×33mObservation parameterTemperatureNode size of WSNs54The number of perceived data collected/ten thousand230Collection interval (s)31Distance of CHs and sink (m)10Eelec (nJ/bit)50εmp (pJ/bit/m4)0.0013εfs (pJ/bit/m2)100EP (nJ/bit)5E0 (J)5


### 4.2. Performance Evaluation

First, the performance results of the three stages are analyzed separately. In the first stage, clustering classification positions of similar nodes are obtained; in the second stage, clustering classification of similar data nodes is obtained; in the third stage, as a result of the first and second stages, the generated sensing data are made deredundant by means of random weighting. Second, the influence ofK1 on the deredundancy ratio in the second stage is analyzed. Finally, the energy consumption is analyzed with Dat [9], TCDA, TSDA, and HMDA.In the first stage, the sink performs clustering according to the nodes’ coordinate positions by running the improvedk-means clustering algorithm. K is assumed to be 4, and β={0,0.3,0.5,0.7,1}. The results of the four clusters also change significantly as β varies. The diamond in the figure represents the cluster center of the four clusters. The node’s cluster distribution probability is shown in Table 3, and the clustering results are shown in Figure 5.Table 3
Node distribution probability in clusters.
Node IDCluster 1Cluster 2Cluster 3Cluster 4060%40%00260%40%0050080%20%90080%20%100040%60%1920%0080%2020%0080%3260%40%003360%40%0045040%60%046040%60%0Figure 5
Node clustering of the improvedk-means scheme with varying β.
(a)
β=0(b)
β=0.3(c)
β=0.5(d)
β=0.7(e)
β=1According to the probability ratio, the sink classifies the nodes that are prone to change into corresponding clusters. As shown in Table3, the classification results are C1=0,2,21,22,23,24,25,26,27,28,29,30,31,32,33, C2=1,34,35,36,37,38,39,40,41,42,43,44, C3=3,4,5,6,7,8,9,45,46,47,48,49,50,51,52,53, and C4=10,11,12,13,14,15,16,17,18,19,20.In the second stage, the CHs perform Gaussian mixture clustering. By successively acquiring edge sensing data from nodes within each cluster, the CHs can analyze data similarity according to further improve the deredundancy ratio. Similar classification results in clusterC1 are shown in Figure 6.Figure 6
Data similarity distribution ofC1.As shown in Figure6, C1 is divided into 4 subclusters: C11=22,25,28,30,32, C12=23,24,26, C13=27,29,31,33, and C14=0,2,21. Similarly, cluster C2 includes 3 subclusters: C21=1,34,35,36, C22=37,38,39, and C23=40,41,43,44; C3 is classified into C31=3,4,5,6,7, C32=8,9,45,46, andC33=47,48,49,50,51,52,53; and C4 is divided into C41=10,11,12,C42=13,14,15,16, andC43=17,18,19,20.In the third stage, the data in similar clusters will be randomly weighted to optimize the redundancy ratio. For subclusterC13=27,29,31,33 in cluster C1, the deredundancy performance, redundancy error, and mean square error are shown in Figures 7 and 8 and Table 4, respectively.Figure 7
Deredundancy result ofC13.Figure 8
Deredundancy error ofC13.Table 4
The mean square errors of nodes inC13.
NodeMean square error270.035290.004310.034330.006As shown in Figure7, the sensing data of subcluster C13 tend to be the middle values with randomly weighted optimization. The sensing data of node 29 and node 33 are close to the deredundancy results. However, the values of node 27 and node 31 are relatively far away. From Figure 8, we can see that the mean square errors of nodes 29 and 33 are relatively lower than those of nodes 27 and 31. According to the results in Table 4, it can be seen that the mean square errors of nodes 27, 29, 31, and 33 are 0.035, 0.004, 0.034, and 0.006, respectively, which indicates that even if the data are similar, there are still differences between the sensing data. Therefore, for the methods of data similarity analysis with the coordinates of nodes, the lack of spatial correlation analysis can cause greater errors. Multistage clustering improves the accuracy of sensing data similarity.Since the deredundancy ratio of MHCSD is related to the data similarity clusteringK1 in the second stage and the value of K1 affects the accuracy of the data correlation, the effect of K1 on the deredundancy ratio is shown in Figure 9.Figure 9
Effect ofK1 on deredundancy ratio.As shown in Figure9, the deredundancy ratio gradually decreases as K1 increases. When K1=1, it indicates that clusters C1, C2, C3, and C4 are not divided into any similar subclusters, and MHCSD treats all nodes in clusters C1, C2, C3, and C4 as redundant nodes, which perform random weighting to optimize sensing data. Therefore, the deredundancy ratio is maximized. However, when K1=1, it is equivalent to clustering all nodes by position similarity without considering the data similarity cluster, which leads to a larger error. When K1=10, MHCSD classifies the nodes into 10 similar subdata clusters in each cluster C1, C2, C3, and C4 and randomly weights them to deduplicate the sensing data. Hence, the redundancy ratio is the lowest, which guarantees the accuracy of the deredundant data. To ensure both the accuracy of the data and the deredundancy ratio of the data, we set K1=4 in the following performance analysis.Figure10 shows that as the number of nodes increases, the deredundancy ratio also increases and varies between 65% and 75%. When the number of nodes is 23, the deredundancy ratio is the highest (75%). When the number of nodes is less than 3, the proposed scheme omits the spatial correlation deredundancy and transmits the sensing data to the corresponding CHs, which degrades the deredundancy ratio. When the number of nodes is larger than 3, MHCSD performs a spatial correlation deredundancy algorithm, deduplicates redundant nodes in clusters, and obviously improves the deredundancy ratio.Figure 10
The deredundancy ratio of MHCSD.As seen from Figure11, the deredundancy ratio of the HMDA algorithm varies between 97.50% and 98.0%, which is obviously higher than those of TCDA and Dat. Compared with TCDA and Dat, the deredundancy ratio of HMDA increases by 1.7% and 4.7%, respectively. Therefore, HMDA combines MHCSD and TCDA to reduce redundant data comprehensively and can further remove 70% of the redundant data. Additionally, the accuracy of the deredundancy nodes is maintained between 0.004 and 0.035, and within the allowable error range for a user, the deredundancy ratio reaches the highest. The results in Figure 11 also verify that HMDA is effective in improving the deredundancy ratio based on spatial-temporal correlations.Figure 11
Deredundancy ratio of different schemes.The energy consumed by different schemes is shown in Figure12. The energy consumed by the four algorithms increases gradually as the number of nodes increases. Among the different schemes, the energy consumption of HMDA is much lower than those of the other three algorithms. For the proposed HMDA scheme, energy consumption increases very slowly. When the number of nodes is 50, the energy consumption of HMDA is only 0.12 J, which is obviously lower than those of the other three algorithms. The reason is that HMDA will adaptively perform both spatial correlation and temporal correlation analyses.Figure 12
Energy consumptions of different schemes.The network lifetimes of different schemes are shown in Figure13. When the number of nodes is lower than 15, the lifetimes of HMDA, TCDA, Dat, and MHCSD remain stable at 260 s, 250 s, 120 s, and 15 s, respectively. The reason is that the deredundancy ratios of the 4 schemes are 97.5%, 96.3%, 93%, and 70%, which ensures that all nodes perform the same data processing scheme with constant energy consumption. It is obvious that the lifetime of HMDA is longer than that of the other 3 schemes. Especially when the number of nodes increases to 50, the lifetime of HMDA is 109 s, which is 12.6, 3.0, and 3.9 times higher than those of MHCSD, TCDA, and Dat, respectively. The results in Figures 11–13 demonstrate that the proposed HMDA scheme can achieve better performance in terms of the deredundant ratio, energy consumption, and network lifetime.Figure 13
Lifetimes of different schemes.


## 4.1. Experimental Setup

To verify the effectiveness of the proposed method, the temperature sensing data from the Intel Berkeley Laboratory are used [35]; these data include 54 nodes, and each node collects sensing data every 0.5 minutes. The map is shown in Figure 4. To verify the deredundancy ratio of edge sensing data and the network lifetime, the data transmission model and node energy consumption model are adopted. The experiments consider the following metrics: the deredundancy ratio, the deredundancy error, the influence of the amount of similar data clusters K1 on the deredundancy ratio, and the energy consumption. The proposed HMDA will be compared with the TCDA, TSDA, and Dat algorithms [9]. The parameters and their values are shown in Table 2.Figure 4
The map of sensor nodes in the experiment.Table 2
Parameters of the experiments.
ParameterValueDurationFeb. 28~Apr. 5, 2004Area coverage42m×33mObservation parameterTemperatureNode size of WSNs54The number of perceived data collected/ten thousand230Collection interval (s)31Distance of CHs and sink (m)10Eelec (nJ/bit)50εmp (pJ/bit/m4)0.0013εfs (pJ/bit/m2)100EP (nJ/bit)5E0 (J)5


## 4.2. Performance Evaluation

First, the performance results of the three stages are analyzed separately. In the first stage, clustering classification positions of similar nodes are obtained; in the second stage, clustering classification of similar data nodes is obtained; in the third stage, as a result of the first and second stages, the generated sensing data are made deredundant by means of random weighting. Second, the influence ofK1 on the deredundancy ratio in the second stage is analyzed. Finally, the energy consumption is analyzed with Dat [9], TCDA, TSDA, and HMDA.In the first stage, the sink performs clustering according to the nodes’ coordinate positions by running the improvedk-means clustering algorithm. K is assumed to be 4, and β={0,0.3,0.5,0.7,1}. The results of the four clusters also change significantly as β varies. The diamond in the figure represents the cluster center of the four clusters. The node’s cluster distribution probability is shown in Table 3, and the clustering results are shown in Figure 5.Table 3
Node distribution probability in clusters.
Node IDCluster 1Cluster 2Cluster 3Cluster 4060%40%00260%40%0050080%20%90080%20%100040%60%1920%0080%2020%0080%3260%40%003360%40%0045040%60%046040%60%0Figure 5
Node clustering of the improvedk-means scheme with varying β.
(a)
β=0(b)
β=0.3(c)
β=0.5(d)
β=0.7(e)
β=1According to the probability ratio, the sink classifies the nodes that are prone to change into corresponding clusters. As shown in Table3, the classification results are C1=0,2,21,22,23,24,25,26,27,28,29,30,31,32,33, C2=1,34,35,36,37,38,39,40,41,42,43,44, C3=3,4,5,6,7,8,9,45,46,47,48,49,50,51,52,53, and C4=10,11,12,13,14,15,16,17,18,19,20.In the second stage, the CHs perform Gaussian mixture clustering. By successively acquiring edge sensing data from nodes within each cluster, the CHs can analyze data similarity according to further improve the deredundancy ratio. Similar classification results in clusterC1 are shown in Figure 6.Figure 6
Data similarity distribution ofC1.As shown in Figure6, C1 is divided into 4 subclusters: C11=22,25,28,30,32, C12=23,24,26, C13=27,29,31,33, and C14=0,2,21. Similarly, cluster C2 includes 3 subclusters: C21=1,34,35,36, C22=37,38,39, and C23=40,41,43,44; C3 is classified into C31=3,4,5,6,7, C32=8,9,45,46, andC33=47,48,49,50,51,52,53; and C4 is divided into C41=10,11,12,C42=13,14,15,16, andC43=17,18,19,20.In the third stage, the data in similar clusters will be randomly weighted to optimize the redundancy ratio. For subclusterC13=27,29,31,33 in cluster C1, the deredundancy performance, redundancy error, and mean square error are shown in Figures 7 and 8 and Table 4, respectively.Figure 7
Deredundancy result ofC13.Figure 8
Deredundancy error ofC13.Table 4
The mean square errors of nodes inC13.
NodeMean square error270.035290.004310.034330.006As shown in Figure7, the sensing data of subcluster C13 tend to be the middle values with randomly weighted optimization. The sensing data of node 29 and node 33 are close to the deredundancy results. However, the values of node 27 and node 31 are relatively far away. From Figure 8, we can see that the mean square errors of nodes 29 and 33 are relatively lower than those of nodes 27 and 31. According to the results in Table 4, it can be seen that the mean square errors of nodes 27, 29, 31, and 33 are 0.035, 0.004, 0.034, and 0.006, respectively, which indicates that even if the data are similar, there are still differences between the sensing data. Therefore, for the methods of data similarity analysis with the coordinates of nodes, the lack of spatial correlation analysis can cause greater errors. Multistage clustering improves the accuracy of sensing data similarity.Since the deredundancy ratio of MHCSD is related to the data similarity clusteringK1 in the second stage and the value of K1 affects the accuracy of the data correlation, the effect of K1 on the deredundancy ratio is shown in Figure 9.Figure 9
Effect ofK1 on deredundancy ratio.As shown in Figure9, the deredundancy ratio gradually decreases as K1 increases. When K1=1, it indicates that clusters C1, C2, C3, and C4 are not divided into any similar subclusters, and MHCSD treats all nodes in clusters C1, C2, C3, and C4 as redundant nodes, which perform random weighting to optimize sensing data. Therefore, the deredundancy ratio is maximized. However, when K1=1, it is equivalent to clustering all nodes by position similarity without considering the data similarity cluster, which leads to a larger error. When K1=10, MHCSD classifies the nodes into 10 similar subdata clusters in each cluster C1, C2, C3, and C4 and randomly weights them to deduplicate the sensing data. Hence, the redundancy ratio is the lowest, which guarantees the accuracy of the deredundant data. To ensure both the accuracy of the data and the deredundancy ratio of the data, we set K1=4 in the following performance analysis.Figure10 shows that as the number of nodes increases, the deredundancy ratio also increases and varies between 65% and 75%. When the number of nodes is 23, the deredundancy ratio is the highest (75%). When the number of nodes is less than 3, the proposed scheme omits the spatial correlation deredundancy and transmits the sensing data to the corresponding CHs, which degrades the deredundancy ratio. When the number of nodes is larger than 3, MHCSD performs a spatial correlation deredundancy algorithm, deduplicates redundant nodes in clusters, and obviously improves the deredundancy ratio.Figure 10
The deredundancy ratio of MHCSD.As seen from Figure11, the deredundancy ratio of the HMDA algorithm varies between 97.50% and 98.0%, which is obviously higher than those of TCDA and Dat. Compared with TCDA and Dat, the deredundancy ratio of HMDA increases by 1.7% and 4.7%, respectively. Therefore, HMDA combines MHCSD and TCDA to reduce redundant data comprehensively and can further remove 70% of the redundant data. Additionally, the accuracy of the deredundancy nodes is maintained between 0.004 and 0.035, and within the allowable error range for a user, the deredundancy ratio reaches the highest. The results in Figure 11 also verify that HMDA is effective in improving the deredundancy ratio based on spatial-temporal correlations.Figure 11
Deredundancy ratio of different schemes.The energy consumed by different schemes is shown in Figure12. The energy consumed by the four algorithms increases gradually as the number of nodes increases. Among the different schemes, the energy consumption of HMDA is much lower than those of the other three algorithms. For the proposed HMDA scheme, energy consumption increases very slowly. When the number of nodes is 50, the energy consumption of HMDA is only 0.12 J, which is obviously lower than those of the other three algorithms. The reason is that HMDA will adaptively perform both spatial correlation and temporal correlation analyses.Figure 12
Energy consumptions of different schemes.The network lifetimes of different schemes are shown in Figure13. When the number of nodes is lower than 15, the lifetimes of HMDA, TCDA, Dat, and MHCSD remain stable at 260 s, 250 s, 120 s, and 15 s, respectively. The reason is that the deredundancy ratios of the 4 schemes are 97.5%, 96.3%, 93%, and 70%, which ensures that all nodes perform the same data processing scheme with constant energy consumption. It is obvious that the lifetime of HMDA is longer than that of the other 3 schemes. Especially when the number of nodes increases to 50, the lifetime of HMDA is 109 s, which is 12.6, 3.0, and 3.9 times higher than those of MHCSD, TCDA, and Dat, respectively. The results in Figures 11–13 demonstrate that the proposed HMDA scheme can achieve better performance in terms of the deredundant ratio, energy consumption, and network lifetime.Figure 13
Lifetimes of different schemes.


## 5. Conclusion

Focusing on the problem of data redundancy in WSNs, a multistage hierarchical clustering deredundancy algorithm is proposed to decrease the additional power consumption and extend the lifetime of a WSN. Based on the improvedk-means clustering method, all nodes are classified according to the node position information and temporal similarity. The Gaussian hybrid clustering method is adopted to improve the redundant similarity of edge nodes. According to the secondary classification results, the sensing data generated by the redundant nodes are randomly weighted to remove the redundant data. Detailed analysis and experimental results show that, compared with the existing schemes, the proposed scheme is superior in terms of the deredundancy ratio, power consumption, and lifetime of a WSN.



---

*Source: 6664324-2021-03-12.xml*