无线传感器网络中一种分布式安全存储方案*

曾新革，马 征，2，王国军*

(1.中南大学信息科学与工程学院，长沙 410083;2.湖南大学信息科学与工程学院，长沙 410082)

无线传感器网络是由大量传感器节点通过无线通讯自组织形成的网络。传感器节点由供电模块，无线通讯模块，感应模块，计算等模块构成。通过各个模块间的相互协作，传感器节点可以将无线传感器网络在监控区域中监测的数据信息发送给邻近的传感器节点直到特定的用户。由于传感器网络体型小，价格便宜，部署方便，被广泛用于智能交通、环境监控、火山监测、深海探测、敌情侦察、智能衣服等科学，医学和军事应用［1－3］。

但由于无线传感器网络处开放的无线环境中，很容易被窃听和破坏，并且节点能量有限，会由于能量的耗尽而失效。如何构建安全的数据存储方案，有效地保证无线传感器网络中数据的存储有效和存储安全，不被窃取和恶意篡改，甚至能在即使有少许节点失效的情况仍能恢复数据是一个重大的课题。本文将提出一种以数据为中心的分布式存储方案，在保证数据安全的同时，有效地节省存储空间。

本文将在第1部分介绍相关工作，接着在第2部分提出网络模型，再着在第3部分描叙提出的方案，然后在第4部分对方案进行实验的模拟和分析。最后第5部分对全文进行总结。

1 相关工作

传感器网络数据的存储主要分为两大类。一类是将数据通过汇聚节点(Sink)发送到外部网络进行存储，即外部存储。另一类是内部存储，即将数据存储在传感器网络内部。本文所要讨论的属于内部存储。

内部存储又分为集中式的存储和分布式的存储:

集中式的存储是将传感器网络中生成的数据全部存于中心节点。中心节点一般为汇聚节点Sink，或Mobile Sink［4］。虽然在传感器网络中认为Sink节点具有很强的能力和完善的保护措施，能完全保证存储于其上的数据安全。但集中式的存储中Sink既要存储大量的数据又要处理所有用户的查询，会造成Sink成为网络的瓶颈［1，5］。集中式存储中如果中心节点失效，那么全部的数据会丢失。同时由于节点都要将数据发送到中心节点，所以收集数据时开销大，容错性差。

分布式的存储，有本地存储和以数据为中心的存储。本地存储是传感器节点存储自己产生的数据，或者通过其他方法将数据随机地分发到邻近的传感器节点进行存储［6－7］。本地存储的方法在存储数据的时候不需要消耗额外的通信能量，但查询数据将耗费大量的通信能量。

而以数据为中心的分布式存储近年来越来越受到关注。以数据为中心的存储是在感知数据不需要被及时查询到的网络中，根据需要存储的数据内容的特点来将数据存储到相应的节点以便于更好地查询［8］。在感知数据量大，感知数据增加的速度大于查询数据的速度为特点的传感器网络，以数据为中心的存储方案有更高的性能。

分布式存储可以很好地解决集中式存储中储数据的中心节点会成为网络瓶颈的问题，也避免了中心节点失效而造成数据全部丢失的危险。关于本地存储的安全的研究已有不少，如文献［9－11］，但以数据为中心的存储安全的研究较少。文献［9－11］提出将数据通过Shamir Secret Sharing将数据分成许多共享份存于邻居节点，只需要获得这些共享份中的一部分共享份就可以获取出原来数据的存储方法来提高数据的可靠性。但他们都是将数据存储于邻居节点，并不是基于以数据中心的传感器网络，因此存储和查询的效率都不高。文献［9－10］的分布式存储方案中每个共享份和原来的数据大小相等，多份共享份就有多份冗余，因此会大量消耗存储空间。而文献［11］提到的加密方案减小了存储空间，但他没有具体实现，且用的代数签名(Algebraic Signature)进行认证并不能很好地保证数据的完整性。因为构造两个具有相同代数签名的数据并不难，且他不能很好的预防节点伪造数据。因此，本文基于以上问题提出了基于数据为中心的分布式存储方案。

2 网络模型

2.1 网络模型

本文采用的无线传感器网络结构如图1所示。拥有大量的资源有限的普通传感器节点，普通传感器节点在部署的区域内监听并生成数据，如感知温度，压力，湿度等。生成的原始数据记为D。以及少量的资源富有的存储节点Storage Node，主要是存储容量大。每个存储节点和普通节点都有自己唯一的ID。分别用v和s来表示普通节点和存储节点。

图1 网络结构

网络还包含一个Sink节点，用来处理用户的查询和从存储节点上获取数据。存储节点位于网络比较中心的位置，这样普通传感器节点生成的数据发送到存储节点时候会比较节能［12］。Sink位于网络的中心，能更好的均衡各方向存储节点或普通节点与Sink节点进行通讯时所带来的开销。

2.2 安全假设

Sink节点是链接外界网络和无线网络的枢纽。我们认为其是能力强大的，能承受任意安全攻击，也就是Sink节点总是可信的。

攻击主要来自:①普通节点和存储节点可能被恶意的敌方损坏。②攻击者可能进行被动攻击，例如监听数据，从而知道数据的发送和传输或数据的内容。③敌方也可能主动攻击，攻陷某些节点包括普通节点和存储节点，攻陷后，敌方可能窃取，伪造，篡改数据，或给查询返回错误的结果。

传感器网络中每个普遍节点和Sink间共享密钥kv。每个存储节点和Sink间共享密钥ks。同时每个普通节点和每个存储节点间共享密钥kvs。

2.3 以数据为中心的存储

当普通传感器将生成数据D时。运用我们将要提到的存储方案将数据加密成n个共享份(D1，D2，D3，…，Dn)，然后利用单向的 Hash 函数和密钥kv生成消息验证码。将此共享份和消息验证码和节点编号等用生成数据的节点与相应的存储节点间的密钥进行加密。并将每份加密的共享份分发到对应的存储节点上去。这些对应的存储节点是通过不同的GHT映射来确定的。发送的数据如下:

其中v为生成此数据的传感器节点的编号。seqno是用于标识此数据的唯一序列号。MACkv(Di)是将共享份Di用单向Hash函数和密钥kv生成的消息验证码。然后将seqno、共享份和消息验证码用v和si间的密钥kvsi加密后发送给存储节点si。通过加密可以防止敌方窃听而泄密数据内容。消息验证码可以防止存储节点恶意地篡改数据或发送错误数据。

当用户需要查询时，用户向Sink发出查询数据请求，如图2所示。Sink收到用户查询请求并验证用户的权限。验证成功后，Sink向存储节点发送查询请求，可以采用基于隐私保护的策略查询［13］或基于安全区域的查询［14］。存储节点收到Sink发来的查询请求，会将相应的数据，即存储在n个存储节点上的n个秘密共享份发回给Sink。Sink首先验证MACkv(Di)是否正确来验证各份共享份是否数据完整。从完整的共享份中选取不小于阈值k(1≤k≤n)的份数进行重构出数据。任意小于k的份数将不能重构出数据。其中n和k是系统设置的参数，用于控制分布式的数据的容灾性。文中提到的各标记及其意义如表1所示。

图2 用户查询

表1 各标记表示的意义

3 存储方案

将生成的数据D加密成n个共享份，文献［8－9］提出了基于SSS(Shamir’s Secret Sharing)的加密方法。文献［10］虽然没说用SSS加密，但其采用的方法就是SSS，且提供了具体实现和分析。

SSS是基于拉格朗日插值的加密算法。SSS的加密方法是通过构造一条k－1次曲线F(x)，并把数据D做为其常数项，选取曲线上的n个点作为秘密共享份即加密后的结果，然后将共享份分发给n个存储节点。从线性代数的知识容易得知，只要获取k个共享份也就是曲线上的k个点就可以重构出此曲线方程，从而得出数据D。

SSS方案中每份秘密共享份和曲线方程的常数项即数据D属于同一个域ℤp，所以共享份的大小和原数据的大小相同［15］，即|Di|=|D|。一个(k，n)的秘密共享，经过加密后数据总大小为:

即所产生的最终数据将是原数据的n倍，存储效率不高。因此我们对之改进，减小每份秘密共享份的大小。本文提出了迭代的SSS分布式存储方案和基于Reed Solomon Code的存储方案。

3.1 迭代的SSS分布式存储方法(RSS)

RSS方案是将数据D分成k－1份，每份标识为di。di的大小为D的k－1分之一。然后用每份数据di在小的域ℤp中构建曲线生成共享份。共享份的大小和di的大小相同。从而节省每份共享份的大小。最终的曲线的构造是用SSS方案迭代构造而成。

(1)将D分成k－1 份，分别为d1，d2，…dk－1。简单的分法是假设D有m位，取前m/(k－1)位作为d1，第二个m/(k－1)位作为dn，直达dk－1。如果k=1，意味着只需要1份共享份就可以恢复出数据。那么直接拷贝n份D作为D1，D2，…，Dn。例如D的大小有40位，如果k=5，也就是说要将数据D分成四份，每份10位。于是将D的前10位作为d1，D的第10到20位作为d2，D的第20到30位作为d3，最后10位作为d4。

(2)迭代构造k－1次曲线。

将数据分成k－1份后，选取一个大的素数p使得p＞max(dmax，n)，不等式中dmax=max(di)。在ℤp中任意选取1个数a，把d1和a分别作为一次多项式的一条一次项系数和常数项系数即SSS方案构造一次多项式曲线F1(x)=ax+d1。然后从这条曲线上选取两点=F1(1)=F1(2)。这就相当于SSS将d1分成两份秘密共享份。接着用和d2分别作为二次项系数，一次项系数和常数项的SSS方案构造一条二次多项式曲线F2(x)=2++d2。又在这条二次曲线上选取三个点=F2(1)，=F2(2)和=F2(3)，相当于d2的三个共享份，同时这三个共享份包含了d1的信息，所以生成和后将删除和。接着又用和d3构造一条三次多项式曲线F3(x)=。如此选取点，构建曲线，删除前面一次生成的点，再在新曲线上选取点，迭代直到k－1。此时由前面选取的k－1个点和dk－1，最后生成一条k－1次多项式曲线

(3)然后在此曲线上选取n个点生成

即为加密生成的n份秘密共享份。

加密的算法如下:

重构数据时，从各个存储节点获得秘密共享份，从中选取k个秘密共享份Di。然后构造出多项式曲线:

3.2 基于Reed Solomon Code的秘密共享(RSC)

RSS迭代的方法虽然能节省存储空间，但增加了计算量。利用Reed Solomon Code的秘密共享方法，将数据D直接分成k份作为一条k－1次曲线的系数来构造曲线能一次构造出曲线，从而节省计算量。同时也能使得共享份的大小和di大小相同。

(1)将D分成k份，分别为d1，d2，…dk。

(2)构造k－1次曲线。

把d1，d2，…dk作为系数构造曲线

(3)从上面选取n个点作为共享份。

具体算法如下:

也很容易得知RSC方法的每份秘密共享份Di的大小为|D|的k分之一。对于一个(k，n)的秘密分享，改进后的秘密共享方法生成的数据大小为:

4 实验分析

网络中各节点会由于能量耗尽或被破坏而失效。假设存储节点的失效率为p。在(k，n)分布式存储方案中。SSS，RSS和RSC方案都需要失效的节点不多于n－k才能恢复出数据。所以运用(k，n)分布式方案后的数据丢失率为P。

设定网络中有100个存储节点，节点的失效率为p，其中的失效率意味着返回错误的共享份或不返回共享份。对不同的(k，n)情况下数据的从获取的共享份不能构建出原来数据的概率(50次平均后的结果)如图3所示。其中的(1，1)曲线相当于把原始数据直接存储。从图中容易知道，在节点失效率不高的情况下，分布式的存储方案都能很好的减少数据的丢失率。而在节点失效率高时，意味着此时网络已经接近生命周期末期，快邻近死亡了。此时(k，n)分布式存储方案减小丢失率成效不明显。是由于多份数据的存储会带来多份数据的失效率，而失效率越高，能保障至少k份共享份完整的概率急剧变小。

图3 数据丢失率

网络中普通节点生成数据，假设原始的数据包大小为64 bit。SSS，RSS和RSC各个方案加密后的数据大小和加密时间分别如图4和图5。RSS方案中共享份的大小仅为SSS方案中共享份大小的k－1分之一。图4中显示了RSS方案在存储上优于SSS方案，但从图5可看出RSS需要消耗更多的计算开销。这是由于其迭代多次才能构造曲线，所以开销大。

图4 加密后数据的大小(原始大小为64 bit)

图5 每加密一个数据包用的时间

而RSC方案由于每份共享份的大小为原数据的1/k。所以所有共享份总大小比RSS中共享份的总大小要小。所以在需要的存储上小于RSS方案且远远小于SSS方案，同时能一次构造出曲线，因而加密所消耗的计算时间和SSS方案差不多，且低于RSC方案的加密时间。很好的验证了RSC的存储方案能有效地节省存储空间，同时保持较小的计算量。

对于查询开销，由于查询的方式与SSS的查询策略的方法没有太大区别，只是节省了查询到的结果的大小，能节省一点开销。

5 结束语

本文提出了一种高效的分布式数据存储方案，使得加密数据的同时又能节省存储空间，并且具有一定的容灾能力。虽然在提升存储效率的同时稍微增加了用于加密的计算开销，但计算量是较小的，相比于节省的存储空间来说是值得的。尤其对于实际应用中n比较小的情况下能达到很好的效果。值得指出的是，本文的某些细节还可以进一步进行探讨，比如采用什么样的方案数据发到各存储节点更节能等。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine.2002，40(8):102－114.

［2］陈积明，林瑞仲，孙优贤.无线传感器网络通信体系研究现状及展望［J］.传感技术学报，2006，19(4):1290－1295.

［3］Sung J，Ahn S，Park T，et al.Wireless Sensor Networks for Cultural Property Protection［C］//AASNET’08.2008:615－620.

［4］Xu Xing，Luo Ji，Zhang Qian.Delay Tolerant Event Collection in Sensor Networks with Mobile Sink［C］//INFOCOM 2010.2010，1－9.

［5］孙利民，陈渝， ，等.无线传感器网络［M］.北京:清华大学出版社，2005:227－238.

［6］Intanagonwiwat C，Govindan R，Estrin D，et al.Directed Diffusion for Wireless Sensor Networking［J］.IEEE/ACM Trans.on Networking，2003，11(1):2－16.

［7］Bhavani Thuraisingham.Security and Privacy for Sensor Databases［J］.Sensor Letters，Volume 2(1):37－47.

［8］Diao Y，Ganesan D，Mathur G，et al.Rethinking Data Management for Storage-centric Sensor Networks［C］//CIDR 2007.2007:22－31.

［9］Yi Ren，Vladimir O，Frank Y L，et al.A Distributed Data Storage and Retrieval Scheme in Unattended WSNs Using Homomorphic Encryption and Secret Sharing［C］//Wireless Days(WD)，2009 2nd IFIP，2009:1－6.

［10］Parakh A，Kak S.A Distributed Data Storage Scheme for Sensor Networks［J］.Security and Privacy in Mobile Information and Communication Systems，2009，17:14－22.

［11］Wang Q，Ren K，Lou W，et al.Dependable and Secure Sensor Data Storage with Dynamic Integrity Assurance［C］//INFOCOM 2009，2009:954－962.

［12］王先峰，项军，胡斌杰.一种无线传感器网络能量模型的评估及改进［J］.传感技术学报，2009，22(9):1318－1323.

［13］Subramanian N，Yang Ka，Zhang W，et al.ElliPS:A Privacy Preserving Scheme for Sensor Data Storage and Query［C］//INFOCOM09，2009:936－944.

［14］Shi J，Zhang R，Zhang Y.Secure Range Queries in Tiered Sensor Networks［C］//INFOCOM09，2009:945－953.

［15］Hugo Krawczyk.Secret Sharing Made Short［C］//CRYPTO93，1993:136－146.