霧/邊緣計(jì)算的底層算法分析

董春利，王 莉

（1.南京交通職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院，江蘇 南京 211188；2.上海劍曦信息科技有限公司，上海 200051）

0 引 言

有幾種底層算法用于促進(jìn)霧/邊緣計(jì)算，本文將其歸納為4種算法進(jìn)行討論[1]：

（1）發(fā)現(xiàn)：識(shí)別網(wǎng)絡(luò)中可用于分布式計(jì)算的邊緣資源；

（2）基準(zhǔn)測(cè)試：捕獲用于決策的資源性能，以最大化部署性能；

（3）負(fù)載均衡：根據(jù)不同的標(biāo)準(zhǔn)，如優(yōu)先級(jí)、公平性等，在資源之間分配工作負(fù)載；

（4）放置：為部署工作負(fù)載，確定合適的資源。

1 發(fā) 現(xiàn)

發(fā)現(xiàn)是指識(shí)別邊緣資源，以便可以在云或用戶(hù)設(shè)備/傳感器上部署工作負(fù)載[2]。通常邊緣計(jì)算研究假定邊緣資源是已被發(fā)現(xiàn)的，但這不是一件容易的事。這里使用3種技術(shù)，分別為編程基礎(chǔ)設(shè)施、握手協(xié)議和消息傳遞技術(shù)。

第一種技術(shù)使用如霧滴（Foglets）之類(lèi)的編程基礎(chǔ)設(shè)施，于是邊緣資源加入云邊緣生態(tài)系統(tǒng)的機(jī)制被提出。具體地，提出了一種發(fā)現(xiàn)協(xié)議，將一個(gè)應(yīng)用的資源需求與邊緣上的可用資源相匹配。盡管如此，該協(xié)議假定邊緣資源是眾所周知的或可供使用的，實(shí)現(xiàn)了一個(gè)附加的加入?yún)f(xié)議，允許從與用戶(hù)具有相同地理距離的一組資源中選擇一個(gè)邊緣節(jié)點(diǎn)。

第二種技術(shù)使用握手協(xié)議。邊緣即服務(wù)（EaaS）平臺(tái)為一組同質(zhì)邊緣資源提供輕量級(jí)發(fā)現(xiàn)協(xié)議。該平臺(tái)需要主節(jié)點(diǎn)，可以是計(jì)算可用網(wǎng)絡(luò)設(shè)備或者是執(zhí)行管理器進(jìn)程，并與邊緣節(jié)點(diǎn)通信的專(zhuān)用節(jié)點(diǎn)。管理器與潛在的邊緣節(jié)點(diǎn)通信，并在邊緣節(jié)點(diǎn)上執(zhí)行進(jìn)程以運(yùn)行命令。一旦被發(fā)現(xiàn)，LXD容器可以部署在邊緣節(jié)點(diǎn)上。

第三種技術(shù)使用消息傳遞。在傳感器網(wǎng)絡(luò)環(huán)境中，終端設(shè)備可能不一定能夠訪問(wèn)互聯(lián)網(wǎng)。研究表明，可以使用由連接到互聯(lián)網(wǎng)的節(jié)點(diǎn)（稱(chēng)為處理節(jié)點(diǎn)）提供的服務(wù)，從而在這樣的網(wǎng)絡(luò)中傳遞消息。具體地，提出了一種用于識(shí)別處理節(jié)點(diǎn)的發(fā)現(xiàn)方法，假設(shè)用戶(hù)可以與網(wǎng)絡(luò)中的任何節(jié)點(diǎn)通信，提交查詢(xún)，并依賴(lài)于基于仿真的驗(yàn)證。

2 基準(zhǔn)測(cè)試

基準(zhǔn)測(cè)試是一種事實(shí)上的方法，用于捕獲計(jì)算系統(tǒng)的性能（如存儲(chǔ)器、CPU、網(wǎng)絡(luò)等實(shí)體）。需要使用標(biāo)準(zhǔn)性能評(píng)估工具，捕獲與每個(gè)實(shí)體性能相關(guān)的度量標(biāo)準(zhǔn)[3]。

邊緣基準(zhǔn)測(cè)試可分為評(píng)估功能屬性的基準(zhǔn)測(cè)試、基于應(yīng)用的基準(zhǔn)測(cè)試以及集成基準(zhǔn)測(cè)試。大多數(shù)邊緣基準(zhǔn)測(cè)試研究是評(píng)估邊緣處理器的功耗、CPU和內(nèi)存性能。

由于多種原因，在邊緣環(huán)境中基準(zhǔn)測(cè)試變得更具挑戰(zhàn)性。首先，因?yàn)樯形刺峁┎东@各種工作負(fù)載的邊緣特定應(yīng)用的基準(zhǔn)測(cè)試。現(xiàn)有的基準(zhǔn)測(cè)試通常是不太適合邊緣的科學(xué)應(yīng)用。相反已經(jīng)使用了語(yǔ)音驅(qū)動(dòng)的基準(zhǔn)測(cè)試和物聯(lián)網(wǎng)（IoT）應(yīng)用。其次，在資源受限的邊緣節(jié)點(diǎn)上，運(yùn)行額外的耗時(shí)應(yīng)用具有挑戰(zhàn)性，需要用于邊緣的輕量級(jí)基準(zhǔn)測(cè)試工具。最后，僅僅對(duì)邊緣資源進(jìn)行基準(zhǔn)測(cè)試并不充分，還需要一種用于對(duì)云和邊緣資源進(jìn)行基準(zhǔn)測(cè)試的集成方法。

3 負(fù)載均衡

當(dāng)邊緣數(shù)據(jù)中心部署在網(wǎng)絡(luò)邊緣時(shí)，使用高效負(fù)載均衡算法分配任務(wù)的問(wèn)題，已經(jīng)引起了人們的極大關(guān)注。邊緣現(xiàn)有的負(fù)載均衡算法采用4種技術(shù)，即粒子群優(yōu)化、協(xié)作負(fù)載均衡、基于圖的平衡以及廣度優(yōu)先搜索[4]。

He等人提出了用于車(chē)輛互聯(lián)網(wǎng)（IoV）的軟件定義云/霧網(wǎng)絡(luò)（SDCFN）架構(gòu)。SDCFN允許集中式控制車(chē)輛之間的網(wǎng)絡(luò)，并幫助中間件獲得負(fù)載均衡所需的信息。該研究采用粒子群優(yōu)化-約束優(yōu)化進(jìn)行負(fù)載均衡，以減少延遲，并有效地實(shí)現(xiàn)車(chē)輛所需的服務(wù)質(zhì)量（QoS）。

CooLoad提出了霧/邊緣數(shù)據(jù)中心之間的協(xié)作負(fù)載均衡模型，以減少服務(wù)暫停時(shí)間。CooLoad為每個(gè)數(shù)據(jù)中心分配一個(gè)緩沖區(qū)，以接收來(lái)自客戶(hù)端的請(qǐng)求。當(dāng)緩沖區(qū)中的項(xiàng)目數(shù)超過(guò)某個(gè)閾值時(shí)，對(duì)數(shù)據(jù)中心的傳入請(qǐng)求，將負(fù)載均衡到相鄰的數(shù)據(jù)中心。這項(xiàng)工作假設(shè)數(shù)據(jù)中心通過(guò)高速傳輸連接，以實(shí)現(xiàn)有效的負(fù)載均衡。

Song等人指出，在單個(gè)集群中運(yùn)行的云平臺(tái)的現(xiàn)有負(fù)載均衡算法，不能直接應(yīng)用于動(dòng)態(tài)和點(diǎn)對(duì)點(diǎn)的霧計(jì)算架構(gòu)。為了實(shí)現(xiàn)有效的負(fù)載均衡，可將霧結(jié)構(gòu)抽象為圖模型，其中每個(gè)頂點(diǎn)表示節(jié)點(diǎn)，圖邊表示任務(wù)之間的數(shù)據(jù)依賴(lài)性。于是，提出了一種動(dòng)態(tài)圖重新分區(qū)算法，使用先前的負(fù)載均衡結(jié)果作為輸入，最小化負(fù)載均衡結(jié)果差異，同時(shí)提出了原始狀態(tài)。

Puthal等人專(zhuān)注于開(kāi)發(fā)一種有效的動(dòng)態(tài)負(fù)載均衡算法，一種為邊緣數(shù)據(jù)中心的認(rèn)證方法。通過(guò)應(yīng)用廣度優(yōu)先搜索（BFS）方法，將任務(wù)分配給未充分利用的邊緣數(shù)據(jù)中心。每個(gè)數(shù)據(jù)中心都使用當(dāng)前負(fù)載和用于計(jì)算當(dāng)前負(fù)載的最大容量建模。驗(yàn)證方法允許負(fù)載均衡算法找到一個(gè)經(jīng)過(guò)驗(yàn)證的數(shù)據(jù)中心。

4 放 置

霧/邊緣計(jì)算中的一個(gè)具有挑戰(zhàn)性的問(wèn)題，是將輸入的計(jì)算任務(wù)放在合適的霧/邊緣資源上。放置算法解決了這個(gè)問(wèn)題，需要考慮霧/邊緣層資源的可用性和環(huán)境變化[5]。現(xiàn)有技術(shù)可被分類(lèi)為動(dòng)態(tài)條件感知技術(shù)和迭代技術(shù)。迭代技術(shù)可以進(jìn)一步分為2個(gè)空間，即迭代資源空間和迭代問(wèn)題空間。

王等人指出，現(xiàn)有的工作解決了靜態(tài)網(wǎng)絡(luò)條件和預(yù)定資源需求下的霧/邊緣計(jì)算中的放置問(wèn)題，不是動(dòng)態(tài)條件感知（不考慮用戶(hù)的移動(dòng)性和資源可用性的變化）。通過(guò)考慮一組額外的參數(shù)來(lái)解決這個(gè)缺點(diǎn)，包括用戶(hù)的位置、偏好、數(shù)據(jù)庫(kù)位置以及系統(tǒng)上的負(fù)載。

霧計(jì)算層次結(jié)構(gòu)中，資源的迭代方法是另一種有效的技術(shù)。Taneja等人提出了一種用于分層霧計(jì)算的放置算法，利用了傳統(tǒng)的云計(jì)算和最近的霧計(jì)算。該算法從霧向云迭代，以便先將計(jì)算模塊放置在可用的霧節(jié)點(diǎn)上。

與上述迭代方法相反，可以在識(shí)別問(wèn)題空間上執(zhí)行多次迭代。Skarlat等人提出了一種稱(chēng)為霧服務(wù)放置問(wèn)題（FSPP）的方法，以便在物聯(lián)網(wǎng)服務(wù)中更優(yōu)地共享霧節(jié)點(diǎn)中的資源。

5 結(jié) 論

本次調(diào)查中注意到，霧/邊緣計(jì)算資源管理中，發(fā)現(xiàn)、基準(zhǔn)測(cè)試、負(fù)載均衡和放置方面的算法還比較有限，需要進(jìn)一步開(kāi)發(fā)用于對(duì)云和邊緣資源進(jìn)行基準(zhǔn)測(cè)試的集成方法，同時(shí)需充分考慮用戶(hù)的移動(dòng)性和資源可用性的變化。