Wireless-based localization using a zonal framework

Patent metadata

Field	Value
Publication number	US-9674656-B2
Application number	US-201414185768-A
Country	US
Kind code	B2
Filing date	Feb 20, 2014
Priority date	Feb 20, 2014
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

Disclosed herein are techniques and systems for performing wireless-based localization using a zonal framework. An area (i.e., surface or space) may be partitioned into multiple zones, and one or more signal propagation models for one or more wireless access points (APs) may be generated for each zone. The result is a set of zonal signal propagation models that allow for improved model fitness on a per-zone basis. A process includes receiving a location query associated with a wireless communication device, selecting a target zone among multiple available zones of an area, and estimating a location of the wireless communication device based at least in part on one of a signal propagation model associated with the target zone or a fingerprint-based localization. The signal propagation model associated with the target zone may be generated based on training samples observed exclusively within the target zone.

First claim

The invention claimed is:

1. A computer-implemented method comprising:
receiving a location query associated with a wireless communication device;
dividing, by one or more processors, an area into multiple zones, individual zones of the multiple zones being located at least partially within the area, and individual zones of the multiple zones being associated with respective zonal signal propagation models;
determining, by the one or more processors, an estimated location of the wireless communication device within the area, the estimated located being based at least in part on a global signal propagation model associated with the area;
selecting, by the one or more processors, a target zone among the multiple zones that is closest to the estimated location of the wireless communication device; and
determining, by the one or more processors, a final estimated location of the wireless communication device based at least in part on a zonal signal propagation model associated with the target zone, the zonal signal propagation model being one of the respective zonal signal propagation models.

2. The computer-implemented method of claim 1 , further comprising generating the zonal signal propagation model associated with the target zone based on training samples observed exclusively within the target zone.

3. The computer-implemented method of claim 2 , further comprising determining that a number of the training samples observed meets or exceeds a threshold number of training samples before generating the zonal signal propagation model.

4. The computer-implemented method of claim 1 , wherein selecting the target zone further comprises:
receiving a wireless communication sample from the wireless communication device, the wireless communication sample reporting a received signal strength (RSS) from one or more wireless access points at the wireless communication device;
using respective histograms of the one or more wireless access points to calculate a likelihood of observing the wireless communication sample in individual zones of the multiple zones; and
selecting the target zone from among the multiple zones that maximizes the likelihood of observing the wireless communication sample.

5. The computer-implemented method of claim 4 , further comprising:
filtering out individual zones of the multiple zones based on a comparison of wireless access points in the area to the one or more wireless access points reported in the wireless communication sample to obtain a set of candidate zones with at least one common wireless access point to the one or more wireless access points; and
using histograms corresponding to wireless access points located in individual zones of the set of candidate zones to calculate the likelihood of observing the wireless communication sample in the individual zones of the set of candidate zones.

6. The computer-implemented method of claim 1 , wherein selecting the target zone comprises determining that a center of the target zone is closer to the estimated location than other centers of other zones of the multiple zones.

7. The computer-implemented method of claim 1 , wherein selecting the target zone further comprises:
selecting a subset of zones among the multiple zones based on respective distances from individual zones of the multiple zones to the estimated location;
determining respective estimated locations of the wireless communication device according to respective zonal signal propagation models associated with each zone in the subset of zones; and
selecting the target zone as a zone among the subset of zones that minimizes a model fitness error for the respective zonal signal propagation models.

8. The method of claim 1 , wherein the zonal signal model associated with the target zone includes one of a path loss signal propagation model or a linear model.

9. A system comprising:
one or more processors; and
one or more memories storing computer-executable instructions that, upon execution by the one or more processors, cause performance of operations comprising:
receiving a location query associated with a wireless communication device;
determining a first location estimate of the wireless communication device within an area based at least in part on a global signal propagation model associated with the area as a whole;
selecting a target zone among multiple available zones of the area, the target zone being associated with a zonal signal propagation model, each of the multiple available zones located at least partially within the area;
determining a second location estimate of the wireless communication device within the area based at least in part on the zonal signal propagation model;
determining that a first model fitness error of the global signal propagation model is less than a second model fitness error of the zonal signal propagation model; and
determining a final location estimate of the wireless communication device based at least in part on the global signal propagation model.

10. The system of claim 9 , wherein selecting the target zone comprises:
receiving a wireless communication sample from the wireless communication device, the wireless communication sample reporting a received signal strength (RSS) from one or more wireless access points at the wireless communication device;
using respective histograms of the one or more wireless access points to calculate a likelihood of observing the wireless communication sample within individual zones of the multiple available zones; and
selecting the target zone as a zone among the multiple available zones that maximizes the likelihood of observing the wireless communication sample.

11. The system of claim 10 , the operations further comprising:
shifting the RSS reported in the wireless communication sample by multiple gain offsets across a range of possible gain offsets to obtain multiple shifted RSS measurements;
for individual shifted RSS measurements of the multiple shifted RSS measurements, selecting respective zones of the multiple available zones that maximize a likelihood of observing the individual shifted RSS measurements; and
selecting a gain offset among the multiple gain offsets corresponding to a maximum among multiple likelihoods determined for the individual shifted RSS measurements.

12. The system of claim 9 , the global signal propagation model is generated for individual wireless access points of multiple wireless access points within the area.

13. The system of claim 9 , wherein determining the second location estimate comprises selecting a set of candidate zones including the target zone, and wherein the operations further comprise:
determining respective zonal signal propagation models associated with each zone in the set of candidate zones;
applying the respective zonal signal propagation models to estimate respective locations of the wireless communication device for each of the candidate zones; and
resolving the second location estimate as an average of the respective locations.

14. The system of claim 9 , wherein the zonal signal propagation model is generated based on training samples observed exclusively within the target zone.

15. The system of claim 9 , wherein selecting the target zone comprises selecting the target zone as a zone having a center that is closer to the estimated location than other centers of other zones of the multiple available zones.

16. A computer-implemented method comprising:
partitioning, by one or more processors, an area into multiple zones, individual zones of the multiple zones being associated with respective zonal signal

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Li Liqun
• Shen Guobin
• Zhao Chunshui
• Zhao Feng

Classifications

• H04W64/00 Primary

  Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management · CPC title

• H04W4/029

  Location-based management or tracking services · CPC title

• H04W84/12

  WLAN [Wireless Local Area Networks] · CPC title

• H04W4/021 Primary

  Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences · CPC title

• H04W84/02

  Hierarchically pre-organised networks, e.g. paging networks, cellular networks, WLAN [Wireless Local Area Network] or WLL [Wireless Local Loop] · CPC title