CN106093852A - A kind of method improving WiFi fingerprint location precision and efficiency - Google Patents

Abstract

The invention relates to a method for improving the accuracy and efficiency of WiFi fingerprint positioning. In the offline training stage, a fingerprint database for online positioning is constructed, and the K-means clustering algorithm is used to classify the fingerprint database. The signal strength value of the sampling point is processed by data smoothing; in the online positioning stage, the K nearest neighbor algorithm is used to find the K fingerprints closest to the measured fingerprint, and the position of the sampling point corresponding to the average value of the K fingerprints is the estimated position of the point to be measured. The invention can improve positioning accuracy and positioning efficiency.

Description

A Method of Improving the Accuracy and Efficiency of WiFi Fingerprint Positioning

technical field

The invention relates to the field of WiFi-based indoor positioning technology, in particular to a method for improving the accuracy and efficiency of WiFi fingerprint positioning.

Background technique

Indoor positioning system is one of the current hot spots in the field of information technology. With the rapid development of the Internet of Things and wireless communication technology, location-based services have shown broad application prospects in the fields of medical care, public safety, and industrial production.

The Global Positioning System (Global Positioning System, GPS) is a widely used positioning technology at the present stage, and it is widely used in various location services. However, the GPS positioning system cannot locate indoors, because this positioning method requires more than three satellites to provide positioning information. Generally, it is only suitable for open and unsheltered outdoor environments. In a relatively closed indoor environment, the GPS positioning system cannot The information required for positioning is obtained through satellites. It can be seen that the GPS positioning system is only suitable for outdoor positioning, but cannot meet the positioning requirements in a variety of indoor environments. At this time, the WiFi positioning technology based on the wireless local area network is rapidly heating up, and the most widely used one is the WiFi fingerprint positioning technology. The WiFi fingerprint positioning technology is a technology with high accuracy and practicability in the wireless positioning technology, and it does not require additional hardware. The facilities are cheap, so they are very practical.

WiFi fingerprint positioning is derived from database positioning technology. It needs to create a fingerprint database in advance. The offline signal strength and location coordinates are stored in the fingerprint database. Since the multipath propagation of the signal is dependent on the environment, the multipath characteristics of the channel in different locations are also different, showing a very strong particularity. The location fingerprint positioning technology effectively utilizes the multipath effect and combines multipath features with location information. Since the multipath effect of the channel is unique at the same location point, the multipath structure can be used as a fingerprint in the database. The point to be tested obtains the wireless signal sent by the access point in the same environment, matches the received wireless signal strength with the fingerprint in the database, and finds the most similar result for positioning.

The WiFi fingerprint positioning technology is specifically divided into two stages in the positioning implementation: the offline training stage and the online positioning stage.

Offline training phase: first deploy wireless AP in the positioning environment and determine the location of the sampling point so that each sampling point can receive the signal transmitted by the wireless AP. Place a signal receiving device (mobile device) at each sampling point, record the signal strength (RSSI value) received from each AP, and store these signal strength values and coordinate information in the fingerprint database, thus uniquely identifying this sampling point . After all sampling points are sampled, a fingerprint database of complete signal strength information and corresponding location relationship, that is, a fingerprint map, is constructed.

Online positioning stage: measure and obtain the signal strength information of each AP in real time at the point to be tested, and match it with the information in the location fingerprint database, and perform matching analysis between the measured data and the pre-stored data, so as to estimate the location of the terminal to be tested.

However, the traditional WiFi fingerprint positioning algorithm has low positioning accuracy and low positioning efficiency.

Contents of the invention

The technical problem to be solved by the present invention is to provide a method for improving the positioning accuracy and efficiency of WiFi fingerprints, which can improve the positioning accuracy and positioning efficiency.

The technical scheme adopted by the present invention to solve the technical problem is: provide a method for improving the accuracy and efficiency of WiFi fingerprint positioning, construct a fingerprint database for online positioning in the offline training stage, and use K-means aggregation in the fingerprint database In the fingerprint database, the signal strength values of the sampling points are processed by data smoothing; in the online positioning stage, the K nearest neighbor algorithm is used to find the K fingerprints closest to the measured fingerprints, and the average value of the K fingerprints corresponds to the sampling point The position of is the estimated position of the point to be measured.

The fingerprint database constructed for online positioning specifically includes the following steps:

Select an indoor environment as the positioning area, in this positioning area, deploy n wireless access points and select L sampling points, and record the position coordinates of each sampling point;

At each sampling point, the mobile terminal with WiFi signal detection function is used to detect the signal strength, and the RSSI value of each wireless access point is collected multiple times, and then the collected data is smoothed to obtain the smoothed mean value of the sampling point. Fingerprint: traverse L sampling points, get L fingerprints, and store them in the fingerprint database.

Described adopting K-means clustering algorithm to classify in the fingerprint database specifically comprises the following steps:

Carry out K-means clustering on the fingerprint database, using Euclidean distance as the evaluation criterion of similarity, the fingerprints with smaller distances are gathered in one subclass, and the fingerprints with larger distances are far away from each other;

Execute the previous step several times until the clustering ends, and the fingerprint database becomes a fingerprint sample space with K subclasses.

The K-means clustering algorithm is specifically:

Input L fingerprints and the number of clusters K, where K≤L; randomly select K fingerprints from the L fingerprints as the initial cluster center;

For the remaining fingerprints, calculate the distance from each fingerprint to each cluster center, and after finding the minimum distance, divide the fingerprints into the corresponding clusters, obtain new clustering results, and complete the fingerprint assignment;

Calculate the new cluster center and compare it with the last cluster center. If the two are the same, the clustering ends. Otherwise, update the cluster center and return to the previous step to perform clustering.

The online positioning stage specifically includes the following steps:

Match the measured fingerprint with the fingerprint database after training, calculate the distance between the measured fingerprint and each cluster center, and find the cluster corresponding to the minimum distance;

Calculate the distance between the measured fingerprint and each fingerprint in the cluster corresponding to the minimum distance;

Arrange according to the obtained distance values in ascending order, keep the smallest K distances, and select the fingerprints corresponding to the K distances as reference fingerprints, and the corresponding sampling point coordinates as reference coordinates;

Calculate the mean value of these K reference coordinates as the estimated position of the measured fingerprint.

Beneficial effect

Due to the adoption of the above-mentioned technical solution, the present invention has the following advantages and positive effects compared with the prior art: the present invention adopts the mean value smoothing method to reduce the volatility of the fingerprint sequence in the offline stage, and adopts K-means clustering The algorithm classifies and processes WiFi fingerprints. In the online positioning stage, a K-nearest neighbor algorithm based on K-means clustering is proposed to improve the positioning efficiency.

Description of drawings

Fig. 1 is the training flowchart of fingerprint database among the present invention;

Fig. 2 is a flow chart of K-means clustering among the present invention;

Fig. 3 is a flowchart of the K-nearest neighbor algorithm based on K-means clustering in the present invention.

detailed description

Below in conjunction with specific embodiment, further illustrate the present invention. It should be understood that these examples are only used to illustrate the present invention and are not intended to limit the scope of the present invention. In addition, it should be understood that after reading the teachings of the present invention, those skilled in the art can make various changes or modifications to the present invention, and these equivalent forms also fall within the scope defined by the appended claims of the present application.

The embodiment of the present invention relates to a method for improving the accuracy and efficiency of WiFi fingerprint positioning. In the offline training phase, a fingerprint database for online positioning is constructed, and the K-means clustering algorithm is used to classify the fingerprint database. The signal strength values of the sampling points in the database are processed by data smoothing; in the online positioning stage, the K nearest neighbor algorithm is used to find the K fingerprints closest to the measured fingerprints, and the position of the sampling point corresponding to the average value of the K fingerprints is the location of the point to be tested. Estimated location.

offline training phase

In the offline training phase, first deploy wireless access points (APs) in the positioning environment and determine the location of the sampling points so that each sampling point can receive the signal transmitted by the wireless AP. Then place a signal receiving device (mobile device) at each sampling point, record the signal strength (RSSI value) received from each AP, and finally store these signal strength values and coordinate information in the fingerprint database, thus uniquely identifying this AP. Sampling points, the data of all sampling points are stored in the database to form a fingerprint database for online positioning.

Ideally, the received signal strength RSSI value will decrease regularly with the increase of the propagation distance, but in practical applications, the wireless signal is affected by environmental factors during the propagation process, such as indoor signal multipath, reflection, The absorption of walls and doors, etc., causes the signal to have an inconsistent attenuation relationship, so that the RSSI value of each wireless AP collected at any sampling point is not unique, and there is a large fluctuation, which affects the accuracy of the fingerprint database in the offline training phase. Therefore, it is necessary to take some effective and feasible measures to minimize the fluctuation of the RSSI value, so as to reduce the data error of the fingerprint database and improve the positioning accuracy during online positioning.

For any sampling point, when recording the RSSI value of each wireless AP, it will be found that the RSSI value of any wireless AP is not unique, and the RSSI values received in different time periods are different, and sometimes the difference is very large. Big. Therefore, it is not possible to use a certain RSSI measurement value as a standard and store it in the database as the fingerprint data of a certain sampling point, which will cause a large positioning error. , collect the RSSI value of each wireless AP multiple times, and then smooth the collected data, thereby reducing the fluctuation of the RSSI value and improving the positioning accuracy. There are many methods for signal smoothing, such as mean method, median method, mode method, etc. In this embodiment, the mean value smoothing method is used for data smoothing processing.

The mean smoothing method pre-sets a standard deviation threshold X _D , and at any sampling point, calculates the standard deviation SD of the multiple RSSI values collected for each wireless AP _. The larger the standard deviation _SD , the greater the RSSI value is. The more obvious the fluctuation, that is, the greater the interference by the environment, if the average value of the data at this time is used as the RSSI value of a wireless AP at the sampling point and stored in the fingerprint database, the error will be large. The mean smoothing method first divides the data into two parts, as shown in formulas (1) and (2), where S ₁ represents the mean value of the part of data that is less than the mean value S _av of all data, and S ₂ represents the mean value of the part that is greater than the mean value S _av of all data The average value of that part of the data; secondly, use a to measure the proportion of S ₁ and S ₂ in the received signal strength RSSI, as shown in formula (4), when S _D > X _D , S ₁ accounts for more Large proportion, that is, the data of the stronger part of the signal accounts for a larger proportion in the collected data, and vice versa; finally, the RSSI value of a certain wireless AP at any sampling point can be calculated by using formula (3) and stored in fingerprint database. This value is calculated by S ₁ and S ₂ according to different proportions. S ₁ accounts for a larger proportion in places where the signal is stronger, and S ₂ takes a larger proportion in places where the signal is weaker. Therefore, this method can effectively reduce the fluctuation of the RSSI value , to improve the data accuracy of the fingerprint database in the offline training phase.

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; 1</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; 1</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The RSSI value after the mean smoothing method is:

RSSI＝(1-a)*S ₁ +a*S ₂ (3)

in:

$\begin{array}{c}\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 0.5</span>}<span\; class="notranslate">\; *</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}\\ \mathrm{<span\; class="notranslate">\; 0.5</span>}<span\; class="notranslate">\; *</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}\end{array}\right.\\ \mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}\end{array}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

K-means clustering can also be called K-means clustering. The K-means clustering method is a widely used clustering algorithm suitable for various data types. The algorithm is simple and fast to implement. K-means clustering is a typical distance-based clustering algorithm, which uses distance as a measure of similarity. The basic idea of the algorithm is to divide the existing samples into K sub-categories according to the similarity between them, and compare the similarity with each other. Large samples are clustered together, and samples with less similarity are far away from each other. The K-means clustering algorithm can efficiently classify, so that the entire WiFi fingerprint database is divided into different sub-categories, thereby reducing the location fingerprint search range in the online positioning stage and improving positioning efficiency.

The first stage of the WiFi fingerprint algorithm is to build a WiFi fingerprint database in an offline state. In the WiFi environment, assuming that in a specific indoor area, n WiFi signal strengths, that is, RSSI values, can be detected, L sampling points are selected in this positioning area, and the location information of the sampling points is known, using a two-dimensional space Coordinates (x, y) represent. The n RSSI values (rssi ¹ , rssi ² ,...rssi ⁿ ) can be collected at each sampling point, and the array is used as the fingerprint of this sampling point, and each fingerprint corresponds to the position of the sampling point one by one, forming a one-to-one mapping relationship. Then this fingerprint database can be expressed as formula (5).

$\mathrm{<span\; class="notranslate">\; L</span>}\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccc}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\\ {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}& {\mathrm{<span\; class="notranslate">\; rss</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& & <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; ...</span>}& <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& & <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\end{array}\right]<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

Among them, LR contains location information and RSSI sequence, then the fingerprint information can be separately expressed as location set L and fingerprint set R, as shown in formula (6) and formula (7).

$\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{cc}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}\\ {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}\end{array}\right]<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccc}{\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\\ {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& & <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& \mathrm{<span\; class="notranslate">\; ...</span>}& <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>& <span\; class="notranslate">\; .</span>& & <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; ...</span>}& {\mathrm{<span\; class="notranslate">\; rssi</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\end{array}\right]<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

When training the WiFi fingerprint of the fingerprint database in the offline training phase, the fingerprint data needs to be preprocessed first, that is, the above-mentioned mean smoothing method is used to smooth the fingerprint set R, and the obtained After that, the K-means clustering algorithm is used to analyze the fingerprint collection Carry out classification processing. The process of training the fingerprint database is shown in Figure 1.

The specific training steps are the following four steps:

Step1. Select an indoor environment as the positioning area. In this positioning area, deploy n wireless APs and select L sampling points, and record the position coordinates of each sampling point.

Step2. At each sampling point, use a mobile terminal with WiFi signal detection function to perform signal strength detection, collect the RSSI value of each wireless AP multiple times, and then smooth the collected data to obtain the smoothed mean value of this sampling point fingerprint 1≤i≤L; traverse L sampling points, get L fingerprints, and store them in the fingerprint database.

Step3. Carry out K-means clustering on the fingerprint database, and use Euclidean distance as the evaluation criterion for similarity. Fingerprints with smaller distances are gathered in one subclass, and fingerprints with larger distances are far away from each other.

Step4. Execute Step3 multiple times until the clustering ends, and the fingerprint database becomes a fingerprint sample space with K subclasses. Among them, the K-means clustering method mentioned in Step3, its execution process is divided into the following five steps:

1. Enter L fingerprints and the number of clusters K, (K≤L); randomly select K fingerprints from L fingerprints as the initial cluster center C=(C ₁ , C ₂ ,...C _K ).

2. For the remaining (LK) fingerprints, calculate the distance Dis tan ce={d _ij |i=1,2,...,(LK) from each fingerprint to each cluster center; j=1,2, ...,K}, where d _ij represents the distance from the i-th fingerprint to the j-th cluster center, find min(Dis tan ce), divide the i-th fingerprint into the j-th cluster, and get a new cluster result.

3. Repeat the second step to complete the assignment of the remaining fingerprints to form K clusters G ₁ , G ₂ ,...,G _j ,...G _K , each class G _j contains its cluster center and belongs to the cluster The fingerprint members of the class, the total number of fingerprints is n _j .

4. According to the formula Calculate new cluster centers, where _{rssi i} represents the ith RSSI value in class Gj. Calculate the class center of each class to get the new cluster center

5. If C ^* = C, that is, the two adjacent cluster centers are the same, that is, the classification tends to be stable, and the clustering ends. The current G ₁ , G ₂ ,...,G _j ,...G _K represent the final formed clustering. Otherwise, set C=C ^* , that is, update the cluster center, and return to step 2 to continue the clustering process. The flow of the K-means clustering algorithm is shown in Figure 2.

Online Orientation Phase

K-Nearest Neighbor Algorithm (KNNSS) is an improved algorithm of Nearest Neighbor Algorithm (NNSS). The nearest neighbor algorithm is easy to implement and the algorithm is simple. Match the measured fingerprints measured in the online stage with the fingerprint database to find the closest fingerprint. The position of the fingerprint corresponding to the sampling point is the estimated position of the point to be measured. The reference fingerprint selected by the nearest neighbor algorithm is relatively single, and the positioning result is unstable, which is prone to large errors.

To solve the problem of a single reference fingerprint, this embodiment adopts a K-nearest neighbor algorithm (K-Nearest Neighbor in Signal Space, KNNSS). In the KNNSS algorithm, instead of selecting the sampling point corresponding to a single fingerprint as the estimated position of the point to be tested, K fingerprints closest to the actual measured fingerprint are selected, and the average value of the K sampling points is calculated, and the average value is the target point to be tested. The estimated location of the point. However, although KNNSS reduces the positioning error on the basis of NNSS, it needs to compare the measured fingerprints with all the fingerprints in the fingerprint database to find the distance difference every time it is positioned online. This positioning process takes too long and the system has a large amount of calculation. , the positioning efficiency is too low. Therefore, in order to improve positioning efficiency while improving positioning accuracy, this embodiment designs a K-nearest neighbor algorithm based on K-means clustering. The positioning process is shown in Figure 3, specifically the following five steps:

Step1. Match the measured fingerprint r=(rssi ₁ , rssi ₂ ,...,rssi _n ) with the fingerprint database after training, and calculate the distance between r and each cluster center, recorded as D=[D ₁ ,D ₂ , ..., D _K ].

Step2. Find the class corresponding to the minimum value min(D) in D, denoted as G _MIN .

Step3. Calculate the distance between the measured fingerprint r=(rssi ₁ , rssi ₂ ,...,rssi _n ) and each fingerprint in G _MIN recorded as in Indicates the i-th fingerprint in this class, n _g indicates the number of fingerprints in this class.

Step4. Will Arranged in ascending order, remove the significantly larger distance values, keep the remaining K distances, and select the fingerprints corresponding to the K distances as reference fingerprints, and the corresponding sampling point coordinates as reference coordinates.

Step5. Calculate the mean value of these K reference coordinates as the estimated position of the measured fingerprint, and the calculation method is shown in formula (8).

$\begin{array}{cc}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; K</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}& {\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; K</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\end{array}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

It is not difficult to find that the present invention uses the mean smoothing method to reduce the volatility of the fingerprint sequence in the offline stage, and uses the K-means clustering algorithm to classify the WiFi fingerprints. The K nearest neighbor algorithm improves the positioning efficiency.

Claims (5)

1. A method for improving WiFi fingerprint location accuracy and efficiency, characterized in that, in the offline training phase, construct a fingerprint database for online location, and classify using the K-means clustering algorithm in the fingerprint database, wherein the fingerprint The signal strength values of the sampling points in the database are processed by data smoothing; in the online positioning stage, the K nearest neighbor algorithm is used to find the K fingerprints closest to the measured fingerprints, and the position of the sampling point corresponding to the average value of the K fingerprints is the location of the point to be tested. estimated location. 2. the method for improving WiFi fingerprint location accuracy and efficiency according to claim 1, is characterized in that, the fingerprint database that described construction is used for online location specifically comprises the following steps: Select an indoor environment as the positioning area, in this positioning area, deploy n wireless access points and select L sampling points, and record the position coordinates of each sampling point; At each sampling point, the mobile terminal with WiFi signal detection function is used to detect the signal strength, and the RSSI value of each wireless access point is collected multiple times, and then the collected data is smoothed to obtain the smoothed mean value of the sampling point. Fingerprint: traverse L sampling points, get L fingerprints, and store them in the fingerprint database. 3. the method for improving WiFi fingerprint location accuracy and efficiency according to claim 1, is characterized in that, adopting K-means clustering algorithm to classify in the fingerprint database specifically comprises the following steps: Carry out K-means clustering on the fingerprint database, using Euclidean distance as the evaluation criterion of similarity, the fingerprints with smaller distances are gathered in one subclass, and the fingerprints with larger distances are far away from each other; Execute the previous step several times until the clustering ends, and the fingerprint database becomes a fingerprint sample space with K subclasses. 4. the method for improving WiFi fingerprint location accuracy and efficiency according to claim 1, is characterized in that, described K-means clustering algorithm is specifically: Input L fingerprints and the number of clusters K, where K≤L; randomly select K fingerprints from the L fingerprints as the initial cluster center; For the remaining fingerprints, calculate the distance from each fingerprint to each cluster center, and after finding the minimum distance, divide the fingerprints into the corresponding clusters, obtain new clustering results, and complete the fingerprint assignment; Calculate the new cluster center and compare it with the last cluster center. If the two are the same, the clustering ends. Otherwise, update the cluster center and return to the previous step to perform clustering. 5. The method for improving WiFi fingerprint positioning accuracy and efficiency according to claim 1, wherein the online positioning stage specifically comprises the following steps: Match the measured fingerprint with the fingerprint database after training, calculate the distance between the measured fingerprint and each cluster center, and find the cluster corresponding to the minimum distance; Calculate the distance between the measured fingerprint and each fingerprint in the cluster corresponding to the minimum distance; Arrange according to the obtained distance values in ascending order, keep the smallest K distances, and select the fingerprints corresponding to the K distances as reference fingerprints, and the corresponding sampling point coordinates as reference coordinates; Calculate the mean value of these K reference coordinates as the estimated position of the measured fingerprint.