畢業(yè)設(shè)計(jì)外文翻譯---基于最長壽命的無線傳感器網(wǎng)絡(luò)連續(xù)查詢處理(共26頁)

1、PAGE 畢業(yè)設(shè)計(jì)(b y sh j)(論文(lnwn)外文資料(zlio)翻譯學(xué) 院： 電子工程學(xué)院 專業(yè)班級： 電子信息工程 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 外文出處： Ad Hoc Networks 附 件：1.外文資料翻譯譯文； 2.外文原文 指導(dǎo)教師評語：簽名： 年 月 日基于(jy)最長壽命的無線傳感器網(wǎng)絡(luò)連續(xù)查詢處理Konstantinos Kalpakis* , Shilang Tang計(jì)算機(jī)科學(xué)部門(bmn)和電氣工程部門,馬里蘭大學(xué),巴爾摩摘要(zhiyo)監(jiān)測應(yīng)用成為無線傳感器網(wǎng)絡(luò)（WSNS）最重要的應(yīng)用之一。這類應(yīng)用通常具有長期運(yùn)行的復(fù)雜查詢處理技術(shù)且通過傳感器流對此

2、處理技術(shù)進(jìn)行評估。基于無線傳感器網(wǎng)絡(luò)中傳感器的能量有限，高效節(jié)能查詢的評價(jià)對于延長系統(tǒng)使用壽命來說是至關(guān)重要的使用期限指的是此網(wǎng)絡(luò)查詢從開始到停止所執(zhí)行其預(yù)定任務(wù)的最早時(shí)間。我們通過使用表達(dá)式樹對復(fù)雜查詢進(jìn)行建模。我們考慮使無線傳感器網(wǎng)絡(luò)的使用期限最大化以達(dá)成表達(dá)式樹T的持續(xù)網(wǎng)絡(luò)內(nèi)評估，因此可在基站獲得其根值。網(wǎng)絡(luò)內(nèi)評估意味著對于算符T的評估可能會推至網(wǎng)絡(luò)節(jié)點(diǎn)且同樣意味著對T進(jìn)行重復(fù)評估（每輪一次）。持續(xù)的網(wǎng)絡(luò)內(nèi)T評估需要解決以下問題的兩個(gè)方面：（1）相對于網(wǎng)絡(luò)節(jié)點(diǎn)的T的運(yùn)算符，變量和變量的放置（2）以上量值對于適當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)的路徑選擇，網(wǎng)絡(luò)節(jié)點(diǎn)需要使用以上量值評估運(yùn)算符。我們對其復(fù)雜性進(jìn)行了分

3、析，并且為T節(jié)點(diǎn)在WSN傳感器節(jié)點(diǎn)上的放置提供了一種簡單而有效的算法。我們所提出的運(yùn)算符放置算法試圖使總傳輸數(shù)據(jù)量最小化。T的放置可引起一定的最大使用期限并行流（MLCF）問題。我們提供的算法可以找到解決MLCF問題的近優(yōu)積分方案，其中一種便是收集路徑，一定數(shù)量的積分流被路由。我們對于T的持續(xù)網(wǎng)絡(luò)內(nèi)評估包括以上放置和路由算法。實(shí)驗(yàn)證明，我們的做法能夠一貫地、有效地找到對于無線傳感網(wǎng)絡(luò)表達(dá)式樹的持續(xù)網(wǎng)絡(luò)內(nèi)評估的最大使用期限解決方案。 2010 Elsevier B.V. All rights reserved.1.介紹遠(yuǎn)程監(jiān)控是無線傳感器網(wǎng)絡(luò)最具有吸引力的應(yīng)用之一。像環(huán)境監(jiān)測和建筑監(jiān)測，它們通常

4、會在興趣點(diǎn)處通過傳感器不斷的運(yùn)行查詢數(shù)據(jù)流。例如有一種查詢應(yīng)用，可以在火山監(jiān)測中每五分鐘報(bào)告當(dāng)前活動的情況，這是由于傳感器的加工和相關(guān)表面振動，氣壓和溫度，氣體密度的變化，磁場變異等因素所產(chǎn)生的數(shù)據(jù)流測量，如何讓這些因素運(yùn)用在這些查詢中并得到長時(shí)間高效地成功處理和操作的無線傳感器網(wǎng)絡(luò)運(yùn)行是部署的一個(gè)重要的問題，有些問題不可行，是由于經(jīng)常補(bǔ)充傳感器電池的能量成本過高。在本文中，我們在無線傳感器網(wǎng)絡(luò)中考慮長期運(yùn)行復(fù)雜的查詢并且對此技術(shù)進(jìn)行評估的任務(wù)。此類查詢有多個(gè)(du )運(yùn)算符依賴的函數(shù)，并要求每一輪每次重復(fù)評估運(yùn)算符。由于在傳感器網(wǎng)絡(luò)中通信前傳感器耗能所產(chǎn)生的數(shù)據(jù)量，我們把目標(biāo)推向處理網(wǎng)絡(luò)查詢

5、 18。我們的模型運(yùn)用非循環(huán)圖Q且對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ò)(wnglu)DAG中評價(jià)連續(xù)(linx)Q的表達(dá)根需要解決以下兩個(gè)方面的任務(wù)：（a）在Q的網(wǎng)絡(luò)節(jié)點(diǎn)上安置變量和常量的運(yùn)算符，（b）尋址適合的操作數(shù)網(wǎng)絡(luò)節(jié)點(diǎn)，需要他們來評價(jià)操作數(shù)。這兩點(diǎn)內(nèi)容是有聯(lián)系的，因?yàn)樵贕的布局上某些源到目標(biāo)的路由選擇要求傳感器節(jié)點(diǎn)之間以何種方式尋址，這對決定執(zhí)行尋址的安置具有主要影響。雖然在網(wǎng)絡(luò)查詢中有許多重要的優(yōu)化目標(biāo)需

6、要連續(xù)評估（如響應(yīng)時(shí)間，可靠性等）。由于部分傳感器能耗和著手分析如何分離方面的任務(wù)，我們主要是提高系統(tǒng)的最大限度壽命 - 直到傳感器網(wǎng)絡(luò)壽命結(jié)束之前完成其執(zhí)行的預(yù)定任務(wù)。我們發(fā)現(xiàn)，在我們的實(shí)驗(yàn)評估中顯示，在路由方面有一個(gè)最佳解決方案，來有效地分離的路由和安置。在安置任務(wù)方面找到最佳的解決方案，我們需要考慮最低通信成本的位置（MCP）。MCP 問題是在Q的單個(gè)評價(jià)期間對于已分配Q的一個(gè)或多個(gè)頂點(diǎn)使其在網(wǎng)絡(luò)節(jié)點(diǎn)之間傳送數(shù)據(jù)的總量最小化。MCP問題即使是Q有著成本優(yōu)勢并以單位為1的高度樹，但還是MAX SNP-hard。我們描述了一個(gè)簡單而有效的貪婪啟發(fā)式，我們稱之為GREEDYMCP算法，在實(shí)際顯

7、示中證明最佳的解決MCP問題的方案可用GREEDYMCP算法來實(shí)現(xiàn)。找到一個(gè)最佳的解決尋址方案，是我們解決使用并行流最大壽命的（MLCF）問題。MLCF問題是并行的流量為給定的一組源的目標(biāo)提供數(shù)據(jù)傳輸速率以解決系統(tǒng)最大壽命的問題。我們?yōu)镸LCF問題提供了一個(gè)有效的，簡單的算法,在網(wǎng)絡(luò)的n個(gè)節(jié)點(diǎn)中對于部分源目的地N為了滿足帶有并行流數(shù)據(jù)通信要求，其算法在n + N路徑中發(fā)現(xiàn)了最大限度的分?jǐn)?shù)階系統(tǒng)壽命To，我們稱之為ALGRSM-MLCF的算法。由分?jǐn)?shù)四舍五入下來，我們得到了一個(gè)關(guān)于MLCF問題最佳并行流解決方案，其a=（To nN +1）/T。在實(shí)踐中往往Ton+N，a1。我們的實(shí)驗(yàn)表明，ALG

8、RSM MLCF優(yōu)于現(xiàn)有的尋址算法，但可在系統(tǒng)的壽命和能耗方面應(yīng)用MLCF問題。ALGRSM MLCF 是一種基于修正單形法 (RSM) 的迭代算法。我們在網(wǎng)絡(luò)中連續(xù)查詢 Q的評估(pn )的方法有 GREEDYMCP 和 ALGRSM-MLCF兩種。首先，我們使用ALGRSM MLCF在網(wǎng)絡(luò)(wnglu)中找到一個(gè)(y )Q的位置，并為路由上的所有數(shù)據(jù)值使用ALGRSM-MLCF來滿足傳達(dá)。我們通過廣泛的實(shí)驗(yàn)評估表明，我們始終認(rèn)為在無線傳感器網(wǎng)絡(luò)中對于連續(xù)的網(wǎng)絡(luò)復(fù)雜查詢評價(jià)關(guān)鍵是解決最大壽命的方法。雖然我們采取統(tǒng)一的方式來解決手頭的任務(wù)，我們只需要兩個(gè)網(wǎng)絡(luò)元數(shù)據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和傳感器的初始能量

9、，這是對其它許多網(wǎng)絡(luò)任務(wù)都非常有用的知識。請注意，通過我們的方法發(fā)現(xiàn)小規(guī)模的路由解決方案在傳感器中間接的限制了分配路由信息?？傊?，對于在無線傳感器網(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è)簡單而有效的ALGRSM-MLCF算法，它會在無線傳感器網(wǎng)絡(luò)中發(fā)現(xiàn)最接近整數(shù)解來解決最大生命周期并行流（MLCF）問題的方案。 ALGRSM MLCF優(yōu)于現(xiàn)有的尋址方法。

10、 關(guān)于MLCF 問題我們發(fā)現(xiàn)放置去耦和即將開始的路由任務(wù)都有效 我們使用GREEDYMCP和ALGRSMMLCF方法來最大限度地有效的提高系統(tǒng)的壽命。本文的其余部分安排如下：我們在第2節(jié)中回顧相關(guān)工作，然后在第3節(jié)，我們給予必要的準(zhǔn)備工作。我們在第4節(jié)中表達(dá)描述DAGs中安置的無線傳感器網(wǎng)絡(luò)的GREEDYMCP算法，在一定的MCP問題實(shí)例條件下，用GREEDYMCP算法證明找到最佳的解決方案。我們在 4.2 節(jié)中分析復(fù)雜的MCP問題，并表明MCP 問題對于高度為 1 的樹和提供他們限制的頂點(diǎn)是MAX SNP-hard。然后，我們把注意力放在操作數(shù)的尋址上，我們在第5節(jié)中提出MLCF問題的ALG

11、RSM-MLCF算法。我們在第6節(jié)中提出實(shí)驗(yàn)方法的評估并描述了結(jié)果。在第7節(jié)我們得出結(jié)論。2. 相關(guān)(xinggun)工作pietzuch等人，考慮在傳統(tǒng)的分布式處理(chl)系統(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)格(fngg)，且有足夠的計(jì)算能力，它不同于我們所研究的有限能量的無線傳感器網(wǎng)絡(luò)。在無線傳感器網(wǎng)絡(luò)中，由于Intanagonwiwat等人在一定的背景下，網(wǎng)絡(luò)處理的概念被首次引入，在定向擴(kuò)散中以投機(jī)性取巧的方式消除重復(fù)。Gehrke和Madden等人是第一個(gè)將

12、查詢處理和傳感器網(wǎng)絡(luò)集成一體的，可以通過傳感器網(wǎng)絡(luò)很容易的查詢?nèi)蝿?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)簡單的運(yùn)算符 （聚合、 篩選器等），而在工作中我們的模型審議優(yōu)化的運(yùn)算符的位置是從通信角度考慮的。Ren等人，考慮在簡單的聚合查詢中進(jìn)行質(zhì)量感知處理（如在感興趣的矩形區(qū)域中計(jì)算傳感器

13、測量平均，最小，最大值）。他們提出了集中式的算法，找到傳感器使用無功路由到基站計(jì)算概率的答案來收集其測量的子集。Hu 等人擴(kuò)大了Olston和Widom的工作，提出了連續(xù)聚合查詢（總和，平均，計(jì)數(shù)等）的近似答案的問題。他們?yōu)閭鞲衅鳒y量分配指定了可接受公差范圍查詢答案的方法。如果它超出公差范圍，之后傳感器將在基站中測量。這在許多方面與我們的不同：我們只考慮除了最小值、 最大值、 平均值以外的帶有各類運(yùn)算符的復(fù)雜查詢、 并直接提供準(zhǔn)確的解答查詢、尋求優(yōu)化系統(tǒng)的壽命。許多研究者都主張使用以數(shù)據(jù)為中心的技術(shù)，允許網(wǎng)絡(luò)高效的存儲和已命名的數(shù)據(jù)使用檢索查詢 16。提出并研究 6,8,23,28,29,31

14、，以數(shù)據(jù)為中心的推挽式查詢處理技術(shù)，它可以分類為兩種主要方法：結(jié)構(gòu)化和非結(jié)構(gòu)化的基于散列的數(shù)據(jù)存儲技術(shù) 29和comb-needle方法23。Kapadia和Krishnamachari 20目前在單接收器方柵傳感器網(wǎng)絡(luò)中（所有類型和任意一個(gè)型）運(yùn)用數(shù)學(xué)基礎(chǔ)分析比較這兩種類型一次性查詢的方法，后來，Ahn和Krishnamachari 2發(fā)現(xiàn)，以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)性能的伸縮性取決于能源和存儲資源是否增加，并發(fā)現(xiàn)在特定應(yīng)用程序中更多的節(jié)點(diǎn)生成查詢負(fù)載。Bonfils等人5考慮在傳感器網(wǎng)絡(luò)中查詢運(yùn)算符節(jié)點(diǎn)的位置，以盡量減少評估這種表達(dá)樹的總通信成本。對于任何父-子查詢樹中的運(yùn)算符，用一個(gè)節(jié)點(diǎn)誘

15、導(dǎo)通信成本，然而這些運(yùn)算符的放置和數(shù)據(jù)傳輸速率與從子到其父之間的最短路徑是相關(guān)的。他們(t men)提供了一個(gè)分布式的協(xié)議，嘗試通過優(yōu)化放置并不斷地在相鄰節(jié)點(diǎn)之間移動以適應(yīng)變化的數(shù)據(jù)速率。不認(rèn)為是通過移動相鄰節(jié)點(diǎn)所產(chǎn)生的交換信號形成5。我們ALGRSM MLCF算法不同于他們，我們算法是讓數(shù)據(jù)通過多條路徑尋求優(yōu)化系統(tǒng)壽命的，而不是通過單一路徑來尋求通信總成本的。限制母與父之間的數(shù)據(jù)單個(gè)路徑的尋址，而在不利影響使用壽命的情況下允許多個(gè)路徑的尋址?？梢钥吹綀D10，我們的方法采用最短路徑的路由算法在所有情況下的最佳位置(wi zhi)實(shí)現(xiàn)了更好的壽命。Srivastava等人 30考慮有層次結(jié)構(gòu)的放

16、置網(wǎng)絡(luò)(wnglu)節(jié)點(diǎn)，逐步增加計(jì)算能力和網(wǎng)絡(luò)寬帶，這樣能使總成本的計(jì)算和通訊最小化。我們假設(shè)在一個(gè)不同的網(wǎng)絡(luò)模型中的傳感器的能量是受限均勻的且有不同的目標(biāo)和優(yōu)化系統(tǒng)的壽命，這并不一定減少總成本的計(jì)算和通信。Garg和Konemann14描述了一種接近并行流問題的迭代算法并最大限度的得到求解證明。它的LP 配方是不同于MLCF。他們的目標(biāo)是最大限度地提高網(wǎng)絡(luò)下邊緣有限總流量的容量，而我們是最大限度地提高網(wǎng)絡(luò)有限壽命和節(jié)點(diǎn)能量。此外，我們的 ALGRSM MLCF 算法在解決方案中是以路由的路徑數(shù)量為界的，而在算法14中發(fā)現(xiàn)解決方案，它們可以使用任意多個(gè)路由路徑作為迭代次數(shù)。因?yàn)橛猩俨糠致酚陕?/p>

17、徑是重要的，所以在實(shí)踐中部分因?yàn)榉职l(fā)到傳感器中，而且相關(guān)的路由信息的使用保持較小，有較少的路徑。Chang和 Tassiulas 7 提出了一種最短路徑的路由算法用來收集最大壽命的數(shù)據(jù)從而在每個(gè)環(huán)節(jié)的每個(gè)節(jié)點(diǎn)處反映通信能耗和剩余的能量。雖然他們還制訂了一個(gè)線性規(guī)劃的路由問題，他們通過其擬議的算法來獲得壽命與現(xiàn)實(shí)的壽命進(jìn)行比較。我們制定的最優(yōu)路徑問題不同于線性規(guī)劃，我們的 ALGRSM MLCF 算法有效地直接的解決了 LP以獲得最佳路由。此外，在算法7的性能中是主要依賴參數(shù)所使用的算法，而ALGRSM MLCF是 非參數(shù)的。Wu等人32考慮使用一個(gè)給定的路由樹來興建發(fā)射/接收傳感器的時(shí)間表，以

18、收集數(shù)據(jù)。他們描述了發(fā)送和接收槽的分配(fnpi)，減少傳輸過程中的碰撞，以及使用傳感器的方法。這項(xiàng)工作對我們的工作是有幫助的。Wu等人32只是假設(shè)一個(gè)路由樹，而我們的方法可在連續(xù)查詢(chxn)的評估中構(gòu)建了一個(gè)安置和路由。另一方面，我們ALGRSM MLCF算法不考慮沖突期間通過傳感器的傳輸。推導(dǎo)詳細(xì)的發(fā)送/接收(jishu)安排位置/路由表也是重要的，他們的方法可能是一個(gè)步驟一個(gè)目標(biāo)。3. 準(zhǔn)備工作我們利用整個(gè)文件記錄了定義和符號，其中包括簡單的模型，無線傳感器網(wǎng)絡(luò)的概念和表達(dá)式樹。3.1. 共同的定義和符號給定一個(gè)圖G，我們用VG 表示其頂點(diǎn)及用EG表示其邊緣集。為簡單起見，對于頂點(diǎn)v

19、，我們經(jīng)常寫vG，而不是 vVG 和對于邊緣點(diǎn)ij寫 ijG，而不是 ijE G 。通過其頂點(diǎn)的一個(gè)子集讓GV=(V,EG V V) 成為G的子圖。在子圖 G 中誘導(dǎo)其邊緣的一個(gè)子集，我們通常用 GA=(V,A) ?？紤]邊緣有向圖G帶邊緣權(quán)WR|E|G|。邊緣IJEG 的邊緣收縮圖G是從崩潰（合并）G頂點(diǎn)到頂點(diǎn)j得到的圖。一個(gè)頂點(diǎn)i到頂點(diǎn) j 的折疊，我們需要以下三個(gè)步驟圖：（一）如果KJEG，則每個(gè)邊緣Wki權(quán)數(shù)為KIEG，然后添加權(quán)數(shù)WKI邊緣KJ至G，否則邊緣增加權(quán)數(shù)KJ到WKI，（b）如果JKEG。則每個(gè)邊緣IK2權(quán)數(shù)為IKEG， 然后添加權(quán)數(shù)WIK邊緣JK至G，否則增加的邊緣權(quán)數(shù)JK

20、 到WIK，（c）刪除頂點(diǎn)i和任何自我循環(huán)G.（邊緣JJ）考慮分區(qū)=V1，V2，Vm; 從頂點(diǎn)的分區(qū)G設(shè)置 V G，代替一些m1。進(jìn)一步我們通過定義的縮圖G表示以下邊緣加權(quán)有向圖G。 G的頂點(diǎn)是，如果在IJEG的邊緣存在一個(gè)從Vi到Vj的G，即uvEG和uVi,jVj是邊緣的切緣。每邊的權(quán)數(shù)等于從Vi到Vj 的邊緣G晉級權(quán)數(shù)的總和。請注意，G的獲得是G通過承包所有的內(nèi)塊（未切割）邊緣圖的總和。鑒于一實(shí)例優(yōu)化問題， opt（I）和sol（I）分別是最優(yōu)和最可行的解決方案。為簡單起見， opt(I) 和 sol(I) 將還相應(yīng)的標(biāo)明解決方案。相對誤差的解決方案 sol(I) 等于 opt(I)，其

21、近似比等于 sol(I) / opt(I)。每當(dāng)他們允許(ynx)實(shí)例有未知數(shù)的分?jǐn)?shù)值時(shí)。請我們參閱連續(xù)積分解決方案來優(yōu)化問題。我們用小寫和大寫的粗體字母分別表示向量(xingling)和矩陣，如X和A分別是矢量和矩陣。向量X被定義為 。由于兩個(gè)(lin )向量，我們說x主導(dǎo)y并寫成X Y，如果其中我們說 x比 y大是按字典順序，來說明是否索引一組最小的非零的xy 正負(fù)。由于矩陣是一個(gè)單一列向量，許多符號/矩陣操作自然是延伸的向量。我們用表示矩陣A的轉(zhuǎn)置。給了n m 矩陣和兩個(gè)指數(shù)序列I屬于1,2，n; J屬于1;2;n，我們通過定義A的矩陣;其中由于我們延長的符號和 Ay 是索引集，一組指數(shù)

22、序列始終通過其元素按升序排列轉(zhuǎn)換序列列出。3.2. 無線傳感器網(wǎng)絡(luò)模型考慮無線傳感器網(wǎng)絡(luò) （WSN）的 n 個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)用 b表示，其被指定為其余傳感器節(jié)點(diǎn)的基站。雖然傳感器被假定為有限的非補(bǔ)充能量，且傳感器通過唯一的 Id 來標(biāo)識，所以基站沒有能源的限制?？拷鼈鞲衅鞲信d趣的點(diǎn)稱為數(shù)據(jù)源，而他們在預(yù)定義的數(shù)據(jù)速率中監(jiān)視和生成感測數(shù)據(jù)。在基站分析中連續(xù)查詢獲取數(shù)據(jù)并處理生成的數(shù)據(jù)源的數(shù)據(jù)構(gòu)成，并被解析為一個(gè)表達(dá)式DAG。時(shí)間是離散的，被定義的數(shù)據(jù)速率是傳感器節(jié)點(diǎn)在每隔一段時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)包的數(shù)目。為簡單起見，我們假設(shè)數(shù)據(jù)包的大小是固定的。在系統(tǒng)壽命周期T是最早的時(shí)候，無線傳感器網(wǎng)絡(luò)在一個(gè)或多

23、個(gè)傳感器中通過耗能來執(zhí)行其預(yù)定的任務(wù)（例如查詢評價(jià)）。無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是仿照一個(gè)有向圖G=V,E的;用它來代替V=1;2; n;和E屬于VV。每當(dāng)i能成功發(fā)送一個(gè)數(shù)據(jù)包到j(luò)，就存在ijE。讓距離在i和j之間。為了從節(jié)點(diǎn)i發(fā)送一個(gè)數(shù)據(jù)包到節(jié)點(diǎn)j，讓 耗能，并讓的節(jié)點(diǎn)j收到了數(shù)據(jù)包所需的能量。為讓節(jié)點(diǎn)i可使用能源，我們認(rèn)為b=。為簡單起見，我們假設(shè)在每個(gè)節(jié)點(diǎn)附近的單源節(jié)點(diǎn)是傳感器網(wǎng)絡(luò)的一個(gè)基站。實(shí)際部署中可以在相同的節(jié)點(diǎn)附近有多個(gè)傳感器，這將是理想的，他們共享的采集數(shù)據(jù)。相同節(jié)點(diǎn)周圍的所有傳感器可以收到其中任何(rnh)一個(gè)信號，這可能是很容易做的。引入一個(gè)新的節(jié)點(diǎn)，與作為數(shù)據(jù)源，然后追加

24、到G，i附近的1/4范圍(fnwi)內(nèi)為每個(gè)傳感器節(jié)點(diǎn)j，兩個(gè)新的邊和，同時(shí)(tngsh)和等于0。傳感器網(wǎng)絡(luò)同樣可以處理由多個(gè)基站引入的一個(gè)新的節(jié)點(diǎn) ，作為新的單一基站，然后追加到G，每個(gè)基站為 I，的新的邊緣在本文中，我們不考慮有關(guān)信號和信道干擾，傳輸調(diào)度是為了避免或減少這種干擾的問題。調(diào)度發(fā)射后可制定路由方案，這樣可在潛伏期增加查詢評價(jià)。3.3一個(gè)復(fù)雜查詢的評估模型我們將介紹一個(gè)簡單的模型，我們將使用連續(xù) （重復(fù)） 處理的復(fù)雜查詢。在查詢中只有一個(gè)運(yùn)算符（如添加、 相乘，等） 或只有一個(gè)操作符 （例如總和、 計(jì)數(shù)、 最小、 最大等）稱為簡單，否則它稱為復(fù)雜。過去我們對于復(fù)雜查詢是在傳感器

25、網(wǎng)絡(luò)中關(guān)于傳感器的測量。在每輪感應(yīng)期間，使用傳感器的當(dāng)前度量單位 （可能是事先測量）查詢評估。我們模型使用定向根值的表達(dá)圖 （DAGs）查詢。表達(dá)圖DAG的一個(gè)根值Q是其一個(gè)單根（頂點(diǎn)沒有任何父母點(diǎn)），符合內(nèi)部頂點(diǎn)的運(yùn)算符（無兒無女的頂點(diǎn)）及對應(yīng)常量或變量。每個(gè)頂點(diǎn)vV Q的 有關(guān)值不變，但不同的尺寸大?。╒）是衡量單位數(shù)據(jù)包大小的。uvE Q 每邊的權(quán)數(shù)是等于大?。║）。每個(gè)頂點(diǎn)有一個(gè)或多個(gè)操作數(shù)（子點(diǎn)），其主要是一個(gè)功能的操作。在 AND 運(yùn)算符 （OR 運(yùn)算符） 的模型中，對于運(yùn)算符的功能的評價(jià)是需要所有 （任何一個(gè)） 其操作數(shù)參與的。表達(dá)的DAG出現(xiàn)在各個(gè)領(lǐng)域，如TinyDB的SQL連

26、續(xù)查詢評價(jià) 選擇樓層，房間，AVG（溫度）來自傳感器地板 70采樣(ci yn)周期30秒;其中運(yùn)算符是關(guān)系代數(shù)運(yùn)算符，子葉是傳感器樣本 （測量），它們都有一個(gè)樹DAG表示。當(dāng)請求運(yùn)算符可用時(shí)，需要評估運(yùn)算符，可以用一個(gè)渴望（盡快）或懶惰（當(dāng)它需要輸出要求時(shí)）的方式表示。此評價(jià)在一定回合不需要分配綁定的值。在一個(gè)命令的程序中評價(jià)（可能不是全部）運(yùn)算符，使其根值提供提供給用戶。在表達(dá)DAG中設(shè)H為一個(gè)無線傳感器網(wǎng)絡(luò)并用Q來進(jìn)行評估。我們調(diào)用主機(jī)圖H和客圖Q。在時(shí)間t中分配變量vV G值，這取決于測量src(v)屬于V H ，設(shè)置主機(jī)的網(wǎng)絡(luò)節(jié)點(diǎn)（傳感器）通常要設(shè)置v的數(shù)據(jù)源，設(shè)置一個(gè)變量的數(shù)據(jù)源可

27、能是一個(gè)單件或是傳感器附近的一小部分。為了評估在主機(jī)h中的客體Q，我們需要在一個(gè)或多個(gè)主機(jī)節(jié)點(diǎn)上放置所有客體頂點(diǎn)。每個(gè)頂點(diǎn)vV Q可以在主機(jī)節(jié)點(diǎn)上被放置一個(gè)指定的候選節(jié)點(diǎn)如果V是一個(gè)變量，則每個(gè)在cands(v)中的候選主機(jī)節(jié)點(diǎn)（V）是V值評估的結(jié)果，如果有的話，一次向它提供其所需要的所有操作符，如果cands=則客頂點(diǎn)為v，如果則受到固定的限制，否則被稱為自由。我們擴(kuò)展設(shè)置數(shù)據(jù)源，并設(shè)置任何客頂點(diǎn)子集而候選主機(jī)作為和如果我們呼吁一個(gè)受理，圖1給出了一個(gè)示例查詢表達(dá)的DAG（樹）。一個(gè)DAG中的客體節(jié)點(diǎn)Q被安置到主機(jī)的網(wǎng)絡(luò)H中去，則每個(gè)頂點(diǎn)v VQ被放置了一個(gè)非空集的主機(jī)節(jié)點(diǎn)。每當(dāng)一個(gè)頂點(diǎn)vV

28、Q必要的時(shí)候，一個(gè)主機(jī)節(jié)點(diǎn)要求被提供，這樣做可能需要檢測或計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)i，甚至是計(jì)算i和其他主機(jī)的網(wǎng)絡(luò)之間的通信節(jié)點(diǎn)。圖 2 提供了示例并顯示了被放置到無線傳感器網(wǎng)絡(luò)上表達(dá)的DAG 圖形(txng)1 圖形(txng)2此后，我們只考慮位置，其中每個(gè)客體(kt)的頂點(diǎn)都被放置在一個(gè)主機(jī)節(jié)點(diǎn)上，即在主機(jī)的網(wǎng)絡(luò)中是不能復(fù)制客體頂點(diǎn)。考慮將客體網(wǎng)絡(luò)DAG Q放置到主機(jī)網(wǎng)絡(luò)H。放置在同一主機(jī)節(jié)點(diǎn)的客體頂點(diǎn)集的候選集的交集一般非空。因此，通過消除放置在不同主機(jī)節(jié)點(diǎn)的客體頂點(diǎn)邊緣（切邊），我們能夠得到關(guān)于客體圖的連接組件的集合，這樣所有的連接組件的頂點(diǎn)Vi就被放置在同一主機(jī)節(jié)點(diǎn)ui。換言之，將客體Q放置在

29、主機(jī)H會引起VQ 的分區(qū)，這樣所有Vi的客體頂點(diǎn)將被放置在主機(jī)節(jié)點(diǎn) 請注意，的每塊區(qū)Vi是可以受理的我們稱這種分區(qū)為允許分區(qū)。此外，每一輪Q的評估中的傳輸數(shù)據(jù)量等于切邊的總成本，其中，切邊指的是由放置引起的。換言之，給定放置中Q的單個(gè)評估所需要的總傳輸量等于通過分區(qū)的Q的收縮的總重量。事實(shí)上，從主機(jī)節(jié)點(diǎn)ui至客體節(jié)點(diǎn)uj所需的傳輸總量相對于中邊緣ViVj的重量。確定相當(dāng)于每輪評估Q中總傳輸總量的放置成本。通過重新標(biāo)記每個(gè)頂點(diǎn)，其中Vi中的客體頂點(diǎn)被放置在主機(jī)節(jié)點(diǎn)ui，從而確定放置傳輸需求圖R 成為從中獲取的圖。由于客體頂點(diǎn)放置在 和 ，邊緣的量等于每輪從主機(jī)節(jié)點(diǎn)ui到主機(jī)節(jié)點(diǎn)u所需的總傳輸數(shù)據(jù)

30、量。我們在放置通信節(jié)點(diǎn)中定義最小 Q 到 H 上的成本(MCP) 問題是為了尋找到候選主機(jī)頂點(diǎn)上以最低的成本 （傳送數(shù)據(jù)的量）的位置。由于Q安置到主機(jī)h上并且(bngqi)誘導(dǎo)分隔邊緣的位置，本質(zhì)上它是遵循的MCP問題等同于下面的總權(quán)數(shù)圖劃分問題的。我們?yōu)榱思s束定義分區(qū) （MCCP）最小成本 的問題，如下所示：任何邊緣加權(quán)圖G和一個(gè)函數(shù)找到這樣(zhyng)一個(gè)最低的成本切邊（邊割），非空為每個(gè)連接組件的Gi G-A.MCCP問題(wnt)實(shí)例的最佳解決方案，也是為客體Q 到主機(jī) H的 MCP 問題的最佳解決方案，反之亦然。我們研究了 4.2 節(jié)的 MCP 和 MCCP 問題的復(fù)雜性。鑒于已將

31、客體Q放置到主機(jī)H，我們現(xiàn)在需要找到一種高效節(jié)能的方式以滿足傳輸需求圖R所傳達(dá)的數(shù)據(jù)路徑需要，從而使系統(tǒng)使用期限最大化。換言之，我們需要找到最大使用期限T以及滿足為收集起點(diǎn)終點(diǎn)對數(shù)（邊緣）的傳輸需求的路徑，其中需求等于從主機(jī)節(jié)點(diǎn)Si到主機(jī)節(jié)點(diǎn)di的邊緣重量（一輪中所需傳輸數(shù)據(jù)量）。這就是我們在第5節(jié)中有考慮過的最大使用期限并行流（MLCF）問題。在本文中，我們假設(shè)了表達(dá)式DAGs和AND-算法模式。同樣，我們也假設(shè)變量v V Q的數(shù)據(jù)源是單個(gè)的，因此v固定在其單個(gè)數(shù)據(jù)源主機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)上。此外，我們假設(shè)Q根固定在基站且Q的頂點(diǎn)放置不會被復(fù)制，即，對于所有的vVQ來說，。并且，我們還以為，無論在計(jì)算

32、運(yùn)算符v值的時(shí)候，還是在測量和分配變量v值的時(shí)候，或者是在配備常量v值的時(shí)候所消耗的能源，相比于所有頂點(diǎn)v VQ的傳輸所消耗的能源來說，都是不容忽視的。無線傳感網(wǎng)絡(luò)課程(kchng)論文外文(wiwn)原文Maximum lifetime continuous query processing in wireless sensor networksKonstantinos Kalpakis* , Shilang TangComputer Science and Electrical Engineering Department, University of Maryland, Baltimor

33、eABSTRACTMonitoring applications emerge as one of the most important applications of wireless sensor networks (WSNs). Such applications typically have long-running complex queries that are continuously evaluated over the sensor measurement streams. Due to the limited energy of the sensors in WSNs ,

34、energy efficient query evaluation is critical to prolong the system lifetime the earliest time that the network can not perform its intended task anymore.We model complex queries by expression trees and consider the problem of maximizing the lifetime of a wireless sensor network for the continuous i

35、nnetwork evaluation of an expression trees T , so the value of its root is available at the base station. In-network evaluation means that the evaluation of the operators of T may be pushed to the network nodes, and continuous means the repeated evaluation of T (once at each round). Continuous in-ne

36、twork 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 network nodes and (b) the routing of their values to the appropriate network nodes that needed them to evaluate the operators. We analyze th

37、e complexity 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 communicated. A placement of T induces a certain Maximum Lifetime Concurrent

38、 Flow (MLCF) problem. We provide an efficient algorithm that finds near-optimal 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 in-network evaluation of T consists of utilizing both o

39、ur placement and routing algorithms above.We demonstrate experimentally that our approach consistently and effectively find the maximum lifetime solutions for the continuous in-network evaluation of 無線傳感網(wǎng)絡(luò)(wnglu)課程論文expression trees in wireless sensor networks.IntroductionRemote monitoring applicati

40、ons are one of the most attractive applications of wireless sensor networks. 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 s

41、uch 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, magnetic variance, and etc. How

42、 to energy efficiently process these long-running queries is a critical problem to the success of the deployment and operation of wireless sensor networks, since often replenishing the energy of the sensors by replacing their batteries is cost prohibitive or even infeasible. In this paper, we consid

43、er the task of the continuous evaluation of long-running complex queries in wireless sensor networks. Such queries have multiple function-dependent 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 o

44、f data the network can communicate before the sensors deplete their energy, we aim to push the queries into the network 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

45、 leaves are constants or variables. Each vertex of Q has a size for its value and a set of candidate network 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 in-network evaluatio

46、n of a rooted expression DAG Q entails addressing the following two aspects of the task: (a) the placement of the operators, variables, and constants of Q to network nodes, and (b) the routing of the operand values to the appropriate network nodes that needed them to evaluate the operators. These tw

47、o aspects are coupled because the placement of Q imposes certain sourcedestination routing requirements among the sensor nodes, and the manner in which routing is performed can have a major impact on placement decisions.While there are many important optimization goals for the continuous in-network

48、evaluation of queries (e.g. response time, reliability, etc.), we focus on maximizing the system lifetime the time until the sensor network losses its ability to perform its 無線傳感網(wǎng)絡(luò)(wnglu)課程論文intended task due to depletion of energy at (some of) its sensors, and analyze how to decouple the two aspect

49、s of the task at hand. We find, as shown in our experimental evaluation, that having a near optimal solution to the routing aspect effectively decouples the routing and placement aspects, and therefore allows us to solve these two aspects one at a time.To find a near optimal solution to the placemen

50、t aspect of the task, we consider the minimum communication cost placement (MCP) problem. The MCP problem is that of minimizing the total amount of data communicated among network nodes , which have been assigned one or more vertices of Q, during a single evaluation of Q. We show that the MCP proble

51、m is MAX SNP-hard even when Q is a tree of height 1 with unit cost edges. We describe a simple and efficient greedy heuristic, which we call the GREEDYMCP algorithm, for the MCP problem ,and show practically useful cases under which GREEDYMCP finds provably optimal solutions to the MCP problem. To f

52、ind a near optimal solution to the routing aspect of the task, we solve a maximum lifetime concurrent flow (MLCF) problem. The MLCF problem is the problem of maximizing the lifetime of a system that concurrently pushes flow to satisfy the data rate demands for a given set of sourcedestination pairs.

53、 We provide an efficient and simple algorithm for the MLCF problem, which we call the ALGRSM-MLCF algorithm, that finds at most n + N paths that maximize the fractional system lifetime To for satisfying the concurrent flow data demands for N sourcedestination pairs in a network with n nodes. By roun

54、ding down that fractional solution, we get an a-optimal integral concurrent flow solution to the MLCF problem, where Since often in practice We experimentally show that ALGRSM-MLCF outperforms existing routing algorithms that could be applied to the MLCF problem ,in terms of system life time and ene

55、rgy overhead. ALGRSM-MLCF is an iterative algorithm based on the Revised Simplex Method (RSM). Our approach for the continuous in-network evaluation of query Q consists of using both GREEDYMCP and ALGRSM-MLCF. First, we use GREEDYMCP to find a placement of Q on the network, and we use ALGRSM-MLCF fo

56、r routing all the data values that need to be communicated. We show, through an extensive experimental evaluation, that our approach consistently finds the maximum lifetime 無線傳感網(wǎng)絡(luò)(wnglu)課程論文無線傳感網(wǎng)絡(luò)(wnglu)課程論文solution for the continuous in-network evaluation of complex queries in wireless sensor netwo

57、rks. Although we take a centralized approach to tackle the task at hand, we only require the knowledge of two network metadata the network topology and the initial energy of sensors, which are very useful to many other network tasks as well. Note that the small size of the routing solution found by

58、our approach limits the overhead of distributing the routing information to the sensors. In summary, for the task of continuous in-network processing of complex queries in wireless sensor networks (WSNs), the original contributions of this paper are as follows:theoretically analyze the complexity of

59、 the MCP problem, the problem of placing expression DAGs on WSNs with minimum total communication vide a greedy heuristic GREEDYMCP , for the MCP problem. GREEDYMCP finds provably optimal solutions in practical useful vide a simple and effective algorithm, ALGRSM-MLCF, that finds ne

60、ar optimal integral solutions to the maximum lifetime concurrent flow (MLCF) problem in WSNs . ALGRSM-MLCF outperforms existing routing methods.we find that having near optimal solutions to the MLCF problem enables the decoupling of the placement and routing aspects of the task at hand.our approach,