兩層傳感網隱私保護的不完全數據Skyline查詢協議

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

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

兩層傳感網隱私保護的不完全數據Skyline查詢協議

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

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

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

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

無線傳感器網絡；隱私保護；Skyline查詢；不完全數據

0 引言

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

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

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

1 相關工作

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

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

2 預備知識

2.1 網絡模型

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

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

圖1 兩層 WSN體系結構

2.2 查詢模型

Skyline查詢的目的是獲取特定時間周期和區域內所有感知節點采集到的感知數據的最優支配集。所以，Skyline查詢指令Q可以形式化表示為：

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

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

2.3 攻擊模型與安全目標

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

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

1)Sink可以獲取感知數據明文，而存儲節點無法獲知；

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

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

2.4 不完全Skyline查詢

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

定義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是不完全數據集S的Skyline集中的點，則點P+∞一定在S+∞的Skyline集中，其中P+∞表示將P中缺失屬性置換為+∞，S+∞表示將S中所有缺失屬性置為+∞。

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

2.5 前綴成員驗證機制

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

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

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

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

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

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

定理2 對于數值x和區間[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的比特數組，如圖2(a)，初始時每位都置為0，并采用k個相互獨立的哈希函數h1、h2、…、hk來表示b個元素的集合X={x1,x2,…,xb}。當該Bloom過濾器需要存儲元素xi(1≤xi≤b)時，首先計算h1(xi)、h2(xi)、…、hk(xi)的值，然后將比特數據中對應位置比特值置為1，如圖2(b)，h1(x1)=3，h2(x1)=6，h3(x1)=8，則將數組中第(3,6,8)位都置為1。類似的，為表示元素x2，也將第(8,11,13)位都置為1，如圖2(c)，若一個位置被多次置為1，則只有第一次起作用，其他幾次操作不會產生任何效果。

圖2 Bloom過濾器機制示意圖

2.7Merkle哈希樹

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

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

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

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

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

圖3 Merkle哈希樹的建立

3 隱私保護不完全Skyline查詢協議

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

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

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

3.1 數據存儲階段

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

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

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

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

步驟7 將如下消息發送給存儲節點M：

3.2 數據查詢階段

數據查詢由存儲節點和Sink協作完成，存儲節點負責計算包含查詢結果的最優支配桶集，并返回給Sink。Sink解密密文數據，計算出最終的查詢結果。

存儲節點 當存儲節點M收到查詢指令Q后，執行以下操作：

步驟2 存儲節點M將Skyline桶集SKYb發送給Sink。

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

4 協議分析

4.1 正確性分析

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

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

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

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

4.2 安全性分析

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

定理3PPIS方案在完成Skyline查詢的過程中，感知節點發送的隱私數據是安全的。

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

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

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

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

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

4.3 完整性分析

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

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

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

4.4 性能分析

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

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

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

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

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

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

(3)

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

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

(4)

5 實驗結果與分析

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

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

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

1)節點數量n對通信能耗Et的影響。

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

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

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

圖4 n對感知節點通信能耗的影響

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

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

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

圖6 lm對感知節點通信能耗的影響

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

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

圖7 ρ對感知節點通信能耗的影響

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

6 結語

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

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

)

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

[2] 彭輝,陳紅,張曉瑩,等.面向雙層傳感網的隱私保護k-NN查詢處理協議[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] 崔斌,盧陽.基于不確定數據的查詢處理綜述[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)；安徽師范大學研究生科研創新與實踐項目(2016yks041)。

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

1001- 9081(2017)06- 1599- 06

10.11772/j.issn.1001- 9081.2017.06.1599

TP309.2

A