System and method for locating wireless devices

• US 7,683,835 B2
• Filed: 08/15/2007
• Issued: 03/23/2010
• Est. Priority Date: 08/15/2006
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Sharma, Navin Kumar
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Mull; Fred H
• Application Number:
  US11/839,336
• Publication Number:
  US 20080042898A1
• Time in Patent Office: 951 Days
• Field of Search: 342/458, 342463-465
• US Class Current: 342/458
• CPC Class Codes: G01S 5/0284 Relative positioning
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A system and method for locating a wireless device includes estimating respective distances between a wireless device and each of a plurality of access points, based upon respective signal strengths of a plurality of signals received by the wireless device from the plurality of access points. The location of the wireless device is estimated based upon the estimated respective distances and position information of the access points.

Claims

1. A method for locating a wireless device, comprising:

for each access point of a plurality of access points;

receiving, at a managing device, an indication of a strength of a signal received by a wireless device from the access point; and

calculating, at the managing device, a distance between the wireless device and the access point using at least the indication of the strength of the signal; and

determining, at the managing device, a probable location of the wireless device using at least each of the calculated distances, the determining comprising;

determining a plurality of polygons defined by the wireless device and the plurality of access points; and

calculating a weighted center of mass of each polygon of the plurality of polygons, the weighted center of mass of each polygon determined using an assigned weight for a vertex of the polygon;

wherein calculating the weighted center of mass comprises using at least a sum of the indications of the strength of the signals received at the managing device.

2. The method of claim 1, wherein the probable location of the wireless device comprises the probable location of the wireless device in an indoor environment.

3. The method of claim 1, wherein respective locations of each of the plurality of access points, are used to determine the probable location.

4. The method of claim 1, wherein a weighted center of mass of one of the polygons comprises the probable location of the wireless device.

5. The method of claim 1, wherein determining, at the managing device, the probable location of the wireless device further comprises:

determining a subset of the weighted centers of mass;

determining a location polygon using the subset; and

calculating the weighted center of mass of the location polygon, wherein the weighted center of mass of the location polygon comprises the probable location of the wireless device.

6. The method of claim 1, wherein determining, at the managing device, the probable location of the wireless device comprises using a Kalman filter.

7. The method of claim 1, wherein calculating, at the managing device, a distance between the wireless device and the access point comprises using a Kalman filter.

8. The method of claim 1, wherein determining, at the managing device, the probable location of the wireless device further comprises:

calculating a range circle for each access point of the plurality of access points;

determining a plurality of intersection points between two of the range circles; and

calculating a weighted midpoint of a chord between the plurality of intersection points, wherein the weighted midpoint of the chord comprises the probable location of the wireless device.

9. The method of claim 1, wherein determining, at the managing device, a probable location of the wireless device comprises:

using a location of each access point of the plurality of access points;

determining a plurality of polygons;

calculating a weighted center of mass of each polygon of the plurality of polygons;

determining a subset of the weighted centers of mass;

determining a location polygon using the subset; and

calculating the weighted center of mass of the location polygon, wherein the weighted center of mass of the location polygon comprises the probable location of the wireless device, wherein the probable location of the wireless device comprises the probable location of the wireless device in an indoor environment; and

wherein calculating, at the managing device, a distance between the wireless device and the access point further comprises using a Kalman filter.

10. A system for locating wireless devices, comprising:

a managing device comprising;

a processor;

an interface operable to receive, for each access point of a plurality of access points, an indication of a strength of a signal received by a wireless device from the access point; and

a storage device embodying a program of instructions operable, when executed on the processor, to;

calculate, for each access point of the plurality of access points, a distance between the wireless device and the access point using at least the indication of the strength of the signal; and

determine a probable location of the wireless device using at least each of the calculated distances, the determining comprising;

determine a plurality of polygons defined by the wireless device and the plurality of access points; and

calculate a weighted center of mass of each polygon of the plurality of polygons, the weighted center of mass of each polygon determined using an assigned weight for a vertex of the polygon;

wherein calculating the weighted center of mass comprises using at least a sum of the indications of the strength of the signals received at the managing device.

11. The system of claim 10, wherein the probable location of the wireless device comprises a location of the wireless device in an indoor environment.

12. The system of claim 10, wherein the program of instructions is further operable to determine the probable location of the wireless device using a location of each access point of the plurality of access points.

13. The system of claim 10, wherein the program of instructions is further operable to determine the probable location of the wireless device by:

determining a subset of the weighted centers of mass;

determining a location polygon using the subset; and

calculating the weighted center of mass of the location polygon, wherein the weighted center of mass of the location polygon comprises the probable location of the wireless device.

14. The system of claim 10, wherein the program of instructions is further operable to determine the probable location of the wireless device by using a Kalman filter.

15. The system of claim 10, wherein the program of instructions is further operable to calculate, for each access point of the plurality of access points, a distance between the wireless device and the access point using a Kalman filter.

16. A system for locating wireless devices, comprising:

means for receiving, for each access point of a plurality of access points, an indication of a strength of a signal received by a wireless device from the access point;

means for calculating, for each access point of the plurality of access points, a distance between the wireless device and the access point using at least the indication of the strength of the signal;

means for determining a probable location of the wireless device using at least each of the calculated distances;

means for determining a plurality of polygons defined by the wireless device and the plurality of access points; and

means for calculating a weighted center of mass of each polygon of the plurality of polygons, the weighted center of mass of each polygon determined using an assigned weight for a vertex of the polygon;

wherein calculating the weighted center of mass comprises using at least a sum of the indications of the strength of the signals received at the managing device.

17. Logic encoded in a computer-readable media, the logic being operable, when executed on a processor, to:

receive, for each access point of a plurality of access points, an indication of a strength of a signal received by a wireless device from the access point;

calculate, for each access point of the plurality of access points, a distance between the wireless device and the access point using at least the indication of the strength of the signal; and

determine a probable location of the wireless device using at least each of the calculated distances, the determining comprising;

determining a plurality of polygons defined by the wireless device and the plurality of access points; and

calculating a weighted center of mass of each polygon of the plurality of po1ygons, the weighted center of mass of each polygon determined using an assigned weight for a vertex of the polygon;

wherein calculating the weighted center of mass comprises using at least a sum of the indications of the strength of the signals received at the managing device.