基于邊緣算力協(xié)同系統(tǒng)的視頻智能分析任務動態(tài)調度方法

李成華 石勝濤 李孝天 江小平* 石鴻凌

①(中南民族大學電子信息工程學院 武漢 430074)

②(智能無線通信湖北省重點實驗室 武漢 430074)

1 引言

人工智能分析技術對視頻數(shù)據(jù)進行分析的計算結果有助于提升風險防控的事前預警能力。在文物安防領域，使用人臉識別、消防通道擁堵、徘徊行為識別、攀爬行為識別等人工智能模型進行異常事件識別，可加強文物保護工作的科技支撐，對提升文物博物館單位的風險防控能力具有重要意義。

調查發(fā)現(xiàn)，多數(shù)文物博物館單位目前對大量視頻數(shù)據(jù)的處理方式是將其上傳到云中心進行智能分析處理，盡管云計算的方式能夠提供有效的數(shù)據(jù)存儲和處理設施，但是不斷增長的數(shù)據(jù)量將會導致高能量消耗，給通信帶寬帶來沉重的負擔[1,2]，并且存在“不能接受”時延[3,4]以及大量云計算資源消耗的問題。其次，由于云中心距離數(shù)據(jù)產(chǎn)生的地方比較遠，當把數(shù)據(jù)傳輸?shù)皆浦行倪M行存儲和處理時，它的重要性和“新鮮度”將會下降[5,6]。針對上述利用云計算對大量視頻數(shù)據(jù)進行智能分析出現(xiàn)的問題，本文考慮將視頻數(shù)據(jù)放在邊緣側文物博物館單位本地進行智能分析處理。在文物博物館單位本地對視頻數(shù)據(jù)進行智能分析存在兩方面的問題，一方面，文物博物館單位的監(jiān)控系統(tǒng)所包含的攝像頭數(shù)量較多，所產(chǎn)生的視頻監(jiān)控數(shù)據(jù)非常多，并且單個智能應用在運行時需要的算力多，這對文物博物館單位本地的計算資源是一個很大的挑戰(zhàn)。另一方面，通過調研發(fā)現(xiàn)文物博物館單位內OA(Office Automation)系統(tǒng)、門禁管理系統(tǒng)、售票等系統(tǒng)的計算資源沒有得到充分的利用，其系統(tǒng)的利用率普遍不高且資源消耗在時間上存在不均衡的現(xiàn)象。通過以上分析可以看出，研究一種在資源受限的情況下將文物博物館單位內現(xiàn)有的可用空閑計算資源充分利用起來的方法，使得盡可能多的視頻數(shù)據(jù)被智能分析，對進一步提升文物博物館單位的風險防控能力具有重要意義。

資源分配和任務調度優(yōu)化是計算系統(tǒng)的重要研究問題之一，其解決方案影響資源使用的有效性和用戶的服務體驗。目前，對資源約束下的任務分配問題有以下研究，文獻[7]提出了一種基于預測的資源分配方案，利用自回歸滑動平均模型動態(tài)地為周期數(shù)據(jù)和緊急數(shù)據(jù)預留資源，在滿足緊急數(shù)據(jù)傳輸條件的前提下最小化對周期數(shù)據(jù)傳輸?shù)挠绊憽Ｎ墨I[8]提出了帶 CPU 容量、電池電量約束的任務-節(jié)點分配模型。文獻[9]采用分布式遺傳算法(Genetic Algorithm, GA)求解CPU、內存和帶寬約束下混合云任務分配問題，利用有偏隨機鍵和特定解碼規(guī)則處理不可行解，最大化同時處理的任務數(shù)。文獻[10]建立混合整數(shù)規(guī)劃模型，確定滿足邊緣節(jié)點 CPU、內存和存儲容量約束的利用率最大化的任務分配方案。文獻[11]標記節(jié)點的硬軟件參數(shù)，設計并實現(xiàn)了任務分配的回溯搜索算法。文獻[12]提出一種基于無人機無線能量傳輸?shù)倪吘売嬎阆到y(tǒng)能耗優(yōu)化方法，通過聯(lián)合優(yōu)化能量收集時間、用戶發(fā)射功率和卸載決策，最小化系統(tǒng)總能耗。文獻[13]提出在線調度方法，最大化滿足截止時間的任務個數(shù)。文獻[14]提出一個電路維修任務調度的數(shù)學模型，在地理信息和資源等約束條件下，最大限度地提高效益，并將維修過程中的風險降至最低。文獻[15]在計算資源有限以及通信能力受到限制的條件下提出了基于李雅普諾夫優(yōu)化的實時調度算法，解決了多個設備之間的資源分配調度問題。

然而，現(xiàn)有的工作沒有考慮當計算節(jié)點現(xiàn)有應用業(yè)務資源使用情況動態(tài)變化時，在保證現(xiàn)有業(yè)務的正常運行的情況下，利用節(jié)點上可用資源量進行任務的動態(tài)分配問題。因此，本文提出一種在資源約束下的視頻智能分析任務的動態(tài)調度方法，其主要貢獻如下：

(1) 將文物博物館單位具有可用資源的設備作為視頻智能分析任務的計算節(jié)點，采用容器管理和集群資源監(jiān)控等技術構建出邊緣算力協(xié)同系統(tǒng)，在此系統(tǒng)上采用基于背包理論的任務分配算法實現(xiàn)了任務的動態(tài)調度，本文給出了該動態(tài)調度的流程。

(2) 充分考慮文物博物館單位在本地進行視頻智能分析任務處理過程中的資源限制，以背包理論為基礎，將要解決的問題建模為2維多重背包問題，并采用動態(tài)規(guī)劃求解了在資源約束情況下的視頻智能分析任務的調度優(yōu)化問題，實現(xiàn)最大化任務執(zhí)行所帶來的安全價值效益。

2 邊緣算力協(xié)同系統(tǒng)構成

邊緣算力協(xié)同系統(tǒng)從文物博物館單位的流媒體服務器獲取視頻數(shù)據(jù)資源描述信息，并使用系統(tǒng)內的算力資源完成視頻智能分析任務(Video Intelligent Analysis Tasks, VIAT)的計算，分析得到的結果供文物博物館單位的業(yè)務應用使用。邊緣算力協(xié)同系統(tǒng)構成如圖1所示，主要包括控制中心(Controller, Ctr)、算力資源(Computing Source, CS)兩個部分。

圖1 邊緣算力協(xié)同系統(tǒng)構成

控制中心Ctr動態(tài)監(jiān)測算力資源CS中每個計算節(jié)點上空閑可用計算資源的變化情況，根據(jù)計算節(jié)點上空閑可用計算資源量將待處理的視頻智能分析任務調度到算力資源CS中的計算節(jié)點進行處理。控制中心Ctr由資源收集器、任務調度器和任務管理器等3個功能模塊構成，它們的主要功能是：

(1) 資源收集器：實時收集各計算節(jié)點上資源使用情況；

(2) 任務調度器：根據(jù)系統(tǒng)中計算節(jié)點資源使用情況以及待分配的VIAT任務，執(zhí)行本文提出的基于背包理論的任務分配方法以獲得任務分配方案，再發(fā)出視頻智能分析任務的調度指令；

(3) 任務狀態(tài)管理器：包括待分配任務的管理以及正在執(zhí)行任務的狀態(tài)管理。

算力資源CS提供執(zhí)行視頻智能分析任務所需的CPU和內存計算資源，由文物博物館單位內具有空閑可用計算資源的節(jié)點組成，每個節(jié)點上都運行著該單位現(xiàn)有的主應用業(yè)務(Main Application Business, MAB)，計算節(jié)點設置有3個模塊：資源監(jiān)測器、任務執(zhí)行器和模型庫，它們的主要功能是：

(1) 資源監(jiān)測器：實現(xiàn)計算節(jié)點資源使用情況的數(shù)據(jù)采集并實時上傳到控制中心Ctr的資源收集器；

(2) 任務執(zhí)行器：根據(jù)控制中心Ctr的調度指令要求，啟動執(zhí)行視頻智能分析任務或停止執(zhí)行任務；

(3) 模型庫：存放處理視頻數(shù)據(jù)所需要的人工智能模型。

3 基于背包理論的任務分配算法

3.1 問題分析

分析文物博物館單位面臨的視頻智能分析任務的實際場景可知：一方面，每個視頻智能分析任務VIAT都要占用計算節(jié)點上計算資源(如CPU核數(shù)、內存占用量等)，要求所分配任務的執(zhí)行不能影響該計算節(jié)點上主應用的正常運行。另一方面，因為監(jiān)控視頻部署的具體點位、不同的時間段以及深度學習模型分析任務目標的不同，使得執(zhí)行不同智能視頻分析任務對文物安全風險防范及產(chǎn)生安全價值效益也不同，所以，希望任務分配方案在每個計算節(jié)點上能獲得的安全價值效益盡量高。可見，本文面臨的問題可描述為一個求解資源約束下的任務分配問題，即尋找滿足約束條件下的“任務-計算節(jié)點”最優(yōu)分配方案，使得執(zhí)行任務獲取的安全價值效益更高。

3.2 模型建立

上述任務分配問題可建模為2維費用多重背包問題。在經(jīng)典的2維多重背包問題中，有N種物品和一個容量為V，載重為U的背包。第k件物品最多有n[k] 件，每件的體積是a[k] ，重量是b[k]，價值是w[k]，優(yōu)化目標是求解將哪些物品裝入背包中使得背包中物品價值總和最大。

在本文面臨的場景中，每個計算節(jié)點可被視為一個提供確定計算資源量的背包，而每個需要消耗CPU和內存資源的視頻智能分析任務可被視為物品，物品的類別即人工智能分析模型的種類。用變量fi表示第i計算節(jié)點個數(shù)，變量Tj代表第j類視頻智能分析任務，本文所面臨的2維費用多重背包問題可以表述為：現(xiàn)有CPU、內存空閑資源量分別為,的計算節(jié)點fi(i=1,2,3,...)以及待分配的視頻智能分析任務VIAT，其中，第j類VIAT任務的個數(shù)最多有nj個，執(zhí)行每個VIAT所需的CPU資源為，內存資源為，以及執(zhí)行該任務所獲得的安全效益價值VTj，在這些條件下，求解如何將VIAT分配在計算節(jié)點fi上執(zhí)行，使得fi上執(zhí)行的任務所獲得的安全效益總價值V最大？

3.3 問題求解

動態(tài)規(guī)劃算法是求解決策過程最優(yōu)化的數(shù)學方法之一，是一種強大的算法設計技術，已被廣泛應用于解決許多組合優(yōu)化問題，適合解決具有最優(yōu)子結構和重疊子問題屬性的問題[16,17]，本文采用動態(tài)規(guī)劃算法求解本文提出的問題。算法具體實現(xiàn)如下：

在該任務分配算法中，C[]表示每個任務需要的CPU計算資源數(shù)組，M[]表示每個任務需要的內存計算資源數(shù)組，V[]表示每個任務對應的安全價值效益數(shù)組，TN為所有類別任務的和。如算法1，第1行表示在每個調度時間周期tτ時對計算節(jié)點上的空閑資源可用量、任務集合進行更新。第2行表示對每個任務進行遍歷，對任務的1次遍歷完成意味著1個階段的完成。第2行到第10行說明了動態(tài)規(guī)劃算法求解在資源約束情況下具有最大安全價值效益的任務集合，第11行使用findResult()函數(shù)遞歸找出當前調度周期任務調度結果解向量。第12行表示執(zhí)行當前調度周期內調度的任務所能獲得的最大安全價值效益。第13行表示最后返回當前調度周期內的調度任務調度結果解向量以及對應的最大安全價值效益。

4 任務動態(tài)調度流程

上述基于背包理論的任務調度算法部署在圖1所示邊緣算力協(xié)同計算系統(tǒng)的任務調度器中，配合邊緣算力協(xié)同計算系統(tǒng)的其他功能模塊共同實現(xiàn)VIAT任務的動態(tài)調度，其調度流程如圖2所示，其主要流程說明如下：

圖2 任務動態(tài)調度流程

(1) 初始化控制中心Ctr任務管理器的VIAT任務信息，包括VIAT任務種類、任務所需CPU、內存資源、每類任務的最大個數(shù)、安全價值效益等信息。

算法1 任務調度算法

(2) 控制中心Ctr的資源收集器每隔tτ時間周期性地收集fi上的資源實時使用情況，通過對數(shù)據(jù)處理得到CPU和內存資源觀察值,。

(3) 將當前時間周期內的資源觀察值、計算節(jié)點正常運行所需預留的資源量ζc=(1-λc)Cfi,ζm=(1-λm)Mfi進行比較(其中，Cfi為計算節(jié)點總CPU資源，Mfi為總內存資源)。當滿足資源觀察值分別同時大于ζc,ζm時，跳轉執(zhí)行步驟(4)；當,中 有一個值小于ζc或ζm時，跳轉執(zhí)行步驟(5)。

(4) 任務調度器調用本文“基于背包理論的任務分配算法”，得到當前時間周期的任務調度解空間向量Ifi以及安全價值效益Vtτ fi，比較Vtτ fi與上一個時間周期獲得的安全價值效益Vtτ-1fi的大小。當Vtτ fi ≥Vtτ-1fi，任務調度器根據(jù)分配解空間向量Ifi發(fā)出“任務分配指令”，fi上的任務執(zhí)行器根據(jù)指令信息停止或啟動VIAT任務，并通知任務管理器更新VIAT任務的狀態(tài)信息；當Vtτ fi ＜Vtτ-1fi，fi保持上一個調度周期的任務執(zhí)行。

(5)fi停止執(zhí)行當前正在運行的VIAT任務，任務調度器根據(jù)資源觀察值調用“基于背包理論的任務分配算法”模塊功能，得到當前時間周期的任務分配解空間向量Ifi以及安全價值效益Vtτ fi，發(fā)出“任務分配指令”，fi上的任務執(zhí)行器根據(jù)指令信息執(zhí)行VIAT任務，并通知任務管理器更新正在執(zhí)行任務的狀態(tài)值。

在進行任務調度時，以計算節(jié)點的資源觀察值為判斷任務可調度性的重要判斷依據(jù)，將資源觀察值與保證系統(tǒng)正常運行所需預留資源量進行比較，當資源觀察值大于需要預留的資源量時，說明VIAT任務是可調度的。當資源觀察值小于所需預留的資源量時，說明VIAT的執(zhí)行已經(jīng)影響到MAB的工作了，計算節(jié)點fi處于過載狀態(tài)，即VIAT任務不可調度；為了保證MAB的正常運行，將VIAT任務全部停止執(zhí)行。綜上所述，本文所提出的任務調度模型是以確保MAB正常工作為前提來判斷任務的可調度性的。

5 仿真實驗

5.1 實驗環(huán)境

本文采用圖3所示的技術架構搭建邊緣算力協(xié)同系統(tǒng)實驗環(huán)境，主要采用了容器集群管理Kubernetes(K8s)技術和集群資源監(jiān)控Prometheus技術。實驗中采用的Kubernetes的版本是19.3.1，Prometheus的版本是2.26.0。

圖3 邊緣算力協(xié)同系統(tǒng)的技術架構圖

本次實驗將一類視頻智能分析任務定義成為一個job，每一類任務按監(jiān)控視頻數(shù)據(jù)資源標識以及時間段切分成不同個數(shù)的task，實驗調度的job信息如表1所示。其中，安全價值效益是咨詢安防專家意見后給出的。實驗中使用K8s對CPU內存資源進行度量，CPU的計量單位為毫(m)核，內存的計量單位為Mi。實驗中，設置控制中心Ctr的資源收集器收集計算節(jié)點資源消耗的周期τ為1 min，調度周期設置為5 min。

表1 實驗所調度的job定義

5.2 實驗與結果分析

為了評估本文方法的效果，將本文采用的動態(tài)規(guī)劃求解算法與貪心算法進行任務調度效果對比分析。實驗分別針對單計算節(jié)點任務調度以及多計算節(jié)點任務調度開展。

5.2.1 單計算節(jié)點

單計算節(jié)點任務調度實驗是在控制中心Ctr和1個計算節(jié)點之間進行的，實驗觀察的主要內容是：比較采用不同的任務分配算法時在計算節(jié)點上獲取的安全價值效益情況，以及執(zhí)行VIAT計算任務是否影響了主應用業(yè)務MAB的運行。

(1) 設置系統(tǒng)預留資源量

為了保證計算節(jié)點的穩(wěn)定運行，需要給系統(tǒng)預留的一定資源量，本實驗設置計算節(jié)點總CPU資源使用率λc為90%，總內存的使用率λm為90%。

(2) 調度前主業(yè)務應用MAB的資源消耗情況

在未進行視頻智能分析任務VIAT分配前，該計算節(jié)點上的主業(yè)務應用為辦公任務，其24 h內的資源消耗情況如圖4所示。

圖4 未進行任務調度前計算節(jié)點辦公業(yè)務資源消耗情況

(3) 實施動態(tài)任務調度后的資源消耗情況

圖5為本文算法與貪心算法分別在計算節(jié)點f上進行任務調度后的CPU資源消耗情況。由圖5可知，計算節(jié)點的CPU利用率較圖4有了穩(wěn)定提升，且總CPU資源消耗的平均值沒有超過85%，低于λc。表明不管是采用本文的動態(tài)規(guī)劃算法還是貪心算法進行動態(tài)任務調度后，從CPU資源維度上看，VIAT的執(zhí)行沒有影響f上主業(yè)務應用MAB的正常運行。

圖5 單計算節(jié)點動態(tài)規(guī)劃和貪心算法CPU消耗對比

圖6為本文算法與貪心算法分別在計算節(jié)點f上進行任務調度后的內存資源消耗情況。從圖6中可知，內存資源使用的峰值接近12 000 Mi，f上總內存為16 000 Mi，最高利用率約為75%，低于λm，表明從內存資源維度上看，VIAT的執(zhí)行沒有影響f上主業(yè)務應用MAB的正常運行。

圖6 單計算節(jié)點動態(tài)規(guī)劃和貪心算法內存消耗對比

(4) 獲得的安全價值效益分析

圖7給出了采用本文算法與采用貪心算法時所獲得的安全價值效益在不同時間段的對比情況。從圖7可知，本文算法進行任務調度所獲得的安全價值效益絕大部分時間段都高于貪心算法的收益。

圖7 單計算節(jié)點動態(tài)規(guī)劃和貪心算法價值效益對比

5.2.2 多計算節(jié)點場景

多計算節(jié)點任務調度實驗是在控制中心和兩個計算節(jié)點之間進行的，實驗觀察的主要內容是：計算節(jié)點之間對VIAT的協(xié)同處理情況；比較在多計算節(jié)點上采用不同的任務分配算法進行VIAT的協(xié)同處理時，所獲取的安全價值效益情況。

(1) 系統(tǒng)預留資源量的設置與單節(jié)點場景相同。

(2) 調度前主業(yè)務應用MAB的資源消耗情況在未進行視頻智能分析任務VIAT分配前，f1,f2上的主業(yè)務應用為辦公任務，兩個計算節(jié)點24 h內的資源消耗情況如圖8所示。

圖8 未進行任務調度前f1、f2上辦公業(yè)務資源消耗情況

(3) 實施動態(tài)任務調度后的資源消耗及任務協(xié)同情況

圖9為本文算法與貪心算法分別在f1,f2上進行任務調度后的CPU資源消耗情況。由圖9可知，計算節(jié)點上的CPU利用率較圖8有了穩(wěn)定提升，且VIAT的執(zhí)行沒有影響f上辦公主應用業(yè)務MAB的正常運行。

圖10為本文算法與貪心算法分別在f1,f2上進行任務調度后的內存資源消耗情況。由圖10可知，兩個節(jié)點的內存利用率提高了，且VIAT的執(zhí)行沒有影響節(jié)點上辦公主應用業(yè)務MAB的正常運行。

圖10 多計算節(jié)點動態(tài)規(guī)劃和貪心算法內存消耗對比

從圖9、圖10可知邊緣算力協(xié)同系統(tǒng)中f1,f2能對VIAT進行協(xié)同處理，主要體現(xiàn)在當系統(tǒng)節(jié)點上CPU資源變化時，調度器根據(jù)節(jié)點上CPU資源消耗情況進行任務調度，綜合考慮系統(tǒng)中計算節(jié)點的資源情況，將VIAT重新調度到合適的節(jié)點上運行。

(4) 獲得的安全價值效益分析

圖11給出了采用本文算法與采用貪心算法所獲得的安全價值效益在不同時間段的對比情況。從圖11可知，本文算法進行任務調度所獲得的安全價值效益絕大部分時間段都高于貪心算法的效益。

圖11 多計算節(jié)點動態(tài)規(guī)劃和貪心算法價值效益對比

6 結束語

本文以文物博物館單位需要使用更多算力來對更多的監(jiān)控視頻數(shù)據(jù)開展基于人工智能模型分析為需求，提出了基于邊緣算力協(xié)同系統(tǒng)的視頻智能分析任務動態(tài)調度方法。實驗數(shù)據(jù)表明，該方法能有效地將文物博物館單位內具有空閑計算資源的設備構建為一個邊緣算力協(xié)同系統(tǒng)，采用基于背包理論設計的任務分配算法能在不影響計算節(jié)點日常辦公應用服務正常運行的前提下實現(xiàn)視頻智能任務的動態(tài)調度，實現(xiàn)了充分利用有限資源完成視頻智能分析任務獲得最大安全價值效益的目的，提高了現(xiàn)有資源的利用率。本文雖然是以文物博物館單位的需求為背景開展的研究，但所提出的邊緣算力協(xié)同系統(tǒng)構建方法以及基于背包理論的任務分配算法不僅僅適用于此應用場景，對有類似需要充分利用系統(tǒng)資源的其他領域應用場景也具有適用性。