日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

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

★華為云鄭子木

1　邊緣計(jì)算中的在線智能

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

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

2　邊緣計(jì)算在線解決方案

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

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

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

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

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

3　協(xié)同計(jì)算

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

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

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

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

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

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

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

圖1 邊緣計(jì)算架構(gòu)圖

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

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

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

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

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

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

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

4　協(xié)同存儲(chǔ)

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

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

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

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

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

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

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

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

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

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

圖3 CaLa算法示例

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

5　結(jié)束語(yǔ)

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

作者簡(jiǎn)介：

倪宏秋（2000-），女，安徽人，博士生，現(xiàn)就讀于中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，主要研究方向?yàn)檫吘売?jì)算等。

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

鄭子木（1991-），男，廣東人，主任工程師，博士，現(xiàn)就職于華為云，研究方向?yàn)檫吘堿I、多任務(wù)學(xué)習(xí)及AIoT。

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