無線傳感器網(wǎng)絡(luò)多維top-k主導(dǎo)查詢.pdf

1、傳感器以及傳感器網(wǎng)絡(luò)技術(shù)正在快速進(jìn)步,一系列新型的信息查詢技術(shù)也隨之產(chǎn)生。top-k主導(dǎo)查詢要求返回一組數(shù)據(jù)中主導(dǎo)其他數(shù)據(jù)個(gè)數(shù)最多的k個(gè)數(shù)據(jù)。對(duì)于異常事件檢測(cè)、動(dòng)物行為變化監(jiān)測(cè)等傳感器網(wǎng)絡(luò)應(yīng)用,top-k主導(dǎo)查詢非常重要。top-k主導(dǎo)查詢結(jié)合了skyline查詢和top-k查詢的優(yōu)點(diǎn),不僅有效控制了返回?cái)?shù)據(jù)的數(shù)目,而且不依賴于用戶偏好:top-k主導(dǎo)查詢對(duì)于任何用戶返回相同的結(jié)果。
　　傳感器采集的數(shù)據(jù)往往具有多維分量、數(shù)量龐大

2、,上傳全部數(shù)據(jù)到源節(jié)點(diǎn)將耗費(fèi)巨大的通信開銷。因此,我們必須設(shè)計(jì)高效的算法,以盡可能減小top-k主導(dǎo)查詢的總通信開銷。同時(shí),集中式算法不適用于傳感器網(wǎng)絡(luò)環(huán)境,這增大了設(shè)計(jì)算法的難度。最后,即使總通信開銷得到有效控制,如果某個(gè)節(jié)點(diǎn)的通信量遠(yuǎn)大于其他節(jié)點(diǎn)(我們稱該節(jié)點(diǎn)為瓶頸節(jié)點(diǎn)),也會(huì)極大地減小傳感器網(wǎng)絡(luò)的使用壽命,所以我們?cè)O(shè)計(jì)的算法必須盡可能減小瓶頸節(jié)點(diǎn)的通信開銷。
　　本文是第一個(gè)致力于解決多維傳感器數(shù)據(jù)top-k主導(dǎo)查詢問題的工

3、作。我們提出了三種有效算法,首先,我們提出了直觀的簡(jiǎn)單算法,它在得到的top-k查詢結(jié)果的基礎(chǔ)上進(jìn)行;然后,我們基于二等分空間劃分策略(BinarySpacePartitioning,BSP)提出了基礎(chǔ)算法;最后,我們利用傳感器數(shù)據(jù)具有時(shí)間相關(guān)性和空間相關(guān)性的特點(diǎn),提出了改進(jìn)算法。接著,我們?yōu)楹?jiǎn)單算法和基礎(chǔ)算法給出通信開銷分析和瓶頸分析。為了展現(xiàn)算法的效果,我們?cè)贗ntelBerkeley實(shí)驗(yàn)室數(shù)據(jù)集和三種合成數(shù)據(jù)集的基礎(chǔ)上進(jìn)行了多組仿