黃 月

(沈陽理工大學 自動化與電氣工程學院，沈陽 110159)

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

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

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

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

本文基于以下假設：

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

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

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

圖1 查詢系統(tǒng)結構圖注：○傳感器節(jié)點；△存儲節(jié)點；□基站。

1.1 LVC算法

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

算法偽代碼如下所示：

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

1.2 存儲節(jié)點的選擇

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

(1)

sp∈Clusteri,NVi∈Clusteri,

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

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

2 查詢處理

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

圖2 簇的測量范圍

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

初始化: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 仿真與結果分析

在300m×300m區(qū)域內，160個傳感器節(jié)點隨機部署進行仿真實驗，傳感器節(jié)點的通信半徑為50m，路由協(xié)議采用GPSR[11]協(xié)議。

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

圖3 LVC算法效果

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

圖4 平均傳包率與查詢率的關系

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

4 結論

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