面向WSN的安全范围查询协议研究

摘 要： 针对两层无线传感器网络中范围查询所要求的低能耗和高隐私保护，提出了一种具有隐私和完整性保护的安全范围查询协议：SPQ。SPQ是由数据加密、前缀成员验证、概率邻居验证、查询传输过程分离等技术组成，能够在保证不泄露隐私的情况下完成范围查询。分析和仿真结果表明，相对于其他安全协议，SPQ在保证范围查询安全性的同时具有更低能耗。

关键词： 无线传感器网络； 范围查询； 能耗； 隐私保护

中图分类号： TN915.08?34； TP393 文献标识码： A 文章编号： 1004?373X（2014）11?0080?05

Abstract： For low power consumption and high privacy protection required for range query in two?tiered wireless sensor networks， a secure range query protocol with privacy and integrity protection called SPQ （Secure probabilistic range query） is proposed. SPQ consists of data encryption， prefix membership verification， probabilistic neighborhoods verification， and separation technology of query and transmission process. It can ensure the achievement of range query without privacy reveal. Analyses and simulation results show that SPQ has the lower power consumption relative to other security protocols under the precondition to guarantee the security of range query.

Keywords： wireless sensor network； range query； power consumption； privacy protection

0 引 言

随着无线传感器网络（Wireless Sensor Networks，WSNs）的不断应用发展，在其上的数据查询任务越来越多，数据查询过程中的安全要求也愈发显得重要起来。WSNs数据查询可以快速将WSNs收集到的部分有效数据或特定数据聚集到Sink（汇聚节点），再由Sink对查询结果进行分析计算以便控制WSNs或做出其他决策。WSNs数据查询主要分为两大类，一是简单查询，对WSNs收集数据进行较简单的查询操作， 目前的研究热点主要是范围查询、Top?k查询、skyline查询和基于类型查询，这类查询简单且通用性强，可适用于不同WSNs具有较好的研究价值；二是复杂查询，查询过程复杂，需要专门的查询策略，通用性不强，一般针对特定WSNs。WSNs范围查询就是查询给定区间范围的数据查询。该查询简单实用，应用范围广，而且对其研究也会对其他简单查询有指导意义。

本文提出了一种基于WSNs的安全数据查询协议SPQ（Secure probabilistic range query），通过前缀成员验证技术[1?2]保证查询隐私性，利用概率邻居验证技术[3]进行查询结果完整性验证；并使查询过程和传输结果过程分离尽可能减少通信量（减少能耗），增强对WSNs的适用性。

1 相关工作

WSNs安全范围查询的研究内容包括以下两个方面：查询过程隐私性保护和查询结果完整性验证。其中前者需要满足：

① 普通传感器节点收集到的数据不会丢失、泄露、被篡改、被伪造；

② 存储节点存储的数据和查询请求在查询过程中不会丢失、泄露、被篡改、被伪造；

③ 数据和查询请求以及查询结果在传输过程中被窃取也不会泄露隐私。

同时后者需要满足：

① 满足查询条件的数据要全部包含在查询结果中；

② 查询结果一旦丢失、被删改、被伪造都可以被Sink节点有效检测出来。

文献[4]首次提出了基于桶模式[5?6]的考虑隐私保护的范围查询，文献[7] 改进了该范围查询，提出了Hybrid时空交叉验证方法。文献[8] 提出了SMQ子树采样技术来完成范围查询的隐私保护。密歇根州立大学的CHEN Fei和LIU A X提出了一种全新的范围查询策略，即基于前缀成员验证技术的SafeQ[9]。

对WSNs范围查询隐私保护研究的主流协议有两类，即基于桶模式和基于前缀成员验证技术。基于桶模式的范围查询有一个天然的缺陷，即一旦存储节点被俘获，虽然具体数据和查询结果泄露不了，但是攻击者可以根据分桶情况大概推断出查询的数据范围。所以这就从根本上决定了基于桶模式的范围查询的安全水平有限；基于前缀成员验证技术的SafeQ范围查询的安全性比桶模式完善，但其仍存在能耗较高的问题，由于传感器网络具有能量受限的关键特性，这就成了SafeQ推广的一个瓶颈。

本文提出的SPQ属于第二类协议，天然上就比基于桶模式的协议有更高的安全性。另外SPQ通过改变查询策略和完整性验证方法来进一步降低能耗，使得SPQ有更低的能耗。

2 网络模型

WSNs安全数据查询即隐私保护研究主要是基于两层传感器网络模型[10]，如图1所示，范围查询也不例外。SPQ就是基于该模型的协议。

图1 两层无线传感器网络模型

如图1所示，该网络模型高层由存储节点组成，存储节点（Storage Node）就是有较大存储空间和较强计算能力的传感器节点；底层由大量的普通传感器节点组成，普通节点资源受限且成本低。数据的查询过程如下：用户的查询要求（Query）通过Sink传到存储节点，普通节点收集到数据后将数据传到存储节点存储，然后在存储节点上进行查询计算，最后将满足条件的查询结果（Reply）回传给Sink并最终返回给用户。

WSNs数据查询选用两层模型有如下好处：普通传感器节点只需要将所有采集到的数据传输给附近的存储节点而不是通过很长的路径传输给Sink节点，这大大降低了能耗，避免Sink节点遭遇通信瓶颈；Sink只和存储节点通信并可得到查询结果，这使查询过程更加有效率。

3 WSNs安全范围查询协议

对于WSNs来说，能耗大小往往是考虑是否实施安全策略的掣肘。SPQ的目标就是在保证查询的安全同时尽量减少能耗。

3.1 关键技术

3.1.1 数据加密

SPQ中，每个普通传感器节点[si]都将和Sink共享一个密钥[ki，]并且[ki]定期更换。普通节点[si]收集到的数据[d1，…，dn]在查询过程中都将被[ki]加密，即便是完成查询过程并收集查询结果上传给Sink的存储节点也无法得到具体的数据信息，这就保证了数据的私密性。

3.1.2 前缀成员验证

存储节点在无法识别具体数据的情况下，仍然需要完成查询过程，这就应用了前缀成员验证技术。前缀成员验证技术就是将验证数据是否符合范围查询的条件转化为比较数据项的大小。例如判断数据12是否符合范围查询。12的二进制表示是1100，首先对其构造前缀家族得到{1100 110* 11** 1*** ****}，然后再进行前缀数值化得到{11001 11010 11100 11000 10000}；于此同时[11，15]的二进制表示是[1011，1111]，即{1011 1100 1101 1110 1111}，首先进行前缀转化得到{1011 11**}，再对其前缀数值化得到{10111 11100}。在最终的前缀数值化组里，他们有相同的项11100，这就表明数据12符合范围查询[11，15]。反之如果其中没有相同数据项，则说明该数据不符合范围查询条件。在SPQ中，用三个哈希函数来应用前缀成员验证技术。三个哈希函数分别是[Φ，Ψ，Ω。]

3.1.3 概率邻居验证

SPQ的查询结果完整性验证通过概率邻居验证技术实现。即普通节点[si]得到查询结果后，生成消息（t，i，len），并将该消息传给附近邻居节点。其中t是时间段，i是传感器编号，len是满足查询的数据项数目。然后每个邻居节点以一定概率p随机加入（t，i，len）到自己的查询结果中并加密上传，Sink接收到查询结果后根据各个（t，i，len）进行查询结果完整性验证。

3.2 SPQ一维数据查询过程

WSNs范围查询通常可以根据数据项维度的不同分为一维数据查询和多维数据查询。一维数据查询过程最简单，随着维度的增加，往往多维数据查询的能量消耗呈指数增长。SPQ就要尽量避免这种情况，改善不同维度的能耗情况。对一维数据查询时，SPQ实现过程如下伪代码所示。其中Sink为汇聚节点，Storage Node为存储节点，[si，sj]为普通节点。

具体查询细节如下：

① 普通节点[si]收集到一定数据并排序后得到[d1，d2，…，dn，]应用第一个哈希函数[Ψ]加密得到定长的消息编码[Ψ（d1，d2，…，dn）]并发送给存储节点。当Sink想要做出查询[{t，[a，b]}]时，会先用另外一个函数[Ω]对查询范围进行处理最终将会发送[{t，Ω（[a，b]）}]到存储节点。

② 存储节点处理查询时用到第三个函数[Φ，]当[Φ（j，Ψ（d1，d2，…，dn），Ω（[a，b]））]为真时，说明[dj]满足查询条件；为假时说明[dj]不满足查询条件，应当舍弃。存储节点将满足查询条件的最小数据和最大编号以及数据个数（min_d，max_d，len）i反馈给[si。]

③[si]在收到反馈结果后，找出队列中包括编号min_d和max_d的所有中间数据[dmin_d，…，dmax_d，]并加入dmin-1（如min_d-1<1，则取[dmin_d-1=]-1），[dmax_d+1]（如[max_d+1>n，]则取[dmax_d+1=∞]）。[si]生成消息（t，i，len），并将该消息传给附近邻居节点。其中t是时间段，i是传感器编号，len是满足查询的数据数目。

④ 假如[si]收到邻居节点[si_neighbor]发送来的消息（t，i_neighbor，len），将以一定概率p将此消息加入到自己需上传的查询结果中去，即最终上传{（t，i_neighbor，len）p，dmin_d，[…]，dmax_d} ki。其中[ki]是[si]和Sink共享的密钥。

上传数据经过存储节点最终传到Sink，Sink再对所有查询结果进行完整性验证，至此SPQ结束。

3.3 SPQ多维数据查询过程

因为现实应用中，范围查询应用场景往往是针对多维数据而言的，所以将SPQ协议应用到对多维数据查询也是非常必要的。下面简述多维数据下SPQ的查询过程：

①普通节点[si]收集到[n个m]维数据[（d11，d21，…，][dm1），]…，[（d1n，d2n，…，dmn）]后，应用第一个哈希函数Ψ加密得到m个定长的消息编码[Ψ（d11，d12，…，d1n），][Ψ（d21，d22，…，d2n），][Ψ（dm1，dm2，…，dmn）]并发送给存储节点。当Sink想要做出查询[{t，[a1，b1]，…，[am，bm]}]时，会先用另外一个函数[Ω]对查询范围进行处理最终将会发送[{t，Ω（[a1，b1]），…，][Ω（[am，bm]）}]到存储节点。

② 存储节点处理查询时用到第三个函数Φ，当[Φ（j，Ψ（dt1，…，dtn），Ω（[at，bt]））]为真时（其中[1≤t≤m]），说明[dj]满足维度[t]上的查询条件；为假时说明[dj]不满足维度[t]的查询条件，应当舍弃。当把所有维度做完后，求编号的交集就得到最终的查询结果，存储节点将这些满足查询条件的数据编号最值{（min_d1，max_d1），…， （min_dm，min_dm），len}反馈给[si。]

[si]在查询过程中对上传数据按随机某个维度[t]的值进行排序。在收到反馈结果后，根据查询结果找出所有符合条件数据并加密。

③、④与一维数据查询过程相同。

4 性能分析

4.1 安全性分析

因为普通节点数据量小，如被俘获对全局查询结果影响不大，所以现在主要考虑存储节点被俘后的情况，以此来验证SPQ的安全性能。

由于查询结果已加密，所以存储被俘后无法获得有效的查询数据。被俘存储节点可以做的工作主要是丢弃数据和更改查询结果（min_d，max_d，len）i。这两者破坏都可以由Sink在完整性验证时检测出来。

4.2 能耗分析

SPQ相对之前的范围查询协议在能耗上有改进，一个原因是由于查询过程和传输查询结果过程分离的结果，这样一来不符合查询条件的数据将不会上传到存储节点，减低了很大一部分数据传输量，即减少了普通节点发送数据消耗的能量，又降低了存储节点接收数据所需的能耗，明显降低了安全范围查询的能量消耗。

4.3 仿真实验

本文使用原始数据集在Matlab平台上对SPQ和SafeQ进行仿真，在长宽均为300 m的区域有100个普通节点随机分布，4个存储节点较均匀分布，居中一个Sink节点。假设传感器节点有效传输距离为75 m，利用TAG（Tiny Aggregation Service for Ad Hoc Sensor Network）算法建立路由路径，每个普通节点向存储节点传输数据平均需要1.8跳。每个节点平均有20个邻居节点，向每个邻居节点发送验证消息的概率为0.4。仿真实验中，能耗值是指具体能耗除以时间，即类似功率的一个衡量能耗水平的值。

实验主要是对比SPQ和SafeQ对不同维度数据进行查询时的能耗。为了保证实验结果的正确性，所有实验采用相同的真实数据集，一维数据集和二维数据集是从三维数据集中剥离的一个维度和两个维度，即不同维度的实验在单位时间内接收到的查询结果数据项数量应该是相同的。

（1） 一维数据查询

第一组实验是在一维数据查询下，SPQ和SafeQ的能耗对比情况，如图2，图3所示。

通过实验结果图对比知，针对一维数据查询时，在相同数据集来源情况下，SPQ普通节点能耗值比SafeQ低3.2倍；SPQ存储节点能耗值比SafeQ低2.5倍。在一维数据情况下，SPQ能耗水平明显低于SafeQ。

（2） 多维数据查询

第二组实验是在多维数据查询下（本实验使用三维数据），SPQ和SafeQ的对比情况，如图4，图5所示。

通过实验二结果图对比知，针对三维数据查询时，在相同数据集来源情况下，SPQ普通节点能耗值比SafeQ低3.64倍；SPQ存储节点能耗值比SafeQ低1.17倍。在三维数据情况下，SPQ能耗水平也低于SafeQ。

（3） 不同维度数据查询对比

第三组实验是在不同维度数据查询下，SPQ的表现情况对比，如图6，图7所示。

通过结果图对比知，在相同数据集来源情况下，SPQ普通节点对三种维度数据查询时能耗成线性增长；SPQ存储节点对三种维度数据查询时能耗也是成线性增长。即在多维数据查询情况下，SPQ的节能能力同样突出。

5 结 语

本文提出的SPQ协议的数据隐私性保护通过前缀成员验证技术来实现，数据完整性验证则主要由概率邻居验证技术来完成，并通过一系列通信策略优化减少通信量即能耗，使其优于现有的SafeQ和基于桶模式的范围查询。虽然SPQ相比现有协议能耗更加低，安全性能也很好，但是相比不加隐私保护的查询策略，能耗仍然偏高，需进一步寻找安全策略或通信方式减少能耗，使安全数据查询可以更加好的推广。

参考文献

[1] CHENG J， YANG Hao， WONG S， et al. Design and implementation of cross?domain cooperative firewall [C]// Procee?dings of IEEE International Conference on Network Protocols. Beijing，China： IEEE， 2007： 284?293.

[2] LIU A X， CHEN Fei. Collaborative enforcement of firewall policies in virtual private networks [C]// Proceedings of PODC. Toronto， Canada： PODC， 2008： 95?104.

[3]范永健，陈红.两层传感器网络中可验证隐私保护Top?k查询协议[J].计算机学报，2012，35（3）：423?433.

[4] SHENG Bo， LI Qun. Verifiable privacy?preserving sensor networks storage for range query [J]. IEEE Transactions on Mobile Computing， 2011， 10（9）： 1312?1326.

[5] HACIGUMUS H， IYER B R， Li C， et al. Executing SQL over encrypted data in the database service provider model [C]// Proceedings of SIGMOD. Madison， Wisconsin，USA： SIGMOD， 2002： 216?227.

[6] HORE B， MEHROTRA S，TSUDIK G..A privacy?preserving index for range queries [C]// Proceedings of VLDB. Toronto， Ca?nada： VLDB， 2004： 720?731.

[7] ZHANG Rui， SHI Jing， ZHANG Yan?chao. Secure cooperative data storage and query processing in unattended tiered sensor networks [J]. IEEE Journal on Selected Areas in Communications， 2012， 30（2）： 433?441.

[8] YU C， 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.

[9] CHEN Fei， LIU A X. Privacy? and integrity?preserving range queries in sensor networks [J]. IEEE?ACM Transactions on Networking， 2012， 20（6）： 1774?1787.

[10] RATNASAMY S， KARP B， SHENKER S， et al. Data?centric storage in sensornets with GHT （geographic hash table） [J]. Mobile Networks and Applications， 2003， 8（4）： 427?442.