Method and system for determining user location in a wireless communication network

• US 7,406,116 B2
• Filed: 03/26/2004
• Issued: 07/29/2008
• Est. Priority Date: 03/28/2003
• Status: Expired due to Fees

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Youssef, Moustafa, Agrawala, Ashok K
• Primary Examiner(s): VO, DON NGUYEN
• Application Number:
  US10/529,372
• Publication Number:
  US 20050243936A1
• Time in Patent Office: 1,586 Days
• Field of Search: 375/213, 375/224, 342/357.01, 342/357.08, 342/357.17, 342/386, 342/450, 455/456.3
• US Class Current: 375/213
• CPC Class Codes: H04B 17/318 Received signal strength
• CPC Class Codes: H04L 27/2601 Multicarrier modulation systems
• 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

In a wireless communication network, the location of an addressable receiver relative to the locations of a plurality of addressable sources of electromagnetic radiation is found using probabilistic models of the signal strength measured at the addressable receiver. The inventive method provides location determination on a finer spatial scale than was heretofore available. A region of interest is calibrated via a discrete-space radio map storing probability distributions of received signal strength at the measurement locations. The stored probability distributions are compensated for temporal variability and biases, such as through temporal correlations of the sampled received signal strength. A measurement of the signal strength at the addressable receiver from each of the plurality of addressable sources is used in conjunction with the discrete-space radio map to identify one of the coordinates thereof that maximizes the conditional probability P(xls), where x is the radio map location and s is a vector of measured signal strengths.

Claims

1. A method for locating an addressable receiver of electromagnetic radiation relative to locations of a plurality of addressable sources of the electromagnetic radiation in a wireless communication network, the method comprising the steps of:

establishing a plurality of radio maps having coordinates corresponding to locations in space at which a calibration signal strength from each of a set of the plurality of addressable sources is measured, each of said radio maps having stored at said coordinates thereof a probability distribution of said calibration signal strength from a corresponding one of said set of said plurality of addressable sources;

measuring a received signal strength of each of said set of addressable sources at the addressable receiver;

compensating said received signal strength measurement of each of said set of addressable sources for temporal variations therein; and

identifying one of said coordinates of said plurality of radio maps corresponding to a location in space at which said compensated signal strength measurement of said set of addressable sources would be measured with maximum probability given said probability distribution of calibration signal strength of said set of addressable sources thereat, said identified coordinate being a discrete-space estimate of the location of the addressable receiver.

2. The method for locating an addressable receiver as recited in claim 1, whereby said probability distribution is a histogram of said calibration signal strength at each of said plurality of coordinates.

3. The method for locating an addressable receiver as recited in claim 1, whereby said probability distribution is a continuous probability distribution modeled from said calibration signal strength measurements from each of the plurality of addressable sources at each of said plurality of coordinates.

4. The method for locating an addressable receiver as recited in claim 3, whereby said radio map establishing step includes the steps of:

averaging a predetermined averaging number of said calibration signal strength measurements for each of said plurality of coordinates;

calculating m autoregression coefficients, m being an integer value, for an autoregressive model of order m of said averaged calibration signal strength measurements for each of said set of addressable sources at each of said plurality of coordinates; and

modeling said continuous probability distribution for each of said plurality of coordinates from said averaging number and said m autoregression coefficients.

5. The method for locating an addressable receiver as recited in claim 4, whereby said received signal strength measurement compensating step includes the step of averaging said predetermined averaging number of said received signal strength measurements for each of said set of addressable sources.

6. The method for locating an addressable receiver as recited in claim 4, whereby said modeled continuous probability distribution is interpolated via an interpolation function applied between a predetermined number of adjacent ones of said plurality of coordinates of said radio map to establish a continuous-space location estimate of the addressable receiver.

7. The method for locating an addressable receiver as recited in claim 6, whereby said interpolation function is a linear function of space between said adjacent ones of said plurality of coordinates of said radio map.

8. The method for locating an addressable receiver as recited in claim 4, whereby said order m of said autoregressive model is unity (m=1).

9. The method for locating an addressable receiver as recited in claim 8, whereby said modeled continuous probability distribution is Gaussian.

10. The method for locating an addressable receiver as recited in claim 9, whereby said autoregression coefficient is equated to a one-sample lag autocorrelation coefficient of said averaged calibration signal strength measurements.

11. The method for locating an addressable receiver as recited in claim 10, whereby said modeled Gaussian probability distribution has a mean value equal to a mean value of said calibration signal strength measurements and has a variance equal to a variance of said calibration signal strength measurements multiplied by a function of said averaging number and said one-sample lag autocorrelation coefficient.

12. The method for locating an addressable receiver as recited in claim 11, whereby said function of said averaging number and said one-sample lag autocorrelation coefficient is:

$\frac{1}{n^2}<br><br>\left\{{\left(\frac{1-{\mathrm{\alpha <br><br>}}^n}{1-\mathrm{\alpha <br><br>}}\right)}^2+n-1-{\mathrm{\alpha <br><br>}}^2<br><br>\frac{1-{\mathrm{\alpha <br><br>}}^{2<br><br>\left(n-1\right)}}{1-{\mathrm{\alpha <br><br>}}^2}\right\},$

where n is said averaging number and α

is said one-sample lag autocorrelation coefficient.

13. The method for locating an addressable receiver as recited in claim 9, whereby said modeled Gaussian probability distribution of said calibration signal strength is interpolated via a continuously variable estimate of a mean value of said Gaussian probability function applied between a predetermined number of adjacent ones of said plurality of coordinates of said radio map to establish a continuous-space location estimate of the addressable receiver.

14. The method for locating an addressable receiver as recited in claim 13, whereby predetermined number of adjacent ones of said plurality of coordinates is three, said three coordinates forming vertices of a triangle, said continuous-space location estimate of the addressable receiver being located in said triangle corresponding to a location in space at which said compensated signal strength measurement of said set of addressable sources would be measured with maximum probability given said probability distribution of calibration signal strength of said set of addressable sources thereat.

15. The method for locating an addressable receiver as recited in claim 1 further including the steps of:

comparing said discrete-space location estimate to a previously identified discrete-space location estimate;

adding a perturbation value to said received signal strength measurements of each of said addressable sources if said previously calculated discrete-space location estimate is separated from said discrete-space location estimate by greater than a predetermined value;

compensating said perturbed received signal strength measurements for temporal variations therein; and

repeating the method at said coordinate identifying step using said compensated perturbed received signal strength measurements as said compensated signal strength measurement of each of said addressable source.

16. The method for locating an addressable receiver as recited in claim 1, whereby said coordinate identifying step further includes the steps of:

selecting a predetermined clustering number of said set of addressable sources from which said predetermined clustering number of greatest average received signal strengths are measured as a cluster key;

forming a cluster of said coordinates of said radio map corresponding to each of said set of addressable sources at which a calibration signal measurement taken thereat is among said predetermined clustering number of greatest calibration signal measurements in each radio map corresponding to a respective one of said addressable sources in said cluster key; and

evaluating only said coordinates of said cluster to identify said one of said coordinates.

17. The method for locating an addressable receiver as recited in claim 1, whereby said coordinate identifying step further includes the steps of:

selecting one of said set of addressable sources from which a greatest average received signal strength is measured as a first addressable source of a cluster key;

forming a cluster of said coordinates of said radio map corresponding to said first addressable source of said cluster key;

appending to said cluster key one of said set of addressable sources from which a next greatest average received signal strength is measured;

deleting from said cluster all of said coordinates therein for which said calibration signal measurement is less than said calibration signal measurements of said addressable sources in said appended cluster key;

repeating the method at said cluster key appending step until said cluster contains only a predetermined number of coordinates; and

evaluating only said coordinates of said cluster to identify said one of said coordinates.

18. A method for locating an addressable source of electromagnetic radiation relative to locations of a plurality of addressable receivers of the electromagnetic radiation in a wireless communication network, the method comprising the steps of:

establishing a plurality of radio maps having coordinates corresponding to locations in space at which a calibration signal strength from the addressable source is measured at each of a set of the plurality of addressable receivers, each of said radio maps having stored at said coordinates thereof a probability distribution of said calibration signal strength measured at a corresponding one of said set of said plurality of addressable receivers;

measuring a received signal strength of the addressable source at each of said set of addressable receivers;

compensating said received signal strength measurement of the addressable source at each of said set of addressable receivers for temporal variations therein; and

identifying one of said coordinates of said plurality of radio maps corresponding to a location in space at which said compensated signal strength of the addressable source would be measured at said set of addressable receivers with maximum probability given said probability distribution of calibration signal strength of said addressable source at said set of addressable receivers, said identified coordinate being a discrete-space estimate of the location of the addressable source.

19. The method for locating an addressable source as recited in claim 18, whereby said probability distribution is a histogram of said calibration signal strength at each of said plurality of coordinates.

20. The method for locating an addressable source as recited in claim 18, whereby said probability distribution is a continuous probability distribution modeled from said calibration signal strength measurements from the addressable source at each of said set of addressable receivers for each of said plurality of coordinates.

21. The method for locating an addressable source as recited in claim 20, whereby said radio map establishing step includes the steps of:

averaging a predetermined averaging number of said calibration signal strength measurements for each of said plurality of coordinates;

calculating m autoregression coefficients, m being an integer value, for an autoregressive model of order m of said averaged calibration signal strength measurements for the addressable source at each of said plurality of coordinates; and

modeling said continuous probability distribution for each of said plurality of coordinates from said averaging number and said m autoregression coefficients.

22. The method for locating an addressable source as recited in claim 21, whereby said received signal strength measurement compensating step includes the step of averaging said predetermined averaging number of said received signal strength measurements from the addressable source at each of said set of addressable receivers.

23. The method for locating an addressable source as recited in claim 21, whereby said modeled continuous probability distribution is interpolated via an interpolation function applied between a predetermined number of adjacent ones of said plurality of coordinates of said radio map to establish a continuous-space location estimate of the addressable source.

24. The method for locating an addressable source as recited in claim 23, whereby said interpolation function is a linear function of space between said adjacent ones of said plurality of coordinates of said radio map.

25. The method for locating an addressable source as recited in claim 21, whereby said order m of said autoregressive model is unity (m=1).

26. The method for locating an addressable source as recited in claim 25, whereby said modeled continuous probability distribution is Gaussian.

27. The method for locating an addressable source as recited in claim 26, whereby said autoregression coefficient is equated to a one-sample lag autocorrelation coefficient of said averaged calibration signal strength measurements.

28. The method for locating an addressable source as recited in claim 27, whereby said modeled Gaussian probability distribution has a mean value equal to a mean value of said calibration signal strength measurements and has a variance equal to a variance of said calibration signal strength measurements multiplied by a function of said averaging number and said one-sample lag autocorrelation coefficient.

29. The method for locating an addressable source as recited in claim 28, whereby said function of said averaging number and said one-sample lag autocorrelation coefficient is:

$\frac{1}{n^2}<br><br>\left\{{\left(\frac{1-{\mathrm{\alpha <br><br>}}^n}{1-\mathrm{\alpha <br><br>}}\right)}^2+n-1-{\mathrm{\alpha <br><br>}}^2<br><br>\frac{1-{\mathrm{\alpha <br><br>}}^{2<br><br>\left(n-1\right)}}{1-{\mathrm{\alpha <br><br>}}^2}\right\},$

where n is said averaging number and α

is said one-sample lag autocorrelation coefficient.

30. The method for locating an addressable source as recited in claim 26, whereby said modeled Gaussian probability distribution of said calibration signal strength is interpolated via a continuously variable estimate of a mean value of said Gaussian probability function applied between a predetermined number of adjacent ones of said plurality of coordinates of said radio map to establish a continuous-space location estimate of the addressable source.

31. The method for locating an addressable source as recited in claim 30, whereby predetermined number of adjacent ones of said plurality of coordinates is three, said three coordinates forming vertices of a triangle, said continuous-space location estimate of the addressable source being located in said triangle corresponding to a location in space at which said compensated signal strength measurement of the addressable source would be measured at said set of addressable receivers with maximum probability given said probability distribution of calibration signal strength of the addressable source at said set of addressable receivers.

32. The method for locating an addressable source as recited in claim 18 further including the steps of:

comparing said discrete-space location estimate to a previously identified discrete-space location estimate;

adding a perturbation value to said received signal strength measurements of the addressable source if said previously calculated discrete-space location estimate is separated from said discrete-space location estimate by greater than a predetermined value;

compensating said perturbed received signal strength measurements for temporal variations therein; and

repeating the method at said coordinate identifying step using said compensated perturbed received signal strength measurements as said compensated signal strength measurement of the addressable source.

33. The method for locating an addressable source as recited in claim 18, whereby said coordinate identifying step further includes the steps of:

selecting a predetermined clustering number of said set of addressable receivers from which said predetermined clustering number of greatest average received signal strengths are measured as a cluster key;

forming a cluster of said coordinates of said radio map corresponding to each of said set of addressable receivers at which a calibration signal measurement taken thereat is among said predetermined clustering number of greatest calibration signal measurements in each radio map corresponding to a respective one of said addressable receivers in said cluster key; and

evaluating only said coordinates of said cluster to identify said one of said coordinates.

34. The method for locating an addressable source as recited in claim 18, whereby said coordinate identifying step further includes the steps of:

selecting one of said set of addressable receivers at which a greatest average received signal strength is measured as a first addressable receiver of a cluster key;

forming a cluster of said coordinates of said radio map corresponding to said first addressable receiver in said cluster key;

appending to said cluster key one of said set of addressable receivers at which a next greatest average received signal strength is measured;

deleting from said cluster all of said coordinates therein for which said calibration signal measurement is less than said calibration signal measurements of said addressable receivers in said appended cluster key;

repeating the method at said cluster key appending step until said cluster contains only a predetermined number of coordinates; and

evaluating only said coordinates of said cluster to identify said one of said coordinates.

35. A system for locating a user in a wireless communication network comprising:

a computing device having a wireless network interface card installed therein, said wireless network interface card adapted to the wireless communication network;

a plurality of access points for communicating signals between said wireless network interface card and the wireless communication network;

a radio map builder for establishing a plurality of radio maps having coordinates corresponding to locations in space at which a calibration signal strength as measured between each of a set of said plurality of access points and said wireless network interface card, each of said radio maps having stored at said coordinates thereof a probability distribution of said calibration signal strength for each of said plurality of access points;

a radio map database for storing said plurality of radio maps therein;

a correlation modeler for performing time-series analysis on said calibration signal measurement and compensating said calibration signal measurement for temporal variations therein;

a correlation handler for compensating a location determination signal between said wireless network interface card and each of said access points; and

a discrete-space estimator for providing a discrete-space estimate of the user location by identifying one of said coordinates of said plurality of radio maps corresponding to a location in space at which said compensated location determination signal would be measured with maximum probability given said probability distribution of calibration signal strength measurements between said wireless network interface card and said plurality of access points stored in said corresponding radio maps.

36. The system for locating a user in a wireless communication network as recited in claim 35 further comprising:

a clustering module for selecting as a cluster key a predetermined clustering number of access points at which said predetermined clustering number of greatest signal strengths between said wireless network interface card and said access point was measured and for grouping together into a cluster coordinates of said radio maps corresponding to each of said set of access points at which said calibration signal measurement is among said predetermined clustering number of greatest calibration signal measurements in each radio map corresponding to a respective one of said access points in said cluster key; and

a clustering database for storing a plurality of clusters and corresponding cluster keys therein.

37. The system for locating a user in a wireless communication network as recited in claim 35 further comprising a small-scale compensator for adjusting said location determination signal for spatial variations therein when a previously calculated discrete-space estimate is spatially removed from said discrete-space estimate by greater than a predetermined threshold.

38. The system for locating a user in a wireless communication network as recited in claim 35 further comprising a continuous-space estimator for applying an interpolation function between a predetermined number of adjacent ones of said plurality of coordinates of said radio map to establish a continuous-space estimate of the user location.

39. The system for locating a user in a wireless communication network as recited in claim 35, wherein said plurality of access points and said wireless network interface card are compliant with Institute of Electrical and Electronics Engineers'"'"' 802.11 standard.