★中國科學(xué)技術(shù)大學(xué) 倪宏秋，談海生

★華為云鄭子木

1　邊緣計算中的在線(xiàn)智能

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

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

2　邊緣計算在線(xiàn)解決方案

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

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

其次，本團隊專(zhuān)注于基于在線(xiàn)深度增強學(xué)習的方法，以更好地利用現有數據資源。這一思路涉及高能效動(dòng)態(tài)虛擬機管理、5G異構網(wǎng)絡(luò )鏈路協(xié)同調度以及深度學(xué)習計算模型的調度等關(guān)鍵問(wèn)題。本團隊研究已經(jīng)實(shí)現了計算與網(wǎng)絡(luò )資源的在線(xiàn)管理、模型在線(xiàn)調度和計算優(yōu)化，為提升邊緣計算的效能提供了有力支持。

最后，本團隊以在線(xiàn)博弈思維為指導，考慮了多方利益博弈。這一思路引領(lǐng)了團隊在網(wǎng)絡(luò )資源擁塞博弈、云邊競爭在線(xiàn)定價(jià)以及多信道網(wǎng)絡(luò )中的信道匯合策略等領(lǐng)域取得了重要突破。本團隊已經(jīng)開(kāi)展了在線(xiàn)定價(jià)與博弈、網(wǎng)絡(luò )資源擁塞博弈等研究，為構建更具競爭力和協(xié)同性的在線(xiàn)邊緣計算環(huán)境提供了新的思路。

以下，本文將通過(guò)簡(jiǎn)要介紹邊緣計算中云邊端協(xié)同中的幾個(gè)關(guān)鍵技術(shù)的代表性工作，向大家闡述相關(guān)模型、算法和實(shí)現。

3　協(xié)同計算

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

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

3.1　在線(xiàn)任務(wù)分配與調度模型

在計算卸載問(wèn)題中，任務(wù)的分配和調度問(wèn)題是至關(guān)重要的。

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

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

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

圖1 邊緣計算架構圖

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

3.2　在線(xiàn)任務(wù)分配與調度算法

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

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

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

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

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

4　協(xié)同存儲

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

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

4.1　支持關(guān)聯(lián)及旁路的多緩存在線(xiàn)協(xié)作機制

在數據、服務(wù)在何處存儲這個(gè)方向，本團隊研究了支持關(guān)聯(lián)及旁路的多緩存在線(xiàn)協(xié)作機制。

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

圖2 移動(dòng)邊緣計算的典型示例

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

4.2　支持延遲命中及旁路的在線(xiàn)緩存算法

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

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

圖3 CaLa算法示例

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

5　結束語(yǔ)

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

作者簡(jiǎn)介：

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

談海生（1981-），男，教授，博士生導師，現任教于中國科學(xué)技術(shù)大學(xué)，研究方向為網(wǎng)絡(luò )算法與系統實(shí)現、邊緣計算、工業(yè)互聯(lián)網(wǎng)和AI Edge。

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

摘自《自動(dòng)化博覽》2023年10月刊