基于車聯(lián)云的資源動態(tài)部署方案

原 帥，吳學文，朱曉凱

(河海大學 計算機與信息學院，江蘇 南京 211100)

0 引 言

車聯(lián)云(vehicular cloud，VC)是一種集成了車載自組網(wǎng)絡[1]和云計算的新型云組織技術，其中的關鍵性問題是如何整合利用車載資源。現(xiàn)有的車聯(lián)網(wǎng)僅以云服務提供商作為資源的提供者，然而車聯(lián)云模式將用戶本身作為資源的提供者，利用車中已有的軟硬件資源，車聯(lián)云VC集成了計算、傳感、通信和存儲資源，提供相應的服務和權限給授權用戶。自車聯(lián)云VC被提出以來，多數(shù)研究討論都集中于各類VC應用場景，即以何種方式提供服務的研究。而對整體資源動態(tài)部署、調度方案的研究較少，相關的研究也剛剛起步，處在理論探討階段[2-4]。

針對現(xiàn)狀，本文主要采用車聯(lián)云體系，將車載自組網(wǎng)和云計算結合起來，使得以往封閉的、單向的車聯(lián)網(wǎng)系統(tǒng)成為一個完整的體系，在對車載自組網(wǎng)基礎架構、云平臺資源管理的研究基礎上，提出了車聯(lián)云資源動態(tài)部署方案。針對車聯(lián)云中任務調度問題，提出相應的優(yōu)化方案，旨在提高車聯(lián)云資源部署方案的穩(wěn)定性和可靠性[5]。

本文對車聯(lián)云VC資源動態(tài)部署方案的基本部署和調度方法進行了研究，完成資源部署整體方案的架構設計。并對車聯(lián)云VC資源調度模塊進一步研究，針對用戶任務與代理節(jié)點間的匹配問題，提出基于改進型層次分析法(enhanced analytic hierarchy process，E-AHP)和二分圖最佳匹配(Kuhn-Munkres，KM)匹配算法的調度模型[6-8]，從全局的角度提高用戶的滿意度和服務的可靠性。基于MATLAB仿真，驗證方案的有效性。

1 方案設計

為實現(xiàn)資源共享、滿足設計目標和節(jié)點分級化管理，車聯(lián)云VC資源動態(tài)部署需要統(tǒng)一的平臺進行管控，使得不同的用戶都可以通過該平臺申請服務。云計算平臺提供資源服務的核心方式是將不同租戶的不同種類的資源放置在同一個共享的基礎架構上統(tǒng)一處理。

1.1 VC部署方案總體設計

本文提出的VC資源部署方案從系統(tǒng)功能分為以下3部分：資源整合、資源管理[9]和資源維護。方案總體框架設計如圖1所示。

圖1 方案總體架構設計

1.2 任務調度設計

資源調度系統(tǒng)的核心是資源調度策略的使用[10]，本文的資源調度策略包括：

(1)一級調度：任務調度，實現(xiàn)任務與AN間的調度，即對于用戶提交服務申請后，鄰近的RSU接受該服務請求，選擇合適的AN編號ID分配給用戶。當用戶跨RSU通信區(qū)時，亦需重新對RSU進行選擇，即需實現(xiàn)RSU的動態(tài)實時選擇。

(2)二級調度：虛擬機調度，實現(xiàn)AN與VM間的調度，即給用戶分配合適的AN后，一方面需要考慮本地AN資源是否足以使用戶請求的任務得以運行，若不足，結合本RSU服務區(qū)其它AN資源實現(xiàn)VM；另一方面需要考慮到服務的切換handover，即為了保障服務的連續(xù)性和質量，當用戶從一個RSU覆蓋區(qū)駛向另一個RSU覆蓋區(qū)時，需要VM。

本文的研究重點是一級調度，提出一種基于改進型層次分析法E-AHP和二分圖KM匹配算法的一級調度模型，并對其中關鍵步驟進行闡述，該任務調度模型流程如圖2所示。

圖2 任務調度模型流程

1.2.1 建立二分圖網(wǎng)絡

任務與AN間網(wǎng)絡圖G=(V,E)，其中V為頂點的集合，包括子集T和子集AN，E為邊的集合。

子集T指用戶任務集合，記T={t1,t2,…,tN}，其中t1到tN是N個相互獨立的任務，基于本方案中的資源調度準則，每個子任務優(yōu)先選擇同一RSU服務范圍內的AN點。

子集AN指資源發(fā)起點AN集合，記AN={AN1,AN2,…,ANM}，其中AN1到ANM是M個發(fā)起點，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中節(jié)點分為子集T和子集AN，各子集內部無邊相連，邊上有權值，目標函數(shù)是使得所有用戶的偏好程度綜合最大。因此問題的實質是二分圖的最優(yōu)匹配問題。最終的匹配目標是使得所有用戶的偏好程度綜合最大，即在帶權二分圖中總權值最大。目標函數(shù)

(1)

1.2.2 建立三層評估體系

AHP層次分析法，基于定性和定量的分析和決策，將決策有關的元素分解為目標層、準則層和方案層。因此建立如下三層評估體系：

(1)目標層：即決策的目的，所需要解決的問題，本方案中所需解決的是每個用戶如何獲得所需的最佳的服務；

(2)準則層：即決策時需考慮的因素，基于車載云計算QoS的考量，本文中主要考慮CPU、內存、帶寬3種。將這3種因素作為研究對象，進行決策方案的評估；

(3)方案層：即決策時的各種備選方案，本文中是指ANj(j=1,2,…,M)，共M個備選方案。假定各個方案是相互獨立的，不相互影響。

AHP層次評估體系如圖3所示。

圖3 AHP評估

依據(jù)此三層體系，層層計算，最終得到各個備選方案的權值。然而對各個方案進行綜合排序時，容易產(chǎn)生這樣的結果：當備選方案集合發(fā)生變化時，其中某個備選方案的子集會產(chǎn)生排序結果不一致的現(xiàn)象。原因在于現(xiàn)有的處理方法中的歸一化處理，有其不足之處。將各個方案對于某指標的相對重要權值做歸一化處理，則意味著對某指標有貢獻的方案越多，則各個方案的相對重要性就越小。簡單的說，AHP算法中，判斷矩陣中的元素是指標間的相對重要程度，而權重卻是指標的權重，兩者不一致。

為了使兩者一致，本文提出了改進型的AHP(enhanced-AHP，E-AHP)算法。

(2)

(3)

即依據(jù)此進行排序，從而保證方案之間的獨立性，備選方案集的改變不影響方案子集的原有排序方式。

1.2.3 二分圖匹配KM

KM(Kuhn-Munkres)算法常采用頂標法，即通過給每一個頂點一個標號(頂標)求最大權匹配。常用的求最大權問題算法有最大流或匈牙利算法。本文中采用匈牙利算法，即通過修改頂標將問題轉化為完備匹配問題。

獲取到各個用戶對各個備選方案的權值矩陣后，由于一般來說，用戶任務數(shù)量遠多于AN代理節(jié)點數(shù)量，故在實際計算時將用戶集合隨機分成多組，每組數(shù)量最大不多于AN數(shù)量，通過求每一組局部最佳匹配，獲得全局的最佳匹配。對每一組具體算法步驟如下：

(1)初始化可行頂標，如每個ti節(jié)點的可行頂標設為它出發(fā)的所有邊的最大權，ANj節(jié)點的可行頂標設為0，任意選取一個初始匹配M，可置空；

(2)遍歷集合T，保證集合T的飽和，即保證每個用戶都能得到相應的所需的服務，從集合T的每一個頂點出發(fā)在等價子圖中找增廣路。在等價子圖中沒找到增廣路，轉(3)，若已經(jīng)遍歷完，轉(5)；

(3)修改頂標，記所有現(xiàn)在已搜索過的ti節(jié)點為S集合，記所有現(xiàn)在已搜索過的ANj節(jié)點記為Y集合，考察所有一段在S集合，一段不屬于Y集合中頂點可以構成的邊，取

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

(4)

把所有S集合中的ti減少Δd之后，所有在Y集合中的點的可行頂標增加Δd，其它頂保持原值不變，從而有新的邊加入等價子圖；

(4)更新匹配數(shù)，通過交換匹配邊和未匹配邊，使得M邊的數(shù)目加1，轉(2)；

(5)若集合T中頂點已遍歷完，且找到完備匹配，則匹配結束，M為最佳匹配。

當找到每一組用戶任務等價子圖的完備匹配時，也就意味著找到了圖G的最佳匹配，只需將各個匹配邊的頂標相加，即可獲得最終的總的最大的權值。基于該一級調度模型獲得的匹配結果，能夠滿足多數(shù)用戶的服務需求，從全局的角度保障大多數(shù)人的利益。

2 仿真與結果分析

為了能夠更好地評估本文提出的基于改進型層次分析法和二分圖匹配的任務調度算法的性能。一方面提出改進型AHP算法，比較改進型AHP算法與傳統(tǒng)AHP算法對各個備選方案排序結果的影響。另一方面，針對服務類型的不同，分成3種用戶，每種生成不同的判斷矩陣(通過一致性檢驗)，以用戶滿意度作為評價指標，仿真算法性能。

2.1 改進型AHP算法對方案排序結果的仿真

假定現(xiàn)某一用戶申請計算密集型服務，有5個備選代理節(jié)點AN，選擇指標為CPU、帶寬和內存。AHP各層判斷矩陣見表1～表4。

經(jīng)MATLAB計算，上述判斷矩陣均可通過一致性檢驗。設定兩種場景：

(1)原始5種備選方案。

表1 各指標對于目標層相對權重

表2 各備選方案間對于CPU相對權重

表3 各備選方案間對于內存相對權重

表4 各備選方案間對于帶寬相對權重

(2)如果備選方案AN1由于車主撤出車聯(lián)云而不能實施，即現(xiàn)只有剩余的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，即現(xiàn)有的計算方式存在一定的不足。

當采用E-AHP，針對場景(2)，有結果為AN3>AN2>AN5>AN4，兩者一致。從圖4和圖5可以看出，E-AHP中某些方案的權重分布中某些指標權重變?yōu)?，這是因為E-AHP在各個方案對于某指標的相對重要權值做歸一化處理的基礎上，將獲得的權重變?yōu)橄鄬嘀兀Ｕ狭伺c判斷矩陣中的元素是指標間的相對重要程度的一致性，從而避免了對某指標有越多貢獻的方案相對重要性卻越小。

圖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利用理想方案與各方案之間的相對有效性來判斷方案的優(yōu)劣，保證了各個方案之間的獨立性，使得決策結果更加合理與科學。

2.2 用戶滿意度實驗的仿真

此小節(jié)以用戶滿意度為性能指標，基于MATLAB，采用5個備選代理節(jié)點，準則層指標為CPU、內存和帶寬，考察用戶數(shù)量對算法性能的影響。定義函數(shù)M文件random.m和ZDPP.m，分別用于生成隨機判斷矩陣和實現(xiàn)最佳匹配。

如圖6所示，從整體來看，用戶滿意度在80%到96%之間，經(jīng)計算平均滿意度為91.0%。當用戶數(shù)量較少時，用戶滿意度呈現(xiàn)不規(guī)律性。當用戶數(shù)量大于40時，用戶滿意度呈現(xiàn)逐漸上升的趨勢，且具有相對的穩(wěn)定性。當用戶數(shù)量多于65時，用戶滿意度又呈現(xiàn)逐漸下降的趨勢。采用了本章的任務調度算法，用戶滿意度性能較為合格，因為使用E-AHP獲得備選方案的各個權值后，采用二分圖KM，能夠在滿足獲得總體最大權值的同時盡可能保證每個用戶也采用最好的備選方，即從全局的角度保障多數(shù)人的服務質量。

圖6 任務調度算法性能

3 結束語

針對車載資源總量大但利用率低的問題，本文提出了新型實用車載網(wǎng)絡的車聯(lián)云。針對車聯(lián)云VC中任務調度問題，本章提出了一種基于E-AHP和KM匹配的調度算法，給出了算法的流程圖，詳述了方案具體實現(xiàn)和仿真比較。首先是對車聯(lián)云中任務調度問題的論述，說明存在用戶任務與代理節(jié)點間的多目標決策性問題。接著詳細闡明算法，方案采用層次分析法AHP，選擇CPU、內存和帶寬3種準則，構建了三層評估體系。然后層層計算系統(tǒng)的總排序權重，最后得到各個方案對于總目標的總權重。基于AHP層次分析法獲得權重后，采用KM算法將權重轉化為頂點集的頂標，通過求等價子圖的完備匹配最終獲得二分圖最佳匹配，即最終用戶集合與代理節(jié)點集合間的最佳匹配。最后，是對任務調度算法的仿真與結果分析，實驗結果表明本文方案的有效性和可靠性。

[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).[張恒巍,衛(wèi)波,王晉東,等.基于分布估計蛙跳算法的云資源調度方法[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).[肖建明,王波.基于資源監(jiān)控統(tǒng)計的云計算主動調度方法[J].計算機系統(tǒng)應用,2014,23(10):69-72.]