基于车联云的资源动态部署方案

原 帅，吴学文，朱晓凯

(河海大学 计算机与信息学院，江苏 南京 211100)

0 引 言

车联云(vehicular cloud，VC)是一种集成了车载自组网络[1]和云计算的新型云组织技术，其中的关键性问题是如何整合利用车载资源。现有的车联网仅以云服务提供商作为资源的提供者，然而车联云模式将用户本身作为资源的提供者，利用车中已有的软硬件资源，车联云VC集成了计算、传感、通信和存储资源，提供相应的服务和权限给授权用户。自车联云VC被提出以来，多数研究讨论都集中于各类VC应用场景，即以何种方式提供服务的研究。而对整体资源动态部署、调度方案的研究较少，相关的研究也刚刚起步，处在理论探讨阶段[2-4]。

针对现状，本文主要采用车联云体系，将车载自组网和云计算结合起来，使得以往封闭的、单向的车联网系统成为一个完整的体系，在对车载自组网基础架构、云平台资源管理的研究基础上，提出了车联云资源动态部署方案。针对车联云中任务调度问题，提出相应的优化方案，旨在提高车联云资源部署方案的稳定性和可靠性[5]。

本文对车联云VC资源动态部署方案的基本部署和调度方法进行了研究，完成资源部署整体方案的架构设计。并对车联云VC资源调度模块进一步研究，针对用户任务与代理节点间的匹配问题，提出基于改进型层次分析法(enhanced analytic hierarchy process，E-AHP)和二分图最佳匹配(Kuhn-Munkres，KM)匹配算法的调度模型[6-8]，从全局的角度提高用户的满意度和服务的可靠性。基于MATLAB仿真，验证方案的有效性。

1 方案设计

为实现资源共享、满足设计目标和节点分级化管理，车联云VC资源动态部署需要统一的平台进行管控，使得不同的用户都可以通过该平台申请服务。云计算平台提供资源服务的核心方式是将不同租户的不同种类的资源放置在同一个共享的基础架构上统一处理。

1.1 VC部署方案总体设计

本文提出的VC资源部署方案从系统功能分为以下3部分：资源整合、资源管理[9]和资源维护。方案总体框架设计如图1所示。

图1 方案总体架构设计

1.2 任务调度设计

资源调度系统的核心是资源调度策略的使用[10]，本文的资源调度策略包括：

(1)一级调度：任务调度，实现任务与AN间的调度，即对于用户提交服务申请后，邻近的RSU接受该服务请求，选择合适的AN编号ID分配给用户。当用户跨RSU通信区时，亦需重新对RSU进行选择，即需实现RSU的动态实时选择。

(2)二级调度：虚拟机调度，实现AN与VM间的调度，即给用户分配合适的AN后，一方面需要考虑本地AN资源是否足以使用户请求的任务得以运行，若不足，结合本RSU服务区其它AN资源实现VM；另一方面需要考虑到服务的切换handover，即为了保障服务的连续性和质量，当用户从一个RSU覆盖区驶向另一个RSU覆盖区时，需要VM。

本文的研究重点是一级调度，提出一种基于改进型层次分析法E-AHP和二分图KM匹配算法的一级调度模型，并对其中关键步骤进行阐述，该任务调度模型流程如图2所示。

图2 任务调度模型流程

1.2.1 建立二分图网络

任务与AN间网络图G=(V,E)，其中V为顶点的集合，包括子集T和子集AN，E为边的集合。

子集T指用户任务集合，记T={t1,t2,…,tN}，其中t1到tN是N个相互独立的任务，基于本方案中的资源调度准则，每个子任务优先选择同一RSU服务范围内的AN点。

子集AN指资源发起点AN集合，记AN={AN1,AN2,…,ANM}，其中AN1到ANM是M个发起点，AN间相互独立。显然M

当点ti(i=1,2,…,N)向点ANj(j=1,2,…,M)有申请服务意图时，将两点相连形成一条边，边上赋有权值，记为W(i,j)。权值W(i,j)是指VCM中心预估的用户对AN服务点的偏好程度，若ti(i=1,2,…,N)和ANj(j=1,2,…,M)两点间不存在边时，则令W(i,j)=0。

注意到，同一服务时刻子集T中元素只能选择一个子集AN中的元素，而AN中的元素可以同时被多个子集T中元素选择，即只能“一对一”或“多对一”，而不能“一对多”。

从上述建模中，可以得到匹配图G中节点分为子集T和子集AN，各子集内部无边相连，边上有权值，目标函数是使得所有用户的偏好程度综合最大。因此问题的实质是二分图的最优匹配问题。最终的匹配目标是使得所有用户的偏好程度综合最大，即在带权二分图中总权值最大。目标函数

(1)

1.2.2 建立三层评估体系

AHP层次分析法，基于定性和定量的分析和决策，将决策有关的元素分解为目标层、准则层和方案层。因此建立如下三层评估体系：

(1)目标层：即决策的目的，所需要解决的问题，本方案中所需解决的是每个用户如何获得所需的最佳的服务；

(2)准则层：即决策时需考虑的因素，基于车载云计算QoS的考量，本文中主要考虑CPU、内存、带宽3种。将这3种因素作为研究对象，进行决策方案的评估；

(3)方案层：即决策时的各种备选方案，本文中是指ANj(j=1,2,…,M)，共M个备选方案。假定各个方案是相互独立的，不相互影响。

AHP层次评估体系如图3所示。

图3 AHP评估

依据此三层体系，层层计算，最终得到各个备选方案的权值。然而对各个方案进行综合排序时，容易产生这样的结果：当备选方案集合发生变化时，其中某个备选方案的子集会产生排序结果不一致的现象。原因在于现有的处理方法中的归一化处理，有其不足之处。将各个方案对于某指标的相对重要权值做归一化处理，则意味着对某指标有贡献的方案越多，则各个方案的相对重要性就越小。简单的说，AHP算法中，判断矩阵中的元素是指标间的相对重要程度，而权重却是指标的权重，两者不一致。

为了使两者一致，本文提出了改进型的AHP(enhanced-AHP，E-AHP)算法。

(2)

(3)

即依据此进行排序，从而保证方案之间的独立性，备选方案集的改变不影响方案子集的原有排序方式。

1.2.3 二分图匹配KM

KM(Kuhn-Munkres)算法常采用顶标法，即通过给每一个顶点一个标号(顶标)求最大权匹配。常用的求最大权问题算法有最大流或匈牙利算法。本文中采用匈牙利算法，即通过修改顶标将问题转化为完备匹配问题。

获取到各个用户对各个备选方案的权值矩阵后，由于一般来说，用户任务数量远多于AN代理节点数量，故在实际计算时将用户集合随机分成多组，每组数量最大不多于AN数量，通过求每一组局部最佳匹配，获得全局的最佳匹配。对每一组具体算法步骤如下：

(1)初始化可行顶标，如每个ti节点的可行顶标设为它出发的所有边的最大权，ANj节点的可行顶标设为0，任意选取一个初始匹配M，可置空；

(2)遍历集合T，保证集合T的饱和，即保证每个用户都能得到相应的所需的服务，从集合T的每一个顶点出发在等价子图中找增广路。在等价子图中没找到增广路，转(3)，若已经遍历完，转(5)；

(3)修改顶标，记所有现在已搜索过的ti节点为S集合，记所有现在已搜索过的ANj节点记为Y集合，考察所有一段在S集合，一段不属于Y集合中顶点可以构成的边，取

Δd=min{ti+ANj-w(i,j),ti∈S,ANj∉Y}

(4)

把所有S集合中的ti减少Δd之后，所有在Y集合中的点的可行顶标增加Δd，其它顶保持原值不变，从而有新的边加入等价子图；

(4)更新匹配数，通过交换匹配边和未匹配边，使得M边的数目加1，转(2)；

(5)若集合T中顶点已遍历完，且找到完备匹配，则匹配结束，M为最佳匹配。

当找到每一组用户任务等价子图的完备匹配时，也就意味着找到了图G的最佳匹配，只需将各个匹配边的顶标相加，即可获得最终的总的最大的权值。基于该一级调度模型获得的匹配结果，能够满足多数用户的服务需求，从全局的角度保障大多数人的利益。

2 仿真与结果分析

为了能够更好地评估本文提出的基于改进型层次分析法和二分图匹配的任务调度算法的性能。一方面提出改进型AHP算法，比较改进型AHP算法与传统AHP算法对各个备选方案排序结果的影响。另一方面，针对服务类型的不同，分成3种用户，每种生成不同的判断矩阵(通过一致性检验)，以用户满意度作为评价指标，仿真算法性能。

2.1 改进型AHP算法对方案排序结果的仿真

假定现某一用户申请计算密集型服务，有5个备选代理节点AN，选择指标为CPU、带宽和内存。AHP各层判断矩阵见表1～表4。

经MATLAB计算，上述判断矩阵均可通过一致性检验。设定两种场景：

(1)原始5种备选方案。

表1 各指标对于目标层相对权重

表2 各备选方案间对于CPU相对权重

表3 各备选方案间对于内存相对权重

表4 各备选方案间对于带宽相对权重

(2)如果备选方案AN1由于车主撤出车联云而不能实施，即现只有剩余的4种方案。

基于AHP分别计算场景(1)和场景(2)获得最终方案权重总分布，如图4(a)、图4(b)所示。基于E-AHP分别计算场景(1)和场景(2)，方案权重分布如图5(a)、图5(b)所示。

给出上述4种情况下，方案总排序表见表5。

无论采用AHP或是E-AHP，对于场景(1)方案总排序均为：AN3>AN2>AN1>AN4>AN5。为了保障方案之间的独立性，即备选方案集的改变不影响方案子集的原有排序方式原则，对于场景(2)新的总排序应为：AN3>AN2>AN4>AN5。然而对于AHP，新的各方案总排序结果为：AN2>AN3>AN4>AN5，显然不同于AN3>AN2>AN4>AN5，即现有的计算方式存在一定的不足。

当采用E-AHP，针对场景(2)，有结果为AN3>AN2>AN5>AN4，两者一致。从图4和图5可以看出，E-AHP中某些方案的权重分布中某些指标权重变为1，这是因为E-AHP在各个方案对于某指标的相对重要权值做归一化处理的基础上，将获得的权重变为相对权重，保障了与判断矩阵中的元素是指标间的相对重要程度的一致性，从而避免了对某指标有越多贡献的方案相对重要性却越小。

图4 AHP各备选方案权重分布

图5 E-AHP各备选方案权重分布

备选方案AN1AN2AN3AN4AN5AHP场景(1)权重0.15920.31550.37030.07890.0761排序32145AHP场景(2)权重—0.41820.39420.10820.0795排序—1234E-AHP场景(1)权重0.36300.65250.70840.16160.1437排序32145E-AHP场景(2)权重—0.70820.72690.19170.1512排序—2134

因此，E-AHP利用理想方案与各方案之间的相对有效性来判断方案的优劣，保证了各个方案之间的独立性，使得决策结果更加合理与科学。

2.2 用户满意度实验的仿真

此小节以用户满意度为性能指标，基于MATLAB，采用5个备选代理节点，准则层指标为CPU、内存和带宽，考察用户数量对算法性能的影响。定义函数M文件random.m和ZDPP.m，分别用于生成随机判断矩阵和实现最佳匹配。

如图6所示，从整体来看，用户满意度在80%到96%之间，经计算平均满意度为91.0%。当用户数量较少时，用户满意度呈现不规律性。当用户数量大于40时，用户满意度呈现逐渐上升的趋势，且具有相对的稳定性。当用户数量多于65时，用户满意度又呈现逐渐下降的趋势。采用了本章的任务调度算法，用户满意度性能较为合格，因为使用E-AHP获得备选方案的各个权值后，采用二分图KM，能够在满足获得总体最大权值的同时尽可能保证每个用户也采用最好的备选方，即从全局的角度保障多数人的服务质量。

图6 任务调度算法性能

3 结束语

针对车载资源总量大但利用率低的问题，本文提出了新型实用车载网络的车联云。针对车联云VC中任务调度问题，本章提出了一种基于E-AHP和KM匹配的调度算法，给出了算法的流程图，详述了方案具体实现和仿真比较。首先是对车联云中任务调度问题的论述，说明存在用户任务与代理节点间的多目标决策性问题。接着详细阐明算法，方案采用层次分析法AHP，选择CPU、内存和带宽3种准则，构建了三层评估体系。然后层层计算系统的总排序权重，最后得到各个方案对于总目标的总权重。基于AHP层次分析法获得权重后，采用KM算法将权重转化为顶点集的顶标，通过求等价子图的完备匹配最终获得二分图最佳匹配，即最终用户集合与代理节点集合间的最佳匹配。最后，是对任务调度算法的仿真与结果分析，实验结果表明本文方案的有效性和可靠性。

[1]Mejri M N,Ben-Othman J,Hamdi M.Survey on VANET security challenges and possible cryptographic solutions[J].Vehicular Communications,2014,1(2):53-66.

[2]Whaiduzzaman M,Sookhak M,Gani A,et al.A survey on vehicular cloud computing[J].Journal of Network & Computer Applications,2013,40(1):325-344.

[3]Yu R,Zhang Y,Gjessing S,et al.Toward cloud-based vehicu-lar networks with efficient resource management[J].IEEE Network,2013,27(5):48-55.

[4]Lee E,Lee E K,Gerla M,et al.Vehicular cloud networking:Architecture and design principles[J].Communications Magazine IEEE,2014,52(2):148-155.

[5]ZHANG Hengwei,WEI Bo,WANG Jindong,et al.Cloud resource scheduling method based on estimation of distribution shuffled frog leaping algorithm[J].Application Research of Computers,2014,30(11):3225-3228(in Chinese).[张恒巍,卫波,王晋东,等.基于分布估计蛙跳算法的云资源调度方法[J].计算机应用研究,2014,30(11):3225-3228.]

[6]Salahuddin M A,Al-Fuqaha A,Guizani M.Software-defined networking for RSU clouds in support of the internet of vehicles[J].Internet of Things Journal IEEE,2015,2(2):133-144.

[7]Crepaldi R,Beavers R,Ehrat B,et al.LoadingZones:Leveraging street parking to enable vehicular internet access[J].ACM SIGMOBILE Mobile Computing and Communications Review,2013,16(16):38-41.

[8]Mandal U,Habib M,Zhang S,et al.Greening the cloud using renewable-energy-aware service migration[J].IEEE Network,2013,27(6):36-43.

[9]Mishra M,Das A,Kulkarni P,et al.Dynamic resource mana-gement using virtual machine migrations[J].Communications Magazine IEEE,2012,50(9):34-40.

[10]XIAO Jianming,WANG Bo.Cloud computing active scheduling method based on resource monitoring statistics[J].Computer Systems & Applications,2014,23(10):69-72(in Chinese).[肖建明,王波.基于资源监控统计的云计算主动调度方法[J].计算机系统应用,2014,23(10):69-72.]