抗窃听攻击的传感器网络空间范围聚集查询处理算法*

胡震海，王立松

(南京航空航天大学计算机科学与技术学院，江苏 南京 210016)

1 引言

无线传感器网络作为物联网的重要组成部分，被广泛应用于医疗卫生、智能家居、国防军事等领域。无线传感器一般具有廉价、体积小、质量小、能量有限、无线通信、较弱的计算能力和简易的操作系统等特点[1]。无线传感器能够被灵活地布置，通过无线传输方式交换数据形成一个能够存储、计算、传输部署区域感知数据的多跳自组织网络。无线传感器的便捷部署，节省了人力物力，具有广泛的应用前景。

无线传感器网络中，用户经常提交空间范围聚集查询以获取网络中某区域的统计信息。相比较传统的数据收集方式，数据聚集的收集方式节省了能量开销。

一方面传感器节点大都采用电池供电，常被部署于环境恶劣和无人值守的地方，部署后更换难度比较大。鉴于传感器节点的更换难度以及有限能量，我们在采用传感器节点存储与传输感知数据的同时，应尽量延长传感器节点的生命周期。另一方面由于传感器容易被监听，故在实际应用部署中可能会面临隐私数据泄露和篡改问题。例如，在军事领域中，传感器网络被部署获取侦查区域数据，监测数据被监听或篡改会带来意想不到的后果；智能家居中，传感器被部署于居民住宅内，用以统计区域内居民水煤电的用量情况，借以帮助市政单位做出决策。所以，应用无线传感器获取数据时，能量高效且考虑隐私的空间范围聚集查询成为广泛应用中关键的一环。

现有的无线传感器网络聚集查询隐私保护方法大都基于预先构造好的拓扑结构和全网络的所有节点来处理，且常采用加密的形式对感知数据进行保护。拓扑结构的维护以及加密的方式都增加了传感器节点的能耗。

针对以上问题，本文提出一种抗窃听攻击的传感器网络空间范围聚集查询处理PCPDA(Part of the area based on Cluster Privacy-preserving Data Aggregation)算法，对无线传感器网络中部分区域采用空间范围聚集查询方式收集感知数据。基站将查询消息发送至指定区域，指定区域内采用边查询边聚集的方式，动态地按照既定路线广播查询消息，收集感知数据，最后将聚集消息返回给基站。这种基于路线的收集方式，不依赖于预先构造好的拓扑结构，且在未采用任何加密措施的情况下，保护了传感器节点原始数据的隐私性。

2 预备知识

传感器网络中的隐私保护既需要通过隐私保护策略来防止数据泄露和篡改，同时也需要通过数据管理技术来完成数据聚集、数据查询，并且需要进行性能优化以减少能量损耗。传感器网络中的隐私保护策略主要包括数据扰动技术、数据加密技术和数据匿名化技术，数据管理技术主要从数据存储、路由建立、查询策略等方面进行性能优化[2]。故我们需要在保证传感器网络的隐私数据不被泄露的情况下完成数据聚集。

传感器网络在完成数据聚集情况下的隐私保护加密策略主要包括端到端加密策略和逐跳加密策略。

(1)逐跳加密：He等人[3]提出2种协议CPDA(Cluster-based Private Data Aggregation)和SMART(Slice-Mix-AggRegaTe)，CPDA中无线传感器网络组织成簇结构，簇内节点通过在感知数据中添加私有随机数来保证感知数据的隐私性，簇头节点利用多项式的代数性质来计算所需的聚合值。SMART中采用数据分片技术，将分片后j-1份数据片通过逐跳加密机制传输给相邻的j-1个节点，节点对所收到的分片数据进行聚合，并根据所构造的TAG树，将聚合结果传输给下一个节点，直至Sink节点。

SMART采用文献[4]中提出的随机密钥分配策略，该密钥策略主要由3部分组成：①密钥预分配：密钥池中有K个密钥，传感器网络中的每个传感器节点从池中随机选取k个密钥。②发现共享密钥：每个节点找出它们邻居中拥有相同密钥的节点，如果2个节点拥有相同密钥，则建立安全链接。③建立路径密钥：没有相同密钥的邻居节点，可以通过多跳方式建立安全链接。

基于SMART的隐私保护加密过程分为3个步骤：分片、混合和聚集。①分片：节点随机选取自身相邻或h跳范围内的节点，目标节点将自身数据分割成j份，自身保留1份数据，将其余j-1份数据通过安全通道随机分发到h跳范围内的节点。②混合：节点接收加密的数据分片后，使用发送节点的公钥解密，接收节点等待一段时间，确保其余的分片数据到达，然后将接收到的分片数据相加。③聚集：节点数据混合后沿着拓扑树将数据聚集到Sink节点。

在SMART的基础上,文献[5]提出了一种改进的传感器网络隐私保护协议PECDA(Privacy-preserving and Energy efficient Continuous Data Aggregation)。PECDA不需要对查询区域内所有节点进行分片，对于所构造的拓扑树，在数据分片阶段只需对叶子节点进行分片。由于叶子节点只包括自身的感知数据，为避免其感知数据泄露给父亲节点，数据分片阶段只需对叶子节点进行分片，叶子节点将分片后的j-1份数据通过安全链接传输给邻居节点。

文献[6]中提出的DADPP(Data Aggregation Different Privacy-levels dim Protection)，根据不同的隐私级别，将同一簇内的所有节点划分为多个组，各组内的节点有相同的隐私级别。 每个组分别对原始数据进行预处理，然后发给簇头节点，簇头节点聚集所有组预处理后数据，最后汇聚至基站。文献[7]提出的iPDA(integrity-protecting Private Data Aggregation)利用SMART中切分重组的思想来保护数据的隐私，并通过构造不相交的聚合路径/树来收集感知数据，利用冗余数据进行完整性验证。文献[8]提出的ESPART(Energy-Saving Private-preserving AggRegaTion)对SMART进行了改进，一方面基于所构造的树结构本身降低通信量从而节省能量，另一方面随机分配节点时间片，降低信息传输过程中的碰撞率，同时限制串通数据范围，降低了数据丢失对聚集精准度的影响。文献[9]在文献[3]的基础上提出一种适应性较强的数据融合方法LSDA(Lightweight Secure Data Aggregation)，该方法采用分片重组技术，根据网络通信量调整簇内节点分片大小。文献[10]提出一种低能耗隐私数据安全融合方法LCSDA(Low energy-Consuming Secure Data Aggregation)，该方法根据最短路径原则为簇内节点选取邻居节点，并借助prim算法建立簇内数据的融合路径。

(2)端到端加密：文献[11]提出一种简单的求和同态加密策略，采用该策略实现端到端加密机制的SUM聚集。该策略包含加密函数Enc()和解密函数Dec()，其中：Enc(m,k,M)=m+kmodM，Dec(c,k,M)=c-kmodM。节点Si与Sink节点共享密钥ki，k是ki由计算得到的，M是系统参数，用m1、m2表示传感器节点S1和S2的原始感知数据。文献[12]提出的SP(Secret Perturbation)模式系列与方案AHE(Add Homomorphism)思路类似，其中BSP(Basic Secret Perturbation-based)模式通过添加辅助数据项，不仅实现了AHE功能，还能够应对重放攻击；FSP(Fully-reporting SP-based)模式中，Sink节点减去所有节点的秘密扰动数据和可得到正确的聚集结果；O-ASP(Optimal Adaptive SP-based)模式和D-ASP(Distributed Adaptive SP-based)通过对FSP的优化减少了数据传输的通信量。文献[13]提出SIES(Secure In-network processing of Exact Sum)方案，通过加同态加密技术和数据共享[14]等技术实现密文数据的聚集操作，SIES通过SECOA(SECure Outsourced Aggregation)[15]来验证聚集结果的完整性。压缩数据收集是基于压缩感知理论的一项重要突破，由于其开销低的特性，已经在传感器网络中被用作数据收集的方法。在存在开放无线介质情况下，压缩数据收集易受到各种攻击的影响，文献[16]提出一种高效的具有隐私保护能力的压缩数据收集方案，该方案在压缩数据收集过程中，采用同态加密的方式避免流量跟踪和保证消息的机密性。无线传感器网络常通过端到端或逐跳的方式验证数据，检测虚假数据的注入。前者，检测工作发生在消息聚集后，且只能在Sink节点进行。端到端的检测方式效率不高，容易致使大量合法数据丢失。对此，文献[17]提出一种基于端到端同态加密形式的隐私保护策略，并且通过逐跳的方式进行数据安全检测，以此降低对Sink节点的依赖。

现有基于数据聚集情况下的隐私保护策略，采用数据加密技术，并且都是基于全网络节点下的静态查询。针对以上问题，本文提出一种抗窃听攻击的传感器网络空间范围聚集查询处理算法，该算法不依赖于某种加密策略，采用边查询边聚集的方法，动态地收集感知数据，能够在完成数据聚集情况下保证节点原始数据的隐私性。

3 抗数据窃听攻击的动态传感器网络空间范围聚集查询PCPDA

PCPDA利用窗体查询收集部分区域节点的感知数据并保证节点原始数据的隐私性。查询窗体内，采用基于分簇的动态查询方法，窗体内以边查询边聚集的方式进行。

3.1 算法思想

为了避免现有算法的一些问题，本文提出一种抗窃听攻击的传感器网络空间范围聚集查询处理算法，该算法可分为3个阶段：

(1)查询发起节点(Sink节点)利用位置路由协议[18]将查询消息发送至查询区域。

(2)查询区域内采用分簇的方法，簇内每个节点获得的感知数据皆为其遍历过的所有节点的感知数据的和，所以攻击者无法获得节点的原始感知数据。

(3)感知消息聚集后，利用位置路由协议发送回Sink节点，当Sink节点接收到聚集数据后，得到的便是聚集区域的感知数据之和。

为了不失一般性，如图1所示基于一般的网络分布情况，采用PCPDA收集查询区域的感知数据。以Sink节点为查询起始节点，用Ci(i=0,1,2…)表示簇头节点，用a,b,c…表示数据节点，其收集过程如下所示：

(1)Sink节点发出查询消息和随机数num，利用位置路由协议将查询消息和num发送至查询区域的一个数据节点a。

(2)a收到查询消息和num后，根据其维护的邻居信息选取第1个网格内的簇头节点C0，用于收集该簇内数据节点的感知数据。

定义1NA(m)为节点m的后继子区域(借助网格描述)，NC(m)为NA(m)后继子区域的簇头节点，NA(m)中除了NC(m)其余为数据节点。后继子区域需满足如下约束：后继子区域的所有节点均是节点m的邻居节点，子区域内所有节点能够互相通信。

(3)数据节点a将查询消息发送至C0，由于无线广播特性，网格内所有节点均能收到查询消息。网格中所有节点都收到查询信息后，按照路线行进方向排序数据节点，数据节点的聚集方式采用依次叠加的方法。如图1所示第1个网格内，节点a将感知数据与num相加后的结果Da发送给节点b。Da到达节点b后，与感知数据Db相加，然后将相加后的结果发送给节点c，以此类推，直至将子区域内所有数据节点的聚集结果发送给簇头节点。

(4)簇头节点C0收集完子区域的感知数据后，将会计算下1个簇头节点C1和子区域，将查询消息发送至子区域NA(C0),将子区域NA(a)的聚集结果发送至NA(C0)中的第1个节点m(按照路线行进方向排序后)。节点m与NA(C0)查询结果融合后，与步骤(3)类似，簇头节点C1将收集NA(C0)区域内所有数据节点的感知数据。C1收集完NA(C0)区域内所有节点感知数据后，将会继续计算下1个簇头节点和子区域。

(5)按照步骤(3)继续收集区域未遍历节点的感知数据，直至遍历完查询区域内所有节点，获得整个查询区域的查询结果。

(6)查询区域内的最后1个簇头节点Cn利用位置路由协议将查询结果发送回Sink节点。

Figure 1 Execution procedure of the PCPDA algorithm图1 PCPDA算法执行示意图

3.2 算法设计

窗体查询区域内的传感器网络表示为SN={C1,C2,…,Cn}，假设节点的通信半径用R来表示。

(1)基于网格(子区域)查询结果收集策略。

为了能够遍历整个查询区域，采用划分网格(子区域)的思想，将整个区域划分成多个网格(子区域)，依靠网格的依次递进，使得查询消息发送至整个查询区域中的所有节点，借此来收集部分区域的感知数据。由于无线通信的广播特性，网格中的所有节点均能收到消息。采用按序聚集感知数据策略，将当前网格中所有的节点按照当前前进方向矢量排序。

(2)网格大小。

当查询消息传至当前网格的最后1个节点，需确定下1个网格时，约定下1个网格的所有节点需满足在当前节点的通信范围内。由于无线通信的广播特性，网格中节点接收到查询消息后，按照排序后的顺序依次聚集节点的感知数据。

(3)簇头的选取。

由算法执行过程可知，簇头节点Ci会将已遍历过节点的聚集结果和查询消息发送给Ci+1，因此簇头的选取是算法执行过程的关键一步。由算法执行的约束条件可知，NA(Ci)中所有数据节点需在Ci通信范围内，所以NA(Ci)的数据节点均在Ci维护的邻居信息中，将NA(Ci)中的数据节点根据路线行进方向进行排序，选取排序后的末尾节点作为Ci+1。

(4)如何处理空洞。

如图2所示，查询节点收集完网格EFGH中数据节点的感知数据后，需将查询消息和部分查询结果发送至下1个查询节点。由于网格EFGH下方的区域GHKI不存在节点的邻居节点，区域GHKI成为空洞区域，导致查询处理过程中断。为了避免该问题，利用位置路由协议绕过该空洞区域，即节点e以矩形区域IKLM的中心为目的位置(其中KM之间的距离为R)，利用位置路由协议将查询消息和部分查询结果发送至该矩形区域中的1个节点。图2中，节点e通过f、g到达区域IMLK中的节点，然后从该节点开始继续后续的查询处理过程。若矩形区域IMLK中不存在节点或位置路由协议无法将查询消息和部分查询结果发送至区域IMLK中的节点，则采用上述方法类似的思想，以IMLK下方的区域LMNQ的中心为目的位置(其中LN之间的距离为R)，利用位置路由协议将消息发送至该区域中的1个节点。

Figure 2 Bypassing the void region图2 绕过路由空洞

3.3 能耗分析

本节从理论上对PCPDA、SMART和PECDA进行能耗分析。为了表述方便，对下文要用到的符号及其含义进行说明，如表1所示。

Table 1 Meaning table of variables表1 基本符号及其含义

采用PCPDA收集查询区域SRS中的所有节点的感知数据。整个查询过程的能耗可分为2个部分：(1)查询消息的发送，即子区域SRi中的簇头节点SRCi将查询消息广播至子区域SRi+1内所有节点(其中i为1～n-1)，用Equery表示；(2)感知数据聚集阶段的能耗，用Edata表示。

SMART与PECDA的能耗主要包括数据分片传输安全通道的建立、查询消息的分发和感知数据聚集3阶段。这里主要针对SMART和PECDA中查询消息发送与数据的聚集过程与PCPDA进行对比分析。假设SMART与PECDA中叶子节点所占比例为p，同PCPDA用Equery表示查询阶段消耗的能量，Edata表示数据聚集阶段消耗的能量。

为了便于分析，用E(PCPDA)、E(SMART)和E(PECDA)表示3种算法总的能耗，Equery(PCPDA)、Equery(SMART)和Equery(PECDA)分别表示3种算法查询阶段的能耗，Edata(PCPDA)、Edata(SMART)和Edata(PECDA)分别表示3种算法聚集阶段的能耗。

定理1E(PCPDA)

证明

PCPDA中：

(1)

Dist(SRCi-1,n)≤R,∀n∈Num(SRi),1≤i≤n

(2)

Dist(n,SRCi)≤R,∀n∈Num(SRi),1≤i≤n

(3)

式(1)～式(3)为子区域的约束条件。

E(PCPDA)=Equery+Edata

(4)

其中，

Equery=Sq*E*n

(5)

(6)

SMART中：

E(SMART)=Equery+Edata

(7)

其中，

Equery=Sq*E*N

(8)

(9)

PECDA中：

E(PECDA)=Equery+Edata

(10)

其中，

Equery=Sq*E*N

(11)

(12)

由式(5)、式(8)、式(11)可推出：

Equery(PCPDA)

(13)

由式(6)、式(9)、式(12)可推出：

Edata(PCPDA)

(14)

由式(13)、式(14)可得结论。

□

3.4 隐私分析

文献[4]给出了密钥分配的2个重要性能：任意2个邻居之间至少有1个相同密钥的概率为Pconnect,第3方节点拥有相同密钥的概率为Poverhear：

(15)

Poverhear=k/K

(16)

4 仿真分析

本节通过仿真对算法进行分析，在文献[19]的仿真器上实现了PCPDA与现有算法里的SMART和PECDA，其中硬件环境为2.6 GHz CPU，8 GB内存，软件环境为Ubuntu操作系统、eclipse开发环境。传感器节点分别以均匀分布和非均匀分布的方式部署在矩形监视区域中。

仿真参数选择如下：根据文献[20]，无线通信发送和接收1 byte的能量消耗公式为：Et=α+γ*dm，Er=β,其中,α和β为捕获通信电子消耗的能量，γ为功率放大器消耗的能量，m为路径损耗指数，d为传输距离。采用文献[21]中的参数：γ=10 pJ/bit/m2，α=45 nJ/bit，β=135 nJ/bit，m=2。其他参数如表2所示。

Table 2 Simulation parameters表2 仿真参数

4.1 时间延时

时间延时是性能评估的一个重要指标。基于KIPDA(K-Indistinguishable Privacy-preserving Data Aggregation)[22]，比较了现有算法和PCPDA的时钟周期数。由图3可知，现有算法的时间延时高于PCPDA的。因为SMART中需要对查询区域内所有节点进行分片、混合和聚集，PECDA仅需对叶子节点进行分片、混合和聚集，相比SMART，PECDA一定程度上降低了时间开销。PCPDA查询过程中由于无需对节点感知数据分片后再聚集，缩短了查询过程中的时间延时，提升了效率。

Figure 3 Influence of the number of network nodes on the time delay图3 网络节点数对时间延时的影响

4.2 通信开销和能量消耗

Figure 4 Influence of the number of network nodes on communication overhead图4 网络节点数对通信开销的影响

图5和图6分别展示了网络节点密度、查询区域大小条件下能量的损耗。

Figure 5 Influence of the number of network nodes on energy loss图5 网络节点数对能量损耗的影响

Figure 6 Influence of query region size on energy loss图6 查询区域大小对能量损耗的影响

可见，算法PCPDA的能耗小于SMART和PECDA的。主要差异来源于SMART和PECDA中需要建立安全通道，对节点感知数据进行分片分发。随着查询区域变大，查询区域内的节点数变大，PCPDA、SMART、PECDA因分发查询消息和聚集感知数据，因此3种算法的总能耗随着查询区域的增大而变大。图7和图8分别展示了感知数据大小、查询消息大小对3种算法能耗的影响。由式(13)、式(14)可知，算法PCPDA在查询阶段、聚集阶段的能耗皆小于SMART和PECDA的。由图7和图8可知，3种算法的能耗随着查询消息的增大而增大，随着感知数据的增大而增大。

Figure 7 Influence of the sensing data size on energy loss图7 感知数据大小对能耗的影响

Figure 8 Influence of the query message size on energy loss图8 查询消息大小对能量损耗的影响

另外，由于SMART和PECDA依赖预先构造好的拓扑树，拓扑结构的变化对其能耗的影响比较大。由图9可知，在不同的拓扑结构下，SMART和PECDA在能耗方面有着不同的表现，而PCPDA在不同拓扑下的能耗则相对稳定。

Figure 9 Influence of different network topologies on energy loss图9 不同网络拓扑对能量损耗的影响

5 结束语

现有传感器网络聚集查询隐私保护算法通过数据加密来保护节点感知数据的隐私性，且全网络中所有节点参与查询处理。数据的加解密操作增大了节点计算能耗，且在很多情况下，用户只对传感器网络中部分区域的聚集结果感兴趣，此时如果还采用全网络隐私保护聚集查询方法，必然大大增加节点的资源开销。针对现有算法的一些问题，本文提出一种抗窃听攻击的传感器网络空间范围聚集查询处理算法，该算法在未采用任何数据加密情况下，不仅完成了节点数据的聚集查询，而且查询过程中保证了感知数据的隐私性。由于聚集过程中无任何加解密操作，节省了节点的能量，加快了聚集效率。仿真结果和理论分析表明，PCPDA在能量损耗和隐私性保护方面均优于现有的一些算法。