【正文】 畢業(yè)設(shè)計(jì) (論文 )外文資料翻譯 學(xué) 院 ： 電子工程學(xué)院 專業(yè)班級(jí) ： 電子信息工程 DZ 電子 083 學(xué)生姓名 ： 范嘉敏 學(xué) 號(hào)： 510830310 指導(dǎo)教師 ： 掌明 外文出處 ： Ad Hoc Networks 附 件 ： ； 指導(dǎo)教師評(píng)語： 簽名： 年 月 日 基于 最長壽命的 無線傳感器網(wǎng)絡(luò) 連續(xù)查詢處理 Konstantinos Kalpakis* , Shilang Tang 計(jì)算機(jī)科學(xué) 部門 和電氣工程部門 ,馬里 蘭 大學(xué) ,巴爾 摩 摘要 監(jiān)測(cè)應(yīng)用成為無線傳感器網(wǎng)絡(luò)（ WSNS）最重要的應(yīng)用之一。這類應(yīng)用通常具有長期運(yùn)行的復(fù)雜查詢處理技術(shù)且通過傳感 器流對(duì)此處理技術(shù)進(jìn)行評(píng)估。 基 于無線傳感器網(wǎng)絡(luò)中傳感器的 能量 有限，高效節(jié)能 查詢 的 評(píng)價(jià)對(duì)于延長系統(tǒng) 使用 壽命來說 是 至關(guān)重要 的 — 使用期限指的是此網(wǎng)絡(luò) 查詢從 開始 到 停止 所 執(zhí)行其預(yù)定任務(wù)的最早時(shí)間。 我們通過使用表達(dá)式樹對(duì)復(fù)雜查詢進(jìn)行建模。我們考慮使無線傳感器網(wǎng)絡(luò)的使用期限最大化以達(dá)成表達(dá)式樹 T 的持續(xù)網(wǎng)絡(luò)內(nèi)評(píng)估，因此可在 基站 獲得其根值。網(wǎng)絡(luò)內(nèi)評(píng)估意味著對(duì)于算符 T的評(píng)估可能會(huì)推至網(wǎng)絡(luò)節(jié)點(diǎn)且同樣意味著對(duì) T進(jìn)行重復(fù)評(píng)估（每 輪一次）。持續(xù)的網(wǎng)絡(luò)內(nèi) T評(píng)估需要解決以下問題的兩個(gè)方面：（ 1）相對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)的 T的運(yùn)算符，變量和變量的放置 （ 2）以上量值對(duì)于適當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)的路徑選擇，網(wǎng)絡(luò)節(jié)點(diǎn)需要使用以上量值評(píng)估運(yùn)算符。 我們對(duì)其復(fù)雜性進(jìn)行了分析，并且為 T節(jié)點(diǎn)在 WSN傳感器節(jié)點(diǎn)上的放置提供了一種簡(jiǎn)單而有效的算法。我們所提出的運(yùn)算符放置算法試圖使總傳輸數(shù)據(jù)量最小化。 T 的放置可引起一定的最大使用期限并行流（ MLCF）問題。我們提供的算法可以找到解決 MLCF 問題的近優(yōu)積分方案，其中一種便是收集路徑，一定數(shù)量的積分流被路由。我們對(duì)于 T的持續(xù)網(wǎng)絡(luò)內(nèi)評(píng)估包括以上放置和路由算法。 實(shí)驗(yàn)證明，我們的做法能夠一貫地、有效地找到對(duì)于無線傳感網(wǎng)絡(luò)表達(dá)式樹的持續(xù)網(wǎng)絡(luò)內(nèi)評(píng) 估的最大使用期限解決方案。 2020 Elsevier . All rights reserved. 遠(yuǎn)程監(jiān)控 是 無線傳感器網(wǎng)絡(luò) 最具有吸引力 的應(yīng)用之一。 像 環(huán)境監(jiān)測(cè)和 建筑 監(jiān)測(cè)， 它們 通常 會(huì) 在 興趣 點(diǎn) 處 通過 傳感器 不斷 的 運(yùn)行查詢 數(shù)據(jù)流。例如 有一種 查詢應(yīng)用 ，可以 在火山監(jiān)測(cè)中每五分鐘 報(bào)告當(dāng)前活動(dòng)的 情況 ，這是由于 傳感器 的 加工和 相關(guān) 表面振動(dòng)， 氣壓和溫度，氣體密度的變化，磁場(chǎng)變異 等 因素 所產(chǎn)生的數(shù)據(jù)流測(cè)量， 如何 讓這些因素 運(yùn)用在 這些查詢 中并得到 長時(shí)間高 效地 成功 處理 和操作的無線傳感器網(wǎng)絡(luò) 運(yùn)行 是部署的一個(gè) 重要 的問題， 有些問題不可行，是 由于 經(jīng)常補(bǔ)充傳感器 電池 的能量成本過高 。 在本文中，我們 在無線傳感器網(wǎng)絡(luò) 中 考慮 長期運(yùn)行復(fù)雜的查詢并且對(duì)此技術(shù) 進(jìn)行評(píng)估 的 任務(wù)。 此類查詢有 多個(gè) 運(yùn)算符 依賴的 函數(shù)， 并要求每一輪每次 重復(fù)評(píng)估運(yùn)算符 。 由于在 傳感器 網(wǎng)絡(luò) 中 通信前傳感器 耗能 所 產(chǎn)生的數(shù)據(jù)量 ，我們把 目標(biāo)推向 處理 網(wǎng)絡(luò) 查詢 [18]。 我們 的 模型 運(yùn)用 非循環(huán)圖 Q 且對(duì) Q 進(jìn)行詳細(xì)的描述，其內(nèi)部節(jié)點(diǎn)與 子節(jié)點(diǎn) 用 操作數(shù)運(yùn)算符 （函數(shù)） 查詢 、 它 們 的葉 用 常量或變量 表達(dá) 。 Q的 每個(gè)頂點(diǎn) 都 有其 重要性 且每 一組 都 可放 置 候選 網(wǎng)絡(luò)節(jié)點(diǎn)。 在 Q的每個(gè) 頂點(diǎn) 上 有一組源傳感器節(jié)點(diǎn)，其用于分配 查詢結(jié)果給該變量 。 在 網(wǎng)絡(luò) DAG 中 評(píng)價(jià)連續(xù) Q的 表達(dá) 根 需要解決以下兩個(gè)方面的任務(wù)：（ a） 在Q的 網(wǎng)絡(luò)節(jié)點(diǎn) 上 安置 變量和常量 的運(yùn)算符 ， （ b） 尋址 適合的 操作數(shù) 網(wǎng)絡(luò)節(jié)點(diǎn)，需要他們來 評(píng)價(jià) 操作數(shù) 。這兩 點(diǎn)內(nèi)容是有聯(lián)系的 ，因?yàn)?在 G的布局上 某些源 到目標(biāo)的路由選擇 要求傳感器節(jié)點(diǎn)之間 以何種方式 尋址 ，這對(duì) 決定 執(zhí)行尋址的安置具有主要 影響 。 雖然 在網(wǎng)絡(luò)查詢 中 有許多重要的優(yōu)化目標(biāo)需要 連續(xù)評(píng)估（如響應(yīng)時(shí)間，可靠性等） 。 由于 部分傳感器能耗和著手分析如何分離方面的任務(wù) ， 我們 主要是 提高系 統(tǒng) 的 最大限度 壽命 直到傳感器網(wǎng)絡(luò) 壽命結(jié)束之前完成 其執(zhí)行的預(yù)定 任務(wù) 。我們發(fā)現(xiàn)，在我們的實(shí)驗(yàn) 評(píng)估 中 顯示，在路由 方面 有一個(gè) 最佳解決方案， 來 有效地分離的 路由 和安置 。 在 安置任務(wù)方面 找到 最佳 的 解決方案，我們 需要 考慮 最低 通信成本 的 位置（ MCP）。 MCP 問題是 在 Q 的 單個(gè) 評(píng)價(jià) 期間 對(duì)于已 分配 Q 的 一個(gè)或多個(gè)頂點(diǎn) 使其在 網(wǎng)絡(luò)節(jié)點(diǎn)之間 傳送數(shù)據(jù)的總量 最小化 。 MCP 問題 即使是 Q 有著成本優(yōu)勢(shì)并以 單位 為 1 的 高度樹 ，但還是 MAX SNPhard。我們描述了一個(gè)簡(jiǎn)單而有效的貪婪啟發(fā)式，我們稱 之 為 GREEDYMCP 算法， 在實(shí)際顯示中 證明最 佳的解決 MCP問題 的方案 可用 GREEDYMCP 算法來 實(shí)現(xiàn) 。 找到一個(gè) 最佳的 解決 尋址 方案 ， 是 我們解決 使用 并 行 流 最大 壽命的 （ MLCF）問題。 MLCF 問題是 并行的 流量為 給定的 一組 源 的目標(biāo)提供 數(shù)據(jù)傳輸速率 以解決系統(tǒng)最大 壽命 的問題 。 我們 為 MLCF 問題 提供了一個(gè)有效的， 簡(jiǎn)單的算法 ,在網(wǎng)絡(luò)的 n個(gè)節(jié)點(diǎn)中對(duì)于 部分 源 目的地 N 為了 滿足帶有并行流數(shù)據(jù)通信要求 ，其算法在 n + N 路徑中發(fā)現(xiàn)了最大限度的分?jǐn)?shù)階系統(tǒng)壽命 To， 我們稱之為ALGRSMMLCF 的算法 。 由分?jǐn)?shù) 四舍五入下來 ， 我們得到 了 一個(gè) 關(guān)于 MLCF 問題最佳并 行 流解決方案，其 a=（ To — n— N +1） /T。在實(shí)踐中往往 Ton+N， a≈ 1。我們的實(shí)驗(yàn)表明， ALGRSM MLCF 優(yōu)于現(xiàn)有的 尋址 算法， 但 可 在 系統(tǒng)的 壽命和能 耗 方面應(yīng)用 MLCF 問題。 ALGRSM MLCF 是一種基于 修正單形法 (RSM) 的迭代算法。 我們?cè)诰W(wǎng)絡(luò) 中 連續(xù) 查詢 Q 的 評(píng)估的 方法 有 GREEDYMCP 和 ALGRSMMLCF 兩種 。 首先， 我們使用 ALGRSM MLCF 在網(wǎng)絡(luò)中找到 一個(gè) Q的位置 ， 并為路由上的所有數(shù)據(jù)值使用 ALGRSMMLCF 來滿足傳達(dá) 。 我們 通過廣泛的實(shí)驗(yàn)評(píng)估 表明 ， 我們 始終認(rèn)為 在 無線傳感器網(wǎng)絡(luò) 中 對(duì)于 連續(xù) 的網(wǎng)絡(luò) 復(fù)雜查詢 評(píng)價(jià) 關(guān)鍵是解決最大壽命的方法 。 雖然我們采取 統(tǒng)一 的 方式來解決手頭的 任務(wù) ， 我們只需要兩個(gè)網(wǎng)絡(luò)元數(shù)據(jù) — 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和 傳感器的初始能量 ，這 是 對(duì) 其 它 許多網(wǎng)絡(luò)任務(wù) 都 非常有用 的 知識(shí) 。請(qǐng)注意， 通過我們的方法發(fā)現(xiàn) 小規(guī)模的路由解決方案 在 傳感器 中 間接的 限制了 分配路由信息 。 總之，對(duì)于 在無線傳感器網(wǎng)絡(luò)（ WSNS）中 連續(xù) 處理 復(fù)雜 查詢 的 網(wǎng)絡(luò) 任務(wù) ，本文 貢獻(xiàn)如下： ?從理論上分析 MCP 問題 的復(fù)雜性 ， 是 將無線傳感器網(wǎng)絡(luò) 中 放置 DAGs的 表達(dá)與最低的總通信成本的 混合在一起 。 ?為 MCP 的問題 提供貪婪啟發(fā)式 GREEDYMCP。 GREEDYMCP 在實(shí)際應(yīng)用情況下 發(fā)現(xiàn) 并 證明最佳的解決方案。 ?提供一個(gè)簡(jiǎn)單而有效的 ALGRSMMLCF 算法 ， 它會(huì) 在 無線傳感器網(wǎng)絡(luò) 中發(fā)現(xiàn)最接近整數(shù)解 來解決 最大生命周期 并 行 流（ MLCF）問題的 方案。 ALGRSM MLCF 優(yōu)于現(xiàn)有的 尋址 方法。 ?關(guān)于 MLCF 問題 我們發(fā)現(xiàn)放置 去耦 和 即將開始的路由任務(wù) 都有效 ?我們 使用 GREEDYMCP 和 ALGRSMMLCF 方法 來 最大限度地 有效的 提高系統(tǒng)的壽命。 本文的其余部分安排如下：我們?cè)诘?2節(jié) 中 回顧 相關(guān)工作，然后在第 3節(jié)，我們 給予必要的準(zhǔn)備工作 。我們?cè)诘?4節(jié) 中 表達(dá) 描述 DAGs 中 安置 的 無線傳感器網(wǎng)絡(luò)的 GREEDYMCP 算法， 在一定 的 MCP 問題實(shí)例條件下 ，用 GREEDYMCP算法 證明找到最佳的解決方案 。 我們 在 節(jié) 中 分析 復(fù)雜的 MCP 問題 ，并 表明MCP 問題對(duì)于 高度 為 1 的樹 和提供他們 限制 的頂點(diǎn) 是 MAX SNPhard。 然后，我們把注意力放在操作數(shù)的 尋址上 ，我們 在第 5 節(jié)中 提出 MLCF 問題 的ALGRSMMLCF 算法。我們?cè)诘?6 節(jié)中 提出實(shí)驗(yàn) 方法的 評(píng)估 并描述了 結(jié)果。在第 7 節(jié) 我們得出結(jié)論 。 2. 相關(guān)工作 pietzuch 等人 ， 考 慮 在傳統(tǒng)的分布式處理系統(tǒng)中放置網(wǎng)絡(luò)運(yùn)算符。 在類似的網(wǎng)絡(luò)設(shè)置 中 ， Ahmad 等 人，在 覆蓋的 網(wǎng)絡(luò) 中 用 放置 的 三個(gè)運(yùn)算符算法 構(gòu)造查詢處理 并比較其 每一個(gè) 性能 。他們認(rèn)為 由節(jié)點(diǎn)組成的 網(wǎng)絡(luò) 具有 互聯(lián)網(wǎng)的風(fēng)格， 且有 足夠的計(jì)算能力 ， 它不同于 我們所研究的 有限能量 的 無線傳感器網(wǎng)絡(luò) 。 在 無線傳感器網(wǎng)絡(luò)中， 由 于 Intanagonwiwat 等 人 在 一定的 背景下 ， 網(wǎng)絡(luò)處理的概念被首次引入， 在定向擴(kuò)散中 以投機(jī) 性 取巧的方式 消除重復(fù)。 Gehrke 和Madden 等人 是第一個(gè)將查詢處理和傳感器網(wǎng)絡(luò)集成 一體 的 ， 可以通過 傳感器網(wǎng)絡(luò) 很容易的 查詢 任務(wù) 。 在美洲獅項(xiàng) 目 中 ， 有人 建議 在 傳感器網(wǎng)絡(luò) 中以傳感器數(shù)據(jù)分層 結(jié)構(gòu) 管理作為一個(gè)分布式數(shù)據(jù)庫系統(tǒng) 。在 TinyDB 中 ， 無線傳感器網(wǎng)絡(luò) 被提 出 引入 查詢處理的框架 用來從事時(shí)間地點(diǎn)分發(fā) ，往往是 在 無線傳感器網(wǎng)絡(luò)中 采樣數(shù)據(jù) 和 傳遞 數(shù)據(jù)。 解決能源 利用 效率是考慮 問題 的主要因素之一， 但不是 解決最大系統(tǒng)壽命 的目標(biāo)。此外， 在 查詢運(yùn)算符中 [11,24] 從功能角度進(jìn)行建模，而且往往是相當(dāng)簡(jiǎn)單的運(yùn)算符 （聚合、 篩選器等），而在工作中我們 的 模型 審議優(yōu)化的運(yùn)算符 的 位置 是從 通信角度考慮的 。 Ren 等 人， 考慮 在 簡(jiǎn)單的聚合查詢 中進(jìn)行 質(zhì)量感知 處理 （如 在感興趣的 矩形區(qū)域中 計(jì)算 傳感器測(cè)量 平均， 最小，最大 值 ）。 他們提出了 集中式的算法， 找到傳感器使用無功路由到基站計(jì)算 概率 的答案 來 收集其測(cè)量的子集。 Hu 等人 擴(kuò)大了 Olston 和 Widom的工作， 提出了 連續(xù)聚合查詢（總和，平均，計(jì)數(shù)等）的近似答案的問題。 他們?yōu)閭鞲衅?測(cè)量 分配指定 了 可接受公差 范圍 查詢答案 的方法 。如果它超出公 差范圍 ， 之后 傳感器 將在 基站 中 測(cè)量 。 這 在許多方面與我們的不同：我們 只 考慮 除了 最小值、 最大 值 、 平均值以外的帶有各類運(yùn)算符的復(fù)雜 查詢、 并直接 提供準(zhǔn)確的解答查詢 、 尋求優(yōu)化系統(tǒng)的 壽命 。 許多研究者都主張使用 以 數(shù)據(jù)為 中心的技術(shù)，允許網(wǎng)絡(luò) 高效的 存儲(chǔ)和已命名的數(shù)據(jù)使用 檢索 查詢 [16]。提出并 研究 [6,8,23,28,29,31]，以數(shù)據(jù)為中心的推 挽 式查詢處理技術(shù)， 它 可以分類為兩種主要方法： 結(jié)構(gòu)化和非結(jié)構(gòu)化的 基于散列的數(shù)據(jù)存儲(chǔ)技術(shù) [29]和 bneedle 方 法 [23]。 Kapadia 和 Krishnamachari [20]目前 在 單接收器 方柵 傳感器網(wǎng)絡(luò)中 （所有類型和任意 一個(gè) 型） 運(yùn)用數(shù)學(xué)基礎(chǔ)分析 比較這兩種 類型一次性查詢的 方法，后來， Ahn 和 Krishnamachari [2]發(fā)現(xiàn)，以數(shù)據(jù)為中心的