Four Anchor Sensor Nodes Based Localization Algorithm over Three-Dimensional Space

  • cc icon
  • 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.


  • KEYWORD

    Localization , Received signal strength indicator , Three-dimensional space , Wireless sensor network

  • 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].

    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:

    image

    The equations are converted to linear equations by subtraction and substitution.

    image

    where

    image

    In 2D space the position of (x, y) is obtained by solving the following matrix operations:

    image

    where

    image

    and

    image

    are referred to (xixj) and (yiyj), respectively. In 3D space, through the common procedure of 2D trilateration (2DT), the following equations are obtained

    image

    where

    image

    In 3D space, the position of (x, y, z) can be calculated by solving the following matrix equations.

    image
    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

    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:

    image

    Where d = r is the distance between the target and the virtual reference node A1=((x1),(y1),(z1)). The height and distance are calculated using following equations:

    image

    where

    image

    After estimating the distance of all SAs, the targets’ position of (x, y) are determined by calculating the following equations, the regular 2DT.

    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.

    image

    Where

    image

    The equations are converted to linear equations with subtraction and substitution.

    image

    where

    image

    The position of (x, y) is obtained by solving the following matrix equations.

    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:

    image

    where

    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

    where

    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:

    image

    in 2D and

    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:

    image

    where

    image
    image
    image

    where

    image
    image

    where

    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:

    image
    image

    where

    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.

    image

    where

    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. 7a 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. 7b 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. 8a). 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.

      >  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:

    image

    We found that solving the 2×2 matrix takes 20m + 2d + 18a, 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 49m + 3d + 45a. 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 53m + 9d + 39a + 3q 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 34m + 3d + 32a + 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.

  • 1. Schiller J. H., Voisard A. 2004 Location-Based Services google
  • 2. 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] P.72-82 google
  • 3. 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] P.1293-1303 google
  • 4. 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] P.193-197 google
  • 5. 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] P.24-32 google
  • 6. 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] Vol.1 P.60-72 google
  • 7. 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] Vol.6536 P.209-220 google
  • 8. 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] P.1-3 google
  • 9. Karalar T. C., Rabaey J. 2006 “An RF ToF based ranging implementation for sensor networks” [in Proceedings of the IEEE International Conference on Communications] P.3347-3352 google
  • 10. 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] Vol.22 P.70-84 google
  • 11. 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] P.105-111 google
  • 12. 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] P.239-246 google
  • 13. Rappaport T. S. 2002 Wireless Communications: Principles and Practice google
  • 14. 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] P.1213-1218 google
  • 15. Ypma T. J. 1995 “Historical development of the Newton-Raphson method” [SIAM Review] Vol.37 P.531-551 google
  • [Fig. 1.] (a) Two-dimensional trilateration and (b) three-dimensional trilateration.
    (a) Two-dimensional trilateration and (b) three-dimensional trilateration.
  • [Fig. 2.] The complexity-reduced three-dimensional trilateration localization approach.
    The complexity-reduced three-dimensional trilateration localization approach.
  • [Fig. 3.] The four anchor sensor nodes based localization algorithm over three-dimensional space (FAST) approach.
    The four anchor sensor nodes based localization algorithm over three-dimensional space (FAST) approach.
  • [Fig. 4.] (a) Relationship between height and distance and (b) conversion of three-dimensional to two-dimensional.
    (a) Relationship between height and distance and (b) conversion of three-dimensional to two-dimensional.
  • [Fig. 5.] Height estimation using the ground anchor node and another node.
    Height estimation using the ground anchor node and another node.
  • [Fig. 6.] The received signal strength indicator and standard deviation depending on distance.
    The received signal strength indicator and standard deviation depending on distance.
  • [Fig. 7.] Distance error of three-dimensional (3D) trilateration method (a) and complexity-reduced 3D trilateration localization approach method (b).
    Distance error of three-dimensional (3D) trilateration method (a) and complexity-reduced 3D trilateration localization approach method (b).
  • [Fig. 8.] Distance error of the FAST method for the ground node (a) and sensor node in the first group (b).
    Distance error of the FAST method for the ground node (a) and sensor node in the first group (b).