TMCnet News

Wireless Sensor Network Localization Research [Sensors & Transducers (Canada)]
[October 22, 2014]

Wireless Sensor Network Localization Research [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: DV-Hop algorithm is one of the important range-free localization algorithms. It performs better in isotropic density senor networks, however, it brings larger location errors in random distributed networks. According to the localization principle of the DV-Hop algorithm, this paper improves the estimation of average single hop distance by using the Least Equal Square Error, and revises the estimated distance between the unknown node and the anchor node with compensation coefficient considering the wireless sensors deployed in the non-planar application scenarios. This localization algorithm is based on compensation coefficient. Simulation results show that the improved algorithm has better locating performance in locating precision by increasing appropriate computation overhead, and is a feasible locating scheme in WSN in both random distributing and dynamic topology networks. Copyright © 2014 IFSA Publishing, S. L.



Keywords: Wireless Sensor Networks (WSN), DV-Hop, Compensation coefficient, Localization, Algorithm.

(ProQuest: ... denotes formulae omitted.) 1. Introduction Wireless sensor networks (Wireless Sensor Networks, WSN) is composed of a large number of sensor nodes with randomly distributed structure, information collection, processing, self-organizing network forwarding can be done in its cover area. In WSN applications, the location information of the sensor is critical to monitor network activity. In monitoring and tracking the target, routing based on the position information, load balancing of the network, the network topology, and other applications [1], these are required to know the network node own position in advance, the position information is applied in the communication and collaboration process, and these applications are completed. Thus, the wireless sensor network positioning technology is the foundation of the entire network, which achieves a variety of functions.


Existing node localization algorithm can be divided into two categories in the different locating ways [2], there are algorithm based on the distance (range-based) and algorithm without distance (range-free). In positioning algorithm without ranging, DV-Hop (distance vector-hop) algorithm is one of the typical positioning algorithm, it is one of the distributed localization methods, which are proposed in advantage of distance vector routing and positioning beacon nodes, the method is simple, and there is good scalability [3-4], but it is the use of jumping distance instead of straight line distance, ideal positioning effect is achieved only in the isotropic dense network.

In this paper, because there are the limitations of DV-Hop algorithm in the randomly distributed network environment, the network average value per hop distance is obtained by using minimum mean square error method, and the impact on the positioning results are taken into account when monitoring region is non-planar, through the use of compensation coefficient, the fluctuation of the monitored area is reduced, the effects of the calculating distance is down between the unknown node and beacon node calculation, the positioning accuracy of the algorithm is improved.

2. DV-Hop Localization Algorithm The basic idea of DV-Hop localization algorithm is that the distance between unknown nodes and beacon nodes is equal to the product of the network average distance of the per hop and the hop number between them. When the distance with three or more beacon nodes is obtained on the unknown node, their own positioning can be realized. Its positioning is generally divided into three stages [2-3]: First the distance vector broadcast protocol is used between nodes and information is forwarded, in all network nodes, the minimum number of hops between each beacon nodes is obtained; Secondly, after the position of the other beacon nodes and a minimum hop count are obtained in the beacon node, the average network hop distance is calculated, and then it is as a correction is broadcasted to the network. The first correction is only received and record, and it is forwarded to the neighbor nodes, and then based on the smallest hop records, the hop distance is calculated near each beacon node. Finally, when the distances are obtained from an unknown node to three or more beacon nodes, and the trilatération method or maximum likelihood estimation method are performed to calculate their coordinates.

Beacon nodes i,j, k are shown in Fig. 1, the linear distances dtj, dik can be calculated between them according to the distance formula. If the minimum number of hops from i to j, and k is hops y, and hopsk, the average network hop distance of the beacon node i is obtained by the following formula to calculate.

... (1) The average distance per hop is hops ...

Assuming that p is to be positioned node, the number of hops is minimum between beacon nodes i and p, that distance is minimum from beacon nodes i to p. Thus, p obtains the average distance value at each hop from i, Cp = Ci , the estimated distance of each beacon node are C"hopspi,C"hopspj,C"hopspk from p. Then the position of the node p is calculated by using trilatération.

3. Improved DV-Hop Localization Algorithm DV-Hop localization algorithm is the exchange of information based on network connectivity and distance vector, the straight-line distance is instead of hop distance, and average hop distance is only obtained in the isotropic dense network, thus it is closer to the actual distance value, otherwise there is an error larger [7]. In the practical application, WSN nodes are generally randomly distributed between the nodes and the beacon nodes, they are often not known linear path, and the nodes are deployed in the monitor area, these nodes are not completely in the same plane, and then the calculated resulting distance is the estimated value from unknown nodes along the ground curve to the beacon nodes. This is generally greater than the projection of the distance between unknown node and the beacon nodes in the horizontal plane [8]. If you use this estimate to calculate the coordinates of the unknown node, it will exacerbate the error of the estimate coordinate values.

This section is for DV-Hop algorithm limitations in the randomly distributed network environment. First, the original algorithm to calculate the average distance per hop is improved by using minimum mean square error method, and then the estimated distance between the unknown node and the beacon nodes is corrected by using the compensation factor, the positioning accuracy of the algorithm is improved.

3.1. Minimum Mean Square Error Method to Calculate the Average Hop Distance The conventional methods are to calculate the average each hop distance value Ci by unbiased estimation, and because the Formula (2) value is equal to zero, the estimated value of the average hop distance is obtained [5].

... (2) m is the number of beacon nodes in network. The average hop distance value C is estimated by this method, the mean of their estimation error is zero, but in general, the error meets the normal distribution, according to the parameter estimation theory, it is as the cost function of estimation error, using the mean square error is more rational than just to use variance or deviation [6].

Therefore, we use the minimum mean square error method to calculate the average hop distance, if the Formula (3) is minimized the estimated value of the average hop distance can be obtained.

... (3) If ... the average distance per-hop can be obtained based on minimum mean square error method, and the estimated value is as follow: ... (4) For example in Fig. 1, the average hop distance is obtained by calculating beacon nodes according to Formula (4), it is ...

3.2. Calculation of Compensation Coefficient After the inter-node information is mutually forwarded in the first stage, each beacon node can get the coordinate information of other beacon nodes and minimum hops away. At this time, the actual distance of each beacon node the calculated to the other beacon nodes based on the distance formula between two points, respectively, and the average hop distance is calculated according to Formula (4). For example, the coordinates of the beacon node i and beacon node j are respectively (xi,yi),(Xj,yj) * According to the distance formula, the obtained actual distance between them is dj, then the estimated distance is dijEST, which is calculated based on the average hop distance and minimum hops between them, the difference value between the estimated distance and actual distance is A d. =\d.P,T-d-1 , thus this growth ratio of two beacon nodes is ... Finally, the information with the average distance per hop and growth ratio will be broadcasted in each beacon node, so that each unknown node receives the average distance per hop and the growth ratio of every pair beacon nodes, and their values are stored. Thus each unknown node will obtain the following data: (1) coordinate values of each beacon node; (2) to estimate the distance between the node own and each beacon nodes; between (3) ratio of increasing distance between each pair of beacon nodes.

Let the estimated distance be dijEST between the pair of beacon nodes i, j, the increasing ratio is mij the estimated distance between unknown node p and beacon nodes i, j is respectively dpiEST, dpjEST, then ... (5) DpiJ represents the deviation degree factor of connections in which the unknown node p deviate beacon nodes i, j, the greater Dpij, the greater the connection which the unknown node p deviates from the beacon nodes i, j. Since a single mij growth ratio does not fully reflect the communicated state between the node p and the beacon nodes i, j, in order to maximize the distance between unknown nodes and beacon nodes closer to the actual distance, the weighted average method is used [9], the compensation coefficient values of unknown node hops are calculated, and there are least ones of three beacon nodes. Specific methods are as follows: Assuming the known hops from the unknown node p to all beacon nodes, three beacon nodes are identified at least hops. That is three beacon nodes nearest from an unknown node, they are beacon nodes i,j,k.

First, the degree of deviation factor is calculated from the unknown node p to the connections between beacon node i and all the other beacon nodes, i.e.

... (6) where n is the number of nodes in the beacon.

To take the smallest three ones of the degree of deviation factors from unknown node p to the connection lines between beacon nodes i and all other beacon nodes, they are Dpi1, Dpi1, Dp13, and according to the weighted average method, the corresponding compensation coefficient Mpi are calculated from the unknown node p to beacon node i.

...

where mi1, mi2, mi3 are respectively the smallest three ones of the degrees of deviation factors from unknown node p to the connection lines between beacon nodes i and all other beacon nodes. Similarly available from unknown node p to beacon node j, k, their corresponding compensation coefficient are Mpj, Mpk.

3.3. The Distance between Unknown Nodes to Beacon Node is Corrected by Using the Compensation Factor By the above method, we obtain the appropriate compensation factor of nearest three beacon nodes from the unknown node, the estimation distance between them can be corrected. For example, the estimated distance between the unknown node p and the beacon node i is dpiEST, the appropriate compensation coefficient is Mpi, the corrected distance is ..., Similarly available, the corrected distances are ... from p to beacon node j, k. Such corrected distance information of unknown node p is gotten after it got away from its recent three beacon nodes.

3.4. The Coordinates of the Unknown Node are Calculated After the distance information between unknown node and its nearest three beacon node is obtained by the above method, the coordinates of the unknown node are calculated by using trilatération. However, the aforementioned calculated distance from unknown nodes to the nearest three beacon nodes have some errors with the actual situation, which may cause that the trilatération equations has no solution. To avoid this situation, we use the least squares method [10] to calculate the final coordinates of unknown nodes [11-14].

4. Experimental Evaluation By using Matlab, simulation comparative analysis is done on the DV-Hop localization algorithm and its improved algorithms based compensation coefficient. Let node distribution be 100m x 100m square region, the sensor nodes are randomly distributed in the simulation area, the number of nodes is maintained at 150, each node has the same communication distance R = 35m , which the coordinate position of the beacon node is known, the unknown node coordinate position is obtained by algorithm. The different number of beacon nodes are set in simulation, the average location error is compared in the different algorithms. In wireless sensor network positioning, the general positioning error is defined as the ratio of error value between the estimated node position and the actual node position and communication radius that is as follow.

... (8) wherein (...) and (X, y) are the estimated position and the actual position of the unknown node, the average location error is defined as ... error (i) / un, error(i) is the positioning error of the unknown node i, un is the number of unknown nodes.

In this paper, DV-Hop algorithm has been improved in two aspects: First, the network average, estimated value of each hop distance is calculated by using the minimum mean square error method, the second, compensation coefficient is introduced to correct the estimated distance between the unknown nodes and beacon nodes. The simulation is done in the improvement method of the first aspect, on this basis, further improvements are made in the simulation method of the second aspect, the positioning accuracy is compared between the improved algorithm and the original algorithm, the simulation results are shown in Fig. 2 and Fig. 3.

As can be seen from Fig. 2, when the number of participating position beacon nodes is increasing, the positioning error of the two algorithms is reduced. In the beginning, the positioning accuracy of the improved algorithm is little difference with the original algorithm, but with the increase in the beacon nodes, by using minimum mean square error method, the calculated average network hop distance is closer to the actual average distance per-hop in random network, thereby the positioning error of nodes is effectively reduced, wherein the lower maximum value is reached to 8 %.

In Fig. 3, the estimated distance between the unknown nodes and the beacon nodes is corrected further by compensation coefficients, and it is closer to the actual distance, thus the positioning error of unknown nodes is further reduced, it can be seen from the figure that the positioning error is reduced by an average of 15 % to 18 % in the improved algorithm than traditional DV-Hop localization algorithm, positioning accuracy is significantly improved. When the number of beacon nodes is 60, in two algorithms, the improved amplitude of the positioning accuracy becomes smaller, the average location error changes are stabilized.

In summary, the average error is always less in this paper improved positioning algorithm than the original DV-Hop algorithm, and there is good stability. However, during the execution of the algorithm, the growth ratio in the many beacon nodes is broadcasted, and the compensation coefficients are calculated, the improved algorithm of this paper will increase in terms of communication overhead and computation than the original algorithm.

5. Conclusions and Outlook In this paper, because there are the limitations of DV-Hop algorithm in the random distributed network environment, first by using minimum mean square error method, the improvements are made to the original algorithm to calculate the average distance per hop, and then the compensation factor is introduced to correct the distance between the unknown nodes and beacon nodes, DV-Hop algorithm is proposed based on a compensation coefficient. Through simulation, the improved algorithm average location error is less than one of the original algorithms, and there is good stability. However, the positioning accuracy is improved in the improved algorithm, which is adding the amount of communication and the amount of computation, and the algorithm will increase the cost. How to maintain good location accuracy, while reducing the overhead of communication and the amount of computation is the future content of further study References [1] . Peng Yu, Wang Dan, A review: wireless sensor networks localization, Journal of Electronic Measurement and Instrument, 25, 5, 2011.

[2] . Sun Limin, Li Jianzhong, Chen Yu, Wireless sensor networks, Tsinghua University Press, Beijing, 2005, pp. 149-151.

[3] . Niculescu D., Nath B., Ad-hoc Positioning System (APS), in Proc. of the IEEE GLOBECOM, San Antonio, 2001, pp. 2926-2931.

[4] . Niculescu D., Nath B., DV Based Positioning in Ad hoc Networks, Journal of Telecommunication Systems, 22, 1-4,2003, pp. 267-280.

[5] . Ji Weiwei, Liu Zhong, Study on the Application of DV-Hop Localization Algorithms to Random Sensor Networks, Journal of Electronics & Information Technology, 30,4,2008, pp. 970-974.

[6] . Zhang Xianda, Modem signal processing, Tsinghua University Press, Beijing, 2002, pp. 40-42.

[7] . Liu Shaofei, Zhao Qinghua, Wang Huakui, DV-Hop Localization Algorithm Based on Estimate of Average Hop Distance and Correction in Position, Chinese Journal of Sensors and Actuators, 22, 8, 2009, pp. 1154-1158.

[8] . Xu Jianbo, Liu Huiya, Sensor localization algorithm in wireless sensor network based on different plane, Computer Engineering and Applications, 44, 24, 2008, pp. 115-117.

[9] . Huang Dekai, You Tiantong, Improved DV-Hop Algorithm Based on Hop Estimation, Computer and Modernization, 12,2012.

[10] . Lin Jinchao, Chen Bing, Liu Haibo, Iterative algorithm for locating nodes in WSN based on modifying average hopping distances, Journal on Communications, 30, 10,2009, pp. 107-113.

[11] . Jian Li, Jianmin Zhang, Xiande Liu, A Weighted DV-Hop Localization Scheme for Wireless Sensor Networks, in Proceedings of the International Conference on Scalable Computing and Communications', the Eighth International Conference on Embedded Computing, 2009, pp. 269-272.

[12] . Bulusu N., Heidemann J., Estrin D., GPS-less low cost outdoor localization for very small devices, IEEE Personal Communications, 05, 2000, pp. 28-34.

[13] . Hongyang Chen, Kaoru Sezaki, Ping Deng, Hing Cheung So, An Improved DV-Hop Localization Algorithm with Reduced Node location Error for Wireless Sensor Networks, Communications and Computer Sciences, 08,2008, pp. 2232-2236.

[14] . Koen Langendoen, Niels Reijers, Distributed Localization in Wireless Sensor Networks: A Quantitative Comparison, Computer Networks, 2003, pp. 499-518.

Liang Xin School of Information Science and Engineering, Hunan International Economics University, Changsha, 410205, China Tel: 86-0731-88127113 E-mail: [email protected] Received: 1 June 2014 /Accepted: 29 August 2014 /Published: 30 September 2014 (c) 2014 IFSA Publishing, S.L.

[ Back To TMCnet.com's Homepage ]