孫鈺坤，張 興，雷 波

(1.北京郵電大學(xué) 泛網(wǎng)無線通信教育部重點(diǎn)實(shí)驗(yàn)室，北京 100876；2.中國電信股份有限公司研究院，北京 102209)

0 引言

隨著人工智能與移動(dòng)互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，增強(qiáng)現(xiàn)實(shí)、人臉識(shí)別、圖像渲染、自動(dòng)駕駛等新型業(yè)務(wù)應(yīng)用大量涌現(xiàn)，這些新型業(yè)務(wù)應(yīng)用通常需要消耗巨大的計(jì)算資源、存儲(chǔ)資源以及能耗，目前智能終端設(shè)備的計(jì)算能力尚且比較有限，電池容量也比較低，無法滿足這些新興業(yè)務(wù)應(yīng)用的處理需求。因此，云計(jì)算得以提出并持續(xù)升溫。

云計(jì)算利用虛擬化技術(shù)建立超大容量的算力資源池，使得各種應(yīng)用可以獲得所需的計(jì)算資源、存儲(chǔ)資源以及軟件和平臺(tái)服務(wù)。云計(jì)算的出現(xiàn)滿足了計(jì)算密集型的業(yè)務(wù)處理需求，但是，自動(dòng)駕駛這一類智能應(yīng)用同時(shí)具有時(shí)延敏感的特性，終端到云端的傳輸時(shí)延在很多情況下無法滿足這一類應(yīng)用對(duì)于超低時(shí)延的需求。因此，ETSI于2014年12月成立移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)行業(yè)規(guī)范組(Industry Specification Group,ISG)，啟動(dòng)移動(dòng)邊緣計(jì)算標(biāo)準(zhǔn)化，以發(fā)展移動(dòng)邊緣計(jì)算[1]。ETSI將MEC定義為一種可以在無線接入網(wǎng)絡(luò)中移動(dòng)用戶附近位置提供IT和云計(jì)算功能的網(wǎng)絡(luò)架構(gòu)，旨在將IT和云計(jì)算從核心網(wǎng)絡(luò)遷移到邊緣接入網(wǎng)絡(luò)，以縮短任務(wù)處理端到端的時(shí)延，并確保數(shù)據(jù)的安全性與隱私性。2016年9月移動(dòng)邊緣計(jì)算的概念被擴(kuò)展為多接入邊緣計(jì)算(Multi-access Edge Computing,MEC)，將移動(dòng)邊緣計(jì)算從電信蜂窩網(wǎng)絡(luò)進(jìn)一步延伸至其他無線網(wǎng)絡(luò)，以擴(kuò)大邊緣計(jì)算在包括WiFi和固定訪問技術(shù)在內(nèi)的異構(gòu)網(wǎng)絡(luò)中的適用性。

邊緣計(jì)算設(shè)備和智能終端設(shè)備的大量部署，雖然解決了網(wǎng)絡(luò)中海量數(shù)據(jù)上傳至云計(jì)算中心導(dǎo)致的帶寬緊缺、網(wǎng)絡(luò)擁塞、時(shí)延過長(zhǎng)的問題，但也使得算力資源呈現(xiàn)泛在部署的趨勢(shì)，不可避免地出現(xiàn)了“算力孤島”效應(yīng)。一方面，邊緣計(jì)算節(jié)點(diǎn)沒有進(jìn)行有效的協(xié)同處理任務(wù)，單一節(jié)點(diǎn)的算力資源無法滿足如圖像渲染等超大型的計(jì)算密集型任務(wù)的算力資源需求，仍然無法解決同時(shí)具有計(jì)算密集和時(shí)延敏感特性的新型業(yè)務(wù)的超低時(shí)延需求問題；另一方面，雖然一些邊緣計(jì)算節(jié)點(diǎn)出現(xiàn)超負(fù)載無法有效處理計(jì)算任務(wù)的情況，但是由于網(wǎng)絡(luò)負(fù)載的不均衡，勢(shì)必會(huì)有一些計(jì)算節(jié)點(diǎn)仍然處于空閑的狀態(tài)，導(dǎo)致邊緣網(wǎng)絡(luò)的算力資源無法得到充分的利用。

因此，為了高效、協(xié)同地利用全網(wǎng)異構(gòu)的算力資源，2019年由運(yùn)營商、設(shè)備商等主導(dǎo)提出一種基于分布式系統(tǒng)的計(jì)算與網(wǎng)絡(luò)融合的技術(shù)方案——算力感知網(wǎng)絡(luò)[2-5](Computing-aware Networking,CAN),以實(shí)現(xiàn)ICT系統(tǒng)的聯(lián)合優(yōu)化調(diào)度，提供端到端的體驗(yàn)保證。CAN旨在將云邊端多樣的算力通過網(wǎng)絡(luò)的方式連接與協(xié)同，實(shí)現(xiàn)計(jì)算與網(wǎng)絡(luò)的深度融合及協(xié)同感知，以及算力資源的按需調(diào)度和高效共享[6-10]。

算力感知路由和算力資源分配是算力感知網(wǎng)絡(luò)研究中的一個(gè)關(guān)鍵問題，在傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)中，算力與網(wǎng)絡(luò)通常是單獨(dú)進(jìn)行管理。在算力管理方面，計(jì)算卸載技術(shù)作為邊緣計(jì)算的一項(xiàng)關(guān)鍵技術(shù)，在邊緣計(jì)算概念被提出之后，便有許多研究者提出基于單用戶多節(jié)點(diǎn)[11]、多用戶單節(jié)點(diǎn)[12]以及多用戶多節(jié)點(diǎn)[13-14]的任務(wù)卸載策略，這些策略實(shí)質(zhì)上都是將終端任務(wù)與邊緣計(jì)算節(jié)點(diǎn)進(jìn)行完美匹配。在網(wǎng)絡(luò)管理方面，研究主要集中在如何優(yōu)化任務(wù)路由策略[15]。

針對(duì)目前研究存在的問題，本文在多任務(wù)、多路由節(jié)點(diǎn)、多邊緣服務(wù)器的邊緣算力網(wǎng)絡(luò)場(chǎng)景下，分別基于用戶業(yè)務(wù)側(cè)、網(wǎng)絡(luò)側(cè)、邊緣計(jì)算資源池側(cè)，構(gòu)建算力需求、網(wǎng)絡(luò)狀態(tài)、算力資源的感知信息模型；基于感知信息模型，在計(jì)算資源和存儲(chǔ)資源的約束限制下，以用戶業(yè)務(wù)的調(diào)度傳輸時(shí)延最小化為優(yōu)化目標(biāo)，聯(lián)合優(yōu)化路由控制、計(jì)算節(jié)點(diǎn)的選擇和存儲(chǔ)、算力資源的分配；最后，本文提出了基于Floyd的算力感知路由分配策略，有效地將算力與網(wǎng)絡(luò)進(jìn)行協(xié)同管理，緩解網(wǎng)絡(luò)負(fù)載不均衡的問題，并通過仿真分析了所提策略在改善用戶業(yè)務(wù)體驗(yàn)以及算網(wǎng)資源利用率方面的性能。

1 任務(wù)調(diào)度系統(tǒng)建模

1.1 算力感知網(wǎng)絡(luò)系統(tǒng)概述

如圖1所示，算力感知網(wǎng)絡(luò)系統(tǒng)由終端設(shè)備、基站以及邊緣網(wǎng)關(guān)(路由節(jié)點(diǎn))、邊緣服務(wù)器(邊緣計(jì)算節(jié)點(diǎn))和云中心組成。其中用戶業(yè)務(wù)由終端設(shè)備發(fā)起請(qǐng)求，通過無線鏈路傳輸至基站；邊緣網(wǎng)關(guān)主要負(fù)責(zé)路由控制和數(shù)據(jù)轉(zhuǎn)發(fā)，在實(shí)際網(wǎng)絡(luò)系統(tǒng)中，邊緣網(wǎng)關(guān)可以部署在基站側(cè)，路由節(jié)點(diǎn)之間可以通過實(shí)時(shí)動(dòng)態(tài)的鏈路進(jìn)行數(shù)據(jù)傳輸；邊緣服務(wù)器是以硬件基礎(chǔ)設(shè)施為虛擬化資源的邊緣應(yīng)用平臺(tái)，主要負(fù)責(zé)提供存儲(chǔ)和計(jì)算資源，進(jìn)行用戶業(yè)務(wù)的處理，邊緣計(jì)算節(jié)點(diǎn)與路由節(jié)點(diǎn)之間通過固定鏈路進(jìn)行數(shù)據(jù)傳輸；云中心具有充足的存儲(chǔ)資源和計(jì)算資源，是部署在距離用戶較遠(yuǎn)位置的大型服務(wù)器集群，邊緣計(jì)算節(jié)點(diǎn)與云中心節(jié)點(diǎn)之間具有固定的鏈路進(jìn)行數(shù)據(jù)傳輸，雖然在本文的系統(tǒng)模型中，假設(shè)用戶業(yè)務(wù)只在由邊緣計(jì)算節(jié)點(diǎn)組成的邊緣算力感知網(wǎng)絡(luò)中進(jìn)行處理，但是云中心是算力感知網(wǎng)絡(luò)架構(gòu)中不可或缺的一部分，因此在圖1中予以表示。

圖1 算力感知網(wǎng)絡(luò)系統(tǒng)Fig.1 System of computing-aware networks

1.2 任務(wù)模型

假設(shè)算力感知網(wǎng)絡(luò)系統(tǒng)中共有M個(gè)終端設(shè)備，終端設(shè)備的集合表示為Μ={1,2,...,M}，m∈Μ表示一個(gè)終端設(shè)備，假設(shè)每個(gè)終端設(shè)備每次最多發(fā)起一個(gè)計(jì)算任務(wù)處理請(qǐng)求。

假設(shè)算力感知網(wǎng)絡(luò)系統(tǒng)中共存在K個(gè)用戶業(yè)務(wù)，用戶業(yè)務(wù)的集合表示為Κ={1,2,...,K}，k∈Κ表示一個(gè)用戶業(yè)務(wù)。第k個(gè)用戶業(yè)務(wù)可以表示為Sk(Ak,Xk,Ck,Dkmax,Dka,Bk)，其中Ak表示用戶業(yè)務(wù)k所接入的路由節(jié)點(diǎn)，Xk表示用戶業(yè)務(wù)k所需要的存儲(chǔ)資源的量化值，Ck表示用戶業(yè)務(wù)k所需要的計(jì)算資源的量化值(中央處理器的轉(zhuǎn)數(shù)/比特?cái)?shù)據(jù)/秒，即單位時(shí)間處理單位比特?cái)?shù)據(jù)所需要的中央處理器的轉(zhuǎn)數(shù))，Dkmax表示用戶業(yè)務(wù)k允許的最大業(yè)務(wù)處理時(shí)延，Dka表示用戶業(yè)務(wù)k接入路由節(jié)點(diǎn)的時(shí)延，Bk表示用戶業(yè)務(wù)k的大小。

1.3 通信模型

終端設(shè)備發(fā)出請(qǐng)求的用戶業(yè)務(wù)通過無線鏈路傳輸?shù)剿懔Ω兄W(wǎng)絡(luò)中的邊緣無線接入點(diǎn)，根據(jù)香農(nóng)定理，用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak的數(shù)據(jù)傳輸速率可以表示為：

Rk,Ak=Bk,Aklb(1+γk,Ak)，

(1)

其中，Bk,Ak表示用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak信道的帶寬，γk,Ak表示用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak傳輸?shù)男旁氡?Signal Noise Ratio,SNR),表示為：

(2)

式中，pk,Ak表示用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak的發(fā)射功率，N0表示加性高斯白噪聲的譜密度，hk,Ak表示用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak的路徑損耗，hk,Ak的大小與用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak之間的距離有關(guān)，距離越遠(yuǎn)，路徑損耗越大。本文主要研究終端設(shè)備發(fā)出的業(yè)務(wù)請(qǐng)求在算力感知網(wǎng)絡(luò)中如何基于感知的信息路由調(diào)度到最佳的算力節(jié)點(diǎn)上進(jìn)行業(yè)務(wù)處理，因此沒有考慮用戶業(yè)務(wù)的位置分布，而是將用戶業(yè)務(wù)到所接入的路由節(jié)點(diǎn)的數(shù)據(jù)傳輸速率進(jìn)行統(tǒng)一的量化表示。

綜上所述，用戶業(yè)務(wù)k到所接入的路由節(jié)點(diǎn)Ak的接入時(shí)延為：

(3)

終端設(shè)備發(fā)出請(qǐng)求的用戶業(yè)務(wù)在算力感知網(wǎng)絡(luò)中,通過動(dòng)態(tài)的通信鏈路在相鄰的路由節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)傳輸，假設(shè)在算力感知網(wǎng)絡(luò)中路由節(jié)點(diǎn)之間動(dòng)態(tài)鏈路的數(shù)據(jù)傳輸速率可以感知，則表示為：

式中，wi,j表示路由節(jié)點(diǎn)i與路由節(jié)點(diǎn)j之間的數(shù)據(jù)傳輸速率，滿足

(4)

因此，用戶業(yè)務(wù)k在路由節(jié)點(diǎn)i和路由節(jié)點(diǎn)j之間的傳輸時(shí)延為：

(5)

算力感知網(wǎng)絡(luò)中的計(jì)算節(jié)點(diǎn)與路由節(jié)點(diǎn)之間通過固定鏈路進(jìn)行數(shù)據(jù)傳輸，路由節(jié)點(diǎn)i到計(jì)算節(jié)點(diǎn)n之間的數(shù)據(jù)傳輸速率可以表示為：

(6)

因此，如果用戶業(yè)務(wù)k選擇計(jì)算節(jié)點(diǎn)n，則通過路由節(jié)點(diǎn)傳輸?shù)接?jì)算節(jié)點(diǎn)n的到達(dá)時(shí)延為：

(7)

1.4 計(jì)算、存儲(chǔ)資源模型

在算力感知網(wǎng)絡(luò)系統(tǒng)中，網(wǎng)絡(luò)控制面需要實(shí)時(shí)感知計(jì)算節(jié)點(diǎn)的存儲(chǔ)資源以及算力資源狀態(tài)。假設(shè)網(wǎng)絡(luò)中存在N個(gè)計(jì)算節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)的集合表示為Ν={1,2,...,N}，n∈Ν表示一個(gè)計(jì)算節(jié)點(diǎn)，則第n個(gè)計(jì)算節(jié)點(diǎn)可表示為Zn(An,Xn,Cn,Rn)，其中An表示該計(jì)算節(jié)點(diǎn)連接的路由節(jié)點(diǎn)標(biāo)簽，Xn表示該計(jì)算節(jié)點(diǎn)的存儲(chǔ)資源大小，Cn表示該計(jì)算節(jié)點(diǎn)的計(jì)算資源大小(中央處理器的轉(zhuǎn)數(shù)/比特?cái)?shù)據(jù)/秒，即單位時(shí)間處理單位比特?cái)?shù)據(jù)所需要的中央處理器轉(zhuǎn)數(shù))，Rn表示該計(jì)算節(jié)點(diǎn)到路由節(jié)點(diǎn)的數(shù)據(jù)傳輸速率。

綜上所述，當(dāng)計(jì)算節(jié)點(diǎn)的存儲(chǔ)資源、計(jì)算資源滿足用戶業(yè)務(wù)需求時(shí)，用戶業(yè)務(wù)的計(jì)算時(shí)延為：

(8)

2 任務(wù)調(diào)度優(yōu)化模型

在上述算力感知網(wǎng)絡(luò)系統(tǒng)架構(gòu)模型、任務(wù)模型、通信模型、計(jì)算和存儲(chǔ)資源模型的基礎(chǔ)上，一個(gè)任務(wù)處理的總時(shí)延包括任務(wù)接入時(shí)延、任務(wù)傳輸時(shí)延、任務(wù)到達(dá)計(jì)算節(jié)點(diǎn)時(shí)延、任務(wù)處理時(shí)延和任務(wù)等待時(shí)延，由于任務(wù)處理時(shí)延和任務(wù)等待時(shí)延在確定的算力需求條件下具有統(tǒng)一性，因此可以在優(yōu)化模型中不予考慮，所以用戶業(yè)務(wù)k到調(diào)度的計(jì)算節(jié)點(diǎn)的傳輸時(shí)延為：

tk,t=Dka+Dt+Dk,n,a。

(9)

考慮聯(lián)合優(yōu)化計(jì)算任務(wù)路由策略和算力資源的分配，本文將最終的計(jì)算任務(wù)調(diào)度優(yōu)化問題建模為：

(10)

目標(biāo)函數(shù)的約束條件如下：

(11)

(12)

式中，Κn表示調(diào)度到計(jì)算節(jié)點(diǎn)n的所有用戶業(yè)務(wù)的集合，約束條件(11)表示調(diào)度到計(jì)算節(jié)點(diǎn)的所有用戶業(yè)務(wù)可利用的存儲(chǔ)資源不超過該計(jì)算節(jié)點(diǎn)可以提供的存儲(chǔ)資源，約束條件(12)表示調(diào)度到計(jì)算節(jié)點(diǎn)的所有用戶業(yè)務(wù)可利用的計(jì)算資源不超過該計(jì)算節(jié)點(diǎn)可以提供的計(jì)算資源。

由于當(dāng)算力感知網(wǎng)絡(luò)處于部分計(jì)算節(jié)點(diǎn)過載，或者全網(wǎng)計(jì)算節(jié)點(diǎn)過載的情況時(shí)，根據(jù)最小化用戶業(yè)務(wù)傳輸時(shí)延的目標(biāo)得到的調(diào)度策略，部分用戶業(yè)務(wù)勢(shì)必會(huì)因?yàn)樗懔Y源短缺而無法按需完成任務(wù)處理，考慮實(shí)際工程問題的可行性以及算法的復(fù)雜度，需要重點(diǎn)關(guān)注的不是如何精確地求出最優(yōu)解，而是在如何保證用戶公平性的前提下，高效快速地獲得一個(gè)聯(lián)合優(yōu)化路徑選擇與計(jì)算節(jié)點(diǎn)選擇的次優(yōu)解，本文提出一種基于Floyd的算力感知路由分配(CARA)算法來解決該問題，為計(jì)算任務(wù)均衡選擇優(yōu)化的路徑以及計(jì)算節(jié)點(diǎn)。

3 基于Floyd的算力感知路由分配算法

Floyd算法是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法。在算力感知網(wǎng)絡(luò)架構(gòu)中，路由控制器可以感知用戶業(yè)務(wù)的數(shù)據(jù)大小和網(wǎng)絡(luò)的鏈路狀態(tài)(包括鏈路的數(shù)據(jù)傳輸速率、抖動(dòng)以及丟包率等)。因此，可以根據(jù)網(wǎng)絡(luò)感知的信息計(jì)算出用戶業(yè)務(wù)經(jīng)過網(wǎng)絡(luò)中任意一條鏈路的傳輸時(shí)延，所有的終端設(shè)備、路由節(jié)點(diǎn)、計(jì)算節(jié)點(diǎn)和動(dòng)態(tài)的鏈路時(shí)延構(gòu)成一個(gè)實(shí)時(shí)變化的多源點(diǎn)加權(quán)圖。

算力感知網(wǎng)絡(luò)中計(jì)算任務(wù)調(diào)度策略的優(yōu)化目標(biāo)之一便是最短傳輸時(shí)延的路徑選擇，基于Floyd算法可以計(jì)算出將用戶業(yè)務(wù)路由至各個(gè)節(jié)點(diǎn)的最短時(shí)延以及其對(duì)應(yīng)的具體調(diào)度路徑，進(jìn)而選擇時(shí)延最短的計(jì)算節(jié)點(diǎn)作為最佳計(jì)算節(jié)點(diǎn)及根據(jù)Floyd算法確定的路徑作為最優(yōu)路由策略，如算法1所示。

算法1 基于Floyd算法的算力感知路由分配策略輸入:算力感知網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)狀態(tài)Z,計(jì)算節(jié)點(diǎn)數(shù)目N,算力感知網(wǎng)絡(luò)中鏈路狀態(tài)W,用戶業(yè)務(wù)的算力需求S,用戶業(yè)務(wù)數(shù)目K輸出:任務(wù)調(diào)度路徑P,任務(wù)處理節(jié)點(diǎn)X1:基于Floyd算法計(jì)算將用戶業(yè)務(wù)路由至各個(gè)計(jì)算節(jié)點(diǎn)的最短時(shí)延Dmin,獲取最優(yōu)調(diào)度路徑P'2:根據(jù)Dmin選擇時(shí)延最短的計(jì)算節(jié)點(diǎn)以及對(duì)應(yīng)路徑作為調(diào)度策略,計(jì)算最短時(shí)延D*min,獲取最優(yōu)調(diào)度路徑P*和最佳計(jì)算節(jié)點(diǎn)N*3:for k=1:Kdo4: for n=1:Ndo5: ifN*(k)==n6: ifSk,2≤Nn,2且Sk,3≤Nn,37: 最佳計(jì)算節(jié)點(diǎn)N*不變8: 最優(yōu)調(diào)度路徑P*不變9:更新節(jié)點(diǎn)存儲(chǔ)資源狀態(tài) Nn,2:=Nn,2-Sk,210:更新節(jié)點(diǎn)計(jì)算資源狀態(tài) Nn,3:=Nn,3-Sk,311: else12: 重復(fù)步驟6的判斷,依次循環(huán)遍歷N個(gè)節(jié)點(diǎn)直到資源滿足或者回到初始節(jié)點(diǎn)停止13: 更新最佳計(jì)算節(jié)點(diǎn)N*(回到初始不更新)14:更新最優(yōu)調(diào)度路徑P*(回到初始不更新)15:更新節(jié)點(diǎn)存儲(chǔ)資源狀態(tài) N*,2:=N*,2-S*,216:更新節(jié)點(diǎn)計(jì)算資源狀態(tài) N*,3:=N*,3-S*,317: end if18: end if19: end for20: end for 21: return 最佳計(jì)算節(jié)點(diǎn)N*,最優(yōu)調(diào)度路徑P*

然而，算力感知網(wǎng)絡(luò)作為一種面向B5G/6G通信的新型網(wǎng)絡(luò)架構(gòu)，與傳統(tǒng)的無線網(wǎng)絡(luò)面臨同樣的問題，即網(wǎng)絡(luò)負(fù)載不均衡，網(wǎng)絡(luò)中部分計(jì)算節(jié)點(diǎn)的計(jì)算任務(wù)超過所能容納的最大任務(wù)數(shù)目，導(dǎo)致計(jì)算任務(wù)的處理時(shí)延過長(zhǎng)，無法滿足時(shí)延敏感型的新型網(wǎng)絡(luò)業(yè)務(wù)需求。與此同時(shí)，網(wǎng)絡(luò)中另一部分節(jié)點(diǎn)可能沒有計(jì)算任務(wù)達(dá)到，處于資源空閑狀態(tài)，沒有充分利用全網(wǎng)的算力資源，導(dǎo)致算力資源利用率低下。因此，僅僅基于Floyd算法選擇最短時(shí)延的路由策略，進(jìn)而確定計(jì)算節(jié)點(diǎn)的方案在網(wǎng)絡(luò)負(fù)載不均衡的情況下，無法聯(lián)合優(yōu)化計(jì)算任務(wù)路由策略和算力資源的分配。

如算法1中第3～20步所示，根據(jù)Floyd算法已經(jīng)確定的路由分配策略，如果一個(gè)計(jì)算任務(wù)被分配的計(jì)算節(jié)點(diǎn)已經(jīng)過載，則將計(jì)算任務(wù)循環(huán)調(diào)度到下一個(gè)有剩余算力資源的計(jì)算節(jié)點(diǎn)。為保證用戶的公平性，計(jì)算任務(wù)按照標(biāo)簽順序優(yōu)先獲取網(wǎng)絡(luò)的算力資源；為降低算法的計(jì)算復(fù)雜度，計(jì)算任務(wù)在重新選擇計(jì)算節(jié)點(diǎn)時(shí)，默認(rèn)循環(huán)至下一個(gè)有剩余算力資源的計(jì)算節(jié)點(diǎn)即可，無需再次基于Floyd算法優(yōu)化調(diào)度策略。

假設(shè)邊緣算力網(wǎng)絡(luò)系統(tǒng)中路由節(jié)點(diǎn)的個(gè)數(shù)為R，則本文基于Floyd算法的CARA策略的算法時(shí)間復(fù)雜度為O(R3KN2)，若使用暴力搜索算法來遍歷求解用戶業(yè)務(wù)的計(jì)算節(jié)點(diǎn)選擇、路由控制以及存儲(chǔ)、算力資源分配，其時(shí)間復(fù)雜度為O(NKRR)，相比于具有指數(shù)級(jí)時(shí)間復(fù)雜度的暴力搜索算法，隨著路由節(jié)點(diǎn)和用戶業(yè)務(wù)數(shù)目的增加，本文方法時(shí)間復(fù)雜度顯著下降。

4 仿真實(shí)驗(yàn)

本節(jié)對(duì)基于Floyd 算法的算力感知路由分配(CARA)策略進(jìn)行仿真實(shí)驗(yàn)。首先對(duì)仿真場(chǎng)景和參數(shù)進(jìn)行說明，然后展示仿真結(jié)果并對(duì)其進(jìn)行分析。

4.1 仿真場(chǎng)景與仿真參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中，考慮多終端設(shè)備、多路由節(jié)點(diǎn)、多邊緣計(jì)算節(jié)點(diǎn)的場(chǎng)景，如圖2所示。在模擬的算力感知網(wǎng)絡(luò)系統(tǒng)中，包含3個(gè)邊緣計(jì)算節(jié)點(diǎn)、6個(gè)邊緣路由節(jié)點(diǎn)，以及若干發(fā)出業(yè)務(wù)請(qǐng)求的終端設(shè)備，其數(shù)量可以進(jìn)行具體的設(shè)定，所接入的路由節(jié)點(diǎn)隨機(jī)生成。路由節(jié)點(diǎn)之間的鏈路動(dòng)態(tài)連接，相連兩個(gè)路由節(jié)點(diǎn)之間的數(shù)據(jù)傳輸速率動(dòng)態(tài)變化，如圖2的權(quán)值所示，計(jì)算節(jié)點(diǎn)與路由節(jié)點(diǎn)之間的鏈路連接固定，各個(gè)節(jié)點(diǎn)之間的鏈路連接情況以及數(shù)據(jù)數(shù)傳速率如圖2所示。

圖2 仿真場(chǎng)景Fig.2 Simulation topology

如表1所示，設(shè)置默認(rèn)情況下的算力感知網(wǎng)絡(luò)系統(tǒng)參數(shù)。

表1 仿真參數(shù)設(shè)置

假設(shè)K個(gè)用戶業(yè)務(wù)均為同時(shí)發(fā)起，算力感知網(wǎng)絡(luò)的初始狀態(tài)為無任何任務(wù)執(zhí)行。

以圖2所示的網(wǎng)絡(luò)場(chǎng)景作為測(cè)試系統(tǒng)，與本文提出的CARA策略進(jìn)行對(duì)比的就近調(diào)度算法描述如下：用戶業(yè)務(wù)始終選擇部署位置最近的計(jì)算節(jié)點(diǎn)，即接入R1、R2的用戶業(yè)務(wù)選擇N1計(jì)算節(jié)點(diǎn)，接入R3、R5的用戶業(yè)務(wù)選擇N3計(jì)算節(jié)點(diǎn)，接入R4、R6的用戶業(yè)務(wù)選擇N2計(jì)算節(jié)點(diǎn)。

4.2 評(píng)價(jià)指標(biāo)

4.2.1 滿意用戶數(shù)

若任務(wù)獲得所需要的算力資源，而且任務(wù)處理完成總時(shí)延不超過允許的最大時(shí)延，則認(rèn)為業(yè)務(wù)處理成功，即：

(13)

(14)

I(k)=I(k1)I(k2)。

(15)

因此，滿意用戶數(shù)為：

(16)

4.2.2 業(yè)務(wù)平均處理時(shí)延

為了統(tǒng)計(jì)所有K個(gè)用戶業(yè)務(wù)的平均任務(wù)完成時(shí)延，本文將網(wǎng)絡(luò)超負(fù)載之后沒有得到所需算力資源的用戶業(yè)務(wù)處理時(shí)間附加等待時(shí)延：

(17)

式中，Κout為過載之后沒有獲取所需的算力資源的用戶業(yè)務(wù)集合。

綜上所述，系統(tǒng)中用戶業(yè)務(wù)的平均處理時(shí)延為：

(18)

4.2.3 算力資源利用率

算力感知網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)的存儲(chǔ)資源利用率為網(wǎng)絡(luò)中使用的存儲(chǔ)資源與網(wǎng)絡(luò)中節(jié)點(diǎn)存儲(chǔ)資源總和的比值[16]，表示為：

(19)

算力感知網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)的計(jì)算資源利用率為網(wǎng)絡(luò)中使用的計(jì)算資源與網(wǎng)絡(luò)中節(jié)點(diǎn)的計(jì)算資源總和的比值[16]，表示為：

(20)

4.3 仿真結(jié)果與分析

4.3.1 滿意用戶數(shù)

系統(tǒng)負(fù)載均衡時(shí)滿意的用戶數(shù)與系統(tǒng)用戶總數(shù)的關(guān)系如圖3所示，系統(tǒng)負(fù)載不均衡時(shí)滿意的用戶數(shù)與系統(tǒng)用戶總數(shù)的關(guān)系如圖4所示。

圖3 滿意用戶數(shù)與用戶數(shù)目關(guān)系(負(fù)載均衡)Fig.3 Number of satisfied users vs users( load balance)

圖4 滿意用戶數(shù)與用戶數(shù)目關(guān)系(負(fù)載不均衡)Fig.4 Number of satisfied users vs users (load un balance)

由圖3和圖4可以看出，采取CARA策略滿意的用戶數(shù)一直大于或等于就近調(diào)度策略，而且隨著用戶數(shù)目的增加或者負(fù)載不均衡時(shí)，效果更為明顯。當(dāng)負(fù)載不均衡時(shí)，采取就近調(diào)度策略滿意用戶數(shù)目不隨著用戶總數(shù)的增加而增加，很快陷入系統(tǒng)部分飽和狀態(tài)，而采取CARA策略直到系統(tǒng)資源全部耗盡才陷入超負(fù)載狀態(tài)。

4.3.2 業(yè)務(wù)平均處理時(shí)延

算力感知網(wǎng)絡(luò)中用戶業(yè)務(wù)平均處理時(shí)延與系統(tǒng)中用戶總數(shù)的關(guān)系如圖5所示。隨著系統(tǒng)用戶數(shù)目的增加，CARA調(diào)度策略和就近調(diào)度策略產(chǎn)生的平均時(shí)延幾乎都在增加。在網(wǎng)絡(luò)負(fù)載均衡和負(fù)載不均衡兩種情況下，采取CARA調(diào)度策略產(chǎn)生的用戶業(yè)務(wù)平均處理時(shí)延均小于就近調(diào)度策略，而且隨著系統(tǒng)用戶數(shù)目的增加，采取CARA策略縮短的時(shí)延效果更為顯著。在系統(tǒng)負(fù)載不均衡時(shí)，采取CARA調(diào)度策略縮短的時(shí)延也更為明顯，而且隨著系統(tǒng)用戶數(shù)目增加到一定數(shù)量之后，在負(fù)載不均衡的情況下采取CARA調(diào)度策略的時(shí)延，也小于在負(fù)載均衡情況下采取就近調(diào)度策略的時(shí)延。

圖5 時(shí)延與用戶數(shù)目關(guān)系Fig.5 Average delay vs the number of users

4.3.3 存儲(chǔ)資源利用率

存儲(chǔ)資源利用率與系統(tǒng)中用戶總數(shù)的關(guān)系如圖6所示。

圖6 存儲(chǔ)資源利用率Fig.6 Storage resource utilization ratio

由圖6可以看出，在系統(tǒng)負(fù)載均衡與系統(tǒng)負(fù)載不均衡兩種情況下，采取CARA調(diào)度策略時(shí)系統(tǒng)的存儲(chǔ)資源利用率隨著用戶數(shù)目增加一直在提高，即使在超負(fù)載的情況下，存儲(chǔ)資源也沒有被完全利用，分析原因?yàn)榇藭r(shí)系統(tǒng)的計(jì)算資源已經(jīng)完全耗盡，存儲(chǔ)資源與計(jì)算資源是協(xié)同處理計(jì)算任務(wù)的，當(dāng)存儲(chǔ)資源與計(jì)算資源沒有完全適配計(jì)算任務(wù)時(shí)，會(huì)有一種資源無法得到充分利用。采取CARA調(diào)度策略得到的存儲(chǔ)資源利用率隨著用戶數(shù)目的增加越來越高于采取就近調(diào)度策略得到的存儲(chǔ)資源利用率，而且在系統(tǒng)負(fù)載不均衡時(shí)，優(yōu)勢(shì)更為明顯。

4.3.4 計(jì)算資源利用率

計(jì)算資源利用率與系統(tǒng)中用戶總數(shù)的關(guān)系如圖7所示。

圖7 計(jì)算資源利用率Fig.7 Computing resource utilization ratio

由圖7可以看出，在系統(tǒng)負(fù)載均衡和系統(tǒng)負(fù)載不均衡兩種情況下，采取CARA調(diào)度策略時(shí)系統(tǒng)的計(jì)算資源利用率隨著用戶數(shù)目的增加一直在增加，直到負(fù)載達(dá)到飽和狀態(tài)時(shí)，計(jì)算資源完全利用。與存儲(chǔ)資源同樣的效果，隨著用戶數(shù)目的增加，采取CARA調(diào)度策略得到的計(jì)算資源利用率越來越高于采取就近調(diào)度策略，而且在系統(tǒng)負(fù)載不均衡時(shí)，優(yōu)勢(shì)更為明顯。

5 結(jié)束語

算力感知網(wǎng)絡(luò)通過感知算網(wǎng)資源信息以及業(yè)務(wù)需求信息，將業(yè)務(wù)對(duì)于算力的需求與泛在分布式的算力資源進(jìn)行映射，并通過無所不至的網(wǎng)絡(luò)進(jìn)行連接，動(dòng)態(tài)、彈性地調(diào)度算力資源為用戶提供服務(wù)，提高算網(wǎng)資源的利用率，達(dá)到計(jì)算密集型以及時(shí)延敏感型的業(yè)務(wù)對(duì)于未來邊緣網(wǎng)絡(luò)的需求。本文提出一種算力感知網(wǎng)絡(luò)中算力感知路由分配系統(tǒng)，定義一個(gè)由通信時(shí)延組成的目標(biāo)函數(shù)，并建模一個(gè)計(jì)算任務(wù)調(diào)度問題。為解決這一問題，提出了一種基于Floyd的算力感知路由分配(CARA)策略，聯(lián)合優(yōu)化了路由策略與算力資源分配。數(shù)值仿真結(jié)果表明，CARA策略能夠在滿意的用戶數(shù)目和系統(tǒng)用戶業(yè)務(wù)處理時(shí)延方面提供比就近調(diào)度策略更優(yōu)的性能，并且能夠提高網(wǎng)絡(luò)的存儲(chǔ)資源和計(jì)算資源利用率。