面向移動群智感知的兩階段位置隱私保護方法

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

(1. 河南理工大學 軟件學院, 河南 焦作 454000;2. 河南理工大學 計算機科學與技術學院, 河南 焦作 454000)

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

2 兩階段位置隱私保護方法

2.1 隱私保護任務分配

考慮工人移動速度差異對任務完成率的影響, 使用工人到任務的行程時間作為衡量指標. 任務分配流程簡述如下:

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

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

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

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

下面給出邊緣節(jié)點之間如何協(xié)作計算工人的密文行程時間差.首先基于同態(tài)加密利用Paillier加密算法的加法同態(tài)性, 設計一種密文差值計算實現(xiàn)工人之間加密時間的比較.假設加密函數(shù)是E(x), 解密函數(shù)是D(x),c1和c2分別是明文p1,p2的密文, 則根據(jù)加法同態(tài), 對于明文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)可通過計算密文差值計算實際明文的差值, 而無需解密明文.

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

(3)

則密文下的行程時間差為

最后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 隱私保護數(shù)據(jù)上傳

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

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

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

(7)

則稱M滿足ε-LDP.

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

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

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

(8)

(9)

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

(10)

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

算法2TDLDP算法.

輸入:ε,ω,W,Lt;

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

步驟1) for eachwiinWdo

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

步驟6) end for

步驟9) end for

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

3 隱私安全分析

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

3.1 任務分配階段

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

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

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

(11)

(12)

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

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

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

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

(13)

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

(14)

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

(15)

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

(16)

則

(17)

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

4 仿真實驗分析

4.1 實驗設置

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

4.2 仿真結果分析

4.2.1 任務分配階段性能評估

任務完成率(task completion rate, TCR)是指在任務規(guī)定行程時間前完成任務占所有任務的比例, 是評價任務分配方法的一個重要指標. 將CTWS與未保護工人位置隱私的任務分配算法TST[4]、 用加噪方式的任務分配方法(DPTA)[8]進行對比, 結果如圖2所示.

圖2 不同算法任務完成率對比Fig.2 Comparison of task completion rates of different algorithms

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

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

(18)

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

(19)

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

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

圖3 不同算法服務質量損失對比Fig.3 Comparison of service quality loss of different algorithms

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