=Paper=
{{Paper
|id=Vol-3919/short7
|storemode=property
|title=Enhanced Genetic Algorithm-Based Wi-Fi Access Points Deployment for RTT Positioning: Fitness Function Design and Analysis
|pdfUrl=https://ceur-ws.org/Vol-3919/short7.pdf
|volume=Vol-3919
|authors=Meng Sun,Yunjia Wang,Nanshan Zheng,Qianxin Wang,Guoliang Chen,Zengke Li
|dblpUrl=https://dblp.org/rec/conf/ipin/0006WZW0L24
}}
==Enhanced Genetic Algorithm-Based Wi-Fi Access Points Deployment for RTT Positioning: Fitness Function Design and Analysis==
https://ceur-ws.org/Vol-3919/short7.pdf
Enhanced Genetic Algorithm-Based Wi-Fi Access Points
Deployment for RTT Positioning: Fitness Function Design
and Analysis
Meng Sun1,*,† , Yunjia Wang1,† , Nanshan Zheng1,† , Qianxin Wang1,† , Guoliang Chen1,† and
Zengke Li1,†
1
School of Environment and Spatial Informatics, China University of Mining and Technology, Xuzhou, 221116, China
Abstract
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
fitness 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 different 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.
Keywords
Indoor localization, Wi-Fi RTT, Wi-Fi ranging positoning, enhanced genetic algorithm, fitness function
1. Introduction
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
Proceedings of the Work-in-Progress Papers at the 14th International Conference on Indoor Positioning and Indoor Navigation
(IPIN-WiP 2024), October 14–17, 2024, HongKong, China
*
Corresponding author: Meng Sun
†
These authors have the same affiliation.
" msun@cumt.edu.cn (M. Sun); wyjc411@163.com (Y. Wang); znshcumt@163.com (N. Zheng); wqx@cumt.edu.cn
(Q. Wang); chglcumt@163.com (G. Chen); zengkeli@yeah.net (Z. Li)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
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 affects 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 different fitness functions on RTT localization accuracy.
2. Methods
2.1. Overview of This Work
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.
Figure 1: Flow graph of this work.
2.2. Enhanced Genetic Algorithm-based Optimal Wi-Fi RTT Access Points
Deployment
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
first 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 ), ..., (𝑥𝑗𝑖 , 𝑦𝑖𝑗 ), ..., (𝑥𝑛𝑖 , 𝑦𝑖𝑛 )} (1)
where Ξ𝑖 is the chromosome of the 𝑖 − 𝑡ℎ sample, 𝑖 ∈ {1, 2, ..., 𝐷}, 𝑛 denotes the number of Wi-Fi
APs, (𝑥𝑗𝑖 , 𝑦𝑖𝑗 ) is the coordinate of the 𝑗 − 𝑡ℎ AP, 𝑗 ∈ {1, 2, ..., 𝑛}, respectively. All samples are assigned
scores according to a fitness function, which describes their adaptability to the search space. 𝐷 samples
represent 𝐷 kinds of possible Wi-Fi AP layouts, and their scores are described as:
⎧
⎪
⎪ 𝑓 {𝑂1 } = 𝑓 {(𝑥11 , 𝑦11 ), ..., (𝑥𝑛1 , 𝑦1𝑛 )} → 𝑐1
⎪
⎨𝑓 {𝑂2 } = 𝑓 {(𝑥1 , 𝑦 1 ), ..., (𝑥𝑛 , 𝑦 𝑛 )} → 𝑐2
⎪
2 2 2 2
.. (2)
⎪
⎪
⎪ .
⎪
1 1
𝑓 {𝑂𝐷 } = 𝑓 {(𝑥𝐷 , 𝑦𝐷 ), ..., (𝑥𝑛𝐷 , 𝑦𝐷 𝑛 )} → 𝑐
⎩
𝐷
where 𝑓 (∙) is the fitness function, 𝑐𝐷 is the score of the 𝐷 − 𝑡ℎ individual, respectively. Based on the
scores, EGA selects the best individuals for evolution. The higher an individual’s score, the greater its
chance of being selected. After selection, adaptive crossover and mutation operations are executed. The
mutated population is then re-evaluated and scored again according to (2). This closed-loop operation
of scoring-selection-crossover-mutation continues until a convergence condition is met.
2.3. Fitness Function Using CRLB
The Cramer-Rao lower bound defines the minimum variance of any unbiased estimator [16]. For a
localization scheme comprising 𝑛 Wi-Fi APs with coordinates 𝑠𝑖 = [𝑥𝑖 , 𝑦𝑖 ]𝑇 ∈ R2 , 𝑖 ∈ {1, 2, ..., 𝑛} and
an undetermined target with ground-truth position 𝑡 = [𝑥, 𝑦]𝑇 ∈ R2 , if the measured RTT data is 𝑑 ˆ
and the RTT observation from each AP is independent, the PDF is defined by:
𝑛
∏︁
ˆ |𝑡) = 𝑝(𝑑
𝑝(𝑑 ˆ1 |𝑡) × 𝑝(𝑑
ˆ2 |𝑡) × · · · × 𝑝(𝑑
ˆ𝑛 |𝑡) = 𝑓 (𝑑ˆ𝑖 |𝑡) (3)
𝑖=1
ˆ𝑖 = 𝑑𝑖 − 𝜁,
𝑑 𝜁 ∼ 𝒩 (0, 𝜎 2 ) (4)
ˆ = [𝑑ˆ1 , ..., 𝑑ˆ𝑖 , ..., 𝑑ˆ𝑛 ], 𝑑ˆ𝑖 and 𝑑𝑖 represent the measured distance and the ground-truth distance
where 𝑑
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 (3) as follows:
𝑡 = 𝑎𝑟𝑔𝑚𝑎𝑥𝑙𝑛𝑝(𝑑 ˆ |𝑡) (5)
ˆ |𝑡) is expressed as:
where 𝑙𝑛𝑝(𝑑
𝑛
∑︁
ˆ |𝑡) = 𝑙𝑛𝑝(𝑑ˆ1 |𝑡) + ... + 𝑙𝑛𝑝(𝑑ˆ𝑛 |𝑡) =
𝑙𝑛𝑝(𝑑 𝑙𝑛𝑝(𝑑ˆ𝑖 |𝑡) (6)
𝑖=1
According to the Gaussian function, Equation (6) is further given by:
𝑙𝑛𝑝(𝑑ˆ |𝑡) = 𝑀 − 1 [(𝑑 ˆ − 𝑑(𝑡))𝑇 𝑅−1 (𝑑
ˆ − 𝑑(𝑡))] (7)
2
where 𝑑(𝑡) is the ground-truth distance between the undetermined target and Wi-Fi APs, 𝑑(𝑡) =
[𝑑1 (𝑡), ..., 𝑑𝑖 (𝑡), ..., 𝑑𝑛 (𝑡)], 𝑑𝑖 (𝑡) = ||𝑡 − 𝑠𝑖 ||2 , 𝑅 is the variance matrix, 𝑅 = 𝑑𝑖𝑎𝑔{𝜎12 , ..., 𝜎𝑛2 }, 𝑀 is
expressed as:
𝑛
∑︁ 1
𝑀= 𝑙𝑛 √ (8)
𝑖=1
2𝜋𝜎𝑖
Since the localization problem involves calculating the target’s position estimation ˆ𝑡 using 𝑠 and 𝑑,
^ ˆ𝑡
varies with the dynamic 𝑑 that has a ranging variance 𝜎 (see Section 2.4.2). The estimation covariance
^ 2
matrix of ˆ𝑡 is bounded by the inverse of the Fisher information matrix (FIM) 𝐼:
𝐸{(𝑡 − ˆ𝑡)(𝑡 − ˆ𝑡)𝑇 } ≥ 𝐼 −1 (𝑡) (9)
where 𝐼 is further given by:
ˆ |𝑡)∇𝑙𝑛𝑝(𝑑
𝐼 =𝐸[∇𝑙𝑛𝑝(𝑑 ˆ |𝑡)𝑇 ]
(10)
[︂ ]︂
2 ˆ 𝐼𝑥𝑥 𝐼𝑥𝑦
= −𝐸[∇ 𝑙𝑛𝑝(𝑑|𝑡)] =
𝐼𝑦𝑥 𝐼𝑦𝑦
where ∇ and ∇2 denote the operator of first and second-order differentiation, 𝐸(∙) represents the
expectation operator, 𝐼𝑥𝑥 , 𝐼𝑦𝑦 , 𝐼𝑥𝑦 and 𝐼𝑦𝑥 are the elements of 𝐼, respectively.
Taking the first-order differentiation of (7) with respect to 𝑡, we obtain:
∇𝑙𝑛𝑝(𝑑 ˆ |𝑡) = ∇𝑑𝑇 (𝑡)𝑅−1 (𝑑 ˆ − 𝑑(𝑡)) (11)
Taking differentiation of (11) with respect to 𝑡, we have:
𝐼 = ∇𝑑𝑇 (𝑡)𝑅−1 ∇𝑑(𝑡) (12)
The CRLB of RTT positioning for a mobile target 𝑡 is defined as the summation of the CRLBs of each
coordinate:
2
𝜎𝐶 2
(𝑡) = 𝜎𝐶 (𝑥) + 𝜎𝐶 2
(𝑦) = 𝑡𝑟(𝐼 −1 (𝑡)) (13)
𝑡𝑟(𝐼(𝑡)) 𝐼𝑥𝑥 + 𝐼𝑦𝑦
𝑡𝑟(𝐼 −1 (𝑡)) = = (14)
𝑑𝑒𝑡(𝐼(𝑡)) 𝐼𝑥𝑥 × 𝐼𝑦𝑦 − 𝐼𝑥𝑦 × 𝐼𝑦𝑥
where 𝑡𝑟(∙) and det(∙) denote taking the trace and determinant of 𝐼, respectively.
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 = (15)
𝐿
where 𝐿 is the number of testing points (also denoted as grid points in the paper), 𝑐𝑟𝑙𝑏𝑗 is the CRLB of
the 𝑗 − 𝑡ℎ testing point, respectively.
2.4. Fitness Function Using RTT/RSS Measurement Errors
2.4.1. RTT ranging error-based fitness function
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:
∑︀𝐿 ∑︀𝑛 𝑗
𝑖=1 𝑗=1 𝐸𝑖
𝑓 𝑖𝑡2 = (16)
𝐿
where 𝐸𝑖𝑗 denotes the ranging error with respect to the 𝑖 − 𝑡ℎ testing point and the 𝑗 − 𝑡ℎ Wi-Fi AP.
𝐸𝑖𝑗 is calculated by:
𝐸𝑖𝑗 = 𝑎0𝑗 + 𝑎1𝑗 𝑑𝑗𝑖 + 𝑎2𝑗 (𝑑𝑗𝑖 )2 (17)
where 𝑑𝑗𝑖 is the plane distance between the 𝑖 − 𝑡ℎ testing point and the 𝑗 − 𝑡ℎ Wi-Fi AP. Equation (16)
represents the fitness function using RTT ranging error.
2.4.2. RTT ranging variance-based fitness function
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:
𝜎𝑑𝑖 = 𝑘𝑑𝑖 𝑑𝑖 + 𝑏𝑑𝑖 (18)
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 𝜎𝑑𝑖
𝑓 𝑖𝑡3 = (19)
𝐿
where 𝜎𝑑𝑗 𝑖 represents the ranging variance from the 𝑗 − 𝑡ℎ AP at the 𝑖 − 𝑡ℎ testing point, and 𝜎𝑑𝑗 𝑖 is
calculated based on (18).
Figure 2: The distribution of RTT ranging variances for different APs at various distances: (a) No.1 AP; (b) No.2
AP; (c) No.3 AP.
2.4.3. RSS variance-based fitness function
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:
𝜎𝑟𝑖 = 𝑘𝑟𝑖 𝑑𝑖 + 𝑏𝑟𝑖 (20)
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.
Similar to the RTT ranging variance-based fitness function, the fitness function using RSS variance is
defined as follows: ∑︀𝐿 ∑︀𝑛 𝑗
𝑖=1 𝑗=1 𝜎𝑟𝑖
𝑓 𝑖𝑡4 = (21)
𝐿
where 𝜎𝑟𝑗𝑖 represents the ranging variance from the 𝑗 − 𝑡ℎ AP at the 𝑖 − 𝑡ℎ testing point, and 𝜎𝑟𝑗𝑖 is
calculated based on (20).
Figure 3: The distribution of RSS variances for different APs at various distances: (a) No.1 AP; (b) No.2 AP; (c)
No.3 AP.
2.4.4. RSS/RTT variance summation-based fitness function
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:
∑︀𝐿 ∑︀𝑛 𝑗 𝑗
𝑖=1 𝑗=1 (𝜎𝑑𝑖 + 𝜎𝑟𝑖 )
𝑓 𝑖𝑡5 = (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.
2.5. Fitness Function Using Simulated Positioning Error
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 (23)
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
fitness function is defined as: ∑︀𝐿
𝑝𝑒𝑖
𝑓 𝑖𝑡6 = 𝑖=1 (25)
𝐿
where 𝐿 is the number of testing points.
3. Experiments
3.1. Experimental Setup
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 (𝑡)).
√︀
Figure 4: Experimental area.
3.2. Positioning Results With the AP Layouts Indicated by EGA Using Different
Fitness Functions
Table I shows that localization with the AP layout indicated by the simulated positioning error-based
fitness 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 offers a mean accuracy of about 1.136 m and an AET of 0.133
s. These results demonstrate the significant impact of using different fitness functions on finding the
optimal AP layout.
Table 1
Errors Comparisons of Different Fitness Functions
Functions Mean/(m) RMSE/(m) 75th/(m) 90th/(m) AET/s
CRLB 1.062 1.157 1.377 1.681 35.4
Simulated
0.947 1.039 1.277 1.570 2.204
localization error
Ranging error 1.136 1.208 1.414 1.668 0.133
RTT variance 1.467 1.532 1.786 2.089 0.136
RSS variance 1.429 1.520 1.784 2.189 0.135
Summation of
1.508 1.576 1.840 2.098 0.136
RTT/RSS variances
3.3. Positioning Performance Comparison of EGAs with Different Fitness Functions
and Different Numbers of Samples
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 effective strategy for improving the performance of the EGA using variance-based fitness functions.
Table 2
Mean Localization Errors Comparison of EGAs With Different Numbers of Samples
Different numbers of samples
Functions
100 200 300 400 500 600 700 800 900 1000
CRLB 1.124 1.082 1.063 1.093 1.062 1.060 1.093 1.104 1.069 1.078
Simulated localization error 1.157 0.937 0.937 0.947 0.947 0.936 0.931 0.930 0.928 0.916
Ranging error 1.289 1.167 1.124 1.103 1.136 1.123 1.109 1.116 1.129 1.126
RTT variance 1.246 1.470 1.464 1.483 1.467 1.533 1.478 1.504 1.477 1.664
RSS variance 1.254 1.374 1.454 1.404 1.429 1.471 1.413 1.400 1.440 1.489
Summation of RTT/RSS variances 1.282 1.447 1.426 1.459 1.508 1.509 1.498 1.509 1.591 1.539
3.4. Discussion
Using different strategies for fitness function design yields different 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 efficiency of the EGA algorithm.
Figure 5: Visual localization results of the six fitness functions. (a) CRLB; (b) Simulated positioning error; (c)
Ranging error; (d) RTT variance; (e) RSS variance; (f) Summation of RTT and RSS variances.
Fig. 5 illustrates the visual localization results and the deployments of Wi-Fi APs using the six
fitness functions. It can be observed that the positions of Wi-Fi APs generated by the CRLB-based or
simulated positioning error-based fitness function effectively cover the testing area well. However,
performing localization using the AP layout indicated by the ranging error-based fitness function,
despite achieving a mean accuracy of 1.1 m, results in a slightly concentrated distribution of APs (as
seen in Fig. 5(c)), leading to more areas with large positioning errors compared to Fig. 5(a) and 5(b).
Regarding the distributions of Wi-Fi APs generated by the variance-based fitness functions, a more
pronounced phenomenon of concentrated distribution is observed, with the Wi-Fi APs in Fig. 5(e) even
appearing in a linear arrangement. The areas with large errors (dark colors) in Fig. 5(d), 5(e), and 5(g)
are also more than those in Fig. 5(a) and 5(b). Based on the above discussion, it can be concluded that
designing fitness functions should consider the specific application requirements (e.g., accuracy, time
complexity, actual distribution of AP locations, etc.).
4. Conclusion
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.
Acknowledgments
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).
References
[1] L. Banin, O. Bar-Shalom, N. Dvorecki, Y. Amizur, Scalable wi-fi client self-positioning using
cooperative ftm-sensors, IEEE Trans. Instrum. Meas. 68 (2018) 3686–3698. doi:10.1109/TIM.
2018.2880887.
[2] H. Cao, Y. Wang, J. Bi, S. Xu, M. Si, H. Qi, Indoor positioning method using wifi rtt based
on los identification and range calibration, ISPRS Int. J. Geo-Inf. 9 (2020) 627. doi:10.3390/
ijgi9110627.
[3] N. Dvorecki, O. Bar-Shalom, L. Banin, Y. Amizur, A machine learning approach for wi-fi rtt
ranging, in: Proc. ITM Inst. Navig., 2019, pp. 435–444. doi:10.33012/2019.16702.
[4] H. Cao, Y. Wang, J. Bi, Y. Zhang, G. Yao, Y. Feng, M. Si, Los compensation and trusted nlos
recognition assisted wifi rtt indoor positioning algorithm, Expert Syst. Appl. 243 (2024) 122867.
doi:10.1016/j.eswa.2023.122867.
[5] W. Shao, H. Luo, F. Zhao, H. Tian, S. Yan, A. Crivello, Accurate indoor positioning using temporal–
spatial constraints based on wi-fi fine time measurements, IEEE Internet Things J. 7 (2020)
11006–11019. doi:10.1109/JIOT.2020.2992069.
[6] X. Feng, K. A. Nguyen, Z. Luo, A wifi rss-rtt indoor positioning system using dynamic model
switching algorithm, IEEE J. Indoor Seamless Position. Navig. (2024) 1–15. doi:10.1109/JISPIN.
2024.3385356.
[7] J.-H. Seong, S.-H. Lee, W.-Y. Kim, D.-H. Seo, High-precision rtt-based indoor positioning system
using rcdn and rpn, Sensors 21 (2021) 3701. doi:10.3390/s21113701.
[8] G. Guo, R. Chen, F. Ye, Z. Liu, S. Xu, L. Huang, Z. Li, L. Qian, A robust integration platform of
wi-fi rtt, rss signal, and mems-imu for locating commercial smartphone indoors, IEEE Internet of
Things J. 9 (2022) 16322–16331. doi:10.1109/JIOT.2022.3150958.
[9] B. Zhou, Z. Wu, Z. Chen, X. Liu, Q. Li, Wi-fi rtt/encoder/ins-based robot indoor localization using
smartphones, IEEE Trans. Veh. Technol. 72 (2023) 6683–6694. doi:10.1109/TVT.2023.3234283.
[10] M. Sun, Y. Wang, S. Xu, H. Qi, X. Hu, Indoor positioning tightly coupled wi-fi ftm ranging and
pdr based on the extended kalman filter for smartphones, IEEE Access 8 (2020) 49671–49684.
doi:10.1109/ACCESS.2020.2979186.
[11] L. Huang, B. Yu, H. Li, H. Zhang, S. Li, R. Zhu, Y. Li, Hpips: A high-precision indoor pedestrian
positioning system fusing wifi-rtt, mems, and map information, Sensors 20 (2020) 6795. doi:10.
3390/s20236795.
[12] L. Banin, U. Schatzberg, Y. Amizur, Wifi ftm and map information fusion for accurate positioning,
in: Proc. of the 2016 IPIN, 2016.
[13] M. Sun, Y. Wang, L. Huang, S. Xu, H. Cao, W. Joseph, D. Plets, Simultaneous wifi ranging
compensation and localization for indoor nlos environments, IEEE Commun. Lett. 26 (2022)
2052–2056. doi:10.1109/LCOMM.2022.3187208.
[14] N. P. Eberechukwu, H. Park, C. Laoudias, S. Horsmanheimo, S. Kim, Dropout autoencoder
fingerprint augmentation for enhanced wi-fi ftm-rss indoor localization, IEEE Commun. Lett. 27
(2023) 1759–1763. doi:10.1109/LCOMM.2023.3272972.
[15] M. Sun, Y. Wang, S. Xu, H. Yang, K. Zhang, Indoor geomagnetic positioning using the enhanced
genetic algorithm-based extreme learning machine, IEEE Trans. Instrum. Meas. 70 (2021) 1–11.
doi:10.1109/TIM.2021.3072699.
[16] C. Li, J. Trogh, D. Plets, E. Tanghe, J. Hoebeke, E. De Poorter, W. Joseph, Crlb-based positioning
performance of indoor hybrid aoa/rss/tof localization, in: Proc. of the 2019 IPIN, IEEE, 2019, pp.
1–6. doi:10.1109/IPIN.2019.8911771.