CN108616836A - A kind of WLAN positioning network-building methods based on signal statistics distribution - Google Patents

Abstract

A WLAN positioning networking method based on the statistical distribution of signals described in the present invention first considers the correlation between each access point (Access point, AP), and calculates the probability density function of the signal at the reference point; secondly, uses the probability The density function calculates the probability of different signal vectors appearing at the reference point, and combines the position prior probability of the reference point to calculate the weighted probability of the reference point; then, calculates the average positioning accuracy of the reference point to obtain the average positioning of the target area Accuracy; Finally, the AP position in the target area is optimized using a simulated annealing algorithm. The WLAN positioning and networking method based on the statistical distribution of signals provided by the present invention can reasonably select the position of the AP and avoid the blindness of the AP arrangement.

Description

A WLAN positioning networking method based on signal statistical distribution

technical field

The invention belongs to indoor positioning technology, and in particular relates to a WLAN positioning networking method based on statistical distribution of signals.

Background technique

With the rapid development of wireless communication technology and the widespread popularization of mobile devices, people's demand for location-based services continues to grow, which brings unprecedented development space for location-based services. Nowadays, the outdoor positioning system represented by the Global Positioning System (Global Positioning System, GPS) can realize real-time and reliable outdoor positioning. However, due to the complexity of the indoor environment and the shielding of signals by buildings, the positioning performance of outdoor positioning systems drops sharply indoors, making it difficult to meet people's positioning needs. Therefore, the indoor positioning system has become a research hotspot of many scholars. At present, the mainstream positioning technologies used in indoor positioning systems mainly include radio frequency identification (Radio Frequency Identification, RFID) positioning technology, ultra wideband (Ultra Wideband, UWB) positioning technology, WLAN (Wireless Local Area Network, WLAN) indoor positioning technology, Zigbee indoor positioning technology, etc. technology, visible light indoor positioning technology, etc. Among them, due to the wide deployment and low cost of wireless local area network, WLAN indoor positioning technology has been widely used.

The positioning methods used in WLAN indoor positioning technology mainly include positioning methods based on Angle of Arrival (AOA), positioning methods based on Time of Flight (TOF), and positioning methods based on Received Signal Strength (RSS). . The indoor positioning method based on RSS has become one of the main indoor positioning methods due to the advantages of easy acquisition and high precision of RSS. The traditional RSS ranging method is easily affected by the indoor complex environment, and its positioning performance is poor. The positioning method based on location fingerprint can describe the target environment very well and achieve high positioning accuracy. The positioning method based on location fingerprint mainly includes offline stage and online stage. In the offline stage, RSS is collected at each reference point, and the mapping relationship between physical coordinates and signal strength is established, so as to build a location fingerprint database; in the online stage, RSS is collected in real time and compared with the database to complete the settlement of the target location.

When building a location fingerprint database, several wireless access points (AccessPoints, APs) need to be deployed in the target environment, but the blind deployment of APs not only consumes a lot of manpower and material resources, but also cannot improve the positioning accuracy. In order to find a method for reasonably arranging APs, it is necessary to develop a WLAN positioning networking method based on signal statistical distribution.

Contents of the invention

The purpose of the present invention is to provide a WLAN positioning networking method based on signal statistical distribution, which can reasonably select the AP position and avoid the blindness of AP arrangement.

A WLAN positioning networking method based on signal statistical distribution of the present invention comprises the following steps:

Step 1. Select the target area to be located;

Step 2. Determine the positions of all WLAN access points in the target area, and arrange m APs in the target area, that is, AP ₁ , AP ₂ , . . . , AP _m ;

Step 3. Determine the positions of all reference points in the target area, and select n RPs in the target area, namely RP ₁ , RP ₂ , . . . , RP _n ;

Step 4. Calculate the Euclidean distance between the i-th RP and the j-th AP physical space Among them, (x _i , y _i ) is the location coordinate of the i-th RP, and (x _j , y _j ) is the location coordinate of the j-th AP;

Step 5, making the RSS obey the Gaussian distribution, and considering the correlation between each AP, calculating the probability density function of the RSS measured at the i-th RP;

Step 6. Calculate the probability value p _i1 of the qth RSS vector R _q =[r ₁ r ₂ ... r _m ] ^T (1≤q≤Q) appearing at the i-th reference point, where r _i (1≤i≤ m) is the RSS value from the j-th AP received by the i-th reference point, and Q is the number of all possible RSS vectors;

Step 7. Calculate the prior probability p _i2 of the location of the i-th reference point;

Step 8. Calculate the weighted probability p _i =p _i1 ×p _i2 of the RSS vector R _q appearing at the ith RP;

Step 9, calculating the average positioning accuracy of the i-th reference point;

Step ten, calculating the average positioning accuracy of the target area;

Step eleven, use the average positioning accuracy e of the target area as the objective function of the simulated annealing algorithm, and use this algorithm to find the optimal solution of the objective function, even if the e value is the smallest, so as to obtain the optimal AP placement position;

Step 12, the algorithm ends, and the optimal AP position coordinates are returned.

In the fifth step, the RSS is made to obey the Gaussian distribution, and the correlation between each AP is considered, and the probability density function of the RSS measured at the i-th RP is calculated, including the following steps:

5a. Assuming that the propagation model of the signal conforms to the log-normal path loss model, the expression of the signal strength value P _ij received by the i-th reference point from the j-th access point is:

Among them, d ₀ is the reference distance, take d ₀ =1m; P(d ₀ ) is the power at the reference point; γ is the path loss index, which reflects the relationship between the loss of signal strength and the propagation distance; d _ij is the The Euclidean distance from the i reference point to the jth AP, ζ is the random noise that obeys the Gaussian distribution N(u,σ ² );

5b. Collect 10,000 RSS values from m APs at the _i -th reference point, a total of 10,000×m RSS values, expressed as:

5c, using the matrix R _i obtained in step 5b to calculate the covariance matrix C is:

Among them, c _jj (1≤j≤m) is the variance of the RSS value from the jth AP, and c _jk (1≤k≤m, j≠k) is the RSS value from the jth AP and the kth AP covariance;

5d. Define X=(x ₁ ,x ₂ ,...,x _m ) ^T as the RSS vector measured at the i-th RP, where x _i (1≤i≤m) is the RSS vector from the j-th AP RSS value, calculate the probability density function f _i (X) of the RSS measured at the i-th RP as:

Wherein, U _i =(μ ₁ , μ2,...,μ _m ) ^T is the mean vector of the RSS values from m APs received at the i-th RP.

In said step six, calculating the probability value that a set of RSS vectors appear at the i reference point includes the following steps:

6a. Determine the integral neighborhood δ of the RSS vector (δ>0);

6b. The probability of the RSS vector appearing at the i-th RP is:

In the seventh step, calculating the prior probability p _i2 of the location of the i-th reference point includes the following steps:

7a, the physical environment around the furniture is set as the area of interest, and the obstacle is the unreachable area; the map of the target area is converted into an image whose pixel width is n; initialization k=1, k is the counting amount;

7b. Set the starting point A and the ending point B; set A as the grid T to be processed;

7c. Store T into the open list, which is a list of grids to be checked;

7d. Delete T from the open list, and add T to the closed list. The closed list stores the squares that do not need to be checked again; for the reachable adjacent squares of T, check whether it is already in the open list, and if so, enter Step 7e; if not, go to step 7f;

7e. Calculate the Euclidean distance d from T to its adjacent square, the Euclidean distance G from T to the starting point A, and the Euclidean distance G′ from the adjacent square to the starting point A. If G+d<G′, set T to is the parent square of the adjacent square, and the value of the cost function is F=G+H+d, H is the Manhattan distance from the adjacent square to the end point B;

7f. Put the adjacent grid of T into the open list, set T as its parent grid; calculate the cost function F=G+H, where G is the Euclidean distance from the adjacent grid to the starting point A;

7g. Select the grid C with the smallest cost function value F from the open list, store C in the path trace _k , and judge whether C is equal to the end point B, if so, go to step 7h, if not, set C as the grid to be processed T, go to step 7c;

7h. Obtain the simulation path trace _k , judge whether k is less than or equal to the number of paths K, if so, k=k+1, return to step 7b; if not, the path simulation ends, and K simulation paths are obtained;

7i. Divide the target area into five sub-areas; observe the K paths obtained by the simulation, and count the prior probability of each sub-area; assuming that the reference point is equally likely to appear in each sub-area, then according to the priori of the sub-area to which the reference point belongs Probability, to obtain the prior probability p _i2 of the location of each reference point.

In said step nine, calculating the average positioning accuracy of the i reference point includes the following steps:

9a. Calculate the weighted probability p ₁ , p ₂ ,...p _n of the RSS vector R _q appearing at all reference points, and find out the maximum weighted probability of its appearance:

p _max = max(p ₁ ,p2,...,p _n );

Record the physical coordinates of the reference point corresponding to the maximum weighted probability p _max ;

9b. Calculate the Euclidean distance from the ith reference point to the point with the largest weighted probability of the RSS vector R _q appearing;

9c. Take different RSS vectors, repeat step six, step seven and step eight in turn, and obtain the weighted probability that all possible RSS vectors appear at the i-th reference point, and the weighted probability vector P _i is:

Among them, Q is the number of all possible RSS vectors; is the weighted probability that the qth RSS vector appears at the ith reference point;

9d, repeating steps 9a and 9b, under all possible RSS value conditions, calculate the distance vector from the i-th reference point to the point with the largest weighted probability of RSS occurrence:

in, is the Euclidean distance from the i-th reference point to the point with the highest weighted probability of the q-th RSS vector appearing;

9e, utilize the weighted probability vector and the distance vector that step 9c and step 9d obtain, obtain the average positioning accuracy of the i reference point as:

e _i =P _i ×D _i .

In the eleventh step, the average positioning accuracy e of the target area is used as the objective function of the simulated annealing algorithm, and the optimal solution of the objective function is found through the algorithm, even if the value of e is the smallest, so as to obtain the optimal AP placement position, including The following steps:

11a. Initialize the parameters involved in the simulated annealing algorithm, that is, set the initial temperature T ₀ , the temperature drop rate λ, the number of iterations L, and the temperature lower limit T _min ;

11b. Initialize l=1, T=T ₀ , set the initial solution state w, and calculate the value f(w) of the objective function in the current solution state;

11c. Randomly replace the AP position coordinates to be selected with the AP position coordinates in the initial solution to obtain a new solution w ^* , and calculate f(w ^* );

11d. Calculate Δf, Δf=f(w ^* )-f(w);

11e. If Δf<0, accept w ^* as the current solution; otherwise, calculate And generate a random number between 0 and 1, judge Whether it is greater than the random number, if yes, then accept w ^* as the current solution, and then enter step 11f; if not, then directly enter step 11f;

11f, judging whether the algorithm has reached the number of iterations L, if yes, enter step 11g; if not, then l=l+1, enter step 11c;

11g. Judging whether the current temperature T of the algorithm is greater than the temperature lower limit T _min , if yes, go to step 11h; if not, go to step 12;

11h. Let the current temperature T=T×λ, the number of iterations l=1, and go to step 11c.

Beneficial effect

The present invention considers the correlation between APs and combines the lognormal path loss model to describe the RSS distribution at the reference point more accurately. On this basis, combined with the prior probability of the position of the reference point, the weighted probability of the reference point is calculated, so as to obtain the average positioning accuracy of each reference point, and finally obtain the average positioning accuracy of the target area; and use it as the target of the simulated annealing algorithm function to obtain the most reasonable AP location to achieve AP location optimization, and while reasonably arranging AP locations, high indoor positioning accuracy is ensured. The present invention can be applied to the radio communication network environment, and the method provided can reasonably select the AP position.

Description of drawings

Fig. 1 is the flowchart of step 1 to step 12 among the present invention;

Fig. 2 is the selected target area and reference point position of the present invention;

Figure 3 is the path simulation result;

Fig. 4 is sub-area division result;

Figure 5a is a boxplot of the positioning accuracy of all reference points in the target area when a single AP is placed in five positions in the target area;

Figure 5b is a boxplot of the positioning accuracy of all reference points in the target area when two APs are placed at 5 positions in the target area;

Figure 6a is the optimization result of the simulated annealing algorithm in the case of single AP;

Figure 6b shows the optimization results of the simulated annealing algorithm in the case of two APs.

specific implementation plan

The present invention will be further described below in conjunction with accompanying drawing.

A WLAN positioning networking method based on signal statistical distribution provided by the present invention comprises the following steps:

Step 1. Select the target area to be located.

Step 2: Determine the positions of all WLAN access points in the target area, and arrange m APs in the target area, that is, AP ₁ , AP ₂ , . . . , AP _m .

Step 3: Determine the positions of all reference points in the target area, and select n RPs in the target area, namely RP ₁ , RP ₂ , . . . , RP _n .

Step 4. Calculate the Euclidean distance between the i-th RP and the j-th AP physical space Wherein, (x _i , yi) is the position coordinate of the i-th RP, and (x _j , y _j ) is the position coordinate of the j-th AP.

Step 5. Make the RSS obey the Gaussian distribution, and consider the correlation between each AP, and calculate the probability density function of the RSS measured at the i-th RP, which specifically includes the following steps:

5a. Assuming that the propagation model of the signal conforms to the log-normal path loss model, the expression of the signal strength value P _ij received by the i-th reference point from the j-th access point is:

Among them, d ₀ is the reference distance, take d ₀ =1m; P(d ₀ ) is the power at the reference point; γ is the path loss index, which reflects the relationship between the loss of signal strength and the propagation distance; d _ij is the The Euclidean distance from the i reference point to the jth AP, ζ is the random noise that obeys the Gaussian distribution N(u,σ ² ).

5b. Collect 10,000 RSS values from m APs at the _i -th reference point, a total of 10,000×m RSS values, expressed as:

5c, using the matrix R _i obtained in step 5b to calculate the covariance matrix C is:

Among them, c _jj (1≤j≤m) is the variance of the RSS value from the jth AP, and c _jk (1≤k≤m, j≠k) is the RSS value from the jth AP and the kth AP covariance of .

5d. Define X=(x ₁ ,x ₂ ,...,x _m ) ^T as the RSS vector measured at the i-th RP, where x _i (1≤i≤m) is the RSS vector from the j-th AP RSS value, calculate the probability density function f _i (X) of the RSS measured at the i-th RP as:

Wherein, U _i =(μ ₁ ,μ ₂ ,...,μ _m ) ^T is the mean vector of the RSS values received at the i-th RP from m APs.

Step 6. Calculate the probability value p _i1 of the qth RSS vector R _q =[r ₁ r ₂ ... r _m ] ^T (1≤q≤Q) appearing at the i-th reference point, where r _i (1≤i≤ m) is the RSS value from the jth AP received by the ith reference point, and Q is the number of all possible RSS vectors; the specific steps are as follows:

6a. Determine the integral neighborhood δ of the RSS vector (δ>0);

6b. The probability of the RSS vector appearing at the i-th RP is:

Step 7: Calculating the prior probability p _i2 of the position of the i-th reference point, the specific steps are as follows:

7a. Set the physical environment around the furniture as the area of interest, and the obstacle as the unreachable area; convert the map of the target area into an image with a pixel width of η; initialize k=1, and k is the count.

7b. Set the starting point A and the ending point B; set A as the grid T to be processed.

7c. Store T in the open list, which is a list of check boxes.

7d. Delete T from the open list, and add T to the closed list. The closed list stores the squares that do not need to be checked again; for the reachable adjacent squares of T, check whether it is already in the open list, and if so, enter Step 7e; if not, go to step 7f.

7e. Calculate the Euclidean distance d from T to its adjacent square, the Euclidean distance G from T to the starting point A, and the Euclidean distance G′ from the adjacent square to the starting point A. If G+d<G′, set T to is the parent square of the adjacent square, and the value of the cost function is F=G+H+d, and H is the Manhattan distance from the adjacent square to the end point B.

7f. Put the adjacent squares of T into the open list, set T as its parent square; calculate the cost function F=G+H, where G is the Euclidean distance from the adjacent square to the starting point A.

7g. Select the square C with the smallest cost function value F from the open list, store C in the path trace _k , and judge whether C is equal to the end point B. If so, go to step 7h, if not, set C as the square to be processed T, go to step 7c.

7h. Obtain the simulation path trace _k , judge whether k is less than or equal to the number of paths K, if so, k=k+1, return to step 7b; if not, the path simulation ends, and K simulation paths are obtained.

7i. Divide the target area into five sub-areas; observe the K paths obtained by the simulation, and count the prior probability of each sub-area; assuming that the reference point is equally likely to appear in each sub-area, then according to the priori of the sub-area to which the reference point belongs Probability, to obtain the prior probability p _i2 of the position of each reference point.

Step 8: Calculate the weighted probability p _i =p _i1 ×p _i2 of the RSS vector R _q appearing at the ith RP.

Step 9, calculate the average positioning accuracy of the i-th reference point, the specific steps are as follows:

9a. Calculate the weighted probability p ₁ , p ₂ ,...p _n of the RSS vector R _q appearing at all reference points, and find out the maximum weighted probability of its appearance:

p _max = max(p ₁ ,p ₂ ,...,p _n );

Record the physical coordinates of the reference point corresponding to the maximum weighted probability p _max .

9b. Calculate the Euclidean distance from the i-th reference point to the point with the highest weighted probability of the RSS vector R _q appearing.

9c. Take different RSS vectors, repeat step six, step seven and step eight in turn, and obtain the weighted probability that all possible RSS vectors appear at the i-th reference point, and the weighted probability vector P _i is:

Among them, Q is the number of all possible RSS vectors; is the weighted probability that the qth RSS vector appears at the ith reference point.

9d, repeating steps 9a and 9b, under all possible RSS value conditions, calculate the distance vector from the i-th reference point to the point with the largest weighted probability of RSS occurrence:

in, is the Euclidean distance from the i-th reference point to the point with the highest weighted probability of the q-th RSS vector appearing.

9e, utilize the weighted probability vector and the distance vector that step 9c and step 9d obtain, obtain the average positioning accuracy of the i reference point as:

e _i =P _i ×D _i .

Step 10. Calculate the average positioning accuracy of the target area:

Step 11. Use the average positioning accuracy e of the target area as the objective function of the simulated annealing algorithm, and use this algorithm to find the optimal solution of the objective function, even if the value of e is the smallest, so as to obtain the optimal AP placement position. The objective function is expressed as :

Among them, w is the coordinates of the AP position, and the specific steps of the algorithm are as follows:

11a. Initialize the parameters involved in the simulated annealing algorithm, that is, set the initial temperature T ₀ , the temperature drop rate λ, the number of iterations L, and the temperature lower limit T _min .

11b. Initialize l=1, T=T ₀ , set the initial solution state w, and calculate the value f(w) of the objective function in the current solution state.

11c. Randomly replace the position coordinates of the AP to be selected with the position coordinates of a certain AP in the initial solution to obtain a new solution w ^* and calculate f(w ^* ).

11d. Calculate Δf, Δf=f(w ^* )-f(w);

11e. If Δf<0, accept w ^* as the current solution; otherwise, calculate And generate a random number between 0 and 1, judge Whether it is greater than the random number, if yes, then accept w ^* as the current solution, and then enter step 11f; if not, directly enter step 11f.

11f. Judging whether the algorithm has reached the number of iterations L, if yes, go to step 11g; if not, then l=l+1, go to step 11c.

11g. Judging whether the current temperature T of the algorithm is greater than the temperature lower limit T _min , if yes, go to step 11h; otherwise, go to step 12.

11h. Let the current temperature T=T×λ, the number of iterations l=1, and go to step 11c.

Step 12, the algorithm ends, and the optimal AP position coordinates are returned.

Claims (3)

1. A WLAN positioning networking method based on signal statistical distribution is characterized in that: the method comprises the following steps:

step one, selecting a target area to be positioned;

step two, determining the positions of all WLAN access points in the target area, and arranging m APs (access points), namely APs (access points) in the target area₁，AP₂，...，AP_m；

Step three, determining the positions of all reference points in the target area, and selecting n RPs (namely RPs) in the target area₁，RP₂，...，RP_n；

Step four, calculating the Euclidean distance between the ith RP and the jth AP physical spaceWherein (x)_i,y_i) Is the location coordinate of the ith RP, (x)_j,y_j) Is the position coordinate of the jth AP;

step five, enabling the RSS to obey Gaussian distribution, considering the correlation among the APs, and calculating the probability density function of the RSS measured at the ith RP;

step six, calculating the q-th RSS vector R_q＝[r₁r₂… r_m]^T(1. ltoreq. Q. ltoreq. Q) probability value p of occurrence at the ith reference point_i1Wherein r is_i(i is more than or equal to 1 and less than or equal to m) is the RSS value from the jth AP received by the ith reference point, and Q is the number of all possible RSS vectors;

step seven, calculating the position prior probability p of the ith reference point_i2；

Step eight, calculating RSS vector R_qWeighted probability p of occurrence at ith RP_i＝p_i1×p_i2；

Calculating the average positioning precision of the ith reference point;

step ten, calculating the average positioning precision of the target area;

step eleven, taking the average positioning precision e of the target area as a target function of a simulated annealing algorithm, and searching the optimal solution of the target function through the algorithm, namely, the value e is minimum, so as to obtain the optimal AP placing position;

and step twelve, finishing the algorithm and returning to the optimal AP position coordinate.

2. The method of claim 1, wherein the signal statistics distribution-based WLAN positioning networking method comprises: in step seven, calculating the position prior probability p of the ith reference point_i2The method comprises the following steps:

7a, setting a physical environment around furniture as an interesting area and setting an obstacle as an inaccessible area, converting a map of a target area into an image with the pixel width of η, and initializing k to be 1, wherein k is the number;

7B, setting a starting point A and an end point B; setting A as a square T to be processed;

7c, storing the T into an opening list, wherein the opening list is a check list to be checked;

7d, deleting T from the opening list, adding T into the closing list, wherein the closing list stores squares which do not need to be checked again; checking whether the reachable adjacent square grids of the T are in the opening list or not, and if so, entering a step 7 e; if not, entering step 7 f;

7e, calculating the Euclidean distance d from the adjacent square grid to the adjacent square grid, the Euclidean distance G from the T to the starting point A, the Euclidean distance G 'from the adjacent square grid to the starting point A, and if G + d is less than G', setting the T as the parent square grid of the adjacent square grid, wherein the value of the cost function is F ═ G + H + d, and H is the Manhattan distance from the adjacent square grid to the end point B;

7f, putting the adjacent grids of the T into an opening list, and setting the T as a father grid of the T; calculating a cost function F ═ G + H, wherein G is the Euclidean distance from the adjacent square to the starting point A;

7g, selecting a square grid C which enables the cost function value F to be minimum from the opening list, and storing the C into the path trace_kJudging whether C is equal to the end point B, if so, entering a step 7h, otherwise, setting C as a square T to be processed, and entering a step 7C;

7h, obtaining the trace of the simulation path_kJudging whether K is less than or equal to the number K of the paths, if so, setting K as K +1, and returning to the step 7 b; if not, ending the path simulation to obtain K simulation paths;

7i, dividing the target area into five sub-areas; observing K paths obtained by simulation, and counting the position prior probability of each subregion; assuming that the reference points in each subregion appear equally, the position prior probability p of each reference point is obtained according to the prior probability of the subregion to which the reference point belongs_i2。

3. The method of claim 1, wherein the signal statistics distribution-based WLAN positioning networking method comprises: in the ninth step, calculating the average positioning accuracy of each reference point according to the weighted probability of the RSS value at each reference point, comprising the following steps:

9a, calculating RSS vector R_qWeighted probability p of occurrence at all reference points₁,p₂,...p_nAnd find the maximum weighted probability of its occurrence:

p_max＝max(p₁,p₂,...,p_n)；

record the maximum weighted probability p_maxThe physical coordinates of the corresponding reference points;

9b, calculating the RSS vector R from the ith reference point_qThe Euclidean distance of the point with the maximum weighted probability;

9c, taking different RSS vectors, and repeating the step six, the step seven and the step eight in sequence to obtain the weighted probability of all possible RSS vectors appearing at the ith reference point, wherein the weighted probability vector P_iComprises the following steps:

wherein Q is the number of all possible RSS vectors;a weighted probability of occurrence of the qth RSS vector at the ith reference point;

9d, repeating the steps 9a and 9b, and calculating the distance vector from the ith reference point to the point with the maximum RSS occurrence weighting probability under all possible RSS value-taking conditions:

wherein,the Euclidean distance from the ith reference point to the point with the maximum weighting probability of the appearance of the qth RSS vector is calculated;

9e, obtaining the average positioning accuracy of the ith reference point by using the weighted probability vector and the distance vector obtained in the steps 9c and 9d as follows:

e_i＝P_i×D_i。