A node localization algorithm based on Voronoi diagram and support vector machine for wireless sensor networks

Abstract

For wireless sensor network, the localization algorithm based on Voronoi diagram has been applied. However, the location accuracy node position in wireless sensor network needs to be optimized by the analysis of the literature, a node location algorithm based on Voronoi diagram and support vector machine is proposed in this article. The basic idea of the algorithm is to first divide the region into several parts using Voronoi diagram and anchor node in the localization region. The range of the initial position of the target node is obtained by locating the target node in each region and then the support vector machine is used to optimize the position of the target node accurately. The localization performance of the localization algorithm is analyzed by simulation and real-world experiments. The experimental results show that the localization algorithm proposed in this article is better than the optimal region selection strategy based on Voronoi diagram-based localization scheme and Weighted Voronoi diagram-based localization scheme localization algorithms in terms of localization accuracy. Therefore, the performance of the localization algorithm proposed in this article is verified.

Keywords

Wireless sensor network Voronoi diagram support vector machine localization accuracy Voronoi diagram and support vector machine

Introduction

Wireless sensor networks (WSNs) have many advantages because of their own characteristics, and they are used in many fields at present. Its localization technology has become the focus of current research and has shown its importance in many fields.^1,2 In the field of medical and health care,^3–5 it is impossible to obtain the location of a patient’s disease without localization technology; in the field of construction,⁶ it is difficult to obtain the fault location of a building without localization technology; in the field of forest protection, if the location of sensor nodes cannot be obtained accurately, it is difficult to determine the accurate disaster location and achieve efficient disaster treatment. At present, Global Localization System (GPS) is the most common localization method, which can accurately locate its own position,^7–9 but sensor nodes are limited by factors such as cost and power consumption; it is impossible to install GPS on each node, so it is not used in the general localization scheme. Node localization based on WSN has become a research hotspot in recent years, and a great number of algorithms based on it have been studied and applied.

The research of location algorithm can be divided into two categories: location algorithm based on ranging and location algorithm based on non-ranging. A direct location method based on time of arrival (TOA) localization algorithm is proposed in Khalaf-Allah.¹⁰ A localization method based on Angle of Arrival (AOA) algorithm is proposed in Yang et al.,¹¹ which uses wavelet transform to assist localization. A localization algorithm for WSNs based on Received Signal Strength Indication (RSSI) is proposed in Chen et al.¹² and then the weighted centroid algorithm is used to improve the localization accuracy. In Khalaf-Allah,¹⁰ Yang et al.,¹¹ and Chen et al.,¹² the application of several location algorithms based on ranging is introduced. A localization method for WSNs based on Approximate Point-in-triangulation Test (APIT) algorithm is proposed in Liu et al.,¹³ which reduces the energy consumption by reducing the number of real anchor nodes. A localization algorithm based on Multidimensional Scaling (MDS) for WSN is proposed in Stojkoska and Vesna¹⁴ and then the localization performance is improved by distance correction. The node location algorithm based on distance vector (DV)-Hop algorithm has also been studied by many researchers. In Cai et al.,¹⁵ a mathematical weighted DV-Hop location model is proposed and genetic algorithm is used to solve the model. A new method called N2-3DDV-Hop (non-dominated sorting genetic algorithm II with three-dimensional (3D) distance-vector hop) is proposed in Cai et al.,¹⁶ which builds on the 3D-DV-Hop algorithm by adding multi-objective model and non-dominated sorting genetic algorithm II (NSGA-II). In Wang et al.,¹⁷ a Gaussian error correction multi-objective positioning model with non-dominated sorting (NSGA-II) is proposed, which is named Gaussian error correction multi-objective positioning model with NSGA-II (GGA-II)-DVHop. In Liu et al.,¹³ Stojkosa and Vesna,¹⁴ Cai et al.,^15,16 and Wang et al.,¹⁷ the application of localization methods based on non-ranging is introduced. The algorithms introduced above are basically applied to the location of static nodes. At present, the location algorithm based on mobile nodes has also been studied and applied by many scholars.

According to the investigation and analysis, the localization algorithm based on Voronoi diagram is already improved, but the localization accuracy needs to be improved. Therefore, this article proposes an improved algorithm based on Voronoi diagram and Voronoi diagram and support vector machine (VD-SVM). The major contributions of this work can be summarized as follows:

Determines the range of location of a certain target node by dividing the location area by Voronoi partition.

Uses the support vector machine (SVM) for each sub-area of the division.

Validates the performance of the proposed node location method in both indoor and outdoor environments.

The remainder of this article is structured as follows. Section “Related works” reviews some related works on node localization systems based on VD-SVM. Section “Node localization algorithm” introduces the proposed model and describes how to determine the location of node. The experimental design and results are discussed in section “Localization algorithm simulation and experimental.” Finally, the conclusion drawn from the current work and brief discussion of future work are presented in section “Conclusion.”

Related works

Since the official support of the SVM, it has become a mainstream technology for machine learning because of its excellent performance in text classification tasks. In recent years, SVM has been widely used in localization. A data fusion localization algorithm based on SVM in WSN is proposed in Wang et al.;¹⁸ based on the TOA/time difference of arrival (TDOA) localization technology, this article proposes a SVM data fusion model and optimizes the parameters based on the search algorithm to improve the localization algorithm based on least squares SVM. The probabilistic SVM localization of WSN is proposed in Samadian,¹⁹ the localization method is optimized using the SVM, and then the localization accuracy is optimized by the ARPoFiL (Attracted/Repulsive Potential Filed Localization) method. Mao et al.²⁰ proposed a SVM “one-to-one” node localization algorithm based on ranging, which uses the basic 2% classification principle of SVM to extend the classification of multiple categories and then locate the nodes. SVM is also widely used in Wi-Fi indoor localization. Yu et al.²¹ studied the indoor localization based on SVM and locate the fingerprint library. The localization of beacon-based SVM in WSN is proposed in Livinsa and Jayashri,²² mainly by awakening the learning concept of SVM and improving the localization accuracy. A fast SVM-based localization algorithm proposed in large-scale WSN is proposed in Zhu and Wei;²³ the algorithm constructs a minimum span by introducing a similarity measure and divides the support vectors into groups according to the maximum similarity in the feature space. To solve the problem that the localization performance is reduced due to the distance measurement error in the non-ranging localization algorithm, a SVM-based range-free localization (RFSVM) algorithm is proposed in Tang et al.²⁴ A parameter optimization algorithm based on Krill-herd algorithm (KH-SVM) is proposed in Zhu and Wei,²⁵ because the classification of SVM determines the localization accuracy; the choice of parameters is the decisive factor.

Voronoi diagram (Tyson polygon or Dirichlet diagram) is composed of a set of continuous polygons composed of vertical bisection lines connecting two adjacent point lines. As a general basic geometric data structure, it is widely used in node coverage and network location. A node localization algorithm based on Voronoi diagram without distance measurement in WSN is proposed in Jichun et al.²⁶ The algorithm sorts the received signal strength of the received anchor nodes and uses the Unit Disk Graph (UDG) map to calculate the Voronoi region of each anchor node; the centroid of the intersection of the regions is the position of the node. To verify the localization skills of mobile robots, a generalized Voronoi diagram is proposed in Song and Liu²⁷ and then the hidden Markov model is used for reasoning. Lasla et al.²⁸ proposed a new localization algorithm based on Half Symmetric Lens (HSL) using the geometry of half symmetric lens in WSN. In this algorithm, the Voronoi diagram is used to alleviate the problem of non-localizable sensor nodes. A sequence localization correction algorithm based on 3D Voronoi diagram is proposed in Yang and Liu.²⁹ The Voronoi diagram is used to divide the spatial region to construct the order list of the virtual anchor node, and the RSSI method between the beacon nodes is used as the reference to correct the measured distance and the position sequence of the unknown node. Lu et al.³⁰ proposed a new localization algorithm called Basic Complete Voronoi Diagram localization scheme (BCVD). The full text mainly introduces the principle problem behind the complete Voronoi diagram. In Di and Qiang,³¹ the application of the introduced Voronoi diagram in the localization of underwater sensor nodes is introduced. The above literature mainly introduces the application of Voronoi diagram in various aspects and the improvement of Voronoi diagram algorithm to improve the localization accuracy.

Whether in the indoor environment or in the outdoor environment, the location through the Voronoi map is a coarse-grained location, so there is a big error in the positioning results. At present, many scholars have improved the Voronoi diagram or combined with some other algorithms to improve the positioning accuracy, but there are still some problems. To locate in a more fine-grained environment, this article uses the combination of Voronoi diagram and SVM to locate, which can further improve the positioning accuracy under the condition of relatively low energy consumption and complexity. Finally, compared with the localization algorithm proposed by Zixiao et al.³² and Cai et al.,³³ the performance of the proposed VD-SVM algorithm is more excellent.

Node localization algorithm

Network initialization

The purpose of network initialization is to ensure the stability of node information in the network. When the information of nodes in the network remains stable, the node can guarantee the accuracy of its information when broadcasting and receiving information. The steps for network initialization are as follows:

Step 1. All nodes in the network estimate their own location information and measure the distance $d_{i}$ between the node $i$ and its neighbor nodes through the RSSI distance information.

Step 2. All anchor nodes $N_{i}$ know their own location, so anchor nodes broadcast their own information $A_{i}$ (including location information, node ID, RSSI, etc.) to neighbor nodes, unknown nodes according to anchor node broadcast information to determine their own location. The information $A_{i}$ contained in the anchor node can be represented as: $A_{i} = {Lo c_{i}, I D_{i}, RSSI, d_{i}}$ .

Step 3. Node $P$ (neighbor node of node $P$ is node $i$ ) directly receives anchor node information $A_{i}$ and then updates the information $A_{i}$ and stores it and node $P$ forwards the new information $A_{i}$ .

Step 4. When the node $P$ indirectly receives the anchor node information $A_{i}$ , that is, the information forwarded by the neighbor node, first of all, it is necessary to confirm whether the node $P$ will have received information from a node $q$ ( node $q$ is not a neighbor node of node $i$ ) prior to receiving the information from a node $q$ . If the information sent by node $q$ is not previously received, the information update information $A_{i}$ is accepted and stored; if the previous node $P$ has received the message, which is sent by node $q$ , it is also necessary to determine whether the sum of the distance from node $i$ to node $P$ and the distance from node $P$ to node $q$ is less than the previously stored distance $d_{i}$ , if less than, the information $A_{i}$ is updated and stored, and node $P$ forwards the new information $A_{i}$ ; or discards the information.

Step 5. Step 3 and Step 4 are performed iteratively, indicating that the network has been initialized when the information of all nodes in the network remains unchanged.

The flow chart of network initialization is shown in Figure 1.

Figure 1.

Network initialization flow chart.

Constructing a Voronoi diagram model

The location algorithm proposed in this article is through the division of the location region, through each part of the target node location, which is a distributed node location method. First of all, by constructing Voronoi diagram, the localization region is divided, so that the localization changes scattered part by part to locate the nodes, so as to achieve better coverage of the localization nodes.

To understand the application of Voronoi diagram in node location, the method and properties of constructing Voronoi diagram are analyzed. Through analysis and research, it is found that the fastest way to construct Voronoi diagram is Delaunay triangulation. When generating a Voronoi diagram, there are first several points in the region. These points generate their dual Delaunay triangulation and then each triangulation can find the corresponding circumcircle, by finding the center of these circumscribed circles and connecting the adjacent centers. Finally, a polygon mesh is formed with each triangle vertex as a generator, that is, a Voronoi diagram of several points in the region is obtained, and the specific implementation result is shown in Figure 2.

Figure 2.

The principle of Voronoi diagram generation.

Assuming that 50 sensor nodes are randomly deployed in a certain area, these sensor nodes are determined to be anchor nodes. The Voronoi diagram formed using the Delaunay triangle method is shown in Figure 3. It can be seen from the Figure 3 that the determined area is divided into several parts.

Figure 3.

Division of regions by Voronoi diagram.

Determine the location of node

Suppose there are N wireless sensor nodes $A_{i} = {A_{1}, A_{2}, A_{3}, \dots, A_{N}}$ randomly distributed in the location area, where there are $m$ $(m < N)$ anchor nodes $A_{i} = {A_{1}, A_{2}, A_{3}, \dots, A_{m}}$ whose coordinate position information is known, and the remaining node $A_{i} = {A_{m}, A_{m} + 1, A_{m} + 2, \dots, A_{n}}$ position information is unknown, which needs to be calculated by the localization algorithm. Assume that the communication distance of the node is recorded as R, that is, the node can only communicate with the anchor node within its communication range.

Determine the area where the target node is located

In the communication process of the node, the information is transmitted by the RSSI signal. The analog signal generally adopts the shadowing model when transmitting

10 \lg \frac{RSSI}{RSS I_{0}} = - 10 β \lg (\frac{d}{d_{0}}) + X_{dB}

(1)

where $X_{dB}$ represents a puzzling distribution variable with an average of 0, $β$ represents the path loss factor, and $d_{0}$ represents the reference distance.

In equation (1), since $X_{dB}$ is a Gaussian random noise, it is generally ignored that there is not much influence on the result, so it can be roughly estimated, then it can be concluded that

\frac{d}{d_{0}} \approx {(\frac{RSSI}{RSS I_{0}})}^{- (1 / β)}

(2)

Assuming that the node is to determine its position, it is assumed that it can obtain the RSSI value of the surrounding $K (1 \leq K \leq M)$ anchor nodes, and then according to the communication distance of the receiving signal strength nodes, suppose

RSS I_{i 1} \geq RSS I_{i 2} \geq RSS I_{i 3} \geq \dots RSS I_{ik}

(3)

According to the model in formula (1), it can be concluded

\frac{d_{i 1}}{d_{i 2}} \approx {(\frac{RSS I_{i 1}}{RSS I_{i 2}})}^{- (1 / β)} < \frac{RSS I_{i 1}}{RSS I_{i 2}}, \frac{d_{i 1}}{RSS I_{i 1}} < \frac{d_{i 2}}{RSS I_{i 2}}

(4)

Available from formula (4)

0 < \frac{d_{i 1}}{RSS I_{i 1}} < \frac{d_{i 2}}{RSS I_{i 2}} < \frac{d_{i 3}}{RSS I_{i 3}} < \dots < \frac{d_{ik}}{RSS I_{ik}}

(5)

It can be seen from the analysis that we can solve the inequality (5) using the weighted Voronoi diagram, first using the weighted Voronoi diagram of the K nodes around the node to be located to receive the signal. The formula for the weighted Voronoi diagram can be expressed as

W (P_{i}, λ_{i}) = {\begin{matrix} x ε W (P_{i}, λ_{i}) | \frac{d (x, P_{i})}{λ_{i}} \leq \frac{d (x, P_{j})}{λ_{j}} \\ j = 1, 2, \dots, n, j \neq i \end{matrix}

(6)

where $λ_{i}$ represents the weight of the Voronoi diagram in the spatial set.

According to formulas (5) and (6), it can be known that the node $i$ is located in the weighted Voronoi region of $K_{1}$ . Then, the determined region is removed, and the weighted Voronoi region where the node is located is obtained in turn, and the solution set of inequality (5) can be obtained, and the centroid of the solution set us to locate the estimated region position of the node $i$ .

Node precise localization

SVM is a machine learning pattern recognition method, which has obvious advantages in solving small sample, nonlinear and other problems. In this article, SVM is used to locate nodes. The localization of SVM can be divided into three stages: training stage, broadcast stage, and localization stage. Because of the partition calculation of Voronoi graph, we have preliminarily divided the region and roughly determined the region where the target node is located. Then, the SVM algorithm is used for location.

Training phase. If a node has determined that the area is area 2 in Figure 4, each node in that area sends a packet to the anchor node in the communication range and is represented as unreachable to the node not in the communication range. Therefore, each node can obtain its distance information to the anchor node through the signal strength index, and the distance information of the node is stored in the node. Each anchor node sends a packet $A_{i} = {Lo c_{i}, I D_{i}, RSSI, d_{i}}$ to the sink node, including the location information of the node, the ID, RSSI value of the node, and the distance vector stored in the node. The SVM training algorithm is executed in the sink node, and the SVM parameter information corresponding to all the classifications is calculated.

Broadcast phase. The sink node broadcasts the SVM parameter information calculated during the training phase to all nodes in the region. The sensor node processes the information broadcasted by the aggregation node, and the algorithm trains all the nodes, and finally locates the target node.

Localization phase. After the unknown node receives the SVM parameter information, the SVM classification is carried out in the node according to its own distance vector, the category in the region is estimated, and the centroid coordinates of the small lattice in the region are taken as the position coordinates of the target node.

Figure 4.

Distribution of sensor nodes for Voronoi diagram.

Localization algorithm simulation and experiment

Simulation study

To verify the location method proposed in this article, we compare the performance with the two location algorithms in Zixiao et al.³² and Cai et al.³³ In the performance verification, MATLAB 2015b is used for experimental simulation and the network size is set to 150 m × 150 m × 150 m. This section mainly carries on the performance verification analysis from three aspects, namely, the communication radius, the number of anchor nodes, and the total number of nodes. To ensure the accuracy of the experimental results, 100 groups of experiments were carried out to calculate the average value of the experimental results. In experimental verification, the proposed positioning algorithm is compared with two positioning algorithms ORSS-VBLS³² and W-VBLS³³ to verify the performance of the proposed algorithm.

Effect of communication radius

The size of the communication radius affects the unknown determination of the target node, because when the communication radius is too large or too small, there are too few or too many anchor nodes around the target node, which will affect the determination of the location of the target node and lead to the increase of localization error. The experimental results are shown in Figure 5; it shows that the location error of the proposed location algorithm VD-SVM is lower than that of the other two location algorithms, and the positioning performance of W-VBLS algorithm is similar to that of VD-SVM algorithm. It can also be seen from the figure that average positioning error of VD-SVM algorithm is stable after the communication radius is 30 m, which shows that the localization performance can be better when the communication radius is controlled between 30 and 45 m. When the communication radius is between 15 and 33 m, the average positioning error of the ORSS-VBLS positioning algorithm is much higher than the other two algorithms. When the communication radius is 15 m, the average positioning error is the maximum value of 0.25. When the communication radius is 20 m, there is an intersection between the average positioning error values of the W-VBLS algorithm and the VD-SVM algorithm, and the value is about 0.09.

Figure 5.

Influence of communication radius on localization accuracy.

Effect of anchor density

The number of anchor nodes is particularly important when locating the target node. If there is no anchor node in the communication range, the target node cannot be located. When the number of fixed nodes is 500, the influence of the number of anchor nodes on the localization error is verified by experiments. The result is shown in Figure 6. It can be seen from the figure that as the number of anchor nodes increases, the positioning error of the VD-SVM positioning method proposed in this paper gradually decreases. Moreover, the localization accuracy of the VD-SVM localization algorithm is better than the other two localization algorithms. When the number of anchor nodes is more than 15, the localization accuracy of the localization algorithm ORSS-VBLS is basically similar to that of the localization algorithm VD-SVM, and the localization error of the localization algorithm W-VBLS is greater than the other two algorithms. When the number of anchor nodes is 5, the average positioning error of W-VBLS algorithm and VD-SVM algorithm is almost equal, and the value is about 0.15. When the number of anchor nodes is between 5 and 12, the average positioning error of the ORSS-VBLS algorithm is higher than that of the W-VBLS algorithm, but when the number of anchor nodes is between 12 and 30, the average positioning error of the W-VBLS algorithm is higher than that of the ORSS-VBLS algorithm.

Figure 6.

The influence of the number of anchor nodes on the localization accuracy.

Effect of sensor density

In this article, in the fixed WSN area, the density of randomly deployed sensor nodes has an impact on the localization accuracy. In the case of sparse deployment of sensor nodes, there are fewer nodes that can communicate in the communication range, which affects the accuracy of location. The density of the nodes will affect the communication between the nodes to a certain extent, resulting in the reduction of the localization accuracy of the nodes. Through the experimental analysis, as shown in Figure 7, the location errors of the three location algorithms decrease with the increase in the number of nodes, and it can be concluded that the location error of the VD-SVM location algorithm is compared with that of ORSS-VBLS and W-VBLS, the localization error of VD-SVM is small as a whole. In the area we determine, the location error area is stable when the node is deployed about 300, indicating that the number of nodes is better in the determined range when the number of nodes is about 300.

Figure 7.

Influence of total number of nodes on location accuracy.

Experimental evaluation

Experimental equipment

The equipment required during the experimental verification phase includes sensor node, sink node, and laptop. The sensor nodes used in the experiment as shown in Figure 8(a) are based on STM32W108 ZigBee nodes manufactured using ARM-Cotex-M3 technology, in line with ZigBee/IEEE802.15.4 standards, and can meet the requirements of users for low-cost, low-power WSNs. Its main function is to broadcast information to the sink node. The required sink nodes are shown in Figure 8(b), with STM32W108 as the control core, wireless transmission rates up to 250 kbps/s, and support for random selection of channels from 11 to 26. It provides a serial port connected to the PC terminal, and its main function is to send the information received from the sensor nodes to the PC terminal for data collection and processing.

Figure 8.

Experimental equipment: (a) sensor node and (b) link node.

Experimental scene

Experiments are also conducted over a real WSN tested. To verify the performance of the proposed localization method in real environment, choose indoor meeting rooms and outdoor two scenes. The previous section compares the localization algorithm VD-SVM proposed in this article with the other two localization algorithms through simulation experiments, but the simulation experiments verify that the environment is ideal. In order to further verify the performance of the localization algorithm proposed in this article, the validated node deployment in a real environment is shown in Figures 9 and 10. As shown in Figure 9, an outdoor 20 m × 20 m open area is selected as an experimental scene, and 20 nodes are randomly deployed in the area (including 3 aggregation nodes and 17 sensor nodes). There are also three computers in the area to connect with the aggregation node, receive the data information sent by the node, and process the information. In order to get a clearer understanding of the environment deployment, Figure 9(b) is a logical diagram of the outdoor environment deployment. As shown in Figure 10, an indoor experimental environment of 5 m × 5 m is selected. Because the location area of the indoor environment is limited, only eight nodes are randomly deployed in the environment (including one sink node and seven sensor nodes) and there is a laptop connected to the sink node. Figure 10(b) is a logical diagram of the deployment of the indoor environment. The nodes involved in the experiment are two kinds of sensor nodes and sink nodes, and the sensor nodes are divided into anchor nodes and target nodes. The anchor node broadcasts its own position information in a certain time interval in the deployment area, and the sink node which receives the broadcast information transmits the data to the PC terminal.

Figure 9.

Node deployment in outdoor environment: (a) Real graph of node distribution in outdoor environment and (b) Logical diagram of node distribution in outdoor environment.

Figure 10.

Node deployment in indoor environment: (a) Real graph of node distribution in indoor environment and (b) Logical diagram of node distribution in indoor environment.

The VD-SVM algorithm needs to first locate the target area using the Voronoi diagram to locate the target node and then use the SVM algorithm to accurately locate it. To verify the localization performance of the proposed localization algorithm, the algorithm is verified in the experimental scenario. The experiment is mainly carried out in two parts. One is the performance analysis of the VD-SVM localization algorithm under the parameter change; the other is the experimental verification of the VD-SVM localization algorithm compared with ORSS-VBLS and W-VBLS localization algorithms.

Performance analysis of VD-SVM

In order to verify the performance of the localization algorithm proposed in this article, we analyze the performance of the algorithm by changing the parameters. In the location algorithm proposed in this article, we determine the communication radius and node power through experiments to ensure its location performance. Different communication radii are used in different indoor and outdoor location areas. In the process of positioning, the deployment of sensor nodes is usually dense. If each node has communicated with high power, it will aggravate the interference between nodes, reduce the communication efficiency, and cause a waste of node energy. However, if the transmission power is too small, it will affect the connectivity of the network and reduce the positioning performance. Therefore, in the positioning process, we use a certain algorithm to control the transmission power of the node, that is, to determine the better transmission power. The setting of the communication radius is adjusted according to the size of the located area. Because if the communication radius of the node is too small, the network may be disconnected; the communication radius is too large, although it will ensure its connectivity, but the network structure shows a very strong mesh network characteristic. Therefore, the effect of anchor node ratio and communication radius on localization accuracy and the influence of anchor node ratio and communication radius on energy consumption are analyzed by two experiments.

Influence of communication radius and anchor node ratio on VD-SVM

The experimental verification results of the influence of the change of anchor node ratio and communication radius on the localization accuracy are shown in Figure 11; it can be seen from the figure that the localization error of the node decreases with the increase in the anchor node ratio. The determination of communication radius also has a certain impact on the localization accuracy. The figure shows that when the communication radius is in the range of 5–30, the localization error is smaller when R is 15, as the proportion of anchor nodes increases, the average positioning error region becomes stable. When the anchor node ratio is 0.2, the average positioning error is the maximum value of about 0.21; when the anchor node ratio is 0.6, the average positioning error is the minimum value of about 0.1. From the experimental results, it can be concluded that the determination of the appropriate value of the communication radius has an obvious impact on the localization accuracy, so, to ensure the higher node localization accuracy, we determine the communication radius of 15 in this environment.

Figure 11.

Comparison of average positioning error when communication radius is different.

Energy consumption analysis of VD-SVM algorithm

This part is mainly through the analysis of energy consumption, and the experimental result is shown in Figure 12. It can be seen from the figure that the localization energy consumption decreases gradually with the increase in the proportion of anchor nodes, and the energy consumption is better when the communication radius is determined to be 20, when the anchor node ratio is 0.2, the energy consumption is the maximum value, which is about 25; when the anchor node ratio is 0.6, the energy consumption is the minimum value, which is about 10. When the communication radius is 15 m, the size of energy consumption changes erratically, when the anchor node ratio is between 0.3 and 0.4, the energy consumption decreases steadily; when the anchor node ratio is between 0.4 and 0.45, the energy consumption decreases relatively. It can be seen from the conclusion that in the experimental environment, when the number of anchor nodes is relatively large, the energy consumption is small, and the larger or smaller communication radius will cause the localization energy consumption of the nodes to increase. Therefore, it is more important to determine the appropriate value of the communication radius and the number of anchor nodes.

Figure 12.

Comparison of energy consumption when communication radius is different.

Performance comparison and analysis of VD-SVM with ORSS-VBLS and W-VBLS

Energy consumption analysis

The results of the energy consumption problem of the localization algorithm under the real environment verification are shown in Figure 13. As shown in the figure, in outdoor and indoor environments, the overall energy consumption increases as the communication radius increases. And the energy consumption of the VD-SVM positioning method proposed in this article is lower than the ROSS-VBLS and W-VBLS algorithms. In Figure 13(a), when the communication radius is 5 m, the energy consumption of VD-SVM is about 16; when the communication radius is 16 m, the energy consumption of VD-SVM is about 12; when the communication radius is 30 m, the energy consumption of VD-SVM is about 21. The energy consumption of the ORSS-VBLS algorithm fluctuates; when the communication radius is between 10 and 16 m, the energy consumption gradually decreases; when the communication radius is greater than 16 m, the energy consumption gradually increases; and its minimum energy consumption is about 16. The energy consumption of W-VBLS algorithm increases steadily; when the communication radius is about 18 m, the energy consumption is the lowest, and its value is about 18. In Figure 13(b), when the communication radius is between 6 and 10 m, the energy consumption value of the VD-SVM method and the W-VBLS algorithm is relatively close; when the communication radius is 4 m, the energy consumption is the lowest, and its energy consumption value is about 11. The energy consumption of the ORSS-VBLS algorithm is the highest; when the communication radius is 10 m, the energy consumption is about 30.

Figure 13.

Comparison of the influence of communication radius on energy consumption in (a) outdoor and (b) indoor environments.

Effect of communication radius

The results of the verification of the communication radius to the localization accuracy in the real environment are shown in Figure 14. It can be seen from the results of the two groups of experiments that the localization accuracy is gradually reduced with the increase in the communication radius, and the localization algorithm VD-SVM proposed in this article and the other two. The comparison results show that the localization accuracy of VD-SVM method is better than the ORSS-VBLS and W-VBLS, indicating that the localization algorithm is suitable under the proposed localization environment and conditions. In Figure 14(a), the average positioning error of the ROSS-VBLS algorithm is relatively large, and when the communication radius is between 5 and 10 m, the average positioning error decreases sharply. The maximum value of the average positioning error of the W-VBLS algorithm is 0.2, and the minimum value is about 0.5. And when the communication radius is larger than 10 m, the change of the average positioning error is small. The difference between the average positioning error of the VD-SVM positioning method and the W-VBLS algorithm is small. When the communication radius is 5 m, the average positioning error of the VD-SVM method is about 0.15, and the average positioning error of the W-VBLS algorithm is about 0.2. When the communication radius is 10 m, the average positioning error of the VD-SVM positioning method is about 0.09, and the average positioning error of the W-VBLS algorithm is about 0.1. When the communication radius is larger than 22 m, the average positioning errors of the three positioning algorithms are similar.

Figure 14.

Comparison of the influence of communication radius on positioning accuracy in (a) outdoor and (b) indoor environments.

Effect of noise

The noise existing in the environment is unavoidable and will have certain influence on the localization accuracy. Therefore, in order to verify its influence on the localization accuracy, the experimental results are verified in the real environment. The results are shown in Figure 15. The localization algorithm VD-SVM has better localization accuracy under the influence of noise than the other two localization algorithms ORSS-VBLS and W-VBLS. The results of the two sets of experiments show that the localization error increases with the increase in noise, and the noise has great influence on the ORSS-VBLS and W-VBLS algorithms in the two experimental scenarios. The localization errors of the two algorithms vary greatly, but VD-SVM algorithm has a small range of localization error, which indicates that the VD-SVM is more robust both indoors and outdoors. In Figure 15(a), the average location error range of the VD-SVM location algorithm is about 0.02–0.08. When the degree of noise is between 0.1 and 0.25, the difference of the average location error between VD-SVM and W-VBLS is small and then becomes larger. The average positioning error of ORSS-VBLS algorithm is the largest. When the degree of noise is 0.1, the average positioning error is about 0.1 and when the degree of noise is 0.5, the average positioning error is about 0.15. In Figure 15(b), the average location error of VD-SVM algorithm is between 0.05 and 0.1. When the noise level is 0.1, the average location errors of ORSS-VBLS, W-VBLS, and VD-SVM algorithms are about 0.15, 0.08, and 0.05, respectively, and when the noise level is 0.5, the average location errors of ORSS-VBLS, W-VBLS, and VD-SVM are 0.2, 0.18, and 0.1, respectively.

Figure 15.

Comparison of the influence of noise on positioning accuracy in (a) outdoor and (b) indoor environments.

Effect of number of anchor nodes

To further verify the positioning performance of the positioning method proposed in this article in the complex environment, by verifying the influence of the number of anchor nodes on the positioning accuracy in the positioning area, the experimental results are shown in Figure 16. It can be seen from the figure that whether in indoor or outdoor environment, the positioning accuracy of the proposed positioning method VD-SVM is better. In Figure 16(a), with the increase in the number of anchor nodes, the positioning accuracy of the three positioning methods increases gradually. When the number of anchor nodes is between 3 and 11, the positioning accuracy of VD-SVM algorithm increases steadily, and the positioning accuracy of the other two algorithms increases relatively, and the two algorithms have an intersection point when the number of anchor nodes is 4 and 6. When the number of anchor nodes is 3, the positioning accuracy of the three algorithms is relatively close, of which the positioning accuracy of VD-SVM algorithm is about 0.45 and that of the other two algorithms is about 0.4. When the number of anchor nodes is 7 and 9, the positioning accuracy of VD-SVM algorithm is about 0.78 and 0.9. When the number of anchor nodes is 11, the positioning accuracy of VD-SVM algorithm is about 0.98, so almost all nodes can determine their positions. Due to the limited positioning area in the indoor environment, a small number of destination sensor nodes are deployed, so the number of anchor nodes is set between 1 and 5 in this experiment. In Figure 16(b), the positioning accuracy of the three positioning algorithms increases gradually, compared with the outdoor environment, the positioning accuracy of the three algorithms is relatively stable in the indoor environment. When the number of nodes is more than 3, the positioning accuracy of the three algorithms is gradually close to each other. When the number of nodes is 4, the positioning accuracy of ORSS-VBLS, W-VBLS, and VD-SVM algorithms is about 0.7, 0.79, and 0.85, respectively. When the number of anchor nodes is 5, the positioning accuracy of VD-SVM algorithm tends to be close to 1, and the positioning accuracy of the other two algorithms tends to be equal.

Figure 16.

Comparison of the influence of number of anchor nodes on positioning accuracy in (a) outdoor and (b) indoor environments.

Time complexity analysis

By analyzing the time complexity of the VD-SVM algorithm, that is, the computational workload required to implement the algorithm, the proposed algorithm VD-SVM is compared with ORSS-VBLS and W-VBLS, and the results are shown in Figure 17. As can be seen from the figure, in both indoor and outdoor environments, the time complexity of VD-SVM algorithm is relatively better, but the gap is small compared with the other two algorithms. In Figure 17(a), the time complexity of the algorithm increases with the increase in n value. When n is between 0 and 15, the time complexity values of VD-SVM and W-VBLS are very similar, and in a certain interval, the time complexity of VD-SVM algorithm is greater than that of W-VBLS algorithm. However, the time complexity of ORSS-VBLS algorithm is unstable as a whole, and when n is 22, the complexity of the algorithm reaches 500. The complexity of W-VBLS and VD-SVM algorithm reaches 500 when n is 23 and 25, respectively. In Figure 17(b), there are some similarities in the time complexity and value of the three algorithms. When n is 15, the time complexity of VD-SVM, W-VBLS, and ORSS-VBLS algorithm is about 190, 200, and 220, respectively. When n is 29 and 27, respectively, the complexity of ORSS-VBLS and W-VBLS algorithm reaches 500. When n is 30, the time complexity of VD-SVM algorithm is about 470.

Figure 17.

Comparison of time complexity of algorithms in (a) outdoor and (b) indoor environments.

Conclusion

In this article, a localization algorithm based on Voronoi diagram and SVM algorithm is proposed. First, the localization region of sensor network is divided into several parts by establishing Voronoi partition model, and the initial region and preliminary estimated position of the target node are judged. In order to further improve the localization accuracy, SVM algorithm is used to locate the target nodes accurately. Through the simulation and real environment experiment verification and analysis, the location algorithm proposed in this article can achieve the better location of the target node, and its performance is better than the other two localization algorithms ORSS-VBLS and W-VBLS. The next step is to further study the verification and analysis of the algorithm in large-scale and complex environment.

Footnotes

Acknowledgements

The authors would like to thank the reviewers for their thorough reviews and helpful suggestions.

Handling Editor: Yanjiao Chen

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China under grant nos 61762079 and 61662070 and Key Science and Technology Support Program of Gansu Province under grant nos 1604FKCA097 and 17YF1GA015.

ORCID iDs

Zhanjun Hao

Yan Yan

References

Broday

. Wireless distributed environmental sensor networks for air pollution measurement the promise and the current reality. Sensors 2017; 17(10): 2263.

Zheng

Wang

, et al. Non-intrusive traffic data collection with wireless sensor networks for intelligent transportation systems. Ad Hoc Sens Wireless Netw 2016; 34: 4157.

Baig

Gholamhosseini

. Smart health monitoring systems: an overview of design and modeling. J Med Syst 2013; 37(2): 9898.

Cheng

. Construction of WSN and application of localization for in-home healthcare of the elderly. Appl Mech Mater 2012; 263-266: 5.

Sghaier

Mellouk

Augustin

, et al. Wireless sensor networks for medical care services. In: Proceedings of the 2011 7th international wireless communications & mobile computing conference, Istanbul, Turkey, 4-8 July 2011. New York: IEEE.

Meimanat

Nikolaidis

, et al. A robust positioning architecture for construction resources localization using wireless sensor networks. In: Proceedings of the winter simulation conference (WSC), Phoenix, AZ, 11-14 December 2011. New York: IEEE.

Chen

Zhang

, et al. An improved spatial localization algorithm in WSN based on GPS. Semicond Optoelectron 2015; 36(4): 618–621.

Stankovic

Stoleru

. Secure walking GPS: a secure localization and key distribution scheme for wireless sensor networks. In: Proceedings of the ACM conference on wireless network security, Hoboken, NJ, 22-24 March 2010. New York: ACM.

Gandhi

Rama

. GPS based multi-hop communication with localization in subterranean wireless sensor networks. Procedia Comput Sci 2015; 57: 1189–1198.

10.

Khalaf-Allah

. Time of arrival (TOA)-based direct location method. In: Proceedings of the 2015 16th international radar symposium (IRS), Dresden, 24-26 June 2015. New York: IEEE.

11.

Yang

Yongyi

Min

. An AOA location algorithm based on wavelet transform. Microcomput Appl 2014; 33(3): 47–49, 54.

12.

Chen

Pan

Liang

, et al. AWCL: adaptive weighted centroid target localization algorithm based on RSSI in WSN. In: Proceedings of the 2010 3rd IEEE international conference computer science and information technology (ICCSIT), Chengdu, China, 9-11 July 2010. New York: IEEE.

13.

Liu

Wang

Yao

, et al. VN-APIT: virtual nodes-based range-free APIT localization scheme for WSN. Wireless Netw 2016; 22(3): 867–878.

14.

Stojkoska

Vesna

. Improved MDS-based algorithm for nodes localization in wireless sensor networks. In: Proceedings of the Eurocon 2013, Zagreb, Croatia, 1-4 July 2013. New York: IEEE.

15.

Cai

Wang

Cui

, et al. Weight convergence analysis of DV-hop localization algorithm with GA. Soft Comput 2020; 24: 18249-18258.

16.

Cai

Wang

, et al. Multi-objective three-dimensional DV-hop localization algorithm with NSGA-II. IEEE Sens J 2019; 19(21): 10003–10015.

17.

Wang

Huang

Cui

, et al. A Gaussian error correction multiobjective positioning model with NSGA II. Concurr Comput Pract Exper 2020; 32(5): 5464.

18.

Wang

Huang

Liu

, et al. Localization algorithm based on SVM-data fusion in wireless sensor networks. In: Proceedings of the 2009 3rd international conference on genetic & evolutionary computing, Guilin, China, 14-17 October 2010. New York: IEEE.

19.

Samadian

. Probabilistic support vector machine localization in wireless sensor networks. ETRI J 2011; 33(6): 924–934.

20.

Mao

Congling

Fei

, et al. Node localization algorithm in wireless sensor networks based on SVM. J Comput Res Dev 2014; 51(11): 2427–2436.

21.

Jiang

Liang

. An indoor localization of WiFi based on support vector machines. Adv Mater Res 2014; 926-930(5): 2438–2441.

22.

Livinsa

Jayashri

. Localization with beacon based support vector machine in Wireless Sensor Networks. In: Proceedings of the 2015 international conference on robotics, automation, control and embedded system, Chennai, India, 18-20 February 2015. New York: IEEE.

23.

Zhu

Wei

. Localization algorithm for large scale wireless sensor networks based on fast-SVM. Wireless Person Commun 2016; 95: 1859-1875.

24.

Tang

Liu

Song

, et al. Support vector machine based range-free localization algorithm in wireless sensor network. In: Xin-Lin

(ed.) Machine learning and intelligent communications Mlicom. Cham: Springer, 2016.

25.

Zhu

Wei

. Localization algorithm in wireless sensor networks based on improved support vector machine. J Nanoelectron Optoelectron 2017; 12(5): 452–459.

26.

Jichun

Liusheng

Hongli

, et al. A novel range free localization scheme based on Voronoi diagrams in wireless sensor networks. J Comput Res Dev 2008; 45(1): 119–125.

27.

Song

Liu

. A hidden Markov model approach for Voronoi localization. In: Proceedings of the IEEE international conference on robotics & biomimetics IEEE, Shenzhen, China, 12-14 December 2013. New York: IEEE.

28.

Lasla

Derhab

Ouadjaout

, et al. Half-symmetric lens based localization algorithm for wireless sensor networks. In: Proceedings of the 37th annual IEEE conference on local computer networks, Clearwater, FL, 22-25 October 2013. New York: IEEE.

29.

Yang

Liu

. Sequence localization algorithm based on 3D Voronoi diagram in wireless sensor network. Appl Mech Mater 2014; 644-650: 4422–4426.

30.

Zhou

Wang

, et al. Principles of the complete Voronoi diagram localization. IEEE Trans Mob Comput 2016; 15(8): 2048–2063.

31.

Qiang

. Non-full sequence-based localization algorithm for 3D underwater sensor networks. J Comput Appl 2018. https://en.cnki.com.cn/Article_en/CJFDTotal-JSJY201801008.htm

32.

Zixiao

Baihai

Lijing

, et al. An optimal region selection strategy for WSNs localization based on Voronoi diagram. In: Proceedings of the 2015 34th Chinese control conference (CCC). Hangzhou, China, 28-30 July 2015. New York: IEEE.

33.

Cai

Pan

Gao

, et al. Research of localization algorithm based on weighted Voronoi diagrams for wireless sensor network. EURASIP J Wireless Commun Netw 2014; 2014(1): 50.