CN115022964B - A Method and System for Indoor Positioning Radio Map Reconstruction Based on Graph Signals - Google Patents

Abstract

The invention proposes a method and system for indoor positioning radio map reconstruction based on graph signals. By modeling each reference point as a vertex of a graph and its radio data as a graph signal, a graph signal model is first developed where virtual reference points and their radio data can be interpolated into a radio map as missing vertices. Then, the latent spatial structure between all real and virtual reference points is explored to find the graph Laplacian, which is used to reconstruct the radio map via semi-supervised graph interpolation. Simulation experiments prove that the wireless map reconstruction method proposed by the present invention has achieved good performance in positioning accuracy, showing the potential of graph-based wireless map reconstruction in deep learning-based indoor positioning.

Description

A Method and System for Indoor Positioning Radio Map Reconstruction Based on Graph Signals

technical field

The invention belongs to the field of image signal processing, in particular to a method and system for indoor positioning radio map reconstruction based on image signals.

Background technique

Indoor positioning is a key technology for location-based services (LBS) in indoor navigation, building emergency rescue, and many other areas where global navigation satellite systems (GNSS) are inaccessible. For many indoor positioning scenarios, traditional distance-based positioning techniques, including Time of Arrival (TOA), Time Difference of Arrival (TDOA), Angle of Arrival (AOA) and Received Signal Strength (RSS) are still applicable. However, distance-based localization relies heavily on the accuracy of signal propagation models, which means that accurate localization often requires line-of-sight (LOS) propagation. In contrast, indoor environments are usually more diverse and complex, so non-line-of-sight propagation (NLOS) is a more common channel model. In the case of NLOS, using radio fingerprints for positioning can adapt to the irregular structure of the indoor environment and achieve high positioning accuracy.

Fingerprint-based localization is generally divided into two stages: offline training and online estimation. During the offline training phase, radio fingerprints are collected at reference points with known localizations, forming a radio map of the environment. Typically, Received Signal Strength Indicator (RSSI) and Channel State Information (CSI) can be used as fingerprints. In this field, many machine learning algorithms such as K-Nearest Neighbors (KNN), Artificial Neural Networks (ANN), Support Vector Machines (SVM), Restricted Boltzmann Machines have been widely used. Furthermore, since the relationship between radio fingerprints and localization is fundamentally nonlinear, deep learning based localization has received increasing attention in this field. For example, deep neural network (DNN), convolutional neural network (CNN), and recurrent neural network (RNN) have been proposed for indoor localization of radio fingerprints. Recently, graph neural networks (GNNs) have also been considered in this field. Compared with traditional machine learning methods, indoor positioning based on deep learning has higher positioning accuracy.

The quality of the radio map in the offline phase has a great influence on the accuracy of indoor positioning. Intuitively, a denser radio map contains more detail of the electromagnetic properties of the environment and thus enables more precise positioning. In addition, radio samples should be collected multiple times per reference point to obtain more fine-grained and reliable data. However, in practice, the number of reference points is very limited due to the cost of hardware, time and labor. In some large buildings, the cost of intensive off-site surveys may even be too high to be practical. Meanwhile, it is difficult to deploy as many reference points to build a dense radio map due to privacy/security issues or deployment constraints. Second, since indoor wireless environments are naturally time-varying, radio maps may become outdated, and the cost of real-time data calibration for a large number of reference points is not realistic. In conclusion, it is very expensive to repeatedly collect data at reference points, so the collected data is usually not fine-grained. Furthermore, despite the aforementioned difficulties, high-resolution radio maps remain impossible due to unexpected hardware failures or transmission losses, which make radio maps incomplete in space or time. In this regard, incomplete radio maps lacking radio data are one of the main challenges for deep learning-based indoor localization.

Wireless map construction or reconstruction technologies mainly include calibration-free data collection, dynamic adaptive methods, machine learning, deep learning, and crowdsourcing. Among them, calibration-free data collection such as QR-Loc systems is difficult to achieve intensive scene monitoring. The kernel parameters of the improved Bayesian regression method can adapt to dynamic changes, but a wireless monitor needs to be installed next to each AP, which increases the equipment cost. Based on deep learning methods, most of them use Generative Adversarial Network (GAN) to expand real data, and the network needs a lot of training. This kind of method mainly focuses on fingerprint recovery and data enhancement of time samples, without considering spatial enhancement. Based on machine learning methods, such as manifold learning technology, Gaussian process regression, etc., although they can be enhanced in space, it largely depends on the number and deployment of reference points and there is an over-smoothing problem. They are not sparse, they use complete sample information to make predictions, and not all sample information contributes to prediction. RGWR based on geographic weighting needs to measure the logarithmic distance model in advance, which is difficult to obtain accurately in the whole environment, and the logarithmic path loss model still cannot accurately describe the complex RSS distribution. Crowdsourcing-based methods require additional user intervention to fully exploit the full perception capabilities of mobile devices, while continuous inertial measurement unit (IMU) monitoring consumes a lot of mobile device battery.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings of the above-mentioned prior art, and provide a method and system for indoor positioning radio map reconstruction based on map signals, so as to solve the defects of spatial enhancement in radio map reconstruction in the prior art, so as to improve indoor positioning performance improvement.

In order to achieve the above object, the present invention adopts the following technical solutions to achieve:

A method for reconstructing indoor positioning radio maps based on graph signals, comprising the following steps:

Constructing an indoor positioning framework to obtain an initial indoor radio map, where some reference nodes are missing in the initial indoor radio map;

At the missing part of the reference nodes in the initial radio map, fill in the virtual reference nodes to obtain the radio map to be reconstructed. The reference nodes in the radio map to be reconstructed are regarded as nodes of the graph topology, and the fingerprint information on each reference node is regarded as information on graph topology nodes;

The fingerprint information on each virtual node in the graph topology is recovered by the graph Laplacian semi-supervised interpolation method; the reconstructed radio map is obtained.

A further improvement of the present invention is:

Preferably, several virtual nodes are filled in other positions in the initial radio map, and a newly reconstructed radio map is obtained by the graph Laplacian semi-supervised interpolation method; the other positions are outside the reference nodes in the previously reconstructed radio map s position.

Preferably, the reconstructed radio map is evaluated by RSS recovery accuracy analysis; the newly reconstructed radio map is evaluated by DNN neural network.

Preferably, the graph Laplacian semi-supervised interpolation method recovers information on each virtual node in the graph topology as follows: establish a weighted adjacency matrix reflecting the K nearest neighbors of all nodes in the graph topology, and the weighted adjacency matrix in the weighted adjacency matrix The weight is based on the positional relationship between nodes in the graph topology; the Laplacian matrix is established through the weighted adjacency matrix; the smoothness equation is established based on the Laplacian matrix, and the smoothness equation is transformed into a problem function for solving missing values in the graph topology. After solving the problem function, the information recovery on the virtual node is completed.

Preferably, the weighted adjacency matrix is W _{i, j} , in the graph signal, the closer the connection between node i and node j, the greater the value of W _{i, j} ;

Among them, m _{i, j} is the binary value (0, 1) adjacency matrix of K-nearest neighbors, if node j is the K-nearest neighbor node of node i, then m _{i, j} = 1, otherwise it is 0; g _{i, j} is the node pair Euclidean distance between (i, j).

Preferably, the problem function of the missing value is:

Wherein, y is the signal to be restored, _xi is the remaining reference nodes, S _K is the set of the remaining reference nodes, and L is the Laplacian matrix.

Preferably, the problem function of solving the missing value is solved by the CVX toolbox of matlab.

Preferably, the smoothness equation is:

TV(x)＝x ^T Lx＝∑ _i≠j W _ij ( _xi -x _j ) ² (2)

A radio map reconstruction system for indoor positioning based on graph signals, comprising:

a frame construction unit, configured to construct an indoor positioning frame and obtain an initial indoor radio map;

The graph topology establishment unit is used to fill the initial radio map with virtual nodes, obtain the radio map to be reconstructed, regard the reference nodes in the radio map to be reconstructed as the nodes of the graph topology, and regard the fingerprint information on each reference node as information on graph topology nodes;

A recovery unit is used for recovering information on each virtual node in the graph topology through a graph Laplacian semi-supervised interpolation method; obtaining a reconstructed radio map.

Preferably, it also includes:

RSS recovery accuracy evaluation unit for evaluating the reconstructed radio map by RSS recovery accuracy analysis;

DNN neural network evaluation unit for evaluating newly reconstructed radio maps by DNN neural network.

Compared with the prior art, the present invention has the following beneficial effects:

The present invention proposes a graph-based radio map reconstruction method for deep learning-based indoor localization. By modeling each reference point as a vertex of a graph and its radio data as a graph signal, a graph signal model is first developed where virtual reference points and their radio data can be interpolated into a radio map as missing vertices. Then, the latent spatial structure between all real and virtual reference points is explored to find the graph Laplacian, which is used to reconstruct the radio map via semi-supervised graph interpolation. Under the established graph signal processing model, the present invention regards the reconstruction of the radio map as the sampling and restoration of the graph signal, with the help of the prior spatial smoothing knowledge of the graph signal, adopts a suitable graph signal algorithm to semi-supervise the existing radio map Interpolation, and finally the reconstruction of the radio map is completed to achieve the improvement of spatial resolution. Then evaluate the accuracy of RSS recovery on the reconstructed radio map, or use it for deep neural network training to verify whether it is helpful to improve the accuracy of indoor positioning.

Simulation experiments prove that the wireless map reconstruction method proposed by the present invention has achieved good performance in positioning accuracy, showing the potential of graph-based wireless map reconstruction in deep learning-based indoor positioning. Compared with previous methods, the present invention utilizes the spatial smoothness of graphic signals, and can be directly used to reconstruct signals in unknown regions without early training. This method can take full advantage of the potential spatial correlation between data, rather than just exploiting the relationship on the surface of the data. Therefore, it has an advantage in the recovery accuracy of fingerprint information corresponding to most APs.

Furthermore, there are extensive NLOS occlusions in indoor positioning scenes, resulting in unsmooth space in some areas, which may affect the positioning performance of the radio map reconstruction based on the graph signal method. For this reason, the present invention also designs and discusses a method to avoid NLOS, the maximum The well-designed and reconstructed radio map method that makes use of the potential smoothness of space, carefully designs positions in the initial indoor positioning radio map and fills several virtual nodes, and obtains a newly reconstructed indoor positioning radio map, and the newly reconstructed indoor positioning radio map It has better positioning performance and lower error, and this filling method can effectively save the number of nodes in the early stage of reference node deployment, thereby reducing the cost of offline map construction, making the positioning performance test of the map signal recovery method better than Traditional methods have clear advantages. .

Description of drawings

Figure 1 is a schematic diagram of the collection of radio fingerprints for indoor positioning.

Figure 2 is the architecture of the indoor radio map reconstruction positioning system based on the graph signal method.

Figure 3 is the UCIIndoor radio map.

Figure 4 is the radio map of the fourth floor of the first building selected by UCIIndoor.

Figure 5 is the RSS recovery accuracy error graph of AP41.

Fig. 6 is the RSS recovery accuracy error graph of AP253.

Fig. 7 is a schematic diagram of the radio map after losing 40 reference nodes.

Figure 8 is a schematic diagram of a well-designed interpolation of a virtual node between two adjacent nodes.

Figure 9 is the CDF diagram of the cumulative error distribution function of different algorithms.

Fig. 10 is a schematic diagram after removing interference points.

Fig. 11 is a diagram of the average positioning error after various algorithms delete interference points.

Fig. 12 is a map of positioning error changes after three fillings after the UWB ranging 3D map loses 50 reference nodes.

Figure 13 is a diagram of the positioning error change after three fillings after the UWB ranging 3D map loses 20 reference nodes.

Detailed ways

The present invention is described in further detail below in conjunction with accompanying drawing:

For the original radio map, due to some factors, the existing reference nodes may be damaged or lost, resulting in an incomplete radio map. Either adjust the layout of existing reference nodes, drop some reference nodes, and rebuild a new radio map, or populate it directly based on existing reference points. The present invention collectively refers to these cases as the radio map reconstruction problem. Its purpose is to obtain better localization performance. These incomplete radio maps, or radio maps after artificially discarding nodes, are called initial radio maps.

Based on the above problems, an embodiment of the present invention discloses a method for reconstructing indoor positioning radio maps based on map signals, the method includes the following steps:

Step 1, the establishment of the system model: the present invention first selects the information given in the data set in the indoor positioning data set to facilitate the construction of the reference node area (such as a certain building, a certain floor, or the entire space) of the spatial graph topology, thereby selecting and constructing The original radio map on which the present invention is based. There are relatively detailed reference nodes in the original radio map, and the present invention considers most of the reference nodes in the original radio map as missing, and obtains an initial radio map containing only a small number of reference nodes, and uses it as the initial radio map before reconstruction .

Based on the reference node area selected above, a fingerprint-based indoor positioning framework is established, the reference node is regarded as a node in the graph topology, the fingerprint data is regarded as graph data, and the whole system is abstracted into a graph signal processing (Graph Signal Processing) model, namely Graph topology.

表示第N个AP发送到参考点的指纹信息。并在不同时间采集了总共N_s个样本。因此，指纹数据集的大小是N_r×N_s×N_AP，N_s是一个参考点上的样本数，N_AP是AP节点数，即指纹数据的特征维度的大小。Figure 1 demonstrates the collection of radio fingerprints for indoor localization. Assuming there are four AP nodes indoors, the initial radio map has N _r reference points. Take the first reference point as an example. The reference point receives multiple wireless fingerprint information from different AP nodes, where

Indicates the fingerprint information sent by the Nth AP to the reference point. And a total of N _s samples were collected at different times. Therefore, the size of the fingerprint dataset is N _r ×N _s ×N _AP , where N _s is the number of samples at a reference point, and N _AP is the number of AP nodes, that is, the size of the feature dimension of the fingerprint data.

Assuming that the number of reference points after wireless map reconstruction is N, the size of the final fingerprint dataset is N×N _s ×N _AP . The radio map reconstruction problem can be described as using the original N _r ×N _s ×N _AP dataset, extending or adjusting N _r to obtain the reconstructed NN _s ×N _AP data.

The proposed method of the present invention aims to reduce the cost of manually reconstructing offline radio maps by utilizing the fingerprint information and spatial topology information covering the area of reference points. Generate fingerprints of areas not covered by reference points for more accurate indoor localization. The entire positioning system architecture is shown in Figure 2. The architecture mainly consists of radio map reconstruction, recovery of node data using graph signals and a DNN localization model.

Step 2: Radio map reconstruction. The radio map reconstruction of the present invention is based on this initial radio map, followed by filling virtual nodes (either randomly or at selected specific locations) and reconstructing, considering all reference nodes (real and virtual) as graph topology nodes , fingerprint information as a graph signal. Then use the graph signal method (Graph Laplacian semi-supervised interpolation) of formula (3) to generate fingerprint information on these virtual nodes, so as to obtain different indoor positioning fingerprint training sets.

The populated radio map has N reference nodes and information on the existing K actual reference nodes. The data of other (N-K) nodes is considered to be lost. In addition to filling virtual nodes in the original lost position to verify the accuracy of RSS recovery, the present invention also elaborately designs a new reconstruction method in order to overcome the NLOS situation, and the original radio map along a certain direction (longitude, latitude or x, y or z direction) inserts a dummy node between each pair of real nodes that are already in close proximity. This construction of the invention can overcome most NLOS situations.

The present invention uses graph signal processing means to restore or generate fingerprint data on the reconstructed virtual reference node, and the specific graph Laplacian semi-supervised interpolation process is:

以及与该信号对应的加权无向图记作

其中v＝{1，…，N}是N个顶点的集合，

是节点之间边的集合。可以用x_i来表示在节点i∈v处的信号值大小。邻接矩阵W是一个加权对称矩阵，反映了边之间的连接强度关系，如果有边(i，j)∈ε，则W_i，j≥0，否则W_i，j＝0。节点i和节点j的联系(相关性)越紧密，则W_i，j的值就越大。拉普拉斯矩阵L＝D-W被引入，其中D是度矩阵。(1) Consider those signals related to undirected, weighted, connected graphs, denoted as

And the weighted undirected graph corresponding to this signal is written as

where v={1,...,N} is a set of N vertices,

is the set of edges between nodes. We can use _xi to represent the magnitude of the signal value at node i∈v. The adjacency matrix W is a weighted symmetric matrix that reflects the connection strength relationship between edges. If there is an edge (i, j)∈ε, then W _{i, j} ≥ 0, otherwise W _{i, j} = 0. The closer the connection (correlation) between node i and node j, the greater the value of W _i,j . A Laplacian matrix L=DW is introduced, where D is the degree matrix.

然后让M的对应元素为1，记录为

每条边的权重与两个节点距离的平方成反比。最后，构造以下加权邻接矩阵W:(2) Then use the K-nearest neighbor method to construct the spatial graph topology. Specifically, according to the geographical locations of all nodes, the distance g i _, j between all node pairs (i, j) is calculated to form a distance matrix G. Then it is necessary to eliminate the connections between some nodes whose physical distance correlation is less. Therefore, create an all-zero matrix M, and then need to find the first k elements with the smallest distance for the i-th row of the matrix G, which is recorded as

Then let the corresponding element of M be 1, record as

The weight of each edge is inversely proportional to the square of the distance between two nodes. Finally, construct the following weighted adjacency matrix W:

When W is constructed, the corresponding degree matrix D and Laplacian matrix L=D−W can also be constructed. In the scenario of the present invention, the nodes are used as the vertices of the graph, the distance relationship between the nodes is used as the weight of the edges, and the fingerprint data is used as the information on the nodes of the graph.

(3) Many recovery methods are only based on the superficial relationship of the data without extracting the underlying relationship of the data. In this embodiment, it is assumed that there are potential spatial features between the reconstructed actual reference node and the virtual reference node. The wireless fingerprint information between nodes with closer distance should be similar, while the data between nodes with farther distance should be more different, this property is called spatial smoothness. Spatial smoothness is an important characteristic of graphic signals. On a connected graph, assuming that the graph information continues to diffuse, the signal values of different nodes will gradually become similar over time. In the extreme case, the signal values of all nodes on the graph will become the same. To measure the smoothness or signal correlation of the signal y, the Laplacian quadratic form below is used to describe this relationship. The smaller the value of the equation, the smoother the signal on the graph.

TV(y)=y ^T Ly=∑ _i≠j W _ij (y _i -y _j ) ² (2)

When data for one or more nodes is missing, the present invention addresses this issue through a graph semi-supervised learning framework. The framework assumes that data resides in graph nodes. The data between spatially adjacent nodes should be smoother, that is, the graph signal is smoother, and the smoothness equation shown in formula (2) should be smaller and smoother. The present invention considers that the value of the missing position has the smooth relationship with the values of its adjacent known nodes, and obtains the spatial smoothness representation ^yT Ly. Then, the smoothness equation is transformed into a problem function for solving missing values in the graph topology, as shown in formula (3), and the global quantity represented by spatial smoothness is optimized by formula (3) to find the missing value, that is, on the virtual node The information of has been restored, and the radio map can be reconstructed after solving the formula (3). Constraints in this process restrict that the value generated at a known location should be equal to the known value.

Specifically, if y is the signal to be recovered, it is known that the signals on K nodes are x. The purpose of graph semi-supervised interpolation is to estimate y and guarantee that x _i =y _i , i∈S _K at known nodes. Similar to low-rank matrix recovery, this method is semi-supervised. These unobserved values are computed at each time step for a given observed value. The method does not require a training phase, and the missing NK node data can be directly reconstructed when node S _K is observed, or when virtual sensors including unknown values are wanted. This problem can be expressed as:

Solving the above problem through the CVX toolbox of matlab, the signal y to be recovered can be obtained, that is, the fingerprint information in the reconstructed wireless map is obtained, and the reconstructed radio map is correspondingly obtained, and there are N reference nodes in the radio map , each reference node has its own longitude and latitude, and each reference node has its corresponding fingerprint information.

Further, although nodes have underlying graph structure features, there is a common NLOS problem in indoor environments due to the particularity of indoor localization scenarios. This leads to the fact that the distance between the generated virtual node and its neighbors may be relatively far, so their fingerprint data may not be smooth due to signal occlusion and interruption. This problem may limit the application of graph smoothness to a certain extent. In the radio map reconstruction problem of the present invention, it is necessary to maximize the underlying smoothness of the map despite NLOS blurring the map. Therefore, this embodiment also proposes a well-designed radio map filling method, using the positioning accuracy of the test set as an indirect evaluation index. Fill in several virtual nodes in other positions in the reconstructed radio map, repeat steps (1) to (3), restore the fingerprint information on the newly added reference nodes, and obtain the new reconstruction by the Laplacian semi-supervised interpolation method. organization's radio map;

Further, considering that some areas in the building are walls or other non-free spaces, and no target can appear, the present invention will also remove these redundant interfering position reference nodes newly added under the well-designed filling method. The indoor positioning accuracy of the newly reconstructed radio map using the described method is better than that of the original radio map, and also better than the positioning accuracy of the newly reconstructed baseline method.

Step 4: training set training stage. Input the fingerprint information in the reconstructed radio map generated by step 2 into the neural network of the present invention for training, obtain the corresponding target longitude and latitude of each fingerprint data through the neural network, and combine the calculated longitude and latitude with the fingerprint The actual longitude and latitude of the data are compared and calculated to obtain the loss function. When the loss function meets the set requirements, the neural network training ends, and finally the obtained network model parameters are saved. The indoor positioning model used in the present invention is a three-layer DNN model. The input size of the network is (N×N _s )×N _AP , that is, there are N×N×N _s samples, and the feature dimension of each sample is N _AP . For different datasets, the number of neurons in layer 1, layer 2 and layer 3 is different. Can be determined by the actual situation. The neural network positioning test set selects the regions selected by the present invention corresponding to the original test set to check the positioning performance.

Using the MSE function as the loss function of the DNN, the network will directly output the coordinates of the target. Using the Adam optimizer, the initial learning rate of the network is 0.01. Use _L2 loss as weight decay, and set the value to 5×10 ^-4 . In addition, in order to avoid the death of network neurons to a certain extent, the activation function of each FC layer uses the Leakyrelu function.

Step 5: Performance verification stage. Input the test set data into the network model saved in step 3 to verify the positioning performance of the method of the present invention.

In order to facilitate the analysis of RSS recovery accuracy. Assuming that the original radio map has N reference nodes, and N _r reference nodes are left after randomly losing nodes, if the same radio map is reconstructed as before, since the lost points are randomly distributed, it can be considered as a random In the reconstruction method, the fingerprint information in the reconstructed radio map and the information of the known original N reference nodes are analyzed for RSS recovery accuracy.

Analyze and evaluate the gap between the radio map and the baseline method using the graph signal method to reconstruct the original lost node position by RSS recovery accuracy analysis; further, for the well-designed new layout of the present invention, due to not knowing the original N reference points location, the location accuracy performance gap between the newly reconstructed radiomap using the graph signal method and the baseline method for indoor positioning using the graph signal method in well-designed location via the DNN neural network of step 4, which is used as the radiomap reconstruction Indirect evaluation criteria. An existing, conventional method of recovering the graph signal was set as the baseline method. It is found that the radio map reconstructed by the graph signal method has better RSS recovery accuracy at the lost node locations than the baseline method.

The invention also discloses an indoor positioning radio map reconstruction system based on map signals, including:

a frame construction unit, configured to construct an indoor positioning frame and obtain an initial indoor radio map;

The graph topology establishment unit is used to fill the initial radio map with virtual nodes, obtain the radio map to be reconstructed, regard the reference nodes in the radio map to be reconstructed as the nodes of the graph topology, and regard the fingerprint information on each reference node as information on graph topology nodes;

A recovery unit is used for recovering information on each virtual node in the graph topology through a graph Laplacian semi-supervised interpolation method; obtaining a reconstructed radio map.

Further, it also includes:

RSS recovery accuracy evaluation unit for evaluating the reconstructed radio map by RSS recovery accuracy analysis;

DNN neural network evaluation unit for evaluating newly reconstructed radio maps by DNN neural network.

Example 1

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

In the experiment, the numerical results of the algorithm performance were demonstrated in the 2D scene of the fourth floor of the first building under the UCIIndoor dataset and the UWB ranging 3D scene dataset. At the same time, Gaussian process regression (GPR) and linear interpolation (Linear) are selected as the comparison method of the present invention.

Figure 3 is the original radio map of UCIIndoor. The X-coordinate is the longitude, the Y-coordinate is the latitude, and the Z-coordinate is the floor. Because the three buildings are far away from each other, it is difficult to establish a connected graph on all reference points. Moreover, the original dataset does not give floor heights, so it is not suitable for forming distance-based 3D graphic topology. For this purpose, Figure 4 is the radio map of the fourth floor of the first building that was selected, with a total of 68 reference nodes. Table 1 and Figure 5, and Figure 6 show the RSS recovery accuracy of the original lost nodes (random reconstruction method) using the remaining 28 reference nodes after randomly losing 40 reference nodes. Since there are a total of 520 APs, it cannot be shown in detail. Here Some representative results are shown, the abscissa is 40 missing nodes, and the ordinate is RSS deviation. The fingerprint data recovery accuracy of the method that can find the graph signal is the highest, which is better than the traditional method of comparison.

Fig. 7 is a schematic diagram of a radio map after losing 40 reference nodes, and Fig. 8 is a schematic diagram of a carefully designed interpolation of a virtual node between two adjacent nodes. Table 2 shows that 40 nodes were randomly lost twice in the original data set, called Case1 and Case2 respectively, when reconstructed according to the radio map in this implementation, graph Laplacian semi-supervised interpolation, Gaussian process regression and linear interpolation test set It can be found that in the scenario of this embodiment, the positioning error of the graph signal method is significantly better than that of Gaussian process regression and linear interpolation. Fig. 9 is the cumulative error distribution function of different algorithms, it can be found that the method of this embodiment is superior to the comparison scheme, especially in the control of larger errors.

Table 1

RSS Estimation Error Performance Comparison of Different Algorithms for Reconstructing Original Location Data (DBM)

Method AP7 AP15 AP23 AP69 AP184 AP185 AP220 ... Average Graph 0.1438 0 2.1633 0 1.0890 1.0858 0 ... 0.4864 GPR 0.2045 0 2.2292 0 1.2045 1.3392 0 ... 0.5192 Linear 0.4561 0 5.5733 0 1.4225 1.3939 0 ... 0.8981

Table 2

Performance comparison of different algorithms for reconstructing well-designed new location data

Scenario Nolost Lost but not recovery Graph GPR Linear interp case1 10.3687m 12.1040m 11.1908m 11.6164m 13.2037m case2 10.3687m 10.6638m 10.4294m 10.9735m 12.4048m

Also, since the building is in the shape of an "X", the middle part where the "X" can be found may be a wall or other part that cannot be a free space. Therefore, these new nodes in the middle part are impossible to exist in practice, so they have become a source of disturbing data that interferes with the localization results and should be eliminated. Fig. 10 is a schematic diagram after removing interference points. In the present invention, the suffix "-r" is used to indicate the situation after deletion. Figure 11 shows the average positioning error after various algorithms delete interference points. It can be found that after the interference points are removed, the positioning accuracy of any method has been further improved, and the method of graph signal is still the best method among them.

Likewise, the above method can be applied to 3D scenes. Figure 12 and Figure 13 show that after the UWB ranging 3D data set (with 324 reference nodes) has randomly lost 50 and 20 reference nodes, it is first filled into the symmetrical 324 nodes as before. Then fill in more dummy nodes in an elaborate fashion based first on the x-direction and then the y-direction. Finally, the average positioning error trend graphs after radio maps containing 324, 612 and 1156 points were built respectively. It can be found that the graph signal method proposed in the present invention not only improves the performance in 2D scenes, but also significantly improves the positioning performance of the system in 3D scenes.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the scope of the present invention. within the scope of protection.

Claims (5)

1. An indoor positioning radio map reconstruction method based on a map signal is characterized by comprising the following steps:

constructing an indoor positioning frame, and obtaining an indoor initial radio map, wherein part of reference nodes are missing in the indoor initial radio map;

filling virtual reference nodes at the reference nodes of the missing part of the initial radio map to obtain a radio map to be reconstructed, regarding the reference nodes in the radio map to be reconstructed as nodes of a map topology, and regarding fingerprint information on each reference node as information on the nodes of the map topology;

recovering fingerprint information on each virtual node in the graph topology by a graph Laplace semi-supervised interpolation method; obtaining a reconstructed radio map;

step 1, signals related to undirected, weighted and connected graphs are recorded as

Weighted undirected corresponding to the signalThe drawing is marked as->

Wherein->

Is a set of N vertices, < >>

Is a collection of edges between nodes; by x _i Is indicated at node->

Signal value magnitude at; the adjacency matrix W is a weighted symmetric matrix reflecting the connection strength relationship between edges, and if edges (i, j) ∈ε are present, W _i,j Not less than 0, otherwise W _i,j =0; introducing a laplace matrix l=d-W, wherein D is a degree matrix;

step 2, constructing a space diagram topology by using a K-nearest neighbor method; calculating the distance g between all node pairs (i, j) according to the geographic positions of all nodes _i,j Forming a distance matrix G; creating an all-zero matrix M, then finding the first k elements with the smallest distance for the ith row of the matrix G, and recording as

Then let M's corresponding element be 1, record as +.>

The weight of each edge is inversely proportional to the square of the distance between two nodes; finally, the following weighted adjacency matrix W is constructed:

when W is constructed, the corresponding degree matrix D and laplace matrix l=d-W are also constructed; taking nodes as vertexes of the graph, taking distance relations among the nodes as weights of edges, and taking fingerprint data as information on the nodes of the graph;

in step 3, on the connected graph, in order to measure the smoothness or signal correlation of the signal y, TV (y) is solved using the following laplace quadratic form, where TV (y) is:

TV(y)＝y ^T Ly＝Σ _i≠j W _ij (y _i -y _j ) ² (2)

when data of one or more nodes is lost, the data is solved by a graph semi-supervised learning framework, and the value of the missing position is considered to have a smooth relation with the value of the adjacent known nodes on the premise that the framework data is positioned in the graph nodes, so that the spatial smoothness is expressed as y ^T Ly; then, converting the smoothness equation into a problem function for solving missing values in the graph topology, optimizing the global quantity expressed by the space smoothness through the formula (3), and finding the missing values so that the information on the virtual nodes is recovered, wherein the problem function is shown in the formula (3);

solving a formula (3) to obtain a signal y to be recovered, obtaining fingerprint information in a reconstructed radio map, and correspondingly obtaining the reconstructed radio map, wherein the radio map is provided with N reference nodes, each reference node has respective longitude and latitude, and each reference node has corresponding fingerprint information;

filling a plurality of virtual nodes in other positions of the reconstructed radio map, repeating the steps 1-3, recovering fingerprint information on newly added reference nodes, and obtaining the newly reconstructed radio map through a graph Laplace semi-supervised interpolation method.

2. The indoor positioning radio map reconstruction method based on the map signal according to claim 1, wherein the reconstructed radio map is evaluated by RSS restoration accuracy analysis; the newly reconstructed radio map is evaluated by means of a DNN neural network.

3. The indoor positioning radio map reconstruction method based on the map signal according to claim 1, wherein the problem function of the missing value is solved by a CVX toolbox of matlab.

4. A map reconstruction system for indoor positioning radio based on map signals for implementing the method of claim 1, comprising:

the frame construction unit is used for constructing an indoor positioning frame and obtaining an indoor initial radio map;

the map topology establishing unit is used for filling virtual nodes into the initial radio map to obtain a radio map to be reconstructed, and taking reference nodes in the radio map to be reconstructed as nodes of the map topology, and fingerprint information on each reference node is taken as information on the nodes of the map topology;

the recovery unit is used for recovering the information on each virtual node in the graph topology through a graph Laplace semi-supervised interpolation method; and obtaining a reconstructed radio map.

5. An indoor positioning radio map reconstruction system based on a map signal as recited in claim 4, further comprising:

an RSS recovery precision evaluation unit for evaluating the reconstructed radio map by means of RSS recovery precision analysis;

and the DNN neural network evaluation unit is used for evaluating the newly reconstructed radio map through the DNN neural network.

Images