Non-Line-of-Sight Beacon Identification for Sensor Localization

Abstract

In recent years, sensors are often deployed to sense the target environment. Besides the sensed environmental information, sensor's position information itself is very important in most cases. With the increasing number of sensors, automatic sensor localization becomes necessary. For accurately localizing sensors, line of sight between nodes and beacons is often required. However, in many cases, it is very difficult to ensure that every beacon has the line of sight to a target sensor node. In this paper, a non-line-of-sight beacon identification approach is proposed. With which, the beacons that have no line of sight to a target sensor can be found out and then ruled out, thus the final localization result can be rectified and the accuracy can be improved. Simulations are conducted, and results show that non-line-of-sight beacons can be identified effectively. The proposed approach will be helpful in the real sensor localization in sensor networks, especially for the systems that beacons are sparsely deployed.

1. Introduction

Nowadays, wireless sensor networks are often applied to build sensing systems for Structural Health Monitoring (SHM). For instance, Yu et al. developed a wireless MEMS inclination sensor system for monitoring large-scale hook structures [1]. There is no doubt that embedded sensor network systems are always coupled to the physical world. Besides the sensed information, sensor's position information itself is very important for Structural Health Monitoring. At one hand, people try to find the best, and optimal positions for deploying sensors; so that fewer sensors are needed but still can assure sound monitoring result [2–4]. While at the other hand, with the decreasing of sensors’ prices nowadays, people tend to deploy more sensors so that they can deploy them more freely [5]. In this case, sensors are often localized after the deployment rather than before the deployment. However, with the increasing number of the deployed sensors, manual localization is not any longer practical. Automatic sensor localization becomes necessary and is needed to be developed.

In localization systems, sensors can be either localized using the ranging-free approach using only the proximity information such as Centroid algorithm [6], DV-Hop propagation method [7], and so on, or using the ranging-based approach such as lateration [8] in which sensors are localized using the distance-based scheme using several fixed beacons. A beacon means a node whose position is already known so that it can be used as the reference point. Triangle rule is applied to determine the sensor position. However, this approach requires precise distances between sensors and beacons. Hence, line of sight between nodes and beacons is necessary to ensure the localization correctness. However, in many cases, it is very difficult to ensure that every beacon has the line of sight to a target sensor node, which will consequently make the distances overestimated for those beacons that have nonline of sight to the sensor node. Here, nonline of sight means that the receiver will receive the signal after being reflected, refracted, or diffracted instead of receiving the direct path signal. Hence, if a beacon has no line of sight, the distance between the beacon and a receiver will become much larger than its direct path. In this case, the final localization results will definitely been distorted. In this paper, a non-line-of-sight beacon identification approach is proposed. With which, the beacons who have no line of sight to a target sensor can be found out and then ruled out, thus the final result can be rectified and the accuracy can be improved. The proposed method will be helpful in the real sensor localization in sensor networks, especially for the system that beacons are sparsely deployed.

2. Distance-Based Sensor Localization

For localization systems, generally speaking, two kinds of schemes can be used, that is, range-based localization scheme which uses absolute point-to-point distance estimates or angle estimates for calculating location and range-free localization scheme which uses only the connectivity and proximity. Usually, lateration is often applied to locate a node with distance estimates from a sensor node to several fixed beacons. Figure 1 shows a two-dimensional lateration with three beacons.

Figure 1

Two-dimensional lateration.

For a three-dimensional localization problem, four beacons not in a same plane are usually required, as shown in Figure 2, and the following equations stand:

$$\begin{array}{cc}& {\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}+{\left(z-z_i\right)}^{\mathrm{2}}=d_i^2\hspace{1em}i=\mathrm{1,2},\mathrm{3,4},\end{array}$$ (1)

where ( $x,y,z$ ) are the coordinates of an unknown node; ( $x_i,y_i,z_i$ ) are the coordinates of the ith beacon $\text{B}i$ ; and $d_i$ is the distance between the beacon and a unknown node. Equation (1) can be rewritten to be

$$\begin{array}{cc}& x{x}_i+y{y}_i+z{z}_i=\frac{r^{\mathrm{2}}+r_i^2-d_i^2}{2},\hspace{1em}i=\mathrm{1,2},\mathrm{3,4},\end{array}$$ (2)

where r and $r_i$ represent the distance of the unknown node and the ith beacon $\text{B}i$ to the origin of coordinates, respectively, which can be expressed as

$$\begin{array}{cc}& r^{\mathrm{2}}=x^{\mathrm{2}}+y^{\mathrm{2}}+z^{\mathrm{2}},\\ r_i^2=x_i^2+y_i^2+z_i^2.\end{array}$$ (3)

Figure 2

Three-dimensional localization.

The effect of beacon deployment on the localization was studied, and a projection method was proposed and applied to enable the beacons to be deployed at one plane [5, 9]. The projection method can be shown in Figure 3. With which, only three beacons are required to locate a node in a three-dimensional space. Usually localizing a node in a three-dimensional space requires four beacons which are not in a same plane. However, if the beacons are deployed at the same plane, there will be two possible solutions (positions), which lie in two sides of the beacon plane. Therefore, if we can determine at first which side the node will be at the beacon plane, then the node position can be uniquely and correctly determined [5]. Our simulations also showed that deploying the beacons around the node will improve its localization accuracy. Expanding the beacon span can also decrease the localization error to some extent. The most important advantage is that the projection method can allow the beacons to be deployed at one plane while the localization accuracy is not nearly deteriorated.

Figure 3

Projection method.

3. Localization with Non-Line-of-Sight Beacon Included

In sensor localization, sensing directivity of both receiver and transmitter is another important issue. It is always an important effect on the localization accuracy. This is proved by the MIT Cricket experiments that the distance measurement accuracy is good only when the receiver has a very small angle to the transmitter [10]. Otherwise, error increases significantly. This is due to the fact that the gain of both of the receiver and transmitter dramatically drops when the angle increases. For this consideration, it seems that in a beacon grid as shown in Figure 4, it is better to use only the nearest beacon which covers the target node, because they can often guarantee relative small angles to the receiver which in turn provides good distance estimates.

Figure 4

The nearest beacon in a beacon grid to a target node.

With the projection method, three beacons are enough to build up a three-dimensional lateration as shown in Figure 5. If we know the distances from the node to the three beacons, then the possible position will be at the crossing point of the three-spherical surfaces. After we project this three-dimensional lateration into the beacon plane (the plane built by the three beacons), then it can be degraded into a two-lateration problem. In order to identify the non-line-of-sight beacons, the beacon grid should be deployed into a rectangle grid. Thus for the four nearest beacons to a node, say, B1, B2, B3, and B4, they should be on the vertices of a rectangle.

Figure 5

Three-dimensional lateration.

Figure 6 shows the projected figure with beacons B1, B2, and B3. From the figure, we can see that every two circles will generate a line according to their common points. Three beacons will totally generate 3 of such lines, that is, line $l_{\mathrm{12}}$ , $l_{\mathrm{23}}$ , and $l_{\mathrm{13}}$ . These 3 lines will definitely pass the point c which is just the projected point of the node. If beacon B3 has no line of sight resulting in overestimating the distance, the projected radius to beacon B3 will be enlarged. In Figure 6, the dashed line circle is the biased circle indicating the enlarged measured distance. Since circle B1 and circle B2 are not changed, $l_{\mathrm{12}}$ remains unchanged, while $l_{\mathrm{23}}$ and $l_{\mathrm{13}}$ are moved to the $l_{\mathrm{23}}^{\prime }$ and $l_{\mathrm{13}}^{\prime }$ , the crossing point c is also moved to $c\prime$ . In fact, as we know, in a two-dimensional plane, two lines are enough to determine a point. To determine the projected point c, we only need to examine the lines $l_{\mathrm{12}}$ and $l_{\mathrm{23}}$ for their convenience. Because line $l_{\mathrm{12}}$ is kept unchanged, the possible projected point c can only move along the line $l_{\mathrm{12}}$ . In this case, if beacon B3 has no line of sight, then only y value of the node will be changed while there will be no effect on its x value. Vice versa, the nonline of sight of the beacon B1 will only affect the node's x value but will have no effect on its y value. From the mathematical view, since beacons B1 and B2 are at the x-axis and the line B2B3 is parallel to y-axis, node's position can be found to be

$$\begin{array}{cc}& x=\frac{r_2^2-r_1^2-d_2^2+d_1^2}{\mathrm{2}\left(x_2-x_{\mathrm{1}}\right)},\\ y=\frac{r_3^2-r_2^2-d_3^2+d_2^2}{\mathrm{2}\left(y_3-y_{\mathrm{2}}\right)}.\end{array}$$ (4)

Suppose the measurement error of $d_{\mathrm{3}}$ is e, then the y error of the localization result is

$$\begin{array}{cc}& {\epsilon }_y=-\frac{d_{\mathrm{3}}\cdot e}{y_3-y_{\mathrm{2}}}-\frac{e^{\mathrm{2}}}{\mathrm{2}\left(y_3-y_{\mathrm{2}}\right)}.\end{array}$$ (5)

If the distance measurement error e is much smaller than $d_{\mathrm{3}}$ , then (5) can be approximately estimated to be

$$\begin{array}{cc}& {\epsilon }_y\approx c_{\mathrm{0}}\cdot e,\end{array}$$ (6)

where

$$\begin{array}{cc}& c_{\mathrm{0}}=-\frac{d_{\mathrm{3}}}{y_3-y_{\mathrm{2}}}.\end{array}$$ (7)

Figure 6

Projected figure with beacon B3 has nonline of sight.

4. Non-Line-of-Sight Beacon Identification

As shown in Figure 7, four beacons, deployed at the vertices of 4 angles of a rectangle, are used to locate a node. These four beacons can combine four triangles. Localization can be executed by every triangle with the projection method. Without losing generality, if beacon B3 is assumed to have no line of sight, it will not affect the triangle B1B2B4, but will affect all the other triangles. With every triangle, a position estimate can be obtained. So totally 4 position estimates can be gotten. If we examine the position domain, we can determine the non-line-of-sight beacons according to their position distribution.

Figure 7

Localization with identifying non-line-of-sight beacon.

In Figure 7(b), the grey area indicates the possible right position with line of sight. The size of the grey area is determined by the reasonable localization error. When B3 is blocked, which results in a large positive measurement error, the position result P134 determined by triangle B1B3B4 will have a big y error and P123 will have a big x error, while P124 will fall into the grey area. With this kind of position distribution, we can determine exactly which beacon has non line of-sight. Here, we neglect triangle B2B3B4 because both of its x and y errors are very large. As the nonline of sight of beacon B3 only leads to big error on y error of P134 and x error of P123, we get rid of these two values in order to get a correct answer. Thus, the node's position can be rectified to be as

$$\begin{array}{cc}& x=\frac{x_{P\mathrm{124}}+x_{P\mathrm{134}}}{\mathrm{2}},\\ y=\frac{y_{P\mathrm{124}}+y_{P\mathrm{123}}}{\mathrm{2}}.\end{array}$$ (8)

On the whole, the whole approach contains next 4 steps.

• (i)

  Determine four beacons which are at the four vertices of a rectangle which covers a target node.

• (ii)

  Separate the four beacons into four groups with each containing three beacons and executing localization procedure.

• (iii)

  Study the position distribution and determine the non-line-of-sight beacon.

• (iv)

  Rule out the wrong effect and rectify the result.

5. Simulations

Beacons B1, B2, B3, and B4 are deployed as shown in the Figure 8. Assume that the measurement-distance estimate to beacon B3 suffers an extra positive 50 cm measurement error due to the lack of the line of sight.

Figure 8

Simulation model.

Figures 9, 10, and 11 show the localization errors for the x-, y-, and z-direction when the node is in plane $z=\mathrm{1}$  m. It is found that when beacon B3 has a big positive measurement error, in x-direction there is no effect, but in y- and z-direction, this kind of measurement error causes a very big localization error. We also find that error increases when the actual distance from the node to the beacon B3 increases. On the contrary, even when we do not know which beacon has no line of sight, according to the localization results, we can determine that the beacon B3 actually has no line of sight and therefore should be avoided in the sensor localization.

Figure 9

Localization errors at x-direction.

Figure 10

Localization errors at y-direction.

Figure 11

Localization errors at z-direction.

In order to clearly examine the x error, Figure 12 gives its contour figure. In this figure, polygons stand for the error contour at $\pm 3$  cm. Projected beacon positions are also marked in order to consider the effect of the node position on the localization errors. This figure shows that the error is very small if the projected node position is within the beacon span, nearly all localized points have absolute error smaller than 3 cm. However, it also shows that localization error will be slightly larger if the projected node position lies in another area. It shows that for accurate localization, it is better to use the nearest beacon whose project area can cover the project position of a node.

Figure 12

Contour of x error.

6. Conclusions

This paper proposes an approach to identify non-line-of-sight beacon and rectify the localization result. With which, beacons who have no line of sight can be found out effectively by studying localization results distribution from several separated groups, so that the relevant overestimated distances can be ruled out. Thus the final result can be rectified and accuracy can be improved. Simulations show the correctness of the proposed approach.