HK1121329A - Efficient location and tracking of mobile subscribers - Google Patents

Abstract

A method for locating and tracking devices in a mobile telephone network compries the steps of (a) receiving mobile telephone control parameters in a subscriber database; and (b) using one or more location parameter databases (LPDBs), each mapping control parameters to a geographic location and returning a location result when queried. One or more filters is applied to the control parameters that is received by the subscriber database, each filter selectively initiating processing using a LPDB appropriate to the task of the filter and to the current state of the device.

Description

Efficient location and tracking of mobile subscribers

Technical Field

The present invention relates to a method and apparatus for efficiently locating and tracking devices in a mobile telephone network and implicitly the subscribers carrying the devices when they appear in the network.

Background

In a mobile telephone system, a subscriber carries a handset. When a subscriber initiates or receives a call or text message or data session, radio communication occurs between the handset and a Base Transceiver Station (BTS), a familiar mast in modern landscapes. Not only is the encoding of the message passed between the caller and the call recipient transmitted, the handset and BTS also transmit a large amount of control information between themselves for the purpose of reliably and efficiently supporting communications, for example, the system must choose when to pass the call to another BTS as the subscriber moves around. Control information in a global system for mobile communications (GSM) system contains information about the signal strength of neighboring BTSs, timing advance information to indicate that handsets further from the BTS transmit earlier to match their time slots, transmission error rates, and many other information. Other technologies, such as Code Division Multiple Access (CDMA), use different information to achieve the same goal of reliable and efficient communication. We refer to these parameters collectively as mobile phone control parameters.

Mobile telephone system

A Location Parameter Database (LPDB) associates mobile phone control parameters with the geographical location of the handset. The LPDB may be constructed and maintained in one of several ways, and the LPDB may map one of several useful subsets of control parameters to a geographic location. We provide several examples of LPDBs with different accuracy, processing cost, and geographic coverage integrity.

Mobile subscriber location database

The mobile subscriber location database is the database by means of which the service location query is served. Which consists of a subscriber database and several positioning parameter databases. The location parameter database is controlled by a database manager.

Subscriber database

The subscriber database contains original records of mobile subscriber parameters derived from control information passed between the subscriber and the network. These records are maintained for all subscribers and provide the information needed to satisfy the query for the subscriber's location, if it should be made. The cost of maintaining a subscriber database is low because the records it maintains do not need to be processed in any way unless and until the location of the relevant subscriber is queried.

Location parameter database

A Location Parameter Database (LPDB) maps a subset of the control parameters to a table of geographic locations within a geographic area. The location database may contain one or more LPDBs. The choice of which LPDBs to maintain in the location database may depend at least on the geographical parameters of the area, the available computer processing power per location query, the network topology, and the available mobile phone network control information. The coordinate system used by the LPDB and the encoding of the appropriate mobile phone control parameters within the LPDB are LPDB specific. The LPDB translates the location into a table that, once output, is available for use by other parts of the system. One such table is a map polygon.

Precision and cost values are associated with each LPDB in the location database. These allow the location database to select how to implement each location query. Next we describe some examples of LPDBs.

Radio Frequency (RF) level LPDB

The control information for a GSM handset contains the signal strength observed at the handset for the serving BTS and up to 6 neighboring BTSs. The signal strength varies depending on the distance from the BTS, the topography of the area, the presence of buildings, and many other factors. In the RF level LPDB, the geographical area is subdivided into regular small squares, called "buckets". For each bucket, the RF level LPDB maintains a distribution of expected signal strength values received from visible BTSs. At the time of a location query, the bucket that best matches the last recorded signal strength profile for the subscriber's phone being location queried is selected as the bucket in which the subscriber is located.

Comparison LPDB

In mobile networks, it is now very common to co-locate 3 BTSs at a single location, each of which is oriented to serve a sector of the surrounding area of 120 degrees. The ratio of RF signal strengths from any pair of BTSs observed by the handset is then constant with distance from the BTS along a given radial direction and depends largely on the orientation of the phone relative to the BTS. Thus, if a pair of co-located BTSs at one site and another pair of co-located BTSs at a site that is physically separate from the first pair are both visible to a phone, the location of the phone can be accurately derived, such as by triangulation.

In this case, the LPDB consists of an encoding of a function of RF ratio for the bearings of all co-located BTS pairs. At the location query, a ratio is calculated for the last RF level observed by the handset. The position is found using the functions in the LPDB and 2 positions are triangulated to derive the location of the handset. Triangulation provides a very accurate location where 2 sets of co-located BTS pairs are visible to the mobile device. Without 2 sets of co-located BTS pairs, it is not possible to obtain any position readings. Thus, this LPDB sometimes needs to be supplemented by another more uniform database, but it is highly accurate in areas with good mobile phone coverage.

Cell, timing advance LPDB

In GSM mobile phone networks, the cell serving an active handset is always known. In addition, control information is passed to the phone to inform it of the Timing Advance (TA) slot to be used at the time of transmission. This allows the phone to compensate for the transmission delay between itself and the BTS, and is implicitly a coarse-grained coding of the distance between the BTS and the phone. The radius of a single TA slot is about 550 m. In the case of a BTS serving a 360 ° radius, this limits the location of the phone to somewhere in the ring-shaped area, the actual area of which varies with the TA value. In the increasingly common case where a BTS serves only a 120 sector, the location is limited to one third of the circle. An important factor of the (cell, TA) method is that the transition from (cell, TA) to location can be fast. In particular, there are few enough (cell, TA) pairs so that the resulting polygon for each can be stored in the lookup table.

Cell only LPDB

The more coarse grained LPDBs are LPDBs that return location based on only the serving cell. In practice techniques may be used that estimate the maximum range of a cell, which may be much smaller than the theoretical range of the cell. The radius of the resulting circle is reduced and is therefore fully useful for many positioning applications.

Disclosure of Invention

A first aspect is a method for locating and tracking devices in a mobile telephone network, comprising the steps of:

(a) receiving mobile phone control parameters in a subscriber database;

(b) using one or more Location Parameter Databases (LPDBs), each mapping control parameters to geographic locations and returning location results upon query;

wherein one or more filters are applied to the control parameters received by the subscriber database, each filter selectively initiating processing using an LPDB appropriate to the filter's task and to the device's current state.

For at least one positioning parameter database, a filter may determine whether the positioning parameter database is supplied with control parameters. The filter may also observe changes in the control parameters for a given subscriber or for members of a group of subscribers. By using a minimum cost location parameter database, these control parameters may relate to a particular geographic area of interest.

The filter may select the appropriate location parameter database that provides the lowest computational cost. A positioning mechanism may also be selected that has the least processing cost, but can be expected to return results with the necessary accuracy, for a particular request.

The filter may select an appropriate location parameter database depending on whether a trigger condition is met, which may be related to a subscriber entering the defined area. The trigger condition may relate to a subscriber leaving the defined area. If a trigger condition is met, the filter causes the supply of control parameters to an appropriate location parameter database and returns the geographic location of the associated subscriber. If the trigger condition is not met, the filter is recalculated after a period of time that is a function of the subscriber's estimated speed. Information from one position fix may be used to limit the possible locations for the next fix.

The filter may invoke a retrospective processing of the stored subscriber database content to discover where the subscriber entering the geographic area originated. The filter may invoke a retrospective processing of the stored subscriber database content to discover a history of subscriber activity.

Additional LPDBs with different cost tradeoffs may be added to provide more options to the system. When there is only partial coverage, the next higher accuracy LPDB is selected, or the most accurate lower accuracy LPDB available is selected. High accuracy tracking can be achieved using the initial (cell, timing advance) LPDB to identify candidate buckets in the RF LPDB.

An origin trigger may be triggered when a subscriber or member of a subscriber set leaves a defined geographic area, where the origin trigger is implemented using a filter. A destination trigger may be triggered when a subscriber or member of a group of subscribers enters a defined geographic area, where the destination trigger is implemented using a filter. The proximity trigger monitors whether two subscribers are in proximity to each other.

A subscriber group may be automatically defined as a subscriber that is in a particular area at a particular time. When some members of the group again appear close, or enter another area with similar characteristics to the first area, the appropriate trigger will be invoked. A contact tree is generated using the call records to discover a group of call recipients for a particular handset or a group of callers to a particular handset.

The method may be used to determine the presence of vehicles in congested areas, the presence of vehicles in toll systems or road use charging systems, the use of vehicles on roads for insurance pricing, to locate and track mobile subscribers for government, regulatory and law enforcement purposes, to track vehicles in fleets of vehicles.

A second aspect is an apparatus for locating and tracking a device in a mobile telephone network, comprising:

(a) a subscriber database that receives mobile phone control parameters;

(b) one or more positioning parameter databases, each mapping control parameters to geographic locations and returning positioning results upon query;

wherein one or more filters are applied to a flow of control parameters received by the subscriber database, each filter selectively initiating processing using an LPDB that is appropriate for the task of the filter and for the current state of the device.

Drawings

Fig. 1 is an example of a configuration of an apparatus that may be used in an embodiment of the present invention.

Fig. 2 is an example of a configuration of an apparatus that may be used in an embodiment of the present invention.

Fig. 3 is an example of location tracking.

Fig. 4 is an example of how improved accuracy may be obtained in position tracking.

Fig. 5 is an example of an origin triggered scenario.

Fig. 6 is an example of a case of destination triggering.

Fig. 7 is an example of a case of proximity of multiple subscribers.

Detailed Description

The present invention relates to a method and apparatus for efficiently locating and tracking devices in a mobile telephone network and implicitly the subscribers carrying the devices when they appear in the network. The mechanism for efficient global positioning is detailed in one embodiment. The concept of trace and trigger is introduced and a family of efficient trace and trigger mechanisms is described.

The system processes control parameters of the handsets of mobile phone subscribers when the handsets are observed on the monitored mobile phone network and stores the parameters in a subscriber database. Updated control parameters are continuously streamed to the subscriber database as they are observed on the network. Some control parameters implicitly encode the location of the handset, e.g., and most directly, the handset is almost always within a few kilometers of the serving cell base station.

One or more Location Parameter Databases (LPDBs) are constructed and maintained. Each LPDB contains a transition from a subset of the handset control parameters to a geographic location. For example, a serving cell LPDB may be present. When a location request is received or generated for a particular mobile device, parameters stored in the subscriber database are referenced and processed by the selected LPDB to generate a position fix to respond to the location request.

In addition to establishing LPDBs to passively react to any location request, active filters may also be attached to the flow of updated control parameters flowing into the subscriber database. These filters may be configured to perform a variety of location-oriented functions: for example, it may monitor activity in a particular geographic area, or observe activity of a particular subscriber (as identified by subscriber and equipment identifiers). Possible subscriber and equipment identity codes include an identity code for a Mobile Station Integrated Services Digital Network (MSISDN), an International Mobile Subscriber Identity (IMSI), and an International Mobile Equipment Identity (IMEI). The filter may also be configured to inform external clients of the activity it discovers, and it may trigger internal components to further process the information it passes, e.g., the filter may call some retrospective processing to discover where a subscriber entering a geographic area originated from.

FIG. 1 shows an embodiment of the present invention. The mobile telephone 10 transmits the control parameters 11 to the BTS 100. The control parameters are stored in the subscriber database 12. One or more location parameter databases 19 are constructed and maintained using data from subscriber database 12. Each LPDB 19 includes a transition from a subset of handset control parameters to a geographic location. Active filters 13, 15 and 17 may be attached to the stream of updated control parameters flowing into the subscriber database. These filters may be configured to perform a variety of location-oriented functions: for example, it may monitor activity in a particular geographic area, or observe activity of a particular subscriber (as identified by subscriber and equipment identifiers). LPDB 14 is constructed based on the parameter data passed by filter 13. LPDB 16 is constructed based on the parameter data passed by filter 15. LPDB 18 is constructed based on the parameter data passed by filter 17.

Figure 2 shows yet another embodiment of the present invention. Mobile phone 20 transmits control parameters 21 to BTS 200. The control parameters are stored in the subscriber database 22. One or more location parameter databases 23 are constructed and maintained using data from subscriber database 22. Each LPDB 23 includes a transition from a subset of handset control parameters to a geographic location. Active filters 24, 26 and 28 may be attached to the updated control parameter stream available from subscriber database 22. These filters may be configured to perform a variety of location-oriented functions: for example, it may monitor activity in a particular geographic area, or observe activity of a particular subscriber (as identified by subscriber and equipment identifiers). LPDB 25 is constructed based on the parameter data passed by filter 24. LPDB 27 is constructed based on the parameter data passed by filter 26. LPDB 29 is constructed based on the parameter data passed by filter 28.

Those skilled in the art will appreciate that it is possible to create further embodiments of the invention incorporating aspects of the embodiments of the invention shown in figures 1 and 2.

The method of storing the original parameters until they are needed by the LPDB is particularly efficient because it does not require processing information relating to a particular subscriber unless and until some form of location information for that subscriber is needed. Alternatively, unprocessed control parameters are maintained until they become outdated, and are only processed if location services are applied to the subscriber. This also has the advantage that no commitment needs to be made as to which subscribers are placed in location mode at any time. All subscribers are potentially locatable and this can be done if there is a sudden need to locate any individual subscriber.

Efficiency is also achieved by structuring the form of the location service so that low processing cost operations are generally sufficient to satisfy the form. Locating a handset through a serving cell with an accuracy of a few kilometers is orders of magnitude less costly than locating a handset through an RF level with an accuracy within a few hundred meters lower. Any positioning request, whether explicitly or implicitly represented, can be considered to have the required accuracy. The required accuracy may vary significantly. For a particular request, the positioning mechanism is selected that has the least processing cost but can be expected to return results with the necessary accuracy. In this way, many location requests ultimately have a low cost, and the system can support a much higher overall request rate than would otherwise be the case. Each LPDB maintained amortizes its own location mechanism, and new LPDBs with different cost tradeoffs can be added to provide more options to the system.

Actuator element

The ability to locate and track mobile subscribers in a mobile communication system is paramount to government, regulatory and law enforcement agencies, and is also a starting factor for a large number of business opportunities. The ability to immediately and automatically locate a caller of emergency services in an emergency situation can save lives. Taxi companies wish to track all of their taxis so that they can effectively allocate the nearest available taxi when a customer calls a taxi. Local businesses can promote promotions by text messaging details of special offers to everyone present in their locale. Police forces may enforce a statute that limits a person from remaining at or near home by triggering when the person's phone moves outside of the home address. A subscriber or group of subscribers may only be concerned when they enter or leave a particular area. In this case, a trigger may be issued to notify interested parties that the subscriber has arrived or departed.

The method of the present invention utilizes the available LPDBs in order to optimally optimize the location requests it receives. Although our example is specific to GSM parameters, the same principles apply clearly to parameters associated with other technologies, and an appropriate LPDB may be constructed for mobile phone systems using these technologies. In the mechanisms we describe for tracking and triggering, low resolution positioning such as those provided by the cell only LPDB may be sufficiently accurate at many stages of the tracking and triggering process.

Location query

For direct positioning queries, it is desirable to express precision within the query. The location database selects the lowest cost LPDB with sufficient accuracy and forwards the query to the LPDB. During normal events, the selected LPDB returns a location result. If this is not possible, for example if the LPDB has only partial coverage, the next higher accuracy LPDB is selected. If such an LPDB is not present, a lower precision LPDB may be queried in order to produce results that may at least have some use.

Position tracking

The flexibility of multiple complementary LPDBs is particularly clear where the system is required to monitor subscribers and/or areas for specific conditions. The tracking mechanism is the way the system supports monitoring the path followed by all members of a group of subscribers or any individual subscriber. Clearly, a user of a system wishing to track a particular subscriber may simply query the location of the subscriber repeatedly with the accuracy they require. However, this would be a waste of resources, especially if the subscriber is not actually moving.

Tracking notifications

When tracking a subscriber, the system reports the subscriber's location calculated with a user-specified accuracy each time the subscriber moves a certain user-specified distance from the last reported location. The tracking flip-flop achieves its efficiency using a filter. When a filter observes a new set of parameters for a subscriber, it needs to determine whether the subscriber is approaching a specified distance from its last reported location. In the usual case, this is achieved by a low cost low precision LPDB. If at this stage it is determined that the tracking notification condition is not met, no further processing is required in the filter.

Safety time

After determining that the tracking notification condition is not satisfied, the filter may be set to not perform further processing for a certain amount of time in the future. The system estimates an upper bound on how fast the subscriber can travel and uses this upper bound to calculate the minimum amount of time that it may take for the subscriber to move far enough to satisfy the notification condition. For example, if high speed power travel is possible, the upper bound may be 80 miles per hour; or it may be 40 miles per hour if only travel in urban areas is possible. Thus, the system does not need to make another location calculation for the subscriber before the time interval expires. Of course, the subscriber's parameters will still be recorded in the LPDB as they arrive (as they would for any user) in order to satisfy any future ad hoc location queries.

The next low accuracy LPDB query will only need to be implemented when new parameters arrive after a safe time interval has been exceeded. Higher accuracy LPDBs need only be used if the low accuracy LPDB cannot unambiguously determine whether the subscriber has satisfied the tracking notification condition. If it is determined that the conditions for further tracking of the notification have been met at this point, the location of the subscriber may be notified with the required accuracy.

We can see in fig. 3 how a tracking notification will be made at each of the 6 locations along a complex path when the subscriber has travelled along that path. The sequential positions are solid black circles indicated at 30, 31, 32, 33, 34 and 35. Unfilled circles are circles centered on a solid black circle, where the radius of the unfilled circle is given by the maximum velocity times the safe time. Points 30, 31, 32, 33, 34 and 35 are the only points along the path at which a full location request with the accuracy required by the client is requested. If the journey has taken the subscriber 30 minutes, polling for location at 30 second intervals would require 60 location requests instead of the 6 required using our tracking mechanism.

Accuracy improvement of tracking

The accuracy of position location during tracking can be improved at little cost because subsequent location requests are not truly independent; information from one position fix may limit the possible locations of the next position fix. This is illustrated in the following examples.

Consider the case where tracking is required to have high accuracy and in fact the high accuracy LPDB uses the initial (cell, timing advance) LPDB to identify candidate buckets in the RF LPDB. An example is given in fig. 4. At time t1, the (cell, TA) LPDB location, which we call (cell 1, TA1), locates the subscriber between the two circles given by the area 40. The subscriber is located within circle 42 by using RF and (cell, TA) location at time t 1. At time t2, the (cell, TA) LPDB location, which we call (cell 2, TA2), locates the subscriber between the two circles given by the area 41. The subscriber is located within circle 49 by using RF and (cell, TA) location at time t 2. FIG. 4 shows that the subscriber has moved from circle 42 at t1 to circle 49 at t 2. The tracking filter also observes that there has been a handoff of the subscriber from (cell 1, TA1) to (cell 2, TA2) at time t3 in area 45. By using the time difference t3 minus t1, and the subscriber's maximum sensible movement speed, we find that the subscriber must be located in the area 44 at t 1. Since we also know that the subscriber was within circle 42 at t1, the subscriber's position at t1 shrinks to the intersection of 42 and 44, which is small region 43. This result may be reported. Also, by using the time difference t2 minus t3, and the subscriber's maximum sensible movement speed, we find that the subscriber must have been located in the area 46 at t 2. Since we also know that the subscriber was within circle 49 at t2, the subscriber's position at t2 shrinks to the intersection of 46 and 49, which is small region 48. This result may be reported. Based on the subscriber having been in region 45 at time t3, region 47, defined by the four curved boundaries, is a likely region that the subscriber may have been in between t1 and t 2.

Positioning trigger

The location triggering mechanism shares many of the efficiency techniques used in location tracking. In particular, a secure time mechanism is used to limit the query rate inside the system, while ensuring that triggers will be triggered in a timely manner when appropriate conditions are met.

Origin/destination trigger

The origin and destination triggers are similar to each other. An origin trigger is a trigger that arises when a subscriber (or a member of a group of subscribers) leaves a defined geographic area. A destination trigger is a trigger that arises when a subscriber (or a member of a group of subscribers) enters a defined geographic area. Although in the most general case the destination trigger may be an origin trigger using the complement of the region, the difference is important because it is most often the case that one is concerned with entering or leaving, respectively, the region bounded by the low-level polygon, most often the region of interest is a region in the region of the point of interest.

The origin and destination triggers are implemented by filters. When the filter observes a new set of parameters for the subscriber in the relevant set, it needs to determine for the destination trigger whether the subscriber is approaching the zone boundary from outside and for the origin trigger whether the subscriber is approaching the zone boundary from inside.

Origin trigger

In the case of an origin trigger, the system defines a safe area in the coordinate space of a low cost, low precision LPDB. The security area may be as simple as a set of serving cells contained entirely in the origin area. The product of the size of the safe area and the cost of the location query in the LPDB provides the sum cost of using the particular LPDB for that area. We can select the lowest cost LPDB by this metric to provide the first filter for the cage flip-flop. The filter may complete the process if it receives the new parameters and immediately determines that the subscriber is in the safe area according to the low cost LPDB. As with the tracking notification, the location within the safe area is used to generate a safe time interval in addition to generating a location result. This safe time is attached to the filter, which avoids it conducting any further location queries during the time interval duration. If the filter cannot determine that the subscriber is in the safe area using the low cost LPDB, it may actually determine that the subscriber has left the trigger area and a trigger should be raised to notify the client. It is more likely, however, that the filter will need to use a more accurate and higher cost LPDB to perform further queries. When a sufficiently accurate LPDB is used, it will be determined that the subscriber has left the trigger area, or the subscriber will be given a new (but smaller) safety area and a new (but shorter) safety timer.

Fig. 5 shows a subscriber 50 within an origin trigger area 53. Rectangular area 52 is defined as a safe area. Circle 51 is centered on subscriber 50. The circle 51 has a radius such that the radius is the minimum distance from the subscriber 50 to the edge of the safe area 52. A safe time may then be defined, which is the radius of 51 divided by the maximum speed of subscriber 50. During the safe time, the subscriber is no longer required to be located.

Destination

Destination triggers are monitored in a manner similar to origin triggers. In the case of the destination, the unsafe area is defined using a low cost LPDB that contains the destination trigger area. A safe timer is defined based on the minimum time a subscriber can reach an unsafe area. When the security timer expires, the subscriber's location is first calculated with the lowest cost LPDB until a sufficiently accurate result is obtained to set a new unsafe area and security timer, or report that a destination area has been entered. Fig. 6 shows an example of a destination trigger where an unsafe area 62 and a safe timer for a subscriber 60 are being monitored. A destination trigger area 63 is defined and an unsafe area 62 is defined. Subscriber 60 is outside of unsecured area 62. The circle 61 is centered on the subscriber 60 and has a radius given by the shortest distance from the subscriber 60 to the unsafe area 62. The safe time is defined as this radius divided by the maximum speed.

Proximity trigger

The proximity trigger monitors whether two given subscribers are in proximity to each other. Proximity may be triggered for a discrete pair of subscribers or for any pair in a group of subscribers. The concept of safe time may be used again when tracking the proximity of a pair of discrete subscribers. When the pair is determined to be sufficiently separated with a low accuracy LPDB, a timer is set according to the maximum possible approach speed. The safe time may be defined as the distance between subscribers divided by the maximum closing speed of any subscriber multiplied by 1/2. The factor 1/2 arises because two subscribers may approach each other at a maximum approach speed with respect to the earth's surface. During the duration of this timer, no location query need be made for any subscriber (at least for the purpose of proximity to this pair). The process may repeat when the timer expires. A high accuracy LPDB must be used only when the subscribers are sufficiently close.

More complex variants are used in cases where any proximity to a subscriber from a group of subscribers may cause a triggering event. Rather than testing the proximity of each permutation of pairs, the system defines safe areas for each subscriber based on the subscriber's current location. The safe area extends the area around the subscriber as far as possible, consistent with the safe time to reach the area by any of the other members of the subscriber group. The secure region of each subscriber may then be processed in the same manner as the origin trigger for that subscriber for the period of secure time. The process of generating a secure area for each member of the subscriber group is itself subject to an efficient selection of LPDBs and is given as follows. Each subscriber is located with a low cost LPDB. The closest possible distance between each pair is calculated. This calculation is used to define the safe area for each subscriber. In the case of a subscriber having a sufficiently large safe area according to the low cost LPDB, no further consideration is required for the subscriber in establishing the safe area. The remaining subscribers are located using the higher accuracy LPDB in order to create a large enough safe area for each subscriber, or to inform the clients of the trigger whether the subscriber is within sufficient proximity. The safety timers of all subscribers are started. When a safety timer is completed, a new safety timer is recalculated for the subscriber based on how long it can be guaranteed that the subscriber will remain in its safe area. When a subscriber leaves its secure area, a new secure area is calculated for the subscriber based on the minimum distance to the current secure area of the other members of the subscriber group in question.

The mechanism can be modified to iteratively update the safe area of neighboring subscribers, where it is necessary to provide each subscriber with a sufficiently large safe area that does not require processing. What is achieved is that once the proximity trigger has been set, the only significant processing cost is spent on subscribers who are in close proximity to be in contact with other subscribers.

Fig. 7 shows a plurality of subscribers 70, 71, 72, 73 and 74 being monitored, having respective safe areas defined by circles 75, 76, 77, 78 and 79. Obviously, different subscribers are monitored with different security zones and therefore there are different security timers. The two subscribers closest together, subscribers 70 and 71, must be assigned the smallest safe area and therefore will require the highest amount of positioning processing to verify that they have sufficiently close proximity. Subscribers 72, 73 and 74 only need to be checked again after a much longer time delay because they are not currently close to any other subscription in the group.

Automatically defining subscriber groups

Tracking and various forms of triggering allow monitoring of subscriber groups. These groups may be defined manually, but they may also be defined as subscribers meeting specific historical location conditions. Given that a group contains everyone that might be of interest in the context of a system user, we can define the group as a subscriber who is in a particular area at a particular time. When some members of the group again appear close, or enter another area with similar characteristics to the first area, the appropriate trigger will be invoked. Without an automatic group, the client would have to explicitly record the subscribers that satisfy the original request and then feed them back into the subsequent request.

Historical analysis

Some location-based services require that historical information be maintained, as location requests may involve past times, and not until later times the subject (e.g., subscriber) is known. In this case, the system has no choice but to keep the historical information as long as it may be needed for analysis. For example, if a law enforcement agency identifies past criminal activity when evidence is present, it may be desirable under control to analyze the mobile phone history of someone who becomes a suspect in light of the evidence.

In general, any kind of tracking or trigger analysis may only be of interest in retrospect. But to accomplish this, the complete history of each subscriber must be maintained for as long as the time interval between the activity and the suspicion, which may be several years. Given sufficient data storage capacity, the problem can be solved by the described system. Processing of any saved data is not required until it becomes the subject of the historical analysis. The raw control parameters can simply be stored and the system can be run in the following manner: data is saved for the date in question and the saved data is replayed as new input data when a history interval draws attention.

Contact tree tracking

A specific example of a history analysis is the generation of a contact tree. The principle is to use call records to discover call recipients for a particular handset or a group of callers to a particular handset. We can identify a handset contact that is a caller to a handset, a call recipient of a handset, a Short Message Service (SMS) sender to the handset, or an SMS recipient of the handset.

When other forms of interaction via the handset are developed, these interactions may also be used to determine contacts as long as the contacts have the identification numbers transmitted in the network control information. It is then possible to identify the closing of the contact group. Assume, for example, that A calls B, B calls C, C calls D, X calls Y, and Y transmits a text message to A. Therefore if a draws attention, B, C, D, X and Y also draw attention. However, contact analysis may be hindered by processes that use multiple separate handsets (e.g., anonymous, prepaid (pay-as-you-go) handsets). However, if a calls B on the first handset of B and B calls C on the second handset of B, then it is likely that the two handsets of B are already in actual proximity immediately or shortly after a calls B, so the system incorporates facilities to generate a contact tree by proximity as well as direct call relationships. Assume, for example, that a calls B on a first handset of B and another handset in proximity to the first handset of B calls C. Assume that the other handset is the second handset of B. We thus get a contact group: A. a first handset of B, a second handset of B, and C.

This technique is most effective for the complete coverage of all mobile networks in the historical data; we can thus ensure that all contacts can be identified. But even if only some networks are covered, we can identify close contacts within the same network and augment these with calling contacts from billing records to establish a denser network of contacts for individual handsets than has been possible so far. For example, where several anonymous prepaid mobile phones are present on the same network, and the contact set for a handset of interest generated from billing information contains one of these handsets, close contacts within the monitored network may identify other prepaid handsets, which may then be analyzed for contacts, extending the contact set of the originating handset.

Relative proximity

In the case where both handsets are on the same mobile network, the system can very efficiently and accurately generate candidate handsets that are very close to the first handset. Although the actual position produced may have some degree of error, it will be observed that the handset has many control parameters that are approximately the same. We can configure the system with a set of parameters that behave in this way. The proximity may then be evaluated by comparing the original parameters without the need for expensive steps of translating them to location with a high precision LPDB.

In the case where the two handsets are on different mobile networks, some aspect of relative proximity may be used, as there are cases where different networks share the BTS site. However, in general, a set of possibly close handsets will be calculated using a low cost LPDB, and for those possibly close handsets in the set, a high precision location request will be made to determine an accurate proximity.

Various modifications and alterations of this invention will become apparent to those skilled in the art without departing from the scope of this invention, and it should be understood that this invention is not to be unduly limited to the illustrative embodiments set forth herein.

Claims (35)

1. A method for locating and tracking devices in a mobile telephone network, comprising the steps of:

(a) receiving mobile phone control parameters in a subscriber database;

(b) using one or more Location Parameter Databases (LPDBs), each mapping control parameters to geographic locations and returning location results when queried;

wherein one or more filters are applied to the control parameters received by the subscriber database, each filter selectively initiating processing using an LPDB appropriate to the filter's task and to the device's current state.

2. The method of claim 1, wherein for at least one positioning parameter database, a filter determines whether the positioning parameter database is supplied with control parameters.

3. The method of claim 1, wherein a filter observes changes in control parameters for a given subscriber or for members of a group of subscribers.

4. The method of claim 3, wherein the filter uses a least cost positioning parameter database to observe control parameters related to a particular geographic area of interest.

5. The method of claim 1, wherein the filter selects an appropriate location parameter database depending on whether a triggering condition is satisfied.

6. The method of claim 1, wherein the filter selects the location parameter database that provides the lowest computational cost.

7. The method of claim 1, wherein for a particular request, a positioning mechanism is selected that has the least processing cost but can be expected to return results with the requisite accuracy.

8. The method of claim 5, wherein a trigger condition relates to a subscriber entering a defined area.

9. The method of claim 5, wherein a trigger condition relates to a subscriber leaving a defined area.

10. The method of claim 5, wherein if a trigger condition is not met, the filter is recalculated after a period of time that is a function of the subscriber's estimated speed.

11. The method of claim 1, wherein information from one position fix is used to limit the possible positions of the next fix.

12. The method of claim 5, wherein if a trigger condition is met, the filter causes an appropriate positioning parameter database to be supplied with control parameters and returns a geographic location of the associated subscriber.

13. The method of claim 1, wherein a filter invokes retrospective processing of stored subscriber database content to discover where subscribers entering a geographic area originated.

14. The method of claim 1, wherein a filter invokes retrospective processing of stored subscriber database content to discover an activity history of a subscriber.

15. The method of claim 1, wherein additional LPDBs with different cost tradeoffs can be added to provide more options for the system.

16. The method of claim 1, wherein the subscriber database maintains a control parameter record for all subscribers on a network.

17. The method of claim 1, wherein a location parameter database uses RF hierarchy.

18. The method of claim 1, wherein a location parameter database uses pairing ratios.

19. The method of claim 1, wherein a positioning parameter database uses cell timing advance.

20. The method of claim 1, wherein a location parameter database uses cell identities.

21. The method of claim 1, wherein a location parameter database uses GPS trajectory data fed back from a GPS device used by the subscriber.

22. The method of any preceding claim, wherein when there is only partial coverage, the next higher accuracy LPDB is selected, or the most accurate lower accuracy LPDB available is selected.

23. The method of claim 1, wherein an initial (cell, timing advance) LPDB is used to identify candidate buckets in an RF LPDB for high accuracy tracking.

24. The method of claim 1, wherein an origin trigger is triggered when a subscriber or member of a subscriber group leaves a defined geographic area, wherein the origin trigger is implemented using a filter.

25. The method of claim 1, wherein a destination trigger is triggered when a subscriber or member of a subscriber group enters a defined geographic area, wherein the destination trigger is implemented using a filter.

26. The method of claim 1, wherein a proximity trigger monitors whether two subscribers are close to each other.

27. The method of claim 1, wherein a subscriber group is automatically defined as a subscriber that is in a particular area at a particular time.

28. The method of claim 27, wherein when some members of the group again appear close, or enter another area with similar characteristics to the first area, an appropriate trigger will be invoked.

29. The method of claim 1, wherein a contact tree is generated using call records to discover a group of call recipients for a particular handset or a group of callers to a particular handset.

30. The method of claim 1, wherein the method is used to determine the presence of a vehicle in a congested area.

31. The method of claim 1, wherein the method is used to determine the presence of a vehicle in a road toll system or a road usage charging system.

32. The method of claim 1, wherein the method is used to determine usage of vehicles on a road for insurance pricing.

33. The method of claim 1, wherein the method is used to locate and track mobile subscribers for government, regulatory, and law enforcement purposes.

34. The method of claim 1, wherein the method is used to track vehicles in a fleet of vehicles.

35. An apparatus for locating and tracking a device in a mobile telephone network, comprising:

(a) a subscriber database that receives mobile phone control parameters;

(b) one or more positioning parameter databases, each mapping control parameters to geographic locations and returning positioning results upon query;

wherein one or more filters are applied to a flow of control parameters received by the subscriber database, each filter selectively initiating processing using an LPDB that is appropriate for the task of the filter and for the current state of the device.