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

《无线传感器网络不重复记录求与近似算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、码：AApproximatesummationalgorithmofdistinctrecordsforwirelesssensornetwork1.SchoolofInformationScienceandEngineering，HunanUniversity，ChangshaHunan410082，China；2.CollegeofElectricalandInformationEngineering，HunanUniversity，ChangshaHunan410082，China；143.CollegeofBiomedicalEngineer

3、ing，South-CentralUniversityforNationalities，WuhanHubei430000，ChinaAbstract：Sincetheexistingsummationaggregationalgorithmsarealmostduplicate-sensitive，anapproximatealgorithmFlajolet-MartinSUM（FM-S）ofdistinctsummationqueryforWirelessSensorNetwork（WSN）wasproposed.InFM-S，eachnodein

4、WSNcombinedtheFM-SalgorithmandtherandomnumbersampleofbinomialdistributiontodohashconversionsoastofillasummationsequenceoflengthL，andeachnodeforwardedthegeneratedsequencetothefathernodeinroutingtree.Thentherootnodereceivedthesummationsequenceofwholenetwork.Finally，accordingtothe

5、sequenceofrootnode，theapproximationsummationvalueofdistinctrecordsinsensornetworkscouldbeobtained.Theexperimentalresultsshowthatthedistributedalgorithmisoflowpowerconsumption，highfaulttolerance，robustnessandscalability.Keywords：WirelessSensorNetwork（WSN）；distributed14algorithm；

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

7、法就是一种近似SUM聚集算法，该算法有效地解决了SUM聚集对重复数据敏感的问题，能够提高网络的整体性能。为了减少网络的通信开销，延长网络的寿命，在实际中会采用分布式聚集查询。现在大部分分布式聚集查询的核心思想是Madden等[4]提出的TinyAggregation（TAG）算法，及TinyDB[5]数据库系统。算法思想是将聚集查询通过类SQL语句下发到整个传感器网络，并由路由算法生成一棵代表全网节点的路由树。在整个聚集过程中，节点将会把接收到来自子节点的数据集和自己生成的数据集合并生成一个新的数据集，并把新的数据集发送给父节点，最终汇聚节点会得到一

8、个包含了全网所有数据的聚集值。14在现实环境中，传感器节点的部署非常复杂，节点随时都有可能因为电量耗尽而失效