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 
which bring the estimation deviation in the hop-distance and localization errors.
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 
the same as the traditional DV-hop.
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 |
|
| 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
|
| • |
Computing adjusting value of hop-distance: We compute
the adjusting value of hop-distance using the following formula: |
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).
Subscribe Today
