一种车载端为主的城市路网当前与未来速度查询方法

韩京宇; 王彦之; 陈进; 晏鑫鑫; 张怡婷

doi:10.11999/JEIT240102

一种车载端为主的城市路网当前与未来速度查询方法

doi: 10.11999/JEIT240102

南京邮电大学计算机学院南京 210003

基金项目: 江苏省重点研发计划(BE2022065-5)

详细信息

作者简介:
韩京宇：男，教授，研究方向为空间时态数据库、大数据与机器学习

王彦之：男，硕士生，研究方向为机器学习与数据挖掘

陈进：男，硕士生，研究方向为数据库系统与数据挖掘

晏鑫鑫：男，硕士生，研究方向为时空数据管理与数据挖掘

张怡婷：女，副教授，研究方向为大数据管理与网络安全

通讯作者:
韩京宇　jyhan@njupt.edu.cn

中图分类号: TN929.53; TP311.132
计量
- 文章访问数: 145
- HTML全文浏览量: 54
- PDF下载量: 16
- 被引次数: 0
出版历程
- 收稿日期: 2024-02-26
- 修回日期: 2024-06-15
- 网络出版日期: 2024-06-24
- 刊出日期: 2024-09-26

A Mobile-Side-Dominant Method for Querying Present and Future Velocity on Urban Roads

School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Funds: Jiangsu Provincial Key Research & Development Plan (BE2022065-5)

摘要

摘要: 城市智能交通管理中经常查询路段的当前和未来交通速度，该文提出一种车载边缘为主(VED)的城市路段速度查询和预测方法：车载端在速度低于一定阈值时，与其它车载端交换收集到的数据，并在本地构建轻量级的当前和历史速度索引，以支持当前速度查询。为了用尽可能少的模型支持速度预测，提出根据路段拓扑同构将路网划分成若干路段等价类，根据周期性时窗和路段等价类将整个时空划分成若干模型等价类，同一个模型等价类的路段在给定时窗呈现相似的交通运行模式。针对每个模型等价类，车载端和数据中心配合进行联邦学习，训练长短期记忆模型(LSTMs)并存储在车载端，以响应车载端对附近未来交通状况的查询。每个车载端本地索引数据、本地响应查询，避免了查询响应延迟和通信拥塞；数据保存在车载端，而非集中存放，避免了安全攻击导致的隐私泄漏。
- 智能交通 /
- 查询 /
- 预测 /
- 索引 /
- 联邦学习
Abstract: Querying present and future traffic velocities of road segments is a routine task in urban intelligence transportation management, and a Vehicle-equipped-Edge Dominant (VED) method is proposed to answer the querying of present and future velocity of urban road segments. The collected data is exchanged with the other mobile sides by every vehicle-equipped mobile side when the mobile side’s speed falls below a given threshold, and the light-weighted present and history velocity indexes are constructed locally to support the querying of present velocity. To train as few models as possible to predict future velocities, a road network is proposed to be partitioned into a set of road-segment clusters based on the segments’ topological morphism and the spatio-temporal space is proposed to be partitioned into a set of model-equivalence classes according to the periodic time windows and road-segment clusters. The similar traffic patterns are exhibited by the road segments in the same model-equivalence class within the given time window. For every model-equivalence class, the federated learning is performed between the mobile sides and the data center to train the Long Short-Term Memories (LSTMs) which are stored at the mobile sides to answer the querying of future velocities of nearby areas. Data is indexed by every mobile side and queries are answered locally, thus the query response latency and possible communication congestion can be avoided. Further, data is stored at the mobile sides, rather than at one data center, so as to prevent the privacy leakage due to security attacks.
- Intelligence transportation /
- Query /
- Prediction /
- Index /
- Federated learning

HTML全文

图 1 路网上车载端数据交换的示例

下载: 全尺寸图片幻灯片

图 2 路段z的进入与引出路段

下载: 全尺寸图片幻灯片

图 3 时空立方2-1-3-SH(z,5)中的2-3-IC(z,5)

下载: 全尺寸图片幻灯片

图 4 进入路段同构的推导示例

下载: 全尺寸图片幻灯片

图 5 z和z'的进入路段示例

下载: 全尺寸图片幻灯片

图 6 模拟数据集上gc随η的变化

下载: 全尺寸图片幻灯片

图 7 Geolife数据集上gc随η的变化

下载: 全尺寸图片幻灯片

图 8 Geolife上时隙范围对当前查询精度的影响(当前路段)

下载: 全尺寸图片幻灯片

图 9 Geolife上路段范围对当前查询精度的影响(当前时隙)

下载: 全尺寸图片幻灯片

图 10 Geolife上LSTM的数量随mn同构值的变化

下载: 全尺寸图片幻灯片

图 11 Geolife上LSTM的数量随β的变化

下载: 全尺寸图片幻灯片

图 12 未来查询精度随mn的变化(k=6)

下载: 全尺寸图片幻灯片

图 13 未来查询精度随时隙数k的变化(m=n=2)

下载: 全尺寸图片幻灯片

图 14 VED和Trellis时空覆盖率的对比

下载: 全尺寸图片幻灯片

图 15 不同时空范围下当前查询精度的对比

下载: 全尺寸图片幻灯片

2 inSphere

输入：路网$ \mathrm{D}\mathrm{N} $，进入同构参数$ m $，目标路段$ \mathrm{t}\mathrm{s}\mathrm{g} $
输出：路段$ \mathrm{t}\mathrm{s}\mathrm{g} $的$ m $跳距内的进入路段
(1) 初始化队列$ Q $并将$ \mathrm{t}\mathrm{s}\mathrm{g} $入队
(2) $ \mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{t}\left(\mathrm{t}\mathrm{s}\mathrm{g}\right),\mathrm{ }\mathrm{r}\mathrm{e}\mathrm{t}\leftarrow \varnothing $
(3) while $ Q $非空 do
(4) 　$ \mathrm{s}\mathrm{g}\leftarrow {Q}.\mathrm{p}\mathrm{o}\mathrm{p}\left(\cdot\right) $, $ \mathrm{r}\mathrm{e}\mathrm{t}\leftarrow \mathrm{r}\mathrm{e}\mathrm{t}\cup \left\{\mathrm{s}\mathrm{g}\right\} $
(5) 　if $ \left\|\mathrm{s}\mathrm{g}\right\| < m $ then
(6) 　　获取$ \mathrm{s}\mathrm{g} $的所有直接前驱并将它们送入队列$ Q $
(7) 　end
(8) end

下载: 导出CSV

1 同构路段划分

输入：路网$ \mathrm{D}\mathrm{N} $，同构参数$ m $和$ n $，特征标签集合$ L $
输出：路段的同构分组
(1) 将$ \mathrm{D}\mathrm{N} $的第1个路段$ \mathrm{s}\mathrm{g} $压入栈$ \mathrm{S}\mathrm{K} $中
(2) while $ \mathrm{S}\mathrm{K} $非空 do
(3) 　$ \mathrm{s}\mathrm{g}\leftarrow \mathrm{S}\mathrm{K}.\mathrm{p}\mathrm{o}\mathrm{p}\left(\cdot\right) $
(4) 　if $ \mathrm{s}\mathrm{g} $未被处理过 then
(5) 　　　　$ \mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{t}\left(\mathrm{s}\mathrm{g}\right) $
(6) 　　　$ \mathrm{s}\mathrm{g}\mathrm{的}\mathrm{前}\mathrm{驱}\mathrm{路}\mathrm{段}\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{g}\mathrm{s}\leftarrow \mathrm{i}\mathrm{n}\mathrm{S}\mathrm{p}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\left(\mathrm{D}\mathrm{N},\mathrm{s}\mathrm{g},m\right) $
(7) 　　　$ \mathrm{s}\mathrm{g}\mathrm{的}\mathrm{后}\mathrm{继}\mathrm{路}\mathrm{段}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{s}\mathrm{g}\mathrm{s}\leftarrow \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{S}\mathrm{p}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\left(\mathrm{D}\mathrm{N},\mathrm{s}\mathrm{g},n\right) $
(8) 　　　$ \mathrm{h}\mathrm{c}\leftarrow \mathrm{f}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}\left(\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{g}\mathrm{s},\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{s}\mathrm{g}\mathrm{s},L\right) $
(9) 　　　根据$ \mathrm{h}\mathrm{c} $将$ \mathrm{s}\mathrm{g} $归类
(10) end
(11) if $ \mathrm{s}\mathrm{g} $的邻接路段$ w $未被分类过 then
(12) 　　 push$ \left(w\right) $
(13) end
(14) else
(15) 　　 $ \mathrm{s}\mathrm{g}=\mathrm{S}\mathrm{K}.\mathrm{p}\mathrm{o}\mathrm{p}\left(\cdot\right) $
(16) end

下载: 导出CSV

3 响应未来交通查询

输入：车载端的LSTM模型，对未来交通的查询$ \mathrm{f}\mathrm{q}\left(\mathrm{r}\mathrm{s},\mathrm{t}\mathrm{s}\right) $，当前　速度索引PVI，恢复矩阵$ \bf{A}\bf{V} $
输出：对应的时空单元$ \mathrm{S}\mathrm{G}\left(\mathrm{r}\mathrm{s},\mathrm{t}\mathrm{s}\right) $的预测速度
(1) $ \mathrm{l}\mathrm{s}\mathrm{t}\mathrm{m}\leftarrow \mathrm{车}\mathrm{载}\mathrm{端}\mathrm{对}\mathrm{应}\mathrm{于}\mathrm{S}\mathrm{G}\left(\mathrm{r}\mathrm{s},\mathrm{t}\mathrm{s}\right)\mathrm{的}\mathrm{L}\mathrm{S}\mathrm{T}\mathrm{M}\mathrm{模}\mathrm{型} $
(2) $ \mathrm{s}\mathrm{h}\leftarrow \mathrm{P}\mathrm{V}\mathrm{I}\mathrm{中}\mathrm{对}\mathrm{应}\mathrm{于} $mn(k–1)–SH(rs,ts–1)时空范围的样本概况
(3) 预测集$ \mathrm{p}\mathrm{v}\leftarrow \varnothing $
(4) for $ \mathrm{c}\mathrm{l}\in \mathrm{s}\mathrm{h} $ do
(5) 　$ \mathrm{v}\mathrm{v}\leftarrow \mathrm{计}\mathrm{算}\mathrm{c}\mathrm{l}\mathrm{中}\mathrm{的}\mathrm{速}\mathrm{度} $
(6) 　if $ \mathrm{c}\mathrm{l} $ 为空 then
(7) 　　$ \mathrm{v}\mathrm{v}\leftarrow \bf{A}\bf{V}\left[\mathrm{r}\mathrm{s},\mathrm{t}\mathrm{s}\right]\mathrm{中}\mathrm{的}\mathrm{数}\mathrm{据} $
(8) 　end
(9) 　$ \mathrm{将}\mathrm{v}\mathrm{v}\mathrm{加}\mathrm{入}\mathrm{p}\mathrm{v} $
(10) end
(11) $ \mathrm{r}\mathrm{e}\mathrm{t}\leftarrow \mathrm{l}\mathrm{s}\mathrm{t}\mathrm{m}\left(\mathrm{p}\mathrm{v}\right) $
(12) return ret

下载: 导出CSV

参考文献(21)

[1]	PELANIS M, ŠALTENIS S, and JENSEN C S. Indexing the past, present, and anticipated future positions of moving objects[J]. ACM Transactions on Database Systems, 2006, 31(1): 255–298. doi: 10.1145/1132863.1132870.
[2]	PFOSER D, BRAKATSOULAS S, BROSCH P, et al. Dynamic travel time provision for road networks[C]. The 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Irvine, USA, 2008: 68. doi: 10.1145/1463434.1463513.
[3]	CHANG Jundong. Spatial-temporal based traffic speed imputation for GPS probe vehicles[C]. The Fifth International Conference on Network, Communication and Computing, Kyoto, Japan, 2016: 326–330. doi: 10.1145/3033288.3033339.
[4]	CHEN Rongsheng and LEVIN M W. Traffic state estimation based on Kalman filter technique using connected vehicle V2V basic safety messages[C]. 2019 IEEE Intelligent Transportation Systems Conference, Auckland, New Zealand, 2019: 4380–4385. doi: 10.1109/ITSC.2019.8917343.
[5]	崔艳玲, 金蓓弘, 张扶桑. 基于数据融合的高速公路交通状况检测[J]. 计算机学报, 2017, 40(8): 1798–1812. doi: 10.11897/SP.J.1016.2017.01798. CUI Yanling, JIN Beihong, and ZHANG Fusang. Highway traffic condition detection with data fusion[J]. Chinese Journal of Computers, 2017, 40(8): 1798–1812. doi: 10.11897/SP.J.1016.2017.01798.
[6]	BEI Pan, DEMIRYUREK U, and SHAHABI C. Utilizing real-world transportation data for accurate traffic prediction[C]. IEEE 12th International Conference on Data Mining, Brussels, Belgium, 2012: 595–604. doi: 10.1109/ICDM.2012.52.
[7]	HE Zhixiang, CHOW C Y, and ZHANG Jiadong. STCNN: A spatio-temporal convolutional neural network for long-term traffic prediction[C]. The 20th IEEE International Conference on Mobile Data Management, Hong Kong, China, 2019: 226–233. doi: 10.1109/MDM.2019.00-53.
[8]	TANG Keshuang, CHEN Siqu, CAO Yumin, et al. Short-term travel speed prediction for urban expressways: Hybrid convolutional neural network models[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(3): 1829–1840. doi: 10.1109/TITS.2020.3027628.
[9]	TONG Guan, PENG Jiaheng, and LIANG Jun. Spatial-temporal graph multi-gate mixture-of-expert model for traffic prediction[C]. IEEE 26th International Conference on Intelligent Transportation Systems, Bilbao, Spain, 2023: 36–41. doi: 10.1109/ITSC57777.2023.10422031.
[10]	LI Maosen, CHEN Siheng, SHEN Yanning, et al. Online multi-agent forecasting with interpretable collaborative graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 4768–4782. doi: 10.1109/tnnls.2022.3152251.
[11]	岳猛, 王怀远, 吴志军, 等. 云计算中DDoS攻防技术研究综述[J]. 计算机学报, 2020, 43(12): 2315–2336. doi: 10.11897/SP.J.1016.2020.02315. YUE Meng, WANG Huaiyuan, WU Zhijun, et al. A survey of DDoS attack and defense technologies in cloud computing[J]. Chinese Journal of Computers, 2020, 43(12): 2315–2336. doi: 10.11897/SP.J.1016.2020.02315.
[12]	QI Bozhao, KANG Lei, and BANERJEE S. A vehicle-based edge computing platform for transit and human mobility analytics[C]. The Second ACM/IEEE Symposium on Edge Computing, San Jose, USA, 2017: 1. doi: 10.1145/3132211.3134446.
[13]	吴洪越, 陈志伟, 石博文, 等. 一种面向边缘计算环境的去中心化服务请求分发方法[J]. 计算机学报, 2023, 46(5): 987–1002. doi: 10.11897/SP.J.1016.2023.00987. WU Hongyue, CHEN Zhiwei, SHI Bowen, et al. Decentralized service request dispatching for edge computing systems[J]. Chinese Journal of Computers, 2023, 46(5): 987–1002. doi: 10.11897/SP.J.1016.2023.00987.
[14]	张晓东, 张朝昆, 赵继军. 边缘智能研究进展[J]. 计算机研究与发展, 2023, 60(12): 2749–2769. doi: 10.7544/issn1000-1239.202220192. ZHANG Xiaodong, ZHANG Chaokun, and ZHAO Jijun. State-of-the-art survey on edge intelligence[J]. Journal of Computer Research and Development, 2023, 60(12): 2749–2769. doi: 10.7544/issn1000-1239.202220192.
[15]	WANG Tian, LUO Hao, ZHENG Xi, et al. Crowdsourcing mechanism for trust evaluation in CPCS based on intelligent mobile edge computing[J]. ACM Transactions on Intelligent Systems and Technology, 2019, 10(6): 62. doi: 10.1145/3324926.
[16]	FELDMAN M, LAI K, STOICA I, et al. May. Robust incentive techniques for peer-to-peer networks[C]. The 5th ACM Conference on Electronic Commerce, New York, USA, 2004: 102–111. doi: 10.1145/988772.988788.
[17]	陈山枝, 葛雨明, 时岩. 蜂窝车联网(C-V2X)技术发展、应用及展望[J]. 电信科学, 2022, 38(1): 1–12. doi: 10.11959/j.issn.1000-0801.2022007. CHEN Shanzhi, GE Yuming, and SHI Yan. Technology development, application and prospect of cellular vehicle-to-everything (C-V2X)[J]. Telecommunications Science, 2022, 38(1): 1–12. doi: 10.11959/j.issn.1000-0801.2022007.
[18]	HOCHREITER S and SCHMIDHUBER J. Long short-term memory[J]. Neural Computation, 1997, 9(8): 1735–1780. doi: 10.1162/neco.1997.9.8.1735.
[19]	RAMSAK F, MARKL V, FENK R, et al. Integrating the UB-tree into a database system kernel[C]. The 26th International Conference on Very Large Data Bases, Cairo, Egypt, 2000: 263–272.
[20]	NIELSEN F. On a generalization of the Jensen–Shannon divergence and the Jensen–Shannon centroid[J]. Entropy, 2020, 22(2): 221. doi: 10.3390/e22020221.
[21]	MCMAHAN B, MOORE E, RAMAGE D, et al. Communication-efficient learning of deep networks from decentralized data[C]. The 20th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, USA, 2017: 1273–1282.