李 卓，宋子暉，沈 鑫，陳 昕

（1.網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室（北京信息科技大學(xué)），北京 100101；2.北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京 100101）

（*通信作者電子郵箱lizhuo@bistu.edu.cn）

0 引言

在移動群智感知（Mobile Crowd Sensing，MCS）系統(tǒng)［1］中，用戶完成數(shù)據(jù)感知任務(wù)后向MCS 平臺提交感知數(shù)據(jù)，用戶的提交數(shù)據(jù)包括位置信息和感知數(shù)據(jù)。由于提交中的位置信息與用戶的實(shí)際位置統(tǒng)一，任務(wù)感知結(jié)果反映出用戶實(shí)際所處的真實(shí)環(huán)境信息［2］，導(dǎo)致用戶提交數(shù)據(jù)存在泄漏用戶隱私的風(fēng)險(xiǎn)。一方面，不同屬性之間存在不同的用戶隱私風(fēng)險(xiǎn)；另一方面，屬性之間的關(guān)聯(lián)也會暴露用戶隱私。如地圖信息感知任務(wù)，用戶去指定地點(diǎn)查看該地點(diǎn)的建筑名稱等信息并提交到MCS 服務(wù)器，感知數(shù)據(jù)為地名、建筑名等公共數(shù)據(jù)，但只對用戶提交數(shù)據(jù)中的位置信息隱私保護(hù)，通過感知結(jié)果依舊可以泄露用戶的位置隱私。

設(shè)計(jì)MCS 中的隱私保護(hù)機(jī)制比較復(fù)雜。不同于其他MCS 存在用戶主動上傳數(shù)據(jù)這一步驟，這一步驟增加了用戶隱私泄露的風(fēng)險(xiǎn)；MCS 中的用戶執(zhí)行的感知任務(wù)多為公共數(shù)據(jù)，導(dǎo)致提交數(shù)據(jù)中的信息會與眾多公開信息關(guān)聯(lián)，進(jìn)一步增加了用戶隱私泄露的風(fēng)險(xiǎn)；同時無法保證MCS 服務(wù)平臺的可信程度，隱私保護(hù)機(jī)制不僅要面向攻擊者，同時也要面向MCS系統(tǒng)本身。

本地差分隱私（Local Differential Privacy，LDP）［3］保護(hù)是一種不依賴可信第三方、不受限于類型的數(shù)據(jù)隱私量化方法。LDP隱私保護(hù)的原理是對整體數(shù)據(jù)添加隨機(jī)噪聲達(dá)到保護(hù)個體數(shù)據(jù)的目的，因此在數(shù)據(jù)量相同的情況下，發(fā)布數(shù)據(jù)的有效數(shù)據(jù)比例減小。

綜合考慮MCS 中用戶提交數(shù)據(jù)的特點(diǎn)，本文針對邊緣計(jì)算（Edge Computing，EC）支持下MCS 場景，基于本地差分隱私（LDP）保護(hù)原理設(shè)計(jì)出用戶提交數(shù)據(jù)屬性聯(lián)合隱私保護(hù)的CS-MVP（Crowd Sensing with Multi-Value data privacy Protection）算法和用戶提交數(shù)據(jù)屬性獨(dú)立隱私保護(hù)的CS-MAP（Crowd Sensing with Multi-Attribute data privacy Protection）算法。針對用戶提交數(shù)據(jù)的多個屬性，將屬性關(guān)聯(lián)為兩部分：一是位置數(shù)據(jù)和感知結(jié)果數(shù)據(jù)的關(guān)聯(lián)關(guān)系，該部分體現(xiàn)數(shù)據(jù)的可用性；另一部分為用戶信息數(shù)據(jù)分別與位置數(shù)據(jù)和感知結(jié)果數(shù)據(jù)的關(guān)聯(lián)關(guān)系，該部分體現(xiàn)了用戶的隱私。CS-MVP 和CS-MAP 算法使得用戶提交數(shù)據(jù)滿足上述兩部分所構(gòu)建的LDP隱私約束模型。本文算法的主要優(yōu)點(diǎn)如下：

1）用戶僅需依據(jù)算法在本地對提交數(shù)據(jù)依概率替換，無需增加額外的交互和計(jì)算過程，且無需依賴可信第三方。

2）依據(jù)MCS 屬性關(guān)聯(lián)的LDP 隱私約束相較于LDP 數(shù)據(jù)隱私約束，避免了對單個屬性數(shù)據(jù)進(jìn)行大規(guī)模統(tǒng)計(jì)計(jì)算恢復(fù)原始感知數(shù)據(jù)的分布，用戶提交數(shù)據(jù)中直接保留了可用性部分，增加了數(shù)據(jù)的可用性。

3）針對不同規(guī)模的MCS 任務(wù)類型設(shè)計(jì)了CS-MVP 和CS-MAP 兩種隱私保護(hù)算法。CS-MVP 算法以屬性聯(lián)合的方法來增加隱私性，解決了隨機(jī)擾動范圍較小時，LDP模型的隨機(jī)性降低造成的隱私性降低問題；CS-MAP算法以屬性獨(dú)立的方式增加數(shù)據(jù)可用性，解決了任務(wù)數(shù)量和感知數(shù)據(jù)范圍較大的場景下，LDP模型的隨機(jī)性增加導(dǎo)致數(shù)據(jù)可用性降低問題。

1 研究現(xiàn)狀

針對MCS 中用戶提交數(shù)據(jù)的隱私保護(hù)，當(dāng)前研究主要集中在保護(hù)用戶的位置信息和感知數(shù)據(jù)。

對于提交數(shù)據(jù)中的位置信息，由于用戶在執(zhí)行感知任務(wù)時，自身的位置與提交數(shù)據(jù)中的位置信息一致，因此，提交數(shù)據(jù)中的位置信息存在暴露用戶位置隱私的風(fēng)險(xiǎn)，用戶多次提交數(shù)據(jù)，可能泄露其軌跡。文獻(xiàn)［4］研究虛擬位置技術(shù)，將用戶的真實(shí)位置映射到一個虛擬的位置上來進(jìn)行數(shù)據(jù)提交，但虛擬位置存在一些不合理的情況導(dǎo)致隱私性降低，且攻擊者根據(jù)虛擬的位置和用戶背景知識可推斷出用戶實(shí)際位置。文獻(xiàn)［5］基于空間泛化技術(shù)提出了基于粒度的位置隱私保護(hù)算法，自適應(yīng)地將用戶位置泛化到不同粒度空間；在此基礎(chǔ)上，文獻(xiàn)［6］提出利用沃羅諾伊的概念來生成匿名區(qū)域；文獻(xiàn)［7］提出一種位置K-匿名的算法，用一個包含K個用戶的空間區(qū)域替代用戶的真實(shí)位置，在這K個用戶中，任何一個用戶的位置都與其他K-1個用戶的位置不可分辨。然而用戶節(jié)點(diǎn)移動性會導(dǎo)致匿名區(qū)域的改變，從而使匿名區(qū)域面積過小不滿足隱私保護(hù)要求，或過大降低位置準(zhǔn)確性。

文獻(xiàn)［8］提出基于區(qū)域覆蓋數(shù)量的中心化差分隱私保護(hù)技術(shù)，以單位區(qū)域中的用戶數(shù)量來構(gòu)建差分隱私保護(hù)模型，對城市人口流量數(shù)據(jù)中的個人位置進(jìn)行保護(hù)；文獻(xiàn)［9］定義密度約束來計(jì)算出整體感知用戶位置信息的全局敏感度，構(gòu)建滿足差分隱私的拉普拉斯噪聲分量，對整體感知數(shù)據(jù)的中的位置信息進(jìn)行差分隱私保護(hù)。

提交數(shù)據(jù)中的感知數(shù)據(jù)，包含數(shù)據(jù)類型復(fù)雜，且與用戶所處環(huán)境密切相關(guān)。感知數(shù)據(jù)本身會泄露用戶隱私，屬性之間的關(guān)聯(lián)也存在隱私泄露的風(fēng)險(xiǎn)，因?yàn)橥ㄟ^感知數(shù)據(jù)可間接獲得用戶當(dāng)前位置信息。為降低由用戶提交數(shù)據(jù)導(dǎo)致的用戶隱私泄露問題，文獻(xiàn)［10］利用多級代理機(jī)制，在不可信移動感知平臺之間構(gòu)建代理服務(wù)器，并提出了一種新的差分隱私保護(hù)機(jī)制使得用戶數(shù)據(jù)滿足差分隱私約束來保護(hù)用戶身份隱私；然而這種方式無法保證多級代理之間的可信程度，代理之間可能聯(lián)合從而使用戶隱私泄露。文獻(xiàn)［11］設(shè)計(jì)了一個對數(shù)據(jù)隱私保護(hù)下的移動群智感知系統(tǒng)架構(gòu)，利用多個功能實(shí)體間的相互協(xié)作，實(shí)現(xiàn)了節(jié)點(diǎn)授權(quán)驗(yàn)證、節(jié)點(diǎn)匿名提交數(shù)據(jù)、數(shù)據(jù)隱私驗(yàn)證、用戶匿名激勵發(fā)放等功能。該方法雖然可實(shí)現(xiàn)完整的匿名數(shù)據(jù)提交和匿名數(shù)據(jù)評估，但將系統(tǒng)功能分散為多個實(shí)體增加了系統(tǒng)復(fù)雜程度，用戶認(rèn)證、令牌加密等算法也增加了計(jì)算復(fù)雜性。

LDP 技術(shù)由于不受數(shù)據(jù)類型的限制，已有多項(xiàng)工作使用LDP 技術(shù)來保護(hù)社會感知數(shù)據(jù)［12-13］。文獻(xiàn)［14］基于Copula 函數(shù)構(gòu)造滿足LDP 的多維度群智感知數(shù)據(jù)。文獻(xiàn)［15］提出LoPub 算法，構(gòu)造多維本地差分隱私擾動機(jī)制來解決多屬性下的節(jié)點(diǎn)隱私保護(hù)機(jī)制，利用統(tǒng)計(jì)計(jì)算方法，從多維聯(lián)合分布中計(jì)算出單一屬性的邊緣分布情況。文獻(xiàn)［16］提出面向Key-Value 類型數(shù)據(jù)的隱私發(fā)布機(jī)制PrivKV 算法，對Key 屬性和Value 屬性的數(shù)據(jù)分別進(jìn)行LDP 擾動，并提供數(shù)據(jù)統(tǒng)計(jì)算法從被隱私化的數(shù)據(jù)中分別計(jì)算Key的頻數(shù)和Value的均值。然而，這些算法均只針對通用數(shù)據(jù)類型來設(shè)計(jì)隱私保護(hù)機(jī)制，沒有考慮MCS系統(tǒng)中用戶提交數(shù)據(jù)的特點(diǎn)。

本文基于邊緣計(jì)算支持下的MCS，提出CS-MVP 和CSMAP 用戶提交數(shù)據(jù)隱私保護(hù)算法，基于MCS 中用戶提交數(shù)據(jù)的屬性關(guān)系，構(gòu)建兩種關(guān)系之間的LDP隱私約束，不但應(yīng)用了LDP 理論在隱私保護(hù)上的優(yōu)勢，同時避免了在數(shù)據(jù)恢復(fù)時復(fù)雜的統(tǒng)計(jì)計(jì)算。

2 模型定義

本章定義MCS 的系統(tǒng)模型，并給出用戶提交數(shù)據(jù)的隱私性模型和任務(wù)數(shù)據(jù)的可用性模型，提出隱私約束下的可用性最大化問題。

2.1 移動群智感知用戶原始感知數(shù)據(jù)和提交數(shù)據(jù)模型

首先將用戶采提交據(jù)構(gòu)建為數(shù)學(xué)模型。設(shè)MCS 中感知任務(wù)位置集合L={l1，l2，…，lN}，感知任務(wù)結(jié)果的取值范圍X={x1，x2，…，xM}，原始感知數(shù)據(jù)可表示為r=(l∈L，x∈X)，則任意用戶ui的提交數(shù)據(jù)記作di=

2.2 多屬性用戶提交數(shù)據(jù)的本地差分隱私模型

用戶的原始感知數(shù)據(jù)可以為任意位置和任意感知數(shù)據(jù)的組合，即r∈R，其中R為L和X中所有元素對應(yīng)構(gòu)成組合的集合。

任務(wù)執(zhí)行后，用戶獲得正確的原始感知數(shù)據(jù)ri∈RT。一組能保證任務(wù)完成的原始感知數(shù)據(jù)集合RT是R的一個子集，RT?R。RT表示所有位置li與用戶實(shí)際在該位置感知到的結(jié)果xi的組合的集合。

構(gòu)建滿足LDP的用戶原始感知數(shù)據(jù)和發(fā)布數(shù)據(jù)模型。存在隱私保護(hù)算法Q，其定義域和值域分別為RT和R，滿足：

存在隱私保護(hù)算法QX，其定義域和值域均為X；隱私保護(hù)算法QL，其定義域和值域均為L，滿足：

則算法Q滿足隱私預(yù)算為ε的用戶數(shù)據(jù)屬性聯(lián)合的本地差分隱私保護(hù)，QX、QL滿足隱私預(yù)算為ε的用戶數(shù)據(jù)屬性獨(dú)立的本地差分隱私保護(hù)。

2.3 用戶隱私化提交數(shù)據(jù)的可用性模型

用戶真實(shí)的提交數(shù)據(jù)集合D={d1，d2，…，di，…}。對D中所有數(shù)據(jù)采用相同的隱私保護(hù)算法，構(gòu)建隱私化提交數(shù)據(jù)集合D'={d'1，d'2，…，d'i，…}。

設(shè)D對應(yīng)的原始感知數(shù)據(jù)RT中存在ra=，ra∈RT，D'=Q(D)，則集合D'中任意r'∈R的概率為：

對于隱私化的用戶提交數(shù)據(jù)，相同位置中正確數(shù)據(jù)的概率大于錯誤數(shù)據(jù)的概率時，可保留正確感知數(shù)據(jù)信息。即D'中包含ra的數(shù)據(jù)的概率大于僅包含數(shù)據(jù)la的概率：

定義隱私保護(hù)算法Q生成的數(shù)據(jù)滿足MCS 任務(wù)可用性指標(biāo)I：

基于LDP 隱私模型，可用性指標(biāo)I反映了能從提交數(shù)據(jù)中恢復(fù)正確感知數(shù)據(jù)的概率。

2.4 隱私約束下的可用性最大問題

MCS 中用戶發(fā)布數(shù)據(jù)隱私約束下的可用性最大問題可記作：

3 EC支持下的用戶提交數(shù)據(jù)隱私保護(hù)算法

3.1 EC支持下的移動群智感知系統(tǒng)流程

為分離用戶和MCS 云服務(wù)器的直接交互，消除MCS 云服務(wù)器泄露用戶隱私的風(fēng)險(xiǎn)，在MCS 中引入邊緣計(jì)算架構(gòu)。同時，滿足LDP的隱私保護(hù)算法［17-20］對原始感知數(shù)據(jù)［21-22］隱私處理后會生成部分噪聲數(shù)據(jù)，隱私預(yù)算越高，提交數(shù)據(jù)中的噪聲數(shù)據(jù)越多，引入邊緣服務(wù)器，在靠近用戶端計(jì)算恢復(fù)出任務(wù)需求數(shù)據(jù)，過濾掉用戶提交數(shù)據(jù)中相同任務(wù)的噪聲數(shù)據(jù)，降低MCS系統(tǒng)數(shù)據(jù)傳輸成本。

基于邊緣計(jì)算架構(gòu)設(shè)計(jì)了MCS系統(tǒng)流程如圖1所示。任務(wù)分發(fā)階段，云服務(wù)器向邊緣服務(wù)器發(fā)布感知任務(wù)，由邊緣服務(wù)器代替云服務(wù)器對用戶進(jìn)行任務(wù)分發(fā)，用戶執(zhí)行的具體感知任務(wù)對云服務(wù)器保持隱私性；任務(wù)提交階段，用戶首先利用滿足LDP的隱私保護(hù)算法，本地處理原始感知數(shù)據(jù)，然后提交隱私化的感知數(shù)據(jù)給邊緣服務(wù)器；邊緣服務(wù)器聚合所有用戶提交數(shù)據(jù)，通過統(tǒng)計(jì)計(jì)算恢復(fù)任務(wù)結(jié)果提交云服務(wù)器。

圖1 邊緣計(jì)算支持下MCS用戶數(shù)據(jù)隱私保護(hù)流程Fig.1 Flow of MCS user data privacy protection supported by EC

整個過程中云服務(wù)器不直接接觸用戶數(shù)據(jù)，而邊緣服務(wù)器接觸到的為用戶滿足LDP 隱私的提交數(shù)據(jù)，因此保證了用戶隱私。

3.2 CS-MVP算法

本節(jié)介紹滿足LDP的用戶提交數(shù)據(jù)屬性聯(lián)合隱私保護(hù)算法的設(shè)計(jì)。屬性聯(lián)合即將用戶提交數(shù)據(jù)中的位置和感知結(jié)果屬性組合成的數(shù)據(jù)作為整體構(gòu)建隱私約束。隱私化的發(fā)布數(shù)據(jù)符合用戶提交數(shù)據(jù)取值范圍且滿足LDP隱私約束。

設(shè)L中位置的數(shù)量為N，感知任務(wù)的取值范圍X的元素?cái)?shù)量為M，則集合R中的元素個數(shù)為M×N。屬性聯(lián)合的原始感知數(shù)據(jù)的取值范圍為RT，隱私化的用戶提交數(shù)據(jù)中感知數(shù)據(jù)的取值范圍為R。Q為RT到R的隨機(jī)轉(zhuǎn)移矩陣。

考慮感知任務(wù)執(zhí)行前RT未確定。首先構(gòu)建由R向R的隨機(jī)轉(zhuǎn)移矩陣QR。QR的元素為條件概率qij=P(rj|ri)。

QR應(yīng)滿足以下約束：

式（9）表示任意元素ri變換為rj所有可能取值的概率和為1；式（10）表示該變換滿足隱私預(yù)算為ε的LDP隱私約束。

用戶提交數(shù)據(jù)可用性為：

在每個位置感知相同的數(shù)據(jù)量的情況下，問題（6）可轉(zhuǎn)換為：

求解可得：

任務(wù)執(zhí)行后，每個用戶依據(jù)其原始感知數(shù)據(jù)，選擇QR對應(yīng)的行，所有被選擇的行組成由RT向R的實(shí)際使用的轉(zhuǎn)移概率矩陣Q。如圖2所示。

圖2 基于隨機(jī)轉(zhuǎn)移矩陣的MCS用戶提交數(shù)據(jù)的隱私算法Fig.2 Privacy algorithm of MCS user submitted data based on random transition matrix

實(shí)際的狀態(tài)轉(zhuǎn)移矩陣Q依據(jù)真實(shí)的感知結(jié)果來構(gòu)建，在任務(wù)執(zhí)行前，邊緣服務(wù)器根據(jù)隱私預(yù)算，首先構(gòu)建完全隨機(jī)轉(zhuǎn)移矩陣QR，用戶在感知結(jié)束后選擇需要的行對原始感知數(shù)據(jù)隨機(jī)變換。隱私化的用戶感知流程為：

1）邊緣服務(wù)器計(jì)算感知任務(wù)位置數(shù)量N，感知數(shù)據(jù)取值范圍元素個數(shù)M。

2）邊緣服務(wù)器生成用戶原始感知數(shù)據(jù)取值范圍和提交數(shù)據(jù)取值范圍R：

3）邊緣服務(wù)器計(jì)算轉(zhuǎn)移概率參數(shù)a=M×N-1+eε。

4）邊緣服務(wù)器生成完全隨機(jī)轉(zhuǎn)移矩陣QR，其元素值為：

5）用戶執(zhí)行感知任務(wù)，獲得原始感知數(shù)據(jù)ri，從QR中選擇第i行對ri隨機(jī)變換得到隱私算法的發(fā)布數(shù)據(jù)r'，生成用戶提交數(shù)據(jù)=

屬性聯(lián)合的MCS 用戶提交數(shù)據(jù)隱私保護(hù)算法將用戶的原始感知數(shù)據(jù)隨機(jī)變換到取值空間中任意值，該算法可直接保留位置和感知結(jié)果的對應(yīng)關(guān)系。對于同一個任務(wù)位置，雖然取值空間存在多個值，但MCS 的用戶原始感知數(shù)據(jù)中，相同位置只存在唯一值，CS-MVP 算法將個體數(shù)據(jù)隨機(jī)化，擾亂了數(shù)據(jù)整體分布，但原始數(shù)據(jù)保持了最高的后驗(yàn)概率，因此恢復(fù)算法僅需統(tǒng)計(jì)提交數(shù)據(jù)的頻數(shù)即可恢復(fù)真實(shí)結(jié)果。

CS-MVP算法為用戶提交數(shù)據(jù)提供了嚴(yán)格的隱私性，但該算法中數(shù)據(jù)的取值空間大小為任務(wù)量和所有任務(wù)結(jié)果取值空間大小的乘積，當(dāng)任務(wù)量過多或任務(wù)取值范圍過大時，提交數(shù)據(jù)的取值范圍也將擴(kuò)大，這導(dǎo)致原始感知數(shù)據(jù)恢復(fù)算法需求的樣本量增加。為解決聯(lián)合隱私造成的取值空間相乘性擴(kuò)大問題，本文另外提出了屬性獨(dú)立的MCS 用戶提交數(shù)據(jù)的本地差分隱私保護(hù)算法。

3.3 CS-MAP算法

本節(jié)介紹屬性獨(dú)立的用戶提交數(shù)據(jù)的本地差分隱私保護(hù)算法。將用戶提交數(shù)據(jù)中位置屬性數(shù)據(jù)和感知結(jié)果數(shù)據(jù)獨(dú)立地進(jìn)行隱私保護(hù)，可降低多個屬性取值空間相乘引起的提交數(shù)據(jù)取值空間的擴(kuò)大。MCS中任務(wù)需求為位置數(shù)據(jù)和感知結(jié)果數(shù)據(jù)之間的對應(yīng)關(guān)系，因此，設(shè)計(jì)屬性獨(dú)立的MCS 用戶提交數(shù)據(jù)隱私保護(hù)機(jī)制需要在保證不同屬性獨(dú)立隱私約束的情況下保留位置和感知結(jié)果數(shù)據(jù)的對應(yīng)關(guān)系，以保留提交數(shù)據(jù)的可用性。

仍針對上述場景，所有任務(wù)的位置L的數(shù)量為N，感知任務(wù)的取值范圍X的元素?cái)?shù)量為M。屬性獨(dú)立的本地差分隱私算法即構(gòu)建由狀態(tài)空間L到L的轉(zhuǎn)移矩陣QL和由狀態(tài)空間到X的隨機(jī)變換矩陣QX。其中QL和QX的元素分別為

對于任意原始感知數(shù)據(jù)ra=，為保持生成提交數(shù)據(jù)中l(wèi)a和xa的對應(yīng)關(guān)系，基于獨(dú)立狀態(tài)轉(zhuǎn)移，設(shè)計(jì)了兩階段的轉(zhuǎn)移過程：第一階段，對ra=做隨機(jī)擾動，若生成數(shù)據(jù)為ra=，則用戶用原始感知數(shù)據(jù)構(gòu)建提交數(shù)據(jù)；若生成數(shù)據(jù)為虛假數(shù)據(jù)，則執(zhí)行第二階段。第二階段，構(gòu)建虛假數(shù)據(jù)，分別從集合L和集合X中去掉la和xa，然后以均勻分布分別從中選出的數(shù)據(jù)構(gòu)建用戶的提交數(shù)據(jù)。

基于上述步驟，可保留原始感知數(shù)據(jù)中位置和感知結(jié)果的對應(yīng)關(guān)系，即保留了用戶提交數(shù)據(jù)的可用性，并且可得出如下約束條件：

其中：式（17）為在兩個屬性獨(dú)立變換過程中保持正確數(shù)據(jù)的概率相同，且若在變換過程中位置保持不變，則此時感知數(shù)據(jù)也應(yīng)保持不變；式（18）為位置和感知數(shù)據(jù)獨(dú)立變換的約束，類比式（9）；式（19）屬于獨(dú)立的LDP隱私約束。

用戶提交數(shù)據(jù)可用性為：

屬性獨(dú)立的本地差分隱私保護(hù)算法，對用戶原始感知數(shù)據(jù)中的不同屬性數(shù)據(jù)獨(dú)立擾動，提交數(shù)據(jù)的取值空間相較于屬性聯(lián)合算法降低了樣本需求量；但屬性獨(dú)立算法只對數(shù)據(jù)的屬性滿足差分隱私約束，對用戶提交數(shù)據(jù)不滿足嚴(yán)格的隱私約束，相較于聯(lián)合算法隱私性降低。

3.4 基于差分隱私發(fā)布的感知數(shù)據(jù)恢復(fù)算法

本文所提出的CS-MVP 算法和CS-MAP 算法均依據(jù)MCS用戶提交數(shù)據(jù)屬性間關(guān)系分析和處理，擾亂用戶信息與位置、感知結(jié)果的對應(yīng)關(guān)系，保留位置與感知結(jié)果的對應(yīng)關(guān)系。邊緣服務(wù)器匯總所有用戶的提交數(shù)據(jù)，計(jì)算恢復(fù)任務(wù)感知數(shù)據(jù)的算法不需要經(jīng)過復(fù)雜的統(tǒng)計(jì)計(jì)算，根據(jù)用戶提交數(shù)據(jù)可用性最大化，只需要計(jì)算提交數(shù)據(jù)中相同位置數(shù)據(jù)中頻數(shù)最大值即可。具體流程如算法3所示。

匯總所有用戶的提交數(shù)據(jù)，提交數(shù)據(jù)中攜帶的隱私化任務(wù)感知數(shù)據(jù)屬于取值空間R，將提交數(shù)據(jù)按取值空間R計(jì)數(shù)，記錄每個可能取值的頻數(shù)；然后按相同位置將R劃分，對每個位置取頻數(shù)最大的元素，作為恢復(fù)的感知結(jié)果。

4 理論分析

4.1 算法的時間復(fù)雜性

根據(jù)算法1和算法2可分析得算法的時間復(fù)雜度。

定理1CS-MVP 算法的時間復(fù)雜度為O(MN)，CS-MAP算法的時間復(fù)雜度為O(max(M，N))。

算法1 中感知任務(wù)位置集合L，感知數(shù)據(jù)取值范圍X，采用嵌套循環(huán)，外循環(huán)共循環(huán)N次，內(nèi)循環(huán)共循環(huán)M次，則雙重循環(huán)的時間復(fù)雜度就是O(M×N)。類比算法1，算法2 中第4）步構(gòu)建QX和QL的時間復(fù)雜度均為max(M，N)，同時第6）步中用戶遍歷QX和QL，即MAP 的算法復(fù)雜度為O(max(M，N))。

4.2 數(shù)據(jù)隱私性

定理2算法CS-MVP 的一組發(fā)布數(shù)據(jù)對其原始感知數(shù)據(jù)滿足隱私預(yù)算為ε的LDP約束。

證明 依據(jù)隨機(jī)轉(zhuǎn)移矩陣，可得發(fā)布數(shù)據(jù)中任意r'∈R來自于原始感知數(shù)據(jù)r∈R的轉(zhuǎn)移概率P(r'|r)，

定理3算法CS-MAP 的一組發(fā)布數(shù)據(jù)對其原始感知數(shù)據(jù)的位置數(shù)據(jù)和感知結(jié)果屬性分別滿足ε的LDP約束。

證明 發(fā)布數(shù)據(jù)中任意r'=∈R，由原始感知數(shù)據(jù)變換來的轉(zhuǎn)移概率為：

其為原始感知數(shù)據(jù)中任務(wù)位置屬性到la的轉(zhuǎn)移概率，可知對于任意原始數(shù)據(jù)中位置屬性數(shù)據(jù)li(lj∈L)滿足：

對于任意原始感知數(shù)據(jù)中感知結(jié)果屬性數(shù)據(jù)xi，xj∈X滿足：

定理4算法CS-MAP的任意發(fā)布數(shù)據(jù)r'∈R對其原始感知數(shù)據(jù)r∈RT滿足隱私預(yù)算為ε+ln(min(M，N) -1)的LDP隱私約束。

存在如下等式：

概率比的滿足如下：

4.3 數(shù)據(jù)可用性

對于最優(yōu)機(jī)制，不同任務(wù)之間的數(shù)據(jù)不受任務(wù)實(shí)際數(shù)據(jù)如何取值影響，即對任意任務(wù)所有可能取值，由其他任務(wù)變換而來的概率應(yīng)相同。公式如下：

5 實(shí)驗(yàn)與結(jié)果分析

基于Python 環(huán)境使用真實(shí)數(shù)據(jù)集GeoLife［23］對算法進(jìn)行性能評估。GeoLife 數(shù)據(jù)集是由微軟亞洲研究院于2016 年發(fā)布的北京地區(qū)的軌跡信息，其中主要包含182 個移動設(shè)備的17 621 個軌跡數(shù)據(jù)。將統(tǒng)計(jì)相同時間段和一定區(qū)域范圍內(nèi)的設(shè)備數(shù)量作為感知任務(wù)，共提取出1 134個感知任務(wù)與感知數(shù)據(jù)對。同時實(shí)現(xiàn)了LoPub和PrivKV算法作為對比。

感知數(shù)據(jù)的可用性表現(xiàn)為真實(shí)數(shù)據(jù)與噪聲數(shù)據(jù)生成概率的差值，隨著樣本量增大，概率接近于數(shù)據(jù)頻率。可用性越大，正確數(shù)據(jù)與錯誤數(shù)據(jù)的概率差值越大，即樣本頻率差值越大。即可用性越高，計(jì)算獲得真實(shí)感知數(shù)據(jù)所需的用戶提交數(shù)據(jù)數(shù)量越少。定義數(shù)據(jù)樣本比（Data Sample Ratio，DSR）為所有任務(wù)獲得的感知數(shù)據(jù)的平均個數(shù)。實(shí)驗(yàn)驗(yàn)證在不同隱私預(yù)算和DSR 下，計(jì)算感知數(shù)據(jù)的準(zhǔn)確率。使用0-1 損失函數(shù)來度量統(tǒng)計(jì)值和原始值的誤差。

任務(wù)的平均數(shù)據(jù)準(zhǔn)確率記作：

將隱私預(yù)算控制在［0，10］，DSR 控制在［0，5 000］。對實(shí)驗(yàn)中的每個狀態(tài)均計(jì)算10次結(jié)果后取均值。

首先分析在不同DSR 和不同隱私預(yù)算下，CS-MVP 和CSMAP算法的平均數(shù)據(jù)準(zhǔn)確性，驗(yàn)證算法的適用范圍。

如圖3 所示，當(dāng)隱私預(yù)算大于3.5，每個任務(wù)平均采集數(shù)據(jù)量大于300 時，CS-MVP 算法恢復(fù)任務(wù)結(jié)果的準(zhǔn)確性大于95%；在隱私預(yù)算大于2，每個任務(wù)平均數(shù)據(jù)采集量大于200時，CS-MAP 算法恢復(fù)任務(wù)結(jié)果的準(zhǔn)確性大于95%。CS-MAP算法比CS-MVP 算法具有更大的隱私預(yù)算適用范圍，且在相同隱私約束下，需要采集的數(shù)據(jù)量更少。

圖3 CS-MVP和CS-MAP算法生成數(shù)據(jù)的平均準(zhǔn)確率Fig.3 Average accuracies of data generated by CS-MVP and CS-MAP algorithms

利用CS-MVP 和CS-MAP 算法順序隱私化處理多個數(shù)據(jù)，對比運(yùn)行時間，每次實(shí)驗(yàn)統(tǒng)計(jì)10 次處理時間取平均值，實(shí)驗(yàn)結(jié)果如表1所示。從表1可看出，兩算法的運(yùn)行時間隨著數(shù)據(jù)量的增加差距逐漸增大。在數(shù)據(jù)量為1 000 以內(nèi)時，CS-MAP算法的運(yùn)行時間0.04 s以下，而CS-MVP算法的運(yùn)行時間最長已超過20 s。屬性獨(dú)立的隨機(jī)算法可顯著降低算法的運(yùn)行時間。

表1 CS-MVP和CS-MAP算法的平均運(yùn)行時間Tab.1 Average running times of CS-MVP and CS-MAP algorithms

實(shí)驗(yàn)過程中實(shí)現(xiàn)了LoPub 和PrivKV 算法來對比CS-MVP算法的性能。分別在隱私預(yù)算ε=2，4，6 三種情況下，對比CS-MVP、CS-MAP、LoPub 和PrivKV 四種算法隨著DSR 增加生成數(shù)據(jù)的準(zhǔn)確性。

如圖4 所示，隨著數(shù)據(jù)量的增多各算法生成數(shù)據(jù)的準(zhǔn)確性逐漸增加；對滿足LDP 的隱私保護(hù)算法，隱私預(yù)算增加，隱私性降低，數(shù)據(jù)可用性增加，圖4 中體現(xiàn)在隨著隱私預(yù)算的增加，在數(shù)據(jù)達(dá)到相同隱私預(yù)算下，需要的DSR越小。

從圖4 可明顯看出，在相同條件下，CS-MAP 算法的準(zhǔn)確性大于CS-MVP 算法和PrivKV 算法的準(zhǔn)確性。在隱私預(yù)算ε≥2 時，CS-MVP 算法的準(zhǔn)確性比PrivKV 平均高40%。原因在于：PrivKV是對數(shù)據(jù)進(jìn)行二值差分隱私擾動，其發(fā)布值的隱私空間小，在隱私性低的情況下能保持較高的可用性；而CSMVP 機(jī)制的發(fā)布空間為感知數(shù)據(jù)所有可取值空間，發(fā)布值取錯誤值的概率更大。整體來看，CS-MVP直接從提交數(shù)據(jù)中計(jì)算兩個屬性數(shù)據(jù)間的對應(yīng)關(guān)系，而PrivKV 需要統(tǒng)計(jì)頻次計(jì)算分布來得出真實(shí)值，因此需要更多的數(shù)據(jù)量來支撐。

在隱私預(yù)算為2 和4 時，CS-MVP 算法的數(shù)據(jù)準(zhǔn)確性比LoPub 高30%；在隱私預(yù)算為6 時CS-MVP 算法略低于LoPub算法，其原因在于LoPub 算法發(fā)布值的取值空間也為感知數(shù)據(jù)的所有取值，在隱私預(yù)算小時，可用性較低，且需要計(jì)算數(shù)據(jù)的整體分布，然后從中再恢復(fù)對應(yīng)關(guān)系，因此需要的數(shù)據(jù)量較多，在相同數(shù)據(jù)量下，準(zhǔn)確性低于CS-MVP。兩種算法的準(zhǔn)確率在隱私預(yù)算增大時表現(xiàn)得逐漸相等，如圖4（c），但LoPub算法需要多次迭代操作來逼近結(jié)果，算法復(fù)雜度要遠(yuǎn)大于CSMVP。圖4（b）中在樣本量大于20 后，CS-MVP 的準(zhǔn)確性大于LoPub，其原因在于，LoPub是利用EM（Expectation Maximization）算法計(jì)算分布，EM 算法迭代過程中預(yù)設(shè)初始分布為均勻分布，群智感知結(jié)果分布與均勻分布相差較大，計(jì)算的任務(wù)數(shù)據(jù)準(zhǔn)確率較低。

圖4 CS-MAP、CS-MVP、PrivKV、LoPub生成數(shù)據(jù)的準(zhǔn)確性對比Fig.4 Accuracy comparison of CS-MAP，CS-MVP，PrivKV，LoPub generated data

最后，CS-MAP的算法的數(shù)據(jù)準(zhǔn)確率在三種情況下均大于其他三個算法，且在較低的隱私預(yù)算下也能保持較高的數(shù)據(jù)準(zhǔn)確性。原因在于該算法發(fā)布值的空間只在每個屬性的各自獨(dú)立空間中，且直接保留了位置和感知結(jié)果的對應(yīng)關(guān)系。從圖4 可知，CS-MAP 算法比LoPub 算法的數(shù)據(jù)準(zhǔn)確率平均提高了26.94%，比PrivKV 算法平均提高了84.34%；CS-MVP 算法比LoPub算法平均提高了66.24%，比PrivKV 算法平均提高了144.14%。

接下來驗(yàn)證邊緣計(jì)算模式支持下隱私保護(hù)的MCS 系統(tǒng)感知開銷。保持用戶提交的感知數(shù)據(jù)量不變，分析網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量。記Ce為邊緣計(jì)算支持下的傳輸數(shù)據(jù)量，Cc為不引入邊緣計(jì)算模式時的傳輸數(shù)據(jù)量。傳輸數(shù)據(jù)降低比記作：

在保證感知數(shù)據(jù)恢復(fù)準(zhǔn)確性大于95%的情況下，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 邊緣計(jì)算模式對MCS系統(tǒng)數(shù)據(jù)傳輸量的影響Fig.5 Influence of edge computing mode on data transmission amount in MCS system

從圖5 可知，隨著提交數(shù)據(jù)總量的提升，邊緣計(jì)算可顯著減少數(shù)據(jù)傳輸量。邊緣計(jì)算服務(wù)器匯聚所有隱私算法生成的發(fā)布數(shù)據(jù)，忽略隨機(jī)算法生成的錯誤數(shù)據(jù)，只向云端傳輸實(shí)際任務(wù)數(shù)據(jù)，當(dāng)平均任務(wù)數(shù)據(jù)DSR 大于10 時，對每個任務(wù)采集10 個以上的感知數(shù)據(jù)，而只向云端傳輸一個數(shù)據(jù)，可降低90%網(wǎng)絡(luò)中的數(shù)據(jù)量，這與實(shí)驗(yàn)結(jié)果相符合。

6 結(jié)語

本文針對MCS 用戶數(shù)據(jù)提交階段隱私保護(hù)困難和因隱私保護(hù)帶來的成本增加問題，建立了用戶提交數(shù)據(jù)的隱私性和任務(wù)數(shù)據(jù)可用性模型，設(shè)計(jì)了基于用戶提交數(shù)據(jù)屬性關(guān)系的CS-MVP 算法和CS-MAP 算法。在MCS 中引入邊緣計(jì)算架構(gòu)，設(shè)計(jì)了邊緣計(jì)算支持下的隱私化MCS 系統(tǒng)感知模式。針對MCS 用戶提交數(shù)據(jù)可用性的下界進(jìn)行理論分析，證明CSMVP 算法在數(shù)據(jù)屬性聯(lián)合隱私約束下的最優(yōu)性，CS-MAP 算法在數(shù)據(jù)屬性獨(dú)立隱私約束下的最優(yōu)性，并定量給出CS-MVP和CS-MAP 算法生成數(shù)據(jù)的可用性。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的LoPub 和PrivKV 算法相比，在相同隱私預(yù)算下，CS-MVP 和CS-MAP 算法擁有更高的數(shù)據(jù)準(zhǔn)確性和更低的數(shù)據(jù)量需求。CS-MAP 算法較之CS-MVP 算法擁有更高的數(shù)據(jù)可用性和更低的算法復(fù)雜度，但其隱私約束局限于一組任務(wù)數(shù)據(jù)，對存在多組感知數(shù)據(jù)的用戶數(shù)據(jù)不滿足隱私約束。邊緣計(jì)算的引入可減低MCS 系統(tǒng)中90%的數(shù)據(jù)傳輸量。在當(dāng)前工作的基礎(chǔ)上，未來擬開展隱私保護(hù)下的MCS 任務(wù)分發(fā)和激勵機(jī)制的優(yōu)化研究。