基于分簇的无线传感器网络Top-K 数据查询算法

江 欣，李长庚

(中南大学 物理与电子学院，湖南 长沙410083)

0 引 言

随着物联网的发展，无线传感器网络被运用到社会活动中的方方面面，如医疗护理、森林火灾和洪水监测等［1］。数据查询是无线传感器网络应用中的一个非常关键的应用，而Top－K 查询是查询应用中的一个重要内容［2］。无线传感器网络通过监控范围中最大的监测参数(如，血压、心率、温度、土壤水分等参数)，可以起到判断人的身体指标、森林温度预警和洪水监测的作用。由于传感器节点通常都是分布在无人看护的环境中，所以，减少传感器网络的整体能耗是研究者追求的目标，能量消耗越小，节点生命周期就越长。由于无线传感器网络中的能量消耗的绝大部分是通信能耗，因此，无线传感器网络的一个迫在眉睫的问题就是如何降低网络的整体通信能耗。

为了节省通信量，TAG［3］算法采用对网内数据进行融合的思想减少数据的传输量，得到精确的查询结果。TAG算法是把这个网络看成一颗树，这样数据传输的跳数是多跳，通信能耗相对比较大。FILA［4］算法是基于过滤的算法，此过滤算法虽减少了冗余数据的上传，但当数据变化比较大时会产生很大的窗口更新代价，消耗能量较多。

针对TAG 与FILA 算法的不足，本文提出一种基于分簇的无线传感器网络Top－K 数据查询算法，首先对网络进行分簇［5～7］，每个簇选出一个簇头节点，簇中其他节点将数据传递给簇头节点，然后再传给Sink 节点，这使得传输的跳数在两跳之内，减少了发送和接收能耗。在每个节点设置过滤器值，当数据不够时利用探寻来补充数据，使得数据的传输次数减少，降低整体能耗。

1 网络分簇

1.1 簇头选举

在算法的预处理阶段，传感器网络中的节点先生成一个数，此数大于0 小于1，之后算出簇头竞争的判定值Pc(r)，让生成的数与判定值比较大小，如果数比判断值Pc(r)小，则节点就是相对应簇的簇头节点。Pc(r)的计算公式为

式中 Pc(r)为节点竞争簇头的判定值，p 为网络最初时已分簇的簇头数目，Ei为i 传感器节点的剩下的能量，E0为传感器节点最开始的能量，n 为总的传感器节点数，r 为轮数，Nch为目前传感器节点当选成簇头的数目。pEi/E0的比值可以作为选取簇头的标准，剩下的能量越多，那么，变成簇头的机会就会越大。分子中式子是作为“均衡因子”用来平衡簇头数量，而分母中加入Nchmod(1/p)是为了规避由于相同节点经常被选为簇头节点而使得能量消耗过快造成节点过早死去。

1.2 簇头数优化机制

当网络中簇头选举完成后，计算簇头间的距离，设置一个距离阈值，避免簇头与簇头之间由于距离太近或者太远引起分簇不匀，簇头之间的距离不在阈值范围内的就需重新选择簇头。簇头距离阈值U 的确定依照下式［8］

式中 U 为传感器网络中最优簇头数目，N 为传感器网络中的传感器节点总的数目，M 为传感器网络的范围边界的长度，dbs为每个簇中的簇头到Sink 节点之间的长度，通过式(2)，如果已知N 与M 的大小，通过测量dbs就可以得到相应的阈值U 的区间，Eelec为接收电路能耗，且Eelec=50 nJ/bit，εfs为自由空间模型放大器能耗，且εfs=10 pJ/bit/m，εmp为多径衰减模型的放大器能耗，且εmp=0.001 3 pJ/bit/m4。

1.3 成簇机制

当簇头优化完成之后，每个簇头通过泛洪将信息广播出去，此信息包含节点的ID 身份、节点剩下的能量和节点所在的位置，然后通知本簇中其他传感器节点，本簇的簇头节点已经选举完成，本簇中其余的传感器节点在接收到本簇的簇头发来的泛洪信息之后，算出一个成簇的权值WCL，WCL表达式如下

式中 WCL为传感器节点成为簇的权值，ECH为此簇的簇头节点剩下的能量，d(i，CH)为i 传感器节点与其对应簇的簇头节点的距离。通过式(3)分析，传感器节点剩下能量越大、所在簇的簇头节点ECH越大，而节点与簇头的d(i，CH)减小时，那么，WCL会变大，节点成为该簇的节点机会增加，WCL通过分析传感器节点剩下的能量和节点之间的距离，可以合理分簇。经过算出成为不同簇的WCL，传感器节点会选取WCL最大的簇成为其相应的簇，然后将节点的ID、位置和剩余的能量以信息的形式发送给簇头表示愿意成为本簇成员，而簇头节点在接收到相应簇的其他传感器节点发来的信息之后表示分簇过程结束。

2 算法描述

设网络中传感器节点的过滤器的值为fn(T)=BT，n=1，2，…，N。

查询过程中，在T 以后时刻，Sink 节点依照用户提出的查询要求Kt(q)，q=1，2，…，取其中最大的值作为本次用户所需要查询的KT值，即KT=max{Kt(q)，q=1，2，…}，并通过泛洪的方式向网络中的节点发送目前所需要查询的KT值。

网络中节点收到泛洪信号之后，收集的感知数据不在时间区间t(t'－T≤t≤t'，其中，t'＞T)内的感知数据去掉，把标记已传递的记号的感知数据也去掉，同时将余下的其他数据排序，获得最大的K 个值。然后将此K 个值与目前此节点的过滤器fn(t－1)对比，只向簇头节点传递大于过滤器fn(t－1)的数据，同时将向簇头节点传输的数据打上已传递记号。每个簇的簇头节点在得到本簇中其他节点上传的感知数据后，把本簇中其他节点的感知数据与簇头节点本身采集到的感知数据进行排序，获取满足要求的最大的K 个值，然后把这满足要求的K 个值发送给Sink 节点，供用户进行数据查询。

将Sink 节点收到所有簇头节点发送过来的数据看作是一个数据集Wt，设此时Sink 节点所拥有的数据集Wt一共有M 个数据，通过排序之后大小顺序为wt(1)≤wt(2)≤…≤wt(M)。如果比Bt－1大的数据的数量多于或者等于K，那么，就对最大的K 个数据进行网内存储，供用户快速查询，然后进入设定过滤器值的阶段。

如果所收集的数据集Wt中比Bt－1大的数据的数量小于K，则表示过滤器值设置偏高，使比Bt－1小的感知数据未发送过来，这需继续探寻比Bt－1小的感知数据，补全Top－K数据，满足查询的要求。本簇中的节点在获取Sink 节点的探寻的消息和条件后，将没有标记已传递记号的，同时又比探寻条件的值大的感知数据继续传递给簇头节点，然后由簇头节点上传给Sink 节点。同时把已发送的感知数据标记已传递的记号，当Sink 节点获取了满足条件的K 个值后才停止探寻，然后才把这些数据进行网内存储，供用户查询，接下来才进入设定过滤器值的阶段。

在探寻阶段之后，如果Sink 节点数据集的数据个数为M't，将收集到的感知数据排序，记wt(1)≤wt(2)≤…≤wt(M't)，通过上述的探寻过程可以确保M't大于或等于K。这时可设定一个新的Bt值作为预测值，用来判断接下来的查询能否成为有用Top－K 数据。为了减少感知数据的通信能耗，一般情况下Sink 节点不需要更新过滤器值，只在需要的情况下才去更新过滤器值。当上限值Bt大于上一时刻的Bt－1时，如果某个节点的数据超过了过滤器值时，那么表示该节点的过滤器值低了，需要将该节点过滤器设置新的Bt以阻止更多的冗余数据，当Bt小于或者等于Bt－1时，则某个节点的过滤器值可能超过Bt，而Bt是Top－K 结果与非Top－K 结果的分割点，这样可能会造成Top－K 查询结果的错误，此时应该将可能会出现的节点的过滤器值设置为Bt，保证Bt仍然是所有节点过滤器值的上限，保证Top－K结果的正确。最后，把所有需更新的传感器节点的过滤器值fn(t)更新为Bt，同时把对应的过滤器值发送到其对应的节点当中去。

3 仿真结果与分析

对算法进行仿真参数如下:传感器网络在100 m×100 m的平面下，传感器网路中传感器节点的总数为100 个，将每个节点均匀分簇，一共分成10 个簇，每个簇10 个节点，所有节点固定就不再移动。网络中所有传感器节点的初始能量相同，且E0=0.5 J，不考虑丢包率和其他因素影响。设每个节点相隔15 s 记录一个感知数据，传感器可以存储最近100 个时间点的感知数据，查询中Kt的一个常数，以整个传感器网络中的所有传感器节点发送和接收感知数据包的整体能耗作为Top－K 查询的评价指标［8］。

簇中节点发送到相对应簇的簇头节点的感知数据含有16 bits 的数据值和16 bits 的数据ID 身份，而数据ID 身份中又含有8 bits 的传感器节点ID 身份和8 bits 的时间点。基站发送给簇头节点的探寻包的大小是16 bits，发送给簇头节点更新过滤器包是16 bits。为了与本文算法进行对比，同时仿真了FILA 与TAG 两种算法并进行对比，如图1所示。

图1 网络分成10 个簇整体能耗实验结果Fig 1 Experimental results of overall energy consumption while networks is divided into 10 clusters

通过与FILA 和TAG 算法的网络整体能耗相比的仿真实验结果可以看出，当K 的取值比较小时，本文算法与FILA算法的网络整体能耗相差比较小，但是随着K 值取值越大，算法的网络整体能耗都在增加，但FILA 算法的整体能耗增加幅度比较大，能耗也较多，本文算法的网络整体能耗只是在平稳的增加，而TAG 算法不管K 值取多大，网络整体能耗都比较大。通过仿真实验对比可以看出，运用本文算法的Top－K 数据查询的网络生命周期会更长。

4 结 论

本文所提出一种基于分簇的无线传感器网络的Top－K数据查询算法，通过对无线传感器网络节点进行分簇实现数据的传输只需要1 跳或2 跳，减少数据的传输次数，达到减少通信损耗的目的，然后通过节点数据相互之间的关联性对节点设置过滤器值以降低冗余数据的传递，通过探寻过程保证Top－K 数据查询的正确性，达到降低无线传感器网络的整体能耗的目的，从而延长整个网络的生命周期。

［1］ Sakai H，Iiyamab S，Tokoc K.Evaluation of water quality and pollution using multichannel sensors［J］.Sensors and Actuators B:Chemical，2000，66:1.

［2］ Silberstein A，Braynard R，Ellis C，et al.A sampling－based approach to optimizing top－k queries in sensor networks［C］∥Proceeding of 22nd International Conference on Data Engineering，USA:IEEE，2006:68.

［3］ Madden S，Franklin M J，Hellerstein J M，el al.TAG:A tiny aggregation service for Ad Hoc sensor networks［C］∥Proceeding of the Fifth Symp on Operating Systems Design and Implementation，OSDI’02，USA:IEEE，2002:131－146.

［4］ Wu M，Xu J，Tang X，et al.Top－K monitoring in wireless sensor networks［J］.IEEE Trans on Knowledge and Data Engineering，2007，19:962－976.

［5］ Akcan H，Bronnimann H.A new deterministic data aggregation method for WSNs［J］.Signal Processing，2007，87(12):2965－2977.

［6］ 郭书城，卢 昱，许定根.基于分簇无线传感器网络的路由算法研究［J］.通信学报，2010，31(8):63－69.

［7］ 韩志杰.一种基于ARMA 的WSNs 非均衡分簇路由算法［J］.电子学报，2010，38(4):865－869.

［8］ Heinzelman W，Chandrakasan A，Balakrishman H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.