Abstract: The traditional DV-Hop localization algorithm does not take into account the impact of differences between neighbouring nodes in calculating the average distance per hop distance, resulting in reduced positioning accuracy. To solve this problem, we designed a DV-Hop localization algorithm based on RSSI correction. According to the RSSI dissipation model principle, hops are weighted by using RSSI signal strength values. Our proposed algorithm performed as follows. First, it calculates the average distance per hop by using the hops which have been weighted. Second, it calculates the whole network average distance per hop. Finally, it calculates the coordinates of the unknown node with a total least squares method. Simulation results show that the proposed algorithm effectively improves the positioning accuracy without increasing hardware devices.
INTRODUCTION
Node localization algorithms are divided into two categories in Wireless Sensor Network (WSN), i.e., localization algorithms based on ranging and localization algorithms without ranging was proposed by Sun et al. (2005). The former algorithms calculate the position according to measured information, though high accuracy they require special hardware implementation and high cost. The latter algorithms often use methods such as multi-hop routing exchange information and nodes connectivity to carry through position estimation without additional hardware, so, they are more suitable for practical applications in large-scale wireless sensor networks and they are getting more attention in positioning algorithms as the work of Wang et al. (2005).
DV-Hop proposed by Niculescu and Nath (2003) is a widely used localization algorithm in WSN such as in the study of Lin et al. (2009), Wang et al. (2011), Zhou et al. (2011), Zhang et al. (2012), Wen et al. (2014) and Guo et al. (2013). They have improved the algorithm and achieved certain results. Each improved methods have certain drawbacks. For example, DV-Hop algorithm does not weight hops according to the distances between neighbouring nodes when calculating hops which only uses beacon nodes’ average distance per hop to estimate the distances between the unknown nodes and the beacon nodes and it uses maximum likelihood estimation method to calculate the coordinates of the unknown nodes. Because of these above three aspects, these algorithms can reduce positioning accuracy, such as the studies of Lin et al. (2009), Wang et al. (2011), Zhou et al. (2011) and Zhang et al. (2012). In order to improve the positioning accuracy, a new improved algorithm is proposed in this study.
MATERIALS AND METHODS
For the benchmark of our study, we first review of DV-Hop algorithm which is a distributed localization algorithm based on distance vector which was proposed by Niculescu and Nath (2003). The basic idea is that the estimating distance between the beacon nodes and unknown nodes is obtained through hops multiplied by the average distance per hop.
Algorithm positioning process: DV-Hop algorithm positioning process goes through three stages:
| • | Counting the minimum the number of hops between nodes: Beacon node broadcasts packets which contain coordinates of the location itself, number and hops to the neighbour nodes. Neighbour nodes record packet information ignoring packet from the same node with larger hops. Then packet’s hops value pluses 1 and forwards to their neighbour nodes. By this stage, all the nodes obtain the minimum number of hops for each beacon node. |
| • | Estimating the distance between the beacon nodes and the unknown nodes: After stage 1, each beacon node uses the following equation to calculate the average distance per hop: |
| (1) |
where, (xi, yi) and (xj, yj) denote the position of beacon nodes i and j, respectively and hopsj is the minimum number of hops between i and j. Then, the beacon nodes broadcast calculated hopsizes to the network. After unknown nodes receive them, estimation of distance between the two can be obtained through hopsize multiplied by the minimum hop count hops.
| • | Unknown nodes position estimation: After unknown nodes getting the distance of three or more beacon nodes, they use trilateration method or maximum likelihood estimation method to estimate their position coordinates |
Algorithm problems: In the DV-Hop localization algorithm, curve distances from the beacon nodes are estimated through using the straight-line. Nodes connect each other with a certain probability. When two nodes far away communicate with each other with a small probability, a greater positioning error is bound to occur if the number of hops between nodes is simply thought as one hop. Even if no other factors, simply using the number of hops to indicate the distance is not reliable, because the distances between values from the same number of hops between the distance values vary greatly.
As shown in Fig. 1, B1, B2, B3 are beacon nodes, A is an unknown node. Distances from B1 and B2, B3 are 40, 75, 100, respectively and the minimum number of hops, respectively is 2, 5, respectively. The average distance per hop of B1 is (40+100)/(2+5) = 20. Actual distance between B1 and B is 15 and between B and A is 40. Using DV-Hop to estimate the distance between B1 and A is 20x2 = 40 which is greater from the actual distance. Therefore, in the case of non-uniform network structure, positioning accuracy is low.
| Fig. 1: | Schematic diagram of DV-Hop algorithms distance error |
Improved algorithm: When calculating the number of hops in the first stage in DV-Hop algorithm, it does not base on the distance between nodes to weight the number of hops, thereby resulting in a lower positioning accuracy. To solve this problem, the improved algorithm proposed in this study, gives different weights between nodes according to nodes distance which can alleviate the problems.
Jump distance was used instead of the actual distance to calculate the distance between the unknown nodes and beacon nodes in second phase of DV-Hop algorithm. In general, it is non-straight line between two nodes, so large error occurs when the number of hops is multiplied by the average distance per hop, resulting in reduced positioning accuracy. Improved algorithm at this stage uses the whole network average distance per hop to replace the average distance per hop to make the estimated distance between unknown nodes and beacon nodes closer to the actual distance between them. Finally, using total least squares method instead of the maximum likelihood method or trilateration to calculate the coordinates of unknown nodes in the third stage.
RSSI: Received Signal Strength Indicator (RSSI) estimates the distance according to signal attenuation between transmitting and receiving nodes. The study of Yang et al. (2011) showed that with transmission distance increasing, the value of RSSI value decreases Zhao and Chen (2009). The transmission model of RSSI is shown as follows:
| (2) |
where, Pr(d0), Pr(d) are reception power when distance is d0 and distance is d, respectively. d0 is a reference distance measured from nearby transmitter. β is path loss factor, usually the value is between 2 and 4.
The closer the distance, the greater the RSSI value measured of the receiving node, the greater the distance, the smaller the RSSI value measured of the receiving node which can be seen from the RSSI transmission model. Therefore, RSSI value between nodes can be used to sign the size of the distance. This algorithm uses RSSI ranging technology to weight hops.
Improved algorithm positioning process
Weighted number of the minimum hops between nodes: Beacon node broadcasts a packet (xi, yi, idi, hops, RSSIi) directly to its neighbour nodes. Where in, xi, yi are the coordinates of a beacon node, idi is an identification number of the node, hops is the hop count which is initialized to 0, RSSI is the signal strength of node receiving group which is initialized to 0.
The direct neighbour node records the packet information after receiving it, hops plus 1, RSSI is nodded as RSSI value of the reception time of the packet and then, forwards the packet to its neighbour node, after neighbour node receives the packet, it calculates weights according to RSSI value R of the reception packet: wi = RSSIi uses weights to weight value of hops in the packet: hops = hops+wi and to forward this packet.
If a node receives packer with the same number of id from other nodes, it will compare the received value with the value of hops in their stored packet. Packer is ignored if the hops in is greater than the current value, if less then return step b to weight hops.
By this stage, all the nodes obtain the weighted hops of all the beacon nodes.
Estimating the distance between the unknown nodes and the beacon nodes: Similar to second stage of DV-Hop, each beacon node uses Eq. 1 to calculate the average distance per hops.
Each node broadcasts the average distance per hops which it calculates, the packet format is (idi, hopsize). Each node that receives this data adds this information to the table. Then it continues to broadcast it to its neighbours. A packet with repeating id is discarded. After the broadcast, all the nodes know the average distance per hop of each beacon node. Then taking the sum of all the average distance per hop and averaging as follows:
| (3) |
where, n is the number of the beacon nodes. The average distance per hop of the whole network is obtained. The distance between it and the beacon node is calculated as follows:
| (4) |
Estimating position of unknown nodes: When the unknown node i gets more than three values of di, different from DV-Hop algorithm, the improved algorithm uses the total least squares to calculate the coordinate of unknown node.
Theorem of the total least squares method was described in work of Yang et al. (2011) and works of Liu et al. (2011).
In linear equation AX = B, set A∈Cm×n, B∈Cm×n and R(B)⊆R(A), singular value of A and C are decomposed as
| (5) |
where, V11(p) is a n row and the p column of the matrix, V12(p) is a n row and the (n+d-p) column of the matrix, V12 is a d row and the p column of the matrix, V23(p) is a d row and the (n+d-p) column of the matrix.
Set σp<σp+1, when V22 full row rank, A, B, respectively are
Total least squares method fully considers two errors generated by position deviation caused by GPS itself positioning. They are beacon nodes position error and Inter-node distance error. Thus, at the same time reflect the calculated coordinates of unknown nodes affected by two errors, therefore, make more precise coordinates of unknown nodes.
RESULTS AND DISCUSSION
Set of parameters: In order to verify the performance of the improved algorithm, we use MATLAB7.0 to simulate the algorithm. We deploy 100 nodes randomly in the flat area 100×100 m. Assume unknown nodes and beacon nodes have the same transmission radius R, the value of which is 50 m. Percentage of beacon nodes is ranged from 0.05-0.35. We compare our algorithm from position error and ranging error with the traditional DV-Hop algorithm (Lin et al., 2009; Wang et al., 2011; Zhou et al., 2011; Zhang et al., 2012; Wen et al., 2014; Guo et al., 2013).
Positioning error: We first compare the average positioning error of proposed algorithm with the average positioning error of DV-Hop algorithm at different ratios of beacon nodes. The results are shown in Fig. 2.
We next compare the average positioning error of proposed algorithm with the average positioning error of DV-Hop algorithm at different ratios of beacon nodes. The results are shown in Fig. 3.
From Fig. 2 and 3 we can find that compared with the traditional DV-Hop algorithm, the proposed algorithm can greatly improve the positioning error and average position error which means that positioning accuracy is considerably improved in the case when rare beacon nodes are deployed.
| Fig. 2: | Comparison of positioning error within 100×100 m area |
| Fig. 3: | Comparison of positioning error within 200×200 m area |
| Fig. 4: | Comparison of ranging error |
Ranging error: When the communication radius is 50 m, ranging error comparisons of DV-Hop algorithm and improved algorithm with the change of the number of beacons are shown in Fig. 4.
As can be seen from Fig. 4, ranging errors of the improved algorithms are much lower than those of DV-Hop with beacon increasing. For example, when the communication radius is 50 m, ranging error of the improved algorithms reduces 1.85 m compared with the DV-Hop algorithm. The results shown in Fig. 4 verify that our proposed algorithm can greatly improve the ranging errors compared with the traditional DV-Hop method.
From the above analysis we can obviously find that our proposed algorithm can greatly improve positioning errors, average positioning errors and ranging errors compared with the traditional DV-Hop algorithm which validate the good performance of our method.
CONCLUSION
Positioning accuracy and power consumption are two important indicators of evaluating positioning algorithm. The traditional DV-Hop localization algorithm does not take into account the impact of differences between neighbouring nodes in calculating the average distance per hop distance, resulting in reduced positioning accuracy. In order to improve the positioning accuracy, a localization algorithm in sensor nodes which use a RSSI to correct DV-Hop algorithm is proposed. In the case of without adding additional hardware, the improved algorithm modifies the calculation of the number of hops in the first stage DV-Hop algorithm. In the second phase, adding a broadcast packet increases a small amount of network traffic. Experimental results show that in the case of a slight increase in network traffic and a slight increase in the case of the calculation, compared with existing methods, the improved algorithm greatly reduces ranging error and positioning error rates, improves the positioning accuracy of the node and has a strong practice.
ACKNOWLEDGMENT
The present study was supported in part by Young Talents Fund Project in Anhui Province of China (No. 2013SQRL083ZD), Anhui University Provincial Natural Science Research Project (No. KJ2014A247) and Open platform topics of Suzhou University of China (No. 2012YKF38, No. 2011YKF10).