Distributed localization algorithm for wireless sensor network based on multidimensional scaling and the shortest path distance correction

Abstract

Sensor localization is crucial for the configuration and applications of wireless sensor network (WSN). A novel distributed localization algorithm, MDS-DC was proposed for wireless sensor network based on multidimensional scaling (MDS) and the shortest path distance correction. In MDS-DC, several local positioning regions with reasonable distribution were firstly constructed by an adaptive search algorithm, which ensures the mergence between the local relative maps of the adjacent local position regions and can reduce the number of common nodes in the network. Then, based on the relationships between the estimated distances and actual distances of anchors, the distance estimation vectors of sensors around anchors were corrected in each local positioning region. During the computations of the local relative coordinates, an iterative process, which is the combination of classical MDS algorithm and SMACOF algorithm, was applied. Finally, the global relative positions or absolute positions of sensors were obtained through merging the relative maps of all local positioning regions. Simulation results show that MDS-DC has better performances in positioning precision, energy efficiency and robustness to range error, which can meet the requirements of applications for sensor localization in WSN.

Keywords

wireless sensor network (WSN) / multidimensional scaling / local positioning region / relative coordinates

References

[1] Akyildiz I. F., Su W., Sankarasubramaniam Y., et al. A survey on sensor network[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[2] Bulusu N., Heidemann J., Estrin D. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications, 2000, 7(5): 28-34.

[3] Niculescu D, Nath B. Ad hoc positioning system[C]. In: Proceedings of 2001 IEEE Global Telecommunications Conference. Texas, USA, 2001. 2926–2931.

[4] He Tian, Huang Chengdu, Blum B M et al. Range-free localization schemes in large scale sensor network[C]. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. San Diego, USA, 2003. 110–120.

[5] Cox T. F., Cox M. A. Multidimensional Scaling[M]. 2001, Boca Raton, USA: Chapman Hall.

[6] Yi Shang, Ruml W, Zhang Ying. Localization from mere connectivity in sensor networks[C]. In: Proc of the 4th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York, USA, 2003. 201–212.

[7] Biaz S, Ji Yiming. Precise distributed localization algorithm for wireless networks[C]. In: Proceedings of the 6th IEEE International Symposium on WoWMoM. Taormina, Italy, 2005. 388–394.

[8] Cheung K W, So H C. A multidimensional scaling framework for mobile location using time-of-arrival measurements[J]. IEEE Transactions on Signal Processing, 2005(2): 460–470.

[9] Ji Xiang, Zha Hongyuan. Sensor positioning in wireless ad-hoc sensor network using multidimensional scaling[C]. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong, China, 2004. 2652–2661.

[10] Yi Shang, Ruml W. Improved MDS-based localization[ C]. In: Proceedings of the 23rd Conference of the IEEE Communicatons Society. Hong Kong, China, 2004. 2640–2651.

[11] Liu C. E. Research on Self Localization and Target Tracking in Wireless Sensor Networks[D]. 2006, Beijing: Institute of Acoustics, Chinese Academy of Sciences.

[12] Zhan F. B. Three fastest shortest path algorithms on real road networks[J]. Journal of Geographic Information and Decision Analysis, 1997, 1(1): 69-82.

[13] De Leeuw J. Recent Developments in Statistics[M]. 1977, the Netherlands: North-Holland 133-145.