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

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

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

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