孫鈺坤,張 興,雷 波
(1.北京郵電大學 泛網無線通信教育部重點實驗室,北京 100876;2.中國電信股份有限公司研究院,北京 102209)
隨著人工智能與移動互聯(lián)網技術的不斷發(fā)展,增強現(xiàn)實、人臉識別、圖像渲染、自動駕駛等新型業(yè)務應用大量涌現(xiàn),這些新型業(yè)務應用通常需要消耗巨大的計算資源、存儲資源以及能耗,目前智能終端設備的計算能力尚且比較有限,電池容量也比較低,無法滿足這些新興業(yè)務應用的處理需求。因此,云計算得以提出并持續(xù)升溫。
云計算利用虛擬化技術建立超大容量的算力資源池,使得各種應用可以獲得所需的計算資源、存儲資源以及軟件和平臺服務。云計算的出現(xiàn)滿足了計算密集型的業(yè)務處理需求,但是,自動駕駛這一類智能應用同時具有時延敏感的特性,終端到云端的傳輸時延在很多情況下無法滿足這一類應用對于超低時延的需求。因此,ETSI于2014年12月成立移動邊緣計算(Mobile Edge Computing,MEC)行業(yè)規(guī)范組(Industry Specification Group,ISG),啟動移動邊緣計算標準化,以發(fā)展移動邊緣計算[1]。ETSI將MEC定義為一種可以在無線接入網絡中移動用戶附近位置提供IT和云計算功能的網絡架構,旨在將IT和云計算從核心網絡遷移到邊緣接入網絡,以縮短任務處理端到端的時延,并確保數(shù)據的安全性與隱私性。2016年9月移動邊緣計算的概念被擴展為多接入邊緣計算(Multi-access Edge Computing,MEC),將移動邊緣計算從電信蜂窩網絡進一步延伸至其他無線網絡,以擴大邊緣計算在包括WiFi和固定訪問技術在內的異構網絡中的適用性。
邊緣計算設備和智能終端設備的大量部署,雖然解決了網絡中海量數(shù)據上傳至云計算中心導致的帶寬緊缺、網絡擁塞、時延過長的問題,但也使得算力資源呈現(xiàn)泛在部署的趨勢,不可避免地出現(xiàn)了“算力孤島”效應。一方面,邊緣計算節(jié)點沒有進行有效的協(xié)同處理任務,單一節(jié)點的算力資源無法滿足如圖像渲染等超大型的計算密集型任務的算力資源需求,仍然無法解決同時具有計算密集和時延敏感特性的新型業(yè)務的超低時延需求問題;另一方面,雖然一些邊緣計算節(jié)點出現(xiàn)超負載無法有效處理計算任務的情況,但是由于網絡負載的不均衡,勢必會有一些計算節(jié)點仍然處于空閑的狀態(tài),導致邊緣網絡的算力資源無法得到充分的利用。
因此,為了高效、協(xié)同地利用全網異構的算力資源,2019年由運營商、設備商等主導提出一種基于分布式系統(tǒng)的計算與網絡融合的技術方案——算力感知網絡[2-5](Computing-aware Networking,CAN),以實現(xiàn)ICT系統(tǒng)的聯(lián)合優(yōu)化調度,提供端到端的體驗保證。CAN旨在將云邊端多樣的算力通過網絡的方式連接與協(xié)同,實現(xiàn)計算與網絡的深度融合及協(xié)同感知,以及算力資源的按需調度和高效共享[6-10]。
算力感知路由和算力資源分配是算力感知網絡研究中的一個關鍵問題,在傳統(tǒng)的網絡架構中,算力與網絡通常是單獨進行管理。在算力管理方面,計算卸載技術作為邊緣計算的一項關鍵技術,在邊緣計算概念被提出之后,便有許多研究者提出基于單用戶多節(jié)點[11]、多用戶單節(jié)點[12]以及多用戶多節(jié)點[13-14]的任務卸載策略,這些策略實質上都是將終端任務與邊緣計算節(jié)點進行完美匹配。在網絡管理方面,研究主要集中在如何優(yōu)化任務路由策略[15]。
針對目前研究存在的問題,本文在多任務、多路由節(jié)點、多邊緣服務器的邊緣算力網絡場景下,分別基于用戶業(yè)務側、網絡側、邊緣計算資源池側,構建算力需求、網絡狀態(tài)、算力資源的感知信息模型;基于感知信息模型,在計算資源和存儲資源的約束限制下,以用戶業(yè)務的調度傳輸時延最小化為優(yōu)化目標,聯(lián)合優(yōu)化路由控制、計算節(jié)點的選擇和存儲、算力資源的分配;最后,本文提出了基于Floyd的算力感知路由分配策略,有效地將算力與網絡進行協(xié)同管理,緩解網絡負載不均衡的問題,并通過仿真分析了所提策略在改善用戶業(yè)務體驗以及算網資源利用率方面的性能。
如圖1所示,算力感知網絡系統(tǒng)由終端設備、基站以及邊緣網關(路由節(jié)點)、邊緣服務器(邊緣計算節(jié)點)和云中心組成。其中用戶業(yè)務由終端設備發(fā)起請求,通過無線鏈路傳輸至基站;邊緣網關主要負責路由控制和數(shù)據轉發(fā),在實際網絡系統(tǒng)中,邊緣網關可以部署在基站側,路由節(jié)點之間可以通過實時動態(tài)的鏈路進行數(shù)據傳輸;邊緣服務器是以硬件基礎設施為虛擬化資源的邊緣應用平臺,主要負責提供存儲和計算資源,進行用戶業(yè)務的處理,邊緣計算節(jié)點與路由節(jié)點之間通過固定鏈路進行數(shù)據傳輸;云中心具有充足的存儲資源和計算資源,是部署在距離用戶較遠位置的大型服務器集群,邊緣計算節(jié)點與云中心節(jié)點之間具有固定的鏈路進行數(shù)據傳輸,雖然在本文的系統(tǒng)模型中,假設用戶業(yè)務只在由邊緣計算節(jié)點組成的邊緣算力感知網絡中進行處理,但是云中心是算力感知網絡架構中不可或缺的一部分,因此在圖1中予以表示。
圖1 算力感知網絡系統(tǒng)Fig.1 System of computing-aware networks
假設算力感知網絡系統(tǒng)中共有M個終端設備,終端設備的集合表示為Μ={1,2,...,M},m∈Μ表示一個終端設備,假設每個終端設備每次最多發(fā)起一個計算任務處理請求。
假設算力感知網絡系統(tǒng)中共存在K個用戶業(yè)務,用戶業(yè)務的集合表示為Κ={1,2,...,K},k∈Κ表示一個用戶業(yè)務。第k個用戶業(yè)務可以表示為Sk(Ak,Xk,Ck,Dkmax,Dka,Bk),其中Ak表示用戶業(yè)務k所接入的路由節(jié)點,Xk表示用戶業(yè)務k所需要的存儲資源的量化值,Ck表示用戶業(yè)務k所需要的計算資源的量化值(中央處理器的轉數(shù)/比特數(shù)據/秒,即單位時間處理單位比特數(shù)據所需要的中央處理器的轉數(shù)),Dkmax表示用戶業(yè)務k允許的最大業(yè)務處理時延,Dka表示用戶業(yè)務k接入路由節(jié)點的時延,Bk表示用戶業(yè)務k的大小。
終端設備發(fā)出請求的用戶業(yè)務通過無線鏈路傳輸?shù)剿懔Ω兄W絡中的邊緣無線接入點,根據香農定理,用戶業(yè)務k到所接入的路由節(jié)點Ak的數(shù)據傳輸速率可以表示為:
Rk,Ak=Bk,Aklb(1+γk,Ak),
(1)
其中,Bk,Ak表示用戶業(yè)務k到所接入的路由節(jié)點Ak信道的帶寬,γk,Ak表示用戶業(yè)務k到所接入的路由節(jié)點Ak傳輸?shù)男旁氡?Signal Noise Ratio,SNR),表示為:
(2)
式中,pk,Ak表示用戶業(yè)務k到所接入的路由節(jié)點Ak的發(fā)射功率,N0表示加性高斯白噪聲的譜密度,hk,Ak表示用戶業(yè)務k到所接入的路由節(jié)點Ak的路徑損耗,hk,Ak的大小與用戶業(yè)務k到所接入的路由節(jié)點Ak之間的距離有關,距離越遠,路徑損耗越大。本文主要研究終端設備發(fā)出的業(yè)務請求在算力感知網絡中如何基于感知的信息路由調度到最佳的算力節(jié)點上進行業(yè)務處理,因此沒有考慮用戶業(yè)務的位置分布,而是將用戶業(yè)務到所接入的路由節(jié)點的數(shù)據傳輸速率進行統(tǒng)一的量化表示。
綜上所述,用戶業(yè)務k到所接入的路由節(jié)點Ak的接入時延為:
(3)
終端設備發(fā)出請求的用戶業(yè)務在算力感知網絡中,通過動態(tài)的通信鏈路在相鄰的路由節(jié)點之間進行數(shù)據傳輸,假設在算力感知網絡中路由節(jié)點之間動態(tài)鏈路的數(shù)據傳輸速率可以感知,則表示為:
式中,wi,j表示路由節(jié)點i與路由節(jié)點j之間的數(shù)據傳輸速率,滿足
(4)
因此,用戶業(yè)務k在路由節(jié)點i和路由節(jié)點j之間的傳輸時延為:
(5)
算力感知網絡中的計算節(jié)點與路由節(jié)點之間通過固定鏈路進行數(shù)據傳輸,路由節(jié)點i到計算節(jié)點n之間的數(shù)據傳輸速率可以表示為:
(6)
因此,如果用戶業(yè)務k選擇計算節(jié)點n,則通過路由節(jié)點傳輸?shù)接嬎愎?jié)點n的到達時延為:
(7)
在算力感知網絡系統(tǒng)中,網絡控制面需要實時感知計算節(jié)點的存儲資源以及算力資源狀態(tài)。假設網絡中存在N個計算節(jié)點,計算節(jié)點的集合表示為Ν={1,2,...,N},n∈Ν表示一個計算節(jié)點,則第n個計算節(jié)點可表示為Zn(An,Xn,Cn,Rn),其中An表示該計算節(jié)點連接的路由節(jié)點標簽,Xn表示該計算節(jié)點的存儲資源大小,Cn表示該計算節(jié)點的計算資源大小(中央處理器的轉數(shù)/比特數(shù)據/秒,即單位時間處理單位比特數(shù)據所需要的中央處理器轉數(shù)),Rn表示該計算節(jié)點到路由節(jié)點的數(shù)據傳輸速率。
綜上所述,當計算節(jié)點的存儲資源、計算資源滿足用戶業(yè)務需求時,用戶業(yè)務的計算時延為:
(8)
在上述算力感知網絡系統(tǒng)架構模型、任務模型、通信模型、計算和存儲資源模型的基礎上,一個任務處理的總時延包括任務接入時延、任務傳輸時延、任務到達計算節(jié)點時延、任務處理時延和任務等待時延,由于任務處理時延和任務等待時延在確定的算力需求條件下具有統(tǒng)一性,因此可以在優(yōu)化模型中不予考慮,所以用戶業(yè)務k到調度的計算節(jié)點的傳輸時延為:
tk,t=Dka+Dt+Dk,n,a。
(9)
考慮聯(lián)合優(yōu)化計算任務路由策略和算力資源的分配,本文將最終的計算任務調度優(yōu)化問題建模為:
(10)
目標函數(shù)的約束條件如下:
(11)
(12)
式中,Κn表示調度到計算節(jié)點n的所有用戶業(yè)務的集合,約束條件(11)表示調度到計算節(jié)點的所有用戶業(yè)務可利用的存儲資源不超過該計算節(jié)點可以提供的存儲資源,約束條件(12)表示調度到計算節(jié)點的所有用戶業(yè)務可利用的計算資源不超過該計算節(jié)點可以提供的計算資源。
由于當算力感知網絡處于部分計算節(jié)點過載,或者全網計算節(jié)點過載的情況時,根據最小化用戶業(yè)務傳輸時延的目標得到的調度策略,部分用戶業(yè)務勢必會因為算力資源短缺而無法按需完成任務處理,考慮實際工程問題的可行性以及算法的復雜度,需要重點關注的不是如何精確地求出最優(yōu)解,而是在如何保證用戶公平性的前提下,高效快速地獲得一個聯(lián)合優(yōu)化路徑選擇與計算節(jié)點選擇的次優(yōu)解,本文提出一種基于Floyd的算力感知路由分配(CARA)算法來解決該問題,為計算任務均衡選擇優(yōu)化的路徑以及計算節(jié)點。
Floyd算法是一種利用動態(tài)規(guī)劃的思想尋找給定的加權圖中多源點之間最短路徑的算法。在算力感知網絡架構中,路由控制器可以感知用戶業(yè)務的數(shù)據大小和網絡的鏈路狀態(tài)(包括鏈路的數(shù)據傳輸速率、抖動以及丟包率等)。因此,可以根據網絡感知的信息計算出用戶業(yè)務經過網絡中任意一條鏈路的傳輸時延,所有的終端設備、路由節(jié)點、計算節(jié)點和動態(tài)的鏈路時延構成一個實時變化的多源點加權圖。
算力感知網絡中計算任務調度策略的優(yōu)化目標之一便是最短傳輸時延的路徑選擇,基于Floyd算法可以計算出將用戶業(yè)務路由至各個節(jié)點的最短時延以及其對應的具體調度路徑,進而選擇時延最短的計算節(jié)點作為最佳計算節(jié)點及根據Floyd算法確定的路徑作為最優(yōu)路由策略,如算法1所示。
算法1 基于Floyd算法的算力感知路由分配策略輸入:算力感知網絡中計算節(jié)點狀態(tài)Z,計算節(jié)點數(shù)目N,算力感知網絡中鏈路狀態(tài)W,用戶業(yè)務的算力需求S,用戶業(yè)務數(shù)目K輸出:任務調度路徑P,任務處理節(jié)點X1:基于Floyd算法計算將用戶業(yè)務路由至各個計算節(jié)點的最短時延Dmin,獲取最優(yōu)調度路徑P'2:根據Dmin選擇時延最短的計算節(jié)點以及對應路徑作為調度策略,計算最短時延D*min,獲取最優(yōu)調度路徑P*和最佳計算節(jié)點N*3:for k=1:Kdo4: for n=1:Ndo5: ifN*(k)==n6: ifSk,2≤Nn,2且Sk,3≤Nn,37: 最佳計算節(jié)點N*不變8: 最優(yōu)調度路徑P*不變9:更新節(jié)點存儲資源狀態(tài) Nn,2:=Nn,2-Sk,210:更新節(jié)點計算資源狀態(tài) Nn,3:=Nn,3-Sk,311: else12: 重復步驟6的判斷,依次循環(huán)遍歷N個節(jié)點直到資源滿足或者回到初始節(jié)點停止13: 更新最佳計算節(jié)點N*(回到初始不更新)14:更新最優(yōu)調度路徑P*(回到初始不更新)15:更新節(jié)點存儲資源狀態(tài) N*,2:=N*,2-S*,216:更新節(jié)點計算資源狀態(tài) N*,3:=N*,3-S*,317: end if18: end if19: end for20: end for 21: return 最佳計算節(jié)點N*,最優(yōu)調度路徑P*
然而,算力感知網絡作為一種面向B5G/6G通信的新型網絡架構,與傳統(tǒng)的無線網絡面臨同樣的問題,即網絡負載不均衡,網絡中部分計算節(jié)點的計算任務超過所能容納的最大任務數(shù)目,導致計算任務的處理時延過長,無法滿足時延敏感型的新型網絡業(yè)務需求。與此同時,網絡中另一部分節(jié)點可能沒有計算任務達到,處于資源空閑狀態(tài),沒有充分利用全網的算力資源,導致算力資源利用率低下。因此,僅僅基于Floyd算法選擇最短時延的路由策略,進而確定計算節(jié)點的方案在網絡負載不均衡的情況下,無法聯(lián)合優(yōu)化計算任務路由策略和算力資源的分配。
如算法1中第3~20步所示,根據Floyd算法已經確定的路由分配策略,如果一個計算任務被分配的計算節(jié)點已經過載,則將計算任務循環(huán)調度到下一個有剩余算力資源的計算節(jié)點。為保證用戶的公平性,計算任務按照標簽順序優(yōu)先獲取網絡的算力資源;為降低算法的計算復雜度,計算任務在重新選擇計算節(jié)點時,默認循環(huán)至下一個有剩余算力資源的計算節(jié)點即可,無需再次基于Floyd算法優(yōu)化調度策略。
假設邊緣算力網絡系統(tǒng)中路由節(jié)點的個數(shù)為R,則本文基于Floyd算法的CARA策略的算法時間復雜度為O(R3KN2),若使用暴力搜索算法來遍歷求解用戶業(yè)務的計算節(jié)點選擇、路由控制以及存儲、算力資源分配,其時間復雜度為O(NKRR),相比于具有指數(shù)級時間復雜度的暴力搜索算法,隨著路由節(jié)點和用戶業(yè)務數(shù)目的增加,本文方法時間復雜度顯著下降。
本節(jié)對基于Floyd 算法的算力感知路由分配(CARA)策略進行仿真實驗。首先對仿真場景和參數(shù)進行說明,然后展示仿真結果并對其進行分析。
在仿真實驗中,考慮多終端設備、多路由節(jié)點、多邊緣計算節(jié)點的場景,如圖2所示。在模擬的算力感知網絡系統(tǒng)中,包含3個邊緣計算節(jié)點、6個邊緣路由節(jié)點,以及若干發(fā)出業(yè)務請求的終端設備,其數(shù)量可以進行具體的設定,所接入的路由節(jié)點隨機生成。路由節(jié)點之間的鏈路動態(tài)連接,相連兩個路由節(jié)點之間的數(shù)據傳輸速率動態(tài)變化,如圖2的權值所示,計算節(jié)點與路由節(jié)點之間的鏈路連接固定,各個節(jié)點之間的鏈路連接情況以及數(shù)據數(shù)傳速率如圖2所示。
圖2 仿真場景Fig.2 Simulation topology
如表1所示,設置默認情況下的算力感知網絡系統(tǒng)參數(shù)。
表1 仿真參數(shù)設置
假設K個用戶業(yè)務均為同時發(fā)起,算力感知網絡的初始狀態(tài)為無任何任務執(zhí)行。
以圖2所示的網絡場景作為測試系統(tǒng),與本文提出的CARA策略進行對比的就近調度算法描述如下:用戶業(yè)務始終選擇部署位置最近的計算節(jié)點,即接入R1、R2的用戶業(yè)務選擇N1計算節(jié)點,接入R3、R5的用戶業(yè)務選擇N3計算節(jié)點,接入R4、R6的用戶業(yè)務選擇N2計算節(jié)點。
4.2.1 滿意用戶數(shù)
若任務獲得所需要的算力資源,而且任務處理完成總時延不超過允許的最大時延,則認為業(yè)務處理成功,即:
(13)
(14)
I(k)=I(k1)I(k2)。
(15)
因此,滿意用戶數(shù)為:
(16)
4.2.2 業(yè)務平均處理時延
為了統(tǒng)計所有K個用戶業(yè)務的平均任務完成時延,本文將網絡超負載之后沒有得到所需算力資源的用戶業(yè)務處理時間附加等待時延:
(17)
式中,Κout為過載之后沒有獲取所需的算力資源的用戶業(yè)務集合。
綜上所述,系統(tǒng)中用戶業(yè)務的平均處理時延為:
(18)
4.2.3 算力資源利用率
算力感知網絡中計算節(jié)點的存儲資源利用率為網絡中使用的存儲資源與網絡中節(jié)點存儲資源總和的比值[16],表示為:
(19)
算力感知網絡中計算節(jié)點的計算資源利用率為網絡中使用的計算資源與網絡中節(jié)點的計算資源總和的比值[16],表示為:
(20)
4.3.1 滿意用戶數(shù)
系統(tǒng)負載均衡時滿意的用戶數(shù)與系統(tǒng)用戶總數(shù)的關系如圖3所示,系統(tǒng)負載不均衡時滿意的用戶數(shù)與系統(tǒng)用戶總數(shù)的關系如圖4所示。
圖3 滿意用戶數(shù)與用戶數(shù)目關系(負載均衡)Fig.3 Number of satisfied users vs users( load balance)
圖4 滿意用戶數(shù)與用戶數(shù)目關系(負載不均衡)Fig.4 Number of satisfied users vs users (load un balance)
由圖3和圖4可以看出,采取CARA策略滿意的用戶數(shù)一直大于或等于就近調度策略,而且隨著用戶數(shù)目的增加或者負載不均衡時,效果更為明顯。當負載不均衡時,采取就近調度策略滿意用戶數(shù)目不隨著用戶總數(shù)的增加而增加,很快陷入系統(tǒng)部分飽和狀態(tài),而采取CARA策略直到系統(tǒng)資源全部耗盡才陷入超負載狀態(tài)。
4.3.2 業(yè)務平均處理時延
算力感知網絡中用戶業(yè)務平均處理時延與系統(tǒng)中用戶總數(shù)的關系如圖5所示。隨著系統(tǒng)用戶數(shù)目的增加,CARA調度策略和就近調度策略產生的平均時延幾乎都在增加。在網絡負載均衡和負載不均衡兩種情況下,采取CARA調度策略產生的用戶業(yè)務平均處理時延均小于就近調度策略,而且隨著系統(tǒng)用戶數(shù)目的增加,采取CARA策略縮短的時延效果更為顯著。在系統(tǒng)負載不均衡時,采取CARA調度策略縮短的時延也更為明顯,而且隨著系統(tǒng)用戶數(shù)目增加到一定數(shù)量之后,在負載不均衡的情況下采取CARA調度策略的時延,也小于在負載均衡情況下采取就近調度策略的時延。
圖5 時延與用戶數(shù)目關系Fig.5 Average delay vs the number of users
4.3.3 存儲資源利用率
存儲資源利用率與系統(tǒng)中用戶總數(shù)的關系如圖6所示。
圖6 存儲資源利用率Fig.6 Storage resource utilization ratio
由圖6可以看出,在系統(tǒng)負載均衡與系統(tǒng)負載不均衡兩種情況下,采取CARA調度策略時系統(tǒng)的存儲資源利用率隨著用戶數(shù)目增加一直在提高,即使在超負載的情況下,存儲資源也沒有被完全利用,分析原因為此時系統(tǒng)的計算資源已經完全耗盡,存儲資源與計算資源是協(xié)同處理計算任務的,當存儲資源與計算資源沒有完全適配計算任務時,會有一種資源無法得到充分利用。采取CARA調度策略得到的存儲資源利用率隨著用戶數(shù)目的增加越來越高于采取就近調度策略得到的存儲資源利用率,而且在系統(tǒng)負載不均衡時,優(yōu)勢更為明顯。
4.3.4 計算資源利用率
計算資源利用率與系統(tǒng)中用戶總數(shù)的關系如圖7所示。
圖7 計算資源利用率Fig.7 Computing resource utilization ratio
由圖7可以看出,在系統(tǒng)負載均衡和系統(tǒng)負載不均衡兩種情況下,采取CARA調度策略時系統(tǒng)的計算資源利用率隨著用戶數(shù)目的增加一直在增加,直到負載達到飽和狀態(tài)時,計算資源完全利用。與存儲資源同樣的效果,隨著用戶數(shù)目的增加,采取CARA調度策略得到的計算資源利用率越來越高于采取就近調度策略,而且在系統(tǒng)負載不均衡時,優(yōu)勢更為明顯。
算力感知網絡通過感知算網資源信息以及業(yè)務需求信息,將業(yè)務對于算力的需求與泛在分布式的算力資源進行映射,并通過無所不至的網絡進行連接,動態(tài)、彈性地調度算力資源為用戶提供服務,提高算網資源的利用率,達到計算密集型以及時延敏感型的業(yè)務對于未來邊緣網絡的需求。本文提出一種算力感知網絡中算力感知路由分配系統(tǒng),定義一個由通信時延組成的目標函數(shù),并建模一個計算任務調度問題。為解決這一問題,提出了一種基于Floyd的算力感知路由分配(CARA)策略,聯(lián)合優(yōu)化了路由策略與算力資源分配。數(shù)值仿真結果表明,CARA策略能夠在滿意的用戶數(shù)目和系統(tǒng)用戶業(yè)務處理時延方面提供比就近調度策略更優(yōu)的性能,并且能夠提高網絡的存儲資源和計算資源利用率。