近似查詢處理(數(shù)據(jù)庫)

時(shí)間：2022-12-29 18:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-29 18:30:01 來源：信息時(shí)代

    近似查詢處理 : 允許查詢結(jié)果具有一定誤差的查詢處理技術(shù)。查詢所獲得的結(jié)果不要求是精確結(jié)果,而是在一定的誤差允許范圍內(nèi)的結(jié)果。傳感器節(jié)點(diǎn)的物理特點(diǎn)導(dǎo)致節(jié)點(diǎn)感知的數(shù)據(jù)多具有一定的誤差值,在很多情況下,人們并不需要知道節(jié)點(diǎn)的精確數(shù)據(jù),而只需要通過一些近似查詢處理技術(shù)就可以完成查詢。
近似查詢處理主要利用感知數(shù)據(jù)間的關(guān)聯(lián)性,通過上傳給基站的部分?jǐn)?shù)據(jù)推測(cè)整體數(shù)據(jù)的情況,從而縮減傳遞的數(shù)據(jù)量,減少能量的消耗。無線傳感器網(wǎng)絡(luò)中的主要的近似查詢處理涉及到: 通過鄰居節(jié)點(diǎn)或節(jié)點(diǎn)的歷史數(shù)據(jù)來近似估計(jì)實(shí)際情況,以及利用一些統(tǒng)計(jì)學(xué)技術(shù)來估算查詢結(jié)果。基于模型分析、基于概要技術(shù)和數(shù)據(jù)卸載等方法是常用的近似查詢處理方法。
1.基于模型分析的近似查詢處理方法
傳感器網(wǎng)絡(luò)收集的感知數(shù)據(jù)只表示在采樣點(diǎn)上的一些離散信息。模型認(rèn)為所有傳感器節(jié)點(diǎn)感知的不同類型的數(shù)據(jù)之間都存在一定的關(guān)系。給定一個(gè)模型,某個(gè)節(jié)點(diǎn)產(chǎn)生的某種類型的數(shù)據(jù)可以用來估計(jì)出其他節(jié)點(diǎn)產(chǎn)生的其他類型的數(shù)據(jù)。例如,一個(gè)節(jié)點(diǎn)的溫度采樣很有可能會(huì)提高對(duì)附近節(jié)點(diǎn)的感知的濕度數(shù)據(jù)的估計(jì)的可信度。另外,從通信代價(jià)的角度來講,接收近距離節(jié)點(diǎn)的數(shù)據(jù)要比接收遠(yuǎn)距離節(jié)點(diǎn)的數(shù)據(jù)節(jié)省能量。
模型可以用來對(duì)傳感器讀數(shù)進(jìn)行更好地分析,幫助解決采樣值在空間上的不均衡問題,幫助確認(rèn)提供錯(cuò)誤信息的節(jié)點(diǎn),并且推斷出壞死節(jié)點(diǎn)或即將壞死節(jié)點(diǎn)的采樣數(shù)據(jù)。另外,模型提供了一個(gè)框架,可以優(yōu)化傳感器的數(shù)據(jù)接收——只有在當(dāng)前模型不能夠推斷出一個(gè)符合精度的數(shù)據(jù)時(shí),才允許傳感器采集數(shù)據(jù)。常用的模型包括概率模型和線性模型。
查詢處理引擎使用概率模型(probabilistic model)來回答關(guān)于傳感器網(wǎng)絡(luò)當(dāng)前狀態(tài)的查詢。使用一個(gè)概率密度函數(shù)p(X₁,X₂,X₃,…,X_n)來表示這個(gè)模型,X_i是某個(gè)傳感器上的某個(gè)屬性(例如,5號(hào)節(jié)點(diǎn)上的溫度)。通常每個(gè)傳感器的某種類型只能對(duì)應(yīng)一個(gè)屬性。
用戶提出感知查詢后,這些查詢被翻譯成基于模型的概率運(yùn)算。錯(cuò)誤容忍度(error tolerance)和目標(biāo)可信度(target confidence)表明了用戶對(duì)于近似性的要求。如果用模型估計(jì)出的概率滿足或超出用戶定義的可信度,概率模型可以直接給出估計(jì)出的數(shù)值。如果概率模型的可信度比較低,概率模型就需要在回答查詢之前從傳感器網(wǎng)絡(luò)中獲得可以幫助提高精度的采樣值。選擇哪些節(jié)點(diǎn)的采樣值是一個(gè)優(yōu)化的問題,通過優(yōu)化可以選擇最好的一組屬性來觀察,盡量在滿足用戶提出的可信度的同時(shí)將這個(gè)過程耗費(fèi)的能量代價(jià)減小到最少。
線性模型假設(shè)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)間具有一定程度的感知數(shù)據(jù)空間關(guān)聯(lián)性,即線性相關(guān)性。線性模型可以被應(yīng)用于“區(qū)域快照查詢”中。這種查詢以盡量縮小查詢?cè)L問節(jié)點(diǎn)個(gè)數(shù)為目的。區(qū)域快照是由一組被選定的代表節(jié)點(diǎn)和一個(gè)閾值T構(gòu)成的。通過這些代表節(jié)點(diǎn)的地理位置以及節(jié)點(diǎn)采樣值可以得到網(wǎng)絡(luò)中數(shù)值分布的梗概。線性模型需要不斷地學(xué)習(xí)來提高準(zhǔn)確度,學(xué)習(xí)的過程是: 在節(jié)點(diǎn)的緩存中不斷讀取新的有價(jià)值的數(shù)據(jù),來確保節(jié)點(diǎn)感知的數(shù)據(jù)始終能與一個(gè)代表節(jié)點(diǎn)感知的數(shù)據(jù)相似。節(jié)點(diǎn)需要周期性的檢測(cè)代表節(jié)點(diǎn)是否稱職,如果發(fā)現(xiàn)代表節(jié)點(diǎn)能量不足或者壞死,節(jié)點(diǎn)會(huì)重新發(fā)出邀請(qǐng),重新選擇代表節(jié)點(diǎn)。
線性模型假設(shè)地理位置相鄰的節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)滿足線性關(guān)系,如室內(nèi)聲音監(jiān)控應(yīng)用。但在很多應(yīng)用中,空間上相鄰的節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)通常并不十分滿足線性關(guān)系,而很可能是隨機(jī)數(shù)據(jù)或者是滿足一定概率相關(guān)性的數(shù)據(jù)。
2.基于概要技術(shù)的近似查詢處理方法
概要技術(shù)(sketch)的核心思想是利用哈希函數(shù)把數(shù)據(jù)從一個(gè)取值范圍映射到另一個(gè)占用較小內(nèi)存空間的取值范圍,生成概要數(shù)據(jù)結(jié)構(gòu)。Flajolet和Martin提出了支持計(jì)數(shù)查詢的概要技術(shù)(counting sketch),用來快速地求解數(shù)據(jù)集中不同元素的個(gè)數(shù),簡(jiǎn)稱為FM概要(FM sketch)技術(shù)。
FM概要技術(shù)被應(yīng)用到無線傳感器網(wǎng)絡(luò)的感知查詢處理中。經(jīng)過一次遍歷并只用一小塊空間就能快速估計(jì)感知數(shù)據(jù)流中不同元素的個(gè)數(shù),在節(jié)省能量的同時(shí)也盡可能地提高了查詢精度。使用FM概要技術(shù)進(jìn)行網(wǎng)內(nèi)聚集對(duì)于無線傳感器網(wǎng)絡(luò)具有很強(qiáng)的適應(yīng)性。傳感器網(wǎng)絡(luò)的無線傳播特性使一個(gè)節(jié)點(diǎn)同時(shí)向很多鄰居節(jié)點(diǎn)進(jìn)行廣播成為可能。其次,sketch技術(shù)對(duì)復(fù)制不敏感,允許一個(gè)傳感器節(jié)點(diǎn)把所有傳給它的網(wǎng)絡(luò)數(shù)據(jù)合并到一個(gè)將要發(fā)送的數(shù)據(jù)包中。選擇合適的同步策略,就可以非常方便地聚集數(shù)據(jù)而每個(gè)節(jié)點(diǎn)只需進(jìn)行一次廣播。
3.利用數(shù)據(jù)卸載技術(shù)的近似查詢處理方法
數(shù)據(jù)卸載在無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)管理中被廣泛使用,在此主要介紹數(shù)據(jù)卸載在近似連接查詢中的應(yīng)用。在無線傳感器網(wǎng)絡(luò)中執(zhí)行多連接查詢時(shí),需要耗費(fèi)巨大能量在節(jié)點(diǎn)之間進(jìn)行大量的數(shù)據(jù)傳輸。在一個(gè)小型的由電池驅(qū)動(dòng)的無線傳感器網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)都受能量和存儲(chǔ)容量的限制,而在網(wǎng)絡(luò)之外存在一個(gè)連接節(jié)點(diǎn),它的能量、內(nèi)存和CPU都不受限制。網(wǎng)絡(luò)的任務(wù)是監(jiān)測(cè)環(huán)境數(shù)據(jù),并利用感知到的數(shù)據(jù)進(jìn)行連接。為了計(jì)算一個(gè)給定時(shí)間段內(nèi)的感知數(shù)據(jù)的連接結(jié)果,連接節(jié)點(diǎn)需要向網(wǎng)絡(luò)中的節(jié)點(diǎn)發(fā)出查詢,接著,數(shù)據(jù)節(jié)點(diǎn)將自己的數(shù)據(jù)發(fā)送到連接節(jié)點(diǎn)進(jìn)行連接。為節(jié)省能量開銷,每個(gè)數(shù)據(jù)節(jié)點(diǎn)傳送盡量少的數(shù)據(jù)到連接節(jié)點(diǎn)。在每次傳送數(shù)據(jù)之前,數(shù)據(jù)節(jié)點(diǎn)先將本地感知數(shù)據(jù)的概要信息傳送給連接節(jié)點(diǎn)。連接節(jié)點(diǎn)利用這些概要信息來決定從不同的節(jié)點(diǎn)索取實(shí)際的數(shù)據(jù)。連接節(jié)點(diǎn)只會(huì)向每個(gè)節(jié)點(diǎn)索取它所感知的數(shù)據(jù)中的一部分,產(chǎn)生的連接結(jié)果是傳送全部數(shù)據(jù)時(shí)的連接結(jié)果集的子集。這一問題稱為傳感網(wǎng)絡(luò)中的近似連接問題。在進(jìn)行近似連接時(shí),希望連接節(jié)點(diǎn)向不同的數(shù)據(jù)節(jié)點(diǎn)索取的數(shù)據(jù)能夠滿足最大連接結(jié)果子集(MAX-subset)要求,即被傳送給連接節(jié)點(diǎn)的數(shù)據(jù)可以產(chǎn)生最大的連接結(jié)果集。