两层传感网隐私保护的不完全数据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