★中國地質(zhì)大學(xué)（武漢）計算機學(xué)院楊在航，李躍鵬，曾德澤

摘要：邊端融合計算架構由于其算力節點(diǎn)分布廣、實(shí)時(shí)處理能力強的特點(diǎn)，近年來(lái)在各種領(lǐng)域被廣泛使用，但是它在計算、通信與數據安全方面仍然面臨諸多挑戰。編碼計算因其通信負載低、計算開(kāi)銷(xiāo)小、隱私保障高的特性恰好契合邊端融合場(chǎng)景的需求而得到了學(xué)術(shù)界的廣泛關(guān)注。因此，本文探索了將編碼計算應用于邊端融合計算架構中的發(fā)展趨勢與關(guān)鍵技術(shù)，并在此基礎上，提出了一種基于編碼計算的邊端融合任務(wù)卸載策略。

1簡(jiǎn)介

隨著(zhù)萬(wàn)物互聯(lián)時(shí)代的到來(lái)，大量智能設備以及諸多新型應用得到了大規模普及，例如智慧城市、虛擬現實(shí)、智能交通等應用如雨后春筍般涌現，為智能社會(huì )的發(fā)展注入了新的活力。智能應用高速發(fā)展的背后實(shí)際上離不開(kāi)邊緣計算作為支撐和基礎。邊緣計算將計算與存儲資源下沉到網(wǎng)絡(luò )邊緣處，由于更靠近終端設備，用戶(hù)請求不再需要經(jīng)過(guò)長(cháng)時(shí)間傳輸到核心網(wǎng)進(jìn)行處理，而是直接在數據產(chǎn)生處進(jìn)行計算，從而大幅度降低了傳輸時(shí)延與能量消耗。邊緣側設備與端側設備均可共同參與計算，協(xié)同構成邊端融合計算環(huán)境。然而邊端融合環(huán)境中的設備大多是由低算力硬件組成，這使得單個(gè)設備無(wú)法獨自完成這個(gè)任務(wù)。而且，終端設備大多具有較強的移動(dòng)性，當大量終端設備頻繁地從一個(gè)邊緣服務(wù)器的覆蓋范圍移動(dòng)到另一個(gè)邊緣服務(wù)器的覆蓋范圍內時(shí)，整個(gè)環(huán)境呈現出高度動(dòng)態(tài)性。此外，相比于云數據中心，邊緣側和端側設備因成本較低無(wú)法配備高強度安全保護策略導致其更容易受到惡意節點(diǎn)的攻擊。

與此同時(shí)，近年來(lái)研究人員將編碼理論應用到分布式計算領(lǐng)域，并提出了一種新的計算框架，即編碼計算。編碼計算旨在借助靈活多樣的編碼方式來(lái)降低通信負載、緩解計算延遲并保護數據隱私[1]。編碼計算的出現引起了學(xué)術(shù)界的廣泛討論，被認為是解決上述邊端融合計算所面臨挑戰的一個(gè)有潛力的途徑。例如，Guo[2]等提出了一種面向無(wú)人機群的分布式編碼計算框架，通過(guò)將無(wú)人機群的編碼任務(wù)卸載到邊緣服務(wù)器上，不僅節省了無(wú)人機群的飛行能耗，而且降低了掉隊無(wú)人機節點(diǎn)所引發(fā)的計算延遲；Parkash[3]等提出了編碼計算框架CodedFedL，將結構化編碼冗余注入無(wú)線(xiàn)邊緣網(wǎng)絡(luò )下的聯(lián)邦學(xué)習中，以減少離散并加快訓練過(guò)程；Zhao[4]等提出了一種基于邊緣節點(diǎn)選擇的子任務(wù)分配方法，以減少編碼邊緣計算系統的總計算時(shí)間。

然而應用編碼計算到邊端融合環(huán)境中仍然面臨著(zhù)不小的阻力。首先，編碼計算目前主要應用于分布式云環(huán)境中，邊端融合環(huán)境所呈現的弱算力、高異構、弱連接、廣分布、高動(dòng)態(tài)等特性加大了編碼任務(wù)傳輸和計算的難度。其次，傳輸并處理編碼所產(chǎn)生的大量冗余數據會(huì )給整個(gè)系統帶來(lái)極高的能量開(kāi)銷(xiāo)，邊緣側和端側設備將難以承受這些額外能量開(kāi)銷(xiāo)所帶來(lái)的成本問(wèn)題。

因此，本文介紹了編碼計算和將其融入邊端融合計算的發(fā)展趨勢以及面臨的挑戰，并探討了一種基于編碼計算的邊端融合任務(wù)卸載策略。

2邊端融合計算面臨的挑戰

近年來(lái)，邊緣計算所蘊含的巨大潛力，使其已經(jīng)成為學(xué)術(shù)界和工業(yè)界共同關(guān)注的熱點(diǎn)話(huà)題。然而邊緣計算仍處于發(fā)展早期，與相對成熟的云計算相比，將其與端側設備融合構成邊端融合計算，不論是其自身體系結構局限還是技術(shù)積累，都還存在諸多問(wèn)題亟需解決。

（1）計算延遲

邊端融合環(huán)境下的設備大多是由不可靠的低端硬件構成，單個(gè)設備的性能較差使得任務(wù)逐漸采取分布式計算完成。但相關(guān)研究[10]發(fā)現即使使用同構機器運算相同任務(wù)時(shí)，由于網(wǎng)絡(luò )條件變化、資源競爭等因素，每個(gè)機器所需的計算時(shí)間也不盡相同，其中部分工作節點(diǎn)的任務(wù)完成速度非常慢，達到平均值的5到8倍。因此，一旦邊端融合環(huán)境中存在因工作能力低下導致任務(wù)完成速度較慢的工作節點(diǎn)時(shí)，等待這些工作節點(diǎn)的反饋會(huì )給整個(gè)計算任務(wù)造成不可預測的延遲。

（2）通信瓶頸

數據洗牌是分布式計算系統（包括邊端融合環(huán)境）的核心步驟，其目的是在分布式計算節點(diǎn)之間交換中間值或原始數據[5]。例如，在MapReduce架構中，數據從Mapper被傳輸到Reducer。通過(guò)對Facebook的Hadoop架構進(jìn)行追蹤分析，研究人員發(fā)現平均有33％的作業(yè)執行時(shí)間都花費在數據洗牌上。在TeraSort、WordCount、RankedInvertedIndex和SelfJoin等應用程序中，50％～70％的執行時(shí)間用于數據洗牌。然而，在每一次數據洗牌過(guò)程中，整個(gè)數據集都通過(guò)網(wǎng)絡(luò )進(jìn)行通信，頻繁數據交互帶來(lái)的通信開(kāi)銷(xiāo)造成了分布式計算系統的性能瓶頸。

（3）安全與隱私

缺乏對邊端融合環(huán)境中的數據安全與隱私保護的舉措將會(huì )增加人們的日常風(fēng)險。假設一個(gè)家庭在周?chē)渴鹆宋锫?lián)網(wǎng)，那么人們就可以從感知到的數據中了解到這個(gè)家庭的很多隱私信息，例如，通過(guò)讀取電力或水的使用情況，人們可以很容易地推測房子是否空置[6]。造成這種現象的原因一方面是社會(huì )缺乏對隱私和數據的保護意識。我們以Wi-Fi網(wǎng)絡(luò )安全為例，在4.39億使用無(wú)線(xiàn)連接的家庭中，49%的Wi-Fi網(wǎng)絡(luò )是不安全的，80%的家庭仍然將路由器設置為默認密碼。另一方面是缺乏有效的工具來(lái)保護網(wǎng)絡(luò )邊緣處的數據隱私和安全。相比于云環(huán)境，邊端融合環(huán)境中的資源高度受限，這使得傳統的安全保護方法可能無(wú)法被部署，或者被有效應用。

（4）移動(dòng)性問(wèn)題

隨著(zhù)終端算力的增加，智能手機、平板、智能汽車(chē)等硬件逐漸成為了構成邊端融合的算力主力軍。這類(lèi)設備最大的特性就是具有極強的移動(dòng)性，當終端設備的移動(dòng)范圍跨越多個(gè)邊緣服務(wù)器的覆蓋范圍時(shí)，終端設備狀態(tài)的更新以及設備與應用之間的重新連接將是一大難點(diǎn)[7]。

3編碼計算的出現

目前邊端融合計算面臨著(zhù)多個(gè)方面的挑戰，這嚴重制約了邊端融合計算的進(jìn)一步發(fā)展與應用。幸運的是，編碼計算通過(guò)借助靈活多樣的編碼方式有望解決邊端融合計算中存在的問(wèn)題。為了方便讀者理解編碼計算的基本思想，我們將從計算延遲、通信負載和安全隱私三個(gè)方面來(lái)具體闡述并給出相關(guān)示例。

（1）降低通信負載編碼。圖1展示了一個(gè)由1個(gè)主節點(diǎn)和2個(gè)工作節點(diǎn)組成的分布式計算系統，其中A1、A2存儲在工作節點(diǎn)W1中，A3、A3存儲在工作節點(diǎn)W2中。我們的目標是將任務(wù)A3發(fā)送到工作節點(diǎn)W1，并將任務(wù)A2發(fā)送到工作節點(diǎn)W2。因此，我們可以設計這樣一種編碼，使主節點(diǎn)將編碼信息A2+A3廣播到2個(gè)工作節點(diǎn)，一旦工作節點(diǎn)接收到廣播信息之后就能夠利用本地已存儲的數據進(jìn)行解碼。顯然，與未編碼方案相比，編碼方案可以降低50％的通信負載。

圖1降低通信負載編碼示例

（2）減少計算延遲編碼。圖2展示了一個(gè)由1個(gè)主節點(diǎn)和3個(gè)工作節點(diǎn)組成的分布式計算系統，整個(gè)系統的目標是計算矩陣乘法AX。在進(jìn)行數據傳輸之前，原始任務(wù)矩陣A被平均劃分為兩個(gè)子矩陣A1和A2，然后將兩個(gè)子矩陣進(jìn)行線(xiàn)性編碼生成新的子矩陣（A1+A2），接著(zhù)主節點(diǎn)M將A1、A2和（A1+A2）分別發(fā)送給工作節點(diǎn)W1、W2和W3。每個(gè)工作節點(diǎn)接收到子矩陣任務(wù)之后，將子矩陣與X相乘并將計算結果返回給主節點(diǎn)M。通過(guò)觀(guān)察可知，主節點(diǎn)只需要接收到任意兩個(gè)計算結果就能恢復出最終結果，而無(wú)需等待掉隊節點(diǎn)的反饋。

圖2減少計算延遲編碼示例

（3）面向安全隱私編碼。圖3展示了一種用于保護雙邊隱私的編碼計算示例。具體來(lái)說(shuō)，輸入矩陣被分割成子矩陣并用隨機矩陣編碼[8]。下面以工作節點(diǎn)為8、共謀節點(diǎn)為1來(lái)說(shuō)明編碼過(guò)程。

主節點(diǎn)首先將輸入矩陣A，B進(jìn)行劃分，如式（1）所示：

                                                  （1）

然后分別為A、B各生成一個(gè)隨機矩陣KA、KB。主節點(diǎn)為每個(gè)工作節點(diǎn)i選擇不同的參數xi，生成的編碼數據如式（2）和式（3）：

                                     （2）

                                                                   （3）

工作節點(diǎn)在接收到編碼數據后，每個(gè)工作節點(diǎn)i計算，并將計算結果返回給主節點(diǎn)，則每個(gè)工作節點(diǎn)的計算任務(wù)相當于多項式h（x）在點(diǎn)x=xi的值如式（4）：

                       （4）

由上式可知，多項式h（x）中4項A1B1、A2B1x、A1B2x、A2B2x的系數可組成最終結果，而在整個(gè)過(guò)程中，任一計算節點(diǎn)均未收到原始數據，一定程度上保障了數據的安全與隱私。因此，主節點(diǎn)可以采取多項式插值法確定該多項式，從而獲得所需的系數。

圖3面向安全隱私編碼示例

4基于編碼計算的邊端融合計算架構

傳統的邊端融合計算架構如圖4（a）所示，邊端融合環(huán)境下無(wú)論是邊緣設備還是終端設備都可以被抽象為計算節點(diǎn)，它們既可以向其余節點(diǎn)發(fā)送任務(wù)，也可以參與到任務(wù)的計算中來(lái)。例如任務(wù)A可以在主節點(diǎn)處進(jìn)行劃分并分別卸載到三個(gè)不同的節點(diǎn)，只有所有計算結果成功返回主節點(diǎn)才能恢復出最終結果。但是邊端融合環(huán)境中的節點(diǎn)大多是由不可靠的低端硬件構成，這些節點(diǎn)極易出現失效或掉隊現象，這會(huì )給計算任務(wù)造成不可預測的延遲。此外，邊端融合環(huán)境中節點(diǎn)資源受限并且網(wǎng)絡(luò )條件處于高度動(dòng)態(tài)變化中，這使得原有的數據保護方案難以應用到邊端融合環(huán)境中，從而導致了數據泄露問(wèn)題。

將編碼計算融入至邊端融合計算是解決上述問(wèn)題的潛力途徑，其架構如圖4（b）所示。該架構中主節點(diǎn)在任務(wù)分發(fā)之前會(huì )對原始任務(wù)矩陣進(jìn)行編碼，即便在任務(wù)傳輸時(shí)數據遭到泄露，攻擊者也只能獲取到編碼之后的數據而無(wú)法恢復出原始數據。同時(shí)，通過(guò)觀(guān)察可知，主節點(diǎn)只需要接收到任意3個(gè)計算結果就能恢復出最終結果，即便某個(gè)節點(diǎn)出現掉隊或者失效現象也不會(huì )對整個(gè)任務(wù)造成高延遲現象。

圖4邊端融合計算架構演變圖

5案例：基于編碼技術(shù)的邊端融合任務(wù)卸載策略

即便基于編碼計算的邊端融合計算架構解決了由掉隊現象帶來(lái)的計算延遲并避免了數據泄露問(wèn)題，但是主節點(diǎn)在任務(wù)分發(fā)階段仍然延續了編碼計算在分布式云環(huán)境中的平均分配原則。需要注意的是，邊端融合環(huán)境中的節點(diǎn)在計算性能、地理位置、網(wǎng)絡(luò )條件等方面存在極大的異構性，簡(jiǎn)單地將編碼任務(wù)進(jìn)行平均分配無(wú)疑會(huì )降低整個(gè)分布式系統的任務(wù)執行效率。此外，編碼計算容易產(chǎn)生大量冗余數據，引發(fā)高能耗問(wèn)題。為此，接下來(lái)我們探討一個(gè)基于編碼技術(shù)的邊端融合任務(wù)卸載問(wèn)題。

如圖5所示，該系統由一個(gè)主節點(diǎn)和多個(gè)工作節點(diǎn)構成的集合I組成。這些節點(diǎn)大多是由不可靠的低端硬件組成，并且節點(diǎn)之間在計算性能、地理位置和通信能力等方面存在較大的異構性。在任務(wù)分發(fā)之前，位于主節點(diǎn)上的原始任務(wù)矩陣將按行平均劃分為K個(gè)子任務(wù)，在使用MDS碼編碼之后整個(gè)任務(wù)矩陣變?yōu)榱薔行，即N個(gè)子任務(wù)。編碼后的子任務(wù)既可以選擇直接在本地執行，也可以卸載到工作節點(diǎn)上執行。當選擇卸載到工作節點(diǎn)上執行時(shí)，工作節點(diǎn)會(huì )有一定幾率出現掉隊現象從而導致任務(wù)完成時(shí)間增加。一旦主節點(diǎn)接收到任意K個(gè)返回結果時(shí)就能恢復出最終結果。

圖5編碼任務(wù)部分卸載架構圖

（1）系統算法設計：針對邊端融合環(huán)境下的編碼任務(wù)部分卸載問(wèn)題，我們提出了一種基于迭代貪心的節點(diǎn)選擇算法。該算法通過(guò)對工作節點(diǎn)進(jìn)行迭代交換的方式不斷降低整個(gè)系統的能量開(kāi)銷(xiāo)，算法的具體步驟如表1所示。

表1基于迭代貪心的節點(diǎn)選擇算法

（2）實(shí)驗結果：為了評估該系統所使用算法的性能，我們將所提出的算法（IterationGreedyPolicy，IGP）與隨機卸載算法（RandomOffloadingPolicy，ROP）、全卸載算法（AllOffloadingPolicy，AOP）和本地優(yōu)先算法（LocalComputingPolicy，LCP）進(jìn)行對比并分別探究了主節點(diǎn)發(fā)送功率和工作節點(diǎn)CPU頻率等因素對于不同方案能量開(kāi)銷(xiāo)的影響，實(shí)驗結果如圖6、7所示。

圖6不同方案的能量開(kāi)銷(xiāo)與主節點(diǎn)發(fā)送功率關(guān)系圖

圖7不同方案的能量開(kāi)銷(xiāo)與工作節點(diǎn)CPU頻率關(guān)系圖

調節主節點(diǎn)發(fā)送功率，四種方案能量開(kāi)銷(xiāo)的變化情況如圖6所示，增大主節點(diǎn)的發(fā)送功率會(huì )提高傳輸任務(wù)的能量開(kāi)銷(xiāo)但本地執行的能量開(kāi)銷(xiāo)保持不變。由于A(yíng)OP方案將所有任務(wù)卸載到工作節點(diǎn)執行，故該方案的能量開(kāi)銷(xiāo)增幅最大。盡管LCP方案將大部分任務(wù)交由主節點(diǎn)執行，但受制于任務(wù)時(shí)延約束的影響，仍有少部分任務(wù)被卸載到工作節點(diǎn)執行，所以L(fǎng)CP方案的能耗曲線(xiàn)雖保持不斷上漲但增幅較低。我們所提出的IGP方案產(chǎn)生的能量開(kāi)銷(xiāo)相比于其他方案保持最低，一方面是隨著(zhù)任務(wù)傳輸能量的提高，會(huì )有越來(lái)越多的任務(wù)轉移到主節點(diǎn)上執行，另一方面IGP方案存在著(zhù)工作節點(diǎn)的迭代交換過(guò)程，該過(guò)程會(huì )不斷地對能耗進(jìn)行優(yōu)化調整。

調節工作節點(diǎn)CPU頻率，四種方案能量開(kāi)銷(xiāo)的變化情況如圖7所示，提高工作節點(diǎn)的CPU頻率會(huì )縮短任務(wù)執行時(shí)間但主節點(diǎn)執行和發(fā)送任務(wù)的能量開(kāi)銷(xiāo)保持不變。同時(shí)工作節點(diǎn)性能的增強不會(huì )改變AOP方案和LCP方案的卸載決策，因此AOP方案與LCP方案的能量開(kāi)銷(xiāo)自動(dòng)化博覽·邊緣計算專(zhuān)輯/2023.02/49保持不變，ROP方案的能量開(kāi)銷(xiāo)仍然呈現一定的波動(dòng)性。我們所提出的IGP方案產(chǎn)生的能量開(kāi)銷(xiāo)保持最低，并且在1.5GHz至2.7GHz區間能量開(kāi)銷(xiāo)不斷降低，隨后保持不變，這是由于部分工作節點(diǎn)計算性能較差無(wú)法滿(mǎn)足任務(wù)的時(shí)延約束，但這類(lèi)節點(diǎn)在地理位置和網(wǎng)絡(luò )條件方面存在優(yōu)勢，從而導致傳輸任務(wù)產(chǎn)生的能量開(kāi)銷(xiāo)較低。隨著(zhù)工作節點(diǎn)的性能增強，這類(lèi)節點(diǎn)也會(huì )逐漸滿(mǎn)足任務(wù)的時(shí)延約束，從而在IGP方案的迭代交換部分能夠實(shí)現對于這類(lèi)節點(diǎn)的選擇。

6結語(yǔ)

隨著(zhù)智能設備算力的不斷加強，邊端融合計算架構正發(fā)揮著(zhù)舉足輕重的作用，但應用邊端融合計算到實(shí)際生活中還面臨著(zhù)諸多挑戰，編碼計算的出現有望打破僵局。因此，本文介紹了邊端融合計算架構所面臨的挑戰與編碼計算的基本思想，提出了基于編碼計算的邊端融合計算架構，并設計了一種基于編碼計算的邊端融合任務(wù)卸載策略作為案例，以此驗證編碼計算與邊端融合計算架構相結合技術(shù)的可行性。

作者簡(jiǎn)介：

楊在航（1997-），男，湖北人，碩士，現就讀于中國地質(zhì)大學(xué)（武漢）計算機學(xué)院，研究方向為編碼計算、邊端融合計算等。

李躍鵬（1994-），男，河南人，博士，現就讀于中國地質(zhì)大學(xué)（武漢）計算機學(xué)院，主要研究方向為可信邊緣計算等。

曾德澤（1984-），男，四川人，中國地質(zhì)大學(xué)（武漢）計算機學(xué)院教授、博士生導師，主要研究方向為邊緣計算、未來(lái)網(wǎng)絡(luò )等。

參考文獻：

[1]鄭騰飛,周桐慶,蔡志平,吳虹佳.編碼計算研究綜述[J].計算機研究與發(fā)展,2021,58(10):2187-2212.

[2]GuoY,GuS,ZhangQ,etal.Acodeddistributedcomputingframeworkfortaskoffloadingfrommulti-UAVtoedgeservers[C].2021IEEEWirelessCommunicationsandNetworkingConference(WCNC).IEEE,2021:1-6.

[3]PrakashS,DhakalS,AkdenizMR,etal.Codedcomputingforlow-latencyfederatedlearningoverwirelessedgenetworks[J].IEEEJournalonSelectedAreasinCommunications,2020,39(1):233-250.

[4]ZhaoS.Anode-selection-basedsub-taskassignmentmethodforcodededgecomputing[J].IEEECommunicationsLetters,2019,23(5):797-801.

[5]VargheseB,WangN,BarbhuiyaS,etal.Challengesandopportunitiesinedgecomputing[C].2016IEEEInternationalConferenceonSmartCloud(SmartCloud).IEEE,2016:20-26.

[6]ShiW,CaoJ,ZhangQ,etal.Edgecomputing:Visionandchallenges[J].IEEEInternetofThingsJournal,2016,3(5):637-646.

[7]LiH,ShouG,HuY,etal.Mobileedgecomputing:Progressandchallenges[C].20164thIEEEInternationalConferenceonMobileCloudComputing,Services,andEngineering(MobileCloud).IEEE,2016:83-84.

[8]ChangWT,TandonR.Onthecapacityofsecuredistributedmatrixmultiplication[C].2018IEEEGlobalCommunicationsConference(GLOBECOM).IEEE,2018:1-6.

[9]CaoC,WangJ,WangJ,etal.Optimaltaskallocationandcodingdesignforsecurecodededgecomputing[C].2019IEEE39thInternationalConferenceonDistributedComputingSystems(ICDCS).IEEE,2019:1083-1093.

[10]YadwadkarNJ,HariharanB,GonzalezJE,etal.Multi-tasklearningforstraggleravoidingpredictivejobscheduling[J].TheJournalofMachineLearningResearch,2016,17(1):3692-3728.

摘自《自動(dòng)化博覽》2023年第2期暨《邊緣計算2023專(zhuān)輯》