# PCA-Guided Routing Algorithm for Wireless Sensor Networks

Authors: Gong Chen; Liansheng Tan; Yanlin Gong; Wei Zhang
Journal: Journal of Computer Networks and Communications
 (2012)

---

## Abstract

An important performance concern for wireless sensor networks (WSNs) is the total energy dissipated by all the nodes in the network over the course of network lifetime. In this paper, we propose a routing algorithm termed as PCA-guided routing algorithm (PCA-RA) by exploring the principal component analysis (PCA) approach. Our algorithm remarkably reduces energy consumption and prolongs network lifetime by realizing the objective of minimizing the sum of distances between the nodes and the cluster centers in a WSN network. It is demonstrated that the PCA-RA can be efficiently implemented in WSNs by forming a nearly optimalK-means-like clustering structure. In addition, it can decrease the network load while maintaining the accuracy of the sensor measurements during data aggregating process. We validate the efficacy and efficiency of the proposed algorithm by simulations. Both theoretical analyses and simulation results demonstrate that this algorithm can perform significantly with less energy consumption and thus prolong the system lifetime for the networks.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) [1] consist of battery-powered nodes which inherit sensing, computation, and wireless communication capabilities. Although there have been significant improvements in processor design and computing issues, limitations in battery provision still exist, bringing energy resource considerations as the fundamental challenge in WSNs. Consequently, there have been active research efforts devoted to lifting the performance limitations of WSNs. These performance limitations include network throughput, energy consumption and, network lifetime. Network throughput typically refers to the maximum amount of packets that can be successfully collected by the cluster heads (CHs) in the network, energy consumption refers to the minimize energy dissipation that nodes in the network consume, and network lifetime refers to the maximum time limit that nodes in the network remain alive until one or more nodes drain up their energy.The routing algorithms have been specifically designed for WSNs because the energy optimization is an essential design issue. A good routing scheme is helpful in improving these performance limits such as reducing the energy consumption, prolonging the network lifetime, and increasing the network throughput. Network researchers have studied a great variety of routing protocols in WSNs differing based on the application and network architecture. As demonstrated in [2, 3], it can be classified into four categories: flit, hierarchical clustering, location-based routing, and QoS-based routing. The current routing protocols have their own design trade-offs between energy and communication overhead savings, as well as the advantages and disadvantages of each routing technique.As per the representative hierarchical clustering protocol, low energy adaptive clustering hierarchy (LEACH) [4] has simplicity, flexibility, and scalability because its manipulations rely on randomized rotation of the cluster heads (CHs), but its features of unregulated distribution, unbalanced clustering structure, uniform initial energy, and so on, hinder its performance. Based on LEACH, there are many variants, such as [5–8]. LEACH-E [5] more likely selects the nodes with higher energy as the CHs. LEACH-C [5] analytically determines the optimum number of CHs by taking into account the energy spent by all clusters. PEGASIS [6], TEEN [7], and ATEEN [8] improve the energy consumption by optimizing the data transmission pattern. HEED [9] is a complete distributed routing protocol which has different clustering formations and cluster-heads selecting measures. These protocols have many restrictive assumptions and applicable limitations, so it has great improvement space and extensibility. The rapid development of wireless communications technology, and the miniaturization and low cost of sensing devices, have accelerated the development of wireless sensor networks (WSNs) [10, 11]. As in [12], Zytoune et al. proposed a uniform balancing energy routing protocol (UBERP). The BP K-means [13] and BS K-means [14] can improve the structure of clusters and perform better load-balance and less energy consumptions. HMP-RA [15] proposes a solution to address this issue through a hybrid approach that combines two routing strategies, flat multihop routing and hierarchical multihop routing. ESCFR and DCFR can map small changes in nodal remaining energy to large changes in the function value and consider the end-to-end energy consumption and nodal remaining energy [16]. Biologically inspired intelligent algorithms build a hierarchical structure on the network for different kinds of traffic, thus maximizing network utilization, while improving its performance [17].  In the case where sensor nodes are mobile, as in [18, 19], the nodes can adjust their position to help balance energy consumption in areas that have high transmission load and/or mitigate network partition.In this paper, we consider an overarching algorithm that encompasses both performance metrics. It desires to minimize the sum of distances in the clusters. We show that the principal component analysis (PCA) [20], a useful statistical technique that has found application in fields such as face recognition and image compression, and a common technique for finding patterns in data of high dimension, can form a near-optimal K-means-like clustering structure, in which the distance between the non-CH nodes and CHs is near minimized.Moreover, the data aggregating issue associated with the measurements accuracy calls for a careful consideration in scheme about data collecting and fusing. In this paper, we investigate the PCA technology in a high relative measurements context for WSNs. Our objective is to obtain a good approximation to sensor measurements by relying on a few principal components while decreasing the network load.The remainder of this paper is organized as follows. In Section2, we describe the network and energy model. Section 3 presents the PCA-guided routing algorithm (PCA-RA) model and gives numerical results to demonstrate the working mechanism of PCA-RA. Section 4 discusses the PCA-RA algorithm solution strategies. In Section 5, we simulate the PCA-RA and compare it with LEACH and LEACH-E. Finally, Section 6 concludes this paper.


## 2. Syestem Model

### 2.1. The Network Model

Let us consider a two-tier architecture for WSNs. Figure1 shows the physical network topology for such a network. There are three types of nodes in the networks, namely, a base station (BS), the cluster-head nodes (CHNs), and the ordinary sensor nodes (OSNs).Figure 1
Physical topology for two-tier wireless sensor networks.For each cluster of sensor nodes, there is one a CHN, which is different from an OSN in terms of functions. The primary functions of a CHN are (1) data aggregation for data measurements from the local clusters of OSNs and (2) relaying the aggregated information to the BS. For data fusion, a CHN analyzes the content of each measurement it receives and exploits the correlation among the data measurements. An CHN has a limited lifetime, so we need consider rotating the CHNs to balance to the energy consumption.The third component is the BS. We assume that there is sufficient energy resource available at the BS and thus there is no energy constraint at the BS.


### 2.2. The Energy Consumption Model

We compute the energy consumption using the first-order radio model [5]. The equations, which are used to calculate transmission costs and receiving costs for an L-bit message to cross a distance d, are shown below,
(1)ETX(L,d)={L(Eelec+εfsd2),d<d0L(Eelec+εmpd4),d≥d0,ERX(L)=LEelec.
In (1), the electronics energy, Eelec, depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, whereas the amplifier energy, εfsd2 or εmpd4, depends on the distance to the receiver and the acceptable bit-error rate. d0 is the distance threshold.


## 2.1. The Network Model

Let us consider a two-tier architecture for WSNs. Figure1 shows the physical network topology for such a network. There are three types of nodes in the networks, namely, a base station (BS), the cluster-head nodes (CHNs), and the ordinary sensor nodes (OSNs).Figure 1
Physical topology for two-tier wireless sensor networks.For each cluster of sensor nodes, there is one a CHN, which is different from an OSN in terms of functions. The primary functions of a CHN are (1) data aggregation for data measurements from the local clusters of OSNs and (2) relaying the aggregated information to the BS. For data fusion, a CHN analyzes the content of each measurement it receives and exploits the correlation among the data measurements. An CHN has a limited lifetime, so we need consider rotating the CHNs to balance to the energy consumption.The third component is the BS. We assume that there is sufficient energy resource available at the BS and thus there is no energy constraint at the BS.


## 2.2. The Energy Consumption Model

We compute the energy consumption using the first-order radio model [5]. The equations, which are used to calculate transmission costs and receiving costs for an L-bit message to cross a distance d, are shown below,
(1)ETX(L,d)={L(Eelec+εfsd2),d<d0L(Eelec+εmpd4),d≥d0,ERX(L)=LEelec.
In (1), the electronics energy, Eelec, depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, whereas the amplifier energy, εfsd2 or εmpd4, depends on the distance to the receiver and the acceptable bit-error rate. d0 is the distance threshold.


## 3. PCA-Guided Routing Algorithm Model

PCA is a classic technique in statistical data analysis, data compression, and image processing. PCA transforms a number of correlated variables into a number of uncorrelated variables called principal components. The objective of PCA is to reduce the dimensionality of the dataset, but not only retain most of the original variability in the data. The first principal component accounts for as much of the variability in the data as possible. Mathematically, how to pick up the dimensions with the largest variances is equivalent to finding the best low-rank approximation of the data via the singular value decomposition (SVD) [21].The design of routing algorithm is important in wireless sensor networks. Although plenty of interests are drawn on it, there is still a challenge to face on the aspect of efficiency and energy consumption. In this section, we will describe the notations about PCA-guided routing algorithm model firstly and then propose the PCA-guided clustering model, and finally, we will present the PCA-guided data aggregating model.


### 3.1. Notations

LetX={x1,x2,…,xn} represents the location coordinate matrix of a set of n sensors, Y={y1,y2,…,yn} represents the centered data matrix, where yi=xi-x¯, which defines the centered distance vector column wise, and x¯=∑ixi/n is the mean vector column wise of X matrix.LetM={m1,m2⋯mp} be a group of measurements collecting from the sampling period. Each sensor generates a stream of data. Let DN×P be a matrix with elements Dij, 1⩽i⩽n, 1⩽j⩽p, being the measurement taken by sensor i at point j. Let QN×P be a centered matrix with elements qij=dij-di./n, di.=∑jdij.


### 3.2. PCA-Guided Clustering Model

We define the equation for the SVD of matrixY [22] as follows:
(2)Y=∑kλkukvk.
The covariance matrix (ignoring the factor 1/n) is
(3)∑i(xi-x¯)T(xi-x¯)=YTY.
The principal components vk are eigenvectors satisfying
(4)YTYvk=λk2vk,vk=YTukλk2.


#### 3.2.1.K-Means Clustering Model

According to [23, 24], we find the PCA dimension reduction automatically by performing data clustering according to the K-means objective function [25, 26]. Using K-means algorithm, it can form a better cluster structure by minimizing the sum of squared errors. We define the squared distance between sensor nodes and cluster centers as
(5)JK=∑k=1K∑i∈Ck(xi-mk)2,
where mk=∑xi∈Ckxi/nk is the center of cluster Ck and nk is the number of sensor nodes in Ck. Given the fact that by minimizing the distance between sensor nodes and cluster centers, the energy consumption can be effectively reduced. Our clustering algorithm is thus designed to be capable of minimizing the above metric JK.For the sake of convenience, let us start with the case ofK=2. To obtain the explicit expression for Jk, letting
(6)d(Cp,Cl)=∑i∈Cp∑j∈Cl(xi-xj)2
be the sum of squared distances between two clusters Cp and Cl, after some algebra one obtains the following:
(7)J2=d(C1,C1)2n1+d(C2,C2)2n2,
where n1 and n2 are the numbers of sensor nodes in C1 and C2, n is the total number of sensor nodes; therefore, we get n=n1+n2.If denoting(8)y2-=∑iyiTyin=d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2,(9)JD=n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22],
we thus have
(10)ny2--12JD=n(d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2)-12(n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22])=d(C1,C1)2n+d(C2,C2)2n+d(C1,C2)n-2n1n2d(C1,C2)2nn1n2+n1n2d(C1,C1)2nn12+n1n2d(C2,C2)2nn22=(d(C1,C1)2n+n1n2d(C1,C1)2nn12)+(d(C2,C2)2n+n1n2d(C2,C2)2nn22)+(d(C1,C2)n-2n1n2d(C1,C2)2nn1n2)=(n1d(C1,C1)2nn1+n2d(C1,C1)2nn1)+(n2d(C2,C2)2nn2+n1d(C2,C2)2nn2)=(n1+n2)d(C1,C1)2nn1+(n2+n1)d(C2,C2)2nn2=d(C1,C1)2n1+d(C2,C2)2n2=J2.
That is
(11)J2=ny2--12JD,
where y2¯ is a constant and it denotes the distance between the sensor nodes and the center for all nodes; thus min (JK) is equivalent to max (JD), and because the two resulting clusters are as separated and compact as possible. Because the averaged intracluster distance is greater than the sum of the averaged intercluster distances, that is
(12)d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22>0.
From (9), it is seen that  JD is always positive. This is to say, evidenced from (11), for K=2 minimization of cluster objective function JK is equivalent to maximization of the distance objective JD, which is always positive.WhenK>2, we can do a hierarchical divisive clustering, where each step using the K=2 is a clustering procedure.  This procedure can get an approximated K-means clustering structure.


#### 3.2.2. PCA-Guided Relaxation Model

In [24], it proves that the relaxation solution of JD can get via the principal component. It sets the cluster indicator vector to be
(13)q(i)={n2nn1,ifi∈C1-n1nn2,ifi∈C2.The indicator vector satisfies the sum-to-zero and normalization conditions. Consider the squared distance matrixH=(hij), where hij=∥xi-xj∥2. qTHq=-JD is easily observed.(
1
) The First Relaxation Solution
Letq take any value in [-1,1]; the solution of minimization of J(q)=qTHq/qTq is given by the eigenvector corresponding to the lowest eigenvalue of the equation  Hz=λz.(
2
) The Second Relaxation Solution
LetH^=(h^ij), where the element is given by
(14)h^ij=hij-hi.n-h.jn+h..n2,
in which, hi.=∑jhij, h.j=∑ihij, h..=∑ijhij.
After computing, we haveqTH^q=qTHq=-JD, then relaxing the restriction q, the desired cluster indicator vector is the eigenvector corresponding to the lowest eigenvalue of H^z=λz.(
3
) The Third Relaxation Solution
With some algebra, we can obtainH^=-2YTY. Therefore, the continuous solution for cluster indicator vector is the eigenvector corresponding to the largest eigenvalue of the covariance matrix YTY which by definition, is precisely the principal component v1.


#### 3.2.3. PCA-Guided Clustering Model

According to the mentioned above, forK-means clustering where K=2, the continuous solution of the cluster indicator vector is the principal component v1, that is, clusters C1 and C2 are given by
(15)C1={i∣v1(i)≤0},C2={i∣v1(i)>0}.We can consider using PCA technology to clustering sensor nodes for WSNs. It near minimizes the sum of the distances between the sensor nodes and cluster centers.Example 1.
Let us assume in a WSN there are 20 sensors distributed in the network.X represents the 2D coordinate matrix. 											(16)X=[29.471,4.9162,69.318,65.011,98.299,55.267,40.007,19.879,62.52,73.336,37.589,0.98765,41.986,75.367,79.387,91.996,84.472,36.775,62.08,73.128;19.389,90.481,56.921,63.179,23.441,54.878,93.158,33.52,65.553,39.19,62.731,69.908,39.718,41.363,65.521,83.759,37.161,42.525,59.466,56.574].
Compute the eigenvector of the matrix, YTY, that is, the principal component v1:
(17)v1T=[-0.11623,-0.47282,0.10624,0.058301,0.40896,0.0013808,-0.20539,-0.22552,0.033439,0.17823,-0.15446,-0.45626,-0.067391,0.18908,0.16501,0.22147,0.2697,-0.11445,0.04397,0.13673].
If v1(i)⩽0, sensor i belongs to C1, otherwise it belongs to C2. We depicted the above clustering results into Figure 2.Figure 2
The clustering structure for 20 sensor nodes.WhenK>2, we do a hierarchical divisive clustering, where each step uses the K=2 clustering procedure.In summary, a PCA-guided clustering model can be used to form a nearly optimalK-means-like clustering structure.


### 3.3. PCA-Guided Data Aggregating Model

As mentioned above,DN×P represents the data measurement matrix collected from the sampling period by the cluster heads. Q is a centered matrix about D.The vector{wk}1≤k≤N is the principal components satisfying
(18)QQTwk=λkwk.Because in most cases there exist high correlations between sensor measurements, good approximations to sensor measurements can be obtained by relying on few principal components. The first principal component accounts for as much of the variability in the data as possible, so we can find the first principal component vectorw1, such that their projection data can effectively express the original measurements. Approximations Q^ to Q are obtained by
(19)Q^=w1w1TQ=w1Z,
where
(20)Z=w1TQ.The CHs only send three packets aboutZ, wk, and the mean vector column-wise G of D matrix to the base station:
(21)G=(gi=di.p),di.=∑jdij.Because the mean vector column-wiseG is subtracted by the CHs prior to the aggregation of its value, the base station can add back after the computation of the approximation.Example 2.
If the CH collects the matrixD as follow:
(22)D=[20.320.220.820.320.320.420.520.420.420.320.620.420.420.520.620.520.220.120.420.220.220.320.420.320.320.220.820.320.320.420.520.420.320.220.820.320.320.420.520.420.420.320.620.420.420.520.620.520.220.120.420.220.220.320.420.320.320.220.820.320.320.420.520.420.320.220.820.320.320.420.520.420.220.120.420.220.220.320.420.3],Then the CH can compute the matrixQ and the principal components w1,
(23)Z=w1TQ=[-0.26306,-0.56555,0.93394,-0.26306-0.26306,0.039433,0.34193,0.039433],w1=[0.39468,0.21031,0.21031,0.39468,0.39468,0.21031,0.21031,0.39468,0.39468,0.21031],G=[20.4,20.462,20.262,20.4,20.420.462,20.262,20.4,20.4,20.262],
then the packet about Z, w1, and G  are delivered to the base station. The base station will compute the approximation Q^.After adding back the subtracted mean valueG, we can obtain: (24)D^=[20.29620.17720.76920.29620.29620.41420.53520.41620.40720.34420.65920.40720.40720.47120.53420.47120.20720.14420.45920.20720.20720.27120.33420.27120.29620.17720.76920.29620.29620.41420.53520.41620.29620.17720.76920.29620.29620.41420.53520.41620.40720.34420.65920.40720.40720.47120.53420.47120.20720.14420.45920.20720.20720.27120.33420.27120.29620.17720.76920.29620.29620.41620.53520.41620.29620.17720.76920.29620.29620.41620.53520.41620.20720.14420.45920.20720.20720.27120.33420.271].


## 3.1. Notations

LetX={x1,x2,…,xn} represents the location coordinate matrix of a set of n sensors, Y={y1,y2,…,yn} represents the centered data matrix, where yi=xi-x¯, which defines the centered distance vector column wise, and x¯=∑ixi/n is the mean vector column wise of X matrix.LetM={m1,m2⋯mp} be a group of measurements collecting from the sampling period. Each sensor generates a stream of data. Let DN×P be a matrix with elements Dij, 1⩽i⩽n, 1⩽j⩽p, being the measurement taken by sensor i at point j. Let QN×P be a centered matrix with elements qij=dij-di./n, di.=∑jdij.


## 3.2. PCA-Guided Clustering Model

We define the equation for the SVD of matrixY [22] as follows:
(2)Y=∑kλkukvk.
The covariance matrix (ignoring the factor 1/n) is
(3)∑i(xi-x¯)T(xi-x¯)=YTY.
The principal components vk are eigenvectors satisfying
(4)YTYvk=λk2vk,vk=YTukλk2.


### 3.2.1.K-Means Clustering Model

According to [23, 24], we find the PCA dimension reduction automatically by performing data clustering according to the K-means objective function [25, 26]. Using K-means algorithm, it can form a better cluster structure by minimizing the sum of squared errors. We define the squared distance between sensor nodes and cluster centers as
(5)JK=∑k=1K∑i∈Ck(xi-mk)2,
where mk=∑xi∈Ckxi/nk is the center of cluster Ck and nk is the number of sensor nodes in Ck. Given the fact that by minimizing the distance between sensor nodes and cluster centers, the energy consumption can be effectively reduced. Our clustering algorithm is thus designed to be capable of minimizing the above metric JK.For the sake of convenience, let us start with the case ofK=2. To obtain the explicit expression for Jk, letting
(6)d(Cp,Cl)=∑i∈Cp∑j∈Cl(xi-xj)2
be the sum of squared distances between two clusters Cp and Cl, after some algebra one obtains the following:
(7)J2=d(C1,C1)2n1+d(C2,C2)2n2,
where n1 and n2 are the numbers of sensor nodes in C1 and C2, n is the total number of sensor nodes; therefore, we get n=n1+n2.If denoting(8)y2-=∑iyiTyin=d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2,(9)JD=n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22],
we thus have
(10)ny2--12JD=n(d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2)-12(n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22])=d(C1,C1)2n+d(C2,C2)2n+d(C1,C2)n-2n1n2d(C1,C2)2nn1n2+n1n2d(C1,C1)2nn12+n1n2d(C2,C2)2nn22=(d(C1,C1)2n+n1n2d(C1,C1)2nn12)+(d(C2,C2)2n+n1n2d(C2,C2)2nn22)+(d(C1,C2)n-2n1n2d(C1,C2)2nn1n2)=(n1d(C1,C1)2nn1+n2d(C1,C1)2nn1)+(n2d(C2,C2)2nn2+n1d(C2,C2)2nn2)=(n1+n2)d(C1,C1)2nn1+(n2+n1)d(C2,C2)2nn2=d(C1,C1)2n1+d(C2,C2)2n2=J2.
That is
(11)J2=ny2--12JD,
where y2¯ is a constant and it denotes the distance between the sensor nodes and the center for all nodes; thus min (JK) is equivalent to max (JD), and because the two resulting clusters are as separated and compact as possible. Because the averaged intracluster distance is greater than the sum of the averaged intercluster distances, that is
(12)d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22>0.
From (9), it is seen that  JD is always positive. This is to say, evidenced from (11), for K=2 minimization of cluster objective function JK is equivalent to maximization of the distance objective JD, which is always positive.WhenK>2, we can do a hierarchical divisive clustering, where each step using the K=2 is a clustering procedure.  This procedure can get an approximated K-means clustering structure.


### 3.2.2. PCA-Guided Relaxation Model

In [24], it proves that the relaxation solution of JD can get via the principal component. It sets the cluster indicator vector to be
(13)q(i)={n2nn1,ifi∈C1-n1nn2,ifi∈C2.The indicator vector satisfies the sum-to-zero and normalization conditions. Consider the squared distance matrixH=(hij), where hij=∥xi-xj∥2. qTHq=-JD is easily observed.(
1
) The First Relaxation Solution
Letq take any value in [-1,1]; the solution of minimization of J(q)=qTHq/qTq is given by the eigenvector corresponding to the lowest eigenvalue of the equation  Hz=λz.(
2
) The Second Relaxation Solution
LetH^=(h^ij), where the element is given by
(14)h^ij=hij-hi.n-h.jn+h..n2,
in which, hi.=∑jhij, h.j=∑ihij, h..=∑ijhij.
After computing, we haveqTH^q=qTHq=-JD, then relaxing the restriction q, the desired cluster indicator vector is the eigenvector corresponding to the lowest eigenvalue of H^z=λz.(
3
) The Third Relaxation Solution
With some algebra, we can obtainH^=-2YTY. Therefore, the continuous solution for cluster indicator vector is the eigenvector corresponding to the largest eigenvalue of the covariance matrix YTY which by definition, is precisely the principal component v1.


### 3.2.3. PCA-Guided Clustering Model

According to the mentioned above, forK-means clustering where K=2, the continuous solution of the cluster indicator vector is the principal component v1, that is, clusters C1 and C2 are given by
(15)C1={i∣v1(i)≤0},C2={i∣v1(i)>0}.We can consider using PCA technology to clustering sensor nodes for WSNs. It near minimizes the sum of the distances between the sensor nodes and cluster centers.Example 1.
Let us assume in a WSN there are 20 sensors distributed in the network.X represents the 2D coordinate matrix. 											(16)X=[29.471,4.9162,69.318,65.011,98.299,55.267,40.007,19.879,62.52,73.336,37.589,0.98765,41.986,75.367,79.387,91.996,84.472,36.775,62.08,73.128;19.389,90.481,56.921,63.179,23.441,54.878,93.158,33.52,65.553,39.19,62.731,69.908,39.718,41.363,65.521,83.759,37.161,42.525,59.466,56.574].
Compute the eigenvector of the matrix, YTY, that is, the principal component v1:
(17)v1T=[-0.11623,-0.47282,0.10624,0.058301,0.40896,0.0013808,-0.20539,-0.22552,0.033439,0.17823,-0.15446,-0.45626,-0.067391,0.18908,0.16501,0.22147,0.2697,-0.11445,0.04397,0.13673].
If v1(i)⩽0, sensor i belongs to C1, otherwise it belongs to C2. We depicted the above clustering results into Figure 2.Figure 2
The clustering structure for 20 sensor nodes.WhenK>2, we do a hierarchical divisive clustering, where each step uses the K=2 clustering procedure.In summary, a PCA-guided clustering model can be used to form a nearly optimalK-means-like clustering structure.


## 3.2.1.K-Means Clustering Model

According to [23, 24], we find the PCA dimension reduction automatically by performing data clustering according to the K-means objective function [25, 26]. Using K-means algorithm, it can form a better cluster structure by minimizing the sum of squared errors. We define the squared distance between sensor nodes and cluster centers as
(5)JK=∑k=1K∑i∈Ck(xi-mk)2,
where mk=∑xi∈Ckxi/nk is the center of cluster Ck and nk is the number of sensor nodes in Ck. Given the fact that by minimizing the distance between sensor nodes and cluster centers, the energy consumption can be effectively reduced. Our clustering algorithm is thus designed to be capable of minimizing the above metric JK.For the sake of convenience, let us start with the case ofK=2. To obtain the explicit expression for Jk, letting
(6)d(Cp,Cl)=∑i∈Cp∑j∈Cl(xi-xj)2
be the sum of squared distances between two clusters Cp and Cl, after some algebra one obtains the following:
(7)J2=d(C1,C1)2n1+d(C2,C2)2n2,
where n1 and n2 are the numbers of sensor nodes in C1 and C2, n is the total number of sensor nodes; therefore, we get n=n1+n2.If denoting(8)y2-=∑iyiTyin=d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2,(9)JD=n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22],
we thus have
(10)ny2--12JD=n(d(C1,C1)2n2+d(C2,C2)2n2+d(C1,C2)n2)-12(n1n2n[2d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22])=d(C1,C1)2n+d(C2,C2)2n+d(C1,C2)n-2n1n2d(C1,C2)2nn1n2+n1n2d(C1,C1)2nn12+n1n2d(C2,C2)2nn22=(d(C1,C1)2n+n1n2d(C1,C1)2nn12)+(d(C2,C2)2n+n1n2d(C2,C2)2nn22)+(d(C1,C2)n-2n1n2d(C1,C2)2nn1n2)=(n1d(C1,C1)2nn1+n2d(C1,C1)2nn1)+(n2d(C2,C2)2nn2+n1d(C2,C2)2nn2)=(n1+n2)d(C1,C1)2nn1+(n2+n1)d(C2,C2)2nn2=d(C1,C1)2n1+d(C2,C2)2n2=J2.
That is
(11)J2=ny2--12JD,
where y2¯ is a constant and it denotes the distance between the sensor nodes and the center for all nodes; thus min (JK) is equivalent to max (JD), and because the two resulting clusters are as separated and compact as possible. Because the averaged intracluster distance is greater than the sum of the averaged intercluster distances, that is
(12)d(C1,C2)n1n2-d(C1,C1)n12-d(C2,C2)n22>0.
From (9), it is seen that  JD is always positive. This is to say, evidenced from (11), for K=2 minimization of cluster objective function JK is equivalent to maximization of the distance objective JD, which is always positive.WhenK>2, we can do a hierarchical divisive clustering, where each step using the K=2 is a clustering procedure.  This procedure can get an approximated K-means clustering structure.


## 3.2.2. PCA-Guided Relaxation Model

In [24], it proves that the relaxation solution of JD can get via the principal component. It sets the cluster indicator vector to be
(13)q(i)={n2nn1,ifi∈C1-n1nn2,ifi∈C2.The indicator vector satisfies the sum-to-zero and normalization conditions. Consider the squared distance matrixH=(hij), where hij=∥xi-xj∥2. qTHq=-JD is easily observed.(
1
) The First Relaxation Solution
Letq take any value in [-1,1]; the solution of minimization of J(q)=qTHq/qTq is given by the eigenvector corresponding to the lowest eigenvalue of the equation  Hz=λz.(
2
) The Second Relaxation Solution
LetH^=(h^ij), where the element is given by
(14)h^ij=hij-hi.n-h.jn+h..n2,
in which, hi.=∑jhij, h.j=∑ihij, h..=∑ijhij.
After computing, we haveqTH^q=qTHq=-JD, then relaxing the restriction q, the desired cluster indicator vector is the eigenvector corresponding to the lowest eigenvalue of H^z=λz.(
3
) The Third Relaxation Solution
With some algebra, we can obtainH^=-2YTY. Therefore, the continuous solution for cluster indicator vector is the eigenvector corresponding to the largest eigenvalue of the covariance matrix YTY which by definition, is precisely the principal component v1.


## 3.2.3. PCA-Guided Clustering Model

According to the mentioned above, forK-means clustering where K=2, the continuous solution of the cluster indicator vector is the principal component v1, that is, clusters C1 and C2 are given by
(15)C1={i∣v1(i)≤0},C2={i∣v1(i)>0}.We can consider using PCA technology to clustering sensor nodes for WSNs. It near minimizes the sum of the distances between the sensor nodes and cluster centers.Example 1.
Let us assume in a WSN there are 20 sensors distributed in the network.X represents the 2D coordinate matrix. 											(16)X=[29.471,4.9162,69.318,65.011,98.299,55.267,40.007,19.879,62.52,73.336,37.589,0.98765,41.986,75.367,79.387,91.996,84.472,36.775,62.08,73.128;19.389,90.481,56.921,63.179,23.441,54.878,93.158,33.52,65.553,39.19,62.731,69.908,39.718,41.363,65.521,83.759,37.161,42.525,59.466,56.574].
Compute the eigenvector of the matrix, YTY, that is, the principal component v1:
(17)v1T=[-0.11623,-0.47282,0.10624,0.058301,0.40896,0.0013808,-0.20539,-0.22552,0.033439,0.17823,-0.15446,-0.45626,-0.067391,0.18908,0.16501,0.22147,0.2697,-0.11445,0.04397,0.13673].
If v1(i)⩽0, sensor i belongs to C1, otherwise it belongs to C2. We depicted the above clustering results into Figure 2.Figure 2
The clustering structure for 20 sensor nodes.WhenK>2, we do a hierarchical divisive clustering, where each step uses the K=2 clustering procedure.In summary, a PCA-guided clustering model can be used to form a nearly optimalK-means-like clustering structure.


## 3.3. PCA-Guided Data Aggregating Model

As mentioned above,DN×P represents the data measurement matrix collected from the sampling period by the cluster heads. Q is a centered matrix about D.The vector{wk}1≤k≤N is the principal components satisfying
(18)QQTwk=λkwk.Because in most cases there exist high correlations between sensor measurements, good approximations to sensor measurements can be obtained by relying on few principal components. The first principal component accounts for as much of the variability in the data as possible, so we can find the first principal component vectorw1, such that their projection data can effectively express the original measurements. Approximations Q^ to Q are obtained by
(19)Q^=w1w1TQ=w1Z,
where
(20)Z=w1TQ.The CHs only send three packets aboutZ, wk, and the mean vector column-wise G of D matrix to the base station:
(21)G=(gi=di.p),di.=∑jdij.Because the mean vector column-wiseG is subtracted by the CHs prior to the aggregation of its value, the base station can add back after the computation of the approximation.Example 2.
If the CH collects the matrixD as follow:
(22)D=[20.320.220.820.320.320.420.520.420.420.320.620.420.420.520.620.520.220.120.420.220.220.320.420.320.320.220.820.320.320.420.520.420.320.220.820.320.320.420.520.420.420.320.620.420.420.520.620.520.220.120.420.220.220.320.420.320.320.220.820.320.320.420.520.420.320.220.820.320.320.420.520.420.220.120.420.220.220.320.420.3],Then the CH can compute the matrixQ and the principal components w1,
(23)Z=w1TQ=[-0.26306,-0.56555,0.93394,-0.26306-0.26306,0.039433,0.34193,0.039433],w1=[0.39468,0.21031,0.21031,0.39468,0.39468,0.21031,0.21031,0.39468,0.39468,0.21031],G=[20.4,20.462,20.262,20.4,20.420.462,20.262,20.4,20.4,20.262],
then the packet about Z, w1, and G  are delivered to the base station. The base station will compute the approximation Q^.After adding back the subtracted mean valueG, we can obtain: (24)D^=[20.29620.17720.76920.29620.29620.41420.53520.41620.40720.34420.65920.40720.40720.47120.53420.47120.20720.14420.45920.20720.20720.27120.33420.27120.29620.17720.76920.29620.29620.41420.53520.41620.29620.17720.76920.29620.29620.41420.53520.41620.40720.34420.65920.40720.40720.47120.53420.47120.20720.14420.45920.20720.20720.27120.33420.27120.29620.17720.76920.29620.29620.41620.53520.41620.29620.17720.76920.29620.29620.41620.53520.41620.20720.14420.45920.20720.20720.27120.33420.271].


## 4. PCA-Guided Routing Algorithm Solution Strategies

In Section3, we have actually proposed a PCA-guided clustering and data aggregating model for routing optimization problem in WSNs by theoretical analyses and numerical examples. The following steps provide an overview of the solution strategy.


### 4.1. Initialization Stage

In the first stage, we assume that a set ofN location coordinates are gathered at the base station. The base station computes the first principal component v1. The two clusters C1 and C2 are determined via v1 according to (15) by the BS.


### 4.2. Clusters Splitting Stage

When the number of sensor nodes is huge, two clusters are not enough and can induce the energy consume rapidly, considering splitting these clusters whose memberships are more than the CH can support.If there areK clusters, there are on average N/K nodes per cluster (one CH node and non-CH nodes). We define that
(25)Ave=N/K.We can estimate the average energy dissipated per round to get the most energy efficient number of the clusters as follows:(26)Eround=k(ECH+Enon-CH)=k[lEelec(Nk-1)+alEelec+alεmpdtoBS4+(Nk-1)(lEelec+lεfsdtoCH2)].
The notation and definition of the parameters in (26) are described as Table 1.Table 1
Parameter description.
Parameters
Head description
k
The number of the clusters
N
The total number of the sensor nodes
E
elec
The energy consumption per bit when sending and receiving
l
The sending data bit
ε
mp
/
ε
fs
The energy consumption about the amplifier
a
The data aggregating rate. It is application specific, where we assumea=3 as mentioned in Section 2.
d
toBS
The average distance between the CHs and the BS. We assume it = 75 m
d
toCH
The average distance between the CHs and the non-CH nodes. From [5], we obtain dtoCH=(1/2π)(M2/k), in which,  M  denotes the area of this field.We can get(27)Eround=l[(2N+k)Eelec+3kεmpdtoBS4+εfsM22πNk-εfsM22π].According to  the average energy dissipated per round, the scope of the clusters’ number can be estimated when it is the most energy efficient. In [4, 13, 14], the authors use the average energy dissipated per round to obtain the optimal cluster number. Based on this methodology, here in this paper, we study the appropriate upper limit of the cluster nodes to perform the clusters splitting and thus extend this methodology.Example 3.
If we assume the number of sensor nodes is 100, the average energy dissipated per round as the number of clusters is varied between 1 and 20. Figure3 shows that it is most energy efficient when there are between 3 and 5 clusters in the 100-node network. We define that the most appropriate number of clusters is varied from 3 to 5 because
(28)(Eround(3)-Eround(min))Eround(min)<0.03,(Eround(5)-Eround(min))Eround(min)<0.03.Figure 3
Average energy dissipation per round with varying the number of clusters.We obtain that the appropriate upper limit of the cluster nodes is 100/3 = 34.If the number of cluster nodes is more than 34, the PCA-guided clustering algorithm will implement to split it.


### 4.3. Cluster Balancing  Stage

We use the BS running the PCA-guided clustering algorithm to divide sensor nodes based on the geographical information. We getK clusters from N nodes in the field rapidly and form better clusters by dispersing the CHs throughout the network.Now let us introduce the basic idea of the cluster balancing stage. Above, we get the number of clustersK if there are N nodes. We define the average node number per cluster as Ave. The cluster-balanced step is added in each iteration process. If |Cj|>Ave, 1≤j≤K, the BS computes dist(si,uq¯), where si∈Cj,j≠q and |Cq|<Ave. This means to compute the distances between the nodes and each cluster center whose cluster’s node number is less than Ave. The BS gets si if its value is minimum and adjusts the node into the corresponding cluster computed. After implementing the cluster-balanced step, the BS limit the node number in each cluster and change the clusters unequal distribution in the space of nodes originally.Example 4.
Figure4 gives an example to illustrate how the cluster-balanced step works. In this example, if we only consider the geographical information of sensor nodes while using PCA-guided splitting algorithm, the sensor nodes s1 to s1 should belong to the C1. However, the nodes in C1 are more than Ave(=5). Thus, this scenario motivates the cluster-balanced step. To have a balance among all the clusters, in our method, we suggest that the sensor s6 should be grouped into C2 because its distance is nearest to C2. We obtain the final balanced cluster structure by a serial standard PCA-guided splitting stage and the cluster balancing stage.Figure 4
An example of the cluster balancing stage.


### 4.4. Cluster Heads Selecting Stage

After the base station divides the appropriate clusters using PCA technique, it needs to select the optimal cluster heads in these clusters. Assume that the initial energy is same, the base station can rank the matrixY for each cluster and section the sensor nodes which is the nearest to the cluster centers.


### 4.5. Data Aggregating Stage

The sensor nodes begin to transfer the data to the cluster heads after finishing the cluster formation. The cluster heads collect the measurements from the sensor nodes and then compute the first principal componentw1 (as (18)), the mean vector G  (as (21)), and Z (as (20)). They can be delivered to the base station with a constant packet size for each cluster head. At last, the base station will compute the approximate measurements by these packets.


### 4.6. The Description for PCA-Guided Routing Algorithm

The procedure taken by the base station is as follows.Step  1: compute the first principal componentv1,Step  2: according to (15), the two clusters C1 and C2 are determined via v1.Step  3: computeEround and get the appropriate upper limit of the cluster nodes.Step  4: while the cluster node number are more than the appropriate upper limit.Step  5: compute a newv1 for the cluster.Step  6: repeat Step  2 and Step  3.Step  7: endStep  8: if needed, implement the cluster balancing stage.Step  9: select the cluster heads.Step  10: computew1 (according to (18)), G (according to (21)), and Z (according to (20)) for the approximate measurements.


## 4.1. Initialization Stage

In the first stage, we assume that a set ofN location coordinates are gathered at the base station. The base station computes the first principal component v1. The two clusters C1 and C2 are determined via v1 according to (15) by the BS.


## 4.2. Clusters Splitting Stage

When the number of sensor nodes is huge, two clusters are not enough and can induce the energy consume rapidly, considering splitting these clusters whose memberships are more than the CH can support.If there areK clusters, there are on average N/K nodes per cluster (one CH node and non-CH nodes). We define that
(25)Ave=N/K.We can estimate the average energy dissipated per round to get the most energy efficient number of the clusters as follows:(26)Eround=k(ECH+Enon-CH)=k[lEelec(Nk-1)+alEelec+alεmpdtoBS4+(Nk-1)(lEelec+lεfsdtoCH2)].
The notation and definition of the parameters in (26) are described as Table 1.Table 1
Parameter description.
Parameters
Head description
k
The number of the clusters
N
The total number of the sensor nodes
E
elec
The energy consumption per bit when sending and receiving
l
The sending data bit
ε
mp
/
ε
fs
The energy consumption about the amplifier
a
The data aggregating rate. It is application specific, where we assumea=3 as mentioned in Section 2.
d
toBS
The average distance between the CHs and the BS. We assume it = 75 m
d
toCH
The average distance between the CHs and the non-CH nodes. From [5], we obtain dtoCH=(1/2π)(M2/k), in which,  M  denotes the area of this field.We can get(27)Eround=l[(2N+k)Eelec+3kεmpdtoBS4+εfsM22πNk-εfsM22π].According to  the average energy dissipated per round, the scope of the clusters’ number can be estimated when it is the most energy efficient. In [4, 13, 14], the authors use the average energy dissipated per round to obtain the optimal cluster number. Based on this methodology, here in this paper, we study the appropriate upper limit of the cluster nodes to perform the clusters splitting and thus extend this methodology.Example 3.
If we assume the number of sensor nodes is 100, the average energy dissipated per round as the number of clusters is varied between 1 and 20. Figure3 shows that it is most energy efficient when there are between 3 and 5 clusters in the 100-node network. We define that the most appropriate number of clusters is varied from 3 to 5 because
(28)(Eround(3)-Eround(min))Eround(min)<0.03,(Eround(5)-Eround(min))Eround(min)<0.03.Figure 3
Average energy dissipation per round with varying the number of clusters.We obtain that the appropriate upper limit of the cluster nodes is 100/3 = 34.If the number of cluster nodes is more than 34, the PCA-guided clustering algorithm will implement to split it.


## 4.3. Cluster Balancing  Stage

We use the BS running the PCA-guided clustering algorithm to divide sensor nodes based on the geographical information. We getK clusters from N nodes in the field rapidly and form better clusters by dispersing the CHs throughout the network.Now let us introduce the basic idea of the cluster balancing stage. Above, we get the number of clustersK if there are N nodes. We define the average node number per cluster as Ave. The cluster-balanced step is added in each iteration process. If |Cj|>Ave, 1≤j≤K, the BS computes dist(si,uq¯), where si∈Cj,j≠q and |Cq|<Ave. This means to compute the distances between the nodes and each cluster center whose cluster’s node number is less than Ave. The BS gets si if its value is minimum and adjusts the node into the corresponding cluster computed. After implementing the cluster-balanced step, the BS limit the node number in each cluster and change the clusters unequal distribution in the space of nodes originally.Example 4.
Figure4 gives an example to illustrate how the cluster-balanced step works. In this example, if we only consider the geographical information of sensor nodes while using PCA-guided splitting algorithm, the sensor nodes s1 to s1 should belong to the C1. However, the nodes in C1 are more than Ave(=5). Thus, this scenario motivates the cluster-balanced step. To have a balance among all the clusters, in our method, we suggest that the sensor s6 should be grouped into C2 because its distance is nearest to C2. We obtain the final balanced cluster structure by a serial standard PCA-guided splitting stage and the cluster balancing stage.Figure 4
An example of the cluster balancing stage.


## 4.4. Cluster Heads Selecting Stage

After the base station divides the appropriate clusters using PCA technique, it needs to select the optimal cluster heads in these clusters. Assume that the initial energy is same, the base station can rank the matrixY for each cluster and section the sensor nodes which is the nearest to the cluster centers.


## 4.5. Data Aggregating Stage

The sensor nodes begin to transfer the data to the cluster heads after finishing the cluster formation. The cluster heads collect the measurements from the sensor nodes and then compute the first principal componentw1 (as (18)), the mean vector G  (as (21)), and Z (as (20)). They can be delivered to the base station with a constant packet size for each cluster head. At last, the base station will compute the approximate measurements by these packets.


## 4.6. The Description for PCA-Guided Routing Algorithm

The procedure taken by the base station is as follows.Step  1: compute the first principal componentv1,Step  2: according to (15), the two clusters C1 and C2 are determined via v1.Step  3: computeEround and get the appropriate upper limit of the cluster nodes.Step  4: while the cluster node number are more than the appropriate upper limit.Step  5: compute a newv1 for the cluster.Step  6: repeat Step  2 and Step  3.Step  7: endStep  8: if needed, implement the cluster balancing stage.Step  9: select the cluster heads.Step  10: computew1 (according to (18)), G (according to (21)), and Z (according to (20)) for the approximate measurements.


## 5. Simulation Results

To evaluate the performance of PCA-RA, we simulate it, LEACH and LEACH-E, using a random 100-node network. The BS is located at(50,150) in a 100×100 m2 field.Figures5 and 6 show the clustering structure for using LEACH and PCA-RA. Comparing Figures 5 and 6, one finds that each cluster is as compact as possible, and the cluster heads locate more closely to the cluster centers by using PCA-RA. This gives us an intuition that it is more efficient to balance the load of network and to even distribute the nodes among clusters by using PCA-RA.Figure 5
The clustering structure for using LEACH.Figure 6
The clustering structure for using PCA-RA.The benefits of using PCA-RA are further demonstrated in Figures7 and 8, where we compare the network performance of network lifetime and throughput under the PCA-RA with that under LEACH and LEACH-E. Figure 7 shows the total number of nodes that remain alive over the simulation time, while the first dead node remains alive for a more long time in PCA-RA, this is because PCA-RA takes into account the structure of clusters and the location of the cluster heads. Figure 8 shows that PCA-RA sends much more data in the simulation time than LEACH and LEACH-E.Figure 7
System lifetime using LEACH, LEACH-E and PCA-RA.Figure 8
Throughput using LEACH, LEACH-E, and PCA-RA.Note that the survey nodes in each round areNSi; each node can send Di data. Then, the maximum throughput can be expressed as follows;
(29)ThroughputPCA-RA=∑i=1TmaxNSi·Di.From Figure7, the Tmax for PCA-RA are more than the Tmax for LEACH and LEACH-E. Then, ThroughputPCA-RA>ThroughputLEACH and ThroughputPCA-RA>ThroughputLEACH-E.For example, under the given test data, there are60.456*103 bits data sent in whole network lifetime with PCA-RA. And there are 33.394*103 bits and 28.235*103 bits by using LEACH-E and LEACH, respectively. The mathematics demonstrates that PCA-RA has 80.01% increase about throughput compared with LEACH-E and 114.12% increase about throughput compared with LEACH.PCA-RA is a centralized algorithm, and the complexity and communication cost of PCA-RA mostly happen in BS. About the balance structure stage, we think the effect on time complexity is small and consider that the time complexity is comparable to LEACH-C.Table2 displays the network lifetime (in terms of the time that the first node becoming dead) and the resulted square error function of the senor node structure under K-means algorithms and PCA-RA.Table 2
A numerical example.
Parameters
K-means
PCA-RA
Square error
34392.980
38405.656
The first node dead time
88 rounds
99 roundsFrom Table2, we can find that K-means algorithm can get a minimum square error. Because of the cluster-balanced step, PCA-RA can get a bigger square error, but the sensor nodes can survive a longer time. This implies that one can reach a certain tradeoff between the total spatial distance of sensor structure and the network lifetime. The suboptimal solution in PCA-RA can achieve such tradeoff.In Figure9, we simulate the sensor nodes collecting the measurements about temperature in some regions. Assume that the base station receive the packets from the cluster head in two minutes interval. Figure 9 demonstrates the approximations obtained by the base station about a certain sensor node in some intervals.Figure 9
Approximation obtained for the sensor nodes.


## 6. Conclusions

In this paper, we propose the PCA-guided routing algorithm for WSNs. By disclosing the connection between PCA andK-means, we design a clustering algorithm by utilizing PCA technique which efficiently develops a clustering structure in WSNs. Moreover, as a compression method, we demonstrate that the PCA technique can be used in data aggregation for WSNs as well. We establish the explicit procedure of PCA-guided routing algorithm for WSNs by incorporating PCA technique into both the data aggregating and routing process.  The advantages of the proposed algorithm are demonstrated through both theoretical analyses and simulation results. The simulation results show that the PCA-guided routing algorithm significantly reduces the energy consumption, prolongs the lifetime of network, and improves network throughput when compared with LEACH and LEACH-E. Further, it keeps the accuracy about the measurements while reducing the network load.Future research will focus on the distributed strategies of PCA-guided data aggregation and will investigate the performance of PCA-RA with different values of parameterK.



---

*Source: 427246-2012-12-13.xml*