This research presents a distributed and formula-based bilateration algorithm that can be used to provide initial set of locations. In this scheme each node uses distance estimates to anchors to solve a set of circle-circle intersection (CCI) problems, solved through a purely geometric formulation. The resulting CCIs are processed to pick those that cluster together and then take the average to produce an initial node location. The algorithm is compared in terms of accuracy and computational complexity with a Least-Squares localization algorithm, based on the Levenberg–Marquardt methodology. Results in accuracy vs. computational performance show that the bilateration algorithm is competitive compared with well known optimized localization algorithms.
References
[1]
Zhong, Z.; Wang, D.; He, T. Sensor Node Localization Using Uncontrolled Events. Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS ’08), Beijing, China, 17–20 June 2008; pp. 438–445.
[2]
Youssef, A.; Youssef, M. A Taxonomy of Localization Schemes for Wireless Sensor Networks. Proceedings of the International Conference on Wireless Networks, Las Vegas, NV, USA, 25–28 June 2007.
[3]
Chan, F.; So, H. Accurate distributed range-based positioning algorithm for wireless sensor networks. IEEE Trans. Signal Process 2009, 57, 4100–4105.
[4]
Niculescu, D.; Nath, B. DV based positioning in ad hoc networks. Telecommun. Syst 2003, 22, 267–280.
[5]
He, T.; Huang, C.; Blum, B.; Stankovic, J.; Abdelzaher, T. Range-free localization and its impact on large scale sensor networks. ACM Trans. Embed. Comput. Syst 2005, 4, 877–906.
[6]
Stoleru, R.; Stankovic, J. Probability Grid: A Location Estimation Scheme for Wireless Sensor Networks. Proceedings of the 2004 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON ’04), Santa Clara, CA, USA, 4–7 October 2004; pp. 430–438.
[7]
Goldenberg, D.; Bihler, P.; Cao, M.; Fang, J.; Anderson, B.; Morse, A.; Yang, Y. Localization in Sparse Networks Using Sweeps. Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, Los Angeles, CA, USA, 24–29 September 2006; pp. 110–121.
[8]
Akyildiz, I.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E. A survey on sensor networks. IEEE Commun. Mag 2002, 40, 102–114.
[9]
Gezici, S. A survey on wireless position estimation. Wirel. Pers. Commun 2008, 44, 263–282.
[10]
Li, M.; Liu, Y. Rendered path: Range-free localization in anisotropic sensor networks with holes. IEEE/ACM Trans. Netw 2010, 18, 320–332.
[11]
Jordt, G.; Baldwin, R.; Raquet, J.; Mullins, B. Energy cost and error performance of range-aware, anchor-free localization algorithms. Ad Hoc Netw 2008, 6, 539–559.
Stoleru, R.; He, T.; Stankovic, J. Range-Free Localization. In Secure Localization and Time Synchronization for Wireless Sensor and Ad Hoc Networks; Springer: Berlin, Germany, 2007; pp. 3–31.
[14]
Yu, K.; Guo, Y. Robust Localization in Multihop Wireless Sensor Networks. Proceedings of the Vehicular Technology Conference (VTC Spring 2008), Singapore, 11–14 May 2008; pp. 2819–2823.
[15]
Moses, R.; Krishnamurthy, D.; Patterson, R. A self-localization method for wireless sensor networks. EURASIP J. Appl. Signal Process 2003, 4, 348–358.
[16]
Doherty, L.; El Ghaoui, L. Convex Position Estimation in Wireless Sensor Networks. Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’01), Anchorage, AK, USA, 22–26 April 2001; 3, pp. 1655–1663.
[17]
Chan, F.; So, H. Efficient weighted multidimensional scaling for wireless sensor network localization. IEEE Trans. Signal Process 2009, 57, 4548–4553.
[18]
Weng, Y.; Xiao, W.; Xie, L. Diffusion-based em algorithm for distributed estimation of gaussian mixtures in wireless sensor networks. Sensors 2011, 11, 6297–6316.
[19]
Liu, J.; Zhang, Y.; Zhao, F. Robust Distributed Node Localization with Error Management. Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Florence, Italy, 22–25 May 2006; pp. 250–261.
[20]
Tarr？o, P.; Bernardos, A.M.; Casar, J.R. Weighted least squares techniques for improved received signal strength based localization. Sensors 2011, 11, 8569–8592.
[21]
Yang, Z.; Liu, Y. Quality of trilateration: Confidence-based iterative localization. IEEE Trans. Parallel Distrib. Syst 2009, 21, 631–640.
[22]
Patwari, N.; Ash, J.; Kyperountas, S.; Hero, A.; Moses, R.; Correal, N. Locating the nodes. IEEE Signal Process. Mag 2005, 22, 54–69.
[23]
Andersen, J.; Rappaport, T.; Yoshida, S. Propagation measurements and models for wireless communications channels. IEEE Commun. Mag 1995, 33, 42–49.
[24]
Rappaport, T.S. Wireless Communications: Principles and Practice; Prentice Hall PTR: Upper Saddle River, NJ, USA, 1996; Volume 207.
[25]
Huang, Y.; Benesty, J.; Chen, J. Acoustic MIMO Signal Processing; Springer: Berlin, Germany, 2006.
[26]
Huang, Y.; Benesty, J.; Elko, G.; Mersereati, R. Real-time passive source localization: A practical linear-correction least-squares approach. IEEE Trans. Speech Audio Process 2002, 9, 943–956.
[27]
Chen, H.; Sezaki, K.; Deng, P.; So, H. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks. Proceedings of the 3rd IEEE Conference on Industrial Electronics and Applications (ICIEA ’08), Singapore, 3–5 June 2008; pp. 1557–1561.
[28]
Verdone, R.; Dardari, D.; Mazzini, G.; Conti, A. Wireless Sensor and Actuator Networks: Technologies, Analysis and Design; Elsevier: Amsterdam, The Netherlands, 2008; p. 211.
[29]
Dennis, J.; Schnabel, R. Numerical Methods for Unconstrained Optimization and Nonlinear Equations; Society for Industrial Mathematics: Englewood Cliffs, NJ, USA, 1996; p. 227.
[30]
Nocedal, J.; Wright, S. Numerical Optimization; Springer: Berlin, Germany, 2006; p. 8.
[31]
Cheng, B.; Vandenberghe, L.; Yao, K. Distributed algorithm for node localization in wireless ad-hoc networks. ACM Trans. Sens. Netw 2009, 6, 1–20.
[32]
Costa, J.A.; Patwari, N.; Hero, A.O., III. Distributed weighted-multidimensional scaling for node localization in sensor networks. ACM Trans. Sensor Netw 2006, 2, 39–64.
[33]
Delbos, F.; Gilbert, J.; Glowinski, R.; Sinoquet, D. Constrained optimization in seismic reflection tomography: A Gauss–Newton augmented Lagrangian approach. Geophys. J. Int 2006, 164, 670–684.
[34]
Roweis, S. Levenberg-Marquardt Optimization; University Of Toronto: Toronto, ON, Canada, 1996.
[35]
Ye, N. The Handbook of Data Mining; Lawrence Erlbaum: Mahwah, NJ, USA, 2003.
[36]
Li, X.; Hua, B.; Shang, Y.; Xiong, Y. A robust localization algorithm in wireless sensor networks. Front. Comput. Sci. China 2008, 2, 438–450.
[37]
Bourke, P. Intersection of Two Circles, 1997. Available online: http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/ (accessed on 9 January 2010).
[38]
Savvides, A.; Park, H.; Srivastava, M. 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, Atlanta, GA, USA, 28 September 2002; pp. 112–121.
[39]
Langendoen, K.; Reijers, N. Distributed localization in wireless sensor networks: A quantitative comparison. Comput. Netw 2003, 43, 499–518.
[40]
XST-AN019a, A.N. XBee and XBee-PRO OEM RF Module Antenna Considerations, 2005.Available online: http://www.digi.com (accessed on 9 January 2010).
[41]
Cormen, T. Introduction to Algorithms; The MIT Press: Cambridge, MA, USA, 2001; p. 23.
[42]
Sch？rghofer, N. The Third Branch of Physics: Essays in Scientific Computing; Nobert: Hamburg, Germany, 2005; pp. 53–71.
[43]
Wang, A.; Chandrakasan, A. Energy-efficient DSPs for wireless sensor networks. IEEE Signal Process. Mag 2002, 19, 68–78.
[44]
Sinha, A.; Chandrakasan, A. Energy Aware Software. Proceedings of the 13th International Conference on VLSI Design, Calcutta, India, 3–7 January 2000; pp. 50–55.
[45]
TI-Algorithms. Optimized Sort Algorithms for DSP, 2011. Available online: http://processors.wiki.ti.com/index.php/Optimized_Sort_Algorithms_For_DSP (accessed on 9 January 2012).
[46]
Dietz, H.; Dieter, B.; Fisher, R.; Chang, K. Floating-Point Computation with Just Enough Accuracy. Proceedings of the Computational Science (ICCS ’06), Reading, UK, 28–31 May 2006; pp. 226–233.
[47]
Mansi, R. Enhanced quicksort algorithm. Int. Arab J. Inform. Technol 2010, 7, 161–166.
