Advanced
Four Anchor Sensor Nodes Based Localization Algorithm over Three-Dimensional Space
Four Anchor Sensor Nodes Based Localization Algorithm over Three-Dimensional Space
Journal of Information and Communication Convergence Engineering. 2012. Dec, 10(4): 349-358
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/li-censes/bync/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : June 07, 2012
  • Accepted : July 09, 2012
  • Published : December 31, 2012
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hwajeong Seo
Howon Kim
howonkim@pusan.ac.kr

Abstract
Over a wireless sensor network (WSN), accurate localization of sensor nodes is an important factor in enhancing the association between location information and sensory data. There are many research works on the development of a localization algorithm over three-dimensional (3D) space. Recently, the complexity-reduced 3D trilateration localization approach (COLA), simplifying the 3D computational overhead to 2D trilateration, was proposed. The method provides proper accuracy of location, but it has a high computational cost. Considering practical applications over resource constrained devices, it is necessary to strike a balance between accuracy and computational cost. In this paper, we present a novel 3D localization method based on the received signal strength indicator (RSSI) values of four anchor nodes, which are deployed in the initial setup process. This method provides accurate location estimation results with a reduced computational cost and a smaller number of anchor nodes.
Keywords
I. INTRODUCTION
Sensor networks are an emerging field for ubiquitous environments such as surveillance, environmental monitorring, home automation, and health care systems. These applications utilize sensory data together with knowledge of location information for location-based services or authentication algorithms [1 , 2] . Moreover, the location information determines the deployment strategies in mobile sensor networks [3 , 4] . When mobile sensors are densely or spatially deployed in a field, to enlarge the coverage of the sensing area and efficiency of communication, the initially deployed nodes should be replaced.
To provide accurate location information, many localization algorithms have been proposed over two-dimensional (2D) space, but in reality, sensor nodes are deployed in the 3D space. For this reason, our research has focused on 3D space and has also considered the light-computational cost algorithm. A previous method, the complexity-reduced 3D trilateration localization approach (COLA), [5] computes the localization using six anchor sensor nodes and simplifies the 3D computational overhead to 2D trilateration.
However, the COLA method has made little progress in reducing computational cost and can even increase the number of anchor nodes. For this reason, we need to adapt a more efficient and lightweight method for wireless sensor network (WSN) environments.
In this paper, we propose a localization algorithm based on four anchor nodes using the received signal strength indicator (RSSI). Among the four anchor nodes, three nodes are placed at equal height and the other node is deployed on the ground. This method reduces the complexity over 3D localization to 2D localization and enhances the accuracy of the information.
This paper is organized as follows: In Section II, we introduce the formulas for distance estimation using RSSI and overview the related research on node localization in WSNs. In Section III, we introduce the complexity of 2D and 3D trilateration techniques and COLA. The details of our FAST approach are described in Section IV, and we evaluate the performance of the proposal compared with others in Section V. Finally, the conclusion is drawn in Section VI.
II. RELATED WORK
- A. Localization Algorithms
Localization algorithms are classified into range-free and range-based methods. Range-free schemes do not utilize the any range measurements.
A range-free localization scheme for 3D WSNs is proposed by Yadav et al. [6] . This scheme is utilized with mobile and static sensor nodes. Mobile sensors equipped with global positioning system (GPS) periodically broadcast beacon messages about their location. When static sensor nodes enter the communication range of any mobile node, the static nodes calculate their individual position based on the equation of a sphere.
Another range-free localization scheme for 3D WSNs is proposed by Mishra and Gore [7] . The procedure not only helps sensor nodes to self-localize, but it is also able to verify the estimated location and re-estimate it, if it is needed. The sensor nodes calculate their positions based on GPS location information from anchor nodes.
In contrast to range-free schemes, range-based techniques use information on the absolute range and angle estimates. For this reason, range-based schemes are more accurate than range-free schemes. Location estimation is computed using the following methods: received signal strength (RSS) is measured in each received packet, which can be quantized into the RSSI. The information presents the distance between the source and destination nodes because RSS is reduced as the distance increases. The drawback of RSS is irregular signal propagation and multipath fading causing inaccuracy in range estimation [8] .
Time of arrival (TOA) exploits the signal propagation time between the source and destination nodes. The drawback of TOA is the necessity of high clock resolution. The transmitter and recipient are required to synchronize the clock, which caused much more overhead than the other methods [9] .
The time difference of arrival (TDOA) approach uses the arrival time of a signal obtained from at least three nodes. The difference in the signal arrival information determines the source location [10] .
Angle of arrival (AoA) measurement is a method for determining the direction of propagation of a radio-frequency wave incident on an antenna array [11] .
Landscape-3D is proposed in [12] , introducing the concept of mobile location assistants that are aware of their moving positions through GPS information. A locationunaware node can estimate its own location based on RSSI.
COLA is proposed in [7] to lower the complexity by reducing 3D trilateration to 2D trilateration through the use of super anchor nodes—ones with pairwise positions whose coordinates only differ in the z-axis. This technique attempted to reduce the computational cost by using a typical 2D trilateration for 3D trilateration.
- B. Distance Estimation Using RSSI
Most of the currently available transceivers use RSSI to estimate the signal power at the receiving antenna [13] . From RSSI, we can also estimate the distance among transceivers because it regularly decreases as the distance widens.
Thefollowingis the formula for finding the RSSI value [14] .
PPT Slide
Lager Image
where n is a signal propagation constant or exponent, d is a distance from sender, and A is a received signal strength at 1 m distance.
The information about a distance can be determined with a formula. Using Formula 2, the distance between each node is accurately estimated.
III. RSSI-BASED 3D TRILATERATION VERSUS COLA
- A. 2D and 3D Trilateration
In this section, we explore the existing localization algorithm by analyzing the fundamental concept of the trilateration techniques in 2D and 3D spaces. The position of the sensor node in 2D space can be obtained by solving the following equations:
PPT Slide
Lager Image
The equations are converted to linear equations by subtraction and substitution.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
In 2D space the position of (x, y) is obtained by solving the following matrix operations:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are referred to ( xi xj ) and ( yi yj ), respectively. In 3D space, through the common procedure of 2D trilateration (2DT), the following equations are obtained
PPT Slide
Lager Image
where
PPT Slide
Lager Image
In 3D space, the position of (x, y, z) can be calculated by solving the following matrix equations.
PPT Slide
Lager Image
PPT Slide
Lager Image
- B. Complexity-Reduced 3D Trilateration Localization Approach (COLA)
In the COLA approach, a set of super anchor (SA) nodes are utilized for range estimation. Each SA is equipped with
PPT Slide
Lager Image
(a) Two-dimensional trilateration and (b) three-dimensional trilateration.
PPT Slide
Lager Image
The complexity-reduced three-dimensional trilateration localization approach.
with two positions that are only different in height. The SA can be constructed by equipping it with two transceivers and two antennas of different heights.
The first step of the COLA approach is to estimate the distance between the SAs and the target. The next step is to identify the height of the target’s position h in 3D space using the SAs’ two different heights h1 , h2 with the Pythagorean theorem and trigonometry functions in the following equations:
PPT Slide
Lager Image
Where d = r is the distance between the target and the virtual reference node à 1 =(( x 1 ),( y 1 ),( z 1 )). The height and distance are calculated using following equations:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
The four anchor sensor nodes based localization algorithm over three-dimensional space (FAST) approach.
After estimating the distance of all SAs, the targets’ position of (x, y) are determined by calculating the following equations, the regular 2DT.
PPT Slide
Lager Image
IV. THE FAST APPROACH
In this paper, we propose a novel approach of localization over 3D space. The four anchor sensor node-based localization algorithm over 3D space (FAST) is efficient in terms of the number of anchor nodes and computation complexity and also presents sufficient accuracy. The FAST approach in Fig. 3 uses four anchor nodes composed of two groups. The first group consists of three anchor nodes, ( A1 , A2 , A3 ), equipped with different (x, y) positions and equal heights. The second group consists of the other node, Ad .The node is installed at the bottom of the space.
The first step of our approach is to estimate the distance between the target and anchor nodes. The next step is identifying the target’s position of (x, y) based on the estimated distance. To reduce the 3D complexity to 2D space, we first simplify the problem using the Pythagorean theorem. In Fig. 4 , the relationship of the estimated distance and location are illustrated.
Therefore, we can estimate the (x, y) position with a simple calculation. The estimation is calculated by performing regular 2DT, with the following system of equations.
PPT Slide
Lager Image
Where
PPT Slide
Lager Image
The equations are converted to linear equations with subtraction and substitution.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
The position of (x, y) is obtained by solving the following matrix equations.
PPT Slide
Lager Image
(a) Relationship between height and distance and (b) conversion of three-dimensional to two-dimensional.
PPT Slide
Lager Image
After the position of (x, y) is estimated, the final step of FAST is to estimate the height of the target. The target’s position is calculated using the distance of the ground anchor node dg and the other node d1 and the quadratic equation. In Fig. 5 , the height estimation is illustrated.
The height of the sensor node can be obtained by solving the following equations:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
The equations are converted to a quadratic equation by subtraction and substitution. The height is obtained by solving the following quadratic equation.
  • ε⋅ z2− 2⋅μ⋅ z +σ= 0
PPT Slide
Lager Image
Height estimation using the ground anchor node and another node.
where
PPT Slide
Lager Image
V. EVALUATION
- A. Accuracy
In this section, we analyze the accuracy of estimation depending on the measurement error; RSSI-based range estimation shows inaccurate estimation, so it should be able to tolerate the measurement error. The accuracy of the localization algorithm is expressed as follows:
PPT Slide
Lager Image
in 2D and
PPT Slide
Lager Image
in 3D show the error expression and Δ x , Δ y , Δ z denote the estimated errors on the target’s coordinates at the x, y, and z axes, respectively. Fig. 6 shows the RSSI and standard deviation depending on the distance. As the distance increases between the recipient and sender, the RSSI decreases because signal interruption and signal attenuation increase. The standard deviation fluctuates from three to six. Therefore, the localization algorithm should be tolerant to the standard deviation.
- 1) 3DT
Δ x , Δ y , Δ z are estimated using error Δ di on estimated distance di between the target and anchor node. Following are the mathematically estimated error expressions:
PPT Slide
Lager Image
PPT Slide
Lager Image
The received signal strength indicator and standard deviation depending on distance.
where
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
- 2) COLA
The COLA approach has a different level of accuracy compared to the previous 3DT, because the location estimation procedure is different. The COLA approach first estimates the z-axis and then using the z-axis location, the xand y-axis are determined. The error in the distance estimation of coordination of the z-axis is determined by the error in the distance of the two anchor nodes with a common SA. Coordination of the x- and y-axis are determined by all of the anchor nodes’ distance estimation because to convert the 3D space to 2D space, COLA uses the anchor and reference nodes’ estimation and then on 2D space COLA uses the x, y location of SAs. The estimate errors are mathematically expressed as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
- 3) FAST
The error in the distance for the FAST method is estimated using the opposite procedure from that of COLA. In FAST, the distances on the x- and y-axis are estimated and then using this information, the z-axis is determined. Accuracy in the x- and y-axis is determined by the three nodes with their height in common and that for the z-axis is determined by two nodes, one for ground node and one for the other. The estimate errors are mathematically expressed as follows.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
- B. Experimental Results
In this section, we compare the methods for distance estimation accuracy. In Fig. 6 , it is shown that the RSSI value contains errors that ranged from 3 to 6, so localization algorithm needs to have resilience against RSSI errors.
Fig. 7 a shows results for the accuracy in 3DT. In this case, the three axes have a similar distance estimation error, because their positions are obtained by solving the matrix using the three axes values together.
Fig. 7 b contains the results of the COLA method. The method calculates the x- and y-axis with same parameter, so their error graphs have similar shapes. The z-axis is obtained by two nodes in the SA using the x, y position and it increases the distance error arithmetically as the RSSI error increases. Fig. 8 illustrates the result of the FAST method depending on each node.
In case of the ground node, the x and y positions are not changed by the RSSI error, but the z position fluctuates with a wide gap as the RSSI error increases (the z-axis and average distance error are the same value so their plots overlaps in Fig. 8 a). In the case of the sensor node in the first group, the x and y positions maintain a sufficient accuracy rate, but the z position has a wide error gap because the distance estimation error of the sensor’s x and y positions affects the z-axis in accuracy. Even though the error rates are larger than with other methods, the FAST method is the proper localization because the standard deviation of the RSSI presents between three and six value, that is, within the range, and our method also presents a sufficiently small error rate.
PPT Slide
Lager Image
Distance error of three-dimensional (3D) trilateration method (a) and complexity-reduced 3D trilateration localization approach method (b).
PPT Slide
Lager Image
Distance error of the FAST method for the ground node (a) and sensor node in the first group (b).
- C. Computational Cost
- 1) 2DT versus 3DT
We show the computational cost that is required by 2DT and 3DT. To solve the 3×3 matrix, we use Cramer’s rule with the following expressions:
PPT Slide
Lager Image
We found that solving the 2×2 matrix takes 20 m + 2 d + 18 a , where m , d , and a are the computational cost for multiplication, division, and addition. We also assume that an addition operation equals a subtraction operation in terms of computation time. When solving the 3×3 matrix, it takes 49 m + 3 d + 45 a . Comparing both methods, 3DT has more overhead than 2DT.
- 2) COLA
The COLA method proposes a lightweight localization algorithm whose calculation process comprises three sections. One is solving the height of the destination. Another is estimation of the distance between the anchor nodes and the destination node. The other is calculating the x- and y-axis positions based on the height and distance estimation. However, it computes the x- and y-axis positions with a computational cost in 2DT. It consumes many computational resources and is even required to compute the squaring operation when estimating the z-axis position. As a result, its computation time takes 53 m + 9 d + 39 a + 3 q and has no advantage for localizing the node over 3D space compared to 3DT, where q is the squaring operation.
- 3) Our Proposed Approach
Our proposal decreases the computational cost and has the same number of anchor nodes as 3DT. In implementation of 3DT, it is required to deploy the 4 anchor nodes. In the case of the COLA method, dispatching the 6 anchor nodes is needed. Our proposal utilizes the 4 anchor nodes and costs to compute the localization of 3D space with 34 m + 3 d + 32 a + q (the squaring and division operation have the same complexity as multiplication using Newton’s method). The proposal implies the nature of 2DT when calculating the x- and y-axis positions, whose computation costs is equal to that of 2DT. To estimate the zaxis, a simple equation is calculated using information on the distance between two anchor nodes and the destination node.
VI. CONCLUSIONS
This paper presented a 3D localization algorithm for a resource constrained device. We adapted existing localization techniques together with pre-deployed four anchor nodes comprising three nodes that have equal height and the other on the ground, which can measure the location information based on RSSI. The approach has lower computation costs and uses a small number of anchor nodes compared to a previous method (COLA). It also produces accurate localization results over3D space.
Acknowledgements
This work was supported by a National Research Foundation of Korea (NRF) grant (No. 2010-0026621) funded by the Korea government (MEST).
References
Schiller J. H. , Voisard A. 2004 Location-Based Services Morgan Kaufmann Publishers San Francisco, CA
Liu D. , Ning P. 2003 “Location-based pairwise key establishments for static sensor networks” in Proceedings of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks Fairfax: VA 72 - 82
Zou Y. , Chakrabarty K. 2003 “Sensor deployment and target localization based on virtual forces” in Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications 1293 - 1303
Yoo Y. , Agrawal D. P. 2008 “Mobile sensor relocation to prolong the lifetime of wireless sensor networks” in Proceedings of the IEEE Vehicular Technology Conference Singapore 193 - 197
Shih C. Y. , Marron P. J. 2010 “COLA: complexity-reduced trilateration approach for 3D localization in wireless sensor networks” in Proceedings of the 4th International Conference on Sensor Technologies and Applications Venice, Italy 24 - 32
Yadav V. , Mishra M. K. , Sngh A. K. , Gore M. M. 2009 “Localization scheme for three dimensional wireless sensor networks using GPS enabled mobile sensor nodes” International Journal of Next-Generation Networks 1 (1) 60 - 72
Mishra M. K. , Gore M. M. 2011 “Robust and distributed range-free localization using anchor nodes with varying communication range for three dimensional wireless sensor networks” Distributed Computing and Internet Technology, Lecture Notes in Computer Science 6536 209 - 220
Wu R. H. , Lee Y. H. , Tseng H. W. , Jan Y. G. , Chuang M. H. 2008 “Study of characteristics of RSSI signal” in Proceedings of the IEEE International Conference on Industrial Technology Chengdu, China 1 - 3
Karalar T. C. , Rabaey J. 2006 “An RF ToF based ranging implementation for sensor networks” in Proceedings of the IEEE International Conference on Communications Istanbul, Turkey 3347 - 3352
Gezici S. , Tian Z. , Giannakis G. B. , Kobayashi H. , Molisch A. F. , Poor H. V. , Sahinoglu Z. 2005 “Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks” IEEE Signal Processing Magazine 22 (4) 70 - 84
Nasipuri A. , Li K. 2002 “A directionality based location discovery scheme for wireless sensor networks” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications Atlanta: GA 105 - 111
Zhang L. , Zhou X. , Cheng Q. 2006 “Landscape-3D: a robust localization scheme for sensor networks over complex 3D terrains” in Proceedings of the 31st IEEE Conference on Local Computer Networks Tampa: FL 239 - 246
Rappaport T. S. 2002 Wireless Communications: Principles and Practice 2nd ed. Prentice Hall Upper Saddle River, NJ
Lau E. E. L. , Chung W. Y. 2007 “Enhanced RSSI-based real-time user location tracking system for indoor and outdoor environments” in Proceedings of the International Conference on Convergence Information Technology Gyeongju, Korea 1213 - 1218
Ypma T. J. 1995 “Historical development of the Newton-Raphson method” SIAM Review 37 (4) 531 - 551