無(wú)線傳感器網(wǎng)絡(luò)分布式數(shù)據(jù)庫(kù)的挑戰(zhàn)

無(wú)線傳感器網(wǎng)絡(luò)分布式數(shù)據(jù)庫(kù)的挑戰(zhàn)

1wsn技術(shù)方面無(wú)線傳感器網(wǎng)絡(luò)（wsd）是一個(gè)由大量微傳感器節(jié)點(diǎn)通過(guò)無(wú)線通信組成的多段自組織網(wǎng)絡(luò)系統(tǒng)。目標(biāo)是在無(wú)線通信的覆蓋下合作感知、收集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)受監(jiān)視對(duì)象的信息，并將其發(fā)送給支持者。它綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)、通信技術(shù)和微電機(jī)技術(shù),在軍事、工業(yè)、醫(yī)療、交通、環(huán)保等諸多方面有著巨大的應(yīng)用價(jià)值。WSN本質(zhì)上是一個(gè)以數(shù)據(jù)為中心的網(wǎng)絡(luò),傳感器采集的數(shù)據(jù)稱為感知數(shù)據(jù),其特征是只有追加操作的連續(xù)數(shù)據(jù)流及近似的模糊數(shù)據(jù),并且具有連續(xù)不斷的查詢。因此,現(xiàn)有的研究都把WSN數(shù)據(jù)庫(kù)看作為來(lái)自物理世界的連續(xù)數(shù)據(jù)流組成的分布式數(shù)據(jù)庫(kù)。由于WSN中節(jié)點(diǎn)計(jì)算能力、存儲(chǔ)容量、通信能力都有限,且節(jié)點(diǎn)依靠電池供電,在很多場(chǎng)合下,電池是不可更換的,直接影響網(wǎng)絡(luò)的壽命。WSN中的感知數(shù)據(jù)特性以及傳感器節(jié)點(diǎn)自身特性給數(shù)據(jù)管理帶來(lái)了傳統(tǒng)分布式數(shù)據(jù)庫(kù)技術(shù)沒(méi)有的一些新挑戰(zhàn)。具體表現(xiàn)在如下幾個(gè)方面:(1)需要研究針對(duì)WSN數(shù)據(jù)特征的數(shù)據(jù)管理技術(shù)。由于傳感器節(jié)點(diǎn)可以持續(xù)采集監(jiān)測(cè)環(huán)境中的數(shù)據(jù),WSN中的數(shù)據(jù)往往是連續(xù)無(wú)限的數(shù)據(jù)流,其數(shù)據(jù)往往是近似的且數(shù)據(jù)分布的統(tǒng)計(jì)特征是未知的。而傳統(tǒng)的分布式數(shù)據(jù)庫(kù)中的數(shù)據(jù)往往是間斷有限的,數(shù)據(jù)是確定的且數(shù)據(jù)分布的統(tǒng)計(jì)特征已知。(2)需要研究平衡能量消耗和響應(yīng)時(shí)間的數(shù)據(jù)管理技術(shù)。能量消耗是WSN的一個(gè)重要技術(shù)指標(biāo),直接影響到網(wǎng)絡(luò)的使用壽命;而響應(yīng)時(shí)間是WSN的另一項(xiàng)重要指標(biāo),尤其是對(duì)實(shí)時(shí)監(jiān)測(cè)應(yīng)用。響應(yīng)時(shí)間和能量消耗是一對(duì)相互沖突的技術(shù)指標(biāo)。因此,如何平衡響應(yīng)時(shí)間和能量消耗,確保在滿足響應(yīng)時(shí)間要求的情況下,盡可能降低能量消耗,是一個(gè)值得深入研究的課題。(3)需要研究針對(duì)flash存儲(chǔ)器,以降低能耗為目標(biāo)的數(shù)據(jù)存儲(chǔ)技術(shù)。由于flash具有高可靠性、高密度、低能耗等一些特點(diǎn),傳感器節(jié)點(diǎn)都是用flash作為永久性存儲(chǔ)器。和硬盤技術(shù)相比,flash具有許多獨(dú)特特性,傳統(tǒng)的數(shù)據(jù)庫(kù)存儲(chǔ)技術(shù)不再適用。本文將從數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)與索引、數(shù)據(jù)模式、數(shù)據(jù)查詢及優(yōu)化和數(shù)據(jù)挖掘等方面闡述WSN的數(shù)據(jù)管理技術(shù)。2分布式數(shù)據(jù)庫(kù)的管理架構(gòu)典型的傳感器網(wǎng)絡(luò)的系統(tǒng)結(jié)構(gòu)包括資源受限的傳感器節(jié)點(diǎn)群組成的多跳自組織網(wǎng)絡(luò)、資源豐富的Sink節(jié)點(diǎn)、互聯(lián)網(wǎng)和用戶界面等。映射到傳感器網(wǎng)絡(luò)的分布式數(shù)據(jù)庫(kù)系統(tǒng)也采用兩層體系結(jié)構(gòu),如圖1所示,它是由運(yùn)行在傳感器節(jié)點(diǎn)上本地?cái)?shù)據(jù)庫(kù)和運(yùn)行在sink節(jié)點(diǎn)上與局部數(shù)據(jù)庫(kù)進(jìn)行交互的分布式數(shù)據(jù)庫(kù)管理層組成。本地?cái)?shù)據(jù)庫(kù)主要具有3個(gè)關(guān)鍵元素:(1)查詢引擎。生成能量有效的查詢計(jì)劃用于執(zhí)行查詢,得到具有可信值的查詢結(jié)果。(2)數(shù)據(jù)處理方法(如數(shù)據(jù)匯總及數(shù)據(jù)老化算法等)。為高效的數(shù)據(jù)查詢提供多粒度的數(shù)據(jù)匯總,刪除一些已過(guò)時(shí)的數(shù)據(jù),以節(jié)約flash存儲(chǔ)空間。(3)能量有效的存儲(chǔ)管理。用于實(shí)現(xiàn)flash存儲(chǔ)器分配與管理,為提高查詢處理速度建立相關(guān)的索引等。這3個(gè)組件的實(shí)例依賴節(jié)點(diǎn)的能力。位于Sink節(jié)點(diǎn)上的分布式數(shù)據(jù)管理層通常亦稱為代理數(shù)據(jù)庫(kù),它包括兩個(gè)關(guān)鍵組件:一個(gè)為數(shù)據(jù)緩存(cache),用于保存低層節(jié)點(diǎn)監(jiān)測(cè)到的數(shù)據(jù)匯總及從傳感器節(jié)點(diǎn)查詢得到的結(jié)果;另一個(gè)為查詢處理引擎,決定如何處理每個(gè)查詢命令。查詢可以使用cache中數(shù)據(jù)進(jìn)行局部查詢;或在做相應(yīng)的優(yōu)化操作后,把查詢請(qǐng)求傳送給相應(yīng)的節(jié)點(diǎn),從節(jié)點(diǎn)中提取更多的數(shù)據(jù)。3相關(guān)性存儲(chǔ)/存儲(chǔ)設(shè)備在通常情況下,傳感器節(jié)點(diǎn)需要保存監(jiān)測(cè)數(shù)據(jù)、系統(tǒng)可執(zhí)行代碼及系統(tǒng)設(shè)置信息等,永久性存儲(chǔ)器是傳感器節(jié)點(diǎn)的組成部分之一。出于抗震性、節(jié)點(diǎn)大小以及能量消耗等方面考慮,硬盤不適用于作為傳感器節(jié)點(diǎn)的永久性存儲(chǔ)器,flash是目前的最佳選擇。傳感器節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)與索引技術(shù)要考慮flash特性、節(jié)點(diǎn)的能量消耗等因素。3.1ddfldusb存儲(chǔ)技術(shù)根據(jù)flash存儲(chǔ)單元的組織方式,flash分為兩類:NAND和NOR。NOR采用隨機(jī)訪問(wèn)方式,存儲(chǔ)容量小,適用于作為程序存儲(chǔ)器。而NAND以頁(yè)(page)的方式進(jìn)行訪問(wèn),存儲(chǔ)容量大,適用于存儲(chǔ)大量數(shù)據(jù)的永久性存儲(chǔ)器。NANDflash的一個(gè)異常特性為讀、寫操作的不對(duì)稱性。讀、寫是以頁(yè)(Page)為單位進(jìn)行的,而且寫數(shù)據(jù)之前必須先進(jìn)行擦除。而擦除是以塊為單位,每塊由若干頁(yè)組成。也就是說(shuō),若要更新某一頁(yè)數(shù)據(jù),必須先把該頁(yè)所在的塊讀出,然后把該塊進(jìn)行擦除,再寫入。因此,寫一頁(yè)的代價(jià)很高,而且flash塊受擦除次數(shù)限制,典型值大約為10萬(wàn)次。flash這些特性給基于NANDflash的存儲(chǔ)技術(shù)帶來(lái)了挑戰(zhàn)。表1為一些flash存儲(chǔ)器的性質(zhì)。然而,NANDFlash的顯著優(yōu)點(diǎn)是它的高容量和低功率消耗。和DRAM及NORflash存儲(chǔ)器相比,其容量大(單片容量目前可達(dá)32GB),每GB的單價(jià)低,而且讀寫所消耗的能量也低。另外,和通信能耗相比,對(duì)同一數(shù)據(jù),本地存儲(chǔ)到NANDFlash上比把數(shù)據(jù)發(fā)送到鄰居節(jié)點(diǎn)(MICAZ通信設(shè)備)的能耗要低100倍以上。因此,NANDflash是傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)在傳感器節(jié)點(diǎn)上的一種理想設(shè)備。表2為這些flash讀寫一個(gè)字節(jié)數(shù)據(jù)的能量消耗比較。3.2elf的存儲(chǔ)方式根據(jù)WSN的數(shù)據(jù)流以及flash存儲(chǔ)器的特征,目前傳感器節(jié)點(diǎn)上的數(shù)據(jù)存儲(chǔ)方式主要有兩種方式:一種為不帶索引基于日志結(jié)構(gòu)的文件存儲(chǔ)方式,另一種為基于索引結(jié)構(gòu)的存儲(chǔ)方式。針對(duì)傳感器節(jié)點(diǎn)設(shè)計(jì)的第一個(gè)文件系統(tǒng)是matchbox,已集成到tinyOS系統(tǒng)中。Matchbox提供了基本的flash存儲(chǔ)器的磨損平衡機(jī)制和遠(yuǎn)程文件訪問(wèn)方法,只允許對(duì)數(shù)據(jù)進(jìn)行追加(append)操作,不允許隨機(jī)訪問(wèn)文件中的數(shù)據(jù),如修改(modify)操作?？梢酝瑫r(shí)打開多個(gè)文件。其特點(diǎn)是程序代碼很小,只有10kB,運(yùn)行時(shí)內(nèi)存占用量也很少,最小約為362個(gè)字節(jié)。當(dāng)打開的文件多時(shí),內(nèi)存占用量也會(huì)隨著增加。文獻(xiàn)是針對(duì)傳感器節(jié)點(diǎn)設(shè)計(jì)的基于flash存儲(chǔ)器的日志結(jié)構(gòu)文件系統(tǒng)(EfficientLogStructuredFlashFileSystem,ELF)。ELF考慮到傳感器節(jié)點(diǎn)的資源限制,僅為系統(tǒng)的通用任務(wù)提供了一些基本的文件管理操作,如open,create,modify,append,read,seek,delete,rename,truncation等。與傳統(tǒng)的基于flash的文件系統(tǒng)的不同之處主要在于對(duì)文件的寫操作(包括append和modify)。對(duì)于append操作,ELF并不為每個(gè)append操作創(chuàng)建一個(gè)日志數(shù)據(jù)項(xiàng),而是對(duì)每個(gè)文件,利用一個(gè)寫緩沖區(qū)緩存追加到同一頁(yè)的日志項(xiàng),當(dāng)緩沖區(qū)滿時(shí)再寫入到flash頁(yè)上。這樣可以減少對(duì)flash寫的次數(shù),以延長(zhǎng)flash的使用壽命和降低能量消耗。而對(duì)于modify操作,ELF申請(qǐng)一個(gè)新的flash頁(yè)來(lái)存儲(chǔ)修改的頁(yè)面,而不是寫入原來(lái)的頁(yè)中,以實(shí)現(xiàn)flash頁(yè)的磨損平衡。另外,ELF提供了碎片回收和故障恢復(fù)機(jī)制。碎片回收用于實(shí)現(xiàn)flash頁(yè)的磨損平衡、可用空間的擦除和再分配,故障恢復(fù)用于當(dāng)系統(tǒng)或flash頁(yè)發(fā)生故障時(shí)利用檢查點(diǎn)技術(shù)實(shí)現(xiàn)數(shù)據(jù)恢復(fù)。受到日志結(jié)構(gòu)文件系統(tǒng)的啟發(fā),文獻(xiàn)提出一種基于B+tree索引的日志結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)技術(shù),其基本思想是把索引組織成事務(wù)日志。把對(duì)B+tree樹節(jié)點(diǎn)的寫操作編碼成一個(gè)日志記錄,并存儲(chǔ)在內(nèi)存緩沖區(qū)中。當(dāng)緩沖區(qū)包含的數(shù)據(jù)足夠裝滿一頁(yè)時(shí),則寫入flash中。另外,對(duì)每個(gè)B+tree樹節(jié)點(diǎn),還保存一個(gè)頁(yè)地址鏈接表,指向該B+tree節(jié)點(diǎn)存儲(chǔ)的日志記錄的flash頁(yè)的地址。FlashDB根據(jù)WSN不同類型的工作負(fù)荷參數(shù)和NANDflash設(shè)備的一些特性參數(shù),設(shè)計(jì)了一種自調(diào)節(jié)的數(shù)據(jù)存儲(chǔ)方法。它綜合了傳統(tǒng)的基于磁盤的B+tree索引和基于日志結(jié)構(gòu)的B+tree索引技術(shù),采用自調(diào)節(jié)技術(shù)動(dòng)態(tài)地調(diào)節(jié)它的存儲(chǔ)結(jié)構(gòu),以適應(yīng)不同的工作負(fù)荷和flash設(shè)備,靈活地以兩種方式中的一種存儲(chǔ)索引節(jié)點(diǎn)。它把索引的自調(diào)節(jié)性質(zhì)形式化為一個(gè)雙態(tài)系統(tǒng)并提出相應(yīng)的算法,實(shí)現(xiàn)理論上的最優(yōu)。Microhash提出一種基于hash索引結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)方式。它把flash的數(shù)據(jù)存儲(chǔ)區(qū)組織成堆(heap),監(jiān)測(cè)數(shù)據(jù)按時(shí)間順序以循環(huán)數(shù)組方式存儲(chǔ)在flash的數(shù)據(jù)存儲(chǔ)區(qū)上,這種方式直接解決了刪除、寫以及磨損平衡問(wèn)題。Microhash在把監(jiān)測(cè)數(shù)據(jù)存儲(chǔ)到flash時(shí),同時(shí)建立索引。索引采用兩層索引結(jié)構(gòu),即index層和directory層。Index的每個(gè)索引記錄格式為[idx,offset],其中idx為數(shù)據(jù)存儲(chǔ)的flash頁(yè)的地址,offset為存儲(chǔ)在該頁(yè)相對(duì)起始地址的偏移值。directory的每個(gè)記錄項(xiàng)包括index層的某個(gè)flash頁(yè)的地址以及索引數(shù)據(jù)項(xiàng)值的上、下界。值得進(jìn)一步研究的是,在傳感器節(jié)點(diǎn)數(shù)據(jù)庫(kù)構(gòu)建和維護(hù)索引時(shí),必須考慮能量消耗問(wèn)題。建立索引可以提高訪問(wèn)數(shù)據(jù)的速度,減少讀取flash頁(yè)的次數(shù)。但建立和維護(hù)索引除了增加額外的存儲(chǔ)空間外,其讀寫也需要消耗能量,尤其是對(duì)索引的寫操作。這些能量消耗要在查詢處理中得到補(bǔ)償,索引才有意義。因此,使用索引結(jié)構(gòu)只有在數(shù)據(jù)訪問(wèn)操作非常頻繁時(shí)才有效,否則通過(guò)順序掃描來(lái)執(zhí)行查詢更節(jié)約能量。4基于數(shù)據(jù)的存儲(chǔ)和磁盤索引技術(shù)4.1種網(wǎng)內(nèi)數(shù)據(jù)存儲(chǔ)方案在WSN中,傳感器監(jiān)測(cè)數(shù)據(jù)可以存儲(chǔ)在本地節(jié)點(diǎn),也可以根據(jù)數(shù)據(jù)的屬性通過(guò)某種映射技術(shù)存儲(chǔ)到網(wǎng)絡(luò)中的一些指定節(jié)點(diǎn)上,即以數(shù)據(jù)為中心的存儲(chǔ)技術(shù)。文獻(xiàn)提出基于地理位置散列表(GeographicHashTable,GHT)的以數(shù)據(jù)為中心的存儲(chǔ)方法。其基本思想為:首先用一個(gè)GHF將數(shù)據(jù)映射到一個(gè)地理位置,然后采用地理路由協(xié)議——貪心周邊無(wú)狀態(tài)路由協(xié)議(GreedyPerimeterStatelessRouting,GPSR)將測(cè)量數(shù)據(jù)存儲(chǔ)到距離該位置最近的傳感器節(jié)點(diǎn)。當(dāng)某個(gè)監(jiān)測(cè)數(shù)據(jù)出現(xiàn)頻率很高時(shí),會(huì)導(dǎo)致很多數(shù)據(jù)映射到同一個(gè)節(jié)點(diǎn),即出現(xiàn)“熱點(diǎn)”(hotspot)現(xiàn)象,GHT使用結(jié)構(gòu)復(fù)制技術(shù)解決這種問(wèn)題。文獻(xiàn)針對(duì)目標(biāo)跟蹤應(yīng)用提出了一種網(wǎng)內(nèi)數(shù)據(jù)存儲(chǔ)方案(Energy-conservingApproximateStoragEScheme,EASE)。EASE在網(wǎng)絡(luò)內(nèi)保持兩個(gè)版本的目標(biāo)跟蹤數(shù)據(jù),一個(gè)為高精度數(shù)據(jù),一個(gè)是低精度近似數(shù)據(jù)。高精度數(shù)據(jù)保存在移動(dòng)目標(biāo)附近的節(jié)點(diǎn)上,以避免長(zhǎng)距離的更新引起能量消耗。而與此相對(duì)應(yīng)的低精度數(shù)據(jù),則復(fù)制到一個(gè)指定節(jié)點(diǎn)上,以減少查詢費(fèi)用,指定節(jié)點(diǎn)對(duì)用戶來(lái)說(shuō)是透明的。存儲(chǔ)在指定節(jié)點(diǎn)的不精確移動(dòng)目標(biāo)位置數(shù)據(jù)由一個(gè)近似半徑來(lái)限定。也就是說(shuō),如果移動(dòng)目標(biāo)保持在近似半徑范圍內(nèi)移動(dòng),它的精確位置數(shù)據(jù)更新只存儲(chǔ)在最近的節(jié)點(diǎn)上。此時(shí),其對(duì)應(yīng)的不精確表示并不更新,即不發(fā)送到指定的節(jié)點(diǎn)。相應(yīng)地,若查詢的精度約束條件低于近似半徑指定的值,則查詢結(jié)果可直接通過(guò)指定存儲(chǔ)節(jié)點(diǎn)獲得,否則查詢要轉(zhuǎn)發(fā)到本地存儲(chǔ)節(jié)點(diǎn),以獲得更精確的結(jié)果。EASE還通過(guò)適當(dāng)?shù)卦O(shè)置近似半徑來(lái)平衡數(shù)據(jù)更新傳輸流量和查詢流量,以優(yōu)化網(wǎng)絡(luò)的性能。WSN在軍事上得到了很大的應(yīng)用。為了實(shí)現(xiàn)數(shù)據(jù)的安全存儲(chǔ)和安全傳輸,防止敵方能夠從捕獲的節(jié)點(diǎn)中獲取數(shù)據(jù),文獻(xiàn)提出了一種漫游數(shù)據(jù)存儲(chǔ)方法(EvasiveDataStorage,EDS)。其基本思想為:網(wǎng)絡(luò)中有價(jià)值的數(shù)據(jù)并不是存儲(chǔ)在某個(gè)固定的節(jié)點(diǎn)上,而是以一種不可預(yù)知的方式在網(wǎng)絡(luò)中漫游。敵方若已經(jīng)捕獲先前存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn),也不能很快地訪問(wèn)數(shù)據(jù),因?yàn)閿?shù)據(jù)已不再存儲(chǔ)在該節(jié)點(diǎn)上。另外,EDS采用位置限定法,對(duì)漫游的位置加以限制,降低通信負(fù)擔(dān);采用數(shù)據(jù)劃分(DataSplitting)策略,把數(shù)據(jù)分成小片,每一片獨(dú)立地存儲(chǔ)在網(wǎng)絡(luò)的不同節(jié)點(diǎn)上,以防止敵方的睡眠攻擊。4.2確定節(jié)點(diǎn)位置和使用方式以數(shù)據(jù)為中心的存儲(chǔ)技術(shù)根據(jù)數(shù)據(jù)的屬性把相關(guān)聯(lián)的數(shù)據(jù)存儲(chǔ)到指定的節(jié)點(diǎn),可通過(guò)數(shù)據(jù)融合技術(shù)對(duì)數(shù)據(jù)進(jìn)行處理,避免把大量的測(cè)量數(shù)據(jù)傳輸?shù)骄W(wǎng)外,以達(dá)到降低數(shù)據(jù)傳輸能耗的目的。在數(shù)據(jù)查詢中,為了能快速地定位到數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn),避免在全網(wǎng)泛洪廣播查詢請(qǐng)求,需要對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)建立分布式索引技術(shù)。如GHT技術(shù)可以直接根據(jù)數(shù)據(jù)的屬性,利用Hash函數(shù),定位到數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)。加州大學(xué)洛杉磯分校開發(fā)的Dimensions系統(tǒng)采用空間分解技術(shù)對(duì)數(shù)據(jù)建立索引。其基本思想為:首先根據(jù)查詢的空間范圍確定層次級(jí)別數(shù)d,然后遞歸地對(duì)查詢空間進(jìn)行分解,每一級(jí)分成4個(gè)子區(qū)域。即第0級(jí)為整個(gè)監(jiān)測(cè)區(qū)域,選擇一個(gè)節(jié)點(diǎn)為簇頭節(jié)點(diǎn);第1級(jí)將整個(gè)監(jiān)測(cè)區(qū)域劃分為4個(gè)子區(qū)域,每個(gè)子區(qū)域都選擇一個(gè)節(jié)點(diǎn)為簇頭節(jié)點(diǎn);第2級(jí)又把第1級(jí)的子區(qū)域劃分為4個(gè)子區(qū)域,同樣每個(gè)子區(qū)域都選擇一個(gè)節(jié)點(diǎn)為簇頭節(jié)點(diǎn)。以此類推,一直劃分到第d級(jí)為止,下級(jí)簇頭節(jié)點(diǎn)不能和上級(jí)簇頭節(jié)點(diǎn)使用同一個(gè)節(jié)點(diǎn)。當(dāng)查詢指定空間范圍的數(shù)據(jù)時(shí),將查詢結(jié)果從第d級(jí)開始逐級(jí)傳送到頂點(diǎn)和用戶。該索引技術(shù)適用于本地存儲(chǔ)數(shù)據(jù)和指定空間范圍的多分辨率查詢要求,其缺陷是簇頭節(jié)點(diǎn)能量消耗過(guò)快,并且易造成通信瓶頸問(wèn)題。文獻(xiàn)提出了一種分布式索引方法(DistributedIndexforFeaturesinSensorNetworks,DIFS),該方法綜合了GHT技術(shù)和空間分解技術(shù),利用GHT技術(shù)實(shí)現(xiàn)了以數(shù)據(jù)為中心的存儲(chǔ),利用空間分解技術(shù)實(shí)現(xiàn)對(duì)分布式數(shù)據(jù)的索引。區(qū)別于文獻(xiàn)所采用的空間分解技術(shù),其構(gòu)造的層次結(jié)構(gòu)的每個(gè)非根節(jié)點(diǎn)具有多個(gè)父節(jié)點(diǎn),以解決能量消耗和通信瓶頸問(wèn)題。每個(gè)節(jié)點(diǎn)都存儲(chǔ)特定地理范圍內(nèi)和特定監(jiān)測(cè)數(shù)據(jù)值范圍內(nèi)的數(shù)據(jù)。上層節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)覆蓋的地理范圍大,但覆蓋的監(jiān)測(cè)數(shù)據(jù)值的范圍小。相反,下層節(jié)點(diǎn)的數(shù)據(jù)覆蓋的地理范圍小,但數(shù)據(jù)值的范圍大。在查詢數(shù)據(jù)時(shí),首先選擇最高父節(jié)點(diǎn)的集合,這些節(jié)點(diǎn)覆蓋所有查詢要求的數(shù)據(jù)名的范圍。然后根據(jù)查詢要求的空間范圍逐層進(jìn)行遍歷,最后得到查詢結(jié)果。DIFS適用于指定空間范圍以及指定數(shù)據(jù)值范圍的單屬性的查詢要求。上述索引技術(shù)只用于對(duì)單一屬性數(shù)據(jù)建立索引,而在異構(gòu)WSN中可具有多種類型傳感器,能測(cè)量到不同屬性的數(shù)據(jù)。文獻(xiàn)提出了一種支持多屬性范圍查詢的分布式索引技術(shù)(DistributedIndexforMulti-dimensionaldata,DIM)。DIM方法依賴兩種技術(shù):局部保持(locality-preserving)地理散列和基于地理位置的貪婪周邊路由協(xié)議GPSR。它首先通過(guò)局部保持地理散列函數(shù)將一個(gè)多維數(shù)據(jù)映射到二維平面空間的一點(diǎn),然后應(yīng)用GPSR將該數(shù)據(jù)存儲(chǔ)在離該點(diǎn)最近的節(jié)點(diǎn)上。同樣,在查詢數(shù)據(jù)時(shí),根據(jù)查詢請(qǐng)求的數(shù)據(jù)要求,通過(guò)局部保持地理散列函數(shù)獲得測(cè)量數(shù)據(jù)所在的區(qū)域,并應(yīng)用GPSR把查詢傳送到這些區(qū)域,從這些區(qū)域中提取相應(yīng)的數(shù)據(jù)。5基于psra的運(yùn)動(dòng)方程現(xiàn)有的WSN數(shù)據(jù)庫(kù)系統(tǒng)對(duì)傳感器監(jiān)測(cè)的數(shù)據(jù)流建模大多為對(duì)傳統(tǒng)的數(shù)據(jù)模式進(jìn)行擴(kuò)展,主要有基于工作流模式、基于關(guān)系模式、基于對(duì)象模式。針對(duì)WSN的一些特殊應(yīng)用,也可以建立特殊的數(shù)據(jù)模式。Aurora系統(tǒng)是一種面向時(shí)間工作流模式建模的系統(tǒng),其查詢建立在Aurora查詢代數(shù)基礎(chǔ)上,包括3個(gè)與順序無(wú)關(guān)的操作(Filter,Map和Union)和4個(gè)對(duì)順序敏感的操作(BSort,Aggregate,Join和Resample)。Aurora的數(shù)據(jù)流采用統(tǒng)一的元組序列形式(TS,A1,A2,…,An),其中TS為時(shí)間戳,Ai(1≤i≤n)為與應(yīng)用相關(guān)的數(shù)據(jù)域,對(duì)數(shù)據(jù)流的操作只有添加操作。Aurora系統(tǒng)針對(duì)于高效調(diào)度、服務(wù)質(zhì)量和優(yōu)化結(jié)構(gòu)而設(shè)計(jì),以統(tǒng)一處理方式支持連續(xù)查詢、滑動(dòng)窗口和其它的一些特別查詢。Borealis對(duì)Aurora系統(tǒng)進(jìn)行了擴(kuò)展,其數(shù)據(jù)流為形如(TS,tuple-type,id,A1,A2,…,An)的元組序列,其中tuple-type支持插入、刪除和替換操作,id為元組的標(biāo)識(shí)符。另外,Borealis還設(shè)計(jì)了支持如下操作的數(shù)據(jù)流引擎:查詢的動(dòng)態(tài)更改、查詢結(jié)果的動(dòng)態(tài)更新。Aurora和Borealis都實(shí)現(xiàn)了分布式數(shù)據(jù)流模型,可根據(jù)網(wǎng)絡(luò)條件的變化動(dòng)態(tài)配置。TinyDB采用基于關(guān)系的數(shù)據(jù)模式,并對(duì)傳統(tǒng)的關(guān)系模式進(jìn)行了擴(kuò)展。它把傳感器節(jié)點(diǎn)的測(cè)量數(shù)據(jù)定義為一個(gè)單一的、無(wú)限長(zhǎng)的、有兩類屬性的虛擬關(guān)系表:一類用來(lái)定義測(cè)量數(shù)據(jù),如節(jié)點(diǎn)標(biāo)識(shí)符、測(cè)量時(shí)間、測(cè)量數(shù)據(jù)類型、單位等;另一類用來(lái)描述測(cè)量數(shù)據(jù)本身,如溫度、位置等。傳感器產(chǎn)生的測(cè)量數(shù)據(jù)對(duì)應(yīng)表的一行,對(duì)數(shù)據(jù)的查詢就是對(duì)這個(gè)無(wú)限虛擬表的查詢。美國(guó)斯坦福大學(xué)針對(duì)WSN開發(fā)的STREAM系統(tǒng)采用的也是基于關(guān)系的數(shù)據(jù)模式。它把數(shù)據(jù)流建模為無(wú)邊界的、只能進(jìn)行添加操作的元組對(duì)(tuple,timestamp)組成的數(shù)據(jù)流,把關(guān)系作為支持更新、插入和刪除操作、隨時(shí)間變化的元組包。其語(yǔ)義建立在3組抽象操作上:關(guān)系-關(guān)系操作、數(shù)據(jù)流-關(guān)系操作和關(guān)系-數(shù)據(jù)流操作。COUGAR是一個(gè)基于抽象數(shù)據(jù)類型(AbstractDataType)的數(shù)據(jù)流系統(tǒng),它采用兩種模式對(duì)數(shù)據(jù)進(jìn)行建模:用對(duì)象關(guān)系模式來(lái)組織建模存儲(chǔ)數(shù)據(jù);引入一種時(shí)間序列模式建模組織傳感器監(jiān)測(cè)數(shù)據(jù),并定義了相應(yīng)的關(guān)系代數(shù)操作、時(shí)間序列操作以及關(guān)系及時(shí)間序列之間的操作。針對(duì)傳感器測(cè)量數(shù)據(jù)的不確定性,PSRA擴(kuò)展傳統(tǒng)的關(guān)系模型到概率數(shù)據(jù)流關(guān)系(ProbabilisticStreamRelation)模型,并擴(kuò)展傳統(tǒng)關(guān)系模型的操作,在概率數(shù)據(jù)流模型上定義了StreamUnion,StreamIntersection,StreamSelect,Streamproject,StreamJoin等操作。PSRA通過(guò)概率數(shù)據(jù)流模型有效地解決了WSN的數(shù)據(jù)不確定性以及數(shù)據(jù)的相互關(guān)系等一些特征,并提供了能量高效的操作。傳感器網(wǎng)絡(luò)的有些應(yīng)用并不需要精確的測(cè)量數(shù)據(jù),如對(duì)森林防火監(jiān)控,用溫度傳感器對(duì)周圍的環(huán)境進(jìn)行監(jiān)控,對(duì)測(cè)量的數(shù)據(jù)并不需要它的精確值,只需把測(cè)量數(shù)據(jù)劃分為低、較低、中、較高、高、極高幾個(gè)等級(jí)。根據(jù)這一類應(yīng)用的特征,文獻(xiàn)中提出一種基于粗糙集(RoughSet)理論的數(shù)據(jù)建模方法。利用粗糙集對(duì)數(shù)據(jù)建模,可以很好地實(shí)現(xiàn)數(shù)據(jù)融合操作,從而減小數(shù)據(jù)存儲(chǔ)量及網(wǎng)絡(luò)傳輸量,達(dá)到節(jié)約能量,延長(zhǎng)網(wǎng)絡(luò)壽命的目的。6數(shù)據(jù)的檢查、處理和優(yōu)化6.1分布式數(shù)據(jù)庫(kù)的原理WSN的數(shù)據(jù)查詢應(yīng)用可以分為兩大類:查詢動(dòng)態(tài)數(shù)據(jù)和查詢歷史數(shù)據(jù)。在查詢動(dòng)態(tài)數(shù)據(jù)中,數(shù)據(jù)在傳感器監(jiān)測(cè)到的一個(gè)小的時(shí)間窗內(nèi)有效,例如事件檢測(cè)查詢或一些特定查詢(當(dāng)前的溫度是多少?)。而查詢歷史數(shù)據(jù)是指對(duì)檢測(cè)到的歷史數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘,用于發(fā)現(xiàn)事件特殊模式,分析數(shù)據(jù)走趨,形成特定事件的理想模型等。對(duì)這一類應(yīng)用來(lái)說(shuō),每一個(gè)數(shù)據(jù)都是重要的,不能被拋棄。WSN數(shù)據(jù)庫(kù)系統(tǒng)可理解為一個(gè)兩層結(jié)構(gòu)的分布式數(shù)據(jù)庫(kù)系統(tǒng):運(yùn)行在Sink節(jié)點(diǎn)上的代理數(shù)據(jù)庫(kù)服務(wù)器和運(yùn)行在傳感器節(jié)點(diǎn)上的局部數(shù)據(jù)庫(kù)。數(shù)據(jù)查詢的處理過(guò)程一般為:首先用戶使用命令式查詢接口把查詢請(qǐng)求發(fā)送到網(wǎng)絡(luò),通過(guò)路由技術(shù)傳送到運(yùn)行在Sink節(jié)點(diǎn)的代理服務(wù)器。其次,代理服務(wù)器根據(jù)接收到的用戶請(qǐng)求生成相應(yīng)查詢計(jì)劃。然后,代理服務(wù)器把查詢計(jì)劃通過(guò)路由技術(shù)發(fā)送到相應(yīng)的傳感器節(jié)點(diǎn)。節(jié)點(diǎn)接收到查詢后,執(zhí)行查詢,并把結(jié)果傳送到代理服務(wù)器。最后,代理服務(wù)器對(duì)節(jié)點(diǎn)返回的結(jié)果進(jìn)行處理,并把最終結(jié)果返回給相應(yīng)的用戶。由于SQL語(yǔ)言在數(shù)據(jù)庫(kù)領(lǐng)域廣泛應(yīng)用,其顯著優(yōu)點(diǎn)為:(1)方便用戶。用戶使用SQL語(yǔ)言只需定義他所想要的數(shù)據(jù),而不需要知道如何獲取這些數(shù)據(jù),并且SQL語(yǔ)言易學(xué),也容易理解。(2)語(yǔ)言形式與實(shí)現(xiàn)分離。也就是說(shuō),查詢系統(tǒng)內(nèi)部修改了如何執(zhí)行一個(gè)查詢,而查詢語(yǔ)言形式并沒(méi)有改變。目前,WSN的數(shù)據(jù)查詢語(yǔ)言大多都延續(xù)了傳統(tǒng)的SQL語(yǔ)言形式,并對(duì)SQL語(yǔ)言進(jìn)行了擴(kuò)展。TinyDB的查詢語(yǔ)言在WSN中具有一定的代表性,其語(yǔ)法結(jié)構(gòu)表述如下:其中,select-list是數(shù)據(jù)屬性或與屬性相關(guān)的聚集函數(shù),gb-list是數(shù)據(jù)屬性表,where-predicate和having-predicate是謂詞,方括號(hào)中的內(nèi)容是可選項(xiàng)。6.2低能量消耗的查詢優(yōu)化技術(shù)WSN中的查詢優(yōu)化策略大致可分為運(yùn)行在Sink節(jié)點(diǎn)上的多查詢優(yōu)化策略和運(yùn)行在網(wǎng)內(nèi)節(jié)點(diǎn)上的單查詢優(yōu)化策略。這兩種技術(shù)結(jié)合起來(lái)構(gòu)造WSN的查詢優(yōu)化系統(tǒng)。優(yōu)化的目標(biāo)要在保證網(wǎng)絡(luò)服務(wù)質(zhì)量的前提下,盡可能降低能量消耗,以延長(zhǎng)網(wǎng)絡(luò)的壽命。多查詢優(yōu)化策略建立在單查詢優(yōu)化策略之上,它把用戶發(fā)送到Sink節(jié)點(diǎn)的查詢集合Q優(yōu)化成一個(gè)新的查詢集合Q’,以盡可能地刪除Q中不同查詢中的冗余請(qǐng)求。優(yōu)化的最佳情形為新查詢集Q’中的查詢結(jié)果剛好能滿足Q中的所有查詢請(qǐng)求,并且Q中不同查詢所需要的同樣數(shù)據(jù)可根據(jù)Q’中查詢?cè)趥鞲衅骶W(wǎng)絡(luò)中僅獲取一次。文獻(xiàn)利用貪婪查詢插入算法把相似的查詢集構(gòu)造為一個(gè)新的優(yōu)化后查詢集,以盡可能地減少冗余的查詢請(qǐng)求,優(yōu)化后再把優(yōu)化的查詢發(fā)送到網(wǎng)絡(luò)中。文獻(xiàn)也提出了一種基于Sink節(jié)點(diǎn)的查詢優(yōu)化策略,它把查詢計(jì)劃擴(kuò)展到查詢執(zhí)行的各個(gè)方面,包括路由、傳感器監(jiān)測(cè)和數(shù)據(jù)/元數(shù)據(jù)的收集。其查詢優(yōu)化過(guò)程分為兩個(gè)階段:劃分階段和精化階段。劃分階段通過(guò)評(píng)估查詢集合的查詢計(jì)劃得到一個(gè)查詢費(fèi)用最小的查詢集并決定是否要收集元數(shù)據(jù)。若不需要收集元數(shù)據(jù),則把新的查詢集發(fā)送到相關(guān)的節(jié)點(diǎn),否則進(jìn)入精化階段。精化階段收集元數(shù)據(jù)并重新評(píng)估查詢計(jì)劃,得到一個(gè)新的代價(jià)最小的查詢集,并傳送到相關(guān)的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)收到查詢請(qǐng)求,執(zhí)行查詢,并把查詢結(jié)果傳送到Sink節(jié)點(diǎn)。目前,傳感器網(wǎng)絡(luò)廣泛采用網(wǎng)內(nèi)數(shù)據(jù)處理技術(shù)來(lái)降低數(shù)據(jù)傳送量,以節(jié)約傳輸?shù)哪芰肯?。大部分系統(tǒng)都是結(jié)合數(shù)據(jù)融合和路由技術(shù),在數(shù)據(jù)傳輸?shù)穆酚晒?jié)點(diǎn)上把相關(guān)聯(lián)的數(shù)據(jù)融合在一起,以降低數(shù)據(jù)傳輸量。這類技術(shù)對(duì)數(shù)據(jù)查詢的匯總操作(如max,sum等)很有效,但沒(méi)有對(duì)查詢運(yùn)算進(jìn)行優(yōu)化。文獻(xiàn)提出了一種針對(duì)查詢運(yùn)算(如filter,join等)的層次式網(wǎng)絡(luò)查詢優(yōu)化策略。網(wǎng)絡(luò)采取層次式組織,越在上層的節(jié)點(diǎn),其計(jì)算能力和通信能力越強(qiáng)。數(shù)據(jù)由葉節(jié)點(diǎn)獲取,查詢請(qǐng)求由根節(jié)點(diǎn)向下發(fā)送到葉節(jié)點(diǎn),查詢結(jié)果從葉節(jié)點(diǎn)向上傳送到根節(jié)點(diǎn)。為了降低網(wǎng)絡(luò)通信量,查詢運(yùn)算一般在低層節(jié)點(diǎn)上執(zhí)行,但這時(shí)需要較高的計(jì)算費(fèi)用。該策略通過(guò)貪婪算法優(yōu)化查詢運(yùn)算的執(zhí)行層次來(lái)平衡計(jì)算費(fèi)用與網(wǎng)絡(luò)通信量,以達(dá)到降低整個(gè)網(wǎng)絡(luò)能量消耗的目的?，F(xiàn)有的傳感器網(wǎng)絡(luò)數(shù)據(jù)庫(kù)系統(tǒng)也都采用一些查詢優(yōu)化策略。TinyDB的查詢優(yōu)化目標(biāo)是降低網(wǎng)絡(luò)的總能量消耗。它采用基于代價(jià)的查詢優(yōu)化技術(shù)來(lái)產(chǎn)生能量消耗盡可能少的查詢執(zhí)行計(jì)劃。查詢代價(jià)由傳感器節(jié)點(diǎn)采集數(shù)據(jù)和傳輸查詢結(jié)果的能量消耗決定。其優(yōu)化技術(shù)主要集中于數(shù)據(jù)采集和謂詞操作的執(zhí)行次序,并且確定可以共享的數(shù)據(jù)采集操作,刪除不必要的數(shù)據(jù)采集操作。TinyDB還通過(guò)優(yōu)化基于事件的查詢來(lái)降低冗余的數(shù)據(jù)采集操作。根據(jù)這一特點(diǎn),TinyDB采用基于重寫的多查詢的優(yōu)化技術(shù),把多個(gè)外部事件轉(zhuǎn)化為一個(gè)事件流,使得不管事件以何種頻率發(fā)生,只能同時(shí)有一個(gè)查詢?cè)谶\(yùn)行,這樣就可避免頻繁地啟動(dòng)數(shù)據(jù)采集操作。在STREAM系統(tǒng)中,一旦持續(xù)查詢發(fā)布,就生成一個(gè)相應(yīng)的查詢計(jì)劃。查詢計(jì)劃的執(zhí)行由用于運(yùn)行狀態(tài)資源管理的全局調(diào)度器來(lái)控制,使得單數(shù)據(jù)流查詢?cè)谶\(yùn)行時(shí)內(nèi)存占用方面幾乎是最佳的。STREAM系統(tǒng)所采用的優(yōu)化技術(shù)包括:在查詢計(jì)劃中重新分配窗口運(yùn)算;使用數(shù)據(jù)流限制來(lái)減少窗口的大小;標(biāo)識(shí)共享計(jì)算和共享內(nèi)存的時(shí)機(jī);當(dāng)由于資源限制迫使降低查詢的精度要求,得到近似的查詢結(jié)果時(shí),可以使用減少滑動(dòng)窗口、降低采樣頻率等相關(guān)的技術(shù)來(lái)實(shí)現(xiàn)。查詢優(yōu)化問(wèn)題是傳感器網(wǎng)絡(luò)領(lǐng)域的研究難題之一。它必須設(shè)計(jì)一些高效的分布式處理和數(shù)據(jù)重用技術(shù),既要降低全網(wǎng)絡(luò)的能量消耗,又要避免少量節(jié)點(diǎn)因負(fù)擔(dān)過(guò)重,能量消耗過(guò)快而失效,從而影響到整個(gè)網(wǎng)絡(luò)的使用壽命。6.3在線數(shù)據(jù)挖掘算法傳感器網(wǎng)絡(luò)是一個(gè)以數(shù)據(jù)為中心的網(wǎng)絡(luò),傳感器從監(jiān)測(cè)環(huán)境收集到的大量數(shù)據(jù)可能存在某種內(nèi)在聯(lián)系。數(shù)據(jù)挖掘技術(shù)可用于從大量的數(shù)據(jù)中挖掘出人們感興趣的數(shù)據(jù)關(guān)聯(lián)規(guī)則或傳感器節(jié)點(diǎn)間的關(guān)系。文獻(xiàn)提出了一種用于挖掘傳感器節(jié)點(diǎn)行為模式的算法,其主要目的是確定傳感器節(jié)點(diǎn)行為模式的關(guān)聯(lián)規(guī)則。這些規(guī)則可以用于資源管理或用于彌補(bǔ)網(wǎng)絡(luò)通信的不利因素,以便改進(jìn)網(wǎng)絡(luò)服務(wù)質(zhì)量。文中給出了傳感器節(jié)點(diǎn)行為模式關(guān)聯(lián)規(guī)則的形式化定義;提出了一種針對(duì)數(shù)據(jù)挖掘處