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

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

作　　者：叶青 史昕[3] 孙梦薇[3] 朱健 YE Qing;SHI Xin;SUN Mengwei;ZHU Jian(National Engineering Research Center for Mountainous Highways,Chongqing 400067,China;School of Big Data and Software Engineering,Chongqing University,Chongqing 401331,China;School of Information Engineering,Chang’an University,Xi’an Shaanxi 710064,China)

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

出　　处：《计算机应用》2023年第3期869-875,共7页journal of Computer Applications

基　　金：国家山区公路工程技术研究中心开放基金课题(GSGZJ-2020-06)。

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

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

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]