# Wireless Sensor Network Target Localization Algorithm Based on Two- and Three-Dimensional Delaunay Partitions

Authors: Chenguang Shao
Journal: Journal of Sensors
 (2021)

---

## Abstract

The target localization algorithm is critical in the field of wireless sensor networks (WSNs) and is widely used in many applications. In the conventional localization method, the location distribution of the anchor nodes is fixed and cannot be adjusted dynamically according to the deployment environment. The resulting localization accuracy is not high, and the localization algorithm is not applicable to three-dimensional (3D) conditions. Therefore, a Delaunay-triangulation-based WSN localization method, which can be adapted to two-dimensional (2D) and 3D conditions, was proposed. Based on the location of the target node, we searched for the triangle or tetrahedron surrounding the target node and designed the localization algorithm in stages to accurately calculate the coordinate value of the target. The relationship between the number of target nodes and the number of generated graphs was analysed through numerous experiments, and the proposed 2D localization algorithm was verified by extending it the 3D coordinate system. Experimental results revealed that the proposed algorithm can effectively improve the flexibility of the anchor node layout and target localization accuracy.


---

## Body

## 1. Introduction

With the rapid development of wireless communication technology and small embedded devices, WSNs have been used in numerous applications, such as target localization [1], environmental monitoring [2], smart factories [3], and agriculture and field habitat monitoring [4]. In practice, sensor network technology is used to monitor and collect data on specific targets in the area of interest.The precise location coordinates of the target are critical for target monitors, and the data are analysed in data centres. For example, in sensitive areas involving rescue operations, the precise location of the target is first obtained. Typically, the location coordinates of the monitored target are unknown. Therefore, designing a scheme in which a WSN is used to accurately locate the target and constantly adjust the state when the location of the target moves is critical. Furthermore, the calculation efficiency of the proposed algorithm and the energy consumption of the nodes should be balanced. The accuracy of the positioning and comprehensive performance of the algorithm determines the quality of the localization method. GPS positioning systems can achieve high accuracy, but the systems are not suitable for indoor environments and complex areas. When the location information of the target is determined using WSNs, the trajectory of the target can be estimated and drawn by combining related algorithms. The performance of positioning technology or methods markedly affects the localization accuracy and monitoring quality of WSNs.Localization schemes are typically classified into distance-based localization schemes and distance-free localization schemes [5]. In distance-based localization scheme, the distance between the unknown node and the anchor node is estimated, whereas in the distance-free localization scheme, the location of the unknown node on the premise of uncertain distance is calculated [6]. Generally, the distance-based localization scheme exhibits a high localization accuracy, but its algorithm complexity is high, which requires computation. The distance-independent location scheme has low localization accuracy and low algorithm complexity. Range-based localization methods have been widely studied. The signal time of arrival (TOA) [7], time difference of arrival (TDOA) [8], angle of arrival (AOA) [9, 10], and received signal strength (RSS) are calculated. The ranging method based on TOA technology is simple, but it requires considerable hardware performance, numerous computations, and high equipment costs. The TDOA method is an improvement of the TOA method and can accurately measure the coordinates of the target. However, this method requires two transmission signals of different rates, which results in a large operating overhead for the network. In addition, the AOA method must calculate the angle between the transmitting and receiving ends and must communicate and transmit in a line-of-sight environment. Therefore, the AOA is not suitable for precise locations in WSNs. The development of low-cost, fast calculation speed, and accurate localization methods is critical in WSN monitoring. Received signal strength indicator- (RSSI-) based localization methods have been widely used and commercialized [11–13]. The lost power between the transmitted and received power can thus be converted and calculated using a mathematical model. Furthermore, equipment hardware for WSN node localization using the RSSI method is commercialized and does not require additional separate components. RSSI-based localization technology is suitable for low-cost, high-precision, and large-scale WSNs.The triangulation method has been studied in detail in fields, such as WSN coverage, routing algorithms, and localization, which optimise the node network layout and construct an optimal triangulation network. Therefore, the aim of this study is to optimise the location distribution of sensor nodes, improve the localization accuracy and performance of the localization algorithm, and extend it to the 3D coordinate system for testing.(1)
To solve the problems of layout optimization and low localization accuracy of anchor nodes occurring in conventional localization methods, the Delaunay triangulation method was introduced, and a localization scheme was designed to estimate the location coordinates of the target(2)
Based on the location of the target node, its surrounding triangle or tetrahedron were searched, and the location algorithm was designed in stages to accurately calculate the coordinate value of the target. The relationship between the number of target nodes and the number of generated graphs was analysed through numerous experiments, and the proposed 2D algorithm was verified by extending it to the 3D coordinate system(3)
We designed an experimental simulation and algorithm comparison and conducted numerous experiments with various parameters to verify the localization accuracy and reliability of the algorithmThe related work is reviewed in Section2. In Section 3, the RSS channel model is presented, and related problems are described. The strategy we propose is detailed in Sections 4 and 5. In Sections 6 and 7, relevant experimental verification and algorithm comparison are designed. Concluding remarks alongside the future work are given in last section.


## 2. Related Works

The deployment method and algorithm design of anchor nodes are a research focus of target localization. In experiment tests performed by many researchers, the coordinate location distribution of anchor nodes generally occurs in the shape of a square, rectangle, and triangle [14–16]. Therefore, before experimentation, it is necessary to fix the location of the node in advance. If the location of the anchor node changed, the localization accuracy calculated also changed. Therefore, the fixed deployment mode of the anchor node is not suitable for the environment where nodes are randomly deployed.Among the localization algorithm distance-based measurement, the most typical algorithms include the trilateral centroid localization, triangular measurement, least square method, and hyperbola localization algorithm. The trilateral centroid localization method has a small number of nodes and a low accuracy of target localization and is not suitable for 3D. The triangular measurement method needs to calculate the angle between the target and node, which undoubtedly increased cost. In [17], the author proposed a new sensor node localization scheme that improved the RSSI algorithm by considering power transmission and reception parameters to estimate the initial location of the node. A genetic algorithm is used to minimize the localization error, and the optimized coordinates are obtained by combining mutation and crossover operators. However, the layout optimization of the nodes is not considered, and the test environment is not suitable for 3D coordinates. In [18], two localization algorithms were designed based on anchor nodes, H-V scanning and diagonal localization algorithms, to estimate the coordinates of sensor nodes in the monitoring area. Among these algorithms, the diagonal localization algorithm belongs to the RSSI-based localization technology which can improve the localization accuracy of unknown nodes. However, the layout of anchor nodes is not sufficiently flexible to adjust dynamically according to the number of nodes, which may lead to nonsystematic errors. This method is suitable for 2D localization conditions but lacks a test of the real dimension. [19] proposed a robust ranging method to track the location of the target and used the trilateral localization method based on RSSI ranging. Consequently, the author reports the result of applying the trilateral localization technology to the measuring point and calculates the distance error between the ideal measuring point and measuring point through computer simulation. However, the computation speed of the trilateral localization method is slow, and the localization error is not accurate. In [20], the authors proposed a non-site-specific algorithm to better estimate the relationship between the RSS and distance. The author selected the most appropriate RSS value in the original RSS values through an algorithm to reduce the outlier effect, thereby ensuring the consistency between the RSS and distance relationship. In [21], the authors analysed the influence of two types of environmental interference on the RSSI value, used Kalman filter to preprocess the RSSI, and proposed a triangle centroid localization algorithm based on weighted feature points. Experiments reveal that higher localization accuracy can be achieved, but its network did not have the characteristics of a self-organizing layout and is not suitable for 3D localization. In [14], to improve the precision of inside localization and optimize the allocation of node resources in WSNs, an equal-arc trilateral localization algorithm based on RSSI is proposed from the perspective of increasing measurement precision and bettering beacon nodes layout. Compared with the square layout, the triangle layout, and the improved triangle layout, the localization accuracy of this algorithm increased by 81%, 54%, and 48%, respectively. Finally, the author revealed that the proposed equal-arc triangulation algorithm can improve the localization accuracy and reasonably control sensor costs. However, in many applications, anchor nodes usually must be self-deployed for layout, and it is not possible to prespecify whether the layout of anchor nodes is square or other shapes. Delaunay triangulation has the optimal partition mode and geometric characteristics and is applied in the research direction of geometric routing, location, coverage, segmentation, data storage, and processing [22]. Li et al. [23] proposed a simple yet effective segmentation-based approach to detect trunk position and Delaunay triangulation (DT) geometry-based localization method for autonomous robots navigating in a forest environment. Experiments show the proposed method reach accurate global localization precision without a good initial pose or GPS signal.The Delaunay division method can optimize the layout of 2D nodes, and applies to the network layout of 3D sensor nodes, based on the location coordinates of the nodes. Delaunay triangle segmentation can improve the flexibility of node layout and strengthen the correlation between anchor nodes. Therefore, we used the Delaunay partition method to optimize the Delaunay network layout for randomly deployed anchor nodes. Consequently, methods are designed to accurately estimate the coordinates of the target in 2D and 3D.


## 3. RSSI Ranging Principle and Problem Description

### 3.1. RSSI Ranging Principle

WSN localization methods are categorised into two ranging localization and localization without ranging depending on whether to measure the received signal and the transmitted signal is necessary. Localization technologies based on ranging primarily include TOA, TDOA, RSSI, and AOA. However, considering comprehensive indicators such as hardware cost, network computing power, and localization accuracy, the technical method based on RSSI is primarily used, combined with the improved localization algorithm to accurately locate the target. The primary principle of using RSSI ranging technology is used to establish a signal loss or attenuation model in the propagation process to estimate the distance between the transmitter and receiver. As displayed in Figure1, the red line represents the waveform of the signal intensity varying with the distance under the ideal path loss model, and the blue line represents the waveform of the signal interference in the environment.Figure 1
Schematic of the loss during RSS signal propagation.The localization algorithm based on the path loss model is used to determine the parameters of the path loss model according to the received RSSI data, and the model is used to estimate the distance value or further processing. We assume that the number of RSSIs received isM, and the RSSI value i received by node k is RSSIs,i[24]. Distance estimation was then performed based on the statistical RSSI measurement model.
(1)RSSIk,i=Pk−10ηklogdk+vk,i,where dk is the distance between the target and the anchor node k; Pk and ηk are the RSSI path loss model parameters of the anchor node k; and vk,i is a zero-mean Gaussian random distribution variable whose variance is equal to σk.
(2)dk=10Ak−RSSIk/10ηk.The noise in the model obeys a Gaussian distribution, and the generated random variables are processed using the average value. When estimating the distance, the median value of a set of RSSI data is used for estimationRSSIk¯=RSSIk=MedianRSSIk,i,i=1,⋯,M. The median value processing method was used to eliminate the random error of the original RSSI data, where RSSIk¯ represents the median value of the RSSI data collected by the anchor node k, which can be expressed as follows.
(3)RSSIk¯=1M∑i=1MRSSIk,i.During propagation, the RSSI obeys the Gaussian distributionNμ,σ2 of the mathematical expectation μ and variance σ. The probability density function for any RSSI value is expressed as follows:
(4)fRSSIk¯=1σ2πe−RSSIk¯−μ/2σ2,where the specific expressions of μ and σ are as follows:
(5)μ=1M∑i=1MRSSIk,i,σ2=1M∑i=1MRSSIk,i−μ2.In the subsequent experimental verification process, after multiple sets of distance values measured by the anchor node, the localization method or algorithm is used to achieve an accurate estimation of the location of the target.


### 3.2. Problem Description

The method of using RSSI to determine the target distance is the first step in localization. Next, an efficient localization algorithm is designed to estimate the location coordinates of the target node. In the conventional method, a trilateral centroid localization algorithm with low power consumption and fast measurement speed is used to solve the coordinates of the target. As displayed in Figure2, the location coordinate of the node Txt,yt,zt to be tested is considered T, and the coordinates of the three anchor nodes, A, B, and C are Ax1,y1,z1, Bx2,y2,z2, and Cx3,y3,z3, respectively. Thus, the principle of trilateral measurement is that the distances between the three anchor nodes of A, B, and C to the target T are ra, rb, and rc. Consequently, the circles formed by their respective measured radii intersect at a point T, and then, the location coordinates of the point T can be determined by establishing a system of equations.Figure 2
Three-sided positioning.However, in the test, the radii of pointsra, rb, and rc are ra, rb, and rc, respectively, and their three circles cannot intersect at one point. As displayed in Figures 3 and 4, when the circles formed using the radii did not intersect at one point, Bulusu et al. [25] assumed axa1,ya1,zz1, bxb1,yb1,zb1, and cxc1,yc1,zc1 as the intersection points formed by them. Next, determine the centre of mass of the three coordinates as the target coordinates. Thus, the approximate target coordinate value T can be obtained by calculation, and T=xa1+xb1+xc1/3,xa2+xb2+xc2/3,xa3+xb3+xc3/3 is calculated. However, the accuracy of the unknown target coordinates estimated by the trilateral centroid localization algorithm is not high, particularly when a certain height difference exists between the transmitter and receiver. In the calculation process for trilateral centroid localization, constraints should be considered, which is not conducive to large-scale network operations.Figure 3
Intersect inside.Figure 4
External intersection.


## 3.1. RSSI Ranging Principle

WSN localization methods are categorised into two ranging localization and localization without ranging depending on whether to measure the received signal and the transmitted signal is necessary. Localization technologies based on ranging primarily include TOA, TDOA, RSSI, and AOA. However, considering comprehensive indicators such as hardware cost, network computing power, and localization accuracy, the technical method based on RSSI is primarily used, combined with the improved localization algorithm to accurately locate the target. The primary principle of using RSSI ranging technology is used to establish a signal loss or attenuation model in the propagation process to estimate the distance between the transmitter and receiver. As displayed in Figure1, the red line represents the waveform of the signal intensity varying with the distance under the ideal path loss model, and the blue line represents the waveform of the signal interference in the environment.Figure 1
Schematic of the loss during RSS signal propagation.The localization algorithm based on the path loss model is used to determine the parameters of the path loss model according to the received RSSI data, and the model is used to estimate the distance value or further processing. We assume that the number of RSSIs received isM, and the RSSI value i received by node k is RSSIs,i[24]. Distance estimation was then performed based on the statistical RSSI measurement model.
(1)RSSIk,i=Pk−10ηklogdk+vk,i,where dk is the distance between the target and the anchor node k; Pk and ηk are the RSSI path loss model parameters of the anchor node k; and vk,i is a zero-mean Gaussian random distribution variable whose variance is equal to σk.
(2)dk=10Ak−RSSIk/10ηk.The noise in the model obeys a Gaussian distribution, and the generated random variables are processed using the average value. When estimating the distance, the median value of a set of RSSI data is used for estimationRSSIk¯=RSSIk=MedianRSSIk,i,i=1,⋯,M. The median value processing method was used to eliminate the random error of the original RSSI data, where RSSIk¯ represents the median value of the RSSI data collected by the anchor node k, which can be expressed as follows.
(3)RSSIk¯=1M∑i=1MRSSIk,i.During propagation, the RSSI obeys the Gaussian distributionNμ,σ2 of the mathematical expectation μ and variance σ. The probability density function for any RSSI value is expressed as follows:
(4)fRSSIk¯=1σ2πe−RSSIk¯−μ/2σ2,where the specific expressions of μ and σ are as follows:
(5)μ=1M∑i=1MRSSIk,i,σ2=1M∑i=1MRSSIk,i−μ2.In the subsequent experimental verification process, after multiple sets of distance values measured by the anchor node, the localization method or algorithm is used to achieve an accurate estimation of the location of the target.


## 3.2. Problem Description

The method of using RSSI to determine the target distance is the first step in localization. Next, an efficient localization algorithm is designed to estimate the location coordinates of the target node. In the conventional method, a trilateral centroid localization algorithm with low power consumption and fast measurement speed is used to solve the coordinates of the target. As displayed in Figure2, the location coordinate of the node Txt,yt,zt to be tested is considered T, and the coordinates of the three anchor nodes, A, B, and C are Ax1,y1,z1, Bx2,y2,z2, and Cx3,y3,z3, respectively. Thus, the principle of trilateral measurement is that the distances between the three anchor nodes of A, B, and C to the target T are ra, rb, and rc. Consequently, the circles formed by their respective measured radii intersect at a point T, and then, the location coordinates of the point T can be determined by establishing a system of equations.Figure 2
Three-sided positioning.However, in the test, the radii of pointsra, rb, and rc are ra, rb, and rc, respectively, and their three circles cannot intersect at one point. As displayed in Figures 3 and 4, when the circles formed using the radii did not intersect at one point, Bulusu et al. [25] assumed axa1,ya1,zz1, bxb1,yb1,zb1, and cxc1,yc1,zc1 as the intersection points formed by them. Next, determine the centre of mass of the three coordinates as the target coordinates. Thus, the approximate target coordinate value T can be obtained by calculation, and T=xa1+xb1+xc1/3,xa2+xb2+xc2/3,xa3+xb3+xc3/3 is calculated. However, the accuracy of the unknown target coordinates estimated by the trilateral centroid localization algorithm is not high, particularly when a certain height difference exists between the transmitter and receiver. In the calculation process for trilateral centroid localization, constraints should be considered, which is not conducive to large-scale network operations.Figure 3
Intersect inside.Figure 4
External intersection.


## 4. WSN Target Localization Algorithm Based on 2D Delaunay

### 4.1. Building a 2D Delaunay Network

In the Delaunay method, the region is divided according to the location of the node and a triangular network with an optimal layout is generated. According to the properties of Voronoi [26] and Delaunay [27], only the neighbouring nodes corresponding to the adjacent edges of Voronoi generate the corresponding triangle network, and the vertices of the triangle are composed of the nodes in the Voronoi unit body and its neighbouring nodes. In a nutshell, the vertices of each triangle in the Delaunay triangle network are composed of the three nearest nodes, and each side of the triangle will not intersect. Therefore, the construction of Delaunay triangulation will markedly reduce the localization time of anchor nodes and improve localization accuracy.As shown in Figure5, 70 anchor nodes si were randomly located on the plane L with an area of SL, and the red dots represent the anchor nodes. Next, we used the Delaunay method to divide the area according to the 70 node coordinates sixi,yi,zi. In Figure 6, the area divided by Delaunay is a triangular network composed of triangles NΔ with various shapes. After the calculations are completed, in area L, the number of triangles NΔ depends on the location coordinate sixi,yi,zi of the node and the number of nodes n. Thus, the greater the number of nodes is, the more triangles NΔ are generated.Figure 5
Randomly generate anchor nodes.Figure 6
Two-dimensional Delaunay division.Initially, the number of randomly deployed nodes in areaL=200×200 was n (n=100), and the number of triangles in the Delaunay triangulation obtained from the test was NΔ=184. The number of triangles was proportional to n, as listed in Table 1, which revealed the number of triangles generated by the Delaunay method when n has different values. Table 1 indicates that as the number of nodes increases, the number of triangles generated increases accordingly. Second, the total area S0 of the formed Delaunay graph also changed with the number of nodes and location coordinates. Consequently, as the number of nodes n increased, the total area S0 of Delaunay also increased, and its area ratio S0/SL gradually approached 100%.Table 1
Change in the number of anchor nodes.
LnN△S0 (m2)S0/SL200×20030502937473.44%200×20050893446086.15%200×200701263055287.63%200×2001001843683992.10%200×2001502833693392.33%200×2002003833724593.11%200×2003005813781094.53%


### 4.2. Determining the Target Surrounded by Triangles

First, the coordinates of the nodes were divided using the Delaunay method, and the inner coordinates of each triangle were determined. The distance between the target and vertices of the triangle was calculated to determine the triangle surrounded by the target. The coordinates of the target are unknown; thus, the judgement method is the core step of positioning. In Figure7, five black dots represent five nodes with unknown coordinates. The coordinates of these five targets are: (127,135), (150,150), (145,170), (90,170), and (42,130). In a test, the coordinates of an unknown target cannot be determined in advance. Therefore, determining the triangle surrounded by the target is difficult. To address this problem, the area ratio method was used.Figure 7
Set the location of the target.Figures8 and 9, display a partial diagram of a certain part of the Delaunay triangulation. The coordinates of triangles and △ABC and △BCD are known and are Ax1,y1, Bx2,y2, Cx3,y3, and Dx4,y4, respectively. Because the coordinates of the target T are unknown, the distances between the four points A, B, C, D, and T can be measured by Equation (2) as dAT, dBT, dCT, and dDT, respectively. Therefore, determining whether T is in △ABC or inside the triangle △BCD is the key in this method.Figure 8
T is inside △ABC.Figure 9
T is outside △ABC.If pointT is inside the triangle △ABC, then the area of the small triangle formed by T and △ABC satisfies the following conditions: SΔABT+SΔACT+SΔBCT≤SΔABC. If point T is not inside the triangle ΔABC, then it satisfies SΔABT+SΔACT+SΔBCT>SΔABC. The area of SΔABC can be calculated using Equation (8), and the area of the small triangle SΔABT, SΔACT, SΔBCT can be calculated using Helen formula as follows:
(6)S=14d1+d2+d3d1+d2−d3d1+d3−d2d2+d3−d1,where d1, d2, and d3 are the distances between the vertices of targets T and ΔABC.Thus, the targetT can be estimated to be specifically located in a certain triangle in the Delaunay triangulation, and a corresponding localization method can be designed to calculate the coordinates of target T. Next, the subsequent localization method is implemented in stages in a real situation.


### 4.3. WSN Localization Algorithm Based on 2D Delaunay Partition

After this analysis, a target localization algorithm based on 2D Delaunay partitioning (2D-DPTL) was proposed, which is categorised into two stages to accurately locate the target.Stage 1. When the number of anchor nodes is large, method 1 is used for localization.Method 1. First, the number of known nodesn is randomly deployed in a plane with an area of L size. Then, the corresponding Delaunay triangulation is generated according to the position coordinates of the known node sixi,yi (i=1,2,⋯,n). Thus, in the first step, the judgement method described in the previous section is used to determine a triangle surrounded by T. Next, we calculated and generated the inner coordinates sjxj,yj corresponding to each Delaunay triangle. The coordinates of the inner point of the triangle can be calculated using the following expression:
(7)sjxj,yj=aixi+bixi+1+cixi+2ai+bi+ci,aiyi+biyi+1+ciyi+2ai+bi+ci,where ai, bi, and ci are the side lengths of the triangle and xi,yi, xi+1,yi+1, and xi+2,yi+2 represent the vertices of the triangle corresponding to the inner centre.As displayed in Figure10, the blue five-pointed star represents the inner point of each triangle in the Delaunay triangle network, and its number is equal to the number NΔ of triangles. The coordinates of each inner point are numbered, and the figure reveals that 126 inner points exist in total. Based on this method, the triangle surrounded by the target and its corresponding inner coordinates were determined. The red triangles in Figure 11 indicate the respective areas corresponding to the five target points. Next, the area ratio Sk=Sj/Sm of the triangle to which the target Tfxf,yf belongs is calculated. We assume that the area of all triangles is Sj,j=1,2,⋯,NΔ, and the median Sm=Sj+1,j=1,2,⋯,NΔ/2 or Sm=Sj+1/2+Sj/2+1,j=1,2,⋯,NΔ/2 area of the triangle is obtained. If Sj≤Sm, then the inner coordinate Gjxj,yj of the triangle is considered to be the estimated coordinate of the target Tfxf,yf (i.e., Tfxf,yf=sjxj,yj). If Sj>Sm, the centre of the triangle is used as the estimated value of T. However, this results in a large error. Thus, method 2 in stage 2 was used.Figure 10
Drawing the inner point of each triangle.Figure 11
Finding the triangle surrounded by the target.Stage 2. When the number of anchor nodes is small, method 2 is used for localization.Method 2. When the number of anchor nodes is small, the number of triangles divided by Delaunay is small. Consequently, the areaSj,j=1,2,⋯,NΔ of the triangle where the target is located is too large, and the accuracy of using the inner coordinates in method 1 as target’s estimated coordinates is too low. Therefore, in the first step, the method in phase 1 is used to determine the area ratio. Next, the calculated inner point Gj connects the vertex coordinates of the triangles A, B, and C to which it belongs and divides it into three small triangles, as illustrated in Figure 12, which are composed of green lines. We subsequently calculated the inner coordinates G1x4,y4 of the small triangle where the target is located. As displayed in Figure 13, the three points A, B, and C represent a triangle formed in the Delaunay triangulation network, Gx0,y0 represents its inner centre, and G1x4,y4 represents the inner coordinate of the small triangle △BCG. Thus, the coordinates of G1x4,y4 can be selected as the estimated coordinates of the target point T (i.e., G1x4,y4=Tfxf,yf), when the area ratio of the area Sl,l=1,2,⋯,NL of the small triangle △BCG to the area of S is Sl/S≤1. For example, the area ΔBCG of a triangle SΔ can be calculated using Equation (8), and SΔ is a positive value (usually the absolute value SΔ).
(8)SΔ=12x1y11x2y21x3y31=12x1y2+x2y3+y1x3−x3y2−x2y1−x1y3.Figure 12
Delaunay second division.Figure 13
Partial schematic.If the ratio of the areaSl,l=1,2,⋯,NL of the small triangle △BCG where the target is located into the area of Sm satisfies the condition Sl/Sm>1, the least squares method is used for calculation. We assumed that T is inside △BCG and used Equation (2) to measure the distance between each vertex of the small triangle △BCG and Tfxf,yf; thus, d1=dT1G, d2=dT1C, and d3=dT1B. The coordinates of the three vertices of △BCG are Gx0,y0, Bx3,y3, and Cx2,y2. Therefore, the following equations can be established:
(9)x0−xf2+y0−yf2=d1,x2−xf2+y2−yf2=d2,x3−xf2+y3−yf2=d3.Then, by subtractingd3 from d1 and d2 in Equation (9), the following equation can be obtained:
(10)x02−x32−2x0−x3xf+y02−y32−2yfy0−y3=d12−d32,x22−x32−2x2−x3xf+y22−y32−2yfy2−y3=d22−d32.Equation ((11) can be expressed as a linear equation [28].
(11)HX=b.Among them,(12)H=2x0−x32y0−y32x2−x32y2−y3,X=xfyf,andb=x02−x32+y02−y32+d32−d12x22−x32+y22−y32+d32−d22.Thus, the coordinate ofT can be solved by the following expression:
(13)X~=HTH−1HTb.However, the distanced1=dT1G from the target T to the inner heart Gx0,y0 could not be accurately determined. The distance dG1G is approximately estimated as the distance of d1, that is, dG1G=d1=dT1G. Among them, dG1G can be calculated using equation dG1G=x0−x42+y0−y42.In general, methods 1 and 2 can be used in combination in a real localization process. The proposed 2D Delaunay target localization method can locate the target quickly according to the number of nodes.


## 4.1. Building a 2D Delaunay Network

In the Delaunay method, the region is divided according to the location of the node and a triangular network with an optimal layout is generated. According to the properties of Voronoi [26] and Delaunay [27], only the neighbouring nodes corresponding to the adjacent edges of Voronoi generate the corresponding triangle network, and the vertices of the triangle are composed of the nodes in the Voronoi unit body and its neighbouring nodes. In a nutshell, the vertices of each triangle in the Delaunay triangle network are composed of the three nearest nodes, and each side of the triangle will not intersect. Therefore, the construction of Delaunay triangulation will markedly reduce the localization time of anchor nodes and improve localization accuracy.As shown in Figure5, 70 anchor nodes si were randomly located on the plane L with an area of SL, and the red dots represent the anchor nodes. Next, we used the Delaunay method to divide the area according to the 70 node coordinates sixi,yi,zi. In Figure 6, the area divided by Delaunay is a triangular network composed of triangles NΔ with various shapes. After the calculations are completed, in area L, the number of triangles NΔ depends on the location coordinate sixi,yi,zi of the node and the number of nodes n. Thus, the greater the number of nodes is, the more triangles NΔ are generated.Figure 5
Randomly generate anchor nodes.Figure 6
Two-dimensional Delaunay division.Initially, the number of randomly deployed nodes in areaL=200×200 was n (n=100), and the number of triangles in the Delaunay triangulation obtained from the test was NΔ=184. The number of triangles was proportional to n, as listed in Table 1, which revealed the number of triangles generated by the Delaunay method when n has different values. Table 1 indicates that as the number of nodes increases, the number of triangles generated increases accordingly. Second, the total area S0 of the formed Delaunay graph also changed with the number of nodes and location coordinates. Consequently, as the number of nodes n increased, the total area S0 of Delaunay also increased, and its area ratio S0/SL gradually approached 100%.Table 1
Change in the number of anchor nodes.
LnN△S0 (m2)S0/SL200×20030502937473.44%200×20050893446086.15%200×200701263055287.63%200×2001001843683992.10%200×2001502833693392.33%200×2002003833724593.11%200×2003005813781094.53%


## 4.2. Determining the Target Surrounded by Triangles

First, the coordinates of the nodes were divided using the Delaunay method, and the inner coordinates of each triangle were determined. The distance between the target and vertices of the triangle was calculated to determine the triangle surrounded by the target. The coordinates of the target are unknown; thus, the judgement method is the core step of positioning. In Figure7, five black dots represent five nodes with unknown coordinates. The coordinates of these five targets are: (127,135), (150,150), (145,170), (90,170), and (42,130). In a test, the coordinates of an unknown target cannot be determined in advance. Therefore, determining the triangle surrounded by the target is difficult. To address this problem, the area ratio method was used.Figure 7
Set the location of the target.Figures8 and 9, display a partial diagram of a certain part of the Delaunay triangulation. The coordinates of triangles and △ABC and △BCD are known and are Ax1,y1, Bx2,y2, Cx3,y3, and Dx4,y4, respectively. Because the coordinates of the target T are unknown, the distances between the four points A, B, C, D, and T can be measured by Equation (2) as dAT, dBT, dCT, and dDT, respectively. Therefore, determining whether T is in △ABC or inside the triangle △BCD is the key in this method.Figure 8
T is inside △ABC.Figure 9
T is outside △ABC.If pointT is inside the triangle △ABC, then the area of the small triangle formed by T and △ABC satisfies the following conditions: SΔABT+SΔACT+SΔBCT≤SΔABC. If point T is not inside the triangle ΔABC, then it satisfies SΔABT+SΔACT+SΔBCT>SΔABC. The area of SΔABC can be calculated using Equation (8), and the area of the small triangle SΔABT, SΔACT, SΔBCT can be calculated using Helen formula as follows:
(6)S=14d1+d2+d3d1+d2−d3d1+d3−d2d2+d3−d1,where d1, d2, and d3 are the distances between the vertices of targets T and ΔABC.Thus, the targetT can be estimated to be specifically located in a certain triangle in the Delaunay triangulation, and a corresponding localization method can be designed to calculate the coordinates of target T. Next, the subsequent localization method is implemented in stages in a real situation.


## 4.3. WSN Localization Algorithm Based on 2D Delaunay Partition

After this analysis, a target localization algorithm based on 2D Delaunay partitioning (2D-DPTL) was proposed, which is categorised into two stages to accurately locate the target.Stage 1. When the number of anchor nodes is large, method 1 is used for localization.Method 1. First, the number of known nodesn is randomly deployed in a plane with an area of L size. Then, the corresponding Delaunay triangulation is generated according to the position coordinates of the known node sixi,yi (i=1,2,⋯,n). Thus, in the first step, the judgement method described in the previous section is used to determine a triangle surrounded by T. Next, we calculated and generated the inner coordinates sjxj,yj corresponding to each Delaunay triangle. The coordinates of the inner point of the triangle can be calculated using the following expression:
(7)sjxj,yj=aixi+bixi+1+cixi+2ai+bi+ci,aiyi+biyi+1+ciyi+2ai+bi+ci,where ai, bi, and ci are the side lengths of the triangle and xi,yi, xi+1,yi+1, and xi+2,yi+2 represent the vertices of the triangle corresponding to the inner centre.As displayed in Figure10, the blue five-pointed star represents the inner point of each triangle in the Delaunay triangle network, and its number is equal to the number NΔ of triangles. The coordinates of each inner point are numbered, and the figure reveals that 126 inner points exist in total. Based on this method, the triangle surrounded by the target and its corresponding inner coordinates were determined. The red triangles in Figure 11 indicate the respective areas corresponding to the five target points. Next, the area ratio Sk=Sj/Sm of the triangle to which the target Tfxf,yf belongs is calculated. We assume that the area of all triangles is Sj,j=1,2,⋯,NΔ, and the median Sm=Sj+1,j=1,2,⋯,NΔ/2 or Sm=Sj+1/2+Sj/2+1,j=1,2,⋯,NΔ/2 area of the triangle is obtained. If Sj≤Sm, then the inner coordinate Gjxj,yj of the triangle is considered to be the estimated coordinate of the target Tfxf,yf (i.e., Tfxf,yf=sjxj,yj). If Sj>Sm, the centre of the triangle is used as the estimated value of T. However, this results in a large error. Thus, method 2 in stage 2 was used.Figure 10
Drawing the inner point of each triangle.Figure 11
Finding the triangle surrounded by the target.Stage 2. When the number of anchor nodes is small, method 2 is used for localization.Method 2. When the number of anchor nodes is small, the number of triangles divided by Delaunay is small. Consequently, the areaSj,j=1,2,⋯,NΔ of the triangle where the target is located is too large, and the accuracy of using the inner coordinates in method 1 as target’s estimated coordinates is too low. Therefore, in the first step, the method in phase 1 is used to determine the area ratio. Next, the calculated inner point Gj connects the vertex coordinates of the triangles A, B, and C to which it belongs and divides it into three small triangles, as illustrated in Figure 12, which are composed of green lines. We subsequently calculated the inner coordinates G1x4,y4 of the small triangle where the target is located. As displayed in Figure 13, the three points A, B, and C represent a triangle formed in the Delaunay triangulation network, Gx0,y0 represents its inner centre, and G1x4,y4 represents the inner coordinate of the small triangle △BCG. Thus, the coordinates of G1x4,y4 can be selected as the estimated coordinates of the target point T (i.e., G1x4,y4=Tfxf,yf), when the area ratio of the area Sl,l=1,2,⋯,NL of the small triangle △BCG to the area of S is Sl/S≤1. For example, the area ΔBCG of a triangle SΔ can be calculated using Equation (8), and SΔ is a positive value (usually the absolute value SΔ).
(8)SΔ=12x1y11x2y21x3y31=12x1y2+x2y3+y1x3−x3y2−x2y1−x1y3.Figure 12
Delaunay second division.Figure 13
Partial schematic.If the ratio of the areaSl,l=1,2,⋯,NL of the small triangle △BCG where the target is located into the area of Sm satisfies the condition Sl/Sm>1, the least squares method is used for calculation. We assumed that T is inside △BCG and used Equation (2) to measure the distance between each vertex of the small triangle △BCG and Tfxf,yf; thus, d1=dT1G, d2=dT1C, and d3=dT1B. The coordinates of the three vertices of △BCG are Gx0,y0, Bx3,y3, and Cx2,y2. Therefore, the following equations can be established:
(9)x0−xf2+y0−yf2=d1,x2−xf2+y2−yf2=d2,x3−xf2+y3−yf2=d3.Then, by subtractingd3 from d1 and d2 in Equation (9), the following equation can be obtained:
(10)x02−x32−2x0−x3xf+y02−y32−2yfy0−y3=d12−d32,x22−x32−2x2−x3xf+y22−y32−2yfy2−y3=d22−d32.Equation ((11) can be expressed as a linear equation [28].
(11)HX=b.Among them,(12)H=2x0−x32y0−y32x2−x32y2−y3,X=xfyf,andb=x02−x32+y02−y32+d32−d12x22−x32+y22−y32+d32−d22.Thus, the coordinate ofT can be solved by the following expression:
(13)X~=HTH−1HTb.However, the distanced1=dT1G from the target T to the inner heart Gx0,y0 could not be accurately determined. The distance dG1G is approximately estimated as the distance of d1, that is, dG1G=d1=dT1G. Among them, dG1G can be calculated using equation dG1G=x0−x42+y0−y42.In general, methods 1 and 2 can be used in combination in a real localization process. The proposed 2D Delaunay target localization method can locate the target quickly according to the number of nodes.


## 5. WSN Target Localization Algorithm Based on 3D Delaunay

The proposed 2D WSN localization algorithm of the Delaunay division were extended to 3D. 3D localization algorithms are suitable for practical applications. The trilateral localization method can be used to determine the approximate coordinates of the target but cannot be used to measure the height of thez-axis. Therefore, referring to the localization method in Section 5.3, the 3D localization algorithm was designed according to various stages.


### 5.1. Three-Dimensional Space Divided by Delaunay

According to the content in Section4, the Delaunay method is used to divide the coordinate points in the 2D plane, and the Delaunay figure obtained is a network composed of many triangles. When the Delaunay method is used to divide n the node 3D coordinates, the resulting graph is a 3D network composed of NN>n tetrahedrons. As displayed in Figure 14, 100 anchor nodes are randomly deployed in a space of 200 m3, and the blue solid dots represent nodes with known coordinates. Next, the location coordinates of these 100 nodes are divided using the Delaunay method, and the 12 edge lengths of cube 200 m3 were set as constrained edges. As displayed in Figure 15, the black 3D graphic network was composed of many tetrahedrons with different volumes. Comparing the graphs divided by the 2D Delaunay and 2D Delaunay methods reveals that the 2D Delaunay diagram is consisting of a triangular network composed of multiple small triangles, and the 3D Delaunay diagram is a 3D network consisting of multiple tetrahedrons. When the coordinate value of the node is fixed, the generated Delaunay network is unique.Figure 14
Randomly deploy nodes.Figure 15
Delaunay divides the 3D space.The analysis revealed that the density of the triangular network or the 3D network after Delaunay is primarily determined by the number of nodes. Therefore, the data in Table2 are used to verify the relationship between the 3D area size L, the number of nodes n, and the number of tetrahedrons N formed under the given conditions of the node coordinates.Table 2
Verifying the relationship between the number of nodes and other variables.
LnNV (m3)V/V0LnNV (m3)V/V0200×200×2001005125.3744e+0667.18%200×200×201004835.3744e+0567.18%200×200×200703274.8725e+0660.91%200×200×20703194.8725e+0560.91%200×200×200502284.3816e+0654.77%200×200×20502114.3816e+0554.77%200×200×20020612.2605e+0628.26%100×100×20703231.2181e+0560.90%200×200×501004791.3436e+0667.18%100×100×20502141.0954e+0554.77%200×200×50703331.2181e+0660.90%100×50×20703196.0906e+0460.91%Table2 denotes that the greater the number of nodes is, the greater the number of tetrahedrons is. Thus, the total volume V of the formed Delaunay graph increases with an increased number of nodes. The number of inner points primarily depends on the number of nodes, and the size of the constraint space has limited effect on it. Many experiments have revealed that the size of V is primarily determined by the number of nodes and the location of nodes. Furthermore, the ratio of the total volume V of the tetrahedron formed by Delaunay to the volume V0 of the deployment area increases as the number of nodes increases. However, the growth of the volume percentage V/V0 was not considerably accelerated, and the volume ratio is low and between 50% and 70%. In Section 6, the distance between nodes is set through experiments to increase the volume ratio and optimise the location distribution of anchor nodes.


### 5.2. Determining Tetrahedron the Target Is In

The basic properties of Delaunay do not change with the increase in dimensionality, but the problems faced by the 3D localization method differ from those of 2D localization. When the coordinates of the nodes are divided using the Delaunay method, the inner centre of each tetrahedron should be calculated. Currently, estimating the location of the targetT in the Delaunay tetrahedral network is the core step of 3D localization. The principle of the judgement strategy is similar to that of the 2D localization method in Section 4, but the method and algorithm to be calculated differ. Assuming that the vertices of each tetrahedron in the divided Delaunay are composed of known anchor nodes, using Equations (1)–(3), the RSSI values of the three transmission points with the strongest signal strength and the four closest distances d4≤k≤6 between the known and unknown nodes can be calculated. Although the coordinates of the target are unknown, judging that T is located inside a certain tetrahedron is the first step in proposing a 3D WSN target localization algorithm.As displayed in Figures16 and 17, the tetrahedron A−BCD represents a certain tetrahedron in the Delaunay 3D network, and E−BCD represents the adjacent tetrahedron. Among these technologies, the coordinates of points A, B, C, D, and E are known and represent known nodes. The coordinate position of the unknown target T is uncertain, but the distance from the vertices A, B, C, D, and E of the tetrahedron can be measured by Equation (2) if dAT, dBT, dCT, dDT, and dET are assumed. If the point T is inside the tetrahedron A−BCD, the sum of the volume V of the tetrahedron formed by the vertices of the target T and A−BCD or T and E−BCD satisfies the condition VABCT+VACDT+VABDT+VBCDT≤VABCDVABET+VAECT+VABCT+VBCET≤VABCE. If the target T is not inside a tetrahedron A−BCD, then VABCT+VACDT+VABDT+VBCDT>VABCD. To calculate the volume A−BCD of the tetrahedron, the corresponding coordinate values are substituted into the Euler tetrahedron Formula (14).
(14)V=161111x1x2x3x4y1y2y3y4z1z2z3z4=16x2−x1y2−y1z2−z1x3−x2y3−y2z3−z2x4−x3y4−y3z4−z3,where xi, yi, and zi are the known vertex coordinates of tetrahedron A−BCD or E−BCD. The coordinates of the target T cannot be directly calculated, but the distance between each vertex of the tetrahedron can be estimated using the RSSI ranging model, which is set as d1, d2, d3, d4, and d5. Therefore, tetrahedron’s edge length formula can be used to calculate the volume, and Equation (15) can be used to calculate the volume Vl of the small tetrahedrons VABCT, VACDT, VABDT, and VBCDT.
(15)Vl2=12880111110d12d22d321d120d42d521d22d420d621d32d52d620.Figure 16
PointT is inside A−BCD.Figure 17
PointT is outside A−BCD.Among these values,Vl is a positive value. Therefore, the corresponding tetrahedral volume can be calculated using Equations (14) and (15) as follows: using the afore-mentioned method, we determined the tetrahedron in the Delaunay network target is inside.


### 5.3. 3D WSN Target Localization Algorithm Based on 3D Delaunay

A novel WSN target localization algorithm based on 3D Delaunay was proposed. According to the relationship between the number of nodes and the number of tetrahedrons after the Delaunay division, the algorithm was designed in two stages. In the first stage, the number of nodes and area range were determined. The number of tetrahedrons generated by the 3D Delaunay method was approximately three times greater than the number formed by the 2D Delaunay method. Therefore, the 3D Delaunay method was more suitable for target localization with many nodes. In the second stage, the number of nodes is small, and the analysis and design are performed with reference to the 2D Delaunay localization method.Stage 1. When the number of nodes is large, the coordinates of the centreI of the tetrahedron are mainly used to estimate the coordinates of the target.Method 1. First, we calculated the inner coordinatesIxi,yi,zi of each tetrahedron. In Figure 18, the red dots represent the inner points of each tetrahedron, the number of which is equal to the number of tetrahedrons. According to the method in Section 5.2, we find the tetrahedron surrounded by the target T and use Equation (16) to calculate the inner coordinates Ixi,yi,zi of the tetrahedron.
(16)x1=S1x1+S2x2+S3x3+S4x4S1+S2+S3+S4,y1=S1y1+S2y2+S3y3+S4y4S1+S2+S3+S4,z1=S1z1+S2z2+S3z3+S4z4S1+S2+S3+S4.Figure 18
Calculating the inner point of a tetrahedron.Assume that the vertex coordinates of the tetrahedron arex1,y1,z1, x2,y2,z2, x3,y3,z3, and x4,y4,z4. Here, Sii=1,2,3,4 represents the side area of the tetrahedron, and the inner point Ixi,yi,zi of the tetrahedron can be calculated using Equation (16). In the experiment, three unknown target coordinates are given. Next, the tetrahedron where the target is located is determined by using the method described in Section 5.2. As displayed in Figure 19, the three black tetrahedrons each contain three targets.Figure 19
Tetrahedron surrounded by target.To avoid selecting the inner points of some tetrahedrons that are too large, the coordinates of the target are assumed to be inaccurate. Therefore, the volume ratio of the tetrahedron was determined to solve the afore-mentioned problem. The volume of all tetrahedrons isVj (j=1,2,⋯,Np), where Np is the number of tetrahedrons. Next, the volume median Vm=Vj+1/2,j=1,3,⋯,Np or Vm=Sj+1/2+Sj/2/2,j=2,4,⋯,Np of the divided tetrahedron was calculated. Assuming that the volume of the tetrahedron in which the target T is located satisfies Vj≤Vm, the tetrahedral centre coordinate Gjxj,yj can be replaced with the coordinate of the target T, that is, Ffxf,yf=Ijxj,yj. Assuming that Vj>Vm, the method in phase 2 is used.Stage 2. When fewer known node coordinates exist, and the formed tetrahedron volume satisfies the conditionVj>Vm, the inner coordinates cannot be estimated as the coordinates of the unknown target.Method 2. WhenVj>Vm is determined in the first step, the coordinates of the target T are directly solved using the least squares method. As displayed in Figures 20 and 21, the red mark indicates target T, and T is inside the A−BCD tetrahedron. When the tetrahedron surrounded by the target T is located for the first time, the least square method combined with the RSSI ranging principle is used to solve the problem with less computation time.Figure 20
T is inside the tetrahedron.Figure 21
Distance fromT to the tetrahedron vertex.Assuming thatT is inside A−BCD, we use Equation (2) to measure the distance between the four vertices of the tetrahedron A−BCD and Tfxf,yf, where d1=AT, d2=BT, d3=CT, and d4=DT. Consequently, the coordinates of the three vertices of △BCG are known, Ax1,y1,z1, Bx2,y2,z2, Cx3,y3,z3, and Dx4,y4,z4, which can be calculated as follows:
(17)x1−xf2+y1−yf2+z1−zf2=d1,x2−xf2+y2−yf2+z2−zf2=d2,x3−xf2+y3−yf2+z3−zf2=d3,x4−xf2+y4−yf2+z4−zf2=d4.Next, subtractd4 from d1, d2, and d3 from Equation (17) to obtain the following expression:
(18)x12−x42−2x1−x4xf+y12−y42−2y1−y4yf+z12−z42−2z1−z4zf=d12−d42,x22−x42−2x2−x4xf+y22−y42−2y2−y4yf+z22−z42−2z2−z4zf=d22−d42,x32−x42−2x3−x4xf+y32−y42−2y3−y4yf+z32−z42−2z3−z4zf=d32−d42.Next, Equation (18) is rewritten as a system of linear equations, similar to Equation (11), where
(19)H=2x1−x42y1−y42z1−z42x2−x42x2−x42z2−z42x3−x42y3−y42z3−z4,X=xfyfzf,and b can be rewritten as a determinant
(20)b=x12−x42+y12−y42+z12−z42=d42−d12x22−x42+y22−y42+z22−z42=d42−d22x32−x42+y32−y42+z32−z42=d42−d32.Thus, Equation (9) is used to calculate the determinant coordinate value of the target T, and then the corresponding value is removed.


## 5.1. Three-Dimensional Space Divided by Delaunay

According to the content in Section4, the Delaunay method is used to divide the coordinate points in the 2D plane, and the Delaunay figure obtained is a network composed of many triangles. When the Delaunay method is used to divide n the node 3D coordinates, the resulting graph is a 3D network composed of NN>n tetrahedrons. As displayed in Figure 14, 100 anchor nodes are randomly deployed in a space of 200 m3, and the blue solid dots represent nodes with known coordinates. Next, the location coordinates of these 100 nodes are divided using the Delaunay method, and the 12 edge lengths of cube 200 m3 were set as constrained edges. As displayed in Figure 15, the black 3D graphic network was composed of many tetrahedrons with different volumes. Comparing the graphs divided by the 2D Delaunay and 2D Delaunay methods reveals that the 2D Delaunay diagram is consisting of a triangular network composed of multiple small triangles, and the 3D Delaunay diagram is a 3D network consisting of multiple tetrahedrons. When the coordinate value of the node is fixed, the generated Delaunay network is unique.Figure 14
Randomly deploy nodes.Figure 15
Delaunay divides the 3D space.The analysis revealed that the density of the triangular network or the 3D network after Delaunay is primarily determined by the number of nodes. Therefore, the data in Table2 are used to verify the relationship between the 3D area size L, the number of nodes n, and the number of tetrahedrons N formed under the given conditions of the node coordinates.Table 2
Verifying the relationship between the number of nodes and other variables.
LnNV (m3)V/V0LnNV (m3)V/V0200×200×2001005125.3744e+0667.18%200×200×201004835.3744e+0567.18%200×200×200703274.8725e+0660.91%200×200×20703194.8725e+0560.91%200×200×200502284.3816e+0654.77%200×200×20502114.3816e+0554.77%200×200×20020612.2605e+0628.26%100×100×20703231.2181e+0560.90%200×200×501004791.3436e+0667.18%100×100×20502141.0954e+0554.77%200×200×50703331.2181e+0660.90%100×50×20703196.0906e+0460.91%Table2 denotes that the greater the number of nodes is, the greater the number of tetrahedrons is. Thus, the total volume V of the formed Delaunay graph increases with an increased number of nodes. The number of inner points primarily depends on the number of nodes, and the size of the constraint space has limited effect on it. Many experiments have revealed that the size of V is primarily determined by the number of nodes and the location of nodes. Furthermore, the ratio of the total volume V of the tetrahedron formed by Delaunay to the volume V0 of the deployment area increases as the number of nodes increases. However, the growth of the volume percentage V/V0 was not considerably accelerated, and the volume ratio is low and between 50% and 70%. In Section 6, the distance between nodes is set through experiments to increase the volume ratio and optimise the location distribution of anchor nodes.


## 5.2. Determining Tetrahedron the Target Is In

The basic properties of Delaunay do not change with the increase in dimensionality, but the problems faced by the 3D localization method differ from those of 2D localization. When the coordinates of the nodes are divided using the Delaunay method, the inner centre of each tetrahedron should be calculated. Currently, estimating the location of the targetT in the Delaunay tetrahedral network is the core step of 3D localization. The principle of the judgement strategy is similar to that of the 2D localization method in Section 4, but the method and algorithm to be calculated differ. Assuming that the vertices of each tetrahedron in the divided Delaunay are composed of known anchor nodes, using Equations (1)–(3), the RSSI values of the three transmission points with the strongest signal strength and the four closest distances d4≤k≤6 between the known and unknown nodes can be calculated. Although the coordinates of the target are unknown, judging that T is located inside a certain tetrahedron is the first step in proposing a 3D WSN target localization algorithm.As displayed in Figures16 and 17, the tetrahedron A−BCD represents a certain tetrahedron in the Delaunay 3D network, and E−BCD represents the adjacent tetrahedron. Among these technologies, the coordinates of points A, B, C, D, and E are known and represent known nodes. The coordinate position of the unknown target T is uncertain, but the distance from the vertices A, B, C, D, and E of the tetrahedron can be measured by Equation (2) if dAT, dBT, dCT, dDT, and dET are assumed. If the point T is inside the tetrahedron A−BCD, the sum of the volume V of the tetrahedron formed by the vertices of the target T and A−BCD or T and E−BCD satisfies the condition VABCT+VACDT+VABDT+VBCDT≤VABCDVABET+VAECT+VABCT+VBCET≤VABCE. If the target T is not inside a tetrahedron A−BCD, then VABCT+VACDT+VABDT+VBCDT>VABCD. To calculate the volume A−BCD of the tetrahedron, the corresponding coordinate values are substituted into the Euler tetrahedron Formula (14).
(14)V=161111x1x2x3x4y1y2y3y4z1z2z3z4=16x2−x1y2−y1z2−z1x3−x2y3−y2z3−z2x4−x3y4−y3z4−z3,where xi, yi, and zi are the known vertex coordinates of tetrahedron A−BCD or E−BCD. The coordinates of the target T cannot be directly calculated, but the distance between each vertex of the tetrahedron can be estimated using the RSSI ranging model, which is set as d1, d2, d3, d4, and d5. Therefore, tetrahedron’s edge length formula can be used to calculate the volume, and Equation (15) can be used to calculate the volume Vl of the small tetrahedrons VABCT, VACDT, VABDT, and VBCDT.
(15)Vl2=12880111110d12d22d321d120d42d521d22d420d621d32d52d620.Figure 16
PointT is inside A−BCD.Figure 17
PointT is outside A−BCD.Among these values,Vl is a positive value. Therefore, the corresponding tetrahedral volume can be calculated using Equations (14) and (15) as follows: using the afore-mentioned method, we determined the tetrahedron in the Delaunay network target is inside.


## 5.3. 3D WSN Target Localization Algorithm Based on 3D Delaunay

A novel WSN target localization algorithm based on 3D Delaunay was proposed. According to the relationship between the number of nodes and the number of tetrahedrons after the Delaunay division, the algorithm was designed in two stages. In the first stage, the number of nodes and area range were determined. The number of tetrahedrons generated by the 3D Delaunay method was approximately three times greater than the number formed by the 2D Delaunay method. Therefore, the 3D Delaunay method was more suitable for target localization with many nodes. In the second stage, the number of nodes is small, and the analysis and design are performed with reference to the 2D Delaunay localization method.Stage 1. When the number of nodes is large, the coordinates of the centreI of the tetrahedron are mainly used to estimate the coordinates of the target.Method 1. First, we calculated the inner coordinatesIxi,yi,zi of each tetrahedron. In Figure 18, the red dots represent the inner points of each tetrahedron, the number of which is equal to the number of tetrahedrons. According to the method in Section 5.2, we find the tetrahedron surrounded by the target T and use Equation (16) to calculate the inner coordinates Ixi,yi,zi of the tetrahedron.
(16)x1=S1x1+S2x2+S3x3+S4x4S1+S2+S3+S4,y1=S1y1+S2y2+S3y3+S4y4S1+S2+S3+S4,z1=S1z1+S2z2+S3z3+S4z4S1+S2+S3+S4.Figure 18
Calculating the inner point of a tetrahedron.Assume that the vertex coordinates of the tetrahedron arex1,y1,z1, x2,y2,z2, x3,y3,z3, and x4,y4,z4. Here, Sii=1,2,3,4 represents the side area of the tetrahedron, and the inner point Ixi,yi,zi of the tetrahedron can be calculated using Equation (16). In the experiment, three unknown target coordinates are given. Next, the tetrahedron where the target is located is determined by using the method described in Section 5.2. As displayed in Figure 19, the three black tetrahedrons each contain three targets.Figure 19
Tetrahedron surrounded by target.To avoid selecting the inner points of some tetrahedrons that are too large, the coordinates of the target are assumed to be inaccurate. Therefore, the volume ratio of the tetrahedron was determined to solve the afore-mentioned problem. The volume of all tetrahedrons isVj (j=1,2,⋯,Np), where Np is the number of tetrahedrons. Next, the volume median Vm=Vj+1/2,j=1,3,⋯,Np or Vm=Sj+1/2+Sj/2/2,j=2,4,⋯,Np of the divided tetrahedron was calculated. Assuming that the volume of the tetrahedron in which the target T is located satisfies Vj≤Vm, the tetrahedral centre coordinate Gjxj,yj can be replaced with the coordinate of the target T, that is, Ffxf,yf=Ijxj,yj. Assuming that Vj>Vm, the method in phase 2 is used.Stage 2. When fewer known node coordinates exist, and the formed tetrahedron volume satisfies the conditionVj>Vm, the inner coordinates cannot be estimated as the coordinates of the unknown target.Method 2. WhenVj>Vm is determined in the first step, the coordinates of the target T are directly solved using the least squares method. As displayed in Figures 20 and 21, the red mark indicates target T, and T is inside the A−BCD tetrahedron. When the tetrahedron surrounded by the target T is located for the first time, the least square method combined with the RSSI ranging principle is used to solve the problem with less computation time.Figure 20
T is inside the tetrahedron.Figure 21
Distance fromT to the tetrahedron vertex.Assuming thatT is inside A−BCD, we use Equation (2) to measure the distance between the four vertices of the tetrahedron A−BCD and Tfxf,yf, where d1=AT, d2=BT, d3=CT, and d4=DT. Consequently, the coordinates of the three vertices of △BCG are known, Ax1,y1,z1, Bx2,y2,z2, Cx3,y3,z3, and Dx4,y4,z4, which can be calculated as follows:
(17)x1−xf2+y1−yf2+z1−zf2=d1,x2−xf2+y2−yf2+z2−zf2=d2,x3−xf2+y3−yf2+z3−zf2=d3,x4−xf2+y4−yf2+z4−zf2=d4.Next, subtractd4 from d1, d2, and d3 from Equation (17) to obtain the following expression:
(18)x12−x42−2x1−x4xf+y12−y42−2y1−y4yf+z12−z42−2z1−z4zf=d12−d42,x22−x42−2x2−x4xf+y22−y42−2y2−y4yf+z22−z42−2z2−z4zf=d22−d42,x32−x42−2x3−x4xf+y32−y42−2y3−y4yf+z32−z42−2z3−z4zf=d32−d42.Next, Equation (18) is rewritten as a system of linear equations, similar to Equation (11), where
(19)H=2x1−x42y1−y42z1−z42x2−x42x2−x42z2−z42x3−x42y3−y42z3−z4,X=xfyfzf,and b can be rewritten as a determinant
(20)b=x12−x42+y12−y42+z12−z42=d42−d12x22−x42+y22−y42+z22−z42=d42−d22x32−x42+y32−y42+z32−z42=d42−d32.Thus, Equation (9) is used to calculate the determinant coordinate value of the target T, and then the corresponding value is removed.


## 6. Experimental Verification and Result Analysis

### 6.1. A Linear Regression Analysis of Relevant Data

Experiment 1. Determining the relationship between the number of anchor nodes and the number of graphs generated by the Delaunay division.Comparing the graphs formed by the 2D and 3D Delaunay methods revealed that the 2D Delaunay graph is a triangular network composed of multiple small triangles, while the 3D Delaunay graph is a 3D network composed of multiple tetrahedrons. When changingL, the number of tetrahedrons primarily depends on the number of nodes n. The relationship between the number of nodes divided by the 2D and 3D Delaunay methods and the number of corresponding graphics were analysed. With the same number of nodes, the number of triangles generated by the Delaunay method is considerably smaller than the number of tetrahedrons. Thus, the number of graphs generated by the Delaunay method is linearly related to the number of nodes. As displayed in Figure 22, we set the size of the 2D area to L=200m2 and the 3D area to L=200m3. Next, we set the number of different nodes n20≤n≤200, obtain the number of triangles NΔ and the number of tetrahedrons N, and draw a scatter plot of the two. Figure 22 reveals that the number of triangles or tetrahedrons formed after the Delaunay division appears to have a linear relationship with the number of nodes n. To verify this result, linear regression analysis was performed using Excel software. Assume that the linear equations of two of them can be expressed as follows:
(21)y1=ax0+b,2D,y2=cx1+d,3D.Figure 22
Delaunay scatter chart.When using Excel software to analyse its linear regression characteristics, select the confidence area as 95% and the constant as 0, and generate the corresponding predictive regression and residual plots. Next, the Delaunay linear regression equation and regression characteristics of 2D and 3D data were calculated, and the linear regression equation fitting diagram shown in Figure23 was obtained.Figure 23
Linear regression analysis.Figure23 displays the linear regression equation y1=1.887x. Among these results, the coefficient of determination R2=1 of the equation y1 indicates that the data fit is excellent and close to 1. The value obtained by the regression analysis satisfies the condition Fvalue=Pvalue<0.01, which indicates that the regression effect of the linear equation is significant. Similarly, to analyse the data obtained by the 3D Delaunay division, the equation is y2=5.4132x. Furthermore, all the indicators satisfy the linear regression. Therefore, the number of triangles or tetrahedrons obtained after Delaunay division is positively linearly related to the number of nodes.Finally, residual analysis was used for the 2D and 3D data, as displayed in the residual diagrams in Figures24 and 25. In the figures, the two sets of data are evenly distributed on both sides of the symmetry axis x=0, which demonstrates that the variables are linearly distributed. Finally, through afore-mentioned analysis, the number of triangles or tetrahedrons formed after the Delaunay division and the number of nodes n satisfy a linear relationship.Figure 24
2D data residual plot.Figure 25
3D data residual plot.


### 6.2. A Setting the Distance Constraint ValueK between Anchor Nodes

Experiment 2. Setting the distance constraint valuek between Delaunay generated anchor nodes.Data in Tables1 and 2 were tested. First, the first row of 2D data in Table 1 reveals that when the number of nodes is small, the calculated area accounts for a low percentage. This result likely occurs because the distribution of a small number of randomly generated anchor nodes is uneven, and the distance between nodes is too close, which results in a low proportion of the area or volume of the Delaunay network. After these analyses, when the number of anchor nodes is small, initial constraints were added to the distance between the nodes generated randomly to increase the proportion of the area divided by the Delaunay method; the minimum constraint distance k is set. The distance dsi,sj≤k between each node Delaunay is constrained to make it evenly distributed, where k is a fixed value that can be obtained through multiple experiments.In experiment 2, we set the phase parameters asL=200×200, n=30, and k=25 for verification. As listed in Table 3, the experiment randomly generated 10 sets of 2D data and calculated the total proportion S0/SL of each group of Delaunay generated areas So and total areas SL. By comparing the data in Table 3 with the data in the first row of Table 1, setting the constraint distance value k between anchor nodes can increase the area ratio of the anchor nodes. By setting k, the utilization rate of the anchor node can be improved, and the area of the divided area can be increased. Second, the calculated average of the total area ratio of the 10 sets of data in Table 4 is 83.62%, which is an average increase of 10.18% compared with 73.44% in Table 1.Table 3
Setting conditionk, the data of the 2D Delaunay graph.
Serial numberDelaunay areaS0 (m2)Total area ratioS0/SL (%)13.3977e+0484.94%23.3350e+0483.38%33.2263e+0480.66%43.3672e+0484.18%53.4795e+0486.99%63.4602e+0486.51%73.0426e+0476.04%83.2313e+0480.78%93.3888e+0484.72%103.5203e+0488.01%Table 4
Setting conditionk, the data of the 3D Delaunay graph.
Serial numberDelaunay volumeV (m3)Total volume ratioV/V0 (%)13.3977e+0484.94%23.3350e+0483.38%33.2263e+0480.66%43.3672e+0484.18%53.4795e+0486.99%63.4602e+0486.51%73.0426e+0476.04%83.2313e+0480.78%93.3888e+0484.72%103.5203e+0488.01%Similarly, Table4 lists the test results of the Delaunay method, which randomly generates 3D data to verify the influence of the distance k between the constraint nodes on the Delaunay volume. First, we set the relevant parameters L=200×200×200, n=70, and k=45 for the experiments. In the experiment, the 3D volume data V formed by the anchor nodes divided by Delaunay and 10 sets of data for the total volume of V0/VL were obtained (as listed in Table 4).The calculated average volume ratio of Table4 is 80.17%, which is an average increase of 19.26% compared with the 60.91% data value in Table 2 under the same conditions. Therefore, the verification and analysis of the above two sets of data reveal that when the data were initially randomly generated; adding the constraint value k of the distance between anchor nodes could increase the Delaunay generation area or volume. Consequently, the area and volume ratio of Delaunay’s divided areas increased, rendering the layout of the anchor nodes reasonable.


## 6.1. A Linear Regression Analysis of Relevant Data

Experiment 1. Determining the relationship between the number of anchor nodes and the number of graphs generated by the Delaunay division.Comparing the graphs formed by the 2D and 3D Delaunay methods revealed that the 2D Delaunay graph is a triangular network composed of multiple small triangles, while the 3D Delaunay graph is a 3D network composed of multiple tetrahedrons. When changingL, the number of tetrahedrons primarily depends on the number of nodes n. The relationship between the number of nodes divided by the 2D and 3D Delaunay methods and the number of corresponding graphics were analysed. With the same number of nodes, the number of triangles generated by the Delaunay method is considerably smaller than the number of tetrahedrons. Thus, the number of graphs generated by the Delaunay method is linearly related to the number of nodes. As displayed in Figure 22, we set the size of the 2D area to L=200m2 and the 3D area to L=200m3. Next, we set the number of different nodes n20≤n≤200, obtain the number of triangles NΔ and the number of tetrahedrons N, and draw a scatter plot of the two. Figure 22 reveals that the number of triangles or tetrahedrons formed after the Delaunay division appears to have a linear relationship with the number of nodes n. To verify this result, linear regression analysis was performed using Excel software. Assume that the linear equations of two of them can be expressed as follows:
(21)y1=ax0+b,2D,y2=cx1+d,3D.Figure 22
Delaunay scatter chart.When using Excel software to analyse its linear regression characteristics, select the confidence area as 95% and the constant as 0, and generate the corresponding predictive regression and residual plots. Next, the Delaunay linear regression equation and regression characteristics of 2D and 3D data were calculated, and the linear regression equation fitting diagram shown in Figure23 was obtained.Figure 23
Linear regression analysis.Figure23 displays the linear regression equation y1=1.887x. Among these results, the coefficient of determination R2=1 of the equation y1 indicates that the data fit is excellent and close to 1. The value obtained by the regression analysis satisfies the condition Fvalue=Pvalue<0.01, which indicates that the regression effect of the linear equation is significant. Similarly, to analyse the data obtained by the 3D Delaunay division, the equation is y2=5.4132x. Furthermore, all the indicators satisfy the linear regression. Therefore, the number of triangles or tetrahedrons obtained after Delaunay division is positively linearly related to the number of nodes.Finally, residual analysis was used for the 2D and 3D data, as displayed in the residual diagrams in Figures24 and 25. In the figures, the two sets of data are evenly distributed on both sides of the symmetry axis x=0, which demonstrates that the variables are linearly distributed. Finally, through afore-mentioned analysis, the number of triangles or tetrahedrons formed after the Delaunay division and the number of nodes n satisfy a linear relationship.Figure 24
2D data residual plot.Figure 25
3D data residual plot.


## 6.2. A Setting the Distance Constraint ValueK between Anchor Nodes

Experiment 2. Setting the distance constraint valuek between Delaunay generated anchor nodes.Data in Tables1 and 2 were tested. First, the first row of 2D data in Table 1 reveals that when the number of nodes is small, the calculated area accounts for a low percentage. This result likely occurs because the distribution of a small number of randomly generated anchor nodes is uneven, and the distance between nodes is too close, which results in a low proportion of the area or volume of the Delaunay network. After these analyses, when the number of anchor nodes is small, initial constraints were added to the distance between the nodes generated randomly to increase the proportion of the area divided by the Delaunay method; the minimum constraint distance k is set. The distance dsi,sj≤k between each node Delaunay is constrained to make it evenly distributed, where k is a fixed value that can be obtained through multiple experiments.In experiment 2, we set the phase parameters asL=200×200, n=30, and k=25 for verification. As listed in Table 3, the experiment randomly generated 10 sets of 2D data and calculated the total proportion S0/SL of each group of Delaunay generated areas So and total areas SL. By comparing the data in Table 3 with the data in the first row of Table 1, setting the constraint distance value k between anchor nodes can increase the area ratio of the anchor nodes. By setting k, the utilization rate of the anchor node can be improved, and the area of the divided area can be increased. Second, the calculated average of the total area ratio of the 10 sets of data in Table 4 is 83.62%, which is an average increase of 10.18% compared with 73.44% in Table 1.Table 3
Setting conditionk, the data of the 2D Delaunay graph.
Serial numberDelaunay areaS0 (m2)Total area ratioS0/SL (%)13.3977e+0484.94%23.3350e+0483.38%33.2263e+0480.66%43.3672e+0484.18%53.4795e+0486.99%63.4602e+0486.51%73.0426e+0476.04%83.2313e+0480.78%93.3888e+0484.72%103.5203e+0488.01%Table 4
Setting conditionk, the data of the 3D Delaunay graph.
Serial numberDelaunay volumeV (m3)Total volume ratioV/V0 (%)13.3977e+0484.94%23.3350e+0483.38%33.2263e+0480.66%43.3672e+0484.18%53.4795e+0486.99%63.4602e+0486.51%73.0426e+0476.04%83.2313e+0480.78%93.3888e+0484.72%103.5203e+0488.01%Similarly, Table4 lists the test results of the Delaunay method, which randomly generates 3D data to verify the influence of the distance k between the constraint nodes on the Delaunay volume. First, we set the relevant parameters L=200×200×200, n=70, and k=45 for the experiments. In the experiment, the 3D volume data V formed by the anchor nodes divided by Delaunay and 10 sets of data for the total volume of V0/VL were obtained (as listed in Table 4).The calculated average volume ratio of Table4 is 80.17%, which is an average increase of 19.26% compared with the 60.91% data value in Table 2 under the same conditions. Therefore, the verification and analysis of the above two sets of data reveal that when the data were initially randomly generated; adding the constraint value k of the distance between anchor nodes could increase the Delaunay generation area or volume. Consequently, the area and volume ratio of Delaunay’s divided areas increased, rendering the layout of the anchor nodes reasonable.


## 7. Comparison Analysis

In this section, the proposed 2D-DPTL algorithm was compared with the centroid, amorphous, and APIT algorithms [29]. The degree of irregularity (DOI) represents the degree of irregularity of the signal and generally is a value in the range of [0,1]. DOI is defined as the distance change of the largest wireless signal per unit degree change in the signal propagation direction [29]. When the DOI value is zero, this indicates that the signal model is an ideal circular signal model. In this experiment, the node was deployed in an area L with a range of 200×200, and the communication range of the node was set to Rc=20m. Through experimental tests, we set the relevant parameters of the RSSI path loss model as follows: noise standard deviation σk=4, path loss value ηk=2.5, and Pk=−24. Next, the neighbour density (ND), anchor percentage deployment method (random deployment or uniform deployment), and other parameters were selected to verify the accuracy of the algorithm.


### 7.1. Effect of Changing the Number of Nodes on Average Localization Error

Experiment 3. Effect of changing the number of anchor nodes on the average localization error (ALE) of the algorithm.First, we analysed the effect of the change in the number of anchor nodes on the ALE and compared the performance of the proposed algorithm with other algorithms. Next, the parametersDOI=0 and ND=8 were set, and two sets of experiments were designed with various node deployment methods. As displayed in Figure 26, when nodes were deployed uniformly, the ALE of the five algorithms decreased as the percentage of anchor nodes increased. However, the ALE values of the various algorithms differed considerably. The centroid algorithm (CA) exhibited the highest ALE and did not consider the optimization of the anchor node layout, and the calculation method is not rigorous. The proposed 2D-DPTL algorithm exhibited a lower ALE value than other algorithms because the distance judgement condition between nodes was added to optimize the node layout. Consequently, the proposed algorithm divided the target area twice to improve the localization accuracy and reduce the ALE of the algorithm.Figure 26
Uniform node deployment.Comparing Figures26 and 27 reveals that the deployment methods differed considerably, and under the same values of other indicators, the ALE value of randomly deployed nodes was greater than that of uniformly deployed nodes. This result likely occurred because the uniform deployment of anchor nodes rendered the layout of nodes reasonable and increased the accuracy of target localization. Consequently, the ALE of the proposed algorithm was higher than that of other algorithms because the Delaunay method could optimally divide node’s location according to its location coordinates from an optimal triangle network, and the location of the target was estimated, which improved location accuracy. Second, the proposed algorithm performed a secondary calculation on the problem of target’s excessive localization range and reduced the ALE value of the overall network.Figure 27
Random node deployment.


### 7.2. Effect of the Density of Neighbour Nodes on ALE

Experiment 4. Effect of changing the density of neighbouring nodes on the ALE when the DOI differed.The effect of the change in the neighbour node density of each algorithm on its ALE was verified. WithAP=28 and uniform deployment of nodes, we set DOI=0 and DOI=0.1 to conduct two sets of experiments, as displayed in Figures 28 and 29, which reveal that the CA exhibited the highest ALE because this algorithm estimated the centre of mass coordinates as the target localisation and failed to reduce the localisation error. The proposed algorithm used a phased calculation method to reduce ALE.Figure 28
ALE of all algorithms whenDOI=0.Figure 29
ALE of all algorithms whenDOI=0.1.In Figure28, the ALE values of the amorphous and APIT algorithms decreased as the density of neighbouring nodes increased, whereas the ALEs of the CA and the proposed algorithm were not affected by a change in neighbouring node density. These results were attributed to the absence of the interaction between the target node and neighbouring nodes. Figures 28 and 29 reveal that the improvement in signal irregularity reduces the average localisation accuracy of the algorithm. Consequently, these experiments reveal that the localisation accuracy of the proposed algorithm was superior to that of the other algorithms and can be maintained within a certain range.


## 7.1. Effect of Changing the Number of Nodes on Average Localization Error

Experiment 3. Effect of changing the number of anchor nodes on the average localization error (ALE) of the algorithm.First, we analysed the effect of the change in the number of anchor nodes on the ALE and compared the performance of the proposed algorithm with other algorithms. Next, the parametersDOI=0 and ND=8 were set, and two sets of experiments were designed with various node deployment methods. As displayed in Figure 26, when nodes were deployed uniformly, the ALE of the five algorithms decreased as the percentage of anchor nodes increased. However, the ALE values of the various algorithms differed considerably. The centroid algorithm (CA) exhibited the highest ALE and did not consider the optimization of the anchor node layout, and the calculation method is not rigorous. The proposed 2D-DPTL algorithm exhibited a lower ALE value than other algorithms because the distance judgement condition between nodes was added to optimize the node layout. Consequently, the proposed algorithm divided the target area twice to improve the localization accuracy and reduce the ALE of the algorithm.Figure 26
Uniform node deployment.Comparing Figures26 and 27 reveals that the deployment methods differed considerably, and under the same values of other indicators, the ALE value of randomly deployed nodes was greater than that of uniformly deployed nodes. This result likely occurred because the uniform deployment of anchor nodes rendered the layout of nodes reasonable and increased the accuracy of target localization. Consequently, the ALE of the proposed algorithm was higher than that of other algorithms because the Delaunay method could optimally divide node’s location according to its location coordinates from an optimal triangle network, and the location of the target was estimated, which improved location accuracy. Second, the proposed algorithm performed a secondary calculation on the problem of target’s excessive localization range and reduced the ALE value of the overall network.Figure 27
Random node deployment.


## 7.2. Effect of the Density of Neighbour Nodes on ALE

Experiment 4. Effect of changing the density of neighbouring nodes on the ALE when the DOI differed.The effect of the change in the neighbour node density of each algorithm on its ALE was verified. WithAP=28 and uniform deployment of nodes, we set DOI=0 and DOI=0.1 to conduct two sets of experiments, as displayed in Figures 28 and 29, which reveal that the CA exhibited the highest ALE because this algorithm estimated the centre of mass coordinates as the target localisation and failed to reduce the localisation error. The proposed algorithm used a phased calculation method to reduce ALE.Figure 28
ALE of all algorithms whenDOI=0.Figure 29
ALE of all algorithms whenDOI=0.1.In Figure28, the ALE values of the amorphous and APIT algorithms decreased as the density of neighbouring nodes increased, whereas the ALEs of the CA and the proposed algorithm were not affected by a change in neighbouring node density. These results were attributed to the absence of the interaction between the target node and neighbouring nodes. Figures 28 and 29 reveal that the improvement in signal irregularity reduces the average localisation accuracy of the algorithm. Consequently, these experiments reveal that the localisation accuracy of the proposed algorithm was superior to that of the other algorithms and can be maintained within a certain range.


## 8. Conclusions

The Delaunay division method can optimize the layout of 2D nodes and can be applied to the network layout of 3D sensor nodes based on the location coordinates of the nodes. Delaunay triangle division can improve the flexibility of the node layout and strengthen the correlation between the anchor nodes. Therefore, the Delaunay partition method was used to optimize the Delaunay network layout of randomly deployed anchor nodes. Two localization algorithms were designed to accurately estimate the position of the target in 2D and 3D coordinate systems. The proposed algorithm has limitations in the network life cycle and delay and must be verified in a real-world scenario. The results of this study provide a critical important direction for future research.



---

*Source: 4047684-2021-11-17.xml*