無人機(jī)基站輔助的內(nèi)容緩存多目標(biāo)優(yōu)化策略

紀(jì)洪運(yùn),沈 航,白光偉

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

1 引 言

在新一代無線通信網(wǎng)絡(luò)中,各種新興無線多媒體通信業(yè)務(wù)日趨普及.字節(jié)跳動旗下APP“抖音”最新發(fā)布的《2020抖音數(shù)據(jù)報(bào)告》顯示,截止2020年12月,抖音日均視頻搜索量突破4億,日活躍用戶突破6億.以短視頻平臺為代表的新興移動終端應(yīng)用將以往web通信中對信息流的請求變?yōu)橥扑?即用戶安裝運(yùn)行相關(guān)的APP后,應(yīng)用服務(wù)提供商會推薦大量如視頻、新聞等內(nèi)容供用戶瀏覽.隨著用戶體量的增長,短視頻類平臺對于網(wǎng)絡(luò)負(fù)載的影響已經(jīng)不容忽視.

在上述的短視頻類應(yīng)用中,視頻文件以內(nèi)容為中心存在明顯的聚類特征,應(yīng)用服務(wù)提供商會推薦大量的視頻內(nèi)容,而用戶主動搜索的內(nèi)容也存在明顯的重復(fù)性,如在2020年COVID-19病毒肆虐期間,話題為“共同抗疫”的有關(guān)視頻播放量達(dá)423億次.除了具有內(nèi)容為中心的時(shí)效性外,相關(guān)的國內(nèi)及國際主流手機(jī)應(yīng)用上看到人們關(guān)心的視頻內(nèi)容具有地理上的區(qū)域特征,如社交軟件內(nèi)部的同城板塊、個(gè)人博客中帶有地理位置信息的標(biāo)注戳等,都強(qiáng)化了社交網(wǎng)絡(luò)中的地理位置類標(biāo)簽與信息本身的耦合性.

當(dāng)無線數(shù)據(jù)的業(yè)務(wù)量及數(shù)據(jù)流量大幅增長,現(xiàn)有的無線頻譜資源會面臨不足以支持大量的無線多媒體通信需求的問題,網(wǎng)絡(luò)運(yùn)營商需要采取有效手段以減少重復(fù)的多媒體數(shù)據(jù)傳輸和下載.

一方面,利用移動邊緣計(jì)算(Mobile Edge Computing,MEC)技術(shù)可以將計(jì)算、存儲、處理功能放置在網(wǎng)絡(luò)邊緣的邊緣服務(wù)器處,從而大大緩解骨干網(wǎng)的負(fù)擔(dān).在存儲方面具體來說,通過放置靠近用戶終端的緩存設(shè)備以減少重復(fù)的文件傳輸.緩存設(shè)備存儲熱門文件,并在用戶請求時(shí)直接發(fā)送給用戶,避免訪問骨干網(wǎng)而產(chǎn)生不必要的流量負(fù)載.

另一方面,近年來,由于體積小,價(jià)格低和靈活性高,無人機(jī)(Unmanned Aerial Vehicle,UAV)已廣泛用于許多行業(yè),以上優(yōu)勢有利于解決傳統(tǒng)通信中如基站部署成本高和對特殊環(huán)境的適應(yīng)性較差等問題.通過將UAV部署為空中基站(Drone Base Station,DBS)輔助無線通信網(wǎng)絡(luò),可以減輕某些熱點(diǎn)地區(qū)高峰時(shí)段的流量壓力[1].

本文針對短視頻類應(yīng)用使用場景,構(gòu)建一個(gè)無線網(wǎng)絡(luò)通信區(qū)域模型,并采用無人機(jī)基站作為移動邊緣計(jì)算中的邊緣服務(wù)器.通過對無人機(jī)基站中高速緩存和無人機(jī)基站移動路徑的優(yōu)化,緩解大量無線多媒體通信場景下通信資源不足的問題.

為了對系統(tǒng)緩存部署的優(yōu)良程度進(jìn)行評估,本文引入文獻(xiàn)[2]中的系統(tǒng)平均緩存命中率(The average cache hit ratio of the system),作為評價(jià)本系統(tǒng)對于文件請求響應(yīng)和節(jié)約高速緩存的重要指標(biāo).在技術(shù)使用的選擇上,深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)將深度學(xué)習(xí)(Deep Learning,DL)的感知能力和強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)的決策能力相結(jié)合,可以直接根據(jù)輸入的信息進(jìn)行預(yù)測和控制,是一種更接近人類思維方式的人工智能方法[3].本文提出一種基于深度強(qiáng)化學(xué)習(xí)的無人機(jī)基站緩存聯(lián)合解決策略(Drone Base Station Caching with Deep Reinforcement Learning,DC-DRL),其核心思想是,根據(jù)視頻文件內(nèi)容的流行度預(yù)測設(shè)計(jì)邊緣服務(wù)器的內(nèi)容緩存策略,并與無人機(jī)基站的部署調(diào)度相結(jié)合,進(jìn)行多因素、多目標(biāo)的聯(lián)合優(yōu)化,以提升邊緣節(jié)點(diǎn)高速緩存的系統(tǒng)平均緩存命中率.

2 相關(guān)工作

無線數(shù)據(jù)業(yè)務(wù)量急劇增長業(yè)務(wù)增長模式的驅(qū)動力已經(jīng)由以連接為中心的通信(例如語音和短消息)向以內(nèi)容為中心的通信(例如視頻流和音樂)轉(zhuǎn)移[4].為提升網(wǎng)絡(luò)容量以滿足需求,各大運(yùn)營商部署了密集的小基站,但這對回傳鏈路造成了極大的負(fù)擔(dān)[4].而從移動用戶的角度來看,由于MEC服務(wù)器位于網(wǎng)絡(luò)的邊緣,非常接近移動設(shè)備的位置,因此可以結(jié)合用戶移動性和內(nèi)容訪問日志來優(yōu)化使用體驗(yàn)[5].

一些現(xiàn)有文獻(xiàn)涉及基站內(nèi)容緩存以及無人機(jī)基站調(diào)度的研究成果,如在邊緣緩存文件放置方面,文獻(xiàn)[3]中研究了具有移動邊緣計(jì)算功能的5G網(wǎng)絡(luò)中小型基站的內(nèi)容緩存策略,并給出了相對優(yōu)化的MyCaching算法;文獻(xiàn)[6]中研究了無感知環(huán)境下移動邊緣計(jì)算網(wǎng)絡(luò)中的緩存放置優(yōu)化問題;文獻(xiàn)[7]中研究了車聯(lián)網(wǎng)環(huán)境下緩存文件預(yù)測機(jī)制;文獻(xiàn)[2,8,9]研究了D2D條件下邊緣協(xié)同緩存問題;文獻(xiàn)[10]提出了一種基于高速緩存的無人機(jī)優(yōu)化物聯(lián)網(wǎng)系統(tǒng)中的多媒體數(shù)據(jù)吞吐量最大化的方法.在無人機(jī)基站聯(lián)合部署方面,文獻(xiàn)[11]綜述了5G無線網(wǎng)絡(luò)下多層無人機(jī)基站架構(gòu)的挑戰(zhàn)、趨勢和前景;文獻(xiàn)[12-14]研究了多無人機(jī)基站系統(tǒng)的能耗優(yōu)化問題;文獻(xiàn)[15]研究了多無人機(jī)調(diào)度中的3D軌跡計(jì)劃優(yōu)化問題;文獻(xiàn)[16]提出了一種基于多智能體深度強(qiáng)化學(xué)習(xí)的分布式干擾協(xié)調(diào)策略.

但以上研究大多針對無線網(wǎng)絡(luò)或無人機(jī)部署方面單一目標(biāo)進(jìn)行優(yōu)化,然而在實(shí)際應(yīng)用中,區(qū)域內(nèi)無線網(wǎng)絡(luò)面臨的問題大多是多因素、多目標(biāo)聯(lián)合優(yōu)化問題,與所處時(shí)間以及空間有著難以忽略的關(guān)聯(lián)性.例如,在以上考慮系統(tǒng)緩存放置及分發(fā)的研究中,都忽略了區(qū)域內(nèi)文件流行度與二維平面上請求內(nèi)容的關(guān)系;在以上考慮無人機(jī)移動性問題的研究中,很少有將無人機(jī)基站自身屬性(如所攜帶的緩存內(nèi)容)考慮在內(nèi)的情況.文獻(xiàn)[4]雖然同時(shí)考慮到了移動基站與緩存預(yù)測的結(jié)合,然而其使用的是基于文件相似性和用戶相似性的單個(gè)用戶內(nèi)容偏好預(yù)測算法及無人機(jī)部署方面的聚類算法,通過暴力求解的方式給出最終答案,大大增加了網(wǎng)絡(luò)內(nèi)的計(jì)算負(fù)擔(dān).近年來,使用機(jī)器學(xué)習(xí)的方法解決過去難以解決的問題成為新風(fēng)潮,機(jī)器學(xué)習(xí)所擁有的的從經(jīng)驗(yàn)中得出結(jié)論的方法可以有效解決傳統(tǒng)方法中計(jì)算量過大而難以求解的問題,其中,人們多用循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network,RNN)處理序列變化的數(shù)據(jù).

本文采用的長短期記憶(Long short term memory,LSTM)神經(jīng)網(wǎng)絡(luò)來處理時(shí)變的文件參數(shù)序列,相比普通的循環(huán)神經(jīng)網(wǎng)絡(luò),LSTM能夠在更長的序列中有更好的表現(xiàn).在強(qiáng)化學(xué)習(xí)中,Actor-Critic算法合并了Value-based和Policy-based兩類強(qiáng)化學(xué)習(xí)算法,可以為DBS在空間移動選擇上提供強(qiáng)有力的幫助.本文將長短期記憶神經(jīng)網(wǎng)絡(luò)輸出的文件流行度的預(yù)測結(jié)果與MyCaching方法[3]的文件放置與更新的策略有機(jī)結(jié)合,將輸出的帶有時(shí)序特征的網(wǎng)絡(luò)文件流行度預(yù)測結(jié)果作為指導(dǎo)無人機(jī)基站移動的強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)的關(guān)鍵輸入動作,以最大化系統(tǒng)平均緩存命中率.

3 系統(tǒng)模型

3.1 問題描述

本文擬解決緩存放置和無人機(jī)部署的聯(lián)合優(yōu)化問題.這是一個(gè)NP難問題,難以求解.這個(gè)優(yōu)化問題中的變量都是離散的,如果在算法中使用暴力求解的方式,該算法的復(fù)雜度將遠(yuǎn)超相關(guān)設(shè)備的計(jì)算能力,并且難以實(shí)現(xiàn).為了有效地解決這個(gè)問題,本文將其分解為兩個(gè)子問題,并提出了相應(yīng)的算法,即具有緩存功能的無人機(jī)基站的內(nèi)容緩存策略,以及宏基站控制下的集中式無人機(jī)部署方案.

3.2 模型描述

如圖1所示,在由一個(gè)具有宏基站及若干個(gè)無人機(jī)基站和移動設(shè)備組成的區(qū)域性無線網(wǎng)絡(luò)中,若干個(gè)空中無人機(jī)基站為地面用戶提供服務(wù),無人機(jī)自身攜帶高速緩存,同時(shí)可以通過宏基站向核心網(wǎng)請求內(nèi)容.該示例圖中可以明顯看出無人機(jī)基站(DBS)與地面宏基站及地面用戶的從屬關(guān)系.從上面的討論中可以看出,緩存文件流行度及DBS的移動性對DBS緩存內(nèi)容有著顯著的影響.基于此,本文將定義一個(gè)基于請求文件流行度與DBS移動性的DBS緩存模型.

分別用m和n表示DBS和移動蜂窩網(wǎng)絡(luò)中文件請求設(shè)備的數(shù)量.設(shè)N={n1,n2,n3,n4…}為蜂窩移動網(wǎng)絡(luò)中文件請求設(shè)備的集合.無人機(jī)基站可以連接到宏基站和地面用戶,并且每個(gè)用戶都可以獨(dú)立地請求所需內(nèi)容.

圖1 支持高速緩存的無人機(jī)輔助的蜂窩網(wǎng)絡(luò)Fig.1 Cache-enabling UAV-assisted cellular networks

短視頻類APP中,應(yīng)用服務(wù)提供商會向用戶推送短視頻內(nèi)容,用戶也可根據(jù)自身愛好搜索瀏覽一些帶有“話題標(biāo)簽”的短視頻內(nèi)容.因此,由有限數(shù)量的不同內(nèi)容文件組成的文件庫包含應(yīng)用服務(wù)提供商推送的和用戶額外請求的短視頻類文件.設(shè)F={f1,f2,f3,f4…}為文件庫內(nèi)文件的集合.本文使用每個(gè)用戶對每個(gè)文件的請求頻率來表示這個(gè)文件的受歡迎程度.首先進(jìn)行無人機(jī)基站緩存的初始化,隨著無人機(jī)基站上的高速緩存被文件庫中文件填滿,每個(gè)無人機(jī)的緩存文件進(jìn)行替換更新.假設(shè)每個(gè)用戶設(shè)備基于APP自有推送需要和用戶在APP內(nèi)的搜索指令對無人機(jī)基站發(fā)出請求,并且單位時(shí)間內(nèi)每次請求一個(gè)內(nèi)容.用p(i)表示第i個(gè)文件f被請求的概率,作為第i個(gè)文件的流行度.本文中選取流行度存最高的若干個(gè)文件替換之前的文件存儲于高速緩存,直至高速緩存中的空間再次被填滿.同時(shí),每個(gè)無人機(jī)基站可以借由宏基站從核心網(wǎng)請求內(nèi)容.假定待請求文件數(shù)為F,單個(gè)無人機(jī)的緩存大小為C,系統(tǒng)時(shí)間為T={t1,t2,t3,…,tz},單個(gè)文件f大小為ω.在本文中的無人機(jī)基站組成的網(wǎng)絡(luò)中,無人機(jī)基站m根據(jù)預(yù)測的每一個(gè)內(nèi)容文件在該DBS的文件流行度和無人機(jī)基站緩存狀態(tài)替換該DBS的緩存內(nèi)容.在本文中,第i個(gè)待緩存文件fi在本地的流行度被定義為為pi(m,[tz,tz+1)),它由[tz,tz+1)內(nèi),待緩存文件fi將被請求的次數(shù)決定.則無人機(jī)基站m上高速緩存對于文件F的緩存狀態(tài)向量為[s1(m,[tz,tz+1)),…,sF(m,[tz,tz+1))]T,其中si(m,[tz,tz+1))=

(1)

本文考慮在被劃分?jǐn)?shù)量為K個(gè)小區(qū)域的2D目標(biāo)區(qū)域中實(shí)現(xiàn)多無人機(jī)通信覆蓋的場景,在圖1中,M={m1,m2,m3,m4…}為一組無人機(jī),作為固定高度的移動基站為地面用戶提供互聯(lián)網(wǎng)服務(wù).每個(gè)DBS都有通信距離R作為連通性約束,當(dāng)它們與它們連接的設(shè)備的距離大于R時(shí),二者將失去連接.由于無人機(jī)飛行在一定的高度,所以覆蓋范圍R0≤R始終成立.一般情況下,一個(gè)小區(qū)域中心的興趣點(diǎn)(Point of Interests,PoI)被認(rèn)為是該小區(qū)的服務(wù)點(diǎn).為避免DBS之間的信道干擾,DBS之間的距離R1>R.在假定場景中,無人機(jī)從隨機(jī)位置起飛,學(xué)習(xí)以方向θ∈[0,2π)和距離l∈[0,lmax)移動,或者簡單地懸停在當(dāng)前位置.

為了實(shí)現(xiàn)無人機(jī)輔助蜂窩移動網(wǎng)絡(luò)對地面用戶的有效覆蓋,本文引入文獻(xiàn)[13]中所采用的系統(tǒng)平均覆蓋分?jǐn)?shù)作為一個(gè)“時(shí)空”的度量,用以衡量某個(gè)特定的PoI在過去的t個(gè)時(shí)段中是如何被DBS通信覆蓋的,因此,可以得到式(2):

(2)

其中ωt(b)表示在時(shí)段t時(shí),一個(gè)PoIb被覆蓋的指數(shù),則ct(b)∈[0,1].在完成T個(gè)時(shí)段的作業(yè)后,可以計(jì)算該點(diǎn)在時(shí)間段的平均覆蓋率,如式(3)所示:

(3)

則該次作業(yè)的最終平均覆蓋率分?jǐn)?shù)是Ct=Ct|t=T.

3.3 優(yōu)化目標(biāo)

邊緣服務(wù)器提供服務(wù)時(shí),對于內(nèi)容緩存的效率可以由多個(gè)維度表征,其中,請求文件的緩存命中率是對于緩存效率的一個(gè)行之有效的量化方法.

本文的優(yōu)化目標(biāo)是最大化系統(tǒng)整體的平均緩存命中率,具體地,通過對無人機(jī)基站m和時(shí)間間隔[tz,tz+1)進(jìn)行拆分,得到緩存狀態(tài)向量s(m,[tz,tz+1)).則系統(tǒng)平均緩存命中率可以表示為式(4):

(4)

式(4)中:Is(m,[tz,tz+1))(i(k))為指示函數(shù),由0和1表征,分別代表待請求文件fi在被用戶請求時(shí)未在和已在無人機(jī)基站m的高速緩存上.由此,將時(shí)間段z與無人機(jī)基站數(shù)m綜合起來,可以得到式(5)中的最大化系統(tǒng)平均緩存命中率:

(5)

式(5)中:s(m,[tz,tz+1))是待優(yōu)化變量,ω=[ω1,…,ωF]T表示整個(gè)內(nèi)容文件庫F中各個(gè)內(nèi)容文件的大小,z為各個(gè)時(shí)間段,m為各個(gè)無人機(jī)基站.

在實(shí)際的網(wǎng)絡(luò)內(nèi)容文件緩存和分發(fā)問題中,往往內(nèi)容文件的大小都是長短不一的,為了使問題拆分方便解決,本文將每一個(gè)長短不一的內(nèi)容文件拆分為不同數(shù)量、同等大小的小文件塊,因此,在緩存階段,本文要解決的是同等大小的小文件塊的選擇排序問題,具體地,本文將對每個(gè)無人機(jī)m上的文件塊根據(jù)pi(m,[tz,tz+1))進(jìn)行排序,直到填滿緩存空間Cm,而對于這種背包問題的相關(guān)處理前人已有許多研究[17].那么在引入文件流行度后問題式(5)可以寫成式(6)中的形式:

(6)

式(6)中的si(m,[tz,tz+1))是本文中的待優(yōu)化變量.根據(jù)章節(jié)3.1中所述,此NP難問題直接求解會變得非常復(fù)雜,因?yàn)樗婕暗蕉嗑S部署和多維文件概率求解.因此,在這一部分,本文將聯(lián)合優(yōu)化問題劃分為兩個(gè)復(fù)雜度較低的次優(yōu)解.從時(shí)間間隔[tz,tz+1)和無人機(jī)基站m入手可以解耦合為許多背包容量為Cm、品數(shù)為F的0-1背包問題.

在緩存文件的分發(fā)階段,無人機(jī)基站接到文件請求后首先在本地搜尋相應(yīng)緩存,若沒有找到則向干路網(wǎng)請求響應(yīng)文件,因此,提高本文提出的系統(tǒng)內(nèi)平均緩存命中率可以減少系統(tǒng)通過宏基站向干路網(wǎng)請求的流量,減少干路網(wǎng)流量負(fù)載.

4 DC-DRL策略設(shè)計(jì)

根據(jù)以上討論,本文考慮了應(yīng)用內(nèi)容文件的自帶參數(shù),將無人機(jī)基站(DBS)中的緩存文件流行度與無人機(jī)移動軌跡進(jìn)行聯(lián)合優(yōu)化,即設(shè)計(jì)一種同時(shí)考慮時(shí)、空因素的緩存策略.本策略通過將由LSTM預(yù)測所生成的文件流行度序列進(jìn)行比較排序作為Actor-Critic網(wǎng)絡(luò)的輸入序列,得出本文所需要的無人機(jī)基站緩存文件更新以及無人機(jī)的移動路徑,即在內(nèi)層使用神經(jīng)網(wǎng)絡(luò)進(jìn)行緩存內(nèi)容放置與更新的基礎(chǔ)上,在外層的無人機(jī)位置調(diào)度方面,使用深度強(qiáng)化學(xué)習(xí)的Actor-Critic算法來輔助對無人機(jī)的位置調(diào)度.由于實(shí)際的深度強(qiáng)化學(xué)習(xí)過程是集中在宏基站的中央控制器(Central controller)上進(jìn)行,只需把生成結(jié)果發(fā)送至DBS,因此可以有效節(jié)約DBS的計(jì)算負(fù)擔(dān)和數(shù)據(jù)傳輸流量.

4.1 基于LSTM的文件流行度預(yù)測

在緩存文件流行度的預(yù)測方面,利用長短期記憶神經(jīng)網(wǎng)絡(luò)進(jìn)行下一時(shí)段文件流行度的預(yù)測,相較于傳統(tǒng)方法,更加強(qiáng)調(diào)時(shí)間序列對于緩存文件的重要作用,通過引入緩存矩陣,可以將文件存儲的二元性有效表示并方便進(jìn)行動作處理運(yùn)算.本文中的緩存策略取決于內(nèi)容流行度預(yù)測,在時(shí)間段t中預(yù)測到的t+1時(shí)間段內(nèi)的流行度與實(shí)際t+1時(shí)間段的流行度越接近,用戶就越有可能在時(shí)間段t+1中的請求緩存正確的內(nèi)容,因此需要提高預(yù)測的準(zhǔn)確性.考慮到內(nèi)容文件流行度和用戶軌跡都是與時(shí)間有關(guān)的序列,長短期記憶(LSTM)深度學(xué)習(xí)模型由一個(gè)記憶單元和幾個(gè)門組成.如圖2所示,本文中的LSTM單元的結(jié)構(gòu)由記憶元組(memory cell)和非線性的門單元(nonlinear gating unit)組成,使用記憶元組可以保持系統(tǒng)的狀態(tài),使用非線性的門單元可以在每一個(gè)時(shí)間點(diǎn)調(diào)節(jié)記憶元組的輸入、輸出信息.每個(gè)遞歸的神經(jīng)網(wǎng)絡(luò)都可以分解成無數(shù)個(gè)基本重復(fù)單元,本文使用了4個(gè)神經(jīng)網(wǎng)絡(luò)層并且以圖2關(guān)系進(jìn)行交互.

圖2 DC-DRL中的LSTM網(wǎng)絡(luò)模型Fig.2 Long Short-Term memory model in DC-DRL

由于現(xiàn)有深度學(xué)習(xí)框架大多應(yīng)用于圖像處理領(lǐng)域,其中所處理的圖像文件以矩陣形式存儲和處理,本文因此受到啟發(fā),將緩存文件提取特征后的狀態(tài)以矩陣形式表示,則用戶請求文件的離散流行度分布為式(7):

(7)

其中pij表示第i個(gè)用戶請求第j個(gè)文件的概率.矩陣是行隨機(jī)的,因?yàn)榈趇行表示第i個(gè)用戶的離散概率分布,因此,第i行中所有元素的總和等于1.隨著文件數(shù)量的增長,該矩陣可能變得稀疏.

在Python官方網(wǎng)站給出的模型框架下,本文考慮到所需要的流行度結(jié)果,對文件進(jìn)行處理和特征提取,在算法1中給出了本文的預(yù)測流程.

算法1.基于LSTM的文件流行度預(yù)測算法

輸入:宏基站接收到的需求序列

輸出:文件流行度預(yù)測序列

1. 導(dǎo)入相關(guān)包

2. 定義預(yù)測步長、回溯時(shí)間和訓(xùn)練次數(shù)

3. forf=1,…,Fdo

4. 讀入基站接收需求序列

5. 定義分割數(shù)據(jù)函數(shù)

6. 生成隨機(jī)種子

7. 定義訓(xùn)練集大小

8. 數(shù)據(jù)集切分

9. 定義前瞻步長

10. 分割訓(xùn)練集和測試集

11. 重新設(shè)置數(shù)據(jù)格式

12. 構(gòu)建 LSTM 網(wǎng)絡(luò)

13. 帶入訓(xùn)練集進(jìn)行訓(xùn)練學(xué)習(xí)

14. 定義預(yù)測步長

15. 預(yù)測

16. 累加記錄預(yù)測結(jié)果

17. 更新預(yù)測結(jié)果

18. end for

19. 預(yù)測結(jié)果正則化

20. 計(jì)算真實(shí)值與預(yù)測值的誤差

4.2 基于Actor-Critic的無人機(jī)基站調(diào)度

本文使用的強(qiáng)化學(xué)習(xí)包含演員(actor)、環(huán)境(environment)、獎勵(lì)函數(shù)(reward function)3個(gè)部分.在算法中需要為DBS制定相應(yīng)的行動方案(policy),使得本文中獎勵(lì)函數(shù)得到的獎勵(lì)值最大化.考慮到本文的最終目標(biāo)是最大化無人機(jī)基站組網(wǎng)整體的系統(tǒng)平均緩存命中率,Actor-Critic算法結(jié)合了以策略為基礎(chǔ)的和以值為基礎(chǔ)的兩類強(qiáng)化學(xué)習(xí)算法,非常適用于無人機(jī)系統(tǒng)的調(diào)度決策.

本文將決策算法當(dāng)作Actor,用來實(shí)現(xiàn)概率選擇行為,又將以值為基礎(chǔ)的強(qiáng)化學(xué)習(xí)算法當(dāng)作Critic,用來評判Actor的行為得分,Actor又會根據(jù)Critic的評分修改行為的概率.在算法內(nèi)既可以在范圍內(nèi)處理連續(xù)動作的選取事件,又可以進(jìn)行單步更新[16].

在獎勵(lì)函數(shù)的設(shè)計(jì)中,本文著重強(qiáng)調(diào)了緩存命中率,同時(shí)本文創(chuàng)建一個(gè)Critic網(wǎng)絡(luò)來計(jì)算Q函數(shù)值,就可以得出應(yīng)用于無人機(jī)調(diào)度的Actor-Critic網(wǎng)絡(luò).Actor參數(shù)的梯度變?yōu)槭?8):

(8)

此時(shí)的Critic根據(jù)估計(jì)的Q值和實(shí)際Q值的平方誤差進(jìn)行更新,對Critic來說,其loss為式(9):

(9)

算法2.深度強(qiáng)化學(xué)習(xí)-聯(lián)合緩存和軌跡設(shè)計(jì)

1. 將重放緩沖區(qū)容量初始化為B

2. for UAVi=1,…,Ndo

3. 用權(quán)重θQi和θμi隨機(jī)初始化評價(jià)網(wǎng)絡(luò)Qi和演員網(wǎng)絡(luò)μi,

4.用權(quán)重θQ′i=θQi和θμ′i=θμi初始化目標(biāo)網(wǎng)絡(luò),

5. end for

6. for episode=1,…,Mdo

7. 初始化環(huán)境并接收初始狀態(tài)st+1,

8. for t=1,…,Tdo

9. For each UAVi,select

(10)

11. for UAVi=1,…,Ndo

12. if UAViflies beyond the border or disconnected then

(11)

14. 取消 UAVi的移動

16. end if

17. end for

18. store(st,at,rt,st+1)inB,st←st+1

19. for UAVi:= 1,…,Ndo

20. 獲取隨機(jī)樣本(sj,aj,rj,sj+1)∈B

22. 用最小的lossL(θQi)更新評價(jià)網(wǎng)絡(luò)權(quán)重θQi.

23.用▽θμiJ(θμi)更新演員網(wǎng)絡(luò)權(quán)重θμi

24.更新兩個(gè)目標(biāo)網(wǎng)絡(luò)權(quán)重θQ′i,θμ′i

25. end for

26. end for

27.end for

5 仿真實(shí)驗(yàn)與性能分析

本節(jié)通過一系列的仿真實(shí)驗(yàn),對本文提出的解決方案(DC-DRL)進(jìn)行性能分析與評價(jià).本章節(jié)首先介紹實(shí)驗(yàn)場景的設(shè)置,然后分析結(jié)果.

5.1 實(shí)驗(yàn)設(shè)置

本文中的實(shí)驗(yàn)使用TensorFlow 1.0和Python 3.7進(jìn)行.在仿真實(shí)驗(yàn)中,首先設(shè)定目標(biāo)區(qū)域大小為80m×80m的一片區(qū)域,并切割為16塊熱點(diǎn)區(qū)域.本文將 DC-DRL與一些常用的緩存文件置換方法進(jìn)行了比較,例如在內(nèi)容替代策略上,本文通過將DC-DRL策略與先入先出(First Input First Output,FIFO)策略、最近最少使用(least recently used,LRU)策略、最不經(jīng)常使用(Least Frequently Used,LFU)策略等常用策略相比較,得出本文使用LSTM進(jìn)行預(yù)測的優(yōu)勢,在無人機(jī)調(diào)度方面,本文設(shè)置了動態(tài)無人機(jī)與懸停無人機(jī)的對比實(shí)驗(yàn).在具體細(xì)節(jié)上,對于軌跡設(shè)計(jì),本文選擇了兩個(gè)基準(zhǔn)線進(jìn)行比較:

1.懸停:為避免碰撞,無人機(jī)懸停在用戶的集群中心.

2.圓形飛行軌跡:無人機(jī)以100m的半徑和恒定的速度周期性地圍繞簇中心運(yùn)動.

本文通過大量實(shí)驗(yàn)在神經(jīng)網(wǎng)絡(luò)中找到合適的超參數(shù).在實(shí)驗(yàn)中設(shè)置學(xué)習(xí)率為0.001,批大小Bs=32,更新迭代數(shù)Bup=200,緩存空間大小C=2000,折扣因子γd=0.9.本文使用一個(gè)兩層全連接神經(jīng)網(wǎng)絡(luò)作為目標(biāo)和評估網(wǎng)絡(luò),隱藏層的神經(jīng)單元數(shù)為120.

5.2 實(shí)驗(yàn)數(shù)據(jù)與分析

在無人機(jī)基站(DBS)緩存模擬步驟中,本文考慮了兩個(gè)實(shí)驗(yàn)因素:緩存大小和緩存替換策略.緩存大小決定了一次可以在高速緩存中保存的內(nèi)容量.當(dāng)開辟的存儲空間填滿時(shí),系統(tǒng)需要遵從緩存替換策略確定從緩存中刪除哪些對象.本文提出的DC-DRL策略在緩存替代策略上使用基于文件流行度的替換方法.在對比實(shí)驗(yàn)上,本文考慮了5種緩存替換策略:最優(yōu)緩存策略、本文提出策略(DC-DRL)、按照對象到達(dá)的順序刪除對象(FIFO)、根據(jù)最近使用情況刪除對象(LRU)、刪除不受歡迎的對象(LFU).后3種策略不再贅述,其中,最優(yōu)緩存策略表示提前預(yù)知下一時(shí)段的所需文件從而進(jìn)行內(nèi)容預(yù)取的緩存策略,是一種理想狀態(tài),實(shí)際情況不可達(dá)到.

仿真實(shí)驗(yàn)中,在一個(gè)熱點(diǎn)區(qū)域上,本文中使用在校園網(wǎng)絡(luò)場景中抓取的一小時(shí)的帶有時(shí)間戳的短視頻文件序列作為輸入提供給邊緣緩存中央控制器,并以章節(jié)3.3中方法切割文件為尺寸小于512Kb的小文件,模擬器生成實(shí)驗(yàn)的緩存命中率作為輸出.實(shí)驗(yàn)使用緩存命中率作為緩存性能的主要性能指標(biāo),著眼于優(yōu)化目標(biāo)對所使用的緩存空間和替換策略的敏感性.

本文在DBS靜止?fàn)顟B(tài)下對DC-DRL和其它傳統(tǒng)緩存替代策略得到的平均緩存命中率進(jìn)行了比較.緩存文件數(shù)在文件庫中文件數(shù)總數(shù)的占比在本文中被定義為緩存率,如圖3所示,當(dāng)緩存率處于20%以下時(shí),本文提出的基于長短期神經(jīng)網(wǎng)絡(luò)的緩存策略性能明顯優(yōu)于傳統(tǒng)的緩存策略.例如:當(dāng)緩存率為10%時(shí),本文提出算法比LRU算法的系統(tǒng)平均緩存命中率高出接近4%,當(dāng)需要80%的平均緩存命中率時(shí),LRU策略與本文提出的基于長短期神經(jīng)網(wǎng)絡(luò)的替換策略相比還需要約一半的緩存率,LFU算法比本文提出算法所需緩存率高出一倍,傳統(tǒng)緩存算法在利用緩存文件歷史流行度信息上與機(jī)器學(xué)習(xí)的方法比較更為機(jī)械化,在處理更長的歷史信息的能力上不如長短期記憶神經(jīng)網(wǎng)絡(luò).LRU忽略了緩存內(nèi)容的大小和訪問延遲.LFU在使用時(shí)也需要有無效機(jī)制的支持.

圖3 系統(tǒng)平均緩存命中率性能比較Fig.3 Systemaverage cache hit rate comparison

學(xué)習(xí)率(Learning rate)是監(jiān)督學(xué)習(xí)以及深度學(xué)習(xí)中重要的超參數(shù),其決定對輸出誤差的利用程度.合理設(shè)置學(xué)習(xí)率能夠使目標(biāo)函數(shù)在合適的時(shí)間內(nèi)收斂到局部最小值.如圖4所示,學(xué)習(xí)率不能太大也不能太小,因?yàn)檫^大的學(xué)習(xí)率會引起收斂過程的波動,而過小的學(xué)習(xí)率容易導(dǎo)致訓(xùn)練速度變慢.本文將深度強(qiáng)化學(xué)習(xí)的學(xué)習(xí)率設(shè)置在0.001～0.01,并最終選擇0.001、0.002和0.005這3個(gè)有區(qū)別和代表性的學(xué)習(xí)率下的實(shí)際結(jié)果.從圖中可以看出,0.001是這個(gè)場景中的最佳選擇,因?yàn)橄到y(tǒng)平均緩存命中率會隨著訓(xùn)練過程平滑地增加到收斂.

圖5比較了不同數(shù)量無人機(jī)基站下的平均緩存命中率.無人機(jī)采用圓形包裝算法單獨(dú)部署,以最大限度地?cái)U(kuò)大覆蓋范圍,根據(jù)平均覆蓋分?jǐn)?shù)閾值選擇鏈路方案.用戶數(shù)、無人機(jī)可服務(wù)的最大用戶數(shù)、文件總數(shù)和緩存大小分別為15、10、10和5.很明顯,命中率隨著無人機(jī)基站的數(shù)量增加而增加.使用隨機(jī)替代算法的結(jié)果保持不變,因?yàn)樗鼪]有利用文件內(nèi)容的特性.隨著無人機(jī)數(shù)量逐漸增長,在服務(wù)區(qū)域內(nèi)服務(wù)區(qū)的重疊面積越來越多,鏈接越來越穩(wěn)定.在本文的仿真設(shè)置背景下,4個(gè)無人機(jī)協(xié)作已經(jīng)可以取得逼近最優(yōu)的結(jié)果.

圖4 具有不同學(xué)習(xí)率的AC算法與訓(xùn)練集數(shù)的收斂性Fig.4 Convergence of AC algorithm with different learning rates versus the number of training episodes

圖5 系統(tǒng)平均緩存命中率與無人機(jī)數(shù)量關(guān)系Fig.5 Average cache hit rate versus the number of UAVs

6 結(jié)束語

本文對邊緣計(jì)算的無人機(jī)基站內(nèi)容緩存問題進(jìn)行了研究,設(shè)計(jì)了一種基于深度強(qiáng)化學(xué)習(xí)的無人機(jī)基站緩存策略,該策略可以對系統(tǒng)模型進(jìn)行多因素、多目標(biāo)的聯(lián)合優(yōu)化,根據(jù)多份緩存文件基于時(shí)間所得出的流行度,進(jìn)行差異化緩存放置,并將預(yù)測結(jié)果作為指導(dǎo)無人機(jī)調(diào)度的因素,使緩存在無人機(jī)基站的MEC服務(wù)器中的內(nèi)容更容易被該區(qū)域中的用戶請求,使緩存內(nèi)容的總命中率最大化.仿真結(jié)果表明,使用本文所提策略所達(dá)到的系統(tǒng)平均緩存命中率明顯優(yōu)于傳統(tǒng)流行度預(yù)測方法以及固定基站的方法.本文策略有效地提高了緩存文件的總請求命中率,然而在實(shí)際應(yīng)用中,流媒體文件是多種多樣的,如何針對不同種類文件設(shè)計(jì)應(yīng)算法提高系統(tǒng)效用.下一步研究工作的重點(diǎn)是,在其他具體應(yīng)用場景下,針對不同的文件設(shè)計(jì)有效的策略,以進(jìn)一步提高研究的實(shí)用性.