邊緣計(jì)算支持下的移動(dòng)群智感知本地差分隱私保護(hù)機(jī)制

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

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

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

0 引言

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

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

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

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

2 模型定義

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

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

首先將用戶(hù)采提交據(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)，則任意用戶(hù)ui的提交數(shù)據(jù)記作di=

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

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

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

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

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

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

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

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

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

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

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

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

2.4 隱私約束下的可用性最大問(wèn)題

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

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

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

為分離用戶(hù)和MCS 云服務(wù)器的直接交互，消除MCS 云服務(wù)器泄露用戶(hù)隱私的風(fēng)險(xiǎn)，在MCS 中引入邊緣計(jì)算架構(gòu)。同時(shí)，滿(mǎn)足LDP的隱私保護(hù)算法［17-20］對(duì)原始感知數(shù)據(jù)［21-22］隱私處理后會(huì)生成部分噪聲數(shù)據(jù)，隱私預(yù)算越高，提交數(shù)據(jù)中的噪聲數(shù)據(jù)越多，引入邊緣服務(wù)器，在靠近用戶(hù)端計(jì)算恢復(fù)出任務(wù)需求數(shù)據(jù)，過(guò)濾掉用戶(hù)提交數(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ù)器對(duì)用戶(hù)進(jìn)行任務(wù)分發(fā)，用戶(hù)執(zhí)行的具體感知任務(wù)對(duì)云服務(wù)器保持隱私性；任務(wù)提交階段，用戶(hù)首先利用滿(mǎn)足LDP的隱私保護(hù)算法，本地處理原始感知數(shù)據(jù)，然后提交隱私化的感知數(shù)據(jù)給邊緣服務(wù)器；邊緣服務(wù)器聚合所有用戶(hù)提交數(shù)據(jù)，通過(guò)統(tǒng)計(jì)計(jì)算恢復(fù)任務(wù)結(jié)果提交云服務(wù)器。

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

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

3.2 CS-MVP算法

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

設(shè)L中位置的數(shù)量為N，感知任務(wù)的取值范圍X的元素?cái)?shù)量為M，則集合R中的元素個(gè)數(shù)為M×N。屬性聯(lián)合的原始感知數(shù)據(jù)的取值范圍為RT，隱私化的用戶(hù)提交數(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)滿(mǎn)足以下約束：

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

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

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

求解可得：

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

圖2 基于隨機(jī)轉(zhuǎn)移矩陣的MCS用戶(hù)提交數(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é)果來(lái)構(gòu)建，在任務(wù)執(zhí)行前，邊緣服務(wù)器根據(jù)隱私預(yù)算，首先構(gòu)建完全隨機(jī)轉(zhuǎn)移矩陣QR，用戶(hù)在感知結(jié)束后選擇需要的行對(duì)原始感知數(shù)據(jù)隨機(jī)變換。隱私化的用戶(hù)感知流程為：

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

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

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

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

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

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

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

3.3 CS-MAP算法

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

仍針對(duì)上述場(chǎng)景，所有任務(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的元素分別為

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

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

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

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

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

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

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

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

4 理論分析

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

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

定理1CS-MVP 算法的時(shí)間復(fù)雜度為O(MN)，CS-MAP算法的時(shí)間復(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)的時(shí)間復(fù)雜度就是O(M×N)。類(lèi)比算法1，算法2 中第4）步構(gòu)建QX和QL的時(shí)間復(fù)雜度均為max(M，N)，同時(shí)第6）步中用戶(hù)遍歷QX和QL，即MAP 的算法復(fù)雜度為O(max(M，N))。

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

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

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

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

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

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

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

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

存在如下等式：

概率比的滿(mǎn)足如下：

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

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

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

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

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

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

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

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

如圖3 所示，當(dāng)隱私預(yù)算大于3.5，每個(gè)任務(wù)平均采集數(shù)據(jù)量大于300 時(shí)，CS-MVP 算法恢復(fù)任務(wù)結(jié)果的準(zhǔn)確性大于95%；在隱私預(yù)算大于2，每個(gè)任務(wù)平均數(shù)據(jù)采集量大于200時(shí)，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 算法順序隱私化處理多個(gè)數(shù)據(jù)，對(duì)比運(yùn)行時(shí)間，每次實(shí)驗(yàn)統(tǒng)計(jì)10 次處理時(shí)間取平均值，實(shí)驗(yàn)結(jié)果如表1所示。從表1可看出，兩算法的運(yùn)行時(shí)間隨著數(shù)據(jù)量的增加差距逐漸增大。在數(shù)據(jù)量為1 000 以?xún)?nèi)時(shí)，CS-MAP算法的運(yùn)行時(shí)間0.04 s以下，而CS-MVP算法的運(yùn)行時(shí)間最長(zhǎng)已超過(guò)20 s。屬性獨(dú)立的隨機(jī)算法可顯著降低算法的運(yùn)行時(shí)間。

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

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

如圖4 所示，隨著數(shù)據(jù)量的增多各算法生成數(shù)據(jù)的準(zhǔn)確性逐漸增加；對(duì)滿(mǎ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 時(shí)，CS-MVP 算法的準(zhǔn)確性比PrivKV 平均高40%。原因在于：PrivKV是對(duì)數(shù)據(jù)進(jìn)行二值差分隱私擾動(dòng)，其發(fā)布值的隱私空間小，在隱私性低的情況下能保持較高的可用性；而CSMVP 機(jī)制的發(fā)布空間為感知數(shù)據(jù)所有可取值空間，發(fā)布值取錯(cuò)誤值的概率更大。整體來(lái)看，CS-MVP直接從提交數(shù)據(jù)中計(jì)算兩個(gè)屬性數(shù)據(jù)間的對(duì)應(yīng)關(guān)系，而PrivKV 需要統(tǒng)計(jì)頻次計(jì)算分布來(lái)得出真實(shí)值，因此需要更多的數(shù)據(jù)量來(lái)支撐。

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

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

最后，CS-MAP的算法的數(shù)據(jù)準(zhǔn)確率在三種情況下均大于其他三個(gè)算法，且在較低的隱私預(yù)算下也能保持較高的數(shù)據(jù)準(zhǔn)確性。原因在于該算法發(fā)布值的空間只在每個(gè)屬性的各自獨(dú)立空間中，且直接保留了位置和感知結(jié)果的對(duì)應(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%。

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

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

圖5 邊緣計(jì)算模式對(duì)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ī)算法生成的錯(cuò)誤數(shù)據(jù)，只向云端傳輸實(shí)際任務(wù)數(shù)據(jù)，當(dāng)平均任務(wù)數(shù)據(jù)DSR 大于10 時(shí)，對(duì)每個(gè)任務(wù)采集10 個(gè)以上的感知數(shù)據(jù)，而只向云端傳輸一個(gè)數(shù)據(jù)，可降低90%網(wǎng)絡(luò)中的數(shù)據(jù)量，這與實(shí)驗(yàn)結(jié)果相符合。

6 結(jié)語(yǔ)

本文針對(duì)MCS 用戶(hù)數(shù)據(jù)提交階段隱私保護(hù)困難和因隱私保護(hù)帶來(lái)的成本增加問(wèn)題，建立了用戶(hù)提交數(shù)據(jù)的隱私性和任務(wù)數(shù)據(jù)可用性模型，設(shè)計(jì)了基于用戶(hù)提交數(shù)據(jù)屬性關(guān)系的CS-MVP 算法和CS-MAP 算法。在MCS 中引入邊緣計(jì)算架構(gòu)，設(shè)計(jì)了邊緣計(jì)算支持下的隱私化MCS 系統(tǒng)感知模式。針對(duì)MCS 用戶(hù)提交數(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ù)，對(duì)存在多組感知數(shù)據(jù)的用戶(hù)數(shù)據(jù)不滿(mǎn)足隱私約束。邊緣計(jì)算的引入可減低MCS 系統(tǒng)中90%的數(shù)據(jù)傳輸量。在當(dāng)前工作的基礎(chǔ)上，未來(lái)擬開(kāi)展隱私保護(hù)下的MCS 任務(wù)分發(fā)和激勵(lì)機(jī)制的優(yōu)化研究。