戴 華，王 敏，易 訓(xùn)，楊 庚,2，葉慶群

1.南京郵電大學(xué) 計算機(jī)學(xué)院，南京 210023

2.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室，南京 210023

3.墨爾本皇家理工大學(xué) 科學(xué)學(xué)院，澳大利亞 墨爾本 3000

無線傳感器網(wǎng)絡(luò)安全MAX/MIN查詢技術(shù)綜述*

戴 華1,2+，王 敏1，易 訓(xùn)3，楊 庚1,2，葉慶群1

1.南京郵電大學(xué) 計算機(jī)學(xué)院，南京 210023

2.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室，南京 210023

3.墨爾本皇家理工大學(xué) 科學(xué)學(xué)院，澳大利亞 墨爾本 3000

隨著無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）的廣泛應(yīng)用，對于具備安全保護(hù)能力的數(shù)據(jù)查詢技術(shù)的需求日益迫切，安全MAX/MIN查詢就是其中一種重要的數(shù)據(jù)查詢方式?，F(xiàn)有的安全MAX/MIN查詢技術(shù)多數(shù)采用半誠實威脅模型，以保護(hù)感知節(jié)點采集數(shù)據(jù)和查詢結(jié)果的私密性為研究重點，較少關(guān)注由于數(shù)據(jù)篡改、偽造等攻擊手段導(dǎo)致的查詢結(jié)果完整性驗證問題。從數(shù)據(jù)隱私保護(hù)和查詢結(jié)果完整性驗證這兩個角度出發(fā)，分別基于傳統(tǒng)WSN和兩層WSN對現(xiàn)有的安全MAX/MIN查詢處理技術(shù)進(jìn)行了總結(jié)，介紹了網(wǎng)絡(luò)模型和查詢模型，并給出了在兩種網(wǎng)絡(luò)結(jié)構(gòu)中關(guān)于私密性和完整性的問題描述；全面分析了現(xiàn)有方法采用的關(guān)鍵技術(shù)和協(xié)議流程，討論了各自的優(yōu)點和不足，同時指出未來的研究方向。

無線傳感器網(wǎng)絡(luò)；MAX/MIN查詢；隱私保護(hù)；完整性驗證

1 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）由若干感知設(shè)備通過無線通信協(xié)議構(gòu)成，通常分布在無人值守的地域之中，用以探測所部屬環(huán)境的物理信息。分布的感知設(shè)備通常具有一定的計算能力，能通過無線連接方式與周圍鄰近的感知設(shè)備進(jìn)行通信，在軍事安全、環(huán)境監(jiān)測等方面具有廣闊的應(yīng)用前景。傳統(tǒng)無線傳感器網(wǎng)絡(luò)[1]如圖1所示，其網(wǎng)絡(luò)結(jié)構(gòu)簡單，由部署在特定區(qū)域的大量傳感器節(jié)點組成，由于成本限制，感知節(jié)點在計算、存儲、能量等資源上受限，僅與鄰近的節(jié)點通信，從而形成多跳式通信結(jié)構(gòu)；對于基站的查詢請求，往往由網(wǎng)絡(luò)內(nèi)各感知節(jié)點通過查詢協(xié)議協(xié)作完成。兩層無線傳感網(wǎng)絡(luò)[2]（two-tiered wireless sensor network）如圖2所示，在傳統(tǒng)WSN的基礎(chǔ)上引入存儲節(jié)點（storage node）作為網(wǎng)絡(luò)中間層，存儲節(jié)點資源豐富，負(fù)責(zé)收集、存儲其所在區(qū)域內(nèi)的感知節(jié)點采集的數(shù)據(jù)；對于基站的查詢指令，由存儲節(jié)點構(gòu)成的上層網(wǎng)絡(luò)協(xié)作完成。

隨著傳感器網(wǎng)絡(luò)的應(yīng)用發(fā)展，涉及數(shù)據(jù)的隱私性和完整性的安全問題也日益凸顯。例如，在野生動植物監(jiān)測場景中，珍稀物種的監(jiān)控信息可能被竊取，用于非法狩獵；在國防軍事領(lǐng)域，敏感區(qū)域監(jiān)測信息可能被非法監(jiān)聽或篡改而影響國家安全；在居民日常生活中，各種資源（如水、電、煤氣等）的使用監(jiān)測信息可能被非法采集和分析而用于盜竊作案等。當(dāng)前，針對私密性和完整性的安全保護(hù)已成為WSN應(yīng)用和研究中的熱點問題。在傳統(tǒng)WSN中，所有感知節(jié)點在數(shù)據(jù)存儲和通信上具有同質(zhì)性，且參與基站發(fā)起的查詢處理過程，因此防范任一感知節(jié)點被俘獲而導(dǎo)致的數(shù)據(jù)泄露和完整性驗證問題是研究的關(guān)鍵；而在兩層WSN中，存儲節(jié)點不僅存儲著所在區(qū)域內(nèi)所有感知節(jié)點采集的數(shù)據(jù)，同時負(fù)責(zé)響應(yīng)基站的查詢指令，導(dǎo)致存儲節(jié)點成為該網(wǎng)絡(luò)結(jié)構(gòu)中的關(guān)鍵節(jié)點，因此防范針對存儲節(jié)點中數(shù)據(jù)私密性和完整性是兩層WSN安全問題研究的關(guān)鍵。此外，由于資源受限的感知節(jié)點是傳感器網(wǎng)絡(luò)的核心組成部分，如何提高節(jié)點的能耗利用效率，從而提高整個網(wǎng)絡(luò)的生命周期，也是各項研究的一個重要目標(biāo)。

數(shù)據(jù)查詢（data query）是傳感器網(wǎng)絡(luò)事件監(jiān)測和數(shù)據(jù)管理應(yīng)用中的基本手段。在當(dāng)前面向傳感器網(wǎng)絡(luò)的數(shù)據(jù)查詢技術(shù)研究中，安全數(shù)據(jù)查詢已引起廣泛的關(guān)注并成為研究的熱點，包括安全Top-k查詢[3-15]、范圍（range）查詢[16-25]和最值（MAX/MIN）查詢[26-35]等。這些研究工作主要從數(shù)據(jù)隱私保護(hù)和（或）查詢結(jié)果完整性驗證角度，提出各種行之有效的解決方案。本文針對安全MAX/MIN查詢處理，分別從傳統(tǒng)WSN和兩層WSN出發(fā)，對現(xiàn)有工作進(jìn)行綜述研究，總結(jié)現(xiàn)有工作的核心思想，討論各項工作的優(yōu)缺點，并展望未來可能的研究方向。

本文組織結(jié)構(gòu)如下：第2章為相關(guān)模型介紹以及問題描述；第3章和第4章根據(jù)不同的網(wǎng)絡(luò)模型對現(xiàn)有的安全最值（MAX/MIN）查詢技術(shù)進(jìn)行分析與總結(jié)；第5章對現(xiàn)有研究工作進(jìn)行分析，并對未來可能的研究方向進(jìn)行展望。

2 模型及問題描述

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

傳統(tǒng)WSN模型如圖1所示，整個網(wǎng)絡(luò)由基站（或者Sink節(jié)點）和大量感知節(jié)點構(gòu)成，為了控制網(wǎng)絡(luò)部署成本，感知節(jié)點往往是計算、存儲、能量等資源受限的設(shè)備，感知節(jié)點之間形成多跳式網(wǎng)絡(luò)通信結(jié)構(gòu)，實現(xiàn)對網(wǎng)絡(luò)部署區(qū)域內(nèi)數(shù)據(jù)的采集和監(jiān)控。

兩層WSN結(jié)構(gòu)如圖2所示，通過在傳統(tǒng)WSN的基礎(chǔ)上引入了資源豐富的存儲節(jié)點，將整個網(wǎng)絡(luò)分割為連續(xù)不重合的單元。每個單元由一個存儲節(jié)點和若干感知節(jié)點構(gòu)成，其中感知節(jié)點負(fù)責(zé)采集數(shù)據(jù)，并發(fā)送至存儲節(jié)點；而存儲節(jié)點則負(fù)責(zé)接收并存儲來自感知節(jié)點的數(shù)據(jù)，同時還負(fù)責(zé)執(zhí)行來自基站的查詢請求。最終該結(jié)構(gòu)形成分工明確的兩層結(jié)構(gòu)的網(wǎng)絡(luò)，其中單元內(nèi)的感知節(jié)點與存儲節(jié)點之間構(gòu)成以數(shù)據(jù)采集和傳輸為目標(biāo)的下層網(wǎng)絡(luò)結(jié)構(gòu)，而存儲節(jié)點與基站之間則形成以數(shù)據(jù)存儲和查詢處理為目標(biāo)的上層網(wǎng)絡(luò)結(jié)構(gòu)。

上述兩種網(wǎng)絡(luò)模型中的感知節(jié)點均為資源受限設(shè)備，且都負(fù)責(zé)數(shù)據(jù)采集，節(jié)點之間的數(shù)據(jù)通信協(xié)議（如TAG（tiny aggregation）[36]、LEACH（low energy adaptive clustering hierarchy）[37]等）有通用性。兩者的區(qū)別也較明顯，在傳統(tǒng)WSN中，感知節(jié)點除了負(fù)責(zé)采集數(shù)據(jù)之外，還負(fù)責(zé)一定時間周期的數(shù)據(jù)存儲，且響應(yīng)和執(zhí)行基站的查詢指令；而兩層WSN中由于資源豐富的存儲節(jié)點的加入，感知節(jié)點僅負(fù)責(zé)數(shù)據(jù)采集并發(fā)送至存儲節(jié)點進(jìn)行存儲，不再參與查詢處理，而是交由存儲節(jié)點完成基站的查詢處理請求。這就使得在同等條件下兩層WSN的網(wǎng)絡(luò)生命周期比傳統(tǒng)WSN更長，穩(wěn)定性也更高；但由于存儲節(jié)點的制備成本較高，導(dǎo)致同等條件下兩層WSN的部署成本高于傳統(tǒng)WSN。

Fig.1 Traditional WSN structure圖1 傳統(tǒng)WSN結(jié)構(gòu)圖

Fig.2 Two-tiered WSN structure圖2 兩層WSN結(jié)構(gòu)圖

2.2 查詢模型

MAX/MIN查詢是以獲取特定時間和區(qū)域內(nèi)感知節(jié)點采集到的數(shù)據(jù)的最大或最小值為目的的查詢方法，形式化表示為：

其中，S表示查詢區(qū)域內(nèi)的感知節(jié)點集合；t為查詢時間；MAX/MIN表示所要查詢的最值類型。例如Qt=({s1,s2,…,s100},t,MAX)，表示查詢在t時間內(nèi)感知節(jié)點s1～s100所覆蓋區(qū)域的最大值。

在傳統(tǒng)WSN中，基站將查詢指令在網(wǎng)絡(luò)內(nèi)進(jìn)行廣播，感知節(jié)點根據(jù)自身位置判斷是否參與查詢處理，若是則根據(jù)查詢協(xié)議執(zhí)行查詢處理過程；而在兩層WSN中，基站的查詢指令只在存儲節(jié)點構(gòu)成的上層網(wǎng)絡(luò)進(jìn)行廣播，滿足查詢條件的存儲節(jié)點根據(jù)查詢協(xié)議執(zhí)行查詢處理指令，并返回結(jié)果，而感知節(jié)點并不參與查詢處理過程。

2.3 問題描述

（1）隱私性：是指感知節(jié)點采集的數(shù)據(jù)以及查詢處理結(jié)果對其他節(jié)點不可見的私密性要求。在傳統(tǒng)WSN中，由于構(gòu)成網(wǎng)絡(luò)的感知節(jié)點的同質(zhì)性，都負(fù)責(zé)數(shù)據(jù)采集、存儲，并參與查詢處理，這就需要防范任一感知節(jié)點窺探網(wǎng)絡(luò)內(nèi)部其他節(jié)點的隱私數(shù)據(jù)，即對于任一節(jié)點si而言，無法獲取Dt-Di,t中的任何數(shù)據(jù)；而在兩層WSN中，由于存儲節(jié)點M不僅存儲所在單元內(nèi)所有感知節(jié)點采集的數(shù)據(jù)，同時還負(fù)責(zé)執(zhí)行基站的查詢處理請求，導(dǎo)致其成為網(wǎng)絡(luò)的關(guān)鍵節(jié)點，這也使得防范M窺探感知節(jié)點采集的隱私數(shù)據(jù)成為研究重點，即防范M獲取Dt中的任何數(shù)據(jù)。

（2）完整性：是指基站獲得查詢結(jié)果的正確性和完備性需求，即獲得的查詢結(jié)果R為符合查詢條件的感知節(jié)點采集的最大值或最小值。網(wǎng)絡(luò)中任何參與查詢處理的節(jié)點對于數(shù)據(jù)的篡改或偽造都可能造成基站無法獲得正確且完備的查詢結(jié)果，因此基站需要具有檢測和發(fā)現(xiàn)R是否滿足完整性要求的能力，即判斷R∈Dt∧(?di(di∈(Dt-{R}))→R≥di)是否成立。

在面向WSN的安全MAX/MIN查詢處理研究中，現(xiàn)有工作多數(shù)采用半誠實（honest-but-curious）威脅模型[38]，即假設(shè)網(wǎng)絡(luò)中的節(jié)點能夠遵循既定的查詢處理協(xié)議，但有窺探其他節(jié)點隱私數(shù)據(jù)的企圖，并在此基礎(chǔ)上重點研究針對隱私性的安全查詢處理方法。而針對完整性的研究工作相對較少，在面向查詢結(jié)果完整性驗證的研究中，一般采用攻擊模型（attack model）[28,31]，即假設(shè)網(wǎng)絡(luò)中的感知節(jié)點不僅可能窺探其他節(jié)點的隱私，還有可能篡改、偽造或丟棄數(shù)據(jù)，從而造成查詢結(jié)果不正確或不完整，最終對建立在該查詢結(jié)果基礎(chǔ)上的上層應(yīng)用決策的正確性產(chǎn)生影響。由于面向查詢結(jié)果完整性驗證的威脅模型更強(qiáng)，其研究的復(fù)雜度也相對較高。

此外，由于感知節(jié)點的能量受限特性，對于安全MAX/MIN查詢處理方案的性能主要是從網(wǎng)絡(luò)能耗和生命周期這兩個角度進(jìn)行評價。由于數(shù)據(jù)通信產(chǎn)生的能耗占絕大部分，一般采用網(wǎng)絡(luò)通信代價替代網(wǎng)絡(luò)能耗評價指標(biāo)。

3 面向傳統(tǒng)WSN的查詢處理方法

Fig.3 Query process of traditional WSN圖3 傳統(tǒng)WSN的查詢過程

傳統(tǒng)WSN的安全MAX/MIN查詢處理過程由基站與感知節(jié)點交互完成，本文通過實例給出傳統(tǒng)WSN中查詢處理的一般流程。如圖3所示，設(shè)網(wǎng)絡(luò)由感知節(jié)點{s1,s2,…,s12}組成，采用TAG協(xié)議，在執(zhí)行查詢處理時，基站首先將包含查詢區(qū)域（圓形區(qū)域）、時間指令Qt通過協(xié)調(diào)節(jié)點s2在網(wǎng)絡(luò)內(nèi)發(fā)起廣播，處于查詢區(qū)域內(nèi)的節(jié)點{s2,s3,s6,s8}進(jìn)一步廣播查詢指令，并執(zhí)行查詢指令，根據(jù)既定協(xié)議處理相關(guān)數(shù)據(jù)，最終生成查詢結(jié)果R并上傳至基站。查詢區(qū)域外的其他節(jié)點則不參與查詢處理。現(xiàn)有的面向傳統(tǒng)WSN的安全MAX/MIN查詢處理方法有CDAM（concealed data aggregation for maximum/minimum）[26]、KIPDA（kindistinguishable privacy-preserving data aggregation）[27]、RCDA（recoverable concealed data aggregation）[28]、PMMA（privacy-preserving MAX/MIN aggregation）[29]、SDAM（secure data aggregation for maximum/minimum）[30]和SASPKC（secure aggregation scheme using stateful public key cryptography）[31]，其中CDAM、KIPDA、PMMA和SDAM重點解決傳統(tǒng)無線傳感器網(wǎng)絡(luò)中的隱私保護(hù)MAX/MIN查詢處理問題，而RCDA和SASPKC則主要研究安全數(shù)據(jù)融合方案，但支持安全MAX/MIN查詢處理。這幾種方法在主體流程上類似，它們的核心區(qū)別在于采用不同的安全策略（如對稱加密、哈希消息認(rèn)證碼（Hash-based message authentication code，HMAC）、數(shù)據(jù)匿名等），設(shè)計滿足特定安全性需求和性能需求的查詢協(xié)議，具體工作如下：

（1）CDAM

文獻(xiàn)[26]提出了一種支持MAX/MIN查詢的傳感器網(wǎng)絡(luò)隱私保護(hù)數(shù)據(jù)聚集方法CDAM，該方法利用Domingo-Ferrer隱私同態(tài)加密機(jī)制[39]實現(xiàn)數(shù)據(jù)的隱私保護(hù)。利用該加密方法，CDAM的基本思想如下：設(shè)節(jié)點感知si采集到的數(shù)據(jù)為w，則si首先將w表示如下：

然后分別對ei中的每一位進(jìn)行加密，加密時先將待加密的數(shù)據(jù)a分割成一組滿足特定要求的分片數(shù)據(jù)(a1,a2,…,ad)，再將這組數(shù)據(jù)分別執(zhí)行乘積和取余操作，即E(a)=(a1?r modm,a2?r modm,…,ad?r modm)，E(a)即為數(shù)據(jù)a對應(yīng)的密文。加密完成后，若si為葉節(jié)點，則發(fā)送加密后的數(shù)據(jù)至父節(jié)點；若為中間節(jié)點，根據(jù)上述加密方法的加法同態(tài)特性，將收到的密文數(shù)據(jù)與自身計算所得的密文數(shù)據(jù)按位相加，并將加和得出的新數(shù)據(jù)發(fā)送至父節(jié)點?；臼盏礁?jié)點發(fā)送的密文數(shù)據(jù)后，首先按位解密數(shù)據(jù)，然后對解密得到的數(shù)據(jù)依次進(jìn)行判斷，進(jìn)而確定最終的查詢結(jié)果。

CDAM能夠?qū)崿F(xiàn)隱私保護(hù)的前提是不存在感知節(jié)點被俘獲，否則加密所用的參數(shù)設(shè)置都將泄露。此外，當(dāng)感知數(shù)據(jù)的數(shù)值較大時，加密過程形成的密文分量將同步增多，這也將導(dǎo)致網(wǎng)絡(luò)傳輸通信開銷顯著增長，降低網(wǎng)絡(luò)的生命周期。

（2）KIPDA

文獻(xiàn)[27]提出了一種非加密形式的安全MAX/MIN查詢處理方法KIPDA，該方法基于信息擾亂技術(shù)，通過在感知數(shù)據(jù)中混入擾亂數(shù)據(jù)實現(xiàn)敏感數(shù)據(jù)的隱私保護(hù)。該方法的基本思想如下：首先基站生成全局秘密信息集GSS，用以指定真實數(shù)據(jù)的位置，對于任一感知節(jié)點si，均進(jìn)行如下預(yù)處理過程：si選取GSS的一個單元素子集NS表示真實感知數(shù)據(jù)的位置信息；si將偽裝數(shù)據(jù)按照是否大于真實數(shù)據(jù)值分成兩類，其中小于真實數(shù)據(jù)值的偽裝數(shù)據(jù)所在的位置索引與NS共同構(gòu)成si的秘密信息集NSSi，NSSi由基站設(shè)置并分發(fā)，且滿足NSSi≠?；si將真實數(shù)據(jù)和偽裝數(shù)據(jù)按照位置索引要求放入集合Ui中。當(dāng)基站啟動查詢后，若si為葉節(jié)點，則si將Ui發(fā)送至父節(jié)點；若si為中間節(jié)點，則按索引位置比較自身數(shù)據(jù)集和收到的其他孩子節(jié)點發(fā)來的數(shù)據(jù)集，選取相同索引位置上的最大值組成新的數(shù)據(jù)集，并發(fā)送至父節(jié)點。最后，基站將收到的數(shù)據(jù)集按上述方式計算出最終數(shù)據(jù)集UBS，并根據(jù)GSS獲得UBS中相應(yīng)索引位置上的數(shù)據(jù)，進(jìn)而計算出查詢結(jié)果R。

在KIPDA中，節(jié)點的私密信息集僅與基站共享，且每個節(jié)點的數(shù)據(jù)索引信息不外泄，因此攻擊者很難區(qū)分真實數(shù)據(jù)與偽裝數(shù)據(jù)；但KIPDA中全局安全集和各感知節(jié)點自身記錄的各類數(shù)據(jù)索引集之間存在一定可計算關(guān)系，當(dāng)被攻擊的節(jié)點數(shù)量達(dá)到一定界限時，數(shù)據(jù)隱私就會存在泄露的風(fēng)險。KIPDA的網(wǎng)絡(luò)通信代價主要取決于用于隱匿查詢結(jié)果的數(shù)據(jù)集合的規(guī)模，當(dāng)規(guī)模較大時，網(wǎng)絡(luò)通信代價較高，但安全性增強(qiáng)，反之亦然。

（3）RCDA

文獻(xiàn)[28]提出了一種具有隱私保護(hù)和完整性驗證功能的數(shù)據(jù)融合方法RCDA。該方法中的基站能夠獲取任意感知節(jié)點的數(shù)據(jù)值，因此該方法也支持MAX/MIN查詢處理。在RCDA中，感知節(jié)點首先對采集的數(shù)據(jù)進(jìn)行編碼：假設(shè)各感知節(jié)點所采集的感知數(shù)據(jù)長度為l，共有n個節(jié)點，則節(jié)點si生成長度為n×l的編碼，并將該編碼分成n個長度為l的部分，其中第i部分即為si的感知數(shù)據(jù)di，其余部分用0填充。然后感知節(jié)點生成密文數(shù)據(jù)和相應(yīng)的簽名數(shù)據(jù)，其中密文數(shù)據(jù)是采用文獻(xiàn)[40]提出的EC-EG（elliptic curve ElGamal）加密方法對編碼數(shù)據(jù)加密形成密文，而簽名數(shù)據(jù)是采用文獻(xiàn)[41]提出的基于雙線性映射的聚合簽名方案對di進(jìn)行數(shù)字簽名處理所形成的簽名。在查詢處理過程中，葉節(jié)點將上述兩部分信息直接上傳至父節(jié)點；而中間節(jié)點則將收到的孩子節(jié)點發(fā)來的密文和簽名數(shù)據(jù)分別與自身生成的數(shù)據(jù)對應(yīng)相加，然后將得到的數(shù)據(jù)繼續(xù)向父節(jié)點上傳，直至基站。當(dāng)基站收到鄰居感知節(jié)點發(fā)來的數(shù)據(jù)信息后，首先解密其中的密文數(shù)據(jù)，并根據(jù)位置信息獲取各感知節(jié)點采集的數(shù)據(jù)，再利用簽名數(shù)據(jù)校驗這些數(shù)據(jù)的完整性，最終即可獲得查詢結(jié)果。

RCDA具有良好的隱私保護(hù)和查詢結(jié)果完整性驗證能力，但該方法的編碼方式使得各節(jié)點的編碼長度與感知節(jié)點的數(shù)量n成正比，任何節(jié)點都需要為其他n-1個感知節(jié)點預(yù)留數(shù)據(jù)空間，導(dǎo)致較大的數(shù)據(jù)冗余，特別是在大規(guī)模部署的應(yīng)用場景中，該問題更加突出。此外，RCDA使用的加密方法和簽名方法的復(fù)雜度較高，對于傳感器設(shè)備的硬件要求相對較高，從而導(dǎo)致網(wǎng)絡(luò)部署成本增加。

（4）PMMA

文獻(xiàn)[29]提出了具有抗共謀攻擊能力的隱私保護(hù)MAX/MIN查詢處理方法PMMA。該方法利用前綴成員驗證機(jī)制（prefix membership verification，PMV）[42-43]實現(xiàn)無需明文參與的數(shù)據(jù)比較，并采用HMAC[44]和對稱加密方法實現(xiàn)隱私保護(hù)MAX/MIN查詢?；舅枷肴缦拢涸O(shè)感知節(jié)點采集數(shù)據(jù)的域為[dlow,dhigh]。對于任一感知節(jié)點si而言，設(shè)其在一個查詢周期內(nèi)采集的感知數(shù)據(jù)的最大值為di，si首先利用僅與基站共享的密鑰ki對di進(jìn)行加密，得到的密文數(shù)據(jù)記為(di)ki；然后利用PMV機(jī)制計算di的數(shù)值化前綴成員編碼集N(F(di))，以及區(qū)間[di,dhigh]的數(shù)值化前綴區(qū)間編碼集N(S([di,dhigh]))；最后利用HMAC算法對上述集合進(jìn)行編碼，得到HMACg(N(F(di)))和HMACg(N(S([di,dhigh])))。在數(shù)據(jù)傳輸過程中，若si為葉節(jié)點，則只需發(fā)送密文數(shù)據(jù)(di)ki和兩個HMAC編碼至父節(jié)點；若si為中間節(jié)點，根據(jù)PMV的數(shù)值化比較原理：若F(x)∩S([di,dhigh])≠?，則有x∈[di,dhigh]成立，即x≥di；si則可以確定所收到數(shù)據(jù)和自身采集數(shù)據(jù)中包含最大值的密文數(shù)據(jù)以及HMAC編碼集合，并發(fā)送至父節(jié)點；最后，基站利用同樣方法確定整個網(wǎng)絡(luò)中蘊含最大值的密文數(shù)據(jù)，并利用與感知節(jié)點共享的密鑰解密獲得明文查詢結(jié)果。

由于PMV機(jī)制中每一個感知數(shù)據(jù)都將生成至少2倍數(shù)據(jù)位長的前綴編碼，再加上后續(xù)的HMAC處理，使得每個感知節(jié)點需要傳輸?shù)臄?shù)據(jù)量增大，進(jìn)而導(dǎo)致整個網(wǎng)絡(luò)的通信代價較高。同時，由于所有感知節(jié)點共享HMAC密鑰，若存在一個感知節(jié)點與攻擊者共謀，則攻擊者將能夠利用字典攻擊獲得經(jīng)由該感知節(jié)點轉(zhuǎn)發(fā)的HMAC編碼對應(yīng)的明文感知數(shù)據(jù)。

（5）SDAM

文獻(xiàn)[30]在CDAM基礎(chǔ)上提出了一種基于概率加密機(jī)制的隱私保護(hù)MAX/MIN查詢方法SDAM。該方法利用概率加密的異或同態(tài)特性代替CDAM中的Domingo-Ferrer加法同態(tài)特性，使得查詢處理過程更加高效和安全。SDAM采用GM概率加密協(xié)議[45]，對單位比特b∈{0,1}進(jìn)行加密，得到密文數(shù)據(jù)EGM(b)=zb?r2mod N，其中N為RSA模數(shù)，z為模N的隨機(jī)偽二次非剩余，且z∈ZN,ZN={0,1,2,…,N-1}，r∈ZN′,ZN′={a∈ZN|gcd(a,N)=1}，gcd(a,b)表示a和b的最大公約數(shù)。SDAM在感知節(jié)點數(shù)據(jù)無重復(fù)的前提下使用概率加密機(jī)制的同態(tài)異或特性，即EGM(b⊕b′)=EGM(b)?EGM(b′)mod N(b,b′∈{0,1})。本文以獲取最大值的查詢方法為例，描述該方法的基本思想。設(shè)感知節(jié)點si采集的數(shù)據(jù)值為di，用矢量ui表示如下：

si首先利用概率加密方法按位加密ui，生成加密矢量數(shù)據(jù)。若si為葉節(jié)點，則si直接將加密矢量數(shù)據(jù)發(fā)送至父節(jié)點；若si為中間節(jié)點，則si將其自身生成的加密矢量數(shù)據(jù)以及接收到的孩子節(jié)點的加密矢量數(shù)據(jù)進(jìn)行合成處理，生成合成后的加密矢量數(shù)據(jù)，并發(fā)送至父節(jié)點。當(dāng)基站收到根節(jié)點發(fā)來的矢量數(shù)據(jù)時，基站進(jìn)行解密處理，獲得最終的查詢結(jié)果。

SDAM解決了CDAM中存在感知節(jié)點被俘獲情況下的隱私保護(hù)失效的問題，能夠?qū)崿F(xiàn)隱私保護(hù)MAX/MIN查詢。但該方法與CDAM類似，當(dāng)感知節(jié)點采集的數(shù)據(jù)值較大時，按位加密的方法也將使得查詢處理的通信代價同步增長，導(dǎo)致整個網(wǎng)絡(luò)生命周期降低。

（6）SASPKC

文獻(xiàn)[31]在RCDA的基礎(chǔ)上通過引入同態(tài)加密方法，提出了一種基于狀態(tài)公鑰加密方案的數(shù)據(jù)融合方法SASPKC，同樣支持安全MAX/MIN查詢處理。在該方法中，每個感知節(jié)點利用文獻(xiàn)[46]提出的秘鑰生成方法HKDF（Hash based key derivation function）計算動態(tài)秘鑰。對于任一感知節(jié)點si而言，HKDF產(chǎn)生的秘鑰包含ki1和ki2兩部分。在執(zhí)行查詢時，si首先將其采集的感知數(shù)據(jù)用RCDA中同樣的編碼方式生成編碼數(shù)據(jù)di，并分別計算密文數(shù)據(jù)Ci=ki1+dimod M和簽名數(shù)據(jù)HMAC(Ci,ki2)；若si為葉節(jié)點，則將計算后的數(shù)據(jù)直接發(fā)送至父節(jié)點，若為中間節(jié)點，則將孩子節(jié)點的數(shù)據(jù)與自身計算的數(shù)據(jù)分別進(jìn)行融合處理（密文數(shù)據(jù)相加，簽名數(shù)據(jù)異或），然后再上傳融合后的密文和簽名數(shù)據(jù)?；臼盏礁兄?jié)點發(fā)來的數(shù)據(jù)時，首先解密其中的密文數(shù)據(jù)，并恢復(fù)各節(jié)點采集的明文數(shù)據(jù)，進(jìn)而獲得查詢結(jié)果，然后利用簽名數(shù)據(jù)進(jìn)行結(jié)果完整性驗證。

與RCDA類似，SASPKC同樣具有良好的隱私保護(hù)和查詢結(jié)果完整性驗證能力，但由于SASPKC采用與RCDA中同樣的編碼方法，導(dǎo)致其也存在類似的數(shù)據(jù)冗余問題。同時，SASPKC中使用的同態(tài)加密方法使其具有比RCDA更低的網(wǎng)絡(luò)通信代價。

4 面向兩層WSN的查詢處理方法

兩層WSN在傳統(tǒng)WSN的基礎(chǔ)上引入存儲節(jié)點作為中間層，從而將數(shù)據(jù)采集與數(shù)據(jù)查詢過程分離,使得資源受限的感知節(jié)點僅負(fù)責(zé)采集數(shù)據(jù)并傳輸至存儲節(jié)點，存儲節(jié)點負(fù)責(zé)執(zhí)行基站的查詢指令，從而減少感知節(jié)點由于參與查詢處理過程而帶來能量消耗。因此，兩層WSN的MAX/MIN查詢方法需要研究兩個階段的交互協(xié)議，如圖4所示，一是從感知節(jié)點到存儲節(jié)點的數(shù)據(jù)上傳協(xié)議，二是基站與存儲節(jié)點之間的查詢處理協(xié)議。

Fig.4 Query process of two-tiered WSN圖4 兩層WSN查詢過程

現(xiàn)有的兩層WSN中的安全MAX/MIN查詢方法PMQP（privacy-preserving MAX/MIN query protocol）[32]、EMQP（energy-efficient privacy-preserving MAX/MIN query protocol）[33]、RSCS-PMQ（random secure comparator selection based privacy-preserving MAX/MIN query）[34]和ERM-MQP（efficient random modulation MAX/MIN query protocol）[35]都采用上述兩階段協(xié)議設(shè)計方案，它們的不同點主要有：在感知節(jié)點中采用不同的安全策略對采集數(shù)據(jù)進(jìn)行處理；基于感知節(jié)點對采集數(shù)據(jù)的安全處理方法，在存儲節(jié)點與基站之間設(shè)計相應(yīng)的安全查詢協(xié)議，實現(xiàn)特定安全目標(biāo)和性能要求的安全查詢。具體的相關(guān)工作如下。

（1）PMQP

與PMMA類似，文獻(xiàn)[32]同樣利用PMV機(jī)制，提出了面向兩層WSN的隱私保護(hù)MAX/MIN查詢方法。在安全機(jī)制使用上，PMQP同樣使用HMAC和對稱加密技術(shù)；在查詢處理方法的設(shè)計實現(xiàn)上，PMQP根據(jù)兩層傳感器網(wǎng)絡(luò)的結(jié)構(gòu)特點，提出相應(yīng)的處理方案，實現(xiàn)針對兩層結(jié)構(gòu)中處于關(guān)鍵位置的存儲節(jié)點的數(shù)據(jù)隱私屏蔽保護(hù)。該方法的基本思想為：與PMMA相同，感知節(jié)點首先加密一個查詢周期中采集的感知數(shù)據(jù)的最大值形成密文數(shù)據(jù)，然后利用PMV機(jī)制計算該最大值的數(shù)值化前綴成員編碼集合和數(shù)值化前綴區(qū)間編碼集合，最后利用HMAC算法對上述集合進(jìn)行編碼。感知節(jié)點將編碼后數(shù)據(jù)和加密后的感知數(shù)據(jù)發(fā)送至存儲節(jié)點存儲。在執(zhí)行查詢處理時，基站向存儲節(jié)點發(fā)送查詢指令，存儲節(jié)點接收到基站的查詢指令后，利用PMV的數(shù)值比較特性確定蘊含查詢結(jié)果的密文數(shù)據(jù)，并將該數(shù)據(jù)反饋給基站。基站收到存儲節(jié)點反饋的數(shù)據(jù)后，使用與感知節(jié)點共享的密鑰進(jìn)行解密，進(jìn)而獲得最終的明文查詢結(jié)果。

由于PMQP的基本原理與PMMA相似，PMMA所存在的前綴編碼導(dǎo)致通信代價較高的問題在PMQP中同樣存在。同時，PMQP能夠防范僅存在存儲節(jié)點的隱私窺探。但當(dāng)存儲節(jié)點與任一感知節(jié)點“共謀”時，存儲節(jié)點將能夠獲取所有感知節(jié)點共享的HMAC密鑰，此時存儲節(jié)點即可利用字典攻擊方法，獲得任一感知節(jié)點上傳的HMAC編碼對應(yīng)的明文感知數(shù)據(jù)。

（2）EMQP

為了降低網(wǎng)絡(luò)通信代價，文獻(xiàn)[33]提出了一種基于0-1編碼[47]的兩層WSN的隱私保護(hù)MAX/MIN查詢處理方法EMQP。該方法利用0-1編碼機(jī)制的數(shù)值比較特性實現(xiàn)無需明文參與的數(shù)值比較，并采用HMAC和對稱加密方法，在確保感知節(jié)點采集數(shù)據(jù)與存儲節(jié)點之間的隱私隔離的同時，實現(xiàn)MAX/MIN查詢處理。該方法的基本思想如下：在數(shù)據(jù)上傳階段，任意感知節(jié)點si將單位時間周期內(nèi)采集的最大數(shù)據(jù)di進(jìn)行加密，生成密文(di)ki，然后再對di進(jìn)行0-1編碼，并將得到的編碼數(shù)據(jù)E0(di)和E1(di)進(jìn)行數(shù)值化和HMAC編碼處理，最后將處理后的數(shù)據(jù)發(fā)送至存儲節(jié)點。在查詢處理階段，存儲節(jié)點接收到基站的查詢指令后，存儲節(jié)點根據(jù)0-1編碼機(jī)制中“若E1(x)∩E0(y)≠?，則有x＞y成立”這一數(shù)據(jù)比較方法，確定蘊含查詢結(jié)果的密文數(shù)據(jù)，并將該密文數(shù)據(jù)以及相應(yīng)的節(jié)點ID發(fā)送給基站。最后，基站根據(jù)與相應(yīng)感知節(jié)點共享的密鑰，解密獲得查詢結(jié)果，完成整個查詢處理。

由于EMQP采用了編碼數(shù)量較少的0-1編碼機(jī)制，此外EMQP還引入基于Hash編碼壓縮的優(yōu)化方法，進(jìn)一步降低用于數(shù)值比較的編碼數(shù)據(jù)的空間占用，使得EMQP在網(wǎng)絡(luò)通信代價消耗上顯著優(yōu)于PMQP。但由于EMQP采用與PMQP相同的所有感知節(jié)點共享HMAC密鑰的策略，這也使得EMQP與PMQP的隱私保護(hù)效果完全相同，只能防范針對單一存儲節(jié)點的隱私窺探，無法解決當(dāng)存儲節(jié)點與感知節(jié)點“共謀”時的隱私保護(hù)問題。

（3）RSCS-PMQ

文獻(xiàn)[34]在EMQP的基礎(chǔ)上，提出了一種基于安全比較碼隨機(jī)選擇的兩層WSN隱私保護(hù)MAX/MIN查詢處理方法RSCS-PMQ，這里的安全比較碼即為經(jīng)過HMAC和數(shù)值化處理的0-1編碼。與EMQP相比，該方法就是通過減少感知節(jié)點上傳的編碼數(shù)量，達(dá)到降低網(wǎng)絡(luò)通信代價的目的。該方法的基本思想如下：在數(shù)據(jù)上傳階段，任意感知節(jié)點si對數(shù)據(jù)di進(jìn)行加密，生成密文(di)ki，然后再對di進(jìn)行HMAC數(shù)值化0-1編碼，與EMQP不同的是，RSCS-PMQ只選擇0-1編碼中的一種隨機(jī)安全碼與密文數(shù)據(jù)以及節(jié)點ID一起上傳至存儲節(jié)點。在查詢處理階段，存儲節(jié)點收到基站的查詢指令后，利用最大隨機(jī)安全比較碼選擇算法（max random secure comparator selection,MaxRSC）計算出最小化最大安全比較碼集合，進(jìn)而確定包含最值查詢結(jié)果的最小化候選密文集，再將此密文集發(fā)送至基站。此時，基站只需利用與感知節(jié)點共享的密鑰解密接收到的密文數(shù)據(jù)，即可獲得最終的查詢結(jié)果。

由于安全比較碼隨機(jī)選擇機(jī)制的引入，RSCSPMQ中感知節(jié)點需上傳的編碼數(shù)量比EMQP平均減少了約50％，從而顯著降低感知節(jié)點的通信代價；但只存儲隨機(jī)安全碼也導(dǎo)致存儲節(jié)點只能確定包含查詢結(jié)果的密文集合（可能包含1個或多個候選密文數(shù)據(jù)，大樣本實驗表明平均包含約2個）。而EMQP則能夠確定唯一的密文查詢結(jié)果，這就使得RSCS-PMQ在存儲節(jié)點與基站的通信代價上略高于EMQP。此外，由于采用相同的編碼策略和安全機(jī)制，RSCSPMQ與EMQP在隱私保護(hù)能力上幾乎相同。

（4）ERM-MQP

文獻(xiàn)[35]基于隨機(jī)數(shù)和數(shù)值變換相結(jié)合的密碼理論，提出了一種面向兩層WSN的隨機(jī)調(diào)制隱私保護(hù)查詢協(xié)議ERM-MQP。該方法采用文獻(xiàn)[48]所述的基于身份加密的密鑰分配方案為查詢建立兩條秘密通道：一條為感知節(jié)點與基站之間的會話密鑰，對存儲節(jié)點保密；另一條為感知節(jié)點與存儲節(jié)點之間的會話密鑰。ERM-MQP引入并證明了一種不泄露原始傳感數(shù)據(jù)的隱私保護(hù)數(shù)值比較方法，進(jìn)而實現(xiàn)隱私保護(hù)MAX/MIN查詢處理，其核心協(xié)議主要包含四部分：①節(jié)點與基站分別隨機(jī)調(diào)制參數(shù)；②感知節(jié)點對感知數(shù)據(jù)進(jìn)行數(shù)值變換，并傳送至存儲節(jié)點；③存儲節(jié)點收到密文數(shù)據(jù)后，解密獲得最值隱私數(shù)據(jù)，并使用基站的公鑰進(jìn)行加密反饋給基站。④基站對存儲節(jié)點發(fā)來的密文數(shù)據(jù)進(jìn)行解密，獲得最終的查詢結(jié)果。

ERM-MQP只需要傳遞節(jié)點ID、時間參數(shù)和調(diào)制后的密文數(shù)據(jù)，因此能夠降低網(wǎng)絡(luò)的通信代價。但ERM-MQP安全性能不高：首先，當(dāng)存儲節(jié)點與任一感知節(jié)點共謀時，存儲節(jié)點即可獲得關(guān)鍵參數(shù)，此時很容易計算出任何感知節(jié)點上傳的敏感數(shù)據(jù)；此外，由于ERM-MQP實際采用的數(shù)值比較方法是隱匿系數(shù)的一次多項式，且隱匿的系數(shù)存在特定數(shù)量關(guān)系，在存儲節(jié)點擁有所有隱私數(shù)據(jù)的情況下，該一次多項式較容易被破解，這也導(dǎo)致ERM-MQP對于感知節(jié)點采集數(shù)據(jù)的隱私保護(hù)能力較弱。

此外，Top-k查詢在特殊情況下(k=1)可以退化為MAX/MIN查詢，即Top-1查詢，因此現(xiàn)有的安全Top-k查詢方法[3-15]理論上也能完成安全MAX/MIN查詢?nèi)蝿?wù)。但由于Top-k查詢的算法和協(xié)議并不是專門為Top-1進(jìn)行最優(yōu)化設(shè)計的，在性能和安全性控制上并不適用于安全MAX/MIN查詢方法。

5 展望與總結(jié)

5.1 對現(xiàn)有工作的總結(jié)

綜合前述安全MAX/MIN查詢處理方法的分析和討論，本文對現(xiàn)有研究工作從安全目標(biāo)、安全模型、共謀防范、通信代價以及實現(xiàn)技術(shù)等方面進(jìn)行總結(jié)，如表1所示。

當(dāng)前面向WSN中安全MAX/MIN查詢的研究工作多數(shù)都是建立在半誠實模型基礎(chǔ)上，重點研究查詢處理中的隱私保護(hù)問題，較少關(guān)注查詢結(jié)果的完整性驗證問題。特別是在面向兩層WSN的研究工作中，尚未見有關(guān)MAX/MIN查詢完整性驗證的報道。

對于共謀攻擊問題，CDAM、PMMA、PMQP、EMQP、ERM-MQP和RSCS-PMQ均不具備共謀攻擊的防范能力，其根本原因在于這些方法中的所有感知節(jié)點都共享實現(xiàn)安全查詢的關(guān)鍵參數(shù)，當(dāng)其中任一感知節(jié)點被俘獲，攻擊者將具備反向獲取其他節(jié)點采集數(shù)據(jù)以及查詢結(jié)果的能力。KIPDA能夠在一定程度上防范共謀攻擊，但當(dāng)共謀節(jié)點數(shù)量達(dá)到一定閾值（與該方法中所使用的秘密信息集的規(guī)模有關(guān)）時，攻擊者將具備在含有擾亂數(shù)據(jù)的數(shù)據(jù)集中定位查詢結(jié)果數(shù)據(jù)的能力。RCDA、SDAM和SASPKC的抗共謀攻擊能力相對較強(qiáng)，任一感知節(jié)點無法得知其他任何感知節(jié)點的數(shù)據(jù)信息，在多個節(jié)點被俘獲共謀的情況下，不會造成其他節(jié)點采集數(shù)據(jù)的隱私泄露問題。

Table1 Comparison and conclusion of existing secure MAX/MIN query methods表1 現(xiàn)有的安全MAX/MIN查詢方法對比總結(jié)

在通信代價上，在CDAM、KIPDA、PMMA、RCDA、SDAM、SASPKC和ERM-MQP中，中間節(jié)點能夠?qū)⒑⒆庸?jié)點發(fā)來的數(shù)據(jù)與自身數(shù)據(jù)進(jìn)行融合，且融合結(jié)果不影響查詢處理，這就使得所有感知節(jié)點的通信負(fù)載都相等，感知節(jié)點的能量消耗均衡，能夠最大化整個網(wǎng)絡(luò)的生命周期。而在PMQP、EMQP和RSCSPMQ中，距離數(shù)據(jù)匯集中心越近的感知節(jié)點的通信負(fù)載越大，直接導(dǎo)致網(wǎng)絡(luò)中感知節(jié)點的能量消耗不均衡，整個網(wǎng)絡(luò)的生命周期存在“木桶”效應(yīng)。

在實現(xiàn)安全MAX/MIN查詢的技術(shù)手段上，PMMA、PMQP、EMQP和RSCS-PMQ主要采用對稱加密保護(hù)數(shù)據(jù)私密性，并利用HMAC和具備數(shù)據(jù)比較特性的編碼方法實現(xiàn)無需明文參與的密文數(shù)據(jù)比較，進(jìn)而實現(xiàn)隱私保護(hù)MAX/MIN查詢。CDAM和SDAM分別使用隱私同態(tài)加密和概率加密方法，都利用了特殊加密方法的數(shù)值比較特性實現(xiàn)隱私保護(hù)MAX/MIN查詢。RCDA和SASPKC采用相同的編碼方式，分別使用EC-EG加密和狀態(tài)公鑰加密方法實現(xiàn)針對感知數(shù)據(jù)的隱私保護(hù)，并分別使用雙線性映射簽名和HMAC實現(xiàn)查詢結(jié)果的完整性驗證。ERM-MQP則采用身份加密機(jī)制在基站與感知節(jié)點之間秘密傳輸多項式的系數(shù)，并利用多項式實現(xiàn)隱私保護(hù)MAX/MIN查詢。

5.2 對未來工作的展望

MAX/MIN查詢處理作為一種重要的數(shù)據(jù)查詢方法，被廣泛應(yīng)用于各種傳感器網(wǎng)絡(luò)環(huán)境中。隨著應(yīng)用的不斷深入和拓展，查詢處理過程中的安全保護(hù)問題也越來越引起業(yè)界的廣泛關(guān)注，如感知節(jié)點采集數(shù)據(jù)和查詢結(jié)果數(shù)據(jù)的隱私保護(hù)問題，查詢結(jié)果的完整性驗證問題等。由于感知節(jié)點資源有限，安全性能的提高必然伴隨著通信代價的增長，如何降低網(wǎng)絡(luò)通信代價也是業(yè)界研究的重點之一。因此，傳感器網(wǎng)絡(luò)安全MAX/MIN查詢技術(shù)的進(jìn)一步研究可以從如下三方面展開：

（1）完整性驗證?，F(xiàn)有的面向WSN的安全MAX/MIN查詢處理技術(shù)，多數(shù)都是以半誠實模型為基礎(chǔ)，研究針對查詢過程中的感知數(shù)據(jù)以及查詢結(jié)果的隱私保護(hù)問題，對于查詢結(jié)果的完整性驗證問題研究相對較少，特別是在兩層傳感器網(wǎng)絡(luò)中針對查詢結(jié)果完整性驗證的相關(guān)研究尚未見報道。而在實際應(yīng)用中，攻擊者不僅可能會窺探網(wǎng)絡(luò)內(nèi)部的隱私數(shù)據(jù)，同時還可能篡改或偽造數(shù)據(jù)，破壞查詢結(jié)果的完整性。因此，具有查詢結(jié)果完整性驗證能力的安全MAX/MIN查詢方法仍有待進(jìn)一步研究。

（2）抗共謀攻擊。由于WSN應(yīng)用環(huán)境中感知節(jié)點部署的規(guī)模性需求，感知節(jié)點通常是成本較低的資源受限設(shè)備，這就使得感知節(jié)點自身的安全防御能力受限，容易被攻擊者俘獲，并發(fā)起共謀攻擊。在諸多攻擊方法中，這種內(nèi)外結(jié)合的共謀攻擊往往更具有破壞性，研究具備較強(qiáng)抗共謀攻擊能力的安全MAX/MIN查詢方法是一個具有挑戰(zhàn)性的問題。

（3）安全性和通信代價的權(quán)衡和優(yōu)化。現(xiàn)有安全MAX/MIN查詢方法往往都權(quán)衡于安全保護(hù)能力和通信代價之間，通信代價的降低常伴隨著安全保護(hù)能力的降低，而安全性的提高往往又帶來通信代價的不斷增長。因此，針對安全性和通信代價的合理權(quán)衡和優(yōu)化的研究方案同樣具有實際應(yīng)用價值。

[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4):393-422.

[2]Gnawali O,Jang K Y,Paek J,et al.The Tenet architecture for tiered sensor networks[C]//Proceedings of the 4th International Conference on Embedded Networked Sensor Systems,Boulder,USA,Oct 31-Nov 3,2006.New York:ACM,2006:153-166.

[3]Liang Junbin,Jiang Chan,Ma Xingpo,et al.Secure data aggregation for top-k queries in tiered wireless sensor networks[J].Ad hoc&Sensor Wireless Networks,2016,32(2):51-78.

[4]Yu C M,NiGK,Chen I Y,et al.Top-query result completeness verification in tiered sensor networks[J].IEEE Transactions on Information Forensics and Security,2014,9(1):109-124.

[5]Zheng Jiping,Song Baoli,Wang Yongge,et al.Adaptive fil-ter updating for energy-efficient top-k queries in wireless sensor networks using Gaussian process regression[J].International Journal of Distributed Sensor Networks,2015:1-14.

[6]Li Guilin,Gao Xing,Liao Minghong,et al.An iterative algorithm to process the top-k query for the wireless sensor networks[J].International Journal of Embedded Systems,2015,7(1):26-33.

[7]Fan Yongjian,Chen Hong.Verifiable privacy-preserving topk query protocol in two-tiered sensor networks[J].Chinese Journal of Computers,2012,35(3):423-433.

[8]Dai Hua,Yang Geng,Huang Haiping,et al.Efficient verifiable top-k queries in two-tiered wireless sensor networks[J].KSII Transactions on Internet and Information Systems,2015,9(6):2111-2131.

[9]Ma Li,Liu Jingfa,Yao Yonglei.Privacy-preserving top-k query in two-tiered wireless sensor networks[J].International Journal of Advancements in Computing Technology,2012,4(6):226-235.

[10]Li Rui,Lin Yaping,Yi Yeqing,et al.Asecure top-k query protocol in two-tiered sensor networks[J].Journal of Computer Research and Development,2012,49(9):1947-1958.

[11]Huang Haiping,Feng Juan,Wang Ruchuan,et al.An exact top-k query algorithm with privacy protection in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2014:1-10.

[12]Dai Hua,Yang Geng,Qin Xiaolin,et al.Privacy-preserving top-k query processing in two-tiered wireless sensor networks[J].Journal of Computer Research and Development,2013,50(6):1239-1252.

[13]Ma Xingpo,Song Hong,Wang Jianxin,et al.Anovel verification scheme for fine-grained top-k queries in two-tiered sensor networks[J].Wireless Personal Communications,2014,75(3):1809-1826.

[14]Dai Hua,Yang Geng,Xiao Fu,et al.EVTQ:an efficient verifiable top-k query processing in two-tiered wireless sensor networks[C]//Proceedings of the 9th IEEE International Conference on Mobile Ad-hoc and Sensor Networks,Dalian,China,Dec 11-13,2013.Washington:IEEE Computer Society,2013:206-211.

[15]Liang Junbin,Ma Xingpo,Kui Xiaoyan.Research on data aggregation algorithms for top-k queries in query-drivenbased two-tiered sensor networks[J].Chinese Journal of Electronics,2014,42(10):2075-2080.

[16]Zhang Xiaoying,Dong Lei,Peng Hui,et al.Collusionaware privacy-preserving range query in tiered wireless sensor networks[J].Sensors,2014,14(12):23905-23932.

[17]Bu Jiajun,Yin Mingjian,He Daojing,et al.SEF:a secure,efficient,and flexible range query scheme in two-tiered sensor networks[J].International Journal of Distributed Sensor Networks,2011,7(4):876-879.

[18]Liao W H,Chen C C.Data storage and range query mechanism for multi-dimensional attributes in wireless sensor networks[J].IET Communications,2010,4(15):1799-1808.

[19]Dong Lei,Chen Xuan,Zhu Jianxiang,et al.Asecure collusionaware and probability-aware range query processing in tiered sensor networks[C]//Proceedings of the 34th IEEE Symposium on Reliable Distributed Systems,Montreal,Canada,Sep 28-Oct 1,2015.Washington:IEEE Computer Society,2015:110-119.

[20]Dong Lei,Zhu Jianxiang,Zhang Xiaoying,et al.SEMR:secure and efficient multi-dimensional range query processing in two-tiered wireless sensor networks[C]//LNCS 9098:Proceedings of the 16th International Conference on Web-Age Information Management,Qingdao,China,Jun 8-10,2015.Berlin,Heidelberg:Springer,2015:520-524.

[21]Chen Fei,LiuA X.Privacy and integrity-preserving range queries in sensor networks[J].IEEE/ACM Transactions on Networks,2012,20(6):1774-1787.

[22]Tsou Y T,Lu C S,Kuo S Y.Privacy-and integrity-preserving range query in wireless sensor networks[C]//Proceedings of the 2012 Global Communications Conference,Anaheim,USA,Dec 3-7,2012.Piscataway,USA:IEEE,2012:328-334.

[23]Zhang Xiaoying,Dong Lei,Peng Hui,et al.Achieving efficient and secure range query in two-tiered wireless sensor networks[C]//Proceedings of the 22nd International Symposium of Quality of Service,Hong Kong,China,May 26-27,2014.Piscataway,USA:IEEE,2014:380-388.

[24]Dai Hua,Ye Qingqun,Yi Xun,et al.VP2RQ:efficient verifiable privacy-preserving range query processing in twotiered wireless sensor networks[J].International Journal of Distributed Sensor Networks,2016,12(11).

[25]Yi Yeqing,Li Rui,Chen Fei,et al.Adigital watermarking approach to secure and precise range query processing in sensor networks[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications,Turin,Italy,Apr 14-19,2013.Piscataway,USA:IEEE,2013:1950-1958.

[26]Ertaul L,Kedlaya V.Computing aggregation function minimum/maximum using homomorphic encryption schemes in wireless sensor networks(WSNs)[C]//Proceedings of the 2007 International Conference on Wireless Networks,Las Vegas,USA,Jun 25-28,2007.USA:CSREA Press,2007:186-192.

[27]Groat M M,He Wenbo,Forrest S.KIPDA:k-indistinguishable privacy-preserving data aggregation in wireless sensor networks[C]//Proceedings of the 30th International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies,Shanghai,Apr 10-15,2011.Piscataway,USA:IEEE,2011:2024-2032.

[28]Chen C M,Lin Y H,Lin Y C,et al.RCDA:recoverable concealed data aggregation for data integrity in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,23(4):727-734.

[29]Yao Yonglei,Ma Li,Liu Jingfa.Privacy-preserving MAX/MIN aggregation in wireless sensor networks[J].Advances in Information Sciences&Service Sciences,2012,4(6):272-280.

[30]SamanthulaBK,Jiang Wei,Madria S.Aprobabilistic encryption based MIN/MAX computation in wireless sensor networks[C]//Proceedings of the 14th International Conference on Mobile Data Management,Milan,Italy,Jun 3-6,2013.Washington:IEEE Computer Society,2013:77-86.

[31]Boudia OR M,Senouci S M,Feham M.Anovel secure aggregation scheme for wireless sensor networks using stateful public key cryptography[J].Ad Hoc Networks,2015,32(C):98-113.

[32]Yao Y,Xiong N,Park J H,et al.Privacy-preserving max/min query in two-tiered wireless sensor networks[J].Computers&Mathematics with Applications,2013,65(9):1318-1325.

[33]Dai Hua,Yang Geng,Qin Xiaolin.EMQP:an energy-efficient privacy-preserving MAX/MIN query in two tiered sensor networks[J].International Journal of Distributed Sensor Networks,2013,2013(1):1492-1519.

[34]Dai Hua,Wei Tianyi,Huang Yue,et al.Random secure comparator selection based privacy-preserving MAX/MIN query processing in two-tiered sensor networks[J].Journal of Sensors,2016,6:1-13.

[35]Liu Honghui,Liu Shubo,Liu Mengjun,et al.Efficient random modulation privacy-preserving MAX/MIN query protocol in two-tiered wireless sensor networks[J].Computer Science,2014,41(12):95-100.

[36]Madden S,Franklin M J,Hellerstein J M,et al.TAG:a tiny aggregation service for ad-hoc sensor networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.

[37]Heinzelman,R W,ChandrakasanA,Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,Maui,USA,Jan 4-7,2000.Washington:IEEE Computer Society,2000:1-10.

[38]Bo?ovi? V,Socek D,SteinwandtR,et al.Multi-authority attribute-based encryption with honest-but-curious central authority[J].International Journal of Computer Mathematics,2009,3:268-283.

[39]Domingo-Ferrer J.Aprovably secure additive and multiplicative privacy homomorphism[C]//LNCS 2433:Proceedings of the 5th International Conference on Information Security,Sao Paulo,Brazil,Sep 30-Oct 2,2002.Berlin,Heidelberg:Springer,2002:471-483.

[40]Mykletun E,Girao J,Westhoff D.Public key based cryptoschemes for data concealment in wireless sensor networks[C]//Proceedings of the 2006 International Conference on Communications,Istanbul,Turkey,Jun 11-15,2006.Washington:IEEE Computer Society,2006:2288-2295.

[41]DanB,Gentry C,LynnB,et al.Aggregate and verifiably encrypted signatures from bilinear maps[C]//LNCS 2656:Proceedings of the 2003 International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology,Warsaw,Poland,May 4-8,2003.Berlin,Heidelberg:Springer,2003:416-432.

[42]Cheng J,Yang Hao,Wong S H Y,et al.Design and implementation of cross-domain cooperative firewall[C]//Proceedings of the 2007 International Conference on Network Protocols,Beijing,Oct 16-19,2007.Washington:IEEE Computer Society,2007:284-293.

[43]LiuA X,Chen Fei.Collaborative enforcement of firewall policies in virtual private networks[C]//Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing,Toronto,Canada,Aug 18-21,2008.New York:ACM,2008:95-104.

[44]Krawczyk H,CanettiR,Bellare M.HMAC:keyed-hashing for message authentication[R].RFC Editor,1997.

[45]Goldwasser S,Micali S.Probabilistic encryption[J].Journal of Computer and System Sciences,1984,28(2):270-299.

[46]Chen L.Recommendation for key derivation using pseudorandom functions[J].National Institute of Standards and Technology:Special Publication,2008,800:108.

[47]Lin H Y,Tzeng W G.An efficient solution to the Millionaires'problem based on homomorphic encryption[C]//LNCS 3531:Proceedings of the 3rd International Conference on Applied Cryptography and Network Security,New York,Jun 7-10,2005.Berlin,Heidelberg:Springer,2005:456-466.

[48]Yang Geng,Wang Jiangtao,Cheng Hongbing,et al.Akey establish scheme for WSN based on IBE and Diffie-Hellman algorithms[J].Acta Electronica Sinica,2007,35(1):180-184.

附中文參考文獻(xiàn)：

[7]范永健,陳紅.兩層傳感器網(wǎng)絡(luò)可驗證Top-k查詢處理協(xié)議[J].計算機(jī)學(xué)報,2012,35(3):423-433.

[10]李睿,林亞平,易葉青,等.兩層傳感器網(wǎng)絡(luò)中的安全Top-k查詢協(xié)議[J].計算機(jī)研究與發(fā)展,2012,49(9):1947-1958.

[12]戴華,楊庚,秦小麟,等.面向隱私保護(hù)的兩層傳感網(wǎng)Topk查詢處理方法[J].計算機(jī)研究與發(fā)展,2013,50(6):1239-1252.

[15]梁俊斌,馬行坡,奎曉燕.查詢驅(qū)動模式下兩層傳感器網(wǎng)絡(luò)Top-k查詢匯聚算法研究[J].電子學(xué)報,2014,42(10):2075-2080.

[35]劉泓暉,劉樹波,劉夢君,等.面向兩層WSNs的高效隨機(jī)調(diào)制隱私保護(hù)最值查詢協(xié)議[J].計算機(jī)科學(xué),2014,41(12):95-100.

[48]楊庚,王江濤,程宏兵,等.基于身份加密的無線傳感器網(wǎng)絡(luò)密鑰分配方法[J].電子學(xué)報,2007,35(1):180-184.

Survey of Secure MAX/MIN Query Processing in Wireless Sensor Networks*

DAI Hua1,2+,WANG Min1,YI Xun3,YANG Geng1,2,YE Qingqun1
1.School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
2.Jiangsu Key Laboratory of Big Data Security and Intelligent Processing,Nanjing 210023,China
3.School of Science,Royal Melbourne Institute of Technology University,Melbourne 3000,Australia
+Corresponding author:E-mail:daihua@njupt.edu.cn

DAI Hua,WANG Min,YI Xun,et al.Survey of secure MAX/MIN query processing in wireless sensor networks.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1191-1203.

With the development of wireless sensor networks(WSNs),the secure data queries which have the ability of privacy preserving and completeness protection are demanded urgently,such as the secure MAX/MIN queries.The existing secure MAX/MIN queries are mostly based on honest-but-curious threat model and focus on protecting the privacy of sensor data and query result from attacks,but they less consider the problem of incomplete result caused by data tampering or forgery.From the perspectives of privacy protecting and result completeness verification,this paper summarizes the existing secure MAX/MIN query technologies in the traditional WSNs and twotiered WSNs,respectively.This paper firstly introduces the common query model and network models,and gives the detailed problem descriptions of privacy-preserving and completeness-protection in WSNs.Then,this paper dis-cusses the key technologies and protocols proposed in the existing works,and analyzes their advantages and disadvantages.Finally,this paper points out the future research directions according to the analysis and conclusion.

wireless sensor networks;MAX/MIN query;privacy preserving;completeness verification

2016-11,Accepted 2017-04.

DAI Hua was born in 1982.He is an associate professor at Nanjing University of Posts and Telecommunications,and the member of CCF.His research interests include data management and security and database security,etc.戴華（1982—），男，江蘇鹽城人，南京郵電大學(xué)計算機(jī)學(xué)院副教授，CCF會員，主要研究領(lǐng)域為數(shù)據(jù)管理與安全，數(shù)據(jù)庫安全等。

WANG Min was born in 1992.She is an M.S.candidate at Nanjing University of Posts and Telecommunications.Her research interest is data management and security in wireless sensor networks.王敏（1992—），女，江蘇淮安人，南京郵電大學(xué)碩士研究生，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)數(shù)據(jù)管理與安全。

YI Xun was born in 1967.He is a professor and Ph.D.supervisor at Royal Melbourne Institute of Technology University.His research interests include information security and distributed data processing,etc.易訓(xùn)（1967—），男，湖北孝感人，澳大利亞墨爾本皇家理工大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為信息安全，分布式數(shù)據(jù)處理等。

YANG Geng was born in 1961.He is a professor and Ph.D.supervisor at Nanjing University of Posts and Telecommunications,and the senior member of CCF.His research interests include cloud computing and security,data security and privacy protection,etc.楊庚（1961—），男，江蘇建湖人，南京郵電大學(xué)教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域為云計算與安全，數(shù)據(jù)安全，隱私保護(hù)等。

YE Qingqun was born in 1992.She is an M.S candidate at Nanjing University of Posts and Telecommunications.Her research interest is data management and security in wireless sensor networks.葉慶群（1992—），女，安徽安慶人，南京郵電大學(xué)碩士研究生，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)數(shù)據(jù)管理與安全。

A

：TP393

*The National Natural Science Foundation of China under Grant Nos.61300240,61402014,61472193,61572263,61502251,61502243(國家自然科學(xué)基金);the Natural Science Foundation of Jiangsu Province under Grant Nos.BK20151511,BK20141429,BK20161516(江蘇省自然科學(xué)基金面上項目);the Project of Natural Science Research of Jiangsu University under Grant Nos.14KJB520027,15KJB520027(江蘇省高校自然科學(xué)基金面上項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-04-24,http://kns.cnki.net/kcms/detail/11.5602.TP.20170424.1757.006.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1191-13

10.3778/j.issn.1673-9418.1611028

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056