Optimization schemes for wireless sensor network localization

Niewiadomska-Szynkiewicz, E. ; Marks, M.

International Journal of Applied Mathematics and Computer Science, Tome 19 (2009) no. 2, pp. 291-302

Résumé

Many applications of wireless sensor networks (WSN) require information about the geographical location of each sensor node. Self-organization and localization capabilities are one of the most important requirements in sensor networks. This paper provides an overview of centralized distance-based algorithms for estimating the positions of nodes in a sensor network. We discuss and compare three approaches: semidefinite programming, simulated annealing and two-phase stochastic optimization-a hybrid scheme that we have proposed. We analyze the properties of all listed methods and report the results of numerical tests. Particular attention is paid to our technique-the two-phase method-that uses a combination of trilateration, and stochastic optimization for performing sensor localization. We describe its performance in the case of centralized and distributed implementations.

Détail

Keywords: wireless sensor networks, localization, stochastic optimization, simulated annealing
Mots-clés : sieć bezprzewodowa, sieć sensorowa, lokalizacja, optymalizacja stochastyczna, wyżarzanie symulowane

Bibliographie

[1] Anderson, B. D. O., Mao, G. and Fidan, B. (2007). Wireless sensor network localization techniques, Computer Networks 51(10): 2529-2553.

[2] Biswas, P. and Ye, Y. (2004). Semidefinite programming for ad hoc wireless sensor network localization, IPSN '04: Proceedings of the 3-rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA, ACM Press, New York, NY, pp. 46-54.

[3] Borchers, B. (1999). CSDP, a C library for semidefinite programming, Optimization Methods Software 11(1-4): 613-623.

[4] Boyd, S., Ghaoui, L. E., Feron, E. and Balakrishnan, V. (1994). Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, PA.

[5] de Brito, L. M. P. L. and Peralta, L. M. R. (2007). Collaborative localization in wireless sensor networks, SENSORCOMM 2007: Proceedings of the International Conference on Sensor Technologies and Applications, Valencia, Spain, IEEE Computer Society, pp. 94-100.

[6] Dekkers, A. and Aarts, E. (1991). Global optimization and simulated annealing, Mathematical Programming 50(8): 367-393.

[7] Doherty, L., Pister, K. and Ghaoui, L. E. (2001). Convex postion estimation in wireless sensor networks, INFOCOM 2001: Proceedings of the 20-th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, USA, pp. 1655-1663.

[8] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Studies in Applied Mathematics, Addison-Wesley, Boston, MA.

[9] Hightower, J. and Borriello, G. (2001). Localization systems for ubiquitous computing, Computer 34(8): 57-66.

[10] Hu, L. and Evans, D. (2004). Localization for mobile sensor networks, MobiCom 2004: Proceedings of the 10-th Annual International Conference on Mobile Computing and Networking, Philadelphia, PA, USA, IEEE Computer Society, pp. 45-57.

[11] Ji, X. and Zha, H. (2004). Sensor positioning in wireless ad hoc sensor networks with multidimensional scaling, INFOCOM 2004: Proceedings of the 23-rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, pp. 2652-2661.

[12] Kannan, A. A., Mao, G. and Vucetic, B. (2005). Simulated annealing based localization in wireless sensor network, LCN '05: Proceedings of the IEEE Conference on Local Computer Networks. 30-th Anniversary, Sydney, Australia, IEEE Computer Society, pp. 513-514.

[13] Kannan, A. A., Mao, G. and Vucetic, B. (2006). Simulated annealing based wireless sensor network localization with flip ambiguity mitigation, Proceedings of the 63-rd IEEE Vehicular Technology Conference, Melbourne, Australia, pp. 1022-1026.

[14] Marks, M. and Niewiadomska-Szynkiewicz, E. (2007). Two-phase stochastic optimization to sensor network localization, SENSORCOMM 2007: Proceedings of the International Conference on Sensor Technologies and Applications, Valencia, Spain, IEEE Computer Society, pp. 134-139.

[15] Niculescu, D. and Nath, B. (2001). Ad hoc positioning system (APS), GLOBECOM: Proceeding of the Global Telecommunications Conference, San Antonio, CA, USA, pp. 2926-2931.

[16] Shang, Y., Ruml,W., Zhang, Y. and Fromherz, M. (2004). Localization from connectivity in sensor networks, IEEE Transactions on Parallel and Distributed Systems 15(11): 961-974.

[17] Sturm, J. F. (1999). Using SeDuMi 1.02, aMATLAB toolbox for optimization over symmetric cones, Optimization Methods Software 11(1-4): 625-653.