基于优化Paillier算法的两层无线传感器网络范围查询计算方法

A Range Query and Calculation Method Based on Optimized Paillier Algorithm in Two-Layer Wireless Sensor Networks

摘要

针对现有两层无线传感器网络范围查询中数据计算效率较低以及感知节点能耗消耗较高的问题，提出一种基于优化Paillier算法的两层无线传感器网络范围查询计算方法。首先，利用具有可验证性的优化Paillier方法加密感知数据，在保证数据安全隐私的前提下实现密文下的数据运算，将计算平台从查询节点转移到存储节点，提高数据运算效率。其次，提出一种基于最左0-1编码和HMAC数据摘要算法的低功耗数值比较方法，在保证数据稳定性的前提下，降低感知节点能耗。最后，给出该方法的具体设计与实现，并利用树莓派和温湿度、光照强度传感器构建感知节点，利用英伟达TX2边缘计算平台构建存储节点，以此构建实验平台，将范围查询计算方法在该平台进行移植与实现。与现有方法在感知节点能耗、数据计算效率方面进行对比分析，结果表明，本文方法能够在降低感知节点能耗的基础上提高数据计算效率。

Abstract

Aiming at the problems of low data calculation efficiency and high energy consumption of sensing nodes in the existing two-layer wireless sensor network range query, a two-layer wireless sensor network range query calculation method based on the optimized Paillier algorithm is proposed. First of all, the verifiable optimized Paillier method is used to encrypt the sensing data, and the data operation under the ciphertext is realized under the premise of ensuring data security and privacy, and the computing platform is transferred from the query node to the storage node to improve the efficiency of data operation. Secondly, a low-power numerical comparison method based on left-most 0-1 encoding and HMAC data digest algorithm is proposed, which can reduce the energy consumption of sensing nodes under the premise of ensuring the stability of data comparison. Finally, the specific design and implementation of the method is given, and the sensing node is constructed by using the Raspberry Pi, temperature, humidity and light intensity sensors, and the storage node is constructed by using the NVIDIA TX2 edge computing platform, so as to build an experimental platform, and the range query calculation method implemented in the platform is transplanted and implemented. Compared with the existing methods in terms of energy consumption of sensing nodes and data computing efficiency, the results show that the method in this paper can improve the efficiency of data computing on the basis of reducing the energy consumption of sensing nodes.

Graphical abstract

关键词

两层无线传感器网络 / 范围查询 / 优化Paillier算法 / 最左0-1编码

Key words

two-layer wireless sensor network / range query / optimizing Paillier algorithm / left-most 0-1 encoding

0　 引 言

当前，无线传感器网络（WSN,wireless sensor network）在自然环境感知、军事监测、工业生产等各种重要领域都有着广泛的应用^[1，2]。其中，两层无线传感器网络（two-layer wireless sensor network）是一种以感知节点为底层，存储节点为中间层，查询节点为上层的无线传感器网络，具有网络拓扑结构简单、链路质量稳定、路由结构单一、查询高效和负载均衡等技术特点。隐私数据范围查询作为一种获取传感器数据、监控节点的必要手段，在当前关于两层无线传感器网络的研究中得到广泛关注^[3~5]。在现实应用中，感知节点往往被布置于长时间无人管理的户外环境，存储节点则需要存储大量感知数据并负责执行查询节点查询请求。因此如何降低感知节点获取感知数据和数据上传过程中所产生的能耗，提高存储节点数据隐私安全性成为了隐私数据范围查询研究领域关注的重点^[6，7]。

针对两层无线传感器网络范围查询，Chen等^[8]首次提出一种基于前缀编码的秘密比较机制范围查询方法SafeQ (secure and efficient query)。SafeQ方法使用对称加密算法对感知数据进行加密，采用前缀编码方案保证范围查询过程中的隐私保护。为了确保数据安全，该方法引入邻居链机制实现数据可验证性。虽然SafeQ方法能够有效地保证网络查询隐私安全性和数据一致性，但是由于采用了前缀编码，在查询过程中需要上传较多的编码信息和邻居链信息，因此感知节点会产生较高的通讯能耗。Dai等^[9]提出一种具有隐私安全性的低功耗范围查询方法CSRQ (communication-efficient secure range queries)。CSRQ方法使用AES对称加密算法对感知数据加密，使用0-1编码和HMAC算法生成数值比较链。在此基础上，将经过算法摘要的数值比较链进一步使用Hash算法进行映射，减少了数据比较链密文的长度，降低了感知节点的通讯能耗。但是该方法依然存在感知节点通讯能耗高、数值比较计算量大等问题。胡等^[10]在CSRQ方法的基础上提出一种基于压缩HMAC方法的传感器网络范围查询方法，该方法采用反向0-1编码和压缩HMAC方法构建数据比较链，有效地提高范围查询中的数值比较效率，并且降低了感知节点通讯能耗。Deng等^[11]针对存储节点和查询节点中产生的数据隐私安全问题，提出一种基于HMAC、base64编码和优化0-1编码的两层无线传感器网络范围查询方案，该方法在降低感知节点通信能耗的同时也降低了感知节点的计算能耗。该方法考虑到了多维感知数据下的范围查询，将范围查询方法从一维推广到多维。

在实际应用中，经过范围查询后经常会产生数据计算的需求，但是现有方法中对范围查询下的数据计算方法研究较少。基于此，本文提出一种基于优化Paillier算法^[12]的两层无线传感器网络范围查询计算方法。首先，为了提高范围查询方法下的数据计算效率，本文利用优化Paillier算法加密感知数据，解决了感知数据密文下的数据计算问题，将数据计算平台由查询节点转移到存储节点，减少大量待计算数据在网络传输中所花费的时间消耗。其次，现有方法中，感知节点在数据加密和数据传输过程中所产生的能耗仍然具有优化空间，从降低感知节点能耗角度出发，提出一种基于最左0-1编码和Hash消息身份验证编码机制HMAC的高效数值比较方法。

1　 系统模型与问题描述

1.1　两层无线传感器网络结构

两层无线传感器网络可以被划分为多个查询集合，体系结构如图1所示，每个查询集合由多个计算、存储资源受限的感知节点和一个资源丰富的存储节点构成。存储节点用于存储感知节点提交的数据，并响应查询节点的数据查询请求。感知节点造价便宜且自身可以配置多种不同类型的传感器，如温湿度、光照度、二氧化碳浓度等传感器，完成各类感知任务并通过无线网络将感知数据上传至存储节点。查询节点产生数据范围查询和查询计算请求，接收存储节点返回的结果，对结果进行验证等。

1.2　范围查询计算模型

根据两层无线传感器网络结构，查询模型定义如下：

1） 两层无线传感器网络可被划分为多个查询单元，假设第i个查询单元U_i由多个传感器节点和一个存储节点M构成，每一个感知节点和存储节点都分配一个唯一编号，查询单元U_i内第i个感知节点编号为s_i，感知节点集合表示为S=\{s_{\mathrm{1}},s_{\mathrm{2}},s_{\mathrm{3}},\dots ,s_i,\dots ,s_n\}，查询单元U_i记为U_i=\left\{M,S\right\}。

2） 范围查询请求为Q_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}=\{T,\Gamma ,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i]\},T为待查询的时间段，T=\{T_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}},T_{\mathrm{e}\mathrm{n}\mathrm{d}}\}，\Gamma为待查询的感知节点，S_{\mathrm{i}}为待查询的传感器类型，d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i为范围查询下界，d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i为范围查询上界。

3） 在两层无线传感器网络查询计算请求中，查询节点会产生数据计算操作，传感器数据计算模型是在范围查询的基础上加入数据计算操作命令，针对一维的数据计算可以形式化为：Q_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}=\{\Gamma ,T,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i],\mathrm{c}\mathrm{m}\mathrm{d}\}。其中，\mathrm{c}\mathrm{m}\mathrm{d}为数据计算操作命令，其语法格式基于\mathrm{S}\mathrm{q}\mathrm{l}语句。例如，计算节点002在2021年11月10日一天中20到30摄氏度的平均温度，可公式化为：

Q_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}=\{"\mathrm{002}","\mathrm{2021}-\mathrm{11}-\mathrm{10}\mathrm{00}:\mathrm{00,2021}-\mathrm{11}-\mathrm{11}\mathrm{24}:\mathrm{00}",\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e},\left[\mathrm{20,30}\right]"\mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{v}\mathrm{e}(\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e})\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}"\}

2　 优化Paillier算法及其密钥管理机制

2.1　优化Paillier加密算法

与现有范围查询方法中广泛采用AES对称加密算法不同，本文使用Paillier同态加密算法对感知数据进行加密。Paillier加密算法为非对称加密算法，因此在密钥管理方面优于AES对称密钥加密算法，但是传统Paillier算法计算复杂，且不具备数据验证功能，不适用于感知节点这类计算资源敏感型硬件。因此，本文基于文献[13]和文献[14]提出一种具有信息验证的高效Paillier算法，优化Paillier加密算法采用“加密+签名”的加密体制实现数据可验证性，该加密体制的好处在于比单独进行加密、签名操作的效率要高。优化Paillier加密体制本质为对称加密和公钥体制的混合，执行过程如算法1，其中，明文，随机数,H\left(x\right)为\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}函数，||是消息连接符号,\ll和\gg分别为左移和右移符号。

由于r是在加密之前由加密用户随机选取的，加密用户可以在加密之前随机选择多个r\in {\mathbb{Z}}_n^{\mathrm{*}}，并预先计算r^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}},并在加密时用户随机选取一个r^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}对明文进行加密。这样，加密只需在{\mathbb{Z}}_{n^{\mathrm{2}}}上做两个简单的乘法运算，进一步提高了加密的效率。并且由于签名机制的引入，可以验证消息明文m的数据完整性和准确来源，如果验证失败则丢弃，验证成功则采用，优化Paillier算法与Paillier算法加、解密运算次数对比如表1所示。

2.1.1　优化Paillier算法安全性证明

性质1 优化Paillier与传统Paillier算法安全性等价。

语义安全性证明：假定给出明文x和y以及其中一条明文对应密文C的情况下，对于优化Paillier算法攻击者无法判断密文C对应的是x还是y的密文。这是由于在数学上判断n次剩余问题是困难的。针对优化Paillier算法和Paillier算法都是判断\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}的剩余问题，因此两者语义安全性问题等价，优化Paillier算法具有强安全性。

2.1.2　优化Paillier算法同态性分析

对于优化Paillier算法假设有明文x和y可得：

C(x)=(\mathrm{1}+(x||r_x)n){z_x}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}（1）

C(y)=(\mathrm{1}+(y||r_y)n){z_y}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}（2）

针对同态加法运算可得(3)式：

C(x)\otimes C(y)\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}=[(\mathrm{1}+(x||r_x)n){z_x}^n]\otimes \left[(\mathrm{1}+\left(y|\left|r_y\right|n\right){z_y}^n\right]\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}=

\left[\mathrm{1}+n\left(x\left|\left|r_x+y\right|\right|r_y\right)\right](z_x{z}_y{)}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\mathrm{2}}（3）

则C(x)\otimes C(y)=C(x+y)成立，因此优化Paillier算法具有加法同态性。

2.2　密钥管理机制设计

本文基于两层无线传感器网络模型设计了密钥管理协议，协议具体流程图如图2所示。

步骤1 感知节点中设置了感知节点ID，在请求组网时发送感知节点ID信息，存储节点在接收到ID信息后验证ID信息是否合法，合法则将设备ID信息发送给查询节点。

步骤2 查询节点接收到存储节点发送的设备ID后，生成优化Paillier算法中公钥\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}和私钥\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{r}\mathrm{i}}，为了防止公钥\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}被非法篡改，利用HMAC算法对私钥进行信息摘要得到\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}^{\mathrm{\text{'}}}，最后将\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}和\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}^{\mathrm{\text{'}}}发送给存储节点。

步骤3 存储节点在接收到公钥\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}和公钥摘要信息后，判断\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}^{\mathrm{\text{'}}}与\mathrm{K}\mathrm{e}{\mathrm{y}}_{\mathrm{p}\mathrm{u}\mathrm{b}}的是否匹配，如果匹配感知节点执行隐私数据上传步骤，如果不匹配，继续重复步骤1。

3　 基于优化Paillier算法的范围查询计算方法

3.1　基于最左0-1编码的数值比较方法

0-1编码由Lin等^[15]于2005年首次提出，其主要功能是保证两个数据在不泄露数据原文的前提下进行数值比较。本文基于文献[16]提出一种优化0-1编码，并将其命名为最左0-1编码。最左0-1编码在0-1编码的基础上优化了编码方式和数值化过程，其编码规则如下，设正整数B=\{b_{n-\mathrm{1}},b_{n-\mathrm{2}},\dots ,b_{\mathrm{1}},b_{\mathrm{0}}\}为n位二进制数据。其中，b_{n-\mathrm{1}}是数值B的最高位，b_{\mathrm{0}}是数值B最低位。则二进制序列B的最左1编码为：Z(B)=\{b_{n-\mathrm{1}},b_{n-\mathrm{2}},\dots ,b_{i-\mathrm{1}},\mathrm{1}|b_i=\mathrm{0}\bigwedge \mathrm{1}\le i\le n\}，二进制序列B的最左0编码为：O(B)=\{b_{n-\mathrm{1}},b_{n-\mathrm{2}},\dots ,b_i|b_i=\mathrm{1}\bigwedge \mathrm{1}\le i\le n\}。

最左0-1编码基于0-1编码的基本性质，编码过程是在0-1编码的基础上最高位补1，在不改变基础0-1编码格式的前提下保持编码长度一致。例如，x=\mathrm{7}={\left(\mathrm{0111}\right)}_{\mathrm{2}},y=\mathrm{10}={\left(\mathrm{1010}\right)}_{\mathrm{2}}，则x对应的最左0编码Z(x)=\left\{\mathrm{11011,10011}\right\}，最左1编码O(x)=\left\{\mathrm{10101,10001}\right\}，y对应的最左0编码Z(y)=\left\{\mathrm{10001}\right\},最左1编码O(x)=\{\mathrm{10111,10011,10001}\}。对应十进制数最左0编码Z(x)=\left\{\mathrm{27,19}\right\}，最左1编码O(x)=\{\mathrm{21,17}\}，y对应十进制最左0编码Z(y)=\left\{\mathrm{17}\right\}，最左0编码O(y)=\{\mathrm{23,19,17}\}。

最左0-1编码性质及其定理。

性质2 设正整数B为长度为n的二进制数据链，其最左0编码和最左1编码分别为Z(B)和O(B)，则Z\left(B\right)\bigcap O\left(B\right)=\mathrm{\varnothing }。

证 假设Z\left(B\right)和O\left(B\right)有交集，因此在B的二进制编码中必然存在一位同时为0和1，但是一位只能存储1或0，因此假设不成立，证毕。

性质3 设正整数B为长度为n的二进制数据链，其最左0编码和最左1编码分别为Z(B)和O(B)，则Z\left(B\right)和O\left(B\right)集合元素数量之和为n。（证明方法同性质1证明方法一致。）

定理1 对于正整数x和y，当且仅当Z(x)\bigcap O(y)\ne \mathrm{\varnothing }时，x>y成立；当且仅当Z(x)\bigcapO(y)=\mathrm{\varnothing }时，x\le y成立；当且仅当Z(x)=O(y)时，x=y成立。

证 设有二进制长度为n的正整数x和y，对应的0-1编码分别为Z(x),O(x)和Z(y),O(y)。若Z(x)\bigcap O(y)\ne \mathrm{\varnothing }，则Z(x)和O(y)有公共元素b=\{\mathrm{1},b_i,b_{i-\mathrm{1}},\dots ,b_{\mathrm{0}}{\}}_{\mathrm{2}}。设最高位后一位为第i位，通过最左0-1编码原理反推可得x和y的第n到j位相同，但是x的第j-\mathrm{1}位数据为0，而y的第j-\mathrm{1}位数据为1，因此有。同样，根据最左0-1编码机制容易得出Z(x)\bigcap O(y)\ne\mathrm{\varnothing }，因此有。通过逆否命题可以得出x\le y\iff Z(x)\bigcap O(y)=\mathrm{\varnothing }。

由最左0-1编码性质和定理可知，数值x与数值y的大小比较的问题可以转换为对数值x和数值x的最左0-1编码求交集的问题，为了保护数据隐私安全性，对最左0-1编码集合增加HMAC信息摘要处理。以数据x为例，经过HMAC信息摘要后得到\mathrm{H}\mathrm{M}\mathrm{A}{\mathrm{C}}_k(Z(x))和\mathrm{H}\mathrm{M}\mathrm{A}{\mathrm{C}}_k(O(x))，其中k为HMAC密钥，由感知节点和查询节点所共享。

3.2　范围查询计算方法基本思想

基于优化Paillier算法的范围查询计算方法中有范围查询和查询计算两个功能，功能实现主要包含节点查询和查询命令处理两个阶段。

1） 节点查询阶段：查询节点根据用户需求生成范围查询命令或查询计算命令，范围查询命令Q_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}=\{T,\Gamma ,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i]\}，查询计算命令Q_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}=\{\Gamma ,T,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i],\mathrm{c}\mathrm{m}\mathrm{d}\}。

2） 查询命令处理阶段：存储节点M作为查询单元U_i的存储中心，在处理查询节点查询计算命令前需要存储查询单元U_i中感知节点S=\{s_{\mathrm{1}},s_{\mathrm{2}},s_{\mathrm{3}},\dots ,s_i,\dots ,s_n\}的感知数据。存储节点M接收到查询节点的查询计算命令后，根据命令协议对命令进行合法性分析，即\mathrm{C}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}\left(Q\right)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}时对查询计算命令Q在此进行判断。如果Q为范围查询命令，则根据Q_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}=\{T,\Gamma ,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i]\}中的命令信息与存储节点数据库中数据进行数据比较，如果数据比较结果合法，将范围查询结果返回给查询节点。若Q为查询计算命令，存储节点要根据Q_{\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}=\{\Gamma ,T,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i],\mathrm{c}\mathrm{m}\mathrm{d}\}命令中的信息对数据进行查询后使用命令解析器对\mathrm{c}\mathrm{m}\mathrm{d}进行解析，然后执行\mathrm{c}\mathrm{m}\mathrm{d}命令，最后将结果返回给查询节点。

3.3　范围查询计算方法设计

基于优化Paillier算法的范围查询计算方法主要由感知数据上传阶段和范围查询与数据运算阶段两个部分构成。

3.3.1　感知数据上传阶段

在数据采集周期内，感知节点对采集到的感知数据按照传感器类型进行分类并使用优化Paillier算法加密，然后对每类传感器数据中的最大值和最小值先后进行最左0-1编码和HMAC数据摘要操作，最后将数据集密文和经过处理后的最值编码信息上传到存储节点。

查询单元C_i=\left(M,\left\{s_{\mathrm{1}},s_{\mathrm{2}},s_{\mathrm{3}},\dots ,s_m\right\}\right)内任意感知节点s_i在时间周期t_i内采集到N个n维感知数据为\{d_{\mathrm{1}}^{\mathrm{1}},d_{\mathrm{1}}^{\mathrm{2}},d_{\mathrm{1}}^{\mathrm{3}},\dots ,d_{\mathrm{1}}^n\},\{d_{\mathrm{2}}^{\mathrm{1}},d_{\mathrm{2}}^{\mathrm{2}},d_{\mathrm{2}}^{\mathrm{3}},\dots ,d_{\mathrm{2}}^n\},\dots ,{d_N^{\mathrm{1}},d_N^{\mathrm{2}},d_N^{\mathrm{3}},\dots ,d_N^n\}。

设感知节点在查询节点获取到的密钥为\mathrm{K}\mathrm{e}{\mathrm{y}}_i，则在时间周期t_i结束之前s_i依次执行以下操作：

1） 对s_i采集到的感知数据按传感器类型分为n组，每个分组有N个数据\{d_{\mathrm{1}}^{\mathrm{1}},d_{\mathrm{1}}^{\mathrm{2}},d_{\mathrm{1}}^{\mathrm{3}},\dots ,d_{\mathrm{1}}^n\},\{d_{\mathrm{2}}^{\mathrm{1}},d_{\mathrm{2}}^{\mathrm{2}},d_{\mathrm{2}}^{\mathrm{3}},\dots ,d_{\mathrm{2}}^n\},\dots ,\{d_N^{\mathrm{1}},d_N^{\mathrm{2}},d_N^{\mathrm{3}},\dots ,d_N^n\}。

2） 获取每个分组的最大值和最小值，设第i个分组的最大值和最小值分别为d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i和d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i。

3） 对第i个分组的最大值和最小值分别进行最左0-1编码得:\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{0}}(d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i),\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{1}}(d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i),\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{0}}(d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i),\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{1}}(d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i)。为了提高数据通信安全性，同时降低通讯能耗，本文对编码后的最值信息进行编码长度比较，得到元素最小的集合，然后进行HMAC数据摘要运算。假设上传数据为d，则上传规则如(4)式：

(4)

其中，\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}(x)为对x进行HMAC数据摘要操作，\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}(x)为计算编码集合中元素个数。

4） 利用优化Paillier算法对感知数据集进行加密，得到数据密文P(S_d)：

P\left(S_d\right)=\{P\left(d_{\mathrm{1}}^{\mathrm{1}},d_{\mathrm{1}}^{\mathrm{2}},d_{\mathrm{1}}^{\mathrm{3}},\dots ,d_{\mathrm{1}}^n\right),P\left(d_{\mathrm{2}}^{\mathrm{1}},d_{\mathrm{2}}^{\mathrm{2}},d_{\mathrm{2}}^{\mathrm{3}},\dots ,d_{\mathrm{2}}^n\right),

\dots ,P(d_N^{\mathrm{1}},d_N^{\mathrm{2}},d_N^{\mathrm{3}},\cdots ,d_N^n)\}

5） 上传数据\mathrm{U}\mathrm{p}(d)由感知节点s_i的ID、获取时间戳T_{s_i}、分组内最值编码构成，规则如(5)式所示：

\mathrm{U}\mathrm{p}\left(d\right)=\{P\left(S_{d_i}\right),\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}\left(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{u}}\left(d_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)\right),

\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}\left(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{u}}\left(d_{\mathrm{m}\mathrm{i}\mathrm{n}}\right)\right),T_{s_i}\}(5)

最后将最值编码信息和数据密文打包上传到存储节点。

3.3.2　范围查询与数据运算阶段

查询和数据运算协议是在保证查询节点和存储节点之间通信安全性的前提下，完成感知数据的查询和计算。查询节点在用户输入完毕后，将待查询的感知数据类型、查询范围、时间范围、节点设备号组成查询命令Q=\{\mathrm{I}\mathrm{D},T,S_i,[d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i],\mathrm{c}\mathrm{m}\mathrm{d}\}。存储节点在接收到查询命令后，根据最左0-1编码数据对比性质，将满足条件的数据上传给查询节点。在数据计算模式下，利用优化Paillier算法的满足的同态性质，在存储节点完成数据运算，然后将结果返回给查询节点。查询节点接受并解密返回结果，利用Paillier算法验证规则验证，验证成功后返回给用户。具体协议设计如下。

• 查询节点命令生成阶段

1） 以一维数据为例，查询节点接收到用户待查询范围、设备ID、查询时间段、计算命令后先将范围数据d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i进行最左0-1编码和HMAC数据摘要，得到：

H\left(\mathrm{L}\mathrm{Z}\mathrm{O}\left(d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i,d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i\right)\right)=

\{\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{0}}(d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i)),\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{1}}(d_{\mathrm{l}\mathrm{o}\mathrm{w}}^i))

\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{0}}(d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i)),\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}(\mathrm{L}\mathrm{Z}{\mathrm{O}}^{\mathrm{1}}(d_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}^i))\}

2） 根据用户给出的信息组成查询命令Q=\{\mathrm{I}\mathrm{D},T,S_i,H\left(\mathrm{L}\mathrm{Z}\mathrm{O}(d)\right),\mathrm{c}\mathrm{m}\mathrm{d}\}，将查询命令Q发送给存储节点。

• 存储节点处理阶段

1） 利用数据库函数，筛选出符合查询命令的数据行，即匹配设备\mathrm{I}\mathrm{D}、数据上传时间T的数据行。

2） 存储节点在获得数据行后，根据数据化编码类型选择范围编码H\left(\mathrm{L}\mathrm{Z}\mathrm{O}(d)\right)中对应的数据进行对比。若感知数据组最值d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i,d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i与\mathrm{l}\mathrm{o}{\mathrm{w}}_i,\mathrm{h}\mathrm{i}\mathrm{g}{\mathrm{h}}_i满足(6)~(8)式其中之一，则表明该数据满足查询请求。

\mathrm{L}\mathrm{Z}\mathrm{O}(\mathrm{l}\mathrm{o}{\mathrm{w}}_i)\le \mathrm{L}\mathrm{Z}\mathrm{O}(d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i)\le \mathrm{L}\mathrm{Z}\mathrm{O}(\mathrm{h}\mathrm{i}\mathrm{g}{\mathrm{h}}_i)(6)

\mathrm{L}\mathrm{Z}\mathrm{O}(\mathrm{l}\mathrm{o}{\mathrm{w}}_i)\le \mathrm{L}\mathrm{Z}\mathrm{O}(d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i)\le \mathrm{L}\mathrm{Z}\mathrm{O}(\mathrm{h}\mathrm{i}\mathrm{g}{\mathrm{h}}_i)(7)

\mathrm{L}\mathrm{Z}\mathrm{O}\left(d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i\right)\le \mathrm{L}\mathrm{Z}\mathrm{O}\left(\mathrm{l}\mathrm{o}{\mathrm{w}}_i\right)\wedge \mathrm{L}\mathrm{Z}\mathrm{O}(\mathrm{h}\mathrm{i}\mathrm{g}{\mathrm{h}}_i)\le \mathrm{L}\mathrm{Z}\mathrm{O}(d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i)(8)

最后，将满足条件数据对应的设备ID、时间戳信息和加密数据传送到查询节点，即：

\mathrm{r}\mathrm{e}\mathrm{t}=\{\mathrm{I}{\mathrm{D}}_i,d_i,T_i\}

3） 在数据计算模式下，还需要将处理好的数据使用优化Paillier算法进行数据计算，首先对\mathrm{c}\mathrm{m}\mathrm{d}命令进行解析，根据\mathrm{c}\mathrm{m}\mathrm{d}命令生成对应的计算方法，最后将计算数据和计算方法输入存储节点提供的函数内，得到结果，将结果返回给查询节点。

• 查询节点验证阶段

接收存储节点的信息后，查询节点利用优化Paillier算法验证方法验证数据安全性。利用优化Paillier算法解密数据，获取数据的最大值和最小值，最后判断数据密文最值是否与加密数据组内最值一致，如果不一致则表明接收到的数据已经被伪造或篡改，丢弃数据；如果一致，则表明数据一切正常，随后将结果返回。

3.4　隐私安全性分析

本节将从感知数据和范围查询、查询计算过程这两个方面对基于优化Paillier算法的范围查询计算方法的隐私安全性进行分析。

1） 感知数据隐私安全性：如果感知节点s_i需发送感知数据d_i^i，首先要利用优化Paillier算法对d_i^i进行加密，加密密钥仅与查询节点通过密钥管理机制共享。因此，在无密钥的情况下，获取明文数据的复杂度与破解加密算法是等价的，所以可以保证在存储节点和网络下的其他节点无法获取感知数据d_i^i。其次，我们将待上传数据的最值d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i和d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i使用最左0-1编码得到编码集合，再利用HMAC处理最值d_{\mathrm{m}\mathrm{a}\mathrm{x}}^i和d_{\mathrm{m}\mathrm{i}\mathrm{n}}^i的最左0-1编码集合，使得在存储节点中无需数据明文参与下即可进行数值比较，确保感知数据的隐私安全性。

2） 查询计算的隐私安全性：在范围查询过程中，查询节点发送的主要内容为待查询的数据范围，数据范围需要先生成最左0-1编码集合，然后利用HAMC机制对编码集合进行信息摘要处理，因此即使存储节点被绑架，但是依旧无法通过查询命令获取感知数据明文。查询计算在范围查询的基础上增加了数据计算操作添加了计算指令，在计算过程中，存储节点使用优化Paillier加密下的密文进行数据计算，计算结果也是密文数据。因此，在无密钥的情况下破解数据计算结果与破解加密算法相同，可以有效保证查询计算的隐私安全性。

4　 实验评估与分析

4.1　实验环境与程序设计

本文以树莓派为核心处理单元结合温湿度、光敏传感器模组构建感知节点，以内存为8 GB，运行Linux系统的NVIDIA TX2构建存储节点，使用VMware构建的内存为2 GB，硬盘空间为20 GB的Ubuntu虚拟机构建查询节点。使用Python语言设计各个节点的应用程序，存储节点作为服务器，查询节点和感知节点作为客户端，三者通过TCP服务器/客户端模型进行通讯，并以此搭建实验平台对本文方法进行设计与验证。

范围查询计算方法程序由感知节点程序，存储节点程序和查询节点程序三部分构成。

感知节点程序主要功能是利用密钥管理机制请求与查询节点进行组网、数据处理与上传。建立连接过程：连接到存储节点的服务器后发出组网请求，然后等待接收查询节点发出的加密公钥，验证公钥信息无误后组网成功。数据处理与上传过程：首先使用接收到的公钥对感知数据加密，对最值数据进行最左0-1编码以及HMAC运算生成最值比较链，然后将加密数据和数值比较链组成JSON数据帧，最后发送给存储节点。

存储节点程序主要功能是存储感知数据和处理范围查询或数据计算请求。存储感知数据功能：在感知节点连接到存储节点服务器、完成密钥交换后会主动上传数据密文和数据索引，存储节点在接收到数据后需要检查数据库状态，根据数据信息创建数据表，然后将数据存储到数据库即可。处理查询计算数据请求分为范围查询操作和数据计算操作，这部分是本文所关注的重点问题。处理范围查询请求命令时，首先需要将查询请求数据中的时间戳、节点ID、设备类型数据与数据库现有数据进行比较，如果满足查询条件则进行下一步的数值比对，最后利用本文提出的基于最左0-1编码的数值比较方法，如果存储的感知数据满足范围查询条件，则上传数据以及数据的时间信息、节点信息、传感器设备信息。处理计算查询请求与处理范围查询模式类似，首先需要比对查询节点信息，然后存储节点根据计算查询请求的命令对满足同态运算的感知数据进行密文下的运算，最后将运算的结果返回给查询节点。

查询节点程序主要功能是组网、查询请求以及接收和处理返回信息。查询节点在接收到感知节点的组网请求后，需要向感知节点发送出组网信息，信息包括公钥信息和HMAC密钥信息。其中公钥信息由查询节点自行生成，HMAC密钥信息通过相应的规则更改公钥得到。查询节点范围查询功能由用户选择查询属性：时间戳、节点信息、传感器信息等，然后选择查询范围，查询计算功能则需要在范围查询的基础上添加计算规则，最后由系统将信息编码、加密后发送到存储节点。查询节点发送查询计算请求后，存储节点会返回查询结果，查询节点首先需要基于本文提出的可验证性的Paillier算法对查询结果进行完整性验证，然后利用Paillier私钥解密数据得到查询结果。

4.2　实验与分析

为验证本文方法在实际应用中的性能表现，将本文方法与CSRQ方法^[9]和LDRQ方法^[11]在本文设计的实验平台上从感知节点能耗和数据查询计算效率两个方面进行对比实验。

4.2.1　感知节点能耗实验

使用纳普科技PM9816数字功率计来测量感知节点能耗，测试电压量程0.5~600 V，电流量程0.05 mA~40 A。电流做功的多少跟电流的大小、电压的高低、通电时间长短有关。当电路两端电压为U，电路中的电流为I，通电时间为t时，消耗的电能W为：W=UIt。

实验1 以单个周期内获取感知数据维度d为变量，设周期内采集数据个数为20,其他实验参数如表2所示，测试感知数据维度对感知节点能耗的影响，功耗测试实验结果如图3所示。

由图3所示，随着感知数据维度的增加，本文方法与CSRQ、LDRQ方法感知节点的能耗均呈线性增长。因为数据维度d的增加，导致CSRQ方法需构建新的数据比较项和加密约束链，这使得CSRQ方法中感知节点通讯能耗增加；LDRQ方法尽管不需要构建繁琐的加密约束链，但是需要构建冗长的数据比较链并对数据进行AES加密；本文方法数据比较集占上传数据的比例较低，因此感知节点能耗增加比较平缓。随着感知数据维度d的增加，本文方法感知节点能耗相较于CSRQ方法降低33%左右。

实验2 以单个周期内获取传感器数据个数n为变量，设采集数据维度为3，其他实验参数如表2所示，测试周期内获取感知数据量n对感知节点能耗的影响，功耗测试实验结果如图4所示。

由图4所示，随着感知数据量n的增加，三种方法的感知节点能耗均呈线性提高，其中CSRQ方法增加最为迅速。这是因为CSRQ方法需要在感知节点中构建加密约束链和数据比较项，随着数据的增多所需要的加密约束链也就更长，并且需要设计更多的比较项。本文方法无需构建冗长的加密约束链，数据增加只会导致数据加密计算能耗和密文长度增加。在该实验中，本文方法相较于CSRQ和LDRQ方法表现好。

4.2.2　数据查询计算效率对比实验

在数据查询计算效率对比实验中，我们针对数据进行求和运算，根据计算完成时间进行计算效率对比，实验结果如图5所示。

如图5所示，CSRQ方法和LDRQ方法的计算耗时随着数据计算个数的增长呈指数型增加，计算数据个数增加至1 000以后，本文方法在计算效率上明显优于CSRQ和LDRQ方法。这是因为随着计算数据量的增加，存储节点需要通过网络传递给查询节点的数据量也在增加，过程中会产生大量的时间浪费,而本文方法使用存储节点作为数据计算平台的策略相较于CSRQ和LDRQ方法节省了大量的数据传输所消耗的时间，有效地提高了数据计算效率。

5　 结 语

本文以无线传感器网络下隐私数据范围查询为研究背景，根据范围查询下的数据计算问题提出一种基于优化Paillier算法的两层无线传感器网络范围查询计算方法。该方法对Paillier算法进行计算优化和可验证性优化，降低Paillier加密计算步骤使其能够应用于资源受限的感知节点的同时，实现密文下的数据计算。针对现有方法中感知节点能耗问题的不足，提出一种基于最左0-1编码和HMAC方法的数值比较机制，将密文数值大小比较问题转化为两个最左0-1编码HMAC摘要集合是否存在交集的问题。理论分析和实验结果表明，该方法的查询计算具备高效性，感知节点具备低功耗性。

参考文献

[1] HEMALATHA T， RAMESH M V， RANGAN V P. Effective and accelerated forewarning of landslides using wireless sensor networks and machine learning［J］. IEEE Sensors Journal， 2019， 19（21）： 9964-9975. DOI： 10.1109/JSEN.2019.2928358 .

[2] LLORET J， SENDRA S， GARCIA L， et al. A wireless sensor network deployment for soil moisture monitoring in precision agriculture［J］. Sensors （Basel， Switzerland）， 2021， 21（21）： 7243. DOI： 10.3390/s21217243 .

[3] TSOU Y T， LU C S， KUO S Y. SER： Secure and efficient retrieval for anonymous range query in wireless sensor networks［J］. Computer Communications， 2017， 108： 1-16. DOI： 10.1016/j.comcom.2017.04.007 .

[4] WANG L， ZHAO M， CHEN J， et al. A novel privacy- and integrity-preserving approach for multidimensional data range queries in two-tiered wireless sensor networks［J］. International Journal of Distributed Sensor Networks， 2019， 15（6）： 155014771985589. DOI： 10.1177/1550147719855893 .

[5] WAN S， ZHAO Y， WANG T， et al. Multi-dimensional data indexing and range query processing via Voronoi diagram for Internet of things［J］. Future Generation Computer Systems， 2018， 91：382-391. DOI: 10.1016/j.future.2018.08.007 .

[6] WEN Y P， LIU J X， DOU W C， et al. Scheduling workflows with privacy protection constraints for big data applications on cloud［J］. Future Generations Computer Systems （FGCS）， 2020： 1084-1091. DOI： 10.1016/j.future.2018.03.028 .

[7] 钱涵佳， 王宜怀， 彭涛， 等. 轻量级窄带物联网应用系统中高效可验证加密方案［J］. 计算机研究与发展， 2019， 56（5）： 1112-1122. DOI： 10.7544/issn1000-1239.2019.20180217 .

[8] QIAN H J， WANG Y H， PENG T， et al. Efficient and verifiable encryption scheme in lightweight narrowband Internet of Things applications［J］. Journal of Computer Research and Development， 2019， 56（5）： 1112-1122. DOI： 10.7544/issn1000-1239.2019.20180217（Ch ）.

[9] CHEN F， LIU A X. Privacy- and integrity-preserving range queries in sensor networks［J］. IEEE/ACM Transactions on Networking， 2012， 20（6）： 1774-1787. DOI： 10.1109/TNET.2012.2188540 .

[10] DAI H， YE Q Q， YANG G， et al. CSRQ： Communication-efficient secure range queries in two-tiered sensor networks［J］. Sensors （Basel， Switzerland）， 2016， 16（2）： 259. DOI： 10.3390/s16020259 .

[11] 胡乔木， 邓昀. 基于压缩HMAC算法的传感器网络范围查询方法［J］. 计算机工程， 2021， 47（12）： 200-208. DOI： 10.19678/j.issn.1000-3428.0062221 .

[12] HU Q M， DENG Y. Range query method based on compressed HMAC algorithm for sensor networks［J］. Computer Engineering， 2021， 47（12）： 200-208. DOI： 10.19678/j.issn.1000-3428.0062221（Ch ）.

[13] DENG Y， CHEN J， WANG Y， et al. A security multi-dimensional range query protocol based on left 0-1 encoding in two-tiered wireless sensor networks［J］. Journal of Circuits， Systems and Computers， 2022， 31（9）： 250157：1-2250157：32 （2022）. DOI: 10.1142/s0218126622501572 .

[14] PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes［M］//Advances in Cryptology — EUROCRYPT’99. Berlin： Springer， 2007： 223-238. DOI： 10.1007/3-540-48910-x_16 .

[15] 姜正涛， 刘建伟， 王育民. Paillier-Pointcheval公钥概率加密体制的改进［J］. 计算机工程， 2008， 34（3）： 38-39. DOI： 10.3969/j.issn.1000-3428.2008.03.014 .

[16] JIANG Z T， LIU J W， WANG Y M. Improvement on Paillier-Pointcheval probabilistic public-key encryption scheme［J］. Computer Engineering， 2008， 34（3）： 38-39. DOI： 10.3969/j.issn.1000-3428.2008.03.014 （Ch ）.

[17] 张燕平， 凌捷. 一种改进的水平分布式环境下基于同态加密的隐私保护算法［J］. 计算机科学， 2017， 44（8）： 157-161. DOI： 10.11896/j.issn.1002-137X.2017.08.028 .

[18] ZHANG Y P， LING J. Improved algorithm for privacy-preserving association rules mining on horizontally distributed databases［J］. Computer Science， 2017， 44（8）： 157-161. DOI： 10.11896/j.issn.1002-137X.2017.08.028（Ch ）.

[19] LIN H Y， TZENG W G. An efficient solution to the millionaires’ problem based on homomorphic encryption［M］//Applied Cryptography and Network Security. Berlin： Springer， 2005： 456-466. DOI： 10.1007/11496137_31 .

[20] 刘梦君， 刘树波， 丁永刚. 基于0-1编码的参与式感知隐私保护的数据价值匹配方案［J］. 计算机科学， 2018， 45（3）： 133-139. DOI： 10.11896/j.issn.1002-137X.2018.03.021 .

[21] LIU M J， LIU S B， DING Y G. 0-1 code based privacy-preserving data value matching in participatory sensing［J］. Computer Science， 2018， 45（3）： 133-139. DOI： 10.11896/j.issn.1002-137X.2018.03.021（Ch ）.

基金资助

国家自然科学基金(61902189)

江苏省高等学校基础科学（自然科学）研究项目(22KJA520004)

湖南省重点研发科技计划项目(2021NK2020)