（河南工業(yè)貿(mào)易職業(yè)學(xué)院，信息工程系，河南鄭州市，450000）張海霞

隨著科技發(fā)展，定位技術(shù)發(fā)展越來越快，幾乎延伸到了各行各業(yè)，人們對(duì)定位要求越來越精準(zhǔn)，僅憑借全球定位系統(tǒng)（GPS）的室外定位已經(jīng)無法滿足人們需求[1-3]。因?yàn)橐苿?dòng)通訊設(shè)備和Wi-Fi信號(hào)的廣泛覆蓋，基于Wi-Fi的室內(nèi)定位算法憑借其成本低、定位精度高且無需其他外設(shè)等優(yōu)點(diǎn)，逐漸成為現(xiàn)階段的研究熱點(diǎn)之一[4]。該定位方法在定位收集信號(hào)的過程中，基于Wi-Fi的室內(nèi)定位僅依靠信號(hào)接受強(qiáng)度指示（RSSI）就可以完成定位，但由于障礙物遮擋、環(huán)境變化等多重因素引起的時(shí)效性、多徑效應(yīng)等問題，RSSI信號(hào)存在誤差，在極大程度上影響著室內(nèi)定位的精度[5]。因此，對(duì)基于Wi-Fi的室內(nèi)定位研究十分必要。

1 分區(qū)聚類算法

1.1 WAP聚類算法

目前，通?？梢赃x擇在無線傳感器網(wǎng)絡(luò)（Wireless sensor network，WSN）應(yīng)用系統(tǒng)中加入移動(dòng)節(jié)點(diǎn)的方法來實(shí)現(xiàn)更加靈活地完成現(xiàn)場(chǎng)監(jiān)測(cè)過程，但是如何對(duì)動(dòng)態(tài)過程采用具備低能耗與高精度的WSN節(jié)點(diǎn)進(jìn)行定位是現(xiàn)階段眾多研究人員需要解決的問題等。

AP聚類算法中以p作為節(jié)點(diǎn)為聚類中心的度量。由于環(huán)境、人員流動(dòng)、多徑效應(yīng)等因素的影響，不同信號(hào)接收裝置接收到RSSI信號(hào)值存在差異，僅憑借歐氏距離計(jì)算S，選取矩陣中值或者均值作為相似性度量，會(huì)導(dǎo)致定位結(jié)果不準(zhǔn)確。針對(duì)上述問題，本文引入熵值法對(duì)S相似度進(jìn)行優(yōu)化后，對(duì)優(yōu)化后的p進(jìn)行加權(quán)處理，已獲得更加準(zhǔn)確的粗定位結(jié)果。

熵值法用來判斷指標(biāo)的離散程度。將每個(gè)節(jié)點(diǎn)的一組RSSI值作為輸入計(jì)算權(quán)重，并將得到的權(quán)重作為不同信號(hào)接收裝置對(duì)該節(jié)點(diǎn)的影響因子。其中，針對(duì)異質(zhì)特征維數(shù)同質(zhì)化問題，需要將特征維數(shù)的標(biāo)準(zhǔn)化處理。首先歸一化處理數(shù)據(jù)，計(jì)算正向特征維數(shù)和負(fù)向特征維數(shù)數(shù)值。

正向特征維數(shù)：

負(fù)向特征維數(shù)：

將一組RSSI值作為輸入，熵值法具體計(jì)算公式如下：

其中，RSSIij為指紋庫中第i個(gè)數(shù)據(jù)點(diǎn)的第j個(gè)RSSI值，i=1，2，…，n；j=1，2，…，N，n為樣本數(shù)，N為RSSI值數(shù)，j表示權(quán)重。則節(jié)點(diǎn)i，k之間的相似度計(jì)算方式為：

通過得到的權(quán)值計(jì)算數(shù)據(jù)點(diǎn)之間的相似度，對(duì)相似度進(jìn)行均值加權(quán)處理，則p的值為：

1.2 基于KWAP-KNN算法原理及流程

距離信號(hào)發(fā)射裝置越近，則RSSI信號(hào)接收更準(zhǔn)確。且RSSI信號(hào)值在空間上區(qū)分能力有限，通常都在1m以上，所以為了避免相鄰指紋信息在位置上二異性，兩個(gè)信號(hào)發(fā)射裝置布置距離應(yīng)該在1m以上。以信號(hào)接收裝置為圓心，根據(jù)實(shí)際環(huán)境確定覆蓋區(qū)域半徑，盡量保障大部分區(qū)域在劃分的覆蓋區(qū)域范圍內(nèi)。

區(qū)域劃分依據(jù)為位置信息，選擇K-means進(jìn)行分區(qū)，該方法簡(jiǎn)單且容易實(shí)現(xiàn)，選取信號(hào)發(fā)射裝置所在位置為K個(gè)聚類中心的位置，通過聚類對(duì)未覆蓋區(qū)域和交叉區(qū)域進(jìn)行分區(qū)。當(dāng)對(duì)未知節(jié)點(diǎn)進(jìn)行區(qū)域劃分時(shí)，根據(jù)RSSI值差異確定歸屬區(qū)域，如果屬于覆蓋區(qū)域，直接進(jìn)行WAP聚類，如果屬于未覆蓋或者交叉區(qū)域，通過K-means重新進(jìn)行歸類，當(dāng)所有的節(jié)點(diǎn)被劃分到不同區(qū)域時(shí)，劃定小區(qū)域。最后通過KNN聚類在小區(qū)域內(nèi)獲取粗定位結(jié)果。整個(gè)區(qū)域劃分及定位流程如圖1所示。

圖1 區(qū)域劃分流程圖

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

區(qū)域劃分以實(shí)際室內(nèi)環(huán)境和信號(hào)發(fā)射裝置布置為準(zhǔn)，以信號(hào)發(fā)射裝置位置為圓心，固定距離為圓心，劃分區(qū)域。實(shí)驗(yàn)在14m×11m的區(qū)域進(jìn)行，現(xiàn)場(chǎng)布置了共6個(gè)路由器作為信號(hào)發(fā)射裝置。

通過Matlab軟件來仿真驗(yàn)證本文的定位算法。進(jìn)行仿真測(cè)試時(shí)，按照表1數(shù)據(jù)來設(shè)定各項(xiàng)參數(shù)。在100m的范圍內(nèi)以隨機(jī)方式設(shè)置共60個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)的通信半徑設(shè)定為20m。節(jié)點(diǎn)分布圖如圖2所示。

表1 參數(shù)設(shè)置

圖2 節(jié)點(diǎn)分布圖

圖3為AP聚類和WAP兩種聚類的效果圖。

圖3 聚類效果圖

選取一百組測(cè)試點(diǎn)進(jìn)行實(shí)驗(yàn)，未進(jìn)行區(qū)域劃分之前，分別使用KNN、AP-KNN、WAP-KNN三種算法進(jìn)行定位?？梢缘玫饺鐖D4所示的誤差累積圖。圖中可以看出，隨著節(jié)點(diǎn)數(shù)目增加，WAP-KNN累積定位誤差低于其余兩種定位方法。

圖4 平均誤差累積

圖5為三種定位方法誤差累積分布圖。100個(gè)參考點(diǎn)中，定位誤差小于2.5m的概率，KNN、APKNN、WAP-KNN算中算法分別為72%、67%、62%，其中KNN算法概率最高。但是WAP-KNN算法所有參考點(diǎn)的定位誤差均小于3.45m，AP-KNN均小于4.00m，WAP-KNN總體定位誤差較小。而且APKNN和WAP-KNN這兩種方法定位沒有出現(xiàn)誤差較大的點(diǎn)。之后對(duì)三種方法求解平均定位誤差，并對(duì)其最小最大誤差進(jìn)行分析，可得如表2所示的定位誤差表。從表中數(shù)據(jù)看出，WAP-KNN算法的平均誤差、最大最小誤差值都比其余兩種算法要小。

圖5 三種定位方法誤差累積分布圖

表2 三種定位算法定位誤差表

3 結(jié)語

綜上所述，針對(duì)單一聚類算法存在的多種問題，提出一種基于KWAP-KNN的分區(qū)聚類算法。實(shí)驗(yàn)結(jié)果證明，無論從樣本點(diǎn)的之間相似性，還是從聚類時(shí)間來講，WAP聚類算法都比AP聚類算法低，聚類效果更好。區(qū)域劃分后，KWAP-KNN算法得到的粗定位結(jié)果更準(zhǔn)確，定位精度可達(dá)到1.8m左右。