无线传感器网络中分布式存储方案的改进

王学军

江苏省宿迁学院计算机科学系 江苏 223800

0 引言

本文将提出一种基于 Shamir秘密共享方法的分布式存储方法。运用此方法将数据加密成共享份分发到各个存储节点上，在获取数据时只要获取大于阈值的共享份就可以还原出数据。同时对Shamir秘密共享方法进行改进，减小每份秘密共享份的大小，使得存储更高效。

1 传感器网络的结构

本文采用的无线传感器网络如图1所示。拥有大量的普通无线传感器，普通传感器在部署的区域内监视并生成数据，如感知温度、压力、湿度等。生成的原始数据记为D。普通传感器将产生的数据运用我们将要提到的加密方法将数据加密成多个共享份 ( D1, D2, D3,...,Dn)，并将这些共享份分发到n个存储节点上进行存储。网络中同时有少量的存储节点(数量大于n)和一个Sink节点。

图1 无线传感器网络结构

其中存储节点位于网络比较中心的位置，这样普通传感器节点生成的数据发到邻近的存储节点，存储节点上形成秘密共享份Di发给Sink。Sink从发来的数据中重新构建出原来的数据 D，只要得到的有效秘密共享份的数目大于阈值k即可。其中n和k是系统设置的参数，用于控件分布式的数据的容灾性。图2为用户查询数据示意图。

图2 用户查询数据示意图

为表述方便，对于文中提到的各标记和其表示的意义列表如表1。

表1 各标记表示的意义

2 分布式存储方法

2.1 Shamir秘密共享分布式存储方法

Shamir秘密共享是基于拉格朗日值的加密算法。其把数据D看成为一个数，同时选取一个大的素数p，且p大于D且大于n。在[0,]p之间随机选取 1k− 个数，分别为造出一个 1k− 多项式。其中ia用作多项式的第i次项的系数，D作为常数项系数，如公式化，然后在此多项式构成的曲线上选取 ( 1 , F(1) ), ( 2 ,F(2 ) ), … ,(n ,F(n))分别作为加密后生成的秘密共享份 D1,D2, ...,Dn。在重构数据时只需要获得秘密共享份中的k份就可重构出曲线 ()Fx，从而得出常数项D，即得出原来的数据。

DAS加密算法描述如下：

而在重构数据时，只要获得多项式曲线上任意k个点，即k份 Di就可以得出此多项式曲线的方程，进而求得F ( 0)= D ，获得了原数据。

此方法中每份秘密共享份的大小和原数据的大小相同，即Di= D。对于一个(k,n)的秘密共享来说，有：

即所产生的最终数据是原数据的倍，存储效率不高。因此我们对之进行改进，减小每份秘密共享份的大小。

2.2 改进后的Shamir秘密共享分布式存储方法

改进后的方法是直接将数据D分成 k − 1份后，选取一个大素数p，使得 p ＞max(dmax,n)其中的 dmax= m ax(di)，在Zp选取任意一个数a，把 d1和a分别作为一次多项式的一次项系数和常数项系数构造一次多项式曲线 F1( x) = a x + d1。然后从这条曲线上选取两点 Ad11= F1( 1),= F1(2)。这就相当于与Shamir的(2，2)秘密共享将 d1分成两份秘密共享份。接着用 Ad12,分别作为二次项系数、一次项系数和常数项构造一条二次多项式曲线：

输入：数据D DD D① 选取一个大的素数p，使得pn＞且pD＞。D就是要加密的数据② 在区域 nZ 中随机选取 1k− 个数 1 2 3 1输出：秘密共享份 1 2, ,...,n aa a a−③ 用D和 1 2 3 1, , ,...,k aa a a−构建出一个 1k− 次多项式曲线, , ,...,k= + + + +④ Do for 1in≤≤选取(i，F(i))作为 iD Fx D axax a x p() ... (mod )2 k−1 1 2 1k−

如此选点构建曲线，删除前面一次生成的点，再在新曲线上选取点迭代，直到 1k− 。此时由前面 1k− 个点和1kd−，最后生成一条 1k− 次多项式曲线：

DES加密算法描述如下：

输入：数据D输出：秘密共享份 1 2, ,..., n DD D① 选取一大素数 p，使得= ≤ ≤ −② 在区域 pZ 中随机选取1个数a生成曲线 1 1()，其中 max max(),1 ( 1)p d n＞max( ,)max d d i k i Fx ax d= +③ 在生成的曲线上选取两个点11 1(1)A F=④ Do for 21ik≤≤−a.用前面生成的点和 id生成多项式曲线：AF= 和121(2)d d Fx A x A x= + +() ...i i−1 i d i d i i−2() (1)i −2−+ +b.在此曲线上选取n个秘密共享份：(,())A x d di −21i=c.删除前一次生成的秘密共享D nFn n i A A A d d d i i −11 2, ,...,i −1i −1 d.将 1D到 nD作为最终生成的秘密共享份

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

容易得知，改进后方法的每份秘密共享份iD的大小约为D的 1k− 分之一。对于一个(,)kn的秘密共享来说，改进后的秘密共享方法生成的数据大小仅为：

从而很好地节省了存储空间。

3 实验结果

由于实验中的传感器数目不是很大，我们选取比较小的n和k。如图3所示，选取(2，3)、(3，6)、(4，9)、(5，10)、(7，12)作为秘密共享点，图3中显示了利用(n，k)秘密共享每加密 1KB数据所消耗的时间。其中 DS线表示的是采用Shamir秘密共享方案加密算法得出的数据；而 DES线表示的是采用改进后的 Shamir秘密共享方案加密算法所得的数据。图4表示的是1KB数据经过加密后产生的n份秘密共享份的总大小。

从图3和图4可以看出，在n，k取值比较小的情况之下，两种算法加密数据所消耗的时间相差不大，但总的分发数据有了很大的减少。这说明DES方案加密有较高的存储效率。

图3 每KB数据加密所用时间

图4 1KB数据加密后分发数据总大小

4 结束语

本文针对Shamir秘密共享加密方案进行了改进，提出了一种效率较高的分布式存储方法，使得数据得到加密的同时又节省了存储空间，具有一定的容灾能力。但在提升存储效率的同时会稍微加大用于加密的计算开销，这相比于节省的存储空间来说是值得的。尤其对于实际应用中存储节点比较少的情况下能达到很好的效果。本文的一些细节还可以进一步研究，如数据如何分发到各存储节点更节能等。下一步将继续研究，以求更好改善分布式存储方法的性能。

[1]孙利民,李建中,陈渝等.无线传感器网络[M].北京:清华大学出版社.2005.

[2]方红萍,方康玲.无线传感器网络数据存储策略研究综述[J].计算机工程与设计.2010.

[3]梁小满,马行坡.无线传感器网络数据存储技术研究进展[J].计算机应用研究.2009.

[4]王刚,黄刘生,杨振国等.无线传感网络中的存储节点配置[J].小型微型计算机系统.2010.

[5]毕学军,杨朝红.无线传感器网络的数据存储和索引技术[J].计算机工程.2009.