淤地壩監測場景下邊緣計算協作式任務調度方法①

章新川,胡 煒,王懷軍,安 洋,李軍懷

1(陜西省水利廳,西安 710048)

2(西安理工大學 計算機科學與工程學院,西安 710048)

1 引言

淤地壩作為壩區資源開發利用和經濟建設的基礎工程,在黃土高原水土保持中的地位尤為顯著[1].同時也存在相應的潰壩風險,因潰壩事件導致的水土流失、生態破壞時有發生,嚴重的潰壩事件會危害壩區居民生命安全.目前淤地壩在信息化管理、險情預測方面,存在數據利用率低、數據記錄方式落后等問題.為解決這些問題,壩區遠程監測、實時評估等在線實時監測模式逐漸成為淤地壩防護的研究熱點.

在5G、物聯網技術高速發展的背景下,采用“云-邊-端”方式實現對淤地壩的實時監測、傳輸、處理和風險預警,具有重要意義.通過部署在壩區的水尺、雨量計、視頻等傳感器采集數據,并經過邊緣節點預處理后上傳至云端統一管理和風險評估與預警.近幾年,有學者通過結合壩區傳感數據建立淤地壩潰壩模型,將采集數據作為參數輸入潰壩風險模型進行預警[2],實現對所覆蓋壩區的24 小時智能監測.然而,通常情況下淤地壩基礎潰壩模型計算復雜度較高,也會是否在汛期而進一步提升.同時由于淤地壩數量多、分布廣,一般按照行政區劃進行管理,因此采用“云-邊-端”方式可以有效保證監測與預警任務執行的實時性.

本文考慮了實際場景中各因素對計算任務完成時間的影響,建立了相應的數學模型,并利用模擬退火(Simulated Annealing,SA)算法能夠快速提供一個較為精確的近似解[3],對淤地壩的計算任務調度問題進行求解.

2 相關研究

2.1 淤地壩安全問題研究

顧艷玲等[4]基于熵理論將不同賦權方法進行有機集成,明確了壩體安全評估特征值權重指標,并通過最大化模型參數香農熵,保證估計結果的相對穩健.黃黎明等[5]基于工程風險清單、風險搜集、大數據風險分析三方面并結合物聯網技術建立質量風險管理框架,得到以物聯網技術實現水利工程風險管理的重要經驗.王乃欣等[6]利用3Ds Max 等建模技術對淤地壩潰壩進行仿真,為研究潰壩時的救災搶險、應急管理做出了重要的參考依據.黃肖[7]利用MIKE 軟件建立了一套關于壩系布局與洪水關系的預測模型,實現模擬研究洪水作用下淤地壩的調控作用.李平等[8]將現有判斷水庫群發溢洪方法與貝葉斯網絡有機結合,并根據場景特征增加了上下游水壩潰壩關系因子,建立了完整的貝葉斯溢洪評估網絡.

2.2 邊緣計算任務調度研究

Seid 等[9]提出了一種基于無人機的F-RAN 體系結構新方向,該結構采用分布式強化學習(DRL)算法對邊緣設備進行學習,有效提高了計算任務卸載效率,并優化了計算資源分配.Liu 等[10]建立了一種基于優化邊緣服務器資源的分配算法,提高了移動邊緣計算架構的計算資源利用率.Zhou 等[11]通過模擬退火算法解決了D2D 資源分配成本高的問題,在資源分配組合中引入模擬退火算法,有效降低資源分配成本和任務平均計算時間.Liao 等[12]提出了一種有效的低復雜度啟發式算法,可以在可接受水平內保證邊緣計算網絡的計算資源保持,降低時間成本并最大化用戶任務卸載量.Anousha 等[13]對傳統Min-Min 調度算法進行改進,充分利用原算法在策略制定速度上的優點,并避免原算法負載均衡性能不足、任務執行時間跨度高的缺點,最終改善傳統Min-Min 算法性能.

對淤地壩進行實時監測,并將其數據作為參數輸入至潰壩模型,由此產生淤地壩計算任務.為提高淤地壩風險預警的時效性,需要對計算任務進行合理調度,縮短計算任務完成時間.各淤地壩計算任務卸載位置的精確求解屬于整數線性規劃中的NP 難問題.此類問題雖存在精確最優解,但計算量極大,耗時極長.

通常分布式的邊緣計算具有高隱私、低成本、易部署等優勢,但其計算資源、存儲容量都有所限制.在邊緣計算中,由于其計算資源受到限制,從單一角度出發的應用計算切分模式將變得不可實施.多用戶模式情景下,網絡資源和服務器資源的競爭十分普遍.此時計算任務卸載決策需要結合邊緣計算資源分配決策[14],通過減少應用完成時間的方式,提高系統整體服務水平[15].

3 邊緣計算場景下協作式任務調度策略

面向淤地壩監測任務調度策略實現思路如圖1所示,分為3 個步驟:信息獲取、建立任務完成時間模型、模擬退火算法求最優解.

圖1 基于模擬退火算法的任務調度策略實現思路圖

(1)信息獲取.該過程為任務調度服務器收集節點產生的計算任務信息和邊緣服務器計算資源信息.其中計算任務信息包括:計算任務總量、所有任務的計算量、傳輸計算任務的數據量;邊緣服務器信息包括:服務器計算能力、基站與節點間的通信帶寬、服務器數量.

(2)建立任務完成時間模型.建立任務完成時間模型,并代入任務信息與服務器信息,計算所有任務在某個邊緣服務器上的完成時間,該服務器的運行時間即為完成卸載至此的所有計算任務時間.

(3)模擬退火算法規劃卸載位置.隨機分配計算任務至服務器上,根據任務完成時間模型計算每一個服務器的運行時間,并取服務器中最大完成時間作為系統任務完成時間.降低算法溫度,同時對任務分配位置進行隨機調整,計算新分配方式下的任務完成時間,并依據Metropolis 接受準則接受新解.重復迭代直至達到終止條件,輸出任務最優分配位置.

模擬退火算法(SA)由Metropoils 準則和退火過程兩部分組成[16].前者實現了SA 算法如何在處于局部最優解時發生概率突跳并最終獲得全局最優解,是算法的基礎;后者則是SA 算法尋找最優解的迭代過程.Metropoils 準則是一種以概率接收新解,而不是以完全確定規則的重要采樣方法.得益于Metropoils 準則,SA算法可跳出局部最優解,并尋找全局最優解.

4 任務完成時間模型

壩系包括多個壩區,每個壩區采集節點都會定時產生一個計算量不同的計算任務,壩系周邊有若干個計算能力不同的邊緣服務器與壩區連接.該場景下,所有節點產生的計算任務地位平等,所有計算任務信息、邊緣服務器計算能力信息可知.其變量標識如表1所示.

表1 邊緣計算網絡變量標識表

計算任務由壩區節點卸載至連接的邊緣服務器上進行計算,任務完成時間共分為3 個部分:任務數據傳輸時間、任務平均等待時間、任務在邊緣服務器上的執行時間、計算結果由邊緣服務器向中心服務器上傳時間.任務完成時間模型如下.

(1)任務數據傳輸時間:由采集節點與服務器連接基站間的無線數據傳輸速率Bj,及任務傳輸數據大小di決定,如式(1):

(2)考慮到每個邊緣服務器的計算資源是有限的,任務量較多的時候會出現任務卸載等待及拒絕現象.接下來,分析任務卸載時的平均等待時間和卸載成功率.

假設,任務到達率為λ,將M/M/s/N/∞多服務器排隊模型[17]運用于任務卸載中,卸載任務到達邊緣計算服務器后以 隊列的形式保存,遵循先到達先服務的準則.系統負荷水平ρ如式(2):

記Pi表示排隊系統的狀態概率,其中,0 ≤i≤N+s,如式(3):

根據正則性條件,如式(4):

在ρ≠1的情況下,計算出狀態概率P0,如式(5):

根據P0進一步計算得到隊列中等待處理的任務的平均隊長和平均等待時間twait,如式(6)、式(7),其中平均等待時間根據排隊論[18]計算得到,該參數表示從任務到達邊緣計算服務器到被成功處理所需的平均等待時間.

(4)結果上傳中心服務器時間:由于邊緣服務器所連接的壩區基站功率極大,上傳結果數據量相對較小,因此選擇對該部分時間忽略不計.

(5)任務完成時間:由任務數據傳輸時間、任務平均等待時間和計算任務執行時間共同組成,如式(9):

其中,li表示計算任務Taski的卸載位置,li∈{1,2,···,M},li=M即表示計算任務Ti在編號為M的邊緣服務器執行計算,則任意一個邊緣服務器完成卸載任務的總時間如式(10):

那么系統任務完成時間為所有服務器中的最長運行時間,如式(11):

其中,i∈Oj表示在編號為j的邊緣服務器上運行的所有計算任務.

任務卸載成功率表示為任務被邊緣計算服務器成功處理并接受服務的概率,如式(12):

為最小化計算任務完成時間,將原問題轉化為有約束的目標函數如式(13):

其中,約束C要求任務的卸載成功率超過目標約束值.

5 基于模擬退火算法的任務卸載方法

基于SA 算法最優化計算任務卸載位置,即求目標函數(13)最優解的過程.設置算法初始溫度T0、終止溫度Tfin、溫度衰減系數 α以及每個溫度下的迭代次數β.并假設存在n個淤地壩同時產生一個計算信息不同的計算任務,生成任務計算量矩陣Ctask與傳輸數據量矩陣Ddata,分別如式(14)、式(15)所示.結合式(1)、式(8)生成數據傳輸時間模型矩陣Atrans、任務執行時間模型矩陣Ajobs,如式(16)、式(17)所示.

通過隨機函數生成一個n×m的0-1 矩陣記為初始解向量矩陣Zold,其中定義解向量矩陣Zold=(zij)n×m,zij∈{0,1},其形式如式(14),向量矩陣Z表示所有設備的計算方式及任務卸載位置.解向量j=1,2,3,···,m表示計算任務是否選擇在邊緣計算服務器1,2,···,m上執行.zij=0 表示計算任務Ti不會選擇該方式執行,zij=1 表示計算任務Ti選擇該計算方式執行計算.

式(18)表示任務1在編號為1的邊緣服務器上運行,任務2在編號為2的邊緣服務器上運行,任務3在編號為5的邊緣服務器上運行,任務4、5在編號為4的邊緣服務器上運行.

結合線性代數相關內容與式(11),獲取完成時間跨度矩陣Ttime,如式(19).

其中,,表示第i個服務器完成卸載至此所有任務的運行時間,令Ttime矩 陣中最大值為系統任務完成時間told.同時隨機交換原解向量矩陣Zold中3 個元素的位置,生成新的解向量矩陣Znew,并計算該解矩陣下的任務完成時間tnew.并求出完成時間跨度差,如式(20).

若Δt＜0,則一定接受新解Znew,若Δt＞0,以Metropoils 準則接受新解Znew,如式(18)接受新解Znew.判斷此次迭代是否達到該溫度下迭代次數上限,若沒有達到次數上限,則重復進行位置交換與完成時間;若達到該溫度下的迭代次數上限,則降低算法溫度,如式(21).

判斷是否達到規定的最低溫度;若未達到最低溫度則降低當前溫度,重置迭代次數,并重復上述迭代過程,若達到規定的最低溫度,則輸出當前解向量矩陣,算法結束.如圖2所示,表示一次迭代過程.

圖2 模擬退火算法制定任務卸載位置迭代流程

6 實驗仿真與結果分析

6.1 性能評價標準

利用模擬退火算法建立計算任務調度策略的主要目的為降低計算任務完成時間即任務執行時間跨度,使得系統的風險預警更具備時效性.此外,為綜合評定算法性能,增加任務總執行時間、計算任務調度策略制定時間以及系統負載均衡共同作為算法性能評價標準.

各指標的物理意義分別如下:

(1)任務執行時間跨度:即系統第一個任務開始至最后一個任務完成的時間跨度.

(2)任務總執行時間:即所有任務在邊緣服務器上的執行時間總和.

(3)計算任務調度策略制定時間:即任務調度服務器收集到計算任務信息后,制定所有計算任務卸載位置的總時間.

(4)系統負載均衡:評價一個網格計算平臺是否分配均衡,本文將采用各個節點的標準方差進行評價.其評價公式如式(22),其中M表示邊緣服務器個數,Xi表示第i個邊緣服務器被調用的次數,表示所有邊緣服務器平均被調用的次數,σ表示系統負載標準方差,其值越小,表明系統負載越均衡.

6.2 結果分析

實驗中設置計算任務量ci在區間[5,20]隨機生成,傳輸數據量di在區間[10,50]隨機生成.邊緣服務器的計算能力在區間[2,3]隨機生成,節點與邊緣服務器的通信帶寬Bj=1000.SA 算法初始溫度T0=200,終止溫度Tmin=3,每個溫度下的迭代次數為30,冷卻率取α=0.99.

(1)不同任務數量下,SA 算法與Min-Min 算法的性能比較

為研究兩種算法在任務數量不同時的性能差異.實驗邊緣服務器數量設置為50,任務數量在區間[100,1000]以100 遞增取值,共計10 組實驗,每組實驗重復10 次取平均值.圖3的4 個子圖分別表示兩種算法在不同任務數量下的4 種評價指標性能差異.

圖3 兩種算法在不同任務數量下的綜合性能

由圖3(a)、圖3(b)可知,采用SA 算法進行任務調度,可有效降低系統任務執行時間跨度、任務執行時間總和,且當計算任務量越小,SA 算法求出的解越接近精確解.其原因是算法初始化后,迭代次數將被確定,解矩陣越小,SA 算法越接近窮舉法,因此算法的時間性能越好.由圖3(c)可知,為降低任務執行時間跨度,SA 算法將會為計算能力較強的服務器分配更多的計算任務,因此其算法的負載均衡性能會有所損失.由圖3(d)可知,雖然SA 算法存在較為明顯的時間性能優勢,但其任務調度策略制定時間相比于Min-Min 算法也會增加,且利用SA 算法的制定調度決策的時間將呈現線性增加,貼合SA 算法的時間復雜度O(kl(n)),其中k為每個溫度下的迭代次數,l(n)為問題規模的多項式函數.

(2)不同服務器數量下,SA 算法與Min-Min 算法的性能比較

為研究兩種算法在邊緣服務器數量不同時的性能差異.實驗邊緣服務器數量在區間[30,100]以10 遞增取值,共計8 組實驗,每組實驗重復10 次取平均值.圖4(a)至圖4(d)分別表示兩種算法在不同服務器數量下的4 種評價指標性能差異.

由圖4(a)可知,增加參與計算的邊緣服務器可有效降低兩種算法的任務執行時間跨度,且邊緣服務器的數量越多,SA 算法的性能優勢將越明顯,其原因為:在增加邊緣服務器數量時,雖然兩種算法均會降低任務完成時間跨度,但由于SA 算法更加精確,因此下降趨勢較Min-Min 算法更加明顯.由圖4(b)可知,當參與計算的服務器增加時,Min-Min 算法將會分配給計算能力較差的服務器分配計算任務,因此任務執行時間總和將會增長.通過圖4(c)可知,增加服務器數量會改善系統整體的負載均衡性能,但本文采用SA 算法制定任務調度策略的目的是降低任務執行時間跨度,勢必會提高計算能力較強服務器的負載,因此系統負載均衡性能將會有所不足.由圖4(d)可知,增加邊緣服務器數量將會擴大SA 算法解矩陣規模,提高SA 算法時間復雜度,導致求解時間增加.

圖4 兩種算法在不同服務器數量下的綜合性能

7 結論與展望

針對淤地壩監測與預警系統時效性問題,設計了基于模擬退火的多個邊緣計算服務器相互協作任務調度方法.根據任務調度分析,建立任務完成時間模型.并說明了在淤地壩計算任務的執行沒有優先級時,應用模擬退火算法制定調度策略可以達到該場景下降低完成時間跨度的任務調度目的,并給出了調度優化問題的解決步驟.最后通過仿真實驗,驗證了基于模擬退火的調度方法符合場景需求,可以達到預期的效果.