无线传感网中高效可视化算法.pdf 12页

'中国科技论文在线http://www.paper.edu.cn#无线传感网中高效可视化算法**万佳林，程思瑶（哈尔滨工业大学计算机科学与技术学院，哈尔滨150001）5摘要：随着硬件制造技术、无线传感网技术和可视化技术的不断发展，无线传感网在生活中的很多方面都得到了应用，包括环境监测、生物多样性调查和医疗卫生等各大领域；可视化技术也被应用在金融数据分析、信息管理和医疗成像等领域。随着人们对传感网查询结果的可视化需求的增加，考虑无线传感网中的可视化算法具有极其重要的意义。本文进行了相关10的研究，主要的研究成果如下：第一，本文提出了均衡抽样过程中的误差转换算法，考虑到了可视化设备的硬件信息（屏幕的宽、高和分辨率）对查询误差的影响，并给出了具体的数学证明，提高了查询的精度。最后，通过在模拟的无线传感网上进行实验，验证了算法的有效性。第二，本文研究了累加式的抽样算法，并且基于Android平台实现了可视化的原型系统。15关键词：计算机网络；传感网；聚集计算；可视化中图分类号：TP393.0AnEfficientVisualizationAlgorithminWirelessSensorNetworks20WANJialin,CHENGSiyao(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)Abstract:Withtherapiddevelopmentofhardwaremanufacturingtechnology,wirelesssensornetworksandvisualizationtechnology,wirelesssensornetworkshavebeenappliedinavarietyoffields,suchasenvironmentmonitoring,biodiversitysurveyandmedicalandhealthcare,while25visualizationtechnologyhasbeenwildlyutilizedinfinancialdataanalysis,informationmanagementandmedicalimagingsystem.Astheneedforvisualizationinsensorqueryingincreases,it"sextremelysignificanttostudythevisualizationalgorithmsinwirelesssensornetworks.Themaincontributionsofthisdissertationareasfollowing:Firstly,anuniformsamplingbasederrorconversionalgorithmisproposed.Theerrorconversionalgorithmtakesthehardwareinformation(includingthewidth,height30andresolutionofscreen)ofquerydevicesintoconsideration,andprovesthecorrectnessofthealgorithm.Somesimulatedexperimentsareconductedtoshowtheeffectivenessoftheproposedmethod.Secondly,weproposeanincrementalsamplingalgorithmandbuildthecorrespondingprototypesystemonAndroidplatform.Keywords:ComputerNetworks;WirelessSensorNetworks;Aggregation;Visualization350引言随着硬件制造技术和无线网络技术的发展，无线传感器网络越来越多地应用在日常生活中。例如，环保部门通过无线传感器网络来获取一定区域的PM2.5浓度信息等。由于传感器网络的规模一般比较大，通过sink结点来获取整个网络中的聚集感知数据以求获得精确40结果时，数据传输量可能会相当大。而在实际应用中，具有一定误差的聚集查询结果也是可以接受的。近几年以来，越来越多的研究开始考虑通过收集一小部分传感器数据来获得用户基金项目：高等学校博士学科点专项科研基金新教师类资助课题（20132302120045）；国家自然科学基金（61632010,61370217,U1509216）作者简介：万佳林(1993-)，男，硕士生，无线传感器网络通信联系人：程思瑶(1982)，女，副教授，硕导，主要研究方向：传感网、物联网、感知大数据.E-mail:csy@hit.edu.cn-1- 中国科技论文在线http://www.paper.edu.cn可以接受的具有一定误差的聚集查询结果。在无线网络技术发展的同时，针对无线传感器网络进行查询的用户设备也正在发生巨大的变革。以前人们总是通过连接到sink节点的电脑来对整个网络进行查询，返回的结果是45一系列数据。而随着智能手持设备的飞速发展，现在人们可能希望选择智能手机或者平板电脑来进行一些查询操作。而随着可视化技术的不断发展，现在人们不再满足于仅仅获得一系列传感网聚集查询的数值结果，而更倾向于得到显示在用户可视化设备上的可视化的图表，这样用户可以更直观地看到数据的变化趋势以及相关性。本课题主要针对于无线传感器网络中可视化算法的研究及相应可视化原型系统的开发。50可视化算法研究主要包括两个部分：其一，在已有的均衡抽样算法的基础上，将可视化设备的相关硬件信息纳入考虑范围，对查询误差如何确定做出更加细化的分析，然后给出相应的查询误差转换算法。其二，在对传感器网络中的数据进行查询时，考虑一种累加式的抽样算法，即在已经抽取的样本信息的基础上，根据用户对查询结果的反应，重新在传感器网络中进行更加细化的抽样，使得查询结果能根据用户的反应做出一定的优化，增加用户对查询结55果的满意度。1相关工作1.1无线传感网中的抽样技术近年来，随着无线传感器网络的广泛应用和网络规模的不断增大，在进行一些查询时传感器网络中的通信量不断增加，导致传感器结点传输数据的能量消耗也不断增加。由于网络60中的单个传感器结点只有有限的能量，因此，如何合理地减少网络中的通信量以延长网络的寿命成为了十分关键的一个问题。文献[1]研究了基于抽样的top-k优化问题，根据历史感知数据，算法给过去一段时间有很大感知值的传感器结点赋予更大的抽样概率，但是不适用于非常规事件以及结点失效的情形。文献[2,3,4]研究了无线传感器网络中基于过滤器filter的top-k查询问题。文献[2]算法根65据历史数据给结点设定一个过滤区间，而且将查询看做伯努利试验过程，过滤区间可以保证查询结果正确的置信概率不小于指定的阈值，但是不能处理非正常值出现的情况。文献[3]算法对每一个传感器结点指定一个过滤区间，只有当传感器的感知值超过这个过滤区间时，新的感知值才会被更新到sink结点。这个方法可以明显减少网络中的通信量，但是每个传感器结点对应的过滤范围不好确定。文献[4]基于分簇的传感器网络中，用到剪枝的思想，70大小排序低于一个指定值时，可以被认为不会出现在最终的查询结果中。文献[5,6]研究了基于统计信息的网内数据聚集算法。文献[5]算法假设结点的感知值符合高斯分布模型，传输数据时并不需要传实际的感知数据，只需要传送基于统计信息的高斯分布模型的各项参数和对应的权重即可。然而，实际感知数据并不一定符合高斯分布，所以算法存在一定的局限性。文献[6]利用统计学方法定义了感知数据中的离群点，并在实际查询时去掉离群点，减少网75络通信量的同时也增加了结果的准确性。文献[7]研究了无线传感网网内控制的问题。在进-2- 中国科技论文在线http://www.paper.edu.cn行网内数据传递时，根据传感器网络的拓扑结构，考虑多播和网内聚集的折中以最小化网络通信量，将多路聚集问题归约为最小权值顶点覆盖问题，可以在多项式时间内解决。文献[8,9]设计了一种duplicate-insensitivesketch来处理近似聚集和sum和近似计数count的问题。文献[10]研究了无线传感器网络中的分层聚集问题。根据各个结点潜在的可能减少的通信量来80对结点进行分层，利用贪心的思想动态地更新误差界，以最小化网内聚集时产生的数据通信量。文献[11,12,13]研究了无线传感器网络中的等高线查询问题。文献[11]的主要想法是根据传感器网络中的一部分结点来构建等高线图（contourmap），算法对每个结点计算相对于周围邻居的感知值下降最快的方向（梯度方向），然后选出这些下降最快的结点，根据泰森多边形对网络进行划分，最后根据这些少量的结点构造出等高线图。文献[14]研究了静态传感85器网络中的基于均衡抽样的(ϵ,δ)-近似聚集算法。用户给定一个可以容忍的查询误差界ϵ、越界概率δ和聚集操作类型（聚集和sum、聚集平均值average或无重复计数值dis_count），算法根据用户的输入信息和sink结点中保存的传感器网络的静态信息，依据统计学方法计算出一个抽样的样本数m，使得在网络中均衡抽样m次时得到的近似聚集结果符合用户定义的误差界。文献[14]证明了基于均衡抽样的(ϵ,δ)-近似聚集算法可以满足用户的任意精度要90求，但是没有考虑在得到近似聚集结果之后如何将结果可视化地显示在用户可视化设备上的问题。1.2可视化技术可视化技术主要可以分为三类，包括基于几何的技术，面向像素的技术和基于层次的技术。基于几何的技术的主要思想是，将数据库中的数据以几何投影的方式来表现，例如，将95n维数据投影到二维平面上的n条平行直线上，直线与属性一一对应，直线上的位置表示属性值的大小。面向像素的技术的主要思想是，用一个带颜色的屏幕像素来表示一个数据项的属性值，每个属性对应一个屏幕窗口，各个屏幕窗口的相同坐标处的像素点的组合即表示一个完整的数据项。基于层次的技术的主要思想是，将数据库中具有层次结构的信息以层次化的方式来展现，例如，以递归的形式将n维数据空间划分为子空间，各个子空间也要以层次100化的方式来展现。随着大数据时代的来临，数据可视化技术的发展和完善将是未来的一个趋势。然而，可视化技术也面临着一些重大的问题，例如，对于一个庞大的数据库进行可视化的时候，选取全部的数据很可能造成数据传输量过大和传输延迟过长的问题，这也是今后数据可视化的一个主要的研究方向。105文献[15,16,17]研究了如何将大量数据可视化地展现给用户的问题。文献[15]针对于折线图的可视化问题。例如，用户需要查询过去一段时间内北京的PM2.5浓度变化情况，于是用户输入原始查询式，算法根据用户的可视化设备的参数信息（如宽、高等）重写关系代数表达式，新的查询式根据时间维度来对要采集的数据进行分组，算法从每一组数据集合中仅仅取出上下左右四个边界点，并在用户设备上将这些点以折线图的形式表现出来。文献[15]110证明了这样取数据点的正确性和有效性，原本需要从数据库传输到用户设备的大量数据可以-3- 中国科技论文在线http://www.paper.edu.cn被极大地精简，由此提高了系统的可用性并大大减少了通信量。但是，对于传感器网络而言，由于传感器结点的个数相当多，时间维度是不唯一的，文献[15]提出的方法并不适用于传感器网络中对多个传感器结点感知值的可视化，而且不能累加式地细化指定区域内的可视化结果。115文献[16]设计了基于线性简化算法（linesimplificationalgorithm）时间序列降维技术，可以很好的降低时间序列数据的维度，但是算法的时间复杂度为O(nlogn)，不如文献[15]中算法的O(n)，而且没有考虑根据设备参数将数据可视化地显示在用户设备上的问题。文献[17]针对于柱状图的可视化问题。例如，用户需要查询过去一段时间内国航、东航、南航和川航四家航空公司的平均晚点时间排名，要求查询结果可视化地显示在设备上而且排120名顺序必须准确。算法根据各个航空公司的晚点时间范围，检查时间范围有重叠的所有航空公司，并对有重叠的航空公司累加式地从数据库中采新的值，以更新晚点时间范围，最终使得各个航空公司的晚点时间范围互不相交，于是得到精确的排名顺序。文献[17]很好地保证了查询结果的顺序正确，但是没有考虑指定分组之间的聚集值的比例问题。可视化的目的是将大量的数值型数据转换为图表类型的数据，并在用户的可视化设备上125进行显示。直观地，当手机屏幕显示图表的时候，屏幕的宽、高和分辨率等硬件参数对图表的显示效果会有一定的影响，可能会引入除查询误差之外新的误差。于是，研究可视化设备的硬件信息（宽、高、分辨率）对查询误差的影响显得很有必要。2算法设计2.1引言130本节主要介绍了无线传感网中的两个可视化算法。其一，均衡抽样过程中的查询误差转换算法。由于传感器网络中的基于均衡抽样的(ϵ,δ)-近似聚集算法在文献[14]中已经得到了很好的研究，本章设计的算法对文献[14]中的均衡抽样算法进行了一些改进，将用户使用的可视化设备的相关硬件信息考虑进去，对查询误差进行转换，使得查询误差更加接近真实值。其二，更高精度的累加式抽样算法。在已经查询过的基础上，根据用户的反馈再次对传感器135数据库进行查询，在保留已查询数据的基础上，累加式地抽取更多信息展示给用户，提高用户对指定的感兴趣部分的满意度。2.2背景知识均衡抽样指的是在一个特定数据集合中进行有放回的随机抽取，且每个数据项被抽到的概率均相同。文献[14]中证明了基于均衡抽样的(ϵ,δ)-近似聚集算法给出的近似聚集值与精确140值之间的误差大于ϵ的概率不超过δ。算法的第一步需要确定抽样的样本容量m。第二步，在确定需要抽样的样本容量m之后，sink节点就需要在传感网内触发均衡抽样。第三步，m次均衡抽样完成之后，sink节点收集返回的m个感知值样本，计算感知值样本的平均值即为算法的输出。-4- 中国科技论文在线http://www.paper.edu.cn可视化的目的是将大量的数值型数据转换为图表类型的数据，并在用户的可视化设备上145进行显示。直观地，当手机屏幕显示图表的时候，屏幕的宽、高和分辨率等硬件参数对图表的显示效果会有一定的影响，可能会引入除查询误差之外新的误差。于是，研究可视化设备的硬件信息（宽、高、分辨率）对查询误差的影响显得很有必要。2.3误差转换算法误差转换的框架图如图1所示：150图1误差转换的框架图算法中涉及到的符号如表2所示：表2误差转换算法的相关符号符号描述e用户进行可视化查询时可以接受的总误差w可视化设备的屏幕宽（mm）h可视化设备的屏幕高（mm）res可视化设备的屏幕分辨率x一个像素点的长度r屏幕显示具体数值时造成的绝对误差a屏幕纵轴能显示的最小数值b屏幕纵轴能显示的最大数值v0当前查询的精确结果ϵ查询误差上界δ失败概率上界由于无线传感器网络中的(ϵ,δ)近似聚集算法研究已经比较成熟，即用户给定查询误差界155ϵ、越界概率δ和聚集操作类型（聚集和sum、聚集平均值average或无重复计数值dis_count），传感器网络就能给出相应的聚集结果。本部分做的主要工作是找到查询误差ϵ和可视化结果与精确结果之间的误差e之间的联系，即fe,w,h,res那么当用户给出可以接受的总误差e时，模型能根据上述关系得到用户可以接受的查询误差160ϵ，通过传感器网络查询后，将近似聚集结果返回给用户，并显示在用户的可视化设备上。-5- 中国科技论文在线http://www.paper.edu.cn针对这个问题的算法主要分为三步：第一，先根据设备参数（屏幕宽w，高h，分辨率res）得到设备在显示一个具体数值时产生的绝对误差r；第二，根据绝对误差r和用户给出的可接受的总的可视化误差e，得到对应的查询误差ϵ；第三，根据得到的查询误差ϵ在无线传感网中进行查询并将近似聚集结果返回并可视化的显示，此时的显示结果误差应不超过165总的可视化误差e。（1）现在的显示屏显示图像时，都是由一个一个像素点组合而成的。直观地，在数据可视化的过程中，sink结点返回一个近似聚集查询结果，反映在设备屏幕上时，误差值应该是像素点的长度所代表的数值的整数倍，而且误差至少为一个像素点（在纵轴上多显示一个像素点或少显示一个像素点）。我们将设备在显示一个具体数值时产生的误差定义为一个像170素点的长度，下面给出绝对误差r的推倒过程。hw屏幕分辨率=宽度分辨率*高度分辨率，即res*xx得xh*w/resw则r(ba)*x/h(ba)*h*res（2）假设某一次查询时精确结果为v0，传感器网络返回的近似聚集结果为v，根据175[4]中提出的算法，显然v1,1v0v0经过可视化之后，实际展示给用户的结果在区间v1r,v1r00根据用户可以接受的总的可视化误差为e，可知180v1r,v1rv1e,v1e0000即v1rv1e00re可得，即为对应的查询误差。v0[14]（3）得到查询误差之后，根据用户指定的越界概率，将(ϵ,δ)做为文献中算法的输入，将sink的返回值可视化地显示在用户设备上，此时的显示结果误差不超过用户可接185受的总的可视化误差。例如，用户想要根据无线传感网查询当前哈尔滨的气温，于是可以认为[a,b]=[-50,50](摄氏度)，假设用户的可视化设备宽w=100（毫米），高h=100（毫米），分辨率res=200*200，用户可以接受的总的可视化误差e=0.1，越界概率=0.1，当前气温精确值v020（摄氏度），则可以根据上述计算得到可视化的绝对偏差r=0.5（摄氏度），输入到传感器网络的-6- 中国科技论文在线http://www.paper.edu.cn190可接受查询误差=0.1-0.5/20=0.075。然后，(ϵ,δ)=（0.075,0.1）做为基于均衡抽样的(ϵ,δ)近似聚集算法的输入，得到的查询结果显示在用户可视化设备上。2.4累加式抽样算法在传感器网络规模比较大的情况下，传感器数据库的规模也相应的会比较大，如果想要将整个数据库的数据细节经过一次查询就完全展示给用户，会面临两个关键的问题：其一，195如此大规模的数据库如果全部通过网络传输，查询延迟将是相当高的；其二，如果考虑用户的实际需求，一般情况下，用户希望先看到整个数据库中数据的大致情况，然后再对某一特定的范围进行详细查看，而不是看到整个数据库的详细情况。于是，本文提出累加式抽样的算法。简而言之，累加式即在保留已抽取数据的基础之上，递增地抽取更多的数据，目的是对用户感兴趣的局部地区进行更加详细的刻画。累加式抽样200算法包括两个主要步骤：（1）根据用户的可视化设备和查询要求，对传感器数据库进行一次粗略的查询，目的是让用户对数据库的全局变化趋势和相关性有一个直观的了解。（2）用户获得对整个数据库的概要信息后，通过Android手机客户端做出反馈，即手动选择感兴趣的范围（时间范围或传感器编号范围等），然后手机在已经查询得到数据的基205础之上，根据用户选择的范围，重新对传感器数据库进行更加细致的查询，并将查询结果返回给用户手机并可视化的展示给用户。图3过去24小时哈尔滨的PM2.5浓度变化情况图45点至13点之间的详细信息例如，用户通过手机查询过去24小时哈尔滨的PM2.5浓度变化情况，原始可视化结果210如图3所示。如果用户想要进一步查看时间位于5-13之间的更详细的信息，在手动选取新的查询范围之后，进行累加式抽样，精度更高的可视化结果如图4所示。3实验测试3.1实验设置均衡抽样中的误差转换算法涉及到从网络中进行抽样和误差转换两个主要部分。本部分215采用一个模拟的具有5000个节点的传感器网络，传感器网络中节点的感知数据由算法随机生成，且取值范围为[10,40]。在下面的实验中，我们主要考虑查询误差ϵ和越界概率δ对抽样样本和平均值的聚集精度的影响，以及用户输入误差与实际查询误差之间的转换关系。-7- 中国科技论文在线http://www.paper.edu.cn3.2算法性能分析第一组实验考查基于均衡抽样的(ϵ,δ)近似聚集算法需要的抽样样本数和抽样率与查询220误差ϵ和越界概率δ的关系。在下面的实验中，越界概率δ的取值分别为0.05、0.1和0.2，对于每个不同的δ值，ϵ的值从0.1增加到0.4，然后根据每一组(ϵ,δ)的取值计算达到指定精度所需要的样本数m和抽样率。本实验仅仅考虑平均值这一种聚集操作。实验结果如图5-(a)和图5-(b)所示。根据图5-(a)和图5-(b)，对于同一越界概率δ而言，随着查询误差ϵ的增大，所需的抽样样本数明显减少。例如，当δ=0.1时，ϵ取0.1时样本225数m为1152，抽样率为23.0%；ϵ取0.2时样本数m仅为288，抽样率为5.8%。对于不同的越界概率δ而言，当查询误差ϵ取值相同时，δ越大，所需的抽样样本数越少。例如，当ϵ=0.2时，δ取0.05时样本数m为1152，抽样率为23.0%；δ取0.1时样本数m为811，抽样率为16.2%；δ取0.2时样本数m仅为492,抽样率为9.9%。由此可见，对于查询误差精度要求不太高的查询过程而言，所需要的样本数相当少，即可达到用户的查询精度要求。230(a)抽样样本数m与ϵ,δ的关系(b)抽样率与ϵ,δ的关系(c)平均值的精度与ϵ,δ的关系(d)实际查询误差ϵ与用户输入误差e的关系图5实验结果235第二组实验考查平均值聚集值的相对误差与查询误差ϵ和越界概率δ的关系。在下面的实验中，越界概率δ的取值分别为0.05、0.1和0.2，对于每个不同的δ值，ϵ的值从0.1增加到0.4，然后根据每一组(ϵ,δ)的取值计算近似聚集值与精确值之间的相对误差。实验结果如图5-(c)所示。根据图5-(c)，随着查询误差ϵ的增加，近似聚集值的相对误差整体趋势是增加的，但是由于均衡抽样的随机性，相对误差的变化趋势并不是绝对单调的。240第三组实验考查实际查询误差ϵ与用户输入误差e之间的关系。根据前面的算法分析部-8- 中国科技论文在线http://www.paper.edu.cn分，当用户的可视化设备确定时，实际上ϵ与e之间的关系为线性关系。本实验中用户设备的屏幕宽50mm，高88.9mm，分辨率20000，可视化过程中的显示范围为[0,100]。在实验中e的取值从0.1增加到0.4，步长为0.02，根据每个e值计算实际查询误差ϵ的值。实验结果如图5-(d)所示。实验结果中，ϵ与e之间的关系为线性关系，ϵ随e的增大而增大，且实际245查询误差ϵ要比用户输入误差e小。4原型系统设计4.1系统框架整个系统的框架结构如图6所示：250图6系统框架图本节详细介绍了针对本文提出的两个可视化算法而实现的原型系统。在可视化设备多样化的今天，本文选择基于开源Android系统的智能手机作为原型系统的查询工具，并在Android平台上使用Java开发了一个可视化手机客户端，通过无线方式与服务器进行交互，并能将服务器返回的查询数据以折线图或直方图的形式展示给用户。255由于静态传感器网络的每个传感器节点均可以将过去一段时间感知到的数据暂时存储起来，于是可以将整个传感网看做一个数据库，并可以通过数据库管理系统来对其中的数据进行查询等操作。本系统在Apache+Mysql+PHP的集成平台xampp上开发，采用服务器端的Mysql数据库来模拟真实的传感器数据库，并使用PHP脚本开发语言来设计服务器端的脚本程序。260用户在Android手机客户端上输入查询参数（包括查询误差和越界概率），客户端将查询参数传送给服务器端，服务器端根据收到的查询参数，使用标准SQL语言来对数据库进行查询，并将查询结果进行处理之后以Json格式传回Android手机客户端，客户端进行解码之后，将一系列数值型的查询结果以折线图或直方图的形式展示出来。另外，用户在得到可视化的结果之后，可以通过点触屏幕的相应位置来选择感兴趣的范围，并通过客户端发出265第二次查询；服务器端将返回指定范围内更加详细的数据，并由Android手机客户端进行第二次可视化操作，此时的可视化结果范围更小，但显示的信息更加详细。4.2传感器数据库本文使用Mysql数据库来模拟真实的传感器数据库。在传感器数据库中，一条元组由三个属性来确定，即数据采集时间time、传感器节点标号id和感知值value。在静态传感器网-9- 中国科技论文在线http://www.paper.edu.cn270络中，假设每个传感器节点的标号各不相同且从1依次递增。对于某个特定的传感器节点而言，其数据采集时间time也各不相同且从1依次递增。每一条元组（time，id，value）表示在时间time标号为id的传感器节点采集到了数据value。数据库中关系表的结构如表7所示：表7关系表的结构序号字段名别称类型备注1time数据采集时间Int联合主键2id节点标号Int联合主键3value感知值Varchar(10)非空4.3系统结构275Android手机端可视化程序的activity跳转过程如图8所示：图8activity的跳转过程4.4系统展示图9(a)-(h)展示可视化原型系统的运行情况。图(a)为系统主界面，用户按照提示在文本280输入框中输入符合要求的参数（如图(b)），点击“折线图”按钮时，将数据以折线图的形式展示在手机屏幕上（如图(c)）。在得到折线图之后，若用户想要查看某个范围内更加细致的信息，则可以通过点击横坐标对应的条柱来选取范围的起始点和结束点（如图(d-f)），然而系统根据用户选择的范围重新进行查询，并将结果以折线图的形式展示在手机屏幕上（如图(g)）。如果用户需要得到直方图的表现形式，则可以回到主界面，重新输入查询参数并点285击“直方图”按钮，数据将以直方图的形式展示在手机上（如图(h)）。(a)主界面(b)输入查询参数-10- 中国科技论文在线http://www.paper.edu.cn(c)点击“折线图”按钮(d)点击折线图中横坐标“9”对应的矩形片290(e)点击折线图中横坐标“15”对应的矩形片(f)点击屏幕任意地方(g)详细显示的9到15之间的详细信息(h)回到主界面，输入查询参数后，点击“直方图”图9系统展示过程2955结论本文针对无线传感网的特性和用户可视化的查询需求，对无线传感网中的可视化算法进行了研究。本文在基于均衡抽样的(ϵ,δ)近似聚集算法的基础之上，研究了查询误差的转换算法。基于均衡抽样的(ϵ,δ)近似聚集算法可以在用户给定任意精度查询参数的情况下，通过抽样方法给出满足用户要求的近似聚集结果。然而，这个经典的近似算法没有考虑到用户可视300化设备对查询误差的影响。首先，本文对均衡抽样过程中手机硬件信息对实际查询误差造成的影响进行了分析；其次，在考虑可视化设备的硬件信息（显示屏幕的宽、高、分辨率）的基础上，我们用数学的方法证明了用户输入误差与实际查询误差之间的转换关系，并得到了相应的转换公式。最后，我们通过模拟实验对本部分提出的算法进行了验证。本文在可视化过程中，研究了更高精度的累加式抽样算法。为了更有效地处理用户的更305高精度查询请求，本文设计了一种累加式的抽样算法。首先，用户通过查询得到整个数据库的概况，选择自己感兴趣的范围；其次，根据用户选择的范围，在保留已得到数据的基础上，再次对传感网进行查询，查询结果展示更小范围内的详细信息。最后，我们针对本算法实现了一个基于Android平台的原型系统，通过Mysql数据库来模拟真实的无线传感网数据，构-11- 中国科技论文在线http://www.paper.edu.cn建了服务器端的脚本程序，并通过Android手机端的客户端程序来进行可视化的查询。310[参考文献](References)[1]A.S.Silberstein,R.Braynard,C.Ellis,K.Munagala,andJ.Yang.Asampling-basedapproachtooptimizingtop-kqueriesinsensornetworks,"inthe22ndInternationalConferenceonDataEngineering(ICDE)[C].2006,pp.68-68.[2]J.Cheng,H.Jiang,J.Liu,W.Liu,andC.Wang.Onefficientprocessingofcontinuoushistoricaltop-queriesin315sensornetworks[J].IEEETransactionsonVehicularTechnology,2011,60(5):2363-2367.[3]M.Wu,J.Xu,X.Tang,andW.-C.Lee.Top-kmonitoringinwirelesssensornetworks[J].IEEETransactionsonKnowledgeandDataEngineering,2007,19(7):962-976.[4]M.Ye,X.Liu,W.-C.Lee,andD.L.Lee.Probabilistictop-kqueryprocessingindistributedsensornetworks,"inthe26thInternationalConferenceonDataEngineering(ICDE)[C].2010,pp.585-588.320[5]H.JiangandS.Jin.Scalableandrobustaggregationtechniquesforextractingstatisticalinformationinsensornetworks.Inthe26thIEEEInternationalConferenceonDistributedComputingSystems(ICDCS)[C].IEEE,2006,pp.69-69.[6]A.Deligiannakis,Y.Kotidis,V.Vassalos,andA.Delis.Anotheroutlierbitesthedust:Computingmeaningfulaggregatesinsensornetworks.Inthe25thInternationalConferenceonDataEngineering(ICDE)[C].2009,pp.325988-999.[7]A.SilbersteinandJ.Yang.Multipleaggregationforin-networkcontrolofsensors.Inthe23thInternationalConferenceonDataEngineering(ICDE)[C].2007,pp1-14.[8]J.Considine,M.Hadjieleftheriou,F.Li,J.Byers,andG.Kollios.Robustapproximateaggregationinsensordatamanagementsystems[J].ACMTransactionsonDatabaseSystems(TODS),2009,34(1):6.330[9]J.Considine,F.Li,G.Kollios,andJ.Byers.Approximateaggregationtechniquesforsensordatabases.Inthe20thInternationalConferenceonDataEngineering(ICDE)[C].2004,pp.449-460.[10]A.Deligiannakis,Y.Kotidis,andN.Roussopoulos.Hierarchicalin-networkdataaggregationwithqualityguarantees.InAdvancesinDatabaseTechnology-EDBT[C].2004,pp.658-675.[11]M.LiandY.Liu.Iso-map:Energy-efficientcontourmappinginwirelesssensornetworks[J].IEEE335TransactionsonKnowledgeandDataEngineering,vol.22,no.5,2010,pp.699-710.[12]A.Silberstein,R.Braynard,andJ.Yang.Energy-efficientcontinuousisolinequeriesinsensornetworks.Inthe22ndInternationalConferenceonDataEngineering(ICDE)[C].2006,pp.145-145.[13]W.Xue,Q.Luo,L.Chen,andY.Liu.Contourmapmatchingforeventdetectioninsensornetworks.Inthe2006ACMinternationalconferenceonManagementofdata(SIGMOD)[C].2006,pp.145-156.340[14]程思瑶，无线传感器网络中分布式计算方法的研究[D].哈尔滨：哈尔滨工业大学,2012.[15]U.Jugel,Z.Jerzak,G.Hackenbroich,andV.Markl.M4:Avisualization-orientedtimeseriesdataaggregation[J].PVLDB,2014,7(10):797-808.[16]T.Fu.Areviewontimeseriesdatamining[J].EAAIJournal,2011,24(1):164-181.[17]A.Kim,E.Blais,S.Madden,andR.Rubinfeld.Rapidsamplingforvisualizationswithorderingguarantees[J].345PVLDB,2015,8(5):521-532.-12-'