【正文】 我們 始終認為 在 無線傳感器網絡 中 對于 連續(xù) 的網絡 復雜查詢 評價 關鍵是解決最大壽命的方法 。我們的實驗表明， ALGRSM MLCF 優(yōu)于現有的 尋址 算法， 但 可 在 系統的 壽命和能 耗 方面應用 MLCF 問題。 MLCF 問題是 并行的 流量為 給定的 一組 源 的目標提供 數據傳輸速率 以解決系統最大 壽命 的問題 。 MCP 問題是 在 Q 的 單個 評價 期間 對于已 分配 Q 的 一個或多個頂點 使其在 網絡節(jié)點之間 傳送數據的總量 最小化 。 雖然 在網絡查詢 中 有許多重要的優(yōu)化目標需要 連續(xù)評估（如響應時間，可靠性等） 。 Q的 每個頂點 都 有其 重要性 且每 一組 都 可放 置 候選 網絡節(jié)點。 在本文中，我們 在無線傳感器網絡 中 考慮 長期運行復雜的查詢并且對此技術 進行評估 的 任務。 實驗證明，我們的做法能夠一貫地、有效地找到對于無線傳感網絡表達式樹的持續(xù)網絡內評 估的最大使用期限解決方案。我們所提出的運算符放置算法試圖使總傳輸數據量最小化。我們考慮使無線傳感器網絡的使用期限最大化以達成表達式樹 T 的持續(xù)網絡內評估，因此可在 基站 獲得其根值。 畢業(yè)設計 (論文 )外文資料翻譯 學 院 ： 電子工程學院 專業(yè)班級 ： 電子信息工程 DZ 電子 083 學生姓名 ： 范嘉敏 學 號： 510830310 指導教師 ： 掌明 外文出處 ： Ad Hoc Networks 附 件 ： ； 指導教師評語： 簽名： 年 月 日 基于 最長壽命的 無線傳感器網絡 連續(xù)查詢處理 Konstantinos Kalpakis* , Shilang Tang 計算機科學 部門 和電氣工程部門 ,馬里 蘭 大學 ,巴爾 摩 摘要 監(jiān)測應用成為無線傳感器網絡（ WSNS）最重要的應用之一。 我們通過使用表達式樹對復雜查詢進行建模。 我們對其復雜性進行了分析，并且為 T節(jié)點在 WSN傳感器節(jié)點上的放置提供了一種簡單而有效的算法。我們對于 T的持續(xù)網絡內評估包括以上放置和路由算法。例如 有一種 查詢應用 ，可以 在火山監(jiān)測中每五分鐘 報告當前活動的 情況 ，這是由于 傳感器 的 加工和 相關 表面振動， 氣壓和溫度，氣體密度的變化，磁場變異 等 因素 所產生的數據流測量， 如何 讓這些因素 運用在 這些查詢 中并得到 長時間高 效地 成功 處理 和操作的無線傳感器網絡 運行 是部署的一個 重要 的問題， 有些問題不可行，是 由于 經常補充傳感器 電池 的能量成本過高 。 我們 的 模型 運用 非循環(huán)圖 Q 且對 Q 進行詳細的描述，其內部節(jié)點與 子節(jié)點 用 操作數運算符 （函數） 查詢 、 它 們 的葉 用 常量或變量 表達 。這兩 點內容是有聯系的 ，因為 在 G的布局上 某些源 到目標的路由選擇 要求傳感器節(jié)點之間 以何種方式 尋址 ，這對 決定 執(zhí)行尋址的安置具有主要 影響 。 在 安置任務方面 找到 最佳 的 解決方案，我們 需要 考慮 最低 通信成本 的 位置（ MCP）。 找到一個 最佳的 解決 尋址 方案 ， 是 我們解決 使用 并 行 流 最大 壽命的 （ MLCF）問題。在實踐中往往 Ton+N， a≈ 1。 首先， 我們使用 ALGRSM MLCF 在網絡中找到 一個 Q的位置 ， 并為路由上的所有數據值使用 ALGRSMMLCF 來滿足傳達 。 總之，對于 在無線傳感器網絡（ WSNS）中 連續(xù) 處理 復雜 查詢 的 網絡 任務 ，本文 貢獻如下： ?從理論上分析 MCP 問題 的復雜性 ， 是 將無線傳感器網絡 中 放置 DAGs的 表達與最低的總通信成本的 混合在一起 。 ALGRSM MLCF 優(yōu)于現有的 尋址 方法。 我們 在 節(jié) 中 分析 復雜的 MCP 問題 ，并 表明MCP 問題對于 高度 為 1 的樹 和提供他們 限制 的頂點 是 MAX SNPhard。 2. 相關工作 pietzuch 等人 ， 考 慮 在傳統的分布式處理系統中放置網絡運算符。 Gehrke 和Madden 等人 是第一個將查詢處理和傳感器網絡集成 一體 的 ， 可以通過 傳感器網絡 很容易的 查詢 任務 。此外， 在 查詢運算符中 [11,24] 從功能角度進行建模，而且往往是相當簡單的運算符 （聚合、 篩選器等），而在工作中我們 的 模型 審議優(yōu)化的運算符 的 位置 是從 通信角度考慮的 。 他們?yōu)閭鞲衅?測量 分配指定 了 可接受公差 范圍 查詢答案 的方法 。提出并 研究 [6,8,23,28,29,31]，以數據為中心的推 挽 式查詢處理技術， 它 可以分類為兩種主要方法： 結構化和非結構化的 基于散列的數據存儲技術 [29]和 bneedle 方 法 [23]。他們提供了一個分布式的協議， 嘗試通過優(yōu)化放置 并 不斷地 在 相鄰節(jié)點 之間移動 以適應變化的數據速率 。 可以看到圖 10，我們的方法 采用 最短路徑 的路由算法在所有情況下的 最佳位置 實現了更好的壽命 。它的 LP 配方是不同 于 MLCF。 Chang 和 Tassiulas [7] 提出了一種最短路徑的路由算法用來 收集 最大壽命的 數據 從而在每個環(huán)節(jié)的每個節(jié)點處 反映通信 能耗 和剩余的能量。 Wu 等人 [32]考慮 使用一個給定的 路由 樹 來 興建發(fā)射 /接收傳感器的時間表，以收集數據 。 另一方面，我們 ALGRSM MLCF 算法不考慮沖突期間通過傳感器的傳輸 。 為簡單起見， 對于頂點 v， 我們經常寫 v∈ G，而不是 v∈ V[G] 和 對于邊緣點 ij 寫 ij∈ G，而不是 ij∈ E [G] 。 邊緣 IJ∈ E[G] 的 邊 緣收縮圖 G是從崩潰（合并） G 頂點到頂點 j 得到的圖。 進一 步 我們通過 Π定義的縮圖 G 表示 以下邊緣加權有向圖 GΠ 。 鑒于 一 實例優(yōu)化問題， opt（ I）和 sol（ I） 分別 是 最優(yōu) 和最 可行的 解決方案。 請我們參閱連續(xù)積分解決方案來優(yōu)化問題 。由于矩陣是一個 單一列 向量，許多符號 /矩陣操作自然 是 延伸的 向量 。2。一個節(jié)點 用 b表示 ， 其 被指 定為 其余 傳感器節(jié)點的基站 。時間是離散的 ， 被定義 的 數據速率 是 傳感器節(jié)點 在每 隔一段 時間內 傳輸的數據 包的數目。用它 來代替 V=﹛ 1。每當 i能成功發(fā)送一個數據包到 j，就 存在ij∈ E。 為簡單起見，我們 假設 在 每個 節(jié) 點附近的單源節(jié)點 是傳感器網絡的一個基站 。傳感器網絡同樣可以處理 由 多個基站引入 的 一個新的節(jié)點 ，作為新的單一基站，然后追加到 G，每個基站 為 I， 的新的邊緣 在本文中， 我們不考慮有關信號和信道干擾，傳輸 調度 是 為 了 避免或減少這種干擾的問題 。過去 我們 對于 復雜查詢 是在 傳感器網絡 中關于傳感器的測量 。每個頂點 v∈ V [Q]的 有關 值不變，但不同的 尺寸 大?。?V）是 衡量 單位數據包大小 的 。 表達的 DAG 出現在各個領域，如 TinyDB 的 SQL 連續(xù) 查詢評價 選擇樓層，房間， AVG（溫度） 來自 傳感器 地板 6 房間地板 AVG（溫度） 70 采樣周期 30 秒 。在一 個命令的程序中評價 （可能不是全部） 運算符，使其根值提供提供給用戶。 為了評估在主機 h 中的 客 體 Q， 我們需要 在 一個或多個主機節(jié)點 上 放置 所有客 體 頂點 。每當一個頂點 v∈ V[Q]必要的 時候 ，一個主機節(jié)點 要求 被 提供 ， 這樣做可能需要檢測或 計算 網絡節(jié)點 i，甚至 是 計算 i 和其他主機的網絡之間的通信節(jié)點。因此，通過消除放置在不同主機節(jié)點的客體頂點邊緣（切邊），我們能夠得到關于客體圖的連接組件的集合，這樣所有的連接組件的頂點 Vi 就被放置在同一主機節(jié)點 ui。事實上，從主機節(jié)點 ui至客體節(jié)點 uj所需的傳輸總量相對于 中邊緣 ViVj 的重量。 我們 在 放置通信 節(jié)點中 定義最小 Q 到 H 上的成本 (MCP) 問題 是 為 了 尋找到 候選主機頂點上 以最低的成本 （傳送數據的量） 的 位置 。 鑒于已將客體 Q放置到主機 H，我們現在需要找到一種高效節(jié)能的方式以滿足傳輸需求圖 R所傳達的 數據路徑需要，從而使系統使用期限最大化。同樣，我們也假設變量 v ∈ V [Q]的數據源 是單個的，因此 v 固定在其單個數據源主機網絡節(jié)點上。theoretically analyze the plexity of the MCP problem, the problem of placing expression DAGs on WSNs with minimum total munication cost. our approach, consisting of using GREEDYMCP and ALGRSMMLCF together is both effective and efficient at maximizing the system lifetime. The rest of the paper is organized as follows. We review related work in Section 2 , and then in Section 3 we give the necessary preliminaries. We describe our GREEDYMCP algorithm for the placement of expression DAGs into WSNs in Section 4, and show that GREEDYMCP finds optimal solutions to MCP problem instances under certain conditions . We analyze the plexity of the MCP problem in Section and show that the MCP problem is MAX SNPhard even for trees of height 1 and unit cost edged provided they have restricted vertices. We then turn our attention to the routing of operands, and we present our ALGRSMMLCF algorithm for the MLCF problem in Section 5. We discuss the results from our experimental evaluation of the proposed approach in Section 6. We conclude in Section 7. 2. Related work Pietzuch et al. [26] consider workaware operator placement in conventional distributed stream processing systems. In similar work settings, Ahmad et al. [1] give three operator placement algorithms for constructing a query processing overlay work and pare their performance. Th