Skip to main content
Erschienen in: Wireless Networks 4/2009

01.05.2009

Sequential Monte Carlo localization in mobile sensor networks

verfasst von: Weidong Wang, Qingxin Zhu

Erschienen in: Wireless Networks | Ausgabe 4/2009

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Node localization in wireless sensor networks is essential to many applications such as routing protocol, target tracking and environment surveillance. Many localization schemes have been proposed in the past few years and they can be classified into two categories: range-based and range-free. Since range-based techniques need special hardware, which increases the localization cost, many researchers now focus on the range-free techniques. However, most of the range-free localization schemes assume that the sensor nodes are static, the network topology is known in advance, and the radio propagation is perfect circle. Moreover, many schemes need densely distributed anchor nodes whose positions are known in advance in order to estimate the positions of the unknown nodes. These assumptions are not practical in real network. In this paper, we consider the sensor networks with sparse anchor nodes and irregular radio propagation. Based on Sequential Monte Carlo method, we propose an alterative localization method—Sequential Monte Carlo Localization scheme (SMCL). Unlike many previously proposed methods, our work takes the probabilistic approach, which is suitable for the mobile sensor networks because both anchors and unknown nodes can move, and the network topology need not be formed beforehand. Moreover, our algorithm is scalable and can be used in large-scale sensor networks. Simulation results show that SMCL has better localization accuracy and it can localize more sensor nodes when the anchor density is low. The communication overhead of SMCL is also lower than other localization algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Hightower, J., & Borriello, G. (2001). Location systems for ubiquitous computing. IEEE Computer, 34(8), 57–66. Hightower, J., & Borriello, G. (2001). Location systems for ubiquitous computing. IEEE Computer, 34(8), 57–66.
2.
Zurück zum Zitat Wellenhoff, B. H., Lichtenegger, H., & Collins, J. (1997). Global positioning system: Theory and practice (4th ed). New York, LLC: Springer-Verlag. Wellenhoff, B. H., Lichtenegger, H., & Collins, J. (1997). Global positioning system: Theory and practice (4th ed). New York, LLC: Springer-Verlag.
3.
Zurück zum Zitat Jourdan, D. B., Deyst, J. J., Jr., Win, M. Z., & Roy, N. (2005). Monte Carlo localization in dense multipath environments using UWB ranging. In Proceedings of ICU 2005 (pp. 314–319). Zurich, Switzerland: IEEE Press. Jourdan, D. B., Deyst, J. J., Jr., Win, M. Z., & Roy, N. (2005). Monte Carlo localization in dense multipath environments using UWB ranging. In Proceedings of ICU 2005 (pp. 314–319). Zurich, Switzerland: IEEE Press.
4.
Zurück zum Zitat Goldenberg, D. K., Krishnamurthy, A., Maness, W. C., Yang, Y. R., Young, A., Stephen Morse, A., Savvides, A., & Anderson, B. D. O. (2005). Network localization in partially localizable networks. In Proceedings of INFOCOM 2005 (Vol. 1, pp. 313–326). Miami, FL, USA: IEEE Press. Goldenberg, D. K., Krishnamurthy, A., Maness, W. C., Yang, Y. R., Young, A., Stephen Morse, A., Savvides, A., & Anderson, B. D. O. (2005). Network localization in partially localizable networks. In Proceedings of INFOCOM 2005 (Vol. 1, pp. 313–326). Miami, FL, USA: IEEE Press.
5.
Zurück zum Zitat Zaruba, G. V., Huber, M., & Kamangar, F. A. (2004). Monte Carlo sampling based in-home location tracking with minimal RF infrastructure requirements. In Proceedings of the IEEE Globecom 2004 (Vol. 6, pp. 3624–3629). Dallas, TX, USA: IEEE Press. Zaruba, G. V., Huber, M., & Kamangar, F. A. (2004). Monte Carlo sampling based in-home location tracking with minimal RF infrastructure requirements. In Proceedings of the IEEE Globecom 2004 (Vol. 6, pp. 3624–3629). Dallas, TX, USA: IEEE Press.
6.
Zurück zum Zitat Savvides, A., Han, C.-C., & Strivastava, M. B. (2001). Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of MobiCom’01 (pp. 166–179). Rome, Italy: ACM Press. Savvides, A., Han, C.-C., & Strivastava, M. B. (2001). Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of MobiCom’01 (pp. 166–179). Rome, Italy: ACM Press.
7.
Zurück zum Zitat Niculescu, D., & Nath, B. (2003). Ad hoc positioning system (APS) using AOA. In Proceedings of INFOCOM 2003 (pp. 1734–1743). San Francisco, CA, USA: IEEE Press. Niculescu, D., & Nath, B. (2003). Ad hoc positioning system (APS) using AOA. In Proceedings of INFOCOM 2003 (pp. 1734–1743). San Francisco, CA, USA: IEEE Press.
8.
Zurück zum Zitat McGuire, M., Plataniotis, K. N., & Venetsanopoulos, A. N. (2003). Location of mobile terminals using time measurements and survey points. IEEE Transactions Vehicular Technology, 52(4), 999–1011.CrossRef McGuire, M., Plataniotis, K. N., & Venetsanopoulos, A. N. (2003). Location of mobile terminals using time measurements and survey points. IEEE Transactions Vehicular Technology, 52(4), 999–1011.CrossRef
9.
Zurück zum Zitat Patwari, N., & Hero, A. O., III. (2003). Using proximity and quantized RSS for sensor localization in wireless networks. In Proceedings of IEEE/ACM WSNA’03 (pp. 20–29). San Diego, CA, USA: ACM Press. Patwari, N., & Hero, A. O., III. (2003). Using proximity and quantized RSS for sensor localization in wireless networks. In Proceedings of IEEE/ACM WSNA’03 (pp. 20–29). San Diego, CA, USA: ACM Press.
10.
Zurück zum Zitat Niculescu, D., & Nath, B. (2003). DV based positioning in ad hoc networks. Kluwer Journal of Telecommunication Systems, 22, 267–280.CrossRef Niculescu, D., & Nath, B. (2003). DV based positioning in ad hoc networks. Kluwer Journal of Telecommunication Systems, 22, 267–280.CrossRef
11.
Zurück zum Zitat Bulusu, N., Heidemann J., & Estrin, D. (2001). Density adaptive algorithms for beacon placement in wireless sensor networks. In Proceedings of IEEE ICDCS’01. Phoenix, AZ, USA: IEEE Press. Bulusu, N., Heidemann J., & Estrin, D. (2001). Density adaptive algorithms for beacon placement in wireless sensor networks. In Proceedings of IEEE ICDCS’01. Phoenix, AZ, USA: IEEE Press.
12.
Zurück zum Zitat Bulusu, N., Heidemann, J., & Estrin, D. (2000). GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications, Special Issue on "Smart Spaces and Environments", 7(5), 28–34. Bulusu, N., Heidemann, J., & Estrin, D. (2000). GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications, Special Issue on "Smart Spaces and Environments", 7(5), 28–34.
13.
Zurück zum Zitat He, T., Huang, C., Blum, B. M., Stankovic, J. A., & Abdelzaher, T. (2003). Range-free localization schemes for large scale sensor networks. In Proceedings of MobiCom’03 (pp. 81–95). San Diego, CA, USA: ACM Press. He, T., Huang, C., Blum, B. M., Stankovic, J. A., & Abdelzaher, T. (2003). Range-free localization schemes for large scale sensor networks. In Proceedings of MobiCom’03 (pp. 81–95). San Diego, CA, USA: ACM Press.
15.
Zurück zum Zitat Savvides, A., Girod, L., Srivastava, M. B., & Estrin, D. (2004). Localization in sensor networks. In Proceedings of Wireless Sensor Networks (pp. 327–349). Kluwer Academic Publishers. Savvides, A., Girod, L., Srivastava, M. B., & Estrin, D. (2004). Localization in sensor networks. In Proceedings of Wireless Sensor Networks (pp. 327–349). Kluwer Academic Publishers.
16.
Zurück zum Zitat Nagpal, R. (1999). Organizing a global coordinate system from local information on an Amorphous Computer, A.I. Memo No. 1666, MIT AI Laboratory. Nagpal, R. (1999). Organizing a global coordinate system from local information on an Amorphous Computer, A.I. Memo No. 1666, MIT AI Laboratory.
17.
Zurück zum Zitat Nagpal, R., Shrobe, H., & Bachrach, J. (2003). Organizing a global coordinate system from local information on an ad hoc sensor network. In Proceedings of IPSN ’03 (pp. 333–348). Palo Alto, CA, USA: Springer. Nagpal, R., Shrobe, H., & Bachrach, J. (2003). Organizing a global coordinate system from local information on an ad hoc sensor network. In Proceedings of IPSN ’03 (pp. 333–348). Palo Alto, CA, USA: Springer.
18.
Zurück zum Zitat Wang, W., & Zhu, Q. (2006). High accuracy geometric localization scheme for wireless sensor networks. In Proceedings of International Conference on Communications, Circuits and Systems (ICCCAS) (Vol. 3, pp. 1507–1512). Guilin, China: IEEE Press. Wang, W., & Zhu, Q. (2006). High accuracy geometric localization scheme for wireless sensor networks. In Proceedings of International Conference on Communications, Circuits and Systems (ICCCAS) (Vol. 3, pp. 1507–1512). Guilin, China: IEEE Press.
19.
Zurück zum Zitat Galstyan, A., Krishnamachari, B., Lerman, K., & Pattem, S. (2004). Distributed online localization in sensor networks using a moving target. In Proceedings of the Third ACM International Symposium on Information Processing In Sensor Networks, (pp. 61–70). Berkeley, CA, USA: ACM Press. Galstyan, A., Krishnamachari, B., Lerman, K., & Pattem, S. (2004). Distributed online localization in sensor networks using a moving target. In Proceedings of the Third ACM International Symposium on Information Processing In Sensor Networks, (pp. 61–70). Berkeley, CA, USA: ACM Press.
20.
Zurück zum Zitat Liu, C., Wu, K., & He, T. (2004). Sensor localization with ring overlapping based on comparison of received signal strength indicator. In Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems (pp. 516–518). Fort Lauderdale, FL, USA: IEEE Press. Liu, C., Wu, K., & He, T. (2004). Sensor localization with ring overlapping based on comparison of received signal strength indicator. In Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems (pp. 516–518). Fort Lauderdale, FL, USA: IEEE Press.
21.
Zurück zum Zitat Dellaert, F., Fox, D., Burgard, W., & Thrun, S. (1999). Monte Carlo localization for mobile robots. In Proceedings of IEEE International Conference on Robotics and Automation (ICRA99), (Vol. 2, pp. 1322–1328). Detroit, MI, USA: IEEE Robotics and Automation Society. Dellaert, F., Fox, D., Burgard, W., & Thrun, S. (1999). Monte Carlo localization for mobile robots. In Proceedings of IEEE International Conference on Robotics and Automation (ICRA99), (Vol. 2, pp. 1322–1328). Detroit, MI, USA: IEEE Robotics and Automation Society.
22.
Zurück zum Zitat Thrun, S., Fox, D., Burgard, W., & Frank, D. (2001). Robust Monte Carlo localization for mobile robots. Artificial Intelligence Journal, 128(1–2), 99–141.MATHCrossRef Thrun, S., Fox, D., Burgard, W., & Frank, D. (2001). Robust Monte Carlo localization for mobile robots. Artificial Intelligence Journal, 128(1–2), 99–141.MATHCrossRef
23.
Zurück zum Zitat Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O. III, Moses, R. L., & Correal, N. S. (2005). Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Processing Magazine, Special issue on Signal Processing in Positioning and Navigation, 22(4), 54–69. Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O. III, Moses, R. L., & Correal, N. S. (2005). Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Processing Magazine, Special issue on Signal Processing in Positioning and Navigation, 22(4), 54–69.
24.
Zurück zum Zitat Biswas, R., Thrun, S., & Guibas, L. (2004). A probabilistic approach to inference with limited information in sensor networks. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (pp. 269–276). Berkeley, CA, USA: ACM Press. Biswas, R., Thrun, S., & Guibas, L. (2004). A probabilistic approach to inference with limited information in sensor networks. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (pp. 269–276). Berkeley, CA, USA: ACM Press.
25.
Zurück zum Zitat Henderson, T. C., Grant, E., & Luthy, K. (2005). Precision localization in Monte Carlo sensor networks. In Proceedings of the 18th International Conference on Computer Applications in Industry and Engineering (pp. 26–31). Honolulu, HI, USA: ISCA. Henderson, T. C., Grant, E., & Luthy, K. (2005). Precision localization in Monte Carlo sensor networks. In Proceedings of the 18th International Conference on Computer Applications in Industry and Engineering (pp. 26–31). Honolulu, HI, USA: ISCA.
26.
Zurück zum Zitat Hu, L., & Evans, D. (2004). Localization for mobile sensor networks. In Proceedings of MobiCom 2004 (pp. 45–57). Philadelphia, PA, USA: ACM Press. Hu, L., & Evans, D. (2004). Localization for mobile sensor networks. In Proceedings of MobiCom 2004 (pp. 45–57). Philadelphia, PA, USA: ACM Press.
27.
Zurück zum Zitat Handschin, J. E. (1970). Monte Carlo techniques for prediction and filtering of non-linear stochastic processes. Automatica, 6, 555–563.MATHCrossRefMathSciNet Handschin, J. E. (1970). Monte Carlo techniques for prediction and filtering of non-linear stochastic processes. Automatica, 6, 555–563.MATHCrossRefMathSciNet
28.
Zurück zum Zitat Bucy, R., & Senne, K. (1971). Digital synthesis of nonlinear filter. Automatica, 7, 287–298.MATHCrossRef Bucy, R., & Senne, K. (1971). Digital synthesis of nonlinear filter. Automatica, 7, 287–298.MATHCrossRef
29.
Zurück zum Zitat Isard, M., & Blake, A. (1996). Contour tracking by stochastic propagation of conditional density. In Proceedings of the 4th European Conference on Computer Vision-Volume I (pp. 343–356). Cambridge, UK: Springer. Isard, M., & Blake, A. (1996). Contour tracking by stochastic propagation of conditional density. In Proceedings of the 4th European Conference on Computer Vision-Volume I (pp. 343–356). Cambridge, UK: Springer.
30.
Zurück zum Zitat Doucet, A., Godsill, S., & Andrieu, C. (2000). On Sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 10, 197–208.CrossRef Doucet, A., Godsill, S., & Andrieu, C. (2000). On Sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 10, 197–208.CrossRef
31.
Zurück zum Zitat Doucet, A., de Freitas, N., & Gordon, N. (2001). An introduction to sequential Monte Carlo methods. In A. Doucet, N. de Freitas, & N. Gordon (eds.). Sequential Monte Carlo methods in practice. New York: Springer-Verlag. Doucet, A., de Freitas, N., & Gordon, N. (2001). An introduction to sequential Monte Carlo methods. In A. Doucet, N. de Freitas, & N. Gordon (eds.). Sequential Monte Carlo methods in practice. New York: Springer-Verlag.
32.
Zurück zum Zitat Maybeck, P. S. (1979). Stochastic models, estimation and control (Vol. 1). New York: Academic Press.MATH Maybeck, P. S. (1979). Stochastic models, estimation and control (Vol. 1). New York: Academic Press.MATH
33.
Zurück zum Zitat Anderson, B. D. O., & Moore, J. B. (1979). Optimal filtering. NJ: Prentice-Hall.MATH Anderson, B. D. O., & Moore, J. B. (1979). Optimal filtering. NJ: Prentice-Hall.MATH
34.
Zurück zum Zitat Gordon, N. J., Salmond, D. J., & Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimate. IEE Proceedings, 140, 107–113. Gordon, N. J., Salmond, D. J., & Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimate. IEE Proceedings, 140, 107–113.
35.
Zurück zum Zitat Arulampalam, S., Maksell, S., Gordon, N., & Clapp, T. (2002). A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking. IEEE Transactions of Signal Processing, 50(2), 174–188.CrossRef Arulampalam, S., Maksell, S., Gordon, N., & Clapp, T. (2002). A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking. IEEE Transactions of Signal Processing, 50(2), 174–188.CrossRef
36.
Zurück zum Zitat Camp, T., Boleng, J., & Davies, V. (2002). A survey of mobility models for ad Hoc networks research. Wireless Communications and Mobile Computing, 2(5), 483–502.CrossRef Camp, T., Boleng, J., & Davies, V. (2002). A survey of mobility models for ad Hoc networks research. Wireless Communications and Mobile Computing, 2(5), 483–502.CrossRef
37.
Zurück zum Zitat Zhou, G., He, T., Krishnamurthy, S., & Stankovic, J. A. (2004). Impact of radio irregularity on wireless sensor networks. In Proceedings of MobiSys 2004 (pp. 125–138). Boston, MA, USA: ACM Press. Zhou, G., He, T., Krishnamurthy, S., & Stankovic, J. A. (2004). Impact of radio irregularity on wireless sensor networks. In Proceedings of MobiSys 2004 (pp. 125–138). Boston, MA, USA: ACM Press.
38.
Zurück zum Zitat Zhou, G., He, T., Krishnamurthy, S., & Stankovic, J. A. (2006). Models and solutions for radio irregularity in wireless sensor networks. ACM Transactions on Sensor Networks, 2(2), 221–262.CrossRef Zhou, G., He, T., Krishnamurthy, S., & Stankovic, J. A. (2006). Models and solutions for radio irregularity in wireless sensor networks. ACM Transactions on Sensor Networks, 2(2), 221–262.CrossRef
Metadaten
Titel
Sequential Monte Carlo localization in mobile sensor networks
verfasst von
Weidong Wang
Qingxin Zhu
Publikationsdatum
01.05.2009
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 4/2009
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-007-0064-3

Weitere Artikel der Ausgabe 4/2009

Wireless Networks 4/2009 Zur Ausgabe

Neuer Inhalt