Xuanlong Nguyen
Michael I. Jordan
Abstract
We show that the coarse-grained and fine-grained localization problems for ad hoc sensor networks can be posed and solved as a pattern recognition problem using kernel methods from statistical learning theory. This stems from an observation that the kernel function, which is a similarity measure critical to the effectiveness of a kernel-based learning algorithm, can be naturally defined in terms of the matrix of signal strengths received by the sensors. Thus we work in the natural coordinate system provided by the physical devices. This not only allows us to sidestep the difficult ranging procedure required by many existing localization algorithms in the literature, but also enables us to derive a simple and effective localization algorithm. The algorithm is particularly suitable for networks with densely distributed sensors, most of whose locations are unknown. The computations are initially performed at the base sensors, and the computation cost depends only on the number of base sensors. The localization step for each sensor of unknown location is then performed locally in linear time. We present an analysis of the localization error bounds, and provide an evaluation of our algorithm on both simulated and real sensor networks.
- Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In INFOCOM '00 (2). 775--784.Google Scholar
- Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low cost outdoor localization for very small devices. Tech. Rep. 00-729, Computer Science Department, University of Southern California.Google Scholar
- D'Costa, A. and Sayeed, A. 2003. Collaborative signal processing for distributed classification in sensor networks. In 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03). 193--208. Google Scholar
- Girod, L. and Estrin, D. 2001. Robust range estimation using acoustic and multimodal sensing. In IEEE/RSI International Conference on Intelligent Robots and Systems (IROS'01).Google Scholar
- Hightower, J. and Borriello, G. 2000. Real-time error in location modeling for ubiquitous computing. In Location Modeling for Ubiquitous Computing---Ubicomp'01 Workshop Proceedings. 21--27.Google Scholar
- Lanckriet, G., Cristianini, N., Ghaoui, L. E., Bartlett, P., and Jordan, M. 2004. Learning the kernel matrix with semi-definite programming. J. Machine Learn. Res. 5, 27--72. Google Scholar
- Li, D., Wong, K., Hu, Y., and Sayeed, A. 2002. Detection, classification, and tracking of targets. IEEE Signal Process. Mag. 19, 17--29.Google Scholar
- Poor, H. V. 1994. An Introduction to Signal Detection, 2nd Ed. Springer-Verlag. Google Scholar
- Priyantha, N., Chakraborty, A., and Balakrishnan, H. 2000. The Cricket location-support system. In ACM International Conference on Mobile Computing and Networking. ACM Press, New York. Google Scholar
- Savarese, C., Rabaey, J., and Langendoen, K. 2002. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In USENIX Annual Technical Conference. Monterey, CA, 317--327. Google Scholar
- Savvides, A., Han, C., and Srivastava, M. 2001. Dynamic fine grained localization in ad-hoc sensor networks. In Proceedings of the 5th International Conference on Mobile Computing and Networking. 166--179. Google Scholar
- Schölkopf, B. and Smola, A. 2002. Learning with Kernels. MIT Press, Cambridge, MA.Google Scholar
- Seidel, A. and Rappaport, T. 1992. 914MHz path loss prediction models for indoor wireless communications in multi-floored buildings. IEEE Trans. Antenn. Propag. 40, 207--217.Google Scholar
- Sheng, X. and Hu, Y. 2003. Energy based acoustic source localization. In 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03). 285--300. Google Scholar
- Vapnik, V. 1998. Statistical Learning Theory. John Wiley & Sons, New York. Google Scholar
- Want, R., Hopper, A., Falcao, V., and Gibbons, J. 1992. The active badge location system. ACM Trans. Inform. Syst. 10, 91--102. Google Scholar
- Ward, A., Jones, A., and Hopper, A. 1997. A new location technique for the active office. IEEE Personn. Comm. 4, 42--47.Google Scholar
- Whitehouse, C. 2002. The design of Calamari: An ad-hoc localization system for sensor networks. MS. thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley.Google Scholar
Index Terms
- A kernel-based learning approach to ad hoc sensor network localization
Recommendations
Simultaneous localization, calibration, and tracking in an ad hoc sensor network
IPSN '06: Proceedings of the 5th international conference on Information processing in sensor networksWe introduce Simultaneous Localization and Tracking, called SLAT, the problem of tracking a target in a sensor network while simultaneously localizing and calibrating the nodes of the network. Our proposed solution, LaSLAT, is a Bayesian filter that ...
Distributed Localization Scheme for Mobile Sensor Networks
Localization is an essential and important research issue in wireless sensor networks (WSNs). Most localization schemes focus on static sensor networks. However, mobile sensors are required in some applications such that the sensed area can be enlarged. ...
Efficient and accurate sensor network localization
Wireless sensor networks (WSN) have great potential in ubiquitous computing. However, the severe resource constraints of WSN rule out the use of many existing networking protocols and require careful design of systems that prioritizes energy ...
Comments