CN101932012B - Method for compressing sensor network data based on optimal order estimation and distributed clustering - Google Patents

Abstract

The invention relates to a sensor network data compression method based on optimal order estimation and distributed clustering. Existing data compression methods are inefficient. The present invention utilizes the time-space correlation of data collected by sensor nodes, on the one hand, by introducing optimal order estimation, thereby defining the number of original data groups to be transmitted by the system, not only obtaining effective correlation coefficients, but also avoiding redundant coefficients On the other hand, the network is divided into clusters, and the node data is processed in units of clusters. This can not only improve the efficiency of the base station in processing the data of each node, but also enhance the ability of the base station to quickly locate outliers or abnormal nodes. The invention is applicable to the environment real-time monitoring system based on the wireless sensor network, can realize the effective compression of the wireless sensor network data, and effectively reduce the average energy consumption of nodes.

Description

A Data Compression Method for Sensor Networks Based on Optimal Order Estimation and Distributed Clustering

technical field

The invention belongs to the technical field of data compression, and relates to a sensor network data compression method based on optimal order estimation and distributed clustering.

Background technique

In a monitoring system based on wireless sensor networks (WSNs), each sensor node collects local information around itself, processes it and transmits it to the sink node, and the sink node summarizes the local data collected by all nodes to obtain the overall information of the region of interest. In a wireless sensor network, due to the influence of various factors such as background noise, node failure, wireless communication instability and energy constraints, the sensory data information acquired, processed and transmitted by nodes often has certain errors and certain errors. degree of uncertainty, however in some applications a certain amount of error is usually allowed. That is, under the premise of ensuring the application requirements, the amount of data transmitted in the network can be reduced by reducing a certain data accuracy, thereby reducing the energy consumption of nodes in the network. The data compression algorithm in the wireless sensor network is to seek a method to effectively reduce the amount of data in transmission, thereby reducing the energy consumption of nodes and improving the overall performance of the entire network under the premise of ensuring a certain data accuracy. In many practical applications of wireless sensor networks, the probability of anomalies in the monitored area is always relatively small. In the absence of anomalies, when the same sensor node collects data continuously, the data collected at successive moments must exist. At the same time, the data collected by different sensor nodes in adjacent areas at the same time must have spatial correlation. If these data with time and space redundancy are sent to the base station, it will consume a lot of energy for the nodes. Therefore, how to effectively eliminate the redundancy of node perception data in time and space has become a key problem to be solved in data compression in wireless sensor networks. How to design an effective wireless sensor network data compression algorithm for the specific application needs of WSNs in environmental monitoring is a very meaningful research topic.

The wireless sensor network data compression algorithm uses the time and space redundancy in the node perception data, first directly transmits several groups of node perception data, extracts the correlation between different nodes at different times of the same node, and then combines distributed coding, Restore the original perception data of the node at the base station. There is only a simple modulo operation at the node, and a large number of algorithm operations are transferred to the base station. This can minimize the energy consumption of the unit data transmitted by the node while ensuring a certain accuracy. , but in practical application, it is feasible to replace the battery regularly or provide direct long-term power supply to the base station, so this algorithm has a broad application prospect. However, this type of algorithm still has some shortcomings. For example, when estimating the predicted correlation coefficient, there is no clear definition of the number of groups of original data to be transmitted. If the node is allowed to transmit too much original data, it will inevitably consume a lot of energy of the node. Not only is it not conducive to prolonging the service life of the node, but it will also increase the dimension of the correlation coefficient to be calculated at the base station, that is, the introduction of redundant correlation coefficients, so that the calculation amount of the base station is too large, which in turn affects the response time and data accuracy of the system ; If the number of original data groups transmitted by the node is too small, the base station cannot calculate enough correlation coefficients, and the predicted data will hardly meet the accuracy requirements, resulting in reduced system availability. Therefore, how to effectively define the amount of original data to be transmitted It is a problem worthy of in-depth discussion and solution of the algorithm. In addition, as the scale of the network increases, it is difficult for this algorithm to operate efficiently in the mode of multiple nodes corresponding to a single base station, because the base station needs to receive the compressed codes of each node and calculate the original data of each node one by one according to the correlation coefficient. When calculating the data of the first node and the last node, there must be a large time difference, so the larger the network scale, the greater the time difference, which increases the system delay and affects the application range of the algorithm. Based on these two points , the optimal order distributed clustering tree compression algorithm introduces optimal order estimation on the one hand, so as to define the number of original data groups to be transmitted by the system, not only to obtain effective correlation coefficients, but also to avoid the generation of redundant coefficients, and on the other hand On the one hand, the network is divided into clusters, and the node data is processed in units of clusters. This can not only improve the efficiency of the base station in processing the data of each node, but also enhance the ability of the base station to quickly locate outliers or abnormal nodes, thereby effectively improving the overall wireless transmission efficiency. The comprehensive monitoring ability of the sensor network system to the monitoring area.

Contents of the invention

The purpose of the present invention is to provide a wireless sensor network (WSNs) data compression method that can be used for environmental monitoring, so as to optimize the comprehensive index composed of data accuracy and node average energy consumption.

In order to achieve the above object, the technical solution of the present invention is achieved in that:

Step (1). The nodes in the monitoring area transmit their monitoring values to the base station. After all nodes transmit a set of monitoring values, the base station uses the joint information criterion (CIC) to determine the optimal order. If the obtained order is not optimal, and the node If the number of transmitted data sets does not exceed N/3, the node continues to transmit the original monitoring value; otherwise, the base station obtains the initial prediction coefficient matrix Φ _m from the value transmitted by the node, and builds a structure tree at the base station, where N represents an algorithm cycle containing The number of node transmission data groups, the method of obtaining the initial prediction coefficient matrix and the method of establishing the structure tree are mature technologies;

Step (2). The base station divides the nodes in the monitoring area into several clusters according to the prediction coefficient matrix Φ _m , and takes the cluster as the unit. The base station generates a compression command according to the node monitoring value, and the node generates the binary digit i to be transmitted according to the compression command; the base station Designate the nodes in the cluster in turn to act as the cluster head, and the cluster head is responsible for transmitting its own uncompressed monitoring values and the compressed codes of other nodes in the cluster to the base station, while the cluster head receives instructions from the base station;

Step (3). Each node in the cluster obtains the base station compression instruction sequentially through the cluster head, and each node takes the modulus of the binary value after its modulus conversion to 2 ⁱ to obtain an i-bit binary compressed code, and transmits the compressed code through the cluster head to the base station, while the cluster head transmits its uncompressed monitoring value to the base station;

(

对应第m个节点第r组监测值的估计值)，再由该节点的i位压缩码可以在结构树中定位出一个子序列，由于子序列间隔距离2^i-1Δ以概率P大于均方误差N_r，m，故在该子序列中离

最近的序列值即为节点最终估计值

同时

又成为估计同一时刻下一节点的已知条件，即在更新Φ_m时要考虑新估计出的数值；Step (4). The base station uses the cluster as a unit to obtain the estimated value of each node in the cluster from the prediction coefficient matrix Φ _m calculated in step (1) and the original monitoring value transmitted by the cluster head

(

Corresponding to the estimated value of the r-th group monitoring value of the m-th node), and then a sub-sequence can be located in the structure tree by the i-bit compressed code of the node, since the sub-sequence interval distance 2 ^i-1 Δ is greater than the average square error N _{r, m} , so in this subsequence

The most recent sequence value is the node's final estimate

at the same time

It becomes a known condition for estimating the next node at the same moment, that is, the newly estimated value should be considered when updating Φ _m ;

Step (5). After obtaining the final estimated value of all nodes in each cluster, the base station calculates and issues the compression commands required by the nodes in each cluster at the next moment. When the number of value groups monitored by the node reaches N, jump to step (1), otherwise jump to step (2).

The invention proposes a sensor network data compression method based on optimal order estimation and distributed clustering. Since the energy of nodes is mainly consumed in the transmission of original monitoring information, by introducing optimal order estimation, the number of groups of raw data transmitted by nodes to the base station is reduced, thereby reducing the average energy consumption of nodes; the calculation is concentrated on the time domain and the space domain On the series of node values that are closer to the nodes to be estimated, outlying nodes that have a weak correlation with the nodes to be estimated are eliminated, thereby effectively reducing the dimension of the data processed by the algorithm, improving the algorithm operation speed and the accuracy of node data recovery; if the monitoring area The network scale is large. After the base station clusters the regional nodes, if there is an abnormality in the region, the base station can quickly locate the cluster where the abnormal area is located, and then directly establish a connection with the node that detected the abnormality. Compared with searching the entire region one by one, it can effectively Reduce system delay and improve real-time performance of system monitoring. Using the method of the present invention, under different network scales, the sensor network data compression method based on optimal order estimation and distributed clustering is superior to direct distributed structure tree compression in terms of data accuracy and comprehensive indicators of node average energy consumption. algorithm.

Description of drawings

Fig. 1 is a block diagram of a distributed coding method;

Figure 2 is a decoding structure tree;

Fig. 3 is a flow chart of the method of the present invention.

Detailed ways

The core idea of the present invention is: on the one hand, the optimal order estimation is introduced to define the number of original data groups to be transmitted by the system. It is necessary to obtain an effective correlation coefficient and avoid the generation of redundant coefficients. On the other hand, the network Clustering processing, processing node data in units of clusters, which can not only improve the efficiency of the base station in processing the data of each node, but also enhance the ability of the base station to quickly locate outliers or abnormal nodes, thereby effectively improving the monitoring of the entire wireless sensor network system. District monitoring capabilities.

The present invention will be described in further detail below in conjunction with the accompanying drawings.

As shown in Figure 1, distributed coding means that when two or more nodes in the monitoring area perceive the original data at the same time, an asymmetric coding method is used between the nodes to establish a distributed compression structure of the wireless sensor network. When the data collected by the nodes When the sequence is a Gaussian correlated independent and identically distributed discrete sequence, the experiment proves that when node B compresses its own data, regardless of whether it knows the correlation coefficient of node A and node B data at the current moment, using the above distributed compression mode can obtain equivalent compression performance. Extend the block diagram from two nodes to n nodes, and compress the compression code obtained by compressing the current data according to the data collected before, and calculate and determine the correlation between the data of each node by the base station, and send the number of bits of the compression code to each node , and finally restore the original monitoring value of each node.

Based on the above-mentioned basic principle of distributed coding, the distributed structure tree compression algorithm first transmits N/3 sets of original values from all nodes to the base station. The size of N can be determined according to the specific application. The base station builds a structure tree based on these original values and calculates Prediction coefficient matrix Φ _m , the base station also needs to calculate the compression command corresponding to each node, that is, each node needs to compress the number of digits of the respective monitoring values (after A/D) at the next collection time, at the same time, the base station To designate a node to transmit its uncompressed monitoring value, in order to make the energy of each node in the monitoring area be consumed in a balanced manner, the node can be designated by the base station in turn, and the nodes perform 2 ⁱ modulo calculations on the original monitoring value according to the instructions received by each node, so that Compress the collected data to i bits, and after receiving the i-bit codes of each node at the base station, a smaller numerical sequence can be located in the previously established structure tree, combined with the original monitoring value transmitted by the designated node and the previously calculated prediction coefficient The matrix Φ _m restores the original monitoring value corresponding to the i-bit compressed code. After all the node values are restored at the current moment, the base station will update the prediction coefficient matrix and the number of coded digits of each node at the next moment, and so on. The value of will be continuously estimated by the forecast. It is necessary to further explain the structure tree involved in the above algorithm, the determination of the prediction coefficient and the value of i. The structure tree first starts from the mean value of the aforementioned N/3 groups of original data, and expands to both ends at intervals of Δ, Δ The size determines the accuracy of the algorithm, and the extension range is determined by the specific application. The above-mentioned extended sequence with Δ as the interval is split into the parity sequence, and two sets of subsequences with a distance of 2Δ can be obtained. In the same way, the subsequence can be split again. The number of times is determined by the number of bits i. After the i split, the distance between adjacent nodes of each subsequence is 2 ⁱ Δ, and each subsequence in the i-th layer corresponds to a unique i-bit code. According to the above expression, the decoding shown in Figure 2 can be established Structure tree, when the base station obtains the i-bit code sent by a certain node, it can locate the corresponding subsequence, and then calculate an estimated value by the prediction coefficient, and find the sequence value closest to the estimated value in the located subsequence, Thus recovering the monitoring value of the node.

This method realizes wireless sensor network data compression in the above-mentioned two-dimensional space and follows the following process, as shown in Figure 3:

Step (1). The nodes in the monitoring area transmit their monitoring values to the base station. After all nodes transmit a set of monitoring values, the base station uses the joint information criterion (CIC) to determine the optimal order. If the obtained order is not optimal, and the node If the number of transmitted data sets does not exceed N/3, the node continues to transmit the original monitoring value; otherwise, the base station obtains the initial prediction coefficient matrix Φ _m from the value transmitted by the node, and builds a structure tree at the base station, where N represents an algorithm cycle containing The number of data sets transmitted by the nodes, the method of obtaining the initial prediction coefficient and the method of establishing the structure tree are all mature technologies;

求得，其中p是概率，Δ是图2结构树中序列间距，

是方差；Step (2). The base station divides the nodes in the monitoring area into several clusters according to the prediction coefficient matrix Φ _m , and takes the cluster as the unit. The base station generates a compression command according to the node monitoring value, and the node generates the binary digit i to be transmitted according to the compression command; the base station Designate the nodes in the cluster in turn to act as cluster heads. The cluster head is responsible for transmitting its own uncompressed monitoring values and the compressed codes of other nodes in the cluster to the base station. At the same time, the cluster head receives instructions from the base station, where the value of i is according to the formula

Obtained, where p is the probability, Δ is the sequence distance in the structure tree in Figure 2,

is the variance;

Step (3). Each node in the cluster obtains the base station compression instruction sequentially through the cluster head, and each node takes the modulus of the binary value after its modulus conversion to 2 ⁱ to obtain an i-bit binary compressed code, and transmits the compressed code through the cluster head to the base station, and at the same time, the cluster head transmits its uncompressed monitoring value to the base station;

最近的序列值即为节点最终估计值

，同时，

又成为估计同一时刻下一节点的已知条件，即在更新Φ_m时要考虑新估计出的数值；Step (4). The base station uses the cluster as a unit to obtain the estimated value of each node in the cluster from the prediction coefficient matrix Φ _m calculated in step (1) and the original monitoring value transmitted by the cluster head (corresponding to the estimated value of the r-th group monitoring value of the m-th node), and then a sub-sequence can be located in the structure tree by the i-bit compressed code of the node. Since the sub-sequence interval distance 2 ^i-1 Δ is greater than mean square error N _{r, m} , so in this subsequence

The most recent sequence value is the node's final estimate

,at the same time,

It becomes a known condition for estimating the next node at the same moment, that is, the newly estimated value should be considered when updating Φ _m ;

Step (5). After obtaining the final estimated value of all nodes in each cluster, the base station calculates and issues the compression commands required by the nodes in each cluster at the next moment. When the number of value groups monitored by the node reaches N, jump to step (1), otherwise jump to step (2).

In short, the present invention proposes a sensor network data compression method based on optimal order estimation and distributed clustering: network nodes are randomly distributed in the monitoring area, after optimal order estimation, this method can divide nodes with spatial correlation In the same cluster, by establishing a prediction coefficient matrix and a decoding structure tree at the base station, the recovery and restoration of the node monitoring value encoding is realized. The node only transmits the monitoring value during the initialization process of the prediction coefficient, and then only needs to perform a simple modulo operation to realize the monitoring value. By encoding and transmitting codes with a relatively small amount of data, the average energy consumption of nodes can be greatly reduced, thereby effectively improving the comprehensive monitoring performance of sensor networks. It should be noted that methods such as different methods of using optimal order estimation at the base station (such as applying to spatial correlation order estimation or time correlation order estimation) do not depart from the spirit and scope of the technical solution of the present invention.

Claims (1)

1. The sensor network data compression method based on optimal order estimation and distributed clustering, it is characterized in that the method comprises the steps: Step (1). The nodes in the monitoring area transmit their monitoring values to the base station. After all nodes transmit a set of monitoring values, the base station uses the joint information criterion to determine the optimal order. If the obtained order is not optimal and the data set transmitted by the node If the number does not exceed N/3, the node continues to transmit the original monitoring value; if the obtained order is optimal, the base station obtains the initial prediction coefficient matrix Φ _m from the value transmitted by the node, and builds a structure tree at the base station, where N Indicates the number of node transmission data groups included in an algorithm cycle; Step (2). The base station divides the nodes in the monitoring area into several clusters according to the prediction coefficient matrix Φ _m ; taking the cluster as a unit, the base station generates a compression instruction according to the node monitoring value, and the node generates the binary digit i to be transmitted according to the compression instruction; the base station Designate the nodes in the cluster in turn to act as the cluster head, and the cluster head is responsible for transmitting its own uncompressed monitoring values and the compressed codes of other nodes in the cluster to the base station, while the cluster head receives instructions from the base station; Step (3). Each node in the cluster obtains the base station compression instruction sequentially through the cluster head, and each node takes the modulus of the binary value after its modulus conversion to 2 ⁱ to obtain an i-bit binary compressed code, and transmits the compressed code through the cluster head to the base station, while the cluster head transmits its uncompressed monitoring value to the base station; Step (4). The base station takes the cluster as a unit, and obtains the estimated value of each node in the cluster from the prediction coefficient matrix Φ _m calculated in step (1) and the original monitoring value transmitted by the cluster head

Then a subsequence is located in the structure tree by the i-bit compression code of the node, and in the subsequence

The most recent sequence value is the node's final estimate

at the same time

It becomes a known condition for estimating the next node at the same moment, that is, the newly estimated value is considered when updating Φ _m ; Step (5). After obtaining the final estimated value of all nodes in each cluster, the base station calculates and issues the compression commands required by the nodes in each cluster at the next moment. If the number of value groups detected by the node reaches N, then jump to step (1); if the number of value groups monitored by the node does not reach N, then jump to step (2); Where r represents the number of groups, m represents the node number, Φ _m represents the prediction coefficient matrix of m nodes,

Indicates the final estimated value of the rth group of the mth node,

Indicates the estimated value of the r-th group of monitoring values of the m-th node.

Images