CN102547980B - Positioning smooth stabilization mechanism based on generation tree - Google Patents

Abstract

The invention discloses a positioning smooth and stable mechanism based on spanning tree. During the positioning process, the system calculates the positioning position and display position for each mobile node. All possible positioning positions in the application environment form a connected graph. The system calculates the positioning position of the mobile node according to the received signal strength of the mobile node, and takes the display position of the mobile node at the last moment as the root and uses the breadth-first search method to construct the connected graph. tree, and then determine the nearest common ancestor node of the latest K+1 positioning positions, and set the positioning position of the ancestor node as the current display position, thereby realizing the smooth display of the positioning track. The present invention determines the final display position by comparing the recent positioning results, which can effectively reduce the adverse effects of the instability of the received signal strength itself on the positioning results, improve the positioning accuracy, and greatly reduce the common jumping phenomenon in the positioning process .

Description

Smooth and stable positioning mechanism based on spanning tree

technical field

The invention relates to a node positioning method of a wireless network, in particular to a node track smoothing and stabilizing processing method in an indoor environment based on a spanning tree for a wireless network.

Background technique

In a wireless WIFI network, there are usually a certain number of WIFI access points (Access Points, AP hotspots). Since these AP hotspots are immovable, these AP hotspots are usually regarded as anchor nodes that know their physical location information ( i.e. fixed nodes). In order to locate personnel, each person is required to carry a tag, so this type of tag to be located can be called a mobile tag. In order to reduce system cost, the mobile tag only has the ability to periodically send beacon detection frames, but does not have the function of receiving data. When the AP hotspot receives the detection frame of the mobile tag, it will calculate the corresponding received signal strength indicator (Received Signal Strength Indicator, RSSI) information, and assemble multiple received RSSI information into a data packet through wireless multi-hop routing or The wired network sends to the network server, and the network server calculates the current real-time position of each moving object.

In order to calculate the specific location of the mobile tag, the literature [BAHL P, PADMANABHAN V. "RADAR: An in-building RF-based user location and tracking system", Infocom, 2000] proposes to pre-select some information collection points in the coverage area , and then collect the RSSI values corresponding to the detection frames received by each AP when the mobile tags are at these collection points, and record them in the form of (x, y, RSSI ₁ , RSSI ₂ ,..., RSSI _n ), where x, y is the abscissa and ordinate position of the sampling point, and RSSI _i (1≤i≤n) is the RSSI value relative to AP _i when the mobile tag is located at the sampling point. In this way, RADAR obtains a distribution map of RSSI values in the positioning area. In the positioning process, if the RSSI value of the mobile tag relative to each AP node is (RSSI′ ₁ , RSSI′ ₂ , ..., RSSI′ _n ), RADAR will search the pre-recorded RSSI distribution map in the background to select the most in line with the current The position of the information is used as the coordinates of the mobile tag, that is, the value of formula (1) is calculated for all points in the RSSI distribution diagram.

$\sqrt{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; RSSI</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; RSSI</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

The coordinates of the points in the RSSI distribution map corresponding to the smallest of these values are the final positioning results.

However, in the actual environment, the external environment has a greater impact on the RSSI value, that is, the RSSI will change significantly with time and changes in the external environment (such as weather factors, the gap between sunny and cloudy days is large), thus The RSSI value is extremely unstable, which often leads to wrong positioning results. Due to the uncertainty of the results of the positioning algorithm, if the final positioning result is displayed without any processing according to the positioning method of the RADAR system, it will cause continuous jumping of the mobile tag trajectory. In addition, the general smoothing mechanism requires that the location be determined at a certain location several times in a row, but in the actual location application environment based on RSSI, the probability of being positioned at the same location several times in a row is low, thus This causes disadvantages such as non-mobility of mobile nodes and large positioning delay, which greatly reduces the performance of the positioning system.

Contents of the invention

The purpose of the present invention is to provide a smooth and stable positioning mechanism based on spanning tree, which can effectively reduce the impact of unstable RSSI values on positioning results, improve positioning accuracy, and effectively ensure the correctness and continuity of moving tracks.

In order to solve these problems in the prior art, the technical solution provided by the invention is:

A smooth and stable positioning mechanism based on spanning tree. During the positioning process, the system calculates the positioning position and display position for each mobile node. In the application environment, all possible positioning positions form a connected graph. Calculate the positioning position of the mobile node based on the received signal strength of the node, and use the breadth-first search method to construct a spanning tree for the connected graph with the display position of the mobile node at the last moment as the root, and then determine the nearest common ancestor of the latest K+1 positioning positions node, and set the positioning position of the ancestor node as the current display position, so as to realize the smooth display of the positioning track.

For the above technical solution, we have a further detailed solution. As an optimization, by smoothing the latest K+1 positioning position, taking the display position of the mobile node at the previous moment as the root, a spanning tree is established through breadth-first search, and then K is determined. The nearest common ancestor node of +1 positioning position, the position of this common ancestor node is the display position at the current time t, and the specific method includes the following steps:

Step 1: In the actual positioning environment, select some fixed points (sampling points) as possible positioning results, and connect lines between these points to represent the movement of the mobile node between these positions, so as to prevent the node from passing through the wall;

Step 2: Use any positioning algorithm to determine the positioning position of the moving object. Assume that the positioning position of the moving object at time t is A _t , and the display position at time t is S _t . In the connected graph composed of all discrete positioning positions, Take S _t-1 as the root, and use the breadth-first search method to construct a local spanning tree on the connected graph, which contains at least all the latest K+1 positioning positions;

Step 3: Find the nearest common ancestor node of these K+1 positioning positions on the spanning tree, assuming that the common ancestor node is B, and finally record the positioning position B as the display position of the node at time t, and set S _t =B.

Further, the positioning algorithm described in step 2 above may use any discrete positioning algorithm, including other discrete positioning algorithms not based on received signal strength.

Furthermore, the positioning smooth and stable mechanism is determined based on the common analysis of the positioning positions at K+1 moments of t, t-1, t-2, ..., t-(K-1), t-K of the positioning algorithm The final positioning result.

Further, the local spanning tree is established using the breadth-first search method described in the above step 2, the local spanning tree contains the latest K+1 positioning positions, and its height only needs to be enough to contain the latest K+1 positioning positions, that is, Yes (this can reduce the number of nodes to search, thereby improving the efficiency of the smoothing mechanism).

As an optimization, the S _t-1 to B is the longest common path from S _t-1 to K+1 positioning positions, that is, the mechanism locates the display position at time t at the farthest reliable position.

Compared with the scheme in the prior art, the advantages of the present invention are:

1. The positioning smooth and stable mechanism based on spanning tree provided by the present invention, it determines the final display position by comparing the recent positioning results, which can effectively reduce the instability of the received signal strength indicator (RSSI) value itself to the positioning results Adverse effects, and then effectively eliminate individual positioning errors, improve positioning accuracy, and greatly reduce the common jumping phenomenon in the positioning process;

2. The present invention ensures the correctness and continuity of the moving track for locating the mobile node by positioning the final display position at the farthest reliable position;

3. Compared with other stable mechanisms that require several consecutive positionings at the same place to determine the position as the final display position, the present invention can effectively use the information of each positioning result and improve the sensitivity of label movement. And reduce the delay of the system.

Description of drawings

The present invention will be further described below in conjunction with accompanying drawing and embodiment:

Fig. 1 is the structural arrangement drawing of the embodiment of the present invention;

Fig. 2 is a smooth demonstration diagram of a positioning result according to an embodiment of the present invention;

Fig. 3 is a smooth demonstration diagram of another positioning result according to the embodiment of the present invention.

Detailed ways

The above solution will be further described below in conjunction with specific embodiments. It should be understood that these examples are used to illustrate the present invention and not to limit the scope of the present invention. The implementation conditions used in the examples can be further adjusted according to the conditions of specific manufacturers, and the implementation conditions not indicated are usually the conditions in routine experiments.

Example:

The positioning smooth and stable mechanism based on spanning tree described in this implementation, in the positioning process, the system calculates the positioning position and display position for each mobile node, and all possible positioning positions in the application environment form a connected graph. The middle system calculates the positioning position of the mobile node according to the received signal strength of the mobile node, and uses the breadth-first search method to construct a spanning tree for the connected graph with the display position of the mobile node at the last moment as the root, and then determines the latest public location of the latest positioning position. An ancestor node, and set the positioning position of the ancestor node as the current display position, so as to realize the smooth display of the positioning track.

As shown in Figure 1, we first placed 12 AP devices in the flat floor of the building as shown in Figure 1, and then selected 13 sampling points (indicated by circles in the figure) in the corridors and rooms on the fifth floor to collect RSSI signal, the connecting lines in the figure indicate that the positioning label will only move on the track formed by these connecting lines. After a period of sampling preparation (30 minutes in this embodiment), we calculated the average value of the RSSI signal strength of each sampling point relative to each AP node at the 13 sampling points.

In the actual positioning, all mobile tags send out beacon frames at a certain period (actually set to 1 second), and because the mobile tags only have the function of sending packets but not the functions of receiving and unpacking, the cost price is very cheap. When the AP node in the network receives the beacon frame from the label, it will calculate the corresponding RSSI value, add a local AP timestamp to the RSSI value, and then store the RSSI value locally. In addition, the AP node also sends a data packet to the network server at a certain period, and the data packet includes RSSI information of all tags received in this period and their corresponding time stamps.

When the network server receives the data packet from the AP, it will unpack the information, and we believe that the packet sending time of the AP is the same as the receiving time of the network server, that is, we ignore the sending time of the data packet. Therefore, when decoding data packets, we will correct the timestamps of each AP to the local time of the network server, so as to achieve relative synchronization among APs.

When positioning the mobile tag, at the current time t, we will compare the received real-time RSSI value of the mobile tag (received between time t-1 and time t) with the RSSI values at 15 sampling points. Compare and determine the sampling point with the smallest Euclidean distance as the positioning position of the mobile tag.

Subsequently, the smoothing mechanism will perform trajectory smoothing analysis and processing on the positioning position at time t and the k+1 positioning results of the previous k positioning results at the current time to determine the final positioning result. If the current positioning is the first time, then directly output the positioning result as the final display result; otherwise, if the number of positioning times is less than k+1 (including the current one), then maintain the display result of the mobile label unchanged; if If the number of times of positioning is greater than k+1 (including the current time), smoothing processing is performed. Set k to 4 in the actual system.

The actual positioning smoothing process is as follows. The current mobile label display position is at sampling point 2, and the positioning positions at time t and the previous 4 times are shown in the following table:

moment t t-1 t-2 t-3 t-4 Location Sampling point 6 Sampling point 5 Sampling point 9 Sampling point 6 Sampling point 5

Then build a breadth-first search local spanning tree in Figure 1. As shown in Figure 2: the nearest common ancestor node of these five positioning results in the graph is sampling point 5, so the display position at time t is set at sampling point 5. On the other hand, the paths from sampling point 2 to the five positioning results are respectively 2-5-6, 2-5, 2-5-9, 2-5-6, 2-5, so the common The trajectory is sampling point 2-5, so the output of sampling point 2-5 is the movement trajectory of the label, and sampling point 5 is the display at the final time t.

Another positioning smoothing process in practice is as follows. The current mobile label display position is at sampling point 2, and the positioning positions at time t and the previous 4 times are shown in the following table:

moment t t-1 t-2 t-3 t-4 Location Sampling point 1 Sampling point 2 Sampling point 3 Sampling point 1 Sampling point 5

Then build a breadth-first search local spanning tree in Figure 1. As shown in Figure 3: the nearest common ancestor node of these five positioning results in the graph is sampling point 2, so the display position at time t is set at sampling point 2, that is, the mobile label does not move. On the other hand, the paths from sampling point 2 to the five positioning results are respectively 2-1, 2-5, 2, 2-3, 2-1, 2-5, so the common trajectory shared by the five times is empty, so The label does not move, and sample point 2 is the final display at time t.

Subsequently, the mobile label will move on the display interface with a smoothed motion track.

The above examples are only to illustrate the technical conception and characteristics of the present invention, and its purpose is to allow people familiar with this technology to understand the content of the present invention and implement it accordingly, and cannot limit the protection scope of the present invention. All equivalent changes or modifications made according to the spirit of the present invention shall fall within the protection scope of the present invention.

Claims (5)

1. positioning smooth antihunt means based on spanning tree, it is characterized in that, in position fixing process, system is each mobile node equal compute location position and display position, in applied environment, all position locations form connected graph, system is calculated the position location of mobile node according to the received signal strength of mobile node, and the display position constantly of take on this mobile node is connected graph structure spanning tree as root adopts BFS method, and then the nearest public ancestor node of definite up-to-date K+1 position location, and the position location of this ancestor node is set to current display position, and then realize the flow display of positioning track,

By smoothing processing is carried out in a up-to-date K+1 position location, the root that is shown as with a moment on mobile node is set up spanning tree, and then the nearest public ancestor node of definite K+1 position location, the position of this public ancestor node is set to current t display position constantly, and concrete grammar comprises the following steps:

Step 1: under actual location environment, select some fixing points as positioning result, and these point between line to represent the movement of mobile node between these positions, thereby prevent that node is through walls;

Step 2: determine the position location of mobile object by any one location algorithm, mobile object is A in t position location constantly _t, t display position is constantly S _t, in the connected graph forming in all discrete position locations, with S _t-1for root, adopt BFS method on connected graph, to construct a local spanning tree, this spanning tree at least comprises all up-to-date K+1 position locations;

Step 3: find the nearest public ancestor node of this K+1 position location in spanning tree, this nearest public ancestor node is B, position location B is designated as node t display position constantly the most at last, and S is set _t=B.

2. the positioning smooth antihunt means based on spanning tree according to claim 1, is characterized in that, the location algorithm described in step 2 adopts discrete location algorithm arbitrarily, comprise other not discrete location algorithms based on received signal strength.

3. positioning smooth antihunt means based on spanning tree according to claim 1 and 2, it is characterized in that, described positioning smooth antihunt means are the t based on location algorithm, t-1, t-2,, t-(K-1), t-K is total to the common analysis of K+1 position location constantly and determines final positioning result.

4. the positioning smooth antihunt means based on spanning tree according to claim 1, is characterized in that, the employing BFS method described in step 2 is set up local spanning tree, and described local spanning tree comprises a up-to-date K+1 position location.

5. the positioning smooth antihunt means based on spanning tree according to claim 1, is characterized in that described S _t-1to B, be S _t-1to the longest common path of K+1 position location, the method is positioned at securing position farthest by t display position constantly.