# Distributed Cooperative Localization with Optimized Constraints for 3D WSNs

Authors: Yun Hong; Song Wang; Zhaoyang Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In three-dimensional (3D) Wireless Sensor Networks (WSNs), the localization suffers from localization accuracy and computation efficiency problem due to added dimension compared with 2D WSNs. Aiming at localizing WSNs in 3D way, we propose a distributed cooperative localization method with optimized constraints. The optimized constraints effectively limit the potential range where the unknown nodes are limited. By analyzing the positions of anchors which are within the communication radius of unknown node, the initial positions of unknown nodes are geometrically estimated in several situations. They link with each other and form a 3D cooperative network. Based on message passing (MP) theory, we extend the 2D cooperative localization to 3D distributed cooperative localization. In this process, optimized constraints derived from hop information and RSSI avoid the gross error and large deviation in the localization. Simulation results in various scenarios show the improvement of accuracy and efficiency compared with traditional methods.


---

## Body

## 1. Introduction

Wireless Sensor Networks (WSNs) are an emerging technology that have numerous potential applications including many areas of personal and ubiquitous computing. They cover body area networks, smart homes, and a variety of environmental and military applications [1, 2]. WSNs are formed by small autonomous nodes that contain a CPU, memory, battery, a wireless transceiver, and some sensors that measure physical attributes, e.g., temperature, velocity, light etc. Their information only makes sense when their locations are obtained [4]. Since WSNs face more changeable and complex environment, the localization of 3D distribution presents a great challenge of effective and robust algorithm for 3D WSNs [5, 6].Many localization algorithms have been proposed to locate nodes in 2D WSNs [7, 8]. These algorithms include range-based localization and range-free localization. Some range-based localization methods include received signal strength indicator (RSSI) [9], time of arrival (ToA) [10], angle of arrival (AoA) [11], and time difference on arrival (TDoA) [12]. Some range-free localization methods include APIT [13], centroid, and DV-HOP [14]. These methods have been widely used in 2D WSNs and obtain good performance. When the dimension is added to 3D WSNs, some research simply extend 2D localization to 3D localization, e.g., 3D-DV-HOP, 3D-centriod, etc. Although the extended methods can locate the sensor nodes, their accuracy is largely affected by the added dimension.For localization of 3D WSNs, some researches explore geometric modeling by analyzing the node organization. Fan et al. [15] define a dissimilarity matrix representing the distance of each node to every other node in the 3D network. This definition combines with multidimensional scaling and Helmet Transformation to convert the local coordinates of the node into a global coordinate system. Shan and Sun [16] propose landscape-3D algorithm by taking it as a functional dual of target tracking. The location assistant periodically broadcasts its position and measures the distance by RSSI. This information contributes to node state prediction and updates iteration of Unscented Karman Filter so that 3D localization is realized. Zhou et al. [17] propose 3D node localization algorithms using the particle swarm optimization framework. The methods include preprocessing factors for manipulating RSS and follow a sphere-based deployment region, which overcomes the disjunctive between RSS and distance estimation. Bayrakdal and Cao et al. [18, 19] extend the 3D localization method based on the flying anchors. In the scheme, each anchor is equipped with a GPS receiver and broadcasts its location information as it flies through the sensing space. Each sensor node in the sensing area then estimates its own location by applying basic geometry principles to the location information it receives from the flying anchors. We should notice that large-scale sensor network is limited by node densities and computation complexity. Because network topologies and path planning of anchors increase extra computation. Most of the researches above are still not applicable in complex sensing environment.In 3D WSNs, low accuracy and high computation complexity are key problems of localization. To overcome the problems caused by added dimension, distributed cooperative system shows feasibility and applicability, which is widely used in 2D localization. Yuan et al. [20] explore localization technology of WSNs with the convex hull constraint. Neighborhood collaboration happens inside the convex hull of its neighbors. Iterative self-positioning algorithms implement on all individual sensors in a distributed and cooperative way. Papaioannou et al. [21] propose a probabilistic framework through strengths of collaboration platforms. The collaboration is from peripolar geometry and interrobot localization measurements and mediates weaknesses of unmanned aerial and ground vehicles. Zou and Liu and Singh et al. [22, 23] initialize the localization by convex estimator then model the localization problem as convex maximum likelihood estimator. This process is based on the RSS signal analysis. Wu et al., Liang and Meyer, Nitithumbundit and chan, Liu et al., and Wang et al. [24–28] investigate the cooperative localization based on empirical ranging data. To reduce communication and computational cost, an asymmetric double exponential ranging error model combines passing approximate beliefs in a way of Gaussian distributions and analytical approximation of peer-to-peer messages. As the 3D localization requires high accuracy and low computation complexity, the distributed cooperative strategy can be extended to 3D WSNs aiming at eliminating the uncertainty and complexity of 3D localization.To solve the problems in 3D localization, we propose a distributed cooperative localization scheme based on message passing of optimized constraints. The contributions of this paper can be summarized as follows.(1)
The scheme firstly builds the posteriori marginal PDF model. It also depicts the possible distributed area of unknown node and forms the optimized constraints for further localization(2)
By geometric analysis, the initial position of unknown node is estimated. It starts the distributed cooperative algorithm through MP which updates the estimated position to approach the ground truth(3)
While the variational message passing (VMP) is regarded as the updated rule, the updated process is calibrated by optimized constraints so that network localization breakdown is avoided


## 2. Materials and Methods

We consider a 3D WSN consisting of two types of sensor nodes: unknown nodes and anchors. Anchors, which have known positions (for example, through GPS or system design), provide reference for localization. Unknown nodes, i.e., sensor nodes to be located, have unknown positions and attempt to infer their positions based on range measurements to the anchors. These sensor nodes are located atxi,i∈G≔1,⋯,N, and xi is a 3D random variable representing the position of sensor node i. Among sensor nodes, unknown node set U is not aware of its positions, and anchors are aware of their positions at μi,i∈A≔1,⋯M. Thus, all sensor node set are denoted by G=A∪U. We assume that sensor node i acquires a noisy measurement dij, which is the measured distance to sensor node j (j can be either an unknown node or an anchor). It can also be estimated when the coordinates of two nodes are known. Then, we have the estimated distance
(1)d^ij=xi−xj+eij,where· denotes the Euclidean norm, and eij is the measurement noise, which may obey log-normal, Gaussian, or any other appropriate distribution measured in various deployment districts. Without loss of generality, we assume that measurement noise obeys Gaussian distribution, so eij∼Neij;0,σij2. σij is the standard deviation (SD). The probability density function of node distance is as
(2)pdijxi,xj=12πσij2exp−dij−xi−xj22σij2.The probability density function of node distance can be simply denoted byfij≜pdijxi,xj. We assume that the relative positions are conditionally independent and they only depend on the two nodes involved.
(3)pZX=∏i∈G∏j∈Gipdijxi,xj,where X are defined as the position set X≜xi:i∈G of all sensor nodes, and Z are defined as the distance set Z≜dij:i∈G,j∈Gi of all sensor nodes. The marginal probability density function (PDF) of positions for all unknown nodes can be characterized.
(4)PXZ=∏i∈G∏j∈Gipdijxi,xj∏i∈Gpxi,where the priori probability pxi are simply denoted by fi≜pxi. Our objective is to compute (or approximate) the a posteriori marginal PDF for each unknown node.


## 3. Distributed Cooperative Localization Scheme

In this section, we present a distributed cooperative localization scheme aiming at improving localization accuracy with low communication overhead and computation complexity. In the localization process, the optimized constraints for unknown node should be firstly built to represent possible distributed area. By transforming the optimized constraints, the positions of unknown nodes are initialized. These positions are updated in a distributed cooperative way to improve the localization accuracy.


### 3.1. Optimized Constraints

In 3D WSNs, the localization accuracy is low only using the Received Signal Strength Indication (RSSI) and hop information. Due to the measurement deviation, localization of unknown node always has gross error. For most existing localization methods, gross error affects the localization accuracy, or even leads to localization failure. Although the insufficient information cannot estimate the accurate position, it can provide the possible distributed area of unknown node. By the possible node distributed area, the estimated position of unknown node is calibrated and large deviation is avoided. Thus, we explore to narrow down the area and define optimized constraints to denote the possible distribution area of unknown node so that a more accurate position is estimated.To build the possible node distributed area, the position relationship among sensor nodes within one-hop and two-hop range is analyzed. If the anchor can communicate with the unknown node directly, it means the anchor is within the one-hop range of unknown node and this anchor belongs to the one-hop anchor set denoted byA_onehop. If the anchor can only communicate with the unknown node through another one node, it means the anchor is within the two-hop range of the known node and this anchor belongs to the two-hop anchor set denoted by A_twohop. One-hop anchor set and two-hop anchor set can locate basic possible distributed space of unknown node.For one-hop anchor set, distance between each anchor and unknown node is less than communication radiusR. It is denoted as
(5)di,A_onehop<R,where i∈U is the unknown node. The distance between unknown node i and every anchor in set A_onehop is less than R. The position relationship above is shown in Figure 1 when the element amount of set A_onehop is three. The shadow is the possible distributed space of the unknown node.Figure 1
Position relationship of the unknown node and one-hop anchor set.For two-hop anchor set, distance between each anchor and unknown node is more than communication radiusR and less than 2R. It is denoted as
(6)R<di,A_twohop<2R,where i∈U, and the distance between unknown node i and each anchor in set A_twohop is more than R and less than 2R. The position relationship above is shown in Figure 2 when the element amount of set A_onehop is two and the element amount of set A_twohop is one. The shadow is the possible distributed space of unknown node.Figure 2
Position relationship of the unknown node, one-hop anchor set, and two-hop anchor set.As Figures1 and 2 show, the possible distributed space of unknown node is too large to limit the estimated position. To overcome the problem, RSSI is introduced. For simplicity, we assume that the sensor nodes are equipped with omnidirectional antennas. The two-ray ground reflection model of RSSI is as
(7)Prd=PtGtGrht2hr2d4L,where Prdis the received signal power corresponding to d. Pt is the transmitting signal power. Gt and Gr represent antenna gain of transmitter and receiver. ht and hr are the height of transmitter and receiver. LL≥1 is the system loss. Empirical studies have shown that the model works quite well in long-distance transmission environments. The measured distance between two nodes is shown as
(8)d=PtGtGrht2hr2PrL4.Considering the environmental inference, measured distance is not quite accurate. The maxnoise of estimated distance is regarded as the threshold to denote the maximum deviation of real distance. The relationship between measured RSSI and estimated RSSI is shown as(9)Pi,A_onehop−MaxNoise<P^i,A_onehopd^i,A_onehop<Pi,A_onehop+MaxNoise.Pi,A_onehop is the measured RSSI. P^i,A_onehopd^i,A_onehop is the estimated RSSI calculated by estimated position of unknown node according to equation (7). d^i,A_onehop is the estimated distance between estimated position of node i and node within one-hop communication range. Maxnoise is the maximum deviation of distance measurement. The constraints combining (5), (6), and (9) are shown in
(10)d^i,A_onehop<R,R<d^i,A_twohop<2R,Pi,A_onehop−MaxNoise<P^i,A_onehopd^i,A_onehop<Pi,A_onehop+MaxNoise.The optimized constraints in situation of Figures1 and 2 can be shown in Figures 3 and 4. In the figures, we should note RSSImin=Pi,A_onehop−MaxNoise and RSSImax=Pi,A_onehop+MaxNoise.Figure 3
Position relationship with optimized constrains in Figure1.Figure 4
Position relationship with optimized constrains in Figure2.


### 3.2. Initial Positions of Unknown Node

The possible distributed space of unknown node is derived by one-hop and two-hop information and RSSI, but it is an irregular polyhedron for 3D WSN. It is difficult to denote the boundary of irregular polyhedron in mathematical form, so the exact position of unknown node cannot be obtained in this condition. To locate unknown node, we firstly design the geometric method to estimate the initial position. On the basis, the position of unknown node is continuously updated using Massage Passing (MP), a distributed cooperative method, until the estimated position approaches the real value infinitely. This process requires the method is simple and feasible. To avoid large computation overhead, geometric method is designed to initialize the position of unknown node.According to the difference of RSSIs, we discuss the position initialization in the following situations. As this process depends on the anchors within the communication radius of unknown node, the number of selected anchors is equal or less than three so that the initialization process is simplified. Note that the selection is random. In the communication among sensor nodes, RSSI is affected by the complex environment, so2MaxNoise is defined to indicate the proximity of RSSIs.When RSSIs between selected anchors and unknown node are proximate, the measured distance comparison calculated by measured RSSIs is shown as(11)dij−dik≤2MaxNoise,where i∈U is the unknown node and k,j∈A_onehop is the node within one-hop range. If selected anchors all meet the condition in (11), it indicates that the distance to all selected anchors is almost same. This situation is shown in Figure 5. The initial position of the unknown node is the centroid of selected anchors as
(12)x1Ini=1p∑j∈A_onehop′μ1j,x2Ini=1p∑j∈A_onehop′μ2j,x3Ini=1p∑j∈A_onehop′μ3j,where xIni=x1Ini,x2Ini,x3IniT is the initial position of the unknown node and μj=μ1j,μ2j,μ3jT is the position of the selected anchors in one-hop anchor set. A_onehop′ denotes the one_hop set which only consists of selected anchors. p is the number of selected anchors as it may be one, two, or three.Figure 5
Initial position of the unknown node for proximate RSSI in (11).In Figure5, the shadow is the possible distributed space of the unknown node. The white dot U is the position of the unknown node. The black dot C is the initial position of the unknown node. The black dots A1,A2,A3 are the selected anchors.If measured distance between unknown node and any selected anchor meets the inequality (13), it indicates that the unknown node is closer to the anchor with larger RSSI.
(13)dij−dik>2MaxNoise.When the number of anchor in one-hop anchor set is two, the position relationship of these sensor nodes is shown in Figure6.Figure 6
Initial position of the unknown node for different RSSIs in (13).In Figure6, the white dot U is the position of the unknown node and the white dot C is the midpoint of A1 and A2. Because the unknown node is closer to anchor A1, the shadow representing the possible distributed area is the left half of intersecting space. The line A2C has an intersection with spherical shell. The midpoint UIni of point C and intersection is regarded as the initial position of unknown node as
(14)x1Ini=2R+dA1A24dA1A2μ11+3dA1A2−2R4dA1A2μ12,x2Ini=2R+dA1A24dA1A2μ21+3dA1A2−2R4dA1A2μ22,x3Ini=2R+dA1A24dA1A2μ31+3dA1A2−2R4dA1A2μ32,where dA1A2 is the measured distance between A1 and A2. μ1=μ11,μ21,μ31T is the coordinate of anchor A1. μ2=μ12,μ22,μ32T is the coordinate of anchor A2.When the number of selected anchors in one-hop anchor set is three and at least one measured distance is far more than other measured distance, it is a different situation compared with Figure5. Assumed that the RSSIs of selected anchors meet the inequality (15), then distances of these anchors meet the inequality (16) accordingly.
(15)PiA1<PiA2<PiA3,A1,A2,A3∈A_onehop,(16)diA1<diA2<diA3,A1,A2,A3∈A_onehop.The subsituation is further defined based on inequality (16) when anchor A1,A2 meets inequality (11) and A1,A3 and A2,A3 meet inequality (13). It indicates that the unknown node is closer to anchor A1,A2 and farther than A3 as shown in Figure 7. The white dot is the centroid of anchor A1,A2,A3. The line A3C has an intersection with spherical shell. As the inequality (16) tells us, the unknown node is in the shadow area. In this situation, midpoint UIni of point C and intersection is regarded as the initial position of the unknown node.Figure 7
Initial position of the unknown node for different RSSIs in (15).By geometric analysis, the coordinate of initial position is as shown in(17)x1Ini=R+dCA32dCA3x1c+R−dCA32dCA3μ13,x2Ini=R+dCA32dCA3x2c+R−dCA32dCA3μ23,x3Ini=R+dCA32dCA3x3c+R−dCA32dCA3μ33,where xc=x1c,x2c,x3cT is the coordinate of centroid C which is obtained from equation (12). dCA3 is the estimated distance between centroid C and anchor A3. μ3=μ13,μ23,μ33T is the coordinate of anchor A3.For the rest subsituations, the unknown node is closer to anchorA1 as shown in Figure 8. These subsituations are A2,A3 meet inequality (11), and A1,A2,A3 do not meet inequality (11). The initial position of the unknown node should be in the area which is close to anchor A1. From Figure 8, the centroid of A1,A2,A3 can be regarded as the initial position.Figure 8
Initial position of the unknown node for different RSSIs for rest subsituation.


### 3.3. Cooperative Localization Method

The initial positions in the above situations are usually the center of possible distributed space. Actually, they still deviate from the real position of the unknown node. To approach the real position, MP, a cooperative localization method, is introduced as since outperforms in 2D localization technology. It fuses position information and distance information of the whole network in a cooperative way so that localization accuracy is improved. In this process, MP only needs to send and receive the position message and RSSI message once while sensor node linearly estimates its position by itself. It largely reduces the communication overhead and computation complexity. For 3D WSN, the added dimension leads to the increasing computation complexity and localization error. It urgently requires localization method to eliminate the effect of added dimension. As a distributed cooperative method, MP has advantages of flexible message exchange and fast calculation which could promote 3D localization technology.To locate unknown nodei, messages from anchor a and unknown node l should be considered where a,l∈A_onehop. Anchor a and unknown node l should cover all the sensor nodes within the communication radius of unknown node i. As the distance-measurement model is nonlinear, variational message passing is introduced to calculate the cooperative message shown in equations (18) and (19). To avoid the large deviation, we design the judgement factor and penalty function for anchor messages and unknown node messages, respectively.
(18)mfia⟶xixi=Pfia⟶xixiexp∫θJabxalnpdiaxi,xadxa,(19)mfil⟶xixi=Pfil⟶xixiexp∫θJlbxllnpdilxi,xldxl,where mfia⟶xixi,mfil⟶xixi are the messages from anchor factor fia and unknown anchor factor fil. bxa,bxl are the confidence from last iteration. θJa and θJl are the judgement factor of anchor and unknown node. They are designed to judge if the updated position meets the constraints in (10). If the updated position meets the constraints, θJ=1. Otherwise, θJ=0.In equations (18) and (19), Pfia⟶xixi,Pfil⟶xixi are the penalty functions. It is calculated by equation (19).
(20)Pxi=expδvix,where vix is the amount change of sensor nodes which meets the constraints (10). If the amount is increased or unchanged after update, vix=1. Otherwise, vix=p/q where p is the node amount which meets the constraints after update. q is the node amount which meets the constraints before update. δ is the float constant which denotes the effect of constraints.The unknown node receives the messages from anchor and other unknown nodes, and it fuses the cooperative messages to update the position of unknown node. The confidence is shown in(21)bxi≜1Z∏a∈A_onehopmfia⟶xixi∏l∈U_onehopmfil⟶xixi,where Z is the confidence constant and U_onehop is other unknown node set in which unknown nodes are within the communication radius of target unknown node.After putting equations (18) and (19) into (21), the equation (21) is transformed into
(22)bxi∝expδVax∑a∈A_onehopθJagiaxi+δ′Vlx∑l∈U_onehopθJlgilxi,where Vax is the global variable of node amount change which is extended from vix. giaxi,gilxi are calculated by
(23)giaxi≜diaσia2μa−xi−12σia2μa−xi2,(24)gilxi≜∫b^xldilσil2xl−xi−12σil2xl−xi2.Because computation complexity needs to be limited in 3D WSNs, we simplify the nonlinear distance formula by Taylor Expansion into linear distance formula. In equations (23) and (24), Fiaxi≜μa−xi and Filxi,xl=xl−xi are, respectively, expanded around x^i∗and x^i∗,x^m∗with second-order Taylor Expansion. Then, the confidence is linearized as
(25)b^xi∝exp−12xiTV∧i−1xi+xiTV∧i−1μ^i.The variance value of node position is as(26)V^i=δVax∑a∈A_onehopiθJa1σia2I−diaσia2∇Fia2+δVlx∑l∈U_onehopθJl1σil2I−dilσil2HFil−1.The mean value of node position is as(27)μ^i=V^iδVax∑a∈A_onehopθJa1σia2μa+diaσia2∇Fia−∇Fia2μ~i+δVlx∑l∈U_onehopθJl1σil2μ~l+dilσil2∇Fil−HFilμ~i,where ∇Fia,∇Fia2 is the first-order and second-order gradient of Fiaxi at x^i∗. ∇Fil,HFil is the first-order partial derivative and Hessian matrix.In 3D WSN localization, the added dimension also increases the dimension of parameters above. Parameters∇Fia,∇Fil,∇Fia2,HFil need to be deduced again as shown in equations
(28)∇Fia=x1i∗−μ1ad^iax2i∗−μ2ad^iax3i∗−μ3ad^ia,(29)∇Fil=x1i∗−x1l∗d^ilx2i∗−x2l∗d^ilx3i∗−x3l∗d^il,(30)∇Fia2=1d^ia−x1i∗−μ1ad^ia3−x1i∗−μ1ax2i∗−μ2ad^ia3−x1i∗−μ1ax3i∗−μ3ad^ia3−x1i∗−μ1ax2i∗−μ2ad^ia31d^ia−x2i∗−μ2ad^ia3−x2i∗−μ2ax3i∗−μ3ad^ia3−x1i∗−μ1ax3i∗−μ3ad^ia3−x2i∗−μ2ax3i∗−μ3ad^ia31d^ia−x3i∗−μ3ad^ia3,(31)HFil=1d^il−x1i∗−x1l∗d^il3−x1i∗−x1l∗x2i∗−x2l∗d^il3−x1i∗−x1l∗x3i∗−x3l∗d^il3−x1i∗−x1l∗x2i∗−x2l∗d^il31d^il−x2i∗−x2l∗d^il3−x2i∗−x2l∗x3i∗−x3l∗d^il3−x1i∗−x1l∗x3i∗−x3l∗d^il3−x2i∗−x2l∗x3i∗−x3l∗d^il31d^il−x3i∗−x3l∗d^il3.The distributed cooperative localization is conducted in the situation of known initial position which is adjusted by the variance and mean. For each round of iteration, the updated position should be compared with the optimized constraints in (10). If the updated position meets the optimized constraints, the updated position would be put into the next iteration. If not, the updated position of last round remains unchanged and would be put into the next iteration. Until the iteration counts reach the setting, the localization process ends.


## 3.1. Optimized Constraints

In 3D WSNs, the localization accuracy is low only using the Received Signal Strength Indication (RSSI) and hop information. Due to the measurement deviation, localization of unknown node always has gross error. For most existing localization methods, gross error affects the localization accuracy, or even leads to localization failure. Although the insufficient information cannot estimate the accurate position, it can provide the possible distributed area of unknown node. By the possible node distributed area, the estimated position of unknown node is calibrated and large deviation is avoided. Thus, we explore to narrow down the area and define optimized constraints to denote the possible distribution area of unknown node so that a more accurate position is estimated.To build the possible node distributed area, the position relationship among sensor nodes within one-hop and two-hop range is analyzed. If the anchor can communicate with the unknown node directly, it means the anchor is within the one-hop range of unknown node and this anchor belongs to the one-hop anchor set denoted byA_onehop. If the anchor can only communicate with the unknown node through another one node, it means the anchor is within the two-hop range of the known node and this anchor belongs to the two-hop anchor set denoted by A_twohop. One-hop anchor set and two-hop anchor set can locate basic possible distributed space of unknown node.For one-hop anchor set, distance between each anchor and unknown node is less than communication radiusR. It is denoted as
(5)di,A_onehop<R,where i∈U is the unknown node. The distance between unknown node i and every anchor in set A_onehop is less than R. The position relationship above is shown in Figure 1 when the element amount of set A_onehop is three. The shadow is the possible distributed space of the unknown node.Figure 1
Position relationship of the unknown node and one-hop anchor set.For two-hop anchor set, distance between each anchor and unknown node is more than communication radiusR and less than 2R. It is denoted as
(6)R<di,A_twohop<2R,where i∈U, and the distance between unknown node i and each anchor in set A_twohop is more than R and less than 2R. The position relationship above is shown in Figure 2 when the element amount of set A_onehop is two and the element amount of set A_twohop is one. The shadow is the possible distributed space of unknown node.Figure 2
Position relationship of the unknown node, one-hop anchor set, and two-hop anchor set.As Figures1 and 2 show, the possible distributed space of unknown node is too large to limit the estimated position. To overcome the problem, RSSI is introduced. For simplicity, we assume that the sensor nodes are equipped with omnidirectional antennas. The two-ray ground reflection model of RSSI is as
(7)Prd=PtGtGrht2hr2d4L,where Prdis the received signal power corresponding to d. Pt is the transmitting signal power. Gt and Gr represent antenna gain of transmitter and receiver. ht and hr are the height of transmitter and receiver. LL≥1 is the system loss. Empirical studies have shown that the model works quite well in long-distance transmission environments. The measured distance between two nodes is shown as
(8)d=PtGtGrht2hr2PrL4.Considering the environmental inference, measured distance is not quite accurate. The maxnoise of estimated distance is regarded as the threshold to denote the maximum deviation of real distance. The relationship between measured RSSI and estimated RSSI is shown as(9)Pi,A_onehop−MaxNoise<P^i,A_onehopd^i,A_onehop<Pi,A_onehop+MaxNoise.Pi,A_onehop is the measured RSSI. P^i,A_onehopd^i,A_onehop is the estimated RSSI calculated by estimated position of unknown node according to equation (7). d^i,A_onehop is the estimated distance between estimated position of node i and node within one-hop communication range. Maxnoise is the maximum deviation of distance measurement. The constraints combining (5), (6), and (9) are shown in
(10)d^i,A_onehop<R,R<d^i,A_twohop<2R,Pi,A_onehop−MaxNoise<P^i,A_onehopd^i,A_onehop<Pi,A_onehop+MaxNoise.The optimized constraints in situation of Figures1 and 2 can be shown in Figures 3 and 4. In the figures, we should note RSSImin=Pi,A_onehop−MaxNoise and RSSImax=Pi,A_onehop+MaxNoise.Figure 3
Position relationship with optimized constrains in Figure1.Figure 4
Position relationship with optimized constrains in Figure2.


## 3.2. Initial Positions of Unknown Node

The possible distributed space of unknown node is derived by one-hop and two-hop information and RSSI, but it is an irregular polyhedron for 3D WSN. It is difficult to denote the boundary of irregular polyhedron in mathematical form, so the exact position of unknown node cannot be obtained in this condition. To locate unknown node, we firstly design the geometric method to estimate the initial position. On the basis, the position of unknown node is continuously updated using Massage Passing (MP), a distributed cooperative method, until the estimated position approaches the real value infinitely. This process requires the method is simple and feasible. To avoid large computation overhead, geometric method is designed to initialize the position of unknown node.According to the difference of RSSIs, we discuss the position initialization in the following situations. As this process depends on the anchors within the communication radius of unknown node, the number of selected anchors is equal or less than three so that the initialization process is simplified. Note that the selection is random. In the communication among sensor nodes, RSSI is affected by the complex environment, so2MaxNoise is defined to indicate the proximity of RSSIs.When RSSIs between selected anchors and unknown node are proximate, the measured distance comparison calculated by measured RSSIs is shown as(11)dij−dik≤2MaxNoise,where i∈U is the unknown node and k,j∈A_onehop is the node within one-hop range. If selected anchors all meet the condition in (11), it indicates that the distance to all selected anchors is almost same. This situation is shown in Figure 5. The initial position of the unknown node is the centroid of selected anchors as
(12)x1Ini=1p∑j∈A_onehop′μ1j,x2Ini=1p∑j∈A_onehop′μ2j,x3Ini=1p∑j∈A_onehop′μ3j,where xIni=x1Ini,x2Ini,x3IniT is the initial position of the unknown node and μj=μ1j,μ2j,μ3jT is the position of the selected anchors in one-hop anchor set. A_onehop′ denotes the one_hop set which only consists of selected anchors. p is the number of selected anchors as it may be one, two, or three.Figure 5
Initial position of the unknown node for proximate RSSI in (11).In Figure5, the shadow is the possible distributed space of the unknown node. The white dot U is the position of the unknown node. The black dot C is the initial position of the unknown node. The black dots A1,A2,A3 are the selected anchors.If measured distance between unknown node and any selected anchor meets the inequality (13), it indicates that the unknown node is closer to the anchor with larger RSSI.
(13)dij−dik>2MaxNoise.When the number of anchor in one-hop anchor set is two, the position relationship of these sensor nodes is shown in Figure6.Figure 6
Initial position of the unknown node for different RSSIs in (13).In Figure6, the white dot U is the position of the unknown node and the white dot C is the midpoint of A1 and A2. Because the unknown node is closer to anchor A1, the shadow representing the possible distributed area is the left half of intersecting space. The line A2C has an intersection with spherical shell. The midpoint UIni of point C and intersection is regarded as the initial position of unknown node as
(14)x1Ini=2R+dA1A24dA1A2μ11+3dA1A2−2R4dA1A2μ12,x2Ini=2R+dA1A24dA1A2μ21+3dA1A2−2R4dA1A2μ22,x3Ini=2R+dA1A24dA1A2μ31+3dA1A2−2R4dA1A2μ32,where dA1A2 is the measured distance between A1 and A2. μ1=μ11,μ21,μ31T is the coordinate of anchor A1. μ2=μ12,μ22,μ32T is the coordinate of anchor A2.When the number of selected anchors in one-hop anchor set is three and at least one measured distance is far more than other measured distance, it is a different situation compared with Figure5. Assumed that the RSSIs of selected anchors meet the inequality (15), then distances of these anchors meet the inequality (16) accordingly.
(15)PiA1<PiA2<PiA3,A1,A2,A3∈A_onehop,(16)diA1<diA2<diA3,A1,A2,A3∈A_onehop.The subsituation is further defined based on inequality (16) when anchor A1,A2 meets inequality (11) and A1,A3 and A2,A3 meet inequality (13). It indicates that the unknown node is closer to anchor A1,A2 and farther than A3 as shown in Figure 7. The white dot is the centroid of anchor A1,A2,A3. The line A3C has an intersection with spherical shell. As the inequality (16) tells us, the unknown node is in the shadow area. In this situation, midpoint UIni of point C and intersection is regarded as the initial position of the unknown node.Figure 7
Initial position of the unknown node for different RSSIs in (15).By geometric analysis, the coordinate of initial position is as shown in(17)x1Ini=R+dCA32dCA3x1c+R−dCA32dCA3μ13,x2Ini=R+dCA32dCA3x2c+R−dCA32dCA3μ23,x3Ini=R+dCA32dCA3x3c+R−dCA32dCA3μ33,where xc=x1c,x2c,x3cT is the coordinate of centroid C which is obtained from equation (12). dCA3 is the estimated distance between centroid C and anchor A3. μ3=μ13,μ23,μ33T is the coordinate of anchor A3.For the rest subsituations, the unknown node is closer to anchorA1 as shown in Figure 8. These subsituations are A2,A3 meet inequality (11), and A1,A2,A3 do not meet inequality (11). The initial position of the unknown node should be in the area which is close to anchor A1. From Figure 8, the centroid of A1,A2,A3 can be regarded as the initial position.Figure 8
Initial position of the unknown node for different RSSIs for rest subsituation.


## 3.3. Cooperative Localization Method

The initial positions in the above situations are usually the center of possible distributed space. Actually, they still deviate from the real position of the unknown node. To approach the real position, MP, a cooperative localization method, is introduced as since outperforms in 2D localization technology. It fuses position information and distance information of the whole network in a cooperative way so that localization accuracy is improved. In this process, MP only needs to send and receive the position message and RSSI message once while sensor node linearly estimates its position by itself. It largely reduces the communication overhead and computation complexity. For 3D WSN, the added dimension leads to the increasing computation complexity and localization error. It urgently requires localization method to eliminate the effect of added dimension. As a distributed cooperative method, MP has advantages of flexible message exchange and fast calculation which could promote 3D localization technology.To locate unknown nodei, messages from anchor a and unknown node l should be considered where a,l∈A_onehop. Anchor a and unknown node l should cover all the sensor nodes within the communication radius of unknown node i. As the distance-measurement model is nonlinear, variational message passing is introduced to calculate the cooperative message shown in equations (18) and (19). To avoid the large deviation, we design the judgement factor and penalty function for anchor messages and unknown node messages, respectively.
(18)mfia⟶xixi=Pfia⟶xixiexp∫θJabxalnpdiaxi,xadxa,(19)mfil⟶xixi=Pfil⟶xixiexp∫θJlbxllnpdilxi,xldxl,where mfia⟶xixi,mfil⟶xixi are the messages from anchor factor fia and unknown anchor factor fil. bxa,bxl are the confidence from last iteration. θJa and θJl are the judgement factor of anchor and unknown node. They are designed to judge if the updated position meets the constraints in (10). If the updated position meets the constraints, θJ=1. Otherwise, θJ=0.In equations (18) and (19), Pfia⟶xixi,Pfil⟶xixi are the penalty functions. It is calculated by equation (19).
(20)Pxi=expδvix,where vix is the amount change of sensor nodes which meets the constraints (10). If the amount is increased or unchanged after update, vix=1. Otherwise, vix=p/q where p is the node amount which meets the constraints after update. q is the node amount which meets the constraints before update. δ is the float constant which denotes the effect of constraints.The unknown node receives the messages from anchor and other unknown nodes, and it fuses the cooperative messages to update the position of unknown node. The confidence is shown in(21)bxi≜1Z∏a∈A_onehopmfia⟶xixi∏l∈U_onehopmfil⟶xixi,where Z is the confidence constant and U_onehop is other unknown node set in which unknown nodes are within the communication radius of target unknown node.After putting equations (18) and (19) into (21), the equation (21) is transformed into
(22)bxi∝expδVax∑a∈A_onehopθJagiaxi+δ′Vlx∑l∈U_onehopθJlgilxi,where Vax is the global variable of node amount change which is extended from vix. giaxi,gilxi are calculated by
(23)giaxi≜diaσia2μa−xi−12σia2μa−xi2,(24)gilxi≜∫b^xldilσil2xl−xi−12σil2xl−xi2.Because computation complexity needs to be limited in 3D WSNs, we simplify the nonlinear distance formula by Taylor Expansion into linear distance formula. In equations (23) and (24), Fiaxi≜μa−xi and Filxi,xl=xl−xi are, respectively, expanded around x^i∗and x^i∗,x^m∗with second-order Taylor Expansion. Then, the confidence is linearized as
(25)b^xi∝exp−12xiTV∧i−1xi+xiTV∧i−1μ^i.The variance value of node position is as(26)V^i=δVax∑a∈A_onehopiθJa1σia2I−diaσia2∇Fia2+δVlx∑l∈U_onehopθJl1σil2I−dilσil2HFil−1.The mean value of node position is as(27)μ^i=V^iδVax∑a∈A_onehopθJa1σia2μa+diaσia2∇Fia−∇Fia2μ~i+δVlx∑l∈U_onehopθJl1σil2μ~l+dilσil2∇Fil−HFilμ~i,where ∇Fia,∇Fia2 is the first-order and second-order gradient of Fiaxi at x^i∗. ∇Fil,HFil is the first-order partial derivative and Hessian matrix.In 3D WSN localization, the added dimension also increases the dimension of parameters above. Parameters∇Fia,∇Fil,∇Fia2,HFil need to be deduced again as shown in equations
(28)∇Fia=x1i∗−μ1ad^iax2i∗−μ2ad^iax3i∗−μ3ad^ia,(29)∇Fil=x1i∗−x1l∗d^ilx2i∗−x2l∗d^ilx3i∗−x3l∗d^il,(30)∇Fia2=1d^ia−x1i∗−μ1ad^ia3−x1i∗−μ1ax2i∗−μ2ad^ia3−x1i∗−μ1ax3i∗−μ3ad^ia3−x1i∗−μ1ax2i∗−μ2ad^ia31d^ia−x2i∗−μ2ad^ia3−x2i∗−μ2ax3i∗−μ3ad^ia3−x1i∗−μ1ax3i∗−μ3ad^ia3−x2i∗−μ2ax3i∗−μ3ad^ia31d^ia−x3i∗−μ3ad^ia3,(31)HFil=1d^il−x1i∗−x1l∗d^il3−x1i∗−x1l∗x2i∗−x2l∗d^il3−x1i∗−x1l∗x3i∗−x3l∗d^il3−x1i∗−x1l∗x2i∗−x2l∗d^il31d^il−x2i∗−x2l∗d^il3−x2i∗−x2l∗x3i∗−x3l∗d^il3−x1i∗−x1l∗x3i∗−x3l∗d^il3−x2i∗−x2l∗x3i∗−x3l∗d^il31d^il−x3i∗−x3l∗d^il3.The distributed cooperative localization is conducted in the situation of known initial position which is adjusted by the variance and mean. For each round of iteration, the updated position should be compared with the optimized constraints in (10). If the updated position meets the optimized constraints, the updated position would be put into the next iteration. If not, the updated position of last round remains unchanged and would be put into the next iteration. Until the iteration counts reach the setting, the localization process ends.


## 4. Simulation

In this section, simulations are conducted to show the performance of the proposed method in 3D environments. The simulations are designed to locate unknown node in space. All the sensor nodes including anchors and unknown nodes are randomly and uniformly distributed. Figure9 gives an example to show the node distribution in the simulation. The black dots represent the unknown nodes and red dots represent the anchors. Each of them has the same communication radius. In this localization process, the results are based on the average value of repeated simulations. Thus, average localization error (ALE) and cumulative distribution functions (CDFs) are introduced to denote the localization accuracy. On the basis, the simulations are designed to explore the effect of algorithm parameters and the performance compared with other 3D localization methods.Figure 9
The distributed nodes in 3D space.


### 4.1. Algorithm Parameters

In simulation, parameter configuration of proposed algorithm has influence on the localization performance. To explore the localization performance under multiparameter configuration, the simulations are conducted with different parameters. These parameters consist of maxnoise-SD ratio (MSDR), SD of anchor distance (SDA), SD of unknown node distance (SDU), and iteration count. The appropriate selection of algorithm parameters was aimed at improving the localization accuracy and optimizing the localization model.All the simulations in this section have the same simulation environment with forty anchors and one hundred and sixty unknown nodes. The communication radius of all the sensor nodes is 30 m. We assume that the localization environment is in a low level of inference. The parameters of signal are set asGt=Gr=1,L=1,ht=hr=1. The exhibited results in the paper are all the average value of twenty repeated experiments.We firstly explore the effect of maxnoise-SD ratio. For the optimized constraints and initial position, the maxnoise describes the maximal deviation of measured distance which divides the space of possible distribution. It usually depends on the SD from statistical data of measured distance. In theory, maxnoise is usually triple SD of measure distance. Actually, it is affected by the experiment environment, algorithm process, and definition of initial position. In outdoor localization, the SD of measure distance is about 2 m, so we set theSD=2m in the simulation. The MSDR is set as 2.5, 3.0, 3.5, and 4 while the maxnoise is 5, 6, 7, and 8 m. Other algorithm parameters are constants. In the simulation, SDA is 2 and SDU is 2. The iteration count is set as 15. In this condition, the simulation results are shown in Figure 10.Figure 10
The CDFs with different MSDRs.From Figure10, the CDFs are higher when MSDRs are 3 and 3.5. It indicates that the localization outperforms in these conditions. The simulation results are basically consistent with theoretical analysis. However, Figure 10 shows that the localization results when MSDR is 3.5 are better than that when MSDR is 3. Because maxnoise can distinguish the distance size, a larger value than theoretical result can find a more accurate distributed area. It defines the node neighbor in a longer way, but oversize of MSDR would lead to the deviation. When MSDR is 4 or 5, the accuracy decreases largely.SDA and SDU are the posteriori SD of distance between unknown node and other nodes. It affects the localization result through equation (26) and (27). Because the measured position of anchors and estimated position have different accuracy, the localization results vary with the value of SDA and SDU. To explore the effect, simulations are conducted as the SDAs are 1, 2, 4, and 6 and SDUs are 2, 5, 8, and 12. For other algorithm parameters, MSDR is 3 and iteration count is set as 15. The simulation results are shown in Figures 11 and 12.Figure 11
The CDFs with respect to different SDAs.Figure 12
The CDFs with respect to different SDUs.Figure11 shows the CDFs of different SDAs. SDA describes the SD of distance measurement under the condition of measured position of anchor. As the measured position of anchor is accurate through GPS or other devices, its measurement deviation is small compared with estimated position of unknown node. It indicates SDA depends more on measured distance. Figure 11 shows localization results under the simulation environment are better when SDA is 2 m. On contrary, SDU is much larger if better localization results are expected. Figure 12 shows localization results are better when SDU is 5 m or 8 m. The reason is SDU not only depends on the measured distance but also is affected by the estimated position of unknown node. Obviously, the estimated position of unknown node has lower accuracy compared with measured position of anchor. Therefore, SDA should be smaller than SDU when the localization method is applied in practice and the values of SDA and SDU should be adjusted according to sensor-located communication environment.Iteration count and convergence is important to evaluate the performance of the proposed algorithm. Their effects are explored in this section so that optimal iteration count is selected. The optimal selection not only improves the localization accuracy but also avoids redundant computation. The simulations are conducted when MSDR is 3, SDA is 2, and SDU is 2. The simulation results are shown in Figure13.Figure 13
The ALEs change with iterations.In Figure13, the ALE decreases when the count of iteration increases. From the first iteration to fifth iteration, the decreasing speed is fast. After that, the decreasing speed slows down. The phenomenon indicates that cooperative algorithm constantly adjusts the estimated position of unknown node to approach the ground truth as soon as possible. When the count of iteration reaches 10, the ALE is convergent. To avoid the redundant computation, the count of iteration is usually set as 10.


### 4.2. Method Comparison

The proposed method (PM) is tested with several algorithm parameters, and its optimal parameters are selected in different scenarios. Meanwhile, the method comparison should be designed to explore its improvement of performance compared with existing methods. In 3D localization, 3D-DV-HOP, Ou-3D in paper [19], and 3D-MDS in paper [15] are widely used and outperforms well, so they are selected to compare with proposed algorithm. These simulations are conducted simultaneously in the various scenarios with different communication radius and node density. The cross-over simulations help find the advantages and better application background of the listed methods. For the proposed method, the algorithm parameters are set as MSDR is 3, SDA is 2, SDU is 2, and iteration count is 15. We assume that the localization environment is in a low level of inference. The proportion of anchor is 20%, and the exhibited results in the paper are the average value of twenty repeated experiments.To explore the performance of the four methods, the communication radius is set as 20 m, 30 m, 40 m, and 50 m while the total number of nodes is 200. In this condition, the comparison results are shown in Figure14.Figure 14
Localization accuracy with different communication radius.From Figure14, the accuracy of all methods increases with communication radius increases. It indicates that localization results of these methods all depend on the communication radius. When the communication radius increases, the neighboring nodes of unknown nodes are more so that they can provide more reference for localization process. However, the changes and trends of these methods are different. The proposed method in the paper, 3D-DV-HOP and 3D-MDS change less compared with Ou-3D, so Ou-3D is more sensitive to communication radius. Although the localization accuracy of Ou-3D is highest when the communication radius is long, it would not apply for the special condition with short communication radius.Among four localization methods, the proposed method and Ou-3D have higher accuracy. They can improve the accuracy by 20% to 50%. The proposed method has close accuracy compared with Ou-3D. When the communication is less than 30 m, the proposed method is better. When the communication is more than 30 m, Ou-3D is better. For localization accuracy from Figure15, the proposed method has good performance and is acceptable.Figure 15
Localization accuracy with different node density.To explore the performance about the effect of node density, the total number of nodes is set as 100, 200, 300, and 400 while the communication radius is all 30 m. In this condition, the comparison results are shown in Figure15.Figure15 shows the accuracy of four methods as the node density changes. Among four methods, 3D-MDS is the method which is most sensitive to the node density while Ou-3D is not affected by node density. It is due to localization of Ou-3D only through flying anchor and no interaction existed among unknown nodes. The accuracy of proposed method and 3D-DV-HOP improves as the node density increases, but they are less sensitive to the node density.From Figure15, 3D-DV-HOP has the lowest localization accuracy while PM and Ou-3D are close in the accuracy. When the total number of nodes is 400, the 3D-MDS is the most accurate method. However, it depends on the node density too much. Considering the localization accuracy and the effect from node density, the proposed method and Ou-3D perform best.


### 4.3. Algorithm Efficiency

To evaluate the algorithm performance, localization accuracy is not the only benchmark. Especially for localization technology in large-scale WSNs, the method is expected to be highly efficient. Application requires the localization algorithm with low communication overhead and computation complexity. In this section, the proposed method is compared with 3D-DV-HOP, Ou-3D, and 3D-MDS in terms of communication overhead and computation complexity.The communication overhead is firstly analyzed. We list the communication overhead of four methods in Table1.Table 1
Communication overhead comparison.
AlgorithmPackagePMO(PU)3D-DV-HOPO(U)Ou-3DO(QU)3D-MDSO(U2)Table1 shows the approximate packages in the localization where U denotes the number of the unknown nodes. Among four methods, 3D-MDS is the concentrated method which has the heaviest communication load. Other three methods have close communication load, but they are different when the total number of nodes is large. For PM, P denotes the number of nodes within the communication radius. In most cases, its value is small, so it would not overload the network. Ou-3D has the same order of magnitude with PM. Here, Q denotes the number of anchors which build communication with the unknown node. In fact, this process requires that the anchor be always in the status of communication and the unknown node be waiting for communication. Once the movement trajectory of flying anchor is not reasonable, the communication would increase a lot. Compared with these methods, 3D-DV-HOP has the lowest communication load as the simplest method. Because heavy communication load leads to energy consumption, it hinders the application of large scale WSN in complex outdoor environment. We select the communication overhead to evaluate the communication load and energy consumption which was aimed at improving the efficiency and effectivity of the method. The analysis of Table 1 indicates that the communication overhead of PM and 3D-DV-HOP is acceptable.In the localization of WSNs, the hardware of sensors always limits the computation complexity and the large amount of computation would add energy consumption. These situations require low computation complexity of localization method, so we compare the computation complexity as shown in Table2.Table 2
Computation complexity comparison.
AlgorithmComplexityPMO(UM)3D-DV-HOPO(U)Ou-3DO(UN+A)3D-MDSO(U2)Among four methods, 3D-DV-HOP performs best in computation complexity compared with other three methods. PM and Ou-3D have the same order of magnitude. For PM,M denotes the distributed cooperative computation and its value is not large due to the limited counts of iteration. For Ou-3D, N is the geometric computation and A is the computation of flying anchor’s path plan. The geometric computation N is comparable with distributed cooperative computation M, but the computation of path plan A is large and affects the performance a lot.Finally, we evaluate the localization methods considering both accuracy and efficiency. 3D-DV-HOP is the most efficient method, but its accuracy is not acceptable. 3D-MDS outperforms in the condition of high node density, but it costs more communication overhead and computation complexity. PM and Ou-3D have similar performance in accuracy, but the efficiency of Ou-3D is more uncertain due to the flying anchor. Although localization process of Ou-3D does not add extra communication overhead and complexity computation, it is affected by the flying anchor which needs to plan its flying path and sends signal to other nodes all the time. In the fixed or simple distributed space of node, the flying anchor is feasible. When the localization faces a more complex environment, the Ou-3D is affected. Meanwhile, Ou-3D has to complete the whole path to locate all the sensor nodes and this process cannot be simultaneous. It limits the application of Ou-3D compared with other methods. To compromise the accuracy and efficiency, the proposed method outperforms. It improves the localization accuracy as the communication overhead and computation complexity are reduced as much as possible. Especially for large scale and complex WSNs, the proposed method can balance the localization accuracy and efficiency.


## 4.1. Algorithm Parameters

In simulation, parameter configuration of proposed algorithm has influence on the localization performance. To explore the localization performance under multiparameter configuration, the simulations are conducted with different parameters. These parameters consist of maxnoise-SD ratio (MSDR), SD of anchor distance (SDA), SD of unknown node distance (SDU), and iteration count. The appropriate selection of algorithm parameters was aimed at improving the localization accuracy and optimizing the localization model.All the simulations in this section have the same simulation environment with forty anchors and one hundred and sixty unknown nodes. The communication radius of all the sensor nodes is 30 m. We assume that the localization environment is in a low level of inference. The parameters of signal are set asGt=Gr=1,L=1,ht=hr=1. The exhibited results in the paper are all the average value of twenty repeated experiments.We firstly explore the effect of maxnoise-SD ratio. For the optimized constraints and initial position, the maxnoise describes the maximal deviation of measured distance which divides the space of possible distribution. It usually depends on the SD from statistical data of measured distance. In theory, maxnoise is usually triple SD of measure distance. Actually, it is affected by the experiment environment, algorithm process, and definition of initial position. In outdoor localization, the SD of measure distance is about 2 m, so we set theSD=2m in the simulation. The MSDR is set as 2.5, 3.0, 3.5, and 4 while the maxnoise is 5, 6, 7, and 8 m. Other algorithm parameters are constants. In the simulation, SDA is 2 and SDU is 2. The iteration count is set as 15. In this condition, the simulation results are shown in Figure 10.Figure 10
The CDFs with different MSDRs.From Figure10, the CDFs are higher when MSDRs are 3 and 3.5. It indicates that the localization outperforms in these conditions. The simulation results are basically consistent with theoretical analysis. However, Figure 10 shows that the localization results when MSDR is 3.5 are better than that when MSDR is 3. Because maxnoise can distinguish the distance size, a larger value than theoretical result can find a more accurate distributed area. It defines the node neighbor in a longer way, but oversize of MSDR would lead to the deviation. When MSDR is 4 or 5, the accuracy decreases largely.SDA and SDU are the posteriori SD of distance between unknown node and other nodes. It affects the localization result through equation (26) and (27). Because the measured position of anchors and estimated position have different accuracy, the localization results vary with the value of SDA and SDU. To explore the effect, simulations are conducted as the SDAs are 1, 2, 4, and 6 and SDUs are 2, 5, 8, and 12. For other algorithm parameters, MSDR is 3 and iteration count is set as 15. The simulation results are shown in Figures 11 and 12.Figure 11
The CDFs with respect to different SDAs.Figure 12
The CDFs with respect to different SDUs.Figure11 shows the CDFs of different SDAs. SDA describes the SD of distance measurement under the condition of measured position of anchor. As the measured position of anchor is accurate through GPS or other devices, its measurement deviation is small compared with estimated position of unknown node. It indicates SDA depends more on measured distance. Figure 11 shows localization results under the simulation environment are better when SDA is 2 m. On contrary, SDU is much larger if better localization results are expected. Figure 12 shows localization results are better when SDU is 5 m or 8 m. The reason is SDU not only depends on the measured distance but also is affected by the estimated position of unknown node. Obviously, the estimated position of unknown node has lower accuracy compared with measured position of anchor. Therefore, SDA should be smaller than SDU when the localization method is applied in practice and the values of SDA and SDU should be adjusted according to sensor-located communication environment.Iteration count and convergence is important to evaluate the performance of the proposed algorithm. Their effects are explored in this section so that optimal iteration count is selected. The optimal selection not only improves the localization accuracy but also avoids redundant computation. The simulations are conducted when MSDR is 3, SDA is 2, and SDU is 2. The simulation results are shown in Figure13.Figure 13
The ALEs change with iterations.In Figure13, the ALE decreases when the count of iteration increases. From the first iteration to fifth iteration, the decreasing speed is fast. After that, the decreasing speed slows down. The phenomenon indicates that cooperative algorithm constantly adjusts the estimated position of unknown node to approach the ground truth as soon as possible. When the count of iteration reaches 10, the ALE is convergent. To avoid the redundant computation, the count of iteration is usually set as 10.


## 4.2. Method Comparison

The proposed method (PM) is tested with several algorithm parameters, and its optimal parameters are selected in different scenarios. Meanwhile, the method comparison should be designed to explore its improvement of performance compared with existing methods. In 3D localization, 3D-DV-HOP, Ou-3D in paper [19], and 3D-MDS in paper [15] are widely used and outperforms well, so they are selected to compare with proposed algorithm. These simulations are conducted simultaneously in the various scenarios with different communication radius and node density. The cross-over simulations help find the advantages and better application background of the listed methods. For the proposed method, the algorithm parameters are set as MSDR is 3, SDA is 2, SDU is 2, and iteration count is 15. We assume that the localization environment is in a low level of inference. The proportion of anchor is 20%, and the exhibited results in the paper are the average value of twenty repeated experiments.To explore the performance of the four methods, the communication radius is set as 20 m, 30 m, 40 m, and 50 m while the total number of nodes is 200. In this condition, the comparison results are shown in Figure14.Figure 14
Localization accuracy with different communication radius.From Figure14, the accuracy of all methods increases with communication radius increases. It indicates that localization results of these methods all depend on the communication radius. When the communication radius increases, the neighboring nodes of unknown nodes are more so that they can provide more reference for localization process. However, the changes and trends of these methods are different. The proposed method in the paper, 3D-DV-HOP and 3D-MDS change less compared with Ou-3D, so Ou-3D is more sensitive to communication radius. Although the localization accuracy of Ou-3D is highest when the communication radius is long, it would not apply for the special condition with short communication radius.Among four localization methods, the proposed method and Ou-3D have higher accuracy. They can improve the accuracy by 20% to 50%. The proposed method has close accuracy compared with Ou-3D. When the communication is less than 30 m, the proposed method is better. When the communication is more than 30 m, Ou-3D is better. For localization accuracy from Figure15, the proposed method has good performance and is acceptable.Figure 15
Localization accuracy with different node density.To explore the performance about the effect of node density, the total number of nodes is set as 100, 200, 300, and 400 while the communication radius is all 30 m. In this condition, the comparison results are shown in Figure15.Figure15 shows the accuracy of four methods as the node density changes. Among four methods, 3D-MDS is the method which is most sensitive to the node density while Ou-3D is not affected by node density. It is due to localization of Ou-3D only through flying anchor and no interaction existed among unknown nodes. The accuracy of proposed method and 3D-DV-HOP improves as the node density increases, but they are less sensitive to the node density.From Figure15, 3D-DV-HOP has the lowest localization accuracy while PM and Ou-3D are close in the accuracy. When the total number of nodes is 400, the 3D-MDS is the most accurate method. However, it depends on the node density too much. Considering the localization accuracy and the effect from node density, the proposed method and Ou-3D perform best.


## 4.3. Algorithm Efficiency

To evaluate the algorithm performance, localization accuracy is not the only benchmark. Especially for localization technology in large-scale WSNs, the method is expected to be highly efficient. Application requires the localization algorithm with low communication overhead and computation complexity. In this section, the proposed method is compared with 3D-DV-HOP, Ou-3D, and 3D-MDS in terms of communication overhead and computation complexity.The communication overhead is firstly analyzed. We list the communication overhead of four methods in Table1.Table 1
Communication overhead comparison.
AlgorithmPackagePMO(PU)3D-DV-HOPO(U)Ou-3DO(QU)3D-MDSO(U2)Table1 shows the approximate packages in the localization where U denotes the number of the unknown nodes. Among four methods, 3D-MDS is the concentrated method which has the heaviest communication load. Other three methods have close communication load, but they are different when the total number of nodes is large. For PM, P denotes the number of nodes within the communication radius. In most cases, its value is small, so it would not overload the network. Ou-3D has the same order of magnitude with PM. Here, Q denotes the number of anchors which build communication with the unknown node. In fact, this process requires that the anchor be always in the status of communication and the unknown node be waiting for communication. Once the movement trajectory of flying anchor is not reasonable, the communication would increase a lot. Compared with these methods, 3D-DV-HOP has the lowest communication load as the simplest method. Because heavy communication load leads to energy consumption, it hinders the application of large scale WSN in complex outdoor environment. We select the communication overhead to evaluate the communication load and energy consumption which was aimed at improving the efficiency and effectivity of the method. The analysis of Table 1 indicates that the communication overhead of PM and 3D-DV-HOP is acceptable.In the localization of WSNs, the hardware of sensors always limits the computation complexity and the large amount of computation would add energy consumption. These situations require low computation complexity of localization method, so we compare the computation complexity as shown in Table2.Table 2
Computation complexity comparison.
AlgorithmComplexityPMO(UM)3D-DV-HOPO(U)Ou-3DO(UN+A)3D-MDSO(U2)Among four methods, 3D-DV-HOP performs best in computation complexity compared with other three methods. PM and Ou-3D have the same order of magnitude. For PM,M denotes the distributed cooperative computation and its value is not large due to the limited counts of iteration. For Ou-3D, N is the geometric computation and A is the computation of flying anchor’s path plan. The geometric computation N is comparable with distributed cooperative computation M, but the computation of path plan A is large and affects the performance a lot.Finally, we evaluate the localization methods considering both accuracy and efficiency. 3D-DV-HOP is the most efficient method, but its accuracy is not acceptable. 3D-MDS outperforms in the condition of high node density, but it costs more communication overhead and computation complexity. PM and Ou-3D have similar performance in accuracy, but the efficiency of Ou-3D is more uncertain due to the flying anchor. Although localization process of Ou-3D does not add extra communication overhead and complexity computation, it is affected by the flying anchor which needs to plan its flying path and sends signal to other nodes all the time. In the fixed or simple distributed space of node, the flying anchor is feasible. When the localization faces a more complex environment, the Ou-3D is affected. Meanwhile, Ou-3D has to complete the whole path to locate all the sensor nodes and this process cannot be simultaneous. It limits the application of Ou-3D compared with other methods. To compromise the accuracy and efficiency, the proposed method outperforms. It improves the localization accuracy as the communication overhead and computation complexity are reduced as much as possible. Especially for large scale and complex WSNs, the proposed method can balance the localization accuracy and efficiency.


## 5. Conclusion

In this paper, we developed a cooperative localization model for 3D WSN. Based on the model, we established optimized constraints which initialized the position of unknown node and calibrated cooperative process. The distributed cooperative method was designed to approach the ground truth through VMP update rule of MP. The simulation results showed that proposed method outperformed in accuracy and the distributed design improved the efficiency. The outcome of this paper provides a guideline for the localization of 3D WSN, enabling robust and energy-efficient localization networks.



---

*Source: 9031939-2022-04-29.xml*