2. 安徽师范大学 数学计算机科学学院, 安徽 芜湖 241003;
3. 南京邮电大学 计算机学院, 南京 210013
针对两层传感器网络环境,提出了一种安全高效的范围查询算法. 在数据存储阶段,传感节点对感知数据进行加密处理,并利用保序函数生成保序编码,然后将密文和编码数据上传至存储节点. 在查询处理阶段,Sink通过克莱姆法则将查询范围转换成下上限多项式,并将查询请求信息发送给存储节点;存储节点通过多项式信息和保序编码,实现无须明文数值参与下的大小比较,从而确定查询结果,并返回给Sink;Sink获得查询结果,并对感知数据进行真实性和完整性验证. 理论分析和实验结果表明,该算法能够保证感知数据、查询结果和目标范围区间的隐私,且与现有方法相比具有更高的能效.
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
A secure and energy-efficient range query algorithm in two-tiered wireless sensor networks was proposed. In data storing phase, each sensor node encrypts its sensory data, generates order-preserving encoding by employing order-preserving function and then transmits the encoded and encrypted data to its corresponding storage node. In query processing phase, the Sink converts query range into the lower bound and upper bound of polynomials through Cramer's rule and then sends the query request to the storage node. According to the order-preserving encoding and polynomial information, the storage node implements comparison without knowing the actual values of the collected data and queried range and thus obtains the final query result which is then returned back to Sink. Next, The Sink acquires the final query result and verifies the validity and integrity of sensory data. Analysis and experiment show that the algorithm can ensure the privacy of the sensory data, the query result and the query range, and has an advantage over the existing methods in the energy consumption.
无线传感器网络(WSN,wireless sensor networks)是由大量资源受限的传感节点构成的，通过数据聚集和查询等操作实现监控和侦查等功能，具有广泛的应用场景[1]. 由于WSN往往部署在野外地区，难以维护，使得WSN应用面临严重的安全问题，研究和解决这类安全问题，对拓展WSN的应用领域具有重要的意义.
由于两层WSN具有路由简单、使用寿命长等优点，已成为新的研究热点. 很多学者提出了基于两层WSN的安全数据查询方案[2, 3, 4, 5, 6, 7]. 这些方案通过数据加密以保证数据的机密性和正确性，因此，查询结果完整性检测是各方案的研究重点. Shi等[2]采用时空方法来检测查询结果的完整性. Sheng等[3]提出编码数技术解决查询结果完整性检测问题. Chen等[4]提出的SafeQ方案利用前缀成员验证技术实现完整性检测. 笔者通过保序函数和克莱姆法则求多项式的方法，在不泄露隐私信息的情况下，精确地完成传感器网络范围查询，并通过加密链和保序编码集方法完成数据完整性检测.
1 预备知识 1.1 网络模型两层WSN由传感节点、存储节点和Sink三种类型的节点构成. 大量的传感节点构成下层网络，负责感知数据，特点是价格便宜、资源有限；少量资源丰富的存储节点构成上层网络，负责存储感知数据，处理Sink的查询请求. 两层WSN被划分为若干个单元，每个单元由一个存储节点和若干个传感节点构成，每个单元内部节点构成一个融合树，其中存储节点为根节点，称为单元头节点.
1.2 攻击模型两层WSN中，由于存储节点不仅拥有大量数据，且担负执行Sink的查询请求，使得存储节点往往成为主要的攻击目标. 因此，笔者重点关注存储节点被捕获的隐私保护措施，被捕获的存储节点可进行3种攻击：① 获取存储节点中存储的所有数据；② 伪造数据返回给Sink；③ 返回部分查询结果给Sink.
1.3 查询模型范围查询的流程：传感节点将感知数据传输到存储节点上存储，当Sink进行范围查询时，直接对存储节点进行查询请求，存储节点根据Sink的查询范围、传感节点ID和查询周期返回查询结果给Sink. 范围查询Q模型形式化表示为
| $ Q=\left( cell=C \right)\wedge \left( epoch=t \right)\wedge \left( D \right) $ |
其中：C为查询所在单元，t为查询周期，D为查询范围. 范围查询Q=(C,t,D)在指定单元指定周期内查询所有属于范围D内的数据.
2 安全高效的范围查询算法下面给出安全高效的范围查询(SERQ,secure and energy-efficient range query)算法的具体过程，其基本思想主要包括如下6个阶段.
1) 前期准备阶段. Sink与每个传感节点ni,j共享密钥Ki,j以保证感知数据的机密性和真实性，其中j表示节点所在单元ID，i表示单元内节点ID，同时还共享保序函数Fi,j(x). 因为Sink对每个单元操作是相同的，且所有操作都在同一个单元内进行，所以，密钥和保序函数分别简写为Ki和Fi(x). 共享保序函数使得存储节点能准确返回查询结果.
2) 网络拓扑结构构建阶段. 两层WSN被划分为若干个单元，每个单元由1个存储节点和若干个传感节点构成. 每个单元内部节点构成一个路由树，其中存储节点为根节点.
3) 数据存储阶段. 传感节点对1个周期内感知到的数据进行排序，并按数据升(降)序的顺序对数据加密构成加密数据集. 同时，通过保序函数对数据进行编码形成保序编码集.
4) 范围查询请求阶段. Sink进行查询操作Q=(C,t,D). Sink将查询请求发送给每个单元的存储节点，查询信息包括周期号和转换后的查询范围.
5) 查询结果返回阶段. 当存储节点接收到Sink的查询请求后，存储节点将每个传感节点中保序编码集的编码与其对应的查询范围进行比较，如果在查询范围内，则存储节点将该编码以及对应的加密数据分别放入返回编码集和返回加密数据集并传输给Sink.
6) 验证阶段. Sink收到查询结果后，通过与传感节点共享的密钥对密文集进行解密获得原数据，通过重构保序编码集来判断查询结果的完整性.
2.1 数据存储阶段在时间周期t结束后，每个传感节点ni进行如下操作.
步骤1 节点对周期t获得的感知数据排序，即d1<…<dm；并用密钥对感知数据进行加密，得到(d1)Ki,…,(dm)Ki.
步骤2 构造新数据以实现完整性检测. 新数据由两部分组成，分别是原数据和原数据与其下一个原数据之差值，且每个传感节点生成两个随机的下限数x0和上限数xm+1(满足x0<min∧xm+1>max，其中感知数据的数值范围为[min,max]，m为感知数据个数). 例如，传感节点有两个感知数据x1和x2 (x1< x2)，并生成下上限数x0和x3，则构造的新数据为x0‖ x1－x0,x1‖ x2－x1,x2‖ x3－x2,x3‖random，其中‖为连接符. 为了保证新的数据仍然是有序的，将所有右半部分的数据的位数设置成相等的. 例如，假设所有数据之间最大差值为5位，x2－x1和x3－x2值分别为5和2，则两差值分别表示为00101和00010.
步骤3 通过保序函数对新数据进行编码得到编码集. 采用文献[8]保序函数对数据编码，编码函数为Fi(x)，因此其编码集为
| $ \begin{align} & {{C}_{i,t}}=\left\{ i,t,\left\{ {{F}_{i}}\left( {{d}_{j}}\left\| {{\left( {{d}_{j+1}}-{{d}_{j}} \right)}_{r}} \right. \right)\left| j=0,1,\cdots ,m,\right. \right. \right. \\ & \ \ \ \ \ \ \ \ \ \ \ \ \left. \left. {{F}_{i}}\left( {{d}_{m+1}}\left\| {{\left( random \right)}_{r}} \right. \right) \right\} \right\} \\ \end{align} $ | (1) |
其中r表示将所有差值转换为r位二进制.
步骤4 传输给存储节点. 传感节点将加密数据集Ei,t={i,t,{(dj|j=0,1,…,m)Ki}}和保序编码集Ci,t传输给储存节点.
2.2 范围查询请求范围查询请求阶段，Sink进行查询操作，Sink将查询请求Q分别发送给每个单元的存储节点，查询信息包括周期号和转换后的查询范围. 因为存储节点上的存储信息为加密数据集和保序编码集，为了使存储节点能够精确返回查询结果，Sink需要通过保序函数将查询范围对应到每个传感节点，即对查询范围进行转换，具体过程如下.
步骤1 查询范围转换. 对于单元C，转换每个节点ni的查询范围[a,b]，即通过保序函数得到查询范围(ai,bi)，其中ai=Fi(a‖(1…1)r)，bi= Fi(b‖(0…0)r).
步骤2 构造二元组集. 对单元C内所有节点进行转换得到2个二元组集，下限二元组BL={(i,ai)|i=1,2,…,N(N为单元C内传感节点个数)}，上限二元组BU={(i,bi)|i=1,2,…,N}.
步骤3 构造下限和上限多项式. 通过克莱姆法则分别求出下限二元组和上限二元组对应的下限多项式和上限多项式. 构造过程：通过二元组集(i,ai)生成Ax=y，其中y=(a1,a2,…,aN)，A为根据节点ID号得到的范德蒙矩阵，x=(m0,m1,…,mn)T，然后通过克莱姆法则求出m0,m1,…,mn，得出下限多项式FLC(x)，同理可得上限多项式FUC(x).
步骤4 将查询请求(t,FLC(x),FUC(x))传输给C单元内的存储节点.
2.3 查询处理在查询处理阶段，存储节点首先根据查询指令Q中的下限和上限多项式获得单元内每个传感节点对应的查询范围，与保序编码集的数据进行比较，从而确定符合查询结果的密文数据集和编码集并返回给Sink；Sink解密存储节点返回的密文数据，进而得到最终的查询结果.
1) 存储节点. 当收到Sink的查询请求Q=(t,FLC(x),FUC(x))后，存储节点对单元内每个传感节点ni进行如下操作.
假设ERi为存储ni的密文的集合变量，CRi为编码的集合变量，初始状态下ERi= $ \varnothing $、CRi=$ \varnothing $.
① 根据下上限多项式和ID号求出节点ni对应的查询范围，ai =FLC(i)，bi =FUC(i).
② 存储节点依次获取ni在t内上传的密文数据和编码Fi(dj‖(dj+1－dj)r)，并与ai和bi比较大小关系，若ai≤Fi(dj‖(dj+1－dj)r)≤bi，将(dj)Ki加入ERi,t，Fi(dj‖(dj+1－dj)r)加入CRi,t.
③ 为了实现完整性验证，存储节点需要将查询范围内两端的前驱和后继数据及对应的编码分别放入ERi,t和CRi,t中，如果没有数据符合范围查询，则将范围查询两端最近的2个数据分别放入ERi,t和CRi,t中.
④ 存储节点将ERi,t和CRi,t发送给Sink.
定理1 SERQ算法的查询结果正确.
证明 已知Fi(x)为保序函数，且ai= Fi(a‖(1…1)r)，bi= Fi(b‖(0…0)r). 若ai ≤ Fi(dj‖(dj+1－dj)r) ≤ bi成立，则 (a‖(1…1)r) ≤ (dj‖(dj+1－dj)r)≤(b‖(0…0)r).
因此，a≤dj≤b 成立，即dj∈[a,b].
同理，当Fi(dj‖(dj+1－dj)r)<ai或Fi(dj‖(dj+1－dj)r)>bi时，有dj<a或dj>b，即dj$ \notin $[a,b].
证毕.
2) Sink. 被俘获的存储节点可进行如返回伪造数据或部分结果等攻击，因此，Sink对返回的查询结果进行验证，操作步骤如下.
① Sink通过与ni共享密钥Ki对ERi,t进行解密得到{d′1,d′2,…,d′m}，Sink很容易判断这些数据是否正确和真实. 如果数据是正确和真实的，则进一步执行操作②.
② Sink通过与ni共享的保序函数Fi(x)对解密后的数据进行保序编码重构得到CNi,t. 然后将CNi,t与CRi,t进行比较，如果两集合相同则返回结果是完整的，否则不完整. Sink可以根据完整性检测结果推导出存储节点是否被俘获.
上述算法可实现一维数据的范围查询，对于多维数据的范围查询而言，由于多维数据本质上是由多个一维数据组合而成的，所以通过上述算法执行过程的扩展实现多维数据的隐私保护范围查询.
2.4 算法分析 2.4.1 安全性分析下面分别从感知数据的隐私性和查询范围的隐私性2个角度分析算法的隐私安全性.
1) 感知数据的隐私性. 传感节点将加密数据集和保序编码集传输给存储节点，因此，存储节点只能通过加密数据集和保序编码集推导出原数据.
① 加密数据集. 传感节点将感知数据传输给存储节点之前，对感知数据进行了加密，且密钥仅与Sink共享，所以，存储节点获得明文数据的难度与破解加密算法相同. 因此，存储节点以及传输路径上的其他存储节点无法通过加密数据获得明文数据.
② 保序编码集. 保序函数Fi(x)中添加了noise并进行多次迭代使得攻击者不能通过Fi(dj‖(dj+1－dj)r)推导出dj‖(dj+1－dj)r. 同时，即使获得数据dj‖(dj+1－dj)r，在不知道r的情况下也不能推导出dj. 假设Fi(x)泄露的概率为δ，则数据泄露的概率为δ/r.
由①和②可知，所提出的范围查询算法能确保感知数据的隐私性.
2) 查询范围区间的隐私性. Sink传输给存储节点为下限和上限多项式，存储节点虽然通过多项式和节点ID号获得保序函数处理后的范围[ai,bi]，但是从上面的分析可知保序函数具有单向性，因此，存储节点无法通过[ai,bi]获取原始的查询范围[a,b].
2.4.2 能耗分析相对于传感节点，存储节点资源丰富，因此网络的生命周期主要受传感节点的能耗影响. 为了简化处理，主要从传感节点能耗角度给出算法的能耗分析.
SERQ算法中，传感节点能耗主要包含两方面：①通信能耗ET，主要由发送加密数据集、编码集和接收消息构成；②计算能耗EC，由加密和保序函数计算构成. 因此，传感节点的总能耗为
| $ {{E}_{all}}={{E}_{T}}+{{E}_{C}} $ | (2) |
以单元为单位，假设单元内有N个传感节点，传感节点单个周期内产生m个感知数据，感知数据的长度为ω bit，节点ID号和周期数据长度为lid bit和lt bit，单个密文数据和通过保序函数得到的编码的长度分别为α bit和β bit. 加密运算和保序函数运算的单位能耗分别为ec和eop，传输和接收1 bit数据的平均能耗分别为es和er，传感节点到存储节点的平均跳数为L.
由算法的存储数据方案可知，每个传感节点ni将上传m+2个密文数据及对应的保序函数产生的编码，其通信能耗为
| $ {{E}_{T}}=\sum\limits_{i=1}^{N}{\left( {{l}_{id}}+{{l}_{t}}+\left( m+2 \right)\left( \alpha +\beta \right) \right)\left( L{{e}_{s}}+\left( L-1 \right){{e}_{r}} \right)} $ | (3) |
每个传感节点需要对m+2个数据加密和编码，因此，其计算能耗为
| $ {{E}_{c}}=N\left( m+2 \right)\left( {{e}_{c}}+{{e}_{op}} \right) $ | (4) |
由式(3)和式(4)可得
| $ \begin{array}{l} {E_{all}} = N\left( {\left( {{l_{id}} + {l_t} + \left( {m + 2} \right)\left( {\alpha + \beta } \right)} \right) \times } \right.\\ \left. {\left( {L{e_s} + \left( {L - 1} \right){e_r}} \right) + \left( {m + 2} \right)\left( {{e_c} + {e_{op}}} \right)} \right) \end{array} $ | (5) |
在数据存储阶段，传感节点构造新数据并进行编码，由于新数据与相邻数据相关，所以产生的编码集构成编码链，使得Sink接收到查询结果后，可以对返回结果进行完整性验证. 被捕获的存储节点可进行以下2种攻击.
1) 攻击者将一些伪造数据放入查询结果中. 查询结果包括数据密文和与前后数据项相关联的编码链，因此，被捕获的存储节点在不知道密钥和保序函数信息的情况下不能正确伪造这些数据项.
2) 删除查询结果中部分数据. 当进行范围查询时，存储节点需要将满足查询条件的数据和编码放入ER和CR中. 当被捕获的存储节点丢弃部分数据时，存储节点需要重新编辑被删除数据的下一个数据项的编码. 由于存储节点不能获取原始的感知数据，编码长度为β bit，所以完整性检测的概率为1－1/2β. 如果没有数据项满足范围查询，存储节点需要将di和dj的密文和编码传输给Sink，其中di(dj)是小(大)于查询范围下(上)限最近数据项，同样需要重构编码，完整性检测的概率为1－1/2β. 若有k项不连续的数据项被删除，则完整性检测的概率为1－1/2βk. 因此，只要β足够大，则检测的概率接近于1.
3 实验及分析模拟执行提出的SERQ算法与Encoding[3]算法在节点数、周期内感知数据等参数不同情况下的能耗进行比较. 实验环境为Core i3-3220CPU，4 GB内存；软件环境为Win7操作系统，VS. NET 2010和Matlab. 同时，采用文献[6]给出的TelosB参数，传输和接收1 bit的能耗分别为es=0.72 μJ和er=0.81 μJ，利用RC4对数据进行加解密，10 bit数据能耗为8.92 μJ. 其他参数如表 1所示.
 | 表1 实验参数的默认值 |
在每组实验中，仿真系统随机分布传感节点，并随机产生一个拓扑结构网络，计算范围查询的能耗，循环执行20组网络能耗，并取其平均能耗作为范围查询的总能耗，实验结果及分析如下.
1) 当传感节点数N变化时，节点的能耗如图 1所示. 由 图 1可知，随着传感节点数N增加导致整个网络需要传输的感知数据量和编码量也增大，传感节点的平均跳数也增大，因此SERQ和Encoding的总能耗都随之增长. 同时，SERQ能量消耗远低于Encoding，且增长幅度也低于Encoding，约为55%.
|
图1 传感器节点N对能量消耗的影响 |
Encoding算法将感知数据放入m个桶中，不仅泄露了感知数据的分布情况，同时传输的信息中包括桶标签和非查询范围内的数据(桶方案是非精确性查询)，增加了通信量. 另外，Encoding需要对每个桶进行编码，并进行大量的Hash运算，计算能耗远大于SERQ算法中简单的算术运算. 因此，SERQ在通信量和计算能耗上远比Encoding少.
2) 当单位周期内传感节点产生的数据量m变大时，传感节点的能耗如 图 2所示. 由图 2可知，当m增大时，由于传感节点需要上传给存储节点的感知数据数量增多，使得SERQ和Encoding两算法的总能耗增加；由于生成用于完整性验证的编码计算能耗SERQ比Encoding小，同时SERQ不需要传输桶信息等通信量，使得SERQ节省能量约45%.
|
图2 感知数据对能量消耗的影响 |
因此，与Encoding相比，SERQ算法对传感节点总能耗有显著的降低. 同时，传感节点的能耗主要由数据通信产生，而计算能耗所占比例较少.
4 结束语笔者提出了一种SERQ算法. 在SERQ中，传感节点对其收集的感知数据进行加密处理，构建新数据并利用保序函数生成保序编码. 同时，Sink将查询范围转换成下限和上限多项式. 存储节点通过下上限多项式对每个节点生成相应的查询范围，使得存储节点对密文完成范围查询. 因此，存储节点不仅不能获得原始的感知数据，而且不能获得目标范围区间. 获得查询结果后，Sink通过解密并重构编码集实现对感知数据真实性和完整性的检测. 理论分析和实验结果显示，SERQ能够保证感知数据、查询结果和目标范围区间的隐私性，且与现有方案相比具有更高的能效.
| [1] | Gnawali O, Jang K Y, Paek J, et al. The tenet architecture for tiered sensor networks[C]//Proceedings of ACM SenSys 2006. Colorado: ACM Press, 2006: 153-166.[引用本文:1] |
| [2] | Jing Shi, Zhang Rui, Zhang Yanchao. A spatiotemporal approach for secure range queries in tiered sensor networks[J]. IEEE Trans Wireless Communications, 2011, 10(1): 264-273.[引用本文:2] |
| [3] | Bo Sheng, Li Qun. Verifiable privacy-preserving sensor network storage for range query[J]. IEEE Transactions on Mobile Computing, 2011, 10(9): 1312-1326.[引用本文:3] |
| [4] | Chen Fei, Alex X Liu. SafeQ: secure and efficient query processing in sensor networks[C]//Proceedings of the 29th IEEE Conference on Computer Communications (INFOCOM). San Diego: IEEE, 2010: 1-9.[引用本文:2] |
| [5] | 蒋文涛, 吕俊伟, 杨曙辉, 等. 传感器网络中面向数据聚集的有向分簇算法[J]. 北京邮电大学学报, 2012, 35(3): 25-29. Jiang Wentao, Lü Junwei, Yang Shuhui, 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.[引用本文:1] |
| [6] | Yao Yonglei, Xiong Naixue, Hyuk Park, et al. Privacy-preserving max/min query in two-tiered wireless sensor networks[J]. Computers & Mathematics with Applications, 2013, 65(9): 1318-1325.[引用本文:2] |
| [7] | Chan Haowen, Adrian Perrig. Efficient security primitives deried from a secure aggregation algorithm[C]//Proceedings of the ACM Conference on Computer and Communications Security (CCS). Alexandria: ACM Press, 2008: 521-534.[引用本文:1] |
| [8] | Liu Dongxi, Wang Shenlu. Programmable order-preserving secure index for encrypted database query[C]//Proceedings of the 2012 IEEE 5th International Conference on Cloud Computing. Honolulu: IEEE, 2012: 502-509.[引用本文:1] |