基于Stackelberg博弈的车载边缘计算任务卸载策略

张 俊， 王 杨， 张聪聪， 许闪闪

(芜湖职业技术学院 网络工程学院,安徽 芜湖 241003；2.安徽师范大学 计算机与信息学院，安徽 芜湖 241003)

引 言

随着通信和计算技术的迅猛发展，新兴的5G应用程序(例如，增强现实、自动驾驶等)不仅给车辆终端的处理能力带来了巨大压力，又给无线接入网带来了很大的负担。针对车辆终端处理能力不足的问题，采用车载边缘计算模式是一种有效的解决方案。通常情况下，主要有两种车载边缘计算的解决思路：广泛部署轻量级的服务器和挖掘附近车辆未充分利用的资源。第一种方案需要大量的资金投入，而且在非高峰时期会存在资源过剩的情况。因此，该方案面临的问题是如何寻求适中的成本来调节不断增长的任务需求。第二种方案不需要部署额外的服务器，利用附近的车辆提供大量的计算资源来缓解高峰时段的网络拥塞。未来的智能汽车将配备更强大的CPU、更大容量的数据存储单元和更先进的通信技术，以满足用户更高的需求。这意味着，第二种方法更加容易实施，任务不需要经过基站，进而减少传输时延。

尽管车载边缘计算(Vehicle Edge Computing，VEC)具有上述优势，大面积部署仍然面临着关键的挑战：(1)缺乏激励机制来刺激附近车辆提供有效的资源。自私理性的车辆如果没有收益一般不会提供服务资源，另外，基站无法获取车辆的私有信息。因此，在信息不对称的情形下，建立一种有效优化服务提供商的机制尤为重要。(2)缺乏低复杂度的任务卸载机制。每辆车都是独立的实体，只有对所有的车辆进行合理地分配，才能最小化网络总时延，达到更为理想的执行效果。

这些挑战促使我们寻找一种合适的博弈策略来鼓励车辆参与任务卸载。在VEC执行任务卸载中，服务提供者和请求者都参与其中，通过合理分配自身的资源，实现系统效用最大化。若参与者没有单方面偏离当前策略，则称这种状态为纳什均衡。因此，通过寻找任务卸载博弈的纳什均衡来确定最优定价的卸载策略。

在所有的博弈模型中，Stackelberg博弈被广泛用于解决定价问题。Stackelberg博弈的基本策略是领导者有权采取第一个行动，追随者观察领导者的行动，并据此做出自己的行动。利用Stackelberg博弈的主要优势如下：(1)能够准确地描述了服务提供者和请求者之间的交互；(2)领导者与跟随者的关系符合服务提供者与请求者的不平等地位；(3)如果Stackelberg均衡存在，则它可以为服务提供者和请求者提供最优价格和卸载比例。

因此，本文提出了一种基于stackelberg博弈的任务卸载策略，该策略能够获得最优价格和卸载比例，以便服务提供者向请求者提供服务。Stackelberg博弈用于服务提供者和请求者之间的信息交互，接着推导出纳什均衡状态，并提出了一种最优定价的任务卸载算法。大量的仿真实验结果表明，该算法能够有效地减少任务的总时延，同时最大限度地提高整体效用。

1 相关工作

随着无线通信、人工智能和云计算技术的飞速发展，许多学者认为智能社区汽车(the Intelligent Community Vehicle,ICV)是传统车辆的未来发展趋势。ICV配备了先进的车载传感器、控制器、执行器等设备，可以实现V2X[1]的智能信息共享。利用IoV中的通信技术将任务传输到具有丰富计算资源的其他基础结构是实现自动驾驶的一个关键步骤[2]。

下面从优化目标的角度将IoV的任务卸载问题大致分为四类。

⑴以降低时延为目标的任务卸载。在[3]中提出了一种综合优化算法的资源分配模型，该模型考虑边缘服务器的计算能力在不同时间段发生变化，实现车辆总任务卸载时延最小。在[4]中主要考虑车辆之间的任务卸载，提出了基于在线学习的分布式计算卸载算法，以达到对平均卸载时延的最小化。在[5]中根据最优节点选取理论设计了一种任务卸载方案，实现了任务卸载全过程中耗时更少。在[6]中提出了一种启发式搜索算法，通过优化候选对象选择、转移排序和任务分配来解决任务卸载问题，权衡了时延和可靠性。

⑵以降低能耗为目标的卸载决策。在[7]中提出了一种车载终端设备的节能VEC框架，并开发了基于ADMM的节能资源配置算法。在[8]中将卸载问题表述为NP难问题，提出了一种启发式算法来逐步解决卸载问题，设计了一种预测性组合传动模式，并为计算设施建立深度学习模型，以达到车辆能耗最小化。在[9]中提出了一种基于共识ADMM的分布式任务卸载方案，将具有耦合变量的原始问题转换为可分离目标的等效一般共识问题，从而降低终端车辆的能耗。

⑶以权衡能耗和时延为目标的卸载决策。在[10]中，提出了基于半马尔可夫决策的集中式任务分配算法，在综合考虑任务时延和移动设备能耗的前提下，使系统平均成本最小化。在[11]中提出了一种混合NOMA的第三种策略，通过应用几何规划(GP)获得了最优时间和功率分配的闭式表达式。在[12]中提出了一种具有混合能源供应的F-RAN的时延感知能效计算卸载方案，利用绿色电源来支持从移动用户的计算卸载，在延迟和网络约束下以最大程度地减少不可再生电网的能耗。

⑷以权衡时延和成本为目标的卸载决策。在[13]和[14]中，提出了两种基于云的车辆边缘计算卸载框架，分别采用运筹学理论和Stackelberg博弈论方法，使MEC服务器和车辆的效益最大化。在[15]中提出了一种基于凸凹过程的合同优化算法以激励服务车辆提供服务，设计了基于定价的任务卸载机制，在信息不对称的情况下实现服务提供商的期望效用最大化。在[16]中引入附近备份服务器来补充资源，提出Stackelberg博弈的卸载方案以实现改善服务提供商效用的目标。在[17]中，考虑计算任务的时间消耗和车辆的移动性，提出一种预测组合模式的卸载方案，减少计算卸载的停留时延和传输成本。

然而，较少有论文考虑到车辆的移动性。事实上，信道传输的数据速率和有效的通信时间都受到数据传输距离的影响。在本文中，针对VEC系统的优点，提出任务卸载方案，旨在最小化任务完成的平均卸载时延，而主要考虑任务完成的时延和车辆的移动性。

2 系统模型

2.1 VEC模型

服务车SV(Service Vehicle)：SV是拥有空闲计算资源的车辆，可以帮助请求车执行任务。请求车表示为SV={p,εsr,fs,vs,Ps}，其中p表示SV提供的任务卸载成本，εsr表示通信成本，fs表示SV的计算强度，vs和Ps分别表示SV的速度和瞬时位置。

请求车RV(Request Vehicle)：RV是需要卸载任务的车辆，表示为RV={λ,Dt,fr,vr,Pr}，其中λ表示卸载百分比，Dt表示任务数据的大小，fr表示RV的计算强度，vr表示RV的速度，Pr表示RV的瞬时位置。

如图1所示，我们设想了一个VEC网络场景，蜂窝网络的基站均部署在路边，通过电线连接到互联网上的服务器。所有车辆都配备有两个无线接口：蜂窝网络接口和IEEE802.11p网络接口。因此，车辆可以使用4G协议连接到蜂窝网络，也可以使用IEEE 802.11p协议互相通信。SDN控制器用于管理任务的卸载，也可以与蜂窝网络、车辆和内容服务器通信。SDN控制器充当车辆和内容服务器之间的中介。

如果RV想卸载内容，需要通过蜂窝网络向SDN控制器发送请求。然后，SDN控制器发回一组SV和关于请求内容的信息。与RV行驶方向相同的临近车辆若具有所请求任务的副本，则这些车辆是SV。同时，SDN控制器向所有SV发送一条消息，请他们参加博弈。接下来，SV将自己的信息发送给RV。最后，RV根据最低价格选择最终的SV进行任务卸载。如果所有SV提供的卸载价格过高，客户将直接在本地执行。在考虑的时间段内，车辆的身份是稳定的。提出的基本假设如下:

1)在卸载过程中每辆车的速度和方向保持不变。

2)在通信范围内每个RV只能将任务卸载给一个SV，每个SV可以向多个RV提供服务。

3)仅考虑V2V的任务卸载，如果RV仅有一个通信链接，RV的任务只能被卸载到它的一跳邻居。

2.2 系统模型

(1)

每一对RV和SV只有在通信范围R内才有机会进行通信，即RV和SV之间的距离(需要满足不等式)||PRVi(t)-PSVj(t)||R。假设RVi在t0=0时刻有一个计算密集型任务，第Δt时刻的RVi与SVj之间的欧式距离为

(2)

有几项工作表明停留时延服从伽马分布[18]。通常来说,伽马分布的概率密度函数Ga(△t,dij(△t),θ)和伽马函数Γ(dij(△t))分别表示为

(3)

(4)

其中，θ是比例参数，其值是由道路段的实际情况决定的[19]。SVj的停留时延为

(5)

2.2.2 计算模型 任务完成的时间包括三个过程所消耗的时间:1)任务内容的交付;2)任务执行;3)任务结果反馈。考虑计算密集型任务，如果RVi决定任务在本地执行的时间为

(6)

(7)

由于RV和SV都是移动的车辆，卸载任务的总计算时间应该小于RV和SV之间的相互接触时间,即

(8)

2.2.3 信任模型 在具有多个SV的系统中，一些SV很受欢迎，RV想要卸载任务给它们，而其他不受欢迎的SV，可能少数RV对它们感兴趣。我们根据历史信任值和现有观察值对SV未来行为进行预测，由RV确定是否将任务卸载给SV。根据RV对SV的信任分布来建模SV的受欢迎程度。而信任值是两个相邻车辆直接交互过程中对SV行为的评价值。根据文献[20]可知信任关系为

(9)

2.3 Stackelberg模型

2.3.1 效用函数 RV的效用函数是通过卸载节省的时间与获取数据成本之间的差值。RV的效用函数定义为

(10)

其中，α1+α2=1,0≤α1≤1和0≤α2≤1，α1和α2是权重。

SV的策略是通过定价来最大化收益。SV的效用函数包含三部分内容：1)辅助RV执行任务获得的利润；2)因信任度的提升而获得的利润；3)由于任务传输而消耗的通信成本。因此，SV的效用函数可以定义为

(11)

其中，β1+β2=1,0≤β1≤1和0≤β2≤1，β1和β2是权重。

3 基于Stackelberg博弈的任务卸载策略

3.1 问题描述

将RV的任务请求和SV的价格建模为非合作的Stackelberg博弈，SV是领导者，RV是跟随者。Stackelberg博弈包括两个阶段：在第一阶段，每个候选SV都提供成本p；在第二阶段，RV根据价格p确定从每个SV获取任务的卸载比例λ。 最后，RV选择提供最低价格p的SV进行任务卸载。在博弈中，每一方都是追求最大效用。因此，任务卸载问题可以表述为：

(12)

s.t.εsrppmax

(13)

其中，pmax表示SV提供的最大价格。

3.2 纳什均衡解

(14)

(15)

(16)

ur(λ)对λ求一阶导和二阶导得到

(17)

(18)

(19)

综上所述，RV的最优策略λ*的表达式为

(20)

(21)

(22)

3.3 算法的设计与实现

设计了一种基于Stackelberg(Stackelberg Game Based Task Offloading Algorithm)博弈的任务卸载算法，用于从SV候选集合中选择价格最低的SV执行任务卸载。RV向SV发出请求后，查询是否有车辆提供任务卸载服务。如果有，则执行SGTO算法。

SGTO算法的时间复杂度为O(n)。因此，在移动车辆上实现SGTO算法是可行的。此外，要运行算法SGTO，RV必须有SV实时输入所需数据项的信息。有关SV所需数据项的信息可以从APP程序和SDN控制器获得，SDN控制器将有关数据项的信息返回给RV。然后，每个SV将自己的信息发送给RV。

4 仿真实验分析

4.1 仿真参数设置

图2 含有交通信号灯的城市道路仿真场景Fig.2 Urban road simulation scene with traftic lights

采用SUMO来评估基于真实道路的SGTO算法。从OpenStreetMap中提取真实场景的特征信息，并使用JOSM对数字地图进行处理。然后将这些数字地图数据导入SUMO进行处理，其中根据特定的道路拓扑生成车辆流量。通过对SUMO界面的预先定义，可以在仿真过程中获得车辆的速度和相应的时间等关键参数。这里考虑的场景是一个有交通信号灯的城市道路，只考虑交通信号灯对车辆行驶速度的影响。我们以安徽省芜湖市的花津南路(大工山路-文昌西路)作为依据。其仿真场景为图2所示。

为了获得模拟结果，通过Matlab 2016b进行了1000次蒙特卡罗模拟。其参数设置为表1。

将该算法与文献中最近提出的两种方法[21-22]进行比较:

基于梯度迭代(GBI)[21]:该算法用于获得三方Stackelberg博弈均衡，其中三方为停放车辆、RSU和移动车辆。

先到先得(FCFS)[22]:一个用户访问服务车，车辆选择第一个进行卸载。

5.2 仿真结果分析

图3描述的是在不同通信成本εsr的条件下，不同效用函数和计算强度fr的关系。从图3(a)可以看出，在同一通信成本εsr条件下，随着计算强度fr的增加，效用函数ur逐渐减少；这是因为fr的值较小时，RV处理任务需要的时间较长；随着fr的值逐渐增加，RV处理任务的时间逐渐缩短。同时，在同一计算强度fr的条件下，随着通信成本εsr的增加，RV的效用函数ur减少。从图3(b)可以看出，在同一通信成本εsr条件下，随着计算强度fr的增加，效用函数us逐渐减少；这是因计算强度fr增加时，任务卸载给SV的数据量减少，从而造成了SV的效用函数us的减少；而在同一计算强度下，随着通信成本εsr的增加，效用函数us逐渐减少。

表1 实验参数

图4描述的是不同算法的效用函数与计算强度fr的关系。从图4(a)可以看出，对于FCFS算法，效用函数ur的值总是为零，这意味着FCFS不能优化RV的效用；而且当计算强度fr达到一定的值时，GBI算法的效用函数ur的值也为零，这说明GBI算法优化RV效用的效果受计算强度fr的值影响；同时SGTO算法的效用函数ur的值也随着计算强度fr的增大而减小。由图4(b)可以看出，在同一计算强度fr下，SGTO算法和GBI算法的效用函数us的值总是小于FCFS算法，这是因为FCFS算法的任务处理时间比较短，不考虑RV的效用函数；而且当计算强度fr达到一定的值时，GBI算法的效用函数us的值为零；结合图4(a)可知，FCFS算法不能同时优化两个效用函数；而且GBI算法优化两个效用函数的效果没有SGTO算法好，GBI算法受计算强度fr的值影响较大。

图5描述的是不同计算强度fr的效用函数和通信成本εsr的关系。由图5(a)可知，在同一通信成本εsr的条件下，计算强度fr越大，效用函数ur的值反而越小，且在同一计算强度fr的条件下，随着通信成本εsr的增加，效用函数ur逐渐降低。这是因为通信成本的增加，使得需要支付的通信成本更大。从图5(b)可以看出，在同一计算强度fr的条件下，随着通信成本εsr的增加，SV效用函数us逐渐减少。且在同一通信成本εsr的条件下，随着计算强度fr的增加，效用函数us也会减少。

图6描述的是不同算法的效用函数与通信成本εsr的关系。从图6(a)可以看出，对于FCFS算法，不管通信成本εsr的值为多少，效用函数ur的值总是趋近于零；而当通信成本us达到一定的值时，GBI算法的效用函数ur的值也为零；同时SGTO算法的效用函数ur的值也随着通信成本εsr的增大而减小；但是在同一通信成本εsr条件下，SGTO算法的效用函数ur的值总是大于FCFS算法和GBI算法的值。由图6(b)可以看出，SGTO算法和GBI算法的效用函数随通信成本εsr的变化幅度不大，而FCFS算法的效用函数us虽然值较大，但RV的参与度不高，会使得SV的收益不佳。

图7描述的是不同通信成本εsr的卸载价格p和计算强度fr的关系。从图7(a)可以看出，在同一通信成本εsr下，随着计算强度fr的增加，任务卸载的价格p逐渐降低。这是因为随着计算强度fr的增加，RV出于经济考虑会降低任务卸载率，进一步影响到任务卸载的购买性能的降低。因此，SV会做出降低价格的措施应对这一变化。从图7(b)可以看出，在同一通信成本εsr下，随着计算强度fr的增加，任务卸载节省的时间逐渐减少。这是因为任务在RV上执行的时间随着计算强度fr的增加而减少。

图8描述的是不同算法的卸载价格p和计算强度fr的关系。从图8(a)可以看出，算法SGTO相对于GBI和FCFS算法，任务卸载的成本是最低的。在仿真中，任务卸载的成本SV选择最大值pmax。从图8(b)可以看出，SGTO算法比GBI算法节省的时间更多。这是因为SGTO算法可以产生比GBI更好的优化结果。

(a)效用函数ur与计算强度fr的关系 (b)效用函数us与计算强度fr的关系图3 不同通信成本εsr的效用函数和计算强度fr的关系Fig.3 The relationship between the caculated strength of εsr and fr

(a) 效用函数ur与计算强度fr的关系 (b)效用函数us与计算强度fr的关系图4 不同算法的效用函数与计算强度fr的关系Fig.4 The relationship between utility function and fr

(a)效用函数ur与通信成本εsr的关系 (b)效用函数us与通信成本εsr的关系图5 不同计算强度fr的效用函数和通信成本εsr的关系Fig.5 The relationship between fr and εsr

(a)效用函数ur与通信成本εsr的关系 (b)效用函数us与通信成本εsr的关系图6 不同算法的效用函数和通信成本εsr的关系Fig.6 The relationship utility function and εsr

(a)任务卸载价格与计算强度fr的关系 (b)任务卸载时延与计算强度fr的关系图7 不同通信成本εsr的卸载价格和计算强度fr的关系Fig.7 The relationship between εsr and fr

(a)任务卸载价格与计算强度fr的关系 (b)任务卸载时延与计算强度fr的关系图8 不同算法的卸载价格和计算强度fr的关系Fig.8 The relationship between offload price and fr

5 总结

本文提出了一种基于Stackelberg博弈的任务卸载方案。该方案考虑了车辆的移动性和计算成本，建立了RV和SV之间效用最大化的交互模型；并在Stackelberg纳什均衡解的基础上，提出了一种SV收益与RV成本均衡的任务卸载模型，以实现边缘计算环境中IoV的任务卸载。实验结果与已有研究提出的GBI算法和FCFS算法相比较，在不同计算强度和通信成本的条件下，SGTO优化效用函数的效果总是优于FCFS、GBI算法，该方案不仅满足了RV和SV的需求，也有效地降低了任务卸载时延。但是由于实验参数设置不具有普遍性和代表性，日后研究中需考虑不同道路状况和突发事件下，SGTO算法结果受车辆移动性实时改变的影响。