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

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

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

0 引言

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

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

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

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

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

1 問題建模

1.1 系統模型

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

圖1 系統框架圖Fig.1 System frame diagram

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

1.2 依賴任務定義

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

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

(1)

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

(2)

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

類似地,任務A輸出的數據數量Aout為:

(3)

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

1.3 時延模型

1.3.1 計算延遲

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

(4)

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

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

(5)

式中:No,size為任務ai到達時設備o上現有的任務數量大小。

1.3.2 傳輸模型

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

(6)

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

(7)

1.4 優化問題

1.4.1 約束條件

(8)

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

(9)

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

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

(10)

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

1.4.2 優化目標

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

(11)

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

2 加權輪換最短路徑算法

2.1 模型概述

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

① 基于依賴任務子任務間的并行結構和依賴關系,對依賴任務的結構進行劃分和處理,進行更精確的調度;

② 考慮依賴任務中并行結構的爭用影響;

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

2.2 任務結構劃分

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

① 與節點N有并行關系的節點與節點N在同一層;

② 每層節點數量盡量少,以降低算法復雜度。

重組示意圖如圖2所示。

(a) 原任務結構

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

2.3 卸載策略路徑模型

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

(a) 對任務結構進行重組

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

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

② 路徑:節點下方的路徑權值表示該節點策略對應的時延。

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

2.4 任務卸載最優設備序列

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

(12)

可知k是一個與任務無關的常數,只與設備自身參數有關。

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

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

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

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

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

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

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

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

2.5 設備權重計算

2.5.1 初始權重計算

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

(13)

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

2.5.2 根據任務結構更新權重:

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

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

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

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

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

(14)

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

2.6 構建路徑模型

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

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

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

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

3 仿真評估

3.1 仿真參數網絡模型

生成一個空地網絡,其中地面由一個云和3個邊緣組成,衛星星座使用Starlink。

3.2 基準算法

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

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

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

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

3.3 終端任務的仿真結果

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

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

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

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

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

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

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

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

3.3.3 貪婪算法的局限性

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

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

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

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

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

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

4 結論

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