第9章 數(shù)據(jù)管理

1、第九章 數(shù)據(jù)管理提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理的目的n把傳感器網(wǎng)絡(luò)上數(shù)據(jù)的邏輯視圖(命名、存取和操作)和網(wǎng)絡(luò)的物理實(shí)現(xiàn)分離開來，使得傳感器網(wǎng)絡(luò)的用戶和應(yīng)用程序只需要關(guān)心所要提出的查詢的邏輯結(jié)構(gòu)，而無需關(guān)心傳感器的細(xì)節(jié)。n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理面臨的挑戰(zhàn)n傳感器網(wǎng)絡(luò)的組成及特征n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理的要求傳感器網(wǎng)絡(luò)數(shù)據(jù)管理要求n節(jié)能n由于通訊消耗的能量比計(jì)算要大；因此，為了減少能量消耗應(yīng)該盡可能減

2、少通訊量。n分散計(jì)算n集中計(jì)算和存儲(chǔ)會(huì)存在性能瓶頸和單個(gè)節(jié)點(diǎn)故障，因此，分散計(jì)算要求同時(shí)提高系統(tǒng)性能和容錯(cuò)能力。傳感器網(wǎng)絡(luò)數(shù)據(jù)管理要求 (續(xù))n有效的查詢處理n傳統(tǒng)數(shù)據(jù)庫n持久的關(guān)系nAd-Hoc查詢n隨機(jī)的訪問n“無限”的磁盤空間n當(dāng)前狀態(tài)有效n被動(dòng)的存儲(chǔ)n相對(duì)較低的更新率n很少“實(shí)時(shí)服務(wù)”n假定數(shù)據(jù)精確無誤n 傳感器數(shù)據(jù)庫n 瞬間的流n 連續(xù)的查詢n 序列化的訪問n 有限的主存n 數(shù)據(jù)的到達(dá)順序是關(guān)鍵n 主動(dòng)的存儲(chǔ)n 數(shù)據(jù)采樣頻率未知n 實(shí)時(shí)響應(yīng)n 過時(shí)/近似的數(shù)據(jù)提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)系統(tǒng)結(jié)構(gòu)n四種主要的系統(tǒng)結(jié)構(gòu)

3、n集中式結(jié)構(gòu)n半分布式結(jié)構(gòu)n分布式結(jié)構(gòu)n層次結(jié)構(gòu)集中式n數(shù)據(jù)處理過程n數(shù)據(jù)按照事先指定的方式從傳感器網(wǎng)絡(luò)傳輸?shù)街行姆?wù)器n中心服務(wù)器處理用戶查詢請(qǐng)求n缺點(diǎn)n存在性能瓶頸和單個(gè)節(jié)點(diǎn)失敗n通訊開銷大半分布式結(jié)構(gòu)n數(shù)據(jù)處理過程n傳感器節(jié)點(diǎn)執(zhí)行某些計(jì)算來聚集數(shù)據(jù)，以此減少通訊開銷。n比如，檢測(cè)交通量的傳感器可以通過原始的壓力數(shù)據(jù)來計(jì)算每個(gè)時(shí)間片斷內(nèi)經(jīng)過的車輛數(shù)。n經(jīng)過預(yù)處理的數(shù)據(jù)被傳送到中央服務(wù)器進(jìn)行進(jìn)一步處理。n范例：nFjords (“Framework in Java for Operators on Remote Data Streams”)nCougarFjordnFjord是UC Berk

4、eley的Telegraph項(xiàng)目的一部分n包括兩個(gè)組件n查詢處理引擎n同時(shí)采用PUSH和PULL技術(shù)的查詢處理引擎n根據(jù)計(jì)算環(huán)境的變化動(dòng)態(tài)調(diào)整查詢執(zhí)行計(jì)劃n傳感器代理(Sensor proxy)n是傳感器節(jié)點(diǎn)和查詢處理器之間的接口。n主要功能：n避免傳感器節(jié)點(diǎn)直接發(fā)送數(shù)據(jù)給大量感興趣的用戶。n指示傳感器以預(yù)定義的方式來進(jìn)行本地計(jì)算。n按照用戶要求來控制傳感器的采樣率和傳送率，以此來減少能量消耗。CougarnCornell 大學(xué)的傳感器項(xiàng)目n基本思想：n盡可能多地把計(jì)算下推到傳感器節(jié)點(diǎn)，以此來減少傳感器和服務(wù)器之間地通訊。n傳感器節(jié)點(diǎn)執(zhí)行任務(wù)：n本地計(jì)算n和鄰居傳感器節(jié)點(diǎn)進(jìn)行通訊來完成聚集網(wǎng)內(nèi)

5、聚集(in-network aggregation)半分布式結(jié)構(gòu) (續(xù))n缺點(diǎn):n仍然存在大量的數(shù)據(jù)需要發(fā)送到中心服務(wù)器進(jìn)行進(jìn)一步處理。分布式結(jié)構(gòu)n分布式結(jié)構(gòu)的特性n前提假設(shè)，每個(gè)傳感器節(jié)點(diǎn)具有較高的存儲(chǔ)、計(jì)算和通訊能力。n把所有的計(jì)算和通訊都下推到傳感器網(wǎng)絡(luò)中，沒有中心服務(wù)器。n使用Hash 技術(shù)(比如，DHT,分布式Hash表)來進(jìn)行存儲(chǔ)和檢索傳感器檢測(cè)到的事件。層次結(jié)構(gòu)n主要包括兩個(gè)組成部分n傳感器網(wǎng)絡(luò)層，每個(gè)傳感器節(jié)點(diǎn)具有一定的計(jì)算和存儲(chǔ)能力。其作用是：從代理接受命令進(jìn)行本地計(jì)算將數(shù)據(jù)傳送到代理。n代理網(wǎng)絡(luò)層。每個(gè)代理節(jié)點(diǎn)完成五項(xiàng)任務(wù)：從用戶接收查詢向傳感器節(jié)點(diǎn)發(fā)送控制命令或者其它信息

6、從傳感器節(jié)點(diǎn)接收數(shù)據(jù)處理查詢將查詢結(jié)果返回給用戶。層次結(jié)構(gòu) (續(xù))n特點(diǎn)n克服了單點(diǎn)失敗和性能瓶頸n增強(qiáng)系統(tǒng)可擴(kuò)展性n減少了通訊開銷n更好地使用適應(yīng)性查詢處理技術(shù)n充分利用查詢空間局部性和用戶興趣局部性特征Spatial &Interest Locality提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)數(shù)據(jù)模型n數(shù)據(jù)模型n現(xiàn)有的研究主要是對(duì)傳統(tǒng)的關(guān)系模型、對(duì)象關(guān)系模型或時(shí)間序列模型的有限擴(kuò)展。n將感知數(shù)據(jù)視為分布在多個(gè)節(jié)點(diǎn)上的關(guān)系，將傳感器網(wǎng)絡(luò)看成是一個(gè)分布式數(shù)據(jù)庫n采用時(shí)間序列和概率模型表示感知數(shù)據(jù)的時(shí)間特性和不確定性數(shù)據(jù)模型n研究

7、實(shí)例(一)nTinyDB系統(tǒng)的數(shù)據(jù)模型是對(duì)傳統(tǒng)的關(guān)系模型的簡(jiǎn)單擴(kuò)展。它把傳感器網(wǎng)絡(luò)數(shù)據(jù)定義為一個(gè)單一的、無限長的虛擬關(guān)系。n該表具有兩類屬性：n感知數(shù)據(jù)屬性：溫度值、電壓值n描述感知數(shù)據(jù)的屬性：感知數(shù)據(jù)的獲得時(shí)間、傳感器節(jié)點(diǎn)IDn每個(gè)傳感器節(jié)點(diǎn)產(chǎn)生的每一組讀數(shù)都對(duì)應(yīng)關(guān)系表中的一行（無限虛擬關(guān)系表）數(shù)據(jù)模型 (續(xù))n研究實(shí)例(二)nCougar系統(tǒng)把傳感器網(wǎng)絡(luò)看成是一個(gè)大型分布式數(shù)據(jù)庫系統(tǒng)，每個(gè)傳感器對(duì)應(yīng)于分布式數(shù)據(jù)庫的一個(gè)節(jié)點(diǎn)，存儲(chǔ)部分?jǐn)?shù)據(jù)。nCougar系統(tǒng)的數(shù)據(jù)模型支持傳統(tǒng)的關(guān)系數(shù)據(jù)以及傳感器生成的感知數(shù)據(jù)(用時(shí)間序列來表示)。nCougar系統(tǒng)實(shí)現(xiàn)了時(shí)間序列和關(guān)系數(shù)據(jù)之間的3類操作：n關(guān)

8、系投影操作：把一個(gè)時(shí)間序列轉(zhuǎn)換成一個(gè)關(guān)系。n積操作：輸入一個(gè)關(guān)系和一個(gè)時(shí)間序列，輸出一個(gè)新的時(shí)間序列。n聚集操作：輸入是時(shí)間序列，輸出是關(guān)系時(shí)間序列和關(guān)系數(shù)據(jù)之間操作編號(hào)最低溫度11024編號(hào)溫度時(shí)間(s)1102005.10.31242005.10.31編號(hào)地點(diǎn)1北京2哈爾濱3南京地點(diǎn)溫度濕度(%)時(shí)間(s)北京10202005.10.31哈爾濱4152005.10.31南京14142005.11.01編號(hào)溫度濕度(%)時(shí)間(s)110202005.10.3124152005.10.31314142005.11.01關(guān)系投影操作聚集操作積操作查詢語言n主要查詢模式n快照查詢n連續(xù)查詢n基于實(shí)

9、踐的查詢n基于生命周期的查詢n基于準(zhǔn)確率的查詢查詢語言n基于SQL的查詢語言（TinySQL）;支持選擇、投影、設(shè)定采樣頻率、分組聚集、用戶自定義聚集函數(shù)、事件觸發(fā)、生命周期查詢、設(shè)定存儲(chǔ)節(jié)點(diǎn)和簡(jiǎn)單的連接操作nTinyDB查詢語法SELECT select-list FROM sensorsWHERE predicate GROUP BY gb-list HAVING predicateTRIGGER ACTION command-name(param)EPOCH DURATION time /*定義查詢執(zhí)行的周期*/查詢語言n支持連續(xù)周期性查詢n不支持查詢觸發(fā)器nCougar查詢語法SELE

10、CT select-listFROM Sensordata SWHERE predicate GROUP BY attributesHAVING predicateDURATION time-interval /* 指定查詢的生命期*/EVERY time-span /*定義查詢執(zhí)行的周期*/提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)數(shù)據(jù)存儲(chǔ)與索引技術(shù)n在以數(shù)據(jù)為中心的存儲(chǔ)系統(tǒng)中，每個(gè)傳感器節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)按照數(shù)據(jù)名存儲(chǔ)在網(wǎng)絡(luò)的某個(gè)或某些傳感器節(jié)點(diǎn)上。根據(jù)數(shù)據(jù)項(xiàng)的名字，可以很容易地在傳感器網(wǎng)絡(luò)中找到相應(yīng)的數(shù)據(jù)項(xiàng)。n數(shù)據(jù)命名方法n以數(shù)據(jù)為中心

11、的數(shù)據(jù)存儲(chǔ)方法的性能n數(shù)據(jù)中心存儲(chǔ)方法n一維分布式索引數(shù)據(jù)命名方法n層次命名方法CHINA/Universities/DLUT/CS/cameraln“屬性值”命名方法type=cameravalue=image.jpglocation=“CS Dept, Dalian University of Technology, Dalian, China”n數(shù)據(jù)的命名方法隱含地定義了數(shù)據(jù)能夠被存取的方式。以數(shù)據(jù)為中心的數(shù)據(jù)存儲(chǔ)方法的性能n數(shù)據(jù)存儲(chǔ)方法n以數(shù)據(jù)為中心方法：指使用數(shù)據(jù)名字來存儲(chǔ)和查詢數(shù)據(jù)。通過數(shù)據(jù)名到傳感器節(jié)點(diǎn)的映射算法實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)。n外部存儲(chǔ)方法：把所有感知數(shù)據(jù)都存儲(chǔ)在傳感器以外的計(jì)算

12、機(jī)節(jié)點(diǎn)上。n內(nèi)部存儲(chǔ)方法：所有感知數(shù)據(jù)都存儲(chǔ)在產(chǎn)生該數(shù)據(jù)的傳感器節(jié)點(diǎn)上。以數(shù)據(jù)為中心的數(shù)據(jù)存儲(chǔ)方法的性能 (續(xù))n三類數(shù)據(jù)存儲(chǔ)方法開銷數(shù)據(jù)中心存儲(chǔ)方法n地理散列函數(shù)n地理散列方法把數(shù)據(jù)的關(guān)鍵字被一個(gè)散列函數(shù)隨機(jī)地映射為一個(gè)地理位置，即地理坐標(biāo)(x,y)(注意:這種映射可以是一對(duì)多的)。n地理路由協(xié)議GPSR(greedy perimeter stateless routing)n地理散列方法和GPSR的結(jié)合n增強(qiáng)地理散列方法的魯棒性n地理散列方法的結(jié)構(gòu)復(fù)制一維分布式索引nDIFS (Distributed Index Features in Sensor networks)n參考：DIFS:

13、A Distributed Index for Features in Sensor Networks提綱n傳感器網(wǎng)絡(luò)數(shù)據(jù)管理介紹n系統(tǒng)結(jié)構(gòu)n數(shù)據(jù)模型和查詢語言n數(shù)據(jù)存儲(chǔ)與索引技術(shù)n查詢處理技術(shù)n總結(jié)查詢處理技術(shù)n傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢類型n歷史查詢：對(duì)從傳感器獲得的歷史數(shù)據(jù)的查詢。n “列出1999年A區(qū)域的平均降水量”n快照查詢：對(duì)傳感器網(wǎng)絡(luò)在某一給定時(shí)間點(diǎn)的查詢。n “列出所有傳感器當(dāng)前的溫度值”n連續(xù)查詢：關(guān)注某一段時(shí)間內(nèi)傳感器網(wǎng)絡(luò)數(shù)據(jù)的變化 情況n“列出從現(xiàn)在開始24小時(shí)內(nèi)，A區(qū)域每30分鐘內(nèi)的最高溫度”n傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢處理方法n集中式查詢處理n分布式查詢處理集中與分布式查詢處理方法

14、n集中查詢處理適應(yīng)于：n獲取數(shù)據(jù)存儲(chǔ)于中心數(shù)據(jù)庫；在中心數(shù)據(jù)庫上對(duì)查詢進(jìn)行處理n傳感器能源充足，而且數(shù)據(jù)采集周期長的應(yīng)用環(huán)境n例如: A計(jì)劃n分布式優(yōu)點(diǎn)：n在網(wǎng)絡(luò)內(nèi)對(duì)數(shù)據(jù)進(jìn)行聚集操作n減少數(shù)據(jù)傳送n降低節(jié)點(diǎn)和網(wǎng)絡(luò)地能量消耗n提高查詢響應(yīng)地實(shí)時(shí)性n例如：B計(jì)劃聚集操作的處理技術(shù)n集中式與分布式聚集技術(shù)n流水線聚集技術(shù)集中式與分布式聚集技術(shù)n集中式聚集：n所有的傳感器首先將數(shù)據(jù)都傳送到客戶端，然后在客戶端執(zhí)行聚集。n分布式聚集：n在傳感器網(wǎng)絡(luò)內(nèi)由多個(gè)傳感器節(jié)點(diǎn)協(xié)作執(zhí)行聚集操作，最后將聚集結(jié)果路由到客戶端。流水線聚集技術(shù)n在傳感器網(wǎng)絡(luò)內(nèi)進(jìn)行聚集計(jì)算時(shí)，由于通訊失敗、節(jié)點(diǎn)移動(dòng)等原因，很難保證結(jié)果完全正

15、確。n流水線聚集技術(shù)把時(shí)間分為多個(gè)長度為i秒的時(shí)間段。在每個(gè)時(shí)間段內(nèi)，收到聚集請(qǐng)求的每個(gè)節(jié)點(diǎn)都將前一個(gè)時(shí)間段收到的子節(jié)點(diǎn)的數(shù)據(jù)與本地感知數(shù)據(jù)作聚集，并將得到的部分聚集結(jié)果向上傳送。n能夠使未收到聚集請(qǐng)求的節(jié)點(diǎn)參與聚集 運(yùn)算。n每隔i秒都收到一個(gè)新的聚集結(jié)果。流水線聚集范例SELECT COUNT(*) FROM sensors流水線聚集范例SELECT COUNT(*) FROM sensors流水線聚集范例SELECT COUNT(*) FROM sensors流水線聚集范例SELECT COUNT(*) FROM sensors流水線聚集范例SELECT COUNT(*) FROM sen

16、sors流水線聚集范例SELECT COUNT(*) FROM sensorsTinyDB的查詢處理技術(shù)n元數(shù)據(jù)管理n計(jì)算謂詞和執(zhí)行采樣操作的優(yōu)化排序n具有事件查詢的優(yōu)化技術(shù)元數(shù)據(jù)管理n節(jié)點(diǎn)的元數(shù)據(jù)包括n屬性n事件n用戶自定義的功能n擴(kuò)展聚集函數(shù)的定義者必須提供關(guān)于聚集函數(shù)特 征信息.TinyDB要求擴(kuò)展聚集函數(shù)必須是單調(diào)的 (Monotonic)比如COUNT()可表征的(Exemplary),比如MIN();或者歸納的(Summary)比如 AVERAGE()n與處理和傳輸數(shù)據(jù)的能源消耗相關(guān)的信息計(jì)算謂詞和執(zhí)行采樣操作的優(yōu)化排序nTinyDB優(yōu)化器解決采樣操作與謂詞操作優(yōu)化排序問題的過程：n調(diào)用解決具有串并聯(lián)圖約束的操作排序問題的算法，產(chǎn)生一個(gè)采樣操作和謂詞操作的優(yōu)化序列。n確定序列中可共享的采樣操作，從隊(duì)列中刪除不必要的采樣操作。n產(chǎn)生采樣操作和謂詞操作的優(yōu)化執(zhí)行計(jì)劃。操作排序問題舉例SELECT light, magFROM sensorsWHERE pred1(mag)AND pred2(light)SAMPLE INTERVAL 1s E(mag) E(light)1500 uJ vs. 90 uJ Possible orderings:1. Sample light Sample mag Apply pred1 Apply pred22.