Four Anchor Sensor Nodes Based Localization Algorithm over ThreeDimensional Space
 Author: Seo Hwajeong, Kim Howon
 Organization: Seo Hwajeong; Kim Howon
 Publish: Journal of information and communication convergence engineering Volume 10, Issue4, p349~358, 31 Dec 2012

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 threedimensional (3D) space. Recently, the complexityreduced 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 , Threedimensional 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 locationbased 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 twodimensional (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 lightcomputational cost algorithm. A previous method, the complexityreduced 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 rangefree and rangebased methods. Rangefree schemes do not utilize the any range measurements.
A rangefree 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 rangefree localization scheme for 3D WSNs is proposed by Mishra and Gore [7]. The procedure not only helps sensor nodes to selflocalize, but it is also able to verify the estimated location and reestimate it, if it is needed. The sensor nodes calculate their positions based on GPS location information from anchor nodes.
In contrast to rangefree schemes, rangebased techniques use information on the absolute range and angle estimates. For this reason, rangebased schemes are more accurate than rangefree 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 radiofrequency wave incident on an antenna array [11].
Landscape3D 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 zaxis. 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].
where
n is a signal propagation constant or exponent,d is a distance from sender, andA 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. RSSIBASED 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:
The equations are converted to linear equations by subtraction and substitution.
where
In 2D space the position of (x, y) is obtained by solving the following matrix operations:
where
and
are referred to (
x_{i} ？x_{j} ) and (y_{i} ？y_{j} ), respectively. In 3D space, through the common procedure of 2D trilateration (2DT), the following equations are obtainedwhere
In 3D space, the position of (x, y, z) can be calculated by solving the following matrix equations.
> B. ComplexityReduced 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 heightsh_{1} ,h_{2} with the Pythagorean theorem and trigonometry functions in the following equations:Where
d =r is the distance between the target and the virtual reference node A_{1}=((x _{1}),(y _{1}),(z _{1})). The height and distance are calculated using following equations:where
After estimating the distance of all SAs, the targets’ position of (x, y) are determined by calculating the following equations, the regular 2DT.
IV. THE FAST APPROACH
In this paper, we propose a novel approach of localization over 3D space. The four anchor sensor nodebased 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, (
A_{1} ,A_{2} ,A_{3} ), equipped with different (x, y) positions and equal heights. The second group consists of the other node,A_{d} .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.
Where
The equations are converted to linear equations with subtraction and substitution.
where
The position of (x, y) is obtained by solving the following matrix equations.
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
d_{g} and the other noded_{1} 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:
where
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
V. EVALUATION
> A. Accuracy
In this section, we analyze the accuracy of estimation depending on the measurement error; RSSIbased 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:
in 2D and
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 Δd_{i} on estimated distanced_{i} between the target and anchor node. Following are the mathematically estimated error expressions:where
where
where
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 zaxis and then using the zaxis location, the xand yaxis are determined. The error in the distance estimation of coordination of the zaxis is determined by the error in the distance of the two anchor nodes with a common SA. Coordination of the x and yaxis 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:
where
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 yaxis are estimated and then using this information, the zaxis is determined. Accuracy in the x and yaxis is determined by the three nodes with their height in common and that for the zaxis is determined by two nodes, one for ground node and one for the other. The estimate errors are mathematically expressed as follows.
where
> 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 yaxis with same parameter, so their error graphs have similar shapes. The zaxis 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 zaxis 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 zaxis 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:
We found that solving the 2×2 matrix takes 20
m + 2d + 18a , wherem ,d , anda 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 yaxis positions based on the height and distance estimation. However, it computes the x and yaxis positions with a computational cost in 2DT. It consumes many computational resources and is even required to compute the squaring operation when estimating the zaxis position. As a result, its computation time takes 53
m + 9d + 39a + 3q and has no advantage for localizing the node over 3D space compared to 3DT, whereq 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 + 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 yaxis 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 predeployed 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.

[Fig. 1.] (a) Twodimensional trilateration and (b) threedimensional trilateration.

[Fig. 2.] The complexityreduced threedimensional trilateration localization approach.

[Fig. 3.] The four anchor sensor nodes based localization algorithm over threedimensional space (FAST) approach.

[Fig. 4.] (a) Relationship between height and distance and (b) conversion of threedimensional to twodimensional.

[Fig. 5.] Height estimation using the ground anchor node and another node.

[Fig. 6.] The received signal strength indicator and standard deviation depending on distance.

[Fig. 7.] Distance error of threedimensional (3D) trilateration method (a) and complexityreduced 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).