無線傳感器網絡中一種分布式安全存儲方案*

曾新革，馬 征，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.