WO2010003898A1 - Environment-driven adaptive geolocation system - Google Patents

Abstract

The invention relates to a system capable of managing two processes in parallel and permanently: the periodical GPS reading by the mobile apparatus in order to determine the precise geographical location thereof; the identification by the mobile apparatus of the identifier (ID) of the antenna to which the mobile apparatus is connected (GSM, UMTS, Wimax, Wifi and a combination thereof). The system stores each new ID, and then associates thereto the duration during which the mobile apparatus remained connected when the mobile apparatus is later linked to a new antenna. The data is sorted periodically (e.g. every 24 hours) in order to identify and store in a memory the geographical areas in which the user spends a significant amount of time. The identification of the ID enables the system to know if the same is located in a known and previously stored geographical area. The rate of GPS reading is then increased and focused on the average duration between the entry into a geographical area and the loss of the GPS signal. The system is thus capable of precisely locating the mobile apparatus at the entrance of a building. The system identifies and also stores in a memory, for each geographical area, the average GPS location before the loss of the GPS signal. In a case of need, this estimated position can be used for locating the mobile apparatus.

Description

 ADAPTIVE GEOLOCATION SYSTEM PILOTED BY THE ENVIRONMENT

Description

Technical area

This invention relates to geolocation technologies, to precisely define the geographical position (latitude, longitude) of a mobile device (mobile phone, PDA, ...).

State of the art

While the use of GPS is spreading in many applications, the problem of geolocation by GPS when the user is inside a building remains unresolved. This limit has a significant impact on the performance of the applications, as a user is in fact spending the majority of his time in places that do not allow proper GPS reception (open air).

Several technologies not relying on the GPS attempt to provide an answer:

Geolocation by the network of the mobile operator

The mobile device of the user using the GSM technology is by default connected to an antenna of the network of the mobile operator. By considering the geographical area covered by this antenna, the unique identifier of this antenna and the intensity of the signal, it is possible to geolocate the user, even inside a building. This technology works certainly inside buildings, but it has the disadvantage of being imprecise, compared to GPS. The defined geographical area has a precision of 300 meters (urban area) to several km (rural area). Moreover, the same geographical point can be covered by several zones, which makes the antenna-geographical location association even more delicate.

This technology has been improved by considering several antennas so as to establish a triangulation (E-OTD, TOA, TDOA in particular). This approach requires a significant investment to equip the network, which no major operator has done and plans to do.

Geolocation by signals (Wi-Fi, GSM) of the environment

The mobile device of the user receives at a given geographical point the signals of the Wi-Fi terminals in the vicinity. Any terminal is defined by a unique MAC address and the signal strength varies depending on the geographical point.

It is thus possible, for any given geographical point, to define a unique signature of the MAC addresses and signal strength, and to link it to the GPS coordinates of the point, obtained by other methods.

Thus, when the user wants to know his position, his mobile device identifies the signature of the place to transmit it to a system which, by comparison with a base of GPS coordinates-coordinates, thus precisely geolocates the device.

This technology also works inside buildings, but it requires a location of all possible locations, to identify for each geographical point the associated signature. Note that the terminals change over time (change of physical position, MAC address if the terminal is changed), which requires driving the operation regularly.

A similar approach has been developed from the signature of the 7 antennas of the operator located in the environment of the user.

Geolocation by GPS (tracking)

The only possible alternative, using GPS technology, is to record at regular intervals the position of the mobile device (tracking). We thus obtain the last very precise position, ideally 'in front of the door of the building'.

This technique is nevertheless impossible to implement because of the power consumption of the GPS, when the mobile device combines telephony and GPS. A period of GPS reading of a few minutes (every 5 minutes for example) limits the duration of the battery to a few hours.

disadvantages

At present, the technologies that can allow indoor location are either too imprecise to be used, too cumbersome to implement or too restrictive for the user.

In the case of a call to emergency services, for example, current technologies do not allow to indicate precisely where the user is. Brief summary of the invention

The object of the invention is to provide a solution to accurately geolocate the mobile device at the entrance of the building in which it is located, without any prior identification, without any manipulation of the user, while optimizing the use of GPS (energy consumption).

According to the invention, these objects are achieved in particular by means of the object of the appended claims. In particular the invention provides the last position at the entrance of the building, sufficient to unambiguously identify the building in which the mobile device is located. In the case of a call to the emergency services, this information is sufficient to guide the relief.

This solution has the advantage over the prior art to allow the geolocation of any mobile device located in a building without prior operation and without consequences on the use of the device, including its autonomy on battery .

Brief description of the figures

Examples of implementation of the invention are indicated in the description illustrated by the appended figures in which:

Figures 1a and 1b schematically illustrate the main methods of the invention.

Figure 1c illustrates an overview of the system infrastructure of the invention.

Figures 2 to 9 illustrate more specifically the methods of the invention relating to the algorithms of: GPS control (Figures 2 and 3); GPS reading (Fig. 4); cell mapping (Figs 5 and 6); fusion algorithm (Fig. 7); updated places (Fig. 8 and 9).

Example of embodiment of the invention

A mobile device equipped with a GPS and a transmission means, being connected to an antenna, can be considered in a geographical area (Cell). Preferably when the mobile device is in this cell, it automatically connects to this antenna, the transmitted signal being the strongest (compared to neighboring cells). According to the invention, the mobile device can connect to a cell of a mobile radiotelephone network, for example a 2G, 3G or higher network, such as GSM, GPRS, EDGE, UMTS, CDMA2000 or other, or to a network Wi-Fi (IEEE 802.11), WiMAX (IEEE 802.16) or any other wireless network.

The exemplary embodiment presented refers to the NAVSTAR GPS navigation system (Global Positioning System) by brevity. The invention is however not limited to this system and can be applied to any GNSS navigation system (Global Navigation Satellite System), for example the Galileo system, GLONASS, Beidou, COMPASS and so on.

With reference to Figure 1 c, the 131 a 131 b, 131 b corresponding to a cell can be likened to a circle of a few tens of meters to several kilometers radius. Since the intensity of the signal can fluctuate, at a geographical point, the mobile device can oscillate between several antennas 132a, 132b, 132c.

According to one aspect of the present invention, the mobile device 120 can identify the antenna 132a, 132b, 132c to which it is connected by a unique identifier designating it (CeII-ID). This identifier can be for example the CeII-ID of the GSM network, or the MAC address for a Wi-Fi terminal. The system of the invention identifies the geographical areas, also designated as "places" 180 in the following, usual of the user and stores it, each place is defined by several parameters, for example:

o The CeII-IDs that define it.

o The number of visits since its creation.

o The total time spent in the place, updated, preferably, the accumulation of total time spent in a place has a weighting coefficient, so that places that are not usual are 'forgotten' after a certain time.

o The average time before the loss of the GPS signal (tps) in order to control the GPS playback frequency in function.

o The efficiency of the GPS reading in the place, which allows in the case of a low efficiency (few successful GPS readings) to introduce a _PS t.

o GPS 'average' position with loss of GPS signal (Pos _PS )

As illustrated schematically in Figures 1a and 1b, the system of the invention comprises a GPS control method 102 and a GPS reading method 103, carried out permanently, according to the terms that will be seen in the following .

The system of the invention also comprises a method for organizing and updating the locations illustrated schematically in FIG. 1b. This method is preferably activated with a predetermined frequency, for example every 24 hours. It comprises a step of mapping cells 1 12, one or more melting steps 1 13 and one or more updating steps places 1 16. The development of these Steps will be explained later, with reference to the corresponding figures.

With reference to FIG. 1c, the system of the invention may comprise one or more autonomous mobile devices 120, for example cellular telephones with a satellite geolocation interface, for locating on the basis of radio signals received by GNSS locating satellites 130. Each of the devices 120 is arranged to independently execute the method of the invention, or the mobile devices are connected to a central server (not shown), for example an alarm center or a control center. logistics, and wherein part of the methods of the invention is executed in the server.

According to one aspect of the invention, the mobile device learns and dynamically stores the places 180 that the user usually frequents, based on the identifiers of the cells 131a, 131b, 131c of the sound network. environment. As will be seen later, this learning involves the creation and the continuous updating of a list of the visited cells, as well as periodic stages of mapping of the cells, making it possible to identify and memorize the places visited usually and, for each location, the average position of GPS signal loss.

Preferably, the system also provides mechanisms to erase places that have not been visited for some time. This limits the memory occupancy of the list of stored locations while increasing the statistical reliability of the system, because the memory resources of the mobile device are used to store the locations with a higher probability of being visited. Examples of such mechanisms to "forget" places will be presented later.

The steering of the GPS will now be described in relation to Figures 2 and 3. The mobile device periodically identifies, for example with a rate of 10 s the CeII-ID in which it is connected (step 203), in steps 205 and 206 the system decides whether the device has just changed cells, and whether it has been in the same cell for more than 30 minutes, or another specified time interval. In this case, the GPS playback frequency is switched to 'sleep' mode (T _G ps-2, step 208), for example once an hour.

When the mobile device leaves a cell, the data is updated (step 210). The t _œ ιι variable is used to determine the time spent in a cell. The cells are stored in an array, cell (k), or other appropriate data structure, sequentially, each with the time spent in that cell, and the array cell (k) will be analyzed later for identify new places and update existing ones.

The system of the invention also decides (steps 215 and 216) if, when changing cell, the mobile device also leaves a known place. In this case, the GPS playback frequency is reset to normal cycle (steps 217 and 218).

Preferably when the mobile device is in a place, and if it has a low GPS reading efficiency, the GPS playback frequency is increased around the _PS t to determine more closely the last GPS position valid. However, it is not excluded that the mobile device enters and leaves the place before t _PS . In this case, the frequency must be restored in normal mode.

In step 220 the location data are updated. Preferably, the variable measuring the effectiveness of GPS reading is weighted taking into account the previous results, so as not to influence this average by an extreme result (mobile device left outdoors or on the contrary in a place without GPS reception).

With reference to FIG. 3, the system identifies whether, when changing cells, the mobile device enters a place or changes location (steps 302 and 303). The variable t _Lιeu is used to determine the time spent in a cell and / or a given place. The variables making it possible to evaluate the effectiveness of the GPS reading are also initialized (step 305). CountGPS, to count the number of GPS readings, CountNoGPS, to count the number of invalid reads, CountGPSok, to count the number of valid readings

[0036] If the place has a _PS t (step 308), the reading frequency of the GPS is modified (step 309), for example: if the _PS t is less than 3 minutes, reading every 20 seconds during the 4 first minutes after entering the place, then normal period of 15 minutes; if the _PS t is greater than 3 minutes, reading every 30 seconds, three minutes before and three minutes after t _PS , otherwise normal period of 15 minutes.

If the mobile device has been for more than 30 minutes in the same place (step 310), the GPS playback frequency has changed to 'sleep' mode (step 312, T _GP s-2), for example a times per hour.

The GPS reading method will now be described in relation to FIG. 4.

The reading of the GPS is controlled by the GPS control methods mentioned in Figures 1a and 2 with a frequency T _GP s- When the mobile device is in a place (step 403), the GPS efficiency is systematically determined. The system distinguishes between valid and non-valid GPS readings (step 405), a valid GPS reading being defined as a reading whose accuracy is less than a predetermined threshold, for example 60 m. The efficiency corresponds to the ratio between the number of valid readings (variable GPSOK count, step 406) / total number of readings (variable GPS count, step 404). Preferably, the GPS reading algorithm of the invention selects the GPS readings with a precision greater than that required in step 405, for example greater than 30 meters (step 418).

The variables used in the calculation of the efficiency are also used for the management of the _PS T.

Only three events can stop the GPS playback frequency in T _PS :

o Case 1: The mobile device came out of the place quickly (see GPS control, figure 2, steps 205, 210);

o Case 2: The mobile device has been in the scene for more than a few times and there have been more than three invalid GPS readings (step 408). The mobile device is probably already in the building at this time;

o Case 3: the GPS readings are valid and the t _PS is largely exceeded. ie 2 or 3 minutes after t _PS (step 410). The _PS t is probably too small;

Meanwhile, the system keeps in memory the last three valid GPS positions (step 415). An 'average' GPS position, Pos _PS (i), is determined for each location with a t _PS , closest to the last GPS position read before the loss of the GPS signal (step 420). The average position before the loss of the GPS signal is used as a position indication when the mobile device can not receive the GPS signal, for example inside a building.

In cases 2 and 3, at the end of this process, the variables t _PS (i) and Pos _PS (i) are updated for the place (i) (step 420). The GPS playback frequency is restored to normal mode. The cell mapping method of the invention will now be described with reference to FIGS. 5 and 6.

According to one aspect of the invention, the places or geographical areas that are usual and significant for the user are identified in that the time spent in a predetermined number of consecutive or adjacent cells exceeds a predefined threshold, for example a location. is identified when the time spent in three consecutive cells is greater than 10 minutes (step 505).

The method of mapping the cells is performed on the cells recorded periodically, for example once every 24 hours, (step 1 12 of Figure 1). The cells are sequentially taken in groups, for example groups of three cells in sequence, to compare the duration of permanence to the desired threshold, for example 10 minutes (step 505).

If the criterion is met, a zone, or place is then formed (step 508).

The system evaluates whether the following cells can not be integrated into this zone, first according to this 10 minute criterion (steps 506, 507), then by observing whether these cells are not in fact already included in the formed area.

Preferably the system finally observes whether previous cells are not included in the zone (step 51 1) or in the previous zone (step 512), and where appropriate integrates them (step 515), or merges the zone into examination with the previous zone (step 518).

Preferably, the system analyzes all the cells created. The zones will first be analyzed in turn before being confronted with the existing places. At this stage, several identical zones may exist distinct ways, and in the same area, identical cells can be repeated.

Preferably the invention also comprises a method of sorting cells within the same area to avoid duplication. This process will now be described with reference to FIG.

The zones are considered one by one, and the cells the constituents are classified, for example by CeII-ID ascending (step 602). Several data sorting algorithms are available and usable in the present invention, for example the so-called 'Partition-Fusion' algorithm (MergeSort) commonly described in the computer literature.

The zones are now all ordered. Sorting identifies duplicate cells in each area (step 605) and eliminates them by correctly accounting for the time (duration) spent in each cell and area (step 607).

Preferably the zones composed of variables Cell (k) are now formed of variables CellZone (k), with in addition to parameters CeII-ID and duration, a new datum, the number of visits.

According to another aspect of the invention, a fusion algorithm makes it possible to merge the zones which have at least one cell in common. This algorithm will now be described with reference to FIG.

According to this example, the algorithm comprises a step (step 704) of listing all the cells present in the zones, in an intermediate variable CelITri, by associating them with the following parameters: CeII-ID, associated zone, or a index to identify the associated area. These cells are then sorted in increasing order of CeII-ID (step 705), with an appropriate sorting algorithm, for example a fusion sorting algorithm.

The duplicate cells are then easily identified (step 710), which then allows to merge the relevant areas correctly counting the passage counter and durations (steps 720, 730).

The areas are now ordered and unique (without common point).

According to another aspect the method of the invention comprises an update algorithm places that will now be described with reference to Figures 8 and 9.

According to Figure 8, the 'Fusion' algorithm described above is used to merge the areas and places that have at least one cell in common (step 803).

Preferably, a coefficient R is introduced (step 805) in order to update the data related to the Places. This coefficient is decreasing because of the elapsed time of the last update, for example according to an exponential law, and applies to the parameters of duration and counting of the visits of the places and cells that compose them (steps 806 and 807). .

This principle allows to 'forget' an important place when no longer visited for several weeks (move, change of work, end of vacation, ...).

The second form of update concerning the cells that make up the Places will now be described with reference to FIG. 9. The Zones make it possible to gradually connect new cells to already created places. Nevertheless, these cells can be anecdotal (a café next to the user's home and very occasionally visited) and must be erased. This avoids an artificial phenomenon of irreversible enlargement of the Places with time.

Cells whose visits, weighted, are less than a criterion of 0.1 are erased (step 902).

Places are sorted according to the variable "duration" (step 904) and only the places appearing at the top of the list, for example the first 20, are kept (step 906). The goal is indeed to 'learn' the environment of the user (and the mobile device) by keeping only what is significant in his lifestyle.

For Places whose GPS reading efficiency is low, a _PS t is introduced (step 908) so as to control the GPS reading accurately.

Main data (structure)

o Zone (i) = [CellZone (1), CellZone (2), ...] with CellZone (j) = [Cell-ID, count, duration]

o CellTri (i) = [Cell-ID, Zone n (n)]

o Location (i) = [count, duration, tPS, GPSEf f, CellLieu (1), CellLieu (2), ...]

o With CellLieu (j) = [Cell-ID, duration, count]

Claims

claims 1. System for geolocation of a mobile device by GNSS, arranged to recognize the geographical area in which the mobile device is located, characterized in that the periodicity of the GNSS reading is driven by the recognition of the geographical area in which the mobile device is located. 2. A GNSS geolocation system according to claim 1, characterized in that said mobile device can connect to a wireless network comprising several cells, for example a GSM (2G) / UMTS (3G or higher technology) network, or a wireless data network, for example a Wi-Fi or WiMax network, each cell having an identifier, said recognition of the geographical area being based on said identifiers of the cells. 3. GNSS geolocation system according to the preceding claim, characterized in that said mobile device is programmed to learn the geographical areas on the basis of said cell identifiers. 4. GNSS geolocation system according to one of the preceding claims, characterized in that the system identifies and stores in memory for each geographical area the average GNSS position before the loss of the GNSS signal. 5. GNSS geolocation system according to one of the preceding claims, characterized in that the system identifies and stores in memory for each geographical area the average time between entry into the geographical area and loss of the GNSS signal. 6. GNSS geolocation system according to one of the preceding claims, characterized in that the system space periodicity of the GNSS playback (sleep mode) when it has been in the same geographical area for a sufficiently long time. 7. GNSS geolocation system according to claim 2, characterized in that said recognition of the geographical area comprises a step of comparing the time spent in a predetermined number of consecutive or adjacent cells with a predefined threshold. 8. GNSS geolocation system according to one of the preceding claims, characterized in that the average position before the loss of the GNSS signal is used to locate the mobile device. 9. GNSS geolocation system according to one of the preceding claims, arranged to delete geographical areas that have not been visited for some time.