0 引言

    位置指紋定位^[1]是目前室內(nèi)定位中應(yīng)用較多的定位方式，其在線定位階段中檢測(cè)值與數(shù)據(jù)庫(kù)快速匹配決定了定位效率，而聚類(lèi)算法^[2]能降低大量數(shù)據(jù)的維度，減少匹配計(jì)算量，故使用較多。

    文獻(xiàn)[3]采用K-means聚類(lèi)的方法對(duì)KNN方法進(jìn)行改進(jìn)，該方法利用K-means聚類(lèi)對(duì)初始點(diǎn)鄰域進(jìn)行篩選，用算法減小了奇異點(diǎn)對(duì)于計(jì)算的影響，但是其定位效率不高。文獻(xiàn)[4]提出應(yīng)用K-means聚類(lèi)的方法對(duì)指紋空間進(jìn)行聚類(lèi)，將整個(gè)解空間分為若干子空間。該方法降低了匹配工作的計(jì)算量，但不能保證聚類(lèi)算法得到最優(yōu)解。而且以上兩種K-means聚類(lèi)算法都是被動(dòng)依托于環(huán)境中AP的條件，存在聚類(lèi)結(jié)果受初始值的影響較大和極易陷入局部最值的問(wèn)題。待測(cè)環(huán)境中AP數(shù)量多，即可用算法去篩選最優(yōu)點(diǎn)，濾除極差點(diǎn)；若環(huán)境中AP數(shù)量較少，以上方法則差強(qiáng)人意。

    試驗(yàn)中發(fā)現(xiàn)AP位置布局變化會(huì)對(duì)定位精度產(chǎn)生較大影響，而關(guān)于這方面的研究極少。本文提出一種AP主動(dòng)布局優(yōu)化方法，在不增加AP數(shù)量條件下由改進(jìn)的K-means聚類(lèi)算法提高定位系統(tǒng)整體性能和定位精度。

1 室內(nèi)定位AP部署優(yōu)化模型

1.1 部署優(yōu)化的目標(biāo)函數(shù)

    空間中無(wú)線電傳播損耗^[5]模型一般用下式表示：

其中，s、t為定位空間的邊界長(zhǎng)度。

1.2 計(jì)算步驟

    單純形法(Simplex Method，SM)^[6]進(jìn)行尋優(yōu)計(jì)算的理論較為完善，但在室內(nèi)指紋定位研究中涉及文獻(xiàn)較少。在傳統(tǒng)單純形法迭代計(jì)算過(guò)程中，對(duì)初始三角形進(jìn)行拉伸、收縮、對(duì)稱(chēng)等計(jì)算操作，剔除模型中殘差最大的頂點(diǎn)，補(bǔ)充一個(gè)新的頂點(diǎn)構(gòu)建新的三角形，不斷重復(fù)這個(gè)尋找過(guò)程，當(dāng)目標(biāo)函數(shù)值滿足約束條件時(shí)，對(duì)通過(guò)迭代計(jì)算得到的三角形選取殘差最小的點(diǎn)即最佳逼近解。

    模擬退火（Simulated Annealing，SA）^[7]算法是一種模擬物理降溫過(guò)程的優(yōu)化算法，其核心思想是：較高初溫時(shí)粒子能量較高，漸進(jìn)冷卻時(shí)粒子漸趨有序，最后在常溫時(shí)粒子達(dá)到最終穩(wěn)定狀態(tài)。模擬退火算法主要由解空間、目標(biāo)函數(shù)和初始解3部分組成。

    模擬退火算法對(duì)于全局控制穩(wěn)定但收斂慢，單純形法計(jì)算速度快，但極易局部最優(yōu)，兩者優(yōu)勢(shì)互補(bǔ)。單純形-模擬退火（SMSA）融合算法的思路是先利用單純形算法搜索到局部最小值，然后利用模擬退火算法的突跳性使它能跳出局部極小值，搜索是否有單純形新的局部最小極值，若有以該點(diǎn)替代初值繼續(xù)搜索，伴隨退溫操作通過(guò)循環(huán)而趨近于全局最優(yōu)解。計(jì)算步驟如下：

2 改進(jìn)K-means聚類(lèi)算法

    傳統(tǒng)K-means聚類(lèi)算法^[8]隨機(jī)產(chǎn)生K個(gè)子類(lèi)的中心，根據(jù)與各子類(lèi)中心的距離將剩余的每個(gè)對(duì)象劃分到距離最短的子類(lèi)中，然后重新計(jì)算每個(gè)子類(lèi)中所有對(duì)象的平均值并將其作為新的聚類(lèi)中心，不斷重復(fù)操作，直到誤差平方和函數(shù)收斂為止。傳統(tǒng)方法缺點(diǎn)是計(jì)算量大、效率低，有可能得到局部最優(yōu)解，原因在于初始聚類(lèi)中心的選擇，當(dāng)聚類(lèi)中心接近空間數(shù)據(jù)分布稠密區(qū)間點(diǎn)時(shí)，定位效率高、運(yùn)算時(shí)間短，但空間數(shù)據(jù)分布稀疏時(shí)效果差。

    研究中對(duì)于聚類(lèi)算法的初始聚類(lèi)中心加以改進(jìn)設(shè)置，不是隨機(jī)選取，而以部署優(yōu)化后的AP為初始中心，以測(cè)試點(diǎn)到AP的歐式距離作為目標(biāo)函數(shù)來(lái)聚類(lèi)，聚類(lèi)過(guò)程中舍棄奇異點(diǎn)。優(yōu)化部署AP時(shí)的目標(biāo)函數(shù)本質(zhì)是距離誤差達(dá)到最小，因此選取離AP最近坐標(biāo)對(duì)應(yīng)的RSS信號(hào)特征向量對(duì)數(shù)據(jù)庫(kù)進(jìn)行聚類(lèi)效率最高。

    改進(jìn)K-means 聚類(lèi)算法步驟如下：

    (1)Offline采集階段

    Input：信號(hào)采樣數(shù)據(jù)集X={X₁，X₂，…，X_n}

    Output：s個(gè)類(lèi)C_n(1≤s≤n) 

    ①初始化程序中的聚類(lèi)參數(shù)，規(guī)劃聚類(lèi)數(shù)k(2<k<q<n)，隨機(jī)偶選樣本點(diǎn)并設(shè)置為初始運(yùn)算類(lèi)中心h₁，h₂，…，h_k，設(shè)置迭代門(mén)限條件為均方差最小或者迭代次數(shù)達(dá)到閾值。

    ②計(jì)算X_p(p=1，2，…，n)與各初始類(lèi)中心坐標(biāo)的歐式距離dij，求均值降序排序，并將每個(gè)排序點(diǎn)分配到最近鄰的類(lèi)中心的子類(lèi)中。

    ③計(jì)算子類(lèi)中所有參考點(diǎn)之間歐式距離和，選取最小值對(duì)應(yīng)的點(diǎn)作為新的聚類(lèi)中心。

    ④迭代停止條件判斷：若不滿足最小平均方差或者未達(dá)迭代門(mén)限條件，返回執(zhí)行步驟②，用新聚類(lèi)中心重新聚類(lèi)；否則，終止程序。

    (2)Online定位階段

    Input：目標(biāo)信號(hào)采樣樣本點(diǎn)數(shù)據(jù)X_rssi

    Output：比對(duì)輸出位置坐標(biāo)值

    ①計(jì)算定位目標(biāo)X_rssi與各聚類(lèi)中心的歐式距離d_rssi，則區(qū)分目標(biāo)點(diǎn)所屬子類(lèi)。

    ②計(jì)算X_rssi與類(lèi)目中心的歐式距離，用KNN法匹配出目標(biāo)點(diǎn)的位置坐標(biāo)值并輸出運(yùn)算結(jié)果。

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

3.1 實(shí)驗(yàn)平臺(tái)

    由美國(guó)Signal Hound公司的SA44B型頻譜儀測(cè)量接收機(jī)和Intel公司的Minnow Board Turbott嵌入式微系統(tǒng)組成信號(hào)采集處理模塊，其中USB端口連接Tenda的W311MA型無(wú)線網(wǎng)卡，與其他采集模塊AP節(jié)點(diǎn)一起組成無(wú)線傳感器網(wǎng)絡(luò)。經(jīng)由JCG的JHR-N926R型無(wú)線路由器將采集到的數(shù)據(jù)發(fā)送至聯(lián)想ThinkPad E440筆記本電腦服務(wù)器上。

    為驗(yàn)證AP位置優(yōu)化算法的有效性，實(shí)驗(yàn)在實(shí)驗(yàn)樓10 m×13 m的空曠教室中進(jìn)行，如圖1所示，以0.8 m間距設(shè)置參考坐標(biāo)點(diǎn)間距（這是地磚的尺寸，以便測(cè)量），位置點(diǎn)依次設(shè)置為A、B、C、D，文獻(xiàn)[9]驗(yàn)證了較小定位空間內(nèi)選用4個(gè)AP時(shí)性價(jià)比最高，故選用4個(gè)AP，各AP初始坐標(biāo)為A(2.0，2.0)，B(2.0，8.0)，C(6.6，8.0)，D(6.6，2.0)，并組成矩形陣列。

    信號(hào)源采用USPRB200型發(fā)生器，其中心頻率可設(shè)置為70 MHz～6 GHz。發(fā)射源頻率調(diào)制為840 MHz來(lái)模擬手機(jī)干擾源頻率，信號(hào)功率為15 dB，信號(hào)源的萬(wàn)向天線與支架的中心軸線重合，支架平面距地面0.5 m，較低的信號(hào)源高度可以減少地面的反射波的測(cè)量擾動(dòng)，以每間隔1 m選取參考坐標(biāo)進(jìn)行指紋信息數(shù)據(jù)采集，支架中心軸對(duì)準(zhǔn)參考點(diǎn)標(biāo)記，采集時(shí)間為15 s，采集期間人員手機(jī)關(guān)閉以凈化電波環(huán)境，降低外界干擾。離線階段共采集參考位置40個(gè)，每個(gè)指紋位置采集3次，其中排除靠近建筑拐角和堆積雜物的區(qū)域，以及與AP太近和重合的參考位置。

3.2 實(shí)驗(yàn)及誤差分析

    對(duì)定位環(huán)境中的指紋點(diǎn)和參考點(diǎn)依次進(jìn)行數(shù)據(jù)采集，并將初始坐標(biāo)進(jìn)行單純形法位置優(yōu)化，優(yōu)化后的位置坐標(biāo)為A1(3.8，0.4)，B1(11.3，1.9)，C1(1.9，9.6)，D1(7.8，12.3)，將接收機(jī)放置于優(yōu)化后的新坐標(biāo)點(diǎn)上，如圖2所示，采用K-means聚類(lèi)算法進(jìn)行定位。根據(jù)文獻(xiàn)[10]的驗(yàn)證結(jié)論，當(dāng)K=3時(shí)對(duì)目標(biāo)的定位精度相對(duì)最高，因此本文定位算法的參數(shù)K設(shè)置為3。

    從圖3可知，應(yīng)用SMSA算法優(yōu)化后的測(cè)試點(diǎn)平均定位誤差均略有下降，當(dāng)進(jìn)行AP位置優(yōu)化后定位精度也明顯提高了很多，K-means平均定位誤差為1.5 m時(shí)的概率達(dá)到68%，比優(yōu)化前提高了13.8%。同時(shí)經(jīng)過(guò)SMSA算法優(yōu)化后的K-means聚類(lèi)算法的運(yùn)算效率明顯提升，如圖4所示，由于以布局優(yōu)化后AP坐標(biāo)作為初始聚類(lèi)中心，初始聚類(lèi)運(yùn)算速度很快，經(jīng)過(guò)布局優(yōu)化的改進(jìn)K-means聚類(lèi)算法的總耗時(shí)為55.23 s，比優(yōu)化前減少了13.26 s，其室內(nèi)定位結(jié)果達(dá)到定位要求。

4 結(jié)論

    本文采用先進(jìn)的嵌入式和頻譜接收機(jī)建立了室內(nèi)定位系統(tǒng)，利用SMSA融合算法對(duì)室內(nèi)定位模型進(jìn)行了尋優(yōu)計(jì)算，確定了室內(nèi)環(huán)境的最優(yōu)化布局。實(shí)驗(yàn)證明，本文提出的室內(nèi)AP主動(dòng)布局優(yōu)化方法和改進(jìn)的K-means聚類(lèi)算法合理利用了AP資源，提高了定位精度。如何實(shí)現(xiàn)對(duì)室內(nèi)環(huán)境復(fù)雜和人員流動(dòng)較密集區(qū)域的AP部署優(yōu)化以及對(duì)動(dòng)態(tài)目標(biāo)的準(zhǔn)確定位，還需要在今后實(shí)驗(yàn)中去驗(yàn)證。

參考文獻(xiàn)

[1] 鄧中亮.室內(nèi)定位現(xiàn)狀與發(fā)展趨勢(shì)研究[J].中國(guó)通信，2013，10(3)：42-55.

[2] 何海平，郭杭，方爽.基于模糊聚類(lèi)的ZigBee室內(nèi)定位系統(tǒng)設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2016，42(5)：71-73，77.

[3] 崔斌，趙西安.一種基于傳播模型和位置指紋的混合室內(nèi)定位方法[J].測(cè)繪通報(bào)，2015，43(6)：35-38 .

[4] 都伊林．一種模糊聚類(lèi)KNN位置指紋定位算法[J].微型機(jī)與應(yīng)用，2012，31(23)：55-58.

[5] 孫鳳，施偉斌，黃靈鳳.基于無(wú)線傳感器網(wǎng)絡(luò)的室內(nèi)定位技術(shù)的研究[J].電子技術(shù)應(yīng)用，2013，39(10)：80-83.

[6] 李健，高永濤，謝玉玲，等.基于無(wú)需測(cè)速的單純形法微地震定位改進(jìn)研究[J].巖石力學(xué)與工程學(xué)報(bào)，2014，33(7)：1336-1346.

[7] 劉彥隆，呂顯朋，王相國(guó).混合遺傳算法在WSNs定位中的應(yīng)用[J].傳感器與微系統(tǒng)，2014，33(2)：150-153.

[8] 陳空，宋春雷，陳家斌.基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法[J].導(dǎo)航定位與授時(shí)，2016，3(4)：58-64.

[9] 周牧，蒲巧林，田增山.室內(nèi)WLAN定位中位置指紋優(yōu)化的接入點(diǎn)部署方法[J].通信學(xué)報(bào)，2015，36(Z1)：30-41.

[10] 陳望，賈振紅，覃錫忠，等.基于改進(jìn)K-means聚類(lèi)算法的室內(nèi)WLAN定位研究[J].激光雜志，2014，39(7)：11-14.

作者信息:

陳云飛1，2，杜太行1，3，江春冬1，3，王景玉1，李娟妹1

（1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津300130；2.邢臺(tái)職業(yè)技術(shù)學(xué)院 電氣工程系，河北 邢臺(tái)054000；

3.河北省控制工程研究中心，天津300130）