久久久91-久久久91精品国产一区二区-久久久91精品国产一区二区三区-久久久999国产精品-久久久999久久久精品

★中國科學技術大學 倪宏秋，談海生

★華為云鄭子木

1　邊緣計算中的在線智能

隨著大數據、IoT和人工智能等技術的蓬勃發展，網絡邊緣設備所產生的數據量開始快速增長，以云和數據中心為核心的集中式處理模式將無法快速處理邊緣設備所產生的海量數據。在該背景下，傳統的云計算場景中存在的實時性差、帶寬受限制、無法保證數據安全和隱私以及能耗高等問題也變得越來越突出。因此，為了解決或緩解這些問題，更好地為用戶提供服務，云計算的一個必然趨勢是將計算資源靠近數據源與用戶部署，就近提供低延遲、高安全、低成本云邊端協同計算服務，這就是邊緣計算。據預測，未來超過50%的數據需要在網絡邊緣側計算和存儲。

邊緣計算在自動駕駛、工業制造、IoT等領域的應用場景復雜多樣。同時，可以看到，在邊緣計算的重要應用場景，如移動計算中，用戶、計算任務、計算數據往往在線到達，這種在線到達的特點表現在它們的存在、到達的時間以及次序都是幾乎不可預測的。此外，移動計算設備所處的網絡環境與其能連接的邊緣計算服務器的計算環境也隨著時間和地點動態變化。而邊緣計算應用場景的一個顯著特點是低延遲要求。我們需要能夠實時做出決策，并且這些決策方案必須盡可能簡潔，以便能夠輕松部署在異構且分布式的邊緣節點上。這要求在處理動態到達的用戶、任務和數據時，能夠快速響應并執行相應的計算，以滿足實時性和效率的要求。因此，在線模型和在線智能是邊緣計算的固有需要。

2　邊緣計算在線解決方案

近幾年，本實驗室團隊一直致力于邊緣計算的在線解決方案的設計、分析與實現，并通過深入研究和充分利用三種核心思路，取得了令人鼓舞的初步成果。

首先，本團隊積極探索了基于在線近似算法的方法，以提供最差情況下的性能保證。這一思路涵蓋了云邊端協同在線任務分配和調度、在線協作存儲、在線協流調度等關鍵領域。我們的研究成果包括云邊端協同在線動態存儲和云邊端在線任務與數據流調度，為實現高效的在線邊緣計算奠定了堅實的基礎。

其次，本團隊專注于基于在線深度增強學習的方法，以更好地利用現有數據資源。這一思路涉及高能效動態虛擬機管理、5G異構網絡鏈路協同調度以及深度學習計算模型的調度等關鍵問題。本團隊研究已經實現了計算與網絡資源的在線管理、模型在線調度和計算優化，為提升邊緣計算的效能提供了有力支持。

最后，本團隊以在線博弈思維為指導，考慮了多方利益博弈。這一思路引領了團隊在網絡資源擁塞博弈、云邊競爭在線定價以及多信道網絡中的信道匯合策略等領域取得了重要突破。本團隊已經開展了在線定價與博弈、網絡資源擁塞博弈等研究，為構建更具競爭力和協同性的在線邊緣計算環境提供了新的思路。

以下，本文將通過簡要介紹邊緣計算中云邊端協同中的幾個關鍵技術的代表性工作，向大家闡述相關模型、算法和實現。

3　協同計算

在邊緣計算的背景下，計算卸載（即將工作負載從移動設備傳輸到邊緣云）是云邊端協同中的主要問題之一。在計算卸載問題中，需要決策用戶設備卸載哪些任務、卸載的任務分配到何處以及服務器中每個任務按什么順序執行等子問題。一個最佳的卸載解決方案必須合理利用異構資源，滿足不同的用戶需求，能處理復雜的網絡環境，同時還需要考慮用戶的移動性和任務的依賴性。計算卸載問題將直接影響用戶端的服務質量，因此設計適合的計算卸載算法對邊緣云與移動設備之間的有效協調至關重要。

移動設備到邊緣云的計算卸載流程主要體現在3個部分，如圖1所示，即移動設備、通信鏈路和邊緣云。具體而言，移動設備負責劃分應用程序，得到相應的卸載方案；通信鏈路負責上傳分區的傳輸，主要受帶寬、連接性和設備移動性的影響；邊緣云的服務器負責平衡服務器負載，以實現最大的服務效率和系統吞吐量。

3.1　在線任務分配與調度模型

在計算卸載問題中，任務的分配和調度問題是至關重要的。

任務分配問題指的是：任務經過劃分后，需要將任務從終端設備分配到邊緣服務器。分配任務時，需要結合任務的計算成本、任務與服務器之間的傳輸成本、邊緣服務器的情況等因素生成分配策略，按照分配策略將任務分配到最合適的邊緣服務器上進行計算。

任務調度問題指的是：當一定數量的計算任務被卸載到邊緣服務器或云服務器上后，需要設計服務器上的調度算法來決定任務隊列中任務的計算順序。另外，在滿足更優化的成本的情況下，調度策略中存在將當前服務器上的任務遷移到其他服務器的可能。

在一個邊緣計算系統中，由于任務以任意時間、次序在線到達，任務的信息在其到達前不可知；并且有若干異構邊緣服務器，它們執行同一任務時間各異；同時，網絡中也散布著諸多移動設備，移動端到服務器間的任務上傳和下載的網絡時延差異很大，更增加調度的不確定性。這些都為解決這一難題增添了挑戰。

圖1 邊緣計算架構圖

對此，文章定義了一個如下的在線任務分配與調度模型：首先在邊緣云系統中，共有k個異構邊緣云服務器，表示為K={s1,s2,...,sk}，每一個服務器對部分移動應用提供服務。其中，邊緣云服務器集合K中包含距離較遠，但是具有強大處理能力的遠程云服務器。任務被表示為J={j1,j2,...}，其中，任務集J中的每一個任務都是原子性的和不可分割的。rj表示為任務j發布的時間，當任務發布后，終端設備就會將任務分配給邊緣云服務器，并且當任務分配后，不會遷移到別的服務器上，由此，無須考慮任務遷移所帶來的成本。當任務j分配到服務器s_k后，任務在服務器上的處理時間表示為p_kj。任務的響應時間指的是任務發布到任務完全結束之間的時間。對于任務j和服務器s_k之間，設定一個時延敏感度w_kj，如果任務無法被分配到服務器上，則設定w值為無窮大。加權響應時間指的是時延敏感度與響應時間的乘積。

3.2　在線任務分配與調度算法

為解決在線計算卸載問題，基于上述系統模型，以最小化總加權響應時間為目標，本實驗室團隊設計了一個在線的、考慮任務上傳和下載時延的計算卸載問題的通用模型，并提出了第一個在線近似算法OnDisc算法，該算法研究了一種不需要考慮任務到達規律的在線任務分配與調度方案。

在調度策略上，OnDisc算法中的優化目標加權響應時間的權重由任務對時延的敏感度所決定。調度算法遵循著最高剩余密度優先的原則，該算法被稱為最高剩余密度優先算法，可以避免服務器上的任務頻繁切換。當所有任務都具有相同的權重w時，HRDF策略即等同于最短剩余時間優先策略。

在分配策略上，OnDisc基于貪婪的思想，根據加權延遲增量最小在線分配，期望使分配動作對總剩余加權密度的貢獻最小。

OnDisc算法在速度增強模型中具有可擴展性，本團隊證明了在速度增強模型下，OnDisc具有常數的競爭比。同時，本團隊也基于Google集群數據（包含120,000個任務）進行了大規模模擬，證明了集中式或分布式OnDisc均能顯著減少任務的平均響應時間。

可見，該提案模型非常通用化，算法設計簡潔，易于分布式部署，具有良好的理論性能保證，并有基于真實數據。

4　協同存儲

移動邊緣緩存利用了邊緣服務器提供的存儲資源，是MEC的使用案例之一。邊緣服務器附近的移動設備可以通過無線接入的方式訪問邊緣服務器。由于邊緣服務器距離移動設備更近，移動設備可以將其任務或文件緩存在附近的邊緣服務器上，這樣不僅擴展了本地移動設備的能力，還能夠避免遠程服務器與緩存連接的網絡節點之間的重復傳輸。而且，隨著存儲成本的降低，在無線邊緣端部署緩存變得性價比更高。

在邊緣計算場景中，多緩存問題是研究的重點。在邊緣計算場景中的緩存問題中，給定一個由K個插槽（頁）和一組文件組成的緩存。當請求在線到達，且所請求的文件在緩存中時，代價為0。否則，必須花費一定的獲取代價將文件獲取到緩存中。與遠程云數據中心相比，邊緣服務器的存儲能力是有限的，因此只能在每個邊緣服務器上部署部分文件，并且邊緣服務器上的文件會以一定的策略進行更新，以便更好地服務在線請求。

4.1　支持關聯及旁路的多緩存在線協作機制

在數據、服務在何處存儲這個方向，本團隊研究了支持關聯及旁路的多緩存在線協作機制。

這個問題考慮這樣一個場景：如圖2中，有一組通過互聯網連接的異構邊緣服務器和遠程云數據中心。開始時，每個邊緣服務器都可以從遠程云數據中心配置一些初始應用程序。對于到達邊緣服務器s請求文件f的請求r，表示為r:=(s,f)。如果服務器s已經配置好了文件f，那么可以在本地為其提供服務并且無額外代價，如圖中的請求r₁所示。如果應用程序不在服務器s上，那么可以選擇將請求轉發（Relay）到已經配置了文件f的附近的邊緣服務器上進行處理，并需要花費轉發代價，如圖2中的請求r₂所示。也可以選擇花費旁路（Bypass）代價執行旁路處理，直接繞過邊緣服務器到遠程云數據中心上，如圖2中的請求r₃所示。此外，為了更好地服務后續請求，邊緣服務器可能會從遠程云數據中心獲取（Fetch）某些特定的文件，并花費獲取代價重新配置文件。如果服務器已經滿了，還需要替換某些現有的文件以騰出空間，這時就需要去決定哪個文件f需要被存儲以及應該何時被安裝。基于這個問題，文章提出了Camul算法。

圖2 移動邊緣計算的典型示例

Camul算法是具有旁路和轉發的多緩存上的漸近最優在線緩存算法。該算法將旁路、轉發和獲取成本全部考慮在內，在不犧牲命中率的情況下降低了總成本。它貪心地選擇本地執行、關聯或旁路，通過標記決策決定是否選擇獲取。本團隊也基于Google數據集和Yahoo基準數據集進行了驗證，證明了文章所提出的算法可以減少高達85%的訪問開銷。

4.2　支持延遲命中及旁路的在線緩存算法

在CDN和MEC等實際應用中，由于物理距離較長，從遠程數據中心獲取丟失文件的時延可能超過100ms，而兩個連續文件請求的平均間隔時間可能低至1μs，例如，每秒有100萬個文件請求。而在從遠程數據中心檢索丟失文件的期間，是無法立即處理該文件的后續請求的，因此不應該簡單地將其視為命中。這種情況也不同于簡單的未命中，因為在將文件獲取到本地服務器后，請求可以作為命中。因此，我們稱這種情況為延遲命中（Delayed Hit）。此外，傳統的緩存模型假設所有丟失的文件在被訪問之前都必須被獲取并存儲在本地緩存中，而在與云相關的應用程序場景中，文件請求可以直接發送到遠程云，并在遠程云提供服務，我們稱之為旁路。

圖3展示了基于云的系統中的在線文件緩存，其中有一個本地緩存服務器和多個遠程數據中心，該系統具有文件未命中、命中、延遲命中和旁路的處理方式。X的第一個請求在T1到達，由于X未存儲在緩存中，因此這是一次未命中，會從數據中心1獲取X，并且由于獲取延遲，X在時間T3之前不會在本地緩存中就緒。然后，對X的另一個請求在T2到達（T1<T2<T3），它將被放置在緩沖區并在T3服務，這是一個延遲命中。第3個X的請求在T3到達，這是一個命中。對于T4時到達的Y請求，我們選擇直接旁路該請求，以避免緩存中的空間分配。

圖3 CaLa算法示例

本提案也考慮了在延遲命中和旁路的情況下，設計合理的在線緩存算法，以最小化請求的平均響應時間。該問題的難點在于文件請求在線到達，文件之間的大小和獲取延遲也可以任意，并且延遲命中的存在導致對一次文件未命中帶來的損失難以估計。針對該問題，我們通過給每個文件設定未命中代價上界來確定文件權重，并調用支持權重的經典緩存模型，以處理文件大小和代價均不一致的情況。本團隊證明了所設計的算法CaLa具有接近理論下界的競爭比，并且經過大規模實驗驗證，證明了CaLa相比當前最好算法可以減少32%的請求響應時間。

5　結束語

本文探討了邊緣計算領域中在線智能的重要性，旨在為讀者提供一個深入了解的窗口。文章簡要總結了邊緣計算在線解決方案，并在之后的內容中更詳細地介紹了本實驗室團隊在協同計算和協同存儲方面的代表性成果。同時，如果您希望深入了解更多關于邊緣計算、在線智能以及相關領域的知識，本團隊專著《邊緣計算理論與系統實踐：基于CNCFKubeEdge的實現》可能會為您提供更多深入了解的機會。

作者簡介：

倪宏秋（2000-），女，安徽人，博士生，現就讀于中國科學技術大學計算機科學與技術學院，主要研究方向為邊緣計算等。

談海生（1981-），男，教授，博士生導師，現任教于中國科學技術大學，研究方向為網絡算法與系統實現、邊緣計算、工業互聯網和AI Edge。

鄭子木（1991-），男，廣東人，主任工程師，博士，現就職于華為云，研究方向為邊緣AI、多任務學習及AIoT。

摘自《自動化博覽》2023年10月刊