一种支持数据恢复的安全聚集算法

石鲁生，朱慧博

(1．宿迁学院计算机科学系，江苏宿迁　223800；2．南京航空航天大学计算机科学与技术学院，江苏南京　210016)

0　引言

无线传感器网络(wireless sensor networks，WSN)是由随机分布的集成了传感器、数据处理单元和通信单元的微小节点通过自组织方式构成的智能系统[1]。数据收集是无线传感器网络投入实际应用后的主要功能，由于资源受限的特征突出，各种收集方法一直将如何延长网络生命周期、降低能耗作为重要的设计目标。

收集数据时，数据聚集是WSN一项重要的节能技术[2]。由于传统的数据聚集方法如TAG[3]等在降低能耗的同时没有解决聚集过程中的安全问题，不具备实用价值，因此各种安全聚集算法应运而生。例如DADPP[4]通过向原始数据中添加随机种子和私有随机数进行扰动，达到隐私保护目的，ESPART[5]通过对原始数据的切片和加密传输来保护数据隐私，SIES[6]算法使用同态加密函数保护数据隐私，并可验证聚集结果的完整性，iCPDA[7]算法在隐私保护和完整性验证中分别使用了安全多方计算方法和同行监督机制，但安全的聚集算法带来了新的问题，一是原本降低了的通信开销大增；二是聚集类型受限严重，很多算法仅支持SUM一种。

可恢复数据的安全数据聚集算法RSDA(recoverable security data aggregation)，在保护数据隐私以及提供有效的数据完整性和真实性验证基础上，特别设计了数据恢复机制，从而使聚集节点在得到聚集结果的同时，能够精确、有效地恢复聚集前的原始数据。这些原始数据的获得让其他后续聚集操作在执行时，类型不再受限，同时也降低了网络总的能耗开销。

1　系统模型

1．1网络模型

由于层次化(分簇)无线传感器网络具有更好的扩展性和能量有效性[8]，RSDA算法中基于分簇的两层网络结构模型如下：

(1)一个基站(Base Station，BS)，它拥有强大的计算和通信能力，足够大的存储空间，稳定的电力供应，并采取了严密的防护措施。

(2)簇头节点(H-Sensors，HS)，负责收集簇内节点采集到的数据，然后聚集转发给基站。令网络中簇的数目为，簇头节点集合为。

(3)簇成员节点(L-Sensors，LS)，负责采集监测区域内的感知数据，再发送至簇头。簇头为的簇成员节点表示为，其原始感知数据用表示。

1．2攻击模型

鉴于BS不易被捕获，假设其是安全可信的，则将攻击依照严重程度分为以下3种：

(1)窃听无线通信。攻击者未捕获任何节点，但通过窃听网络中的无线通信获取或伪造数据。

(2)捕获LS。攻击者可以获取或篡改被捕获LS的感知数据，当然亦可攻击其转发的感知数据。

(3)捕获HS。攻击者可以获取被捕获HS所在簇内所有LS的感知数据，并可篡改HS上报给基站的中间聚集结果。

1．3密钥预分配

异构无线传感器网络部署前，BS首先根据EC-EG[9]方案生成密钥对(PBS，RBS)再根据Boneh[10]等的方案为Hi生成密钥对(PHi，RHi)。其中PBS为所有BS和HS共享的公钥，PHi是BS与Hi共享的公钥，RBS和RHi则分别为BS和Hi的私钥。

BS预先装载自身的密钥对(PBS，RBS)和每个Hi的公钥PHi。Hi除装载自身的密钥对(PHi，RHi)外，还将装载PBS和一个用于验证签名的哈希函数H()。

待网络部署完毕，各分簇形成后，为保护每个簇成员Lij和其簇头Hi之间的通信，同样由基站为它们生成一个密钥对P(Lij，RLij)。

2　可恢复数据的安全聚集算法

RSDA算法由三部分组成：簇内数据收集和聚集；簇头加密和签名传输；基站聚集和安全验证。

2．1簇内数据收集和聚集

(1)Lij发送加密的dij和签名sij给对应的Hi；

(2)Hi接收到加密信息后，利用Lij的签名sij验证dij的真实性；

(3)在一定时间周期内，Hi收集簇内所有dij，执行簇内聚集，并将聚集结果di作为自身数据。

2．2簇头加密和签名传输

(1)加密簇头Hi的di∶mi=di‖0t，其中‖为简单连接，0t为t个0组成的二进制数，l为传输信息中有效感知数据的bit位数，t=l×(i-1)。

(2)计算Hi的密文：ci=(ri，ai)=(ki×G，Mi+ki×Y)，其中ki为[1，Z]内的随机数，Mi=map(mi)=mi×G，map()为一个将值m映射为椭圆曲线点M的函数，满足加法同态性质，Z，G，Y∈PBS。

(3)计算Hi的签名：si=RHi×H(di)，其中H()为Hi预装的哈希函数。

(4)Hi将数据对(ci，si)向基站发送。

2．3基站聚集和安全验证

(1)并非所有簇头的聚集结果都一跳直接传输至基站，当一个簇头接收到其他一个或多个簇头的聚集结果时，它将把接收到的所有密文和签名与对应的自身密文和签名求和，得到新的密文、签名数据对，再向基站发送。在基站聚集后将得到最终结果(C，S)，即

(3)从M′获得m′∶m′=rmap(M′)=m1+m2+…+mn，其中rmap()为map()的反函数。

(4)恢复di：利用解密函数

Decode(m′，n，l)∶di=m′[(i-1)×l，i×l-1]

恢复并获取di。其中di为二进制数m′的第(i-1)×l位至i×l-1位上的数字所构成的二进制数，i=1，2，…，n。

2．4数据恢复示例

一个基于分簇的两层无线传感器网络如图1所示，其中BS为基站，H1、H2、H3和H4分别为4个簇头，每个簇包含数量不等的LS。如H2所在簇，共有L21L22、L23、L24和L255个，其他簇类似。

假设BS发出一个AVERAGE请求，启动数据聚集。令H2所在簇内5个LS的感知数据d21=5、d22=6、d23=4、d24=3、d25=2。H2收集到这些加密数据后，执行簇内AVERAGE聚集，得d2=4。其他簇类似可得d1=5、d3=2和d4=7。

l=3可满足d1、d2、d3和d4有效数据的传输需求，则H2加密d2得：m2=d2‖03=(100)2‖(000)2=(100000)2，再计算密文和签名对(c2，s2)发往。其他簇同理可得m1=(101)2、m3=(010000000)2、m4=(111000000000)2。

BS聚集所有HS的密文和签名后，得到(C，S)，解密C可得M′=M1+M2+M3+M4，再利用rmap函数得m′=m1+m2+m3+m4=(111010100101)2，则可恢复d1、d2、d3和d4：

d1=m′[(1-1)×3，1×3-1]=(111010100101)2[0，2]=(101)2=5

d2=m′[(2-1)×3，2×3-1]=(111010100101)2[3，5]=(100)2=4

d3=m′[(3-1)×3，3×3-1]=(111010100101)2[6，8]=(010)2=2

d4=m′[(4-1)×3，4×3-1]=(111010100101)2[9，11]=(111)2=7

3　主要性能分析与仿真

3．1安全性

根据2．2节攻击模型，分析RSDA算法的安全性。

(1)无线通信遭窃听。此时算法的安全性能够得到保障。因簇内或簇间的通信都进行了加密，只窃听无线通信，攻击者无法破解。此外由于算法要求所有传输信息必须具备相应的签名，而攻击者没有密钥无法伪造签名，因而不可能在通信链路中篡改信息或注入虚假信息。

(2)LS被捕获。如果攻击者将被捕获LS伪装成正常节点或发送较为合理的伪装数据参与聚集，目前算法都无法检测此类攻击，不过这种攻击危害性很小。在RSDA算法中，除被捕获LS外，攻击者无法假冒其他节点的信息，也不能篡改被捕获节点转发的信息，其原因是无法伪造相应的签名。

(3)HS被捕获。如果攻击者捕获了HS，情况将比较严重。而RSDA算法中使用了椭圆曲线加密技术，簇内聚集时，没有关于椭圆曲线点的加法函数，聚集无法完成，所以对椭圆曲线构造方法一无所知的攻击者，将无法完成任何未经授权的聚集。

此外，在应对共谋攻击方面，由于采用了共享密钥以及签名机制，即使在网络节点平均密度较低时，RSDA算法仍然较容易发现共谋攻击，而且节点密度越大，发现共谋攻击的能力越强。假设网络中的节点均匀分布，当节点通信半径R=50 m，平均节点密度取不同值时，RSDA算法与iCPDA算法无法检测出共谋攻击的概率[7]如图2所示。

图2　RSDA算法与iCPDA算法应对共谋攻击的能力

通过以上分析可以看出，在各种攻击面前，算法表现出了非常好的安全性能。特别值得指出的是，与iCPDA算法只能验证聚集结果的完整性不同，RSDA算法通过签名机制可以验证所有原始数据的真实性和完整性，这为数据恢复后其他操作的进行提供了可靠的保障。

3．2数据恢复

2．4节的示例表明，基站在获得最终结果的同时，可以恢复所有簇头的聚集结果。因此在一些精度要求不高的应用环境中，许多后续操作可以直接在基站执行。因为同一簇内的地理位置相近，所采集数据在数值上相似甚至重复的情况非常普遍，如令各簇的聚集结果如平均值作为本簇值的代表，基站可轻松获得全部感知数据近似的最值或总和。

在精度要求较高的场合，可以借助HS的帮助完成各种后续操作。这是由于在簇内聚集过程中，HS同样可以还原簇内各LS的原始数据，并进行验证，因此基站只要命令每个HS节点执行指定聚集函数即可。

数据恢复功能完全突破了以往各种安全聚集算法对聚集类型的限制，同时也节省了执行后续聚集工作的计算和通信开销，进而从总体上降低了网络中的能量消耗，延长了网络寿命。

3．3查询周期

通过最终聚集结果的准确性可以衡量算法查询周期的长短，即时间效率。记AR为基站聚集结果与由真实数据所得聚集结果的比值，理想情况下，AR=1。在现实环境中，如果所有数据的收集、传输、加密和聚集工作都能在指定查询周期内顺利完成，则AR值应接近或达到1，但因在指定查询周期内一些数据的处理工作没完成，必导致准确性降低，且查询周期越短，准确性越差。而较长的查询周期可以减少因无线信道内的碰撞而造成的数据丢失，进而提高准确性。因此，如果某时间点之后，算法的AR值一直稳定在1附近，则该时间点就是算法近似的最小查询周期。

利用TOSSIM仿真环境，将500个传感器节点随机部署在一个指定的区域内，分别模拟执行TAG、iCPDA(取0.1，0.2，0.3)和RSDA算法(n取50，100，150)各50次，计算平均值，得查询周期和通信开销的结果分别如图3和图4所示。其中pc为iCPDA算法中节点成为簇头的概率，n为RSDA算法中簇头的个数。当pc分别取0.1、0.2和0.3时，RSDA算法中簇头个数n分别为50、100和150。仿真中假定簇头拥有远高于一般簇成员的计算和存储能力。

图3　TAG、iCPDA和RSDA算法的查询周期

如图3，对RSDA算法，在n=150时，查询周期大约为20 s，基本与不带隐私保护和完整性验证功能的TAG算法相当，这是因为此时网内HS数量较多，每个簇的成员较少，借助簇头强大的计算能力，簇内数据收集、加密、聚集等工作能在较短时间内完成，从而缩短了整个网络的查询周期。当n=100和50时，RSDA算法的查询周期分别增大至和附近，说明随着数量的减少，簇内数据收集和处理的工作量增大，延长了查询周期。iCPDA和RSDA算法的查询周期分别随pc和n值的增大而减小，趋势相同，但对应的查询周期RSDA算法更短，且优势明显。

3．4通信开销

由于无线传感器网络中数据通信的能量消耗远大于计算，因此可以用通信开销来衡量整个网络的能耗。

图4　TAG、iCPDA和RSDA算法的通信开销

如图4所示，3种算法的通信开销都与查询周期关系不大，其中功能最简单的TAG算法通信开销最低。iCPDA与RSDA算法的通信开销分别随着和值的增大而增大，因为或值的增大意味着有更多的簇，需要更多的数据传输。可见在分簇的无线传感器网络中，并非越多越好。除n=50以外，RSDA算法的通信开销只多出对应iCPDA算法少许，相差不大。这主要是由于RSDA算法中所传输的数据包信息丰富，长度较长所致。考虑到RSDA算法可以提供更高级别的安全保障，以及数据恢复为后续工作节省的能量消耗，首次聚集过程中的通信开销是可以接受的，多次聚集后，总的通信开销优于iCPDA算法。

4　结束语

RSDA算法较好的实现了数据的隐私保护，并具备验证数据真实性和完整性的功能。算法的数据恢复能力，使聚集节点能够恢复聚集前的原始数据。性能分析和仿真实验的结果验证了算法的安全性和高效性，虽然首次聚集通信量稍大，但多次聚集后，总体能耗令人满意。

目前的RSDA算法对于簇内成员为一般传感器节点，簇头为计算、存储、通信等能力远高于一般簇成员的高资源传感器节点的异构无线传感器网络显然更加适用，如何使其更具通用性以及如何进一步降低首次聚集过程中的能耗开销将是今后努力的方向。

参考文献：

[1]冯延蓬，仵博，郑红燕．异构无线传感器网络中基于POMDP的实时调度算法．仪表技术与传感器，2012(8)：101-104．

[2]王翥，魏德宝，王玲．传感器网络数据聚合时机控制算法．仪表技术与传感器，2012(5)：75-78．

[3]MADDEN S，FRANKLIN M J，HELLERSTEIN J M．TAG：A Tiny Aggregation Service for Ad hoc Sensor Networks．Proceedings of the 5th Symposium on Operating Systems Design and Implementation．NewYork，USA，2002：131-146．

[4]YAO Jian-Bo，WEN Guang-Jum．Protecting classification priracy data aggregation in wireless sensor networks．Proceedings of the 4th International Conference on Wireless Communication．Networking and Mobile Computing (WiCOM)．Dalian：China，2008：1-5．

[5]杨庚，王安琪，陈正宇，等．一种低耗能的数据融合隐私保护算法．计算机学报，2011，34(5)：792-800．

[6]Stavrns Papadopoulos，Aggelos Kiayias，Dimitris Papadias．Secure and efficient in-network processing of exact SUM queries．Proceedings of the 27th International Conference on Data Engineering(ICDE)．Hannover：Germany，2011：517-528．

[7]HE W，LIU X，NGUYEN H，et al．A cluster-based protocol to enforce integrity and preserve privacy in data aggregation．Proceedings of the 29th IEEE International Conference on Distributed Computing Systems Workshops．Montreal：QC，Canada，2009：14-19．

[8]张金荣，王越，王东，等．组合能量圆分布无线传感器网络分簇路由与拓扑形成算法．仪表技术与传感器，2009(1)：61-64．

[9]MYKLETUN E，GIRAO J，WESTHOFF D．Public Key Based Cryptoschemes for Data Concealment in Wireless Sensor Networks．Proc．of the 2006 IEEE International Conference on Communications(ICC2006)，Istanbul：Turkey，2006：2288-2295．

[10]BONEH D，GENTRY C，LYNN B，et al．Aggregate and Verifiably Encrypted Signatures from Bilinear Maps．Proc of the 22nd International Conference on Theory and Applications of Cryptographic Techniques (Eurocrypt2003)，Warsaw：Poland，2003：416-432．