Location awareness is a key enabling feature and fundamental challenge in present and future wireless networks. Most existing localization methods rely on existing infrastructure and thus lack the flexibility and robustness necessary for large ad hoc networks. In this paper, we build upon SPAWN (sum-product algorithm over a wireless network), which determines node locations through iterative message passing, but does so at a high computational cost. We compare different message representations for SPAWN in terms of performance and complexity and investigate several types of cooperation based on censoring. Our results, based on experimental data with ultra-wideband (UWB) nodes, indicate that parametric message representation combined with simple censoring can give excellent performance at relatively low complexity. 1. Introduction Location awareness has the potential to revolutionize a diverse array of present and future technologies. Accurate knowledge of a user's location is essential for a wide variety of commercial, military, and social applications, including next-generation cellular services [1, 2], sensor networks [3, 4], search-and-rescue [5, 6], military target tracking [7, 8], health care monitoring [9, 10], robotics [11, 12], data routing [13, 14], and logistics [15, 16]. Typically, only a small fraction of the nodes in the network, known as anchors, have prior knowledge about their location. The remaining nodes, known as agents, must determine their locations through a process of localization or positioning. The ad hoc and often dynamic nature of wireless networks requires distributed and autonomous localization methods. Moreover, location-aware wireless networks are frequently deployed in unknown environments and hence can rely only on minimal (if any) infrastructure, human maintenance, and a priori location information. Cooperation is an emerging paradigm for localization in which agents take advantage of network connections and interagent measurements to improve their location estimates. Non-Bayesian cooperative localization in wireless sensor networks is discussed in [17]. Different variations of Bayesian cooperation have been considered, including Monte-Carlo sequential estimation [18] and nonparametric belief propagation in static networks [19]. For a comprehensive overview of Bayesian and non-Bayesian cooperative localization in wireless networks, we refer the reader to [20], which also introduces a distributed cooperative algorithm for large-scale mobile networks called SPAWN (sum-product algorithm over a wireless network). This
References
[1]
J. J. Caffery and G. L. Stüber, “Overview of radiolocation in CDMA cellular systems,” IEEE Communications Magazine, vol. 36, no. 4, pp. 38–45, 1998.
[2]
A. H. Sayed, A. Tarighat, and N. Khajehnouri, “Network-based wireless location: challenges faced in developing techniques for accurate wireless location information,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 24–40, 2005.
[3]
A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, “Wireless sensor networks for habitat monitoring,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA '02), pp. 88–97, ACM Press, September 2002.
[4]
T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03), pp. 81–95, September 2003.
[5]
K. Pahlavan, X. Li, and J. P. M？kel？, “Indoor geolocation science and technology,” IEEE Communications Magazine, vol. 40, no. 2, pp. 112–118, 2002.
[6]
S. J. Ingram, D. Harmer, and M. Quinlan, “Ultrawideband indoor positioning systems and their use in emergencies,” in Proceedings of the Position Location and Navigation Symposium (PLANS '04), pp. 706–715, April 2004.
[7]
C.-Y. Chong and S. P. Kumar, “Sensor networks: evolution, opportunities, and challenges,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1247–1256, 2003.
[8]
H. Yang and B. Sikdar, “A protocol for tracking mobile targets using sensor networks,” in Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications, pp. 71–81, May 2003.
[9]
X. Ji and H. Zha, “Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04), vol. 4, pp. 2652–2661, March 2004.
[10]
R. A. Marjamaa, P. M. Torkki, M. I. Torkki, and O. A. Kirvel？, “Time accuracy of a radio frequency identification patient tracking system for recording operating room timestamps,” Anesthesia & Analgesia, vol. 102, no. 4, pp. 1183–1186, 2006.
[11]
D. Fox, W. Burgard, F. Dellaert, and S. Thrun, “Monte Carlo localization: efficient position estimation for mobile robots,” in Proceedings of the 16th National Conference on Artificial Intelligence (AAAI '99), pp. 343–349, Orlando, Fla, USA, July 1999.
[12]
J. J. Leonard and H. F. Durrant-Whyte, “Mobile robot localization by tracking geometric beacons,” IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 376–382, 1991.
[13]
R. Jain, A. Puri, and R. Sengupta, “Geographical routing using partial information for wireless ad hoc networks,” IEEE Personal Communications, vol. 8, no. 1, pp. 48–57, 2001.
[14]
H. Frey, “Scalable geographic routing algorithms for wireless ad hoc networks,” IEEE Network, vol. 18, no. 4, pp. 18–22, 2004.
[15]
R. J. Fontana and S. J. Gunderson, “Ultra-wideband precision asset location system,” in Proceedings of IEEE Conference on Ultra Wideband Systems and Technologies (UWBST '02), vol. 21, no. 1, pp. 147–150, Baltimore, Md, USA, May 2002.
[16]
W. C. Chung and D. Ha, “An accurate ultra wideband (UWB) ranging for precision asset location,” in Proceedings of IEEE Conference on Ultra Wideband Systems and Technologies (UWBST '03), pp. 389–393, November 2003.
[17]
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, vol. 22, no. 4, pp. 54–69, 2005.
[18]
M. Castillo-Effen, W. A. Moreno, M. A. Labrador, and K. P. Valavanis, “Adapting sequential Monte-Carlo estimation to cooperative localization in wireless sensor networks,” in Proceedings of IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems (MASS '06), pp. 656–661, Vancouver, Canada, October 2006.
[19]
A. T. Ihler, J. W. Fisher III, R. L. Moses, and A. S. Willsky, “Nonparametric belief propagation for self-localization of sensor networks,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 809–819, 2005.
[20]
H. Wymeersch, J. Lien, and M. Z. Win, “Cooperative localization in wireless networks,” Proceedings of the IEEE, vol. 97, no. 2, pp. 427–450, 2009.
[21]
A. T. Ihler, J. W. Fisher, and A. S. Willsky, “Particle filtering under communications constraints,” in Proceedings of the 13th IEEE/SP Workshop on Statistical Signal Processing, pp. 89–94, Bordeaux, France, July 2005.
[22]
M. Welling and J. J. Lim, “A distributed message passing algorithm for sensor localization,” in Proceedings of the 17th International Conference on Artificial Neural Networks (ICANN '07), pp. 767–775, September 2007.
[23]
C. Pedersen, T. Pedersen, and B. H. Fleury, “A variational message passing algorithm for sensor self-localization in wireless networks,” in Proceedings of IEEE International Symposium on Information Theory Proceedings (ISIT '11), pp. 2158–2162, Saint-Petersburg, Russia, July 2011.
[24]
M. Caceres, F. Penna, H. Wymeersch, and R. Garello, “Hybrid cooperative positioning based on distributed belief propagation,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 10, pp. 1948–1958, 2011.
[25]
M. Z. Win and R. A. Scholtz, “Characterization of ultra-wide bandwidth wireless indoor channels: a communication-theoretic view,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 9, pp. 1613–1627, 2002.
[26]
M. Z. Win and R. A. Scholtz, “On the robustness of ultra-wide bandwidth signals in dense multipath environments,” IEEE Communications Letters, vol. 2, no. 2, pp. 51–53, 1998.
[27]
A. F. Molisch, J. R. Foerster, and M. Pendergrass, “Channel models for ultrawideband personal area networks,” IEEE Wireless Communications, vol. 10, no. 6, pp. 14–21, 2003.
[28]
J.-Y. Lee and R. A. Scholtz, “Ranging in a dense multipath environment using an UWB radio link,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 9, pp. 1677–1683, 2002.
[29]
D. Dardari, A. Conti, U. Ferner, A. Giorgetti, and M. Z. Win, “Ranging with ultrawide bandwidth signals in multipath environments,” Proceedings of the IEEE, vol. 97, no. 2, pp. 404–425, 2009.
[30]
W. Suwansantisuk and M. Z. Win, “Multipath aided rapid acquisition: optimal search strategies,” IEEE Transactions on Information Theory, vol. 53, no. 1, pp. 174–193, 2007.
[31]
H. Xu and L. Yang, “Timing with dirty templates for low-resolution digital UWB receivers,” IEEE Transactions on Wireless Communications, vol. 7, no. 1, pp. 54–59, 2008.
[32]
M. Z. Win, P. C. Pinto, and L. A. Shepp, “A mathematical theory of network interference and its applications,” Proceedings of the IEEE, vol. 97, no. 2, pp. 205–230, 2009.
[33]
N. C. Beaulieu and D. J. Young, “Designing time-hopping ultrawide bandwidth receivers for multiuser interference environments,” Proceedings of the IEEE, vol. 97, no. 2, pp. 255–284, 2009.
[34]
M. Z. Win, G. Chrisikos, and A. F. Molisch, “Wideband diversity in multipath channels with nonuniform power dispersion profiles,” IEEE Transactions on Wireless Communications, vol. 5, no. 5, pp. 1014–1022, 2006.
[35]
M. Z. Win, G. Chrisikos, and N. R. Sollenberger, “Performance of Rake reception in dense multipath channels: implications of spreading bandwidth and selection diversity order,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 8, pp. 1516–1525, 2000.
[36]
C. Falsi, D. Dardari, L. Mucchi, and M. Z. Win, “Time of arrival estimation for UWB localizers in realistic environments,” EURASIP Journal on Advances in Signal Processing, vol. 2006, Article ID 32082, pp. 1–13, 2006.
[37]
S. Venkatesh and R. M. Buehrer, “Non-line-of-sight identification in ultra-wideband systems based on received signal statistics,” IET Microwaves, Antennas & Propagation, vol. 1, no. 6, pp. 1120–1130, 2007.
[38]
D. B. Jourdan, J. J. Deyst Jr., M. Z. Win, and N. Roy, “Monte Carlo localization in dense multipath environments using UWB ranging,” in Proceedings of IEEE International Conference on Ultra-Wideband (ICU '05), pp. 314–319, September 2005.
[39]
S. Venkatesh and R. M. Buehrer, “Multiple-access design for ad hoc UWB position-location networks,” in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC '06), vol. 4, pp. 1866–1873, Las Vegas, Nev, USA, April 2006.
[40]
D. Dardari, A. Conti, J. Lien, and M. Z. Win, “The effect of cooperation on UWB-based positioning systems using experimental data,” EURASIP Journal on Advances in Signal Processing, vol. 2008, Article ID 513873, 2008.
[41]
S. Venkatesh and R. M. Buehrer, “Power control in UWB position-location networks,” in Proceedings of IEEE International Conference on Communications (ICC '06), vol. 9, pp. 3953–3959, Istanbul, Turkey, June 2006.
[42]
W. C. Headley, C.R.C.M. da Suva, and R. M. Buehrer, “Indoor location positioning of non-active objects using ultra-wideband radios,” in Proceedings of IEEE Radio and Wireless Symposium (RWS '07), pp. 105–108, Long Beach, Calif, USA, January 2007.
[43]
D. B. Jourdan, D. Dardari, and M. Z. Win, “Position error bound for UWB localization in dense cluttered environments,” IEEE Transactions on Aerospace and Electronic Systems, vol. 44, no. 2, pp. 613–628, 2008.
[44]
Y. Shen and M. Z. Win, “Fundamental limits of wideband localization—part I: a general framework,” IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 4956–4980, 2010.
[45]
Y. Shen, H. Wymeersch, and M. Z. Win, “Fundamental limits of wideband localization—part II: cooperative networks,” IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 4981–5000, 2010.
[46]
Y. Shen and M. Z. Win, “On the accuracy of localization systems using wideband antenna arrays,” IEEE Transactions on Communications, vol. 58, no. 1, pp. 270–280, 2010.
[47]
S. Gezici, Z. Tian, G. B. Giannakis et al., “Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 70–84, 2005.
[48]
I. Oppermann, M. H？m？l？inen, and J. Iinatti, UWB Theory and Applications, John Wiley & Sons, 2004.
[49]
H. Wymeersch, Iterative Receiver Design, Cambridge University Press, 2007.
[50]
D. Fox, W. Burgard, H. Kruppa, and S. Thrun, “A Monte Carlo algorithm for multi-robot localization,” Tech. Rep. CMU-CS-99-120, Computer Science Department, Carnegie Mellon University, Pittsburgh, Pa, USA, 1999.
[51]
D. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge University Press, 2003.
[52]
A. Doucet, S. Godsill, and C. Andrieu, “On sequential Monte Carlo sampling methods for Bayesian filtering,” Statistics and Computing, vol. 10, no. 3, pp. 197–208, 2000.
[53]
Z. Botev, Nonparametric Density Estimation Via Diffusion Mixing, Postgraduate Series, The University of Queensland, 2007, http://espace.library.uq.edu.au/view/UQ:120006.
[54]
J. Lien, A framework for cooperative localization in ultra-wideband wireless networks [M.S. thesis], Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Mass, USA, 2007.
