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

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

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

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

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

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

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

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

0 引言

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

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

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

1 相關工作

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

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

2 預備知識

2.1 網(wǎng)絡模型

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

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

圖1 兩層 WSN體系結構

2.2 查詢模型

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

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

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

2.3 攻擊模型與安全目標

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

基于上述假設，隱私保護Skyline查詢的安全目標為：

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

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

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

2.4 不完全Skyline查詢

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

定義1 對于兩個可能含有不完全屬性的D維點P和Q，P支配Q必須滿足以下兩個條件：

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

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

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

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

2.5 前綴成員驗證機制

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

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

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

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

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

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

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

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

(1)

x

(2)

2.6Bloom過濾器

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

圖2 Bloom過濾器機制示意圖

2.7Merkle哈希樹

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

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

2)將排序后的驗證編碼依次對應到Merkle哈希樹的葉子節(jié)點；

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

4)將根節(jié)點編碼Hroot作為完整性驗證編碼發(fā)送給存儲節(jié)點。

圖3 Merkle哈希樹的建立

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

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

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

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

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

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

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

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

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

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

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

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

存儲節(jié)點 當存儲節(jié)點M收到查詢指令Q后，執(zhí)行以下操作：

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

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

4 協(xié)議分析

4.1 正確性分析

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

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

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

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

4.2 安全性分析

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

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

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

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

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

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

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

4.3 完整性分析

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

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

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

4.4 性能分析

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

1)計算復雜度。參照文獻[2]，本文對PPIS協(xié)議中感知節(jié)點和存儲節(jié)點的計算復雜度進行分析。感知節(jié)點需要對數(shù)據(jù)進行Bloom過濾器(BF)編碼操作(以下稱為BF編碼操作)和加密操作，因為每個桶都需要進行2次BF編碼操作，因此BF編碼操作的計算復雜度為O(2mh)，因為是以桶為單位加密桶中數(shù)據(jù)的，因此加密算法的復雜度為O(「Ir/(mle)?×m)，則傳感節(jié)點的計算復雜度為O(2mh)+O(「Ir/(mle)?×m)。

存儲節(jié)點單次BF編碼比較操作的計算復雜度為O(lm)，則存儲節(jié)點的計算復雜度為O(nmlm)。

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

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

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

(3)

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

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

(4)

5 實驗結果與分析

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

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

本實驗采用的加密算法為128位數(shù)據(jù)加密標準(DataEncryptionStandard,DES)，Bloom過濾器選擇4個哈希函數(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é)點數(shù)量n對通信能耗Et的影響。

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

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

由圖5可以看出，隨著N和B的增加，PPIS和SMQ的Et變化相似，當N和B大到一定程度后趨水平，圖5(a)因為兩者分桶方案是預先確定的，當所有桶都有數(shù)據(jù)時，隨著N的增加，上傳編碼量不會再增加；圖5(b)因為隨著桶數(shù)量增加，會使一個桶里至多有一個數(shù)據(jù)，此時編碼數(shù)量也達到了最大值。而SMQ的分桶方案是由感知節(jié)點自身計算，與感知數(shù)據(jù)的量成正相關關系，因此，圖5(a)中SMQ的Et一直有增大的趨勢，圖5(b)中SMQ的Et沒有大的變化。

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

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

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

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

圖6 lm對感知節(jié)點通信能耗的影響

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

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

圖7 ρ對感知節(jié)點通信能耗的影響

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

6 結語

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

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

)

[1] 戴華,楊庚,肖甫,等.兩層無線傳感網(wǎng)中能量高效的隱私保護范圍查詢方法[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)的隱私保護k-NN查詢處理協(xié)議[J].計算機學報,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].計算機應用,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。

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

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

1001- 9081(2017)06- 1599- 06

10.11772/j.issn.1001- 9081.2017.06.1599

TP309.2

A