A combined algorithm for tunnel personnel localization based on error areal division

Abstract

In a tunnel personnel positioning system, the average positioning error is typically used to reflect the precision and accuracy of the positioning algorithm. However, in practical applications, the error areal distribution is generally non-uniform. The positioning errors of some areas are greater than the average positioning errors, which lead to a low positioning accuracy. In this study, based on the simulation of the positioning error areal distributions of the quadrilateral centroid localization and maximum likelihood estimation algorithms, the causes for large positioning errors in upper and lower edges and four corners were analyzed. In addition, a combined localization algorithm based on error areal division was proposed to improve the average positioning accuracy. Thus, the quadrilateral centroid localization algorithm was used for the middle section of the tunnel personnel location area, the maximum likelihood estimation algorithm was used for the upper and lower edges, and the centroid algorithm was used for the four corners. The simulation results show that the average positioning errors of the combined localization algorithm were reduced by 5.56% and 44.76% when compared with those of the quadrilateral centroid localization and maximum likelihood estimation algorithms, respectively, while the maximum positioning error was reduced by 46.45% and 42.81%, respectively.

Keywords

Tunnel personnel positioning average positioning error combined localization algorithm error areal division

Introduction

With the development of tunnel engineering in China, indoor positioning technology has become widely used in tunnel engineering. In tunnels, the construction environment is poor,¹ the reference node layout is irregular, and the positioning signal attenuation is large, which lead to an uneven error in areal distribution in the tunnel personnel positioning system, where the positioning errors of some edge areas are greater than the average positioning errors. Therefore, it is necessary to find a method to reduce the maximum positioning error of some edge areas. In this study, the positioning error distribution characteristics of common algorithms were studied, the cause of large positioning error was analyzed in some edge areas based on the simulation results, and a combined localization positioning algorithm for tunnel personnel based on error areal division is proposed. The purpose was to improve the positioning accuracy and safety of tunnel personnel during construction.

The most commonly used wireless tunnels positioning technologies in tunnels include ZigBee technology, chirp spread spectrum (CSS) technology, and ultra-wideband (UWB) technology. ZigBee can achieve real-time positioning of tunnel personnel, which requires a large number of reference nodes.^2,3 UWB technology has strong anti-interference and high ranging accuracy; however, it has low transmission effective distance and high cost.^4,5 Compared with the above methods, CSS technology has a lower transmission power, longer transmission distance, and lower cost.^6,7 Considering the feasibility of the technology, high-performance requirements, and cost of tunnel personnel positioning systems, CSS technology was selected for the proposed tunnel personnel positioning system. The most commonly used measurement technologies in tunnels include time of arrival (TOA),⁸ time difference of arrival (TDOA),⁹ angle of arrival (AOA),¹⁰ and received signal strength indicator (RSSI).¹¹ TOA and TDOA require high-precision time synchronization between the reference nodes, and the hardware cost of the system is high. The AOA is greatly affected by the environment and antenna, such that the error is relatively large. The RSSI is based on the wave propagation loss model of the signal in free space, for which there is no need for time synchronization or an additional transmission module. This technology has low cost and high feasibility. Therefore, in this study, the RSSI positioning method was selected for the proposed tunnel personnel positioning system.

At present, the most commonly used tunnel personnel positioning algorithms include the centroid algorithm, maximum likelihood estimation algorithm, weighted centroid algorithm, trilateral measurement algorithm, quadrilateral measurement algorithm, trilateral centroid localization algorithm, and quadrilateral centroid localization algorithm. The characteristics, evaluation indices, and simulation environments of the above-mentioned algorithms are listed in Table 1. The centroid algorithm is often used in indoor positioning technologies. The cost of this algorithm is low, and the algorithm itself is simple; however, this algorithm is not suitable for a complex positioning environment.³² The weighted centroid algorithm^28–31 is based on the centroid algorithm with the addition of a weighted factor. Researchers have improved the positioning accuracy by continuously optimizing the weighted factor. The trilateral measurement algorithm^21–23 is easily affected by the actual environment when measuring the distance between the reference node and the positioning node, which results in three circles being unable to intersect at one point. Based on the trilateral measurement algorithm, a group of reference nodes is added to the quadrilateral measurement algorithm^19,20 to reduce the influence of closed areas; however, there is still a problem with four circles not intersecting at one point. The maximum likelihood estimation algorithm^24–27 can solve this problem and improve the positioning accuracy. The trilateral and quadrilateral centroid localization algorithms^12–18 locate the centroid through the intersections of three or four circles, respectively. In the early stage, the most widely used positioning algorithm is the trilateral measurement algorithm; however, the accuracy of the trilateration measurement algorithm is low. Among the improved localization algorithms proposed by researchers based on this algorithm, the quadrilateral centroid localization and maximum likelihood estimation algorithms are commonly used as they have higher positioning accuracy. Therefore, the quadrilateral centroid localization and maximum likelihood estimation algorithms were selected to simulate the areal distribution of the positioning error.

Table 1.

Common tunnel personnel location algorithm and simulation parameter analysis.

Algorithm	Details	Simulation parameters and evaluation indices	References
Trilateral and quadrilateral centroid localization algorithms	Combination of weighted centroid location with the gradient descent method.	PA: 4 m × 4 m NOUN: 10 EI: average positioning error	Zhang and Wang¹²
	Combining the quadrilateral measurement algorithm with the weighted centroid algorithm.	PA: 600 m × 600 m NOUN: 1 EI: average positioning error	Zhang et al.¹³
	The isosceles triangle reference node layout model is established.	PA: 8 m × 8 m NOUN: 10 EI: average positioning error, mean square error	Wang et al.¹⁴
	Combining the centroid algorithm and weighted factor with trilateral measurement algorithm.	PA: 16 m × 120 m Distance between reference nodes: 20, 24, 30 m NOUN: 95,381 EI: average positioning error, mean square error	Wang et al.¹⁵
	Based on the traditional trilateral localization algorithm, the centroid algorithm is combined.	PA: 25 m × 15 m NOUN: 50 EI: average positioning error	Huangfu et al.¹⁶
	The distance deviation coefficient is updated repeatedly to update the positioning result.	PA: 40 m × 40 m NOUN: 50 EI: average positioning error	Chen et al.¹⁷
	The trilateral centroid localization algorithm is used to locate the position node n times.	PA: 1 m × 1 m NOUN: 1 EI: the localization result of mobile node’s trajectory	Qiu et al.¹⁸
Trilateral and quadrilateral measurement algorithms	Newton iteration is used to refine the distance between the unknown and reference nodes.	PA: 1 km × 1 km NOUN: 200 EI: average positioning error	Cheng and Sun¹⁹
	Combined with the quadrilateral measurement algorithm and dynamic weighted factor.	PA: 20 m × 10 m NOUN: 4 EI: weighted factor index error, average positioning error	Wang et al.²⁰
	Combined with the trilateral measurement algorithm; provides a node selection strategy and filtering.	PA: 1 km × 1 km NOUN: 100 EI: average positioning error	Zeng et al.²¹
	The location model is constructed using the lost location information, and the positioning model is solved to improve the positioning accuracy.	PA: 5 m × 100 m NOUN: 10 EI: average positioning error	Gao and Yang²²
	The centroid localization algorithm is improved to solve the shortcomings of the trilateral measurement algorithm using the Eddystone technology.	PA: 12 m × 12 m NOUN: 10 EI: positioning error	Zhou et al.²³
Maximum likelihood estimation	1. The pre-processing algorithm optimizes the coordinates. 2. Combined with the maximum likelihood estimation algorithm.	PA: 13 m × 15 m NOUN: 9 EI: error probability, average positioning error	Geng et al.²⁴
	1. The least squares method is used to find the maximum likelihood equations. 2. The influence of the reference node on the positioning error is analyzed.	PA: 30 m × 30 m NOUN: 4 EI: average positioning error, maximum positioning error, minimum positioning error	Zhong et al.²⁵
	The global maximum of the likelihood function is obtained by the Newton iterative algorithm, and the least squares solution of the target position is derived.	PA:10 m × 10 m × 10 m NOUN: 8 EI: root mean square error Bias	Zhao et al.²⁶
	The least squares method based on the Taylor series is used to locate the unknown nodes.	PA: 13 m × 13 m NOUN: 20 EI: error variation	Zhan et al.²⁷
Centroid algorithm	An intersection threshold is proposed to compensate for the positioning accuracy using the distance boundary.	PA: 90 m × 90 m NOUN: 21 EI: average positioning error	Kim and Shin²⁸
	The RSSI value of the reference node is used to estimate the position of the adjacent node, and then the weighted centroid value of the adjacent node is used to determine the location of the unknown node.	PA: 20 m × 20 m NOUN: 40 EI: average positioning error	Rahman et al.²⁹
	Based on the improved weighted centroid algorithm, the estimated distance difference is introduced.	PA: 10 m×10 m NOUN: 30 EI: average positioning error	Zhao et al.³⁰
	The unknown and reference nodes are introduced into the centroid formula of the advanced centroid location algorithm.	PA: 100 m × 100 m NOUN: 100 EI: absolute error, relative error	Gong and Wu³¹

RSSI: received signal strength indicator; PA: positioning areal; NOUN: number of unknown nodes; EI: evaluation index.

In summary, researchers generally use optimized and improved measures of ranging and positioning algorithms to improve the overall areal positioning accuracy, as evaluated by the average positioning error. A rectangle was used as the simulation area, with a few simulation nodes. This method could not reflect the areal distribution characteristics of the positioning error as no research that used this method has been reported in the literature. The remainder of this article is organized as follows: the following solutions are proposed. Section “Algorithm and parameters” introduces the principles of two common algorithms and determines the simulation parameters combined with the particularity of a tunnel environment. Section “Simulation and distribution of the positioning error area” discusses the reasons for the large positioning error in some edge areas. Section “A combined algorithm for tunnel personnel localization based on error areal division” presents the proposed combined localization algorithm based on error areal division and the simulation in a tunnel environment. Conclusion is presented in section “Conclusion.”

Algorithm and parameters

Quadrilateral centroid localization algorithm

A quadrilateral centroid localization algorithm is proposed based on the characteristics of the trilateral measurement algorithm, centroid algorithm, and CSS technology. As shown in Figure 1, there are a positioning node (X) and four reference nodes (C₁, C₂, C₃, and C₄) in a tunnel personnel positioning system. Suppose the coordinates of the four reference nodes are C₁(x₁, y₁), C₂(x₂, y₂), C₃(x₃, y₃), and C₄(x₄, y₄), the measured distances between the positioning node and the reference nodes are d₁, d₂, d₃, and d₄. Theoretically, the four circles will intersect at one point, which is the positioning node. However, in the actual environment, the measurement signal will be reflected, diffracted, and scattered, which will lead to ranging error. Therefore, the four circles would intersect in pairs to form a closed quadrangle area (the yellow area in Figure 1) instead of one point. The coordinates of the intersection of the four circles near the positioning node are O(x₁₁, y₁₁), P(x₁₂, y₁₂), Q(x₁₃, y₁₃), and R(x₁₄, y₁₄), and the coordinates of the positioning node are X(x, y), then O(x₁₁, y₁₁) can be obtained as

{\begin{matrix} {(x_{1} - x_{11})}^{2} + {(y_{1} - y_{11})}^{2} = d_{1}^{2} \\ {(x_{2} - x_{11})}^{2} + {(y_{2} - y_{11})}^{2} = d_{2}^{2} \end{matrix}

(1)

Figure 1.

A schematic diagram of the quadrilateral centroid localization algorithm.

Similarly, the coordinate values of P, Q, and R can be obtained by equation (1), and the coordinates of the centroid can be obtained using equation (2)

\begin{matrix} x = \frac{1}{4} (x_{11} + x_{12} + x_{13} + x_{14}) \\ y = \frac{1}{4} (y_{11} + y_{12} + y_{13} + y_{14}) \end{matrix}

(2)

Maximum likelihood estimation algorithm

A schematic diagram of the maximum likelihood estimation algorithm^33,34 is shown in Figure 2. Suppose there are reference nodes C₁(x₁, y₁), C₂(x₂, y₂), …, C_n(x_n, y_n), the distances between the positioning node and the reference nodes are d₁, d₂, …, d_n, and the coordinates of the positioning node are X(x, y), then equation (3) can be obtained as

{\begin{matrix} {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = d_{1}^{2} \\ {(x - x_{2})}^{2} + {(y - y_{2})}^{2} = d_{2}^{2} \\ . . . \\ {(x - x_{n})}^{2} + {(y - y_{n})}^{2} = d_{n}^{2} \end{matrix}

(3)

Figure 2.

Schematic diagram of the maximum likelihood estimation algorithm.

After transformation, the following equation can be obtained

{\begin{matrix} 2 (x_{1} - x_{n}) x + 2 (y_{1} - y_{n}) y = x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} - d_{1}^{2} + d_{n}^{2} \\ 2 (x_{2} - x_{n}) x + 2 (y_{2} - y_{n}) y = x_{2}^{2} - x_{n}^{2} + y_{2}^{2} - y_{n}^{2} - d_{2}^{2} + d_{n}^{2} \\ . . . \\ 2 (x_{n - 1} - x_{n}) x + 2 (y_{n - 1} - y_{n}) y = x_{n - 1}^{2} - x_{n}^{2} + y_{n - 1}^{2} - y_{n}^{2} - d_{n - 1}^{2} + d_{n}^{2} \end{matrix}

(4)

Equation (4) can be expressed in the matrix form $AX = b$ as follows

A = [\begin{matrix} 2 (x_{1} - x_{n}) & 2 (y_{1} - y_{n}) \\ 2 (x_{2} - x_{n}) & 2 (y_{2} - y_{n}) \\ . . . & . . . \\ 2 (x_{n - 1} - x_{n}) & 2 (y_{n - 1} - y_{n}) \end{matrix}]

(5)

X = [\begin{matrix} x \\ y \end{matrix}]

(6)

b = [\begin{matrix} x_{1}^{2} - x_{n}^{2} + y_{1}^{2} - y_{n}^{2} - d_{1}^{2} + d_{n}^{2} \\ x_{2}^{2} - x_{n}^{2} + y_{2}^{2} - y_{n}^{2} - d_{2}^{2} + d_{n}^{2} \\ . . . \\ x_{n - 1}^{2} - x_{n}^{2} + y_{n - 1}^{2} - y_{n}^{2} - d_{n - 1}^{2} + d_{n}^{2} \end{matrix}]

(7)

Using the least squares method, the least squares solution can be obtained as

\hat{X} = {(A^{T} A)}^{- 1} A^{T} b

(8)

The ranging error K in a tunnel environment

The characteristics of wireless electromagnetic wave propagation in a tunnel environment conform to the indoor logarithmic distance path loss model described in Wu et al.³⁵ As shown in equation (9)

PL (dB) = PL (d_{0}) (dB) + 10 γ \log_{10} \frac{d}{d_{0}} + X_{σ} (dB)

(9)

where d₀ is the reference distance (generally set at 1 m for an indoor channel), PL(d₀) is the path loss of the reference distance d based on Wang,³⁶ PL(d₀) = 32.5 in a tunnel environment, d is the distance between the reference node and the positioning node, and $γ$ is the path loss exponent, which is set between 2.1 and 3.3 for an indoor channel environment and to 3.0 in a tunnel environment. $X_{σ}$ is independent of the distance between the reference node and the positioning node, and is usually set to 0 for convenience in calculation.

In actual environment, the measurement signal will be reflected, diffracted, and scattered, which will lead to the ranging error K. Based on the wireless electromagnetic wave propagation model in a tunnel environment and the measurement data in Wang,³⁶ the distance between the reference nodes was set to 60 m. Considering the width of the tunnel, the distance between the reference node and the positioning node was only 61.40 m, and the original ranging error K was set from 0.6 to 3.0 m.

Determination of the simulation parameters in the error area

At present, three one-way three lanes are widely used in motorway designs. Based on the code for the design of highway tunnels (JTG D70-2004), the tunnel excavation width was taken as the simulation environment width of the tunnel, which was set to 17 m. Owing to rough surface resulting from tunnel excavation, it is difficult to achieve an accurate rectangular layout for the reference node. Therefore, the positioning area was taken as an isosceles trapezoid in the simulation process. The simulation parameters are presented in Table 2. A large ranging error causes a large positioning error; thus, ranging errors of K = 2.4 and 3.0 m were simulated.

Table 2.

Simulation parameters for the positioning error area distribution.

Coordinates of reference nodes	Number of positioning nodes	Ranging error K
(0,0), (1,17) (59,17), (60,0)	90,000 randomly generated points in the location area	K = 2.4, 3.0 m

Simulation and distribution of the positioning error area

Based on the ranging error and simulation parameters in the tunnel environment, this study simulated the positioning error areal distribution of two types of tunnel personnel positioning algorithms (i.e. quadrilateral centroid localization and maximum likelihood estimation algorithms). The areal simulation characteristics of the two algorithms were obtained, which provided the basis for the error areal division in section “A combined algorithm for tunnel personnel localization based on error areal division.”

The positioning error $e_{i}$ was used to evaluate the accuracy of the positioning algorithm, as shown in equation (10)

e_{i} = \sqrt{{(x_{s} - x_{g})}^{2} + {(y_{s} - y_{g})}^{2}}

(10)

where (x_s, y_s) are the theoretical coordinates of the positioning node, and (x_g, y_g) are the estimation coordinates of the positioning node estimated by the algorithm.

Simulation of the distribution of the positioning error area using the quadrilateral centroid localization algorithm

Using the parameters listed in Table 2, the distribution of the positioning error area was simulated using the quadrilateral centroid localization algorithm with ranging errors of K = 2.4 and 3.0 m. The distribution of the positioning error area is shown in Figure 3. It can be seen that the distribution of the positioning error area using the quadrilateral centroid localization algorithm was small in the middle and large in the upper and lower edges and four corners. The maximum positioning error occurred at the upper left corner of the positioning area and was significantly greater than the average positioning errors.

Figure 3.

Simulation of the distribution of the positioning error area using the quadrilateral centroid localization algorithm: (a) K = 2.4 m and (b) K = 3.0 m.

Simulation of the distribution of the positioning error area using the maximum likelihood estimation algorithm

Using the simulation parameters listed in Table 2, the distribution of the positioning error area was simulated using the maximum likelihood estimation algorithm with ranging errors of K = 2.4 and 3.0 m. The distribution of the positioning error area is shown in Figure 4. It can be seen that the distribution of the positioning error area using the maximum likelihood estimation algorithm was small in the middle and large on the left and right sides. The maximum positioning error occurred at the lower right corner of the positioning area, and was larger than the average positioning error.

Figure 4.

Simulation map for the distribution of the positioning error area using the maximum likelihood estimation algorithm: (a) K = 2.4 m and (b) K = 3.0 m.

Analysis and discussion of the simulation results

A comparison of the positioning errors between the quadrilateral centroid localization algorithm and the maximum likelihood estimation algorithm is shown in Table 3. It can be seen that the average positioning error of the quadrilateral centroid localization algorithm is smaller than that of the maximum likelihood estimation algorithm; however, the maximum positioning error is greater than that of the maximum likelihood estimation algorithm. Therefore, the quadrilateral centroid localization algorithm was mainly used in the areal division, and the maximum likelihood estimation algorithm was used in areas with large errors.

Table 3.

Comparison of positioning errors in areal distribution between the two algorithms.

Algorithm category	Ranging error K/m	Maximum positioning error/m	Average positioning error/m
Quadrilateral centroid localization algorithm	2.4	2.9178	0.7512
Quadrilateral centroid localization algorithm	3.0	3.6434	0.8685
Maximum likelihood estimation algorithm	2.4	2.7242	1.2320
Maximum likelihood estimation algorithm	3.0	3.4215	1.5468

The following is an analysis for the causes of the large positioning error in areal distribution based on the quadrilateral centroid localization algorithm. Using the simulation parameters listed in Table 2, taking K = 3.0 m, and positioning nodes are X₁ (30, 8.5) and X₂ (30, 2), the circles were drawn by taking the reference nodes (C₁, C₂, C₃, and C₄) as the center of the circle and the distance from the reference node to X₁ as the radius. In order to make the image more concise, only curves in the closed area were retained. D₁ represents the theoretical distance from the reference node C₁ to the positioning node X₁, and d₁ represents its measured distance with ranging error. Due to the positioning error in the actual situation, the circle curve generated by measured radius will form a closed area (the yellow area in Figure 5). Similarly, the area where X₂ is located can be analyzed. The centroid area of the positioning node (X₁ (30, 8.5) and X₂ (30, 2)) in the upper and lower edges was shown based on the quadrilateral centroid localization algorithm.

Figure 5.

Centroid area using the quadrilateral centroid localization algorithm: (a) X₁ (30, 8.5) and (b) X₂ (30, 2).

Figure 5 shows that with the same ranging errors, as the positioning node moves closer to the lower edge, the symmetry of the y-coordinates of the upper and lower vertices of the quadrilateral region becomes worse (with respect to the horizontal line). The quadrilateral centroid localization algorithm used the centroid of the algorithm to estimate the theoretical location of the positioning node. Therefore, the positioning error in the lower edge of the positioning area was larger, that is, the closer to the lower-edge line, the greater the error. This analysis was also applicable to the upper edge.

Next, taking the top left corner as an example, the causes of the large positioning error in the four corners are analyzed. As shown in Figure 6, when K = 3.0 m, the blue areas was defined as the four corners. Taking the reference nodes as the center of the circle, the distance from the reference node to positioning node, X₃, as the radius, theoretically, the four circles would intersect at point X₃. D₁ represents the theoretical distance from the reference node C₁ to the positioning node X₃, and d₁ represents its measured distance. Due to the ranging error in the actual situation, the circle curve would form a closed area (the yellow area in Figure 6). The yellow area represents the actual centroid area.

Figure 6.

Centroid area using the quadrilateral centroid localization algorithm with positioning node located in the left vertex area.

The yellow area in Figure 6 represents the centroid area of the positioning node solved using the quadrilateral measurement centroid algorithm. The observations show that most of the estimated positions of this algorithm were outside the positioning area, which was inconsistent with the actual situation, and thus needs further improvement.

A combined algorithm for tunnel personnel localization based on error areal division

A combined localization algorithm is proposed based on error areal division according to the distribution characteristics of the error area shown in Figures 3 and 4, which was determined using the quadrilateral centroid localization, maximum likelihood estimation, and centroid algorithms. The specific strategies are as follows: the quadrilateral centroid localization algorithm was used for the middle area of the tunnel personnel positioning area, the maximum likelihood estimation algorithm was used for the upper and lower edges, and the centroid was used to replace the estimated locations of all the positioning nodes in the four corners.

The localization algorithm for the four corners

Based on the distribution of the positioning error area simulated using the quadrilateral centroid localization algorithm (Figure 3), the localization of the four corner areas is shown in Figure 7 (when K = 3.0). In this study, the centroid O of the triangle was used as the estimated coordinates (x_g, y_g) of all the positioning nodes in the area. In those areas, the distance d_i from the centroid O to any node X_i is the positioning error $e_{i}$ of the node X_i. The area is very small (The average area is 1.1233 m².), and the distance d_i is also very small.

Figure 7.

Schematic diagram of the four corner positioning areas.

The triangular areas of C₁ and C₄ were exactly the same (as well as those of C₂ and C₃); thus, the positioning errors for the triangular areas of C₁ and C₂ were analyzed.

Assuming the coordinates of nodes X_a, X_b, and X_c are X_a (x_a, y_a), X_b (x_b, y_b), and X_c (x_c, y_c), respectively, the coordinates of the centroid O of area are as follows

\begin{matrix} x_{o} = \frac{1}{3} (x_{a} + x_{b} + x_{c}) \\ y_{o} = \frac{1}{3} (y_{a} + y_{b} + y_{c}) \end{matrix}

(11)

The distances from the three nodes X_a, X_b, and X_c to centroid O are

\begin{matrix} d_{a} = \sqrt{{(x_{o} - x_{a})}^{2} + {(y_{o} - y_{a})}^{2}} \\ d_{b} = \sqrt{{(x_{o} - x_{b})}^{2} + {(y_{o} - y_{b})}^{2}} \\ d_{c} = \sqrt{{(x_{o} - x_{c})}^{2} + {(y_{o} - y_{c})}^{2}} \end{matrix}

(12)

In the area, the farthest node to the centroid O can only appear on the three vertices of the triangle. From equations (10) and (12), that is, d_max is the maximum value of the positioning error.

The maximum positioning error $e_{\max}$ is

e_{\max} = \max {d_{a}, d_{b}, d_{c}}

(13)

According to equations (11)–(13), the maximum positioning error of area of C₁ was $e_{\max}$ = 1.0917 m, while that of C₂ was $e_{\max}$ = 1.1142 m.

Through an analysis of the area of C₁ and C₂, it can be concluded that the maximum positioning error in the four corners of the reference node was 1.1442 m, which basically met the requirements of the tunnel personnel positioning accuracy. Therefore, selecting the centroid to replace the estimated coordinates of all positioning nodes can effectively reduce the positioning error.

The localization algorithm for the upper- and lower-edge areas

According to the distribution of the algorithm for the positioning error area with different ranging errors (as shown in Figures 3 and 4) to study how to divide the positioning error area reasonably. The middle area in Figure 3 is a concave polygon. Based on the concept of compatible triangulation,^37,38 the constraint conditions can affect the presentation of the concave polygon image. To make the generated image sufficiently saturated, the middle area in the non-concave polygonal areas was divided when the grid was constructed for analysis and calculation. In this study, three line segments were selected to replace the upper- and lower-edge arcs, whereas the four corner areas were directly replaced by triangular areas. The quadrilateral centroid localization algorithm was used for the white area and the maximum likelihood estimation algorithm for the yellow area. The blue area used its centroid to represent the estimated location of all positioning nodes in the area. The middle area was divided into three parts (left, middle, and right) by two red dotted lines. This method not only avoids concave polygons but also gives full benefits of the quadrilateral centroid localization and maximum likelihood estimation algorithms.

All the parameters in the areal division of the combined localization algorithm were observed based on the distribution of the positioning error area (as shown in Figures 3 and 4), and the results of the division are shown in Figure 8. D is the edge length of the triangles at four corners, L is the edge length of the upper and lower areas, S is the lateral distance between the reference nodes, K is the ranging error, and W is a parameter of the upper and lower areas which related to S. In the simulation of the tunnel personnel positioning system, D was set at 1.5 m and S was set at 60 m. L was set at 30 m when K was 3.0 m as well as L was set at 36 m when K was2.4 m. The relationship between L, S, and K is L = S − 10. The relationship between W and S is W = 0.05S.

Figure 8.

Division of the upper and lower edges.

Simulation and distribution of the positioning error area of the combined localization algorithm

Using the simulation parameters in Table 2, the distribution of the positioning error area was simulated using the combined localization algorithm with ranging errors of K = 2.4 and 3.0 m. The distribution of the positioning error area is shown in Figure 9, combined with Figures 3 and 4. It can be seen that the positioning errors for the four corners using the combined localization algorithm were significantly reduced, while the positioning errors for the upper and lower edges were improved. The location of the maximum positioning error from the middle of the four corners or the lower-edge area to the upper right corner of the upper-edge area also changed significantly. The positioning errors of the entire area were reduced to various degrees.

Figure 9.

Simulation map for the distribution of the positioning error area based on the combined localization algorithm: (a) K = 2.4 m and (b) K = 3.0 m.

It can be seen from Figure 9 and Table 3 that with ranging errors of K = 2.4 and 3.0 m, the average positioning errors of the combined localization algorithm were 0.6965 and 0.8347 m, respectively. This resulted in reductions of 7.28% and 3.89%, respectively, in comparison with the quadrilateral centroid localization algorithm and 43.47% and 46.04%, respectively, in comparison with the maximum likelihood estimation algorithm. The maximum positioning errors of the combined localization algorithm were 1.6312 and 1.8651 m, respectively, which resulted in 44.09% and 48.81% reductions, respectively, in comparison with the quadrilateral centroid localization algorithm, and by 40.12% and 45.49% compared with the maximum likelihood estimation algorithm. Thus, both the average and maximum positioning errors of the combined positioning algorithm were significantly reduced.

Conclusion

Applying the simulation parameters, an isosceles trapezoid simulation area with an irregular reference node layout and more than 90,000 unknown nodes was determined in a tunnel environment. The characteristics of the positioning error areal distribution were determined using the quadrilateral centroid localization and maximum likelihood estimation algorithms. The causes of the formation of large positioning errors were analyzed.

Based on the characteristics and analysis of the positioning error areal distribution of two common algorithms, a combined localization algorithm for tunnel personnel based on error area division is proposed.

The positioning area was divided into three parts: middle, upper, and lower edges, and four corners. The quadrilateral centroid localization algorithm was used for the middle area, the maximum likelihood estimation algorithm for the upper and lower edges, and the centroid algorithm for the four corners. The simulation results show that the average positioning errors of the combined localization algorithm were reduced by 5.56% and 44.76% compared with those of the quadrilateral centroid localization and maximum likelihood estimation algorithms, respectively, while the maximum positioning errors were reduced by 46.45% and 42.81%, respectively.

The results of this study can help improve the positioning accuracy of tunnel personnel positioning system and the rescue efficiency for tunnel personnel during dangerous accidents. The distribution and division of the positioning error area also provide a new reference for other indoor positioning fields.

Footnotes

Handling Editor: Peio Lopez Iturri

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Traffic Research Project of the Department of Transport of Shaanxi Province under Grant nos 17-55X, 18-33X, and 20-29K.

ORCID iD

Haiying Wang

References

Liu

Guo

, et al. A complete feasible and nodes-grouped scheduling algorithm for wireless rechargeable sensor networks in tunnels. Sensors 2018; 18: 3410.

Moridi

Kawamura

Sharifzadeh

, et al. An investigation of underground monitoring and communication system based on radio waves attenuation using ZigBee. Tunn Undergr Space Technol 2014; 43: 362–369.

Cao

QM.

Research of underground staff positioning system based on wireless sensor network. IEEE Access 2011; 11: 600–603.

De Angelis

Nilsson

Skog

, et al. Indoor positioning by ultra wide band radio aided inertial navigation. Pol Akad Nauk 2010; 3: 447–460.

Zhao

Sandoval

EB.

A UWB-based indoor positioning system employing neural networks. J Geovisualiz Spat Anal 2020; 4(2): 707–340.

Jung

Lee

KS.

A study on the indoor positioning method of a motorcar detection system based on CSS (Chirp Spread Spectrum). Autom Control Intell Syst 2015; 3(6): 133–140.

Bernard

Bouvet

Pottier

, et al. Multiuser chirp spread spectrum transmission in an underwater acoustic channel applied to an AUV fleet. Sensors 2020; 20: 1527.

Yin

DS.

Mine personnel positioning accurate method based on RSSI and TOA. Meas Control Technol 2017; 35: 13–15, 20.

Deng

Wang

Zheng

, et al. A closed-form localization algorithm and GDOP analysis for multiple TDOAs and single TOA based hybrid positioning. Appl Sci 2019; 9: 4935.

10.

Shao

Zhang

Wang

Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables. IEEE Trans Signal Process 2014; 62(10): 2580–2594.

11.

Andres

Fabian

Christian

, et al. Experimental evaluation of RSSI-based positioning system with low-cost LoRa devices. Ad Hoc Netw 2020; 105(2020): 102168.

12.

Zhang

Wang

Design of positioning system for firemen based on Zigbee and RFID. Exp Technol Manage 2017; 34(7): 122–140.

13.

Zhang

Kang

Han

, et al. A simulation study on mine power system leakage fault location. Comput Simul 2016; 33(2): 330–334.

14.

Wang

Liu

, et al. Optimizing node localization in wireless sensor networks based on received signal strength indicator. IEEE Access 2019; 7(99): 73880–73889.

15.

Wang

Liang

, et al. A quadratic weighted centroid algorithm for tunnel personnel positioning. Int J Distrib Sens Netw 2020; 16: 1–12.

16.

Huangfu

Wang

Zhao

XX.

Research on tunnel personnel positioning system and accuracy based on UWB technology. Chin Comput Commun 2019; 3: 111–113.

17.

Chen

Wang

Ouyang

, et al. Iterative positioning algorithm for indoor node based on distance correction in WSNs. Sensors 2019; 19(22): 4871.

18.

Qiu

Zhou

Xia

, et al. A localization strategy based on n-times trilateral centroid with weight. Int J Commun Syst 2012; 25(9): 1160–1177.

19.

Cheng

Sun

YJ.

Accurate positioning of intelligent agriculture wireless sensor based on improved quadrilateral ranging algorithm. Jiangsu Agri Sci 2017; 45(17): 234–237.

20.

Wang

Tong

Bai

, et al. ZigBee dynamic weighted centroid four points location algorithm based on RSSI. Appl Res Comput 2018; 35(9): 109–111.

21.

Zeng

, et al. Advanced combination localization algorithm based on trilateration for dynamic cluster network. IEEE Access 2019; 7: 180965–180975.

22.

Gao

Yang

XM.

An improved trilateration positioning algorithm. Ind Mine Autom 2020; 46(2): 79–81.

23.

Zhou

Yang

JT.

An improved indoor trilateral localization algorithm based on Eddystone-TLM centroid. Modern Electron Tech 2020; 43(2): 179–181.

24.

Geng

Wang

Zhu

, et al. Accuracy improvement of positioning data in greenhouse for agricultural machinery via optimisation algorithm. J Eng 2019(15): 547–551.

25.

Zhong

Jin

JJ.

Analysis and implementation of maximum likelihood estimation positioning algorithm based on RSSI. J Jilin Univ Sci Ed 2014; 52: 560.

26.

Zhao

Song

Zhao

, et al. Maximum likelihood algorithm for single-observer passive coherent location using TDOA measurements. J Data Acquist Process 2017; 32(5): 898–905.

27.

Zhan

Zhao

Improvement and implementation of localization algorithm based on RSSI maximum likelihood estimation. J Henan Norm Univ Nat Sci Ed 2018; 46(5): 37–41.

28.

Kim

Shin

A distance boundary with virtual nodes for the weighted centroid localization algorithm. Sensors 2018; 18: E1054.

29.

Rahman

Park

Kim

KD.

RSS-based indoor localization algorithm for wireless sensor network using generalized regression neural network. Arab J Sci Eng 2012; 37(4): 1043–1053.

30.

Zhao

, et al. An improved weighted centroid localization algorithm based on difference of estimated distances for wireless sensor networks. Telecommun Syst 2013; 53(1): 25–31.

31.

Gong

HY.

An improvement to advanced centroid location algorithm. Adv Eng Forum 2012; 6–7: 615–620.

32.

Wang

Huang

LG.

Improved centroid localization algorithm in application of underground personnel positioning. Coal Mine Mach 2012; 33(8): 76–78.

33.

Zhou

Zhu

Luo

, et al. Direct positioning maximum likelihood estimator using TDOA and FDOA for coherent short-pulse radar. IET Radar Sonar Navig 2017; 11(10): 1505–1511.

34.

Bar-Shalom

Weiss

AJ.

Direct positioning of stationary targets using MIMO radar. Signal Process 2011; 91: 2345–2358.

35.

Xia

Liu

, et al. Probability-based indoor positioning algorithm using iBeacons. Sensors 2019; 19(23): 5226.

36.

Wang

SP.

Research on key technology of tunnel personnel positioning system based on CSS. Xi’an, China: Chang’an University, 2018.

37.

Zhai

Tang

Wang

, et al. Enhancing received signal strength-based localization through coverage hole detection and recovery. Sensors 2018; 18(7): 2075.

38.

Rivara

Diaz

Terminal triangles centroid algorithms for quality delaunay triangulation. Comput Aid Design 2020; 125: 102870.