CN103327603A

CN103327603A - Three-dimensional node positioning method used for wireless sensor network based on APIT

Info

Publication number: CN103327603A
Application number: CN2012100735367A
Authority: CN
Inventors: 刘琳岚; 舒坚; 张海利
Original assignee: Nanchang Hangkong University
Current assignee: Nanchang Hangkong University
Priority date: 2012-03-20
Filing date: 2012-03-20
Publication date: 2013-09-25

Abstract

Provided is a three-dimensional node positioning method used for a wireless sensor network based on an APIT. If an unknown node has at least six neighboring beacon nodes, the relations of tetrahedrons composed of the neighboring beacon nodes of the unknown node and the unknown node are sequentially judged, if the unknown node is included in one tetrahedron, then the tetrahedron is cut through all middle vertical faces of the tetrahedron, by comparing RSSIs of the four beacon nodes forming the tetrahedron received by the unknown node, which cutting portion of the tetrahedron cut through the middle vertical faces the unknown node exists in is confirmed, the intersection of all the cutting portions including the known nodes is calculated to obtain a narrowed space where the unknown node exists, a centroil of the intersection of the narrowed spaces of all the tetrhedrons serves as an estimation position of the unknown node, and therefore the position coordinate of the unknown node is thereby calculated.

Description

APIT-based Node 3D Positioning Method for Wireless Sensor Networks

技术领域 technical field

本发明涉及无线传感器网络，尤其涉及一种用于无线传感器网的基于APIT的节点三维定位法。The invention relates to a wireless sensor network, in particular to an APIT-based node three-dimensional positioning method for a wireless sensor network.

背景技术 Background technique

在无线传感器网络(wireless sensor networks，WSN)中，位置信息对其监测活动至关重要，事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没有位置信息的监测消息往往毫无意义。因此节点定位是无线传感器网络最基本的功能之一，对其应用的有效性起着关键的作用。In wireless sensor networks (WSN), location information is crucial to its monitoring activities. The location of the event or the location of the node that obtains the information is the important information contained in the sensor node monitoring message. Monitoring without location information Messages are often meaningless. Therefore, node location is one of the most basic functions of wireless sensor networks, and it plays a key role in the effectiveness of its application.

接收信号强度指示值(received signal strength indicator，RSSI)作为WSN中最容易获得的参数一直受到定位方法研究者的青睐。基于RSSI值的定位方法的主要思想是根据RSSI衰减模型将两节点间的RSSI衰减值直接转换成两个节点间的距离，最后通过多个信标节点(配备GPS定位系统或通过其它方式能直接获得位置信息的节点)与待定位节点(位置未知的节点)间的距离计算待定位节点的位置坐标。Received signal strength indicator (RSSI), as the most easily obtained parameter in WSN, has been favored by positioning method researchers. The main idea of the positioning method based on RSSI value is to convert the RSSI attenuation value between two nodes directly into the distance between two nodes according to the RSSI attenuation model, and finally through multiple beacon nodes (equipped with GPS positioning system or through other means can directly The distance between the node that obtains the location information) and the node to be positioned (the node whose location is unknown) is used to calculate the location coordinates of the node to be positioned.

然而，RSSI受环境影响较大，随着应用场景的变化其性能表现不一。如：RSSI与无线信号的关联性较大，若传感器节点靠近地面，其发射信号容易被地磁干扰。空旷的操场由于障碍物比小树林要少，所以在空旷场地，RSSI性能表现较好。However, RSSI is greatly affected by the environment, and its performance varies with the change of application scenarios. For example, RSSI is highly correlated with wireless signals. If the sensor node is close to the ground, its transmitted signal is easily interfered by geomagnetism. The open playground has fewer obstacles than the grove, so the RSSI performance is better in the open field.

鉴于以上所述，RSSI的精确度很大程度上依赖其应用环境，很多复杂地形的场景下，RSSI不能准确地转化成节点间距离信息造成较大的误差。在此种复杂条件下，人们提出了一种运用但不严格依赖RSSI值的定位方法——APIT定位方法。它只需要RSSI的“模糊值”来比较节点间距离的远近，并不严格将RSSI转化为精确的距离值。所以，在复杂环境中，如多障碍物场景、近地场景中，APIT巧妙地避免了RSSI值因受到干扰而不准确的情况。In view of the above, the accuracy of RSSI depends largely on its application environment. In many complex terrain scenarios, RSSI cannot be accurately converted into distance information between nodes, resulting in large errors. Under such complex conditions, people have proposed a positioning method that uses but does not strictly depend on the RSSI value - the APIT positioning method. It only needs the "fuzzy value" of RSSI to compare the distance between nodes, and does not strictly convert RSSI into an accurate distance value. Therefore, in complex environments, such as multi-obstacle scenes and near-earth scenes, APIT skillfully avoids the situation where the RSSI value is inaccurate due to interference.

APIT定位方法是一种与测距无关的定位方法。换句话说，这种定位方法并不是使用测得的物理参数值直接转换成节点间距离进而得到待定位节点位置的定位方法。APIT定位方法的原理如下：The APIT positioning method is a positioning method that has nothing to do with ranging. In other words, this positioning method is not a positioning method that directly converts the measured physical parameter values into the distance between nodes to obtain the position of the node to be positioned. The principle of the APIT positioning method is as follows:

其理论支持是最佳三角形内点测试法(perfect point-in-triangulation test，PIT)，即假如存在一个方向，节点M沿着这个方向移动会同时远离或接近A、B、C，那么M在△ABC外，如图1(b)所示；否则，M在△ABC内，如图1(a)所示。Its theoretical support is the perfect point-in-triangulation test (PIT), that is, if there is a direction, the node M will move away from or close to A, B, and C at the same time when moving along this direction, then M is in the Outside △ABC, as shown in Figure 1(b); otherwise, M is inside △ABC, as shown in Figure 1(a).

在APIT定位方法中，邻居节点(在通信范围内的节点)间通常通过交换比较各自接收到的RSSI值，利用“RSSI越小，节点间距离越大”的规律，判断距离某一锚节点的远近。如图2(a)，待定位节点M与邻居节点1交换信息可知，节点M接收到锚节点B、C的RSSI值大于节点1接收到锚节点B、C的RSSI值，而节点M接收到锚节点A的RSSI值小于节点1接收到锚节点A的RSSI值。根据RSSI值的比较，如果节点M移动至节点1所在位置，将会远离节点B、C并靠近节点A。依次对邻居节点2、3、4进行相同的判断，待定位节点M在△ABC内。而在图2(b)中可知，节点M假如运动至邻居节点2所在位置，将会同时靠近A、B、C，那么断定M在△ABC外。最终，如图2(c)，对待定位节点所属三角形的重叠区域使用质心方法，计算出其质心作为待定位节点的坐标。In the APIT positioning method, neighbor nodes (nodes within the communication range) usually exchange and compare the received RSSI values, and use the law of "the smaller the RSSI, the greater the distance between nodes" to judge the distance from an anchor node. near and far. As shown in Figure 2(a), the node M to be positioned exchanges information with its neighbor node 1. It can be seen that the RSSI value received by node M from anchor nodes B and C is greater than the RSSI value received by node 1 from anchor nodes B and C, while node M receives The RSSI value of anchor node A is smaller than the RSSI value received by node 1 from anchor node A. According to the comparison of RSSI values, if node M moves to the location of node 1, it will be far away from nodes B and C and close to node A. Carry out the same judgment on neighbor nodes 2, 3, and 4 in turn, and the node M to be located is within △ABC. In Figure 2(b), it can be seen that if node M moves to the location of neighbor node 2, it will be close to A, B, and C at the same time, so it is concluded that M is outside △ABC. Finally, as shown in Figure 2(c), the centroid method is used to calculate the centroid of the overlapping area of the triangle to which the node to be located belongs as the coordinate of the node to be located.

在这里，由于计算三角形区域的质心需要的计算量比较大，所以通常情况下，研究人员采用网格扫描(GRID SCAN)的方法。其主旨是将整个平面分割成若干等大的正方形。每个正方形对应一个计数器。判断信标节点构成的每一个三角形，若该三角形包含待定位节点，则该三角形内的每一个正方形所对应的计数器加一；若该三角形不包含待定位节点，则该三角形内的每一个正方形所对应的计数器减一。最后筛取计数器计数最高值的所有正方形，求取这些正方形质心的平均值作为待定位节点的估计位置。示意图如图3(a)、(b)所示。Here, because the calculation of the centroid of the triangular area requires a relatively large amount of calculation, researchers usually use the method of grid scanning (GRID SCAN). Its purpose is to divide the whole plane into several squares of equal size. Each square corresponds to a counter. Judging each triangle formed by the beacon node, if the triangle contains the node to be located, the counter corresponding to each square in the triangle is incremented by one; if the triangle does not contain the node to be located, each square in the triangle The corresponding counter is decremented by one. Finally, all the squares with the highest value of the counter are screened out, and the average value of the centroids of these squares is calculated as the estimated position of the node to be located. The schematic diagram is shown in Figure 3(a) and (b).

且在判断待定位节点的时候，如果待定位节点的邻居节点个数较少，APIT定位方法经常因为边界效应出现“in-to-out error”和“out-to-in error”两种情况。当待定位节点距离信标节点组成三角形的边缘较近的时候，很容易将原本位于三角形外的待定位节点判断为位于三角形内，也很容易将原本位于三角形内的待定位节点定位与三角形外。其示意图如图4。M为待定位节点，N为M的邻居节点，图4(a)为“in-to-out error”的示意图，M收到A、B、C三个信标节点的RSSI值均小于N收到A、B、C三个节点的RSSI值。依照APIT定位的原理M应判断为位于△ABC的外部，但实际M位于三角形内部。图4(b)为“out-to-in error”的示意图，M收到A、B两个信标节点的RSSI大于N收到A、B的RSSI，M收到C节点的RSSI小于N点收到C点的RSSI。按APIT定位方法，M被误判位于△ABC内部，实际却在△ABC外部。And when judging the node to be located, if the number of neighbor nodes of the node to be located is small, the APIT positioning method often has two situations: "in-to-out error" and "out-to-in error" due to boundary effects. When the node to be located is close to the edge of the triangle formed by the beacon nodes, it is easy to judge the node to be located outside the triangle as being located in the triangle, and it is also easy to locate the node to be located originally located inside the triangle with the triangle outside the triangle. . Its schematic diagram is shown in Figure 4. M is the node to be located, and N is the neighbor node of M. Figure 4(a) is a schematic diagram of "in-to-out error". RSSI values to nodes A, B, and C. According to the principle of APIT positioning, M should be judged to be located outside △ABC, but actually M is located inside the triangle. Figure 4(b) is a schematic diagram of "out-to-in error". The RSSI received by M from the two beacon nodes A and B is greater than the RSSI received by N from A and B, and the RSSI received by M from node C is smaller than N. The RSSI of point C is received. According to the APIT positioning method, M is misjudged to be inside △ABC, but actually outside △ABC.

目前的基于APIT的定位方法还大多集中在二维平面上，其不足之处在于其只能将整个网络部署在二维平面，而对于部署在三维空间中的节点，二维定位方法束手无策。而在三维定位中，计算的复杂度、通信量等等诸多因素变大，致使三维定位的难度变大精度变低。Most of the current positioning methods based on APIT are concentrated on the two-dimensional plane. Their disadvantage is that they can only deploy the entire network on the two-dimensional plane. For the nodes deployed in the three-dimensional space, the two-dimensional positioning method is helpless. However, in 3D positioning, many factors such as computational complexity and communication volume become larger, resulting in greater difficulty and lower accuracy of 3D positioning.

发明内容 Contents of the invention

本发明的目的在于不以大幅增加硬件、通信和计算开销为前提，提供一种基于APIT的三维节点定位及其求精方法。该方法应适用于在三维空间中大规模随机部署的传感器网络，并且简单易行、实用性较强，且较之APIT-3D定位方法，在定位精度方面有较大幅度提升。The purpose of the present invention is to provide an APIT-based three-dimensional node positioning method and its refinement method without greatly increasing hardware, communication and calculation costs. This method should be suitable for large-scale random deployment of sensor networks in three-dimensional space, and is simple and practical, and compared with the APIT-3D positioning method, the positioning accuracy has been greatly improved.

本发明的用于无线传感器网的基于APIT的节点三维定位法，其包括：若未知节点具有至少6个邻居信标节点，则依次判断该未知节点的邻居信标节点所构成的每个四面体与该未知节点的关系；若该未知节点包含于一个四面体内，用该四面体的所有中垂面对该四面体进行切割；通过比较该未知节点收到构成该四面体的4个信标节点的RSSI，确定未知节点存在于中垂面切割后四面体的哪一切割部分；对该四面体所有的包含该未知节点的切割部分求取交集得到未知节点存在的缩小空间；将所有四面体的缩小空间的交集的质心作为未知节点的估计位置，从而计算出未知节点的位置坐标。The APIT-based node three-dimensional positioning method for wireless sensor networks of the present invention includes: if the unknown node has at least 6 neighbor beacon nodes, then sequentially judge each tetrahedron formed by the neighbor beacon nodes of the unknown node The relationship with the unknown node; if the unknown node is contained in a tetrahedron, cut the tetrahedron with all the vertical sides of the tetrahedron; receive the 4 beacon nodes that constitute the tetrahedron by comparing the unknown node The RSSI of the unknown node is determined in which cut part of the tetrahedron after the vertical plane cut; the intersection of all the cut parts of the tetrahedron containing the unknown node is obtained to obtain the reduced space where the unknown node exists; all the tetrahedron's The centroid of the intersection of the reduced space is used as the estimated position of the unknown node, so as to calculate the position coordinates of the unknown node.

优选地，若未知节点具有2-5个邻居信标节点，采用以下公式计算其位置坐标；Preferably, if the unknown node has 2-5 neighbor beacon nodes, the following formula is used to calculate its position coordinates;

$\{\begin{matrix} {x x}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {x x}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {y the y}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {y the y}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {z z}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {z z}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \end{matrix}$

其中，RSSI_i代表未知节点接收到第i个邻居信标节点的RSSI值，n代表未知节点的邻居信标节点的个数，(x_i，y_i，z_i)分别代表各个邻居信标节点的三维坐标，(x_estimate，y_estimate，z_estimate)为未知节点的位置坐标。Among them, RSSI _i represents the RSSI value of the i-th neighbor beacon node received by the unknown node, n represents the number of neighbor beacon nodes of the unknown node, (xi _, y _i , z _i ) represent each neighbor beacon node The three-dimensional coordinates of , (x _estimate , y _estimate , z _estimate ) are the position coordinates of unknown nodes.

优选地，设置两个变量分别代表未知节点被判断为四面体内或外；若某一邻居节点收到的构成四面体的4个邻居信标节点的RSSI均大于或小于未知节点所收到4个邻居信标节点的RSSI，则代表未知节点在四面体外的变量加一，否则另一变量加一；依次判断完所有邻居节点收到RSSI与未知节点收到RSSI的大小关系，比较所设两个变量大小以确定未知节点是在四面体内还是在四面体外。Preferably, two variables are set to represent that the unknown node is judged to be inside or outside the tetrahedron; if the RSSI received by a certain neighbor node of the four neighbor beacon nodes that constitute the tetrahedron is greater than or less than the four received by the unknown node The RSSI of the neighbor beacon node represents that the variable of the unknown node outside the tetrahedron is increased by one, otherwise the other variable is increased by one; after judging the relationship between the RSSI received by all neighbor nodes and the RSSI received by the unknown node in turn, compare the two set Variable size to determine whether the unknown node is inside or outside the tetrahedron.

优选地，在确定未知节点存在于中垂面切割后四面体的哪一切割部分的过程中，如果Preferably, in the process of determining which cut part of the tetrahedron after the mid-vertical plane cut the unknown node exists, if

$(({x x}_{b b} - - {x x}_{a a})) [[x x - - \frac{(({x x}_{b b} + + {x x}_{a a}))}{22}]] + + (({y the y}_{b b} - - {y the y}_{a a})) [[y the y - - \frac{(({y the y}_{b b} + + {y the y}_{a a}))}{22}]] + + (({z z}_{b b} - - {z z}_{a a})) [[z z - - \frac{(({z z}_{b b} + + {z z}_{a a}))}{22}]] > > 00$

成立，则AN＞BN，则A、N分别位于中垂面的两侧；如果AN＜BN，则A、N位于中垂面的同侧；其中线段AB为四面体的中垂面所垂直的一条边，线段AB两端点坐标分别为A(x_a，y_a，z_a)B(x_b，y_b，z_b)，N代表未知节点，其坐标为N(x，y，z)。If it is established, then AN>BN, then A and N are located on both sides of the vertical plane; if AN<BN, then A and N are located on the same side of the vertical plane; where the line segment AB is perpendicular to the vertical plane of the tetrahedron An edge, the coordinates of the two ends of the line segment AB are A(x _a , y _a , z _a )B(x _b , y _b , z _b ), N represents an unknown node, and its coordinates are N(x, y, z).

优选地，所述缩小空间的交集的质心通过以下步骤获得：将整个空间分划成多个大小相等的小立方体网格，每个网格对应一个计数器；对每一个四面体执行以下操作：如果一个四面体包含未知节点，则该四面体内的网格的计数器加一；如果一个四面体不包含未知节点，则该四面体内的网格的计数器减一；如果该四面体的网格与未知节点位于中垂面的同一侧，该网格对应的计数器再加一；如果该四面体的网格与未知节点不在中垂面的同一侧，该网格对应的计数器减一；最后筛选计数器计数最高的网格，求取这些网格所组成图形的质心作为所述缩小空间的交集的质心。Preferably, the centroid of the intersection of the reduced spaces is obtained through the following steps: divide the whole space into a plurality of small cube grids of equal size, each grid corresponds to a counter; perform the following operations on each tetrahedron: if If a tetrahedron contains unknown nodes, the counter of the grid in the tetrahedron is incremented by one; if a tetrahedron does not contain unknown nodes, the counter of the grid in the tetrahedron is decremented by one; If it is on the same side of the mid-vertical plane, the counter corresponding to the grid will be increased by one; if the grid of the tetrahedron is not on the same side of the mid-vertical plane as the unknown node, the counter corresponding to the grid will be decremented by one; the last screening counter counts the highest grids, and obtain the centroids of the graphs formed by these grids as the centroids of the intersection of the reduced spaces.

优选地，所述缩小空间的交集的质心通过以下步骤获得：将整个空间分划成多个大小相等的小立方体网格，每个网格对应一个计数器；对每个四面体及该四面体的每个中垂面执行以下操作：如果一个四面体包含未知节点，则该四面体内与未知节点处于一个中垂面的一侧的网格对应的计数器加一。Preferably, the centroid of the intersection of the reduced space is obtained through the following steps: divide the entire space into a plurality of small cube grids of equal size, each grid corresponds to a counter; for each tetrahedron and the tetrahedron Each mid-vertical plane performs the following operation: If a tetrahedron contains unknown nodes, the counter corresponding to the mesh within the tetrahedron that the unknown node is on a side of a mid-vertical plane is incremented by one.

附图说明 Description of drawings

从对说明本发明的主旨及其使用的优选实施例和附图的以下描述来看，本发明的以上和其它目的、特点和优点将是显而易见的，在附图中：The above and other objects, features and advantages of the present invention will be apparent from the following description of preferred embodiments illustrating the gist of the invention and its use, and the accompanying drawings, in which:

图1(a)、(b)为PIT示意图；Figure 1 (a), (b) is a schematic diagram of the PIT;

图2(a)、(b)、(c)为APIT定位示意图；Figure 2 (a), (b), (c) is a schematic diagram of APIT positioning;

图3(a)、(b)为网格扫描说明示意图；Figure 3 (a), (b) is a schematic diagram illustrating grid scanning;

图4(a)、(b)分别是in-to-out error和out-to-in error示意图；Figure 4(a) and (b) are schematic diagrams of in-to-out error and out-to-in error respectively;

图5为被6次切割后四面体示意图；Figure 5 is a schematic diagram of a tetrahedron after being cut 6 times;

图6为邻居信标点较少而导致定位精度低的二维示意图；Figure 6 is a two-dimensional schematic diagram of low positioning accuracy due to fewer neighbor beacon points;

图7为APIT-3D示意图；Figure 7 is a schematic diagram of APIT-3D;

图8为中垂面切割示意图；Fig. 8 is a schematic diagram of mid-vertical cutting;

图9为本发明与APIT-3D方法的定位时间开销比较图。Fig. 9 is a comparison diagram of positioning time overhead between the present invention and the APIT-3D method.

具体实施方式 Detailed ways

下面，将结合附图对本发明进行详细说明。Below, the present invention will be described in detail with reference to the accompanying drawings.

邻居节点：能够互相通信的节点互称为邻居节点。Neighbor nodes: Nodes that can communicate with each other are called neighbor nodes.

邻居信标节点：是指能够通信的信标节点。Neighbor beacon node: refers to a beacon node that can communicate.

信标节点：具有GPS自定位能力的节点。Beacon node: a node with GPS self-positioning capability.

切割部分：代表四面体被其一个中垂面切割后形成的各个部分。Cut part: Represents each part formed after the tetrahedron is cut by one of its vertical planes.

缩小空间：四面体的包含未知节点的所有切割部分的交集。Reduced space: the intersection of all cut parts of a tetrahedron containing unknown nodes.

首先，将无线传感器节点随机播撒在三维空间中。其中信标节点具有GPS自定位能力。所有的信标节点通过GPS定位获得自身位置信息以后，向自身通信范围内所有节点广播自身位置信息与ID。所有传感器节点接收信标节点广播的信息并记录接收信号的RSSI值。若未知节点收到不同信标节点的消息个数达到4个，执行APIT-3D定位方法。若未收到信息，将未知节点定位为空间中心。若收到消息个数为1～3个，则将未知节点定位于所收到信息的信标节点组成的图形(点、线段、三角形)的质心。First, the wireless sensor nodes are randomly scattered in the three-dimensional space. Among them, the beacon node has GPS self-positioning capability. After all beacon nodes obtain their own location information through GPS positioning, they broadcast their own location information and ID to all nodes within their own communication range. All sensor nodes receive the information broadcast by the beacon node and record the RSSI value of the received signal. If the unknown node receives four messages from different beacon nodes, execute the APIT-3D positioning method. If no information is received, the unknown node is positioned as the spatial center. If the number of received messages is 1-3, the unknown node is located at the centroid of the graph (point, line segment, triangle) composed of the beacon nodes of the received information.

若未知节点收到不同信标节点的消息个数达到6个，则判断未知节点是否在信标节点所构成的四面体内。具体方法为：设置两个变量分别代表未知节点被判断为四面体内或外。若某一邻居节点收到的构成四面体的4个信标节点的RSSI均大于或小于未知节点所收到4个信标节点的RSSI，则代表未知节点在四面体外的变量加一，否则另一变量加一。依次判断完所有邻居节点收到RSSI与未知节点收到RSSI的大小关系，比较所设两个变量大小以断定四面体与未知节点间的位置关系。其判断依据为：给定线段AB两端点坐标分别为A(x_a，y_a，z_a)B(x_b，y_b，z_b)，如果点N(x，y，z)满足AN＞BN，即A、N位于中垂面的两侧，则有：If the number of messages received by the unknown node from different beacon nodes reaches 6, it is judged whether the unknown node is in the tetrahedron formed by the beacon nodes. The specific method is: setting two variables to represent whether the unknown node is judged to be inside or outside the tetrahedron. If the RSSI received by a neighbor node of the four beacon nodes that constitute the tetrahedron is greater than or less than the RSSI of the four beacon nodes received by the unknown node, it means that the variable of the unknown node outside the tetrahedron is increased by one, otherwise another Increments a variable by one. After judging the size relationship between the RSSI received by all neighbor nodes and the RSSI received by the unknown node in turn, compare the two set variables to determine the positional relationship between the tetrahedron and the unknown node. The judgment basis is as follows: the coordinates of the two ends of the given line segment AB are A(x _a , y _a , z _a )B(x _b , y _b , z _b ), if point N(x, y, z) satisfies AN> BN, that is, A and N are located on both sides of the vertical plane, then:

$(({x x}_{b b} - - {x x}_{a a})) [[x x - - \frac{(({x x}_{b b} + + {x x}_{a a}))}{22}]] + + (({y the y}_{b b} - - {y the y}_{a a})) [[y the y - - \frac{(({y the y}_{b b} + + {y the y}_{a a}))}{22}]] + + (({z z}_{b b} - - {z z}_{a a})) [[z z - - \frac{(({z z}_{b b} + + {z z}_{a a}))}{22}]] > > 00 - - - - - - ((11))$

成立，如图7所示。established, as shown in Figure 7.

若某未知节点的邻居信标节点的个数为n，则可构成C_n ⁴个四面体，依次判断这些四面体与未知节点的关系。若未知节点包含于四面体内，采用“中垂面切割”法。通过比较未知节点收到构成四面体的4个信标节点的RSSI，确定未知节点存在于中垂面切割后四面体的哪一部分，如图8。最后取所有四面体中被缩小后的可能存在空间的交集的质心作为定位的估计位置。If the number of neighbor beacon nodes of an unknown node is n, C _n ⁴ tetrahedrons can be formed, and the relationship between these tetrahedrons and the unknown node can be judged in turn. If the unknown nodes are included in the tetrahedron, use the "vertical plane cut" method. By comparing the RSSI received by the unknown node from the four beacon nodes that constitute the tetrahedron, it is determined which part of the tetrahedron the unknown node exists in after the vertical plane cut, as shown in Figure 8. Finally, the center of mass of the intersection of the reduced possible spaces in all tetrahedrons is taken as the estimated position of positioning.

在求质心的过程中采取改进的GRID SCAN方法。即将整个空间分划成多个大小相等的小立方体网格，每个网格对应一个计数器。定标过程中，将属于包含未知节点的四面体内的网格的计数器加一，其余网格计数器减一。如果网格与未知节点位于中垂面的同一侧，计数器再加一，否则减一。以此逐一判断每一个四面体与其6个中垂面。最后筛选计数器计数最高的网格，求取这些网格所组成图形的质心作为定位结果。The improved GRID SCAN method is adopted in the process of finding the centroid. That is, the whole space is divided into multiple small cube grids of equal size, and each grid corresponds to a counter. During calibration, the counters belonging to the meshes within the tetrahedron containing the unknown nodes are incremented by one, and the counters of the remaining meshes are decremented by one. If the grid is on the same side of the vertical plane as the unknown node, the counter is incremented by one, otherwise it is decremented by one. In this way, each tetrahedron and its 6 vertical planes are judged one by one. Finally, screen the grid with the highest counter count, and obtain the centroid of the graphics formed by these grids as the positioning result.

对于由于邻居信标节点个数较小导致定位精度低的未知节点，本发明采用RSSI加权弥补求精方法。根据未知节点收到邻居信标节点的RSSI值来求取权重，获得位置的计算公式。For the unknown nodes with low positioning accuracy due to the small number of neighboring beacon nodes, the present invention adopts the RSSI weighted compensating and refining method. Calculate the weight according to the RSSI value received by the unknown node from the neighbor beacon node, and obtain the calculation formula of the position.

对于邻居信标节点个数为2-5的未知节点，采用以下定标公式：For unknown nodes with 2-5 neighbor beacon nodes, the following scaling formula is used:

$\{\begin{matrix} {x x}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {x x}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {y the y}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {y the y}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {z z}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {z z}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \end{matrix} - - - - - - ((22))$

其中，RSSI_i代表未知节点接收到第i个邻居信标节点的RSSI值。n代表未知节点的邻居信标节点的个数。(x_i，y_i，z_i)分别代表各个邻居信标节点的三维坐标。Among them, RSSI _i represents the RSSI value received by the unknown node from the i-th neighbor beacon node. n represents the number of neighbor beacon nodes of unknown nodes. ( _xi , y _i , zi ₎ respectively represent the three-dimensional coordinates of each neighboring beacon node.

公式(2)由公式(3)推导而来。Formula (2) is derived from formula (3).

$\{\begin{matrix} {x x}_{estimate estimate} = = {Σ Σ}_{i i = = 11}^{n no} \frac{{x x}_{i i}}{{d d}_{i i}} / / {Σ Σ}_{i i = = 11}^{n no} \frac{11}{{d d}_{i i}} \\ {y the y}_{estimate estimate} = = {Σ Σ}_{i i = = 11}^{n no} \frac{{y the y}_{i i}}{{d d}_{i i}} / / {Σ Σ}_{i i = = 11}^{n no} \frac{11}{{d d}_{i i}} \\ {Z Z}_{estimate estimate} = = {Σ Σ}_{i i = = 11}^{n no} \frac{{z z}_{i i}}{{d d}_{i i}} / / {Σ Σ}_{i i = = 11}^{n no} \frac{11}{{d d}_{i i}} \end{matrix} - - - - - - ((33))$

式(3)中d_i代表未知节点与第i个邻居信标节点间的距离。而通过公式(3)又有：In formula (3), d _i represents the distance between the unknown node and the i-th neighbor beacon node. And through the formula (3) there are:

$\underset{{d d}_{a a} {d d}_{b b} {d d}_{c c} {d d}_{d d} &RightArrow; &Right Arrow; 00}{lim lim} \sqrt{{((x x - - {x x}_{estimate estimate}))}^{22} + + {((y the y - - {y the y}_{estimate estimate}))}^{22} + + {((z z - - {z z}_{estimate estimate}))}^{22}} = = 00 - - - - - - ((44))$

成立。从式(4)分析得出，当未知节点与信标节点之间的距离趋近于0，此求精方法的误差越小，趋近于0。established. From the analysis of formula (4), when the distance between the unknown node and the beacon node is close to 0, the error of this refinement method is smaller and close to 0.

实验证明，该方法的开销相对APIT-3D定位方法只有微幅增加，见图9。Experiments have proved that the cost of this method is only slightly increased compared with the APIT-3D positioning method, as shown in Figure 9.

尽管已示出和描述了本发明的优选实施例，可以设想，本领域的技术人员可在所附权利要求的精神和范围内设计对本发明的各种修改。While a preferred embodiment of the invention has been shown and described, it is contemplated that various modifications of the invention can be devised by those skilled in the art within the spirit and scope of the appended claims.

Claims

1. a kind of node three-dimensional localization method based on APIT for wireless sensor network, it is characterized in that:

If the unknown node has at least 6 neighbor beacon nodes, then determine the relationship between each tetrahedron formed by the neighbor beacon nodes of the unknown node and the unknown node in turn;

If the unknown node is contained in a tetrahedron, cut the tetrahedron with all the vertical sides of the tetrahedron; by comparing the RSSI received by the unknown node from the four beacon nodes that make up the tetrahedron, it is determined that the unknown node exists Which cutting part of the tetrahedron after cutting in the vertical plane; obtain the intersection of all the cutting parts of the tetrahedron containing the unknown node to obtain the reduced space where the unknown node exists;

The centroid of the intersection of the reduced space of all tetrahedrons is used as the estimated position of the unknown node, so as to calculate the position coordinates of the unknown node.

2. the node three-dimensional localization method based on APIT for wireless sensor network as claimed in claim 1, it is characterized in that:

If the unknown node has 2-5 neighbor beacon nodes, use the following formula to calculate its position coordinates;

\{\begin{matrix} {x x}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {x x}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {y the y}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {y the y}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \\ {z z}_{estimate estimate} = = \frac{{Σ Σ}_{i i = = 11}^{n no} {z z}_{i i} * * 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}}{{Σ Σ}_{i i = = 11}^{n no} 1010^{\frac{{RSSI RSSI}_{i i}}{2020}}} \end{matrix}

Among them, RSSI _i represents the RSSI value of the i-th neighbor beacon node received by the unknown node, n represents the number of neighbor beacon nodes of the unknown node, (xi _, y _i , z _i ) represent each neighbor beacon node The three-dimensional coordinates of , (x _estimate , y _estimate , z _estimate ) are the position coordinates of unknown nodes.

3. the APIT-based node three-dimensional positioning method for wireless sensor network as claimed in claim 1, is characterized in that: the concrete method of judging whether this unknown node is in the tetrahedron that neighbor beacon node forms is:

Setting two variables represents whether the unknown node is judged to be inside or outside the tetrahedron;

If the RSSI received by a neighbor node of the four neighbor beacon nodes that constitute the tetrahedron is greater than or less than the RSSI received by the four neighbor beacon nodes of the unknown node, it means that the variable of the unknown node outside the tetrahedron is increased by one, Otherwise the other variable is incremented by one;

After judging the relationship between the RSSI received by all neighbor nodes and the RSSI received by the unknown node in turn, compare the two set variables to determine whether the unknown node is inside or outside the tetrahedron.

4. the APIT-based node three-dimensional localization method for wireless sensor network as claimed in claim 1 or 3, is characterized in that: in the process of which cutting part of tetrahedron after determining that unknown node exists in vertical plane cutting ,if

(({x x}_{b b} - - {x x}_{a a})) [[x x - - \frac{(({x x}_{b b} + + {x x}_{a a}))}{22}]] + + (({y the y}_{b b} - - {y the y}_{a a})) [[y the y - - \frac{(({y the y}_{b b} + + {y the y}_{a a}))}{22}]] + + (({z z}_{b b} - - {z z}_{a a})) [[z z - - \frac{(({z z}_{b b} + + {z z}_{a a}))}{22}]] > > 00

If it is established, then AN>BN, then A and N are located on both sides of the vertical plane; if AN<BN, then A and N are located on the same side of the vertical plane;

The line segment AB is a side perpendicular to the vertical plane of the tetrahedron, and the coordinates of the two ends of the line segment AB are A(x _a , y _a , z _a )B(x _b , y _b , z _b ), and N represents an unknown node , whose coordinates are N(x, y, z).

5. the APIT-based node three-dimensional localization method for wireless sensor network as claimed in claim 1 or 3, is characterized in that: the centroid of the intersection of described narrowing space obtains by following steps:

Divide the entire space into multiple grids of small cubes of equal size, each grid corresponds to a counter; perform the following operations on each tetrahedron:

If a tetrahedron contains unknown nodes, the counter of the mesh within the tetrahedron is incremented by one; if a tetrahedron does not contain unknown nodes, the counter of the mesh within the tetrahedron is decremented by one; If the node is on the same side of the mid-vertical plane, the counter corresponding to the grid is added by one; if the grid of the tetrahedron is not on the same side of the mid-vertical plane as the unknown node, the counter corresponding to the grid is decremented by one;

Finally, the grid with the highest counter count is screened, and the centroid of the graph formed by these grids is obtained as the centroid of the intersection of the reduced spaces.

6. the APIT-based node three-dimensional localization method for wireless sensor network as claimed in claim 1 or 3, is characterized in that: the centroid of the intersection of described narrowing space obtains by following steps:

Divide the entire space into multiple small cubic grids of equal size, each grid corresponds to a counter; perform the following operations on each tetrahedron and each vertical plane of the tetrahedron:

If a tetrahedron contains unknown nodes, the counter in the tetrahedron corresponding to the mesh with the unknown node on one side of the vertical plane is incremented by one.