基于分片的轻量级数据融合隐私保护算法

王 军，徐彦惠+，李 莉

(1.沈阳化工大学 计算机科学与技术学院，辽宁 沈阳 110142； 2.沈阳化工大学 辽宁省化工过程工业智能化技术重点实验室，辽宁 沈阳 110142)

0 引 言

无线传感器网络(wireless networks，WSN)是由大量具有数据采集、数据处理、数据存储和无线通信等功能的资源受限的微型传感器节点以自组织和多跳路由方式构成的信息传输网络[1]。

数据融合技术是WSN的关键技术之一，该技术的意义在于其直接决定了网络的生存周期[2]。通过数据融合，去除冗余信息，进而减小传输数据量，实现能量的节约，增加网络生命周期，达到数据高效收集的目的[3]。

W.B.He，X.Liu等提出了CPDA(lightweight-cluster-based private data aggregation)算法和SMART(slice-mix-aggregate)算法[4]。CPDA计算开销很大，而且SMART也很昂贵，通信开销太大，并且对数据丢失很敏感[5]。

针对上述算法的不足本文提出了一种基于分片的轻量级数据融合隐私保护算法L-CPDA(a lightweight-cluster-based private data aggregation)。在分片前通过数据扰动技术提高数据安全性，根据簇内节点数目的不同对数据进行动态分片，同时对网络中的孤立节点进行数据扰动。这样能够降低计算与通信消耗。

1 相关工作

He等分别扩展了PDA算法，提出了两种能够兼顾隐私保护和完整性验证的数据融合方案iPDA和iCPDA[6]，但是在能验证完整性的同时，计算复杂度大大增加。苘大鹏等提出了E-CPDA(energy-efficient cluster-based privacy data aggregation)[7]，由簇头选取协作节点，协作节点起到辅助完成数据融合的作用,在计算量、通信消耗方面都优于CPDA，E-CPDA是以4个节点成簇举例，但当簇内节点数量大于4个时，没有给出一般性的计算方法。宋蕾等针对节点能耗和精度的问题提出一种基于博弈论的数据融合算法DFABGT(data fusion algorithm based on game theory)[8]。簇内节点以收益和能耗为效益函数的输入参数进行博弈。本算法能有效提高精确度，降低节点能耗，但该算法的数据融合是基于贝叶斯理论[9]的，计算相对复杂，计算量较大。

综上所述，L-CPDA算法是针对现有算法普遍存在计算量大和通信量大的问题提出的一种轻量级数据融合隐私保护算法，采用动态分片的方式，根据簇内节点的数量对节点进行动态分片，簇内只有成员节点进行数据分片操作，簇头节点只需接收成员节点发送的混合分片结果，不进行分片操作，同时，L-CPDA为了算法的安全性，利用随机数对节点的原始数据进行扰动提高数据的隐私性。

2 CPDA算法描述

CPDA算法是由He等提出的经典保护数据隐私的机制。实现CPDA方案需要进行3个步骤：簇的形成、簇内串通、簇头融合。CPDA算法运用噪声干扰来实现对数据的保护。在簇内融合时，CPDA算法将节点自身采集到的数据与自身产生的随机数和节点之间的共享种子进行噪声运算，得到节点的扰动数据，再将得到的扰动数据与簇内其它节点计算所得的扰动数据进行串通交换。簇内各节点将扰动数据相加得到一个中间值，各个节点将该值发送至簇头，最后由簇头节点利用多项式的性质计算出最终的融合结果。

CPDA算法虽然能在一定程度上保护采集数的隐私性，同时也能基本保证数据的精确性，但是CPDA算法仍然有一定的缺陷，CPDA算法在通信的过程中，簇内每个节点最少要进行二次幂多项式运算，假设簇的规模是m，簇中每个节点都需要进行m-1次二项式运算，每个簇内节点要进行m-1次解密操作和m-1次加密操作，并最终需要求解m阶的逆矩阵得到融合结果，m值越大，计算就越复杂。簇内任意两个节点间都需要进行数据交换，因此通信开销也会增大。所以大规模的网络不适合采用CPDA算法，本文针对CPDA算法的缺陷，以保护数据隐私为前提，提出了L-CPDA算法，新提出算法在计算量和数据通信量上都比CPDA算法要更有优势，在隐私保护度和计算量上得到平衡。

3 网络模型

本文用连通图G(V，E) 表示无线传感器网络，其中v(v∈V) 表示网络中的传感器节点，e(e∈E) 表示无线传感器网络中的无线链路，将无线传感器网络中的节点个数表示为N=|V|。

4 L-CPDA算法描述

4.1 加密方法

无线传感器网络的通信链路通常是不安全的，为防止传输的数据被窃听，保护数据的隐私，对数据进行加密是十分必要的，加密是保护数据的重要手段之一，L-CPDA与CPDA一样，采用随机密钥分配机制[10]。在预分配阶段，首先无线传感器网络生成有含K个密钥的秘钥池，节点从秘钥池中随机选取k个密钥，若存在两个节点含有相同的密钥，记为keys，那么这两个节点之间就建立起了一条安全链路，密钥分配结束后，任意两个WSN节点能够共享同一个密钥的概率为

Pconncet=1-((K-k!)2)/((K-2k)!K!)

(1)

如果两个节点间没有共享密钥，则可以采取多跳的方式建立一条安全链路来实现节点间加密解密的过程。偷听者同样也可以从密钥池中随机选取k个密钥，如果这k个密钥中含有keys，偷听者就可以对节点监听，假设加密信息被窃听的概率为Poverhear，因此Poverhear=k/K， 假设密钥池中有K=10 000个密钥，每个节点选取200个密钥，任意一对节点拥有相同密钥的概率为Pconnect=98.3%，那么没有相同密钥的概率为1.5%，如果一个节点对没有相同的密钥，则可以使用以上文所述的路径密钥建立方式来形成节点间共享密钥。如果两个节点选择了一个共享密钥，那么其它的节点也拥有这个密钥的可能性很低，通常是一个很小的数，即为Poverhear=0.2%。

4.2 算法步骤介绍

L-CPDA算法分为5个步骤，分别是：簇的形成、簇内节点分片、簇内节点串通、簇内节点混合、簇间数据融合，为了表述方便，所用到的符号说明见表1。

表1 符号说明

4.2.1 L-CPDA成簇阶段

L-CPDA采取和CPDA一样的成簇方式，簇的形成过程如图1所示。在图1(a)中，网络中的传感器节点布置好之后，查询服务器向邻居节点发送HELLOW消息，接受到HELLOW消息的节点以pc的概率决定自己是否成为簇头，此处pc是一个预设的数，如果节点成为簇头，它将像查询服务器一样，继续向其它邻居节点发送HELLOW消息，否则，在等待特定的时间后，将会从邻居节点获得HELLOW消息，选择加入一个簇，如图1(b)所示。存在这样的情况：如果节点分布密集，其它节点同时收到不同簇头节点发送的HELLOW消息，那么它将通过发送JOIN消息随机选择其中一个作为簇头。如图1(c)所示，节点6同时收到节点3和节点8的消息，从中随机选择一个簇头加入。以此类推，重复这个过程，经过一段时间就形成了若干个簇群，这些簇最终就形成了一棵融合树。CPDA中用mc表示一个最小的簇(mc=3)。对于不满足条件，无法成簇的节点，在图1(d)中节点12所在的簇规模m

图1 簇的形成

4.2.2 簇内节点分片

在簇的形成过程中，利用一个非在线的装置，使每个节点产生一个随机数ai，这个随机数只有节点本身与查询服务器知道，对其它节点是透明的，利用随机数对节点采集到的原始数据进行数据扰动，可提高数据的隐私性。

将簇建立好之后，每个簇内包含一个簇头节点和若干个成员节点，当簇的规模m满足2n

(2)

将加密的分片数据记为Enc(ki,j，fi,j)， 对于前文提到的簇的大小m<3，被划分到节点集W中的节点，也只需进行数据扰动操作，不进行数据分片操作。在图2中以节点0和节点3为簇头的簇的规模满足21

图2显示根据簇的规模不同，簇内节点分片的情况。

图2 簇内节点分片

4.2.3 簇内节点串通

簇内节点串通分3个步骤：首先，簇内的簇头和每个成员需要等待一段时间，保证接收到所有的分片。之后，簇内成员节点或簇头利用和发送分片数据的节点之间的共享密钥将收到的数据解密，例如节点i解密来自节点j的分片数据可以表示为Dec(ki,j，fi,j)。 簇内的节点将自己所留的一片分片数据和解密后的所有分片数据求和，由于簇头节点未进行分片，只需将自身的数据和解密后的分片数据求和。最终簇内成员节点和簇头都得到了一个新的数据混杂结果，用di表示，由于节点集W中的节点没有足够的节点，只能进行数据扰动运算而不进行分片操作，这样会减少通信开销和数据的传输量，同时节点也具有一定的隐私保护能力。簇内节点串通情况如图3所示。

图3 簇内节点串通

4.2.4 簇内数据混合

在数据混合阶段，为了确保所有的混合信息都能被收到，节点i在收到其它节点发送的混合分片数据以后，会等待特定的时间，确保节点i能接收到所有的分片数据，簇内的各个成员节点将自己计算的混合数据融合结果di发送至簇头，簇内成员节点将数据上传完毕之后，簇头节点将收到的混合数据与自身所计算的混合数据进行相加数据融合，得到这个簇的最终混合数据Ri。

图4描述了簇内混合阶段示例情况，节点0的混合结果为R0=d0+d1+d2节点3的混合结果为R3=d6+d4+d5+d3， 节点8的混合结果为R8=d7+d9+d10+d11， 节点12的混合结果即数据扰动的结果R12=d12。

图4 簇内数据混合

4.2.5 簇间数据融合

在这个阶段，所有节点都推算出了混合结果，融合树的建立参照TAG算法进行构建[11]，采用TAG算法对每个簇头建立融合树，簇头将混合数据Ri沿着融合树的方向逐层向上传递，一层层向上融合，最后，QS节点将在得到的融合中去除掉每个节点产生的随机数信息，也就是最终真正的融合结果。如图4所示，节点3、节点8和节点12将混合结果R3、R8、R12发送给查询服务器(节点0)，然后节点0计算出融合值R3+R8+R12， 最后节点0通过将节点的随机数去除可以算出最终融合的真实结果为

(3)

簇间数据融合过程如图5所示。

图5 簇间数据融合

5 性能分析

本文主要从计算量、隐私保护性和数据通信量这3个方面对L-CPDA进行分析，并和CPDA进行比较。

5.1 计算量分析

假设一个簇中含有ABCD这4个节点，用DA表示节点进行了一次算数运算(加、减、乘、除)，用DB表示节点进行了一次加密运算，用DC表示节点进行了一次解密运算。以节点A为例，在CPDA算法中，节点进行簇内融合时需要执行以下任务：节点在采集到原始数据后，节点ABCD分别用自身产生的随机数和公开的种子值进行数据扰动，计算方法如下

比如，教师可以组织学生参与校内组织的“××演讲大赛”，结合学生的独特优势，让学生相互合作，不断沟通交流，互相讨论稿件的创作以及应该用什么样的语态来进行演讲，从而让学生在此过程中了解团队合作的重要性，并且明确团队合作中应该进行适当的分工，在一定程度上还能够提高学生的人际交往能力。正所谓“世界上没有相同的两片树叶”，每个学生有其独特的观点，这就需要学生学会如何与他人沟通，吸收他人的意见。教师组织的这一个活动，能够有效提高学生的沟通能力、人际交往能力，并且培养学生的合作意识。最重要的是能够促使学生在学校就明确团结的重要性，为学生将来就业奠定基础。

QCPDA-midnode=39DA+3DB+3DC

(4)

对于簇头节点，在进行簇内其它节点相同的操作之外，还要将融合运算考虑进去(实际上是3个加法运算)，所以簇头的计算量表示为

QCPDA-cnod=42DA+3DB+3DC

(5)

在L-CPDA算法中，假设采集到的数据是20，产生的随机数是4，那么经过数据扰动后得到的综合数据是20+4=24，进行了一次算数运算，通过计算：24/4=6,24/6=4,24-6-4=14，可以这个数据将被分为4、6、14这3个分片，这个过程进行了4次算数运算，之后簇内成员节点将其中的两个分片数据进行加密，此处有2个加密运算，因为假设簇的大小为4，簇头不进行分片，所以它要接收来自簇头以外的两个成员节点的分片数据，收到后对它们进行解密与自己剩余的那片数据相加。所以在L-CPDA算法中簇内每个节点的计算量为

QL-CPDA-midnode=7DA+2DB+2DC

(6)

对于L-CPDA中的簇头节点，簇头节点和簇内成员节点一样，首先进行数据扰动，执行了一次算数运算。不进行分片操作，接下来收到来自3个节点的两片加密的分片数据，对这3个数据进行3次解密，再与自身的综合数据进行相加运算，最后，簇头节点将3个节点发送的组合数据进行融合(实质是进行3次加法运算)，所以在L-CPDA算法中簇内每个节点的计算量为

QL-CPDA-cnod=7DA+3DC

(7)

可以看出，L-CPDA较CPDA无论在簇内通信量，还是在簇头计算量上都有较大的优势。

5.2 数据通信量分析

(8)

而L-CPDA算法使用动态分片的方式，根据簇的规模大小决定节点的分片数，当簇的规模满足2n

NL-CPDA=(m-1)·(log2m)

(9)

两种方案簇内传输数据包的个数对比如图6所示。

图6 簇内通信阶段的数据包个数

从图6中我们可以看出，CPDA算法簇内串通数据量增长较快，呈现幂次性增长，簇的规模越大，增长的也越快。而与CPDA方案相比，L-CPDA算法簇内串通阶段数据量增长较慢，增长幅度较小，类似线性增长，所以，在簇内数据通信量方面，L-CPDA比CPDA有较好的优势。

5.3 隐私保护性分析

隐私性代表了节点在通信过程中被破解的概率。在CPDA算法中，若一个簇的大小为m，簇内的每个节点都需要将自己采集的数据与种子值进行多项式运算，再加密发送给簇内m-1个节点，簇内其它节点只有知道了这m-1个密钥，这个节点的数据才会被破解。因此CPDA算法中一个节点被破解的概率为

(10)

这里的mmax表示簇的规模的最大值，mc表示簇的规模的最小值，q为窃听率，P(m=k) 表示簇的规模为k时的概率。

在L-CPDA算法中，定义节点发送数据为出度，节点接收数据为入度，在本算法中攻击者只有获得该节点产生的随机值和J-1个出度以及所有的入度，才能得到该节点得数据，因此可以得到

(11)

J是分片数，其中mmax表示簇的最大规模，mc表示簇的最小规模，P(in-degree=d)表示入度为d的概率，dmax表示簇内节点的最大的入度。两种算法的隐私度比较如图7所示。

图7 L-CPDA与CPDA的隐私度比较

从图7中可以看出，L-CPDA的隐私保护性要比CPDA略低，这是由于在L-CPDA中采取了动态分片的方式，随着簇的规模变化，分片数目也会发生变化，在通信过程中，节点的串通次数比CPDA要小，需要破解的通信链路变少，所以在pc=0.3的情况下，数据泄露率要高于CPDA，但是L-CPDA隐私数据被破解的概率低于0.02%，足够保护数据的隐私。

6 结束语

为了降低无线传感器网络数据融合过程中的计算和通信消耗，本文提出了一种轻量级的基于动态分片的数据融合隐私保护算法，针对CPDA算法通信量大、计算量大的缺点进行改进。从性能分析可以看出，虽然L-CPDA算法的隐私保护性略低于CPDA，但是数据被窃听的概率在可接受的范围之内；L-CPDA比CPDA通信量小，计算量低，从而能够减少数据通信的通信量，延长无线传感器网络的生命周期，有更强的实用性。此外，本文未考虑数据完整性，这将是下一步要进行的工作。