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

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

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

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

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

指紋定位算法;接入點;泰森多邊形;KNN;K-Means

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

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

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

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

1 指紋定位算法

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

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

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

1.1 KNN指紋定位算法

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

(1)

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

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

(2)

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

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

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

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

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

2 VAPFC定位算法

2.1 VAPFC算法的離線聚類分析

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

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

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

2.1.1 區(qū)域分割

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

①初始化DT

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

②構建DT

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

③確定每個離散點的相鄰三角形

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

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

(3)

式中:dti表示DT中第i個三角形,Vij是dti的第j個頂點,G是離散點標記集合,其初始值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)表示離散點Vij的所有相鄰三角形的集合,dti是該集合的初始元素,記為st0,k表示Vij的相鄰三角形的個數(shù)。

④計算離散點的相鄰三角形的外接圓圓心

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

(5)

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

⑤生成泰森多邊形

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

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

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

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對應的泰森多邊形VSj內(nèi)部,則將fpi聚類到VSj中,記為Cluster(fpi,VSj),即:

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

(6)

2.2 VAPFC算法的在線定位分析

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

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

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

(7)

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

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

2.2.2 位置估計

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

圖2 VAPFC算法在線定位流程

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

①S1大于T

S1為VSj中所有的指紋與U的距離中的最小值。S1大于T,表明VSj中不存在滿足閾值條件的指紋,故將與U相似度最高的fp1加入指紋選擇集以估計待定位點的位置。若經(jīng)過對多個移動點定位后發(fā)現(xiàn),在S中均找不到小于T的值,說明T的設定值過小,此時應以當前T值為準線T0,以ΔT為正增量,對T值進行上浮調(diào)整,記為Ti(i=1,2,…),直到存在Si小于T,且找到使算法的平均定位誤差達到最小的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對應的指紋均加入指紋選擇集中。為避免T值過大導致定位誤差增加,應對當前T值下的定位誤差進行考量。若定位誤差較大,則極有可能是由T取值偏大從而使得相似度較低的參考點進入指紋選擇集造成的,故應對T值進行下降調(diào)整并同時觀測定位誤差的變化,該過程與①中T值修正過程正相反。

3 仿真實驗及結果分析

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

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

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

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

對3種定位算法各進行5次仿真,每次仿真設置10 000個待定位點,將5次仿真結果求均值得3種算法的定位誤差與定位時間,如表2所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

為驗證VAPFC算法是否具有普適性,我們對100 m×100 m,200 m×200 m和400 m×400 m的定位區(qū)域進行了仿真。從仿真結果圖7～圖9可知,在不同的定位區(qū)域中,當AP數(shù)目增加時,3種算法的定位誤差和定位時間的總體變化趨勢均與將3種算法在40 m×40 m定位區(qū)域中仿真得到的結果規(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 總結

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

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

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

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

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

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

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

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

[8] 唐文勝,李姍,匡旺秋. RF室內(nèi)定位指紋庫空間相關生成算法[J]. 計算機工程與應用,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]. 微型機與應用,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] 劉春燕,王堅. 基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J]. 武漢大學學報(信息科學版),2014,39(11):1287-1292.

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

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

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

[19] 趙春江,吳華瑞,劉強,等. 基于Voronoi的無線傳感器網(wǎng)絡覆蓋控制優(yōu)化策略[J]. 通信學報,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

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

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

(華南師范大學計算機學院,廣州 510631)

TP393

A

1004-1699(2017)12-1941-07

呂娜(1993-),女,碩士研究生,主要研究方向為物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡;

單志龍(1976-),男,教授,博士,博士生導師,主要研究方向為物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡、移動互聯(lián)網(wǎng)、計算機與通信網(wǎng)等,zhilongshan@gmail.com。