無(wú)線傳感器網(wǎng)絡(luò)中分布式存儲(chǔ)方案的改進(jìn)

王學(xué)軍

江蘇省宿遷學(xué)院計(jì)算機(jī)科學(xué)系 江蘇 223800

0 引言

本文將提出一種基于 Shamir秘密共享方法的分布式存儲(chǔ)方法。運(yùn)用此方法將數(shù)據(jù)加密成共享份分發(fā)到各個(gè)存儲(chǔ)節(jié)點(diǎn)上，在獲取數(shù)據(jù)時(shí)只要獲取大于閾值的共享份就可以還原出數(shù)據(jù)。同時(shí)對(duì)Shamir秘密共享方法進(jìn)行改進(jìn)，減小每份秘密共享份的大小，使得存儲(chǔ)更高效。

1 傳感器網(wǎng)絡(luò)的結(jié)構(gòu)

本文采用的無(wú)線傳感器網(wǎng)絡(luò)如圖1所示。擁有大量的普通無(wú)線傳感器，普通傳感器在部署的區(qū)域內(nèi)監(jiān)視并生成數(shù)據(jù)，如感知溫度、壓力、濕度等。生成的原始數(shù)據(jù)記為D。普通傳感器將產(chǎn)生的數(shù)據(jù)運(yùn)用我們將要提到的加密方法將數(shù)據(jù)加密成多個(gè)共享份 ( D1, D2, D3,...,Dn)，并將這些共享份分發(fā)到n個(gè)存儲(chǔ)節(jié)點(diǎn)上進(jìn)行存儲(chǔ)。網(wǎng)絡(luò)中同時(shí)有少量的存儲(chǔ)節(jié)點(diǎn)(數(shù)量大于n)和一個(gè)Sink節(jié)點(diǎn)。

圖1 無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

其中存儲(chǔ)節(jié)點(diǎn)位于網(wǎng)絡(luò)比較中心的位置，這樣普通傳感器節(jié)點(diǎn)生成的數(shù)據(jù)發(fā)到鄰近的存儲(chǔ)節(jié)點(diǎn)，存儲(chǔ)節(jié)點(diǎn)上形成秘密共享份Di發(fā)給Sink。Sink從發(fā)來(lái)的數(shù)據(jù)中重新構(gòu)建出原來(lái)的數(shù)據(jù) D，只要得到的有效秘密共享份的數(shù)目大于閾值k即可。其中n和k是系統(tǒng)設(shè)置的參數(shù)，用于控件分布式的數(shù)據(jù)的容災(zāi)性。圖2為用戶查詢數(shù)據(jù)示意圖。

圖2 用戶查詢數(shù)據(jù)示意圖

為表述方便，對(duì)于文中提到的各標(biāo)記和其表示的意義列表如表1。

表1 各標(biāo)記表示的意義

2 分布式存儲(chǔ)方法

2.1 Shamir秘密共享分布式存儲(chǔ)方法

Shamir秘密共享是基于拉格朗日值的加密算法。其把數(shù)據(jù)D看成為一個(gè)數(shù)，同時(shí)選取一個(gè)大的素?cái)?shù)p，且p大于D且大于n。在[0,]p之間隨機(jī)選取 1k? 個(gè)數(shù)，分別為造出一個(gè) 1k? 多項(xiàng)式。其中ia用作多項(xiàng)式的第i次項(xiàng)的系數(shù)，D作為常數(shù)項(xiàng)系數(shù)，如公式化，然后在此多項(xiàng)式構(gòu)成的曲線上選取 ( 1 , F(1) ), ( 2 ,F(2 ) ), … ,(n ,F(n))分別作為加密后生成的秘密共享份 D1,D2, ...,Dn。在重構(gòu)數(shù)據(jù)時(shí)只需要獲得秘密共享份中的k份就可重構(gòu)出曲線 ()Fx，從而得出常數(shù)項(xiàng)D，即得出原來(lái)的數(shù)據(jù)。

DAS加密算法描述如下：

而在重構(gòu)數(shù)據(jù)時(shí)，只要獲得多項(xiàng)式曲線上任意k個(gè)點(diǎn)，即k份 Di就可以得出此多項(xiàng)式曲線的方程，進(jìn)而求得F ( 0)= D ，獲得了原數(shù)據(jù)。

此方法中每份秘密共享份的大小和原數(shù)據(jù)的大小相同，即Di= D。對(duì)于一個(gè)(k,n)的秘密共享來(lái)說，有：

即所產(chǎn)生的最終數(shù)據(jù)是原數(shù)據(jù)的倍，存儲(chǔ)效率不高。因此我們對(duì)之進(jìn)行改進(jìn)，減小每份秘密共享份的大小。

2.2 改進(jìn)后的Shamir秘密共享分布式存儲(chǔ)方法

改進(jìn)后的方法是直接將數(shù)據(jù)D分成 k ? 1份后，選取一個(gè)大素?cái)?shù)p，使得 p ＞max(dmax,n)其中的 dmax= m ax(di)，在Zp選取任意一個(gè)數(shù)a，把 d1和a分別作為一次多項(xiàng)式的一次項(xiàng)系數(shù)和常數(shù)項(xiàng)系數(shù)構(gòu)造一次多項(xiàng)式曲線 F1( x) = a x + d1。然后從這條曲線上選取兩點(diǎn) Ad11= F1( 1),= F1(2)。這就相當(dāng)于與Shamir的(2，2)秘密共享將 d1分成兩份秘密共享份。接著用 Ad12,分別作為二次項(xiàng)系數(shù)、一次項(xiàng)系數(shù)和常數(shù)項(xiàng)構(gòu)造一條二次多項(xiàng)式曲線：

輸入：數(shù)據(jù)D DD D① 選取一個(gè)大的素?cái)?shù)p，使得pn＞且pD＞。D就是要加密的數(shù)據(jù)② 在區(qū)域 nZ 中隨機(jī)選取 1k? 個(gè)數(shù) 1 2 3 1輸出：秘密共享份 1 2, ,...,n aa a a?③ 用D和 1 2 3 1, , ,...,k aa a a?構(gòu)建出一個(gè) 1k? 次多項(xiàng)式曲線, , ,...,k= + + + +④ Do for 1in≤≤選取(i，F(xiàn)(i))作為 iD Fx D axax a x p() ... (mod )2 k?1 1 2 1k?

如此選點(diǎn)構(gòu)建曲線，刪除前面一次生成的點(diǎn)，再在新曲線上選取點(diǎn)迭代，直到 1k? 。此時(shí)由前面 1k? 個(gè)點(diǎn)和1kd?，最后生成一條 1k? 次多項(xiàng)式曲線：

DES加密算法描述如下：

輸入：數(shù)據(jù)D輸出：秘密共享份 1 2, ,..., n DD D① 選取一大素?cái)?shù) p，使得= ≤ ≤ ?② 在區(qū)域 pZ 中隨機(jī)選取1個(gè)數(shù)a生成曲線 1 1()，其中 max max(),1 ( 1)p d n＞max( ,)max d d i k i Fx ax d= +③ 在生成的曲線上選取兩個(gè)點(diǎn)11 1(1)A F=④ Do for 21ik≤≤?a.用前面生成的點(diǎn)和 id生成多項(xiàng)式曲線：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個(gè)秘密共享份：(,())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作為最終生成的秘密共享份

重構(gòu)數(shù)據(jù)時(shí)，從各個(gè)存儲(chǔ)點(diǎn)獲得秘密共享份，從中選取k個(gè)秘密共享份 Di。然后構(gòu)造出多項(xiàng)式曲線：

容易得知，改進(jìn)后方法的每份秘密共享份iD的大小約為D的 1k? 分之一。對(duì)于一個(gè)(,)kn的秘密共享來(lái)說，改進(jìn)后的秘密共享方法生成的數(shù)據(jù)大小僅為：

從而很好地節(jié)省了存儲(chǔ)空間。

3 實(shí)驗(yàn)結(jié)果

由于實(shí)驗(yàn)中的傳感器數(shù)目不是很大，我們選取比較小的n和k。如圖3所示，選取(2，3)、(3，6)、(4，9)、(5，10)、(7，12)作為秘密共享點(diǎn)，圖3中顯示了利用(n，k)秘密共享每加密 1KB數(shù)據(jù)所消耗的時(shí)間。其中 DS線表示的是采用Shamir秘密共享方案加密算法得出的數(shù)據(jù)；而 DES線表示的是采用改進(jìn)后的 Shamir秘密共享方案加密算法所得的數(shù)據(jù)。圖4表示的是1KB數(shù)據(jù)經(jīng)過加密后產(chǎn)生的n份秘密共享份的總大小。

從圖3和圖4可以看出，在n，k取值比較小的情況之下，兩種算法加密數(shù)據(jù)所消耗的時(shí)間相差不大，但總的分發(fā)數(shù)據(jù)有了很大的減少。這說明DES方案加密有較高的存儲(chǔ)效率。

圖3 每KB數(shù)據(jù)加密所用時(shí)間

圖4 1KB數(shù)據(jù)加密后分發(fā)數(shù)據(jù)總大小

4 結(jié)束語(yǔ)

本文針對(duì)Shamir秘密共享加密方案進(jìn)行了改進(jìn)，提出了一種效率較高的分布式存儲(chǔ)方法，使得數(shù)據(jù)得到加密的同時(shí)又節(jié)省了存儲(chǔ)空間，具有一定的容災(zāi)能力。但在提升存儲(chǔ)效率的同時(shí)會(huì)稍微加大用于加密的計(jì)算開銷，這相比于節(jié)省的存儲(chǔ)空間來(lái)說是值得的。尤其對(duì)于實(shí)際應(yīng)用中存儲(chǔ)節(jié)點(diǎn)比較少的情況下能達(dá)到很好的效果。本文的一些細(xì)節(jié)還可以進(jìn)一步研究，如數(shù)據(jù)如何分發(fā)到各存儲(chǔ)節(jié)點(diǎn)更節(jié)能等。下一步將繼續(xù)研究，以求更好改善分布式存儲(chǔ)方法的性能。

[1]孫利民,李建中,陳渝等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社.2005.

[2]方紅萍,方康玲.無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)策略研究綜述[J].計(jì)算機(jī)工程與設(shè)計(jì).2010.

[3]梁小滿,馬行坡.無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)技術(shù)研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究.2009.

[4]王剛,黃劉生,楊振國(guó)等.無(wú)線傳感網(wǎng)絡(luò)中的存儲(chǔ)節(jié)點(diǎn)配置[J].小型微型計(jì)算機(jī)系統(tǒng).2010.

[5]畢學(xué)軍,楊朝紅.無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)存儲(chǔ)和索引技術(shù)[J].計(jì)算機(jī)工程.2009.