CN101877820A - Multiple Deviceless Object Tracking Method Based on Dynamic Clustering Algorithm for Wireless Networks - Google Patents

Abstract

The invention relates to a method for simultaneously tracking multiple unequipped objects based on a dynamic clustering algorithm by using wireless network technology. Arrange some wireless sensor nodes communicating with each other on the indoor ceiling, and each node acts as a radio frequency transmitter and a radio frequency receiver at the same time. When there are no moving objects, the signal strength received between them is stable. Otherwise, dynamic clustering is performed according to the different effects of multiple non-device target objects on the received signal strength of different nodes. That is, when there is an influence, the corresponding cluster will be generated, and the node with the highest remaining energy in the cluster will be selected as the cluster head. Then, the cluster head of each cluster collects the changes of the signal strength among the nodes in the cluster and uses the probability coverage algorithm to calculate the position of the objects in the cluster.

Description

Multiple Deviceless Object Tracking Method Based on Dynamic Clustering Algorithm for Wireless Networks

technical field

The invention relates to a method for realizing tracking of multiple non-device objects by using dynamic clustering technology based on wireless network technology. The invention solves the difficult problem that multiple non-equipment objects cannot be tracked in the traditional wireless network field, and is a low-cost and high-efficiency tracking method for multiple non-equipment objects. The invention belongs to the field of object location tracking and wireless communication.

Background technique

Multi-object tracking technology has always been a research hotspot, and has many practical application scenarios, such as vehicle tracking, battlefield detection, animal habitat behavior monitoring, and patient detection in hospitals, etc. GPS is a highly accurate tracking technology, but it can only be used outdoors, where satellite signals are blocked. Locating indoor moving objects is more complicated. Laser positioning technology is famous for its accuracy in distance measurement, but its related equipment is very expensive, and it is more suitable for outdoor environments. At present, the technologies used for object tracking at home and abroad are divided into two categories, one is based on radio frequency technology, and the other is based on non-radio frequency technology. Non-RF technologies mainly include video technology, infrared technology, pressure technology, and ultrasonic technology. Video technology uses multiple cameras to collect image information, and then captures objects through image processing algorithms. Such techniques are usually expensive and cannot be used in dark environments. Because of its limited range, infrared technology requires very careful and dense arrangement to locate objects, and if it is not deployed carefully, it is still easy to have loopholes. Pressure technology uses acceleration and air pressure sensors placed on the floor to detect whether someone's footprints pass through its detection range. This technology also requires a very dense node arrangement to effectively locate within the required range, and the cost is relatively high. Ultrasonic technology generally obtains position information through the ultrasonic time-of-flight method (Time-of-Flight). This technology always requires the tracked object to carry a sending or receiving device. For example, the Bat ultrasonic system requires the tracked object to carry a Bat (transmission device) periodically sends ultrasonic pulses, or such as MOCUS can only test the number of objects passing through a fixed area. In addition, like the Cricket positioning system, by combining ultrasonic and radio frequency, the time difference between the two receiving signals is used to measure the distance. This method also requires the tracked object to carry a relevant signal receiver.

Since various wireless devices have been widely used in daily work and life, radio frequency technology is known for its low cost. Related positioning technologies include 802.11, RFID (RFID) and wireless sensor network (WSN). Wireless sensor network is a network composed of a large number of cheap wireless sensors, which can collaboratively monitor, perceive and collect information of various environments or monitoring objects in the network coverage area in real time, and process it. The processed information passes through It is sent wirelessly and transmitted to the observer in an ad hoc multi-hop network. However, the existing object tracking methods of these technologies all require the tracked object to carry a wireless transceiver, and then obtain the position of the object through the size of the wireless signal strength (RSS) at the receiving end or by adding some auxiliary methods. This condition is obviously not satisfied in some environments and applications, such as security or anti-theft departments, some malicious break-ins or attackers will not carry similar devices to assist in tracking.

After searching, it is found that the current methods of object tracking without equipment, such as image technology, infrared technology, pressure technology, ultrasonic technology, etc., have their own limitations. They have high cost, difficult layout, or cannot be applied to dark scenes, etc. defect. Therefore, it is difficult for them to be put into practical applications on a large scale, which greatly limits the application prospects of object tracking technology in practice.

The present invention fills up this technical gap, and will effectively solve various problems caused by the above-mentioned technology used in tracking objects without equipment, especially the problem of tracking multiple objects without equipment. The present invention uses wireless signals (such as 802.11 or zigbee, etc.) as the basic input source to track objects, and uses the interference of tracked objects to the environment, especially the interference to wireless signals, to perform positioning and tracking in the wireless network. Since the current wireless signal is an open and almost free resource, our technology will obtain a relatively high accuracy while retaining the low-cost advantage of the wireless signal, thereby providing a low-cost, high-efficiency, covert and non-intrusive Real-time object positioning and tracking technology.

In addition, the dynamic clustering algorithm used in the wireless network to distinguish multiple non-device objects is very different from the traditional clustering method. Traditional approaches fail to distinguish between multiple unequipped objects. The traditional clustering algorithm is to divide the nodes in the network, and divide the nodes with close physical locations into a group, and there is usually a cluster head in each group. The member nodes in the cluster send data to the cluster head without going back to the base station through a long path. The size of the cluster is determined by the cluster radius, which is the maximum number of hops from the cluster members to the cluster head. The simplest clustering is one-hop (1-hop) clustering, and there is a direct link connection between the nodes in the cluster and the cluster head. The cluster head further processes the collected data in the cluster, removes data redundancy, and sends the required data back to the base station. The amount of data transmission can be greatly reduced and energy efficiency can be improved. Moreover, due to the reduction of data transmission requests, wireless channel resources can be used more effectively, and the degree of transmission conflict is reduced, thereby improving the quality of data transmission. The traditional clustering algorithm in the wireless network adopts a fixed clustering method, that is, the size of the cluster is basically unchanged.

However, in the distributed dynamic clustering algorithm (Dynamic Clustering) adopted by the present invention, the existence and size of clusters will change with time and changes in required characteristics. Using the distributed dynamic clustering algorithm can effectively separate the areas affected by the signal strength of multiple objects, that is, as long as the distance between multiple objects is not very close, we can reduce the transmission power of the nodes, and then Effective clustering is performed according to the different effects of multiple non-device target objects on the received signal strength of different nodes.

Contents of the invention

The technical problem to be solved by the present invention is that traditional wireless network-based object tracking requires the tracked object to carry a wireless node to assist in tracking. How to realize the high-precision, high-accuracy, high-real-time, and low-cost simultaneous tracking of multiple unequipped objects under a large-scale wireless network is an urgent problem to be solved in the field of unequipped object tracking.

The technical scheme adopted for realizing the above purpose is:

The invention first establishes a model based on the change of the location and signal strength of the target object without equipment, and then introduces methods such as networking assistance and transmission power adjustment, and adopts a distributed dynamic clustering algorithm (Dynamic Clustering) and dynamically adjusts nodes. The method of sending power. In this way, multiple unequipped objects can be tracked at the same time, and the tracking accuracy can be guaranteed.

First of all, building a model refers to modeling the impact of only a pair of wireless node signal strength changes (Dynamic of Radio Signal Strength) for different positions of non-device target objects. In order to better meet the practical application, the pair of wireless nodes are placed on the indoor ceiling. Detect and model the relationship between the two based on the position of the tracked object on the ground. Common models are based only on the Propagation Model. That is, when the distance between the RF signal receiving end and the RF signal sending end is getting farther and farther away, generally speaking, the received signal strength will gradually decrease. This model only considers the relationship between the distance of the object from a single wireless node and the received signal strength, and does not consider the influence of the object on the signal strength change at different locations. The present invention is the first effort to build such a model. Our research found that if there is no moving object in the environment, the change of signal strength is very small, almost negligible. However, when the object moves, it will affect the signal strength. Therefore, the present invention adopts a certain wireless node layout and networking technology, utilizes the research model that moving objects will cause changes in the received signal strength of different communication nodes, and then analyzes the single non-device target according to the corresponding geometric information and signal strength changes of these nodes. Objects are tracked. Here we use the broadcast mode, that is, each wireless node is the sending end to send signals to other nodes, and also the receiving end to receive signals from other nodes. For each pair of wireless nodes that communicate with each other, according to the change value of the signal strength generated by it, the possible range of the object is inferred according to the model, then for many nodes that communicate with each other, there are many estimated areas of such objects, and we consider the overlapping area The most places are most likely where the object exists.

Secondly, dynamic clustering means that the existence and size of clusters will change with the change of time and required characteristics, so it can effectively separate the areas affected by the signal strength of multiple objects, that is, as long as multiple The distance between objects is not very close, we can effectively cluster by reducing the node transmission power, and then according to the different effects of multiple non-device target objects on the received signal strength of different nodes. That is, when there is an influence, the corresponding cluster will be generated, and the node with the highest remaining energy in the cluster will be selected as the cluster head. Then, the cluster head of each cluster collects the change of the signal strength among the nodes in the cluster and calculates the position of the objects in the cluster, and obtains an effective solution for tracking multiple target objects without equipment. In order to reduce the size of the cluster radius so that the system can locate multiple non-device target objects in a short distance, we use one-hop clustering.

After the clustering is successful, in each clustering, the cluster head processes the signal strength change information in the cluster. The invention sets each cluster head to use the optimal probability cover algorithm (Probabilistic Cover), so that each cluster head is in this cluster. The cluster can accurately calculate the position of the target object without equipment in the cluster. The optimal probabilistic covering algorithm is a major improvement based on the optimal covering algorithm. It introduces a probability model. For each pair of nodes communicating with each other, if the signal strength of an unequipped target object changes, the possibility of the object being within its calculation range is estimated in a probabilistic manner. This leads to a more accurate algorithm.

The present invention utilizes the wireless network to track objects without equipment, and the beneficial effects that can be achieved are as follows:

Enables simultaneous tracking of multiple device-free objects. The present invention solves the problem that multiple objects without devices cannot be tracked simultaneously in the traditional wireless network;

low cost. Radio frequency technology is known for its low cost, traditional deviceless tracking technology is expensive equipment, or requires extremely sophisticated arrangements. The present invention is simple in arrangement, easy to use, and can be applied in dark environment;

High tracking accuracy. The present invention can realize the object tracking accuracy without equipment to reach about one meter;

High real-time performance. The present invention can track the existing position of an object without equipment within one second;

Strong scalability. The present invention can make the tracking system have strong expansibility, because the arrangement is simple, and it is easy to be applied to the tracking system in a large area.

Description of drawings

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Figure 1 is a schematic diagram of tracking an unequipped object in a wireless network.

Figure 2 is a schematic diagram of the position of the tracked object and the change of signal strength (RSS Dynamic).

Fig. 3 is a schematic diagram of possible position estimation of an object based on a single pair of wireless nodes.

Fig. 4 is a schematic diagram of the state transition of each wireless node in the distributed algorithm.

Figure 5 is a schematic diagram of the clustering algorithm.

Figure 6 is an example of a clustering algorithm.

As shown in Figure 1, a group of wireless nodes are arranged on the indoor ceiling, as shown by the black dots in the figure, each node not only continuously sends signals as a radio frequency signal transmitter, but also serves as a radio frequency signal receiver. Unequipped objects on the ground, such as people, have an impact on the received signal strength, as shown in the connection lines between some wireless nodes in the figure. The thick connection lines represent large changes in the signal strength between the wireless nodes connected to them. Conversely, thin lines represent small variations in signal strength between the wireless nodes connecting them.

As shown in Figure 2, two wireless nodes are arranged on the indoor ceiling, as shown by the two black origins in the figure. d represents the distance from the radio frequency transmitter to the radio frequency receiver, r ₁ represents the distance from the tracked object to the radio frequency transmitter, r ₂ represents the distance from the tracked object to the radio frequency receiver, h represents the distance from the wireless node to the ground, P ₁ represents The direct path of the wireless signal from the RF transmitter to the RF receiver, _P2 represents the ground reflection path of the wireless signal from the RF transmitter to the RF receiver, and P _obj represents the object-influenced path of the wireless signal from the RF transmitter to the RF receiver. The main latitude MPL represents the vertical projection line on the ground of the connecting line of two wireless nodes, and the latitude PL represents other lines parallel to the MPL on the ground. The main meridian MVL represents the projection line on the ground of the perpendicular bisector of the line connecting two wireless nodes, and the meridian VL represents other lines parallel to the MVL on the ground.

L shown in Figure 3 represents the length of the rectangle, and W represents the width of the rectangle. This rectangle is the possible location area of the non-device object estimated according to the signal strength change (RSS Dynamic).

Among them, Threshold in Figure 4 represents the signal strength change (RSS Dynamic) value that distinguishes whether there is an object.

The hollow circles arranged in a rectangle in FIG. 5 refer to the wireless nodes arranged on the indoor ceiling, and the solid circles represent the positions of the objects on the ground. Each rectangular area represents the possible location area of an object estimated by a pair of wireless nodes.

The example in Figure 6 generates two dynamic clusters, and each cluster is marked with a large dashed box in the figure. The cluster in the upper right corner of the figure is cluster 1, and the cluster in the lower left corner is cluster 2. Node 4 is the cluster head of cluster 1, and node 14 is the cluster head of cluster 2. The cluster head of each cluster is responsible for calculating the position of the objects in the cluster. The rectangle with thick dotted line is the actual position of the non-equipment object, and the rectangle with thin dotted line is the position of the non-equipment object calculated by the cluster head.

Detailed ways

The basic idea of the invention is shown in Figure 1. Arrange some wireless nodes communicating with each other on the indoor ceiling. Each node not only transmits signals as a radio frequency transmitter, but also receives signals as a radio frequency receiver at the same time. At that time, the signal strength received between them was stable. When the non-device object moves around, it will cause the signal strength between some wireless nodes to change, and the invention uses the change of the signal strength between these different wireless nodes to track the position of the non-device object.

The invention adopts a single device-free object tracking method based on an optimal coverage algorithm in a wireless network. It is divided into two main steps. The first step is the modeling step. The purpose of this step is to model only a pair of wireless nodes communicating with each other, and to obtain the relationship between the position of different unequipped objects and the change of signal strength. relation. The second step is the tracking step, where multiple specific device-free object tracking algorithms are implemented.

We first introduce the modeling implementation in the first step. Figure 2 shows a schematic diagram of the influence of different positions of a single non-device object on the RF signal strength of a pair of communicating wireless nodes. Among the pair of wireless nodes, one acts as a radio frequency transmitter and the other acts as a radio frequency signal receiver. The RF transmitter continuously sends a signal to the RF signal receiver. In order to meet the practical application, the wireless nodes are arranged on the indoor ceiling. We have found through research that if there is no moving object in the environment, the change of the signal strength received by the RF signal receiver is very small, almost negligible. However, the presence of objects will affect the signal strength. According to the radar equation (Radar Equation), the influence of existing objects on the change of received signal strength can be expressed by the following formula,

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; obj</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}{{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 3</span>}}{{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="r"\; filenames="H2009101921347E0000021.png,H2009101921347E0000051.png"\; state="\{\{state\}\}">r</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}{{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="r"\; filenames="H2009101921347E0000012.png,H2009101921347E0000021.png"\; state="\{\{state\}\}">r</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

Here r ₁ represents the distance from the tracked object to the RF transmitter, r ₂ represents the distance from the tracked object to the RF receiver, and d represents the distance from the RF transmitter to the RF receiver. σ is the radar cross section of the unequipped object being tracked. This value is defined as the ratio of the object's scattered power to the incident power density. The size of this value is related to the size and material of the object. If the tracked object is a person, the value is 1. _Pt is the transmitted power in watts, _Gt is the antenna gain of the RF transmitter, _Gr is the antenna gain of the RF receiver, and λ is the wavelength of the transmitted radio wave.

Through the above formula, that is to say, for a fixed unequipped object and a pair of fixedly arranged radio frequency transmitters and receivers, the influence of the object on the signal strength change is only related to r ₁ and r ₂ , and other parameters can be regarded as is a constant of fixed size.

Therefore, through the above formula, we can prove that when the object is at the MPL and MVL, it usually has a greater impact on the change of the signal strength, even on each PL or VL, when the object is at the midpoint position, it will have a greater impact on the signal strength. The change of the signal has a greater impact, and when the object is farther and farther away from the position, the influence on the change of the signal strength will be smaller and smaller. In addition, according to the received signal strength variation value, the possible regional shape of the object on the ground is an ellipse, as shown in Fig. 2 . Fig. 2 is a top view of Fig. 1, so as to illustrate this problem concretely and intuitively. Here I use a bounding rectangle instead of this ellipse. L is the length of the rectangle and W is the width of the rectangle. The size of the length and width can be obtained through our modeling results.

Figure 4 is an example of its modeling for the situation where the distance between wireless nodes is 4 meters. Here, we need to realize the modeling of the distance settings of different wireless nodes, and obtain the relationship diagram of the influence of different object positions and signal strengths. Because the MPL and MVL object positions will produce the largest signal strength change, therefore, in this example, using the object position as the measurement standard, we can see that when the object is at the center of the MPL and MVL, the signal change value tends to be the largest, Here the x-axis is the distance from the object to the center point of the MPL and MVL, and the y-axis represents the change value (dB) of the signal strength. First, we use a threshold (threshold) to intercept these two curves. The solid line indicates the change of the signal intensity caused by the object on the MPL, and the dotted line indicates the change of the signal intensity caused by the object on the MPL. The intercept produced on the MPL signal strength change line is regarded as the length of the above-mentioned rectangle, and the intercept produced on the MVL signal strength change line is regarded as the width of the above-mentioned rectangle. The size of the threshold is defined as the maximum value of signal strength change when the non-device object does not exist and there are other moving objects in the environment. This value is due to the noise in the environment, so it is usually relatively small. For example, in this example, the maximum value of the signal strength change caused by the noise is 0.7dB. After intercepting on the way with this threshold, the value of the rectangle length L is 2.85 m, the value of the rectangle length W is 1.12 m.

We use the above method to model a pair of wireless nodes at different distances. Next, in the second step, we introduce the inventive multi-object tracking system based on the dynamic clustering algorithm.

The system can use any number of wireless nodes. Figure 5 is an example of a tracking system using 16 wireless nodes, which are currently using telosB wireless transceiver nodes produced by Crossbow Company. Figure 5 is also a top view. These 16 wireless nodes are arranged in a 4×4 grid and placed on the ceiling of the room, and their height from the ground is all 2.4 meters. Each wireless node is used as a radio frequency transmitter to send signals in broadcast mode, and also as a radio frequency receiver to receive signals sent from other wireless nodes. Their default transmission frequency is -10dBm, and the radio frequency is set to 2.4GHz. The distance between nodes is selected as 2m. This distance can be adjusted according to different needs of users. Generally speaking, if the distance is selected smaller, the tracking accuracy will be higher, but the cost of deployment will also increase accordingly, because the deployment Nodes will increase accordingly. However, the distance between nodes should be selected between 2m and 6m, because the too small distance between nodes makes the received signal strength between nodes too strong, and it is difficult for objects to cause excessive changes in received signal strength. Too large node distance will make the received signal strength between nodes too weak, and the noise interference will increase accordingly.

However, the present invention will adopt a distributed dynamic clustering algorithm (Dynamic Clustering) and a method for dynamically adjusting node transmission power. Dynamic clustering means that the existence of clusters and their size will change with time and changes in required characteristics. Because the optimal coverage algorithm cannot track multiple objects, the distributed dynamic clustering algorithm can effectively separate the areas affected by the signal strength of multiple objects, that is, as long as the distance between multiple objects Not very close, we can effectively cluster by reducing the node's transmit power, and then according to the different effects of multiple non-device target objects on the received signal strength of different nodes. That is, when there is an influence, the corresponding cluster will be generated, and the node with the highest remaining energy in the cluster will be selected as the cluster head. Then, the cluster head of each cluster collects the change of the signal strength among the nodes in the cluster and calculates the position of the objects in the cluster, and obtains an effective solution for tracking multiple target objects without equipment. In order to reduce the size of the cluster radius so that the system can locate multiple non-device target objects in a short distance, we use one-hop clustering.

We also proposed a new optimal probabilistic cover algorithm (Probabilistic Cover), so that each cluster head can accurately calculate the position of the target object without equipment in the cluster. The optimal probabilistic covering algorithm is a major improvement based on the optimal covering algorithm. It introduces a probability model. For each pair of nodes communicating with each other, if the signal strength of an unequipped target object changes, the possibility of the object being within its calculation range is estimated in a probabilistic manner. This leads to a more accurate algorithm.

Because non-device objects will affect the signal strength changes between some nodes, for these we call "affected wireless links", the purpose of the distributed dynamic clustering algorithm is to dynamically classify the nodes in the system according to the affected links Wireless nodes are clustered. The clustering of the present invention is a dynamic clustering method, because the clustering has a certain life time. Each cluster starts when the affected wireless link is detected and ends when the local information is collected by the cluster head.

In the dynamic clustering algorithm of the present invention, each wireless node has 4 states, as shown in Figure 4, at the very beginning, all nodes are in "static state" (STATIC), and each wireless node will establish a static Table, this static table stores the RF signal strength sent by all neighbor nodes. Each node will ignore the packets sent from nodes 5 meters away, because the signals of nodes that are too far away are easily interfered by noise through experiments. Each node establishes a link threshold for each neighbor that sends signals to it. This threshold is calculated from the signal strength variation in the environment without tracking objects, which is mainly caused by the noise in the environment.

When a wireless node measures that the signal strength change from a neighbor node is greater than the threshold, it enters the "DYNAMIC" state and starts an initial time counter, which symbolizes event detection. The purpose of setting the initial time counter is to prevent more than one wireless node from claiming to be the cluster head at the same time in the next step. At some time t, the initial timer at wireless node i is defined as,

${\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; init</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}$

${\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}$

P _t ⁱ is the remaining energy of wireless node i, which is described here as the ratio of existing energy to initial energy. The remaining energy is approximated by the real-time voltage of the wireless node, and the voltage value can be directly read and obtained through the ADC of the wireless node operating system Tinyos. V _max is 3.0 volts for the node's 2 AA batteries. T _c is a constant, it can make the low remaining energy node wait for at least T _c time. T _c is defined according to the transmission time of a single data packet and the size of the cluster. In our experiments, this value is usually set to 0.5 seconds. T _r is a small random time counter whose upper limit is bound by the value of T _c . Through these settings, we can make the node with the most remaining energy in each cluster become the cluster head.

In the "dynamic" (DYNAMIC) state, when the wireless node detects a reachable cluster head, it becomes a member node. Otherwise, the node will claim to be the cluster head, and then enter the "cluster head" (HEAD) state after the time counter counts. When the cluster head finds that a stronger (more remaining energy) cluster head is within its one-hop range, it will change itself into a "member" (MEMER) state, and then make itself a member of the cluster head. If there are two wireless nodes with the same residual energy, the one with the largest ID will become the cluster head. This cluster head selection criterion will ensure that the strongest (the most remaining energy) wireless node will become the cluster head. The cluster head of each cluster will have information about all "affected wireless links" in the cluster. And a member node may belong to multiple cluster heads. In other words, different clusters may overlap.

When the cluster head is selected, the cluster head will estimate the position of the object according to the information of "affected wireless links" in the cluster. Here we use the probabilistic coverage algorithm to realize the tracking and positioning of unequipped objects in the cluster. From the foregoing, we know that for each affected wireless link, the area of possible locations of objects resembles an ellipse. Here we use a circumscribing rectangle to illustrate this area to simplify the calculation. In order to get the size of this rectangle, we use a threshold to intercept the signal change curves of the MPL and MVL positions, as shown in Figure 3, Figure 3 is an example of a wireless node with a length of 4 meters, and the width intercepted based on the MPL is the length of the rectangle L or L', the width intercepted based on MVL is the width of the rectangle, W or W'. The higher the threshold is set, the smaller the estimated device-free object area will be, and vice versa, the lower the threshold will be, the larger the estimated device-free object area will be.

For each affected wireless link, we can estimate the area where the object may exist, represented by a rectangle. For each rectangle, we set a weight to represent the probability that the object exists in this area.

Pr _i (%)=D/M _i

Here, Pr _i is the probability that the object exists within the estimated rectangular area for the affected wireless link i. D is the received signal strength change value (RSS Dynamic), and M _i is the average maximum signal strength change value of the affected wireless link i in modeling. And according to the model, for the object possible area between short-distance wireless nodes, its weight is larger than that of long-distance, if its transmission power is set as sensitive transmission power.

After estimating the possible area for each affected wireless link, there will be many such rectangles in the wireless node grid, as shown in Figure 5, some rectangles may overlap, if A certain location has many such overlaps and has the highest weight, then the object is most likely to be in this area. It is possible to generate several rectangular clusters in the system area, either due to the presence of non-equipment objects or due to noise. We ignore those small rectangular clusters because they are most likely to be generated by noise. Then, for each rectangular cluster, we employ a probabilistic coverage algorithm to estimate the location of the object. We use a fixed-size square (0.5m side length) to scan the entire grid area. At each scan point, we calculate the coverage of the square at that location, which is the intersection area of the square and each rectangle multiplied by the rectangle Probability weights and cumulative sum. The location with the largest coverage value is the estimated object location.

Here we use the example in the figure to explain in detail. In Figure 6, the 16 wireless nodes are marked with numbers, from 1 to 16. Among them, there are many affected wireless links. Correspondingly, each link has a corresponding The estimated possible area of the object, so there are many rectangles of different sizes, the darker rectangle has a high weight, and the lighter rectangle has a small weight. Using the distributed dynamic clustering algorithm, two rectangular clusters will be generated, which are the wireless nodes surrounded by two dotted lines in the figure. In the figure, node 6 and node 7 belong to cluster 1 and cluster 2 at the same time. So they will send the corresponding signal strength change value to the 2 cluster heads, which are node 4 and node 14 in the figure. Because probabilistic coverage algorithms have small cluster sizes, it is easy to use them to locate multiple unequipped objects.

After a lot of experiments, our algorithm can achieve the average accuracy of tracking multiple unequipped objects at about 1 meter, and the average distance between these unequipped objects is about 5 meters. If the distance between these objects is very close, we think They are the same object.

Claims (9)

1. a wireless network is based on a plurality of no equipment object tracking method of dynamic clustering algorithm, it is characterized in that: based on the wireless network technology, cause the variation modeling of the signal strength signal intensity between the radio node and the method for distinguishing and following the trail of a plurality of no equipment objects by the method for dynamic clustering according to the diverse location of no equipment object.

2. wireless network according to claim 1 is characterized in that based on a plurality of no equipment object tracking method of dynamic clustering algorithm: based on the wireless network technology, utilize the communication capacity of radio node.

3. wireless network according to claim 1 is characterized in that based on a plurality of no equipment object tracking method of dynamic clustering algorithm: by the diverse location of no device target object in surveyed area carried out modeling to the influence of the wireless node signals Strength Changes of intercommunication mutually of different transmitted powers.

4. wireless network according to claim 3 is characterized in that based on a plurality of no equipment object tracking method of dynamic clustering algorithm: each only a pair of relatively radio node of intercommunication mutually, carry out modeling to no equipment object diverse location in surveyed area.

5. wireless network according to claim 3 is based on a plurality of no equipment object tracking method of dynamic clustering algorithm, it is characterized in that: utilizing does not manyly have the equipment object tracking to the change in signal strength between the radio node, thereby abate the noise influence, improve and follow the trail of precision.

6. wireless network according to claim 3 is characterized in that based on a plurality of no equipment object tracking method of dynamic clustering algorithm: threshold value (threshold) is set distinguishes the existence that has or not object.

7. wireless network according to claim 1 is based on a plurality of no equipment object tracking method of dynamic clustering algorithm, it is characterized in that: the method for utilizing dynamic clustering, distinguish many that a plurality of different objects cause to the change in signal strength between the radio node, determine a plurality of object numbers, and the difference trace location.

8. wireless network according to claim 7 is based on a plurality of no equipment object tracking method of dynamic clustering algorithm, and it is characterized in that: the dynamic clustering algorithm need utilize the result of modeling.

9. wireless network according to claim 7 is characterized in that based on a plurality of no equipment object tracking method of dynamic clustering algorithm: the dynamic clustering algorithm is only handled the radio node data that change in signal strength is arranged, and shortens the response time, saves energy consumption.

Images