趙天祺,趙洺月,師 越,鄭曠宇

(北京航空航天大學(xué) 電子信息工程學(xué)院,北京 100191)

0 引言

近年來,OneWeb和StakLink等衛(wèi)星網(wǎng)絡(luò)快速發(fā)展,為天地協(xié)同計算帶來了機(jī)遇和挑戰(zhàn)。隨著衛(wèi)星技術(shù)的不斷發(fā)展,衛(wèi)星將配備高速星間鏈路進(jìn)行數(shù)據(jù)通信[1]和先進(jìn)的機(jī)載計算系統(tǒng)[2-3],使得數(shù)據(jù)傳輸可以實現(xiàn)低延遲和高吞吐量[4-6]。在偏遠(yuǎn)地區(qū),難以連接云邊緣網(wǎng)絡(luò)的終端設(shè)備可以將任務(wù)卸載到衛(wèi)星而不是云中心,顯著提高通信質(zhì)量,降低終端任務(wù)的處理時延。

許多常見的終端任務(wù),如無人駕駛、圖像識別等,通常內(nèi)部都具有一定的并行與依賴關(guān)系[7-9]。并且隨著協(xié)同計算的發(fā)展,一個完整的任務(wù)也可以被分解為許多個并行子任務(wù)分別在不同設(shè)備上進(jìn)行計算,如機(jī)器學(xué)習(xí)中將訓(xùn)練集分解為不同小訓(xùn)練集后分配到不同計算設(shè)備上[10-11]。邊緣服務(wù)器分配多并行依賴任務(wù)的一個重要問題就是如何將任務(wù)卸載到合適的服務(wù)器,從而在保證任務(wù)依賴關(guān)系順序的前提下,減少由于并行子任務(wù)搶占服務(wù)器引起的服務(wù)器擁塞,降低任務(wù)整體卸載時延[12-13]。

然而,衛(wèi)星的高動態(tài)性、有限的計算資源對依賴任務(wù)的卸載策略優(yōu)化帶來了很大的挑戰(zhàn)。低地球軌道(Low Earth Orbit,LEO)具有機(jī)動性和靈活性,這使得衛(wèi)星與地面設(shè)備之間的連接隨著時間的推移而變化,從而影響了終端能否成功向衛(wèi)星卸載任務(wù)[14-16]。

并且,在傳統(tǒng)的依賴關(guān)系任務(wù)卸載策略中,主要通過對子任務(wù)進(jìn)行優(yōu)先度排序來確定子任務(wù)調(diào)度順序[17-19]。這些方法在調(diào)度任務(wù)時主要考慮子任務(wù)間的依賴關(guān)系,而不直接考慮任務(wù)間的并行性,所以根據(jù)優(yōu)先度調(diào)度的方法對于簡單的串行依賴任務(wù)具有較好的性能表現(xiàn),但對于具有并行結(jié)構(gòu)的依賴性任務(wù)可能并不十分適合。然而,一個子任務(wù)往往與其他任務(wù)同時具有多個復(fù)雜的依賴與并行關(guān)系,或者說子任務(wù)間的并行結(jié)構(gòu)與依賴關(guān)系往往并不獨立,無法通過在原串行任務(wù)的基礎(chǔ)上直接添加優(yōu)化并行任務(wù)的算法來實現(xiàn)。

因此,本文提出了修剪路徑(PruningPath)算法,旨在建立一個星地協(xié)同任務(wù)卸載系統(tǒng),在滿足依賴任務(wù)約束的前提下將設(shè)備卸載問題轉(zhuǎn)為最短路徑問題,并通過修建設(shè)備保證算法的低復(fù)雜度。

1 問題建模

1.1 系統(tǒng)模型

考慮在空地融合網(wǎng)絡(luò)中構(gòu)建一個協(xié)同計算框架,如圖1所示。它由四部分組成:衛(wèi)星、云、邊緣和終端,設(shè)備總數(shù)為m。衛(wèi)星均勻分布在近地軌道上,具有通信和計算能力。認(rèn)為云具有非常強(qiáng)的計算能力和多核計算能力,因此可以認(rèn)為云上任務(wù)的計算時間為0,且分配到云上的多個并行任務(wù)可以同時處理,不會產(chǎn)生等待能耗。相對而言,衛(wèi)星、邊緣和終端的計算能力較弱,同時只能處理一項任務(wù),因此分配給邊緣和終端的任務(wù)會產(chǎn)生計算延遲,且當(dāng)多個并行任務(wù)分配給一個邊緣或終端時,由于排隊會產(chǎn)生等待延遲。在系統(tǒng)模型中,假設(shè)兩個計算設(shè)備在一定距離內(nèi)是可連接的,則二者可以相互傳輸數(shù)據(jù)。假設(shè)每個任務(wù)傳輸?shù)拇笮∮邢?因此多個任務(wù)數(shù)據(jù)可以在同一信道中同時傳輸。

圖1 系統(tǒng)框架圖Fig.1 System frame diagram

整個系統(tǒng)協(xié)同計算步驟如下:當(dāng)一個依賴任務(wù)到達(dá)時,系統(tǒng)將其視為一系列串聯(lián)的子任務(wù)集;同時,在任務(wù)到達(dá)時判斷衛(wèi)星的可用性,并將終端設(shè)備、云和當(dāng)前時刻可用的衛(wèi)星構(gòu)建為協(xié)同任務(wù)卸載系統(tǒng);隨后,系統(tǒng)將每個任務(wù)的卸載策略對應(yīng)到一個路徑節(jié)點上,計算相應(yīng)的延遲并將其分配為路徑權(quán)重,得到時延路徑模型,從而將依賴任務(wù)卸載問題轉(zhuǎn)化為最短路徑問題。

1.2 依賴任務(wù)定義

定義一個具有m個原子性子任務(wù)的依賴任務(wù)為A:

A={a1,a2,…,an} 。

(1)

每個子任務(wù)都有相應(yīng)的任務(wù)大小ai,size和輸出ai,out:A={ai,size,ai,out},任務(wù)A的輸入數(shù)據(jù)大小Ain為:

(2)

式中:a1,a2,…,ak(1≤k)表示任務(wù)A中沒有前置任務(wù)的子任務(wù)。

類似地,任務(wù)A輸出的數(shù)據(jù)數(shù)量Aout為:

(3)

式中:al,al+1,…,an(l≤n)表示任務(wù)A中沒有后置任務(wù)的子任務(wù)。

1.3 時延模型

1.3.1 計算延遲

不同計算設(shè)備的計算資源是異構(gòu)的,因此不同設(shè)備計算同一任務(wù)的成本不同。任務(wù)卸載的時延與任務(wù)本身計算量和設(shè)備計算能力有關(guān)。一個原子型子任務(wù)ai在設(shè)備o上的計算時間為:

(4)

式中:o的取值為(0,m),用于表示不同的計算設(shè)備,fo表示該設(shè)備每秒可以計算的數(shù)據(jù)量。角標(biāo)o的定義在下文相同。

假設(shè)除云以外的計算設(shè)備每次只允許計算一個任務(wù),則當(dāng)設(shè)備o上已有任務(wù)時,任務(wù)ai分配到該設(shè)備上等待計算的時間為:

(5)

式中:No,size為任務(wù)ai到達(dá)時設(shè)備o上現(xiàn)有的任務(wù)數(shù)量大小。

1.3.2 傳輸模型

通過香農(nóng)公式,可以得到設(shè)備o1到設(shè)備o2的傳輸速度為:

(6)

任務(wù)ai從設(shè)備o1～o2的傳輸時間為:

(7)

1.4 優(yōu)化問題

1.4.1 約束條件

(8)

每個子任務(wù)只能卸載到一個設(shè)備上,表示為:

(9)

任務(wù)A中的子任務(wù)只有在前置任務(wù)完成后才能開始,表示為:

Tfai≤Tsav,?ai∈A,av∈Cai,

(10)

式中:Tfai表示子任務(wù)ai的完成時間,Tsav表示子任務(wù)av的開始時間,Cai表示任務(wù)ai的后置任務(wù)集。

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

優(yōu)化目標(biāo)是減少整個依賴任務(wù)A的卸載延遲,可表示為:

(11)

依賴任務(wù)的卸載決策已被證明是NP-hard[20],無法在多項式時間內(nèi)找到最優(yōu)解。

2 加權(quán)輪換最短路徑算法

2.1 模型概述

本節(jié)提出了天地一體化協(xié)同計算背景下依賴任務(wù)卸載的加權(quán)輪換最短路徑模型算法,該方法確定了依賴任務(wù)的調(diào)度方案,包括每個子任務(wù)的開始執(zhí)行時間和卸載設(shè)備的決策。該算法的開發(fā)主要基于3個原則:

① 基于依賴任務(wù)子任務(wù)間的并行結(jié)構(gòu)和依賴關(guān)系,對依賴任務(wù)的結(jié)構(gòu)進(jìn)行劃分和處理,進(jìn)行更精確的調(diào)度;

② 考慮依賴任務(wù)中并行結(jié)構(gòu)的爭用影響;

③ 在保證調(diào)度算法性能的前提下,盡量降低調(diào)度算法的復(fù)雜度。

2.2 任務(wù)結(jié)構(gòu)劃分

由于節(jié)點路徑模型的局限性,該模型只能對只有串行結(jié)構(gòu)的依賴任務(wù)進(jìn)行優(yōu)化。為了將其擴(kuò)展到具有并行結(jié)構(gòu)的依賴任務(wù),對依賴任務(wù)結(jié)構(gòu)進(jìn)行分解和重構(gòu),形成由僅由串行結(jié)構(gòu)子任務(wù)集組成的新任務(wù)結(jié)構(gòu)。分離重構(gòu)原理如下:

① 與節(jié)點N有并行關(guān)系的節(jié)點與節(jié)點N在同一層;

② 每層節(jié)點數(shù)量盡量少,以降低算法復(fù)雜度。

重組示意圖如圖2所示。

(a) 原任務(wù)結(jié)構(gòu)

(b) 重組后的任務(wù)結(jié)構(gòu)圖2 任務(wù)結(jié)構(gòu)重組示意圖Fig.2 Task structure reorganization diagram

2.3 卸載策略路徑模型

為了便于解釋,使用圖3(a)中的任務(wù)為例,并將計算設(shè)備(可以是云、邊緣、衛(wèi)星或終端)的數(shù)量設(shè)置為兩個,命名為c0和c1。該任務(wù)的卸載策略路徑模型如圖3(b)所示。路徑模型中的每一層表示對應(yīng)的子任務(wù)集及其卸載策略。該模型分為節(jié)點和路徑兩個部分。

(a) 對任務(wù)結(jié)構(gòu)進(jìn)行重組

(b) 任務(wù)策略路徑模型圖3 任務(wù)重構(gòu)與策略路徑模型構(gòu)建Fig.3 Task reconstruction and strategy path model

① 節(jié)點:路徑模型中每個節(jié)點都代表一個卸載策略。例如,第二行節(jié)點“S01”表示子任務(wù)b在c0處卸載,子任務(wù)c在c1處卸載。特別地,底部節(jié)點0和頂部節(jié)點1是為方便計算而創(chuàng)建的虛擬節(jié)點。

② 路徑:節(jié)點下方的路徑權(quán)值表示該節(jié)點策略對應(yīng)的時延。

利用最短路徑算法計算模型中的最短路徑,理論上可以得到性能最優(yōu)的調(diào)度方案。但該方法有一個明顯的缺點,即算法復(fù)雜度過高,因此需要對算法復(fù)雜度進(jìn)行優(yōu)化。

2.4 任務(wù)卸載最優(yōu)設(shè)備序列

假設(shè)任務(wù)A中某個子任務(wù)ai的前置任務(wù)ap已經(jīng)在設(shè)備o1上執(zhí)行,則將ai卸載到設(shè)備o2的時延為(o1和o2可以相同):

(12)

可知k是一個與任務(wù)無關(guān)的常數(shù),只與設(shè)備自身參數(shù)有關(guān)。

通過對子任務(wù)卸載時間的建模,發(fā)現(xiàn)任務(wù)的卸載時間模型是與任務(wù)大小成比例的一階函數(shù)。也就是說,對于同一個任務(wù)來說,在前置任務(wù)的卸載設(shè)備確定且不考慮等待時延的情況下,不同設(shè)備卸載該任務(wù)的時延大小排序是確定的。即k值越低,對應(yīng)設(shè)備的卸載時延越小。由此可以得到任務(wù)的最優(yōu)卸載設(shè)備序列。

但是,在實際卸載中不能直接使用該序列將任務(wù)分配給序列中的第一個即最優(yōu)的設(shè)備進(jìn)行卸載,原因有以下三點:

① 多個前置任務(wù)有相同的后置任務(wù):如果前置任務(wù)分配到不同的設(shè)備上,則從不同前置任務(wù)來看該后置任務(wù)的最優(yōu)設(shè)備可能是不同的,顯然卸載策略發(fā)生了沖突。如圖4所示,其中子任務(wù)上的顏色代表將其卸載到對應(yīng)顏色的設(shè)備上。

圖4 多前置任務(wù)理論最佳設(shè)備產(chǎn)生沖突Fig.4 Multiple pre-task theory optimal device conflict

② 一個前置任務(wù)有多個并行的后置任務(wù):當(dāng)前置任務(wù)的卸載設(shè)備確定后,它所有后置任務(wù)的最優(yōu)卸載設(shè)備是相同的。如果同時將多個后置任務(wù)分配給了同一個設(shè)備,將會產(chǎn)生額外的等待時延,如圖5所示。

圖5 并行任務(wù)分配到同一設(shè)備產(chǎn)生排隊時延Fig.5 Parallel tasks assigned to the same device cause queuing delay

③ 將每個子任務(wù)直接分配給其最優(yōu)設(shè)備只能得到每一層子任務(wù)的局部最優(yōu)策略,而不能得到考慮整個依賴任務(wù)中所有子任務(wù)的全局最優(yōu)策略。

為了解決上述問題,提出了加權(quán)輪換最短路徑算法,通過給設(shè)備分配權(quán)重并根據(jù)卸載策略進(jìn)行相應(yīng)的權(quán)重增減,得到一個動態(tài)的最優(yōu)設(shè)備排序列表。

2.5 設(shè)備權(quán)重計算

2.5.1 初始權(quán)重計算

當(dāng)任務(wù)ai的前置任務(wù)ap卸載設(shè)備已確定時,可以得到ai在每個設(shè)備上卸載時延的大小。使用以下公式定義對任務(wù)ai來說不同設(shè)備j的初始權(quán)值wi,j:

(13)

式中:k為前文中的參數(shù),α為歸一化參數(shù)。

2.5.2 根據(jù)任務(wù)結(jié)構(gòu)更新權(quán)重:

(1) 多前置任務(wù)的權(quán)重疊加

當(dāng)子任務(wù)具有多個前置任務(wù)時,不同的前置任務(wù)可能會在不同設(shè)備上執(zhí)行,從而導(dǎo)致該子任務(wù)從不同的前置任務(wù)角度分析可能會具有多個最優(yōu)設(shè)備列表。根據(jù)前置任務(wù)的大小比例,對每個設(shè)備在這些列表中的權(quán)重按正比取加權(quán)平均值,得到最終對該子任務(wù)來說每個設(shè)備的權(quán)重與最優(yōu)列表,如圖6所示。

圖6 多前置任務(wù)的權(quán)重疊加Fig.6 Weight superposition of multiple pre-tasks

(2) 多后置任務(wù)的權(quán)重削減

為解決多個并行子任務(wù)被分配到同一個設(shè)備導(dǎo)致計算設(shè)備擁塞的問題,將并行子任務(wù)中更大的子任務(wù)設(shè)置為更高的優(yōu)先級,優(yōu)先將其分配至更優(yōu)的設(shè)備,避免被分配到性能較差設(shè)備上而產(chǎn)生延遲。用以下公式更新其他任務(wù)的對應(yīng)設(shè)備權(quán)重:

(14)

式中:w為初始權(quán)重,ki為各設(shè)備對高優(yōu)先級子任務(wù)的優(yōu)先級,Nsize為該設(shè)備上已分配的任務(wù)大小,fo為該設(shè)備的計算能力,p、q為歸一化參數(shù)。示意圖如圖7所示。

2.6 構(gòu)建路徑模型

根據(jù)各任務(wù)設(shè)備權(quán)重列表進(jìn)行路徑節(jié)點篩選,為方便闡述,使用圖8中終端任務(wù)及4個設(shè)備[0,1,2,3]舉例說明如何篩選設(shè)備。構(gòu)建的路徑模型如圖9所示。

圖8 終端任務(wù)及最優(yōu)設(shè)備列表Fig.8 Terminal tasks and optimal devices list

圖9 篩選設(shè)備后的最短路徑模型Fig.9 Shortest path model after filtering device

利用最短路徑算法獲得模型中的最短路徑,這就是任務(wù)卸載的最優(yōu)策略。關(guān)于設(shè)備排序列表中保留的數(shù)量,如果太多則算法復(fù)雜度高,保留太少則性能不佳,在實驗評估后選擇保留3個。

3 仿真評估

3.1 仿真參數(shù)網(wǎng)絡(luò)模型

生成一個空地網(wǎng)絡(luò),其中地面由一個云和3個邊緣組成,衛(wèi)星星座使用Starlink。

3.2 基準(zhǔn)算法

本文使用的基準(zhǔn)算法如下:

① 任務(wù)全部卸載到云(Cloud)執(zhí)行:將終端生成的任務(wù)傳輸?shù)皆贫?在云端計算后再傳輸回終端,調(diào)度順序為任務(wù)釋放時間和任務(wù)準(zhǔn)備時間。

② 局部(Cloud)最優(yōu)算法:將每個子任務(wù)直接調(diào)度到其最優(yōu)服務(wù)器上進(jìn)行計算,不考慮任務(wù)搶占和全局規(guī)劃。

③ 貪婪(Greed):不篩選設(shè)備,使用所有設(shè)備建立最短路徑模型,計算最優(yōu)調(diào)度方案。

3.3 終端任務(wù)的仿真結(jié)果

在每次仿真中,每種算法執(zhí)行10次,取其平均值作為每種算法的性能。

3.3.1 不同算法對卸載時延的影響

不同算法下的任務(wù)卸載時延如圖10所示。從圖10(a)可以看出,PruningPath可以明顯降低卸載時延。而從圖10(b)總時延的角度考慮,PruningPath算法性能最優(yōu)。Cloud算法性能不佳的主要原因是終端與云之間距離過遠(yuǎn)產(chǎn)生的傳輸延遲,Local算法是由于只考慮局部最優(yōu)解過于短視,從圖10(a)和圖10(b)聯(lián)合分析可以看出Greed算法性能不佳的主要原因是算法運行時間過長。本文算法最多可以將卸載時延降低31.9%。

(a) 不考慮算法運行時間只考慮卸載時延

(b) 考慮算法運行時間與卸載時間的總時延圖10 不同算法下的任務(wù)卸載時延Fig.10 Task offloading delay under different algorithms

3.3.2 不同算法對卸載能耗的影響

不同算法下的任務(wù)卸載能耗如圖11所示,可以看出,本文算法相比局部最優(yōu)算法具有較低的能耗,這是因為能耗大小也與任務(wù)計算時間與傳輸時間有關(guān),當(dāng)以時延為目標(biāo)優(yōu)化卸載方案時,在一定程度內(nèi)也會優(yōu)化任務(wù)的卸載能耗。圖11中卸載到云方案的能耗較低,但卸載到云方案的時延較高,表明了云計算能力強(qiáng),但偏遠(yuǎn)地區(qū)終端與云距離過長的特點。

圖11 不同算法下的任務(wù)卸載能耗Fig.11 Energy consumption of task offloading

3.3.3 貪婪算法的局限性

本節(jié)在路徑模型中保留不同數(shù)量的最優(yōu)設(shè)備來測量算法的性能。將保留設(shè)備數(shù)量設(shè)置為1時,該算法實際上就是Local算法。

保留不同設(shè)備數(shù)量的任務(wù)卸載時延如圖12所示。從圖12(a)可以看出,隨著設(shè)備數(shù)量的增加,任務(wù)卸載本身的時延來越小。但如圖12(b)所示,當(dāng)設(shè)備超過一定數(shù)量時,總時延反而呈上升趨勢,這是由于路徑算法的時間復(fù)雜度過高導(dǎo)致的。

(a) 不考慮算法運行時間只考慮卸載時延

(b) 考慮算法運行時間與卸載時間的總時延圖12 保留不同設(shè)備數(shù)量的任務(wù)卸載時延Fig.12 Different numbers of servers on latency influence

測量了不同保留設(shè)備數(shù)量下算法的運行時間,結(jié)果如表1所示,可以看出,當(dāng)設(shè)備數(shù)量超過3時,算法運行時間已經(jīng)與任務(wù)卸載時延的數(shù)量級相同,即算法本身將產(chǎn)生不可忽視的時延。所以在算法中使用更多數(shù)量的設(shè)備不一定能得到更好的性能,這進(jìn)一步說明了在路徑模型中刪減設(shè)備的必要性。

表1 保留設(shè)備數(shù)量對算法運行時間的影響Tab.1 Different number of servers on latency influence 單位:s

4 結(jié)論

本文提出了一種用于天地協(xié)同計算中基于最短路徑模型的卸載方法PruningPath,利用任務(wù)結(jié)構(gòu)重組與建模將依賴任務(wù)調(diào)度問題轉(zhuǎn)化為最短路徑問題,并采用權(quán)值輪換修剪設(shè)備降低算法復(fù)雜度。實驗結(jié)果表明,該算法在將卸載時延最多降低31.9%的同時,保持了較低的復(fù)雜度和運行時間。