(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2006/0240841 A1
`Bhattacharya
`(43) Pub. Date:
`Oct. 26, 2006
`
`US 20060240841A1
`
`(54) ESTIMATING THE LOCATION OF A
`WIRELESS TERMINAL BASED ON
`ASSISTED GPS AND PATTERN MATCHING
`
`(75)
`
`(73)
`
`(21)
`(22)
`
`Inventor: Tarun Kumar Bhattacharya, San Jose,
`CA (US)
`Correspondence Address:
`DEMONT & BREYER, LLC
`SUTE 250
`1OO COMMONS WAY
`HOLMDEL, NJ 07733 (US)
`Assignee: POLARIS WIRELESS, INC., Santa
`Clara, CA (US)
`Appl. No.:
`11/419,640
`
`Filed:
`
`May 22, 2006
`
`Publication Classification
`
`(51)
`
`Int. C.
`H04O 7/20
`
`(2006.01)
`
`(52) U.S. Cl. ........................................ 455/456.1; 455/12.1
`
`(57)
`
`ABSTRACT
`
`A method of using a non-GPS-derived technique to estimate
`the location of an Assisted-GPS-enabled wireless terminal
`for the purposes of generating location-specific assistance
`data for the wireless terminal is disclosed. The wireless
`terminal then uses the assistance data to acquire and process
`one or more GPS signals and to derive information that is
`probative of the wireless terminal's location. The GPS
`derived location information is then combined with non
`GPS-derived location to form an estimate of the location of
`the wireless terminal that is better than can be derived from
`either alone. This combination of GPS-derived and non-GPS
`techniques is particularly useful when the wireless terminal
`can only acquire one or two GPS signals because it is not
`possible to determine the location of the wireless terminal
`with only two GPS signals alone.
`
`2OO
`
`---4-20
`
`221
`
`
`
`
`
`
`
`Y
`
`7
`
`7 o 213
`
`Y
`
`7
`
`7
`
`LOcation Client
`
`Page 1 of 50
`
`SAMSUNG EX-1065
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 1 of 32
`
`US 2006/0240841 A1
`
`Figure 1 (Prior Art)
`
`
`
`121
`
`/
`
`1
`
`/ foL 113
`
`1
`
`/
`
`/
`
`LOCation Client
`
`Page 2 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 2 of 32
`
`US 2006/0240841 A1
`
`Figure 2
`
`
`
`
`
`
`
`200 O O
`
`211
`
`ar
`
`r
`
`-
`
`2 2 O
`
`221
`
`/
`
`/
`
`7
`WireleSS
`Switching Center
`212
`
`Y
`
`7
`
`/ o 213
`
`/
`
`7
`
`Y
`
`LOCation Client
`
`214
`
`/
`
`7
`
`7
`
`Page 3 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 3 of 32
`
`US 2006/0240841 A1
`
`Figure 3
`
`To/From Wireless Switching Center 211,
`ASSistance Server 212, and LOCation Client 213
`
`LOCation Server 214
`
`
`
`
`
`TranSCeiver
`
`PrOCeSSOr
`
`303
`
`301
`
`Operating System
`
`/ 214
`
`Application Software
`
`302
`
`LOCation-Trait Database
`
`Trait-Correction Database
`
`Page 4 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 4 of 32
`
`US 2006/0240841 A1
`
`Figure 4
`
`
`
`
`
`Build LOCation-Trait Database 313
`
`Build Trait-Correction Database 314
`
`401
`
`402
`
`Estimate LOCation of WireleSS
`Terminal 201
`
`Use Estimate of WireleSS Terminal
`In Location-Based Application
`
`Maintain LOCation-Trait Database 313
`and Trait-Correction Database 314
`
`405
`
`Page 5 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 5 of 32
`
`US 2006/0240841 A1
`
`Figure 5
`
`Partition Geographic Region
`into Plurality of Locations
`
`501
`
`ASCertain Location-Specific
`Traits for Each LOCation
`
`502
`
`
`
`TO PrOCeSS 402
`
`Page 6 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 6 of 32
`
`US 2006/0240841 A1
`
`Figure 6a
`
`
`
`Page 7 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 7 of 32
`
`US 2006/0240841 A1
`
`Figure 6b
`
`
`
`Page 8 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 8 of 32
`
`US 2006/0240841 A1
`
`Figure 6c
`
`LOCation 1
`
`LOCation 2
`
`LOCation 3
`
`
`
`2
`
`LOCation 4
`
`LOCation 6
`
`-- 200
`
`LOCation 8
`
`Page 9 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 9 of 32
`
`US 2006/0240841 A1
`
`Figure 6d
`
`
`
`- Location 9
`
`a
`
`Location 10
`
`
`
`it 2 - - - - - - - -
`
`
`
`- - -
`
`- - -
`
`- - -
`
`- - -
`
`- y--------
`
`Location 11
`
`% — Location 16
`
`%
`%
`
`Location 13
`
`N
`
`4
`
`% % LOCation 12
`- Location 15
`%
`? LOCation 19
`-200
`
`- LOCation 17
`
`— LOCation 18
`
`Page 10 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 10 of 32
`
`US 2006/0240841 A1
`
`Figure 6e
`
`- Location 20 - LOCations 21, 22, 23, and 24
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`%
`
`— Locations 27 and 28
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`LOCation 26 —/
`
`— LOCation 25
`
`Page 11 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 11 of 32
`
`US 2006/0240841 A1
`
`Figure 6f
`
`
`
`Page 12 of 50
`
`

`

`eet 12 of 32
`
`US 2006/0240841 Al
`
`Figure 6g
`
`
`
`
`
`
`
`
` _
`
`
`
`Page 13 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006
`
`Sheet 13 of 32
`
`US 2006/0240841 A1
`
`LOCation 1
`
`|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`? ? ? ? ? ?
`
`
`
`– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
`
`
`
`
`
`
`
`
`Page 14 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 14 of 32
`
`US 2006/0240841 A1
`
`Figure 6i
`
`LOCation 16
`
`Location 17
`
`— Location 18
`
`— Location 19
`
`H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H. H.
`
`Page 15 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 15 of 32
`
`US 2006/0240841 A1
`
`Figure 6
`
`
`
`ØS),
`
`LOCation 24
`
`LOCation 25
`
`)
`
`F- = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
`
`Location 35
`
`LOCation 20 —
`
`(
`
`LOCation 21
`
`LOCation 28 %
`
`|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`Slocation32s
`
`Location 2
`
`LOCation 3
`
`(
`
`LOCation 22
`
`LOCation 26
`
`)
`
`LOCation 23
`
`LOCation 27
`
`
`
`
`
`
`
`
`
`
`
`Page 16 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 16 of 32
`
`US 2006/0240841 A1
`
`Figure 6k
`
`Location
`/ 38
`LOCation
`42
`
`
`
`
`
`
`
`
`
`- Location 43
`
`Page 17 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 17 of 32
`
`US 2006/0240841 A1
`
`Figure 6L
`
`- - - - - - - - T - - -
`
`- - - - - - - -
`
`Page 18 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 18 of 32
`
`US 2006/0240841 A1
`
`Figure 6m
`
`
`
`Page 19 of 50
`
`

`

`ication Oct. 26, 2006 Sheet 19 Of 32
`
`US 2006/0240841 A1
`
`
`
`Page 20 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 20 of 32
`
`US 2006/0240841 A1
`
`Figure 7
`
`
`
`From Process 502
`
`Generate the Calibration Function for Every Possible Make and Model of Radio
`
`701
`
`702 M 402
`
`Store the Calibration Function for Every Possible Make and Model of Radio in
`Signal-Strength Corrections Database
`
`703
`
`To Processes 402 and 403
`
`Page 21 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 21 of 32
`
`US 2006/0240841 A1
`
`Figure 8a
`
`Reported Value, R
`
`
`
`Page 22 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 22 of 32
`
`US 2006/0240841 A1
`
`Figure 8b
`
`Reported Value, R
`
`
`
`Page 23 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 23 of 32
`
`US 2006/0240841 A1
`
`Figure 8C
`
`Calibrated
`Value, S
`
`N
`
`S = C(R, K, Q)
`
`-Ho Reported Value, R
`
`Page 24 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 24 of 32
`
`US 2006/0240841 A1
`
`Figure 9
`
`From PrOCeSS 401
`
`
`
`(Maintain LOCation-Trait Database 313
`And Trait-COrrection Database 314
`
`Develop a Drive-Test Regimen
`
`|
`
`Implement the Drive-Test
`Regimen
`
`I-405
`
`Implement the Drive-Test
`Regimen
`
`:
`
`Page 25 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 25 of 32
`
`US 2006/0240841 A1
`
`Figure 10
`
`From PrOCeSS 401
`
`Estimate LOCation of WireleSS Terminal
`
`
`
`Generate Probability
`Distributions Based On
`Observed Electromagnetic
`Traits
`
`Generate Probability
`Distributions Based On ASSisted
`GPS
`
`1002
`
`y
`403
`
`Combine Probability Distributions Based on
`Observed Electromagnetic Traits and Probability
`Distributions Based on ASSisted GPS to
`Generate Estimate of LOCation of WireleSS
`Terminal
`
`TO PrOCeSS 802
`
`Page 26 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 26 of 32
`
`US 2006/0240841 A1
`
`Figure 11a
`
`From PrOCeSS 401
`
`Generate Probability Distributions
`Based on Observed Electromagnetic Traits
`
`
`
`
`
`
`
`
`
`Receive Sets of Measurements of Electromagnetic Traits
`Observed with Respect to Wireless Terminal 201
`
`Correct Measurements of Electromagnetic Traits, When
`Appropriate, To Eliminate Systemic Biases
`
`Correct Measurements of Electromagnetic Traits, When
`Appropriate, To Eliminate Situational Biases
`
`1101
`
`1102
`
`1103
`
`y
`
`1001
`
`Perform Search Area Reduction
`
`Generate Yestimates of the location of the WireleSS terminal at
`times H, through Hy
`
`1104
`
`1105
`
`as -
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`- -
`
`TO PrOCeSS 1003
`
`Page 27 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 27 of 32
`
`US 2006/0240841 A1
`
`Figure 11b
`
`From ProceSS 1103
`
`Perform Search Area Reduction TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
`
`Designate a Location as improbable When a Difference of a Measurement of a Trait
`Differs from the Expected Value for that Trait By a Threshold
`
`a
`
`1111
`
`Designate a Location as Improbable When a Ranking of a Plurality of Measurements of a
`Trait Differs from the Ranking of the Expected Values for that Trait
`
`1112
`
`|
`
`Designate a Location as improbable When A Measurement of a Signal is Not Received
`When it Would Have Been Received if Wireless Terminal 201 Were in that Location
`
`1113
`
`y- 1104
`
`Designate a Location as improbable When A Measurement of a Signal is Received When
`it Would Not Have Been Received if WireleSS Terminal 201 Were in that LOCation
`
`1114
`
`Designate a Location as Improbable When a Location is Not Served by a Base Station
`That is Providing Service to Wireless Terminal 201
`
`Designate a Location as improbable When a Location is Not Served by a Neighboring
`Base Station of WireleSS Terminal 201
`
`1115
`
`a
`
`1116
`
`To PrOCeSS 1105
`
`Page 28 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 28 of 32
`
`US 2006/0240841 A1
`
`Figure 11c
`
`From POCeSS 1104
`
`- - - - - - - - - - - - - - - - - - - - - - - - -
`Generate Current Probability Distribution
`For LOCation of Wireless Terminal
`
`Summarily Set the Probability of Wireless Teminal 201 in a Location at Instant H, to
`Zero if the Location has been Designated as Improbable at Instant H. In Process 1104
`
`1121
`
`Generate Euclidean Norms Between Measurement and Expected Values for All
`Locations at All Instants Not Designated as Improbable
`
`
`
`1122
`
`11 / 05
`
`Generate Un-Normalized Probability Distribution at Each Instant Based on Euclidean
`Norms
`
`Generate Normalized Probability Distribution at Each Instant Based On Un-
`Normalized Current Probability Distribution
`
`1123
`
`1124
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`To Process 903
`
`Page 29 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 29 of 32
`
`US 2006/0240841 A1
`
`Figure 12
`
`From POCeSS 401
`
`Estimate Location of WireleSS Terminal
`Based on Assisted GPS
`
`Generate ASSistance Data Based on Estimate of LOCation of
`WireleSS Terminal at Instant H and Transmit it to WireleSS
`Terminal 201
`
`Receive GPS-Derived Information and Generate Preliminary
`Estimates of LOCation of WireleSS Terminal 201 Based on GPS
`Derived Information For Each of Instants G. Through Gz
`
`-
`
`
`
`TO ProceSS 903
`
`:
`| - 1002
`
`12O2
`
`1203
`
`1204
`
`Page 30 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 30 of 32
`
`US 2006/0240841 A1
`
`Figure 13
`
`From Subtask 1001
`
`From Subtask 1002
`
`combine Estimates Based O Observed
`Electromagnetic Traits and Assisted GPS
`Determine Composite Instants J. J. From Non-GPS-Based Provisional
`Instants H. Hy and GPS-Based Provisional Instants G. Gz
`
`Construct Probability Distributions W, ... We For Instants J. JE
`
`1301
`
`1302
`
`
`
`Determine Extrapolated Probability Distributions Di si < F, 1s is F, izi
`
`1303
`
`1
`y 003
`
`Compute Probability Distribution Li For Each Instant J. As Weighted
`Average of W, and Extrapolated Probability Distributions Di, j e {1,..., F} - {i}
`
`Generate Estimate of Location of Terminal 201 at One or More Instants Ji based on Li
`
`Provide LOCation Estimates of Process 1305 to LOCation Client 213
`
`Provide location EstimatesofProcess 1305 to Location client 213
`
`1304
`
`1305
`
`ls
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`- -
`
`To Process 702
`
`Page 31 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 31 of 32
`
`US 2006/0240841 A1
`
`Figure 14
`
`NO-GPS
`
`Instants
`
`H
`
`s
`
`H
`
`H
`
`s
`
`H.
`
`GPS
`Instants
`
`Composite
`Instants
`
`G.
`
`G.
`
`G
`
`G4
`
`G5
`
`Ge
`
`d
`
`J2
`
`J3
`
`J4
`
`J5
`
`J6
`
`J7 J8
`
`Jg
`
`Page 32 of 50
`
`

`

`Patent Application Publication Oct. 26, 2006 Sheet 32 of 32
`
`US 2006/0240841 A1
`
`Figure 15
`
`Non-GPS
`Instants
`
`GPS
`Instants
`
`Composite
`Instants
`
`Time
`
`Page 33 of 50
`
`

`

`US 2006/0240841 A1
`
`Oct. 26, 2006
`
`ESTMATING THE LOCATION OF A WIRELESS
`TERMINAL BASED ON ASSISTED GPS AND
`PATTERN MATCHING
`
`FIELD OF THE INVENTION
`0001. The present invention relates to telecommunica
`tions in general, and, more particularly, to a technique for
`estimating the location of a wireless terminal and using the
`estimate of the location in a location-based application.
`
`BACKGROUND
`0002 FIG. 1 depicts a diagram of the salient components
`of wireless telecommunications system 100 in accordance
`with the prior art. Wireless telecommunications system 100
`comprises: wireless terminal 101, base stations 102-1, 102
`2, and 102-3, wireless switching center 111, assistance
`server 112, location client 113, and Global Positioning
`System (“GPS) constellation 121. Wireless telecommuni
`cations system 100 provides wireless telecommunications
`service to all of geographic region 120, in well-known
`fashion.
`0003. The salient advantage of wireless telecommunica
`tions over wireline telecommunications is the mobility that
`is afforded to the users. On the other hand, the salient
`disadvantage of wireless telecommunications lies in that fact
`that because the user is mobile, an interested party might not
`be able to readily ascertain the location of the user.
`0004 Such interested parties might include both the user
`of the wireless terminal and remote parties. There are a
`variety of reasons why the user of a wireless terminal might
`be interested in knowing his or her location. For example,
`the user might be interested in telling a remote party where
`he or she is or might seek advice in navigation.
`0005. In addition, there are a variety of reasons why a
`remote party might be interested in knowing the location of
`the user. For example, the recipient of an E 9-1-1 emergency
`call from a wireless terminal might be interested in knowing
`the location of the wireless terminal so that emergency
`services vehicles can be dispatched to that location.
`0006 There are many techniques in the prior art for
`estimating the location of a wireless terminal.
`0007. In accordance with one technique, the location of a
`wireless terminal is estimated to be at the center of the cell
`or centroid of the sector in which the wireless terminal is
`located. This technique is advantageous in that it does not
`require that additional hardware be added to the wireless
`terminal or to the wireless telecommunications system, and,
`therefore, the first technique can be inexpensively imple
`mented in legacy systems. The first technique is only accu
`rate (in present cellular systems), however, to within a few
`kilometers, and, therefore, it is generally not acceptable for
`applications (e.g., emergency services dispatch, etc.) that
`require higher accuracy.
`0008. In accordance with a second technique, the location
`of a wireless terminal is estimated by triangulating the angle
`of arrival or multilaterating the time of arrival of the signals
`transmitted by the wireless terminal. This technique can
`achieve accuracy to within a few hundreds of meters and is
`advantageous in that it can be used with legacy wireless
`terminals. The disadvantage of this second technique, how
`
`ever, is that it generally requires that hardware be added to
`the telecommunication system's base stations, which can be
`prohibitively expensive.
`0009. In accordance with a third technique, the location
`of a wireless terminal is estimated by a radio navigation unit,
`such as, for example, a Global Positioning System (GPS)
`receiver, that is incorporated into the wireless terminal. This
`technique is typically accurate to within tens of meters but
`is disadvantageous in that it does not work consistently well
`indoors, in heavily wooded forests, or in urban canyons.
`Furthermore, the accuracy of this third technique can be
`severely degraded by multipath reflections.
`0010. Therefore, the need exists for a technique for
`estimating the location of a wireless terminal with higher
`resolution than the first technique and without some of the
`costs and disadvantages of the second and third techniques.
`
`SUMMARY OF THE INVENTION
`0011. The present invention enables the construction and
`use of a system that can estimate the location of a wireless
`terminal without some of the costs and limitations associated
`with techniques for doing so in the prior art.
`0012. The present invention is based on the recognition
`that there are traits of electromagnetic signals that are
`dependent on topography, the receiver, the location of the
`transmitter, and other factors. For example, if a particular
`radio station is known to be received strongly at a first
`location and weakly at a second location, and a given
`wireless terminal at an unknown location is receiving the
`radio station weakly, it is more likely that the wireless
`terminal is at the second location than at the first location.
`0013 By quantifying “strongly' and “weakly' and
`extending this principle to multiple traits and multiple
`signals, the present invention can estimate the location of a
`wireless terminal with greater accuracy.
`0014. The illustrative embodiment comprises: generating
`a first non-GPS-derived estimate of the location of a wireless
`terminal based on a first measurement of a trait of a first
`signal; and generating assistance data for a satellite signal
`that is received by the wireless terminal, wherein the assis
`tance data is based on the first non-GPS-derived estimate of
`the location of the wireless terminal.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0015 FIG. 1 depicts a map of a portion of a wireless
`telecommunications system in the prior art.
`0016 FIG. 2 depicts a diagram of the salient components
`of wireless telecommunications system 200 in accordance
`with the illustrative embodiment of the present invention.
`0017 FIG. 3 depicts a block diagram of the salient
`components of location server 214, as shown in FIG. 2, in
`accordance with the illustrative embodiment.
`0018 FIG. 4 depicts a flowchart of the salient processes
`performed in accordance with the illustrative embodiment of
`the present invention.
`0.019
`FIG. 5 depicts a flowchart of the salient processes
`performed in accordance with process 401 of FIG. 4:
`building Location-Trait Database 313.
`
`Page 34 of 50
`
`

`

`US 2006/0240841 A1
`
`Oct. 26, 2006
`
`0020 FIGS. 6a through 6k depict geographic regions and
`their deconstruction into a plurality of locations.
`0021
`FIG. 6L depicts an alternative partitioning of geo
`graphic region 220 into 64 square locations.
`0022 FIG. 6m depicts a graphical representation of an
`adjacency graph of geographic region 220 as partitioned in
`FIGS. 6c through 6e.
`0023 FIG. 6n depicts a graphical representation of an
`adjacency graph of the highway intersection partitioned in
`FIGS. 6h through 6k.
`0024 FIG. 7 depicts a flowchart of the salient processes
`performed as part of process 402 of FIG. 4: populating
`Trait-Correction Database 313.
`0025 FIGS. 8a through 8c depict illustrative distortion
`and correction curves.
`0026 FIG. 9 depicts a flowchart of the salient processes
`performed in process 403 (of FIG. 4): maintaining Loca
`tion-Trait Database 313.
`0027 FIG. 10 depicts a flowchart of the salient processes
`performed in process 701 of FIG. 7: estimating the location
`of wireless terminal 201.
`0028 FIG. 11a depicts a flowchart of the salient pro
`cesses performed in process 901 of FIG. 9: generating the
`probability distribution for the location of wireless terminal
`201 based on the traits of one or more signals received by,
`or transmitted to, wireless terminal 201 at instants H
`through H.
`0029 FIG. 11b depicts a flowchart of the salient pro
`cesses performed in accordance with process 1104 of FIG.
`11a: search area reduction.
`0030 FIG. 11c depicts a flowchart of the salient pro
`cesses performed in accordance with process 1105: gener
`ating the probability distribution for that wireless terminal
`201 at each of instants H through H.
`0031
`FIG. 12 depicts a flowchart of the salient processes
`performed in process 902 of FIG. 9: generating the prob
`ability distribution for the location of wireless terminal 201
`based on GPS-derived information (i.e., information from
`GPS constellation 221).
`0032 FIG. 13 depicts a flowchart of the salient processes
`performed in process 903 of FIG. 9: combining non-GPS
`based and GPS-based probability distributions for the loca
`tion of wireless terminal 201.
`0033 FIG. 14 depicts a first example of combining
`non-GPS-based instants H through H and GPS-based
`instants G through GZ into composite instants J through Jr.
`0034 FIG. 15 depicts a second example of combining
`non-GPS-based instants H through H and GPS-based
`instants G through G2 into composite instants J through J.
`
`DETAILED DESCRIPTION
`0035. For the purposes of this specification, the following
`terms and their inflected forms are defined as follows:
`0036. The term “location' is defined as a one-dimen
`sional point, a two-dimensional area, or a three-dimen
`sional Volume.
`
`0037. The term “staying probability” is defined as an
`estimate of the probability Ps(b. T. N. W) that wireless
`terminal W in location bat calendrical time Twill still
`be in location b at time T+At, given environmental
`conditions, N.
`0038. The term “moving probability” is defined as an
`estimate of the probability PM (b. T. N. W., c) that
`wireless terminal W in location bat calendrical time T
`will be in adjacent location c at time T+At, given
`environmental conditions, N.
`0.039 The term “environmental conditions N,” are
`defined to include one or more physical aspects of the
`environment, and includes, but is not limited to, the
`weather, the astronomical conditions, atmospheric con
`ditions, the quantity and density of radio traffic, the
`quantity and density of vehicular traffic, road and
`sidewalk construction, etc.
`0040. The term “calendrical time T is defined as the
`time as denominated in one or more measures (e.g.,
`seconds, minutes, hours, time of day, day, day of week,
`month, month of year, year, etc.).
`0041. Overview—FIG. 2 depicts a diagram of the salient
`components of wireless telecommunications system 200 in
`accordance with the illustrative embodiment of the present
`invention. Wireless telecommunications system 200 com
`prises: wireless terminal 201, base stations 202-1, 202-2,
`and 202-3, wireless switching center 211, assistance server
`212, location client 213, location server 214, and GPS
`constellation 221, which are interrelated as shown. The
`illustrative embodiment provides wireless telecommunica
`tions service to all of geographic region 220, in well-known
`fashion, estimates the location of wireless terminal 201
`within geographic region 220, and uses that estimate in a
`location-based application.
`0042. In accordance with the illustrative embodiment,
`wireless telecommunications service is provided to wireless
`terminal 201 in accordance with the Universal Mobile
`Telecommunications System, which is commonly known as
`“UMTS.” After reading this disclosure, however, it will be
`clear to those skilled in the art how to make and use
`alternative embodiments of the present invention that oper
`ate in accordance with one or more other air-interface
`standards (e.g., Global System Mobile “GSM, CDMA
`2000, IS-136 TDMA, IS-95 CDMA 3G Wideband CDMA,
`IEEE 802.11 WiFi, 802.16 WiMax, Bluetooth, etc.) in one or
`more frequency bands.
`0043 Wireless terminal 201 comprises the hardware and
`software necessary to be UMTS-compliant and to perform
`the processes described below and in the accompanying
`figures. For example and without limitation, wireless termi
`nal 201 is capable of:
`0044) i. measuring one or more traits of one of more
`electromagnetic signals and of reporting the measure
`ments to location server 214, and
`0045 ii. transmitting one or more signals and of
`reporting the transmission parameters of the signals to
`location server 214, and
`0046) iii. receiving GPS assistance data from assis
`tance server 212 to assist it in acquiring and processing
`GPS ranging signals.
`
`Page 35 of 50
`
`

`

`US 2006/0240841 A1
`
`Oct. 26, 2006
`
`Wireless terminal 201 is mobile and can be at any location
`within geographic region 220. Although wireless tele
`communications system 200 comprises only one wire
`less terminal, it will be clear to those skilled in the art,
`after reading this disclosure, how to make and use
`alternative embodiments of the present invention that
`comprise any number of wireless terminals.
`0047 Base stations 202-1, 202-2, and 202-3 communi
`cate with wireless switching center 211 and with wireless
`terminal 201 via radio in well-known fashion. As is well
`known to those skilled in the art, base stations are also
`commonly referred to by a variety of alternative names such
`as access points, nodes, network interfaces, etc. Although
`the illustrative embodiment comprises three base stations, it
`will be clear to those skilled in the art, after reading this
`disclosure, how to make and use alternative embodiments of
`the present invention that comprise any number of base
`stations.
`0.048. In accordance with the illustrative embodiment of
`the present invention, base stations 202-1, 202-2, and 202-3
`are terrestrial, immobile, and within geographic region 220.
`It will be clear to those skilled in the art, after reading this
`disclosure, how to make and use alternative embodiments of
`the present invention in which some or all of the base
`stations are airborne, marine-based, or space-based, regard
`less of whether or not they are moving relative to the Earth's
`surface, and regardless of whether or not they are within
`geographic region 220.
`0049 Wireless switching center 211 comprises a switch
`that orchestrates the provisioning of telecommunications
`service to wireless terminal 201 and the flow of information
`to and from location server 214, as described below and in
`the accompanying figures. AS is well known to those skilled
`in the art, wireless Switching centers are also commonly
`referred to by other names Such as mobile Switching centers,
`mobile telephone Switching offices, routers, etc.
`0050 Although the illustrative embodiment comprises
`one wireless switching center, it will be clear to those skilled
`in the art, after reading this disclosure, how to make and use
`alternative embodiments of the present invention that com
`prise any number of wireless Switching centers. For
`example, when a wireless terminal can interact with two or
`more wireless Switching centers, the wireless Switching
`centers can exchange and share information that is useful in
`estimating the location of the wireless terminal. For
`example, the wireless Switching centers can use the IS-41
`protocol messages HandoffMeasurementRequest and Hand
`offMeasurementRequest2 to elicit signal-strength measure
`ments from one another. The use of two or more wireless
`Switching centers is particularly common when the geo
`graphic area serviced by the wireless Switching center is
`Small (e.g., local area networks, etc.) or when multiple
`wireless Switching centers serve a common area.
`0051. In accordance with the illustrative embodiment, all
`of the base stations servicing wireless terminal 201 are
`associated with wireless switching center 211. It will be
`clear to those skilled in the art, after reading this disclosure,
`how to make and use alternative embodiments of the present
`invention in which any number of base stations are associ
`ated with any number of wireless Switching centers.
`0.052
`Assistance server 212 comprises hardware and
`Software that is capable of performing the processes
`
`described below and in the accompanying figures. In gen
`eral, assistance server 212 generates GPS assistance data for
`wireless terminal 201 to aid wireless terminal 201 in acquir
`ing and processing GPS ranging signals from GPS constel
`lation 221. In accordance with the illustrative embodiment,
`assistance server 212 is a separate physical entity from
`location server 214; however, it will be clear to those skilled
`in the art, after reading this disclosure, how to make and use
`alternative embodiments of the present invention in which
`assistance server 212 and location server 214 share hard
`ware, software, or both.
`0053 Location client 213 comprises hardware and soft
`ware that use the estimate of the location of wireless
`terminal 201—provided by location server 214 in a loca
`tion-based application, as described below and in the accom
`panying figures.
`0054 Location server 214 comprises hardware and soft
`ware that generate one or more estimates of the location of
`wireless terminal 201 as described below and in the accom
`panying figures. It will be clear to those skilled in the art,
`after reading this disclosure, how to make and use location
`server 214. Furthermore, although location server 214 is
`depicted in FIG. 2 as physically distinct from wireless
`switching center 211, it will be clear to those skilled in the
`art, after reading this disclosure, how to make and use
`alternative embodiments of the present invention in which
`location server 214 is wholly or partially integrated with
`wireless switching center 211.
`0055. In accordance with the illustrative embodiment,
`location server 214 communicates with wireless Switching
`center 211, assistance server 212, and location client 213 via
`a local area network; however it will be clear to those skilled
`in the art, after reading this disclosure, how to make and use
`alternative embodiments of the present invention in which
`location server 214 communicates with one or more of these
`entities via a different network such as, for example, the
`Internet, the Public Switched Telephone Network (PSTN),
`etc.
`In accordance with the illustrative embodiment,
`0056.
`wireless Switching center 211, assistance server 212, loca
`tion client 213, and location server 214 are outside of
`geographic region 220. It will be clear to those skilled in the
`art, after reading this disclosure, how to make and use
`alternative embodiments of the present invention in which
`Some or all of wireless Switching center 211, assistance
`server 212, location client 213, and location server 214 are
`instead within geographic region 220.
`0057 Location Server 214 FIG. 3 depicts a block dia
`gram of the salient components of location server 214 in
`accordance with the illustrative embodiment. Location
`server 214 comprises: processor 301, memory 302, and
`local-area network transceiver 303, which are intercon
`nected as shown.
`0058 Processor 301 is a general-purpose processor that is
`capable of executing operating system 311 and application
`Software 312, and of populating, amending, using, and
`managing Location-Trait Database 313 and Trait-Correction
`Database 314, as described in detail below and in the
`accompanying figures. It will be clear to those skilled in the
`art how to make and use processor 301.
`
`Page 36 of 50
`
`

`

`US 2006/0240841 A1
`
`Oct. 26, 2006
`
`0059 Memory 302 is a non-volatile memory that stores:
`0060) i. operating system 311, and
`0061 ii. application software 312, and
`0062) iii. Location-Trait Database 313, and
`0063) iv. Trait-Correction Database 314.
`It will be clear to those skilled in the art how to make and
`use memory 302.
`0064 Transceiver 303 enables location server 214 to
`transmit and receive information to and from wireless
`Switching center 211, assistance server 212, and location
`client 213. In addition, transceiver 303 enables location
`server 214 to transmit information to and receive informa
`tion from wi