外文翻譯---基于最長(zhǎng)壽命的無(wú)線傳感器網(wǎng)絡(luò)連續(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è)設(shè)

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

3、;p>　　監(jiān)測(cè)應(yīng)用成為無(wú)線傳感器網(wǎng)絡(luò)（WSNS）最重要的應(yīng)用之一。這類應(yīng)用通常具有長(zhǎng)期運(yùn)行的復(fù)雜查詢處理技術(shù)且通過(guò)傳感器流對(duì)此處理技術(shù)進(jìn)行評(píng)估?；跓o(wú)線傳感器網(wǎng)絡(luò)中傳感器的能量有限，高效節(jié)能查詢的評(píng)價(jià)對(duì)于延長(zhǎng)系統(tǒng)使用壽命來(lái)說(shuō)是至關(guān)重要的—使用期限指的是此網(wǎng)絡(luò)查詢從開(kāi)始到停止所執(zhí)行其預(yù)定任務(wù)的最早時(shí)間。</p><p>　　我們通過(guò)使用表達(dá)式樹(shù)對(duì)復(fù)雜查詢進(jìn)行建模。我們考慮使無(wú)線傳感器網(wǎng)絡(luò)的使用期限最大化以達(dá)成

4、表達(dá)式樹(shù)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)估需要解決以下問(wèn)題的兩個(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)算符。</p><p>　　我們對(duì)其復(fù)雜性進(jìn)行了分析，并且為T節(jié)點(diǎn)在WSN傳感器節(jié)點(diǎn)上的放置提供了一種簡(jiǎn)

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

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

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

8、算符。由于在傳感器網(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é)果給該變量。</p><p>　　在網(wǎng)絡(luò)DAG中評(píng)價(jià)連續(xù)Q的表達(dá)根需要解決以下兩個(gè)方面的任務(wù)：（

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

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

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

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

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

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

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

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

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

18、/p><p>　　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ú)線傳感器網(wǎng)絡(luò)。</p><p>　　在無(wú)線傳感器網(wǎng)絡(luò)中，由于Intanagonwiwat等人在一定的背景下，網(wǎng)絡(luò)處

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

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

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

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

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

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

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

26、度地提高網(wǎng)絡(luò)下邊緣有限總流量的容量，而我們是最大限度地提高網(wǎng)絡(luò)有限壽命和節(jié)點(diǎn)能量。此外，我們的 ALGRSM MLCF 算法在解決方案中是以路由的路徑數(shù)量為界的，而在算法[14]中發(fā)現(xiàn)解決方案，它們可以使用任意多個(gè)路由路徑作為迭代次數(shù)。因?yàn)橛猩俨糠致酚陕窂绞侵匾?，所以在?shí)踐中部分因?yàn)榉职l(fā)到傳感器中，而且相關(guān)的路由信息的使用保持較小，有較少的路徑。</p><p>　　Chang和 Tassiulas [7] 提

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

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

29、lt;/p><p><b>　　3. 準(zhǔn)備工作</b></p><p>　　我們利用整個(gè)文件記錄了定義和符號(hào)，其中包括簡(jiǎn)單的模型，無(wú)線傳感器網(wǎng)絡(luò)的概念和表達(dá)式樹(shù)。</p><p>　　3.1. 共同的定義和符號(hào)</p><p>　　給定一個(gè)圖G，我們用V[G] 表示其頂點(diǎn)及用E[G]表示其邊緣集。為簡(jiǎn)單起見(jiàn)，對(duì)于頂點(diǎn)v，我們

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

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

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

33、ol(I) 將還相應(yīng)的標(biāo)明解決方案。相對(duì)誤差的解決方案 sol(I) 等于 opt(I)，其近似比等于 sol(I) / opt(I)。每當(dāng)他們?cè)试S實(shí)例有未知數(shù)的分?jǐn)?shù)值時(shí)。請(qǐng)我們參閱連續(xù)積分解決方案來(lái)優(yōu)化問(wèn)題。</p><p>　　我們用小寫和大寫的粗體字母分別表示向量和矩陣，如X和A分別是矢量和矩陣。向量X被定義為 。由于兩個(gè)向量，我們說(shuō)x主導(dǎo)y并寫成X≥ Y，如果其中我們說(shuō) x比 y大是按字典順序，來(lái)說(shuō)明是否

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

35、無(wú)線傳感器網(wǎng)絡(luò)模型</p><p>　　考慮無(wú)線傳感器網(wǎng)絡(luò) （WSN）的 n 個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)用 b表示，其被指定為其余傳感器節(jié)點(diǎn)的基站。雖然傳感器被假定為有限的非補(bǔ)充能量，且傳感器通過(guò)唯一的 Id 來(lái)標(biāo)識(shí)，所以基站沒(méi)有能源的限制。靠近傳感器感興趣的點(diǎn)稱為數(shù)據(jù)源，而他們?cè)陬A(yù)定義的數(shù)據(jù)速率中監(jiān)視和生成感測(cè)數(shù)據(jù)。在基站分析中連續(xù)查詢獲取數(shù)據(jù)并處理生成的數(shù)據(jù)源的數(shù)據(jù)構(gòu)成，并被解析為一個(gè)表達(dá)式DAG。時(shí)間是離散的，被定義

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

37、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=∞。</p><p>　　為簡(jiǎn)單起見(jiàn)，我們假設(shè)在每個(gè)節(jié)點(diǎn)附近的單源節(jié)點(diǎn)是傳感器網(wǎng)絡(luò)的一個(gè)基站。實(shí)際部署中可以在相同的節(jié)點(diǎn)附近有多個(gè)傳感器，這將是理想的，他們共享的采集數(shù)據(jù)。相同節(jié)點(diǎn)周圍的所有傳感器可以收到其中任何一個(gè)信號(hào)，這可能是很容易做的。引入一個(gè)新的節(jié)點(diǎn)，與作為數(shù)據(jù)源，然后追加到G

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

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

40、DAGs）查詢。表達(dá)圖DAG的一個(gè)根值Q是其一個(gè)單根（頂點(diǎn)沒(méi)有任何父母點(diǎn)），符合內(nèi)部頂點(diǎn)的運(yùn)算符（無(wú)兒無(wú)女的頂點(diǎn)）及對(duì)應(yīng)常量或變量。每個(gè)頂點(diǎn)v∈V [Q]的 有關(guān)值不變，但不同的尺寸大小（V）是衡量單位數(shù)據(jù)包大小的。uv∈E [Q ]每邊的權(quán)數(shù)是等于大小（U）。每個(gè)頂點(diǎn)有一個(gè)或多個(gè)操作數(shù)（子點(diǎn)），其主要是一個(gè)功能的操作。在 AND 運(yùn)算符 （OR 運(yùn)算符） 的模型中，對(duì)于運(yùn)算符的功能的評(píng)價(jià)是需要所有 （任何一個(gè)） 其操作數(shù)參與的。<

41、;/p><p>　　表達(dá)的DAG出現(xiàn)在各個(gè)領(lǐng)域，如TinyDB的SQL連續(xù)查詢?cè)u(píng)價(jià)</p><p>　　選擇樓層，房間，AVG（溫度）</p><p><b>　　來(lái)自傳感器</b></p><p><b>　　地板<6</b></p><p><b>　　房間地

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

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

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

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

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

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

48、傳輸量等于通過(guò)分區(qū)的Q的收縮的總重量。事實(shí)上，從主機(jī)節(jié)點(diǎn)ui至客體節(jié)點(diǎn)uj所需的傳輸總量相對(duì)于中邊緣ViVj的重量。確定相當(dāng)于每輪評(píng)估Q中總傳輸總量的放置成本。通過(guò)重新標(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ù)量。</p><p>　　我們?cè)诜胖猛ㄐ殴?jié)點(diǎn)中定義最小 Q 到

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

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

51、最大使用期限并行流（MLCF）問(wèn)題。</p><p>　　在本文中，我們假設(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)放置不會(huì)被復(fù)制，即，對(duì)于所有的v∈V[Q]來(lái)說(shuō)，。并且，我們還以為，無(wú)論在計(jì)算運(yùn)算符v值的時(shí)候，還是在測(cè)量和分配變量v值的時(shí)候，或者是在配備常量v值的時(shí)候所消耗的能源，相比

52、于所有頂點(diǎn)v ∈V[Q]的傳輸所消耗的能源來(lái)說(shuō)，都是不容忽視的。</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>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</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>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</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>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</p><p>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</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>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</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>　　《無(wú)線傳感網(wǎng)絡(luò)》課程論文</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