Abstract: Localization is significant for various applications in Wireless Sensor Networks. It is found that the estimated hop-distance will affect localization result. In this study, we propose a Cosine Theorem-based DV-hop localization algorithm (CTDV-hop) to improve localization precision. After estimating the average hop-distance by the traditional DV-hop technique, we select the middle node between every two anchor-pairs in the transmission route one by one. Then the estimated hop-distance is adjusted by the angle between the anchor-pairs to that selected middle node. We hence obtain the improved localization results and can accurately locate even the distribution of nodes is non-uniform. The simulation results illustrate that the CTDV-hop algorithm effectively improves the localization precision without extra energy consumption in networks.
INTRODUCTION
A number of sensor nodes, which have the abilities of sensing, processing and communication, form Wireless Sensor Networks (WSNs). They autonomously observe the physical world and periodically transmit data to the Base Station. It is necessary to associate the acquired data with positions and make data geographically meaningful. Many applications, such as target tracking, environment monitoring (Xiao and Wu, 2010), all inherently rely on the location information. The sensing data might be meaningless for applications if there is lack of node positions. Besides, location information also supports some fundamental network layer services including topology controlling, routing and clustering, etc. Hence, localization is a crucial issue for different applications of WSNs.
Generally, sensor nodes are randomly deployed into the interesting field by aircraft or rockets. Manually recording or entering the positions of each node is impractical especially for large scale WSNs. GPS (Global Positioning System) can solve the problem of localization in outdoor environments. For very small, cheap and low power devices, however, practical considerations such as limited cost and power of nodes preclude the use of GPS from all them (Bulusu et al., 2000). Therefore, GPS equipments can only be equipped onto anchor nodes in WSNs localization. Based on the anchors assisting, the other nodes (unknown nodes) obtain their positions adopting in different localization algorithms.
Low consumption and accurate position are the two major indicators of localization algorithm performance (Gao et al., 2010a). Many localization algorithms are designed based on various positioning principles, environmental constrains, accuracy requirements (Gao et al., 2010b) etc. There are two typical types of localization algorithms according to whether measuring the actual distances between nodes or not: Range-based and Range-free. Due to hardware limitations and power constraints of sensors, Range-free algorithms are more preferable and cost-effective options when compared to more expensive and energy-consuming Range-based schemes.
It is the pivotal problem for sensor localization to decrease the complexity and improve precision. The localization accuracy is depended on the precision of estimated average hop-distance adopting DV-hop, because it does not measure the physical distance of nodes. Aiming at the disadvantages of less accurate in DV-hop techniques, we propose Cosine Theorem-based DV-hop localization algorithm (CTDV-hop) to improve precision.
The advantages of the CTDV-hop are listed as follows:
| • | The CTDV-hop algorithm is a Range-free technique that we only utilize the connectivity of nodes during localization |
| • | The CTDV-hop algorithm effectively improves the localization precision with low consumption |
| • | The CTDV-hop algorithm can obtain the better localization results even the nodes distribution is non-uniform |
Recently, localization technique becomes a focus of research in WSNs. Based on there need the distance information or not, there are two typical localization approaches: Range-based techniques and Range-free techniques.
Range-based localization technique: Range-based techniques need to measure precise distance or orientation between neighbor nodes. Those informations are then used to localize the remained unknown nodes by trilateration. ToA (Time of Arrival) (Girod et al., 2002), TDoA (Time Difference on Arrival) (Harter et al., 2002), AoA (Angle of Arrival) (Niculescu and Nath, 2003) and RSSI (Received Signal Strength Indicator ) (Bahl and Padmanabhan, 2000) are the popular Range-based methods.
ToA (Girod et al., 2002) measures the distance between nodes using signal propagation time. In TDoA (Harter et al., 2002), the inter-node distance is calculated based on the difference in propagation times of radio and acoustic signals originated at the same point. AoA technique locates the position by estimating and mapping relative angles between neighbors (Niculescu and Nath, 2003).
RSSI (Bahl and Padmanabhan, 2000) is one of the simplest localization methods that broadly used in many fields. It utilizes the characteristic that the energy of radio signal decreases as it propagates in space. According to the intensity of received signal, the receivers thus measure the attenuation and deduce the distance to the sender. The accuracy of RSSI measurements is highly sensitive to multipath, fading and other sources of interference, which may result in more errors.
The Range-based algorithms can obtain higher precision localization results. Unfortunately, they depend on point-to-point distance or orientation to calculate their position. In addition, they require special hardware for implementation such as GPS, which are too expensive to be implemented in large scale of WSNs.
Range-free localization algorithm: Range-free algorithms are based on connectivity information to estimate the nodes position. Compare to those expensive Range-based methods, Range-free techniques have the advantages of low consumption because there is no distance or angle measuring. They can use estimated distance instead of metrical distance for localization. After estimating the connectivity of nodes, the sensor determines its own position through varieties of methods. There are some common methods such as Centroid (Bulusu et al., 2000), DV-Hop (Nicolescu and Nath, 2001), Amorphous (Nagpal et al., 2003), MDS-MAP (Shang et al., 2003) and APIT (He et al., 2003) and so on.
Bulusu et al. (2000) proposed Centroid algorithm that localized nodes to the centroid of the proximate anchor nodes. The anchors send out beacons that include their position information to neighbor nodes at periodic intervals. The receiver infers proximity to a collection of anchors and estimates the position of the unknown node to the centroid of reference points (i.e., anchor nodes). The localization precision depends on the separate distance of adjacent reference points and the transmission range. The Centroid algorithm is completely depended on the connectivity of network. Therefore, it needs high density of anchors and can only obtain coarse-grained localization.
He et al. (2003) proposed APIT (Approximate Point in Triangle) algorithm to improve result in face of irregular radio pattern and random node placement. Unknown nodes perform their location estimating by dividing the environment into triangular regions between every three anchors nodes and test whether their positions are inside or outside those triangles. A central server to narrow down the possible area in which a target node resides then processes the information. APIT can obtain a better result even there is an irregular radio pattern and random node placement. It, however, requirements a big anchor-to-node ratio and anchor number in localization, which results high expensive cost.
ALS (Area Localization Scheme) (Chandrasekhar et al., 2006) is a centralized Range-free scheme that provides nodes location estimating within certain area, rather than the exact coordinates of the sensor. The sensors measure the lowest power level that they receive from each anchor node and forward this information with the data to the Sink for processing. The nodes in the area are computed by the server or anchors to determine their positions. Through determining the size of areas, nodes adjust the granularity of scheme by varying a number of power levels.
Niculescu and Nath proposed a distributed localization algorithm, DV-Hop (Distance Vector Hop) (Nicolescu and Nath, 2001). In the DV-Hop, anchors broadcast their location information throughout the network and each sensor keeps track of hop-counts to the other anchors. After the completion of information exchange, the average hop-distance between anchor nodes is estimated. Each sensor estimates its distance to anchors after receiving average hop-distance and corresponding hop-counts. The performance and accuracy of the DV-Hop will deteriorate if the node distribution is sparse or non-uniform. Amorphous algorithm (Nagpal et al., 2003) is improved based on the DV-Hop, which replaces the distance of nodes by the average hop-distance. The localization error is higher when there is excessive estimation of hop-distance.
Recently, there are some MDS (Multidimensional Scaling) based localization algorithms that display the structure of distance data as a geometrical picture and estimate the relative position of nodes with respect to each other. Using MDS, Medidi et al. (2006) applied complex but accurate localization algorithm to estimate the position of cluster heads. The remaining nodes can locate using cluster heads as reference nodes. MDS-MAP [8] is a centralized localization approach that locates using connectivity information. It creates a two dimensional relative map of nodes that preserves the neighborhood relationships. They all require MDS with some enhanced nodes and the accuracy is limit when the nodes are non-uniform distributed.
There are also some mobile-assisted localization techniques. Wu et al. (2006) proposed self-localization method that can dynamically satisfy with certain requirements, including monitor coverage, network connectivity or fault tolerance. However, they are too expensive to apply in WSNs. Other study focused on energy efficient pre-schedule scheme to save consumption (2007) and diverse-rate based dual energy aware scheduling scheme (2009). However, this study are wakes at localization precisions.
It is well considered that Range-free localization methods are more appropriate in hardware spending and energy consumption. Researchers regard it as a cost-effective and hopeful solution for localization in resource constrained WSNs. In this study, we focus on the investigation of Range-free localization algorithm for WSNs. The advantages of the DV-Hop are that it provides absolute coordinates and absolute orientation. It has the advantages of low cost and equips easily that does not require any additional infrastructure. The CTDV-hop algorithm proposed in this study is a Range-free technique that based on the DV-Hop.
COSINE THEOREM-BASED DV-HOP ALGORITHM
We firstly review the process of the DV-Hop algorithm and later analyze its disadvantages. We find out that exact hop-distance estimating is the key problem in localization, because the error would propagate and cause larger localization errors. Moreover, we notice that the transmission link of two nodes will bring deviation and affect the estimated results. Utilizing this characteristic, we propose a Cosine T heorem-based DV-hop (CTDV-hop) algorithm to improve the estimated value of hop-distance and hence obtain the better localization results.
Deviation of estimation in dv-hop: The DV-Hop is one of the most common Range-free schemes, which locates nodes based on Distance Vector (DV) routing. Each node keeps the minimum hops to every anchor and uses the hop-count as reference to estimate the physical distance. Once an unknown node obtains the distance and position of three or more anchors, it can estimate its own position by triangulation.
The DV-Hop algorithm is simple, but it can perform well only in dense and uniform nodes distribution WSNs. There might be occur deviation between the estimated hop-distance and the actual hop-distance when the distribution is non-uniform. The errors of result will increase when we use these estimated hop-distances for localization.
Generally, nodes are randomly deployed into the sensing area while the nodes density is not evenly. Some nodes would take a roundabout route for data transmission in this situation. The sparser nodes locate, the fewer neighbors they have and the less candidate routes they could pass. The transmission route is not the shortest path, which induces the estimation of nodes distance is shorter than their physics distances.
We present an example to describe this estimation deviation. As shown in Fig. 1, there are three anchor nodes A1, A2 and A3 (the green shadow circles), the other nodes in the sensing field are all unknown nodes (the white circles). The distance between A2 and A1 is equal to the distance between A1 and A3.
| Fig. 1: | The estimation error in non-uniform distribution |
It is obvious that there are four hops between A1 and A2, we hence estimate the average hop-distance
There are five hops from A1 to A3, we similarly obtain the average hop-distance
They need more intermediate nodes for relaying when the nodes density is sparser.
The route will make a detour in order to transmit the packets because there
are fewer candidates near the shortest path of A1 to A3.
We hence infer
These errors will propagate through all subsequent triangulation computations, which lead to useless information. The accuracy derived through triangulation depends heavily on the hop-distance in DV-Hop. Therefore, it is the key problem to decrease the estimation errors of hop-distance. Aiming at the above challenges, we propose Cosine Theorem-based DV-hop algorithm (CTDV-hop) to improve the accuracy of localization.
CTDV-hop algorithm: By observation, we find out that the angle between two anchors and the middle node is closely allied to their transmission route. This angle is almost obtuse or closes to 180° when the link is the shorter path, otherwise the angle will be smaller if they connect by a detour path.
As shown in Fig. 2, there are two routes linking the anchor A1 to A2: l1 and l2 (the pink real line and the green dashed line). The node n1 and n2 is the middle node of the route l1 and l2 respectively where their angle to the anchors in both route sides is α and β. The path l1 is closer to the straight distance |A1A2| than l2. In this situation, we will deduce α>β.
| Fig. 2: | Scenario with hop-distance deviation |
We notice that the distance of transmission path is shorter when the angle is bigger, while the distance is longer when the angle is small. It indicates that the smaller angle it is, the further path it detours. Therefore, there will lead to more deviation in estimated hop-distance. Altogether, we can obtain more accurate result when this angle is closer to 180°.
In order to provide better position estimation, we utilize this characteristic to adjust the hop-distance. According to the angle and hop-count, the average hop-distance in different transmission routes is refined. We further decrease the estimation error and obtain more exact localization results.
The CTDV-Hop algorithm is comprised of four steps.
Step 1. Initialization: Each anchor broadcasts a beacon containing its location with hop-count value to all nodes in the network. The receivers record the minimal hop-count of every anchor and flood outward to its neighbors with hop-count incremented. Through this processing, all nodes in the network know the minimal hop-count to every anchor.
Step 2. Average hop-distance estimation:After obtaining the minimal
hop-count to the other anchors, the anchor preliminary estimates the average
hop-distance
Step 3. Hop-distance adjusting: Pick the middle node and obtain the angle.
We select the transmission route with the minimal hop-count that connects to each anchor and then pick the middle node of the route (e.g., the node n in Fig. 3.a; the node n1 and n2 in Fig. 3b). We obtain the angle θ between the middle node n and the anchors both sides.
| • | Compute average hop-distance: Let k be the hop-count between two anchors, |A1A2| be the straight distance of A1 to A2, |A1n| be the distance of A1 to n and |A2n| be the distance of A2 to n. We also know |A1A2| = d, but |A2n| is unknown |
There are two different cases listed as follows according to the value of k.
| • | k is even: We let |A1n|=|A2n|
= l because the node n is the middle of the transmission route. Based
on the Cosine Theorem, we obtain the hop-distance |
| (1) |
| Fig. 3: | Angle adjusting to hop-distance, (a) k is even and (b) k is odd |
| • | k is odd: We select two middle nodes (n1
and n2) on the transmission route for correction. Likewise, we
can deduce the hop-distance |
| (2) |
| • | Computing adjusting value of hop-distance: We compute the adjusting value of hop-distance using the following formula: |
| (3) |
Hence, we correct the estimated hop-distance.
Step 4. Node localization: Having obtained the corrected hop-distance to the anchor, the unknown nodes compute their position by trilateration as same as the DV-hop algorithm.
The CTDV-hop algorithm repeats the above processes until finishes all nodes localization.
SIMULATION RESULTS
To evaluate our proposed CTDV-hop algorithm, we conduct simulation experiments in this section. Our simulation environment is set up based on Matlab. In simulation, we use Spanning Tree route and set the radio range R to 5 m. We randomly deploy 300 sensor nodes into a 100x100m square area where anchor nodes are uniformly deployed.
| Fig. 4: | Localization error, (a) uniform distribution and (b) nonuniform distribution |
We present two metrics for performance evaluating: localization error and localization coverage. We take the average results of experiments with 50 runs. Figure 4 a, b and 5 show the of the comparison localization results with different algorithms.
As illustrated in Fig. 4, the CTDV-hop algorithm achieves good performance of localization error. The localization error is smaller than some traditional Range-free algorithms (Amorphous and DV-Hop) when there have the same ratio of anchors. It can also obtain better localization results even there are fewer anchors.
With the number of anchors increasing, the average estimated hop-distance is refined. Compared to other Range-free algorithms, we highly improve the localization precision. We can achieve the better result (the localization error is almost less than 80%) while needs not mounts of anchors (n = 8).
Figure 4a shows the localization error comparison with sensors uniform distribution and Fig. 4b is the results with non-uniform distribution.
| Fig. 5: | Localization coverage |
It is shown that the performances of Amorphous and DV-Hop algorithm become worse in uniform distribution. The distribution does not affect the localization results adopting CTDV-Hop. We can also obtain well result even the sensors are non-uniform distributed.
As illustrated in Fig. 5, the localization coverage of all algorithms raises along with the number of anchors increases. From the results, we can see that the localization coverage using CTDV-hop is close to the others. It does not gain advantage in the aspect of improving localization coverage.
CONCLUSIONS
Aiming at the disadvantage of Range-free algorithms, we propose a Cosine Theorem-based DV-hop algorithm (CTDV-hop) to improve the localization precision. With the angle of transmission route assisting, the CTDV-hop decreases the estimated hop-distance. The simulation results show that it obviously improves the precision of localization results even the sensors are non-uniform distributed. It needs fewer anchors to obtain the same localization precision than the traditional Range-free algorithms. Hence, it is more suitable to the practical applications of WSNs.
However, the CTDV-hop is deficient at improving localization coverage. In addition, the localization result is not accurate to the nodes nearby the anchors. In conclusion, localization technique is a promising and useful field of WSNs with new algorithms, hardware and applications. In the future, we need to focus on more accurate, effective and lightweight Range-free localization algorithms.
ACKNOWLEDGMENTS
This study is fully sponsored by Scientific and Technological Innovation Project of Hunan Transportation Department (No. 200724).