传感器网络是一种无线网络，它们广泛应用于环境监控、目标跟踪、建筑物安全监测、农业精细化耕种、活火山监测、运输业监控、人类活动监控以及其他监控领域。传感器网络的数据，其表现形式与传统的数据源完全不同，它们成倍连续地传送，是一种快速、时变、不确定、无限的数据流，而且跟历史信息无关。　　 在数据流模型中，某些或全部需要被操作的输入数据并不是通过随机访问硬盘或内存得到的，它们是以一个或多个连续的数据流形式达到的。数据流在几个方面与常规的存储关系模型不同。对于数据流来说，随机访问特定数据是不允许的。数据流中的各数据元素是在线达到的，系统并不对来自于一个或几个数据流源的各数据元素达到的顺序进行控制。数据流在规模上有可能是无限大的。当数据流中一个数据元素被处理完毕，它就会被丢弃或存档。除非被存放到存储器中，否则被处理过的数据元素不容易被取回。相比于数据流的规模，显然存储器的容量是非常小的。　　 传统的数据库管理系统及其改进版本都无法适应对传感器网络数据流的有效管理。为此，需要建立一种全新的数据流管理系统(DataStreaming Management System-DSMS)，以便处理数据流并可对数据流进行动态、持续的查询操作。　　 传统的数据库系统并不是设计用来处理时间紧急的一类应用问题，它们也缺乏支持实时处理或实时交易所需要的特征。而且，传统的数据库管理系统也不是设计用来连续且快速地载入个体数据项，它们不能直接支持连续的数据查询，而这恰好是数据流应用的典型特征。此外，在对高速数据流进行查询和其它处理(如数据分析和数据挖掘)时，重点关注的是查询结果的近似准确性和查询过程的自适应性；而传统的数据库管理系统关注的重点则是由稳定的查询计划所计算出的精准答案。如果用于对数据流进行复杂且大量的持续查询，传统的数据库系统及其数据处理算法在功能上是不能满足要求的，面对这样的应用问题其数据管理和数据处理方法在很多方面都需要被重新考虑。　　 在本文中，针对成倍、连续、高速以及时变的数据流，我们研究了数据管理及查询处理的相关问题，将研究重点集中在称为数据流管理系统这种新出现的数据库管理系统技术上。与传统的数据库管理系统相比，数据流管理系统能够对实时进入和实时离开系统的连续数据流进行持续的查询，数据仅存放在主存储器上以便处理。这种数据流可以是传感器数据、证券市场数据或网络数据流等。　　 在数据库管理系统领域，一直以来一个重要的挑战就是如何最优地利用资源以使系统的性能达到最佳，同时兼顾、平衡其它因素，如数据的可恢复性和可靠性。数据流管理系统也具有这些特征，但它们常常有着不同的侧重点。数据流管理系统涉及的是推送式数据源(Push-based Sources)，这种数据源常常通过在系统中登记过的持续查询输入数据流。一般来说，查询结果的有效性往往取决于结果产生的速度。这意味着极小化延时和极大化数据流通量是极为重要的，所以希望能够将CPU执行时间和内存使用量降到最小。有很多相关技术可以用来达到这些目的，如删除不重要的元组以降低系统的负载(负载剥离)，对算子的排序进行最优调度以减少系统所需要的元组数量，等等。在这些技术中，有很多种(如负载剥离)会大大影响查询的准确度，从本质上来说也就改变了查询的原意。因此，有必要研究更准确的查询技术以及系统性能评价标准，兼顾性能和准确度两者之间的平衡，并确保查询达到一定程度的准确性。　　 在本文中，我们提出了一个自适应分布式数据流管理系统(Adaptive Distributed Data Streaming Management System-ADDSMS)的框架，该系统是一个数据流控制接口，它运行于分布式数据流资源阵列与需要访问和分析这些数据流的终端客户之间。整个框架提供了一种数据流管理和数据流查询处理的机制，可为分布式传感器网络数据流的在线获取、管理、处理、存储以及融合提供支持。　　 所提出的自适应分布式数据流管理系统由三个主要模块组成：系统管理模块，数据封装模块以及查询处理器模块。这种系统结构为数据流的处理提供了一种分布式方案。　　 系统管理模块由三部分组成，包括数据流与查询登记，查询优化器以及查询分配管理器。其中，最重要的是查询分配管理器，它采用优化过的查询和费用模型作为图形分配器的输入。图形分配器被用来聚类在已知数量聚类中的各图形节点，这些聚类代表查询执行节点(即查询处理器模块)。以输入数据流的特征和操作算子的费用模型为基础，可以计算出各操作算子的开销。查询分配器具有自适应性，它可以每隔一定周期自动执行查询分配指令。当输入数据流的特征改变时，查询分配器也会即时执行查询分配指令，在这种情况下，费用模型变得无效。如果由于增加或删除了某些查询使得查询计划被修改，那么查询分配必须重做。此外，当某些处理器模块出现故障时，在故障期，分配管理器可以在现有的无故障处理器模块中重新分配查询计划；在故障模块恢复正常后，它还可以再次将查询计划重新分配到所有查询处理器模块中。　　 数据封装模块由两部分组成。第一部分是数据流接口组件，它负责从数据源(即传感器网络)读入数据流。数据流接口使用的是一个网络接口，该接口从传感器网络中挑选出数据并检查它们的有效性。如果是有效数据，那么该数据将从字节数组形式解码成与其匹配的对象类型。然后，数据对象会被转换成包含所有类型数据字段的记录对象。对一个特定数据流源的封装就是将其数据转换成一个统一记录，该记录携带着数据流元素的所有数据字段。记录对象含有数据字段的名称、类型和数值，所以我们可以在来自于各类数据流源的所有各类数据流中使用相同的算子模型。数据封装模块的第二部分是流监控组件。为了计算已登记查询的费用模型，必须获得输入流的特征。流监控组件的任务就是为系统收集有关输入流的统计信息并将这些信息发送到查询优化器和分配管理器。数据封装模块的这两个组件都使用所收集的元数据以生成自适应分布式查询。　　 查询处理器模块包含九个组件：查询计划分析器、算子组态、算子调度程序、执行引擎、执行运行监控器、连接管理器、流接收器、流发送器以及存储管理器。所有这些组件都被集成在查询计划的执行之中。此外，非常重要的是这些组件都是按照使整个系统的性能达到最优的方式来运行的。所有这些组件都保持相互通信，这就使得在这些组件之间进行切换的开销可以达到最小。查询处理器模块的核心是算子调度程序，它是一个线程，在一组基于查询计划的给定条件下，该程序决定着哪个算子被执行。在内核层，线程调度程序决定着运行哪个算子以及如何在算子之间共享资源(如处理器的时间和内存)。算子调度的目的是极小化内存需求和元组延时。　　 查询分配管理器和算子调度程序是数据流管理系统的主要组件，它们与整个系统的自适应特征密切相关。　　 近年来，大规模监控基础设施(如无线传感器网络)的出现，带来了如何采用分布式方法处理数据流的查询这样一个具有挑战性的问题。在监控网络中，数据流的查询必须在系统内部采用分布式方法进行处理，以便使网络中资源受限的各查询处理器节点的性能达到最优。此外，在数据流高速传输的环境下，为能实现数据的高流通量和低延时，查询处理的操作算子必须能被自适应地配置在查询计划中，以使数据移动的代价最小。　　 在本文中，针对无线传感器网络的数据流管理系统，我们提出了一种三级优化策略，包括传感器定位优化、查询分配优化以及查询操作算子最优调度，以最大限度地减少处理数据流所需要的资源。　　 第一级优化是针对传感器部署(即传感器节点定位)的优化。在无线传感器网络中，传感器的部署是一个至关重要的问题，它对网络的建造成本、查询操作需要处理的数据量以及网络的监测能力都会产生重要影响。在监测区域对多个传感器实施最优部署，可以使传感器节点的数量达到最少，而传感器数量的减少又有利于减少数据流管理系统需要管理的数据量。过去虽然有许多研究都曾涉及到这个问题，但它们大多都假设监测区域是一个开放式空间，即传感器可以部署在该区域内的任何位置上。在本文中，我们考虑的监测区域是一个有定位约束的区域，即在区域内的某些位置点是不能部署传感器的。传感器定位问题(Sensor Location Problem-SLP)是一个非线性、非凸规划问题，其目的是要确定所有传感器的安装位置，以对目标区域实施有效监控。对传感器定位的要求是，使用最少的传感器，而使监控覆盖的区域达到最大。　　 进化算法是一类模仿生物世界选择与进化机制的通用随机搜索方法。进化算法与其它优化算法不同(如爬山算法和模拟退火算法)，它不是依靠一个解而是通过一组有潜力的候选解组成一个群体去解决一个优化问题。　　 一般来说，各种进化算法都是基于以下机制运行的。由若干个体组成一个群体，然后将群体初始化。每个个体都对应着优化问题一个可能的解，解的质量可以通过一个适应度函数来评价。进化算法在每一次迭代中，即在进化过程的每一代中，都会执行选择操作，该操作会将适应度较好的个体挑选出来并让它们进入到下一代的群体中。使用变异、交叉或其它进化操作可以改变个体。以上过程被不断重复，直到算法产生的结果收敛为止。此时，可以认为由算法找到的最终解就是优化问题的最优解。遗传算法(Genetic Algorithm-GA)和粒子群算法(Particle Swarm Optimization-PSO)被认为是最重要的两种进化算法。对于许多组合优化问题来说，GA和PSO已被认为在获得最优解或近似最优解方面是最有效的，但它们也存在一些缺陷。目前，已经出现了一些混合算法，用来克服GA和PSO的缺陷。研究人员已经提出了PSO算法一些改进的版本，其中引入了其它进化算法的优异特性。最近几年，已有很多学者研究过如何将选择、变异、交叉以及各种不同的进化机制结合进PSO算法中。　　 GA和PSO在它们固有的并行特征方面是非常相似的，然而实验结果表明，在求解不同的优化问题时它们又有着各自独有的优点。我们希望将这两种算法综合在一起，以期获得两者的优异特征。在本文中，我们提出了一种自适应混合优化算法(Adaptive HybridOptimization-AHO)，该算法采用一个模糊逻辑控制器作为智能切换开关，它可以在不同类型的优化算法之间按某种规则进行自动转换。　　 在本文中，我们采用了三种进化算法来求解传感器的定位问题，包括粒子群优化算法PSO、遗传算法GA以及我们提出的自适应混合优化算法AHO。AHO算法包含PSO算法和GA算法。在进化过程中，AHO算法通过一个模糊逻辑控制器(Fuzzy logic controller-FLC)可以自适应地在PSO算法和GA算法之间进行智能切换。通过改变感应模式、传感器数量以及监控区域的定位约束，我们分别采用这三种进化算法对传感器部署问题进行了多种仿真实验，对各种条件下由这三种算法所获得的监控区域覆盖率和计算成本都进行了比较，结果表明这三种算法在各种条件下都能获得好的定位效果。但与PSO算法和GA算法相比，AHO算法由于能够利用PSO和GA算法各自的优点并避开它们的缺点，在二元感应模式、指数衰减感应模式以及梯度衰减感应模式下，采用AHO算法对传感器进行部署可以获得最大的监控区域覆盖率，而且只需经过较少代的进化AHO算法就能获得传感器定位问题的全局最优解。　　 第二级优化是针对查询分配过程的优化，其目的是要将多个持续查询以负载均衡的方式分配到所有查询执行节点(即查询处理器模块)上，并极小化各处理节点之间的交互通信总量。对数据流进行一次持续查询可以形象地用一个数据流图来表示。为了在一个数据流管理系统中运行多个持续查询，通常的方法是将它们的数据流图统一在一个查询计划上，然后由一个查询执行引擎依次执行计划中的各个步骤，产生出所需要的查询结果。在查询计划中有“节点”和“边”这两个基本要素，节点有三类，分别是源节点(代表数据流源)、操作算子节点(包括选择算子、连接算子、合并算子、聚合算子、时间尺度算子以及窗口算子等)以及汇点(代表用户的应用软件)；而连接两个节点的边则代表节点之间的数据流。查询计划的这种特征使它可以用一个有向非循环图(称为查询图)来表示，图中的每个顶点都代表一个操作算子，而每条边则代表数据流；在顶点和操作算子之间、边与数据流之间分别构成一对一的映射关系。自适应分布式数据流管理系统(ADDSMS)的性能完全取决于能否将多个查询在可用的各查询处理器之间实现均衡的负载分配以及能否极小化各查询处理器之间相互通信的影响。在本文中，我们采用了一个合适的费用模型用于查询计划与查询图(有向非循环图)之间的映射，并根据“数据流处理与监测公用系统”(Public Infrastructure for Processing and ExploringStreams-PIPES)中连续滑窗查询的语义学规则和实现机制建立了该模型。PIPES是一种基础资源，它可以提供构建一个分布式数据流管理系统所需的各种基本要素或组件。费用模型为每个操作算子提供了费用计算公式。将一个操作算子的费用计算公式应用到它的输入数据流，就可以计算出它的输出数据流的特征。对任一数据流进行查询，该费用模型都会从查询计划图的数据流源开始自底向上依次运用费用计算公式计算出所有中间数据流的特征。所产生的查询图可以反映出每个算子的费用以及前后算子之间的通信开销。　　 为了将多个持续查询以负载均衡的方式分配到相关查询处理器节点上，可以采用图形分割算法对查询计划图中的操作算子群按负载均衡以及节点间交互通信量最少的原则进行分割。在本文中，我们提出了一种新的蚁群算法，称为载物相似度蚂蚁模型(Similarity CarryingAnt Model，SCAM-ant)，用于求解数据流查询计划图的分割问题。第一个蚁群聚类算法是由J.L.Deneubourg等人提出的。后来，P.Kuntz、P.Layzell和D.Snyers提出了一种用于图形分割的蚁群聚类算法，称为KLS算法，该算法将图形分割问题嵌入到一个欧几里德空间或欧几里德平面中去考虑。基于蚁群的聚类模型本质上是一个动力学系统，蚂蚁可以移动查询图中的顶点(即操作算子)以完成算子的聚类。各顶点(操作算子)究竟被哪些类吸引、被哪些类拒绝是由顶点与类之间的距离决定的。蚁群聚类算法的提出以及对它所做的改进都受到了自然界蚂蚁行为的启发。关于蚂蚁，人们已经发现的特征之一是，一只蚂蚁能够提起自身重量20～50倍的重物。这种特征已经被用来增强蚁群聚类的性能。在我们所提出的蚂蚁模型中，一只蚂蚁在移动过程中具有同时携带多个物品的能力。这种成组抓一放物品的行为可以减少蚂蚁移动的次数，从而达到减少完成聚类过程所需时间的目的。在SCAM-ant模型中，每只蚂蚁在移动过程可以同时搬运多个对象(顶点，即算子)，数量由搬运对象和候选对象的相似度决定。SCAM-ant算法利用了物群移动特性，可以有效减少完成聚类过程所需的时间，这是对现有的单物搬运蚁群聚类算法的改进。　　 为了提供一种适用于数据流查询图顶点(算子)之间相似度测量的方法，我们提出了一种改进的SimRank算法。SimRank原为一种只能确定结构相似性的普通算法。在本文中，我们将SimRank算法与查询图中各条边的权值相结合(边的权值通过费用模型计算)，得到一种新的相似度测量方法，这种方法可以基于查询结构和算子之间的内部数据流反映出算子之间是否具有相似关系。　　 为了有效使用SCAM-ant算法完成算子的聚类，我们提出了一种融合SCAM-ant算法的通用模板。采用该模板，算子聚类的最终结构将紧密遵循由这个模板所定义的构型。模板上所有聚类的质心是基于用户需求定义的，并不依赖于被聚类的操作算子的特征空间。　　 为了测试我们所提出的持续查询分配算法的性能，我们使用了两个指标，即通信开销和负载不均衡性。在不同的算子聚类之间总的通信开销以及在不同查询处理器节点之间的负载不均衡性可以反映出分配策略的优劣。　　 从本文的实验结果可以清楚地看出，与KLS算法相比，SCAM-ant算法的性能更好。通信开销和负载不均衡性这两个指标证实，采用我们提出的SCAM-ant算法，可以在更少的时间内实现更好的算子聚类。SCAM-ant模型是非常有效的，它能减少蚂蚁搬运算子所需要的旅行次数。　　 我们的实验结果也显示出SCAM-ant算法可以生成负载均衡性很好的分布式查询计划，具有最小的通信开销。与光普、线性、散射和多级KL分割算法相比，在分区数量不断增长的情况下，SCAM-ant算法保持负载均衡的能力更稳定。　　 第三级优化是针对查询操作算子调度的优化，其目的是自适应地调度在查询处理中将要使用的多个操作算子。算子的最优调度可以极小化计算机内存需求以及查询结果输出的延时。以前，用于调度数据流查询及其操作算子的方法都假设每个算子是以一个单独的线程运行，或者所有的算子结合在同一个查询计划中像Chain算法[124]一样用单线程运行。这两种方法都存在线程开销过大以及因操作费时引起延时两个严重缺陷。以前在某些数据流管理系统的调度中所建立的Chain算法只关注极小化最大内存使用量，而忽视了输出延时这一重要方面。当输入的数据流激增时，Chin算法将遭受到元祖匮乏，从而引起高延时。为了克服这些缺陷，在本文中我们提出了一种新的聚类算子调度算法(Clustered Operators Scheduling-COS)。该算法基于各算子的选择性和计算开销自适应地将查询计划中的所有算子聚类到不同的组中，并使用S-均值(S-mean)聚类方法计算开销。S-均值聚类是基于相似度驱动的聚类方法，它与K-均值方法相似，但两者存在一些差别。S-均值聚类会将所有的算子组合到一个新的聚类中，如果这些算子对现有各个聚类质心的相似度的最大值小于给定的阈值。但在K-均值聚类方法中，所有节点都必须归到现有的K个聚类中的一个，这对那些与其最靠近聚类的相似度非常低的节点是不公平的。不规定聚类数目K的值可以为聚类过程提供高度的自适应性。　　 为了比较不同算子调度算法的性能，我们采用离散事件仿真系统(Discrete Event Simulation-DES)建立了数据处理单元仿真模型。实验结果表明，将COS聚类算子调度算法与传统的FIFO算法、Chain算法以及多线程算法进行比较，在所有仿真条件下COS算法都表现出了更好的性能。此外，在可扩展性和鲁棒性方面，COS算法也表现得非常好。COS算法还能用高效率的方式使用内存和计算资源，这使得它可以在资源受限的情况下连续工作，而其它调度算法此时却失去了它们的稳定性。实验评估证实了COS算法作为持续查询处理器具备自适应性、灵活性、可靠性、可扩展性以及鲁棒性。　　 总体来说，ADDSMS自适应分布式数据流管理系统是一个数据管理器，它具有自适应能力，可被用来处理数据流。系统中的每一级优化都可以基于数据流的特征和用户的查询提供一定程度的灵活性。　　 在数据流管理系统的研究中，其安全性问题也需要加以考虑。作为今后的一项工作，我们需要关注两类主要威胁：对数据不正当的释放和不正当的修改。以本文提出的系统结构为基础，我们将对安全机制及其实现方法进行研究。至于第三类问题，即拒绝服务攻击，可以通过授权过程加以解决。