Distributed weighted-multidimensional scaling for node localization in sensor networks

ABSTRACT

Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This article introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most accurate range measurements and naturally accounts for communication constraints within the sensor network. Each node adaptively chooses a neighborhood of sensors, updates its position estimate by minimizing a local cost function and then passes this update to neighboring sensors. Derived bounds on communication requirements provide insight on the energy efficiency of the proposed distributed method versus a centralized approach. For received signal-strength (RSS) based range measurements, we demonstrate via simulation that location estimates are nearly unbiased with variance close to the Cramér-Rao lower bound. Further, RSS and time-of-arrival (TOA) channel measurements are used to demonstrate performance as good as the centralized maximum-likelihood estimator (MLE) in a real-world sensor network.

REFERENCES

• 1: Recursive Position Estimation in Sensor Networks, Proceedings of the Ninth International Conference on Network Protocols, p.35, November 11-14, 2001
• 2: Benzécri, J. 1973. L'Analyse des Données, Tome 2, L'Analyse des Correspondences. Dunod, Paris.
• 3: Caffery Jr., J. and Stuber, G. L. 1998. Subscriber location in cdma cellular networks. IEEE Trans. Veh. Tech. 47, 2 (May), 406--416.
• 4: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 5: Catovic, A. and Sahinoglu, Z. 2004. The Cramer-Rao bounds of hybrid TOA/RSS and TDOA/RSS location estimation schemes. Tech. Rep. TR2003-143, Mitsubishi Electric Research Laboratory. (Jan).
• 6: Chen, P.-C. 1999. A non-line-of-sight error mitigation algorithm in location estimation. In IEEE Wireless Communication and Networking Conference. 316--320.
• 7: Cleveland, W. 1979. Robust locally weighted regression and smoothing scatterplots. J. Amer. Stat. Assoc. 74, 368, 829--836.
• 8: Correal, N. S., Kyperountas, S., Shi, Q., and Welborn, M. 2003. An ultra wideband relative location system. In IEEE Conference on Ultra Wideband Systems and Technologies.
• 9: Coulson, A. J., Williamson, A. G., and Vaughan, R. G. 1998. A statistical basis for lognormal shadowing effects in multipath fading channels. IEEE Trans. Veh. Tech. 46, 4 (April), 494--502.
• 10: Cox, D. 1972. Delay doppler characteristics of multipath propagation at 910 MHz in a suburban mobile radio environment. IEEE Trans. Antennas and Propagation AP-20, 5 (Sep), 625--635.
• 11: Cox, T. and Cox, M. 1994. Multidimensional Scaling. Chapman & Hall, London.
• 12: Davidson, M. L. 1983. Multidimensional Scaling. Wiley, Ney York.
• 13: Doherty, L., Pister, K. S. J., and Ghaoui, L. E. 2001. Convex position estimation in wireless sensor networks. In IEEE INFOCOM. Vol. 3. 1655--1663.
• 14: Fleming, R. and Kushner, C. 1995. Low-power, miniature, distributed position location and communication devices using ultra-wideband, nonsinusoidal communication technology. Tech. rep., Aetherwire Inc., Semi-Annual Technical Report, ARPA Contract J-FBI-94-058. (July).
• 15: Locating Tiny Sensors in Time and Space: A Case Study, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.214, September 16-18, 2002
• 16: Greenacre, M. J. 1984. Theory and Applications of Correspondence Analysis. Academic Press Inc., London.
• 17: Groenen, P. 1993. The majorization approach to multidimensional scaling: Some problems and extensions. DSWO Press.
• 18: Gupta, P. and Kumar, P. R. 2000. The capacity of wireless networks. IEEE Trans. Inform. Theory 46, 2, 388--404.
• 19: Hashemi, H. 1993. The Indoor Radio Propagation Channel. Proc. IEEE 81, 7 (July), 943--968.
• 20: Ji, X. and Zha, H. 2004. Sensor positioning in wireless ad-hoc sensor networks with multidimensional scaling. In IEEE INFOCOM, 2652--2661.
• 21: Kim, S., Pals, T., Iltis, R., and Lee, H. 2002. CDMA multipath channel estimation using generalized successive interference cancellation algorithm for radiolocation. In 37th Annual Conference on Information Sciences and Systems.
• 22: Kruskal, J. 1964a. Multidimensional scaling by optmizing goodness-of-fit to a nonmetric hypothesis. Psychometrika 29, 1--27.
• 23: Kruskal, J. 1964b. Nonmetric multidimensional scaling: a numerical method. Psychometrika 29, 115--129.
• 24: Lange, K., Hunter, D. R., and Yang, I. 2000. Optimization transfer using surrogate objective functions. J. Computational Graph. Stat. 9, 1 (March), 1--20.
• 25: Moses, R. L., Krishnamurthy, D., and Patterson, R. 2002. An auto-calibration method for unattended ground sensors. In Proceedings of IEEE International Conference on Acoustic Speech and Signal Processing. Vol. 3. 2941--2944.
• 26: Moses, R. L., Krishnamurthy, D., and Patterson, R. 2003. A self-localization method for wireless sensor networks. EURASIP Journal on Applied Sig. Proc. 4 (Mar.), 348--358.
• 27: Nagpal, R., Shrobe, H., and Bachrach, J. 2003. Organizing a global coordinate system from local information on an ad hoc sensor network. In 2nd International Workshop on Information Processing in Sensor Networks.
• 28: Niculescu, D. and Nath, B. 2001. Ad hoc positioning system. In IEEE Globecom 2001. Vol. 5. 2926--2931.
• 29: Dragoş Niculescu , Badri Nath, Error characteristics of ad hoc positioning systems (aps), Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989463]
• 30: Pahlavan, K., Krishnamurthy, P., and Beneat, J. 1998. Wideband radio propagation modeling for indoor geolocation applications. IEEE Comm. Magazine, 60--65.
• 31: Neal Patwari , Alfred O. Hero, III, Using proximity and quantized RSS for sensor localization in wireless networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941354]
• 32: Patwari, N. and Hero III, A. O. 2004. Manifold learning algorithms for localization in wireless sensor networks. In Proceedings of IEEE International Conference on Acoustic Speech and Signal Processing.
• 33: Patwari, N., Hero III, A. O., Perkins, M., Correal, N., and O'Dea, R. J. 2003. Relative location estimation in wireless sensor networks. IEEE Trans. Sig. Proc. 51, 8 (Aug.), 2137--2148.
• 34: Michael Rabbat , Robert Nowak, Distributed optimization in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984626]
• 35: Ramsay, J. 1982. Some statiscal approaches to multidimensional scaling data. J. R. Statist. Soc. A 145, part 3, 285--312.
• 36: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 37: Savarese, C., Rabaey, J. M., and Beutel, J. 2001. Locationing in distributed ad-hoc wireless sensor networks. In Proceedings of IEEE International Conference on Acoustic Speech and Signal Processing. 2037--2040.
• 38: Andreas Savvides , Wendy L. Garber , Randolph L. Moses , Mani B. Srivastava, An Analysis of Error Inducing Parameters in Multihop Sensor Node Localization, IEEE Transactions on Mobile Computing, v.4 n.6, p.567-577, November 2005 [doi>10.1109/TMC.2005.78]
• 39: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 40: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 41: Takane, Y., Young, F., and de Leeuw, J. 1977. Nonmetric individual differences multidimensional scaling: An alternating least squares method with optimal scaling features. Psychometrika 42, 7--67.
• 42: Tenenbaum, J. B., de Silva, V., and Langford, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 2319--2323.
• 43: Zinnes, J. and MacKay, D. 1983. Probabilistic multidimensional scaling: complete and incomplete data. Psychometrika 48, 27--48.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Performance

Keywords:
Distributed optimization, multidimensional scaling, node localization, position estimation, sensor networks