Title of Invention

A METHOD FOR DETERMINING IN A PROCESSING UNIT THE LOCATION OF DEVICE

Abstract A method and apparatus for use in a hybrid position location system. The method and apparatus combines measurements from Global Positioning System (GPS) and terrestrial transceiver stations to compute the location of a device. An algebraic solution to hybrid position location system equations is output from the method and apparatus. The method and apparatus determines the position of a device using a non-iterative method, as against the use of a conventional iterative least mean square method. The method of the present invention can be used to solve the location system equations in scenarios where a non-iterative solution is desirable. In certain scenarios, the location system equations may have two possible solutions. An iterative method would converge on one of the solutions, without any indication of the existence of the other ambiguous solution. Moreover, the iterative method may converge on the incorrect of the two ambiguous solutions. Use of the presently disclosed method and apparatus yields both the ambiguous solutios. The disclosed method may be followed up with iterative methods, using the solutions from the algebraic method as initial estimates of the device location for the iterative method. A different process can then select the correct solution. Thus, the algebraic method can be used to detect the existence of ambiguous solutions, and to find both solutions.
Full Text FIELD OF THE INVENTION
The present invention relates generally to locating the position of devices, and specifically to a method and apparatus for determining the position of a device based upon information provided iErom Global Positioning System (GPS) satellites and associated position location systems.
BACKGROUND OF THE INVENTION
Recent developments in Global Portion system (GFS) and terrestrial mobile communications make it desirable to integrate GPS functionality into mobile communications devices such as cellular mobile stations. The cellular geolocation problem can be solved using either network-based methods or using handset-based methods.
Terrestrial Location
Network-based solutions rely on the signal transmitted from the mobile station and received at multiple fixed base stations. This can be accomplished by measuring the Time of Arrival (TOA) of the mobile station signal at the base stations. The mobile will lie on a hyperbola defined by the difference in time of arrival of the same signal at different base stations. An accurate position estimate depends on accurate synchronization and signal structure (bandwidth, etc.).
GPS-based Location
GPS-based location relies on a constellation of 24 satellites (plus one or more in-orbit spares) drding the earth every 12 hours. The satellites are at an altitude of 26,000 km. Each satellite transmits two signals: LI (1575.42 MHz) and L2 (1227.60 MHz). The LI signal is modulated with two Pseudo-random

Noise (FN) codes-the protected (P) code and the coarse/acquisition (C/A) code. The L2 signal curies only the P code. Each satellite transmits a unique code, allowing the receiver to identify the signals. Civilian navigation receivers use only die C/A on the LI frequency.
The idea behind GPS is to use satellites in space as reference points to determine location. By accurately measuring the distances from three satellites, the receiver "triangulates" its position anywhere on earth. The receiver measures distance by measuring the time required for the signal to travel from the satellite to the receiver. However, the problem in measuring the travel time is to know exactly when the signal left the satellite. To accomplish this, all the satellites and the receivers are synchronized in such a way that they generate the same code at exacdy the same time. Hence, by knowing die time that the signal left the satellite, and observing the time it receives the signal based on its internal dock, the receiver can determine the travel time of the signal If the receiver has an accurate dock synchronized with the C3*S satellites, three measurements from three satellites are sufficient to determine position in three dimensions. Each pseudorange (PR) measurement gives a p>osition on the surface of a sphere centered at the corresponding satellite. The GPS satellites are placed in a very precise orbit according to the GPS master plan. GPS receivers have a stored "almanac" which indicates where eadi satellite is in the sky at a given time. Ground stations continuously monitor GPS satellites to observe dieir variation in orbit. Once the satellite position has been measured, the information is relayed back tc die sateulie and the satellite broadcasts these minor errors "^hemeris" along with its timing information as part of die navigation message.
It is very expensive to have an accurate dock at the GPS receiver. In practice, GPS receivers measure time of arrival differences from four satellites with respect to its own dock and then solve for both the us^s position and die dock bias with respect to GPS time. Hgure 1 shows four satellites 101,102,103, 104 and a GPS receiver 105. Measuring time of arrival differenoes from kna satellites involves solving a system of four equations with four unknowns given the PR measurements and satellite positions (satellite data) as shown in Hgure 1. In other words, due to receiver clock error, the four spheres will not intersect at a single point. The recdver then adjusts its dodc sudi that the four spheres intersect at one point.
Hybrid Position Location System
The terrestrial location solution and the GPS solution complement eadi

other. For example, in rural and subizzban areas not too many base stations can hear the mobUe station, but a GPS receiver can see four or more satellites. Conversely, in dense urban areas and inside buildings, GPS receivers may not detect enough satellites. Ho^vever, ti:\e snobile station can see two or znoie base Stations. The hybrid solution takes advantage of cellular/PCS information that is already available to botii the mobile station and ttve network. Combining GPS and terrestrial measurements provides substantial improvements in the availability of the location solution. The hybrid position location system m;^ combine Roimd-trip Delay (RTD) and Pilot phase measurements from the terrestrial network with GPS measurements:
The hybrid approach merges GPS arul network measurements to compute the location of the mobile station. The mobile station collects measurements from the GPS constdlation and cellular/PCS network. These measurements are fused together to produce an estimate of the mobile station position.
When enou^ GPS measurements are available, it is unnecessary to use network measurements. However, when tiiere are less than four satellites or, in the case of bad geometry, four or more satellite meastirements, the measurements must be complemented with network measurements. The miiumum number of measurements for obtaining a solution will be equal to the number of unknowns. Since the system has four unknowns (three coordinates and GPS receiver time bias) the minimum nuntber of measuronents to obtain a solution will be iova. For any satellite measurements that are not available round trip delay (RTD) measureoKnts may be used to determine the range to a base station. RTD measurements may also be used to provide time aiding information. In addition other information, such as HM offeet pseudo-ranges (if time bias is the same as for satellites), FN offeet differences (if time bias is difierent) and altitude aiding may be tased to provide additional information and thus iius^ase the numbs of equations that include the unknowns being sought (i,e., X, y, 2, and time o^set). As long as the total nvimber of equations is krger than four it will be posable to find a solution.
Roimd Trip Delay fRTD)
The pilot timing on the forward link of each sector in the base station is synchronized with GPS system time. The mobile station time reference is the time of occurrence, as measured at the mobile station antenna connector of the earliest arriving usable multipatii component being used in the demodulation. The mobile station time reference is used as tiie transmit time of tiie reverse

traffic and access chaxmels.
Figure 2 shows one terrestrial transceiver station 201 and a mcAik station 202. As shown in Figure 2, tfie mobile 202 uses the recdved time reference hom. the serving base station 201 as its own time reference. Accoimting for its own hardware and software delays, the mobile station trar\smits its signal such that it is received back at the serving base station 201 delayed by a total of 2r, assuming tiiat the fcnward and reverse Iiz\ks have essentially equal propagation dela3rs. The total delay is measured at tiie base station by correlating the received signal from die mobile station 202 with the referenced signal at time T^. The measured RTD correq>onds to twice Ae distance betwea\ ^ mobile 2D2 and the base station 201 (after calibratian of base station side hardware delays).
Note that knowledge of Hvs FN of the serving base station can also be used (due to sectorization as a roug^ an^ of arrival (AOA) measurement) to help with resolving ambiguity.
Pilot Phase Measurements
The mobile station is continuotisly searching for active and neig^iboring pilots. In the process, it measures tiie FN o^et of each pilot it receives. If the time reference is the same on both FN offset and satellite measurements tiien the bias on iHnese measurements (as measured at the corresponding antenna coimector) will be the same. They can tiien botii be regarded as pseudo-ranges.
If the time referents are dizrerent then we can simply use FN offset differences between each pilot and tiie reference (earliest arrival) pilot The pilot FN phase ditference is the same as time difference of arrival (TDOA) of tiie two pilots from the two base stations. Hgure 4 shows two such base stations 401 and a mobile station 405.
Note that on most cellular S3^stems antennas are sectorized and each FN is associated with a sector radier than widi a base statioiL Hence, eadi measuronsit can provide, in addition to the TDOA information, some level of angle of arrival information (AOA) that can be used to resolve ambiguity.
Altitude aiding measurement
It is always possible to determine with which sector the phone is in communicating. This can give an estimate of the phones position to within three to five kilometers. Network plaiming is usually done based on digital maps of the coverage area. Based on terrain information and knowledge of the sector it is always possible to obtain a good estimate of the user elevation.

3-D positianing with three satellites
Figure 3 shows three satellites 301, 302, 303, a terrestrial transceiver station 304, and a mobile station 305. As shown in Figuxe 3, since fite mobile Station 305 is receiving CDMA signals from at least cme base station 304, the mobile 305 will acquire System tune. Its sense of system time is delayed with respect to true system time at the serving base station 304 by tiie propagation delay T between the mobile staticm 305 and base station 304. Qnoe the mobile
station 305 tries to access tite system, or is on the tra^ dtannel, the
RTD propagation dday t is estimated by —r—• This estimate can be used to adjust
the mobile system time to correspond to "true" GPS time. Now a mobik dock within the mobile station 305 is synchronized with GPS time; hence only three measurements from three satellites 301, 302, 303 are needed. Note that multipath does not impact the performance of the system because the mobile system time is shifted from GPS time by T regardless of whether the signal took a direct path or a reflected path. Instead of the RTD measurement at the base station 30, the mobile station"s measurement of the pilot phase offset can be used to reduce to three the number of satellites recjuired.
3-D positioning with two satellites
In addition to using the RTD to the serving base station for timing, the serving base station can also be used for ranging, as shown in Figure 5. Hgure 5 shows two satellites 501,502, a base station 504, and a mobile station 505. The distance to the serving base station 504 is given by R3Ct where C is the speed
of light Multipati\ here wiU impact positioning accuracy. Note that vinder certain geometry scenarios, we may get two ambiguous solutions. The ambiguity can be resolved by usang either sectorization or forward link informatioiu For example, pilot FN phase differerKe of a neighboring pilot can be used to resolve tiie resulting ambiguity. Also, pilot phase measurements may be used instead of, or in addrticm to, the RTD measurement.
3-D positioning with cme satellite
In this scenario, the proposed approach requires one additional measurement from the cellular/PCS network. This additional measurement covild be either a second RTD measurement or a pilot phase offset on the forweurd liiUc Figure 6 illustrates a satellite 601, two terrestrial transceiver statioi\s 604, and a mobile station 605. To reduce the impact of multipath on the

calculated position, die mobile station 605 reports the pilot phase of the earliest arriving path.
What combining different types of measurements, iterative solutions (such as the well-known "Newton-algorithm" based gradient approach) may be used to determine the solution (Le., the position of the device soought). However, in certain scenarios in which an iterative solution is used, two solutions are possible. Two solutions are possible because of the quadratic nature of the measurements that are used in the iterative equation (Le., the fact that at least one of the unknowns for -which a solution is required are raised to the secxmd power). The possible existence of two solutions creates ambiguity in the solution. That is, it is not dear which of the two solutions represent the location sought This applies to all the types of positioning systems (except AOA) including the Global Positioning System (GPS).
The existence of ambiguity dependents on the existence of measurement redundancy and on the relative locations of the satellites and terrestrial transceiver stations that provide location information. There is always ambiguity when there is no redurulancy in the measurements. However, ambiguity also always exists when there is redundancy, but the geometry is such that the amount of information provided is insufficient, even in light of additional measurements. However, these are rare occurrences.
An iterative method will converge to one of the solutions without any indication of the existence or position of the other solution. The particular solution to which it converges will depend solely on the irdtlal condition losed.
In the case of GPS, because of the distance of the satellites, the ambiguous solution is typically very far from the surface of the Earth. It is therefore impossible that the iterative method would converge to the wrong solution if given an initial condition dose to the surface of the earth However, when combining satellite measurements with base station measurements it is very possible that the two ambiguous solutions will be dose to each other. The iterative method would thus converge arbitrarily to one of the two solutions without a clear determination as to whether the solution to which it converged was the correct solution, or whether there are two solutions at all.
An exhaustive search can be performed to identify both solutions, if two solutions exist. However, if only one solution exists, it may be necessary to run the Least Mean Square (LMS) iterative process several times before a determination can be made that only one solution exists.
The algebraic method presented by Bancroft ("An Algebraic Solution of the GPS equations", published by IEEE on January 8,1984) and by Schipper

(njtilization of Exact Solutions of the Pseudo-range EquatMrns", VS. Patent Number 5,914^86, filed August 5, 1997) both require that all measurements have the same time bias. This is a CDnstraining requirement on the types of measurements that can be used with an sdgebraic method. Accordingly, when measurements from a CDMA communications S3^tem base station are bang lised as one of tiie sources of information, FN phase measurements are used to determine the pseudo-range to the base station. The use of FN phase mesisurement requires that ^le GPS receiver be synchronized with the cellular transceiver rK>t only witii respect to dock frequency, but also with reelect ot dock phase.
As noted above, another measurement that is advantageous to tise is the mesisiuement of RTD between ^be device whose location is being sou^t asad a terrestrial transceiver statiorv siurh as a cellular commtmication base statioru However, since the time bias in the range meastirement Ihat results from the measurement of RTD (which is zero) is not die same as the time bias associated with the GPS measurements, the rar^e measurement that is derived from RTD cannot be used in the algebraic solution at all. In order for the algebraic method to be the most useful method for identifying ambiguous solutions, the metiiod should be able to make use of aU the measurements that are available.
A more versatile algebraic mediod and apparatus for performing the method for use with hybrid positioning system eqviations is therefore described.
SUMMARY OF THE INVENTION
The disdosed method and apparatus is used in a hybrid position location syst^n. The disdosed method and apparatus combines measurements from a Global Positioning System (GPS) and terrestrial transceiver stations to con^te the location of a device. An algd>raic solution to hybrid positkm locati
Use of file presently disclosed, metihod and apparatus yields both the ambiguous solutions. The algebraic method may then be followed up with iterative methods, using the solutions from the algebraic method as initial estimates of the device location. A different process can then select the correct solution. Thus, the algebraic method can be used to detect the existence of ambiguotis solutions, and to find both solutions.
It should be understood by those skilled in the art that the method and apparatus disclosed is described in the context of a hybrid GPS and cellular location System. However, the disclosed method and apparatus is equally applicable to any location system that combines satellite and terrestrial measurements, such as integrated GPS and Long Range Navigation (LORAN) or other such terrestrial systems.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the following drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 shows four satellites and a GPS receiver;
Figure 2 shows on terrestrial transceiver station and a mobile station;
Figure 3 shows three satellites a terrestrial transceiver station, and a mobile station;
Figure 4 shows two such base station and a mobile station;
Figure 5 shows two satelites 501, 502, a base station 504, and a mobile station 505;
Figure 6 illustrates a satellite 601, two terrestrial transceiver stations 604, and a mobile station; and
Figure 7 shows the structure of one example of a device used to implement the disclosed method and apparatus.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
Overview
The disclosed method and apparatus is a System that uses both terrestrial transceiver stations and satellites (Le., a hybrid position location system) to

locate the position of a device in a position location system. The presently described method and apparatus is most useful in a hybrid position location system in which there are either not enough satelite measurements to determine a receiver"s position or in which a more accurate position can be determined using a combination of satellites and terrestrial transceiver stations, such as base stations of a cellular communication system.
In accordance with the disclosed method and apparatus, an "elgebrakf melhod is used to determine whetever two solution exist axui the value of both solutions, without iteration. Accordingly, the use of an algebraic method is preferable for obtaining both ambiguous solutiox^. The disclosed method and apparatus provides an algebraic (Le., non-iterative, approximate) solution to a System of navigation equations. The system of navigation equations includes one equation for each of the following: (1) the altitude of the device, as determined by altitude aiding information, (2) satellite measurements; (3) time aiding information (i.e., an estimate of the receiver clock bias); and (4) terrestrial measurements. The disclosed method and apparatus can be used to solve the system of navigation equations in scenarios where a non-iterative solution is desirable.
The approximation proposed here relies on linearizing satellite and altitude aiding measurements around an initial estimate of the user position. Lineeurizing the satellite and altitude measurements means removing terms that are squared (i.e., raised to a power of two). In one embodiment of the disclosed method and apparatus, the initial estimate of the user position is attained by using information indicating with which sector of a sectorized terrestrial transceiver station the user is communicating (equivalent to information for E911 phase 1). Alternatively, the initial location could be determined by any other means for estimating the location in question, such as previous location fixes, information attained through other petition location techniques, ete. In another embodiment of the method and apparatus disclosed, the initial estimate is either the center of the serving sector or the serving base station itself Accordingly, it should be understood that the estimate can be made using information regarding the location of the serving sector and/or the serving base station or any other information that would provide a reasonable estimation of the location being sought
An initial estimation based on the location of the serving base station will typically be accurate to within 10-15kms. The approximation made by linearizing the satellite and altitude aiding measurements is required because algebraic location determination methods can only be applied if the unknowns

that are raised to a power of two (i-e., tmknowns of the secxmd order) can be grouped together to form a single variable. The variable must be defined the same way in each of the navigation equations. This is not possible in the case in which the four types of ziavigation equations noted above are presented due to the differences in the form of each of these four equations. Linearizing the satellite and altitude aiding measurements reduces the number of second order unknowns and thus allows the second order unknowns to be grouped together and defined as a quadratic variable having a consistent definition throughout each of the navigation equations.
If one of the solutions is more than 15km from the reference point, then that solution will be inaccurate. However, such an inaccurate solution will not be the desired solution since we have predetermined that the solution should be within 15km of the reference point in cases in which the reference point cannot be predetermined to be within 15km of the user (Le., in systems in which cells have a radius of greater than 15 km, such as in Australia), the accuracy of the approximation can be improved if the altitude information is not approximated by a plane wave approximatioa
Accordingly, if the altitude information is linearized, then the ambiguity can be resolved as long as only one of the ambiguous solutions is within 10-15km of the center of the reference point. If both solutions are within 15km of the reference point, then the approximations are valid for both solutions. Therefore, the estimates for both solutions are accurate and one solution cannot be selected over the other. Therefore, other criteria must be used to distinguish the desired solution from the erroneous solution.
Once an approximate solution is determined, the approximate solution can be used as the initial condition for determining a more accurate iterative solution. Using the solutions from the approximate solution as initial estimates of the mobile station location provides a rapid convergence to a solution that lacks the error introduced by the approximation.
Some of the criteria that can be used to idoitify the correct solution include, but are not limited to: (1) sector angle opening (i.e., the angular size of the sector) and orientation, (2) distance to serving base station relative to expected cell size, (3) relative LMS cost of the two solutions in the case where there is redundancy, (4) received signal power and (5) Coverage maps available for network planning. Coverage maps would constitute the optimal criterion.
Although the description of the method in this document uses a hybrid GPS and cellular location system as an example, it can easily be applied to any location system that combines satellite and terrestrial measurements, such as

integrated GPS and LORAN.
There are different types of terrestrial measurements. These may be treated as belonging to one of three categories: ranges, pseudo-ranges or range differences. In addition estimates of the dock bias and/or the altitude may be available. The algebraic method and apparatus described below can handle any of the following combinations of satellite and base station measuremaits:
1. Terrestrial measurements and satellite measurements as
pseudoranges with the same bias (with or without the plane-wave
approximation).
2. Terrestrial measurements as range differences and satellite
measurements as pseudoranges (using the plane-wave approximation)
3. Terrestrial measurements as range and satellite measurements as
pseudoranges (using the plane-wave approximation). This corresponds to the
case in which Pseudo-random Noise (FN) offset differences (different bias than
satellites) and RTD are both available. Range measurements are then used to
convert all the range differences into ranges.
To any of bise measurement combinations can also be added:
• Clock bias estimate
• Altitude aiding (approximating the earth as a plane)
The techniques described in this document can be extended to other types of measurements.
Defirutions
In this section, notations are defined that are used throughout the rest of this document The subscript "s" is used to denote the satellite measurements and satellite locations. The subscript "b)" is used to denote the base station measure~nents and base station locations. The symbols r,p,S are used to
represent ranges, pseudo-ranges and range differences respectively. The coordinates of an entity are denoted as x„ =[jc«« y^ Zf^\. The system
unknotvns are represented as jr=[j bf -\x y z bf - The variable b
represents the satellite measurement time bias. The letter "h" will also be used
for base station measurements in the case where it can be assumed diat die bias
is die same as it is for satellite measurements. Conventional notetion and
conventional definitions are used for the norm of a vector |x.| = yxf + y? + z?
and the dot product of two vectors: = XfXj + y^yj + ZfZj.
The approximations that are being made in the manipulation of the

navigation equations assume tiiat an estimate of die receiver position is available that is accurate to within 10-15kms. In general, live sector with li\e earliest time of arrival at the phone will be referred to as the serving sector. The
reference point will be the center o£ die coverage area of the serving sector.
Note that if the size of the sector is larger than 10-15 km^ then it may be necesseuy to run an iteraticm of the disclosed metiiod wharein the reference point is updated according to tiie result In general howevo: this will not be necessary.
Altitude Aiding
An estimate of the altitude of the mobile station may be available from
terrain information, previous location solutions, or otiher sources or measurements. If the mobile location x. s[x. y^ z^] is defined in Earth
Centered Earth Fixed (ECEF) coordinates, the estimate of the altitude is an estimate of |J.|. In oidet to include altitude aiding in the algebraic solution, we
must e^q^ress the altitude aiding equation as a linear equation so that it will not restrict tiie choice of the algebraic method quadratic term. This can be achieved by rotating the coordinate frame such tiiat the altitude estimate becomes a linear combination of ihe unknowns in the S3rstem of equations (witiun a certain radius of the rotation reference point).
We rotate the ECEF coordinate frame such that the Z-axis passes through a point selected as an initial estimate of the location of the mobile station. In the case of a hybrid location sj^stem using terrestrial transceiver stations, such as cellular base stations, and GPS satellites, this initial estimate can be a point in ^ coverage area of a selected base staticm. If the base station measurements are pseudo-ranges or ranges then ^ cents of the servii\g sector can be used as initial estimate. If the base station measurements are range-differences, then the serving base station (range-difference reference) wUl have to be used as die initial estimate. This is due to Hxe constraints imposed by die method in the case of range-difiierence measurements.
If the initial estimate of the mobile station location is dose to die true location of the mobile station, then the estimate of the mobile station altitude is an estimate of the Z coordinate of the mobile station in the new rotated coordinate frame. It is obvious that linearization can alternatively be accomplished by transformix^ the altitude estimate to an estimate of the X coordinate or die Y coordinate of the mobile station (instead of the Z coordinate, as described above). The rotation matrix T is computed as follows:
represents the ECEF coordinates of the initial estimate

for the mobile station locatioiw then these coordinates can be transformed to a spherical coordinate system as follows. If0,


7 represents the coordinates of satellite i in ECEF coordinates, and J,;.
represents the coordinates of satellite i in the rotated coordinate system. Accordingly, Equation (5) represents the oMsrdinates of satellite i in the rotated coordinate sj^stem, as calculated fzom the coordinates of the sat^te in ECEF coordixuites. An estimate is thus provided for the Z coordinate of ti\e mobile station in the rotated coordinate system. The estimate of the Z coordinate can be taken into account simply by adding a new linear equation, z = z, to the system of equations. One goal of the present method is to define system equations in terms of X. Equation 6a provides a means for expressing the location sought in terms of the linear variable, X. The variables A^, l^ ax\d c, are selected to malce the equality true.
A u=l X+c (6a)
In Equaticm 6b, A^ is equal to tiie one-dimensional matrix [0 0 1 0], X is equal to ^ one dimensional matrix including die four unknowns x, y, z, and b, J. is equal to zero, and c, is equal to z.
/ / -



A system of equations can be written in the following form that express the relationship of each set of satellite mfiasurements to the location that is sought
Au=c (9a)
St ^ ^
Writing Equation 8b in the form of Equation 9a for eadt of a plurality erf satellites s, tiiroug^ s„ results iru

Time Aiding
An RTD measurement made at the reference base station can be used to estimate the bias in the mobile station clock. An RTD measurement is made by measuring the amount of time required for a signal transmitted from a base station to reach a mobile station, be retransmitted by the mobile station, and be received by the base station, assuming a synchronous retransmission (i.e., the transmitted and received signals are syndtronous) by ihe mobile station. If an assumption is made that the propagation time is equal in both directions, then the amoimt of time required for signals to travel from the base station to the mobile station can be determined from the one half the RTD measurement Accordingly, since the mobile station dock is offset from the base station dock by the amount of time required for a signal to traverse the distance between the base station and the mobile, the mobile station dock bias with respect to the base station can be determined. It should be noted that the mobile station dock is used as the time reference to measure the GPS pseudoranges. Accordingly:
(10)
where b is an estimate of the bias bias in the time reference used to perform GPS pseudorange measurements. Estimates of the clock bias may also

be available from, other source or measurements, such as previous navigatkm solutions. The estimate of &e dock bias can be taken into accoimt simply by expressing a new linear equation, b-b, in ^ form used for the ^tem of
X
equations. Here, ^5"=/,A+ c, z
A
Terrestrial Measurements ami Sj^stem Resolution
The terrestrial measurements can be treated in three ways:
1. Terrestrial pseudoranges
2. Terrestrial ranges
3. Terrestrial time difference of arrivals.
Terrestrial measurements as pseudo-ranges
Pilot phase measurements made by the mobile station can be treated as pseudoranges. In a System lasing both GPS and LORAN, LORAN measurements may be treated as pseudoranges. If the terrestrial measurements are treated as pseudoranges, they can be expressed as:
(12)
where b1, is the bias on each measurement
For each one of the measurements we perform the following manipulation. First subtract b, from both sides. then square both sides of the equation, resulting in:

Next, all of the second order terras are collected on the right side of the equation:






We can find tiie solutions tiiat correspond to these two values of X by substituting them into ti\e definition of tiie system variables as a function of X:
J _; _ (21)
2 2
To distingxaish tiie correct solution, we substitute tiiese two soluticms back into the system of equations to find the solution that yields very small residuals. If both solutions yield small residiutls, the system has two ambiguous solutions.
Terrestrial measurements as ranges
RTD measurement performed by a base station can be used to estimate the distance between the mobile station and tiie base station. The RTD measxarement made at die refereiM» base station can be treated as a range measurement The RTD measurement made at the reference base station can be combined with mobile station"s measurement of tiie time differerure of arrival of ti« pilot signal from the reference base staticm and other base statiorxs to obtain ranges to other base stations.
Note fliat in this case we do not r»eed to use the approximation for altitude aiding described above.
If tiie terrestrial measurements are treated as ranges, they can be expressed in the form:
(22)
For each one of the measurements we can perform the following manipudation:












We can find the solutions that correspond to these two values of λ by substituting them into the definition of the system variables as a function of λ
(41)
Ambquity Resolution
Algebraic resolutions of quadratic systems always yield two solutions, even in case of redimdancy. In accordance with one embodiment of the disclosed method and apparatus, to distinguish the correct solution, we substitute these two solutions back into the system of equations to find the solution that yeilds small residuals. If both solutions yield small residuals, the system has two ambiguous solutions. The correct solution will be the one that is consistent with the sector information associated with the base station measurements. Altennativety, it will be understood by those skilled in the art that any of the method used to determine the initial estimate of the location sought may also be used to assist in resolving the ambiguity (Le., select one of the two solutions). For example, the sector that is in communication with the device whose location is being sought may eliminate one of the solutions, alternatively, the location of the serving base station, the altitude of the device as determined by an altitude sensor within the device, or any other information that migiht be used to limit the possibility that one of the solutions is more likely to be correct As noted above, some of the criteria that can be used to resolve the ambiguity indude, but are not limited to: (1) sector angle opening (ie., the angular size of the sector) and orientation, (2) distance to serving base station relative to respected cell size, (3) relative LMS cost of the two solutions in the case where there is redundancy, (4) received signal power and (5) Coverage

maps available for network planning.
Figure 7 shows the structure of one device 700 used to implement the disclosed method and apparatus. As shown in Figure 7, the device 700 includes an antenna 702, a transceiver 704, and a processor 706. The antenna receives signals from each of the signal source, such as satellites and terrestrial transceiver stations. The signals are coupled from the antenna 702 to the transceiver 704. The signals are then processed by the transaceiver 704 in a manner well-known to those skilled in the art The transceivar may be an analog communications transceiver, digital communications transceiver, GPS position location transceiver, Loran transceiver, or any combination of these or other types of transceivers. The processed signals are then coupled to the processor 706. The processor 706 may be any type of computational device that is capable of performing the functions described above, including a general purpose microprocessor including memory, a special purpose microprocessor including memory, an application specific integrated circuit (ASIC) (or portion of an ASIC), dedicated circuity comprising discrete components, a state machine, or any general purpose computer, including mini-computer, desktop computer, laptop computer, or mainframe computer. The processor 706 outputs the location of the device 700. It shoiald be understood that the processing functions performed by the processor 700 may be distributed among several components that may or may not reside in the same physical location. For example, it is common for information to be collected by a device and transmitted to an external device, such as position determination equipment (FDE) which performs some of the required calculations and manipulations.
It should be noted that the preferred embodiments described above are dted by way of example, and the full scope of the invention is limited only by the claims. For example, while the application notes the use of communication base stations in several examples above, the terrestrial transceiver stations may be any station capable of providing signals that would accommodate the current method and apparatus for determining position location. likewise, the satellites referred to in many of the above examples are GPS satellites. Nonetheless, it will be understood that the satellites may be any system which provides additional signals that provide position location that can be used as described above for position location determinations.
WECLAIM:


WE CLAIM :
1. A method for determining in a processing unit the location of a device comprising the steps of:
a) receiving range information, pseudo-range information, and difference of arrival information related to a particular location sought to be determined, the range information being the distance between the location of the device and a first transmission point, the pseudo-range information being the distance between the location of the device and a second transmission point plus a clock bias, and the difference of arrival information being the difference between the time at which a reference signal transmitted from a third transmission point arrived at the location of the device and the time at which a second signal transmitted from a fourth transmission point arrived at the location of the device;
b) using a plane-wave approximation to eliminate any unknown second order terms associated with the pseudo-range information;
c) substituting a first quadratic variable for any unknown second order terms in the range information;
d) constructing a coordinate frame with one of the transmission points associated with the range information, the pseudo-range information, or the difference of arrival information as the origin of the coordinate frame;
e) expressing as a set of equations, the range difference of arrival, range, and pseudo-range information in terms of the newly constructed coordinate frame;
f) substituting a second quadratic variable for the coordinates of the unknown location, thus placing the equation for the difference of arrival, range, and pseudo-range information in the same form;
g) concatenating the equations for the range, pseudo-range and difference of arrival information into a single set of equations;

h) expressing the coordinates of the location of the device and the time bias as a function of the quadratic variable;
i) solving for the second quadratic variable, and thus determining two
solutions for the location sought; and j) outputting the location sought.
A method of determining in a processing unit the position of a device, comprising the steps of:
a) selecting an initial position estimate having an assumed accuracy;
b) linearlizing second order satellite and altitude aiding measurements around the initial estimate;
c) solving for the position of the device using the linearized satellite and altitude aiding measurements;
d) disregarding any solution for the position of the device that is more inaccurate than the assumed accuracy of the initial position estimate;
e) accepting any solution for the position of the device that is more accurate than the assumed accuracy of the initial position estimate; and
f) output the acceptable solutions for the position of the device.
The method as claimed in claim 2, wherein at least one of the acceptable solutions for the position of the device is used as an initial point for an iterative determination of the location of the position sought.
The method as claimed in claim 2, comprising the steps of : a) using at least one of the following criteria to identify a correction solution for the position of the device if more than one solution is more accurate than the assumed accuracy of the initial position estimate:
i) sector angle opening and orientation;
ii) distance to serving base station relative to expected cell size;

iii) relative Least Mean Square (LMS) cost of the two solutions for the
position of the device in the case where there is reduncancy;
iv) received signal power; and
v) coverage maps available for network planning.
A method of determining in a processing unit the coordinates, and thus the location, of a mobile device, comprising the steps of :
a) receiving altitude aiding information in the form of earth center, earth
fixed (ECEF) coordinates representing the location of the mobile device;
b) rotating the ECEF coordinate frame such that the z-axis passes through a
point selected as an initial estimate of the location of the mobile device;
c) using the altitude aiding information to provide the value of the z
coordinate in the new coordinate frame;
d) receiving one or more of range, pseudo-range, and range difference
information;
e) solving for time bias, the y coordinate of the mobile device, and the x
coordinate for the mobile device using one of more of the received range,
pseudo-range, and range difference information; and
f) outputting the x, y, z coordinates of the mobile device.

Documents:

in-pct-2002-0863-che abstract.pdf

in-pct-2002-0863-che claims-duplicate.pdf

in-pct-2002-0863-che claims.pdf

in-pct-2002-0863-che correspondences-others.pdf

in-pct-2002-0863-che correspondences-po.pdf

in-pct-2002-0863-che description (complete)-duplicate.pdf

in-pct-2002-0863-che description (complete).pdf

in-pct-2002-0863-che drawings.pdf

in-pct-2002-0863-che form-1.pdf

in-pct-2002-0863-che form-19.pdf

in-pct-2002-0863-che form-26.pdf

in-pct-2002-0863-che form-3.pdf

in-pct-2002-0863-che form-5.pdf

in-pct-2002-0863-che others.pdf

in-pct-2002-0863-che pct.pdf

in-pct-2002-0863-che petition.pdf


Patent Number 216152
Indian Patent Application Number IN/PCT/2002/863/CHE
PG Journal Number 13/2008
Publication Date 31-Mar-2008
Grant Date 10-Mar-2008
Date of Filing 07-Jun-2002
Name of Patentee QUALCOMM INCORPORATED
Applicant Address 5775 Morehouse Drive, San Diego, California 92121-1714,
Inventors:
# Inventor's Name Inventor's Address
1 FERNANDEZ-CORBATON, Ivan, J 919 Diamond Street San Diego, California 92109,
2 VAYANOS, Alkinoos, Hector 1134 South Felspar Street, #2 San Diego, California 92109,
3 AGASHE, Parag, A 10173 Camino Ruiz #4, San Diego, California 92126,
4 SOLIMAN, Samir, S 11412, Cypress Canyon Park Drive San Diego, California 92131,
PCT International Classification Number G01S 5/14
PCT International Application Number PCT/US00/33375
PCT International Filing date 2000-12-07
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 09/460,180 1999-12-10 U.S.A.