CN108627798A - WLAN indoor positioning algorithms based on linear discriminant analysis and gradient boosted tree - Google Patents

Abstract

The invention is a WLAN indoor positioning algorithm based on linear discriminant analysis and gradient boosting tree. In order to reduce the impact of the time-varying characteristics of received signal strength (RSSI) on positioning accuracy in indoor WLAN environments, LDA is proposed to extract the positioning features of the original RSSI signal, and the prediction of position coordinates is realized by building a GBDT model. This method is mainly divided into 4 processes. 1) Collect the RSSI signal value of the AP at the reference point, and form a fingerprint data with the position coordinates of the reference point, and store it in the fingerprint database; 2) Solve the intra-class scatter matrix and inter-class scatter matrix of the fingerprint data to obtain the projection matrix to realize the extraction of RSSI signal positioning features; 3) use the forward distribution algorithm and the additive model to iteratively generate the GBDT positioning model; 4) in the online phase, collect the RSSI signal values of APs around the test point, use LDA for feature extraction, and Input the GBDT positioning model to calculate the position coordinates.

Description

WLAN Indoor Localization Algorithm Based on Linear Discriminant Analysis and Gradient Boosting Tree

Technical field:

The invention belongs to the field of WLAN indoor positioning. It is an indoor positioning method that uses linear discriminant analysis (LDA) to extract positioning features from fingerprint data in the offline stage of WLAN indoor positioning, and constructs a positioning model through gradient boosting tree (GBDT). This method can effectively improve the WLAN indoor positioning accuracy.

Background technique:

In recent years, with the breakthrough of smart devices and Internet technology, more and more scenarios that need to use location services have been derived, and people's demand for location services has also expanded from outdoor driving navigation to indoor positioning. However, the Global Positioning System (GPS), which is commonly used outdoors, cannot work in an indoor environment because building walls block signals. In order to enable users to obtain accurate location information indoors, researchers at home and abroad have developed a variety of indoor positioning systems based on different working principles. Among them, the system based on WLAN technology is the most common. Since WLAN has become one of the infrastructures in buildings, the positioning system based on WLAN does not need to build dedicated positioning hardware equipment, which reduces the cost of the system and the difficulty of implementation. WLAN indoor positioning is divided into offline phase and online phase.

In the offline stage, the received signal strength value (RSSI) of the access point (AP) is collected at the reference point, and the position coordinates of the reference point form a fingerprint information, which is stored in the fingerprint database. However, referring to FIG. 1 , due to influences such as multipath propagation and occlusion, the RSSI signal exhibits time-varying characteristics. Utilizing raw fingerprint data will seriously reduce the prediction accuracy of localization algorithms. Algorithms for predicting the user's real-time location can be divided into the nearest neighbor method (NN), the maximum likelihood method and the artificial neural network method. The precision of NN is too low, the real-time performance of the maximum likelihood method is poor, and the generalization ability of the artificial neural network method is insufficient. Therefore, the present invention proposes a WLAN indoor positioning algorithm based on linear discriminant analysis and gradient boosting tree (LDA-GBDT).

Invention content:

Aiming at the problem that the time-varying characteristics of RSSI signal reduce the positioning accuracy, the present invention proposes to use LDA to extract the positioning features in the RSSI signal, and realize the prediction of position coordinates by constructing a GBDT positioning model.

In order to achieve the above object, the present invention adopts the following technical solutions: in the offline stage, first collect the RSSI signal value of the AP at each reference point, and form fingerprint data together with the corresponding position coordinates, then use LDA to extract the positioning features of the original RSSI signal, In order to eliminate the time-varying characteristics of the RSSI signal and the influence of noise and the like. Finally, the original fingerprint database is updated, and the GBDT positioning model is generated iteratively through the forward distribution algorithm and the additive model. In the online stage, collect the RSSI signal value of the AP around the test point, use LDA to extract the positioning feature, and then input it into the GBDT positioning model to predict the position coordinates. The schematic diagram of the positioning method of the present invention is shown in Figure 2.

A kind of WLAN indoor positioning algorithm based on LDA-GBDT, comprises the following steps successively:

(1) Select a reference point evenly in the area to be located, collect the RSSI signal value of the access point (AP) on the reference point, and form an ordered vector with the coordinates of the reference point, which is the location fingerprint data of the reference point.

(2) Using LDA to extract the positioning features in the original RSSI signal, the steps are as follows:

1) Construct the objective function;

2) According to the coordinates of the reference point, the location fingerprint data is divided into k categories, and the inter-class scatter matrix S _b of each type of fingerprint data is obtained. The calculation formula is as follows:

Among them, Z _j represents the number of the jth (j=1, 2, ..., k) type fingerprint data, μ _j represents the j (j = 1, 2, ..., the mean vector of the k type fingerprint data , μ represents the mean vector of all fingerprint data.

3) Calculate the intra-class scatter matrix S _ω of various fingerprint data according to the following formula;

Among them, η _j is the set of the jth (j=1, 2, ..., k) class fingerprint data, and γ represents the jth (j=1, 2, ..., k) class fingerprint data set in the fingerprint data.

4) Calculate the eigenvalues and eigenvectors of the matrix S _ω ^-1 S _b according to the calculation results of 2) and 3), and obtain the projection matrix.

5) Use the projection matrix obtained in 4) to calculate the new fingerprint data set after extracting the positioning features through LDA.

(3) Using the new fingerprint data set obtained in (2), according to the forward distribution algorithm, the negative gradient value of the loss function is used as the approximate value of the residual in the boosting tree algorithm of the regression problem, and a classification regression tree is fitted.

(4) Linearly combine the classification and regression trees generated in (3) using an additive model.

(5) Repeat steps (3) and (4) to establish a GBDT positioning model.

(6) Collect the RSSI signal of the AP at the test point, use LDA to extract its positioning features, and then input it into the GBDT positioning model established in (5) to calculate the coordinates of the test point.

This algorithm aims to use LDA to extract the positioning features in the original RSSI signal, reduce the impact of its time-varying characteristics on the positioning accuracy, and predict the position coordinates by constructing a GBDT positioning model. Compared with the prior art, the present invention has the following advantages:

(1) Extracting the positioning features of the original RSSI signal can effectively filter out redundant signals and noise contained therein;

(2) The GBDT positioning model can reduce the impact of outliers on positioning accuracy by constructing an accurate loss function;

(3) In the case of the same positioning error, the algorithm proposed by the present invention uses fewer APs.

Description of drawings:

Figure 1 is a diagram of the source of the time-varying error of the RSSI signal;

FIG. 2 is a schematic diagram of the indoor positioning algorithm;

Fig. 3 is the algorithm flowchart of the present invention;

Figure 4 is a scene diagram of indoor positioning.

Detailed ways:

Refer to FIG. 3 for the flow chart of the method of the present invention. The implementation of the offline stage is to collect the RSSI signal value of the AP on the reference point through the mobile device, and form a set of ordered vectors with the coordinates of the position, which is the location fingerprint data of the reference point. Use LDA to reorganize the positioning information of the original RSSI signal, filter out redundant positioning features and noise, and extract the most discriminative positioning features, and then according to the forward distribution algorithm, use the negative gradient value of the loss function as a regression problem in the boosting tree algorithm The approximate value of the residual, fit a classification and regression tree, and finally use the additive model to linearly combine the generated classification and regression trees to generate a GBDT positioning model. In the online stage, the RSSI signal value of the AP on the test point is collected, and the positioning feature is extracted by LDA, which is input into the GBDT positioning model to calculate the coordinates of the test point. The specific implementation steps are as follows:

(1) Referring to Fig. 4, it is a floor plan of the indoor scene to be positioned, and the whole area is 221 square meters in total. The uniformly selected reference points in this area are represented by light-colored dots, and the randomly selected test points are represented by dark-colored squares.

(2) Specify the coordinate origin of the area to be positioned, and measure the position coordinates of the reference point and the test point selected in (1).

(3) Collect the RSSI signal value of the AP at the reference point, and form an ordered vector together with the position coordinates of the reference point measured in (2), which is the location fingerprint data of the reference point, and store it in the fingerprint database. Then LDA is used to extract the localization features of the original RSSI signal.

The "fingerprint database" mentioned herein is a database for storing reference point fingerprint data.

The specific operation steps of "LDA extracting the positioning feature of the original RSSI signal" described therein are:

1) Input the original location fingerprint dataset

Wherein, N is the total number of reference points, γ _i =(rss ₁ , rss ₂ , ..., rss _n ) represents the RSSI values of n APs collected at the i-th reference point, and n represents the total number of APs. li represents the coordinates of the i-th reference point.

2) Construct the objective function.

3) The fingerprint data is divided into k classes according to the coordinates of the reference points, and the inter-class scatter matrix s _b is calculated; wherein, the "inter-class scatter matrix" is expressed as k represents the total number of categories of fingerprint data, Z _j represents the number of fingerprint data of the jth (j=1, 2, ..., k) class, μ _j represents the j (j=1, 2, ..., k ) is the mean vector of fingerprint data, and μ represents the mean vector of all fingerprint data.

4) Calculate the intra-class scatter matrix S _ω ;

Among them, the "intra-class scatter matrix" is expressed as k represents the total number of categories of fingerprint data, η _j is the collection of jth (j=1, 2, ..., k) type fingerprint data, γ represents fingerprint data, μ _j represents the jth (j=1, 2, . . . . , k) mean vector of class fingerprint data.

5) According to the results of 3) and 4), calculate the eigenvalues and eigenvectors of the matrix S _ω ^-1 S _b .

6) Select the first θ eigenvalues of the matrix S _ω ^-1 S _b , and stretch the corresponding eigenvectors into a projection matrix Ψ;

Among them, θ represents the dimension of the matrix Ψ, and the value range is [1, n], that is, the dimension of the fingerprint data after extracting the positioning features. n represents the total number of APs.

7) According to Calculate the new fingerprint data set after the location feature extraction;

Wherein, the "new fingerprint data set" can be expressed as N is the total number of reference points, Indicates the θ-dimension position fingerprint data at the i-th reference point after location feature extraction, r _ss′ represents the new RSSI signal value after location feature extraction, γ _i represents the original fingerprint data at the i-th reference point, l _i represents the The coordinates of i reference points.

8) Repeat the above 7 steps to perform LDA positioning feature extraction on the original RSSI signal according to another dimension of position coordinates.

(3) Using the new fingerprint data set D′ obtained in (2), initialize the first classification regression tree

Among them, N is the total number of reference points. L is a loss function, and the present invention adopts the Huber loss function, which can significantly reduce the influence of abnormal values in the fingerprint data set D' on the positioning result. l _i represents the coordinates of the i-th reference point. τ represents the output value of the leaf node of the classification regression tree.

(4) When the mth (m=1, 2, ..., M) classification regression tree is generated, the negative gradient value α _mi of the loss function is used as the approximate value of the residual in the regression problem boosting tree algorithm, and the fitting A classification regression tree.

Among them, α _mi represents the loss of the fingerprint data of the i (i=1, 2, ..., N) reference point when the m (m = 1, 2, ..., M) classification and regression tree is generated The negative gradient value of the function. M is the total number of generated classification and regression trees.

The specific steps of "fitting a classification and regression tree" described therein are:

1) set is the input space;

Among them, N is the total number of reference points.

2) Traverse the segmentation feature h (h=1, 2, ..., θ), and scan the corresponding segmentation point s (s = rss' ₁ , rss' ₂ , ... , rss′ _θ ), recursively divide the input space P into two regions;

3) When the mean square error of the respective sets of the two subfields in 2) is the smallest, and the sum of their mean square errors is the smallest, the corresponding segmentation feature and eigenvalue division point are the optimal segmentation variables and segmentation points;

4) Divide the input space P into two sub-regions with the optimal segmentation variable and segmentation point (h, s) selected in 3), and use linear search to calculate the output value of each sub-region;

5) Repeat the operations of 2), 3) and 4) to recursively divide the input space P into β ₁ , β ₂ , . . . , β _R , and these R sub-regions are mutually disjoint. The output value of each sub-region of the m-th classification and regression tree is represented by τ _mr ;

Wherein, r (r=1, 2, . . . , R) represents the serial number of the sub-region.

6) According to the output value τ _mr of each sub-region, the mth classification and regression tree is expressed as

(5) Multiply the regularization coefficient λ before each classification and regression tree, and its value range is (0, 1] to avoid overfitting the training sample data.

(6) Linearly add the regularized classification and regression trees in (5) using an additive model. Wherein, the "additive model" is F _m =F _m-1 +λ _m T _m . λ _m represents the regularization coefficient of the mth (m=1, 2, . . . , M) classification regression tree.

(7) Repeat (4) to (6) to generate the GBDT positioning model F _M .

Wherein, the "GBDT positioning model" can be expressed as M represents the total number of classification and regression trees generated.

(8) In the online stage, collect the RSSI signal value of the AP on the test point, use LDA to extract the positioning feature, and input it into the GBDT positioning model generated in (7), to obtain the specific coordinates of the test point.

Comparing the test point coordinates calculated in (8) with the real value of the test point coordinates measured in (2), the average positioning error is 1.51m. Therefore, the algorithm according to the present invention can obtain a relatively high accuracy in the WLAN indoor environment. High positioning accuracy.

Claims (1)

1. a kind of WLAN indoor positioning algorithm based on proposed LDA-GBDT, is characterized in that, comprises the following steps: (1) uniformly select a reference point in the area to be positioned, collect the RSSI signal value of the access point AP on the reference point, and form an ordered vector with the coordinates of the reference point, which is the position fingerprint data of the reference point; (2) Using LDA to extract the positioning features in the original RSSI signal, the steps are as follows: 1) Construct the objective function; 2) According to the coordinates of the reference point, the location fingerprint data is divided into k categories, and the inter-class scatter matrix S _b of each type of fingerprint data is obtained. The calculation formula is as follows: Among them, Z _j represents the number of jth (j=1, 2, ..., k) type fingerprint data, μ _j represents the mean value of j (j=1, 2, ..., k) type fingerprint data Vector, μ represents the mean vector of all fingerprint data; 3) Calculate the intra-class scatter matrix S _ω of various fingerprint data according to the following formula; Among them, η _j is the set of the jth (j=1, 2, ..., k) class fingerprint data, and γ represents the jth (j=1, 2, ..., k) class fingerprint data set in the fingerprint data; 4) Calculate the eigenvalues and eigenvectors of the matrix S _ω ^-1 S _b according to 2) and 3) to obtain the projection matrix; 5) Utilize the projection matrix obtained in 4), and calculate the new fingerprint data set after extracting the location feature through LDA; (3) Use the new fingerprint data set obtained in (2), according to the forward distribution algorithm, use the negative gradient value of the loss function as the approximate value of the residual in the regression problem boosting tree algorithm, and fit a classification regression tree; (4) Using an additive model to linearly combine the classification regression trees generated in (3); (5) Repeat steps (3) and (4) to set up the GBDT positioning model; (6) Collect the RSSI signal of the AP at the test point, use LDA to extract its positioning features, and then input it into the GBDT positioning model established in (5) to calculate the coordinates of the test point.