无线传感器网络ε-近似查询处理算法研究

《无线传感器网络ε-近似查询处理算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文无线传感器网络ε-近似查询处理算法研究RESEARCHONε-APPROXIMATEQUERYPROCESSINGALGORITHMSINWIRELESSSENSORNETWORKS高静哈尔滨工业大学2010年6月国内图书分类号：TP393.01学校代码：10213国际图书分类号：004.9密级：公开工学硕士学位论文无线传感器网络ε-近似查询处理算法研究硕士研究生：高静导师：李建中教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2010年6月授予学位单位：哈尔滨工业大学C

2、lassifiedIndex:TP393.01U.D.C:004.9DissertationfortheMasterDegreeinEngineeringRESEARCHONε-APPROXIMATEQUERYPROCESSINGALGORITHMSINWIRELESSSENSORNETWORKSCandidate：GaoJingSupervisor：Prof.LiJianzhongAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienc

3、eandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,2010Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要无线传感器网络是由大量具备感知、计算和通信能力的传感器节点组成的以数据为中心的自组网络，已经广泛应用于医疗监护、军事侦察、环境和交通监测、空间探索和灾难救助等领域。在许多应用中，能够反映监测区域的概况信息的

4、感知数据的聚集结果以及Top-K查询结果，对用户有着重要的意义。传感器网络中，早期聚集查询和Top-K查询主要以精确算法为主。然而，数据在采集时的错误和传输过程中的干扰使得感知数据不可避免地带有一定的噪声。为了进一步地减少查询的能量消耗，近年的研究工作主要集中在近似的查询处理方法。然而，现有的近似查询处理方法通常处理全网数据，无法对区域查询提供有效的支持；另外，现有的近似查询方法针对固定的误差界限，无法达到任意误差，并且不能不误差进行灵活地调整。针对以上两个问题，本文丰富并扩展了ε-近似查询处理架构，提出了能够处理任意

5、查询区域和任意误差的近似聚集查询方法和近似Top-K查询方法。对于聚集函数SUM和MIN，本文分别提出了EA-Sum和EA-Min算法。EA-Sum算法采用了动态规划的思想计算满足用户要求的任意区域和任意误差的最优数据传输策略，有效地降低了能量开销。EA-Min算法通过仅传输可能为最小值的节点的数据来降低能量损耗。本文提出了EA-TopK算法，该算法使用了过滤的思想，将不可能成为Top-K结果数据抛弃，以达到减少计算和通信开销的目的。EA-TopK算法不仅能够支持任意的查询区域和任意的误差，还能够保证查询结果中正确的结

6、果的概率满足用户给定的要求。对于EA-Sum算法、EA-Min算法和EA-TopK算法，本文在真实的数据集合上进行了实验。实验结果证实了本文提出的算法的能够获得正确的查询结果，并且能够有效地降低能量消耗。关键词：无线传感器网络；聚集查询；Top-K查询；ε-近似；区域查询I哈尔滨工业大学硕士学位论文AbstractWirelesssensornetworksisakindofwirelessself-organizingnetworkswithadistinctdata-centricproperty,whichcon

7、sistsofalargenumberofsensornodesthatintegratesensordevices,dataprocessingunitandthemodulefortheshortdistancewirelesscommunications.Wirelesssensornetworkshavebeenusedfornumerousapplicationsincludingmedicalmonitoring,militarysurveillance,environmentandtrafficmonit

8、oring,spaceexplorationanddisasterrelief.Inmanyreal-worldscenarios,theresultsofaggregationqueriesandTop-kqueriesareimportantforuserstogetsummarizationinformationaboutt