Robust system multiangulation using subspace methods

ABSTRACT

Sensor location information is a prerequisite to the utility of most sensor networks. In this paper we present a robust and low-complexity algorithm to self-localize and orient sensors in a network based on angle-of-arrival (AOA) information. The proposed non-iterative subspace-based method is robust to missing and noisy measurements and works for cases when sensor orientations are either known or unknown. We show that the computational complexity of the algorithm is O (mn²), where m is the number of measurements and n is the total number of sensors. Simulation results demonstrate that the error of the proposed subspace algorithm is only marginally greater than an iterative maximum-likelihood estimator (MLE), while the computational complexity is two orders of magnitude less. Additionally, the iterative MLE is prone to converge to local maxima in the likelihood function without accurate initialization. We illustrate that the proposed subspace method can be used to initialize the MLE and obtain near-Cramér-Rao performance for sensor localization. Finally, the scalability of the subspace algorithm is illustrated by demonstrating how clusters within a large network may be individually localized and then merged.

REFERENCES

• 1: J. Ash and L. Potter. Sensor network localization via received signal strength measurements with directional antennas. Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing pages 1861--1870, Monticello, IL, Sep 2004.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: I. Borg and P. Groenen. Modern Multidimensional Scaling: Theory and Applications Springer, 1997.
• 4: Chiao-En Chen , Andreas M. Ali , Hanbiao Wang, Design and testing of robust acoustic arrays for localization and enhancement of several bird sources, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127819]
• 5: J.C. Chen, K. Yao, and R.E. Hudson. Source localization and beamforming. IEEE Signal Processing Magazine 19(2):30--39, 2002.
• 6: T.F. Coleman and Y. Li. An interior, trust region approach for nonlinear minimization subject to bounds. SIAM Journal on Optimization 6:418--445, 1996.
• 7: L. Doherty, L. El Ghaoui, and K. Pister. Convex position estimation in wireless sensor networks. Proc. INFOCOM 3:1655--1663, 2001.
• 8: G. Golub and C. Van Loan. Matrix Computations Johns Hopkins University Press, 3rd edition, 1996.
• 9: M. Gu and S.C. Eisenstat. A stable and fast algorithm for updating the singular value decomposition. Technical Report YALEU/DCS/RR-966, New Haven, CT, 1993.
• 10: R.L. Moses, D. Krishnamurthy, and R. Patterson. An auto-calibration method for unattended ground sensors. IEEE International Conference on Acoustics, Speech, and Signal Processing 3(4):III-2941-III-2944, May 13-17, 2002.
• 11: D. Niculescu and B. Nath. Ad hoc positioning system (APS)using AOA.Proc. INFOCOM 3:1734--1743, 2003.
• 12: N. Patwari, J.N. Ash, S. Kyperountas, A.O. Hero III, R.L. Moses, and N.S. Correal. Locating the nodes: cooperative localization in wireless sensor networks. IEEE Signal Processing Magazine 22(4):54--69, July 2005.
• 13: H. Vincent Poor, An introduction to signal detection and estimation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 14: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 15: P.H. Schönemann and R.M. Carroll. Fitting one matrix to another under choice of a central dilation and a rigid motion. Psychometrika 35:245--255, 1970.
• 16: J. Smith and J. Abel. Closed-form least-squares source location estimation from range-difference measurements. IEEE Transactions on Acoustics, Speech, and Signal Processing ASSP-35(12), 1987.
• 17: N. Srebro and T. Jaakkola. Weighted low-rank approximations. Proc. of the 20th International Conf. on Machine Learning 2003.
• 18: G. Stewart. An updating algorithm for subspace tracking. IEEE Trans. on Signal Processing 40(6):1535--1541, June 1992.
• 19: P. Stoica and R. Moses. Spectral Analysis of Signals Prentice Hall, 2005.
• 20: J.B. Tenenbaum, V. de Silva, and J.C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science 290(5500):2319--2323, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Algorithms, Design

Keywords:
angle-of-arrival (AOA), calibration, localization, sensor networks