群智感知中基于維諾單元的隱私保護方法

龍 浩,張書奎,張 力

(1.蘇州大學 計算機科學與技術學院,江蘇 蘇州 215006;2.徐州工業職業技術學院 信息與電氣工程學院,江蘇 徐州 221002;3.江蘇省現代企業信息化應用支撐軟件工程技術研發中心,江蘇 蘇州 215104)

0 概述

在信息化時代,隨著智能手機的普及,移動群智感知應用得到迅速發展。移動用戶通過攜帶移動終端設備能夠在不同的位置監測到復雜的數據信息,比如噪音、天氣、大氣、交通。目前,研究人員已開發了大量移動感知應用,如環境檢測、交通監測、噪音監測等[1-2]。然而,在大多數情況下,感知任務需要參與者在不同位置獲得感知數據,參與者的位置信息很容易被暴露。由于隱私保護問題會影響用戶參與感知任務的積極性,因此保護參與者的位置隱私信息是群智感知應用研究的重要內容。

現有隱私保護方法利用多匿名機制來隱藏用戶的身份信息[3],然而惡意用戶通過獲得大量時空相關信息仍能夠推測出用戶的真實信息。文獻[4]通過將隨機噪音加入參與者位置信息中,使得惡意用戶很難分辨出參與者的真實位置信息,然而加擾的位置信息在恢復過程中容易出現失真情況。文獻[5]通過建立多匿名混沌區域來保護參與者的身份和位置信息,基于多個參與者組成混沌區域,然而該方法并沒有考慮到混沌區域用戶之間的協作問題,因此感知數據的傳輸效率受到較大影響。如何建立有效的混沌區域保障用戶隱私,并在混沌區域實現數據的有效傳輸是本文研究的主要內容。因此,本文在移動群智感知網絡中提出基于維諾單元的隱私保護方法(PP-Voronoi),參與者建立維諾單元,然后通過單跳或者多跳的方式廣播需求,聯合其他用戶建立混沌區域,并利用混沌區域的參與者代表與感知平臺進行數據交互,從而實現參與者的隱私保護。

1 相關工作

隱私保護是目前群智感知研究的重要內容,參與者在完成感知任務時會面臨隱私泄露的風險,由于考慮到隱私成本影響其參與感知任務的積極性,因此現有提出的隱私保護方法主要分為加密、匿名、感知位置隱藏和建立混沌區域4類方法。文獻[6-7]提出盲簽名和部分盲簽加密數據的隱私保護激勵機制,但是算法計算量均較大。文獻[8]采用TLC加密和匿名方法在參與者上傳競標與感知數據以及更新聲譽值3個階段進行隱私保護。文獻[9]對參與者敏感屬性進行隱私保護,根據敏感程度設計不同的敏感等級,實現個性化的隱私保護,然而惡意用戶仍能根據參與者上傳的感知數據推斷出參與者的位置信息。文獻[10]針對位置數據發布應用提出一種差異隱私保護算法,通過隱私位置聚類收縮來隱藏參與者的真實位置和訪問某個位置的頻率,該算法主要針對稀疏位置數據集,但由于其采用聚類方式,因此時間復雜度較高。文獻[11-12]通過空間區域的時延特點為用戶增加虛擬位置和用戶信息。然而,這些方法在計算用戶感知數據時容易出現信息誤差,為加強參與者身份和位置信息的隱私保護,構建不同位置和大小的混合區域,引入多用戶k-匿名算法來保護參與者身份和位置信息。文獻[13]針對感知參與者較少場景中暴露用戶位置隱私的問題，提出多匿名多方服務器協作驗證方法來保護用戶的位置隱私。然而,該方法沒有考慮混沌區域內用戶之間位置信息的隱藏,另外其中混沌區域內用戶數據采用CP-ABE加密的方式,增加了計算復雜度。

為建立有效的混沌區域并實現混沌區域用戶有效的協作和數據傳輸,用戶先根據感知任務建立維諾單元,再通過廣播方式單跳或者多跳聯合其他用戶建立混沌區域,并為每一個混沌區域選擇一個代表,實現其與感知平臺的信息交互。

2 隱私保護方法的構建

在群智感知網絡中,任務發布者通過感知平臺發布感知任務,希望能找到距離感知任務節點盡可能近的移動用戶來完成感知任務。在傳統方法中,是參與者將位置發送給平臺,平臺根據參與者位置和感知節點位置的匹配度來分發任務給參與者,另外,參與者上傳的感知數據也具有感知節點的位置信息。因此,該過程存在隱私泄露的問題,使得參與者不愿意將自己的隱私位置發送給平臺,即使參與者隱藏自己的位置,由于參與者的移動或者在稀疏的網絡環境中,平臺也很容易推斷出參與者的位置。為解決隱私泄露問題,本文提出一種基于維諾單元的隱私保護方法。

2.1 維諾單元的建立

為保護參與者的隱私,參與者通過建立維諾單元來隱藏自身的位置。維諾單元是計算幾何中一種幾何結構,也是一種空間分割方法。二維平面上的維諾圖中的多邊形通常被稱為維諾單元。在幾何空間中,維諾單元代表了各個節點相應的空間描述或作用范圍。維諾單元的建立如圖1所示。

圖1 維諾單元的建立示意圖

定義1假設參與者集合S={s1,s2,…,sn},N>3是歐幾里德平面R上的一個點集,并且這些點不共線,任意4點不共圓,用d(vi,vj)表示vi和vj之間的歐幾里德距離,E(P,S)表示感知節點和參與者集合的環境,設?p∈E,則區域Vi={p∈R2|d(p,si)≤d(p,sj),i,j=1,2,…,n,i≠j}稱為si的維諾單元,各點的維諾單元共同組成維諾圖。

平面上的維諾圖可看作是將參與者集合S中的每個點作為生長核,以相同的速率向外擴張,直到彼此相遇為止而在平面上形成的圖形。除了最外層的點形成的開放區域外,其余每個點都形成一個凸多邊形(維諾單元)。在維諾圖中,任意一個維諾單元中的任意一個內點到該維諾單元控制點si的距離都小于該點到其他任何控制點sj的距離。在維諾圖中,維諾單元通常用于生成“領地”或控制區域,而且由于維諾圖中的每個控制點唯一被一個維諾單元包含,因此可以用維諾圖清晰地表達控制點之間的空間相鄰關系。結合人類日常行為習慣與社會活動準則來看,人們通常會選擇最短時間、最近距離、最低成本以及最優路線來解決生活中遇到的問題,這就反映出人類所遵循的空間行為準則。從這一層面來說,如果將維諾圖中的種子點理解為人類日常行為或活動的出發點或目的地,那么維諾圖內的各個維諾單元就反映了在一段時間內其對應行為活動的空間參考或影響的范圍。

感知平臺將維諾單元中所有感知節點的任務轉發給對應的參與者si,由于維諾單元中感知節點離si距離最近,因此參與者能更好地完成任務,獲得高質量的感知數據。然而,參與者基于隱私的考慮,不愿意將自己的位置發送給感知平臺。因此,本文需要解決的問題是如何保護每一位參與者的隱私,并且使感知平臺能夠將維諾單元中感知節點的任務分發給對應的參與者。

2.2 混沌區域的建立

由于通過感知平臺來計算參與者的維諾單元存在很大程度的隱私泄露,因此參與者可以通過聯系他的鄰居來建立各自的維諾單元,然后每個參與者將建立好的維諾單元發送給感知平臺獲得對應的感知節點任務。該方法從表面上看參與者并沒有將自己的隱私位置發送給平臺,然而其感知平臺還是能夠通過足夠的信息推斷出參與者的位置,首先感知平臺能獲得參與者維諾單元的范圍,然后感知平臺獲得參與者提交的感知點數據,通過兩個數據的匹配,感知平臺同樣能確定參與者的位置信息。因此,參與者僅依靠建立維諾單元還不能完全實現隱私保護,為解決該問題,本文提出一種基于維諾單元的隱私保護算法,每個參與者可以通過聯系其他參與者共同建立混沌區域來保護各自隱私,參與者的隱私保護水平由參與者請求隱私保護值(K,Amin)決定,其中,K代表參與者建立混沌區域中至少包含K個參與者,Amin表示混沌區域的最小面積。算法具體步驟如下:1)每個參與者采用分布式方法建立自己的維諾單元Vi;2)相鄰參與者形成一個混沌區域C;3)為混沌區域選取一個參與者代表sr。

本文參考文獻[14]中的算法來建立參與者的維諾單元。算法主要分成兩步:首先尋找參與者的鄰居;其次通過參與者節點和鄰居節點幾何平分線的交點來計算維諾單元的邊界。參與者通過相互通知的方式來發現各自的維諾鄰居,當參與者確認了維諾鄰居后,通過與鄰居節點幾何平分線的交點來建立維諾單元,并計算維諾單元的面積Ai。

當各參與者建立維諾單元后,為進一步保護參與者隱私,相鄰參與者建立一個混沌區域。本文采用P2P SKA[15]方法來建立混沌區域,參與者si先通過單跳路由向其維諾鄰居廣播一個請求,尋找鄰居加入,如果沒有找到足夠的鄰居,將繼續通過多跳路由進行尋找,直到找到K-1個鄰居。參與者si與鄰居采用匿名的方式進行通信,如果鄰居收到請求后同意加入混沌區域,則將自己的匿名信息和維諾單元的面積Ai發送給si。由于尋找鄰居需要耗費比較長的搜索時間,多次廣播請求也會耗費網絡資源,因此為節省時間和網絡開銷,當鄰居加入到混沌區域后,鄰居節點也可以廣播請求尋找自己的鄰居加入,并為每一個參與者建立緩存聯系清單,在廣播請求時優先緩存清單的鄰居,找到新的鄰居后更新緩存清單。在群智感知網絡中,參與者為動態移動,然而事實上,在很多情況下參與者的移動在一段時間內處于維諾單元范圍內(比如家、公司),尤其是當參與者想要接收維諾單元的感知任務時,考慮到最壞情況下,即使混沌區域的參與者離開當前位置,新的鄰居也可以動態加入混沌區域。圖2中灰色區域為建立的混沌區域C={s8,s15,s16,s21,s25},其中K=5。具體混沌區域的建立過程見算法1。

圖2 混沌區域的建立示意圖

算法1建立混沌區域并計算混沌區域參與者代表的算法

輸入S={s1,s2,…,sn},K

輸出the setAof the chaotic region area,the representativesr

1.C←{φ};V←{φ};h←1;A←{φ}

//V represents the Voronoi diagram and Virepresents the

//Voronoi cell

//Step 1:The establishment of the Voronoi diagram

2.for i from 1 to n do

3.V←Viof si

4.end

//Step 2:The establishment of the cloaked region

5.A←A ∪ area(Vi)// Calculate the area of si

6.while |C|

7.Broadcast a request to the cached contact list of the neighbors within h hop(s) from si

8.C←C∪{sj}

9.A←A ∪ area(Vj)

10.h←h+1

11.end

12.return A

//Step 3:The calculation of the representative

13.for siin C do

14.Calculation the average distance difrom sito other users

15.D←D∪{di} //D represent the set of the participants’

//distances

16.end

17.Finding the user of the smallest average distance as the representative sr

18.return sr

2.3 混沌區域的數據收集及獎勵與懲罰機制

混沌區域參與者完成感知任務后,需要將感知數據提交到平臺。為保護參與者的位置信息,本文將混沌區域參與者的感知數據匯總后,由混沌區域的代表進行提交。參與者完成感知任務后,將感知數據封裝成數據包,其格式包括維諾單元的編號CID,獲取感知數據的時間Time、感知數據節點的編號NID和感知數據DATA,具體格式如圖3所示。參與者將數據包發送給混沌區域的代表sr,收到數據包后sr為每一個參與者計算其數據質量(Quality of Data,QoD)評價值E(si),將E(si)和數據包匯總后形成一個新的數據包,并將新的數據包發送給感知平臺。新的數據包格式包括混沌區域編號RID和K個參與者的匯總數據,具體數據包格式如圖4所示。

圖3 K個參與者的數據包

圖4 混沌區域感知數據包

感知平臺收到混沌區域發送過來的匯總數據后,首先計算每一個維諾單元區域的QoD評價值,然后將平臺計算的評價值和發送過來的評價值進行比較,如果這兩個值不相等,則平臺將發送一個驗證信息給混沌區域的代表sr,驗證數據包是否出錯或者存在丟失。由sr確認后重新計算評價值發送給平臺,平臺再次驗證無誤后進行最終的獎勵和處罰。

在感知系統中,通過計算參與者提交感知QoD評價值來決定是否分發獎勵給參與者。感知系統主要懲罰質量評價值過低的參與者,如果參與者提交偽造數據,當QoD評價值低于閾值ε時,參與者將不能獲得獎勵。為鼓勵成員提高整體的感知QoD,混沌區域的K個成員關系被看作是一種協作的裙帶關系,系統為混沌區域設置一個整體感知QoD評價閾值α,整體QoD評價值E(K)決定了每個參與者聲譽值的更新。混沌區域的QoD評價值計算公式如下:

(1)

其中,ni代表平臺需求的樣本數據,di代表參與者提交的感知數據。式(1)中通過平臺要求的樣本數據和混沌區域參與者提交的有效數據容量的差值與樣本數據比值的平方根來檢測參與者采集感知數據的失真程度,然后將量化值轉化為數據質量評價值E(K)。

本文定義ri為當前任務聲譽值,r′i為這次任務之前的聲譽值。為保證任務執行的質量,每個任務設置一個聲譽閾值rm。以混沌區域中的一個參與者為例,具體聲譽更新方法如下:

(2)

聲譽值更新方法將混沌區域看作一個團隊,如果團隊某個成員提交了質量低的感知數據,使得整個團隊數據質量評價值小于閾值,則團隊所有的成員聲譽值都將降低,因此為保證團隊成員的利益,要求團隊的每個參與者都能提交真實可靠的數據。另外,當參與者聲譽值r′i

3 仿真與性能評價

本文首先對仿真實驗的參數和實驗方法進行介紹說明,然后根據不同的用戶數量與隱私保護水平,對隱私保護成功率、平均響應時間、平均通信量進行比較與評價。隱私保護成功率是指在惡意用戶攻擊下能夠成功隱藏的用戶數量,本文采用文獻[17]中提出的惡意攻擊方法。平均通信量指感知任務過程中參與者之間信息交互的平均流量。平均響應時間是指參與者建立混沌區域并與感知平臺進行數據交互耗費的總時間。平均通信量和平均響應時間反映了隱私保護方法的效率。隱私保護水平在實驗中主要是指混沌區域中包含的用戶數量。為評價PP-Voronoi方法的性能,本文選擇Coprivacy方法[18]和Privacy_l方法[19]進行對比實驗。Coprivacy方法通過用戶之間的協作形成匿名區域,匿名區域內的用戶使用該組的密度中心代替真實位置交互數據。Privacy_l方法通過用戶協作博弈建立匿名區域,然后使用安全求和協議計算區域的錨點與感知平臺進行數據交互。兩種方法在形式上與本文方法類似,因此具有較好的可比性。

3.1 仿真設置

為驗證本文方法的性能,基于Dev-cpp 5.4 C++開發隱私保護仿真系統。實驗軟硬件環境為:Windows 7,Intel(R) Core(TM) i5-3470 3.20 GHz的CPU,8 GB內存。選用城市的真實數據集Milano,平均每千米的用戶數為7 382[20],擁有智能手機的用戶比例為40%。網絡用戶通信采用NS2進行仿真,用戶之間的通信基于4G網絡,帶寬為20 Mb/s,隱私保護水平(K)為5～10,所有實驗結果至少進行100輪后取平均值。

3.2 性能分析

仿真比較在不同參與者數量和隱私保護水平下3種方法的隱私保護成功率。如圖5所示,由于本文PP-Voronoi方法采用不規則混沌區域,且考慮了混沌區域內部用戶之間的位置保護,因此其隨著參與者增多,隱私保護成功率隨之增加直至最高。如圖6所示,隨著參與者數量增多,加入混沌區域內的用戶數增多,隱私保護成功率隨之提高,由此可以看出,Coprivacy方法的隱私保護成功率基本保持不變,PP-Voronoi方法呈緩慢增長,且隱私保護成功率最高。

圖5 3種方法在不同參與者數量下的隱私保護成功率

圖6 3種方法在不同隱私保護水平下的隱私保護成功率

圖7表示3種方法在不同參與者數量下的數據交互平均響應時間。Privacy_l方法需要耗費時間構建一個可信區域,因此其平均響應時間最多。需要指出的是Coprivacy方法假設混沌區域內的參與者都是可信的,且混沌區域的錨點為直接指定,因此其平均響應時間最低。PP-Voronoi方法由于需要通過計算參與者的平均間距確定混沌區域代表,需要耗費時間,因此平均響應時間要高于Coprivacy方法,但是比Privcay_l方法平均響應時間要低。如圖8所示,隨著隱私保護水平的提升,由于建立混沌區域及混沌區域內用戶的交互時間增加,因此各方法的平均響應時間均增加。

圖7 3種方法在不同參與者數量下的平均響應時間

圖8 3種方法在不同隱私保護水平下的平均響應時間

由圖9可以看出,仿真初期由于參與者數量有限,因此建立混沌區域需要參與者與鄰居進行更多的通信量。Privacy_l方法需要更多的協作通信建立混沌區域和錨點,因此其需要的平均通信量最多,且隨著參與者數量的增加通信量下降較慢。PP-Voronoi方法通過參與者的鄰居緩存清單建立通信,平均通信量低于Privacy_l方法,但是比假設完全可信環境的Coprivacy方法要高,且隨著參與者數量增加,平均通信量已經接近Coprivacy方法。如圖10所示,隨著隱私保護水平的提高及混沌區域內參與者數量的增加,3種方法的通信量隨之增加。

圖9 3種方法在不同參與者數量下的平均通信量

圖10 3種方法在不同隱私保護水平下的平均通信量

4 結束語

本文提出一種基于維諾單元的隱私保護方法,在用戶構建維諾單元的基礎上形成不規則的混沌區域,使感知平臺無法直接推斷出參與者的隱私信息,同時混沌區域中內部用戶構建的維諾單元也能保護內部用戶的隱私。此外,本文通過選擇混沌區域代表的方式并采用數據融合的方法與感知平臺進行數據交互,進一步保護參與者的位置信息,且對混沌區域整體數據質量進行評價來更新參與者的聲譽值,從而保證感知數據的質量。在真實數據集上的仿真結果驗證了本文PP-Voronoi方法的可行性與有效性。下一步將優化混沌區域內部參與者動態更新方法,并在此基礎上設計參與者進行數據傳輸的輕量級加密算法。