WSN中基于几何学的分布式轮廓查询方法研究-毕业论文

硕 士 学 位 论 文中文题目： WSN中基于几何学的分布式轮廓查询方法研究 Research on the Geometry-Based Distributed Skyline 英文题目： Query Method in WSN 论文作者： 指导教师： 专 业： 计算机软件与理论 完成时间： 摘 要摘 要近年来，环境污染、空气质量问题得到日益关注，结合实际情况，实现无线传感器网络的价值越来越得到人们的关注。基于无线传感器网络的轮廓查询策略已经得到广泛应用，尤其在环境检测等领域的查询，而这些应用领域多数涉及到空间距离问题。由于空间位置的多维性，给一般的轮廓查询策略在属性计算方面带来巨大的计算代价。为提高传感器能量的高效利用，对基于空间距离上的轮廓查询需要新的解决策略，为此本文提出一种基于几何学的分布式轮廓查询方法（GDSky）。本文首先采用几何学的方法将整个查询区域划分，以便在各个子区域之间可以进行区域间支配关系的判定，本文采用基于凸包顶点的轮廓区域削减方法，可以快速查找到与特定查询区域相关的空间轮廓数据，减少了节点间比较次数。提出了基于三角剖分法的区域划分策略，该方法是将用户指定的查询区域划分为若干个子区域，使得查询在各个子区域间可以进行分布式进行。设计了一种子区域内分簇的策略，对一个子区域内的数据分簇，以进行轮廓的并行查询，节省时间。为了遍历到所有相邻的传感器检测地点，削减掉在空间距离上被支配的节点，本文提出了基于数据节点树的分布式查询策略，并利用非空间的轮廓查询方法，对已获得空间轮廓的非空间属性进行一般轮廓查询，与此同时，对剩余的未找到的空间轮廓数据进行空间轮廓查询，从而实现并行执行。最后，本文还提出了子区域间削减策略，可以削减掉被支配的一个子区域内所有节点，以及子区域内部削减策略，可以削减掉一个子区域内某些被支配的节点，减少网络中数据的传输消耗。大量仿真实验的结果表明，本文提出的GDSky方法可以较快速的查询到距离查询地点较近且污染力较大的地点，可以高效减少数据间支配比较次数，降低传感器节点的能量消耗，提高查询效率。关键词：无线传感器网络，环境监测，分布式轮廓查询，凸包，削减IAbstractABSTRACTIn recent years, environmental pollution and the quality problem of the air get the increasing attention. According to the actual situation, to realize the value of the wireless sensor network gets more and more concern. The skyline query strategies in wireless sensor networks have been widely used in the field of environmental detection, and these areas mostly are related to the spatial distance problem. Since the multi-dimensional of the spatial position, it brings the enormous computational cost for the general skyline query strategy with the aspect of the attribute calculation. In order to improve the efficient use of sensor energy, it needs a new query strategy to solve the skyline query on the spatial distance. This paper proposes a method of the geometry-based distributed skyline query (GDSky). The specific work is as follows.This paper uses the method of the geometry-based region partition to divide the whole query region into several sub-regions, so that it can determine the dominance relationship between sub-regions. This paper proposes a method of cut of the skyline area based on the convex hull vertices, which can quickly find the spatial skyline data with respect of a specific query area, and reduce the comparison times between nodes. This paper adopts the regional partition based on the triangulation method which divides the query region into several sub-regions. So it can carry out a distributed query in each sub-region. The paper also designs the clustering strategy in one sub-region, which can cluster on the data within a sub-region in order to query the skyline in parallel and save time. Besides, in order to traverse all the neighbor sensor detective locations, and cut the nodes which are dominated on the spatial distance. the paper also proposes the distributed query strategy based on the data node tree. To carry out the general skyline query on the non-spatial properties of the obtained spatial skyline，the paper also puts forward the non-spatial skyline query method. At the same time, the strategy conducts the spatial skyline query on the remaining spatial skyline data so as to realize the parallel execution. This paper presents the cut strategy among the sub-regional, which can cut all dominated nodes in one sub-region. And IIIalso puts forward the cut strategy in a sub-region, which can cut some dominated nodes in a sub-region and reduce the data communication in the network.Simulation results show that the method GDSky proposed in this paper can quickly find the places which are near to the query locations and have the larger pollution energy. The method also can efficiently reduce the times of comparison between data, improve the query efficiency, and reduce the energy consumption of sensor node.Key Words: wireless sensor network, environmental monitoring, distributed skyline query, convex hull, cutting node IV目 录目 录第1章 引 言11.1 研究背景11.1.1 环境质量监测概述11.1.2 环境监测特点及需求21.2 研究现状51.2.1 无线传感器网络在环境监测中的应用51.2.2 无线传感器网络的查询特点61.3 问题的提出8第2章 轮廓查询102.1 轮廓查询112.2 典型的轮廓查询方法122.2.1 基于非空间的轮廓查询方法122.2.2 基于空间的轮廓查询方法132.3 本章小节15第3章 基于几何学的空间轮廓查询173.1 基于传感器部署的区域划分173.1.1 Voronoi图183.1.2 Delaunay图183.1.3 区域划分策略193.2 基于凸包顶点的轮廓区域削减203.2.1 凸包213.2.2 空间轮廓区域的削减方法233.3 空间轮廓区域的削减方法过程283.4 本章小节29第4章 分布式轮廓查询304.1 区域划分304.1.1 基于三角剖分法的区域划分304.1.2 子区域内分簇324.2 分布式区域查询344.2.1 子区域内并行查询344.2.2 区域间查询结果合并384.3 基于几何学的分布式轮廓查询方法404.4 本章小节41第5章 实验与分析435.1 实验环境配置435.1.1 实验环境及方案435.1.2 实验数据集435.2 实验结果与分析445.3 本章小结49第6章 总结与展望506.1 总结506.2 展望51致 谢52参考文献53攻读学位期间发表的学术论文及参加科研情况56VII图表目录图 表 目 录图目录图1-1 某城市内居民区及其附近概况图4图2-1 Skyline选择宾馆例子11图2-2 节点间支配关系14图3-1 查询区域示意图17图3-2 Voronoi图18图3-3 Delaunay图 19图3-4 基于Voronoi图的区域划分19图3-5 查询区域划分后抽象图20图3-6 凸包示意图21图3-7 基于凸包顶点的轮廓区域的确定24图3-8 轮廓区域削减结果25图3-9 传感器节点中地理信息27图3-10 单调函数排序示意图27图3-11 空间轮廓区域的削减过程28图4-1 一个简单多边形的一种三角剖分31图4-2 查询区域三角剖分示意图32图4-3 分簇结构33图4-4 子区域内分簇33图4-5 数据节点树T 35图4-6 子区域内轮廓数据回收37图4-7 各子区域内轮廓查询结果37图4-8 子区域的削减39图4-9 轮廓查询最终结果40图5-1 数据节点数与支配比较次数44图5-2 查询节点数与支配比较次数45图5-3 传感器能量消耗 46图5-4 查询节点数与响应时间47图5-5 执行效率百分比48图5-6 数据节点数与合并时间48表目录表4-1 数据元组的格式38表4-2 簇头节点S1的数据表40表4-3 簇头节点S1的数据表40表5-1 实验参数43VIII第1章 引 言第1章 引 言1.1 研究背景随着全球各个国家对环境保护问题的日益关注，人类有必要将智慧投入到环境保护问题上，当“雾霾”一词走进人类的生活当中，人类更加意识到科学发展才是硬道理，有些地方的发展是以环境质量为代价来获得经济的快速发展，这样的发展方式并非是科学有效的。我国已经出台了多项方针政策来应对环保问题，而更加科学、创新的新思想新技术是解决实际问题的关键所在。1.1.1 环境质量监测概述近些年越来越多的环境污染问题受到关注，如空气质量1，水资源污染，电力设备辐射，噪声污染等。就空气质量检测情况来说，从上世纪开始，欧美等发达国家和地区的研究者就对空气质量监测网络进行了大量研究，他们对于的设计标准就是快速便捷、灵活有效、针对性强。为了满足城镇化发展的需求，我国也出台了大量的方针政策来完善环境空气质量监测方法，但是，仍然缺乏满足特殊条件的监控条件更为细致的创新方法，对于监测网络设计方面的研究有待发展，尤其是针对特殊人群要求的监测网络的设计，更应该投入更多的科学研究。1) 国外情况在美国，按照行政级别分为国家级的监测站以及各州及地方监测站，通常对各种污染物的监测是分开的2。这种监测方法存在一些特点，首先是监测的范围较广，环境监控中心通常是将监测站设置在大型城市及周边地区，从而来监测该地区的空气质量水平；其次是监测站的数量少，由于美国人口稀少，通常将监测站设置于大城市周边，这是因为大城市通常是污染较为严重的地区，通过这种方法就可以了解到整个州的空气污染情况。再次，为了保证污染物的能够得到充分扩散，监测点通常需要安放在距离污染源有一定距离的位置。在欧洲地区，通常将监测站设置在大城市的附近，监测的是整个地区的平均空气质量水平，根据具体的实际情况，采用不同的设计原则来规划监测站的具体地理位置，在欧盟地区，不同国家采用适合自己的设计原则来设计监测系统，对于不同的污染物的监测方法中含有不同的监测原则。2) 国内情况在我国，目前人们得到的空气质量信息是通过在每个城市中设置若干个监控子站，且这些子站必须设置在空旷、不被人为干扰的地方，要避免安放在在距离污染源较近的地方。这种监测方法得到的结果是某城市的平均空气质量水平。这种方法的具体过程通常是在一个城市设立若干个监测子站，子站内有自动监测的仪器对数据的进行连续的自动监测，监测员定期的将监测结果取回进行科学分析，最终得到相关的空气质量监测数据。但是在这种传统的监测方法中，按照国家环保部环境空气质量监测规范的相关规定，环境监测子站坚决不可以随便安置，要按照一定的标准进行安放位置的选取，通过遵循这样的规定获得的监测的数据才有代表性和说服力。规定中有具体的空气质量评价点位的安放要求，要求点位的周围不可以存在污染源，而且监控点位必须设置在能代表全市环境空气污染水平的位置。以上传统策略都无法监测到距离人群密集处周边的环境污染概况，当查询某任意指定范围时，传统策略在灵活性方面受到一定限制。因此，将轮廓查询与无线传感器网络（WSN）技术相结合应用在环境质量监测中是非常有效的方法3,4,5。1.1.2 环境监测特点及需求2015年政府工作报告中李克强总理对环保问题做出了重大部署，对于环保问题的提议，政府仍然投入了大量的关注，在政府工作报告中还明确指出要打好节能减排和环境治理攻坚战，环境污染是百姓的忧患，是百姓心中时刻挂念的大事。报告中提到对二氧化硫的排放程度要降低3%左右，对氮氧化物的排放程度要降低5%左右，要加快实行大气污染防治行动计划，提倡采用绿色环保节约型能源行动计划的落实，对机动车尾气要加大处理力度，实行区域的联合防范与联合控制管理等。加强环境监测也是民之所向，环境治理已成为当前的是刻不容缓的首要问题。人口密集的市中心监测站点能否加密，主干道和工地旁能否增设监测点6，未来能否设置路边监测站来监测机动车尾气，在全社会集思广益，设计一个效率高、代表性好、目的性强的空气质量监测网络是人们更为关心的身边的热点问题，随之而来的，设计出这样一个灵活高效的空气质量监测系统也是长期以来科研工作的难点。我们迫切需要一种网络监测系统来切实解决人们身边的、老百姓更为关注的环境污染监测问题。而这样的系统应该具有以下特点：1) 空气质量监测站应设在市民生活区周围，但又要避免因过多的人为活动造成监测数据出现偏差；2) 具有开放式网络结构及网络的自组织特性，节点可以随时加入，失效节点可以随时删除，同时不对原有系统造成任何影响；3) 具有实时的监测功能，用户在任意时间都可以查看信息；4) 可以针对个别感兴趣的属性进行查询，系统返回的结果均为有“意义”的数据信息。针对以上需求，由于无线传感器网络的监测系统具有较好的扩展性，而且在灵活性上也能满足不同用户的需求。我们快速联想到将无线传感器网络的查询与环境监测问题想结合来解决当前人们关注的问题。就目前被广泛关注的空气质量问题，现有的查询策略是在城市内设置若干子站，子站必须设置在空旷、不能被人为干扰的地区，而不能选择靠近污染源的位置，反应的仅是整个城市的平均空气质量水平。但是，居民实际关心的往往是人群密集地区的空气质量问题。气象局对空气质量检测方法是通过在城市中设置若干监测站，覆盖范围较为广泛。不同于气象局检测过程，本文所提出的基于传感器网络查询方法覆盖范围更加灵活，节点具有无线通信能力，使节点之间协同监控。本文提出的策略可以查询出对居民区附近影响力较大的地点。图1-1为某城市局部地区区域图，上述的空气质量检测例子中，居民区相当于查询点集Q，居民区周围的多条公路、工厂等相当于数据点集P。图1-1 某城市内居民区及其附近概况图 如图所示，在这些有污染潜力的街道工厂周围安装适当数量的传感器用来检测数据，此时用户并不偏好于某一维属性，而是根据多个属性值来综合判断。查询出距离居民区更近的并且空气污染指数大的传感器节点就是我们要找的轮廓数据。因此，本文首先提出基于凸包顶点的轮廓区域削减策略查找距离查询点较近的数据节点的集合，通过该策略可以迅速查询到上述问题中指定查询范围内距离所有人群密集地都近的空间位置，也就是对人群影响较大的位置。随后，本文进一步提出基于数据节点树的分布式轮廓查询策略，针对非空间属性（如空气质量检测实例中的CO2, SO2, PM2.5值等）进行查询，从而获得污染较为严重的地点。综上，通过本文提出的基于几何学分布式空间轮廓查询策略最终可以查询到距离人群密集处较近的污染源污染概况。这样的监测系统同样可以应用到城市局部区域雾霾天气监控当中，由于城市内受雾霾天气影响的区域较大较广泛，用户想查询出距离某些居民区、医院、娱乐场所等人群密集地点附近情况，从而快速及时的采取治理措施或作出相应的雾霾天气警告以指示居民出行情况。霾的主要形成因素有三点：一是水平方向风速较小，二是垂直方向上出现逆温，三是大气污染物浓度增加。所以，传感器检测的属性可以包括空间属性和非空间属性，空间属性通常指到查询点的距离，对于非空间属性，如空气的湿度、温度、风速、气压、空气中的颗粒密度等。这里，查询出距离查询点更近的并且空气湿度更高、颗粒密度更大、风速更小的传感器节点就是我们要找的轮廓数据。我们在所要查询的城市区域的中心处设置一个雾霾情况监控中心，首先进行基于空间的轮廓查询,找到空间距离上离查询点较近的空间轮廓节点集合Sspatial，再利用一般的轮廓查询算法对上述轮廓数据的非空间属性上的进行支配关系的判断。这样可以大量减少数据之间的比较次数，降低传感器能量的消耗。1.2 研究现状目前，无线传感器网络轮廓查询策略多数是取数据的全部属性进行支配关系的判定，并没有将基于空间属性的轮廓查询进行单独考虑。查询过程中，尽管采用分布式查询策略，但效率低，传输代价大，能量消耗大。因此，本文提出几何学的分布式轮廓查询策略着重于数据的空间属性，采用树型存储结构分布式查询，结合传感器网络，可以在实际背景中进行有效的查询。1.2.1 无线传感器网络在环境监测中的应用随着环境问题日益加剧,人们对自己身边的环境状况提出了更高的要求,与此同时,无线传感网络技术也在快速发展，在环境监测中无线传感网络正发挥着灵活且关键性的作用，这种结合也收到了一定成效，并且利用传感器网络的监测应用越来越广泛，这也更加肯定了无线传感器网络应用前景的远大，无线传感器网络中较为成熟的应用实例如下：1) 传感器网络监测森林火灾，利用传感器节点感知火灾附近的温度，湿度，烟浓度，大火将引起传感器附近温度高、湿度低及烟浓度高。消防员可以提前下发一个轮廓查询来找出这些危险区；2) Citysee，一个实时的CO2检测系统，应用在中国无锡，一个拥有1096个传播节点及100个传感器节点的大规模无线传感器网络中7；3) 研究不同鸟种行为，由无线传感器网络感知的数据反映鸟类的喜好，如温度、湿度等，从而判定鸟类常出现的地点；4) 电力设施冰灾实时监测与预警系统，利用无线传感器网络的查询功能，可以快速查找到用户需求的易结冰点位，以便及时有效的采取应急措施，有效降低冰灾造成的财产损失8。1.2.2 无线传感器网络的查询特点1) 无线传感器网络由部署在监测区域内微型传感器节点就可以组成一个无线传感器网络，这样的传感器节点的特点是数量大，价格低以满足大范围灵活查询部署的需求，由这些传感器节点通过无线通信方式会自发形成一个自组织的网络系统，这个网络可以相互协作地感知数据、采集数据和处理网络覆盖区域中被感知对象的信息，并将查询结果发送给观察者。2) 无线传感器网络特点 大规模性为了获得大范围的监控信息且使获得的信息足够精确，通常在监测区域内部部署大量的传感器节点，通过传感器对各自信息的感知采集，整个网络可以分布式处理大量的采集信息，降低对单个传感器节点的精度限制，可以有效提高监测的准确度；这样的部署方式，在网路中会存在大量的冗余节点，可以有效减少未检测地区的存在，而且这些节点可以提高系统的容错性。 自组织性现有的传感器网络应用中，通常将传感器节点大面积的分散部署到某个查询区域内，而传感器节点之间的相邻位置关系预先是不固定的，由于传感器之间需要相互通信，需要知道与之相邻的各传感器所在的位置关系，这就要求传感器节点需要具有自组织能力，这种能力可以使节点自发的设置属性并控制信息，从而形成一个相互联络的网络系统。而在通信过程中，部分传感器节点可能会失效，这是由于能量耗尽或环境因素造成的，在这种情况下，其他的传感器节点就会自动的补充进来来接替这些失效节点继续工作，因此，我们说传感器网络具有自组织能力，它可以根据网络需求动态的增加或减少网络中的传感器节点数目。 以数据为中心通过采用节点编号来辨别不同的传感器节点，根据传感器网络通信协议设计方案可以设置节点编号在整个网络中的是否需要设为唯一。但是，节点编号与节点位置没有必然联系，同时，由传感器自组织组成的网络与各个节点编号之间的关系是完全随机的、不确定的。查询过程中，用户将所关心的事件即查询要求直接下发给网络，网络在获得查询结果后将其返回给用户。网络中都是以数据作为传输信息，传输的并非仅是节点的编号，由于这种网络是以数据本身作为查询或传输的信息，所以它是一个以数据为中心的网络。 协作执行任务传感器节点之间都是协作式的完成任务，每当用户下发一个查询时，首先各节点协作式采集各类信息，将信息存储到本地，然后对采集到的信息作处理计算等任务，在处理过程中会有信息的传输，最后将查询结果传输返回给用户。通过这样的方式，传感器的节点可以相互协调的对查询对象的进行感知，最终查询到到精确完整的数据信息。同时，在这种方式下，传感器节点之间也可以进行远距离的数据传输，大大加强了网络的通信能力。3) 无线传感器网络中的数据查询目前对传感器网络的数据查询方式的研究主要以分布式查询为主，集中式的监测查询只需在系统的中心服务器上进行，但是，一旦中心服务器瘫痪，便会造成系统性能的瓶颈，分布式查询与集中式查询的最大区别就是，分布式查询并非在一个服务器上集中进行，而是将查询下发在传感器网络内部的各个节点，由传感器节点组成的网络系统针对用户下发的感兴趣的查询进行相应的处理，从而快速准确的获得查询结果。因此分布式查询的特点在于，用户输入在不同的查询要求，系统会返回不同的查询结果信息，而且查询结果是与查询条件相关的信息。通过以上分析我们可以了解到，传统的环境监测方法已经无法满足与人们实际生活息息相关，紧密相连的百姓生活周边的环境监测问题的迫切需求，我们急需一个切实解决百姓周边环境污染问题的监测系统，这个系统可以实时的，准确便捷的返回用户的查询需求，可以有效的支持网络中节点的扩大与收缩，具有规模大，自组织，可协调的网络特点，而无线传感器网络中对数据的查询恰好满足以上特点，因此，将环境监测与传感器网络结合，采用传感器网络中的数据查询方式，可以有效解决百姓身边的实际问题。1.3 问题的提出本文针对传统环境监测方法的不足，结合无线传感器网络数据查询特点，提出用无线传感器网络查询方法解决环境监测问题，并对基于特定查询区域的空间属性特点进行深入研究，针对传感器网络数据的多维性及复杂性问题，本文提出一种基于几何学的分布式空间轮廓查询方法。工作内容如下：1) 提出了无线传感器网络中基于几何学的分布式轮廓查询方法，该查询方法将无线传感器网络的查询分为四个部分：轮廓区域削减，区域划分，区域内并行查询，区域间查询结果合并。2) 轮廓区域削减。本文提出了基于凸包顶点的轮廓区域削减方法，可以快速查找到与特定查询区域相关的空间轮廓数据，减少了节点间比较次数。3) 区域划分。本文提出了基于三角剖分法的区域划分方法，利用该方法可以将整个查询区域划分为若干查询子区域，以便查询在各个子区域间可以分布式的进行。提出子区域内分簇的策略，对一个子区域内的数据分簇，以进行轮廓的并行查询，节省时间。4) 区域内并行查询。本文提出了基于数据节点树的分布式查询策略，可以遍历到所有相邻的传感器检测地点，削减掉在空间距离上被支配的节点。又提出了非空间的轮廓查询方法，对已获得空间轮廓的非空间属性进行一般轮廓查询，与此同时，对剩余的未找到的空间轮廓数据进行空间轮廓查询，从而实现并行执行。5) 区域间查询结果合并。本文提出了子区域间削减策略，可以削减掉被支配的一个子区域内所有节点，又提出了子区域内部削减策略，可以削减掉一个子区域内某些被支配的节点。本文共分为六章，各部分内容如下：第1章 引言，提出了本文的研究背景及意义，提出了环境质量监测的重大意义以及国内外环境质量监测的现状，分析了传统环境监测的数据查询与特点，进一步分析了原有查询方法的不足，并阐述了环境监测实际问题中的迫切需求。还提出了传感器网络成熟的应用，阐明了无线传感器网络中的查询特点。通过分析环境质量检测的实际情况，证明了将环境监测问题与无线传感器网络相结合现实意义的重要性。在本章的最后，提出了本文要解决的问题以及组织结构。第2章 轮廓查询，介绍了现有轮廓查询的意义与应用，本文将无线传感器网络中轮廓查询方法划分为基于非空间的轮廓查询方法和基于空间的轮廓查询方法，并对这两类方法进行了深入研究，提出了适合于环境质量监测系统中的轮廓查询方法。本章还介绍了空间支配关系及空间轮廓的相关定义。第3章 基于几何学的空间轮廓查询，在了解Voronoi图及Delaunay图等几何学基础上，确定查询节点构成的最大凸多边形凸包，提出了基于凸包顶点的轮廓区域削减机制，介绍了空间轮廓区域具体削减方法。第4章 分布式轮廓查询，提出了采用基于三角剖分法及子区域内分簇的区域的划分方法，研究了分布式区域查询机制，提出了在基于数据节点树的空间轮廓查询，以及非空间轮廓查询的子区域内并行查询策略，还提出了区域间查询结果的合并方法，对查询数据的回收进行高效的削减，提出了有效的基于几何学的分布式轮廓查询机制。第5章 实验及性能分析，将现有的轮廓查询同本文提出的轮廓查询进行比较，证明本文提出的轮廓查询策略具有效率高，能耗低等优点，还证明了本文提出方法在查询结果上的具有完整性与准确性。第6章 结论与展望，对本文研究内容提出了详细的的总结，提出了本文的主要研究工作，还提出了今后进一步的研究工作的展望。56第2章 轮廓查询第2章 轮廓查询Skyline 查询是一个典型的多目标优化的问题，研究人员对它的研究开始时间很早，并且采用不同的Skyline查询方法进行深入而广泛的研究，Skyline的中文解释称为“轮廓”，对轮廓数据的查询处理则称之为“轮廓查询”，它是从众多查询数据中找出用户感兴趣的值，以供具体应用条件下提供相关处理策略及解决方案之用。首先介绍“支配”的定义。就目前被广泛关注的环境监测问题来说，CitySee是当前现有的基于无线传感器网络的城市CO2监测系统，该系统位于无锡市内， 一个拥有1096个传播节点及100个传感器节点的大规模无线传感器网络，设计者利用传感器来监测CO2的浓度，Concentration（%）来表示CO2在空气中的浓度。假设位于两个监测地点C1和C2的传感器监测的浓度分别是C1. concentration=6.9%，C2. concentration=7.9%，但是，不同的用户需求带来不同的支配含义，就环境污染问题来讲，用户下发的查询是想获得CO2污染浓度较大的节点，这时，我们通过比较得出C2的浓度值大于C1的浓度值，因此，用户想要获得的查询结果是C2这样的节点，则此时我们称C2支配C1。相反，若用户下发的查询是应用到大棚内CO2气体浓度的监测，而且大棚内近期浓度较低，想查询出哪些点位浓度较低，则此时，用户下发的查询便是尽量查询到CO2浓度值较低的节点，即想获得的C1这样的节点，则此时我们称C1支配C2。综上，我们可以得出，按照用户的不同查询要求，不同的感兴趣方向，查询的结果会不同，甚至相反。上面例子我们假设查询数据仅存在一维属性，即CO2浓度值，那么本章所提出的“轮廓”一词用在什么场合呢，就刚刚的问题，我们会自然地想到，当查询数据的属性要求是多个维度时，我们该如何查询。这就是轮廓查询要解决的问题。设存在两个传感器节点C1、C2均监测温度、湿度两个属性值，若用户想查询到温度上大且湿度上也大的节点，即通过查询得到的节点C1在温度、湿度属性上都不比另一个节点C2差，且至少在一个属性上比C2的好，这样我们就可以说，在该用户需求下，节点C1支配节点C2。定义一个数据集合U，“轮廓”就是集合U的一个子集，且该子集内的全部数据在任意属性维度上均不被集合U内的任何其他数据支配，则该子集内的所有数据点就是集合U的“轮廓”，是数据信息中的特殊数据9。为了满足用户对多维属性上的查询要求，多种轮廓查询方法应运而生，如本文提出的基于空间的轮廓查询方法，该方法是在查询属性中包括空间距离数据的一种轮廓查询方法，针对这样的特殊属性，本文提出了特殊的处理策略来加快查询。图2-1 Skyline选择宾馆例子利用轮廓查询的结果，可以仅针对轮廓结果采取进一步措施来处理，避免针对整个集合内全部数据的逐一处理。经典例子就是海滩度假选择宾馆，如图2-1所示，图中黑色点的集合就是距离海滩近且价格便宜的轮廓数据，而这个查询过程就是轮廓查询。例如在多个仓库囤积苹果，每个仓库内安放传感器进行温度、湿度的监测。当通过下发的轮廓查询，查找到某些仓库的温度高且湿度大时，苹果保护工人只需要针对这些轮廓仓库内的苹果进行处理，如降温等，无需对所有仓库内苹果进行处理。因此，轮廓查询技术在现实生产生活方面得到了广泛应用，可以减少不必要的操作，节约时间，节省能耗，达到事半功倍的效果。2.1 轮廓查询基于上述传统监测策略仅能监测大范围地区平均情况，对于任意小范围灵活性受限的问题，考虑到环境监测多涉及到空间属性问题，且该问题通常为一般的轮廓查询带来大量的计算代价，因此本文提出一种传感器网络中的轮廓查询策略来解决空间属性相关的轮廓查询。目前，现有的传感器轮廓查询策略基本上可以分为以下两类：1)基于非空间的轮廓查询策略，如文献101112131415所示，这种策略的特点是所有传感器节点均需参与查询。由于所有的空间属性及非空间属性同时参与查询，这类策略会带来大量的支配比较次数及计算代价，同时，数据元组过长，数据传输代价及节点能量消耗增大，查询到的可能是污染能力很大但距离人群密集处很远的数据，这些数据并非是人们最关心的数据；2)基于空间的轮廓查询策略。如文献1617181920所示，策略通常应用到与查询位置相关的轮廓查询中，但当前现有的该类策略仅能查找到对查询区域有影响的空间位置，未能返回区域周边质量概况。2.2 典型的轮廓查询方法由于传感器网络轮廓查询策略多数是取数据的全部属性进行支配关系的判定，并没有将基于空间属性的轮廓查询进行单独考虑。本文由空间属性的特性，将传感器网络中的轮廓查询分为两类，一类是基于非空间的轮廓查询方法，全部属性同时参与查询，另一类是基于空间的轮廓查询方法，将空间属性单独考虑，将其作为一种特殊的查询属性。2.2.1 基于非空间的轮廓查询方法对传感器网络轮廓查询,基于非空间的轮廓查询策略最常见的是基于过滤器削减策略，如文献101112132122所示。文献10支持多维数据的轮廓查询，返回的是在多维属性上不被支配的节点集合，提出了轮廓查询的In-network处理算法，这个算法可以实现降低通信成本且实现负载均衡，但其从根节点下发初始过滤器并且在各个节点不断地更新，削减能力最强的过滤器在叶子节点产生，并随查询结果回传进行第二次削减，这五次增大了计算代价，加大传感器能量消耗。文献11提出了称为SKYFILTER的一种基于过滤器的轮廓查询策略。该方法利用对传感器节点之间的无线通信的削减来提高效率，通过计算得到多维过滤器来提高传感器节点间整体无线通信的削减效率。文献12在传感器节点处设置本地或全局过滤器，过滤器的设置可以抑制不必要的数据传输，但是，全局过滤器的使用有一定的限制，它仅适用于中小规模的传感器网络。以上策略将导致在数据回收过程中产生大量的传输消耗，计算过滤器时花费大量的存储及传输代价。文献13通过全局和局部优化实现多维轮廓查询，将子空间轮廓书记与父空间轮廓数据联系在一起，子空间进行轮廓查询后，必须将其结果归并到现有的父空间轮廓查询，且这个父空间是已经扩展的，这无疑带来了一定的计算代价。文献14是基于流的分布式轮廓计算方法，提出了分布在零散的多维对象的复杂轮廓监控功能方法，针对处理对象的碎片提出了随机游走模型。 文献15是面对维度灾难问题，提出的从众多的轮廓对象中选择最有趣的对象来获得真正可控的和个性化的查询结果。因此，该类策略节点间的支配比较次数及计算代价都会增加，元组过长，数据传输消耗及能量消耗也会随之加大，获得的数据节点可能是污染较为严重的区域但是距离人群密集地较远，这样的节点并非是人们真正关心的地理位置。2.2.2 基于空间的轮廓查询方法文献1617181920232425都是现有的基于空间的轮廓查询策略。这些方法通常是与查询点相关的轮廓查询。文献1617是将所有其他数据节点信息统一传送到某一节点处的，在该处判断与现有轮廓节点之间的支配关系。这种策略在局部网络出现问题时，会直接影响整体结果的正确性，效率低，传输代价大。文献18提出的策略是利用三角剖分法将查询空间划分为多个三角区域，在各个区域进行轮廓查询。任意三角区域要等待顺时针方向相邻的三角区域传来的局部轮廓结果而不能并行执行，降低效率。文献19是基于范围的轮廓查询，利用I-SKY及N-SKY索引方法同时考虑空间和空间对象的查询属性，来处理对象频繁运动的查询，这种索引方法能够避免了重新计算查询的索引和结果从零开始。但是却增大了索引带来的一定代价。文献20解决的是以单调函数计算前k个曼哈顿空间轮廓查询问题，提出一个算法以近似线性的时间来计算前k个轮廓节点。以上空间轮廓查新策略仅能查询到在空间位置上对查询区域有一定影响的区域，但其不能查找到整个查询区域的环境污染概况。由此，本文提出基于几何学的空间轮廓查询方法，首先利用数据的空间属性查找到空间位置上不被支配的空间轮廓数据，进而削减掉全部被支配的数据节点，这些节点不能满足用户的需求，空间轮廓的削减可以减少网络中数据的传输，减少后续查询过程中节点之间的支配比较次数，降低传感器能量的消耗，此外，还能够提高查询的有效性并减少查询时间。下面介绍空间支配关系以及空间轮廓的定义。1)空间支配关系节点间的空间支配关系是一个基础性定义，在此基础上可以快速了解空间轮廓的定义。设数据节点集合P=p1,p2,.,pn，代表的是传感器节点集合，包括在2维空间的一些数据点。其中，传感器节点的功能是感知数据、处理数据、转发数据以及参与轮廓查询。查询节点集合Q=q1,.,qn，如图1-1所示的所有居民区构成的集合，包括在2维空间的一些查询点。D(pi,qj)是2维空间中的距离量。图2-2所示的为节点间支配关系，其中，矩形边框B是最小矩形边界MBR。查询过程中，B不断更新，B=BMBR(SR（p，Q）)。B中包含所有的候选轮廓节点。B之外的数据节点为被支配的节点，因此，无需判断与他们之间的支配关系。图2-2 节点间支配关系如图所示，已知一个2维的查询节点集合Q=q1,.,qn，以及两个数据节点p、p，那么，空间支配关系的定义如下：定义1：点p空间上关于Q支配p当且仅当对于任意的qiQ，D(p, qi)D(p, qi)并且对于某个qjQ有D(p, qj)D(p, qj)。已知一个二维点的集合中有两个数据点p，p，以及两个查询点q1，q2，之所以p点空间上支配p点是因为q1和q2到p的距离都比到p的距离小，我们设直线l为pp线段的垂直平分线，那么q1，q2，p会位于平分线l的同一侧，而p却在平分线l的另一侧，我们使用这个几何学规则解释两个点之间的空间支配关系，从而来证明我们所举算法的基础理论。对于每一个点p，存在一个圆C(qi, p)，这个圆的中心位于点qi并且它的半径为D(qi, p)，很明显的看到，qi到圆C(qi, p)内任意一点的距离都比到p的距离小。如图2-2所示，图中显示了p的支配区域以及支配p的区域，因此，我们只需要判断每一个p相对于那些在支配p的区域的点，无需比较所有的点与点之间的支配关系，通过这一理论，我们可以快速削减掉被支配的节点，减少节点间支配比较次数。2)空间轮廓通过上述支配关系的比较，能够找到空间上关于查询点集合支配能力较大的数据节点集合，这些节点就是空间轮廓。已知数据点集P=p1,p2,.,pn以及查询节点集Q=q1,.,qn：定义2：与Q集合相关的P集合的空间轮廓是指空间上不被P中任何其他节点支配的P集合中的节点。节点p在关于Q的空间轮廓集合记为pS(Q)。由此我们得到如下公式： pS(Q) pP且pp, qiQ,使得D(p, qi)D(p, qi) (2.1)2.3 本章小节本章首先介绍了轮廓查询的基本思想，然后提出了典型的轮廓查询方法，本文将典型轮廓查询方法大致划分为两大类方法，一类是基于非空间的轮廓查询方法，在这类方法中，本文主要介绍了基于过滤器的轮廓削减方法，及基于流的分布式轮廓计算方法等，通过对这类方法的分析，我们了解到该类方法针对于实际背景未能做出有效的解决，且对于网络中的能量消耗也是较大的。另一类方法是基于空间的轮廓查询方法，当前对这类方法的研究仅局限于查找空间问题上的感兴趣的点，并未结合其他多位属性进行轮廓查询。将针对上述存在的问题，在本文后面的研究工作将展开讨论。在基于空间的轮廓查询中，本文还介绍了空间支配关系及空间轮廓的相关概念，以为后续空间轮廓查询方法的具体介绍做准备。第3章 基于几何学的空间轮廓查询第3章 基于几何学的空间轮廓查询为了减少数据之间的比较次数，本文提出了一种按照部署在不同地点的传感器节点采用基于几何学的区域划分策略将区域进行划分的方法，由于传感器检测的属性包括空间属性（即到各查询点的距离）及非空间属性（如检测的PM2.5值或空气中SO2浓度等），由此，本文提出采用基于几何学的空间轮廓查询方法快速查询到一部分在空间距离上支配能力更大的地理位置，首先计算出由查询节点形成的最大查询边界，利用基于凸包顶点的轮廓区域削减方法，可以快速查找到在空间位置上距离人群密集处较近的部分数据节点集合。3.1 基于传感器部署的区域划分如图3-1所示，虚线圈表示查询区域，图中下标为q的代表图1-1中的人群密集处，如居民区等，图中下标为p的代表部署在工厂等污染源的传感器。要想查询到距离所有居民区都近的的传感器节点，即为空间轮廓数据。根据传感器节点要安放的位置，将整个查询区域划分成若干个基于几何学的不同子区域，每个子区域内对应一个传感器节点。图3-1 查询区域示意图3.1.1 Voronoi图本文采用几何学中Voronoi图26方法对空间区域进行划分，该方法是一种高效的几何划分策略，在划分的各个子区域之间可以进行区域间支配关系的判定。在d维空间中的一个集合P的Voronoi图将空间划分成若干区域，如图3-2所示，包含点p的区域V(p)记为Voronoi单元27。这个Voronoi单元每条边都是连接点p及P中的另一个点p线段的垂直平分线。针对于每一个点p的Voronoi边，它的相应点p称为p的Voronoi邻居。相应于点p（pP）的区