0 引言

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

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

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

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

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

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

其中,，s,、t為定位空間的邊界長度。

1.2 計算步驟

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

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

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

2 改進K-means聚類算法

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

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

    改進K-means 聚類算法步驟如下：

    (1)Offline采集階段

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

    Output：s個類C_n(1≤s≤n) 

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

    ②計算X_p(p=1，2,，…,，n)與各初始類中心坐標的歐式距離dij，求均值降序排序,，并將每個排序點分配到最近鄰的類中心的子類中,。

    ③計算子類中所有參考點之間歐式距離和，選取最小值對應的點作為新的聚類中心,。

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

    (2)Online定位階段

    Input：目標信號采樣樣本點數(shù)據(jù)X_rssi

    Output：比對輸出位置坐標值

    ①計算定位目標X_rssi與各聚類中心的歐式距離d_rssi,，則區(qū)分目標點所屬子類,。

    ②計算X_rssi與類目中心的歐式距離，用KNN法匹配出目標點的位置坐標值并輸出運算結果,。

3 實驗結果與分析

3.1 實驗平臺

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

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

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

3.2 實驗及誤差分析

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

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

4 結論

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

參考文獻

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

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

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

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

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

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

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

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

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

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

作者信息:

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

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

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