Method and system for radio map filtering via adaptive clustering

• US 20050266855A1
• Filed: 05/28/2004
• Published: 12/01/2005
• Est. Priority Date: 05/28/2004
• Status: Active Grant

• 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
• Granted Patent: US 7,155,239 B2
• Time in Patent Office: Days
• US Class Current: 455/456.100
• 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 estimating a location of a wireless device in a wireless location system comprising:

forming a first set comprising the signal strength received from reference devices that the wireless device receives a signal from and an indicator of no signal strength measured for reference devices that the wireless device does not receive a signal from;

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

forming a cluster comprising calibration points selected based on the scan subset; and

calculating the distance between the first set and each of the calibration point in the cluster; and

selecting the smallest distance as a location estimate.

2. The method of claim 1 wherein the step of forming a cluster further comprises forming a cluster comprising 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 scan subset further comprises forming a subset comprising reference devices in the first set that has an associated signal strength above a first fixed threshold.

4. The method of claim 3 wherein the step of forming a cluster further comprises:

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

forming a second calibration subset for each calibration subset comprising reference devices having an available RSSI; and

clustering calibration points where at least every element of the scan subset is in the second calibration subset and where the number of elements that belong to the first calibration subset and do not belong to the intersection of the scan subset and the first calibration subset is equal to or does not exceed a predetermined number.

5. The method of claim 4 wherein the step of clustering calibration points further comprises clustering calibration points that has available RSSI and where the number of elements that belong to the first calibration point and do not belong to the intersection of the scan subset and the first calibration subset is less than or equal to a fixed portion of the total reference devices.

6. 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.

7. The methods of claim 1 further comprise utilizing wireless channel information and the wireless device'"'"'s capabilities to adjust the thresholds and portion.

8. 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 reference devices operable to send a signal;

a plurality of calibration points distributed throughout the wireless network wherein a signal strength received from the reference devices at each of the calibration points forms a radio map; and

the wireless device located in the network operable to;

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

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 cluster points selected from the radio map based on the scan subset; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the calibration points in the cluster set.

9. The system of claim 8 wherein the cluster set comprises calibration points selected that contain the exact same reference devices as the scan subset.

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

11. The system of claim 8 wherein the step of clustering calibration points further comprises clustering calibration points that has available RSSI and where the number of elements that belong to the first calibration point and do not belong to the intersection of the scan subset and the first calibration subset is less than or equal to a fixed portion of the total reference devices.

12. The system of claim 8 wherein any reference devices in the scan set that are not in the radio map are considered newly installed reference devices.

13. The system of claim 8 wherein the wireless device is a radio frequency identification tag.

14. The system of claim 8 wherein the wireless device is a handheld computer unit.

15. The system of claim 8 wherein the wireless device is a computer with a wireless network transceiver.

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

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

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

a memory storing a radio map comprising;

a plurality of calibration points, each of the plurality of calibration points including a set of received signal strength indicator values for each of a plurality of reference devices;

a receiver that receives a RSSI value from each of the plurality of reference devices; and

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

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;

form a cluster set comprising cluster points selected from the radio map base on the scan set; and

determine an estimated location by selecting the smallest distance between the scan subset and each of the cluster points of the cluster set.

19. The device of claim 18 wherein the wireless device is part of a radio frequency identification tag.

20. The device of claim 18 wherein the wireless device is a wireless data entry terminal.