MOTION SENSOR FUSION IN INDOOR LOCALIZATION

A method includes receiving at least one wireless signal measurement and motion sensor measurements. The method also includes generating a location estimate based on the at least one wireless signal measurement. The method also includes determining whether a step is present based on the motion sensor measurements. The method also includes, in response to determining that a step is present, determining a step heading offset based on the location estimate and the motion sensor measurements, and determining a step length and heading based on the motion sensor measurements and the step heading offset. The method also includes determining a location of an object based on at least one of (i) the at least one wireless signal measurement or (ii) the step length and heading.

TECHNICAL FIELD

This disclosure relates generally to wireless communications systems. Embodiments of this disclosure relate to methods and apparatuses for motion sensor fusion in indoor localization of an object.

BACKGROUND

Indoor positioning has grown in popularity over the last decade with applications in both smart homes and commercial facilities. While most of the existing indoor positioning techniques (e.g., Bluetooth and WiFi) suffer from poor accuracy, ultra-wide band (UWB) can provide a robust and accurate indoor localization solution. UWB-based localization techniques generally use two-way ranging (TWR) or time-of-arrival (ToA). However, these techniques cannot cater to multiple users at the same time, hence are not very scalable. On the other hand, in downlink time difference-of-arrival (DL-TDoA) the target does not directly communicate with the UWB anchors, but only listens to the downlink messages from the anchors. Hence, DL-TDoA not only serves multiple users at the same time, but also does not pose any privacy concerns.

SUMMARY

Embodiments of the present disclosure provide methods and apparatuses for motion sensor fusion in indoor localization of an object.

In one embodiment, a method includes receiving at least one wireless signal measurement and motion sensor measurements. The method also includes generating a location estimate based on the at least one wireless signal measurement. The method also includes determining whether a step is present based on the motion sensor measurements. The method also includes, in response to determining that a step is present, determining a step heading offset based on the location estimate and the motion sensor measurements, and determining a step length and heading based on the motion sensor measurements and the step heading offset. The method also includes determining a location of an object based on at least one of (i) the at least one wireless signal measurement or (ii) the step length and heading.

In another embodiment, a device includes a transceiver and a processor operably connected to the transceiver. The processor is configured to: receive at least one wireless signal measurement and motion sensor measurements; generate a location estimate based on the at least one wireless signal measurement; determine whether a step is present based on the motion sensor measurements; in response to determining that a step is present, determine a step heading offset based on the location estimate and the motion sensor measurements, and determine a step length and heading based on the motion sensor measurements and the step heading offset; and determine a location of an object based on at least one of (i) the at least one wireless signal measurement or (ii) the step length and heading.

In another embodiment, a non-transitory computer readable medium includes program code that, when executed by a processor of a device, causes the device to: receive at least one wireless signal measurement and motion sensor measurements; generate a location estimate based on the at least one wireless signal measurement; determine whether a step is present based on the motion sensor measurements; in response to determining that a step is present, determine a step heading offset based on the location estimate and the motion sensor measurements, and determine a step length and heading based on the motion sensor measurements and the step heading offset; and determine a location of an object based on at least one of (i) the at least one wireless signal measurement or (ii) the step length and heading.

Before undertaking the DETAILED DESCRIPTION below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document. The term “couple” and its derivatives refer to any direct or indirect communication between two or more elements, whether or not those elements are in physical contact with one another. The terms “transmit,” “receive,” and “communicate,” as well as derivatives thereof, encompass both direct and indirect communication. The terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation. The term “or” is inclusive, meaning and/or. The phrase “associated with,” as well as derivatives thereof, means to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, have a relationship to or with, or the like. The term “controller” means any device, system or part thereof that controls at least one operation. Such a controller may be implemented in hardware or a combination of hardware and software and/or firmware. The functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. The phrase “at least one of,” when used with a list of items, means that different combinations of one or more of the listed items may be used, and only one item in the list may be needed. For example, “at least one of: A, B, and C” includes any of the following combinations: A, B, C, A and B, A and C, B and C, and A and B and C. As used herein, such terms as “1st” and “2nd,” or “first” and “second” may be used to simply distinguish a corresponding component from another and does not limit the components in other aspect (e.g., importance or order). It is to be understood that if an element (e.g., a first element) is referred to, with or without the term “operatively” or “communicatively”, as “coupled with,” “coupled to,” “connected with,” or “connected to” another element (e.g., a second element), it means that the element may be coupled with the other element directly (e.g., wiredly), wirelessly, or via a third element.

DETAILED DESCRIPTION

Aspects, features, and advantages of the disclosure are readily apparent from the following detailed description, simply by illustrating a number of particular embodiments and implementations, including the best mode contemplated for carrying out the disclosure. The disclosure is also capable of other and different embodiments, and its several details can be modified in various obvious respects, all without departing from the spirit and scope of the disclosure. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive. The disclosure is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings.

The present disclosure covers several components which can be used in conjunction or in combination with one another or can operate as standalone schemes. Certain embodiments of the disclosure may be derived by utilizing a combination of several of the embodiments listed below. Also, it should be noted that further embodiments may be derived by utilizing a particular subset of operational steps as disclosed in each of these embodiments. This disclosure should be understood to cover all such embodiments.

FIG.1illustrates an example wireless network100according to various embodiments of the present disclosure. The embodiment of the wireless network100shown inFIG.1is for illustration only. Other embodiments of the wireless network100could be used without departing from the scope of this disclosure.

The wireless network100includes access points (APs)101and103. The APs101and103communicate with at least one network130, such as the Internet, a proprietary Internet Protocol (IP) network, or other data network. The AP101provides wireless access to the network130for a plurality of stations (STAs)111-114within a coverage area120of the AP101. The APs101-103may communicate with each other and with the STAs111-114using Wi-Fi or other WLAN (wireless local area network) communication techniques. The STAs111-114may communicate with each other using peer-to-peer protocols, such as Tunneled Direct Link Setup (TDLS).

Dotted lines show the approximate extents of the coverage areas120and125, which are shown as approximately circular for the purposes of illustration and explanation only. It should be clearly understood that the coverage areas associated with APs, such as the coverage areas120and125, may have other shapes, including irregular shapes, depending upon the configuration of the APs and variations in the radio environment associated with natural and man-made obstructions.

As described in more detail below, one or more of the APs may include circuitry and/or programming to enable motion sensor fusion in indoor localization of an object. AlthoughFIG.1illustrates one example of a wireless network100, various changes may be made toFIG.1. For example, the wireless network100could include any number of APs and any number of STAs in any suitable arrangement. Also, the AP101could communicate directly with any number of STAs and provide those STAs with wireless broadband access to the network130. Similarly, each AP101and103could communicate directly with the network130and provide STAs with direct wireless broadband access to the network130. Further, the APs101and/or103could provide access to other or additional external networks, such as external telephone networks or other types of data networks.

FIG.2Aillustrates an example AP101according to various embodiments of the present disclosure. The embodiment of the AP101illustrated inFIG.2Ais for illustration only, and the AP103ofFIG.1could have the same or similar configuration. However, APs come in a wide variety of configurations, andFIG.2Adoes not limit the scope of this disclosure to any particular implementation of an AP.

The AP101includes multiple antennas204a-204nand multiple transceivers209a-209n. The AP101also includes a controller/processor224, a memory229, and a backhaul or network interface234. The transceivers209a-209nreceive, from the antennas204a-204n, incoming radio frequency (RF) signals, such as signals transmitted by STAs111-114in the network100. The transceivers209a-209ndown-convert the incoming RF signals to generate IF or baseband signals. The IF or baseband signals are processed by receive (RX) processing circuitry in the transceivers209a-209nand/or controller/processor224, which generates processed baseband signals by filtering, decoding, and/or digitizing the baseband or IF signals. The controller/processor224may further process the baseband signals.

Transmit (TX) processing circuitry in the transceivers209a-209nand/or controller/processor224receives analog or digital data (such as voice data, web data, e-mail, or interactive video game data) from the controller/processor224. The TX processing circuitry encodes, multiplexes, and/or digitizes the outgoing baseband data to generate processed baseband or IF signals. The transceivers209a-209nup-converts the baseband or IF signals to RF signals that are transmitted via the antennas204a-204n.

The controller/processor224can include one or more processors or other processing devices that control the overall operation of the AP101. For example, the controller/processor224could control the reception of forward channel signals and the transmission of reverse channel signals by the transceivers209a-209nin accordance with well-known principles. The controller/processor224could support additional functions as well, such as more advanced wireless communication functions. For instance, the controller/processor224could support beam forming or directional routing operations in which outgoing signals from multiple antennas204a-204nare weighted differently to effectively steer the outgoing signals in a desired direction. The controller/processor224could also support OFDMA operations in which outgoing signals are assigned to different subsets of subcarriers for different recipients (e.g., different STAs111-114). Any of a wide variety of other functions could be supported in the AP101by the controller/processor224including motion sensor fusion in indoor localization of an object. In some embodiments, the controller/processor224includes at least one microprocessor or microcontroller. The controller/processor224is also capable of executing programs and other processes resident in the memory229, such as an OS. The controller/processor224can move data into or out of the memory229as required by an executing process.

The controller/processor224is also coupled to the backhaul or network interface234. The backhaul or network interface234allows the AP101to communicate with other devices or systems over a backhaul connection or over a network. The interface234could support communications over any suitable wired or wireless connection(s). For example, the interface234could allow the AP101to communicate over a wired or wireless local area network or over a wired or wireless connection to a larger network (such as the Internet). The interface234includes any suitable structure supporting communications over a wired or wireless connection, such as an Ethernet or RF transceiver. The memory229is coupled to the controller/processor224. Part of the memory229could include a RAM, and another part of the memory229could include a Flash memory or other ROM.

As described in more detail below, the AP101may include circuitry and/or programming for motion sensor fusion in indoor localization of an object. AlthoughFIG.2Aillustrates one example of AP101, various changes may be made toFIG.2A. For example, the AP101could include any number of each component shown inFIG.2A. As a particular example, an access point could include a number of interfaces234, and the controller/processor224could support routing functions to route data between different network addresses. Alternatively, only one antenna and transceiver path may be included, such as in legacy APs. Also, various components inFIG.2Acould be combined, further subdivided, or omitted and additional components could be added according to particular needs.

FIG.2Billustrates an example STA111according to various embodiments of the present disclosure. The embodiment of the STA111illustrated inFIG.2Bis for illustration only, and the STAs112-114ofFIG.1could have the same or similar configuration. However, STAs come in a wide variety of configurations, andFIG.2Bdoes not limit the scope of this disclosure to any particular implementation of a STA.

The STA111includes antenna(s)205, transceiver(s)210, a microphone220, a speaker230, a processor240, an input/output (I/O) interface (IF)245, an input250, a display255, and a memory260. The memory260includes an operating system (OS)261and one or more applications262.

The transceiver(s)210receives from the antenna(s)205, an incoming RF signal (e.g., transmitted by an AP101of the network100). The transceiver(s)210down-converts the incoming RF signal to generate an intermediate frequency (IF) or baseband signal. The IF or baseband signal is processed by RX processing circuitry in the transceiver(s)210and/or processor240, which generates a processed baseband signal by filtering, decoding, and/or digitizing the baseband or IF signal. The RX processing circuitry sends the processed baseband signal to the speaker230(such as for voice data) or is processed by the processor240(such as for web browsing data).

TX processing circuitry in the transceiver(s)210and/or processor240receives analog or digital voice data from the microphone220or other outgoing baseband data (such as web data, e-mail, or interactive video game data) from the processor240. The TX processing circuitry encodes, multiplexes, and/or digitizes the outgoing baseband data to generate a processed baseband or IF signal. The transceiver(s)210up-converts the baseband or IF signal to an RF signal that is transmitted via the antenna(s)205.

The processor240can include one or more processors and execute the basic OS program261stored in the memory260in order to control the overall operation of the STA111. In one such operation, the processor240controls the reception of forward channel signals and the transmission of reverse channel signals by the transceiver(s)210in accordance with well-known principles. The processor240can also include processing circuitry configured to enable motion sensor fusion in indoor localization of an object. In some embodiments, the processor240includes at least one microprocessor or microcontroller.

The processor240is also capable of executing other processes and programs resident in the memory260, such as operations for enabling motion sensor fusion in indoor localization of an object. The processor240can move data into or out of the memory260as required by an executing process. In some embodiments, the processor240is configured to execute a plurality of applications262, such as applications to enable motion sensor fusion in indoor localization of an object. The processor240can operate the plurality of applications262based on the OS program261or in response to a signal received from an AP. The processor240is also coupled to the I/O interface245, which provides STA111with the ability to connect to other devices such as laptop computers and handheld computers. The I/O interface245is the communication path between these accessories and the processor240.

The processor240is also coupled to the input250, which includes for example, a touchscreen, keypad, etc., and the display255. The operator of the STA111can use the input250to enter data into the STA111. The display255may be a liquid crystal display, light emitting diode display, or other display capable of rendering text and/or at least limited graphics, such as from web sites. The memory260is coupled to the processor240. Part of the memory260could include a random-access memory (RAM), and another part of the memory260could include a Flash memory or other read-only memory (ROM).

AlthoughFIG.2Billustrates one example of STA111, various changes may be made toFIG.2B. For example, various components inFIG.2Bcould be combined, further subdivided, or omitted and additional components could be added according to particular needs. In particular examples, the STA111may include any number of antenna(s)205for MIMO communication with an AP101. In another example, the STA111may not include voice communication or the processor240could be divided into multiple processors, such as one or more central processing units (CPUs) and one or more graphics processing units (GPUs). Also, whileFIG.2Billustrates the STA111configured as a mobile telephone or smartphone, STAs could be configured to operate as other types of mobile or stationary devices.

As discussed earlier, while most of the existing indoor positioning techniques (e.g., Bluetooth and WiFi) suffer from poor accuracy, UWB can provide a robust and accurate indoor localization solution. UWB-based localization techniques generally use TWR or ToA. However, these techniques cannot cater to multiple users at the same time, hence are not very scalable. On the other hand, in DL-TDoA, the target does not directly communicate with the UWB anchors, but only listens to the downlink messages from the anchors. Hence, DL-TDoA not only serves multiple users at the same time, but also does not pose any privacy concerns.

DL-TDoA involves a downlink broadcast technology to position the target. The location of the target is calculated from the differences of arrival times measured on pairs of transmission paths between the target and anchors. The anchors are pre-installed and time synchronized and their locations are known to the target. The anchors send signals with timestamps to the target. The target uses the timestamps of the signals received from different anchors to calculate the time difference of arrival from different anchors.

For example,FIG.3illustrates an example network300in which DL-TDoA can be performed according to various embodiments of the present disclosure. As shown inFIG.3, the network300includes a target301disposed in proximity to multiple anchors302. The target301and the anchors302could represent various components of the wireless network100, such as the STA111and the AP101. The location of the target301is calculated by determining the point of intersection of the hyperbolas303representing the distance differences (that is time difference of arrival multiplied by the speed of light). The target301uses measurements from at least four anchors302(three DL-TDoA measurements) to calculate its location. Note that the location of the target301is calculated at the target301itself. The advantage of this technique is that multiple targets301can listen to the downlink messages from the anchors302, making the solution scalable.

Let the distance difference (obtained by multiplying the time difference of arrival with the speed of light) between anchors i and j be represented as dij. The value dijis the difference between the distance of anchor i from the target301and the distance of anchor j from the target301. If anchor k is the initiator or the reference anchor, a ranging round will involve obtaining the distance difference between all anchors302and anchor k. For example, if anchor Al is the reference anchor for the network300, the measurements obtained in the ranging round will be d21, d31and d41. The location of the target301is the intersection point of the hyperbolas303representing these distance differences. The time between two ranging rounds is referred to as the ranging interval.

In practice, due to measurement errors, the hyperbolas303often do no intersect at a single point. Multipath also leads to huge errors in the measurements. Hence, an optimizer, for example least squares, Levenberg Marquardt (LM) or gradient descent algorithm, can be used to calculate the location of the target301. However, these solutions need at least 3 UWB DL-TDoA measurements to localize the target301. Hence, although UWB is capable of providing a highly accurate solution under controlled environments, in a more practical scenario, the quality and quantity of received measurements may be impacted by multipath and occlusion. Localization cannot be performed when there is complete absence of UWB measurements due to occlusion.

To address these and other issues, this disclosure provides systems and methods for motion sensor fusion in indoor localization of an object. As described in more detail below, the disclosed embodiments feature a motion sensor-assisted solution to perform robust and accurate indoor localization using UWB DL-TDoA measurements. That is, the disclosed embodiments combine UWB DL-TDoA measurements with motion sensor measurements to provide a UWB localization technique that is accurate (e.g., by also taking into account sensor information) and simultaneously robust to multipath and occlusion.

Note that while some of the embodiments discussed below are described in the context of smart phones, these are merely examples. It will be understood that the principles of this disclosure may be implemented in any number of other suitable contexts or systems, including other fixed or portable electronic devices (e.g., tablets, laptops, and the like).

Before describing the disclosed techniques in detail, it may be helpful to provide the following contextual information.

Pedestrian Dead Reckoning/Step and Heading System

Dead reckoning is a method of estimating the position of a moving object using the object's last known position and adding incremental displacements on top of that. Pedestrian dead reckoning, or PDR, refers specifically to the scenario where the object in question is a pedestrian walking in an indoor or outdoor space. With the proliferation of sensors inside smart devices (e.g., smartphones, tablets, smart watches, and the like), PDR has naturally matured to supplement wireless positioning technologies that have been long supported by these devices, such as Wi-Fi, cellular service, and UWB. The inertial measurement unit (IMU) is a device that combines numerous sensors with functional differences. For example, the accelerometer measures linear acceleration, the gyroscope measures angular velocity, and the magnetometer measures the strength and direction of the magnetic field. These three sensors can detect motion and estimate its velocity, i.e., speed and heading. PDR is also referred to as the Step and Heading (SH) system.

Extended Kalman Filter

A Kalman filter recursively estimates the state of a dynamical system from a sequence of measurements obtained over time and an assumption of state trajectory. It assumes an underlying system that is modeled by two linear equations: a state transition/motion equation and a measurement/observation equation. The motion equation describes the evolution of the state of the system and relates the current state to a previous state as follows:

where xkis the current state, xk-1is the last state, Akis the state transition matrix, ukis the current input, Bkis the control/input matrix, and vk˜N(0,Qk) is the process noise which represents uncertainty in state.

The measurement equation relates the current observation to the current state as follows:

where ykis the latest observation, Hkis the observation matrix, and wk˜N(0,Rk) is the observation noise.

At each time index k, the Kalman filter estimates the state of the system by applying a prediction step followed by an update step. The outcome of these two steps is the state estimate {circumflex over (x)}kat time index k and its covariance matrix Pk, which are in turn used to estimate the states at later points in time.

In the prediction step, the Kalman filter predicts the current state xk|k-1(a priori estimate) from the most recent state estimate {circumflex over (x)}k-1, its covariance Pk-1, and any inputs using the motion equation as follows:

In the update step, the Kalman filter uses the latest observation to update its prediction and obtain the (a posteriori) state estimate {circumflex over (x)}kand its covariance Pkas follows:

where Kkis the Kalman gain and is a function of the a priori estimate covariance Pk|k-1, observation matrix Hk, and observation noise covariance matrix Rk.

The extended Kalman filter (EKF) is a work-around to handle non-linearities in the motion or measurement models. If the motion or measurement equations are not linear, the Kalman filter could not be used unless these equations are linearized. Consider the following non-linear motion and measurement equations:

where fkand hkare non-linear functions. The EKF applies the predict and update steps as follows:

For the EKF, the prediction step includes the following:

For the EKF, the update step includes the following:

The state estimate {circumflex over (x)}kand its covariance Pkare propagated to track the state of system.

In the context of localization, the state is the target 2D location. In the context of UWB DL-TDoA based indoor localization, the observations are UWB distance difference measurements, which are calculated from TDoA measurements by multiplying it with the speed of light.

FIG.4illustrates an example system400for performing indoor localization according to various embodiments of the present disclosure. The system400includes a background tracking filter to infer step heading and displacement within a time window when UWB measurements are present. The system400can perform online heading calibration to find an offset in step heading obtained from sensor readings. In addition, the system400can perform online step size parameter calibration to find the parameter value to calculate step length or size. The embodiment of the system400shown inFIG.4is for illustration only. Other embodiments of the system400could be used without departing from the scope of this disclosure. For ease of explanation, the system400will be described as being implemented in the network300ofFIG.3, such as in the target301. However, the system400could be implemented in any other suitable device(s) or system(s).

As shown inFIG.4, the system400includes a localization block401and a sensing block402. The localization block401receives UWB measurements405from one or more anchors302. In some embodiments, the UWB measurements405include UWB DL-TDoA measurements. If the localization block401receives a sufficient number (e.g., at least three) of UWB DL-TDoA measurements, the localization block401uses an optimizer along with a tracking filter, or a tracking filter alone, to track the location420of the target301. However, it is possible to encounter cases where no UWB measurements405are received by the localization block401, either due to occlusion or due to the target301leaving the coverage area of the anchors302. In such cases, the state of the tracking filter is not updated.

It is also possible that the UWB measurements405received by the localization block401are of poor quality, possibly impacted by multipath. In such scenarios, the tracking filter may not generate the correct output. In order to deal with scenarios of no UWB measurements405or poor quality UWB measurements405, the localization block401uses information from the sensing block402to track the target301.

The localization block401takes the UWB measurements405and step information415from the sensing block402as input to obtain the location output420. The localization block401can use a tracking filter or an optimizer and tracking filter to fuse the UWB measurements405and sensor data to localize the target301. Some examples of optimizers that can be used to localize the target301based on UWB measurements405include least square, Levenberg Marquardt (LM), and gradient descent algorithm. A tracking filter (for example, an Extended Kalman Filter (EKF) or particle filter) can be used to fuse UWB measurements405and sensor data to localize the target301.

The sensing block402uses motion sensor measurements410to detect steps as the user walks. The length/size and direction/heading of the steps are calculated using these measurements and, given the current location of the target301, they are used to calculate its next location.

FIG.5illustrates further details of an example sensing block402according to various embodiments of the present disclosure. As shown inFIG.5, the sensing block402takes the motion sensor measurements410(which can be IMU measurements) as input to a step detection operation505, which is performed to detect a user step. In some embodiments, the step detection operation505uses linear acceleration information obtained from the motion sensor measurements410.FIGS.6A and6Billustrate charts600and650showing example linear acceleration information that can be used for step detection according to various embodiments of the present disclosure. Every time a peak in the linear acceleration is detected by an IMU accelerometer, as shown by the dotted vertical lines inFIGS.6A and6B, a step is signaled. In some embodiments, the magnitude of linear acceleration is used for peak detection, such as shown inFIG.6A. In other embodiments, a particular component of the linear acceleration (e.g., the z-component, such as shown inFIG.6B) is used depending on the way the target301is held.

Whenever a step is detected, the sensing block402performs a step size and heading calculation510to calculate the size of the step and its heading. The output of the step size and heading calculation510is the step information415, which can be provided to the localization block401.

In the step size and heading calculation510, the step size sncan be computed according to the Weinberg model as follows:

where amaxand aminare the maximum and minimum acceleration since the last peak was detected, and α∈[0, 1] is a user-dependent scaling coefficient referred to as the Weinberg parameter or the step size parameter. The parameters amaxand aminare obtained by finding the peaks and valleys in the acceleration as shown in the example chart700ofFIG.7. In some embodiments, a fixed value for the step size parameter (e.g., α=0.4) based on experimentation is used. In other embodiments, other ways of computing the step size sninclude Kim's model, which uses the average of acceleration in each step to compute step size, and Scarlet model, which is an empirical model.

In the step size and heading calculation510, the step heading can be obtained using the motion sensor provided orientation, which is computed using linear acceleration and magnetometer readings, or it can be obtained using gyroscope readings.

In some embodiments, gyroscope readings are integrated to obtain the step heading. The heading is initialized with orientation from the motion sensor at the start of the trajectory. If {circumflex over (θ)}nis the heading at step n, it is calculated as:

where tsnrepresents the duration of nthstep. The angular velocity obtained over the duration of the step is integrated and added to the heading at the time of the previous step to obtain the current heading. In some embodiments, tilt compensation is applied to the angular velocity using rotation quaternions before integrating it to obtain the heading.

In some embodiments, orientation ϕ obtained directly from the motion sensor is used to calculate the step heading using the following equation:

whereϕnis the average orientation over the duration of nthstep.

The sensing block402can also perform an online heading calibration515, in which the sensing block402calculates an offset in step heading obtained from sensor readings. As discussed above, the step heading can be obtained from IMU orientation and gyroscope readings. However, there could be some offsets in the step heading compared to the true heading. It is therefore helpful or necessary to calibrate the offset since the localization block401is driven by step size and heading when UWB measurements are lost. Further details of the heading calibration515are provided below.

In some embodiments, a background random walk EKF (EKF-RW)520is used along with the sensor readings to calculate the heading offset online. The background EKF-RW520uses UWB measurements405, whenever they are available, to generate location estimates. The background EKF-RW520will now be explained in greater detail.

A random walk EKF estimates the state xk=[xkyk]Tby using a motion model given as:

where (xk>yk) represents the 2D location of the target301and xk-1is the previous state of the EKF representing the previous 2D location of the target301. The term vk˜N(0,Qk) represents the process noise, which can be given by the following:

where Δt=tk−tk-1is the time difference between consecutive steps and op is the variance in the speed of the target301.

The measurement model maps the current UWB measurements405, which can include the distance difference measurements (dij) from anchor pair i and j (among the anchors302), to the current state using the measurement equation:

Here, dijrepresents the difference in distance di of the target301from anchor i and its distance djfrom the anchor j. The term dijis a measurement obtained by multiplying the TDoA from anchors i and j with the speed of light. In Equation (6), xiand xjrepresent the 2D location of the anchors i and j, respectively, and wk˜(μk, Rk) represents the measurement noise.

Considering a fixed value hAfor the height of the anchors i and j and approximate value hTfor the height of the target301, the mapping between the state and measurements is given as:

Equation (6) is linearized into the following equation:

where ykis a vector of measurements dijavailable from different pairs of anchors302, and Hkis the Jacobian matrix obtained by taking the partial derivative of dijwith the state vector. The row vector of Hkcorresponding to the measurement dijis given as:

The state of the background EKF-RW520is updated every time UWB measurements405are received. The state remains the same if no measurements are received.

In order to improve the accuracy of state estimation, outlier removal is performed on the UWB measurements405before they are used by the background EKF-RW520. Outlier removal is performed in between the prediction and update steps of EKF-RW. To perform outlier removal, first the prediction step of the tracking filter is executed to obtain an initial location estimate of the next location of the target301. An estimate of distance difference measurements is calculated at the predicted location, and these are compared against the measured distance difference measurements. If the absolute difference between an estimated and measured distance difference measurement lies above a threshold, the distance difference measurement is labeled as an outlier and is not used in the update step of tracking filter.

As discussed above, the heading offset should be calibrated since the localization block401is driven by step size and heading when UWB measurements are lost. The value of step heading is obtained as:

where Δθ is the offset in the heading, that is the difference between the calculated heading and true heading.

As described above, the sensing block402can use the background EKF-RW520to compute the heading offset. The background EKF-RW520runs whenever good UWB measurements405are available. Hence, the assumption here is that the sensing block402starts the trajectory estimation from a good measurement zone. A set of conditions are used to trigger the heading calibration515. These conditions include (i) whether the target301is moving in a straight line based on the motion sensor measurements410, (ii) whether there are a sufficient number of UWB measurements405satisfying a condition (e.g., good UWB measurements405), and (iii) whether the target301is in motion based on displacement data. When all of these conditions are satisfied, the heading calibration515is triggered and the heading offset is computed. When the heading calibration515is triggered, the estimated heading is obtained from the location estimates obtained from the background EKF-RW520in the straight-line window. This estimated heading is compared to the heading information obtained from the motion sensor measurements410to calculate the heading offset.

FIG.8illustrates an example process800that can be performed in the heading calibration515according to various embodiments of the present disclosure. As shown inFIG.8, the process800starts with the sensing block402initializing parameters tturnand tcalibwith the initial timestamp at the start of the trajectory. The parameter tturnrefers to the timestamp of the last turn made, and the parameter tcalibrefers to the timestamp of when the last time heading calibration was performed.

At operation801, the sensing block402checks for a straight-line motion by checking the gyroscope readings for last k seconds (e.g., k=5). The angular velocity obtained from the gyroscope is expected to be low in a straight line motion, hence the check for straight line is done by checking if a predetermined percentile (e.g., the 90th percentile) of gyroscope readings is less than a predetermined threshold value Thcalib(e.g., 30°). At operation803, the sensing block402checks if there are a sufficient number of UWB measurements405(threshold=Ncalib) received in the last k seconds. At operation805, the sensing block402checks if there is non-zero motion in last k seconds by checking the displacement (threshold=Dcalib) based on background EKF-RW in the last k seconds. At operation807, the sensing block402checks if sufficient time has elapsed since the last calibration was done and last turn was made. This is checked by comparing the difference between the current timestamp and tcaliband tturnwith thresholds tth1and tth2, respectively. If all these conditions are satisfied, then heading calibration is triggered, as shown at operation809. The heading offset is obtained by subtracting the implied heading {circumflex over (θ)}RW(computed through linear regression of background EKF-RW estimates {xk} in the last k seconds) with the heading obtained from integrated gyroscope readings, as given by the following equation:

In parallel, at operation811, the sensing block402checks another condition to detect a turn. This condition is checking if the 90th percentile of gyroscope readings is above a threshold Thturn. If so, then a turn is detected, as indicated at operation813. The heading calibration515is continuously performed throughout the course of the trajectory whenever the trigger conditions are satisfied.

FIG.9illustrates another example process900that can be performed in the heading calibration515according to various embodiments of the present disclosure. As shown inFIG.9, the process900is performed as a two-step calibration that includes coarse calibration and fine calibration. At operation901, the parameter afineis initialized to zero. This is a parameter to ensure that coarse calibration is performed only once. The coarse calibration is only performed once as the first calibration during the course of trajectory estimation. The trigger conditions for coarse calibration are relaxed, that is Thcalibis a bigger value and Ncalibis smaller. The purpose of the coarse calibration is to have an estimate of the heading offset even if the stricter trigger conditions of fine calibration are not met during the entire course of the trajectory. At operation903, the sensing block402determines if afineis equal to zero. If so, then at operation905, the sensing block402sets the trigger thresholds for coarse calibration to be {Thcalibcoarse, Ncalibcoarse.}. If not, then at operation907, the sensing block402sets the trigger thresholds for fine calibration to be {Thcalibfine, Ncalibfine}.

At operation909, the sensing block402determines if the trigger conditions (either the coarse trigger thresholds or the fine trigger thresholds) are met. If the trigger conditions are met, then at operation911, the sensing block402performs the heading calibration (either the coarse calibration or the fine calibration, according to the threshold values set in operation905or907). Once the coarse calibration is performed, the sensing block402sets the parameter afineto be equal to one at operation913. This ensures that the sensing block402does not enter this coarse calibration state again. Whenever the stricter trigger conditions are met, the fine calibration is performed along the remaining course of the trajectory.

FIG.10illustrates yet another example process1000that can be performed in the heading calibration515according to various embodiments of the present disclosure. As shown inFIG.10, the process1000is substantially similar to the process800ofFIG.8, except that orientation information obtained directly from the motion sensor is used to calculate the heading, rather than gyroscope readings. In the process1000, straight-line motions are detected by comparing the variance of orientation in a prior time period (e.g., the last k seconds) against a threshold Thϕcalib. Similarly, turns are detected by comparing the variance of orientation in the last k seconds against another threshold Thϕturn.

FIG.11illustrates further details of another example sensing block402according to various embodiments of the present disclosure. As shown inFIG.11, the sensing block402performs both heading and step size parameter calibration. That is, instead of just the heading calibration515(as inFIG.5), here the sensing block402performs a step size and heading calibration1115.

The step size and heading calibration1115includes the techniques of the heading calibration515, and also includes a step size parameter calibration. The step size parameter calibration is performed using the same trigger conditions as the heading calibration. Step calibration is also performed looking at background EKF-RW estimates {xk} in the last k seconds. For every step detected in the last k seconds, the total displacement d during the step duration is obtained using the estimates of background EKF-RW, such as by the following.

where tsnis the duration of nthstep and {circumflex over (x)}tis the estimate of background EKF-RW at time t.

If a0is the original set value of the step size parameter, the updated step size parameter value based on step n is obtained as:

where snis the size of nthstep.

An updated {circumflex over (α)} is calculated for each step in the last k seconds. The updated value of step size parameter (αupdated) is obtained by taking the average of all {circumflex over (α)} corresponding to the steps in last k seconds.

In some embodiments, step size parameter calibration is performed once during the course of the trajectory. In other embodiments, step size parameter calibration can be performed every time the trigger conditions for calibration are met.

AlthoughFIGS.3through11illustrate example techniques for motion sensor fusion in indoor localization of an object and related details, various changes may be made toFIGS.3through11. For example, various components inFIGS.3through11could be combined, further subdivided, or omitted and additional components could be added according to particular needs. In addition, while shown as a series of steps, various operations inFIGS.3through11could overlap, occur in parallel, occur in a different order, or occur any number of times. In another example, steps may be omitted or replaced by other steps.

FIG.12illustrates a flow chart of a method1200for motion sensor fusion in indoor localization of an object according to various embodiments of the present disclosure, as may be performed by one or more components of the network300(e.g., the target301or the anchors302). The embodiment of the method1200shown inFIG.12is for illustration only. One or more of the components illustrated inFIG.12can be implemented in specialized circuitry configured to perform the noted functions or one or more of the components can be implemented by one or more processors executing instructions to perform the noted functions.

As illustrated inFIG.12, the method1200begins at step1201. At step1201, an electronic device receives at least one wireless signal measurement and motion sensor measurements. This could include, for example, the target301receiving at least one UWB measurement405and motion sensor measurements410(e.g., from an IMU). In some embodiments, the UWB measurements405are UWB DL-TDoA measurements.

At step1203, the electronic device generates a location estimate based on the at least one wireless signal measurement. This could include, for example, the target301using the background EKF-RW520to generate location estimates, such as shown inFIG.5.

At step1205, the electronic device determines whether a step is present based on the motion sensor measurements. This could include, for example, the target301performing the step detection operation505to detect a step, such as shown inFIG.5.

At step1207, in response to determining that a step is present, the electronic device determines a step heading offset based on the location estimate and the motion sensor measurements, and determines a step length and heading based on the motion sensor measurements and the step heading offset. This could include, for example, the target301performing the heading calibration515to determine the heading offset, and performing the step size and heading calculation510to obtain the step length and heading, such as shown inFIG.5.

At step1209, the electronic device determines a location of an object based on at least one of (i) the at least one wireless signal measurement or (ii) the step length and heading. This could include, for example, the target301determining the location of the target301and generating a location output420, such as shown inFIG.4.

AlthoughFIG.12illustrates one example of a method1200for motion sensor fusion in indoor localization of an object, various changes may be made toFIG.12. For example, while shown as a series of steps, various steps inFIG.12could overlap, occur in parallel, occur in a different order, or occur any number of times.