POSITIONING SYSTEM AND METHOD

DESCRIPTION

POSITIONING SYSTEM AND METHOD

The invention relates to a system, method, tracking unit and computer program for use in positioning.

In general, positioning systems use a plurality of transmitters to determine the position of a mobile unit. For example, to determine three dimensional position there are at least three unknowns, namely the position in the x, y, and z directions. The position of a mobile unit may be determined by sending ranging signals from a number of transmitters and calculating the time of flight from the transmitter to the mobile unit. Since the internal clock of the ranging unit may also have an unknown offset, there are four unknowns to be determined (x, y, z and offset) and so ranging signals from four transmitters are needed to determine the four unknowns.

The Global Positioning Satellite (GPS) system is of this type, using ranging signals from at least four satellites to determine the location of a mobile unit on the earth. Likewise, indoor positioning systems have been proposed in which the position of a receiver is calculated using radio frequency (RF) signal strength. RF signals are received from several base stations, the received signal strength is converted into a range measurement using a knowledge of the propagation environment and trilateration performed to calculate location. Trilateration is a well known mathematical technique that uses distances from known points to calculate location. Trilateration is closely related to triangulation, though the latter uses angles instead of the distances used by the former.

The most widely known example of such an indoor positioning system is the system designed by Microsoft known as RADAR which uses a combination of trilateration and pattern matching of the signal strengths with a database of measured values. RADAR is described in "RADAR: an in-building RF-based user location and tracking system", Bahl et al, Proceedings of INFOCOM 2000, Tel Aviv, March 2000.

However, in indoor applications to position a mobile unit within a room or building it can be very inconvenient to provide a large number of transmitters and the infrastructure needed to link them. Accordingly such systems are not particularly suitable and there therefore remains a need for a positioning system that can work with a fewer transmitters than would otherwise be needed.

According to the invention there is provided a positioning method for tracking a target in an environment including first and second walls, the positioning method including: positioning a tracking unit having a transceiver and a processor in an initial position in the vicinity of both the first and second walls; receiving in the tracking unit a ranging signal from a transmitter on the target, the ranging signal including a direct signal component traveling directly from the target to the tracking unit and indirect signal components reflected off a plurality of reflectors including the first and second walls; calculating estimates of estimation parameters corresponding to the signal components, wherein the estimation parameters are the perpendicular distances of the tracking unit to the respective reflectors or the angles of the direct signal component with respect to the perpendicular to the respective reflectors; identifying the indirect components corresponding to the first and second walls from the estimation parameters; continuing to receive signals from the transmitter on the target; and tracking the estimation parameters to track the indirect components reflected off the first and second walls.

In preferred embodiments, the estimation parameters are the distances of the tracking unit to the respective reflectors. These distances change relatively slowly with time. Alternatively, the estimation parameters are the angles of the direct line of sight signal with respect to the reflectors. These angles too may change slowly and smoothly from their initial estimates.

The method is intended for use indoors, but may also be used elsewhere where suitable straight walls are available. The invention allows a position measurement to be taken using a single signal transmitted from a single transmitter to a receiver and accordingly removes the need for triangulation or trilateration to a plurality of base stations.

A significant difficulty is to identify the components of the arriving signal that come from the first and second walls, given that a receiver will receive a great many reflections from tables, people, chairs, and any other object in the room.

In the invention, this difficulty is solved by starting with the receiver in the vicinity of the first and second walls, i.e. in the corner near these walls, at which point the signal components reflected off the walls will in general be both large compared with other reflected signal components and, more significantly still, will arrive with less delay than signal components reflected off more distant reflectors. Thus, identification of signal components is relatively straightforward. The exact starting position is not critical - all that is required is that the tracking unit is in the vicinity of the walls, i.e. closer to the first and second walls than to other comparable, significant, reflectors. As each wall must be individually identified, the user must stand closer to one wall than the other or the user can stand anywhere and a tracking unit at an exactly known position with respect to both walls can relay pictorial information of the position to the mobile user.

The tracking unit then tracks the corresponding signal components, for example as the tracking unit is moved around a room or the tracking unit is stationary and the mobile user obtains pictorial information of the position of the target in the room. In this way, the method may continue to track the target even with the tracking unit in the middle of the room receiving a confusing number of signals from the various walls and contents of a room. The tracking may be carried out using a Kalman filter using an estimator.

The step of calculating estimates of estimation parameters may include identifying distances Dj,D₂ from the set {D ... D_K ) and/or angles φ_} and #>₂ from the set {φ_l ...φ_κ } arising from the estimator equation:

wherein:

N is the number of sample points; ψ_k is the angle of the direct signal component with respect to the perpendicular to the¹ reflector, where £=0 corresponds to the direct path and £=1 ,2 ... n correspond to the paths reflected once off the first, second ... «* walls respectively;

D_k is the perpendicular distance of the tracking unit from the l reflector; the received, mixed-down correlation function is given byR(r)such that R(τ_n) = R„ is the «^Λ sample point of the data R(_r) ; the correlation function C(T) is given by:

Rft is a unit triangle of base two times the chip width 2T_C and a_k is the value of the height of the triangle such that C„ = C(Tη) is the value of the sample point yielded by the model in Equation (2); and

It is the distance travelled by the ranging signal received via the A"¹ path, given by

= ~^dl +⁴ A cos^ + D_k² (3) c where c is the speed of light; and θ_k is the phase of the ranging signal received by the k^th path.

It will be appreciated that equivalent forms of these equations may be used. For example, the distance may be replaced by equivalent delay time using the well-known relationship d=ct, where d is distance and t the corresponding delay time.

The direction of the direct signal is estimated by using the signal received from the target (ranging signal) with the parameter estimator in Equation (1) for the angle of arrival of the LOS signal with respect to all the reflectors of the ranging signal. The ranging signal must contain the LOS and at least reflections off two perpendicular adjoining walls. The user must stand at some known position with respect to each of these walls or in the corner closer to one wall than the other. The direction is measured with respect to the first and second walls, i.e. with respect to the room, a much more useful local reference frame than an absolute direction with respect to true north. The method according to the invention gives this direction directly.

Preferably, both the direction of the direct signal component and the distance between target and tracking unit are calculated.

The direction is conveniently represented by the angles of the incoming direct signal component with respect to the perpendiculars to the first and second walls. By obtaining the angles of arrival with respect to the perpendicular direction to each of the two walls, the angle in three dimensions can be calculated, i.e. the angle of the target both horizontally and vertically.

The calculated angles are updated using the perpendicular distances of the tracker to the first and second walls estimated from the ranging signal without remeasuring the distances to the first and second walls. This is possible as the new values of the perpendicular distances should change slowly and smoothly over time from their initial values. Alternatively, the angle of arrival or direction could be updated by tracking the new estimates of the angels from their initial values.

Preferably, the method may further include displaying on a graphical display the first and second walls and a graphical indication of the angles to the first and second walls, for example an arrow pointing to the target. In this way the user of the tracking unit may be guided towards the target or the tracking unit is stationary and relays pictorial information of the room to the mobile personal digital assistant (PDA).

The target may be, for example, a set of keys such as car keys and the user may have a PDA arranged as the tracking unit to find the user's keys. Other applications include locating components, individuals or tools in a factory, office or warehouse environment.

The initial measurement of the distance to the first and second walls may be carried out in any of a number of ways. For example, the method may include: positioning the tracking unit close to and spaced away from a corner of a room having first and second walls, closer to the first wall than the second wall; transmitting a signal from the tracking unit; receiving the reflections of the signal of at least the first and second walls; measuring first and second times of flight of the signal reflecting off the first and second walls respectively; and calculating the distance of the tracking unit to the first wall and the distance of the tracking unit to the second wall from the measured times of flight.

An alternative possibility is to have a predetermined start location, an orientation marked out in the room at known measured distances from the first and second walls, and to start the tracking from this known location. In this case, the measuring step can take place in advance. In another aspect, the invention relates to a tracking unit arranged to track a target having a transmitter in an indoor environment with at least first and second walls, the tracking unit comprising: a transceiver; and a processing unit; wherein the transceiver is arranged to receive a signal from a transmitter on the target including a direct signal component traveling directly from the target to the tracking unit and indirect signal components reflected off at least one wall and to continue to receive signals from the transmitter on the target; and the processing unit is arranged: to calculate estimates of estimation parameters corresponding to the signal components, wherein the estimation parameters are the perpendicular distances the tracking unit to the respective reflectors or the angles of the direct signal component with respect to the perpendicular to the respective reflectors; to identify the indirect components corresponding to the first and second walls from the estimation parameters; to continue to receive signals from the transmitter on the target; and to track the estimation parameters to track the indirect components reflected off the first and second walls.

The tracking unit may include a display, and may be arranged to display the first and second walls and a graphical indication of the direction to the target with respect to the first and second walls.

The processing unit may be arranged to identify the distances Dj and D₂ from the reflection off the first and second walls from the tracker; and to implement a Kalman filter for tracking the value of these estimated distances D and E>₂ as the signals are continued to be received in order to continually track the angles of arrival as the tracker moves.

Note that the tracker could be stationary and the user mobile.

In another aspect, the invention relates to a system including a tracking unit as set out above and a target including a transmitter for transmitting a signal to the tracking unit.

The invention also relates to a computer program for carrying out the steps of a method as set out above.

For a better understanding, embodiments of the invention will now be described, purely by way of example, with reference to the accompanying drawings, in which: Figure 1 shows a system according to a first embodiment of the invention;

Figure 2 is a flow diagram of the operation of the system shown in Figure 1 ; and

Figure 3 is an example of the display on the tracking unit.

Figure 4 is a flow diagram of the operation of a second embodiment of the invention; and

Figure 5 is a flow diagram of the operation of a third embodiment of the invention.

Referring to Figure 1 , a tracking unit 10 includes a transceiver 12 and antenna 14 as well as processor 16. The tracking unit in the embodiment is a personal digital assistant (PDA) type device having a display 11. A target 20 includes a target transceiver 22 and a target antenna 24. The tracking unit 10 is shown in the corner of a room having a first wall

1 and a second wall 2 arranged at right angles. The tracking unit is closer to the first wall 1 than the second wall 2. Figure 1 also shows the distances Dj and E>₂ of the tracking unit to the first and second walls respectively, measured perpendicularly to the walls, and angles φj and φ₂ which are the angles between the direct path between the target and tracking unit and the perpendicular direction 3, 4 to the first and second walls respectively. Note that although the Figure shows these angles only in the plane of the paper, the angles ψi and ^₂may be in any orientation to the perpendicular directions 3, 4.

The processor 16 includes code stored in a memory (not shown) for causing the processor to carry out the steps set out below and shown in the flow diagram of Figure 2, in a manner known to those skilled in the art.

In use, the tracking unit is first (step 30) positioned in a corner of the room as shown, closer to one of the walls, the first wall 1 , than another, the second wall 2. In the example, the user stands with his back to the first wall 1 and with the second wall 2 on the left. This allows the tracking unit to display the room correctly oriented on the display 11. In preferred embodiments, the PDA can accept a user input to toggle between a number of modes, to correspond to different orientations. For example, in a rectangular room, in one mode the initial position is with the user standing with the shortest wall behind him and a long wall on the user's left, and in another mode the initial position may be with the user standing with a long wall behind him and with a short wall on his right hand side.

Next, a sounding radio signal is transmitted (step 32), although in other embodiments it is not necessary, reflected off the first and second walls 1 ,2 and received (step 34) back at the first transceiver 12 where the received sounding signal is passed to the processor 16. These reflections are shown in Figure 1 as R₇ and R₂ respectively.

The processor estimates the delay (step 36) between transmitting the sounding signal and receiving the backscattered reflections Rj, R₂ of the sounding signal from the first and second reflecting walls 1 , 2. The value of each of these delays is denoted Tj and T₂ respectively. The reflections may be detected by correlation of the received sounding signal with a replica of the transmitted sounding signal. The measurement of delays may be assisted, particularly when there is more than one reflected path, by calculating the times at which the second order derivative of the correlation function of the received sounding signal peaks. The processor may receive a number of additional reflections from other walls and contents of the room, but since the user is standing in the corner close to the first and second walls these arrive later and may be discarded. The backscattered signals giving the smallest delays are taken to be those of the nearest walls. From the estimated delays T_} and T₂ the processor 16 estimates the distance (step 38), from the tracking unit 10 to each of the reflecting surfaces; D] = c.Tj and D₂ = c.T₂ where c is the speed of light. These distances are determined perpendicular to the reflecting surface.

The user, by standing with his or her back to the first wall and with the second wall on the left hand side, identifies to the tracking unit 10 the orientation of the user within the room. The reflected signal with the lowest delay, T is known to be the signal bouncing off the rear wall and the reflected signal with the next lowest delay, T₂, is known to be the signal bouncing off the left wall. Thus, the signals corresponding to the different walls are identified.

In the present embodiment, the sounding signal serves a dual purpose. In addition to enabling the distances Di, D₂ to be estimated, the sounding signal is received by the target 20. In response to receiving the sounding signal, the target 20 transmits (step 40) a first radio signal, which in the present specification is referred to as the ranging signal. The ranging signal reaches the tracking unit 10 via at least three paths; a direct path, a reflection off the first wall 1 , and a reflection off the second wall 2. These three paths are denoted P₀, Pi and P respectively in Figure 1. The ranging signal may also reach the tracking unit via further paths, off additional reflectors, not shown in the drawings, which are denoted P₃, P₄ etc.

The processor 16 performs an analysis (step 42) of the received ranging signal in order to calculate the direction of the target 20 from the tracking unit 10. The analysis will be described below in some detail. The direction will be expressed as the angles φi and φ₂ with respect to the first and second perpendicular bisectors. In this calculation step, the signal components and corresponding arrival times of the signal components reflected just once off the first and second walls are identified in the received signal.

As well as the angles, the distance d₀ between target 20 and tracking unit 10 is also determined.

The analysis used in the initial calculation step (and subsequently) comprises generating a mathematical model of the received multipath- corrupted correlation function. This model yields an estimator for the following estimation parameters: the range d₀, the perpendicular distance from tracker to each of the K reflectors {D_x ...D_κ}.a ά, importantly, the angle of arrival of the direct component of the ranging signal with respect to each of the K reflectors {φ ...φ_κ} . If we identify Dj and D₂ for wall 1 and wall 2 we can therefore identify φι and φ₂ and hence the direction of the LOS with respect to the perpendicular adjoining walls. The step of calculating the direction requires the estimator

where the received, mixed-down correlation function data is given byR(r)such that R(T_n) = R„ is the «^th sample point of the data R(τ). The parameter model of the received mixed-down correlation function is

C(T) = ∑_kR(^Jβt (2) k=0 where R(10) is a unit triangle of base double the chip width 2T_C, l_k is the position of the peak of the triangle and a_k is the value of the height of the triangle such that C_n =C(T^ the value of the sample point yielded by the model in Equation (2).

Importantly the peak position of each constituent correlation peak in Equation (2) is given by the form:

where ψ_k is the angle between the LOS component of the ranging signal and the perpendicular bisector of the &^th reflector of the ranging signal.

Using the estimator, via curve fitting, of Equation (1) with Equations (2) and (3), a set of the estimation parameters ...^} along with d₀ and {D_λ,. D_κ }is estimated. In order to determine the direction of the LOS we need to identify ψι and φ₂ with respect to each of the two perpendicular adjoining walls, i.e. we need to identify which of the K received signal components corresponds to the signal components reflected off the first and second walls. From the value of D₃ for wall 1 and the value of D₂ for wall 2 determined above the values of the estimation parameters ψi and φ₂ are calculated. The values for ψι and φ₂ give directly the direction of the LOS signal.

Signals continue to be received from the target 20 on a continuous or repeating basis and are passed to the processing unit. The processor then updates its estimate of the angles ψι and φ₂ without necessarily having to re-measure the distance to the first and second walls. The Kalman filters 18 in the target unit track the values of φ_} and φ₂ which should change slowly and smoothly from their initial values. Thus, the measured signal components with corresponding φ and φ₂ values can be identified as the signal components reflected off the first and second walls can be identified, and the ψj and φ₂ values calculated from these signal components can be used to correct the estimates of ψi and φ₂ to keep the Kalman filter on track. In an alternative version of the first embodiment, the estimation parameters that are tracked are just the perpendicular distances Dj and D₂ to the first and second wall. Since Di and D₂ should change even more slowly over time than φi and φ₂Ms may give an improved result for the tracking of the estimation parameters. The user may walk around, for example towards the target, and as he or she does so the estimate of the angles φ and φ₂ is continually updated. The tracking unit displays (step 44) on its display 1 1 a representation 50, 52 of the first and second walls 1 , 2 and an arrow 54 representing the direction of the target, as illustrated in Figure 3. Thus, the display is continually updated with an indication of the direction to the target.

A key advantage of this approach is that the direction to the target is calculated relative to the walls of the room. This allows the user to accurately orient the tracking unit and easily find the target. An absolute direction relative to due North, for example, would be much less useful in an indoor environment.

When the user leaves the room, he or she knows to start once again from a corner of the new room as before or at a pre-determined spot in the room. This allows the identification of the two adjoining walls of the new room with the corresponding signal components in the new room environment. These signal components are then tracked as before as the user moves around the room. In a variation of the above method, the method only calculates the distances to the closest walls, not to all reflectors identified in the step of receiving back-scattered signals. In this case, the calculation step is still able to calculate the angles and distance, but only using the signals from the paths denoted P₀, Pi and P₂, not any additional paths.

In a second embodiment of the operation of the invention, illustrated in Figure 4, the steps of transmitting a sounding signal, receiving the reflected signal and calculating distances to reflectors are omitted.

Instead, in the calculation step 42 using the received ranging signal, the perpendicular distances from the tracker to the reflectors D and D₂ are obtained from the parameter estimated in Equations (1), (2) and (3). There is still a need to identify each of the closest walls to orient the display. In the second embodiment, the distances to each of the two closest reflectors calculated in calculation step 42 in the initial position close to the corner of two walls are identified (step 43) as the distances to the two walls. The updating of the angles and distance as the tracking unit moves then continues as in the first embodiment.

In a third embodiment as set out in Figure 5, the user starts initially at a known position. The method then proceeds as in the first embodiment, except that the distances to the two nearest walls are known. The calculation in step 36 then merely calculates the distances of other reflectors to the tracking unit from the received back-scattered signal in step 34, which improves the accuracy of angle and distance estimates.

In a variation (not shown) the initial distances to the two nearest walls (D and D₂) known from the known initial position and then the angles ψι and φ₂ are estimated and identified from the values of D and D₂ and the distance calculated from the parameter estimation in step 42 from the ranging signal.

From reading the present disclosure, other variations and modifications will be apparent to persons skilled in the art. Such variations and modifications may involve equivalent and other features which are already known in the design, manufacture and use of tracking systems and which may be used in addition to or instead of features described herein. Although claims have been formulated in this application to particular combinations of features, it should be understood that the scope of disclosure also includes any novel feature or any novel combination of features disclosed herein either explicitly or implicitly or any generalisation thereof, whether or not it mitigates any or all of the same technical problems as does the present invention.