Abstract
We propose the Boerdijk–Coxeter Helix (BC Helix) model geometry as a potential node configuration for human users who are localizing within an unstructured environment. When the localization nodes are placed in Boerdijk–Coxeter Helix geometry, the nodes form a regular pattern such that the user can plant new nodes in his or her direction of travel without compromising coverage area or orientation. This paper is also a follow-up to an earlier research paper examining algorithms for three-dimensional localization using a barometer to assist finding the z-coordinate. We provide simulation results examining the potential effects of the Boerdijk–Coxeter Helix geometry on localization accuracy and computation time, and experimental results showing the potential of the helix geometry compared to the random placement of nodes.
1 INTRODUCTION
Localization has advanced through the years with recent interests shifting to indoor navigation and GPS-denied applications. However, there are still some improvements that could be made. Firstly, current urban navigation assumes that nodes could be placed into the environment beforehand—but this assumption does not work for users (Asher et al., 2011; Rantakokko et al., 2012; Mapar, 2010; Ojeda & Borenstein, 2007) who have to face an environment that is neither known beforehand nor structured enough to place nodes. Secondly, the target environment may span across multiple elevations on top of being unknown—this means that localization solutions for such environments need to allow the user to set up their network flexibly across multiple locations utilizing elevations with no fixed structure.
We shall hone in on one possible improvement to arrange a localization network of nodes to give optimal accuracy for the user. The user needs to plant anchors that are reasonably spread out and give good localization accuracy, while retaining the ability to travel without losing their bearings. This research seeks to develop an algorithm suggesting an optimal formation of nodes that has new nodes added to the current network compared to a static set of nodes set from the beginning (Yuan et al., 2015).
Current methods have set up anchors or known sensor points within the area of localization prior to the user localizing himself. This runs on a few assumptions: that the user of the system is somewhat familiar with the area, that the area is guaranteed to have support for the user, and that the anchors of the network can be supported separately from the localization receiver.
However, this paper intends to apply its results for human users who must enter unexplored areas and thus have no prior knowledge of what the area is able to support. Therefore, this algorithm cannot simply suggest a set formation from the beginning. It needs to suggest a formation that retains localization accuracy as the user moves through the target area and adds new nodes to the network.
In addition, we intend to apply this formation to other aspects of localization. This particular research is a follow-up on improving GPS-denied localization with barometer-assisted algorithms (Goh et al., 2019). We will show the effects of the BC Helix formation on localization performance when used in conjunction with traditional 3D-trilateration and modified algorithms using barometers.
We shall frame the scenario of how the user sets up the proposed localization network. We took a cue from the concept of the pseudolite (Jones, 2017; Rapinski et al., 2012), a terminal that can receive and transmit positioning signals on its own. We also drew inspiration from prior research examining planting a network of nodes within an unknown environment (Qin et al., 2017).
The user carries mobile positioning nodes along with him. He will plant an initial node as an anchor at his starting location. The localization system will indicate to them a radius to plant a second anchor based on the communications range Rc of the anchor.
The system will start providing location estimates upon setting up at least four anchors in three dimensions within the area. After this initial network, the localization system will recommend other locations to plant mobile positioning nodes as checkpoints as the user moves through the area.
Figure 1 shows a sample scenario where the user may travel in a general path. The exact path of travel between nodes does not affect the final geometry of the anchors relative to each other. This usage scenario assumes the user does not know the layout of the area beforehand (also known as an unstructured environment). The user carrying a tag is not expected to receive signals from all anchors in order to make a calculation, but they need a minimum of four anchor readings to make a calculation in three dimensions.
Scenario of planting new anchors for localization network. All nodes are assumed to have the same maximum communications range Rc
In this scenario, we add new points along the direction we travel in. As we assume the user to not know the environment beforehand, it is not safe to assume the user can switch direction arbitrarily to plant new points. The user would otherwise get lost within the environment and be unable to obtain an estimate before planting the minimum four anchors.
This also implies that deriving a model based on maximum area or volume (Morales & Kassas, 2017) is not safe as the direction of travel could drastically change for the user depending on where they start and where they place the initial number of nodes. Therefore, we have to derive an alternative model where the user is able to plant anchors in their direction of travel while not compromising area of coverage. This alternative model will need to have a start point and a temporary end point to travel and place anchors.
When planting anchors in a formation along our travel path, we need to consider the following three factors:
The anchors must be within communications range of each other and inter-nodal distance dij must be less than or equal to maximum communication range Rc :dij ≤ Rc
Any one anchor must be able to communicate with the other three anchors within the network; as new anchors are added to the formation, it will eventually exceed maximum communications range of anchors Rc at the starting point
The minimum four anchors used for localization should be in a formation that minimizes localization error (deviation from ground truth) and uncertainty (the possible radius around an estimate the point can be)
In addition, we took a cue from prior research that advocated using geometry as the basis of arranging nodes (Benbadis et al., 2007; Han et al., 2009, 2015; Xie & Dai, 2014). This line of research advocates placing anchors as vertices of regular polyhedrals (for three-dimensional cases) or polygons (for two-dimensional cases) that yield the lowest localization error.
Benbadis proposed that the advantage of using set geometric formations to place anchors diminishes over time as the number of anchors increase in comparison to the random placement of anchors around the borders of the target area (Benbadis et al., 2007).
With these factors, we considered using a helical formation of anchors oriented to the desired travel direction. A helix presents a circular formation within a plane while traveling in a direction, hence lending itself well to regular formations of points. The requirement of limiting anchors within a certain range of each other meant that this helix could not diverge, meaning it could not expand its helical radius with successive vertices placed further away from each other as it progressed.
We therefore propose the Boerdijk–Coxeter Helix (BC Helix), also known as a tetrahelix. It is a helix formed from a linear progression of tetrahedrons linked to each other. The unit tetrahedrons in the helix not only give a formation of four vertices to provide minimum 3D-localization, but the regular tetrahedral geometry was also optimal for four anchors to provide minimal localization error.
We will subsequently explain the mechanics of the Boerdijk–Coxeter Helix, simulations examining the performance of this helix, and a field trial testing this helical formation with real-time localization.
1.1 Adapting the Boerdijk–Coxeter (BC) helix model to localization
The Boerdijk–Coxeter Helix (BC Helix) is also known as a tetrahelix because the vertices can form interlocking tetrahedrons that coil at a set angle. Assuming unit edge length for each tetrahedron unit within the helix, r is the radius of the helix, θhelix is the rotation angle in the x-y plane in which each vertex is away from the previous vertex, and hhelix is the vertical separation between vertices. We also include a maximum communications range of the localization nodes Rc as an actual scaling factor to the BC Helix, and Rc is set as the distance between vertices.
The coordinates of the vertices are listed in terms of the previously mentioned helical parameters as seen in Equation (1) where anchor index i is an element of n anchors. In this scenario, anchor index i can start from 0 as the resulting coordinate (Rcr, 0, 0) is a legitimate coordinate within the helix:
1
By default, the Boerdijk–Coxeter Helix travels in the direction of the z-axis while all vertices in the x-y plane are on the perimeter of a circle with radius Rcr. We can model an internal cylinder within this helix as well, which has a radius of 
. This internal cylinder radius is less than half of the helical radius Rcr.
If deriving the centroids of each individual tetrahedron forming the BC Helix, the centroids all fall within the loci of this internal cylinder. Figure 2 shows a BC Helix with its base parameters.
BC Helix with base parameters: helical radius Rcr, internal radius 
, height between vertices Rchhelix, and angle θhelix. On the left is a sample sequence of vertices while the right shows helix vertices in the x-y plane
Prior literature has typically advocated using global dilution of precision (GDOP) as a benchmark of how well the resulting localization network minimizes localization accuracy (Li et al., 2012; Shi et al., 2017; Hao et al., 2008). For reference, GDOP is evaluated using the variances arising from range measurements D to a target point (x, y, z) (Langley, 1999).
We use positional dilution of precision (PDOP) in this scenario, instead, as we wish to focus only for the three-dimension spatial component and we assume that the timing component is negligible for our scenario. PDOP is derived as shown in Equations (2) and (3).
2
3
The PDOP criterion, however, has some notable limitations. For example, PDOP is reliant on the position of anchors relative to themselves and the target at the specified time. In other words, geometry plays a role in the final calculation of PDOP. When new anchors are being added to the network, the geometry will thus change with every iteration—and there is no guarantee that the new formation will yield the same minimum PDOP as the previous formation.
For the BC Helix, the change in PDOP will arise from the number of anchors added to the helix even if the nodes have regular geometry. In addition, we cannot expect a minimization of PDOP when the nodes have regular geometry. As a result, PDOP cannot be the sole criterion in determining whether the BC Helix configuration will perform better than a random configuration.
As a result, we decided to use two main criteria: One is the true error of the location estimate (the distance between the location estimate and the ground truth) while the other is the root-mean-square (RMS) residual (the average distance between the location estimate and any one range reading from an anchor). These criteria were inspired by Monica and Ferrari’s work (2015) apart from the PDOP criteria. While simulations and case study trials could determine the true error of the algorithms, true deployment on the ground would have to rely on RMS residual because the ground truth is unknown.
1.2 Localization with trilateration algorithms
Within this research, we localized points with two different trilateration algorithms utilizing a barometer in addition to traditional 3D-trilateration. These two algorithms worked on the basis of using the barometer reading and converting the resulting localization problem from three dimensions to two dimensions. The logic behind using the barometer was that we would obtain a lower relative error as we went up further in height—which would, in turn, improve localization accuracy in three dimensions for multiple elevations.
Traditional 3D-trilateration uses range measurements D from n anchors to resolve a location. Resolving a location works on the principle of minimizing E, the sum of squared errors ei as seen in Equation (4). ei is the distance error between the true distance Ri to actual target (x, y, z) and the range measurements Di from each anchor i(xi,yi,zi); where anchor i is an element of n anchors. The location is then derived with non-linear least squares (NLSQ) numerical solvers, or approximated with linear least squares (LSQ) solvers (Murphy Jr. & Hereman, 1999).
4
The first barometer-assisted algorithm uses the height reading h to find the horizontal projection P of range reading D and deriving an x-y estimate closest to P as seen in Figure 3 (Goh et al., 2019).
Visualization of horizontal projection model from the perspective of anchor i
Horizontal projection P is derived from finding the angle θ formed between the range reading D and barometer reading h, as shown in Equation (5):
5
We then follow by taking the cosine component of range measurement Di for the horizontal projection Pi as seen in Equation (6):
6
An alternative way to obtain horizontal projection Pi for anchor i would be to take the square root of the difference between squared vertical distance and squared range measurements, as seen in Equation (6). This method can be considered if there are hardware and/or coding restrictions in calculating trigonometric functions.
We then derive the estimate (
), from the minimized sum of squared errors E as seen in Equation (7). For this algorithm, the z-estimate 
is our barometer reading h:
7
The sum of squared errors in Equation (7) is in two dimensions. We can find the sum of squared errors from this method in three dimensions by substituting the barometer reading as shown in Equation (8):
8
where 
is the distance from the estimate point (
) to anchor i (xi,yi,zi).
The algorithm based on Equation (7) shall be termed as the horizontal projection method within this paper.
The second barometer-assisted algorithm directly substitutes the reading into the sum of least squares formula and evaluate an estimate as seen in Figure 4.
Visualization of direct substitution model from the perspective of anchor i
The resulting equation as expressed in Equation (9) reduces the number of unknowns to two dimensions instead of three, and the sum of squared errors is in three dimensions:
9
The algorithm based on Equation (9) shall be termed as the direct substitution method within this paper.
We compared the barometer reading h to the anchors’ z-coordinates to determine the anchors that could be used for localization. From there, the system can select anchors that have range measurements D less than or equal to the maximum communications range Rc as shown in Equation (10):
10
An alternative method would be to select anchors that are within a vertical range surrounding the target point using the criteria listed in Equation (11), as the BC Helix would have target points within tetrahedron units of four anchors:
11
After this initial selection of anchors, we need to determine whether the target is too close to the anchor. Both barometer algorithms have a dependence on the barometer’s relative error, and will subsequently meet limitations when the target is too close to the anchor.
For the horizontal projection algorithm, this is because the horizontal projection P is calculated from range measurement D and height measurement h. A target too close to the anchor in the z-axis would mean P converges to D, which would result in a matrix singularity—and thus no solution when calculating through the LSQ method.
This paper has its simulations calculate an initial estimate for both horizontal projection and direct substitution methods using the LSQ method before passing this initial estimate to the NLSQ methods. As such, the criteria for anchors to be usable for localization is for range measurements D to be greater than the vertical gap between the target and the anchor and listed here as Equation (12):
12
If there are anchors that do not exhibit the criteria established in Equation (12), we consider these anchors too close to the target and thus isolate them. We then derive an initial estimate based on the centroid of these anchors. Otherwise, we can find an initial estimate through LSQ solvers. The initial estimate is passed through NLSQ solver as per normal to find the localization accuracy.
For real-time implementation, the user can choose not to remove the anchors exhibiting these problems; this would prevent the algorithm from finding less than four viable anchors to make an estimate and consequently crashing.
Another alternative to real-time implementation would be to generate the initial estimate on startup of the algorithm and use the last logged location estimate as the initial guess; this would reduce the calculation steps needed for the real-time algorithm.
2 SIMULATION AND PARAMETERS
We created simulations testing various properties of the BC Helix in localizing points with MATLAB. Within these simulations, we sought to examine three main issues: The first issue was whether the scale of separation between localization nodes would affect the resulting localization performance; the second issue was whether localization performance would be affected as more points were added to the network of nodes forming the BC Helix; and the third issue was whether the BC Helix geometry would actually perform better than a random placement or regular placement.
We have three main metrics within these simulations: computation time, true error, and RMS residual. Computation time is the amount of time taken for the localization algorithm to derive an estimate. True error is the amount of deviation a location estimate has from the true location of a point. RMS residual is the average deviation a location estimate has from an anchor’s range reading D, which is expressed in three dimensions for the purposes of this paper.
Within these simulations, we also tested for three trilateration algorithms: 3D-trilateration, a barometer-assisted algorithm that derives a horizontal projection P from range readings D and barometer reading h before minimizing the sum of squared errors based on P, and a barometer-assisted algorithm that directly substitutes barometer reading h into the system of equations determining the squared errors derived from range readings D. Within these algorithms, we first find an initial guess using linear least squares (LSQ) solvers before passing on these initial guesses into non-linear least squares (NLSQ) solvers.
We also tested three variants for points generated within different sectors of the BC Helix when examining the effects of edge length separation and adding new vertices to the helix. The test of three different target location loci was to examine whether localization performance would change depending on the target’s location within the BC Helix. The first variant was pointing anywhere within the BC Helix; the second variant was pointing within the internal cylinder of the BC Helix; and the third variant was pointing in the outer ring of the BC Helix—in between the internal cylinder and the radius of the BC Helix.
Figure 5 shows the three variants of generated points.
Boerdijk–Coxeter Helix and variations of randomly generated points
We conducted these simulations with some common parameters as shown in Table 1.
Overview of common variables used for Boerdijk–Coxeter Helix simulations
The simulations are all normalized to the maximum communications range of the anchors Rc. The standard deviations of measurement noise were based on experimental readings we did on a BitCraze LPS Ultra Wideband (UWB) system and an BMP388 barometer. The standard deviation of range measurement noise σD is based on the measurement percentage error of the BitCraze UWB unit, taken from prior experiments shown in Table 2 BitCraze LPS Range readings.
BitCraze LPS range readings (mm accuracy)
Figure 6 shows BitCraze LPS percentage errors across range intervals.
BitCraze LPS percentage errors across range intervals
The standard deviation of barometer measurement noise σh is a normalized value based on a maximum range of 25 m for the BitCraze UWB unit, with an average height measurement error of 0.275 m at 25 m. The height measurement error of 0.275 m was derived from a test of the BMP388 barometer across a height of 0.1 m to 30 m, where the root-mean-square error (RMSE) was 3.29193 Pa and translated as per Equations (13) and (14):
13
14
At dP =±3.29193 Pa and P0 = 101325 Pa, relative accuracy in height dh is therefore a range of 0.2746 m to 0.2754 m. The average height measurement percentage error of 0.275 m at 25 m then translates to 0.011 as a normalized value.
2.1 Effects of edge length separation/scaling
Within this simulation, we tested for two factors: the effects of localizing points within or outside of the helix’s internal cylinder, and the effects of RMS residual, true error, and computation time when the anchors were placed at fractions of their maximum communications range between each other.
We generated random points within the target area and ran location estimates with both 3D-trilateration and barometer-assisted algorithms. We generated the helix based on the edge length gap between anchors and how high we needed this helix to reach.
Because the helix is affected by edge length for its height, altering the edge length would also alter the number of anchors (i.e., vertices) required to build the helix. For this simulation, we tested in set ratios of Rc in intervals of 0.1, from 0.1Rc to unit edge length Rc itself.
Within this simulation, we had two additional metrics for the localization performance: PDOP and error occurrence. PDOP is the general rating of how well the anchors are placed relative to each other. PDOP, in this case, is more of a confirmation of whether the proximity of the anchors between each other affects localization accuracy than an actual assessment criterion. Error occurrence is the number of times the localization algorithm encounters height readings that exceed that of the range reading; this usually occurs when the target is close to an anchor.
Error occurrence is also split into two sub categories. Singularity error counts all cases of the target being too close to any number of anchors within the network, which then causes the LSQ solvers to be unable to compute a solution. Critical error counts all cases where more than half the anchors in the network are too close to the target; we consider localization to be inaccurate in this scenario as the simulation will usually skip onto the next iteration for another localization attempt.
2.2 Edge length separation/scaling results
As seen in Figure 7, direct substitution of the barometer reading yields equal computation time as 3D-trilateration through the edge length ratios. The horizontal projection algorithm using the barometer reading unfortunately performed the worst of the three algorithms, being the fastest at 0.5 Rc and the slowest at 0.1 Rc. The horizontal projection algorithm also experienced increased computation time after 0.5 Rc, peaking at 0.7 Rc before reducing computation time to a similar minimum time at Rc.
BC Helix localization performance from 0.1 of unit edge length to unit edge length Rc (computation time, true error, RMS residual)
Both barometer-assisted algorithms still retain higher true error than 3D-trilateration from 0.1 to 0.9 Rc, but their true error becomes smaller than that of 3D-trilateration from 0.9 Rc onwards. All three algorithms only have similar true error or accuracy at unit edge length itself, with the direct substitution algorithm having a narrower gap in true error from 3D-trilateration through all edge length ratios as seen in Figure 7. In this scenario, the direct substitution method yielded lower true error values and is more accurate than the horizontal projection method.
3D-trilateration yielded the lowest RMS residual as seen in Figure 7. The RMS residual of both barometer algorithms are still worse than 3D-trilateration, with the direct substitution algorithm having a smaller gap than 3D-trilateration. For the barometer algorithms, there is a clear trend of RMS residual being minimal at 0.2 Rc and peaking maximum uncertainty at 0.7 Rc before tapering off at Rc itself.
From the performance of all three algorithms, we could immediately conclude that directly substituting the barometer reading to resolve a location estimate is more accurate and precise than attempting horizontal projection.
While we could determine which barometer-assisted algorithm to use, the three metrics mentioned do not show a clear answer in figuring out the most optimal edge length separation between anchors. As a result, we looked at two additional factors: first was the PDOP, which could hint at the best separation to space out anchors, and second was the number of occurrences in which we encountered targets being too close to an anchor—an optimal edge length separation would minimize such occurrences.
Correlating localization accuracy and computation time with PDOP, however, is where the results begin to look paradoxical.
As seen in Figure 8, the lowest PDOP is found at 0.2 Rc, but 0.2 Rc has the highest number of occurrences where targets get too close to the anchor. The lowest rates of singularity scenarios occurred at 0.5 to 0.6 Rc onward, but the chances of more than half the anchors being too close to the target increased from 0.6 Rc onward.
BC Helix localization performance from 0.1 of unit edge length to unit edge length Rc (PDOP and anchor singularity errors)
However, we also find that the PDOP of the anchors reach a temporary plateau from 0.6 to 0.7 Rc. Additionally, critical error issues have the lowest occurrence at 0.6 to 0.7 Rc before crossing into approximately the same number of occurrences as anchor singularity issues at 0.8 Rc also shown in Figure 8.
When comparing the localization performance for points within specific areas of the BC Helix, we found that the overall localization performance more closely resembled that for points within the outer ring of the BC Helix as seen in Figures 9 and 10. We also find that points within the internal cylinder of the BC Helix experience better localization performance (shorter computation time, lower true error, and lower RMS residual) than points within the outer ring of the BC Helix. As the points within the BC Helix are much more centralized within the loci of the BC Helix and have greater distribution of range readings, this is an expected result.
BC Helix localization performance from 0.1 of unit edge length to unit edge length Rc (computation time, true error, and RMS residual). Graphs of the internal cylinder data are on the left while the right shows graphs of the data from the outer ring
Helix localization performance from 0.1 of unit edge length to unit edge length Rc (PDOP and anchor singularity errors). Graphs of the internal cylinder data are on the left while the right shows graphs of the data from the outer ring
Looking at the algorithms’ overall performance, we can infer that it is safe to attempt placing anchors between each other from 0.5 Rc onward (i.e., at least half of the anchors’ maximum communication range). The direct substitution and 3D-trilateration method experience the smallest difference in performance between 0.6 to 0.9 Rc, with the direct substitution method performing similar to 3D-trilateration at unit edge length itself.
2.3 Effects of increasing BC Helix nodes/vertices
While the Boerdijk–Coxeter Helix has a defined geometry, we still need to know whether localization accuracy is consistent throughout the entire length of the helix or if the localization accuracy changes as the helix expands. In this case, the vertical length of the helix (i.e., z-axis) increased as more vertices are added.
As vertices on the Boerdijk–Coxeter Helix are well defined, the independent variables would be the number of anchors n, the noise ratio σD for range measurements D, and the noise ratio σh for barometer measurement h. The random variable is that the points generated within the space of a helix with n anchors. To normalize the results, we assume that unit edge length (i.e., Rc = 1). We tested from 4 anchors to 100 anchors for the number of anchors n.
2.4 BC Helix nodes/vertices results
Across all sets of points, the horizontal projection barometer algorithm performed worse than 3D-trilateration and the direct substitution barometer algorithm as seen in Figure 11. The direct substitution method had similar computation time to traditional 3D-trilateration, but yielded lower true error values. In other words, the direct substitution method computed equally fast as 3D-trilateration but at a better accuracy.
Localization performance from 4 anchors to 100 anchors in BC Helix (overall)
RMS residuals derived from barometer-assisted methods (horizontal projection and direct substitution) were worse than 3D-trilateration for all sets of points. The direct substitution method had a smaller RMS residual than the horizontal projection method, and the gap in RMS residual was actually wider for points outside of the BC Helix’s internal cylinder.
Comparing the localization performance for points within specific regions of the BC Helix, we found that the direct substitution algorithm trades off a slight increase in computation time for better accuracy across all regions of the BC Helix.
Points within the internal cylinder also experience better localization performance with shorter computation time, lower true error, and lower RMS residual compared to points within the outer ring of the BC Helix, as seen in Figure 12. Surprisingly, the computation time for both internal cylinder and outer ring variations did not experience a major increase as compared to the scenario of the whole BC Helix loci.
Localization performance from 4 anchors to 100 anchors in BC Helix. Data from the internal cylinder is graphed on the left while data from the outer ring is graphed on the right
For all three algorithms across all regions of the BC Helix, the computation time, true error, and RMS residual fluctuated within a small range from 4 anchors to 100 anchors. In other words, the number of anchors did not adversely affect the localization performance of the algorithms and it is expected that the algorithms will perform consistently as the BC Helix expands further in a set direction.
2.5 Anchor configuration
We also need to examine and confirm whether anchors placed in the BC Helix configuration provide better localization accuracy than random placement or a specific preset configuration. This simulation focused specifically on anchor placements while keeping the other parameters the same.
We used six anchors across all types of configurations, as we intended to conduct field tests with the same number of anchors. Three configurations were tested: the BC Helix format where anchors were placed at the vertices of the helix; a random format where the locations were randomly generated on the border of the helix’s circumference (similar to our previous simulation testing the viability of the barometer-assisted algorithms); and finally, a set configuration where each anchor was a progression in height and angular separation. The maximum height all anchors could reach was the maximum height of the BC Helix to maintain a fair comparison between the three.
The placement of the random anchor configuration and set anchor configuration could be seen as analogous to placing points on the outer surface area of a cylinder that the BC Helix occupies. Target points for localization were generated anywhere within this cylindrical and BC Helix loci. A sample scenario of all three types of anchor configurations can be seen in Figure 13.
Sample scenario of anchor configurations being tested
The set configuration is determined by the number of anchors and the maximum height as shown in Equation (15). The number of anchors affects the angular separation in the x-y plane, and the anchors are spaced equally within the z-axis:
15
The remaining parameters are as listed in Equation (16):
16
For this simulation, we set the scaling factor Rc = 1 to normalize the results. We tested for 100 sets of range readings over 100 randomly generated sets of anchors, yielding over 1,000 randomly generated target points. To confirm the correlation between PDOP and localization accuracy, the PDOP of points being localized against the various configurations were calculated and recorded for statistical analysis.
All anchor configurations were tested with one trilateration algorithm only; this was to isolate the effects of anchor arrangement and compare methods separately across simulations later. We also tested for points generated anywhere in the BC Helix instead of splitting across specific sectors.
2.6 Anchor configuration results
With six anchors, the BC Helix configuration performed better than random placement across all parameters, regardless of the location of the target points within the BC Helix. The regular arrangement’s performance depended on the algorithm used: it performed the worst with 3D-trilateration, but had accuracy between a random setup and the BC Helix setup.
The irregular performance of the regular arrangement across algorithms meant it was not a safe arrangement to use immediately, and more research is needed to optimize a regular configuration different from the BC Helix configuration.
The direct substitution method obtained shorter computation times than 3D-trilateration, and retained a similar scale of timing across the anchor configurations. Surprisingly, the direct substitution method retained a similar scale of magnitude with its RMS residual, and the RMS residual can actually be smaller than that of 3D-trilateration when using random arrangements or regular arrangement.
The RMS residual of the direct substitution method was higher than that of 3D-trilateration only with the BC Helix formation. While this was predicted based on the simulation results, the scale of the difference between the two methods was actually very small, to the scale of the 4th decimal point (0.0005).
The PDOP was not affected by the algorithm used, but by the random points generated and the subsequent range readings from the different anchor configurations. Nonetheless, the BC Helix arrangement yielded the lowest PDOP value. This also ties back in with the assumption that a lower PDOP allows for better localization accuracy—which the comparison between anchor configurations also show.
In general, the BC Helix configuration had a lower true error (and is thus more accurate) than the randomly arranged anchors, but had a slightly higher RMS residual (therefore it was not as precise). The BC Helix configuration also had a shorter computation time on average compared to a random configuration, although regular geometries need to be further examined for a definitive comparison to the BC Helix configuration.
The mean of each parameter for all anchor configurations are shown below in Table 3 sorted by each algorithm used.
Table of mean results for anchor configurations calculated with NLSQ solvers
2.7 Summary of simulation results
For the BC Helix and 3D-node placement simulations, the formation shows promise in cutting computation time for localization. The greater advantage of the formation however seems to lie in improving the accuracy of the estimated point compared to any random formation.
In terms of barometer-assisted algorithms, the direct substitution algorithm yielded similar computation times to 3D-trilateration while producing higher accuracy, thus it is advised to adopt this method including the barometer reading compared to converting the reading through horizontal projection and introducing further ambiguity within the estimate.
We also found that points within the internal cylinder region of the BC Helix experience better localization performance compared to points in the outer ring of the BC Helix. This means it is best for the user to travel within the central region of the BC Helix. The low deviation in computation time, accuracy, and uncertainty as more anchors are placed to lengthen the BC Helix formation indicates that the user can expect relatively stable performance within most regions of the BC Helix.
3 EXPERIMENTAL VALIDATION
We conducted our experiment by comparing the BC Helix setup of node placement to a random placement. The experiment was conducted in a spiral staircase leading up to three floors within the central area of the university campus and measurements were taken of the internal diameter of the spiral staircase in order to obtain the BC Helix coordinates.
The internal diameter was 6.74 m, which translates to a radius of 3.27 m for the BC Helix. The internal cylinder radius based off the helix radius of 3.27 m was 1.3875 m. The height from the ground level to the ceiling of the 3rd floor was 11 m, while the gap between the 1st floor and the 2nd floor was measured at 6 m, and the gap between the 2nd and 3rd floors was measured to be 4.5 m. Thus, the height-to-horizontal-radius ratio was 3.36:1.
However, because the heights prescribed by the formula were not mappable for the spiral staircase within the test site, the BC Helix required anchors to be hung from the ledge of the spiral staircase using fishing line. The fishing line attached to each anchor was adjusted to specific lengths so the anchors would ultimately end up within the specified formation.
Figure 14 illustrates the test site layout of the anchors in the BC Helix formation from a bird’s eye view.
Test site layout of the anchors in the BC Helix formation
To compare between the BC Helix arrangement and random node arrangements, we took readings of the same test points with two different sets of coordinates: one set of coordinates for the BC Helix configuration, while the other set of coordinates that were random were found appropriate to mount UWB anchors on.
Table 4 shows these different sets of coordinates for anchor placement.
Coordinates of anchors for field trial (node configuration)
We also decided to split test points based on the region of the BC Helix between the internal cylinder region and the region outside of the internal cylinder. This was to determine if there was any difference in localization performance for points within these two regions. Table 5 shows the coordinates of the test points.
Coordinates of test points for field trial (node configuration)
Figure 15 shows the layout of the points when subject to both anchor configurations.
Layout of anchor configurations for field trial. BC Helix configuration with a visualized helix is on the left while data from a random configuration is on the right
To position test points, we utilized two different methods. For points within the internal cylindrical loci of the BC Helix, we used a ceiling winch within the test site to hoist the UWB tag to various heights. To simulate points outside of the internal cylindrical loci of the BC Helix, we attached the BitCraze Roadrunner to an extendable pole and extended segments accordingly.
The UWB tag was comprised of a power bank supplying power to both the BitCraze Roadrunner and an Adafruit BMP388 paired with a Raspberry Pi Zero W. Figure 16 shows the Roadrunner UWB tag with the separate BMP388 barometer.
Roadrunner UWB tag with Raspberry Pi and BMP388 barometer. The BMP388 with Raspberry Pi Zero W is on the left while the right depicts the BitCraze Roadrunner
We took two minutes’ worth of readings for each test point with the algorithm localizing every 100 ms. That would translate to about 1,200 readings in total for each test point. We also chose to compare only the direct substitution algorithm against traditional 3D-trilateration in this experiment, because the direct substitution algorithm has shown consistently better performance as a barometer-assisted algorithm within the simulations.
3.1 Hardware Setup
We used Loco Positioning System (LPS) units supplied by BitCraze for the anchors and a Roadunner unit from BitCraze as the target receiver. Both the LPS and Road-runner utilized DWM1000 UWB units, and were rated to be able to transmit and receive up to 10 m based on their default power settings.
We chose the BitCraze Roadrunner because it combined a UWB unit, accelerometer, and BMP388 barometer unit in the initial beta release—a combination of sensor units within a portable package that was particularly suitable for our applications. By the time we purchased these units, however, the final released units did not include the barometer.
As a result of obtaining the Roadrunner units without the barometer, we used separate BMP388 barometers sold by Adafruit to obtain height readings. To do so, we used a reference barometer at the ground level of our test site and a target barometer attached to the Roadrunner.
The reference barometer was powered and programmed through an Arduino board which was connected to the logging computer. The barometers attached to the Roadrunner target were paired with a Raspberry Pi Zero W that sent back height readings using Secure Shell (SSH) protocol. Our logging computer was a Dell Precision 5510 laptop running an i7 chip, with Ubuntu OS to facilitate interfacing with the BitCraze hardware.
As the BitCraze firmware operates with C language and its UI interface works in Python, range readings and barometer readings from Python had to be imported into a MATLAB function containing our algorithms. The MATLAB function subsequently calculated a location estimate, its corresponding RMS residual, and computation time back to Python to log as a separate data file. True error from ground truth was calculated separately using the logged location estimates.
We used the Stanley Fatmax TLM 330s laser rangefinder to find reference distances and ground truth; it has a rated accuracy of ±1.5 mm at 10 m. For the field trial testing for the BC Helix formation, we also used a measuring tape rated to mm accuracy that could measure up to 5 m—this was mainly used to measure the length of the extendable pole and therefore set reference heights for our test points.
3.2 Results and discussion of experiment
For the BC Helix configuration as seen in the Table 6 algorithm results, all test points encountered shorter computation time and higher RMS residual over 3D-trilateration. These points still followed the trends of our simulation results comparing the barometer algorithm against 3D-trilateration.
Algorithm results using BC Helix configuration
In terms of accuracy expressed in true error however, multiple test points had the barometer algorithm perform worse than 3D-trilateration. However, the trend of the barometer having a lower relative error as height increases still holds true. For test points with higher altitudes, the extent of relative error is better than for the test points closer to the ground.
For the random configuration result seen in Table 7, all test points (test points 1 to 4) within the internal cylindrical loci saw a significant downgrade in accuracy with the barometer algorithm compared to 3D-trilateration. Only the test points outside of the internal cylindrical locus (test points 5 to 7) had better accuracy with the barometer algorithm than with 3D-trilateration.
Algorithm results using random configuration
However, half the test points (test points 1, 5, and 6) exhibited worse computation time with the barometer algorithm than 3D-trilateration, with test point 1 experiencing the worst accuracy on top of a longer computation time. The barometer experiencing less relative error as height increased also manifested itself within this configuration, with the degradation of true error in localizing points improving for test points with higher altitudes.
As for barometer performance itself, Table 8 shows the barometer’s measurements for the BC Helix and the random formation.
Performance of barometer
The barometer has lower mean relative error across most test points in the random formation compared to the BC Helix formation. However, no definite conclusions could be drawn regarding whether anchor formation impacts barometer performance because the height readings for the random formation fluctuated as time went on.
From test points 2, 3, and 4 within the internal cylindrical locus of the BC Helix, the height readings were higher on average compared to the actual height. In addition, it was found that the barometer performed the best for test points 3 and 4 within a BC Helix formation—making any deduction about anchor geometry affecting barometer performance ambiguous.
However, as the barometer measurement is independent from any range readings between the anchors and tag, anchor geometry is unlikely to affect the accuracy of the barometer. Instead, it is more likely that the barometer will either experience severe noise in its readings or the pressure at the test site will change over time and temperature.
Given the significant relative error of the barometer at lower heights in the test ground, it was found that the barometer’s accuracy became the largest factor in determining localization accuracy. Upon further inspection of the relative errors encountered by the range measurements and the barometer, we found that the barometer had greater percentage error compared to the range measurements at various points. The measurement percentage errors for range measurements and the barometer during both formations are listed in Table 9.
Measurement percentage errors
When the barometer had a lower percentage error than at least half of the anchors’ range measurements, the barometer algorithms performed better than 3D-trilateration. Conversely, the localization accuracy was worse with the barometer-assisted algorithms when the barometer had worse precision than the range measurements. This turned out to corroborate the barometer algorithms failing when the barometer had worse noise and error than the range measurements.
In addition, while the test site was chosen because the height-to-radius ratio was significant enough to test the research, the radius was relatively small at only 3.27 m and could have limited the magnitude of range readings possible. In other words, the test site might be sufficiently small for measurement error to be significant. Given the drastic difference in performance we see in standalone barometer trials versus field trials, it is suspected that a larger scale test site could provide a more definitive answer with both anchor geometry and the barometer’s improvement towards localization accuracy.
In light of these results, we can conclude that the BC Helix is a more reliable formation in preventing malfunctions in localization, while random configuration is more likely to incur unstable localization performance.
4 CONCLUSION
We proposed the Boerdijk–Coxeter Helix (BC Helix) geometry as a solution to accommodate the largest volume possible, keeping anchors within the best communications range between each other, and a sufficiently regular pattern that would allow the human user to plant new points along the path where he or she travels.
From our simulations of edge length ratios to the formation of anchors in a BC Helix formation, it is recommended to place anchors at a distance above half of their maximum communications range between each other for optimal performance in accuracy and localization time. We expect this optimal range between anchors to hold for other regular geometric formations.
While there was a small increase in computation time when the BC Helix exceeded 55 anchors within our simulations, the relatively stable performance in accuracy and computation time of the algorithms with the BC Helix formation indicated that this was not a major problem. We also found that the BC Helix did improve localization accuracy and time within the three dimensions of our simulations, and the field trial with the BC Helix formation showed similar results.
The field trial of the BC Helix formation in placing anchors shows promise in providing a more stable localization performance while providing a regular layout for human users to set up as their localization network. Points closer to the center region of the BC Helix also get better localization performance by virtue of having a more evenly distributed set of range readings.
We also found within our simulations and field trial that the barometer-assisted algorithms work in conjunction with the BC Helix formation in improving computation time and accuracy. The benefits of the barometer algorithms still hold within the field trial, in that it experiences lower error as the target goes through higher altitudes.
Possible future research would include adapting the BC Helix formation such that different helices could be linked and finding alternative formations such that individual area segments could contribute to an optimal node arrangement for a combined area. Examining potential formations that allow the mobile movement of nodes (Han et al., 2013) so that a group of human users could be a moving network (McIntire et al., 2018) to localize themselves instead of planting a network of anchors would be a bigger step towards developing an independent localization network for humans.
HOW TO CITE THIS ARTICLE
Ann AGC, Foong S, Ahmed A, Soh, GS. Adapting the Boerdijk–Coxeter helix as node configuration for GPS-denied localization in three dimensions. NAVIGATION. 2021;68:485–506. https://doi.org/10.1002/navi.446
CONFLICT OF INTEREST
None.
Footnotes
Funding information
This research received no specific grant from any funding agency, commercial, or not-for-profit sectors.
- Received April 6, 2020.
- Revision received January 5, 2021.
- Accepted July 31, 2021.
- © 2021 Institute of Navigation
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
Jump to section
Related Articles
Cited By...
- No citing articles found.