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

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

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