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

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

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

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

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

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

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

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

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

1 指紋定位算法

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

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

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

1.1 KNN指紋定位算法

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

(1)

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

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

(2)

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

1.2 基于K-Means聚類(lèi)的KNN指紋定位算法

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

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

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

2 VAPFC定位算法

2.1 VAPFC算法的離線(xiàn)聚類(lèi)分析

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

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

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

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)建需要一個(gè)足夠大的初始三角形dt0,定位區(qū)域Dl×w屬于dt0,記初始DT0={dt0},dt0=((10 000,-10 000),(-10 000,-10 000),(0,10 000))。

②構(gòu)建DT

將N個(gè)AP逐個(gè)部署在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完成。

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

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

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

(3)

式中:dti表示DT中第i個(gè)三角形,Vij是dti的第j個(gè)頂點(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的相鄰三角形的個(gè)數(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個(gè)三角形,GC(sth)表示三角形sth的外接圓圓心。

⑤生成泰森多邊形

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

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

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

2.1.2 指紋信息錄入

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

2.1.3 指紋聚類(lèi)

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

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

(6)

2.2 VAPFC算法的在線(xiàn)定位分析

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

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

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

(7)

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

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

2.2.2 位置估計(jì)

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

圖2 VAPFC算法在線(xiàn)定位流程

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

①S1大于T

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

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

②存在Smaxi

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

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

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

圖3 40 m×40 m仿真場(chǎng)景圖

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

①定位精度和定位時(shí)間的比較分析

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

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

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

②聚類(lèi)中心對(duì)定位誤差的影響分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

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

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

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

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

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

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

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

[8] 唐文勝,李?yuàn)?匡旺秋. RF室內(nèi)定位指紋庫(kù)空間相關(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] 都伊林. 一種模糊聚類(lèi)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). 基于幾何聚類(lèi)指紋庫(kù)的約束KNN室內(nèi)定位模型[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2014,39(11):1287-1292.

[16] 陳國(guó)良,張言哲,汪云甲,等. WiFi-PDR室內(nèi)組合定位的無(wú)跡卡爾曼濾波算法[J]. 測(cè)繪學(xué)報(bào),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?；范讯鈧}(cāng)儲(chǔ)貨物定位技術(shù)[J]. 化工學(xué)報(bào),2016,67(3):878-884.

[19] 趙春江,吳華瑞,劉強(qiáng),等. 基于Voronoi的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J]. 通信學(xué)報(bào),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)目來(lái)源:國(guó)家自然科學(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ú)線(xiàn)傳感器網(wǎng)絡(luò);

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