无线传感器网络安全MAX/MIN查询技术综述*

戴 华，王 敏，易 训，杨 庚,2，叶庆群

1.南京邮电大学 计算机学院，南京 210023

2.江苏省大数据安全与智能处理重点实验室，南京 210023

3.墨尔本皇家理工大学 科学学院，澳大利亚 墨尔本 3000

无线传感器网络安全MAX/MIN查询技术综述*

戴 华1,2+，王 敏1，易 训3，杨 庚1,2，叶庆群1

1.南京邮电大学 计算机学院，南京 210023

2.江苏省大数据安全与智能处理重点实验室，南京 210023

3.墨尔本皇家理工大学 科学学院，澳大利亚 墨尔本 3000

随着无线传感器网络（wireless sensor network，WSN）的广泛应用，对于具备安全保护能力的数据查询技术的需求日益迫切，安全MAX/MIN查询就是其中一种重要的数据查询方式。现有的安全MAX/MIN查询技术多数采用半诚实威胁模型，以保护感知节点采集数据和查询结果的私密性为研究重点，较少关注由于数据篡改、伪造等攻击手段导致的查询结果完整性验证问题。从数据隐私保护和查询结果完整性验证这两个角度出发，分别基于传统WSN和两层WSN对现有的安全MAX/MIN查询处理技术进行了总结，介绍了网络模型和查询模型，并给出了在两种网络结构中关于私密性和完整性的问题描述；全面分析了现有方法采用的关键技术和协议流程，讨论了各自的优点和不足，同时指出未来的研究方向。

无线传感器网络；MAX/MIN查询；隐私保护；完整性验证

1 引言

无线传感器网络（wireless sensor network，WSN）由若干感知设备通过无线通信协议构成，通常分布在无人值守的地域之中，用以探测所部属环境的物理信息。分布的感知设备通常具有一定的计算能力，能通过无线连接方式与周围邻近的感知设备进行通信，在军事安全、环境监测等方面具有广阔的应用前景。传统无线传感器网络[1]如图1所示，其网络结构简单，由部署在特定区域的大量传感器节点组成，由于成本限制，感知节点在计算、存储、能量等资源上受限，仅与邻近的节点通信，从而形成多跳式通信结构；对于基站的查询请求，往往由网络内各感知节点通过查询协议协作完成。两层无线传感网络[2]（two-tiered wireless sensor network）如图2所示，在传统WSN的基础上引入存储节点（storage node）作为网络中间层，存储节点资源丰富，负责收集、存储其所在区域内的感知节点采集的数据；对于基站的查询指令，由存储节点构成的上层网络协作完成。

随着传感器网络的应用发展，涉及数据的隐私性和完整性的安全问题也日益凸显。例如，在野生动植物监测场景中，珍稀物种的监控信息可能被窃取，用于非法狩猎；在国防军事领域，敏感区域监测信息可能被非法监听或篡改而影响国家安全；在居民日常生活中，各种资源（如水、电、煤气等）的使用监测信息可能被非法采集和分析而用于盗窃作案等。当前，针对私密性和完整性的安全保护已成为WSN应用和研究中的热点问题。在传统WSN中，所有感知节点在数据存储和通信上具有同质性，且参与基站发起的查询处理过程，因此防范任一感知节点被俘获而导致的数据泄露和完整性验证问题是研究的关键；而在两层WSN中，存储节点不仅存储着所在区域内所有感知节点采集的数据，同时负责响应基站的查询指令，导致存储节点成为该网络结构中的关键节点，因此防范针对存储节点中数据私密性和完整性是两层WSN安全问题研究的关键。此外，由于资源受限的感知节点是传感器网络的核心组成部分，如何提高节点的能耗利用效率，从而提高整个网络的生命周期，也是各项研究的一个重要目标。

数据查询（data query）是传感器网络事件监测和数据管理应用中的基本手段。在当前面向传感器网络的数据查询技术研究中，安全数据查询已引起广泛的关注并成为研究的热点，包括安全Top-k查询[3-15]、范围（range）查询[16-25]和最值（MAX/MIN）查询[26-35]等。这些研究工作主要从数据隐私保护和（或）查询结果完整性验证角度，提出各种行之有效的解决方案。本文针对安全MAX/MIN查询处理，分别从传统WSN和两层WSN出发，对现有工作进行综述研究，总结现有工作的核心思想，讨论各项工作的优缺点，并展望未来可能的研究方向。

本文组织结构如下：第2章为相关模型介绍以及问题描述；第3章和第4章根据不同的网络模型对现有的安全最值（MAX/MIN）查询技术进行分析与总结；第5章对现有研究工作进行分析，并对未来可能的研究方向进行展望。

2 模型及问题描述

2.1 网络模型

传统WSN模型如图1所示，整个网络由基站（或者Sink节点）和大量感知节点构成，为了控制网络部署成本，感知节点往往是计算、存储、能量等资源受限的设备，感知节点之间形成多跳式网络通信结构，实现对网络部署区域内数据的采集和监控。

两层WSN结构如图2所示，通过在传统WSN的基础上引入了资源丰富的存储节点，将整个网络分割为连续不重合的单元。每个单元由一个存储节点和若干感知节点构成，其中感知节点负责采集数据，并发送至存储节点；而存储节点则负责接收并存储来自感知节点的数据，同时还负责执行来自基站的查询请求。最终该结构形成分工明确的两层结构的网络，其中单元内的感知节点与存储节点之间构成以数据采集和传输为目标的下层网络结构，而存储节点与基站之间则形成以数据存储和查询处理为目标的上层网络结构。

上述两种网络模型中的感知节点均为资源受限设备，且都负责数据采集，节点之间的数据通信协议（如TAG（tiny aggregation）[36]、LEACH（low energy adaptive clustering hierarchy）[37]等）有通用性。两者的区别也较明显，在传统WSN中，感知节点除了负责采集数据之外，还负责一定时间周期的数据存储，且响应和执行基站的查询指令；而两层WSN中由于资源丰富的存储节点的加入，感知节点仅负责数据采集并发送至存储节点进行存储，不再参与查询处理，而是交由存储节点完成基站的查询处理请求。这就使得在同等条件下两层WSN的网络生命周期比传统WSN更长，稳定性也更高；但由于存储节点的制备成本较高，导致同等条件下两层WSN的部署成本高于传统WSN。

Fig.1 Traditional WSN structure图1 传统WSN结构图

Fig.2 Two-tiered WSN structure图2 两层WSN结构图

2.2 查询模型

MAX/MIN查询是以获取特定时间和区域内感知节点采集到的数据的最大或最小值为目的的查询方法，形式化表示为：

其中，S表示查询区域内的感知节点集合；t为查询时间；MAX/MIN表示所要查询的最值类型。例如Qt=({s1,s2,…,s100},t,MAX)，表示查询在t时间内感知节点s1～s100所覆盖区域的最大值。

在传统WSN中，基站将查询指令在网络内进行广播，感知节点根据自身位置判断是否参与查询处理，若是则根据查询协议执行查询处理过程；而在两层WSN中，基站的查询指令只在存储节点构成的上层网络进行广播，满足查询条件的存储节点根据查询协议执行查询处理指令，并返回结果，而感知节点并不参与查询处理过程。

2.3 问题描述

（1）隐私性：是指感知节点采集的数据以及查询处理结果对其他节点不可见的私密性要求。在传统WSN中，由于构成网络的感知节点的同质性，都负责数据采集、存储，并参与查询处理，这就需要防范任一感知节点窥探网络内部其他节点的隐私数据，即对于任一节点si而言，无法获取Dt-Di,t中的任何数据；而在两层WSN中，由于存储节点M不仅存储所在单元内所有感知节点采集的数据，同时还负责执行基站的查询处理请求，导致其成为网络的关键节点，这也使得防范M窥探感知节点采集的隐私数据成为研究重点，即防范M获取Dt中的任何数据。

（2）完整性：是指基站获得查询结果的正确性和完备性需求，即获得的查询结果R为符合查询条件的感知节点采集的最大值或最小值。网络中任何参与查询处理的节点对于数据的篡改或伪造都可能造成基站无法获得正确且完备的查询结果，因此基站需要具有检测和发现R是否满足完整性要求的能力，即判断R∈Dt∧(∀di(di∈(Dt-{R}))→R≥di)是否成立。

在面向WSN的安全MAX/MIN查询处理研究中，现有工作多数采用半诚实（honest-but-curious）威胁模型[38]，即假设网络中的节点能够遵循既定的查询处理协议，但有窥探其他节点隐私数据的企图，并在此基础上重点研究针对隐私性的安全查询处理方法。而针对完整性的研究工作相对较少，在面向查询结果完整性验证的研究中，一般采用攻击模型（attack model）[28,31]，即假设网络中的感知节点不仅可能窥探其他节点的隐私，还有可能篡改、伪造或丢弃数据，从而造成查询结果不正确或不完整，最终对建立在该查询结果基础上的上层应用决策的正确性产生影响。由于面向查询结果完整性验证的威胁模型更强，其研究的复杂度也相对较高。

此外，由于感知节点的能量受限特性，对于安全MAX/MIN查询处理方案的性能主要是从网络能耗和生命周期这两个角度进行评价。由于数据通信产生的能耗占绝大部分，一般采用网络通信代价替代网络能耗评价指标。

3 面向传统WSN的查询处理方法

Fig.3 Query process of traditional WSN图3 传统WSN的查询过程

传统WSN的安全MAX/MIN查询处理过程由基站与感知节点交互完成，本文通过实例给出传统WSN中查询处理的一般流程。如图3所示，设网络由感知节点{s1,s2,…,s12}组成，采用TAG协议，在执行查询处理时，基站首先将包含查询区域（圆形区域）、时间指令Qt通过协调节点s2在网络内发起广播，处于查询区域内的节点{s2,s3,s6,s8}进一步广播查询指令，并执行查询指令，根据既定协议处理相关数据，最终生成查询结果R并上传至基站。查询区域外的其他节点则不参与查询处理。现有的面向传统WSN的安全MAX/MIN查询处理方法有CDAM（concealed data aggregation for maximum/minimum）[26]、KIPDA（kindistinguishable privacy-preserving data aggregation）[27]、RCDA（recoverable concealed data aggregation）[28]、PMMA（privacy-preserving MAX/MIN aggregation）[29]、SDAM（secure data aggregation for maximum/minimum）[30]和SASPKC（secure aggregation scheme using stateful public key cryptography）[31]，其中CDAM、KIPDA、PMMA和SDAM重点解决传统无线传感器网络中的隐私保护MAX/MIN查询处理问题，而RCDA和SASPKC则主要研究安全数据融合方案，但支持安全MAX/MIN查询处理。这几种方法在主体流程上类似，它们的核心区别在于采用不同的安全策略（如对称加密、哈希消息认证码（Hash-based message authentication code，HMAC）、数据匿名等），设计满足特定安全性需求和性能需求的查询协议，具体工作如下：

（1）CDAM

文献[26]提出了一种支持MAX/MIN查询的传感器网络隐私保护数据聚集方法CDAM，该方法利用Domingo-Ferrer隐私同态加密机制[39]实现数据的隐私保护。利用该加密方法，CDAM的基本思想如下：设节点感知si采集到的数据为w，则si首先将w表示如下：

然后分别对ei中的每一位进行加密，加密时先将待加密的数据a分割成一组满足特定要求的分片数据(a1,a2,…,ad)，再将这组数据分别执行乘积和取余操作，即E(a)=(a1⋅r modm,a2⋅r modm,…,ad⋅r modm)，E(a)即为数据a对应的密文。加密完成后，若si为叶节点，则发送加密后的数据至父节点；若为中间节点，根据上述加密方法的加法同态特性，将收到的密文数据与自身计算所得的密文数据按位相加，并将加和得出的新数据发送至父节点。基站收到根节点发送的密文数据后，首先按位解密数据，然后对解密得到的数据依次进行判断，进而确定最终的查询结果。

CDAM能够实现隐私保护的前提是不存在感知节点被俘获，否则加密所用的参数设置都将泄露。此外，当感知数据的数值较大时，加密过程形成的密文分量将同步增多，这也将导致网络传输通信开销显著增长，降低网络的生命周期。

（2）KIPDA

文献[27]提出了一种非加密形式的安全MAX/MIN查询处理方法KIPDA，该方法基于信息扰乱技术，通过在感知数据中混入扰乱数据实现敏感数据的隐私保护。该方法的基本思想如下：首先基站生成全局秘密信息集GSS，用以指定真实数据的位置，对于任一感知节点si，均进行如下预处理过程：si选取GSS的一个单元素子集NS表示真实感知数据的位置信息；si将伪装数据按照是否大于真实数据值分成两类，其中小于真实数据值的伪装数据所在的位置索引与NS共同构成si的秘密信息集NSSi，NSSi由基站设置并分发，且满足NSSi≠∅；si将真实数据和伪装数据按照位置索引要求放入集合Ui中。当基站启动查询后，若si为叶节点，则si将Ui发送至父节点；若si为中间节点，则按索引位置比较自身数据集和收到的其他孩子节点发来的数据集，选取相同索引位置上的最大值组成新的数据集，并发送至父节点。最后，基站将收到的数据集按上述方式计算出最终数据集UBS，并根据GSS获得UBS中相应索引位置上的数据，进而计算出查询结果R。

在KIPDA中，节点的私密信息集仅与基站共享，且每个节点的数据索引信息不外泄，因此攻击者很难区分真实数据与伪装数据；但KIPDA中全局安全集和各感知节点自身记录的各类数据索引集之间存在一定可计算关系，当被攻击的节点数量达到一定界限时，数据隐私就会存在泄露的风险。KIPDA的网络通信代价主要取决于用于隐匿查询结果的数据集合的规模，当规模较大时，网络通信代价较高，但安全性增强，反之亦然。

（3）RCDA

文献[28]提出了一种具有隐私保护和完整性验证功能的数据融合方法RCDA。该方法中的基站能够获取任意感知节点的数据值，因此该方法也支持MAX/MIN查询处理。在RCDA中，感知节点首先对采集的数据进行编码：假设各感知节点所采集的感知数据长度为l，共有n个节点，则节点si生成长度为n×l的编码，并将该编码分成n个长度为l的部分，其中第i部分即为si的感知数据di，其余部分用0填充。然后感知节点生成密文数据和相应的签名数据，其中密文数据是采用文献[40]提出的EC-EG（elliptic curve ElGamal）加密方法对编码数据加密形成密文，而签名数据是采用文献[41]提出的基于双线性映射的聚合签名方案对di进行数字签名处理所形成的签名。在查询处理过程中，叶节点将上述两部分信息直接上传至父节点；而中间节点则将收到的孩子节点发来的密文和签名数据分别与自身生成的数据对应相加，然后将得到的数据继续向父节点上传，直至基站。当基站收到邻居感知节点发来的数据信息后，首先解密其中的密文数据，并根据位置信息获取各感知节点采集的数据，再利用签名数据校验这些数据的完整性，最终即可获得查询结果。

RCDA具有良好的隐私保护和查询结果完整性验证能力，但该方法的编码方式使得各节点的编码长度与感知节点的数量n成正比，任何节点都需要为其他n-1个感知节点预留数据空间，导致较大的数据冗余，特别是在大规模部署的应用场景中，该问题更加突出。此外，RCDA使用的加密方法和签名方法的复杂度较高，对于传感器设备的硬件要求相对较高，从而导致网络部署成本增加。

（4）PMMA

文献[29]提出了具有抗共谋攻击能力的隐私保护MAX/MIN查询处理方法PMMA。该方法利用前缀成员验证机制（prefix membership verification，PMV）[42-43]实现无需明文参与的数据比较，并采用HMAC[44]和对称加密方法实现隐私保护MAX/MIN查询。基本思想如下：设感知节点采集数据的域为[dlow,dhigh]。对于任一感知节点si而言，设其在一个查询周期内采集的感知数据的最大值为di，si首先利用仅与基站共享的密钥ki对di进行加密，得到的密文数据记为(di)ki；然后利用PMV机制计算di的数值化前缀成员编码集N(F(di))，以及区间[di,dhigh]的数值化前缀区间编码集N(S([di,dhigh]))；最后利用HMAC算法对上述集合进行编码，得到HMACg(N(F(di)))和HMACg(N(S([di,dhigh])))。在数据传输过程中，若si为叶节点，则只需发送密文数据(di)ki和两个HMAC编码至父节点；若si为中间节点，根据PMV的数值化比较原理：若F(x)∩S([di,dhigh])≠∅，则有x∈[di,dhigh]成立，即x≥di；si则可以确定所收到数据和自身采集数据中包含最大值的密文数据以及HMAC编码集合，并发送至父节点；最后，基站利用同样方法确定整个网络中蕴含最大值的密文数据，并利用与感知节点共享的密钥解密获得明文查询结果。

由于PMV机制中每一个感知数据都将生成至少2倍数据位长的前缀编码，再加上后续的HMAC处理，使得每个感知节点需要传输的数据量增大，进而导致整个网络的通信代价较高。同时，由于所有感知节点共享HMAC密钥，若存在一个感知节点与攻击者共谋，则攻击者将能够利用字典攻击获得经由该感知节点转发的HMAC编码对应的明文感知数据。

（5）SDAM

文献[30]在CDAM基础上提出了一种基于概率加密机制的隐私保护MAX/MIN查询方法SDAM。该方法利用概率加密的异或同态特性代替CDAM中的Domingo-Ferrer加法同态特性，使得查询处理过程更加高效和安全。SDAM采用GM概率加密协议[45]，对单位比特b∈{0,1}进行加密，得到密文数据EGM(b)=zb⋅r2mod N，其中N为RSA模数，z为模N的随机伪二次非剩余，且z∈ZN,ZN={0,1,2,…,N-1}，r∈ZN′,ZN′={a∈ZN|gcd(a,N)=1}，gcd(a,b)表示a和b的最大公约数。SDAM在感知节点数据无重复的前提下使用概率加密机制的同态异或特性，即EGM(b⊕b′)=EGM(b)⋅EGM(b′)mod N(b,b′∈{0,1})。本文以获取最大值的查询方法为例，描述该方法的基本思想。设感知节点si采集的数据值为di，用矢量ui表示如下：

si首先利用概率加密方法按位加密ui，生成加密矢量数据。若si为叶节点，则si直接将加密矢量数据发送至父节点；若si为中间节点，则si将其自身生成的加密矢量数据以及接收到的孩子节点的加密矢量数据进行合成处理，生成合成后的加密矢量数据，并发送至父节点。当基站收到根节点发来的矢量数据时，基站进行解密处理，获得最终的查询结果。

SDAM解决了CDAM中存在感知节点被俘获情况下的隐私保护失效的问题，能够实现隐私保护MAX/MIN查询。但该方法与CDAM类似，当感知节点采集的数据值较大时，按位加密的方法也将使得查询处理的通信代价同步增长，导致整个网络生命周期降低。

（6）SASPKC

文献[31]在RCDA的基础上通过引入同态加密方法，提出了一种基于状态公钥加密方案的数据融合方法SASPKC，同样支持安全MAX/MIN查询处理。在该方法中，每个感知节点利用文献[46]提出的秘钥生成方法HKDF（Hash based key derivation function）计算动态秘钥。对于任一感知节点si而言，HKDF产生的秘钥包含ki1和ki2两部分。在执行查询时，si首先将其采集的感知数据用RCDA中同样的编码方式生成编码数据di，并分别计算密文数据Ci=ki1+dimod M和签名数据HMAC(Ci,ki2)；若si为叶节点，则将计算后的数据直接发送至父节点，若为中间节点，则将孩子节点的数据与自身计算的数据分别进行融合处理（密文数据相加，签名数据异或），然后再上传融合后的密文和签名数据。基站收到感知节点发来的数据时，首先解密其中的密文数据，并恢复各节点采集的明文数据，进而获得查询结果，然后利用签名数据进行结果完整性验证。

与RCDA类似，SASPKC同样具有良好的隐私保护和查询结果完整性验证能力，但由于SASPKC采用与RCDA中同样的编码方法，导致其也存在类似的数据冗余问题。同时，SASPKC中使用的同态加密方法使其具有比RCDA更低的网络通信代价。

4 面向两层WSN的查询处理方法

两层WSN在传统WSN的基础上引入存储节点作为中间层，从而将数据采集与数据查询过程分离,使得资源受限的感知节点仅负责采集数据并传输至存储节点，存储节点负责执行基站的查询指令，从而减少感知节点由于参与查询处理过程而带来能量消耗。因此，两层WSN的MAX/MIN查询方法需要研究两个阶段的交互协议，如图4所示，一是从感知节点到存储节点的数据上传协议，二是基站与存储节点之间的查询处理协议。

Fig.4 Query process of two-tiered WSN图4 两层WSN查询过程

现有的两层WSN中的安全MAX/MIN查询方法PMQP（privacy-preserving MAX/MIN query protocol）[32]、EMQP（energy-efficient privacy-preserving MAX/MIN query protocol）[33]、RSCS-PMQ（random secure comparator selection based privacy-preserving MAX/MIN query）[34]和ERM-MQP（efficient random modulation MAX/MIN query protocol）[35]都采用上述两阶段协议设计方案，它们的不同点主要有：在感知节点中采用不同的安全策略对采集数据进行处理；基于感知节点对采集数据的安全处理方法，在存储节点与基站之间设计相应的安全查询协议，实现特定安全目标和性能要求的安全查询。具体的相关工作如下。

（1）PMQP

与PMMA类似，文献[32]同样利用PMV机制，提出了面向两层WSN的隐私保护MAX/MIN查询方法。在安全机制使用上，PMQP同样使用HMAC和对称加密技术；在查询处理方法的设计实现上，PMQP根据两层传感器网络的结构特点，提出相应的处理方案，实现针对两层结构中处于关键位置的存储节点的数据隐私屏蔽保护。该方法的基本思想为：与PMMA相同，感知节点首先加密一个查询周期中采集的感知数据的最大值形成密文数据，然后利用PMV机制计算该最大值的数值化前缀成员编码集合和数值化前缀区间编码集合，最后利用HMAC算法对上述集合进行编码。感知节点将编码后数据和加密后的感知数据发送至存储节点存储。在执行查询处理时，基站向存储节点发送查询指令，存储节点接收到基站的查询指令后，利用PMV的数值比较特性确定蕴含查询结果的密文数据，并将该数据反馈给基站。基站收到存储节点反馈的数据后，使用与感知节点共享的密钥进行解密，进而获得最终的明文查询结果。

由于PMQP的基本原理与PMMA相似，PMMA所存在的前缀编码导致通信代价较高的问题在PMQP中同样存在。同时，PMQP能够防范仅存在存储节点的隐私窥探。但当存储节点与任一感知节点“共谋”时，存储节点将能够获取所有感知节点共享的HMAC密钥，此时存储节点即可利用字典攻击方法，获得任一感知节点上传的HMAC编码对应的明文感知数据。

（2）EMQP

为了降低网络通信代价，文献[33]提出了一种基于0-1编码[47]的两层WSN的隐私保护MAX/MIN查询处理方法EMQP。该方法利用0-1编码机制的数值比较特性实现无需明文参与的数值比较，并采用HMAC和对称加密方法，在确保感知节点采集数据与存储节点之间的隐私隔离的同时，实现MAX/MIN查询处理。该方法的基本思想如下：在数据上传阶段，任意感知节点si将单位时间周期内采集的最大数据di进行加密，生成密文(di)ki，然后再对di进行0-1编码，并将得到的编码数据E0(di)和E1(di)进行数值化和HMAC编码处理，最后将处理后的数据发送至存储节点。在查询处理阶段，存储节点接收到基站的查询指令后，存储节点根据0-1编码机制中“若E1(x)∩E0(y)≠∅，则有x＞y成立”这一数据比较方法，确定蕴含查询结果的密文数据，并将该密文数据以及相应的节点ID发送给基站。最后，基站根据与相应感知节点共享的密钥，解密获得查询结果，完成整个查询处理。

由于EMQP采用了编码数量较少的0-1编码机制，此外EMQP还引入基于Hash编码压缩的优化方法，进一步降低用于数值比较的编码数据的空间占用，使得EMQP在网络通信代价消耗上显著优于PMQP。但由于EMQP采用与PMQP相同的所有感知节点共享HMAC密钥的策略，这也使得EMQP与PMQP的隐私保护效果完全相同，只能防范针对单一存储节点的隐私窥探，无法解决当存储节点与感知节点“共谋”时的隐私保护问题。

（3）RSCS-PMQ

文献[34]在EMQP的基础上，提出了一种基于安全比较码随机选择的两层WSN隐私保护MAX/MIN查询处理方法RSCS-PMQ，这里的安全比较码即为经过HMAC和数值化处理的0-1编码。与EMQP相比，该方法就是通过减少感知节点上传的编码数量，达到降低网络通信代价的目的。该方法的基本思想如下：在数据上传阶段，任意感知节点si对数据di进行加密，生成密文(di)ki，然后再对di进行HMAC数值化0-1编码，与EMQP不同的是，RSCS-PMQ只选择0-1编码中的一种随机安全码与密文数据以及节点ID一起上传至存储节点。在查询处理阶段，存储节点收到基站的查询指令后，利用最大随机安全比较码选择算法（max random secure comparator selection,MaxRSC）计算出最小化最大安全比较码集合，进而确定包含最值查询结果的最小化候选密文集，再将此密文集发送至基站。此时，基站只需利用与感知节点共享的密钥解密接收到的密文数据，即可获得最终的查询结果。

由于安全比较码随机选择机制的引入，RSCSPMQ中感知节点需上传的编码数量比EMQP平均减少了约50％，从而显著降低感知节点的通信代价；但只存储随机安全码也导致存储节点只能确定包含查询结果的密文集合（可能包含1个或多个候选密文数据，大样本实验表明平均包含约2个）。而EMQP则能够确定唯一的密文查询结果，这就使得RSCS-PMQ在存储节点与基站的通信代价上略高于EMQP。此外，由于采用相同的编码策略和安全机制，RSCSPMQ与EMQP在隐私保护能力上几乎相同。

（4）ERM-MQP

文献[35]基于随机数和数值变换相结合的密码理论，提出了一种面向两层WSN的随机调制隐私保护查询协议ERM-MQP。该方法采用文献[48]所述的基于身份加密的密钥分配方案为查询建立两条秘密通道：一条为感知节点与基站之间的会话密钥，对存储节点保密；另一条为感知节点与存储节点之间的会话密钥。ERM-MQP引入并证明了一种不泄露原始传感数据的隐私保护数值比较方法，进而实现隐私保护MAX/MIN查询处理，其核心协议主要包含四部分：①节点与基站分别随机调制参数；②感知节点对感知数据进行数值变换，并传送至存储节点；③存储节点收到密文数据后，解密获得最值隐私数据，并使用基站的公钥进行加密反馈给基站。④基站对存储节点发来的密文数据进行解密，获得最终的查询结果。

ERM-MQP只需要传递节点ID、时间参数和调制后的密文数据，因此能够降低网络的通信代价。但ERM-MQP安全性能不高：首先，当存储节点与任一感知节点共谋时，存储节点即可获得关键参数，此时很容易计算出任何感知节点上传的敏感数据；此外，由于ERM-MQP实际采用的数值比较方法是隐匿系数的一次多项式，且隐匿的系数存在特定数量关系，在存储节点拥有所有隐私数据的情况下，该一次多项式较容易被破解，这也导致ERM-MQP对于感知节点采集数据的隐私保护能力较弱。

此外，Top-k查询在特殊情况下(k=1)可以退化为MAX/MIN查询，即Top-1查询，因此现有的安全Top-k查询方法[3-15]理论上也能完成安全MAX/MIN查询任务。但由于Top-k查询的算法和协议并不是专门为Top-1进行最优化设计的，在性能和安全性控制上并不适用于安全MAX/MIN查询方法。

5 展望与总结

5.1 对现有工作的总结

综合前述安全MAX/MIN查询处理方法的分析和讨论，本文对现有研究工作从安全目标、安全模型、共谋防范、通信代价以及实现技术等方面进行总结，如表1所示。

当前面向WSN中安全MAX/MIN查询的研究工作多数都是建立在半诚实模型基础上，重点研究查询处理中的隐私保护问题，较少关注查询结果的完整性验证问题。特别是在面向两层WSN的研究工作中，尚未见有关MAX/MIN查询完整性验证的报道。

对于共谋攻击问题，CDAM、PMMA、PMQP、EMQP、ERM-MQP和RSCS-PMQ均不具备共谋攻击的防范能力，其根本原因在于这些方法中的所有感知节点都共享实现安全查询的关键参数，当其中任一感知节点被俘获，攻击者将具备反向获取其他节点采集数据以及查询结果的能力。KIPDA能够在一定程度上防范共谋攻击，但当共谋节点数量达到一定阈值（与该方法中所使用的秘密信息集的规模有关）时，攻击者将具备在含有扰乱数据的数据集中定位查询结果数据的能力。RCDA、SDAM和SASPKC的抗共谋攻击能力相对较强，任一感知节点无法得知其他任何感知节点的数据信息，在多个节点被俘获共谋的情况下，不会造成其他节点采集数据的隐私泄露问题。

Table1 Comparison and conclusion of existing secure MAX/MIN query methods表1 现有的安全MAX/MIN查询方法对比总结

在通信代价上，在CDAM、KIPDA、PMMA、RCDA、SDAM、SASPKC和ERM-MQP中，中间节点能够将孩子节点发来的数据与自身数据进行融合，且融合结果不影响查询处理，这就使得所有感知节点的通信负载都相等，感知节点的能量消耗均衡，能够最大化整个网络的生命周期。而在PMQP、EMQP和RSCSPMQ中，距离数据汇集中心越近的感知节点的通信负载越大，直接导致网络中感知节点的能量消耗不均衡，整个网络的生命周期存在“木桶”效应。

在实现安全MAX/MIN查询的技术手段上，PMMA、PMQP、EMQP和RSCS-PMQ主要采用对称加密保护数据私密性，并利用HMAC和具备数据比较特性的编码方法实现无需明文参与的密文数据比较，进而实现隐私保护MAX/MIN查询。CDAM和SDAM分别使用隐私同态加密和概率加密方法，都利用了特殊加密方法的数值比较特性实现隐私保护MAX/MIN查询。RCDA和SASPKC采用相同的编码方式，分别使用EC-EG加密和状态公钥加密方法实现针对感知数据的隐私保护，并分别使用双线性映射签名和HMAC实现查询结果的完整性验证。ERM-MQP则采用身份加密机制在基站与感知节点之间秘密传输多项式的系数，并利用多项式实现隐私保护MAX/MIN查询。

5.2 对未来工作的展望

MAX/MIN查询处理作为一种重要的数据查询方法，被广泛应用于各种传感器网络环境中。随着应用的不断深入和拓展，查询处理过程中的安全保护问题也越来越引起业界的广泛关注，如感知节点采集数据和查询结果数据的隐私保护问题，查询结果的完整性验证问题等。由于感知节点资源有限，安全性能的提高必然伴随着通信代价的增长，如何降低网络通信代价也是业界研究的重点之一。因此，传感器网络安全MAX/MIN查询技术的进一步研究可以从如下三方面展开：

（1）完整性验证。现有的面向WSN的安全MAX/MIN查询处理技术，多数都是以半诚实模型为基础，研究针对查询过程中的感知数据以及查询结果的隐私保护问题，对于查询结果的完整性验证问题研究相对较少，特别是在两层传感器网络中针对查询结果完整性验证的相关研究尚未见报道。而在实际应用中，攻击者不仅可能会窥探网络内部的隐私数据，同时还可能篡改或伪造数据，破坏查询结果的完整性。因此，具有查询结果完整性验证能力的安全MAX/MIN查询方法仍有待进一步研究。

（2）抗共谋攻击。由于WSN应用环境中感知节点部署的规模性需求，感知节点通常是成本较低的资源受限设备，这就使得感知节点自身的安全防御能力受限，容易被攻击者俘获，并发起共谋攻击。在诸多攻击方法中，这种内外结合的共谋攻击往往更具有破坏性，研究具备较强抗共谋攻击能力的安全MAX/MIN查询方法是一个具有挑战性的问题。

（3）安全性和通信代价的权衡和优化。现有安全MAX/MIN查询方法往往都权衡于安全保护能力和通信代价之间，通信代价的降低常伴随着安全保护能力的降低，而安全性的提高往往又带来通信代价的不断增长。因此，针对安全性和通信代价的合理权衡和优化的研究方案同样具有实际应用价值。

[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4):393-422.

[2]Gnawali O,Jang K Y,Paek J,et al.The Tenet architecture for tiered sensor networks[C]//Proceedings of the 4th International Conference on Embedded Networked Sensor Systems,Boulder,USA,Oct 31-Nov 3,2006.New York:ACM,2006:153-166.

[3]Liang Junbin,Jiang Chan,Ma Xingpo,et al.Secure data aggregation for top-k queries in tiered wireless sensor networks[J].Ad hoc&Sensor Wireless Networks,2016,32(2):51-78.

[4]Yu C M,NiGK,Chen I Y,et al.Top-query result completeness verification in tiered sensor networks[J].IEEE Transactions on Information Forensics and Security,2014,9(1):109-124.

[5]Zheng Jiping,Song Baoli,Wang Yongge,et al.Adaptive fil-ter updating for energy-efficient top-k queries in wireless sensor networks using Gaussian process regression[J].International Journal of Distributed Sensor Networks,2015:1-14.

[6]Li Guilin,Gao Xing,Liao Minghong,et al.An iterative algorithm to process the top-k query for the wireless sensor networks[J].International Journal of Embedded Systems,2015,7(1):26-33.

[7]Fan Yongjian,Chen Hong.Verifiable privacy-preserving topk query protocol in two-tiered sensor networks[J].Chinese Journal of Computers,2012,35(3):423-433.

[8]Dai Hua,Yang Geng,Huang Haiping,et al.Efficient verifiable top-k queries in two-tiered wireless sensor networks[J].KSII Transactions on Internet and Information Systems,2015,9(6):2111-2131.

[9]Ma Li,Liu Jingfa,Yao Yonglei.Privacy-preserving top-k query in two-tiered wireless sensor networks[J].International Journal of Advancements in Computing Technology,2012,4(6):226-235.

[10]Li Rui,Lin Yaping,Yi Yeqing,et al.Asecure top-k query protocol in two-tiered sensor networks[J].Journal of Computer Research and Development,2012,49(9):1947-1958.

[11]Huang Haiping,Feng Juan,Wang Ruchuan,et al.An exact top-k query algorithm with privacy protection in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2014:1-10.

[12]Dai Hua,Yang Geng,Qin Xiaolin,et al.Privacy-preserving top-k query processing in two-tiered wireless sensor networks[J].Journal of Computer Research and Development,2013,50(6):1239-1252.

[13]Ma Xingpo,Song Hong,Wang Jianxin,et al.Anovel verification scheme for fine-grained top-k queries in two-tiered sensor networks[J].Wireless Personal Communications,2014,75(3):1809-1826.

[14]Dai Hua,Yang Geng,Xiao Fu,et al.EVTQ:an efficient verifiable top-k query processing in two-tiered wireless sensor networks[C]//Proceedings of the 9th IEEE International Conference on Mobile Ad-hoc and Sensor Networks,Dalian,China,Dec 11-13,2013.Washington:IEEE Computer Society,2013:206-211.

[15]Liang Junbin,Ma Xingpo,Kui Xiaoyan.Research on data aggregation algorithms for top-k queries in query-drivenbased two-tiered sensor networks[J].Chinese Journal of Electronics,2014,42(10):2075-2080.

[16]Zhang Xiaoying,Dong Lei,Peng Hui,et al.Collusionaware privacy-preserving range query in tiered wireless sensor networks[J].Sensors,2014,14(12):23905-23932.

[17]Bu Jiajun,Yin Mingjian,He Daojing,et al.SEF:a secure,efficient,and flexible range query scheme in two-tiered sensor networks[J].International Journal of Distributed Sensor Networks,2011,7(4):876-879.

[18]Liao W H,Chen C C.Data storage and range query mechanism for multi-dimensional attributes in wireless sensor networks[J].IET Communications,2010,4(15):1799-1808.

[19]Dong Lei,Chen Xuan,Zhu Jianxiang,et al.Asecure collusionaware and probability-aware range query processing in tiered sensor networks[C]//Proceedings of the 34th IEEE Symposium on Reliable Distributed Systems,Montreal,Canada,Sep 28-Oct 1,2015.Washington:IEEE Computer Society,2015:110-119.

[20]Dong Lei,Zhu Jianxiang,Zhang Xiaoying,et al.SEMR:secure and efficient multi-dimensional range query processing in two-tiered wireless sensor networks[C]//LNCS 9098:Proceedings of the 16th International Conference on Web-Age Information Management,Qingdao,China,Jun 8-10,2015.Berlin,Heidelberg:Springer,2015:520-524.

[21]Chen Fei,LiuA X.Privacy and integrity-preserving range queries in sensor networks[J].IEEE/ACM Transactions on Networks,2012,20(6):1774-1787.

[22]Tsou Y T,Lu C S,Kuo S Y.Privacy-and integrity-preserving range query in wireless sensor networks[C]//Proceedings of the 2012 Global Communications Conference,Anaheim,USA,Dec 3-7,2012.Piscataway,USA:IEEE,2012:328-334.

[23]Zhang Xiaoying,Dong Lei,Peng Hui,et al.Achieving efficient and secure range query in two-tiered wireless sensor networks[C]//Proceedings of the 22nd International Symposium of Quality of Service,Hong Kong,China,May 26-27,2014.Piscataway,USA:IEEE,2014:380-388.

[24]Dai Hua,Ye Qingqun,Yi Xun,et al.VP2RQ:efficient verifiable privacy-preserving range query processing in twotiered wireless sensor networks[J].International Journal of Distributed Sensor Networks,2016,12(11).

[25]Yi Yeqing,Li Rui,Chen Fei,et al.Adigital watermarking approach to secure and precise range query processing in sensor networks[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications,Turin,Italy,Apr 14-19,2013.Piscataway,USA:IEEE,2013:1950-1958.

[26]Ertaul L,Kedlaya V.Computing aggregation function minimum/maximum using homomorphic encryption schemes in wireless sensor networks(WSNs)[C]//Proceedings of the 2007 International Conference on Wireless Networks,Las Vegas,USA,Jun 25-28,2007.USA:CSREA Press,2007:186-192.

[27]Groat M M,He Wenbo,Forrest S.KIPDA:k-indistinguishable privacy-preserving data aggregation in wireless sensor networks[C]//Proceedings of the 30th International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies,Shanghai,Apr 10-15,2011.Piscataway,USA:IEEE,2011:2024-2032.

[28]Chen C M,Lin Y H,Lin Y C,et al.RCDA:recoverable concealed data aggregation for data integrity in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,23(4):727-734.

[29]Yao Yonglei,Ma Li,Liu Jingfa.Privacy-preserving MAX/MIN aggregation in wireless sensor networks[J].Advances in Information Sciences&Service Sciences,2012,4(6):272-280.

[30]SamanthulaBK,Jiang Wei,Madria S.Aprobabilistic encryption based MIN/MAX computation in wireless sensor networks[C]//Proceedings of the 14th International Conference on Mobile Data Management,Milan,Italy,Jun 3-6,2013.Washington:IEEE Computer Society,2013:77-86.

[31]Boudia OR M,Senouci S M,Feham M.Anovel secure aggregation scheme for wireless sensor networks using stateful public key cryptography[J].Ad Hoc Networks,2015,32(C):98-113.

[32]Yao Y,Xiong N,Park J H,et al.Privacy-preserving max/min query in two-tiered wireless sensor networks[J].Computers&Mathematics with Applications,2013,65(9):1318-1325.

[33]Dai Hua,Yang Geng,Qin Xiaolin.EMQP:an energy-efficient privacy-preserving MAX/MIN query in two tiered sensor networks[J].International Journal of Distributed Sensor Networks,2013,2013(1):1492-1519.

[34]Dai Hua,Wei Tianyi,Huang Yue,et al.Random secure comparator selection based privacy-preserving MAX/MIN query processing in two-tiered sensor networks[J].Journal of Sensors,2016,6:1-13.

[35]Liu Honghui,Liu Shubo,Liu Mengjun,et al.Efficient random modulation privacy-preserving MAX/MIN query protocol in two-tiered wireless sensor networks[J].Computer Science,2014,41(12):95-100.

[36]Madden S,Franklin M J,Hellerstein J M,et al.TAG:a tiny aggregation service for ad-hoc sensor networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.

[37]Heinzelman,R W,ChandrakasanA,Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,Maui,USA,Jan 4-7,2000.Washington:IEEE Computer Society,2000:1-10.

[38]Božović V,Socek D,SteinwandtR,et al.Multi-authority attribute-based encryption with honest-but-curious central authority[J].International Journal of Computer Mathematics,2009,3:268-283.

[39]Domingo-Ferrer J.Aprovably secure additive and multiplicative privacy homomorphism[C]//LNCS 2433:Proceedings of the 5th International Conference on Information Security,Sao Paulo,Brazil,Sep 30-Oct 2,2002.Berlin,Heidelberg:Springer,2002:471-483.

[40]Mykletun E,Girao J,Westhoff D.Public key based cryptoschemes for data concealment in wireless sensor networks[C]//Proceedings of the 2006 International Conference on Communications,Istanbul,Turkey,Jun 11-15,2006.Washington:IEEE Computer Society,2006:2288-2295.

[41]DanB,Gentry C,LynnB,et al.Aggregate and verifiably encrypted signatures from bilinear maps[C]//LNCS 2656:Proceedings of the 2003 International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology,Warsaw,Poland,May 4-8,2003.Berlin,Heidelberg:Springer,2003:416-432.

[42]Cheng J,Yang Hao,Wong S H Y,et al.Design and implementation of cross-domain cooperative firewall[C]//Proceedings of the 2007 International Conference on Network Protocols,Beijing,Oct 16-19,2007.Washington:IEEE Computer Society,2007:284-293.

[43]LiuA X,Chen Fei.Collaborative enforcement of firewall policies in virtual private networks[C]//Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing,Toronto,Canada,Aug 18-21,2008.New York:ACM,2008:95-104.

[44]Krawczyk H,CanettiR,Bellare M.HMAC:keyed-hashing for message authentication[R].RFC Editor,1997.

[45]Goldwasser S,Micali S.Probabilistic encryption[J].Journal of Computer and System Sciences,1984,28(2):270-299.

[46]Chen L.Recommendation for key derivation using pseudorandom functions[J].National Institute of Standards and Technology:Special Publication,2008,800:108.

[47]Lin H Y,Tzeng W G.An efficient solution to the Millionaires'problem based on homomorphic encryption[C]//LNCS 3531:Proceedings of the 3rd International Conference on Applied Cryptography and Network Security,New York,Jun 7-10,2005.Berlin,Heidelberg:Springer,2005:456-466.

[48]Yang Geng,Wang Jiangtao,Cheng Hongbing,et al.Akey establish scheme for WSN based on IBE and Diffie-Hellman algorithms[J].Acta Electronica Sinica,2007,35(1):180-184.

附中文参考文献：

[7]范永健,陈红.两层传感器网络可验证Top-k查询处理协议[J].计算机学报,2012,35(3):423-433.

[10]李睿,林亚平,易叶青,等.两层传感器网络中的安全Top-k查询协议[J].计算机研究与发展,2012,49(9):1947-1958.

[12]戴华,杨庚,秦小麟,等.面向隐私保护的两层传感网Topk查询处理方法[J].计算机研究与发展,2013,50(6):1239-1252.

[15]梁俊斌,马行坡,奎晓燕.查询驱动模式下两层传感器网络Top-k查询汇聚算法研究[J].电子学报,2014,42(10):2075-2080.

[35]刘泓晖,刘树波,刘梦君,等.面向两层WSNs的高效随机调制隐私保护最值查询协议[J].计算机科学,2014,41(12):95-100.

[48]杨庚,王江涛,程宏兵,等.基于身份加密的无线传感器网络密钥分配方法[J].电子学报,2007,35(1):180-184.

Survey of Secure MAX/MIN Query Processing in Wireless Sensor Networks*

DAI Hua1,2+,WANG Min1,YI Xun3,YANG Geng1,2,YE Qingqun1
1.School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
2.Jiangsu Key Laboratory of Big Data Security and Intelligent Processing,Nanjing 210023,China
3.School of Science,Royal Melbourne Institute of Technology University,Melbourne 3000,Australia
+Corresponding author:E-mail:daihua@njupt.edu.cn

DAI Hua,WANG Min,YI Xun,et al.Survey of secure MAX/MIN query processing in wireless sensor networks.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1191-1203.

With the development of wireless sensor networks(WSNs),the secure data queries which have the ability of privacy preserving and completeness protection are demanded urgently,such as the secure MAX/MIN queries.The existing secure MAX/MIN queries are mostly based on honest-but-curious threat model and focus on protecting the privacy of sensor data and query result from attacks,but they less consider the problem of incomplete result caused by data tampering or forgery.From the perspectives of privacy protecting and result completeness verification,this paper summarizes the existing secure MAX/MIN query technologies in the traditional WSNs and twotiered WSNs,respectively.This paper firstly introduces the common query model and network models,and gives the detailed problem descriptions of privacy-preserving and completeness-protection in WSNs.Then,this paper dis-cusses the key technologies and protocols proposed in the existing works,and analyzes their advantages and disadvantages.Finally,this paper points out the future research directions according to the analysis and conclusion.

wireless sensor networks;MAX/MIN query;privacy preserving;completeness verification

2016-11,Accepted 2017-04.

DAI Hua was born in 1982.He is an associate professor at Nanjing University of Posts and Telecommunications,and the member of CCF.His research interests include data management and security and database security,etc.戴华（1982—），男，江苏盐城人，南京邮电大学计算机学院副教授，CCF会员，主要研究领域为数据管理与安全，数据库安全等。

WANG Min was born in 1992.She is an M.S.candidate at Nanjing University of Posts and Telecommunications.Her research interest is data management and security in wireless sensor networks.王敏（1992—），女，江苏淮安人，南京邮电大学硕士研究生，主要研究领域为无线传感器网络数据管理与安全。

YI Xun was born in 1967.He is a professor and Ph.D.supervisor at Royal Melbourne Institute of Technology University.His research interests include information security and distributed data processing,etc.易训（1967—），男，湖北孝感人，澳大利亚墨尔本皇家理工大学教授、博士生导师，主要研究领域为信息安全，分布式数据处理等。

YANG Geng was born in 1961.He is a professor and Ph.D.supervisor at Nanjing University of Posts and Telecommunications,and the senior member of CCF.His research interests include cloud computing and security,data security and privacy protection,etc.杨庚（1961—），男，江苏建湖人，南京邮电大学教授、博士生导师，CCF高级会员，主要研究领域为云计算与安全，数据安全，隐私保护等。

YE Qingqun was born in 1992.She is an M.S candidate at Nanjing University of Posts and Telecommunications.Her research interest is data management and security in wireless sensor networks.叶庆群（1992—），女，安徽安庆人，南京邮电大学硕士研究生，主要研究领域为无线传感器网络数据管理与安全。

A

：TP393

*The National Natural Science Foundation of China under Grant Nos.61300240,61402014,61472193,61572263,61502251,61502243(国家自然科学基金);the Natural Science Foundation of Jiangsu Province under Grant Nos.BK20151511,BK20141429,BK20161516(江苏省自然科学基金面上项目);the Project of Natural Science Research of Jiangsu University under Grant Nos.14KJB520027,15KJB520027(江苏省高校自然科学基金面上项目).

CNKI网络优先出版:2017-04-24,http://kns.cnki.net/kcms/detail/11.5602.TP.20170424.1757.006.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1191-13

10.3778/j.issn.1673-9418.1611028

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056