《电子信息工程毕业论文8.doc》由会员分享，可在线阅读，更多相关《电子信息工程毕业论文8.doc（25页珍藏版）》请在三一文库上搜索。
1、毕业设计(论文)外文资料翻译学 院： 电子工程学院 专业班级： 电子信息工程 DZ电子083 学生姓名： 范嘉敏 学 号： 510830310 指导教师： 掌明 外文出处： Ad Hoc Networks 附 件：1.外文资料翻译译文； 2.外文原文 指导教师评语：签名： 年 月 日基于最长寿命的无线传感器网络连续查询处理Konstantinos Kalpakis* , Shilang Tang计算机科学部门和电气工程部门,马里兰大学,巴尔摩 摘要监测应用成为无线传感器网络（WSNS）最重要的应用之一。这类应用通常具有长期运行的复杂查询处理技术且通过传感器流对此处理技术进行评估。基于无线传感器
2、网络中传感器的能量有限，高效节能查询的评价对于延长系统使用寿命来说是至关重要的使用期限指的是此网络查询从开始到停止所执行其预定任务的最早时间。我们通过使用表达式树对复杂查询进行建模。我们考虑使无线传感器网络的使用期限最大化以达成表达式树T的持续网络内评估，因此可在基站获得其根值。网络内评估意味着对于算符T的评估可能会推至网络节点且同样意味着对T进行重复评估（每轮一次）。持续的网络内T评估需要解决以下问题的两个方面：（1）相对于网络节点的T的运算符，变量和变量的放置（2）以上量值对于适当网络节点的路径选择，网络节点需要使用以上量值评估运算符。我们对其复杂性进行了分析，并且为T节点在WSN传感器节
3、点上的放置提供了一种简单而有效的算法。我们所提出的运算符放置算法试图使总传输数据量最小化。T的放置可引起一定的最大使用期限并行流（MLCF）问题。我们提供的算法可以找到解决MLCF问题的近优积分方案，其中一种便是收集路径，一定数量的积分流被路由。我们对于T的持续网络内评估包括以上放置和路由算法。实验证明，我们的做法能够一贯地、有效地找到对于无线传感网络表达式树的持续网络内评估的最大使用期限解决方案。 2010 Elsevier B.V. All rights reserved.1.介绍远程监控是无线传感器网络最具有吸引力的应用之一。像环境监测和建筑监测，它们通常会在兴趣点处通过传感器不断的运行
4、查询数据流。例如有一种查询应用，可以在火山监测中每五分钟报告当前活动的情况，这是由于传感器的加工和相关表面振动，气压和温度，气体密度的变化，磁场变异等因素所产生的数据流测量，如何让这些因素运用在这些查询中并得到长时间高效地成功处理和操作的无线传感器网络运行是部署的一个重要的问题，有些问题不可行，是由于经常补充传感器电池的能量成本过高。在本文中，我们在无线传感器网络中考虑长期运行复杂的查询并且对此技术进行评估的任务。此类查询有多个运算符依赖的函数，并要求每一轮每次重复评估运算符。由于在传感器网络中通信前传感器耗能所产生的数据量，我们把目标推向处理网络查询 18。我们的模型运用非循环图Q且对Q进行
5、详细的描述，其内部节点与子节点用操作数运算符 （函数）查询、它们的叶用常量或变量表达。Q的每个顶点都有其重要性且每一组都可放置候选网络节点。在Q的每个顶点上有一组源传感器节点，其用于分配查询结果给该变量。在网络DAG中评价连续Q的表达根需要解决以下两个方面的任务：（a）在Q的网络节点上安置变量和常量的运算符，（b）寻址适合的操作数网络节点，需要他们来评价操作数。这两点内容是有联系的，因为在G的布局上某些源到目标的路由选择要求传感器节点之间以何种方式寻址，这对决定执行寻址的安置具有主要影响。虽然在网络查询中有许多重要的优化目标需要连续评估（如响应时间，可靠性等）。由于部分传感器能耗和着手分析如何
6、分离方面的任务，我们主要是提高系统的最大限度寿命 - 直到传感器网络寿命结束之前完成其执行的预定任务。我们发现，在我们的实验评估中显示，在路由方面有一个最佳解决方案，来有效地分离的路由和安置。在安置任务方面找到最佳的解决方案，我们需要考虑最低通信成本的位置（MCP）。MCP 问题是在Q的单个评价期间对于已分配Q的一个或多个顶点使其在网络节点之间传送数据的总量最小化。MCP问题即使是Q有着成本优势并以单位为1的高度树，但还是MAX SNP-hard。我们描述了一个简单而有效的贪婪启发式，我们称之为GREEDYMCP算法，在实际显示中证明最佳的解决MCP问题的方案可用GREEDYMCP算法来实现。
7、找到一个最佳的解决寻址方案，是我们解决使用并行流最大寿命的（MLCF）问题。MLCF问题是并行的流量为给定的一组源的目标提供数据传输速率以解决系统最大寿命的问题。我们为MLCF问题提供了一个有效的，简单的算法,在网络的n个节点中对于部分源目的地N为了满足带有并行流数据通信要求，其算法在n + N路径中发现了最大限度的分数阶系统寿命To，我们称之为ALGRSM-MLCF的算法。由分数四舍五入下来，我们得到了一个关于MLCF问题最佳并行流解决方案，其a=（To nN +1）/T。在实践中往往Ton+N，a1。我们的实验表明，ALGRSM MLCF优于现有的寻址算法，但可在系统的寿命和能耗方面应用M
8、LCF问题。ALGRSM MLCF 是一种基于修正单形法 (RSM) 的迭代算法。我们在网络中连续查询 Q的评估的方法有 GREEDYMCP 和 ALGRSM-MLCF两种。首先，我们使用ALGRSM MLCF在网络中找到一个Q的位置，并为路由上的所有数据值使用ALGRSM-MLCF来满足传达。我们通过广泛的实验评估表明，我们始终认为在无线传感器网络中对于连续的网络复杂查询评价关键是解决最大寿命的方法。虽然我们采取统一的方式来解决手头的任务，我们只需要两个网络元数据网络拓扑结构和传感器的初始能量，这是对其它许多网络任务都非常有用的知识。请注意，通过我们的方法发现小规模的路由解决方案在传感器中间
9、接的限制了分配路由信息。总之，对于在无线传感器网络（WSNS）中连续处理复杂查询的网络任务，本文贡献如下： 从理论上分析MCP问题的复杂性，是将无线传感器网络中放置DAGs的表达与最低的总通信成本的混合在一起。 为MCP的问题提供贪婪启发式GREEDYMCP。GREEDYMCP在实际应用情况下发现并证明最佳的解决方案。 提供一个简单而有效的ALGRSM-MLCF算法，它会在无线传感器网络中发现最接近整数解来解决最大生命周期并行流（MLCF）问题的方案。 ALGRSM MLCF优于现有的寻址方法。 关于MLCF 问题我们发现放置去耦和即将开始的路由任务都有效 我们使用GREEDYMCP和ALGR
10、SMMLCF方法来最大限度地有效的提高系统的寿命。本文的其余部分安排如下：我们在第2节中回顾相关工作，然后在第3节，我们给予必要的准备工作。我们在第4节中表达描述DAGs中安置的无线传感器网络的GREEDYMCP算法，在一定的MCP问题实例条件下，用GREEDYMCP算法证明找到最佳的解决方案。我们在 4.2 节中分析复杂的MCP问题，并表明MCP 问题对于高度为 1 的树和提供他们限制的顶点是MAX SNP-hard。然后，我们把注意力放在操作数的寻址上，我们在第5节中提出MLCF问题的ALGRSM-MLCF算法。我们在第6节中提出实验方法的评估并描述了结果。在第7节我们得出结论。2. 相关
11、工作pietzuch等人，考虑在传统的分布式处理系统中放置网络运算符。在类似的网络设置中，Ahmad等人，在覆盖的网络中用放置的三个运算符算法构造查询处理并比较其每一个性能。他们认为由节点组成的网络具有互联网的风格，且有足够的计算能力，它不同于我们所研究的有限能量的无线传感器网络。在无线传感器网络中，由于Intanagonwiwat等人在一定的背景下，网络处理的概念被首次引入，在定向扩散中以投机性取巧的方式消除重复。Gehrke和Madden等人是第一个将查询处理和传感器网络集成一体的，可以通过传感器网络很容易的查询任务。在美洲狮项目中，有人建议在传感器网络中以传感器数据分层结构管理作为一个分
12、布式数据库系统。在TinyDB中，无线传感器网络被提出引入查询处理的框架用来从事时间地点分发，往往是在无线传感器网络中采样数据和传递数据。解决能源利用效率是考虑问题的主要因素之一，但不是解决最大系统寿命的目标。此外，在查询运算符中 11,24 从功能角度进行建模，而且往往是相当简单的运算符 （聚合、 筛选器等），而在工作中我们的模型审议优化的运算符的位置是从通信角度考虑的。Ren等人，考虑在简单的聚合查询中进行质量感知处理（如在感兴趣的矩形区域中计算传感器测量平均，最小，最大值）。他们提出了集中式的算法，找到传感器使用无功路由到基站计算概率的答案来收集其测量的子集。Hu 等人扩大了Olston
13、和Widom的工作，提出了连续聚合查询（总和，平均，计数等）的近似答案的问题。他们为传感器测量分配指定了可接受公差范围查询答案的方法。如果它超出公差范围，之后传感器将在基站中测量。这在许多方面与我们的不同：我们只考虑除了最小值、 最大值、 平均值以外的带有各类运算符的复杂查询、 并直接提供准确的解答查询、寻求优化系统的寿命。许多研究者都主张使用以数据为中心的技术，允许网络高效的存储和已命名的数据使用检索查询 16。提出并研究 6,8,23,28,29,31，以数据为中心的推挽式查询处理技术，它可以分类为两种主要方法：结构化和非结构化的基于散列的数据存储技术 29和comb-needle方法23
14、。Kapadia和Krishnamachari 20目前在单接收器方栅传感器网络中（所有类型和任意一个型）运用数学基础分析比较这两种类型一次性查询的方法，后来，Ahn和Krishnamachari 2发现，以数据为中心的传感器网络性能的伸缩性取决于能源和存储资源是否增加，并发现在特定应用程序中更多的节点生成查询负载。Bonfils等人5考虑在传感器网络中查询运算符节点的位置，以尽量减少评估这种表达树的总通信成本。对于任何父-子查询树中的运算符，用一个节点诱导通信成本，然而这些运算符的放置和数据传输速率与从子到其父之间的最短路径是相关的。他们提供了一个分布式的协议，尝试通过优化放置并不断地在相邻
15、节点之间移动以适应变化的数据速率。不认为是通过移动相邻节点所产生的交换信号形成5。我们ALGRSM MLCF算法不同于他们，我们算法是让数据通过多条路径寻求优化系统寿命的，而不是通过单一路径来寻求通信总成本的。限制母与父之间的数据单个路径的寻址，而在不利影响使用寿命的情况下允许多个路径的寻址。可以看到图10，我们的方法采用最短路径的路由算法在所有情况下的最佳位置实现了更好的寿命。Srivastava等人 30考虑有层次结构的放置网络节点，逐步增加计算能力和网络宽带，这样能使总成本的计算和通讯最小化。我们假设在一个不同的网络模型中的传感器的能量是受限均匀的且有不同的目标和优化系统的寿命，这并不一
16、定减少总成本的计算和通信。Garg和Konemann14描述了一种接近并行流问题的迭代算法并最大限度的得到求解证明。它的LP 配方是不同于MLCF。他们的目标是最大限度地提高网络下边缘有限总流量的容量，而我们是最大限度地提高网络有限寿命和节点能量。此外，我们的 ALGRSM MLCF 算法在解决方案中是以路由的路径数量为界的，而在算法14中发现解决方案，它们可以使用任意多个路由路径作为迭代次数。因为有少部分路由路径是重要的，所以在实践中部分因为分发到传感器中，而且相关的路由信息的使用保持较小，有较少的路径。Chang和 Tassiulas 7 提出了一种最短路径的路由算法用来收集最大寿命的数据
17、从而在每个环节的每个节点处反映通信能耗和剩余的能量。虽然他们还制订了一个线性规划的路由问题，他们通过其拟议的算法来获得寿命与现实的寿命进行比较。我们制定的最优路径问题不同于线性规划，我们的 ALGRSM MLCF 算法有效地直接的解决了 LP以获得最佳路由。此外，在算法7的性能中是主要依赖参数所使用的算法，而ALGRSM MLCF是 非参数的。Wu等人32考虑使用一个给定的路由树来兴建发射/接收传感器的时间表，以收集数据。他们描述了发送和接收槽的分配，减少传输过程中的碰撞，以及使用传感器的方法。这项工作对我们的工作是有帮助的。Wu等人32只是假设一个路由树，而我们的方法可在连续查询的评估中构建
18、了一个安置和路由。另一方面，我们ALGRSM MLCF算法不考虑冲突期间通过传感器的传输。推导详细的发送/接收安排位置/路由表也是重要的，他们的方法可能是一个步骤一个目标。3. 准备工作我们利用整个文件记录了定义和符号，其中包括简单的模型，无线传感器网络的概念和表达式树。3.1. 共同的定义和符号给定一个图G，我们用VG 表示其顶点及用EG表示其边缘集。为简单起见，对于顶点v，我们经常写vG，而不是 vVG 和对于边缘点ij写 ijG，而不是 ijE G 。通过其顶点的一个子集让GV=(V,EG V V) 成为G的子图。在子图 G 中诱导其边缘的一个子集，我们通常用 GA=(V,A) 。考虑边
19、缘有向图G带边缘权WR|E|G|。边缘IJEG 的边缘收缩图G是从崩溃（合并）G顶点到顶点j得到的图。一个顶点i到顶点 j 的折叠，我们需要以下三个步骤图：（一）如果KJEG，则每个边缘Wki权数为KIEG，然后添加权数WKI边缘KJ至G，否则边缘增加权数KJ到WKI，（b）如果JKEG。则每个边缘IK2权数为IKEG， 然后添加权数WIK边缘JK至G，否则增加的边缘权数JK 到WIK，（c）删除顶点i和任何自我循环G.（边缘JJ）考虑分区=V1，V2，Vm; 从顶点的分区G设置 V G，代替一些m1。进一步我们通过定义的缩图G表示以下边缘加权有向图G。 G的顶点是，如果在IJEG的边缘存在一
20、个从Vi到Vj的G，即uvEG和uVi,jVj是边缘的切缘。每边的权数等于从Vi到Vj 的边缘G晋级权数的总和。请注意，G的获得是G通过承包所有的内块（未切割）边缘图的总和。鉴于一实例优化问题， opt（I）和sol（I）分别是最优和最可行的解决方案。为简单起见， opt(I) 和 sol(I) 将还相应的标明解决方案。相对误差的解决方案 sol(I) 等于 opt(I)，其近似比等于 sol(I) / opt(I)。每当他们允许实例有未知数的分数值时。请我们参阅连续积分解决方案来优化问题。我们用小写和大写的粗体字母分别表示向量和矩阵，如X和A分别是矢量和矩阵。向量X被定义为 。由于两个向量，
21、我们说x主导y并写成X Y，如果其中我们说 x比 y大是按字典顺序，来说明是否索引一组最小的非零的xy 正负。由于矩阵是一个单一列向量，许多符号/矩阵操作自然是延伸的向量。我们用表示矩阵A的转置。给了n m 矩阵和两个指数序列I属于1,2，n; J属于1;2;.n，我们通过定义A的矩阵;其中由于我们延长的符号和 Ay 是索引集，一组指数序列始终通过其元素按升序排列转换序列列出。3.2. 无线传感器网络模型考虑无线传感器网络 （WSN）的 n 个节点。一个节点用 b表示，其被指定为其余传感器节点的基站。虽然传感器被假定为有限的非补充能量，且传感器通过唯一的 Id 来标识，所以基站没有能源的限制。
22、靠近传感器感兴趣的点称为数据源，而他们在预定义的数据速率中监视和生成感测数据。在基站分析中连续查询获取数据并处理生成的数据源的数据构成，并被解析为一个表达式DAG。时间是离散的，被定义的数据速率是传感器节点在每隔一段时间内传输的数据包的数目。为简单起见，我们假设数据包的大小是固定的。在系统寿命周期T是最早的时候，无线传感器网络在一个或多个传感器中通过耗能来执行其预定的任务（例如查询评价）。无线传感器网络的拓扑结构是仿照一个有向图G=V,E的;用它来代替V=1;2; . n;和E属于VV。每当i能成功发送一个数据包到j，就存在ijE。让距离在i和j之间。为了从节点i发送一个数据包到节点j，让 耗
23、能，并让的节点j收到了数据包所需的能量。为让节点i可使用能源，我们认为b=。为简单起见，我们假设在每个节点附近的单源节点是传感器网络的一个基站。实际部署中可以在相同的节点附近有多个传感器，这将是理想的，他们共享的采集数据。相同节点周围的所有传感器可以收到其中任何一个信号，这可能是很容易做的。引入一个新的节点，与作为数据源，然后追加到G，i附近的1/4范围内为每个传感器节点j，两个新的边和，同时和等于0。传感器网络同样可以处理由多个基站引入的一个新的节点 ，作为新的单一基站，然后追加到G，每个基站为 I，的新的边缘在本文中，我们不考虑有关信号和信道干扰，传输调度是为了避免或减少这种干扰的问题。调
24、度发射后可制定路由方案，这样可在潜伏期增加查询评价。3.3一个复杂查询的评估模型我们将介绍一个简单的模型，我们将使用连续 （重复） 处理的复杂查询。在查询中只有一个运算符（如添加、 相乘，等） 或只有一个操作符 （例如总和、 计数、 最小、 最大等）称为简单，否则它称为复杂。过去我们对于复杂查询是在传感器网络中关于传感器的测量。在每轮感应期间，使用传感器的当前度量单位 （可能是事先测量）查询评估。我们模型使用定向根值的表达图 （DAGs）查询。表达图DAG的一个根值Q是其一个单根（顶点没有任何父母点），符合内部顶点的运算符（无儿无女的顶点）及对应常量或变量。每个顶点vV Q的 有关值不变，但不
25、同的尺寸大小（V）是衡量单位数据包大小的。uvE Q 每边的权数是等于大小（U）。每个顶点有一个或多个操作数（子点），其主要是一个功能的操作。在 AND 运算符 （OR 运算符） 的模型中，对于运算符的功能的评价是需要所有 （任何一个） 其操作数参与的。表达的DAG出现在各个领域，如TinyDB的SQL连续查询评价 选择楼层，房间，AVG（温度）来自传感器地板 70采样周期30秒;其中运算符是关系代数运算符，子叶是传感器样本 （测量），它们都有一个树DAG表示。当请求运算符可用时，需要评估运算符，可以用一个渴望（尽快）或懒惰（当它需要输出要求时）的方式表示。此评价在一定回合不需要分配绑定的值。
26、在一个命令的程序中评价（可能不是全部）运算符，使其根值提供提供给用户。在表达DAG中设H为一个无线传感器网络并用Q来进行评估。我们调用主机图H和客图Q。在时间t中分配变量vV G值，这取决于测量src(v)属于V H ，设置主机的网络节点（传感器）通常要设置v的数据源，设置一个变量的数据源可能是一个单件或是传感器附近的一小部分。为了评估在主机h中的客体Q，我们需要在一个或多个主机节点上放置所有客体顶点。每个顶点vV Q可以在主机节点上被放置一个指定的候选节点如果V是一个变量，则每个在cands(v)中的候选主机节点（V）是V值评估的结果，如果有的话，一次向它提供其所需要的所有操作符，如果can
27、ds=则客顶点为v，如果则受到固定的限制，否则被称为自由。我们扩展设置数据源，并设置任何客顶点子集而候选主机作为和如果我们呼吁一个受理，图1给出了一个示例查询表达的DAG（树）。一个DAG中的客体节点Q被安置到主机的网络H中去，则每个顶点v VQ被放置了一个非空集的主机节点。每当一个顶点vVQ必要的时候，一个主机节点要求被提供，这样做可能需要检测或计算网络节点i，甚至是计算i和其他主机的网络之间的通信节点。图 2 提供了示例并显示了被放置到无线传感器网络上表达的DAG 图形1 图形2此后，我们只考虑位置，其中每个客体的顶点都被放置在一个主机节点上，即在主机的网络中是不能复制客体顶点。考虑将客体
28、网络DAG Q放置到主机网络H。放置在同一主机节点的客体顶点集的候选集的交集一般非空。因此，通过消除放置在不同主机节点的客体顶点边缘（切边），我们能够得到关于客体图的连接组件的集合，这样所有的连接组件的顶点Vi就被放置在同一主机节点ui。换言之，将客体Q放置在主机H会引起VQ 的分区，这样所有Vi的客体顶点将被放置在主机节点 请注意，的每块区Vi是可以受理的我们称这种分区为允许分区。此外，每一轮Q的评估中的传输数据量等于切边的总成本，其中，切边指的是由放置引起的。换言之，给定放置中Q的单个评估所需要的总传输量等于通过分区的Q的收缩的总重量。事实上，从主机节点ui至客体节点uj所需的传输总量相对
29、于中边缘ViVj的重量。确定相当于每轮评估Q中总传输总量的放置成本。通过重新标记每个顶点，其中Vi中的客体顶点被放置在主机节点ui，从而确定放置传输需求图R 成为从中获取的图。由于客体顶点放置在 和 ，边缘的量等于每轮从主机节点ui到主机节点u所需的总传输数据量。我们在放置通信节点中定义最小 Q 到 H 上的成本(MCP) 问题是为了寻找到候选主机顶点上以最低的成本 （传送数据的量）的位置。由于Q安置到主机h上并且诱导分隔边缘的位置，本质上它是遵循的MCP问题等同于下面的总权数图划分问题的。我们为了约束定义分区 （MCCP）最小成本 的问题，如下所示：任何边缘加权图G和一个函数找到这样一个最低
30、的成本切边（边割），非空为每个连接组件的Gi G-A.MCCP问题实例的最佳解决方案，也是为客体Q 到主机 H的 MCP 问题的最佳解决方案，反之亦然。我们研究了 4.2 节的 MCP 和 MCCP 问题的复杂性。鉴于已将客体Q放置到主机H，我们现在需要找到一种高效节能的方式以满足传输需求图R所传达的数据路径需要，从而使系统使用期限最大化。换言之，我们需要找到最大使用期限T以及满足为收集起点终点对数（边缘）的传输需求的路径，其中需求等于从主机节点Si到主机节点di的边缘重量（一轮中所需传输数据量）。这就是我们在第5节中有考虑过的最大使用期限并行流（MLCF）问题。在本文中，我们假设了表达式DA
31、Gs和AND-算法模式。同样，我们也假设变量v V Q的数据源是单个的，因此v固定在其单个数据源主机网络节点上。此外，我们假设Q根固定在基站且Q的顶点放置不会被复制，即，对于所有的vVQ来说，。并且，我们还以为，无论在计算运算符v值的时候，还是在测量和分配变量v值的时候，或者是在配备常量v值的时候所消耗的能源，相比于所有顶点v VQ的传输所消耗的能源来说，都是不容忽视的。外文原文Maximum lifetime continuous query processing in wireless sensor networksKonstantinos Kalpakis* , Shilang Tang
32、Computer Science and Electrical Engineering Department, University of Maryland, BaltimoreABSTRACTMonitoring applications emerge as one of the most important applications of wireless sensor networks (WSNs). Such applications typically have long-running complex queries that are continuously evaluated
33、over the sensor measurement streams. Due to the limited energy of the sensors in WSNs , energy efficient query evaluation is critical to prolong the system lifetime the earliest time that the network can not perform its intended task anymore.We model complex queries by expression trees and consider
34、the problem of maximizing the lifetime of a wireless sensor network for the continuous innetwork evaluation of an expression trees T , so the value of its root is available at the base station. In-network evaluation means that the evaluation of the operators of T may be pushed to the network nodes,
35、and continuous means the repeated evaluation of T (once at each round). Continuous in-network evaluation of T entails addressing the following two coupled aspects of the problem: (a) the placement of the operators, variables, and constants of T to network nodes and (b) the routing of their values to
36、 the appropriate network nodes that needed them to evaluate the operators. We analyze the complexity and provide a simple and effective algorithm for the placement of the nodes of T onto the sensor nodes of a WSN. Our algorithm of operator placement attempts to minimize the total amount of data that
37、 need to be communicated. A placement of T induces a certain Maximum Lifetime Concurrent Flow (MLCF) problem. We provide an efficient algorithm that finds near-optimal integral solutions to the MLCF problem, where a solution is a collection of paths on which certain amount of integral flow is routed
38、. Our approach to the continuous in-network evaluation of T consists of utilizing both our placement and routing algorithms above.We demonstrate experimentally that our approach consistently and effectively find the maximum lifetime solutions for the continuous in-network evaluation of expression tr
39、ees in wireless sensor networks.1. IntroductionRemote monitoring applications are one of the most attractive applications of wireless sensor networks. Such applications, like environmental monitoring and building surveillance, normally have long running queries over the data streams that are continu
40、ously generated by sensors near the points of interest. For example, one such query can be found in volcano monitoring application report the current activity level every five minutes, which is measured by processing and correlating the data streams generated by sensors on surface vibration, air pre
41、ssure and temperature, gas density change, magnetic variance, and etc. How to energy efficiently process these long-running queries is a critical problem to the success of the deployment and operation of wireless sensor networks, since often replenishing the energy of the sensors by replacing their
42、batteries is cost prohibitive or even infeasible. In this paper, we consider the task of the continuous evaluation of long-running complex queries in wireless sensor networks. Such queries have multiple function-dependent operators and require repeated evaluation once per each round. Due to the disp
43、arity between the amount of data generated by the sensors and the amount of data the network can communicate before the sensors deplete their energy, we aim to push the queries into the network for processing 18. We model a query with a rooted expression directed acyclic graph (DAG) Q, whose interna
44、l nodes are operators (functions) with children as their operands, and its leaves are constants or variables. Each vertex of Q has a size for its value and a set of candidate network nodes to which it may be placed. Each variable vertex of Q has a set of source sensor nodes, whose measurements are u
45、sed to assign values to that variable. The continuous in-network evaluation of a rooted expression DAG Q entails addressing the following two aspects of the task: (a) the placement of the operators, variables, and constants of Q to network nodes, and (b) the routing of the operand values to the appr
46、opriate network nodes that needed them to evaluate the operators. These two aspects are coupled because the placement of Q imposes certain sourcedestination routing requirements among the sensor nodes, and the manner in which routing is performed can have a major impact on placement decisions.While
47、there are many important optimization goals for the continuous in-network evaluation of queries (e.g. response time, reliability, etc.), we focus on maximizing the system lifetime the time until the sensor network losses its ability to perform its intended task due to depletion of energy at (some of) its sensors, and analyze how to decouple the two aspects of the task at hand. We find, as shown in our experimental evaluation, that havi