1、原文：http:/ &nb
2、sp; 毕业设计 (论文 )外文资料翻译 学 院 ： 电子工程学院 专业班级 ： 电子信息工程 DZ 电子 083
3、 学生姓名 ： 范嘉敏 学 号： 510830310 指导教师 ： 掌明 &n
4、bsp; 外文出处 ： Ad Hoc Networks 附 件 ： 1.外文资料翻译译文； 2.外文原文 指导教师评语： 签名： &
5、nbsp; 年 月 日 &
6、nbsp; 基于 最长寿命的 无线传感器网络 连续查询处理 Konstantinos Kalpak
7、is* , Shilang Tang 计算机科学 部门 和电气工程部门 ,马里 兰 大学 ,巴尔 摩 摘要 监测应用成为无线传感器网络（ WSNS）最重要的应用之一。这类应用通常具有长期运行的复杂查询处理技术且通过传感 器流对此处理技术进行评估。 基 于无线传感器网络中传感器的 能量 有限，高效节能 查询 的 评价对于延长系统 使用 寿命来说 是 至关重要 的 使用期限指的是此网络 查询从 开始 到 停止 所 执行其预定任务的最早时间。 我们通过使用表达式树对复杂查询进行建模。我们考虑使无线传感器网络的使用期限最大化以达成表达式树 T 的持续
8、网络内评估，因此可在 基站 获得其根值。网络内评估意味着对于算符 T 的评估可能会推至网络节点且同样意味着对 T进行重复评估（每 轮一次）。持续的网络内 T 评估需要解决以下问题的两个方面：（ 1）相对于网络节点的 T 的运算符，变量和变量的放置 （ 2）以上量值对于适当网络节点的路径选择，网络节点需要使用以上量值评估运算符。 我们对其复杂性进行了分析，并且为 T 节点在 WSN 传感器节点上的放置提供了一种简单而有效的算法。我们所提出的运算符放置算法试图使总传输数据量最小化。 T 的放置可引起一定的最大使用期限并行流（ MLCF）问题。我们提供的算法可以找到解决 MLCF 问题的
9、近优积分方案，其中一种便是收集路径，一定数量的积分流被路由。我们对于 T 的持续网络内评估包括以上放置和路由算法。 实验证明，我们的做法能够一贯地、有效地找到对于无线传感网络表达式树的持续网络内评 估的最大使用期限解决方案。 2010 Elsevier B.V. All rights reserved. 1.介绍 远程监控 是 无线传感
10、器网络 最具有吸引力 的应用之一。 像 环境监测和 建筑 监测， 它们 通常 会 在 兴趣 点 处 通过 传感器 不断 的 运行查询 数据流。例如 有一种 查询应用 ，可以 在火山监测中每五分钟 报告当前活动的 情况 ，这是由于 传感器 的 加工和 相关 表面振动， 气压和温度，气体密度的变化，磁场变异 等 因素 所产生的数据流测量， 如何 让这些因素 运用在 这些查询 中并得到 长时间高 效地 成功 处理 和操作的无线传感器网络 运行 是部署的一个 重要 的问题， 有些问题不可行，是 由于 经常补充传感器 电池 的能量成本过高 。 在本文中，我们 在无线传感器网络 中 考虑 长期
11、运行复杂的查询并且对此技术
12、 进行评估 的 任务。 此类查询有 多个 运算符 依赖的 函数， 并要求每一轮每次 重复评估运算符 。 由于在 传感器 网络 中 通信前传感器 耗能 所 产生的数据量 ，我们把 目标推向 处理 网络 查询 18。 我们 的 模型 运用 非循环图 Q 且对 Q 进行详细的描述，其内部节点与 子节点 用 操作数运算符 （函数） 查询 、 它 们 的叶 用 常量或变量 表达 。 Q 的 每个顶点 都 有其 重要
13、性 且每 一组 都 可放 置 候选 网络节点。 在 Q 的每个 顶点 上 有一组源传感器节点，其用于分配 查询结果给该变量 。 在 网络 DAG 中 评价连续 Q 的 表达 根 需要解决以下两个方面的任务：（ a） 在Q 的 网络节点 上 安置 变量和常量 的运算符 ， （ b） 寻址 适合的 操作数 网络节点，需要他们来 评价 操作数 。这两 点内容是有联系的 ，因为 在 G 的布局上 某些源 到目标的路由选择 要求传感器节点之间 以何种方式 寻址 ，这对 决定 执行寻址的安置具有主要 影响 。 虽然 在网络查询 中 有许多重要的优化目标需要 连续评估（如响应时间，可
14、靠性等） 。 由于 部分传感器能耗和着手分析如何分离方面的任务 ， 我们 主要是 提高系 统 的 最大限度 寿命 - 直到传感器网络 寿命结束之前完成 其执行的预定 任务 。我们发现，在我们的实验 评估 中 显示，在路由 方面 有一个 最佳解决方案， 来 有效地分离的 路由 和安置 。 在 安置任务方面 找到 最佳 的 解决方案，我们 需要 考虑 最低 通信成本 的 位置（ MCP）。 MCP 问题是 在 Q 的 单个 评价 期间 对于已 分配 Q 的 一个或多个顶点 使其在 网络节点之间 传送数据的总量 最小化 。 MCP 问题 即使是 Q 有着成本优势并以 单位 为
15、 1 的 高度树 ，但还是 MAX SNP-hard。我们描述了一个简单而有效的贪婪启发式，我们称 之 为 GREEDYMCP 算法， 在实际显示中 证明最 佳的解决 MCP问题 的方案 可用 GREEDYMCP 算法来 实现 。 找到一个 最佳的 解决 寻址 方案 ， 是 我们解决 使用 并 行 流 最大 寿命的 （ MLCF）问题。 MLCF 问题是 并行的 流量为 给定的 一组 源 的目标提供 数据传输速率 以解决系统最大 寿命 的问题 。 我们 为 MLCF 问题 提供了一个有效的， 简单的算法 ,在网络的 n 个节点中对于 部分 源 目的地 N 为了 满足带有并行流数据通
16、信要求 ，其算法在 n + N 路径中发现了最大限度的分数阶系统寿命 To， 我们称之为ALGRSM-MLCF 的算法 。 由分数 四舍五入下来 ， 我们得到 了 一个 关于 MLCF 问题最佳并 行 流解决方案，其 a=（ To n N +1） /T。在实践中往往 To>>n+N， a 1。我们的实验表明， ALGRSM MLCF 优于现有的 寻址 算法， 但 可 在 系统的 寿命和能 耗 方面应用 MLCF 问题。 ALGRSM MLCF 是一种基于 修正单形法 (RSM) 的迭代算法。 我们在网络 中 连续 查询 Q 的 评估的 方法 有 GREEDYMCP 和 ALGRSM-MLCF 两种 。 首先， 我们使用 ALGRSM MLCF 在网络中找到 一个 Q 的位置 ， 并为路由上的所有数据值使用 ALGRSM-MLCF 来满足传达 。 我们 通过广泛的实验评估 表明 ，
