CN104181500A - Real-time locating method based on inertia information and chance wireless signal characteristics - Google Patents

Abstract

The invention provides a real-time locating method based on inertia information and chance wireless signal characteristics. The real-time locating method based on inertia information and chance wireless signal characteristics comprises the steps that under the condition of an initial position, the motion state of a locating target is detected through a sensor of a locating terminal, and then the motion direction and the chance wireless signal characteristics of the current position are obtained; the possible position and the historical route of the locating target can be corrected through an improved particle filter method by combining inertia information and chance wireless signal characteristics, and then locating results are output in real time. According to the real-time locating method based on inertia information and chance wireless signal characteristics, in order to guarantee that the accuracy of a signal map established in real time, it is required that the locating target returns to the position where the locating target passes at one historical moment during locating, and therefore inertia drift is successively corrected. Compared with the prior art, the real-time locating method based on inertia information and chance wireless signal characteristics has the advantages that advanced exploration of the environment of the locating target is not needed, a high precision requirement can be met just through a common inertia sensor and a signal collecting unit of an ordinary intelligent terminal, implementation is successful, and the calculation amount is small.

Description

A Real-Time Positioning Method Based on Inertial Information and Characteristics of Opportunistic Wireless Signals

technical field

The invention relates to a positioning method in the field of wireless communication, in particular to a real-time positioning method based on inertial information and opportunistic wireless signal characteristics. the

Background technique

With the popularization of mobile devices and personal devices, positioning technology has become a hot research field at present and in the future. The positioning system can determine the location information of the terminal equipment, and at the same time use the location information for location-based services, such as navigation, tracking, monitoring, etc. According to the scope of use, location-based services mainly include outdoor positioning applications and indoor positioning applications. the

In the outdoor positioning system, the global positioning system (GPS) or other satellite positioning systems are usually used for positioning. The GPS system can provide outdoor personal positioning information very well. The advantage of using GPS for positioning is that the effective coverage of satellites is large, and positioning and navigation signals are free. However, GPS relies on the line-of-sight transmission of signals between satellites and receivers, and the wireless signals emitted by GPS satellites are too weak to penetrate most of the obstacles such as buildings. As a result, GPS system positioning is not effective indoors. Accurate, and the cost of positioning the terminal is relatively high. the

Since more than 70% of wireless communication services are carried out indoors, indoor positioning technology has attracted increasing attention in recent years. Indoor positioning systems are used to provide indoor location information of individuals and devices. Accuracy and calculation convergence time are considered to be the most important factors of positioning technology. Now there are many indoor positioning technologies, such as infrared indoor positioning technology, radio frequency identification technology, wireless local area network positioning technology, dead reckoning technology and so on. the

The main characteristics of these technologies are briefly listed as follows:

1) Infrared indoor positioning technology

Infrared (Infrared) is the earliest technology used for indoor positioning. The principle of infrared indoor positioning technology positioning is that the infrared IR mark emits modulated infrared rays, which are received by an optical sensor installed indoors for positioning. Although infrared rays have relatively high indoor positioning accuracy, infrared rays can only travel at a line-of-sight distance because light rays cannot pass through obstacles. The two main disadvantages of line-of-sight and short transmission distance make the indoor positioning effect very poor. When the sign is placed in a pocket or blocked by a wall, it will not work properly; and receiving antennas need to be installed in each room and corridor, which is expensive; infrared rays are easily interfered by fluorescent lamps or lights in the room, resulting in a decrease in positioning accuracy. Therefore, infrared rays are only suitable for short-distance transmission and have limitations in precise positioning. the

2) Radio Frequency Identification (RFID) technology

Radio Frequency (Radio Frequency) is also commonly used in Personal Indoor Positioning (IPS). Radio frequency identification technology uses radio frequency to conduct non-contact two-way communication and exchange data to achieve the purpose of identification and positioning. This technology has a large range of action, and can obtain centimeter-level positioning information within a few milliseconds, and because it does not depend on visible light, it has a wider range of applications. However, due to the high cost of equipment and privacy issues, and it is easily affected by metal or water environments, this positioning method has not been used on a large scale and only works in specific scenarios. the

3) Wireless local area network (WLAN) positioning technology

Wireless local area network (WLAN) is based on the 1EEE802.11 protocol. It is a computer local area network that uses wireless channels as the transmission medium. It is the product of the combination of computer networks and wireless communication technologies. The function enables users to truly realize broadband network access anytime, anywhere and at will. Mobile users have increasingly strong demands for immediacy and locality of information, which provides a broad development space for location services based on WLAN systems. The positioning technology in the WLAN system mainly includes technologies such as triangulation positioning and signal strength positioning based on RSSI (Received Signal Strength Indication) or TOA/TDOA/AOA. Among them, the signal strength positioning technology mainly includes two types of methods such as signal strength fingerprint/signal propagation model positioning. There are many well-known WLAN positioning systems, such as the RADAR system, which uses signal strength and signal-to-noise ratio signal-to-noise for triangulation positioning technology. By establishing a radio frequency channel propagation model, multiple WLAN access points (APs) can be based on the signal space ( The nearest neighbor in the NNSS) positioning algorithm is used to locate the mobile base station. The CAMPASS system provides low-cost and relatively high-precision positioning services for users carrying WLAN devices through WLAN infrastructure and digital compass. the

4) Dead Reckoning

Dead reckoning technology is a very important navigation technology. Dead Reckoning originated from navigation in the 17th century. It refers to the method of calculating the current position from a known fixed point with a compass and speed; Speed, time, and distance can calculate the current position information. Based on different physical characteristics and application environments, dead reckoning sensors can be combined with each other to achieve different configuration schemes, such as inertial navigation systems composed of gyroscopes and accelerometers, drift-free positioning methods composed of magnetometers and accelerometers, gyroscopes, magnetic Meter and accelerometer element positioning methods, etc. Dead Reckoning has high accuracy in short-distance positioning, but has the disadvantage of accumulating errors. the

Contents of the invention

As described in the background technology, in view of the deficiencies in the prior art, the purpose of the present invention is to provide a real-time positioning method based on inertial information and opportunistic wireless signal characteristics, which does not need to enter the environmental data of the navigation scene in advance; Various opportunistic wireless signals in the scene are used as the calibration basis for inertial navigation, which can solve the problem that the cumulative error caused by the use of inertial navigation system is too large and cannot be used for a long time; at the same time, because a variety of opportunistic wireless signals are used as calibration criteria, it can overcome The use of a single wireless signal as a calibration criterion in traditional methods may lead to the problem of inaccurate criteria in some special cases. the

The content of the present invention includes four main parts: input parameters, algorithm flow, core algorithm, and output parameters. the

(1) Input parameters

The input parameters of the present invention include but not limited to: inertial information, opportunistic wireless signal characteristic information, and initial position information. the

Wherein, the inertial information includes, but is not limited to: compass direction information of the positioned terminal, and motion acceleration information of the positioned terminal. Opportunistic wireless signal feature information includes any wireless signal with low time-varying high spatial correlation that can be detected by the positioning terminal, such as Wi-Fi signal, cellular base station signal, wireless broadcast TV signal, and so on. the

(2) Algorithm process

The algorithm flow is shown in Figure 1, which is mainly divided into the following steps:

1) Use reliable methods such as GPS signals or artificially designated positions as the starting position, and input the average distance of each movement of the positioning target, that is, the step size information, to initialize the positioning system;. 

2) Monitor the motion state of the positioning target through the acceleration sensor of the positioning terminal. If the positioning target moves, use the wireless signal sensor to obtain the characteristic information of the wireless signal of opportunity, and at the same time use the compass of the positioning terminal to obtain the general direction of the movement, and perform step 3) , otherwise return to step 2);

3) Use the inertial information and opportunistic wireless signal characteristics collected by the positioning terminal as the driving information of the particle filter to update the state of the particle swarm, and at the same time calculate the possible position of the current positioning target through the particle swarm and update its historical trajectory, and output the positioning result , back to step 2). the

(3) Core algorithm

The core algorithm of the present invention is the improved particle filter method, which estimates the position of the terminal by simulating a certain number of particles and updating the weight and state of the particles. The particle filter method includes the following four steps: particle initialization, particle State update, particle weight update, particle resampling. the

1) Particle initialization

Particle initialization is to take the given or measured starting position as the center of the circle, and randomly distribute a certain number of particles near the center of the circle with the probability of decreasing from near to far from the center of the circle. For each particle, the step size in the input parameter As the probability distribution center, set a random and different feature step size, and additionally set a random compass offset as the basis for particle state update. the

2) Particle status update

The particle state update process is as follows: update the current opportunistic wireless signal feature information of all particles by using the opportunistic wireless signal characteristic information measured by the positioning terminal; use the movement direction information obtained by the positioning terminal to combine the characteristic step size and characteristic compass deviation of each particle After adding a certain random zero-mean Gaussian perturbation, track inference is applied to each particle to update the particle's position information. the

The method of calculating the current position of the particle through track inference is as follows: Let the collected direction information be the angle between the direction of motion and the direction of magnetic north, set it as θ, let the characteristic step of each particle be l _i , and the characteristic compass offset is θ _i , the randomly generated step size disturbance is Δl, the compass offset disturbance is Δθ, and the coordinates of the particle’s position at the previous moment are (x, y), then after updating the state, the particle’s position (x′, y′) for: $\left\{\begin{array}{c}{x}^{\′}=x+(l_i+\mathrm{\Δl})*\cos (\mathrm{\θ}+{\mathrm{\θ}}_i+\mathrm{\Δ\θ})\\ {\mathrm{the\; y}}^{\′}=\mathrm{the\; y}+(l_i+\mathrm{\Δl})*\sin (\mathrm{\θ}+{\mathrm{\θ}}_i+\mathrm{\Δ\θ})\end{array}\right..$

3) Particle weight update

Particle weights are updated in the following way: by dividing the virtual space of the map, the map where the location is located is divided into several square virtual occupancy grids in a checkerboard shape. For example, cosine similarity) calculates the similarity of the wireless signal characteristics of the particle twice in succession. If the similarity is higher than a certain threshold, the particle is considered to be a re-entrant particle and given a high weight. Otherwise, if the particle does not enter the unified occupancy cell or enter the same occupancy cell but the similarity is lower than the set threshold, the particle is marked as a non-reentrant particle, and the weight is set to low weight. the

The specific process of calculating the similarity and updating the weight is as follows: Assume that the signal fingerprint vectors of a particle entering the same occupied cell successively twice are (s ₁ , s ₂ , s ₃ ,..., s _m ) and (s ′ ₁ , s′ ₂ , s′ ₃ ,…, s′ _m ), in the vector, the value at position i is from the union of signal sources of two signal vectors, the signal strength of the i-th signal source, if a certain If there is no vector from the signal source in the vector, it will be set to zero and filled. Therefore, the cosine similarity ρ of the signal vector is calculated according to the following formula: The closer the calculated ρ is to 1, the more similar the two signal vectors are, and the closer to 0, the greater the difference between the two signal vectors. When ρ is greater than a certain empirically preset threshold, it is considered that the particle has passed its historical position during the movement, and the particle is considered to be a reentrant particle. At this time, the particle is calculated by the formula δ=e ^-1 /logρ The weight δ at this time.

4) Particle resampling

Particle resampling is carried out as follows: in the particle weight update step, the number of reentrant particles is counted, and when the proportion of reentrant particles to the total number of particles is higher than a certain threshold, resampling is performed. When resampling, the weight is larger (smaller) Particles of the new generation are copied and multiplied into a new generation of particles with a high (low) probability, and the generated new particles are in the original position of the parent particles, and the weights are reset to 1/N (N is the total number of particles), and the characteristic step The length and characteristic compass offset are the characteristic step size and characteristic compass offset of the parent particle plus a zero-mean Gaussian disturbance. the

It should be pointed out that for each positioning process, the positioning target needs to return to the position it has experienced at least once. By returning to the historical position, the particles that can correctly represent the closed-loop path are selected and given a high weight. Correct the current positioning result and correct its historical trajectory through the weighted average algorithm. the

The weighted average algorithm uses the historical positions of the particles to calculate the possible positions pointed by the particle swarm corresponding to each step, and the weight of each step is determined by the weight of the particles before the last resampling. the

Among them, the specific process of using the weighted average algorithm to update the particle position is as follows: suppose the current position of N particles is (xi _, y _i ), and the current weight of each particle is δ _i , then the target position obtained through the particle cloud calculation is : Similarly, the historical track can be updated by using the historical position of each particle and the current weight of the particle.

(4) Output parameters

The output parameters of the present invention are the location information and historical track of the positioning terminal. the

(5) Others

The devices to which this method is applied include, but are not limited to, handheld devices with various sensors, background processing servers, computers, and other video display devices. the

Description of drawings

Figure 1: Flow chart of positioning algorithm

Figure 2: Schematic diagram of the experimental area

Figure 3: Experimental route

Figure 4 Pure inertia trajectory

Figure 5 The corrected route

Figure 6 Error comparison

Figure 7 Cumulative error comparison

Specific examples

The real-time positioning method based on the inertial information and opportunistic wireless signal characteristics of the present invention is further elaborated by taking an indoor positioning test example in the third teaching building of Beijing University of Posts and Telecommunications. The present invention is generally applicable to application scenarios having the basic features in this example. the

In this example, it is difficult to receive GPS signals in the lobby of the middle and ground floor of the third teaching building of Beijing University of Posts and Telecommunications, but there are abundant indoor signals of opportunity. Stand still, and the overview of signals of opportunity measured by the positioning terminal is shown in Table 1 below:

Table 1 Summary of wireless signals

wireless signal type number of independent signals Wi-Fi 14 cellular base station signal 6

The floor plan of the lobby on the ground floor of the third teaching building of Beijing University of Posts and Telecommunications is shown in the figure below, and the experimental area is shown by the dotted line box, as shown in Figure 2:

The test starts, and the input parameters are shown in Table 2:

Table 2 output parameters

Parameter Type parameter value Default User Step Size 0.65m Longitude and latitude of positioning starting point 116.363382,39.966199 Initial particle distribution radius 10m Number of simulated particles 5000

In the positioning algorithm process, firstly, the starting point of positioning (116.363382, 39.966199) is used as the center of the circle, and within the distribution radius (10m), 5000 particles are randomly placed with the probability of decreasing from the center to the farthest. For each particle, the input parameter The step size (0.65m) is the mean value of the normal probability distribution, with 2 as the variance, set a random non-negative characteristic step size for each particle, and additionally set a 0-mean Gaussian random variable as the compass offset to complete the particle Cloud initialization. the

Then the experimenter carries the positioning terminal to move, and the positioning terminal monitors the acceleration change caused by each movement, performs a moving window filter on the vertical acceleration, recognizes each stepping behavior, and records the current opportunity when each stepping behavior occurs The characteristic information of the wireless signal, and the direction of terminal movement detected by the compass sensor at this time, the following table 3 shows the results obtained from a certain data collection in an experiment:

Table 3 Example of experimental data

signal identification sample value signal identification sample value direction signal 92 02:06:03:40:55:01 -77 58:66:ba:77:34:b0 -88 02:06:03:40:55:00 -76 58:66:ba:77:35:50 -86 58:66:ba:77:17:30 -76 58:66:ba:94:52:10 -86 58:66:ba:94:59:30 -74 58:66:ba:94:5b:30 -85 (4138, 313) -95 58:66:ba:94:53:d0 -85 (4138, 312) -101 58:66:ba:94:96:50 -81 (4138, 58677) -93 0c:da:41:1e:22:30 -80 (4138, 424) -98 58:66:ba:77:36:f0 -78 (4140, 2) -95 58:66:ba:77:33:10 -78 (4138, 36431) -95 58:66:ba:94:58:10 -77 the the

The collected direction information is the angle between the direction of motion and the direction of magnetic north, which is set to θ, and the characteristic step size of each particle is l _i , the characteristic compass offset is θ _i , the randomly generated step size disturbance is Δl, and the compass The offset disturbance is Δθ, and the coordinates of the position of the particle at the previous moment are (x, y), then after updating the state, the position (x', y') of the particle is: $\left\{\begin{array}{c}{x}^{\′}=x+(l_i+\mathrm{\Δl})*\cos (\mathrm{\θ}+{\mathrm{\θ}}_i+\mathrm{\Δ\θ})\\ {\mathrm{the\; y}}^{\′}=\mathrm{the\; y}+(l_i+\mathrm{\Δl})*\sin (\mathrm{\θ}+{\mathrm{\θ}}_i+\mathrm{\Δ\θ})\end{array}\right.$

The route chosen for this experiment is shown in Figure 3. the

The trajectory obtained by pure inertial navigation is shown in Figure 4. the

It can be seen from Figure 4 that there is a large inertial drift in the uncorrected trajectory, and it gradually moves away from the real position as the navigation progresses. The route of inertial navigation after correction by this method is shown in Figure 5. the

It can be seen from Figure 5 that the trajectory after adding the correction algorithm, when returning to the historical position, the navigation trajectory has been significantly corrected. Figure 6 below is the error comparison chart of the two navigation methods, and Figure 7 is the cumulative error comparison chart. the

As can be seen from Figures 6 and 7, this positioning algorithm has significantly improved the positioning error compared with traditional inertial navigation, and the step of returning to the historical point in this algorithm has a significant effect on reducing inertial drift. the

Table 4 below shows the mean and standard deviation of the positioning errors generated by the two methods, as well as the cumulative positioning errors. It can be clearly seen that, compared with pure inertial positioning, this method improves both the mean and standard deviation of the errors. the

Table 4 Error comparison

In summary, we can see that the present invention can effectively correct the inertial offset caused by inertial navigation, and both the error mean and the error standard deviation are obviously superior to traditional inertial navigation. the

Claims (8)

1. A real-time positioning method based on inertial information and opportunistic wireless signal characteristics, including input parameters, core algorithm, algorithm flow, and output parameters. the 2. A kind of real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1, its input parameters include but not limited to: inertial information, opportunistic wireless signal characteristic information, initial position information, wherein: 1) The inertial information in the input parameters is characterized in that the inertial information includes but not limited to the compass direction information of the positioned terminal and the motion acceleration information of the positioned terminal; 2) The opportunistic wireless signal in the input parameters is characterized by including any wireless signal with low time-varying high spatial correlation that can be detected by the positioning terminal, such as Wi-Fi signal, cellular base station signal, wireless broadcast TV signal etc; 3) The initial position information in the input parameter may be the longitude and latitude information of the positioning terminal or the coordinate information relative to a known reference point. the 3. The core algorithm of a real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1, characterized in that the real-time position information estimation and correction is realized by using the improved particle filter method combined with track inference , that is to use a particle filter to estimate the position of the terminal by simulating a certain number of particles, and update the weight and state of the particles. The particle filter method includes the following three steps: particle state update, particle weight update, and particle resampling; where : 1) The simulation of a certain number of particles in the positioning core algorithm is characterized in that, with the given or measured starting position as the center of the circle, a certain number of particles are randomly distributed on the center of the circle with the probability of decreasing from near to far from the center of the circle Nearby, for each particle, take the step size in the input parameter as the center of the probability distribution, set a random and different feature step size, and additionally set a random compass offset as the basis for particle state update; 2) Particle state update in the positioning core algorithm is characterized in that the current opportunity wireless signal feature information of all particles is updated using the opportunity wireless signal characteristic information measured by the positioning terminal; the movement direction information obtained by using the positioning terminal measurement is combined with each After the particle’s characteristic step size and characteristic compass offset, plus a certain random zero-mean Gaussian disturbance, apply track inference to each particle to update the particle’s position information; 3) The particle weight update in the positioning core algorithm is characterized in that it is carried out in the following way: by dividing the virtual space of the map where the positioning is located, the map where the positioning is located is divided into several square virtual occupancy grids in a checkerboard shape, for For particles that fall into the same occupied cell one after another, use the similarity (for example, cosine similarity) to calculate the similarity of the wireless signal characteristics of the particle’s two chances. If the similarity is higher than a certain threshold, the particle is considered to be a reentrant Particles are given a high weight. On the contrary, if the particle does not enter the unified occupancy grid or enters the same occupancy grid but the similarity is lower than the set threshold, the particle is marked as a non-reentrant particle, and the weight is set to a low weight; 4) The resampling of particles in the positioning core algorithm is characterized in that it is carried out as follows: in the particle weight update step described in 3), the number of re-entrant particles is counted, when the re-entrant particles account for a proportion of the total number of particles higher than Resampling is performed at a certain threshold. During resampling, particles with higher (lower) weights are copied and multiplied into a new generation of particles with a higher (lower) probability, and the generated new particles are in the original position of the parent particles. The weights are reset to 1/N (N is the total number of particles), and the feature step size and feature compass offset are the parent particle feature step size and feature compass offset plus a zero-mean Gaussian disturbance. the 4. the algorithm flow of a kind of real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1, it is characterized in that, carry out according to the following steps: 1) Use reliable methods such as GPS signals or artificially designated positions as the starting position, and input the average distance of each movement of the positioning target, that is, the step size information, to initialize the positioning system; 2) Monitor the motion state of the positioning target through the acceleration sensor of the positioning terminal. If the positioning target moves, use the wireless signal sensor to obtain the characteristic information of the wireless signal of opportunity, and at the same time use the compass of the positioning terminal to obtain the general direction of the movement, and perform step 3) , otherwise return to step 2); 3) Use the inertial information and opportunistic wireless signal characteristics collected by the positioning terminal as the driving information of the particle filter to update the state of the particle swarm, and at the same time use the particle swarm to calculate the possible position of the current positioning target and update its historical trajectory, and output the positioning As a result, go back to step 2). the 5. The algorithm flow of a real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1, characterized in that, for each positioning process, the positioning target needs to return to a previously experienced position at least once, By returning to the historical position, the particles that can correctly represent the closed-loop path are selected and given a high weight, and then the current positioning result can be corrected by the weighted average algorithm and its historical trajectory can be corrected. the 6. In the algorithm flow of a real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 4, said correcting the current positioning result and correcting its historical trajectory through the weighted average algorithm is characterized in that, by Weighted average, using the historical position of the particle, calculates the possible position pointed by the particle group corresponding to each step, and the weight of each step is determined by the weight of the particle before the last resampling. the 7. The output parameters of the real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1 may be the real-time position information of the positioning terminal and the historical track information of the positioning terminal. the 8. A real-time positioning method based on inertial information and opportunistic wireless signal characteristics according to claim 1, characterized in that, the applied devices include but not limited to handheld devices with various sensors, background processing servers, computers and Other video display devices. the