NL2004070C2 - Method for determining the location of a mobile device, mobile device and system for such method. - Google Patents

Description

Method for determining the location of a mobile device, mobile device and system for such method

The present invention relates a method for 5 determining the location of a mobile device.

The present invention further relates to a mobile device adapted for use in such a method.

The present invention also relates to a system comprising such a mobile device.

10 Tight profit margins and increasing global competition are driving industrial operations to achieve maximum efficiencies. This level of performance requires optimal orchestration of human and material resources, ensuring that the right personnel, equipment, and raw 15 materials are in the right place at the right time. Today the systems have evolved into real-time location systems (RTLS) that bring the function of resource tracking to the forefront. These systems can use a range of wireless technologies to deliver industrial RTLS functionality. Even 20 though RTLS systems exist, no system has been able to breakthrough in a wider application domain because all of them have some (or many) shortcomings. The requirements differ a lot, and with existing technology only compromises can be reached. These facts coupled with the worldwide 25 deployment of wireless networks in recent years, has made localization research in wireless networks a popular field of research. Many of these localization systems are based on Received Signal Strength (RSS) measurements, because in most existing wireless networks RSS information can be obtained 30 with no additional hardware and energy costs. Other localization systems use techniques like Time Difference Of Arrival (TDOA), Time Of Flight(TOF), Ultra Wide Band(UWB) and Angle of Arrival(AOA). In general, these techniques are more 2 accurate than RSS-based localization, but require specialized hardware and more energy. Therefore, RSS-based localization is still an active and popular field of research. In this patent we focus on RSS-based localization, 5 nevertheless the localization approaches described in this patent are also applicable in conjunction with other localization techniques like TDOA, TOF and UWB.

We distinguish three RSS-based localization methodologies for processing the signal strength measurements for 10 localization. These localization methodologies are fingerprinting, range-based and range-free localization.

Most existing RSS-based localization systems make use of fingerprinting, first proposed by [RAD00]. Fingerprinting requires a predeployment phase in which the 15 signal strength is recorded to stationary infrastructure nodes at several locations. The recorded measurements, taken at a particular position, represent the fingerprint of that particular position. So the localization area is divided into a large set of positions and associated fingerprints.

20 Localization is done by finding the closest match in the database of fingerprints. This means that the RSS measurements are directly used for estimating the position of the nodes, fingerprinting achieves a relatively high accuracy in indoor environments. This is logical because it 25 copes with walls and other sources of noise that are common in indoor environments. The main disadvantage is that this approach requires an excessive amount of measurements in the predeployment phase. Note that the required number of measurements increases with the size of the localization 30 area and required localization accuracy.

RSS- and range-based localization algorithms assume that the signal strength decay over distance follows a distribution that is known beforehand. This distribution 3 is used for converting one or several signal strength measurements into distance estimates. Empirical studies show that the environment has a significant influence on the RSS and therefore on aforementioned distribution ([RAP96]).

5 Therefore, most distributions include several parameters that try to capture aforementioned influence of the environment. Most existing algorithms assume that the optimal value for these environmental parameters are known beforehand (as in [EP601]) or are calibrated by performing 10 measurements before deployment ([PAT01], [DWM06], [PRB03] and [PRBO 7]). The value of these environmental parameters determines how well the choosen distribution fits reality.

It is logical that the performance of range-based localizations depends on the goodness of fit of 15 aforementioned statistical distribution. The main advantage of range-based localization over fingerprinting is that it requires significantly less measurements before deployment than fingerprinting.

Range-free localization approaches use radio 20 connectivity ([DVH01], [AMO03], [MOB04] and [ENH04]) or proximity information ([PIT03] and [ROC04]). Existing localization algorithms based on radio connectivity assume that the transmission range ([MOB04]) or the deployment distribution is uniform and known beforehand ([DVH01], 25 [AMO03] and [ENH04]) . This means that the performance depends on the difference between the expected and real values of the transmission range and deployment distribution. Moreover, radio connectivity information is just a quantization of signal strength measurements. It is 30 logical that this quantization decreases the localization accuracy compared to using unquantized signal strength measurements. Theoretical studies also support aforementioned statement ([PAT05]).

4

Proximity based localization algorithms only assume that the signal strength decays over distance ([ECO05], [PIT03], [ROC04] and [US735] ) . The main difference with range-based algorithms is that they only use the order 5 of RSS measurements. Therefore, proximity based localization algorithms do not require any measurements before deployment at the cost that range-based algorithms outperform proximity based algorithms when the signal strength over distance distribution fits reality.

10 The main disadvantage of existing localization approaches is that the performance depends on measurements before deployment in order to calibrate the localization system (as in [US849], [EP328], [US442], [US572]). The problem is that these measurements only represent a snapshot 15 of the localization environment. This means that existing localization algorithms assume that the conditions during the measurements do not significantly change over time.

These conditions can be environment related like humidity, temperature and moving objects. Moreover, these conditions 20 also include the orientation and directionality of the antenna. It is known that these conditions have a large influence on the RSS and are therefore inherent to RSS-based localization. This means that most existing localization algorithms are not well suited in dynamic environments.

25 Aforementioned problems can partly be solved by deploying a dense localization infrastructure and periodically performing online (as in [US371] and [W0738]) and/or offline calibration measurements. These solutions significantly increase the energy, deployment and maintenance costs of a 30 RTLS. Note that these solutions only take the changing environment conditions into account. The calibration problem still exists for parameters that significantly change every 5 time the node locates itself like the orientation of the antenna.

In this patent we focus on realtime autocalibration of these parameters in range-based 5 localization algorithms, which is a solution of aforementioned problem. This boils down to the calibration of parameters on the basis of localization measurements instead of separate calibration measurements. With respect to localization, we are not directly interested in the 10 values of these parameters. Therefore, these parameters are called nuisance parameters. The idea of autocalibration of nuisance parameters is not new, also in the field of RSS-and range-based localization ([GUS08]). The disadvantage of this approach is that it estimates more unknowns, while 15 processing the same amount of measurements. Moreover, increasing the number of unknowns also changes the performance of an estimator. Altogether, increasing the number of autocalibrated nuisance parameters comes at a cost. This patent combines the autocalibration of nuisance 20 parameters and making an educated guess of the value of a nuisance parameter, instead of autocalibrating all nuisance parameters as in [GUS08]. Compared to existing localization approaches, our invention decreases the energy, deployment and maintenance costs significantly. Moreover, our invention 25 outperforms [GUS08] in terms of localization accuracy and reliability.

The present invention provides a method for determining the location of a mobile device, comprising the steps of: receiving from at least two reference stations a 30 wirelessly transmitted signal, the location of the reference stations being known, wherein the signal is influenced by at least one parameter; determining at least one property of the received signal; determining an educated guess for at 6 least one of the influencing parameters; estimating the at least one influencing parameters based on the at least one determined property and the at least one guessed, influencing parameter; estimating the distances to the at 5 least two reference stations based on the at least one determined property and the at least one estimated, influencing parameter; and determining the position of the mobile device based on the distances to the at least two reference stations. The educated guess serves as an initial 10 value for an estimator being used to estimate the influencing parameter. The educated guess may be provided by some further algorithm, it may be some predetermined value that has been determined to be a suitable value for a representative set of the possible circumstances, or it may 15 even be some random initial value, although the later might result in either more computational effort to reach a sufficiently accurate estimation, or a less accurate estimation.

This method comprises two estimating steps. The 20 person skilled in the art will naturally understand that these steps do not necessarily need to be two distinct steps, but, in a preferred embodiment of the present invention, are combined in a single estimating step that estimates the distances to the at least two reference 25 stations, only producing the estimated, influencing parameter as a by-product, which may be used in a further method as the educated guess in a subsequent estimation to determine an updated position based upon a next determined value of the at least one property.

30 In a further embodiment, the optimizer is also provided with a set of constraints, the constraints describing some prior knowledge of the system. For example, the signal strength diminishes with the distance to the 7 transmitter, or in other words, the path loss exponent is positive. By providing the optimiser with the condition that the path loss exponent is strictly positive, the accuracy of the estimation can be improved.

5 In another aspect according to the present invention a method is provided, wherein the determined properties of the received signal comprise at least one of: the Received Signal Strength, RSS; the Time Difference of Arrival, TDoA; the Time of Flight, ToF; and the Angle of 10 Arrival, AoA.

If the signal strength of the reference stations is (at least approximately) known at some location, for example a previous location of the mobile device, or the location of the reference station itself, the distance to 15 the reference stations can be derived from the Received

Signal Strength based on the knowledge that the transmitted signal attenuates quadraticly with the distance travelled. Depending on further knowledge of the possible locations of the mobile device, two or three reference stations are 20 required to determine the location of the mobile device.

Alternatively, if the delay (which might be zero) is known between the transmissions of two reference stations, the possible locations of the mobile station can be reduced to a hyperbolic line based on the Time Difference 25 of the Arrival of the transmitted messages. If another pair of reference stations is used (which requires a total of at least three reference stations), the intersection of the two hyperbolic lines specifies the location of the mobile device .

30 Furthermore, by making use of the Time of Flight, it is again possible to derive the distance from the reference stations. To get more accurate results more or less fixed time lags can be taken into account, for example 8 a time lag due to decoding of the received signal and processing of the received message. In order to use the Time of Flight, some form of syncing the clock of the mobile device to the reference stations is needed.

5 In a further alternative the Angle of Arrival of the signal is used to determine the location. Either the mobile device determines the angle between at least three reference stations to determine its location, or the Angle of Arrival of two reference stations in combination with the 10 orientation of the mobile device. Alternatively, the reference stations measure the Angle of Arrival of the signal from the mobile device. In this case, only two reference stations are needed to determine the location.

According to another aspect of the present 15 invention a method is provided, wherein the at least one influencing parameter comprises at least one of: the path loss exponent; the transmission power; the antenna orientation; the antenna gain; the temperature; and the humidity.

20 In one embodiment, the present invention provides a mobile device comprising: a receiver for receiving a wirelessly transmitted signal from at least two reference stations with known location, wherein the signal is influenced by at least one parameter; received signal 25 evaluation means, connected to the receiver, for determining at least one property of the received signal; guessing means for determining an educated guess for at least one of the influencing parameters; a parameter estimator, connected to the received signal evaluation means and the guessing means, 30 for determining an estimate of the influencing parameter based on the determined property and the guessed, influencing parameter; a distance estimator, connected to the received signal evaluation means and the parameter 9 estimator, for estimating the distances to the at least two reference stations based on the at least one determined property and the at least one estimated, influencing parameter; and location determination means for determining 5 the location of the device based on the distances to the at least two reference stations, the location determination means being connected to the distance estimator.

The above embodiment comprises two estimators, the parameter estimator and the distance estimator. The person 10 skilled in the art will naturally understand that these estimators do not necessarily need to be two distinct estimators, but, in a preferred embodiment of the present invention, are combined in a single estimator that estimates the distances to the at least two reference stations, only 15 producing the estimated, influencing parameter as a byproduct .

In a further embodiment, a mobile device is provided, wherein the received signal evaluation means determine at least one of: the Received Signal Strength, 20 RSS; the Time Difference of Arrival, TDoA; the Time of Flight, ToF; and the Angle of Arrival, AoA.

In another embodiment, the present invention provides a mobile device, wherein the at least one parameter comprises at least one of: the path loss exponent; the 25 transmission power; the antenna orientation; the antenna gain; the temperature; and the humidity.

The present invention also provides a system for determining the location of a mobile device, comprising: at least two reference stations comprising a transmitter; and a 30 mobile device according to the present invention.

FIG. 1 is a reprentation of a wireless localization network. It also shows the relations between the wireless entities.

10 FIG. 2 is a flowchart of the new localization method.

FIG. 3 is a flowchart of the new localization method.

5 FIG. 4 is a flowchart of the existing localization method.

FIG. 5 is a flowchart autocalibrating the path loss exponent on the basis of one or several signal strength measurements using the new localization method.

10 FIG. 6 is a flowchart autocalibrating the transmission power and/or antenna orientation and gain on the basis of one or several signal strength measurements using the new localization method.

FIG. 7 is a flowchart autocalibrating additive 15 external factors on the basis of one or several TOF measurements using the new localization method.

FIG. 8 is a flowchart autocalibrating multiplicative external factors on the basis of one or several TOF measurements using the new localization method. 20 FIG. 9 is a flowchart autocalibrating additive and multiplicative external factors on the basis of one or several TOF measurements using the new localization method.

System 300 in FIG 1 represents a wireless localization network. System 300 includes infrastructure 25 nodes 301, 302, 303, 304, 305, 306 and a node 307 that locates itself on the basis of several distance measurements 308, 309, 310, 311, 312, 313 to infrastructure nodes. Throughout this patent we name nodes like node 307 that position themselves: blind nodes. In the wireless 30 localization network 300 the blind node and/or the infrastructure nodes measure the distance to each other. These distance measurements are processed in order to estimate the position of the blind node.

11 FIG 4 shows a flow diagram of method 200 of the localization method described in the prior art section. This method distinguishes two phases, namely the calibration phase 205 and the localization phase 206. The main 5 difference between these phases is the purpose of the measurements. In the localization phase the measurements are at least used for localization. In the calibration phase the measurements are used for anything except localization. The calibration phase 205 is a phase that calibrates the 10 required nuisance parameters 202. Aforementioned phase consists of performing calibration measurements 203 and on the basis of these measurements this approach calibrates the nuisance parameters 204 and outputs nuisance parameter values 225. Aforementioned calibrated values of the nuisance 15 parameters are used as input for the localization phase 206. In the localization phase 206, the blind node and/or the infrastructure nodes first perform localization measurements 102 as described in system 300. The distances are estimated 104 on the basis of these measurements 102 and calibrated 20 nuisance parameters 225. The localization algorithm 105 estimates the position on the basis of the distance estimates 104. The localization algorithm 105 could also evaluate other input 106, like inertial measurements. The striped lines indicate that this is optional.

25 FIG 2 shows a flow diagram of the method 100 of the new localization method. In the localization phase 101, the blind node and/or the infrastructure nodes first perform localization measurements 102 as described in system 300. On the basis of these measurements and educated guess 108 on 30 the value of a specified set of nuisance parameters, the new localization method calibrates a specified set of nuisance parameters 103. The distances 104 are estimated on the basis of the measurements 102 and calibrated nuisance parameters 12 103. The localization algorithm 105 estimates the position on the basis of the distance estimates 104. The localization algorithm 105 could also evaluate other input 106. The position estimate of the localization algorithm provides 5 input 107 for the (re-)calibration of the nuisance parameters 103. Method 110 represents the autocalibration of the nuisance parameters. Although, the representation of method 110 may seem to indicate that the autocalibration of nuisance parameters is an iterative process. Method 110 only 10 indicates that the autocalibration of the nuisance parameters is based on the localization measurements.

The proposed method can use any estimator for estimating the position by processing aforementioned information. So method 100 is independent of the used 15 estimator. The current implementation uses the Gauss-Newton Method as the estimator.

FIG 3 represents processes 103, 104, 105 and 107 as one block and therefore supports aforementioned statement.

20 A fundamental difference with prior art is that our invention combines the autocalibration and the use of educated guesses on nuisance parameters. Educational guesses differ in their foundations. Foundations of educational guesses are but are not limited to: 25 - Theoretical studies - Empirical studies

The following section contains several embodiments of the invention. Embodiments of the invention are but are not limited to: 30 - FIG. 5 represents a localization algorithm that autocalibrates the path loss exponent 132 on the basis of at least one or several signal strength measurements 131. The 13 values of one or more nuisance parameters are based on educational guesses 108.

- FIG. 6 represents a localization algorithm that autocalibrates the transmission power and/or orientation and 5 gain of antenna 142 on the basis of at least one or several signal strength measurements 141. The values of one ore more nuisance parameters are based on educational guesses 108.

- FIG. 7 represents a localization algorithm that autocalibrates the additive external factors 152 on the 10 basis of at least one or several TOF measurements 151. The values of zero or more nuisance parameters are based on educational guesses 108.

- FIG. 8 represents a localization algorithm that autocalibrates the multiplicative external factors 162 on 15 the basis of at least one or several TOF measurements 161. The values of zero or more nuisance parameters are based on educational guesses 108.

- FIG. 9 represents a localization algorithm that autocalibrates the additive and multiplicative external 20 factors 172 on the basis of at least one or several TOF measurements 171. The values of zero or more nuisance parameters are based on educational guesses 108.

As an example, we provide a detailed description of a possible implementation of the system shown by FIG. 5. 25 This implementation autocalibrates the path loss exponent by including it in the Maximum Likelihood Estimator.

maXq={Z,y,n} Y' n) ( 1 ) 30 Here y) represent the position estimate of a node; n represents the path loss exponent. Y(x, y, n) represents the maximum likelihood expression that depends on 0 = {Sr Yr -°} . As mentioned before, the maximum likelihood 14 expression could be maximized by any estimator like the Gauss-Newton Method. The rest of the parameters are estimated with educated guesses.

While the present invention has been described 5 with reference to preferred embodiments, those skilled in the art will recognize that various modifications may be made. Variations upon and modifications to the preferred embodiment are provided by the present invention, which is limited only by the appended claims.

15

References [PAT01] N.Patwari, R.J.O'Dea, Y.Wang: Relative Location in Wireless Networks. Presented at IEEE Vehicular Technology 5 Conference, Spring, Rhodes, Greece, May 2001.

[DWM06] J.A.Costa, N.Patwari, A.0.Hero: Distributed Weighted Multidimensional Scaling for Node Localization in Sensor Networks. ACM Transactions on Sensor Networks, Feb.

10 2006, vol. 2, no. 1, pp. 39-64.

[PIT03] T.He, C.Huang, B.M.Blum, J.Stankovic, T.Abdelzaher: Range-free localization schemes for large scale sensor networks. MobiCom, San Diego, California, 15 September 2003, pp. 81-95.

[HAS93] Hashemi H.: The indoor radio propagation channel,

Proc. IEEE, July 1993, pp. 943- 996.

20 [RAP96] Rappaport T.S., Wireless Communication: Principles and Practice, Prentice Hall, ISBN 013 3755633, 1996.

[PRB03] V. Ramadurai and M. L. Sichitiu: Localization in wireless sensor networks: A probabilistic approach, in Proc. 25 of the 2003 International Conference on Wireless Networks (ICWN 2003), Las Vegas, NV, June 2003, pp. 275-281.

[PRB07] Rong Peng, Mihail L. Sichitiu: Probabilistic Localization for Outdoor Wireless Sensor Networks. ACM 30 SIGMOBILE Mobile Computing and Communications, Volume 11, Issue 1, January 2007, pp. 53-64.

16 [MCS03] K.Whitehouse, D.Culler: Macro-Calibration in Sensor/Actuator Networks. Mobile Networks and. Applications Journal (MONET), Special Issue on Wireless Sensor Networks, ACM Press, June, 2003.

5 [PER07] K.Whitehouse, C.Karlof, D.Culler: A Practical Evaluation of Radio Signal Strength for Ranging-based Localization. Mobile Computing and Communications Review, Volume 11, Number 1, 2007.

10 [PAT03] N. Patwari, A.O. Hero, M.Perkins, N.S.Correal, R.J.O'Dea: Relative Location Estimation in Wireless Sensor Networks. IEEE Transactions on Signal Processing, special issue on Signal Processing in Networks, vol. 51, no. 8, 15 August 2003, pp. 2137-2148.

[PAT06] Signal Strength Localization Bounds in Ad Hoc and Sensor Networks when Transmit Powers are Random Patwari, N.; Hero, A.O. Sensor Array and Multichannel Processing, 2006.

20 Fourth IEEE Workshop on Volume , Issue , 12-14 July 2006 Page(s): 299 - 303.

[MAL07] R.A.Malaney: Nuisance Parameters and Location Accuracy in Log-Normal Fading Models. IEEE Transactions on 25 Wireless Communications, March 2007, Volume: 6, page(s): 937-947 [GUS08] F.Gustafsson, F.Gunnarsson: Localization based on observations linear in log range. IFAC World Congress, 30 Seoul, 2008.

[ECO05] K. Yedavalli, B. Krishnamachari, S. Ravula, and B. Srinivasan: Ecolocation: A sequence based technique for RF- 17 only localization in wireless sensor networks. IEEE IPSN 2005, April 2005.

[ROC04] C. Liu, K. Wu, and T. He: Sensor localization with 5 ring overlapping based on comparison of received signal strength indicator. IEEE Mobile Ad-hoc and Sensor Systems (MASS), Oct. 2004.

[RAD00] P. Bahl and V. N. Padmanabhan: RADAR: An in-10 building RF-based user location and tracking system. INFOCOM 2000, pages 775-784, March 2000.

[DVH01] D.Niculescu, B.Nath: Ad hoc positioning systems. IEEE Globecom 2001, San Antonio. 2001.

15 [AMO03] R.Nagpal, H.Shrobe, J.Bachrach: Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. 2nd International Workshop on Information Processing in Sensor Networks (IPSN). April 2003.

20 [MOB04] L.Hu, D.Evans: Localization for Mobile Sensor Networks. Tenth Annual International Conference on Mobile Computing and Networking (MobiCom 2004), USA. 2004.

25 [ENH04] S.Dulman, P.Havinga: Statistically enhanced localization schemes for randomly deployed wireless sensor networks. DEST International Workshop on Signal Processing for Sensor Networks, Australia. 2004.

30 [PAT05] N. Patwari: Location estimation in sensor networks. Phd thesis. 2005.

[US849] Publication number: US2006176849 and EP1689126 18 [EP328] Publication number: EP1575328 [US442] Publication number: US2005176442 and EP1575325 5 [US572] Publication number: US2007117572 [US371] Publication number: US2009154371 10 [W0738] Publication number: W02007056738 [US735] Publication number: US2007111735 [EP601] Publication number: EP1617601 15

Claims (8)

A method according to claim 1, wherein when estimating at least one of the influencing parameters a set of conditions is included, which conditions describe known knowledge of the system. Method according to claim 1 or 2, wherein the determined properties of the received signal comprise at least one of: - the received signal strengths, RSS; - the time difference of arrival, TDoA; - the flight time, ToF; and - the angle of arrival, AoA. Method according to claim 1, 2 or 3, wherein the at least one influencing parameter comprises at least one of: - the path loss exponent; - the transmission power; 10. the antenna orientation; - the antenna gain; - the temperature; and - the humidity. A mobile device comprising: - a receiver for receiving a wirelessly transmitted signal from at least two reference stations with a known location, the signal being influenced by at least one parameter; 20. receive signal evaluation means, connected to the receiver, for determining at least one property of the received signal; - guessing means for determining a well-founded guess of at least one of the influencing parameters; 25. a parameter estimator associated with the receive signal evaluation means and the guessing means for determining an estimate of the influencing parameter based on the determined property and the fermented influencing parameter; 30. a distance estimator, connected to the receive signal evaluation means and the parameter estimator, for estimating the distances to the at least two reference stations based on the at least one particular property and the at least one estimated influencing parameter; and - location determining means for determining the location of the device, based on the distances to the at least two reference stations, wherein the location determining means are connected to the distance estimator. Mobile device according to claim 5, wherein the parameter estimator is provided with a set of conditions, which conditions describe known knowledge of the system, and which conditions are included in the estimation of the estimator. Mobile device according to claim 5 or 6, wherein the received signal evaluation means determine at least one of: - the received signal strength, RSS; - the time difference of arrival, TDoA; 20. the flight time, ToF; and - the angle of arrival, AoA. 8. Mobile device as claimed in claim 5, 6 or 7, wherein the at least one parameter comprises at least one of: - the path loss exponent; - the transmission power; - the antenna orientation; - the antenna gain; 30. the temperature; and - the humidity. A system for determining the location of a mobile device, comprising: - at least two reference stations comprising a transmitter; and 5. a mobile device according to any of claims 5-8.