面向天地一體化網(wǎng)絡(luò)的計算卸載算法

耿 蓉, 王宏艷, 劉 暢, 徐 賽

(1. 東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 遼寧 沈陽 110169; 2. 東軟集團(tuán)股份有限公司, 遼寧 沈陽 110179)

天地一體化網(wǎng)絡(luò)[1-2]由天基骨干網(wǎng)、天基邊緣接入網(wǎng)以及地基節(jié)點(diǎn)網(wǎng)(地基骨干網(wǎng))[3-4]三部分組成.由于目前衛(wèi)星數(shù)量不足、衛(wèi)星類型單一、在軌升級困難帶來的計算資源受限問題使得天基信息系統(tǒng)的綜合效能受到阻礙,并且在空、天、地維度上也不能很好地配合.因此,本文將計算卸載[5]技術(shù)結(jié)合到天地一體化網(wǎng)絡(luò)中,以緩解天地一體化網(wǎng)絡(luò)存在的問題.針對由于衛(wèi)星數(shù)量不足、類型單一、再組升級困難帶來的計算資源受限和“天弱地強(qiáng)”等問題,給出了相應(yīng)的最優(yōu)卸載算法,將任務(wù)卸載到合適的卸載站點(diǎn)進(jìn)行計算,降低網(wǎng)絡(luò)時延和能耗,以便高效地完成任務(wù).本文旨在利用計算卸載技術(shù)均衡天地一體化網(wǎng)絡(luò)的負(fù)載,在低時延、低能耗的情況下完成任務(wù),為未來新型網(wǎng)絡(luò)處理復(fù)雜的密集計算型任務(wù)提供理論基礎(chǔ).

目前,國內(nèi)外學(xué)者對一般移動云計算系統(tǒng)中的計算卸載問題進(jìn)行了廣泛的研究[6-8].文獻(xiàn)[9-10]給出了計算卸載的經(jīng)典模型.然而在面對終端計算能力不足的問題時,文獻(xiàn)[11]提出了基于Cloud-RAN的移動云計算系統(tǒng)中近乎最優(yōu)的能效方案；文獻(xiàn)[12]表征了計算和通信負(fù)載之間的基本權(quán)衡；文獻(xiàn)[5]提出了通信和計算功耗之間的最佳權(quán)衡；文獻(xiàn) [13]提出了一種基于MDP的卸載算法,該算法可以幫助用戶決定是否將多階段移動應(yīng)用程序中相同應(yīng)用階段的計算任務(wù)卸載給附近的所有cloudlet(移動設(shè)備或者是計算機(jī),提供附近移動設(shè)備使用的計算能力,用戶可直接訪問附近移動設(shè)備的資源).此外,文獻(xiàn)[14]給出用戶的一組任務(wù),此任務(wù)可以在用戶和cloudlet上并行執(zhí)行,用戶的目標(biāo)是向每個cloudlet分配最優(yōu)數(shù)量的任務(wù),使任務(wù)執(zhí)行獎勵最大化,而處理成本最小化.可見,目前的研究都是基于傳統(tǒng)的本地策略來減輕移動系統(tǒng)中有限資源的限制,而面對天地一體化這種復(fù)雜的網(wǎng)絡(luò)以上解決方法是遠(yuǎn)遠(yuǎn)不夠的.

因此,為了解決天地一體化網(wǎng)絡(luò)中的終端設(shè)備在存儲、計算和能耗方面的資源需求與運(yùn)行越來越復(fù)雜的移動應(yīng)用程序之間的矛盾日益突出的問題,本文突破傳統(tǒng)的本地執(zhí)行策略,為在高軌骨干節(jié)點(diǎn)、地基骨干節(jié)點(diǎn)和邊緣接入節(jié)點(diǎn)服務(wù)器上執(zhí)行任務(wù)卸載提供了新的理論和方法,提出天地一體化網(wǎng)絡(luò)的本地-骨干-邊緣接入節(jié)點(diǎn)的三層計算卸載模型,此模型應(yīng)用每一層的全部卸載站點(diǎn)數(shù),使卸載的性能和可伸縮性得到提高,解決了計算資源受限的難題;同時通過此模型所給出的各項(xiàng)指標(biāo)以及約束條件,本文提出基于DQN算法來制定出最優(yōu)的卸載策略,使任務(wù)在低時延、低能耗的情況下高效完成,更加體現(xiàn)了此模型的應(yīng)用價值.

1 天地一體化網(wǎng)絡(luò)中的計算卸載模型設(shè)計

1.1 卸載模型的建立

1) 卸載站點(diǎn)模型建立.卸載站點(diǎn)(offloadee)模型的建立需要考慮天地一體化網(wǎng)絡(luò)的結(jié)構(gòu)與特點(diǎn),建立與之相對應(yīng)的模型.卸載站點(diǎn)用一個五元組Oon(con,fon,don,von,non)來表示,其中o是卸載站點(diǎn)數(shù),n是終端設(shè)備數(shù),con為卸載站點(diǎn)的終端設(shè)備總計算能力(本文用CPU來體現(xiàn))，fon為剩余計算能力(本文用當(dāng)前時刻所能提供的CPU來表示)，don為距離(卸載站點(diǎn)與卸載任務(wù)所在移動端的距離)，von為速度矢量(卸載站點(diǎn)的運(yùn)動速度大小與方向)，non為網(wǎng)絡(luò)(當(dāng)前站點(diǎn)的網(wǎng)絡(luò)連接狀況).

2) 任務(wù)模型建立. 每個任務(wù)都可以用一個四元組Vin(win,ain,bin,vin)來描述,其中,i是任務(wù),win為終端設(shè)備n的第i個任務(wù)的計算量，ain為任務(wù)i卸載的輸入數(shù)據(jù)，bin為卸載任務(wù)i執(zhí)行完畢返回數(shù)據(jù),vin為任務(wù)i所在終端設(shè)備n的速度矢量(包括速度大小和速度的方向).得到任務(wù)特性的參數(shù)后,在1.2節(jié)建立任務(wù)卸載的開銷模型.

3) 通信模型建立.當(dāng)?shù)趎個終端設(shè)備的第i個計算任務(wù)需要執(zhí)行時,當(dāng)前終端就會發(fā)送任務(wù)卸載請求,其他的計算節(jié)點(diǎn)就會給出響應(yīng),終端根據(jù)響應(yīng)來決定是直接卸載還是劃分后卸載,以及是本地執(zhí)行還是卸載到其他站點(diǎn)上.在這里,din=0表示終端設(shè)備n的任務(wù)i在本地執(zhí)行,不進(jìn)行卸載.din>0表示任務(wù)被卸載到其他卸載站點(diǎn)來執(zhí)行.另外,在卸載過程中,用式(1)所示的信道速率來選擇合適的信道進(jìn)行數(shù)據(jù)傳輸,

(1)

同時,本文也將采用馬爾可夫信道模型來估計任務(wù)卸載過程中的信道狀況.下面給出有限狀態(tài)馬爾可夫信道模型.

本文使用Gilbert-Elliott通道建立通信鏈路,該信道模型是具有兩種狀態(tài)的馬爾可夫鏈:良好(用0表示)或壞(用1表示).如果信道處于良好狀態(tài),則以高速率(v0)傳輸數(shù)據(jù),如果信道處于壞的狀態(tài),則以低速率(v1)傳輸數(shù)據(jù).如果第n個時間單位期間信道狀態(tài)φn良好,則記φn=0,否則φn=1.因此,通道狀態(tài)φ的狀態(tài)轉(zhuǎn)移矩陣P由式(2)給出:

(2)

式中：p00是表示信道由良好狀態(tài)轉(zhuǎn)化為良好狀態(tài)的概率；p01是由良好狀態(tài)轉(zhuǎn)化為壞狀態(tài)概率；p10是壞狀態(tài)轉(zhuǎn)化為良好狀態(tài)的概率；p11是壞狀態(tài)轉(zhuǎn)化為壞狀態(tài)概率.

穩(wěn)態(tài)分布表示為μ=(μ0,μ1),其中μ0,μ1分別表示信道處于良好或壞狀態(tài)的穩(wěn)態(tài)概率.兩種狀態(tài)的穩(wěn)態(tài)概率計算公式為μ0=p10/(p10+p01),μ1=p01/(p10+p01). 因此,如果假設(shè)終端設(shè)備的傳輸功率是靜態(tài)的,則預(yù)期的穩(wěn)態(tài)傳輸速率vμ可表示為vμ=μ0v0+μ1v1.

1.2 任務(wù)卸載開銷計算

根據(jù)上面所給出的任務(wù)和卸載站點(diǎn)的簡單模型,可以得到任務(wù)在不同卸載情況下的卸載開銷模型.下面給出任務(wù)卸載到天地一體化網(wǎng)絡(luò)中不同站點(diǎn)的卸載開銷模型,分別是本地執(zhí)行建模、骨干節(jié)點(diǎn)執(zhí)行建模以及邊緣接入節(jié)點(diǎn)執(zhí)行建模.

(3)

本地執(zhí)行的能耗為

(4)

其中δin代表終端設(shè)備執(zhí)行計算的能耗系數(shù).

一個任務(wù)被執(zhí)行前,要求其所有直接先驅(qū)任務(wù)必須已經(jīng)完成.下面給出任務(wù)就位時間的概念.

定義1就位時間是當(dāng)前執(zhí)行任務(wù)的所有先驅(qū)任務(wù)完成的最早時間,對于本地執(zhí)行的就位時間表示為

(5)

綜上,終端設(shè)備n的任務(wù)i在本地執(zhí)行時的完成時間為本地執(zhí)行時間與本地計算時的就位時間之和,即

(6)

根據(jù)式(4)和式(6),可以給出任務(wù)本地執(zhí)行的開銷表達(dá)式,本文將其定義為本地執(zhí)行的計算能耗代價.

定義2能耗代價EEC(energy efficiency commitment)是任務(wù)執(zhí)行的能源消耗與所需計算完成時間的權(quán)重之和.下面給出任務(wù)在本地執(zhí)行時的EEC表達(dá)式:

(7)

(8)

(9)

由式(8)和式(9)可知卸載到骨干節(jié)點(diǎn)執(zhí)行的時間總開銷Tb為

(10)

考慮任務(wù)間通常具有依賴性,任務(wù)i在骨干節(jié)點(diǎn)的就位時間定義為

(11)

(12)

由于骨干節(jié)點(diǎn)有較強(qiáng)的計算能力,因此,對任務(wù)在骨干節(jié)點(diǎn)的計算能耗忽略不計.用Es,Er分別代表任務(wù)發(fā)送時的能量消耗以及任務(wù)接收時的能量消耗,則骨干節(jié)點(diǎn)總的能量開銷Eb為

(13)

根據(jù)式(12)和式(13),可以計算出任務(wù)卸載到骨干節(jié)點(diǎn)的能耗代價EEC:

(14)

由式(14)可以看出,終端設(shè)備n的數(shù)據(jù)傳輸速率越高,則計算任務(wù)卸載過程的時延和能耗越低.

(15)

(16)

由式(15)和式(16)可知卸載到邊緣計算節(jié)點(diǎn)的總時間開銷Th為

(17)

在建立上述模型之前,還需要具體分析一下邊緣接入節(jié)點(diǎn)卸載的延遲表達(dá)式.下面是邊緣計算卸載的時延分析.

如果計算延遲很大,則總延遲主要取決于計算延遲.此時延遲由發(fā)送時間、卸載時間以及接收時間三部分組成,其表達(dá)式為

(18)

其中，m代表邊緣計算節(jié)點(diǎn)的個數(shù).

如果計算延遲很短,則總延遲主要取決于通信延遲,即發(fā)送時間和接收時間,其延遲表達(dá)式為

(19)

從式(18)和式(19)的延遲表達(dá)式可以得到邊緣計算延遲表達(dá)式為

(20)

用Ec,Es,Er分別代表任務(wù)本身執(zhí)行計算卸載(computation)時的能耗開銷、數(shù)據(jù)發(fā)送到卸載站點(diǎn)時的能耗開銷以及卸載終端進(jìn)行數(shù)據(jù)接收時的能耗開銷,則邊緣接入節(jié)點(diǎn)總的能量開銷表示為Eh:

(21)

考慮任務(wù)間通常具有依賴性,在邊緣接入節(jié)點(diǎn)的就位時間定義為

(22)

(23)

由于邊緣接入節(jié)點(diǎn)通常具有分布廣泛的特點(diǎn),因此,任務(wù)在邊緣接入節(jié)點(diǎn)執(zhí)行完成后計算結(jié)果返回的能耗忽略不計.則總的能量開銷表示為Eh:

(24)

根據(jù)式(23)和式(24),可以計算出任務(wù)卸載到邊緣接入節(jié)點(diǎn)的能耗代價:

(25)

2 基于DQN的計算卸載算法設(shè)計

通過對任務(wù)、卸載站點(diǎn)的建模以及對開銷模型的設(shè)計,已經(jīng)得到了任務(wù)執(zhí)行卸載的各項(xiàng)需求與指標(biāo),將其與任務(wù)卸載執(zhí)行模型、信道模型的特點(diǎn)進(jìn)行綜合考慮,并在本文有限狀態(tài)的馬爾可夫鏈的計算卸載環(huán)境下,本文提出了基于DQN(deep Q-learning network)的卸載算法以得到更優(yōu)的卸載策略,高效地完成低時延、低損耗卸載.

2.1 傳統(tǒng)的Q學(xué)習(xí)(Q-learning)算法

Q學(xué)習(xí)算法是利用動作值函數(shù)尋找最優(yōu)的策略,尋找到對于每個狀態(tài)來說的最佳動作,完成任務(wù)最優(yōu)卸載.具體的一些過程如下所述.

Q學(xué)習(xí)算法中智能體通過即時動作值和累積獎勵值進(jìn)行狀態(tài)的轉(zhuǎn)移決策,針對計算卸載的馬爾可夫模型,當(dāng)智能終端任務(wù)進(jìn)行卸載時,對周圍的信道狀態(tài)進(jìn)行估計,對計算能力進(jìn)行監(jiān)測,以(Oi,wtotal)為任務(wù)的處理狀態(tài),其中Oi代表當(dāng)前處理任務(wù)的卸載站點(diǎn)(offloadee)的編號,wtotal表示截止到當(dāng)前狀態(tài),處理的任務(wù)數(shù)據(jù)總量;以(Oi,wi)為任務(wù)下一步要進(jìn)行的動作,其中wi表示下一步動作時要卸載的數(shù)據(jù)量大小,智能終端卸載任務(wù)每一步的即時回報(獎勵)函數(shù)用總時延和總能耗線性表達(dá)式的倒數(shù)來計算.在Q學(xué)習(xí)算法中,每個狀態(tài)-動作組都需要計算并將其對應(yīng)的Q值存儲在一個表中,然后通過優(yōu)化可迭代計算得到Q(s,a)的值來逼近最優(yōu)值函數(shù),進(jìn)而得到最優(yōu)卸載策略.

2.2 基于DQN的計算卸載算法設(shè)計

通過上面對于Q學(xué)習(xí)算法的描述可以看出,Q學(xué)習(xí)雖然可以通過獲得最大的獎勵來解決問題,但并不理想.并且在實(shí)際問題中,天地一體化網(wǎng)絡(luò)卸載環(huán)境復(fù)雜多變,可能的狀態(tài)會超過 1萬.在 Q 表中存儲所有的Q值,會導(dǎo)致Q(s,a)非常大,這樣就很難得到足夠的樣本來遍歷每個狀態(tài),從而導(dǎo)致算法的失敗.因此,提出使用深度神經(jīng)網(wǎng)絡(luò)來估計Q(s,a),而不是計算每個狀態(tài)動作對的Q值,這就是DQN的基本思想.

DQN算法就是基于傳統(tǒng)Q學(xué)習(xí)算法基礎(chǔ)上利用深度卷積神經(jīng)網(wǎng)絡(luò)CNN來加快Q學(xué)習(xí)算法中卸載過程的收斂速度.在本研究中設(shè)置初始的回報函數(shù)為0,回報函數(shù)用總時延和總能耗線性表達(dá)式的倒數(shù)來計算,因此將1.2小節(jié)開銷模型進(jìn)行整合,首先給出t時刻第i個任務(wù)的時延Tti和能耗Eti的表達(dá)式:

(26)

(27)

因?yàn)楸疚牡男遁d任務(wù)處于天地一體化網(wǎng)絡(luò)中,所以offloadee有邊緣接入節(jié)點(diǎn)、天基骨干節(jié)點(diǎn)和地基骨干節(jié)點(diǎn),對于不同offloadee的時延和能耗的計算方式也不同,計算方式如式(26)和式(27)所示,回報函數(shù)如式(28)所示:

rt=1/[αTti+βEti].

(28)

式中,α和β分別代表時延和能耗的權(quán)重,其最大值為1.

設(shè)在t時刻,智能終端選取動作at環(huán)境從狀態(tài)st轉(zhuǎn)移到st+1所給出的獎例為rt，則rt=r(st,at,st+1);st和rt是決定st+1與rt的概率分布的因素,且Qt為t時刻開始時狀態(tài)動作對的動作估計值.在整個過程中動作的更新迭代規(guī)則如式(29)所示:

(29)

其中,η為學(xué)習(xí)率,代表學(xué)習(xí)速度,其值越大代表收斂速度越快,但值如果過大則可能造成不穩(wěn)定的收斂,影響最優(yōu)的結(jié)果.

在DQN算法中利用深度CNN壓縮狀態(tài)空間并加快Q學(xué)習(xí)算法中卸載過程的收斂速度,神經(jīng)網(wǎng)絡(luò)將每一個動作的Q(s,a)值轉(zhuǎn)換成Q網(wǎng)絡(luò),然后利用反向傳播和梯度下降方法使得損失函數(shù)最小化.損失函數(shù)如式(30)所示:

(30)

其中,γ是折扣因子,決定智能體對于長遠(yuǎn)回報的觀望程度,值越接近1表明越關(guān)注長遠(yuǎn)回報,越接近0表明越關(guān)注當(dāng)即回報.

對于每個卸載策略,深度CNN都是Q值的非線性近似值,這樣就加快了Q學(xué)習(xí)方案的收斂速度.下面給出DQN原理示意圖,見圖1.

通過以上分析,基于DQN的計算卸載策略算法如表1所示.

圖1 DQN原理示意圖

表1 基于DQN的計算卸載算法

其中第9步實(shí)現(xiàn)了將經(jīng)驗(yàn)值存儲到記憶庫中,然后對Q網(wǎng)絡(luò)進(jìn)行訓(xùn)練.DQN中存在1個記憶庫,它能夠?qū)W習(xí)現(xiàn)在正在經(jīng)歷著的, 也可以學(xué)習(xí)從前經(jīng)歷過的, 甚至是學(xué)習(xí)別人的經(jīng)歷.所以每一次基于 DQN算法變更的期間,都能夠隨機(jī)抽取一些以往的經(jīng)歷來進(jìn)行學(xué)習(xí).正是因?yàn)椴捎昧穗S機(jī)抽取這種做法,才能夠達(dá)到打亂經(jīng)歷之間相關(guān)性的目的,使得神經(jīng)網(wǎng)絡(luò)能夠更有效率地進(jìn)行更新.

3 算法仿真與性能分析

本文的卸載仿真是利用Python+NS網(wǎng)絡(luò)仿真軟件進(jìn)行的.假設(shè)一個場景:在一定范圍內(nèi)模擬天地一體化網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn),考慮到天地一體化網(wǎng)絡(luò)結(jié)構(gòu)特征,擬選取2個天基骨干節(jié)點(diǎn)、2個地基骨干節(jié)點(diǎn)、6個邊緣接入節(jié)點(diǎn)的模式進(jìn)行仿真.即1個卸載終端(offloader),10個計算卸載站點(diǎn)(offloadee),其中4個用來模仿天基或者地基骨干節(jié)點(diǎn)的計算卸載站點(diǎn)(B_offloadee),剩下的均為邊緣接入節(jié)點(diǎn)的計算卸載站點(diǎn)(E_offloadee),它們在不同緯度上呈現(xiàn)隨機(jī)分布.所有的卸載站點(diǎn)(offloadees)之間通過無線網(wǎng)絡(luò)連接.offloadee為offloader提供任務(wù)計算卸載服務(wù).由上述分析,采用時延和能耗為指標(biāo),選擇經(jīng)典計算卸載算法[15](基于Lyapunov優(yōu)化的卸載算法:此算法在計算卸載技術(shù)中應(yīng)用最為廣泛)和基于DQN的計算卸載算法與Q學(xué)習(xí)算法進(jìn)行仿真并對比分析評價算法性能.

在進(jìn)行算法性能分析之前,利用Python散點(diǎn)圖模擬天地一體化網(wǎng)絡(luò)中計算節(jié)點(diǎn)結(jié)構(gòu)的分布和散點(diǎn)分布圖,如圖2所示.其中紅色散點(diǎn)代表骨干節(jié)點(diǎn),最上邊的6個紅色散點(diǎn)代表天地一體化網(wǎng)絡(luò)中最上層,處于最高位置,擁有強(qiáng)大計算能力的6顆高軌衛(wèi)星,具有在固定軌道上移動的特點(diǎn).最下面的5個紅色散點(diǎn)代表的是地基骨干節(jié)點(diǎn),其分布在地面,位置固定,計算能力在理論上最強(qiáng).處于中間位置的藍(lán)色散點(diǎn)是邊緣接入網(wǎng)絡(luò)的計算節(jié)點(diǎn),其數(shù)量不固定,具有移動性,以分布式方式呈現(xiàn),計算能力要遠(yuǎn)小于其他兩種計算節(jié)點(diǎn),正是由于其分布式特點(diǎn),使其在與卸載終端距離方面更具優(yōu)勢.

圖2 計算節(jié)點(diǎn)分布圖

基于以上模擬天地一體化網(wǎng)絡(luò)的計算節(jié)點(diǎn)進(jìn)行仿真,來分析Lyapunov算法(經(jīng)典計算卸載算法)、Q學(xué)習(xí)算法、DQN算法在時延、能耗指標(biāo)下的性能對比.

卸載過程中的時延對比結(jié)果如圖3所示,基于Lyapunov優(yōu)化的卸載算法最大,通過DQN算法的計算卸載策略在時延的花費(fèi)上要低于其他算法.

能耗對比結(jié)果如圖4所示.對于某些能耗不充足的卸載終端offloader來說,其對降低能耗的需求要強(qiáng)于對降低時延的需求,即用時延來換取能耗,因此在天地一體化網(wǎng)絡(luò)任務(wù)計算卸載中能耗也顯得至關(guān)重要.

由圖3和圖4可知,采取不同卸載算法,時延開銷、能耗開銷的整體趨勢是一樣的,即采取DQN算法可以同時在時延和能耗開銷上進(jìn)行優(yōu)化.

圖3 時延對比分析圖

圖4 能耗對比分析圖

在1.2節(jié)對卸載開銷進(jìn)行建模的過程中,就提到權(quán)重的問題,而上述對于時延和能耗的分析是沒有設(shè)置時延和能耗各自所占的權(quán)重進(jìn)行分析的.下文給出不同權(quán)重設(shè)置時,采用不同卸載算法情況下時延和能耗的總開銷對比.

由圖5和圖6可知,當(dāng)時延和能耗權(quán)重采用

不同的占比時,DQN算法的卸載策略總開銷都是更小的,再一次證明本文算法的有效性.

4 結(jié) 語

針對天地一體化網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn),結(jié)合分析計算卸載技術(shù)的特點(diǎn)和應(yīng)用場景,本文提出將計算卸載技術(shù)應(yīng)用到網(wǎng)絡(luò)中,在理論上可以對任務(wù)處理的高效性起到極大的推動作用.同時為了解決計算資源受限問題,建立了與天地一體化網(wǎng)絡(luò)體系結(jié)構(gòu)一一對應(yīng)的卸載模型,不同卸載站點(diǎn)在時延上的開銷比例各不相同.在建立時延和能耗的總開銷模型中,提出了設(shè)置權(quán)重的思想,可以讓卸載端有所取舍.最后對本文提出的DQN計算卸載算法進(jìn)行仿真,從時延開銷、能耗開銷等方面驗(yàn)證算法的有效性.仿真結(jié)果表明,采取DQN計算卸載算法可以同時在時延和能耗開銷上進(jìn)行優(yōu)化,高效地完成卸載過程.