Optimization Mapping Method on Feasible Duration of Service
Function Chain in Vehicle-road Cooperative Network

doi:10.16097/j.cnki.1009-6744.2023.01.013

Abstract

Abstract: Considering the difference in the connected duration of physical links in vehicle-road cooperative network, this paper proposes an optimization model of service function chains (SFC) mapping to maximize the feasible mapping duration. First, the physical transmission network model is proposed to represent the vehicle-road cooperative network, and the connected durations are analyzed for the vehicle-to-vehicle link and the vehicle-to-road link. Then, an integer programming problem is established, aiming to maximize feasible mapping duration with the mapping constraints of SFC. To solve the NP-hard problem, this paper provides an approximation technique based on the enhanced subgraph isomorphic and design the pruning based on node characteristics, link attributes, and the connection between links to reduce the complexity. By considering the difference in the connected duration of physical links and optimizing the selection, experimental results show that the feasible mapping duration of the proposed algorithm has increased by 34.4% under the communication range equal to 150 meters and the maximum speed of the vehicle equals 60 km ⋅ h- 1 . Experimental results on the three main influencing factors, including the vehicle-vehicle communication range, the number of vehicles and the maximum vehicle speed, show that the proposed algorithm can effectively improve the feasible mapping duration of service.

Key words: information technology, service function chain, graph, mapping feasible duration, vehicle-road cooperative network

摘要： 以车路协同网络为研究对象，针对物理链路间连通时长的差异性，本文提出优化可行时长的服务功能链映射算法。首先，建立车路协同的物理传输网络模型，并分别分析车车链路和车路链路的连通时长；其次，以映射可行时长为优化目标，以服务功能链的映射规则为约束，建立整数规划问题；最后，为求解该NP-hard问题，提出基于改进子图同构的映射算法，联合考虑车路协同环境中的节点属性、链路属性及链路间关联关系，设计剪枝策略，从而实现服务链路在物理链路上的组合优化映射。实验结果表明，通过考虑物理链路连通时长的差异性，并对其进行优化选择，提出算法在车间通信距离150m和最大车速60km·h-1 条件下，可将可行时长提升34.4%；同时，在车车通信范围、车辆数以及最大车辆速度这3项主要参数设置中均可验证发现，所提算法可有效提升映射可行时长。

关键词: 信息技术, 服务功能链, 图模型, 映射可行时长, 车路协同

CLC Number:

TN929.5

MENG Yun, NIU Yong-hao, WANG Ping, DAI Liang. Optimization Mapping Method on Feasible Duration of Service Function Chain in Vehicle-road Cooperative Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 114-122.

孟芸, 牛永豪, 王萍, 代亮. 车路协同网络中服务功能链可行时长优化映射算法[J]. 交通运输系统工程与信息, 2023, 23(1): 114-122.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/10.16097/j.cnki.1009-6744.2023.01.013

http://www.tseit.org.cn/EN/Y2023/V23/I1/114

References

[1] 张毅, 姚丹亚, 李力, 等. 智能车路协同系统关键技术与应用[J]. 交通运输系统工程与信息, 2021, 21(5): 40- 51. [ZHANG Y, YAO D Y, LI L, et al. Technologies and applications for intelligent vehicle-infrastructure cooperation systems[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 40-51.]

[2] 王进文, 张晓丽, 李琦, 等. 网络功能虚拟化技术研究进展[J]. 计算机学报, 2019, 42(2): 185-206. [WANG J W, ZHANG X L, LI Q, et al. Network function virtualization technology: A survey[J]. Chinese Journal of Computers, 2019, 42(2): 185-206.]

[3] MOURADIAN C, KIANPISHEH S, ABU- LEBDEH M, et al. Application component placement in NFV-based hybrid cloud/fog systems with mobile fog nodes[J]. IEEE Journal on Selected Areas in Communications, 2019, 37 (5): 1130-1143.

[4] NEMETH B, MOLNER N, MARTIN-PEREZ J, et al. Delay and reliability-constrained VNF placement on mobile and volatile 5G infrastructure[J]. IEEE Transactions on Mobile Computing, 2021, 21(9): 3150- 3162.

[5] 王侃, 赵楠, 李军怀, 等. 移动边缘计算网络中联合无线多播的服务功能链部署算法[J]. 通信学报, 2020, 41(10): 37- 47. [WANG K, ZHAO N, LI J H, et al. Service function chain embedding algorithm with wireless multicast in mobile edge computing network[J]. Journal on Communications, 2020, 41(10): 37-47.]

[6] 汤红波, 邱航, 游伟, 等. 基于联合备份的服务功能链可靠性保障的部署方法[J]. 电子与信息学报, 2019, 41 (12): 3006-3013. [TANG H B, QIU H, YOU W, et al. A reliability-guarantee method for service function chain deployment based on joint backup[J]. Journal of Electronics & Information Technology, 2019, 41(12): 3006-3013.]

[7] 魏亮, 黄韬, 张娇, 等. 基于强化学习的服务链映射算法[J]. 通信学报, 2018, 39(1): 90-100. [WEI L, HUANG T, ZHANG J, et al. Service chain mapping algorithm based on reinforcement learning[J]. Journal on Communications, 2018, 39(1): 90-100.]

[8] 孙士清, 彭建华, 游伟, 等. 5G网络下资源感知的服务功能链协同构建和映射算法[J]. 西安交通大学学报, 2020, 54(8): 140-148. [SUN S Q, PENG J H, YOU W, et al. A coordinating composition and mapping algorithm for a service function chain with resource-aware[J]. Journal of Xi'an Jiaotong University, 2020, 54(8): 140- 148.]

[9] CAO H T, YANG L X, ZHU H B. Novel node-ranking approach and multiple topology attributes-based embedding algorithm for single-domain virtual network embedding[J]. IEEE Internet of Things Journal, 2018, 5(1): 108-120.

[10] KANG R, HE F, SATO T, et al. Virtual network function allocation to maximize continuous available time of service function chains with availability schedule[J]. IEEE Transactions on Network and Service Management, 2021, 18(2): 1556-1570.

[11] KANG R, HE F, OKI E. Robust virtual network function allocation in service function chains with uncertain availability schedule[J]. IEEE Transactions on Network and Service Management, 2021, 18(3): 2987-3005.

[12] WANG J Y, QI Q, QING S D, et al. Elastic vehicular resource providing based on service function-group resource mapping of smart identify network[J]. IEEE Systems Journal, 2018, 12(2): 1897-1908.

[13] ZHANG P Y, WANG C, AUGLA G S, et al. IoV Scenario: Implementation of a bandwidth aware algorithm in wireless network communication mode[J]. IEEE Transactions on Vehicular Technology, 2020, 69(12): 15774-15785.

[14] WANG J Y, HE B, WANG J, et al. Intelligent VNFs selection based on traffic identification in vehicular cloud networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5): 4140-4147.

[15] REN M Y, ZHANG J, KHOUKHI L, et al. A unified framework of clustering approach in vehicular AD HOC networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(5): 1401-1414.

[16] CARLETTI V, FOGGIA P, SAGGESE A, et al. Challenging the time complexity of exact sub-graph isomorphism for huge and dense graphs with VF3[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(4): 804-818.

Optimization Mapping Method on Feasible Duration of Service Function Chain in Vehicle-road Cooperative Network

车路协同网络中服务功能链可行时长优化映射算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Jian, ZHANG Chi, FU Zhi-yan, LIU Ke-liang. Research Review of Influence of Social Network Information on Travel Behavior [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 1-10.
[2]	LI Xiang, YAN Qi-peng, LUO Chen. Impact of Built Environment on Flow of Transfer Passengers Between Subway and Bus Considering Spatial Heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 100-110.
[3]	ZHENG Yue, GAO Liang-peng, CHEN Xue-wu. Investigating Influencing Factors on Metro-bus Transfer Demand Incorporating Spatial Heterogeneity Based on Multi-source Data [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 128-138.
[4]	HE Wen-wu, PEI Bo-yu, LI Ya-ting, LIU Xiao-yu, XU Shao-bing. Traffic Flow Forecasting Based on Bi-directional Adaptive Gating Graph Convolutional Networks [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 187-197.
[5]	CHEN Jian, LIU Ke-liang, LI Wu, DI Jing, PENG Tao. Spatial Heterogeneity Model of Impact of Community Built Environment on Vehicle Miles Traveled [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(6): 124-133.
[6]	ZHANG Xie, XIAO En-yuan, LIU Hong-zhi, ZHAO Yi-fei, WANG Meng-qi. Fluctuation Characteristics of Arrival Flight Flow Based on Limited Penetrable Visibility Graph [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(6): 244-257.
[7]	CHEN Qi-xiang , LV Bin , CHEN Xi-qun , HAO Bin-bin, HE Jia-xi. Impacts of Built Environment on Competition and Cooperation Relationship Between Taxi and Subway Considering Spatial Heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 25-35.
[8]	LIU Yi-cheng, LI Zhi-peng , LV Chun-pu , ZHANG Tao , LIU Yan. Network-wide Traffic Flow Prediction Research Based on DTW Algorithm Spatial-temporal Graph Convolution [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 147-157.
[9]	CHEN Ding , ZHOU Shui-ting, CHEN Yun , SU Min-xian. Traffic Performance Identification Method Based on Adaptive Congestion Index [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 137-144.
[10]	XU Dong-wei , PENG Hang , SHANG Xue-tian , WEI Chen-chen , YANG Yan-fang . Road Network Data Repair Based on Graph Autoencoder-generative Adversarial Network [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 33-41.
[11]	XU Zhen-yi, WANG Ren-jun , ZHANG Cong , WANG Rui-bin , XIA Xiu-shan. Automatic Identification of High-emitting Vehicle Based on Deep Feature Clustering [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 298-309.
[12]	ZHANG Shu-jing , XU Qi , JIA Shun-ping , LIAO Jing-yi. Spatial and Temporal Effects of New Urban Rail Transit Lines on Residential Property Value Uplift [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(4): 54-62.
[13]	ZHANG Wei-bin , ZHANG Pu-lin, SU Zi-yi , SUN Feng. Missing Data Repairs for Road Network Traffic Flow with Self-attention Graph Auto-encoder Networks [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(4): 90-98.
[14]	LI Xi,SHI Tian-yun, CHANG Bao, MA Xiao-ning, LIU Jun. Locomotive Label System Construction Method Based on Equipment Portrait [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(2): 189-195.
[15]	JIANG Yu, TONG Chu, LIU Zhen-yu, HU Zhi-tao, XU Cheng, ZHANG Hong-hai. Optimal Model of Taxiway Scheduling Based on Time Margin Control [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(1): 207-213.