基于时空相关的传感器网络汇聚查询算法

王雷春，李艳梅，周国玉

（湖北大学计算机与信息工程学院，湖北 武汉430062）

0 引言

传感器网络（wireless sensor networks，简称WSN）中节点的能量极其有限，网络中的传感器由于电源能量的原因经常失效或废弃.如何在网络工作过程中节省能源，最大化网络的生命周期，是传感器网络研究所面临的重要挑战.

在传感器网络中，能量消耗的大部分来自网络中数据传输.因此，减少网络中的数据传输量成为节省网络能量、延长网络生命的重要手段.其核心思想是通过网络中节点和汇聚中心对网络中的数据进行预处理，以减少网络中的数据传输量，从而实现能量的有效利用.

文献［1-2］中采用基于路线的数据收集算法处理K近邻查询，以获得距离某位置最近的K个节点的感知数据.Cheng等［3］利用采样技术减少参与查询处理的节点数目，通过设置合理的采样概率保证查询结果质量满足精度要求的同时尽量降低能耗.文献［4-7］中研究了连续近似聚集查询，利用节点感知数据具有时间相关性减少相似感知数据的发送.文献［8］中利用节点感知数据具有时间相关特性，提出了一种自适应设置节点误差配额的算法，降低网络中的数据通信量.文献［9-10］中提出了采用多条数据收集路线的并行K近邻查询处理算法DIKNN和PCIKNN，利用多条路线并行执行以减少时间延迟和能量消耗.文献［11］中设计了一种利用节点冗余保证查询处理过程鲁棒性的算法ESA，避免了因节点失效而中断，减少簇头节点收集其邻居节点感知数据的能耗.潘立强等［12］提出了一种近似Skyline查询处理算法，在满足用户查询需求的前提下最大化地节省能量.

上述算法在一定程度上减少了网络中节点数据查询的效率，降低了网络中的能量消耗，但也存在不足.如文献［4-8］中只考虑了节点感知数据具有的时间相关性，文献［11］中则只考虑了节点和邻居节点之间的数据空间相关性，因此数据查询效率都不高.另外，这些算法大多来自于传统数据查询算法的改进，在处理器、存储和通信能力方面要求较高，并不适合在资源、能量等方面严重受限的传感器网络.

本文中提出一种基于时空相关的汇聚查询算法STCAQ.STCAQ通过传感器网络中节点采样数据的时空相关性，对节点和空间区域的数据进行汇聚查询，以减少网络中的数据传输量，提高网络生命.STCAQ借鉴了上述文献的优点并进行了改进：1）当节点采样数据实际值和预测值在规定范围内时，汇聚中心只保存节点的预测值；2）空间区域在某一时刻的查询数据通过基于空间相关的判定算法求得.通过以上改进，STCAQ可以在极大地减少网络中传输的数据量的同时提高数据查询成功率和查询质量.

1 时空相关理论

1.1 基本定义

1.1.1 时间相关

定义1 节点采样数据时间相关.在传感器网络中，同一节点在相近时间采样数据所表现出来的相似性.

判定方法1 节点采样数据时间相关判定.假定节点在连续时间范围（t1，t2，…，tn）采样数据为ψt＝（d1，d2，…，dn），在时刻tn＋1采样数据为dn＋1，dθ为预先规定的阈值.如果

1）di和dj间相关（i，j∈｛1，2，…，n｝）；

2）｜dn＋1-di｜＜dθ（i＝1，2，…，n）；则dn＋1和ψ时间相关.

1.1.2 空间相关

定义2 节点空间相关.监测同一区域不同节点采样数据所表现出来的相似性.

定义3 空间读向量.传感器网络中节点Ni的空间读向量由一个滑动窗口Δt内的一系列读数组成.Ni的读数可表示为

其中xi（t）表示节点Ni在t时刻的采样数据值.

定义4 空间读向量相似度.两个节点空间读向量之间的相似程度.

两个节点和之间的空间读向量相似度SNi，Nj表示为：

这里，vi（t）和vj（t）分别是节点Ni和Nj的空间读向量，SNi，Nj∈［0，1］.

判定方法2 节点空间相关判定.两个节点是空间相关的当且仅当SNi，Nj∈Sθ，其中Sθ是预先给定的空间读向量相似度阈值.

1.2 基于时间相关的节点采样数据预测 假定传感器节点在连续时间范围内（t1，t2，…，tn）的采样值为ψt＝（d1，d2，…，dn），在第tn＋1时刻的采样值为dn＋1和ψt时间相关，则dn＋1可通过公式计算：

其中，α1，α2，…，αn为预测系数，其取值遵循时间相关规律，即离预测值越近的取值越大，反之越小.在本文中，考虑到节点采样的频率及其时间相关特点，α1，α2，…，αn取值为αi＝2i（i＝1，2，…，n）.

在STCAQ中，网络中的每个节点和汇聚中心都按照上述公式对下一时刻的节点采样值进行预测，但节点是根据该节点实际历史采样数据值对下一时刻的采样值进行预测，汇聚中心根据保存在数据库中的数据对下一时刻的采样值进行预测.

1.3 基于空间相关的区域判定

定义5 空间相关区域.指定空间范围内任意两个节点均空间相关的区域.

显然，如果查询区域不是空间相关区域，说明该查询区域内节点采样值差异较大，查询得到的结果不能反映该查询区域的真实状况，也是没有意义的.因此，本文中所指的查询区域均是空间相关区域.判定方法3（空间相关区域判定）假定指定空间区域有n个节点，如果该空间区域满足下条件：

1）通过判定方法2确定在该空间区域范围内与节点Ni（i＝1，2，…，n）空间相关的节点集为ψNi；

2）ψ＝ψN1∩ψN2∩…∩ψNn；

3）ψ≠φ；（φ为空集）

判定该区域为空间相关区域.

如果通过上述判定方法得到的ψ是一空的节点集，说明选择的查询区域节点采样数据差异较大，需要重新确定查询区域的物理范围.

定义6 空间相关区域质心.空间相关区域质心G（t，x，y，d）定义为该空间区域的重心.

假定一个空间相关区域包括n个节点，节点Ni的空间位置为（xi，yi），在时刻ti的采样值为di，则空间相关区域质心G（ti，xi，yi，di）可计算为：

2 算法描述

STCAQ包括两部分：基于时间相关预测的节点采样数据汇聚；基于空间相关的区域查询.前者对传感器网络中的节点采样数据进行基于时间相关的预测汇聚，并将结果保存在汇聚中心的数据库中；后者用于查询指定区域范围的信息.

2.1 基于时间相关预测的节点采样数据汇聚 基于时间相关预测的节点采样数据汇聚由传感器网络中的节点和汇聚中心共同完成.详细步骤描述如下：

2.1.1 节点

1）获取节点N在时间范围（t1，t2，…，tn）数据ψt＝（d1，d2，…，dn）；

2）按照公式（2）计算节点N在下一时刻tn＋1的数据预测值dp；

3）计算节点N在下一时刻tn＋1预测值dp和实际采样值dr的差值d′；

4）如果d′大于预先规定的阈值dΔ，向汇聚中心发送dr；否则，不向汇聚中心发送.上述步骤在簇形成后在各个节点内部反复执行，直到新簇产生.

2.1.2 汇聚中心

1）获取任一节点Ni在时间范围（t1，t2，…，tn）数据ψt＝（d1，d2，…，dn）；

2）按照公式（2）计算节点N在下一时刻tn＋1的数据预测值dp；

3）将节点Ni在下一时刻tn＋1的数据预测值dp存入数据库；

4）等待一定延时：如果接收到节点发送的实际采样数据值dr，对数据库中的节点在该时刻的预测值进行更新；否则，不更新.

汇聚中心反复执行上述步骤，直到网络生命终止.

2.2 基于空间相关的区域查询 基于空间相关的区域查询详细步骤可描述如下：

1）指定要查询区域Area的空间范围和查询时刻ti；

2）根据给定Area的范围，查询所有在Area区范围的节点；

3）根据判定方法1），计算这个空间区域所有空间相关的节点集ζnode；

4）如果ζnode＝φ，转到步骤1）；否则，转到下一步；

5）按照公式3）计算Area的质心G（ti，xi，yi，di），即为Area的查询值.

指定空间区域查询结果与空间区域的选择有关.空间区域中相关节点数越多，相关度越大，结果越精确；反之，结果越难反映空间区域的查询结果.

3 实验结果分析

为了评价算法的性能，在文献［13］中的模拟器上实现了算法STCAQ和ESA［11］，并对两种算法在能量消耗、查询成功率和查询质量等方面的性能进行了比较.实验的硬件环境为双核Intel CPUP4（2×2.1 GHz），2 048MB内存；软件环境为Ubuntu操作系统、Eclipse开发工具.

根据文献［14］，无线通信电路发送和接收1Byte的能量消耗公式为Et＝α＋γ×dn，Eγ＝β.其中α为通信发送电路消耗的能量，γ为传输放大器消耗的能量，d为传

输距离；n为路径损失因子（path loss factor），β为通信接收电路消耗的能量.采用文献［13］中的参数：α＝45nJ／bit，γ＝10pJ／bit／m2，β＝135nJ／bit，e＝2.其他参数如表1所示.

表1 实验参数

3.1 能量消耗比较 图1显示了失效节点数目对能量消耗的影响.对于其他算法，随着失效节点数目的增大，查询处理过程因查询节点失效而中断的概率增大，为了获得正确的查询结果，算法需要反复重新执行，带来了大量的能量消耗.而STCAQ算法基于时空相关的预测查询算法，在没有节点有异常情况时，不需要向簇头发送查询处理数据，因而极大减少了网络中的能量消耗.

图1 算法能量消耗比较

3.2 查询成功率和查询质量比较 图2显示了网络失效节点数目对查询成功率的影响.由图2可知，随着网络中节点失效数目的增加，两种算法的查询成功率和查询质量均逐渐降低；与ESA算法相比，STCAQ算法的查询成功率和查询质量下降较为缓慢.这是因为网络中失效节点数的增加，影响了查询的成功，导致查询成功率和查询质量下降；而STCAQ算法的查询区域基于空间相关，区域查询的结果可由区域中空间相关的节点计算得到，受网络中失效节点影响较小.

图2 算法查询成功率和查询质量比较

3.3 网络数据传输量比较 图3显示了不同算法随着网络生命变化时的网络中的数据传输量.由图可知，随着网络生命的减少，几种算法的网络数据传输量都在减少，而STCAQ算法减少最为缓慢.这是因为，随着网络生命减少，网络中有效工作的节点数目减少，因而减少了查询时网络中的数据传输量.STCAQ算法在正常情况下，是进行预测查询，只在有异常情况时才进行数据传输，因而减少缓慢.

图3 算法平均查询时延比较

图4 算法平均查询时延比较

3.4 查询时延比较 图4显示了网络中活跃节点数目减少对算法查询延时的影响.由图4可知，随着网络中活跃节点减少，ESA算法的查询延时也减少，STCAQ算法查询延时基本不变.在ESA算法中，随着网络中活跃节点减少，节点处理和传播的时延也减少，降低了算法的查询时延.STCAQ算法在正常情况下是预测查询，只在有异常情况时才进行数据传输，因而查询时延变化较小.

4 结论

提出一种基于时空相关的传感器网络汇聚查询算法STCAQ.STCAQ依据网络中节点采样数据的时空相关性，分别提出基于时间相关的节点预测算法和基于空间相关的空间相关区域查询算法.仿真实验表明，与ESA算法相比，STCAQ在保持较高的查询成功率和查询质量的同时，减少网络数据通信量，节省了网络能量.下一步的工作是在真实的环境中实现STCAQ，进一步对其进行验证和改进.

［1］Wu Shanhung，Chuang Kunta，Chen Chungmin，et al.Toward the optimal itinerary-based KNN query processing in mobile sensor networks［J］.IEEE Transact ions on Know ledge and Data Engineering，2008，20（12）：1655-1668.

［2］Fu Taoyang，Peng Wenchih，Lee Wangchien.Parallelizing itinerary-based KNN query processing in wireless sensor networks［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22（5）：711-729.

［3］Cheng Siyao，Li Jianzhong，Ren Qianqian，et al.Bernoulli sampling based（epsilon，delta）-approximate aggregation in larger-scale sensor networks［C］／／Proceedings of the 29th IEEE International Conference on Computer Communications.San Diego，2010：1181-1189.

［4］Jain N，Yal agandula P，Dahlin M，et al.STAR：Self-tuning aggregation for scalable monitoring［C］／／Proceedings of the 33rd International Conference on Very Large Data Bases，Vienna，2007：962-973.

［5］Tang Xueyan，Xu Jianliang.Adaptive data collect ion strategies for lifetime-constrained wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（6）：721-734.

［6］Tang Xueyan，Xu Jianliang.Optimizing lifetime for continuous data aggregation with precision guarantees in wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2008，16（4）：904-917.

［7］Chen Baichen，Liang Weifa，Zhou Rui，et al.Energy-efficient top k-query process in wireless sensor networks［C］／／Proceedings of the 19th ACM Conference on Information andKnowledge Management.Toronto，2010：329-338.

［8］Jain N，Yalagandula P，Michael Dahlin，et al.Self-tuning bandwidth-aware monitoring for dynamic data streams［A］.Proceedings of the 22nd International Conference on Data Engineering［C］／／IEEE Computer Society，Washington，2009：114-125.

［9］YAO Y X，TANG X Y，LIM E P.Localized monitoring of KNN queries in wireless sensor networks［J］.The Very Large Database Journal，2009，18（1）：99-117.

［10］WU S H，CHUANG K T，CHEN C M，et al.Toward the optimal itinerary-based KNN query processing in mobile sensor networks［J］.IEEE Transactions on Knowledge and Data Engineering，2008，20（12）：1655-1668.

［11］刘亮，秦小麟，郑桂能，等.能量高效的无线传感器网络空间范围查询处理算法［J］.计算机学报，2010，34（5）：763-778.

［12］潘立强，李建中，骆吉洲.无线传感器网络中一种近似Skyline查询处理算法［J］.软件学报，2010，21（5）：1020-1030.

［13］COMAN A，SANDER J，NASCIMENTO M A.Adaptive processing of historical spatial range queries in peer-to-peer sensor networks［J］.Distributed and Parallel Databases，2007，22（2／3）：133-163.

［14］RAPPAPORT T.Wireless communications：principles and practice［M］.New Jersey：Prentice-Hall Press，1996.