1、2023 03 10计算机应用,Journal of Computer Applications2023,43(3):869-875ISSN 10019081CODEN JYIIDUhttp：/基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法叶青1，2，史昕3*，孙梦薇3，朱健3（1.国家山区公路工程技术研究中心，重庆 400067；2.重庆大学 大数据与软件学院，重庆 401331；3.长安大学 信息工程学院，西安 710064）（通信作者电子邮箱）摘要：针对交通监测传感网络时间同步拓扑的能量有效性和场景适应性问题，提出一种基于形式概念分析的交通监测传感网络贪婪性同步拓扑算法GST-FC
2、A。首先分析交通监测传感网络同步拓扑的场景适应性需求和能量有效性问题模型；其次，利用形式概念分析（FCA）对同层和相邻层传感节点的邻接特征进行关联性解析，根据最多邻居贪婪策略构建广播元组（BT）并划分同步集合；然后利用回溯广播改进传感网络时间同步协议（TPSN）算法的层探测广播策略，同时设计向上托管机制，增大已同步节点信息的共享范围，进一步缓解贪婪策略产生的局部最优解问题；最后对GST-FCA的能量有效性和场景适应性进行测试。仿真结果表明，相较于TPSN、LECFO等算法，GST-FCA在部署位置、部署规模、道路部署三个测试场景中的同步报文开销分别至少降低11.54%、24.59%和39.16
3、%。由此可见，GST-FCA能缓解局部最优解问题并降低同步报文开销，而且能在同步拓扑满足上述三个场景适应性需求下达到良好的能量有效性。关键词：交通监测传感网络；同步拓扑；形式概念分析；广播元组；贪婪策略；同步报文开销中图分类号：TP391.9 文献标志码：AGreedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor networkYE Qing1，2，SHI Xin3*，SUN Mengwei3，ZHU Jian3（1.Natio
4、nal 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）Abstract:Aiming at the energy efficiency and sc
5、ene 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
6、 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 acc
7、ording 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
8、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
9、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 probl
10、em 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
11、);broadcast tuple;greedy strategy;synchronization packet overhead0 引言 面向交通监测的无线传感网络是智能交通领域新型应用场景中的关注焦点1，传感网络具备的部署便利性2、感知协作性3、交互泛在性等优点为传统交通监测应用带来显著的改变4。实现感知协作性依赖于传感节点之间的时间文章编号：1001-9081（2023）03-0869-07DOI：10.11772/j.issn.1001-9081.2022010141收稿日期：20220211；修回日期：20220530；录用日期：20220620。基金项目：国家山区公路工程技术研究中
12、心开放基金课题（GSGZJ-2020-06）。作者简介：叶青（1994），男，重庆人，工程师，博士研究生，主要研究方向：智慧交通、车路协同、自动驾驶；史昕（1987），男，河南南阳人，副教授，博士，CCF会员，主要研究方向：无线传感网络时间同步、车联网协同感知；孙梦薇（1997），女，陕西渭南人，硕士研究生，主要研究方向：车联网协同感知；朱健（1997），男，重庆人，硕士研究生，主要研究方向：无线传感网络时间同步。第 43 卷计算机应用同步，即给特定区域内的传感节点提供一个公共通用的时间尺度5。该尺度旨在建立各个传感节点感知数据与共识时间之间的一致性映射关系，交通监测传感网络中与时序相关的所有
13、操作均需解析该项映射关系6。时间同步算法主要由同步拓扑构建和时钟偏差估计构成，其中同步拓扑旨在明确同步数据报文的传输路径并决定报文数量的传输规模，也是执行时钟偏差估计的重要前提条件7。交通监测传感网络的时间同步在能量有效性和场景适应性方面拥有独特的设计需求。能量有效性需求主要体现在：传感网络的时间同步主要依赖节点间同步报文的无线共享交换。文献 8 指出单个传感器节点将 1 Kb字节数据传输100 m所需的能量等价于执行三百万条指令消耗的能量，传输大量同步报文将加快传感器节点能量的枯竭。然而在交通监测传感网络中，传感节点的核心任务是采集处理与传输共享交通流数据，如果传感节点能量不加节制地消耗在同
14、步报文无线传输中，则传感节点的核心任务时间将大幅下降9。场景适应性需求主要体现在：交通监测传感网络的Sink节点通常考虑供电和维护的便利性进行部署，同步拓扑算法的能量有效性不能受Sink节点部署位置的影响；交通监测传感网络需要部署大规模的节点实现协同感知，同步拓扑算法的能量有效性不能受限于节点的部署规模；交通监测传感节点部署受限于道路边界呈现狭长部署形态10，部分节点的同步报文传输必须采用多跳中继方式实现11。典型时间同步拓扑构建算法主要有以下几种：1）传感网路 时 间 同 步 协 议（Timing-synchronization Protocol of Sensor Network，TPSN
15、）算法12利用层探测方法构建泛洪同步拓扑实现全网内时间同步，由于所有节点均参与同步报文传输，同步过程会产生大量冗余报文。2）PBS（Pairwise Broadcast Synchronization）算法13利用无线信道广播特性，同步位于相同广播区域内的节点，可有效减少同步报文开销，但局限于单跳同步。3）GPA（Group-wise Pair-selection Algorithm）14利用PBS算法通过层与层之间的同步传递实现多跳同步，存在大量已同步节点重复参与同步报文传输的现象，从而引入较多 额 外 的 能 量 开 销。4）DMSP（Distributed Multi-hop Synch
16、ronization Protocol）算法15是 GPA 的一种改进，设置同步节点链表保存与筛选已同步节点，避免已同步节点重复参与同步，但是忽略了多基准节点的选择问题。5）FDMS（Fast Distributed Multiple-hop Synchronization）算法16根据节点邻接 特 征 选 择 互 为 相 邻 的 三 个 节 点 执 行 RBS（Reference Broadcast Synchronization）算法17，该算法对节点拓扑连通性要求较高，仅适用于具备强连通性的拓扑结构。6）EGTS（External Gradient Time Synchronization）算法18是FDMS算法的一种改进，在邻居节点间选择参考节点多跳广播时间报文，能够减少多跳同步中已同步节点的重复报文传输量，但是同样继承了 FDMS 算法对拓扑连通性要求较高的特点。7）LECFO（Linear Estimation of Clock Frequency Offset）算法19与ICPTR（Improved Clock Parameters Tracking and Rangin