电子信息工程无线传感器中英文对照外文翻译文献

中英文对照外文翻译文献

(文档含英文原文和中文翻译)

基于最长寿命的无线传感器网络连续查询处理

摘要

监测应用成为无线传感器网络（WSNS）最重要的应用之一。这类应用通常具有长期运行的复杂查询处理技术且通过传感器流对此处理技术进行评估。基于无线传感器网络中传感器的能量有限，高效节能查询的评价对于延长系统使用寿命来说是至关重要的—使用期限指的是此网络查询从开始到停止所执行其预定任务的最早时间。

我们通过使用表达式树对复杂查询进行建模。我们考虑使无线传感器网络的使用期限最大化以达成表达式树T的持续网络内评估，因此可在基站获得其根值。网络内评估意味着对于算符T的评估可能会推至网络节点且同样意味着对T进行重复评估（每轮一次）。持续的网络内T评估需要解决以下问题的两个方面：（1）相对于网络节点的T的运算符，变量和变量的放置（2）以上量值对于适当网络节点的路径选择，网络节点需要使用以上量值评估运算符。

我们对其复杂性进行了分析，并且为T节点在WSN传感器节点上的放置提供

了一种简单而有效的算法。我们所提出的运算符放置算法试图使总传输数据量最小化。T的放置可引起一定的最大使用期限并行流（MLCF）问题。我们提供的算法可以找到解决MLCF问题的近优积分方案，其中一种便是收集路径，一定数量的积分流被路由。我们对于T的持续网络内评估包括以上放置和路由算法。

实验证明，我们的做法能够一贯地、有效地找到对于无线传感网络表达式树的持续网络内评估的最大使用期限解决方案。

2010 Elsevier B.V. All rights reserved. 1.介绍

远程监控是无线传感器网络最具有吸引力的应用之一。像环境监测和建筑监测，它们通常会在兴趣点处通过传感器不断的运行查询数据流。例如有一种查询应用，可以在火山监测中每五分钟报告当前活动的情况，这是由于传感器的加工和相关表面振动，气压和温度，气体密度的变化，磁场变异等因素所产生的数据流测量，如何让这些因素运用在这些查询中并得到长时间高效地成功处理和操作的无线传感器网络运行是部署的一个重要的问题，有些问题不可行，是由于经常补充传感器电池的能量成本过高。

在本文中，我们在无线传感器网络中考虑长期运行复杂的查询并且对此技术进行评估的任务。此类查询有多个运算符依赖的函数，并要求每一轮每次重复评估运算符。由于在传感器网络中通信前传感器耗能所产生的数据量，我们把目标推向处理网络查询 [18]。我们的模型运用非循环图Q且对Q进行详细的描述，其内部节点与子节点用操作数运算符 （函数）查询、它们的叶用常量或变量表达。Q的每个顶点都有其重要性且每一组都可放置候选网络节点。在Q的每个顶点上有一组源传感器节点，其用于分配查询结果给该变量。

在网络DAG中评价连续Q的表达根需要解决以下两个方面的任务：（a）在Q的网络节点上安置变量和常量的运算符，（b）寻址适合的操作数网络节点，需要他们来评价操作数。这两点内容是有联系的，因为在G的布局上某些源到目标的路由选择要求传感器节点之间以何种方式寻址，这对决定执行寻址的安置具有主要影响。

虽然在网络查询中有许多重要的优化目标需要连续评估（如响应时间，可靠性等）。由于部分传感器能耗和着手分析如何分离方面的任务，我们主要是提高系统的最大限度寿命 - 直到传感器网络寿命结束之前完成其执行的预定任务。我们发现，在我们的实验评估中显示，在路由方面有一个最佳解决方案，来有效地分离的路由和安置。

在安置任务方面找到最佳的解决方案，我们需要考虑最低通信成本的位置（MCP）。MCP 问题是在Q的单个评价期间对于已分配Q的一个或多个顶点使其在网络节点之间传送数据的总量最小化。MCP问题即使是Q有着成本优势并

以单位为1的高度树，但还是MAX SNP-hard。我们描述了一个简单而有效的贪婪启发式，我们称之为GREEDYMCP算法，在实际显示中证明最佳的解决MCP问题的方案可用GREEDYMCP算法来实现。

找到一个最佳的解决寻址方案，是我们解决使用并行流最大寿命的（MLCF）问题。MLCF问题是并行的流量为给定的一组源的目标提供数据传输速率以解决系统最大寿命的问题。我们为MLCF问题提供了一个有效的，简单的算法,在网络的n个节点中对于部分源目的地N为了满足带有并行流数据通信要求，其算法在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来满足传达。我们通过广泛的实验评估表明，我们始终认为在无线传感器网络中对于连续的网络复杂查询评价关键是解决最大寿命的方法。虽然我们采取统一的方式来解决手头的任务，我们只需要两个网络元数据—网络拓扑结构和传感器的初始能量，这是对其它许多网络任务都非常有用的知识。请注意，通过我们的方法发现小规模的路由解决方案在传感器中间接的限制了分配路由信息。

总之，对于在无线传感器网络（WSNS）中连续处理复杂查询的网络任务，本文贡献如下：

?从理论上分析MCP问题的复杂性，是将无线传感器网络中放置DAGs的表达与最低的总通信成本的混合在一起。

?为MCP的问题提供贪婪启发式GREEDYMCP。GREEDYMCP在实际应用情况下发现并证明最佳的解决方案。

?提供一个简单而有效的ALGRSM-MLCF算法，它会在无线传感器网络中发现最接近整数解来解决最大生命周期并行流（MLCF）问题的方案。 ALGRSM MLCF优于现有的寻址方法。

?关于MLCF 问题我们发现放置去耦和即将开始的路由任务都有效

?我们使用GREEDYMCP和ALGRSMMLCF方法来最大限度地有效的提高系统的寿命。

本文的其余部分安排如下：我们在第2节中回顾相关工作，然后在第3节，我们给予必要的准备工作。我们在第4节中表达描述DAGs中安置的无线传感器网络的GREEDYMCP算法，在一定的MCP问题实例条件下，用GREEDYMCP

算法证明找到最佳的解决方案。我们在 4.2 节中分析复杂的MCP问题，并表明MCP 问题对于高度为 1 的树和提供他们限制的顶点是MAX SNP-hard。然后，我们把注意力放在操作数的寻址上，我们在第5节中提出MLCF问题的ALGRSM-MLCF算法。我们在第6节中提出实验方法的评估并描述了结果。在第7节我们得出结论。 2. 相关工作

pietzuch等人，考虑在传统的分布式处理系统中放置网络运算符。在类似的网络设置中，Ahmad等人，在覆盖的网络中用放置的三个运算符算法构造查询处理并比较其每一个性能。他们认为由节点组成的网络具有互联网的风格，且有足够的计算能力，它不同于我们所研究的有限能量的无线传感器网络。

在无线传感器网络中，由于Intanagonwiwat等人在一定的背景下，网络处理的概念被首次引入，在定向扩散中以投机性取巧的方式消除重复。Gehrke和Madden等人是第一个将查询处理和传感器网络集成一体的，可以通过传感器网络很容易的查询任务。在美洲狮项目中，有人建议在传感器网络中以传感器数据分层结构管理作为一个分布式数据库系统。在TinyDB中，无线传感器网络被提出引入查询处理的框架用来从事时间地点分发，往往是在无线传感器网络中采样数据和传递数据。解决能源利用效率是考虑问题的主要因素之一，但不是解决最大系统寿命的目标。此外，在查询运算符中 [11,24] 从功能角度进行建模，而且往往是相当简单的运算符 （聚合、 筛选器等），而在工作中我们的模型审议优化的运算符的位置是从通信角度考虑的。

Ren等人，考虑在简单的聚合查询中进行质量感知处理（如在感兴趣的矩形区域中计算传感器测量平均，最小，最大值）。他们提出了集中式的算法，找到传感器使用无功路由到基站计算概率的答案来收集其测量的子集。Hu 等人扩大了Olston和Widom的工作，提出了连续聚合查询（总和，平均，计数等）的近似答案的问题。他们为传感器测量分配指定了可接受公差范围查询答案的方法。如果它超出公差范围，之后传感器将在基站中测量。这在许多方面与我们的不同：我们只考虑除了最小值、 最大值、 平均值以外的带有各类运算符的复杂查询、 并直接提供准确的解答查询、寻求优化系统的寿命。

许多研究者都主张使用以数据为中心的技术，允许网络高效的存储和已命名的数据使用检索查询 [16]。提出并研究 [6,8,23,28,29,31]，以数据为中心的推挽式查询处理技术，它可以分类为两种主要方法：结构化和非结构化的基于散列的数据存储技术 [29]和comb-needle方法[23]。Kapadia和Krishnamachari [20]目前在单接收器方栅传感器网络中（所有类型和任意一个型）运用数学基础分析比较这两种类型一次性查询的方法，后来，Ahn和Krishnamachari [2]发现，以数据为中心的传感器网络性能的伸缩性取决于能源和存储资源是否增加，并发

现在特定应用程序中更多的节点生成查询负载。

Bonfils等人[5]考虑在传感器网络中查询运算符节点的位置，以尽量减少评估这种表达树的总通信成本。对于任何父-子查询树中的运算符，用一个节点诱导通信成本，然而这些运算符的放置和数据传输速率与从子到其父之间的最短路径是相关的。他们提供了一个分布式的协议，尝试通过优化放置并不断地在相邻节点之间移动以适应变化的数据速率。不认为是通过移动相邻节点所产生的交换信号形成[5]。我们ALGRSM MLCF算法不同于他们，我们算法是让数据通过多条路径寻求优化系统寿命的，而不是通过单一路径来寻求通信总成本的。限制母与父之间的数据单个路径的寻址，而在不利影响使用寿命的情况下允许多个路径的寻址。可以看到图10，我们的方法采用最短路径的路由算法在所有情况下的最佳位置实现了更好的寿命。

Srivastava等人 [30]考虑有层次结构的放置网络节点，逐步增加计算能力和网络宽带，这样能使总成本的计算和通讯最小化。我们假设在一个不同的网络模型中的传感器的能量是受限均匀的且有不同的目标和优化系统的寿命，这并不一定减少总成本的计算和通信。

Garg和Konemann[14]描述了一种接近并行流问题的迭代算法并最大限度的得到求解证明。它的LP 配方是不同于MLCF。他们的目标是最大限度地提高网络下边缘有限总流量的容量，而我们是最大限度地提高网络有限寿命和节点能量。此外，我们的 ALGRSM MLCF 算法在解决方案中是以路由的路径数量为界的，而在算法[14]中发现解决方案，它们可以使用任意多个路由路径作为迭代次数。因为有少部分路由路径是重要的，所以在实践中部分因为分发到传感器中，而且相关的路由信息的使用保持较小，有较少的路径。

Chang和 Tassiulas [7] 提出了一种最短路径的路由算法用来收集最大寿命的数据从而在每个环节的每个节点处反映通信能耗和剩余的能量。虽然他们还制订了一个线性规划的路由问题，他们通过其拟议的算法来获得寿命与现实的寿命进行比较。我们制定的最优路径问题不同于线性规划，我们的 ALGRSM MLCF 算法有效地直接的解决了 LP以获得最佳路由。此外，在算法[7]的性能中是主要依赖参数所使用的算法，而ALGRSM MLCF是 非参数的。

Wu等人[32]考虑使用一个给定的路由树来兴建发射/接收传感器的时间表，以收集数据。他们描述了发送和接收槽的分配，减少传输过程中的碰撞，以及使用传感器的方法。这项工作对我们的工作是有帮助的。Wu等人[32]只是假设一个路由树，而我们的方法可在连续查询的评估中构建了一个安置和路由。另一方面，我们ALGRSM MLCF算法不考虑冲突期间通过传感器的传输。推导详细的发送/接收安排位置/路由表也是重要的，他们的方法可能是一个步骤一个目标。 3. 准备工作