宋 玲，武佩宁

（广西大学 计算机与电子信息学院，广西 南宁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.