CN104703262B - Clustering method of data capture based on compressed sensing - Google Patents

Abstract

The invention discloses a clustering data collection method based on compressed sensing. First, the sensor network implements a clustering algorithm based on edge betweenness and a cluster head selection method based on point betweenness. Then, the cluster head collects the data of the nodes in the cluster, and generates a random measurement matrix to compress the collected data. Finally, the cluster head transmits the compressed data to the base station along the shortest path algorithm, and the base station generates the same measurement matrix to reconstruct the compressed data. If the reconstruction error is greater than a certain threshold, the number of rows of the measurement matrix is increased so that the reconstructed data satisfies A certain error threshold. The invention reduces the energy consumption of data collection, and can adjust the error of the reconstructed data in real time, so as to obtain the reconstructed data satisfying a certain error.

Description

Clustering Data Collection Method Based on Compressed Sensing

technical field

The invention relates to a compressed sensing-based clustering data collection method especially for a wireless sensor network, which belongs to the technical field of communication.

Background technique

Wireless sensor network (Wireless Sensor Network, WSN) is an ad hoc network formed by some low-power, small-sized sensor network nodes in a wireless multi-hop manner. These a large number of dispersed nodes can cooperate at the same time to monitor, perceive and collect various data in a certain area in real time. However, wireless sensor network nodes are densely distributed and have limited energy. Especially in the process of clustering data collection, a large amount of sensing data needs to be transmitted to the cluster head through the sensor network nodes, and then transmitted to the base station. How to design an efficient data collection method has become an urgent problem to be solved.

The traditional data collection method usually transmits all the data collected by a large number of sensor nodes to the base station for processing through the cluster head node. However, in the data collection process of sensor networks, usually multiple sensor nodes perform perception compression on an event, which carries a large amount of redundant data, greatly occupies the network communication bandwidth, and brings unnecessary energy consumption.

In recent years, with the proposal of compressed sensing (compressive sensing, CS), it has opened up a new path for data collection in wireless sensor networks. Compressed sensing theory can be divided into three processes: sampling, measurement, and reconstruction. Sampling: Sampling sparse data; Measurement: Compressing and measuring the sampled data to obtain measured values; Reconstruction: Restoring the original data from the measured value data. However, the existing data collection schemes combined with compressed sensing are mainly carried out through the design of measurement matrix, general clustering, and distributed spatiotemporal correlation.

The design method of the measurement matrix is to design a matrix that satisfies certain characteristics, such as designing a circular sparse Bernoulli observation matrix suitable for sensor nodes with limited hardware resources, using a circular sparse matrix and a pseudo-random Bernoulli sequence, using a structured method construct. It has the advantages of less non-zero elements, good pseudo-randomness, and easy hardware implementation. Under the premise of satisfying the data reconstruction error, less observation data can be obtained by compressing observation, and transmission energy consumption can be reduced.

Ordinary clustering method, that is, by performing a certain clustering algorithm on the network, then generating a random sampling sequence in the cluster head and distributing it to the cluster members, then performing low-speed random sampling in the cluster members, and finally performing signal reconstruction in the cluster head . This method can reduce a certain amount of transmission energy consumption, but cannot guarantee the quality of reconstruction.

Distributed spatio-temporal correlation method, that is, in the process of data collection, only random projection operation is performed on spatial perception data at present, but the compression performance of spatial perception data in the real network is not good, resulting in poor data recovery quality and compressed data The transmission cost is high. A distributed spatio-temporal data collection method is proposed, which can effectively reduce the number of measured values transmitted in the network.

To sum up, the existing compressed sensing combined with sensor network data collection strategies can reduce a certain number of measured values, thereby reducing transmission energy consumption. However, how to reduce intra-cluster transmission energy consumption to reduce the total energy consumption of network transmission, At the same time, there is no suitable solution to obtain reconstructed data satisfying a certain error value.

Contents of the invention

Aiming at the above problems and the sensor network with a certain organizational structure, a clustering data collection method based on compressed sensing is proposed. By implementing the clustering algorithm based on the edge betweenness and the cluster head selection method based on the point betweenness on the sensor network nodes, as well as the feedback of the reconstruction error, it solves the problem of high energy consumption during data collection and the inability to obtain data that meets certain error requirements. question. The present invention obtains the optimal clustering by executing the clustering algorithm based on the edge betweenness and the cluster head selection method based on the point betweenness, and reduces the transmission energy consumption in the cluster, thereby reducing the total transmission energy consumption as much as possible. At the same time, through The reconstruction error is fed back to obtain reconstruction data that meets certain error requirements.

In the present invention, firstly, a clustering algorithm based on edge betweenness and a cluster head selection method based on point betweenness are executed on the sensor network. Then, the cluster head collects the data of the nodes in the cluster, and generates a random measurement matrix to compress the collected data. Finally, the cluster head transmits the compressed data to the base station along the shortest path algorithm, and the base station generates the same measurement matrix to reconstruct the compressed data. If the reconstruction error is greater than a certain threshold, the number of rows of the measurement matrix is increased so that the reconstructed data satisfies A certain error threshold. The invention reduces the energy consumption of data collection, and can adjust the error of the reconstructed data in real time, so as to obtain the reconstructed data satisfying a certain error.

Concrete steps of the present invention are as follows:

Step 1. According to the adjacency matrix of the node , execute the clustering algorithm based on the edge betweenness and the cluster head selection method based on the point betweenness on the sensor network nodes, and obtain the network clustering and the cluster head corresponding to each sub-cluster ;

Step 2. The nodes in the cluster transmit the perceived data to the corresponding cluster head ;

Step 3. Cluster head node generate a random measurement matrix , and for the collected data Perform compressed sampling to obtain a matrix of measured values in the first List , ;

Step 4. Cluster head node After the shortest path algorithm, the measured value transmitted to the base station;

Step 5. The base station receives the data from the cluster head to form a matrix of measured values , then the base station generates the same random measurement matrix , and collect data on the original Perform reconstruction, and the reconstruction process satisfies the following formula:

(1)

Step 6. For the reconstructed data , calculate its mean square error, then execute the feedback algorithm, and finally obtain the reconstructed data that meets the error threshold;

Step seven, end.

Compared with the existing wireless sensor network data collection method combined with compressed sensing, the present invention has the advantages of:

1. The clustering algorithm based on the edge betweenness and the cluster head selection method based on the point betweenness proposed by the present invention can obtain a more reasonable cluster structure, effectively reduce the energy consumption of intra-cluster transmission, and thus reduce the network as much as possible. Total energy consumption for transmission;

2. The present invention calculates the reconstruction error according to the reconstruction data and performs real-time feedback, so that reconstruction data meeting certain error requirements can be obtained without increasing redundant communication energy consumption.

Description of drawings

Fig. 1 is the flowchart that realizes data collection of the present invention;

Figure 2 is a schematic diagram of a 20-node network with a certain organizational structure;

Fig. 3 is a schematic diagram of the result of network division of 20 nodes;

Figure 4 is a comparison of the energy consumption results of the shortest path data collection and the clustered data collection based on compressed sensing.

Specific implementation method

The present invention has designed the clustering type data collection method based on compressed sensing, in conjunction with Fig. 1, the specific implementation method of data collection is as follows:

For a wireless sensor network with a certain organizational structure, set the error threshold of the base station reconstructed data , taking the 20-node network (Figure 2, node numbers from 1 to 20, coordinates (0,0) point is the base station node) and image data as an example. The specific steps are as follows:

Step 1. The base station sets the mean square error threshold after data reconstruction ;

Step 2: Perform a clustering algorithm based on edge betweenness and a cluster head selection method based on point betweenness on the sensor network nodes to obtain network clustering and the cluster head corresponding to each sub-cluster , , , (Fig. 3, wherein nodes 1, 2, 3, 4, 5 are a cluster, nodes 6, 7, 8, 9, 10 are a cluster, nodes 11, 12, 13, 14, 15 are a cluster, nodes 16, 17, 18, 19, and 20 are a cluster, each cluster is marked with a different shape, and the five-pointed star node is the cluster head in the corresponding cluster);

Step 3. The nodes in the cluster transmit the perceived data to the corresponding cluster head ;

Step 4. Cluster head node , , , random measurement matrix , , , , and for the collected data , Perform compressed sampling to obtain a matrix of measured values in the first List , ;

Step 5. Cluster head node After the shortest path algorithm, the measured value transmitted to the base station;

Step 6. The base station receives the data from the cluster head to form a matrix of measured values , and then the base station generates a random measurement matrix , and collect data on the original Perform reconstruction, and the reconstruction process satisfies the following formula:

(1)

Step 7. For the reconstructed data , according to the following formula to calculate the mean square error:

(2)

Step 8. Compare reconstruction errors and the error threshold , if the error is greater than or equal to the error threshold, that is , go to step nine, otherwise go to step ten;

Step 9. Add measurement matrix The number of rows is re-reconstructed to obtain the reconstructed data. If the mean square error of the reconstructed data is greater than the mean square error threshold, that is , continue to increase the measurement matrix number of rows until the mean square error is less than the mean square error threshold, go to step 10;

Step ten, end.

In order to verify the effectiveness of this method, this method is tested on the Matlab simulation platform, and a 20-node network is deployed in a 100m Within the monitoring area of 100m, the coordinates of the base station are (0,0). The nodes have the same initial energy, and the energy consumed by the nodes is calculated according to the following formula:

(3)

In the formula represents the distance between two nodes, is the proportional coefficient of distance energy consumption, is the adjustment factor, , when the node and node There are edge connections between , the energy consumed to transmit a packet at both ends of this edge is ; and when there is no edge between two nodes, that is , the energy consumed to transmit a data packet between these two edges is . The transmission distance is set to 40m.

The data is transmitted in the network for 50 rounds. At this time, no node in the network is exhausted. Compared with the clustering data collection method based on compressed sensing and the shortest path data collection method, the results are shown in Figure 4. It can be seen from the figure that the clustering data collection method based on compressed sensing significantly reduces network energy consumption.

Then, the image data is fed back at the base station, when the number of rows of the measurement matrix When it is set to 10, 20, 30, 40, 50 in turn, each round of feedback will add two lines to the original line value, namely , set the mean square error threshold of the image data to 200, and 150-250 is the acceptable range of the mean square error. It is found through experiments that the measurement matrix with different numbers of rows can adjust the number of rows through feedback to obtain the mean square that satisfies the conditions. error.

To sum up, the clustered data collection method based on compressed sensing can not only effectively reduce the total energy consumption of transmission, but also obtain reconstructed data that meets certain error requirements by feeding back reconstruction errors.

Claims (2)

1. a clustering method of data capture based on compressed sensing, it is characterised in that first, sensor network perform based on The cluster algorithm of limit betweenness and based on a betweenness bunch of head system of selection；Then, bunch head collects the data of bunch interior nodes, and produces Random measurement matrix is compressed sampling to the data collected；Finally, the data after compression are passed by bunch head along shortest path first Being passed to base station, base station produces identical calculation matrix and is reconstructed compression data, if reconstructed error is more than certain threshold value, then Increase calculation matrix line number so that reconstruct data meet certain error threshold value；Described method at least includes following premise and step:

Premise:

Sensor network nodes distribution has certain texture characteristic；

The mean square error threshold value of base station sets reconstruct data；

Step:

Step one, adjacency matrix according to node, to sensor network nodes perform cluster algorithm based on limit betweenness and based on Bunch head system of selection of some betweenness, obtains network cluster dividingAnd bunch head that each sub-clustering is corresponding；

The data perceived are transferred to bunch head of correspondence by step 2, bunch interior nodes；

Step 3, leader cluster nodeProduce random measurement matrix, and to the data collectedIt is compressed sampling, is surveyed Value matrixInRow,；

Step 4, leader cluster nodeThrough shortest path first by measured valueIt is transferred to base station；

Step 5, base station receive the data from bunch head, constitute measured value matrix, then base station produces phase Same random measurement matrix, and to primary collection dataBeing reconstructed, restructuring procedure meets following formula:

(1)

Step 6, to reconstruct data out, calculate its mean square error, then, perform feedback algorithm, finally, be met by mistake The reconstruct data of difference limen value;

Step 7, end.

2. the method for claim 1, it is characterised in that described feedback algorithm, the most also includes:

1) calculate the mean square error of reconstruct data, useRepresent, contrast reconstructed errorAnd error thresholdIf error is more than by mistake Difference limen value, i.e., go to step 2), otherwise go to step 3)；

2) in order to improve reconstruction accuracy, calculation matrix is increasedNumber of lines, regenerate the random measurement matrix of more higher-dimension, so After, re-start reconstruct, obtain reconstructing data, if the mean square error after Chong Gou is still above error threshold, i.e., continue Increase calculation matrixNumber of lines, until error less than error threshold, goes to step 3)；

3) terminate.