Disclosure of Invention
In order to overcome the defects of the prior art, the invention provides an indoor three-dimensional space fingerprint positioning method based on WKNN fusion. Under the condition of not thinning the 3D fingerprint database, K nearest neighbor reference points can be obtained through KNN, and a positioning result is obtained through weighting; and solving another positioning result according to the geometric relation between the coordinates and the distance of the base station in the database, and fusing the two results to realize more accurate and stable positioning precision. The method makes full use of the position fingerprint information, and has the advantages of simple calculation, high positioning precision and high stability.
The technical scheme adopted by the invention for solving the technical problem comprises the following steps:
step 1: establishing a fingerprint off-line information base;
an off-line library building stage: selecting a plurality of reference points in a positioning area, and measuring the received signal strength of all base stations on each reference point; storing the reference point coordinates and the received signal strength into a database together to form a fingerprint database;
and (3) in an online positioning stage: matching the signal intensity information received by the target with information in a fingerprint library by using KNN to obtain K nearest neighbor reference point coordinates:
in the formula D p Indicating signal strength distance, OB indicating signal strength information received by the object, NO k Representing k nearest-neighbor reference points matched by KNN algorithmFingerprint information;
step 2: introducing distance weight W to K nearest neighbor reference point coordinates obtained in the step 1 i :
Wherein (x) i ,y i ,z i ) Reference point coordinates representing the ith nearest neighbor, (x, y, z) target coordinates, d i Representing the signal strength distance between the signal strength information received by the target and the fingerprint information of the ith reference point, wherein epsilon is a positive number;
and step 3: adopting a Chan algorithm based on TDOA to relocate the target;
step 3-1: and (3) calculating:
where d is the actual distance between the target and the base station, d
0 As reference distance, P (d) and P (d)
0 ) Respectively indicate when the target is at a distance d and d from the base station
0 Average received power in time, α represents a path loss parameter; theta represents noise due to shadow fading and fast fading, and theta is a mean of 0, variance
Normal random variable of (1);
step 3-2: an expression of the distance d is derived from equation (3):
equation (4) is modified:
step 3-3: the method for reducing the influence of the noise by adopting the adaptive iterative variance algorithm of the noise specifically comprises the following steps:
the raw noise is defined as:
the noise obtained by the adaptive iterative variance algorithm of the noise is
Step 3-3-1: order to
Let i be 2;
Step 3-3-3: adding 1 to i;
step 3-3-4: repeating the steps 3-3-2 to 3-3-3 until
When it is time, the cycle is ended, and
variance of theta using adaptive iterative variance algorithm with noise
Carrying out treatment;
according to the distance d
i Corresponding noise thereof
The method is obtained by adopting a Chan algorithm in TDOA to carry out positioning calculationA new set of target point coordinates (x, y, z);
and 4, step 4: fusing the positioning results of the step 2 and the step 3, which comprises the following specific steps:
in the X direction:
in the formula (I), the compound is shown in the specification,
the result of the fusion in the X direction is shown,
indicating position information of the WKNN method in the X direction;
indicating the position information, variance, of the Chan algorithm in the X direction
And
obtaining by adopting a statistical method of multiple measurements;
y direction:
in the formula (I), the compound is shown in the specification,
the result of the fusion in the Y direction is shown,
indicating position information of the WKNN method in the Y direction;
representing the Chan AlgorithmPosition information in the Y direction, variance
And
obtaining by adopting a statistical method of multiple measurements;
the Z direction:
in the formula (I), the compound is shown in the specification,
showing the result of the fusion in the Z direction,
indicating position information of the WKNN method in the Z direction;
indicating the position information, variance, of the Chan algorithm in the Z direction
And
and obtaining the data by adopting a statistical method of multiple measurements.
Preferably, in the formula (1), when p is 1, D p Denotes the Manhattan distance, D when p is 2 p Representing the euclidean distance.
Preferably, the epsilon < 0.01.
Preferably, said d 0 =1m,α=2。
By adopting the WKNN fusion-based indoor three-dimensional space fingerprint positioning method, the position fingerprint information is fully mined by adopting an information fusion algorithm, the positioning precision is improved, and the instability in the positioning process is overcome. The method breaks through indoor plane positioning, can position in an indoor three-dimensional space, and is suitable for scenes such as indoor multilayer parking lots, superstores, railway stations and the like.
Detailed Description
The invention is further illustrated with reference to the following figures and examples.
As shown in fig. 1 and fig. 2, the present invention provides an indoor three-dimensional spatial fingerprint positioning method based on WKNN fusion, which includes the following steps:
step 1: establishing a fingerprint off-line information base;
an off-line library building stage: selecting a plurality of reference points in a positioning area, and measuring the received signal strength of all base stations on each reference point; storing the reference point coordinates and the received signal strength into a database together to form a fingerprint database;
and (3) in an online positioning stage: matching the signal intensity information received by the target with information in a fingerprint library by using KNN to obtain K nearest neighbor reference point coordinates:
in the formula, D p Indicating signal strength distance, OB indicating signal strength information received by the object, NO k Fingerprint information of k nearest neighbor reference points matched by the KNN algorithm is represented;
step 2: for the K nearest neighbor reference point coordinates obtained in the step 1, but KNN is a mean value algorithm, namely, several reference points are obtainedIs regarded as the target position, is usually inaccurate, so the WKNN algorithm is adopted to introduce the distance weight W i :
Wherein (x) i ,y i ,z i ) Reference point coordinates representing the ith nearest neighbor, (x, y, z) target coordinates, d i Representing the signal strength distance between the signal strength information received by the target and the fingerprint information of the ith reference point, wherein epsilon is a very small positive number and is used for preventing the divisor in the formula from being zero;
and step 3: adopting a Chan algorithm based on TDOA to relocate the target;
step 3-1: and (3) calculating:
where d is the actual distance between the target and the base station, d
0 As reference distance, P (d) and P (d)
0 ) Respectively indicate when the target is at a distance d and d from the base station
0 Average received power in time, α represents a path loss parameter; theta denotes noise due to shadow fading and fast fading, and theta is a mean of 0 and a variance
Normal random variable of (1);
step 3-2: an expression of the distance d is derived from equation (3):
an unbiased estimator of the distance estimate is used to modify equation (4):
step 3-3: the formula (5) can generate larger distance deviation when the signal changes frequently, therefore, the invention provides a noise adaptive iterative variance algorithm, thereby reducing the influence of noise on propagation path evaluation, and the specific steps are as follows:
the raw noise is defined as:
the noise obtained by the adaptive iterative variance algorithm of the noise is
Step 3-3-1: order to
Let i be 2;
Step 3-3-3: adding 1 to i;
step 3-3-4: repeating the steps 3-3-2 to 3-3-3 until
When it is time, the cycle is ended, and
variance of theta using adaptive iterative variance algorithm with noise
Carrying out treatment;
according to distance d
i And itCorresponding noise
Performing positioning calculation by using a Chan algorithm in TDOA to obtain a group of new target point coordinates (x, y, z);
in a three-dimensional space, because the nodes matched with the position fingerprints are enough, the invention provides a TDOA-based distance measurement method for geometric positioning, and distance difference is obtained by differentiating the distances; obtaining a weighted least square result of the position by a hyperbolic positioning method or a trilateral positioning method, wherein higher positioning accuracy can be obtained by a Chan algorithm or a Taylor series expansion method of TDOA in a three-dimensional space;
and 4, step 4: fusing the positioning results of the step 2 and the step 3, which comprises the following specific steps:
and respectively obtaining a WKNN positioning result and a multilateral positioning result based on TDOA through the 3 steps, regarding the two positioning results as two different information sources in fusion positioning, and respectively fusing the three dimensions of X, Y and Z through an information fusion formula.
In the X direction:
in the formula (I), the compound is shown in the specification,
the result of the fusion in the X direction is shown,
indicating position information of the WKNN method in the X direction;
indicating the position information, variance, of the Chan algorithm in the X direction
And
obtaining by adopting a statistical method of multiple measurements;
y direction:
in the formula (I), the compound is shown in the specification,
the result of the fusion in the Y direction is shown,
indicating position information of the WKNN method in the Y direction;
indicating the position information, variance, of the Chan algorithm in the Y direction
And
obtaining by adopting a statistical method of multiple measurements;
the Z direction:
in the formula (I), the compound is shown in the specification,
showing the result of the fusion in the Z direction,
indicating position information of the WKNN method in the Z direction;
indicating the position information, variance, of the Chan algorithm in the Z direction
And
and obtaining the data by adopting a statistical method of multiple measurements.
Preferably, in the formula (1), when p is 1, D p Denotes the Manhattan distance, D when p is 2 p Representing the euclidean distance.
Preferably, the epsilon < 0.01.
Preferably, said d 0 =1m,α=2。
The specific embodiment is as follows:
step 1, setting a simulation scene.
Simulation scenario set to [500,500,500 ]]m 3 Under the three-dimensional coordinate system of (1):
scene one: as shown in fig. 3, the target is located at [420,420,420] meters, the target is located by using a location fingerprint method and using KNN, WKNN algorithms and a Chan algorithm based on TDOA, the location results obtained by the two algorithms are fused, and the result is included in a scene-location table.
TABLE 1 scene-location table
| True position of target
|
[420,420,420]
|
| Position of KNN
|
[412.5,412.5,412.5]
|
| WKNN position
|
[415.67,415.67,415.67]
|
| Chan algorithm position
|
[425.24,412.22,418.31]
|
| Fusion site
|
[423.32,412.91,417.78] |
On the basis of the above steps, 1000 times of target positioning is carried out, the distance from the positioning result to the true value in various methods is used as an independent variable, the percentage falling into an error circle is used as a dependent variable, and a Cumulative Distribution Function (CDF) diagram related to the error is made.
Scene two: as shown in fig. 4, the target moves arbitrarily in the positioning space, the positioning and tracking are performed by using the position fingerprint KNN, the position fingerprint WKNN, and the geometric positioning Chan method, the two methods, WKNN and Chan, are fused, and the positioning effect is evaluated.
And 2, constructing a fingerprint database. 8 vertexes of the cube are selected in the space as each reference point of one target to be positioned.
The first stage is as follows: in the positioning area, 20 × 20 × 20 reference points are selected according to a regular shape, that is, every 25m of each coordinate is recorded as a fingerprint reference point, and the received signal strength of all APs is measured on each reference point. The reference point coordinates and the received signal strength are stored in a database together to form a fingerprint database with 8000 reference points. The mapping relation between the positions in the fingerprint database and the fingerprint signals is stored in a relation table.
And a second stage: and (3) calculating Euclidean distance information of the target and each reference point by using the formula (1), and matching the Euclidean distance information with the signal information in the database by KNN.
And 3, weighting the matched 8 reference point position fingerprints. Introducing the weight of the distance to approach the true value of the target more, including:
KNN is a mean value algorithm, namely the mean value of 8 reference points is taken as the target position, in order to improve the precision and reduce the cost, a WKNN algorithm can be adopted, the reciprocal of the distance is taken as a weight factor, namely the weight of which reference point is higher when the reference point is close to, and epsilon is 0.01.
And 4, reversely solving the distance according to the signal strength, and positioning the target again through a Chan algorithm based on TDOA.
Calculating the distance from a target to an anchor node by adopting an unbiased estimator of the signal pair distance, and taking the difference of the distances as the distance difference value of the TDOA:
the Chan algorithm is a method of weighting least squares twice on a target, and in the first weighting, independent variables and long target distance are assumed to obtain a primary target position solution. And (3) obtaining a variance matrix by using the distance approximation between the solution and each anchor node to replace a true value, obtaining a process solution by using a first weighted least square algorithm, constructing a relation matrix because the actual independent variables meet the distance constraint, namely are not independent, obtaining a final solution by using a second weighted least square method, and obtaining an accurate target position solution by reverse solution.
And 5, fusing the WKNN positioning result of the fingerprint and the positioning result of the Chan algorithm.
In this embodiment, the standard deviation σ is taken W =5,σ T In practice, the variance should be obtained statistically.
And 6, comparing the performance indexes.
To illustrate the superiority of the present invention, for scene 1, the cumulative distribution function is selected as the comparison index; for scene 2, the position root mean square error and the position average root mean square error are selected as comparison indicators. The comparison method is a plurality of positioning methods mentioned by the invention, such as a fingerprint KNN, a fingerprint WKNN, a Chan algorithm based on TDOA, and a final fusion result of the invention. And (3) taking the accumulated distribution function and Root Mean Square Error (RMSE) as comparison indexes, and defining the target position RMSE at the time t as follows:
in the formula, x
t ,y
t And z
t Is the position of the target at time t,
and
is the target location estimated by various methods.
Fig. 5 shows the results of 1000 monte carlo simulations of a target located at the MS ═ 420,420,420, according to fig. 5:
the convergence of the fusion WKNN algorithm is fastest, and the error is basically within 15 m; the error is basically within 25m after the WKNN algorithm and the Chan algorithm are carried out; the KNN algorithm is located at 25 × 25 × 25m by itself 3 The target in the area is regarded as the center point of the cube, so that the position resolution of the target is low, the jump phenomenon exists in the cumulative distribution function, and the positioning accuracy is the worst.
FIG. 6 is a graph of pairs 500X 500m 3 The target moves randomly and 1000 monte carlo simulations are performed, and the results can be obtained according to fig. 6:
when the traditional KNN algorithm is used for real-time positioning, the target resolution is low, namely the KNN is positioned at 25 multiplied by 25m for the target 3 All will target the center point of this cube; while WKNN can adjust the position by weight within the above-mentioned area range, the highest accuracy is only near the reference point and the center, and the accuracy of the rest of the area is still relatively poor. The positioning accuracy of KNN and WKNN is very unstable in the whole positioning process. The KNN error is about 4-18 m, the WKNN error is about 4-11 m, but the fluctuation is large. The positioning of the Chan algorithm based on the TDOA is relatively stable, the fluctuation is less, but the precision is basically maintained at about 10m, and the fusion result can improve the precision and reduce the instability of WKNN, and the precision is maintained at about 6 m.