This paper proposes a distributed algorithm for establishing connectivity and location estimation in cluster-based wireless sensor networks. The algorithm exploits the information flow while coping with distributed signal processing and the requirements of network scalability. Once the estimation procedure and communication protocol are performed, sensor clusters can be merged to establish a single global coordinate system without GPS sensors using only distance information. In order to adjust the sensor positions, the refinement schemes and cooperative fusion approaches are applied to reduce the estimation error and improve the measurement accuracy. This paper outlines the technical foundations of the localization techniques and presents the tradeoffs in algorithm design. The feasibility of the proposed schemes is shown to be effective under certain assumptions and the analysis is supported by simulation and numerical studies.
References
[1]
Doucet, A.; de Freitas, N.; Gordon, N. Sequential Monte Carlo Methods in Practice; Springer-Verlag: New York, NY, USA, 2001.
[2]
Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. Novel approach to nonlinear/non-gaussian bayesian state estimation. Proc. IEEE？1993, 140, 107–113.
[3]
Wen, C.Y.; Hsiao, Y.C. Decentralized anchor-free localization for wireless ad-hoc sensor networks. Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Singapore, October 2008; pp. 2777–2785.
[4]
Bahl, P.; Padmanabhan, V.N. RADAR: An in-building rf based user location and tracking system. Proceedings of IEEE INFOCOM, Tel Aviv, Israel, March 26–30, 2000; pp. 775–784.
[5]
Yedavalli, K.; Krishnamachari, B. Sequence-based localization in wireless sensor networks. IEEE Trans. Mob. Comput？2008, 7, 81–94, doi:10.1109/TMC.2008.4387797.
[6]
Savarese, C.; Rabaey, J.M.; Beutel, J. Locating in distributed ad-hoc wireless sensor networks. Proceedings of ICASSP, Salt Lake City, UT, USA, May 7–11, 2001; pp. 2037–2040.
[7]
Savvides, A.; Han, C.C.; Srivastava, M.B. Dynamic fine-grained localization in ad-hoc networks of sensors. Proceedings of ACM SIGMOBILE, Rome, Italy, July 16–21, 2001; pp. 166–179.
[8]
Doherty, L.; Pister, K.; Ghaoui, L.E. Convex position estimation in wireless sensor networks. Proceedings of IEEE INFOCOM, Anchorage, AK, USA, April 2001; pp. 1655–1663.
[9]
Capkun, S.; Hamdi, M.; Hubaux, J.P. GPS-free positioning in mobile ad-hoc networks. Proceedings of the 34th Hawaii International Conference on System Sciences, Maui, HI, USA, January 3–6, 2001; pp. 3481–3490.
[10]
Iyengar, R.; Sikdar, B. Scalable and distributed GPS free positioning for sensor networks. Proceedings of IEEE International Conference on Communications, Anchorage, AK, USA, May 11–15, 2003; pp. 338–342.
[11]
Hightower, J.; Borriello, G. Particle filters for location estimation in ubiquitous computing: A case study. Proceedings of the Sixth International Conference on Ubiquitous Computing, Nottingham, UK, September 7–10, 2004; pp. 88–106.
[12]
Eren, T.; Goldenberg, D.; Whiteley, W.; Yang, Y.R.; Morse, A.S.; Anderson, B.; Belhumeur, P. Rigidity, computation, and randomization in network localization. Proceedings of IEEE INFOCOM, Hong Kong, China, March 7–11, 2004; pp. 2673–2684.
[13]
Savvides, A.; Garber, W.; Adlakha, S.; Moses, R.; Srivastava, M.B. On the error characteristics of multihop node localization in ad-hoc sensor networks. Proceedings of IPSN, Palo Alto, CA, USA, April 22–23, 2003; pp. 317–332.
Kim, Y.G.; Ahn, J.H.; Cha, H.J. Locating acoustic events based on large-scale sensor networks. Sensors？2009, 9, 9925–9944, doi:10.3390/s91209925. 22303155
[16]
Niculescu, D.; Nath, B. DV based positioning in ad hoc networks. Kluwer J. Telecommun. Syst？2003, 22, 267–280, doi:10.1023/A:1023403323460.
[17]
Girod, L. A Self-Calibrating System of Distributed Acoustic Arrays. Ph.D. Thesis, UCLA: Los Angeles, CA, USA. 2005.
[18]
Medidi, M.; Slaaen, R.A.; Zhou, Y.; Mallery, C.J.; Medidi, S. Cluster-based localization in wireless sensor networks. Proceedings of Wireless Sensing and Processing, Kissimmee, FL, USA, April 17–18, 2006; 6248, p. 62480J.
[19]
Chan, H.; Luk, M.; Perrig, A. Using clustering information for sensor networks localization. Proceedings of International Conference on Distributed Computing in Sensor Systems, CA, USA, June 30–July 1, 2005; pp. 109–125.
[20]
Moore, D.; Leonard, J.; Rus, D.; Teller, S. Robust distributed network localization with noisy range measurements. Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys’04), Baltimore, MD, USA, November 3–5, 2004; pp. 50–61.
[21]
Ji, X.; Zha, H. Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling. Proceedings of IEEE INFOCOM, Hong Kong, China, March 7–11, 2004; pp. 2652–2661.
[22]
Priyantha, N.B.; Balakrishnan, H.; Demaine, E.; Teller, S. Anchor-Free Distributed Localization in Sensor Networks. Technical Report No. 892;; MIT Laboratory for Computer Science: Cambridge, MA, USA, 2003.
[23]
Nagpal, R.; Shrobe, H.; Bachrach, J. Organizing a global coordinate system from local information on an ad hoc sensor network. Proceedings of IPSN, Palo Alto, CA, USA, April 22–23, 2003; pp. 333–348.
[24]
Patwari, N.; Hero, A.O.; Perkins, M.; Correal, N.S.; O’Dea, R.J. Relative location estimation in wireless sensor networks. IEEE Trans. Signal Process？2003, 51, 2137–2148, doi:10.1109/TSP.2003.814469.
[25]
Grabowski, R.; Khosla, P. Localization techniques for a team of small robots. Proceedings of IEEE IROS, Maui, HI, USA, October 29–November 3, 2001; pp. 1067–1072.
[26]
Savvides, A.; Park, H.M.; Srivastava, M.B. The bits and flops of the N-hop multilateration primitive for node localization problems. Proceedings of the First ACM International Workshop on Wirless Sensor Networks and Applications, Atlanta, GA, USA, September 28, 2002; pp. 112–121.
[27]
Ihler, A.T.; Fisher, J.W.; Moses, R.L.; Willsky, A.S. Nonparametric belief propagation for self-localization of sensor networks. IEEE J. Select. Areas Commun？2005, 23, 809–819, doi:10.1109/JSAC.2005.843548.
[28]
Savarese, C.; Rabay, J.; Langendoen, K. Robust positioning algorithms for distributed ad hoc wireless sensor networks. Proceedings of USENIX Technical Annual Conference, Monterey, CA, USA, June 10–15, 2002; pp. 317–327.
[29]
Bach, W.; Dam, D.; Evers, L.; Jonker, M.; Scholten, H.; Havinga, P. An iterative quality-based localization algorithm for ad hoc networks. Proceedings of the International Conference on Pervasive Computing, Zurich, Switzerland, August 26–28, 2002; pp. 55–61.
[30]
Chintalapudi, K.K.; Dhariwal, A.; Govindan, R.; Sukhatme, G. Ad hoc localization using ranging and sectoring. Proceedings of INFOCOM, Hong Kong, China, March 7–11, 2004; pp. 2662–2672.
[31]
de Brito, L.M.P.L.; Peralta, L.M.R. An analysis of localization problems and solutions in wireless sensor networks. Tekhne？2008, 9, 146–172.
[32]
Gustafsson, F.; Gunnarsson, F. Mobile positioning using wirelsss networks. IEEE Signal Process. Mag？2005, 22, 41–53, doi:10.1109/MSP.2005.1458284.
[33]
Sayed, A.H.; Tarighat, A.; Khajehnouri, N. Network-based wireless location. IEEE Signal Process. Mag？2005, 22, 24–40, doi:10.1109/MSP.2005.1458275.
[34]
Luo, J.; Shukla, H.V.; Hubaux, J.P. Non-interactive location surveying for sensor networks with mobility-differentiated TOA. Proceedings of the 25th IEEE INFOCOM, Barcelona, Spain, April 23–29, 2006; pp. 1–12.
[35]
Tang, H.; Park, Y.W.; Qiu, T.S. A TOA-AOA-based NLOS error mitigation method for location estimation. EURASIP J. Adv. Signal Process？2008, 8, 1–14.
[36]
Guvenc, I.; Chong, C.C. A survey on TOA based wireless localization and NLOS mitigation techniques. IEEE Commun. Surv. Tutorials？2009, 11, 107–124, doi:10.1109/SURV.2009.090308.
[37]
Savvides, A.; Girod, M.S.L.; Estrin, D. Localization in sensor networks. In Wireless Sensor Networks; Kluwer Academic Publishers: Boston, MA, USA, 2004.
[38]
Wen, C.Y.; Sethares, W.A. Automatic decentralized clustering for wireless sensor networks. EURASIP J. Wirel. Commun. Netw？2005, 5, 686–697.
[39]
Aspnes, J.; Eren, T.; Goldenberg, D.K.; Morse, A.S.; Whiteley, W.; Yang, Y.R.; Anderson, B.D.O.; Belhumeur, P.N. A theory of network localization. IEEE Trans. Mob. Comput？2006, 5, 1663–1678, doi:10.1109/TMC.2006.174.
[40]
Wen, C.Y.; Morris, R.D.; Sethares, W.A. Distance estimation using bidirectional communications without synchronous clocking. IEEE Trans. Signal Process？2007, 55, 1927–1939, doi:10.1109/TSP.2006.889406.
[41]
Chib, S.; Greenberg, E. Understanding the Metropolis-Hastings algorithm. Am. Statist？1995, 49, 327–335.
[42]
Chu, K.T.; Wen, C.Y.; Ouyang, Y.C.; Sethares, W.A. Adaptive distributed topology control for wireless ad hoc sensor networks. Proceedings of the First International Conference on Sensor Technologies and Applications, Valencia, Spain, October 14–20, 2007; pp. 378–386.
[43]
Bachrach, J.; Taylor, C. Localization in sensor networks. In Handbooks of Sensor Networks: Algorithms and Architectures; John Wiley & Sons: Hoboken, NJ, USA, 2005; pp. 277–310.
[44]
Horn, B.K.P.; Hilden, H.; Negahdaripour, S. Closed-form solution of absolute orientation using orthonormal matrices. J. Opt. Soc. Am？1988, 5, 1127–1135, doi:10.1364/JOSAA.5.001127.
[45]
Wang, X.L.; Qi, H.R.; Beck, S.; Du, H.T. Progressive approach to distributed multiple-target detection in sensor networks. In Sensor Network Operations; John Wiley & Sons: Hoboken, NJ, USA, 2006; pp. 486–503.
[46]
Hanebeck, U.D.; Briechle, K.; Rau, A. Progressive bayes: A new framework for nonlinear state estimation. Proceedings of SPIE AeroSense Symposium, Orlando, FL, USA, April 21, 2003; 5099, pp. 256–267.
Stone, M. The opinion pool. Ann. Stat？1961, 32, 1339–1342, doi:10.1214/aoms/1177704873.
[49]
Zhao, F.; Guibas, L. Wireless Sensor Networks: An Information Processing Approach; Morgan Kaufmann: San Fransisco, CA, USA, 2004.
[50]
Pinheiro, P.; Lima, P. Bayesian sensor fusion for cooperative object localization and world modeling. Proceedings of the 8th Conference on Intelligent Autonomous Systems, Amsterdam, The Netherlands, March 10–13, 2004; pp. 1–8.
[51]
Julier, S.; Uhlmann, J. General decentralized data fusion with covariance intersection (CI). In Handbook of Multisensor Data Fusion; CRC Press: Boca Raton, FL, USA, 2001.
[52]
Wen, C.Y.; Chen, J.K.; Sethare, W.A. Asynchronous two-way ranging using Tomlinson-Harashima precoding and UWB signaling. EURASIP J. Wirel. Commun. Netw？2008, 8, 1–13.
[53]
Davies, R.B. Algorithm AS 155: The distribution of a linear combination of χ2 random variables. Appl. Statist？1980, 29, 323–333, doi:10.2307/2346911.
[54]
Imhof, J.P. Computing the distribution of quadratic forms in normal variables. Biometrika？1961, 48, 419–426.
[55]
Fieller, E. The distribution of the index in a normal bivariate population. Biometrika？1932, 24, 428–440.
[56]
Ware, R.; Lad, F. Approximating the Distribution for Sum of Product of Normal Variables. Research Report;; Mathematics and Statistics Department, Canterbury University: Christchurch, New Zealand, 2003.
[57]
Hinkley, D. On the ratio of two correlated normal random variables. Biometrika？1969, 56, 635–639, doi:10.1093/biomet/56.3.635.
[58]
Leone, F.C.; Nelson, L.S.; Nottingham, R.B. The folded normal distribution. Technometrics？1961, 3, 543–550, doi:10.1080/00401706.1961.10489974.
[59]
Roberts, G.; Gelman, A.; Gilks, W. Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms. Technical Report;; University of Cambridge: Cambridge, UK, 1994.
[60]
Bulusu, N.; Heidemann, J.; Estrin, D. GPS-less low-cost outdoor localization for very small devices. IEEE Person. Commun？2000, 7, 28–34.
[61]
Hightower, J.; Borriello, G.; Want, R. SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength. UW CSE Technical Report 00-02-02;; University of Washington: Washington, DC, USA, 2002.
[62]
Coxon, A. The User’s Guide to Multidimensional Scaling; Heinemann Educational Books: London, UK, 1982.
