基于星地協(xié)同的低時延任務卸載算法

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

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

0 引言

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

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

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

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

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

1 問題建模

1.1 系統(tǒng)模型

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

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

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

1.2 依賴任務定義

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

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

(1)

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

(2)

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

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

(3)

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

1.3 時延模型

1.3.1 計算延遲

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

(4)

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

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

(5)

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

1.3.2 傳輸模型

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

(6)

任務ai從設備o1～o2的傳輸時間為:

(7)

1.4 優(yōu)化問題

1.4.1 約束條件

(8)

每個子任務只能卸載到一個設備上,表示為:

(9)

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

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

(10)

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

1.4.2 優(yōu)化目標

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

(11)

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

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

2.1 模型概述

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

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

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

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

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

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

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

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

重組示意圖如圖2所示。

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

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

2.3 卸載策略路徑模型

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

(a) 對任務結(jié)構(gòu)進行重組

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

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

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

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

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

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

(12)

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

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

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

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

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

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

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

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

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

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

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

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

(13)

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

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

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

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

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

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

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

(14)

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

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

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

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

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

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

3 仿真評估

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

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

3.2 基準算法

本文使用的基準算法如下:

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

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

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

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

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

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

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

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

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

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

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

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

3.3.3 貪婪算法的局限性

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

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

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

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

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

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

4 結(jié)論

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