無線傳感器網絡中分布式存儲方案的改進

王學軍

江蘇省宿遷學院計算機科學系 江蘇 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.