兩層傳感器網絡中隱私保護的等區間近似查詢算法

王濤春，崔壯壯，劉 盈,2

(1.安徽師范大學 數學計算機科學學院，安徽 蕪湖 241002; 2.網絡與信息安全安徽省重點實驗室(安徽師范大學)，安徽 蕪湖 241002)(*通信作者電子郵箱wangtc@ahnu.edu.cn)

兩層傳感器網絡中隱私保護的等區間近似查詢算法

王濤春1,2*，崔壯壯1，劉 盈1,2

(1.安徽師范大學 數學計算機科學學院，安徽 蕪湖 241002; 2.網絡與信息安全安徽省重點實驗室(安徽師范大學)，安徽 蕪湖 241002)(*通信作者電子郵箱wangtc@ahnu.edu.cn)

隱私保護已經成為拓展無線傳感器網絡(WSN)應用的關鍵因素，是當前的研究熱點。針對傳感器網絡中感知數據的安全性問題，提出了兩層傳感器網絡中隱私保護的等區間近似查詢(PEIAQ)算法。首先，將傳感器節點編號及其采集的數據等信息隱藏在隨機向量中；然后，基站根據接收到的向量信息構造線性方程組，從而得到包含全局統計信息的直方圖；最后，根據直方圖完成近似查詢。此外，PEIAQ利用數據擾動技術和傳感器節點與基站共享密鑰的方式來對感知數據進行加密，保證了感知數據的隱私性。仿真實驗顯示，PEIAQ的通信量在查詢階段明顯低于隱私保護通用近似查詢(PGAQ)的通信量，約節省60%，因此，該PEIAQ具有低能耗、高效率等特點。

兩層傳感器網絡；隱私保護；近似查詢；數據聚集

0 引言

近年來，隨著無線傳感器網絡(Wireless Sensor Network, WSN)技術的迅速發展，關于WSN的應用已廣泛滲入到環境監測、智能交通、醫療衛生、軍事國防等多個領域[1]。然而，隨著應用范圍的不斷擴大所引發的隱私安全問題成為新的挑戰。

為了解決無線傳感器網絡的隱私問題，研究人員關于無線傳感器網絡隱私保護技術開展了大量的研究，取得了很多研究成果。目前，無線傳感器網絡數據隱私保護技術主要從數據查詢、數據聚集和訪問控制三個方面來研究[2]。由于無線傳感器網絡中的節點能量耗費直接影響到網絡的壽命，因此好的隱私保護技術在保證隱私的前提下應該具有低通信量、低計算量等特點。

本文提出基于網內數據聚集的隱私保護等區間近似查詢算法，將無線傳感器節點采集的數據及其編號等信息蘊含在隨機向量中，中間匯聚節點對上傳向量進行求和匯聚，在基站構建線性方程組，最終得到包含全局統計信息的直方圖及對應的無線傳感器節點編號，進而使用直方圖中的統計信息進行范圍查詢、Top-k查詢、COUNT、SUM等近似查詢。

1 相關工作

查詢處理技術是無線傳感器網絡的關鍵技術，由于傳感器網絡具有多跳、無線通信的特點，使得無線傳感器網絡面臨嚴重的安全問題，將隱私保護技術應用于無線傳感器網絡感知數據查詢處理，從而滿足無線傳感器網絡對數據安全性的要求。

目前關于無線傳感器網絡中的數據查詢主要是針對范圍的查詢，文獻[3]較早地提出了有關傳感器網絡中范圍查詢的隱私保護，通過增大查詢對象的范圍來有效地保護查詢隱私，但同時會造成過多的能量開銷。

為了進一步減少查詢處理的通信量，很多專家學者提出采用近似查詢算法來避免不必要的數據傳遞，從而減少通信量。Fan等[4]提出了概要技術，其基本思想是利用哈希將數據從某一范圍映射到另一范圍，從而生成概要數據，即用一個小范圍的數據集來表示另一個大范圍的數據集。

文獻[5]提出針對某一具體地理范圍內的窗口查詢，避免與查詢無關節點參與查詢，從而造成能量的浪費；文獻[6]提出了同態加密的隱私保護技術；文獻[7-10]對無線傳感器網絡中的隱私保護查詢進行研究，提出了基于兩層傳感器網絡的隱私保護技術。上述文獻只適用于單一查詢類型，不能滿足多種類型的近似查詢，且查詢效率不高。

2 研究模型

2.1 網絡模型

現有的隱私保護查詢算法主要基于兩層無線傳感器網絡[11]，網絡模型如圖1所示。在兩層無線傳感器網絡中，網絡的下層由大量的傳感器節點組成，特點是資源受限；網絡的上層由少量的匯聚節點組成，匯聚節點存儲傳感器節點上傳的感知數據并響應基站節點的查詢請求，匯聚節點具有大存儲、高計算等特點，能有效地縮短查詢的響應時間，延長了網絡的壽命。

圖1 兩層傳感器網絡示意圖

2.2 數據聚集模型

文獻[12]的研究表明通信是節點能量消耗的主要因素，利用數據聚集能夠有效地降低無線傳感器網絡中的通信量，減少能量消耗，提高無線傳感器節點的使用壽命。

2.3 查詢模型

為了簡化網絡中的通信量，本文在通用近似查詢算法PGAQ(Privacy-preserving Generic Approximate Query)[13]的基礎上提出一種新的等區間近似查詢(Privacy-preserving Equal-Interval Approximate Query, PEIAQ)算法。PGAQ采用節點相似的傳感器網絡模型，基站把采集數據的值域劃分成k個區間，然后同隨機生成的參照向量一起下發至每個傳感器節點，節點把采集的數據等信息上傳基站，最后在基站構建方程組進行求解，進而完成一般近似查詢。PEIAQ改進思路為：將原有的k個數據域區間簡化成一個三元組{Vmin,Vmax,k}，其中Vmin、Vmax分別表示采集數據值域的最小值、最大值，k表示進行查詢時等區間的區間數。k值決定了數據采集的粒度，k值越大，近似度就越大，查詢結果也就越模糊。

2.4 攻擊模型

無線傳感器網絡中攻擊者主要可進行以下三類攻擊：數據竊聽攻擊、數據篡改攻擊和共謀攻擊[14]。

1)數據竊聽攻擊：攻擊者對傳感器節點間的無線通信鏈路進行監聽，分析信號的特點，獲取傳輸的信息。這類攻擊者是無線傳感器網絡主要的攻擊方式。2)數據篡改攻擊：攻擊者通過俘獲傳感器節點偽造虛假數據、惡意改變或刪除真實數據等方式影響傳感器網絡應用，因此篡改攻擊對網絡安全的威脅更大。3)共謀攻擊[15]：攻擊者通過俘獲網絡中的多個傳感器節點，擾亂網絡通信。在共謀攻擊中，隨著攻擊者破壞能力的不斷增強，攻擊者可能獲得通信協議、加密密文、拓撲結構等隱私信息，從而破壞網絡的安全性。相對于非共謀攻擊，共謀攻擊對網絡安全的危害性更大。

3 等區間近似查詢算法

等區間近似查詢算法PEIAQ的基本思想是將無線傳感器節點采集的數據及其編號等信息蘊含在隨機向量中，中間匯聚節點對上傳向量進行求和匯聚，在基站構造線性方程組得到包含全局統計信息的直方圖及對應的無線傳感器節點編號，進而使用直方圖中的統計信息進行近似查詢。PEIAQ主要包括初始化階段和查詢階段。

3.1 初始化階段

基站為每一個傳感器節點si分配一個隨機向量作為參照(稱為參照向量)(a1,a2,…,am)T，為了防止信息泄露，基站還需為每一個傳感器節點分配另一個隨機向量作為干擾(稱為干擾向量)(d1,d2,…,dm)T；基站將參照向量、干擾向量等信息進行加密后下發至各個傳感器節點，傳感器節點利用相應的密鑰解密得到相應向量信息。

假設n個傳感器節點為{s1,s2, …,sn}，Vmin、Vmax表示傳感器節點采集數據的最小值、最大值。初始階段，基站隨機生成一個m×n階參照矩陣A為:

由于傳感器節點si對應于參照矩陣A中的第i列參照向量(a1i,a2i,…,ami)T，而任意兩個無線傳感器節點的參照向量不同，因此參照矩陣A中需要滿足條件：當i≠j時，(a1i,a2i,…,ami)T≠(a1j,a2j,…,amj)T。

3.2 查詢階段

基站將查詢命令廣播給無線傳感器節點后，節點從查詢命令中解析出采集數據值域的最大值、最小值和劃分粒度k值等信息，并進行以下操作。

1)數據采集。

傳感器節點采集數據，利用參照向量和干擾向量等信息將采集到的數據隱藏到生成的新向量中，即為結果向量。對于傳感器節點，在查詢周期t內采集數據后，生成的結果向量為

2)數據聚集。

當無線傳感器節點采集數據后便會將結果向量上傳給匯聚節點，匯聚節點對這些數據進行匯聚操作。假設某匯聚節點需要對j個傳感器節點上傳的數據進行匯聚，則得到的結果向量為：

3)基站處理。

基站收到數據后，先對其進行解密，然后把所有無線傳感器節點上傳的結果向量進一步進行聚集，得到最終結果向量R：

結果向量R與所有節點的干擾向量進行差操作便可得到中間向量B=(b1,b2,…,bm)T，具體為：

基站構造如下線性方程組：

(1)

方程組(1)的系數矩陣為參照矩陣A，因此最終求得的解{K1,K2, …,Kn}即為節點采集數據所在區域編號，進而可以得到一個等區間的直方圖。最終根據等區間直方圖得到近似查詢結果。

3.3 性能分析

1)查詢結果精確度。

對于查詢精確度，基站進行近似查詢的精確度受區間劃分三元組{Vmin,Vmax,k}的影響，當等區間的區間劃分的越細，即劃分粒度越小，則查詢精度越高。

2)隱私性。

PEIAQ通過基站與傳感器節點共享密鑰可以防范攻擊者的竊聽攻擊，使用擾動技術可以有效防范攻擊者的篡改攻擊，使用參照向量，可以防范攻擊者的共謀攻擊。具體分析如下：

預防數據竊聽攻擊：假設攻擊者通過俘獲聚集節點進行攻擊，由于基站使用與傳感器節點共享的密鑰對每個傳感器節點對應的參照向量進行加密，加密后由基站廣播給傳感器節點，匯聚節點無法得知傳感器節點和基站共享的密鑰，因此匯聚節點不能獲得相應的參照向量。攻擊者在不知道參照向量的情況下不能通過竊聽的數據推導出節點ID信息和采集的數據信息，從而預防了數據竊聽攻擊。

預防數據篡改攻擊：由于攻擊者無法竊聽到真實的隱私信息，因此在無法得知傳感器節點參照向量的前提下無法偽造虛假數據、惡意改變原有數據，從而預防了數據篡改攻擊。

預防共謀攻擊：由于攻擊者無法得知其他傳感器節點的共享秘鑰以及參照向量，因此無法俘獲網絡中的多個傳感器節點來擾亂網絡通信，從而預防了共謀攻擊。

3)穩定性。

本算法采用兩層網絡模型。在兩層傳感器網絡中，一般傳感器節點不需要存儲大量數據、執行復雜的查詢任務和發送數據到基站，而是把這些任務分配給配置高、穩定性好的中間節點來完成，這大大降低了傳感器節點的存儲成本、計算代價和通信開銷，提高了網絡的穩定性，從而盡可能降低了傳感器及其網絡出現故障所帶來的影響。假如某個傳感器節點無法正常工作或者網絡出現故障，致使部分傳感器網絡沒有上報感知數據，在基站構建線性方程組進行最后求解時，未上報數據的傳感器節點所求解為零解，基站可將這些零解處理成缺失值，但這并不影響基站對其他節點的觀測。

4 實驗及分析

為了驗證等區間近似查詢算法PEIAQ的性能，本章對算法PEIAQ與通用近似查詢算法PGAQ在節點數、向量長度和查詢周期等參數變化對通信量影響的情況進行比較。設實驗參數的默認值如表1所示。

表1 實驗參數默認值

圖2顯示在查詢階段，傳感器節點數目n對算法PEIAQ與算法PGAQ的通信量的影響情況，由圖可知，隨著傳感器節點數目的增多，PEIAQ的通信量增加幅度遠小于算法PGAQ。由于PEIAQ在查詢過程中傳送的基本單位數據較少，PGAQ在基站向傳感器節點下發數據時，需要傳送k個采集區間，并在查詢階段對感知數據進行處理時需要對這k個區間一一檢索；PEIAQ在基站向傳感器節點下發數據時，只需傳遞一個三元組{Vmin,Vmax,k}，在查詢階段處理采集數據時只需要進行一個簡單運算。因此等區間近似查詢算法具有低能耗、高效率等特點。

圖2 查詢階段的通信量

為了進一步驗證各個參數對算法PEIAQ通信量的影響，實驗分別對參照向量長度、查詢次數和查詢區間精度三個參數進行觀察。圖3(a)顯示了參照向量長度m對通信量的影響，由于參照向量的長度決定了查詢階段基本傳送數據單元的大小，因此隨著m的增大，數據通信量呈迅速上升趨勢。圖3(b)顯示了查詢周期對通信量的影響，隨著單位時間內查詢次數的增多，數據通信量以線性方式增長。圖3(c)顯示了查詢區間數k取值對通信量的影響，由于k值的增加不會對基本傳送數據單元的大小造成影響，因此數據通信量的變化呈現出一條直線。

這一實驗表明，查詢區間精度對查詢階段的通信量幾乎沒有影響，增加查詢區間的精度并不會給整個網絡帶來過多負擔，但是參照向量的長度與傳感器節點的數目對通信量影響較大，因此在實際網絡的布置中，不應該采用增加參照向量的長度和傳感器節點數目的方式來提高查詢的精確性，這樣會顯著增加網絡通信量，進而影響整個網絡的壽命。

圖3 各參數對數據通信量的影響

5 結語

本文針對無線傳感器網絡隱私數據查詢算法，研究了算法適用的網絡模型、數據聚集模型以及攻擊模型，在分析現有隱私數據查詢算法的不足的基礎上，以近似查詢為切入點，提出一種安全性能更高，更加適用于兩層傳感器網絡的等區間近似查詢算法PEIAQ，PEIAQ借助數據擾動技術和傳感器節點與基站共享密鑰的方式來對隱私信息進行加密，保證了數據的隱私性。最后通過理論分析和仿真實驗驗證了等區間近似查詢算法的有效性和安全性。

無線傳感器網絡數據融合面臨著數據竊聽、數據篡改和共謀等攻擊的嚴峻挑戰，因此數據完整性驗證也是WSN的研究熱點。下一步將主要研究數據完整性驗證問題，使得無線傳感器網絡中的近似查詢算法不僅保證了數據的隱私性和查詢的精確性，還能對查詢結果的完整性進行驗證。

References)

[1] BUTUN I, MORGERA S D, SANKAR R. A survey of intrusion detection systems in wireless sensor networks [J]. IEEE Communications Surveys & Tutorials, 2014, 16(1): 266-282.

[2] 范永健,陳紅,張曉瑩.無線傳感器網絡數據隱私保護技術[J].計算機學報,2012,35(6):1131-1146.(FAN Y J, CHEN H, ZHANG X Y. Data privacy preservation in wireless sensor networks [J]. Chinese Journal of Computers, 2012, 35(6): 1131-1146.)

[3] SHENG B, LI Q. Verifiable privacy-preserving range query in two-tiered sensor networks [C]// Proceedings of the 2008 IEEE 27th Conference on Computer Communications. Piscataway, NJ: IEEE, 2008: 46-50.

[4] FAN Y C, CHEN A L P. Efficient and robust sensor data aggregation using linear counting sketches [EB/OL]. [2016- 11- 16]. http://web.nchu.edu.tw/～yfan/index.files/ipdps.pdf.

[5] COMAN A, NASCIMENTO M A, SANDER J. A framework for spatio-temporal query processing over wireless sensor networks [C]// Proceedings of the 2004 1st International Workshop on Data Management for Sensor Networks: in Conjunction with VLDB. New York: ACM, 2004: 104-110.

[6] GENTRY C. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.

[7] ZENG J, WU Y, WU Y, et al. Energy-efficient and privacy-preserving range query in participatory sensing [C]// Proceedings of the 2016 IEEE Trustcom/BigDataSE/ISPA. Piscataway, NJ: IEEE, 2016: 876-883.

[8] CUI J, ZHONG H, TANG X, et al. A fined-grained privacy-preserving access control protocol in wireless sensor networks [C]// Proceedings of the 9th International Conference on Utility and Cloud Computing. New York: ACM, 2016: 382-387.

[9] YU L, LI J Z, GAO H, et al. Enablingε-approximate querying in sensor networks [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 169-180.

[10] 戴華,何瑞良,楊庚,等.基于桶劃分的兩層傳感網隱私保護Top-k查詢[J].北京郵電大學學報,2015,38(5):18-22.(DAI H, HE R L, YANG G, et al. Bucket partition based privacy-preserving Top-kquery processing in two-tiered wireless sensor networks [J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(5): 18-22.)

[11] 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. New York: ACM, 2006: 153-166.

[12] SZEWCZYK R, FERENCZ A. Energy implication of network sensor designs [EB/OL]. (2008- 04- 01) [2015- 06- 30]. http://bwrcs.eecs.berkeley.edu/Classes/CS252/Projects/Reports/robert_szewczyk.pdf.

[13] 范永健，陳紅，張曉瑩，等.無線傳感器網絡中隱私保護通用近似查詢協議[J].計算機學報,2014,37(6):918-920.(FAN Y J, CHEN H, ZHANG X Y, et al. Privacy-preserving generic approximate query in wireless sensor networks [J]. Chinese Journal of Computers, 2014, 37(6): 918-920.)[14] 張曉瑩，董蕾，陳紅.無線傳感器網絡隱私保護范圍查詢處理技術[J].華東師范大學學報(自然科學版),2015,2015(5):1-13.(ZHANG X Y, DONG L, CHEN H. Privacy-preserving range query processing in wireless sensor networks [J]. Journal of East China Normal University (Natural Science), 2015, 2015(5): 1-13.)

[15] 遲令.基于無線傳感器網絡的身份認證體系的研究[D].長春:吉林大學,2015:11-12.(CHI L. The research of identity authenticantion system on wireless sensor networks [D]. Changchun: Jilin University, 2015: 11-12.)

Privacy-preservingequal-intervalapproximatequeryalgorithmintwo-tieredsensornetworks

WANG Taochun1,2*, CUI Zhuangzhuang1, LIU Ying1,2

(1.CollegeofMathematicsandComputerScience,AnhuiNormalUniversity,WuhuAnhui241002,China; 2.AnhuiProvincialKeyLaboratoryofNetworkandInformationSecurity(AnhuiNormalUniversity),WuhuAnhui241002,China)

Privacy preservation, a key factor in expanding the application of Wireless Sensor Network (WSN), is the current research hotspot. In view of the privacy of sensory data in WSN, Privacy-preserving Equal-Interval Approximate Query (PEIAQ) algorithm in two-tiered sensor networks based on data aggregation was proposed. Firstly, sensor node IDs and sensory data were concealed in a random vector, and then linear equations were worked out by the base station based on the random vector. As a result, a histogram containing global statistics was formed, and finally the results of approximate query were obtained. In addition, sensory data were encrypted through perturbation technique and sharing key between the sensor node and base station, which can ensure the privacy of sensory data. Simulation experiments show that the PEIAQ has a 60% decrease approximately in the traffic compared with PGAQ (Privacy-preserving Generic Approximate Query) in the query phase. Therefore, PEIAQ is efficient and costs low-energy.

two-tiered sensor network; privacy-preservation; approximate query; data aggregation

2017- 03- 22;

2017- 05- 24。

國家自然科學基金資助項目(61402014, 61602009)；安徽省自然科學基金資助項目(1508085QF134)；安徽省教學研究項目(2016jyxm0411)。

王濤春(1979—)，男，安徽無為人，副教授，博士， CCF會員，主要研究方向：隱私保護、無線傳感器網絡； 崔壯壯(1994—)，男，安徽蒙城人，主要研究方向：無線傳感器網絡； 劉盈(1993—)，男，安徽阜陽人，碩士研究生，主要研究方向：無線傳感器網絡。

1001- 9081(2017)09- 2563- 04

10.11772/j.issn.1001- 9081.2017.09.2563

TP309.2

A

This work is partially supported by the National Natural Science Foundation of China (61402014, 61602009), the Natural Science Foundation of Anhui Province (1508085QF134), the Teaching Research Foundation of Anhui Province (2016jyxm0411).

WANFTaochun, born in 1979, Ph. D., associate professor. His research interests include privacy preserving, wireless sensor networks.

CUIZhuangzhuang, born in 1994. His research interests include wireless sensor networks.

LIUYing, born in 1993, M. S. candidate. His research interests include wireless sensor networks.