Introduction
For indoor environments where GPS is not available, substantial research has been conducted on positioning technologies that leverage diverse wireless technologies, such as ultra-wideband (UWB) [1], RF identification (RFID) [2], and Bluetooth low energy (BLE) [3], etc. However, due to the widespread adoption and use of Wi-Fi on most consumer devices, Wi-Fi has garnered attention as a highly practical and promising technology for indoor positioning. Various Wi-Fi-based positioning technologies have been developed, and they can be broadly categorized into time-based, signal-based, and angle-based algorithms depending on the measurement targets used for positioning [4].
The time-based algorithms are capable of calculating distance based on the propagation time data collected during the exchange of information between a transmitter and a receiver. However, precise time synchronization between the two devices is very important for the accurate distance calculation. The round trip time (RTT) is a highly effective algorithm that can be utilized without the need for time synchronization between devices. The fine timing measurement (FTM) is the first RTT technique introduced in the 802.11mc standard [5]. More recently, the 802.11az standard, which utilizes features of 802.11ax (Wi-Fi 6) to enhance its efficiency, has been introduced [6]. After obtaining the distance measurements using the FTM, the lateration methods can be used to determine the position of the target. Typically, the lateration is made by three anchor nodes called trilateration, as shown in Fig. 1, but a multilateration can also be considered when better accuracy is required.
The angle-based algorithms leverage the received signal to determine the angles between the transmitter and the receiver. These have a constraint that directional antennas are required. However, with the advent of multi-input multi-output (MIMO) technology in the 802.11n standard for Wi-Fi, the use of channel state information (CSI) to measure angles without directional antennas has become possible. After acquiring the angles using the CSI, a triangulation method with two or three anchors can be employed for positioning, as shown in Fig. 1(b) [7].
The signal-based algorithms include lateration methods and fingerprinting methods that use received signals. Traditionally, lateration has used received signal strength indicator (RSSI) and signal path-loss propagation models [8], and fingerprinting has involved collecting extensive RSSI data at each location to learn the signal patterns [9], [10], [11]. However, RSSI is highly affected by multipath fading, resulting in low accuracy in distance measurements. Additionally, since RSSI contains only limited information, a larger number of anchors are required to learn diverse signal patterns.
While fingerprinting usually achieves higher accuracy than lateration, it may require data collection and prior training overhead. Recently, significant progress has been made in Wi-Fi sensing technology, which enables us to collect CSI, including the received signal strength (RSS) and distorted channel information due to multipath fading between the transmitter and receiver. Therefore, fingerprinting with CSI, which is more reliable and provides more information than RSSI, can achieve higher accuracy with a smaller number of anchors [12], [13], [14], [23], [24].
In real-world scenarios, it is crucial to develop an appropriate Wi-Fi positioning method that considers factors such as the size of the target space, the level of infrastructure deployment, and changes in the environmental structure. This paper focuses on an environment with sparsely deployed anchors that requires instantaneous positioning without prior training. In addition, it should be applicable to commonly available off-the-shelf devices for real-world deployment. We aim to develop a positioning method for the target environment based on time and angle. Here are the two key challenges that must be addressed to achieve this.
Sparse anchors: To achieve high accuracy using indoor positioning methods, multiple anchors are required [15]. However, not all Wi-Fi access points (APs) can be utilized for positioning. Only a few APs that are capable of performing measurement functions for positioning, including accurate coordinate information, can be used for this purpose. We refer to such APs as anchors.
Measurement errors: The accuracy of angle and distance measurements using wireless signals is affected by the measurement algorithms and hardware limitations [16], [17].
In this paper, we introduce bilatangulation (bi + lateartion + angulation), a positioning method which is a cluster-based double-step method. The first step is to reduce the minimum number of anchors required for positioning to two by adding the orientation information of the angle to the distance information to address sparse anchors. The second step does not directly reduce the measurement errors in distance and angle. Instead, it addresses the measurement errors caused by hardware limitations by leveraging the complementary characteristics of each error to compensate for the positioning error from the previous step. The proposed method is evaluated through experiments conducted in an indoor environment using off-the-shelf network interface card (NIC), including anchors and targets. This method is based on clusters of intersections from multiple data samples to obtain stable results.
The contributions of this paper can be summarized as follows:
Surfacing the complementary characteristics of measurement errors in distances calculated from the FTM and angles derived from the CSI caused by hardware limitations based on indoor and outdoor experiments (see Section IV-B).
Proposing a novel cluster-based double-step positioning method to address the two key challenges using the two anchors and the complementary characteristics of the distance and angle measurement errors (see Section V).
Implementing anchor and target equipment using an off-the-shelf network NIC to achieve the proposed positioning method (see Section VI-A).
Evaluating the proposed positioning method by practical experiments using the implemented equipment in an indoor environment (see Section VI).
This paper is structured as follows: Section II shows the existing Wi-Fi based indoor positioning systems. Section III shows the preliminary background of the measurement techniques used in the proposed method. Section IV presents the challenges associated with the deployment of the positioning methods. Section V introduces a novel cluster-based double-step positioning method. Section VI presents experimental results to evaluate the performance of the proposed positioning method. Finally, Section VII concludes this paper with remaining future works.
Related Work
This section provides an overview of the existing Wi-Fi indoor positioning methods using off-the-shelf NIC. Table 1 summarizes the features of each method, categorized by environments with sparse anchors and non-sparse anchors.
In [17], the authors analyzed the RTT performance characteristics of FTM and presented a clustering-based trilateration supported by a weighted concentric circle generation (CbT & WCCG) scheme. In [18], the authors presented a method for calibrating ranging using a model that can separate RTT results from FTM into line-of-sight (LoS) and non-line-of-sight (NLoS) environments. In [19], the authors presented an angle-based SpotFi method using CSI collected from off-the-shelf NIC. In [10], the authors presented an RSSI-based fingerprinting method that uses a stacked autoencoder (SAE) and an attention-based long short-term memory (ALSTM) framework. These methods are challenging to use in a sparse anchor environment as they necessitate at least three anchors or a large number of anchors.
Several methods have been presented to address sparse anchor environments. In [20], authors presented a SiFi system that uses an off-the-shelf NIC with three antennas for positioning by arranging the antennas in a triangular shape to a single anchor. In [21], the authors presented SAIL, a single anchor-based positioning system that uses distance information and information from the accelerometer of a smartphone. These methods require specialized hardware, such as arranging antennas in specific geometrical configurations or using additional sensors. In [22], the authors presented the Chronus method for positioning by measuring the distance from one anchor by synchronizing the receiver and transmitter using a channel hopping protocol. This method require modifications to existing protocols.
In [23], The authors presented a deep neural network (DNN) based classification model trained using CSI fingerprints between a Wi-Fi access point and a receiver with a fixed location without any equipment attached to the target(i.e., device-free fingerprinting with two anchors). In [24], the authors presented a novel random forest fingerprinting localization (RFFP) method, which can also operate with a single anchor utilizing CSI. These methods can achieve high accuracy in sparse anchor environments but require data collection and prior training.
In contrast, we propose a positioning method that does not require specialized hardware, protocol modification, or prior training.
Preliminary Background
This section offers preliminary background on the round trip time of flight (RToF) and angle of arrival (AoA) techniques that are used in the proposed method.
A. RToF with Fine Timing Measurement
The Wi-Fi Alliance introduced the fine timing measurement (FTM) protocol to measure RToF in the IEEE 802.11-2016 standard [5]. This protocol operates without an association between Wi-Fi devices, and calculates the round trip time (RTT) by measuring the timestamps.
Fig. 2 shows the operational process of the FTM. The first step is to send an initial FTM request packet by an initiator that knows the media access control (MAC) addresses of the responders that support the FTM. The exchange process of the FTM and ACK starts after the responder sends the ACK, and after the exchange process ends, the initiator uses the recorded timestamp to calculate the RTT as follows:\begin{equation*} RTT = (t_{4}-t_{1})-(t_{3}-t_{2}) \tag {1}\end{equation*}
B. AoA with Channel State Information
In wireless communication systems, data signals are transmitted across a radio channel between the transmitter (Tx) and the receiver (Rx). After receiving the signal, the receiver can calculate the CSI, which contains information regarding attenuation and phase shift of the signal caused by multipath fading [25]. The Wi-Fi channel is divided into multiple subcarriers using orthogonal frequency division multiplexing (OFDM), and the channel is modeled as follows:\begin{equation*} y=H*x + n \tag {2}\end{equation*}
The MUSIC algorithm uses CSI as an input to estimate the AOA of a signal received from a uniform linear antenna array [26], [27]. The AOA is estimated using the phase difference of the signal received between the antenna arrays, with the range being −90° to 90°. Given an antenna array with a specified spacing of d, as shown in Fig. 3, the time delay between the reception of signals at two antennas is \begin{equation*} \boldsymbol {\varphi }=e^{-j2\pi f \tau }=e^{-j2\pi f \times (d \sin {\theta }/c)} \tag {3}\end{equation*}
The Challenges Associated with Deploying Positioning Methods
This section describes the challenges that must be addressed in the deployment of positioning methods based on experimental results.
A. The Scarcity of Available Anchor
For distance-based trilateration or multilateration, a minimum of three anchors are necessary. Even in indoor environments with numerous Wi-Fi APs, problems may emerge if only a limited number of APs can function as anchors. The most common problem is the existence of two possible symmetrical positions. For example, if there are only two available anchors in a room, as shown in Fig. 4, bilateration based on the distances
Unilatangulation determines a position using the distance and angle information from a single anchor. When measuring angles using the MUSIC algorithm, the values range from −90° to 90°. Thus, as shown in Fig. 4(b), another symmetry problem arises, making it difficult to determine the exact position. These problems arise due to a lack of available information.
B. The Measurement Errors Caused by Hardware Limitations
When utilizing anchors to measure distances and angles in real-world settings, many types of measurement errors are occurred depending on the measuring technique. Interestingly, these two different kinds of errors demonstrate complementary characteristics in the experimental results. As shown in Fig. 5, the measured distance is larger than the ground truth and the measured angle is smaller than the ground truth. To investigate the characteristics of these measurement errors, we empirically conducted real-world measurements utilizing off-the-shelf equipment to measure distances using the FTM and angles using CSI and MUSIC algorithm.
The distance measurements were performed in both outdoor and indoor environments as shown in Fig. 6(a) and Fig. 6(b) with increasing distance. As a result, the measured distances were mostly larger than the ground truth represented by the dotted line as shown in Fig. 7. The angle measurements were conducted in an indoor environment as shown in Fig. 6(b) at 20, 40, and 60 degrees of AOA, covering negative and positive angles. As a result, the measured angles were smaller than the ground truth as shown in Fig. (8).
The characteristics of these errors are also confirmed by existing research that utilized off-the-shelf NICs. In [28], the authors illustrated the distance errors observed using the FTM under different conditions. In [29], the authors utilized CSI and MUSIC algorithm to illustrate the error in angular measurements from −90° to 90°. However, these papers do not explain the causes behind the emergence of error characteristics, and to the best of our knowledge, this aspect has not yet been addressed in other studies.
The distance error characteristic is caused by the time of arrival(ToA) estimation method when using FTM. The received signal is sampled as shown in Fig. 9, and if a signal arrives between the sampling points, the estimated ToA will be larger than the real ToA, so the errors become larger [30]. Examining the particular reason for the angular error characteristic is difficult, but it is estimated to be associated with the accuracy of the MUSIC algorithm and the impact of multipath fading in the indoor environment. The MUSIC algorithm can estimate the AoA of each propagation path between −90° to 90°. However, to estimate the AOA for K propagation paths, at least
Bilatangulation
In this section, we introduce a bilatangulation method for indoor positioning that utilizes only two anchors. This method uses the distance information calculated from the FTM and the angle information calculated from the CSI.
The main purpose of bilatangulation is to address the challenges described in Section IV. As shown in Fig. 10, the first step is to address the symmetry problem that arises when using two anchors. The second step is to compensate for the measurement errors. The following two subsections describe each step in detail, and Table 2 provides the descriptions of the symbols.
A. Distance and Angle Samples Collection
As shown in Fig. 11, to simplify the illustration, the baseline
B. Step 1: Addressing the Symmetry Problem
This step uses the orientation of the angles to address the symmetry problem described in Section IV-A. As shown at the top of Fig. 12, when there are distance samples
Algorithm 1 Bilatangulation
Step 1:
for
for
if
else
end if
end for
end for
Step 2:
for
if
else
end if
end for
for
if
else
end if
end for
return P
Additionally, as shown at the bottom of Fig. 12, the original positioning point can be used to resolve the symmetry problem of unilatangulation, allowing the results of unilatangulation to be used for positioning.
C. Step 2: Compensation for Measurement Errors
This step uses the complementary characteristics of the error between the distance and angle described in Section IV-B to further reduce the original error. As shown in Fig. 13, based on the x-coordinate of the original positioning point, the two anchors use
When a cluster of intersection points
Performance Evaluation
This section describes the evaluation results of the bilatangulation. First, we evaluate the feasibility and accuracy of the proposed positioning method using two anchors. Second, we evaluated the accuracy of the measurement error compensation method. Finally, we evaluated the performance of bilatangulation against existing state-of-the-art methods proposed in similar environments. The experiments were based on clusters to utilize the measurement error characteristics of the samples and accommodate the variability in sample values. The number of distance and angle samples collected from each anchor is standardized to N, increasing from 1 to 10.
A. Experimental Setup
Hardware: The experiments were conducted without additional antenna extensions. Both the target and anchor utilized in the experiment were equipped with an Intel AX210 NIC chipset, that enables FTM. The target was constructed using the Raspberry Pi compute module 4 for experimental convenience, along with a dedicated IO board to accommodate the Intel AX210 NIC chipset. The anchor was configured to capture the FTM and CSI data by replacing the NIC of the LG Ultralaptop series with an Intel AX210 NIC chipset. For collecting CSI data, we utilized PicoScenes [31], an open-source tool that supports an Intel AX210 NIC chipset installed on an anchor.
Software: The experiments were conducted without making any additional protocol modifications. The target operates on the Raspberry Pi operating system, while the anchor utilized the Ubuntu 20.24.6 operating system. To enable Intel AX210 NIC, an Intel iwlwifi wireless driver was installed on both devices. FTM data were collected using the iw command, while CSI data were obtained using the Python library provided by PicoScenes.
Testbed: We evaluated the bilatangulation in an indoor testbed measuring
in width and7.5\ m in height, as shown in Fig. 6(b). As shown in Fig. 14(a), the distance between the two anchors was spaced9\ m apart, and the position of the target was measured at six different points.6.9\ m
B. Positioning Accuracy Using the Two Anchors
The first step of bilatangulation enables positioning with two anchors. The cluster of bilateration results is created, and its center point
The clustering technique can significantly reduce positioning errors if a large number of samples with varying variances are collected from multiple anchors. However, in the sparse anchor environment that we focus on, increasing the number of samples does not have a significant impact. Despite achieving a minimum mean positioning error (MPE) of
C. Results of Error Compensation
The second step of bilatangulation further reduces positioning errors by leveraging the inherent complementary characteristics between distance and angle measurement errors, especially in scenarios where the clustering technique alone is insufficient to reduce positioning errors. The experiments were conducted by adding two clusters of unilatangulation results from each anchor.
Fig. 14(c) shows the formation of three clusters. The
On the other hand, when comparing the results of the two steps, the MPE using a single sample in the second step was smaller than that of the sample with the minimum MPE in the first step. Fig. 14(f) shows the CDF of the original and final errors for all cases. The 90-percentile of the original and final errors were
D. Comparison of Performance with Existing State-of-the-Art Methods in Similar Environments
Bilatangulation is a method proposed for positioning in sparse anchor environments without the need for specialized hardware or protocol modifications. As shown in Table 3, existing positioning methods that demonstrate high accuracy in similar environments include the CSI-based fingerprinting methods Device-free and RFFP. The performance evaluation of these two methods was conducted in a testbed similar to the one used in this paper.
Device-free uses CSI collected from 16 reference points spaced
Conversely, our method requires no prior training and, as mentioned in Section VI-C, it does not depend on large volumes of data. Although the correlation between data volume and accuracy is weak, our method achieves performance comparable to fingerprinting methods with relatively less data. Thus, it removes the need for extensive data collection and learning, simplifying the process of achieving high-accuracy positioning.
Conclusion
This paper introduces bilatangulation, a novel indoor positioning method utilizing two anchors. This method addresses the challenges presented in environments with sparse anchors and hardware limitations associated with off-the-shelf NICs, without requiring any specialized hardware and protocol modifications.
We proposed bilatangulation that consists of a cluster-based double-step process. While the first step validated the possibility of positioning with two anchors, the clustering approach yielded an average minimum error of 1.58 meters, potentially limiting further error reduction. In the second step, the complementary features of the distance and angle measurement errors were utilized to reduce the final positioning error by compensating for both types of errors. Consequently, the average compensated error is reduced by approximately 88% from the original error.
Two limitations of bilatangulation need to be addressed. The first limitation is its difficulty in application within sparser environments where only one anchor is available. To address this, it is necessary to research techniques for measuring distances and angles more precisely. The second limitation is the total time required to position all targets in a large-scale environment. Since 802.11mc’s FTM requires making N distance measurements if there are N targets, the total positioning time increases with N. To address this, it is necessary to research into techniques for simultaneous distance and angle measurement of multiple targets, leveraging 802.11az.