CN108495252B - Indoor positioning network element optimization layout method based on genetic algorithm and simulated annealing - Google Patents

Abstract

The invention discloses an indoor positioning network element optimization layout method based on genetic algorithm and simulated annealing, belonging to the field of indoor positioning and comprising the following steps: step (1): carrying out network element layout; step (2): determining control parameters required by the adaptive genetic algorithm; and (3): initializing the network element layout; and (4): calculating the fitness; and (5): judging whether genetic convergence conditions are met; and (6): selecting a network element layout with higher fitness; and (7): performing cross operation on the binary codes to obtain filial generations; and (8): carrying out negation operation on the binary code to obtain variation; and (9): generating a new network element layout space; step (10): carrying out simulated annealing operation on the population; step (11): generating an optimal network element layout result; step (12): and outputting the optimal network element layout result, and ending. The invention has strong global search capability and local search capability, improves the positioning precision and improves the search efficiency.

Description

An optimal layout method for indoor positioning network elements based on genetic algorithm and simulated annealing

technical field

The invention belongs to the field of indoor positioning, in particular to an indoor positioning network element optimization layout method based on genetic algorithm and simulated annealing.

Background technique

With the development of network technology and communication technology, location services have become increasingly important. Since most of the activities of people are carried out indoors, indoor positioning has attracted more and more attention. Among them, indoor positioning based on UWB The technology can achieve centimeter-level positioning accuracy in specific scenarios, and has been widely used in various indoor positioning products. However, the deployment cost of UWB positioning base stations is very high. When the number of network elements is limited, how to layout can make positioning It is a very meaningful research topic to have the largest coverage of the signal and the highest positioning accuracy.

The problem of optimal layout of network elements is a NP-hard problem, and the current researches all stay at the level of applying heuristic algorithms to find the optimal solution. Among them, the genetic algorithm can find the optimal solution in a random way in the sense of probability. The document "Agapie A, Wright A H. Theoretical analysis of steady state genetic algorithms [J]. Applications of Mathematics, 2014, 59(5): 509 -525. Theoretical analysis of steady state genetic algorithms" uses genetic algorithms to solve wireless network planning problems, but genetic algorithms do not have a feasible feedback mechanism, and in some cases, a large number of redundant iterations will be generated, resulting in low efficiency and other problems. At the same time, in practical application, the genetic algorithm will be prone to premature phenomenon and poor local optimization ability. Simulated annealing algorithm has strong local search ability and can avoid the search process from falling into the local optimal solution. It is not suitable for the entire search space, and it is difficult to make the search process enter the most promising search area. The document "Han R, Feng C, Xia H, et al.Coverageoptimization for dense deployment small cell based on ant colony algorithm[C],2014IEEE80th.IEEE,2014:1-5" uses ant colony algorithm to lay out network elements The cost and coverage of network element deployment are the layout goals, but in the initial stage of ant colony algorithm search, there is little or no available information, so the convergence speed of ant colony algorithm is slow. In the aspect of indoor positioning simulation, the research and implementation of a high-precision indoor positioning simulation system in the literature can input a network element layout in a specific indoor scene to obtain the positioning signal coverage and average positioning error of the area to be located.

SUMMARY OF THE INVENTION

The purpose of the present invention is to disclose an indoor positioning network element optimization layout method based on genetic algorithm and simulated annealing with strong local search ability and high efficiency.

The object of the present invention is achieved in this way:

The optimal layout method of indoor positioning network elements based on genetic algorithm and simulated annealing includes the following steps:

Step (1): Layout of network elements: Number the positions of arrangable network elements in sequence and arrange the network elements, and at the same time convert the number of each network element into a binary code:

Draw grids in the floor plan of a specific indoor scene, and consider the intersection of the grids on the exterior walls of the indoor scene as the positions where network elements can be deployed. The number is converted to binary code.

Step (2): Determine the control parameters required by the adaptive genetic algorithm, including population size, maximum number of iterations, crossover probability and mutation probability:

The control parameters required by the adaptive genetic algorithm include: population size, maximum number of iterations, crossover probability and mutation probability. In the network element layout, n network elements are required, the binary code of each network element is an m-bit binary number, and each network element layout is regarded as a chromosome with a length of len=n*m. If the number of populations is k, the population size is a matrix of k*len.

Step (3): Initialize the network element layout: randomly select n mutually different network elements from all arrangable network element groups as the initial network element layout;

Step (4): Calculate the fitness:

adaptability:

In the above formula, N represents the number of test points in the positioning area, and ERROR _i represents the positioning error of the positioning point i.

Step (5): iteratively determine whether the genetic convergence condition is met, if the genetic convergence condition is met, jump to step (9), otherwise jump to step (6);

Step (6): Select the network element layout with higher fitness:

A random number r is generated between 0 and the total fitness, and then the population individuals are randomly sampled according to the roulette method, and the probability that the population individual x _i is selected is F( _xi ):

In the above formula, f( _xi ) is the fitness of the population individual _xi ; the network element layout with higher fitness is selected.

Step (7): Perform a crossover operation on the binary code according to the crossover probability P _b of the network element layout with higher fitness to obtain the offspring:

Take a single-point crossover operation: first generate a random real number 0≤r≤1, set the crossover probability 0<P _b <1, if r<P _b , crossover needs to be performed, otherwise it is not performed. If crossover is required, the crossover position is randomly selected, and the codes of the binary strings after the crossover position are exchanged.

Step (8): Invert the binary code according to the mutation probability P _y for the network element layout with higher fitness to obtain mutation:

Generate a random real number 0≤r≤1, if r<P _y , mutate, 0<P _y <1 is the mutation probability; if mutation is required, first determine the mutation position rand*chromo_size, if it is 0, do not mutate , otherwise the inversion operation of the binary code of the mutation position produces mutation, so that 1 becomes 0 and 0 becomes 1.

Step (9): Generate a local optimal network element layout result, and generate a new network element layout space according to the coordinate information:

After the local optimal network element layout result is obtained through the adaptive genetic algorithm, the binary code of the local optimal network element layout result is converted into decimal code and corresponding coordinate information. Under the premise of keeping the height value z unchanged, in the xOy plane, with each network element position in the local optimal network element layout result as the center, make a regular hexagon, and calculate the coordinate information of the vertex position of each regular hexagon. , and each network element location is the center as a new network element layout space. ;The new number of the network element at the center point of the regular hexagon is the decimal code followed by "00", and the vertex number of each regular hexagon is followed by the decimal code of the network element at the center point of the regular hexagon followed by adding "00" in a clockwise direction. 01" "02" "03" "04" "05" "06".

Step (10): use the simulated annealing network element layout algorithm to perform a simulated annealing operation on the population to obtain a relatively optimal network element layout method:

The network element layout algorithm of simulated annealing: starting from a higher temperature, with the decrease of temperature parameters, according to the positioning accuracy of the current network element layout and the positioning accuracy of the new network element layout space, the new network element layout space is accepted with a certain probability. Through random selection of all possible situations of network element layout in the entire physical space, a relatively optimal network element layout method is finally obtained.

Step (11): generating an optimal network element layout result by using a relatively optimal network element layout method;

Step (12): output the optimal network element layout result, and end.

The beneficial effects of the present invention are:

The invention takes the adaptive genetic algorithm as the main process, and integrates the simulated annealing mechanism into it to adjust and optimize the population. It has strong global search ability and strong local search ability, which improves the positioning accuracy. Because the network element layout group is changed before the simulated annealing algorithm is performed, not only the search efficiency is improved, but also the obtained network element layout result is closer to the actual optimal network element layout result.

Description of drawings

Fig. 1 is the flow chart of the optimal layout method of indoor positioning network elements based on genetic algorithm and simulated annealing;

FIG. 2 is a schematic diagram of network element layout changes in a specific embodiment scenario;

FIG. 3 is a schematic diagram of the recoding situation of network element No. 3 in a specific implementation scenario.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings:

The optimal layout method of indoor positioning network elements based on genetic algorithm and simulated annealing includes the following steps:

Step (1): Layout of network elements: Number the positions of arrangable network elements in sequence and arrange the network elements, and at the same time convert the number of each network element into a binary code:

Draw grids in the floor plan of a specific indoor scene, and consider the intersection of the grids on the exterior walls of the indoor scene as the positions where network elements can be deployed. The number is converted to binary code.

Step (2): Determine the control parameters required by the adaptive genetic algorithm, including population size, maximum number of iterations, crossover probability and mutation probability:

The control parameters required by the adaptive genetic algorithm include: population size, maximum number of iterations, crossover probability and mutation probability. In the network element layout, n network elements are required, the binary code of each network element is an m-bit binary number, and each network element layout is regarded as a chromosome with a length of len=n*m. If the number of populations is k, the population size is a matrix of k*len.

Step (3): Initialize the network element layout: randomly select n mutually different network elements from all arrangable network element groups as the initial network element layout;

Step (4): Calculate the fitness:

adaptability:

In the above formula, N represents the number of test points in the positioning area, and ERROR _i represents the positioning error of the positioning point i.

Step (5): iteratively determine whether the genetic convergence condition is met, if the genetic convergence condition is met, jump to step (9), otherwise jump to step (6);

Step (6): Select the network element layout with higher fitness:

A random number r is generated between 0 and the total fitness, and then the population individuals are randomly sampled according to the roulette method, and the probability that the population individual x _i is selected is F( _xi ):

In the above formula, f( _xi ) is the fitness of the population individual _xi ; the network element layout with higher fitness is selected.

Step (7): Perform a crossover operation on the binary code according to the crossover probability P _b of the network element layout with higher fitness to obtain the offspring:

Take a single-point crossover operation: first generate a random real number 0≤r≤1, set the crossover probability 0<P _b <1, if r<P _b , crossover needs to be performed, otherwise it is not performed. If crossover is required, the crossover position is randomly selected, and the codes of the binary strings after the crossover position are exchanged.

Step (8): Invert the binary code according to the mutation probability P _y for the network element layout with higher fitness to obtain mutation:

Generate a random real number 0≤r≤1, if r<P _y , mutate, 0<P _y <1 is the mutation probability; if mutation is required, first determine the mutation position rand*chromo_size, if it is 0, do not mutate , otherwise the inversion operation of the binary code of the mutation position produces mutation, so that 1 becomes 0 and 0 becomes 1.

Step (9): Generate a local optimal network element layout result, and generate a new network element layout space according to the coordinate information:

After the local optimal network element layout result is obtained through the adaptive genetic algorithm, the binary code of the local optimal network element layout result is converted into decimal code and corresponding coordinate information. Under the premise of keeping the height value z unchanged, in the xOy plane, with each network element position in the local optimal network element layout result as the center, make a regular hexagon, and calculate the coordinate information of the vertex position of each regular hexagon. , and each network element location is the center as a new network element layout space. ;The new number of the network element at the center point of the regular hexagon is the decimal code followed by "00", and the vertex number of each regular hexagon is followed by the decimal code of the network element at the center point of the regular hexagon followed by adding "00" in a clockwise direction. 01" "02" "03" "04" "05" "06".

Step (10): use the simulated annealing network element layout algorithm to perform a simulated annealing operation on the population to obtain a relatively optimal network element layout method:

The network element layout algorithm of simulated annealing: starting from a higher temperature, with the decrease of temperature parameters, according to the positioning accuracy of the current network element layout and the positioning accuracy of the new network element layout space, the new network element layout space is accepted with a certain probability. Through random selection of all possible situations of network element layout in the entire physical space, a relatively optimal network element layout method is finally obtained.

Step (11): generating an optimal network element layout result by using a relatively optimal network element layout method;

Step (12): output the optimal network element layout result, and end.

Example 1 is given below:

As shown in Figure 2a, Figure 2b, Figure 2c, I represents the wall of the building, II represents the network element, and the dark network element is the currently obtained network element layout result. The size of the scene is 8m*4m*3m. Due to the engineering construction requirements, network elements can only be deployed on the wall and within 1m from the wall. Therefore, a grid with a density of 2m*2m is set on the plane map, and the network elements are laid out. The positions are set on the grid on the wall, a total of 12, and the heights are randomly distributed between 2.8m and 3m. The position of the No. 1 network element is used as the coordinate origin, and the network elements are numbered 1-12 in a clockwise order.

Step (1): perform binary encoding on it. Since the maximum number of network elements is 12, four-digit binary numbers are used for encoding, and the "1-12" network elements are sequentially encoded as "0001-1100";

Step (2): determine that the population size is 50, the maximum number of iterations is 20, the crossover probability is 0.6, and the mutation probability is 0.01;

Step (3): According to experience, four network elements numbered 1, 5, 7, and 11 are selected as the initial layout, as shown in Figure 2a;

Step (4): calculating fitness according to the aforementioned disclosed high-precision indoor positioning simulation system;

Step (5): iteratively determine whether the fitness meets the condition of less than 3m, if it is satisfied, skip to step (9), if not, skip to step (6) to prepare for genetic operation;

Steps (6) to (8): genetic operations are performed in the network element layout group to obtain the local optimal solution. It is assumed that the local optimal solution obtained when the convergence conditions are met is transcoded into No. 3, 8, 10, and 12 networks. element, as shown in Figure 2b;

Step (9): Change the network element layout group and re-encode it, as shown in Figure 3, taking the No. 3 network element as an example, including 7 network element positions, so there are 7*4=28 in the new network element layout group network element;

Steps (10) to (12): perform a simulated annealing operation on the above groups, and obtain network element layout results of network elements No. 300, 801, 1004, and 1204, as shown in Figure 2c.

The invention takes the adaptive genetic algorithm as the main process, and integrates the simulated annealing mechanism into it to adjust and optimize the population. It has strong global search ability and strong local search ability, which improves the positioning accuracy. Because the network element layout group is changed before the simulated annealing algorithm is performed, not only the search efficiency is improved, but also the obtained network element layout result is closer to the actual optimal network element layout result.

The above description is not intended to limit the present invention, and for those skilled in the art, the present invention may have various modifications and variations. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (8)

1. An indoor positioning network element optimization layout method based on genetic algorithm and simulated annealing is characterized in that: comprises the following steps:

step (1): and (3) carrying out network element layout: numbering the positions of the deployable network elements in sequence, deploying the network elements, and converting the number of each network element into a binary code;

step (2): determining control parameters required by the adaptive genetic algorithm, including population scale, maximum iteration times, cross probability and variation probability;

and (3): initializing the network element layout: randomly selecting n different network elements from all the deployable network element groups as initial network element layouts;

and (4): calculating the fitness;

and (5): iteratively judging whether a genetic convergence condition is met, if the genetic convergence condition is met, jumping to the step (9), and if not, jumping to the step (6);

and (6): selecting a network element layout with higher fitness;

and (7): the network element layout with higher fitness is arranged according to the cross probability P_bPerforming cross operation on the binary codes to obtain filial generations;

and (8): the network element layout with higher fitness is arranged according to the mutation probability P_yCarrying out negation operation on the binary code to obtain variation;

and (9): generating a local optimal network element layout result, and generating a new network element layout space according to the coordinate information; the method specifically comprises the following steps:

after obtaining a local optimal network element layout result through a self-adaptive genetic algorithm, converting a binary code of the local optimal network element layout result into a decimal code and corresponding coordinate information; on the premise of keeping the height value z unchanged, respectively making regular hexagons by taking each network element position in the local optimal network element layout result as a center in an xOy plane, calculating coordinate information of the vertex position of each regular hexagon, and taking the calculated coordinate information and each network element position as a center together to serve as a new network element layout space; the new number of the net element at the central point of the regular hexagon is decimal code and then '00', and the number of the vertex of each regular hexagon is formed by sequentially adding '01', '02', '03', '04', '05' and '06' in the clockwise direction after the decimal code of the net element at the central point of the regular hexagon;

step (10): a simulated annealing operation is carried out on the group by using a simulated annealing network element layout algorithm to obtain a relatively optimal network element layout method;

step (11): generating an optimal network element layout result by using a relatively optimal network element layout method;

step (12): and outputting the optimal network element layout result, and ending.

2. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (1) is specifically as follows:

drawing grids in a plan view of a specific indoor scene, considering that intersection points of the grids on the outer wall of the indoor scene are positions where network elements can be arranged, arranging the network elements at the positions where the network elements can be arranged, numbering the network elements in sequence, and converting the number of each network element into binary coding.

3. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (2) is specifically as follows:

the control parameters required by the adaptive genetic algorithm include: population scale, maximum iteration times, cross probability and variation probability; in the network element layout, n network elements are needed, the binary code of each network element is an m-bit binary number, and each network element layout is regarded as a chromosome with a length len equal to n x m; if the population number is k, then the population size is k × len matrix.

4. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the fitness in the step (4) is as follows:

in the above formula, N represents the number of test points of the positioning area, ERROR_iIndicating the positioning error of the positioning point i.

5.The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (6) is specifically as follows:

generating a random number r between 0 and the total fitness, and randomly sampling population individuals x in a roulette mode_iProbability of being selected F (x)_i)：

In the above formula, f (x)_i) Is a population of individuals x_iThe fitness of (2); and selecting the network element layout with higher fitness.

6. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (7) is specifically as follows:

adopting single-point cross operation: firstly, a random real number 0 is more than or equal to r and less than or equal to 1, and a cross probability 0 is set<P_b<1, if r<P_bIf not, the crossing is not carried out; if the crossing is needed, the crossing position is randomly selected, and the binary string codes after the crossing position are exchanged.

7. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (8) is specifically as follows:

generating a random real number 0 ≦ r ≦ 1, if r<P_yThen, variation is performed, 0<P_y<1 is the mutation probability; if the variation is needed, firstly, the variation position rand chromo size needs to be determined, if the variation position rand chromo size is 0, the variation is not performed, otherwise, the binary code of the variation position is inverted to generate the variation, so that 1 becomes 0, and 0 becomes 1.

8. The indoor positioning network element optimizing layout method based on genetic algorithm and simulated annealing as claimed in claim 1, wherein: the step (10) is specifically as follows:

simulated annealing network element layout algorithm: and starting from a certain higher temperature, receiving a new network element layout space with a certain probability according to the positioning precision of the current network element layout and the positioning precision of the new network element layout space along with the reduction of the temperature parameter, and finally obtaining the relatively optimal network element layout by randomly selecting all possible conditions of the network element layout in the whole physical space.

Images