# 3D Localization Algorithm Based on Voronoi Diagram and Rank Sequence in Wireless Sensor Network

Authors: Xi Yang; Fang Yan; Jun Liu
Journal: Scientific Programming
 (2017)

---

## Abstract

Accurate nodes’ localization is a key problem in wireless sensor network (WSN for short). This paper discusses and analyzes the effects of Voronoi diagram in 3D location space. Then it proposes Sequence Localization Correction algorithm based on 3D Voronoi diagram (SLC3V), which introduces 3D Voronoi diagram to divide the 3D location space and constructs the rank sequence tables of virtual beacon nodes. SLC3V uses RSSI method between beacon nodes as a reference to correct the measured distance and fixes the location sequence of unknown nodes. Next, it selects optimal parameterN and realizes the weighted location estimate withN valid virtual beacon nodes by normalization process of rank correlation coefficients. Compared with other sequence location algorithms, simulation experiments show that it can improve the localization accuracy for nodes in complex 3D space with less measurements and computational costs.


---

## Body

## 1. Introduction

Due to its broad applications, researchers have been concerned with wireless sensor network (WSN). As one of the key technologies of the Internet of Things, WSN has been widely applied in various fields, such as military affairs, wise industries, environmental monitor, and smart home. The location information of wireless sensor nodes is needed in many applications. And location information can be used to self-organize, manage networks, select the optimal route, determine the occurrence area of the monitoring events, track moving targets, and so on. Therefore, node localization is attractive in wireless sensor network and plays a key role in the application of wireless sensor network [1–3].Due to the characteristics of wireless sensor network, traditional localization methods in computer network cannot be directly applied, such as Global Positioning System (GPS).Only a few sensor nodes can be equipped with GPS module or predeployed in a specific location if the operation cost and maintenance cost are taken into consideration. These nodes can know their own coordinates and assist other nodes to realize self-localization.Localization accuracy directly affects the application effects, so great attentions have been paid to the localization problem. And many researchers have put forward many theories and efficient solutions.In the past, most of the researches only paid much attention to the self-localization in 2D space with beacon nodes, which know their own location information beforehand (for example, [4, 5]). And current localization algorithms in 2D can be classified into two kinds: range-based algorithm and range-free algorithm [6, 7]. For range-based algorithms, distances are commonly computed by using different parameters such as time, angles, or signal strength and the location is estimated on the basis of the distances. For the range-free algorithms, unknown nodes calculate their approximate locations by using information from a few beacon nodes.With the mature technology and market promotion, beacon nodes may be dynamic and localization will expand from the two-dimensional (2D) space to three-dimensional (3D) space.As we all know, wireless sensor nodes are deployed in real environment, which is three-dimensional. And many applications often need three-dimensional location information. Localization in 3D space is more difficult than in 2D space. In addition, more factors should be considered in 3D localization, such as the environmental changes, the insufficient number of beacon nodes, and various disturbing effects in the signal transmission process.Now, 3D localization has become a current research trend and one of the hot problems. Many researchers extend 2D localization technologies into 3D space, such as tetrahedral centroid localization algorithm and 3D DV-Hop, APIT, RSSI location, and partial filter, which have achieved good results and have been used to some extent.Currently, localization algorithms in 3D space can include two categories: hierarchical location and nonhierarchical location. In hierarchical location, nodes are mostly deployed in the interior of the monitoring buildings. In this condition, users or networks only need the floor information of unknown node replacing the specificZ coordinate value. Some of the proposals [8, 9] in this category are discussed in greater detail. However, nodes may be deployed underwater or in hills in nonhierarchical location. Users often need to estimate the specific Z coordinate value. Such approaches are depicted in [10–12].In this paper, we introduce Voronoi diagram into localization algorithm and propose a new Sequence Localization Correction algorithm based on Voronoi diagram, which can be used in 3D space. The new algorithm divides location space with 3D Voronoi diagram, corrects the measured distance, and fixes location sequence of unknown nodes, which reduces the space partition complexity and raises localization accuracy. In order to reduce the effects of the number of real beacon nodes, SL3CV selects optimal parameterN to determine the number of valid virtual beacon nodes in the last localization estimation, which also improves the localization accuracy. The localization estimation of unknown nodes can be calculated through the weights based on the optimal location sequence table of virtual beacon nodes.This paper includes 5 sections. The concepts of 3D Voronoi diagram and location sequences are described in Section2. Section 3 describes and analyzes the localization procedures of SLC3V algorithm in 3D space. This paper analyzes and compares the proposed localization algorithm with other algorithms through an exhaustive systematic performance study and simulation experiments in Section 4. Finally, this paper concludes in Section 5.


## 2. Related Techniques

### 2.1. 3D Voronoi

There are many space partition methods. Voronoi diagram is a kind of partition method, which divides the space into a number of subregions. Now Voronoi diagram is widely used in various fields, such as geographical information system, information system, and meteorology. Many researchers use Voronoi diagram to study the coverage problem in WSN.Voronoi diagram divides the plane into many regions. We are given a finite set of points{p1,…,pn}, 2⩽n<∞, in the Euclidean plane. Let X(x,y) be any point in the space. Let d(pi,X) denote the Euclidean distance with X(x,y) and pi(xi,yi), i∈I={1,2,…,n}. Then (1)dpi,X=xi-x2+yi-y2.Voronoi diagram divides the plane inton regions (Voronoi region) around each generator point pi, which makes any point X in Voronoi region V(pi) satisfy the following condition: (2)Vpi,X=x∣dpi,X⩽dpj,X,∀i≠j∧i,j∈I.Then V(P) is the sets of Voronoi region V(pi).We find that 2D Voronoi diagram includes many continuous polygons, which are composed of a set of perpendicular bisectors. And all perpendicular bisectors are vertical to the connection lines between two adjacent points. With the increase of dimension, the formation of Voronoi cells has changed into high dimensional polyhedron. Therefore a Voronoi cell in 3D space is a 3D polyhedron.After divided, any point in any given Voronoi cell is closer to the corresponding Voronoi site than other Voronoi sites. And all Voronoi cells combine together without overlapping and seams in [13, 14].Because of the practicability of 3D Voronoi diagram, there are many computational methods developed to divide 3D discrete point set. In order to decrease the computational complexity, many researchers proposed various fast generation methods of 3D Voronoi diagram.Figure1 shows the 3D Voronoi diagram of 20 scattered points in the 3D closed space, in which the dots are 20 discrete points randomly deployed.Figure 1
Voronoi diagram in 3D space.


### 2.2. Sequence-Based Localization

Recently, some researches propose sequence-based localization method, which is efficient by combining range-based algorithm and range-free algorithm, but it is used in almost 2D space [15, 16]. The procedure of sequence-based localization in 2D space is given as follows:(1)
Construct the boundary of 2D space.(2)
Divide 2D space into three kinds of region, such as vertices, edges, and faces by a set of perpendicular bisectors between all beacon nodes.(3)
Compute the centroids of every region, which are called virtual beacon nodes, and the distance between virtual beacon nodes and real beacon nodes.(4)
Determine all location sequences of virtual beacon nodes in the localization space and rank them in a location sequence table.(5)
Calculate the rank correlation coefficient between the location sequence of unknown node and the other sequence of virtual beacon nodes in the location sequence table and search for the maximum value as the nearest location sequence to the unknown node location sequence. The centroid mapped to by that sequence is the localization estimate of the unknown node.Figure2 shows an example of sequence for four reference nodes. In the example, the four predefined nodes are scattered in the plane. Region 3 is a face, and its location sequence is 4321. Similarly, Region 2 is an edge, and its location sequence is 1134. Similarly, Region 4 is a point, and its location sequence is 3311.Figure 2
Example of sequence for four reference nodes.Compared with other RSSI localization methods, sequence-based localization algorithm does not use RSSI to compute distance. RSSI is used to determine the location sequence of the unknown node.In three-dimensional space, we extend the 2D sequence-based algorithm and divide 3D space into three kinds of region, such as edges, faces, and bodies by a set of min-vertical planes.


## 2.1. 3D Voronoi

There are many space partition methods. Voronoi diagram is a kind of partition method, which divides the space into a number of subregions. Now Voronoi diagram is widely used in various fields, such as geographical information system, information system, and meteorology. Many researchers use Voronoi diagram to study the coverage problem in WSN.Voronoi diagram divides the plane into many regions. We are given a finite set of points{p1,…,pn}, 2⩽n<∞, in the Euclidean plane. Let X(x,y) be any point in the space. Let d(pi,X) denote the Euclidean distance with X(x,y) and pi(xi,yi), i∈I={1,2,…,n}. Then (1)dpi,X=xi-x2+yi-y2.Voronoi diagram divides the plane inton regions (Voronoi region) around each generator point pi, which makes any point X in Voronoi region V(pi) satisfy the following condition: (2)Vpi,X=x∣dpi,X⩽dpj,X,∀i≠j∧i,j∈I.Then V(P) is the sets of Voronoi region V(pi).We find that 2D Voronoi diagram includes many continuous polygons, which are composed of a set of perpendicular bisectors. And all perpendicular bisectors are vertical to the connection lines between two adjacent points. With the increase of dimension, the formation of Voronoi cells has changed into high dimensional polyhedron. Therefore a Voronoi cell in 3D space is a 3D polyhedron.After divided, any point in any given Voronoi cell is closer to the corresponding Voronoi site than other Voronoi sites. And all Voronoi cells combine together without overlapping and seams in [13, 14].Because of the practicability of 3D Voronoi diagram, there are many computational methods developed to divide 3D discrete point set. In order to decrease the computational complexity, many researchers proposed various fast generation methods of 3D Voronoi diagram.Figure1 shows the 3D Voronoi diagram of 20 scattered points in the 3D closed space, in which the dots are 20 discrete points randomly deployed.Figure 1
Voronoi diagram in 3D space.


## 2.2. Sequence-Based Localization

Recently, some researches propose sequence-based localization method, which is efficient by combining range-based algorithm and range-free algorithm, but it is used in almost 2D space [15, 16]. The procedure of sequence-based localization in 2D space is given as follows:(1)
Construct the boundary of 2D space.(2)
Divide 2D space into three kinds of region, such as vertices, edges, and faces by a set of perpendicular bisectors between all beacon nodes.(3)
Compute the centroids of every region, which are called virtual beacon nodes, and the distance between virtual beacon nodes and real beacon nodes.(4)
Determine all location sequences of virtual beacon nodes in the localization space and rank them in a location sequence table.(5)
Calculate the rank correlation coefficient between the location sequence of unknown node and the other sequence of virtual beacon nodes in the location sequence table and search for the maximum value as the nearest location sequence to the unknown node location sequence. The centroid mapped to by that sequence is the localization estimate of the unknown node.Figure2 shows an example of sequence for four reference nodes. In the example, the four predefined nodes are scattered in the plane. Region 3 is a face, and its location sequence is 4321. Similarly, Region 2 is an edge, and its location sequence is 1134. Similarly, Region 4 is a point, and its location sequence is 3311.Figure 2
Example of sequence for four reference nodes.Compared with other RSSI localization methods, sequence-based localization algorithm does not use RSSI to compute distance. RSSI is used to determine the location sequence of the unknown node.In three-dimensional space, we extend the 2D sequence-based algorithm and divide 3D space into three kinds of region, such as edges, faces, and bodies by a set of min-vertical planes.


## 3. SLC3V Algorithm

Based on 2D sequence-based localization algorithm, 3D sequence-based orthocenter localization algorithm (3DSBO for short) is proposed in [17]. However, we find that the space division methods are not optimal and localization errors are rather large with the decrease in the number of real beacon nodes while they are high-accuracy localization technique. And the errors will increase if we do not consider the environmental influences on the estimation of the location sequences. And 3DSBO only use three virtual beacon nodes to estimate the location of unknown nodes.Voronoi diagram has high order mode, so we consider the 3D application scenarios. While 3D Voronoi diagram has been introduced into sequence localization [18], SL3V cannot correct location sequence of the unknown node according to the environment. Furthermore, SL3V chooses the optimal polyhedron and calculates the coordinate with the virtual beacon nodes in the optimal polyhedron, which increases the localization error.This paper extends Sequence Localization Correction algorithm based on 3D Voronoi diagram (SLC3V), which considers dividing the 3D space by using 3D Voronoi diagram. After partition, SLC3V determines the centroids of three kinds of regions in the polyhedrons, which are called virtual beacon nodes. Then it computes the distance between virtual beacon nodes and real beacon nodes. According to the distance rank, we can form the location sequence table of all beacon nodes, including real beacon nodes and virtual beacon nodes. Then we compute and correct the location sequence table of the unknown nodes by using RSSI method. Therefore the location sequence table of the unknown nodes will be closer to the truth.By estimating the coordinate of real beacon nodes with Kendall coefficients, it selects the optimal parameterN, which decides the valid number of virtual beacon nodes used in localization estimation. Finally, it produces the optimal localization sequences of N valid virtual beacon nodes and estimates the coordinate of the unknown node with Kendall coefficients between the sequences in optimal localization sequence table and the unknown node sequence.


### 3.1. Division of 3D Space

In the 3D space, we construct the cube boundary according to the location environment. The real beacon nodes are scattered in the 3D space randomly. The real beacon nodes are the real nodes deployed by users.Next we use the 3D Voronoi diagram to divide the 3D space. Then the Voronoi polyhedrons are produced. Each real beacon node is interior of the corresponding Voronoi polyhedron. In order to reduce the complexity of partition, we use the fast method in [13] to generate 3D Voronoi diagram.After partition, 3D space includes three kinds of regions, such as edges, faces, and bodies by a set of min-vertical planes.We present an example to illustrate the above ideas. As shown in Figure3, there are 3 real beacon nodes defined as A, B, and C, which are marked by the solid dotes.Figure 3
Real beacon nodes in 3D space.


### 3.2. Location Sequence Calculation

Firstly, we should determine all virtual beacon nodes based on the partition method. This paper marks all the regions and calculates the centroid of every region, which is defined as virtual beacon nodes. Then we sort all virtual beacon nodes. Because the location space is 3D, the kinds of regions change from vertices, edges, and faces into edges, faces, and bodies.For simplifying the calculation, we define the centroid of every region as follows. The centroid of any edge is its midpoint. The centroid of any face is calculated according to [15]. The centroid of any body is midpoint of the line between the two farthest points in the corresponding polyhedron.Then we can rank the location sequences of virtual beacon nodes according to distance between the virtual beacon nodes and real beacon nodes.In the 3D space, the positions of real beacon nodes are known, and all virtual beacon nodes are determined after partition. So we can calculate the distance between any virtual beacon nodes and all real beacon nodes. Then we can assign the location sequence table values based on distance, which is the indication of how near or far the virtual beacon node is from all real beacon nodes.In the example of Figure3, hollow dotes, such as E, F, and G, represent virtual beacon nodes. And each virtual beacon node has its own location sequence based on the distance rank, which is marked beside it in Figure 3. Node E is the centroid of edges, and its location sequence is 123, since the distance rank of A from it is 1 (A is the closest), and the respective distance rank of C is 3 (C is the farthest). Similarly, node G is the centroid of bodies, and its location sequence is 131. Node F is the centroid of faces, and its location sequence is 321.After this step, the location sequence table of all virtual beacon nodes can be calculated in any 3D space with real beacon nodes.


### 3.3. Location Sequence Correction of Unknown Nodes

In order to obtain the distance rank of unknown nodes, we assume that the real beacon nodes send data package to its neighbor nodes. And all unknown nodes are in the transmission area of real beacon nodes. So the unknown nodes measure the distance to real beacon nodes by using the Received Signal Strength Indicator (RSSI) method. According to the distance measured, any unknown node can determine its own location sequence. If location sequences of unknown nodes are more accurate, the localization estimate of unknown nodes has better accuracy. So we will use the distance and RSSI between real beacon nodes as a reference to correct the measured distance and fix location sequence of unknown nodes.R S S I i is the average RSSI (dbm) of the signal, which unknown node X receives from beacon node Bi. Pi is the average power (mW) of the signal which unknown node X receives from beacon node Bi. So the transformational relation between RSSIi and Pi is shown in(3)Pi=10RSSIi/10.R S S I i j is the average Received Signal Strength Indicator (RSSI) (dbm) of the signal, which real beacon node Bi receives from real beacon node Bj. Pij is the average power of the signal which real beacon node Bi receives from real beacon node Bj. Similarly, the transformational relation between RSSIij and Pij is shown in (4)Pij=10RSSIij/10.d B i j is the distance between real beacon node Bi and real beacon node Bj, which is deduced according to (1). dij is the distance between unknown node X and real beacon node Bi. Then, we can deduce the relation equation as follows:(5)dij=Pij1/η×dBijPi1/η.So,di represents the average value of dij, which is the distance between unknown nodes X and real beacon node Bi. R is the number of real beacon nodes.(6)di=∑j=1RdijR.From the above definition, location sequence of unknown node is deduced and corrected as follows:(1)
All real beacon nodes broadcast information in the same power periodically. Then unknown nodes will receive RSSI value of each real beacon node and calculate respective average valueRSSIi. Real beacon node Bi also can calculate the corresponding RSSIij of real beacon node Bj.(2)
All real beacon nodes broadcastPij and dBij, which are calculated by using (4). Then unknown nodes will receive information and calculate di. Finally, location sequence of unknown nodes can be decided according to the fixed di.Because of the RSSI correction, unknown nodes can correct their measured distance according to the environment. Thus the algorithm in this paper can fix location sequence of unknown node and ensure location sequence consistent with the actual situation.


### 3.4. Optimal ParameterN Selection

In this step, we calculate the order correlation coefficients between the vectors in sequence table of virtual beacon nodes and the unknown node sequence, respectively.Statistics offers two metrics to calculate the rank correlation coefficient between two location sequences. They are Spearman’s Coefficient and Kendall’s Tau, respectively. According to the analysis [15] and our simulation results, Kendall’s Tau can obtain better performance in localization algorithm. So we describe it simply. Kendall’s Tau is often used to calculate the correlation between the two sequences. Given two location sequences U=ui and V=vi, 1≤i≤n, where ui and vi represent the ranks of different beacon nodes, Kendall’s Tau compares all the n(n-1)/2 possible pairs of ranks ui,vi and uj,vj, respectively, to determine the numbers of matching pairs and nonmatching pairs. A pair is matching or concordant if ui>uj⇒vi>vj or ui<uj⇒vi<vj and nonmatching or discordant if ui>uj⇒vi<vj or ui<uj⇒vi>vj. The correlation between two sequences is calculated as follows:(7)τ=nc-ndnc+nd+ntunc+nd+ntv,where nc is the number of concordant pairs, nd is the number of discordant pairs, ntu is the number of ties in U, and ntv is the number of ties in V. The range of τ is [-1,1].At the same time, we should calculate the Kendall coefficients between the vectors in sequence table of virtual beacon nodes and the real beacon nodes sequence, respectively.Compared with other algorithm, this paper uses parameterN to determine the optimal number of virtual beacon nodes that are used in the weighted estimation. The suitable parameter N can decrease the localization error. We define all real beacon nodes as the sample set S and select the optimal parameter N according to localization estimation of real beacon nodes. We calculate the optimal parameter Nj value of jth real beacon node. Then the final optimal parameter N is the average of Nj.For example, given the location sequenceU of any real beacon node Yjx,y,z, Yj∈S, SLC3V obtains the location sequence table of virtual beacon nodes T=T1,T2,….According to (7), we can calculate the correlation coefficients τTk of location sequence table U and Tk. τTk reflects real beacon node Yj’s proximity to the sequence Tk. Then we can normalize τTk by altering its range from -1,1 to 0,1. The normalized τTk is used as weights. Then we can estimate the coordinate of real beacon node Yj, respectively.Therefore, theMth estimation coordinate of real beacon node Yj is calculated by selecting M largest coefficients as follows:(8)Y^jMx^jM,y^jM,z^jM=1∑k=1M1+τTk/2∑k=1M1+τTk2Ck,where Ck is the coordinate of the kth location sequence Tk. M is any integer values in the range of [1,Nmax]. Nmax is the constant predefined by users, such as 10 or the numbers of virtual beacon nodes. So we have Nmax estimation coordinates of real beacon node Yj.Then we calculate the localization error of any estimation coordinates of real beacon nodeYj as follows:(9)EYjM=xj-x^jM2+yj-y^jM2+zj-z^jM2.According to the same steps, we calculate∑jEYjM of all real beacon nodes. Then N is the optimal parameters of all real beacon nodes in [1,Nmax], which makes the localization error ∑jEYjM minimum. Once N is calculated, other unknown nodes are estimated with the same N.(10)N=arg⁡minM∈1,Nmax⁡∑jEYjM.


### 3.5. Weighted Estimation

After determining the optimal parametersN, we produce optimal location sequence table, which has N largest Kendall coefficients between all virtual beacon nodes and the unknown node sequence.We use the normalized Kendall coefficients between the sequences in optimal location sequence table and the unknown node location sequence as the weights and estimate the coordinate of the unknown node.For example, given the localization sequenceW of unknown node Xx,y,z, SLC3V algorithm constructs an optimal location sequence table T=T1,T2,…,TN. Then we can calculate the coefficient τTi, which is the one of each sequence in location sequence W and Ti.Therefore, unknown nodeX’s coordinate is estimated as follows:(11)Xx^,y^,z^=1∑i=1N1+τTi/2∑i=1N1+τTi2Ci.


### 3.6. Periodic Update of Network Topology

By using the above procedures, all unknown nodes can be estimated. When the network topology changes, the algorithm will regularly update and delete the invalid beacon node. The localization calculation restarts from space division.


### 3.7. Complexity and Analysis

The main advantage of SLC3V algorithm is that better partition method reduces the complexity and introduction of valid virtual beacon nodes raises the location accuracy.The step of space division mainly decides Voronoi polyhedrons, which takesO(n2) time and space each. Then the steps of localization sequence construction require Onlog⁡n operations. Location sequence of unknown nodes costs some time and energy, but it only has the relation with the number of beacon nodes. For calculating Kendall’s coefficients between two sequences, there are O(N2) operations. And searching through it takes O(N2n2log⁡n) time and O(N2n3) space. Since the step of weighted estimation includes the normalization and estimation, it takes O(N2) time and O(N) space.Therefore the worst case time requirement in SLC3V isO(N2n4) and the worst case space requirement is O(N2n3).However, the 3D sequence-based localization in [17] takes O(n6) time and On5 space in the worst case. SLC3V algorithm has improved in the algorithm complexity. SLC3V and SL3V have almost the same time and space complexity.


## 3.1. Division of 3D Space

In the 3D space, we construct the cube boundary according to the location environment. The real beacon nodes are scattered in the 3D space randomly. The real beacon nodes are the real nodes deployed by users.Next we use the 3D Voronoi diagram to divide the 3D space. Then the Voronoi polyhedrons are produced. Each real beacon node is interior of the corresponding Voronoi polyhedron. In order to reduce the complexity of partition, we use the fast method in [13] to generate 3D Voronoi diagram.After partition, 3D space includes three kinds of regions, such as edges, faces, and bodies by a set of min-vertical planes.We present an example to illustrate the above ideas. As shown in Figure3, there are 3 real beacon nodes defined as A, B, and C, which are marked by the solid dotes.Figure 3
Real beacon nodes in 3D space.


## 3.2. Location Sequence Calculation

Firstly, we should determine all virtual beacon nodes based on the partition method. This paper marks all the regions and calculates the centroid of every region, which is defined as virtual beacon nodes. Then we sort all virtual beacon nodes. Because the location space is 3D, the kinds of regions change from vertices, edges, and faces into edges, faces, and bodies.For simplifying the calculation, we define the centroid of every region as follows. The centroid of any edge is its midpoint. The centroid of any face is calculated according to [15]. The centroid of any body is midpoint of the line between the two farthest points in the corresponding polyhedron.Then we can rank the location sequences of virtual beacon nodes according to distance between the virtual beacon nodes and real beacon nodes.In the 3D space, the positions of real beacon nodes are known, and all virtual beacon nodes are determined after partition. So we can calculate the distance between any virtual beacon nodes and all real beacon nodes. Then we can assign the location sequence table values based on distance, which is the indication of how near or far the virtual beacon node is from all real beacon nodes.In the example of Figure3, hollow dotes, such as E, F, and G, represent virtual beacon nodes. And each virtual beacon node has its own location sequence based on the distance rank, which is marked beside it in Figure 3. Node E is the centroid of edges, and its location sequence is 123, since the distance rank of A from it is 1 (A is the closest), and the respective distance rank of C is 3 (C is the farthest). Similarly, node G is the centroid of bodies, and its location sequence is 131. Node F is the centroid of faces, and its location sequence is 321.After this step, the location sequence table of all virtual beacon nodes can be calculated in any 3D space with real beacon nodes.


## 3.3. Location Sequence Correction of Unknown Nodes

In order to obtain the distance rank of unknown nodes, we assume that the real beacon nodes send data package to its neighbor nodes. And all unknown nodes are in the transmission area of real beacon nodes. So the unknown nodes measure the distance to real beacon nodes by using the Received Signal Strength Indicator (RSSI) method. According to the distance measured, any unknown node can determine its own location sequence. If location sequences of unknown nodes are more accurate, the localization estimate of unknown nodes has better accuracy. So we will use the distance and RSSI between real beacon nodes as a reference to correct the measured distance and fix location sequence of unknown nodes.R S S I i is the average RSSI (dbm) of the signal, which unknown node X receives from beacon node Bi. Pi is the average power (mW) of the signal which unknown node X receives from beacon node Bi. So the transformational relation between RSSIi and Pi is shown in(3)Pi=10RSSIi/10.R S S I i j is the average Received Signal Strength Indicator (RSSI) (dbm) of the signal, which real beacon node Bi receives from real beacon node Bj. Pij is the average power of the signal which real beacon node Bi receives from real beacon node Bj. Similarly, the transformational relation between RSSIij and Pij is shown in (4)Pij=10RSSIij/10.d B i j is the distance between real beacon node Bi and real beacon node Bj, which is deduced according to (1). dij is the distance between unknown node X and real beacon node Bi. Then, we can deduce the relation equation as follows:(5)dij=Pij1/η×dBijPi1/η.So,di represents the average value of dij, which is the distance between unknown nodes X and real beacon node Bi. R is the number of real beacon nodes.(6)di=∑j=1RdijR.From the above definition, location sequence of unknown node is deduced and corrected as follows:(1)
All real beacon nodes broadcast information in the same power periodically. Then unknown nodes will receive RSSI value of each real beacon node and calculate respective average valueRSSIi. Real beacon node Bi also can calculate the corresponding RSSIij of real beacon node Bj.(2)
All real beacon nodes broadcastPij and dBij, which are calculated by using (4). Then unknown nodes will receive information and calculate di. Finally, location sequence of unknown nodes can be decided according to the fixed di.Because of the RSSI correction, unknown nodes can correct their measured distance according to the environment. Thus the algorithm in this paper can fix location sequence of unknown node and ensure location sequence consistent with the actual situation.


## 3.4. Optimal ParameterN Selection

In this step, we calculate the order correlation coefficients between the vectors in sequence table of virtual beacon nodes and the unknown node sequence, respectively.Statistics offers two metrics to calculate the rank correlation coefficient between two location sequences. They are Spearman’s Coefficient and Kendall’s Tau, respectively. According to the analysis [15] and our simulation results, Kendall’s Tau can obtain better performance in localization algorithm. So we describe it simply. Kendall’s Tau is often used to calculate the correlation between the two sequences. Given two location sequences U=ui and V=vi, 1≤i≤n, where ui and vi represent the ranks of different beacon nodes, Kendall’s Tau compares all the n(n-1)/2 possible pairs of ranks ui,vi and uj,vj, respectively, to determine the numbers of matching pairs and nonmatching pairs. A pair is matching or concordant if ui>uj⇒vi>vj or ui<uj⇒vi<vj and nonmatching or discordant if ui>uj⇒vi<vj or ui<uj⇒vi>vj. The correlation between two sequences is calculated as follows:(7)τ=nc-ndnc+nd+ntunc+nd+ntv,where nc is the number of concordant pairs, nd is the number of discordant pairs, ntu is the number of ties in U, and ntv is the number of ties in V. The range of τ is [-1,1].At the same time, we should calculate the Kendall coefficients between the vectors in sequence table of virtual beacon nodes and the real beacon nodes sequence, respectively.Compared with other algorithm, this paper uses parameterN to determine the optimal number of virtual beacon nodes that are used in the weighted estimation. The suitable parameter N can decrease the localization error. We define all real beacon nodes as the sample set S and select the optimal parameter N according to localization estimation of real beacon nodes. We calculate the optimal parameter Nj value of jth real beacon node. Then the final optimal parameter N is the average of Nj.For example, given the location sequenceU of any real beacon node Yjx,y,z, Yj∈S, SLC3V obtains the location sequence table of virtual beacon nodes T=T1,T2,….According to (7), we can calculate the correlation coefficients τTk of location sequence table U and Tk. τTk reflects real beacon node Yj’s proximity to the sequence Tk. Then we can normalize τTk by altering its range from -1,1 to 0,1. The normalized τTk is used as weights. Then we can estimate the coordinate of real beacon node Yj, respectively.Therefore, theMth estimation coordinate of real beacon node Yj is calculated by selecting M largest coefficients as follows:(8)Y^jMx^jM,y^jM,z^jM=1∑k=1M1+τTk/2∑k=1M1+τTk2Ck,where Ck is the coordinate of the kth location sequence Tk. M is any integer values in the range of [1,Nmax]. Nmax is the constant predefined by users, such as 10 or the numbers of virtual beacon nodes. So we have Nmax estimation coordinates of real beacon node Yj.Then we calculate the localization error of any estimation coordinates of real beacon nodeYj as follows:(9)EYjM=xj-x^jM2+yj-y^jM2+zj-z^jM2.According to the same steps, we calculate∑jEYjM of all real beacon nodes. Then N is the optimal parameters of all real beacon nodes in [1,Nmax], which makes the localization error ∑jEYjM minimum. Once N is calculated, other unknown nodes are estimated with the same N.(10)N=arg⁡minM∈1,Nmax⁡∑jEYjM.


## 3.5. Weighted Estimation

After determining the optimal parametersN, we produce optimal location sequence table, which has N largest Kendall coefficients between all virtual beacon nodes and the unknown node sequence.We use the normalized Kendall coefficients between the sequences in optimal location sequence table and the unknown node location sequence as the weights and estimate the coordinate of the unknown node.For example, given the localization sequenceW of unknown node Xx,y,z, SLC3V algorithm constructs an optimal location sequence table T=T1,T2,…,TN. Then we can calculate the coefficient τTi, which is the one of each sequence in location sequence W and Ti.Therefore, unknown nodeX’s coordinate is estimated as follows:(11)Xx^,y^,z^=1∑i=1N1+τTi/2∑i=1N1+τTi2Ci.


## 3.6. Periodic Update of Network Topology

By using the above procedures, all unknown nodes can be estimated. When the network topology changes, the algorithm will regularly update and delete the invalid beacon node. The localization calculation restarts from space division.


## 3.7. Complexity and Analysis

The main advantage of SLC3V algorithm is that better partition method reduces the complexity and introduction of valid virtual beacon nodes raises the location accuracy.The step of space division mainly decides Voronoi polyhedrons, which takesO(n2) time and space each. Then the steps of localization sequence construction require Onlog⁡n operations. Location sequence of unknown nodes costs some time and energy, but it only has the relation with the number of beacon nodes. For calculating Kendall’s coefficients between two sequences, there are O(N2) operations. And searching through it takes O(N2n2log⁡n) time and O(N2n3) space. Since the step of weighted estimation includes the normalization and estimation, it takes O(N2) time and O(N) space.Therefore the worst case time requirement in SLC3V isO(N2n4) and the worst case space requirement is O(N2n3).However, the 3D sequence-based localization in [17] takes O(n6) time and On5 space in the worst case. SLC3V algorithm has improved in the algorithm complexity. SLC3V and SL3V have almost the same time and space complexity.


## 4. Simulation and Evaluation

### 4.1. Simulation Model

In wireless channels, there is the log-normal shadowing model that is most common simulation model. The log-normal shadowing model generates RSS samples as a function of distance.(12)PRd=PT-PLd0-10ηlg⁡dd0+Xσ,where PR is the power of received signal, which defines Received Signal Strength Indication (RSSI). PT is the power of transmitted signal, and PLd0 is the path loss for a reference distance of d0. η is the path loss exponent. And we define its random variation as a Gaussian random variable of zero mean and σ2 variance Xσ=N0,σ2. The unit of power is dBm, and the one of distances is meter.However, this model shows how signals attenuate ideally. In fact, there are many nonideal factors taken into account, such as various obstructions and electromagnetic interferences. If the situations mentioned above are to be considered, then (12) should be modified by introducing extra parameters in the right-hand side.


### 4.2. Simulation Environment

For simplicity, we simulate SLC3V algorithm and analyze its performance in Matlab. We assume that whether beacon nodes or unknown nodes are in the mutual radio range of other nodes, which means that all nodes can receive the message sent by other nodes. And node communication radius is 8 m. A 48-bit arithmetic linear congruential pseudorandom number generator was used, and results were averaged over 100 random trials. We chooseNmax is 10.P e represents the localization error in this paper and is defined as follows: (13)Pe=estimatelocation-reallocationWirelesscommunicationradius×100%In order to compare and evaluate SLC3V algorithm, this paper analyses the two performances, such as localization error and computation time. Then we compare our algorithm with other sequence-based localization algorithms. Firstly, we implement 3DSBO [17] and SL3V [18] in the same environment.


### 4.3. Simulation Results of SLC3V

Due to the better partition method, the space complexity of SLC3V algorithm is lower. Location sequence correction and optimal parameterN are introduced to make our average localization error the lowest in the above 3 algorithms. Whether increasing or decreasing the real beacon nodes, SLC3V algorithm has higher location accuracy, as shown in Table 1. Because SLC3V selects valid virtual beacon nodes in last estimation this algorithm raises average localization error to 12.0% when it only has 8 real beacon nodes, which show that it reduces the rising rate of localization error. Compared with SL3V, SLC3V fixes the location sequence with the RSSI correction and select optimal number N. So SLC3V has higher accuracy.Table 1
Average localization error in 3D.
Number of beacon nodes 3DSBO (%) SL3V (%) SLC3V (%) 8 18.9 18.3 12.0 16 9.6 9.4 8.9 24 4.9 4.8 4.3 32 2.5 2.4 1.9Average computation time in 3 algorithms above is in consistency with our time complexity analysis in Section3.7, as described in Table 2.Table 2
Average computation time in 4 algorithms.
Number of beacon nodes 3DSBO (%) SL3V (%) SLC3V (%) 8 0.52 0.46 0.40 16 1.33 1.01 1.00 24 2.59 2.10 2.12 32 3.80 2.80 2.81When the number of real beacon nodes raises to 32, SLC3V algorithm has obvious advantages in computation time, which comes about because of its partition method.In order to verify the effect of the optimalN, average localization errors are calculated in different N through extensive experiments. Figure 4 draws the curve of average localization errors with 32 real beacon nodes. The average localization error is lowest when optimal N is 7 calculated by SLC3V.Figure 4
Average localization error in differentN.Figure5 plots the average localization error due to 3DSBO, SL3V, and SLC3V as a function of the standard deviation in RSS log-normal distribution σ for different values of path loss exponents η, where the number of beacon nodes is 8. So we find that SLC3V is better than others under changing environment.Figure 5
Average localization error curves with standard deviationσ.
(a)
η = 2 (b)
η = 4In Figures5(a) and 5(b), path loss exponent η is, respectively, 2 and 4. Average localization error using SLC3V is always lower than that in 3DSBL in different standard deviation σ. And For higher values of σ, the localization error due to SLC3V decreases faster than localization error due to 3DSBO. The main results show that SLC3V performs better than 3DSBO in the antinoise and anti-interference properties.Based on the above experimental results of two performance parameters, SLC3V algorithm has better performances in the same conditions compared with other 3D sequence-based location algorithms.


## 4.1. Simulation Model

In wireless channels, there is the log-normal shadowing model that is most common simulation model. The log-normal shadowing model generates RSS samples as a function of distance.(12)PRd=PT-PLd0-10ηlg⁡dd0+Xσ,where PR is the power of received signal, which defines Received Signal Strength Indication (RSSI). PT is the power of transmitted signal, and PLd0 is the path loss for a reference distance of d0. η is the path loss exponent. And we define its random variation as a Gaussian random variable of zero mean and σ2 variance Xσ=N0,σ2. The unit of power is dBm, and the one of distances is meter.However, this model shows how signals attenuate ideally. In fact, there are many nonideal factors taken into account, such as various obstructions and electromagnetic interferences. If the situations mentioned above are to be considered, then (12) should be modified by introducing extra parameters in the right-hand side.


## 4.2. Simulation Environment

For simplicity, we simulate SLC3V algorithm and analyze its performance in Matlab. We assume that whether beacon nodes or unknown nodes are in the mutual radio range of other nodes, which means that all nodes can receive the message sent by other nodes. And node communication radius is 8 m. A 48-bit arithmetic linear congruential pseudorandom number generator was used, and results were averaged over 100 random trials. We chooseNmax is 10.P e represents the localization error in this paper and is defined as follows: (13)Pe=estimatelocation-reallocationWirelesscommunicationradius×100%In order to compare and evaluate SLC3V algorithm, this paper analyses the two performances, such as localization error and computation time. Then we compare our algorithm with other sequence-based localization algorithms. Firstly, we implement 3DSBO [17] and SL3V [18] in the same environment.


## 4.3. Simulation Results of SLC3V

Due to the better partition method, the space complexity of SLC3V algorithm is lower. Location sequence correction and optimal parameterN are introduced to make our average localization error the lowest in the above 3 algorithms. Whether increasing or decreasing the real beacon nodes, SLC3V algorithm has higher location accuracy, as shown in Table 1. Because SLC3V selects valid virtual beacon nodes in last estimation this algorithm raises average localization error to 12.0% when it only has 8 real beacon nodes, which show that it reduces the rising rate of localization error. Compared with SL3V, SLC3V fixes the location sequence with the RSSI correction and select optimal number N. So SLC3V has higher accuracy.Table 1
Average localization error in 3D.
Number of beacon nodes 3DSBO (%) SL3V (%) SLC3V (%) 8 18.9 18.3 12.0 16 9.6 9.4 8.9 24 4.9 4.8 4.3 32 2.5 2.4 1.9Average computation time in 3 algorithms above is in consistency with our time complexity analysis in Section3.7, as described in Table 2.Table 2
Average computation time in 4 algorithms.
Number of beacon nodes 3DSBO (%) SL3V (%) SLC3V (%) 8 0.52 0.46 0.40 16 1.33 1.01 1.00 24 2.59 2.10 2.12 32 3.80 2.80 2.81When the number of real beacon nodes raises to 32, SLC3V algorithm has obvious advantages in computation time, which comes about because of its partition method.In order to verify the effect of the optimalN, average localization errors are calculated in different N through extensive experiments. Figure 4 draws the curve of average localization errors with 32 real beacon nodes. The average localization error is lowest when optimal N is 7 calculated by SLC3V.Figure 4
Average localization error in differentN.Figure5 plots the average localization error due to 3DSBO, SL3V, and SLC3V as a function of the standard deviation in RSS log-normal distribution σ for different values of path loss exponents η, where the number of beacon nodes is 8. So we find that SLC3V is better than others under changing environment.Figure 5
Average localization error curves with standard deviationσ.
(a)
η = 2 (b)
η = 4In Figures5(a) and 5(b), path loss exponent η is, respectively, 2 and 4. Average localization error using SLC3V is always lower than that in 3DSBL in different standard deviation σ. And For higher values of σ, the localization error due to SLC3V decreases faster than localization error due to 3DSBO. The main results show that SLC3V performs better than 3DSBO in the antinoise and anti-interference properties.Based on the above experimental results of two performance parameters, SLC3V algorithm has better performances in the same conditions compared with other 3D sequence-based location algorithms.


## 5. Conclusion and Future Work

Localization in wireless sensor networks is still a critical research issue for researchers recently. Most researchers concentrate on the study in 2D space. With the wide application and proliferation of WSNs, the problem of localizing nodes in 3D space has received much attention.Based on SL3V, this paper proposes an efficient algorithm localization algorithm called Sequence Localization Correction algorithm based on 3D Voronoi diagram (SLC3V), which combines 3D Voronoi diagram with the sequence localization in WSN.SLC3V algorithm extends 2D sequence-based location into 3D space. SLC3V not only can realize unknown node self-localization, but also overcomes the original sequence-based localization algorithm. The shortcomings of this original sequence-based localization algorithms are the higher partition complexity, the higher location error in complicated disturbing environment, and the lower constant number of valid virtual beacon nodes. SLC3V algorithm adapts 3D Voronoi diagram to divide the space. So it effectively reduces the number and the complexity of generating the virtual beacon nodes. Considering the variability of the environment and the impact of outside interference, we introduce the RSSI correction method to adapt the location sequence of the unknown node rapidly. The selection of optimal parameterN increases valid virtual beacon nodes in location estimation compared with other algorithms, which improve the location accuracy.In order to verify the effectiveness of SLC3V, we deploy real beacon nodes randomly in the 3D cube during simulation. Experimental results prove that the proposed algorithm has good performance in either more beacon nodes or fewer beacon nodes. It can be adaptive according to the number of beacon nodes and changes in environment and network.In the future, we will build test-bed and deploy real nodes on it. The algorithm performance is tested on test-bed in laboratory. Then we will optimize the algorithm further and apply it in practical applications, such as the surveillance and control on food storage.



---

*Source: 4769710-2017-01-22.xml*