Systems and Methods for Room-Level Location Using WiFi

• US 20140226503A1
• Filed: 02/14/2013
• Published: 08/14/2014
• 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: Biehl, Jacob, Cooper, Matthew L.
• Granted Patent: US 9,408,040 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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 a location of a mobile device in a building, performed at a server having one or more processors and memory, the method comprising:

receiving base station signal strength measurements taken at a plurality of distinct points in the building, wherein the signals are received from a plurality of radio-transmitting base stations in the building, the building is partitioned into a plurality of regions, and at least one respective point of the distinct points is in each of the respective regions; and

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

2. The method of claim 1, wherein one or more of the region classifiers is configured to compute probability estimates according to a calculation formula of the form F(X)=Σ

_mw_mh_m(X), where m ranges over a respective set of base station pairs, each w_m is a non-negative real number, X is a variable representing a set of test signal strength measurements, and each h_m(X) is 1 or 0 depending on whether the difference between signal strengths from the corresponding pair of base stations is greater than a corresponding threshold value θ

_m.

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

4. The method of claim 1, further comprising:

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

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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 region classifiers for distinct regions yield similar high-probability estimates;

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

reapplying 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, and each aggregate region 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 signal strength measurements from at least a subset of the base stations, the measurements taken by a mobile device at an unknown point in the building;

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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. A system for determining a region in a building where a mobile device is located, comprising:

one or more processors;

memory; and

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

receiving base station signal strength measurements taken at a plurality of distinct points in the building, wherein the signals are received from a plurality of radio-transmitting base stations in the building, the building is partitioned into a plurality of regions, and at least one respective point of the distinct points is in each of the respective regions; and

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

9. The system of claim 8, wherein one or more of the region classifiers is configured to compute probability estimates according to a calculation formula of the form F(X)=Σ

_mw_mh_m(X), where m ranges over a respective set of base station pairs, each w_m is a non-negative real number, X is a variable representing a set of test signal strength measurements, and each h_m(X) is 1 or 0 depending on whether the difference between signal strengths from the corresponding pair of base stations is greater than a corresponding threshold value θ

_m.

10. The system of claim 8, wherein the instructions for training comprise instructions for iteratively selecting parameters that minimize the total error for the training set.

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

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

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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.

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

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

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

reapplying the region classifiers using the additional signal strength measurements.

13. The system of claim 8, wherein each region is part of a unique aggregate region, and each aggregate region 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.

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

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

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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.

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

receiving base station signal strength measurements taken at a plurality of distinct points in a building, wherein the signals are received from a plurality of radio-transmitting base stations in the building, the building is partitioned into a plurality of regions, and at least one respective point of the distinct points is in each of the respective regions; and

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

16. The computer readable storage medium of claim 15, wherein one or more of the region classifiers is configured to compute probability estimates according to a calculation formula of the form F(X)=Σ

_mw_mh_m(X), where m ranges over a respective set of base station pairs, each w_m is a non-negative real number, X is a variable representing a set of test signal strength measurements, and each h_m(X) is 1 or 0 depending on whether the difference between signal strengths from the corresponding pair of base stations is greater than a corresponding threshold value θ

_m.

17. The computer readable storage medium of claim 15, wherein the instructions for training comprise instructions for iteratively selecting parameters that minimize the total error for the training set.

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

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

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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 region classifiers for distinct regions yield similar high-probability estimates;

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

reapplying the region classifiers using the additional signal strength measurements.

20. The computer readable storage medium of claim 15, wherein each region is part of a unique aggregate region, and each aggregate region 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 signal strength measurements from at least a subset of the base stations, the measurements taken by a mobile device at an unknown point in the building;

selecting pairs of received signal strength measurements, and for each pair, subtracting one of the signal strength measurements from the other signal strength measurement, 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.

22. A method of identifying a location of a mobile device in a building, performed at a server having one or more processors and memory, the method comprising:

receiving base station signal strength measurements taken at a plurality of distinct points in the building, wherein the signals are received from a plurality of radio-transmitting base stations in the building, the building is partitioned into a plurality of regions, and at least one respective point of the distinct points is in each of the respective regions; and

building a respective known signal strength vector for each respective point comprising an ordered sequence of the base station identifiers, wherein the base station identifiers within each respective known signal strength vector are ordered by the signal strengths of the corresponding base stations as measured at the respective point;

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

building a test signal strength vector comprising an ordered sequence of the base station identifiers, wherein the base station identifiers are ordered by the corresponding signal strengths;

computing an edit distance between the test signal strength vector and at least a subset of the known signal strength vectors, wherein the edit distance between a pair of signal strength vectors comprises the minimum number of atomic operations required to transform one of the signal strength vectors in the pair into the other signal strength vector in the pair;

selecting k known signal strength vectors whose corresponding edit distances from the test signal strength vector are the smallest of the computed edit distances, where k is a positive integer;

determining a likely region where the mobile device is located based on the regions corresponding to the k known signal strength vectors; and

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