论文部分内容阅读
无线传感器网络综合了无线通信、嵌入式系统和分布式处理等多种技术,近年来成为工业界和学术界的研究前沿和热点。该技术具有广阔的应用前景,能广泛应用于国防军事、环境监测、城市管理、智能家居、制造业、反恐抗灾等领域。数据管理技术是无线传感器网络的重要支撑技术,其目标之一是在满足应用要求的前提下尽量减少节点能量消耗。 当前研究者主要集中在选择查询、聚集查询等简单查询算法的研究上。随着技术的不断进步,传感器节点的计算、存储和通信功能都在不断增强。硬件的进步,使得节点可以做更复杂的事情,也刺激了新的复杂应用需求。本文针对复杂查询处理技术展开了研究,利用网内处理、分层、过滤器等机制,尽量下推操作符,避免不必要的通信开销,大大提高了算法效率。本文的主要贡献包括以下几个方面: (1)健壮数据聚集 网内聚集查询在中间节点对数据进行预处理,可以减少消息传送的数量或者大小,从而实现能量的有效利用。本文分析了错误和异常数据可能对聚集结果造成的影响,提出了健壮聚集算法RAA。RAA对传统聚集查询进行了改进,在聚集的同时利用读向量相似性判断数据是否发生了错误或异常,删除错误数据,聚集正常数据并报告异常,使用户可以对网络目前状况有清晰的理解。 (2)中位数查询 低廉的价格和恶劣的环境会导致传感器节点采样数据中存在误差和异常数据,所以有时候需要通过中位数查询来反映整个监测区域的平均水平。首先提出了基于等高直方图的中位数查询算法HMA,然后对其进行了扩展,提出了结合直方图与过滤器的HFMA算法,每个采样周期中只需要收集落在过滤器当中的数据,大大减少了能量开销。另外提出了影响因子的概念,用于对过滤器外的数据的分布进行评估,影响因子是可以聚集的,基站通过收到的落在过滤器内的数据和影响因子的聚集结果便可以计算出精确的中位数值。 (3)空间受限的自连接查询 连接查询是传感器网络中一类重要的查询,可找出不同数据源之间感知数据的联系。如果节点只和自己周围的节点发生连接关系,本文称这样的查询为空间受限的自连接查询。利用现有的SENS-join算法可以解决空间受限的自连接查询。但是在SENS-join算法预计算阶段,它要把所有的属性连接元组都发送到基站。对于空间受限的自连接查询,由于每个节点只和自己周围的节点发生连接关系,那么显然将所有的属性连接元组都发送到基站会浪费过多的能量。于是本文对其进行了改进,首先提出了层次网格路由策略,其特点是地理位置上临近的节点的数据可以在某个较高层次的网格簇头汇聚;然后基于层次网格提出了高效的自连接查询算法,在网格簇头提前进行半连接操作,可以将部分非匹配元组在网内提前过滤掉,从而避免将他们发往基站,进一步降低节点能耗。 (4) Top-k Region查询 由于传感器节点的读数存在噪音,以单个节点的读数作为查询结果不是那么可靠;另外,单个节点的监测范围有限,往往不能覆盖到用户要求的区域,基于此,本文提出Top-k Region查询,以区域而非节点作为查询结果。本文对传统sql语句进行了扩充,以方便用户使用sql语句提交Top-k Region查询;分析了静态区域和动态区域划分下的Top-k Region查询。针对动态区域划分下的Top-k Region查询,提出一种分布式的查询算法,利用分而治之的思想首先将网络分成很多区域,然后每个区域自组织形成一个簇。大部分簇内节点的区域聚集值可以在簇头算出来,簇头可以将不会成为结果的值提前过滤掉,避免了过多的区域聚集值传往基站,大大提高了效率,延长了网络生命周期。 (5)查询处理原型系统的设计 在原型系统方面,在借鉴现有的系统架构的基础上,本文提出了可扩展的三层架构,最上层利用Internet连接可以快速增加或删除基站,可以很好的适应大规模网络;采用有线加无线的方式,可以实现查询的快速响应;采用分层的结构,可以充分利用基站和代理节点的能力;针对该架构,给出了系统功能组件的详细描述;在此基础上,对相关技术难点进行了探索,完成了技术选择和概要设计。