無線傳感器網(wǎng)絡(luò)中基于采樣的查詢處理方法研究

宋春暉 趙洪剛

1 黑龍江農(nóng)業(yè)工程職業(yè)學(xué)院信息學(xué)院 黑龍江 150088

2 黑龍江大學(xué)信息技術(shù)研究所 黑龍江 150080

0 前言

無線傳感器網(wǎng)絡(luò)產(chǎn)生大量的分布式感知數(shù)據(jù)，有效地掌握這些感知數(shù)據(jù)是傳感器網(wǎng)絡(luò)使用者的最終目的。在查詢過程中最小化無線通訊數(shù)據(jù)量，將節(jié)約十分可觀的能量，從而延長無線傳感器網(wǎng)絡(luò)的生命周期。因此，對感知數(shù)據(jù)查詢處理技術(shù)的研究具有重要意義。

1 感知數(shù)據(jù)的查詢處理

以前，對感知數(shù)據(jù)進行管理和處理是由應(yīng)用程序來實現(xiàn)，這需花費大量的時間和精力，限制了無線傳感器網(wǎng)絡(luò)的發(fā)展。研究表明：可以用一套與傳統(tǒng)設(shè)計方法不同的、以數(shù)據(jù)為中心的思想來解決上述問題。

感知數(shù)據(jù)查詢處理系統(tǒng)包括兩部分。即：運行在基站或計算機上的查詢處理軟件和運行在傳感器節(jié)點上的傳感器端軟件。前者主要功能是查詢解析、檢查、進行查詢優(yōu)化并將優(yōu)化后的查詢以“多跳”路由方式分發(fā)到傳感器網(wǎng)絡(luò)中，然后收集感知數(shù)據(jù)并以“多跳”路由方式將數(shù)據(jù)返回到基站或計算機上。后者進行查詢接收、查詢處理、采樣和通信等操作，是一組分層次的組件。

可將感知數(shù)據(jù)具體查詢處理執(zhí)行過程描述如下：

(1) 用戶在查詢處理界面指定查詢?nèi)蝿?wù)。

(2) 查詢處理模塊獲取用戶輸入信息，并進行查詢解析及檢查操作。

(3) 查詢處理模塊將解析、檢查后的查詢命令轉(zhuǎn)化為一種內(nèi)部結(jié)構(gòu)交給優(yōu)化器。

(4) 優(yōu)化器對來自查詢處理模塊的查詢命令進行基于查詢代價的優(yōu)化。

(5) 優(yōu)化器從優(yōu)化后的一組查詢計劃中選擇代價最低的查詢計劃轉(zhuǎn)化為具體的、即將被執(zhí)行的查詢語句。

(6)查詢處理模塊將上一步中產(chǎn)生的查詢語句按照一定的路由策略通過網(wǎng)絡(luò)管理器分發(fā)到各個節(jié)點。

(7) 節(jié)點按照查詢處理請求收集感知數(shù)據(jù)，同時進行最大化的感知數(shù)據(jù)本地處理。

(8) 節(jié)點將處理后的數(shù)據(jù)沿查詢分發(fā)過程建立的路由樹傳播給雙親節(jié)點。

(9) 雙親節(jié)點進一步將其轉(zhuǎn)發(fā)或?qū)⑵渑c自己收集并處理后的數(shù)據(jù)、或從其他子節(jié)點收集到的數(shù)據(jù)進行合并后再轉(zhuǎn)發(fā)。

(10) 如此不斷進行下去，直到基站收集到用戶感興趣的數(shù)據(jù)為止。

2 基于采樣的查詢方法

采樣方法的本質(zhì)是避免列舉整個樣本分布，通過在優(yōu)化查詢過程中列舉大量樣本來近似代替聯(lián)合分布。優(yōu)化的目的是在所有傳感器節(jié)點感知數(shù)據(jù)值中盡量減少錯誤數(shù)量。

PROSPECTORGREEDY方法簡單的通過一次貪心地增加獲取的感知數(shù)據(jù)值的方式構(gòu)建一個查詢計劃。首先要給出所有樣本中每個傳感器節(jié)點對最后查詢結(jié)果的貢獻的優(yōu)先權(quán)。只要查詢計劃的能量消耗沒有超出預(yù)算，算法會貪心的最大化挖掘傳感器節(jié)點ui的 ∑SS[s,i]值，并擴張當前查詢計劃來獲得傳感器節(jié)點ui的感知數(shù)據(jù)值。

3 PROSPECTORPROOF算法及其優(yōu)化

本節(jié)設(shè)計一種新的例證方法，它以自下而上的形式，通過傳遞一個附加值來校對返回值，從而提高算法的準確性。

3.1 參數(shù)說明

(1) 用S表示一個布爾樣本矩陣，其含義與前文相同。

(2) 用ones(s)表示為第s個樣本提供前k個感知數(shù)據(jù)值的一組節(jié)點。

(3) 用smallers(ui,uj)表示第s個樣本中以節(jié)點uj為根的子樹中的一組節(jié)點，這些節(jié)點的感知數(shù)據(jù)值要比節(jié)點ui上的感知數(shù)據(jù)值小。

(4) 用一個變量b(ei) 表示為網(wǎng)絡(luò)中的每條邊ei所分配的帶寬。在此算法中，不需要變量α(ei)表示查詢計劃是否用到了ei這條邊。原因是例證查詢計劃必須用到網(wǎng)絡(luò)中的所有邊，否則無法證明前一個感知數(shù)據(jù)值，因為任何未被例證查詢計劃訪問的傳感器節(jié)點都可能產(chǎn)生最大的感知數(shù)據(jù)值。

(5) 用一個整型變量 xs(ui,uj)表示當查詢計劃運行到第 s個樣本時，傳感器節(jié)點ui的感知數(shù)據(jù)值是否被節(jié)點uj證明，其中：ui∈desc(uj)。

(6) 用r表示根節(jié)點。

(7) 用sibling(ui,uj)表示一組傳感器節(jié)點，這些傳感器節(jié)點是uj的孩子節(jié)點同時又不是節(jié)點ui的祖先。

3.2 PROSPECTORPROOF算法

在傳統(tǒng)的查詢方法中，網(wǎng)絡(luò)中的每一條邊都被分配給一定的帶寬b(ei)，指定節(jié)點ui所允許通過的最大感知數(shù)據(jù)量。節(jié)點ui將保證在分配的b(ei)個帶寬中感知數(shù)據(jù)能夠被返回，在以節(jié)點ui為根的子樹中，大小為l的子集真正包含有前l(fā)個感知數(shù)據(jù)值。這時，稱這l個感知數(shù)據(jù)值被節(jié)點ui證明。在例證計劃執(zhí)行過程中，每個節(jié)點ui都按照以下步驟執(zhí)行：

(1) 從子樹中收到返回值。節(jié)點 ui從其每個孩子節(jié)點 uj收到b(ei)個感知數(shù)據(jù)值，在這些值中，前k個感知數(shù)據(jù)值被節(jié)點uj證明。

(2) 排序。節(jié)點 ui將從其孩子節(jié)點中收集到的所有感知數(shù)據(jù)和它自身的感知數(shù)據(jù)值進行排序，選擇出即將要被上傳的前b(ei)個感知數(shù)據(jù)值。

(3) 證明感知數(shù)據(jù)值。考慮在前 b(ei)個中的、即將要被上傳的每個感知數(shù)據(jù)值y，這個感知數(shù)據(jù)值被節(jié)點ui證明。

(4) 將感知數(shù)據(jù)值返回給雙親節(jié)點。前 b(ei)個感知數(shù)據(jù)值都要傳遞給節(jié)點 ui的雙親節(jié)點 parent(ui)。如果被節(jié)點 uj證明的感知數(shù)據(jù)的數(shù)量小于b(ei)，那么這個數(shù)量值也要被上傳給其雙親節(jié)點；如果這個數(shù)量值不小于b(ei)，那么所有b(ei)個感知數(shù)據(jù)值也都假定已被證明。

這種優(yōu)化節(jié)約了通訊所帶來的能量消耗，這個來自子樹的數(shù)量值極有可能證明它們所傳遞的所有感知數(shù)據(jù)，完全排除要從葉子節(jié)點傳遞這個值的必要性。

在上述執(zhí)行過程的末尾，根節(jié)點返回一系列的感知數(shù)據(jù)值作為查詢操作的結(jié)果，同時，這些查詢操作的結(jié)果證明了它們中的前 'k個感知數(shù)據(jù)值在整個目標無線傳感器網(wǎng)絡(luò)中也是前 'k個感知數(shù)據(jù)值。實際上，被根節(jié)點返回的其他感知數(shù)據(jù)值可能在也可能不在前k個感知數(shù)據(jù)值中，但是對觀察者來說，它們可能仍然有用。就是說，它們有助于構(gòu)建一個更有效率的向上掃描查詢計劃，來找回遺漏的前k個感知數(shù)據(jù)值，下一步將研究這個問題。

下面的這個引理是直接描述例證查詢執(zhí)行計劃的：

引理：在例證查詢計劃中，被某個傳感器節(jié)點證明了的l個感知數(shù)據(jù)真正是以這個節(jié)點為根的子樹中的前l(fā)個感知數(shù)據(jù)。下面用一系列的線性規(guī)劃公式來表達在已分配帶寬的例證查詢執(zhí)行計劃中的優(yōu)化問題。如下所示：

式(1)說明查詢優(yōu)化的目標是通過所有樣本，最大化被根節(jié)點證明的前k個感知數(shù)據(jù)值中的數(shù)量。

式(2)指定查詢計劃的總的能量限制。發(fā)送被節(jié)點證明的感知數(shù)據(jù)的數(shù)量的能量消耗非常小，可以被適當?shù)仡A(yù)算在非葉子傳感器節(jié)點的固定的能量消耗中。

式(3)指明帶寬約束限制。與PROSPECTORLP+LF算法相似。

式(4)說明任何一個感知數(shù)據(jù)值被某一傳感器節(jié)點證明的約束，這個感知數(shù)據(jù)值必須被這個節(jié)點和擁有這個感知數(shù)據(jù)值的節(jié)點之間的所有傳感器節(jié)點證明。

式(5)指明例證約束限制。也就是說，對于來自傳感器節(jié)點 ui的感知數(shù)據(jù)值 y想被節(jié)點 uj證明，要求傳感器節(jié)點 uj的每個孩子節(jié)點uk(除了上傳出y的那個孩子節(jié)點)必須證明一些更小的感知數(shù)據(jù)值。

式(6)指明變量xs(ui,uj)的完整性約束。

本節(jié)論述的 PROSPECTORPROOF算法采用一個變量xs(ui,uj)代替了后者采用的 xs(ui)個變量而又沒有降低算法的整體性能。該算法的查詢結(jié)果要更為準確，但是它也存在著不足，即是前面提到的例外：當孩子節(jié)點uk真正返回以節(jié)點uk為根的子樹中的所有感知數(shù)據(jù)值的時候，這些感知數(shù)據(jù)值中沒有比y更小的了。針對這種情況可以對算法進行改進以提高其查詢操作的準確性和算法的可用性。

4 改進的PROSPECTORPROOF算法

PROSPECTORPROOF算法雖然與前面的查詢方法相比有很大提高，但是它在實際運行的過程中也存在一些例外，使得算法沒有更好的可適應(yīng)性。因此，可以對以上所述的算法進行改進，從其例外的條件開始改進算法，以使改進后的算法總能夠返回更確切的感知數(shù)據(jù)值。

改進的算法的基本思想是利用PROSPECTORPROOF算法作為前一部分，如果傳感器根節(jié)點能夠證明所有前k個感知數(shù)據(jù)值，那么結(jié)束查詢操作。否則，執(zhí)行本算法的第二部分——“向上掃描”操作來重新查詢被遺漏或未被證明的前k個感知數(shù)據(jù)值。

本算法第二部分的執(zhí)行要依賴于第一部分運行所搜集的信息來縮小查詢范圍。最佳情況是第一部分產(chǎn)生合理的查詢結(jié)果，這樣第二部分執(zhí)行起來將會變得十分容易甚至不需要執(zhí)行第二部分。

假設(shè)及參數(shù)說明：

(1) 假定在第一階段，每個傳感器節(jié)點 ui記住了它自身的感知數(shù)據(jù)值和這個傳感器節(jié)點的孩子節(jié)點所傳過來的感知數(shù)據(jù)值。

(2) 用retrieved(ui)表示上述假設(shè)中節(jié)點ui所記住的一組感知數(shù)據(jù)值。

(3) 假設(shè)傳感器節(jié)點 ui同樣記住了這些感知數(shù)據(jù)值中被節(jié)點ui證明的感知數(shù)據(jù)值。

(4) 用proven(ui)表示傳感器節(jié)點ui記住的感知數(shù)據(jù)值中被它證明的一組感知數(shù)據(jù)值。改進的 PROSPECTORPROOF算法主體：

在本算法中，將PROSPECTORPROOF算法作為第一部分，當?shù)谝徊糠值倪\行得到了觀察者滿意的結(jié)果時，本算法結(jié)束；否則，進入本算法的主體部分進行進一步的優(yōu)化查詢。現(xiàn)在研究改進算法的第二部分執(zhí)行流程：

(1) 接收雙親節(jié)點的請求

傳感器節(jié)點ui接收來自parent(ui)的一個三元組(l,ya,yb)，這個三元組的功能是請求網(wǎng)絡(luò)中的傳感器節(jié)點ui返回前一個感知數(shù)據(jù)值，請求返回的值要在ya和yb之間。

(2) 將要求發(fā)送給孩子節(jié)點

傳感器節(jié)點 ui按照如下步驟構(gòu)造一個查詢請求(l’,ya’,yb’)：

①l'=l-|proven(ui)∩(ya,yb)|。傳感器節(jié)點ui能夠利用已經(jīng)被證明的感知數(shù)據(jù)值來回復(fù)查詢要求，這些值來自節(jié)點ui的雙親節(jié)點。只有剩余部分的查詢請求需要被發(fā)送給它的孩子節(jié)點。

②ya'=max(ya,y)。其中 y是 retrieved(ui)∩(ya,yb)中的第l個感知數(shù)據(jù)值，如果這個值存在并且不是-∞的話。也就是說為了能在 ya和 yb之間，任何感知數(shù)據(jù)值至少必須比ya大才可以。

③ yb'=min(yb,min(proven(ui)))。傳感器節(jié)點ui應(yīng)該不需要向它的孩子節(jié)點請求任何比min(proven(ui))大的感知數(shù)據(jù)值，因為所有這些節(jié)點必須已經(jīng)在 proven(ui)中。如果l’>0 并且 (ya,yb)≠φ，那么傳感器節(jié)點ui就將這個請求以廣播的方式發(fā)送給它的孩子節(jié)點。

(3) 接收并返回查詢結(jié)果

如果傳感器節(jié)點ui在前面的步驟中已經(jīng)向其孩子節(jié)點發(fā)送了請求，它將會收到感知數(shù)據(jù)值并將這些值加入到retrieved(ui)中。最后，傳感器節(jié)點 ui將retrieved(ui)∩(ya,yb)中的前一個感知數(shù)據(jù)值返回給它的雙親節(jié)點。

查詢操作的啟動過程如下：當感知數(shù)據(jù)值 y是retrieved(r)中的第k大的值時，根節(jié)點r以廣播的方式啟動本算法的第二部分，向其節(jié)點的孩子節(jié)點發(fā)送查詢請求(k-k',y,min(proven(r)))，然后各傳感器節(jié)點按照預(yù)先設(shè)定的規(guī)則執(zhí)行此查詢操作，并返回確定的查詢結(jié)果。

5 總結(jié)

本文具體描述了PROSPECTORPROOF算法的實現(xiàn)。算法要求節(jié)點將收到的來自其子樹的感知數(shù)據(jù)值和它自身的感知數(shù)據(jù)值排成一個有序序列。檢查傳感器節(jié)點ui能否證明每個即將要上傳給雙親節(jié)點parent(ui)的感知數(shù)據(jù)值。如果即將要被節(jié)點ui上傳的所有感知數(shù)據(jù)值都能夠被節(jié)點ui證明，則直接將這些感知數(shù)據(jù)值上傳，否則，將要被上傳的感知數(shù)據(jù)值中被節(jié)點 ui證明的感知數(shù)據(jù)的數(shù)量值也上傳給節(jié)點 ui的雙親節(jié)點。通過這個上傳的數(shù)量值就能夠證明它所傳遞的所有感知數(shù)據(jù)值，排除了從葉子節(jié)點傳遞這個值的必要性，實現(xiàn)了算法的功能又降低了整體通訊量。

本文提出的基于的PROSPECTORPROOF改進算法，以PROSPECTORPROOF算法作為第一部分，如果第一部分返回的值都已被傳感器根節(jié)點證明，那么不需要此算法；否則，執(zhí)行改進算法的第二部分。在改進算法的第二部分中利用了前一部分PROSPECTORPROOF算法中返回的被根節(jié)點證明的數(shù)據(jù)量，根據(jù)這個數(shù)據(jù)量以及返回的查詢結(jié)果，確定一個三元組(l,ya,yb)，并將查詢請求的消息從根節(jié)點開始廣播到其各個孩子節(jié)點，直到返回了確切的感知數(shù)據(jù)值，本算法結(jié)束。改進的算法利用了前一算法產(chǎn)生的數(shù)據(jù)，將查詢范圍一步步縮小，最后得到理想的查詢結(jié)果。新算法引入了本地過濾的查詢策略，在傳感器節(jié)點自身將感知數(shù)據(jù)過濾，大大減少了傳感器節(jié)點間的通訊量，從而降低了算法的能耗。實驗數(shù)據(jù)表明，在不影響數(shù)據(jù)精確度的情況下，系統(tǒng)能耗減少11.5%，算法具有很好的實用性能。

[1] 李建中.無線傳感器網(wǎng)絡(luò)專刊前言[J].軟件學(xué)報.2007.

[2] Pottie GJ,Kaiser WJ.Wireless integrated newtork sensors.Communications of the ACM.2000.

[3] 李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進展[J].軟件學(xué)報.2003.

[4] Schurgers C and Srivastava MB."Energy efficient routing in wireless Network-Centric Operations:Creating the Information Force.Virginia:IEEE Communications Society.2001.

[5] Benjamin G, Deborah E, et al. DIFS:a distributed index for features in sensor networks. Proc. of the 1st IEEE Int’l Workshop on Sensor Network Protocols and Applications Anchorage.2003.

[6] Sylvia R, Brad K, Scott S,et al.Data-Centric storage in sonsomets with GHT.a geographic hash table.Mobile Networks and Applications.2003.

[7] Scott S, Sylvia R, Brad K,et al.Data-Centrie storage in sensor nets.ACM SIGCOMM Computer Communication Review.2003.

[8] A.Deshpande,C.Guestrin,S.Madden,J.Hellerstein,and W.Hong.Model-driven data acquisition in sensor networks[C].In Proc.of the 2004 Intl.Conf.on Very Large Data Bases.Toronto. Canada.Aug.2004.