无线传感器网络极大地拓展了人类对物理世界的感知能力,在诸多方面都有着广泛应用,因此受到学术界的广泛关注。无线传感器网络上的数据收集和查询处理是其提供的基本而重要的服务,然而无线传感器网络的能量受限、自组织、可靠性差等特点导致其在支持数据收集和查询处理方面存在许多困难。首先,节点电源能量有限成为阻碍WSN应用的严重问题。而在大规模网络中通常存在长距离数据传输以及巨大的数据流,这两个因素在很多应用中大大加剧了某些节点的能量消耗速率,从而严重影响网络生命期。因此,如何在数据收集和查询处理过程中延长网络生命期成为第一项挑战。其次,用户感兴趣的检测目标与传感器节点的感知对象不尽相同,可能对隐藏在原始数据中的有用信息和知识感兴趣。在这种情况下,不需要将所有原始数据上传到sink节点的网内处理成为节约能耗的重要途径。然而由于节点计算和存储能力有限,如何在资源受限的情况下使得网络能够支持新的查询成为第二项挑战。最后,因为WSN具有很强的动态特性,数据传输路由及其所支撑的应用可靠性相对其它无线网络较低。如何保障查询处理和数据传输的顺利进行成为第三项挑战。本文针对上述三项挑战考虑数据收集和查询处理相关优化问题,提出相应优化策略和算法,并从理论和实验角度分析和验证所提策略和算法的有效性。本文取得如下研究成果。首先,分别针对网络中的数据收集以及多对多的数据聚集这两种应用提出最大化网络生命期的优化策略。(1)首次研究了数据收集传感器网络上的最大化生命期问题,其中生命期被定义为数据收集的轮数,直到第一个节点耗尽它的能量为止。证明该问题是NP完全的,并提出一种近似最优化算法。提出一种改进策略,以减少巨大的计算开销和存储整数规划的空间。最后以大量的实验验证了算法的效率。(2)研究了如何获得能量有效的聚集策略,以优化传感器网络中的多对多聚集。即在网络中,多个节点提供自己的数据,同时多个节点需要某一部分数据的聚集值。证明在同时考虑路由和聚集选择的时候,该问题是NP完全的。所提出的三个近似算法中,两个算法针对特殊情况,一个算法针对问题的一般情况,其核心思想是利用针对Steiner树问题的近似算法。所有算法都被证明具有常数或者多项式近似比。其次,分别针对极值区域查询和概率Skyline查询这两种WSN中的新查询提出查询处理和优化算法。(1)研究了极值查询的一种更普遍的情况—极值区域查询,即给定查询半径R,极值区域查询将返回所有半径为R的碟形区域取值中的最大/最小值,其中一个碟形区域的值被定义为该区域内所有传感器读数的某种聚集结果。针对该类查询提出一种分布式算法EXQ,不但有效减少了查询处理过程中的能量开销,而且使得每个传感器的能量消耗更平均,从而延长了网络的寿命。从理论和实验两方面比较了EXQ和集中式算法的能量开销和能耗分布。(2)研究如何计算存在概率最大的skyline的问题,称为Pr-Skyline问题。为此,首先给出Pr-Skyline问题的定义,并证明其是NP完全问题及多项式时间不可近似性。尽管如此,所提出的SKY-SEARCH算法结合多重剪枝策略仍然能够保证在较大的数据规模下仍具有较高的平均计算效率,并且基于过滤器的分布式优化策略显著减少了查询过程中的传输开销和节点所需的存储空间。大量的实验验证了SKY-SEARCH算法和分布式优化策略的执行效率和可扩展性。最后,分别针对发现查询处理过程中的关键节点(割点),以及在低任务周期模式下的多查询调度提出相关算法和优化策略。(1)提出了一种高效的分布式割点探测算法CVD,并发地遍历拓扑图上的各个节点,并对基于区间编码的生成树上的边进行染色。该并发模式极大地减少了查询处理过程中的时间延迟,并且提出了一种优化策略以进一步减少能量开销和时间延迟。证明了CVD的正确性,并从理论和实验角度分析了CVD的性能。模拟实验和真实实验均表明,与其它算法相比,CVD具有更低的能量开销,更短的时间延迟,以及更好的可靠性。(2)为了缓解网络在低任务周期(low-duty-cycle)模式下的传输拥塞并减少数据丢失,每个查询需要进行调度,以在时间和空间两个维度上平衡各个节点的传输负载。本部分工作因而定义了负载平衡(LB)问题,并证明其在网络拓扑无限制的情况下是NP完全问题。提出两种时间调度算法,并分析其性能。然后提出一种基于所提算法的查询调度协议。模拟实验结果显示,所提算法在绝大多数情况下显著地提高了网络的性能。