無線傳感器網(wǎng)絡隱私保護范圍查詢處理技術

張曉瑩，董 蕾，陳 紅

（1．中國人民大學 信息學院，北京 100872；2．中國人民大學 數(shù)據(jù)工程與知識工程國家教育部重點實驗室，北京 100872）

0 引 言

無線傳感器網(wǎng)絡（以下簡稱傳感器網(wǎng)絡）是由大量微型傳感器節(jié)點通過自組織的方式形成的多跳分布式網(wǎng)絡系統(tǒng)，通過傳感器節(jié)點感知、計算和傳輸數(shù)據(jù)，為人們提供服務．作為物聯(lián)網(wǎng)的重要組成部分，傳感器網(wǎng)絡被廣泛應用在軍民重要領域，允許人們在任何時間、地點和環(huán)境下獲取大量重要信息．隨著傳感器網(wǎng)絡的不斷發(fā)展，在多個關鍵性領域的實際應用與部署過程中暴露出嚴重的隱私問題．例如在智能電網(wǎng)領域，不法分子通過截獲家庭用電信息推測出家里是否有人、何時無人等家庭敏感信息；在智慧醫(yī)療領域，醫(yī)生通過醫(yī)療傳感器隨時查詢患者的體溫、血壓、心率等重要體征數(shù)據(jù)，這些數(shù)據(jù)可能被非法人員竊取，造成患者隱私泄露；在軍事國防領域，無線傳感器被部署在重要的軍事監(jiān)控區(qū)域收集各種情報信息，這些情報信息一旦被敵軍竊取或篡改，將導致重大決策失誤．這些暴露出的隱私問題會泄露用戶和監(jiān)測對象的重要信息，甚至威脅到用戶和監(jiān)測對象的安全，極大地阻礙了傳感器網(wǎng)絡的廣泛應用．因此，研究傳感器網(wǎng)絡隱私保護技術，對傳感器網(wǎng)絡和物聯(lián)網(wǎng)的發(fā)展具有積極的推動意義．

隱私保護范圍查詢處理技術由Sheng［1］等人于2008年提出．目前，隱私保護范圍查詢處理技術已經(jīng)成為新的研究熱點．隱私保護范圍查詢處理技術的主要目標是：在范圍查詢處理的過程中，有效控制非法用戶對網(wǎng)絡敏感信息的訪問，防止網(wǎng)絡敏感信息的泄露，同時，盡量減少能量消耗，降低對通訊信道的占用，提高查詢結(jié)果的精確度和可靠性．然而傳感器網(wǎng)絡自身所具有的資源受限、分布式等特征，給隱私保護范圍查詢處理技術研究帶來了極大的挑戰(zhàn)．

（1）節(jié)點能量有限是傳感器網(wǎng)絡的一大特點，網(wǎng)絡剩余能量直接影響網(wǎng)絡生命周期．研究［2］表明節(jié)點之間的通信是消耗能量的主要因素，高通信量的隱私保護技術并不適合傳感器網(wǎng)絡．因此，如何實現(xiàn)低通信量的隱私保護技術，最大程度地減少能量消耗，提高感知節(jié)點的壽命，是研究傳感器網(wǎng)絡隱私保護范圍查詢處理技術面臨的首要挑戰(zhàn)．

（2）傳感器節(jié)點是一種微型嵌入式設備，攜帶的處理器和存儲器能力較弱，這使得計算復雜和存儲成本高的隱私保護技術并不符合傳感器網(wǎng)絡的實際要求．因此，如何實現(xiàn)低計算量的隱私保護技術是研究傳感器網(wǎng)絡隱私保護范圍查詢處理技術面臨的另一個嚴峻挑戰(zhàn)．

（3）傳感器網(wǎng)絡是一個開放的網(wǎng)絡系統(tǒng)，傳感器節(jié)點一般通過飛機播散等方式被隨機部署到無人值守的環(huán)境中，無法預料傳感器節(jié)點的位置、鄰居節(jié)點等信息．此外，攻擊者的攻擊能力日漸強大，攻擊方式日趨多樣，因此，如何提高隱私保護技術的健壯性，抵御多種攻擊，是研究傳感器網(wǎng)絡隱私保護范圍查詢處理技術面臨的重要挑戰(zhàn)．

本文對現(xiàn)有的傳感器網(wǎng)絡隱私保護范圍查詢研究成果進行了系統(tǒng)總結(jié)，對代表協(xié)議的核心技術進行了較詳細的闡述，對比分析了各協(xié)議的優(yōu)缺點，并展望了未來需要深入研究的方向．

1 研究模型

1．1 網(wǎng)絡模型

現(xiàn)有的隱私保護范圍查詢協(xié)議主要基于兩層傳感器網(wǎng)絡［3］．如圖1所示，在兩層傳感器網(wǎng)絡中，大量的傳感器節(jié)點位于網(wǎng)絡的下層，少量的管理節(jié)點（Master Node，又稱為存儲節(jié)點）位于網(wǎng)絡的上層．管理節(jié)點是基站與傳感器節(jié)點之間的一座“橋梁”．基站將用戶命令下發(fā)到管理節(jié)點，傳感器節(jié)點進行周期性采樣并定期將感知數(shù)據(jù)發(fā)送到最近的管理節(jié)點．管理節(jié)點負責存儲管轄范圍內(nèi)的傳感器節(jié)點數(shù)據(jù)和執(zhí)行基站的命令．相比于傳感器節(jié)點，基站和管理節(jié)點都是高資源節(jié)點，其資源不受限制．

兩層的傳感器網(wǎng)絡具有以下優(yōu)點：

（1）節(jié)省傳感器節(jié)點的資源．傳感器節(jié)點的能量、計算能力、存儲空間等都非常有限．在兩層傳感器網(wǎng)絡中，傳感器節(jié)點不需要存儲大量歷史數(shù)據(jù)、發(fā)送數(shù)據(jù)到基站和執(zhí)行復雜的查詢?nèi)蝿?，這些任務均由管理節(jié)點負責完成，大大降低傳感器節(jié)點的存儲成本、通信開銷和計算代價，從而延長網(wǎng)絡的生命周期．

（2）縮短查詢的響應時間．管理節(jié)點存儲著大量傳感器節(jié)點數(shù)據(jù)，并且其計算能力和存儲空間不受限制，因而能夠更加高效地完成用戶的查詢?nèi)蝿?，快速返回查詢結(jié)果．

（3）增強網(wǎng)絡的可擴展性．引入管理節(jié)點后，整個網(wǎng)絡按照管理節(jié)點被分成許多子網(wǎng)．每個子網(wǎng)由一個管理節(jié)點和若干傳感器節(jié)點組成，不同子網(wǎng)中的傳感器節(jié)點可以是異構(gòu)的，每個子網(wǎng)獨立運行．

1．2 攻擊模型

根據(jù)已有的研究成果，我們將攻擊者的攻擊方式大致分為三類：竊聽攻擊、篡改攻擊和共謀攻擊．大部分隱私保護范圍查詢協(xié)議主要抵御前兩類攻擊，少量協(xié)議能夠抵御第三類攻擊．

（1）竊聽攻擊

攻擊者通過竊聽節(jié)點之間的無線通信鏈路獲取網(wǎng)絡節(jié)點的敏感信息．在竊聽攻擊中，攻擊者只關注敏感信息的內(nèi)容，不會改變敏感信息．

（2）篡改攻擊

攻擊者通過俘獲網(wǎng)絡節(jié)點向網(wǎng)絡中注入虛假信息、惡意改變或刪除真實信息等方式以達到影響最終結(jié)果的目的．在篡改攻擊中，攻擊者試圖改變敏感信息，因此篡改攻擊對網(wǎng)絡安全的威脅更大，需要更強的保護手段．

（3）共謀攻擊

隨著攻擊者破壞能力的不斷增強，攻擊者可以同時俘獲多個節(jié)點，并控制這些被俘獲節(jié)點進行合作共謀從而破壞網(wǎng)絡的安全性．相對于非共謀攻擊，共謀攻擊對網(wǎng)絡安全的危害性更大．

1．3 性能評價模型

評價隱私保護范圍查詢協(xié)議的性能指標主要有4類：隱私性、完整性、高效性和精確性．

（1）隱私性

傳感器網(wǎng)絡中的敏感信息多種多樣，例如節(jié)點數(shù)據(jù)、中間結(jié)果、最終結(jié)果或用戶查詢．隱私性要求保護敏感信息不被非法用戶獲?。舾行畔⒌拇_定與應用相關．在隱私保護范圍查詢處理技術研究中，敏感信息通常指傳感器節(jié)點的感知數(shù)據(jù)和用戶的查詢命令．

（2）完整性

傳感器網(wǎng)絡是一個自組織多跳的網(wǎng)絡系統(tǒng)，感知數(shù)據(jù)從采集節(jié)點到基站往往需要經(jīng)過其他中間節(jié)點的轉(zhuǎn)發(fā)，還可能需要進行輕量級的計算．完整性要求感知數(shù)據(jù)被真實轉(zhuǎn)發(fā)和正確計算．完整性直接影響最終查詢結(jié)果，因此完整性通常是指結(jié)果完整性，即基站收到的最終結(jié)果應該包含真實的結(jié)果，禁止攻擊者惡意改變、刪除結(jié)果和注入非法信息．

（3）高效性

傳感器網(wǎng)絡的能量有限，網(wǎng)絡剩余能量直接影響網(wǎng)絡的生命周期．研究結(jié)果［2］顯示節(jié)點通信和計算，特別是節(jié)點通信，是消耗能量的主要因素．為了延長網(wǎng)絡的生命周期，高效性要求協(xié)議盡可能降低通信成本和計算代價．

（4）精確性

給定用戶命令，網(wǎng)絡按照協(xié)議執(zhí)行操作、計算結(jié)果．理想的情況下真實結(jié)果與計算所得結(jié)果是等價的．為了實現(xiàn)隱私性、完整性和高效性，有時會犧牲一定的結(jié)果精度．精確性要求協(xié)議在滿足隱私性、完整性和高效性的前提下，結(jié)果應該在可接受的誤差范圍內(nèi)盡可能精確．

2 隱私保護范圍查詢處理技術

現(xiàn)有隱私保護范圍查詢協(xié)議主要采用的隱私保護技術包括：桶技術、前綴成員驗證技術和保序加密技術．此外，還有其他隱私保護技術，如Z-O編碼技術、BF編碼技術和矩陣變換技術．

2．1 桶技術

桶技術（Bucketing Scheme）［4-5］將值域劃分成若干連續(xù)不相交的區(qū)間．每個區(qū)間可以看作是一個只存放指定取值范圍數(shù)據(jù)的桶，使用一個或多個桶表示敏感信息．

文獻［1，6］采用桶技術和編碼策略（Encoding Scheme）保護范圍查詢中的隱私性和完整性．協(xié)議主要思想是：使用一個桶集合表示用戶查詢和節(jié)點數(shù)據(jù)．具體方法如下：令Tagi表示桶i的桶號，Bi表示桶i的取值范圍．用戶查詢范圍［a，b］被表示成一個桶號集合｛Tag1，Tag2，…，Tagm｝，其中，［a，b］?B1∪B2∪…∪Bm，且B1∪B2∪…∪Bm是能覆蓋［a，b］的最小桶集合，即對于任意的Bi（1≤i≤m），都滿足［a，b］∩Bi≠?．基站將查詢范圍的桶集合下發(fā)到存儲節(jié)點，數(shù)據(jù)d被轉(zhuǎn)換成桶號Tagj，滿足d∈Bj．節(jié)點使用與基站共享的密鑰加密數(shù)據(jù)，并與對應的桶號一起發(fā)送到存儲節(jié)點．判斷d∈［a，b］是否成立，只需判斷Tagj∈｛Tag1，Tag2，…，Tagm｝是否成立．判斷過程在存儲節(jié)點上進行，桶技術允許存儲節(jié)點在不獲取敏感信息的情況下完成查詢．為了保證基站檢測出被篡改的查詢結(jié)果，節(jié)點si需要為t時刻的每個空桶j構(gòu)造一個碼（Encoding Nu mber），即nu m（i，j，t）．基站通過此碼判斷查詢結(jié)果的完整性．桶技術本質(zhì)上是一種泛化技術，即用粗粒度的信息代替精確的信息，因此會導致查詢結(jié)果存在誤識別（False Positive）．桶技術雖然沒有直接泄露敏感信息，但是會泄露敏感信息的范圍，并且隱私保護程度與桶的劃分粒度有關，粒度越粗，隱私性越高，但通信代價越大，結(jié)果誤識別率越高．

文獻［7-8］使用文獻［1］中的桶技術實現(xiàn)隱私保護，并提出一種時空交叉驗證技術（Spatiotemporal Cr osscheck Technique）檢驗結(jié)果的完整性．時空交叉驗證技術包括空間交叉驗證策略（Spatial Cr osscheck Appr oach）和時間交叉驗證策略（Temporal Cr osscheck Approach）．空間交叉驗證策略利用節(jié)點之間的關系，為每個節(jié)點si構(gòu)造一個位圖Vi，t，表示si在t時刻的數(shù)據(jù)分布情況．si將位圖消息＜i，Vi，t＞發(fā)送給選擇的節(jié)點．收到位圖消息的節(jié)點將其附加到自己的每一個非空桶中與數(shù)據(jù)一起上傳到存儲節(jié)點．文獻［7］給出兩種節(jié)點選擇方法：一種基于子網(wǎng)廣播，另一種基于鄰居節(jié)點，研究表明基于子網(wǎng)廣播的選擇方法傳輸位圖所需的通信量遠高于基于鄰居節(jié)點的選擇方法，但前者的不完整結(jié)果檢測率高于后者．為了平衡節(jié)點通信量和不完整結(jié)果檢測率，文獻［8］提出一種混合節(jié)點選擇方法．時間交叉驗證策略利用數(shù)據(jù)之間的關系，每個節(jié)點si構(gòu)造一個緩沖區(qū)（Buffer）記錄最近I個連續(xù)提交周期的數(shù)據(jù)分布情況，并將其附加到每一個非空桶中．由于引入額外的時空信息，時空交叉驗證技術的通信代價較高．

文獻［9］研究了兩層傳感器網(wǎng)絡中的安全多維范圍查詢處理技術．為了保護用戶查詢和節(jié)點數(shù)據(jù)的隱私，將文獻［1］中的桶技術擴展到多維數(shù)據(jù)空間，并提出三種完整性驗證策略，分別是：編碼策略（Encoding）、概率空間交叉驗證策略（Probabilistic Spatial Crosscheck）和概率時間交叉驗證策略（Pr obabilistic Temporal Cr osscheck）．第一種驗證策略是文獻［1］的編碼策略在多維數(shù)據(jù)空間的擴展，后兩種驗證策略是對文獻［7］的時空交叉驗證技術的概率化，即并不是將所有其他節(jié)點的位圖消息和自己的緩沖區(qū)信息附加到所有非空桶中，而是以一定的概率選擇性地附加這些驗證信息．顯然，這種概率性的驗證策略不能100%檢測出不完整結(jié)果．

2．2 前綴成員驗證技術

前綴成員驗證技術（Prefix Membership Verification）最早應用于跨域協(xié)作防火墻（Cr oss-Do main Cooperative Firewall）領域，允許位于不同網(wǎng)絡管理域的防火墻在不知道對方規(guī)則的情況下協(xié)同執(zhí)行各自規(guī)則并過濾數(shù)據(jù)包．文獻［10］首次提出前綴成員驗證技術，文獻［11］對其進行了改進．前綴成員驗證技術根據(jù)規(guī)則判斷一個數(shù)值x和一個前綴P的成員關系：如果x∈P，當且僅當P∈PF（x），PF（x）是x的前綴族．

Safe Q協(xié)議［12-13］采用前綴成員驗證技術實現(xiàn)兩層網(wǎng)絡中的隱私保護范圍查詢．Saf e Q的核心思想：分別為用戶查詢和節(jié)點數(shù)據(jù)構(gòu)建一個特殊集合，將數(shù)值與區(qū)間的成員關系判斷轉(zhuǎn)化為兩個集合交集是否為空的判斷．具體過程：給定一個整數(shù)d，其二進制表示為b1b2…bw（bi∈｛0，1｝），d的第i個前綴表示為b1b2…bw－i＋1*…*，d的前綴族F（d）被定義為一個包含d的第0個至第w個前綴的集合，即F（d）＝｛b1b2…bw，b1b2…bw－1*，…，b1*…*，*…*｝．給定一個查詢范圍［a，b］，其前綴碼S（［a，b］）被定義為能夠覆蓋［a，b］中所有整數(shù)的前綴的最小集合．令N（）為數(shù)字化函數(shù)，對F（d）和S（［a，b］）進行數(shù)字化處理，即依次將F（d）和S（［a，b］）中的“*”用“1”替換，并在第一個“0”位前添加“1”，得到N（F（d））和N（S（［a，b］））．存儲節(jié)點判斷d是否屬于［a，b］，只需判斷是否滿足N（F（d））∩N（S（［a，b］））≠?．圖2演示了Safe Q判斷12是否屬于［11，14］的過程．為了提高存儲節(jié)點的查詢效率，節(jié)點在上傳數(shù)據(jù)前對數(shù)據(jù)進行升序排列，存儲節(jié)點只需找到滿足判定條件的數(shù)據(jù)上下界．考慮到存儲節(jié)點可能被攻擊者俘獲從而破壞結(jié)果的完整性，Safe Q設計了一種鄰居關系鏈（Neighbor hood Chain），要求每個節(jié)點在上傳數(shù)據(jù)時為每個數(shù)據(jù)項附加其在本提交周期產(chǎn)生的有序數(shù)據(jù)集中對應的最近左數(shù)據(jù)項，通過檢查鄰居關系鏈的數(shù)據(jù)有序性和連續(xù)性驗證結(jié)果的完整性．前綴成員驗證技術可以避免桶技術泄露粗粒度信息的問題，同時得到精確的查詢結(jié)果．除了數(shù)據(jù)鄰居鏈，文獻［13］還構(gòu)建了Mer kle哈希樹（Mer kle Hash Tree）［15］驗證結(jié)果．由于前綴成員驗證技術將一個數(shù)值轉(zhuǎn)換成一個集合，因此增加了節(jié)點的通信量．

2．3 保序加密技術

保序加密技術（Order-preserving Encryption）是一種確定性的加密機制，依賴于特定的保序加密函數(shù)實現(xiàn)．一個數(shù)據(jù)空間經(jīng)過保序加密函數(shù)處理后被映射到另一個數(shù)據(jù)空間，假設原數(shù)據(jù)空間中的任意兩個不相等的數(shù)據(jù)d1和d2分別對應于新數(shù)據(jù)空間中數(shù)據(jù)D1和D2且d1≠D1，d2≠D2，如果d1＞d2，那么必有D1＞D2，即新數(shù)據(jù)空間中數(shù)據(jù)仍然保持原數(shù)據(jù)空間中的大小關系［14］．保護加密技術最早由文獻［16］提出，一個保序加密函數(shù)被認為是安全的當且僅當攻擊者只有通過窮舉攻擊才能破解密文．因此，保序加密技術的安全程度取決于保序加密函數(shù)的復雜程度，函數(shù)越復雜，安全性越高．

SEF協(xié)議［17］提供傳感器網(wǎng)絡中的安全范圍查詢．為了保護隱私性，SEF使用保序?qū)ΨQ加密技術（Or der-preser ving Sy mmetric Encr yption，OPSE）［14］在不泄露敏感信息的情況下保證范圍查詢的順利執(zhí)行．為了保護結(jié)果的真實性和完整性，SEF設計出一種數(shù)據(jù)結(jié)構(gòu)——AI樹（Authenticity＆Integrity Tree）對查詢結(jié)果進行驗證．SEF協(xié)議分為3部分：傳感器節(jié)點處理、管理節(jié)點處理和基站處理．在傳感器節(jié)點上，假設采集到N個數(shù)據(jù)d1，…，dN，首先使用OPSE對N＋2個數(shù)據(jù)d0，d1，…，dN，dN＋1（d0／dN＋1分別是值域的最大／小值）加密處理得到e0，…，eN＋1，然后排序加密數(shù)據(jù)項并自下而上構(gòu)造一棵AI樹．在AI樹中，葉子節(jié)點存儲加密數(shù)據(jù)項，中間節(jié)點和根節(jié)點存儲孩子節(jié)點的摘要值（Digest）和兩個標簽（Label），一個標簽記錄節(jié)點在樹中的層次（Level），另一個標簽記錄該節(jié)點在父節(jié)點中的位置．圖3是一棵AI樹，節(jié)點采集到9個數(shù)據(jù)項（不包括d0和dN＋1），這些數(shù)據(jù)項在AI樹中按照升序排列．h4－5表示該節(jié)點存儲了e4和e5的摘要信息，位于樹的第1層，是其父節(jié)點的左孩子．這棵AI樹的HMAC＝h0－10．為了減少通信開銷，節(jié)點只將HMAC和加密數(shù)據(jù)項發(fā)送到管理節(jié)點．管理節(jié)點根據(jù)加密數(shù)據(jù)項重構(gòu)節(jié)點的AI樹．用戶查詢范圍使用同樣的OPSE處理．當收到來自基站的范圍查詢，管理節(jié)點檢查傳感器節(jié)點的數(shù)據(jù)，將落在查詢范圍的加密數(shù)據(jù)項和相應的上下界作為結(jié)果返回基站．此外，存儲節(jié)點還需要返回該節(jié)點的驗證對象（Verification Object，VO），用于驗證結(jié)果的真實性和完整性．VO包括3部分：該節(jié)點AI樹的H MAC；從根節(jié)點到下邊界父節(jié)點所經(jīng)過節(jié)點的左兄弟節(jié)點摘要值；從根節(jié)點到上邊界父節(jié)點所經(jīng)過節(jié)點的右兄弟節(jié)點摘要值．當基站收到管理節(jié)點返回的結(jié)果，首先根據(jù)摘要值重構(gòu)AI樹和H MAC，并與收到的H MAC進行比較，若相等，則結(jié)果是真實完整的，否則結(jié)果無效．以圖3為例，當結(jié)果為｛e5，e6，e7，e8｝時，VO＝｛h0－3，h4，h9，h10｝．基站根據(jù)h4和h5重構(gòu)出h4－5，使用同樣的方法重構(gòu)出h6－7、h8－9、h4－7、h8－10、h0－7．最終重構(gòu)出h0－10．基站比較重構(gòu)的h0－10是否等于收到的HMAC，從而判斷結(jié)果的真實性和完整性．

圖3 AI樹的例子Fig．3 An example of AI tree

EQ協(xié)議［18］向傳感器網(wǎng)絡中引入云節(jié)點作為存儲節(jié)點，使用順序加密機制（Or der Encryption Mechanism，OEM）防止敏感信息泄露，構(gòu)造位圖表（Bit-Map Table，BM）和異或鏈表（XOR Linked List，X2L）驗證結(jié)果的完整性．與SEF協(xié)議一樣，EQ協(xié)議也分為3個部分：傳感器節(jié)點處理、管理節(jié)點處理和基站處理．傳感器節(jié)點在上傳數(shù)據(jù)之前需要執(zhí)行4個步驟：①將感知數(shù)據(jù)映射到有序區(qū)間中；②根據(jù)感知數(shù)據(jù)的坐標（區(qū)間，位置）構(gòu)建BM表，并計算出BM值；③在每個感知數(shù)據(jù)中加入左右鄰居數(shù)據(jù)，得到X2L，并使用OEM加密；④將節(jié)點號、時間信息和加密數(shù)據(jù)一起發(fā)送到云節(jié)點．基站也使用相同的OEM機制加密查詢范圍，并下發(fā)到云節(jié)點．云節(jié)點根據(jù)加密的查詢范圍和感知數(shù)據(jù)執(zhí)行查詢?nèi)蝿眨⒎祷夭樵兘Y(jié)果．當節(jié)點的感知數(shù)據(jù)不符合查詢要求時，要求云節(jié)點上傳該節(jié)點的BM值．基站解密數(shù)據(jù)，根據(jù)X2L和BM值判斷結(jié)果是否完整．圖4演示了EQ協(xié)議的執(zhí)行過程．

文獻［19］結(jié)合保序函數(shù)（Order-preserving Function）、置換函數(shù)（Per mutation Function）和d-階分離矩陣（d-disj unct Matrix）實現(xiàn)兩層傳感器網(wǎng)絡中的隱私保護范圍查詢，但忽略了結(jié)果被篡改的情況．在協(xié)議中，基站為所有傳感器節(jié)點構(gòu)造相同的保序函數(shù)p、置換函數(shù)σ和d階分離矩陣M＝（M1，M2，…，Mn）．假設節(jié)點在t時刻采集到一系列數(shù)據(jù)D＝｛d1，d2，…，dm｝，允許出現(xiàn)重復數(shù)據(jù)．節(jié)點首先使用保序函數(shù)處理數(shù)據(jù)得到σ（D）＝｛σ（d1），σ（d2），…，σ（dm）｝，σ（D）去除重復元素，然后使用置換函數(shù)處理數(shù)據(jù)得到p（D）＝｛p（d1），p（d2），…，p（dm）｝，p（D）保留重復元素，最后根據(jù)d階分離矩陣，計算出列向量C節(jié)點將C和σ（D）發(fā)送到存儲節(jié)點．基站使用相同的保序函數(shù)σ將查詢范圍［a，b］轉(zhuǎn)換為｛Qmin，Qmax｝，其中，Qmin＝min｛σ（d）∣d∈［a，b］｝，Qmax＝max｛σ（d）∣d∈［a，b］｝．存儲節(jié)點根據(jù)｛Qmin，Qmax｝和σ（D）確定滿足條件的數(shù)據(jù)集D′，并將D′和C返回基站．基站根據(jù)D′、C＝（c1，c2，…，cm）T和M＝（M1，M2，…，Mn）求解出D′中每個數(shù)據(jù)的頻數(shù)．d-階分離矩陣在傳感器節(jié)點上存儲需要額外空間．當查詢范圍較大時，根據(jù)C和A確定唯一結(jié)果的計算復雜度較高．

圖4 EQ協(xié)議的執(zhí)行過程Fig．4 Process of EQ

文獻［20-21］提出一種支持隱私性與完整性保護的范圍查詢協(xié)議．為了保護敏感信息的隱私性，協(xié)議使用數(shù)據(jù)區(qū)間表示感知數(shù)據(jù)和查詢范圍，并基于多項式技術構(gòu)造保序加密函數(shù)和查詢函數(shù)分別保護感知數(shù)據(jù)和查詢范圍．傳感器節(jié)點將保序加密后的數(shù)據(jù)發(fā)送到存儲節(jié)點．基站將查詢條件轉(zhuǎn)換為一個與傳感器節(jié)點ID相關的查詢條件后發(fā)送到存儲節(jié)點．存儲節(jié)點分別為每個提交數(shù)據(jù)的傳感器節(jié)點計算查詢條件，并完成查詢?nèi)蝿眨疄榱吮Ｗo結(jié)果的完整性，協(xié)議采用數(shù)字水印技術（Digital Water marking），為數(shù)據(jù)區(qū)間構(gòu)建一條水印鏈，基站借助該水印鏈可以驗證結(jié)果是否真實可靠．文獻［20-21］還提出一種數(shù)據(jù)結(jié)構(gòu)——多維區(qū)間樹（Multi-Di mensional Range Tree，MDRT）實現(xiàn)隱私保護多維范圍查詢，同時構(gòu)造多條水印鏈保護結(jié)果完整性．對于存儲空間和計算能力有限的傳感器節(jié)點，MDRT需要額外的存儲空間，并且構(gòu)造復雜．

2．4 其他隱私保護技術

ZOSR協(xié)議［22］采用R-D判別方法（又稱為半徑距離判別法）和Z-O編碼比較技術（又稱為0-1編碼比較技術）［23］實現(xiàn)隱私保護范圍查詢．R-D判別方法將數(shù)值與查詢區(qū)間上下邊界的比較轉(zhuǎn)化為該數(shù)值到查詢區(qū)間中心的距離與查詢范圍半徑的比較．Z-O編碼比較技術對敏感信息進行編碼：令xnxn－1…x1是數(shù)值x的二進制形式，其中xi∈｛0，1｝，且1≤i≤n，x的Z編碼集合和O編碼集合分別是Zx＝｛xnxn－1…xi1∣xi＝0，1≤i≤n｝和Ox＝｛xnxn－1…xi∣xi＝1，1≤i≤n｝．Z-O編碼具有的性質(zhì)：x＞y當且僅當Ox∩Zy≠?．ZOSR協(xié)議的具體過程如下：每次查詢時，基站首先將本次查詢參數(shù)（包含查詢范圍的中心值）秘密分配給所有傳感器節(jié)點，并向存儲節(jié)點發(fā)送查詢范圍［a，b］半徑的O編碼集合．傳感器節(jié)點根據(jù)收到的查詢參數(shù)，計算感知數(shù)據(jù)到查詢范圍中心距離的Z編碼集合，并將其發(fā)送到存儲節(jié)點．存儲節(jié)點利用Z-O編碼的性質(zhì)進行查詢處理，返回查詢結(jié)果．為了防止被俘獲節(jié)點惡意返回錯誤結(jié)果，要求存儲節(jié)點廣播查詢半徑的O編碼集合，每個傳感器節(jié)點自行判斷其數(shù)據(jù)是否符合查詢條件，并生成驗證碼發(fā)送到存儲節(jié)點．基站根據(jù)這些驗證碼檢驗查詢結(jié)果是否完整．ZOSR協(xié)議在驗證結(jié)果時需要傳感器節(jié)點二次參與，增加了傳感器節(jié)點通信量和計算量．此外，傳輸Z-O編碼也會增加節(jié)點通信代價．

ESRQ協(xié)議［24］是一種基于特殊編碼的隱私保護范圍查詢協(xié)議．ESRQ利用布隆過濾器（Bloo m Filter）［25］的良好特性設計出一種特殊的二進制位串——BF碼，使用單向散列函數(shù)將感知數(shù)據(jù)和查詢范圍分別映射成一個BF碼．BF碼在保護感知數(shù)據(jù)和用戶查詢的同時，保留了一定的特征信息，將對數(shù)值是否落在指定范圍的判斷轉(zhuǎn)換成對兩個BF碼的比較，從而允許管理節(jié)點在不獲取敏感信息的情況下完成范圍查詢．ESRQ協(xié)議借助有序數(shù)據(jù)之間的順序關系提出一種完整性驗證機制，允許基站檢測出不合法的結(jié)果．此外，ESRQ協(xié)議還對性能進行了改進：一方面，根據(jù)BF碼“0”和“1”的分布特征設計出兩種無損壓縮機制——基于絕對位置的壓縮機制和基于相對位置的壓縮機制，縮短BF碼的長度，降低節(jié)點通信成本；另一方面，設計出一種多編碼機制，將一個查詢范圍劃分成若干組，依次為每個組構(gòu)造相應的BF碼，在不增加傳感器節(jié)點通信代價的情況下降低結(jié)果的誤識別率．

除了竊聽攻擊和篡改攻擊，文獻［26］還考慮了節(jié)點之間的共謀行為，提出一系列抵御共謀攻擊的隱私保護范圍查詢協(xié)議CPRQ．其核心思想是：在ESRQ協(xié)議的基礎上，設計出差異化的BF編碼機制，避免不同節(jié)點具有相同的“數(shù)據(jù)-BF碼”映射關系，再參照差異編碼規(guī)則，設計出與之匹配的成員關系判定機制．差異化的BF碼不僅可以抵御多種攻擊，而且保證管理節(jié)點完成范圍查詢．CPRQ系列協(xié)議包括c-CPRQ、r-CPRQ和u-CPRQ三種協(xié)議．c-CPRQ基于混淆機制為每個傳感器節(jié)點構(gòu)造不同的散列函數(shù)集合，防止惡意節(jié)點根據(jù)共享的散列函數(shù)集合推測出其他節(jié)點的“數(shù)據(jù)—BF碼”映射關系，但存在誤否定（False Negative）問題，導致結(jié)果不完整．為了消除誤否定，r-CPRQ采用寬松成員關系判定機制，避免誤否定的發(fā)生，但是由于r-CPRQ的判定機制比c-CPRQ的寬松，無法有效過濾不符合要求的數(shù)據(jù)，導致誤識別率增加．為了實現(xiàn)低誤識別率和零誤否定率，u-CPRQ基于不確定機制為每個傳感器節(jié)點重新構(gòu)造散列函數(shù)集合，使得不同節(jié)點的散列函數(shù)的數(shù)量和組合均具有不確定性，防止節(jié)點共謀．

SEMR協(xié)議［27］利用矩陣變換技術實現(xiàn)隱私保護多維范圍查詢．其主要思想是：基站構(gòu)造一個秘密的3×3非奇異特征構(gòu)造矩陣M，并根據(jù)矩陣M為每個傳感器節(jié)點隨機構(gòu)造一個特征構(gòu)造矩陣W且W＝M－1．基站和傳感器節(jié)點分別使用M和W構(gòu)造變換查詢（Transf or med Quer y）和特征值矩陣（Characteristic Val ue Matrix），然后將變換查詢和特征值矩陣發(fā)送到存儲節(jié)點，存儲節(jié)點利用變換查詢和特征值矩陣在不獲取敏感信息的情況下完成查詢?nèi)蝿眨唧w過程如下：令D＝＜d1，d2，…，dz＞表示傳感器節(jié)點采集的一個z維數(shù)據(jù)，為每一維數(shù)dj（1≤j≤z）構(gòu)造數(shù)據(jù)向量νj＝（（dj）2，dj，1），從而得到一個z×3的數(shù)據(jù)矩陣V＝（ν1，ν2，…，νz）T，利用公式CV＝V·W計算出數(shù)據(jù)D的特征值矩陣CV．傳感器節(jié)點將加密后的數(shù)據(jù)D以及對應的特征值矩陣CV一起發(fā)送到存儲節(jié)點．令＜［a1，b1］，…，［az，bz］＞表示一個z維的查詢命令，基站為每一維［aj，bj］構(gòu)造查詢向量qj＝（1，－（aj＋bj），aj·bj），從而構(gòu)造一個z×3的查詢矩陣Q＝（q1，q2，…，qz）T，利用公式TQ＝M·QT計算出變換查詢TQ，并將TQ發(fā)送到存儲節(jié)點．存儲節(jié)點根據(jù)TQ和數(shù)據(jù)D的特征值矩陣CV進行判定：計算CV·TQ得到一個z×z矩陣，如果其對角線上的數(shù)值均非正，那么與CV對應的數(shù)據(jù)D一定落在查詢范圍內(nèi)．圖5顯示了SEMR的執(zhí)行過程．當不同傳感器節(jié)點的特征構(gòu)造矩陣W相同時，SEMR協(xié)議不能抵抗共謀攻擊．另外，SEMR協(xié)議不能抵御篡改攻擊．

3 對比分析

近年來，傳感器網(wǎng)絡隱私保護范圍查詢處理技術已經(jīng)成為研究熱點，受到學術界越來越多的關注．我們從協(xié)議采用的主要隱私保護技術、保護的對象、抵御的攻擊模型、隱私保護能力、結(jié)果驗證能力、節(jié)點執(zhí)行效率、結(jié)果精確度等方面對現(xiàn)有的研究成果進行了對比分析，具體詳見表1．

從總體上看，現(xiàn)有的隱私保護范圍查詢研究成果尚未較好地實現(xiàn)隱私性、完整性、高效性和精確性四者之間的均衡．一方面，隱私性要求盡可能減少消息中的敏感信息量，而完整性需要借助一定的信息才能完成結(jié)果驗證；另一方面，高效性要求協(xié)議盡可能降低通信和計算成本，而精確性需要通過節(jié)點之間的交互與計算才能實現(xiàn)．

實現(xiàn)隱私保護范圍查詢的技術多種多樣，各有利弊．桶技術雖然可以隱藏敏感信息，但是桶的范圍允許攻擊者對敏感信息進行合理地估計，并且基于桶技術得到的結(jié)果存在一定的誤識別，導致結(jié)果不精確．盡管保序加密技術使得數(shù)據(jù)在表面上與原始數(shù)據(jù)沒有直接聯(lián)系，但是仍然會泄露數(shù)據(jù)間的大小關系，而且復雜的保序加密函數(shù)還會增加節(jié)點的計算代價．前綴成員驗證技術和Z-O編碼技術均將一個數(shù)值表示成一個包含多個數(shù)值的集合，增加了節(jié)點的通信成本．BF編碼技術雖然具備較高的隱私包含能力和效率，但結(jié)果精確度有待提高．矩陣變換技術大大增加節(jié)點的計算代價．此外，并不是所有協(xié)議均能抵御竊聽、篡改、共謀等多種攻擊．不同的攻擊模型，需要不同的抵御手段．例如，抵御竊聽攻擊需要隱藏原始敏感信息；抵御共謀攻擊需要引入完整性驗證機制，這往往需要加入冗余信息，進一步增加了通信成本；抵御共謀攻擊應該避免不同節(jié)點使用相同的網(wǎng)絡參數(shù)和協(xié)議規(guī)則．

協(xié)議名稱 主要技術保護的對象節(jié)點數(shù)據(jù)用戶查詢抵御的攻擊模型竊聽 篡改 共謀隱私保護能力結(jié)果驗證能力節(jié)點效率通信量 計算量 結(jié)果精確度文獻［1，6］Spatial Cr osscheck［7-8］Temporal Cr osscheck［7-8］Spatiotemporal Crosscheck［7-8］Probabilistic Spatiotemporal Crosscheck［9］桶技術√ √ √ √ 弱 較強 低 低 低√ √ √ √ 弱 較弱 高 低 低√ √ √ √ 弱 較弱 較高 低 低√ √ √ √ 弱 較強 高 低 低√ √ √ √弱 弱 較高 低 低Safe Q［12，13］ 前綴成員驗證技術 √ √ √ √較強 強 高 高 精確SEF［17］EQ［18］文獻［19］文獻［20-21］保序加密技術√ √ √ √ 較強 強 高 高 精確√ √ √ √ 較強 強 高 高 精確√ √ √ 較強 無 較高 高 較高√ √ √ √較強 強 低 高 精確ZOSR［22］ Z-O編碼技術 √ √ √ √較強 強 高 較低 精確ESRQ［24］c-CPRQ［26］r-CPRQ［26］u-CPRQ［26］BF編碼技術√ √ √ √ 較強 強 低 較低 高√ √ √ √ √ 強 強 低 較低 低√ √ √ √ √ 強 強 低 較低 低√ √ √ √ √強 強 低 較低 高SEMR［27］ 矩陣變換技術 √ √ √較強 無 較高 高 精確

4 未來工作展望

傳感器網(wǎng)絡隱私保護范圍查詢處理技術屬于新興研究領域，還有很多挑戰(zhàn)性問題需要進一步研究．

（1）安全強度、執(zhí)行效率、結(jié)果精度之間的優(yōu)化均衡

節(jié)點能量、通信和計算能力、存儲空間等資源受限，是傳感器網(wǎng)絡的重要特征．然而隱私保護范圍查詢協(xié)議往往需要較高的通信與計算代價，降低了執(zhí)行效率，增加了能量開銷，同時縮短了網(wǎng)絡生命周期．傳感器網(wǎng)絡隱私保護范圍查詢協(xié)議的優(yōu)化目標是，在安全強度、執(zhí)行效率和結(jié)果精度三者之間取得平衡，在保證高強度隱私保護的前提下，減少通信與計算代價，提高執(zhí)行效率和結(jié)果精確度．現(xiàn)有的隱私保護范圍查詢協(xié)議雖然提出了許多優(yōu)化平衡策略，但還遠遠不能滿足傳感器網(wǎng)絡的實際應用需求，需要進一步研究．

（2）隱私保護復雜范圍查詢技術

近年來，傳感器技術不斷進步，使得單個傳感器節(jié)點可以感知多種屬性信息，例如，在智能家居中，智能傳感器可以同時感知溫度、濕度、光照等信息．與此同時，用戶查詢也日趨復雜化，從單維數(shù)據(jù)到多維數(shù)據(jù)，從歷史查詢到實時查詢，從快照查詢到連續(xù)查詢．現(xiàn)有研究成果主要研究了單維、歷史、快照式范圍查詢中的隱私保護技術，極少研究隱私保護多維范圍查詢，多維數(shù)據(jù)之間的關聯(lián)性以及節(jié)點通信開銷與計算代價隨著維度增加而快速遞增，增加了隱私保護多維范圍查詢的難度．同時現(xiàn)有成果缺少對實時、連續(xù)式范圍查詢中隱私技術的研究．因此，研究隱私保護復雜范圍查詢技術是傳感器網(wǎng)絡應用發(fā)展的需要，也是未來的重點研究方向．

（3）復雜攻擊環(huán)境下的隱私保護范圍查詢處理技術

作為物聯(lián)網(wǎng)的重要組成部分，傳感器網(wǎng)絡的應用需求日趨多樣化，對隱私保護的要求越來越高；同時，攻擊者的攻擊方式日益復雜、攻擊能力日益強大．現(xiàn)有的隱私保護范圍查詢協(xié)議較多關注竊聽攻擊和簡單的篡改攻擊，極少關注危害性更大的復雜攻擊，如共謀攻擊、重放攻擊等．傳感器網(wǎng)絡的開放性導致我們無法預知攻擊者的攻擊方式和攻擊能力，并且抵御單一攻擊的傳感器網(wǎng)絡已經(jīng)無法保障復雜攻擊環(huán)境下網(wǎng)絡的安全性．為了保證復雜攻擊環(huán)境下隱私保護范圍查詢協(xié)議的安全性能，必須盡可能提高協(xié)議對各類攻擊的抵御能力．

［1］SHENG B，LI Q．Verifiable privacy-preserving range query in t wo-tiered sensor net wor ks［C］／／INFOCOM 2008．The 27t h Conference on Co mputer Co mmunications．IEEE，2008．

［2］ROBERT S，ANDRAS F．Energy i mplication of net wor k sensor designs［J］．（2008-04-01）［2015-06-30］．http：／／www．cs．ber keley．edu／-zewczyk／cs252／paper．pdf．

［3］GNA WALI O，JANG K Y，PAEK J，et al．The tenet architect ure f or tiered sensor net wor ks［C］／／Pr oceedings of the 4th international conference on Embedded net worked sensor systems．ACM，2006：153-166．

［4］HACIGüMüSH，IYER B，LI C，et al．Executing SQL over encr ypted data in t he database-ser vice-pr ovider model［C］／／Proceedings of the 2002 ACM SIGMODinternational conference on Management of data．ACM，2002：216-227．

［5］HORE B，MEHROTRA S，TSUDIK G．A privacy-preser ving index f or range queries［C］／／Proceedings of t he Thirtiet h inter national conference on Very lar ge data bases-Volu me 30．VLDB Endowment，2004：720-731．

［6］SHENG B，LI Q．Verifiable privacy-preser ving sensor net wor k storage f or range query［J］．Mobile Co mputing IEEE Transactions on，2011，10（9）：1312-1326．

［7］SHI J，ZHANG Y．Secure range queries in tiered sensor net works［C］／／INFOCOM 2009，IEEE．IEEE，2009：945-953．

［8］SHI J，ZHANG R，ZHANG Y．A spatiotemporal approach f or secure range queries in tiered sensor net wor ks［J］．IEEE transactions on wireless co mmunications，2011，10（1）：264-273．

［9］ZHANG R，SHI J，ZHANG Y．Secure multidi mensional range queries in sensor net wor ks［C］／／Proceedings of t he tenth ACMinternational sy mposiu m on Mobile ad hoc net working and computing．ACM，2009：197-206．

［10］CHENG J，YANG H，WONG S H Y，et al．Design and i mplementation of cr oss-do main cooperative firewall［C］／／Net wor k Protocols，ICNP 2007．IEEE International Conference on，2007：284-293．

［11］LIU A X，CHEN F．Collaborative enf orcement of firewall policies in virtual private net wor ks［C］／／Proceedings of t he t went y-sevent h ACM sy mposiu m on Principles of distributed co mputing．ACM，2008：95-104．

［12］CHEN F，LIU A X．Safe Q：Secure and efficient query processing in sensor net wor ks［C］／／INFOCOM，2010 Pr oceedings IEEE．IEEE，2010：1-9．

［13］CHEN F，LIU A X．Privacy-and integrity-preserving range queries in sensor net works［J］．Net working，IEEE／ACM Transactions on，2012，20（6）：1774-1787．

［14］BOLDYREVA A，CHENETTE N，LEE Y，et al．Order-preserving sy mmetric encryption［M］／／Advances in Cr yptology-EUROCRYPT 2009．Berlin Heidelber g：Springer，2009：224-241．

［15］MERKLE R C．A certified digital signat ure［C］／／Advances in Cr yptology－CRYPTO＇89 Proceedings．New Yor k：Springer，1990：218-238．

［16］AGRA WAL R，KIERNAN J，SRIKANT R，et al．Or der preserving encr yption f or nu meric data［C］／／Pr oceedings of t he 2004 ACM SIGMODinter national conference on Management of data．ACM，2004：563-574．

［17］BU J，YIN M，HE D，et al．SEF：a secure，efficient，and flexible range quer y sche me in t wo-tiered sensor networ ks［J］．Inter national Jour nal of Distributed Sensor Net wor ks，2011（3）：876-879．

［18］TSOU Y T，L U C S，KUO S Y．Privacy-and integrity-preserving range quer y in wireless sensor net wor ks［C］／／Global Co mmunications Conference（GLOBECOM），2012 IEEE．IEEE，2012：328-334．

［19］NGUYEN T D，BUI T V，DANG V H，et al．Efficiently preser ving data privacy range queries in t wo-tiered wireless sensor net wor ks［C］／／Ubiquitous Intelligence＆Co mputing and 9t h Inter national Conference on Autono mic＆Tr usted Co mputing（UIC／ATC），2012 9t h Inter national Conference on．IEEE，2012：973-978．

［20］LI R，LIN Y，YI Y，et al．A privacy and integrity preser ving range quer y pr otocol in t wo-tiered sensor net wor ks［J］．Chin J Co mput，2013，36：1194-1209．

［21］YI Y，LI R，CHEN F，et al．A digital water mar king appr oach to secure and precise range quer y processing in sensor net wor ks［C］／／INFOCOM，2013 Proceedings IEEE．IEEE，2013：1950-1958．

［22］DOU Y，HUANG H，WANG R，et al．Secure range query in t wo-tiered wireless sensor net wor ks［J］．Jisuanji Yanjiu yu Fazhan／Co mputer Research and Develop ment，2013，50（6）：1253-1266．

［23］LIN H Y，TZENG W G．An efficient sol ution t o t he millionaires＇proble m based on ho mo mor phic encryption［C］／／Applied Cr yptography and Net wor k Security．Berlin Heidelber g：Springer，2005：456-466．

［24］ZHANG X，DONG L，PENG H，et al．Achieving efficient and secure range quer y in t wo-tiered wireless sensor net wor ks［C］／／Pr oceedings of t he IEEE／ACMInter national Sy mposiu m on Qualit y of Ser vice，Hong Kong，China．IEEE，2014：26-27．

［25］BLOOM B H．Space／ti me trade-offsin hash coding with allowable err ors［J］．Co mmunications of t he ACM，1970，13（7）：422-426．

［26］ZHANG X，DONG L，PENG H，et al．Collusion-aware privacy-preser ving range query in tiered wireless sensor net wor ks［J］．Sensors，2014，14（12）：23905-23932．

［27］DONG L，ZHU J，ZHANG X，et al．SEMR：Secure and Efficient Multi-Di mensional Range Quer y Pr ocessing in Two-tiered Wireless Sensor Net wor ks［M］／／Web-Age Inf or mation Management．［S．l．］：Springer Inter national Publishing，2015：520-524．