The present invention relates to an apparatus and method for improving the resolution with which the geographical location of a moving cellular telephone system mobile station may be determined.

Many proposals have been made for locating equipment such as vehicles by

reference to broadcast telecommunications signals. For example, low resolution

navigation systems are known which rely on a network of dedicated low frequency

transmitters, the mobile station measuring the phase difference between the signals

received from different transmitters. By comparing the signals from the different

transmitters the mobile station position can be established to within say 50 or 100

metres. More accurate satellite-based systems are now available which can give very

accurate position information, typically down to 10 metres or less, but such systems

rely upon the mobile station having a line of sight path to three satellites and this is

not easy to achieve in urban environments. Furthermore, satellite-based global positioning systems require substantial expenditure on equipment even if governments

continue to make the basic satellite broadcasting system available free of charge.

Thus the known global positioning systems require substantial infra-structure

investment and. if they are to provide high accuracy, substantial expenditure on dedicated equipment at the mobile stations.

Other proposals have been made for determining the location of vehicles, for

example that referred to as the "Cursor" system which relies upon detecting signals

broadcast by local public radio transmitters operating on the medium wave band to

calculate the position of a mobile station. High accuracy is claimed (typically 5 metres) and the infra-structure in the form of freely broadcasting transmission stations

is already present. The Cursor system does nevertheless require relatively expensive

dedicated equipment to be provided in each mobile station.

Cellular telephone systems have grown explosively in recent years. Digital

systems are now being introduced, and in Europe some such systems operate in

accordance with the GSM standard. There are alternative standards which system

operators use, for example PCM. and the present invention is applicable to all the

known standards. For the purposes of explanation however the invention will be

described with reference to only the GSM standard. In cellular telephone networks,

individual subscribers carry mobile stations which receive signals from and transmit

signals to a series of base stations. The territory covered by the system is broken

down into a series of cells each of which is served by a series of base stations. As the

mobile station moves from one cell to another, communication signals are handed

over from one base station to another on the basis of the strength of the signals

transmitted by the base stations at the current location of the mobile station. It is

fundamental to the operation of a cellular telephone network that the system knows

the whereabouts of the mobile station, and this is achieved by causing the mobile

stations to transmit signals to the base stations periodically, for example when the

mobile stations are switched on, or when the mobile stations transfer from one cell to

another, or on a simple periodic time basis.

It is known with a GSM system to be possible not only to locate which cell a

particular mobile station is within, but also to identify a sub-area of the cell within

which the mobile station is located. This is relatively easily achieved by reference to

the relative strengths of the signals received by the mobile station from each of the

base stations within its area. Unfortunately, given the structure of the GSM system

the location of a mobile station can only be determined to within about 200 metres.

Thus a system operator can identify the fact that a mobile station is within an area

which is roughly circular and has a diameter of about 200 metres, but cannot improve

the accuracy of the available positional information. In some circumstance

knowledge of the position of a mobile station of such low resolution is useful, for

example to an operator trying to control a fleet of vehicles which is widely spread over a region, but in many other circumstances such accuracy is of little use. In

particular, the precise location of for example a stolen vehicle in which a mobile

telephone is being used cannot be determined.

A security system has been proposed for locating stolen vehicles. In that system, protected vehicles are provided with a transmitter which is activated from a

central location in the event of the carrying vehicle being stolen. That transmitter

generates a signal specific to the vehicle which enables the police to locate the precise

position of the vehicle. The system is however relatively cumbersome in operation,

requiring substantial infra-structure and operational support from the police, and

therefore although it is useful for recovering valuable vehicles it has not been used

widely because of cost considerations.

By the very nature of cellular telephone systems, mobile stations of such

systems are often moving. If the movements of such a mobile station were random,

low resolution knowledge of the movement of the mobile station would not add

significantly to the accuracy of the available positional information. In fact however

movements of a mobile station are not random as almost invariably they follow

relatively well-defined routes, for example roads or railway lines, and those routes are

normally selected on a rational basis so as to minimise the distance between the start

and finish points of a particular journey. It is an object of the present invention to

make use of the characteristics of the motion of a mobile station of a cellular

telephone system so as to improve the resolution with which the geographical location

of such a mobile station may be determined.

According to the present invention, there is provided a method for improving

the resolution with which the geographical location of a moving cellular telephone

system mobile station may be determined, wherein signals broadcast by cell base

stations are monitored periodically by the mobile station to generate mobile station

position data, the position data representing a series of geographical areas in a region

through which the mobile station moves as the signals are monitored, the position data

is compared with map data representing transport routes within the region to generate

a series of subsets of routes, each subset corresponding to routes within a respective

said area, and the subsets are compared to identify the route along which the mobile

station is moving by reference to the differences between the routes identified by

successive subsets in the series.

The present invention relies on the assumption that a moving mobile station

will be travelling along one of a series of predetermined routes, generally those routes being represented by the road network. Given that the GSM cellular system enables

location of a mobile station to within 200 metres, in regions were there are few roads

it may be that this relatively low resolution positional information will be sufficient to

make it clear that the mobile station is moving along a single road. In regions of high

road density where they may be say fifty routes within a 200 metre diameter area,

most of those routes will be very small and hence, travelling speeds will be low. Thus

knowledge of a vehicles speed enables an accurate prediction of which routes the

vehicle may be on. Journeys generally include portions in which speeds are significant in the context of knowing the whereabouts of a mobile station within 200

metres. Furthermore, journeys are generally such that the mobile station moves in a

logical manner between two points and therefore, once it is known that a mobile

station is moving along a particular road, it is generally possible to accurately predict

subsequent movements of the mobile station, and if appropriate to intercept the

vehicle carrying the mobile station.

Various techniques can be used for assessing the relative probabilities of the

mobile station moving along individual routes represented by the subsets. For

example, the speed at which the mobile station is travelling may be calculated from

the position data, and that calculated speed may be compared with a predicted speed

for each of the routes in the subsets. The predicted speeds for individual routes may

be updated on the basis of information gathered from sources of information about the

flow of traffic such that for example if a particular route was blocked as the result of a

traffic incident that information would be available to improve the accuracy of the

assessment of which route the mobile station might be travelling along.

An alternative or additional approach would rely upon real time predictions of

a probable next location of the mobile station on the basis of the generated position

data. When the signals are next monitored the actual position can then be compared

with the prediction to assess the relative probabilities of a mobile station moving

along the routes represented by the subsets.

Another approach which may be adopted would be to calculate estimates of

the time it will take for the mobile station to travel from each route in the subset to

adjacent routes, the prediction being compared with the time that elapses before that

other route is identified in a subsequent subset.

In a further approach, position data from a number of mobile stations may be

correlated to identify groups of mobile stations which are moving at substantially the

same speed in the same area. That information would make it possible to compare the

correlated data with the capacities of routes identified by the subsets so as to increase

the accuracy with which the position of the mobile stations may be assessed.

The present invention also provides an apparatus for improving the resolution

with which the geographical location of a moving cellular telephone system mobile

station may be determined, wherein the mobile station comprises means for

periodically monitoring signals broadcast by cell base stations, and the system

comprises means for generating mobile station position data from the monitored

signals, the position data representing a series of geographical areas in a region

through which the mobile station moves as the signals are monitored, means for

storing map data representing transport routes within the region, means for comparing

the position data with the map data to generate a series of subsets of routes each of

which corresponds to routes within a respective said area, and means for comparing

the subsets to identify the route along which the mobile station is moving by reference

to the differences between the routes identified by successive subsets of a series.

Embodiments of the present invention will now be described, by way of

example, with reference to the accompanying drawing which schematically illustrates

the manner in which the method according to the present invention may be put into

effect.

Referring to the accompanying drawing, the straight lines represent vectors

based on for example the available OSCAR data, each vector corresponding to a short

section of a road network. The circles represented in broken lines represent areas

within the region of the represented road network within which a mobile station being

tracked is located at any particular time. Each of the circles represents an area having

a diameter of approximately 200 metres. The region within which the represented

road network is located is overlaid by a series of cells of a cellular telephone system and within that region there will be an array of base stations that transmit signals to

any mobile stations within range. In accordance with the known GSM mobile station

location system, the mobile station monitors the strength of the signals received from

the in-range base stations and transmits to the system data which enables the position

of the mobile station to be determined with a reduction represented by the circles.

If we assume that the mobile station is caused to report its position every thirty

seconds, it might be that the mobile station reports its position at these thirty second

intervals such that the mobile station is successively in the areas represented by circles

1, 2, 3 and 4. It is clear in this example that the mobile station is travelling at a

reasonable speed along a relatively straight highway. If it was desired to intercept a

vehicle carrying the mobile station it would be a relatively simple matter to follow the

vehicle on the basis of the information represented by the circles 1 to 4. The series of

circles 1, 5, 6 and 7 represent an alternative route through the road network in which

the vehicle carrying the . mobile station has turned left on to a side road but then

accelerates, the speed of the vehicle being represented by the space between the

centres of adjacent circles. Once again it would be a simple matter to track such a

vehicle.

As a third example, the circles 1 and 8 to 13 represent an alternative route in

which the vehicle carrying the mobile station first turns right, then turns left, and then

terminates its journey somewhere within the area represented by circle 13. It is not

possible to precisely pin-point the location of the vehicle when its journey is

terminated but it is for example clear that the vehicle is located on one of the routes

represented by vectors 14, 15 and 16 and cannot be on the route represented by vector

17. It would therefore be possible to identify the vehicle carrying the mobile station

when it has next moved and to intercept the vehicle on the only road from which the vehicle can reach the general road networks.

Taking the case of the journey represented by circles 1, 5, 6 and 7, the manner

in which the invention operates will be described in further detail. When the mobile

station reports its position as represented by the circle 1 , a list representing a subset of

the vectors describing the road network is generated, that list identifying vectors 18 to

21. When the mobile station is in the area represented by circle 5. a new list of

possible road vectors would be produced identifying vectors 20. 21 and 22. When the

vehicle is in the position represented by area 6, the related list of possible vectors

would be limited to vectors 22, 23 and 24. When the mobile station is in the region represented by area 7, the possible vector list would be limited to vectors 23 and 25.

Thus by comparison of the lists of vectors corresponding to areas 1 and 5, it would be

apparent that the vehicle had turned left given that vector 22 was present in the list

corresponding to area 5. It could also be apparent that the vehicle had not

subsequently turned right on to the road represented by vector 24 given that vector 25

is in the list corresponding to area 7. Thus, assuming the provision of a database

describing all the roads within a region of interest, it is a relatively simple matter to

rapidly scan that database to determine which route the mobile station is travelling

along. Accordingly the present invention proposes the combination of the relatively

low resolution location information available from the GSM system with readily

available map information using iterative analysis of a series of location fixes.

It will be appreciated that when a mobile station stays in the same location it is

difficult to determine exactly which route that mobile station is on. A slow moving

mobile station is also difficult to pin-point. The frequency with which location fixes

are made may however be adjusted to match the particular circumstances by reference

to the speed of travel of the mobile station. For example, a mobile station may be set

up to automatically report its position every say thirty seconds. Alternatively the

mobile station could report its position only when prompted to do so by a signal

transmitted to it over the cellular network. In the latter case it would be a simple

matter for the signals transmitted over the cellular network to be transmitted at a frequency tailored to the severity of the problem of trying to pin-point the mobile

station position. The analysis of the position information can rely on any convenient

techniques. For example the average speed at which the mobile station is travelling

can be calculated from the spacing between successive positions. This information

can be used to determine which routes the mobile station is most probably on. For

example, if the calculated speed is close to the know average speed on a particular

road, or is close to the speed limit on that road, we can be reasonably confident that

the mobile station is moving down that road rather than a road which has a much

lower average speed or speed limit. This approach would enable for example

confusion between a minor road which follows a motorway and the motorway itself to

be eliminated.

Given the provision of a list of roads that the mobile station must be one, the

mobile station speed and direction make it possible to predict in advance where one

would expect the next location fix to be, given that the mobile station is on a

particular road. The next location fix would then closely match the prediction for

some possible roads, produce a less likely match for other roads, or not match the

prediction at all. Using these predictions it is possible to inform the mobile station to

increase or decrease the rate at which it sends in location details. This enables the

system to tune the frequency with which the mobile station reports its position to the

local density of the road network.

A further approach to improving the resolution of the system would be to

calculate for each road section in a list corresponding to one location area the likely

time it would take to get from that road section to another road section not in the list.

By comparing this calculation with the actual time the mobile station takes to get to a

position in which its next location report includes in its area the predicted destination

road section it would be possible to see which prediction matches the outcome most

closely, and which is unlikely (for example having to travel at very high speed to get

from one road section to the other).

A further method of improving resolution would be to look at a whole series

of location fixes from numerous mobile stations centred in a given location. In this

situation where there is a flow of traffic, it can be assumed that mobile stations in the

same traffic flow will be moving at similar speeds. Combining the probable road

section that each mobile station could be on would, in most cases, narrow down the

possible road sections to just one road section.

Data from external traffic monitoring systems (such as TrafficMaster,

Road Watch etc) could be used to determine traffic conditions on certain roads. If the

speed and direction characteristics for a particular mobile station closely matched this

data then one could be relatively sure that the mobile station is on the given road.

The above techniques could be supplemented by alternative techniques to

improve the match between location information and road network information. The

system could also rely upon map information related to more than the simple road

network, for example the rail system. Furthermore the mechanism of retrieving

location information from the mobile station can be defined in various ways. As

previously mentioned the mobile station can either broadcast its whereabouts at pre¬

defined intervals, or it can be polled by the service provider, or a combination of the

two methods may be used where the broadcast interval can be dynamically altered to

provide an adaptive system. This is particularly useful in built-up areas or where the

mobile station is perceived to have excessive velocity to warrant a higher broadcast

rate. By having control of the location updating procedure, the additional bandwidth

requirement can be minimised.

It would be possible for the mobile station to incorporate circuits capable of

calculating its own position from the signal strengths of the adjacent base stations but

generally the system will operate such that the mobile station transmits to the service

provider the identity of the six strongest signal strengths in its location. The service

provider would calculate the location from the received information.

The improved resolution achieved in accordance with the present invention is

clearly of value in all of the many circumstances in which it has been proposed to

obtain value from being aware of the location of a mobile station. The present

invention does however offer further opportunity given the fact that the invention

relies upon the widely available GSM technology. It would be possible for example

to provide a subsystem of a standard cellular telephone mobile station which did no

more than report to the system provider its location in appropriate circumstances.

Such a subsystem could be fitted in for example pieces of equipment which are liable

to be stolen, such as personal computers. The personal computer could be arranged to in effect broadcast its location as soon as it was disconnected from the mains supply.

This would mean not only that the personal computer would generate a warning signal

indicating that it was being tampered with, but in addition it would enable the police

to track its movement after it has been tampered with. Given that the necessary mobile station equipment can now be manufactured at a relatively trivial cost the

application of the present invention in this context has very significant implications in

the field of locating stolen property, particularly as the necessary equipment is very

small and therefore easy to conceal. The present invention therefore has the ability to

provide a function exactly equivalent to that used by the dedicated vehicle tracking

systems now on offer but at a far lower cost.

Although the mobile station location may be determined by reference to the

signal strengths received from a series of base stations, this location information can

be enhanced by reference to timing advance data. When a mobile station is

communicating with a base station, existing systems apply a timing advance to

maintain synchronisation. This makes it possible to determine with accuracy the

distance of the mobile station from the one base station with which it is

communicating. This information can be used in conjunction with the signal strength

and map data to improve resolution. Of course timing advance data is not available

when a mobile station is not communicating with any base station.

It should also be noted that the disposition of base stations makes it possible to

provide good resolution adjacent to many major transport routes. Generally, base

stations are located close to major routes such as motorways. The location of a

mobile station moving along a motorway can therefore often be very accurately determined from the signal strengths of the two base stations between which it is

located.

The resolution with which mobile station location can be achieved may also be

improved by reference to the process of "handover", that is when the primary cell with

which a mobile station communicates changes due to movement of the mobile station

between the cells. Given that the system operator can detect when handover occurs

and that that will indicate to the system operator that the mobile station is crossing a

reasonably well defined line defined between the two cells involved in the handover,

this information can be added to the other position information to improve accuracy.