System and method of estimating the position of a mobile terminal in a radio telecommunications network

[0001] 1. Technical Field of the Invention

[0002] This invention relates to telecommunication systems. More particularly, and not by way of limitation, the present invention is directed to a system and method of estimating the position of a mobile terminal in a radio telecommunications network.

[0003] 2. Description of Related Art

[0004] In modern radio telecommunication systems, the service area is divided into cells, each of which is served by a base station transceiver. As mobile terminals move about the service area of the system, they are handed off from one cell to another so that there is no lapse in service. In times of emergency, it would be extremely useful to police or other emergency crews responding to the situation to have precise position information for the mobile terminal. For this reason, the Federal Communications Commission (FCC) has mandated that cellular carriers be able to locate the position of a mobile terminal operating in their service areas to within a few hundred feet when the mobile terminal makes an emergency 911 (E911) call. The FCC mandate requires the position of the 911 caller to be computed and passed on to an emergency network operator.

[0005] One solution being considered by carriers operating Time Division Multiple Access (TDMA) networks is to locate mobile terminals using Received Signal Strength (RSS) measurements for signals transmitted by base stations and received at the mobile terminal. Of course, RSS-based position location, once implemented, can also be used for commercial location-based services.

[0006] A major problem with existing solutions for locating mobile terminals is the high cost and complexity required for their implementation into the existing cellular network infrastructure. Some solutions require extensive modifications to base stations or other components of the cellular telecommunication system. Others require extensive modifications to mobile terminals and are inadequate due to the large number of unmodified mobile terminals already in service.

[0007] Position location systems in general require multiple measurements either by the mobile terminal whose position is being determined, or by a set of fixed transceivers (base stations). The measurements are made on signals sent between the base stations and the mobile terminal. The measurements may include time of arrival, angle of arrival, or the signal strength of the received signal. Combinations of all three types may be used as well.

[0008] In general, the computation of the mobile terminal's position involves minimizing some error criterion given a set of functions that define the dependence of the measurements on the true position of the mobile terminal. For example, in the case of time of arrival measurements, this function is the difference between the time of the transmission and the time of reception of the radio signal which is simply the distance between the base station and the mobile terminal divided by the speed of light. While such functions exist for the case of RSS measurements (for example, the Okumura-Hata formula), they typically vary significantly with terrain. Also, when characterized accurately for each location (rather than in a statistical sense for a whole area), the functions generally do not have a convenient closed form mathematical expression. This is due to the large variance in RSS caused by fixed objects around the mobile terminal in each specific location.

[0009] In order to overcome the disadvantage of existing solutions, it would be advantageous to have a system and method of determining the position of a mobile terminal in a radio telecommunications network that can operate in an environment with high location-specific anomalies with a high degree of accuracy. The present invention provides such a system and method.

[0010] In one aspect, the present invention is directed to a method of determining the position of a mobile terminal operating in the coverage area of a radio telecommunications network having a plurality of base station transceivers. The method begins by determining, for a plurality of positions throughout the coverage area of the network, expected Received Signal Strength (RSS) values of a signal transmitted by base station transceivers and received at a typical mobile terminal. Alternatively, the method may determine for a plurality of positions throughout the coverage area of the network, expected RSS values of a signal transmitted by the mobile terminal and received at the base station transceivers. The expected RSS values may be predicted values, or values measured from a test mobile terminal, or both. The expected RSS values are then stored at a plurality of locations in a database. If both predicted and measured values are stored, an indication is stored indicating whether each RSS value is predicted or measured.

[0011] After the database is populated, the system is ready to position mobile terminals in real-time. When a mobile terminal needs to be positioned, RSS measurements made by the mobile terminal on signals transmitted by the base stations are sent back to the cellular network. The RSS measurements obtained from the mobile terminal are compared with the expected RSS values stored in the database, and the position of the mobile terminal is then estimated based on differences between the RSS measurements and the expected RSS values.

[0012] In one embodiment, the RSS measurements obtained from the mobile terminal are compared with the expected RSS values stored in the database by first storing, for each sector of the database, a first expected measurement variance for all locations in the database that are populated with measured values, and storing a second expected measurement variance for all locations in the database that are populated with predicted values. The first expected measurement variance is used in comparing the RSS measurements with the expected RSS values, if the expected RSS values are measured values. If the expected RSS values are predicted values, the second expected measurement variance is used in the comparison.

[0013] The position estimation may be performed by first determining whether the percentage of locations in the database that are populated with measured values exceeds a predefined threshold. If so, a maximum-likelihood estimator may be utilized to estimate the position. If the percentage of locations in the database that are populated with measured values does not exceed the predefined threshold a minimum-mean-square-error estimator may be utilized to estimate the position.

[0014] In another aspect, the present invention is directed to a system for estimating the position of a mobile terminal operating in the coverage area of a radio telecommunications network. The system includes means for determining expected RSS values of signals transmitted by the base station transceivers and received by a typical mobile terminal, for a plurality of positions throughout the coverage area of the network; means for storing the expected RSS values at a plurality of locations in a database; and means for measuring at the mobile terminal for which the position is to be estimated, the RSS of signals transmitted by the base station transceivers in the network. The system also includes means for comparing the RSS measurements obtained by the mobile terminal with expected RSS values, and estimating the position of the mobile terminal based on differences between the RSS measurements and the expected RSS values.

[0015] In yet another aspect, the present invention is directed to a method of populating a database with expected RSS values for a typical mobile terminal operating in the coverage area of a radio telecommunications network. The method begins by determining, for a plurality of positions throughout the coverage area of the network, expected RSS values of a signal transmitted by the network's base station transceivers and received by the typical mobile terminal. This step may include the steps of predicting the expected RSS values for a first portion of the positions with a computer-aided prediction tool, and taking actual measurements of the RSS of signals transmitted by the base station transceivers and received by a test mobile terminal for a second portion of the positions. The predicted and measured expected RSS values are then stored at a plurality of locations in the database. The method may also include the step of tagging each location in the database to indicate whether the stored RSS value is a predicted value or a measured value.

[0016] The invention will be better understood and its numerous objects and advantages will become more apparent to those skilled in the art by reference to the following drawings, in conjunction with the accompanying specification, in which:

[0017] FIG. 1 is a flow chart illustrating one embodiment of the method of the present invention for populating a database with expected RSS values and computing the position of a mobile terminal; and

[0018] FIG. 2 is a simplified functional block diagram of an embodiment of the system of the present invention, including a modified Position Determining Equipment (PDE).

[0019] The present invention is a method of estimating the position of a mobile terminal in a radio telecommunications network where location-specific characteristics at different locations cause large variations in RSS at these locations. As noted above, in each specific location, fixed objects around a mobile terminal may cause large variations in the measured RSS of signals from cooperating base stations. Hence, for RSS-based position location, the present invention implements a database that tabulates the expected RSS values at various locations within the coverage area. Once such a database is available, the position of a mobile terminal may be computed by comparing actual RSS measurements made by the mobile terminal to expected RSS values at different locations tabulated in the database, and then estimating the mobile terminal's position using an error minimization algorithm.

[0020] Two approaches may be used to populate the database. In the first approach, the expected RSS for various channels at a certain location, obtained using computer-aided prediction tools, may be used to populate the database. The prediction tools incorporate terrain and clutter data into their prediction model. While this approach is more accurate than using a simple expression such as the Okumura-Hata formula, an even more accurate approach may be utilized in some situations. This second approach is to measure the actual RSS at various points in the coverage area using, for example, a test mobile terminal. While performing measurements and using these measurements to populate the database provides the best accuracy for the database, there are obvious practical limitations to this approach. In practice, both prediction data and measurement data may be used in combination. For example, prediction data may be used to create the database, and measurement data may then be used to re-calibrate the database when measurements become available.

[0021] A Maximum-Likelihood (ML) estimation algorithm or the like may be utilized to estimate the position of the mobile terminal given a set of RSS measurements. However, when the quality of the data populating the database is not very good, as is the case when only prediction data is used to populate the database, a Minimum-Mean-Square-Error (MMSE) estimate is more robust. Also, parameters used in either the ML algorithm or the MMSE algorithm are different depending on what kind of data is used to populate the database. For example, one of the key parameters, measurement noise variance, is set lower when measurement data is used to populate the database and higher when prediction data is used instead. The situation may be further complicated when the database is a hybrid of both prediction and measurement data. The present invention provides techniques to efficiently compute the position of the mobile terminal while taking into account the nature of the data populating the database.

[0022] The database contains the expected received signal strengths, f_i(x_k), for various locations, x_k, in the database. The location, x, is a vector given by x(x, y), when x and y are the latitude and longitude of the mobile terminal, and f_i(x) is the expected RSS for the i^th sector. The term sector refers to the sector of the cellular antenna that transmits the signal to the mobile terminal. Typically, cellular base station transceivers and antennas are located at the center of the cell that they cover. The coverage area, and the cellular antenna, is typically divided into three 120 sectors. However, the number of sectors, and degrees of coverage, may vary based on the antenna deployment in the network. The position of the mobile terminal is computed by measuring the RSS from a number of such antenna sectors.

[0023] When the position of a mobile terminal is to be determined, a set of measurements r_i(x)f_i(x)n_i where i1, 2, . . . N (where N is the number of sectors measured) are given to the Positioning Determining Equipment (PDE) which is the node in the network that computes the position of the mobile terminal. The quantity n_i is the measurement noise and has a Gaussian probability distribution function when the RSS measurements are expressed in dB.

[0024] The PDE must estimate the unknown position, x, from the measurements, r_i. In order to do this the PDE computes a metric for each position, x_k, in the database and estimates the unknown position, x, based on these metrics. The metric, m_k, is the probability of obtaining RSS measurements, r, (when rr₁, r₂ . . . r_n) and the probability that the true position is x_k. The metric, m_k, is defined by the equation:

[0025] where the quantity p(rx_k) is the probability that measurements, r, are received given that the position is x_k, and the quantity p(x_k) is the apriori probability that the mobile terminal is at position x_k. The quantity p(rx_k) is dependent on the characteristics of the noise variable, n_i. Specifically, for RSS measurements, p(rx_k) is specified by a Gaussian probability distribution function that is defined by a covariance matrix, N. The element in row i and column k of the covariance matrix N is E (n_iE(n_i)n_kE(n_k)), i.e., the expected value of the product of the noise variables minus their mean values. When ik, this is the variance of the noise variable, n_i.

[0026] A covariance matrix for two random variables, x and y, takes the form: $\begin{array}{cc}E\left(xx\right)& E\left(xy\right)\\ E\left(yx\right)& E\left(yy\right)\end{array}$

[0027] where E(xx) is the expected value of x times x, E(xy) is the expected value of x times y, and so on. The expected value E(xx) is the sum (or integral) of (p(x)xx) over all possible values of x, where p(x) is the probability density function of x. In covariance matrices for real values, E(xy) and E(xy) are equal, and hence the matrices are symetric.

[0028] When the position, x, is estimated as the point in the database, x_k, that maximizes this metric, the estimate is a Maximum-Likelihood (ML) estimate. When the position, x, is estimated as E(x_kr), i.e., the expected value of the position, x, given the measurements, r, the estimate is a Minimum-Mean-Square-Error (MMSE) estimate. The quantity E(x_kr) can be computed as _k(m_kx_k)/_km_k, i.e., as a function of the metrics, m_k, for all the points being considered in the database. Note that the contribution of any particular location, x_k, may be removed by setting the apriori probability p(x_k)0. When an MMSE estimate is formed by setting the apriori probabilities for all points except the point with the highest metric, m_k, to zero, the computed position is the same as that for the ML estimate. When a few points that have the highest metrics are chosen, the estimate is not exactly the ML estimate, but is very similar in performance.

[0029] A whole range of estimators between the ML and MMSE estimators can be chosen by varying the number of points considered. When the quality of the measurements is poor and/or the measurements may have biases, the MMSE estimate is more robust and shows better performance in most regions of interest. However, when the measurement quality is good and biases are close to zero, the ML estimate exhibits better performance.

[0030] Marking of Entries in the Database

[0031] The database is essentially a set of sectors and RSS values for these sectors for each physical location in the coverage area of the cellular network. The database may be configured as a table in which each row contains the sectors and RSS values for a single location. A number of rows corresponding to different locations then form the table. In the present invention, each row is marked with a tag that indicates whether the data for that location was populated using prediction algorithms or actual measurements.

[0032] Use of Covariance Matrices in Metric Computation

[0033] In order to compute the position of the mobile terminal, certain entries are selected from the database based upon the identity of the serving sector, the serving RSS, and the number of common neighbors each database entry has with the set of measured sectors. The identity of the serving sector is used to limit the geographical area of the points considered. The measured RSS value in the serving sector is used to limit the points considered to those above a threshold derived from the measured RSS. Lastly, only points with more than a threshold number of common neighbors with the measured sectors are considered. Metrics are computed for these selected points, and the position is subsequently estimated.

[0034] As described earlier, the computation of the metrics requires a covariance matrix, N. Typically, the covariance matrix, N, is different when actual measurements are used instead of predicted values to populate the database. The diagonal elements of the matrix reflect the variance of the measurement errors obtained when measuring the RSS at the mobile terminal. The variances are expected to have lower values when actual measurements are used to populate the database. Performance improvements may also be obtained in some cases by using different covariance matrices for each location since the statistics of the errors in the measurements may be location dependent. Five different methodologies are described below for computing the metrics for each of the points in the database.

[0035] In a first embodiment of the present invention, a separate covariance matrix is stored for each database entry to compute the metrics for each of the locations in the database. When a metric has to be computed for a certain location, the covariance matrix for the corresponding entry is used by extracting the sub-matrix of the covariance matrix whose rows and columns correspond to the sectors that are common between the database entry and the sectors used for the measurement set, r. For example, if the stored covariance matrix is a 33 matrix for the sectors 1, 2 and 3, and the measurements were made on sectors 1 and 3, then, the sub-matrix contains the elements of the covariance matrix indexed by the pairs (1, 1), (3, 3), (1, 3) and (3, 1). This sub-matrix is then used in computing the value of p(rx_k) in order to compute the metric m_k.

[0036] In a second embodiment of the present invention, two covariance matrices are stored for the whole database to compute the metrics for each of the points in the database. One of the covariance matrices pertains to database entries with actual measurement data, and the other covariance matrix pertains to entries with prediction data. Each covariance matrix is larger than the separate covariance matrix that is stored for each database entry in the first embodiment described above. Each matrix contains rows corresponding to all of the sectors in the database. When the metric for a certain location corresponding to a certain database entry is to be determined, the same procedure as described in the first embodiment above may be used. The sub-matrix for the entry is extracted out of the larger covariance matrix that contains information for all the sectors. The covariance matrix is chosen based on the tag for the database entry indicating whether actual measurements or predictions were used to populate the database entry.

[0037] In a third embodiment of the present invention, the covariance matrix is assumed to be a diagonal matrix with different elements for each sector. If the non-diagonal elements, x_ij, (ij) of a square matrix are all zero, the matrix is a diagonal matrix. For example, the following matrix is a diagonal matrix: $\begin{array}{cc}E\left(xx\right)& 0\\ 0& E\left(yy\right)\end{array}$

[0038] As can be seen from this example, there is only the need to store as many elements as there are variables. Thus, the storage size for the covariance matrix is reduced significantly.

[0039] For the present invention, the variables are the errors in the RSS for each of the sectors. Hence, instead of storing a matrix, a single variance value may be stored per sector per location. Assuming, as in the first embodiment above, that the variance is location dependent, a single value is stored for the expected measurement variance of each sector at each location or entry in the database. For example, if there are 20 sectors in the whole system, and 100 locations (grid points) in the area, a total of 2,000 values are stored.

[0040] In a fourth embodiment of the present invention, the covariance matrix is again assumed to be a diagonal matrix with different elements for each sector. It is assumed as in the second embodiment above, that the measurement variance is not location dependent, and therefore a single value is stored in the database for each sector, across all locations. For example, if there are 20 sectors in the whole system, and 100 locations in the area, only 20 values would be stored. Although the variance used is not specific to each location, different values may be stored for measurement and prediction data. The fourth embodiment has the lowest memory storage requirements of the embodiments discussed so far. The storage required for the fourth embodiment is much lower than that required for the third embodiment, just as the storage required for the second embodiment is lower than that required for the first embodiment. Also, the storage required for the third embodiment is lower than that for the first embodiment, and the storage required for the fourth embodiment is lower than that for the second embodiment.

[0041] In a fifth embodiment of the present invention, a single value is used for the variance of all sectors, i.e., it is assumed that the covariance matrix is diagonal with all elements of the diagonal being the same. However, it is assumed that the variance values are different for measurement data and prediction data. Hence, in this embodiment, only two values are stored for the measurement variance. One value is used when computing metrics for entries populated with actual measurement data, and the other value is used when computing metrics for entries populated with prediction data.

[0042] Dynamic Switching of Algorithms

[0043] The selection of the ML or MMSE algorithms may be dynamically switched based on the positions being considered. When the position for a mobile terminal has to be computed, a set of points is selected from the database. Metrics are then computed for these selected points. Then, an ML or an MMSE estimator or some other type of estimator is used to compute the position of the mobile terminal based on these selected points and computed metrics. As discussed above, the criteria used for performing the initial selection of points may include the identity of the serving sector, the measured RSS of the serving sector, and the number of common neighbors each database entry has with the set of measured sectors.

[0044] In the present invention, two different techniques may be utilized, either separately or simultaneously in combination, to optimize positioning performance depending on the set of locations that are selected from the database. A first percentage parameter, V, may be set to a relatively high value such as 80 or 90 percent. When more than V percent of the locations or database entries selected from the database have been populated using actual measurement data, the other selected points (those with prediction data) are not used, i.e., p(x_k) is set to zero for the other points. A second threshold, W, may be set to a lower value. When more than W percent of the locations or database entries selected from the database have been populated using actual measurement data, the ML estimator is used. If fewer than W percent of the locations or database entries selected from the database have been populated using actual measurement data, the MMSE estimator is used.

[0045] FIG. 1 is a flow chart illustrating one embodiment of the method of the present invention for populating the signal strength database with expected RSS values and computing the position of a mobile terminal. At step 11, the database is populated with expected RSS values at different locations throughout the coverage area of the cellular network. The expected RSS values for various channels at each location may be obtained using computer-aided prediction tools. Alternatively, the actual RSS values at various points in the coverage area may be measured and reported using, for example, a test mobile terminal. A combination of predicted and measured data may also be used. At step 12, each row in the database is marked with a tag that indicates whether the data for that location was populated using a prediction algorithm or using actual measurements. Once the database is set up, the positioning procedure shown in the remainder of FIG. 1 may be followed for mobile terminals throughout the network coverage area.

[0046] At step 13, a set of measurements, r, taken by the mobile terminal being located are sent to the PDE for computing the position of the mobile terminal. At step 14, the PDE selects locations x_k from the database using the serving sector, serving RSS, and common neighbor criteria. At step 15, the PDE uses one or more covariance matrices to compute metrics, m_k, for all of the selected points. The type of matrix utilized may vary depending on whether the RSS data is predicted or measured, as described in the five embodiments above. At step 16, it is determined whether more than V percent of the database entries selected from the database were populated using actual measurement data. The parameter, V, is a predefined percentage parameter that may be set to a relatively high value such as 80 or 90 percent. If more than V percent of the selected database entries were populated using actual measurement data, the process moves to step 17 where the selected entries populated with prediction data are not used, i.e., p(x_k) is set to zero for those entries. The process then moves to step 18.

[0047] If it is determined at step 16 that less than V percent of the selected database entries were populated using actual measurement data, the process moves to step 18 where it is determined whether more than W percent of the remaining database entries selected from the database were populated using actual measurement data. The parameter, W, is a predefined percentage parameter that may be set to a value lower than the value of parameter, V. For example, W may be set to a value of 60-70 percent. If more than W percent of the selected database entries were populated using actual measurement data, the process moves to step 19 where the ML estimator is used to compute the position of the mobile terminal using the selected data points. However, if fewer than W percent of the selected database entries were populated using actual measurement data, the MMSE estimator provides a more robust solution. Therefore, the process moves to step 20 where the MMSE estimator is used to compute the position of the mobile terminal using the selected data points.

[0048] Once the position of the mobile terminal has been determined, the process moves to step 21 where it is determined whether or not the position of additional mobile terminals needs to be determined. In practice, the process may wait until there is a mobile terminal that needs to be located, and the process then returns to step 13 where a set of measurements, r, taken by the next mobile terminal to be located are sent to the PDE for computing the position of the mobile terminal. If there are no mobile terminals to be located at step 21, the process ends.

[0049] FIG. 2 is a simplified functional block diagram of an embodiment of the system of the present invention, including a modified Position Determining Equipment (PDE) 31. Predicted RSS values are determined by a Computer-Aided Prediction Tool 32. A Test Mobile Terminal (MT) 34 takes actual measurements of RSS from Base Station Transceivers 33. The predicted RSS values and the actual measurements of RSS are then tagged by a Predicted/Measured Tagging Mechanism 35 to indicate whether each value was predicted or measured. The expected RSS values are then stored in an Expected RSS Database 36. The database may store predicted RSS values, actual RSS measurements, or both. A Database Interface 37 is used to provide the expected RSS values to an RSS Data Selector 38 which selects locations from the database based upon the number of common neighbor cells 39 neighboring the MT's serving sector, and criteria 40 received from the MT's serving Mobile Switching Center (MSC) such as the RSS measured by the MT being located and the MT's serving sector.

[0050] A Metric Calculator 41 uses a Covariance Matrix 42 to compute metrics for the selected RSS values. An Estimator Selector 43 then determines the percentage of selected RSS values that were measured, and if more than a threshold percentage were measured, the selector sends the metrics to a Maximum-Likelihood (ML) Estimation Algorithm 44 to estimate the position of the mobile terminal. If the selector determines that fewer than the threshold percentage of selected RSS values were measured, the selector sends the metrics to a minimum-Mean-square-Error (MMSE) Estimation Algorithm 45 to estimate the position of the mobile terminal. Once a position is determined, the PDE sends the position information to a Mobile Positioning Center (MPC) 47 through an MPC Interface 46. The MPC typically controls a plurality of PDEs within the network for determining the position of mobile terminals throughout the network.

[0051] It is thus believed that the operation and construction of the present invention will be apparent from the foregoing description. While the method, apparatus and system shown and described has been characterized as being preferred, it will be readily apparent that various changes and modifications could be made therein without departing from the scope of the invention as defined in the following claims.