CN114979948B - TOA positioning system and TDOA positioning system anchor node layout optimization method and system under indoor NLOS - Google Patents

Abstract

The invention discloses an anchor node layout optimization method for a TOA positioning system and a TDOA positioning system under indoor NLOS, belonging to the field of indoor positioning technology. The invention adopts an objective function of an average GDOP in an effective positioning area and an objective function of a coverage range of the effective positioning area to determine weight coefficients ω ₀ and ω ₁ , and based on a linear weighted combination method, converts a dual-objective optimization problem into a single-objective optimization problem to obtain a fitness function of an anchor node deployment algorithm. By optimizing the geometric shape of the anchor node deployment, the purpose of balancing positioning accuracy and application cost is achieved without changing the system architecture and the number of anchor nodes.

Description

Anchor node layout optimization method and system for TOA positioning system and TDOA positioning system under indoor NLOS

Technical Field

The present invention belongs to the technical field of indoor positioning, and in particular relates to an anchor node layout optimization method and system for a TOA positioning system and a TDOA positioning system under indoor NLOS.

Background technique

GPS-based positioning and navigation services have brought great convenience to our daily life in outdoor environments. With the popularization of smart devices such as smart mobile devices and service robots, the demand for indoor positioning and navigation is becoming stronger and stronger. According to the evaluation results of the Microsoft International Indoor Positioning Competition, the distance-based indoor positioning system has better positioning performance in complex indoor environments. Among the distance-based positioning algorithms, the energy consumption and complexity of the positioning algorithm based on the TOA and TDOA positioning system architecture are lower than those of other positioning system architectures. Therefore, the distance-based TOA and TDOA positioning systems can be well promoted and applied in actual scenarios.

For distance-based indoor positioning technology, the location of unknown nodes (targets) is obtained by using some nodes with known locations, which are called anchor nodes. In the past few decades, domestic and foreign scholars have proposed many valuable indoor positioning methods with the goal of improving positioning performance and reducing application costs, but non-line-of-sight (NLOS) phenomenon is still a huge challenge faced by distance-based positioning systems. NLOS is a common phenomenon in real indoor scenes, which will seriously affect the accuracy and stability of positioning. Introducing better NLOS positioning algorithms or increasing the density of anchor node deployment can reduce the impact of non-line-of-sight phenomena on positioning systems, but the former will increase the complexity of the algorithm, while the latter will inevitably increase the application cost.

Without changing the system architecture and the number of anchor nodes, optimizing the geometry of anchor node deployment can reasonably balance the accuracy requirements and application costs. Regarding the related research on anchor node layout problems in indoor environments, the paper (Apractical approach to landmark deployment for indoor localization) proposed the maxLminE method to find a landmark positioning mode that can reduce the maximum positioning error in a simple and regular LOS environment. Based on the same optimization goal, the paper (Beacon node placement for minimal localization error) introduced an approximate function to reduce the time cost of deploying anchor nodes to achieve the minimum positioning error and find the suboptimal distribution of anchor nodes within an acceptable time. The paper (Optimal beacon placement for self-localization using three beacon bearings) gives an analytical solution to the optimal anchor node deployment problem of the angle of arrival (AOA) positioning algorithm with three anchor nodes. The paper (Optimum strategy of reference emitter placement for dual-satellite tdoa and fdoa localization) uses particle swarm optimization (PSO) and the Cramer-Rao lower bound (CRLB) as the criterion for determining the performance of the positioning system, and proposes the optimal strategy for the placement of reference emitters for dual-satellite TDOA and frequency difference of arrival (FDOA). The paper (Analysis of passive location communication system based on intelligent optimization algorithm) proposes an improved PSO algorithm, which obtains the optimal deployment of different anchor nodes by deriving the GDOP formula of the error of the multi-machine time difference positioning algorithm. However, these studies on the deployment of positioning anchor nodes are still in a simple line-of-sight environment, and the research on the optimization of the deployment of fixed anchor nodes in the NLOS environment is still in its infancy. At this stage, no effective technical means have been proposed to achieve the goal of balancing positioning accuracy and application cost without changing the system architecture and the number of anchor nodes.

Summary of the invention

In order to overcome the shortcomings of the above-mentioned prior art, the purpose of the present invention is to provide a method and system for optimizing the anchor node layout of a TOA positioning system and a TDOA positioning system under indoor NLOS, so as to solve the problem that the prior art cannot achieve the purpose of balancing positioning accuracy and application cost without changing the system architecture and the number of anchor nodes.

In order to achieve the above object, the present invention adopts the following technical solutions:

The present invention discloses a method for optimizing the layout of anchor nodes of a TOA positioning system and a TDOA positioning system under indoor NLOS, comprising:

S1: Obtain the indoor target positioning area map, determine the number of anchor nodes, and determine the objective function of the average GDOP in the effective positioning area and the objective function of the coverage range of the effective positioning area according to the system architecture;

S2: Determine the weight coefficients ω ₀ and ω ₁ , and determine the fitness function of the anchor node deployment algorithm by combining the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area;

S3: Solve the fitness function of the anchor node deployment algorithm to obtain the optimal layout of anchor nodes under indoor NLOS.

Preferably, the objective function of the average GDOP in the effective positioning area in S1 is:

Wherein, _Ai is the coverage area of i LOS anchor nodes; f is the normalization coefficient; for the positioning system based on TOA architecture, i′=2, f=m-1; for the positioning system based on TDOA architecture, i′=3, f=m-2; m is the total number of deployed anchor nodes; n is the nth position to be estimated; N is the total number of positions to be estimated.

Preferably, the optimization function of the effective positioning area coverage in S1 is:

Wherein, Ai _is the coverage area of i LOS anchor nodes; A is the total positioning area; m′=1 is used for the TOA-based system architecture, and m′=2 is used for the TDOA-based system architecture.

Preferably, the fitness function of the anchor node deployment algorithm in S2 is:

F(X)＝ _ω0 · _FG (X)+ _ω1 · _FA (X)

Among them, ω ₀ is the weight coefficient of the average GDOP objective function of the effective positioning area, and ω ₁ is the two weight coefficients of the coverage objective function of the effective positioning area.

Preferably, the optimized anchor node layout is expressed as:

Preferably, in the fitness function of the anchor node deployment algorithm, ω ₀ +ω ₁ =1.

Preferably, in S2, the positioning accuracy and stability are selected according to actual requirements, and the weight coefficients ω ₀ and ω ₁ are determined.

Preferably, in S1, the number of anchor nodes to be deployed is determined according to the system architecture and the cost and accuracy requirements of the system.

Preferably, the number of iteration steps or the expected fitness function value is used as the termination condition to obtain the optimal fitness value under given weight coefficients ω ₀ and ω ₁ ; the layout mode corresponding to the optimal fitness value under given weight coefficients ω ₀ and ω ₁ is the optimal layout of the anchor nodes.

The present invention also discloses an indoor NLOS TOA positioning system and a TDOA positioning system anchor node layout optimization system, comprising an acquisition module, a fitness function acquisition module and a solution module;

The acquisition module is used to acquire a map of the indoor target positioning area, determine the number of anchor nodes, and determine the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area according to the system architecture;

The fitness function acquisition module is used to determine the weight coefficients ω ₀ and ω ₁ , and determine the fitness function of the anchor node deployment algorithm by combining the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area;

The solution module is used to solve the fitness function of the anchor node deployment algorithm to obtain the optimal layout of the anchor nodes under indoor NLOS.

Compared with the prior art, the present invention has the following beneficial effects:

The present application proposes an indoor NLOS TOA positioning system and TDOA positioning system anchor node layout optimization method, adopts the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area, determines the weight coefficients ω ₀ and ω ₁ , and based on the linear weighted combination method, converts the dual-objective optimization problem into a single-objective optimization problem, and obtains the fitness function of the anchor node deployment algorithm. By optimizing the geometric shape of the anchor node deployment, the purpose of balancing the positioning accuracy and application cost is achieved without changing the system architecture and the number of anchor nodes. In addition, the system architecture, positioning method and number of anchor nodes are not changed, only the layout mode of the anchor nodes (i.e., placement position) is changed, so the overall hardware cost of the system is not increased, and the original ranging accuracy of the system is not changed. The optimization objective function is the linear weighting of the average GDOP objective function in the effective positioning area and the optimization function of the coverage of the effective positioning area, while considering the positioning accuracy and coverage of the positioning system. Generally, the sub-objectives of the dual (multi-) objective optimization problem are contradictory and cannot reach the optimal value at the same time. The present invention linearly combines two sub-optimization objectives through weight coefficients, and converts a dual-objective optimization problem into a single-objective optimization problem, so that unique optimal solutions of the two sub-objectives under given weight coefficients can be obtained.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 shows the anchor node deployment method based on experience and the optimized anchor node deployment method;

Figure 2 is a GDOP contour map of empirical anchor node deployment obtained by simulation;

FIG3 is a GDOP contour map of the optimized anchor node deployment obtained by simulation;

Figure 4 shows the positioning results of the empirical anchor node deployment;

Figure 5 shows the positioning result of optimizing anchor node deployment;

FIG6 is a cumulative distribution function of positioning errors of empirical anchor node deployment and optimized anchor node deployment;

Figure 7 shows the optimal deployment of four anchor nodes in an indoor environment with an obstruction;

FIG8 shows the optimal deployment of anchor nodes under different fitness parameters;

9 is a diagram showing the overall hardware circuit composition of the broadcaster used in the present invention;

FIG. 10 is a diagram showing the overall hardware circuit composition of the receiver used in the present invention.

Detailed ways

In order to enable those skilled in the art to better understand the scheme of the present invention, the technical scheme in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work should fall within the scope of protection of the present invention.

It should be noted that the terms "first", "second", etc. in the specification and claims of the present invention and the above-mentioned drawings are used to distinguish similar objects, and are not necessarily used to describe a specific order or sequence. It should be understood that the data used in this way can be interchanged where appropriate, so that the embodiments of the present invention described herein can be implemented in an order other than those illustrated or described herein. In addition, the terms "including" and "having" and any variations thereof are intended to cover non-exclusive inclusions, for example, a process, method, system, product or device that includes a series of steps or units is not necessarily limited to those steps or units clearly listed, but may include other steps or units that are not clearly listed or inherent to these processes, methods, products or devices.

The present invention discloses a method for optimizing the layout of anchor nodes of a TOA positioning system and a TDOA positioning system under indoor NLOS, comprising:

S1: Obtain the indoor target positioning area map, determine the number of anchor nodes, and determine the objective function of the average GDOP in the effective positioning area and the objective function of the coverage range of the effective positioning area according to the system architecture;

The objective function of the average GDOP in the effective positioning area is:

Wherein, A _i - the coverage area of the i LOS anchor nodes; f - normalization coefficient; i′=2, f=m-1 for the positioning system based on the TOA architecture; i′=3, f=m-2 for the positioning system based on the TDOA architecture; m - the total number of deployed anchor nodes; n - the nth position to be estimated; N - the total number of positions to be estimated;

The optimization function of the effective positioning area coverage is:

Wherein, A _i - the coverage area of i LOS anchor nodes; A - is the total positioning area; m′=1 for the TOA-based system architecture, m′=2 for the TDOA-based system architecture;

S2: Determine the weight coefficients ω ₀ and ω ₁ , and determine the fitness function of the anchor node deployment algorithm by combining the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area;

The fitness function of the anchor node deployment algorithm is:

F(X)＝ _ω0 · _FG (X)+ _ω1 · _FA (X)

Wherein, ω ₀ and ω ₁ are two weight coefficients of the average GDOP objective function of the effective positioning area and the coverage objective function of the effective positioning area, respectively, ω ₀ +ω ₁ =1;

The optimized anchor node layout is expressed as:

S3: Solve the fitness function of the anchor node deployment algorithm to obtain the optimal layout of anchor nodes under indoor NLOS.

The present invention is further described in detail below in conjunction with the accompanying drawings:

The geometric dilution precision (GDOP) is defined as the ratio of the position estimation accuracy to the statistical accuracy of the distance measurement value. The smaller the GDOP value, the higher the positioning accuracy. In the LOS environment, the measurement estimation error of the distance-based positioning system can be considered as a zero-mean independent and identically distributed Gaussian variable. So the geometric dilution precision can be expressed as

Where H is the Jacobian matrix of arrival time difference, Q is the covariance matrix, _δr is the root mean square (RMS) of the measurement error shared by all anchor nodes participating in positioning, and tr(·) represents the matrix trace.

In a known indoor LOS scenario, the optimal layout of m anchor nodes is X = { _xi |i = 1, 2, ..., m}, _xi = ( _xi , _yi ) ^T. This layout is usually obtained by minimizing the average GDOP of the effective positioning area. The layout optimization of the anchor nodes can be expressed as

Where A is the total positioning area, is the GDOP value of the anchor node with m LOS measurement values at the nth position to be estimated, and n is the total number of positions to be estimated.

The roaming of smart devices and the random placement of objects make the NLOS phenomenon occur frequently and randomly, and it is no longer reasonable to assume that the distance measurement error is Gaussian distributed under non-line-of-sight conditions.

Distance measurement estimation under NLOS usually requires detecting the delay of the first path signal. The indoor environment is a multipath fading channel, and the first path signal that can be detected under NLOS conditions becomes a scattered path signal. This means that the measurement error is highly correlated with the geometry of the environment, and the GDOP under NLOS is different from the GDOP under LOS.

However, in practical applications, range measurements usually include both LOS and NLOS measurements, and the principle of anchor node deployment is to ensure that more areas receive as many LOS signals as possible. In some positioning methods, when the number of LOS measurements exceeds 3, it has good performance to reduce the impact of NLOS measurements. Therefore, when only measurements from LOS anchor nodes are used in NLOS environments, the GDOP under NLOS can still be approximately regarded as the GDOP under LOS.

The positioning system based on TOA architecture requires a minimum of 2 anchor nodes, and the positioning system based on TDOA architecture requires a minimum of 3 anchor nodes.

Since the factors that determine the performance of the positioning system include positioning accuracy and stability, the two main optimization goals of the anchor node deployment optimization problem in the NLOS environment are to improve positioning accuracy by minimizing the average GDOP of the effective positioning area and to improve stability by expanding the coverage of the effective positioning area. These two optimization goals are often contradictory. Pursuing the minimum average GDOP will inevitably reduce the coverage of the effective positioning area, but a reasonable design of the fitness function can solve this problem.

The area where GDOP can be calculated is also called the "effective positioning area". For NLOS environments, the positioning available area is divided into several areas according to the number of LOS measurements of the anchor nodes. Because the calculation of GDOP can only use LOS measurements, the average GDOP value of each area should be calculated separately.

The average GDOP of the effective positioning area is

Where, _Ai is the coverage area of the i-th LOS anchor node, and f is the normalization coefficient. For the positioning system based on TOA architecture, i′＝2, f＝m-1, and for the positioning system based on TDOA architecture, i′＝3, f＝m-2, the number of line-of-sight measurements of m anchor nodes, n is the nth calculated position of the anchor node, and N is the total number of calculated positions of the anchor nodes.

The optimization of effective positioning area coverage is achieved by reducing the ratio of invalid positioning area to total positioning area, which can be expressed as:

Among them, m′=1 is used for the system architecture based on TOA, and m′=2 is used for the system architecture based on TDOA.

Based on the linear weighted combination method, the dual-objective optimization problem can be transformed into a single-objective optimization problem. The optimized anchor node layout can be expressed as

The fitness function F(X) is expressed as

F(X)＝ _ω0 · _FG (X)+ _ω1 · _FA (X)

Wherein, ω ₀ and ω ₁ are weight coefficients of two objective function terms, ω ₀ +ω ₁ =1.

[Example]

A TOA-based indoor acoustic positioning system is built in scene A, which is a semi-open hall with a space size of 10×10 (m). There are two square columns in the positioning area.

Compared with other TOA-based positioning technologies, the performance of the acoustic positioning system is easily affected by the indoor NLOS phenomenon. Therefore, this example tests the positioning accuracy of the optimal layout obtained by the method of the present invention by comparing the positioning accuracy of the empirical layout of the acoustic positioning system with 4 anchor nodes and the optimal layout obtained by the method of the present invention.

The geometry of the empirical and optimal anchor node layouts is shown in Figure 1. The GDOP distribution contours of the two anchor node deployment geometries are shown in Figures 2 and 3.

Figure 2 shows the geometric GDOP distribution contour map of the empirical anchor node deployment, with an average GDOP F _G (X) of 1.68, a minimum fitness value F of 0.88, and a ratio of unavailable positioning areas of 8.54%. The geometric GDOP distribution contour map of the optimal anchor node is shown in Figure 3, with an average GDOP of 1.25 and a minimum fitness value of 0.63. All positioning spaces are covered by anchor nodes with at least 2 LOS. By comparing Figures 2 and 3, it can be found that optimizing the deployment of anchor nodes can significantly improve the accuracy and stability of the positioning system.

Broadcasters were used as anchor nodes and deployed according to the two geometric shapes of anchor nodes in Figure 1. Receivers were deployed at test points, and the heights of all broadcasters and receivers were set to 1.5 (m) through estimation and calibration. The experiment was repeated 500 times, and the cumulative distribution function (CDF) of the positioning error under the two deployment methods was obtained. The positioning results based on the empirical anchor node layout and the optimal anchor node layout are shown in Figures 4 and 5. The cumulative distribution function (CDF) of the positioning error of the two anchor node deployment methods is shown in Figure 6. By comparing the cumulative distribution function (CDF) of the positioning error based on the two anchor node deployments at specific test points, the performance of the optimal layout of the anchor nodes obtained by the method of the present invention can be studied.

For the indoor acoustic positioning system used in this experiment, the positioning accuracy is improved from 80% probability within 0.35m to 90% probability within 0.24m. The results of this example show that the accuracy and stability of the positioning system can be significantly improved by optimizing the anchor node layout through the method of the present invention.

The following simulation is performed by taking the layout of four anchor nodes in an indoor environment with an obstruction as an example to further describe the embodiment of the present invention.

FIG7 shows the optimized anchor node layout of the TOA-based positioning system under indoor NLOS. Based on the simulation of FIG7 , the fitness function parameters ω ₀ and ω ₁ are studied.

Figure 8 shows the geometry of the optimized anchor node layout under different combinations of ω ₀ and ω ₁ .

The following are some values of ω ₀ and ω ₁ , as well as the objective function representing the average GDOP of the effective positioning area, the objective function value of the effective positioning area coverage, and the corresponding fitness function value:

It can be found from the table that the global average GDOPF _G (X) decreases with the increase of ω ₀ , while F _A (X) increases with the decrease of ω _1. The minimum fitness F reaches its peak when ω ₀ = ω _1. The simulation results show that by adjusting the values of ω ₀ and ω ₁ , the priority of the average GDOP and the effective positioning area can be controlled.

As a preferred solution, see Figure 9 for the overall hardware circuit composition diagram of the broadcaster used in this example; the broadcaster is mainly composed of a power supply part, a control switch, a DC-DC converter, a low-voltage linear regulator LDO, a microcontroller unit MCU, an audio chip, a power amplifier chip, a radio frequency port and a speaker, and the coverage radius of the broadcaster used is 30m. Figure 10 is the overall hardware circuit composition diagram of the receiver used in this example, and the receiver mainly includes battery charging, a control switch, a DC-DC converter, a low-voltage dropout linear regulator, a microcontroller unit, a field-editable gate array, a Flash memory, a field-editable gate array, an analog-to-digital converter and a microphone.

The above contents are only for explaining the technical idea of the present invention and cannot be used to limit the protection scope of the present invention. Any changes made on the basis of the technical solution in accordance with the technical idea proposed by the present invention shall fall within the protection scope of the claims of the present invention.

Claims (8)

1. A method for optimizing the layout of anchor nodes of a TOA positioning system and a TDOA positioning system under indoor NLOS, characterized by comprising: S1: Obtain the indoor target positioning area map, determine the number of anchor nodes, and determine the objective function of the average GDOP in the effective positioning area and the objective function of the coverage range of the effective positioning area according to the system architecture; S2: Determine the weight coefficient and/> , the fitness function of the anchor node deployment algorithm is determined by combining the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area; S3: Solve the fitness function of the anchor node deployment algorithm to obtain the optimal layout of anchor nodes under indoor NLOS; The objective function of the average GDOP in the effective positioning area described in S1 is: in, -The coverage area of i LOS anchor nodes;/> -Normalization coefficient; Positioning system based on TOA architecture/> ; Positioning system based on TDOA architecture/> ; /> -The total number of deployed anchor nodes; /> - No./> Positions to be estimated; /> -Total number of positions to be estimated; /> For having/> The anchor node for the LOS measurement value is in the The GDOP value at the position to be estimated; The optimization function of the effective positioning area coverage is: in, -/> The coverage area of each LOS anchor node; /> - is the total positioning area; /> For TOA-based system architecture,/> For use in TDOA-based system architectures. 2. According to the method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system, the fitness function of the anchor node deployment algorithm in S2 is: in, is the weight coefficient of the average GDOP objective function of the effective positioning area,/> are the two weight coefficients of the objective function of effective positioning area coverage. 3. According to the method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system, the optimized anchor node layout is expressed as: . 4. The method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system according to claim 2, wherein the fitness function of the anchor node deployment algorithm is . 5. The method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system according to claim 1, characterized in that in S2, the positioning accuracy and stability are selected according to actual requirements, and the weight coefficient is determined. and/> . 6. The method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system according to claim 1, characterized in that in S1, the number of anchor nodes to be deployed is determined according to the system architecture and the cost and accuracy requirements of the system. 7. The method for optimizing the anchor node layout of an indoor NLOS TOA positioning system and a TDOA positioning system according to claim 1, characterized in that the number of iteration steps or the expected fitness function value is used as the termination condition to obtain a given weight coefficient and/> The optimal fitness value under given weight coefficient/> and/> The layout method corresponding to the optimal fitness value under is the optimal layout of the anchor nodes. 8. An indoor NLOS TOA positioning system and TDOA positioning system anchor node layout optimization system, characterized by comprising an acquisition module, a fitness function acquisition module and a solution module; The acquisition module is used to acquire a map of the indoor target positioning area, determine the number of anchor nodes, and determine the objective function of the average GDOP in the effective positioning area and the objective function of the coverage of the effective positioning area according to the system architecture; The objective function of the average GDOP in the effective positioning area is: in, -The coverage area of i LOS anchor nodes;/> -Normalization coefficient; Positioning system based on TOA architecture/> ; Positioning system based on TDOA architecture/> ; /> -The total number of deployed anchor nodes; /> - No./> Positions to be estimated; /> -Total number of positions to be estimated; /> For having/> The anchor node for the LOS measurement value is in the The GDOP value at the position to be estimated; The optimization function of the effective positioning area coverage is: in, -/> The coverage area of each LOS anchor node; /> - is the total positioning area; /> For TOA-based system architecture,/> For TDOA-based system architecture; The fitness function acquisition module is used to determine the weight coefficient and/> , the fitness function of the anchor node deployment algorithm is determined by combining the objective function of the average GDOP in the effective positioning area and the objective function of the coverage range of the effective positioning area; The solution module is used to solve the fitness function of the anchor node deployment algorithm to obtain the optimal layout of the anchor nodes under indoor NLOS.