This invention concerns mobile communication positioning systems (MCPS). These types of systems include cellular telephone systems, paging systems, personal comiiiunication systems and low earth orbit telephone satellite systems where there is an adjunct that provides information about the locations of the mobile transceivers used in the systems.

Background Art

There are four primary modes of operation for a mobile communication positioning system (MCPS) that use timing measurements. These are Radial Remote-Positioning. Radial Self-Positioning. Hyperbolic Self-Positioning, and Hyperbolic Remote-Positioning. The [enn self- positioning means that the mobile works out its own location, remote- positioning means that the mobile telephone system works out where the mobile is located. Each of these modes are discussed in more detail below: Radial remote positioning uses measurements of round trip lime between a number of transceiver base stations and a mobile. Each round trip measurement constrains the location of the mobile to a circle that is centred on the transceiver. The intersection of two of these circles defines two possible locations for the mobile. The two-fold ambiguity is typically resolved using a third radial measurement involving a different base station

In some systems the round trip time is easy to measure. For example, in Global System for Mobile Communications (GSM) the round trip times can be derived from the standard Timing Advance measurements made by a base station with respect to a mobile. In normal operation the Timing Advance is quantised to one bit period.

Radial self-positioning works in a similar fashion to radial remote- positioning, except that the mobile uses the round trip time measurements to a number of base stations to work out its own location.

In hyperbolic self-positioning mode, the mobile will compare the time difference of arrival of the signals from three different base stations. The lime difference of arrival from a first pair ol base stations will generate one hyperbola, the time difference between a second pair of base stations will generate another hyperbola. The intersection of the two hyperbolas will define the location of the mobile.

In some cases, there will be two intersections, giving an ambiguity. This can be solved by the use of a fourth base station. This fourth base station will also allow a higher level of accuracy for the position measurement. Of course measurements from more than four base stations can also be combined to give more accurate measurements.

Hyperbolic remote-positioning works in a similar fashion to hyperbolic self-positioning, except that the transceivers will independently measure the lime of arrival of the signal from the mobile.

Disclosure of the Invention

In a first aspect, the invention is a mobile communication positioning system which includes a facility to make timing measurements between its base stations and a mobile, to indicate the distance of the mobile from at least one of the base stations. The distance indications are processed to produce an ambiguous indication of the position of Ihe mobile and the ambiguity is resolved using one or more of the following techniques.

In another aspect the invention is a method of determining the position of a mobile in a mobile communication positioning system. The method comprises the steps of calculating an ambiguous indication of the position of the mobile from measurements of the distances between base stations and the mobile, then resolving the ambiguities using one or more of the following techniques.

In cases where there is. even a two, -fold ambiguity. measurements of signal strength from one or more of the transceivers can be

used to resolve the ambiguity. Signal averaging or a signal strength contour map may be used to improve the accuracy of the measurements and thereby improve ambiguities more effectively.

Doppler shift measurements can be used to resolve ambiguity. At each of the ambiguous sites, the set of Doppler measurements can be compared with the set of Doppler measurements possible at each site. If the set of actual Doppler measurements do not represent a possible motion at one of the ambiguous position estimates, then that estimate can be ruled out and thus the ambiguity is resolved. Traffic flow information may be used to resolve, or at least aid in the resolution of. ambiguities where it indicates that a vehicle is consistently being measured as having a velocity significantly in e.xcess of that indicated by the prevailing traffic conditions.

Historical position data for a given vehicle or person. ambiguilies may be used to resolve ambiguities insofar as it indicates the most likely area in which the person is to be found.

Overlaying the ambiguous position estimates and their respective error ellipses or confidence regions, onto a map may assist in resolving ambiguities, for instance if the entire confidence interval lies over an impassable region.

For some applications where the positioning application is concurrent with a voice call, position ambiguity can be resolved by an operator questioning the mobile.

In a second aspect the combination of two or more ambiguity resolution techniques can be achieved by multi-sensor fusion, probabilistic approaches, nearest neighbour and kalman filter techniques that allow the integration of multiple sources of information over time.

It may take more than one measurement cycle to resolve all of the ambiguities. Sequences of ambiguous measurements may be examined

before a decision regarding the most likely position of the receiver can be made.

The preferred technique for integrating and evaluating the sequences of measurements is the kalman filter combined with probabilistic techniques to weight each of the observed events. The most likely sequence is chosen as indicating the true position of the mobile.

Buses, trains and light rail (trams) have limited domains due to physical limitations and prescribed routes. Such limitations effectively define lines-of-posilion which, when overlaid with a hyperbolic or radial locus, assist in resolving ambiguity.

Timetable information can also be used to give a first pass elimination of some ambiguous positions.

In a time division multiple access system, ambiguous hyperbolic-hyperbolic position measurements are resolved using the timing advance signal to determine a circular locus which will intersect the hyperbolic loci. The key advantage of this approach is that it uses a timing measurement inherent in the system thus allowing the positioning system to be fully functional with one less measurement of the type that the system is based upon. This scheme is useful for both remote and self-positioning. It is also possible to combine the round trip lime measurement with more than one hyperbolic measurement.

Where the measurements of liming advance and observed time difference between base stations are quantised to one bit. the accuracy of the measurements may be increased by dithering the measurements and averaging them to overcome the quantisation error. This may be achieved by introducing noise, or a sweep.

In another aspect a system embodying the invention may be continuously integrating information from many sources and keeping it up

to date in order to compensate, for instance for timc-of-day. day to clay and seasonal variations.

A good picture of traffic conditions can be derived from the position measurements and the rale at which vehicles are moving in certain regions of a city or along certain arterial roads. The data collected for a given vehicle or person over a period of time could by used to resolve ambiguity based on the statistical history of movement for that vehicle or person.

Gross traffic flow information could also be used to automatically detect changes to the road rules.

Over time the positioning system may build a very accurate signal strength map for each transceiver. Initially this information can be used to resolve ambiguity, as outlined above. The signal strength measurements could be included with the timing measurements to improve the overall accuracy of the system. As well, because in certain systems, such as GSM. there is constant reporting of the signal strength from around 6 transceiver sites, the signal strengths might provide sufficient accuracy by themselves to locate a mobile.

A useful spin-off of this technique is the ability to automatically derive signal strength contour maps. These maps can be used to improve the cellular network ^' s handover performance and for the purposes of network planning and design. The signal strength maps are continually updated, and so are able to compensate for seasonal changes, such as tree foliage changing multipath and signal occlusion, and this enables automatic adaption to any changes in the mobile network configuration.

A computerised kernel could have available many diverse information sources thai it would not be feasible to make available to all users. Such data may include detailed digital maps, locations of key services (services stations, emergency services, hospitals, doctors, restaurants, etc).

The kernel may also be able to integrate many information sources into ambiguity resolution algorithms that would not be feasible to be distributed. Applications could be built around the kernel could provide a range of services based upon position sensitive information. Examples ol such services include but are not limited to route guidance, directions to the nearest hospital, multi-modal route planning, planning courier services. calculating travel times, etc.

In another aspect, a time of arrival signal is detected even though the signal to noise ratio prohibits extraction of a base station identifier or voice communications, and taking all combinations of the times of arrivals of all possible originating base stations, a solution for each combination is formed as though it were the correct combination so that each combination produces a position estimate, and the net effect is a set of ambiguous position estimates which can then be resolved by the techniques claimed in any preceding claim.

In a further aspect, a mobile communications positioning system in which information about the route or terrain is combined with timing information to create ambiguous indications of position of a mobile which are then resolved.

Best Modes for Carrying out the Invention

Ambiguity Resolution

Signal Strength In cases where there is a two-fold ambiguity in a hyperbolic- hyperbolic system, measurements of signal strength from one or more of the transceivers can be used to resolve the ambiguity. This is because the signal strength measurement generates a roughly circular locus which can be used to differentiate the correct position. By comparing the measured signal strengths with those expected at each of the ambiguous position estimates, it

will be possible to determine which of the two. or more, ambiguous position estimates is the more likely. The advantage here is that the ambiguity can be resolved without using further transceivers.

This same technique can be applied to resolve the ambiguity in a circular-circular measurement that is derived from the round trip time from two transceiver sites. In this case it will be necessary to measure the signal strength from a third transceiver, however in some mobile comiiiunication systems, the mobile is constantly monitoring the signal strength of many transceiver sites, and reporting this back to the network. Accordingly, the signal strength measurements are at no cost to capacity. This technique could also be applied to solve ambiguity for hyperbolic-hyperbolic and circular-hyperbolic position measurements.

A single signal strength measurement may be susceptible to various fading influences, and the technique may use various signal averaging techniques to obtain a signal strength measure more indicative of the location of the mobile. A signal strength contour map may be generated, as discussed later, and this may also be used to resolve ambiguities.

/ ngie ofΛirival Ambiguity in hyperbolic-hyperbolic, circular-hyperbolic, and circular-circular systems can be resolved if the angle of arrival of the signal is known at one of the transceiver sites. This could be achieved by building special antenna arrays, however, in many mobile communication systems. the transceivers use directional antennas that create sectors. Although sectors tend to be quite wide, of the order of 120 degrees, there are still certain situations where knowledge of the sector angle and beamwidth can be used to resolve ambiguity.

It is possible that the ambiguity may be realised by a single angle-of-arrival measurement. Alternatively, more than one angle-of arrival measurement may be required for ambiguity resolution.

Because the resolution required in relatively low. that is it only has to decide between two separated points, the measurement of the angle can be coarse and relatively crude angle de tec lion mechanisms will work quite effectively whereas the same techniques would fail in a system wholly reliant upon angle-of-arrival measurements for position determination.

Doppler

In a cellular system the base stations are stationary and hence Doppler measurements measure the radial component of the ground speed of the mobile. Doppler shift measurements can be used to resolve ambiguity. At each of the ambiguous sites, the set of Doppler measurements can be compared with the set of Doppler measurements possible at each site. If the set of actual Doppler measurements do not represent a possible motion at one of the ambiguous position estimates, then that estimate can be ruled out and thus the ambiguity is resolved.

Traffic Flow Information

If traffic flow information is available then it is possible to use this to resolve, or at least aid in the resolution of. ambiguities. If a vehicle (ie a sequence of position measurements) is consistently being measured as having a velocity significantly in excess of that indicated by the prevailing traffic conditions then it is less likely that the vehicle is at this location and it is another sequence of position estimates that represent the true position.

Historical Position Data

With sufficient historical position data for a given vehicle or person, ambiguities could be resolved based on the most likely area in which the person is to be found. Examples include delivery vehicles with regular clients, vehicles with fixed or near fixed routes, persons or vehicles that tend to travel frequently along certain roads or through certain areas. Note thai

this technique would have lo be implemented carefully as it does not make a ^" binary decision but rather assigns probability to each of the ambiguous positions.

Map-Aided Ambiguity Resolution

Another ambiguity resolution techniques is lo overlay the ambiguous position estimates and their respective error ellipses or confidence regions, onto a map.

If the entire confidence region lies over water or any other medium that is impassable given the mode of transport, and the mobile is known to be in a car. bus or train, then it is highly unlikely that the vehicle is at that location. That is. the ambiguity has been reduced, or solved if it was only a two-fold ambiguity.

Operator InteiΥention

For some applications where the positioning application is concurrent with a voice call, position ambiguity can be resolved with non- signal based techniques.

All of the ambiguous positions can be given or displayed to a skilled operator who could then ask a few questions to determine which is the true position. One possible embodiment is to overlay all of the positions onto a map which has key features on it. The operator can then ask if the caller can see certain landmarks in order to determine their position. This technique is of particular use for roadside breakdown and emergency phone calls.

For a self-positioning process a similar technique could be employed. A driver in a vehicle may be lost but may know which suburb or possible suburbs they are in. This may be sufficient to resolve the ambiguity. Similarly the driver may know the name of the road they are or

were recently on. This information can be used to resolve position ambiguity.

Integration of Ambiguity Techniques The combination of two or more ambiguity resolution techniques can be achieved in a variety of ways, they include but are not limited to multi-sensor fusion, probabilistic approaches, nearest neighbour and kalman filler techniques that allow the integration of multiple sources of information over time. It may take more than one measurement cycle lo resolve all of the ambiguities. Sequences of ambiguous measurements may be examined before a decision regarding the most likely position of the receiver can be made. For example, there may be a three-fold ambiguity whereby the first measurement cycle is able lo eliminate one of the estimates. A second measurement may then provide sufficient information to eliminate one of the remaining estimates thus revealing a single estimate of position.

When resolving ambiguities over a period of time, it is then possible to introduce extra sources of information to aid in the ambiguity resolution process. For example, a given sequence of measurements may imply that a vehicle has violated a traffic rule, such as No right turn or One- Way Street. This does not mean that this sequence of measurements is the wrong one but it is contra-indicating. A stronger contraindicating event could be a sequence of measurements that indicate that a vehicle has travelled through a dead-end street. A sequence of measurements that implies that a law or physical rule has been violated represent evidence against a given sequence of position estimates being the correct ones.

The preferred technique for integrating and evaluating the sequences of measurements is the kalman filter combined with probabilistic techniques to weight each of the observed events. The most likely sequence is chosen as indicating Ihe true position of the mobile.

Buses, trains and light rail (trams) have limited domains due to physical limitations and prescribed routes. Such limitations effectively define lines-of-position. Staling that a train is somewhere on the tracks, possibly limited by e,xpectations derived from timetable information, still results in infinite position ambiguity. As discussed with the situation where in rural areas there are limited base stations, the route can be used as a line of position and overlaid with a hyperbolic or radial locus derived from a signal measurement. The intersections define possible positions. Timetable information can be used to give a first pass elimination of some ambiguous positions. If the route involves any sections that are one-way. such as loops, then Doppler information measuring velocity can also be used to eliminate some of the position estimates.

Use of Existing Timing Measurements Some communications systems inherently include a timing measurement that indicate the distance the mobile is from the base station. In other communications system it may be possible to make round trip time measurements. Both of these can be used to produce a circular locus which is not necessarily highly accurate, but is sufficient for ambiguity resolution in a system comprising a more accurate timing technique.

For example in a hyperbolic system, it is necessary to have three base stations in order to make a two dimensional positioning measurement, and even this measurement can be ambiguous.

However in a number of mobile communications systems it is possible to measure the round trip time to a mobile while a call is in progress. This is typically required in lime division multiple access (TDMA) system where mobile transmitters have lo adjust the timing of their signal based on distance from the base station in order to ensure that the signal arrives at the base station at the correct time slot and thus avoiding interference from other signals. An example of such a timing measurement

is the timing advance signal of the GSM system. Since the timing advance signal is a function of distance from the base station . it is possible to use the timing advance to determine the circular locus on which the mobile must lie. The timing advance measurement is only made to one base station and is only made for phones actively engaged in a call.

The timing advance measurement, while being much less accurate then the time difference measurements, provides enough information to distinguish between the two (or more) ambiguous position estimates. The key advantage of this approach is that it uses a timing measurement inherent in the system thus allowing the positioning system to be fully functional with one less measurement of the type thai the system is based upon.

This scheme is useful for both remote and self-positioning. It is also possible lo combine the round trip time measurement with more than one hyperbolic measurement. In the current version of GSM. measurements are made of the timing advance and of the observed time difference between base stations. However these measurements are quantised lo one bit. To increase the accuracy of these measurements, without altering the GSM specification or making major alterations to the base stations or mobiles, requires the introduction of noise into the system timing, so that Ihe measurements are dithered. Averaging can then overcome the quantisation error.

It is possible to also overcome the quantisation error by introducing a deterministic change in the timing of the system, for instance by using a linear sweep. This then causes both Ihe timing advance and the time difference signals to dither. By averaging the dithered measurements it is possible lo increase the accuracy beyond the quantisation error. This could be done with only software changes lo the mobile terminal.

Another way is to dither the timing of the base station transmitter. If the base station is fed by a pulse code modulation link, then by inserting a simple programmable delay device between the link and the

transmitter, any form of dither could introduced. This provides a means to improve system accuracy without modifying the base station transmitter.

Learning Systems A system embodying the invention may be continuously integrating information from many sources to keep the information up lo date and compensating for time-of-day. day to day and seasonal variations.

Feedback from the position measurement process will allow the system to continuously learn and improve.

Road Movement Data

With the ability to position a large number of mobile phones, a good picture of traffic conditions can be derived from the position measurements and the rate at which vehicles are moving in certain regions of a city or along certain arterial roads. The applications for such data include but are not limited to dynamic roule guidance, emergency vehicle dispatch, road planning.

Data could be collected for a given vehicle or person over a period of time and then used lo resolve ambiguity based on the statistical history of movement for that vehicle or person.

Gross traffic flow information could also be used to automatically detect changes to the road rules, information that is very valuable to systems such as route guidance. For example, if vehicle stop turning right at an intersection, then it implies that a No Right Turn has been installed. Similarly if no vehicles travel across a particular intersection in a given direction, that could indicate the road has been closed. The large amount of position information afforded by a mobile phone positioning system would allow such techniques to be feasible.

Signal Strength Learning

When il is in operation, a positioning system based primarily on timing measurements will make a large number of accurate position measurements. As well, for each of these measurements it is possible to measure the signal strength. This means thai over time the positioning system can build a very accurate signal strength map for each transceiver. Initially this information can be used to resolve ambiguity, as outlined above. The signal strength measurements could be included with the timing measurements lo improve the overall accuracy of the system. As well. because in certain systems, such as GSM. there is constant reporting of the signal strength from around G transceiver sites, the signal strengths might provide sufficient accuracy by themselves to locate a mobile.

The locus of the signal strength measurement is theoretically circular, however it is likely to be a considerably more complex shape. including ambiguities. It is straightforward to generate algorithms to allow the proper usage of this information. In the first instance a piece-wise linear representation of the locus would allow computationally effective algorithms. Other techniques such as pattern matching might be useful. A useful spin-oft of this technique is the ability to automatically derive signal strength contour maps. These maps can be used to improve the cellular network ^' s handover performance and for the purposes of network planning and design. The signal strength maps are continually updated, and so are able to compensate for seasonal changes. such as tree foliage changing multipath and signal occlusion, and this enables automatic adaption to any changes in the mobile network configuration.

Ambiguity Generation In GSM. and similar systems, the base stations are differentiated by frequency and by an identifier, or colour code. To use a base station signal for positioning, its identifier or colour code must be decoded to determine the position of the originating signal. Without the colour code, it is not possible to determine which of the base stations using that frequency had transmitted a given signal. Signal propagation limitations will rule out some of the base stations and. if available, signal strength measurements may rule out others but it may be possible that there is more than one base station that could be the originator of the detected signal.

The transmissions from base stations include a training sequence that can be detected at lower signal-to-noise ratios than is possible for the maintenance of voice communications. That is. it is possible lo make a time-of-arrival measurement but not have sufficient signal-to-noise to be able to decode the actual signal, a component of which is the base station identifier (colour code). Hence we can have the situation where a timing measurement is available but which cannot be unambiguously tied to a base station. Taking all combinations of possible originating base stations it is possible to form a solution for each combination as though it were the correct combination. Each combination will produce a position estimate, or more if an ambiguous positioning solution arises. The net effect is a set of position estimates, ie ambiguity which can then be resolved by the techniques already discussed.

Consider as an example the situation where three time-of arrival measurements have been made from three different frequencies. Of these, froq X is fully decoded and is known to come from base station A. Measurements of freq Y and Z are low signal to noise and have been determined (based on limits of signal propagation) to have arisen from base

stations B & C and D &E respectively. The following combinations are possible when solving for position: {Λ.B.D} . (A.B.E) . (Λ.C.Dj . { A.C.D J . Using the timing measurements, ihe position estimation process is repeated four times, once for each combination of possible base stations resulting in at least 4 position estimates which are resolved using other techniques as discussed.

In areas with low density of base stations, such as along highways, there may be continuous voice coverage but at any given time it is possible that the mobile is only within range of a single base station or perhaps only two base stations. This is not sufficient to make a position estimate. Two base stations can be used for a single time difference measurement defining a hyperbolic locus. A single base station can be used to obtain a circular locus via a timing advance or similar measurement. Whatever the system, a single locus represent infinite position ambiguity. the mobile could be at any point on the curve. In rural areas, it is quite likely that the mobile will be on or near major roads. Thus the road can be used as a line of position and the mobile ^' s position is defined as those points where the locus intersects with major roads. There will most likely be more than one such intersecting point resulting in ambiguity. Ambiguity resolution techniques are then used. Similar consideration is given lo mobiles in vehicles that travel fixed routes.

Chopstick decoding The GSM system and most analogue systems use frequency division multiple access. This means that at one base station there are a number of frequencies being transmitted at the same time. If these signals of different frequency have a know phase relationship (either by being linked to a common source, or by a reference phase monitoring receiver that broadcasts the phase relationship) then a mobile receiver can monitor the phase difference between the two stations.

The virtue of this scheme is that the frequency difference between the two frequencies will have a much longer wavelength than either of the two original frequencies. This means that the phase difference can provide a direct measurement of the distance from the base station, without any ambiguity. For example, suppose that one frequency is at 900 MHz and the second is at 900.2 MHz. Each of the original frequencies have a wavelength of about 0.33m. If the uncertainly in distance is about 1 km, then there are 3000 possible locations that could provide the same phase measurement for a single frequency. However the difference frequency will be 200 kHz. so the wavelength will be 1500m. so if the original uncertainty is 1 km there will be only one possible location.

The overall position accuracy is proportional to the frequency difference, so thai if there is more than two frequencies being transmitted at a time from one site, then the closest two frequencies could be used to resolve ambiguity and the further apart frequencies could be used to improve accuracy. This is why the scheme is called chopstick decoding, a reference to the children's piano drill which involves playing pairs of keys, each pair further apart. It should be possible lo integrate all pair wise measurements in an optimal fashion. This scheme will also work in a remote positioning scheme by ordering the mobile to change frequencies, provided that the mobile frequency synthesiser can able to maintain a known phase relationship between the different frequencies.

This technique will provide a very significant increase in accuracy, particularly if there are a range of different frequencies, allowing close pairs to be used to resolve ambiguity and far apart pairs to increase accuracy.

This technique will also decrease the number of base stations needed to make a measurement because a measurement from a single base station will provide a distance measurement. The technique might also provide improved multipath rejection.

This technique differs from frequency differencing techniques in used in the Global Positioning System, as there is only one possible frequency difference in that case, and the difference frequency is still highly ambiguous. The invention also pertains to other positioning systems and to vehicles other than motor vehicles, such as people carrying mobile telephones, ferry fleets, and trains.

It will be appreciated by persons skilled in the arl that numerous variations and/or modifications may be made to the invention as shown in the specific embodiments without departing from the spirit or scope of the invention as broadly described. The present embodiments are. therefore, to be considered in all respects as illustrative and not restrictive.