Wi-Fi ranging positioning based on round-trip time (RTT) measurement is influenced by complex environments and the deployment of access points (AP). This work proposes an enhanced genetic algorithm (EGA)-based strategy for Wi-Fi AP deployment and analyzes the performance of the EGA-based framework by designing iftness functions using Cramer-Rao lower bound (CRLB), simulated localization error and measurement errors of Wi-Fi RTT and received signal strength (RSS). Simulation experiments are conducted to compare RTT ranging positioning using diferent Wi-Fi AP layouts generated by the EGA algorithm configured with various fitness functions. The results show that designing a fitness function based on simulated localization error provides the optimal Wi-Fi AP deployment strategy, leading to the best positioning accuracy with considerable time complexity compared to fitness functions based on CRLB and RTT/RSS measurement errors.
Since mobile phones support the fine time measurement (FTM) protocol [ 1], smartphone-based Wi-Fi RTT localization has been a research spotlight. To achieve accurate localization, various ranging compensation methods have been investigated, such as nonlinear fitting [ 2], machine learning methods [3], etc. However, the popular approach for improving accuracy is to design optimization strategies or fusion systems. For example, RTT localization is optimized by using a support vector machine-based non-line-of-sight (NLoS)/LoS identification strategy in [ 4], which compensates the LoS ranging data and evaluates NLoS data’s participation in positioning based on the NLoS/LoS identification results. In [ 5], a temporal-spatial constraints strategy is presented, which converts sequences of ranging observations into virtual positioning clients by considering the spatial constraints, significantly improving the positioning accuracy. Other optimization methods, such as the dynamic model switching algorithm [6], and conventional neural networks-based positioning model [7], have also reported promising results regarding accuracy improvement.
Combining Wi-Fi RTT with smartphone-embedded sensors has been proven to achieve high-accuracy localization. In [8], an integrated platform using Wi-Fi RTT, RSS, and MEMS-IMU is constructed based on the robustly adaptive Kalman filter and obtains an average precision of 0.572 m in the reported testing site. In [9], another Wi-Fi RTT/Encoder/INS-based fusion system is implemented through an adaptive extended Kalman filter and improves the mean accuracy under NLoS and LoS conditions by 54.62% and 58.38%, respectively. Other fusion systems using filter algorithms such as extended Kalman filter [ 10], particle filter [ 11], etc., can obtain meter-level localization accuracy. Besides, map information [12] and magnetic field data [ 13] are also utilized for fusion positioning methods. Moreover, the fingerprinting approach using Wi-Fi RTT and RSS is investigated in [14], which extracted RTT/RSS characteristics to perform fingerprinting and obtained a 1- mean square error within 0.6 m.
From the above literature review, most state-of-the-art works were conducted with a predefined Wi-Fi access point layout, but few works concentrate on how AP deployment afects RTT positioning. Using an optimal AP deployment can not only achieve the required precision with a limited number of APs but also reduce positioning investment. Motivated by this, we propose to design the optimal Wi-Fi AP layout using the enhanced genetic algorithm (EGA) [15], and carry out experiments to analyze the impacts of EGA with diferent fitness functions on RTT localization accuracy.
As shown in Fig. 1, to evaluate the impact of fitness functions on the performance of the proposed method, the initial step involves training the RTT ranging error model (Section 2.4), RTT and RSS variance models (Section 2.4), and deriving the CRLB calculation methods (Section 2.3). Based on the coordinates of APs and grid points, the plane distance between them is computed. A simulated real-time ranging process is erformed by introducing ranging errors to the plane distance. Subsequently, the simulated localization errors (Section 2.5) of the test points are obtained. Therefore, the fitness functions are designed using CRLB, simulated positioning errors, ranging errors, RTT variance, RSS variance, and the summation of RTT and RSS variances. Further details regarding the EGA-based framework are described in Section 2.2.
In this work, we utilize the enhanced genetic algorithm to search for the optimal strategy by using
operations of selection, adaptive crossover and adaptive mutation. For more details on these operations,
refer to [15]. To find the optimal AP layout using EGA, a population with individuals should be
ifrst defined. The samples contain possible AP layouts and evolve by executing the above three genetic
operators. Every individual carries one chromosome for the evolution process. Since the final search
goal is to find the deployment method for Wi-Fi APs, the chromosome can be coded as:
Ξ = {(1 , 1), ..., ( , ), ..., (, )}
(
, )} → . . .
(
The Cramer-Rao lower bound defines the minimum variance of any unbiased estimator [ 16]. For a
and the RTT observation from each AP is independent, the PDF is defined by:
an undetermined target with ground-truth position = [, ]
localization scheme comprising Wi-Fi APs with coordinates = [, ]
∈ R2, if the measured RTT data is ˆ
∈ R2, ∈ {1, 2, ..., } and
(ˆ|) = (ˆ1|) × (ˆ2|) × · · · ×
(ˆ|) = ∏︁ (ˆ|)
=1
ˆ = − ,
∼ (0, 2)
where ˆ = [ˆ1, ..., ˆ, ..., ˆ], ˆ and represent the measured distance and the ground-truth distance
between the target’s position and the − ℎ Wi-Fi AP, denotes the ranging error term following a
Gaussian distribution with zero mean and variance 2, respectively. The estimation is obtained by
maximizing the Log-likelihood function of (
= (ˆ|)
(ˆ|) = (ˆ1|) + ... + (ˆ|) = ∑︁ (ˆ|)
=1
According to the Gaussian function, Equation (
[(ˆ − ()) − 1(ˆ − ())] expressed as: where () is the ground-truth distance between the undetermined target and Wi-Fi APs, () = [1(), ..., (), ..., ()], () = || − ||2, is the variance matrix, = { 12, ..., 2}, is = ∑︁ √2 =1 1
Since the localization problem involves calculating the target’s position estimation ˆ using and ^, ˆ varies with the dynamic ^that has a ranging variance 2 (see Section 2.4.2). The estimation covariance matrix of ˆ is bounded by the inverse of the Fisher information matrix (FIM) : where is further given by:
{( − ˆ)( − ˆ) } ≥ − 1() =[∇(ˆ|)∇(ˆ|) ] = − [∇2(ˆ|)] = ︂[ ︂] where ∇ and ∇
2 denote the operator of first and second-order diferentiation,
expectation operator, , , and are the elements of , respectively.
(∙ ) represents the
Taking the first-order diferentiation of (
= ∇ ()− 1∇()
The CRLB of RTT positioning for a mobile target is defined as the summation of the CRLBs of each
coordinate:
(
To construct the fitness function, we should first divide the testing area and obtain the coordinates of testing points. Assuming the positioning problem under an optimal Wi-Fi AP layout, the CRLBs on these points should achieve minimal values, resulting in the minimal summation of CRLBs. Therefore, the fitness function can be constructed by taking the mean value of the summation of CRLBs: 1 = ∑︀=1 where is the number of testing points (also denoted as grid points in the paper), is the CRLB of the − ℎ testing point, respectively.
In this work, we utilize the least squares method [10] to simulate RTT ranging errors. If there are testing points in the positioning area, the total ranging error of all the grid points under a particular AP layout is computed as: 2.4.2. RTT ranging variance-based fitness function
2 () = 2 () + 2 () = (− 1()) (− 1()) = (()) (()) =
+
× − ×
(
= 0 + 1 + 2 ( )2
where denotes the ranging error with respect to the − ℎ testing point and the − ℎ Wi-Fi AP.
is calculated by:
where is the plane distance between the − ℎ testing point and the − ℎ Wi-Fi AP. Equation (
As Fig. 2 shows, the ranging variance demonstrates that the greater the true distance, the greater the variance value. We use a linear regression method to describe the changing trend of RTT ranging variance, which is expressed as:
= + 3 = where is the matrix of simulated ranging variance, = ( 1 , ..., ) , is the number of APs, and are the matrices of the linear parameters, = (1 , ..., ) , = (1 , ..., ) , is the matrix of the plane distances between the − ℎ testing point and the Wi-Fi APs, = (1 , ..., , ..., ) , respectively.
For a testing site with grid points, the fitness function using ranging variance can be defined as: ∑︀=1 ∑︀=1 where represents the ranging variance from the − ℎ AP at the − ℎ testing point, and is calculated based on (18).
As Fig. 3 shows, the RSS variance also gradually increases as the ground-truth distance increases. Comparing Fig. 3 with Fig. 2, it can be observed that the fluctuation range of the RSS variance is smaller than that of the RTT ranging variance. We also employ the linear regression method to describe the changing trend of RSS variance as follows:
= + whearne d isatrheethmeatmriaxtroifcessimoufltahteedlirnaenagrinpgarvaamrieatnercse,, == (( 11,, ......,, )) ,, is =the(n1u ,m..b.,erof APs, ) , is the matrix of the plane distances between the − ℎ testing point and the Wi-Fi APs, = (1 , ..., , ..., ) , respectively.
Similar to the RTT ranging variance-based fitness function, the fitness function using RSS variance is defined as follows: 4 = ∑︀=1 ∑︀=1 (20) (21) where represents the ranging variance from the − ℎ AP at the − ℎ testing point, and is calculated based on (20).
Because the measurements of RTT and RSS data are simultaneously executed, using the summation of RSS/RTT can also define a fitness function as follows:
5 = ∑︀=1 ∑︀=1( + ) (22) where and are the variances of RTT ranging and RSS measurement from the − ℎ AP at the − ℎ testing point, respectively. It should be noted that and are normalized before summation.
The optimal Wi-Fi AP deployment method should minimize the estimation error of the target in the testing site. Therefore, using positioning error for fitness function is possible. Given grid points and Wi-Fi APs, the plane distance between grid points and APs is calculated as:
= √︁( − ˆ )2 + ( − ˆ )2 where (, ) and (ˆ , ˆ ) are the coordinates of the − ℎ grid point and the − ℎ Wi-Fi AP, ∈ {1, 2, ..., }, ∈ {1, 2, ..., }. The simulated real-time measured distance is expressed as: ˆ = + (24) where is the simulated ranging error using (17). With the simulated ranging data, the positioning error at the − ℎ grid point can be estimated using a least-squares method [10]. Therefore, the iftness function is defined as: 6 = ∑︀=1 (23) (25) where is the number of testing points.
As shown in Fig. 4, the testing area represents a typical working scenario and 375 grid points are obtained by gridding this area. We measured RTT and RSS data using a Pixel 3 phone at 166 reference points and obtained the parameters of the ranging error model and RTT/RSS data variance models. The used Wi-Fi APs have the hardware part of Intel Dual Band Wireless-AC8260, and we assume that a maximum of 7 Wi-Fi APs are available and they can be installed at all locations within the testing area. The population size of EGA is set to 500. The convergence condition is to reach the maximum number of iterations, which is set to 50. All data analyses are made on a laptop with 16 GB RAM and a 2.3 GHz CPU. The positioning error bound (PEB) is defined for discussion ( Section 3.4), and the calculation method of PEB is: √︀(− 1()).
Table I shows that localization with the AP layout indicated by the simulated positioning error-based iftness function achieves a mean accuracy of 0.947 m, which is 0.115 m, 0.189 m, 0.472 m, 0.507 m, and 0.529 m higher than those achieved by fitness functions using CRLB, ranging errors, ranging variance, and the summation of RTT/RSS variances, respectively. Regarding the comparison of the measurement error-based fitness functions, the ranking from high to low is ranging error, RSS variance, RTT variance, and the summation of RTT/RSS variances, respectively. Moreover, all algorithms with measurement error-based fitness functions can be executed within 0.14 s, showing a time advantage over the CRLB-based and simulated positioning error-based fitness functions. For cases where the required accuracy falls within an acceptable range (e.g., 1.5 m), using the ranging error-based fitness function is also a viable solution, which ofers a mean accuracy of about 1.136 m and an AET of 0.133 s. These results demonstrate the significant impact of using diferent fitness functions on finding the optimal AP layout.
As Table II shows, when using the AP layout indicated by the simulated localization error-based fitness function, the mean localization accuracy exhibits an upward trend as the number of samples increases, ranging from 1.157 m to 0.916 m. The mean accuracy of using the CRLB-based fitness function also shows an upward trend, but it stabilizes around 1.08 m after the number of samples exceeds 200. The ranging error-based fitness function follows a similar trend to the CRLB-based fitness function. However, the mean positioning accuracy of the variance-based fitness functions does not increase as the number of samples increases. Instead, the best mean positioning results are obtained when the number of samples is 100. Moreover, using the summation of RTT and RSS variances as the fitness function does not lead to better positioning results. These results show that increasing the number of samples is not an efective strategy for improving the performance of the EGA using variance-based fitness functions.
Using diferent strategies for fitness function design yields diferent outcomes and demonstrates their respective advantages. For example, employing a variance-based fitness function provides an advantage in terms of time complexity. However, performing LS positioning under the AP layout generated by a variance-based fitness function does not necessarily result in better positioning accuracy. Improving the performance of genetic algorithms by increasing the population size often does not lead to significant improvements. Under such conditions, using a large population size for optimal AP layout searching only leads to a rapid increase in the algorithm’s time complexity. Therefore, adopting an appropriate population size is crucial for the execution eficiency of the EGA algorithm.
In this work, we designed six fitness functions for the EGA-based optimal Wi-Fi AP deployment strategy. The simulation results prove that using CRLB and simulated positioning error for fitness function design can lead to a reasonable Wi-Fi AP layout. However, the time complexity associated with using a CRLB-based fitness function should be considered. Our future work will investigate the comprehensive impact of the number and deployment methods of APs on RTT localization in real-life scenarios, as well as high-accuracy RTT/RSS variance simulation methods.
Thanks to the support of the National Natural Science Foundation of China (No. 42304047) and the Priority Academic Program Development of Jiangsu Higher Education Institutions (Surveying and Mapping Science and Technology Discipline).