Positioning system and method with multipath mitigation

Abstract

The present invention proposed a weighted Centroid Localisation (WCL) algorithm, which does the location estimation based on the known positions of the gateways and the measurements times of arrival (TOA) at the gateways. The algorithm computes the weight of the gateway based on their rank when the gateways are sorted by their TOA. Simulations have demonstrated the algorithm's robustness under different multipath/fading channel conditions and its good location performance.

Claims

1. A system comprising at least a mobile device and a plurality of gateways whose positions are known, wherein the gateways are operatively arranged receive a radio signal from the mobile device and to determine a time of arrival of said signal at the gateway, the system comprising a solver unit operatively arranged to compute the position of the mobile device based on said times of arrival, characterised in that the solver unit is arranged to assign to each gateway a weight factor dependent from its rank when the gateways are sorted by their received time of arrival, whereby those gateways whose time of arrival is earlier are assigned a heavier weight factor, the system being further arranged to compute the position of the mobile device by a weighted sum of the position of the gateways using said weight factors.

2. The system of claim 1, the solver being arranged to compute the weight factors based on the rank and the time-difference of arrival of the signal at the gateways.

3. The system of claim 2, the solver being arranged to divide the time-difference of arrival is by a scale factor dependent from the average distance between the gateways that received the signal.

4. The system of claim 1, wherein the weight factors are always positive or zero, and/or they are zero when the time-difference of arrival exceeds a determined value.

5. The system of claim 1, wherein the solver is arranged for computing the weight factors (w.sub.i) of each gateway by:
=r.sup.2.sub.i.Math.max(0,kt.sub.i/) where r.sub.i represents the rank of the gateway, t.sub.i its time-difference of arrival, the average distance between the gateways that received the signal, and k is a predetermined value.

6. The system of claim 1, operatively arranged to: compute also a range-based position estimation from said times of arrival; determine a first quality parameter expressing the quality of the range-free position estimate, a second quality parameter expressing the quality of said range-based position estimate; and combine the range-free position estimate and the range-based position estimate using said first and second quality parameters.

7. A method of determining the position of a mobile device relative to a plurality of gateways whose positions are known, comprising: determining for each gateway a time of arrival of the signal, assigning to each gateway a weight factor dependent from the rank it occupies when the gateways are sorted by their time of arrival, whereby those gateways whose time of arrival is earlier are assigned a heavier weight factor, computing the position of the mobile device by a weighted sum of the position of the gateways using said weight factors.

8. The method of claim 7, wherein the weight factors are computed based on the rank and the time-difference of arrival of the signal at the gateways.

9. The method of claim 8, wherein the time-difference of arrival is divided by a scale factor dependent from the average distance between the gateways that received the signal.

10. The method of claim 7, wherein the weight factors are always positive or zero, and/or they are zero when the time-difference of arrival exceeds a determined value.

11. The method of claim 7, wherein the weight factors (W.sub.i) of each gateway are calculated by:
W.sub.i=R.sub.i.sup.2.Math.max(0,kt.sub.i/) where r.sub.i represents the rank of the gateway, t.sub.i its time-difference of arrival, the average distance between the gateways that received the signal, and k is a predetermined value.

12. The method of claim 7, comprising: computing also a range-based position estimation from said times of arrival, determining a first quality parameter expressing the quality of the range-free position estimate, and a second quality parameter expressing the quality of said range-based position estimate, and combining the range-free position estimate and the range-based position estimate using said first and second quality parameters.

13. The method of claim 7, comprising a step of correcting the times of arrival towards earlier arrival times, based on an indication of multipath.

14. The method of claim 13, wherein the steps of correcting the times of arrival and of determining a refined position are repeated iteratively until a determined convergence criterion is satisfied.

15. The method of claim 13, wherein the indication of the multipath that the signal has suffered in the propagation to the corresponding gateway is a multipath prediction based on a propagation model.

16. The method of claim 13, wherein the indication of the multipath that the signal has suffered in the propagation to the corresponding gateway is derived from a path loss exponent.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates in schematic simplified manner, a process of localization by which a plurality of gateways receive a localization packet transmitted by a mobile node and determine its location by means of a solver that processes the times of arrival of the packets at each gateway. The invention also proposed enhanced positioning methods that combine a robust range-free estimate with a range-based one.

(2) FIG. 2 represents, by a flowchart, a possible implementation of the inventive method.

(3) FIG. 3 plots a weight function.

(4) FIG. 4 describes an iterative method of position determination.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(5) FIG. 1 illustrates a mobile node 110 in a wireless network transmitting a data packet 135. The wireless network includes a plurality of gateways 160, whose positions are known. A number N of these, whose locations are (x.sub.i,y.sub.i); (i=0, . . . N1), are in reception range and receive the packet 135. Each of the gateways 160 determines the time of arrival TOA of the packet 135, and the corresponding timestamps are collected (arrow 170) in a solver unit 180. The solver unit 180 is represented here as a separate functional entity, and may be physically implemented in a separate server, but it could also, without leaving the invention, be hosted in one of the gateways 160. It would be also conceivable, in the frame of the invention, that the position determination be performed in a plurality of solver units, independently or in collaboration.

(6) Importantly, timestamps 170 taken by different gateways must be comparable with each other. To this purpose, the time references of the gateways 160 could be synchronized, by any suitable synchronization protocol (arrows 140), or the gateways 160 may rely on a common time reference in the form, for example, of GPS-disciplined clocks. In alternative, the time references of the gateways may be independent from each other, but the solver 180 knows their individual timing errors and can correct them, translating the timestamp 170 into a common time reference. It is not an essential feature of the invention that the signal 135 is a data packet, either; the invention could function with any signal whose time of arrival can be determined.

(7) In addition to the timestamp, the gateways could make other information accessible to the solver 180, for example an indicator of the received signal strength (RSSI), or the direction of the signal, if it is available. Should the gateway include a plurality of antennas, the metrics of all the antennas could be transmitted or, the gateway could transmit the metric relative to one selected antenna, chosen as the best representative of the diversity set, for example based on the RSSI or the first time of arrival. The gateway, or the solver, could compute average metrics, based on the signal received by all its antennas (see steps 210, 220 in FIG. 2).

(8) The invention is not limited to the transmission and the reception of a single packet, either. If the transmission 135 is repeated, gateway 160 and/or the solver 180 have access also to the average time of arrival at a particular gateway, and to its variation.

(9) The range-free location method of the invention proceeds in the solver as follows:

(10) The TOA are sorted in decreasing order of arrival time, from the first to the last, and each is assigned a numeric rank r.sub.i (step 230). For example, the smallest TOA (the first signal to be received) is assigned the highest rank, and the highest the lowest rank. In the case represented, the first gateway to receive the signal could acquire rank 6, and the last one would receive rank 1.

(11) The solver also computes the time differences of arrival or TDOA, that is the times of arrival of the signal relative to the first reception, t.sub.i, and the average distance between all the gateways involved, (step 225).

(12) Assume there are a total of N nodes that have received a signal, the position of the mobile device will be determined by a WCL algorithm (step 250): a weighted (vector) sum of the position of the gateways using a set weight factors, which can be expressed as:

(13) $\begin{array}{cc}X=\frac{\underset{i=0}{\overset{N-1}{.Math.}}{w}_i{x}_i}{\underset{i=0}{\overset{N-1}{.Math.}}{w}_i}Y=\frac{\underset{i=0}{\overset{N-1}{.Math.}}{w}_i{y}_i}{\underset{i=0}{\overset{N-1}{.Math.}}{w}_i}& \left(1\right)\end{array}$
where w.sub.i is the weighting factor for gateway G.sub.i, X and Y are the estimated location of the target node.

(14) An important feature of the inventive algorithm is the way to determine the weighting factors w.sub.i (step 240). According to the invention, the weights are determined based on the rank and on the value of the TDOA. Importantly, the values of the TDA may be corrected by a common scale factor that is derived from the average distance between the gateways that received the signal.

(15) Specifically, the weights may be calculated by a weight function that is mainly determined by the rank value and, rank being constant, decreases for larger TDOA, such that gateways that are too far away from the target contribute little or nothing to the weighted summation. In a favourable implementation, the weight function is represented by
w.sub.i=r.sub.i.sup.2.Math.max(0,kt.sub.i/)(2)
where r.sub.i denotes the rank of the i-th gateway, and t.sub.i its TDOA, is the average distance between all the gateways, and k is a constant factor that is predetermined and is not critical. Implementations with k=3, meaning that gateways whose TDOA is three times or more than the average gateway distance (multiplied by propagation speed, of course) contribute nothing to the position, have given good results in simulation. The plot in FIG. 3 shows how the weight factor decreases linearly for increasing t.sub.i in such a case. It is understood, however, that the linear dependence is not an essential feature, and other weight functions could be used as well. Preferably, the weights are never negative, which ensures that the position estimate will be contained in the polygon having the participating gateways at vertexes.

(16) The method described above foresees the transmission of a single packet from the mobile node to the gateways. If more packets are exchanged, the precision can be increased by computing a new location for each packet, as described above, and finally combining the locations in a final estimate. The combination may be a simple average, or foresee different options, for example weighting each position in consideration of the number of receiving gateways, the signal received signal strength, etc.

(17) The invention allows various improvements to enhance its precision and robustness. In a possible variant, the weighting factors on may be partly dependent form the RSSI, if they are available.

(18) Advantageously, the range-free time position estimate calculated based on the TOA by formula can be combined with position estimates of different nature and origin. In one variant, the combination is made with range-free position estimation based on the RSSI's indication, possibly as described in European application No EP16196989 in the name of the applicant, which is hereby incorporated by reference and describes a position estimate in which the received gateways are sorted based on their RSSI, and combined with rank-dependent weights. In this manner a completely range-free position estimate is achieved.

(19) The combination could foresee different options. The simplest is the averaging of the two estimates. A better accuracy could be obtained by applying weight to the two estimates that account for their different precision or reliability. The reliability of the RSSI-based estimate can be deduced by the absolute level of RSSI, and/or by the number of gateway involved. A figure of merit of the TOA-based estimation described above, can be judged by the average inter-gateway spacing , the number of gateways involved and, when several packets are received, TOA deviations.

(20) In general, the TOA timestamps will allow also a range-based estimation of the position of the mobile note together with the range-free one. This estimation may be obtained by conventional lateration techniques, or possibly by the method described in European patent application EP16180854 in the name of the applicant, which is hereby incorporated by reference, and foresees the computation of an extended least median solution, out of a set of three-gateway solutions.

(21) In an embodiment of the invention, the solver computes receives the times of arrival of the packet at the gateways and computes, out of them, both a range-based estimation (x.sub.r,y.sub.r), and, as described above, a range-free estimation (x.sub.f,y.sub.f), which are then combined into one. In this manner, the system of the invention can provide accurate positioning based on ranges when the propagation conditions are optimal or good and, with the onset of multipath, is still capable of positioning the nodes, possibly at the cost of some degradation of precision by using, and giving progressively more weight to, the range-free estimate.

(22) As per the previous enhancement, the range-free and the range-based estimates could be simply averaged, or combined in a weighted average.

(23) Preferably, the solver estimates the quality of the range-based estimate, and of the range-free one. These quality parameters are then use to determine their relative weights in the combination, or to select one rather than the other.

(24) The quality of the range-based estimate can be judged in several ways. A valid possibility involves the least-square error residues of the TDOA,

(25) $\begin{array}{cc}{s}^2=\underset{i=1}{\overset{n-1}{.Math.}}{\left(\sqrt{{\left(x-x_i\right)}^2+{\left(y-y_i\right)}^2}-\sqrt{{\left(x-x_0\right)}^2+{\left(y-y_0\right)}^2}-t_i\right)}^2& \left(3\right)\end{array}$
where (x,y) denotes the range-based estimate, (x.sub.i, y.sub.i) the position of the i-th gateway, (x.sub.o,y.sub.o) that the first gateway that received the packet, and t.sub.i the i-th TDOA. The dilution of precision could also be used.

(26) The quality of the range-free estimate can be judged, as mentioned above, from the average inter-gateway spacing , or also the number of gateways involved and, when several packets are received, TOA deviations.

(27) The quality parameters are compared with two threshold values. If the TDOA error residue s.sup.2 exceeds the corresponding threshold, the range-based estimation is considered unreliable and is simply discarded; the position is estimated by the range-free method alone. Conversely, if the inter-gateway spacing is higher than its corresponding threshold, the range-free estimation is discarded, and the position given by the range-based method only. If, however both estimation appear reliable, from this comparison with the thresholds, then the final estimation of the position will be a weighted average of the two. The relative weights are computed based on the relative quality parameters.

(28) According to another variant, the position of the mobile node 110 is computed iteratively, with a step in which the time-of arrival timestamps t.sub.i are modified after the first position determination, and then a refined position is computed based on the adjusted timestamps. The adjustment of the timestamps, leads to a better positioning because it is done in order to compensate for multipath propagation. For each receiving gateway 160, the timestamp is corrected toward earlier time of arrival in such a manner that the time-shift introduced by multipath is at least in part eliminated.

(29) According to a possible variant, the positioning server 180 includes, or has access to a propagation model 185 (FIG. 1) that provides, from a first position estimate, the predicted values of from the first estimated position 310 (FIG. 4) to any gateway. The model can be setup once and reused as many times as necessary, and requires updates only at major terrain modifications like, in a city, substantial building modification or creation. From this multipath prediction, the timestamps t.sub.i can be modified (320) and a refined position 330, closer to the real position of the mobile node, estimated. The cycle of correcting the timestamps and refining the position can be repeated as many times as necessary, until the positioning the position is satisfactory, using a suitable convergence criterion 340.

(30) In other variants, the multipath correction is not explicitly based on a prediction, but deduced from indicia of the multipath available to the positioning server. For example the server can compute, for each gateway, the path loss exponent L, based on the transmission equation:

(31) $\begin{array}{cc}{P}_{\mathrm{TX}}+G_M+G_G-\mathrm{rssi}=L.Math.10{\log }_{10}\frac{4D}{}& \left(4\right)\end{array}$
where P.sub.TX denotes the transmitter's power, G.sub.M the antenna gain at the mobile node, G.sub.G the gain of the antenna at the gateway, rssi the received signal strength, D the distance, and the wavelength. The loss exponent equals 2 in free-space propagation. Its value will be lower than 2 for guided propagation and, quite often, will be higher than 2. L>2 is an indication of an obstruction, the higher the value of L, the larger the obstruction the signal has suffered. Since on average a large obstruction is correlated to higher delay and stronger multipath, high values of L indicate that multipath has taken place, and may prompt a compensation.

(32) Preferably, the value of rssi in formula 4 is an aggregated value: a statistic indicator of several rssi determinations. It can be a mean, a median, a maximum value, or a quantile. Favourable results have been obtained taking rssi.sub.agg equal to the 80.sup.th percentile of the received rssi values, i.e. a value close to the maximum received signal level.

(33) The exact function used to compensate the t.sub.i may assume different forms, and may be chosen in consideration of the environment around a specific gateway, or mobile node. It has been found advantageous to compensate only those propagation times t.sub.i for which the corresponding loss exponent is larger a given exponent, for example compute a compensation only when L4, and zero compensation when L<4.

(34) The iterative method above foresees at least two, possibly more, estimation of the position. These can be obtained with the rang-free estimate method of the prior embodiments but, in independent aspects of the invention, one all or some position estimates could be obtained otherwise, for example by lateration, based on the times of arrival, or any combination of times of arrival and signal strengths.