CN111669702A - Coarse and fine matching positioning method based on WIFI address and field intensity - Google Patents
Coarse and fine matching positioning method based on WIFI address and field intensity Download PDFInfo
- Publication number
- CN111669702A CN111669702A CN202010498251.2A CN202010498251A CN111669702A CN 111669702 A CN111669702 A CN 111669702A CN 202010498251 A CN202010498251 A CN 202010498251A CN 111669702 A CN111669702 A CN 111669702A
- Authority
- CN
- China
- Prior art keywords
- class
- address
- fingerprint
- matching
- wifi
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
- 238000000034 method Methods 0.000 title claims abstract description 46
- 239000013598 vector Substances 0.000 claims abstract description 54
- 238000004364 calculation method Methods 0.000 claims abstract description 17
- 238000007781 pre-processing Methods 0.000 claims abstract description 9
- 238000000638 solvent extraction Methods 0.000 claims abstract description 6
- 238000001914 filtration Methods 0.000 claims description 23
- 238000005516 engineering process Methods 0.000 claims description 6
- 150000001875 compounds Chemical class 0.000 claims description 3
- 238000012360 testing method Methods 0.000 description 11
- 230000003068 static effect Effects 0.000 description 8
- 238000012545 processing Methods 0.000 description 4
- 238000013461 design Methods 0.000 description 3
- 238000005070 sampling Methods 0.000 description 3
- 238000004458 analytical method Methods 0.000 description 2
- 238000002474 experimental method Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 239000008186 active pharmaceutical agent Substances 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 230000009977 dual effect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005562 fading Methods 0.000 description 1
- 239000012634 fragment Substances 0.000 description 1
- 230000004807 localization Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W4/00—Services specially adapted for wireless communication networks; Facilities therefor
- H04W4/02—Services making use of location information
- H04W4/023—Services making use of location information using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W4/00—Services specially adapted for wireless communication networks; Facilities therefor
- H04W4/30—Services specially adapted for particular environments, situations or purposes
- H04W4/33—Services specially adapted for particular environments, situations or purposes for indoor environments, e.g. buildings
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W64/00—Locating users or terminals or network equipment for network management purposes, e.g. mobility management
- H04W64/006—Locating users or terminals or network equipment for network management purposes, e.g. mobility management with additional information processing, e.g. for direction or speed determination
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Position Fixing By Use Of Radio Waves (AREA)
Abstract
The invention provides a rough and fine matching positioning method based on a WIFI address and field intensity, which comprises the following steps: step 1: carrying out layout of quadrilateral grids or triangular mesh fingerprint points; step 2: collecting and preprocessing data, and establishing a fingerprint database; and step 3: clustering and partitioning the fingerprint databases, and calculating the class center of each fingerprint database class, including the class center signal intensity vector and the class address vector corresponding to the class center signal intensity vector; and 4, step 4: rough matching is carried out on the access point address information of the real-time WIFI signal and the address vector of each class, and rough class range estimation is achieved; and 5: calculating the distance between the real-time WIFI signal strength value and the WIFI signal strength central vector in the class obtained after rough matching and the belonged probability to accurately determine the class to which the real-time WIFI signal strength value belongs so as to enhance the class matching accuracy; step 6: in the precisely determined class set, the final position of the target is calculated by the WKNN algorithm. The method can reduce the workload of fingerprint acquisition and the positioning calculation amount, and improve the WIFI positioning precision.
Description
Technical Field
The invention relates to the technical field of WIFI positioning, in particular to a rough and fine matching positioning method based on WIFI addresses and field intensity.
Background
At present, WIFI positioning is a popular indoor positioning technology, and its positioning method is a propagation model method and a fingerprint identification method based on signal strength. The propagation model method of signal strength refers to using a certain channel fading model assumed under the current environment, estimating the distance between a terminal and an AP (access point, referred to as AP for short) at a known position according to the mathematical relationship, and if a user hears a plurality of AP signals, obtaining the position information of the user through a trilateration algorithm; the fingerprint identification method combines the detection data of a plurality of APs into fingerprint information based on the propagation characteristics of WIFI signals, and estimates the possible position of the moving object by comparing the fingerprint information with reference data. In some scenes that the positioning accuracy is the meter level, WIFI can be used for covering, and the technology is suitable for positioning navigation of people/vehicles, scenes such as medical institutions, markets and theme parks.
For dense people flow scenes such as shopping malls and airports, WIFI signals are likely to be frequently shielded, and a WIFI signal propagation model method with complex changes is difficult to establish, so a fingerprint-based method is generally adopted. The fingerprint library method also faces two problems: firstly, a large positioning range requires huge fingerprint acquisition workload; secondly, the larger the fingerprint database is, the larger the calculation amount is, the more the mismatching is caused, and the positioning precision is influenced.
Disclosure of Invention
In order to make up for the defects in the prior art, the invention provides a rough and fine matching positioning method based on a WIFI address and field intensity.
In order to achieve the purpose, the invention adopts the following technical scheme:
the rough and fine matching positioning method based on the WIFI address and the field intensity comprises the following steps:
step 1: according to the area size of the positioning place and the positioning requirement, the layout of quadrilateral grids or triangular mesh fingerprint points is carried out;
step 2: collecting data and preprocessing the data to establish a fingerprint database;
and step 3: clustering and partitioning the fingerprint databases, and calculating the class center of each fingerprint database class, including the class center signal intensity vector and the class address vector corresponding to the class center signal intensity vector;
and 4, step 4: rough matching is carried out on the access point address information of the real-time WIFI signal and the address vector of each class, and rough class range estimation is achieved;
and 5: distance and probability calculation is carried out by utilizing the real-time WIFI signal intensity value and a WIFI signal intensity central vector value of a class fingerprint database obtained after rough matching, and the class where the WIFI signal intensity central vector value is located is accurately determined so as to enhance class matching accuracy;
step 6: in the precisely determined class set, the final position of the positioning target is calculated.
Further, in step 2, the collected data includes: WIFI signal intensity, WIFI access point AP address information and fingerprint point real coordinates.
Further, defining that the proportion of the nonzero number of the WIFI signal strength values received by each access point to the total observed number of the access point reaches 75% as effective access points, and extracting the observed quantity of the first 10 effective access points with the maximum average signal strength from the observed data of each fingerprint point to serve as basic data established by the fingerprint database. If the effective signals are less than 10, all are taken as the access point observations.
Further, step 3, establishing a clustering fingerprint database by using the maximum signal intensity information, wherein the clustering process is as follows:
taking a 1 st fingerprint point as a clustering starting point of a first class;
② calculating the quantity value N of the AP address contained in the next fingerprint point which is the same as the existing AP addressiAPThen taking out NiAPMaximum value N inIAP(ii) a The class address refers to an AP address commonly contained by all fingerprint points in the same class; n is a radical ofiAPRepresenting the same AP address number of the fingerprint point and the ith class;
③ determining the class attribution of the fingerprint point, if N is satisfiedIAP≥CNAPIf so, classifying the point into an I-type set, simultaneously keeping the intersection of the point and an original I-type address set, updating the I-type address set to be used as a comparison basis of the access point address of the next fingerprint point; otherwise, the point is used as the clustering starting point of the next new class; CNAPThe number of the same access points AP in the same class is the clustering parameter;
and fourthly, repeating the steps II and III until all the points are classified.
Further, step 3, calculating the class center of each fingerprint database class, including the class center signal intensity vector and the corresponding class address vector; the quasi-center signal strength vector includes the mean and standard deviation of the signal strength, and the calculation formula is as follows:
in the formula (I), the compound is shown in the specification,
representing the field intensity values of n APs in the class acquired by the fingerprint points i in the m classes;
and σmIs a class m mean and standard deviation vector of class-like center signal strengths, wherein
σm＝{σ1,m,σ2,m,…,σn,m} (5)
n is the number of identical Mac addresses in class m, DmThe number of dots included in the m-th class is referred to.
Further, step 4, roughly matching the AP address information of the signal access point received in real time with an address vector of a fingerprint library class center to determine a rough class range; the coarse matching method adopts a double-layer filtering technology, and gradually reduces the search space through two times of continuous filtering, wherein the two times of filtering are as follows in sequence:
the method comprises the steps of firstly, filtering, namely filtering by using an AP address corresponding to the RSSI (received signal strength indication) with the maximum signal strength received by a positioning target in real time to obtain a search space;
and a second step of filtering, namely filtering the upper search result by using the access point AP address corresponding to the first N RSSI maximum signal strengths received by the positioning target in real time.
Further, step 5, accurately determining the class of the user by using the distance between the WIFI signal strength value and the WIFI signal strength central vector of each fingerprint database, so as to enhance the class matching accuracy, wherein the steps include:
step one, judging the occurrence frequency of the maximum matching rate based on the WIFI address, and if the occurrence frequency is 1, assigning a corresponding class serial number to a final determined class; otherwise, the second step of fine matching based on the signal characteristics is carried out;
secondly, calculating the relationship between the distance from the real-time received signal vector to various central vectors and the probability according to the same access point address and the formulas (6) to (7); namely, when a user receives the WIFI signal intensity s in real time, relevant preprocessing is carried out on s, and then s and various centers are calculated
The distance between:
and modeling the signal intensity distribution of the class set by using a Gaussian model, wherein the probability density function is as follows:
selecting through a formula 8, assigning the class serial number with a relatively small signal vector distance and a relatively large probability to the final determination class:
cm＝pm(s)/dm(8)
is selected cmThe class with the largest value is used as the matching target without the need of matching the whole fingerprintThe database is searched one by one.
Further, step 6, a weighted nearest neighbor method KWNN is applied to the precisely determined class set to realize final position calculation.
The invention has the beneficial effects that: (1) the invention provides a design that offline sample points are arranged into a quadrilateral grid or a crossed triangular mesh structure, and the sampling points of the triangular grid relative to the quadrilateral grid are reduced by 1/2 under the condition that the positioning accuracy is not different too much, so that the offline sampling workload is reduced by half.
(2) The invention utilizes the maximum signal intensity information to establish a clustering fingerprint database. And calculating the quantity value that the AP address contained in the next fingerprint point is respectively the same as the existing AP address, and giving out the method for determining the optimal clustering parameter.
(3) Firstly, carrying out rough matching by using access point address information of a real-time signal and an address vector of a class center to realize rough class range estimation; and then further calculating by using the distance between the signal intensity value and the signal intensity central vector of each type of fingerprint database and the belonged probability to more accurately determine the class, so as to enhance the class matching accuracy. The data of the fingerprint database with the quadrilateral mesh structure is used for carrying out double-class matching operation analysis, and the matching result shows that the accuracy of fine matching and coarse matching is improved by 2.7 times to the maximum extent; and the method for the optimal matching parameters during the dynamic positioning of the fingerprint database is provided through experiments. And finally, applying a weighted nearest neighbor method KWNN in the accurately determined class set to realize final position calculation.
Drawings
FIG. 1 is a flow chart of the present invention;
FIG. 2 is a layout of fingerprint points of a quadrilateral mesh structure;
FIG. 3 is a layout of fingerprint points of a triangular mesh structure;
fig. 4 shows the clustering condition (partial region) of the fingerprint database, (a) the result of matching point class No. 5, and (b) the result of matching point class No. 24.
Detailed Description
The invention is described in further detail below with reference to the figures and the specific embodiments.
The indoor positioning method based on the fingerprint database mainly comprises two steps: and (4) acquiring an off-line signal, establishing a fingerprint database and calculating the target position by on-line matching. The off-line process comprises fingerprint point layout design, data acquisition preprocessing and database building, and database clustering and partitioning processing for reducing matching workload; the online stage aiming at the clustering fingerprint database also comprises two parts of contents, namely the fingerprint database class is matched and reduced to match a space, and the target position calculation is realized by combining a related positioning algorithm in a specified class.
1.1 fingerprint Point layout Structure design
Through the positioning error analysis of fingerprint point databases with different structural layouts, the average error based on the quadrilateral fingerprint database is only 0.34m lower than that based on the triangular fingerprint database, the maximum error is 2.64m lower, but the probabilities of the errors within 5m of the quadrilateral fingerprint database and the triangular fingerprint database are basically the same, which shows that in a long and narrow environment, offline sample points can be considered to be distributed into a crossed triangular mesh structure, and in the case that the positioning accuracy does not differ too much, 1/2 are fewer than that of a quadrilateral regular grid, so that the offline sampling workload is reduced by half. So, if in a larger range scene, a triangular mesh may be selected.
1.2 offline data acquisition and preprocessing
Comparing the original data, and finding that the difference of the signal strength received in different directions can reach 20dB at most; determining that 75% of the ratio of the non-zero number of the signal strength values received by each access point to the total number of the observation points is a valid access point; and taking the observed quantities of the first 10 effective access points with the maximum average signal intensity on each fingerprint point as basic data established by the fingerprint database. If the effective signals are less than 10, all are taken as the access point observations.
1.3 building a clustered fingerprint database
In the WIFI fingerprint positioning method, an offline fingerprint database needs to be established, and the fingerprint database needed in the indoor environment of a large area is relatively huge, so that the calculated amount is large in the real-time matching process of the database. Therefore, the clustering and partitioning processing is carried out on the fingerprint database, so that only one subclass block is needed to be matched during real-time matching and positioning, the whole fingerprint database is not needed to be matched one by one, and the real-time calculation amount of the algorithm can be reduced.
Clustering and partitioning are to cluster elements in a set together according to feature similarity, and the basic principle is that the feature similarity in a class is greater than the feature similarity of elements in different classes.
And establishing a clustering fingerprint database by using the maximum signal intensity information. The clustering process is as follows:
taking the 1 st fingerprint point as a clustering starting point of the first class.
② calculating the quantity value N of the access point address contained in the next fingerprint point being the same as the existing class addressiAP(NiAPRepresenting the same number of access points as the ith class for that fingerprint point), and then take N outiAPMaximum value N inIAP. The class address refers to an access point address commonly contained in all fingerprint points in the same class.
③ determining the class attribution of the fingerprint point if N is satisfiedIAP≥CNAPIf so, classifying the point into an I-type set, simultaneously keeping the intersection of the point and an original I-type address set, updating the I-type address set to be used as a comparison basis of the access point address of the next fingerprint point; otherwise, the point is used as the clustering starting point of the next new class.
And fourthly, repeating the steps II and III until all the points are classified.
The method relates to a self-defined parameter, namely the number CN of the same access points AP in the same classAPReferred to as clustering parameters. In the experimental scene, the optimal clustering parameters CN of two fingerprint databases are determinedAPThe values were all 7. The experimental result shows that when the clustering parameter is 7, the average error of fingerprint positioning is minimum, and the probability value of the error within 5m is maximum.
1.4 computing class center for each fingerprint database class
After the clustering parameters of the fingerprint database are set, clustering the fingerprint database. Firstly, calculating the class center of each fingerprint database class, wherein the class center comprises a class center signal intensity vector and a class address vector corresponding to the class center signal intensity vector, and the class center is used for subsequent online matching operation. The center-like signal strength vector typically includes the mean and standard deviation of the signal strength, and is calculated as follows:
in the formula (I), the compound is shown in the specification,
and σmIs a class m mean and standard deviation vector of class-like center signal strengths, wherein
σm＝{σ1,m,σ2,m,…,σn,m} (4)
n is the number of identical Mac addresses in class m, DmRefers to the number of points contained in the m-th class, and
representing the field strength values of n APs in the class acquired by the fingerprint point i in the m classes.
After clustering processing, in a real-time matching stage, when a user receives WIFI signal intensity s in real time, relevant preprocessing is carried out on s, and then s and various centers are calculated
The distance between them is as follows:
and modeling the signal intensity distribution of the class set by using a Gaussian model, wherein the probability density function is as follows:
selecting through a formula 8, assigning the class serial number with a relatively small signal vector distance and a relatively large probability to the final determination class:
cm＝pm(s)/dm(8)
is selected cmThe class with the largest value is used as a matching target, and the whole fingerprint database does not need to be searched one by one, so that the real-time calculation amount of the indoor positioning system is greatly reduced, and the real-time performance of the algorithm is improved.
1.5 Online Dual class matching operation
Preprocessing the original acquired signal strength in a 'getting strong and getting weak' mode, namely selecting the information of the first 10 access points with the strongest signal strength values received at the same position point, and matching and positioning the information with a fingerprint database. If the effective signals are less than 10, all are taken as the access point observations.
When on-line matching positioning is carried out, firstly, rough matching is carried out by utilizing access point address information of real-time signals and an address vector of a class center, and rough class range estimation is realized; and then, further, the distance between the signal intensity value and the signal intensity central vector of each type of fingerprint database is used for determining the accurate type, so that the accuracy of type matching is enhanced, and the positioning precision is improved.
1.5.1 Signal AP Address assisted fingerprint library type coarse matching operation
And roughly matching the AP address information of the signal access point received in real time with the address vector of the fingerprint library class center to determine a rough class range. The rough matching method adopts a reference point layer filtering technology, the technology gradually reduces the search space through two times of continuous filtering, and the two times of filtering are sequentially as follows:
and a first step of filtering, namely filtering by using a Mac address of an Access Point (AP) corresponding to the RSSI (received signal strength indication) with the maximum signal strength received in real time by a target TP (TP, Test Point), so as to obtain a search space.
And a second step of filtering, namely filtering the upper search space by using the Mac address of the access point AP corresponding to the first N maximum signal strength RSSIs received by the target TP in real time.
This requires determining the number N of AP access points with the greatest signal strength in the second filtering step, called the matching parameter MNAP. Front MN of each test pointAPThe access point AP addresses corresponding to the maximum signal strengths are compared to the corresponding set of class center addresses Mac. Firstly, a static positioning test is carried out, because the static points are selected from a fingerprint library, the class where the static points are located is known, and therefore the accuracy of class matching is evaluated by adopting the RigR index of the class matching accuracy.
In this experimental scenario, taking the class matching test of the quadrilateral fingerprint database as an example, the class matching result is shown in the following table:
TABLE 1 coarse matching results for static test points
Wherein, MNAPRepresenting pre-test point MN for matching parametersAPA maximum signal strength; ProR indicates that in the class matching process, each test point is subjected to address matching, and the class set where the test point is located is determined according to the maximum matching rate, wherein the probability of the class truth value is included, namely the possible probability of correct class matching; RigR represents the probability value that the class set where the unique maximum address matches is the same as the class true value where the test point is located in the class matching process, namely the accuracy of correct data class matching.
Comparing the class matching result based on the quadrilateral fingerprint database in the table, and when the MN is usedAPWhen the value is small (e.g. 1 or 2), the probability of possible matching ProR is relatively large, but the correct matching rate RigR is very small, so that the value of N is not preferably 1 or 2. When N is 5, the correct matching probability is highest and reaches 41%. Specifically checking the table data, when N is 5, the number of points respectively corresponding to ProR and RigR is 15 and 11, namely 11 points are matched by the correct fingerprint library class obtained by means of the unique maximum address matching rate, and in addition, 4 points are provided, and the maximum address matching rate of the 4 points appears in a plurality of classes once being checkedThe details are shown in the following table:
table 2 partial results of class matching
Wherein, RouC represents the class serial number obtained by two times of continuous filtering matching, and RelC represents the real class serial number.
The figure is a local clustering condition of the fingerprint database, the 4 th fingerprint class library is adjacent to the 5 th fingerprint class library, and the 37 th fingerprint class library is adjacent to the 25 th, 36 th and 38 th fingerprint class libraries. Indicating that the coarse match results in a contiguous class range.
According to the clustering processing result of the fingerprint database, 390 fingerprint points are totally divided into 39 fingerprint data classes, wherein the 1 st to 24 th classes, the 25 th to 31 th classes, the 32 th to 39 th classes, the 23 rd, 24 th and 31 th classes and the 25 th, 26 th and 37 th classes are respectively and sequentially adjacent fingerprint class sets in geometric structure. In the table MNAPThe number of anchor points corresponding to the 10 possible matching rate ProR and the correct matching rate RigR is 22 and 7 respectively, and the specific class matching conditions are shown in table 3. The table shows that when the rough matching uniquely determines the serial number of the class, two conditions exist, namely correct matching exists, and adjacent classes are matched, wherein the former accounts for 58.3%, and the latter accounts for 41.7%; the coarse matching of the remaining 15/27 anchor points using the AP address information yields a class range that has a proximity relationship in geometry.
Therefore, according to the class matching result, when the WIFI access point address information is used for class matching, the WIFI access point address information is easily matched with a plurality of adjacent class sets, and the correct matching rate is not high. Therefore, further matching operations need to be considered to improve the accuracy probability of class matching.
Table 3 type match partial results
Wherein, RouC represents the class serial number obtained by rough matching, ExaC represents the class serial number obtained by fine matching based on the signal intensity below, and RelC represents the real class serial number.
1.5.2 Signal Strength assisted fingerprint library class Fine matching operation
According to the above coarse matching result, the reason why the correct matching rate is low is that the proximity class matching is generated, because the sample points of the proximity class set are relatively close in geometric position and belong to a fragment, and the access points AP that can be received have great similarity. Therefore, to avoid large errors due to matching to neighboring classes, a further class fine match can be made based on the signal strength characteristics, considering the range of possible correct matches, comprising the steps of:
step one, judging the occurrence frequency of the maximum matching rate based on the WIFI address, and if the occurrence frequency is 1, assigning a corresponding class serial number to a final determined class; otherwise, the second step of fine matching based on the signal characteristics is carried out.
And secondly, calculating the distance from the real-time received signal vector to the class center vector and the class probability of the real-time received signal vector according to the same access point address. According to the signal propagation characteristics, the closer the geometrical distance between two data acquisition points is, the higher the probability that the received signal strength values are similar. And (4) performing selection calculation according to the formula 8 to determine a final class.
By adopting the fine matching method, further fine matching operation is carried out on the result after the coarse matching, and the final result of the class matching is obtained as shown in the following table:
TABLE 4 Fine matching results for static test points
Comparing the result table based on rough matching of the access point address with the result table of further fine matching, the fine matching based on the signal vector distance is improved by 2.7 times to the maximum compared with the correct matching rate of the rough matching, and the matching parameter MN corresponding to the maximum correct matching probabilityAPIs 3.
And then, performing a dynamic positioning experiment, performing rough matching operation on WIFI signal strength and address information received by a user in real time by using an access point address, performing fine matching operation by using the distance between the signal strength and a signal center vector of a rough matching determination class, evaluating a matching effect according to positioning accuracy of different matching parameters, and determining an optimal matching parameter during dynamic positioning. Table 5 shows the positioning result obtained by performing a double-class matching operation on the database of the quadrilateral fingerprints and then using the conventional KNN algorithm.
TABLE 5 coarse and fine matching positioning result based on WIFI Address and field intensity
As can be seen from the positioning error values in Table 5, the class matching parameter MNAPWhen 5 is taken, the average error is minimum and is 4.09m, the corresponding maximum error is also minimum, and the probability that the positioning error is less than or equal to 5m is maximum. Therefore, the class matching parameter MN is used for dynamic positioning by using the quadrilateral fingerprint databaseAPThe value should be 5.
Analyzing the reason that the matching parameters of the dynamic and static positioning are inconsistent, because the static positioning data are randomly selected from the fingerprint database, the data acquisition characteristics are consistent with the fingerprint database, the data are acquired in four directions, and the data acquisition times are 40 times, the probability of correct matching is higher; the data in dynamic positioning only adopts a group of received wireless signal data, namely when the scanned signal is changed and updated, new data is immediately used for positioning calculation, because the random of the signal causes great challenge to correct matching, and the matching parameters MN of two test schemes (dynamic positioning and static positioning) are also enabledAPDifferent.
1.6 WKNN positioning algorithm
After rough matching operation to fine matching operation of the fingerprint database class set, only matching positioning calculation is needed to be carried out in the determined set, and the whole fingerprint database does not need to be searched one by one, so that the real-time calculation amount of an indoor positioning system is greatly reduced, and the real-time performance of an algorithm is ensured.
The localization is performed using a Weighted K Nearest neighbor algorithm (WKNN) in the selected class. The K nearest neighbor algorithm is that K minimum position fingerprint points in RSS Euclidean distance are selected, and then the average position coordinates of the fingerprint points are calculated to serve as the positioning result of a user:
wherein (x)i,yi) The coordinates corresponding to the ith nearest neighbor fingerprint point in the determined fingerprint class set;
is the outputted positioning result. Further, WKNN takes into account the difference in distance between the signal strength values at the K fingerprint points and the measured RSS signal strength, so that the weights of different neighboring fingerprint points are also different. And taking the inverse Euclidean distance obtained by calculation as a weight, and calculating the position coordinates as follows:
wherein d isiIs the RSS euclidean distance between the measured RSS sample vector and the mean of the corresponding access point AP of the ith nearest neighbor fingerprint point in the determined class. The reciprocal of the Euclidean distance of the signal is set as a weighting coefficient of the proximity algorithm, so that the coordinate weight of the fingerprint point with smaller actual RSS distance is larger, and the positioning precision of the fingerprint point can be improved to a certain extent.
The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention, and various modifications and changes may be made by those skilled in the art. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the protection scope of the present invention.
Claims (8)
1. The rough and fine matching positioning method based on the WIFI address and the field intensity is characterized by comprising the following steps of:
step 1: according to the area size of the positioning place and the positioning requirement, the layout of quadrilateral grids or triangular mesh fingerprint points is carried out;
step 2: collecting data and preprocessing the data to establish a fingerprint database;
and step 3: clustering and partitioning the fingerprint databases, and calculating the class center of each fingerprint database class, including the class center signal intensity vector and the class address vector corresponding to the class center signal intensity vector;
and 4, step 4: rough matching is carried out on the access point address information of the real-time WIFI signal and the address vector of each class, and rough class range estimation is achieved;
and 5: distance and probability calculation is carried out by utilizing the real-time WIFI signal intensity value and a WIFI signal intensity central vector value of a class fingerprint database obtained after rough matching, and the class where the WIFI signal intensity central vector value is located is accurately determined so as to enhance class matching accuracy;
step 6: in the precisely determined class set, the final position of the positioning target is calculated.
2. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 2, the collected data comprises: WIFI signal intensity, WIFI access point AP address information and fingerprint point real coordinates.
3. The WIFI address and field strength based rough and fine matching positioning method according to claim 2, wherein the effective access points are defined as the points with a ratio of the nonzero number of WIFI signal strength values received by each access point to the total observed number of the points being 75%, and the first 10 effective access point observed quantities with the maximum average signal strength are extracted from the observed data of each fingerprint point and used as the basic data established by the fingerprint database. If the effective signals are less than 10, all are taken as the access point observations.
4. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 3, a clustering fingerprint database is established by using the maximum signal strength information, and the clustering process is as follows:
taking a 1 st fingerprint point as a clustering starting point of a first class;
② calculating the quantity value N of the AP address contained in the next fingerprint point which is the same as the existing AP addressiAPThen taking out NiAPMaximum value N inIAP(ii) a The class address refers to an AP address commonly contained by all fingerprint points in the same class; n is a radical ofiAPRepresenting the same AP address number of the fingerprint point and the ith class;
③ determining the class attribution of the fingerprint point, if N is satisfiedIAP≥CNAPIf so, classifying the point into an I-type set, simultaneously keeping the intersection of the point and an original I-type address set, updating the I-type address set to be used as a comparison basis of the access point address of the next fingerprint point; otherwise, the point is used as the clustering starting point of the next new class; CNAPThe number of the same access points AP in the same class is the clustering parameter;
and fourthly, repeating the steps II and III until all the points are classified.
5. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 3, a class center of each fingerprint database class is calculated, wherein the class center comprises a class center signal strength vector and a class address vector corresponding to the class center signal strength vector; the quasi-center signal strength vector includes the mean and standard deviation of the signal strength, and the calculation formula is as follows:
in the formula (I), the compound is shown in the specification,
representing the field intensity values of n APs in the class acquired by the fingerprint points i in the m classes;
and σmIs a class m mean and standard deviation vector of class-like center signal strengths, wherein
σm＝{σ1,m,σ2,m,…,σn,m} (5)
n is the number of identical Mac addresses in class m, DmThe number of dots included in the m-th class is referred to.
6. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 4, rough matching is performed by using real-time received signal Access Point (AP) address information and an address vector of a fingerprint library class center to determine a rough class range; the coarse matching method adopts a double-layer filtering technology, and gradually reduces the search space through two times of continuous filtering, wherein the two times of filtering are as follows in sequence:
the method comprises the steps of firstly, filtering, namely filtering by using an AP address corresponding to the RSSI (received signal strength indication) with the maximum signal strength received by a positioning target in real time to obtain a search space;
and a second step of filtering, namely filtering the upper search result by using the access point AP address corresponding to the first N RSSI maximum signal strengths received by the positioning target in real time.
7. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 5, the distance between the WIFI signal strength value and the WIFI signal strength center vector of each fingerprint database is used for accurately determining the class of the WIFI address and field strength based rough and fine matching positioning method to enhance class matching accuracy, and the method comprises the following steps:
step one, judging the occurrence frequency of the maximum matching rate based on the WIFI address, and if the occurrence frequency is 1, assigning a corresponding class serial number to a final determined class; otherwise, the second step of fine matching based on the signal characteristics is carried out;
second step, according to the same access pointCalculating the relationship between the distance from the real-time received signal vector to each type of central vector and the probability of the real-time received signal vector according to the formulas (6) to (7); namely, when a user receives the WIFI signal intensity s in real time, relevant preprocessing is carried out on s, and then s and various centers are calculated
The distance between:
and modeling the signal intensity distribution of the class set by using a Gaussian model, wherein the probability density function is as follows:
selecting through a formula 8, assigning the class serial number with a relatively small signal vector distance and a relatively large probability to the final determination class:
cm＝pm(s)/dm(8)
is selected cmThe class with the largest value is used as a matching target, and the whole fingerprint database does not need to be searched one by one.
8. The WIFI address and field strength based rough and fine matching positioning method according to claim 1, wherein in step 6, a weighted nearest neighbor method KWNN is applied to the precisely determined class set to achieve final position calculation.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010498251.2A CN111669702A (en) | 2020-06-04 | 2020-06-04 | Coarse and fine matching positioning method based on WIFI address and field intensity |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010498251.2A CN111669702A (en) | 2020-06-04 | 2020-06-04 | Coarse and fine matching positioning method based on WIFI address and field intensity |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN111669702A true CN111669702A (en) | 2020-09-15 |
Family
ID=72385990
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010498251.2A Withdrawn CN111669702A (en) | 2020-06-04 | 2020-06-04 | Coarse and fine matching positioning method based on WIFI address and field intensity |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111669702A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111935820A (en) * | 2020-09-24 | 2020-11-13 | 腾讯科技（深圳）有限公司 | Positioning implementation method based on wireless network and related equipment |
| CN114845388A (en) * | 2022-05-17 | 2022-08-02 | 电子科技大学 | Indoor positioning method for position fingerprint of sub-direction entropy weighting WKNN |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105044662A (en) * | 2015-05-27 | 2015-11-11 | 南京邮电大学 | Fingerprint clustering multi-point joint indoor positioning method based on WIFI signal intensity |
| CN107333238A (en) * | 2017-07-03 | 2017-11-07 | 杭州电子科技大学 | A kind of indoor fingerprint method for rapidly positioning based on support vector regression |
| CN110519692A (en) * | 2019-09-12 | 2019-11-29 | 中南大学 | Positioning partition method based on Bayes's-k mean cluster |
-
2020
- 2020-06-04 CN CN202010498251.2A patent/CN111669702A/en not_active Withdrawn
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105044662A (en) * | 2015-05-27 | 2015-11-11 | 南京邮电大学 | Fingerprint clustering multi-point joint indoor positioning method based on WIFI signal intensity |
| CN107333238A (en) * | 2017-07-03 | 2017-11-07 | 杭州电子科技大学 | A kind of indoor fingerprint method for rapidly positioning based on support vector regression |
| CN110519692A (en) * | 2019-09-12 | 2019-11-29 | 中南大学 | Positioning partition method based on Bayes's-k mean cluster |
Non-Patent Citations (1)
| Title |
|---|
| 刘春燕: "基于WIFI与惯性技术的行人室内定位算法研究", 《中国优秀硕士学位论文全文数据库信息科技辑》 * |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111935820A (en) * | 2020-09-24 | 2020-11-13 | 腾讯科技（深圳）有限公司 | Positioning implementation method based on wireless network and related equipment |
| CN114845388A (en) * | 2022-05-17 | 2022-08-02 | 电子科技大学 | Indoor positioning method for position fingerprint of sub-direction entropy weighting WKNN |
| CN114845388B (en) * | 2022-05-17 | 2023-02-28 | 电子科技大学 | Indoor positioning method for position fingerprint of sub-direction entropy weighting WKNN |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110012428B (en) | Indoor positioning method based on WiFi | |
| CN107948930B (en) | Indoor positioning optimization method based on position fingerprint algorithm | |
| CN104703143B (en) | A kind of indoor orientation method based on WIFI signal intensity | |
| CN112887902B (en) | Indoor positioning method of WiFi fingerprint based on Gaussian clustering and hybrid measurement | |
| CN108802722B (en) | It is a kind of based on tracking before the Faint target detection virtually composed | |
| CN109951807A (en) | Fusion RSS and CSI indoor orientation method based on WiFi signal | |
| CN106851571B (en) | Decision tree-based rapid KNN indoor WiFi positioning method | |
| CN112135248B (en) | WIFI fingerprint positioning method based on K-means optimal estimation | |
| CN105491661B (en) | Indoor locating system and method based on improved Kalman filter algorithm | |
| CN106851573A (en) | Joint weighting k nearest neighbor indoor orientation method based on log path loss model | |
| CN110049549B (en) | WiFi fingerprint-based multi-fusion indoor positioning method and system | |
| CN104581644B (en) | Indoor WLAN fingerprint databases multiple spot adaptive updates method based on radial base interpolation | |
| CN102695272B (en) | Matching location method and mobile terminal | |
| CN109348416B (en) | Fingerprint indoor positioning method based on binary k-means | |
| CN107677989B (en) | A kind of indoor location localization method carrying out RSSI removal noise based on RSSI maximum value | |
| CN108924756A (en) | Indoor orientation method based on WiFi double frequency-band | |
| CN111669702A (en) | Coarse and fine matching positioning method based on WIFI address and field intensity | |
| CN108445443B (en) | KNN-based fingerprint point clustering method | |
| CN108521631B (en) | Mobile AP (access point) identification method for indoor positioning | |
| CN111757257B (en) | Dynamic fuzzy matching indoor positioning method for overcoming equipment difference | |
| CN109600711B (en) | Indoor positioning method based on channel response frequency domain and spatial domain combined processing | |
| CN108519579B (en) | WiFi fingerprint positioning method for analyzing optimal AP based on interval overlapping degree | |
| CN114679683B (en) | Indoor intelligent positioning method based on derived fingerprint migration | |
| CN108761385A (en) | A kind of indoor location localization method carrying out fingerprint point cluster based on AP virtual coordinates | |
| Park et al. | A parallel artificial neural network learning scheme based on radio wave fingerprint for indoor localization |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WW01 | Invention patent application withdrawn after publication | ||
| WW01 | Invention patent application withdrawn after publication |
Application publication date: 20200915 |