李睿，林亞平，李晉國

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

1 引言

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

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

在網(wǎng)絡(luò)中，傳感器節(jié)點收集了大量監(jiān)測目標(biāo)的細(xì)節(jié)數(shù)據(jù)，而用戶查詢結(jié)果往往需要對滿足查詢條件的細(xì)節(jié)數(shù)據(jù)進(jìn)行綜合計算后得出。例如，用戶可能對一個用于環(huán)境監(jiān)測的傳感器網(wǎng)絡(luò)提出如下查詢請求:

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

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

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

安全條件聚合包含安全查詢和安全聚合兩方面工作。安全查詢獲得滿足條件的細(xì)節(jié)數(shù)據(jù)；安全聚合對滿足條件的細(xì)節(jié)數(shù)據(jù)進(jìn)行聚合。目前還沒有相關(guān)工作研究兩層傳感器網(wǎng)絡(luò)當(dāng)中的條件聚合查詢。與本文最相關(guān)的工作是兩層傳感器網(wǎng)絡(luò)中的安全范圍查詢[9～12]和傳統(tǒng)傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合[13～15]。

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

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

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

本文的主要貢獻(xiàn)如下:①在兩層傳感器網(wǎng)絡(luò)當(dāng)中提出了隱私保護(hù)的條件聚合問題；②提出了一種基于前綴編碼和布魯姆過濾器相結(jié)合的數(shù)據(jù)隱私編碼方案；③提出了一種基于代碼表的數(shù)據(jù)壓縮表示和傳輸方法。

2 模型

2.1 系統(tǒng)模型

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

2.2 基本假設(shè)

對于上述兩層傳感器網(wǎng)絡(luò)，本文做出如下假設(shè)。

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

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

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

2.3 威脅模型

本文研究如何防止攻擊者從傳感器網(wǎng)絡(luò)中獲得敏感數(shù)據(jù)信息而破壞數(shù)據(jù)的隱私性。在很多實際應(yīng)用中，保護(hù)敏感數(shù)據(jù)隱私性是一個關(guān)鍵任務(wù)，如在用于監(jiān)測健康狀況的傳感器網(wǎng)絡(luò)中，個人健康數(shù)據(jù)的保護(hù)就顯得非常重要。

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

3 數(shù)據(jù)加密方案

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

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

圖2 同態(tài)加密運算的基本思想

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

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

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

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

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

在兩層傳感器網(wǎng)絡(luò)中，傳感器節(jié)點和sink共享加密密鑰。傳感器將數(shù)據(jù)進(jìn)行加密后發(fā)送給存儲節(jié)點，存儲節(jié)點對滿足條件的所有傳感器節(jié)點發(fā)送的數(shù)據(jù)進(jìn)行聚合運算，并將運算的結(jié)果發(fā)送給sink。Sink根據(jù)參加聚合運算的數(shù)據(jù)個數(shù)以及數(shù)據(jù)提供者的 ID進(jìn)行解密得到相應(yīng)的明文。因此，數(shù)據(jù)加密方是傳感器節(jié)點，數(shù)據(jù)解密方是sink節(jié)點，密文的運算在存儲節(jié)點上進(jìn)行。

4 數(shù)據(jù)隱私查詢編碼方案

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

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

圖3 編碼方案的基本思想

4.1 前綴成員確認(rèn)

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

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

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

圖4 前綴成員確認(rèn)

4.2 布魯姆過濾器

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

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

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

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

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

圖6 布魯姆過濾器的成員確認(rèn)

4.3 數(shù)據(jù)提交協(xié)議

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

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

Step2 sη應(yīng)用私鑰kη對所有數(shù)據(jù)進(jìn)行加密，得到加密結(jié)果: {,,… , (dn)kη}。

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

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

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

4.4 查詢協(xié)議

查詢協(xié)議處理sink節(jié)點如何對查詢條件進(jìn)行編碼，傳感器節(jié)點如何對查詢條件進(jìn)行轉(zhuǎn)換以及存儲節(jié)點如何實現(xiàn)查詢處理。

當(dāng)需要執(zhí)行范圍查詢[a，b]時，Sink、存儲節(jié)點和傳感器節(jié)點分別執(zhí)行以下步驟來完成該查詢?nèi)蝿?wù)。

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

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

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

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

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

Step7 存儲節(jié)點將滿足條件的所有加密數(shù)據(jù)進(jìn)行聚合，并將聚合結(jié)果發(fā)送給sink。

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

5 基于代碼表的數(shù)據(jù)壓縮表示及傳輸

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

根據(jù)數(shù)據(jù)在同一維上重復(fù)的規(guī)律，本文數(shù)據(jù)壓縮表示和傳輸?shù)幕鞠敕ㄊ?分別在傳感器和存儲節(jié)點上保存?zhèn)鞲衅饕延嬎愕臄?shù)據(jù)的加密和編碼結(jié)果，并用一個較短的代碼來代替該數(shù)據(jù)。當(dāng)傳感器新采集的數(shù)據(jù)在代碼表中存在時，傳感器只需要在代碼表中查詢出該數(shù)據(jù)的代碼發(fā)送給存儲節(jié)點；存儲節(jié)點獲得傳感器發(fā)送來的代碼后，根據(jù)傳感器ID以及發(fā)送來的代碼在本地維護(hù)的代碼表中查詢出對應(yīng)的加密和編碼結(jié)果，從而避免傳感器為該數(shù)據(jù)重復(fù)計算加密和編碼結(jié)果以及減小傳感器和存儲節(jié)點之間的通信開銷。

5.1 代碼表設(shè)計

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

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

表1 sη代碼表

表2 存儲節(jié)點代點碼表

5.2 數(shù)據(jù)表示與傳輸

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

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

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

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

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

Step 2 傳感器sη將通過第一步得到的發(fā)送數(shù)據(jù)發(fā)送給附近的存儲節(jié)點。

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

6 分析

本節(jié)首先對提出方案的安全性進(jìn)行分析，然后重點對協(xié)議的通信開銷以及幾個關(guān)鍵參數(shù)進(jìn)行分析。

6.1 安全性分析

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

6.2 幾個重要參數(shù)的分析

接下來對編碼結(jié)果的大小、假陽性以及同態(tài)加密數(shù)據(jù)的大小進(jìn)行分析。

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

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

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

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

7 實驗

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

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

圖8是在確定同態(tài)加密支持66個數(shù)據(jù)進(jìn)行聚合的情況下，采用聚合和不采用聚合情況下查詢響應(yīng)當(dāng)中數(shù)據(jù)量的大小比較。本文聚合協(xié)議支持跨周期數(shù)據(jù)的聚合，當(dāng)聚合中所跨周期越大，協(xié)議的優(yōu)勢越明顯。計算參與聚合的周期數(shù)為 1～8，對于一維數(shù)據(jù)，本文的協(xié)議發(fā)送數(shù)據(jù)量大小比不進(jìn)行聚合平均要減小94.82%；二維數(shù)據(jù)要減小90.57%；三維數(shù)據(jù)減小82.76%。

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

圖7 Intlab數(shù)據(jù)中的幾個重要參數(shù)

圖8 存儲節(jié)點發(fā)送給sink的查詢結(jié)果的平均大小

圖9 傳感器在不同周期數(shù)的情況下提交給存儲節(jié)點數(shù)據(jù)的平均大小

8 結(jié)束語

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

[1]李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報, 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]崔莉,鞠海玲,苗勇等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機(jī)研究與發(fā)展, 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.