A Node Localization Algorithm for Wireless Sensor Networks Based on Virtual Partition and Distance Correction

WSN is the core component of the Internet of Things. It has the advantages of large scale, low cost, strong adaptability and excellent expansibility, which makes the transmission, processing and application of information in an innovative way. With the development of communication technology, WSN has been widely used in national defense deployment, military reconnaissance, geological survey, intelligent agriculture and other fields, realizing the combination of the Internet of Things and the real world. The nodes in WSN can be divided into sink nodes and other nodes [1]. Generally, sink nodes has strong storage and communication capacity. It can be either an enhanced sensor node or a gateway device with a communication interface. The main task of the sink node is to conduct data interaction with the outside world through a variety of ways, and connect WSN with some other external networks (such as Internet, satellite, 4G/5G communication network and so on) [2]. The main task of other nodes is to collect data in the environment and send the data to the sink node, and then sink node will feedback the data to terminal computer or users [3]. A typical WSN structure is shown in Figure 1.

However, in most cases, the data collected by the sensor nodes must be combined with the location of the sensor nodes to be meaningful. Even more, sometimes users just need the sensor nodes to send back its own location. Therefore, the location of sensor nodes is an important part of WSN, and how to make the location calculation of sensor nodes closer to the reality has become the focus of research in the field of WSN.

At present, sensor nodes localization method can be roughly classified into three categories: the range-based localization method based on external device, the range-free localization method based on network topology structure, the intelligent optimization algorithm localization method. The range-based localization method needed additional distance measurement equipment in the sensor nodes, which would increase the extra hardware costs. And in the forests, swamps, volcanoes and other special circumstances, the precision of distance measuring instrument is easily influenced by adverse environment conditions, which will cause the whole network to paralysis. Therefore, in the case of limited resources and environmental conditions, the range-based localization method is not applicable. For the intelligent optimization algorithm localization method, it usually obtains the coordinates of sensor nodes through thousands of iterations. However, excessive iterative calculation will consume a large amount of energy, which will undoubtedly shorten the life of sensor nodes. In addition, the experiment proves that the localization effect of the intelligent optimization algorithm is very poor in some cases, which is mainly because the intelligent optimization algorithm cannot search further when the coordinates of the beacon nodes is extremely lacking [4]. Therefore, the localization method based on intelligent optimization algorithm is not suitable for WSN. Compared with the above two localization methods, the range-free localization method does not need additional ranging equipment and a lot of calculation. Only according to the network architecture and the connectivity between sensor nodes the coordinates of unknown nodes can be estimated, which can meet the requirements of WSN on energy consumption, cost, application environment and other conditions. To sum up, the range-free localization method is the focus of current research.

DV-Hop algorithm is the most concerned range-free localization algorithm by researchers at present, and it has the advantages of low complexity and good scalability. In DV-Hop algorithm, hop error is the main reason for the unsatisfactory localization accuracy. As shown in Figure 2, the unknown nodes $x$ and $y$ are both located in the communication circle of beacon node $A$, and $Ax\ll Ay$. However, according to DV-Hop, $Ax=Ay$ is obtained. So the result of the one hop distance is seriously inconsistent with the actual situation. Therefore, the traditional DV-Hop algorithm will cause a large distance estimation error and greatly reduce the accuracy of the final localization results. Aiming at this problem, the relevant literature at home and abroad has given the corresponding solution strategy. In Reference [5], Shi D et al. adopted the minimization of average hop error to correct the location of unknown nodes, which has optimized the localization accuracy. In Reference [6], Xue D put forward a genetic optimization DV-Hop localization algorithm. This algorithm was improved by error distance weighting, and the location of unknown nodes was obtained by using the weighted method and analyzing the distribution of beacon nodes, which had lower localization error than DV-Hop. Shi Q proposed a distance weighted algorithm based on DV-Hop in Reference [7],which determined the weight value of least squares by taking advantage of the different influence of beacon nodes, then used the weighted likelihood estimation and trilateral measurement localization to complete localization, thus improving the localization accuracy. In Reference [8], Yi Shang proposed an improved MDS-MAP localization algorithm, which was designed to make MDS-MAP localization algorithm also suitable for distributed location calculation. Since the improved MDS-MAP algorithm divides the whole network into small areas, the MDS-MAP algorithm is implemented in local areas to improve the localization accuracy. Wu C and Yang T proposed an improved DV-Hop algorithm in [9], this algorithm put forward an improvement wireless channel model and a refinement method for the irregularity of WSN based on node degree, improved the poor performance of DV-Hop algorithm in localization accuracy. In Reference [10], Han F et al. proposed a WND-DV-Hop algorithm based on weighting factor. By correcting the counting of one hop between nodes, a weighting coefficient was constructed based on the number of hops, which reduced the influence of beacon nodes with large hops on the localization result. Error correction is carried out after the unknown nodes complete localization, which further improves the localization accuracy. In Reference [11], Li J et al. proposed a new heuristic algorithm based on DV-Hop, which named parallel compact cat swarm optimization (PCCSO). PCCSO algorithm has three communication methods, and the localization result is better than DV-Hop algorithm. Song L et al. proposed a DV-Hop localization algorithm based on the glowworm swarm optimisation (GSO) of mixed chaotic strategy (MGDV-Hop) in Reference [12]. In MGDV-Hop algorithm, the fitness function is established based on the GSO algorithm and through hundreds of iterations to complete the localization. MGDV-Hop algorithm reduces the average localization error to a certain extent.

In general, most of algorithms are optimized on the basis of DV-Hop algorithm, and it has improved the localization accuracy. However, these algorithms still use the distance calculation method of DV-Hop, which multiplies the number of hops by the single hop correction value, so it is still unable to fundamentally avoid the impact of the error caused by the hop distance and the number of hops on the localization results [13]. To solve this problem, this paper proposes a VP-DC localization algorithm. In the distance estimation stage, using the virtual partition algorithm and optimal path search algorithm to calculate the distance, the DV-Hop distance calculation method is abandoned, avoid the hop error effectively. A large number of experiments have proved that the VP-DC algorithm can improve the accuracy of distance estimation between nodes and greatly improve the localization accuracy. It has strong robustness and can be well applied to WSN.

If the communication radius of the node is $R$, then the communication area of the beacon node is divided into several concentric circles with $R/m,2R/m,\cdots \cdots R$ as the radiuses ($m$ is the number of concentric circles), and unknown nodes within the communication range of the beacon node construct virtual circle with $R/m$ as radius. Then, according to the geometric analysis, obtain the area equations of the parts where the virtual circle intersects with each of concentric circles. Finally, the distance of one hop is obtained according to the distribution of nodes in each intersecting parts satisfying the Poisson Distribution solution equation. Since the nodes are randomly distributed, the distance of one hop calculated by different intersecting parts may be different. Therefore, this paper weights these distances to further reduce error. When dividing concentric circles, the larger the value of $m$, the more the intersection parts between the concentric circles and the virtual circle, and the higher the accuracy of the distance calculated by weighting. However, when the distribution of nodes is sparse, leading to the intersection parts are too small and no nodes in some intersection parts, which does not satisfy the Poisson Distribution model, resulting in large distance estimation error. According to a large number of simulation data, when $m=3$, the nodes distribution in each intersection part is the closest to Poisson Distribution model, which can meet the characteristics of WSN node random distribution.

As shown in Figure 3, it is known that $B$ is a beacon node, $U_1,U_2,U_3\cdots U_i$ are unknown nodes, $R$ is communication radius. With $B$ as the center of the circle and $R/3$, $2R/3$, $R$ as the radius, the communication circle of the $B$ is divided into three concentric circles. The unknown nodes located inside the communication circle of $B$ are constructed as virtual circle with the radius of $R/3$. Taking the unknown node $U_i$ as an example, assuming that the distance from $U_i$ to $B$ is $d_i$, and the intersecting areas of the virtual circle of $U_i$ and the three concentric circles of beacon node $B$ are $S_{i1}$, $S_{i2}$, $S_{i3}$ respectively. By analyzing geometry, $S_{i1}$ can be expressed as:$S_{i2}$ can be expressed as:$S_{i3}$ can be expressed as:$d_{i1}$, $d_{i2}$, $d_{i3}$ are the distances from $U_i$ to $B$ in these three cases respectively. The distribution of nodes in WSN is random, so the probability that the unknown node $U_i$ is located inside and outside the communication circle of beacon node $B$ approximately satisfies the Poisson Distribution model [14]. The probability function of Poisson Distribution model is: It is known that the area of the communication circle of $B$ is $\pi R^2$ and the quantity of nodes in the communication circle is $n_B$; the quantity of nodes in the virtual circle of unknown node $U_i$ is $n_i$; and the quantity of nodes in the three intersecting areas are $n_{i1}$, $n_{i2}$, $n_{i3}$ respectively. According to the Poisson distribution model, the following formulas can be listed: By Equations (5)–(7) [15], the values of $S_{i1}$, $S_{i2}$, $S_{i3}$ can be obtained. Substitute the values of $S_{i1}$, $S_{i2}$, $S_{i3}$ into Equations (1)–(3), and then, by solving these three Equations, the values of the unknowns $d_{i1}$, $d_{i2}$, $d_{i3}$ can be obtained respectively. Finally, $d_{i1}$, $d_{i2}$, $d_{i3}$ are weighted and averaged to obtain $d_i$, which is can be expressed as: Thus, the distance of one hop on the communication path is obtained.

In the distance estimation stage, the length of the shortest communication path between nodes is regarded as the actual distance between nodes in the traditional localization algorithm. As shown in Figure 4, $u_1, u_2,\cdots u_8$ are unknown nodes; $b_1$, $b_2$ are beacon nodes. From the figure, it can be seen that the shortest communication path between $b_1$ and $u_4$ is similar to a straight line, so the shortest communication distance is approximately equal to the actual distance between $b_1$ and $u_4$, which is $d_{b_1{u}_1}+d_{u_1{u}_2}+d_{u_2{u}_3}+d_{u_3{u}_4}\approx d_{b_1{u}_4}$; However, the shortest communication distance between $b_2$ to $u_8$ obviously longer than the actual distance, namely the $d_{b_2{u}_5}+d_{u_5{u}_6}+d_{u_6{u}_7}+d_{u_7{u}_8}\gg d_{b_2{u}_8}$. To sum up, when the shortest communication path between nodes is tortuous or deviates from a straight line, the shortest communication distance is far longer than the real distance between nodes [16]. In this case, if the shortest communication distance is still taken as the actual distance between nodes, it will bring a large distance estimation error and eventually reduce the accuracy of localization results. For avoid the distance estimation error mentioned above, this paper proposes a distance estimation method based on optimal path search and distance correction.

Assume that the quantity of beacon nodes in the entire network is $n$, the coordinates of these beacon nodes are: $b_1\left(x_{b_1},y_{b_1}\right)\cdots \cdots b_j\left(x_{b_j},x_{b_j}\right)\cdots \cdots b_n\left(x_{b_n},y_{b_n}\right)$. According to the optimal path search and distance correction, the distances between $u_i$ and each beacon node can be obtained. The distances between $u_i$ and each beacon node are: $d_{u_i{b}_1}\cdots \cdots d_{u_i{b}_j}\cdots \cdots d_{u_i{b}_n}$, so the follwing equations can be obtained: According to the trilateral measurement: Express the Equation set (16) in the form of $DX=E$, so: According to the least square method: Therefore, the coordinate of the unknown node $u_i$ is $\left(x_{u_i},y_{u_i}\right)$.

When the communication radius is 20 m, VP-DC and the other three algorithms are simulated with different number of beacon nodes, and evaluate each algorithm on the basis of the simulation results.

When number of beacon nodes is 20, simulate the VP-DC algorithm and the other three localization algorithms by constantly changing the communication radius. And evaluate each algorithm on the basis of the simulation results.