毕业设计外文翻译---基于最长寿命的无线传感器网络连续查询处理(编辑修改稿)

毕业设计外文翻译---基于最长寿命的无线传感器网络连续查询处理(编辑修改稿)内容摘要：

图形 2 此后，我们只考虑 位置， 其中每个 客体 的顶点 都被放置 在一个主机节点上 ，即 在 主机的网络 中 是不能复制 客体 顶点。 考虑将客体网络 DAG Q 放置到主机网络 H。 放置在同一主机节点的客体顶点集的候选集的交集一般非空。 因此，通过消除放置在不同主机节点的客体顶点边缘（切边），我们能够得到关于客体图的连接组件的集合，这样所有的连接组件的顶点 Vi 就被放置在同一主机节点 ui。 换言之，将客体 Q放置在主机 H会引起V[Q] 的 分区，这样所有 Vi 的客体顶点将被放置在主机节点 请注意， 的每块区 Vi 是可以受理的 — 我们称这种 分区为允许分区。 此外，每一轮 Q的 评估中的传输数据量等于切边的总成本，其中，切边指的是由放置引起 的。 换言之，给定放置中 Q的单个评估所需 要的总传输量等于通过分区 的 Q的收缩 的总重量。 事实上，从主机节点 ui至客体节点 uj所需的传输总量相对于 中边缘 ViVj 的重量。 确定相当于每轮评估 Q 中总传输总量的放置成本。 通过重新标记每个顶点 ，其中 Vi 中的客体顶点被放置在主机节点 ui，从而确定放置传输需求图 R 成为从 中获取的图。 由于客体顶点放置在 和 ，边缘 的量等于每轮从主机节点 ui 到主机节点 u 所需的总传输数据量。 我们 在 放置通信 节点中 定义最小 Q 到 H 上的成本 (MCP) 问题 是 为 了 寻找到 候选主机顶点上 以最低的成本 （传送数据的量） 的 位置。 由 于 Q 安置到主机h上并且诱导 分隔 边缘的位置，本质上 它 是 遵循的 MCP问题 等同于下面的 总 权数图划分问题的。 我们 为了 约束 定义 分区 （ MCCP） 最小成本 的问题，如下所示 ：任何边缘加权图 G 和一个函数 找到 这样 一个最低的成本切边（边割）， 非空 为每个连接组件的 Gi 问题 实例的最佳解决方案，也是为客 体 Q 到主机 H的 MCP 问题的最佳解决方案，反之亦然。 我们研究了 节的 MCP 和 MCCP 问题的复杂性。 鉴于已将客体 Q放置到主机 H，我们现在需要找到一种高效节能的方式以满足传输需求图 R所传达的 数据路径需要，从而使系统使用期限最大化。 换言之，我们需要找到最大使用期限 T 以及满足为收集起点 — 终点对数（边缘） 的传输需求 的路径，其中需求 等于从主机节点 Si到主机节点di的边缘重 量（一轮中所需传输数据量）。 这就是我们在第 5节中有考虑过的最大使用期限并行流（ MLCF）问题。 在本文中，我们假设了表达式 DAGs 和 AND算法模式。 同样，我们也假设变量 v ∈ V [Q]的数据源 是单个的，因此 v 固定在其单个数据源主机网络节点上。 此外，我们假设 Q 根固定在基 站 且 Q 的顶点放置不会 被 复制，即，对于所有的 v∈ V[Q]来说，。 并且，我们还以为 ，无论在计算运算符 v 值的时候，还是在测量和分配变量 v值的时候，或者是在配备常量 v值的时候所消耗的能源，相比于所有顶点 v ∈ V[Q]的传输所消耗的能源来说，都是不容忽视的。 外文原文 Maximum lifetime continuous query processing in wireless sensor works Konstantinos Kalpakis* , Shilang Tang Computer Science and Electrical Engineering Department, University of Maryland, Baltimore ABSTRACT Monitoring applications emerge as one of the most important applications of wireless sensor works (WSNs). Such applications typically have longrunning plex queries that are continuously evaluated 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 work can not perform its intended task anymore. We model plex queries by expression trees and consider the problem of maximizing the lifetime of a wireless sensor work for the continuous in–work evaluation of an expression trees T , so the value of its root is available at the base station. Inwork evaluation means that the evaluation of the operators of T may be pushed to the work nodes, and continuous means the repeated evaluation of T (once at each round). Continuous inwork 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 work nodes and (b) the routing of their values to the appropriate work nodes that needed them to evaluate the operators. We analyze the plexity 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 need to be municated. A placement of T induces a certain Maximum Lifetime Concurrent Flow (MLCF) problem. We provide an efficient algorithm that finds nearoptimal integral solutions to the MLCF problem, where a solution is a collection of paths on which certain amount of integral flow is routed. Our approach to the continuous inwork 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 inwork evaluation of expression trees in wireless sensor works. 1. Introduction Remote monitoring applications are one of the most attractive applications of wireless sensor works. Such applications, like environmental monitoring and building surveillance, normally have long running queries over the data streams that are continuously 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 pressure and temperature, gas density change, magic variance, and etc. How to energy efficiently process these longrunning queries is a critical problem to the success of the deployment and operation of wireless sensor works, since often replenishing the energy of the sensors by replacing their batteries is cost prohibitive or even infeasible. In this paper, we consider the task of the continuous evaluation of longrunning plex queries in wireless sensor works. Such queries have multiple functiondependent operators and require repeated evaluation once per each round. Due to the disparity between the amount of data generated by the sensors and the amount of data the work can municate before the sensors deplete their energy, we aim to push the queries into the work for processing [18]. We model a query with a rooted expression directed acyclic graph (DAG) Q, whose internal 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 work nodes to which it may be placed. Each variable vertex of Q has a set of source sensor nodes, whose measurements are used to assign values to that variable. The continuous inwork eval。