CN104540221B - WLAN indoor orientation methods based on semi-supervised SDE algorithms - Google Patents

Abstract

A WLAN indoor positioning method based on a semi-supervised SDE algorithm relates to the field of indoor positioning. The invention aims to solve the problems of high online positioning complexity and poor real-time positioning of mobile terminals existing in existing WiFi indoor positioning methods. The present invention introduces a semi-supervised SDE dimensionality reduction algorithm and uses unmarked data that is easy to collect to find out the low-dimensional manifold of high-dimensional data representing position information, effectively reducing the positioning accuracy of the WLAN indoor positioning system while ensuring the positioning accuracy of the WLAN indoor positioning system. The calculation amount of the positioning process. At the same time, it reduces the workload of reference point data collection and provides a simple and easy way for the real-time update of the database. The online positioning of the present invention has low complexity and strong real-time positioning of the mobile terminal. The present invention is applicable to WLAN indoor positioning.

Description

WLAN indoor positioning method based on semi-supervised SDE algorithm

technical field

The invention relates to the field of indoor positioning, in particular to an indoor positioning method of position fingerprints.

Background technique

With the wide popularization of wireless network, mobile communication and ubiquitous computing, location-based services (LBS, Location-based Services) are getting more and more attention, and how to determine the user's location is the key to realize LBS. As we all know, the Global Positioning System (GPS, Global Positioning System) system estimates the position by measuring the time difference of arrival of signals from 5 to 24 satellites by a receiver, and can provide a relatively high-precision positioning estimate. However, GPS cannot achieve positioning indoors and in densely populated cities due to the non-line-of-sight of satellite signals. With the proposal of the IEEE802.11 standard, wireless local area networks (WLAN, Wireless Local Area Networks) have been widely distributed in campuses, office buildings and homes. The indoor positioning system based on received signal strength has been widely valued because of its characteristics of convenient deployment, low cost, and no need to add special hardware for positioning measurement.

In the WLAN environment, measure the received signal strength (RSS, Received Signal Strength) value from the wireless access point (AP, Access Point) through the wireless network card and corresponding software of the mobile terminal to obtain information related to the corresponding location, and then pass the matching Algorithms to predict where mobile users are located. Among them, the positioning algorithm based on location fingerprints is widely used because of its high positioning accuracy, full use of existing facilities, and little impact on users for upgrades and maintenance. The position fingerprint positioning algorithm is divided into two steps: the offline measurement stage and the online positioning stage. The offline stage is mainly to establish the corresponding relationship between the position and the received signal strength, that is, set the reference point in the area to be positioned according to certain rules, and measure the location of the reference point. Based on the received different AP signal strength values, the corresponding location fingerprint database Radio Map is established. In the online positioning stage, the corresponding matching algorithm is adopted through the RSS value received by the test point, mainly including the nearest neighbor method, K nearest neighbor method, probability method and neural network method. Among them, the K nearest neighbors method (KNN, K Nearest Neighbors) has certain advantages in algorithm complexity and positioning accuracy, and is widely used in online positioning matching to find the closest position in the position fingerprint database as the final position estimation result. The Radio Map established in the offline stage contains a large amount of data information, and with the expansion of the positioning area and the increase of reference points, the amount of Radio Map information increases exponentially.

The WLAN indoor positioning system based on location fingerprint can effectively improve the positioning accuracy of the system by collecting as much data information as possible in the offline stage. In the online positioning stage, a large amount of data information is processed, which increases the amount of data calculation in the positioning process. For the mobile terminal, its processing capacity is limited, which makes the positioning algorithm difficult to run. At the same time, some feature information not only cannot provide effective location information, but may even affect the accuracy of positioning results.

When the number of APs increases, the dimensional information representing the number of APs in the Radio Map becomes high-dimensional data, and the burden of processing high-dimensional data can be reduced by dimensionality reduction. High-dimensional data may contain many features, all of which describe the same thing, and these features are closely connected to a certain extent. For example, when the same object is photographed from multiple angles at the same time, the obtained data contains overlapping information. If some simplified non-overlapping expressions of these data can be obtained, the efficiency of data processing operation will be greatly improved and the accuracy will be improved to a certain extent. The purpose of dimensionality reduction algorithm is to improve the processing efficiency of high-dimensional data.

There are currently many dimensionality reduction algorithms for different purposes, including linear and nonlinear dimensionality reduction algorithms. Among them, PCA and LDA are typical linear dimensionality reduction algorithms. This type of algorithm has good dimension reduction results for high-dimensional data with linear structure, but it is not suitable for high-dimensional data with nonlinear structure. The nonlinear dimensionality reduction algorithm is mainly based on the manifold learning algorithm. The SDE algorithm is proposed based on the LDE algorithm in the manifold learning algorithm, which is a typical manifold learning algorithm based on feature extraction.

Contents of the invention

The present invention aims to solve the problems of high online positioning complexity and poor real-time positioning of mobile terminals existing in existing WiFi indoor positioning methods, thereby providing a WLAN indoor positioning method based on a semi-supervised SDE algorithm.

The WLAN indoor positioning method based on the semi-supervised SDE algorithm, which is realized by the following steps:

Step 1. Arranging m access points AP (AP _j , 1≤j≤m) for the indoor environment, ensuring that any point in the indoor environment is covered by signals sent by two or more wireless access points AP; m is a positive integer;

Step 2. Set reference points evenly in the indoor environment, choose a reference point as the origin to establish a rectangular coordinate system, obtain the coordinate positions of each reference point in the rectangular coordinate system, and use the signal receiver to collect and collect the coordinates of each reference point on each reference point. Record the received signal strength RSS value k times from each AP, and perform data processing; k is a positive integer;

Step 3, divide the indoor positioning environment into Q sub-areas according to the K-means clustering algorithm, and mark the respective category information for the reference points of each sub-area;

Step 4: collect random unlabeled RSS data, compare it with the feature vectors of each sub-region obtained in step 3, that is, calculate the distance from the feature vectors of each sub-region, and divide the random data category into the nearest feature vector within the sub-region;

Step 5, using the SDE algorithm for each sub-region in the K sub-regions to obtain a feature transformation matrix;

The input parameter of the SDE algorithm, that is, the value of the intrinsic dimension, estimates the RadioMap partition data through the existing intrinsic dimension estimation algorithm, gives the estimated value of the intrinsic dimension of each area data, and determines each area The feature transformation matrix of , and generate a dimensionally reduced location fingerprint database Radio Map ^* ;

Step six, compare the signal strength RSS value obtained by the point to be tested with the feature vectors of each sub-area obtained in step three, that is, to obtain the distance between the feature vector of the test point and the feature vector of each sub-area, and locate the test point at In the subregion closest to its feature vector;

Step 7. In the located sub-region, use the feature transformation matrix obtained in step 5 to reduce the dimensionality of the RSS value of the point to be measured to obtain a low-dimensional RSS ^* , and match it with the fingerprint database Radio Map ^* , using the K nearest neighbor position The fingerprint positioning algorithm accurately locates the test points.

The specific steps of using the signal receiver to collect and record the received signal strength RSS value k times from each AP at each reference point described in step 2, and perform data processing are:

Step 21. Obtain a k×m order matrix for each reference point, the i-th row and j-th column of the matrix represent the RSS value received from the j-th AP in the i-th collection; k, m, i, j are positive integers;

Step 22: Add all the elements in the k×m order matrix column vector obtained by each reference point to get a value, and then divide this value by k, then each reference point gets a 1×m vector , for each reference point, this vector is called the feature vector of the reference point, and the jth element in the vector is used as the jth feature of the reference point; if the RSS value of some APs on a reference point cannot be detected , then it is assigned as the minimum signal value that can be received in this environment -100dBm, so the range of the received signal strength RSS value v of any reference point is -100dBm≤v≤0dBm; this group of vectors is used to realize the aggregation of step 3 class partition.

The specific steps for dividing the indoor positioning environment into Q sub-regions according to the K-means clustering algorithm described in step three are:

Step 31, input the eigenvectors and the number of subregions Q of all reference points measured in step 22;

Step three and two, randomly select the RSS of K reference points from the data obtained in step two and two, that is, the eigenvector values of each reference point are used as the cluster centers of K subregions;

Step 33: Calculate the Euclidean distance between each reference point and the feature vectors of the K cluster centers, and assign each reference point to the sub-region with the smallest Euclidean distance;

Steps three and four, calculating the mean value of the RSS values of each reference point in each sub-region to obtain a new cluster center;

Steps 3 and 5, repeat steps 3 and 3 and 4 until the center of each sub-region does not change;

Step 36: Obtain K subregions and the corresponding clustering center vectors of each subregion, namely: a 1×m vector, which is called the feature vector of this subregion, and the jth element of this vector represents this subregion The jth feature of is also the RSS mean value obtained from the jth AP in this sub-region.

Step 4 The specific process of classifying random RSS data is as follows:

Step 41, input randomly collected unlabeled data, the unlabeled data only has signal strength value but no location information;

Step 42. Comparing the unlabeled data with the feature vectors of each sub-area obtained in step 3, that is, calculating the distance from the feature vectors of each sub-area, and distributing the random data in the sub-area closest to its feature vector, as the category it belongs to.

The specific method of using the SDE algorithm to reduce the dimensionality of each of the K sub-regions described in step five, determine the feature transformation matrix of each region, and generate a new location fingerprint database is as follows:

Step 51. Construct an adjacency graph:

Construct undirected graphs G and G' according to the class label information of high-dimensional data points and their neighbor relationships; where the neighbor relationship is the criterion given by the KNN algorithm, that is, select the nearest K points of the data point as its neighbors, and G represents when When the class label information y _i of xi and _{x j} = y _j and xi _and x _j are K neighbors; G' indicates that when the class label information _{y i ≠} y _j of xi and x _j and _xi x _{and j} are K-nearest neighbors;

Step 52. Calculate the weight matrix:

According to the adjacency graph constructed in step 51, the Gaussian-like function is used to calculate the weight matrix, and its expression is shown in (1):

Among them: w _ij represents the weight between the neighbor points x _i and x _j , || _xi -x _j || ² is the norm distance between the neighbor points x _i and x _j , and the norm distance is calculated by matrix , t is the weight normalization parameter;

Step five and three, determine the objective function and its solution:

According to the goal of the SDE algorithm: maximize the inter-class scatter while minimizing the intra-class scatter; the scatter is represented by the norm distance representing similar and non-like data points;

The corresponding optimization objective function is obtained from the goal of the SDE algorithm, as shown in formula (2), the feature transformation matrix P is the optimal solution to be found:

According to the optimization objective function given by formula (2), it can be known that:

Calculation Formula of Known Matrix Norm This formula is consistent with the calculation formula ||A|| ² ＝tr(AA ^T ) of the trace of the matrix, so the formula (2) is expressed as the trace of the matrix:

Formula (3) is further simplified to:

Since the calculated scalar properties and weight elements of the matrix trace are all real numbers, formula (4) is simplified as:

J(V)＝2tr{P ^T [X(D′-W′)X ^T ]P} (5)

Similarly, formula (2) can be simplified as:

In formula (6), X is the input high-dimensional data, W and W' are the weight matrices corresponding to G and G' respectively; D and D' are diagonal matrices, and their diagonal elements are obtained by formula (7):

Applying the Lagrangian multiplier method to formula (6), it can be obtained as shown in formula (8):

X(D'-W')X ^T P=λX(DW)X ^T P (8)

Perform generalized eigenvalue decomposition on formula (8), and obtain the eigenvalue λ=[λ ₁ ,λ ₂ ,…,λ _n ] ^T and eigenvector p=[p ₁ ,p ₂ ,…,p _n ] ^T ;

Step 54. Eigendimension estimation:

According to the eigenvalues and eigenvectors obtained in steps 5 and 3, the eigendimension is estimated according to formula (9):

Among them: η ^* is the threshold value of information retained in the projection space, which is usually greater than 80%, that is, the ratio of the sum of the first d largest eigenvalues to the sum of all eigenvalues is not less than 80%, which satisfies the requirement for better information on the original data low-dimensional embedding;

Step 55. Calculate the embedding result:

Set the eigendimension estimation threshold according to step 54, select the eigenvectors corresponding to the d eigenvalues to form a transformation matrix P=[p ₁ ,p ₂ ,…,p _d ], and calculate the input height according to formula (10) The dimensionality-reduced data Z _i of the dimensional data point x _i is:

Z _i =P ^T x _i (10)

The low-dimensional signal fingerprint data and feature transformation matrix are obtained through the SDE algorithm, which are recorded as Radio Map ^* and P respectively.

For each sub-region in the K sub-regions described in step 7, use the low-dimensional RadioMap ^* and the feature transformation matrix obtained in step 5 respectively, and use the k nearest neighbor position fingerprint positioning algorithm to locate the test point. The specific method is:

Step 72. Low-dimensional feature vectors of test points and the i-th reference point in the low-dimensional Radio Map ^* of the area The distance between is obtained by formula (11):

Step seven three, select k reference points closest to the test point feature vector distance from small to large in the result, and calculate the position estimation coordinates of the test point by formula (12)

Complete the positioning of the test point.

The present invention introduces a semi-supervised SDE dimensionality reduction algorithm and uses unmarked data that is easy to collect to find out the low-dimensional manifold of high-dimensional data representing position information, effectively reducing the positioning accuracy of the WLAN indoor positioning system while ensuring the positioning accuracy of the WLAN indoor positioning system. The calculation amount of the positioning process. At the same time, it reduces the workload of reference point data collection and provides a simple and easy way for the real-time update of the database. The online positioning of the present invention has low complexity and strong real-time positioning of the mobile terminal.

Description of drawings

FIG. 1 is a schematic diagram of an indoor scene described in Embodiment 3 of the present invention.

Detailed ways

Embodiment 1. The positioning process of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in this embodiment is:

Step 1. Arranging m APs (AP _j , 1≤j≤m) for the indoor environment, ensuring that any point in the environment is covered by signals sent by two or more APs;

Step 2. Set reference points evenly in the indoor environment, choose a reference point as the origin to establish a rectangular coordinate system, obtain the coordinate positions of each reference point in the rectangular coordinate system, and use the signal receiver to collect and collect the coordinates of each reference point on each reference point. Record the received signal strength RSS value k times from each AP and perform corresponding data processing;

Step 3: Divide the indoor positioning environment into Q sub-areas according to the K-means clustering algorithm, and mark the respective category information for the reference points of each sub-area. The received signal strength RSS values of each reference point in each sub-region have similar characteristics, that is, the eigenvectors of each reference point are similar;

Step 4. Collect random unmarked RSS data (the difference from the reference point is that there are only signal strength values but no location information), and compare with the feature vectors of each sub-region obtained in step 3, that is, to obtain the characteristics of each sub-region The distance of the vector, which divides the random data category into the sub-region closest to its feature vector;

Step 5: Apply the SDE algorithm to each sub-region in the K sub-regions. As the input parameter of the SDE algorithm: the value of the intrinsic dimension (Intrinsic Dimensionality), the Radio Map partition data is estimated through the existing intrinsic dimension estimation algorithm, and the estimated intrinsic dimension of each area data is given . Determine the feature transformation matrix of each region, and generate a dimensionally reduced location fingerprint database (Radio Map ^* );

Step six, compare the signal strength RSS value obtained by the point to be tested with the feature vectors of each sub-area obtained in step three, that is, to obtain the distance between the feature vector of the test point and the feature vector of each sub-area, and locate the test point at In the subregion closest to its feature vector;

Step 7. In the located sub-region, use the feature transformation matrix obtained in step 5 to reduce the dimensionality of the RSS value of the point to be measured to obtain a low-dimensional RSS ^* , and match it with the fingerprint database Radio Map ^* , using the K nearest neighbor position The fingerprint positioning algorithm accurately locates the test points.

Embodiment 2. This embodiment is a further description of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in Embodiment 1. In Step 2 of Embodiment 1, using a signal receiver at each reference point The specific steps for collecting and recording the received signal strength RSS value k times from each AP and performing corresponding data processing are:

Step 21. Obtain a k×m order matrix for each reference point, and the i-th row and j-th column of the matrix represent the RSS value received from the j-th AP in the i-th collection;

Step 22: Add all the elements in the k×m order matrix column vector obtained by each reference point to get a value, and then divide this value by k, so that each reference point gets a 1×m vector , for each reference point, this vector is called the feature vector of the reference point, and the jth element in the vector (that is, the mean value of signal strength RSS obtained from AP _j ) can be used as the jth feature of the reference point. Sometimes the RSS value of some APs at a reference point cannot be detected, and it is assigned as the minimum signal value that can be received in this environment -100dBm, so the range of the received signal strength RSS value v of any reference point is - 100dBm≤v≤0dBm. This set of vectors will be used to implement the cluster partitions in step three.

This embodiment provides a fingerprint database sample for subsequent specific embodiments.

Specific embodiment three, this embodiment is a further description of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in specific embodiment one, and the indoor positioning environment according to the K-means clustering algorithm described in step three of specific embodiment one The specific steps of dividing into Q sub-regions are as follows:

Step 31, input the eigenvectors and the number of subregions Q of all reference points measured in step 22;

Step 32, randomly select the RSS (i.e. the eigenvectors of each reference point) values of K reference points from the data obtained in step 22 as the cluster centers of K subregions;

Step 33: Calculate the Euclidean distance between each reference point and the feature vectors of the K cluster centers, and assign each reference point to the sub-region with the smallest Euclidean distance;

Steps three and four, calculating the mean value of the RSS values of each reference point in each sub-region to obtain a new cluster center;

Steps 3 and 5, repeat steps 3 and 3 and 4 until the center of each sub-region does not change;

Step 36: Obtain K subregions and the corresponding clustering center vectors of each subregion (i.e. a 1×m vector, which is called the feature vector of this subregion, and the jth element of this vector represents the value of this subregion The j-th feature is also the RSS mean value obtained from the j-th AP for this sub-region).

This embodiment can ensure that the positioning environment is effectively partitioned, so that the signal strength RSS values received by the reference points in each sub-area from each AP, that is, the similarity of the eigenvectors of each reference point is greater than that from two different sub-areas. The eigenvector similarity of the reference point also lays the foundation for the classification of random RSS data in step 4.

Conduct experiments in the indoor scene shown in Figure 1, with 19 laboratories, 1 meeting room and 1 table tennis room, Indicates an elevator, the wall is made of bricks, aluminum alloy windows and metal doors, the wireless access point AP is Linksys WAP54G-CN, and APs 1 to 27 are marked with AP1, AP2, ..., AP27, and each AP is fixed at a distance from 2m above the ground. The signal receiver is 1.2m above the ground. The arrow marks in the figure indicate the positions of APs 1 to 27. The corridor is selected as the experimental site, which is the grid area in the figure. The interval between adjacent reference points is 1m, a total of 247 reference point.

Use the wireless network card of Intel PRO/Wireless 3945ABG network connection to connect to the network, install NetStumbler software on Lenovo V450 notebook, and collect the signal strength RSS values from 27 access points AP; in the offline stage, in four different directions of all reference points Above, 100 RSS values of APs and related information of APs are continuously sampled and recorded at a sampling frequency of 2 samples per second. Store the physical coordinates and RSS values of all reference points as the data called by the positioning process to create a Radio Map. Randomly collect the RSS data of 580 points in the positioning area, the direction is random and the frequency is 2 per second, each point is sampled for 10 seconds, and the average value is taken as the unmarked data in the SDE algorithm. These data only record signal strength values without specific locations information. Together with the Radio Map, it is used as the input data of the SDE algorithm.

Embodiment 4. This embodiment is a further description of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in Embodiment 1. The specific process of the category division of step 4 random RSS data in Embodiment 1 is:

Step 41, input randomly collected unlabeled data (only signal strength value and no position information);

Step 42. Comparing the unlabeled data with the feature vectors of each sub-area obtained in step 3, that is, calculating the distance from the feature vectors of each sub-area, and distributing the random data in the sub-area closest to its feature vector, as the category it belongs to.

This embodiment can classify the categories of the randomly collected unlabeled data, and provide category information for the SDE algorithm in step five to construct the matrix of all data adjacency graphs.

Embodiment 5. This embodiment is a further description of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in Embodiment 1. In Step 5 of Embodiment 1, each sub-region in the K sub-regions is used. The SDE algorithm performs dimensionality reduction, determines the feature transformation matrix of each region, and generates a new location fingerprint database for specific instructions:

The SDE algorithm is a manifold learning algorithm based on the maximization of inter-class divergence and intra-class divergence. Before the theoretical analysis of the SDE algorithm, the input data is explained as follows: Input high-dimensional marked data and unlabeled data The main difference between the two types of data is that the former corresponds to the data collected at the reference point, which contains position information (x _ix , y _iy ) and its class label y _i ∈{1,2,…,c}. Among them, c indicates that the high-dimensional data is divided into c sub-manifolds, that is, the input high-dimensional data is divided into c categories. The unlabeled data also obtains the corresponding class information after step 4.

Step 51. Construct an adjacency graph

Construct undirected graphs G and G' according to the class label information of high-dimensional data points and their neighbor relations. Among them, the neighbor relationship is the criterion given by the KNN algorithm, that is, select the nearest K points of the data point as its neighbors, and G means that when the class label information y _i of x i and _{x j} = y _j and x _i and x _j are mutually _is the K-nearest neighbor relationship; G' _indicates that when the class label information y _i ≠ y _j of x _i and x _j is the K-nearest neighbor relationship.

Step 52. Calculate the weight matrix

According to the adjacency graph constructed in step 51, a Gaussian-like function is used to calculate the weight matrix. Its expression is shown in (1). In the formula (1), w _ij represents the weight between the neighbor points x _i and x _j , and || _xi -x _j || ² is the norm distance between the neighbor points x _i and x _j , which is calculated by matrix Norm distance, t is the weight normalization parameter.

Step 53: Determine the objective function and its solution

According to the goal of the SDE algorithm: maximize the between-class divergence and minimize the intra-class divergence. Divergence is expressed as a normed distance representing like and non-like data points. The corresponding optimization objective function can be obtained from the objective of the SDE algorithm, as shown in formula (2), the feature transformation matrix P is the optimal solution to be sought.

In the formula: Maximize means: maximize, subject to means: obey;

According to the optimization objective function given by formula (2), the following analysis is made:

Calculation Formula of Known Matrix Norm This formula is consistent with the calculation formula ||A|| ² ＝tr(AA ^T ) of the trace of the matrix, so formula (2) can be expressed as the trace of the matrix:

Formula (3) is further simplified to:

Since the calculated scalar properties and weight elements of the matrix trace are all real numbers, formula (4) can be simplified as:

J(V)＝2tr{P ^T [X(D′-W′)X ^T ]P} (5)

Similarly, formula (2) can be simplified as:

In formula (6), X is the input high-dimensional data, and W and W' are the weight matrix corresponding to G and G' respectively. D and D' are diagonal matrices, and their diagonal elements can be obtained by formula (7):

Applying the Lagrange multiplier method to formula (6), it can be obtained as shown in formula (8):

X(D'-W')X ^T P=λX(DW)X ^T P (8)

Perform generalized eigenvalue decomposition on formula (8), and obtain the eigenvalue λ=[λ ₁ ,λ ₂ ,…,λ _n ] ^T and eigenvector p=[p ₁ ,p ₂ ,…,p _n ] ^T .

Step 54. Eigendimension estimation

The eigendimension is the number of eigenvalues and their corresponding eigenvectors retained during low-dimensional embedding. The larger the eigenvalue corresponding to the eigenvector, the larger the inter-class distance corresponding to this direction, which means that the retained features are more discriminative. The eigendimension d is an important parameter of the algorithm. Whether its value estimation is accurate or not determines the amount of information contained in the low-dimensional data, thus affecting the positioning accuracy. According to the eigenvalues and eigenvectors obtained in steps 5 and 3, the eigendimension is estimated according to formula (9):

Among them, η ^* is the threshold value of information retained in the projected space, which is usually greater than 80%, that is, the ratio of the sum of the first d largest eigenvalues to the sum of all eigenvalues is not less than 80%, which can meet the requirements for the original data information. Low-dimensional embeddings.

Step 55. Calculate the embedding result

According to step 4, set the eigendimension estimation threshold, and select the eigenvectors corresponding to the d eigenvalues to form a transformation matrix P=[p ₁ ,p ₂ ,…,p _d ], then calculate the input high-dimensional according to formula (10) The data Z _i after dimensionality reduction of the data point x _i is:

Z _i =P ^T x _i (10)

The theoretical derivation of the SDE algorithm is given by formulas (2)-(8). The low-dimensional signal fingerprint data and feature transformation matrix can be obtained through the SDE algorithm, which are recorded as Radio Map ^* and P respectively.

Embodiment 6. This embodiment is a further description of the WLAN indoor positioning method of the semi-supervised SDE algorithm described in Embodiment 1. For each sub-region in the K sub-regions described in step 7 in Embodiment 1, Use the low-dimensional Radio Map ^* and feature transformation matrix obtained in step 5, respectively, and use the k-nearest neighbor position fingerprint positioning algorithm to specify the positioning of the test points:

Step 71 and Step 6 locate the test point in the sub-region, and the RSS signal received by the test point is a high-dimensional real-time signal, expressed as R _test =[r ₁ ,r ₂ ,...,r _n ]. Multiply with the feature transformation matrix P of this area (obtained in step 55) using formula (10) to calculate the signal value after dimensionality reduction

Step 72. Low-dimensional feature vectors of test points and the i-th reference point in the region's low-dimensional Radio Map ^* (obtained in step 55) The distance between can be obtained by formula (11):

Step seven three, select k reference points closest to the test point feature vector distance from small to large in the result, and calculate the position estimation coordinates of the test point by formula (12)

Complete the positioning of the test point.

Claims (5)

1. The WLAN indoor positioning method based on the semi-supervised SDE algorithm is realized by the following steps: Step 1. Arranging m access points AP for the indoor environment, ensuring that any point in the indoor environment is covered by signals sent by two or more wireless access points AP; m is a positive integer; Step 2. Set reference points evenly in the indoor environment, choose a reference point as the origin to establish a rectangular coordinate system, obtain the coordinate positions of each reference point in the rectangular coordinate system, and use the signal receiver to collect and collect the coordinates of each reference point on each reference point. Record the received signal strength RSS value k times from each AP, and perform data processing; k is a positive integer; Step 3, divide the indoor positioning environment into Q sub-areas according to the K-means clustering algorithm, and mark the respective category information for the reference points of each sub-area; Step 4: collect random unlabeled RSS data, compare it with the feature vectors of each sub-region obtained in step 3, that is, calculate the distance from the feature vectors of each sub-region, and divide the random data category into the nearest feature vector within the sub-region; Step 5, using the SDE algorithm for each sub-region in the K sub-regions to obtain a feature transformation matrix; The input parameter of the SDE algorithm, that is, the value of the intrinsic dimension, estimates the RadioMap partition data through the existing intrinsic dimension estimation algorithm, gives the estimated value of the intrinsic dimension of each area data, and determines each area The feature transformation matrix of , and generate a dimensionally reduced location fingerprint database Radio Map ^* ; Step six, compare the signal strength RSS value obtained by the point to be tested with the feature vectors of each sub-area obtained in step three, that is, to obtain the distance between the feature vector of the test point and the feature vector of each sub-area, and locate the test point at In the subregion closest to its feature vector; Step 7. In the located sub-region, use the feature transformation matrix obtained in step 5 to reduce the dimensionality of the RSS value of the point to be measured to obtain a low-dimensional RSS ^* , and match it with the fingerprint database Radio Map ^* , using the K nearest neighbor position Fingerprint location algorithm carries out accurate location to test point; It is characterized in that, utilize signal receiver to collect and record the received signal strength RSS value k times from each AP on each reference point described in step 2, and carry out data processing The specific steps are: Step 21. Obtain a k×m order matrix for each reference point, the i-th row and j-th column of the matrix represent the RSS value received from the j-th AP in the i-th collection; k, m, i, j are positive integers; Step 22: Add all the elements in the k×m order matrix column vector obtained by each reference point to get a value, and then divide this value by k, then each reference point gets a 1×m vector , for each reference point, this vector is called the feature vector of the reference point, and the jth element in the vector is used as the jth feature of the reference point; if the RSS value of some APs on a reference point cannot be detected , then assign it as the minimum signal value that can be received in this environment -100dBm, so the range of the received signal strength RSS value v at any reference point is -100dBm≤v≤0dBm; this group of vectors is used to realize the aggregation of step 3 class partition. 2. the WLAN indoor positioning method of semi-supervised SDE algorithm according to claim 1, it is characterized in that the concrete steps that the indoor positioning environment is divided into Q sub-regions according to the K-means clustering algorithm described in step 3 are: Step 31, input the eigenvectors and the number of subregions Q of all reference points measured in step 22; Step 32, randomly select the RSS of K reference points from the data obtained in step 22, that is: the eigenvector values of each reference point are used as the cluster centers of K subregions; Step 33: Calculate the Euclidean distance between each reference point and the feature vectors of the K cluster centers, and assign each reference point to the sub-region with the smallest Euclidean distance; Steps three and four, calculating the mean value of the RSS values of each reference point in each sub-region to obtain a new cluster center; Steps 3 and 5, repeat steps 3 and 3 and 4 until the center of each sub-region does not change; Step 36: Obtain K subregions and the corresponding clustering center vectors of each subregion, namely: a 1×m vector, which is called the feature vector of this subregion, and the jth element of this vector represents this subregion The jth feature of is also the RSS mean value obtained from the jth AP in this sub-region. 3. the WLAN indoor location method of semi-supervised SDE algorithm according to claim 1, it is characterized in that the concrete process of the category division of step 4 random RSS data is: Step 41, input randomly collected unlabeled data, the unlabeled data only has signal strength value but no location information; Step 42. Comparing the unlabeled data with the feature vectors of each sub-area obtained in step 3, that is, calculating the distance from the feature vectors of each sub-area, and distributing the random data in the sub-area closest to its feature vector, as the category it belongs to. 4. the WLAN indoor positioning method of semi-supervised SDE algorithm according to claim 1, it is characterized in that the described in step 5 adopts SDE algorithm to carry out dimensionality reduction to each sub-region in K sub-regions, determines the feature transformation of each region Matrix, and the specific method of generating a new location fingerprint database is: Step 51. Construct an adjacency graph: Construct undirected graphs G and G' according to the class label information of high-dimensional data points and their neighbor relationships; where the neighbor relationship is the criterion given by the KNN algorithm, that is, select the nearest K points of the data point as its neighbors, and G represents when When the class label information y _i of xi and _{x j} = y _j and xi _and x _j are K neighbors; G' indicates that when the class label information _{y i ≠} y _j of xi and x _j and _xi x _{and j} are K-nearest neighbors; Step 52. Calculate the weight matrix: According to the adjacency graph constructed in step 51, the Gaussian-like function is used to calculate the weight matrix, and its expression is shown in (1): Among them: w _ij represents the weight between the neighbor points x _i and x _j , || _xi -x _j || ² is the norm distance between the neighbor points x _i and x _j , and the norm distance is calculated by matrix , t is the weight normalization parameter; Step five and three, determine the objective function and its solution: According to the goal of the SDE algorithm: maximize the inter-class scatter while minimizing the intra-class scatter; the scatter is represented by the norm distance representing similar and non-like data points; The corresponding optimization objective function is obtained from the goal of the SDE algorithm, as shown in formula (2), the feature transformation matrix P is the optimal solution to be found: According to the optimization objective function given by formula (2), it can be known that: Calculation Formula of Known Matrix Norm This formula is consistent with the calculation formula ||A|| ² ＝tr(AA ^T ) of the trace of the matrix, so the formula (2) is expressed as the trace of the matrix: Formula (3) is further simplified to: Since the calculated scalar properties and weight elements of the matrix trace are all real numbers, formula (4) is simplified as: J(V)＝2tr{P ^T [X(D′-W′)X ^T ]P} (5) Similarly, formula (2) can be simplified as: In formula (6), X is the input high-dimensional data, W and W' are the weight matrices corresponding to G and G' respectively; D and D' are diagonal matrices, and their diagonal elements are obtained by formula (7): Applying the Lagrangian multiplier method to formula (6), it can be obtained as shown in formula (8): X(D'-W')X ^T P=λX(DW)X ^T P (8) Carry out generalized eigenvalue decomposition on formula (8), and obtain the eigenvalue λ=[λ ₁ ,λ ₂ ,...,λ _n ] ^T and eigenvector p=[p ₁ ,p ₂ ,. ..,p _n ] ^T ; Step 54. Eigendimension estimation: According to the eigenvalues and eigenvectors obtained in steps 5 and 3, the eigendimension is estimated according to formula (9): Among them: η ^* is the threshold value of the information retained in the projection space, usually the value is greater than 80%, that is, the ratio of the sum of the first d largest eigenvalues to the sum of all eigenvalues is not less than 80%, that is, it satisfies the requirement for better original data information low-dimensional embedding; Step 55. Calculate the embedding result: Set the eigendimension estimation threshold according to step 54, select the eigenvectors corresponding to the d eigenvalues to form a transformation matrix P=[p ₁ ,p ₂ ,...,p _d ], and then calculate according to formula (10) Input the high-dimensional data point x _i and the dimensionally reduced data Z _i is: Z _i =P ^T x _i (10) The low-dimensional signal fingerprint data and feature transformation matrix are obtained through the SDE algorithm, which are recorded as Radio Map ^* and P respectively. 5. the WLAN indoor positioning method of semi-supervised SDE algorithm according to claim 4, it is characterized in that to each sub-area in K sub-areas described in step 7, utilize the low-dimension Radio Map ^* that step 5 obtains respectively and Feature transformation matrix, using the k nearest neighbor position fingerprint positioning algorithm to locate the test point, the specific method is as follows: Step 71 and Step 6 locate the test point in the sub-area, the RSS signal received by the test point is a high-dimensional real-time signal, expressed as R _test = [r ₁ , r ₂ ,...r _n ]; The feature transformation matrix P is multiplied by formula (10) to calculate the signal value after dimensionality reduction Step 72. Low-dimensional feature vectors of test points and the i-th reference point in the low-dimensional Radio Map ^* of the area The distance between is obtained by formula (11): Step seven three, select k reference points closest to the test point feature vector distance from small to large in the result, and calculate the position estimation coordinates of the test point by formula (12) Complete the positioning of the test point.