Bayesian-update based location prediction method for CDMA systems

[0002] This application is related to U.S. Ser. No. 09/139,107 entitled “Pattern Recognition-Based Geolocation”, filed in the names of T. C. Chiang et al on Aug. 26, 1998. The related application is assigned to the assignee of the present invention and is meant to be incorporated herein by reference.

[0003] 1. Field of the Invention

[0004] The present invention relates to a method for locating a mobile telephone unit within a cellular service area, and more particularly to a method for estimating the location of a mobile unit based upon the probability of its being at a particular location of the service area given a certain set of observed attributes.

[0005] 2. Description of the Related Art

[0006] A cellular telephone system must be able to locate a mobile unit within a cellular service area under various RF propagation conditions such, for example, when an E911 call is made from the mobile unit. Conventional methods for locating a mobile unit are typically based on either a triangulation technique which requires signals from three or more base stations within a designated service area, or an angle of arrival technique which requires at least two base stations. In many areas, the number of base stations the mobile unit can detect is less than two. Furthermore, both the triangulation and angle of arrival techniques inherently suffer from inaccuracies and signal fading which result from multi-path propagation.

[0007] In the above-noted related patent application, RF characteristics pertaining to one or more pilot signals radiated from a base station and specific to a particular location within the service area are detected by a mobile unit and transmitted back to a basestation where they are matched to a known set of RF characteristics and other information stored in a database located, for example, in a base station server. The database contains what is known in the art as attribute information and includes, for example, RF characteristics, e.g. pilot signal strength measurements indicative of power and phase-offset, time delay, angle of arrival and round-trip delay of pilot signals which differentiates one location from another. For convenience, the cellular service area is divided into a rectilinear grid and an exhaustive survey consisting of measurements of different attributes is carried out at each of the grid points (sub-cells) to identify the attribute values associated therewith. This information is stored in the database. It should be noted that collection of this information is an inherently time consuming and costly procedure.

[0008] The present invention is directed to a method of estimating, by a Bayesian probability computation procedure, the location of a mobile unit in the service area of a CDMA cellular telephone system and which, among other things, simplifies the generation of a database and eliminates the need for repeated attribute measurements at all of the grid points (sub-cells) in the cellular service area by using a model based approach.

[0009] In the present invention, for pilot signal strength or power measurements, a model for RF signal propagation which is used to characterize RF environments is first generated. The model is expressed in terms of a number of parameters such as total transmit power levels, pilot channel powers, antenna patterns and gains, antenna orientations, distance loss parameters, shadow fading parameters, etc. Some of these parameters are known to the service provider. Values of the other parameters are determined by carrying out pilot strength measurements along a few representative routes in the service area and adjusting the values of these parameters until they yield a good match between the pilot strength values predicted by the model and the corresponding measurements. In the case of a large and diverse service area, multiple models representing different parts of the sub-area may be needed. Once the optimal parameters have been determined, no more data needs to be collected. A database containing pilot signal visibility probabilities for each grid-point or sub-cell in the service area is next generated and stored in memory by running a simulation for all grid-points or sub-cells in the service area. Next, for the other attributes such as phase offsets, their behavior is characterized through a statistical model of the conditional probability of a mobile unit observing a specific phase-offset given that the mobile is located at a given sub-cell. This model is expressed in terms of a few parameters which, also, need to be determined through measurements. Once again, measurements at a few representative locations in the service area suffice for parameter estimation. Exhaustive measurements are not needed as in the referenced invention. The statistical model, moreover, is computationally straight forward, does not need a database, and can be generated in real time.

[0010] When pilot strength and phase offset measurements reported by a mobile unit are received by a location server, it uses these two models to determine the probability of the mobile units being at different grid-points within the service area given the measurements reported by it.

[0011] In the preferred method, an “a-posteriori” location probability distribution is used as an estimate of the mobile unit's location. If the mobile unit reports multiple sets of measurements made at relatively small time intervals, the location server iteratively computes the location probability distribution. In this process, the “a-posteriori” distribution computed at the end of one step is used as the “a-priori” distribution for the next step. This procedure is referred to herein as the Bayesian-Update Location prediction Method (BLMP).

[0012] FIG. 1 is illustrative of a cellular service area divided into a plurality of cells;

[0013] FIG. 2 is illustrative of the cells shown in FIG. 1 being further divided into sub-cells;

[0014] FIG. 3 is illustrative of an embodiment of the subject invention;

[0015] FIG. 4 is a flow chart illustrative of the method for generating a probability database based on the RF signal propagation in accordance with the subject invention;

[0016] FIG. 5 is a flow chart generally illustrative of the method of determining the locality of a mobile unit in accordance with the subject invention; and

[0017] FIGS. 6-9 are a set of three dimensional plots which depict the a-posteriori location probability distribution produced by the Bayesian-update prediction method in accordance with the subject invention for four successive time periods.

[0018] Referring now to the drawings and more particularly to FIG. 1, reference numeral 10 denotes a service area for a CDMA cellular telephone system partitioned into a plurality of contiguous hexagonal cells 12. FIG. 1 also depicts, a plurality of base stations 14₁, 14₂, . . . 14_n−1, 14_nlocated within the service area 10. Also, the service area 10 includes at least one mobile switching center (MSC) 16. Typically, each base station 14₁. . . 14_nhas a sectorized antenna with a distinct pilot signal channel associated with each sector. Three sectored antennas are most common. In FIG. 1, all of the base stations have three sectors each The three sectors associated with base station 14₁, for example, are denoted by the symbols 15_1,1, 15_1,2and 15_1,3, respectively. A mobile unit 20 is located in sector 15_2,1.

[0019] FIG. 2 is further illustrative of the cells 12 being further divided into sub-cells 18 and which are represented by a grid formed by rectilinear grid lines 20 and 22. The reference numbers 1, 2, 3, . . . , 6 of FIG. 2 represent individual sub-cells 18₁, 18₂, . . . 18₆, respectively.

[0020] Turning attention now FIG. 3, shown thereat is a diagram broadly illustrative of the system architecture for determining the location of a mobile unit 20 within the service area 10 in accordance with the subject invention. The MSC 16 operates in conjunction with a plurality of base stations 14₁, . . . 14_nand connects to the local telephone system, not shown. A server 22 comprised of digital computer apparatus and a memory 24 for storing a digital database (DB) are typically located at the site of the MSC 16 for purposes which will now be explained.

[0021] In the invention described in above referenced related application U.S. Ser. No. 09/139,107, each sub-cell 18₁. . . 18_nof the service area 10 (FIG. 3) is identified by a set of observable, i.e. detectable characteristics which are referred to as attributes and include, for example, RF characteristics, e.g. measured pilot signal power (Ec/Io) from different sectors, phase-offsets, time delay or angle of arrival, and round trip delays of one or more pilot signals, hereinafter referred to simply as “pilots”, radiated from each of the base stations 14₁. . . 14_n.

[0022] The database (DB) in U.S. Ser. No. 09/139,107 contains attribute information which differentiates one sub-cell 18 from another and is generated by making a repeated and exhaustive survey which involves taking repeated measurements at all the sub-cells 18₁, . . . 18_n(FIG. 2) of the service area 10. During the operation phase, after the database has been set up and the location service has been deployed, the mobile unit 20 detects and measures attribute values, eg., pilot strengths and phase offsets, from its actual location in sub-cell 18_iand reports them via a message, e.g. a pilot strength measurement message (PSMM), to the base station(s) 14₁. . . 14_n(FIG. 3), which can be one or more of the base stations with which it is in communication. The base station(s) forward their respective reported measurements to a location server 22 via MSC 16. When the attributes are reported to the server 22, the digital computer apparatus 23 associated with the server 22 statistically compares the measured values with the known attribute values stored in the database 24 of all the sub-cells 18 in the service area 10. The sub-cell 18_iwhose attribute values as stored in the database provide the best match for the measurements reported by the mobile unit 20 is considered to be the best estimate of the mobile unit's location.

[0023] Considering now the present invention, it also uses a database; however, in contrast to the above-referenced related invention shown and described in U.S. Ser. No. 09/139,107, the present invention uses a model based approach to generate the database. The database contains for each sub-cell 18₁. . . 18_nin the service area 10, the probabilities that different pilots are visible in that sub-cell. In accordance with this approach, a limited number of pilot strength measurements are carried out along a few representative routes in the service area 10 and an RF signal propagation model is constructed to represent the RF environment associated with the service area. The parameters of this model are adjusted to yield a substantially good match between pilot strengths predicted by the model and the corresponding measurements.

[0024] The RF propagation model used to represent the RF environment associated with the service area and how it is used to generate the database containing pilot visibility probabilities will now be explained.

[0025] With reference to FIG. 1, for sectors 15_1,1, 15_1,2, 15_1,3, 15_2,1. . . 15_n,3, let Ti_1,1, T_{1,2, T1,3, T2,1}, . . . , T_n,3respectively denote the total transmit powers associated with those sectors. Assume that each sector uses a fraction, γ, of its total transmit power for its pilot channel. For example, the pilot channel power for sector 15_1,1is given by γT_1,1.

[0026] Now consider a mobile unit 20 at a location (x,y) in the service area 10. The model assumes that the total power R_i,j(x,y) received by a mobile unit 20 from sector 15_i,j(i=1, 2, . . . , n and j=1, 2, 3) is given by:

[0027] R_i,j(x,y)=T_i,j·G_i,j(x,y)·L_i,j(x,y)·F_i,j(x,y)  (1)

[0028] where G_i,j(x,y) is the antenna gain for sector 15_i,jalong the direction pointing towards, the location (x,y), L_i,j(x,y) is the distance loss between the base station 14_iassociated with sector 15_i,jand the location (x,y) and F_i,j(x,y) is the corresponding shadow fading factor, all in absolute, not dB, units. The pilot channel power received by the mobile unit 20 at location (x,y) from sector 15_i,jis then equal to γR_i,j(x,y).

[0029] The model assumes that the distance loss L_i,j(x,y) can be expressed as:

[0030] L_i,j(x,y)=C_p·[d_i,j(x,y)]^−α  (2)

[0031] where d_i,j(x,y) is the distance between the base station 14_iassociated with the sector 15_i,jand the location (x,y), and C_pand α are constants. Typically, C_ptakes a value in the range 10⁻¹⁰to 10⁻¹⁵and α is between 3 and 5 when d_i,j(x,y) is expressed in units of miles. The two parameters C_pand α, moreover, are environment specific.

[0032] The shadow fading factor F_i,j(x,y) models the impact of terrain and large structures on signal propagation, which create deviations around the signal attenuation predicted by the deterministic path loss and can be written as: $\begin{array}{cc}{F}_{i,j}\left(x,y\right)={10}^{a+\left(X_{i,j}/10\right)}& \left(3\right)\end{array}$

[0033] where X is a non-zero Gaussian random variable with standard deviation α and a is a normalization constant chosen so that the mean value of F_i,j(x,y) equals 1. Moreover, shadow fading factors display spatial correlation. That is, shadow fading factors between a base station 14_iand locations that are reasonably close to each other display statistical correlation. This fact can be represented in the model as follows.

[0034] Let (x₁,y₁) and (x₂,y₂) be two locations in the service area separated by d meters and let F_i,j(x₁,y₁) and F_i,j(x₂, y₂) respectively, be the shadow fading factors between the sector 15_i,jand the locations (x₁,y₁) and (x₂,y₂):

[0035] Accordingly,

[0036] F_i,j(x₁,y₁)=10^α+(x/(10)  (4a)

[0037] and

[0038] F_i,j(x₂,y₂)=10^α+(x/(10)  (4b)

[0039] Next the model assumes that the covariance between the exponents X⁽¹⁾_i,jand X⁽²⁾_i,jis given by:

[0040] E[X_i,j⁽¹⁾X_i,j⁽²⁾]=η{square root over (E[(²  (5)

[0041] where η=e^−d/D. The parameter D₀is called the correlation length associated with the shadow fading environment. It is found that depending on the environment, the correlation length can vary from a few tens of meters to several hundreds of meters.

[0042] Assume now also that the pilot strength measurement carried out and reported to the base station 14_iby the mobile unit 20 is the (E_c/I_ovalue) of the corresponding pilot channel signal. This value is the ratio of the pilot channel power from the concerned sector received by the mobile unit 20 to the total power received by the mobile unit including thermal noise, and, possibly, external interference.

[0043] By letting P_i,j(x,y) denote the power (E_c/I_ovalue) of pilot channel associated with sector 15_i,jas measured by a mobile unit located at the point (x,y), Then: $\begin{array}{cc}{P}_{i,j}\left(x,y\right)=\frac{\gamma R_{i,j}\left(x,y\right)}{N_0+R_{1,1}\left(x,y\right)+R_{1,2}\left(x,y\right)+\dots +R_{n,3}\left(x,y\right)}& \left(6\right)\end{array}$

[0044] where N₀denotes the thermal noise and external interference. Hereafter, for convenience, the symbol (i,j) will be used to refer to the pilot channel associated with sector 15_i,j.

[0045] The description of the RF propagation and pilot measurement model is now complete. Note that the parameters pertaining to the total transmit powers i.e. T_1,1, T_1,2, . . . , the fraction γ of power used for the pilot channel, the antenna gains and orientations which enable one to compute antenna gains in different directions are known to the service provider. Thus, the only parameters whose values need to be determined by matching predicted pilots strengths with measured values are the distance loss parameters C_pand α, the shadow fading standard deviation σ, correlation length D₀, and the thermal noise power N₀.

[0046] Once all of the unknown parameters are determined, the process of populating the database with pilot visibility probabilities can be undertaken. In this illustrative example, it is assumed that the location prediction method uses pilot strength information in a binary form, that is, it is only concerned with whether or not a pilot was visible (i.e. its E_c/I_ovalue was measured above a predetermined threshold T). Then, the database is populated as follows.

[0047] Noting that a pilot (i,j) would be visible at location (x,y) if, $\begin{array}{cc}{P}_{i,j}\left(x,y\right)=\frac{\gamma R_{i,j}\left(x,y\right)}{N_0+R_{1,1}\left(x,y\right)+\dots +R_{n,3}\left(x,y\right)}\ge T.& \left(7\right)\end{array}$

[0048] then, to populate the database, what is needed for each location (x,y) is the probability Pr[P_i,j(x,y)≧T] for each pilot (i,j) that can possibly be seen at that location. These probabilities can be obtained by running a simulation for all grid-points (x,y) in the service area. Before the simulations are carried out, however, for each grid-point (x,y), several counters, one for each of the pilots that can possibly be measured above the threshold T at the grid-point (x,y), are established and set to “0”. In each run of the simulation the shadow fading factors between each grid-point and base station pair are generated according to the appropriate statistical model as described above. The path loss values between a given base station and grid-point are deterministic and once computed can be reused in all the simulation runs.

[0049] Using these factors along with other factors such as path losses, antenna gains, etc., the E_c/I_ovalue for each pilot can be determined for each grid-point (x,y). If, during a simulation run, the E_c/I_ovalue of the pilot (i,j) (i.e. P_i,j(x,y)) is found to be greater than or equal to the threshold T the corresponding counter is incremented by “1”. If P_i,j(x,y) is found to be below the threshold T, the corresponding counter is left unchanged. A large number of simulation runs, each with a different “seed”, are made.

[0050] Assume that M simulation runs are made. At the end of these simulation runs, let C_ij(x,y)/M be the value of the counter associated with the visibility of the pilot (i,j) at the grid-point (x,y). Then it is assumed that the probability of the pilot (i,j) being visible at the grid-point (x,y), i.e. Pr[P_i,j(x,y)≧T]=C_ij(x,y)/N. These probability values are stored in the database. The flow chart of FIG. 4 illustrates this procedure.

[0051] The RF signal propagation and pilot measurement model described above is used to process the pilot strength (or visibility) information reported by the mobile unit 20 in order to determine the latter's location.

[0052] Another model will now be described and is used to process the “phase offset” information reported by a mobile unit. Assume that pilots (i,j) and (k,l) are visible at location (x,y) and the corresponding base stations are 14_iand 14_k. Let p denote the actual phase offset between these two pilots when they are received at the location (x,y). The phase offset, p, refers to the time difference between the arrival of the pilot signals at location (x,y). Assume also that p equals the sum of two components, the first pertaining to the difference in propagation times for those pilot signals if they were to follow the direct, line-of-sight paths from their respective base stations to the location (x,y), and the second pertains to a random deviation which may be caused by the fact that these signals often arrive after several reflections, diffractions, etc. Thus

[0053] p=(d_k−d_i)/c+v  (8)

[0054] where d_iand d_k, respectively, denote the distance between the base station 14_iand 14_kand the location (x,y), c is the speed of light in air and ν is the second component of the phase offset described above. Assume further that ν is a Gaussian random variable with mean zero and standard deviation β. The actual phase offset, p, then has the following Gaussian distribution $\begin{array}{cc}\mathrm{Prob}\left[p_1\le p<p_2\right]=\frac{1}{\sqrt{2\pi }\beta }{\int }_{p_1}^{p_2}\exp \left(-\frac{{\left(p-\left[\frac{d_j-d_i}{c}\right]\right)}^2}{2{\beta }^2}\right)dp& \left(9\right)\end{array}$

[0055] Typically, mobile units report phase offsets in terms of integral number “chip durations”. A chip is a time interval corresponding to one symbol of the spreading sequence(s) used in Code Division Multiple Access (CDMA) wireless systems. For CDMA cellular systems based on the standards IS-95 or ANSI J-008, a chip duration equals about 0.8 microseconds. Thus, the probability of a mobile unit located at (x,y) reporting a phase offset of m chips (m is an integer) is given by: $\begin{array}{cc}\mathrm{Prob}\left[\left(m-\frac{1}{2}\right)\tau \le p<\left(m+\frac{1}{2}\right)\tau \right]=\frac{1}{\sqrt{2\pi }\beta }{\int }_{\left(m-\frac{1}{2}\right)\tau }^{\left(m+\frac{1}{2}\right)\tau }\exp \left(-\frac{{\left(p-\left[\frac{d_j-d_i}{c}\right]\right)}^2}{2{\beta }^2}\right)dp& \left(10\right)\end{array}$

[0056] where τ is the chip duration.

[0057] Equation (10) describes a statistical model for phase offsets which is expressed in terms of a single unknown parameter β. This parameter can be determined empirically via measurements at a few representative locations. Once again exhaustive measurements are not needed.

[0058] Once the database containing pilot visibility probabilities for different locations has been prepared and the model for phase offsets has been identified, the system can be said to be ready to provide the desired location estimation service.

[0059] FIG. 5 is further illustrative of the foregoing description. Reference numeral 26, for example, denotes that the first step involves gathering measurements (data) on representative routes. This is followed by using these measurements to tune the RF propagation model and to find the best set of values for the parameters c_p, α, L, N_oand β as shown by reference numeral 28. Then, as shown by block 30, for all grid points or sub-cells (x,y), a series of simulations are run based on the RF model with the best set of parameters obtained from step 28 in order to build a database (step 30) which contains the probability of seeing a pilot signal, i.e. being either “visible” or “invisible” at the location (x,y) for every x, y location in the search area.

[0060] The, last step 32 of FIG. 5 which involves the determination (estimation) of a mobile unit's location based on the pilot visibility probability and phase offset information reported by it and which will now be described. As mentioned above, the location estimate is computed using the Bayesian-Update Location Prediction Method (BLPM).

[0061] The BLPM is initiated when the location server 23 (FIG. 3) receives a location request from a mobile unit 20 along with a message relaying its pilot strength and phase offset measurements. Again, assume in this example that pilot strength measurements are of a binary form, i.e. they tell whether or not a pilot was above a predetermined threshold T when the mobile unit measured its strength.

[0062] When a first set of PSMM measurements is received, to reduce the number of computations, the location server then identifies a sub-region 17 (FIG. 1) of the service area 10 as the region in which the mobile unit 20 is likely to be located. One example of selecting this sub-region is to center around the area in which the primary pilot or the strongest pilot is most likely to appear. Thus, for instance, if the pilot (2,1) is the primary pilot of the mobile unit 20, the 7 sub-region 17 in FIG. 1 would be identified as the region in which the mobile unit is most likely to be located.

[0063] Now let the number of grid-points in this sub-region be N. Along with the sub-region 17, a set of pilots S consisting of all the pilots that can be visible at least one of the grid-points or sub-cells 18 included in the sub-region 17, is identified. The location server 22 now computes the a-priori, location probability distribution for the mobile unit 20. Let Prob⁽⁰⁾(x,y) denote this a-priori location probability distribution. Then Prob⁽⁰⁾(x,y) is given by: $\begin{array}{cc}{\mathrm{Prob}}^{\left(0\right)}\left(x,y\right)=\{\begin{array}{c}1/N\mathrm{if}\left(x,y\right)\mathrm{is}\mathrm{in}\mathrm{the}\mathrm{sub}\text{-}\mathrm{region}\\ 0\mathrm{otherwise}\end{array}& \left(11\right)\end{array}$

[0064] The form of Prob⁽⁰⁾(x,y) as given above allows one to include in their computations only those grid-points that fall within the selected, sub-region 17, thus leading to a significant saving in computations. Let 0₁denote first set of measurements reported by the mobile unit (at time t₁). 0₁includes of the identities of all those pilots which were visible to the mobile unit 20 when it carried out the measurements. Let (i₁,j₁),(i₂,j₂), . . . , (i_K,j_K) denote these pilots. Suppose those K visible pilots came from L distinct base-stations k₁, k₂, . . . , k_L. Without loss of generality, let k₁be the reference base-station. Assume 0₁also contains the phase offsets (expressed in integral multiples of chip durations) θ_kk, θ_kk, . . . , θ_kk. Then, for each grid-point (x,y) in the sub-region 17 and each pilot (i,j) in the set S, the BLPM uses the database and determines the conditional visibility/invisibility probabilities

[0065] Prob (P_i,j(x,y)≧T) if the pilot was visible,

[0066] Prob (P_i,j(x,y)<T) if the pilot was not visible.

[0067] BLPM also determines the conditional probability of the reported phase offset for that pilot if the mobile unit were located at the grid-point (x,y). Equation (10) is used to determine this probability. Let Prob (p_kk(x,y)), 2≦i≦L denote this conditional probability.

[0068] Now, the next step is to determine, for each grid-point (x,y) in the sub-region 17, the conditional probability of the mobile unit reporting the measurement set 0₁if it were located at that grid-point. Let Prob [0₁|(x,y)] denote this conditional probability. The BLPM approximates this probability by the product of the individual conditional probabilities. Thus, $\begin{array}{cc}\begin{array}{c}\mathrm{Prob}\left(O_1|\left(x,y\right)\right)=\prod _{\left(i,j\right)\in V_1}\mathrm{Prob}\left(P_{i,j}\left(x,y\right)\ge T\right)·\\ \prod _{\left(i,j\right)\in \left(S-V_1\right)}\mathrm{Prob}\left(P_{i,j}\left(x,y\right)<T\right)·\\ \mathrm{Prob}\left(p_{k_2{k}_1}\left(x,y\right)\right)·\\ \mathrm{Prob}\left(p_{k_3{k}_1}\left(x,y\right)\right)\dots \mathrm{Prob}\left(p_{k_L{k}_1}\left(x,y\right)\right)\end{array}& \left(12\right)\end{array}$

[0069] In the above expression V₁refers to the set of pilots that were reported to be visible in the measurement set 0₁.

[0070] Once the conditional probability, Prob 0₁|(x,y)), is determined in the manner described above for each grid-point (x,y), the BLPM computes the a-posteriori location probability distribution for the mobile unit using the well-known Bayes theorem. In particular, the a-posteriori probability of the mobile unit 20 being at grid-point (x,y) given that the reported measurement set is 0₁is given by $\begin{array}{cc}\mathrm{Prob}\left(\left(x,y\right)|O_1\right)=\frac{{\mathrm{Prob}}^{\left(0\right)}\left(x,y\right)·\mathrm{Prob}\left(O_1|\left(x,y\right)\right)}{\mathrm{Prob}\left(O_1\right)}.& \left(13\right)\end{array}$

[0071] Note that the denominator of the right hand side in the above equation is common to all grid-points (x,y). Therefore, to compute the a-posteriori probability distribution, the product Prob⁽⁰⁾(x,y) Prob(0₁|(x,y)) is evaluated for each grid-point (x,y) and then normalized so that the sum of the (normalized) products corresponding to different grid-points in the sub-region 17 equals unity. This completes the computation of the a-posteriori probability distribution of the mobile unit's location given the first reported measurement set 0₁.

[0072] The iterative nature of BLPM comes into play, as shown in FIGS. 6-9, when the mobile unit 20 reports multiple measurement sets 0₁, 0₂, . . . , 0_kat time instants t₁, t₂, . . . , t_krespectively. It is assumed here that t₁<t₂< . . . <t_k. In this case the BLPM uses the a-posteriori location probability distribution computed at the end of one step as the a-priori distribution for the next step. To simplify computations, BLPM assumes all measurement sets to be conditionally independent given the mobile's unit's location. The following is a description of this procedure.

[0073] Let P((x,y)|0₁, . . . , 0_k) denote the a-posteriori location probability distribution at the end of the k^thstep, i.e. after accounting for the first k measurement sets. Here 1≦k≦k−1. To account for the k+1^Stmeasurement set, 0_k+1, the BLPM uses the following relationships: $\begin{array}{cc}\begin{array}{c}P\left(\left(x,y\right)|O_1,O_2,\dots ,O_{k+1}\right)=\frac{\begin{array}{c}P\left(\left(x,y\right)|O_1,\dots ,O_k\right)·\\ P\left(O_{k+1}|\left(x,y\right),O_1,\dots ,O_k\right)\end{array}}{P\left(O_{k+1}|O_1,\dots ,O_k\right)}\\ =\frac{\begin{array}{c}P\left(\left(x,y\right)|O_1,\dots ,O_k\right)·\\ P\left(O_{k+1}|\left(x,y\right)\right)\end{array}}{P\left(O_{k+1}|O_1,\dots ,O_k\right)}\end{array}& \left(14\right)\end{array}$

[0074] In deriving the above relationship an assumption has been made that the measurement set 0_k+1is conditionally independent of the measurement sets 0₁, 0₂, . . . 0_kgiven that the mobile unit's location is (x,y). Notice that the above relationship between P((x,y)|0₁, . . . 0_k) and P((x,y)|0₁, . . . , 0_K) is similar to that between P((x,y)|0₁) and Prob^(O)(x,y) in equation (13) which represents the BLPM computations associated with the processing of the first measurement set 0₁. Also as in equation (13), the denominator of equation (14), does not have to explicitly be evaluated if the numerations are all normalized so that they sum to unity. Thus, it is clear that to process each new measurement set the BLPM essentially repeats the same steps with the a-posteriori location probability distribution computed at the end of the previous step taking the place of the a-priori distribution for the new step. It should be noted that at the end of each step, a suitable function of the corresponding a-posteriori location probability distribution, e.g. the mean value, is computed as the best estimate of the mobile unit's location given all of the measurement sets processed up to that point in time as shown in FIGS. 6-9. At t₀before the first iteration of a BLPM is launched, the grid floor would be level or flat since no probabilities have been calculated. At t₁(FIG. 6), the first iteration is made and the location probability distribution comprising an “a posteriori” set of probabilities for the region 17 is shown. The set of probabilities calculated at t₁is used as the a “priori” set for the computation of new “a posteriori” probabilities at t₂in FIG. 7, which in turn becomes the “a priori” set for t₃and so on as shown in FIGS. 8 and 9 where reference numerals 48₁, 48₂, 48₃and 48₄depict the “mean” estimate of the probability distribution while reference numerals 50₁, 50₂′ 50₃and 50₄depict the “mode” estimate. It can be seen that the updating results in narrowing the region where the mobile unit is apt to be located.

[0075] The methodology described above is directed to the power and phase-offset measurements as the observations 0_t. However, other sources of information can also be incorporated in 0_t, e.g. round trip delay, angle of arrival, etc. when desired. It is believed that the accuracy of the algorithm will be greatly improved thereby. Thus, the advantages of the BLPM technique is that all types of information can be easily incorporated into the algorithm.

[0076] The foregoing merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various other modifications to the method and apparatus as disclosed which, although not explicitly described as shown herein, embody the principles of the invention and are thus within its spirit and scope.