Wireless node location mechanism featuring definition of search region to optimize location computation

• US 20050261004A1
• Filed: 05/18/2004
• Published: 11/24/2005
• Est. Priority Date: 05/18/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Friday, Robert J., Davi, Gregg Scott, Dietrich, Paul F.
• Granted Patent: US 7,433,696 B2
• Time in Patent Office: Days
• US Class Current: 455/456.200
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A wireless node location mechanism that defines a search region to optimize the computations associated with estimating the location of a given wireless node. According to one implementation, a coverage map associated with each radio receiver that records signal strength data is defined out to a threshold signal strength level. Before computing the estimated location of a given wireless nodes, a search region is defined based on the intersection of the coverage maps associated with each radio receiver that detects the wireless node. Some implementations use information provided by the fact that certain radio receivers did not detect the wireless node to further optimize the location estimate. By defining a search region, which is a generally small area relative to the space encompassed by an entire RF environment, the present invention provides several advantages, such as reducing the processing time and/or power to compute estimated locations for wireless nodes.

Claims

1. A method for estimating the location of a wireless node relative to a plurality of radio receivers operative to detect the strength of RF signals, wherein a RF coverage map, corresponding to each of the radio receivers, characterizes the signal strength values for locations in a physical region out to a threshold signal strength level, comprising

collecting signal strength values, detected at a plurality of radio receivers, corresponding to signals transmitted by a wireless node;

defining a search region based on the intersection of the RF coverage maps corresponding to radio receivers that detected signals transmitted by the wireless node;

computing, within the defined search region, the estimated location of the wireless node based on the collected signal strength values and the RF coverage maps corresponding to the plurality of radio receivers.

2. The method of claim 1 wherein the computing step comprises

computing, for each radio receiver, an individual error surface based on the RF coverage map associated with the radio receiver and the signal strength detected by the radio receiver;

aggregating the individual error surfaces to create a total error surface; and

assessing, within the search region, the total error at each location in the total error surface.

3. The method of claim 2 wherein the computing step further comprises finding within the search region the location of the minimum of the total error surface.

4. The method of claim 2 wherein each individual error surface comprises the sum of the squares of the difference between the signal strength values detected by a radio receiver and the signal strength values in a corresponding RF coverage map.

5. The method of claim 1 further comprising

detecting, at a plurality of radio transceivers, the strength of signals transmitted by a wireless node.

6. The method of claim 1 wherein the RF coverage maps each comprise a plurality of location coordinates associated with corresponding signal strength values.

7. The method of claim 6 wherein the RF coverage maps are heuristically constructed.

8. The method of claim 6 wherein the RF coverage maps are based on a mathematical model.

9. The method of claim 1 wherein the signals transmitted by the wireless nodes are formatted according to a wireless communications protocol.

10. The method of claim 9 wherein the wireless communications protocol is the IEEE 802.11 protocol.

11. The method of claim 1 wherein the contribution of each detected signal strength value to the estimated location is weighted according to a weighting function that varies with the signal strength values detected by the radio receivers.

12. The method of claim 11 wherein the computing step comprises

computing, for each radio receiver, an individual error surface based on the RF coverage map associated with the radio receiver and the signal strength detected by the radio receiver;

weighting each of the individual error surfaces according to a weighting function that varies with the signal strength detected by corresponding radio receivers;

aggregating the individual error surfaces to create a total error surface; and

assessing, within the search region, the total error at each location in the total error surface.

13. The method of claim 12 wherein the computing step further comprises finding within the search region the location of the minimum of the total error surface.

14. The method of claim 1 wherein the RF coverage maps are rectangular.

15. The method of claim 14 wherein the aspect ratio of the RF coverage maps are correspond to at least one characteristic of the antennas associated with the corresponding radio receivers.

16. An apparatus facilitating the location of a wireless node in a RF environment, comprising

a plurality of radio receivers comprising at least one antenna, the plurality of radio receivers operative to detect the strength of signals transmitted by wireless nodes and provide the detected signal strengths to a wireless node location model;

wherein a RF coverage map, corresponding to each of the radio receivers, characterizes the signal strength values for locations in a physical region out to a threshold signal strength level, and

a wireless node location module operative to

define a search region based on the intersection of the RF coverage maps corresponding to radio receivers that detected signals transmitted by the wireless node; and

compute within the search region the estimated location of the wireless node based on the collected signal strength values and the RF coverage maps corresponding to the plurality of radio receivers.

17. A method for estimating the location of a wireless node relative to a plurality of radio receivers operative to detect the strength of RF signals, wherein a RF coverage map, corresponding to each of the radio receivers, characterizes the signal strength values for locations in a physical region out to a threshold signal strength value, comprising

collecting signal strength values, detected at a plurality of radio receivers, corresponding to signals transmitted by a wireless node;

defining a search region based on the intersection of the RF coverage maps corresponding to radio receivers that detected signals transmitted by the wireless node; and

computing within the search region the estimated location of the wireless node by comparing, for all unique pairs of radio receivers, the differences in the signal strength values detected by the plurality of radio receivers to corresponding differences in the signal strength values in the RF coverage maps associated with the plurality of radio receivers, wherein the comparison is weighted as a function of at least one of the signal strength values detected by each unique pair of radio receivers.

18. The method of claim 17 wherein the computing step comprises

computing, for all unique pairs of radio receivers, the sum of the squares of the difference between the signal strength values detected by a pair of radio receivers less the difference between the signal strength values within the search region in the RF coverage maps associated with the pair of radio receivers;

combining the sums to create a differential error surface; and

finding within the search region the location corresponding to the minimum of the differential error surface.

19. The method of claim 17 further comprising

detecting, at a plurality of radio transceivers, the strength of signals transmitted by a wireless node.

20. The method of claim 17 wherein the RF coverage maps each comprise a plurality of location coordinates associated with corresponding signal strength values.

21. The method of claim 20 wherein the RF coverage maps are heuristically constructed.

22. The method of claim 20 wherein the RF coverage maps are based on a mathematical model.

23. The method of claim 17 wherein the signals transmitted by the wireless nodes are formatted according to a wireless communications protocol.

24. The method of claim 23 wherein the wireless communications protocol is the IEEE 802.11 protocol.

25. The method of claim 17 wherein each comparison is weighted as a function of at least one of the signal strength values detected by each unique pair of radio receivers.

28. The method of claim 17 wherein the computing step comprises

computing, for all unique pairs of radio receivers, the sum of the squares of the difference between the signal strength values detected by a pair of radio receivers less the difference between the signal strength values, within the search region, in the RF coverage maps associated with the pair of radio receivers;

weighting each of the computed sums based on the lower of the two signal strength values detected by the corresponding pair of radio receivers;

combining the weighted sums to create a differential error surface; and

finding within the search region the location corresponding to the minimum of the differential error surface.

29. In a wireless network environment comprising a plurality of radio receivers deployed within a physical space, a method facilitating location of wireless nodes, the method comprising

defining a location-coordinate model of a physical space, wherein the model includes the locations of a plurality of radio receivers;

determining coverage maps for each of the plurality of radio receivers, wherein the coverage map, for a given radio receiver, defines the expected receive signal strength for locations in the physical space proximal to the given radio receiver;

wherein the boundary of the coverage map is rectangular and defined at least in part by a minimum threshold receive signal strength level;

storing the coverage maps as individual entities in a database.

30. The method of claim 29 wherein the individual entities defining a given coverage map each comprise an identifier corresponding to a radio receiver, the location coordinates of a corner of the coverage map, the number of location bins along a first axis, the number of location bins along a second axis, and a matrix of receive signal strength values.

31. The method of claim 29 wherein the minimum threshold receive signal strength level is the sensitivity of the radio receiver.

32. The method of claim 29 wherein the minimum threshold receive signal strength level is a configurable parameter.

33. The method of claim 29 further comprising

collecting signal strength values, detected at a plurality of radio receivers, corresponding to signals transmitted by a wireless node;

defining a search region based on the intersection of the RF coverage maps corresponding to radio receivers that detected signals transmitted by the wireless node;

computing, within the defined search region, the estimated location of the wireless node based on the collected signal strength values and the RF coverage maps corresponding to the plurality of radio receivers.