面向移動(dòng)群智感知的兩階段位置隱私保護(hù)方法

王 輝, 畢成玉, 申自浩, 劉沛騫

(1. 河南理工大學(xué) 軟件學(xué)院, 河南 焦作 454000;2. 河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 河南 焦作 454000)

隨著無線傳感網(wǎng)絡(luò)和定位技術(shù)的發(fā)展, 移動(dòng)群智感知(mobile crowd sensing, MCS)[1]已成為一種新興的分布式智能感知范式. MCS不需要預(yù)先部署靜態(tài)傳感網(wǎng)絡(luò), 工人手持配備傳感器的智能設(shè)備即可快速、 高效地收集感知數(shù)據(jù), 目前已廣泛應(yīng)用于環(huán)境監(jiān)測、 氣象預(yù)測和社交推薦等領(lǐng)域[2-3].

近年來關(guān)于MCS的研究已有很多結(jié)果. 在任務(wù)分配階段, Akter等[4]提出了一種禁忌搜索TST(tabu search algorithm for task allocation)任務(wù)分配算法減少工人的移動(dòng)距離, 但該算法需要工人提交真實(shí)位置數(shù)據(jù), 存在隱私泄露風(fēng)險(xiǎn). 隨著基于位置服務(wù)中位置隱私保護(hù)研究[5]的發(fā)展, 研究者們開始關(guān)注MCS中的位置隱私保護(hù)[6]. 為保護(hù)任務(wù)分配過程中工人的位置隱私, Song等[7]基于差分隱私(differential privacy, DP)[8]將工人位置的坐標(biāo)轉(zhuǎn)換為極坐標(biāo), 并對(duì)極坐標(biāo)的位置記錄執(zhí)行差分隱私轉(zhuǎn)換以保護(hù)工人的位置隱私, 但同時(shí)也影響了任務(wù)分配結(jié)果的準(zhǔn)確性, 導(dǎo)致任務(wù)完成率較低. 在數(shù)據(jù)上傳階段, 工人上傳到第三方平臺(tái)的感知數(shù)據(jù)中不可避免地包含自身真實(shí)位置數(shù)據(jù). 為保護(hù)工人在數(shù)據(jù)上傳階段的位置隱私, 李卓等[9]基于本地差分隱私(local differential privacy, LDP)[10]設(shè)計(jì)了用戶提交數(shù)據(jù)屬性聯(lián)合隱私保護(hù)的CS-MVP算法, 將個(gè)體位置數(shù)據(jù)隨機(jī)化, 擾亂了數(shù)據(jù)整體分布以保護(hù)位置隱私, 但當(dāng)敵手有足夠的先驗(yàn)知識(shí)時(shí)就會(huì)減弱隱私保護(hù)效果. 也有使用L-多樣性、K-匿名[11]等泛化方法對(duì)位置數(shù)據(jù)進(jìn)行模糊處理, 使第三方無法恢復(fù)數(shù)據(jù), 從而無法區(qū)分個(gè)體以達(dá)到位置隱私保護(hù)的目的, 但同時(shí)導(dǎo)致較高的服務(wù)質(zhì)量損失. 考慮到傳統(tǒng)可信第三方平臺(tái)遭受惡意攻擊的隱私泄露風(fēng)險(xiǎn), 利用區(qū)塊鏈[12]的匿名性和不可篡改性, Yang等[13]提出了一個(gè)基于區(qū)塊鏈的分布式群智感知系統(tǒng)模型, 解決了依賴可信第三方的問題, 但區(qū)塊鏈的透明機(jī)制不利于工人的位置隱私, 無法抵擋來自工人間的協(xié)作攻擊和先驗(yàn)知識(shí)攻擊.

針對(duì)上述問題, 本文設(shè)計(jì)一個(gè)結(jié)合區(qū)塊鏈和邊緣計(jì)算的移動(dòng)群智感知(blockchain and edge computing-mobile crowdsensing, BE-MCS)系統(tǒng)模型, 避免使用第三方平臺(tái), 并針對(duì)工人需上傳自身真實(shí)位置數(shù)據(jù)的兩個(gè)階段設(shè)計(jì)不同的算法. 結(jié)果表明, 該模型在保護(hù)工人位置隱私的同時(shí)取得了較高的任務(wù)完成率和較低的服務(wù)質(zhì)量損失.

1 系統(tǒng)模型

圖1為結(jié)合了區(qū)塊鏈和邊緣計(jì)算的BE-MCS系統(tǒng)模型. 該模型邊緣節(jié)點(diǎn)被視為是半可信的, 其中包含4個(gè)角色:

圖1 BE-MCS系統(tǒng)模型Fig.1 BE-MCS system model

1) 任務(wù)請(qǐng)求者. 任務(wù)請(qǐng)求者在區(qū)塊鏈中通過P2P通信將任務(wù)信息發(fā)送給邊緣節(jié)點(diǎn), 等待其回傳感知數(shù)據(jù);

2) 邊緣節(jié)點(diǎn). 邊緣節(jié)點(diǎn)是分布在感知區(qū)域中的邊緣設(shè)備, 是區(qū)塊鏈的鏈上節(jié)點(diǎn), 收到任務(wù)請(qǐng)求者發(fā)送的任務(wù)后通過區(qū)塊鏈的廣播機(jī)制向感知區(qū)域內(nèi)的工人發(fā)送任務(wù)信息, 協(xié)作完成任務(wù)分配并收集和匯總工人上傳的感知數(shù)據(jù), 處理后發(fā)送給任務(wù)請(qǐng)求者;

3) 工人. 工人向邊緣節(jié)點(diǎn)提交自身關(guān)于位置的信息獲取感知任務(wù), 執(zhí)行感知任務(wù)后將感知數(shù)據(jù)上傳到邊緣節(jié)點(diǎn);

4) 區(qū)塊鏈. 區(qū)塊鏈取代第三方平臺(tái), 利用智能合約作為感知過程提供通信和存儲(chǔ)等功能, 通過合法性驗(yàn)證將交易信息記錄在分布式賬本中.

2 兩階段位置隱私保護(hù)方法

2.1 隱私保護(hù)任務(wù)分配

考慮工人移動(dòng)速度差異對(duì)任務(wù)完成率的影響, 使用工人到任務(wù)的行程時(shí)間作為衡量指標(biāo). 任務(wù)分配流程簡述如下:

1) 任務(wù)請(qǐng)求者將發(fā)布一系列任務(wù)T={t1,t2,…,tm},T中的每個(gè)任務(wù)ti通過Paillier密碼機(jī)制[14]分配一對(duì)公私密鑰對(duì)(pki,ski), 即公鑰pki和私鑰ski, 然后在區(qū)塊鏈中通過P2P通信將任務(wù)ti的公鑰分發(fā)送任務(wù)所在區(qū)域中的邊緣節(jié)點(diǎn)EN, 而將私鑰發(fā)送給最接近EN的邊緣節(jié)點(diǎn)EN′;

2) 邊緣節(jié)點(diǎn)收到任務(wù)信息后, 將向其感知區(qū)域內(nèi)的所有工人發(fā)布任務(wù)ti的公鑰pki;

3) 工人用任務(wù)的公鑰pki解密任務(wù)信息, 根據(jù)自身位置和移動(dòng)速度計(jì)算他們到達(dá)任務(wù)ti的行程時(shí)間, 并使用公鑰pki加密行程時(shí)間, 然后將加密的行程時(shí)間上傳到任務(wù)ti所在的邊緣節(jié)點(diǎn)EN;

4) 邊緣節(jié)點(diǎn)EN接收到加密行程時(shí)間后, 與擁有任務(wù)ti私鑰ski的邊緣節(jié)點(diǎn)EN′協(xié)同,EN將通過密文差值計(jì)算選出行程時(shí)間最短的幾位工人, 將任務(wù)分配給他們.

下面給出邊緣節(jié)點(diǎn)之間如何協(xié)作計(jì)算工人的密文行程時(shí)間差.首先基于同態(tài)加密利用Paillier加密算法的加法同態(tài)性, 設(shè)計(jì)一種密文差值計(jì)算實(shí)現(xiàn)工人之間加密時(shí)間的比較.假設(shè)加密函數(shù)是E(x), 解密函數(shù)是D(x),c1和c2分別是明文p1,p2的密文, 則根據(jù)加法同態(tài), 對(duì)于明文p1,p2, 有

D(c1×c2)=D(E(p1)×E(p2)) modn2=(p1+p2) modn.

(1)

D(c1?c2)=D(E(p1)×E(p2)-1) modn2=(p1-p2) modn,

(2)

式(2)可通過計(jì)算密文差值計(jì)算實(shí)際明文的差值, 而無需解密明文.

對(duì)于明文p1,p2, 由E(p,r)=gp·rnmodn2可得

(3)

則密文下的行程時(shí)間差為

最后c1?c2用私鑰解密, 得到明文下的差值為

D(c1?c2)=D(E(p1,r1)×E(p2,r2)-1)=p1-p2.

(5)

(6)

算法1CTWS算法.

輸出: 選擇出的工人集Wi;

步驟1)Wi←?;

步驟2) ifk>0 then

步驟3)k←n;

步驟4) end if

步驟5) whilep=1 tokdo

步驟6)wmin←null

步驟7) forq=pton-1 do

步驟10) else

步驟12) end if

步驟13) end for

步驟14)Wi←Wi∪wmin;

步驟16) end while

步驟17) returnWi.

2.2 隱私保護(hù)數(shù)據(jù)上傳

在數(shù)據(jù)上傳階段, 由于感知數(shù)據(jù)中不可避免地包含真實(shí)位置數(shù)據(jù), 因此本文通過采用雙擾動(dòng)的差分隱私算法(two disturbance local differential privacy, TDLDP)對(duì)感知數(shù)據(jù)中的位置數(shù)據(jù)進(jìn)行擾動(dòng)以保護(hù)工人的位置隱私. 即使敵手獲取了工人的隱私信息, 這些數(shù)據(jù)也是不真實(shí)的.

定義1(ε-LDP) 給定n個(gè)用戶, 每個(gè)用戶對(duì)應(yīng)一條記錄, 給定一個(gè)隱私保護(hù)算法M及其定義域Dom(M)和值域Ran(M), 如果算法M在任意兩條記錄t和t′(t,t′∈Dom(M))上得到相同的輸出結(jié)果t*(t*∈Ran(M)), 且滿足

Pr[M(t)=t*]≤eε×Pr[M(t′)=t*],

(7)

則稱M滿足ε-LDP.

由定義1可見, LDP通過控制任意兩條記錄輸出結(jié)果的相似度確保算法M滿足ε-LDP. 隱私預(yù)算參數(shù)ε表示隱私的保護(hù)程度,ε越小, 隱私保護(hù)程度越高.即根據(jù)隱私算法M的某個(gè)輸出結(jié)果, 敵手很難推斷出輸入數(shù)據(jù)是哪條記錄.對(duì)于LDP, 每個(gè)用戶都可以自己處理數(shù)據(jù), 即隱私數(shù)據(jù)的處理過程從第三方轉(zhuǎn)移到每個(gè)用戶.因此, 無需考慮第三方的可信度.

性質(zhì)2給定一個(gè)數(shù)據(jù)集C, 將其劃分為n個(gè)不相交的子集,C={C1,C2,…,Cn}, 設(shè)M為滿足ε-LDP的任意隱私預(yù)算, 則算法M滿足C={C1,C2,…,Cn}上的ε-LDP.

雖然LDP機(jī)制在一定程度上限制了敵手竊取工人的位置數(shù)據(jù), 但工人仍無法確定他們的位置數(shù)據(jù)是否已經(jīng)被泄露. 因此, 通過在LDP機(jī)制中添加干擾因子ω, 可進(jìn)一步保護(hù)工人的位置數(shù)據(jù). LDP的隱私保護(hù)原理就是使敵手很難分辨出工人的真實(shí)位置, 但如果敵手有足夠的先驗(yàn)知識(shí)推測工人的位置數(shù)據(jù), 則LDP保護(hù)機(jī)制效果就會(huì)減弱, 但添加擾動(dòng)因子ω使敵手始終無法正確預(yù)估工人的位置數(shù)據(jù), 從而保護(hù)工作者的位置隱私.

(8)

(9)

定義2(ω-干擾因子) 概率混淆矩陣P滿足ω-干擾因子表示為

(10)

結(jié)合定義1和定義2, 本文位置數(shù)據(jù)擾動(dòng)算法如下.

算法2TDLDP算法.

輸入:ε,ω,W,Lt;

輸出: 位置集合L←{Lt,Lf};

步驟1) for eachwiinWdo

步驟2)wi加載其真實(shí)位置數(shù)據(jù)li

步驟6) end for

步驟9) end for

步驟10) returnL←{Lt,Lf}.

3 隱私安全分析

本文方案中, 唯一與工人交互位置數(shù)據(jù)的是邊緣節(jié)點(diǎn).下面通過證明在兩個(gè)階段邊緣節(jié)點(diǎn)始終無法獲得工人的真實(shí)數(shù)據(jù)以證明該方案的安全性.

3.1 任務(wù)分配階段

命題1任務(wù)分配階段, 由于任務(wù)分配是在密文下進(jìn)行的, 所以邊緣節(jié)點(diǎn)無法獲得工人的真實(shí)位置信息.

證明: 在任務(wù)分配階段, 當(dāng)邊緣節(jié)點(diǎn)對(duì)加密行程時(shí)間進(jìn)行比較和排序時(shí), 上述定義的密文計(jì)算的差值基于Paillier加密機(jī)制的加法同態(tài), 該機(jī)制已經(jīng)被證明在語義上是安全的, 并可以抵抗選擇明文攻擊. 這種基于密文的計(jì)算不允許邊緣節(jié)點(diǎn)獲取任何有效信息. 對(duì)于密文c1和c2, 計(jì)算差值:

D(c1?c2)=D(E(p1,r1)×E(p2,r2)-1)=p1-p2,

(11)

(12)

邊緣節(jié)點(diǎn)EN通過EN′返回的查詢結(jié)果1或0判斷兩個(gè)用戶之間的行程時(shí)間差值, 但無法知道明文p1,p2的真實(shí)值.密鑰管理邊緣節(jié)點(diǎn)EN′每次只是根據(jù)請(qǐng)求解密密文差值, 也無法從中獲取任何真實(shí)的位置信息.此外, 假設(shè)兩個(gè)邊緣節(jié)點(diǎn)相互勾結(jié)也只能獲得工人到任務(wù)位置的行程時(shí)間值, 由于工人的速度未知, 還是無法推測出工人的真實(shí)位置.

3.2 數(shù)據(jù)上傳階段

命題2在數(shù)據(jù)上傳階段, 由于工人在上傳感知數(shù)據(jù)前對(duì)位置數(shù)據(jù)進(jìn)行了擾動(dòng), 所以邊緣節(jié)點(diǎn)無法獲得工人的真實(shí)位置信息.

證明: 由于在隱私保護(hù)方面滿足ε-LDP的算法已經(jīng)證明了其隱私保護(hù)能力, 所以只需證明算法2滿足ε-LDP. 目前, LDP的主流擾動(dòng)機(jī)制是隨機(jī)響應(yīng)機(jī)制, 根據(jù)隨機(jī)響應(yīng)機(jī)制給出的LDP的隱私參數(shù)ε, 每個(gè)工人發(fā)送自己真實(shí)位置或(n-1)個(gè)虛假位置的概率表示為

(13)

根據(jù)定義1, 如果

(14)

為真, 則算法2滿足性質(zhì)1和性質(zhì)2以及ε-LDP, 其中N表示所有移動(dòng)工人的總數(shù).如果N包含x個(gè)位置, 則只有一個(gè)位置是工作人員的真實(shí)位置, 干擾位置為(x-1)個(gè).根據(jù)生成規(guī)則, 工人發(fā)送真實(shí)位置的概率表示為

(15)

發(fā)送干擾位置的概率為

(16)

則

(17)

成立.因此, 算法2滿足性質(zhì)1和性質(zhì)2以及ε-LDP.

4 仿真實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

在仿真實(shí)驗(yàn)中, 設(shè)置一個(gè)50 km×50 km的感知區(qū)域, 在整個(gè)感知區(qū)域內(nèi)設(shè)置10個(gè)邊緣節(jié)點(diǎn), 并將其劃分為10個(gè)較小的感知區(qū)域. 在整個(gè)感知區(qū)域內(nèi)隨機(jī)生成任務(wù)和工人的位置, 區(qū)域內(nèi)任務(wù)數(shù)量為50～100, 用戶數(shù)量為150～300. 同時(shí)考慮到工人移動(dòng)速度的不同, 結(jié)合實(shí)際應(yīng)用中的真實(shí)速度值, 按照比例隨機(jī)給工人速度賦值, 即步行速度5 km/h, 騎行速度10 km/h, 駕車速度30 km/h, 賦值比例為3∶5∶2. 本文所有實(shí)驗(yàn)程序均在MATLAB R2020a平臺(tái)上使用MATLAB語言進(jìn)行仿真. 所有實(shí)驗(yàn)的硬件環(huán)境為Windows10 64位操作系統(tǒng), Intel(R) Core(TM) i7-12700F CPU @ 2.1 GHz, 16 GB RAM.

4.2 仿真結(jié)果分析

4.2.1 任務(wù)分配階段性能評(píng)估

任務(wù)完成率(task completion rate, TCR)是指在任務(wù)規(guī)定行程時(shí)間前完成任務(wù)占所有任務(wù)的比例, 是評(píng)價(jià)任務(wù)分配方法的一個(gè)重要指標(biāo). 將CTWS與未保護(hù)工人位置隱私的任務(wù)分配算法TST[4]、 用加噪方式的任務(wù)分配方法(DPTA)[8]進(jìn)行對(duì)比, 結(jié)果如圖2所示.

圖2 不同算法任務(wù)完成率對(duì)比Fig.2 Comparison of task completion rates of different algorithms

由圖2(A)可見, 工人數(shù)量固定為200, 所有算法的TCR隨著任務(wù)數(shù)的增加均有所下降. 因?yàn)槊總€(gè)工人只能執(zhí)行一項(xiàng)任務(wù)時(shí), 任務(wù)越多, 在規(guī)定行程時(shí)間內(nèi)完成一項(xiàng)任務(wù)的概率就越小. DPTA的任務(wù)完成率始終最低, 因?yàn)镈PTA在任務(wù)分配時(shí)根據(jù)上傳加噪的行程距離, 導(dǎo)致任務(wù)完成率較低. CTWS算法略優(yōu)于TST, 因?yàn)樗腔谛谐虝r(shí)間的任務(wù)分配算法, 同時(shí)也表明本文方案可以在不泄露工人真實(shí)位置的情況下實(shí)現(xiàn)最優(yōu)的任務(wù)分配. 由圖2(B)可見, 任務(wù)數(shù)固定為80, 隨著工人數(shù)量的增加, 3種方案的TCR都在增加, 但增速逐漸放緩. CTWS算法總體優(yōu)于另外兩種算法, 這是因?yàn)镃TWS算法在進(jìn)行任務(wù)分配時(shí)的衡量指標(biāo)即為行程時(shí)間, 可以使任務(wù)總用時(shí)最少, 所以在不同的比較實(shí)驗(yàn)中能夠保持更高的任務(wù)完成率, 而另外兩種算法用行程距離作為主要指標(biāo)進(jìn)行任務(wù)分配.

4.2.2 數(shù)據(jù)上傳階段性能評(píng)估

(18)

在K-匿名機(jī)制[11]中, 工人的QL被視為工人的真實(shí)位置li與其公布的中心位置之間的誤差距離.假設(shè)有N個(gè)工人, 則K-匿名機(jī)制的QL表示為

(19)

其中l(wèi)ic表示工人wi發(fā)布的中心位置.

圖3(A)為在相同隱私保護(hù)強(qiáng)度不同工人數(shù)量下的質(zhì)量損失比較結(jié)果. 由圖3(A)可見, 隨著工人數(shù)量的不斷增加, 每種隱私保護(hù)機(jī)制的QL都會(huì)增加,K-匿名機(jī)制的QL最嚴(yán)重. 雖然CS-MVP的QL很少, 但TDLDP算法的QL更少. 因此TDLDP算法的性能優(yōu)于其他算法. 圖3(B)為在相同工人數(shù)量不同隱私保護(hù)強(qiáng)度下QL的比較結(jié)果, 其中隨機(jī)生成150名工人的位置信息作為實(shí)驗(yàn)的真實(shí)位置. 由圖3(B)可見, 隨著隱私級(jí)別的不斷提高, 3種算法的QL都在逐漸增加. 但TDLDP中加入了干擾因子使得QL最小, 因此在服務(wù)質(zhì)量損失方面的性能優(yōu)于其他算法.

圖3 不同算法服務(wù)質(zhì)量損失對(duì)比Fig.3 Comparison of service quality loss of different algorithms

綜上所述, 本文基于群智感知中工人兩次需要提交自身真實(shí)位置的兩個(gè)階段, 給出了結(jié)合區(qū)塊鏈和邊緣計(jì)算的系統(tǒng)模型, 避免使用中心化第三方平臺(tái), 并且有針對(duì)性地對(duì)兩階段提出了不同的位置隱私保護(hù)方法. 在任務(wù)分配階段, 考慮到工人移動(dòng)速度的差異, 用工人到任務(wù)位置的行程時(shí)間作為任務(wù)分配指標(biāo). 基于同態(tài)加密在密文下通過邊緣節(jié)點(diǎn)的協(xié)作完成任務(wù)分配, 并針對(duì)多任務(wù)分配場景進(jìn)行優(yōu)化使任務(wù)總行程時(shí)間最短, 在保護(hù)工人位置隱私的同時(shí)保證了較高的任務(wù)完成率. 在數(shù)據(jù)上傳階段, 差分隱私和干擾因子的結(jié)合使得工人可以在上傳感知數(shù)據(jù)前在本地對(duì)位置數(shù)據(jù)進(jìn)行干擾, 在保護(hù)工人位置隱私的同時(shí)保證了較低的服務(wù)質(zhì)量損失.