面向車聯(lián)網(wǎng)低時(shí)延需求的分布式路徑計(jì)算方案

李瑞彪,任繼軍,任智源

(1.西安郵電大學(xué)通信與信息工程學(xué)院,710121,西安;2.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,710071,西安)

近幾年,移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)和傳感器技術(shù)迅速發(fā)展,車聯(lián)網(wǎng)(internet of vehicles,IoV)技術(shù)成為推動(dòng)未來智慧交通發(fā)展的關(guān)鍵驅(qū)動(dòng)力之一。車聯(lián)網(wǎng)是傳統(tǒng)車載自組織網(wǎng)絡(luò)(vehicular ad hoc network,VANET)的演變,實(shí)現(xiàn)了人、車、路、環(huán)境的智能交互[1],其組織結(jié)構(gòu)由采集層、傳輸層和服務(wù)層共3部分組成[2]。采集層完成信息獲取,傳輸層傳遞數(shù)據(jù),服務(wù)層主要指車載設(shè)備在與網(wǎng)絡(luò)服務(wù)設(shè)備進(jìn)行信息交換的基礎(chǔ)上,充分利用其計(jì)算資源為車輛終端提供不同的功能服務(wù)。車聯(lián)網(wǎng)的業(yè)務(wù)根據(jù)應(yīng)用場景劃分為交通控制、信息服務(wù)以及駕駛安全保障共3大類型,且這3個(gè)類型在網(wǎng)絡(luò)帶寬、連接性能、時(shí)延以及網(wǎng)絡(luò)部署方面具有不同要求[3]。車聯(lián)網(wǎng)的傳輸層支持車對車(V2V)、車對人(V2P)、車對路邊單元(V2I)通信,對于小數(shù)據(jù)的V2V及V2I間傳輸安全類業(yè)務(wù),傳輸時(shí)延問題并不突出。然而,對于時(shí)延要求高的動(dòng)態(tài)地圖、AR導(dǎo)航等信息類服務(wù),在處理周圍龐大的交通數(shù)據(jù)時(shí)相應(yīng)會(huì)面臨嚴(yán)峻的傳輸時(shí)延問題。而且,隨著5G通信服務(wù)的不斷擴(kuò)大,車載網(wǎng)絡(luò)的可擴(kuò)展和復(fù)雜性決定了大數(shù)據(jù)業(yè)務(wù)低時(shí)延處理的難度,因此對于處理一系列承載海量數(shù)據(jù)的新興車聯(lián)網(wǎng)服務(wù)的需求尤為迫切[4]。早期的車載應(yīng)用以云計(jì)算和無線傳感器網(wǎng)絡(luò)(WSN)深度融合的車聯(lián)網(wǎng)架構(gòu)[5]為支撐,憑借其豐富的計(jì)算、存儲(chǔ)資源擺脫車載設(shè)備計(jì)算能力弱的困擾,但云計(jì)算的缺點(diǎn)也很明顯,其遠(yuǎn)離車輛終端用戶,無法解決大數(shù)據(jù)傳輸帶來的高時(shí)延問題,導(dǎo)致車載用戶體驗(yàn)較差。

為克服云計(jì)算模式的缺陷,許多學(xué)者展開了研究。Vemireddy等提出了將車輛當(dāng)作霧節(jié)點(diǎn)的車載霧計(jì)算卸載機(jī)制,利用移動(dòng)的空閑計(jì)算資源迅速地協(xié)作完成應(yīng)用服務(wù)[6];劉可欣等提出了一種“車-邊-云”協(xié)同網(wǎng)絡(luò)架構(gòu),并基于改進(jìn)的煙花算法完成最佳的任務(wù)調(diào)度,實(shí)現(xiàn)時(shí)延性能的最優(yōu)化[7];Vankadara等提出了一種移動(dòng)云環(huán)境中動(dòng)態(tài)任務(wù)卸載方案,專注于降低任務(wù)在本地和遠(yuǎn)程計(jì)算的能源消耗和處理時(shí)延[8];Younis等提出了一個(gè)權(quán)衡任務(wù)分配的多邊緣節(jié)點(diǎn)任務(wù)卸載方案,并基于線性編程方法對網(wǎng)絡(luò)時(shí)延實(shí)現(xiàn)大幅度的性能提升[9];Hou等提出了霧計(jì)算協(xié)助無人機(jī)群的理論架構(gòu),彌補(bǔ)了云計(jì)算在處理延遲敏感服務(wù)方面的不足[10];Hussain等針對車聯(lián)網(wǎng)中海量數(shù)據(jù)低時(shí)延通信問題,提出一種動(dòng)態(tài)Q學(xué)習(xí)算法來進(jìn)行合理的網(wǎng)絡(luò)選擇,并通過對信道容量、車輛的性能考慮來選擇最優(yōu)的傳輸路徑[11]。但是,上述研究采用的任務(wù)結(jié)構(gòu)和類型較為單一,且沒有實(shí)現(xiàn)數(shù)據(jù)在傳輸過程中完成任務(wù)計(jì)算。

為此,本文引入一種基于云霧網(wǎng)絡(luò)架構(gòu)的分布式路徑節(jié)點(diǎn)計(jì)算技術(shù)[12-16],它與網(wǎng)絡(luò)功能虛擬化(network functions virtualization,NFV)技術(shù)[17]相結(jié)合,將不同結(jié)構(gòu)的應(yīng)用服務(wù)靈活地嵌入到附近廣泛分布的邊緣霧網(wǎng)絡(luò)設(shè)備中,在保障大數(shù)據(jù)業(yè)務(wù)的傳輸性能上有獨(dú)特的優(yōu)勢。設(shè)備之間構(gòu)建的網(wǎng)絡(luò)鏈接支持任務(wù)在傳輸過程中完成計(jì)算的能力,但路徑計(jì)算技術(shù)對傳輸時(shí)延問題不突出的安全類業(yè)務(wù)的提升空間不大。在當(dāng)前負(fù)載均衡技術(shù)深入分布式計(jì)算的應(yīng)用當(dāng)中,考慮到單個(gè)網(wǎng)絡(luò)執(zhí)行節(jié)點(diǎn)的數(shù)據(jù)負(fù)載過高或過低都會(huì)造成不必要的時(shí)延消耗,因此節(jié)點(diǎn)設(shè)備間要合理分配任務(wù)資源[18]。又考慮到每個(gè)霧節(jié)點(diǎn)設(shè)備的運(yùn)算能力有限,無法獨(dú)立完成復(fù)雜的計(jì)算業(yè)務(wù),所以一個(gè)完整業(yè)務(wù)可以分割成若干個(gè)獨(dú)立的子業(yè)務(wù)。本文采用一種任務(wù)映射策略,將分割的子業(yè)務(wù)映射到附近固定的霧計(jì)算單元完成路徑計(jì)算,在保障通信質(zhì)量良好的同時(shí)有效降低了時(shí)延[19]。由于映射的不唯一,必然存在不合理的任務(wù)映射方案,因此基于改進(jìn)的離散二值粒子群優(yōu)化(NBPSO)算法得到最優(yōu)的任務(wù)映射。本文還研究了不同類型業(yè)務(wù)、不同結(jié)構(gòu)業(yè)務(wù)以及不同霧設(shè)備負(fù)載在本文方案下的性能。需要說明的是,在追求時(shí)延最小化時(shí)會(huì)導(dǎo)致網(wǎng)絡(luò)設(shè)備的能耗增加,本文為簡化研究的復(fù)雜性并未加入能耗約束[20]。

1 云霧網(wǎng)絡(luò)架構(gòu)

為了將車載服務(wù)處理周期變短,保障用戶服務(wù)質(zhì)量(quality of service,QoS),本節(jié)選取一個(gè)從上到下依次為云計(jì)算層、霧計(jì)算層以及車載用戶終端構(gòu)成的云霧網(wǎng)絡(luò)架構(gòu),如圖1所示。

1,2—交換機(jī);3,4—路由器;5,6—網(wǎng)關(guān)。圖1 云霧網(wǎng)絡(luò)架構(gòu)Fig.1 Cloud and fog network architecture

云計(jì)算層由高性能服務(wù)器集群以分布式方式構(gòu)建,具備計(jì)算速度快、規(guī)模大、可用性高等優(yōu)點(diǎn)。霧計(jì)算層由部署在不同地點(diǎn)的交換機(jī)、路由器、網(wǎng)關(guān)等固定的邊緣設(shè)備組成,實(shí)現(xiàn)應(yīng)用服務(wù)的全網(wǎng)覆蓋。這些設(shè)備具有一定的計(jì)算、存儲(chǔ)和轉(zhuǎn)發(fā)能力,便于在設(shè)備集群內(nèi)進(jìn)行數(shù)據(jù)傳輸。車載用戶終端指車載智能終端,包括車載電腦、智能導(dǎo)航系統(tǒng)等智能設(shè)備。

3層網(wǎng)絡(luò)架構(gòu)之間用無線通信技術(shù)進(jìn)行信息交換。其中,車載用戶終端既是服務(wù)請求的發(fā)起者,也是數(shù)據(jù)的最終接收者,可以與附近或遠(yuǎn)端的網(wǎng)絡(luò)邊緣設(shè)備以及云服務(wù)器進(jìn)行無線通信連接。一般而言,云計(jì)算層中服務(wù)器的計(jì)算能力遠(yuǎn)遠(yuǎn)超過單個(gè)霧節(jié)點(diǎn)的計(jì)算能力,但又因其部署遠(yuǎn)離終端應(yīng)用,使得數(shù)據(jù)傳輸時(shí)延在整個(gè)業(yè)務(wù)周期中的比重較大。因此,在處理簡單的車載業(yè)務(wù)時(shí),將車載用戶終端的服務(wù)請求上傳到附近的網(wǎng)絡(luò)霧節(jié)點(diǎn),利用多個(gè)霧節(jié)點(diǎn)的計(jì)算資源協(xié)同處理數(shù)據(jù)。但是,如果當(dāng)前的車載業(yè)務(wù)過于復(fù)雜,將任務(wù)交給云端可以更好地保證服務(wù)質(zhì)量。此外,云計(jì)算層負(fù)責(zé)霧設(shè)備的實(shí)時(shí)監(jiān)控和管理,同時(shí)根據(jù)霧節(jié)點(diǎn)的算力狀態(tài)、轉(zhuǎn)發(fā)能力以及業(yè)務(wù)流模型等相關(guān)信息,提前擬定好車輛計(jì)算業(yè)務(wù)卸載到網(wǎng)絡(luò)邊緣設(shè)備的業(yè)務(wù)卸載策略,并將業(yè)務(wù)之間明確的調(diào)度關(guān)系從云端緩存到指定霧網(wǎng)絡(luò)中的執(zhí)行節(jié)點(diǎn),利用泛在網(wǎng)絡(luò)節(jié)點(diǎn)的算力資源實(shí)現(xiàn)在網(wǎng)協(xié)同計(jì)算,降低了業(yè)務(wù)消費(fèi)的時(shí)間成本。

2 基于NBPSO算法的業(yè)務(wù)卸載策略

2.1 有向無環(huán)圖的業(yè)務(wù)流模型

有向無環(huán)圖(DAG)描述的業(yè)務(wù)流定義如下:DAG表征為無環(huán)的有向圖,有向無環(huán)圖是對具有優(yōu)先關(guān)系或依賴關(guān)系的事物進(jìn)行抽象描述。將有向無環(huán)圖應(yīng)用于車聯(lián)網(wǎng)業(yè)務(wù)場景中,一個(gè)復(fù)雜的車載業(yè)務(wù)往往可以由若干個(gè)相對簡單且獨(dú)立的車載子業(yè)務(wù)組成,它們在執(zhí)行時(shí)間上存在同步或異步的依賴約束。有向無環(huán)圖的各節(jié)點(diǎn)作為子業(yè)務(wù)節(jié)點(diǎn),有向邊代表子業(yè)務(wù)之間的依賴關(guān)系,用邊上權(quán)值表示前后子業(yè)務(wù)的數(shù)據(jù)傳輸時(shí)延。本文將同一業(yè)務(wù)的DAG業(yè)務(wù)流模型簡單分為串行業(yè)務(wù)流、并行業(yè)務(wù)流以及串并業(yè)務(wù)流共3種結(jié)構(gòu)。

在業(yè)務(wù)調(diào)度過程中,從業(yè)務(wù)起點(diǎn)計(jì)算到達(dá)業(yè)務(wù)終點(diǎn)的有向路徑的數(shù)量是由DAG業(yè)務(wù)流模型的分支條數(shù)所決定的,且每條路徑上的邊權(quán)值總和存在差異,故導(dǎo)致不同分支路徑耗費(fèi)總時(shí)間可能不同,只有各分支路徑中的全部子業(yè)務(wù)均處理完畢,整個(gè)業(yè)務(wù)才能結(jié)束。因此,完整業(yè)務(wù)的結(jié)束時(shí)間為所有任意分支路徑中起點(diǎn)到匯點(diǎn)的最大累積時(shí)延。

為了實(shí)現(xiàn)車聯(lián)網(wǎng)應(yīng)用服務(wù)從中心轉(zhuǎn)移到網(wǎng)絡(luò)邊緣,從集中處理數(shù)據(jù)轉(zhuǎn)變?yōu)榉稚⑻幚頂?shù)據(jù),本節(jié)將有向無環(huán)圖表示的業(yè)務(wù)流模型映射到無向圖(UG)表示的霧網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,映射示例如圖2所示。

q1～q6—子業(yè)務(wù)節(jié)點(diǎn);w1～w11—霧網(wǎng)絡(luò)節(jié)點(diǎn)。圖2 有向無環(huán)圖至無向圖的映射示例Fig.2 Example of a mapping from a directed acyclic graph to an undirected graph

2.2 DAG至UG映射方案

本文將車載應(yīng)用服務(wù)分散化,用M=(Q,K)表示DAG形式的車載業(yè)務(wù)流模型,然后定義Q={q1,q2,…,qs,qs+1,…,qn-1,qn|s≥1,n>s+1}為模型M的車載子業(yè)務(wù)集合。q1,q2,…,qs為s個(gè)車載子業(yè)務(wù)起點(diǎn),qs+1,…,qn-1為中間車載業(yè)務(wù)集合,qn為車載業(yè)務(wù)終點(diǎn)。K為M的有向邊的集合,表示車載子業(yè)務(wù)間的依賴性。子業(yè)務(wù)qj的前向子業(yè)務(wù)集合用r(qj)={qj|(qi,qj)}定義。

定義U=(W,E)無向連通圖表征靜態(tài)霧網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)鋱D,圖U的霧網(wǎng)絡(luò)節(jié)點(diǎn)集合W={w1,w2,…,ws,ws+1,…,wl-1,wl|s≥1,l>s+1}。w1,w2,…,ws為數(shù)據(jù)的發(fā)起節(jié)點(diǎn),wl為目標(biāo)節(jié)點(diǎn),ws+1,…,wl-1為中間節(jié)點(diǎn),發(fā)起節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)都是車輛終端設(shè)備的直連節(jié)點(diǎn)。E為圖U中霧節(jié)點(diǎn)通過無線連通的邊集合,相鄰節(jié)點(diǎn)間的邊支持雙向傳輸,關(guān)聯(lián)兩個(gè)霧計(jì)算節(jié)點(diǎn)。

定義1子業(yè)務(wù)集合卸載規(guī)則。定義卸載節(jié)點(diǎn)集合ξ為Q→W,滿足

(1)

由式(1)可知,車載子業(yè)務(wù)集合Q中的車載業(yè)務(wù)起點(diǎn)q1,q2,…,qs、車載中繼業(yè)務(wù)qs+1,…,qn-1、車載終點(diǎn)業(yè)務(wù)qn分別依次被卸載到霧計(jì)算節(jié)點(diǎn)集合W的數(shù)據(jù)發(fā)起節(jié)點(diǎn)w1,w2,…,ws、中間節(jié)點(diǎn)ws+1,…,wl-1以及目標(biāo)節(jié)點(diǎn)wl。卸載關(guān)系由ξ進(jìn)行統(tǒng)一描述,且源末節(jié)點(diǎn)業(yè)務(wù)卸載唯一,中間節(jié)點(diǎn)業(yè)務(wù)卸載具有隨機(jī)性,故同一車輛卸載業(yè)務(wù)卸載至固定的霧網(wǎng)絡(luò)拓?fù)鋾r(shí)存在多種卸載方案。

定義2有向邊集合映射規(guī)則。定義映射ψ為K→P,其中,P={Path,wiwj|wi,wj∈W},Path,wiwj為節(jié)點(diǎn)wi到wj的數(shù)據(jù)傳輸最短路徑,P為所有Path,wiwj的集合,dwi,wj為在此路徑下兩節(jié)點(diǎn)的單位數(shù)據(jù)量傳輸最短時(shí)延。對于霧網(wǎng)絡(luò)中所有直接或間接關(guān)聯(lián)的兩個(gè)霧節(jié)點(diǎn),參照網(wǎng)絡(luò)邊權(quán)重和節(jié)點(diǎn)連通狀態(tài),利用最短路徑(Dijkstra)算法得到連通節(jié)點(diǎn)間的最短時(shí)延dwi,wj和最短路徑Path,wiwj。

將DAG業(yè)務(wù)流模型的有向邊映射為節(jié)點(diǎn)ξ(qi)至節(jié)點(diǎn)ξ(qj)的數(shù)據(jù)傳輸最短路徑Path,wiwj,并用ψ表示映射的結(jié)果集,即

ψ(qi,qj)=Path,ξ(qi)ξ(qj)

(2)

2.3 DAG至UG的映射時(shí)延優(yōu)化

同一車輛卸載業(yè)務(wù)映射至固定靜態(tài)霧網(wǎng)絡(luò)拓?fù)鋾r(shí),存在多種映射方案,不同的路徑方案產(chǎn)生的時(shí)延不同。因此,合理分配和有效利用霧節(jié)點(diǎn)的運(yùn)算資源可以改善業(yè)務(wù)處理的時(shí)延性能。為降低不同霧節(jié)點(diǎn)之間因數(shù)據(jù)多跳帶來的傳輸時(shí)延開銷,本文構(gòu)建了一種時(shí)延性能優(yōu)化方法。

在某次業(yè)務(wù)映射關(guān)系中,子業(yè)務(wù)qi完成所耗費(fèi)的時(shí)延T(qi)為子業(yè)務(wù)qi的累積時(shí)延Ta(qi)和此業(yè)務(wù)下的計(jì)算時(shí)延Tc(qi)之和,即

T(qi)=Ta(qi)+Tc(qi)

(3)

式中qi的累積時(shí)延Ta(qi)是qi前向子業(yè)務(wù)的時(shí)延之和,包括計(jì)算時(shí)延和傳輸時(shí)延,計(jì)算式為

(4)

其中,Dqjqi表示節(jié)點(diǎn)ξ(qj)到達(dá)節(jié)點(diǎn)ξ(qi)最短通路上處理的數(shù)據(jù)量。qi的計(jì)算時(shí)延Tc(qi)與其映射節(jié)點(diǎn)的數(shù)據(jù)量Dqi、計(jì)算復(fù)雜度系數(shù)η以及霧節(jié)點(diǎn)計(jì)算能力pξ(qi)的變化有關(guān),即

(5)

由上述得出,業(yè)務(wù)終點(diǎn)qn的處理時(shí)延與模型M的業(yè)務(wù)處理時(shí)延等價(jià),即

T(M)=T(qn)

(6)

以DAG業(yè)務(wù)流形式的車輛卸載應(yīng)用映射至指定霧網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)存在多維性,因此業(yè)務(wù)處理的平均延遲不同。業(yè)務(wù)與霧節(jié)點(diǎn)的多維映射關(guān)系都可以由關(guān)系矩陣X來表征。關(guān)系矩陣X為

(7)

式中xqpwq∈X表征指定車載子業(yè)務(wù)到指定霧節(jié)點(diǎn)的映射情況。若xqpwq=0,則表示子業(yè)務(wù)qp到霧節(jié)點(diǎn)wq無映射關(guān)系;若xqpwq=1,則表示子業(yè)務(wù)qp到霧節(jié)點(diǎn)wq有唯一映射關(guān)系。映射關(guān)系也可以表示為

xqpwq∈{0,1},?qp∈Q,?wq∈W

(8)

根據(jù)式(8)的映射關(guān)系,式(3)更新為

(9)

根據(jù)以上介紹的節(jié)點(diǎn)映射規(guī)則,車載業(yè)務(wù)T(M)的處理時(shí)延可表示為X的函數(shù),即

T(M)=F(X)

(10)

將上述時(shí)延優(yōu)化問題轉(zhuǎn)化為二值優(yōu)化問題,模型M至圖U的最佳映射方案建模如下

(11)

2.4 改進(jìn)的離散二值粒子群優(yōu)化算法

改進(jìn)的離散二值粒子群優(yōu)化(NBPSO)算法是一個(gè)全局隨機(jī)尋優(yōu)算法,主要用來優(yōu)化離散空間的約束問題,是粒子群算法(BPSO)的一種改進(jìn)算法[21-22]。該算法不僅促進(jìn)了粒子收斂于群體最優(yōu),而且改善了后期的個(gè)體尋優(yōu)能力,提高了BPSO算法的收斂性能,方便求式(11)的時(shí)延優(yōu)化問題。

假設(shè)粒子群由M個(gè)粒子構(gòu)成,尋優(yōu)空間為m維,最大迭代次數(shù)為Nmax,則第i個(gè)粒子在有限次迭代過程中的位置Xi和速度Vi可表示為

(12)

式中o表示尋優(yōu)空間總維數(shù),即子業(yè)務(wù)與每個(gè)霧節(jié)點(diǎn)可能存在映射的所有情況。

(13)

粒子的動(dòng)態(tài)速度值與迭代次數(shù)呈正相關(guān),定義粒子的自適應(yīng)速度eio為

(14)

(15)

第i個(gè)粒子經(jīng)過k次迭代后的速度變化公式為

(16)

式中w為慣性權(quán)重。第i個(gè)粒子經(jīng)過k次迭代后的位置變化公式為

(17)

定義自適應(yīng)度函數(shù)為

f(X)=F(M)=F(X)

(18)

NBPSO算法求解時(shí)延優(yōu)化模型的具體步驟如下。

1 參數(shù)的設(shè)置:M,Nmax,ci,w

2 fori≤Mdo

3 隨機(jī)初始化粒子的位置和速度

4 由式(18)自適應(yīng)度函數(shù)f(X)評估所有粒子

6 end for

7 for 1 toNmaxdo

8 fori≤Mdo

9 根據(jù)式(13)～(16)計(jì)算粒子迭代的速度Vi

10 根據(jù)式(17)計(jì)算粒子迭代后的位置Xi

11 根據(jù)式(18)重新評估粒子的自適應(yīng)值

14 end if

15 end for

16 end for

18 returnpbest

3 性能仿真和評估

為了測試分布式路徑計(jì)算方案應(yīng)用于車聯(lián)網(wǎng)場景中高通信效率的優(yōu)點(diǎn),本文首先對比中心云服務(wù)計(jì)算與分布式路徑計(jì)算的時(shí)延,然后分別從車聯(lián)網(wǎng)的業(yè)務(wù)類型、DAG業(yè)務(wù)流模型、霧節(jié)點(diǎn)負(fù)載以及不同算法等多個(gè)維度去分析該計(jì)算方案下的時(shí)延性能。同時(shí),考慮到仿真數(shù)據(jù)的真實(shí)性,本次仿真得到的最終數(shù)據(jù)是通過30次實(shí)驗(yàn)的平均值。

假設(shè)將一個(gè)完整的車載業(yè)務(wù)劃分為6個(gè)相對獨(dú)立的子業(yè)務(wù),本文針對同一業(yè)務(wù)仿真采取了3種簡單結(jié)構(gòu)的DAG業(yè)務(wù)流模型,依次為串行業(yè)務(wù)流、并行業(yè)務(wù)流、串并業(yè)務(wù)流,如圖3所示。

(a)串行業(yè)務(wù)流

圖3中,3種結(jié)構(gòu)圖的首尾分別表示業(yè)務(wù)始點(diǎn)和業(yè)務(wù)終點(diǎn),其余均為中間業(yè)務(wù),根據(jù)業(yè)務(wù)卸載策略,將6個(gè)子業(yè)務(wù)卸載到下文采用的霧網(wǎng)絡(luò)拓?fù)鋱D中。

為不失一般性,本文利用Matlab仿真平臺(tái)隨機(jī)產(chǎn)生由12個(gè)霧節(jié)點(diǎn)組成的霧網(wǎng)絡(luò)拓?fù)鋱D,并設(shè)置邊緣權(quán)重表征連通節(jié)點(diǎn)間的數(shù)據(jù)傳輸速率,如圖4所示。其中,w1為業(yè)務(wù)處理起始節(jié)點(diǎn),w12為業(yè)務(wù)處理終止節(jié)點(diǎn),w2～w11為業(yè)務(wù)處理中間節(jié)點(diǎn)。

圖4 霧網(wǎng)絡(luò)拓?fù)銯ig.4 Fog network topology

3.1 仿真參數(shù)設(shè)置

本文采用的仿真軟件為Matlab,實(shí)驗(yàn)涉及的參數(shù)借鑒文獻(xiàn)[23-25]的數(shù)據(jù),具體設(shè)置見表1。其中,平均業(yè)務(wù)計(jì)算復(fù)雜度η表示平均分配到單個(gè)霧映射節(jié)點(diǎn)的業(yè)務(wù)計(jì)算復(fù)雜度。

表1 云霧網(wǎng)絡(luò)和NBPSO算法參數(shù)

3.2 仿真結(jié)果分析

3.2.1 云計(jì)算和分布式路徑計(jì)算平均時(shí)延對比

為驗(yàn)證分布式路徑計(jì)算的優(yōu)越性,本小節(jié)在霧節(jié)點(diǎn)計(jì)算能力相同的前提下,從數(shù)據(jù)量、業(yè)務(wù)計(jì)算復(fù)雜度兩個(gè)角度來比較云計(jì)算和分布式路徑計(jì)算的時(shí)延性能。每個(gè)霧映射節(jié)點(diǎn)處理業(yè)務(wù)的數(shù)據(jù)量和復(fù)雜度相同,DAG業(yè)務(wù)流模型僅采用圖3中的并行結(jié)構(gòu)。云計(jì)算與路徑計(jì)算基于不同數(shù)據(jù)量的時(shí)延對比如圖5和圖6所示。

(a)大數(shù)據(jù)量下云計(jì)算和路徑計(jì)算的時(shí)延對比

從圖5可知,隨著數(shù)據(jù)量的不斷增加,分布式路徑計(jì)算和中心云計(jì)算的平均時(shí)延(包括平均傳輸時(shí)延和平均處理時(shí)延)均呈現(xiàn)上升趨勢。此外,不難看出,在0～500 kb和0～12 Mb下,中心云計(jì)算的平均時(shí)延均要高于分布式路徑計(jì)算的平均時(shí)延,這是由于中心云遠(yuǎn)距離接收和轉(zhuǎn)發(fā)業(yè)務(wù)數(shù)據(jù)導(dǎo)致的結(jié)果。當(dāng)業(yè)務(wù)數(shù)據(jù)量為300 kb和12 Mb時(shí),本文所提方案的時(shí)延分別為39.51 ms和1.12 s,較云計(jì)算的時(shí)延分別降低了18.73 ms和2.95 s。顯然,該方案對于傳輸安全類業(yè)務(wù)和用戶數(shù)據(jù)類業(yè)務(wù)都具有改善意義。特別地,對于大數(shù)據(jù)用戶業(yè)務(wù)的時(shí)延改善程度更為顯著。這是因?yàn)楫?dāng)處理小數(shù)據(jù)安全類業(yè)務(wù)時(shí),云強(qiáng)大的計(jì)算能力在一定程度上可以緩解小數(shù)據(jù)傳輸過程中的延時(shí)問題。但是,當(dāng)處理大數(shù)據(jù)業(yè)務(wù)時(shí),云端的計(jì)算能力發(fā)揮的效果有所下降,其傳輸上的消耗變大。相反,與云中心的超負(fù)荷通信相比,泛在連接的網(wǎng)絡(luò)邊緣設(shè)備靠近終端用戶,服務(wù)響應(yīng)及時(shí)?；谠旗F網(wǎng)絡(luò)架構(gòu)實(shí)現(xiàn)的分布式路徑協(xié)同計(jì)算方案可以顯著降低大數(shù)據(jù)業(yè)務(wù)請求時(shí)延。

圖6比較了分布式路徑協(xié)作計(jì)算和云計(jì)算在不同業(yè)務(wù)計(jì)算復(fù)雜度下的時(shí)延變化趨勢,此時(shí)仿真的業(yè)務(wù)總數(shù)據(jù)量固定為12 Mb,平均業(yè)務(wù)計(jì)算復(fù)雜度根據(jù)表1設(shè)置為0.6η～1.6η?？梢钥闯?當(dāng)業(yè)務(wù)復(fù)雜度由η逐漸增加至1.6η時(shí),路徑協(xié)作計(jì)算的平均處理時(shí)延與云處理平均時(shí)延也相應(yīng)增長,但云計(jì)算增長遲緩。例如,復(fù)雜度由η增加至1.6η,時(shí)延僅從3.21 s增加到3.43 s。這是因?yàn)閿?shù)據(jù)量一定時(shí),云計(jì)算模式的傳輸時(shí)延不會(huì)隨業(yè)務(wù)復(fù)雜度的變化而改變,路徑協(xié)作計(jì)算的傳輸時(shí)延也變化微小,所以業(yè)務(wù)的平均等待時(shí)延僅存在計(jì)算上的時(shí)延消耗?？紤]到網(wǎng)絡(luò)邊緣單個(gè)匯聚節(jié)點(diǎn)的計(jì)算能力有限,所以路徑式協(xié)作計(jì)算處理復(fù)雜業(yè)務(wù)的平均時(shí)延上漲的幅度較大。相反,中心云的計(jì)算能力較強(qiáng),處理復(fù)雜業(yè)務(wù)時(shí)的時(shí)延性能優(yōu)于路徑協(xié)作計(jì)算。由此可推出,當(dāng)業(yè)務(wù)復(fù)雜度不斷增加甚至超越某閾值后,路徑式協(xié)作計(jì)算的處理時(shí)延將會(huì)超過云計(jì)算的處理時(shí)延。因此,復(fù)雜度較低時(shí),分布式路徑協(xié)作計(jì)算的時(shí)效性能好,復(fù)雜度較高時(shí),中心云處理的時(shí)效性能好。

圖6 云計(jì)算和路徑計(jì)算基于計(jì)算復(fù)雜度的時(shí)延對比Fig.6 Latency comparison between cloud computing and path computing based on computational complexities

綜上所述可知,與云計(jì)算遠(yuǎn)距離服務(wù)相比,分步驟處理業(yè)務(wù)的路徑協(xié)作計(jì)算方案極大地提升了業(yè)務(wù)請求的響應(yīng)速度,更易體現(xiàn)低時(shí)延的特性。

3.2.2 不同業(yè)務(wù)類型的時(shí)延性能分析

車聯(lián)網(wǎng)不同業(yè)務(wù)場景對于時(shí)延的容忍度不同,本小節(jié)旨在研究不同類型業(yè)務(wù)在分布式路徑計(jì)算方案下的時(shí)延性能。根據(jù)業(yè)務(wù)承載數(shù)據(jù)量和復(fù)雜度的不同,本文設(shè)計(jì)了駕駛安全類(A1～A3)、交通控制類(B1～B3)、信息服務(wù)類(C1～C3) 共3種業(yè)務(wù)。其中,1、2、3分表代表任務(wù)的復(fù)雜度,1代表復(fù)雜度最小,3代表復(fù)雜度最大。不同業(yè)務(wù)類型的云計(jì)算和路徑計(jì)算的時(shí)延比較如圖7。

圖7 不同業(yè)務(wù)類型的云計(jì)算和路徑計(jì)算的時(shí)延比較Fig.7 Latency comparison between cloud and path computing for different business types

從圖7可以看出,分布式路徑計(jì)算處理不同類型業(yè)務(wù)的平均時(shí)延均低于云計(jì)算的。其中,駕駛安全類、交通控制類、信息服務(wù)類業(yè)務(wù)的時(shí)延降低范圍分別為19.4%～29.3%、24.2%～40.4%以及38.5%～57.0%。信息服務(wù)類業(yè)務(wù)在路徑計(jì)算方案下的改善效果最好。這是因?yàn)槌休d小數(shù)據(jù)的駕駛安全業(yè)務(wù)雖然業(yè)務(wù)的計(jì)算復(fù)雜度要低很多,但是在傳輸性能上的改善程度遠(yuǎn)不如承載大數(shù)據(jù)的信息服務(wù)類業(yè)務(wù)明顯。因此,分布式路徑計(jì)算在降低大數(shù)據(jù)和低復(fù)雜度類型任務(wù)的時(shí)延效果最好。

3.2.3 異構(gòu)DAG業(yè)務(wù)流模型的時(shí)延性能分析

針對同一業(yè)務(wù)存在多種DAG業(yè)務(wù)流形式的內(nèi)在結(jié)構(gòu),不同結(jié)構(gòu)對分布式路徑計(jì)算方案的時(shí)延性能會(huì)產(chǎn)生不同的影響,本小節(jié)旨在分析圖3中所提3種異構(gòu)的業(yè)務(wù)流模型映射到霧網(wǎng)絡(luò)拓?fù)渲械臅r(shí)延性能差別。設(shè)置各霧映射節(jié)點(diǎn)的業(yè)務(wù)計(jì)算復(fù)雜度一致,不同數(shù)據(jù)量下3種DAG結(jié)構(gòu)的時(shí)延比例如圖8所示。

(a)2 Mb (b)5 Mb

從圖8可以看出:不同數(shù)據(jù)量下的端到端時(shí)延情況基本一致;3種結(jié)構(gòu)中并行結(jié)構(gòu)的時(shí)延占比最小,約為5.0%;串行結(jié)構(gòu)的時(shí)延占比最大,約為76.0%;串并結(jié)構(gòu)的時(shí)延占比居中,約為18.7%。這是因?yàn)椴煌Y(jié)構(gòu)的DAG業(yè)務(wù)流模型卸載到固定的網(wǎng)絡(luò)邊緣節(jié)點(diǎn)上分步驟處理業(yè)務(wù)數(shù)據(jù),業(yè)務(wù)完成所花費(fèi)的時(shí)間是霧映射起始節(jié)點(diǎn)到霧映射終止節(jié)點(diǎn)的最大累積時(shí)延。從圖3可知,本文采用的串行業(yè)務(wù)流、并行業(yè)務(wù)流以及串并業(yè)務(wù)流的最大累積時(shí)延由任意分支路徑下的最大業(yè)務(wù)數(shù)目確定,分別為6、5、3。由于同一時(shí)間段處理的業(yè)務(wù)數(shù)目越多,時(shí)延累積權(quán)重越大,故對于同一業(yè)務(wù)的3種異構(gòu)DAG模型,并行結(jié)構(gòu)下用戶體驗(yàn)的最好,串行結(jié)構(gòu)欠佳。

3.2.4 業(yè)務(wù)處理時(shí)延與霧節(jié)點(diǎn)負(fù)載方案的相關(guān)性

為避免出現(xiàn)部分霧映射節(jié)點(diǎn)因過載故障或過低負(fù)載導(dǎo)致的資源浪費(fèi)問題,本小節(jié)研究數(shù)據(jù)量和計(jì)算復(fù)雜度負(fù)載分配關(guān)系對業(yè)務(wù)處理總時(shí)延的影響,DAG業(yè)務(wù)流模型同樣僅采用圖3的并行結(jié)構(gòu),將此DAG模型中的子業(yè)務(wù)集合劃分為前端業(yè)務(wù)、中端業(yè)務(wù)以及后端業(yè)務(wù)。前端業(yè)務(wù)有q1、q2、q3,中端業(yè)務(wù)有q4、q5,后端業(yè)務(wù)有q6、q7、q8。4種前中后端業(yè)務(wù)處理數(shù)據(jù)量和復(fù)雜度的負(fù)載分配關(guān)系為1∶2∶3、2∶2∶2、3∶2∶1、1.5∶3∶1.5,分別用A、B、C、D表示,并設(shè)置總業(yè)務(wù)處理數(shù)據(jù)量為15 Mb,總計(jì)算復(fù)雜度為1 900。

數(shù)據(jù)量和計(jì)算復(fù)雜度分配比例對總時(shí)延的影響如圖9所示。可以看出:當(dāng)節(jié)點(diǎn)數(shù)據(jù)量負(fù)載分別固定為A、B、D方案時(shí),復(fù)雜度分配中A、B、C、D方案的時(shí)延依次增大;當(dāng)節(jié)點(diǎn)數(shù)據(jù)量的負(fù)載分配比例為C時(shí),復(fù)雜度分配方案中A的時(shí)延性能優(yōu)于其他分配比例,C的時(shí)延性能弱于其他比例關(guān)系,且A至C的時(shí)延增長為2.06 s。此外,節(jié)點(diǎn)復(fù)雜度分配方案固定時(shí),不同數(shù)據(jù)量分配下A方案時(shí)延最小。綜合考慮可知,數(shù)據(jù)量和計(jì)算復(fù)雜度的分配關(guān)系都為A時(shí),時(shí)延性能達(dá)到最優(yōu),約1.44 s,兩者都為C時(shí)的時(shí)延性能最差,約3.78 s,所以基于4種比例關(guān)系中最大時(shí)延差距約2.34 s。依此結(jié)果推斷,前端業(yè)務(wù)節(jié)點(diǎn)分配的數(shù)據(jù)量負(fù)載少或復(fù)雜度較低時(shí),業(yè)務(wù)處理時(shí)延有明顯改善。因此,本文任務(wù)映射策略在業(yè)務(wù)前簡單、后復(fù)雜和數(shù)據(jù)量前縮后放方案下有良好的負(fù)載均衡性能。

圖9 數(shù)據(jù)量和計(jì)算復(fù)雜度分配比例對總時(shí)延的影響Fig.9 Impact of data volume and computational complexity allocation ratio on total latency

3.2.5 NBPSO算法與其他算法的時(shí)延性能對比

本小節(jié)將NBPSO算法同隨機(jī)動(dòng)態(tài)算法(Pick-KX)、加權(quán)輪轉(zhuǎn)法(WRR)以及貪婪算法(Greedy-LB)的時(shí)延容忍度比較,從而驗(yàn)證該算法在分布式路徑計(jì)算方案中良好的時(shí)效性。采用并行的DAG業(yè)務(wù)流模型,NBPSO算法與其他算法的時(shí)延性能對比如圖10所示。

從圖10可以看出,NBPSO算法的平均時(shí)延容忍度均低于其他3種算法的。顯然,這4種算法在數(shù)據(jù)量和計(jì)算復(fù)雜度影響下的整體變化趨勢一致,在任意平均計(jì)算復(fù)雜度下,NBPSO算法與其他3種算法的時(shí)延差距隨著數(shù)據(jù)量的增長而增大。同樣地,不同數(shù)據(jù)量下,當(dāng)平均計(jì)算復(fù)雜度從1.6η逐漸減少至0.6η時(shí),兩者之間的時(shí)延寬度也相應(yīng)變窄,由此表明NBPSO算法的時(shí)延性能優(yōu)于其他3種算法的。分析圖10可知,在業(yè)務(wù)量為12 Mb、復(fù)雜度為0.6η時(shí),NBPSO算法的時(shí)延為1.34 s,較Greedy-LB、WRR、Pick-KX算法的時(shí)延分別降低了25.2%、46.3%、53.4%。

研究分析可知,Pick-KX算法隨機(jī)選擇若干個(gè)邊緣網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行業(yè)務(wù)映射,并沒有將節(jié)點(diǎn)的計(jì)算能力考慮在內(nèi);WRR算法和Greedy-LB算法雖然都參照了節(jié)點(diǎn)的計(jì)算能力,且Greedy-LB算法優(yōu)先選擇當(dāng)前局部負(fù)載最小的節(jié)點(diǎn),但兩者均未考慮網(wǎng)絡(luò)邊數(shù)據(jù)傳輸速率低帶來的高通信消耗問題,依然達(dá)不到時(shí)效性能最好。本文采取的NBPSO算法全面地研究了節(jié)點(diǎn)的計(jì)算能力和網(wǎng)絡(luò)邊的數(shù)據(jù)傳輸速率。

4 結(jié)束語

本文提出的基于云霧網(wǎng)絡(luò)架構(gòu)的分布式任務(wù)映射策略具備優(yōu)越的傳輸性能,有效改善了車聯(lián)網(wǎng)新興大數(shù)據(jù)任務(wù)的低時(shí)延問題。但是,本文提出的計(jì)算方案只能在靜態(tài)網(wǎng)絡(luò)邊緣設(shè)備中應(yīng)用,沒有切實(shí)考慮映射節(jié)點(diǎn)故障的服務(wù)遷移問題。而且,車輛應(yīng)用服務(wù)的多樣性決定了DAG業(yè)務(wù)流模型并不固定,若不同服務(wù)同時(shí)映射到相同霧網(wǎng)絡(luò)拓?fù)涮幚頃r(shí),則需考慮多業(yè)務(wù)在相同或不同時(shí)間下的執(zhí)行優(yōu)先級問題。因此,未來的研究方向應(yīng)該從靜態(tài)節(jié)點(diǎn)計(jì)算轉(zhuǎn)移到移動(dòng)車輛協(xié)同計(jì)算、故障轉(zhuǎn)移提高可靠性能、多業(yè)務(wù)并發(fā)或按時(shí)間順序卸載等方面。