Range-Based Localization in Wireless Networks Using Density-Based Outlier Detection

ABSTRACT

Node localization is commonly employed in wireless networks. For example, it is used to improve routing and enhance security. Localization algorithms can be classified as range-free or range-based. Range-based algorithms use location metrics such as ToA, TDoA, RSS, and AoA to estimate the distance between two nodes. Proximity sensing between nodes is typically the basis for range-free algorithms. A tradeoff exists since range-based algorithms are more accurate but also more complex. However, in applications such as target tracking, localization accuracy is very important. In this paper, we propose a new range-based algorithm which is based on the density-based outlier detection algorithm (DBOD) from data mining. It requires selection of the K-nearest neighbours (KNN). DBOD assigns density values to each point used in the location estimation. The mean of these densities is calculated and those points having a density larger than the mean are kept as candidate points. Different performance measures are used to compare our approach with the linear least squares (LLS) and weighted linear least squares based on singular value decomposition (WLS-SVD) algorithms. It is shown that the proposed algorithm performs better than these algorithms even when the anchor geometry about an unlocalized node is poor.

Node localization is commonly employed in wireless networks. For example, it is used to improve routing and enhance security. Localization algorithms can be classified as range-free or range-based. Range-based algorithms use location metrics such as ToA, TDoA, RSS, and AoA to estimate the distance between two nodes. Proximity sensing between nodes is typically the basis for range-free algorithms. A tradeoff exists since range-based algorithms are more accurate but also more complex. However, in applications such as target tracking, localization accuracy is very important. In this paper, we propose a new range-based algorithm which is based on the density-based outlier detection algorithm (DBOD) from data mining. It requires selection of the K-nearest neighbours (KNN). DBOD assigns density values to each point used in the location estimation. The mean of these densities is calculated and those points having a density larger than the mean are kept as candidate points. Different performance measures are used to compare our approach with the linear least squares (LLS) and weighted linear least squares based on singular value decomposition (WLS-SVD) algorithms. It is shown that the proposed algorithm performs better than these algorithms even when the anchor geometry about an unlocalized node is poor.

KEYWORDS

Localization, Positioning, Ad Hoc Networks, Range-Based, Wireless Sensor Network, Outlier Detection, Clustering

Localization, Positioning, Ad Hoc Networks, Range-Based, Wireless Sensor Network, Outlier Detection, Clustering

Cite this paper

nullK. Almuzaini and A. Gulliver, "Range-Based Localization in Wireless Networks Using Density-Based Outlier Detection,"*Wireless Sensor Network*, Vol. 2 No. 11, 2010, pp. 807-814. doi: 10.4236/wsn.2010.211097.

nullK. Almuzaini and A. Gulliver, "Range-Based Localization in Wireless Networks Using Density-Based Outlier Detection,"

References

[1] L. Doherty, K. S. J. Pister and L. El Ghaoui, “Convex Position Estimation in Wireless Sensor Networks,” Proceedings of IEEE INFOCOM, Anchorage, AK, April 2001, pp. 1655-1663.

[2] N. Bulusu, J. Heidemann and D. Estrin, “GPS-Less Low-Cost Outdoor Localization for Very Small Devices,” IEEE Personal Communications, Vol. 7, No. 5, October 2000, pp. 28-34.

[3] T. He, C. Huang, B. M. Blum, J. A. Stankovic and T. Abdelzaher, “Range-Free Localization Schemes For Large Scale Sensor Networks,” Proceedings of ACM MobiCom, San Diego, CA, September 2003, pp. 81-95.

[4] K. Almuzaini and T. A. Gulliver, “A New Distributed Range-Free Localization Algorithm for Wireless Networks,” Proceedings of IEEE Vehicular Technology Conference, Anchorage, AK, September 2009, pp. 20-23.

[5] I. Guvenc and Z. Sahinoglu, “Threshold-Based TOA Estimation for Impulse Radio UWB Systems,” Proceedings of IEEE International Conference on Ultra-Wideband, Zurich, Switzerland, September 2005, pp. 420-425.

[6] X. Wei, L. Wang and J. Wan, “A New Localization Technique Based on Network TDOA Information,” Proceedings of IEEE International Conference on ITS Telecommunications, Chengdu, China, June 2006, pp. 127-130.

[7] A. Hatami, K. Pahlavan, M. Heidari and F. Akgul, “On RSS and TOA Based Indoor Geolocation—A Comparative Performance Evaluation,” Proceedings of IEEE Wireless Communications and Networking Conference, Las Vegas, NV, April 2006, pp. 2267-2272.

[8] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) Using AOA,” Proceedings of IEEE INFOCOM, San Francisco, CA, March-April 2003, pp. 1734-1743.

[9] P. N. Tan, M. Steinbach and V. Kumar, “Introduction to Data Mining,” Pearson Addison Wesley, Boston, 2006.

[10] I. Guvenc, C.-C. Chong and F. Watanabe, “Analysis of a Linear Least-Squares Localization Technique in LOS and NLOS Environments,” Proceedings of IEEE Vehicular Technology Conference, Dublin, Ireland, April 2007, pp. 1886-1890.

[11] C.-H. Park and K.-S. Hong, “Source Localization Based on SVD without a Priori Knowledge,” Proceedings of IEEE International Conference on Advanced Communications Technology, Phoenix Park, Korea, February 2010, pp. 3-7.

[12] D. J. Torrieri, “Statistical Theory of Passive Location Systems,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 20, No. 2, March 1984, pp. 183-198.

[13] H. C. So and F. K. W. Chan, “A Generalized Subspace Approach for Mobile Positioning with Time-of-Arrival Measurements,” IEEE Transactions on Signal Processing, Vol. 55, No. 10, October 2007, pp. 5103-5107.

[14] F. K. W. Chan, H. C. So, J. Zheng and K. W. K. Lui, “Best Linear Unbiased Estimator Approach for Time- of-Arrival Based Localisation,” IET Signal Processing, Vol. 2, No. 2, June 2008, pp.156-163.

[15] D. B. Jourdan, D. Dardari and M. Z. Win, “Position Error Bound for UWB Localization in Dense Cluttered Environments,” Proceedings of IEEE International Conference on Communications, Istanbul, Turkey, June 2006, pp. 3705-3710.

[16] S. Venkatesh and R. M. Buehrer, “Multiple-Access Design for Ad Hoc UWB Position-Location Networks,” Proceedings of IEEE Wireless Communications and Networking Conference, Las Vegas, NV, April 2006, pp. 1866-1873.

[17] J. Vince, “Geometry for Computer Graphics: Formulae, Examples and Proofs,” Springer, Berlin, 2005.

[1] L. Doherty, K. S. J. Pister and L. El Ghaoui, “Convex Position Estimation in Wireless Sensor Networks,” Proceedings of IEEE INFOCOM, Anchorage, AK, April 2001, pp. 1655-1663.

[2] N. Bulusu, J. Heidemann and D. Estrin, “GPS-Less Low-Cost Outdoor Localization for Very Small Devices,” IEEE Personal Communications, Vol. 7, No. 5, October 2000, pp. 28-34.

[3] T. He, C. Huang, B. M. Blum, J. A. Stankovic and T. Abdelzaher, “Range-Free Localization Schemes For Large Scale Sensor Networks,” Proceedings of ACM MobiCom, San Diego, CA, September 2003, pp. 81-95.

[4] K. Almuzaini and T. A. Gulliver, “A New Distributed Range-Free Localization Algorithm for Wireless Networks,” Proceedings of IEEE Vehicular Technology Conference, Anchorage, AK, September 2009, pp. 20-23.

[5] I. Guvenc and Z. Sahinoglu, “Threshold-Based TOA Estimation for Impulse Radio UWB Systems,” Proceedings of IEEE International Conference on Ultra-Wideband, Zurich, Switzerland, September 2005, pp. 420-425.

[6] X. Wei, L. Wang and J. Wan, “A New Localization Technique Based on Network TDOA Information,” Proceedings of IEEE International Conference on ITS Telecommunications, Chengdu, China, June 2006, pp. 127-130.

[7] A. Hatami, K. Pahlavan, M. Heidari and F. Akgul, “On RSS and TOA Based Indoor Geolocation—A Comparative Performance Evaluation,” Proceedings of IEEE Wireless Communications and Networking Conference, Las Vegas, NV, April 2006, pp. 2267-2272.

[8] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) Using AOA,” Proceedings of IEEE INFOCOM, San Francisco, CA, March-April 2003, pp. 1734-1743.

[9] P. N. Tan, M. Steinbach and V. Kumar, “Introduction to Data Mining,” Pearson Addison Wesley, Boston, 2006.

[10] I. Guvenc, C.-C. Chong and F. Watanabe, “Analysis of a Linear Least-Squares Localization Technique in LOS and NLOS Environments,” Proceedings of IEEE Vehicular Technology Conference, Dublin, Ireland, April 2007, pp. 1886-1890.

[11] C.-H. Park and K.-S. Hong, “Source Localization Based on SVD without a Priori Knowledge,” Proceedings of IEEE International Conference on Advanced Communications Technology, Phoenix Park, Korea, February 2010, pp. 3-7.

[12] D. J. Torrieri, “Statistical Theory of Passive Location Systems,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 20, No. 2, March 1984, pp. 183-198.

[13] H. C. So and F. K. W. Chan, “A Generalized Subspace Approach for Mobile Positioning with Time-of-Arrival Measurements,” IEEE Transactions on Signal Processing, Vol. 55, No. 10, October 2007, pp. 5103-5107.

[14] F. K. W. Chan, H. C. So, J. Zheng and K. W. K. Lui, “Best Linear Unbiased Estimator Approach for Time- of-Arrival Based Localisation,” IET Signal Processing, Vol. 2, No. 2, June 2008, pp.156-163.

[15] D. B. Jourdan, D. Dardari and M. Z. Win, “Position Error Bound for UWB Localization in Dense Cluttered Environments,” Proceedings of IEEE International Conference on Communications, Istanbul, Turkey, June 2006, pp. 3705-3710.

[16] S. Venkatesh and R. M. Buehrer, “Multiple-Access Design for Ad Hoc UWB Position-Location Networks,” Proceedings of IEEE Wireless Communications and Networking Conference, Las Vegas, NV, April 2006, pp. 1866-1873.

[17] J. Vince, “Geometry for Computer Graphics: Formulae, Examples and Proofs,” Springer, Berlin, 2005.