Research on Optimization of Distributed Node Location Algorithm in Wireless Sensor Networks

This paper studies the related theories of wireless sensor networks, and an improved DV-Hop algorithm is proposed, which used to estimate the distance error mainly based on the error of average per hop distance, unknown nodes and anchor nodes in traditional algorithm. Through the simulation analysis, it can be found that compared with the traditional Location algorithm of DV-Hop and other improved algorithm, the improved algorithm proposed in this paper can reduce the location error and improve the location accuracy when the proportion of the anchor nodes is moderate and the communication radius is small, and this algorithm is suitable for the low power and wide range wireless sensor network environment.

The WSNs randomly distribute its nodes in the monitoring zone, and the collection, processing and transmission of information are implemented for the perceived objects, which includes sensor node, task management node and sink node. The nodes in sensor are randomly broadcast, and its functions include generating and transmitting monitored data, and transmitting the data to the surrounding sensor nodes after a simple local processing, and the information is transmitted to the sink node by using the way of multi-hop. Each sensor node can acquire, process and transmit monitored data.

Topology Structure
Nodes in wireless sensor network are broadcast randomly, cluster-based topology structure and planebased topology structure form the node topology.

2.2.1.
Cluster-based topology structure. In wireless network, the nodes can be categorized into different clusters, each of which is formed from a cluster head and several members. All of the cluster members transfer the collected data to the head; the sink node receives the data through multi-hop or directly after the cluster head completes a simple data fusion [3]. Cluster head is responsible for large amounts of communication and computation, and it requires more energy consumption. In general, every sensor node in each cluster takes as the cluster head in turn.

2.2.2.
Plane-based topology structure. Plane-based topology structure can be divided into networkbased planar topology and chain-based planar topology. In network-based planar topology, the network structure formed by nodes, and the sensor nodes only exchange data with neighbour nodes, and finally converge to sink nodes, as shown in Figure 1 (a). This topology can still maintain the life of the whole network when some nodes died [4]. In chain-based planar topology, the unknown nodes form several links for sink node to receive information. In the link, the closer distance between sensor node and sink node means larger and more important data transmission. Their neighbours need to reconstitute the link to transmit data, and as shown in Figure 1

Improvement for the Location Algorithm
Although the location algorithm of DV-Hop has the benefits of good scalability and low complexity, location accuracy of it is low. Based on Location algorithm of DV-Hop, the mean per hop distance for the anchor node is improved in this paper firstly. During the calculation process, the anchor nodes selected based to a certain standard, and take the distance between each anchor nodes as the weight to reduce the introduction error [5]. Secondly, for unknown nodes, this paper improves the selection process of the average distance of per hop. Since there are different hops number from the unknown node to the anchor node, different schemes are chosen to obtain the mean distance of per hop for the unknown node. We use the mean hop scope to reduce the error when we get the estimation of the distance from unknown nodes to anchor nodes. Degree of collinearity theory refers to the minimum value in the high line of the three-edge of a triangle consisting of three anchor nodes. As the research shows, if the anchor nodes are collinear or almost collinear, the mean distance for one hop has the minimum error. This section reduces the error in calculating process of mean hop distance of for the anchor node is reduced by screening and weighted. Among the anchor nodes, when the unknown nodes have poor degree of collinearity, using the ratio, which is the actual distance for anchor nodes to minimum hops to calculate average per hop distance will introduce error. For this problem, the method adopted in document is that use the correction coefficient to correct after getting the mean distance per hop between anchor nodes [6]. The coefficient is calculated from the actual distance for the anchor node; ratio of estimate distance difference to hops, which has a certain effect. The methods in this section include first eliminating the anchor nodes that will introduce large errors, and then weighting the anchor nodes [7].
For the rectangular distribution area, the maximum ideal hop k is defined as: (1) (d1, d2, d3 and d4 represent the distance from anchor node i to four vertices of rectangular distribution ranges) In ideal situation, the average distance between hops is close to the communication radius. When the minimum hops the anchor, the node will receive from the other anchor nodes is beyond the maximum ideal hops in the range of node distribution, it will show the degree of collinearity between the anchor nodes is lower in this path and it is removed.
After eliminating the anchor nodes with the poor degree of collinearity, using the method of weighted processing to obtain average jump distance of anchor node i. Definition: (dij means the real distance from anchor nodes i to j； R means the communication radius； hopsij represents the minimum hops from anchor nodes i to j) When the anchor node i is involved for the calculation of the hops' mean distance of nchor node j whose weight is: (m denotes the anchor nodes' number participating in calculating the average distance of hops for the anchor node i) The hops' mean distance for the anchor node i is as follows:

Mean distance for the unknown nodes per hop.
In the selection of the mean hops for these unknown nodes, when the anchor node and the unknown node are at 1 hop, the algorithm of IDV-Hop will directly select the anchor node's average hops, otherwise, the average hops for all anchor nodes should be chosen, so that the division is too general. In algorithm of MDV-Hop, when the hops between the unknown node and the anchor node is smaller than the value of the threshold M, the mean value of the hops' average distance of these anchor nodes is chosen as the hops' mean distance for the unknown nodes, and this strategy increases the computational complexity for the unknown node and anchor node in the 1 hop range. This section presents an improvement for the unknown nodes' average hop distance based on MDV-Hop and IDV-Hop [8]. When the anchor and the unknown node are in the 1 hop range, unknown node directly selects the nearest anchor node hops' mean distance as its mean hop distance. When the minimum hop of unknown node and anchor node is between in the 1~M hops, it takes the mean value of the all anchor nodes' mean hop distance within M hop as mean hop distance. When the minimum hop for the unknown node and anchor node is outside the M hop, and the global mean hop distance is taken [9]. The mean distance of hops for the unknown node K is: (m represents anchor nodes' number in the M hops range around the unknown node k.; n represents the anchor nodes' number in the entire WSN) The threshold M is: (A represents the area that the entire wireless sensor network covered; Ln represents anchor nodes' average number needed for each unknown node location; Tn represents the total nodes' number; Lp represents the anchor nodes' proportion; Hmax represents the maximum number of minimum hops between anchor and unknown nodes) In the case of satisfying the location of all unknown nodes, M selects the minimum value to participate in the operation. When the nodes were distributed unevenly, threshold M needs to be selected slightly larger to meet the coverage of the entire network. The parameter p (the value is between 0-1) is used to adjust the lower limit of the threshold M. If the proportion of anchor nodes is large, a smaller p value can be selected to raise the lower limit. Conversely, if the proportion of anchor nodes is large small, large P values can be selected to reduce the lower limit.
According to the formula (5), in different cases, unknown nodes will select different mean hops distance according to the anchor nodes minimum hops, which overcomes the error caused by simply leveraging the nearest anchor node's mean hops of in the traditional DV-Hop algorithm, and when the unknown node and the anchor node within 1 hop range, it guarantees the average hop distance's accuracy.

The estimated distance calculation based on the average hop scope.
When the nodes' density of near the anchor and the unknown node differs, the difference between the mean distance of hops of the two is larger, and simply using the mean unknown nodes' hop distance to get the calculation distance will lead to large errors. In this section, the average hop scope is claimed. After getting the mean hop distance for the anchor nodes and the unknown nodes mean hop distance, when calculating the distance between the unknown and the anchor nodes, half of hop number near the unknown node leverages the unknown hop mean distance to get the distance, and the other half uses the anchor nodes mean hop distance [10]. The calculation process is: Hopsize hops Hopsize hops = × + × (7) (Hopsizei represents the anchor node i mean hop distance; Hopsizek represents the average hop distance for the unknown node k) And satisfies:

Analysis of Average Location Error
Each experiment was done 100 times, the mean value of which is used as the ultimate result to compare how the anchor nodes' proportion for the impacts on the location error when the communication radius R is set to be 30m. The result is shown in Figure.3. The location error for the 6 three algorithms are compared at different ratio of anchor nodes. With the anchor nodes' proportion adding, the three algorithms' location errors are decreasing. When the proportion for the anchor nodes becomes small, and in the WSN area the anchor nodes are not evenly distributed and have large randomness. Most of the unknown nodes in IDV-Hop and MDV-Hop algorithm choose the global average distance of hops as their own hop distance. and the improved algorithm in this section has a significant effect through the double segmentation of 1 hop and threshold M. When the anchor node's proportion is at 15%~30%, the location effect of threshold M in MDV-Hop algorithm performs better compared with that of simple 1 hop segmentation in IDV-Hop algorithm, and the algorithm is separately processed on the basis of the threshold, and the effect is better. When the proportion for the anchor nodes is more than 30%, the location error does not decrease obviously with the increase of anchor node. The improved algorithm in this section is better than other algorithms.

Figure 3. Comparison of location error under different communication radius
If the communication radius increases, the location errors of all algorithms are reduced. If the communication radius is less than 25m, the distance of 1 hop is small. In the comparison for the algorithm that was improved in this paper, more unknown nodes in IDV-Hop and MDV-Hop algorithm choose the global mean distance of hops as their own hop distance, which leads to the accumulation of errors. If the communication radius is greater than 28m, the anchor nodes obtain the average distance of hops and get better results after screening and weighting, while the average distance of hops scope further reduces the error. In comparison with other improved algorithms, the proposed algorithm was improved has the advantages of different levels.

Fluctuation Analysis of Location Error
When it has totally 100 nodes and 30m communication radius, and 20% nodes are the anchor nodes, every unknown node's location error is depicted in Figure.   section is relatively stable. In order to more clearly compare the differences of fluctuation, the variance is used to represent the data in this paper. The variance of node location error of each algorithm in 100 times experiments shows in Figure.5. The larger the variance is, the greater the error fluctuation of the unknown node location is. Simply comparing the average location error can't fully explain the algorithm's advantages and disadvantages. When the variance is very large and the average location error is very small, for some unknown nodes, their error in the location process is far greater than the average location error, which is unfavourable to the practical application.

Conclusion
The improved the traditional location algorithm of DV-Hop is proposed in this paper. Firstly, when calculating the anchor node's average hop distance, the anchor nodes are screened and weighted, and the anchor nodes that are likely to introduce relatively large errors are eliminated to get the improvement for the accuracy of anchor node mean distance of hops. Secondly, when the calculation of the mean distance of hops between unknown nodes, different selection schemes are adopted for different unknown nodes. Based on the hops of the nearest anchor and unknown node, average hops of anchor node, mean hops of anchor node within the range of M hop or global average hops are selected as its own hop distance. Finally, when the calculation for the distance from anchor node to unknown node, different mean distance of hops to participate in operation will be chosen based on the mean distance of hops scope. When the anchor nodes have the moderate proportion and small communication radius, the algorithm can increase the location accuracy and decrease the location error, which can be widely applicable to the wireless sensor network environment with low power and wide range.