兩層傳感網(wǎng)隱私保護(hù)的不完全數(shù)據(jù)Skyline查詢協(xié)議

左開中,尚 寧,陶 健,王濤春

(1.安徽師范大學(xué) 數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院,安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心,安徽 蕪湖 241003)

兩層傳感網(wǎng)隱私保護(hù)的不完全數(shù)據(jù)Skyline查詢協(xié)議

左開中1,2*,尚 寧1,2,陶 健1,2,王濤春1,2

(1.安徽師范大學(xué) 數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院,安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心,安徽 蕪湖 241003)

(*通信作者電子郵箱zuokz@mail.ahnu.edu.cn)

感知節(jié)點(diǎn)感知數(shù)據(jù)易受外界環(huán)境影響，使得不完全數(shù)據(jù)廣泛存在于無線傳感器網(wǎng)絡(luò)中，且感知數(shù)據(jù)面臨嚴(yán)重的隱私威脅。針對(duì)兩層傳感器網(wǎng)絡(luò)不完全數(shù)據(jù)查詢過程中存在的隱私泄露問題，提出一種基于置換和桶技術(shù)的兩層傳感器網(wǎng)絡(luò)隱私保護(hù)的不完全數(shù)據(jù)Skyline查詢協(xié)議(PPIS)。為了實(shí)現(xiàn)對(duì)不完全數(shù)據(jù)的Skyline查詢，PPIS將缺失屬性值置換為數(shù)據(jù)域的上界值，并將不完全數(shù)據(jù)映射到桶中；為了保證數(shù)據(jù)隱私性，PPIS首先將桶區(qū)間轉(zhuǎn)化為前綴編碼，然后將前綴編碼加載到Bloom過濾器中，保證存儲(chǔ)節(jié)點(diǎn)在無需數(shù)據(jù)和桶區(qū)間明文的前提下執(zhí)行查詢處理；為了保證查詢結(jié)果的完整性，PPIS采用Merkle哈希樹構(gòu)造完整性驗(yàn)證編碼，實(shí)現(xiàn)對(duì)查詢結(jié)果的完整性驗(yàn)證。理論分析和仿真實(shí)驗(yàn)驗(yàn)證了PPIS的安全性和有效性，與現(xiàn)有隱私保護(hù)Skyline查詢協(xié)議SMQ和SSQ相比，PPIS通信能耗節(jié)省了70%以上。

無線傳感器網(wǎng)絡(luò)；隱私保護(hù)；Skyline查詢；不完全數(shù)據(jù)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)被廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、國防軍事[1]等各種重要領(lǐng)域。兩層WSN[1-2]是一種以存儲(chǔ)節(jié)點(diǎn)為中間層的特殊WSN，存儲(chǔ)節(jié)點(diǎn)不僅負(fù)責(zé)接收和存儲(chǔ)感知數(shù)據(jù)，還負(fù)責(zé)響應(yīng)Sink節(jié)點(diǎn)的查詢請(qǐng)求，返回查詢結(jié)果。因此，當(dāng)存儲(chǔ)節(jié)點(diǎn)被俘獲，整個(gè)WSN的隱私數(shù)據(jù)將受到竊取、篡改、刪除等嚴(yán)重威脅。

由于感知節(jié)點(diǎn)布置范圍廣，所在環(huán)境惡劣，采集到的數(shù)據(jù)往往會(huì)有某些屬性的丟失，形成不完全數(shù)據(jù)。不完全數(shù)據(jù)和其他不確定性數(shù)據(jù)[3]不同，不能通過其他屬性推測(cè)出缺失屬性的特征[4]，使得WSN中傳統(tǒng)的數(shù)據(jù)查詢方法不能高效地完成甚至無法完成不完全數(shù)據(jù)查詢。不完全Skyline查詢作為不確定性數(shù)據(jù)查詢研究的一個(gè)重要方面，在數(shù)據(jù)庫和網(wǎng)絡(luò)計(jì)算等領(lǐng)域已被廣泛研究[5-7]。然而，WSN作為不完全數(shù)據(jù)產(chǎn)生的一個(gè)常見環(huán)境，目前對(duì)WSN中不完全Skyline查詢的研究基本處于空白。

針對(duì)這些問題，本文提出了一種面向兩層WSN的隱私保護(hù)不完全Skyline查詢協(xié)議(Privacy-Preserving Incomplete Skyline query protocol in two-tiered sensor network, PPIS)。PPIS采用桶機(jī)制減少感知節(jié)點(diǎn)上傳編碼的數(shù)量，采用不完全數(shù)據(jù)置換算法將不完全數(shù)據(jù)轉(zhuǎn)化成完全數(shù)據(jù)，以便存儲(chǔ)節(jié)點(diǎn)快速處理查詢，采用前綴成員驗(yàn)證機(jī)制、Bloom過濾器和對(duì)稱加密技術(shù)保證數(shù)據(jù)的安全性，實(shí)現(xiàn)無需感知數(shù)據(jù)明文和桶區(qū)間明文參與的數(shù)值線性關(guān)系比較，為不完全Skyline查詢處理提供隱私保護(hù)，采用數(shù)據(jù)壓縮機(jī)制將Bloom過濾器編碼表示成兩個(gè)相鄰1位置之差的集合，縮短感知節(jié)點(diǎn)上傳編碼的長度，并采用Merkle哈希樹構(gòu)造驗(yàn)證編碼，實(shí)現(xiàn)查詢結(jié)果的完整性驗(yàn)證。PPIS不僅實(shí)現(xiàn)了感知數(shù)據(jù)的隱私保護(hù)和查詢結(jié)果的完整性驗(yàn)證，而且大大減少了感知節(jié)點(diǎn)的通信量。

1 相關(guān)工作

針對(duì)兩層WSN隱私保護(hù)完全數(shù)據(jù)查詢的研究，在查詢類型方面，主要關(guān)注范圍查詢[1,8]、top-k查詢[9]和最值查詢[10]，而對(duì)復(fù)雜數(shù)據(jù)查詢研究很少，如k-NN查詢[2]和Skyline查詢[9,11]。對(duì)于兩層WSN隱私保護(hù)Skyline查詢，文獻(xiàn)[9]基于桶技術(shù)提出了多維數(shù)據(jù)安全Skyline查詢協(xié)議——SMQ(Secure Multidimensional Query)，SMQ將感知數(shù)據(jù)歸入桶中，并根據(jù)桶ID判別桶間支配關(guān)系，從而實(shí)現(xiàn)安全Skyline查詢。文獻(xiàn)[11]改進(jìn)了SMQ協(xié)議，提出了基于隱私保護(hù)和完整性驗(yàn)證的Skyline查詢協(xié)議SSQ(SecureSkylineQuery)，保證感知數(shù)據(jù)Skyline查詢可以在沒有數(shù)據(jù)明文和桶區(qū)間明文參與的情況下正常進(jìn)行。

兩層WSN環(huán)境容易產(chǎn)生不完全數(shù)據(jù)，而現(xiàn)有對(duì)不完全數(shù)據(jù)的研究僅僅關(guān)注數(shù)據(jù)庫和網(wǎng)絡(luò)計(jì)算等領(lǐng)域中的不完全數(shù)據(jù)模型[12]、相似性檢索[13]、聚類[14]、Skyline查詢[4-7]、top-k支配查詢[15]和k-NN查詢[16]等。對(duì)于不完全Skyline查詢，文獻(xiàn)[4]針對(duì)不完全數(shù)據(jù)支配關(guān)系的非傳遞特性和循環(huán)特性，提出了虛點(diǎn)和影子Skyline技術(shù)，并基于桶技術(shù)設(shè)計(jì)了ISkyline算法，以實(shí)現(xiàn)不完全Skyline查詢。文獻(xiàn)[6]通過構(gòu)造近似函數(shù)依賴捕獲各維度之間的聯(lián)系，估計(jì)缺失屬性值，實(shí)現(xiàn)不完全Skyline查詢。文獻(xiàn)[7]基于ISkyline協(xié)議和數(shù)據(jù)預(yù)處理的思想將待查詢數(shù)據(jù)各屬性值進(jìn)行預(yù)排序，提出了基于排序的高效不完全Skyline算法(efficient Sort-based Incomplete Data Skyline algorithm, SIDS)。文獻(xiàn)[5]提出失效Skyline、影子Skyline、分層庫等概念，設(shè)計(jì)了一種高效的不完全k-skyband查詢協(xié)議。以上針對(duì)傳統(tǒng)網(wǎng)絡(luò)不完全Skyline查詢協(xié)議的研究，基本是通過使用一些數(shù)據(jù)預(yù)處理方法，使算法能夠高效地處理不完全數(shù)據(jù)，卻很少考慮算法在處理這類特殊數(shù)據(jù)時(shí)的能耗和隱私保護(hù)。而本文的核心聚焦于在結(jié)構(gòu)特殊和能量有限的兩層傳感網(wǎng)中實(shí)現(xiàn)高效的隱私保護(hù)不完全Skyline查詢處理。

2 預(yù)備知識(shí)

2.1 網(wǎng)絡(luò)模型

本文采用與文獻(xiàn)[2]類似的兩層WSN模型,如圖1所示。

整個(gè)網(wǎng)絡(luò)被分割成多個(gè)查詢單元(cells),每個(gè)查詢單元C中包含多個(gè)感知節(jié)點(diǎn){s1,s2,…,sn}和一個(gè)存儲(chǔ)節(jié)點(diǎn)M，其中存儲(chǔ)節(jié)點(diǎn)擁有豐富的計(jì)算資源和存儲(chǔ)資源，負(fù)責(zé)接收、存儲(chǔ)和處理單元內(nèi)感知節(jié)點(diǎn)發(fā)來的感知數(shù)據(jù)，也負(fù)責(zé)執(zhí)行Sink發(fā)送的查詢請(qǐng)求；而資源受限的感知節(jié)點(diǎn)僅負(fù)責(zé)搜集感知數(shù)據(jù)，并及時(shí)將這些數(shù)據(jù)傳送給存儲(chǔ)節(jié)點(diǎn)。存儲(chǔ)節(jié)點(diǎn)利用其遠(yuǎn)距離、高頻率的通信能力與其鄰居節(jié)點(diǎn)進(jìn)行通信，形成多跳的上層通信網(wǎng)絡(luò)。

圖1 兩層 WSN體系結(jié)構(gòu)

2.2 查詢模型

Skyline查詢的目的是獲取特定時(shí)間周期和區(qū)域內(nèi)所有感知節(jié)點(diǎn)采集到的感知數(shù)據(jù)的最優(yōu)支配集。所以，Skyline查詢指令Q可以形式化表示為：

Q=(cell=C)∧(epoch=t)∧(region=G)

其中：C為查詢單元；t為查詢周期；G為查詢區(qū)域。

2.3 攻擊模型與安全目標(biāo)

在兩層WSN中，存儲(chǔ)節(jié)點(diǎn)往往成為惡意攻擊的首選目標(biāo)。盡管感知節(jié)點(diǎn)也可能被俘獲，但是單個(gè)感知節(jié)點(diǎn)感知的數(shù)據(jù)相對(duì)整個(gè)網(wǎng)絡(luò)較少，即使存在少量被俘獲，對(duì)整個(gè)網(wǎng)絡(luò)的影響也不大[1,8]。本文假設(shè)攻擊者企圖俘獲存儲(chǔ)節(jié)點(diǎn)，且Sink可信。

基于上述假設(shè)，隱私保護(hù)Skyline查詢的安全目標(biāo)為：

1)Sink可以獲取感知數(shù)據(jù)明文，而存儲(chǔ)節(jié)點(diǎn)無法獲知；

2)查詢結(jié)果中感知數(shù)據(jù)明文同樣只有Sink可以獲取，而存儲(chǔ)節(jié)點(diǎn)無法獲知；

3)存儲(chǔ)節(jié)點(diǎn)通過插入虛假數(shù)據(jù)包、篡改數(shù)據(jù)和刪除數(shù)據(jù)操作破壞查詢結(jié)果的正確性，能被Sink檢測(cè)出來。

2.4 不完全Skyline查詢

不完全Skyline集和傳統(tǒng)Skyline集概念相同，是一種不被其他點(diǎn)所支配的全部點(diǎn)的集合。不完全Skyline查詢是在給定的不完全數(shù)據(jù)集合中找出Skyline集的過程。不完全Skyline查詢同樣涉及元組支配關(guān)系比較，不失一般性，本文對(duì)元組屬性值優(yōu)劣的判斷用屬性“越小”表示“越優(yōu)”，綜合文獻(xiàn)[4,15]，本文對(duì)不完全數(shù)據(jù)的支配關(guān)系定義如下：

定義1 對(duì)于兩個(gè)可能含有不完全屬性的D維點(diǎn)P和Q，P支配Q必須滿足以下兩個(gè)條件：

1)P、Q中必須存在一個(gè)屬性i，P.i和Q.i是已知的，且P.i

2)對(duì)于所有其他的屬性j，j≠i，P.j和Q.j是未知的或者P.j≤Q.j。

定理1 如果P是不完全數(shù)據(jù)集S的Skyline集中的點(diǎn)，則點(diǎn)P+∞一定在S+∞的Skyline集中，其中P+∞表示將P中缺失屬性置換為+∞，S+∞表示將S中所有缺失屬性置為+∞。

證明 若P是不完全數(shù)據(jù)集S的Skyline集中的點(diǎn)，則S中不存在支配P的點(diǎn)Q，即對(duì)于P和Q共有的屬性值，P的更小。而在將P和Q轉(zhuǎn)化成P+∞和Q+∞的過程中，只是置換了P和Q缺失的屬性，共有的屬性值不會(huì)改變，所以共有的屬性值仍然是P的更小，故Q+∞一定不會(huì)支配P+∞，所以P+∞一定在S+∞的Skyline集中。

2.5 前綴成員驗(yàn)證機(jī)制

為了保證感知數(shù)據(jù)的隱私性，PPIS采用前綴成員驗(yàn)證機(jī)制[10-11]和Bloom過濾器[8,10]，無需數(shù)據(jù)明文的參與即可實(shí)現(xiàn)數(shù)值線性關(guān)系比較

定義2 數(shù)值前綴編碼集合。對(duì)于包含α個(gè)二進(jìn)制位的數(shù)值x=b1b2…bα，其前綴編碼集合為：

F(x)={b1b2…bα,b1b2…bα-1*,…,b1*…*,*…*}

定義3 區(qū)間前綴編碼集合。對(duì)于區(qū)間[a，b]，其前綴編碼集合S([a,b])={p1,p2,…,pδ}滿足：

1)p1,p2,…,pδ為前綴編碼，且其對(duì)應(yīng)的區(qū)間并集等于[a，b]；

2){p1,p2,…,pδ}為滿足1)的最小集合。

定理2 對(duì)于數(shù)值x和區(qū)間[a，b]，當(dāng)且僅當(dāng)F(x)∩S([a,b])≠?成立時(shí)，x∈[a,b]。

x≥y?F(x)∩S([y,dmax])≠?

(1)

x

(2)

2.6Bloom過濾器

本文采用Bloom過濾器存儲(chǔ)前綴成員驗(yàn)證編碼，Bloom過濾器一般采用長度為lm的比特?cái)?shù)組，如圖2(a)，初始時(shí)每位都置為0，并采用k個(gè)相互獨(dú)立的哈希函數(shù)h1、h2、…、hk來表示b個(gè)元素的集合X={x1,x2,…,xb}。當(dāng)該Bloom過濾器需要存儲(chǔ)元素xi(1≤xi≤b)時(shí)，首先計(jì)算h1(xi)、h2(xi)、…、hk(xi)的值，然后將比特?cái)?shù)據(jù)中對(duì)應(yīng)位置比特值置為1，如圖2(b)，h1(x1)=3，h2(x1)=6，h3(x1)=8，則將數(shù)組中第(3,6,8)位都置為1。類似的，為表示元素x2，也將第(8,11,13)位都置為1，如圖2(c)，若一個(gè)位置被多次置為1，則只有第一次起作用，其他幾次操作不會(huì)產(chǎn)生任何效果。

圖2 Bloom過濾器機(jī)制示意圖

2.7Merkle哈希樹

1)將這些驗(yàn)證編碼按數(shù)值大小進(jìn)行排序；

本文提出的識(shí)別方法整體流程如圖1所示。首先利用腳部IMU采集人員運(yùn)動(dòng)時(shí)IMU坐標(biāo)系下的三軸加速度和三軸角速度數(shù)據(jù)。其次根據(jù)三軸加速度信息使用峰值檢測(cè)的方法對(duì)運(yùn)動(dòng)過程進(jìn)行單步的劃分,定義每兩個(gè)峰值之間的數(shù)據(jù)為一個(gè)單步[14],獲得每一個(gè)單步的起始位置和終止位置。然后取出每一個(gè)單步起始位置和終止位置之間的三軸加速度和三軸角速度信息即為單步慣性數(shù)據(jù)。接著我們從每個(gè)單步慣性數(shù)據(jù)中提取選定的65維統(tǒng)計(jì)特征用來表征當(dāng)前單步的速度,將65維統(tǒng)計(jì)特征輸入到利用大量單步統(tǒng)計(jì)特征-速度數(shù)據(jù)訓(xùn)練好的識(shí)別模型之中即可以獲得速度識(shí)別結(jié)果。

2)將排序后的驗(yàn)證編碼依次對(duì)應(yīng)到Merkle哈希樹的葉子節(jié)點(diǎn)；

3)從葉子節(jié)點(diǎn)開始，向上層求出根節(jié)點(diǎn)的編碼Hroot。如圖3所示，若H12是H1和H2的父節(jié)點(diǎn)則H12=h(H1|H2)，其中：h()是一個(gè)單向哈希函數(shù)；“|”表示將兩個(gè)字符串進(jìn)行連接；

4)將根節(jié)點(diǎn)編碼Hroot作為完整性驗(yàn)證編碼發(fā)送給存儲(chǔ)節(jié)點(diǎn)。

圖3 Merkle哈希樹的建立

3 隱私保護(hù)不完全Skyline查詢協(xié)議

本章給出實(shí)現(xiàn)PPIS的具體過程，隱私保護(hù)不完全Skyline查詢由Sink、存儲(chǔ)節(jié)點(diǎn)和感知節(jié)點(diǎn)相互協(xié)作完成，主要分為數(shù)據(jù)存儲(chǔ)和查詢處理兩個(gè)階段：

1)數(shù)據(jù)存儲(chǔ)階段。感知節(jié)點(diǎn)在時(shí)間周期結(jié)束之前，將經(jīng)編碼壓縮后的Bloom過濾器編碼、桶中數(shù)據(jù)密文、節(jié)點(diǎn)ID、完整性驗(yàn)證碼ξ、時(shí)間周期和驗(yàn)證編碼發(fā)送給存儲(chǔ)節(jié)點(diǎn)。

2)數(shù)據(jù)查詢階段。存儲(chǔ)節(jié)點(diǎn)收到查詢命令后，從感知節(jié)點(diǎn)發(fā)來的消息中提取出各個(gè)桶對(duì)應(yīng)的Bloom過濾器編碼，計(jì)算出所有桶的Skyline桶集，并將得到的桶集及桶內(nèi)數(shù)據(jù)上傳至Sink。

3.1 數(shù)據(jù)存儲(chǔ)階段

在數(shù)據(jù)存儲(chǔ)階段，感知節(jié)點(diǎn)對(duì)一個(gè)時(shí)間周期內(nèi)獲取的感知數(shù)據(jù)，首先，篩選出局部Skyline集；其次，將篩選出的Skyline集映射到桶中，然后，對(duì)桶區(qū)間進(jìn)行編碼和以桶為單位加密桶內(nèi)感知數(shù)據(jù)；最后，將處理后的數(shù)據(jù)上傳至其所在查詢單元的存儲(chǔ)節(jié)點(diǎn)。具體處理過程描述如下。

步驟1 將感知數(shù)據(jù)中所有缺失的屬性值置為對(duì)應(yīng)屬性值的最大值，即若一個(gè)感知數(shù)據(jù)的第β維缺失，則將該維數(shù)值置為dmaxβ。

步驟2 計(jì)算置換后感知數(shù)據(jù)的局部Skyline集SKYi，并根據(jù)預(yù)定的桶劃分策略，將SKYi中數(shù)據(jù)歸入對(duì)應(yīng)范圍的桶內(nèi)。

步驟6 為si中感知數(shù)據(jù)構(gòu)造Merkle哈希樹，并計(jì)算其根節(jié)點(diǎn)編碼作為查詢驗(yàn)證碼ξ。

步驟7 將如下消息發(fā)送給存儲(chǔ)節(jié)點(diǎn)M：

3.2 數(shù)據(jù)查詢階段

數(shù)據(jù)查詢由存儲(chǔ)節(jié)點(diǎn)和Sink協(xié)作完成，存儲(chǔ)節(jié)點(diǎn)負(fù)責(zé)計(jì)算包含查詢結(jié)果的最優(yōu)支配桶集，并返回給Sink。Sink解密密文數(shù)據(jù)，計(jì)算出最終的查詢結(jié)果。

存儲(chǔ)節(jié)點(diǎn) 當(dāng)存儲(chǔ)節(jié)點(diǎn)M收到查詢指令Q后，執(zhí)行以下操作：

步驟2 存儲(chǔ)節(jié)點(diǎn)M將Skyline桶集SKYb發(fā)送給Sink。

Sink節(jié)點(diǎn) Sink將查詢指令Q發(fā)送給查詢單元C內(nèi)的M后，等待M返回查詢信息。當(dāng)Sink收到M發(fā)來的信息時(shí)，根據(jù)SKYb中感知節(jié)點(diǎn)的ID信息，利用和感知節(jié)點(diǎn)的共享密鑰ki解密SKYb中密文數(shù)據(jù)得到不完全數(shù)據(jù)，首先驗(yàn)證消息的完整性，再利用定義1的支配關(guān)系判別方法計(jì)算這些不完全數(shù)據(jù)的Skyline集，即可得到Skyline查詢結(jié)果SKYa。

4 協(xié)議分析

4.1 正確性分析

設(shè)h為哈希函數(shù)的數(shù)目，lm為Bloom過濾器編碼長度，b為元素個(gè)數(shù)，則假陽性判定發(fā)生的概率[2]為：

P∈[0,(1-(1-1/lm)hb)h]

其中(1-(1-1/lm)hb)h≈(1-e-hb/lm)b。

因?yàn)閘m和b是較大的正整數(shù)，所以，Bloom過濾器假陽性誤判發(fā)生的概率很低，即Bloom過濾器的假陽性誤判對(duì)PPIS正確性的影響可以忽略不計(jì)。

4.2 安全性分析

PPIS的安全性包括隱私數(shù)據(jù)安全性、桶區(qū)間信息安全性和查詢結(jié)果安全性三個(gè)方面，下面從這三個(gè)方面證明PPIS是安全的。

定理3PPIS方案在完成Skyline查詢的過程中，感知節(jié)點(diǎn)發(fā)送的隱私數(shù)據(jù)是安全的。

證明 在數(shù)據(jù)存儲(chǔ)階段，感知節(jié)點(diǎn)si發(fā)送給存儲(chǔ)節(jié)點(diǎn)M的感知數(shù)據(jù)是經(jīng)過對(duì)稱加密處理后的密文，其中使用的密鑰是Sink和si的共享密鑰ki。在無密鑰ki的前提下，即使攻擊者得到了密文數(shù)據(jù)，也不能求出明文數(shù)據(jù)。因此，感知節(jié)點(diǎn)發(fā)送的隱私數(shù)據(jù)是安全的。

定理4PPIS方案在完成Skyline查詢的過程中，桶區(qū)間范圍是安全的。

證明 在數(shù)據(jù)存儲(chǔ)階段，感知節(jié)點(diǎn)si發(fā)送給存儲(chǔ)節(jié)點(diǎn)M的桶區(qū)間信息是經(jīng)過采用哈希函數(shù)構(gòu)造的Bloom過濾器處理的，所以即使攻擊者得到Bloom過濾器編碼，也無法反向推出區(qū)間范圍信息。因此，感知節(jié)點(diǎn)發(fā)送的各個(gè)桶的區(qū)間范圍是安全的。

定理5PPIS方案在完成Skyline查詢的過程中，其查詢結(jié)果是安全的。

證明 存儲(chǔ)節(jié)點(diǎn)M根據(jù)Bloom過濾器編碼判定密文數(shù)據(jù)的支配關(guān)系，不需要感知數(shù)據(jù)明文和桶區(qū)間明文的直接參與。Sink使用共享密鑰ki解密SKYb中的密文數(shù)據(jù)，得到不完全數(shù)據(jù)，并從中篩選出Skyline查詢結(jié)果SKYa。因此，M無法獲得查詢結(jié)果中的數(shù)據(jù)明文，即查詢結(jié)果是安全的。

4.3 完整性分析

數(shù)據(jù)的完整性包括查詢結(jié)果的正確性和完整性兩個(gè)方面，將從這兩個(gè)方面分析PPIS的完整性。

1)查詢結(jié)果的正確性。由于攻擊者無法得到密鑰ki，且驗(yàn)證編碼是由感知數(shù)據(jù)明文通過單向哈希函數(shù)生成的，因此，攻擊者無法偽造驗(yàn)證編碼。當(dāng)攻擊者通過插入虛假數(shù)據(jù)包、篡改數(shù)據(jù)和刪除數(shù)據(jù)操作進(jìn)行完整性攻擊時(shí)，都會(huì)改變Merkle哈希樹根節(jié)點(diǎn)的哈希值。所以，Sink能檢測(cè)出不正確查詢結(jié)果。

2)查詢結(jié)果的完整性。如果攻擊者刪除了某些滿足查詢條件的桶，則其對(duì)應(yīng)的驗(yàn)證編碼也將一起丟失。此時(shí)，Sink通過剩余的驗(yàn)證編碼和驗(yàn)證對(duì)象構(gòu)造新Merkle哈希樹，求出的根節(jié)點(diǎn)編碼和收到的根節(jié)點(diǎn)編碼是不一致的。所以，Sink能檢測(cè)出不完整查詢結(jié)果。

4.4 性能分析

假設(shè)網(wǎng)絡(luò)中存在n個(gè)感知節(jié)點(diǎn)，每個(gè)感知節(jié)點(diǎn)單位時(shí)間周期內(nèi)產(chǎn)生N個(gè)感知數(shù)據(jù)，其中：SKYi含I個(gè)長度為r的β維感知數(shù)據(jù)，分桶數(shù)為B，N個(gè)感知數(shù)據(jù)映射到m個(gè)桶，驗(yàn)證編碼長度為lc，單位密文數(shù)據(jù)長度為le，加密和HMAC計(jì)算的單位能耗分別為ec和eh，接收和發(fā)送單位數(shù)據(jù)的平均能耗分別為er和es，感知節(jié)點(diǎn)到存儲(chǔ)節(jié)點(diǎn)的平均路徑長度(跳數(shù))為L，感知節(jié)點(diǎn)ID和時(shí)間周期數(shù)據(jù)長度分別為lid和lt。

1)計(jì)算復(fù)雜度。參照文獻(xiàn)[2]，本文對(duì)PPIS協(xié)議中感知節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)的計(jì)算復(fù)雜度進(jìn)行分析。感知節(jié)點(diǎn)需要對(duì)數(shù)據(jù)進(jìn)行Bloom過濾器(BF)編碼操作(以下稱為BF編碼操作)和加密操作，因?yàn)槊總€(gè)桶都需要進(jìn)行2次BF編碼操作，因此BF編碼操作的計(jì)算復(fù)雜度為O(2mh)，因?yàn)槭且酝盀閱挝患用芡爸袛?shù)據(jù)的，因此加密算法的復(fù)雜度為O(「Ir/(mle)?×m)，則傳感節(jié)點(diǎn)的計(jì)算復(fù)雜度為O(2mh)+O(「Ir/(mle)?×m)。

存儲(chǔ)節(jié)點(diǎn)單次BF編碼比較操作的計(jì)算復(fù)雜度為O(lm)，則存儲(chǔ)節(jié)點(diǎn)的計(jì)算復(fù)雜度為O(nmlm)。

2)能耗分析。感知節(jié)點(diǎn)的能耗包括計(jì)算能耗和通信能耗兩方面。

令感知節(jié)點(diǎn)的通信開銷為Et，計(jì)算能耗為Ec。每個(gè)感知節(jié)點(diǎn)發(fā)送給存儲(chǔ)節(jié)點(diǎn)的信息包括時(shí)間周期、節(jié)點(diǎn)ID、完整性驗(yàn)證碼ξ、Bloom編碼和密文數(shù)據(jù)，因此有：

Et=(lid+lt+ξ+「Ir/(mle)?×mle+2βmlm+mlc)×n×(L×es+(L-1)×er)

(3)

感知節(jié)點(diǎn)的計(jì)算能耗為感知節(jié)點(diǎn)進(jìn)行加密和HMAC計(jì)算的能耗，因此有：

Ec=n×I×r×(ec+eh)

(4)

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

為了驗(yàn)證本協(xié)議在性能上的優(yōu)越性，本章在文獻(xiàn)[18]的WSN模擬器基礎(chǔ)上，仿真實(shí)現(xiàn)了PPIS、SSQ和SMQ協(xié)議，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較分析。

實(shí)驗(yàn)環(huán)境為Corei5- 2450MCPU，4GB內(nèi)存；軟件環(huán)境為Windows7 64位操作系統(tǒng)，VS.NET2010和Matlab。實(shí)驗(yàn)使用與SSQ方案中同樣的數(shù)據(jù)集IntelLab(http://berkeley.intel-research.net/labdata)，并在此數(shù)據(jù)集的基礎(chǔ)上按比例ρ隨機(jī)刪除一些屬性，構(gòu)成不完全數(shù)據(jù)。

本實(shí)驗(yàn)采用的加密算法為128位數(shù)據(jù)加密標(biāo)準(zhǔn)(DataEncryptionStandard,DES)，Bloom過濾器選擇4個(gè)哈希函數(shù)和128b的編碼數(shù)組。無線通信電路發(fā)送和接收1b的能量消耗公式為es=α+γ×dk和er=β，其中:α為通信發(fā)送電路消耗的能量，γ為傳輸放大器消耗的能量，d為傳輸距離，k為路徑損失因子，β為通信接收電路消耗的能量[1]。參數(shù)值為：α=45 nJ/b，γ=10 pJ/(b·m2)，β=135 nJ/b，k=2。DES的加密能耗為8.92 μJ，查詢命令長度為24 b。

1)節(jié)點(diǎn)數(shù)量n對(duì)通信能耗Et的影響。

由圖4可知，隨著節(jié)點(diǎn)數(shù)量的增加，感知節(jié)點(diǎn)的平均通信能耗有減少的趨勢(shì)，這是因?yàn)楦兄?jié)點(diǎn)到存儲(chǔ)節(jié)點(diǎn)的平均跳數(shù)有減少的趨勢(shì)。由于PPIS使用了Bloom過濾器的編碼壓縮機(jī)制，同SSQ和SMQ相比，PPIS的Et減少了70%以上。

2)感知數(shù)據(jù)數(shù)量N和桶數(shù)量B對(duì)通信能耗Et的影響。

由圖5可以看出，隨著N和B的增加，PPIS和SMQ的Et變化相似，當(dāng)N和B大到一定程度后趨水平，圖5(a)因?yàn)閮烧叻滞胺桨甘穷A(yù)先確定的，當(dāng)所有桶都有數(shù)據(jù)時(shí)，隨著N的增加，上傳編碼量不會(huì)再增加；圖5(b)因?yàn)殡S著桶數(shù)量增加，會(huì)使一個(gè)桶里至多有一個(gè)數(shù)據(jù)，此時(shí)編碼數(shù)量也達(dá)到了最大值。而SMQ的分桶方案是由感知節(jié)點(diǎn)自身計(jì)算，與感知數(shù)據(jù)的量成正相關(guān)關(guān)系，因此，圖5(a)中SMQ的Et一直有增大的趨勢(shì)，圖5(b)中SMQ的Et沒有大的變化。

圖4 n對(duì)感知節(jié)點(diǎn)通信能耗的影響

圖5 N和B對(duì)感知節(jié)點(diǎn)通信能耗的影響

3)Bloom編碼長度lm對(duì)通信能耗Et的影響。

圖6顯示lm對(duì)感知節(jié)點(diǎn)通信能耗的影響，可以看出，隨著lm的增加，PPIS的Et沒有大的變化而SSQ的Et呈線性增加。這是因?yàn)镻PIS使用了編碼壓縮技術(shù)，編碼長度和Bloom數(shù)組長度沒直接關(guān)系，只取決于Bloom數(shù)組中1的位數(shù)。

圖6 lm對(duì)感知節(jié)點(diǎn)通信能耗的影響

4)不完全數(shù)據(jù)率ρ對(duì)通信能耗Et的影響。

圖7顯示ρ對(duì)感知節(jié)點(diǎn)通信能耗的影響，可以看出，隨著ρ的增加，PPIS的Et逐漸減少，是因?yàn)殡S著不完全數(shù)據(jù)率ρ的增大，使用置換算法后許多屬性值被置為“最劣”，會(huì)有更多的數(shù)據(jù)被支配和丟棄。

圖7 ρ對(duì)感知節(jié)點(diǎn)通信能耗的影響

綜合上述實(shí)驗(yàn)結(jié)果和分析可知：與SSQ和SMQ相比，PPIS協(xié)議有更低的感知節(jié)點(diǎn)通信能耗，且通信能耗節(jié)省了70%以上。

6 結(jié)語

本文提出了一種基于桶技術(shù)和前綴成員驗(yàn)證機(jī)制的兩層傳感網(wǎng)隱私保護(hù)不完全Skyline查詢協(xié)議PPIS。在安全方面，PPIS可以有效地保證數(shù)據(jù)的隱私性和查詢結(jié)果的完整性，存儲(chǔ)節(jié)點(diǎn)在查詢過程中不能得到感知數(shù)據(jù)明文和桶區(qū)間明文且Sink可以通過查詢結(jié)果完整性驗(yàn)證編碼驗(yàn)證查詢結(jié)果的完整性；在性能方面，PPIS有效減少了感知節(jié)點(diǎn)上傳的編碼數(shù)量，降低了感知節(jié)點(diǎn)的通信能耗。理論分析表明，PPIS能夠確保感知數(shù)據(jù)的隱私性，以及查詢結(jié)果的正確性、隱私性和完整性。實(shí)驗(yàn)結(jié)果表明，PPIS和現(xiàn)有隱私保護(hù)Skyline查詢協(xié)議SSQ和SMQ相比具有更好的性能表現(xiàn)。

本文所設(shè)計(jì)PPIS協(xié)議成功抵抗了存儲(chǔ)節(jié)點(diǎn)被俘獲發(fā)起的攻擊，而無法抵抗存儲(chǔ)節(jié)點(diǎn)和感知節(jié)點(diǎn)的共謀攻擊。雖然單純的感知節(jié)點(diǎn)被俘獲對(duì)整個(gè)網(wǎng)絡(luò)數(shù)據(jù)安全性的威脅是很小的，但是當(dāng)存儲(chǔ)節(jié)點(diǎn)和部分感知節(jié)點(diǎn)被俘獲時(shí)，攻擊者可以對(duì)網(wǎng)絡(luò)進(jìn)行共謀攻擊，此時(shí)對(duì)網(wǎng)絡(luò)中數(shù)據(jù)安全的威脅是巨大的，因此，如何設(shè)計(jì)具有抵抗共謀攻擊的安全不完全Skyline查詢協(xié)議，將是下一步研究的重點(diǎn)方向。

)

[1] 戴華,楊庚,肖甫,等.兩層無線傳感網(wǎng)中能量高效的隱私保護(hù)范圍查詢方法[J].計(jì)算機(jī)研究與發(fā)展,2015,52(4):983-993.(DAIH,YANGG,XIAOF,etal.Anenergy-efficientandprivacy-preservingrangqueryprocessingintwo-tieredwirelesssensornetworks[J].JournalofComputerResearchandDevelopment, 2015, 52(4): 983-993.)

[2] 彭輝,陳紅,張曉瑩,等.面向雙層傳感網(wǎng)的隱私保護(hù)k-NN查詢處理協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2016,39(5):872-892.(PENG H, CHEN H, ZHANG X Y, et al. Privacy-preservingk-NN query protocol for two-tiered wireless sensor networks [J]. Chinese Journal of Computers, 2016, 39(5): 872-892.)

[3] 崔斌,盧陽.基于不確定數(shù)據(jù)的查詢處理綜述[J].計(jì)算機(jī)應(yīng)用,2008,28(11):2729-2731.(CUI B, LU Y. Survey on query processing based on uncertain data [J]. Journal of Computer Applications, 2008, 28(11): 2729-2731.)

[4] KHALEFA M E, MOKBEL M F, LEVANDOSKI J J. Skyline query processing for incomplete data [C]// ICDE’08: Proceedings of the 2008 IEEE 24th IEEE International Conference on Data Engineering. Piscataway, NJ: IEEE, 2008: 556-565.

[5] GAO Y J, MIAO X Y, CUI H Y, et al. Processingk-skyband, constrained skyline, and group-by skyline queries on incomplete data [J]. Expert Systems with Applications, 2014, 41(10): 4959-4974.

[6] ALWAN A A, IBRAHIM H, UDZIR N I. A framework for identifying skyline over incomplete data [C]// Proceedings of the 2014 3rd IEEE International Conference on Advanced Computer Science Applications and Technologies. Piscataway, NJ: IEEE, 2014: 79-84.

[7] BHARUKA R, SREENIVASA K P. Finding skylines for incomplete data [C]// Proceedings of the 24th Australasian Database Conference. Darlinghurst: Australian Computer Society, 2013: 109-117.

[8] ZHANG X Y, DONG L, PENG H, et al. Achieving efficient and secure range query in two-tiered wireless sensor networks [C]// Proceedings of the 2014 IEEE 22nd International Symposium on Quality of Service. Piscataway, NJ: IEEE, 2014: 380-388.

[9] YU C M, TSOU Y T, LU C S, et al. Practical and secure multidimensional query framework in tiered sensor networks [J]. IEEE Transactions on Information Forensics and Security, 2011, 6(2): 241-255.

[10] YAO Y L, XIONG N X, PARK J H. Privacy-preserving max/min query in two-tiered wireless sensor networks [J]. Computer & Mathematics with Applications, 2013, 65(9): 1318-1325.

[11] LI J G, LIN Y P, WANG G, et al. Privacy and integrity preserving skyline queries in tiered sensor networks [J]. Security & Communication Networks, 2014, 7(7): 1177-1188.

[12] GRZYMALA-BUSSE J W, CLARK P G, KUEHNHAUSEN M. Generalized probabilistic approximations of incomplete data [J]. International Journal of Approximate Reasoning, 2014, 55(1): 180-196.

[13] CHENG W, JIN X M, SUN J T, et al. Searching dimension incomplete databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(3): 725-738.

[14] ZHANG L Y, LU W, LIU X D, et al. Fuzzy c-means clustering of incomplete data based on probabilistic information granules of missing values [J]. Knowledge-Based Systems, 2016, 99(C): 51-70.

[15] MIAO X Y, GAO Y J, ZHENG B H, et al. Top-kdominating queries on incomplete data [J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1): 252-266.

[16] MIAO X Y, GAO Y J, CHEN G, et al. Processing incompleteknearest neighbor search [J]. IEEE Transactions on Fuzzy Systems, 2016, 24(6): 1349-1363.

[17] PANG H H, TAN K L. Authenticating query results in edge computing [C]// ICDE’04: Proceedings of the IEEE 20th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 560-571.

[18] COMAN A, NASCIMENTO M A, SANDER J. A framework for spatio-temporal query processing over wireless sensor networks [C]// DMSN’04: Proceedings of the 1st International Workshop on Data Management for Sensor Networks: in conjunction with VLDB 2004. New York: ACM, 2004: 104-110.

This work is partially supported by the National Natural Science Foundation of China (61402014), the Scientific Research Innovation and Practice Program for Graduate Students of Anhui Normal University (2016yks041).

ZUO Kaizhong, born in 1974, Ph. D., professor. His research interests include data security, privacy preserving.

SHANG Ning, born in 1990, M. S. candidate. His research interests include wireless sensor network, privacy preserving.

TAO Jian, born in 1989, M. S. candidate. His research interests include distributed system, privacy preserving.

WANG Taochun, born in 1979, Ph. D., associate professor. His research interests include wireless sensor network, privacy preserving.

Privacy-preserving incomplete data Skyline query protocol in two-tiered sensor networks

ZUO Kaizhong1,2*, SHANG Ning1,2, TAO Jian1,2, WANG Taochun1,2

(1.CollegeofMathematicsandComputerScience,AnhuiNormalUniversity,WuhuAnhui241003,China; 2.EngineeringTechnologyResearchCenterofNetworkandInformationSecurity,AnhuiNormalUniversity,WuhuAnhui241003,China)

The sensor data of sensor node is easy to be influenced by the external environment, which makes the incomplete data exist widely in the wireless sensor network and the sensor data face the serious privacy threat. Aiming at the problem of privacy leakage during the query process of incomplete data in two-tiered sensor networks, a Privacy-Preserving Incomplete data Skyline query protocol in two-tiered sensor network (PPIS) based on replacement algorithm and bucket technology was proposed. In order to realize the Skyline query for incomplete data, the value of the missing attribute was replaced to the upper bound of data field and then the incomplete data was mapped into the buckets. In order to preserve the privacy of data, the range of the bucket was transformed into a prefix encoding and then the prefix encoding was loaded into Bloom filters. Thus, the query processing could be executed by the storage node without clear text of the sensor data and real range of the bucket. In order to preserve the integrity of query results, Merkle hash tree was used to construct the integrity verification code for implementing the integrity verification of query results. Theoretical analysis and simulation experiment of real dataset has confirmed the privacy and efficiency of PPIS. Compared with existing privacy-preserving Skyline query protocols — SMQ (Secure Multidimensional Query) and SSQ (Secure Skyline Query), the proposed PPIS can save the communication cost by more than 70%.

Wireless Sensor Network (WSN); privacy-preserving; Skyline query; incomplete data

2016- 11- 10;

2017- 02- 20。

國家自然科學(xué)基金資助項(xiàng)目(61402014)；安徽師范大學(xué)研究生科研創(chuàng)新與實(shí)踐項(xiàng)目(2016yks041)。

左開中(1974—)，男，安徽宿州人，教授，博士，CCF會(huì)員，主要研究方向：數(shù)據(jù)安全、隱私保護(hù)； 尚寧(1990—)，男，安徽阜陽人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、隱私保護(hù)； 陶健(1989—)，男，安徽壽縣人，碩士研究生，主要研究方向：分布式系統(tǒng)、隱私保護(hù)；王濤春(1979—)，男，安徽無為人，副教授，博士，主要研究方向：無線傳感器網(wǎng)絡(luò)、隱私保護(hù)。

1001- 9081(2017)06- 1599- 06

10.11772/j.issn.1001- 9081.2017.06.1599

TP309.2

A