Systems and methods for room-level location using WiFi

• US 9,408,040 B2
• Filed: 02/14/2013
• Issued: 08/02/2016
• Est. Priority Date: 02/14/2013
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Cooper, Matthew L., Biehl, Jacob
• Primary Examiner(s): Kading, Joshua A
• Application Number:
  US13/767,719
• Publication Number:
  US 20140226503A1
• Time in Patent Office: 1,265 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/0284 Relative positioning
• CPC Class Codes: G01S 5/10 Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements , e.g. omega or decca systemsG01S5/12 takes precedence ; beacons and receivers cooperating therewith G01S1/306, G01S1/308
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

A method of identifying a location of a mobile device in a building includes identifying non-overlapping regions in a building. A server collects base station signal strength measurements at a plurality of distinct points in the building, with at least one point in each region. The server trains region classifiers for each region. Each region classifier is configured to compute a probability estimate that the test point is inside the region, using inputs that are signal strength differences. The server receives signal strength measurements from the base stations, taken by a mobile device at an unknown point. The server computes differences in signal strengths between pairs of base stations, and applies the region classifiers to the signal strength differences, thereby estimating the region where the mobile device is located. The server then transmits the estimated region to a user.

Claims

1. A method of identifying locations of mobile devices in buildings, performed at a server having one or more processors and memory, the method comprising:

partitioning a building into a plurality of regions, wherein the building includes a plurality of radio-transmitting base stations at distinct locations;

receiving training data measurements taken at a plurality of distinct points in the building, wherein for each of the distinct points the measurements measure strength of signals received from the base stations, and wherein at least one respective point of the distinct points is in each of the respective regions;

for each respective point of the plurality of distinct points in the building, computing differences between pairs of signal strength measurements taken at the respective point and forming a respective feature vector that includes a plurality of components, each component comprising a respective computed difference associated with a respective base station pair, thereby forming a plurality of feature vectors; and

for each region, using the feature vectors to train a respective region classifier, wherein the training includes selecting a respective subset of the base station pairs that consists of fewer than all base station pairs and determining a respective plurality of parameters corresponding to the respective subset of base station pairs, and wherein the respective plurality of parameters are modified during the training so that the respective region classifier computes probability estimates that test points are inside the respective region using sample feature vectors of signal strength differences for signal strength measurements taken at the test points for signals received from the base stations.

2. The method of claim 1, wherein the selected subset of base station pairs for a first region is M, and the respective plurality of parameters for the corresponding first region classifier F includes, for each m ε

M, a numeric weight w_m and a threshold value θ

_m; and

wherein F has a calculation formula of the form

3. The method of claim 1, wherein training the region classifiers comprises iteratively selecting parameters that minimize total error for the training set.

4. The method of claim 1, further comprising:

receiving sample signal strength measurements from at least a subset of the base stations, wherein the sample signal strength measurements are taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the region classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions; and

transmitting that determination to a user seeking to identify the location of the mobile device.

5. The method of claim 4, further comprising:

requesting additional signal strength measurements at the unknown point when two or more of the region classifiers for distinct regions yield similar high-probability estimates;

receiving the additional signal strength measurements taken at the unknown point; and

reapplying at least a subset of the region classifiers using the additional signal strength measurements.

6. The method of claim 1, wherein each region is part of a unique aggregate region of a plurality of aggregate regions, and each aggregate region of the plurality of aggregate regions comprises a plurality of regions, the method further comprising:

training a respective aggregate classifier for each respective aggregate region, wherein each aggregate classifier is configured to compute a probability estimate that a test point is inside the aggregate region, the computation using inputs that are differences between signal strength measurements taken at the test point for signals received from the base stations.

7. The method of claim 6, further comprising:

receiving sample signal strength measurements from at least a subset of the base stations, the sample signal strength measurements taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the aggregate classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the aggregate regions;

ascertaining that the mobile device has a greater probability of being in a first aggregate region than in any of the other aggregate regions; and

applying each of the region classifiers corresponding to the regions comprising the first aggregate region, to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions in the first aggregate region;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions of the first aggregate region; and

transmitting that determination to a user seeking to identify the location of the mobile device.

8. The method of claim 1, wherein training each respective region classifier further includes determining a respective weight for each base station pair of the respective selected subset of base station pairs.

9. A system for determining regions in buildings where mobile devices are located, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions for;

partitioning a building into a plurality of regions, wherein the building includes a plurality of radio-transmitting base stations at distinct locations;

receiving training data measurements taken at a plurality of distinct points in the building, wherein for each of the distinct points the measurements measure strength of signals received from the base stations, and wherein at least one respective point of the distinct points is in each of the respective regions;

for each respective point of the plurality of distinct points in the building, computing differences between pairs of signal strength measurements taken at the respective point and forming a respective feature vector that includes a plurality of components, each component comprising a respective computed difference associated with a respective base station pair, thereby forming a plurality of feature vectors; and

for each region, using the feature vectors to train a respective region classifier, wherein the training includes selecting a respective subset of the base station pairs that consists of fewer than all base station pairs and determining a respective plurality of parameters corresponding to the respective subset of base station pairs, and wherein the respective plurality of parameters are modified during the training so that the respective region classifier computes probability estimates that test points are inside the respective region using feature vectors of signal strength differences for signal strength measurements taken at the test points for signals received from the base stations.

10. The system of claim 9, wherein the selected subset of base station pairs for a first region is M, and the respective plurality of parameters for the corresponding first region classifier F includes, for each m ε

M, a numeric weight w_m and a threshold value θ

_m; and

wherein F has a calculation formula of the form

11. The system of claim 9, wherein instructions for training the region classifiers comprise instructions for iteratively selecting parameters that minimize total error for the training set.

12. The system of claim 9, the one or more programs further comprising instructions for:

receiving sample signal strength measurements from at least a subset of the base stations, wherein the sample signal strength measurements are taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the region classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions; and

transmitting that determination to a user seeking to identify the location of the mobile device.

13. The system of claim 12, the one or more programs further comprising instructions for:

requesting additional signal strength measurements at the unknown point when two or more of the region classifiers for distinct regions yield similar high-probability estimates;

receiving additional signal strength measurements taken at the unknown point; and

reapplying at least a subset of the region classifiers using the additional signal strength measurements.

14. The system of claim 9, wherein each region is part of a unique aggregate region of a plurality of aggregate regions, and each aggregate region of the plurality of aggregate regions comprises a plurality of regions, the one or more programs further comprising instructions for:

training a respective aggregate classifier for each respective aggregate region, wherein each aggregate classifier is configured to compute a probability estimate that a test point is inside the aggregate region, the computation using inputs that are differences between signal strength measurements taken at the test point for signals received from the base stations.

15. The system of claim 14, the one or more programs further comprising instructions for:

receiving sample signal strength measurements from at least a subset of the base stations, the sample signal strength measurements taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the aggregate classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the aggregate regions;

ascertaining that the mobile device has a greater probability of being in a first aggregate region than in any of the other aggregate regions; and

applying each of the region classifiers corresponding to the regions comprising the first aggregate region, to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions in the first aggregate region;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions of the first aggregate region; and

transmitting that determination to a user seeking to identify the location of the mobile device.

16. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:

partitioning a building into a plurality of regions, wherein the building includes a plurality of radio-transmitting base stations at distinct locations;

receiving training data measurements taken at a plurality of distinct points in the building, wherein for each of the distinct points the measurements measure strength of signals received from the base stations, and wherein at least one respective point of the distinct points is in each of the respective regions;

for each respective point of the plurality of distinct points in the building, computing differences between pairs of signal strength measurements taken at the respective point and forming a respective feature vector that includes a plurality of components, each component comprising a respective computed difference associated with a respective base station pair, thereby forming a plurality of feature vectors; and

for each region, using the feature vectors to train a respective region classifier, wherein the training includes selecting a respective subset of the base station pairs that consists of fewer than all base station pairs and determining a respective plurality of parameters corresponding to the respective subset of base station pairs, and wherein the respective plurality of parameters are modified during the training so that the respective region classifier computes probability estimates that test points are inside the respective region using sample feature vectors of signal strength differences for signal strength measurements taken at the test points for signals received from the base stations.

17. The computer readable storage medium of claim 16, wherein the selected subset of base station pairs for a first region is M, and the respective plurality of parameters for the corresponding first region classifier F includes, for each m ε

M, a numeric weight w_m and a threshold value θ

_m; and

wherein F has a calculation formula of the form

F(X)=Σ

<sub>mε

M</sub>w_mh_m(X),

where X is a variable representing a set of test signal strength measurements for signals from the base stations as measured at an unknown point in the building, and each h_m(X) is 1 or 0 depending on whether a computed difference between signal strengths from the pair of base stations in m is greater than the threshold value θ

_m.

18. The computer readable storage medium of claim 16, the one or more programs further comprising instructions for:

receiving sample signal strength measurements from at least a subset of the base stations, wherein the sample signal strength measurements are taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the region classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions; and

transmitting that determination to a user seeking to identify the location of the mobile device.

19. The computer readable storage medium of claim 18, the one or more programs further comprising instructions for:

requesting additional signal strength measurements at the unknown point when two or more of the region classifiers for distinct regions yield similar high-probability estimates;

receiving the additional signal strength measurements taken at the unknown point; and

reapplying at least a subset of the region classifiers using the additional signal strength measurements.

20. The computer readable storage medium of claim 16, wherein each region is part of a unique aggregate region of a plurality of aggregate regions, and each aggregate region of the plurality of aggregate regions comprises a plurality of regions, the one or more programs further comprising instructions for:

training a respective aggregate classifier for each respective aggregate region, wherein each aggregate classifier is configured to compute a probability estimate that a test point is inside the aggregate region, the computation using inputs that are differences between signal strength measurements taken at the test point for signals received from the base stations.

21. The computer readable storage medium of claim 20, the one or more programs further comprising instructions for:

receiving sample signal strength measurements from at least a subset of the base stations, the sample signal strength measurements taken by a mobile device at an unknown point in the building;

selecting pairs of received sample signal strength measurements, and for each pair, subtracting one of the sample signal strength measurements in the pair from the other sample signal strength measurement in the pair, yielding a set of test signal strength differences;

applying each of the aggregate classifiers to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the aggregate regions;

ascertaining that the mobile device has a greater probability of being in a first aggregate region than in any of the other aggregate regions; and

applying each of the region classifiers corresponding to the regions comprising the first aggregate region, to the set of test signal strength differences, thereby estimating the probability that the mobile device is in each of the regions in the first aggregate region;

determining that the mobile device has a greater probability of being in a first region than in any of the other regions of the first aggregate region; and

transmitting that determination to a user seeking to identify the location of the mobile device.