TWI425241B - Combining the signal intensity characteristic comparison and position prediction analysis of hybrid indoor positioning method - Google Patents

Description

Hybrid indoor positioning method combining signal strength feature comparison and position prediction analysis

The invention relates to a hybrid indoor positioning method for combining signal strength characteristic comparison and position prediction analysis, in particular to a setting step and a tracking positioning step, which can be determined by the judgment module of the operation means by the first predicted position or It is the second predicted position as the predicted position of the user's next move.

With the rapid development of wireless communication technology, the mobile positioning service has been paid more and more attention by everyone. At present, the mobile positioning service is represented by GPS of global positioning system, and there are huge business opportunities for indoor positioning service. However, to provide indoor location services, it is necessary to utilize technologies that are different from global positioning systems. The biggest limitation of GPS technology is that it must be connected to the satellite system at any time. In indoors or in buildings, wireless signals cannot directly connect to the user equipment directly, and the indoor environment is complicated. The precision requirements are relatively high, so the indoor positioning system has many problems such as signal strength extraction, database construction and positioning algorithm to be overcome and solved.

At present, the positioning modes of positioning services in the wireless network environment generally include an Angle of Arrival (AOA), a Time of Arrival (TOA), and a Time Difference of Arrival (TDOA). Positioning mode such as Received Signal Strength (RSS), the signal strength method is more suitable for indoor environment in the above four positioning modes, and the other three positioning modes are more affected by multiple path problems in indoor environment; The method is more predictable for the change of the signal strength when the position is moved. In other words, the signal strength method can obtain higher positioning accuracy.

On the other hand, since GPS cannot provide indoor positioning service, it is necessary to use WiFi positioning system. Selecting an appropriate access point (AP) can also improve the positioning accuracy, and in the positioning judgment of the floor, The WiFi positioning system also provides a viable solution. In a situation where the indoor multipath is severe or the crowd is moving dynamically, the result of the positioning error will also occur when the signal is oscillated and the oscillation is suddenly inaccurate.

With the increasing scope and application of indoor positioning services, today's 802.11 WLANs are widely deployed in indoor environments, and the indoor environment of signal propagation is affected by indoor multipaths. The environment that spreads indoors is quite complicated. And slight changes in the environment can cause serious signal fluctuations, such as the appearance of obstacles or the movement of people. Because of the above situation, even if the user is in the same place, the signal strength received from the 802.11 access points (AP) will be different at different times, this situation will lead to lower positioning accuracy.

Furthermore, after the applicant searched the national patent search system, it found that there were two inventions such as the domestic invention No. I243255 "Indoor positioning method and system using the chaotic sample strategy" and the invention publication No. 201020578 "Indoor positioning method and system" In the case, the two patents only focused on the positioning algorithm itself or the information of the appropriate Access point as the parameters of the positioning algorithm to improve the accuracy of the positioning. However, the situation of signal oscillation is still unavoidable. The two patents have no filtering function for the number of access points and reference points, and the function setting of the scores of the access points and the signal strength, so that the effect of indoor positioning tracking is affected by the long processing time of the signal, and The accuracy of positioning.

In addition, after the applicant has searched the U.S. patent system, the patents related to the present invention are respectively obtained as US Patent No. US0176583, Patent No. US0257831, and Patent No. AU317677, among which US Patent No. 01765833 is not. Considering the influence of signal fluctuation on the positioning accuracy, it is different from the technical content and the achievement of the present invention. As for the US patents US0257831 and AU317677, the two patents not only do not consider the impact of signal fluctuation on the positioning accuracy, but also do not take into account the mobility of the mobile client (mobile client mobility), so the above These patents are indeed different from the technical content and the achieved effects of the present invention.

The main object of the present invention is to provide a hybrid indoor positioning method combining signal strength feature comparison and position prediction analysis, which is mainly used to solve the problem of indoor signal oscillation, thereby combining a better positioning algorithm with a mobile prediction technology. Minimize the adverse effects caused by signal fluctuations, and further correct the predicted position of the tracked person. In an environment where indoor multiple paths are seriously affected, it can still provide indoor positioning services with high accuracy and better positioning quality. A prediction result with reasonable prediction and inaccurate correction is achieved, and a lower positioning error rate can be obtained.

In order to achieve the above-mentioned effects, the technical module used in the present invention is to set a plurality of access points in the indoor area, and to set a plurality of reference points in the indoor area, and collect the identification signals transmitted by the plurality of access points at each reference point by the Internet access device. And transmitting the signal strength data of the plurality of identification signals and the identification signals to the data base of the computing means through the wireless network, and the filtering means filtering the redundant identification signals and reference points in the reference points by the filtering module, so as to use The internet device collects the identification signals transmitted by the plurality of access points at a predetermined time, and the scoring module of the computing means scores each reference point according to the identification signal and the signal strength collected by the user, and the estimation module of the computing means Then, according to the scoring result, a reference point is selected as the first predicted position of the user, and the computing means further estimates the average moving speed of the user according to the plurality of preliminary predicted positions by the mobile prediction module, thereby estimating the second ready movement of the user. Predicting the position, the computing means then determining the first predicted position or the second prediction by the determining module Set as the predicted position of a user's next move.

one. Application field of the invention and problems to be solved

With the improvement of mobile computing capabilities, indoor positioning services have become more and more important, so the user's position and movement path must have a certain degree of mastery. Since most of the electronic devices (10) such as mobile phones, PDAs, and tablet computers have built-in Wi-Fi communication modules (such as wireless network cards), the present invention uses the receiving Wi-Fi signal to achieve positioning. The purpose is more market-worthy. The indoor positioning technology of the present invention can be applied to a large exhibition hall or exhibition venue to guide the user to enter the exhibition hall or the exhibition site, and can be applied to the dormitory, the home or the Offices for office automation, home automation, etc.; this positioning technology can also be applied to allow field personnel (such as business, security personnel, police officers, and taxi drivers) to be informed of their current location information.

Since indoor positioning service systems are mostly constructed under the framework of fingerprint algorithms, fluctuation signals have always been the key to the problem of signal strength (RSS). These fluctuation signals can greatly reduce the accuracy of indoor positioning. To solve this serious problem, any existing fingerprint-based indoor positioning algorithm can be integrated into the indoor positioning technology architecture of the present invention, thereby further estimating the location of the Internet device. position. The invention utilizes the Brownian motion in model prediction, and further proposes a technique of mobility prediction, thereby achieving a prediction result with reasonable prediction estimation and high correction error rate, and obtaining a lower positioning error rate, in addition, when some When the experimental training record of the indoor area (1) or the radio map is outdated and is not practical, it can also be found through the operation of the present invention, and immediate correction and reconstruction can be given.

two. Basic embodiment of the invention

Referring to the first to fourth figures, based on the above-mentioned effects, the basic embodiment of the present invention sets a plurality of access points (APs) at different positions in the indoor area (1), and the method further includes the following Step: setting step: dividing a plurality of reference points (1a) in the indoor area (1), as shown in the fourth figure, and collecting a plurality of access points (40) at each reference point (1a) by the internet device (10). The transmitted identification signal and the collected signal strength data of the plurality of identification signals and the identification signal are transmitted to the database (31) through the communication network (20), thereby constructing a set of radio maps for comparison (radio map); and tracking positioning step: filtering and deleting the redundant identification signal and the reference point (1a) in each reference point (1a) by a filtering module, so that the user can hold the Internet device (10) at a predetermined time The identification signal transmitted by the plurality of access points (40) is collected in time; and the scoring module (33) of a computing means (30) is used according to the signal strength of the plurality of identification signals and identification signals collected by the user. The reference point (1a) is scored, and the estimation mode of the operation means (30) (34) selecting a reference point (1a) as the first predicted position of the user according to the scoring result; on the other hand, the calculating means (30) estimating by the mobile prediction module (35) according to the plurality of preliminary predicted positions The average moving speed of the user further estimates the second predicted position of the user's preparatory movement, and the computing means (30) further determines, by the determining module (36), whether the first predicted position or the second predicted position is used as the user. The predicted position of a move.

Participation. Specific embodiments of the technical features of the present invention 3.1 setting steps

Referring to FIG. 4 and FIG. 4, the filter module of the present invention includes an access point filter (320) and a spatial filter (321). The access point filter (320) adds weak signals and adds The access point (40) is filtered and deleted. After filtering through the access point (40), the spatial filter (321) picks up and simultaneously receives all the access points in the plurality of access points (40). Reference point (1a), by which the reference point (1a) of all access points (40) in the set of multiple access points (40) cannot be received.

In detail, after filtering through the access point, it is assumed that the user can receive the identification signals of the 802.11 APs of the plurality of access point sets Am={AP1, AP2, ..., APm} at a certain point in time, and the space filter ( 321) that is, a reference point (1a) that can simultaneously receive all access points (40) APs in Am, and these reference points (1a) constitute a set S, assuming S={ref1, ref2, ..., refk }, this collection is called a candidate set.

3.2 Tracking and positioning steps

Please refer to the first to fourth figures. The scoring algorithm of the scoring module (33) is mainly based on formula 1, formula 2 and formula 3 to score each reference point (1a), where SS _i is the user. from one access point (40) (AP _i) received signal _strength, W _{i, j} and d _{i, j} are, respectively, wherein a reference point (1a) (ref _j) from one of the access point (40) (AP _i ) the average signal strength received and the standard deviation (as shown in Equation 2), and using a Gaussian distribution to estimate the received from the access point (40) (AP _i ) The signal strength, as shown in the sixth figure, the difference between the user's signal strengths SS _i and W _i,j is the available area (Area _i,j ) (indicated by Equation 1), the reference point (1a) The set of the number of access points (40) (AP _i ) that can be received on (ref _j ) is A _j , and the smaller the difference between A _j and A _m indicates that the position of the user is more likely to be in the reference. Point (1a) (ref _j ), and the score of the reference point (1a) (ref _j ) is performed by the formula 3, and the score result is sent to the estimation module (34). In a specific embodiment, the estimation module (34) selects the reference point (1a) with the smallest score as the first predicted position described above.

Referring to the third and fifth figures, the computing means (30) of the present invention establishes a feature database (39) for storing the user's movement track record, and the estimating step further includes an experimental training step in the experimental training step. The results of a plurality of positioning experiments can be used as a basis for inferential analysis of statistical data, and the probability of calculating the positioning error less than r (p _e1,r ) can be inferred by statistical data for multiple distances ( _r ); (35) is to use the Brownian motion method to calculate the probability that the second predicted position will be in the circle with the distance (r) as the radius (p _{n+1, r} ), as shown in the attached figure 1 when moving the trajectory When the record is less than the preset number, the judging module (36) uses the first predicted position as the predicted position of the user's next move.

Referring to FIG. 5 again, when the moving track record is greater than or equal to the preset number, the determining module (36) selects a positive real number (r) from the statistical data estimation probability (p _{e1, r} ) and the probability ( p _n+1,r ), when the probability (p _e1,r ) is greater than or equal to the probability (p _n+1,r ), the first predicted position is used as the predicted position of the next movement of the user, when the probability is When (p _e1,r ) is less than the probability (p _n+1,r ), the second predicted position is used as the predicted position of the next movement of the user; otherwise, the difference between the first predicted position and the second predicted position When it is too large, the judgment module (36) performs inference analysis using statistical data, and can correct the predicted position of the user's next move based on the inference analysis result.

Specifically, the motion prediction module (35) of the present invention calculates the position (point Q) of the next point based on the position of the previous M FPELs to calculate the average moving speed (v) of the user. (Counted in a recent position FEL), Brownian motion and the method using the calculated position of the point will be the probability (p _{n + 1, r)} in the radius r of the circle where:

3.3 arithmetic means

Please refer to the first and second figures. In a more specific embodiment, the above-mentioned database (31) (radio map) establishes map data of the indoor area (1), and the judgment module of the operation means (30) (36) When determining the predicted position of the user's next move, the determination module (36) transmits the map data corresponding to the predicted position to the user's Internet access device (10), and the reference point (1a) is framed. The grid pattern is densely divided into the indoor area (1). In addition, the communication network (20) includes a wireless local area network and an internet network, and a communication network (20) connected between the Internet access device (10) and each access point (40) and computing means (30). ) is a wireless local area network, which is a wireless local area network (20) (WLAN, Wireless LAN) of the IEEE 802.11 series of standards.

Referring to the first and second figures, the specific embodiment of the computing means (30) of the present invention comprises at least a near-end server (37) and a remote main server (38), when the user first When the indoor positioning service is enabled, the remote main server (38) must be applied for registration. As shown in the second figure, when the user passes the registration process, the above indoor positioning service can be enabled. The above database (31) It can be established on the server (37) for receiving the plurality of identification signals transmitted by the Internet access device (10) and the signal strength data of the identification signal, and using the scoring module (33) for each reference. The point (1a) is scored, and the result is uploaded to the main server (38) for the user's next mobile position prediction operation, and the main server (38) uses the estimation module (34) and the mobile prediction mode. The group (35) and the judging module (36) perform calculations, and then transmit the operation result to the internet device (10) via the server, so that the user can know the current indoor location information.

Hey. Experimental example of the present invention

In order to verify that the indoor positioning method proposed by the present invention is indeed a feasible and effective technical solution, the present invention collects IEEE 802.11 wireless signals of each access point (40) in the indoor area (1) environment through the Internet access device (10), such as Figure 2 shows the top view of the building on the 4th floor of the Department of Capital, National Taiwan University. There are 20 sets of access points (40) in the building. The number of reference points (1a) is 80 and is distributed throughout the building. In the direction of east, south, west, and north, each reference point (1a) is separated by about 2 meters, thereby constructing a wireless map, and the connected device (10) is an action using the Android l.5 operating system. Telephone, and collect about 100 signal samples, and let everyone walk around, in order to actually grasp the movement of people, and predict the location where people want to move. After verification by the experimental example, although some first predicted positions (FPELs) are relatively inaccurate, the reason for the investigation is caused by the fluctuation signal. It is also found that the present invention is really helpful for the reconstruction of the radio map. When relying on the mobile prediction module (35) to infer, it is reasonable to suspect that the radio map of this indoor area (1) may be outdated and should be reconstructed.

In the aspect of mobility prediction technology, the average moving speed of the Internet access device (10) is calculated by M first predicted positions (FPELs). Therefore, the value of M cannot be set too large or too small, so that the Internet can be obtained. The device (10) has an accurate average moving speed, and the optimal number of M values is six first predicted positions (FPELs).

The seventh diagram shows three positioning prediction modes, the first is the training phase and there is no motion prediction mode (ML), the second is no motion prediction mode (without MP), and the third is mobile prediction mode (with MP). The positioning method of the present invention has different positioning precisions in different sampling periods. In fact, the positioning accuracy is the best in the third positioning prediction mode (with MP), and the first positioning mode is the worst. In general, when the sampling period of the receiving signal of the Internet access device (10) is long, there will be better positioning accuracy. As shown in the attached figure, the first positioning prediction mode (ML) prediction technology positioning can be seen. The poor effect is due to the problem of signal fluctuations. The present invention can utilize the motion prediction module (35) to correct the positioning deviation. Therefore, when the sampling period is long and exceeds 2.5 seconds, the positioning average error rate is lower and more stable.

Wu. in conclusion

Therefore, the present invention can solve the problem of indoor signal oscillation by setting the above technical features, so that the preferred positioning algorithm is combined with the mobile prediction technology to minimize the adverse effects caused by signal oscillation and can be further corrected. The predicted position of the tracked person can still provide indoor positioning services with high accuracy and better positioning quality under the environment that the indoor multipath is seriously affected, so as to achieve the prediction result of reasonable estimation and inaccurate correction, and obtain the comparison result. Low positioning error rate.

The above is only one of the possible embodiments of the present invention, and is not intended to limit the scope of the patents of the present invention, and the equivalent implementations of other changes according to the contents, features and spirits of the following claims are It should be included in the scope of the patent of the present invention. The invention is specifically defined in the structural features of the request item, is not found in the same kind of articles, and has practicality and progress, has met the requirements of the invention patent, and has filed an application according to law, and invites the bureau to approve the patent according to law to maintain the present invention. The legal rights of the applicant.

(1). . . Indoor area

(1a). . . Reference point

(10). . . Internet device

(20). . . Wireless network

(30). . . Arithmetic means

(31). . . database

(320). . . Access point filter

(321). . . Space filter

(33). . . Rating module

(34). . . Estimation module

(35). . . Mobile prediction module

(36). . . Judging module

(37). . . server

(38). . . Master server

(39). . . Feature database

(40). . . Access point

The first figure is a schematic diagram of the implementation of the basic architecture of the present invention.

The second figure is a schematic diagram of the implementation of the specific architecture of the present invention.

The third figure is a schematic diagram of the control block of the control means of the present invention.

Figure 4 is a schematic view of the present invention embodied in an indoor area.

The fifth figure is a schematic diagram of the control flow of the present invention.

The sixth figure is a schematic diagram showing the difference in signal intensity of the present invention expressed by a Gaussian distribution.

The seventh figure is a schematic diagram of the error rate comparison of the present invention in three predicted position modes.

Attachment: Figure 1 is a schematic diagram of the predicted position by Brownian motion; Figure 2 is a top view of the building on the 4th floor of the Department of Capital, National Taiwan University.

(10). . . Internet device

(20). . . Communication network

(30). . . Arithmetic means

(31). . . database

(37). . . server

(38). . . Master server

(39). . . Feature database

(40). . . Access point

Claims (9)

A hybrid indoor positioning method combining signal strength characteristic comparison and position prediction analysis, which is to set a plurality of access points (APs) at different positions in an indoor area, the method comprising the following steps: setting step: in the indoor The area is divided into a plurality of reference points, and an identification device transmits the identification signals transmitted by the plurality of access points to each of the reference points, and transmits the plurality of identification signals and the signal strength data of the identification signals The communication network is transmitted to a database; and the tracking and positioning step: filtering the redundant identification signal and the reference point in each reference point by using a filtering module; and the user collecting the plurality of the predetermined time by the network device The identification signal transmitted by the access point is scored by the scoring module of a computing device according to the collected plurality of the identification signals and the signal strength of the identification signal; each of the computing means is scored; The estimating module selects the reference point as the first predicted position of the user according to the scoring result; the computing means moves by another The measurement module estimates the average moving speed of the user according to the plurality of preliminary predicted positions, and further estimates a second predicted position of the user to prepare for movement; the computing means determines, by the determining module, the first predicted position or The second predicted position is used as the predicted position of the next movement of the user, wherein the scoring module scores each of the reference points through Equation 1, Equation 2, and Equation 3: Where SS _{i is} the signal strength received by the access device from one of the access points (AP _i ); W _i,j and d _i,j are respectively at one of the reference points (ref _j ) from one of the access point (AP _i) an average received signal strength and standard deviation, and the Gaussian distribution (Gaussiandistribution) to measure received signal strength from the access point (AP _i), the access means of signal strength SS The difference between _i and W _i,j is expressed by the area (Area _i,j ), and the set of the access points (AP _i ) that can be received on the reference point (ref _j ) is A. _j, a _j and the gap between the smaller a _m represents the position of the user is more likely at the reference point (ref _j), executed by the formula 3 to each row of the reference point (ref _j) score, then The result of the rating is sent to the estimation module. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the filter module comprises an access point filter and a spatial filter, the access point filter system Filtering and deleting the weak signal and the newly added access point, and after filtering by the access point, the spatial filter selects the reference point of all the access points in the plurality of access point sets at the same time. By deleting the reference point that cannot receive all of the access points in the plurality of access point sets. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the estimation module selects the reference point with the smallest score as the first predicted position. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the operation means establishes a feature database for storing the user's movement track record, and the estimating step is Furthermore, an experimental training step is included, in which the plurality of positioning experiment results can be used as the inference analysis basis of the statistical data, and the calculation of the positioning error less than r can be inferred for the plurality of distances (r) with the statistical data. Probability (p _el,r ), the motion prediction module uses the Brownian motion method to calculate the probability that the second predicted position will be in the radius (r) as a radius circle (p _n+1,r ) When the movement track record is less than the preset number, the determination module uses the first predicted position as the predicted position of the next movement of the user. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 4, wherein the determining module selects a positive real number when the moving track record is greater than or equal to the preset number (r) when) estimating the probability (p _{el, r)} and probability (p _{n + 1, r)} of the statistics, when the probability (p _{el, r)} is greater than or equal to the probability (p _{n + 1, r),} which places the first A predicted position is used as the predicted position of the next movement of the user. When the probability (p _el,r ) is less than the probability (p _n+1,r ), the second predicted position is used as the prediction of the next movement of the user. position. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 4 or 5, wherein when the difference between the first predicted position and the second predicted position is too large, the determining module is Inference analysis is performed using the statistical data, and the predicted position of the next movement of the user can be corrected based on the inference analysis result. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the database establishes map data of the indoor area, and when the determining module determines the next movement of the user When predicting the position, the judgment The broken module transmits the map data corresponding to the predicted position to the connected device of the user. The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the reference point is densely divided into the indoor area in a sash manner, and the communication network includes a wireless area. The network and the Internet, the communication network between the Internet device and each of the access points and the computing device is the wireless local area network, and the wireless local area network is an IEEE 802.11 series standard. Wireless local area network (WLAN, Wireless LAN). The hybrid indoor positioning method for combining signal strength feature comparison and position prediction analysis according to claim 1, wherein the operation means comprises at least one near-end server and a remote main server, and the database is Established on the server, the server is configured to receive the plurality of the identification signals transmitted by the network device and the signal strength data of the identification signal, and score the reference points by the rating module, and then score the scores. The result is uploaded to the main server for performing the operation of the next movement position prediction of the user, and the main server further performs calculations by using the estimation module, the motion prediction module and the determination module, and then the operation result is The server is transmitted to the internet device.