2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering
Distributed Low Rank Compressed Sensing Utilized in a Structural Health Monitoring System Farzad Parvaresh, Hossein Tajmir Riahi
Arsham Mostaani Faculty of Engineering University of Isfahan Isfahan, Iran
[email protected] Tel Number: +98-913-106-8232
Abstract— Structural Health Monitoring (SHM) Systems are utilized in critical and vital structures to identify the state of health in them. For the bridges in which SHM systems are widely used, Due to the complexity of structure, dense sensor networks are much more desirable. In literature it is proved that these dense sensor networks can only be implemented using Wireless Sensor Networks while these systems are faced with some challenging problems too. The large size of data being transmitted in such networks and high energy consumption regarding the data transmission, raise the question that how we can reduce the size of data to be transferred and consequently decrease the power dedicated to this task. We have introduced a method to compress large low rank dataset and an algorithm to implement the method in distributed manner. The method is able to cut up to 75% of the size of data which is a high rate of compression compared with the literature. Furthermore the performance of the data regeneration algorithm is studied both in presence and absence of measurement noise and finally the proof of large reduction in power consumption using this method is given mathematically. Keywords— Compressed-Sensing (CS); Low Rank Compressed Sensing; Structural Health Monitoring (SHM); Distributed algorithm; Wireless sensor Networks (WSN)
I. INTRODUCTION The main focus of this paper is to provide distributed method to compress data observed and transmitted in a wireless sensor network being utilized in a Structural Health Monitoring (SHM) system. An SHM system which is utilized in a critical structure to assess the state of health, firstly, needs a sensor network to gather data from the whole parts of structure or equivalently monitor it. To reduce the expenses of implementation and maintenance of wired systems and to add the ability of acquiring data with much more details, use of dense Wireless Sensor Networks (WSNs) is widely spread. In WSNs however, we have concerns about the volume of power consumption in data transmission block of the system. Since the most power consuming task of a WSN is data transmission [1], we are highly interested in any modification that can reduce the size of data to be transmitted or cutting the power consumption regarding data transmission.
Faculty of Engineering University of Isfahan Isfahan, Iran
[email protected] Tel Number: +98-31-3793-5640
Lots of researches is dedicated to introduce power efficient methods that can efficiently detect the modal parameters1 of the structure or detect damage [1-7]. In reference [1] the authors have introduced an SVD based method to detect modal parameters of the structure with a data sampling rate less than Nyquist and without reconstruction of the main signal after being compressively measured, the data compression task however, is limited to decrease in the sampling speed and the damage detecting algorithms limited to mode shape based methods. In [2,3] also Compressed Sensing (CS) in each sensor is utilized and finally the main data is reconstructed using large number of measurements in their CS method and it is shown that at least a M=0.8*L number of measurements is needed to reconstruct the main signal where L is the number of measurements that should be performed to reach Nyquist rate. A distributedly implementable method is also introduced in [4].This approach proposes a restriction on Auto Regressive parameters of the multivariate AR models that eliminates the computation of correlation between signals measured at nodes that are far apart, and as the result reduces the volume of data passed through the network. [5,6] introduce a method in which local data transmission reduces to transferring only modal parameters calculated in each node having access to its data measurements besides the modal estimation received from the previous node. A hierarchical decentralized SHM system that implements flexibility-based damage identification and localization is introduced in [7]. In this research by allowing a large number of sensors to be on standby mode, and incrementally activating clusters, a good energy saving is resulted however this procedure might lead to a considerable delay in system Identification procedures. Apart from SHM systems, several types of Low Rank Compressed Sensing (LRCS) methods are studied before to compress a dataset using its low rank property [8-12]. Some of these methods are based on certain restricted isometry property of the matrices [8,9]. Where some else have used more general notion of parsimony in the matrices with property of being low rank [10-11]. Where in [11], a realistic scenario is studied. In this scenario the main data is not exactly of low rank and can be polluted with Additive Noise in measurements. In [12] also, an SVD based compressive sensing and signal reconstruction scheme is introduced using certain types of random matrices being multiplied by main data, which is considered as the measurement method.
1
Detection of Modal Parameters is an important step in detecting the dynamic characteristic of a structure and to detect its damages if there exist any.
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering Our main contribution in this paper is been the utilization Low Rank Compressed Sensing in an SHM system which have concluded to a high level of compression, compared with other types of compressed sensing. It will be shown that by applying this type of compressed sensing which is more match to the structure of dataset, the volume of compressed data can reduce up to 25% of its main size with a negligible error of data regeneration. This type of data compression raises some challenges in the Implementation level, which have been addressed during this survey and by use of a distributed type of LRCS we have been able to overcome them completely. Finally the proof of the high decrease in the power consumption of WSN in which distributed LRCS is been implemented, compared with a normal centralized WSN is given. In this paper after defining the problem in request in section II, and briefly studying the low-rank property of our data-set in section III, we apply the centralized compressive sensing and reconstruction scheme introduced in [11,12] in section IV-a and then by introducing a distributedly implementable algorithm in IV-b we make the main method implementable in practice. In IV-c the mathematical proof of the power reduction caused by our method is given.
Fig. 1. Color Noise Excitation of The Model Structure in Time Domation
II. DEFINITION OF THE PROBLEM We consider a numerically simulated beam made out of 60 lumped masses with two pinned support where damping ratio in modal analyzing of the beam is considered to be zero. The beam is excited by color Gaussian noise which is made out of white Gaussian noise being filtered by a 4th order Butterworth filter having cutoff frequency of 50Hz. Figure.1 Depicts the excitation signal in time domain while in Figure.2 the excitation is shown in frequency domain and the normalized form of the applied Butterworth filter of order 4 is also plotted. It is assumed that the data has been polluted with additive white Gaussian measurement noise which has rms of 1/30 of the signal rms. The joints of the beam, 59 joints, are observed using 59 smart sensors 2 each have sampling rate of 100Hz and the whole data that here is dealt with, has been acquired during 100 seconds. Finally after 100 seconds of observations a matrix of by of data is obtained which is called where in the acceleration is observed at ith time step in jth sensor located on jth joint of the beam. In Figure.3 the data observed by a sensor during the time is illustrated.
2
By smart sensor we mean a device which is able to sense, process and transcieve data. There are several types of commonly used smart sensor platforms namely Imote-2 which is designed by Illinois SHM team and its details can be found at: http://shm.cs.uiuc.edu/files/docs/Imote2forSHM_UsersGuide. pdf
Fig. 2. Color Noise Excitation of The Model Structure in Frequency Domain
We want to compress data of into one or several matrices with lower overall dimensions. A method is needed which can enable us to compress the data transmitted by each sensor or probably the data transmitted by a group of sensors in WSN. The method also needs to be implementable in distributed manner. The point is that if we transmit all data measured by each sensor to the central node and we compress all acquired data in the central node, we haven’t reduced the power allocated to wireless data transmission task at all. In order to reduce the energy of data transmission we need a method that can perform its compression algorithm before data is been sent to the central node. As is clear, by putting structural data of more sensors together we shall get more chance to have higher rate of compression for the overall data and from the other side putting more data together means transmission of more purely measured data to a certain node which leads to higher rate of power consumption. As the consequence, one side of problem is to look for a compression method with high rate of compression and another
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering side is to have less data transmitted uncompressed within the WSN. In this paper as will be discussed precisely, we only study a simple case in which the procedure of data compression is performed node-by-node and no uncompressed data is transmitted in the network.
Fig. 3. Response of the structure to excitation at the 15th node
shape can be estimated using limited number of mode shapes at a certain time or period of time. In the next subsection the desirable performance of SVD to compress whole data, assuming having access to whole data at one place, is demonstrated but decreasing the computational complexity and having each sensors data compressed remain as the unsolved questions to be addressed in section IV. B. Approximating a Matrix Using Singular Value Decomposition (SVD): A matrix data can be compressed using truncated form of SVD of a matrix. The Idea is displayed in (1) which is about to say that the rectangular matrix X0 with dimension m*n, can be best approximated using singular values, left singular vectors and right singular vectors. Where singular values are non-negative real numbers of and … , left singular vectors are orthonormal complex m*1 column vectors, named , ,…, and right singular vectors are orthonormal complex n*1 column vectors , ,…, known as right such that (2) holds where r, m and n are positive integers with and .
III. LOW RANK COMPRESSED SENSING AND ITS RELATION TO THE PROBLEM
A. Property of Being Low Rank in our Dataset Let’s take a look at a particular and desired property of the matrix . How can we have an estimation of number of active basis that can reconstruct this matrix? We utilize Singular Value Decomposition to obtain an evaluation of the number of highly active basis that are constructing our data in request. Figure.4 is about to demonstrate all the singular values of this matrix. As we can see in this figure, 23th singular value of the matrix has value less than 1/1000 of its 1st singular value. Hence we may not loos so much if we use only first 23 singular values and their corresponding right and left singular vectors to construct the main matrix. This is the reason why we can call the matrix low rank and take some advantage of this feature to put core data to another matrix with much lower size. But how one can have an intuition about why the structural data are of low rank. As we know, by excitation of any of natural frequencies of a structure, its corresponding mode shape appears in the structures special response. Thus assuming the structure to be a linear one, and superposition rule to hold, by knowing transform function of the structure and the function of excitation in frequency domain, we can estimate the shape of structure at an arbitrary time-space point. By considering the fact that in real, there is no white Gaussian noise excitation, we have only a limited number of any structure’s natural frequencies stimulated. Knowing all above gives one enough reason to be convinced that a structures
Fig. 4. Singular values of the acceleration matrix
In (2) is a positive real number indicating the precision of approximation. (1) (2) In the next section an SVD-based method of LRCS is utilized in which using multiplication of two random matrices by main data, two compressed version of the main will be resulted. It will be shown that using the method the error of data compression and regeneration can be ignored while the method is proved to have much less computational complexity in the literature.
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering
IV. INTRODUCING AN LRCS METHOD TO COMPRESS AND RECONSTRUCT ACCELERATION DATA We use low rank compressed sensing method introduced in [11-12] to compress . The method is called sensing row and column spaces. In this section after introducing the core method in centralized implementation, subsection A, the distributed implementation of it is represented at sub-section B. A. Centralized sensing of rows and columns of a matrix To introduce the basic form of our idea we firstly applied it in a central manner which is equivalent to have all data regarding transmitted to a central node and process the whole data to compress it there. Using (3), the resulting compressed versions of will be . The compressed forms of main data which has considerably lower total volume and are solely sufficient to regenerate the main data, (4).
ratio of error norm to main data norm which is calculated using formula (4) is 1.2% in case of absence of noise and for the noisy measurements the estimations will occur with error ration of 7.7%.
Where stands for L-2 or Euclidean norm and in case of presence of noise the matrix is assumed to have noise in itself and consequently the error norm is the error of estimation of noisy measurements. By performing 500 times of simulations, the variance of errors using this method is studied and illustrated in Figure-6. By naming the error ratios of higher than 15%, to be unforgiveable errors, 15 number of unforgiveable errors has been occurred during the 500 times of simulations which means that in 3% of times the algorithm in presence of noisy measurements happens to operate with big errors. As it is visible in Figure-6 this algorithm working on a noise free signal, operates completely stable where in less than 4% of times error ratios bigger than 1.5% has happened, all of which is been less than 8%.
Where and are sensing matrices and is the rank that we consider for the . Indeed the may not be a real low-rank matrix but it can have some powerful singular values which suffice to reconstruct data with venial error. Considering the sizes of the rate of space saving in this method almost is . Sensing matrices of should have i.i.d Gaussian entries or be of type SRFT. An SRFT matrix can be obtained by randomly selecting rows of multiplication of a Fourier transform matrix, , by a diagonal matrix, , with random diagonal values, where more details can be found at [12]. In the recovery step following the (2), we can calculate an estimation of matrix, demonstrated by , using its compressed forms, . As is obvious, there is no need to have access to any entries of the matrix, instead we only need to have the compressed versions of it and the sensing matrices.
The introduced compression-decompression algorithm is been applied on matrix, considering its rank to be 23 so the rate of space saving will be about 61% of data size. Figure.5 shows the performance of the suggested method with and without presence of additive white Gaussian measurement noise with standard deviation of 1/30 rms of measured signal. In this figure the data shown are regarded to what is observed by the whole sensor network at a certain time step. As it can be noticed in the figure, the low rank property of the matrix has helped a lot to compress it with high rate of space saving and regenerate it with negligible error. The
Fig. 5. Demonstration of reconstructed data out of both noisy and and noise free data
Figure.7 is illustration of noise performance of the leveraged low rank compressive sensing algorithm. As is indicated by data-tips, by considering SNR bigger than 20, the error ratio of the compression algorithm became less than 10%. This figure is plotted after performing the simulations 100 times for each SNR. B. Distributed sensing of rows and columns of a matrix We look for a method which can be implementable in distributed manner and each sensor node take part in the procedure of data compression. Thus we are forced to do the two matrix multiplications mentioned in (3) distributedly. The multiplication of is done in distributed manner easily without any
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering data overhead as for the to be calculated we need to have access to the ith row of and jth column of in a sensor. This can be completely possible by generation of same SRFT matrices in all smart sensors of the network using pseudo-random algorithms and by having a memory in each smart sensor that can save the data it has observed during an arbitrary time interval, in our case this time interval is 100 seconds. The multiplication of which results in calculation of is not easily done, however, (6).
the calculation of the ith row of the having length of r, in each node we need to transmit r value, instead of 1 value in centralized form. But we prove that the method is steel explainable in terms of power consumption in next section.
Fig. 7. Error performance of the method in presence of measurement noise
Fig. 6. Error performance of the compresseion-decompression algorithm to reconstruct data
Using the Algorithm-1 which is shown separately, by solving the (6) the second compressed version of can be calculated distributedly in the WSN.
Compared with centralized data transmission the drawback of the distributed compressed sensing algorithm of us, is that for
C. Proving the Good Performance of Distributed Rows and Columns sensing Method in Terms of Overall Power Consumption In this section the overall power consumption of distributed row and column sensing method is compared with a centralized method in which all the observed data are sent wirelessly from each sensor to the central node. As is shown on (5) for the calculation of , we need to have access to a row of which means having access to data measured at all sensors of WSN at a certain time step. Of course since we have access to at the kth node, and we have access to also in this node, using the simple distributed algorithm1 in the kth node at the ith time step we can calculate the entry of this matrix. In comparison of these two methods the two determinative parameters of volume of data transmission and distance of data transmission are considered. Figure.8 depicts the beam on which our simulations are done and the placement of sensors on it which is the same in either distributed or centralized implementation of data processing. As is mentioned in (7) we assume that a direct relation exists between transmission power and both volume of data and distance of data transmission.
Considering the (7), the total power consumption in centralized and implementation of our data processing is given in the (8).
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering
Fig. 8. Demonstration of Beam, placement of sensors on it and the numbering scheme of the sensors
Where stands for the transmission power of sensor and n is the total number of sensors installed on the structure.
Since the summation of the form does not have a closed form, in (11) and (12), is calculated assuming and for which the summation formula is given in (9) and (10).
V. CONCLUSION A low rank compressed sensing were offered to distributedly compress the data being observed in a WSN. Since the dataset which were taken during monitoring of an excited structure, was of low rank, the suggested LRCS method succeeded to highly compress the network data and reduce the power consumption regarding its wireless transmission. Using numerical simulations the error performance of the suggested LRCS algorithm were provided with attractive results with and without presence of noise and from the other side considerably low power consumption of the distributed LRCS was proved. REFERENCES J. Y. Park, M. B. Wkin, A. C. Gilbert,“Modal Analysis with Compressive Measurements”, IEEE Transactions on Signal Processing, Vol. 62, No. 7, 2014. [2] D. Mascarenas, D. Hush, J. Theiler, and C. Farrar, “The Application of Compressed Sensing to Detecting Damage in Structures” 8th Int. Workshop Structural Health Monitoring, 2011. [3] B. Yuequan, J. L. Beck, and L. Hui, “Compressive Sampling for Accelerometer signals in Structural Health Monitoring” Structural Health Monitoring, vol. 10, no. 3, pp. 235–246, 2011. [4] S. N. Pakzad, G. V. Rocha, B. Yu, “Distributed Modal Identification Using Restricted Auto Regressive Models”, International Journal of Systems Science 42, 1473–1489. 2011. [5] S. Dorvash, S. N. Pakzad, L. Cheng, “An Iterative Modal Identification Algorithm for Structural Health Monitoring Using Wireless Sensor Networks. Earthquake and Spectra, Journal of Earthquake Engineering Research Institute, 2012. [6] S. Dorvash, S. N. Pakzad, “Stochastic Iterative Modal Identification Algorithm and Application in Wireless Sensor Networks ”,Structural Control and Health Monitoring. 2012. DOI: 10.1002/stc.1521. [7] G. Hackmann, W. Guo, G. Yan, Zh. Sun, Ch. Lu, Sh. Dyke, “CyberPhysical Codesign of Distributed Structural Health Monitoring with Wireless Sensor Networks ”, IEEE Transaction on Parallel and Distributed Systems, Vol. 25, No. 1, 2014. [8] E. J. Cand`es, J. Romberg, T. Tao, “Stable Signal Recovery from Incomplete and Inaccurate Measurements” Comm. Pure Appl. Math., 59(8):1207–1223, 2006. [9] E. J. Cand`es, T. Tao, “Decoding by Linear programming”, IEEE Transactions on Information Theory, 51(12):4203–4215, 2005. [10] B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed Minimum Rank Solutions to Linear Matrix Equations via Nuclear Norm Minimization, Submitted to SIAM Review, 2007. [11] M. Fazel, E. Candes, B. Recht, P. Parrilo, “Compressed Sensing and Robust Recovery of Low Rank Matrices ”, Systems and Computers, 42nd Asilomar Conference on, pp.1043-1047, 2008. [12]. F. Woolfe, E. Liberty, V. Rokhlin, M. Tygert, “A Fast Randomized Algorithm for the Approximation of Matrices ” Applied and computational harmonic analysis, vol. 25, pp. 335-366, 2007. [1]
In (13) the calculation of which is the wireless transmission power in distributed implementation of signal processing is demonstrated.
Where: considering the data transmission between two adjacent nodes.
Using equation (15), (11) and (12) the ratio of power consumption in centralized to distributed implementations of signal processing is higher than 13.9 for and higher than 318.6 for .
2016 1st International Conference on New Research Achievements in Electrical and Computer Engineering
