1. Introduction

Wireless sensor networks have dissimilar characteristics from conventional wireless networks. These networks consist of low-cost, low-power sensor nodes of smaller sizes having short communication ranges ^[2]. They can be applied to various practical and commercial applications, such as search, rescue, monitoring disaster area, and target tracking. Sensor localization is an essential feature of these location-aware services.

Localization schemes can be classified into two categories: range-free schemes and range-based schemes. The range-free scheme does not require the exact range measurement. Therefore, the cost of range measurements is reduced. Many range-free schemes are presented with diverse characteristics, e.g., APIT ^[3], DV-Hop ^[4], and Centroid ^[5]. The range-free scheme tends to be straightforward. On the other hand, the performance of the range-free scheme is affected by the density of nodes. The performance would be better if the nodes in the network are dense. The performance would be worse if the nodes are sparse in the network. On the other hand, it is impossible to predict whether the nodes are dense or sparse in an indoor environment owing to the dynamicity of the network. In addition, heavy broadcast signals in the range-free scheme can cause higher network traffic. Therefore, the range-free scheme does not cover all criteria occurring in indoor environments.

The range-based scheme requires high accuracy of range measurements because the measured range is used directly for sensor localization. Its accuracy affects the performance of range-based schemes. TOA (Time of Arrival) or TDOA (Time Difference of Arrival) uses time as a parameter for localization. In TOA and TDOA, the NLOS (None Line of Sight) is a very critical problem because it causes large distance error. Many authors discussed the NLOS mitigation in TOA or TDOA schemes ^[6-8]. If the environment is a small area, the propagation time of the signal is too short and difficult to calculate precisely. The sensor node requires an extra device to calculate the exact time, which will cause additional operating costs. The TDOA scheme is applied in GPS and Cricket ^[9]. GPS uses the signal from satellites and has better performance in outdoor localization. On the other hand, it cannot be used in indoor localization. Cricket is proposed for sensor localization in indoor environment. It is based on TDOA using radio and ultrasonic signals concurrently. The cost of the sensor node is less than US $10.

The ROA scheme does not require any special devices for range measurements. It is cost-effective and can be applied easily to the sensor node. Many authors suggested the ROA-based scheme for localization in indoor environments ^[10-12]. Nevertheless, the ROA-based scheme has a few problems. In the ROA-based scheme, the signal strength is affected by multipath fading and shadow fading, which makes the range measurements error. In indoor environments, the effects of multipath fading and shadow fading are much larger than those in urban and outdoor environments. The main focus for sensor localization in indoor environment is to solve these problems. Typically, the effects of multipath fading can be solved by sampling a sufficient number of signals and averaging the signal strength. On the other hand, shadow fading is more critical, and it is not easy to solve for sensor localization in indoor environment. After the node receives the signal from another node, it measures the range between itself and the sending node. The range may be more extensive than the real distance because of the effects of shadow fading. Therefore, it can be composed so that the two ranges are not crossed. Hence, intersections cannot be made between two ranges. It is a critical problem in range-based sensor localization because there is no other way to estimate the position of the sensor without intersections.

This paper formulates two major contributions toward the localization problem in an indoor environment. First, the Master Node (MN), one of the reference nodes nearest to the sensor node, is defined. Hence, the signal from the MN is more reliable for range measurement. Second, this paper proposed an ROA-based sensor localization scheme to mitigate multipath fading and shadow fading problems by expanding or reducing the measured range. The proposed RERR scheme performs the range expansion and reduction based on the most reliable range of signal from the Master Node. After applying the range expansion and reduction, the multi-trilateration method is used to estimate the sensor position because of the wide availability of intersections through the range expansion and reduction process.

The paper is organized as follows. The next section presents the proposed RERR scheme and its detailed description. The simulation results are presented, and the performance of RERR is analyzed with different parameters. Finally, the paper concludes with some closing remarks.

2. RERR Scheme

The RERR scheme is designed for sensor localization in indoor environments. The performance of the RERR scheme depends on the accuracy of the range measurement because the RERR is a range-based scheme using ROA. As mentioned in the previous section, sensor localization based on ROA has two main problems: multipath fading, and shadow fading. The effects of multipath fading can be overcome by sampling a sufficient number of signals and averaging the signal strength. On the other hand, shadow fading is a more critical problem, and it is difficult to overcome it in an indoor environment for sensor localization.

If the estimated distance is shorter than the real distance, there is no intersection between the two ranges of sensor location. No intersection causes a failure of sensor localization. Fig. 1 presents the measured range. The left side represents the range measurements of the ideal case, and the right side represents the range measurements of the real case. In an ideal case, there are six intersections, but in a real case, there are no intersections among the ranges because of shadow fading. There is no way to estimate the position of the sensor node. Therefore, the range expansion and reduction for making intersections are proposed.

Fig. 1. Measured ranges between the ideal case and real case.

2.2 Range Expansion and Range Reduction (RERR)

After the sensor node chooses the MN and SRNs, it performs the range measurements. On the other hand, there are errors in range measurements because of shadow fading. As shown in Fig. 1, the sensor node can have no intersection among the ranges. RERR scheme performs the range expansion and reduction for making intersections.

Fig. 2 shows when the range expansion (RE) is needed. In Fig. 2, there are two reference nodes: R and one sensor node S. The R1 and R2 are measured range from two reference nodes drawn as dotted circles. D is the real distance between the two reference nodes. The total amount of range expansion is E for making intersections. Therefore, E can be expressed as Eq. (1).

(1)

$ E = D - (R1 + R2) $

If both reference nodes are SRNs, not MN, then half of the total amount of expansion is applied to each range. The solid line in Fig. 2 represents a result of range expansion. On the other hand, if one of the two reference nodes is MN, then the range of MN does not need to change because it is the most reliable. In Fig. 3, R is the reference node, and M is MN. The remainder parameters, such as R1, R2, D, and E, are the same as in Fig. 2. The total amount of expansion is only applied to the range of R, not MN. The solid line in Fig. 3 represents a result of range expansion.

Fig. 4 shows when the range reduction (RR) is needed. In Fig. 4, there are two reference nodes: R and one sensor node S. R1 and R2 are the measured range from two reference nodes drawn as dotted circles. D is the real distance between the two reference nodes. The total amount of range reduction is E for making intersections. Therefore, E can be expressed as Eq. (2).

(2)

$ E=(R1-R2)-D $

Range reduction is only applied to a larger range between two ranges because a larger range tends to experience more prominent effects of shadow fading. The total amount of reduction E is only applied to a larger range. The solid line in Fig. 4 represents the results of a range reduction.

The results have shown how to expand or reduce the measured range. On the other hand, it is important to consider how to apply the range expansion and reduction to the multi-trilateration because the RERR scheme uses it as the sensor localization method. Figs. 5-7 show how to apply range expansion and reduction to the multi-trilateration method. First, the sensor node inspects whether the range of MN crosses with the range of other reference nodes and performs the range expansion or reduction if needed. Subsequently, if needed, the sensor node inspects whether the ranges between reference nodes are crossover and performs the range expansion or reduction.

In Fig. 5, there are three reference nodes and one M that is MN. After the sensor node finishes the range measurement, it finds the maximum difference between the ranges of M and each reference node. In the case of Fig. 5, the maximum difference is between reference node 1 and M. All ranges except the M range is expanded. Fig. 6 shows the red line that results from expansion considering the range of M. All of the ranges of reference nodes are crossed with the range of M. There are intersections between each reference node and M. On the other hand, there are no intersections between reference nodes 2 and 3. At that moment, the range expansion is performed. The red line in Fig. 7 shows the final result of the range expansion and reduction. The flow chart in Fig. 8 describes the proposed range expansion and reduction method. After the range expansion and reduction are performed, the RERR scheme performs the multi-trilateration.

Fig. 2. Range Expansion (RE) without MN.

Fig. 3. Range Expansion(RE) with MN.

Fig. 4. Range Reduction (RR).

Fig. 5. Range measurement before the range expansion or reduction.

Fig. 6. Range expansion with the Master Node M.

Fig. 7. Range expansion without the Master Node M.

Fig. 8. RERR flow chart.

2.3 Multi-trilateration

The RERR scheme uses multi-trilateration as a sensor localization method. Multi-trilateration is a popular localization method for diverse range-based schemes, such as ROA, TOA, and TDOA. Initially, it is essential to know the method to estimate the position of the intersection because it is used in the multi-trilateration method.

Fig. 9 shows two reference nodes with the positions (x1, y1) and (x2, y2). In addition, there are two intersections S1 (u1, v1) and S2 (u2, v2). $R1$ and $R2$ are ranges and $D$ is the real distance between two reference nodes. Two positions of the intersections through Eqs. (3)-(5). The two proofs are presented to understand the equation.

(3)

$ P=\frac{(R1^{2}-R2^{2}+D^{2})}{2D}, Q=\sqrt{R1^{2}-P^{2}} $

(4)

$ \begin{array}{l} a=\frac{(x2-x1)*P}{D}, b=\frac{(y2-y1)*P}{D}\\ w=\frac{(y2-y1)*Q}{D}, z=\frac{(x2-x1)*Q}{D} \end{array} $

(5)

$ \begin{align} \begin{array}{l} u1=x1+a-w=x1+\frac{(x2-x1)*P}{D}-\frac{(y2-y1)*Q}{D}\\ v1=y1+b+z=y1+\frac{(y2-y1)*P}{D}+\frac{(x2-x1)*Q}{D}\\ u2=x1+a+w=x1+\frac{(x2-x1)*P}{D}+\frac{(y2-y1)*Q}{D}\\ v2=y1+b-z=y1+\frac{(y2-y1)*P}{D}-\frac{x2-x1)*Q}{D} \end{array} \end{align} $

After finding the intersections, the three reference nodes among the SRNs make a Combination group. The number of Combinations is four if there are four SRNs.

Fig. 10 shows the four Combinations and the final estimated position of the sensor node, ‘E’. In each Combination, there are six intersections. On the other hand, only three intersections (colored) in Fig. 10 are used for sensor localization. In each Combination, the position of the sensor node is estimated by averaging three intersections. In Fig. 10, the cross in each Combination means the estimated position of the sensor node. In the case of Fig. 10, there were four intermediate results from four Combinations. The final position of the sensor node was estimated by averaging these intermediate results.

Fig. 9. Position of the two intersections S1(u1, v1) and S2(u2, v2).

Fig. 10. Four Combinations and the final position of sensor node E.

3. Simulation Environments

This section describes the simulation environments. This study evaluated the performance of the RERR scheme for sensor localization in indoor environment. As mentioned elsewhere, the channel characteristics are rapidly changing indoors. Therefore, it is difficult to expect how much the effects of shadow fading are. The shadow fading factor has a zero-mean value. On the other hand, the standard deviation of the shadow fading factor is not decided. Its variation depends on the environmental conditions. Consequently, this study considered the variable standard deviation of shadow fading and the variable path-loss exponent for covering many environmental conditions in the simulation. The parameters in Table 1 were used for the simulation.

This study used the channel model (6) that is specified in IEEE 802.15.4 Standard ^[13] as the IEEE 802.15.4 Standard suggests LR-WPAN, low-cost, and short-range communication networks suitable for sensor networks. Nine reference nodes were used to minimize the effects of shadow fading. As mentioned earlier, the signal is more reliable if the distance between reference nodes is smaller. The PL(d) was defined as the path loss value in dB when the distance is d cm. The PL(d) can be obtained by

4. Simulation Results

The simulation was separated into two parts to consider various channel conditions. First, the path-loss exponent was fixed to 2, and the standard deviation of the shadow fading factor was from 0 to 7. Second, the standard deviation of the shadow fading factor was fixed to 4, and the path-loss exponent was changed from 2 to 5.

The proposed RERR scheme was compared with Trilateration and Multi-Trilateration. For the performance comparison, the simulation results were the fail ratio in localization and the RMS error of sensor position. Localization could not be detected when the sensor position could not be found, such as the number of SRNs is smaller than 3.

4.1 Various Standard Deviation of Shadow Fading

Figs. 11 and 12 present the simulation results performed in 24m ${\times}$ 24m and 36m ${\times}$ 36m. As illustrated, the RERR scheme has the lowest fail ratio, and the RMS error is lower than Trilateration and Multi-Trilateration. Trilateration is used to determine an unknown position using the distance from three coordinates to an unknown position. Multi-Trilateration uses four coordinates to determine a position. In this case, the standard deviation is zero, and Trilateration has the lowest RMS error, but it is impossible to have a standard deviation of zero.

Fig. 12 shows the same results as Fig. 11. Among them, the failure ratio shows a similar value in the two figures because the location of the reference node is fixed. The size of the map is different during the simulation if the intensity of the signal received by the sensor is weak in the small map, it will reach weakly at 36${\times}$36m. Eventually, failure at 24${\times}$24m will cause failure at 36${\times}$36m.

The RERR scheme has the lowest fail ratio in localization and has the lowest RMS error, whatever the standard deviation of shadow fading. Trilateration or multi-Trilateration cannot know the location of the sensor node without the intersection of the signal range received from three or four reference nodes. Unlike these techniques, however, the RERR can effectively overcome shadowing because of obstacles by increasing or decreasing the range size to find the intersection.

Fig. 11. Various Standard Deviations (24m × 24m).

Fig. 12. Various Standard Deviation (36m × 36m).

4.2 Various Path-loss Exponent

Considering the channel variation and condition, an attempt was made to change the path-loss exponent. In Fig. 13, the RERR scheme has the lowest fail ratio in localization and the lowest RMS error. The other schemes are incomparable. Fig. 14 shows the same results as those depicted in Fig. 13.

Fig. 13. Various Path-Loss Exponent (24m × 24m).

Fig. 14. Various Path-Loss Exponent (36m × 36m).

5. Conclusion

This paper proposed an RERR scheme for indoor sensor localization. Various channel models were considered because this study did not anticipate rapidly changing channel characteristics in indoor environments. The comparison methods were Trilateration and Multi-trilateration, which were used broadly for localization. Through the simulation results, RERR showed better performance irrespective of the standard deviation of shadow fading, path-loss exponent, and the area of the simulation environment.