外文翻譯---基于最長壽命的無線傳感器網絡連續(xù)查詢處理

1、<p>　　中文8100字，5100漢字，24800英文字符</p><p>　　出處：Kalpakis K, Tang S. Maximum lifetime continuous query processing in wireless sensor networks[J]. Ad Hoc Networks, 2010, 8(7):723–741.</p><p>　　畢業(yè)設

2、計(論文)外文資料翻譯</p><p>　　基于最長壽命的無線傳感器網絡連續(xù)查詢處理</p><p>　　Konstantinos Kalpakis* , Shilang Tang</p><p>　　計算機科學部門和電氣工程部門,馬里蘭大學,巴爾摩</p><p><b>　　摘要</b></p><

3、;p>　　監(jiān)測應用成為無線傳感器網絡（WSNS）最重要的應用之一。這類應用通常具有長期運行的復雜查詢處理技術且通過傳感器流對此處理技術進行評估。基于無線傳感器網絡中傳感器的能量有限，高效節(jié)能查詢的評價對于延長系統(tǒng)使用壽命來說是至關重要的—使用期限指的是此網絡查詢從開始到停止所執(zhí)行其預定任務的最早時間。</p><p>　　我們通過使用表達式樹對復雜查詢進行建模。我們考慮使無線傳感器網絡的使用期限最大化以達成

4、表達式樹T的持續(xù)網絡內評估，因此可在基站獲得其根值。網絡內評估意味著對于算符T的評估可能會推至網絡節(jié)點且同樣意味著對T進行重復評估（每輪一次）。持續(xù)的網絡內T評估需要解決以下問題的兩個方面：（1）相對于網絡節(jié)點的T的運算符，變量和變量的放置（2）以上量值對于適當網絡節(jié)點的路徑選擇，網絡節(jié)點需要使用以上量值評估運算符。</p><p>　　我們對其復雜性進行了分析，并且為T節(jié)點在WSN傳感器節(jié)點上的放置提供了一種簡

5、單而有效的算法。我們所提出的運算符放置算法試圖使總傳輸數(shù)據(jù)量最小化。T的放置可引起一定的最大使用期限并行流（MLCF）問題。我們提供的算法可以找到解決MLCF問題的近優(yōu)積分方案，其中一種便是收集路徑，一定數(shù)量的積分流被路由。我們對于T的持續(xù)網絡內評估包括以上放置和路由算法。</p><p>　　實驗證明，我們的做法能夠一貫地、有效地找到對于無線傳感網絡表達式樹的持續(xù)網絡內評估的最大使用期限解決方案。</p&

6、gt;<p>　　2010 Elsevier B.V. All rights reserved.</p><p><b>　　1.介紹</b></p><p>　　遠程監(jiān)控是無線傳感器網絡最具有吸引力的應用之一。像環(huán)境監(jiān)測和建筑監(jiān)測，它們通常會在興趣點處通過傳感器不斷的運行查詢數(shù)據(jù)流。例如有一種查詢應用，可以在火山監(jiān)測中每五分鐘報告當前活動的情況，這是由

7、于傳感器的加工和相關表面振動，氣壓和溫度，氣體密度的變化，磁場變異等因素所產生的數(shù)據(jù)流測量，如何讓這些因素運用在這些查詢中并得到長時間高效地成功處理和操作的無線傳感器網絡運行是部署的一個重要的問題，有些問題不可行，是由于經常補充傳感器電池的能量成本過高。</p><p>　　在本文中，我們在無線傳感器網絡中考慮長期運行復雜的查詢并且對此技術進行評估的任務。此類查詢有多個運算符依賴的函數(shù)，并要求每一輪每次重復評估運

8、算符。由于在傳感器網絡中通信前傳感器耗能所產生的數(shù)據(jù)量，我們把目標推向處理網絡查詢 [18]。我們的模型運用非循環(huán)圖Q且對Q進行詳細的描述，其內部節(jié)點與子節(jié)點用操作數(shù)運算符 （函數(shù)）查詢、它們的葉用常量或變量表達。Q的每個頂點都有其重要性且每一組都可放置候選網絡節(jié)點。在Q的每個頂點上有一組源傳感器節(jié)點，其用于分配查詢結果給該變量。</p><p>　　在網絡DAG中評價連續(xù)Q的表達根需要解決以下兩個方面的任務：（

9、a）在Q的網絡節(jié)點上安置變量和常量的運算符，（b）尋址適合的操作數(shù)網絡節(jié)點，需要他們來評價操作數(shù)。這兩點內容是有聯(lián)系的，因為在G的布局上某些源到目標的路由選擇要求傳感器節(jié)點之間以何種方式尋址，這對決定執(zhí)行尋址的安置具有主要影響。</p><p>　　雖然在網絡查詢中有許多重要的優(yōu)化目標需要連續(xù)評估（如響應時間，可靠性等）。由于部分傳感器能耗和著手分析如何分離方面的任務，我們主要是提高系統(tǒng)的最大限度壽命 - 直到傳

10、感器網絡壽命結束之前完成其執(zhí)行的預定任務。我們發(fā)現(xiàn)，在我們的實驗評估中顯示，在路由方面有一個最佳解決方案，來有效地分離的路由和安置。</p><p>　　在安置任務方面找到最佳的解決方案，我們需要考慮最低通信成本的位置（MCP）。MCP 問題是在Q的單個評價期間對于已分配Q的一個或多個頂點使其在網絡節(jié)點之間傳送數(shù)據(jù)的總量最小化。MCP問題即使是Q有著成本優(yōu)勢并以單位為1的高度樹，但還是MAX SNP-hard。我

11、們描述了一個簡單而有效的貪婪啟發(fā)式，我們稱之為GREEDYMCP算法，在實際顯示中證明最佳的解決MCP問題的方案可用GREEDYMCP算法來實現(xiàn)。</p><p>　　找到一個最佳的解決尋址方案，是我們解決使用并行流最大壽命的（MLCF）問題。MLCF問題是并行的流量為給定的一組源的目標提供數(shù)據(jù)傳輸速率以解決系統(tǒng)最大壽命的問題。我們?yōu)镸LCF問題提供了一個有效的，簡單的算法,在網絡的n個節(jié)點中對于部分源目的地N為

12、了滿足帶有并行流數(shù)據(jù)通信要求，其算法在n + N路徑中發(fā)現(xiàn)了最大限度的分數(shù)階系統(tǒng)壽命To，我們稱之為ALGRSM-MLCF的算法。由分數(shù)四舍五入下來，我們得到了一個關于MLCF問題最佳并行流解決方案，其a=（To —n—N +1）/T。在實踐中往往To>>n+N，a≈1。我們的實驗表明，ALGRSM MLCF優(yōu)于現(xiàn)有的尋址算法，但可在系統(tǒng)的壽命和能耗方面應用MLCF問題。ALGRSM MLCF 是一種基于修正單形法 (RSM

13、) 的迭代算法。</p><p>　　我們在網絡中連續(xù)查詢 Q的評估的方法有 GREEDYMCP 和 ALGRSM-MLCF兩種。首先，我們使用ALGRSM MLCF在網絡中找到一個Q的位置，并為路由上的所有數(shù)據(jù)值使用ALGRSM-MLCF來滿足傳達。我們通過廣泛的實驗評估表明，我們始終認為在無線傳感器網絡中對于連續(xù)的網絡復雜查詢評價關鍵是解決最大壽命的方法。雖然我們采取統(tǒng)一的方式來解決手頭的任務，我們只需要兩個

14、網絡元數(shù)據(jù)—網絡拓撲結構和傳感器的初始能量，這是對其它許多網絡任務都非常有用的知識。請注意，通過我們的方法發(fā)現(xiàn)小規(guī)模的路由解決方案在傳感器中間接的限制了分配路由信息。</p><p>　　總之，對于在無線傳感器網絡（WSNS）中連續(xù)處理復雜查詢的網絡任務，本文貢獻如下：</p><p>　　?從理論上分析MCP問題的復雜性，是將無線傳感器網絡中放置DAGs的表達與最低的總通信成本的混合在一

15、起。</p><p>　　?為MCP的問題提供貪婪啟發(fā)式GREEDYMCP。GREEDYMCP在實際應用情況下發(fā)現(xiàn)并證明最佳的解決方案。</p><p>　　?提供一個簡單而有效的ALGRSM-MLCF算法，它會在無線傳感器網絡中發(fā)現(xiàn)最接近整數(shù)解來解決最大生命周期并行流（MLCF）問題的方案。 ALGRSM MLCF優(yōu)于現(xiàn)有的尋址方法。</p><p>　　?關于M

16、LCF 問題我們發(fā)現(xiàn)放置去耦和即將開始的路由任務都有效</p><p>　　?我們使用GREEDYMCP和ALGRSMMLCF方法來最大限度地有效的提高系統(tǒng)的壽命。</p><p>　　本文的其余部分安排如下：我們在第2節(jié)中回顧相關工作，然后在第3節(jié)，我們給予必要的準備工作。我們在第4節(jié)中表達描述DAGs中安置的無線傳感器網絡的GREEDYMCP算法，在一定的MCP問題實例條件下，用GRE

17、EDYMCP算法證明找到最佳的解決方案。我們在 4.2 節(jié)中分析復雜的MCP問題，并表明MCP 問題對于高度為 1 的樹和提供他們限制的頂點是MAX SNP-hard。然后，我們把注意力放在操作數(shù)的尋址上，我們在第5節(jié)中提出MLCF問題的ALGRSM-MLCF算法。我們在第6節(jié)中提出實驗方法的評估并描述了結果。在第7節(jié)我們得出結論。</p><p><b>　　2. 相關工作</b><

18、/p><p>　　pietzuch等人，考慮在傳統(tǒng)的分布式處理系統(tǒng)中放置網絡運算符。在類似的網絡設置中，Ahmad等人，在覆蓋的網絡中用放置的三個運算符算法構造查詢處理并比較其每一個性能。他們認為由節(jié)點組成的網絡具有互聯(lián)網的風格，且有足夠的計算能力，它不同于我們所研究的有限能量的無線傳感器網絡。</p><p>　　在無線傳感器網絡中，由于Intanagonwiwat等人在一定的背景下，網絡處

19、理的概念被首次引入，在定向擴散中以投機性取巧的方式消除重復。Gehrke和Madden等人是第一個將查詢處理和傳感器網絡集成一體的，可以通過傳感器網絡很容易的查詢任務。在美洲獅項目中，有人建議在傳感器網絡中以傳感器數(shù)據(jù)分層結構管理作為一個分布式數(shù)據(jù)庫系統(tǒng)。在TinyDB中，無線傳感器網絡被提出引入查詢處理的框架用來從事時間地點分發(fā)，往往是在無線傳感器網絡中采樣數(shù)據(jù)和傳遞數(shù)據(jù)。解決能源利用效率是考慮問題的主要因素之一，但不是解決最大系統(tǒng)壽

20、命的目標。此外，在查詢運算符中 [11,24] 從功能角度進行建模，而且往往是相當簡單的運算符 （聚合、 篩選器等），而在工作中我們的模型審議優(yōu)化的運算符的位置是從通信角度考慮的。</p><p>　　Ren等人，考慮在簡單的聚合查詢中進行質量感知處理（如在感興趣的矩形區(qū)域中計算傳感器測量平均，最小，最大值）。他們提出了集中式的算法，找到傳感器使用無功路由到基站計算概率的答案來收集其測量的子集。Hu 等人擴大了O

21、lston和Widom的工作，提出了連續(xù)聚合查詢（總和，平均，計數(shù)等）的近似答案的問題。他們?yōu)閭鞲衅鳒y量分配指定了可接受公差范圍查詢答案的方法。如果它超出公差范圍，之后傳感器將在基站中測量。這在許多方面與我們的不同：我們只考慮除了最小值、 最大值、 平均值以外的帶有各類運算符的復雜查詢、 并直接提供準確的解答查詢、尋求優(yōu)化系統(tǒng)的壽命。</p><p>　　許多研究者都主張使用以數(shù)據(jù)為中心的技術，允許網絡高效的存儲

22、和已命名的數(shù)據(jù)使用檢索查詢 [16]。提出并研究 [6,8,23,28,29,31]，以數(shù)據(jù)為中心的推挽式查詢處理技術，它可以分類為兩種主要方法：結構化和非結構化的基于散列的數(shù)據(jù)存儲技術 [29]和comb-needle方法[23]。Kapadia和Krishnamachari [20]目前在單接收器方柵傳感器網絡中（所有類型和任意一個型）運用數(shù)學基礎分析比較這兩種類型一次性查詢的方法，后來，Ahn和Krishnamachari [2]

23、發(fā)現(xiàn)，以數(shù)據(jù)為中心的傳感器網絡性能的伸縮性取決于能源和存儲資源是否增加，并發(fā)現(xiàn)在特定應用程序中更多的節(jié)點生成查詢負載。</p><p>　　Bonfils等人[5]考慮在傳感器網絡中查詢運算符節(jié)點的位置，以盡量減少評估這種表達樹的總通信成本。對于任何父-子查詢樹中的運算符，用一個節(jié)點誘導通信成本，然而這些運算符的放置和數(shù)據(jù)傳輸速率與從子到其父之間的最短路徑是相關的。他們提供了一個分布式的協(xié)議，嘗試通過優(yōu)化放置并不

24、斷地在相鄰節(jié)點之間移動以適應變化的數(shù)據(jù)速率。不認為是通過移動相鄰節(jié)點所產生的交換信號形成[5]。我們ALGRSM MLCF算法不同于他們，我們算法是讓數(shù)據(jù)通過多條路徑尋求優(yōu)化系統(tǒng)壽命的，而不是通過單一路徑來尋求通信總成本的。限制母與父之間的數(shù)據(jù)單個路徑的尋址，而在不利影響使用壽命的情況下允許多個路徑的尋址。可以看到圖10，我們的方法采用最短路徑的路由算法在所有情況下的最佳位置實現(xiàn)了更好的壽命。</p><p>　

25、　Srivastava等人 [30]考慮有層次結構的放置網絡節(jié)點，逐步增加計算能力和網絡寬帶，這樣能使總成本的計算和通訊最小化。我們假設在一個不同的網絡模型中的傳感器的能量是受限均勻的且有不同的目標和優(yōu)化系統(tǒng)的壽命，這并不一定減少總成本的計算和通信。</p><p>　　Garg和Konemann[14]描述了一種接近并行流問題的迭代算法并最大限度的得到求解證明。它的LP 配方是不同于MLCF。他們的目標是最大限

26、度地提高網絡下邊緣有限總流量的容量，而我們是最大限度地提高網絡有限壽命和節(jié)點能量。此外，我們的 ALGRSM MLCF 算法在解決方案中是以路由的路徑數(shù)量為界的，而在算法[14]中發(fā)現(xiàn)解決方案，它們可以使用任意多個路由路徑作為迭代次數(shù)。因為有少部分路由路徑是重要的，所以在實踐中部分因為分發(fā)到傳感器中，而且相關的路由信息的使用保持較小，有較少的路徑。</p><p>　　Chang和 Tassiulas [7] 提

27、出了一種最短路徑的路由算法用來收集最大壽命的數(shù)據(jù)從而在每個環(huán)節(jié)的每個節(jié)點處反映通信能耗和剩余的能量。雖然他們還制訂了一個線性規(guī)劃的路由問題，他們通過其擬議的算法來獲得壽命與現(xiàn)實的壽命進行比較。我們制定的最優(yōu)路徑問題不同于線性規(guī)劃，我們的 ALGRSM MLCF 算法有效地直接的解決了 LP以獲得最佳路由。此外，在算法[7]的性能中是主要依賴參數(shù)所使用的算法，而ALGRSM MLCF是 非參數(shù)的。</p><p>

28、　　Wu等人[32]考慮使用一個給定的路由樹來興建發(fā)射/接收傳感器的時間表，以收集數(shù)據(jù)。他們描述了發(fā)送和接收槽的分配，減少傳輸過程中的碰撞，以及使用傳感器的方法。這項工作對我們的工作是有幫助的。Wu等人[32]只是假設一個路由樹，而我們的方法可在連續(xù)查詢的評估中構建了一個安置和路由。另一方面，我們ALGRSM MLCF算法不考慮沖突期間通過傳感器的傳輸。推導詳細的發(fā)送/接收安排位置/路由表也是重要的，他們的方法可能是一個步驟一個目標。&

29、lt;/p><p><b>　　3. 準備工作</b></p><p>　　我們利用整個文件記錄了定義和符號，其中包括簡單的模型，無線傳感器網絡的概念和表達式樹。</p><p>　　3.1. 共同的定義和符號</p><p>　　給定一個圖G，我們用V[G] 表示其頂點及用E[G]表示其邊緣集。為簡單起見，對于頂點v，我們

30、經常寫v∈G，而不是 v∈V[G] 和對于邊緣點ij寫 ij∈G，而不是 ij∈E [G] 。通過其頂點的一個子集讓G[V’]=(V’,E[G] ∩V’ ×V’) 成為G的子圖。在子圖 G 中誘導其邊緣的一個子集，我們通常用 G[A]=(V,A) 。</p><p>　　考慮邊緣有向圖G帶邊緣權W∈R|E|G||。邊緣IJ∈E[G] 的邊緣收縮圖G是從崩潰（合并）G頂點到頂點j得到的圖。一個頂點i到頂點

31、 j 的折疊，我們需要以下三個步驟圖：（一）如果KJ￠E[G]，則每個邊緣Wki權數(shù)為KI∈E[G]，然后添加權數(shù)WKI邊緣KJ至G，否則邊緣增加權數(shù)KJ到WKI，（b）如果JK￠E[G]。則每個邊緣IK2權數(shù)為IK∈E[G]， 然后添加權數(shù)WIK邊緣JK至G，否則增加的邊緣權數(shù)JK 到WIK，（c）刪除頂點i和任何自我循環(huán)G.（邊緣JJ）考慮分區(qū)Π=﹤V1，V2，…Vm﹥; 從頂點的分區(qū)G設置 V [G]，代替一些m﹥1。進一步我們通

32、過Π定義的縮圖G表示以下邊緣加權有向圖GΠ。 GΠ的頂點是Π，如果在IJ∈E[GΠ]的邊緣存在一個從Vi到Vj的G，即uv∈E[G]和u∈Vi,j∈Vj是邊緣的切緣。每邊的權數(shù)等于從Vi到Vj 的邊緣G晉級權數(shù)的總和。請注意，GΠ的獲得是G通過承包所有的內塊（未切割）邊緣圖的總和。</p><p>　　鑒于一實例優(yōu)化問題， opt（I）和sol（I）分別是最優(yōu)和最可行的解決方案。為簡單起見， opt(I) 和 s

33、ol(I) 將還相應的標明解決方案。相對誤差的解決方案 sol(I) 等于 opt(I)，其近似比等于 sol(I) / opt(I)。每當他們允許實例有未知數(shù)的分數(shù)值時。請我們參閱連續(xù)積分解決方案來優(yōu)化問題。</p><p>　　我們用小寫和大寫的粗體字母分別表示向量和矩陣，如X和A分別是矢量和矩陣。向量X被定義為 。由于兩個向量，我們說x主導y并寫成X≥ Y，如果其中我們說 x比 y大是按字典順序，來說明是否

34、索引一組最小的非零的x–y 正負。由于矩陣是一個單一列向量，許多符號/矩陣操作自然是延伸的向量。</p><p>　　我們用表示矩陣A的轉置。給了n × m 矩陣和兩個指數(shù)序列I屬于﹛1,2，…n﹜; J屬于﹛1;2;......n﹜，我們通過定義A的矩陣;其中由于我們延長的符號和 Ay 是索引集，一組指數(shù)序列始終通過其元素按升序排列轉換序列列出。</p><p>　　3.2.

35、無線傳感器網絡模型</p><p>　　考慮無線傳感器網絡 （WSN）的 n 個節(jié)點。一個節(jié)點用 b表示，其被指定為其余傳感器節(jié)點的基站。雖然傳感器被假定為有限的非補充能量，且傳感器通過唯一的 Id 來標識，所以基站沒有能源的限制?？拷鼈鞲衅鞲信d趣的點稱為數(shù)據(jù)源，而他們在預定義的數(shù)據(jù)速率中監(jiān)視和生成感測數(shù)據(jù)。在基站分析中連續(xù)查詢獲取數(shù)據(jù)并處理生成的數(shù)據(jù)源的數(shù)據(jù)構成，并被解析為一個表達式DAG。時間是離散的，被定義

36、的數(shù)據(jù)速率是傳感器節(jié)點在每隔一段時間內傳輸?shù)臄?shù)據(jù)包的數(shù)目。為簡單起見，我們假設數(shù)據(jù)包的大小是固定的。在系統(tǒng)壽命周期T是最早的時候，無線傳感器網絡在一個或多個傳感器中通過耗能來執(zhí)行其預定的任務（例如查詢評價）。</p><p>　　無線傳感器網絡的拓撲結構是仿照一個有向圖G=﹙V,E﹚的;用它來代替V=﹛1;2; ...... n﹜;和E屬于V×V。每當i能成功發(fā)送一個數(shù)據(jù)包到j，就存在ij∈E。讓距離在

37、i和j之間。為了從節(jié)點i發(fā)送一個數(shù)據(jù)包到節(jié)點j，讓 耗能，并讓的節(jié)點j收到了數(shù)據(jù)包所需的能量。為讓節(jié)點i可使用能源，我們認為εb=∞。</p><p>　　為簡單起見，我們假設在每個節(jié)點附近的單源節(jié)點是傳感器網絡的一個基站。實際部署中可以在相同的節(jié)點附近有多個傳感器，這將是理想的，他們共享的采集數(shù)據(jù)。相同節(jié)點周圍的所有傳感器可以收到其中任何一個信號，這可能是很容易做的。引入一個新的節(jié)點，與作為數(shù)據(jù)源，然后追加到G

38、，i附近的1/4范圍內為每個傳感器節(jié)點j，兩個新的邊和，同時和等于0。傳感器網絡同樣可以處理由多個基站引入的一個新的節(jié)點 ，作為新的單一基站，然后追加到G，每個基站為 I，的新的邊緣</p><p>　　在本文中，我們不考慮有關信號和信道干擾，傳輸調度是為了避免或減少這種干擾的問題。調度發(fā)射后可制定路由方案，這樣可在潛伏期增加查詢評價。</p><p>　　3.3一個復雜查詢的評估模型&l

39、t;/p><p>　　我們將介紹一個簡單的模型，我們將使用連續(xù) （重復） 處理的復雜查詢。在查詢中只有一個運算符（如添加、 相乘，等） 或只有一個操作符 （例如總和、 計數(shù)、 最小、 最大等）稱為簡單，否則它稱為復雜。過去我們對于復雜查詢是在傳感器網絡中關于傳感器的測量。在每輪感應期間，使用傳感器的當前度量單位 （可能是事先測量）查詢評估。</p><p>　　我們模型使用定向根值的表達圖 （

40、DAGs）查詢。表達圖DAG的一個根值Q是其一個單根（頂點沒有任何父母點），符合內部頂點的運算符（無兒無女的頂點）及對應常量或變量。每個頂點v∈V [Q]的 有關值不變，但不同的尺寸大?。╒）是衡量單位數(shù)據(jù)包大小的。uv∈E [Q ]每邊的權數(shù)是等于大小（U）。每個頂點有一個或多個操作數(shù)（子點），其主要是一個功能的操作。在 AND 運算符 （OR 運算符） 的模型中，對于運算符的功能的評價是需要所有 （任何一個） 其操作數(shù)參與的。<

41、;/p><p>　　表達的DAG出現(xiàn)在各個領域，如TinyDB的SQL連續(xù)查詢評價</p><p>　　選擇樓層，房間，AVG（溫度）</p><p><b>　　來自傳感器</b></p><p><b>　　地板<6</b></p><p><b>　　房間地

42、板</b></p><p>　　AVG（溫度）> 70</p><p><b>　　采樣周期30秒;</b></p><p>　　其中運算符是關系代數(shù)運算符，子葉是傳感器樣本 （測量），它們都有一個樹DAG表示。</p><p>　　當請求運算符可用時，需要評估運算符，可以用一個渴望（盡快）或懶惰（當它

43、需要輸出要求時）的方式表示。此評價在一定回合不需要分配綁定的值。在一個命令的程序中評價（可能不是全部）運算符，使其根值提供提供給用戶。</p><p>　　在表達DAG中設H為一個無線傳感器網絡并用Q來進行評估。我們調用主機圖H和客圖Q。在時間t中分配變量v∈V [G]值，這取決于測量src(v)屬于V [H ]，設置主機的網絡節(jié)點（傳感器）通常要設置v的數(shù)據(jù)源，設置一個變量的數(shù)據(jù)源可能是一個單件或是傳感器附近的

44、一小部分。</p><p>　　為了評估在主機h中的客體Q，我們需要在一個或多個主機節(jié)點上放置所有客體頂點。每個頂點v∈V [Q]可以在主機節(jié)點上被放置一個指定的候選節(jié)點如果V是一個變量，則每個在cands(v)中的候選主機節(jié)點（V）是V值評估的結果，如果有的話，一次向它提供其所需要的所有操作符，如果cands=則客頂點為v，如果則受到固定的限制，否則被稱為自由。我們擴展設置數(shù)據(jù)源，并設置任何客頂點子集而候選主機

45、作為和如果我們呼吁一個受理，圖1給出了一個示例查詢表達的DAG（樹）。</p><p>　　一個DAG中的客體節(jié)點Q被安置到主機的網絡H中去，則每個頂點v ∈V[Q]被放置了一個非空集的主機節(jié)點。每當一個頂點v∈V[Q]必要的時候，一個主機節(jié)點要求被提供，這樣做可能需要檢測或計算網絡節(jié)點i，甚至是計算i和其他主機的網絡之間的通信節(jié)點。圖 2 提供了示例并顯示了被放置到無線傳感器網絡上表達的DAG</p>

46、;<p><b>　　圖形1</b></p><p><b>　　圖形2</b></p><p>　　此后，我們只考慮位置，其中每個客體的頂點都被放置在一個主機節(jié)點上，即在主機的網絡中是不能復制客體頂點。</p><p>　　考慮將客體網絡DAG Q放置到主機網絡H。放置在同一主機節(jié)點的客體頂點集的候選集的交

47、集一般非空。因此，通過消除放置在不同主機節(jié)點的客體頂點邊緣（切邊），我們能夠得到關于客體圖的連接組件的集合，這樣所有的連接組件的頂點Vi就被放置在同一主機節(jié)點ui。換言之，將客體Q放置在主機H會引起V[Q] 的分區(qū)，這樣所有Vi的客體頂點將被放置在主機節(jié)點 請注意，的每塊區(qū)Vi是可以受理的—我們稱這種分區(qū)為允許分區(qū)。此外，每一輪Q的評估中的傳輸數(shù)據(jù)量等于切邊的總成本，其中，切邊指的是由放置引起的。換言之，給定放置中Q的單個評估所需要的總

48、傳輸量等于通過分區(qū)的Q的收縮的總重量。事實上，從主機節(jié)點ui至客體節(jié)點uj所需的傳輸總量相對于中邊緣ViVj的重量。確定相當于每輪評估Q中總傳輸總量的放置成本。通過重新標記每個頂點，其中Vi中的客體頂點被放置在主機節(jié)點ui，從而確定放置傳輸需求圖R 成為從中獲取的圖。由于客體頂點放置在 和 ，邊緣的量等于每輪從主機節(jié)點ui到主機節(jié)點u所需的總傳輸數(shù)據(jù)量。</p><p>　　我們在放置通信節(jié)點中定義最小 Q 到

49、H 上的成本(MCP) 問題是為了尋找到候選主機頂點上以最低的成本 （傳送數(shù)據(jù)的量）的位置。由于Q安置到主機h上并且誘導分隔邊緣的位置，本質上它是遵循的MCP問題等同于下面的總權數(shù)圖劃分問題的。我們?yōu)榱思s束定義分區(qū) （MCCP）最小成本 的問題，如下所示：任何邊緣加權圖G和一個函數(shù)找到這樣一個最低的成本切邊（邊割），非空為每個連接組件的Gi G-A.MCCP問題實例的最佳解決方案，也是為客體Q 到主機 H的 MCP 問題的最佳解決方案，

50、反之亦然。我們研究了 4.2 節(jié)的 MCP 和 MCCP 問題的復雜性。</p><p>　　鑒于已將客體Q放置到主機H，我們現(xiàn)在需要找到一種高效節(jié)能的方式以滿足傳輸需求圖R所傳達的數(shù)據(jù)路徑需要，從而使系統(tǒng)使用期限最大化。換言之，我們需要找到最大使用期限T以及滿足為收集起點—終點對數(shù)（邊緣）的傳輸需求的路徑，其中需求等于從主機節(jié)點Si到主機節(jié)點di的邊緣重量（一輪中所需傳輸數(shù)據(jù)量）。這就是我們在第5節(jié)中有考慮過的

51、最大使用期限并行流（MLCF）問題。</p><p>　　在本文中，我們假設了表達式DAGs和AND-算法模式。同樣，我們也假設變量v ∈V [Q]的數(shù)據(jù)源是單個的，因此v固定在其單個數(shù)據(jù)源主機網絡節(jié)點上。此外，我們假設Q根固定在基站且Q的頂點放置不會被復制，即，對于所有的v∈V[Q]來說，。并且，我們還以為，無論在計算運算符v值的時候，還是在測量和分配變量v值的時候，或者是在配備常量v值的時候所消耗的能源，相比

52、于所有頂點v ∈V[Q]的傳輸所消耗的能源來說，都是不容忽視的。</p><p><b>　　外文原文</b></p><p>　　Maximum lifetime continuous query processing in wireless sensor networks</p><p>　　Konstantinos Kalpakis* ,

53、 Shilang Tang</p><p>　　Computer Science and Electrical Engineering Department, University of Maryland, Baltimore</p><p><b>　　ABSTRACT</b></p><p>　　Monitoring application

54、s 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. Du

55、e 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 network can not perform its intended task anymore.</p><

56、;p>　　We model complex queries by expression trees and consider the problem of maximizing the lifetime of a wireless sensor network for the continuous in–network evaluation of an expression trees T , so the value of it

57、s 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). C

58、ontinuous in-network evaluation of T entails addressing the followin</p><p>　　We analyze the complexity and provide a simple and effective algorithm for the placement of the nodes of T onto the sensor nodes

59、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 Flow (MLCF) problem. We provide an

60、efficient algorithm that finds near-optimal integral solutions to the MLCF problem, where a solution is a collection of paths on which certain amount o</p><p>　　We demonstrate experimentally that our approac

61、h consistently and effectively find the maximum lifetime solutions for the continuous in-network evaluation of </p><p>　　《無線傳感網絡》課程論文</p><p>　　expression trees in wireless sensor networks.</p

62、><p>　　Introduction</p><p>　　Remote monitoring applications are one of the most attractive applications of wireless sensor networks. Such applications, like environmental monitoring and building su

63、rveillance, 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 – re

64、port the current activity level every five minutes, which is measured by processing and correlating the data str</p><p>　　In this paper, we consider the task of the continuous evaluation of long-running comp

65、lex 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 senso

66、rs and the amount of 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 expr</p><p>　　Th

67、e continuous in-network evaluation 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 ro

68、uting of the operand values to the appropriate network nodes that needed them to evaluate the operators. These two aspects are coupled because the placement of Q imposes certain source–destination routing requirements am

69、ong the sensor nodes, and the manner in which routing is p</p><p>　　While there are many important optimization goals for the continuous in-network evaluation of queries (e.g. response time, reliability, etc

70、.), we focus on maximizing the system lifetime – the time until the sensor network losses its ability to perform its </p><p>　　《無線傳感網絡》課程論文</p><p>　　intended task due to depletion of energy at (

71、some of) its sensors, and analyze how to decouple the two aspects 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

72、 routing and placement aspects, and therefore allows us to solve these two aspects one at a time.</p><p>　　To find a near optimal solution to the placement aspect of the task, we consider the minimum communi

73、cation 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.

74、We show that the MCP problem 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 GREEDYMC</p><p>　　To find a near op

75、timal 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 satisf

76、y the data rate demands for a given set of source–destination pairs. 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 maximiz

77、e the fractional system lifetime To for sat</p><p>　　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 place

78、ment of Q on the network, and we use ALGRSM-MLCF for routing all the data values that need to be communicated. We show, through an extensive experimental evaluation, that our approach consistently finds the maximum lifet

79、ime </p><p>　　《無線傳感網絡》課程論文</p><p>　　《無線傳感網絡》課程論文</p><p>　　solution for the continuous in-network evaluation of complex queries in wireless sensor networks. Although we take a centra

80、lized 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 t

81、hat the small size of the routing solution found by our approach limits the overhead of distributing the routing information to the sensors.</p><p>　　In summary, for the task of continuous in-network process

82、ing of complex queries in wireless sensor networks (WSNs), the original contributions of this paper are as follows:</p><p>　　·theoretically analyze the complexity of the MCP problem, the problem of plac

83、ing expression DAGs on WSNs with minimum total communication cost.</p><p>　　·provide a greedy heuristic GREEDYMCP , for the MCP problem. GREEDYMCP finds provably optimal solutions in practical useful ca

84、ses.</p><p>　　·provide a simple and effective algorithm, ALGRSM-MLCF, that finds near optimal integral solutions to the maximum lifetime concurrent flow (MLCF) problem in WSNs . ALGRSM-MLCF outperforms

85、existing routing methods.</p><p>　　·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.</p><p>　　

86、·our approach, consisting of using GREEDYMCP and ALGRSM-MLCF together is both effective and efficient at maximizing the system lifetime.</p><p>　　The rest of the paper is organized as follows. We review

87、 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 optim

88、al solutions to MCP problem instances under certain conditions . We analyze the complexity of the MCP problem in Section 4.2 and show that the MCP problem is MAX SNP-hard even for trees of height 1 and unit cost edged p

89、rovi</p><p>　　Related work</p><p>　　Pietzuch et al. [26] consider network-aware operator placement in conventional distributed stream processing systems. In similar network settings, Ahmad et al

90、. [1] give three operator placement algorithms for constructing a query processing overlay </p><p>　　《無線傳感網絡》課程論文</p><p>　　network and compare their performance. The network considered by them i

91、s internet style and consists of nodes with ample computational power, which is very different from the energy-limited wireless sensor networks we consider.</p><p>　　In wireless sensor networks, the notion o

92、f in-network processing was first introduced by Intanagonwiwat et al. [18] to opportunistically eliminate duplicates in the context of directed diffusion. Gehrke and Madden et al.[11,15,24] are among the first to integra

93、te query processing and sensor networks so tasking sensor networks can be easily done through declarative queries. In the Cougar project [11], a layered architecture of sensor data management is proposed for presenting t

94、he sensor network a</p><p>　　Ren et al .[27] consider quality aware processing of simple aggregate queries (e.g. compute the average, min, max of measurements of sensors in a rectangular area of interest). A

95、 centralized algorithm is proposed to find a subset of sensors whose measurements are collected using reactive routing to the base station to compute a probabilistic answer. Hu et al. [17], expanding upon the work of Ols

96、ton and Widom[25],are concerned with approximate answers to continuous aggregate queries (sum, mean, c</p><p>　　Many researchers have advocated the use of data-centric techniques that allow for efficient in-

97、network storage and retrieval of named data using queries [16]. A number of data-centric push-pull query processing techniques have been proposed and examined [6,8,23,28,29,31], which can be categorized to two main appro

98、aches: structured and unstructured, which can be represented by the geographic hash-based </p><p>　　《無線傳感網絡》課程論文</p><p>　　data-centric storage technique [29] and the comb-needle method [23] resp

99、ectively. Kapadia and Krishnamachari [20] present a comparative mathematical analysis of these two approaches based on two types of simple one-shot queries (ALL-type and ANY-type) in single-sink square-grid sensor networ

100、ks, and later on, Ahn and Krishnamachari [2] find that the scalability of a data-centric sensor networks performance depends upon whether or not the increase in energy and storage resources with more nodes is</p>

101、<p>　　Bonfils et al. [5] consider the placement of operators of a query expression tree to the nodes of a sensor network to minimize the total communication cost of evaluating such a tree. For any pair of parent-chi

102、ld operators in the query tree, the induced communication cost is the product of the length of a shortest path between the nodes, where these operators are placed and the data rate from the child to its parent. They prov