1、基于边缘智能计算的城市交通感知数据自适应恢复向朝参1,2程文辉1,2张昭1,2焦贤龙1,2屈毓锛3陈超1,2戴海鹏41（重庆大学计算机学院重庆400044）2（信息物理社会可信服务计算教育部重点实验室（重庆大学）重庆400044）3（南京航空航天大学电子信息工程学院南京210016）4（南京大学计算机科学与技术系南京210023）（）Intelligent Edge Computing-Empowered Adaptive Urban Traffic Sensing DataRecoveryXiangChaocan1,2,ChengWenhui1,2,ZhangZhao1,2,JiaoXian
2、long1,2,QuYuben3,ChenChao1,2,andDaiHaipeng41（College of Computer Science,Chongqing University,Chongqing 400044）2（Key Laboratory of Dependable Service Computing in Cyber Physical Society(Chongqing University),Ministry of Education,Chongqing400044）3（College of Electronic and Information Engineering,Na
3、njing University of Aeronautics and Astronautics,Nanjing 210016）4（Department of Computer Science and Technology,Nanjing University,Nanjing 210023）AbstractIntelligenttransportationsystems(ITSs)havebeenwidelyusedinsmartcitieswithawidespreadproblemofmissingsensingdata.Thelimitedstoragecomputingcapabili
4、tyoftrafficstationsalsoseverelyrestrictstherecoveryofsensingdataandgreatlyaffectsthenormaluseofITSs.Althoughthepowerfulcomputingcapacityofedgenodescanbeusedtoalleviatethisissue,thehighcomplexityanddynamicsofthetemporalandspatialcorrelationofsensingdatastillposeaseriouschallengetotherecoveryprocess,m
5、akingtheresultofdatarecovery,basedonstaticedgenodesdeploymentanddistribution,unsatisfactory.Inordertoeffectivelysolvethisseriesofproblems,weproposeanadaptiveurbantrafficsensingdatarecoverysystembasedonintelligentedgecomputing.Thesystemmainlyconsistsoftwoparts:Firstly,thesubmodularoptimizationtheoryi
6、susedtodesignasuboptimaldeploymentandallocationschemeforedgenodeswithatheoreticalperformancelowerbound.Secondly,weaddressadatarecoverymethodbasedonthelow-ranktheory.Atthesametime,therecoveryresultsareusedtocalculatethecorrespondingnon-missingtheoreticallowerbound,feedbacktotheedgenodes,andthenupdate
7、thedatadistributionschemetoensurean accurate recovery of subsequent sensing data.The experiments based on large-scale ITSs traces of Australiaillustratethatourmethodcanachieve90%oftheoptimalperformancefortheedgenodedeployment,andimprovethedatarecoveryaccuracyby43.8%incomparisonwiththreebaselines.Fur
8、thermore,theadaptivedatarecoveryschemecanimprovetheaccuracyby40.3%onaverage.Key words edge intelligent computing；intelligent transportation system；edge node deployment；sensing datarecovery；submodulartheory；low-ranktheory收稿日期：2021-09-23；修回日期：2022-06-10基金项目：国家自然科学基金项目（62172063,61872447,62072064）；安徽省高校
9、自然科学研究项目（KJ2021ZD0116）ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(62172063,61872447,62072064)andtheCollegeNaturalScienceResearchProjectofAnhuiProvince(KJ2021ZD0116).通信作者：陈超（）计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202110962JournalofComputerResearchandDevelopment60（3）：619634，202
10、3摘要智能交通系统（intelligenttransportationsystems,ITSs）被广泛用于智慧城市中，却普遍存在感知数据缺失问题.而交通感知站点有限的存储计算能力严重制约感知数据的恢复，极大影响 ITSs 的正常使用.虽然可以利用边缘节点强大的存储计算能力解决这个困境，但边缘节点部署的高复杂性和感知数据时空相关性的高动态性对数据精确恢复提出挑战.为了解决上述挑战，提出基于边缘智能计算的城市交通感知数据自适应恢复系统.具体地，首先利用子模优化理论，提出具有理论下界的边缘节点次优部署分配算法.然后，基于低秩理论恢复感知数据，并基于恢复结果估计非缺失下限，通过反馈自适应调整感知站点的
11、数据上传比例，从而保证数据精确恢复.最后，基于澳大利亚 600 个交通站点 1 年的感知数据构建原型系统，对所提算法进行评估.实验结果表明，所提算法的边缘节点部署性能达到最优性能的 90%以上，缺失数据恢复精度比 3 种对比方法提高 43.8%以上.同时，自适应数据恢复能够平均提高精度 40.3%.关键词边缘智能计算；智能交通系统；边缘节点部署；感知数据恢复；子模理论；低秩理论中图法分类号TP393随着城市的不断快速发展，城市交通问题日益严峻，如交通拥堵等1.为了解决这些问题，大量智能交通系统（intelligenttransportationsystems，ITSs）被广泛地部署，用于城市交
12、通感知和监控2.例如，澳大利亚新南威尔士州构建交通流量监控系统（tafficvolumeviewersystem,TVVS）3，部署超过 600 个交通感知站点.然而，由于设备故障、数据传输和系统供电等问题，感知数据缺失问题在 ITSs 中普遍存在4.例如，文献 5 统计分析发现，澳大利亚 TVVS 系统中约 25%的站点感知数据缺失率超过 60%，严重影响该系统的正常使用.因此，准确实时地恢复大规模 ITSs 缺失感知数据对实现智慧城市的智能交通至关重要.本文提出基于边缘智能计算的大规模交通缺失感知数据恢复系统，既利用大量不同交通站点感知数据之间的相关性，又利用部署在感知站点附近的边缘节点强
13、大的计算处理能力，从而实现大规模交通感知数据的精确自适应恢复.但是，要实现该系统，需要解决 2 方面的挑战：1）高计算复杂性的边缘节点部署.边缘节点部署，既需要考虑部署在不同交通感知站点的成本与收益各不相同，还与交通感知数据分配策略紧密相关，从而使边缘节点最优部署问题更加复杂，在 2.2节被证明是 NP-hard 问题.所以，如何解决这个高计算复杂性问题以实现最优部署非常具有挑战性.2）高时空动态的感知数据相关性.交通感知数据的时空相关性具有动态性、时变性和复杂性，经常受道路拓扑、感知站点位置、天气以及社会事件等多方面因素的影响6.因此，如何基于该动态的、时变的、难建模的时空相关性实现感知数据
14、的精确恢复非常具有挑战性.进一步地，数据之间的相关性影响各个交通感知站点的数据分配策略，如当感知数据之间的相关性较差时，需要增加边缘节点的分配数据量，以保证数据恢复的鲁棒性.但是感知数据之间的高时空动态相关性使保证感知数据恢复精度的鲁棒性非常困难.为了解决上述 2 个挑战，本文提出基于边缘智能计算的城市交通感知数据自适应恢复系统，主要包括 2 部分：p1）具有理论下界的边缘节点次优部署分配.针对挑战 1，首先，通过问题等价转化，解耦边缘节点部署和感知数据分配之间的复杂关系.然后，通过理论证明该问题具有非负的、单调的和子模的目标函数，以及-独立系统的约束条件.最后，基于该问题的性质分析，提出基于
15、子模理论的边缘节点次优部署算法，能够在多项式时间复杂度内获得具有理论下界的近似最优解.2）基于低秩理论的感知数据自适应精确恢复.针对挑战 2，首先，基于实际交通感知数据集，对感知数据进行时空维度的低秩分析；然后，基于该分析结果，提出基于低秩理论的时空维度联合数据恢复算法；最后，针对感知数据相关性的高时空动态变化，提出基于奇异值分解的感知数据非缺失下限估计.基于该下限估计反馈，自适应地调整各交通感知站点的感知数据分配比例，以保证感知数据的精确恢复，从而提高系统数据恢复性能的鲁棒性.综上所述，本文主要具有 3 方面的创新和贡献：1）提出基于边缘智能计算的城市交通感知数据自适应恢复系统，既利用基于子
16、模优化理论的边缘计算，又利用基于低秩理论的智能计算，还基于非缺失下限估计反馈，自适应地调整交通站点感知数据分配比例，从而实现交通感知数据的“闭环”处理，提高系统的鲁棒性.620计算机研究与发展2023，60（3）1/(2+maxcjs/mincjs)cjsesj2）针对边缘节点部署 NP-hard 问题，基于子模优化理论，通过问题解耦转化和性质分析，提出近似比为的边缘节点次优部署分配算法，其中表示任意一个边缘节点 部署在任意一个感知站点处的成本.同时，提出缺失交通感知数据的自适应恢复算法，利用基于低秩理论的感知数据恢复，以及基于奇异值分解的非缺失下限估计反馈调整，实现缺失感知数据的自适应精确恢复.3）基于澳大利亚 600 个交通感知站点 1 年的实际感知数据构建原型系统，并基于该系统进行全面且深入的实验评估.结果表明，所提算法的边缘节点部署性能达到最优性能的 90%以上，缺失数据恢复精度比 3 种方法至少提高 43.8%.同时，自适应数据恢复精度平均提高 40.3%.1相关工作为保障智能交通系统的正常运行，促进智慧城市的进一步发展，大量工作开始致力于研究城市交通感知数据的精确恢复.因此
