Robust localization against outliers in wireless sensor networks

Abstract

In wireless sensor networks, a critical system service is the localization service that determines the locations of geographically distributed sensor nodes. The raw data used by this service are the distance measurements between neighboring nodes and the position knowledge of anchor nodes. However, these raw data may contain outliers that strongly deviate from their true values, which include both the outlier distances and the outlier anchors. These outliers can severely degrade the accuracy of the localization service. Therefore, we need a robust localization algorithm that can reject these outliers. Previous studies in this field mainly focus on enhancing multilateration with outlier rejection ability, since multilateration is a primitive operation used by localization service. But patch merging, a powerful operation for increasing the percentage of localizable nodes in sparse networks, is almost neglected. We thus propose a robust patch merging operation that can reject outliers for both multilateration and patch merging. Based on this operation, we further propose a robust network localization algorithm called RobustLoc. This algorithm makes two major contributions. (1) RobustLoc can achieve a high percentage of localizable nodes in both dense and sparse networks. In contrast, previous methods based on robust multilateration almost always fail in sparse networks with average degrees between 5 and 7. Our experiments show that RobustLoc can localize about 90% of nodes in a sparse network with 5.5 degrees. (2) As far as we know, RobustLoc is the first to uncover the differences between outlier distances and outlier anchors. Our simulations show that RobustLoc can reject colluding outlier anchors reliably in both convex and concave networks.

References

1. Eren, T., Goldenberg, D. K., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., and Belhumeur, P. N. 2004. Rigidity, computation, and randomization in network localization. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies.
2. Foy, W. H. 1976. Position-location solutions by Taylor-series estimation. IEEE Trans. Aerospace Electron. Syst. 12, 2, 187--194.
3. Goldenberg, D. K., Bihler, P., Cao, M., Fang, J., Anderson, B. D. O., Morse, A. S., and Yang, Y. R. 2006. Localization in sparse networks using sweeps. In Proceedings of the Annual ACM International Conference on Mobile Computing and Networking.
4. He, T., Huang, C., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. 2003. Range-free localization schemes for large scale sensor networks. In Proceedings of the Annual ACM International Conference on Mobile Computing and Networking.
5. Horn, B. K. P., Hilden, H., and Negahdaripour, S. 1988. Closed-form solution of absolute orientation using orthonormal matrices. J. Opti. Soc. Am. A, 4, 629.
6. Jian, L.-R., Yang, Z., and Liu, Y.-H. 2010. Beyond triangle inequality: Sifting noisy and outlier distance measurements for localization. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies.
7. Kannan, A. A., Fidan, B., and Mao, G.-Q. 2011. Robust distributed sensor network localization based on analysis of flip ambiguities. Wirel. Netw. 17, 5, 1157--1171.
8. Kiyavash, N. and Koushanfar, F. 2007. Anti-collusion position estimation in wireless sensor networks. In Proceedings of the IEEE Conference on Mobile, Ad Hoc and Sensor System.
9. Kung, H. T., Lin, C.-K., Lin, T.-H., and Vlah, D. 2009. Localization with snap-inducing shaped residuals (SISR): Coping with errors in measurement. In Proceedings of the Annual ACM International Conference on Mobile Computing and Networking.
10. Li, M. and Liu, Y.-H. 2007. Rendered path: Range-free localization in anisotropic sensor networks with holes. In Proceedings of the Annual ACM International Conference on Mobile Computing and Networking. 51--62.
11. Li, Z., Trappe, W., Zhang, Y., and Nath, B. 2005. Robust statistical methods for securing wireless localization in sensor networks. In Proceedings of the International Conference on Information Processing in Sensor Networks. 12.
12. Lim, H. and C., H. J. 2005. Localization for anisotropic sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies. 138--149.
13. Liu, D., Ning, P., and Du, W. K. 2005. Attack-resistant location estimation in sensor networks. In Proceedings of the International Conference on Information Processing in Sensor Networks.
14. Mao, G.-Q. and Fidan, B. 2009. Localization Algorithms and Strategies for Wireless Sensor networks. IGI Global, Hershey, PA.
15. Moore, D., Leonard, J., Rus, D., and Teller, S. 2004. Robust distributed network localization with noisy range measurements. In Proceedings of the ACM Conference on Embedded Networked Sensor Systems.
16. Newsome, J., Shi, E., Song, D., and Perrig, A. 2004. The sybil attack in sensor networks: Analysis & defenses. In Proceedings of the International Conference on Information Processing in Sensor Networks.
17. Niculescu, D. and Nath, B. 2003. DV based positioning in ad hoc networks. Kluwer J. Telecommun. Syst.
18. Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. 2003. Anchor-free distributed localization in sensor networks. In Proceedings of the ACM Conference on Embedded Networked Sensor Systems.
19. Savvides, A., Park, H., and Srivastava, M. B. 2003. The n-hop multilateration primitive for node localization problems. J. Mobile Netw. Appl. 8, 4, 443--451.
20. Shang, Y. and Ruml, W. 2004. Improved MDS-based localization. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies. 2640--2651.
21. Wang, C., Liu, A., and Ning, P. 2007. Cluster-based minimum mean square estimation for secure and resilient localization in wireless sensor networks. In Proceedings of the International Conference on Wireless Algorithms Systems and Applications.
22. Wang, C. and Xiao, L. 2006. Locating sensors in concave areas. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies. 1--12.
23. Wang, X.-P., Liu, Y.-H., Yang, Z., Liu, J.-L., and Luo, J. 2010. ETOC: Obtaining robustness in component-based localization. In Proceedings of the Annual International Conference on Network Protocols.
24. Wang, X.-P., Luo, J., Li, S.-S., Dong, D.-Z., and Cheng, W.-F. 2008. Component based localization in sparse wireless ad hoc and sensor networks. In Proceedings of the Annual International Conference on Network Protocols.
25. Whitehouse, K., Karlof, C., Woo, A., Jiang, F., and Culler, D. 2005. The effects of ranging noise on multihop localization: an empirical study. In Proceedings of the International Conference on Information Processing in Sensor Networks.
26. Xiao, B., Chen, H., and Zhou, S. 2008. Distributed localization using a moving beacon in wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 19, 5, 587--600.
27. Xiao, B., Chen, L., Xiao, Q.-J., and Li, M.-L. 2010a. Reliable anchor-based sensor localization in irregular areas. IEEE Trans. Mobile Comput. 9, 60--72.
28. Xiao, Q.-J., Xiao, B., Cao, J.-N., and Wang, J.-P. 2010b. Multihop range-free localization in anisotropic wireless sensor networks: A pattern-driven scheme. IEEE Trans. on Mobile Comput. 9, 1592--1607.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles