【文章內容簡介】
圖形 2 此后,我們只考慮 位置, 其中每個 客體 的頂點 都被放置 在一個主機節(jié)點上 ,即 在 主機的網絡 中 是不能復制 客體 頂點 。 考慮將客體網絡 DAG Q 放置到主機網絡 H。放置在同一主機節(jié)點的客體頂點集的候選集的交集一般非空。因此,通過消除放置在不同主機節(jié)點的客體頂點邊緣(切邊),我們能夠得到關于客體圖的連接組件的集合,這樣所有的連接組件的頂點 Vi 就被放置在同一主機節(jié)點 ui。換言之,將客體 Q放置在主機 H會引起V[Q] 的 分區(qū),這樣所有 Vi 的客體頂點將被放置在主機節(jié)點 請注意, 的每塊區(qū) Vi 是可以受理的 — 我們稱這種 分區(qū)為允許分區(qū)。此外,每一輪 Q的 評估中的傳輸數(shù)據量等于切邊的總成本,其中,切邊指的是由放置引起 的 。換言之,給定放置中 Q的單個評估所需 要的總傳輸量等于通過分區(qū) 的 Q的收縮 的總重量。事實上,從主機節(jié)點 ui至客體節(jié)點 uj所需的傳輸總量相對于 中邊緣 ViVj 的重量。確定相當于每輪評估 Q 中總傳輸總量的放置成本。通過重新標記每個頂點 ,其中 Vi 中的客體頂點被放置在主機節(jié)點 ui,從而確定放置傳輸需求圖 R 成為從 中獲取的圖。由于客體頂點放置在 和 ,邊緣 的量等于每輪從主機節(jié)點 ui 到主機節(jié)點 u 所需的總傳輸數(shù)據量。 我們 在 放置通信 節(jié)點中 定義最小 Q 到 H 上的成本 (MCP) 問題 是 為 了 尋找到 候選主機頂點上 以最低的成本 (傳送數(shù)據的量) 的 位置 。由 于 Q 安置到主機h上并且誘導 分隔 邊緣的位置,本質上 它 是 遵循的 MCP問題 等同于下面的 總 權數(shù)圖劃分問題的 。 我們 為了 約束 定義 分區(qū) ( MCCP) 最小成本 的問題,如下所示 :任何邊緣加權圖 G 和一個函數(shù) 找到 這樣 一個最低的成本切邊(邊割), 非空 為每個連接組件的 Gi 問題 實例的最佳解決方案,也是為客 體 Q 到主機 H的 MCP 問題的最佳解決方案,反之亦然。我們研究了 節(jié)的 MCP 和 MCCP 問題的復雜性。 鑒于已將客體 Q放置到主機 H,我們現(xiàn)在需要找到一種高效節(jié)能的方式以滿足傳輸需求圖 R所傳達的 數(shù)據路徑需要,從而使系統(tǒng)使用期限最大化。換言之,我們需要找到最大使用期限 T 以及滿足為收集起點 — 終點對數(shù)(邊緣) 的傳輸需求 的路徑,其中需求 等于從主機節(jié)點 Si到主機節(jié)點di的邊緣重 量(一輪中所需傳輸數(shù)據量)。這就是我們在第 5節(jié)中有考慮過的最大使用期限并行流( MLCF)問題。 在本文中,我們假設了表達式 DAGs 和 AND算法模式。同樣,我們也假設變量 v ∈ V [Q]的數(shù)據源 是單個的,因此 v 固定在其單個數(shù)據源主機網絡節(jié)點上。此外,我們假設 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