兩層無線傳感器網絡中安全Skyline查詢協議

宋 玲，武佩寧

（廣西大學 計算機與電子信息學院，廣西 南寧530004）

0 引 言

目前針對無線傳感器網絡的Skyline查詢研究并不多，具有安全保護措施的Skyline查詢協議幾乎無人涉及。針對Skyline的安全問題，本文基于兩層無線傳感器網絡提出了有安全性保證的Skyline查詢協議：SSLine。該協議使用ZO 編碼技術［1，2］來保證數據隱私性，并通過普通節點到Sink節點的端到端數據加密方法保證數據傳輸的安全，采用閾值預篩選技術減少通信量。SSLine可以保證Skyline查詢數據不泄露，保證網絡通信的安全；同時其相對無安全保證的Skyline查詢沒有過多的能耗增加。

1 相關工作

文獻 ［3］提出了目前在無線傳感器網絡中應用最廣的Skyline查詢協議：SkySensor。將Skyline查詢引入無線傳感器網絡后，SkySensor是一個能量有效且具有代表性的傳感器網絡Skyline查詢協議。文獻 ［4］提出一種安全范圍查詢協議ZOSR，首次將Z－O 編碼技術應用到無線傳感器網絡的安全中。文獻 ［3，5，6］研究了Skyline查詢在兩層無線傳感器網絡中的布置和應用。

Skyline查詢分為近似Skyline 查詢和連續Skyline 查詢。近似Skyline查詢是為了減少能耗以適應無線傳感器網絡資源受限的特點，在盡可能低能耗的情況下滿足Skyline查詢的基本要求，由網絡中部分節點傳回的數據得出一個近似結果集。而連續Skyline查詢結果更加精確，本文研究的就是針對連續Skyline查詢。

2 網絡模型

本文提出的SSLine基于兩層傳感器網絡模型［7］，如圖1所示。

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

對于Skyline查詢，兩層傳感器網絡的優勢［8，9］：

（1）增長網絡壽命。顯著降低普通節點傳輸數據量和計算能耗，明顯提高普通節點網絡壽命。

（2）更加適合安全查詢。查詢計算操作集中在存儲節點，即分擔普通節點壓力，又分散了安全壓力，只需要做好存儲節點的保護工作即可完成網絡的安全保護。

（3）網絡可維護性強。網絡能耗主要集中在存儲節點，管理維護工作也就集中在這一層，只需定期更換存儲節點即可完成網絡維護。

（4）機動性強。如果網絡不堪重負或有空余，可增加節點或撤掉存儲節點，很容易布置或撤換。

（5）網絡控制力加強。通過分層結構，使得Sink對整個網絡的控制能力加強，問題節點更容易查找。

3 安全Skyline查詢協議

3.1 關鍵技術

3.1.1 閾值預篩選技術

假設網絡收集數據為二維的，閾值為Sink節點根據上個周期t的Skyline結果數據集每個維度求平均值得到的。一個存儲節點接收數據如圖2所示。

圖2 利用閾值Gt 為數據分區

以閾值Gt為界，可以將數據分為4個區域。

C區為閾值控制區，即該區內數據全部被閾值支配，即該區內所有節點xc＞x0，yc＞y0。其中c為C區中各數據編號。

A 區為閾值被控制區，即該區內數據全部都可以支配閾值，即該區內所有節點xa＜x0，ya＜y0。其中a為A 區中各數據編號，該區數據集一般表示為DA。

B1區和B2區為閾值半控制區，這兩個區域內數據和閾值互不支配，B1區數據不支配閾值但在第一個維度上優于閾值，B2區數據第一個維度不如閾值但在第二個維度上優于閾值。這兩個區域數據集一般表示為DB1和DB2。

在Skyline查詢中，存儲節點的操作即為利用閾值Gt篩選一遍原始感知數據。①如原始感知數據屬于C 區，即數據被閾值Gt支配，則不在考慮該數據；②如原始感知數據屬于A 區，即數據可以支配閾值Gt，則將該數據加入到集合DA 中；③如感知數據在第一維上優于閾值Gt但并不支配閾值Gt，則將該數據加入到DB1；④如感知數據在第一維上不如閾值Gt但在第二個維度上優于閾值Gt，則將該數據加入到DB2。

篩選完數據后如果DA≠，那么將DA∪DB1∪DB2作為Skyline查詢結果超集發送給Sink。如果DA＝，那么發送作為查詢結果給Sink。

以上為二維數據的例子，現將閾值預篩選技術擴展到一般情況，即對于n維感知數據的兩層傳感器網絡，閾值預篩選技術如何應用到Skyline中。

（1）普通節點收集感知數據上傳到存儲節點。

（2）Sink發送Skyline命令到存儲節點，并附帶查詢的閾值Gt，閾值Gt各個維度的值為該存儲節點上個周期即t－1周期查詢結果數據集的各個維度平均值。

（3）對于存儲節點來說，利用閾值Gt篩選一遍原始感知數據。①如原始感知數據屬于C區，即閾值Gt從n個維度上都優于該數據，數據被閾值Gt支配，則不在考慮該數據；②如原始感知數據屬于A 區，即數據可以支配閾值Gt，則將該數據加入到集合DA 中；③如感知數據在第一維上優于閾值Gt但并不支配閾值Gt，則將該數據加入到DB1；④如感知數據在第一維上不如閾值Gt但在第二個維度上優于閾值Gt，則將該數據加入到DB2；…⑤如感知數據在第一維到第i維都不如閾值Gt但在第i＋1個維度上優于閾值Gt，則將該數據加入到DBi。其中1≤t≤n；…⑥如感知數據在第一維到第n－1維都不如閾值Gt但在第n維度上優于閾值Gt，則將該數據加入到DBn。

篩選完數據后如果DA≠，那么將DA∪DB1∪…∪DBn作為Skyline查詢結果超集發送給Sink，Skyline剩余操作在Sink上完成。如果DA＝，那么發送作為查詢結果給Sink。

定理 如果DA≠，那么DA∪DB1∪…∪DBn就是Skyline查詢結果的超集，即Skyline 查詢結果數據集（DA∪DB1∪…∪DBn）。其中n為網絡感知數據維度。

證明：由Skyline查詢的定義得知，Skyline查詢結果數據集中元素不被n 維空間中其它任一數據支配，又知DA≠，由此推出，Skyline查詢結果數據集中元素不會被DA 中任意數據支配。而DA 中數據都可以支配閾值Gt，即Skyline查詢結果數據集中任意元素都不會被閾值Gt支配，（DA∪DB1∪…∪DBn）即為所有不被閾值Gt支配的數據集，所以最終得出：Skyline查詢結果數據集 （DA∪DB1∪…∪DBn）。

證畢。

3.1.2 Z－O 編碼技術

定義1 Z－O 編碼：將數值x二進制化，即x＝ （xnxn－1…x1）2，其中xi∈ ｛0，1｝且1≤i≤n。對x的Z編碼公式和O 編碼公式如下：

定義2 Z－O 編碼技術：就是將比較數據大小的問題轉化為比較數據Z－O 編碼是否有交集。

現舉例說明Z－O 編碼技術，例如判斷x 和y的大小，x＝10，y＝14。二 進 制 表 示 分 別 為x＝ （1010）2，y＝（1110）2。則Ox＝ ｛1，101｝，Zy＝ ｛1111｝，即Z編碼和O編碼無交集，所以x＜y。

3.2 SSLine過程

在SSLine中，用3個函數來應用基于Z－O 編碼的閾值預篩選技術。3個函數分別是Ξ，Θ，Γ。其中普通節點用Ξ生成數據Z－O 編碼值，Sink用Θ 生成閾值Z－O 編碼值，存儲節點用Γ完成查詢操作，生成查詢結果。

N為Z－O編碼數值化函數，對于Ox＝｛1，1001｝，Zy＝｛1，0111｝，其N（Ox）＝｛11，11001｝＝｛3，25｝，N（Zy）＝｛11，10111｝＝ ｛3，23｝。其 中3 相 同，則 說 明N（Ox）＝N（Zy），即Z編碼和O 編碼有交集，x≥y。

假設最終結果N（Ox），N（Zy）無相同項，即N（Ox）≠N（Zy），即Z編碼和O編碼沒有有交集，x＜y。

HMAC （Hash－based message authentication code）為哈希消息摘要生成函數，一般采用HMAC－MD5 或者HMAC－SHA1算法，生成固定長度的消息摘要。

對于HMAC 來說，具有單向性，只有HMACg（N（Ox））＝HMACg（N（Zy））時，N（Ox）＝N（Zy）；HMACg（N（Ox）≠ （HMACg（N（Zy））時，N（Ox）≠N（Zy）。并且通過HMACg（N（Ox））和HMACg（N（Zy））是無法推出N（Ox）和N（Zy）的具體值的。其中g為密鑰。

対于兩層傳感器網絡多維數據查詢，SSLine實現過程如下偽代碼所示。其中Sink為匯聚節點，Storage Node為存儲節點，si為普通節點，存儲節點下層共有 ［IDmin，IDmax］個普通節點。

算法：SSLine 算法輸入：時間周期t，Skyline查詢，普通節點si 收集感知數據Di＝ （d1，d2，…，dn），（i為傳感器ID，n為感知數據維度）輸出：Skyline查詢結果Sink→Storage Node：t，Θ（G1），…，Θ（Gn）si→Storage Node：i，t，Ξ（d1），…，Ξ（dn），Dik Storage Node：for i＝IDmin to IDmax do if（Γ（i，Ξ（d1），Θ（G1））＝1） for j＝2to n do if（Γ（i，Ξ（dj），Θ（Gj））＝0） DBj （dbj）＝Dik dbj＋＋ next i endif next j else for j＝2to n do if（Γ（i，Ξ（dj），Θ（Gj））＝1） DB1（db1）＝Dik db1＋＋ next i endif next j endif DA（da）＝Dik da＋＋ next i Storage Node→Sink：if（DA≠） DA∪DB1∪…∪DBn，Ξ （DA∪DB1∪…∪DBn） else

具體查詢步驟如下：

（1）當Sink要進行Skyline查詢時，會先用另一個函數Θ 對閾值進行處理，最終會發送Θ（G1），…，Θ（Gn）到存儲節點。

（2）普通節點si收集到n 維數據Di＝ （d1，…，dn）后，應用第一個哈希函數Ξ 加密得到n個定長消息編碼Ξ（d1），…，Ξ（dn），再用和Sink共享的密鑰ki，t加密Di得到Dik和Ξ（d1），…，Ξ（dn），并發送給存儲節點。

（3）存儲節點處理查詢時用到第三個函數Γ，當Γ（i，Ξ（dj），Θ（Gj））＝1為真時 （其中1≤j≤n），說明dj≥Gj；為假時說明dj＜Gj。由此判斷數據Di屬于Skyline查詢哪個數據區域，位于A 區放入數據集DA 中，位于Bi區放入數據集DBi中 （n≥i≥1），位于C 區應當舍棄。當把所有數據做完后，如果DA 非空，則求DA∪DB1∪…∪DBn得到最終的查詢結果；DA 為空，作為查詢結果。

（4）將結果傳給Sink，Sink完成后續計算。

至此SSLine結束。

4 性能分析

4.1 安全性分析

存儲節點對數據進行一遍篩選過程中完全沒有接觸具體數據，基本運算都是針對哈希編碼進行的，而哈希編碼具有單向性，攻擊者即便俘獲存儲節點，也不可能推出原始數據值。而具體數據是采用端到端加密，即普通節點和Sink共享密鑰加密數據，也保證了存儲節點只是負責分類轉發，即便獲取了數據也無法解密。而最終上傳結果仍包含哈希編碼，使得Sink 可以在接收到數據后進行抽查驗證，看看是否所有上傳數據都是正確無誤的。

在數據隱私性保護方面，SSLine通過基于Z－O 編碼的閾值預篩選技術最大限度保證了數據的安全；但是在查詢結果完整性上，SSLine并沒有采取保護措施，主要是基于能耗的考慮，加入了數據隱私保護的SSLine的能耗會高于普通Skyline。

4.2 能耗分析

對于能耗增加方面，從計算和通信兩方面都有所增加。計算方面，數據加密、Z－O 編碼和哈希編碼等一系列安全計算操作都會增加計算復雜度；通信方面，因為在發送數據同時要附帶哈希編碼消息摘要，所以通信量也會增加。

在降低能耗降低方面，通過網絡分層和閾值選取從策略上降低能耗。通過網絡分層，將大部分通信和計算能耗轉移到存儲節點，降低普通節點壓力；閾值選取方面，通過閾值篩選使結果集盡可能小也能有效降低通信量，降低能耗。

4.3 仿真實驗

以SkySensor為比較對象來進行仿真實驗。重點比較安全的SSLine相比沒有安全保護機制的SkySensor的能耗。

使用多維數據集在MATLAB 平臺上對SSLine 和SkySensor進行仿真，在長寬均為400 m 的區域有200－500個普通節點隨機分布，4 個存儲節點較均勻分布，居中一個為Sink節點。仿真實驗中，忽略計算量，主要考慮通信量，實驗仿真僅考慮獨立數據分布，暫不考慮相關數據分布和反相關數據分布。全部實驗均進行1000 個時間周期，即1000輪Skyline查詢。能耗值是指具體固定周期內節點平均能耗。

（1）第一組實驗仿真針對不同維度數據 （2到5維）的SSLine和SkySensor的能耗表現。實驗區域內固定有300個普通節點隨機分布，4個存儲節點較均勻分布。

根據SSLine和SkySensor對于不同維度數據查詢時的能耗表現，得出圖3。

圖3 不同維度時的能耗表現

通過圖3 得出，隨著數據維度的增加，SSLine 和SkySensor的能耗都顯著增加。但相比而言，二維數據情況下，SSLine是SkySensor能耗的1.4倍；三維數據情況下，SSLine是SkySensor 能耗的1.07 倍；四維數據情況下，SSLine是SkySensor 能耗的1.18 倍；五維數據情況下，SSLine是SkySensor能耗的1.33倍；平均來說，SSLine相比SkySensor能耗增加了0.29倍，但是隨著感知數據維數的增加，SSLine能耗越來越大，表明SSLine對高維數據查詢表現不理想，仍有改進空間。但在較低維度數據查詢時，即二三四維度Skyline查詢可以應用SSLine。

SSLine和SkySensor對于不同維度數據查詢時各類節點能耗表現的實驗數據如表1和圖4所示。

表1 不同維度數據查詢仿真結果

圖4 不同維度時各類節點能耗表現

對比了SSLine和SkySensor對不同維度Skyline查詢整體表現后，再看不同維度時SSLine和SkySensor各類節點平均能耗，由表1、圖4可知，雖然SSLine整體來說能耗比SkySensor要大，但SSLine的能耗很大一部分由資源豐富的存儲節點承擔，SSLine的普通節點的能耗甚至要優于SkySensor的節點能耗，這就是SSLine的一大優勢，充分保障了普通節點的使用壽命。

（2）第二組實驗仿真比較不同網絡規模 （相同區域內放置200～500個普通節點）的SSLine和SkySensor的能耗表現。實驗數據為二維數據。

根據SSLine和SkySensor對于不同網絡規模數據查詢時的能耗表現如圖5所示。

圖5 不同網絡規模下的能耗表現

通過圖5得出，針對不同規模的傳感器網絡，SkySensor的能耗變化增長緩慢，基本保持平穩。而SSLine針對規模不斷擴大的網絡，其能耗增加較快，但仍屬于線性增加。相比來說，SSLine相比SkySensor能耗較大，相差在1.5倍到2倍之間。

根據SSLine和SkySensor對于不同網絡規模數據查詢時各類節點的能耗表現如表2和圖6所示。

表2 不同網絡規模下仿真結果

對比了SSLine和SkySensor對不同規模Skyline查詢整體表現后，再看不同網絡規模下SSLine和SkySensor各類節點平均能耗表現。由表2、圖6 可知，SSLine的存儲節點承擔了絕大部分能耗，其能耗是普通節點能耗的數十倍甚至上百倍。在相同網絡規模下SSLine的普通節點的能耗要稍優于SkySensor的節點能耗，這再次佐證了SSLine的普通節點的能耗水平很低。

圖6 不同網絡規模下各類節點能耗表現

綜上實驗，SSLine整體能耗要比SkySensor的能耗大，但是SSLine的能耗基本都集中在存儲節點身上，其普通節點能耗水平甚至優于SkySensor，表明了SSLine不僅保證了查詢的安全，同時在網絡能耗控制和網絡壽命上也有一定優越性。

5 結束語

本文提出的SSLine協議的數據隱私性保護通過基于Z－O編碼的閾值預篩選技術來實現，并通過網絡分層，使其具有安全性和盡可能少的能耗增加。分析和實驗仿真結果表明，SSLine具有良好的安全性，在能耗方面也表現突出，普通節點相比沒有安全措施的Skyline查詢協議SkySensor幾乎沒有能耗增長。

雖然SSLine相比現有協議安全性能更好，但是存儲節點的能耗仍然偏高，需進一步尋找安全策略或通信方式減少其能耗；另外，由于沒有考慮完整性驗證，其安全性能有限，也需要做進一步研究。

［1］Dai Hua，Qin Xiaolin，Liu liang，et al.Z－O encoding based privacy－preserving MAX／MIN query protocol in two－tiered wireless sensor networks［J］.Journal of Electronics ＆Information Technology，2013，35 （4）：970－976.

［2］Lee K C K，Zheng B，Lee W－C.Z－SKY：An efficient skyline query processing framework based on Z－order［J］.Very Large Data Bases，2010 （2）：333－362.

［3］Su I－Fang，Chung Yu－Chi，Lee Chiang.Efficient skyline query processing in wireless sensor networks［J］.Parallel Distrib Comput，2010，70 （6）：680－698.

［4］DOU Yi，HUANG Haiping，WANG Ruchuan，et al.Scure range query in two＿tiered wireless sensor networks［J］.Journal of Computer Research and Development，2013，50 （6）：1253－1266 （in Chinese）.［竇軼，黃海平，王汝傳，等.兩層無線傳感器網絡安全范圍查詢協議 ［J］.計算機研究與發展，2013，50 （6）：1253－1266.］

［5］XIN Junchang，SHI Lingxu，WANG Pei，et al.Filter－based probabilistic skyline query processing algorithm in wireless sensor network ［J］.Journal of Northeastern University （Natural Science），2014，35 （7）：944－948（in Chinese）. ［信俊昌，石凌旭，王培，等.傳感器網絡中基于過濾的概率Skyline查詢算法［J］.東北大學學報（自然科學版），2014，35 （7）：944－948.］

［6］Chen Baichen，Liang Weifa，Jeffrey X Y.Energy－efficient skyline query optimization in wireless sensor networks ［J］.Wireless Networks，2012，18 （8）：985－1004.

［7］WANG Haixiang，ZHENG Jiping，SONG Baoli.Skyline query processing in wireless sensor networks ［J］.Computer Science，2013，40 （8）：14－23（in Chinese）.［王海翔，鄭吉平，宋保利.無線傳感器網絡中的Skyline查詢處理技術 ［J］.計算機科學，2013，40 （8）：14－23.］

［8］Zhang Rui，Shi Jing，Zhang Yanchao.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.

［9］Shi Jing，Zhang Rui，Zhang Yanchao.A spatiotemporal approach for secure range queries in tiered sensor networks［J］.IEEE Transactions on Wireless Communications，2011，10（1）：264－273.

［10］Yu Chia－Mu，Tsou Yao－Tung，Lu Chun－Shien，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.