基于移動邊緣計算的GI/GI/1 排隊建模與調度算法

張 珂 張利國

車聯網技術能夠實現車與車、車與路、車與基礎設施的信息交換,但對系統的實時性要求較高[1?4].如果采用集中式的數據處理模式,即數據回傳數據中心進行計算處理,則會產生較大時延.

最近興起的邊緣計算(Edge computing,EC)融合了網絡、計算、存儲等核心使能,分布式部署于靠近物或數據源頭,是就近提供應用服務的新型計算模型[5?9].車聯網中的邊緣計算[10]主要是基于路側單元(Road side units,RSU)進行的.將邊緣計算服務器直接部署于道路兩側,可以將更多的數據計算和存儲從“數據中心”轉移到“路側單元”,部分數據不必再經過網絡上傳云端處理,而在本地完成數據交換及自主決策.從而降低了網絡時延和負荷,有效減少網絡傳輸量,避免網絡擁塞,同時也提升了數據安全性和應用可靠性.然而,一方面由于車輛的移動特點,車載單元將頻繁與不同的路側單元進行信息交互,路側單元間也頻繁地轉移計算任務,密集信息交互帶來了不穩定性[11?13],降低了任務傳輸的可靠性與安全性[14];另一方面交通波動導致任務不均衡[15],路側單元部署規模大、成本高,有些路段可能沒有部署邊緣計算服務器卻有較大的邊緣計算需求.邊緣計算任務的空間分布是不確定的,固定在路側單元的邊緣計算服務器無法對一些指定地點和時間的任務提供服務[16],如何實現邊緣計算服務器的空間優化配置成為了一項重要工作.

智能車的快速發展為上述問題提供了全新的解決思路.它們通常裝備了大量的計算單元、通信設備、傳感器和人機交互設備[17?20].例如,百度的無人駕駛汽車“阿波羅”裝載了價值近百萬元的計算機系統進行存儲和運算,用來分析車輛周邊人、車、道路與環境[21?22].此外,在智能車與其他車輛行駛中將形成相對靜止關系,此時提供移動邊緣計算(Mobile edge computing,MEC)將有效提升實時性與穩定性[23?26].

本文提出一種車聯網環境下的MEC 架構.與基于路側單元的邊緣計算相比,此類MEC 范式最大的不同之處在于:其依賴于具有感知、計算、控制、通信能力的智能車在交通路網中提供彈性的邊緣計算服務[27?31];智能車作為分布式MEC 節點,執行局部、實時、短周期數據的處理與分析.

本文重點研究了MEC 節點形成的移動拓撲結構,按照計算需求的時間和空間約束進行計算任務的時空化研究,建立了基于GI/GI/1 排隊模型的虛擬車任務隊列.根據任務到達時間、任務地點、任務量等研究任務分配問題,利用虛擬化概念最大化智能車的利用程度,提出了基于云平臺Voronoi 的任務分配算法.針對智能車局部任務隊列,引入虛擬服務時間、虛擬截止時間對任務執行模型進行約束.最后以城市道路交通污染排放的實時計算為例,討論了分布式移動邊緣計算方法的有效性.

本文結構如下:第1 節介紹了車聯網環境下的MEC 體系架構和任務分配算法;第2 節建立了MEC 系統模型;第3 節介紹了道路交通污染排放計算任務;第4 節進行了仿真實驗分析;第5 節總結與展望.

1 車聯網環境下的MEC 體系架構

本節設計了如圖1 所示的車聯網環境下時空采樣計算的MEC 體系架構.

圖1 車聯網環境下的MEC 體系架構Fig.1 The MEC architecture for vehicle networks

該體系架構分為三層:物理層、應用層、云端層.物理層由道路車輛形成的車聯網組成,通過短程通信技術進行信息交換.應用層由部署在城市交通路網中的智能車組成,數據處理和交通信息計算服務部署于智能車上進行.云端層擁有更多的計算和存儲資源,智能車動態感知交通信息后,通過云端的邊緣接入上傳自身信息與交通信息,云端利用移動拓撲結構對智能車進行調度.

假設交通路網中有M輛具有車載邊緣計算服務器的智能車提供分布式服務,記作

集合中下標表示智能車的編號,所有智能車在路網中形成了移動拓撲結構,而每輛智能車負責一個子區的計算任務.由于智能車可以在交通路網中移動,因而車載服務器具有空間屬性和速度屬性.

為實現多用戶可以獨立使用智能車而互相不受影響,應用云計算范式對智能車進行虛擬化,則用戶可在云端購買虛擬車(Virtual vehicles,VV),以此獲得智能車的某些計算或控制服務,該虛擬車反映了智能車的空間屬性和速度屬性.記用戶購買的I輛虛擬車集合

集合中下標表示虛擬車的編號.對于用戶而言,事先并不知道智能車的分布情況,只需要在云端購買一輛虛擬車,指定特定地點的計算任務即可.特定地點的計算任務通常可以表示為

其中,Tarr表示任務到達時間;taskX表示任務在空間中的位置,可以用經緯度(lat,lon)表示;Ts表示任務量.

在多任務情況下,虛擬車必須完全隔離,因此需要對虛擬車進行時空建模,描述其在時間和空間上的計算行為.

邊緣計算中的核心使能技術是虛擬化,通過虛擬化技術將物理層的CPU、內存、傳感器等硬件資源映射到虛擬層上,用戶任務通過虛擬車的時空推進程序,利用智能車的傳感器、計算資源、控制器、通信設備與周圍環境進行交互.則虛擬車任務可以看成一種離散的時空推進模型,這里引入Plotkin符號語義[32]如下

其中,tci為任務程序,例如采樣其他車輛信息并做交通污染估計;t1,t1+k,···,t1+(i ?1)k,···為時鐘序列,時間間隔為k; 箭頭表示的流是時空推進;x1,x1+n,···,x1+ (i ?1)n,···為空間序列,空間間隔為n.

當n0 時,表示時間上推進而空間上沒有推進,此時虛擬車處于靜止狀態,可以表示為

此時虛擬車可以在某一位置提供MEC 服務.

同樣,有些空間工程采樣并不需要時間參考,此時虛擬車僅在空間上推進,其空間推進模型可以表示為

利用時空推進模型可以指定智能車的行為,為保證MEC 云平臺的調度系統能夠快速響應,需要進行MEC 調度系統建模.

2 MEC 系統模型

MEC 中資源調度的實質是根據虛擬車產生的不同計算任務、任務到達時間、任務類型等,云端調度系統選擇合適的智能車前往特定地點執行計算任務,為此需要研究調度模型以最大化利用智能車資源.在MEC 中已經實現了資源的虛擬化.本節將進行MEC 系統建模.

2.1 虛擬車任務隊列模型

事實上,虛擬服務時間與物理世界中的智能車服務時間會有偏差,因此設定虛擬截止時間作為對智能車的約束.而虛擬截止時間的計算是以任務到達時間算起,如果第j次任務到達時上次任務仍在進行中,則應當以第j ?1 次任務的虛擬截止時間算起,兩種任務虛擬截止時間計算情況如圖2所示.

圖2 虛擬車任務虛擬截止時間計算示意圖Fig.2 Virtual vehicle task's deadline time calculation schematic diagram

2.2 云平臺調度模型

MEC 調度系統中有M輛智能車運行在路網中,虛擬車產生的每個特定地點計算任務都需要由實體的智能車來完成,也就是計算任務Taski(j) 按照某種分配機制分配給智能車中的某輛車去執行.從第2.1 節可知,在時變環境中,虛擬車產生的計算任務是一個排隊過程,是有時間限制的.為了更高效地提供計算服務,最小化任務的預期系統時間,本節采用分布式自適應策略,引入一種Voronoi 分配算法來解決該問題.

式中,VorAllocation 為分配算法函數,該函數接受三個參數;A為智能車覆蓋的服務區域,包含A區域交通路網中的node 節點和edge 邊的數據信息;是t時刻第i輛虛擬車到達任務的位置;pIV(t)是t時刻智能車的地理位置;r∈{1,···,M}表示分配的智能車編號.

根據A區域中有M輛智能車,Voronoi 分配算法利用連續多中值均勻產生的M個點將A區域細分為M個子區域,每個子區域是一個Voronoi 單元,則輛智能車分別被派到M個子區域中的中值點等待計算任務分配.此時M個中值點即為智能車的初始位置則Voronoi 單元表示如下

2.3 智能車局部隊列模型

在實際任務執行中,虛擬服務時間與物理世界中的智能車服務時間會有偏差.智能車利用排隊論的調度策略,包括先到先服務(First come first service,FCFS),即最先到達隊列的任務最先進行服務;最早截止優先服務(First deadline first service,FDFS),即按照截止時間先后順序重新進行排序,依次進行服務;信用優先服務(Credit first service,CFS),將信用分為2、4、6、8、10 五個等級,按照優先級大的依次進行服務.通過對比,按照時間最優的策略執行任務,令 Φ 表示調度策略,則有

其中,φ為集合中的調度策略.定義為在使用調度策略后的第n?1次任務和第n次任務間的旅行距離,則可計算出智能車實際的旅行時間,記為

式中,φoptimal表示最優策略,智能車將按照該調度策略執行任務.記智能車實際完成任務的服務速率一般項為μIV,則有

式中,μIV表示智能車服務速率,μVV表示虛擬車服務速率.若κ接近1,說明智能車與虛擬車服務速率匹配;若κ較大,則說明智能車的服務速率較差.

由此可以得到如圖3 所示的任務隊列調度模型圖,一個調度模型通常由輸入任務、調度決策、任務執行體組成.已知虛擬車產生的任務到達速率以及Voronoi 分配算法,則其調度流程如下.

圖3 基于Voronoi 分配算法的任務隊列調度模型圖Fig.3 Task queue scheduling model diagram based on Voronoi allocation algorithm

1) 輸入任務:MEC 資源池中的各個任務相互獨立,并且各個任務到達速率為即單位時間間隔內有個任務到達.所有虛擬車的任務到達云平臺調度中心構成全局任務隊列.

2) 調度決策:任務到達云平臺調度中心后,根據Voronoi 分配算法,判斷各個任務地點落入哪一Voronoi 單元,然后將該任務分配給該單元內的智能車,即

3) 任務執行體:同一虛擬車的任務落入不同的Voronoi 單元,將由不同的智能車進行計算服務,所以M輛智能車都有自己的局部任務隊列.智能車將按照局部調度策略對任務隊列進行任務排序,依次對指定地點執行MEC 任務,并在時間期限內完成計算任務.

3 道路交通污染排放計算

隨著電動車、機動車、混合動力車等多能源結構汽車上路,將呈現出混合交通流的趨勢.原來利用宏觀交通流數據作機動車尾氣排放計算的方法已不再適用,而交通管理部門對準確反映且靈活地獲取某一地點的交通污染排放情況有著強烈的需求.

為完成混合交通流下的移動交通污染排放計算任務,本文提出將VSP (Vehicle specific power)模型部署在智能車上.即交管部門提交計算任務地點與計算量后,系統根據任務地點落入哪一Voronoi單元而將任務分配給該單元內的智能車,智能車利用短程通信技術與指定路段的車輛建立通信,發起信息獲取請求,收集道路上車輛類型、運行數據,利用VSP 模型執行交通污染排放的動態測算任務.

VSP 理論的物理意義是瞬態機動車輸出功率與機動車質量的比值,與車輛的瞬態排放具有較強的相關性,能夠評價以秒為單位的瞬間排放量.不同的機動車類型具有不同的VSP 計算公式,根據已有研究,我國城市小型轎車的交通污染排放可以簡化為由速度、加速度和坡度組成的VSP 表達式,如式(22)所示

商務車VSP 的計算公式,如式(23)所示

式中,v為機動車瞬時速度(m/s);a為機動車瞬時加速度(m/s2);grade為道路坡度,當機動車在城市道路中行駛時道路坡度取0.

從式(22)、式(23)可以看出,想要計算一輛機動車的VSP 值需要獲取車輛類型、瞬時速度、瞬時加速度等參數,而車輛移動傳感技術 (如GPS、陀螺儀、加速度計等微傳感器) 迅猛發展使得獲取這些參數成為可能.智能車獲得該路段內的車輛類型、速度、加速度、坡度等信息后,根據VSP 計算公式得到每輛車的VSP 值,結合BIN方法便能夠對排放因子進行分析計算,對照VSP BIN 表1 即可獲得不同類型的機動車瞬時排放量.將該路段的車輛瞬時排放進行累加便可得到路段的交通污染排放水平.

表1 VSP 排放等級與平均排放清單Table 1 VSP modes and the average modal emission rates of each

本節提出利用智能車MEC 技術前往指定路段執行交通污染排放計算任務,為了驗證系統的有效性和任務流程的可行性,將進行仿真實驗進行相應的實驗驗證.

4 仿真實驗

本文在Eclipse 中搭建仿真項目,部署調度模型算法,驗證系統模型的有效性.并在仿真軟件Aimsun 中進行交通污染排放計算任務調度實驗,建立仿真地圖、路網、交通路況等.通過Aimsun API 接口編寫算法控制智能車前往指定地點執行任務,記錄各階段時間,最后進行分析.

在Eclipse 工程實驗中,我們設計了如圖4 所示的MEC 調度系統仿真模式類圖,創建了VirtualVehicle,TaskData,GlobalQueue,Scheduler,IntelligentVehicle 5 個類,從而建立了運行時仿真環境.其中VirtualVehicle 可以創建多個線程實例,按照設定的到達規律生成任務TaskData,這里時間間隔由sleep (InterArrivalTime) 函數實現.TaskData 作為容器將保存虛擬車生成的任務信息.在運行時環境下,VirtualVehicle 將生成Task-Data 任務對象保存到自己的隊列中,并發送到全局隊列,全局隊列由ArrayBlockingQueue 實現.可以實現VirtualVehicle 和Scheduler 的互斥操作,保證全局隊列中數據的安全性.全局隊列的大小是動態變化的,Scheduler 可以從全局隊列中取出任務并按照任務地點落入Voronoi 單元的編號將任務對象發送給對應的IntelligentVehicle.GlobalQueue和Scheduler 在此承擔了信息通道(Channel)的作用,IntelligentVehicle 擁有本地調度器,將根據不同的調度規則計算服務總時間,并得到最優的調度策略.

圖4 MEC 調度系統仿真模式類圖Fig.4 Simulation mode class diagram of MEC scheduling system

算法操作步驟如下:

1) 設定虛擬車數量i和智能車數量m;

2) 設定全局任務隊列閾值;

3) 實例化i個VirtualVehicle 線程實例V Vi,m個IntelligentVehicle 線程實例IVm;

4) 設定V Vi產生任務的時間到達規律參數、任務地點范圍、任務量及范圍;

5)V Vi生成任務,TaskData 存儲任務的到達時間、地理位置、任務量;

6) 按照式(9)計算虛擬服務時間;

7) 按照式(10)計算虛擬截止時間;

8)V Vi將任務打包發送到Channel 通道中的全局任務隊列;

9) 調度器Scheduler 從全局任務隊列取出任務,按照式(14)、式(15)將任務分配到對應的智能車IVm;

10) 智能車IVm將接收到的任務放入自己的局部隊列,按照式(16)調度策略及式(17)～式(19)分別計算

11) 重復步驟4) 至步驟10),直至達到額定任務數量,求得服務總時間最小的調度策略φoptimal.

實驗調用API 從Open Street Map 獲取以北京工業大學為中心,方圓3 000 米范圍的交通路網拓撲圖作為實驗區域數據.任務處理過程中的其中6 個任務分配結果如圖5 所示,最底層是交通路網,9 個方塊表示在A區域內提供邊緣計算的智能車,圓點表示虛擬車發出的計算任務位置,通過Voronoi 算法可以計算得到分界線,將該區域分成了9 個Voronoi 單元,區域索引與智能車索引相同.創建9個IntelligentVehicle 線程實例模擬9 輛智能車,隨機產生9 個均勻分布在路網中的地理位置坐標作為智能車初始位置坐標,如圖5(a)中的方塊所示.創建16 個VirtualVehicle 線程實例模擬16 輛虛擬車,每輛虛擬車都將按照不同的分布規律產生50個任務,任務被動態地發送到全局隊列.Scheduler 按照式(15)將該區域分成9 個Voronoi 單元,即逐個將全局隊列中的任務取出,按照Voronoi 分配算法進行分配.

圖5 基于Voronoi 算法的任務分配結果示意圖Fig.5 Allocation result based on Voronoi algorithm

智能車根據FCFS,FDFS,CFS 調度策略對局部任務隊列進行計算,得到各自最優的調度策略.在FCFS,FDFS,CFS 三種調度算法下的智能車服務時間對比結果如圖6 所示.

圖6 FCFS,FDFS,CFS 調度算法下智能車服務時間對比Fig.6 Service time comparison under scheduling algorithm of FCFS,FDFS,CFS

調度完成后在Aimsun 中模擬智能車提供交通污染排放計算服務的任務場景.利用OSMnx 庫可以獲取北京市朝陽區的交通路網GIS 數據,利用Aimsun 仿真軟件中的插件GIS Importer 將該數據導入Aimsun 生成路網,建立交通網絡.

選擇圖5 中的第5 輛智能車所在區域 (中間區域) 作為實驗區域,根據OD 矩陣將普通車輛放入仿真的真實場景中,然后放入智能車IV5作為控制對象.通過Aimsun API 編寫程序模擬IV執行任務,落入第5 單元區域的任務被IV生成局部任務序列其任務地點標注如圖7 中的圓點所示,智能車IV5初始位置如圖7 中車輛所示.

圖7 交通污染排放計算的智能車調度策略Fig.7 Intelligent vehicle scheduling strategy for traffic pollutant emission computing

仿真程序按照FCFS 調度策略執行任務.讀取第一個任務地點,智能車所在地點計算得到第一次執行任務地點與智能車初始位置之間的距離通過獲取路段平均車速可以計算出智能車到達任務點所在路段的實際旅行時間同理計算出智能車通過任務地點所在路段的時間,這段時間也是智能車執行任務時間,即

表2 VVs 的任務計算參數Table 2 VVs calculation parameters

執行交通污染排放計算任務時,采用Plotkin時空推進式(4),設置程序時間間隔為1 s,同時仿真步長設置成1 s.智能車可以獲得該路段所有車輛的動態信息,通過獲取不同車輛的瞬時速度v和加速度a,利用VSP 模型可以得到每輛車的VSP值,根據BIN 方法得到每輛車的瞬時排放,將計算得到的所有值進行累加得到該路段的整體交通污染排放情況.在此過程中,智能車的實際運行參數以及在每次任務中計算得到的交通污染排放情況如表3所示.

表3 IV 的實際運行參數Table 3 Actual operating parameters of IV

由式(7)、式(11)可知,任務到達速率λVV0.375,虛擬服務速率μVV0.448,此時λVV <μVV.經計算得到智能車真實服務速率μIV0.476,通過式(21)得到κ1.0625,接近1.由文獻[29]可知映射程度較好,提高了智能車的計算資源利用率.

5 結論

本文設計了一種智能車聯網環境下的MEC 體系架構.采用虛擬化技術對智能車計算資源進行了虛擬化抽象,構建了虛擬車服務任務的GI/GI/1 排隊模型,同時基于云平臺的Voronoi 分配算法,對虛擬車任務進行了分配綁定,進而實現了智能車的優化調度與分布式彈性服務,解決了邊緣計算任務分配不均衡問題.下一步,一個重要的研究方向是討論MEC 優化調度任務的實時性.