The following content is reprinted from the article “An Indoor Location Free Wi-fi Fingerprint Filling Algorithm for indoor Stores” by Tencent Location Service.
Author: Tencent Location Service
Links: juejin. Cn/post / 684490…
Source: Nuggets
Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.
For the most mainstream indoor Wi-Fi fingerprint positioning technology, the coverage and freshness of wi-fi fingerprint collection are the most important factors to determine the positioning accuracy. Due to cost and navigation requirements, Tencent’s map location platform currently provides indoor location services that only collect fingerprint information from the corridor of the mall. For larger stores, it is currently difficult to manually collect Wi-Fi fingerprints. This paper introduces how we use the location log data accumulated in the past to realize the automatic filling of wi-fi fingerprint in indoor stores and apply it to indoor location services, thus improving the coverage and service quality of our indoor location services.
First, background
In the indoor environment, the GPS signal is too weak or even undetectable because the signal is blocked by the building and cannot be used for positioning services. With the popularity and widespread deployment of Wi-Fi technology, the positioning technology based on Wi-Fi fingerprint has become the most universal and basic solution for indoor positioning. However, for Wi-Fi fingerprint positioning technology, the coverage and freshness of fingerprint collection are the most important factors to determine the positioning accuracy.
At present, Tencent map location platform provides wi-fi fingerprint based indoor location services for major shopping malls in China. However, due to the cost of fingerprint collection and navigation requirements, fingerprint collection is mainly concentrated in the corridor area of shopping malls. Figure 1 shows the coverage of Wi-Fi fingerprints we collected on a floor of Beijing Euro-Hui Shopping Mall. As can be seen from the picture, we have collected fingerprints for the main corridor areas in the mall. However, for the wider store segment, the current wi-fi fingerprinting process is difficult to cover. This lack of fingerprint coverage makes it impossible for us to ensure consistent quality throughout the store. When a user initiates a location request in the store, wi-fi fingerprint information is missing in the store. Ideally, the Wi-Fi fingerprint collected at the store door is similar to the Wi-Fi information scanned when the user requests location, and the user is located at the store door. However, an even worse situation, as shown in Figure 2, is that we locate the user far from the store, which seriously degrades the user’s location experience.
In this case, the most direct solution is to collect fingerprint information in the store, so that the whole store fingerprint collection coverage. However, because the area of the store is much larger than the corridor area within the mall, the cost of fingerprinting the store can multiply. At the same time, due to more frequent store renovation, relocation and replacement of Wi-Fi equipment, store fingerprints need to be updated more frequently in order to ensure the accuracy of store fingerprints. These factors make it impossible to manually collect store fingerprints under current technology. Therefore, we need to find other ways to populate store fingerprints in the mall and use them for our location services.
2. Automatic filling of store Wi-Fi fingerprint
At present, Tencent map location platform’s indoor location services cover more than 3,000 major shopping malls in China, with hundreds of millions of location requests occurring in these shopping malls every day, and tens of millions of location requests are made when mobile phones are connected to Wi-Fi hot spots. If the Wi-Fi hotspot that a user connects to when making a location request is an in-store hotspot, then the actual location of the user at the time of the location request is likely to be in the store. At this point, the wi-fi scan information uploaded when the user requested a location could be used to establish a store fingerprint. However, there are some challenges that need to be addressed in order to establish a store fingerprint using the log of a user’s location request when connecting to a hotspot:
- Is the Wi-Fi hotspot connected to the user in the store? In which shop?
- How to ensure that the location request connected to the hotspot must be issued in the corresponding shop?
To solve the first problem, we tried to associate each Wi-Fi hotspot with a shop based on the name of each Wi-Fi hotspot, the name of the shop, the location of each Wi-Fi mined from the historical location log, and other information, and established a mapping library between Wi-Fi and the shop. It provides a good data basis for us to fill store fingerprint with positioning log data in the future.
To solve the second problem, we cleaned the location logs according to the signal strength information of wi-fi hot spots in the store scanned in the location request, and retained the request data with strong signal strength, so as to ensure that each request log for store fingerprint filling is generated in the corresponding store as far as possible. Finally, we use the log data of the last month to fill the store fingerprint and update it regularly. In this way, we ensure the automatic filling of the store’s fingerprint and the freshness of the store’s fingerprint — even if the store changes or migrates, our fingerprint data can adapt in time.
Three, constrained positioning
After filling in the store fingerprint, we also need to use the store fingerprint for our location service to fill in areas not covered by manual Wi-Fi fingerprints. However, there was a big difference between store Wi-Fi fingerprints and those collected manually in corridor areas, making it impossible to directly merge the two.
First, the freshness of fingerprints varies from source to source. The store’S Wi-Fi fingerprint comes from the location log and can be automatically updated every day to keep it fresh at all times. However, manual fingerprint collection cycle is generally around a year. Therefore, the fingerprint information in the corridor deteriorates over time, and the matching degree between the fingerprint information and the Wi-Fi list detected during the actual request deteriorates. When these two kinds of fingerprint information are used in location calculation at the same time, bias will exist in fingerprint matching degree due to freshness difference.
Secondly, the reliability of fingerprints obtained by different methods is different. Manually collected Wi-Fi fingerprint has a very clear mark of the real location, high reliability; However, the auto-filling store Wi-Fi fingerprint can only ensure that most of the fingerprint data comes from the store even if the data cleaning policy is added, and there is a certain proportion of noise data in the overall data.
In addition, the size of the area represented by a manual Wi-Fi fingerprint is quite different from that represented by a store fingerprint. Wi-fi fingerprints are collected manually by dividing the location area into grids with the same size. Wi-fi fingerprints are collected from each grid. In the actual positioning process, as shown in Figure 3, we will select one or several grids that are most similar to the wi-fi fingerprints and the collected Wi-Fi list to determine the target location. However, the store Wi-Fi fingerprint describes the characteristics of the entire store. A shop is generally much larger than a grid and varies in size and shape from shop to shop.
Affected by the above factors, we cannot directly and equally integrate the manually collected grid fingerprint and the automatically filled store fingerprint to provide location service. At the same time, considering the low reliability and large coverage of store fingerprint, store fingerprint may cause a large offset if it is eventually involved in location calculation. Therefore, we finally adopt the constrained location based on ranking. Figure 4 shows the overall flow of constrained positioning for our current release.
First, we built a sequencing model to determine whether the target made the request in the store or in the corridor covered by manual fingerprint collection. We extracted a 41-dimensional feature vector for each grid and store based on the wi-fi in the manually collected grid fingerprint and the auto-filled store fingerprint, and the corresponding signal strength of each Wi-Fi. Based on feature vectors, we trained an XGBoost tree model as our sorting model to sort stores and grids and judge the actual area where users send positioning requests.
Then, based on different sorting results, we adopt different positioning strategies. If we judge that the current location of the request is more likely to be in the grid that has been manually collected fingerprints, then we use the existing locating process to select the most similar one or several grids according to the fingerprint characteristics in the grid to calculate the location of the target. If we determine the location of the target location requests are more likely to be in a store, then we will find a shop around the grid, as shown in figure 5, to finally determine the location of the object with the grid, which will locate the constraint at the entrance to the shop most targets, lest produce big location deviation.
Finally, under the above strategy, when the location results deviated too far from the actual location due to the lack of store fingerprints, we were able to re-constrain 50% of the requests to the correct range for location, greatly reducing the number of large offset location results. In cases where the original system was able to locate correctly, error constraints were imposed on at most 2% of the location requests, with no negative impact on existing location performance and other related services.
Four, summary
With the improvement of location service quality, more and more users begin to use our indoor location service, but also put forward higher requirements for location accuracy. However, due to the limitation of system construction cost, indoor fingerprint collection cannot truly cover all indoor areas. The lack of store fingerprint has become the key to restrict the further improvement of indoor location service quality. In this paper, we made use of the advantages of location data accumulated by the team in the past, and automatically filled part of the store fingerprint and used it for location services without increasing the cost, which improved the range of locatable areas and greatly improved the user’s location experience. Fill in the future, we will continue to optimize for fingerprint data quality, combined with more data sources at the same time, improve data accuracy as well as more shops for fingerprint populated, so as to provide a more comprehensive and accurate localization experience, also for the application of more upper service location information services provide a reliable basis.
At present, indoor map products are paid products featured by Tencent location service. If you are interested, you can click to learn about them. Welcome to experience ~
IOS map SDK interior map, Android map SDK interior map