无线传感器网络不重复记录求和近似算法

摘 要：

针对现有的求和算法基本上都是对副本敏感的算法，提出一种对副本不敏感的求和近似算法FM-S。网络中各节点由FM-S和服从二项分布的随机数样本对节点记录进行哈希转换以填充一个长度为L的二进制求和序列，并且每个节点会把生成的序列转发给路由树中的父亲节点，根节点将接收到全网的求和序列，最终根据此序列可计算出网络中不重复记录求和的近似值。实验结果显示该算法是一种分布式、低功耗、容错性高、扩展性和健壮性强的聚集查询算法。

关键词：无线传感器网络；分布式算法；求和查询；近似算法；聚集查询

中图分类号： TP212.9

文献标志码：A

Approximate summation algorithm of distinct records for wireless sensor network

1.School of Information Science and Engineering， Hunan University，Changsha Hunan 410082，China；

2.College of Electrical and Information Engineering， Hunan University，Changsha Hunan 410082，China；

3.College of Biomedical Engineering，South-Central University for Nationalities，Wuhan Hubei 430000，China

Abstract：

Since the existing summation aggregation algorithms are almost duplicate-sensitive， an approximate algorithm Flajolet-Martin SUM （FM-S） of distinct summation query for Wireless Sensor Network （WSN） was proposed. In FM-S， each node in WSN combined the FM-S algorithm and the random number sample of binomial distribution to do hash conversion so as to fill a summation sequence of length L， and each node forwarded the generated sequence to the father node in routing tree. Then the root node received the summation sequence of whole network. Finally， according to the sequence of root node， the approximation summation value of distinct records in sensor networks could be obtained. The experimental results show that the distributed algorithm is of low power consumption， high fault tolerance， robustness and scalability.

Key words：

Wireless Sensor Network （WSN）；distributed algorithm；summation query；approximate algorithm；aggregate algorithm

0 引言

目前，无线传感器网络广泛应用于交通管制[1]、医疗卫生[2]和建筑物健康监测[3]等领域。聚集运算操作经常在无线传感器网络的数据查询处理中使用，SUMmation（SUM）聚集查询是将传感器网络中所有节点采集的数据进行求和。SUM聚集对重复数据是敏感的，大量冗余数据的存在会严重影响最终的聚集结果，但是在很多的情况下，并不需要知道传感器网络SUM聚集的准确值，可以用近似值来代替准确值。本文的FM-S（Flajolet-Martin SUM）算法就是一种近似SUM聚集算法，该算法有效地解决了SUM聚集对重复数据敏感的问题，能够提高网络的整体性能。

为了减少网络的通信开销，延长网络的寿命，在实际中会采用分布式聚集查询。现在大部分分布式聚集查询的核心思想是Madden等[4]提出的Tiny Aggregation （TAG）算法，及TinyDB[5]数据库系统。算法思想是将聚集查询通过类SQL语句下发到整个传感器网络，并由路由算法生成一棵代表全网节点的路由树。在整个聚集过程中，节点将会把接收到来自子节点的数据集和自己生成的数据集合并生成一个新的数据集，并把新的数据集发送给父节点，最终汇聚节点会得到一个包含了全网所有数据的聚集值。

在现实环境中，传感器节点的部署非常复杂，节点随时都有可能因为电量耗尽而失效，很容易导致传感器网络拓扑结构的变化；同时节点在发送数据时由于无线信道存在环境干扰、包冲突和信噪比低从而导致丢包和通信连接失败，就会破坏生成的路由树，从而会严重影响最终的聚集值[6]；如果选择数据重发则会消耗更多的能量，缩短网络的寿命[7]，同时也会造成数据的冗余，最终会严重影响对副本敏感的聚集，例如COUNT和SUM。

如何在环境异常复杂，通信能力、计算能力和能量非常有限的无线传感器网络中进行包括SUM查询在内的聚集查询是一个全新的挑战，目前已经有一些这方面的研究成果。

Liu等[8]提出了基于节点历史数据代表路由树的近似查询算法。算法的主要思想是通过节点间的相关度构建代表路由树进行近似聚集查询。由于查询时只要遍历代表路由树，因此可以减少通信开销，延长网络寿命；但结果容易受网络拓扑结构变化的影响。

Considine等[9]提出了基于Sketch的近似聚集查询算法。算法的核心思想是采用Sketch技术对节点的原始记录数据进行压缩传输，并在网内进行聚集。与其他算法相比，该算法传输的是压缩数据；但是，该算法需要全网的原始数据参与聚集运算，因此通信开销比较大。

Xin等[10]提出了一种基于时间相关性的近似聚集算法。主要思想是为节点设置一个筛选范围，节点数据不在筛选范围内时才将数据传输给汇聚节点，否则汇聚节点采用历史数据计算近似聚集结果。能有效应用于数据连续的聚集；但是算法误差较大。

Su等[11]提出了一种基于空间相关性的近似聚集算法。算法核心思想是网络中各节点建立代表模型，当某一个节点的数据不能被其他节点代表时，才将数据传输给汇聚节点。算法处理Snapshot查询时效率较高；但数据流连续的查询效率较低。

目前，还没有一种有效的算法既能够提高传感器网络的性能，又能解决SUM聚集对副本敏感的问题。本文在FM（Flajolet-Martin）估计计数算法的基础上提出一种对副本不敏感的聚集求和近似算法，记为FM-S。该算法在FM估计计数算法的理论基础上总结出了一种生成二进制求和序列的高效算法，根据该序列可以近似求出传感器网络的SUM聚集值，同时，FM-S算法引入了多路复用（Multi-Path Routing）技术和重复不敏感策略（Duplicate Insensitive Sketches）。FM-S算法在进行SUM聚集操作时对重复数据不敏感，可以得到求和的近似值。例如，节点某一时刻的记录值集合为M={x1，x2，x3，x4，x5}，xi=（pi，ci，ti），其中：pi表示传感器节点，ci表示观测值，ti表示时间；只有当节点记录值的pi，ci，ti参数都相同时才算是节点重复的感知数据。假设x1和x3，x2和x4是重复记录，简单来说，如果使用TAG算法计算SUM=c1+c2+c3+c4+c5，而使用FM-S算法近似计算SUM≈c1+c2+c5，与TAG算法相比，FM-S算法既提高了结果的准确性，又提高了网络的性能。

1 不重复记录求和查询近似算法FM-S

不重复记录求和近似算法FM-S分成以下三个步骤：

步骤1 开始时基站节点采用洪泛的方式将SUM查询传发到传感器网络中所有节点，并且将所有传感器节点按照路由算法生成一棵路由树。

步骤2 各节点把从子节点接收到的数据集以及自己生成的数据集合并生成一个新的数据集M={x1，x2，x3，…}，对新数据集中的每一条记录执行分布式FM-S算法生成一个长度为L的求和序列FM-S（M）[0，1，…，L-1]，每个节点再将多个求和序列组织成一个二维序列发送给上一层节点。

步骤3 重复执行步骤2，根节点会得到一个可用于代表全网数据集结构的FM-S（M）二维序列，最终由这个N行FM-S（M）二维序列估算出全网的不重复记录的SUM值。

1.1 分布式FM-S算法

FM近似计数查询算法最先由Flajolet和Martin在文献[12]中提出，FM算法最大的好处是不需要多次扫描数据库或数据流，只需要一次扫描就可以快速估计出数据库或数据流中不重复记录的个数，并且算法只要在一块远小于数据规模的内存空间里不断更新一个代表数据集的结构——概要数据结构，并且随时都能够根据这个结构快速获得近似查询的结果。

引理1[12] 当i

引理1在文献[12]给出了详细的证明，它是FM-S算法近似计算不重复记录求和的理论依据。

分布式FM-S算法所涉及的参数定义如下：

p1，p2，…，pn代表n个任意相连的无线传感器节点。

M为节点pi在一段时间内生成的数据集，M={x1，x2，x3，…}，xi=（pi，ci，ti）。其中：pi表示传感器节点，ci表示观测值，ti表示时间，只有节点记录值的pi，ci，ti参数都相同时才说明是同一个传感器节点在同一时刻生成的数据，即为重复数据。

FM-S（M）表示数据集M按FM-S算法生成长度为L的二进制求和序列，记为FM-S（M）[0，1，…，L-1]。

SUM表示通过运算得到的不重复记录求和的近似值。

N表示整个网络中所有的数据子集的并集M中不重复记录的个数。

Y表示随机产生符合B（ci，2-δ）二项分布的随机样本，其中δ=lb ci-2 lb lb ci。

Hash（x）表示对样本中的每一个值x进行Hash变换的函数，经过Hash变换后会得到一个长度为L的二进制序列y。

bit（y，k）表示二进制序列y中的第k位。

p（y）表示二进制序列y中最右边的1所处的位置，其公式定义为：

p（y）=min{k|bit（y，k）=1}（1）

FM-S算法的特点就是能用一小块远小于数据集数据范围的内存空间表示数据集，用FM-S（M）表示将数据集M进行FM-S运算后得到的长度为L的二进制序列y（LM），表示为FM-S（M）[0，…，L-1]，其公式定义如下：

FM-S（M）[i]=1，iffx∈M，p（Hash（x））=i（2）

在上述理论的基础上，不重复记录求和的定义如下：

定义1 给定一个数据集M={x1，x2，x3，…}，其中xi=（pi，ci，ti），不重复记录求和可以记为：

其中ci严格保持唯一性，当ci的值较小时，可以使用FM计数序列的方法进行近似求和，即将ci的值转化为计数ci个非重复记录。例如：假如非重复记录ci的值为5，则此时可以转化成5条非重复记录（pi，ci，t1，1），…，（pi，ci，ti，5），利用分布式FM非重复计数算法填充FM-S序列，然后根据FM-S序列求出的非重复记录数就是ci的值。

当ci的值比较小时，可以用估计计数算法来计算SUM的值，并且它与估计计数算法具有一样的准确性和时间复杂性O（ci）；但是当ci的值很大时，这种方法的使用效果并不是很理想。因此，必须采用一种高性能的算法来处理ci值很大时的情况。

为了充分利用FM算法思想来计算非重复求和，可以生成一个二进制求和序列（Summation Sketches），然后利用FM-S估计方法求出ci的值。可以采取一种比较有效的方法来生成求和序列，方法具体分为两步：1）根据引理1，当i< lb n-2 lb lb n时，FM-S（M） [i]被设置为1的概率几乎为100%；因此首先设置求和序列的前δ=lb ci-2lb lb ci位全部为1。2）通过生成符合要求分布的随机样本，并且对样本中的每个值采用Hash变换来填充求和序列余下的L-δ位。最终，可以生成一个长度为L的二进制求和序列FM-S（M）[0，…，L-1]。

由FM-S算法可知，一个记录值xi的二进制求和序列第z位是1必须满足0≤j

本文算法中将FM-S（M） [0，1，…，L-1]中最左边的0所在的位置记为大小为lb n的标志性位，可以近似计算传感器网络中非重复记录ci的值。

标志位的公式定义如下：

R=leftmost{i|FM（M）[i]=0}（4）

引理2[12] r为运行FM-S算法得到的标记位，r的期望值E（r）≈lb （φci），其中φ=0.775351，r的方差σ（r）≈1.12。

从引理2可以知道，使用φ纠错性标志位能够获取ci相对准确的估计值SUM（i），其计算表达式如下所示：

SUM（i）=（1/φ）2r（5）

根据上文的分析可知，在节点pi运行分布式FM-S算法的伪代码如下所示：

Program SumInsert（Mi）

Input： Mi is Multiset of data in pi

Output： FM-S[n][0，…，L-1]

Do while not eof（Mi）

{

cgetElement（Mi）

dselect_prefix（c）

/*设置FM-S序列的前d=lb c-2 lb lb c位全部为1*/

j0

while j

jj+1

FM-S[i][j]1

end while

Y[a]select_sample（seed=（x，c），c，1/2d）

/*随机生成符合B（c，1/2d）二项分布的样本Y，大小为a*/

for k0 to a

jd

例如，当数据集M中c的记录值为16384时，使用FM-S算法生成FM-S二进制求和序列值的过程如下：

1）由c=16384知d=lb c-2 lb lb c=6，于是设置FM-S序列的前6位均为1；

2）产生一个随机数样本Y，它满足二项分布B（16384，1/26），开始会产生16384个满足均匀分布U（0，1）的随机数r1，r2，…，r16384；然后统计ri（i=1，2，…，16384）中使得ri

对数据集M={x1，x2，x3，…}中每一个记录值分别生成FM-S序列，最终根节点会收到一个二维求和序列FM-S[N][0，…，L-1]，由式（5）可知，即可求出SUM=∑

例如，假设数据集M={（1，1024，12：30），（2，16384，12：40），（3，4096，12：50），（4，32768，12：50），（2，16384，12：40），（4，32768，12：50）}是某一个传感器节点P在一段时间内生成的数据集，其中有重复记录值16384和32768。

对节点P运行FM-S算法会输出一个4行16列的二维数组，如下所示：

1111 1111 0110 0000

1111 1111 1111 0100

1111 1111 1101 1000

1111 1111 1111 1010

由式（5）可知，

定理1 一个记录xi=（pi，ci，ti）生成求和序列的时间复杂度为O（lb2 ci）。

证明 αi表示要生成求和序列余下L-δi位二项分布样本的个数，生成求和序列前面δi位的时间复杂度为O（δi），αi个样本值Hash转换生成求和序列的时间复杂度为O（αi），生成xi求和序列总的时间复杂度为O（δi+f（αi）+αi），其中f（αi）表示选取样本大小为αi的时间。因此，时间取决于αi和用于选取αi的方法，由二项分布期望公式知αi的期望值如下：

E（αi）=ci×2-δ，δ=lb ci-2 lb lb ci，即

lb2 ci≤E（αi） < 2 lb2 ci

所以FM-S算法改进后生成一个记录的求和序列的时间复杂度为O（lb 2 ci）。

1.2 产生二项随机数

其中F（x）具有单调非降特性。

即：G（y）=y；Y是在[0， 1]区间上具有均匀分布特性随机变量的CDF，因此，Y=F（x）IID U（0，1）；显然G（y）=y与X的分布特性无关。

若随机变量R～U（0，1），也就是说服从均匀分布，并且有

CDF{CDF（n-1）

pn； n=1，2，…

令{CDF（n-1）

产生X随机数的算法步骤如下：

1）产生一个（0，1）区间上均匀分布随机数r（RND）；

2）若CDF（n-1）

产生随机数算法的伪代码如下所示：

如果随机变量X服从二项分布B（n，p），并且分布律满足的条件为P{X=k}=Cknpk（1-p）n-k（k=1，2，…，n），其中0

产生满足二项分布B（n，p）随机数列的算法步骤如下：

1）产生n个满足均匀分布U（0，1）的随机数r1，r2，…，rn；

2）统计随机数ri（i=1，2，…，n）中满足条件ri≤p时ri的个数记为ni。

算法重复进行多次可以产生满足要求的随机数序列n1，n2，…，nk。

2 仿真实验及结果分析

2.1 仿真实验

仿真实验是在无线传感器网络仿真程序TAG[4]上进行的。在实验中，节点的数目由网络直径大小决定，节点个数是网络直径大小的平方，通过改变网络直径和丢包率等参数来进行实验。在本文算法中，每个节点要传送一个10行16列FM-S二位数组，每个节点要传送的无压缩数据40字节。本文算法采用了文献[12]中提到的压缩技术进行压缩，能将数据压缩至原来的1/4左右，显著减少了网络的传输量。

选取TAG系统中SUM算法（TAG-S）和本文的FM-S算法进行对比实验。

TAG仿真程序模拟现实环境中存在丢包时各节点传输数据的情况。当有丢包发生时，TAG-S算法会选择重发丢失的包，而FM-S采用了多路复用技术和重复不敏感策略，不需要重新发送也能获取比较准确的聚集数据，因此FM-S算法能够显著减少数据的发送量，延长网络的寿命。在这种环境中，会有大量的数据包无法发送至汇聚节点，必然会存在误差。其中，误差率的公式定义如下：

图2考察在模拟现实网络环境下的平均误差率与网络直径的关系。从图2可知，TAG-S算法误差非常大，而本文FM-S算法可将误差范围控制在25%～35%。

图3考察在模拟现实网络环境下TAG-S和FM-S算法随着网络直径增加得到SUM聚集平均值的情况。从图3可知，在模拟现实网络环境下，TAG-S算法得到的实验结果范围非常大，而FM-S实验结果范围相对较小，而且随着网络直径的增加，两种算法实验结果范围的差距越来越明显。

图4考察两种算法随着网络丢包率增加得到SUM聚集平均值的情况。从图4可知，TAG-S算法得到的实验结果范围非常大，而FM-S实验结果范围相对较小。

2.2 算法性能分析

与TAG-S算法相比，FM-S算法具有以下特性：

1）功耗低。TAG-S算法会将所有数据全部上传至汇聚节点，当有丢包发生时，还会选择重发，虽然在传输过程中会将重复的数据删除，但仍然需要传送大量数据；而本文算法每个节点都只需要传送一个经过压缩的FM-S二维数组，需要传输的数据量远少于TAG-S算法，从而降低了节点能量的消耗，延长了网络的寿命，图1的结果很好地说明了这一点。

2）不受重复数据的影响。TAG-S算法没有考虑重复数据的影响，如果有丢包发生，TAG-S算法会选择重发，同一条数据会在网络中存在多份，将会严重影响到最终的聚集结果，而本文算法充分考虑到这个缺点，采用FM-S方法对副本不敏感的算法，确保最终结果的正确性。

3）误差较小。在存在丢包的模拟现实环境下，TAG-S算法有很大的误差；而本文算法采用多路复用技术和重复不敏感策略，即使网络中有丢包发生，也不会重发，并且生成的二进制求和序列FM-S对重复数据不敏感，极大提高了网络的容错性，因此本文误差较小，图3和图4的结果很好地说明了这一点。

3 结语

本文提出了一种基于无线传感器网络的不重复记录求和近似算法。与其他SUM聚集算法不同，FM-S算法对重复数据不敏感，采用重复不敏感策略来处理重复数据，并且引入了多路复用技术，确保了算法具有相对较小的误差，提高了网络的容错性，同时也减少了网络的通信量。因此，FM-S算法可以应用于节点能量有限，又注重SUM查询效率，并且聚集结果不要求十分准确的无线传感器网络中。

参考文献：

[1] BARBAGLI B， BENCINI L， MAGRINI I， et al. A real-time traffic monitoring based on wireless sensor network technologies[C]// Proceedings of the 7th International Wireless Communications and Mobile Computing Conference. Washington， DC： IEEE Computer Society， 2011：820-825.

[2] ZHANG F， DISANTO W， REN J， et al. A novel CPS system for evaluating a neuralmachine interface for artificial legs[C]// Proceedings of 2011 IEEE/ACM International Conference on Cyber-Physical Systems. Washington， DC： IEEE Computer Society， 2011：67-76.

[3] BOCCA M， TOIVOLA J， ERIKSSON M， et al. Structural health monitoring in wireless sensor networks by the embedded Goertzel algorithm[C]// Proceedings of 2011 IEEE/ACM International Conference on Cyber-Physical Systems. Washington， DC：IEEE Computer Society， 2011：206-214.

[4] MADDEN S， FRANKLIN M J， HELLERSTEIN J M， et al. TAG： a Tiny AGgregation service for Ad-Hoc sensor networks[C]// Proceedings of the 5th Symposium on Operating Systems Design and Implementation. New York： ACM，2002：131-146.

[5] THIAGARAJAN A， MADDEN S. Representing and querying regression models in a DBMS[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008：284-292.

[6] HU W， YANG H， HUANG L. Multidimensional data reduction based on compressed sensing for sensor network[C]// Future Wireless Networks and Information Systems. Heidelberg： Springer， 2012：721-728.

[7] SRIVASTAVA N. Challenges of next-generation wireless sensor networks and its impact on society[J]. Journal of Telecommunication，2010，1（1）：128-133.

[8] LIU Y， LIANG W. Approximate querying in wireless sensor networks[C]// Proceedings of the 3th International Conference on Pervasive Computing and Applications. Piscataway： IEEE， 2008：145-145.

[9] CONSIDINE J， HADJIELEFTHERIOU M， LI F， et al. Robust approximate aggregation in sensor data management systems[J]. ACM Transactions on Database Systems， 2009， 34（1）：1-35.

[10] XIN J， WANG X J， CHEN L. et al. Energy-efficient evaluation of multiple skyline queries over a wireless sensor network[C]// Proceedings of the 14th International Conference on Database Systems for Advanced Applications. Heidelberg： Springer， 2009：247-262.

[11] SU F， CHUNG Y， LEE C， et al. Efficient skyline query processing in wireless sensor networks[J]. Journal of Parallel and Distributed Computing， 2010，70（6）：680-698.

[12] FLAJOLET P， MARTIN G. Probabilistic counting algorithms for data base applications[J]. Journal of Computer and System Sciences， 2001，31（1）：134-143.