REALIZING ENTERPRISE-GRADE LOCALIZATION USING WIFI 802.11mc FINE TUNE MEASUREMENT

A method for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters is presented. The method includes enabling a plurality of access points to range with a plurality mobile devices handled by a plurality of users within an enterprise environment, tracking a mobile device of the plurality of mobile devices using onboard sensors as the mobile device travels within the enterprise environment, measuring a plurality of ranges with at least three access points of the plurality of access points at various points along a trajectory, and combining information related to the plurality of ranges and the trajectory to predict a range offset of the mobile device such that the mobile device itself self-calibrates all its range offsets on-demand.

BACKGROUND

Technical Field

The present invention relates to WiFi localization solutions and, more particularly, to realizing an enterprise-grade localization using an 802.11 mc fine tuning measurement.

Description of the Related Art

WiFi localization solutions received a significant boost with the introduction of the Fine Time Measurement (FTM) ranging protocol in the IEEE 802.11-2016 standard (that is, the 802.11 mc standard). The ability to orchestrate WiFi ranging (distance measurement between two devices through FTM) from user-space on commercial off-the-shelf devices has opened the door for third-party service providers to develop enterprise-grade solutions that leverage pre-deployed infrastructure (e.g., WiFi access points (APs)) and end-user devices like smartphones and tablets, to localize both humans and assets in large indoor spaces. Unlike other evolving radio frequency (RF) technologies like Ultra-Wide Band (UWB) that also offer ranging capability, WiFi devices are omnipresent, have a larger coverage area and better penetrability (lower operating frequency and higher power than UWBs), making WiFi FTM more convenient and practical for enterprise-grade indoor solutions. Further, most modern devices already implement WiFi FTM.

SUMMARY

A method for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters is presented. The method includes enabling a plurality of access points to range with a plurality mobile devices handled by a plurality of users within an enterprise environment, tracking a mobile device of the plurality of mobile devices using onboard sensors as the mobile device travels within the enterprise environment, measuring a plurality of ranges with at least three access points of the plurality of access points at various points along a trajectory, and combining information related to the plurality of ranges and the trajectory to predict a range offset of the mobile device such that the mobile device itself self-calibrates all its range offsets on-demand.

A non-transitory computer-readable storage medium comprising a computer-readable program for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters is presented. The computer-readable program when executed on a computer causes the computer to perform the steps of enabling a plurality of access points to range with a plurality mobile devices handled by a plurality of users within an enterprise environment, tracking a mobile device of the plurality of mobile devices using onboard sensors as the mobile device travels within the enterprise environment, measuring a plurality of ranges with at least three access points of the plurality of access points at various points along a trajectory, and combining information related to the plurality of ranges and the trajectory to predict a range offset of the mobile device such that the mobile device itself self-calibrates all its range offsets on-demand.

A system for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters is presented. The system includes a plurality of access points ranging with a plurality mobile devices handled by a plurality of users within an enterprise environment for tracking a mobile device of the plurality of mobile devices using onboard sensors as the mobile device travels within the enterprise environment, measuring a plurality of ranges with at least three access points of the plurality of access points at various points along a trajectory, and combining information related to the plurality of ranges and the trajectory to predict a range offset of the mobile device such that the mobile device itself self-calibrates all its range offsets on-demand.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

The WiFi consortium envisions a larger scope and ecosystem for location-aware WiFi services under the umbrella of WiFi-aware networking. However, to date, there have not been compelling commercial solutions that leverage WiFi Fine Tune Measurement (FTM) for localization. Consequently, it is not clear whether WiFi FTM is ready for prime-time localization at an enterprise-scale.

Previous works have conducted experimental studies to understand WiFi FTM in indoor environments. Being preliminary in nature, WiFi FTM has largely focused on its ranging accuracy in limited experimental settings between homogeneous WiFi devices (with similar Intel WiFi network interface cards (NICs)). To establish FTM’s viability in delivering a practical localization solution, the ability of its ranging primitive needs to be understood to inter-operate seamlessly and accurately with heterogeneous devices, lest there can be no “enterprise-grade” solution. To this end, the exemplary methods present one of the first comprehensive experimental studies that puts the spotlight on heterogeneity in multiple dimensions (device, spectrum, environment) in answering this question.

The extensive measurement study conducted employs multiple off-the-shelf commercial devices (e.g., 6 WiFi access points (APs) and 3 WiFi clients from different vendors) under different spectrum (ranging bandwidth and channel) and environmental (line of sight (LoS) vs. near line of sight (NLoS); cluttered vs. open indoor settings) conditions.

The key inferences from the study include:

FTM ranging suffers from fixed (independent of the AP-client distance) range offsets that vary significantly for different AP client pairs.

The range offsets for a given AP-client pair can vary substantially across different ranging channels (up to 3.6 m) and channel bandwidths (up to 16.2 m).

Ranging errors are largely amplified in NLoS conditions. Additionally, unlike in LoS conditions, wider channels in NLoS conditions do not always yield more accurate ranges.

While the presence of fixed offsets in estimated ranges was observed before, their reasons were unknown and offsets were addressed through a-priori calibration between a fixed set of devices. However, the present extensive study was conducted across multiple dimensions and has exposed the scale and impact of these offsets, while also shedding light on their potential causes. It is found that to compensate for the impact of wireless multi-path and direct-path detection delays, device vendors employ proprietary compensation algorithms. Indeed, there is room in the standard for vendors to advertise for such compensation. While a common vendor for the AP and client can have a synergistic compensation algorithm, this is not possible to address and scale across vendors, resulting in offsets that range from -12 m to 14 m, resulting in localization errors as large as 20 m. Indeed, this poses a fundamental issue in leveraging FTM for practical localization in enterprises, since these offsets cannot be pre-calibrated and accounted for.

This points to the conclusion that WiFi FTM is not ready for prime-time enterprise-scale localization.

However, albeit such unfortunate result, it is believed that the door for leveraging FTM is not completely closed. As a remedy, the exemplary embodiments propose a simple but effective over-the-top (OTT) auto-calibration solution that allows every WiFi device, when it enters an enterprise environment, to self-calibrate its offsets, rendering WiFi FTM useful for localization. The exemplary approach follows the notion of simultaneous localization and calibration, whereby the mobility of the client device is used to measure multiple ranges to the AP at different points on the client’s trajectory, which are then combined with its own mobility (informed by its inertial sensors) to jointly solve for its own location, while compensating for the unknown offsets. This solution can be easily deployed as an Android or iOS application on client devices, enabling seamless integration.

The contributions include an extensive measurement study of WiFi FTM conducted to assess its practical viability for enterprise-grade localization, with heterogeneity across various operational parameters as the focus. The exemplary embodiments propose WiLoc, an OTT auto-calibration solution to remedy the fundamental challenge in inaccurate range estimations, demonstrating that it is still possible to deliver useful localization (median accuracy of ~2 m) with WiFi FTM, notwithstanding its large range offsets.

The exemplary work is the first to explore the shortcomings of WiFi FTM in broader enterprise settings and discuss a remedy toward a practical localization solution.

The IEEE 802.11 mc FTM ranging protocol enables two WiFi devices with asynchronous clocks to cooperatively estimate the distance between themselves by measuring a Round Trip Time (RTT). To measure the RTT, a station (the initiator110) and an AP (the responder120) exchange bursts of messages with each other, as shown in the diagram100ofFIG.1.

Thereafter, the RTT (for k bursts) is calculated as follows:

Once RTT is calculated, distance can be computed as D = ½ ∗ RTT ∗ C, where C is the speed of light.

The success of the FTM ranging protocol lies in the nodes’ ability to accurately record the ToA and ToD. However, in practice, an implementation may capture the ToD earlier or later than when the signal arrives at the transmit antenna connector resulting in an offset. Similarly, a significant amount of time can elapse from when the preamble arrives at the receive antenna (actual ToA) to when the node detects the frame, synchronizes with its logical structure, and computes the ToA. The standard requires devices to compensate for this delay in ToA computation by subtracting an offset from the computed ToA. However, the standard does not provide any guidance on how exactly this offset should be determined leading vendors to implement their own proprietary algorithms to correct the ToA/ToD estimations that often leads to over-or-under compensation resulting in either an inflated or a deflated range. The problem is further exacerbated when two different vendors’ devices interact, with each device’s (incorrect) ToA/ToD estimations (disproportionally) contributing to the eventual range offset.

The 802.11 mc frame has specific fields for devices (both STAs and APs) to indicate to their ranging peer any potential error in ToA and ToD estimations (ToA Error, ToD Error fields, as shown inFIG.2; elements210,220). The standard provides this option to precisely capture a device’s confidence in offset-prediction. However, in the measurement study, it was found that none of the commercial devices actually use these options.

Interestingly, it is observed that the range offsets for a pair of devices is constant for a particular central frequency (channel) and channel bandwidth (e.g., 20/40/80 MHz) combination used during the FTM protocol. It is believed that the devices use constant offset values depending on the channel and bandwidth employed (to account for the difference in processing overheads in wider channels) to compensate for the incorrect ToA/ToD estimations. To understand the scale of the range offsets problem, a detailed measurement study with multiple off-the-shelf devices was conducted.

A measurement study conducted utilizes 6 different WiFi APs - ASUS RTACRH13, Linksys Velop, Google Nest’s Mesh AP system (consisting of three APs in a mesh network, which can be referred to as Google 1, Google 2 and Google 3) and a Compulab Fitlet AP, and 3 different STAs, that is, Google Pixel 5, Xiaomi Mi Note 10, and a Compulab Fitlet acting as a STA. The WiFi chipsets employed by each of these devices are different from each other and all devices support channel widths up to 80 MHz. Note that certain vendors (e.g., Google®) do not allow manual channel and bandwidth selection. Hence, for these devices, only the channel and bandwidth configuration chosen by the device for FTM ranging are employed.

Regarding data collection, to enable seamless FTM ranging on Fitlet devices, the Linux OS’s iw utility was modified using a patch. For Android smartphones, an app that uses the WiFi Ranging Android API was written to send FTM requests periodically (e.g., every 30 ms). Data was collected in both LoS and NLoS scenarios, in diverse indoor environments inside an office building and a university campus: a large, carpeted area, a lab with benches and equipment, a building lobby with furniture, and a large empty open area with tall glass windows.

Regarding LoS conditions, the WiFi FTM ranging performance with static STAs in LoS scenarios was evaluated. For each AP-STA pair, a static STA was placed at various distances from 1 m to 50 m, and the FTM ranges were recorded for a channel and bandwidth (channel 36 / 80 MHz) that is supported by all the AP-STA pairs. The true distance between the client and the AP for Ground Truth (GT) was physically measured. The GT range was used to calculate the range offsets. Two observations were made, that is, there is a fixed range offset, independent of the distance between the AP and the STA and range offsets vary significantly for different AP-client pairs, thus showing how extreme and disparate the offset problem is across heterogeneous devices,

Regarding the impact of the operating frequency, it was then evaluated how range offsets vary based on the operating channel (for a fixed channel bandwidth). It is observed that devices implement a frequency dependent offset (for ToA/ToD correction). However, the variance in these offsets for a given AP-client pair is not very large. The maximum offset difference across different channels, observed with a Xiaomi client and ASUS AP, is 3.6 m.

Regarding the impact of the channel bandwidth, it was shown how range offsets vary for different channel bandwidths (same central frequency), for a given AP-STA pair. The range offsets for the same pair of devices can vary by as much as 16.2 m (for ASUS AP-Fitlet Client) or as little as 1.2 m (for Fitlet AP-Pixel 5 Client).

Regarding the accuracy of the FTM ranges with offset correction, the accuracy of the FTM ranges, with (manual) offset correction was evaluated. For the data previously collected, the offset is estimated as the mean difference between the measured range and the GT range and that is used as the offset value. Subtracting this offset from the measured range gives the range error. It is observed that across device pairs, in the median case, the range errors are ~50 cm, ~30 cm, and ~10 cm, suggesting that FTM ranges in LoS are highly accurate and can aid in accurate localization, provided that the disparate range offsets are resolved.

Regarding NLoS conditions, the FTM ranging accuracy in NLoS conditions was evaluated. To determine the FTM ranging errors, the range offset is manually discounted, which is calculated from the LoS measurements, from the measured range, and the accuracy of the measured ranges. Unlike in LoS, the range errors (for a given channel and bandwidth) are amplified in NLoS conditions. The drop in channel quality, combined with the devices’ inability to exactly identify the Channel Impulse Response peaks (a common issue for multipath signals) further degrades the ToA estimations leading to large range errors. The 80 MHz channel bandwidth, which had the most accurate range estimations in LoS, suffers the most in NLoS due to fact that a signal using wider bandwidth (e.g., 80 MHz) attenuates faster than the same signal spread over a narrower bandwidth (e.g., 20 MHz). More importantly, it was determined that for localization solutions implementing FTM ranging, a wider channel does not always yield accurate ranges.

Regarding LoS versus NLoS FTM ranging, and the impact on localization, given the high inaccuracy of NLoS range estimations, any localization system that uses FTM ranges needs to be able to distinguish LoS ranges from NLoS ranges, so that it can filter out the NLoS ranges.

To make that classification, a simple machine learning model is employed, such as Random Forest, and three inputs are used, that is, last n ranges, last n RSSI values, and variance in last n ranges. The exemplary methods attempt to accurately classify whether the ranges are with an AP in LoS or NLoS. Even using only 5 range samples obtained every 30 ms, the model can correctly classify LoS and NLoS ranges in 83.5% of the cases. Furthermore, assuming the user stays in LoS/NLoS for longer, taking a larger number of range/RSSI samples spaced further apart leads to even higher accuracy, up to 99.5% when considering the previous 20 range/RSSI values obtained every second.

To summarize, it was determined that the range offsets depend on the AP-STA pair, the channel width, and the channel (frequency). Given the plethora of different vendors for WiFi devices and the fact that the devices’ spectrum configurations change frequently, it becomes practically impossible to have an offline solution to this problem. The only way to address this challenge is via an on-demand, real-time, online solution.

In addition, the ranging accuracy deteriorates significantly as the user moves from LoS to NLoS conditions. Thus, it becomes important to design a system that can distinguish between LoS and NLoS ranges, so that it can filter out the NLoS ranges and use only the LoS ranges.

To address the range offset problem in a practical manner, the exemplary methods propose WiLoc, a novel over-the-top (OTT) solution that can be deployed as an application on end-user devices like smartphones and that enables these devices to self-calibrate their range offsets with multiple APs when they enter an enterprise environment, without any human input. At a high level, WiLoc follows the notion of simultaneous localization and calibration. WiLoc employs Euclidean geometry leveraging the user’s mobility, computed using onboard inertial sensors, to measure the ranges at various points of its trajectory and combines both trajectory and range information to solve for the range offset.

WiLoc300assumes an AP310to be statically placed at (xAPyAP), (FIG.3), and the user to start at (xC, yC) and move continuously in a random direction with respect to the AP310. At each time-interval t (e.g., t=1 s), the STA320performs FTM ranging to measure a range Rp, where Rp= rp+ δ with δ being the range offset. To solve for δ, WiLoc300employs two approaches, that is, WiLoclinand WiLocquad. While WiLoclinuses a system of linear equations to solve for δ, WiLocquademploys a quadratic solver. The linear approach is less complex, but results in a less accurate estimation of δ, while the quadratic approach is more complex, but offers more accurate estimation.

The first approach, WiLoclin(854;FIG.4), formulates the problem of solving for δ using a series of linear equations. WiLoclinassumes (xAP, yAP) = (0,0) for the AP location.

Given the STA’s initial position (xC, yC):

As the user moves, at each time interval t, the STA320reaches a new position p, resulting in an additional equation:

where, αiis computed by measuring the heading (magnetometer) information, and di(displacement) is estimated via the STA’s inertial sensors (accelerometer, magnetometer).

Now, for each new equation (2) obtained at every time interval t, the exemplary methods subtract equation (1) from it. This linearizes the system of equations with three unknown variables (xC, yC, and δ). Solving for the three unknowns requires at-least three equations (3 seconds if t = 1), with additional equations increasing the accuracy of the solution (δ).

The second approach, WiLocquad(856;FIG.4), employs a quadratic solver.

WiLocquadassumes (xC, yC) = (0,0) for the STA’s initial position and given the AP is at (xAP,yAP), the Euclidean distance between the AP and STA is given as:

At each time t, with the user at position p, the new Euclidean distance is:

For each new equation (4) at every time interval t, the exemplary methods subtract equation (3) from it (i.e., (4)-(3)). This cancels out δ leaving 2 unknowns, i.e., xAPand yAP. WiLocquadrequires only two equations to solve for the unknowns, with additional equations increasing the accuracy of the solution.

where R1is the range when the user (STA) was at (0,0).

WiLoc300schedules a STA to sequentially range with multiple APs (at least 3) at each time interval t and solves for δAPto compute the true range from each AP. LoS APs are selected by the Random Forest classifier. Subsequently, WiLoc300employs a simple least-square multilateration solver to localize the STA, with the offset-corrected ranges from LoS APs as input to the solver.

In conclusion, WiFi’s fine time measurement (FTM) based ranging protocol has set the stage for mass adoption of location aware applications and services in WiFi-pervading enterprise and consumer ecosystems. However, the lack of deployment of such commercial-scale localization solutions has motivated the execution of a comprehensive experimental study that aims to verify whether WiFi’s FTM is indeed ready for prime-time localization.

With heterogeneity in operation (devices, environments, and spectrum) being the fundamental essence of commercial deployments, the exemplary study focuses on FTM’s ability to deliver useable localization under such practical conditions. Being a first of its kind, the exemplary study reveals several interesting insights for practical operation of FTM, with the most interesting of them being its inability to eliminate substantial offsets in estimated ranges between heterogeneous devices and configurations that degrade performance significantly (up to 20 m error). Albeit such unfortunate result for FTM’s readiness, the exemplary methods also propose a simple but promising remedy, that is, an over-the-top autocalibration solution that allows every WiFi device, when it enters an enterprise environment, to self-calibrate its offsets on-demand, thereby salvaging FTM to render it useful (median error of 2 m) for localization.

FIG.4is a block/flow diagram800of a practical application for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters, in accordance with embodiments of the present invention.

In one practical example, a transmitter802is in communication with a receiver804, and WiLoc300is implemented in an enterprise environment via either WiLoclin(854) or WiLocquad(856). The results810(e.g., variables or parameters or factors or communications) can be provided or displayed on a user interface812handled by a user814.

Regarding the practical applications of the exemplary embodiments, the novelty of 5G is the integration of multiple networks serving diverse sectors, domains and applications, such as multimedia, virtual reality (VR) and augmented reality (AR), machine to machine (M2M) and internet of things (IoT), automotive applications, smart city, etc. The diversity of the 5G applications and their related service requirements in terms of data rate, latency, reliability, and other parameters leads to the necessity for operators to provide a diverse set of 5G networks.

Among the various innovations enabling 5G, one of main necessities and realities is the use of mmWave spectrum be coupled with network densification and massive multiple input, multiple output (MIMO) to serve as an ultra-high-speed access and backhaul systems. A key ingredient for 5G is to enable applications in the mmWave spectrum, such as mobile edge computing (MEC), which is expected to bring information and processing closer to the mobile users and enable ultra-high speed and low latency communications. The exemplary embodiments of the present invention can allow such applications to be successfully implemented.

FIG.5is an exemplary processing system for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters, in accordance with embodiments of the present invention.

The processing system includes at least one processor (CPU)904operatively coupled to other components via a system bus902. A GPU905, a cache906, a Read Only Memory (ROM)908, a Random Access Memory (RAM)910, an input/output (I/O) adapter920, a network adapter930, a user interface adapter940, and a display adapter950, are operatively coupled to the system bus902. Additionally, WiLOC300can be implemented by either using a linear solver854(WiLoclin) or a quadratic solver856(WiLocquad).

A storage device922is operatively coupled to system bus902by the I/O adapter920. The storage device922can be any of a disk storage device (e.g., a magnetic or optical disk storage device), a solid-state magnetic device, and so forth.

A transceiver932is operatively coupled to system bus902by network adapter930.

User input devices942are operatively coupled to system bus902by user interface adapter940. The user input devices942can be any of a keyboard, a mouse, a keypad, an image capture device, a motion sensing device, a microphone, a device incorporating the functionality of at least two of the preceding devices, and so forth. Of course, other types of input devices can also be used, while maintaining the spirit of the present invention. The user input devices942can be the same type of user input device or different types of user input devices. The user input devices942are used to input and output information to and from the processing system.

A display device952is operatively coupled to system bus902by display adapter950.

FIG.6is a block/flow diagram of an exemplary method for assessing viability of a WiFi fine tune measurement (FTM) based ranging protocol for enterprise-grade localization with heterogeneity across operational parameters, in accordance with embodiments of the present invention.

At block1001, enable an access point to communicate with a plurality mobile devices handled by a plurality of users within an enterprise environment.

At block1003, track a mobile device of the plurality of mobile devices as the mobile device travels along a trajectory within the enterprise environment.

At block1005, measure a plurality of ranges at various points along the trajectory.

At block1007, combine information related to the plurality of ranges and the trajectory to predict a range offset of the mobile device such that the mobile device itself self-calibrates all its range offsets on-demand.

FIG.7is a block/flow diagram of exemplary equations for a linear solver and a quadratic solver, as well as for a rage offset, in accordance with embodiments of the present invention.

WiLOC300can be implemented by either using a linear solver854(WiLoclin) or a quadratic solver856(WiLocquad). The range offset equation for the quadratic solver856(WiLocquad) is given as1111.

As used herein, the terms “data,” “content,” “information” and similar terms can be used interchangeably to refer to data capable of being captured, transmitted, received, displayed and/or stored in accordance with various example embodiments. Thus, use of any such terms should not be taken to limit the spirit and scope of the disclosure. Further, where a computing device is described herein to receive data from another computing device, the data can be received directly from the another computing device or can be received indirectly via one or more intermediary computing devices, such as, for example, one or more servers, relays, routers, network access points, base stations, and/or the like. Similarly, where a computing device is described herein to send data to another computing device, the data can be sent directly to the another computing device or can be sent indirectly via one or more intermediary computing devices, such as, for example, one or more servers, relays, routers, network access points, base stations, and/or the like.