A 2-hop spanning tree based scalable clustered localization algorithm for wireless sensor networks

doi:10.7523/j.issn.2095-6134.2009.6.012

Abstract

Abstract:

The proposed localization algorithm first generates clusters and a spanning tree consisting of cluster heads, and then the cluster head computes local coordinates of all member nodes in the cluster. Finally, it generates a global coordinate of all nodes through the above spanning tree. Analysis and simulation show that the proposed algorithm has higher cover rate and precision of localization, lower network traffic, less time consumption, and higher scalability than the existing SDGPSN.

Key words: wireless sensor networks, relative localization, clustering, 2 hop spanning tree

CLC Number:

TP393

MIAO Fu-You, XIONG Yan, WANG Xin-Xia. A 2-hop spanning tree based scalable clustered localization algorithm for wireless sensor networks[J]. , 2009, 26(6): 812-819.

References

[1] Iyengar R, Sikdar B. Scalable and distributed GPS free positioning for sensor networks //IEEE International Conference on Communications(ICC03). Anchorage, AK, USA,2003: 338-342.

[2] Li X, Shi H, Shang Y. A map-growing localization algorithm for ad-hoc wireless sensor networks //Proceedings of the International Conference on Parallel and Distributed Systems-ICPADS. Newport Beach, CA, United States, 2004: 395-402.

[3] Priynatha N B, Balakrishnan H, Demaine E, et al. Anchor-free distributed localization in sensor networks //Proceedings of Conference on Embeded Networked Sensor Systems.Los Angeles, CA, United States,2003: 340-341.

[4] Capkun S, Hamdi M, Hubaux J P. GPS-free positioning in mobile ad-hoc networks //Proceedings of Hawaii International Conference on System Sciences. Maui, HI, United States,2001: 255.

[5] David M, John L, Daniela R, et al. Robust distributed network localization with noisy range measurements //Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. ACM: Baltimore, MD, USA, 2004: 50-61.

[6] Shang Y, Ruml W. Improved MDS-based localization //Proceedings of the 23rd Conference of the IEEE Communicatons Society (Infocom 2004). Hong Kong, 2004: 2640-2651.

[7] Kwon O H, Song H J. Localization through map stitching in wireless sensor networks
[J]. Transactions on Parallel and Distributed Systems, 2008, 19(1): 93-105.

[8] Horn B K P, Hilden H M, Negahdaripour S. Closed-form solution of absolute orientation using orthonormal matrices
[J]. Journal of the Optical Society of America A (Optics and Image Science), 1988, 5(7): 1127-1135.

[9] Doucet A, N de Freitas, Gordon N. Sequential Monte Carlo methods in practice
[M]. Germany:Springer,2001.

[10] Kwon O H, Song H J. Stitching orders in patch-and-stitch localization algorithms for wireless sensor networks //Proceedings of 5th Workshop on Positioning, Navigation and Communication 2008. Hannover, Germany,2008: 233-241.

[1]	WANG Hong, XU Youyu, TAN Chong, LIU Hong, ZHENG Min. Information fusion algorithm based on improved particle swarm BP neural network in WSN [J]. , 2020, 37(5): 673-680.
[2]	YANG Suixin, GENG Xiurui, YANG Weitun, ZHAO Yongchao, LU Xiaojun. A method of hyperspectral remote sensing image classification based on spectral clustering [J]. , 2019, 36(2): 267-274.
[3]	LI Weiqian, QIU Ling. Joint clustering and resource allocation strategy for multicast device-to-device communication underlaying cellular networks [J]. , 2019, 36(1): 137-143.
[4]	XING Tao, HUANG Youhong, HU Qingrong, LI Jun, WANG Guanyong. SAR image segmentation based on dynamical K-means clustering algorithm [J]. , 2016, 33(5): 674-678.
[5]	GONG Xueshuang, YU Lijun, NIE Yueping, ZHU Jianfeng, PAN Yuqing . Spatial-pattern analysis of settlements in western region of Liaoning during pre-Qin period [J]. , 2016, 33(3): 373-379.
[6]	WU Wendi, CHENG Xijun, LIU Feng. CVaR portfolio model based on K-means clustering with the constraint of generalized entropy [J]. , 2016, 33(1): 31-36.
[7]	JIANG Zhi-Peng, GAO Sui-Xiang. Localization algorithm without distance information for wireless sensor networks [J]. , 2011, 28(3): 382-388.
[8]	SUN Bo, GAO Sui-Xiang, LU Qing. Study on optimization of communication radii of nodes in hierarchically clustered wireless sensor networks [J]. , 2010, 27(6): 818-823.
[9]	WANG Qiu-Ming, GAO Hui-Ying, LIU Ke-Cheng. Software requirement analysis based on fuzzy clustering and grey correlation degree [J]. , 2010, 27(6): 859-863.
[10]	QU Wen-Hu, XIE Bao-Ling, SHI Fan. Efficient sink node deployment scheme in wireless sensor networks [J]. , 2010, 27(5): 684-689.
[11]	CAO Zheng, ZHU Ming. A fast and effective similar video search method [J]. , 2010, 27(3): 376-380.
[12]	XIA Lu-Ning, JING Ji-Wu. SA-DBSCAN:A self-adaptive density-based clustering algorithm [J]. , 2009, 26(4): 530-538.
[13]	WANG Jing, XIA Lu-Ning, JING Ji-Wu. Maximum density clustering algorithm [J]. , 2009, 26(4): 539-548.
[14]	SONG Jin-Liang, LUO Tie-Jian, CHEN Su, LIU Wei. A clustering based method to solve duplicate tasks problem [J]. , 2009, 26(1): 107-113.
[15]	JIANG Canming, XU Haixia, LI Bao. Distributed User Authentication in Wireless Sensor Networks [J]. Journal of University of Chinese Academy of Sciences, 2008, 25(1): 80-85.