昌繼青，儲海波，王 進+，沈 炯，施連敏

(1.蘇州大學 計算機科學與技術(shù)學院，江蘇 蘇州 215006；2.蘇州市公安局 大數(shù)據(jù)建設(shè)應(yīng)用支隊，江蘇 蘇州 215008)

0 引 言

傳統(tǒng)的云計算模型由于集中式的存儲特點與帶寬資源限制已經(jīng)無法滿足計算任務(wù)的實時性和高效性需求[1]。在此背景下，邊緣計算作為物聯(lián)網(wǎng)設(shè)備和云數(shù)據(jù)中心之間的橋梁，開創(chuàng)了在網(wǎng)絡(luò)邊緣收集、處理數(shù)據(jù)的新型計算模式。邊緣計算利用靠近數(shù)據(jù)源端的邊緣設(shè)備為用戶提供實時的數(shù)據(jù)處理服務(wù)，將云計算任務(wù)部分卸載到網(wǎng)絡(luò)邊緣以減輕云中心的計算、通信負載，已經(jīng)成為新的研究熱點[2]。雖然邊緣計算能夠有效縮短計算任務(wù)的完成時間且應(yīng)用前景廣闊，但由于邊緣設(shè)備輕量化、分布式等特點，隱私安全和資源限制問題已經(jīng)成為邊緣計算發(fā)展過程中的兩個巨大挑戰(zhàn)。首先，邊緣設(shè)備，如基站、移動終端、路由器、個人電腦等，通常存儲、計算和通信資源有限。尤其，邊緣設(shè)備有限的存儲資源直接限制了它們可以執(zhí)行的計算和通信任務(wù)數(shù)量。因此，如何充分利用邊緣設(shè)備的有限資源，高效地完成計算任務(wù)值得深思。其次，不可信的邊緣設(shè)備引起的隱私安全問題也亟需解決。邊緣設(shè)備通常分散在用戶側(cè)，其分布式的特征導致邊緣設(shè)備更容易被入侵者監(jiān)視或攻擊。在許多邊緣計算應(yīng)用場景中，例如智慧醫(yī)療、自動駕駛、附近影院推薦服務(wù)等，邊緣設(shè)備可能從歷史記錄中推斷出用戶的隱私偏好，損害用戶的隱私安全。因此，本文針對存儲資源有限的邊緣計算系統(tǒng)，設(shè)計了一種隱私編碼計算方案(private coded computation scheme for edge computing system，PCEC)，在保護用戶隱私的前提下有效地降低了通信負載。PCEC方案給出了一個基于線性編碼的計算方案，通過將目標數(shù)據(jù)與其它數(shù)據(jù)通過線性操作混合，使得邊緣設(shè)備在計算過程中無法識別用戶目標數(shù)據(jù)，同時降低通信負載。

1 相關(guān)工作

近年來，在邊緣計算領(lǐng)域的學者們?nèi)〉昧嗽S多優(yōu)秀的成果。Li等[3]提出了一種通用的編碼邊緣計算方案將計算任務(wù)卸載到邊緣設(shè)備，同時考慮計算負載的最小化以及通信效率的最大化。Zhou等[4]以矩陣乘法任務(wù)為例，利用空閑邊緣設(shè)備進行分布式計算以降低計算延遲。越來越多的研究關(guān)注到了邊緣設(shè)備的輕量化和分布式特征，思考如何充分利用有限的資源高效地完成任務(wù)。比如，Wang等[5]針對設(shè)備存儲資源有限且存儲容量各不相同的邊緣系統(tǒng)，通過任務(wù)分配方案和編碼計算方案的聯(lián)合設(shè)計，最小化矩陣相乘任務(wù)中的總成本。Li等[6]提出了一個統(tǒng)一的分布式編碼框架，并將其應(yīng)用在霧計算系統(tǒng)中，實現(xiàn)了通信資源和計算資源之間的權(quán)衡。

此外，邊緣計算中的安全問題，包括數(shù)據(jù)機密性和用戶隱私性[7]，也引起了學者的廣泛關(guān)注。線性編碼能夠在保證安全的同時低帶寬消耗和傳輸延遲[8]，已經(jīng)得到了廣泛的應(yīng)用。在數(shù)據(jù)機密性方面，許多文獻已經(jīng)提出了各種安全高效的編碼計算方案并考慮了豐富的計算模型，例如同構(gòu)邊緣系統(tǒng)[9]、異構(gòu)邊緣系統(tǒng)[10]、“滯后節(jié)點”問題[11]、合作攻擊模型[12]、主動攻擊模型[13]等。然而保護用戶隱私也具有現(xiàn)實意義卻尚未得到充分的研究。針對用戶隱私的保護，Sun等[14]通過將原始數(shù)據(jù)與其它信息進行混淆實現(xiàn)了隱私數(shù)據(jù)恢復。Mirmohseni等[15]提出了一種編碼計算方案，利用設(shè)備幫助用戶計算來自N臺服務(wù)器的K條消息的任意函數(shù)，同時對每個設(shè)備隱藏該函數(shù)。在矩陣乘法任務(wù)中，Kim等[16]提出了一種基于多項式編碼的計算方案，同時保護了數(shù)據(jù)機密性和用戶隱私性。在以上隱私問題的研究中，計算設(shè)備需要存儲整個數(shù)據(jù)，或者從遠程公共數(shù)據(jù)庫下載數(shù)據(jù)。這些方案帶來了額外的存儲要求和通信負載，不能直接應(yīng)用于資源有限的邊緣計算系統(tǒng)。因此，如何利用資源有限的邊緣設(shè)備，在保護用戶隱私的前提下高效地完成計算任務(wù)，成為研究的重點。

2 問題建模

2.1 系統(tǒng)模型

如圖1所示，邊緣計算系統(tǒng)模型通常由云、用戶s0和n個邊緣設(shè)備si組成，i∈{1,…,n} 且n≥2。 邊緣中有一個由w個大小為r×s的矩陣組成的庫B={B1,B2,…,Bw}， 且數(shù)據(jù)塊Bj是B中的第j個矩陣，j∈{1，…,w}，w≥2。 每個邊緣設(shè)備最多存儲t0個數(shù)據(jù)塊，即t0為邊緣設(shè)備的存儲限制，t0>0。 用戶擁有一個大小為m×r的本地矩陣A且僅想要使用B中的一個數(shù)據(jù)塊計算得到ABθ,θ∈{1，…,w}。 用戶隱私性要求任意一個邊緣設(shè)備無法識別用戶目標矩陣的下標θ。

圖1 隱私邊緣計算的系統(tǒng)模型

2.2 計算框架

(.)[i,j]代表一個矩陣第i行第j列的元素，塊矩陣相乘操作定義如下：

定義1 塊矩陣相乘?：假定存在一個大小為e×f的矩陣Q和一個大小為g×h的矩陣F，Qu代表矩陣Q的第u行。按列將矩陣F分成f個層，其中Fv代表第v個層，那么執(zhí)行塊矩陣相乘操作后可以得到式(1)

(1)

然后，隱私計算流程如圖1所示：

(1)用戶將所需數(shù)據(jù)塊的索引θ發(fā)給云，并將矩陣A分發(fā)給邊緣設(shè)備。

(2)收到θ后，云會生成一個計算方案，包括一組編碼系數(shù)矩陣Q={Q1,Q2,…,Qn}， 一個選擇矩陣C和一個解碼矩陣D。然后云把Q發(fā)送給邊緣設(shè)備。

(3)在收到Qi和A后，邊緣設(shè)備si開始執(zhí)行計算任務(wù)。

1)si將存儲的每個數(shù)據(jù)塊按列分成l=αt個層后得到Fi= [M1,1…M1,lM2,1…M2,l…Mt,l]。

2)si計算Gi=Qi?Fi后進一步得到Ri=AGi并把結(jié)果返回給用戶。Ri,u=AGi,u代表Ri中的第u個值。

(4)當接收到所有中間結(jié)果后，用戶s0完成如圖2所示的解碼過程：

1)s0根據(jù)矩陣C選擇Ri中有用的值并得到R′i。 具體來說，若C[i,j]=1， 用戶選擇Ri,j用于解碼過程，并將它加入到R′i。h表示式(2)的值

(2)

2)s0計算得到R′=[R′1T…R′nT]T， 其中 (.)T代表矩陣轉(zhuǎn)置。實際上，R′中共有h個值，其中的任意值都是來自集合 {ABj,v|j∈{1,…,w},v∈{1,…,l}} 中的h個層的線性組合。如果用一個大小為h的矢量x代表這些層，可以得到R′=Dx， 其中D是相應(yīng)的編碼矩陣。

3)s0可以解碼R′=Dx得到x，并恢復出ABθ。

圖2 解碼示例

為評估所提計算方案，我們給出如下定義：

定義2 通信負載：邊緣設(shè)備返回給用戶的中間結(jié)果的大小，即所有中間結(jié)果對應(yīng)的矩陣中的元素總個數(shù)。

2.3 攻擊模型與隱私要求

本文研究了被動攻擊模型，每個邊緣設(shè)備均可能是被動攻擊者，或者被攻擊者竊聽。這些被動攻擊者相互不勾結(jié)，但不斷竊聽網(wǎng)絡(luò)內(nèi)的計算節(jié)點，試圖從收到的數(shù)據(jù)包中破解出用戶的信息。本文重點關(guān)注通信和數(shù)據(jù)計算過程中的隱私保護問題，當用戶解碼得到ABθ后，任意一個設(shè)備無法識別用戶目標矩陣的下標，即θ。 類似的隱私條件已經(jīng)在文獻[14,16]中被研究過。因此，對邊緣設(shè)備的隱私約束為：

定義3 隱私條件：當且僅當對任意i∈{1,…,n}， 邊緣設(shè)備si均滿足式(3)時，計算方案保證了用戶的隱私安全

I(θ;Qi,A,Ri,Vi)=0

(3)

式中：I(·;·) 表示互信息，用于度量變量間共享的信息。式(3)表示邊緣設(shè)備的獲得數(shù)據(jù)Qi,A,Ri,Vi與θ相互獨立，即無法從Qi,A,Ri,Vi中獲得θ的任何信息。

3 隱私編碼計算方案PCEC

本節(jié)給出PCEC的方案設(shè)計。同時我們對該方案進行理論分析，證明它滿足了隱私條件且可以保證ABθ的恢復。

3.1 PCEC方案設(shè)計

本小節(jié)將從存儲分配、隱私計算方案設(shè)計和邊緣計算過程3個關(guān)鍵部分對提出的PCEC方案進行描述。

3.1.1 存儲分配

圖3 存儲分配示例

3.1.2 計算方案設(shè)計

為了便于計算方案的理解，我們先基于圖2中的例子描述PCEC方案的大體思路，然后給出該方案的通用設(shè)計。

示例：在圖2中的邊緣計算部分，有n=3個邊緣設(shè)備和w=3個數(shù)據(jù)塊，每個邊緣設(shè)備存儲了t=2個數(shù)據(jù)塊，每個塊出現(xiàn)在α=2個設(shè)備中，用戶想得到AB1。 在圖2中節(jié)點返回的中間結(jié)果Ri中，目標數(shù)據(jù)塊B1中的每個層要么單獨出現(xiàn)，要么與在其它節(jié)點已經(jīng)發(fā)送過的層組合出現(xiàn)。因此，在所有設(shè)備返回結(jié)果后，用戶可以恢復出AB1。 此外，在s1返回的結(jié)果R1中，數(shù)據(jù)塊B1和B2都使用了2個不同的層。同時其它2個節(jié)點返回結(jié)果的結(jié)構(gòu)類似，且均使用了存儲數(shù)據(jù)塊的不同層。因此，這些邊緣設(shè)備無法辨別哪一個數(shù)據(jù)塊是用戶的目標。在以上例子中我們發(fā)現(xiàn)，可以對返回結(jié)果設(shè)計通用的數(shù)據(jù)結(jié)構(gòu)，以保證每個數(shù)據(jù)塊被使用相同的次數(shù)。同時，隨機選擇使用的層的順序可以進一步保證用戶的隱私性。

通用設(shè)計：首先為每個設(shè)備返回的結(jié)果設(shè)計通用的消息結(jié)構(gòu)，然后用設(shè)備存儲的數(shù)據(jù)來具體地實例化該消息結(jié)構(gòu)。

表1 t=2,α=2時消息結(jié)構(gòu)示例

表2 t=3,α=3時消息結(jié)構(gòu)示例

(2)實例化：接著我們用每個節(jié)點存儲的層來對消息結(jié)構(gòu)進行實例化。為了隱私安全，PCEC方案需要生成一個大小為w×l的隨機矩陣P來實現(xiàn)層的隨機選擇。具體地，第v次從Bj中選取一個層時，該方案將選擇B′j=Bj,u，u=P[j,v]。 因此在Bj中隨機選擇層，相當于在B′j中順序選擇層。首先，每個層在每個邊緣設(shè)備中不會被重復使用。其次，在所有邊緣設(shè)備中，按升序原則使用B′θ的所有層。第三，對于其它數(shù)據(jù)塊中層的選擇必須遵循3條規(guī)則：首先，在所有邊緣設(shè)備的1-sum中，按升序原則使用層。第二，在每個邊緣設(shè)備中，按升序原則使用與B′θ一起出現(xiàn)的層。第三，在每個邊緣設(shè)備中，按降序原則使用層。這3條規(guī)則由強到弱。以上規(guī)則可以保證PCEC最后能恢復出ABθ。

3.1.3 邊緣計算過程

在收到Qi和A后，邊緣設(shè)備si開始執(zhí)行計算任務(wù)。首先，si將存儲的每個數(shù)據(jù)塊按列分成l個層后得到Fi。 然后si計算Gi=Qi?Fi。 注意計算過程相當于把不同的層通過加法組合在一起，即實現(xiàn)隱私計算方案設(shè)計中消息結(jié)構(gòu)和實例化過程。最后，si計算Ri=AGi并把結(jié)果返回給用戶。

3.2 理論分析

3.2.1 隱私性證明

定理1 PCEC方案滿足隱私條件。

證明：根據(jù)鏈規(guī)則，將式(3)中的隱私條件轉(zhuǎn)化如下

I(θ;Qi,A,Ri,Vi)=I(θ;Qi)+I(θ;Vi|Qi)+
I(θ;A|Qi,A,Vi)+I(θ;Ri|Qi,Vi,A)

(4)

首先，用戶的本地數(shù)據(jù)A與θ無關(guān)，因此I(θ;A|Qi,A,Vi)=0。 同時存儲分配階段生成的設(shè)備存儲的數(shù)據(jù)Vi和Fi也與θ無關(guān)，即I(θ;Vi|Qi)=0。

由PCEC的設(shè)計過程可知Qi由消息結(jié)構(gòu)和實例化過程決定。其中消息結(jié)構(gòu)的設(shè)計完全與θ無關(guān)。此外，實例化過程相當于從數(shù)據(jù)塊中選擇不同的層。對于每個設(shè)備存儲的數(shù)據(jù)塊Mb，實例化過程選擇了αt-1個不同的層，b∈{1,…,t}， 設(shè)ob={ob,1,…,ob,αt-1},b∈{1,…,t} 為這些層的下標。ob,u實際上是隨機矩陣P中的一個值，u∈{1,…,αt-1}。 因此{ob|b∈{1,…,t}} 中的元素相互獨立且與θ無關(guān)。所以可知I(θ;Qi)=0。 由于Ri由A,Fi和Qi決定且它們均與θ無關(guān)，因此可得I(θ;Ri|Qi,Vi,A)=0。

綜上，對任意邊緣設(shè)備si,I(θ;Qi,A,Ri,Vi)=0均成立，即PCEC滿足隱私條件。

3.2.2 可解碼性證明

定理2 當 (α-1)t-1≥αt-2且α≥2時，PCEC方案可解碼出ABθ。

用z1代表第二種形式中的所有層的最大下標值。我們假設(shè)z1>p。 在PCEC方案選擇層Mu,z1之前，如果第三種形式中的所有層的下標均大于p，那么為前二種形式選擇層時，PCEC方案可以選擇 {Mu,z|z∈{1,…,p}} 中的任意層。同時，由于前二種形式中只需要p個層，并且第二種形式中的層按照升序原則選擇。因此可知z1≤p, 但這與z1>p相矛盾，所以第三種形式中必然存在一個層Mu,z2滿足z1>p≥z2。 當我們?yōu)榈谌N形式選擇Mu,z2時，Mu,z1尚未使用，然而我們選擇了小于z1的z2， 這與按照降序原則選擇層相矛盾。因此，假設(shè)不成立，即z1≤p且第二種形式中的所有層的下標均不大于p=αt-2+(α-1)t-1。

在消息結(jié)構(gòu)中，每種類型的1-sum由一個單獨的層構(gòu)成，且出現(xiàn)(α-1)t-1次。所以，對于每個設(shè)備中存儲的每個數(shù)據(jù)塊Mu， 我們可以直接獲得 (α-1)t-1個層。同時由于至少α個設(shè)備存儲了該數(shù)據(jù)塊，我們可以從1-sum中直接獲得α(α-1)t-1個層。在每個邊緣設(shè)備的1-sum中，任意非目標數(shù)據(jù)塊Mu遵循降序原則選擇層，因此用戶可以得到數(shù)據(jù) {AMu,v|v∈{1,…,α(α-1)t-1},Mu≠Bθ}。 當 (α-1)t-1≥αt-2,α≥2時，可得α(α-1)t-1=(α-1)(α-1)t-1+(α-1)t-1≥αt-2+(α-1)t-1=p， 即對于任意非目標數(shù)據(jù)塊Mu， 用戶可以直接得到 {AMu,v|v∈{1,…,p},Mu≠Bθ}。 在消息結(jié)構(gòu)中，Bθ中的每個層要么單獨出現(xiàn)要么與已經(jīng)發(fā)送過的非目標塊的層一起出現(xiàn)。因此，在PCEC方案中，當每個設(shè)備返回中間結(jié)果給用戶后，用戶可解碼出ABθ。

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

4.1 環(huán)境和參數(shù)設(shè)置

本文實驗的硬件環(huán)境為Intel Core i5-6400 CPU，8 GB內(nèi)存。我們使用Java語言進行編程實現(xiàn)存儲方案，通過大量實驗計算得到不同參數(shù)下，不同方案的通信負載。同時我們利用Matlab繪圖工具，繪制相關(guān)實驗圖，以此驗證提出方案的性能。我們考慮以下3種參數(shù)：①庫B中的矩陣數(shù)量w；②邊緣設(shè)備的數(shù)量n；③邊緣設(shè)備的存儲限制t0。參數(shù)的默認值為：m=1000，s=1000，n=20，w=15，t0=w/2。 對于每個參數(shù)組合，我們?yōu)槊總€方案生成100個實例，并報告平均結(jié)果。我們將本文的PCEC方案與以下方案比較：

(1)無編碼的隱私計算(uPC)方案：所有邊緣設(shè)備直接計算用戶本地數(shù)據(jù)A和節(jié)點存儲的所有數(shù)據(jù)塊的乘積，并將中間結(jié)果返回給用戶。該方案中用戶無需解碼，可以直接從中間結(jié)果中得到ABθ。 注意此時，若每個節(jié)點均只存儲2個數(shù)據(jù)塊，該方案通信負載最小為2n。

(2)基于分塊的隱私計算(BPC)方案：該方案利用簡單的分布式計算原理，首先將Bθ按列進行分塊，然后把計算ABθ的任務(wù)分散到所有存儲了Bθ的節(jié)點上，即讓這些節(jié)點各自完成一部分子任務(wù)。為了保證用戶隱私，所有設(shè)備除了計算ABθ的子任務(wù)外，還需要額外計算A和它們存儲的其它非目標數(shù)據(jù)塊的乘積，并將結(jié)果返回給用戶。

(3)基于范德蒙矩陣編碼的隱私計算(VPC)[16]方案：每個邊緣設(shè)備將存儲的矩陣按列分成塊α后使用范德蒙矩陣進行編碼。然后，每個設(shè)備將結(jié)果與A相乘，并將乘積返回給用戶。注意，當返回的總中間結(jié)果數(shù)量αn不小于未知數(shù)的數(shù)量αw時，該方案才能實現(xiàn)順利解碼出ABθ。

4.2 計算方案的性能

我們將比較4種方案的通信負載與在不同參數(shù)下的變化情況。首先分析通信負載與庫中的矩陣數(shù)量w的關(guān)系。當n為20個邊緣設(shè)備時，4種方案的通信負載的變化情況如圖4所示。從圖4中可以看到，當w從5變?yōu)?0時，BPC和PCEC的通信負載隨著w的增加而增加。這是因為當w增加時，BPC和PCEC中的邊緣設(shè)備需要將目標矩陣的數(shù)據(jù)與更多不同矩陣的數(shù)據(jù)混淆，導致通信負載增加。而uPC或VPC的通信負載與w無關(guān)。這是由于uPC可實現(xiàn)的最小通信負載是2n，與w無關(guān)。此外，我們還發(fā)現(xiàn)：①PCEC的性能優(yōu)于BPC(減少了約30%的負載)、VPC(減少約35%的負載)、uPC(減少75%的負載)；②在n

圖4 通信負載與w關(guān)系

然后我們分析通信負載與邊緣設(shè)備數(shù)量n的關(guān)系。當w為15個矩陣時，4種方案的通信負載的變化情況如圖5所示。從圖5中可以看到，uPC和VPC的通信負載隨著n的增加而線性增加。這是由于更多的節(jié)點存儲了更多的數(shù)據(jù)，需要返回的數(shù)據(jù)也相應(yīng)變多。其次我們發(fā)現(xiàn)，PCEC中通信負載的增加緩慢，幾乎可以忽略不計。這是由于PCEC中，當節(jié)點數(shù)量增加時，每個數(shù)據(jù)將被存儲更多次，數(shù)據(jù)矩陣的分層數(shù)變多且每一個中間結(jié)果變小，因此總的通信負載增加比較緩慢。此外，BPC的通信負載與n無關(guān)。這是因為BPC要求存儲Bθ的邊緣設(shè)備計算ABθ的一部分。如果有更多的邊緣設(shè)備，每個邊緣設(shè)備將承擔更少的計算任務(wù)。因此BPC的總通信負載主要取決于w的大小。相比較而言，PCEC總是能夠很好地減輕n的變化帶來的影響，并實現(xiàn)最少的通信負載。

圖5 通信負載與n關(guān)系

最后，我們分析通信負載與存儲限制t0的關(guān)系。在圖6中，系統(tǒng)中存在n=20個邊緣設(shè)備和w=15矩陣。通過將每個設(shè)備的存儲限制t0從w/8增加為w，我們比較了4種方案的通信負載。注意，當t0≤w/8時，有t0<2， 即每個設(shè)備最多只能存儲1個數(shù)據(jù)塊。而本文不考慮這種情況下的隱私問題，所以默認每個方案的通信負載為0。從圖6中可知，uPC的通信負載較大，且基本不變。這是由于uPC可實現(xiàn)的最小通信負載是2n，與t0無關(guān)。其次，當t0從w/5增加為w/2時，每個方案的通信負載只有不明顯的降低。因此，在實際應(yīng)用中我們可以選擇存儲能力有限的節(jié)點完成隱私任務(wù)，將存儲資源相對豐富的節(jié)點投入到更復雜的計算任務(wù)中，可以保證通信負載基本不變的前提下，提高節(jié)點的利用率。最后，我們發(fā)現(xiàn)BPC和PCEC的通信負載隨著t0的增加而有所減少，且PCEC始終實現(xiàn)了最低的通信負載。因此，本文提出的方案能夠充分利用邊緣設(shè)備存儲資源有效地節(jié)約通信成本。

圖6 通信負載與t0關(guān)系

5 結(jié)束語

本文主要研究了在一個資源有限的邊緣計算系統(tǒng)中，如何高效地完成計算任務(wù)并保證用戶的隱私安全的問題。針對上述問題，提出了一種面向邊緣計算系統(tǒng)的隱私編碼計算方案，通過設(shè)計基于冗余的存儲方案以及基于線性編碼的計算方案，能夠充分利用邊緣設(shè)備的存儲資源，解決邊緣計算中的隱私保護問題，并降低通信負載。最后，通過設(shè)計實驗對所提PCEC方案進行了分析評估。實驗結(jié)果表明，與其它方案相比，PCEC能夠有效地減少約75%的通信負載。在下一步工作中，我們將利用現(xiàn)實的邊緣計算系統(tǒng)驗證所提出的方案，并考慮異構(gòu)邊緣計算系統(tǒng)中的隱私保護問題。