一種高效的高維數(shù)據(jù)流查詢方法研究

曾利軍

(湖南工學(xué)院 計(jì)算機(jī)與信息科學(xué)學(xué)院，湖南 衡陽421002)

0 引言

Top-k查詢大量運(yùn)用在數(shù)據(jù)庫領(lǐng)域，可以從大量數(shù)據(jù)庫中提取到K個(gè)數(shù)據(jù)集或者數(shù)據(jù)點(diǎn)。目前面臨兩方面的挑戰(zhàn)，許多研究通過數(shù)據(jù)融合來完成數(shù)據(jù)查詢處理，來減少傳送能耗、增長傳感器生命期。數(shù)據(jù)融合技術(shù)中，傳感器網(wǎng)絡(luò)最基礎(chǔ)的應(yīng)用為 top-k。 Silberstein.et.al[1-2]提出了一種線性top-k查詢方法，設(shè)計(jì)了數(shù)據(jù)查詢器。Zeinalipont et.al[3]提出了一種閥值數(shù)據(jù)查詢算法，需查詢的各個(gè)屬性區(qū)域設(shè)置了一些不同的閥值來減小對基站所傳送的無用數(shù)據(jù)。Wu et.al[4-5]在節(jié)點(diǎn)中設(shè)置了濾波器來濾除無用的數(shù)據(jù)。上面的幾種算法一定程度上改善了傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢的效率，降低了能耗，關(guān)注的卻是傳感器一維數(shù)據(jù)集。而傳感器網(wǎng)絡(luò)高維數(shù)據(jù)的查詢在理論研究及實(shí)際應(yīng)用中，同樣有著非常重要的意義，如海洋的檢測研究，生物學(xué)家關(guān)注的是光照度、水溫等，地質(zhì)學(xué)家卻關(guān)注水流速度、酸堿度等。需要設(shè)計(jì)的系統(tǒng)可根據(jù)用戶的需求及偏好采用多屬性的查詢方式。而無線傳感器網(wǎng)絡(luò)多維數(shù)據(jù)查詢研究較少。設(shè)計(jì)傳感器的節(jié)點(diǎn)能量高效及多用戶需求與偏好的連續(xù)高維數(shù)據(jù)的top-k查詢?yōu)楫?dāng)前要解決的首要問題。

1 問題描述

無線傳感器網(wǎng)絡(luò)中，假設(shè)數(shù)據(jù)集為D＝{d1，d2.....dn}，di則為 m-維數(shù)據(jù)點(diǎn)即表示為(m+2)個(gè)數(shù)據(jù)元組：di＝（di.x1，di.x2，.......，di.xm，di.id，di.t），di.xi表示為數(shù)據(jù)，di.id表示為數(shù)據(jù)類ID號，di.t表示所需要的時(shí)間。用戶需求的查詢函數(shù)則可以定義[4]為：表示數(shù)據(jù)在 j維的權(quán)重。用戶需求top-k查詢指的是在數(shù)據(jù)D中來查詢F的函數(shù)值最大K個(gè)點(diǎn)。同多數(shù)研究相同，只需要去考慮典型線性凸函數(shù)。該單調(diào)函數(shù)要滿足以下條件：若 xj≤xj′，則 F（x1，x2，...，xm）≤F（x1′，x2′，...，xm′）。如數(shù)據(jù)維度是 2，對應(yīng) di四元組表示為＜di.x1，di.x2，di.id，di.t＞，di.x1，di.x2則為采樣值。無線傳感器的sink節(jié)點(diǎn)需依據(jù)用戶的每個(gè)wj權(quán)重來返回查詢結(jié)果，表示為URS，用戶偏好不同，則wj不同，傳感器sink節(jié)點(diǎn)可能不只返回K個(gè)結(jié)果。

2 用戶高維處理框架

為了高維數(shù)據(jù)查詢擴(kuò)展的方便、提高數(shù)據(jù)的查詢精度以及減少數(shù)據(jù)通信量，提出一種用戶的高維數(shù)據(jù)查詢處理架構(gòu)。高維數(shù)據(jù)查詢處理框架如圖1，在傳統(tǒng)的框架上進(jìn)行改進(jìn)，具體的改進(jìn)有以下幾點(diǎn)：

（1）根據(jù)用戶的偏好不同，來賦值權(quán)重K值，優(yōu)先來響應(yīng)較大K值的查詢請求；

（2）通過增加可選單元，用來進(jìn)行模糊查詢或處理數(shù)據(jù)老化，與其它設(shè)備相連；

（3）支配圖接收的數(shù)據(jù)查詢結(jié)果同Sink節(jié)點(diǎn)查詢結(jié)果相融合，再傳送到節(jié)點(diǎn)；

（4）從圖1得出，改進(jìn)的處理框架將不會依賴傳感器網(wǎng)絡(luò)路由，各路由結(jié)構(gòu)都可以采用。

圖1中用戶數(shù)據(jù)流先通過無線傳感器網(wǎng)絡(luò)傳送，如果Sink節(jié)點(diǎn)接收的數(shù)據(jù)查詢結(jié)果為RS，則節(jié)點(diǎn)通過檢測支配圖，再與RS相融合，最終傳送給數(shù)據(jù)流目的節(jié)點(diǎn)以及與Sink節(jié)點(diǎn)的匯合?；緜魉蛿?shù)據(jù)同時(shí)，還會回傳TOP-K全局的數(shù)據(jù)信息給無線傳感器網(wǎng)絡(luò)，也可以在當(dāng)經(jīng)過濾波器信息時(shí)，傳送給全局網(wǎng)絡(luò)接收，但可能會影響到數(shù)據(jù)查詢的精度以及查詢的結(jié)果重復(fù)，造成數(shù)據(jù)受限。要進(jìn)行更好的高維數(shù)據(jù)查詢，需在已有的TOP-K基本數(shù)據(jù)查詢方法上，提出一種新的改進(jìn)的用戶高維數(shù)據(jù)查詢算法。

圖1 用戶數(shù)據(jù)高維查詢處理結(jié)構(gòu)圖

3 改進(jìn)的用戶高維數(shù)據(jù)TOP-K查詢算法

由于傳感器網(wǎng)絡(luò)不能進(jìn)行大規(guī)模的通信，通過sink節(jié)點(diǎn)的連續(xù)分發(fā)進(jìn)行濾波器更新難以實(shí)現(xiàn)。同時(shí)濾波器在過濾數(shù)據(jù)需要來設(shè)置其數(shù)據(jù)過期時(shí)間，如果數(shù)據(jù)過期時(shí)間不設(shè)置，則需要設(shè)置區(qū)域的節(jié)點(diǎn)數(shù)設(shè)為counts，F(xiàn)Lsink設(shè)為節(jié)點(diǎn)更新濾波器，設(shè)為節(jié)點(diǎn)數(shù)據(jù)傳送到sink平均路徑的長度。.N則為更新濾波器所引起的額外開銷。如果數(shù)據(jù)過期需要更新一個(gè)濾波器，更新算法如下所示：

輸入表示為sink節(jié)點(diǎn)有效支配圖（DG），輸出表示為非top-k的結(jié)果節(jié)點(diǎn)集合（NS）以及counts

（1）loop：If Sink 所接收的新數(shù)據(jù) data 或者支配圖（DG）的數(shù)據(jù)過期then

（2）更新區(qū)域中Sink的數(shù)據(jù)DG

（3）計(jì)算更新后支配圖（DG）的 FLsink

（4）If FLsink配的新數(shù)據(jù) data then

（5）counts← counts+1；NS ← NS∪{i}

（6）end if

（8）Sink 給集合（NS）各個(gè)節(jié)點(diǎn)發(fā)布 FLsink

（9）count← 0；NS ← φ

（10）end if

（11）end if

（12）end loop

改進(jìn)后的數(shù)據(jù)節(jié)點(diǎn)處理模塊，當(dāng)數(shù)據(jù)節(jié)點(diǎn)接收到濾波器的數(shù)據(jù)集FLsink以后，會進(jìn)行當(dāng)?shù)貫V波器的更新，再從濾波器中去掉過期數(shù)據(jù)，最后尋找需發(fā)送的點(diǎn)（不屬于TOP-K的查詢結(jié)果）。如果FLi為非支配的新數(shù)據(jù)datai，需將數(shù)據(jù)傳送到父節(jié)點(diǎn)，同時(shí)在循環(huán)中去掉過期的數(shù)據(jù)。TSi設(shè)為節(jié)點(diǎn)所發(fā)送數(shù)據(jù)集。

4 總結(jié)

在傳統(tǒng)的數(shù)據(jù)查詢基礎(chǔ)上，設(shè)計(jì)出一種用戶偏好函數(shù)無線傳感器數(shù)據(jù)處理框架。通過支配圖維護(hù)top-k數(shù)據(jù)查詢信息。

通過數(shù)據(jù)支配信息來設(shè)定偏好函數(shù)，使用戶的數(shù)據(jù)查詢更易實(shí)現(xiàn)，而非top-k數(shù)據(jù)查詢結(jié)果可以通過濾波器來進(jìn)行數(shù)據(jù)的過濾處理。本架構(gòu)還有較好的擴(kuò)展性，通過在框架的可選單元加入模糊數(shù)據(jù)查詢，用來解決數(shù)據(jù)的老化。下一步研究異構(gòu)傳感器數(shù)據(jù)通信的內(nèi)容。

［1］Silberstein A，Braynard R，Ellis C，et a1.A SamPling-based Approach to Optimizing Top-k Queries in Sensor Networks[J].Proceedings of IEEE ICDE，2010.

［2］曾利軍，劉卉，彭廣.動態(tài)傳感器網(wǎng)絡(luò)區(qū)域受限的移動sink路徑選擇研究[J].計(jì)算機(jī)應(yīng)用研究，2013，30（6）：1652-1655.

［3］Zeinalipont D，Vagena Z，Gunopulos D，et al.The Threshold Join Algorithm for Top-k Queries in Distributed Sensor Networks[J].Proceedings of workshop data Management for Sensor Networks(DMSN)，2009.

［4］劉卉，李澤軍.基于投影矢量的雙組播樹高效路由數(shù)據(jù)收集[J].傳感技術(shù)學(xué)報(bào)，2013，26（4）：570-576.

［5］Wu M，Xu J Tang X，et al.Top-k Monitoring in Wireless Sensor Networks.IEEE Trans[J].On Knowledge and Data Engineering(TKDE)，2011，19（7）.