(12) United States Patent
`Chang et al.
`
`USOO6889053B1
`(10) Patent No.:
`US 6,889,053 B1
`(45) Date of Patent:
`May 3, 2005
`
`(54) LIKELIHOOD-BASED GEOLOCATION
`PREDICTION ALGORTHMS FOR CDMA
`SYSTEMS USING PLOT STRENGTH
`MEASUREMENTS
`
`(75) Inventors: Kirk K. Chang, Morganville, NJ (US);
`Daniel R. Jeske, Eatontown, NJ (US);
`Kiran M. Rege, Marlboro, NJ (US);
`Yung-Terng Wang, Marlboro, NJ (US)
`(73) Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`
`- - -
`c:
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/359,648
`1-1.
`(22) Filed:
`Jul. 26, 1999
`(51) Int. Cl." .................................................. H04Q 7/00
`(52) U.S. Cl. ................................ 455/456.3; 455/456.5;
`342/357.01; 342/450; 375/262
`(58) Field of Search ......................... 370,342; 375/262;
`342/357.01, 357.02, 450
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`6,249.252 B1 * 6/2001 Dupray .................. 342/357.01
`6,263,208 B1 * 7/2001 Chang et al. ..
`... 455/456.3
`6,496,701 B1 * 12/2002 Chen et al. .......
`... 455/456.5
`6,564,065 B1
`5/2003 Chang et al. - - - - -
`- - - 455/457
`2001/0022558 A1
`9/2001 Karr et al. .................. 342/450
`sk -
`cited by examiner
`-
`- - -
`Primary Examiner William D. Cumming
`(57)
`ABSTRACT
`The location of a mobile wireleSS communication unit in the
`Service area of a CDMA communications System is pre
`dicted utilizing two likelihood functions that define maxi
`mum likelihood estimators of the mobile units location,
`based on attribute measurements, Such as but not limited to
`pilot Signal Strength, being made at the location of the
`mobile unit and reported back to a base station. One of the
`likelihood functions comprises a frequentist likelihood func
`tion and the other comprises a Bayesian-modified likelihood
`function. The likelihood functions are based on the assump
`tion that there is an RF model which provides the probability
`a mobile unit is able to detect one or more attributes
`associated with an arbitrary base station, given it is located
`at an arbitrary location within the Service area. Each of the
`likelihoods are also incorporated into a Sequential Bayesian
`procedure which outputs a posterior distribution indicative
`of the location of the mobile unit.
`
`5,933.462 A *
`
`8/1999 Viterbi et al. ............... 375/262
`
`16 Claims, 8 Drawing Sheets
`
`
`
`BASE STATION
`BS2
`
`s
`
`14,
`
`4. DATA
`
`24
`
`DP
`
`22
`LOCATION SERVER-1
`
`GE
`
`Sl y".
`
`BASE STAON
`BS3
`
`WAIT FOR A NEW LOCATION
`REQUEST TO ARRIVE
`
`30
`
`ROCATION
`REOUES
`ARRIVEO
`
`BASED ONEITHER THE PRIMARY BASE STATIONOR
`THE STRONGEST REPORTED PILOT, EDENTIFY THE
`DOMAIN OF SUPPORT FOR THE MOBILE LOCATION. A.
`AND THE SET OF POSSIBLE PILOTS, K
`
`
`
`
`
`
`
`COMPUTE 8i (x,y) FOR ALL
`(x,y) INA AND FOR ALL PILOTS
`iji ENK USING EQUATION (89)
`
`34
`
`3S
`
`FREQUENTIST
`
`40
`
`SEQUENTIAL
`BAYES
`
`
`
`
`
`
`
`
`
`FREQUENTIST
`ORBAYES
`MODIFIED
`
`
`
`BAYES
`MODIFIED
`
`MLOR
`SEENTIAL
`BAYES
`
`FREQUENTIST
`
`42
`
`FROUENTIST
`ORBAYES
`MODIFIED
`
`BAYES
`MODIFIED
`
`O
`
`BASE STATION
`
`a BS
`
`h
`
`20
`
`Petitioner Uber Ex-1033, 0001
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 1 of 8
`
`US 6,889,053 B1
`
`
`
`
`
`12
`
`p -
`i-M 3 is."
`N153
`is BSE: EASE: C
`-3-49. STATION--...STATION--/
`*i.
`A
`
`:
`: 33
`1523:
`BASE
`BASE
`:
`BASE
`:
`BASE
`:
`-- STATION--STATION--STATION--STATION--
`
`BS.
`i
`B.S. 1s'." B.S.
`BS.
`i
`B.S.
`- STATION--STATION--...STATION--STATION-3s. STATION--
`,
`;
`,
`,
`,
`,
`i. 5 .
`-12
`:
`BASE
`:
`BASE
`:
`BASE
`:
`BASE
`- STATION--STATION--STATION--STATION--
`th igh :
`h n:
`:
`:
`BASE
`:
`BASE
`:
`BASE
`:
`'....STATION--STATION----. STATION--
`
`/12
`
`a.
`
`P
`
`a
`up
`
`V.
`
`A
`
`up
`
`we
`
`Petitioner Uber Ex-1033, 0002
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 2 of 8
`
`US 6,889,053 B1
`
`
`
`18
`A
`Y/ MY.
`
`If
`
`
`
`|
`
`7
`
`-
`
`-
`
`-
`
`
`
`
`
`f 1. 2 4.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OTT T.I.
`III III
`II
`--
`-
`2
`H-AH
`345
`34
`5
`S
`6
`III
`... TT ...
`Tr. Nr.
`-- Y
`-
`
`
`
`
`
`
`
`
`
`
`
`X AXIS
`
`...
`T
`
`
`
`
`
`
`
`
`
`He,
`IIT III
`--
`.
`...
`EEE
`ITT
`
`--
`
`.
`
`.
`
`.
`--
`
`T.
`
`.
`
`rt
`
`.
`.
`III
`ITT
`
`T
`IT III.
`-----
`- T -
`-
`-
`-
`-
`-
`
`
`
`III III
`
`-
`
`III.
`TF. I
`-
`TT I
`y AXIS
`
`I.
`I
`-
`I ITT
`
`Petitioner Uber Ex-1033, 0003
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 3 of 8
`
`US 6,889,053 B1
`
`FIG. 3
`
`
`
`
`
`4. DATA
`
`N/
`
`".
`
`BASE STATION
`BS3
`
`
`
`
`
`BASE STATION
`BS2
`
`BASE STATION
`a BS1
`
`10
`
`N/
`
`
`
`14 y
`* 20
`
`Petitioner Uber Ex-1033, 0004
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 4 of 8
`
`US 6,889,053 B1
`
`FIG. 4
`
`FIG. 4B
`
`FIG 4E
`
`FIG 4C
`
`FIG 4D
`
`
`
`FIG. 4A
`
`WAIT FOR A NEW LOCATION
`REQUEST TO ARRIVE
`
`30
`
`
`
`
`
`
`
`LOCATION
`REQUEST
`ARRIVED?
`
`
`
`YES
`BASED ON EITHER THE PRIMARY BASE STATION OR
`THE STRONGEST REPORTED PILOT, IDENTIFY THE
`DOMAIN OF SUPPORT FOR THE MOBILE LOCATION, A,
`AND THE SET OF POSSIBLE PILOTS, K
`
`COMPUTE 8i (x,y) FOR ALL
`(x,y) IN A AND FOR ALL PILOTS
`ij INK USING EQUATION (B9)
`
`34
`
`3S
`
`TO FIG. 4B
`
`TO FIG. 4E
`
`FREQUENTIST
`40
`
`SEQUENTIAL
`BAYES
`
`
`
`
`
`
`
`
`
`
`
`FREQUENTIST
`OR BAYES-
`MODIFIED2
`
`
`
`
`
`BAYES
`MODIFIED
`
`TO FIG 4C
`
`
`
`38
`
`
`
`ML, OR
`SEQUENTIAL
`BAYES
`
`FREQUENTIST
`
`42
`
`ML
`
`
`
`
`
`FROUENTIST
`OR BAYES
`MODIFIED?
`
`Elio
`
`TO FIG 4D
`
`Petitioner Uber Ex-1033, 0005
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 5 of 8
`
`US 6,889,053 B1
`
`FTG. 4B
`
`FROM FIG 4A
`
`44
`
`INITIALIZE THE FOLLOWING:
`O P(x,y) = 1/||A|| AND Li(x,y) = 1, V(x,y)eA
`S = 1
`
`
`
`CALCULATE L(x,y), Y(x,yleA
`USING EQUATION (1) AND THE MEASUREMENTS |
`
`
`
`CACULATE Pt(x,y), V(x,y)eA
`USINGEOUATION (S) AND NORMALIZE THESE WALUES SO
`THEY SUM TO UNITY TO OBTAIN THE POSTERIOR
`DISTRIBUTION FOR THE LOCATION OF THE MOBILE
`
`COMPUTE MEANOR MODE OF POSTERIOR DISTRIBUTION FOR
`THE LOCATION OF THE MOBILE AND REPORT IT AS THE CURRENT
`PREDICTION OF WHERE THE MOBILE IS LOCATED
`
`MORE
`MEASUREMENTS
`EXPECTED?
`
`
`
`TO FIG 4A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YES
`
`
`
`MEASUREMENT
`RECEIVED?
`
`WAIT FOR NEXT
`MEASUREMENT
`
`
`
`Petitioner Uber Ex-1033, 0006
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 6 of 8
`
`US 6,889,053 B1
`
`FIG. 4C
`
`FROM FIG 4A
`
`60
`
`
`
`62
`
`64
`
`CALCULATE aij(x,y) AND Bij(x,y), Y(x,yle A
`AND FOR ALL ij INK USING EQUATIONS (2) AND (3)
`
`INITIALIZE THE FOLLOWING:
`P(x,y) = 1/A AND la (x,y) = 1, V(x,y: A
`S=1
`
`CALCULATE lux,y) , Y(x,y)eA
`USINGEOUATION (4) AND THE FEASUREENIS -
`
`S
`CALCULATE P(x,y) , v(x,y)6A
`USING EQUATION (7) AND NORMALIZE THESE WALUES
`SO THEY SUM TO UNITY TO OBTAIN THE POSTERIOR
`DISTRIBUTION FOR THE LOCATION OF THE MOBILE
`
`
`
`
`
`
`
`SET
`
`
`
`
`
`
`
`
`
`
`MEASUREMENT
`RECEIVED?
`
`COMPUTE MEAN OR MODE OF POSTERIOR DISTRIBUTION
`FOR THE LOCATION OF THE MOBILE AND REPORT IT AS THE
`CURRENT PREDICTION OF WHERE THE MOBILE IS LOCATED
`
`WAIT FOR NEXT
`MEASUREMENT
`
`MORE
`MEASUREMENTS
`EXPECTED?
`
`
`
`
`
`O
`
`TO FIG 4A
`
`Petitioner Uber Ex-1033, 0007
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 7 of 8
`
`US 6,889,053 B1
`
`FIG. 4D
`
`FROM FIG 4A
`
`78
`
`
`
`O
`
`B2
`
`CALCULATE aij(x,y) AND Bij(x,y), V(x,yleA
`AND FOR ALL ij INK USING EQUATIONS (2) AND (3)
`
`INITIALIZE THE FOLLOWING:
`Sox,y) = Y, (x,y)eA
`S = 1
`
`CALCULATE lit.) , V(x,y)eA
`USINGEOUATION (4) AND THE MEASUREENS:
`
`COMPUTE THE BAYES-MODIFIED MAXIMUM
`LIKELIHOODESTIMATE OF THE CURRENT LOCATION
`OF THE MOBILE BY SELECTING THE (x,y) WHICH
`GIVES THE LARGEST WALUE OF Eux,y)
`
`86
`
`
`
`MORE
`MEASUREMENTS
`EXPECTED2
`
`NO
`
`TO FIG 4A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MEASUREMENT
`RECEIVED?
`
`88
`
`WAIT FOR NEXT
`MEASUREMENT
`
`Petitioner Uber Ex-1033, 0008
`
`

`

`U.S. Patent
`
`May 3, 2005
`
`Sheet 8 of 8
`
`US 6,889,053 B1
`
`FIG. 4E
`
`FORM FIG 4A
`
`94
`
`
`
`INITIALIZE THE FOLLOWING:
`tax,y) = 1, V(x,y)eA
`S = 1
`
`CALCULATE t(x,y). V(x,y)eA
`USING EQUATION (1) AND THE MEASUREMENTS i
`
`
`
`COMPUTE THE FREQUENTIST MAXIMUM
`LIKELIHOODESTIMATE OF THE CURRENT LOCATION
`OF THE MOBILE BY SELECTING THE (x,y) WHICH
`GIVES THE LARGEST WALUE OF lit (, y)
`
`100
`
`MORE
`MEASUREMENTS
`EXPECTED?
`
`TO FIG 4A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MEASUREMENT
`RECEIVED?
`
`WAIT FOR NEXT
`MEASUREMENT
`
`Petitioner Uber Ex-1033, 0009
`
`

`

`US 6,889,053 B1
`
`1
`LIKELIHOOD-BASED GEOLOCATION
`PREDICTION ALGORTHMS FOR CDMA
`SYSTEMS USING PILOT STRENGTH
`MEASUREMENTS
`
`15
`
`25
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`This application is related to U.S. Ser. No. 09/139,107,
`now U.S. Pat. No 6,496,701 entitled “Pattern Recognition
`Based Geolocation', filed in the names of T. C. Chiang et al
`on Aug. 26, 1998; U.S. Ser. No. 09/294,997 entitled “A
`Bayesian-Update Based Location Prediction Method for
`CDMA Systems”, filed in the names of K. K. Chang et all on
`Apr. 20, 1999; and U.S. Ser. No. 09/321,729, now U.S. Pat.
`No. 6,263,208, issued on Jul. 17, 2001, entitled “Geoloca
`tion Estimation Method For CDMA Terminals Based On
`Pilot Strength Measurements”, filed in the names of K. K.
`Chang etal on May 28, 1999. These related applications are
`assigned to the assignee of the present invention and are
`meant to be incorporated herein by reference.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to a method of locating a
`mobile telephone unit within a cellular Service area, and
`more particularly to a method of predicting the location of
`a CDMA mobile unit based upon the probability of its being
`at a particular location of the Service area using an algorithm
`providing a likelihood estimation of the mobile unit's loca
`tion in response to a sequential Set of attributes observed by
`the mobile unit and reported back to a base Station.
`2. Description of Related Art
`A cellular telephone System must be able to locate a
`mobile unit within a cellular service area under various RF
`35
`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.
`In the above-noted related patent application U.S. Pat. No.
`6,496,701 entitled “Pattern Recognition-Based
`Geolocation”, 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 base Station where they
`are matched to a known set of RF characteristics and other
`information obtained from making attribute information
`measurements at all the grid points (Sub-cells) in a cellular
`Service area and which are then Stored in a database located,
`for example, in a base Station Server.
`In the above-noted related patent application U.S. Ser. No.
`09/294,997 entitled “A Bayesian-Update Based Location
`Prediction Method For CDMA systems”, the invention is
`directed to a method of estimating, by a Bayesian probability
`algorithm, the location of a mobile unit in the Service area
`of a CDMA cellular telephone system using a model based
`approach which, among other things, Simplifies the genera
`tion of a database containing a pilot Signal visibility prob
`abilities. This eliminates the need for repeated attribute
`measurements at all of the grid points in the Service area.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`In the above-noted related patent U.S. Pat. No. 6,263,608
`entitled “Geolocation Estimation Method For CDMA Ter
`minals Based On Pilot Strength Measurements”, the inven
`tion is directed to a method of estimating the location of a
`mobile unit in the service area of a CDMA cellular telephone
`System also using a model based approach, but which now
`eliminates the need for a stored database containing pilot
`signal visibility probabilities for all of the grid points or
`Sub-cells in the cellular Service area. The estimation proce
`dure is based entirely on analytical results involving one or
`more key approximations derived, for example, from an
`integrated model of the wireless communications System, its
`RF environment, and attribute measurement.
`
`SUMMARY
`The Subject invention is directed to predicting the location
`of a mobile wireleSS communication unit in the Service area
`of a CDMA communications system utilizing two likelihood
`functions that define maximum likelihood estimators of the
`mobile unit's location, based on attribute measurements,
`Such as but not limited to pilot Signal Strength, being made
`at the location of the mobile unit and reported back to a base
`Station. One of the likelihood functions comprises a frequen
`tist likelihood function and the other comprises a Bayesian
`modified likelihood function. The likelihood functions are
`based on the assumption that there is an RF model which
`provides the probability a mobile unit is able to detect one
`or more attributes associated with an arbitrary base Station,
`given it is located at an arbitrary location within the Service
`area. The frequentist likelihood assumes the RF model
`provides exact visibility probabilities. In contrast, the
`Bayesian-modified likelihood assumes the RF model only
`provides reasonable approximations to the true visibility
`probabilities, and uses the approximations to construct a
`Bayesian prior distribution for the true values. Each of the
`likelihoods can be used in an iterative fashion to produce a
`maximum likelihood estimator for the location of the mobile
`unit by determining the coordinates within the Service area
`which maximize the respective likelihood function.
`Alternatively, or in addition to, each of the likelihoods can
`be incorporated into a Sequential Bayesian procedure which
`outputs a posterior distribution for the location of the mobile
`unit.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is illustrative of a cellular service area divided into
`a plurality of cells,
`FIG. 2 is illustrative of the cells shown in FIG. 1 being
`further divided into Sub-cells;
`FIG. 3 is illustrative of an embodiment of the subject
`invention; and
`FIG. 4 including FIGS. 4A-4E comprise flow charts
`which are illustrative of the preferred methods of determin
`ing the locality of a mobile unit in accordance with the
`Subject invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`Referring now to the drawings and more particularly to
`FIG. 1, the reference numeral 10 denotes a service area for
`a CDMA cellular telephone system partitioned into a plu
`rality of contiguous cells 12, . . . , 12. FIG. 1 also depicts
`a plurality of base Stations 14, . . . , 14, located within the
`Service area 10. Also, the service area 10 includes at least
`one mobile switching center (MSC) 16. Typically each of
`
`Petitioner Uber Ex-1033, 0010
`
`

`

`US 6,889,053 B1
`
`15
`
`25
`
`35
`
`40
`
`3
`the base Stations 14, ..., 14, has a Sectorized antenna with
`a distinct pilot Signal channel associated with each Sector.
`Three Sectored antennas are most common. Each Sector of
`the antenna Serves a corresponding Sector of the associated
`cell. In FIG. 1, all of the base stations 14, . . . , 14, have
`three Sectors each. The three Sectors associated with base
`stations 14, for example, are denoted by the symbols 15,
`15, and 15,
`respectively. A mobile unit 20 is shown in
`sector 15.
`FIG.2 is illustrative of the cells 12,..., 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, respectively.
`Turning attention now to 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 the plurality of base
`Stations 14, . . . , 14, and connects to the local telephone
`System, not shown. A Server 22 including digital computer
`apparatuS 23 and memory 24, for Storing computation
`procedures, model parameters and System data, are typically
`located at the site of the MSC 16 for purposes which will
`now be explained.
`In the invention described in the referenced related patent,
`U.S. Pat. No. 6,496,701 entitled “Pattern Recognition-Based
`Geolocation,” each Sub-cell 18,..., 18, of the Service area
`10 is identified by a set of observable characteristics which
`are referred to as attributes. Examples of attributes are pilot
`signal strengths (Ec/Io), phase-offsets, angles of arrival, and
`pilot round trip delays. The invention of U.S. Pat. No.
`6,496,701 includes a database which contains attribute infor
`mation 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, (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 from its actual
`location in Sub-cell 18, and reports them via a message, e.g.,
`a pilot signal Strength measurement message (PSMM), to
`the base station(s) 14, ..., 14, (FIG. 3), which can be one
`or more of the base stations with which it is in communi
`cation. The base station(s) forward their respective reported
`measurements to the geolocation Server 22. The digital
`computer apparatuS 23 associated with the Server 22 Statis
`tically compares the measured values with the known
`attribute values stored in the database (memory) 24 of all the
`sub-cells 18 in the service area 10. The sub-cell 18, whose
`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 units
`location.
`In the above-referenced related application, Ser. No.
`09/294,997, entitled “A Bayesian-Update Based Location
`Prediction Method For CDMA systems”, a database is also
`used to assist the process of location estimation. However,
`in contrast to the first referenced patent application, i.e. U.S.
`Pat. No. 6,496,701, it uses a model based approach to
`generate a database containing pilot visibility probabilities
`for different Sub-cells 18 in the service area 10. The model
`based approach requires that a limited number of pilot
`Strength measurements be carried out along a few represen
`tative routes in the Service area 10. These measurements are
`then used to identify the parameters of the model that
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`characterizes the Service area and its RF environment. Once
`these parameters are identified, Simulations are then carried
`out to populate the database containing the pilot visibility
`probabilities, which are used in the computation of the
`location distribution of a mobile unit requesting location
`Service. An iterative procedure based on a Bayesian prob
`ability computation is then used to obtain improved esti
`mates of the mobile units location in response to multiple
`Sets of attribute measurements being reported by the mobile
`unit 20. The model-based approach eliminates the need to
`carry out extensive measurements required by the first
`named invention, U.S. Pat. No. 6,496,701.
`In the above-referenced related patent U.S. Pat. No.
`6,263,208, entitled “Geolocation Estimation Method For
`CDMA Terminals Based On Pilot Strength Measurements”,
`the model-based approach embodied in Ser. No. 09/294,997,
`“A Bayesian-Update Based Location Prediction
`Method... ' to characterize the RF environment is used, as
`is the iterative procedure for computing the Bayesian pos
`terior distribution for the location of the mobile. However,
`the database containing pilot visibility probabilities is
`replaced by analytical formulas that can be evaluated in real
`time. The evaluation procedures are compact and can typi
`cally be evaluated in the digital computer apparatus 23
`shown in FIG. 3.
`Considering the present invention, the analytic formula
`tion for the pilot visibility probabilities taught in the above
`referenced patent, U.S. Pat. No. 6,263,208, “Geolocation
`Estimation Method For CDMA terminals Based On Pilot
`Strength Measurements', now Serve as the Starting point for
`the derivation of two likelihood functions, hereafter referred
`to as the frequentist and Bayes-modified likelihood
`functions, respectively. Each of the likelihood functions is
`derived based on the assumptions and mathematical formu
`lations described in attached Appendix A. In as much as the
`likelihood functions depend on the analytic evaluation of the
`pilot visibility probabilities, attached Appendix B provides a
`self-contained development of the relevant details of these
`formulas. Each likelihood function is a function of (x,y), an
`arbitrary location of the mobile unit 20 in the X and y grid
`shown in FIG. 2. Accordingly, each likelihood function is
`used in a first method to obtain a maximum likelihood (ML)
`estimator of the location of the mobile unit 20 by finding the
`(x,y) coordinates which maximizes the value of the respec
`tive likelihood function. An iterative technique for Sequen
`tially updating each ML estimator with additional pilot
`Signal Strength measurements is utilized. In a Second
`method, each of the two likelihood functions are also
`incorporated into a sequential Bayesian procedure, which
`outputs a posterior distribution for the location of the mobile
`unit.
`The Bayes-modified likelihood function, whether it is
`used in the context of ML estimation or a Sequential Baye
`sian procedure, is a Substantial deviation from the inventions
`disclosed in the second and third above referenced related
`applications in the following way. Both of these previously
`disclosed inventions use an RF model to estimate pilot
`Visibility probabilities, the former via Simulation techniques,
`the latter via analytical formula evaluation, and implicitly
`assume that the model holds precisely. The present
`invention, however, uses the same RF model only to deter
`mine the means of beta distributions that are used as
`Bayesian priors for the true (unknown) pilot visibility prob
`abilities. A beta distribution is completely determined once
`its mean and variance have been Specified. Subject to the
`fixed mean values, each of the beta distributions is fully
`Specified by maximizing their variances. Maximizing the
`
`Petitioner Uber Ex-1033, 0011
`
`

`

`S
`variance of the beta priors, Subject to the Specified mean
`values, is consistent with a non-informative (vague) prior
`Specification.
`A Summary of the derivations which appear in Appendix
`A will now be given as prefatory remarks to the description
`of the overall mobile unit 20 location prediction process
`depicted in FIG. 4. In the example shown in FIGS. 1 and 2,
`if the primary base station for the mobile unit 20 is 14, the
`region designated as 17 in FIGS. 1 and 2 is the set of feasible
`locations of the mobile unit 20, and will hereafter be referred
`to as the region A. Along with the region A, the Set of all
`pilots K which are likely to be visible at Some of the grid
`points 18 in the set A is defined.
`For each (x,y)eA, let 0(x,y) denote the true probability
`that the mobile unit 20 is able to see the pilot in sector of
`base Station i when it is located at (x,y). From hereon, the
`notation i will be used to exclusively reference pilots from
`the set K. Let 0(x,y) denote an approximation of 0(x,y)
`based on an RF model described in Appendex B. For each
`pilot ij, let up, equal one or Zero depending on whether the
`mobile unit 20 can See pilot i at the S-th measurement epoch
`or not, respectively. The frequentist likelihood through the
`first S measurement epochs has the following recursive form,
`starting with the definition L'(x,y)=1:
`Ln(x, y) e Lil (x, y)
`(), (x, y))" (1–0, x, y)",
`
`ifeK
`
`1-4
`
`1
`
`(1)
`
`(x, y) e A
`
`For the Bayes-modified likelihood, the prior for 0(x,y) is
`a beta distribution with parameters:
`
`ai;(x, y) =
`f
`
`f3(x, y) = -
`
`if f(x, y) < 1/2
`1,
`6; (x,
`- if 0(x, y) > 1/2
`- P
`1 - 0 (x,y)
`1 - 6 (x,
`I'll, if y(x,y) is 1/2
`6 (x, y)
`1,
`if f(x, y) > 1/2.
`
`(2)
`
`35
`
`(3)
`
`40
`
`The Bayes-modified likelihood function through the first
`S measurement epochs has the following recursive form
`starting with the definition Let'(x,y)=1 for all (x,y)eA:
`
`45
`
`-,
`LiML(x, y) or List(x, y -
`Bf
`Bf
`ai (y,y) + f(x,y) + S-1
`iie K
`
`(x, y) e A
`
`where
`
`is the number of times pilot i was visible amongst the first
`S-1 measurement epochs.
`Each of the likelihood functions (1) and (4) are functions
`of (x,y)eA, an arbitrary possible location for the mobile unit
`20. The ML estimator for the location of the mobile unit 20
`is obtained by evaluating (1) for all (x,y)eA and Selecting the
`
`55
`
`60
`
`65
`
`US 6,889,053 B1
`
`15
`
`25
`
`6
`Values, Say (X, y), which gives the largest Value of (1).
`An updated ML estimate is produced at each measurement
`epoch. In a similar way, using function (4) rather than
`function (1) generates a sequence of Bayes-modified ML
`estimates, Say (Xen yen).
`Utilizing functions (1) or (4) with a Bayesian Sequential
`procedure can generate an alternative Sequence of predic
`tions for the location of the mobile unit 20. In each case, the
`initial prior distribution for the location of the mobile unit 20
`is assumed to be a discrete uniform distribution of the form:
`
`Pat (x, y) = Plul (x, y) =
`, (x,y) e A
`IAI (*
`
`(5)
`
`. , 18,
`.
`where A is the number of grid points 18, .
`contained within A. The posterior distribution for the loca
`tion of the mobile unit 20, through S measurement epochs,
`based on the frequentist likelihood function (1) is, up to a
`constant of proportionality:
`Plly, y) e Pit (x, y)
`(), (x, y))" (1-0, (x, y)",
`
`1-ps,
`
`6
`
`(6)
`
`ifeK
`
`(x, y) e A.
`
`Alternatively, the posterior distribution of the location of the
`mobile unit 20, through S measurement epochs, based on the
`Bayes-modified likelihood function (4) is, up to a constant
`of proportionality:
`
`(7)
`
`reper II. A
`
`Bf Wy
`
`Bi LV, ly
`
`iie K
`
`ai (y,y) + f(x + iy) + S-1
`
`-
`
`(x, y) e A.
`
`A Bayesian Sequence of predictions on where the mobile
`unit 20 is located follows from functions (6) or (7) by using
`the mean or mode of the posterior distribution obtained at
`each measurement epoch. When function (7) is used, the
`Sequence of prediction involves two distinct prior
`distributions, beta and discrete uniform, and the methodol
`ogy is referred to as doubly-Bayesian. This completes the
`Summary of Appendix A.
`A description of the mobile unit 20 location prediction
`process depicted in FIG. 4 will now be given. Considered in
`light of the accompanying appendices A and B and referring
`to FIGS. 4A-4E, the location prediction process in accor
`dance with the Subject invention, as noted above, is imple
`mented in Software which resides in the computer apparatus
`23 located at the geolocation server 22 (FIG. 3).
`The process, referred to hereinafter as the geolocation
`process, begins at step 30 (FIG. 4A) where it is waiting for
`a new location request to arrive. The geolocation process
`continually checks for the arrival of a location request at Step
`32, and if no Such request has arrived, it goes back to the
`waiting State (step 30). When a location Service request
`arrives, the geolocation process identifies the domain of
`Support, i.e., the Set of feasible locations, for the mobile's
`location based on either the identity of the primary base
`station of the mobile unit or the identity of the strongest pilot
`Signal reported by the mobile unit. This is indicated in Step
`34. Pilot signals will hereinafter be referred to simply as
`“pilots.”
`In the example shown in FIGS. 1 and 2, if the primary
`base Station for the mobile unit is base Station 14, the region
`
`Petitioner Uber Ex-1033, 0012
`
`

`

`US 6,889,053 B1
`
`15
`
`25
`
`35
`
`40
`
`7
`designated 17 in FIGS. 1 and 2 would be selected as the
`domain of Support for the mobile's location and will be
`hereinafter referred to as the region A. Along with the region
`A, the geolocation process at Step 34 also identifies the Set
`of all pilots K which are likely to be visible at some of the
`gridpoints 18 in the region A. Next, in Step 36 approxima
`tions for the conditional probability, conditioned on the
`mobile unit being at a location (x,y)eA, that each pilot in K
`is visible to the mobile are computed using equation (B9)
`from Appendix B. At this point, two decisions external to the
`geolocation process must be made. The first decision (Step
`38) that must be made is which of the ML estimation or
`Sequential Bayes estimation methods should be used. For
`each estimation procedure (ML or Sequential Bayes) the
`Second decision to be made is which type of likelihood,
`frequentist or Bayes-modified, should be used (steps 40 and
`42). These two decisions result in the four paths marked
`(2)–(5). FIGS. 4B-4E correspond to each of the four paths,
`only one of which would typically be used in any imple
`mentation of the geolocation process.
`First, suppose path (2) of FIG. 4A is chosen which
`represents the combination of the Sequential Bayes estima
`tion method and the frequentist likelihood function. This is
`shown in FIG. 4B. There step 44 assigns a discrete uniform
`prior probability to all grid points 18 in the set A. The
`discrete uniform prior reflects the initial State of no infor
`mation about the mobile units whereabouts, other than the
`fact that it resides in the region A. The frequentist likelihood
`function is initialized to unity and time is set to S=1. Step 46
`then evaluates the frequentist likelihood based on the first set
`(S=1) of visibility measurements using expression (1) noted
`above. In step 48, the posterior distribution based on the first
`Set of visibility measurements is evaluated using function
`(6). Expression (6) results in values that must be normalized
`So that when they are Summed over all (x,y)eA, the result
`will be unity. The posterior distribution gives the updated
`probability distribution for the location of the mobile unit
`20. A prediction of the location for the mobile unit 20 is next
`obtained in step 50 by computing either the mean or mode
`of the posterior distribution obtained from step 48. The
`prediction obtained in step 50 corresponds to the first set of
`measurements (S=1). If no further measurements are
`expected, the geolocation process terminates, otherwise as
`shown in Step 52 it proceeds to a waiting State (step 54) and
`stays there (via Step 56) until another set of measurements is
`received. At that point, the geolocation process proceeds to
`Step 58 and increments time up to S+1 before proceeding
`back to Step 46 and looping once again through Step 48 and
`step 50 which lead to an updated prediction for the location
`of the mobile unit 20. Eventually, no further measurements
`will be expected and the geolocation process will terminate
`at step 52.
`Next, suppose path (3) of FIG. 4A, which is depicted in
`FIG. 4C, is chosen which represents the combination of the
`Sequential Bayes estimation method and the Bayes-modified
`likelihood function. Step 60 directs the calculation, via
`equations (2) and (3), noted above, of the two parameters for
`the beta prior distribution that is used for the true unknown
`pilot visibility probabilities. Step 62 assigns a discrete
`uniform prior probability to all grid points 18 in the set A.
`The discrete uniform prior reflects the initial state of no
`information about the mobile units whereabouts, other than
`the fact that it resides in the region A. The Bayes-modified
`likelihood function is initialized to unity and time is set to
`S=1. Step 64 then evaluates the Bayes-modified likelihood
`based on the first Set (S=1) of visibility measurements using
`functional expression (4). In Step 66, the posterior distribu
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`tion based on the first set of visibility measurements is
`evaluated using equation (7). Equation (7) gives values that
`must be normalized So that when they are Summed over all
`(x,y)eA, the result will be unity. The posterior distribution
`gives the updated probability distribution for the location of
`the mobile unit 20. A prediction of the location for the
`mobile unit