面向邊緣計算系統的隱私編碼計算方案

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

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

0 引 言

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

1 相關工作

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

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

2 問題建模

2.1 系統模型

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

圖1 隱私邊緣計算的系統模型

2.2 計算框架

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

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

(1)

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

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

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

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

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

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

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

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

(2)

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

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

圖2 解碼示例

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

定義2 通信負載：邊緣設備返回給用戶的中間結果的大小，即所有中間結果對應的矩陣中的元素總個數。

2.3 攻擊模型與隱私要求

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

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

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

(3)

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

3 隱私編碼計算方案PCEC

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

3.1 PCEC方案設計

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

3.1.1 存儲分配

圖3 存儲分配示例

3.1.2 計算方案設計

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

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

通用設計：首先為每個設備返回的結果設計通用的消息結構，然后用設備存儲的數據來具體地實例化該消息結構。

表1 t=2,α=2時消息結構示例

表2 t=3,α=3時消息結構示例

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

3.1.3 邊緣計算過程

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

3.2 理論分析

3.2.1 隱私性證明

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

證明：根據鏈規則，將式(3)中的隱私條件轉化如下

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

(4)

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

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

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

3.2.2 可解碼性證明

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

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

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

4 仿真結果與分析

4.1 環境和參數設置

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

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

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

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

4.2 計算方案的性能

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

圖4 通信負載與w關系

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

圖5 通信負載與n關系

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

圖6 通信負載與t0關系

5 結束語

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