呂 娜,單志龍,張 凡,余劉勇

基于接入點(diǎn)的泰森多邊形指紋聚類定位算法*

呂 娜,單志龍*,張 凡,余劉勇

針對KNN指紋定位算法定位耗時長和基于K-Means聚類的KNN指紋定位算法定位精度不穩(wěn)定的問題,本文提出了一種以接入點(diǎn)為離散點(diǎn)生成泰森多邊形,利用泰森多邊形對指紋聚類,然后使用最強(qiáng)接入點(diǎn)法確定移動節(jié)點(diǎn)的定位區(qū)域,最后通過動態(tài)KNN算法進(jìn)行定位的指紋聚類定位算法。實(shí)驗(yàn)表明,該算法能有效縮短定位時間并提高定位精度,在接入點(diǎn)數(shù)量變化時表現(xiàn)出較好的定位性能,且在不同定位區(qū)域中性能具有較好的普適性。

指紋定位算法;接入點(diǎn);泰森多邊形;KNN;K-Means

移動通信業(yè)的迅速發(fā)展與移動終端的普遍使用使得基于位置服務(wù)LBS(Location Based Services)受到越來越多的關(guān)注,并被廣泛應(yīng)用于人們的生活中。雖然GPS技術(shù)發(fā)展成熟,可以為LBS解決許多室外定位問題,但其受衛(wèi)星信號無法穿透墻壁等因素的影響,在障礙物較多、環(huán)境復(fù)雜的室內(nèi)并不適用[1]。而人類超過80%的活動時間是在室內(nèi)度過,市場對室內(nèi)基于位置服務(wù)有很大需求,如特殊人群監(jiān)護(hù)、礦井人員定位、超市導(dǎo)購等[2-4]。

室內(nèi)定位方法主要有兩類[5]:一類是通過測量信號的到達(dá)時間TOA(Time of Arrival)、到達(dá)時間差TDOA(Time Difference of Arrival)或到達(dá)角度AOA(Angle of Arrival),運(yùn)用三邊測量法對移動節(jié)點(diǎn)進(jìn)行定位。該類方法定位精度較高,但需要額外硬件測量信號傳播的時間或方向,對室內(nèi)定位系統(tǒng)的成本和定位范圍提出了挑戰(zhàn)[6]。另一類方法是基于接收信號強(qiáng)度指示值RSSI(Received Signal Strength Indication)定位。通常地,基于RSSI的定位方法包括基于信號傳播模型定位算法和指紋定位算法[7]。信號傳播模型定位算法因信號在傳播過程中嚴(yán)重受到多徑效應(yīng)、信號衰減和延遲失真等因素的影響及模型中的參數(shù)值依賴建筑物的結(jié)構(gòu)和使用的材料而不能滿足人們對定位系統(tǒng)高精確度、低計(jì)算復(fù)雜度和快速響應(yīng)的要求;指紋定位算法自RADAR系統(tǒng)出現(xiàn)以來,已成為當(dāng)今室內(nèi)定位的主流算法[8]。

指紋定位算法包括離線訓(xùn)練和在線定位兩個階段[1]。在離線階段需完成構(gòu)建指紋庫的工作,通過對指紋聚類,可減少在線階段的指紋匹配量,大大降低計(jì)算復(fù)雜度,提高算法定位效率;在線階段則通過匹配算法如KNN、KWNN、SVM、深度學(xué)習(xí)[9-12]等將待定位點(diǎn)與指紋庫中的指紋進(jìn)行匹配,估計(jì)待定位點(diǎn)位置。該類算法的定位性能雖仍受環(huán)境因素影響,但思路簡單,且不受參數(shù)作用,通過對算法兩個階段的改進(jìn),可以有效提高定位精度和速度。

為減少定位時間,本文提出基于接入點(diǎn)的泰森多邊形指紋聚類定位算法VAPFC(Voronoi Based on Access Point Fingerprint Clustering)。該算法引入泰森多邊形,以接入點(diǎn)AP(Access Point)作為泰森多邊形的離散點(diǎn)來構(gòu)建單元格,從物理位置上用各單元格對指紋分類,然后找到待定位點(diǎn)所屬指紋子類,選取滿足誤差閾值條件的指紋對待定位點(diǎn)進(jìn)行定位。

1 指紋定位算法

指紋定位算法是一種基于場景的定位方法,分為離線訓(xùn)練和在線定位兩個階段。

在離線階段,通過在定位場景中部署N個發(fā)射無線信號的AP,按照一定間隔設(shè)置參考點(diǎn)并測量其信息,建立包括參考點(diǎn)坐標(biāo)(x,y)及其接收到的來自N個AP的RSSI值(RSSI1,RSSI2,…,RSSIN)的指紋庫。

在在線階段,通過測量待定位點(diǎn)的RSSI信息,以RSSI向量作為比較對象,運(yùn)用匹配算法將待定位點(diǎn)與指紋庫中的指紋進(jìn)行匹配,以相似性高的指紋坐標(biāo)作為待定位節(jié)點(diǎn)的位置。常用的匹配算法分為確定性匹配算法、概率性匹配算法及神經(jīng)網(wǎng)絡(luò)算法,其中確定性匹配算法中的KNN算法原理簡單,計(jì)算量相對較少。

1.1 KNN指紋定位算法

KNN指紋定位算法(K-Nearest Neighbor Algorithm)是將在待定位點(diǎn)處實(shí)時觀測的RSSI向量與指紋庫中所有指紋的RSSI向量進(jìn)行相似度測量,選取對比結(jié)果中前K個相似度高的指紋估計(jì)待定位點(diǎn)位置。相似度常以歐氏距離衡量:

(1)

式中:D(αi,β)表示指紋庫中第i個指紋αi的RSSI向量與待定位點(diǎn)β的RSSI向量的距離,距離越小,相似度越高。αij、βj分別表示αi、β接收到的來自第j個AP的RSSI值。

假設(shè)指紋庫中有M(M>K)個指紋。將D1,D2,…,DM升序排序形成新序列S(S1,S2,…,SM),則待定位點(diǎn)β的位置(xβ,yβ):

(2)

式中:xSi和ySi分別表示新序列S中第i個指紋的橫坐標(biāo)和縱坐標(biāo)。

1.2 基于K-Means聚類的KNN指紋定位算法

指紋量較大時,傳統(tǒng)的KNN指紋定位算法對移動點(diǎn)定位的響應(yīng)延時較長,因此很多學(xué)者提出通過對指紋聚類和減少指紋匹配量來提高定位效率[10,13-16]。K-Means就是其中一種常用的聚類方法[16],運(yùn)用K-Means對指紋庫聚類的過程如下:①隨機(jī)選取K個指紋作為初始聚類中心;②計(jì)算其余每個指紋到各聚類中心的距離,按最小距離原則將各指紋聚類到距它最近的中心;③計(jì)算每個類簇的均值,并將均值作為新的聚類中心;④重復(fù)步驟②和步驟③,直到所有指紋到其相應(yīng)聚類中心的距離之和J最小或迭代次數(shù)達(dá)到要求為止。

在線定位時,首先計(jì)算待定位點(diǎn)與各個聚類中心的距離,然后確定距離待定位點(diǎn)最近的聚類中心,最后選取該中心所屬類別中的指紋進(jìn)行KNN定位。

K-Means定位算法思想簡單,并彌補(bǔ)了傳統(tǒng)算法定位效率低的缺陷,但聚類數(shù)K值由經(jīng)驗(yàn)確定且初始聚類中心是隨機(jī)選取的,這種隨機(jī)性和不可靠性使得算法的運(yùn)行效率對初始聚類中心敏感,且定位精度過度依賴聚類初始條件。因此,如能利用固定的AP對指紋聚類,減少算法對初始聚類中心的敏感性,則有可能提高定位算法的性能。

2 VAPFC定位算法

2.1 VAPFC算法的離線聚類分析

1911年,荷蘭氣候?qū)W家Thiessen A H首次將泰森多邊形應(yīng)用于氣象學(xué),以離散分布的氣象站的降雨量衡量各氣象站所屬大區(qū)域的平均降雨量[17]。自此,泰森多邊形的以下特性在諸多領(lǐng)域得到了應(yīng)用[18-19]:①每個泰森多邊形內(nèi)部只有一個離散點(diǎn);②泰森多邊形內(nèi)的點(diǎn)到相應(yīng)離散點(diǎn)的距離最近;③位于泰森多邊形邊上的點(diǎn)到其兩邊的離散點(diǎn)距離相等;④離散點(diǎn)的特征代表了其對應(yīng)泰森多邊形內(nèi)部點(diǎn)的整體趨勢。

為提高定位速度,基于泰森多邊形特性,以AP作為離散點(diǎn),運(yùn)用泰森多邊形生成算法將定位場景劃分為與各AP相對應(yīng)的N個子區(qū)域,即V1,V2,…,VN,將M個指紋按照物理位置聚類到各子區(qū)域中。

VAPFC定位算法實(shí)現(xiàn)指紋聚類的過程如下:

2.1.1 區(qū)域分割

借助泰森多邊形與德洛內(nèi)三角網(wǎng)DT(Delaunay Triangulation)的關(guān)系可實(shí)現(xiàn)泰森多邊形生成算法,即:泰森多邊形的頂點(diǎn)是DT中各相應(yīng)三角形的外接圓圓心,而DT中三角形的頂點(diǎn)是泰森多邊形的離散點(diǎn),其具體步驟如下:

①初始化DT

DT的構(gòu)建需要一個足夠大的初始三角形dt0,定位區(qū)域Dl×w屬于dt0,記初始DT0={dt0},dt0=((10 000,-10 000),(-10 000,-10 000),(0,10 000))。

②構(gòu)建DT

將N個AP逐個部署在Dl×w中。部署APi后,首先找到包含APi的三角形Ti,利用APi和Ti獲取三角形集合TSi,APi位于TSi中所有三角形的外接圓內(nèi);其次將Ti與TSi中的三角形進(jìn)行合并得到多邊形Ci;最后將APi與Ci的所有頂點(diǎn)相連即可得到DTi。DTN生成后,構(gòu)建DT完成。

③確定每個離散點(diǎn)的相鄰三角形

三角形t1,t2,…,tk的共同頂點(diǎn)為V,則稱這k個三角形是點(diǎn)V的相鄰三角形。

dti∈DT,Vij∈dti若Vij?G,則U(Vij,G)

(3)

式中:dti表示DT中第i個三角形,Vij是dti的第j個頂點(diǎn),G是離散點(diǎn)標(biāo)記集合,其初始值G0={(10 000,-10 000),(-10 000,-10 000),(0,10 000)}。若Vij不在G中,則將Vij加入G,記為U(Vij,G)。

ST(Vij,dti)={st0,st1,st2,…,stk-1}

(4)

式中:ST(Vij,dti)表示離散點(diǎn)Vij的所有相鄰三角形的集合,dti是該集合的初始元素,記為st0,k表示Vij的相鄰三角形的個數(shù)。

④計(jì)算離散點(diǎn)的相鄰三角形的外接圓圓心

GCVij={GC(st1),…,GC(sth),…,GC(stk)},
sth∈ST(Vij,dti)

(5)

式中:GCVij表示離散點(diǎn)Vij的所有相鄰三角形的外接圓圓心的集合,sth是集合ST(Vij,dti)中的第h個三角形,GC(sth)表示三角形sth的外接圓圓心。

⑤生成泰森多邊形

將式(5)中GCVij集合里的所有點(diǎn)相連即得離散點(diǎn)Vij對應(yīng)的泰森多邊形。將N個AP對應(yīng)的泰森多邊形集合記為VS={VS1,VS2,…,VSN}。

根據(jù)上述步驟,可以實(shí)現(xiàn)區(qū)域的泰森多邊形分割,如圖1所示,分別以V1、V2、V3和V4為離散點(diǎn)的4個泰森多邊形將整個平面進(jìn)行了無重疊地分割。這4個離散點(diǎn)是DT中的兩個三角形V1V2V3和V1V3V4的頂點(diǎn),而兩個三角形的外接圓圓心A和B是泰森多邊形的頂點(diǎn)。

圖1 泰森多邊形與DT網(wǎng)的關(guān)系展示圖

2.1.2 指紋信息錄入

將M個指紋的信息fp1((x1,y1),(RSSI11,RSSI12,…,RSSI1N)),…,fpM((xM,yM),(RSSIM1,RSSIM2,…,RSSIMN))錄入定位系統(tǒng)中。

2.1.3 指紋聚類

定位區(qū)域分割后,把每個泰森多邊形單元格作為一個類區(qū)域,位于該類區(qū)域中的指紋屬于同一類簇。如果指紋庫中第i個指紋fpi的物理位置位于第j個AP對應(yīng)的泰森多邊形VSj內(nèi)部,則將fpi聚類到VSj中,記為Cluster(fpi,VSj),即:

若In(fpi,VSj),則Cluster(fpi,VSj)

(6)

2.2 VAPFC算法的在線定位分析

在線定位時,首先通過確定待定位點(diǎn)RSSI向量中的最大值找到其所屬定位子區(qū)域,然后運(yùn)用動態(tài)KNN匹配算法估計(jì)待定位節(jié)點(diǎn)的位置。

2.2.1 定位子區(qū)域的獲取

目標(biāo)點(diǎn)接收到的信號強(qiáng)度值與無線信號收發(fā)雙方的距離成一定的對數(shù)關(guān)系[20],表示為傳播路徑損耗模型:

(7)

式中:P(d)表示目標(biāo)點(diǎn)與信號發(fā)射端的距離為d時接收到的信號強(qiáng)度,P(d0)表示距離為d0時接收到的信號強(qiáng)度,n是與定位環(huán)境相關(guān)的路徑損耗指數(shù),XdBm服從N(μ,σ2)分布。

由式(7)可知,待定位點(diǎn)處接收到的信號強(qiáng)度P(d)越大,則待定位點(diǎn)距離信號發(fā)射端越近。記待定位點(diǎn)為U,其RSSI向量中的最大值為RSSIj,則距離U最近的接入點(diǎn)為APj。因泰森多邊形特性(2),故U的定位子區(qū)域是以APj為離散點(diǎn)的泰森多邊形VSj。

2.2.2 位置估計(jì)

假設(shè)VSj中包含L個指紋,使用KNN指紋定位算法計(jì)算U的坐標(biāo),即首先利用式(1)計(jì)算出U與L個指紋的距離序列D(D1,D2,…,DL)的值,然后將D升序排序得到新序列S(S1,S2,…,SL)及S對應(yīng)的指紋序列fp(fp1,fp2,…,fpL),最后將fp中前K個指紋作為參考點(diǎn),使用式(2)估計(jì)U的位置。但KNN算法中K值固定,對于變動的待定位點(diǎn)而言,參與計(jì)算的指紋量可能過多或過少,這兩種情況都會導(dǎo)致定位精度下降。Beomju等[21]也提出運(yùn)用KNN算法定位的精度與K值的選定相關(guān)。為得到更高的定位精度,故在線定位過程中采用設(shè)定誤差門限值T的方法動態(tài)選取K,具體的在線定位流程如圖2所示。

圖2 VAPFC算法在線定位流程

合適的T值對獲得較準(zhǔn)確的位置估計(jì)至關(guān)重要,故當(dāng)以下兩種情況出現(xiàn)時應(yīng)對T值及時進(jìn)行調(diào)整:

①S1大于T

S1為VSj中所有的指紋與U的距離中的最小值。S1大于T,表明VSj中不存在滿足閾值條件的指紋,故將與U相似度最高的fp1加入指紋選擇集以估計(jì)待定位點(diǎn)的位置。若經(jīng)過對多個移動點(diǎn)定位后發(fā)現(xiàn),在S中均找不到小于T的值,說明T的設(shè)定值過小,此時應(yīng)以當(dāng)前T值為準(zhǔn)線T0,以ΔT為正增量,對T值進(jìn)行上浮調(diào)整,記為Ti(i=1,2,…),直到存在Si小于T,且找到使算法的平均定位誤差達(dá)到最小的T值為止。本文中以2為T0,ΔT取0.5,確定T取值區(qū)間為[3.5,4.0],再以3.5為T0,0.1為ΔT,確定T的取值為3.7,如表1所示。

表1 T值對動態(tài)KNN算法的平均定位誤差的影響

②存在Smaxi

Smaxi表示S中小于T的最大值,將S1,S2,…,Si對應(yīng)的指紋均加入指紋選擇集中。為避免T值過大導(dǎo)致定位誤差增加,應(yīng)對當(dāng)前T值下的定位誤差進(jìn)行考量。若定位誤差較大,則極有可能是由T取值偏大從而使得相似度較低的參考點(diǎn)進(jìn)入指紋選擇集造成的,故應(yīng)對T值進(jìn)行下降調(diào)整并同時觀測定位誤差的變化,該過程與①中T值修正過程正相反。

3 仿真實(shí)驗(yàn)及結(jié)果分析

算法的仿真實(shí)驗(yàn)在MyEclipse平臺下進(jìn)行,仿真結(jié)果圖由MATLAB軟件繪制,仿真場景為:40 m×40 m的正方形區(qū)域,區(qū)域內(nèi)均勻部署4個AP,除去4個頂點(diǎn)每5 m布置一個指紋,品紅色三角形代表AP,黑色點(diǎn)代表指紋,如圖3所示。

圖3 40 m×40 m仿真場景圖

在該場景下,首先對傳統(tǒng)的KNN指紋定位算法、基于K-Means聚類的KNN指紋定位算法和VAPFC算法的定位精度和定位時間進(jìn)行了比較,然后分析了聚類中心、AP數(shù)目和定位區(qū)域等的變化對定位誤差和定位耗時的影響。

①定位精度和定位時間的比較分析

對3種定位算法各進(jìn)行5次仿真,每次仿真設(shè)置10 000個待定位點(diǎn),將5次仿真結(jié)果求均值得3種算法的定位誤差與定位時間,如表2所示。

表2 3種算法的定位誤差與時間比較

由于K-Means定位算法與VAPFC定位算法在定位時均縮小了參考點(diǎn)的匹配范圍,故與傳統(tǒng)定位算法相比,K-Means定位算法的定位速度大幅提高,但定位精度下降較大;VAPFC定位算法在定位精度上雖比傳統(tǒng)定位算法降低約15%,但其縮短了約89%的定位時間,符合“在保證一定定位精度的前提下,提高定位時效性”的研究意圖;此外,VAPFC定位算法在定位時間上與K-Means定位算法持平,但K-Means定位算法受聚類中心隨機(jī)性的影響,其定位精度遠(yuǎn)低于VAPFC定位算法。

②聚類中心對定位誤差的影響分析

為探究聚類中心對3種算法定位誤差的影響,在實(shí)驗(yàn)①的仿真場景中進(jìn)行10次仿真,仿真結(jié)果如圖4所示。在所有仿真參數(shù)都不變的情況下,傳統(tǒng)算法因無聚類過程且直接從所有指紋中選擇K個最佳指紋進(jìn)行定位,故其定位精度比其他兩種算法高,定位誤差穩(wěn)定;K-Means定位算法受其隨機(jī)生成的初始聚類中心影響,定位結(jié)果波動較大;VAPFC算法以固定的AP為中心對指紋進(jìn)行聚類,定位結(jié)果波動不大,具有較好的穩(wěn)定性。

圖4 3種定位算法在10次仿真中的定位誤差(m)

圖5 3種定位算法在不同AP數(shù)目下的定位誤差(m)

③AP數(shù)目影響分析

當(dāng)定位場景中的AP數(shù)目發(fā)生改變時,需要重新部署AP,假定指紋位置不變但其RSSI向量值隨AP變化,則算法的定位性能也會隨著變化。

圖5顯示,AP數(shù)量增加,傳統(tǒng)定位算法與VAPFC算法的定位誤差差距較穩(wěn)定,但K-Means定位算法與其他兩種定位算法的誤差差距逐漸縮小,說明K-Means定位算法的定位精度受AP數(shù)目影響較大,這與K-Means算法的聚類效果對其聚類數(shù)K敏感有關(guān);在AP數(shù)目相同時,VAPFC算法的定位誤差始終小于K-Means定位算法,說明該算法相對于K-Means定位算法可得到更高定位精度。

圖6顯示,隨著AP數(shù)量的增加,傳統(tǒng)定位算法因每個指紋信息量增加且在線時沒有減少指紋匹配量,定位耗時逐漸增加;VAPFC定位算法的定位耗時逐步減少至平穩(wěn)狀態(tài);K-Means定位算法的定位耗時受匹配聚類中心時間與匹配選定類別中指紋時間的關(guān)系影響。當(dāng)AP數(shù)量小于10時,匹配指紋時間比匹配聚類中心時間對K-Means定位算法的定位耗時影響更大,算法的整體定位時間逐步減少;當(dāng)AP數(shù)量大于10時,情況正相反。

圖6 3種定位算法在不同AP數(shù)目下的定位時間(s)

通過對圖5、圖6的分析可知,AP數(shù)量對3種定位算法的定位誤差及時間均有影響,尤其對傳統(tǒng)算法的定位時間和K-Means定位算法的定位誤差影響最大;VAPFC定位算法在定位精度上比傳統(tǒng)定位算法降低約15%,但定位速度遠(yuǎn)高于后者;在AP數(shù)目較小時,VAPFC定位算法的定位耗時與K-Means定位算法持平,定位精度遠(yuǎn)高于后者;在AP數(shù)目較大時,VAPFC定位算法的定位精度與K-Means定位算法持平,定位速度遠(yuǎn)高于后者?？傮w而言,無論AP數(shù)目大小,VAPFC算法在定位精度和定位速度上均有優(yōu)勢。

④定位區(qū)域影響分析

為驗(yàn)證VAPFC算法是否具有普適性,我們對100 m×100 m,200 m×200 m和400 m×400 m的定位區(qū)域進(jìn)行了仿真。從仿真結(jié)果圖7～圖9可知,在不同的定位區(qū)域中,當(dāng)AP數(shù)目增加時,3種算法的定位誤差和定位時間的總體變化趨勢均與將3種算法在40 m×40 m定位區(qū)域中仿真得到的結(jié)果規(guī)律基本一致,故VAPFC算法具有較好的普適性。

圖7 100 m×100 m定位區(qū)域中3種定位算法在不同AP數(shù)目下的定位誤差(左)和定位時間(右)

圖8 200 m×200 m定位區(qū)域中3種定位算法在不同AP數(shù)目下的定位誤差(左)和定位時間(右)

圖9 400 m×400 m定位區(qū)域中3種定位算法在不同AP數(shù)目下的定位誤差(左)和定位時間(右)

4 總結(jié)

本文提出了一種估計(jì)室內(nèi)移動點(diǎn)位置的指紋定位算法,該算法運(yùn)用泰森多邊形的特性,通過以AP點(diǎn)為離散點(diǎn)、利用各AP對應(yīng)的泰森多邊形對指紋庫聚類、運(yùn)用最強(qiáng)AP法將待測點(diǎn)位置鎖定到某一子區(qū)域、采用動態(tài)KNN算法對待測點(diǎn)位置進(jìn)行估計(jì)。仿真結(jié)果表明,所提算法VAPFC在有效縮短定位時間的同時保證了定位精度,定位結(jié)果具有較好的穩(wěn)定性和區(qū)域普適性。

[1] 李燕君,徐凱鋒,邵劍集. 利用眾包更新Wi-Fi室內(nèi)定位指紋庫的方法研究[J]. 傳感技術(shù)學(xué)報,2014,27(12):1692-1698.

[2] 鄧中亮,余彥培,袁協(xié),等. 室內(nèi)定位現(xiàn)狀與發(fā)展趨勢研究(英文)[J]. China Communications,2013,10(3):50-63.

[3] 李論,丁恩杰,郝麗娜,等. 一種改進(jìn)的煤礦井下指紋定位匹配算法[J]. 傳感技術(shù)學(xué)報,2014,27(3):388-393.

[4] 陳斌濤,劉任任,陳益強(qiáng),等. 動態(tài)環(huán)境中的WiFi指紋自適應(yīng)室內(nèi)定位方法[J]. 傳感技術(shù)學(xué)報,2015,28(5):729-738.

[5] 郭紅成,羅海勇,尹浩,等. 基于線性插值和動態(tài)指紋補(bǔ)償?shù)姆植际蕉ㄎ凰惴╗J]. 傳感技術(shù)學(xué)報,2009,22(12):1795-1801.

[6] 孫利民,李建中,陳渝. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社,2005:141-146.

[7] 劉曉葉,徐玉斌. 基于自適應(yīng)射頻指紋地圖的WSN室內(nèi)定位算法研究[J]. 傳感技術(shù)學(xué)報,2015,28(8):1215-1220.

[8] 唐文勝,李姍,匡旺秋. RF室內(nèi)定位指紋庫空間相關(guān)生成算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2008,44(23):226-229.

[9] Zhao Y,Liu K,Ma Y,et al. An Improved KNN Algorithm for Localization in Multipath Environments[J]. EURASIP Journal on Wireless Communications and Networking,2014,2014(1):208.

[10] Chen W,Chang Q,Hou H T,et al. A Novel Clustering and KWNN-Based Strategy for Wi-Fi Fingerprint Indoor Localization[C]//International Conference on Computer Science and Network Technology. 2015:49-52.

[11] Wu T F,Lin C J,Weng R C. Probability Estimates for Multi-Class Classification by Pairwise Coupling[J]. Journal of Machine Learning Research,2004,5(4):975-1005.

[12] Wang X,Gao L,Mao S,et al. CSI-Based Fingerprinting for Indoor Localization:A Deep Learning Approach[J]. IEEE Transactions on Vehicular Technology,2017,66(1):763-776.

[13] 都伊林. 一種模糊聚類KNN位置指紋定位算法[J]. 微型機(jī)與應(yīng)用,2012,31(23):55-58.

[14] He C,Guo S,Wu Y,et al. A Novel Radio Map Construction Method to Reduce Collection Effort for Indoor Localization[J]. Measurement,2016,94:423-431.

[15] 劉春燕,王堅(jiān). 基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版),2014,39(11):1287-1292.

[16] 陳國良,張言哲,汪云甲,等. WiFi-PDR室內(nèi)組合定位的無跡卡爾曼濾波算法[J]. 測繪學(xué)報,2015,44(12):1314-1321.

[17] Thiessen A H. Precipitation Averages for Large Areas[J]. Monthly Weather Review,1911,39(7):1082-1084.

[18] 戴波,李志超,劉學(xué)君,等. 基于泰森多邊形的UWB?；范讯鈧}儲貨物定位技術(shù)[J]. 化工學(xué)報,2016,67(3):878-884.

[19] 趙春江,吳華瑞,劉強(qiáng),等. 基于Voronoi的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J]. 通信學(xué)報,2013(9):115-122.

[20] Noh S I,Lee W J,Ye J Y. Comparison of the Mechanisms of the ZigBee’s Indoor Localization Algorithm[C]//Ninth Acis International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing. IEEE Computer Society,2008:13-18.

[21] Shin B,Lee J H,Lee T,et al. Enhanced WeightedK-nearest Neighbor Algorithm for Indoor Wi-Fi Positioning Systems[C]//International Conference on Computing Technology and Information Management. 2012,2(2):574-577.

VoronoiBasedonAccessPointFingerprintClusteringLocalizationAlgorithm*

LüNa,SHANZhilong*,ZHANGFan,YULiuyong

(Schoolof Computer Science,South China Normal University,Guangzhou 510631,China)

To solve the problems of long position time-consuming in KNN fingerprint localization algorithm and unstable accuracy inK-Means clustering based localization algorithm,a novel fingerprint clustering localization algorithm is proposed. This algorithm considers APs as Voronoi diagram’s generators to create Voronoi cells,uses these cells to cluster fingerprints of database and a method based on the biggest

signal strength to find out the positioning subarea of mobile nodes,and estimates the location of mobile node by automatic KNN algorithm. Experiment results reveal that this algorithm sharply reduces position time-consuming,improves the accuracy,and has a good performance when the quantity of AP changes. With the location area altering the performance still exists.

fingerprint localization algorithm;AP;Voronoi diagram;KNN;K-Means

10.3969/j.issn.1004-1699.2017.12.026

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61671213,61370003);廣東省自然科學(xué)基金項(xiàng)目(2015A030313395);廣東省科技計(jì)劃項(xiàng)目(2013B040401014)

2017-05-04修改日期2017-07-18

(華南師范大學(xué)計(jì)算機(jī)學(xué)院,廣州 510631)

TP393

A

1004-1699(2017)12-1941-07

呂娜(1993-),女,碩士研究生,主要研究方向?yàn)槲锫?lián)網(wǎng)、無線傳感器網(wǎng)絡(luò);

單志龍(1976-),男,教授,博士,博士生導(dǎo)師,主要研究方向?yàn)槲锫?lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)、移動互聯(lián)網(wǎng)、計(jì)算機(jī)與通信網(wǎng)等,zhilongshan@gmail.com。