Rigid graph-based three-dimension localization algorithm for wireless sensor networks

doi:10.21629/JSEE.2018.05.05

Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (5): 927-936.doi: 10.21629/JSEE.2018.05.05

• Electronics Technology • Previous Articles Next Articles

Rigid graph-based three-dimension localization algorithm for wireless sensor networks

Xiaoyuan LUO^1,*(), Wenjing ZHONG¹(), Xiaolei LI¹(), Xinping GUAN²()

¹ School of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China
² Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China

Received:2017-09-04 Online:2018-10-26 Published:2018-11-14
Contact: Xiaoyuan LUO E-mail:jiayao89@sina.cn;654110619@qq.com;505665918@163.com;xpguan@sjtu.edu.cn
About author:LUO Xiaoyuan was born in 1976. He received his Ph.D. degree in control theory and control engineering from Yanshan University, China, Qinhuangdao, in 2005. He is currently a professor of the Institute of Electrical Engineering, Yanshan University. His current research interests include cooperative control of multi-agent systems and networked control systems. E-mail: jiayao89@sina.cn|ZHONG Wenjing was born in 1994. She received her bachelor degree in automation from Shanxi University, China, in 2016. She is currently a master student in control theory and control engineering at Yanshan University. Her research interest mainly focuses on rigid graph-based localization for wireless sensor networks. E-mail: 654110619@qq.com|LI Xiaolei was born in 1989. He received his B.S. degree in automation from Yanshan University, Qinhuangdao, China, in 2014, and he is currently pursuing his Ph.D. degree in control science and engineering at Yanshan University. His current research interests include cooperative control of multi-agent systems and nonlinear control system. E-mail: 505665918@163.com|GUAN Xinping was born in 1963. He received his M.S. degree in applied mathematics and Ph.D. degree in electrical engineering from Harbin Institute of Technology, Harbin, China, in 1991 and 1999, respectively. He is currently a professor at Shanghai Jiao Tong University, Shanghai, China. His current research interests include networked control systems, wireless sensor networks and applications, and cooperative control of multi-agent systems. E-mail: xpguan@sjtu.edu.cn
Supported by:
the National Natural Science Foundation of China(61375105);the National Natural Science Foundation of China(61403334);This work was supported by the National Natural Science Foundation of China (61375105; 61403334)

Abstract

Abstract:

This paper investigates the node localization problem for wireless sensor networks in three-dimension space. A distributed localization algorithm is presented based on the rigid graph. Before location, the communication radius is adaptively increasing to add the localizability. The localization process includes three steps: firstly, divide the whole globally rigid graph into several small rigid blocks; secondly, set up the local coordinate systems and transform them to global coordinate system; finally, use the quadrilateration iteration technology to locate the nodes in the wireless sensor network. This algorithm has the advantages of low energy consumption, low computational complexity as well as high expandability and high localizability. Moreover, it can achieve the unique and accurate localization. Finally, some simulations are provided to demonstrate the effectiveness of the proposed algorithm.

Key words: wireless sensor network, localization, rigid graph, quadrilateration

Xiaoyuan LUO, Wenjing ZHONG, Xiaolei LI, Xinping GUAN. Rigid graph-based three-dimension localization algorithm for wireless sensor networks[J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 927-936.

Figures/Tables 15

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Table 1

Fig 7

Fig 8

Table 2

Fig 9

Table 3

Fig 10

Table 4

Fig 11

References 33

1	FADEL E, GUNGOR V C, NASSEF L. A survey on wireless sensor networks for smart grid. Computer Communications, 2015, 71 (11): 22- 33.
2	HERUTOMO A, ABDUROHMAN M, SUWASTIKA N A. Forest fire detection system reliability test using wireless sensor network and Open MTC communication platform. Proc. of the 3rd International Conference on Information and Communication Technology, 2015: 87-91.
3	AHMED M, SALLEH M. Localization schemes in underwater sensor network (UWSN): a survey. Indonesian Journal of Electrical Engineering and Computer Science, 2016, 1 (1): 119- 125.
4	XU G, SHEN W, WANG X. Applications of wireless sensor networks in marine environment monitoring: a survey. Sensors, 2014, 14 (9): 16932- 16954. doi: 10.3390/s140916932
5	MALAVER A, MOTTA N, CORKE P. Development and integration of a solar powered unmanned aerial vehicle and a wireless sensor network to monitor greenhouse gases. Sensors, 2015, 15 (2): 4072- 4096. doi: 10.3390/s150204072
6	XIAO F, LIU W, LI Z, et al. Noise-tolerant wireless sensor networks localization via multi-norms regularized matrix completion. IEEE Trans. on Vehicular Technology, 2017, 67 (3): 2409- 2419.
7	HAN G, JIANG J, ZHANG C. A survey on mobile anchor node assisted localization in wireless sensor networks. IEEE Communications Surveys & Tutorials, 2016, 18 (3): 2220- 2243.
8	XIAO F, SHA C, CHEN L. Noise-tolerant localization from incomplete range measurements for wireless sensor networks. Proc. of the IEEE Conference on Computer Communications, 2015: 2794-2802.
9	MAO G, FIDAN B, ANDERSON B D O. Wireless sensor network localization techniques. Computer Networks, 2007, 51 (10): 2529- 2553. doi: 10.1016/j.comnet.2006.11.018
10	SHRIVASTAVA A, BHARTI P. Localization techniques for wireless sensor networks. International Journal of Computer Applications, 2015, 116 (12): 13- 18. doi: 10.5120/20387-2650
11	YIN J, WAN Q, YANG S. A simple and accurate TDOA-AOA localization method using two stations. IEEE Signal Processing Letters, 2016, 23 (1): 144- 148. doi: 10.1109/LSP.2015.2505138
12	TOMIC S, BEKO M, RUI D. Distributed RSS-AoA based localization with unknown transmit powers. IEEE Wireless Communications Letters, 2016, 5 (4): 392- 395. doi: 10.1109/LWC.2016.2567394
13	TOMIC S, BEKO M, RUI D. Distributed algorithm for target localization in wireless sensor networks using RSS and AoA measurements. Pervasive & Mobile Computing, 2017, 37 (6): 63- 77.
14	HALDER S, GHOSAL A. A survey on mobile anchor assisted localization techniques in wireless sensor networks. Wireless Networks, 2015, 60 (7): 1- 20.
15	HUANG B, XIE L, YANG Z. TDOA-based source localization with distance-dependent noises. IEEE Trans. on Wireless Communications, 2015, 14 (1): 468- 480. doi: 10.1109/TWC.2014.2351798
16	JONDHALE S R, DESHPANDE R S, WALKE S M. Issues and challenges in RSSI based target localization and tracking in wireless sensor networks. Proc. of the International Conference on Automatic Control and Dynamic Optimization Techniques, 2016: 594-598.
17	MOORE D, LEONARD J, RUS D. Robust distributed network localization with noisy range measurements. Proc. of the International Conference on Embedded Networked Sensor Systems, 2004: 50-61.
18	AHMADI R, EKBATANIFARD G, JAHANGIRY A. Improving localization in wireless sensor network using fixed and mobile guide nodes. Journal of Sensors, 2016, 6385380.
19	XU H, SUN H, CHENG Y. Wireless sensor networks localization based on graph embedding with polynomial mapping. Computer Networks, 2016, 106, 151- 160. doi: 10.1016/j.comnet.2016.06.032
20	KRISTALINA P, PRATIARSO A, BADRIYAH T. A wireless sensor networks localization using geometric triangulation scheme for object tracking in urban search and rescue application. Proc. of the 2nd International Conference on Science in Information Technology, 2016: 254-259.
21	TOMIC S, MARIKJ M, BEKO M. Hybrid RSS-AoA technique for 3-D node localization in wireless sensor networks. Proc. of the International Wireless Communications and Mobile Computing Conference, 2015: 1277-1282.
22	WEI N, GUO Q, SHU M L. Three-dimensional localization algorithm of wireless sensor networks base on particle swarm optimization. Journal of China Universities of Posts & Telecommunications, 2012, 19 (11): 7- 12.
23	SHWE H Y, CHONG P H J. Cubic-based 3-D localization for wireless sensor networks. Proc. of the 9th International Conference on Information, Communications and Signal Processing, 2013: 169-179.
24	SECO F, JIMNEZ A R, ZHENG X. RFID-based centralized cooperative localization in indoor environments. Proc. of the International Conference on Indoor Positioning and Indoor Navigation, 2016: 1-7.
25	JI S. A time difference of arrival-based localization algorithm for wireless sensor networks. International Journal of Online Engineering, 2016, 12 (11): 80- 83. doi: 10.3991/ijoe.v12i11.6228
26	AHRIZ I, DZIRI A, RUYET D L. Compressed sensing-based centralized multiple targets localization. Proc. of the 11th International Symposium on Wireless Communications Systems, 2014: 563-567.
27	ZHU Y, GORTLER S J, THURSTON D. Sensor network localization using sensor perturbation. ACM Trans. on Sensor Networks, 2011, 7 (4): 1- 23.
28	SHAMANTHA R B, VARMA S. An algorithmic approach to wireless sensor networks localization using rigid graphs. Journal of Sensors, 2016, 3986321.
29	JACKSON B, JORDAN T. Connected rigidity matroids and unique realizations of graphs. Journal of Combinatorial Theory, 2003, 94 (1): 1- 29.
30	TANIGAWA S I. Generic global rigidity of body-hinge frameworks. Journal of Combinatorial Theory, Series B, 2016, 117, 59- 76. doi: 10.1016/j.jctb.2015.11.003
31	MESBAHI M, EGERSTEDT M. Graph theoretic methods in multiagent networks. Princeton: Princeton University Press, 2010.
32	LIU Y, YANG Z, WANG X, et al. Location, localization, and localizability. Journal of Computer Science and Technology, 2010, 25 (2): 274- 297. doi: 10.1007/s11390-010-9324-2
33	YANG Z, WU C, CHEN T. Detecting outlier measurements based on graph rigidity for wireless sensor network localization. IEEE Trans. on Vehicular Technology, 2013, 62 (1): 374- 383. doi: 10.1109/TVT.2012.2220790

Simulation parameter	Indication	Value
Deployment area/m³	V	200×200×200
Number of nodes/n	N	100 – 140
Communication radius/m	R	50 – 80

Node density/ (n/m³)	P_Ni (100)	P_Ni (120)	P_Ni (140)
0.1	0.33	0.23	0.28
0.2	0.56	0.65	0.79
0.3	0.83	0.90	0.89
0.4	0.92	0.94	0.91
0.5	0.97	0.96	0.99
0.6	0.98	0.98	0.99
0.7	0.98	0.99	0.99
0.8	0.97	1.00	1.00
0.9	1.00	1.00	1.00
1.0	1.00	1.00	1.00

N/n	R/m
N/n	50	55	60	65	70	75
100	4.26	5.82	7.12	9.1	10.94	12.84
	4.86	6.38	7.86	9.78	11.82	14.28
	4.96	6.08	7.46	9.36	11.06	13.54
	5.06	6.62	8.5	10.44	12.46	14.48
	5.12	6.48	8.18	10.1	11.68	14.1
120	6.35	8.02	9.90	12.17	14.93	17.68
	6.27	7.88	9.68	12.40	15.08	18.22
	5.72	7.58	9.92	11.93	14.38	16.95
	6.47	8.02	10.13	12.33	15.25	17.88
	5.12	6.52	8.42	10.82	13.25	15.85
140	6.56	8.46	10.84	12.96	15.83	18.77
	7.39	9.26	11.57	14.63	17.36	20.83
	6.66	8.60	10.70	13.23	15.94	18.77
	7.09	8.97	11.11	13.59	16.50	19.50
	6.09	7.94	10.23	12.70	15.06	17.77

R/m	N=100		N=120		N=140
R/m	P_L/%	N_ave/n	P_L/%	N_ave/n	P_L/%	N_ave/n
40	29.00	2.54	41.67	3.03	50.00	3.84
45	50.00	3.56	65.83	4.35	75.00	5.39
50	63.00	4.72	80.00	5.73	85.71	6.94
55	77.00	6.00	87.50	7.13	92.14	9.09
60	87.00	7.84	92.50	9.12	97.14	11.34
65	92.00	9.74	95.83	11.67	98.57	13.79
70	94.00	11.84	97.50	14.30	100.0	16.73
75	96.00	14.56	98.33	17.08	100.0	20.01
80	96.00	16.96	99.17	20.28	100.0	23.24
85	99.00	19.20	100.0	23.63	100.0	26.90

[1]	Mingyi YOU, Annan LU. A robust TDOA based solution for source location using mixed Huber loss [J]. Journal of Systems Engineering and Electronics, 2021, 32(6): 1375-1380.
[2]	Jingjing PAN, Parth Raj SINGH, Shaoyang MEN. A search-free near-field source localization method with exact signal model [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 756-763.
[3]	Yongsheng ZHAO, Dexiu HU, Yongjun ZHAO, Zhixin LIU. Moving target localization for multistatic passive radar using delay, Doppler and Doppler rate measurements [J]. Journal of Systems Engineering and Electronics, 2020, 31(5): 939-949.
[4]	Qianlin CHENG, Xiaofei ZHANG, Renzheng CAO. Fast parallel factor decomposition technique for coherently distributed source localization [J]. Journal of Systems Engineering and Electronics, 2018, 29(4): 667-675.
[5]	Yuxing MAO, Huiyuan ZHAO, Dongmei YAN. Weak node protection to maximize the lifetime of wireless sensor networks [J]. Journal of Systems Engineering and Electronics, 2018, 29(4): 693-706.
[6]	Umer JAVED, Di HE, Peilin LIU, Yueming YANG. Frequency hopping in IEEE 802.15.4 to mitigate IEEE 802.11 interference and fading [J]. Journal of Systems Engineering and Electronics, 2018, 29(3): 445-455.
[7]	Hailin Feng and Jieyu Dong. Reliability analysis for WSN based on a modular k-out-of-n system [J]. Systems Engineering and Electronics, 2017, 28(2): 407-412.
[8]	Leigang Wang and Tao Zhang. Distributed cooperative localization for sparse communication network with multi-locating messages [J]. Systems Engineering and Electronics, 2016, 27(4): 746-.
[9]	Xuewen Liu, Song Xiao, and Lei Quan. Optical SDMA for applying compressive sensing in WSN [J]. Systems Engineering and Electronics, 2016, 27(4): 780-.
[10]	Wei Xia, Wei Liu, and Lingfeng Zhu. Distributed adaptive direct position determination based on diffusion framework [J]. Systems Engineering and Electronics, 2016, 27(1): 28-.
[11]	Xiaolong Xu, Yu Tang, Xinheng Wang, and Yun Zhang. Variance-based fingerprint distance adjustment algorithm for indoor localization [J]. Systems Engineering and Electronics, 2015, 26(6): 1191-1201.
[12]	Linzhi Huang and Jun Ai. Automatic software fault localization based on artificial bee colony [J]. Systems Engineering and Electronics, 2015, 26(6): 1325-1332.
[13]	Tiebing Wang, Miao Li, Xueying Wang, Wei An, and Yiyu Zhou. C60-based clustering scheme for sensor management in STSS [J]. Journal of Systems Engineering and Electronics, 2015, 26(5): 993-999.
[14]	Peng Wang, Qibin Zhang, and Zonghai Chen. Feature extension and matching for mobile robot global localization [J]. Journal of Systems Engineering and Electronics, 2015, 26(4): 840-.
[15]	Yanshen Du, Ping Wei, and Huaguo Zhang. Semidefinite programming approach for TDOA/GROA based source localization [J]. Journal of Systems Engineering and Electronics, 2015, 26(4): 680-.

Rigid graph-based three-dimension localization algorithm for wireless sensor networks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 33

Related Articles 15

Recommended Articles

Metrics

Comments