文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2020, Vol. 32 Issue (3): 336-344  DOI: 10.3979/j.issn.1673-825X.2020.03.002
0

引用本文 

梁裕丞, 曹傧. VANET云环境下基于人工神经网络的车辆任务卸载策略[J]. 重庆邮电大学学报(自然科学版), 2020, 32(3): 336-344.   DOI: 10.3979/j.issn.1673-825X.2020.03.002.
LIANG Yucheng, CAO Bin. Artificial neural network methods for task offloading in VANET cloud[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2020, 32(3): 336-344.   DOI: 10.3979/j.issn.1673-825X.2020.03.002.

作者简介

梁裕丞(1993-), 男, 河南洛阳人, 硕士研究生, 主要研究方向为移动通信理论与技术。E-mail:15708431962@163.com; 曹傧(1983-), 男, 重庆人, 副教授, 博士, 主要研究方向为网络虚拟化、软件定义网络、资源管理和网络协议设计及性能分析。E-mail:caobin65@163.com

通讯作者

曹傧  caobin65@163.com.

文章历史

收稿日期: 2018-12-20
修订日期: 2020-05-30
VANET云环境下基于人工神经网络的车辆任务卸载策略
梁裕丞1, 曹傧2     
1. 重庆邮电大学 移动通信技术重庆市重点实验室, 重庆 400065;
2. 北京邮电大学 网络与交换技术国家重点实验室, 北京 100876
摘要: 在VANET(vehicular ad-hoc network)云环境中, 由于车辆自身资源受限等原因需要将部分计算密集型任务卸载至周围车辆协同处理。而车辆移动的随机性是影响车辆任务卸载性能好坏的重要因素之一, 对此, 提出了一种车辆间的卸载任务分配策略。考虑到车辆之间连接时间的随机性, 提出一种基于人工神经网络的连接时间预测方法, 该方法能够通过对历史数据的学习, 较为准确地对未来车辆行驶轨迹进行预测。此外, 车辆将空闲资源进行共享意味着自身能耗增加, 由于车辆本身的自私性使得车辆不会无偿为周围车辆提供服务。为了激励车辆之间进行协作, 制定了一种分布式买卖博弈方法达到车辆资源需求与收益之间的平衡, 还设计了一种集中式任务分配策略以获得任务卸载的最大效用。仿真显示, 提出的方法在最大化卸载效用与提高任务卸载成功率方面都有较好的性能。
关键词: VANET云    任务卸载    神经网络    买卖博弈    
Artificial neural network methods for task offloading in VANET cloud
LIANG Yucheng1 , CAO Bin2     
1. Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China;
2. State Key Laboratory of Network and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China
Abstract: In the VANET cloud, some computationally intensive tasks need to be offloaded to the surrounding vehicles for coordinated processing due to the limited resources of the vehicle itself. The randomness of vehicle movement is one of the important factors affecting the offloading performance. For this reason, we propose an offloading task allocation strategy between vehicles. Considering the randomness of connection time between vehicles, we adopt a connection time prediction method based on artificial neural network. This method can accurately predict the future vehicle trajectory by learning historical data. In addition, sharing idle resources to other vehicles means increasing energy consumption. Due to the selfishness of the vehicles, they will not provide services for surrounding vehicles without compensation. In order to encourage the cooperation of available vehicles, we have developed a distributed Buyer/Seller game method to achieve a balance between resource demand and payment. Finally, we design a centralized task allocation strategy to get the maximum utility of task offloading. The simulation results show that the proposed method is feasible in maximizing the offloading utility and improving the success rate of task offloading.
Keywords: VANET cloud    task offloading    neural network    buyer/seller game    
0 引言

随着智能交通系统(intelligent traffic system, ITS)的发展[1],车载应用对于车辆资源的需求越来越高,但是大部分车辆由于自身资源有限(计算资源、存储资源等),其处理能力无法完全满足用户日益增长需求。为提高车辆处理效率、降低能耗,车辆云计算[2]开始被广泛采用。通过该技术,车辆可以将复杂的计算密集型任务卸载到远程云中心或本地边缘云设备[3]进行处理,从而减少本地处理任务开销,缓解车辆资源紧张的问题。车辆云环境下的任务卸载过程主要分为3个步骤:车辆端到云端的任务分发、云端的任务处理及云端到车辆的结果回传。

由于车辆云计算复杂而广泛的应用场景,以及越来越多的车辆将参与到云计算资源共享中,这将给车辆云计算带来许多新的挑战。例如,在许多道路无线环境中,由于没有部署功能强大的边缘云设备,使得车辆资源受限;此外,远程云中心因距离车辆过远造成传输时延高、开销大等问题。对此,我们需要寻求一种新的车辆云计算架构,以满足现有车辆为完成任务卸载对共享资源的需求。

随着车辆技术不断发展,预计未来部分车辆将拥有更加丰富的车载资源,如强大的计算、存储能力,更加丰富的传感器节点等[4],这类车辆亦将成为一类强大的云服务器。资源需求车辆在资源受限的情况下,可以通过任务分割、卸载,共享临近车辆的空闲资源协同处理任务,以VANET(vehicular ad-hoc network)形式实现车辆云计算,提高车辆对于计算密集型任务的处理能力。对此有学者提出了VANET云[5]这一概念,即车辆之间通过互相合作来分享资源、协同处理任务。与此同时,业界也针对类似应用场景,提出了雾计算[6]等相关概念,受到了广泛认可。

VANET云其独特之处在于云服务器可以是具有丰富资源或者较好互联网接入能力的车辆,资源受限车辆希望租用这些车辆的空闲资源。为实现这一目标,需求车辆需要寻找这些资源空闲车辆,了解其资源状态,并与他们进行通信和资源请求。但是,由于车辆的高移动性,会导致卸载过程中丢失与目标车辆的通信,造成任务卸载失败。此外,共享自身计算资源意味着能耗增加,需要考虑如何激励车辆共享自身计算资源,在最大化自身收益的同时又能满足需求车辆的资源需求。针对以上问题,我们采用广泛应用于道路云环境中的VANET云与软件定义网络(software defined network, SDN)相结合的方法[7-9],在路侧单元(road side unit, RSU)部署SDN控制器,通过将车辆通信的控制面与数据面分离,实现网络的灵活控制,使网络作为管道变得更加智能。为了实现车辆与RSU以及车辆间进行通信,每个车辆的车载单元(on board unit, OBU)同时配备有蜂窝网络接口和IEEE 802.11p[10]网络接口,车辆通过蜂窝网络向SDN控制器持续发送自身相关信息(包括车辆的位置、速度及通过信标帧收到的周围车辆的ID等),其系统架构如图 1

图 1 VANET云与SDN结合的智能交通系统架构 Fig.1 System architecture of intelligent traffic system based on VANET cloud and SDN

图 1中,每个RSU是与SDN控制器相关联的宏小区。相邻的SDN控制器之间可以交换数据库的存储内容,以便共享不同路段路况信息。

1 相关工作

车辆云计算可以通过车辆交互及采集道路交通信息,这是自动驾驶技术不可或缺的一部分。利用云技术,车辆可实现规避交通事故、下载最新版地图以及获取交通道路信息等功能。此外,智能车辆还能够自动规划最佳的行驶路径,将用户更加安全快捷地运送到目的地。车企还可以利用车辆云计算技术来驱动产品创新,覆盖车辆的研发进程甚至车辆的整个使用寿命。对于车辆本身来说,车辆可以向云服务器租用所需的资源来运行它们的应用程序,而不用购买和安装额外的软/硬件[11]。在VANET中,由于车辆远离或无法接入远程云中心,文献[4]提出了在移动云计算环境中使用智能车辆作为云服务器的想法,假设这些车辆具有网络接入并且具有车载计算、存储和感测能力,车辆所有者可以按要求或按周期出租车辆的这些资源。此外,诸如出租车和公共汽车等公共交通工具也可以通过将其车辆计算资源出租获得收益。文献[12]通过为车辆云提供可能的架构设计和资源分配以及负载平衡解决方案对文献[4]中的工作进行了拓展。但是在文献[4]及文献[12]中,作者仅考虑了车辆静止时(如在行车场中或交通拥堵时)被用为云服务器的情况,对于动态环境中的车辆资源配置还缺乏足够的理论依据。为实现动态无线频谱资源和云虚拟机资源的最优配置,文献[13]提出了一种移动云环境下的联合资源预留与分配算法,通过捕获移动用户的满意度,对移动应用的资源需求进行匹配。此外,考虑到车辆的随机移动性,文献[7]使用LT-NSR(life time-based network state routing)算法从车辆周期性上传信息中实时导出和建立当前道路的网络拓扑和V2V(vehicle to vehicle)通信路径,将蜂窝网络中的车辆通信业务卸载到V2V路径中。文献[14]采用多阶段随机规划,设计了一种分布式业务分发机制,建立了一种阶段任务卸载最优模型,以获取最优决策用于任务分发控制,来解决动态情况下的节点选择与资源分配问题;类似的,文献[15]提出了一种动态机会卸载算法,利用马尔科夫决策模型得到最优的卸载决策。文献[16]提出了一种基于拍卖的任务迁移算法,该算法可以保证拍卖者公布的价格,个体理性,盈利能力和计算效率的真实性。

基于以上,本文在考虑VANET云场景中,为解决车辆之间相对运动导致车辆连接时间不确定带来的任务卸载失败,以及激励资源空余车辆参与任务卸载,提出了一种人工神经网络与买卖博弈相结合的任务卸载方案。

2 系统模型

不失一般性,假设在一段道路环境下有M个卸载需求的车辆(称为源车辆),定义第s个源车辆为vs;在源车辆周围存在N个具有空闲资源的车辆(称为目标车辆),定义第d个目标车辆为vd

2.1 源车辆卸载效用

考虑系统中所有需求车辆,将源车辆vs的卸载效用定义为

$ {U_s} = {u_s} - {C_s} $ (1)

(1) 式中,Us主要包括卸载收益us和卸载开销Cs。令车辆vs需要卸载的总任务量为Wsus表示需求车辆vs将任务Ws卸载至周围所有可用车辆vd可以获得的总卸载收益。

$ {W_s} = \sum\limits_{d = 1}^N {{W_{sd}}} $ (2)

(2) 式中,Wsd表示直接通过V2V链路卸载至周围车辆vd的任务量。当s=d时表示这部分任务在本地处理。

任务卸载的效用收益采用在移动云计算和无线网络通信中普遍使用的对数函数表示[17]

$ {u_s} = \theta \sum\limits_{d = 1}^N {{P_{sd}}} {\rm{lg}}(1 + {W_{sd}}) $ (3)

(3) 式中:θ为任务卸载收益权重参数,且其值大于零;Psdvs对应的vd可提供的最大处理速率。

Cs表示车辆vs将任务Ws完全卸载需要的开销,其主要由传输开销Cs, t和本地计算开销Cs, p组成,即Cs=Cs, t+Cs, p。为了简化问题,将V2V链路的传输带宽设定为固定值Bsd。将传输开销定义为[18]

$ {C_{s, t}} = \gamma \sum\limits_{d = 1}^N {{W_{sd}}} $ (4)

(4) 式中,γ为通过V2V链路传输1 Mbit需要的单位传输开销。

本地计算开销Cs, p= $\beta \frac{{{W_{ss}}}}{{{P_{ss}}}}$。其中,β为本地计算单位时间的计算开销。

2.2 优化模型

本文关注VANET云环境中车辆任务卸载问题,以最大化源车辆vs卸载效用为优化目标,定义优化模型为

$ {{\rm{max}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {U_s}} $ (5)
$ {{\rm{ s}}{\rm{.t}}{\rm{. }}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{s = 1}^M {{P_{sd}}} \le {P_d}, \forall d} $ (6)
$ {\sum\limits_{d = 1}^N {{W_{sd}}} \le {W_s}, \forall s} $ (7)
$ {\frac{{2{W_{sd}}}}{{{B_{sd}}}} + \frac{{{W_{sd}}}}{{{P_{sd}}}} \le T_{sd}^{{\rm{ pre }}}, \forall s, d} $ (8)
$ {{P_{sd}} \ge 0, \forall s, d} $ (9)
$ {{W_{sd}} \ge 0, \forall s, d} $ (10)

(6) 式表示源车辆vs向一辆目标车辆vd购买的计算速率之和不大于其剩余计算速率;(7)式表示需求车辆vs卸载的总任务量不大于其需求卸载任务量;(8)式表示通过V2V链路进行任务卸载的理论计算时间不大于V2V链路的预测连接时间。

3 车辆移动性预测 3.1 Nagel-Shreckenberg车辆交通模型

为了模拟VANET云环境,我们基于Nagel-Shreckenberg模型[19]对一段道路上的车辆运行情况进行仿真。在本文的模型中,模拟450 m长单向双车道公路场景,并考虑因车辆之间相对位置关系导致车辆变道行驶的情况。并将道路环境抽象为长150个元胞,宽2个元胞,共计300个元胞的二维阵列。定义每个元胞长3 m。每个元胞中最多可以被一辆车占用。车辆具有整数速度(即,在单位时间步长中行驶的元胞数量),其值为1~vmax。对于任意配置,系统的一次更新包括以下5个连续步骤,这些步骤对所有车辆并行执行。

1) 加速。如果车辆的速度v低于vmax并且观察到距离前方的下一辆车距离大于v+1,则车速由v变为v+1。

2) 减速。如果车辆行驶在位置i处观察到前方下一辆车位于位置i+j(jv),则将其速度v降低到j-1。

3) 随机减速。当车速不为0时,以概率p速度由v降低到v-1。

4) 汽车移动。每辆车单位时间向前移动v个元胞。

5) 车辆变道。如果车辆观察到与前方车辆距离大于v+1,此时车辆存在一定的概率进行变道行驶,其中,向左的概率为0.8,向右的概率为0.5。当车辆距离前方车辆距离小于安全距离时,车辆会观察左右平行方向是否存在行驶车辆,如果没有则优先向左侧进行变道,反之向右变道。当车辆与前方车辆距离小于安全距离且左右平行车道都被其他车辆占用,则进行减速运行。

每次模拟,系统重复这些规则。在本文的模型中,总模拟时间600 s,单位时间步长为0.5 s,车辆最大速度(vmax)为5个元胞单位时间步长,相当于108 km/h,减速概率(p)为0.1,交通密度为(ρ)为0.1车辆/单元。

3.2 基于神经网络的连接时间预测

在第2.2节定义的优化模型中,需要对比预测源车辆与目的车辆的最大连接时间和实际连接时间的误差来反映预测结果的准确性。人工神经网络(artificial neural network,ANN)是车辆连接时间预测中最常用的算法之一[20-22]。本文中,使用由NN(neural network)辅助的最大连接时间预测方法来获得车辆间最大连接时间。使用反向传播(back propagation,BP)算法测量权重,通过最小化误差和预测观察结果来观察道路特征。本文的神经网络模型由3个主要层构成:①输入层,由2种输入组成(源车辆、目标车辆与附近车辆当前坐标、速度,且每种输入的总数量与该路段当前车流密度有关); ②隐藏层,包含2层,每层有50个神经元; ③输出层,用于输出预测连接时间。通过调整ANN的参数(例如时期数、学习率、隐藏层数和每层中的神经元数等),可以实现较好的数据拟合性能。训练数据集采用第3.1节中讨论的Nagel-Shreckenberg模型中车辆连接时间的4 000个样本。其中80%用于训练,20%用于评估模型的性能以及它与真实数据的匹配程度。数据集简要说明如下。

1) 真实连接时间。车辆vsvd在Nagel-Shreckenberg模型中的实际连接时间(预测模型的目标输出)。

2) 车辆位置。车辆vsvd的坐标;该路段中vsvd所在RSU关联的其他车辆坐标。

3) 车辆速度。通过观察实时获取的该路段与车辆vsvd所在RSU关联的所有车辆速度。

在如图 1的场景下,所有车辆定期通过蜂窝网络向SDN控制器发送自身的信息(包括使用GPS(global positioning system)获得的车辆定位、车辆当前行驶速度、车辆当前行驶方向、周围车辆信息等),SDN控制器利用这些信息作为数据集对ANN进行训练。当训练完成后SDN控制器在收到车辆的相关信息后,将其输入训练好的ANN中,就可以得到车辆vsvd之间的连接时长TsdpreTsdpre≥0。

3.3 算法时间复杂度分析

参考上述道路场景,输入层、隐藏层、输出层每层神经元数量分别用n1n2n3表示。当使用一个样本进行前馈计算,需要进行2次矩阵运算,2次矩阵乘法分别要进行n1×n2n2×n3次计算,由于输入层和最终输出层结点数量(n1n3)是确定的,所以,可以视为常量。中间的隐藏层包含2层,且神经元数量为n2。因此,对于隐藏层需要进行n2×n2次矩阵运算,所以,对一个样本的前馈计算时间复杂度为O(n1×n2+n2×n2+n2×n3)=O(n2)。

4 基于买卖博弈的资源分配策略 4.1 有效卸载速率

在任务卸载过程中,存在向目标车辆卸载与源车辆本地处理2种情况。对于目标车辆卸载过程主要包括任务提交、目标车辆处理、任务处理结果返回3个环节。利用卸载任务量Wsd可计算出从vsvd的总持续时间为

$ T_{sd}^{{\rm{ct}}} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{W_{sd}}}}{{{B_{sd}}}} + \frac{{{W_{sd}}}}{{{P_{sd}}}} + \frac{{{W_{sd}}}}{{{B_{ds}}}}, }&{s \ne d, \forall s, \forall d}\\ {\frac{{{W_{ss}}}}{{{P_{ss}}}}, }&{s = d, \forall s, \forall d} \end{array}} \right. $ (11)

(11) 式中,Bsd为源车辆和目标车辆间的传输速率。为了简化问题,本文将传输速率Bsd设置为定值,而不同距离下的传输速率变化对任务卸载的影响,将作为我们未来工作的重点。当在本地处理时,Bsd可看做无穷大。因此, 任务的有效卸载速率为

$ {{R_{sd}} = \frac{{{B_{sd}}{P_{sd}}}}{{2{P_{sd}} + {B_{sd}}}}} $ (12)
$ {{\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{s = 1}^M {{P_{sd}}} \le {P_d}, \forall j} $ (13)

(13) 式中,Pd为卸载目标可以提供的的最大计算速率。由(12)式可知,有效卸载速率是关于Pij的凸函数[23]。上文提到目标车辆不会无偿共享自身计算资源。为解决这一问题,设计了一种基于买卖博弈的有偿资源分配算法,以激励目标车辆共享自身的空闲资源,参与任务卸载。该算法将需求车辆vs定义为买方,计算资源空余的目标车辆vd定义为卖方,通过建模分析,利用买卖博弈算法获得vd可以提供的最优计算速率与vs可以给出的最优单位计算速率价格。

4.2 买方分析

买方(源车辆)为提高最大有效卸载速率会向卖方(目标车辆)购买计算速率。定义买方的收益函数为

$ {{G_{{b_{sd}}}} = {\lambda _{sd}}{R_{sd}} - {\alpha _{sd}}{P_{sd}}} $ (14)
$ {{\rm{ s}}{\rm{.t}}{\rm{. }}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{s = 1}^M {{P_{sd}}} \le {P_d}, \forall d} $ (15)

(14) 式中:λsd为单位有效卸载速率的收益;αsd为单位计算速率的售价。通过计算可知卖方收益Gbsd是关于Psd的凸函数。因此,买方收益函数会随着购买的计算速率增加而增加,通过观察买方收益函数和计算速率之间的关系,可以获得计算速率的最优解。即当∂Gbsd/∂Psd=0时,可以得到最优计算速率分配值为

$ P_{sd}^* = \sqrt 2 {B_{sd}}{({\alpha _{sd}})^{ - 0.5}} - 2{B_{sd}} $ (16)
4.3 卖方分析

当卖方收到来自买方资源需求时,卖方会计算单位资源的价格,并将其发给买方。定义卖方的收益函数为

$ {{G_{{s_{sd}}}} = ({\alpha _{sd}} - {c_{sd}}){P_{sd}}} $ (17)
$ {{\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{s = 1}^M {{P_{sd}}} \le {P_d}, \forall d} $ (18)

(17) 式中,csd为卖方单位处理速率的成本价格,由于卸载目标自身属性(包括车辆型号、计算能力、是否愿意参与卸载等)不同,不同卖方初始出价csd也不相同。

同理,由于卖方收益Gssd是关于αsd的凸函数,卖方收益会随着单位计算速率售价的增加而增加。通过观察卖方收益函数与单位计算速率售价之间的关系,获得单位计算速率售价的最优解。

$ \frac{{\partial {G_{{s_{sd}}}}}}{{\partial {\alpha _{sd}}}} = P_{sd}^* + ({\alpha _{sd}} - {c_{sd}})\frac{{\partial P_{sd}^*}}{{\partial {\alpha _{sd}}}} $ (19)

类似于买方计算方法求解最优解的方法,当∂Gssd/∂αsd=0时,可以得到最优单位计算速率价格αsd*

4.4 价格更新函数

卖方为了最大化其收益函数,会基于系统环境逐渐增加计算速率的卖价αsd*,直到其收益函数不再增加,此时计算速率在约束条件下达到最优,卖方收益也达到最大。在这个过程中需要设计一个价格更新函数,允许卖家不断更新其计算速率的售价来最大化自身的收益函数。为了保证卖家的收益大于零,卖家将价格从合理的较低值csd(单位计算速率的成本价格)逐步提高来增加自身收益。这意味着,在价格更新的过程中∂Gssd/∂αsd逐步由正变为零。参考文献[24]中的方法设计如下卖方计算速率价格的更新函数,且在每一轮价格更新直到收敛之前,有(20)式成立。

$ \frac{{\partial {G_{{s_{sd}}}}}}{{\partial {\alpha _{sd}}}} = P_{sd}^* + ({\alpha _{sd}} - {c_{sd}})\frac{{\partial P_{sd}^*}}{{\partial {\alpha _{sd}}}} \ge 0 $ (20)

根据(20)式可得

$ {\alpha _{sd}}(t + 1) \le I({\alpha _{sd}}(t)) $ (21)

(21) 式中:t为迭代次数;I(αsd(t))为价格更新函数,期表达式为

$ I({\alpha _{sd}}(t)) = {c_{sd}} - \frac{{P_{sd}^*}}{{\frac{{\partial P_{sd}^*}}{{\partial {\alpha _{sd}}(t)}}}} $ (22)

为了更好地呈现利用买卖博弈模型进行价格更新和速率请求更新的整个过程,在算法1中,我们对该算法的整个过程进行了详细的阐述。假设卖方计算速率报价从成本单价csd开始,根据(16)式计算此时的Psd*,随后进行判断,若∂Gbsd/∂Psd>0,则使用(22)式更新价格,否则最优价格即为当前报价。最后进行判断,若∂Gssd/∂γsd>0,则根据(22)式更新需求计算速率,否则最优计算速率即为当前需求计算速率。

算法1:分布式资源分配算法。

输入:cλB

输出:P*α*

1) for每一个卖方d

2) 初始化迭代次数t=0;

3) 获得卖方初始报价α=c

4) 计算买方资源需求P

5) if $\frac{{\partial {G_s}}}{{\partial \alpha }} > 0$

6) 卖方根据(22)式更新价格

7) t=t+1

8) else if t>0

9) α*=α

10) else

11) α*=c;

12) end if

13) if $\frac{{\partial {G_b}}}{{\partial P}} > 0$

14) 买方根据(22)式更新速率需求

15) else if t>0

16) P*=P

17) else

18) P*=P(c)

19) end if

20) end for

5 集中式任务分配方法

在第3节中,我们利用神经网络对源车辆与目标车辆之间的V2V链路最大连接时间进行预测。随后,通过算法1,获得目标车辆的最优计算速率与单位价格。在本节中,将利用以上结果对源车辆需要卸载的任务进行分配。

当源车辆与目标车辆之间存在V2V链路时,根据第2节的结果,可以得到源车辆向目标车辆的最大卸载任务量为

$ {w_{sd}} < T_{sd}^{{\rm{ pre }}}{R_{sd}} $ (23)

在算法2中,对任务分配算法进行了详细的说明。

算法2:集中式任务分配算法。

输入:θ, γ, β, Ws

输出:Wss*, Ws1*, …, Wsd*, …, WMN*

1) 获取周围可用目标车辆集合{v1, v2, …, vN};

2) for每个目标车辆d

3) 使用算法1计算Psd*

4) 根据(12)式计算有效卸载速率Rsd

5) 使用神经网络预测链路sd连接时间Tsdpre

6) end for

7) 根据(5)式,s.t.(6)—(10)式计算

$ {\rm{max}}{U_i}, W_{ss}^*, W_{s1}^*, \cdots , W_{sd}^*, \cdots , W_{MN}^*; $

当任务分配完成后,通过观察实际卸载过程来弥补预测结果不准确:若Tsdpre < Tsdct,则将剩余任务通过蜂窝网络进行传输;若TsdpreTsdct,则表示任务完全通过V2V链路完成卸载。

6 仿真与性能分析

在本文所述的VANET云环境中,所有车辆均配备802.11p协议接口与蜂窝网络接口,且V2V链路传输的速率为定值Bsd=11 Mbit/s[13]。不同型号目标车辆计算速率成本价格csd随机产生并服从csd~N(0.1, 0.05)的高斯分布。计算资源分配过程中买方单位有效卸载速率收益θ=1。

6.1 连接时间预测

参照3.2节连接时间预测方法的相关细节,进行连接时间预测方法的仿真参数的设置。并引入文献[7]中的LT-NSR算法,通过对比,分析验证本文的神经网络预测方法的性能。

图 2描述了使用训练完成的ANN进行连接时间预测得到的预测误差直方图。

图 2 人工神经网络神经网络预测结果 Fig.2 Artificial neural network prediction results

图 3呈现了不同算法下车辆连接时间的平均预测误差的对比。文献[7]中所述LT-NSR算法将车辆运行轨迹视为匀速直线运动,通过源车辆与目标车辆的相对速度与相对位置,计算两车之间的连接时间。相比于另外2种算法,其优点为只需获取当前时刻源车辆与周围车辆的实时状态信息,就可以进行连接时间的预测。但是车辆在实际行驶中,会因为周围车辆行驶状态的改变而调整自身驾驶策略,大多数时候并不能严格遵循匀速直线运动,因此,LT-NSR算法的平均预测时间误差较大。相比于LT-NSR算法,文献[18]中的Naive算法,通过观察该路段历史行驶车辆的连接时间,计算连接时间的期望,并将其作为未来车辆之间连接时间的预测结果。但是它需要收集大量历史数据,且预测结果无法随不同车辆的行驶偏好而改变,因此预测误差也较大。而人工神经网络的预测结果明显优于LT-NSR算法和Naive的预测结果。这是由于其强大的自学习和自适应能力。神经网络在训练时,能够通过学习自动提取输出、输出数据间的“合理规则”,并自适应地将学习内容记忆于网络的权值中。由于神经网络具有较强的非线性映射能力,因此,使用神经网络对车辆连接时间的预测结果更为准确。由于需要大量的数据样本对神经经网络进行训练,这无疑又会增加算法的时间复杂度。

图 3 平均预测时间误差对比图 Fig.3 Average prediction time error comparison

图 4为3种预测算法的运行时间对比图,可以观察到由于其相对复杂的自学习机制,使得人工神经网络预测的运行时间随周围可卸载车辆数的增加呈指数增长。

图 4 算法时间复杂度对比 Fig.4 Algorithmic complexity comparison
6.2 最优计算速率

假设源车辆周围存在3辆可以进行任务卸载的目标车辆,令目标车辆单位计算速率成本价格分别为0.1,0.15,0.2。源车辆的初始需求计算速率设置为0.001 Mbit/s。

图 5图 6分别描述了目标车辆价格和处理速率的收敛情况。从图 5可知,在经过3次迭代之后,目标车辆的计算速率分别收敛于9.313,6.954,5.258 Mbit/s。从图 6可知,在经过4次迭代后,目标车辆的价格分别收敛于0.246,0.288,0.325。

图 5 目标车辆处理速率分配更新 Fig.5 Processing rate allocation update
图 6 目标车辆价格更新 Fig.6 Price update
6.3 任务分配结果

图 7描述了任务量与周围可卸载车辆变化对源车辆卸载效用的影响。

图 7 卸载效用对比图 Fig.7 offloading utility comparison

图 7a,当源车辆需要卸载的任务量较大时,如果周围可用目标车辆较少,就会造成源车辆无法卸载的任务增多,此时源车辆只能将大部分任务在本地进行处理,因此计算开销较大,卸载效用较低。但随着周围可用目标车辆数的增加,源车辆可以将更多的任务卸载到周围车辆,因此卸载效用持续增加。相比于高任务量,当任务量较低时,源车辆可以利用自身计算能力处理部分任务,这部分任务避免传输过程中的通信开销,此时卸载效用比大任务量情况下高。如图 7b,随着卸载任务量的增加,源车辆的卸载效用也逐渐提高,但是当卸载任务量超出周围车辆的最大任务处理能力时,源车辆只能将剩余任务在本地进行处理,造成任务处理开销增加,导致卸载效用下降。此外,随着周围可卸载车辆增加,源车辆可以将任务以更低的开销分配给更多的车辆进行处理,因此,相比于车辆较少的情况卸载效用更高,且大任务量情况下卸载开销对卸载效用影响较小。

图 8为采用集中式任务分配策略、贪婪任务分配策略(将所有任务全部迁移)、平均任务分配策略(将任务均分卸载)下的卸载效用随周围可卸载车辆和总卸载任务量变化条件的对比。从图 8中可以观察到,当源车辆周围没有车辆可供卸载的时候,源车辆只能将任务在本地进行处理,因此,3种策略的效用都较低。随着周围可卸载车辆数的增加,源车辆自身处理能力相对于整个系统来说占比逐渐变小,贪婪任务分配策略效用逐渐靠近集中式任务分配策略,而平均任务分配策略因为没有考虑车辆间实际连接时间与最大有效卸载速率,单纯将总任务均匀拆分后卸载至周围车辆,卸载相比于前2种策略较低。

图 8 不同任务量与卸载效用关系图对比图 Fig.8 Comparison of different task volumes and offloading utility

图 9中将同等仿真环境下人工神经网络,LT-NSR,Naive方法对应的累计卸载失败任务量进行了对比。可以观察到随着卸载任务次数的增加,人工神经网络与LT-NSR,Naïve相比,其累计任务失败量最低、增长最慢,证明了使用人工神经网络对车辆之间连接时间的预测结果更加准确。

图 9 卸载失败任务量对比图 Fig.9 Offloading failure task volume comparison
7 结束语

本文提出了一种VANET云环境下的基于神经网络和买卖博弈的任务卸载方法。该方法将SDN控制器部署在与RSU关联的宏小区中。为了最大化车辆有效卸载速率,同时激励有空闲资源的车辆参与到资源共享中,以更高效地完成任务卸载,设计了一种基于买卖博弈的资源分配算法,利用该算法可以获得车辆之间的最大计算速率,当收益合适,且车辆之间存在连接时,每个源车辆都可以选择合适的目标车辆进行任务卸载。部署在与RSU关联宏小区的SDN控制器持续收集通过该路段车辆发送的周期性属性信息,并使用这些信息对神经网络进行训练,随后利用训练完成的神经网络对车辆连接时间进行预测。通过博弈获得的最优计算速率与预测得到的车辆连接时间作为任务卸载优化问题的限制条件,设计一种集中式算法在获得目标车辆的最优卸载任务量的同时,最大化任务卸载效用。仿真结果也验证了本文所提出任务卸载策略的正确性和有效性。

参考文献
[1]
ZHU Y, ZHU X, ZHU S, et al. Intelligent Transportation System based on Internet of Things[C]//World Automation Congress(WAC). Mexico: IEEE, 2012.
[2]
SHARMA M K, KAUR A.A survey on Vehicular Cloud Com-puting and its security[C]//International Conference on Next Generation Computing Technologies.India: IEEE, 2016.
[3]
LIU Y, LEE M, ZHENG Y. Adaptive multi-resource allocation for cloudlet-based mobile cloud computing system[J]. IEEE Transactions on Mobile Computing, 2016, 15(10): 2398-2410. DOI:10.1109/TMC.2015.2504091
[4]
OLARIU S, KHALIL I, ABUELELA M. Taking VANET to the clouds[J]. International journal of powder metallurgy, 2011, 7(1): 7-21.
[5]
MERSHAD K, ARTAIL H. A Framework for implementing mobile cloud services in VANETs[C]//IEEE International Conference on Cloud Computing. USA: IEEE, 2013: 83-90.
[6]
PENG M, YAN S, ZHANG K, et al. Fog computing based radio access networks:issues and challenges[J]. IEEE Network, 2015, 30(4): 46-53.
[7]
HUANG C, CHIANG M, DAO D, et al. V2V data offloading for cellular network based on the Software Defined Network (SDN) Inside Mobile Edge Computing (MEC) Architecture[J]. IEEE Access, 2018, 6(99): 17741-17755.
[8]
BHATIA A. Realization of flexible and scalable VANETs through SDN and virtualization[C]//International Conference on Information Networking. IEEE Computer Society. Thailand: IEEE, 2018: 280-282
[9]
KADHIM A J, SENO S A H. Maximizing the utilization of Fog Computing in Internet of Vehicle using SDN[J]. IEEE Communications Letters, 2018, PP(99): 1-1.
[10]
HU Y, ZHANG W, LI Y, et al. The research of WAVE architecture based vehicles to vehicles communication technology of Intelligent Transport System[C]//International Conference on Power Electronics & Intelligent Transportation System. China: IEEE, 2010: 134-139.
[11]
ALAZAWI Z, ALTOWAIJRI S, MEHMOOD R, et al. Intelligent disaster management system based on cloud-enabled vehicular networks[C]//International Conference on ITS Telecommunications. Russia: IEEE, 2011: 361-368
[12]
OLARIU S, HRISTOV T, YAN G. The Next paradigm shift: from vehicular networks to vehicular clouds[M]//Mobile Ad Hoc Networking: Cutting Edge Directions. 2nd ed. USA: John Wiley & Sons, Inc, 2012: 645-700.
[13]
LI Y, LIU J, CAO B, et al. Joint Optimization of Radio and Virtual Machine Resources with Uncertain User Demands in Mobile Cloud Computing[J]. IEEE Transactions on Multimedia, 2018, 20(9): 2427-2438. DOI:10.1109/TMM.2018.2796246
[14]
TRUONG-HUU T, THAM C K, NIYATO D. A stochastic workload distribution approach for an Ad Hoc mobile cloud[C]//International Conference on Cloud Computing Technology and Science.Singapore: IEEE, 2015: 174-181.
[15]
TRUONG-HUU T, THAM C K, NIYATO D. To offload or to wait: An opportunistic offloading algorithm for parallel tasks in a mobile cloud[C]//International Conference on Cloud Computing Technology and Science. Singapore: IEEE, 2014: 182-189.
[16]
CAO B, XIA S, HAN J, et al. A Distributed Game Methodology for Crowdsensing in Uncertain Wireless Scenario[J]. IEEE Transactions on Mobile Computing, 2019, 1-1.
[17]
YANG D, XUE G, FANG X, et al. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing[C]//International Conference on Mobile Computing and Networking.Istanbul: IEEE, 2012: 173-184.
[18]
THAM C K, CAO B. Stochastic programming methods for workload assignment in an Ad Hoc mobile cloud[J]. IEEE Transactions on Mobile Computing, 2017, PP(99): 1-1.
[19]
NAGEL K, SCHRECKENBERG M. A cellular automaton model for freeway traffic[J]. Journal De Physique I, 1992, 2(12): 2221-2229. DOI:10.1051/jp2:1992262
[20]
CHEN M, LIU X, XIA J, et al. A Dynamic bus-Arrival time prediction model based on APC data[J]. Computer-Aided Civil and Infrastructure Engineering, 2010, 19(5): 364-376.
[21]
PARK T, LEE S. A Bayesian approach for estimating link travel time on urban arterial road network[J]. Lecture Notes in Computer Science, 2004(3043): 1017-1025.
[22]
LIN Y, YANG X, ZOU N, et al. Real-time bus arrival time prediction:case study for Jinan, China[J]. Journal of Transportation Engineering, 2013, 139(11): 1133-1140. DOI:10.1061/(ASCE)TE.1943-5436.0000589
[23]
BOYD S, VANDENBERGHE L. Convex optimization[M].UK: Cambridge University Press. 2004.
[24]
WANG B, HAN Z, LIU K J R. Distributed relay selection and power control for multiuser cooperative communication networks using Stackelberg game[J]. IEEE Transactions on Mobile Computing, 2009, 8(7): 975-990. DOI:10.1109/TMC.2008.153