無線傳感器網(wǎng)絡(luò)中一種分布式安全存儲方案*

曾新革，馬 征，2，王國軍*

(1.中南大學(xué)信息科學(xué)與工程學(xué)院，長沙 410083;2.湖南大學(xué)信息科學(xué)與工程學(xué)院，長沙 410082)

無線傳感器網(wǎng)絡(luò)是由大量傳感器節(jié)點通過無線通訊自組織形成的網(wǎng)絡(luò)。傳感器節(jié)點由供電模塊，無線通訊模塊，感應(yīng)模塊，計算等模塊構(gòu)成。通過各個模塊間的相互協(xié)作，傳感器節(jié)點可以將無線傳感器網(wǎng)絡(luò)在監(jiān)控區(qū)域中監(jiān)測的數(shù)據(jù)信息發(fā)送給鄰近的傳感器節(jié)點直到特定的用戶。由于傳感器網(wǎng)絡(luò)體型小，價格便宜，部署方便，被廣泛用于智能交通、環(huán)境監(jiān)控、火山監(jiān)測、深海探測、敵情偵察、智能衣服等科學(xué)，醫(yī)學(xué)和軍事應(yīng)用［1－3］。

但由于無線傳感器網(wǎng)絡(luò)處開放的無線環(huán)境中，很容易被竊聽和破壞，并且節(jié)點能量有限，會由于能量的耗盡而失效。如何構(gòu)建安全的數(shù)據(jù)存儲方案，有效地保證無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)的存儲有效和存儲安全，不被竊取和惡意篡改，甚至能在即使有少許節(jié)點失效的情況仍能恢復(fù)數(shù)據(jù)是一個重大的課題。本文將提出一種以數(shù)據(jù)為中心的分布式存儲方案，在保證數(shù)據(jù)安全的同時，有效地節(jié)省存儲空間。

本文將在第1部分介紹相關(guān)工作，接著在第2部分提出網(wǎng)絡(luò)模型，再著在第3部分描敘提出的方案，然后在第4部分對方案進(jìn)行實驗的模擬和分析。最后第5部分對全文進(jìn)行總結(jié)。

1 相關(guān)工作

傳感器網(wǎng)絡(luò)數(shù)據(jù)的存儲主要分為兩大類。一類是將數(shù)據(jù)通過匯聚節(jié)點(Sink)發(fā)送到外部網(wǎng)絡(luò)進(jìn)行存儲，即外部存儲。另一類是內(nèi)部存儲，即將數(shù)據(jù)存儲在傳感器網(wǎng)絡(luò)內(nèi)部。本文所要討論的屬于內(nèi)部存儲。

內(nèi)部存儲又分為集中式的存儲和分布式的存儲:

集中式的存儲是將傳感器網(wǎng)絡(luò)中生成的數(shù)據(jù)全部存于中心節(jié)點。中心節(jié)點一般為匯聚節(jié)點Sink，或Mobile Sink［4］。雖然在傳感器網(wǎng)絡(luò)中認(rèn)為Sink節(jié)點具有很強的能力和完善的保護(hù)措施，能完全保證存儲于其上的數(shù)據(jù)安全。但集中式的存儲中Sink既要存儲大量的數(shù)據(jù)又要處理所有用戶的查詢，會造成Sink成為網(wǎng)絡(luò)的瓶頸［1，5］。集中式存儲中如果中心節(jié)點失效，那么全部的數(shù)據(jù)會丟失。同時由于節(jié)點都要將數(shù)據(jù)發(fā)送到中心節(jié)點，所以收集數(shù)據(jù)時開銷大，容錯性差。

分布式的存儲，有本地存儲和以數(shù)據(jù)為中心的存儲。本地存儲是傳感器節(jié)點存儲自己產(chǎn)生的數(shù)據(jù)，或者通過其他方法將數(shù)據(jù)隨機地分發(fā)到鄰近的傳感器節(jié)點進(jìn)行存儲［6－7］。本地存儲的方法在存儲數(shù)據(jù)的時候不需要消耗額外的通信能量，但查詢數(shù)據(jù)將耗費大量的通信能量。

而以數(shù)據(jù)為中心的分布式存儲近年來越來越受到關(guān)注。以數(shù)據(jù)為中心的存儲是在感知數(shù)據(jù)不需要被及時查詢到的網(wǎng)絡(luò)中，根據(jù)需要存儲的數(shù)據(jù)內(nèi)容的特點來將數(shù)據(jù)存儲到相應(yīng)的節(jié)點以便于更好地查詢［8］。在感知數(shù)據(jù)量大，感知數(shù)據(jù)增加的速度大于查詢數(shù)據(jù)的速度為特點的傳感器網(wǎng)絡(luò)，以數(shù)據(jù)為中心的存儲方案有更高的性能。

分布式存儲可以很好地解決集中式存儲中儲數(shù)據(jù)的中心節(jié)點會成為網(wǎng)絡(luò)瓶頸的問題，也避免了中心節(jié)點失效而造成數(shù)據(jù)全部丟失的危險。關(guān)于本地存儲的安全的研究已有不少，如文獻(xiàn)［9－11］，但以數(shù)據(jù)為中心的存儲安全的研究較少。文獻(xiàn)［9－11］提出將數(shù)據(jù)通過Shamir Secret Sharing將數(shù)據(jù)分成許多共享份存于鄰居節(jié)點，只需要獲得這些共享份中的一部分共享份就可以獲取出原來數(shù)據(jù)的存儲方法來提高數(shù)據(jù)的可靠性。但他們都是將數(shù)據(jù)存儲于鄰居節(jié)點，并不是基于以數(shù)據(jù)中心的傳感器網(wǎng)絡(luò)，因此存儲和查詢的效率都不高。文獻(xiàn)［9－10］的分布式存儲方案中每個共享份和原來的數(shù)據(jù)大小相等，多份共享份就有多份冗余，因此會大量消耗存儲空間。而文獻(xiàn)［11］提到的加密方案減小了存儲空間，但他沒有具體實現(xiàn)，且用的代數(shù)簽名(Algebraic Signature)進(jìn)行認(rèn)證并不能很好地保證數(shù)據(jù)的完整性。因為構(gòu)造兩個具有相同代數(shù)簽名的數(shù)據(jù)并不難，且他不能很好的預(yù)防節(jié)點偽造數(shù)據(jù)。因此，本文基于以上問題提出了基于數(shù)據(jù)為中心的分布式存儲方案。

2 網(wǎng)絡(luò)模型

2.1 網(wǎng)絡(luò)模型

本文采用的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。擁有大量的資源有限的普通傳感器節(jié)點，普通傳感器節(jié)點在部署的區(qū)域內(nèi)監(jiān)聽并生成數(shù)據(jù)，如感知溫度，壓力，濕度等。生成的原始數(shù)據(jù)記為D。以及少量的資源富有的存儲節(jié)點Storage Node，主要是存儲容量大。每個存儲節(jié)點和普通節(jié)點都有自己唯一的ID。分別用v和s來表示普通節(jié)點和存儲節(jié)點。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)

網(wǎng)絡(luò)還包含一個Sink節(jié)點，用來處理用戶的查詢和從存儲節(jié)點上獲取數(shù)據(jù)。存儲節(jié)點位于網(wǎng)絡(luò)比較中心的位置，這樣普通傳感器節(jié)點生成的數(shù)據(jù)發(fā)送到存儲節(jié)點時候會比較節(jié)能［12］。Sink位于網(wǎng)絡(luò)的中心，能更好的均衡各方向存儲節(jié)點或普通節(jié)點與Sink節(jié)點進(jìn)行通訊時所帶來的開銷。

2.2 安全假設(shè)

Sink節(jié)點是鏈接外界網(wǎng)絡(luò)和無線網(wǎng)絡(luò)的樞紐。我們認(rèn)為其是能力強大的，能承受任意安全攻擊，也就是Sink節(jié)點總是可信的。

攻擊主要來自:①普通節(jié)點和存儲節(jié)點可能被惡意的敵方損壞。②攻擊者可能進(jìn)行被動攻擊，例如監(jiān)聽數(shù)據(jù)，從而知道數(shù)據(jù)的發(fā)送和傳輸或數(shù)據(jù)的內(nèi)容。③敵方也可能主動攻擊，攻陷某些節(jié)點包括普通節(jié)點和存儲節(jié)點，攻陷后，敵方可能竊取，偽造，篡改數(shù)據(jù)，或給查詢返回錯誤的結(jié)果。

傳感器網(wǎng)絡(luò)中每個普遍節(jié)點和Sink間共享密鑰kv。每個存儲節(jié)點和Sink間共享密鑰ks。同時每個普通節(jié)點和每個存儲節(jié)點間共享密鑰kvs。

2.3 以數(shù)據(jù)為中心的存儲

當(dāng)普通傳感器將生成數(shù)據(jù)D時。運用我們將要提到的存儲方案將數(shù)據(jù)加密成n個共享份(D1，D2，D3，…，Dn)，然后利用單向的 Hash 函數(shù)和密鑰kv生成消息驗證碼。將此共享份和消息驗證碼和節(jié)點編號等用生成數(shù)據(jù)的節(jié)點與相應(yīng)的存儲節(jié)點間的密鑰進(jìn)行加密。并將每份加密的共享份分發(fā)到對應(yīng)的存儲節(jié)點上去。這些對應(yīng)的存儲節(jié)點是通過不同的GHT映射來確定的。發(fā)送的數(shù)據(jù)如下:

其中v為生成此數(shù)據(jù)的傳感器節(jié)點的編號。seqno是用于標(biāo)識此數(shù)據(jù)的唯一序列號。MACkv(Di)是將共享份Di用單向Hash函數(shù)和密鑰kv生成的消息驗證碼。然后將seqno、共享份和消息驗證碼用v和si間的密鑰kvsi加密后發(fā)送給存儲節(jié)點si。通過加密可以防止敵方竊聽而泄密數(shù)據(jù)內(nèi)容。消息驗證碼可以防止存儲節(jié)點惡意地篡改數(shù)據(jù)或發(fā)送錯誤數(shù)據(jù)。

當(dāng)用戶需要查詢時，用戶向Sink發(fā)出查詢數(shù)據(jù)請求，如圖2所示。Sink收到用戶查詢請求并驗證用戶的權(quán)限。驗證成功后，Sink向存儲節(jié)點發(fā)送查詢請求，可以采用基于隱私保護(hù)的策略查詢［13］或基于安全區(qū)域的查詢［14］。存儲節(jié)點收到Sink發(fā)來的查詢請求，會將相應(yīng)的數(shù)據(jù)，即存儲在n個存儲節(jié)點上的n個秘密共享份發(fā)回給Sink。Sink首先驗證MACkv(Di)是否正確來驗證各份共享份是否數(shù)據(jù)完整。從完整的共享份中選取不小于閾值k(1≤k≤n)的份數(shù)進(jìn)行重構(gòu)出數(shù)據(jù)。任意小于k的份數(shù)將不能重構(gòu)出數(shù)據(jù)。其中n和k是系統(tǒng)設(shè)置的參數(shù)，用于控制分布式的數(shù)據(jù)的容災(zāi)性。文中提到的各標(biāo)記及其意義如表1所示。

圖2 用戶查詢

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

3 存儲方案

將生成的數(shù)據(jù)D加密成n個共享份，文獻(xiàn)［8－9］提出了基于SSS(Shamir’s Secret Sharing)的加密方法。文獻(xiàn)［10］雖然沒說用SSS加密，但其采用的方法就是SSS，且提供了具體實現(xiàn)和分析。

SSS是基于拉格朗日插值的加密算法。SSS的加密方法是通過構(gòu)造一條k－1次曲線F(x)，并把數(shù)據(jù)D做為其常數(shù)項，選取曲線上的n個點作為秘密共享份即加密后的結(jié)果，然后將共享份分發(fā)給n個存儲節(jié)點。從線性代數(shù)的知識容易得知，只要獲取k個共享份也就是曲線上的k個點就可以重構(gòu)出此曲線方程，從而得出數(shù)據(jù)D。

SSS方案中每份秘密共享份和曲線方程的常數(shù)項即數(shù)據(jù)D屬于同一個域?p，所以共享份的大小和原數(shù)據(jù)的大小相同［15］，即|Di|=|D|。一個(k，n)的秘密共享，經(jīng)過加密后數(shù)據(jù)總大小為:

即所產(chǎn)生的最終數(shù)據(jù)將是原數(shù)據(jù)的n倍，存儲效率不高。因此我們對之改進(jìn)，減小每份秘密共享份的大小。本文提出了迭代的SSS分布式存儲方案和基于Reed Solomon Code的存儲方案。

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

RSS方案是將數(shù)據(jù)D分成k－1份，每份標(biāo)識為di。di的大小為D的k－1分之一。然后用每份數(shù)據(jù)di在小的域?p中構(gòu)建曲線生成共享份。共享份的大小和di的大小相同。從而節(jié)省每份共享份的大小。最終的曲線的構(gòu)造是用SSS方案迭代構(gòu)造而成。

(1)將D分成k－1 份，分別為d1，d2，…dk－1。簡單的分法是假設(shè)D有m位，取前m/(k－1)位作為d1，第二個m/(k－1)位作為dn，直達(dá)dk－1。如果k=1，意味著只需要1份共享份就可以恢復(fù)出數(shù)據(jù)。那么直接拷貝n份D作為D1，D2，…，Dn。例如D的大小有40位，如果k=5，也就是說要將數(shù)據(jù)D分成四份，每份10位。于是將D的前10位作為d1，D的第10到20位作為d2，D的第20到30位作為d3，最后10位作為d4。

(2)迭代構(gòu)造k－1次曲線。

將數(shù)據(jù)分成k－1份后，選取一個大的素數(shù)p使得p＞max(dmax，n)，不等式中dmax=max(di)。在?p中任意選取1個數(shù)a，把d1和a分別作為一次多項式的一條一次項系數(shù)和常數(shù)項系數(shù)即SSS方案構(gòu)造一次多項式曲線F1(x)=ax+d1。然后從這條曲線上選取兩點=F1(1)=F1(2)。這就相當(dāng)于SSS將d1分成兩份秘密共享份。接著用和d2分別作為二次項系數(shù)，一次項系數(shù)和常數(shù)項的SSS方案構(gòu)造一條二次多項式曲線F2(x)=2++d2。又在這條二次曲線上選取三個點=F2(1)，=F2(2)和=F2(3)，相當(dāng)于d2的三個共享份，同時這三個共享份包含了d1的信息，所以生成和后將刪除和。接著又用和d3構(gòu)造一條三次多項式曲線F3(x)=。如此選取點，構(gòu)建曲線，刪除前面一次生成的點，再在新曲線上選取點，迭代直到k－1。此時由前面選取的k－1個點和dk－1，最后生成一條k－1次多項式曲線

(3)然后在此曲線上選取n個點生成

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

加密的算法如下:

重構(gòu)數(shù)據(jù)時，從各個存儲節(jié)點獲得秘密共享份，從中選取k個秘密共享份Di。然后構(gòu)造出多項式曲線:

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

RSS迭代的方法雖然能節(jié)省存儲空間，但增加了計算量。利用Reed Solomon Code的秘密共享方法，將數(shù)據(jù)D直接分成k份作為一條k－1次曲線的系數(shù)來構(gòu)造曲線能一次構(gòu)造出曲線，從而節(jié)省計算量。同時也能使得共享份的大小和di大小相同。

(1)將D分成k份，分別為d1，d2，…dk。

(2)構(gòu)造k－1次曲線。

把d1，d2，…dk作為系數(shù)構(gòu)造曲線

(3)從上面選取n個點作為共享份。

具體算法如下:

也很容易得知RSC方法的每份秘密共享份Di的大小為|D|的k分之一。對于一個(k，n)的秘密分享，改進(jìn)后的秘密共享方法生成的數(shù)據(jù)大小為:

4 實驗分析

網(wǎng)絡(luò)中各節(jié)點會由于能量耗盡或被破壞而失效。假設(shè)存儲節(jié)點的失效率為p。在(k，n)分布式存儲方案中。SSS，RSS和RSC方案都需要失效的節(jié)點不多于n－k才能恢復(fù)出數(shù)據(jù)。所以運用(k，n)分布式方案后的數(shù)據(jù)丟失率為P。

設(shè)定網(wǎng)絡(luò)中有100個存儲節(jié)點，節(jié)點的失效率為p，其中的失效率意味著返回錯誤的共享份或不返回共享份。對不同的(k，n)情況下數(shù)據(jù)的從獲取的共享份不能構(gòu)建出原來數(shù)據(jù)的概率(50次平均后的結(jié)果)如圖3所示。其中的(1，1)曲線相當(dāng)于把原始數(shù)據(jù)直接存儲。從圖中容易知道，在節(jié)點失效率不高的情況下，分布式的存儲方案都能很好的減少數(shù)據(jù)的丟失率。而在節(jié)點失效率高時，意味著此時網(wǎng)絡(luò)已經(jīng)接近生命周期末期，快鄰近死亡了。此時(k，n)分布式存儲方案減小丟失率成效不明顯。是由于多份數(shù)據(jù)的存儲會帶來多份數(shù)據(jù)的失效率，而失效率越高，能保障至少k份共享份完整的概率急劇變小。

圖3 數(shù)據(jù)丟失率

網(wǎng)絡(luò)中普通節(jié)點生成數(shù)據(jù)，假設(shè)原始的數(shù)據(jù)包大小為64 bit。SSS，RSS和RSC各個方案加密后的數(shù)據(jù)大小和加密時間分別如圖4和圖5。RSS方案中共享份的大小僅為SSS方案中共享份大小的k－1分之一。圖4中顯示了RSS方案在存儲上優(yōu)于SSS方案，但從圖5可看出RSS需要消耗更多的計算開銷。這是由于其迭代多次才能構(gòu)造曲線，所以開銷大。

圖4 加密后數(shù)據(jù)的大小(原始大小為64 bit)

圖5 每加密一個數(shù)據(jù)包用的時間

而RSC方案由于每份共享份的大小為原數(shù)據(jù)的1/k。所以所有共享份總大小比RSS中共享份的總大小要小。所以在需要的存儲上小于RSS方案且遠(yuǎn)遠(yuǎn)小于SSS方案，同時能一次構(gòu)造出曲線，因而加密所消耗的計算時間和SSS方案差不多，且低于RSC方案的加密時間。很好的驗證了RSC的存儲方案能有效地節(jié)省存儲空間，同時保持較小的計算量。

對于查詢開銷，由于查詢的方式與SSS的查詢策略的方法沒有太大區(qū)別，只是節(jié)省了查詢到的結(jié)果的大小，能節(jié)省一點開銷。

5 結(jié)束語

本文提出了一種高效的分布式數(shù)據(jù)存儲方案，使得加密數(shù)據(jù)的同時又能節(jié)省存儲空間，并且具有一定的容災(zāi)能力。雖然在提升存儲效率的同時稍微增加了用于加密的計算開銷，但計算量是較小的，相比于節(jié)省的存儲空間來說是值得的。尤其對于實際應(yīng)用中n比較小的情況下能達(dá)到很好的效果。值得指出的是，本文的某些細(xì)節(jié)還可以進(jìn)一步進(jìn)行探討，比如采用什么樣的方案數(shù)據(jù)發(fā)到各存儲節(jié)點更節(jié)能等。

［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］陳積明，林瑞仲，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)通信體系研究現(xiàn)狀及展望［J］.傳感技術(shù)學(xué)報，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］孫利民，陳渝， ，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，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，F(xiàn)rank 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］王先峰，項軍，胡斌杰.一種無線傳感器網(wǎng)絡(luò)能量模型的評估及改進(jìn)［J］.傳感技術(shù)學(xué)報，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.