0 引言

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

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

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

1 室內定位AP部署優化模型

1.1 部署優化的目標函數

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

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

1.2 計算步驟

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

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

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

2 改進K-means聚類算法

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

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

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

    (1)Offline采集階段

    Input：信號采樣數據集X={X₁，X₂，…，X_n}

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

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

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

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

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

    (2)Online定位階段

    Input：目標信號采樣樣本點數據X_rssi

    Output：比對輸出位置坐標值

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

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

3 實驗結果與分析

3.1 實驗平臺

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

    為驗證AP位置優化算法的有效性，實驗在實驗樓10 m×13 m的空曠教室中進行，如圖1所示，以0.8 m間距設置參考坐標點間距（這是地磚的尺寸，以便測量），位置點依次設置為A、B、C、D，文獻[9]驗證了較小定位空間內選用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型發生器，其中心頻率可設置為70 MHz～6 GHz。發射源頻率調制為840 MHz來模擬手機干擾源頻率，信號功率為15 dB，信號源的萬向天線與支架的中心軸線重合，支架平面距地面0.5 m，較低的信號源高度可以減少地面的反射波的測量擾動，以每間隔1 m選取參考坐標進行指紋信息數據采集，支架中心軸對準參考點標記，采集時間為15 s，采集期間人員手機關閉以凈化電波環境，降低外界干擾。離線階段共采集參考位置40個，每個指紋位置采集3次，其中排除靠近建筑拐角和堆積雜物的區域，以及與AP太近和重合的參考位置。

3.2 實驗及誤差分析

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

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

4 結論

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

參考文獻

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

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

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

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

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

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

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

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

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

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

作者信息:

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

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

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