Method and system for radio map filtering via adaptive clustering

• US 7,155,239 B2
• Filed: 05/28/2004
• Issued: 12/26/2006
• Est. Priority Date: 05/28/2004
• Status: Expired due to Fees

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Inventors: Goren, David P., Zeng, Guang, Vu, Hoai Xuan
• Primary Examiner(s): Kincaid, Lester G.
• Assistant Examiner(s): SHEDRICK, CHARLES TERRELL
• Application Number:
  US10/856,965
• Publication Number:
  US 20050266855A1
• Time in Patent Office: 942 Days
• Field of Search: 455/456.1, 455/456, 707/5
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method for estimating a location of a wireless device in a wireless local network is provided. The method includes forming a first set comprised of the signal strength received from access points that the wireless device received a signal from and an indicator of no signal strength measured for access points that the wireless device did not receive a signal from. Next, a scan subset can be formed comprised of access points in the first set that has associated signal strength. Next, a cluster comprised of the calibration points can be formed based on the scan subset. A distance between the first set and each of the calibration point in the cluster can be calculated. Then, the smallest distance can be selected as the location estimate.

Claims

1. A method for determining a location estimation of a wireless device in a wireless location system having a plurality of reference devices, the method comprising:

receiving signals from one or more of the plurality of reference devices at the wireless device;

forming a first set comprising a plurality of elements, each element of the plurality of elements comprising a signal strength measurements of signals received at the wireless device from each of the plurality of reference devices from which the wireless device receives signals and an indicator of no signal strength measured for each of the plurality of reference devices from which the wireless device does not receive signals;

forming a scan subset comprising each of the plurality of reference devices in the first set that has an associated signal strength measurement;

forming a cluster set comprising calibration points selected from a plurality of calibration points based on the scan subset, wherein the plurality of calibration points comprise a set of received signal strength measurements from signals received at the calibration points from each of the plurality of reference devices; and

calculating a calculated distance between the first set and each of the calibration points in the cluster set, when the cluster set has at least one element;

calculating the calculated distance between the first set and each of the plurality of calibration points, when the cluster set has no elements; and

selecting the calibration point having the smallest calculated distances as the location estimation.

2. The method of claim 1 wherein the step of forming a cluster set further comprises forming a cluster set comprising calibration points selected from the plurality of calibration points that contain exactly the same reference devices as the scan subset.

3. The method of claim 1 wherein the step of forming a first set further comprises detecting newly installed reference devices by identifying signals from reference devices that did not appear in any calibration point within the plurality of calibration points.

4. The methods of claim 1 wherein the step of forming a scan subset further comprises forming a scan subset comprising each of the plurality of reference devices in the first set that has an associated signal strength measurement above a fixed threshold.

5. A system for estimating a location of a wireless device in a wireless network comprising:

a plurality of reference devices distributed throughout the wireless network, each of the plurality of reference devices operable to send a signal;

a plurality of calibration points distributed throughout the wireless network, the calibration points comprising a set of received signal strength measurements from signals received from each of the plurality of reference devices; and

the wireless device located in the network, the wireless device configured to;

form a scan set comprising a received signal strength indicator (RSSI) value from each of the plurality of reference devices from which the wireless device receives signals from and an indicator of no signal received from each of the plurality of reference devices that the wireless device does not receive signals as elements of the scan set;

form a scan subset of the scan set comprising reference devices in the scan set that have associated signal strength;

form a cluster set comprising calibration points selected from the plurality of calibration points based on the scan subset;

determine an estimated location by selecting the smallest distance between the scan subset and each of the calibration points in the cluster set, when the cluster set has at least one element; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the plurality of calibration points, when the cluster set has no elements.

6. The system of claim 5 wherein the cluster set comprises calibration points selected from the plurality of calibration points that contain the exact same reference devices as the scan subset.

7. The system of claim 6 wherein the scan set contains reference devices having an RSSI above a fixed threshold.

8. The system of claim 5 wherein any reference devices in the scan set that are not in the plurality of calibration points are considered newly installed reference devices.

9. The system of claim 5 wherein the wireless device is a radio frequency identification tag.

10. The system of claim 5 wherein the wireless device is a handheld computer unit.

11. The system of claim 5 wherein the wireless device is a computer with a wireless network transceiver.

12. The system of claim 5 wherein the distance is calculated as the square of the distance between the scan subset and each of the calibration points in the system.

13. The system of claim 5 wherein the reference device comprises an access point of a wireless network.

14. A wireless device for use in a wireless network, the wireless device comprising:

a memory configured to store a plurality of calibration points, each of the plurality of calibration points including a set of received signal strength indicator (RSSI) values for signals received from each of a plurality of reference devices;

a receiver configured to receive signals from one or more of the plurality of reference devices; and

a processor coupled to the receiver and the memory, the processor operable to;

determine RSSI values for each of the signals received from the one or more of the plurality of reference devices;

form a scan set comprising the RSSI value from each of the plurality of reference devices that the receiver received signals from and further comprising an indicator of no signal received from each of the plurality of reference devices that the receiver did not receive signals;

form a scan subset comprising reference devices in the scan set that have an associated RSSI value;

form a cluster set comprising calibration points selected from the plurality of calibration points based on the scan set;

determine an estimated location by selecting the smallest distance between the scan subset and each of the calibration points of the cluster set, when the cluster set has at least one element; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the plurality of calibration points, when the cluster set has no elements.

15. The device of claim 14 wherein the wireless device is part of a radio frequency identification tag.

16. The device of claim 14 wherein the wireless device is a wireless data entry terminal.

17. A method for estimating a location of a wireless device in a wireless location system having a plurality of reference devices and a plurality of calibration points, each of the calibration points associated with a set of received signal strength measurements received at the calibration point from each of the plurality of reference devices from which a signal can be receive, the method comprising:

forming a first set comprising a plurality of elements, each element of the plurality of elements corresponding to signal strength measurements of signals received at the wireless device from each of the plurality of reference devices from which the wireless device receives signals and an indicator of no signal strength measured for any of the plurality of reference devices from which the wireless device does not receive signals;

forming a scan subset comprising each of the plurality of reference devices in the first set that has an associated signal strength measurement above a first fixed threshold;

forming a cluster set by;

forming one or more first calibration subset for each calibration point comprising reference devices that have an associated signal strength above a second fixed threshold;

forming one or more second calibration subset for each calibration point comprising reference devices having an available received signal strength indicator;

selecting calibration points that include reference devices that are in the scan subset and contained in the one or more second calibration subset and where a difference between the number of reference devices that belong to the one or more first calibration subset that do not belong to the intersection of the reference devices in the scan subset and the reference devices in the one or more first calibration subset is equal to or does not exceed a fixed portion of the total reference devices; and

calculating a calculated distance between the first set and each of the calibration points in the cluster set when the cluster set has at least one element;

calculating the calculated distance between the first set and each of the plurality of calibration points when the cluster set has no elements; and

selecting the smallest of the calculated distances as a location estimate.

18. A wireless device for use in a wireless network, the wireless device comprising:

a memory configured to store a plurality of calibration points, each of the plurality of calibration points including a set of received signal strength indicator (RSSI) values for signals received from each of a plurality of reference devices;

a receiver configured to receive signals from one or more of the plurality of reference devices; and

a processor coupled to the receiver and the memory, the processor operable to;

determine a received signal strength indicator (RSSI) value for each of the signals received from the one or more of the plurality of reference devices;

form a scan set comprising the RSSI value from each of the plurality of reference devices that the receiver received a signal from and further comprising an indicator of no signal received from each of the plurality of reference devices that the receiver did not receive a signal;

form a scan subset comprising reference devices in the scan set that have an associated RSSI value above a first fixed threshold;

form one or more first calibration subset for each calibration point comprising reference devices that has an associated signal strength above a second fixed threshold; and

form one or more second calibration subset for each calibration subset comprising reference devices having an available received signal strength indicator (RSSI); and

form a cluster set by selecting calibration points that include reference devices that are in the scan subset and contained in the one or more second calibration subset and where a difference between the number of reference devices that belong to the one or more first calibration subset that do not belong to the intersection of the reference devices in the scan subset and the reference devices in the one or more first calibration subset is less than or equal to a fixed portion of the total reference devices; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the calibration points of the cluster set when the cluster set has at least one element; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the plurality of calibration points when the cluster set has no elements.