基于分簇的近似KNN的查詢優(yōu)化算法

黃 月

(沈陽(yáng)理工大學(xué) 自動(dòng)化與電氣工程學(xué)院，沈陽(yáng) 110159)

數(shù)據(jù)查詢是無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)研究的重要內(nèi)容之一。由于傳感器網(wǎng)絡(luò)分布在較大的監(jiān)測(cè)區(qū)域內(nèi)，因此會(huì)產(chǎn)生大量的分布式數(shù)據(jù)，且節(jié)點(diǎn)資源非常有限，查詢過程將消耗大量的能量，因此研究高效的數(shù)據(jù)查詢方法將會(huì)提高網(wǎng)絡(luò)的生存時(shí)間[1-3]。

K近鄰(K-Nearest Neighbor)查詢即查詢距離給定查詢點(diǎn)最近的K個(gè)對(duì)象，在WSN中K近鄰查詢的查詢結(jié)果不僅取決于單個(gè)節(jié)點(diǎn)的數(shù)據(jù)，而且還與其他節(jié)點(diǎn)的數(shù)據(jù)有關(guān)聯(lián)，因此，K近鄰查詢屬于傳感器網(wǎng)絡(luò)中的復(fù)雜查詢問題[4]。傳感器網(wǎng)絡(luò)的數(shù)據(jù)查詢可以分為基于位置的查詢(location-based query)和基于數(shù)值的查詢(value-based query)?；谖恢貌樵兊哪繕?biāo)是查詢相關(guān)空間位置上及其周圍節(jié)點(diǎn)的信息；基于數(shù)值查詢的目標(biāo)是查詢某一數(shù)據(jù)及其周圍數(shù)據(jù)的信息?；谖恢玫牟樵儷@得較多研究成果：Yingqi Xu等[5]提出GRT算法，利用節(jié)點(diǎn)的空間信息建立全局樹結(jié)構(gòu)進(jìn)行查詢。J.Winter等[6]提出KPT算法，該算法利用節(jié)點(diǎn)之間互相通信建立近鄰信息，然后通過廣播通知通信半徑內(nèi)的節(jié)點(diǎn)上傳k-1個(gè)信息，該算法不需要建立檢索結(jié)構(gòu)，算法適用性較強(qiáng)。Yingqi Xu等[7]提出IWQE算法，該算法采用地理路由協(xié)議，首先在查詢范圍內(nèi)選擇查詢節(jié)點(diǎn)，查詢節(jié)點(diǎn)負(fù)責(zé)廣播查詢請(qǐng)求，當(dāng)查詢節(jié)點(diǎn)收到采集信息后，將信息與查詢請(qǐng)求發(fā)送至下一跳的查詢節(jié)點(diǎn)。由于傳感器網(wǎng)絡(luò)的數(shù)據(jù)分散且數(shù)據(jù)相關(guān)性較大，基于數(shù)值的查詢大都集中在Top-k[8]研究，因此研究基于數(shù)值的KNN查詢具有較高的實(shí)際和理論意義。Yongxuan Lai等[9]提出KVC算法，首先根據(jù)節(jié)點(diǎn)測(cè)量的數(shù)據(jù)進(jìn)行分簇，然后在簇內(nèi)選擇存儲(chǔ)節(jié)點(diǎn)，該算法將數(shù)據(jù)在網(wǎng)內(nèi)進(jìn)行處理，減少了數(shù)據(jù)的通信量，但當(dāng)網(wǎng)絡(luò)的數(shù)據(jù)較分散時(shí)，效果變差。李斌陽(yáng)等[10]提出基于過濾器的近似一維KNN查詢優(yōu)化算法(FAKNN)，該算法利用經(jīng)驗(yàn)值作為過濾器，通過過濾器阻止無(wú)效數(shù)據(jù)的發(fā)送，從而節(jié)省節(jié)點(diǎn)能量。

本文提出一種基于分簇的近似KNN查詢優(yōu)化(Approximate K-Nearest Neighbor Based Clustering——CAKNN)算法，提出基于位置、數(shù)據(jù)的分簇算法，該算法將測(cè)量數(shù)據(jù)值及物理位置接近的節(jié)點(diǎn)分為一簇，因此會(huì)減少數(shù)據(jù)傳輸跳數(shù)，降低節(jié)點(diǎn)能量的消耗，但當(dāng)?shù)乩砦恢幂^遠(yuǎn)的節(jié)點(diǎn)測(cè)得相近的數(shù)據(jù)時(shí)，會(huì)導(dǎo)致簇與簇之間測(cè)量數(shù)據(jù)的范圍產(chǎn)生重疊，基于數(shù)據(jù)離散度的查詢算法，通過簇頭節(jié)點(diǎn)報(bào)告的信息，基站可以確定查詢存儲(chǔ)節(jié)點(diǎn)的數(shù)量及查詢個(gè)數(shù)，從而解決簇之間測(cè)量范圍重疊的問題。整體算法可以分為初始化階段和查詢階段。

1 查詢系統(tǒng)的建立

本文基于以下假設(shè)：

(1)傳感器網(wǎng)絡(luò)中存在三類節(jié)點(diǎn)：基站、存儲(chǔ)節(jié)點(diǎn)和采集節(jié)點(diǎn)。在網(wǎng)絡(luò)初始化階段基站負(fù)責(zé)接收數(shù)據(jù)、對(duì)節(jié)點(diǎn)進(jìn)行分簇及選擇存儲(chǔ)節(jié)點(diǎn)，并廣播每個(gè)存儲(chǔ)節(jié)點(diǎn)的測(cè)量范圍，在查詢階段基站負(fù)責(zé)發(fā)送查詢指令；存儲(chǔ)節(jié)點(diǎn)具有較大的存儲(chǔ)能力。

(2)查詢階段，采集節(jié)點(diǎn)以固定頻率采集數(shù)據(jù)，并將數(shù)據(jù)傳送給存儲(chǔ)節(jié)點(diǎn)，若存儲(chǔ)節(jié)點(diǎn)的測(cè)量范圍與其他存儲(chǔ)節(jié)點(diǎn)的測(cè)量范圍產(chǎn)生重疊，則存儲(chǔ)節(jié)點(diǎn)向基站發(fā)送更新報(bào)告，否則不發(fā)送。若基站接收到存儲(chǔ)節(jié)點(diǎn)的更新報(bào)告，則重新進(jìn)行分簇及存儲(chǔ)節(jié)點(diǎn)的選擇。

(3)在較小的時(shí)間間隔和區(qū)域內(nèi)，節(jié)點(diǎn)的監(jiān)測(cè)信息具有相似性，即監(jiān)測(cè)信息變化較小。

圖1 查詢系統(tǒng)結(jié)構(gòu)圖注：○傳感器節(jié)點(diǎn)；△存儲(chǔ)節(jié)點(diǎn)；□基站。

1.1 LVC算法

由于傳感器節(jié)點(diǎn)廣泛分布在較大的監(jiān)測(cè)區(qū)域內(nèi)，若兩個(gè)節(jié)點(diǎn)的測(cè)量數(shù)據(jù)值比較接近，但位置相距較遠(yuǎn)(如圖1節(jié)點(diǎn)1和節(jié)點(diǎn)2所示)，只考慮測(cè)量數(shù)據(jù)進(jìn)行分簇(如K均值分簇)，則簇與簇的測(cè)量范圍不會(huì)產(chǎn)生重疊，即將簇的測(cè)量范圍從小到大依次排列得到[lb1,hb1],…[lbm,hbm]，則lbk≥hbk-1,(k=2,…,m)。但可能將兩個(gè)相距較遠(yuǎn)的節(jié)點(diǎn)分在一個(gè)簇內(nèi)，當(dāng)節(jié)點(diǎn)向存儲(chǔ)節(jié)點(diǎn)傳送數(shù)據(jù)時(shí)會(huì)消耗較多的能量。本文提出一種基于位置-數(shù)據(jù)的分簇(Location-Value Clustering,LVC)算法。

算法偽代碼如下所示：

LVC算法偽代碼初始化:N個(gè)節(jié)點(diǎn),分簇的數(shù)量為Cluster_num-1。while (有兩個(gè)以上的簇測(cè)量范圍重合)Cluster_num=Cluster_num + 1;為每個(gè)簇任意分配一個(gè)節(jié)點(diǎn)Cluster(i)={NVi}。while (簇的集合發(fā)生變化)計(jì)算每個(gè)簇的測(cè)量中心CVCi=∑mj=1valuej計(jì)算每個(gè)簇的位置中心CLCi_X=∑mj=1xj CLCi_Y=∑mj=1yjfor i=1:N 計(jì)算節(jié)點(diǎn)i到每個(gè)簇測(cè)量中心的距離Dist_Value( j ); 計(jì)算節(jié)點(diǎn)i到每個(gè)簇位置中心的歐氏距離Dist( j ); MaxDist=Max(Dist); 若Dist(t)

1.2 存儲(chǔ)節(jié)點(diǎn)的選擇

當(dāng)傳感器網(wǎng)絡(luò)分簇完成后，基站根據(jù)每個(gè)簇包含的節(jié)點(diǎn)集合及節(jié)點(diǎn)的測(cè)量值建立簇的參數(shù)矩陣[cid,sp_id,size,mean,var,lb,hb]，cid為簇的ID號(hào)；sp_id為該簇存儲(chǔ)節(jié)點(diǎn)的ID號(hào)；size為簇內(nèi)的節(jié)點(diǎn)數(shù)量；mean為該簇測(cè)量值的均值；var為該簇測(cè)量值的方差；lb為該簇的測(cè)量下限；hb為該簇的測(cè)量上限。設(shè)簇i的集合為Clsteri={NV1,NV2,…,NVm}，用線性規(guī)劃模型確定存儲(chǔ)節(jié)點(diǎn)：

(1)

sp∈Clusteri,NVi∈Clusteri,

dist(NVi,sp)即為節(jié)點(diǎn)i到存儲(chǔ)點(diǎn)sp的歐式距離。

當(dāng)簇內(nèi)節(jié)點(diǎn)的查詢數(shù)據(jù)發(fā)生變化但簇之間的測(cè)量范圍沒有產(chǎn)生新的重疊，即lbk≥hbk-1,(k=2,…,m)，簇頭僅向基站報(bào)告新的均值和方差，不用報(bào)告每個(gè)節(jié)點(diǎn)的變化情況，因此可以降低能量消耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。若簇之間的測(cè)量范圍產(chǎn)生新的重疊，則重新分簇。由于存儲(chǔ)節(jié)點(diǎn)需要不斷監(jiān)聽網(wǎng)絡(luò)狀態(tài)，因此要消耗較多的能量，可以周期性選擇存儲(chǔ)節(jié)點(diǎn)周圍的節(jié)點(diǎn)作為新的存儲(chǔ)節(jié)點(diǎn)。

2 查詢處理

當(dāng)查詢指令[qv,k]到達(dá)后，基站根據(jù)簇頭的數(shù)據(jù)特點(diǎn)〈cid,sp_id,size,mean,var,lb,hb〉判斷查詢哪些簇的存儲(chǔ)節(jié)點(diǎn)，然后基站向傳感器網(wǎng)絡(luò)發(fā)布查詢命令〈qv,k,spid,〉給特定的存儲(chǔ)節(jié)點(diǎn)，其中查詢命令qv表示要查詢的數(shù)值，spid={sp_id,sp_num}表示將要查詢的存儲(chǔ)節(jié)點(diǎn)的集合，sp_num表示查詢?cè)谠摯貎?nèi)距離qv最近的sp_num個(gè)數(shù)據(jù)。由于本文的LVC算法考慮了位置信息，因此，兩個(gè)簇之間的測(cè)量范圍可能會(huì)產(chǎn)生重疊(如圖2所示)。

圖2 簇的測(cè)量范圍

若查詢數(shù)據(jù)只存在一個(gè)簇內(nèi)，即lbi≤qv≤hbi，則查詢存儲(chǔ)節(jié)點(diǎn)的數(shù)量為1，sp_num=z；若查詢數(shù)據(jù)存在于兩個(gè)簇內(nèi)或在兩個(gè)簇的測(cè)量范圍之間(hbi≤qv≤lbi+1)，則查詢存儲(chǔ)節(jié)點(diǎn)的數(shù)量為2，即sp_num1+sp_num2=z。當(dāng)查詢存儲(chǔ)節(jié)點(diǎn)的數(shù)量為2時(shí)，最直接的方式是將兩個(gè)簇內(nèi)的所有測(cè)量值都傳送給基站，然后由基站計(jì)算K近鄰，但當(dāng)簇內(nèi)節(jié)點(diǎn)較多或k較小時(shí)這將消耗較多的能量，本文提出基于數(shù)據(jù)離散度的近似KNN 數(shù)據(jù)查詢算法解決sp_numi數(shù)量分配問題。根據(jù)查詢數(shù)據(jù)在簇內(nèi)出現(xiàn)的概率估計(jì)出每個(gè)簇的查詢數(shù)量，降低傳輸數(shù)據(jù)的數(shù)量，從而降低網(wǎng)絡(luò)的能量消耗，該算法偽代碼如下：

初始化:sp_num1=0,sp_num2=0,pd1=1,pd2=1P1=12πvar1exp-(qv-mean1)2(2var1) P2=12πvar2exp-(qv-mean2)2(2var2) for i=1:qif ((pd1·P1)>(pd2·P2)) sp_num1=sp_num1+1 pd1=pd1·P1else sp_num2=sp_num2+1 pd2=pd2·P2endend

3 仿真與結(jié)果分析

在300m×300m區(qū)域內(nèi)，160個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署進(jìn)行仿真實(shí)驗(yàn)，傳感器節(jié)點(diǎn)的通信半徑為50m，路由協(xié)議采用GPSR[11]協(xié)議。

圖3給出LVC分簇后的結(jié)果，其中簇1和簇2的數(shù)據(jù)比較接近，但二者地理位置相距較遠(yuǎn)，由圖3可知，LVC算法可以將測(cè)量數(shù)值相近但地理位置相距較遠(yuǎn)的節(jié)點(diǎn)分類。

圖3 LVC算法效果

圖4給出三種算法在不同查詢率下平均傳包率的對(duì)比。查詢率：當(dāng)節(jié)點(diǎn)向存儲(chǔ)節(jié)點(diǎn)傳送一個(gè)數(shù)據(jù)包時(shí)，基站向存儲(chǔ)節(jié)點(diǎn)發(fā)送查詢指令的次數(shù)。平均傳包率=查詢一次傳送數(shù)據(jù)包的總個(gè)數(shù)/節(jié)點(diǎn)數(shù)量。

圖4 平均傳包率與查詢率的關(guān)系

由圖4可知，隨著查詢率的提高，本文提出的CAKNN算法與KVC算法均提高；由于Na?ve算法不受查詢率的影響，因此，平均傳包數(shù)不變；但CAKNN算法與KVC算法的平均傳包數(shù)始終小于Na?ve算法。當(dāng)查詢率小于0.7時(shí)，CAKNN算法優(yōu)于KVC算法，其中最大可提高30.36%；當(dāng)查詢率大于0.7時(shí)，KVC的算法略優(yōu)于CAKNN算法。平均傳包率越小，系統(tǒng)傳送數(shù)據(jù)包的數(shù)量越少，節(jié)點(diǎn)消耗能量越少，網(wǎng)絡(luò)生存時(shí)間也就越長(zhǎng)。由圖4可知本文提出的CAKNN算法具有更低的平均傳包率，因此網(wǎng)絡(luò)的生存時(shí)間更長(zhǎng)。

4 結(jié)論

提出基于位置-數(shù)據(jù)的分簇方法，該算法首先將測(cè)量數(shù)據(jù)值和地理位置接近的節(jié)點(diǎn)分為一簇，降低了網(wǎng)絡(luò)的能量消耗，然后利用數(shù)據(jù)的離散度確定查詢存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)的個(gè)數(shù)，解決了簇之間測(cè)量范圍重疊的問題。仿真結(jié)果表明：通過與Na?ve算法、KVC算法比較，本文提出的CAKNN算法具有較低的平均傳包率，節(jié)約了節(jié)點(diǎn)的能量，提高了網(wǎng)絡(luò)的生存時(shí)間。