# A Practical and Economical Ultra-wideband Base Station Placement Approach for Indoor Autonomous Driving Systems

Authors: Shengchuan Jiang; Cong Zhao; Yifan Zhu; Chenwei Wang; Yuchuan Du
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Automated valet parking (AVP) has attracted much attention as the entry point to autonomous driving. In an indoor environment, high-precision positioning systems are essential for AVP. Ultra-wideband (UWB) is one of the most widely adopted techniques. However, the base station placement significantly influences the system’s positioning accuracy, especially for the irregular architecture of underground parking lots. This article proposes a three-stage practical and economical layout planning approach for UWB base stations, including determining the deployment strategy and layout parameters and comprehensive adjustment and scheme verification. The approach considers regional differentiation accuracy requirements for AVP, such as ramp area, surface fluctuation area, and narrow area. The adopted positioning method of a UWB system is the time difference of arrival (TDOA), and the evaluation index of positioning accuracy is the horizontal dilution of precision (HDOP). Through experimental tests in an actual parking lot, the proposed approach is confirmed to ensure stability and economy with fewer UWB base stations and can meet the positioning accuracy requirements of AVP.


---

## Body

## 1. Introduction

With the rapid development of the Internet of Things (IoT) [1], advanced sensors [2], and connected and automated vehicles [3], the demand for high-accuracy location-based services has exploded. Among these, smart indoor parking lots (mostly indoor) are typical integrated applications of the IoT, sensors, and location services, improving the use of parking resources and user satisfaction, especially with the advent of automated valet parking (AVP) [4]. AVP allows human drivers to leave their vehicles in a drop-off zone (e.g., the elevator entrance of a parking lot), and vehicles execute the parking tasks independently [5]. During AVP, vehicles must obtain their location for path planning, decision-making, and control. The quality of task execution strongly depends on positioning accuracy. However, for an indoor parking lot, infrastructure-enabled high-precision positioning is one of the most economical and reliable schemes in existing AVP technologies [6].Many indoor positioning systems are suitable for smart parking lots, such as Wi-Fi [7], lidar [6], LED light communication [8], and ultra-wideband (UWB) [9]. Among these, UWB has been considered one of the key technologies of next-generation wireless communication because of its low power, anti-interference, strong penetration ability, and high positioning accuracy [9]. However, a UWB positioning system also depends on the beacon positioning method, which must use the known location information of several UWB base stations in the positioning area to determine the mobile station’s location. The layout of UWB base stations strongly impacts the positioning accuracy and stability and affects the overall construction cost. Existing studies have confirmed that the layout of base stations influences positioning accuracy more than the measurement noise and fast fading effect [10, 11]. Therefore, optimizing the base station layout for different physical environments and accuracy requirements are highly significant to realizing the extensive application of UWB positioning systems.In an existing study on base station layout planning, Monica and Ferrari [12] proposed an optimization method for a UWB base station layout for large indoor scenarios, which deduced the optimal layout spacing concerning corridor width and base station height and verified that its mean squared error (MSE) could reach the Cramer–Rao lower bound (CRLB) through simulation. Long et al. [13] proposed a new base station layout design method to minimize the MSE in circular, square, and hexagonal location areas. Qiao et al. [14] proposed a maximum distance measurement variation criterion-based method to optimize the layout of base stations when adding new base stations to the network. Redondi and Amaldi [15] studied an indoor positioning system’s base station layout optimization problem based on wireless sensor signal strength, formulated as mixed integer nonlinear programming to minimize CRLB. A tabu search algorithm was applied to solve the problem. Zhou et al. [16] proposed four CRLB-based metrics to achieve the optimal base station layout and evaluation for indoor rectangular industrial positioning facilities. Sharma and Badarla [17] proposed a scheme to place the positioning base stations on the wall and ceiling, greatly reducing the occlusion during signal propagation and minimizing the positioning error caused by the geometric shape. Meanwhile, they proposed a multiobjective optimization approach to analyze the beacon layout problem (BLP) for the 3D coordinate point cloud representation of indoor environments. The BLP was solved using a nondominating sorting genetic algorithm (NSGA)-II [18]. Kim and Choi [19] introduced a local optimal layout planning method for UWB base stations, formulated as binary integer linear programming with heuristics-based constraints. The experimental results showed that the method could guarantee high-precision and reliable positioning performance for navigating autonomous systems. Wu et al. [20] regarded multiple UWB base stations as a cluster and applied dynamic particle swarm optimization and a genetic algorithm to optimize the layout of base station clusters. Pan et al. [21] proposed a UWB base station layout design method based on a genetic heuristic differential evolution algorithm, which could reduce the average localization error by 28.2% and 12.5% compared to the random and default schemes.However, some studies aim at reducing the number of base stations. Santoro et al. [22] provided a detailed analysis of the uncertainty of the positioning system while the UWB infrastructure grows, and developed a genetic algorithm that minimizes the deployment of new base stations. Wang et al. [23] aimed at achieving full coverage of indoor scenarios with the least number of base stations deployed. The solution reduced the number of required base stations by 6% to 23% based on a greedy and random sampling algorithm. Balac et al. [24] studied the positioning problem based on fault-tolerant triangulation and proposed several algorithms to optimize the number of base stations. However, the optimization results reduced the number of anchor nodes by less than 0.5%. Leune et al. [25] placed base stations by combining genetic optimization with radio impulse propagation simulation and equipped fewer base stations to provide lower root mean square deviation positioning results in complex environments. In [26], genetic algorithm was applied to determine the location of sensors in intelligent buildings combined with the design drawings of buildings, which effectively reduces the number of sensors. A new three-base station UWB positioning algorithm based on TOF was proposed in [27], which can get rid of the strict placement restrictions of the three base stations without sacrificing the positioning speed excessively.Although much progress has been made in base station layout planning of indoor positioning systems, room remains for improvement. Most studies do not consider economic issues in base station layout planning. Meanwhile, when confronted with a real situation, especially for the actual complex environment, some algorithms converge slowly, and many restrictions exist. Moreover, most studies have not considered the spatial features of different positioning areas in the indoor parking lot, the different error sources, and differences in accuracy requirements, which bring additional challenges. This article proposes and verifies an AVP application-oriented optimal and economical layout planning method for UWB base stations. The contributions of this article can be summarized as follows:(i)
We analyze several different standard polygon coverage schemes of UWB base stations and propose the most economical coverage scheme(ii)
We develop a three-stage UWB base station placement planning approach, which is applicable to all kinds of indoor parking lots with high practicability and economy(iii)
We design the layout of UWB base stations and conduct experiments in a real underground parking lot to verify the effectiveness of the three-stage methodThe organization of this article is as follows: firstly, a two-dimensional UWB positioning system based on TDOA is chosen as the research object. The plane geometric accuracy factor HDOP is selected as the evaluation index of positioning accuracy. Based on this, the accuracy measurement experiments of the UWB positioning system are designed and performed. The different base station layout styles are studied via theoretical analysis and MATLAB simulation. The base station layout in various real scenarios is then simulated, and a method of adjustment and optimization is proposed. Meanwhile, various practical scenario layout methods are integrated to form a practical application-oriented one. Finally, the method is discussed and summarized based on the test results.


## 2. Assumptions and Accuracy Criteria

We use the following assumptions throughout the article to simplify the model while keeping it realistic.


### 2.1. Environmental Conditions

The actual environmental scenarios considered in this article include areas where base stations cannot be evenly laid out, ramp areas, undulating surface areas, narrow and long areas, and subareas with different accuracy requirements.


### 2.2. Simplification of UWB Positioning System

In this article, we mainly study the impact of UWB base station layout on positioning accuracy. Therefore, the influence of clock synchronization error between base stations under the TDOA algorithm is not considered. Simultaneously, this article does not consider the aging or damage of UWB base stations over time. In AVP scenarios, the vehicle height is not critical because the vehicle must be moving close to the ground. Therefore, the positioning in AVP scenarios can be simplified to two-dimensional plane positioning.


### 2.3. Accuracy Evaluation Criteria

It is necessary to define and summarize the evaluation indexes of positioning accuracy to evaluate the performance of a positioning system correctly and effectively under different base station layouts.The geometric dilution of precision (GDOP) is one of the most important indexes to measure the positioning accuracy of a UWB indoor positioning system. This is defined as the ratio between the system positioning error and ranging error, which indicates the geometric spatial layout between a mobile station (MS) and base station (BS) and the magnification of ranging error by the degree of clock synchronization between devices. The GDOP can be calculated as follows:(1)GDOP=σx2+σy2+σz2+σc⋅δt2σ,where σx2, σy2, and σz2 represent the error variances in the x, y, and z directions, respectively; σc⋅δt2 represents the error variance due to clock synchronization error; and σ represents the standard deviation of the ranging error. Based on the above assumptions, the horizontal dilution of precision (HDOP) of a two-dimensional plane can be obtained as follows:(2)HDOP=σx2+σy2σ.In this article, the HDOP is applied as the accuracy evaluation index to analyze the two-dimensional positioning accuracy of the UWB positioning system under different BS layouts. Assuming the same ranging error, the smaller the HDOP, the higher the plane positioning accuracy obtained.


### 2.4. Accuracy Verification

We apply the positioning values of the total station coordinate measurement as true values and use the 1,000 times UWB positioning values as measured values. The Euclidean distances of the measured and true values in thex and y directions are then calculated. The total Euclidean distance and its variance for the measured and true values are also obtained. Finally, we take the four values as the judging index of the positioning performance.


## 2.1. Environmental Conditions

The actual environmental scenarios considered in this article include areas where base stations cannot be evenly laid out, ramp areas, undulating surface areas, narrow and long areas, and subareas with different accuracy requirements.


## 2.2. Simplification of UWB Positioning System

In this article, we mainly study the impact of UWB base station layout on positioning accuracy. Therefore, the influence of clock synchronization error between base stations under the TDOA algorithm is not considered. Simultaneously, this article does not consider the aging or damage of UWB base stations over time. In AVP scenarios, the vehicle height is not critical because the vehicle must be moving close to the ground. Therefore, the positioning in AVP scenarios can be simplified to two-dimensional plane positioning.


## 2.3. Accuracy Evaluation Criteria

It is necessary to define and summarize the evaluation indexes of positioning accuracy to evaluate the performance of a positioning system correctly and effectively under different base station layouts.The geometric dilution of precision (GDOP) is one of the most important indexes to measure the positioning accuracy of a UWB indoor positioning system. This is defined as the ratio between the system positioning error and ranging error, which indicates the geometric spatial layout between a mobile station (MS) and base station (BS) and the magnification of ranging error by the degree of clock synchronization between devices. The GDOP can be calculated as follows:(1)GDOP=σx2+σy2+σz2+σc⋅δt2σ,where σx2, σy2, and σz2 represent the error variances in the x, y, and z directions, respectively; σc⋅δt2 represents the error variance due to clock synchronization error; and σ represents the standard deviation of the ranging error. Based on the above assumptions, the horizontal dilution of precision (HDOP) of a two-dimensional plane can be obtained as follows:(2)HDOP=σx2+σy2σ.In this article, the HDOP is applied as the accuracy evaluation index to analyze the two-dimensional positioning accuracy of the UWB positioning system under different BS layouts. Assuming the same ranging error, the smaller the HDOP, the higher the plane positioning accuracy obtained.


## 2.4. Accuracy Verification

We apply the positioning values of the total station coordinate measurement as true values and use the 1,000 times UWB positioning values as measured values. The Euclidean distances of the measured and true values in thex and y directions are then calculated. The total Euclidean distance and its variance for the measured and true values are also obtained. Finally, we take the four values as the judging index of the positioning performance.


## 3. Methodology

### 3.1. Geometry and Coverage Scheme of UWB BS Layout

The number of BSs directly impacts the positioning accuracy. Therefore, we explore the numerical relationship between the number of BSs and the positioning accuracy.


#### 3.1.1. The Relationship between the Number of BSs and the Theoretical Minimum Value of the HDOP

According to the definition of the HDOP [28], the HDOP of UWB positioning based on the TDOA principle meets(3)HDOP≥1∑i=1naxi2+1∑i=1nayi2,where n is the number of BSs participating in the UWB positioning system; and ayi are the cosine and sine of the angle between the connection of the i-th BS and the positioning UWB label and horizontal direction. Let axi=cosαi and ayi=sinαi. (3) can be written as(4)HDOP≥n∑i=1ncos2αi×∑i=1nsin2αi=nfn.Equation (5) can be proved by mathematical induction:(5)fn=n24−14∑i=1ncos2αi2.First, whenn=2,(6)f2=1−14cos2α1+cos2α2.Whenn=NN≥3 and (5) is satisfied for n=N−1,(7)fN=∑i=1Ncos2αi×∑i=1Nsin2αi=fN−1+sin2αN∑i=1N−1cos2αi+cos2αN∑i=1N−1sin2αi+cos2αN⋅sin2αN,=N−124−14∑i=1N−1cos2αi2−12∑i=1N−11−cos2αicos2αN+141−cos22αN,=N24−14∑i=1Ncos2αi2.According to the above, (5) is proved. According to (4), the theoretical lower bound of the HDOP can be calculated as follows:(8)HDOP≥4n.The theoretical lower bound of the HDOP decreases as the number of BSs involved in the system increases. However, when the number of BSs exceeds five, the decrease slows significantly.


#### 3.1.2. Simulation and Analysis of the Impact of the Number of BSs on the HDOP

Considering the installation convenience, UWB BSs are generally arranged in triangles or quadrangles. By simulating the HDOP of each point in the positioning area in MATLAB, the contour map of the location accuracy characteristics in the area when a different number of BSs participate in the calculation is obtained, as shown in Figure1. Based on the simulation results, in ensuring the accuracy and stability of positioning, four to five times the coverage ensures sufficient positioning accuracy and high economy.Figure 1
HDOP distribution map of positioning area for different numbers of BSs in a uniform layout; (a) triangle three times coverage; (b) triangle four times coverage; (c) square three times coverage; (d) square four times coverage; (e) square five times coverage.
(a)(b)(c)(d)(e)


#### 3.1.3. BS Coverage Scheme considering Economy

Based on the construction cost, the premise is to ensure that any point in the location area meetsK times the coverage, and K has been proved to be 4–5 as discussed above. The fewer the BSs used to cover the same area, the more economical is the layout scheme.The BS layout of the UWB positioning system relates to the problem of area coverage, which can be divided into regular triangle and quadrilateral structures. As stated in [29], a square structure has a higher efficiency of four times the coverage layout, and a triangle structure has a higher efficiency of three times the coverage layout. If the effective coverage radius of the UWB tag’s pulse signal is 30 m, the number of BSs needed to achieve three times the coverage of the triangle structure, four times the coverage of the square structure, and five times the coverage of the square structure in different areas is shown in Figure 2. Four times the coverage of the square structure is the best coverage and the best economical solution. Minimal difference exists between the number of BSs required to achieve three and four times the coverage in the same area. Conversely, the number of BSs required to achieve five times the coverage is almost twice the number of BSs required to achieve four times the coverage. However, as mentioned earlier, the positioning accuracy achieved by five and four times the coverage is almost the same. Therefore, the UWB BS layouts for the actual environment are all optimized based on four times the coverage of the square structure.Figure 2
Number of BSs required for different coverages in the same area.


#### 3.1.4. Layout Scheme Adjustment

In practice, the scenario space is often irregular. Thus, it is impossible to realize the uniform layout of BSs. The BSs mostly adopt a rectangular or diamond layout to ensure the coverage of four signals. The HDOP of the positioning area with different side-length ratios is simulated using MATLAB; the results are shown in Table1.Table 1
Distribution characteristics of the HDOP in rectangular and diamond layouts with different axial ratios.
LayoutAxial ratioMinimum HDOPMaximum HDOPAverage HDOP80% grading value HDOP90% grading value HDOPRectangular1.01.2851.8161.4551.4261.5821.41.2891.8601.4851.4511.5841.81.2931.9761.5511.5371.6882.21.2962.1251.6361.6011.7922.61.2962.2991.7351.7291.9463.01.2972.4921.8441.8442.136Diamond1.01.2851.6511.4101.5101.5471.41.2851.7611.4501.5771.6401.81.2851.9811.4941.6471.7252.21.2852.2441.5491.7231.8712.61.2852.5551.6171.8392.0583.01.2852.8781.6801.9602.226We draw the following conclusions according to the above results. Based on the positioning accuracy requirements in [30], 90% of the positioning error standard deviation should be within 10 cm. We deduce that the 90% grading value of the HDOP must be less than 2.0, and the ratio of the long side to the short side should not exceed 2.6 for the rectangular layout. For the diamond layout, the ratio of the long axis to the short axis should not exceed 2.6.


#### 3.1.5. UWB BS Layout in Ramp Area

When the tag to be measured moves on the ramp area, its height is constantly changing. The BS horizontal spacing must then be adjusted according to the ramp gradient. That is, the effective coverage radius of the BS must be adjusted during the calculation.Assuming thatθ is the angle between the slope and the horizontal plane, the slope direction is that in which the elevation on the slope decreases fastest. The slope area studied in this article is the ideal slope. That is, the slope and aspect of each point on the slope are the same. When the orientation of interest is consistent with the gradient direction, the effective radius r′ is(9)r′=rcosθ.


#### 3.1.6. UWB BS Layout in Surface Fluctuation Area

In the actual positioning scenario, the height of the tag to be tested will inevitably change. After deduction, the positioning error caused by the change in tag height is as follows:(10)Gh=1sinα·Δn12+Δn22−2cosαΔn1⋅Δn2,(11)Δrio=ri2+h2−ri−ro2+h2−ro,i=1,2,(12)∇ri0=∂ri0∂x∂ri0∂y,ui=ΔxΔy,where Δni denotes the projection of ui on ∇ri0; x,y denotes the measured coordinate value; ∇ri0 denotes the gradient vector of ri0 at the point to be measured; ri0 denotes the distance difference between BSs; and α denotes the angle between Δn1 and Δn2. Taking the tag height estimation error h as a variable, the positioning error Gh caused by h is simulated and analyzed. The results are shown in Figure 3.Figure 3
Graph ofGh change with tag height.Ash increases, the average positioning error caused by the error in tag height estimation gradually increases, and the maximum error will increase rapidly. When the surface fluctuation is less than 0.3 m, the influence will be less for the BS layout covered by four times the square structural signals (Max Gh<10cm). Therefore, the influence of the elevation difference can be neglected when it is less than 0.3 m. However, when the elevation difference exceeds 0.3 m, the different elevation areas should be divided into subareas.


#### 3.1.7. UWB BS Layout in Narrow Area

For narrow areas, such as lanes and roadways, the length of one direction is much smaller than that of the other. This can be formulated as(13)HDOPx,y=G11+G22,where G11 and G22 denote the direction cosines of the tags in the x and y directions, namely, the precision factors of the x and y directions, respectively. Considering the difference in location accuracy between two directions in the narrow region, we evaluate the location accuracy of the BS layout in the narrow region using the direction-weighted plane accuracy factor, that is, through pairing and giving different weights in different directions. Meanwhile, the error variance of the positioning accuracy in two directions is applied to determine the corresponding weight coefficients:(14)wx=1−σxσx+σy,(15)wy=1−σyσx+σy,(16)HDOPwx,y=wx⋅G11+wy⋅G22.Assuming that the width of a narrow area is 3 m and the length is 30 m, 90% of the area to be measured should satisfy the positioning error variance along the width direction (x direction) and the length direction (y direction) when the tag moves in the narrow area. The surface of the narrow area is planar, and the plane coverage radius of the BS is 50 m. The genetic algorithm toolbox of MATLAB is applied to solve the optimization problem of weighted geometric factors. The simulation results are shown in Figure 4.Figure 4
Directional factor changes with rectangular length.The distance between adjacent BSs in they direction should not exceed 10.5 m to ensure that 90% of the positioning area meets the direction accuracy requirement. The rectangular aspect ratio can then reach 10.5/3 = 3.5 m, exceeding the previous requirement of 2.6 m. When the absolute size of the σx and σy changes, or the width of the narrow area changes, the distance will also change.


#### 3.1.8. UWB BS Layout considering the Difference in Regional Precision Requirements for AVP

Under actual working conditions, different location areas may have different location accuracy requirements for AVP. The weighted region HDOP model is then formulated to obtain an economical and efficient UWB BS layout scheme. The theoretical optimization model is transformed into a multiobjective optimization solution model using the weight of the judgment matrix. Furthermore, the model considers the different positioning accuracy requirements for different areas. The scale of 1–9 is introduced, whereaij denotes the importance of area si relative to area sj, and the corresponding meanings of different values are shown in Table 2.Table 2
Corresponding meanings of different relative importance values.
aij13579Meaning of aijSi equals SjSi slightly more important than SjSi evidently more important than SjSi extraordinarily more important than SjSi superficially more important than SjAfter obtaining the weight coefficients, based on the linear weighting method, the optimization problem of the BS layout considering the difference in location accuracy requirements is transformed into the optimal solution of equation (17). The solution is then the optimal layout of the UWB BSs:(17)min∑i=1mwi⋅HDOPix,y,xy∈D,HDOPix,y≤σiσΔr,where HDOPix,y denotes the HDOP in positioning area i; σi denotes the standard deviation of the maximum positioning error required by the area; and σΔr denotes the standard deviation of the difference error.Using MATLAB to simulate this method, take the positioning area shown in Figure5(a) as an example, in which the standard deviation of the positioning error required by Area 1 is σ1≤10cm; Area 2: σ2≤15cm; Area 3: σ3≤20cm; and Area 4: σ4≤30cm. According to the judgment matrix, the weights of each region are obtained as follows:(18)w1=25;w2=415;w3=15;w4=215.Figure 5
Base station layout considering different positioning accuracy requirements.
(a)(b)The most suitable layout scheme is obtained by a MATLAB genetic algorithm simulation, as shown in Figure5(b).If the standard deviation of the time difference error measurement,σΔr, is 5 cm, the layout of the BS is checked by inverse calculation. The HDOP of the positioning error of each location area is shown in Table 3 and meets the location accuracy requirement. Therefore, the layout scheme is feasible.Table 3
Simulation results of plane accuracy factors for each localization area.
Location areaHDOPAverageMaximum90% indexing valueRequired valueArea 11.41.821.422Area 21.562.361.693Area 31.331.551.364Area 41.541.781.586


#### 3.1.9. Three-Stage UWB Station Layout Planning Method

According to the previous analysis, the layout design methods for various practical scenarios are integrated, and a practical application-oriented regional UWB station layout optimization design method is proposed. The method comprises three stages:Step 1: determine the deployment strategy. The environmental characteristics of each subregion in the region to be located are extracted, and the BS layout strategy of each subregion is determined according to the characteristic environmental parameters.Step 2: determine the layout parameters. Based on the positioning accuracy requirement of each subregion, the layout strategy, and equipment performance parameters, the specific layout spacing, layout number, and other parameters are obtained by the corresponding methods.Step 3: comprehensive adjustment and scheme verification. The layout scheme of each subregion is integrated, and the adjusted scheme is validated by simulating the HDOP. If the location accuracy requirement is satisfied, the scheme of parameters, symbols, and graphics can be further generated. Otherwise, the layout strategy must be determined again until the scheme is validated.In the whole design process of the BS layout scheme, the main parameters involved include (1) characteristic environmental parameters, such as slope, undulating area of surface, and narrow area; (2) positioning accuracy parameters, including the size and direction of positioning errors required by each region; and (3) equipment performance parameters, including the BS signal coverage distance and antenna type.


## 3.1. Geometry and Coverage Scheme of UWB BS Layout

The number of BSs directly impacts the positioning accuracy. Therefore, we explore the numerical relationship between the number of BSs and the positioning accuracy.


### 3.1.1. The Relationship between the Number of BSs and the Theoretical Minimum Value of the HDOP

According to the definition of the HDOP [28], the HDOP of UWB positioning based on the TDOA principle meets(3)HDOP≥1∑i=1naxi2+1∑i=1nayi2,where n is the number of BSs participating in the UWB positioning system; and ayi are the cosine and sine of the angle between the connection of the i-th BS and the positioning UWB label and horizontal direction. Let axi=cosαi and ayi=sinαi. (3) can be written as(4)HDOP≥n∑i=1ncos2αi×∑i=1nsin2αi=nfn.Equation (5) can be proved by mathematical induction:(5)fn=n24−14∑i=1ncos2αi2.First, whenn=2,(6)f2=1−14cos2α1+cos2α2.Whenn=NN≥3 and (5) is satisfied for n=N−1,(7)fN=∑i=1Ncos2αi×∑i=1Nsin2αi=fN−1+sin2αN∑i=1N−1cos2αi+cos2αN∑i=1N−1sin2αi+cos2αN⋅sin2αN,=N−124−14∑i=1N−1cos2αi2−12∑i=1N−11−cos2αicos2αN+141−cos22αN,=N24−14∑i=1Ncos2αi2.According to the above, (5) is proved. According to (4), the theoretical lower bound of the HDOP can be calculated as follows:(8)HDOP≥4n.The theoretical lower bound of the HDOP decreases as the number of BSs involved in the system increases. However, when the number of BSs exceeds five, the decrease slows significantly.


### 3.1.2. Simulation and Analysis of the Impact of the Number of BSs on the HDOP

Considering the installation convenience, UWB BSs are generally arranged in triangles or quadrangles. By simulating the HDOP of each point in the positioning area in MATLAB, the contour map of the location accuracy characteristics in the area when a different number of BSs participate in the calculation is obtained, as shown in Figure1. Based on the simulation results, in ensuring the accuracy and stability of positioning, four to five times the coverage ensures sufficient positioning accuracy and high economy.Figure 1
HDOP distribution map of positioning area for different numbers of BSs in a uniform layout; (a) triangle three times coverage; (b) triangle four times coverage; (c) square three times coverage; (d) square four times coverage; (e) square five times coverage.
(a)(b)(c)(d)(e)


### 3.1.3. BS Coverage Scheme considering Economy

Based on the construction cost, the premise is to ensure that any point in the location area meetsK times the coverage, and K has been proved to be 4–5 as discussed above. The fewer the BSs used to cover the same area, the more economical is the layout scheme.The BS layout of the UWB positioning system relates to the problem of area coverage, which can be divided into regular triangle and quadrilateral structures. As stated in [29], a square structure has a higher efficiency of four times the coverage layout, and a triangle structure has a higher efficiency of three times the coverage layout. If the effective coverage radius of the UWB tag’s pulse signal is 30 m, the number of BSs needed to achieve three times the coverage of the triangle structure, four times the coverage of the square structure, and five times the coverage of the square structure in different areas is shown in Figure 2. Four times the coverage of the square structure is the best coverage and the best economical solution. Minimal difference exists between the number of BSs required to achieve three and four times the coverage in the same area. Conversely, the number of BSs required to achieve five times the coverage is almost twice the number of BSs required to achieve four times the coverage. However, as mentioned earlier, the positioning accuracy achieved by five and four times the coverage is almost the same. Therefore, the UWB BS layouts for the actual environment are all optimized based on four times the coverage of the square structure.Figure 2
Number of BSs required for different coverages in the same area.


### 3.1.4. Layout Scheme Adjustment

In practice, the scenario space is often irregular. Thus, it is impossible to realize the uniform layout of BSs. The BSs mostly adopt a rectangular or diamond layout to ensure the coverage of four signals. The HDOP of the positioning area with different side-length ratios is simulated using MATLAB; the results are shown in Table1.Table 1
Distribution characteristics of the HDOP in rectangular and diamond layouts with different axial ratios.
LayoutAxial ratioMinimum HDOPMaximum HDOPAverage HDOP80% grading value HDOP90% grading value HDOPRectangular1.01.2851.8161.4551.4261.5821.41.2891.8601.4851.4511.5841.81.2931.9761.5511.5371.6882.21.2962.1251.6361.6011.7922.61.2962.2991.7351.7291.9463.01.2972.4921.8441.8442.136Diamond1.01.2851.6511.4101.5101.5471.41.2851.7611.4501.5771.6401.81.2851.9811.4941.6471.7252.21.2852.2441.5491.7231.8712.61.2852.5551.6171.8392.0583.01.2852.8781.6801.9602.226We draw the following conclusions according to the above results. Based on the positioning accuracy requirements in [30], 90% of the positioning error standard deviation should be within 10 cm. We deduce that the 90% grading value of the HDOP must be less than 2.0, and the ratio of the long side to the short side should not exceed 2.6 for the rectangular layout. For the diamond layout, the ratio of the long axis to the short axis should not exceed 2.6.


### 3.1.5. UWB BS Layout in Ramp Area

When the tag to be measured moves on the ramp area, its height is constantly changing. The BS horizontal spacing must then be adjusted according to the ramp gradient. That is, the effective coverage radius of the BS must be adjusted during the calculation.Assuming thatθ is the angle between the slope and the horizontal plane, the slope direction is that in which the elevation on the slope decreases fastest. The slope area studied in this article is the ideal slope. That is, the slope and aspect of each point on the slope are the same. When the orientation of interest is consistent with the gradient direction, the effective radius r′ is(9)r′=rcosθ.


### 3.1.6. UWB BS Layout in Surface Fluctuation Area

In the actual positioning scenario, the height of the tag to be tested will inevitably change. After deduction, the positioning error caused by the change in tag height is as follows:(10)Gh=1sinα·Δn12+Δn22−2cosαΔn1⋅Δn2,(11)Δrio=ri2+h2−ri−ro2+h2−ro,i=1,2,(12)∇ri0=∂ri0∂x∂ri0∂y,ui=ΔxΔy,where Δni denotes the projection of ui on ∇ri0; x,y denotes the measured coordinate value; ∇ri0 denotes the gradient vector of ri0 at the point to be measured; ri0 denotes the distance difference between BSs; and α denotes the angle between Δn1 and Δn2. Taking the tag height estimation error h as a variable, the positioning error Gh caused by h is simulated and analyzed. The results are shown in Figure 3.Figure 3
Graph ofGh change with tag height.Ash increases, the average positioning error caused by the error in tag height estimation gradually increases, and the maximum error will increase rapidly. When the surface fluctuation is less than 0.3 m, the influence will be less for the BS layout covered by four times the square structural signals (Max Gh<10cm). Therefore, the influence of the elevation difference can be neglected when it is less than 0.3 m. However, when the elevation difference exceeds 0.3 m, the different elevation areas should be divided into subareas.


### 3.1.7. UWB BS Layout in Narrow Area

For narrow areas, such as lanes and roadways, the length of one direction is much smaller than that of the other. This can be formulated as(13)HDOPx,y=G11+G22,where G11 and G22 denote the direction cosines of the tags in the x and y directions, namely, the precision factors of the x and y directions, respectively. Considering the difference in location accuracy between two directions in the narrow region, we evaluate the location accuracy of the BS layout in the narrow region using the direction-weighted plane accuracy factor, that is, through pairing and giving different weights in different directions. Meanwhile, the error variance of the positioning accuracy in two directions is applied to determine the corresponding weight coefficients:(14)wx=1−σxσx+σy,(15)wy=1−σyσx+σy,(16)HDOPwx,y=wx⋅G11+wy⋅G22.Assuming that the width of a narrow area is 3 m and the length is 30 m, 90% of the area to be measured should satisfy the positioning error variance along the width direction (x direction) and the length direction (y direction) when the tag moves in the narrow area. The surface of the narrow area is planar, and the plane coverage radius of the BS is 50 m. The genetic algorithm toolbox of MATLAB is applied to solve the optimization problem of weighted geometric factors. The simulation results are shown in Figure 4.Figure 4
Directional factor changes with rectangular length.The distance between adjacent BSs in they direction should not exceed 10.5 m to ensure that 90% of the positioning area meets the direction accuracy requirement. The rectangular aspect ratio can then reach 10.5/3 = 3.5 m, exceeding the previous requirement of 2.6 m. When the absolute size of the σx and σy changes, or the width of the narrow area changes, the distance will also change.


### 3.1.8. UWB BS Layout considering the Difference in Regional Precision Requirements for AVP

Under actual working conditions, different location areas may have different location accuracy requirements for AVP. The weighted region HDOP model is then formulated to obtain an economical and efficient UWB BS layout scheme. The theoretical optimization model is transformed into a multiobjective optimization solution model using the weight of the judgment matrix. Furthermore, the model considers the different positioning accuracy requirements for different areas. The scale of 1–9 is introduced, whereaij denotes the importance of area si relative to area sj, and the corresponding meanings of different values are shown in Table 2.Table 2
Corresponding meanings of different relative importance values.
aij13579Meaning of aijSi equals SjSi slightly more important than SjSi evidently more important than SjSi extraordinarily more important than SjSi superficially more important than SjAfter obtaining the weight coefficients, based on the linear weighting method, the optimization problem of the BS layout considering the difference in location accuracy requirements is transformed into the optimal solution of equation (17). The solution is then the optimal layout of the UWB BSs:(17)min∑i=1mwi⋅HDOPix,y,xy∈D,HDOPix,y≤σiσΔr,where HDOPix,y denotes the HDOP in positioning area i; σi denotes the standard deviation of the maximum positioning error required by the area; and σΔr denotes the standard deviation of the difference error.Using MATLAB to simulate this method, take the positioning area shown in Figure5(a) as an example, in which the standard deviation of the positioning error required by Area 1 is σ1≤10cm; Area 2: σ2≤15cm; Area 3: σ3≤20cm; and Area 4: σ4≤30cm. According to the judgment matrix, the weights of each region are obtained as follows:(18)w1=25;w2=415;w3=15;w4=215.Figure 5
Base station layout considering different positioning accuracy requirements.
(a)(b)The most suitable layout scheme is obtained by a MATLAB genetic algorithm simulation, as shown in Figure5(b).If the standard deviation of the time difference error measurement,σΔr, is 5 cm, the layout of the BS is checked by inverse calculation. The HDOP of the positioning error of each location area is shown in Table 3 and meets the location accuracy requirement. Therefore, the layout scheme is feasible.Table 3
Simulation results of plane accuracy factors for each localization area.
Location areaHDOPAverageMaximum90% indexing valueRequired valueArea 11.41.821.422Area 21.562.361.693Area 31.331.551.364Area 41.541.781.586


### 3.1.9. Three-Stage UWB Station Layout Planning Method

According to the previous analysis, the layout design methods for various practical scenarios are integrated, and a practical application-oriented regional UWB station layout optimization design method is proposed. The method comprises three stages:Step 1: determine the deployment strategy. The environmental characteristics of each subregion in the region to be located are extracted, and the BS layout strategy of each subregion is determined according to the characteristic environmental parameters.Step 2: determine the layout parameters. Based on the positioning accuracy requirement of each subregion, the layout strategy, and equipment performance parameters, the specific layout spacing, layout number, and other parameters are obtained by the corresponding methods.Step 3: comprehensive adjustment and scheme verification. The layout scheme of each subregion is integrated, and the adjusted scheme is validated by simulating the HDOP. If the location accuracy requirement is satisfied, the scheme of parameters, symbols, and graphics can be further generated. Otherwise, the layout strategy must be determined again until the scheme is validated.In the whole design process of the BS layout scheme, the main parameters involved include (1) characteristic environmental parameters, such as slope, undulating area of surface, and narrow area; (2) positioning accuracy parameters, including the size and direction of positioning errors required by each region; and (3) equipment performance parameters, including the BS signal coverage distance and antenna type.


## 3.1.1. The Relationship between the Number of BSs and the Theoretical Minimum Value of the HDOP

According to the definition of the HDOP [28], the HDOP of UWB positioning based on the TDOA principle meets(3)HDOP≥1∑i=1naxi2+1∑i=1nayi2,where n is the number of BSs participating in the UWB positioning system; and ayi are the cosine and sine of the angle between the connection of the i-th BS and the positioning UWB label and horizontal direction. Let axi=cosαi and ayi=sinαi. (3) can be written as(4)HDOP≥n∑i=1ncos2αi×∑i=1nsin2αi=nfn.Equation (5) can be proved by mathematical induction:(5)fn=n24−14∑i=1ncos2αi2.First, whenn=2,(6)f2=1−14cos2α1+cos2α2.Whenn=NN≥3 and (5) is satisfied for n=N−1,(7)fN=∑i=1Ncos2αi×∑i=1Nsin2αi=fN−1+sin2αN∑i=1N−1cos2αi+cos2αN∑i=1N−1sin2αi+cos2αN⋅sin2αN,=N−124−14∑i=1N−1cos2αi2−12∑i=1N−11−cos2αicos2αN+141−cos22αN,=N24−14∑i=1Ncos2αi2.According to the above, (5) is proved. According to (4), the theoretical lower bound of the HDOP can be calculated as follows:(8)HDOP≥4n.The theoretical lower bound of the HDOP decreases as the number of BSs involved in the system increases. However, when the number of BSs exceeds five, the decrease slows significantly.


## 3.1.2. Simulation and Analysis of the Impact of the Number of BSs on the HDOP

Considering the installation convenience, UWB BSs are generally arranged in triangles or quadrangles. By simulating the HDOP of each point in the positioning area in MATLAB, the contour map of the location accuracy characteristics in the area when a different number of BSs participate in the calculation is obtained, as shown in Figure1. Based on the simulation results, in ensuring the accuracy and stability of positioning, four to five times the coverage ensures sufficient positioning accuracy and high economy.Figure 1
HDOP distribution map of positioning area for different numbers of BSs in a uniform layout; (a) triangle three times coverage; (b) triangle four times coverage; (c) square three times coverage; (d) square four times coverage; (e) square five times coverage.
(a)(b)(c)(d)(e)


## 3.1.3. BS Coverage Scheme considering Economy

Based on the construction cost, the premise is to ensure that any point in the location area meetsK times the coverage, and K has been proved to be 4–5 as discussed above. The fewer the BSs used to cover the same area, the more economical is the layout scheme.The BS layout of the UWB positioning system relates to the problem of area coverage, which can be divided into regular triangle and quadrilateral structures. As stated in [29], a square structure has a higher efficiency of four times the coverage layout, and a triangle structure has a higher efficiency of three times the coverage layout. If the effective coverage radius of the UWB tag’s pulse signal is 30 m, the number of BSs needed to achieve three times the coverage of the triangle structure, four times the coverage of the square structure, and five times the coverage of the square structure in different areas is shown in Figure 2. Four times the coverage of the square structure is the best coverage and the best economical solution. Minimal difference exists between the number of BSs required to achieve three and four times the coverage in the same area. Conversely, the number of BSs required to achieve five times the coverage is almost twice the number of BSs required to achieve four times the coverage. However, as mentioned earlier, the positioning accuracy achieved by five and four times the coverage is almost the same. Therefore, the UWB BS layouts for the actual environment are all optimized based on four times the coverage of the square structure.Figure 2
Number of BSs required for different coverages in the same area.


## 3.1.4. Layout Scheme Adjustment

In practice, the scenario space is often irregular. Thus, it is impossible to realize the uniform layout of BSs. The BSs mostly adopt a rectangular or diamond layout to ensure the coverage of four signals. The HDOP of the positioning area with different side-length ratios is simulated using MATLAB; the results are shown in Table1.Table 1
Distribution characteristics of the HDOP in rectangular and diamond layouts with different axial ratios.
LayoutAxial ratioMinimum HDOPMaximum HDOPAverage HDOP80% grading value HDOP90% grading value HDOPRectangular1.01.2851.8161.4551.4261.5821.41.2891.8601.4851.4511.5841.81.2931.9761.5511.5371.6882.21.2962.1251.6361.6011.7922.61.2962.2991.7351.7291.9463.01.2972.4921.8441.8442.136Diamond1.01.2851.6511.4101.5101.5471.41.2851.7611.4501.5771.6401.81.2851.9811.4941.6471.7252.21.2852.2441.5491.7231.8712.61.2852.5551.6171.8392.0583.01.2852.8781.6801.9602.226We draw the following conclusions according to the above results. Based on the positioning accuracy requirements in [30], 90% of the positioning error standard deviation should be within 10 cm. We deduce that the 90% grading value of the HDOP must be less than 2.0, and the ratio of the long side to the short side should not exceed 2.6 for the rectangular layout. For the diamond layout, the ratio of the long axis to the short axis should not exceed 2.6.


## 3.1.5. UWB BS Layout in Ramp Area

When the tag to be measured moves on the ramp area, its height is constantly changing. The BS horizontal spacing must then be adjusted according to the ramp gradient. That is, the effective coverage radius of the BS must be adjusted during the calculation.Assuming thatθ is the angle between the slope and the horizontal plane, the slope direction is that in which the elevation on the slope decreases fastest. The slope area studied in this article is the ideal slope. That is, the slope and aspect of each point on the slope are the same. When the orientation of interest is consistent with the gradient direction, the effective radius r′ is(9)r′=rcosθ.


## 3.1.6. UWB BS Layout in Surface Fluctuation Area

In the actual positioning scenario, the height of the tag to be tested will inevitably change. After deduction, the positioning error caused by the change in tag height is as follows:(10)Gh=1sinα·Δn12+Δn22−2cosαΔn1⋅Δn2,(11)Δrio=ri2+h2−ri−ro2+h2−ro,i=1,2,(12)∇ri0=∂ri0∂x∂ri0∂y,ui=ΔxΔy,where Δni denotes the projection of ui on ∇ri0; x,y denotes the measured coordinate value; ∇ri0 denotes the gradient vector of ri0 at the point to be measured; ri0 denotes the distance difference between BSs; and α denotes the angle between Δn1 and Δn2. Taking the tag height estimation error h as a variable, the positioning error Gh caused by h is simulated and analyzed. The results are shown in Figure 3.Figure 3
Graph ofGh change with tag height.Ash increases, the average positioning error caused by the error in tag height estimation gradually increases, and the maximum error will increase rapidly. When the surface fluctuation is less than 0.3 m, the influence will be less for the BS layout covered by four times the square structural signals (Max Gh<10cm). Therefore, the influence of the elevation difference can be neglected when it is less than 0.3 m. However, when the elevation difference exceeds 0.3 m, the different elevation areas should be divided into subareas.


## 3.1.7. UWB BS Layout in Narrow Area

For narrow areas, such as lanes and roadways, the length of one direction is much smaller than that of the other. This can be formulated as(13)HDOPx,y=G11+G22,where G11 and G22 denote the direction cosines of the tags in the x and y directions, namely, the precision factors of the x and y directions, respectively. Considering the difference in location accuracy between two directions in the narrow region, we evaluate the location accuracy of the BS layout in the narrow region using the direction-weighted plane accuracy factor, that is, through pairing and giving different weights in different directions. Meanwhile, the error variance of the positioning accuracy in two directions is applied to determine the corresponding weight coefficients:(14)wx=1−σxσx+σy,(15)wy=1−σyσx+σy,(16)HDOPwx,y=wx⋅G11+wy⋅G22.Assuming that the width of a narrow area is 3 m and the length is 30 m, 90% of the area to be measured should satisfy the positioning error variance along the width direction (x direction) and the length direction (y direction) when the tag moves in the narrow area. The surface of the narrow area is planar, and the plane coverage radius of the BS is 50 m. The genetic algorithm toolbox of MATLAB is applied to solve the optimization problem of weighted geometric factors. The simulation results are shown in Figure 4.Figure 4
Directional factor changes with rectangular length.The distance between adjacent BSs in they direction should not exceed 10.5 m to ensure that 90% of the positioning area meets the direction accuracy requirement. The rectangular aspect ratio can then reach 10.5/3 = 3.5 m, exceeding the previous requirement of 2.6 m. When the absolute size of the σx and σy changes, or the width of the narrow area changes, the distance will also change.


## 3.1.8. UWB BS Layout considering the Difference in Regional Precision Requirements for AVP

Under actual working conditions, different location areas may have different location accuracy requirements for AVP. The weighted region HDOP model is then formulated to obtain an economical and efficient UWB BS layout scheme. The theoretical optimization model is transformed into a multiobjective optimization solution model using the weight of the judgment matrix. Furthermore, the model considers the different positioning accuracy requirements for different areas. The scale of 1–9 is introduced, whereaij denotes the importance of area si relative to area sj, and the corresponding meanings of different values are shown in Table 2.Table 2
Corresponding meanings of different relative importance values.
aij13579Meaning of aijSi equals SjSi slightly more important than SjSi evidently more important than SjSi extraordinarily more important than SjSi superficially more important than SjAfter obtaining the weight coefficients, based on the linear weighting method, the optimization problem of the BS layout considering the difference in location accuracy requirements is transformed into the optimal solution of equation (17). The solution is then the optimal layout of the UWB BSs:(17)min∑i=1mwi⋅HDOPix,y,xy∈D,HDOPix,y≤σiσΔr,where HDOPix,y denotes the HDOP in positioning area i; σi denotes the standard deviation of the maximum positioning error required by the area; and σΔr denotes the standard deviation of the difference error.Using MATLAB to simulate this method, take the positioning area shown in Figure5(a) as an example, in which the standard deviation of the positioning error required by Area 1 is σ1≤10cm; Area 2: σ2≤15cm; Area 3: σ3≤20cm; and Area 4: σ4≤30cm. According to the judgment matrix, the weights of each region are obtained as follows:(18)w1=25;w2=415;w3=15;w4=215.Figure 5
Base station layout considering different positioning accuracy requirements.
(a)(b)The most suitable layout scheme is obtained by a MATLAB genetic algorithm simulation, as shown in Figure5(b).If the standard deviation of the time difference error measurement,σΔr, is 5 cm, the layout of the BS is checked by inverse calculation. The HDOP of the positioning error of each location area is shown in Table 3 and meets the location accuracy requirement. Therefore, the layout scheme is feasible.Table 3
Simulation results of plane accuracy factors for each localization area.
Location areaHDOPAverageMaximum90% indexing valueRequired valueArea 11.41.821.422Area 21.562.361.693Area 31.331.551.364Area 41.541.781.586


## 3.1.9. Three-Stage UWB Station Layout Planning Method

According to the previous analysis, the layout design methods for various practical scenarios are integrated, and a practical application-oriented regional UWB station layout optimization design method is proposed. The method comprises three stages:Step 1: determine the deployment strategy. The environmental characteristics of each subregion in the region to be located are extracted, and the BS layout strategy of each subregion is determined according to the characteristic environmental parameters.Step 2: determine the layout parameters. Based on the positioning accuracy requirement of each subregion, the layout strategy, and equipment performance parameters, the specific layout spacing, layout number, and other parameters are obtained by the corresponding methods.Step 3: comprehensive adjustment and scheme verification. The layout scheme of each subregion is integrated, and the adjusted scheme is validated by simulating the HDOP. If the location accuracy requirement is satisfied, the scheme of parameters, symbols, and graphics can be further generated. Otherwise, the layout strategy must be determined again until the scheme is validated.In the whole design process of the BS layout scheme, the main parameters involved include (1) characteristic environmental parameters, such as slope, undulating area of surface, and narrow area; (2) positioning accuracy parameters, including the size and direction of positioning errors required by each region; and (3) equipment performance parameters, including the BS signal coverage distance and antenna type.


## 4. Case Study

We verify the performance of the proposed optimization design method of the UWB BS layout using the underground parking lot of Tongji University, Shanghai. As shown in Figure6, tripod with a MS and an electronic total station is applied to obtain the high-precision positioning data as the ground truth. According to the spatial characteristics of different areas in the parking lot and the requirements for ensuring the safety of AVP in different areas [27], the positioning accuracy requirements of each area are analyzed and summarized in Table 4.Figure 6
A tripod with MS and an electronic total station.
(a)(b)Table 4
Accuracy requirements of location in parking lot area.
AreasFeaturesPermissible standard deviation of 90% regional positioning errorVehicle laneHigh speed and simple situationDriving direction 10 cm, vertical driving direction 20 cmPlane intersectionLow speed and complex situation10 cmRampLow speed and complex situationDriving direction 10 cm, vertical driving direction 20 cmEntrance and exitLow speed and complex situationStandard deviation 10 cmParking spaceLow speed and simple situationDriving direction 20 cm, vertical driving direction 20 cmAccording to the three-stage method proposed above, the layout optimization design of BSs is conducted as follows.


### 4.1. Determining Layout Strategy

According to the analysis of the layout in the underground parking lot, the whole area can be divided into four subareas, as shown in Figure7(a). Among them, Area 1 is the entrance and exit of the parking lot, and a rectangular layout scheme can be adopted. Area 2 is a ramp with coupling characteristics between the ramp area and narrow area. After calculating the coverage radius of the ramp according to the slope gradient, the BS layout method based on direction-weighted HDOP can be adopted. Area 3 is a driving lane belonging to a typical narrow region. The BS layout design method based on direction-weighted HDOP should be adopted. Area 4 is the parking spots for which a rectangular layout scheme can be adopted.Figure 7
Schematic map of areas and adjusted UWB BS layout scheme.
(a)(b)


### 4.2. Determining Layout Parameters

The installation height of the BSs in the UWB positioning system is 2.6 m, the height of the tag is approximately 2.0 m, and the effective coverage distance of the tag signal is 30.0 m. Meanwhile, the standard deviation of the station positioning error and time measurement error in the system are both 5.0 cm. Then, the plane coverage radius of the BS isr=R2−H−h2=302−2.6−22=29.9m.According to the above equipment parameters and the site size parameters of the parking lot, and the layout strategy of each subarea determined in the first stage, the specific layout parameters of each subarea are calculated.(1)
Area 1 is the rectangular area with four stations. The simulation results show that the 90% quantile of the HDOP in this area is 1.6081, meeting the positioning accuracy requirement for AVP.(2)
Area 2 is the ramp area. The maximum slope of the ramp is 15%, and the ramp belongs to a narrow area. The aspect ratio should not exceed 2.6. Six BSs should be set up with the distance between adjacent BSs on the same side being 22.3/2 = 11.15. Simultaneously, the optimal layout method based on direction-weighted HDOP is used to check out. In the direction-weighted HDOP model, the weight along the slope direction is 2/3, and the weight along the vertical slope direction is 1/3. The simulation results with the genetic search algorithm show that the 90% indexing value of the positioning accuracy factor along the slope direction is 1.2641 ≤ 2; in the vertical slope direction, this is 2.2665 ≤ 4. Both of these meet the positioning accuracy requirements.(3)
Area 3 is the driving lane. According to AVP requirements, the aspect ratio of the rectangular scheme does not exceed 2.6. Six pairs of BSs should be set up with an interval between adjacent BSs of 13.4 m on one side. These should then be checked using the direction-weighted HDOP model. The accuracy of each direction meets the requirements.(4)
Area 4 is the parking spots. If the standard deviation of 90% regional positioning error is less than 20 cm, the length-width ratio of the rectangular layout can exceed 3. The sub-blocks, which are physically separated in this area, can be arranged according to this aspect ratio.


### 4.3. Comprehensive Adjustment and Scheme Verification

The BS layout schemes of each subregion obtained in the second stage are aggregated, and the BSs with overlapping or extremely similar locations are merged. Finally, the layout scheme shown in Figure7(b) is obtained. After adjustment, the total number of BSs decreases to 30 compared with the original 41 BSs, with a reduction of 27%.The actual positioning accuracy of the underground parking lot is verified by selecting the grid points with a spacing of 2.5 m. The results are shown in Figure8. The range of the grey dotted line represents plus or minus the standard deviation of the positioning error. As shown in Figure 9, there are 96 verification points (sorted by positioning error). Among them, 90 points have standard deviations of less than 5 cm, accounting for 93.75%; four points have standard deviations between 5 and 10 cm, accounting for 4.17%; and only two points have standard deviations exceeding 10 cm, accounting for 2.08%. The positioning accuracy meets the AVP requirements. In Figure 10, we indicate the positions of two points with significantly larger positioning error variance, which can be seen that they are both close to the wall. Therefore, our method has high performance for the actual required area (a reasonable distance from the wall).Figure 8
Absolute positioning error at each verification point arranged from small to large. The error bars represent the standard deviation of measurements.Figure 9
Variance distribution of measured positioning errors of the underground garage.Figure 10
Point distribution with large positioning error variances.


## 4.1. Determining Layout Strategy

According to the analysis of the layout in the underground parking lot, the whole area can be divided into four subareas, as shown in Figure7(a). Among them, Area 1 is the entrance and exit of the parking lot, and a rectangular layout scheme can be adopted. Area 2 is a ramp with coupling characteristics between the ramp area and narrow area. After calculating the coverage radius of the ramp according to the slope gradient, the BS layout method based on direction-weighted HDOP can be adopted. Area 3 is a driving lane belonging to a typical narrow region. The BS layout design method based on direction-weighted HDOP should be adopted. Area 4 is the parking spots for which a rectangular layout scheme can be adopted.Figure 7
Schematic map of areas and adjusted UWB BS layout scheme.
(a)(b)


## 4.2. Determining Layout Parameters

The installation height of the BSs in the UWB positioning system is 2.6 m, the height of the tag is approximately 2.0 m, and the effective coverage distance of the tag signal is 30.0 m. Meanwhile, the standard deviation of the station positioning error and time measurement error in the system are both 5.0 cm. Then, the plane coverage radius of the BS isr=R2−H−h2=302−2.6−22=29.9m.According to the above equipment parameters and the site size parameters of the parking lot, and the layout strategy of each subarea determined in the first stage, the specific layout parameters of each subarea are calculated.(1)
Area 1 is the rectangular area with four stations. The simulation results show that the 90% quantile of the HDOP in this area is 1.6081, meeting the positioning accuracy requirement for AVP.(2)
Area 2 is the ramp area. The maximum slope of the ramp is 15%, and the ramp belongs to a narrow area. The aspect ratio should not exceed 2.6. Six BSs should be set up with the distance between adjacent BSs on the same side being 22.3/2 = 11.15. Simultaneously, the optimal layout method based on direction-weighted HDOP is used to check out. In the direction-weighted HDOP model, the weight along the slope direction is 2/3, and the weight along the vertical slope direction is 1/3. The simulation results with the genetic search algorithm show that the 90% indexing value of the positioning accuracy factor along the slope direction is 1.2641 ≤ 2; in the vertical slope direction, this is 2.2665 ≤ 4. Both of these meet the positioning accuracy requirements.(3)
Area 3 is the driving lane. According to AVP requirements, the aspect ratio of the rectangular scheme does not exceed 2.6. Six pairs of BSs should be set up with an interval between adjacent BSs of 13.4 m on one side. These should then be checked using the direction-weighted HDOP model. The accuracy of each direction meets the requirements.(4)
Area 4 is the parking spots. If the standard deviation of 90% regional positioning error is less than 20 cm, the length-width ratio of the rectangular layout can exceed 3. The sub-blocks, which are physically separated in this area, can be arranged according to this aspect ratio.


## 4.3. Comprehensive Adjustment and Scheme Verification

The BS layout schemes of each subregion obtained in the second stage are aggregated, and the BSs with overlapping or extremely similar locations are merged. Finally, the layout scheme shown in Figure7(b) is obtained. After adjustment, the total number of BSs decreases to 30 compared with the original 41 BSs, with a reduction of 27%.The actual positioning accuracy of the underground parking lot is verified by selecting the grid points with a spacing of 2.5 m. The results are shown in Figure8. The range of the grey dotted line represents plus or minus the standard deviation of the positioning error. As shown in Figure 9, there are 96 verification points (sorted by positioning error). Among them, 90 points have standard deviations of less than 5 cm, accounting for 93.75%; four points have standard deviations between 5 and 10 cm, accounting for 4.17%; and only two points have standard deviations exceeding 10 cm, accounting for 2.08%. The positioning accuracy meets the AVP requirements. In Figure 10, we indicate the positions of two points with significantly larger positioning error variance, which can be seen that they are both close to the wall. Therefore, our method has high performance for the actual required area (a reasonable distance from the wall).Figure 8
Absolute positioning error at each verification point arranged from small to large. The error bars represent the standard deviation of measurements.Figure 9
Variance distribution of measured positioning errors of the underground garage.Figure 10
Point distribution with large positioning error variances.


## 5. Conclusion

This article mainly focuses on the layout planning of UWB BSs for indoor localization of AVP. The TDOA is applied as the positioning approach of the UWB system, and the HDOP is chosen as the accuracy evaluation index. After conducting theoretical analysis and simulation for ideal and actual conditions, we determine the targeted layout analysis method under each condition of the underground parking lot, such as ramp area, surface fluctuation area, and narrow area. A three-stage practical and economical layout design method of UWB BSs is then introduced, including determining the deployment strategy and layout parameters, making comprehensive adjustments, and verifying the scheme. Taking the actual layout planning of a UWB system in an underground parking lot of Tongji University, Shanghai, China, the experimental results show that the proposed three-stage layout design method of UWB BSs for regional differential positioning ensures the accuracy requirements for AVP and greatly reduces the number of BSs. This indicates that the proposed layout planning method of UWB BSs for AVP has high efficiency and good economy.



---

*Source: 3815306-2022-03-03.xml*