面向WSN的安全范圍查詢協(xié)議研究

摘 要： 針對兩層無線傳感器網絡中范圍查詢所要求的低能耗和高隱私保護，提出了一種具有隱私和完整性保護的安全范圍查詢協(xié)議：SPQ。SPQ是由數據加密、前綴成員驗證、概率鄰居驗證、查詢傳輸過程分離等技術組成，能夠在保證不泄露隱私的情況下完成范圍查詢。分析和仿真結果表明，相對于其他安全協(xié)議，SPQ在保證范圍查詢安全性的同時具有更低能耗。

關鍵詞： 無線傳感器網絡； 范圍查詢； 能耗； 隱私保護

中圖分類號： TN915.08?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）11?0080?05

Abstract： For low power consumption and high privacy protection required for range query in two?tiered wireless sensor networks， a secure range query protocol with privacy and integrity protection called SPQ （Secure probabilistic range query） is proposed. SPQ consists of data encryption， prefix membership verification， probabilistic neighborhoods verification， and separation technology of query and transmission process. It can ensure the achievement of range query without privacy reveal. Analyses and simulation results show that SPQ has the lower power consumption relative to other security protocols under the precondition to guarantee the security of range query.

Keywords： wireless sensor network； range query； power consumption； privacy protection

0 引 言

隨著無線傳感器網絡（Wireless Sensor Networks，WSNs）的不斷應用發(fā)展，在其上的數據查詢任務越來越多，數據查詢過程中的安全要求也愈發(fā)顯得重要起來。WSNs數據查詢可以快速將WSNs收集到的部分有效數據或特定數據聚集到Sink（匯聚節(jié)點），再由Sink對查詢結果進行分析計算以便控制WSNs或做出其他決策。WSNs數據查詢主要分為兩大類，一是簡單查詢，對WSNs收集數據進行較簡單的查詢操作， 目前的研究熱點主要是范圍查詢、Top?k查詢、skyline查詢和基于類型查詢，這類查詢簡單且通用性強，可適用于不同WSNs具有較好的研究價值；二是復雜查詢，查詢過程復雜，需要專門的查詢策略，通用性不強，一般針對特定WSNs。WSNs范圍查詢就是查詢給定區(qū)間范圍的數據查詢。該查詢簡單實用，應用范圍廣，而且對其研究也會對其他簡單查詢有指導意義。

本文提出了一種基于WSNs的安全數據查詢協(xié)議SPQ（Secure probabilistic range query），通過前綴成員驗證技術[1?2]保證查詢隱私性，利用概率鄰居驗證技術[3]進行查詢結果完整性驗證；并使查詢過程和傳輸結果過程分離盡可能減少通信量（減少能耗），增強對WSNs的適用性。

1 相關工作

WSNs安全范圍查詢的研究內容包括以下兩個方面：查詢過程隱私性保護和查詢結果完整性驗證。其中前者需要滿足：

① 普通傳感器節(jié)點收集到的數據不會丟失、泄露、被篡改、被偽造；

② 存儲節(jié)點存儲的數據和查詢請求在查詢過程中不會丟失、泄露、被篡改、被偽造；

③ 數據和查詢請求以及查詢結果在傳輸過程中被竊取也不會泄露隱私。

同時后者需要滿足：

① 滿足查詢條件的數據要全部包含在查詢結果中；

② 查詢結果一旦丟失、被刪改、被偽造都可以被Sink節(jié)點有效檢測出來。

文獻[4]首次提出了基于桶模式[5?6]的考慮隱私保護的范圍查詢，文獻[7] 改進了該范圍查詢，提出了Hybrid時空交叉驗證方法。文獻[8] 提出了SMQ子樹采樣技術來完成范圍查詢的隱私保護。密歇根州立大學的CHEN Fei和LIU A X提出了一種全新的范圍查詢策略，即基于前綴成員驗證技術的SafeQ[9]。

對WSNs范圍查詢隱私保護研究的主流協(xié)議有兩類，即基于桶模式和基于前綴成員驗證技術。基于桶模式的范圍查詢有一個天然的缺陷，即一旦存儲節(jié)點被俘獲，雖然具體數據和查詢結果泄露不了，但是攻擊者可以根據分桶情況大概推斷出查詢的數據范圍。所以這就從根本上決定了基于桶模式的范圍查詢的安全水平有限；基于前綴成員驗證技術的SafeQ范圍查詢的安全性比桶模式完善，但其仍存在能耗較高的問題，由于傳感器網絡具有能量受限的關鍵特性，這就成了SafeQ推廣的一個瓶頸。

本文提出的SPQ屬于第二類協(xié)議，天然上就比基于桶模式的協(xié)議有更高的安全性。另外SPQ通過改變查詢策略和完整性驗證方法來進一步降低能耗，使得SPQ有更低的能耗。

2 網絡模型

WSNs安全數據查詢即隱私保護研究主要是基于兩層傳感器網絡模型[10]，如圖1所示，范圍查詢也不例外。SPQ就是基于該模型的協(xié)議。

圖1 兩層無線傳感器網絡模型

如圖1所示，該網絡模型高層由存儲節(jié)點組成，存儲節(jié)點（Storage Node）就是有較大存儲空間和較強計算能力的傳感器節(jié)點；底層由大量的普通傳感器節(jié)點組成，普通節(jié)點資源受限且成本低。數據的查詢過程如下：用戶的查詢要求（Query）通過Sink傳到存儲節(jié)點，普通節(jié)點收集到數據后將數據傳到存儲節(jié)點存儲，然后在存儲節(jié)點上進行查詢計算，最后將滿足條件的查詢結果（Reply）回傳給Sink并最終返回給用戶。

WSNs數據查詢選用兩層模型有如下好處：普通傳感器節(jié)點只需要將所有采集到的數據傳輸給附近的存儲節(jié)點而不是通過很長的路徑傳輸給Sink節(jié)點，這大大降低了能耗，避免Sink節(jié)點遭遇通信瓶頸；Sink只和存儲節(jié)點通信并可得到查詢結果，這使查詢過程更加有效率。

3 WSNs安全范圍查詢協(xié)議

對于WSNs來說，能耗大小往往是考慮是否實施安全策略的掣肘。SPQ的目標就是在保證查詢的安全同時盡量減少能耗。

3.1 關鍵技術

3.1.1 數據加密

SPQ中，每個普通傳感器節(jié)點[si]都將和Sink共享一個密鑰[ki，]并且[ki]定期更換。普通節(jié)點[si]收集到的數據[d1，…，dn]在查詢過程中都將被[ki]加密，即便是完成查詢過程并收集查詢結果上傳給Sink的存儲節(jié)點也無法得到具體的數據信息，這就保證了數據的私密性。

3.1.2 前綴成員驗證

存儲節(jié)點在無法識別具體數據的情況下，仍然需要完成查詢過程，這就應用了前綴成員驗證技術。前綴成員驗證技術就是將驗證數據是否符合范圍查詢的條件轉化為比較數據項的大小。例如判斷數據12是否符合范圍查詢。12的二進制表示是1100，首先對其構造前綴家族得到{1100 110* 11** 1*** ****}，然后再進行前綴數值化得到{11001 11010 11100 11000 10000}；于此同時[11，15]的二進制表示是[1011，1111]，即{1011 1100 1101 1110 1111}，首先進行前綴轉化得到{1011 11**}，再對其前綴數值化得到{10111 11100}。在最終的前綴數值化組里，他們有相同的項11100，這就表明數據12符合范圍查詢[11，15]。反之如果其中沒有相同數據項，則說明該數據不符合范圍查詢條件。在SPQ中，用三個哈希函數來應用前綴成員驗證技術。三個哈希函數分別是[Φ，Ψ，Ω。]

3.1.3 概率鄰居驗證

SPQ的查詢結果完整性驗證通過概率鄰居驗證技術實現。即普通節(jié)點[si]得到查詢結果后，生成消息（t，i，len），并將該消息傳給附近鄰居節(jié)點。其中t是時間段，i是傳感器編號，len是滿足查詢的數據項數目。然后每個鄰居節(jié)點以一定概率p隨機加入（t，i，len）到自己的查詢結果中并加密上傳，Sink接收到查詢結果后根據各個（t，i，len）進行查詢結果完整性驗證。

3.2 SPQ一維數據查詢過程

WSNs范圍查詢通常可以根據數據項維度的不同分為一維數據查詢和多維數據查詢。一維數據查詢過程最簡單，隨著維度的增加，往往多維數據查詢的能量消耗呈指數增長。SPQ就要盡量避免這種情況，改善不同維度的能耗情況。對一維數據查詢時，SPQ實現過程如下偽代碼所示。其中Sink為匯聚節(jié)點，Storage Node為存儲節(jié)點，[si，sj]為普通節(jié)點。

具體查詢細節(jié)如下：

① 普通節(jié)點[si]收集到一定數據并排序后得到[d1，d2，…，dn，]應用第一個哈希函數[Ψ]加密得到定長的消息編碼[Ψ（d1，d2，…，dn）]并發(fā)送給存儲節(jié)點。當Sink想要做出查詢[{t，[a，b]}]時，會先用另外一個函數[Ω]對查詢范圍進行處理最終將會發(fā)送[{t，Ω（[a，b]）}]到存儲節(jié)點。

② 存儲節(jié)點處理查詢時用到第三個函數[Φ，]當[Φ（j，Ψ（d1，d2，…，dn），Ω（[a，b]））]為真時，說明[dj]滿足查詢條件；為假時說明[dj]不滿足查詢條件，應當舍棄。存儲節(jié)點將滿足查詢條件的最小數據和最大編號以及數據個數（min_d，max_d，len）i反饋給[si。]

③[si]在收到反饋結果后，找出隊列中包括編號min_d和max_d的所有中間數據[dmin_d，…，dmax_d，]并加入dmin-1（如min_d-1<1，則取[dmin_d-1=]-1），[dmax_d+1]（如[max_d+1>n，]則取[dmax_d+1=∞]）。[si]生成消息（t，i，len），并將該消息傳給附近鄰居節(jié)點。其中t是時間段，i是傳感器編號，len是滿足查詢的數據數目。

④ 假如[si]收到鄰居節(jié)點[si_neighbor]發(fā)送來的消息（t，i_neighbor，len），將以一定概率p將此消息加入到自己需上傳的查詢結果中去，即最終上傳{（t，i_neighbor，len）p，dmin_d，[…]，dmax_d} ki。其中[ki]是[si]和Sink共享的密鑰。

上傳數據經過存儲節(jié)點最終傳到Sink，Sink再對所有查詢結果進行完整性驗證，至此SPQ結束。

3.3 SPQ多維數據查詢過程

因為現實應用中，范圍查詢應用場景往往是針對多維數據而言的，所以將SPQ協(xié)議應用到對多維數據查詢也是非常必要的。下面簡述多維數據下SPQ的查詢過程：

①普通節(jié)點[si]收集到[n個m]維數據[（d11，d21，…，][dm1），]…，[（d1n，d2n，…，dmn）]后，應用第一個哈希函數Ψ加密得到m個定長的消息編碼[Ψ（d11，d12，…，d1n），][Ψ（d21，d22，…，d2n），][Ψ（dm1，dm2，…，dmn）]并發(fā)送給存儲節(jié)點。當Sink想要做出查詢[{t，[a1，b1]，…，[am，bm]}]時，會先用另外一個函數[Ω]對查詢范圍進行處理最終將會發(fā)送[{t，Ω（[a1，b1]），…，][Ω（[am，bm]）}]到存儲節(jié)點。

② 存儲節(jié)點處理查詢時用到第三個函數Φ，當[Φ（j，Ψ（dt1，…，dtn），Ω（[at，bt]））]為真時（其中[1≤t≤m]），說明[dj]滿足維度[t]上的查詢條件；為假時說明[dj]不滿足維度[t]的查詢條件，應當舍棄。當把所有維度做完后，求編號的交集就得到最終的查詢結果，存儲節(jié)點將這些滿足查詢條件的數據編號最值{（min_d1，max_d1），…， （min_dm，min_dm），len}反饋給[si。]

[si]在查詢過程中對上傳數據按隨機某個維度[t]的值進行排序。在收到反饋結果后，根據查詢結果找出所有符合條件數據并加密。

③、④與一維數據查詢過程相同。

4 性能分析

4.1 安全性分析

因為普通節(jié)點數據量小，如被俘獲對全局查詢結果影響不大，所以現在主要考慮存儲節(jié)點被俘后的情況，以此來驗證SPQ的安全性能。

由于查詢結果已加密，所以存儲被俘后無法獲得有效的查詢數據。被俘存儲節(jié)點可以做的工作主要是丟棄數據和更改查詢結果（min_d，max_d，len）i。這兩者破壞都可以由Sink在完整性驗證時檢測出來。

4.2 能耗分析

SPQ相對之前的范圍查詢協(xié)議在能耗上有改進，一個原因是由于查詢過程和傳輸查詢結果過程分離的結果，這樣一來不符合查詢條件的數據將不會上傳到存儲節(jié)點，減低了很大一部分數據傳輸量，即減少了普通節(jié)點發(fā)送數據消耗的能量，又降低了存儲節(jié)點接收數據所需的能耗，明顯降低了安全范圍查詢的能量消耗。

4.3 仿真實驗

本文使用原始數據集在Matlab平臺上對SPQ和SafeQ進行仿真，在長寬均為300 m的區(qū)域有100個普通節(jié)點隨機分布，4個存儲節(jié)點較均勻分布，居中一個Sink節(jié)點。假設傳感器節(jié)點有效傳輸距離為75 m，利用TAG（Tiny Aggregation Service for Ad Hoc Sensor Network）算法建立路由路徑，每個普通節(jié)點向存儲節(jié)點傳輸數據平均需要1.8跳。每個節(jié)點平均有20個鄰居節(jié)點，向每個鄰居節(jié)點發(fā)送驗證消息的概率為0.4。仿真實驗中，能耗值是指具體能耗除以時間，即類似功率的一個衡量能耗水平的值。

實驗主要是對比SPQ和SafeQ對不同維度數據進行查詢時的能耗。為了保證實驗結果的正確性，所有實驗采用相同的真實數據集，一維數據集和二維數據集是從三維數據集中剝離的一個維度和兩個維度，即不同維度的實驗在單位時間內接收到的查詢結果數據項數量應該是相同的。

（1） 一維數據查詢

第一組實驗是在一維數據查詢下，SPQ和SafeQ的能耗對比情況，如圖2，圖3所示。

通過實驗結果圖對比知，針對一維數據查詢時，在相同數據集來源情況下，SPQ普通節(jié)點能耗值比SafeQ低3.2倍；SPQ存儲節(jié)點能耗值比SafeQ低2.5倍。在一維數據情況下，SPQ能耗水平明顯低于SafeQ。

（2） 多維數據查詢

第二組實驗是在多維數據查詢下（本實驗使用三維數據），SPQ和SafeQ的對比情況，如圖4，圖5所示。

通過實驗二結果圖對比知，針對三維數據查詢時，在相同數據集來源情況下，SPQ普通節(jié)點能耗值比SafeQ低3.64倍；SPQ存儲節(jié)點能耗值比SafeQ低1.17倍。在三維數據情況下，SPQ能耗水平也低于SafeQ。

（3） 不同維度數據查詢對比

第三組實驗是在不同維度數據查詢下，SPQ的表現情況對比，如圖6，圖7所示。

通過結果圖對比知，在相同數據集來源情況下，SPQ普通節(jié)點對三種維度數據查詢時能耗成線性增長；SPQ存儲節(jié)點對三種維度數據查詢時能耗也是成線性增長。即在多維數據查詢情況下，SPQ的節(jié)能能力同樣突出。

5 結 語

本文提出的SPQ協(xié)議的數據隱私性保護通過前綴成員驗證技術來實現，數據完整性驗證則主要由概率鄰居驗證技術來完成，并通過一系列通信策略優(yōu)化減少通信量即能耗，使其優(yōu)于現有的SafeQ和基于桶模式的范圍查詢。雖然SPQ相比現有協(xié)議能耗更加低，安全性能也很好，但是相比不加隱私保護的查詢策略，能耗仍然偏高，需進一步尋找安全策略或通信方式減少能耗，使安全數據查詢可以更加好的推廣。

參考文獻

[1] CHENG J， YANG Hao， WONG S， et al. Design and implementation of cross?domain cooperative firewall [C]// Procee?dings of IEEE International Conference on Network Protocols. Beijing，China： IEEE， 2007： 284?293.

[2] LIU A X， CHEN Fei. Collaborative enforcement of firewall policies in virtual private networks [C]// Proceedings of PODC. Toronto， Canada： PODC， 2008： 95?104.

[3]范永健，陳紅.兩層傳感器網絡中可驗證隱私保護Top?k查詢協(xié)議[J].計算機學報，2012，35（3）：423?433.

[4] SHENG Bo， LI Qun. Verifiable privacy?preserving sensor networks storage for range query [J]. IEEE Transactions on Mobile Computing， 2011， 10（9）： 1312?1326.

[5] HACIGUMUS H， IYER B R， Li C， et al. Executing SQL over encrypted data in the database service provider model [C]// Proceedings of SIGMOD. Madison， Wisconsin，USA： SIGMOD， 2002： 216?227.

[6] HORE B， MEHROTRA S，TSUDIK G..A privacy?preserving index for range queries [C]// Proceedings of VLDB. Toronto， Ca?nada： VLDB， 2004： 720?731.

[7] ZHANG Rui， SHI Jing， ZHANG Yan?chao. Secure cooperative data storage and query processing in unattended tiered sensor networks [J]. IEEE Journal on Selected Areas in Communications， 2012， 30（2）： 433?441.

[8] YU C， TSOU Y T， LU C S， et al. practical and secure multidimensional query framework in tiered sensor networks [J]. IEEE Transactions on Information Forensics and Security， 2011， 6（2）： 241?255.

[9] CHEN Fei， LIU A X. Privacy? and integrity?preserving range queries in sensor networks [J]. IEEE?ACM Transactions on Networking， 2012， 20（6）： 1774?1787.

[10] RATNASAMY S， KARP B， SHENKER S， et al. Data?centric storage in sensornets with GHT （geographic hash table） [J]. Mobile Networks and Applications， 2003， 8（4）： 427?442.