WO2018160141A1 - Apparatus and method for localisation and/or tracking - Google Patents

Abstract

An apparatus and method for localisation and/or tracking is disclosed. The apparatus comprises: a receiver for receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; a computer processor; and a data storage device. The data storage device comprises instructions operative by the computer processor to separate the received signal into the multiple signals by: a)estimating initial path parameters by: estimating a number (L) of signal paths in the received signal; estimating parameters for each signal path using an estimator tool; and deriving an initial background noise; and b) refining the parameters by: i) combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool; ii) re-estimating background noise by re-constructing each signal path using the re-estimated parameters from (i) and subtracting the L re- constructed signal paths from the received signal; and iii) repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria; and using the parameters for each signal path to determine a location and/or motion of a target.

Description

Apparatus and Method for Localisation and/or Tracking

Field of the Invention

[0001] The present invention relates to an apparatus and method for localisation and/or tracking. In particular, the present invention relates to estimation of parameters of indoor wireless signals for localisation and tracking.

Background

[0002] Wireless localisation (e.g. using radio frequency (RF) waves) is a technique which can be employed for actively localising a signal emitter or passively tracking a signal reflector in a propagation environment. In addition, wireless sensing has been used for gesture recognition, human activity recognition and RF imaging. Both areas have a number of important applications including security (e.g. for detecting an intruder to private spaces), elderly care (e.g. generating an alert when an elderly person is behaving abnormally or has fallen down) and retail (e.g. analysing customer behavior in shops).

[0003] Diverse technologies have been proposed for such localisation and tracking including ultrasound, ultra-wideband infrared cameras, and LED visible light. Among these technologies, Wi-Fi based systems stand out as particularly promising due to the pervasive availability of Wi-Fi enabled devices. Billions of Wi-Fi access points (APs) have already been deployed worldwide and almost all mobile devices like cell-phones, tablets, laptops and so on, are equipped with Wi-Fi chipsets. Making use of existing Wi-Fi infrastructures saves the need for designing a dedicated hardware and hence facilitates real-world deployment.

[0004] When transmitted to the physical environment, wireless signals travel along different paths between a transmitter (also referred to as an emitter or a sender) and a receiver. Along each path, the signals can be reflected by a number of objects (i.e. reflectors) located in the propagation environment and hence the signals from each path arrive at the receiver from different angles, at different times, which results in amplitude and phase variations of the received signal. This phenomenon is referred to as a multipath effect.

[0005] The multipath effect links the wireless transmitter, the physical environment and the receiver together. Multipath parameters (e.g. angle-of-arrival (AoA), angle-of- departure (AoD), time-of-flight (ToF), Doppler shift and amplitude) provide essential location and motion information concerning the transmitter, the reflectors in the environment and the receiver. The estimation of these parameters enables many important and innovative applications. A line of sight (LoS) path directly connects the transmitter and the receiver. By estimating the AoA, AoD, or ToF of the LoS path it is possible to localise the transmitter if the location of the receiver is known and vice versa. A reflection path connects the reflectors with the transmitter/receiver pair and allows the localisation of the reflector once the parameters of the reflection path are accurately estimated. A Doppler shift provides information about a radio velocity (i.e. motion) of the transmitter or the reflector with respect to the receiver. Accordingly, motion information together with location information enables applications like human- computer-interaction (e.g. gesture recognition), intruder detection, indoor floor map reconstruction, and so on.

[0006] In order to accurately estimate the above parameters, it is necessary to resolve the signal from each path. The resolvability is, however, determined by the resolution of the communication system. In a typical wireless communication system like Wi-Fi or Long Term Evolution (LTE), channel bandwidth is regulated by the relevant standard. In each of these systems, the most frequently used channel has 20MHz or 10MHz bandwidth, which provides 25ns or 50ns time resolution and results in 7.5m or 15m uncertainty when used for localisation. Similarly, angular (AoA) resolution is determined by a number of receiver antennas employed in the system, which is also limited in a commercial communication system.

[0007] One way to improve the angular resolution limit is to increase the number of antennas, which, however, results in higher hardware costs. Improving ToF resolution is even more difficult as the Wi-Fi standard fixes channel bandwidth and so the total possible bandwidth is only 70 MHz in the 2.4 GHz wireless band. Recent attempts to overcome these limitations include virtual antenna arrays and combining adjacent channels to provide a larger bandwidth. However, these methods introduce constraints on the operation of the system such as requiring channel hopping or physically moving the antenna to receive a transmission.

[0008] An alternative approach is to estimate the path parameters without actually resolving the multipath signals. Subspace-based methods, like MUSIC (multiple signal classification), ESPRIT (estimation of signal parameters via rotational invariant techniques), and JADE (Joint Angle and Delay Estimation), have already been widely adopted to estimate channel parameters. Such methods take the received superimposed signal as input and estimate the parameters of multiple paths simultaneously using an Eigen-space method. Reflected signals are, however, much weaker compared with the LoS signal, and so it is challenging to accurately estimate ToF, AoA and Doppler shift of a target's reflected signal in the presence of interference from such a strong direct path and other background noise. Thus, subspace-based methods suffer from interference and can only achieve sub-optimal estimation accuracy.

[0009] There is therefore a need in the art for a technique that can successfully resolve multiple signals from variant propagation paths and at the same time accurately estimate the parameters of those paths from the resolved signal.

[0010] It is therefore an aim of the present invention to provide an improved apparatus and method for localisation and/or tracking that helps to ameliorate one or more of the above problems.

[0011] A number of references detailing further background to the invention are listed at the end of the present description and are referred to throughout.

Summary of the invention

[0012] In accordance with a first aspect of the invention there is provided an apparatus for localisation and/or tracking comprising:

a receiver for receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; a computer processor; and a data storage device, the data storage device comprising instructions operative by the computer processor to separate the received signal into the multiple signals by: a) estimating initial path parameters comprising:

1. estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise;

b) refining the parameters by: i. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool;

ii. re-estimating background noise by reconstructing each signal path using the re-estimated parameters from (i) and subtracting the L reconstructed signal paths from the received signal; and

i. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria; and

c) using the parameters for each signal path to determine a location and/or motion of a target.

[0013] Thus, embodiments of present invention provide an apparatus for localisation and/or tracking which is able to estimate initial path parameters and refine these parameters using an iterative technique so as to obtain more and more accurate results. The apparatus can be used to resolve each individual signal path and to accurately estimate a number of parameters from the resolved signals.

[0014] Notably, the present apparatus overcomes fundamental accuracy limitations of the prior art such as those dictated by antenna count (for AoA methods) and frequency bandwidth (for ToF methods). Instead, finer resolution is achieved by jointly exploring more properties (i.e. signal dimensions) of the received signal. With multiple signal dimensions jointly estimated, two signals are resolvable if they are resolvable in any individual dimension, which increases the effective system resolution without requiring changing of the resolution in each individual dimension.

[0015] The estimated parameters will be used in wireless systems for localisation and/or tracking. Particular applications include security (e.g. for detecting an intruder), elderly care (e.g. generating an alert when an elderly person is behaving abnormally or has fallen down) and retail (e.g. analysing customer behavior in shops).

[0016] The parameters may be multi-dimensional. In some embodiments, the parameters are at least 2-dimensional, at least 3-dimensional or at least 4-dimensional.

[0017] The parameters may be selected from the list comprising: Angle of Arrival (AoA), Angle of Departure (AoD), Time of Flight (ToF), Doppler Shift and Attenuation.

[0018] The estimator tool may employ a maximal likelihood based method. [0019] The estimator tool may be a multi-dimensional estimator comprising one or more of: an AoA estimator, an AoD estimator, a Doppler estimator, a ToF estimator and an amplitude estimator. The estimator tool may estimate the parameters individually or jointly (i.e. together). The estimator tool may jointly estimate the parameters for each signal path in a sequential manner. The estimator tool may be flexible and may be configured to jointly estimate an arbitrary number of parameters.

[0020] The number (L) of signal paths may be derived from a number of peaks in an output signal from the estimator tool.

[0021] The parameters for each signal path may be derived from locations of peaks in an output signal of the estimator tool.

[0022] The initial background noise may be estimated by re-constructing each signal path with the estimated parameters and subtracting the re-constructed signal paths from the received signal.

[0023] In some embodiments, known technologies from information theory [see references 50 and 51] may be employed to estimate the initial path parameters. For example, multiple one dimensional estimator tools may be employed to estimate multidimensional parameters. In particular, a one dimensional multiple signal classification (MUSIC) estimator tool [reference 27] may be employed to estimate AoA and then the estimated AoA may be used to estimate the ToF using another MUSIC estimator tool and so on. Known two dimensional estimators such as SpotFi [reference 17] or Joint Angle and Delay Estimation (JADE) [reference 52] may be used as the estimator tool in some embodiments.

[0024] The receiver may comprise a plurality of antennas and the AoA estimator may comprise a beamformer configured to remove phase differences between signals of a same transmission timeslot arriving at different antennas in the receiver, summing resulting signals and scanning possible incidence angles to determine an angle of incidence generating a maximum beamformer output.

[0025] The AoD estimator may comprise a beamformer configured to apply a phase shift corresponding to possible departure angles to the sum of the resulting signals from the AoA estimator for each transmission time slot, to sum these signals, to determine an angle of departure generating a maximum beamformer output and to remove the applied phase shifts.

[0026] The Doppler estimator may comprise applying different Doppler shifts to an output from the AoD estimator and correlating this signal with the transmitted wireless signal to identify a Doppler shift producing a closest correlation and providing an output signal using the Doppler shift identified.

[0027] The ToF estimator may comprise correlating an output signal from the Doppler estimator with a delayed version of the transmitted wireless signal to determine the ToF.

[0028] The apparatus may apply successive interference cancellation by:

1. treating the received signal as a strongest signal path and estimating one or more parameters of the received signal using the estimator tool;

2. re-constructing the strongest signal path using the estimated parameters and cancelling the re-constructed strongest signal path from the received signal to provide a residual signal; and

3. repeating step (1) and (2) using the residual signal as the received signal until the residual signal has a power below a predefined threshold.

[0029] The number (L) of signal paths may be estimated as the number of the reconstructed strongest signal paths.

[0030] The apparatus according to claim 8 or 9 wherein the initial background noise is estimated by subtracting the L re-constructed strongest signals from the received signal.

[0031] The estimation of more than one parameter may comprise fixing all but one of the parameters and searching for an optimal value for the one parameter.

[0032] The optimum value may be determined using an expectation maximum (EM) model or a generalized expectation maximum (GEM) model.

[0033] The apparatus may be further configured to determine a direct signal path by identifying the signal path with a shortest ToF and/or a highest amplitude and/or a smallest AoA and AoD difference, and to calculate a difference between the ToF of the direct signal path and a ground-truth ToF to determine a synchronization offset and to correct the ToF measurements for all signal paths by the synchronization offset. [0034] The apparatus may be further configured to correct for local oscillator offset.

[0035] The apparatus may be further configured to correct for carrier frequency offset.

[0036] The apparatus may be further configured for passive localisation and tracking and may further comprise a transmitter for transmitting the wireless signal along the plurality of different paths.

[0037] The receiver and the transmitter may be positioned on a ceiling to ensure a direct path between them exists.

[0038] The apparatus may be further configured to detect a reflection signal from a mobile object by identifying a signal with a non-zero Doppler shift and to use the AoA, AoD and ToF to track a motion of the mobile object.

[0039] The apparatus may be further configured for active localisation and tracking wherein a transmitter on the target transmits the wireless signal along the plurality of different paths.

[0040] The apparatus may be further configured to determine a direct signal path by identifying the signal path with a shortest ToF and/or a highest amplitude and/or a smallest AoA and AoD difference, and to localise the transmitter by using the ToF of the direct signal path to estimate a distance between the transmitter and the receiver, and using the AoA of the direct path signal to estimate an angle of the transmitter so as to localise the transmitter.

[0041] The predefined threshold may correspond to a dynamic range of the apparatus.

[0042] The convergence criteria may comprise determining when a difference of each parameter for each signal path between two successive iterations is smaller than a predefined convergence threshold.

[0043] The received signal may be constituted by a Wi-Fi signal.

[0044] In accordance with a second aspect of the invention there is provided a method for localisation and/or tracking comprising: receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; separating the received signal into the multiple signals by: a) estimating initial path parameters by:

1 . estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise;

b) refining the parameters by:

i. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool;

ii. re-estimating background noise by re-constructing each signal path using the re-estimated parameters from (i) and subtracting the L re-constructed signal paths from the received signal; and

ii. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria; and

c) using the parameters for each signal path to determine a location and/or motion of a target.

[0045] The optional features described in relation to the apparatus of the first aspect of the invention also apply to the method of the third aspect of the invention.

[0046] In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of a statistical model given observations Y , by finding the parameter values Θ that maximize the likelihood p(Y| 0) of making the observations given the parameters. MLE has been widely used for many applications involving parameter estimation and expectation-maximising (EM) algorithms represent a type of algorithm believed useful for solving MLE problems. However, EM cannot solve all MLE problems. EM applies to finding MLE of parameters of an underlying distribution from a given data set when the data is incomplete or has missing values. Specifically, EM may be applied if the observed data Y is incomplete and there is some unobservable data set X whose probability distribution function depends on Θ with the property that maximizing p(X|0) is easier than maximizing p(Y|0). Essentially, EM enhances the incomplete data by finding some useful additional information. Technically, X is a variable that Θ→ X→ Y is a Markov chain. For an MLE problem, if a hidden, unobservable and complete variable can be found, an EM algorithm can be used to solve it. However, EM is not a specific algorithm towards solving any specific problem. EM is a general type of algorithm for solving MLE problems. Reference 7 introduces this type of algorithm and demonstrates its convergence. EM provides a high-level guideline for solving such types of problems but does not give any detailed instructions to solve any specific problems like, e.g. estimating the parameters of indoor multipath signals as per embodiments of the present invention.

[0047] Reference 53 proposes a parameter estimation algorithm to estimate parameters using a sub-space based algorithm known as Joint Angle and Delay Estimation (JADE). A sub-space based algorithm is different in design principle from a maximum likelihood estimation based algorithm. Sub-space based algorithms project the received signal into signal sub-space and noise sub-space by performing Eigen analysis on a covariance matrix of the received signal. Parameters that can make the projected signal and noise sub-space orthogonal to each other provide the estimated results. Accordingly, a sub-spaced based algorithm is not an iterative algorithm. On the other hand, the core operations in steps (a) and (b) of the present method, are all iterative operations.

[0048] As indicated by the name (JADE), reference 53 is designed to merely estimate angle (i.e. AoA) and delay (i.e. ToF). The present method, however, is capable of jointly estimating multi-dimensional parameters, i.e., AoA, AoD, ToF, Doppler shift and signal strength for every multipath signal. The present method is also flexible and can be easily tuned to estimate different combinations of parameters (e.g., 1 -Dimensional ToF, 2-Dimensional AoA + ToF, 3-Dimensional AoA + AoD + ToF, 4-Dimensional AoA + AoD + ToF + Doppler, etc.), to cope with different system conditions. Extending sub- spaced based algorithms to higher dimensions results in significant complexity in system modeling and signal processing, which prohibits its practical usage and implementation. That is also the reason why sub-spaced algorithms are successful in one-dimensional cases, like MUSIC and ESPRIT (estimation of signal parameters via rotational invariant techniques) but sub-spaced algorithms are seldom used in estimating more than two parameters. Due to the intrinsic limitation of sub-spaced algorithms, they are not capable of estimating signal strength.

[0049] Interference cancellation [reference 1 1] is a basic signal processing technique to remove interference. If there are multiple interference sources, their impact can be removed successively, which is also referred to as successive interference cancellation (SIC). SIC is widely used to decode multiple colliding packets, as reference 1 1 does. It decodes the strongest packet, re-constructs the signal of the first packets using the decoded bits, cancels the re-constructed signal from the received signal and decodes the second strongest packet until no packet can be decoded.

[0050] Embodiments of the present invention apply SIC to separate the different signal paths, which is different from traditional usage of SIC for packet decoding where different packets are treated as interference to each other. The present method, however, treats the signal of the same packet but from different paths as interference to each other, which has not been studied previously and is different from traditional usage of SIC.

[0051] SIC may be performed in step (a) of the present method. In particular it involves reconstruction of the original signal from the strongest wireless signal path by using the estimated parameters, which is not part of traditional usage of SIC where existing methods use decoded packet data to reconstruct the signal (superimposed signal from multi-path) as a whole. In traditional usage, the reconstruction does not rely on the channel parameters from individual signal paths. Step (a), however, only provides the initial estimates for the present iterative parameter estimation algorithm. The parameter obtained from step (a) is not accurate enough since the estimation error in the strongest path will cause energy leakage into the residual signal, which impacts the estimation of the next signal as explained in more detail below. In the present method, step (b) is performed to use the output from step (a) and iteratively refine the path parameter estimation for more accurate results. Step (b) is not part of SIC and is not involved in any sub-space based algorithms. It is therefore believed that the combination of steps proposed for the present method provides a new and advantageous approach to estimating parameters of indoor wireless signals.

[0052] Applications of embodiments of the invention include but are not limited to indoor Wi-Fi based localisation systems (i.e. for locating active mobile devices like mobile phones or passive localisation systems for locating a reflector (e.g. human body) not carrying an active wireless device. Embodiments of the invention may be employed in a human-computer interface to support applications like gesture recognition, human activity recognition and so on. Some embodiments of the invention may be employed in security systems to detect the intruders. Brief description of the drawings

[0053] Embodiments of the invention will now be described, by way of example only, with reference to the following drawings, in which:

Figure 1 illustrates joint parameter estimation in a) ToF and AoA dimensions and b) ToF, AoA and Doppler shift dimensions in accordance with embodiments of the invention;

Figure 2A shows a schematic diagram of an apparatus for localisation and/or tracking in accordance with embodiments of the invention;

Figure 2B illustrates a method (referred to as mD-Track) for localisation and/or tracking in accordance with embodiments of the present invention;

Figure 3 illustrates a four-dimensional estimator tool in accordance with embodiments of the invention;

Figure 4 shows a signal structure for a Wi-Fi (multiple input and multiple output) Ml MO preamble, as may be employed in embodiments of the invention;

Figure 5 shows an example output (z-function) of the estimator tool with input: (a) superimposed signal of a stronger signal with AoA and ToF [60.7°, 20.8ns] and a weaker signal with [73.4°, 28.1 ns]; (b) the residual signal after cancelling the stronger signal; (c) reconstructed stronger signal and (d) reconstructed weaker signal after three iterations;

Figure 6 shows a framework of an iterative path parameter estimation method in accordance with an embodiment of the invention, for a two signal path (L=2) example;

Figure 7 shows (a) a histogram of absolute ToF of a shortest path and that of a relative ToF between two paths; (b) a cumulative distribution function (CDF) of a ToF error;

Figure 8 shows three transmitter-chains and three receiver-chains connected together with a power splitter/combiner in (a) one transmitter-chain is connected with two receiver-chains and the remaining two transmitter-chains are connected with the other receiver-chains in (b) and (c); Figure 9 shows (a) a general experimental set up in an indoor meeting room; (b) a customer off the shelf (COTS) Wi-Fi access point (AP) with three antennas; and (c) a WARP (wireless open access research platform) with eight antennas;

Figure 10 plots experimental results indicating the probability that two paths can be resolved for (a) MUSIC 1-Dimensional (1 D) estimate of ToF; (b) MUSIC 1-Dimensional (1 D) estimate of AoA; (c) SpotFi 2-Dimensional joint estimate of AoA+ToF; (d) mD- Track 2-Dimensional (2D) joint estimate of AoA+ToF; (e) mD-Track 3-Dimensional (3D) joint estimate of AoA+ToF+Doppler with Doppler unchanged; (f) mD-Track 4- Dimensional (4D) joint estimate of AoA+ToF+Doppler+AoD, with AoD and Doppler unchanged; (g) mD-Track 4-Dimensional (4D) joint estimate of AoA+ToF+Doppler+AoD, with ToF and Doppler unchanged; and (h) mD-Track 4- Dimensional (4D) joint estimate of AoA+ToF+Doppler+AoD, with ToF and AoD unchanged;

Figure 11 shows graphs of a cumulative distribution function (CDF) of (a) AoA estimation error of a direct path signal; (b) AoA estimation error of reflection path signals; (c) ToF estimation error; and (d) AoD estimation error, for mD-Track, SpotFi, and MUSIC methods;

Figure 12 shows a graph of localisation error of mD-Track and SpotFi when using the WARP platform;

Figure 13 shows a graph of localisation error of mD-Track when using a commercial Wi-Fi device;

Figure 14 shows (a) an indoor floorplan map of a meeting room; (b) a localisation error of mD-Track 2D; and (c) a localisation error of mD-Track 3D, for a person located in the centre of the room;

Figure 15 shows a bar chart of localisation error of mDTrack 3D when tracking multiple targets separated by different distances;

Figure 16 shows graphs of Doppler shifts introduced by different motions when (a) the transmitter moves; (b) a human walks; (c) a human stands still and waves his hand; (d) a human stands still and moves his finger; Figure 17 shows a plot of estimated ToFs, AoAs and Doppler shifts resolved using mDTrack for three static paths in the environment and four mobile paths caused by four hands of two persons; and

Figure 18 shows graphs of (a) Number of iterations mD-Track takes to converge with different number of multipaths; (b) End-to-end execution time of mD-Track; and (c) End-to-end execution time of SpotFi and mD-Track with varied granularities (i.e. step sizes).

Detailed description

[0054] Embodiments of the present invention relate to a method and apparatus for localisation and/or tracking by estimating parameters of indoor wireless signals, which may be used in an active or passive tracking system and which is capable of jointly utilising information from many dimensions (i.e. signal parameters) to break the resolution limit of each individual dimension. Accordingly, embodiments of the invention relate to multi-dimensional tracking and an exemplary system is described in detail below and is referred to as mD-Track.

Overview

[0055] Embodiments of the invention apply a novel path separation algorithm to resolve multipath signals at a much higher resolution (e.g. 25 times higher) than in the prior art, isolating signals reflected off targets of interest. As will be explained in more detail below, in embodiments of the invention it is possible to simultaneously localise multiple persons passively at a high accuracy with just a single Wi-Fi transceiver pair. With a significantly higher sensitivity, mD-Track is able to detect even small finger movements. Embodiments of the invention also utilise novel methods to refine the signal parameters to achieve real-time operation. As exemplified below, mD-Track has been implemented on both WARP and off-the-shelf commodity Wi-Fi hardware and its performance has been evaluated in different indoor environments. The experimental results demonstrate simultaneous tracking of up to four human targets at a median location error of 47cm and a 3.4 times accuracy improvement and a 30 times computational complexity reduction for passive localisation of a single target compared to a state-of-the-art SpotFi system. [0056] Passive motion tracking without any device carried by or attached to a target has been an exciting area of recent interest, with important applications including security surveillance [reference 25], elderly care [reference 2], and retail business [reference 30]. Diverse technologies have been proposed for localisation and tracking including ultrasound [reference 23], infrared [references 38, 39], cameras [reference 12], and LED visible light [references 13, 19, 20]. Among these technologies, Wi-Fi based systems stand out as particularly promising due to the pervasive availability of Wi-Fi access points (APs). For device-free passive tracking, Wi-Fi based systems rely on signal reflections off targets to extract essential motion and location information. By its nature, passive tracking is more challenging than localisation of active wireless transmitters, because reflected signals of interest are typically orders of magnitude weaker than for a direct-path signal, and are typically superimposed with a strong direct-path signal as well as other signals reflected from walls, furniture, and other nearby clutter. How to accurately resolve and identify the weak signal reflected off a target of interest becomes a major challenge for these systems.

[0057] Recent progress in this area has explored many ways of extracting different parameters of the wireless signal, such as angle-of-arrival (AoA) and time-of-flight (ToF) [references 10, 28, 42] for localisation and tracking. These approaches rely on accurately estimating the AoA or ToF of each signal path, and so when multiple paths have similar AoAs or ToFs, these systems face fundamental difficulties resolving the paths to obtain accurate parameter estimates. Resolvability is determined by the number of antennas in the receiver (for AoA) and the transmission frequency bandwidth (for ToF), respectively. A straightforward way to improve AoA resolution is to increase the number of antennas, however, this results in higher hardware cost. Improving ToF resolution is more difficult as Wi-Fi standards fix channel bandwidth. Recent attempts to overcome these limitations include creating virtual antenna arrays by physically moving the antennas and combining adjacent channels to form a larger bandwidth using channel hopping [references 18, 41 , 44]. However, these methods affect ongoing data communication which is undesirable. While other recent systems [references 16, 17] have made attempts to jointly estimate AoA and ToF, they are inherently limited, by design, to the two signal dimensions they can explore, and have high computational complexity, so are not scalable to higher dimensions (i.e. to include other parameters). [0058] Rather than adding more antennas or increasing channel bandwidth, embodiments of the present invention provide an alternative approach for finer resolution by jointly exploring more dimensions of the received signal.

[0059] Figure 1 illustrates the intuition behind the present idea. In this example, three signals S1 , S2 and S3 are deemed to arrive at a wireless receiver simultaneously. As shown in Figure 1 (a), signals S1 and S2 are close in time (i.e. have a similar ToF) and therefore cannot be resolved easily by employing ToF. However, S1 and S2 can be relatively easily resolved with AoA, since their AoA difference is large. Similarly, signals S1 and S3 cannot be easily separated with AoA alone, but are resolvable via ToF. This concept extends to higher dimensions as shown in Figure 1 (b), where the receiver jointly estimates ToF, AoA, and Doppler shift. Here, signals S4 and S5 are close to each other in both AoA and ToF, but since S4 is a signal from a moving source, it exhibits a non-zero Doppler shift that separates it from S5, a reflected signal from a static object with zero Doppler shift. Accordingly, embodiments of the invention propose to improve signal resolvability by jointly exploiting information from more signal dimensions, without changing a resolution limit of any individual dimension.

[0060] The exemplary mD-Track is a passive Wi-Fi tracking system that fuses information from multiple signal dimensions, significantly improving resolvability without requiring a wider frequency bandwidth or a larger number of antennas. To utilise multidimensional information, one approach is to explore each signal dimension separately by performing multiple one-dimensional parameter estimations and then combining the results. However, one-dimensional estimates often cannot achieve the required resolution granularity (as illustrated in Figure 1 (a)) and pairing path parameters from different dimensions is a challenging problem in its own right. Instead, mD-Track jointly estimates multi-dimensional parameters at substantially the same time (e.g. jointly estimating the parameters for each signal path in a sequential manner) so the signal parameters of a same signal are always paired inherently and the resolvability is greatly improved since two signals become resolvable if they can be resolved in any one of the dimensions.

[0061] With signals whose parameters are jointly estimated, mDTrack can passively localise and track the motions of multiple targets simultaneously with only a single transmitter-receiver pair. mD-Track can therefore resolve instances of multiple incoming signals that other super-resolution signal processing methods fail to separate. mD-Track has a high sensitivity to accurately detect even subtle finger movements, enabling it to carry out fine-grained tracking. In order to do so, however, and to make the above approach practical, mD-Track, overcomes the following challenges: a) Multipath signal separation and accurate parameter estimation

[0062] Separating signals of close-by paths is challenging. Even if the signal paths are successfully separated, resolvability does not guarantee accurate estimates of the path parameters. Reflected signals are much weaker compared to the direct path signal, so it is difficult to accurately estimate the parameters of reflected signals in the presence of interference from a strong direct path. To address this, mD-Track may employ successive interference cancellation (SIC) [references 11 , 29], a technique originally proposed for data communication, to remove inter-path interference. To further remove energy leakage and residual interference after SIC, mD-Track employs iterative path parameter refinement during which the signals are iteratively re-estimated and more accurately reconstructed with refined parameters in multiple rounds of estimation, which can be proven to be an expectation maximization estimation algorithm that recalls the structure of a Turbo Decoder [reference 32]. b) Bounding computation for real time operation

[0063] While multi-dimensional joint estimation helps to improve signal resolvability and parameter estimation accuracy, the computation required by the joint estimator increases exponentially with the number of signal dimensions, making the required amount of computation intractable for a real-time system design. To address this challenge, a linear-time estimator is designed to exploit a coordinate descent method together with an expectation maximization algorithm to reduce computational complexity significantly, making the design practical for real-time operation. c) Implementation challenges

[0064] In addition to the foregoing signal processing and algorithmic challenges, implementing mD-Track as a functional system requires addressing multiple practical challenges. First, obtaining absolute ToF information requires sub-nanosecond level of time synchronisation between the sender and receiver, a well-known open challenge. Next, there is an RF carrier frequency offset between the sender and receiver antennas that is usually several hundreds of Hertz, interfering with Doppler shifts that mDTrack aims to estimate, which are of the order of one to 20 Hz. [0065] The design described in detail below, provides solutions to these implementation challenges using both WARP and Commercial Off-The-Shelf (COTS) Wi-Fi access points (AP). The experimental evaluation begins with a sensitivity analysis that analyses each signal parameter, measuring the relative ability of different parameters to resolve signals. Head-to-head comparisons in parameter estimation and passive localisation demonstrate 3.5 times accuracy improvements over the state-of- the-art SpotFi system [reference 17]. Further experiments measure the effect of adding another signal dimension (Doppler shift) to mD-Track, showing approximately a 3 times accuracy improvement, in contrast with a marginal 20% improvement from doubling the frequency bandwidth. Also different from existing approaches, the number of signal paths mD-Track can resolve is no longer limited by the number of antennas. With just three antennas available on the COTS Wi-Fi AP, mD-Track is demonstrated to resolve more than 10 signal paths and to estimate the parameters of each signal path accurately. Finally, with the capability of separating reflected signals from multiple close-by targets, for the first time, mD-Track is able to achieve high accuracy device-free (i.e. passive) multi-target localisation with just a single transceiver pair.

The Design

[0066] Localisation or motion tracking of a target relies on separating superimposed signals and accurately estimating each signal's parameters. For example, active localisation relies on separating the direct path signal from all other signal paths, whereas passive localisation estimates a target's position by separating and estimating the parameters of the reflection paths from the target instead. A wireless signal is characterised by multi-dimensional parameters, each parameter providing a piece of location or motion information about the target.

[0067] In accordance with a first embodiment of the present invention there is provided an apparatus 10 (also referred to as mD-Track) for localisation and/or tracking as illustrated in Figure 2A. The apparatus 10 comprises a receiver 12 for receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter 14 along a plurality of different paths (i.e. Direct Path, Path 1 , Path 2 etc.); a computer processor 16; and a data storage device 18, the data storage device 18 comprising instructions operative by the computer processor 16 to separate the received signal into the multiple signals by: a) estimating initial path parameters by:

1. estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise; and

b) refining the parameters by:

i. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool; ii. re-estimating background noise by re-constructing each signal path using the re-estimated parameters from (i) and subtracting the L reconstructed signal paths from the received signal; and

iii. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria: and

c) using the parameters for each signal path to determine a location and/or motion of a target.

[0068] Figure 2A also shows the parameters that can be retrieved from a wireless signal transmitted by the transmitter 14 and reflected from a mobile human target 20 and a static object 22. The parameters for each signal path comprise the time of flight (τ), the angle of arrival (ø), the angle of departure (φ) and the Doppler shift (γ).

Time of flight (τ)

[0069] The propagation time a signal takes to travel along a particular path from the transmitter 14 to the receiver 12 is referred as the time of flight (ToF) (τ). ToF represents the length information of the propagation path. As Figure 2A depicts, ToF estimation of a reflected signal defines an ellipse where the reflector is located, with the transmitter 14 and receiver 12 as the two focal points of the ellipse. The resolution of a ToF estimation is inversely proportional to the channel bandwidth such that the wider the bandwidth, the finer the ToF resolution [reference 41].

Angle of arrival (ø) and angle of departure (φ)

[0070] The angle of arrival (AoA) (ø) indicates the direction of the reflected signal as it arrives at the receiver 12, and the angle of departure (AoD) (φ) indicates the direction of the signal sent from the transmitter 14. The number of antennas at the receiver 12 and transmitter 14 determines the resolution of the AoA and AoD estimates, respectively.

Doppler shift (y)

[0071] Movement of the transmitter 14, receiver 12, or reflectors 20, 22 all introduce frequency shifts to a carrier frequency of the signal which is referred as Doppler shift (γ). Doppler shift provides motion information and can help to estimate a relative velocity of the target 20. Doppler shift resolution is related to an observation interval such that the longer the interval, the finer the resolution.

[0072] Although not illustrated in Figure 2A, a further parameter of each signal path is its complex attenuation (a) which relates to signal strength. For example, when a signal propagates in air from the transmitter 14 to the receiver 12, its signal strength will be attenuated by a.

[0073] Figure 2B illustrates a method 30 for localisation and/or tracking in accordance with embodiments of the invention. The method 30 comprising: a step 32 of receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; followed by separating the received signal into the multiple signals by: a) a step 34 of estimating initial path parameters by:

1. estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise; and

b) a step 36 of refining the parameters by:

i. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool; ii. re-estimating background noise by re-constructing each signal path using the re-estimated parameters from (i) and subtracting the L reconstructed signal paths from the received signal; and iii. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria: and

c) in a step 38 using the parameters for each signal path to determine a location and/or motion of a target.

Wireless signal model

[0074] The transmitter 14 may comprise an array of N antennas and the receiver 12 may comprise an array of M antennas. Both arrays may be linear with a uniform spacing d between adjacent antennas. In which case, the transmitted signal may be denoted as U(t) = [u₁ (t), u₂ (t), ... , u_N (t)] and using the above signal parameters, the received signal can be expressed as per Equation (1): s(t; υ) = ae^j27TYtc(0)g((p)^TU(t - τ)] (1) where υ = [ø, φ, τ, γ, a]^T is a parameter vector containing the parameters that characterise the signal. An N-antenna transmitter array steering vector g(<p) characterises a phase relationship of the signal coming out of the N transmitting antennas while an M-antenna receiver array steering vector c(0) characterises a phase relationship of the signal arriving at the M receiving antennas. In this case, t indicates time, T signals a transpose of a matrix and j indicates a complex number. The received signal x(t) at the receiver 12 can more accurately be expressed as per Equation (2): x(t) = s(t) + W(t) (2)

where W(t) = [w_t(t), w₂ (t), ... , w_M(t)]^T is M-dimensional complex Gaussian noise capturing the background noise. It should be noted that s(t) and s(t; υ) are used interchangeably throughout this specification.

Multi-dimensional estimator

[0075] Firstly, an environment where there is only one path from the transmitter 14 (i.e. sender) to the receiver 12 is considered. The proposed multi-dimensional estimator tool 40 is illustrated in Figure 3 and is designed to be factored into a number of different modules, each corresponding to one of the above parameters such that multiple modules are employed together to jointly estimate all of the parameters. [0076] As shown in Figure 3, the estimator tool 40 is configured as a 4-dimensional sequential estimator for estimating the parameters AoA, AoD, Doppler shift and ToF of a wireless signal as it propagates along a single path from a transmitter array 42 to a receiver array 44. The signal is illustrated as comprising two consecutive time slots t and the estimator tool 40 is shown to comprise an AoA estimator module 46, an AoD estimator module 48, a Doppler shift estimator module 50 and a ToF estimator module 52 as will be explained in more detail below.

AoA estimator module

[0077] The AoA estimator module 46 is a beamformer which selectively receives signals arriving at a specific AoA 0 in each time slot. It is implemented by multiplying the signal received at each antenna in the receiver array 44 with different complex weights and then combining them. For example, to configure the array to only receive signals from angle 0, weights are applied to remove via phase rotation function c(0) the phase differences at each antenna due to differences in the propagation lengths caused by the incidence angle 0, as depicted in Figure 3. The beamformed signal y_s(t) is then given by Equation (3), where H is a conjugate transpose (i.e. a Hermitian transpose) of a matrix: y_s (t) = c(0_s)^Hx(t) (3)

[0078] Once the phase differences are removed, the signals from all the antennas align in time and are added constructively, so the strength of signal at AoA 0 is maximised. Scanning every possible incidence angle, the AoA that produces the maximum beamformer output is the AoA estimate. The AoA estimator can be extended to 3-dimensions including both azimuth and elevation by employing a two- dimensional receiver antenna array.

AoD estimator module

[0079] A signal structure 60 of a Wi-Fi MIMO (multiple input, multiple output) preamble for spatial multiplexing (as illustrated in Figure 4) is exploited to estimate the AoD using the AoD estimator module 48. In this case, two Long Training Symbols (LTSs) are transmitted by two antennas (TX ant-1 and TX ant-2) in the transmitter array 42 in two time slots sequentially before respective payloads 1 and 2. A spatial mapping matrix is multiplied to the LTS in Figure 4 when transmitted but is inverted at the receiver 12 and hence is ignored here. When received, the signal transmitted by the second antenna travels an additional distance to reach the receiver array 44 and hence introduces an extra phase shift. AoA estimates of a single time slot transmission do not capture such an extra phase shift. To estimate AoD, mD-Track analyses the transmissions from each of the antennas in the transmitter array 42 in successive time slots, as illustrated in Figure 3 for a two-antenna example. The AoD estimator module 48 is also a beamformer, measuring the amount of power resulting from a sum of the AoA beamformers in each time slot, phase shifted by a guess of the AoD g(cp) as per Equation (4): y _s(t) = g(cp_s)^Hx(t) (4)

[0080] In the same manner as the AoA estimator module 46, once the AoD guess is correct, the phase differences due to AoD are removed and the signals thus constructively combine, maximising the output of the AoD beamformer.

Doppler estimator module

[0081] The Doppler estimator module 50 estimates a shift in carrier frequency introduced to the signal by motion of the transmitter 14, receiver 12 or reflector 20. From Equation (1) it is noted that the Doppler shift causes a 2 yt phase shift to the received signal. This can be therefore be cancelled by multiplying the signal with _e-j2 yt Different Doppler shifts are applied, calculating a correlation with the transmitted signal U(t), which is maximised when the applied Doppler shift matches the actual Doppler shift.

ToF estimator module

[0082] The ToF estimator module 52 estimates the ToF by cross-correlating an input signal with a delayed version of the transmitted signal u(t--c). If the received signal is x(t), then the correlation is as per Equation (5): ζ(τ,γ ) = J_T x(t)U^*(t-x)dt (5) where T is the signal duration of x(t). In this case, a peak is observed in z when u(t--c) and the transmitted signal align with each other in time, which yields a ToF estimate of τ. Thus, the correlation is maximised when the delayed signal aligns with the received signal.

Modularity [0083] Embodiments of the present invention combine the above individual modules into a four-dimensional estimator z(0, φ,τ,γ ) as shown in Figure 3 for a two-antenna transmitter 14 and receiver 12. The first step is to estimate AoA for each of the two timeslots using the AoA estimator modules 46, before feeding the outputs of each AoA beamformer into the AoD estimator module 48. The output of the AoD estimator module 48 is then passed to the Doppler estimator module 50 to estimate and remove any Doppler shift, before the signal is correlated with a delayed transmitter signal U(t--c) to estimate the ToF via the ToF estimator module 52. Notably, the processing of the signal through the estimator tool 40 is sequential. However, the order of processing is carefully chosen: Doppler shift affects all antennas equally, and so the AoA and AoD estimator modules 46, 48, which rely on measuring phase differences across different antennas, are unimpaired by any arbitrary Doppler shifts. Furthermore, a parameter search, as described below, allows joint estimation of all of the parameters for each signal path. For the general four-dimensional estimator tool 40 shown in Figure 3, the output is as per Equation (6):

where ζ(0, φ, τ,γ ), referred to as the z-function, is calculated for all possible [ø, φ, τ,γ] combinations. The estimation of the parameters [ø, φ,τ,γ] is then obtained by Equation (7):

(0, cp, T,Y)est = arg_umax|z(0, 9, T,Y ) l (7)

[0084] Combining Equation (1) and Equation (7) with Equation (2) then yields a, as per Equation (8):

(a) est = ^ z((0, φ, τ, γ )_est) (8) where T is signal duration and P is transmitted signal power. The received signal s(t) is now fully characterized by the parameter vector υ = [ø, φ, τ,γ, α]^Τ.

[0085] Since the design is modular it has high flexibility and can be adapted to a three- dimensional estimator for a single-antenna transmitter 14 case, by removing the AoD estimator module 48 and the second AoA estimator module 46 for the second time slot as this is no longer required. It may also be adapted to a two-dimensional estimator or a one-dimensional estimator (e.g. a ToF estimator for a single antenna transceiver case).

Resolving multipath

[0086] The discussion above considered a single wireless propagation path. Here, the design is extended to handle multipath propagation. In this case, it is assumed that the receiver array 44 receives signals from L distinct paths, denoting the signal from the 1^th path as s(t; u[) where U[ = [0_1; φ, τι,Υι, oti]^T . The received signal Y(t) is thus the superposition of the signals from all L paths as per Equation (9):

[0087] The goal is to estimate the path parameters as per Equation (10):

V = ,_¾, ...uJ (10) for all L paths in Y(t). Note that L is also unknown and thus must be estimated.

[0088] Resolvability is the premise of accurate path estimation. Non-resolvable signals are merged and the estimated parameters of the combined signal lead to a non- existing path which deviates from the true paths. Although the multi-dimensional estimator tool 40 described above improves the resolvability by higher dimensional parameters [0_h φ,τι,Υι, α₁]^τ of each path, the energies of nearby signal paths may affect the estimation accuracy (for example, a weaker signal may be overwhelmed by a nearby strong signal and thus not be detected). A controlled experiment is described below to demonstrate such an effect, where two signals with different AoAs (60.7° and 73.4°) and ToFs (20.6ns and 28.1 ns) are created and superimposed. The signal with ToF 20.6ns is 10dB stronger than the other signal. The superimposed signal is input into a 2-dimensional estimator tool as per Figure 3 but configured for estimating only AoA and ToF and an output z-function is as depicted in Figure 5(a). It was expected that two peaks would appear in Figure 5(a). However, the weaker signal, in practice, is dominated by the stronger signal and cannot be detected from the z-function. Similar results have been obtained in previous studies when a 1-dimensional MUSIC or 2- dimensional SpotFi estimator is employed. A main reason for this is that those approaches identify the signal paths and estimate the parameters in a single round. No iterative refining process is included to accurately determine energy shares between different signal paths, as per embodiments of the present invention. [0089] mD-Track employs an iterative path parameter refinement process during which the path signals are iteratively re-estimated and more accurately reconstructed from the refined parameters in multiple rounds of estimation. In some embodiments, a successive interference cancellation (SIC) technique is used as borrowed from communication theory [references 1 1 , 29] to remove the inter-path interference, and derive the initial path estimates as a starting point for the refinement process.

[0090] Figure 5(b) shows the residual signal after cancelling the stronger signal, Figure 5(c) shows a reconstructed stronger signal as explained below and Figure 5(d) shows a reconstructed weaker signal as explained below, after three iterations. The peaks of the z-function appear at [63.5°; 22.5ns] in Figure 5(a), [85.9°; 30.5ns] in Figure 5(b), [61.2°; 21.3ns] in Figure 5(c), and [76.7°; 27.0ns] in Figure 5(d).

Successive Interference Cancellation

[0091] To process the L superimposed signals[s₁(t), s₂ (t), ... s_L(t)] in decreasing order of signal strength, all signals but the strongest, i.e., s-^t) are treated as noise and the multi-dimensional estimator tool 40 described above is applied to the raw received signal Y(t) to obtain the output z-function, as per Figure 5(a). The parameters of signal s_t(t) are estimated as the highest peak in the z-function. After this estimate, we reconstruct signal s-^t) using and cancel it from Y(t) . The residual signal is then calculated as per Equation (1 1): x₂ (t) = Y(t)-_Sl(t) = s₂ (t) + ... + s_L(t) + W(t) (1 1)

[0092] In this residual signal, the second strongest signal s₂ (t) dominates. The process is then iterated, passing x₂ (t) to the multidimensional estimator tool 40, which now treats [s₃(t), ... , s_L(t)] as noise. Now s₂(t) results in the highest peak in z-function, as shown in Figure 5(b). The iteration is continued until all the signals are separately estimated, stopping when the residual power in x_L(t) is below a dynamic range of the receiver 12. The number of paths L is also obtained from the number of resolvable signals. The final residual signal represents an estimation of the background noise, as per Equation (12):

W(t) = Y(t)-∑^_{l Sl}(t) (12)

Iterative path parameter refinement [0093] At this point, mD-Track has obtained an estimate of the number of signal paths L and a coarse estimate of each path's parameters. Errors stem from two aspects. First, although small, the interference from weaker signals still affects the estimation of stronger signals. As shown in Figure 5(a), the peak of the z-function, i.e., [63.5°; 22.5ns], is the estimation result for the stronger signal, which deviates slightly from the ground truth, i.e., [60.7°; 20.8ns], due to the existence of the nearby weaker signal. Second, energy leakage from stronger signal during the cancellation process described above introduces errors to the estimation of the weaker signal. The stronger signal that was reconstructed and cancelled is not identical to the true signal due to estimation errors. Energy leakage to the residual signal has a large effect on the estimation of the weaker signal, which result in a large estimation error, as shown in Figure 5(b). To remove the interference, the stronger signal is reconstructed together with noise x_t(t) from the 1^th path with its estimated parameters and the estimated noise as per Equation (13): x₁ ^' (t) = s₁(t; u₁) + W(t) (13) where the s^t; ^) is reconstructed using the parameters U[ obtained in the first round. The signal x (t) is now refined, containing less interference compared to the raw signal X[(t) in which weaker signals are also considered as noise. Next, the path parameters of xi^' (t), u_j ^' , are re-estimated using the multi-dimensional estimator tool 40 described above. To reduce the leakage, the background noise is re-calculated and updated. After obtaining new parameters u₂ , ... , uij for l_s stronger paths, the noise of the (l_s + l)^th path can be updated as per Equation (14):

W(t) =

_5ι(1; υ (14) where s^tj u_j ^') is reconstructed using refined parameters υ and is closer to the true received signal so that less leakage is contained in the noise. The signal of the (l_s + l)^th path is then reconstructed using the updated noise according to Equation 13.

[0094] The path re-estimation and reconstruction is performed for every path, and so it is possible to obtain a better estimate V^' = [υ₁ ^', υ₂ , ... , u^' for all signal paths. Next V^' is fed back into Equation 13 to start another round of estimation. The above steps of multipath signal re-estimation and reconstruction are iterated and stop when the difference of each path parameter between two consecutive iterations is smaller than a predefined threshold. The threshold can be flexibly tuned to meet different levels of accuracy requirements. In the present embodiment, the threshold is set as the step size of the parameter search above, yielding accurate results for passive localisation and motion tracking as will be explained in more detail below.

[0095] Figure 6 illustrates the workflow of the iterative process 70 based on an example of superimposed signals from two paths. First, the received signal Y(t) which comprises all of the multipath signals plus noise is considered to be the first signal x^t) in step 72 and is fed into the multi-dimensional estimator tool 40 as described above in relation to Figure 3 in step 74 so as to calculate an initial estimate of the parameters for the first signal path. The first signal path is then reconstructed in step 76 using the parameters and the reconstructed first signal s^t; !^) is cancelled from the received signal Y(t) in a step 78 to leave a residual signal x₂ (t) in step 80. The residual signal x₂ (t) is then fed into the multi-dimensional estimator tool 40 as described above in relation to Figure 3 in step 82 so as to calculate an initial estimate of the parameters υ₂ for the second signal path. The second signal path is then reconstructed in step 84 using the parameters υ₂ and then both the reconstructed signals s^t Ui) and s₂ (t; u₂) are cancelled from the received signal Y(t) in a step 86 to update the background noise W(t). The updated noise W(t) is then added to the reconstructed first signal s^t; in step 88 and fed into the multi-dimensional estimator tool 40 as described above in relation to Figure 3 in step 90 so as to calculate a refined estimate of the parameters v_t for the first signal path. The first signal path is then reconstructed in step 92 using the refined parameters v_t and the reconstructed refined first signal s^t; ¾ ) along with the reconstructed second signal s₂(t; u₂) is cancelled from the received signal Y(t) in a step 94 to yield an updated background noise W(t). The updated noise is then added to the reconstructed second signal s₂ (t; u₂) in step 96 and fed into the multidimensional estimator tool 40 as described above in relation to Figure 3 in step 98 so as to calculate a refined estimate of the parameters υ₂ ^' for the second signal path. The second signal path is then reconstructed in step 100 using the parameters υ₂ ^' and then both the reconstructed refined signals si ^ Ui^') and s₂ ^'(t; u₂ ) are cancelled from the received signal Y(t) in a step 102 to further update the background noise W(t) and the process continues iteratively until a convergence condition is met.

[0096] In summary, SIC gives the coarse estimates v_t and υ₂ for the two paths. From there, the iterative process 70 reconstructs the path signals x₁ (t) and x₂ (t) , re- estimates the path parameters and υ₂, and updates the residual signal (i.e. noise) W(t) in each iteration.

[0097] Figures 5(c) and 5(d) present the z-function of the multi-dimensional estimator tool 40 after three rounds of iteration. It is clear that the peaks in Figures 5(c) and 5(d) are much closer to the true path parameters compared with Figures 5(a) and 5(b). Thus, demonstrating that the iterative process helps to better refine the estimated parameters.

Convergence

[0098] A common issue for iterative algorithms is their convergence. It is easy to show that the above iterative process belongs to the EM family of algorithms [references 7, 8] with the expectation step given by Equation 13 and the maximization step given by Equation 7, and so convergence is guaranteed [reference 7]. One problem with EM, however, is that it may converge to a local instead of a global maximum if the EM algorithm is not properly initialised. Comprehensive experiments detailed below show empirically that the present SIC-based initialisation is able to provide an accurate initial start, ensuring that the iterative algorithm converges to the global maximum almost always.

Reducing computational complexity

[0099] From Figure 6, it can be seen that the multi-dimensional estimator tool 40 contributes a significant portion of the computation of mDTrack. Each multidimensional estimator tool 40 solves a maximum likelihood problem by an exhaustive search. Specifically, the total number of possible combinations that a 4-dimensional estimator estimating [ø, φ, τ,γ] has to access is given by Equation (15): n. = P0 χ ρ _φ Χ Ρτ Χ Ργ (15) where p₀ , ρ _φ , ρ_τ and ρ_γ are the number of step points for each path parameter, respectively (e.g., p₀ =100 if the range for AoA estimation is [0,TT] with a step size of 0.01TT). The combination η increases exponentially with the number of dimensions and causes significant overhead. From Figure 6, it is observed that the estimator tool 40 is applied N_iterL times in a system with L paths and N_iter rounds of iteration.

[00100] During the iteration, the input to each multi-dimensional estimator tool 40 is actually the signal from one path plus the noise, as shown in Figure 6. Normally, the power level of the signal is tens of dB higher than noise so that a dominant peak in the output z-function of the estimator is observed as per Figures 5(c) and 5(d). Based on this observation, a coordinate descent method may be used to approach the maximum. In particular, the four-dimensional search of Equation 7 is replaced with four one-dimensional searches. In practice this means that three of the four parameters (e.g. φ, τ, and γ) are fixed while a search for the value of the fourth parameter (e.g., 0) is conducted and a maximal output can be generated as per Equation (16):

0" = arg₀ max|z(0, cp', T', _Y') | (16) where φ' , τ' and γ' are the estimates from the previous iteration. We repeat this process for the other three parameters as per Equations (17), (18) and (19):

cp" = arg_(p max|z(0", cp,

l (17)

T" = arg_T max|z(0", cp", T, _Y') | (18) y" = arg_y max|z(0", cp", T", _Y) | (19) and obtain an update of all four parameters. By doing so, the search space is reduced from P₀ x p _φ x Px x p_yto p₀ + p _φ + ρ_τ + ρ_γ, a significant reduction. The trade-off is that the global maximum of each multi-dimensional estimator tool 40 in Figure 6 is not guaranteed. All that is guaranteed is an increase in the output z-function compared with the start point instead of maximising it.

Generalised EM (GEM)

[00101] From Figure 6 it can be seen that L multi-dimensional estimator tools 40 are required in each round of iteration. If every multi-dimensional estimator tool 40 in one round maximises its z-function, then the expectation is maximised and mD-Track moves towards identifying optimal parameters. The relaxing of the requirement of maximising to simply increasing the expectation is called generalised EM (GEM) [reference 9]. The coordinate descent method satisfies the increasing of the z-function and therefore mD-Track becomes a GEM method. For a GEM algorithm, the convergence to maximum is still guaranteed but more iterations may be needed to achieve the final maximisation of expectation [references 9, 22]. Nevertheless, since the algorithm is carefully initialised and a reasonably good starting point is selected using SIC, mD-Track still converges fast. Experimental results show that mD-Track converges in less than 9 rounds in 90% of cases, even with 10 signal paths. The number of iterations typically reduces to as small as five when there are five signal paths. Therefore, the overall computational overhead is significantly reduced.

Practical Implementation Challenges

[00102] Embodiments of the present invention have been implemented using an HP desktop computer as a backend server with an Intel i7 central processing unit (i.e. processor) and 8GB random access memory (i.e. data storage device). Examples using both WARP v3 boards [reference 26] and commodity Wi-Fi routers (TP-Link, TL- WDR4300 and Compex WPJ558) were employed for collecting the channel measurements and relaying them to the server for processing in real-time.

[00103] The WARP v3 board collects time domain information samples and sends them to a computer connected with the WARP via an Ethernet cable. The computer detects the beginning of a packet, extracts the LTS (long training symbol) in the preamble and sends time domain LTS to the server through the internet.

[00104] All of the commercial access points (APs) are equipped with Atheros Wi- Fi NIC (network interface controller) or SoC (System on Chip) (AR9340, AR9580, and QCA9558), and run a customized OpenWRT system. The Wi-Fi driver is modified in kernel space of OpenWRT to enable CSI (channel state information) collection. A user-space application was also built to retrieve the frequency domain LTS by multiplying the transmitted LTS (defined in 802.1 1 standard) with received CSI (empty subcarriers of CSI and LTS are padded with zeros). The frequency domain LTS is then transformed into time domain information via IFFT (inverse Fast Fourier Transform), which is sent to the server through the internet.

Synchronization

[00105] Due to a lack of tight time synchronisation between Wi-Fi transceivers (for both WARP and commercial APs), the Sampling Frequency Offset (SFO) and the Symbol Timing Offset (STO) add a time-varying delay to the estimated ToF value, which makes it difficult to obtain the absolute ToF [reference 17]. It is observed that the time delay added by SFO and STO is the same for all the paths. Therefore, the ToF difference between a pair of two paths is invariant even in the presence of SFO and STO. Figure 7 shows the results from a controlled experiment comprising connecting radio chains of two QCA9558 together using two RF coaxial cables of different lengths to generate different ToFs (9.2ns and 27.4ns). The ToF of the received signal was then estimated. Figure 7(a) plots a histogram of the estimated absolute ToF values of the signal from the shorter cable, which exhibits a large variation across different transmissions. On the other hand, from this figure it can be seen that the variation of the relative ToF between the two paths is minimal. Figure 7(b) presents a cumulative distribution function (CDF) of a ToF estimation error. This shows that even when the absolute ToF measurements are inaccurate (i.e. with a median error of 13ns), the relative ToF estimates can be very accurate (i.e. with a median error of 0.48ns).

[00106] Based on the above observation, the ToF measurement of the direct path can be used as a reference basis to calibrate the ToF estimations of other reflection paths. First, the ground-truth ToF, AoA and AoD of the direct path need to be calculated based on the locations of the transmitter 14 and receiver 12. From all signal path outputs from mD-Track, the path with 1) the shortest ToF, 2) the highest amplitude, or 3) the smallest AoA and AoD difference, can be identified as the direct path measurement and the Δτ between the measured and ground-truth ToF can therefore be determined. The derived Δτ can then be used to correct the ToF measurements for all reflection paths. In this way, time synchronisation is not required and it is still possible to obtain accurate ToF information.

[00107] In a practical implementation, the WiFi transmitter 14 and receiver 12 may be located at high positions, e.g., on a ceiling, to ensure a direct path between them exists. In such conditions, the targets being monitored may be at a different height and the path parameters (ToF, AoA, AoD) need to be projected to the 2D horizontal plane at the ceiling. This can be done with knowledge of the height of the ceiling. Even when the direct path between the transmitter 14 and receiver 12 is blocked, the system can be aware of that because in such conditions no detected path will match the ground-truth direct path, and, in this case, it is possible to omit ToF as a parameter and employ a lower dimensional estimator tool 40.

Local oscillator (LO) offset calibration

[00108] The antennas of each Wi-Fi frontend are phase-locked to different oscillator phases. The LO offset between antennas must be eliminated to provide accurate angle estimation (AoA and AoD). The constant LO offset can be measured by connecting the TX-chain of the transmitter antennas with the RX-chain of the receiver antennas (e.g. of the WARP or COTS Wi-Fi devices) via coaxial cable. As Figure 8(a) illustrates, the three TX-chains and three RX-chains are connected together via a single power splitter/combiner. However, it is observed that spatial multiplexing fails and no packets can be correctly received with such a setup as the channel matrix becomes singular. To break the singularity, the setups in Figures 8(b) and 8(c) are used where one TX-chain is connected with two RX-chains and the remaining two TX- chains are connected with the remaining RX-chain. In Figure 8(b), the LO offset is measured between: 1) TX-chain 2 and TX-chain 3, as denoted as a₂ ; and 2) RX-chain 1 and RX-chain 2, as denoted as Similarly, LO offset is measured between: 1) TX- chain 1 and TX-chain 2, as denoted as _t ; and 2) RX-chain 2 and RX-chain 3, as denoted as β₂ in Figure 8(c).

Carrier frequency offset (CFO)

[00109] CFO between the transmitter 14 and the receiver 12 may confuse Doppler shift estimation since CFO and Doppler frequency shift have the same effect on a carrier frequency. In mD-Track, Doppler shift is introduced by a moving target, so the Doppler effect only occurs on the signal reflected off the target. On the other hand, CFO is introduced by the transceivers, so it affects all signals. Therefore, the frequency change introduced by CFO has the same value for all signals. Based on this observation, the frequency shifts caused by CFO and Doppler shift can be distinguished. The frequency shift caused by CFO is then subtracted to obtain an accurate Doppler shift estimate. It should be noted that mD-Track has a very high resolution for Doppler estimation, i.e., 1 Hz, so subtle frequency shifts caused by moving targets (e.g. in the order of tens of Hz) are still accurately estimated in the presence of a large CFO value.

Evaluation

[00110] Experiments have been conducted in different indoor environments including labs, meeting rooms and corridors, with strong, medium and weak multipath propagations. Figure 9(a) shows an experimental setup in an indoor meeting room. This comprises a transmitter access point (TX AP), a transmitter array (TX array), a receiver array (RX array) and a receiver access point (RX AP). Figure 9(b) shows a commercial AP having a three-antenna array constituting the RX AP and the RX array, respectively, in some experiments. Figure 9(c) shows a WARP AP having an eight- antenna array constituting the RX AP and the RX array, respectively, in some experiments. In both cases, channel measurements were collected and sent to a server via the internet, where the path parameters were estimated for target tracking and localisation in real time.

Multiple versions of mD-Track

[00111] Three versions of mD-Track were tested, as shown in Table 1. The input signal to each version of mD-Track is different. An LTS symbol consists of 64/128 information samples if a 20/40 MHz channel is used. The LTS symbols received by M receiving antennas are required to estimate AoA plus ToF. Thus the input is a matrix of information samples with size M x 64 (20 MHz) to mD-Track 2D. The matrix size increases to M x 64 x T and M x N x 64 x T for mD-Track 3D and 4D respectively, where N is the number of transmitting antennas and T is the number of packets collected for a Doppler shift estimation. It should be noted that mD-Track requires estimation over multiple packets when and only when Doppler shift is jointly estimated.

[00112] The performance of SpotFi is also evaluated for comparison with the mD-Track embodiments of the present invention. SpotFi estimates ToF plus AoA and takes CSI as input which is calculated using transmitted and received LTS at WARP. The size of the input CSI matrix is M x 56 and M x 114 when using 20 and 40 MHz, respectively.

Table 1 : Comparison of different versions of mDTrack plus SpotFi

Resolving multipaths

[00113] The Applicants have demonstrate that mD-Track has a significantly better ability than previous algorithms to resolve two signals arriving from separate paths. Controlled experiments were conducted by connecting the transmitting and receiving chains of two WARPs with coaxial cables and varying the length of cable to provide different propagation times. The transmitted signal phases were rotated to emulate different AoAs, AoDs and Doppler shifts. The ToF, AoA, AoD and Doppler shift differences between the two signals were varied by a multiple of the parameter's basic resolution (e.g. the resolution of ToF at 20 MHz is Δτ = 50 ns, Doppler at 1 s observation time is Δγ = 1 Hz, angular resolution of AoA and AoD is determined by the antenna count M as for a linear array, e.g., AoA resolution Δ0 = 14.2° if there are eight antennas in the array [reference 15]). When two paths are close to each other, they may not be resolvable and may be estimated as one path deviated from both the two true paths. For each parameter configuration, 1000 packets were transmitted and the two signals were resolved with mD-Track 1000 times using the received packets.

[00114] Figure 10 plots the output parameters for each variant tested. The x- axis and y-axis are the path parameter differences relative to their basic resolution in that dimension, e.g., 0.2 of ToF difference means 0.2 x 50 ns = 10 ns and the color depth (from white to black) indicates the probability that two path signals are resolvable in the 1000 estimations. The resolvability of the mD-Track and SpotFi (using JADE) versions listed in Table 1 are compared also with a 1 D MUSIC algorithm, separately for ToF and AoA. More specifically, in Figure 10 white indicates that the two signals are "non-resolvable" and black indicates that the two signals are "fully resolvable". In particular, Figure 10(a) shows the resolvability of a MUSIC 1 D estimator for ToF; Figure 10(b) shows the resolvability of a MUSIC 1 D estimator for AoA; Figure 10(c) shows the resolvability of a SpotFi 2D estimator for jointly estimating AoA+ToF; Figure 10(d) shows the resolvability of mD-Track 2D to jointly estimate AoA+ToF; Figure 10(e) shows the resolvability of mD-Track 3D to jointly estimate AoA+ToF+Doppler, with Doppler unchanged; Figure 10(f) shows the resolvability of mD-Track 4D to jointly estimate AoA+ToF+Doppler+AoD, with AoD and Doppler unchanged; Figure 10(g) shows the resolvability of mD-Track 4D to jointly estimate AoA+ToF+Doppler+AoD, with ToF and Doppler unchanged; and Figure 10(h) shows the resolvability of mD- Track 4D to jointly estimate AoA+ToF+Doppler+AoD, with ToF and AoD unchanged.

[00115] Observations from Figure 10 are as follows. First, all algorithms perform better than the basic resolution limit, which means that two signals can still be resolved even when the parameter difference is smaller than the basic resolution. Second, increasing the number of dimensions significantly increases resolvability. One dimensional MUSIC is not able to resolve two signals with AoA/ToF difference smaller than about 0.75 of its basic resolution. The fraction can be reduced to about 0.4 for AoA and ToF if applying mD-Track 2D, 0.1 if applying mD-Track 3D and below 0.1 (around 0.04) if applying mD-Track 4D. Even with the same dimension, mD-Track 2D still outperforms SpotFi 2D, as illustrated in a comparison of Figures 10(c) and (d). The improvement stems from the iterative interference cancellation and path refinement process in mDTrack as described above. Both MUSIC and SpotFi estimate parameters of all resolvable paths simultaneously and ignore the mutual interference between paths. mD-Track, however, only estimates one path (the strongest one) at a time and subtracts the estimated signal from the input before estimating the next path. As long as parameters of the stronger path are accurate, the nearby weaker signal is preserved in the residual signal and can be estimated accurately, as shown in Figure 5(c) and (d). Furthermore, increasing the parameter dimensions helps to increase the resolvability significantly.

Estimation Accuracy

[00116] The Applicants have demonstrated that mD-Track according to an embodiment of the invention, estimates signal path parameters with high accuracies. Channel measurements were collected using a Compex WPJ558 router, which has three antennas. The ground truth of the location related parameters, including AoA, AoD, and ToF, were calculated based on the actual positions of the transceivers. A comparison of AoA and ToF estimation is made with MUSIC and SpotFi. The comparison favors MUSIC and SpotFi by selecting the path with the AoA estimate closest to the ground truth as their estimate. The ground truth of Doppler is determined by motion and is hard to measure. An evaluation of mD-Track's Doppler estimation is discussed later.

[00117] Figure 1 1 (a) shows a cumulative distribution function (CDF) of AoA estimation error of the direct path signal for mD-Track 4D, mD-Track 2D, SpotFi and MUSIC. Figure 11 (b) shows a cumulative distribution function (CDF) of AoA estimation error of reflection path signals for mD-Track 4D, mD-Track 2D, SpotFi and MUSIC. Figure 1 1 (c) shows a cumulative distribution function (CDF) of ToF estimation error for mD-Track 4D, mD-Track 2D, SpotFi and MUSIC. Figure 1 1 (d) shows a cumulative distribution function (CDF) of AoD estimation error, for mD-Track 4D LOS (i.e. an active set-up) and mD-Track 4D passive (i.e. using a reflected signal).

AoA and ToF estimation

[00118] AoA estimation results are presented in Figures 11 (a) and (b). From these it is observed that mD-Track provides much more accurate AoA estimates: with only three antennas, mD-Track's median AoA error for the direct path (Figure 11 (a)) is as small as 4.4° and 6.2° for 4D and 2D versions respectively, compared to 13.4° and 17.1 ° for SpotFi and MUSIC, respectively. The AoA estimates of the reflection paths (Figure 1 1 (b)) are less accurate because reflection signals are weaker in most cases. Despite that, mD-Track still achieves a median AoA error of 5.6° and 7.3° for 4D and 2D versions respectively, compared with 16.9° and 24.2° for SpotFi and MUSIC respectively.

[00119] mD-Track calculates the ToF differences between the reflection paths and direct path. From Figure 11 (c), it is clear that mD-Track 4D and 2D are able to estimate the ToF difference between the reflection path and direct path with a median error of 1.23 ns and 1.85 ns, while SpotFi and MUSIC achieve a median error of 3.8 ns and 6.7 ns.

[00120] From the above experiments, it is observed that a higher dimensional estimator provides more accurate results due to its high resolvability, i.e., 2- dimensional SpotFi and mD-Track outperform 1-dimensional MUSIC in both AoA and ToF estimation and 4-dimensional mD-Track provides the most accurate estimation. Even with the same dimensionality, mDTrack 2D outperforms 2-dimensional SpotFi. The improvement comes from the fact that mD-Track provides higher resolvability by interference cancellation and the path parameter estimation refining process described above in multiple rounds, thus embodiments of the present invention are more accurate compared to a sub-space based method like SpotFi.

AoD estimation

[00121] Figure 1 1 (d) shows the AoD estimation results for a direct (LoS) path and a (passive) reflection path using mD-Track 4D. The median errors are 3.3° and 7.6° respectively. It is believed that mD-Track is the first implemented system based on COTS Wi-Fi hardware that can estimate AoD at such a high accuracy.

Passive Localisation

[00122] Further experiments evaluate the device-free passive localisation performance of mD-Track with a single pair of wireless terminals (WARP or COTS Wi- Fi AP). In these experiments, a target person is allowed to move around, reflecting the transmitted signals between the APs from the person's body.

[00123] The results obtained using WARP are presented in Figure 12 which shows localisation error of mD-Track and SpotFi when using the WARP platform. It is observed that mD-Track 3D and 4D are able to achieve a median localisation error of 0.36 m and 0.28 m with eight antennas and 40 MHz bandwidth. It is believed that no prior Wi-Fi based systems have demonstrated such a high accuracy with a single transceiver pair for passive localisation. A comparison is also made of mD-Track with SpotFi, which was originally designed for active localisation. For a fair comparison, an AoA and ToF joint estimator was implemented based on SpotFi's algorithm which was modified it to work with reflected signals in a passive mode. The median error of SpotFi is 1.56 m with eight antennas and 40 MHz. Thus, even mD-Track 2D achieves much better performance than SpotFi.

[00124] The localisation error results obtained using commodity Wi-Fi APs are presented in Figure 13. The commodity AP is equipped with a limited number of antennas, i.e., three compared with eight at WARP, so all three antennas are used in these experiments. The size of the bandwidths is varied along with the number of dimensions of mD-Track to evaluate the performance. As a comparison with WARP, mD-Track 3D and 4D using the commodity AP are still able to achieve a median error of 0.67 m and 0.48 m with 40 MHz bandwdith and only three antennas.

Impact of bandwidth, antennas and dimensionality

[00125] Figures 12 and 13 depict the localisation error with variant signal bandwidth (20 and 40 MHz), antenna count (3, 4 and 8) and dimensionality (2D, 3D and 4D). From the results, a trend is observed that a higher number of dimensions leads to higher accuracy. With the same bandwidth and antenna count (e.g. 8 antennas and 40 MHz), mD-Track 4D achieves a much smaller median error (0.28 m) compared with mDTrack 3D (0.36 m) and 2D (1.16 m). It is also noted that increasing the number of antennas or bandwidth can improve the performance by improving the basic resolution in that dimension. By fixing the bandwidth (40 MHz) and doubling the antenna count from 4 to 8 using WARP, mD-Track 3D reduces the median error from 0.57 m to 0.36 m. By fixing the antenna count (3), and doubling the bandwidth from 20 MHz to 40 MHz using COS Wi-Fi AP, mD-Track 3D reduces the error from 0.89 m to 0.67 m. It is noted that increasing the number of antennas (or radio chains) and bandwidth significantly increases the hardware overhead, especially for the COTS device. Increasing the dimensionality, however, does not incur additional hardware overhead. Effect of location and Doppler shift

[00126] Experiments were conducted to explore the effect of location on localisation performance. Figure 14(a) shows an indoor floorplan map of a meeting room of 60 m² as used in this set-up. The floorplan was divided into 1 m x 1 m grids and a human target was stood in the center of each grid waving his hands. Figure 14(b) shows the localisation error of mD-Track 2D in locating the person in each grid and Figure 14(c) shows the localisation error of mD-Track 3D in locating the person in each grid, where the lightest grids depict the highest errors.

[00127] Channel measurements were collected using WARP and used to locate the target using mDTrack 2D and 3D. From Figure 14(b) it is apparent that the localisation results using AoA+ToF are highly sensitive to the relative location of the target with respect to the transceiver and the other reflectors (i.e. walls). Specifically, the error is higher (lighter colour) when the target is closer to the sender or the wall. Two closely located reflectors have similar AoAs and ToFs so the signal reflected off the human may not be separated from the signal emitted by the sender or reflected off the nearby wall, and therefore they become unresolvable. From Figure 14(c) it is clear that using mD-Track 3D, which incorporates Doppler shift in the estimation, it is possible to resolve signals reflected off mobile targets from ambient static reflectors such as walls. In this case, with the third dimension parameter Doppler shift included, localisation accuracy is high for almost all of the grids. Thus, including Doppler shift incorporates motion information to further resolve signals and makes the system less sensitive to target locations. Accordingly, it is observed that the actual location of the target affects the localisation performance, particularly when the target is located close to the strong direct path between the transceivers.

Multi-target localisation

[00128] Passively localising multiple targets in the same space is a well-known challenging problem, especially when the targets are near to each other. The capability of resolving signals from two nearby reflectors which has been demonstrated above, plays a key role in multi-target localisation. In the present experiment, two targets stood 0.5 m, 1 m, 2 m, and 3 m apart, respectively, and waved their hands. A WARP transceiver equipped with 8 antennas and transmitting using 40 MHz signals was used along with mD-Track in accordance with an embodiment of the invention. The Doppler shifts caused by two hands are rarely the same at a time point since they have different speeds and directions with respect to the receiver, so mD-Track is able to resolve signals from two close-by targets and successfully localise both of them, achieving a median error of 0.51 m. As shown in Figure 15, mD-Track is able to locate four targets simultaneously with a median error of 0.47 m when they are 3 m apart from each other. The error is 0.94 m even when they are 0.5 m apart.

Detecting different types of motions

[00129] Embodiments of the invention like mD-Track are not only capable of tracking the location but also the motion of a target. In this case, the capability of detecting four types of motions using mD-Track was investigated. In scenario one, the transmitter was moved and the Doppler shift was estimated as shown in Figure 16(a). In scenario two, the locations of the transceivers were fixed and a human target moved towards and away from the receiver, with the Doppler shift results being shown in Figure 16(b). In the third scenario, the human target stood still and only waved his hand back and forth and the results are shown in Figure 16(c). In the last scenario, the human target stood still and only moved his fingers back and forth and the results are shown in Figure 16(d). In each case, mD-Track estimated the Doppler shift introduced by the different motions and the results are depicted in Figure 16.

[00130] From Figure 16(a) it is clear that mD-Track can resolve three multipath signals, and all three multipath signals have non-zero Doppler shifts. This is because, when the transmitter moves, all the signal paths have Doppler shifts. From Figure 16(b), when the human target is moving, mD-Track resolves multiple paths and only one has a non-zero Doppler shift, which is the signal reflected from the human body. Similarly, in Figure 16(c), mD-Track resolves multiple paths and only one has a nonzero Doppler shift caused by the hand movement. Comparing Figure 16(b) and (c), it is observed that the Doppler shift caused by hand movements changes more quickly than the one caused by human body movement. In Figure 16(d), it can be seen that even the Doppler shift introduced by slight finger movements can be detected. Accordingly, mD-Track according to embodiments of the invention is very sensitive to motion and can accurately identify signals reflected from a target's body, his moving hands or fingers.

Multi-motion tracking

[00131] Investigations were conducted to determine whether mD-Track was able to detect multiple movements simultaneously. In this experiment, two persons stood and waved their hands at the same time. mD-Track was used to estimate the ToF, AoA and Doppler shift of all the resolvable multipaths in the environment and the results are shown in Figure 17. Three static paths are observed since their Doppler shifts are zero (one of them is the direct LoS path and the other two are the reflected paths from each of the two static human targets). There are also four paths whose Doppler shifts are non-zero - their ToFs and AoAs are different from each other, such that they correspond to the four waving hands of the two persons. The four reflected signals from the hands are clearly resolved and the parameters of each path are accurately estimated. mD-Track can use Doppler shifts to detect motion, as well as ToF and AoA to locate multiple movements at the same time. For each mobile path, it is possible to use the unique time domain Doppler patterns (similar to those in Figure 16), to classify pre-defined motions of individual objects and accordingly, embodiments of the invention may be employed for gesture recognition [reference 24] or activity tracking [references 36, 37], etc.

Computational complexity

[00132] Based on the above information, four parameters affect the computational complexity of embodiments of the invention like mDTrack, i.e., the number of multipaths, the number of iterations mD-Track takes to converge, the dimensionality of estimation, and the number of search steps in each dimension. The estimation algorithm is run using channel measurements collected from different experimental settings and the number of iterations, number of propagation paths, and the execution time for each trace is recorded. Figure 18(a) plots the number of iterations mD-Track performs before converging for L=3, 5, 8 and 10. This shows that mD-Track converges within four iterations 90% of the time for traces with three dominant paths. mD-Track converges quickly within five, eight and nine iterations even when there are five, eight and ten paths, 90% of the time. Figure 18(b) shows overall end-to-end execution time of mD-Track for L=3, 5, 8 and 10 and this shows that even with eight multipaths, the median system latency is as small as 0.13 s.

[00133] Figure 18(c) shows end-to-end execution time of SpotFi and mD-Track with varied granularities (i.e. step sizes). The dimensionality and step size substantially affect the number of combinations for searching. The step sizes of frequency were fixed to 0.1 Hz while the step size of angle and time was varied in order to evaluate the computational complexity of mD-Track 2D, 3D, and 4D, in comparison with SpotFi. mD-Track 2D estimates AoA and ToF jointly, as SpotFi does, but runs much faster than SpotFi, as depicted in Figure 18(c). The end-to-end execution time of mD-Track does not increase much when decreasing the step size or increasing the dimensionality. In the current implementation, a step size of [0.02 rad, 0.5 ns, 0.1 Hz] was used and as a result mD-Track 2D, 3D, and 4D were found to run 30x, 20x and 14x faster than SpotFi.

Indoor active localization

[00134] Received signal strength indication (RSSI) based indoor localisation techniques [references 5, 45] provide coarse localisation accuracies. More advanced techniques [references 10, 42] make use of an antenna array at the latest 802.11 n/802.1 1ac APs [references 31 , 47] to estimate the AoA of a signal emitted from a mobile device. These systems are able to achieve localisation accuracies of a few decimeters, which, however, are still vulnerable to rich multipaths because of the poor resolvability with limited number of antennas at the commodity Wi-Fi APs. Moving the antenna mechanically to emulate a large antenna array is proposed [reference 18], while the locations of most APs today are still fixed and the antennas cannot move freely. The latest ToF based systems [references 35, 41 , 43, 44] also provide high accuracies by combining smaller channels to form a virtual wider bandwidth for finer resolution. However, channel hopping does affect data communication and there is only a total of 70 MHz frequency bandwidth in the 2.4GHz band. All of these systems try to increase the resolution in one particular dimension. Embodiments of the invention like mD-Track, on the other hand, jointly estimate multidimensional information to achieve a much finer resolution.

Passive localization and motion tracking

[00135] A lot of attention is being paid to passive localisation, gesture recognition and Wi-Fi imaging in recent years. Passive localisation is more challenging than active localization. RSSI/CSI signature based passive localisation systems [references 4, 36, 37, 40, 46] usually rely on high-density deployments which are not realistic for large-scale implementations. Wi-Vi [reference 3] employs a signal nulling technique to cancel signals from static objects and then estimate an AoA of a signal reflected off a human. Wi-Vi is able to track the direction of a human's movement, but no location information can be obtained. WiTrack [references 1 , 2] and other systems [references 6, 14, 21 , 33, 48, 49] use dedicated hardware with more than 1 GHz bandwidth to achieve a high resolution ToF for human tracking which is not possible with Wi-Fi. While some recent systems [references 16, 17] consider the use of both AoA and ToF for object tracking, their systems are designed to estimate two- dimensional parameters, and cannot be generalised easily to estimate parameters of more dimensions. Also the computational load in these systems is very high [references 16, 17].

Channel parameter estimation

[00136] Most localisation systems explore information in one dimension. MUSIC [reference 27] is widely employed to obtain AoA or ToF information. SpotFi [reference 17] employs a modified version of MUSIC to jointly search two dimensions, which is similar to JADE [reference 34]. Wi-Deo [reference 16] estimates AoA and ToF using compressive sensing. However, embodiments of the present invention like mDTrack provide a general platform that can be adapted to work with any number of dimensions. In addition, mD-Track significantly reduces the computational load for a multidimensional search, e.g., mDTrack is 30 times faster than SpotFi.

Summary

[00137] To handle multipath propagation, embodiments of the present invention propose a maximum-likelihood based iterative path parameter estimation algorithm. The described embodiment first adopts a coarse cancellation algorithm that resembles successive interference cancellation (SIC) for data communications, but is applied for multipath cancellation. The interference cancellation based method is applied to resolve signals from one path, cancelling the interference from other paths and is repeated to resolve every resolvable path. Building atop this, an iterative cancellation algorithm that recalls the structure of a Turbo Decoder, operating in a loop and iteratively refining the signal parameters is employed. Embodiments of the present invention also perform a multi-dimensional search over each resolved signal to estimate its parameters. The above steps together form the proposed multidimensional parameter estimator according to embodiments of the invention.

[00138] While multi-dimensional joint estimation helps to improve signal resolvability and parameter estimation accuracy, the computation required by the joint estimator increases exponentially with the number of signal dimensions, making the required amount of computation intractable for a system design capable of real-time operation. To address this challenge, a linear-time estimator is proposed to exploit a coordinate descent method together with the expectation maximisation algorithm to reduce computational complexity significantly, making the design practical for real-time operation.

[00139] Thus, embodiments of the invention such as the described mD-Track provide a general platform capable of incorporating information from as many dimensions as possible, to achieve the finest resolution in resolving multipath signals. The experiments described demonstrate greatly improved performance for active and passive multi-target localisation and motion tracking. The platform can be easily extended to support a myriad of applications including gesture recognition and Wi-Fi imaging.

[00140] Although only certain embodiments of the present invention have been described in detail, many variations are possible in accordance with the appended claims. For example, features described in relation to one embodiment may be incorporated into one or more other embodiments and vice versa.

References

[00141] The following references are incorporated herein by reference, with regards to the background of the invention.

[1] F. Adib, Z. Kabelac, and D. Katabi. Multi-person localization via RF body reflections. In NSDI, 2015.

[2] F. Adib, Z. Kabelac, D. Katabi, and R. C. Miller. 3d tracking via body radio reflections. In NSDI, 2014.

[3] F. Adib and D. Katabi. See through walls with WiFi! In ACM SIGCOMM, 2013.

[4] H. Aly and M. Youssef. New insights into WiFi-based device-free localization. In

ACM UbiComp Adjunct, 2013.

[5] P. Bahl and V. N. Padmanabhan. RADAR: an inbuilding rf-based user location and tracking system. In IEEE INFOCOM, 2000.

[6] S. Bartoletti and A. Conti. Passive network localization via uwb wireless sensor radars: The impact of TOA estimation. In IEEE ICUWB, 2011.

[7] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the royal statistical society. Series B, 1977.

[8] M. Feder and E. Weinstein. Parameter estimation of superimposed signals using the EM algorithm. IEEE Trans, on Acoustics, Speech, and Signal Processing, 1988. [9] J. A. Fessler and A. O. Hero. Space-alternating generalized expectation- maximization algorithm. IEEE Trans, on Signal Processing, 1994.

[10] J. Gjengset, J. Xiong, G. McPhillips, and K. Jamieson. Phaser: Enabling phased array signal processing on commodity WiFi access points. In ACM MobiCom, 2014.

[1 1] D. Halperin, T. Anderson, and D.Wetherall. Taking the sting out of carrier sense: Interference cancellation for wireless LANs. In ACM MobiCom, 2008.

[12] H. Hile and G. Borriello. Positioning and orientation in indoor environments using camera phones. IEEE Computer Graphics and Applications, 2008.

[13] P. Hu, L. Li, C. Peng, G. Shen, and F. Zhao. Pharos: Enable physical analytics through visible light based indoor localization. In HotNets, 2013.

[14] Y. Jia, L. Kong, X. Yang, and K. Wang. Through-wallradar localization for stationary human based on lifesign detection. In IEEE RadarCon, 2013.

[15] D. H. Johnson and D. E. Dudgeon. Array Signal Processing: Concepts and Techniques. Simon & Schuster, 1992.

[16] K. Joshi, D. Bharadia, M. Kotaru, and S. Katti. WiDeo: Fine-grained device-free motion tracing using RF backscatter. In NSDI, 2015.

[17] Manikanta Kotaru, Kiran Joshi, Dinesh Bharadia, and Sachin Katti. "SpotFi: Decimeter Level Localization Using WiFi." In Proceedings of the ACM SIGCOMM 2015 [18] S. Kumar, S. Gil, D. Katabi, and D. Rus. Accurate indoor localization with zero start-up cost. In ACM MobiCom, 2014.

[19] L. Li, P. Hu, G. Shen, C. Peng, and F. Zhao. Epsilon: A visible light based positioning system. In NSDI, 2014.

[20] T. Li, C. An, Z. Tian, A. T. Campbell, and X. Zhou. Human sensing using visible light communication. In ACM MobiCom, 2015.

[21] N. Maaref, P. Millot, C. Pichot, and O. Picon. A study of UWB fm-cw radar for the detection of human beings in motion inside a building. IEEE Trans, on Geoscience and Remote Sensing, 2009.

[22] R. M. Neal and G. E. Hinton. A view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pages 355-368. Springer, 1998.

[23] N. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket location-support system. In MobiCom, 2000.

[24] Q. Pu, S. Gupta, S. Gollakota, and S. Patel. Wholehome gesture recognition using wireless signals. In MobiCom, 2013. [25] Y. Qiao, O. Zhang, W. Zhou, K. Srinivasan, and A. Arora. PhyCloak: Obfuscating sensing from communication signals. In NSDI, 2016.

[26] Rice Univ. Wireless Open Access Research Platform (WARP). http://warpproject.org.

[27] R. Schmidt. Multiple emitter location and signal parameter estimation. IEEE Trans, on Antennas and Propagation, vol. 34, no. 3, pp. 276-280, 1986.

[28] S. Sen, J. Lee, K.-H. Kim, and P. Congdon. Avoiding multipath to revive inbuildingWiFi localization. In MobiSys, 2013.

[29] S. Sen, N. Santhapuri, R. R. Choudhury, and S. Nelakuditi. Successive interference cancellation: A back-ofthe- envelope perspective. In ACM HotNets, 2010.

[30] L. Shangguan, Z. Zhou, X. Zheng, L. Yang, Y. Liu, and J. Han. ShopMiner: Mining customer shopping behavior in physical clothing stores with COTS RFID Devices. In ACM SenSys, 2015.

[31] C. Shepard, A. Javed, and L. Zhong. Control channel design for many-antenna mu-mimo. In ACM Mobi- Com, 2015.

[32] B. Sklar. A primer on Turbo Code concepts. IEEE Comms. Magazine, pages 94- 102, Dec. 1997.

[33] S. Sur, X. Zhang, P. Ramanathan, and R. Chandra. Beamspy: Enabling robust 60 ghz links under blockage. NSDI, 2016.

[34] A. J. van der Veen, M. C. Vanderveen, and A. Paulraj. Joint angle and delay estimation using shift-invariance techniques. IEEE Trans, on Signal Processing, 1998.

[35] D. Vasisht, S. Kumar, and D. Katabi. Decimeter-level localization with a single WiFi access point. In NSDI, 2016.

[36] W. Wang, A. X. Liu, M. Shahzad, K. Ling, and S. Lu. Understanding and modeling of WiFi signal based human activity recognition. In ACM MobiCom, 2015.

[37] Y. Wang, J. Liu, Y. Chen, M. Gruteser, J. Yang, and H. Liu. E-eyes: Device-free location-oriented activity identification using fine-grainedWiFi signatures. In ACM MobiCom, 2014.

[38] R. Want, A. Hopper, V. Falcao, and J. Gibbons. The active badge location system. ACM Trans, on Information Systems, 1992.

[39] A. Ward, A. Jones, and A. Hopper. A new location technique for the active office. IEEE Personal Communications, 1997.

[40] J. Xiao, K. Wu, Y. Yi, L. Wang, and L. M. Ni. FIMD: Fine-grained device-free motion detection. In IEEE ICPADS, 2012. [41] Y. Xie, Z. Li, and M. Li. Precise power delay profiling with commodity Wi-Fi. In ACM MobiCom, 2015.

[42] J. Xiong and K. Jamieson. ArrayTrack: a fine-grained indoor location system. In NSDI, 2013.

[43] J. Xiong, K. Jamieson, and K. Sundaresan. Synchronicity: Pushing the envelope of fine-grained localization with distributed MIMO. In ACM HotWireless, 2014.

[44] J. Xiong, K. Sundaresan, and K. Jamieson. ToneTrack: Leveraging frequency- agile radios for indoor wireless localization. In MobiCom, 2015.

[45] M. Youssef and A. Agrawala. The horus WLAN location determination system. In ACM MobiSys, 2005.

[46] M. Youssef, M. Mah, and A. Agrawala. Challenges: Device-free passive localization for wireless environments. In ACM MobiCom, 2007.

[47] H. Yu, O. Bejarano, and L. Zhong. Combating intercell interference in 802.1 l ac- based multi-user mimo networks. In ACM MobiCom, 2014.

[48] Y. Zhou, C. L. Law, Y. L. Guan, and F. Chin. Localization of passive target based on UWB backscattering range measurement. In IEEE ICUWB, 2009.

[49] Y. Zhu, Y. Zhu, B. Y. Zhao, and H. Zheng. Reusing 60ghz radios for mobile radar imaging. In MobiCom, 2015.

[50] Guanghan Xu, R. H. Roy and T. Kailath, "Detection of number of sources via exploitation of centro-symmetry property," in IEEE Transactions on Signal Processing, vol. 42, no. 1 , pp. 102-1 12, Jan 1994.

[51] M. Wax and T. Kailath, "Detection of signals by information theoretic criteria," in IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 33, no. 2, pp. 387-392, Apr 1985.

[52] M. C. Vanderveen, C. B. Papadias and A. Paulraj, "Joint angle and delay estimation (JADE) for multipath signals arriving at an antenna array," in IEEE Communications Letters, vol. 1 , no. 1 , pp. 12-14, Jan. 1997.

[53] M. C. Vanderveen, B. C. Ng, C. B. Papadias and A. Paulraj, "Joint angle and delay estimation (JADE) for signals in multipath environments," 1058-6393/97, IEEE, pp. 1250-1254, 1997.

[54] N. Czink, M. Herdin, H. Ozcelik and E. Bonek. Number of multipath clusters in indoor mimo propagation environments. Electronic Letters, 2004. [55] S. J. Wright. Coordinate descent algorithms. Mathematical Programming, 2015.

[56] T. Zwick, C. Fischer, and W. Wiesbeck. A stochastic multipath channel model including path directions for indoor environments. IEEE journal on Selected Areas in Communications, 2002.

Claims

Claims

1. An apparatus for localisation and/or tracking comprising: a receiver for receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; a computer processor; and a data storage device, the data storage device comprising instructions operative by the computer processor to separate the received signal into the multiple signals by: a) estimating initial path parameters by:

1. estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise;

b) refining the parameters by:

i. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool;

ii. re-estimating background noise by reconstructing each signal path using the re-estimated parameters from (i) and subtracting the L reconstructed signal paths from the received signal; and

iii. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria; and

c) using the parameters for each signal path to determine a location and/or motion of a target.

2. The apparatus according to claim 1 wherein the parameters are selected from the list comprising: Angle of Arrival (AoA), Angle of Departure (AoD), Time of Flight (ToF), Doppler Shift and Attenuation.

3. The apparatus according to claim 2 wherein the estimator tool is a multidimensional estimator comprising one or more of: an AoA estimator, an AoD estimator, a Doppler estimator and a ToF estimator.

4. The apparatus according to claim 3 wherein the receiver comprises a plurality of antennas and the AoA estimator comprises a beamformer configured to remove phase differences between signals of a same transmission timeslot arriving at different antennas in the receiver, summing resulting signals and scanning possible incidence angles to determine an angle of incidence generating a maximum beamformer output.

5. The apparatus according to claim 3 or 4 wherein the AoD estimator comprises a beamformer configured to apply a phase shift corresponding to possible departure angles to the sum of the resulting signals from the AoA estimator for each transmission time slot, to sum these signals, to determine an angle of departure generating a maximum beamformer output and to remove the applied phase shifts.

6. The apparatus according to any one of claims 3 to 5 wherein the Doppler estimator comprises applying different Doppler shifts to an output from the AoD estimator and correlating this signal with the transmitted wireless signal to identify a Doppler shift producing a closest correlation and providing an output signal using the Doppler shift identified.

7. The apparatus according to any one of claims 3 to 6 wherein the ToF estimator comprises correlating an output signal from the Doppler estimator with a delayed version of the transmitted wireless signal to determine the ToF.

8. The apparatus according to any preceding claim wherein successive interference cancellation is applied by:

1. treating the received signal as a strongest signal path and estimating one or more parameters of the received signal using the estimator tool;

2. re-constructing the strongest signal path using the estimated parameters and cancelling the re-constructed strongest signal path from the received signal to provide a residual signal; and

3. repeating step (1) and (2) using the residual signal as the received signal until the residual signal has a power below a predefined threshold.

9. The apparatus according to claim 8 wherein the number (L) of signal paths is estimated as the number of the re-constructed strongest signal paths.

10. The apparatus according to claim 8 or 9 wherein the initial background noise is estimated by subtracting the L re-constructed strongest signals from the received signal.

1 1. The apparatus according to any preceding claim wherein the estimation of more than one parameter comprises fixing all but one of the parameters and searching for an optimal value for the one parameter.

12. The apparatus according to claim 11 wherein the optimum value is determined using an expectation maximum (EM) model or a generalized expectation maximum (GEM) model.

13. The apparatus according to claim 2 further configured to determine a direct signal path by identifying the signal path with a shortest ToF and/or a highest amplitude and/or a smallest AoA and AoD difference, and to calculate a difference between the ToF of the direct signal path and a ground-truth ToF to determine a synchronization offset and to correct the ToF measurements for all signal paths by the synchronization offset.

14. The apparatus according to any preceding claim further configured to correct for local oscillator offset.

15. The apparatus according to any preceding claim further configured to correct for carrier frequency offset.

16. The apparatus according to any preceding claim further configured for passive localisation and tracking and further comprising a transmitter for transmitting the wireless signal along the plurality of different paths.

17. The apparatus according to claim 16 wherein the receiver and the transmitter are positioned on a ceiling to ensure a direct path between them exists.

18. The apparatus according to claim 2 further configured to detect a reflection signal from a mobile object by identifying a signal with a non-zero Doppler shift and to use the AoA, AoD and ToF to track a motion of the mobile object.

19. The apparatus according to any one of claims 1 to 15 further configured for active localisation and tracking wherein a transmitter on the target transmits the wireless signal along the plurality of different paths.

20. The apparatus according to claim 2 further configured to determine a direct signal path by identifying the signal path with a shortest ToF and/or a highest amplitude and/or a smallest AoA and AoD difference, and to localise the transmitter by using the ToF of the direct signal path to estimate a distance between the transmitter and the receiver, and using the AoA of the direct path signal to estimate an angle of the transmitter so as to localise the transmitter.

21. The apparatus according to any preceding claim wherein the predefined threshold corresponds to a dynamic range of the apparatus.

22. The apparatus according to any preceding claim wherein the convergence criteria comprises determining when a difference of each parameter for each signal path between two successive iterations is smaller than a pre-defined convergence threshold.

23. The apparatus according to any preceding claim wherein the received signal is constituted by a Wi-Fi signal.

24. A method for localisation and/or tracking comprising: receiving a received signal, the received signal comprising a superposition of multiple signals derived from a wireless signal transmitted from a transmitter along a plurality of different paths; separating the received signal into the multiple signals by: a) estimating initial path parameters by:

1. estimating a number (L) of signal paths in the received signal;

2. estimating parameters for each signal path using an estimator tool; and

3. deriving an initial background noise; b) refining the parameters by:

iii. combining the initial background noise with a reconstructed signal path using current estimated parameters and re-estimating one or more parameters of each signal path using the estimator tool;

iv. re-estimating background noise by re-constructing each signal path using the re-estimated parameters from (i) and subtracting the L re-constructed signal paths from the received signal; and

v. repeating step (i) and (ii) using the re-estimated background noise as the initial background noise until the parameters for each signal path satisfy a convergence criteria; and

c) using the parameters for each signal path to determine a location and/or motion of a target.