Minimum variance location estimation in wireless networks

• US 7,616,555 B2
• Filed: 10/03/2006
• Issued: 11/10/2009
• Est. Priority Date: 10/03/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hart, Brian Donald
• Primary Examiner(s): HASPEL, AMY C
• Application Number:
  US11/542,721
• Publication Number:
  US 20080080429A1
• Time in Patent Office: 1,134 Days
• Field of Search: 370/203, 370/332, 370/342, 342/350, 342/450, 455/456.1, 455/456.3, 455/426.1
• US Class Current: 370/203
• CPC Class Codes: H04B 17/318 Received signal strength
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

In one embodiment, a method includes receiving received signal strength data, computing an aggregate square error surface based on the received signal strength data, computing a probability surface by applying a probability density function to the aggregate error surface, and computing a mean location of a wireless node.

Claims

1. A data storage medium encoded with computer executable instructions for acquiring information from a wireless network, the computer executable instructions when executed operable to cause a processor to:

collect received signal strength data;

compute an aggregate square error surface based on the received signal strength data, wherein the aggregate square error surface corresponds to a matrix of locations each defined by an x-coordinate and a y-coordinate;

compute a probability surface by computing a probability density function from the aggregate error surface, wherein the probability values of the probability surface are normalized such that a sum of the probability values over an entire surface equals one; and

compute a mean x-coordinate location and a mean y-coordinate location of a wireless node based on the probability surface, wherein the mean x-coordinate location is a sum, for all x-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all y-coordinate values of the matrix, and, wherein the mean y-coordinate location is a sum, for all y-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all x-coordinate values of the matrix.

2. The data storage medium of claim 1 wherein the aggregate error surface characterizes a difference between the received signal strength values and expected received signal strength values.

3. The data storage medium of claim 1 wherein the probability surface is computed based on the following expression:

4. The data storage medium of claim 1 wherein the normalized probability surface is computed based on the following expression:

P(x,y)=Pu(x,y)/Σ

Pu(x,y).

5. A method for estimating a location of a wireless node, comprising:

collecting, by a computing device, received signal strength data;

computing an aggregate square error surface based on the received signal strength data, wherein the aggregate square error surface corresponds to a matrix of locations each defined by an x-coordinate and a y-coordinate;

computing a probability surface by computing a probability density function from the aggregate error surface, wherein the probability values of the probability surface are normalized such that a sum of the probability values over an entire surface equals one; and

computing a mean x-coordinate location and a mean y-coordinate location of a wireless node based on the probability surface, wherein the mean x-coordinate location is a sum, for all x-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all y-coordinate values of the matrix, and, wherein the mean y-coordinate location is a sum, for all y-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all x-coordinate values of the matrix.

6. The method of claim 5 wherein the aggregate error surface characterizes a difference between the received signal strength values and expected received signal strength values.

7. The method of claim 5 wherein the probability surface is computed based on the following expression:

8. The method of claim 5 wherein the normalized probability surface is computed based on the following expression:

P(x,y)=Pu(x,y)/Σ

Pu(x,y).

9. A system comprising:

one or more infrastructure radio transceivers; and

a wireless network infrastructure node operable to;

collect received signal strength data sensed by the one or more infrastructure radio transceivers;

compute an aggregate square error surface based on the received signal strength data, wherein the aggregate square error surface corresponds to a matrix of locations each defined by an x-coordinate and a y-coordinate;

compute a probability surface by computing a probability density function from the aggregate error surface, wherein the probability values of the probability surface are normalized such that a sum of the probability values over an entire surface equals one; and

compute a mean x-coordinate location and a mean y-coordinate location of a wireless node based on the probability surface, wherein the mean x-coordinate location is a sum, for all x-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all y-coordinate values of the matrix, and, wherein the mean y-coordinate location is a sum, for all y-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all x-coordinate values of the matrix.

10. The system of claim 9 wherein the aggregate error surface characterizes a difference between the received signal strength values and expected received signal strength values.

11. The system of claim 9 wherein the probability surface is computed based on the following expression:

12. The system of claim 9 wherein the normalized probability surface is computed based on the following expression:

P(x,y)=Pu(x,y)/Σ

Pu(x,y).

13. A data storage medium encoded with computer executable instructions for acquiring information from a wireless network, the computer executable instructions when executed operable to cause a processor to:

collect received signal strength data for a wireless node;

compute a plurality of aggregate square error surfaces, wherein each of the aggregate square error surfaces corresponds to a matrix of locations each defined by an x-coordinate and a y-coordinate, and wherein one of the plurality of aggregate square error surfaces corresponds to a nominal transmission power, and remaining aggregate square error surfaces each correspond to at least one transmission power above or below the nominal transmission power;

compute an unnormalized probability surface for each of the aggregate square error surfaces;

compute normalized probability surfaces for each of the unnormalized probability surfaces relative to all the probability surfaces, wherein the probability values of the normalized probability surfaces are normalized such that a sum of the probability values over an entire surface equals one;

compute an aggregate probability surface across the normalized probability surfaces at each location bin; and

compute a mean x-coordinate location and a mean y-coordinate location to yield an estimated location of the wireless node based on the aggregate probability surface, wherein the mean x-coordinate location is a sum, for all x-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all y-coordinate values of the matrix, and , wherein the mean y-coordinate location is a sum, for all y-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all x-coordinate values of the matrix.

14. The data storage medium of claim 13 wherein the plurality of aggregate square error surfaces are each composed of one or more error surfaces that characterize differences between the received signal strength values and expected received signal strength values at one or more locations.

15. The data storage medium of claim 13 wherein the probability surface is computed based on the following expression:

16. A method comprising:

collecting received signal strength data for a wireless node;

computing a plurality of aggregate square error surfaces, wherein each of the aggregate square error surfaces corresponds to a matrix of locations each defined by an x-coordinate and a y-coordinate, and wherein one of the plurality of aggregate square error surfaces corresponds to a nominal transmission power, and remaining aggregate square error surfaces each correspond to at least one transmission power above or below the nominal transmission power;

computing an unnormalized probability surface for each of the aggregate square error surfaces;

computing normalized probability surfaces for each of the unnormalized probability surfaces relative to all the probability surfaces, wherein the probability values of the normalized probability surfaces are normalized such that a sum of the probability values over an entire surface equals one;

computing an aggregate probability surface across the normalized probability surfaces at each location bin; and

computing a mean x-coordinate location and a mean y-coordinate location to yield an estimated location of the wireless node based on the aggregate probability surface, wherein the mean x-coordinate location is a sum, for all x-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all y-coordinate values of the matrix, and , wherein the mean y-coordinate location is a sum, for all y-coordinates of the matrix, of the coordinate value of x multiplied by the sum of all normalized probability values across all x-coordinate values of the matrix.

17. The method of claim 16 wherein the plurality of aggregate square error surfaces are each composed of one or more error surfaces that characterize differences between the received signal strength values and expected received signal strength values at one or more locations.