CN110602651B - Positioning method based on WIFI position fingerprint and positioning system of robot - Google Patents

Abstract

The invention discloses a positioning method based on WIFI position fingerprints and a positioning system of a robot, wherein the positioning method based on the WIFI position fingerprints comprises the following steps: acquiring WIFI position fingerprint data of an object to be positioned at each position of a region to be detected so as to establish a WIFI position fingerprint database, and classifying the data of the WIFI position fingerprint database by adopting a K-means clustering and dividing method so as to divide the data into K classes; the RSSI value of each wireless access point received by the object to be positioned at the current position is obtained, the RSSI values of some wireless access points with poor signal strength are removed, Euclidean distances between sampling data formed by the rest RSSI values and K classes are calculated, and a weighted K nearest neighbor method is adopted to carry out matching positioning in the class with the minimum Euclidean distance value, so that the positioning result of the object to be positioned is obtained. The positioning method based on the WIFI position fingerprint and the positioning system of the robot can improve the operation efficiency and the positioning accuracy.

Description

Positioning method based on WIFI location fingerprint and robot positioning system

technical field

The present invention relates to the field of communication technology, in particular to a positioning method based on a WIFI location fingerprint and a positioning system for a robot.

Background technique

Wireless positioning, as the name implies, uses various types of signals received to determine the geographic location of the positioning terminal.

GPS (Global Positioning System) and my country's Beidou navigation system have achieved high-precision positioning in a relatively spacious area. There are also some positioning methods in indoor scenarios, such as infrared positioning, ultrasonic positioning, Bluetooth positioning, and WIFI-based fingerprint information positioning. These methods have their own advantages and disadvantages. At present, with the rapid development of the Internet and mobile communication, a large number of WIFI nodes are arranged in many occasions, and mobile terminals generally have their own WIFI modules, which makes the research on the positioning method based on WIFI fingerprint information have been well developed.

The WIFI-based fingerprint positioning technology mainly uses the correlation between spatial information and the RSSI (Received Signal Strength Indication) of the wireless signal to match the WIFI wireless information collected at the location to be measured with the geographic location information. In the actual positioning environment, the RSSI values of the n wireless access points received by the point to be measured are formed into a set of n-dimensional vectors and the two-dimensional geographic location to form a one-by-one mapping relationship. Different n-dimensional RSSI vectors correspond to different Then, these n-dimensional RSSI vectors are aggregated to form a fingerprint database, and each group of data in the database is called a location fingerprint. Finally, according to the change of RSSI signal strength of the collected wireless access point, a set of RSSI values measured at that time can be used to upload to the positioning server, and by matching with the location fingerprints of the fingerprint database, the location fingerprint with the best similarity can be selected. The corresponding geographic location serves as the estimated location.

The current positioning algorithm based on WIFI fingerprint includes two stages, offline training stage and real-time positioning stage. The main work of the offline training phase is that the staff selects the positions of several reference points in the area to be tested, and simultaneously collects multiple signal strength values from different wireless access points at each reference point, and then compares each reference point. The received RSSI value of each wireless access point, the MAC address and the geographic location information of the reference point form a set of associated triple data groups and are stored in the database, where each group of data in the database is a location fingerprint . In the real-time positioning stage, the user collects the WIFI information of all wireless access points in the positioning area through the terminal device, and forms a two-tuple with the MAC address and RSSI value of the wireless access point as the input content of the fingerprint positioning algorithm. , by comparing one by one, find the closest entry, and then use the geographical coordinates corresponding to the closest group or groups of location fingerprints to perform related calculations, and then estimate the location of the point to be measured.

After researching the current positioning algorithm based on WIFI fingerprints, the inventor found that it has the following problems: in the online positioning stage, when the fingerprint database is small, the comparison can be quickly matched one by one, but with the large amount of data in the fingerprint database. , this operation will consume a lot of time, thus affecting the efficiency of positioning, and will also generate a large number of repeated operations on the positioning server. Therefore, it is also a very big challenge to improve the fingerprint matching algorithm, improve the positioning real-time performance of the positioning system, and reduce the power consumption of the server under the condition of ensuring the positioning accuracy.

The information disclosed in this Background section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person of ordinary skill in the art.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a positioning method based on a WIFI location fingerprint and a positioning system of a robot, which can improve the computing efficiency, provide the positioning real-time performance of the positioning system and reduce the power consumption of the server.

In order to achieve the above object, the present invention provides a positioning method based on WIFI location fingerprints. The object to be located is provided with a WIFI module, and the object to be located establishes communication with multiple wireless access points through the WIFI module. The WIFI module can detect the received RSSI value of each wireless access point, and the positioning method based on the WIFI location fingerprint includes:

Acquire the WIFI location fingerprint data of each position of the object to be located in the area to be measured and store it in a pre-established WIFI location fingerprint database;

The data of the WIFI location fingerprint database is classified into K classes by using the K-means clustering method;

Obtain the RSSI value of each wireless access point received by the object to be located at the current position, remove the RSSI value of the wireless access point whose signal strength is less than the preset threshold, and calculate the remaining sample data composed of each RSSI value For the Euclidean distances from the K classes, in the class with the smallest Euclidean distance value, the weighted K-nearest neighbor method is used to perform matching and positioning to obtain the positioning result of the object to be located.

In an embodiment of the present invention, acquiring the WIFI location fingerprint data of the object to be located at a certain location includes:

sampling the RSSI value of each wireless access point received by the object to be positioned at the position;

Combine the sampling data and filter out a part of the wireless access points based on the stability and signal quality of the wireless access points;

Gaussian filtering is performed on the RSSI value array of each wireless access point in the selected part, and an average value is obtained for the filtered RSSI value array of each wireless access point, and the average value is composed of The collection is stored as the WIFI location fingerprint data of the location.

In an embodiment of the present invention, the combining the sampled data and filtering out a part of the wireless access points with the stability and signal quality of the wireless access points as selection factors includes: calculating each wireless access point in the sampled data The frequency of occurrence of the sampling data of the access point, the frequency values are arranged in descending order, and the Q wireless access points corresponding to the first Q frequency values are formed into the first wireless access point set; The average value of the sampled data of the wireless access points, the average values are arranged in descending order, and the Q wireless access points corresponding to the first Q average values are formed into a second wireless access point set; calculate the sampling The standard deviation of the sampled data of each wireless access point in the data, the standard deviation values are arranged in ascending order, and the Q wireless access points corresponding to the first Q standard deviation values are formed into a third wireless access point set ; Find an intersection for the first set of wireless access points, the second set of wireless access points and the third set of wireless access points, and select the part of the stability and signal in the intersection set Wireless access points with better quality.

The present invention also provides a positioning system for a robot, which includes a robot, a robot controller and a server. The robot has a WIFI module, the robot accesses multiple wireless access points through the WIFI module, and the WIFI module can detect the received RSSI value of each wireless access point. The robot controller communicates with the plurality of wireless access points, and is configured to receive the RSSI value of each wireless access point detected by the WIFI module. The server communicates with the robot controller, and the server includes: a WIFI location fingerprint database establishment module, a clustering module and a positioning module, and the WIFI location fingerprint database establishment module is used to obtain each position of the robot in the area to be measured The WIFI location fingerprint data is stored in the pre-established WIFI location fingerprint database; the clustering module is coupled with the WIFI location fingerprint database establishment module, and is used to use the K-means clustering method to classify the WIFI location fingerprint database. The data is classified to be divided into K categories; the positioning module is coupled with the clustering module, and is used to obtain each wireless access detected by the WIFI module at the current position of the robot when positioning the robot. RSSI data of the access point, and remove the RSSI value of the wireless access point whose signal strength is less than the preset threshold, calculate the Euclidean distance between the sampled data composed of each remaining RSSI value and the K classes, in the Euclidean In the class with the smallest distance value, the weighted K-nearest neighbor method is used for matching and positioning to obtain the positioning result of the robot.

In an embodiment of the present invention, the WIFI location fingerprint database establishment module includes: a sampling module, a wireless access point selection module, and a WIFI location fingerprint data generation module.

The sampling module is used to sample the RSSI value of each wireless access point received by the robot at a certain position;

A wireless access point selection module, coupled with the sampling module, used for combining the sampling data of the sampling module and screening out a part of the wireless access points with the stability and signal quality of the wireless access points as selection factors ;

The WIFI location fingerprint data generation module, coupled with the wireless access point selection module, is used to perform Gaussian filtering on the RSSI value array of each wireless access point selected by the wireless access point selection module , and calculate the average value of the filtered RSSI value array of each wireless access point, and store the set formed by the average value as the WIFI location fingerprint data of the location.

In an embodiment of the present invention, the wireless access point selection module includes: a first wireless access point selection module, a second wireless access point selection module, a third wireless access point selection module, and Intersection seeking module. The first wireless access point selection module is used to calculate the frequency of occurrence of the sampled data of each wireless access point in the sampled data of the sampling module, arrange each frequency value in descending order, and select the corresponding frequency values of the first Q frequency values. The Q wireless access points form a first wireless access point set. The second wireless access point selection module is configured to calculate the average value of the sampled data of each wireless access point in the sampled data, arrange the average values in descending order, and select the Q wireless access points corresponding to the first Q average values. The access points form a second set of wireless access points. The third wireless access point selection module is configured to calculate the standard deviation of the sampled data of each wireless access point in the sampled data, arrange the standard deviation values in ascending order, and select the Q corresponding to the first Q standard deviation values. The wireless access points form a third wireless access point set. The intersection obtaining module is coupled with the first wireless access point selection module, the second wireless access point selection module, and the third wireless access point selection module, and is used for the first wireless access point selection module. An intersection of a set of wireless access points, the second set of wireless access points, and the third set of wireless access points is obtained, and the part is selected from the intersection with good stability and signal quality wireless access point.

In an embodiment of the present invention, the server further includes a positioning correction module. The positioning correction module is coupled with the positioning module and the robot controller, and the robot controller is also used to obtain the rotational speed of the robot motor; the positioning correction module is used to calculate the position of the previous positioning and the position of the current positioning. The first distance between the positions; it is also used to calculate the second distance moved by the robot in the process from the previous positioning to the current positioning according to the rotational speed of the robot motor; it is also used to compare the first distance and the second distance , if the difference between the two is greater than the threshold, it is determined that the positioning result is incorrect, and a message is sent to the robot controller to re-detect the data, otherwise it is determined that the positioning result is correct and the positioning result is sent to the robot controller .

The present invention also provides a server for locating objects based on WIFI location fingerprints, the server comprising:

The WIFI location fingerprint database establishment module is used to obtain the WIFI location fingerprint data of each position of the object to be located in the to-be-measured area and store it in the pre-established WIFI location fingerprint database;

A clustering module, coupled with the WIFI location fingerprint database establishment module, is used for classifying the data of the WIFI location fingerprint database by adopting the K-means clustering division method so as to be divided into K classes;

The positioning module, coupled with the clustering module, is used to obtain the RSSI data of each wireless access point of the current position of the object to be located when positioning the object to be located, and remove the signal strength less than The RSSI value of the wireless access point with the threshold value, calculate the Euclidean distance between the sampled data composed of each remaining RSSI value and the K classes, and use the weighted K-nearest neighbor method for matching and positioning in the class with the smallest Euclidean distance value. Obtain the positioning result of the object to be positioned.

In an embodiment of the present invention, the WIFI location fingerprint database establishment module includes:

a sampling module, configured to sample the RSSI value of each wireless access point received by the object to be located at a certain position;

A wireless access point selection module, coupled with the sampling module, used for combining the sampling data of the sampling module and screening out a part of the wireless access points with the stability and signal quality of the wireless access points as selection factors ;

The WIFI location fingerprint data generation module, coupled with the wireless access point selection module, is used to perform Gaussian filtering on the RSSI value array of each wireless access point selected by the wireless access point selection module , and calculate the average value of the filtered RSSI value array of each wireless access point, and store the set formed by the average value as the WIFI location fingerprint data of the location.

In an embodiment of the present invention, the wireless access point selection module includes:

The first wireless access point selection module is used to calculate the frequency of occurrence of the sampled data of each wireless access point in the sampled data of the sampling module, arrange each frequency value in descending order, and set the corresponding frequency values of the first Q The Q wireless access points form the first wireless access point set;

The second wireless access point selection module is configured to calculate the average value of the sampled data of each wireless access point in the sampled data, arrange the average values in descending order, and select the Q corresponding to the first Q average values. The wireless access points form a second wireless access point set;

The third wireless access point selection module is configured to calculate the standard deviation of the sampled data of each wireless access point in the sampled data, arrange each standard deviation value in ascending order, and select the corresponding standard deviation values of the first Q The Q wireless access points form a third wireless access point set;

The intersection obtaining module is coupled with the first wireless access point selection module, the second wireless access point selection module, and the third wireless access point selection module, and is used for the An intersection of the first wireless access point set, the second wireless access point set, and the third wireless access point set is obtained, and the part of the wireless access points is selected from the intersection.

Compared with the prior art, according to the positioning method based on WIFI location fingerprint, the positioning system and the server of the robot of the present invention, the K-means clustering algorithm is used to classify the fingerprint data, and in the positioning stage, the data matching speed can be effectively accelerated. , which can effectively improve computing efficiency, reduce server power consumption, and improve positioning real-time performance.

Description of drawings

FIG. 1 is a step composition of a positioning method based on a WIFI location fingerprint according to an embodiment of the present invention;

Fig. 2 is the step composition of the K-means clustering method according to an embodiment of the present invention;

3 is a schematic diagram of a network topology of a positioning system of a robot according to an embodiment of the present invention;

FIG. 4 is a structural composition of a positioning system of a robot according to an embodiment of the present invention.

Detailed ways

The specific embodiments of the present invention will be described in detail below with reference to the accompanying drawings, but it should be understood that the protection scope of the present invention is not limited by the specific embodiments.

Unless expressly stated otherwise, throughout the specification and claims, the term "comprising" or its conjugations such as "comprising" or "comprising" and the like will be understood to include the stated elements or components, and Other elements or other components are not excluded.

In order to overcome the problems in the prior art, the present invention provides a positioning method based on a WIFI location fingerprint, a positioning system and a server for a robot. In the process of establishing the WIFI location fingerprint database, the received signal information is preprocessed, It mainly includes the selection of wireless access points and the smoothing of RSSI signals. The K-means clustering algorithm is used to classify the fingerprint data. In the positioning stage, it can effectively speed up the data matching speed, effectively improve the computing efficiency and reduce the server power. It can improve the real-time performance and positioning accuracy of positioning.

Example 1

FIG. 1 is a flowchart of a positioning method based on a WIFI location fingerprint according to an embodiment of the present invention. The object to be located is provided with a WIFI module, the object to be located establishes communication with multiple wireless access points through the WIFI module, and the WIFI module can detect the received RSSI value of each wireless access point. The positioning method based on the WIFI location fingerprint includes steps S1 to S3.

In step S1, the WIFI location fingerprint data of each position of the object to be located in the area to be measured is acquired to establish a WIFI location fingerprint database. Specifically, acquiring the WIFI location fingerprint data of the object to be located at a certain location includes: sampling the RSSI value of each wireless access point received by the object to be located at the location, and sampling multiple times at the location; combining sampling A part of the wireless access points with better stability and signal quality is selected from the data; Gaussian filtering is performed on the RSSI value array of each wireless access point in the selected part to remove some RSSI values, and each RSSI value is removed. The average value of the filtered RSSI value array of each wireless access point is obtained, and the set consisting of the obtained average value of each wireless access point is stored as the WIFI location fingerprint data of the location.

Wherein, selecting a part of the wireless access points with better stability and signal quality in combination with the sampled data includes calculating the frequency of occurrence of the sampled data of each wireless access point in the sampled data, arranging the respective frequency values in descending order, The K wireless access points corresponding to the K frequency values form the first wireless access point set; calculate the average value of the sampled data of each wireless access point in the sampled data, arrange the average values in descending order, and set the The K wireless access points corresponding to the first K average values form the second wireless access point set; calculate the standard deviation of the sampled data of each wireless access point in the sampled data, and arrange each standard deviation value in ascending order , the K wireless access points corresponding to the first K standard deviation values are formed into a third wireless access point set; for the first wireless access point set, the second wireless access point set and the third wireless access point set Access the set of access points to find the intersection. A part of the wireless access points with better stability and signal quality are selected from each wireless access point in the above-mentioned intersection set according to the actual situation.

Specifically, in the area to be tested, suppose the sampling point L receives a set of n wireless access points, which can be expressed as {AP ₁ , AP ₂ ,...AP _n }, and then perform M times at this point. Sampling, consider the frequency of each wireless access point in the entire sampling sample, as shown in Equation 1:

In Equation 1, M(AP _i ) represents the number of samples in which the wireless access point AP _i appears in the sampling, and M represents the total number of samples in the sampling. Then, the Fre(AP _i ) is sorted in descending order, and the first Q wireless access points are selected as the selection result, which is denoted as Q ₁ .

And considering the signal strength of the wireless access points in the sample, the average value of the M times of measured signal strengths of each wireless access point is calculated, as shown in Equation 2:

可以表示该无线访问接入点的信号质量，对采样点L的N个无线访问接入点按照

降序排列，选择前Q个作为选择结果，表示为Q₂。In Equation 2, RSSI _i represents the i-th measurement value of a certain wireless access point.

It can represent the signal quality of the wireless access point. For the N wireless access points of the sampling point L, according to

Sort in descending order, and select the top Q as the selection result, denoted as Q ₂ .

At the same time, the standard deviation should also be considered. After M sampling at the sampling point L, the wireless access point AP ₁ receives M ₁ sets of sampling samples, and the data is {RSSI ₁ , RSSI ₂ ,..., RSSI _m1 }, then the wireless access point AP 1 The standard deviation of the fluctuation of the access point, as shown in Equation 3.

表示M₁次采样样本的平均值。标准差σ可以反映出该无线访问接入点的波动幅度，对采样点L的N个无线访问接入点按照标准差σ进行升序排列，同样选择前Q个无线访问接入点作为选择结果，表示为Q₃。In Equation 3,

Represents the average value of M ₁ sampling samples. The standard deviation σ can reflect the fluctuation range of the wireless access point. The N wireless access points of the sampling point L are arranged in ascending order according to the standard deviation σ, and the first Q wireless access points are also selected as the selection result. Denoted as Q ₃ .

The intersection of Q ₁ , Q ₂ , and Q ₃ obtained above is obtained, as shown in Equation 4.

Q=Q ₁ ∩Q ₂ ∩Q ₂ (4)

Usually, the point to be tested can receive RSSI samples of more than 5 wireless access points, which can achieve good positioning accuracy. The Q value can be set to be greater than 5 according to the number of wireless access points in the actual environment to be tested. If the number of received wireless access points is relatively small, the above scheme is selectively adopted according to the actual situation.

For the selected wireless access point, due to the flow of people and the occlusion of objects during the measurement, some small probability values inevitably appear. In order to improve the accuracy of the final positioning result, this embodiment uses a Gaussian filter model to exclude these low probability values, and performs Gaussian filtering on the selected RSSI value array of each wireless access point in this part to remove some RSSIs value, and averages the filtered array of RSSI values for each AP.

The specific algorithm is as follows: First, suppose that {RSSI ₁ , RSSI ₂ ,...,RSSI _n } is used to represent the n sampling values from a wireless access point at a sample point, then these RSSI values can be represented by a normal model, As shown in Equation 5.

in:

In Equation 5, x represents the RSSI signal strength value.

Then take the value of RSSI between u-3σ<x≤u+3σ, remove the value outside the range, and save it as {RSSI ₁ ,RSSI ₂ ,...,RSSI _n1 }.

Finally, the average value of the selected RSSI values is obtained according to formula 8, and the average value is the calculated RSSI signal strength value R of the sample point from the wireless access point.

In Equation 8, n ₁ represents the total number of filtered samples.

In step S2, the K-means clustering method is used to classify the WIFI location fingerprint database so as to be divided into K classes.

Specifically, as shown in FIG. 2 , the K-means clustering method includes steps S20 to S24 .

The WIFI location fingerprint dataset X={x ₁ , x ₂ ,...,x _n } is used as input, which contains N data objects, the number of cluster centers is K, and the clustering criterion threshold is ε. The dataset divided into K clusters is set as output.

In step S20, K cluster centers M={m ₁ ⁽¹⁾ , m ₂ ⁽¹⁾ , . . . m _K ⁽¹⁾ } are arbitrarily selected from the data set X.

In step S21, calculate the Euclidean distance from each remaining data x _i (i=1,2,...,NK) to the K cluster centers M, denoted by D(i,r), and n is the positioning area The number of all wireless access points in the network, _xi (RSSI _j ) represents the signal strength value of the jth wireless access point received by the ith data object, m _r ⁽¹⁾ (RSSI _j ) represents the th The r cluster centers receive the signal strength value of the jth wireless access point. If the data object x _i does not receive the signal of the jth wireless access point, it is replaced by an infinitely small value, then The algorithm of D(i,r) adopts Equation 9.

In step S22, _xi is assigned to the cluster center with the shortest Euclidean distance.

In step S23, the average value of all objects in each class is calculated and used as the new cluster center point, as shown in Equation 10.

Wherein, in Equation 10, C _r represents the data contained in the j-th type, and N _r represents the number of the j-th type of data.

In step S24, the above three steps are repeated, and the remaining _xi are classified one by one. When the cluster center does not change or the fluctuation of m _r ^(p) is less than the given threshold, the center of K classes is output, and the algorithm ends.

In step S3, the weighted K-nearest neighbor method is used for matching and positioning. Specifically, obtain the RSSI value of each wireless access point received by the object to be located at the current position, remove the RSSI value of some wireless access points with poor signal strength, and calculate the remaining sampled data composed of each RSSI value For the Euclidean distance from K classes, in the class with the smallest Euclidean distance value, the weighted K-nearest neighbor method is used to perform matching and positioning to obtain the positioning result of the object to be located.

Example 2

Based on the same inventive concept, the present invention also provides a positioning system for a robot, which will be described below.

FIG. 3 is a schematic diagram of the network topology of the positioning system of the robot. 4 is a configuration diagram of a positioning system of a robot according to an embodiment. It includes: a robot 1 , a robot controller 2 , and a server 3 .

The robot 1 has a WIFI module 10, and the robot 1 accesses multiple wireless access points through the WIFI module 10, and the WIFI module 10 can detect the received RSSI value of each wireless access point. The robot 1 also has a camera 11, a microcontroller 12, a motor 13, and the like. The robot controller 2 communicates with a plurality of wireless access points for receiving the RSSI value of each wireless access point detected by the WIFI module 10 . Optionally, an OpenWrt router 10a is set in the WIFI module 10 of the robot 1, and data interaction with the robot controller 2 can be performed through the OpenWrt router 10a. For example, running video service software on the OpenWrt router 10a can capture the camera 11 of the robot 1. , and the video from robot 1 can be seen on the robot control terminal 2. The serial port and the network port can also be converted through the OpenWrt router 10a, the control data of the robot control terminal 2 can be sent to the microcontroller 12 of the robot 1, and the microcontroller 12 sends commands to control the motor 13 of the robot 1 to act.

The server 3 communicates with the robot controller 2 . The server 3 includes: a WIFI location fingerprint database establishment module 31 , a clustering module 32 and a positioning module 33 .

The WIFI location fingerprint database establishment module 31 is used to acquire the WIFI location fingerprint data of each position of the robot 1 in the area to be measured, so as to establish a WIFI location fingerprint database.

Specifically, the WIFI location fingerprint database establishment module 31 includes: a sampling module 311 , a wireless access point selection module 312 , and a WIFI location fingerprint data generation module 313 . The sampling module 311 is configured to sample the RSSI value of each wireless access point received by the robot at a certain position, and sample the position for multiple times. The wireless access point selecting module 312 is coupled with the sampling module 311, and is used for selecting a part of wireless access points with better stability and signal quality in combination with the sampling data of the sampling module 311. The WIFI location fingerprint data generation module 313 is coupled with the wireless access point selection module 312, and is used to perform Gaussian filtering on the RSSI value array of each wireless access point selected by the wireless access point selection module 312 to remove the Some RSSI values, and the average value of the filtered RSSI value array of each wireless access point is calculated, and the set consisting of the average value of each wireless access point is used as the WIFI location fingerprint data of the location. to store.

The wireless access point selection module 312 includes: a first wireless access point selection module 312a, a second wireless access point selection module 312b, a third wireless access point selection module 312c, and an intersection obtaining module 312d .

The first wireless access point selection module 312a is used to calculate the frequency of occurrence of the sampled data of each wireless access point in the sampled data of the sampling module, arrange each frequency value in descending order, and select the K corresponding to the first K frequency values. The wireless access points form a first set of wireless access points. The second wireless access point selection module 312b is configured to calculate the average value of the sampled data of each wireless access point in the sampled data, arrange the average values in descending order, and select the K wireless access points corresponding to the first K average values The access points form a second set of wireless access access points. The third wireless access point selection module 312c is configured to calculate the standard deviation of the sampled data of each wireless access point in the sampled data, arrange the standard deviation values in ascending order, and select the K corresponding to the first K standard deviation values. The wireless access points form a third set of wireless access points. The intersection obtaining module 312d is configured to obtain an intersection for the first wireless access point set 312a, the second wireless access point set 312b, and the third wireless access point set 312c, wherein each wireless access point in the intersection set is an intersection. The access point is a selected part of the wireless access points with better stability and signal quality.

The clustering module 32 is coupled with the WIFI location fingerprint database establishment module 31, and is used for classifying the WIFI location fingerprint database into K classes by adopting the K-means clustering method.

The positioning module 33 is coupled with the clustering module 32, and is used to obtain the RSSI data of each wireless access point detected by the WIFI module 10 at the current position of the robot 1 when positioning the robot, and remove some poor signal strengths from it. The RSSI value of the wireless access point is used to calculate the Euclidean distance between the sampled data composed of each remaining RSSI value and the K classes. In the class with the smallest Euclidean distance value, the weighted K-nearest neighbor method is used for matching and positioning to obtain the positioning result of the robot.

In this embodiment, in order to further improve the positioning accuracy, a positioning correction module 34 is also set in the server 3 . It is coupled with the positioning module 33 and the robot controller 2 , and the robot controller 2 is also used to obtain the rotational speed of the robot motor 13 . The positioning correction module 34 is used to calculate the first distance between the position of the previous positioning and the position of this positioning; it is also used to calculate the movement of the robot 1 in the process from the previous positioning to the current positioning according to the rotational speed of the robot motor 13 The second distance of , where the time of this process can be calculated by a timer; it is also used to compare the first distance and the second distance, if the difference between the two is greater than the threshold, it is determined that the positioning result is incorrect this time, and a message is sent to the robot controller 2 to re-detect the data, otherwise it is determined that the positioning result is correct and the positioning result is sent to the robot controller 2 . The robot controller 2 can be displayed through the interface.

To sum up, according to the positioning method based on the WIFI location fingerprint and the positioning system of the robot in this embodiment, in the stage of establishing the WIFI location fingerprint database, the stability and signal quality of the wireless access point are double considered to select the appropriate location. It improves the accuracy and avoids invalid wireless access points; Gaussian filtering is performed on the RSSI value, which makes the value significantly smoother, and the cluttered data with small probability is removed; and K The mean clustering algorithm classifies the fingerprint data, which can speed up the matching speed and improve the real-time positioning in the data matching process in the subsequent positioning stage; in addition, the positioning results are corrected in the positioning system of the robot, which further improves the positioning results. accuracy.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present application. It will be understood that each flow and/or block in the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flow of the flowcharts and/or the block or blocks of the block diagrams.

These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

The foregoing descriptions of specific exemplary embodiments of the present invention have been presented for purposes of illustration and description. These descriptions are not intended to limit the invention to the precise form disclosed, and obviously many changes and modifications are possible in light of the above teachings. The exemplary embodiments were chosen and described for the purpose of explaining certain principles of the invention and their practical applications, to thereby enable one skilled in the art to make and utilize various exemplary embodiments and various different aspects of the invention. Choose and change. The scope of the invention is intended to be defined by the claims and their equivalents.

Claims (4)

1. The positioning method based on the WIFI position fingerprint is characterized in that an object to be positioned is provided with a WIFI module, the object to be positioned is communicated with a plurality of wireless access points through the WIFI module, and the WIFI module can detect the received RSSI value of each wireless access point, and the positioning method based on the WIFI position fingerprint comprises the following steps:

acquiring WIFI position fingerprint data of each position of the object to be positioned in the area to be detected and storing the WIFI position fingerprint data into a pre-established WIFI position fingerprint database;

classifying the data of the WIFI position fingerprint database by adopting a K-means clustering division method so as to divide the data into K classes; and

obtaining the RSSI value of each wireless access point received by the object to be positioned at the current position, removing the RSSI value of the wireless access point with the signal strength smaller than a preset threshold value from the RSSI value, calculating Euclidean distances between sampling data formed by the rest of RSSI values and the K classes, and performing matching positioning by adopting a weighted K nearest neighbor method in the class with the minimum Euclidean distance value to obtain a positioning result of the object to be positioned,

wherein, obtaining the WIFI position fingerprint data of the object to be positioned at a certain position comprises:

sampling the RSSI value of each wireless access point received by the object to be positioned at the position;

screening out a part of wireless access points by combining the sampling data and taking the stability and the signal quality of the wireless access points as selection factors; and

gaussian filtering is carried out on the RSSI value array of each wireless access point of the selected part, the filtered RSSI value array of each wireless access point is averaged, a set formed by the average values is stored as the WIFI position fingerprint data of the position,

wherein the screening a portion of the wireless access points in combination with the sampled data and with stability and signal quality of the wireless access points as selection factors comprises:

calculating the occurrence frequency of the sampling data of each wireless access point in the sampling data, arranging the frequency values in a descending order, and forming a first wireless access point set by Q wireless access points corresponding to the former Q frequency values;

calculating the average value of the sampling data of each wireless access point in the sampling data, arranging the average values in a descending order, and forming a second wireless access point set by Q wireless access points corresponding to the former Q average values;

calculating the standard deviation of the sampling data of each wireless access point in the sampling data, arranging the standard deviation values in an ascending order, and forming a third wireless access point set by the Q wireless access points corresponding to the previous Q standard deviation values; and

-determining an intersection of the first set of wireless access points, the second set of wireless access points and the third set of wireless access points, and-selecting the portion of wireless access points in the intersection,

the method for classifying the data of the WIFI position fingerprint database into K classes by adopting a K-means clustering and partitioning method comprises the following steps:

the method comprises the following steps: setting WIFI position fingerprint data set X as { X ═ X₁,x₂,…,x_nUsing the data set X as an input, wherein the data set X comprises N data objects, the number of the clustering centers is K, the threshold value of the clustering criterion is epsilon, the data set divided into K clusters is set as an output, and K clustering centers M ═ M is arbitrarily selected from the data set X₁ ⁽¹⁾,m₂ ⁽¹⁾,…m_K ⁽¹⁾}；

Step two: calculate each remaining data x_i(i-1, 2, …, N-K) euclidean distances to K cluster centers M, denoted D (i, r), N being the number of all wireless access points in the location area, x_i(RSSI_j) Representing the signal strength value, m, of the jth wireless access point received by the ith data object_r ⁽¹⁾(RSSI_j) Indicating the signal strength value of the jth wireless access point received by the r cluster center if the data object x_iWhen the signal of the jth wireless access point is not received, the signal is replaced by an infinitesimal value, wherein the algorithm of D (i, r) is as follows:

step three: x is to be_iAssigning to the cluster with the shortest Euclidean distance, and calculating the average value of all objects in each cluster

And using the average value as a new cluster center point, the average value

The algorithm of (1) is as follows:

wherein, C_rIndicating data contained in class j, N_rRepresenting the number of j-th class data; and

step four: repeating the first step to the third step, and enabling the rest x_iSorting one by one, when the cluster center is not changed any more or m_r ^(p)When the fluctuation of (2) is less than a given clustering criterion threshold, the centers of the K classes are output, and the algorithm is ended.

2. A positioning system for a robot, comprising:

the robot is provided with a WIFI module, the robot is accessed to a plurality of wireless access points through the WIFI module, and the WIFI module can detect the received RSSI value of each wireless access point;

the robot controller is communicated with the wireless access points and is used for receiving the RSSI value of each wireless access point detected by the WIFI module; and

a server in communication with the robot controller, the server comprising: the robot positioning system comprises a WIFI position fingerprint database establishing module, a clustering module and a positioning module, wherein the WIFI position fingerprint database establishing module is used for acquiring WIFI position fingerprint data of each position of the robot in a region to be detected and storing the WIFI position fingerprint data into a pre-established WIFI position fingerprint database; the clustering module is coupled with the WIFI position fingerprint database establishing module and is used for classifying the data of the WIFI position fingerprint database by adopting a K-means clustering and dividing method so as to divide the data into K classes; the positioning module is coupled with the clustering module and used for acquiring RSSI data of each wireless access point detected by the WIFI module at the current position of the robot when the robot is positioned, removing RSSI values of the wireless access points of which the signal intensity is smaller than a preset threshold value from the RSSI data, calculating Euclidean distances between sampling data consisting of the rest RSSI values and the K classes, and performing matching positioning by adopting a weighted K neighbor method in the class with the minimum Euclidean distance value to acquire a positioning result of the robot,

wherein, the WIFI position fingerprint database establishing module comprises:

the sampling module is used for sampling the RSSI value of each wireless access point received by the robot at a certain position;

the wireless access point selection module is coupled with the sampling module and is used for screening out a part of wireless access points by combining the sampling data of the sampling module and taking the stability and the signal quality of the wireless access points as selection factors; and

a WIFI position fingerprint data generating module, coupled to the wireless access point selecting module, for performing Gaussian filtering on the RSSI value array of each wireless access point selected by the wireless access point selecting module, and averaging the filtered RSSI value arrays of each wireless access point, and storing the set formed by the average values as WIFI position fingerprint data of the position,

wherein, the wireless access point selecting module comprises:

the first wireless access point selection module is used for calculating the occurrence frequency of the sampling data of each wireless access point in the sampling data of the sampling module, arranging the frequency values in a descending order, and forming a first wireless access point set by the Q wireless access points corresponding to the former Q frequency values;

the second wireless access point selection module is used for calculating the average value of the sampling data of each wireless access point in the sampling data, arranging the average values in a descending order, and forming a second wireless access point set by the Q wireless access points corresponding to the former Q average values;

the third wireless access point selection module is used for calculating the standard deviation of the sampling data of each wireless access point in the sampling data, arranging the standard deviation values in an ascending order, and forming a third wireless access point set by the Q wireless access points corresponding to the previous Q standard deviation values; and

an intersection solving module, coupled to the first wireless access point selecting module, the second wireless access point selecting module, and the third wireless access point selecting module, for solving an intersection of the first wireless access point set, the second wireless access point set, and the third wireless access point set, and selecting the part of wireless access points in the intersection,

the clustering module classifies the data of the WIFI position fingerprint database into K classes by adopting a K-means clustering division method, and the classifying into the K classes comprises the following steps:

the method comprises the following steps: setting WIFI position fingerprint data set X as { X ═ X₁,x₂,…,x_nUsing the data set X as an input, wherein the data set X comprises N data objects, the number of the clustering centers is K, the threshold value of the clustering criterion is epsilon, the data set divided into K clusters is set as an output, and K clustering centers M ═ M is arbitrarily selected from the data set X₁ ⁽¹⁾,m₂ ⁽¹⁾,…m_K ⁽¹⁾}；

Step two: calculate each remaining data x_i(i-1, 2, …, N-K) euclidean distances to K cluster centers M, denoted D (i, r), N being the number of all wireless access points in the location area, x_i(RSSI_j) Representing the signal strength value, m, of the jth wireless access point received by the ith data object_r ⁽¹⁾(RSSI_j) Indicating the signal strength value of the jth wireless access point received by the r cluster center if the data object x_iWhen the signal of the jth wireless access point is not received, the signal is replaced by an infinitesimal value, wherein the algorithm of D (i, r) is as follows:

step three: x is to be_iAssigning to the cluster with the shortest Euclidean distance, and calculating the average value of all objects in each cluster

And using the average value as a new cluster center point, the average value

The algorithm of (1) is as follows:

wherein, C_rIndicating data contained in class j, N_rRepresenting the number of j-th class data; and

step four: repeating the first step to the third step, and enabling the rest x_iSorting one by one, when the cluster center is not changed any more or m_r ^(p)When the fluctuation of (2) is less than a given clustering criterion threshold, the centers of the K classes are output, and the algorithm is ended.

3. The positioning system of a robot according to claim 2, wherein said server further comprises:

the positioning correction module is coupled with the positioning module and the robot controller, and the robot controller is further used for acquiring the rotating speed of the robot motor; the positioning correction module is used for calculating a first distance between the position of the previous positioning and the position of the current positioning; the robot positioning system is also used for calculating a second distance moved by the robot in the process from the previous positioning to the current positioning according to the rotating speed of the motor of the robot; and the positioning device is also used for comparing the first distance with the second distance, if the difference between the first distance and the second distance is greater than a threshold value, judging that the current positioning result is incorrect, sending a message to the robot controller for re-detecting data, and otherwise, judging that the current positioning result is correct and sending the positioning result to the robot controller.

4. A server for locating an object based on WIFI location fingerprints, the server comprising:

the WIFI position fingerprint database establishing module is used for acquiring WIFI position fingerprint data of each position of an object to be positioned in the area to be detected and storing the WIFI position fingerprint data into a pre-established WIFI position fingerprint database;

the clustering module is coupled with the WIFI position fingerprint database establishing module and is used for classifying the data of the WIFI position fingerprint database by adopting a K-means clustering and dividing method so as to divide the data into K classes; and

a positioning module, coupled to the clustering module, configured to, when positioning the object to be positioned, obtain RSSI data of each wireless access point at the current position of the object to be positioned, remove an RSSI value of a wireless access point whose signal strength is smaller than a threshold value from the RSSI data, calculate euclidean distances between sampling data formed by remaining RSSI values and the K classes, perform matching positioning in the class with the smallest euclidean distance value by using a weighted K nearest neighbor method, thereby obtaining a positioning result of the object to be positioned,

wherein, the WIFI position fingerprint database establishing module comprises:

the sampling module is used for sampling the RSSI value of each wireless access point received by the object to be positioned at a certain position;

the wireless access point selection module is coupled with the sampling module and is used for screening out a part of wireless access points by combining the sampling data of the sampling module and taking the stability and the signal quality of the wireless access points as selection factors; and

a WIFI position fingerprint data generating module, coupled to the wireless access point selecting module, for performing Gaussian filtering on the RSSI value array of each wireless access point selected by the wireless access point selecting module, and averaging the filtered RSSI value arrays of each wireless access point, and storing the set formed by the average values as WIFI position fingerprint data of the position,

wherein, the wireless access point selecting module comprises:

the first wireless access point selection module is used for calculating the occurrence frequency of the sampling data of each wireless access point in the sampling data of the sampling module, arranging the frequency values in a descending order, and forming a first wireless access point set by the Q wireless access points corresponding to the former Q frequency values;

the second wireless access point selection module is used for calculating the average value of the sampling data of each wireless access point in the sampling data, arranging the average values in a descending order, and forming a second wireless access point set by the Q wireless access points corresponding to the former Q average values;

the third wireless access point selection module is used for calculating the standard deviation of the sampling data of each wireless access point in the sampling data, arranging the standard deviation values in an ascending order, and forming a third wireless access point set by the Q wireless access points corresponding to the previous Q standard deviation values; and

an intersection solving module, coupled to the first wireless access point selecting module, the second wireless access point selecting module, and the third wireless access point selecting module, for solving an intersection of the first wireless access point set, the second wireless access point set, and the third wireless access point set, and selecting the part of wireless access points in the intersection,

the clustering module classifies the data of the WIFI position fingerprint database into K classes by adopting a K-means clustering division method, and the classifying into the K classes comprises the following steps:

the method comprises the following steps: setting WIFI position fingerprint data set X as { X ═ X₁,x₂,…,x_nUsing the data set X as an input, wherein the data set X comprises N data objects, the number of the clustering centers is K, the threshold value of the clustering criterion is epsilon, the data set divided into K clusters is set as an output, and K clustering centers M ═ M is arbitrarily selected from the data set X₁ ⁽¹⁾,m₂ ⁽¹⁾,…m_K ⁽¹⁾}；

Step two: calculate each remaining data x_i(i-1, 2, …, N-K) euclidean distances to K cluster centers M, denoted D (i, r), N being the number of all wireless access points in the location area, x_i(RSSI_j) Representing the signal strength value, m, of the jth wireless access point received by the ith data object_r ⁽¹⁾(RSSI_j) Indicating the signal strength value of the jth wireless access point received by the r cluster center if the data object x_iWhen the signal of the jth wireless access point is not received, the signal is replaced by an infinitesimal value, wherein the algorithm of D (i, r) is as follows:

step three: x is to be_iAssigning to the cluster with the shortest Euclidean distance, and calculating the average value of all objects in each cluster

And using the average value as a new cluster center point, the average value

The algorithm of (1) is as follows:

wherein, C_rIndicating data contained in class j, N_rRepresenting the number of j-th class data; and

step four: repeating the first step to the third step, and enabling the rest x_iSorting one by one, when the cluster center is not changed any more or m_r ^(p)When the fluctuation of (2) is less than a given clustering criterion threshold, the centers of the K classes are output, and the algorithm is ended.

Images