Abstract: Non-line-of-sight (NLOS) errors which derived from the blocking of direct paths have been considered as the dominant problem in the mobile position estimation. Therefore, this study presented a study on the residual weighting algorithm (RWGH). First, the drawback of the traditional RWGH was investigated and then a base station selection strategy was proved to be effective. Moreover, the weight determination also plays an important role in the RWGH and the conventional reciprocal weight performs poor when the number of Line-of-sight (LOS) base station is small. Thus, some new weight computing schemes were proposed and compared, resulting in better performance at the case with few LOS base stations. The proposed algorithm was tested by computer simulations and the result showed better performance and smaller complexity compared with the conventional one.
INTRODUCTION
The method to determine the position of a Mobile Station (MS) had become more and more important in wireless networks due to many location-required wireless services (FCC, 2001). Conventionally, there had been some schemes to estimate the MS location (Li et al., 2010; Gustafsson and Gunnarsson, 2005; Liu et al., 2007), where many parameters, such as Time of Arrival (TOA) (Xu et al., 2011), Time Difference of Arrival (TDOA) (Xu and Zi-Shu, 2011), Time Sum of Arrival (TSOA) (Lay and Chao, 2005), Received Signal Strength (RSS) (Ouyang et al., 2010) and Angle of Arrival (AOA) (Lee, 2011), were employed to construct a linear equation group according to the geometry relation between the MS and the Base Station (BS).
There were two main error sources in localization algorithms, i.e., the measurement noise as well as NLOS errors. The latter had been treated as the fatal issue in wireless localization, where the NLOS signal was reflected or diffracted to produce a much longer path than the direct path, resulting in great degradations of the localization accuracy (Guvenc and Chong, 2009; Jing et al., 2010). Therefore, it is very important to mitigate the NLOS errors in real-world mobile locations.
Many methods had been proposed to mitigate the NLOS error. In literature (Al-Jazzar and Caffery Jr., 2002; Al-Jazzar et al., 2002), people constructed a specified scattering model and then determined the MS position but such a scattering model is difficult to find in practical environments. The second way was to identify the LOS Base Stations (BSs) first and then exploit only the LOS BSs to determine the MS position (Wylie and Holtzman, 1996; Chan et al., 2006), whose drawbacks lied in that the number of LOS BS must be larger than a certain value. Another way to mitigate the NLOS error was to estimate the MS position with all measurements and then the NLOS error can be reduced by the weighting summation (Venkatraman et al., 2004; Chen, 1999).
Generally, the RWGH (Chen, 1999) belongs to the third kind of scheme mentioned above and its performance was better than all other traditional localization algorithms. However, the original RWGH method required a large computation load and is not suitable for real-time realizations. Therefore, this study investigated a novel RWGH, which reduces the complexity while maintains similar estimation accuracies. By studying the influence of the BS number exploited in the weight operation, a BS selection strategy was proposed to reduce the participated BS number and therefore the computation complexity was reduced effectively. Moreover, the weight calculation scheme was investigated and some new alternatives were put forward. Simulations show a better performance of the proposed algorithm with a lower complexity when compared with the original RWGH algorithm.
ORIGINAL RWGH LOCALIZATION
Basis for mobile location: Since there is no any prior information of the range measurements in the localization, only the Least Squares (LS) principle can be used, i.e.:
| (1) |
where, x,
| (2) |
with:
and {Xi (xi, yi), I = 1, 2,... n}. Here (•)T is represents transpose operation. From Eq. 2, the LS solution must obey:
| (3) |
where, (•)-1 denotes the matrix inverse.
Original RWGH algorithm: Define the residual error res(x’S) as:
| (4) |
where, S is no less than three, since the least number of BS to determine the MS position is three for the range measurement method. When there are NLOS range measurements, res(x;S) is likely to be greater than that in the LOS environment.
Taking into consideration a wireless network with M BSs and M range measurements, these measurements can be grouped in various ways so long as each group includes at least three range measurements, e.g., if M = 7, there will be 99 different groups in all, since:
| (5) |
Each group range measurements can be used to estimate the MS position, thus there will be 99 estimations for M = 7. Such estimations are called as Intermediate Location Estimations (ILE) in our study. With each ILE, the residual error could be calculated and then the normalized residual is defined as:
| (6) |
In Eq. 6 (Chen, 1999), it was exploited to refine the location estimation by the weighting operation, i.e.:
| (7) |
Since, a good ILE tended to have a small normalized residual, the reciprocal weight in Eq. 7 usually helps to refine the final estimation. Moreover, Eq. 7 means that the final estimation is the linear combination of the weighted ILEs. Additionally, Eq. 7 produces large calculation loads. For example, 99 LS solutions and 99 residuals should be computed if M = 7.
PROPOSED RWGH LOCALIZATION
In most practical environments, the measurement error is small compared with the NLOS error. Moreover, if there are three more LOS BSs, there must be at least one ILE with small es(X;S) and large weights, while other ILEs will lead to small weights and large residuals.
After careful investigations, the final location estimation made by the reciprocal weight is found to be deteriorated by the ILEs with large residuals. Hence, the group corresponding to large normalized residual can be ignored in Eq. 7, which will be confirmed in the next section. As an example, if there are two NLOS BSs and five LOS BSs, five or less BSs will be exploited in Eq. 7 and it is possible to yield the NLOS-free final estimation.
The explanation above tells us that the employment of ILE without any constraints will bring some accurate ILEs together with more inaccurate ILEs. Then, if the weight of the accurate estimation was not large enough, the original RWGH algorithm suffered from both the large calculation load and the accuracy loss of the final estimation. Accordingly, this study proposes to employ less BSs in Eq. 7 when the RWGH algorithm is used in hybrid LOS/NLOS environments.
Referenced to Chen (1999), if the number of LOS BSs was small, such as 3, the localization accuracy was very poor. Even though, there was one LOS-based ILE in all ILEs, its contribution was not large enough to mitigate the NLOS error. Thus, more extra innovations should be proposed when facing such situations and this study proposes to use more effective weight calculating schemes in stead of the reciprocal weight, i.e., power of the reciprocal of the residual:
| (8) |
Here, x represents the value of normalized residual. When the order i = 1, f(x) converges to the reciprocal weight of original RWGH algorithm.
Generally, if the ILE with the smallest residual is LOS-based estimation, Eq. 7 of a high order made the final location estimation very accurate. However, some residuals of NLOS estimation can also be very small by coincidence. Figure 1 illustrates a localization situation where the measured ranges are corrupted by NLOS error. Obviously, the intersection of circles will be regarded as the final result by mistake, since its residual is very small. Fortunately, the above mistake is an occasional event with small probability. Yet the proposed high order power weight is useful.
Since the final localization result of the high order weighting algorithm is almost the same as the ILE with the smallest residual (such as i = 10), one can be easy to make a compromise when deciding which weighting method to be chosen by observing the Cumulative Distributed Function (CDF) of each weighting algorithms.
SIMULATION AND ANALYSIS
Simulation environment: The simulation environment is shown in Fig. 2, where, R = 200 m and seven BSs locate at (0,3R), (-2R, 4R), (-4R, -R), (-2R, -4R) (2R, 5R), (4R, 0R) and (3R, 5R). Moreover, the position of MS is (500, 300 m). Without loss of generality, the unit ’m’ will be ignored at next.
| Fig. 1: | NLOS estimation with small residual |
The measurement error is modeled as Gaussian variable with zero mean and standard deviation σ (Chan et al., 2006). The model of NLOS error is hard to obtain and this study uses the uniformly distributed random variables to model the NLOS error (Wang et al., 2003).
In order to evaluate the proposed algorithm in NLOS scenarios, four cases are presented:
| • | Case 7/1: Only one range measurement is corrupted by NLOS error |
| • | Case 7/2: Only two range measurements are corrupted by NLOS errors |
| • | Case 7/3: Only three range measurements are corrupted by NLOS errors |
| • | Case 7/4: Only four range measurements are corrupted by NLOS errors |
Simulation result and analysis: In the first simulation, the standard deviation of the measurement error is 5 and the maximum value of the NLOS error is (100, 200, 300, 400, 500). Moreover, there are five algorithm settings in the first simulation:
| • | The traditional RWGH (Chen, 1999) |
| • | The proposed RWGH using three BSs in Eq. 7, namely RWGH_3BS |
| • | The proposed RWGH using three and four Bss in Eq. 7, namely RWGH_4BS |
| • | The proposed RWGH using three, four and five BSs in Eq. 7, namely RWGH_5BS |
| • | The proposed RWGH using three, four, five and six BSs in Eq. 7, namely RWGH_6BS |
| Fig. 2: | Localization geometry of the BSs and MS |
The performance criteria is chosen as the root mean square error (RMSE), viz:
| (9) |
where, (x,y) and (
It is shown in Fig. 3 that the RMSE comparison of different algorithm settings, where one can be explicitly see that large NLOS errors lead to large RMSEs and a large LOS BS number results in better performance. From Fig. 3, it is easy to f ind that theRWGH_3BS setting outperforms all other algorithm settings, which confirm our conclusion in the previous section, i.e., the minimum BS number will produce the best performance in the RWGH algorithm. Moreover, the small BS number in Eq. 7 obviously reduces the computation complexity. On the whole, the performance ranking from the worst to the best with respect to the different algorithm settings is: RWGH method, RWGH_6BS, RWGH_5BS, RWGH_4BS and RWGH_3BS.
Although, the performance of the RWGH algorithm can be improved by using the proposed grouping strategy, whose accuracy is still very poor in case 7/4 and 7/3 as seen from Fig. 3c and d. Thus, the second simulation takes into account the influence of different weighting methods. There are some settings at Table 1, where RWGH represents the traditional algorithm and the algorithms followed are denoted as the proposed RWGH_3BS taking the 1st, 2nd, 5th and 10th order of Eq. 7 as the weighting functions, respectively.
The Standard Deviation (STD) of measurement noise is 1, 5 and 10, respectively, while the maximum NLOS error is 500. The CDF is chosen as the performance criterion.
From Fig. 4, the proposed algorithm is found to perform better than the traditional RWGH when measurement noises are small. But with the increase of the noise, the accuracy of the proposed algorithm degrades fast, which proves our previous deductions, i.e., the estimation with the smallest residual is not always LOS and some residuals of NLOS estimation may be very small by coincidence. The probabilities of the LOS-based ILE with the smallest residual are about 95, 80 and 69% when STD equals to 1, 5 and 10, respectively. This conclusion can be easily reasoned out since about 95, 80 and 69% of estimations are accurate for corresponding case, viz., the localization error is below 100 meters.
| Fig. 3(a-d): | Comparisons of root mean square error for (a) Case 7/1, (b) Case 7/2, (c) Case 7/3 and (d) Case 7/4 RWGH algorithm settings |
| Fig. 4(a-c): | Comparisons of cumulative distributed function for Standard deviation is (a) 1 m, (b) 5 m and (c) 10 m weighting method |
| Table 1: | Algorithm setting of the second simulation |
From Fig. 4, one can conclude that the accuracy of range measurement will affect the CDF. When the accuracy of range measurement increases, the residual of the LOS estimation becomes much smaller, thus, there is a much larger probability for the estimation with the smallest residual to be LOS estimation.
Although, the performance of the proposed weighting algorithm is poor in situations with large measurement noise, Fig. 4 also indicates that if the NLOS error is great, it is much harder for the NLOS-based location estimation to yield a small residual error. Thus, the ILE with the smallest residual will come from the LOS BS at a high probability, which yields good performance in Fig. 5. In Fig. 5, the NLOS error is uniformly distributed in 200~1000 and the STD is 5.
It can be seen from Fig. 5 that the accuracy of the proposed weighting algorithms has been improved by compared with Fig. 4b and the probability of the LOS-based ILE having the smallest residual is about 85%, which is larger than 80% in Fig. 4b. This result proves the correctness of the deduction above.
The performance comparison of the proposed (1/x)2 algorithm with the traditional Least Square (LS) method, RWGH and Constrained Least Square (CLS) method (Wang et al., 2003) is done in the Case 7/4, the result is shown in Fig. 6, where Mean Square Error (MSE) is chosen as the criterion, viz:
| (10) |
Figure 6 shows that the proposed algorithm outperforms other three algorithms. Figure 6a demonstrates the performance variation of each algorithm with the increase of noise variance, where the proposed algorithm is found to have the smallest MSE.
| Fig. 5: | Cumulative distributed function comparison for different weighting method in serious NLOS environments |
| Fig. 6(a-b): | Comparison of performance between (a) Mean square error versus noise variance and (b) Mean square error versus NLOS error algorithms |
Figure 6b shows the MSE of each algorithm versus the maximum value of NLOS error, where the proposed algorithm is also found to be the best algorithm. Moreover, the proposed algorithm is the most robust one among four algorithms as indicated by its flattest curve. From Fig. 6, the performance of the four algorithms can be sorted as Proposed (1/x)2 algorithm>RWGH>CLS>LS.
CONCLUSION
The NLOS error has long been considered as the fatal issue in wireless localization and the RWGH can release this deficiency in hybrid NLOS/LOS environments. However, its high calculation cost may be a big problem in practical applications. Thus, this study investigated the influence of group dimensions and proposes to use less BSs in the RWGH algorithm. Moreover, a novel weighting method has been proposed to further improve the estimation accuracy. Simulations demonstrated that RWGH_3BS outperformed the traditional RWGH algorithm and other NLOS mitigation algorithms in all cases and the higher order weighting algorithm was fond to useful when the measurement noise is vary small or the NLOS error is very large.
ACKNOWLEDGMENTS
This study is supported by the Zhejiang provincial NSF under grant No. LY12E07005 and the open research fund of National Mobile Communications Research Lab, Southeast University (No. 2010D06).