无线传感器网络隐私保护范围查询处理技术

张晓莹，董 蕾，陈 红

（1．中国人民大学 信息学院，北京 100872；2．中国人民大学 数据工程与知识工程国家教育部重点实验室，北京 100872）

0 引 言

无线传感器网络（以下简称传感器网络）是由大量微型传感器节点通过自组织的方式形成的多跳分布式网络系统，通过传感器节点感知、计算和传输数据，为人们提供服务．作为物联网的重要组成部分，传感器网络被广泛应用在军民重要领域，允许人们在任何时间、地点和环境下获取大量重要信息．随着传感器网络的不断发展，在多个关键性领域的实际应用与部署过程中暴露出严重的隐私问题．例如在智能电网领域，不法分子通过截获家庭用电信息推测出家里是否有人、何时无人等家庭敏感信息；在智慧医疗领域，医生通过医疗传感器随时查询患者的体温、血压、心率等重要体征数据，这些数据可能被非法人员窃取，造成患者隐私泄露；在军事国防领域，无线传感器被部署在重要的军事监控区域收集各种情报信息，这些情报信息一旦被敌军窃取或篡改，将导致重大决策失误．这些暴露出的隐私问题会泄露用户和监测对象的重要信息，甚至威胁到用户和监测对象的安全，极大地阻碍了传感器网络的广泛应用．因此，研究传感器网络隐私保护技术，对传感器网络和物联网的发展具有积极的推动意义．

隐私保护范围查询处理技术由Sheng［1］等人于2008年提出．目前，隐私保护范围查询处理技术已经成为新的研究热点．隐私保护范围查询处理技术的主要目标是：在范围查询处理的过程中，有效控制非法用户对网络敏感信息的访问，防止网络敏感信息的泄露，同时，尽量减少能量消耗，降低对通讯信道的占用，提高查询结果的精确度和可靠性．然而传感器网络自身所具有的资源受限、分布式等特征，给隐私保护范围查询处理技术研究带来了极大的挑战．

（1）节点能量有限是传感器网络的一大特点，网络剩余能量直接影响网络生命周期．研究［2］表明节点之间的通信是消耗能量的主要因素，高通信量的隐私保护技术并不适合传感器网络．因此，如何实现低通信量的隐私保护技术，最大程度地减少能量消耗，提高感知节点的寿命，是研究传感器网络隐私保护范围查询处理技术面临的首要挑战．

（2）传感器节点是一种微型嵌入式设备，携带的处理器和存储器能力较弱，这使得计算复杂和存储成本高的隐私保护技术并不符合传感器网络的实际要求．因此，如何实现低计算量的隐私保护技术是研究传感器网络隐私保护范围查询处理技术面临的另一个严峻挑战．

（3）传感器网络是一个开放的网络系统，传感器节点一般通过飞机播散等方式被随机部署到无人值守的环境中，无法预料传感器节点的位置、邻居节点等信息．此外，攻击者的攻击能力日渐强大，攻击方式日趋多样，因此，如何提高隐私保护技术的健壮性，抵御多种攻击，是研究传感器网络隐私保护范围查询处理技术面临的重要挑战．

本文对现有的传感器网络隐私保护范围查询研究成果进行了系统总结，对代表协议的核心技术进行了较详细的阐述，对比分析了各协议的优缺点，并展望了未来需要深入研究的方向．

1 研究模型

1．1 网络模型

现有的隐私保护范围查询协议主要基于两层传感器网络［3］．如图1所示，在两层传感器网络中，大量的传感器节点位于网络的下层，少量的管理节点（Master Node，又称为存储节点）位于网络的上层．管理节点是基站与传感器节点之间的一座“桥梁”．基站将用户命令下发到管理节点，传感器节点进行周期性采样并定期将感知数据发送到最近的管理节点．管理节点负责存储管辖范围内的传感器节点数据和执行基站的命令．相比于传感器节点，基站和管理节点都是高资源节点，其资源不受限制．

两层的传感器网络具有以下优点：

（1）节省传感器节点的资源．传感器节点的能量、计算能力、存储空间等都非常有限．在两层传感器网络中，传感器节点不需要存储大量历史数据、发送数据到基站和执行复杂的查询任务，这些任务均由管理节点负责完成，大大降低传感器节点的存储成本、通信开销和计算代价，从而延长网络的生命周期．

（2）缩短查询的响应时间．管理节点存储着大量传感器节点数据，并且其计算能力和存储空间不受限制，因而能够更加高效地完成用户的查询任务，快速返回查询结果．

（3）增强网络的可扩展性．引入管理节点后，整个网络按照管理节点被分成许多子网．每个子网由一个管理节点和若干传感器节点组成，不同子网中的传感器节点可以是异构的，每个子网独立运行．

1．2 攻击模型

根据已有的研究成果，我们将攻击者的攻击方式大致分为三类：窃听攻击、篡改攻击和共谋攻击．大部分隐私保护范围查询协议主要抵御前两类攻击，少量协议能够抵御第三类攻击．

（1）窃听攻击

攻击者通过窃听节点之间的无线通信链路获取网络节点的敏感信息．在窃听攻击中，攻击者只关注敏感信息的内容，不会改变敏感信息．

（2）篡改攻击

攻击者通过俘获网络节点向网络中注入虚假信息、恶意改变或删除真实信息等方式以达到影响最终结果的目的．在篡改攻击中，攻击者试图改变敏感信息，因此篡改攻击对网络安全的威胁更大，需要更强的保护手段．

（3）共谋攻击

随着攻击者破坏能力的不断增强，攻击者可以同时俘获多个节点，并控制这些被俘获节点进行合作共谋从而破坏网络的安全性．相对于非共谋攻击，共谋攻击对网络安全的危害性更大．

1．3 性能评价模型

评价隐私保护范围查询协议的性能指标主要有4类：隐私性、完整性、高效性和精确性．

（1）隐私性

传感器网络中的敏感信息多种多样，例如节点数据、中间结果、最终结果或用户查询．隐私性要求保护敏感信息不被非法用户获取．敏感信息的确定与应用相关．在隐私保护范围查询处理技术研究中，敏感信息通常指传感器节点的感知数据和用户的查询命令．

（2）完整性

传感器网络是一个自组织多跳的网络系统，感知数据从采集节点到基站往往需要经过其他中间节点的转发，还可能需要进行轻量级的计算．完整性要求感知数据被真实转发和正确计算．完整性直接影响最终查询结果，因此完整性通常是指结果完整性，即基站收到的最终结果应该包含真实的结果，禁止攻击者恶意改变、删除结果和注入非法信息．

（3）高效性

传感器网络的能量有限，网络剩余能量直接影响网络的生命周期．研究结果［2］显示节点通信和计算，特别是节点通信，是消耗能量的主要因素．为了延长网络的生命周期，高效性要求协议尽可能降低通信成本和计算代价．

（4）精确性

给定用户命令，网络按照协议执行操作、计算结果．理想的情况下真实结果与计算所得结果是等价的．为了实现隐私性、完整性和高效性，有时会牺牲一定的结果精度．精确性要求协议在满足隐私性、完整性和高效性的前提下，结果应该在可接受的误差范围内尽可能精确．

2 隐私保护范围查询处理技术

现有隐私保护范围查询协议主要采用的隐私保护技术包括：桶技术、前缀成员验证技术和保序加密技术．此外，还有其他隐私保护技术，如Z-O编码技术、BF编码技术和矩阵变换技术．

2．1 桶技术

桶技术（Bucketing Scheme）［4-5］将值域划分成若干连续不相交的区间．每个区间可以看作是一个只存放指定取值范围数据的桶，使用一个或多个桶表示敏感信息．

文献［1，6］采用桶技术和编码策略（Encoding Scheme）保护范围查询中的隐私性和完整性．协议主要思想是：使用一个桶集合表示用户查询和节点数据．具体方法如下：令Tagi表示桶i的桶号，Bi表示桶i的取值范围．用户查询范围［a，b］被表示成一个桶号集合｛Tag1，Tag2，…，Tagm｝，其中，［a，b］⊆B1∪B2∪…∪Bm，且B1∪B2∪…∪Bm是能覆盖［a，b］的最小桶集合，即对于任意的Bi（1≤i≤m），都满足［a，b］∩Bi≠∅．基站将查询范围的桶集合下发到存储节点，数据d被转换成桶号Tagj，满足d∈Bj．节点使用与基站共享的密钥加密数据，并与对应的桶号一起发送到存储节点．判断d∈［a，b］是否成立，只需判断Tagj∈｛Tag1，Tag2，…，Tagm｝是否成立．判断过程在存储节点上进行，桶技术允许存储节点在不获取敏感信息的情况下完成查询．为了保证基站检测出被篡改的查询结果，节点si需要为t时刻的每个空桶j构造一个码（Encoding Nu mber），即nu m（i，j，t）．基站通过此码判断查询结果的完整性．桶技术本质上是一种泛化技术，即用粗粒度的信息代替精确的信息，因此会导致查询结果存在误识别（False Positive）．桶技术虽然没有直接泄露敏感信息，但是会泄露敏感信息的范围，并且隐私保护程度与桶的划分粒度有关，粒度越粗，隐私性越高，但通信代价越大，结果误识别率越高．

文献［7-8］使用文献［1］中的桶技术实现隐私保护，并提出一种时空交叉验证技术（Spatiotemporal Cr osscheck Technique）检验结果的完整性．时空交叉验证技术包括空间交叉验证策略（Spatial Cr osscheck Appr oach）和时间交叉验证策略（Temporal Cr osscheck Approach）．空间交叉验证策略利用节点之间的关系，为每个节点si构造一个位图Vi，t，表示si在t时刻的数据分布情况．si将位图消息＜i，Vi，t＞发送给选择的节点．收到位图消息的节点将其附加到自己的每一个非空桶中与数据一起上传到存储节点．文献［7］给出两种节点选择方法：一种基于子网广播，另一种基于邻居节点，研究表明基于子网广播的选择方法传输位图所需的通信量远高于基于邻居节点的选择方法，但前者的不完整结果检测率高于后者．为了平衡节点通信量和不完整结果检测率，文献［8］提出一种混合节点选择方法．时间交叉验证策略利用数据之间的关系，每个节点si构造一个缓冲区（Buffer）记录最近I个连续提交周期的数据分布情况，并将其附加到每一个非空桶中．由于引入额外的时空信息，时空交叉验证技术的通信代价较高．

文献［9］研究了两层传感器网络中的安全多维范围查询处理技术．为了保护用户查询和节点数据的隐私，将文献［1］中的桶技术扩展到多维数据空间，并提出三种完整性验证策略，分别是：编码策略（Encoding）、概率空间交叉验证策略（Probabilistic Spatial Crosscheck）和概率时间交叉验证策略（Pr obabilistic Temporal Cr osscheck）．第一种验证策略是文献［1］的编码策略在多维数据空间的扩展，后两种验证策略是对文献［7］的时空交叉验证技术的概率化，即并不是将所有其他节点的位图消息和自己的缓冲区信息附加到所有非空桶中，而是以一定的概率选择性地附加这些验证信息．显然，这种概率性的验证策略不能100%检测出不完整结果．

2．2 前缀成员验证技术

前缀成员验证技术（Prefix Membership Verification）最早应用于跨域协作防火墙（Cr oss-Do main Cooperative Firewall）领域，允许位于不同网络管理域的防火墙在不知道对方规则的情况下协同执行各自规则并过滤数据包．文献［10］首次提出前缀成员验证技术，文献［11］对其进行了改进．前缀成员验证技术根据规则判断一个数值x和一个前缀P的成员关系：如果x∈P，当且仅当P∈PF（x），PF（x）是x的前缀族．

Safe Q协议［12-13］采用前缀成员验证技术实现两层网络中的隐私保护范围查询．Saf e Q的核心思想：分别为用户查询和节点数据构建一个特殊集合，将数值与区间的成员关系判断转化为两个集合交集是否为空的判断．具体过程：给定一个整数d，其二进制表示为b1b2…bw（bi∈｛0，1｝），d的第i个前缀表示为b1b2…bw－i＋1*…*，d的前缀族F（d）被定义为一个包含d的第0个至第w个前缀的集合，即F（d）＝｛b1b2…bw，b1b2…bw－1*，…，b1*…*，*…*｝．给定一个查询范围［a，b］，其前缀码S（［a，b］）被定义为能够覆盖［a，b］中所有整数的前缀的最小集合．令N（）为数字化函数，对F（d）和S（［a，b］）进行数字化处理，即依次将F（d）和S（［a，b］）中的“*”用“1”替换，并在第一个“0”位前添加“1”，得到N（F（d））和N（S（［a，b］））．存储节点判断d是否属于［a，b］，只需判断是否满足N（F（d））∩N（S（［a，b］））≠∅．图2演示了Safe Q判断12是否属于［11，14］的过程．为了提高存储节点的查询效率，节点在上传数据前对数据进行升序排列，存储节点只需找到满足判定条件的数据上下界．考虑到存储节点可能被攻击者俘获从而破坏结果的完整性，Safe Q设计了一种邻居关系链（Neighbor hood Chain），要求每个节点在上传数据时为每个数据项附加其在本提交周期产生的有序数据集中对应的最近左数据项，通过检查邻居关系链的数据有序性和连续性验证结果的完整性．前缀成员验证技术可以避免桶技术泄露粗粒度信息的问题，同时得到精确的查询结果．除了数据邻居链，文献［13］还构建了Mer kle哈希树（Mer kle Hash Tree）［15］验证结果．由于前缀成员验证技术将一个数值转换成一个集合，因此增加了节点的通信量．

2．3 保序加密技术

保序加密技术（Order-preserving Encryption）是一种确定性的加密机制，依赖于特定的保序加密函数实现．一个数据空间经过保序加密函数处理后被映射到另一个数据空间，假设原数据空间中的任意两个不相等的数据d1和d2分别对应于新数据空间中数据D1和D2且d1≠D1，d2≠D2，如果d1＞d2，那么必有D1＞D2，即新数据空间中数据仍然保持原数据空间中的大小关系［14］．保护加密技术最早由文献［16］提出，一个保序加密函数被认为是安全的当且仅当攻击者只有通过穷举攻击才能破解密文．因此，保序加密技术的安全程度取决于保序加密函数的复杂程度，函数越复杂，安全性越高．

SEF协议［17］提供传感器网络中的安全范围查询．为了保护隐私性，SEF使用保序对称加密技术（Or der-preser ving Sy mmetric Encr yption，OPSE）［14］在不泄露敏感信息的情况下保证范围查询的顺利执行．为了保护结果的真实性和完整性，SEF设计出一种数据结构——AI树（Authenticity＆Integrity Tree）对查询结果进行验证．SEF协议分为3部分：传感器节点处理、管理节点处理和基站处理．在传感器节点上，假设采集到N个数据d1，…，dN，首先使用OPSE对N＋2个数据d0，d1，…，dN，dN＋1（d0／dN＋1分别是值域的最大／小值）加密处理得到e0，…，eN＋1，然后排序加密数据项并自下而上构造一棵AI树．在AI树中，叶子节点存储加密数据项，中间节点和根节点存储孩子节点的摘要值（Digest）和两个标签（Label），一个标签记录节点在树中的层次（Level），另一个标签记录该节点在父节点中的位置．图3是一棵AI树，节点采集到9个数据项（不包括d0和dN＋1），这些数据项在AI树中按照升序排列．h4－5表示该节点存储了e4和e5的摘要信息，位于树的第1层，是其父节点的左孩子．这棵AI树的HMAC＝h0－10．为了减少通信开销，节点只将HMAC和加密数据项发送到管理节点．管理节点根据加密数据项重构节点的AI树．用户查询范围使用同样的OPSE处理．当收到来自基站的范围查询，管理节点检查传感器节点的数据，将落在查询范围的加密数据项和相应的上下界作为结果返回基站．此外，存储节点还需要返回该节点的验证对象（Verification Object，VO），用于验证结果的真实性和完整性．VO包括3部分：该节点AI树的H MAC；从根节点到下边界父节点所经过节点的左兄弟节点摘要值；从根节点到上边界父节点所经过节点的右兄弟节点摘要值．当基站收到管理节点返回的结果，首先根据摘要值重构AI树和H MAC，并与收到的H MAC进行比较，若相等，则结果是真实完整的，否则结果无效．以图3为例，当结果为｛e5，e6，e7，e8｝时，VO＝｛h0－3，h4，h9，h10｝．基站根据h4和h5重构出h4－5，使用同样的方法重构出h6－7、h8－9、h4－7、h8－10、h0－7．最终重构出h0－10．基站比较重构的h0－10是否等于收到的HMAC，从而判断结果的真实性和完整性．

图3 AI树的例子Fig．3 An example of AI tree

EQ协议［18］向传感器网络中引入云节点作为存储节点，使用顺序加密机制（Or der Encryption Mechanism，OEM）防止敏感信息泄露，构造位图表（Bit-Map Table，BM）和异或链表（XOR Linked List，X2L）验证结果的完整性．与SEF协议一样，EQ协议也分为3个部分：传感器节点处理、管理节点处理和基站处理．传感器节点在上传数据之前需要执行4个步骤：①将感知数据映射到有序区间中；②根据感知数据的坐标（区间，位置）构建BM表，并计算出BM值；③在每个感知数据中加入左右邻居数据，得到X2L，并使用OEM加密；④将节点号、时间信息和加密数据一起发送到云节点．基站也使用相同的OEM机制加密查询范围，并下发到云节点．云节点根据加密的查询范围和感知数据执行查询任务，并返回查询结果．当节点的感知数据不符合查询要求时，要求云节点上传该节点的BM值．基站解密数据，根据X2L和BM值判断结果是否完整．图4演示了EQ协议的执行过程．

文献［19］结合保序函数（Order-preserving Function）、置换函数（Per mutation Function）和d-阶分离矩阵（d-disj unct Matrix）实现两层传感器网络中的隐私保护范围查询，但忽略了结果被篡改的情况．在协议中，基站为所有传感器节点构造相同的保序函数p、置换函数σ和d阶分离矩阵M＝（M1，M2，…，Mn）．假设节点在t时刻采集到一系列数据D＝｛d1，d2，…，dm｝，允许出现重复数据．节点首先使用保序函数处理数据得到σ（D）＝｛σ（d1），σ（d2），…，σ（dm）｝，σ（D）去除重复元素，然后使用置换函数处理数据得到p（D）＝｛p（d1），p（d2），…，p（dm）｝，p（D）保留重复元素，最后根据d阶分离矩阵，计算出列向量C节点将C和σ（D）发送到存储节点．基站使用相同的保序函数σ将查询范围［a，b］转换为｛Qmin，Qmax｝，其中，Qmin＝min｛σ（d）∣d∈［a，b］｝，Qmax＝max｛σ（d）∣d∈［a，b］｝．存储节点根据｛Qmin，Qmax｝和σ（D）确定满足条件的数据集D′，并将D′和C返回基站．基站根据D′、C＝（c1，c2，…，cm）T和M＝（M1，M2，…，Mn）求解出D′中每个数据的频数．d-阶分离矩阵在传感器节点上存储需要额外空间．当查询范围较大时，根据C和A确定唯一结果的计算复杂度较高．

图4 EQ协议的执行过程Fig．4 Process of EQ

文献［20-21］提出一种支持隐私性与完整性保护的范围查询协议．为了保护敏感信息的隐私性，协议使用数据区间表示感知数据和查询范围，并基于多项式技术构造保序加密函数和查询函数分别保护感知数据和查询范围．传感器节点将保序加密后的数据发送到存储节点．基站将查询条件转换为一个与传感器节点ID相关的查询条件后发送到存储节点．存储节点分别为每个提交数据的传感器节点计算查询条件，并完成查询任务．为了保护结果的完整性，协议采用数字水印技术（Digital Water marking），为数据区间构建一条水印链，基站借助该水印链可以验证结果是否真实可靠．文献［20-21］还提出一种数据结构——多维区间树（Multi-Di mensional Range Tree，MDRT）实现隐私保护多维范围查询，同时构造多条水印链保护结果完整性．对于存储空间和计算能力有限的传感器节点，MDRT需要额外的存储空间，并且构造复杂．

2．4 其他隐私保护技术

ZOSR协议［22］采用R-D判别方法（又称为半径距离判别法）和Z-O编码比较技术（又称为0-1编码比较技术）［23］实现隐私保护范围查询．R-D判别方法将数值与查询区间上下边界的比较转化为该数值到查询区间中心的距离与查询范围半径的比较．Z-O编码比较技术对敏感信息进行编码：令xnxn－1…x1是数值x的二进制形式，其中xi∈｛0，1｝，且1≤i≤n，x的Z编码集合和O编码集合分别是Zx＝｛xnxn－1…xi1∣xi＝0，1≤i≤n｝和Ox＝｛xnxn－1…xi∣xi＝1，1≤i≤n｝．Z-O编码具有的性质：x＞y当且仅当Ox∩Zy≠∅．ZOSR协议的具体过程如下：每次查询时，基站首先将本次查询参数（包含查询范围的中心值）秘密分配给所有传感器节点，并向存储节点发送查询范围［a，b］半径的O编码集合．传感器节点根据收到的查询参数，计算感知数据到查询范围中心距离的Z编码集合，并将其发送到存储节点．存储节点利用Z-O编码的性质进行查询处理，返回查询结果．为了防止被俘获节点恶意返回错误结果，要求存储节点广播查询半径的O编码集合，每个传感器节点自行判断其数据是否符合查询条件，并生成验证码发送到存储节点．基站根据这些验证码检验查询结果是否完整．ZOSR协议在验证结果时需要传感器节点二次参与，增加了传感器节点通信量和计算量．此外，传输Z-O编码也会增加节点通信代价．

ESRQ协议［24］是一种基于特殊编码的隐私保护范围查询协议．ESRQ利用布隆过滤器（Bloo m Filter）［25］的良好特性设计出一种特殊的二进制位串——BF码，使用单向散列函数将感知数据和查询范围分别映射成一个BF码．BF码在保护感知数据和用户查询的同时，保留了一定的特征信息，将对数值是否落在指定范围的判断转换成对两个BF码的比较，从而允许管理节点在不获取敏感信息的情况下完成范围查询．ESRQ协议借助有序数据之间的顺序关系提出一种完整性验证机制，允许基站检测出不合法的结果．此外，ESRQ协议还对性能进行了改进：一方面，根据BF码“0”和“1”的分布特征设计出两种无损压缩机制——基于绝对位置的压缩机制和基于相对位置的压缩机制，缩短BF码的长度，降低节点通信成本；另一方面，设计出一种多编码机制，将一个查询范围划分成若干组，依次为每个组构造相应的BF码，在不增加传感器节点通信代价的情况下降低结果的误识别率．

除了窃听攻击和篡改攻击，文献［26］还考虑了节点之间的共谋行为，提出一系列抵御共谋攻击的隐私保护范围查询协议CPRQ．其核心思想是：在ESRQ协议的基础上，设计出差异化的BF编码机制，避免不同节点具有相同的“数据-BF码”映射关系，再参照差异编码规则，设计出与之匹配的成员关系判定机制．差异化的BF码不仅可以抵御多种攻击，而且保证管理节点完成范围查询．CPRQ系列协议包括c-CPRQ、r-CPRQ和u-CPRQ三种协议．c-CPRQ基于混淆机制为每个传感器节点构造不同的散列函数集合，防止恶意节点根据共享的散列函数集合推测出其他节点的“数据—BF码”映射关系，但存在误否定（False Negative）问题，导致结果不完整．为了消除误否定，r-CPRQ采用宽松成员关系判定机制，避免误否定的发生，但是由于r-CPRQ的判定机制比c-CPRQ的宽松，无法有效过滤不符合要求的数据，导致误识别率增加．为了实现低误识别率和零误否定率，u-CPRQ基于不确定机制为每个传感器节点重新构造散列函数集合，使得不同节点的散列函数的数量和组合均具有不确定性，防止节点共谋．

SEMR协议［27］利用矩阵变换技术实现隐私保护多维范围查询．其主要思想是：基站构造一个秘密的3×3非奇异特征构造矩阵M，并根据矩阵M为每个传感器节点随机构造一个特征构造矩阵W且W＝M－1．基站和传感器节点分别使用M和W构造变换查询（Transf or med Quer y）和特征值矩阵（Characteristic Val ue Matrix），然后将变换查询和特征值矩阵发送到存储节点，存储节点利用变换查询和特征值矩阵在不获取敏感信息的情况下完成查询任务．具体过程如下：令D＝＜d1，d2，…，dz＞表示传感器节点采集的一个z维数据，为每一维数dj（1≤j≤z）构造数据向量νj＝（（dj）2，dj，1），从而得到一个z×3的数据矩阵V＝（ν1，ν2，…，νz）T，利用公式CV＝V·W计算出数据D的特征值矩阵CV．传感器节点将加密后的数据D以及对应的特征值矩阵CV一起发送到存储节点．令＜［a1，b1］，…，［az，bz］＞表示一个z维的查询命令，基站为每一维［aj，bj］构造查询向量qj＝（1，－（aj＋bj），aj·bj），从而构造一个z×3的查询矩阵Q＝（q1，q2，…，qz）T，利用公式TQ＝M·QT计算出变换查询TQ，并将TQ发送到存储节点．存储节点根据TQ和数据D的特征值矩阵CV进行判定：计算CV·TQ得到一个z×z矩阵，如果其对角线上的数值均非正，那么与CV对应的数据D一定落在查询范围内．图5显示了SEMR的执行过程．当不同传感器节点的特征构造矩阵W相同时，SEMR协议不能抵抗共谋攻击．另外，SEMR协议不能抵御篡改攻击．

3 对比分析

近年来，传感器网络隐私保护范围查询处理技术已经成为研究热点，受到学术界越来越多的关注．我们从协议采用的主要隐私保护技术、保护的对象、抵御的攻击模型、隐私保护能力、结果验证能力、节点执行效率、结果精确度等方面对现有的研究成果进行了对比分析，具体详见表1．

从总体上看，现有的隐私保护范围查询研究成果尚未较好地实现隐私性、完整性、高效性和精确性四者之间的均衡．一方面，隐私性要求尽可能减少消息中的敏感信息量，而完整性需要借助一定的信息才能完成结果验证；另一方面，高效性要求协议尽可能降低通信和计算成本，而精确性需要通过节点之间的交互与计算才能实现．

实现隐私保护范围查询的技术多种多样，各有利弊．桶技术虽然可以隐藏敏感信息，但是桶的范围允许攻击者对敏感信息进行合理地估计，并且基于桶技术得到的结果存在一定的误识别，导致结果不精确．尽管保序加密技术使得数据在表面上与原始数据没有直接联系，但是仍然会泄露数据间的大小关系，而且复杂的保序加密函数还会增加节点的计算代价．前缀成员验证技术和Z-O编码技术均将一个数值表示成一个包含多个数值的集合，增加了节点的通信成本．BF编码技术虽然具备较高的隐私包含能力和效率，但结果精确度有待提高．矩阵变换技术大大增加节点的计算代价．此外，并不是所有协议均能抵御窃听、篡改、共谋等多种攻击．不同的攻击模型，需要不同的抵御手段．例如，抵御窃听攻击需要隐藏原始敏感信息；抵御共谋攻击需要引入完整性验证机制，这往往需要加入冗余信息，进一步增加了通信成本；抵御共谋攻击应该避免不同节点使用相同的网络参数和协议规则．

协议名称 主要技术保护的对象节点数据用户查询抵御的攻击模型窃听 篡改 共谋隐私保护能力结果验证能力节点效率通信量 计算量 结果精确度文献［1，6］Spatial Cr osscheck［7-8］Temporal Cr osscheck［7-8］Spatiotemporal Crosscheck［7-8］Probabilistic Spatiotemporal Crosscheck［9］桶技术√ √ √ √ 弱 较强 低 低 低√ √ √ √ 弱 较弱 高 低 低√ √ √ √ 弱 较弱 较高 低 低√ √ √ √ 弱 较强 高 低 低√ √ √ √弱 弱 较高 低 低Safe Q［12，13］ 前缀成员验证技术 √ √ √ √较强 强 高 高 精确SEF［17］EQ［18］文献［19］文献［20-21］保序加密技术√ √ √ √ 较强 强 高 高 精确√ √ √ √ 较强 强 高 高 精确√ √ √ 较强 无 较高 高 较高√ √ √ √较强 强 低 高 精确ZOSR［22］ Z-O编码技术 √ √ √ √较强 强 高 较低 精确ESRQ［24］c-CPRQ［26］r-CPRQ［26］u-CPRQ［26］BF编码技术√ √ √ √ 较强 强 低 较低 高√ √ √ √ √ 强 强 低 较低 低√ √ √ √ √ 强 强 低 较低 低√ √ √ √ √强 强 低 较低 高SEMR［27］ 矩阵变换技术 √ √ √较强 无 较高 高 精确

4 未来工作展望

传感器网络隐私保护范围查询处理技术属于新兴研究领域，还有很多挑战性问题需要进一步研究．

（1）安全强度、执行效率、结果精度之间的优化均衡

节点能量、通信和计算能力、存储空间等资源受限，是传感器网络的重要特征．然而隐私保护范围查询协议往往需要较高的通信与计算代价，降低了执行效率，增加了能量开销，同时缩短了网络生命周期．传感器网络隐私保护范围查询协议的优化目标是，在安全强度、执行效率和结果精度三者之间取得平衡，在保证高强度隐私保护的前提下，减少通信与计算代价，提高执行效率和结果精确度．现有的隐私保护范围查询协议虽然提出了许多优化平衡策略，但还远远不能满足传感器网络的实际应用需求，需要进一步研究．

（2）隐私保护复杂范围查询技术

近年来，传感器技术不断进步，使得单个传感器节点可以感知多种属性信息，例如，在智能家居中，智能传感器可以同时感知温度、湿度、光照等信息．与此同时，用户查询也日趋复杂化，从单维数据到多维数据，从历史查询到实时查询，从快照查询到连续查询．现有研究成果主要研究了单维、历史、快照式范围查询中的隐私保护技术，极少研究隐私保护多维范围查询，多维数据之间的关联性以及节点通信开销与计算代价随着维度增加而快速递增，增加了隐私保护多维范围查询的难度．同时现有成果缺少对实时、连续式范围查询中隐私技术的研究．因此，研究隐私保护复杂范围查询技术是传感器网络应用发展的需要，也是未来的重点研究方向．

（3）复杂攻击环境下的隐私保护范围查询处理技术

作为物联网的重要组成部分，传感器网络的应用需求日趋多样化，对隐私保护的要求越来越高；同时，攻击者的攻击方式日益复杂、攻击能力日益强大．现有的隐私保护范围查询协议较多关注窃听攻击和简单的篡改攻击，极少关注危害性更大的复杂攻击，如共谋攻击、重放攻击等．传感器网络的开放性导致我们无法预知攻击者的攻击方式和攻击能力，并且抵御单一攻击的传感器网络已经无法保障复杂攻击环境下网络的安全性．为了保证复杂攻击环境下隐私保护范围查询协议的安全性能，必须尽可能提高协议对各类攻击的抵御能力．

［1］SHENG B，LI Q．Verifiable privacy-preserving range query in t wo-tiered sensor net wor ks［C］／／INFOCOM 2008．The 27t h Conference on Co mputer Co mmunications．IEEE，2008．

［2］ROBERT S，ANDRAS F．Energy i mplication of net wor k sensor designs［J］．（2008-04-01）［2015-06-30］．http：／／www．cs．ber keley．edu／-zewczyk／cs252／paper．pdf．

［3］GNA WALI O，JANG K Y，PAEK J，et al．The tenet architect ure f or tiered sensor net wor ks［C］／／Pr oceedings of the 4th international conference on Embedded net worked sensor systems．ACM，2006：153-166．

［4］HACIGÜMÜSH，IYER B，LI C，et al．Executing SQL over encr ypted data in t he database-ser vice-pr ovider model［C］／／Proceedings of the 2002 ACM SIGMODinternational conference on Management of data．ACM，2002：216-227．

［5］HORE B，MEHROTRA S，TSUDIK G．A privacy-preser ving index f or range queries［C］／／Proceedings of t he Thirtiet h inter national conference on Very lar ge data bases-Volu me 30．VLDB Endowment，2004：720-731．

［6］SHENG B，LI Q．Verifiable privacy-preser ving sensor net wor k storage f or range query［J］．Mobile Co mputing IEEE Transactions on，2011，10（9）：1312-1326．

［7］SHI J，ZHANG Y．Secure range queries in tiered sensor net works［C］／／INFOCOM 2009，IEEE．IEEE，2009：945-953．

［8］SHI J，ZHANG R，ZHANG Y．A spatiotemporal approach f or secure range queries in tiered sensor net wor ks［J］．IEEE transactions on wireless co mmunications，2011，10（1）：264-273．

［9］ZHANG R，SHI J，ZHANG Y．Secure multidi mensional range queries in sensor net wor ks［C］／／Proceedings of t he tenth ACMinternational sy mposiu m on Mobile ad hoc net working and computing．ACM，2009：197-206．

［10］CHENG J，YANG H，WONG S H Y，et al．Design and i mplementation of cr oss-do main cooperative firewall［C］／／Net wor k Protocols，ICNP 2007．IEEE International Conference on，2007：284-293．

［11］LIU A X，CHEN F．Collaborative enf orcement of firewall policies in virtual private net wor ks［C］／／Proceedings of t he t went y-sevent h ACM sy mposiu m on Principles of distributed co mputing．ACM，2008：95-104．

［12］CHEN F，LIU A X．Safe Q：Secure and efficient query processing in sensor net wor ks［C］／／INFOCOM，2010 Pr oceedings IEEE．IEEE，2010：1-9．

［13］CHEN F，LIU A X．Privacy-and integrity-preserving range queries in sensor net works［J］．Net working，IEEE／ACM Transactions on，2012，20（6）：1774-1787．

［14］BOLDYREVA A，CHENETTE N，LEE Y，et al．Order-preserving sy mmetric encryption［M］／／Advances in Cr yptology-EUROCRYPT 2009．Berlin Heidelber g：Springer，2009：224-241．

［15］MERKLE R C．A certified digital signat ure［C］／／Advances in Cr yptology－CRYPTO＇89 Proceedings．New Yor k：Springer，1990：218-238．

［16］AGRA WAL R，KIERNAN J，SRIKANT R，et al．Or der preserving encr yption f or nu meric data［C］／／Pr oceedings of t he 2004 ACM SIGMODinter national conference on Management of data．ACM，2004：563-574．

［17］BU J，YIN M，HE D，et al．SEF：a secure，efficient，and flexible range quer y sche me in t wo-tiered sensor networ ks［J］．Inter national Jour nal of Distributed Sensor Net wor ks，2011（3）：876-879．

［18］TSOU Y T，L U C S，KUO S Y．Privacy-and integrity-preserving range quer y in wireless sensor net wor ks［C］／／Global Co mmunications Conference（GLOBECOM），2012 IEEE．IEEE，2012：328-334．

［19］NGUYEN T D，BUI T V，DANG V H，et al．Efficiently preser ving data privacy range queries in t wo-tiered wireless sensor net wor ks［C］／／Ubiquitous Intelligence＆Co mputing and 9t h Inter national Conference on Autono mic＆Tr usted Co mputing（UIC／ATC），2012 9t h Inter national Conference on．IEEE，2012：973-978．

［20］LI R，LIN Y，YI Y，et al．A privacy and integrity preser ving range quer y pr otocol in t wo-tiered sensor net wor ks［J］．Chin J Co mput，2013，36：1194-1209．

［21］YI Y，LI R，CHEN F，et al．A digital water mar king appr oach to secure and precise range quer y processing in sensor net wor ks［C］／／INFOCOM，2013 Proceedings IEEE．IEEE，2013：1950-1958．

［22］DOU Y，HUANG H，WANG R，et al．Secure range query in t wo-tiered wireless sensor net wor ks［J］．Jisuanji Yanjiu yu Fazhan／Co mputer Research and Develop ment，2013，50（6）：1253-1266．

［23］LIN H Y，TZENG W G．An efficient sol ution t o t he millionaires＇proble m based on ho mo mor phic encryption［C］／／Applied Cr yptography and Net wor k Security．Berlin Heidelber g：Springer，2005：456-466．

［24］ZHANG X，DONG L，PENG H，et al．Achieving efficient and secure range quer y in t wo-tiered wireless sensor net wor ks［C］／／Pr oceedings of t he IEEE／ACMInter national Sy mposiu m on Qualit y of Ser vice，Hong Kong，China．IEEE，2014：26-27．

［25］BLOOM B H．Space／ti me trade-offsin hash coding with allowable err ors［J］．Co mmunications of t he ACM，1970，13（7）：422-426．

［26］ZHANG X，DONG L，PENG H，et al．Collusion-aware privacy-preser ving range query in tiered wireless sensor net wor ks［J］．Sensors，2014，14（12）：23905-23932．

［27］DONG L，ZHU J，ZHANG X，et al．SEMR：Secure and Efficient Multi-Di mensional Range Quer y Pr ocessing in Two-tiered Wireless Sensor Net wor ks［M］／／Web-Age Inf or mation Management．［S．l．］：Springer Inter national Publishing，2015：520-524．