基于可靠性保障的车联网中服务功能链映射算法_孟芸.pdf

第 59 卷 第 1 期2023 年 1 月南京大学学报（自然科学）（NATURAL SCIENCE）Vol.59,No.1Jan.,2023JOURNAL OF NANJING UNIVERSITY基于可靠性保障的车联网中服务功能链映射算法孟芸1*,牛永豪1,刘鑫一2,代亮1（1.长安大学电子与控制工程学院，西安，710064；2.长安大学信息工程学院，西安，710064）摘要：为支持未来交通系统中的海量服务，网络运营商将车辆作为移动智能终端加入物理设施网络来参与网络功能虚拟化是一种有前景的解决方案.然而，与静态网络不同，车联网的动态拓扑会使部分物理链路发生中断，使承载的虚拟链路失效，导致服务失败.以保障链路可靠性为约束，以提高服务映射成功率为优化目标，提出一种针对动态网络的服务功能链优化映射算法.首先，采用随机几何以及矩生成函数理论分析得出链路可靠性解析表达式，建立移动性物理网络中服务功能链的成功映射条件集合；其次，构造基于可靠性保障的服务功能链映射优化模型；最后，为了实现低复杂度求解，在可靠物理链路提取方案的基础上，采用子图同构的基本思想，结合匹配发散概率优化剪枝效率，并引入适应度匹配以提升映射成功率，从而提出高效映射算法.实验结果证明，与经典的属性排序映射算法以及设备位置映射算法相比，提出的算法能保障链路的可靠性，提高服务映射的成功率.关键词：服务功能链映射，车联网，可靠性，适应度，映射成功率中图分类号：TN929.5 文献标志码：AReliability assurancebased service function chain embedding algorithm in Internet of VehiclesMeng Yun1*,Niu Yonghao1,Liu Xinyi2,Dai Liang1(1.School of Electronics and Control Engineering，Changan University，Xian，710064，China；2.School of Information Engineering，Changan University，Xian，710064，China)Abstract:To support the massive services in the future transportation system，adding vehicles as mobile intelligent terminals into the physical substrate network to participate in network function virtualization is a promising solution.However，unlike the static network，the dynamic topology of the Internet of Vehicles induces the link interruption，and leads to the failure of the embedded virtual links and the related services.Therefore，this paper proposes a service function chain embedding optimization algorithm for the dynamic network with guaranteeing the link reliability，which aims at improving the success embedding ratio.Firstly，the expression of link reliability is obtained by stochastic geometry and moment generating function theory，and a set of successful embedding conditions of the service function chain in the dynamic network is established.Secondly，the optimization model of service function chain embedding is established under guaranteeing the link reliability.Thirdly，to solve the problem with a low complexity，the matching divergence probability is proposed to increase the pruning efficiency，the fitness matching is introduced to improve the success embedding ratio，and the reliable physical link extraction is designed to guarantee the link reliability.Then the service function chain embedding algorithm is given.Experimental results show that the proposed algorithm guarantees the reliability of the embedding links in dynamic networks，while improving the success embedding ratio with the compared algorithms.Key words:service function chain embedding,Internet of Vehicles,reliability,fitness,embedding success rateDOI：10.13232/ki.jnju.2023.01.017基金项目：国家重点研发计划（2020YFB1600400），陕西省重点研发计划（2022GY193，2021KW13），浙江省交通运输厅科技计划（2021032）收稿日期：2022-09-06*通讯联系人，Email：南京大学学报（自然科学）第 59 卷在未来的智能交通系统中，为了进一步提升交通效率以及驾驶舒适性，网络运营商需要支持许多高速率低延迟的新兴定制服务，包括车辆社交网络、协作感知、高精地图、车载多媒体娱乐等1.这些定制服务通常由一系列服务功能组件按序组成，定义为服务功能链（Service Function Chain，SFC），采取传统的专用硬件进行部署存在成本高以及更新难的问题.因此，引入网络功能虚拟化（Network Function Virtualization，NFV）技术，将每项功能以虚拟网络功能组件的形式在物理网络的通用服务器上运行，实现灵活、低成本的部署2.但如果将所有的服务功能组件都部署在路侧设施上，由于车辆的移动性以及路边设施资源的有限性，会存在中断率高和服务映射成功率低的问题3.车辆作为移动终端，其智能程度、计算能力以及通信能力日益提升，数据处理能力和信息交互潜力已然较高，因此，结合车辆部署的 NFV 技术能减轻单一路侧设施部署带来的部署资源受限、高中断率以及低映射成功率的问题，能大幅推进海量新兴服务在交通系统中的大规模应用，因而受到了关注4.结合车辆部署的 NFV 技术需要通过有效的映射方案将各 SFC 中的服务功能组件映射在部署的车辆节点上，使节点之间通过有序协作完成服务3，5-7，因此，在服务的实现过程中，数据需要根据特定的 SFC 按顺序流经承载服务功能组件的车辆节点，并在对应的服务组件上进行相应的计算处理.然而，车联网中的服务功能链的映射问题面临特有的挑战.与静态有线网络不同，车联网具有动态的无线网络拓扑，车辆节点的移动性以及链路间的动态干扰会影响车间链路的可靠性8-9.如果映射车间链路由于移动和干扰而中断，其上承载的 SFC 的数据传输会失效，导致服务失败.因此，映射车间链路的可靠性会直接影响服务能否成功完成10.文献 3，5-7 针对包含车联网在内的移动网络提出服务功能链的映射方案.Zhang et al3提出一种基于车辆位置的映射方案，优先将服务功能节点映射在地理位置接近网络边缘的节点上.Wang et al5将智能识别网络引入车联网的资源模型，使其能在分布式的异构资源上部署复杂的服务功能组.Wang et al6基于深度神经网络以及多粒度级联森林对业务特点进行识别，提出一个车联网中的智能 SFC 映射策略.Nmeth et al7引入移动计算节点充当云计算和边缘计算的基础设施，考虑节点距离以及电池限制，设计了最小化部署成本的映射方案.然而，在已有的移动网络服务功能链的映射研究中，还没有对网络中的物理映射链路的可靠性进行度量以及区分.已有部分研究关注服务功能链的可靠映射问题.针对物理设备故障，Wang et al11提出一种降低带宽开销的联合路径备份模型，Alleg et al12提出一种联合多样性选择和定制冗余机制来提供NFV 框架下的弹性服务.针对硬件以及软件故障，Chen and Wu13设计了最小化服务时延的映射方案，Qu et al14通过基于共享资源的分配策略权衡给定服务链的可靠性、带宽和计算资源消耗，提出一种确定所需软件备份数量的增量映射方法.然而，文献 11-14 对服务功能链的可靠映射问题的研究工作通常关注硬件故障、软件故障及维修周期，其中的故障及维修模型是能够预知的概率模型，并在同类设备上具有一致性.然而，车联网中链路的可靠性与其拓扑以及所受干扰密切相关，不同链路的可靠性之间存在差异，因此具有不确定以及各异性.本文针对车联网中车辆节点的移动性给服务功能链映射带来的特有挑战，采用随机几何以及矩生成函数理论推理车联网中链路可靠性解析式，建立针对移动网络的服务功能链的成功映射条件，构造基于可靠性保障的服务功能链映射优化模型.为了实现低复杂度求解，根据子图同构的基本思想，设计可靠物理链路提取方案，使用匹配发散概率优化剪枝效率，并引入适应度匹配以提高映射成功率，提出基于可靠性保障的高效映射算法，得到 SFC的高效映射.1 系统模型与优化问题 1.1服务模型服务集合记为GS=GS，k，kK，其 中，第k个 服 务 对 应 的 功 能 链 记 为 图GS，k=(VS，k，ES，k)，对应点集合VS，k=vS，ki为第k个服务 174第 1期孟芸等：基于可靠性保障的车联网中服务功能链映射算法的功能节点集合，vS，ki为第k个服务的第i个功能节点.边集合ES，k=|eS，kijvS，ki，vS，kj VS，k为第k个服务中的虚拟链路集合，其中，eS，kij为vS，ki与vS，kj之间的虚拟链路.对应VS，k，记CS，k=CS，kivi VS，k为每个节点所需计算资源形成的向量，其中，CS，ki为完成功能组件vS，ki所需的计算单元的个数.记TS，k=TS，kijeS，kij ES，k为对应每条虚拟链路所需传输资源形成的矩阵，其中，TS，kij为完成eS，kij信息交互所需要的传输单元的个数.1.2物理网络模型将车联网建模为有向图，记为GP=(VP，EP)，其中，VP=vPi为物理节点集合，vPi为第i辆车；EP=|ePijvPi，vPj VP为物理链路集合，其中，ePij为车辆vPi与vPj之间的链路.车间链路的最大通信范围记为R，即如果vPi与vPj距离小于R，则存在链路ePij.对应VP，记CP=CPivi VP为每个物理节点具备计算资源形成的向量，其中，元素CPi为第i辆车所具备的计算单元的个数.记TP=TPijePij EP为对应每条物理链路具备的传