兩層傳感器網絡中一種高效的加密數據條件聚合協議研究

李睿，林亞平，李晉國

(湖南大學 信息科學與工程學院，湖南 長沙 410082)

1 引言

傳感器網絡為環境和移動目標的監測及數據處理提供了一種非常經濟的分布式解決方案[1,2]，兩層結構傳感器網絡(two-tired sensor networks)已被認為是無線傳感器網絡未來的發展趨勢[3～6]。圖 1所示是一個典型的兩層傳感器網絡。在該網絡中包含大量的資源受限的傳感器節點以及數量相對較少的存儲節點。傳感器節點處在網絡中的下層，負責收集監測目標數據，并周期性地將收集到的數據提交給附近的存儲節點。存儲節點處在網絡中的上層，為傳感器節點提供數據存儲服務的同時也負責處理sink節點發來的查詢。

圖1 兩層結構的傳感器網絡的體系結構

在網絡中，傳感器節點收集了大量監測目標的細節數據，而用戶查詢結果往往需要對滿足查詢條件的細節數據進行綜合計算后得出。例如，用戶可能對一個用于環境監測的傳感器網絡提出如下查詢請求:

select average humidity where time ∈ [11:00pm- 2:00 am]and temperature ∈[20℃～25℃]and sense area is A1。

該查詢要求計算滿足時間、溫度和感知區域條件下濕度的平均值。如果將滿足條件的所有細節數據全部發送到sink節點后再進行計算，則在傳感器網內會產生大量的數據流。為了減小網內數據流，降低節點的能耗，研究者提出了數據聚合（data aggregation）[7,8]的概念。數據聚合運算通過網內節點對來自不同數據源的數據進行提前綜合，以此來去除數據冗余，減小數據發送量，達到節能和延長網絡壽命的目的。由于傳感器節點計算能力的受限，傳統傳感器網絡中的數據聚合往往只能針對一個周期內傳感器節點收集的所有數據進行，而沒有考慮對跨周期數據以及通過條件篩選后的數據進行聚合。在兩層傳感器網絡中，存儲節點收集了附近傳感器節點的多個周期內數據，并且具有相對豐富的計算資源，為復雜聚合運算提供了條件。為區別傳統傳感器網絡下的數據聚合運算，本文稱對滿足查詢條件下數據的某一個屬性值進行聚合的運算為條件聚合運算。在兩層傳感器網絡中，存儲節點雖然比傳感器節點具有更豐富的能量，但它們需要承擔更多的計算任務，并且一個存儲節點的失效會導致所在傳感器區域成為檢測盲區。因此，研究兩層傳感器網絡中的條件聚合對延長網絡的生命周期具有非常重要的意義。

然而，存儲節點為條件聚合提供了條件的同時也帶來了新的挑戰。由于其在網絡中扮演的關鍵角色導致在敵對環境下更容易招致攻擊。一個妥協的存儲節點會泄漏存儲在該存儲節點上的敏感數據。如何在兩層傳感器網絡上設計一種安全條件聚合協議，使存儲節點在不泄漏傳感器采集的敏感數據的情況下進行聚合是一項挑戰性的任務。其挑戰性表現在以下幾個方面:第一，為了防止敏感數據的泄漏，需要對傳感器節點采集的數據和 sink發送來的查詢條件進行加密處理，因此，需要解決在不知道數據真實值和查詢條件真實值的情況下實現查詢處理；第二，要解決對滿足查詢條件的加密數據在不解密的情況下實現聚合運算；第三，為了對傳感器采集數據的某一個屬性進行聚合，需要對屬性值單獨進行加密，消耗更多空間，因此要解決傳感器節點和存儲節點之間的數據通信開銷問題。

安全條件聚合包含安全查詢和安全聚合兩方面工作。安全查詢獲得滿足條件的細節數據；安全聚合對滿足條件的細節數據進行聚合。目前還沒有相關工作研究兩層傳感器網絡當中的條件聚合查詢。與本文最相關的工作是兩層傳感器網絡中的安全范圍查詢[9～12]和傳統傳感器網絡中的數據聚合[13～15]。

在兩層傳感器網絡中的安全查詢方面，最具代表性的工作是Chen&Liu提出的SafeQ[12]安全查詢協議。SafeQ考慮的安全模型是傳感器和sink是安全的，攻擊者只妥協存儲節點。在他們設定的模型下，SafeQ具有優良的性能，特別是在多維數據的情形。但如果攻擊者妥協了一個存儲節點的同時再妥協該存儲節點所在單元的一個傳感器節點，則所有存儲在該妥協存儲節點上的數據都會泄露。其原因如下:在 SafeQ中，同一個單元內的所有傳感器共享一個密鑰用于數據的編碼，并且每一個傳感器采集的數據按照有序的方式組織。因此，攻擊者妥協一個傳感器后可以獲得共享密鑰，并控制妥協的傳感器按照需要產生數據，通過二分查找法可以查找出所有其他傳感器采集的數據值。文獻[9～11]是基于桶的隱私和完整性認證方法。桶的方法最主要缺陷有兩個:①攻擊者可以較容易估計出傳感器檢測區域數據的分布情況，這樣部分暴露了敏感信息；②當傳感器采集的數據集中在少數的幾個桶中時，傳感器和存儲節點都會消耗過多的能量和空間。同時，基于桶的方法不適合本文的條件聚合查詢，因為往往一個桶中只有部分數據滿足查詢條件。

在傳統無線傳感器網絡中的安全聚合方面，最具代表性的工作是 Przydatek等人提出的 SIA（secure information aggregation）聚合機制[13]。在SIA機制中，傳感器節點通過共享密鑰對數據進行加密后傳給匯聚節點，匯聚節點用共享密鑰解密后進行聚合，并將聚合后的結果重新進行加密傳給上層匯聚節點。SIA能有效防止外部攻擊者的竊聽，但無法阻止內部妥協的匯聚節點對數據隱私性的泄露。針對這一問題，Castelluccia等人采用同態加密技術實現對密文數據的聚合[15]。由于傳感器節點本身資源受限，傳統的無線傳感網絡中的聚合只考慮將傳感器節點在一個周期內所采集的所有數據進行聚合，沒有考慮跨周期數據的聚合以及對滿足條件的數據進行聚合。

為此，本文提出了一種基于兩層傳感器網絡的安全條件聚合運算協議。該協議包含兩部分:在不泄漏數據隱私的情況下實現范圍查詢以及對符合查詢條件的數據進行聚合。為了在保護數據隱私的情況下實現查詢，本文采用前綴成員確認技術和布魯姆過濾器相結合的辦法對數據進行編碼，實現了存儲節點在不知道數據真實值和查詢條件真實值的情況下進行查詢處理；為了在保護數據隱私的情況下實現數據聚合，采用同態加密技術，使數據在不解密的情況下可以進行相關的聚合運算。另外，針對經過編碼和加密后的數據所占空間較大的問題，在分析傳感器采集數據更新率的基礎上提出了一種基于代碼表的數據壓縮表示與傳輸方法。該方法將傳感器已經計算過的編碼和加密結果保存在代碼表中，并且將該代碼表同步到存儲節點上，當重復數據出現時，只需要傳輸相應的代碼，存儲節點根據代碼在本地代碼表中檢索出相應的編碼和加密結果。分析和實驗結果證實了該方法能有效減少數據通信量以及避免傳感器節點的重復計算。

本文的主要貢獻如下:①在兩層傳感器網絡當中提出了隱私保護的條件聚合問題；②提出了一種基于前綴編碼和布魯姆過濾器相結合的數據隱私編碼方案；③提出了一種基于代碼表的數據壓縮表示和傳輸方法。

2 模型

2.1 系統模型

如圖1所示，一個典型的兩層結構傳感器網絡包括3種類型的節點:傳感器、存儲節點和 sink。傳感器節點是一些資源受限的節點，在網絡中采集數據并周期性地將采集到的數據提交給附近的存儲節點。存儲節點相比傳感器節點具有更豐富的資源，在網絡中存儲節點存儲傳感器發送過來的數據，并根據存儲在其上的數據處理sink節點發送過來的查詢。Sink節點是用戶訪問傳感器網絡的接入點，負責處理用戶提出的問題。當接收到用戶的一個問題后，Sink首先將該問題改寫成符合網絡特點的查詢，并將這些查詢發送給與該問題相關的存儲節點。收到存儲節點發回的查詢結果后，Sink將查詢結果進行綜合得到最終的問題答案發送給用戶。

2.2 基本假設

對于上述兩層傳感器網絡，本文做出如下假設。

1) 傳感區域分成很多個單元(cell)，一個單元中有多個傳感器節點和一個存儲節點。每一個傳感器節點和存儲節點知道節點本身的位置及其所在的單元。所有的傳感器在部署前分配一個唯一的ID。

2) 所有傳感器與存儲節點均是松散同步，本文將時間劃分成互不重疊的周期，每個周期內節點采樣的次數為n次，傳感器sη所采集的數據用三元組(η, t,{,… , dn})表示，其中，t表示周期序號，… ,dn表示傳感器采集的數據；傳感器在周期末向所在單元中的存儲節點發送數據。

3) 所有傳感器與 sink共享一個相同單向散列函數 H(·)；每一個傳感器節點預置一個不同的編碼布魯姆過濾器（包括散列表長度，散列函數個數以及散列函數本身）；每一個傳感器節點和sink共享一個密鑰，如傳感器sη與sink共享的密鑰為kη。

2.3 威脅模型

本文研究如何防止攻擊者從傳感器網絡中獲得敏感數據信息而破壞數據的隱私性。在很多實際應用中，保護敏感數據隱私性是一個關鍵任務，如在用于監測健康狀況的傳感器網絡中，個人健康數據的保護就顯得非常重要。

假設sink是可信的，存儲節點可能被妥協，少量傳感器節點也可能被妥協。另外，本文與文獻[16]一樣采用半可信[17]威脅模型，即妥協的存儲節點在數據處理過程依然嚴格遵守協議，但試圖破壞數據的隱私性。本文不考慮妥協的傳感器節點偽造自己的數據。主要有兩個原因:①很難阻止妥協的傳感器偽造自己的數據；②當限制每一個傳感器在一個周期內發送的數據量時，少量傳感器妥協對最終查詢結果的影響較小，文獻[18，19]指出，如果傳感器節點只偽造自己的數據，查詢結果離真實結果的偏差不會太大。

3 數據加密方案

文獻[16]對在兩層傳感器網絡當中的最大、最小值的聚合問題進行了探討。本文研究平均值、方差以及求和等聚合運算在兩層傳感器中的實現。為了保護數據的隱私性，存儲節點需要在密文的情況下對數據進行聚合。同態加密中對密文的某種特定的線性運算與對明文另一種特定的線性運算是等價的，它可以用來實現密文的聚合運算，因此本文采用同態加密技術對需要進行聚合的數據的屬性值進行加密。

同態加密的思想如圖2所示。用C=Enc(K，V)表示用密鑰 K對明文 V加密得到密文 C，令C1=Enc(K1，V1)，C2=Enc(K2，V2)，根據同態性質有C1+C2=Enc(K1+K2，V1+V2)。根據這一性質，第三方可以對密文數據進行運算得到所需要的運算結果。

圖2 同態加密運算的基本思想

由于無線傳感網絡中傳感器節點資源受限，因此進行同態加密時運算不能太復雜。文獻[20]給出了一種輕量級加法同態加密算法，該算法基于模運算對加法的可分配性性質，即:當a+b＜M時，有(a mod M)+(b mod M)=(a+b) mod M。該同態加密算法能滿足本文的需求。下面簡述該同態加密算法的基本原理以及密文下的求和、均值和方差等聚合運算的具體實現以及相應的解密過程。

該同態加密運算的加、解密基本思想為:選取一個大整數M以及密碼K(K＜M)，對明文p計算C=(p+K) mod M作為其加密結果。由于密鑰K以及M的秘密性，攻擊者在只已知密文的情況下無法破解出明文。要進行解密時，計算(C?K) mod M得到相應的明文。例如，密鑰K=28，明文p=7，大整數M=30，當要加密p時，計算C=(p+K) mod M= (7+28)mod 30=5。要解密C 時，計算(C?K) mod M =(5?28)mod 30=7，得到明文。

由于模運算滿足對加法的分配律，因此該加密算法滿足加法同態。假設對明文 p1和 p2進行加密的密鑰分別為K1和K2，其加密數據的和與求和后進行加密的結果在模運算下一致，即滿足:C=(C1+C2) mod M= (Enc(K1, p1)+ Enc(K2, p2)) mod M = Enc(K1+K2, p1+p2) mod M（注:第三方進行加密數據的運算時，只需要計算Enc(K1, p1)+ Enc(K2, p2)的結果，解密方已知M和密鑰可以正確進行解密運算）。當 p1+p2＜M 時，有(p1mod M)+(p2mod M))mod M=(p1+p2) mod M，因此要正確解密出p1+p2，要求選取的M比參加運算的明文的總和大。當參加同態加密運算的數據個數為n，其中最大的元素為Vmax，一般要求M＞nVmax。

該同態加密不支持除法運算，因此計算數據的平均值時，需要將數據進行解密后除以參加運算的數據個數得出。接下來討論方差的計算。方差的計算公式為

因此，為了計算方差，進行同態加密時，需要計算出明文的平方值，然后分別對明文和明文的平方值采用同態加密算法進行加密。當參加同態加密運算的數據個數為n，其中，最大的元素為Vmax，進一步要求M＞n。n為可支持的參加同態計算的密文個數，該參數將在分析部分和實驗部分進行討論和實驗。當要求參加聚合運算的加密數據個數超過n時，將參加運算的數據分劃分成最少的子集，使得每一子集中所含元素個數不超過n，然后分別進行計算，將結果發送給解密方，解密方進行解密后獲得這些子集的解，再進行后續運算。

在兩層傳感器網絡中，傳感器節點和sink共享加密密鑰。傳感器將數據進行加密后發送給存儲節點，存儲節點對滿足條件的所有傳感器節點發送的數據進行聚合運算，并將運算的結果發送給sink。Sink根據參加聚合運算的數據個數以及數據提供者的 ID進行解密得到相應的明文。因此，數據加密方是傳感器節點，數據解密方是sink節點，密文的運算在存儲節點上進行。

4 數據隱私查詢編碼方案

數據的條件聚合是針對滿足條件的數據進行聚合，采用同態加密可以在不解密數據的情況下實現數據的聚合運算，如何在不知道數據真實值的情況下判斷數據是否滿足相應的查詢條件是一個難點。本文中考慮了一個更為復雜的情況，也就是攻擊者妥協存儲節點后，可能還會妥協一個或者幾個傳感器節點，妥協后的傳感器節點不能威脅其他傳感器節點采集的數據。

本文數據編碼的基本思想是:假設傳感器sη在周期t內采集的數據是{d1,d2,…,dn}。sη對數據采用與 sink共享的密鑰kη進行加密后，應用 2個函數H(·)和 Xη(·)對數據進行編碼，如數據 dj的編碼結果為: Xη(H( dj))。其中， H(·)是一個單向函數，為所有傳感器節點共享；Xη(·)是sη獨享的一個秘密函數。在一個周期結束時，sη將加密和編碼后的數據一起發送給存儲節點。當需要進行一個范圍查詢{t，[a，b]}時，Sink應用另外一個函數 M (·)對查詢范圍進行處理，得到 M ([a, b])。為防止妥協的傳感器節點偽造查詢條件，sink對查詢條件{t, M ([a, b ])}進行數字簽名后發送給相應的存儲節點。當存儲節點需要對傳感器節點sη提交的數據進行查詢時，存儲節點將 sink發來的查詢條件{t, M ([a, b ])}發送給傳感器節點sη。傳感器節點sη確認查詢條件由sink產生后，采用秘密函數 Xη(·)將該查詢條件轉換成{t, Xη(M ([a, b ]))}并發送給存儲節點。存儲節點利用其上面的查詢函數 Q(·)實現對加密的數據進行查詢。這些函數要滿足以下條件:①數據 dj在查詢范圍[a，b]中，當且僅當Q( Xη(B( dj))Xη(M ([a, b ])))為真。該條件保證存儲節點在不知道數據真實值和查詢條件真實值的情況下確定加密數據是否在查詢結果中。②給定Xη(H( dj))和(dj)kη，存儲節點在知道妥協傳感器節點的信息后依然無法計算出數據 dj；同時給定{t, M ([a, b ])}和{t, Xη(M ([a, b ]))}，存儲節點也無法破解 Xη(·)。該條件是保證傳感器節點所采集數據的隱私。③給定 M ([a, b ])，存儲節點和妥協的傳感器節點都不能計算出查詢條件[a，b]。該條件保證查詢條件的隱私性。圖3給出編碼方案的基本思想。

圖3 編碼方案的基本思想

4.1 前綴成員確認

為了實現在存儲節點妥協以及少量傳感器節點妥協情況下能保護數據的隱私性，本文首先將范圍查詢轉換成成員確定。成員確定采用前綴成員技術，該方法在文獻[21]提出，在文獻[22]中成形。前綴成員確認技術的關鍵思想是將判斷一個數據是否在指定的范圍中轉換成判斷一個集合和另外一個集合是否有交集的問題。以下敘述中數字的表示均采用二進制。用{0，1}k{*}w?k表示前面具有k個先導字符“0”或“1”，然后緊跟w?k個“*”的前綴，并稱該前綴為k長度前綴。例如，“1****”是1 長度前綴，該前綴表示的范圍為[1000，1111]。當數據x在一個k長度前綴表示的范圍中，稱x與該前綴匹配。根據前綴的特點，數據x與一個k長度前綴匹配，當且僅當數據x的前k位與該k長度前綴的前k位完全一致。例如，x與1***匹配，則x的第一位必需是1。如果前綴P表示的范圍是前綴Q表示的范圍的子集，稱前綴Q是前綴P的祖先前綴。如前綴 1***是前綴 101*的祖先前綴。如果前綴Q是前綴P的最小祖先前綴，稱前綴Q是前綴P的父前綴。如前綴1***是前綴10**的父前綴。稱包含一個數的所有前綴的集合為該數的前綴科(prefix family)。給定一個數據N，假設該數據采用二進制表示為:b1b2…bw。則該數據的前綴科是一個包含 w+1個前綴的集合:{b1b2…bw，b1b2…bw-1*,…,b1*…*, **…*}。用F(x)表示數x的前綴科。產生一個數據的所有前綴是比較多的。如一個 32位數的前綴科中含 33個前綴，在很多情況下不需要產生所有的前綴。如需要處理的數據在給定的一個前綴表示的范圍內，則所有該前綴的祖先前綴就顯得不重要，因為該前綴表示范圍內的所有數據共享這些祖先前綴。為了減小前綴的數量，定義前綴R下的數據 x的前綴科(prefix family for x under prefix R)。對于數據x，設該數據的前綴科為F(x)，F(x)中所有不是前綴R的祖先前綴的前綴組成的集合稱為數據x在前綴R下的前綴科，記作:FR(x)。

前綴成員確認正是基于以下事實:給定前綴R，任何數據x和前綴P (R是P的祖先前綴)，x在P中，當且僅當P在FR(x)中。為確認一個數據x是否在范圍[a，b]([a，b]是前綴R所確定的范圍的子集)中，首先將范圍轉換成一個最小前綴集合，記作S([a，b])，使得S([a，b])中所有前綴表示的范圍的“并”等于范圍[a，b]。例如，S([10，15])={101*，11**}。計算數據x在前綴R下的前綴科FR(x)。x在范圍[a，b]中，當且僅當 FR(x)∩S([a，b])≠Φ。

接下來討論如何將前綴轉換成數字方便上述集合的運算。本文采用文獻[23]的方法將前綴分別轉換成唯一對應的一個數字。具體方法為:采用數字“1”作為分界符，將前綴前面的“0”或“1”與*分割開，然后將“*”用“0”來表示。例如:前綴1101***，加入分割符后變成:11011***，用0代替*得:11011000。圖4給出了驗證數字2在范圍[0，4]內的過程，給定的前綴R是0***。

圖4 前綴成員確認

4.2 布魯姆過濾器

前綴成員確認技術可將范圍查詢轉換成成員確認。但為一個數字產生的前綴數據很多，直接存儲這些前綴或者簡單對這些前綴進行散列運算會產生兩方面的問題。第一，空間消耗過大；第二，數據的真實值很容易通過查找的辦法揭露出來。因此本文采用布魯姆過濾器來存儲這些前綴。

布魯姆過濾器[24]是一種空間高效的隨機化數據結構，用于元素集合的精簡表示和隸屬關系查詢。標準布魯姆過濾器采用長度為m的比特向量V以及k個相互獨立的散列函數h1，h2，…，hk。當元素s存儲到布魯姆過濾器時，設置V中第h1(s)，h2(s)，…，hk(s)比特值為1。當查詢元素u 是否在布魯姆過濾器中時，檢查V 中第h1(u)，h2(u)，…，hk(u)比特值是否全為 1，如果全為 1，則元素 u以較大概率在S中，如果不全為1，則u不在布魯姆過濾器中。

本文稱具有相同長度比特向量且采用相同的 k個散列函數的布魯姆過濾器為同構布魯姆過濾器。對于同構布魯姆過濾器，定義∩運算。同構布魯姆過濾器的∩運算定義為直接通過布魯姆過濾器的比特向量的邏輯與運算完成，如圖5所示。

圖5 布魯姆過濾器上的交運算

本文采用前綴成員確認技術和布魯姆過濾器相結合的辦法，在數據隱私的情況下判斷數據x是否在指定的范圍[a, b]內。其過程如下:給定前綴范圍R，為數據x產生FR(x)，并對每一個前綴采用單向散列函數 H(·)計算其散列值，然后將散列結果采用布魯姆過濾器存儲。計算S([a, b])，將S([a, b])中的每一個前綴采用散列 H(·)計算其散列值。并對每一個散列結果采用一個單獨的布魯姆過濾器進行存儲，接下來判斷對應S([a, b])的所有布魯姆過濾器中是否至少存在一個布魯姆過濾器是存入FR(x)散列值后的布魯姆過濾器的子集。如果存在，則 x以很大概率在范圍[a，b]內，否則不在該范圍內。對驗證數字2是否在范圍[0，4]內，圖4采用前綴成員確認技術產生了相關前綴。在此結果上，采用本節介紹布魯姆過濾器的辦法進行判斷的過程如圖6所示。

圖6 布魯姆過濾器的成員確認

4.3 數據提交協議

數據提交協議處理傳感器節點如何將采集的數據提交給存儲節點。假設傳感器節點sη在一個周期中產生的數據為: {,… ,dn}，所有的數據都處在范圍 R=[d0，dn+1]內，其中，d0和 dn+1分別代表數據的上屆和下界。所有傳感器和sink均知道范圍R。傳感器sη對收集的數據進行如下處理。

Step1 對每一個數據 dj計算其約束前綴科FR( dj)，對前綴科中的數據進行散列后，為數據 dj構造一個布魯姆過濾器 Bj，將該數據的約束前綴科的散列值存儲在 Bj中。

Step2 sη應用私鑰kη對所有數據進行加密，得到加密結果: {,,… , (dn)kη}。

Step3 sη將加密結果連同編碼結果一起發送給附近的存儲節點。

根據以上敘述，函數H(·)對應傳感器sη的第一步處理的散列方法，即為每一個數據分別計算帶約束前綴集以及將該前綴集進行散列。

Xη(·)傳感器上的秘密布魯姆過濾器中，由于每一個傳感器采用不同的布魯姆過濾器(包括散列表大小，散列函數個數以及不同的帶密鑰散列函數)，存儲節點和妥協的傳感器節點無法根據加密數據(dj)kη和編碼結果 Xη(H( dj))計算出dj。

4.4 查詢協議

查詢協議處理sink節點如何對查詢條件進行編碼，傳感器節點如何對查詢條件進行轉換以及存儲節點如何實現查詢處理。

當需要執行范圍查詢[a，b]時，Sink、存儲節點和傳感器節點分別執行以下步驟來完成該查詢任務。

Step1 Sink計算范圍[a，b]等價的最小前綴集S([a，b])。

Step2 Sink為前綴集 S([a，b])中的每一個前綴p采用共享散列函數計算對應的散列值，將進行散列的結果記作Sh([a，b])。

Step4 Sink將查詢條件{t，Sh([a，b])}進行簽名后發送給存儲節點。

Step5 收到 sink發送來的查詢條件后，當存儲節點要在傳感器節點sη提交的加密數據上執行查詢時，存儲節點首先將查詢條件{t，Sh([a，b])}發送給傳感器節點。sη首先對存儲節點發送來的查詢條件進行認證，確認查詢條件是否由sink產生。當確認查詢條件是由sink產生后，采用其上的秘密布魯姆過濾器為每一個散列結果生成一個布魯姆過濾器，得到新的查詢條件{t, Xη(Sb([a, b]))}，將該查詢條件發送給存儲節點。

Step6 存儲節點根據傳感器節點發送來的查詢條件執行查詢，加密數據(dj)kη在查詢結果中。當且僅當在布魯姆過濾器集合Xη(Sb([a, b]))中存在一個布魯姆過濾器B，使得 Xη(H( dj))∩B=B 成立。

Step7 存儲節點將滿足條件的所有加密數據進行聚合，并將聚合結果發送給sink。

Sink節點當中的秘密函數M (·)對應上述步驟的Step1和Step2。由于散列函數的單向性，攻擊者很難獲得真實查詢條件。存儲節點上的查詢函數對應Step6操作，即判斷其中一個布魯姆過濾器中置“1”的位置是否包含另外一個布魯姆過濾器所有置“1”的位置。

5 基于代碼表的數據壓縮表示及傳輸

為了支持數據的隱私查詢以及對各維的聚合運算，需要對數據不同維上的值進行單獨編碼和加密處理，產生了較大的加密和編碼結果。因此需要研究如何減小傳感器節點和存儲節點之間的通信開銷。對 Intel Lab[25]提供的真實數據 (該數據是Intel Lab在2004年1月3日至2004年3月10日期間部署的 44個傳感器采集的數據，并且每個傳感器采集了溫度、濕度與電壓3種數據)進行了詳細的統計分析，發現如果將這些多維數據作為一個整體看待，相鄰周期數據的重復率很低。如取一個周期為10min時，相鄰周期的三維數據的平均重復率只有1.97%，二維數據的平均重復率也只有4.52%。但是如果單獨從某一維上的數據(如溫度)看，相鄰周期數據的重復率達到59.4%；進一步地，如果保存前面3～5個周期的數據作為歷史數據集，當前周期所產生的數據平均超過99.5%的數據在歷史數據集中，而且在隨后的近 20個周期中，每個周期平均都有超過80%的數據在歷史數據集中。

根據數據在同一維上重復的規律，本文數據壓縮表示和傳輸的基本想法是:分別在傳感器和存儲節點上保存傳感器已計算的數據的加密和編碼結果，并用一個較短的代碼來代替該數據。當傳感器新采集的數據在代碼表中存在時，傳感器只需要在代碼表中查詢出該數據的代碼發送給存儲節點；存儲節點獲得傳感器發送來的代碼后，根據傳感器ID以及發送來的代碼在本地維護的代碼表中查詢出對應的加密和編碼結果，從而避免傳感器為該數據重復計算加密和編碼結果以及減小傳感器和存儲節點之間的通信開銷。

5.1 代碼表設計

根據數據壓縮表示的基本思想，本文分別為傳感器節點和存儲節點設計代碼表。代碼表的設計與維護應該滿足以下條件:①代碼表不能太大，以免占用過多的空間；②存儲節點上的代碼表和傳感器節點上的代碼表的同步不能過于頻繁，以免消耗過多通信資源；③要盡可能地提高存儲節點代碼表的查詢速度，為存儲節點上的代碼表存儲了單元內所有傳感器提交的代碼，傳感器發送來的大部分數據需要在代碼表中進行查詢后得到數據的編碼值和加密值，因此查詢操作是代碼表中最主要的操作。

為了滿足以上條件，傳感器上的代碼表和存儲節點上的代碼表如表1和表2所示。其中，Value、Code、Encode、Cipher、Sensor ID是一些基本屬性，分別表示數據的真實值、代碼值、編碼結果、加密結果以及傳感器節點 ID。傳感器節點代碼表中的Time Slot用于記錄該代碼最近使用的周期號，引入該屬性是為了避免代碼表隨時間的推移而不斷增大。當前周期與代碼記錄中的最近使用周期之差達到設定的閾值時，認為該代碼已經過期；在傳感器代碼表中的可用空間不足時，批量地將過期代碼記錄從表中刪除。傳感器節點代碼表中的Syn tag屬性記錄了該代碼與存儲節點的代碼之間的同步情況，“1”表示已經同步，即在存儲節點的代碼表中有相應的記錄；“0”表示沒有同步，即存儲節點上的代碼表中還沒有該記錄。引入該屬性是為了對代碼進行批量更新，當傳感器節點產生新數據時，只暫時更新本地代碼表，并置該屬性值為“0”，當達到一定條件后再向存儲節點發起代碼批量更新的請求。圖7中 E( di)、 C( di)和 R( di)分別表示對數據 di的編碼、加密和產生的隨機代碼的結果。

表1 sη代碼表

表2 存儲節點代點碼表

5.2 數據表示與傳輸

Step 1 判斷數據di(0≤i≤n)是否在代碼表中。

1) di在代碼表中，更新該代碼的最近使用周期為t，并進一步判斷Syn Tag的值。

Syn Tag值為“1”:獲得該數據的代碼 R( di)作為向存儲節點發送的數據。

Syn Tag值為“0”:獲得該數據的編碼和加密結果 E( di)和 C( di)作為向存儲節點發送的數據。

2) di不在代碼表中，分別計算該數據的編碼和加密結果 E( di)、C( di)，并采用隨機數發生器產生一個長度為且與當前代碼表中代碼不重復的代碼 R( di)作為該數據的代碼，在本地代碼表中插入記錄（ di,R( di)E( di)C( di), t, 0）(如果代碼表中的空間不足，在保存過期代碼的前提下刪除所有過期數據，然后進行數據插入)，并將 E( di)和C( di)作為向存儲節點發送的數據。

Step 2 傳感器sη將通過第一步得到的發送數據發送給附近的存儲節點。

存儲節點接收到傳感器sη發送來的各維上數據后，檢查是否有代碼數據，如果有代碼數據，則根據傳感器的 ID號和數據代碼在本地代碼表中查找出相應數據的編碼和加密結果。

6 分析

本節首先對提出方案的安全性進行分析，然后重點對協議的通信開銷以及幾個關鍵參數進行分析。

6.1 安全性分析

條件聚合協議的安全性包含兩部分:加密數據的安全性以及編碼數據的安全性。加密數據的安全性基于加密數方案本身，由于不同傳感器節點采用不同的密鑰對數據進行加密，因此攻擊者在沒有獲得傳感器密鑰的情況下是很難破解傳感器節點采集數據的真實值。在編碼部分，每一個傳感器分別采用了秘密編碼布魯姆過濾器，由于散列函數的單向性以及秘密性，因此攻擊者無法根據編碼結果解密數據。

6.2 幾個重要參數的分析

接下來對編碼結果的大小、假陽性以及同態加密數據的大小進行分析。

編碼大小及假陽性分析:由于采用布魯姆過濾器對數據進行編碼，因此存在假陽性問題。對于要編碼的數據，要知道其范圍，即在范圍R下的編碼。例如，在環境檢測中，在一個特定的地方，溫度的變化范圍一般用8位就足以區分。假設在范圍R下，數據可以用w位進行區分，則產生n=w+1個前綴，即一個布魯姆過濾器中需要存儲的元素個數。當選取布魯姆過濾器的大小為 m時，散列函數的個數k=ln2m/n。根據假陽性的計算公式:f ≈ (1 - e-km/n)k≈ 0.6185m/n。在Intel Lab[25]提供的真實數據來驗證本文的方案，用8位數據就能區分，即布魯姆中需要存儲的前綴數量是 9，采用的布魯姆過濾器的大小是 91位，理論上數據的假陽性為0.8192%。由于假陽性的存在，因此存儲節點進行聚合的時候，聚合結果與真實值之間存在一定的偏差。設在某一維上數據的最大和最小值分別為Vmax和Vmin，假陽性比率為f，則在最差的情況下的偏差為:f (Vmax?Vmin)。

同態加密數據的大小:由第2節介紹的同態加密原理知:同態加密結果長度為 lh=。其中，Vmax為參加運算的數據的最大值，n為可以支持的參加運算的元素個數。n越大時，可以支持參加同態運算元素的個數越多，存儲節點與sink節點的通信開銷就越小；但n越大，同態加密的結果也就越大，存儲節點和傳感器節點的通信開銷也就越大。因此需要綜合考慮后來確定 n的取值。設代碼長度假為lc，編碼數據長度為le；傳感器在一段時間內采集的數據的個數為M，這M 個元素中通過代碼上傳的數據比率為 r，同時有k個數據進行了代碼更新，則傳感器節點的通信大小為

式(1)中，代碼長度、編碼長度為常數，因此可以變化成:S = (M ×(1 -r) +k )+ C 。從式中可以看出:n越小，傳感器發送的數據量就越小。假設在同一時間段內，需要對M’個數據進行聚合并發送給 sink，則存儲節點的通信空間開銷為

從式(2)中不難看出，n越大，存儲節點發送給sink的開銷就越小。在給定具體參數的情況下，可以求出n的最優值。

7 實驗

本文算法中，能耗與文獻[16]的能耗基本一致，即每發送32bit數據，需消耗33μJ左右的能量，為了便于分析本文算法在各個維度數據中的有效性，用傳感器平均每一個周期向存數節點發送的數據量大小以及存儲節點返給sink的平均每1個查詢的結果大小來評估實驗結果。在OMnet++平臺上實現了本文提出的協議，并采用了 Intel Lab[25]在 2004年1月3日至2004年3月10日期間部署的44個傳感器采集的數據。本文實驗與SafeQ[12]采用了同樣的網絡拓撲結構圖，即實驗將44個傳感器分成4個組，每個組內有11個傳感節點和一個存儲節點。隨機產生了1000個聚合查詢對存儲節點上的數據進行查詢。

本文首先用實驗的方法分析了本文協議中的幾個重要參數:數據的重復率，不同閾值下數據的更新周期以及聚合數據n的取值。圖7(a)給出在不同歷史數據集大小下，數據重復率隨時間變化關系。圖中 1、2、4、6、8分別表示將傳感器在1個周期、2個周期、…、8個周期采集的數據作為歷史數據的情況。從圖中可以看出，歷史數據集越大，數據重復率下降的越慢。圖7(b)表示在不同閾值，不同歷史數據集大小的情況下，數據平均更新周期。例如圖7(b)中，當歷史數據集為8時，設定更新閾值為 80%(即當前周期數據與歷史數據重復率不高于80%)，則平均90個周期需要更新一次歷史數據集。圖7(c)的n表示同態加密支持的數據聚合的個數。圖中表示隨n的不同，傳感器和存儲節點發送數據量大小的和的變化情況，圖中n=66為最優。

圖8是在確定同態加密支持66個數據進行聚合的情況下，采用聚合和不采用聚合情況下查詢響應當中數據量的大小比較。本文聚合協議支持跨周期數據的聚合，當聚合中所跨周期越大，協議的優勢越明顯。計算參與聚合的周期數為 1～8，對于一維數據，本文的協議發送數據量大小比不進行聚合平均要減小94.82%；二維數據要減小90.57%；三維數據減小82.76%。

不同更新閾值同樣影響傳感器節點發送數據量的大小，圖 9對比了一、二、三維數據在不同閾值下傳感器發送數據量大小，為了更好地區分，圖中曲線表示對前面周期數據發送量的總和，如time slot=5，表示前面5個周期傳感器發送數據的總量，并且將更新數據量平均計入該總量中。

圖7 Intlab數據中的幾個重要參數

圖8 存儲節點發送給sink的查詢結果的平均大小

圖9 傳感器在不同周期數的情況下提交給存儲節點數據的平均大小

8 結束語

本文提出了一種隱私保護的條件聚合協議，使存儲節點在不知道數據真實值的情況下對滿足條件的數據進行聚合。為了保護數據和查詢條件的隱私性，提出了一種基于前綴成員確認和布魯姆過濾器相結合的編碼方法，對數據和查詢條件進行編碼，實現存儲節點在不知道數據真實值和查詢條件真實值的情況下進行查詢處理；為了對查詢結果中的數據進行聚合而不暴露數據真實值，采用同態加密技術對數據進行加密，使數據在不解密的情況下能進行聚合運算。根據傳感器采集數據的特點，提出了一種基于代碼表的數據壓縮表示以及傳輸方法，有效減小了傳感器節點和存儲節點之間的通信開銷。分析和實驗結果驗證了所提方案的有效性。

[1]李建中,李金寶,石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報, 2003,14(10):1717-1727 LI J H, LI J B, SHI S F.Concepts, issues and advance of sensor networks and data management of sensor networks[J].Journal of Software, 2003, 14(10):1717-1727.

[2]崔莉,鞠海玲,苗勇等.無線傳感器網絡研究進展[J].計算機研究與發展, 2005, 42(1):163-174.CUI L, JU H L, MIAO Y, et al.Overview of wireless sensor networks[J].Journal of Computer Research and Development, 2005,42(1):163-174.

[3]DESNOYERS P, GANESAN D, LI H, SHENOY P.Presto:a predic-tive storage architecture for sensor networks[A].Proc 10th Workshop on Hot Topics in Operating Systems[C].Berkeley:USENIX Association, 2005.23-23.

[4]ZEINALIPOUR-YAZTI D, LIN S, KALOGERAKI V, et al.Microhash:An efficient index structure for flash-based sensor devices[A].Proc 4th USENIX Conf.on File and Storage Technologies (FAST2005)[C].2005.31-44.

[5]SHENG B, LI Q, MAO W.Data storage placement in sensor networks[A].Proc 7th ACM Inte Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc2006)[C].2006.344-355.

[6]SHENG B, TAN CC, LI Q, MAO W.An approximation algorithm for data storage placement in sensor networks[A].Proc Inte Conf on Wireless Algorithms, Systems and Applications (Wasa 2007)[C].2007.71-78.

[7]HEIDEMANN J.et al.Building efficient wireless sensor networks with low-level naming[A].18th ACM Symposium on Operating Systems Principles[C].October 2001.21-24.

[8]INTANAGONWIWAT C, GOVINDAN R, ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks[A].Proc Annual Inte Conf on Mobile Computing and Networking[C].New York:ACM Press, 2000.56-67.

[9]SHENG B, LI Q.Verifiable privacy-preserving range query in two-tiered sensor networks[A].Proc IEEE Inte Conf on Computer Communications (INFOCOM2008)[C].2008.46-50.

[10]SHI J, ZHANG R, ZHANG Y.Secure range queries in tiered sensor networks[A].Proc IEEE Inte Conf on Computer Communications(INFOCOM2009)[C].2009.945-953.

[11]ZHANG R, SHI J, ZHANG Y.Secure multidimensional range queries in sensor networks[A].Proc ACM Inte Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc2009)[C].2009.197-206.

[12]CHEN F, LIU A X.SafeQ:Secure and efficient query processing in sensor networks[A].Proc IEEE Inte Conf on Computer Communications (INFOCOM 2010)[C].2010.2642-2650.

[13]PRZYDATEK B, SONG D, PERRIG A.SIA:secure information aggregation in sensor networks[A].Proc Inte Embedded Networked Sensor Systems (SenSys’03)[C].2003.255-265.

[14]WANG C, WANG G, ZHANG W, FENG T.Reconciling privacy preservation and intrusion detection in sensory data aggregation[A].Proc IEEE Inte Conf on Computer Communications (INFOCOM 2011)[C].2011.336-340.

[15]CASTELLUCCIA C, MYKLETUN E, TSUDIK G.Efficient aggregation of encrypted data in wireless sensor networks[A].Proc Annual Inte Conf on Mobile and Ubiquitous Systems:Networking and Services[C], San Diego, CA, USA, 2005.109-117.

[16]YAO Y, XIONG N, PARK J, et al.Privacy-preserving max/min query in two-tiered wireless sensor networks[J].Computer and Mathematics with Application.2012, 2:1-8.

[17]GOLDREICH O.Foundations of Cryptography:Vol.2, Basic Applications[M].Cambridge University Press, New York, NY,USA, 2004.

[18]CHAN H, PERRIG A, SONG D.Secure hierarchical in-network aggregation in sensor networks[A].Proceedings of the 13th ACM conference on Computer and communications security[C].New York:ACM Press.2006:278 - 287.

[19]YANG Y, WANG X.ZHU S, et al.Sdap:a secure hop-by-hop data aggregation protocol for sensor networks[J].ACM Transactions on Information and System Security, 2008, 11(4):1-43.

[20]ISKANDER M K, Lee A J, Mossé D.Privacy and robustness for data aggregation in wireless sensor networks[A].Proceedings of the 17th ACM Conference on Computer and Communications Security[C].New York:ACM Press, 2010.699-701

[21]CHENG J, YANG H, WONG S H, et al.Design and implementation of cross-domain cooperative firewall[A].Proc.International Conference on Network Protocols[C].Piscataway:IEEE, 2007.284-293.

[22]LIU A X, CHEN F.Collaborative enforcement of firewall policies in virtual private networks[A].Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing[C].New York:ACM Press, 2008.95-104.

[23]CHANG Y K.Fast binary and multiway prefix searches for packet forwarding[J].Computer Networks, 2007, 51(3):588-605.

[24]BRODER A, MITZENMACHER M.Network applications of Bloom filters:A survey[J].Internet Mathematics, 2004, 11(4):485-509.

[25]Intel lab data[EB/OL].http://berkeley.intel-research.net/ labdata.