田一博,沈 航,白光偉,王天荊

(南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211816)

0 引 言

車聯(lián)網(wǎng)(Internet of Vehicles,IoV)基于車用無線通信技術(shù),將車輛、路邊單元(Road-Side-Unit,RSU)、基站和服務(wù)提供商連接為一個(gè)有機(jī)的整體,實(shí)現(xiàn)全方信息實(shí)時(shí)共享[1].車載用戶可以獲得自動(dòng)駕駛、路徑規(guī)劃、碰撞預(yù)警、車載娛樂、高清地圖下載等服務(wù)[2].一般而言,車輛搭載的計(jì)算設(shè)備能力有限.車聯(lián)網(wǎng)中有許多對(duì)延遲敏感的計(jì)算任務(wù),若任務(wù)被卸載至遠(yuǎn)端的云服務(wù)器,遠(yuǎn)程傳輸和處理帶來的高延遲對(duì)延遲敏感型任務(wù)而言是無法接受的[3].移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)[4]將數(shù)據(jù)處理從云端轉(zhuǎn)移到網(wǎng)絡(luò)邊緣設(shè)備中,終端設(shè)備產(chǎn)生的任務(wù)交由邊緣設(shè)備處理,有效降低傳輸過程中產(chǎn)生的延遲.車輛大部分時(shí)間處于高速移動(dòng)狀態(tài),任務(wù)發(fā)布在時(shí)間和空間上分布不均勻.邊緣網(wǎng)絡(luò)資源有限,很難為車載用戶提供穩(wěn)定的服務(wù)質(zhì)量(Quality-of-Service,QoS)保證[5].車聯(lián)網(wǎng)用戶常同時(shí)處于多個(gè)基站的覆蓋范圍內(nèi),如何為任務(wù)選擇最優(yōu)卸載目的地也是一個(gè)挑戰(zhàn)性問題.

網(wǎng)絡(luò)切片[6]是一種對(duì)網(wǎng)絡(luò)架構(gòu)和服務(wù)模式的重要革新技術(shù).通過將物理無線接入網(wǎng)(Radio Access Network,RAN)劃分為多個(gè)邏輯獨(dú)立的虛擬網(wǎng)絡(luò)(即:切片),多個(gè)運(yùn)營商可以共享同一物理網(wǎng)絡(luò)的資源,從而提升網(wǎng)管靈活度,減少基礎(chǔ)設(shè)施支出和運(yùn)營成本.網(wǎng)絡(luò)功能虛擬化(Network Functions Virtualization,NFV)[7]和軟件定義網(wǎng)絡(luò)(Software-Defined Networking,SDN)[8]是網(wǎng)絡(luò)切片的支撐技術(shù).在RAN側(cè),基站功能包括無線接入和處理等,用于創(chuàng)建無線連接并分配資源.在無線NFV中,無線接入等功能以軟件實(shí)例形式運(yùn)行在基站上,由一個(gè)集中式的控制器進(jìn)行管理.通過采集終端請(qǐng)求信息,控制器根據(jù)QoS需求創(chuàng)建切片并依據(jù)網(wǎng)絡(luò)實(shí)時(shí)流量或拓?fù)湫畔⒄{(diào)度網(wǎng)絡(luò)切片資源.

由于多種類型任務(wù)并存,車聯(lián)網(wǎng)任務(wù)卸載對(duì)網(wǎng)絡(luò)切片技術(shù)有天然的依賴.RAN切片可以為車載用戶不同類型任務(wù)的卸載提供差異化的QoS保證[9].然而,邊緣網(wǎng)絡(luò)設(shè)備中的頻譜和計(jì)算資源有限,使得任務(wù)卸載策略與切片劃分策略呈相互耦合的關(guān)系.另一方面,車聯(lián)網(wǎng)用戶常處于高速移動(dòng)狀態(tài),而單個(gè)基站的覆蓋范圍有限,任務(wù)難以在延遲要求內(nèi)處理完成.協(xié)同多個(gè)基站的資源為同一用戶提供服務(wù)可以解決這一難題,但車輛與基站的關(guān)聯(lián)(association)選擇也成為一項(xiàng)關(guān)鍵且具有挑戰(zhàn)性的問題.

針對(duì)上述挑戰(zhàn)性問題,本文提出面向車聯(lián)網(wǎng)的RAN切片和任務(wù)卸載聯(lián)合優(yōu)化框架,目的是在滿足車輛應(yīng)用任務(wù)卸載延遲需求的基礎(chǔ)上最大化任務(wù)完成率.主要貢獻(xiàn)包括:

1) 提出一種面向服務(wù)的動(dòng)態(tài)RAN切片框架,在大時(shí)間尺度上進(jìn)行資源切片,在小時(shí)間尺度上進(jìn)行任務(wù)調(diào)度,為不同類型的任務(wù)卸載提供差異化QoS保證.基于排隊(duì)模型,RAN切片和任務(wù)卸載聯(lián)合優(yōu)化被建模為一個(gè)耦合約束和資源約束下的最大化長期任務(wù)完成數(shù)的聯(lián)合優(yōu)化問題.

2) 將聯(lián)合優(yōu)化問題進(jìn)一步解耦為RAN切片和任務(wù)調(diào)度兩個(gè)子問題.對(duì)于前者,設(shè)計(jì)一種最優(yōu)化方法,以切片窗口為周期,為RAN切片分配頻譜和計(jì)算資源.對(duì)于后者,設(shè)計(jì)基于深度強(qiáng)化學(xué)習(xí)的算法,解決小時(shí)間尺度下的在線任務(wù)調(diào)度,以適應(yīng)車輛的高速移動(dòng)性和均衡基站負(fù)載.該算法綜合考慮車輛行駛速度和方向,允許任務(wù)的接收和處理分別被不同的基站執(zhí)行.仿真結(jié)果表明,相比現(xiàn)有的方案,本文方案可以顯著提高資源利用率和任務(wù)成果完成率.

本文的剩余部分安排如下:第1節(jié)介紹和本文相關(guān)的研究工作;第2節(jié)對(duì)所提出的系統(tǒng)模型進(jìn)行詳細(xì)描述;第3節(jié)將RAN資源切片和任務(wù)調(diào)度構(gòu)建為一個(gè)帶約束的隨機(jī)優(yōu)化問題;第4節(jié)將隨機(jī)優(yōu)化問題解耦為RAN切片子問題和任務(wù)調(diào)度子問題,并提出一種基于深度強(qiáng)化學(xué)習(xí)的調(diào)度決策算法;第5節(jié)介紹實(shí)驗(yàn)的參數(shù)設(shè)置和仿真結(jié)果;最后對(duì)全文進(jìn)行總結(jié),并指出未來的研究方向.

1 相關(guān)工作

由于車聯(lián)網(wǎng)場(chǎng)景下的任務(wù)常具有高時(shí)延敏感性的特性,任務(wù)卸載效果在很大程度上依賴車輛-基站關(guān)聯(lián)模式.盧旭等人[10]提出了一種基于云邊協(xié)同的計(jì)算卸載網(wǎng)絡(luò)模型,通過對(duì)服務(wù)應(yīng)用進(jìn)行分類,設(shè)計(jì)了一種基于車聯(lián)網(wǎng)的自適應(yīng)邊緣卸載策略,并提出一種基于多目標(biāo)免疫算法實(shí)現(xiàn)卸載時(shí)延、車載終端消耗的多目標(biāo)優(yōu)化.朱思峰等人[11]提出異構(gòu)無線網(wǎng)絡(luò)下行資源切片框架,為機(jī)器類型設(shè)備和移動(dòng)用戶設(shè)備提供差異化QoS保障.該方案利用迭代優(yōu)化方法解決資源分配和設(shè)備接入選擇聯(lián)合決策問題,旨在最大化網(wǎng)絡(luò)效用.許小龍等人[12]提出一種“端-邊-云”協(xié)同的車聯(lián)網(wǎng)邊緣計(jì)算系統(tǒng)模型,并針對(duì)該模型設(shè)計(jì)了基于深度學(xué)習(xí)的分布式服務(wù)卸載方法.該方案通過輸入網(wǎng)絡(luò)環(huán)境中的系統(tǒng)狀態(tài),獲取服務(wù)的卸載策略.Dai等人[13]研究了一種基于MEC的汽車眾包服務(wù)場(chǎng)景,通過聯(lián)合優(yōu)化卸載決策和帶寬資源分配對(duì)車輛感知到的交通數(shù)據(jù)進(jìn)行調(diào)度.該方案設(shè)計(jì)了一種異步深度Q學(xué)習(xí)算法確定卸載決策.總體而言,在動(dòng)態(tài)變化的車聯(lián)網(wǎng)環(huán)境下,傳統(tǒng)的啟發(fā)式算法也可以為車載用戶提供差異化服務(wù),但取得的效果有限.而深度學(xué)習(xí)的應(yīng)用較好地解決了車聯(lián)網(wǎng)環(huán)境多變,任務(wù)信息復(fù)雜的問題.

RAN切片的資源分配也會(huì)影響任務(wù)卸載效果.自動(dòng)駕駛?cè)蝿?wù)往往具有差異化QoS的特性.如果無線電資源的分配無法滿足任務(wù)傳輸速率、時(shí)延或可靠性的要求,則可能無法實(shí)現(xiàn)計(jì)算的負(fù)載均衡.Omar等人[14]研究了車輛網(wǎng)絡(luò)協(xié)同計(jì)算卸載的聯(lián)合通信和計(jì)算時(shí)間分配問題,將任務(wù)卸載資源、本地任務(wù)執(zhí)行資源和車輛輔助任務(wù)遷移資源進(jìn)行聯(lián)合優(yōu)化,以實(shí)現(xiàn)任務(wù)計(jì)算的整體最大可靠性.Xu等人[15]針對(duì)計(jì)算任務(wù)的卸載目的地選擇問題,設(shè)計(jì)了一種適用于邊緣計(jì)算的自適應(yīng)計(jì)算卸載方法,優(yōu)化邊緣計(jì)算系統(tǒng)的任務(wù)卸載延遲和資源利用.劉雷等人[16]針對(duì)車聯(lián)網(wǎng)環(huán)境下有限的網(wǎng)絡(luò)資源和大量用戶需求之間的矛盾,設(shè)計(jì)了任務(wù)卸載和服務(wù)緩存的聯(lián)合優(yōu)化機(jī)制.利用異步分布式智能優(yōu)化算法,得到最優(yōu)卸載決策和資源管理方案.

與低移動(dòng)性場(chǎng)景下的任務(wù)卸載不同,面向車聯(lián)網(wǎng)的任務(wù)卸載需要考慮到用戶的高速移動(dòng)性帶來的影響.這驅(qū)使本文研究一種深度強(qiáng)化學(xué)習(xí)輔助的,基于RAN切片的協(xié)作式任務(wù)卸載方法,在動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境中,找到最優(yōu)的任務(wù)卸載方案,為車輛任務(wù)卸載提供差異化的QoS保證.

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)場(chǎng)景和假設(shè)

如圖1所示,考慮一個(gè)MEC輔助的車聯(lián)網(wǎng)場(chǎng)景,其中包含地面基站、車輛和基于MEC的控制器.車輛和地面基站的集合分別被表示為{I,J}.控制器和基站通過有線連接.作為邊緣網(wǎng)絡(luò)的計(jì)算中心,控制器可以降低車輛獲得服務(wù)的時(shí)延,提高服務(wù)效率.在基站覆蓋范圍內(nèi)的所有車載任務(wù)都可以通過基站卸載到控制器進(jìn)行調(diào)度.控制器根據(jù)網(wǎng)絡(luò)環(huán)境實(shí)時(shí)分配任務(wù),并交由合適的基站處理.基站接收到任務(wù)后,按任務(wù)的需求,延遲約束等信息為其分配物理資源并進(jìn)行處理.最后,基站將處理結(jié)果傳回車輛.

圖1 MEC輔助車聯(lián)網(wǎng)場(chǎng)景Fig.1 MEC assisted internet of vehicles

即使同時(shí)處于多個(gè)基站的覆蓋范圍內(nèi),車輛在同一時(shí)隙也只能關(guān)聯(lián)唯一的基站卸載任務(wù).

2.2 面向任務(wù)卸載服務(wù)的RAN切片框架

本文設(shè)計(jì)一種面向任務(wù)卸載服務(wù)的RAN切片框架,采用長短時(shí)協(xié)同優(yōu)化機(jī)制,以應(yīng)對(duì)網(wǎng)絡(luò)動(dòng)態(tài)性和任務(wù)流量的時(shí)空變化.如圖2所示,本文考慮兩類典型的車聯(lián)網(wǎng)任務(wù),即:延遲敏感型任務(wù)和延遲容忍型任務(wù).前者對(duì)應(yīng)智能汽車內(nèi)部控制指令[17]等,其延遲約束僅為50ms～1s;后者的典型應(yīng)用包括車載設(shè)備的高清地圖下載[18],延遲要求比較寬松.

圖2 多時(shí)間尺度面向任務(wù)卸載的RAN切片框架Fig.2 Multi-timescale task offloading oriented resource management framework

任務(wù)類型o=1(o=2)對(duì)應(yīng)延遲敏感(延遲容忍)型任務(wù).每個(gè)基站的物理資源(頻譜資源和計(jì)算資源)被劃分為2個(gè)面向任務(wù)卸載的RAN切片,即切片1和切片2,分別支持延遲敏感型任務(wù)和延遲容忍型任務(wù).基站j持有的頻譜資源和計(jì)算資源分別表示為cj和sj.基站j分配給切片o∈{1,2}的頻譜和計(jì)算資源數(shù)量表示為cj,o和sj,o.

考慮到車流量的時(shí)空變化,RAN資源的切分策略需要根據(jù)實(shí)際情況動(dòng)態(tài)調(diào)整.文中探索一種多時(shí)間尺度RAN切片框架,以支持具有差異化QoS需求的任務(wù)卸載.如圖2所示.時(shí)間被劃分為多個(gè)等長的切片窗口,每個(gè)切片窗口被劃分為等長的調(diào)度時(shí)隙.切片窗口w包含的調(diào)度時(shí)隙集合被定義為Tw.在切片窗口開始時(shí),控制器根據(jù)收集的歷史任務(wù)信息制定相應(yīng)的RAN切片方案.各個(gè)基站按照切片方案分配頻譜資源和計(jì)算資源.然后在小尺度的調(diào)度時(shí)隙t∈Tw內(nèi),即控制器對(duì)接收到的任務(wù)進(jìn)行調(diào)度;各個(gè)基站按照任務(wù)調(diào)度決策處理任務(wù);基站將任務(wù)的處理結(jié)果傳回車輛;基站將任務(wù)的數(shù)據(jù)上傳到控制器中.

2.3 通信模型

基站根據(jù)任務(wù)類型將同類切片中的資源以正交的形式分配給所關(guān)聯(lián)的車輛.在與基站傳輸?shù)倪^程中,車輛受到的干擾只來自其他基站的傳輸信號(hào).車輛i的發(fā)射功率被表示為Pi.基站j的發(fā)射功率被表示為Pj.定義σ2為平均背景噪聲.若基站j分配給車輛i產(chǎn)生的任務(wù)m的帶寬為ci,j,m,則車輛i向基站j提交任務(wù)m時(shí)的上行傳輸速率被計(jì)算為:

(1)

其中,j′代表基站集合中去除j的剩余基站.Gi,j代表車輛i與基站j之間的信道增益,計(jì)算參照文獻(xiàn)[19].

車輛接收基站的回傳結(jié)果時(shí),同樣只受到來自其他基站的干擾.因此,從基站j回傳任務(wù)m到車輛i的下行傳輸速率為:

(2)

2.4 協(xié)作式任務(wù)調(diào)度框架

針對(duì)車輛的高速移動(dòng)性,本文設(shè)計(jì)一種協(xié)作式的任務(wù)調(diào)度框架.從圖3可以看出,任務(wù)調(diào)度不再依賴單個(gè)基站,而是允許任務(wù)的卸載與處理在不同的基站執(zhí)行.每個(gè)基站包含兩個(gè)處理隊(duì)列,用以緩存采集到的延遲敏感型和延遲容忍型任務(wù).MEC控制器也包含與之對(duì)應(yīng)的兩個(gè)卸載隊(duì)列,用于緩存由基站采集來的兩類任務(wù).綜合多源信息,MEC控制器卸載隊(duì)列中的任務(wù)被轉(zhuǎn)交給不同的基站協(xié)作處理.

圖3 協(xié)作式任務(wù)調(diào)度框架Fig.3 Collaborative task scheduling framework

協(xié)作式任務(wù)調(diào)度需要綜合考慮車輛位置、速度、行駛方向和基站負(fù)載等因素.考慮到基站負(fù)載對(duì)處理延遲的影響,本文利用排隊(duì)論[20]刻畫基站處理任務(wù)的過程,并通過公式推導(dǎo)計(jì)算得到延遲敏感型和延遲容忍型任務(wù)的調(diào)度時(shí)延.

車輛i產(chǎn)生的任務(wù)m中包含任務(wù)的數(shù)據(jù)大小(bits)、所需計(jì)算資源數(shù)目和任務(wù)處理完成的延遲需求,分別被表示為εi,m,τi,m,di,m.下面基于排隊(duì)論建模任務(wù)卸載和處理延遲.

2.4.1 任務(wù)卸載延遲建模

任務(wù)卸載延遲代表任務(wù)從車輛上行由基站j卸載至控制器的時(shí)間.基站j采集到的類型為o的任務(wù)集合Mj,o的總元素個(gè)數(shù)被表示為Mj,o.在控制器覆蓋的區(qū)域內(nèi),請(qǐng)求類型為o的任務(wù)從車輛傳輸?shù)交镜钠骄鶗r(shí)間被量化為:

(3)

將單個(gè)車輛的任務(wù)到達(dá)建模為泊松過程,相應(yīng)地基站接收到的任務(wù)到達(dá)也建模為泊松過程.車輛i產(chǎn)生請(qǐng)求類型o任務(wù)的到達(dá)率被表示為λi,o.定義二元變量ai,j=1代表車輛i與基站j關(guān)聯(lián).也就是說,控制器卸載隊(duì)列中請(qǐng)求類型o任務(wù)的到達(dá)率可以表示為:

(4)

卸載隊(duì)列每次只處理一個(gè)任務(wù).任務(wù)的卸載過程被建模為M/M/1隊(duì)列模型.卸載隊(duì)列的進(jìn)隊(duì)由任務(wù)到達(dá)率決定,卸載隊(duì)列的出隊(duì)由基站傳輸決定.當(dāng)隊(duì)列的進(jìn)隊(duì)速率大于出隊(duì)速率時(shí),隊(duì)列中的任務(wù)會(huì)不斷累積導(dǎo)致隊(duì)列溢出.隊(duì)列以服務(wù)強(qiáng)度反映繁忙程度,定義基站j中請(qǐng)求類型為o的卸載隊(duì)列的服務(wù)強(qiáng)度[21]為:

(5)

為了保持卸載隊(duì)列的穩(wěn)定性(防止隊(duì)列溢出),公式(5)需要滿足:

(6)

任務(wù)m到達(dá)卸載隊(duì)列后,排在任務(wù)m前的任務(wù)索引集合表示為Ω(m).假設(shè)ζi,j,m代表由車輛i產(chǎn)生的任務(wù)m由基站j上載至控制器的時(shí)長.該任務(wù)的卸載延遲被計(jì)算為:

(7)

2.4.2 任務(wù)處理延遲建模

處理延遲指任務(wù)從控制器進(jìn)入基站處理隊(duì)列到任務(wù)被處理完所花費(fèi)的時(shí)長.基站按需為各個(gè)任務(wù)分配計(jì)算資源,計(jì)算資源以虛擬機(jī)實(shí)例(virtual machine instance)為單位分配.每個(gè)虛擬機(jī)實(shí)例的最大CPU周期為s(max)Hz(每秒).假設(shè)基站j為車輛i產(chǎn)生的任務(wù)m分配虛擬機(jī)實(shí)例的數(shù)量為ni,j,m.該基站中處理隊(duì)列o的任務(wù)平均處理時(shí)長被計(jì)算為:

(8)

控制器卸載隊(duì)列中的任務(wù)被分發(fā)到不同基站的處理隊(duì)列中.處理隊(duì)列中任務(wù)的到達(dá)也服從泊松過程.基站j分配給切片o的頻譜資源數(shù)量在所有同類型切片的頻譜資源中的占比為:

(9)

基站j中任務(wù)處理隊(duì)列的服務(wù)類型o任務(wù)到達(dá)率為αj,oλo.任務(wù)處理過程被建模為M/M/1隊(duì)列模型.基于式(4)、式(8)和式(9),基站j中處理隊(duì)列o的服務(wù)強(qiáng)度被定義為:

(10)

為了保持處理隊(duì)列的穩(wěn)定性,式(10)需要滿足:

(11)

在基站j的處理隊(duì)列中,排在任務(wù)m之前的任務(wù)索引集合被表示為ψj(m).該任務(wù)的處理延遲被計(jì)算為:

(12)

2.4.3 任務(wù)移交延遲建模

如圖3所示,每個(gè)任務(wù)在基站的處理隊(duì)列中計(jì)算完成后,直接由基站將結(jié)果傳輸回車輛.基于公式(2),在基站j中的任務(wù)m回傳給車輛i的移交延遲被表示為:

(13)

任務(wù)延遲由卸載延遲、處理延遲和移交延遲組成,由式(7)、式(12)和式(13)得車輛i產(chǎn)生的任務(wù)m的任務(wù)延遲為:

(14)

車輛只有在與基站建立連接時(shí)才能獲取服務(wù).若車輛在離開基站覆蓋范圍時(shí)仍未收到任務(wù)處理結(jié)果,即使任務(wù)調(diào)度時(shí)間未超出本身延遲要求,同樣視為任務(wù)失敗.假設(shè)車輛i從產(chǎn)生任務(wù)m時(shí)到駛出基站j覆蓋范圍的總行駛距離被表示為γi,j,m,車輛i的行駛速率被表示為vi.則任務(wù)m的最大調(diào)度時(shí)間可以被計(jì)算為:

因此,任務(wù)m完成的延遲約束被表示為:

(15)

由于車載用戶行駛方向和速度的時(shí)變性以及路網(wǎng)的復(fù)雜性,車輛未來的行駛軌跡是多變的.單個(gè)基站的覆蓋范圍有限,很難為車載用戶提供完整的服務(wù),協(xié)作式卸載模式有助于減少因車輛離開基站覆蓋范圍而導(dǎo)致的任務(wù)失敗率.盡管如此,協(xié)作式卸載模式也使得基站的選擇策略變得更多,進(jìn)而導(dǎo)致控制器進(jìn)行調(diào)度決策的難度提高.后續(xù)將探討相應(yīng)的解決方案.

3 問題建模

所提方案的目標(biāo)是在滿足差異化QoS需求的基礎(chǔ)上最大化任務(wù)完成數(shù)量.切片窗口w任務(wù)完成情況依賴于RAN切片策略和協(xié)作式任務(wù)調(diào)度策略.面向RAN切片的頻譜資源和計(jì)算資源策略集合分別被表示為:

和

協(xié)作式任務(wù)調(diào)度策略集合被表示為:

定義如下二元變量:

(16)

當(dāng)任務(wù)在滿足延遲約束的條件下完成時(shí),系統(tǒng)獲得對(duì)應(yīng)的收益.相應(yīng)地,若任務(wù)未能完成,系統(tǒng)產(chǎn)生對(duì)應(yīng)的損失.

定義1.在第w個(gè)切片窗口內(nèi),任務(wù)完成且滿足延遲需求時(shí),系統(tǒng)獲得的總獎(jiǎng)勵(lì)U(w):

(17)

其中uj,o∈(0,1)代表請(qǐng)求類型為o的任務(wù)在基站j上的對(duì)應(yīng)收益因子.

定義 2.在第w個(gè)切片窗口內(nèi),任務(wù)未能滿足延遲需求時(shí),系統(tǒng)產(chǎn)生的總損失H(w):

(18)

其中hj,o∈(0,1)代表請(qǐng)求類型為o的任務(wù)在基站j上對(duì)應(yīng)的損失因子.

在滿足QoS需求前提下,使系統(tǒng)長期性地完成更多的車輛任務(wù)是本文的目標(biāo).以最大化車輛任務(wù)完成數(shù)為目標(biāo),動(dòng)態(tài)RAN切片問題被建模為:

(19a)

(19b)

(19c)

(19d)

(6)和(11)

(19e)

問題P0的實(shí)質(zhì)是通過在線的方式,協(xié)調(diào)分配各個(gè)基站的頻譜和計(jì)算資源以及區(qū)域內(nèi)的工作負(fù)載,使得系統(tǒng)長期的平均任務(wù)完成數(shù)最大.其中,約束(19a)保證每個(gè)基站j分配得到的子信道數(shù)為正數(shù).約束(19b)和(19c)保證每個(gè)基站分配給車輛的頻譜和計(jì)算資源不超過自身持有的資源總數(shù).約束(19d)保證了每個(gè)車輛只能連接唯一的地面基站,而不能同時(shí)連接多個(gè).約束(19e)保證了排隊(duì)系統(tǒng)中隊(duì)列的穩(wěn)定性,同時(shí),也表明了RAN資源的切片決策和任務(wù)調(diào)度決策是耦合的,即耦合約束.

4 問題解耦與算法設(shè)計(jì)

為了便于處理,將P0分解為大時(shí)間尺度上的RAN切片子問題和小時(shí)間尺度上的任務(wù)調(diào)度子問題.

4.1 面向任務(wù)卸載的RAN切片資源分配方法

s.t.(19a),(19b)and(19c)

根據(jù)式(17)和式(18),每個(gè)切片窗口內(nèi)的決策獨(dú)立且窗口內(nèi)的各任務(wù)被獨(dú)立地分配資源.RAN切片子問題的實(shí)質(zhì)是最大化每個(gè)切片窗口內(nèi)的任務(wù)完成數(shù)量.現(xiàn)實(shí)中的車流量不會(huì)出現(xiàn)連續(xù)的較大波動(dòng),相鄰切片窗口的車流量具有相似性.

控制器可以參考上一個(gè)切片窗口的任務(wù)調(diào)度策略來優(yōu)化RAN切片.根據(jù)該思路,將P1轉(zhuǎn)化為如下以切片窗口為周期的一次性優(yōu)化(one-shot)問題 :

s.t.cj,o≥0,?o∈{1,2},?j∈J

(20a)

(20b)

(19b)和(19c)

(20c)

問題P2屬于求解多約束條件下的多元函數(shù)極值問題,可以使用拉格朗日乘數(shù)法對(duì)其求解.這種方法將一個(gè)有多個(gè)變量和多個(gè)約束條件的最優(yōu)化問題轉(zhuǎn)化為一個(gè)有多個(gè)變量的無約束方程組的極值問題.P2問題被轉(zhuǎn)化為P3.

在給定任務(wù)調(diào)度策略的情況下,控制器可以計(jì)算出每個(gè)基站處理任務(wù)的具體數(shù)量.然后,根據(jù)任務(wù)的屬性、QoS需求以及各個(gè)基站的資源持有量構(gòu)建出RAN切片子問題.計(jì)算P3可以得到一個(gè)最優(yōu)的RAN切片方案C(w),S(w).

4.2 基于深度強(qiáng)化學(xué)習(xí)的任務(wù)調(diào)度

s.t.19(d),(6)和(11)

問題P1中,各個(gè)切片窗口的資源分配是相互獨(dú)立的.相應(yīng)地,在各個(gè)切片窗口中RAN切片決策固定下進(jìn)行任務(wù)的調(diào)度也是相互獨(dú)立的.因此,求解問題P4時(shí)可以將長期優(yōu)化問題分解為各個(gè)調(diào)度時(shí)隙內(nèi)的短期優(yōu)化問題.短期優(yōu)化問題屬于有限視界的馬爾可夫決策問題.

下文將單個(gè)切片窗口內(nèi)的任務(wù)調(diào)度子問題重新構(gòu)建為一個(gè)馬爾可夫決策問題[22].具體而言,控制器被抽象為一個(gè)智能體(agent).在訓(xùn)練回合l時(shí),控制器觀察環(huán)境的狀態(tài),記錄為s(l).然后基于s(l),控制器采取任務(wù)調(diào)度決策動(dòng)作a(l).做出動(dòng)作后,環(huán)境反饋給相應(yīng)的獎(jiǎng)勵(lì)r(l).同時(shí),根據(jù)狀態(tài)轉(zhuǎn)移概率Pr(s(l+1)|s(l),a(l))將環(huán)境的狀態(tài)轉(zhuǎn)化為新狀態(tài)s(l+1).在本馬爾可夫決策問題中,狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)的表示如下:

·狀態(tài)空間S:任務(wù)調(diào)度需要考慮全局路網(wǎng)中的多個(gè)因素,包括任務(wù)參數(shù)、車輛信息以及各基站位置、資源及隊(duì)列狀態(tài)等信息.用s(l)∈S描述系統(tǒng)狀態(tài),表示為:

(21)

·動(dòng)作空間A:系統(tǒng)在訓(xùn)練回合l做出的任務(wù)調(diào)度描述為動(dòng)作a(l).動(dòng)作的制定基于當(dāng)前的環(huán)境狀態(tài),與問題P4的優(yōu)化變量對(duì)應(yīng),即:

a(l)={A(l)}

(22)

其中,A(l)代表訓(xùn)練回合內(nèi)的任務(wù)調(diào)度決策.為了滿足約束(19d),每個(gè)動(dòng)作只取0或1.

·獎(jiǎng)勵(lì)R:獎(jiǎng)勵(lì)是為了評(píng)估在某個(gè)狀態(tài)下所做動(dòng)作的優(yōu)劣.通過設(shè)立獎(jiǎng)勵(lì)機(jī)制使神經(jīng)網(wǎng)絡(luò)以最大化獎(jiǎng)勵(lì)為目標(biāo)更新優(yōu)化.基于式(17)和式(18),獎(jiǎng)勵(lì)可以被表示為:

r(l)(s(l),a(l))=(U(l)-H(l))

(23)

基站按照深度強(qiáng)化學(xué)習(xí)的決策接收任務(wù)并處理.任務(wù)如果能夠被正常處理,系統(tǒng)需要獲得獎(jiǎng)勵(lì)來肯定這次動(dòng)作.如果系統(tǒng)做出一個(gè)不合理的任務(wù)調(diào)度決策,基站常面臨資源不足的情況,進(jìn)而導(dǎo)致處理隊(duì)列難以保持穩(wěn)定.為了描述這種情況,需要加入懲罰以阻止控制器做出不合理的決策.

令Π代表候選調(diào)度策略的集合.針對(duì)當(dāng)前的調(diào)度時(shí)隙t,目標(biāo)是尋找最大化系統(tǒng)獎(jiǎng)勵(lì)獲得的調(diào)度策略,表示為:

其中,π∈Π代表選擇的任務(wù)調(diào)度策略,φ(l)∈(0,1)代表在訓(xùn)練回合l的折扣因子.由于任務(wù)信息發(fā)布的不可預(yù)知性,狀態(tài)轉(zhuǎn)移概率無法確定.問題P5無法通過傳統(tǒng)的基于模型(model-based)的強(qiáng)化學(xué)習(xí)算法求解,本文采用不依賴模型(model-free)的強(qiáng)化學(xué)習(xí)算法求解最優(yōu)任務(wù)調(diào)度問題.另一方面,由于難以對(duì)車聯(lián)網(wǎng)環(huán)境進(jìn)行建模,本節(jié)引入深度強(qiáng)化學(xué)習(xí)中的深度Q學(xué)習(xí)網(wǎng)絡(luò)(Deep Q-learning Network,DQN)算法,通過改進(jìn)Q學(xué)習(xí)算法,可以應(yīng)對(duì)更加龐大的動(dòng)作狀態(tài)空間.

Q學(xué)習(xí)算法的核心在于構(gòu)建一個(gè)Q表.在狀態(tài)空間下,每個(gè)動(dòng)作獲得的獎(jiǎng)勵(lì)被估計(jì)并存儲(chǔ)到Q表中.動(dòng)作價(jià)值函數(shù)表示為Q(s(l),a(l)|θ),θ代表神經(jīng)網(wǎng)絡(luò)的權(quán)重參數(shù).Q表中每個(gè)狀態(tài)的獎(jiǎng)勵(lì)最大值代表未來可能獲得的最大回報(bào).通過查詢Q表,每個(gè)狀態(tài)下最大收益的動(dòng)作被確定為:

(24)

對(duì)(24)運(yùn)用貝爾曼等式,可以得到Q表中的值,計(jì)算過程為:

(25)

上式中v代表學(xué)習(xí)速率,φ代表貪心概率.

如圖4所示,DQN算法輸出的動(dòng)作就是控制器為每個(gè)任務(wù)做出的調(diào)度決策.相較于人為制定的策略,神經(jīng)網(wǎng)絡(luò)更容易從復(fù)雜的全局環(huán)境中找出當(dāng)前任務(wù)卸載的最優(yōu)解.當(dāng)車輛行駛距離長時(shí),車輛會(huì)通過多個(gè)基站的覆蓋網(wǎng)絡(luò),基站協(xié)作進(jìn)行任務(wù)卸載的概率很高;而當(dāng)行駛的距離短時(shí),任務(wù)卸載多由附近基站獨(dú)自完成.

圖4 面向任務(wù)調(diào)度的DQN框架Fig.4 DQN structure for task scheduling

下面通過算法1來描述基于DQN的任務(wù)調(diào)度機(jī)制.

算法1.基于DQN的任務(wù)調(diào)度

輸入:各基站持有的物理資源,車輛、任務(wù)以及隊(duì)列的信息.

輸出:每個(gè)任務(wù)的最優(yōu)調(diào)度決策.

1.初始化DQN中的參數(shù)和相應(yīng)的動(dòng)作價(jià)值函數(shù);

2. 使用隨機(jī)權(quán)重θ初始化原始神經(jīng)網(wǎng)絡(luò)參數(shù);

3. 使用隨機(jī)權(quán)重θ←θ-初始化目標(biāo)神經(jīng)網(wǎng)絡(luò)參數(shù);

4.for回合episode←1,T(w)do

5.初始化s(0);

6.forl←1,l(max)do

7. 以概率1-φ選擇一個(gè)隨機(jī)動(dòng)作a(l),否則a(l)←π(s(l));

8. 執(zhí)行動(dòng)作a(l),觀察獎(jiǎng)勵(lì)r(l)和狀態(tài)s(l+1);

9.ifl==l(max)then

10. 令Q(s(l),a(l)|θ)←r(l);

11.else

13. 將四元組存儲(chǔ)到經(jīng)驗(yàn)池中;

14. 每隔Na次隨機(jī)抽取批量樣本訓(xùn)練;

15. 根據(jù)梯度下降更新原始神經(jīng)網(wǎng)絡(luò)權(quán)重參數(shù)θ;

16. 每隔Nb步更新目標(biāo)網(wǎng)絡(luò)權(quán)重參數(shù)θ-←θ;

17.end if

18.end for

19.end for

20.return最優(yōu)任務(wù)調(diào)度策略π*;

4.3 聯(lián)合優(yōu)化策略

本節(jié)提出聯(lián)合優(yōu)化策略,大時(shí)間尺度上的RAN切片子問題與小時(shí)間尺度上的協(xié)作式任務(wù)調(diào)度子問題被聯(lián)合求解.算法2給出了RAN切片子問題和協(xié)作式任務(wù)調(diào)度聯(lián)合優(yōu)化策略.

算法2.RAN切片-任務(wù)調(diào)度聯(lián)合優(yōu)化

輸入:各基站內(nèi)總物理資源以及全局內(nèi)車輛、任務(wù)信息.

輸出:每個(gè)切片窗口內(nèi)的RAN切片決策和任務(wù)調(diào)度決策.

1.初始化A(0).

2.Repeat:

3. 給定A(w-1)求解P3,得到C(w),S(w);

4. 確定調(diào)度時(shí)隙集合;

5. 給定C(w),S(w)求解P5,得到調(diào)度時(shí)隙t內(nèi)的A(t);

7.Untilw為最后一個(gè)切片窗口.

首先,系統(tǒng)根據(jù)歷史數(shù)據(jù)中的任務(wù)信息劃分切片窗口的長度.切片窗口確定后,將第w-1個(gè)切片窗口內(nèi)的任務(wù)調(diào)度決策A(w-1)作為求解問題P3的已知條件,并求解出RAN切片決策C(w),S(w).第一個(gè)切片窗口的任務(wù)調(diào)度決策A(0)由歷史數(shù)據(jù)給出.將切片窗口w劃分為多個(gè)同等大小的調(diào)度時(shí)隙t∈Tw.在每個(gè)調(diào)度時(shí)隙內(nèi),將RAN切片決策C(w),S(w)作為求解問題P5的已知條件,得到每個(gè)調(diào)度時(shí)隙內(nèi)的任務(wù)調(diào)度決策.各個(gè)基站按照任務(wù)調(diào)度決策處理任務(wù).在最后一個(gè)調(diào)度時(shí)隙結(jié)束時(shí),系統(tǒng)將每個(gè)調(diào)度時(shí)隙內(nèi)的任務(wù)調(diào)度決策整合為切片窗口w的任務(wù)調(diào)度決策A(w),并記錄為歷史數(shù)據(jù)供第w+1個(gè)切片窗口使用.

聯(lián)合優(yōu)化策略實(shí)現(xiàn)了RAN切片和任務(wù)調(diào)度的交替和長期運(yùn)行.利用相鄰時(shí)間段車流量的相似性,將上個(gè)切片窗口的任務(wù)調(diào)度決策作為已知條件,得到RAN切片決策.不僅減少了系統(tǒng)的計(jì)算任務(wù),也可以提升切片決策的適用性.

5 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本節(jié)通過一系列的仿真實(shí)驗(yàn)驗(yàn)證本文方案的有效性.實(shí)驗(yàn)的硬件環(huán)境中,CPU使用AMD Ryzen5 3500X,其包含6核6線程;GPU使NVIDIA GeForce GTX 1660 SUPER.實(shí)驗(yàn)環(huán)境使用Python 3.6.8和PyTorch 1.7.1實(shí)現(xiàn).本文使用PyTorch搭建卷積神經(jīng)網(wǎng)絡(luò),在訓(xùn)練模型時(shí),原始神經(jīng)網(wǎng)絡(luò)和目標(biāo)神經(jīng)網(wǎng)絡(luò)使用相同的架構(gòu).神經(jīng)網(wǎng)絡(luò)隱藏層間均用全連接層,全連接隱藏層都使用ReLu函數(shù)作為激活函數(shù),最后一層網(wǎng)絡(luò)采用softmax函數(shù)激活函數(shù).神經(jīng)網(wǎng)絡(luò)訓(xùn)練中超參數(shù)的設(shè)置通過多次對(duì)比實(shí)驗(yàn)確定.首先,依據(jù)大量實(shí)驗(yàn)結(jié)果確定各個(gè)超參數(shù)的合理取值范圍.然后,在取值范圍內(nèi)對(duì)各個(gè)超參數(shù)進(jìn)行排列組合.最后,針對(duì)各個(gè)候選的超參數(shù)組合進(jìn)行對(duì)比實(shí)驗(yàn),選定最佳的超參數(shù)組合.具體的超參數(shù)設(shè)置如表1所示.

表1 實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters

為了模擬交通路網(wǎng)環(huán)境,考慮一個(gè)由5條道路交叉而形成兩個(gè)方格的路網(wǎng)場(chǎng)景(與圖1中相似),方格的邊長為1000m.其中包含5個(gè)覆蓋半徑為500m的宏基站,每個(gè)宏基站的發(fā)射功率同為40dBm.MEC控制器放置在5個(gè)宏基站的中心位置處,控制器與宏基站通過有線連接.為了讓仿真貼近現(xiàn)實(shí)環(huán)境,本文實(shí)驗(yàn)選取的車流量數(shù)據(jù)來源為OpenITS開放數(shù)據(jù)平臺(tái).車輛產(chǎn)生任務(wù)的到達(dá)率服從泊松分布.延遲敏感型任務(wù)為智能汽車控制指令,延遲約束的范圍在50ms-1s;延遲容忍型任務(wù)為車載設(shè)備高清地圖下載,延遲約束的范圍在3s-10s.為了保證仿真實(shí)驗(yàn)中任務(wù)信息的多樣性,每個(gè)任務(wù)的延遲約束在限制范圍內(nèi)按概率隨機(jī)給出.其他參數(shù)如表2所示.

表2 仿真參數(shù)Table 2 Simulation parameters

為了客觀地評(píng)估性能,本文選取3種代表性的任務(wù)卸載策略用于對(duì)比,包括:

·基于最大信干噪比的任務(wù)卸載方法(Max-SINR)[23]:RAN切片比例按照平均劃分,控制器進(jìn)行任務(wù)調(diào)度時(shí),選擇與車輛連接最大信干噪比的基站.

·隨機(jī)的任務(wù)調(diào)度方法(Random)[24]:RAN切片比率隨機(jī)分配,控制器進(jìn)行任務(wù)調(diào)度時(shí),隨機(jī)選擇基站.

·距離優(yōu)先的車輛關(guān)聯(lián)方法 (RSE-online)[25]:RAN切片比例按照平均劃分,控制器進(jìn)行任務(wù)調(diào)度時(shí),優(yōu)先選擇距離車輛最近的基站.

首先,評(píng)估可用資源塊(頻譜資源塊和計(jì)算資源塊)增加對(duì)任務(wù)完成率的影響.圖5(a)展示了計(jì)算資源數(shù)固定為15的情況下,頻譜資源增加對(duì)任務(wù)完成率的影響.各方案的任務(wù)完成率不斷提高.在頻譜資源塊增加到15之后,各方案的任務(wù)完成率逐漸趨于穩(wěn)定.充足的頻譜資源使得控制器有更大的決策空間,是性能提升必要條件,但不是唯一條件.接下來考察當(dāng)子信道數(shù)量固定為15時(shí),計(jì)算資源的增加對(duì)性能的影響.如圖5(b)所示,任務(wù)成功率在初始階段快速上升,但當(dāng)計(jì)算資源塊增加到16后,性能不再有明顯提升.這是因?yàn)橄到y(tǒng)處理能力的上限由兩種資源共同決定,當(dāng)任務(wù)數(shù)量飽和后,單純?cè)黾佑?jì)算或頻譜資源都難以提升系統(tǒng)性能.

圖5 可用資源塊數(shù)量對(duì)任務(wù)完成率的影響Fig.5 Impact of the number of available resource blocks on task success rate

圖6展示了本文方案在頻譜和計(jì)算資源塊各固定為15塊,延遲敏感型任務(wù)占比為40%時(shí),成功完成的任務(wù)延遲對(duì)應(yīng)的概率分布.從圖6可以看出,任務(wù)延遲低于1s的比例大約有30%,而低于1s至低于3s的比例沒有任何變化.這是因?yàn)榈陀?s延遲完成的任務(wù)屬于延遲敏感型,而延遲容忍型任務(wù)完成的時(shí)延高于3s.任務(wù)延遲時(shí)間在區(qū)間3.5s～5s內(nèi)的累積概率由44.3%增加至88.6%,這驗(yàn)證了在本文方案下的延遲容忍型任務(wù)大概率在5s內(nèi)就可以被處理完成.任務(wù)延遲時(shí)間低于7s的比例共有98.9%.

圖6 成功完成的任務(wù)延遲時(shí)間累積分布圖Fig.6 Cumulative distribution function of latency for completed tasks

圖7評(píng)估了車流量的變化對(duì)全局資源利用率的影響.車輛密度越高,車流量越大.當(dāng)車輛密度為0.1輛/m2時(shí),四種方案的全局資源利用率都在50%以下.這是因?yàn)榫W(wǎng)絡(luò)中的任務(wù)稀疏,有些基站處于空閑狀態(tài),系統(tǒng)中的資源不能全部利用.另外,可以看出隨著車輛密度的增加,全局資源利用率不斷升高.與Max-SINR和RSE-online相比,本方案的資源利用率分別增加了29%和10%.在車輛密度增加到0.3輛/m2之后,RSE-online和本方案的資源利用率明顯高于其它方案.這是因?yàn)檐囕v密度的增加導(dǎo)致任務(wù)數(shù)量變多,深度強(qiáng)化學(xué)習(xí)能在綜合考慮各個(gè)因素的條件下,更快地做出最優(yōu)調(diào)度決策,降低任務(wù)的處理時(shí)延,并使得系統(tǒng)資源利用率增加.然而,資源的利用率無法增加至100%.這是因?yàn)檐囕v必須要在基站的覆蓋范圍內(nèi)才能與其連接并卸載任務(wù),遠(yuǎn)離車輛的基站無法為其提供服務(wù).

圖7 車輛密度對(duì)全局資源利用率的影響Fig.7 Impact of AV density on resource utilization

圖8評(píng)估了延遲敏感型任務(wù)占比增加對(duì)任務(wù)完成率的影響.隨著延遲敏感型任務(wù)占比的增加,任務(wù)完成率不斷降低.這是因?yàn)檠舆t敏感型任務(wù)的QoS限制導(dǎo)致任務(wù)處理需要更多的資源.增加延遲敏感型任務(wù)的占比,是對(duì)系統(tǒng)的處理能力進(jìn)行壓力測(cè)試.相較于其他方案,所提方法通過感知環(huán)境信息做出合適的任務(wù)調(diào)度決策,提升了任務(wù)完成率,特別是在面對(duì)極端條件時(shí)具有更強(qiáng)的魯棒性.

圖8 延遲敏感型任務(wù)占比對(duì)任務(wù)完成率的影響Fig.8 Impact of the percentage of delay-sensitive tasks on task success rate

6 總 結(jié)

本文提出了一種面向任務(wù)卸載的動(dòng)態(tài)RAN切片框架,不僅實(shí)現(xiàn)了服務(wù)QoS的隔離,也提升了系統(tǒng)處理的魯棒性.針對(duì)任務(wù)調(diào)度,本文設(shè)計(jì)了一種協(xié)作式任務(wù)卸載策略,并引入深度強(qiáng)化學(xué)習(xí)進(jìn)行決策,提升了車載用戶的任務(wù)完成率.仿真結(jié)果表明,本文提出的方案相較于現(xiàn)有方案,有效增加了任務(wù)完成數(shù)量,提升了系統(tǒng)資源利用率,實(shí)現(xiàn)了網(wǎng)絡(luò)服務(wù)的公平性.后續(xù)擬加入對(duì)未來流量變化的預(yù)測(cè).系統(tǒng)可以根據(jù)熱點(diǎn)預(yù)測(cè)信息提前部署資源,靈活地應(yīng)對(duì)網(wǎng)絡(luò)環(huán)境變化.在任務(wù)調(diào)度上,引入基于DQN的改進(jìn)算法,有望進(jìn)一步降低系統(tǒng)的計(jì)算負(fù)擔(dān),提升系統(tǒng)性能.