引用本文
王涛春, 秦小麟, 刘亮, 戴华. 两层无线传感器网络中隐私保护的范围查询[J]. 北京邮电大学学报, 2014, 37(2): 104-108.  
WANG Tao-chun, QIN Xiao-lin, LIU Liang, DAI Hua. Privacy-Preserving Range Query in Two-Tiered Wireless Sensor Networks[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS, 2014, 37(2): 104-108.  
Permissions
Copyright©2014, 《北京邮电大学学报》编辑部
《北京邮电大学学报》编辑部 所有
两层无线传感器网络中隐私保护的范围查询
王涛春1,2, 秦小麟1, 刘亮1, 戴华3    
1. 南京航空航天大学 计算机科学与技术学院, 南京 210016;
2. 安徽师范大学 数学计算机科学学院, 安徽 芜湖 241003;
3. 南京邮电大学 计算机学院, 南京 210016
作者简介: 王涛春(1979—), 男, 副教授, E-mail: wangtc@nuaa.edu.cn.
收稿日期: 2013-08-04
基金项目: 国家自然科学基金项目(61373015, 61300240);国家教育部高等学校博士学科点专项科研基金项目(20103218110017);中央高校基本科研业务费专项基金项目(NP2013307);安徽高校省级自然科学研究项目(KJ2012Z120)
摘要

两层无线传感器网络中存储节点负责存储传感节点的数据和处理Sink节点的查询请求.然而, 由于存储节点的重要性, 使得存储节点成为攻击者攻击的目标, 特别是存储节点被攻击者捕获后, 攻击者能够获取隐秘的传感数据、伪造传感数据和丢弃部分查询结果等.因此, 提出了一种安全的范围查询方案, 保证了数据的机密性和真实性, 并利用签名融合技术, 极大地降低了通信量, 且具有较高的完整性检测概率.在此基础上, 提出了一种检测率更高的范围查询方案.理论分析和实验结果显示, 所提出的方案具有较高的检测率和较低的通信量.

关键词: 隐私保护     范围查询     无线传感器网络     签名融合    
中图分类号:TP393 文献标志码:A 文章编号:1007-5321(2014)02-0104-05 DOI:10.13190/j.jbupt.2014.02.022
Privacy-Preserving Range Query in Two-Tiered Wireless Sensor Networks
WANG Tao-chun1,2, QIN Xiao-lin1, LIU Liang1, DAI Hua3    
1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China;
2. College of Mathematics and Computer Science, Anhui Normal University, Anhui Wuhu 241003, China;
3. College of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210016, China
Abstract

In the two-tiered wireless sensor networks, storage nodes collect data from sensor nodes and answer the queries from the sink. However, for their importance, storage nodes are attractive targets of attack and even might be compromised by the adversary. A compromised storage node may disclose sensitive data to the adversary and return juggled or incomplete sensitive data to the sink. A safe verifiable range query scheme is presented. It offers data confidentiality and query result authenticity. More importantly, it allows sink to verify query result completeness with high probability using signature aggregation technology, which greatly reduces communication cost. And based on the above scheme, it is an improvably secure verifiable range query scheme with higher probability of verification that is proposed. The theoretical analysis and simulations illustrate the schemes have high verification probability and low communication cost.

Key words: privacy-preserve     range query     wireless sensor networks     signature aggregation    

两层无线传感器网络[1](WSNs，wireless sensor networks)由大量资源受限的传感节点和少量资源丰富的存储节点构成，传感节点处于下层，存储节点处于上层.由于WSN具有拓扑结构简单、存储节点资源丰富、查询高效和负载均衡等特点，因此其成为新的研究热点.

然而，两层WSNs面临着严重的安全问题，因此很多学者提出了很多解决方案[2-5].这些方案通过桶技术[6]，保证了数据的机密性和真实性.因此，查询结果完整性检测是各方案研究的重点. Shi等[3]提出通过时空方法来检测查询结果的完整性. Sheng等[4]提出了编码数方法解决完整性检测问题.笔者提出了基于签名融合的两层WSNs的隐私保护范围查询方案，在花费较少通信量情况下，保持较高的检测率.

1 预备知识1.1 网络模型

两层WSNs被划分为若干个单元(cell)，每个单元由一个存储节点和若干个传感节点构成.单元内节点采用融合树拓扑结构，其中存储节点为根节点，称为单元头节点.

1.2 攻击模型

本研究主要考虑存储节点被捕获后的攻击情况.假设攻击者可以捕获任意数量的存储节点，攻击方式包括3种：1) 获得存储节点中存储的数据；2) 伪造部分数据作为查询结果返回给Sink节点；3) 返回部分查询结果传输给Sink节点.

1.3 Boneh签名方案

Boneh等[7]提出了一种融合签名方案，其方案是以双线性映射en为基础的，即en=G1×G2→GT，其中G1、G2和GT是质数n序的循环群，包括5个处理操作：密钥产生、签名、认证、融合和签名融合认证，其具体方案见文献[7].

2 加密数据的范围查询

为了保证数据的机密性，传感节点需要对感知数据进行加密.然而，通过简单的加密虽然能够提供良好的机密性，但在收到查询请求后，必须将所有数据传输给Sink，而查询的范围可能只是小部分数据，因此，该处理方案效率极其低下，可采用桶方案[5]解决此问题.节点对数据加密外，还根据数值的大小在密文上附带一个桶标签tag，再将这些密文传输给.假设所有节点Si预先加载了只有自身和Sink知道的密钥Ki, 0，为了增加机密性，当新周期t开始前，Si通过单向Hash函数计算出新密钥，即Ki, t=Hash(Ki, t-1)，并将Ki, t-1丢弃掉.

Sink进行范围查询(t, [a, b])时，需要将查询请求转换成Qt形式，即根据桶划分规则将查询的数值范围转换成桶集合Bt，并将查询请求Qt=(c, t, Bt)传输给，其中c表示单元ID. 根据Bt返回查询结果.通过数据加密，保证了数据的机密性和真实性，并利用桶技术有效地进行范围查询，但可能只返回部分查询结果，且很难检测，本研究将对该问题的解决方案进行详细描述.

3 SafeVRQ(安全范围查询)方案

通过比较计算签名集与传输签名集来检测查询结果是否完整，并利用签名融合减少通信量.

3.1 范围查询

隐私保护范围查询的主要目的是保证数据的机密性、查询结果的真实性和完整性，处理过程包含4个阶段.

1) 前期准备阶段：对每个节点Si(包括存储节点)前期存储必要信息，包括桶的划分、密钥Ki, 0和单向Hash函数、Boneh方案中的认证密钥对(PSi, RSi)，其中PSi=vi，RSi=xi.最后Sink保存所有的Ki, 0和PSi.

2) 数据存储阶段：在周期t结束后，每个节点Si进行如下步骤操作.

步骤1  根据桶的划分将该周期的所有数据进行分类，并加密，生成数据加密后的集合Ei, t.

步骤2  签名，对每个数据签名，用φi, t, j, k表示，其中i表示Si，j表示桶号，k表示第k项数据，并对同桶中签名进行求和运算，结果用φi, t, j表示，节点Si所有桶签名求和结果的集合用φit表示.

① 签名：φi, tj, k=xihi, k，其中hi, k=H(Dk).

② 签名求和：，即φi, t={φi, t, j|桶Vj非空}.

步骤3  数据融合，每个节点对其子树节点信息进行融合，ξi, t表示根节点为Si子树的加密数据集，Φi, t表示签名集.节点有两种情况.

① 叶子节点Si：则ξi, t=Ei, t，Φi, t=ϕi, t.

② 中间节点Si：假设其有x个孩子节点，当接收到孩子节点数据＜jρ, ξjρ, t, Φjρ, t＞后，获得数据集合ξi, t和签名集合Φi, t.可知ξi, t=(∪ρ=1xξjρ, t)∪Ei, t和

进行同样的操作，当接收到孩子节点的数据后计算出和用于Sink的查询.

3) 查询请求阶段：当Sink进行一个查询操作{c, t, [a, b]}时，首先将查询范围[a, b]转换成桶集合，记为Bt. 收到查询请求Qt=(c, t, Bt)后，将单元内所有在桶集合Bt内的数据集和对应的签名和值ABt, t返回给Sink.

4) 完整性验证阶段:被捕获的可能返回部分查询结果，Sink需要根据返回的签名和集合ABt, t的结果来检测查询结果是否完整.具体的验证过程为：对返回结果进行解密，得到数据集D={d1, 1, …，d1, num1, …, di, 1, …, di, numi, …}，其中i代表节点Si；计算数据集D中数据的Hash值，即hi, j=H(di, j)；最后，计算en(ABt, t, g2)和，如果两者相等则认为返回的查询结果是完整的，否则不完整.

3.2 性能分析

1) 机密性和真实性

攻击者捕获到后，只能得到加密数据.每个节点与Sink的对称密钥不相同，且密钥是随周期t变化而变化的，所以攻击者即使破解或获得某个密钥也不能破解其他节点和周期t之前的密文.另外，Sink通过解密容易判断数据的真实性.

2) 完整性

被捕获的常见的恶意行为是返回部分查询结果，假设每个单元内有一个和N个传感节点，如果丢弃桶j中的数据，为了逃避Sink检测，必须构造正确的签名和φM, tj，假设签名的位长为lφ，则构造正确签名和的正确概率是2－lφ.

假设Si在周期t产生数据在桶j里的概率是pi, j, t，则整个单元内在周期t时，桶j产生数据的概率为

(1)

同时，假设桶j被查询的概率是γj, t，丢弃桶j中数据的概率是δj, t，则丢弃数据的桶数为由于正确构造签名的概率是2－lφ，所以被检测出的概率为

(2)

从式(2) 可知，只要足够大，则检测的概率接近于1.

3) 通信量

通信量主要包括数据存储和查询，数据存储指的是传感节点将数据传输给，查询由Sink查询请求和返回查询结果组成.由于Sink和资源丰富，为了简化处理，本研究只考虑数据存储的通信量.节点传输信息主要由数据集ξi, t和完整性检测的签名集Φi, t两部分组成.由于Φi, t能够融合，因此，Φi, t是一跳广播，假设Si到的平均跳数是l，则ξi, t平均广播l次.假设每个密文的位长为e，nt是节点产生数据项数，节点的ID号位长为i(N≤2i)，桶标签的长度为b(g≤2b)，则Si传输ξi, t的通信量为

(3)

其中: 表示节点Si中非空的桶数，e×nt表示传输加密数据的位数.

对于签名集，在签名位长确定的情况下，其集合长度由其签名的个数(桶数)确定，且不同节点之间相同桶签名可以融合，所以可以将签名看成是1跳，所以这方面的通信花费为

(4)

其中Ai表示的是以节点Si为根节点的子树节点集合.因此，通信花费为

4 ISafeVRQ(优化的SafeVRQ)方案

为了进一步提高检测率，特别是能够检测出丢弃某个或多个桶内的所有数据和其签名集合的恶意行为. ISafeVRQ对节点所有非空桶添加分别表示其前驱和后继非空桶标签数据，提高检测率.

4.1 范围查询

ISafeVRQ方案中，对每个非空桶b上添加2个数据，分别表示桶b前非空桶的桶标签pb和后非空桶的桶标签nb，当pb=0表示桶b前面的桶都为空，同理，nb=g+1表示桶b后面的桶都为空.

当Sink收到信息后采用SafeVRQ提出的验证方案进行验证，判断桶中数据是否完整，如果不通过，则结果不完整；如果通过，则Sink对解密后数据中所有桶标签进行并集，并判断桶标签集合与返回数据对应的桶集合是否相等，相等，则结果完整；否则不完整.

4.2 性能分析

ISafeVRQ与SafeVRQ在数据的机密性和真实性上完全相同，因此主要讨论完整性检测和通信量.

1) 完整性

ISafeVRQ中，对每个非空桶b添加2个分别表示最近的前后非空桶标签.假设查询范围是连续的，丢弃数据分成2种情况.

① 丢弃部分数据.根据SafeVRQ分析可知，Si在周期t桶j被丢弃的概率为pi, j, tγj, tδj, t.同时，在ISafeVRQ方案中，每个桶不仅记录感知数据，还存储其前驱和后继桶标签，因此被丢弃的桶被检测到的概率为

(5)

所以对于整个单元所有桶来说，由于记录桶标签而被检测到的概率为

(6)

Sink可以通过签名和查询结果中的桶标签集合来验证查询结果的完整性，其检测概率为

(7)

② 丢弃桶中所有数据.在ISafeVRQ中，每个桶记录其前驱和后继桶标签，因此在查询范围内只要存在没被丢弃的桶，则被丢弃的桶标签至少有1个被记录，使得Sink能够检测出返回的结果不完整，其概率为PT_det.

从上面分析可知，ISafeVRQ对完整性检测的概率更高，特别对于丢弃桶中所有数据情况，Sink能通过查询结果和签名和集来检测其完整性.

2) 通信量

ISafeVRQ方案中对每个非空桶增加了2个桶标签，根据对SafeVRQ的分析，节点Si中非空桶数为，因此，ISafeVRQ方案对于节点Si每次传输增加的通信量为，即

(8)

对于签名集，两方案相同，即TI_i, t, Φ=Ti, t, Φ，其通信花费为：.

5 实验与分析

在文献[8]的传感器网络模拟器基础上，模拟执行笔者提出的SafeVRQ和ISafeVRQ，并对这2种方案与文献[3]中提出的方案进行了比较.

假设每个单元网络覆盖区域为100 m×100 m，节点数为100，通信半径为20 m，使用128位的HMAC-MD5作为计算编码数的Hash功能，使用64位的RC5对数据进行加解密，平均跳数为8，g为10.假设所有桶被查询的概率γj, t相等，且pγ=0.5，所有桶被丢弃数据的概率δj, t相等为pδ=0.1.

1) 桶数的影响：随着桶数的增大会极大增加空桶的数量，因此Encoding通信量增幅最大. SafeVRQ和ISafeVRQ签名和集的大小与桶数成正比，增幅远小于Encoding.随着桶数的增加，空桶的比例增大，丢弃桶中所有数据的攻击方式对SafeVRQ影响较大，但ISafeVRQ克服了该弱点，如图 1所示.

图 1 桶数对通信量的影响

2) 平均跳数的影响：SafeVRQ对孩子节点的数字签名集合进行融合，因此签名相当于1跳，所以平均跳数对通信量基本没有影响，ISafeVRQ方案通信量的增长主要是由pb和nb产生，通信量增幅很小，但Encoding每跳都需要传输所有空桶的编码值，因此额外通信量与跳数成线性关系，增幅较高.检测率：由于平均跳数对各种信息没有影响，所以检测率没有变化，如图 2所示.

图 2 平均跳数对通信量的影响

3) 查询范围(pγ)和丢弃率(pδ)对检测率的影响：随着pγ的增大，查询结果不完整概率增大，检测率随之增大，查询范围在50%以上时SafeVRQ检测率较高，ISafeVRQ检测率基本接近1，如图 3所示.随着pδ的增加，3个方案的检测率随之提高，如图 4所示，当pδ在10%以上时检测率都比较高.

图 3 pγ对检测率的影响

图 4 pδ对检测率的影响
6 结束语

近来，两层无线传感器网络中范围查询的安全问题已成为新的研究热点.笔者提出用SafeVRQ和ISafeVRQ对检测率和通信量这2个关键的性能指标进行了详细的理论分析和实验验证.通过采用签名融合技术，SafeVRQ和ISafeVRQ极大地降低了通信量.在保证数据的机密性、返回结果的真实性的基础上，本研究提出的2种方案在花费较低的通信量的情况下，取得较高的检测率.

参考文献
[1] Gnawali O, Jang K Y, Paek J, et al. The tenet architecture for tiered sensor networks[C]//2006 the International Conference on Embedded Networked Sensor Systems (SenSys 2006). Colorado: ACM, 2006: 153-166.
[2] 蒋文涛, 吕俊伟, 杨曙辉, 等. 传感器网络中面向数据聚集的有向分簇算法[J]. 北京邮电大学学报, 2012, 35(3): 25–29.
JIANG Wen-tao, LU Jun-wei, YANG Shu-hui, et al. A directional clustering algorithm for data aggregation in sensor networks[J].Journal of Beijing University of Posts and Telecommunications, 2012, 35(3): 25–29.
[3] Shi Jing, Zhang Rui, Zhang Yanchao. A spatiotemporal approach for secure range queries in tiered sensor networks[J].IEEE Trans. Wireless Commun, 2011, 10(1): 264–273. doi: 10.1109/TWC.2010.102210.100548
[4] Sheng Bo, Li Qun. Verifiable privacy-preserving sensor network storage for range query[J].IEEE Transactions on Mobile Computing, 2011, 10(9): 1312–1326. doi: 10.1109/TMC.2010.236
[5] Zhang Rui, Shi Jing, Liu Yunzhong, et al. Verifiable fine-grained top-k queries in tiered sensor networks[C]//2010 the IEEE Conference on Computer Communications (INFOCOM2010). San Diego: IEEE, 2010: 1199-1207.
[6] Hore B, Mehrotra S, Tsudik G. A privacy-preserving index for range queries[C]//2004 the International Conference on Very Large Data Bases (VLDB2004). Toronto: ACM, 2004: 720-731.
[7] Boneh D, Gentry C, Lynn B, et al. Aggregate and verifiably encrypted signatures from bilinear maps[C]//2003 the Int'l Conf. Theory and Applications of Cryptographic Techniques (Eurocrypt2003). Berlin: Springer, 2003: 416-432.
[8] Coman A, Nascimento M A, Sander J A framework for spatio-temporal query processing over wireless sensor networks[C]//2004 the International Conference on Very Large Data Bases(VLDB2004). Toronto: ACM, 2004: 104-110.