Method and device for the localisation of a terminal in a wireless LAN

The invention relates to the location of telecommunication terminals in a Wi-Fi type local network. It relates more particularly to the location of terminals in closed buildings, in order to locate a subscriber who is the bearer of the terminal.

Conventionally, to locate a person in a given geographical area, the GPS positioning system ("Global Positioning System") or the GSM system ("Global System for Mobile Communication") is generally used. However, these techniques are difficult to envisage in a closed environment, because of their performance.

Indeed, these techniques do not provide sufficient accuracy, which must be in the intended application of the order of a few tens of meters.

The object of the invention is therefore to overcome these disadvantages and relates according to a first aspect to a method of locating a terminal in a closed environment according to which the transmission power of telecommunications terminals of a local area network is measured. wirelessly, the powers of the radiation received from at least two terminals are compared with power values ​​stored in a database, and which each correspond to a position of the terminal with respect to the terminal, and the result delivered by the comparison step is filtered, and according to which a particulate filter or a Kalman filter is used during the step of filtering.

Thus, the use of the local Wi-Fi network for the location of the terminal, combined with the use of the particulate filter or the Kalman filter considerably improves the accuracy of the measurements and eliminates the improbable displacements taking into account, in particular, the structure of the building in which the terminal spreads to locate, and to take account of the movements of the user.

The interest of filtering is to limit the effect of power fluctuations that induce inconsistent movements and positions.

According to one embodiment, a particulate filter is used. During particulate filtering, we model all the possible positions of the terminal in the form of particles each affected by a probability of presence, we determine a priori the new possible position of each particle and we correct a weight assigned to the particle, from new measurements of powers.

In this case, the position of each particle is determined <i>a priori</i> from the last known position of the particle and introducing a noise on the velocity of the particle so as to obtain a random displacement of the particles between two successive power measurements.

For example, for the determination <i>a priori</i> of the new possible position of each particle, the value of the new position of the particle, its velocity, and its probability of presence are determined using the following relation:<maths id="math0001" num=""><img file="EP1575328A1_D0001.tif" /></maths>    in which :<ul id="ul0001" list-style="none" compact="compact"><li>x_{k + 1} and there_{k + 1}designate the coordinates determined a priori of the particle;</li><li>x_k and there_k denote the coordinates of the particle determined from a previous power measurement;</li><li>Vx_{k + 1} and Vy_{k + 1}denote the velocity of the particle along the x and y directions;</li><li>vx_k and vy_k designate a noise representing the displacement of the particle between two consecutive measurements.</li></ul>

According to yet another embodiment, during the step of correcting the position of the determined particle <i>a priori,</i> in addition, improbable displacement information of each particle is used and the probability of presence associated with the particle is modified according to the improbable displacement information.

For example, the probability of presence of the particle when the particle has passed through a boundary wall between the last position and the new determined position is canceled. <i>a priori.</i>

According to an advantageous embodiment, information developed from a stored plan of a building in which the terminal to be located is used to develop the information of improbable displacement.

According to yet another advantageous embodiment, a model of a building in which the terminal to be modeled is used, the model comprising a set of possible paths for the particles in which they are authorized to move, this model being preferably elaborated from a Voronoi diagram of the building.

According to another characteristic of the invention, the step of correcting the position of the particle further comprises a step of determining the value of a variable representative of the position of each particle corresponding to received power levels, said variable being modeled as a Gaussian law able to represent a realistic distance that can traverse a particle between two consecutive power measurements.

Finally, the location of the terminal is calculated by calculating the barycentre of the presence probabilities associated respectively with the particles, a step of normalizing the probability of presence associated with the particles may also be provided.

According to another characteristic of the invention, a Kalman filter capable of taking account of the movements of the terminal is used.

The Kalman filter step equations are as follows:<maths id="math0002" num=""><math display="block"><mrow><mtext mathvariant="italic">X</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">k = AX</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub></mrow></msub><msub><mrow><mtext mathvariant="italic">+ w</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0002.tif" /></maths> and<maths id="math0003" num=""><math display="block"><mrow><mtext mathvariant="italic">Z</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">k = HX</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub></mrow></msub><msub><mrow><mtext mathvariant="italic">+ W '</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0003.tif" /></maths> in which :<ul id="ul0002" list-style="none" compact="compact"><li>X_k is a state variable corresponding to the position (x_k, including_k) and speed (vx_k, vy_k) of the terminal;</li><li>Z_k is a measure of x coordinates_BD and there_BD terminal resulting from the measurement of powers;</li><li>w and w 'are Gaussian noises; and</li><li>A and H are matrices of the filter,</li></ul> with:<maths id="math0004" num=""><img file="EP1575328A1_D0004.tif" /></maths><maths id="math0005" num=""><img file="EP1575328A1_D0005.tif" /></maths><maths id="math0006" num=""><img file="EP1575328A1_D0006.tif" /></maths>    <i>and</i><maths id="math0007" num=""><img file="EP1575328A1_D0007.tif" /></maths>

According to the invention, there is also provided a device for locating a terminal in an environment, comprising means for measuring the transmission power of telecommunications terminals of a wireless local area network and means for comparing the power of the received radiation from each terminal with power values ​​stored in a database and which each correspond to a position of the terminal with respect to the terminal and means for filtering the result delivered by the comparison means, the filtering means comprising particulate filtering means or a Kalman filter adapted to take account of the movements of the terminal.

According to a preferred implementation, the steps of the method are determined by the instructions of a localization program incorporated in an electronic circuit, such as a chip, which itself can be arranged in an electronic device such as a communication terminal. The locating method according to the invention can equally well be implemented when this program is loaded in a computing device such as a processor or equivalent, forming part of, for example, a communication terminal, whose operation is then controlled by the execution of the program.

Accordingly, the invention also applies to a computer program, including a computer program on or in an information carrier, adapted to implement the invention. This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code such as in a partially compiled form, or in any other form desirable to implement a method according to the invention.

The information carrier may be any entity or device capable of storing the program. For example, the medium may comprise storage means, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording medium, for example a diskette (floppy disc) or a disk hard.

On the other hand, the information medium may be a transmissible medium such as an electrical or optical signal, which may be conveyed via an electrical or optical cable, by radio or by other means. The program according to the invention can in particular be downloaded from a server accessible on an Internet type network.

Alternatively, the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.

Other objects, features and advantages of the invention will appear on reading the following description, given solely by way of nonlimiting example, and with reference to the appended drawings in which:<ul id="ul0003" list-style="dash" compact="compact"><li>Figure 1 is a schematic view of a closed building in which it is desired to locate a terminal;</li><li>Figure 2 is a block diagram of a locating system according to the invention;</li><li>Figure 3 shows the architecture of a database for locating a terminal from measured powers;</li><li>Fig. 4 is a flowchart illustrating the terminal location principle using a Kalman filter;</li><li>Figure 5 is a flow chart illustrating the principle of location of the terminal in the building using a particulate filter;</li><li>Figure 6 is a schematic view of the building illustrating the particle propagation;</li><li>Fig. 7 is a diagram illustrating the building modeling principle using a Voronoi diagram;</li><li>Figures 8a to 8f illustrate the principle of development of the building model from the Voronoi diagram of this building; and</li><li>Figure 9 is a flowchart illustrating the location of a terminal from particulate filtering using a Voronoi diagram to model the environment in which the terminal is located.</li></ul>

In Figure 1, there is shown the general architecture of a building B, constituted for example by the premises of a company or in which is organized an exhibition or a Salon. Building B constitutes a closed environment in which it is necessary to locate a terminal 10 in order to locate its owner.

The terminal 10 is constituted by a telecommunication station of Wi-Fi type, that is to say a station able to enter into communication with a set of terminals 12, 14, 16 and 18 of a local area network Wi-Fi .

In the context of the present description, a Wi-Fi terminal denotes a terminal of a wireless local area network whose position is not intended to be modified frequently, such as an 802.11 access point or a terminal "Bluetooth" fixed. Note however that the present description applies, in general, to the location of a terminal in any type of wireless LAN.

Referring to Figure 2, the positioning device, which may, for example be fully integrated in the terminal 10, first comprises a first stage 20 incorporating Wi-Fi sensors and power measuring means. This first stage 20 is connected to a first computing stage 22 which communicates with a database 24 in which power level values ​​are stored for each locatable location of the building B. This first computing stage 22 recovers, from the power levels provided by the first stage 20, a probable location for the terminal 10.

Indeed, the location of the terminal 10 is first based on the use of the database in which at each position of the terminal 10 in the building B are assigned values ​​of power levels of the radiation received from the terminals 12, 14, 16 and 18, respectively.

Thus, as represented in FIG. 3, from a measurement of the powers P1, P2, P3 and P4 received from each terminal, it is possible to determine the positions X and Y of the terminal. This database is developed during a preliminary calibration phase during which the building is meshed and, for each mesh of the building corresponding to a position X, Y, power levels received from the Wi terminals are affected. -Fin 12, 14, 16 and 18. For example, in the case where it is a question of locating a terminal on the premises of a company, each mesh corresponds to an office or a room of the building B.

In order to improve the accuracy of the location, the locating device further comprises filtering systems 26 functioning for example independently, namely a filtering system 28 using a Kalman filter, which is intended to take into account movements of the user and limit the fluctuations of positions, or a filtering system 30 constituted by a particulate filter that allows to take into account the building structure and the movement of the user.

With reference to FIG. 4, which illustrates a first embodiment of the invention based on the use of the Kalman filter, after measuring the power levels (step 31), the calculation stage proceeds, when the step 32, to a calculation of the position Z of the terminal 10 from the coordinates extracted from the database (<i>BD</i>). This point Z corresponds to a raw location and is developed from the following equation:<maths id="math0008" num=""><math display="block"><mrow><mtext>Z = arg min Σ (</mtext><msub><mrow><mtext mathvariant="italic">Pborne</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">there</mtext><mtext>) - </mtext><msub><mrow><mtext mathvariant="italic">Pborne</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">received</mtext><msup><mrow><mtext>))</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mspace linebreak="newline" /><mtext mathvariant="italic">z</mtext><mtext>ε (</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">there</mtext><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">delaBD</mtext></mrow><mrow><mtext mathvariant="italic">touteslesbornes</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0008.tif" /></maths>

In other words, the point Z corresponds to the point closest to the space of the powers in the sense of the Euclidean distance between the received powers and the powers of the database.

This point Z is one of the inputs of the Kalman filter whose entries are as follows:<maths id="math0009" num=""><img file="EP1575328A1_D0009.tif" /></maths>    in which :<ul id="ul0004" list-style="none" compact="compact"><li>x_k and there_k designate the coordinates of the terminal;</li><li>vx_k and vy_k designate the coordinates of the speed vector of the terminal; and</li><li>x_<i>BD</i> and there_<i>BD</i> refer to the coordinates extracted from the database.</li></ul>

The state equations of the Kalman filter are as follows<maths id="math0010" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">= A • X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0010.tif" /></maths>    and<maths id="math0011" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">Z</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">= H • X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">+ w '</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0011.tif" /></maths>    which respectively represent the dynamics of the user and the difference between the user position given by the Kalman filter and the position of the user from the database.

In these state equations:<maths id="math0012" num=""><img file="EP1575328A1_D0012.tif" /></maths>

We then seek to find from the state at time k-1, that is to say the state represented by the state variable X_k-1 and the measure at the moment k, that is to say the point Z_k from the database (step 33), the state at time k, that is to say the coordinates of the state variable X_k.

For that, we put the following equations:<maths id="math0013" num=""><math display="block"><mrow><msubsup><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">AX</mtext></mrow><mrow><mtext mathvariant="italic">K</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0013.tif" /></maths><maths id="math0014" num=""><math display="block"><mrow><msubsup><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">AP</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub><mtext>.</mtext><msup><mrow><mtext mathvariant="italic">AT</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msup><mtext> + </mtext><mtext mathvariant="italic">Q</mtext></mrow></math><img file="EP1575328A1_D0014.tif" /></maths><maths id="math0015" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = </mtext><msubsup><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext>.</mtext><msup><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msup><mtext>(</mtext><mtext mathvariant="italic">H</mtext><mtext>.</mtext><msubsup><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext></mtext><msup><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msup><mtext> + </mtext><mtext mathvariant="italic">R</mtext><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup></mrow></math><img file="EP1575328A1_D0015.tif" /></maths><maths id="math0016" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = </mtext><msubsup><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">Z</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">- H</mtext><mtext>.</mtext><msubsup><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup><mtext>)</mtext></mrow></math><img file="EP1575328A1_D0016.tif" /></maths><maths id="math0017" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">Id - K</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext mathvariant="italic">.H</mtext><mtext>)</mtext><msubsup><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">-</mtext></mrow></msubsup></mrow></math><img file="EP1575328A1_D0017.tif" /></maths>

As we can imagine, using these equations, we thus obtain the value of the state variable X_k, which corresponds to the most probable position, with an expected error on the measure corresponding to P_k. (step 34). We then return to the previous step 31 to acquire new power measurements.

As indicated above, according to another variant, or additionally, a particulate filter 30 is furthermore used so as to take account of the structure of the building in which the terminal 10 is propagated.

Particulate filtering is a global method based on an exploration of the building by particles whose dynamics evolve randomly. All of these particles are distributed according to the probability of the process to be estimated, conditional on the observations resulting from the power measurements.

Such a filter makes it possible to integrate several pieces of information of different nature, namely power information or information relating to a position, a map of the environment in which the terminal is located, inertial navigation information, ie speed and acceleration of the terminal, direction of displacement, ... This is made possible by the use of probability densities that model these different parameters.

Thus, the particulate filter is based on the use of a set of particles that model a possible position of the terminal, and which are each assigned a probability of presence.

We will now describe with reference to Figure 5, the filtering procedure using the particulate filter. In this figure, the steps 31 and 32 are identical to the corresponding steps of FIG.

Particulate filtering begins with a determination step <i>a priori</i> of the new position of each of the particles. This step, which will be described in detail later, essentially consists in determining the future position of each particle from their last known position.

This first step is followed by steps 36 and 37 in which the weight of each particle is updated using new measurements from the sensors.

According to this principle, the particulate filter can be defined according to the following two equations:<maths id="math0018" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub><msub><mrow><mtext>, ν</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1575328A1_D0018.tif" /></maths><maths id="math0019" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">Z</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">= h</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">not</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1575328A1_D0019.tif" /></maths>    in which X_k is a vector containing the position and speed of the terminal, ν_k-1 and N_k designate two random noises, f_k and h_k designate two functions, possibly non-linear, allowing respectively to determine the position <i>a priori</i> the terminal according to the previous position history and to link the position <i>a priori</i> to all available measures.

It can be shown that the weight ω_{k + 1}ⁱ of a particle i is related to the weight ω_k of this particle at the instant k preceding and can be defined according to the following relation:<maths id="math0020" num=""><img file="EP1575328A1_D0020.tif" /></maths>    in which :<maths id="math0021" num=""><img file="EP1575328A1_D0021.tif" /></maths>    respectively indicate the probability of presence of a calculated particle <i>a priori,</i> the calculated probability of presence <i>a posteriori</i> and a function of importance penalizing the improbable displacements.

Thus, we see that the weight of each particle takes into account the prediction law <i>a priori</i> and the prediction law <i>a posteriori.</i>

Regarding the determination <i>a priori</i> of the new position of the particles, as indicated previously, this position is determined only from their last known position and by causing the particles to propagate randomly in the building by using a noise on the velocities determined so that the particles move between two successive measurements.

The determination <i>a priori</i> of the new position of each particle is thus carried out from the following relation:<maths id="math0022" num=""><img file="EP1575328A1_D0022.tif" /></maths>    in which<ul id="ul0005" list-style="none" compact="compact"><li>x_{k + 1} and there_{k + 1}designate the coordinates determined a priori of the particle;</li><li>x_k and there_k denote the coordinates of the particle determined from a previous power measurement;</li><li>Vx_{k + 1} and Vy_{k + 1}denote the velocity of the particle along the x and y directions</li><li>vx_k and vy_k designate a noise in the x and y directions reflecting the displacement of the particle between two consecutive measurements.</li></ul>

After determining <i>a priori</i> the new position of each particle, when determining the position a <i>posteriori</i> Particles that have traversed a wall are searched for using a database 38 illustrating a view of the building or, in general, in which improbable displacement information is stored.

Essentially, during this phase, a comparison is made between the path of a particle, between the previous position and the new position, and the plane of the building so as to determine if this particle has crossed a wall. If this is the case, it is necessary to penalize, or even eliminate particles that have crossed a wall because it is a movement that a user can not perform. Thus, at the end of this treatment, each remaining particle corresponds to a possible position within its environment. In the next step 37, after receiving a new measurement, the weight of each particle is updated from the position associated with the power level corresponding to a new measurement. The density of probability of presence affected<i>a posteriori</i> to each particle, that is, taking results from a new measurement is given by the following relation:<maths id="math0023" num=""><img file="EP1575328A1_D0023.tif" /></maths>

It has been found that it is advantageous to choose, in order to develop this probability density, a Gaussian law centered on the position resulting from the measurement and of the standard deviation judiciously chosen so as to represent a realistic distance that the terminal can travel between two successive measurements.

Finally, in the following step 38, the new weight of the particle is determined, according to the following relation:<maths id="math0024" num=""><img file="EP1575328A1_D0024.tif" /></maths>

A weight normalization step may be performed in this step 38 to obtain the following probability density:<maths id="math0025" num=""><img file="EP1575328A1_D0025.tif" /></maths>

Thus, at each reception of a new power measurement, the filter evolves, and the weight of particles evolves. In particular, because of the assignment of a low or no weight to certain particles having undergone an improbable displacement, a degeneracy of the filter appears. This degeneration can continue until a single particle remains in effect.

To overcome this drawback, at the end of step 37 of updating the weight of each particle, if necessary, the particles are resampled so as to reduce the particles which have a very low weight. that is, the particles that correspond to an improbable position of the terminal, in the zone in which the mobile is probably located, that is to say around the particles that have a significant weight. To do this, in a first step 40, it is determined whether the conditions on the resampling are fulfilled. This test consists in detecting if the number of particles N_eff in force is less than a threshold value N_threshold. This test is carried out from the following relation:<maths id="math0026" num=""><img file="EP1575328A1_D0026.tif" /></maths>

In the case where the number of particles is less than the threshold value, resampling is performed (step 42).

If not, the procedure continues with the previously mentioned step 35.

It will be noted that, preferably, in order to avoid losing diversity to the particles, during resampling, a certain diversity is introduced among the particles by introducing a noise into the particles so as to enable them to explore again the area of ​​the building in which they are located.

The resampling algorithm used is as follows:<ul id="ul0006" list-style="dash" compact="compact"><li>in a first step, the covariance matrix S is calculated_k particles;</li><li>We then proceed to calculate the noise D_k such as S_k = D_kD_k^T</li><li>The actual resampling is then carried out by initializing a cumulative distribution function vector CDF such that CDF (1) = 0;</li><li>We build CDF as <i>CDF (i) = CDF</i>=(<i>i</i>-1)<i>+ w</i>^<i>i</i>_<i>k</i> with i = {2: N_s}</li><li>We initialize a variable i to 1;</li><li>We randomly draw a value <i>u</i>(1) in a uniform law U [0, N_s^-1] ;</li><li>The cumulative distribution function is scanned to detect interesting transitions. To do this, a transition detection is performed. It is a question of calculating the value u (j) according to the relation:<maths id="math0027" num=""><math display="block"><mrow><mtext mathvariant="italic">u (j)</mtext><mtext> = </mtext><mtext mathvariant="italic">u (1) +</mtext><mtext></mtext><mfrac><mrow><mtext>j-1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">NOT</mtext></mrow><mrow><mtext mathvariant="italic">S</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1575328A1_D0027.tif" /></maths></li></ul> and to test that the sum of the weights of the particles u (j) is greater than the function CDFi, according to the following relation:<maths id="math0028" num=""><math display="block"><mrow><mtext mathvariant="italic">As long as u (j)&gt; CDF (i)</mtext><mtext> so </mtext><mtext mathvariant="italic">i = i</mtext><mtext>+1</mtext></mrow></math><img file="EP1575328A1_D0028.tif" /></maths>

If this is the case, one increments the variable i and returns to the same weight the particle of interest according to the following relations:<maths id="math0029" num=""><math display="block"><mrow><msubsup><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msubsup><mtext></mtext><msubsup><mrow><mtext mathvariant="italic">= x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msubsup><mtext> and </mtext><msubsup><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msubsup><mtext>=</mtext><msubsup><mrow><mtext mathvariant="italic">NOT</mtext></mrow><mrow><mtext>·</mtext><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>-1</mtext></mrow></msubsup></mrow></math><img file="EP1575328A1_D0029.tif" /></maths>

Finally, in order to prevent particles from getting stuck in an area of ​​the building, in particular because they can not cross a wall, all the particles are scanned, a noise is randomly drawn.ⁱ in a nucleus (Gaussian, Epanechnikov, ...) and we update the new position of the particles such as:<maths id="math0030" num=""><math display="block"><mrow><msubsup><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msubsup><mtext></mtext><msubsup><mrow><mtext mathvariant="italic">= x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msubsup><mtext></mtext><msub><mrow><mtext mathvariant="italic">+ h</mtext></mrow><mrow><mtext mathvariant="italic">Opt</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><msup><mrow><mtext mathvariant="italic">ε</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msup></mrow></math><img file="EP1575328A1_D0030.tif" /></maths>

This last noise makes it possible to reintroduce a new diversity around interesting positions. In the case of a Gaussian kernel, the constant<i>h</i>_<i>OPT</i> is expressed as follows:<maths id="math0031" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">h</mtext></mrow><mrow><mtext mathvariant="italic">Opt</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">AT</mtext><mtext>(</mtext><mtext mathvariant="italic">K</mtext><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">NOT</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mfrac><mrow><mtext>1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">not</mtext></mrow><mrow><mtext mathvariant="italic">x + 4</mtext></mrow></msub></mrow></mfrac><mtext> and </mtext><mtext mathvariant="italic">A (K)</mtext><mtext> = </mtext><mfenced open="(" close=")"><mrow><mfrac><mrow><mtext>4</mtext></mrow><mrow><msub><mrow><mtext>not</mtext></mrow><mrow><mtext>x + 2</mtext></mrow></msub></mrow></mfrac></mrow></mfenced><msup><mrow><mtext>​</mtext></mrow><mrow><mfrac><mrow><mtext>1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">not</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msub><mtext> + 4</mtext></mrow></mfrac></mrow></msup></mrow></math><img file="EP1575328A1_D0031.tif" /></maths>    not_x designating the dimension of the space in which one is located.

In the description that has just been given, the position of each particle determined a priori is corrected by using improbable displacement information developed from a plane of the building in which the terminal moves, this correction essentially consisting in modifying the probability of presence associated with each particle based on improbable displacement information.

According to another embodiment, which will now be described with reference to FIGS. 7 to 9, the particles are forced to move on predetermined paths corresponding only to possible paths for the terminal. To do this, we use a modeling of the building grouping all the possible paths.

As can be seen in FIGS. 7a to 7f, this modeling is based on the development of a Voronoi diagram and is automatically calculated from an image, for example in JPEG format, of the building. In principle, as can be seen in FIG. 6, it is essentially a question of finding the equidistant L limits of objects O present in the environment.

Thus, when we consider the plan of a building, it is easy to detect the walls that are usually represented by black pixels. We then look for the Voronoi diagram associated with the walls. Such a diagram is obtained by means of algorithms within the reach of those skilled in the art, which will therefore not be described further later. Such a diagram is shown in Figure 8a and, on a larger scale in Figure 8b, for a given portion of the building.

As is known, such a diagram is very rich in information and contains in particular a number of arcs related to the search for equidistance limits between the pixels of the wall. In the case of the present invention, it is necessary to remove all the arcs that have a starting node or an arrival node located on a wall, as well as the arcs that intercept a wall.

It is therefore essential, essentially, to recover the main nodes that are equidistant from at least three objects, in particular to keep the nodes that are in the middle of the rooms, as well as those that are close to discontinuities in the walls , related to the presence of doors, (Figure 8c).

Moreover, we reconstruct the arcs between the nodes previously preserved (Figure 8d). Finally, we proceed to a fusion of the nodes which are closest to each other. It is in fact to calculate the barycentre of adjacent nodes and whose length of arcs that binds them is less than a predetermined threshold value (Figure 8f).

From this graph, the particles are forced to move on the arcs. It is therefore no longer necessary to check whether the particles have crossed a wall during the determination phase<i>a priori.</i> In addition, since the area to be explored is smaller, it is possible to reduce the number of particles to be used. On the other hand, it is necessary to manage the displacements of the particles on the arcs, knowing that the relation between these is known.

It was therefore chosen to orient the arcs, an arc having a starting node and an arrival node. With regard to the particles, they are represented by the index of the arc on which they are located, the distance from the starting node of the arc, a speed which is generated randomly, and a weight which is calculated as in the particulate filtering algorithm described above.

Thus, the particles move according to the law of the following movement:<maths id="math0032" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">V</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext mathvariant="italic">* T</mtext><mtext>+</mtext><mfrac><mrow><msup><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow><mrow><mtext>2</mtext></mrow></mfrac><mtext mathvariant="italic">* b</mtext></mrow></math><img file="EP1575328A1_D0032.tif" /></maths><maths id="math0033" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">V</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">= V</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext>-1</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">+ b * T</mtext></mrow></math><img file="EP1575328A1_D0033.tif" /></maths>    in which <i>b</i> is a Gaussian noise.

Three cases can occur.

First, the new position of the particle is positive and less than the length of the arc. The particle remains on the same arc.

The new position of the particle can be positive and greater than the length of the arc. The particle passes over one of the arcs that arrive or depart from the arrival node of the arc on which it was located. In the case where it is an arc starting from the arrival node, the speed remains the same. On the contrary, if it is an arc arriving at the arrival node, the velocity is the opposite of the current velocity of the particle.

Finally, the new position of the particle can be negative. In this case, the particle passes on one of the arcs which arrive or which leave from the node of departure of the arc on which it was. In the case where it is an arc starting from the starting node, the speed is the opposite of the absolute value of its previous speed. On the contrary, if it is an arc arriving at the starting node, the speed is the absolute value of its previous speed.

In addition, when several arcs are available during the change of arcs, we proceed to a new random draw of the arc on which the particle will move. This random draw is carried out according to a uniform law but which could also be any law resulting for example from an apprenticeship.

In view of the foregoing, with reference to FIG. 8, in the case where a new position of the particles is drawn (step 42), the following step 44 is carried out in the search for the new arc associated with the particle.

In the following step 46, a comparison is then made between the distance D traveled and the length of the arc. If the distance is greater than the length Li of the arc, in the following step 48, in the case where the distance is positive, the particle is positioned as follows:<ul id="ul0007" list-style="dash" compact="compact"><li>either on a starting arc with an identical speed and a position given by:<maths id="math0034" num=""><math display="block"><mrow><msub><mrow><mtext>D = DL</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext>,</mtext></mrow></math><img file="EP1575328A1_D0034.tif" /></maths></li><li>either on an arc arriving with a speed equal to the opposite of the current speed of the particle and a position D given by:<maths id="math0035" num=""><math display="block"><mrow><mtext>LJ D = (R-Li).</mtext></mrow></math><img file="EP1575328A1_D0035.tif" /></maths></li></ul>

In the case where the new position of the particle is negative, the particle passes:<ul id="ul0008" list-style="dash" compact="compact"><li>either on a starting arc with a speed equal to the opposite of the absolute value of its previous speed and at a position given by:<maths id="math0036" num=""><math display="block"><mrow><msub><mrow><mtext>D = D + L</mtext></mrow><mrow><mtext>j</mtext></mrow></msub></mrow></math><img file="EP1575328A1_D0036.tif" /></maths></li><li>either on an arc arriving with a speed equal to the absolute value of its previous speed and a position given by D = Abs (D).</li></ul>

The procedure then returns to the previous step 46.

If, during step 46, it has been detected that the distance D is less than the length of an arc, the weight of the particles (step 50) is updated from the position delivered by the measured. A determination of the new current position of the terminal is then made, as indicated above, by calculating the barycentre of the coordinates of all the particles and normalization with the possibility of projecting this barycenter on the graph.