SDN 和MEC 架构下V2X 卸载与资源分配

张海波，王子心，贺晓帆

（1.重庆邮电大学通信与信息工程学院，重庆 400065；2.武汉大学电子信息学院，湖北 武汉 430072）

1 引言

随着无线通信技术的飞速发展，联网的车辆可以通过车辆对基础设施（V2I,vehicle-to-infrastructure）和车辆对车辆（V2V,vehicle-to-vehicle）通信方式形成车载自组网（VANET,vehicular Ad Hoc network）[1-4]。在VANET 中，车辆均配备车载单元（OBU,on board unit），因此具有计算能力和存储能力。然而车辆有限的计算和存储资源难以支持计算密集型的车辆服务，这种能力限制给VANET提出了新的问题。为了解决这一难题，欧洲电信标准化协会（ETSI,European Telecommunications Standards Institute）于2014 年提出移动边缘计算（MEC,mobile edge computing），使云计算服务靠近无线网络边缘，在移动车辆附近提供基于云的服务[5-7]。

MEC 服务器部署在无线网络的边缘，缩短了计算服务器与移动车辆的距离，使移动车辆可以将计算任务卸载至MEC 服务器进行计算。MEC 不仅满足了车辆计算能力扩展的要求，而且弥补了远程云计算导致的长时延的不足[8]。汽车工业的快速发展让车辆也有了计算和缓存能力，车辆计算任务既可以卸载到MEC 服务器进行V2I 通信，也可以卸载到相邻车辆进行V2V 通信。

车辆的移动性和网络拓扑结构的动态变化导致网络稳健性变差。不断发展的5G 接入技术已经应用到V2X通信中，但是5G中的设备对设备（D2D,device-to-device）通信技术还不成熟，目前最可行的方案是结合不同的访问技术来保持可伸缩性和灵活性[9-11]。幸运的是，软件定义网络（SDN,software defined network）具有集成不同访问技术的潜力[12]。SDN 使数据平面与控制平面解耦，其可编程性使网络更加灵活，可以更好地收集车辆动态信息，应用程序可以选择合适的无线接入接口来传输数据[13]。MEC 异构车载网络体系结构中引入的SDN 控制器允许在同一网络体系结构下集成多个网络协议、标准以及灵活管理网络资源。

目前，已存在许多关于MEC 的研究。Zhang等[14]为了降低计算卸载的时延和传输成本，提出了一种基于云的MEC 车载网络卸载框架，减少了计算任务执行的时间消耗和车辆移动性带来的影响。Li 等[15]提出了一种基于Ad Hoc 的多设备任务调度策略。Kan 等[16]通过将计算密集型任务转移到MEC服务器来提升服务质量（QoS,quality of service），将优化问题表述为一个成本最小化问题，并提出了一种启发式算法来解决该问题。You 等[17]考虑了多用户MEC 系统中的资源分配问题，在时延约束下使系统能耗最小化。Deng 等[18]考虑一个多小区MEC 场景，并提出了自适应顺序卸载博弈方法来解决卸载问题。Zhang 等[19]利用拍卖理论提出了一种资源分配机制。Zheng 等[20]考虑动态环境下的多用户计算卸载问题，将移动用户卸载决策过程建模为随机博弈。Mao 等[21]为了降低执行时延和计算能耗，对具有多个独立任务的MEC 系统联合优化任务卸载调度和传输功率分配。但是以上文献未将V2I 模式扩展至V2V 模式，同时忽略了复杂的V2X接入方式和初始卸载节点的合理选择对于系统性能的影响。

SDN 代表了一种新兴的网络范式，它具有整合VANET 的潜力[22]。Liu 等[10]将SDN 引入MEC 异构车载网络，该网络能够在V2X 通信中提供所需的数据速率和可靠性，同时满足应用的具体需求，保持良好的可扩展性和响应性。Huang 等[23]将SDN与MEC 相结合，提出了一种可编程、灵活、可控的5G 软件定义车载网络架构。Huang 等[24]针对复杂的VANET V2V 卸载问题，设计了基于MEC 和SDN 的卸载框架，为车辆寻找最佳卸载路径。李萌等[25]提出了一种基于移动边缘计算的新型网络架构，将软件定义的车载网络中的容错数据传输和计算节点选择过程建模为部分可观测马尔可夫决策过程，使系统成本最小化。然而，以上场景并未进行有效的资源分配，并且V2I 通信模式下的MEC服务器和V2V 通信模式下的车辆所能提供的计算资源都是有限的。因此，在移动车辆任务交付过程中，仍然存在与任务计算相关的挑战，即如何选择恰当的交付节点；如何在资源有限的情况下合理分配资源，使车辆以最小成本完成任务计算。

针对以上问题，本文构建了一种基于SDN 辅助的MEC 车载网络架构，提出一种联合任务卸载与资源分配（JTORA,joint task offloading and resource allocation）机制，联合优化车载网络中的卸载策略、上行子信道分配、传输功率分配和计算资源调度。将SDN 扩展到车辆网络，SDN 控制器可在全局视野下感知网络状态、收集设备信息，同时使车辆可以选择合适的接入方式进行任务卸载。将优化问题转化为最优卸载决策、传输功率分配、子信道分配和计算资源分配问题。优化目标是在约束条件下使系统开销最小化。由于优化问题的NP-hard 性质，本文将原优化问题转化为3 个子算法的相互迭代，进行有效求解。通过分布式势博弈对卸载决策进行建模和分析，并且证明了纳什均衡的存在性。为了在初始阶段得到一个较为满意的匹配对象，采用Agglomerative Clustering 匹配初始卸载节点。利用Q-learning 子算法对传输功率、上行传输信道以及计算资源进行合理分配。仿真结果表明，该机制能有效降低系统总开销。

2 基于SDN 与MEC 的系统模型和优化问题制定

2.1 系统模型

本文构建了基于SDN 辅助的MEC 车载网络模型，网络模型架构如图1 所示。在这个模型中，道路一侧部署路侧单元（RSU,road side unit），每个RSU 都配备一个MEC 服务器。MEC 服务器中的SDN 控制模块将控制平面与数据平面解耦，基于SDN 的车载网络可以实现VANET 与5G 蜂窝网络的集成，同时SDN 控制器可以收集移动设备和MEC 的信息，从全局视野感知网络状态。该网络架构分为三层，具体如下。在用户数据区域，车辆可以通过RSU 将计算任务卸载至MEC 服务器进行V2I 模式通信，也可以将计算任务卸载至相邻车辆进行V2V 模式通信。道路上有N个服从泊松分布的车辆，表示为N={v1,v2,v3,…,vN}。由于车辆和MEC 服务器均可提供计算服务，因此将它们统一定义为服务节点，表示为 G={g1,g2,g3,…,gM}。在网络控制区域部署SDN 控制器，可灵活管理网络资源，全局掌握网络信息，集成多种网络协议和标准，如车载网络、物联网网络和数据网络[25]。网络应用区域由多种网络应用填充而成，通常涉及数据和资源的交换，网络设计的目标就是为了满足这些应用的要求。

为了有效地复用频谱，V2I 模式和V2V 模式在同一频段工作。系统总频谱被分成K个正交子信道，表示为 K={1,2,3,…,K}，每个子信道带宽为BHz。假设每个车辆都有一个计算密集型的任务需要完成，且每个车辆最多分配一个子信道。车辆vi的计算任务可以被描述为，i∈N，其中，di表示计算任务Ti的输入数据大小，包括程序代码和输入参数；表示任务计算完成后的输出大小；si表示完成计算任务Ti所需的CPU 周期数；计算任务Ti所能容忍的最大时延。车辆卸载策略集合表示为 A={a1,a2,a3,…,aN}，若ai=1，则表示vi将任务卸载到服务节点进行计算；若ai=0，则表示vi在本地执行计算任务。类似于之前在移动边缘计算领域的许多工作，本文考虑一个静态网络场景，即车辆集合N 以及网络拓扑结构在计算卸载期间保持不变[26]。

图1 基于SDN 辅助的MEC 车载网络模型架构

2.2 通信模型

在基于SDN 辅助的MEC 车载网络架构中，用户数据区域的每个车辆vi均可将其计算任务Ti卸载到MEC 服务器处理，也可卸载到邻近车辆进行计算，或者在本地执行其计算任务。为了提高频谱利用率，V2V 通信模式复用V2I 模式的上行传输信道。因此，vi在子信道k上的信噪比（SINR,signal to interference plus nois e ratio）可以表示为

其中，pi表示vi的上行传输发送功率，表示vi与服务节点gj在子信道k上的信道增益，N0表示白高斯噪声功率，表示V2I 用户对vi的干扰，表示V2V 用户对vi的干扰。

为了更好地描述信道分配状况，引入信道连接矩阵C与C′，分别为NC×K和ND×K的二元变量矩阵，其中NC和ND分别代表V2I 模式和V2V 模式的用户数量，其二元变量cx,k和表示子信道k是否被分配给用户x或y。若cx,k=1（=1），则表示子信道k被分配给用户x（y）以进行上行数据传输；若cx,k=0（=0），则表示子信道k未被分配给用户x（y）。

在V2X 车载网络中，干扰环境复杂，必然存在跨层干扰。对vi来说，若选择的服务节点为MEC 服务器，则和可以分别表示为和；若选择的服务节点为车辆，则进行V2V 模式通信，和可以分 别表示 为和

根据上述信息，车辆vi的上行传输速率表示为

2.3 计算模型

假设每个车辆vi均有一个计算任务Ti需要完成，并且vi可以通过文献[27-28]中的方法来获得任务信息。任务卸载计算或本地执行均会带来时延和能量消耗，接下来，将具体讨论在不同任务处理方式下的时延和能耗计算模型。

1)本地计算

车辆vi的计算能力为，并且不同的车辆拥有不同的计算能力，则本地执行时延为

根据文献[29]，计算能量消耗为

其中，κ为能耗参数[30-31]，设置为κ=10-28。

结合式(3)和式(4)，将本地执行方案的总开销定义为

其中，α与β分别表示时延和能耗的权重因子，且满足α+β=1,0≤α≤1,0≤β≤ 1。

2)卸载计算

当车辆vi选择将其计算任务卸载至服务节点gj进行计算时，将产生传输时延、传输能耗以及计算时延。基于此，上行传输时延为

传输能耗为

卸载完成以后，服务节点gj将进行任务计算。计算过程所消耗的时间为

其中，表示服务节点gj分配给任务请求车辆vi的计算资源（表征为每秒CPU 周期）。

回程时延[32]为

因此，卸载计算方案的总开销为

为了简单起见，本文省略了服务节点的计算能耗[33]。

2.4 优化问题制定

对于车辆vi，其计算总开销为

本文的优化目标为在SDN 控制器中以系统效益最优为目标，获得最优卸载决策A*、传输功率分配P*、上行信道分配 C*和计算资源分配F*，使系统开销最小。因此，将优化问题制定为

其 中，A={a1,a2,a3,…,aN}为卸载决策集合，C={c1,c2,c3,…,cN}为信道分配集合，P={p1,p2,p3,…,pN}为传输功率分配集合，F={f1,f2,f3,…,fN}为计算资源分配方案，为服务节点gj分配给车辆vi的计算资源。约束条件C1 表示卸载决策，意味着车辆可以将其计算任务卸载给服务节点进行计算或在本地执行任务。C2 和C3 保证信道分配矩阵是二进制变量。C4 表示上行传输功率的变化范围。C5 和C6 表示分配给卸载车辆的计算资源之和为非负数值，且不能超过服务节点的最大计算能力。C7 和C8 表明任务请求车辆只能分配一个上行子信道。C9 表示时延控制，即无论是本地执行还是卸载到服务节点进行计算，总时延不能超过任务所能容忍的最大时延。

整数约束C1～C3 使式(12)问题成为一个混合整数非线性规划。由于该优化问题具有NP-hard 性质和非凸性，求解困难且不切实际。因此，本文提出了一个联合任务卸载和资源分配机制。

3 卸载策略和资源分配方案

3.1 基于Agglomerative Clustering 层次聚类的通信模式选择

层次聚类作为机器学习中非监督学习的一类方法，可以灵活控制不同层次的聚类粒度，具有强聚类能力，能满足不同的应用场景。Agglomerative Clustering 层次聚类[34]算法能够保证距离近的对象被聚类到一个簇中，采用“自底向上”聚类的思路。在本文系统模型下结合车辆任务时延要求进行聚类，将其时延要求作为特征输入，算法思路具体到本文模型如下。

输入车辆任务时延要求数据集TD={x1,x2,…,xN}，聚类簇距离度量函数，聚类簇数量J=2

输出簇划分H={hV2I,hV2V}

1)将数据集中的每一个对象生成一个簇，得到簇列表H={h1,h2,…,hN}，其中，每个簇只包含一个数据对象，即hi={xi}。

2)重复以下步骤，直到得到J个数据簇。

①根据距离度量函数计算其距离，在簇列表H中找出距离最近的2 个簇min{TD(hi,hj)}。

② 合并簇hi与hj，形成新的簇h(i+j)。

③在簇列表H中删除簇hi与hj，并添加簇h(i+j)。

针对步骤2)中①的距离计算，采用平均连锁进行计算

式(13)表示2 个簇之间任意两点之间距离的平均值，该方式可以有效地排除噪点的影响。

3)通过Agglomerative Clustering 层次聚类，将道路上的任务请求车辆进行模式分割，确定其以V2I 模式还是V2V 模式进行通信。若为V2I 模式，则选择本小区内RSU 进行通信；若为V2V 模式，则根据距离选择就近车辆为服务节点。通过模式选择，在初始阶段即为车辆选择较为合适的服务节点匹配。

3.2 卸载博弈建模

对于一个势博弈存在性质，任何异步更新过程必须是有限的，并收敛于纳什均衡[13]。将JTORA机制建模为势博弈，表示为G={N,(ai)i∈N,(ui)i∈N}，其中，ai为vi的卸载决策，ui为vi的代价函数。接下来将详细介绍JTORA 博弈模型。

玩家。每个任务请求车辆均为一个参与者，存在N个参与者竞争有限资源，每个参与者可以将任务卸载至服务节点进行任务计算或者本地计算。

策略。ai∈{0,1}为vi的卸载决策，A 为所有任务请求车辆的卸载决策集合，ai=1表示vi将卸载其计算任务至选定的卸载节点进行计算，ai=0表示vi将在本地执行其任务。

代价函数。当vi选择其卸载决策为ai时的代价函数表示为ui(ai,a-i)，其中a-i代表除vi以外的任务请求车辆的卸载决策集合。每辆车都希望通过适当的卸载策略选择来最小化开销，如式(14)所示。

势博弈收敛于纳什均衡，表示没有任何玩家有偏离当前策略的动机。具体描述介绍如下。

定义1在博弈G={a1,a2,…,aN:u1,u2,…,uN}中，存在一个策略集合使所有参与者均没有改变当前决策的动机，则称A*为G的一个纳什均衡，即

纳什均衡具有显著的自稳定性，这一特性使处于平衡状态的玩家能够得到一个双方都满意的解，因此没有玩家有偏离平衡点的动机[35]。纳什均衡对于非合作问题的解决非常重要。因为每一个任务请求车辆都满足自身理性和利己性，因此均以最小化自身代价为目标。

卸载策略制定以后，Q-learning 将进行通信和计算资源分配，以降低系统开销。

3.3 基于Q-learning 的通信与计算资源分配

Q-learning 是一种典型的强化学习方法，具有收敛性，能够使代理在给定的环境下学习最优策略[36]。将每个请求车辆视作一个代理，状态、行为、奖励设置如下。

状态。系统状态包括3 个部分s=(tc,hc,fc)。tc定义为当前系统总开销，即tc=Zall；hc定义为当前信道分配状态；fc定义为当前服务节点的有效计算资源。

动作。动作包括3 个部分，表示为信道、功率和计算资源矩阵at=[ch,p,cr]。

回报。在t时刻，代理在执行每一个可能的动作at 后，在一定的状态s下会得到一个奖励，其中，为卸载车辆vi在t迭代时刻的卸载开销，为卸载车辆vi在t迭代时刻的无干扰卸载开销。

Q-learning 采用Q 函数作为评价函数，并将其定义为状态-动作值函数，利用Bellman 最优性方程给出最大化总期望收益的最优策略π*[36-37]。

其中，γ(0＜γ＜ 1)为折扣因子，反映了未来收益相对于当前收益的重要性。若γ倾向于0，则代理倾向于考虑即时回报；若γ倾向于1，则代理更关注于未来的收益。

其最优策略表示为

在迭代过程中，需要对Q 值进行更新，但是无法遍历所有状态-动作对，因此通过学习速率μ对有限样本进行操作。则Q 值的更新式可以表示为

其中，μ(0≤μ≤ 1)为学习速率，代表了当前学习知识对之前学习知识的影响。

在迭代过程中本文采用ε-greedy 算法来选择动作[36]。其中，车辆vi的行为表示为信道、功率和计算资源矩阵，表示为

动作轮廓为

ε-greedy机制中每一个动作都有非零的概率被选择，随机选择行为（random）的概率是ε，选择与最大Q 值相关的动作的概率则是1-ε。

Q-learning 算法详细描述如下。

输入学习速率μ，折扣因子γ，贪婪系数ε，最大收敛次数E，卸载车辆集合Nˆ，服务节点状态信息

输出车辆开销

1)初始化Q 矩阵，迭代次数t=0，开始迭代；

2)根据式(20)选择动作；

3)根据式(18)更新Q 矩阵；

4)将s′更新为s；

5)更新迭代次数t=t+1；

6)重复步骤2)～步骤5)，直到达到最大收敛次数E。

3.4 纳什均衡证明

定义2 若一个势博弈G={N,(ai)i∈N,(ui)i∈N}遵从势函数ζ(A)，满足式(21)，则此博弈为完全势博弈。

定理1JTORA 博弈模型是一个完全势博弈，并且总是存在纳什均衡，满足有限改进性质。其遵从的势函数ζ(A)为

证明根据式(22)，可以得到

由式(14)可得

因此，联系式(25)和式(26)可得

组合式(23)与式(24)可知

因此，根据式(27)和式(28)可得

基于上述信息，JTORA 博弈模型是一个完全势博弈，满足式(22)所示势函数，因此至少存在一个纯策略纳什均衡并具有有限改进性质。这意味着车辆卸载决策可以达到一个有效的平衡，即任何车辆单方面改变现有卸载决策不会使自身开销进一步降低。

3.5 联合优化机制总结

JTORA 机制将初始卸载策略设置为所有车辆将其计算任务卸载到每个请求车辆使用Aggregative Clustering 选择的服务节点。计算本地计算代价，通过Q-learning 得到相应的卸载代价。比较本地计算成本和卸载成本，修改卸载策略A。然后进入循环阶段，逐个检查卸载策略中的零元素，重新分配最优资源，直到所有的车辆没有改变现有决策的动机。由于车辆满足自身理性和利己主义，只希望降低自身任务计算的成本，因此每辆车通过比较自身的本地计算成本和卸载成本来修改卸载决策。具体算法描述如下。

输入任务请求车辆数量N，服务节点数量M，初始卸载决策集合 A0及Ti，L,b，κ，α，β，μ，γ

输出A*，C*，P*，F*，Z*

1)初始化：全卸载；L=1；

2)针对每个车辆进行Aggregative Clustering聚类，以确定通信模式，计算，以及通过Q-learning 获得；

4)判断A 是否与A0相同，若不相同，则执行以下步骤；若相同，则算法结束；

5)更新卸载决策AL←A0；

6)针对每个车辆，使其卸载决策ai=1，然后更新AL，以及通过Q-learning 获得；

8)判断AL是否与AL-1相同，若不相同，则重复步骤5)～步骤7)；若相同，则算法结束；

JTORA 机制将优化问题转化为3 个子算法的相互迭代进行有效求解。在步骤2)中，Aggregative Clustering聚类需要计算数据点之间的相互距离，时间复杂度为O(N2)，之后根据距离度量函数更新迭代，因此聚类所需时间复杂度为O(N2logN)。本地计算与卸载计算均各需N次计算，因此步骤2)和步骤3)的时间复杂度为O(2N+EN)；步骤5)～步骤8)的时间复杂度为O(L(2N+))。因此，JTORA 机制的总体时间复杂度为O(2N(L+1)+E(L+N)+N2logN)。

4 仿真分析

本节通过Matlab 仿真平台对SDN 和MEC 环境下的V2X 卸载与资源分配算法进行验证，给出了仿真结果，并评估了所提出机制的性能。本节在IEEE 802.11p 车辆网络场景标准和MEC 白皮书的背景下展开，采用3GPP 标准化中提出的信道增益模型[33]。考虑路边有2 个小区，每个小区都配置了RSU 和MEC 服务器。详细仿真参数如表1 所示。

表1 仿真参数

为了评估所提机制的性能，将JTORA 与其他几种机制进行比较，例如所有本地计算机制（ALCM,all local computing mechanism）、全卸载计算机制（AOCM,all offloading computing mechanism）、无聚类的Q 学习资源分配（QRNC,Q-learning resource allocation without clustering）机制、文献[33]中联合任务计算卸载与干扰管理（JCOIM,joint computation offloading and interference management）机制、初始节点筛选但随机资源分配（ARRA,agglomerative clustering with random resource allocation）机制、文献[18]中的多用户计算卸载（MCO,multi-user computation offloading）机制。

图2 为基于Aggregative Clustering 的通信模式选择，将车辆进行层次聚类，以确定其为V2I 模式通信还是V2V 模式通信。由图2 可知，距离RSU较远的车辆由于其时延需求更倾向于进行V2V 模式通信，而距离RSU 距离较近的用户，根据其对计算能力的需求选择V2I 通信方式，部分车辆由于其对时延要求高于计算能力需求，因此选择V2V通信方式，如图2(b)中虚线圈出区域所示。

图2 基于Aggregative Clustering 的通信模式选择

图3 和图4 分别为任务大小和车辆数目对于总开销的影响。由图3 和图4 可知，数据大小和车辆数目的增加，使系统总开销相应增长。本文所采用的JTORA 机制在降低系统开销方面明显优于其他策略，随着数据量和车辆数目的增加，这些机制之间的性能差异逐渐明显。导致以上仿真结果的主要原因分析如下。传统的ALCM 由于车辆本身计算能力有限而带来较大时延开销；AOCM 随着车辆数目增加导致信道干扰逐渐严重；ARRA 由于未对资源进行有效管理，当任务大小增加时，传输时延增长，因此性能较差；MCO 方案只关注卸载策略而不涉及动态资源分配，因此随着车辆数目增加，信道干扰逐渐严重，使总开销快速增长；JCOIM 应用于本文场景，由于其忽略功率分配对系统开销的影响，因此效果稍有不理想。本文基于 SDN 辅助的JTORA 机制由于有效的卸载与资源管理，使系统开销降低，同时还可以看出，卸载任务的数据量越大，人们从卸载计算中获得的时延和能耗收益就越大。

图3 任务大小与总开销关系

图4 车辆数目与总开销关系

图5 显示了算法的收敛性。随着迭代次数的增加，系统开销逐渐趋于稳定，算法收敛。AOCM 和本文提出的JTORA 机制在经过约600 次迭代后趋于收敛，而QRNC 在约800 次迭代后收敛。这是因为在选择初始卸载节点时，通过Aggregative Clustering 可以选择一个相对满意的服务节点，从而使服务请求者在初始阶段获得一定的满意度，因此可以加快收敛。

图6 显示了信道数量和系统总开销之间的关系。随着信道数的增加，干扰逐渐减小，带来传输时延的降低，从而使系统开销逐渐减小。由于AOCM 受信道数量的影响较大，对于信道干扰更加敏感，因此AOCM 曲线相比于JTORA 曲线下降速度更快。MCO 机制由于其仅考虑卸载决策的优化，却未曾考虑资源分配，因此随着信道数量增加，干扰减小，车辆更倾向于卸载计算，因此在信道数量大于19 以后，MCO 机制开销略大于AOCM。本文基于SDN 辅助的JTORA 机制能够更加灵活地管理资源，控制卸载流量，保证资源有效利用，降低系统开销。

图5 算法收敛性

图6 信道数量与总开销关系

5 结束语

本文通过考虑车载网络复杂的网络环境，构建了一种基于SDN 辅助的MEC 车载网络架构，通过引入SDN 控制器，可灵活管理网络资源，易于收集车辆状态信息，应用程序可以选择合适的无线接口进行数据传输。在此基础上，本文提出了一种基于MEC 的V2X 任务卸载和资源分配机制，通过初始卸载节点的选择、计算卸载决策、无线资源和计算资源的合理分配来最小化系统开销。仿真结果表明，该机制在不同参数变化下均能取得较好效果。