Greedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor network

doi:10.11772/j.issn.1001-9081.2022010141

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (3): 869-875.DOI: 10.11772/j.issn.1001-9081.2022010141

• Network and communications • Previous Articles

Greedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor network

Qing YE¹^,², Xin SHI³(), Mengwei SUN³, Jian ZHU³

^1.National Engineering Research Center for Mountainous Highways，Chongqing 400067，China
^2.School of Big Data and Software Engineering，Chongqing University，Chongqing 401331，China
^3.School of Information Engineering，Chang’an University，Xi’an Shaanxi 710064，China

Received:2022-02-11 Revised:2022-05-30 Accepted:2022-06-20 Online:2022-07-15 Published:2023-03-10
Contact: Xin SHI
About author:YE Qing， born in 1994， Ph. D. candidate， engineer. His research interests include intelligent transportation， vehicle infrastructure cooperation， autonomous driving.
SUN Mengwei， born in 1997， M. S. candidate. Her research interests include collaborative perception based on internet of vehicles.
ZHU Jian， born in 1997， M. S. candidate. His research interests include time synchronization based on wireless sensor network.
Supported by:
Project of Open Fund of National Engineering Research Center for Mountainous Highways(GSGZJ-2020-06)

基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法

叶青¹^,², 史昕³(), 孙梦薇³, 朱健³

^1.国家山区公路工程技术研究中心, 重庆 400067
^2.重庆大学大数据与软件学院, 重庆 401331
^3.长安大学信息工程学院, 西安 710064

通讯作者: 史昕
作者简介:叶青（1994—），男，重庆人，工程师，博士研究生，主要研究方向：智慧交通、车路协同、自动驾驶
史昕（1987—），男，河南南阳人，副教授，博士，CCF会员，主要研究方向：无线传感网络时间同步、车联网协同感知
孙梦薇（1997—），女，陕西渭南人，硕士研究生，主要研究方向：车联网协同感知
朱健（1997—），男，重庆人，硕士研究生，主要研究方向：无线传感网络时间同步。
基金资助:
国家山区公路工程技术研究中心开放基金课题(GSGZJ-2020-06)

Abstract

Abstract:

Aiming at the energy efficiency and scene adaptability problems of synchronization topology， a Greedy Synchronization Topology algorithm based on Formal Concept Analysis for traffic surveillance based sensor network （GST-FCA） was proposed. Firstly， scene adaptability requirements and energy efficiency model of the synchronization topology in traffic surveillance based sensor network were analyzed. Secondly， correlation analysis was performed on the adjacent features of sensor nodes in the same layer and adjacent layers by using Formal Concept Analysis （FCA）. Afterward， Broadcast Tuples （BT） were built and synchronization sets were divided according to the greedy strategy with the maximum number of neighbors. Thirdly， a backtracking broadcast was used to improve the broadcast strategy of layer detection in Timing-synchronization Protocol of Sensor Network （TPSN） algorithm. Meanwhile， an upward hosting mechanism was designed to not only extend the information sharing range of synchronous nodes but also further alleviate the locally optimal solution problem caused by the greedy strategy. Finally， GST-FCA was verified and tested in terms of energy efficiency and scene adaptability. Simulation results show that compared with algorithms such as TPSN， Linear Estimation of Clock Frequency Offset （LECFO）， GST-FCA decreases the synchronization packet overhead by 11.54%， 24.59% and 39.16% at lowest in the three test scenarios of deployment location， deployment scale and road deployment. Therefore， GST-FCA can alleviate the locally optimal solution problem and reduce the synchronization packet overhead， and it is excellent in energy efficiency when the synchronization topology meets the scene adaptability requirements of the above three scenarios.

Key words: traffic surveillance based sensor network, synchronization topology, Formal Concept Analysis (FCA), broadcast tuple, greedy strategy, synchronization packet overhead

摘要：

针对交通监测传感网络时间同步拓扑的能量有效性和场景适应性问题，提出一种基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法GST-FCA。首先分析交通监测传感网络同步拓扑的场景适应性需求和能量有效性问题模型；其次，利用形式概念分析（FCA）对同层和相邻层传感节点的邻接特征进行关联性解析，根据最多邻居贪婪策略构建广播元组（BT）并划分同步集合；然后利用回溯广播改进传感网络时间同步协议（TPSN）算法的层探测广播策略，同时设计向上托管机制，增大已同步节点信息的共享范围，进一步缓解贪婪策略产生的局部最优解问题；最后对GST-FCA的能量有效性和场景适应性进行测试。仿真结果表明，相较于TPSN、LECFO等算法，GST-FCA在部署位置、部署规模、道路部署三个测试场景中的同步报文开销分别至少降低11.54%、24.59%和39.16%。由此可见，GST-FCA能缓解局部最优解问题并降低同步报文开销，而且能在同步拓扑满足上述三个场景适应性需求下达到良好的能量有效性。

关键词: 交通监测传感网络, 同步拓扑, 形式概念分析, 广播元组, 贪婪策略, 同步报文开销

CLC Number:

TP391.9

Qing YE, Xin SHI, Mengwei SUN, Jian ZHU. Greedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor network[J]. Journal of Computer Applications, 2023, 43(3): 869-875.

叶青, 史昕, 孙梦薇, 朱健. 基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 869-875.

Figures/Tables 7

References 25

1	赵祥模，惠飞，史昕，等. 泛在交通信息服务系统的概念、架构与关键技术［J］. 交通运输工程学报， 2014， 14（4）： 105-115. 10.3969/j.issn.1671-1637.2014.04.013
	ZHAO X M， HUI F， SHI X， et al. Concept， architecture， and challenging technology of ubiquitous traffic information service system［J］. Journal of Traffic and Transportation Engineering， 2014， 14（4）： 105-115. 10.3969/j.issn.1671-1637.2014.04.013
2	TACCONI D， MIORANDI D， CARRERAS I， et al. Using wireless sensor networks to support intelligent transportation systems［J］. Ad Hoc Networks， 2010， 8（5）： 462-473. 10.1016/j.adhoc.2009.12.007
3	KATIYAR V， KUMAR P， CHAND N. An intelligent transportation systems architecture using wireless sensor networks［J］. International Journal of Computer Applications， 2011， 14（2）： 22-26. 10.5120/1816-2369
4	BOTTERO M， DALLA CHIARA B， DEFLORIO F P. Wireless sensor networks for traffic monitoring in a logistic centre［J］. Transportation Research Part C： Emerging Technologies， 2013， 26： 99-124. 10.1016/j.trc.2012.06.008
5	SWAIN A R， HANSDAH R C. A model for the classification and survey of clock synchronization protocols in WSNs［J］. Ad Hoc Networks， 2015， 27： 219-241. 10.1016/j.adhoc.2014.11.021
6	UPADHYAY D， DUBEY A K， THILAGAM P S. A statistical tool for time synchronization problem in WSN［J］. Recent Patents on Engineering， 2019， 13（2）： 154-158. 10.2174/1872212112666180712151155
7	ZHANG X X， CHEN H L， LIN K， et al. RMTS： a robust clock synchronization scheme for wireless sensor networks［J］. Journal of Network and Computer Applications， 2019， 135： 1-10. 10.1016/j.jnca.2019.02.028
8	WU Y C， CHAUDHARI Q， SERPEDIN E. Clock synchronization of wireless sensor networks［J］. IEEE Signal Processing Magazine， 2011， 28（1）： 124-138. 10.1109/msp.2010.938757
9	KHAN R A， SHAH S A， ALEEM M A， et al. Wireless sensor networks： a solution for smart transportation［J］. Journal of Emerging Trends in Computing and Information Sciences， 2012， 3（4）： 566-571.
10	BALID W. Fully autonomous self-powered intelligent wireless sensor for real-time traffic surveillance in smart cities［D］. Oklahoma： The University of Oklahoma， 2016： 217-220. 10.1109/icsens.2017.8234157
11	BALID W， TAFISH H， REFAI H H. Intelligent vehicle counting and classification sensor for real-time traffic surveillance［J］. IEEE Transactions on Intelligent Transportation Systems， 2018， 19（6）： 1784-1794. 10.1109/tits.2017.2741507
12	GANERIWAL S， KUMAR R， SRIVASTAVA M. Timing-sync protocol for sensor networks［C］// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. New York： ACM， 2003： 138-149. 10.1145/958491.958508
13	NOH K L， SERPEDIN E， QARAQE K. A new approach for time synchronization in wireless sensor networks： pairwise broadcast synchronization［J］. IEEE Transactions on Wireless Communications， 2008， 7（9）： 3318-3322. 10.1109/twc.2008.070343
14	NOH K L， WU Y C， QARAQE K， et al. Extension of pairwise broadcast clock synchronization for multi-cluster sensor networks［J］. EURASIP Journal on Advances in Signal Processing， 2007， 2008： No.286168. 10.1155/2008/286168
15	CHENG K Y， LUI K S， WU Y C， et al. A distributed multi-hop time synchronization protocol for wireless sensor networks using pairwise broadcast synchronization［J］. IEEE Transactions on Wireless Communications， 2009， 8（4）： 1764-1772. 10.1109/twc.2009.080112
16	DJENOURI D， MERABTINE N， MEKAHLIA F Z， et al. Fast distributed multi-hop relative time synchronization protocol and estimators for wireless sensor networks［J］. Ad Hoc Networks， 2013， 11（8）： 2329-2344. 10.1016/j.adhoc.2013.06.001
17	ELSON J， GIROD L， ESTRIN D. Fine-grained network time synchronization using reference broadcast［J］. ACM SIGOPS Operating Systems Review， 2002， 36（SI）： 147-163. 10.1145/844128.844143
18	YILDIRIM K S， KANTARCI A. External gradient time synchronization in wireless sensor networks［J］. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（3）： 633-641. 10.1109/tpds.2013.58
19	WANG H， ZENG H Y， WANG P. Linear estimation of clock frequency offset for time synchronization based on overhearing in wireless sensor networks［J］. IEEE Communications Letters， 2016， 20（2）： 288-291. 10.1109/lcomm.2015.2510645
20	GU X B， LI J Z， ZHOU G X， et al. Improved clock parameters tracking and ranging method based on two-way timing stamps exchange mechanism［J］. IEEE Signal Processing Letters， 2021， 28： 598-602. 10.1109/lsp.2021.3062483
21	PHAN L A， KIM T. Fast consensus-based time synchronization protocol using virtual topology for wireless sensor networks［J］. IEEE Internet of Things Journal， 2021， 8（9）： 7485-7496. 10.1109/jiot.2020.3038426
22	TIAN Y P， CHUN S H， CHEN G， et al. Delay compensation-based time synchronization under random delays： algorithm and experiment［J］. IEEE Transactions on Control Systems Technology， 2021， 29（1）： 80-95. 10.1109/tcst.2019.2956031
23	ŠKOPLJANAC-MAČINA F， BLAŠKOVIĆ B. Formal concept analysis — overview and applications［J］. Procedia Engineering， 2014， 69： 1258-1267. 10.1016/j.proeng.2014.03.117
24	PRISS U. Formal concept analysis in information science［J］. Annual Review of Information Science and Technology， 2006， 40（1）： 521-543. 10.1002/aris.1440400120
25	CALINESCU G. Computing 2-hop neighborhoods in ad hoc wireless networks［C］// Proceedings of the 2003 International Conference on Ad-Hoc， Mobile， and Wireless Networks， LNCS 2865. Berlin： Springer， 2003： 175-186.

[1]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[2]	HAN Yulao, FANG Dingyi. Multi-objective path planning algorithm for mobile charging devices jointing wireless charging and data collection [J]. Journal of Computer Applications, 2020, 40(6): 1745-1750.
[3]	YANG Yang, PAN Dazhi, LIU Yi, TAN Dailun. New simplified model of discounted {0-1} knapsack problem and solution by genetic algorithm [J]. Journal of Computer Applications, 2019, 39(3): 656-662.
[4]	DONG Baihong, DENG Jian, ZHANG Dingjie, WU Weigang. Technology on data forwarding and routing selection for software defined vehicular Ad Hoc network [J]. Journal of Computer Applications, 2018, 38(1): 26-30.
[5]	WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng. Mutated bat algorithm for solving discounted {0-1} knapsack problem [J]. Journal of Computer Applications, 2017, 37(5): 1292-1299.
[6]	ZHANG Sulan, ZHANG Jifu, HU Lihua, CHU Meng. Semantic annotation model for scenes based on formal concept analysis [J]. Journal of Computer Applications, 2015, 35(4): 1093-1096.
[7]	LIU Zhaoqing FU Yuchen LING Xinghong XIONG Xiangyun. Blog community detection based on formal concept analysis [J]. Journal of Computer Applications, 2013, 33(01): 189-191.
[8]	. Genetic algorithm to generate formal concept [J]. Journal of Computer Applications, 2010, 30(10): 2598-2601.
[9]	. Constructing Chebyshev polynomial synopses with greedy strategy [J]. Journal of Computer Applications, 2009, 29(08): 2253-2253.

Greedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor network

基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 25

Related Articles 9

Recommended Articles

Metrics

拓扑算法	Sink节点位置/m	在不同层的开销
拓扑算法	Sink节点位置/m	1	2	3	4	5
TPSN	（50，100）	5	28	52	52	40
TPSN	（50，50）	23	86	68	2	—
DMSP	（50，100）	2	4	20	14	12
DMSP	（50，50）	2	10	30	2	—
EGTS	（50，100）	5	16	31	34	27
EGTS	（50，50）	23	48	43	3	—
LECFO	（50，100）	2	8	36	50	54
LECFO	（50，50）	2	64	100	10	—
GST-FCA	（50，100）	2	4	10	16	14
GST-FCA	（50，50）	2	10	18	4	—