井下WLAN位置指紋定位中改進(jìn)區(qū)域劃分方法研究

宋明智，錢建生，胡青松

(中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116)

0 引言

礦井人員定位是煤礦安全生產(chǎn)與管理的重要研究課題之一[1]，井下作業(yè)人員位置信息的記錄與監(jiān)測(cè)保證了煤礦生產(chǎn)調(diào)度的高效性以及井下事故救援的有效性。近年來，電子信息技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和移動(dòng)互聯(lián)技術(shù)的快速發(fā)展為井下人員定位課題的研究與創(chuàng)新提供了必要的技術(shù)支持[2-3]。RFID(Radio Frequency Identification)、ZigBee、WiFi等技術(shù)都已在井下人員定位課題中有相應(yīng)的研究與應(yīng)用[4]。在上述定位技術(shù)中，以WiFi技術(shù)為基礎(chǔ)的井下WLAN(Wireless Local Area Network)位置指紋人員定位方法因其擴(kuò)展性強(qiáng)、易維護(hù)、用戶接入量大、覆蓋范圍廣、成本較低、傳輸速率高、保密性好、抗干擾能力強(qiáng)等[5-6]特點(diǎn)，有著廣泛的應(yīng)用前景[7]。

現(xiàn)階段，對(duì)于井下WLAN位置指紋定位的研究主要集中在位置指紋樣本降噪、無線接入點(diǎn)最優(yōu)選擇[8]、在線位置指紋匹配算法[9]等方面，而對(duì)于實(shí)際應(yīng)用中定位效率提升的研究卻很少。一般應(yīng)用場(chǎng)景中，由于井下定位區(qū)域較大，如果在線定位階段使用全局位置指紋數(shù)據(jù)庫(kù)進(jìn)行遍歷求解，不僅很大程度上會(huì)影響定位系統(tǒng)的運(yùn)行效率，同時(shí)也有可能引入不必要的噪聲干擾。目前的解決方案是將定位區(qū)域進(jìn)行合理劃分，將位置指紋數(shù)據(jù)庫(kù)分割成與定位子區(qū)域?qū)?yīng)的子數(shù)據(jù)庫(kù)，用于子區(qū)域粗定位和位置指紋精確匹配[10]。經(jīng)典的位置指紋定位系統(tǒng)中，主要是通過聚類算法來實(shí)現(xiàn)位置指紋樣本的整體性劃分。常用的聚類算法包括K均值法(K-Means)、模糊C均值法(Fuzzy C-Means，F(xiàn)CM)[11]和放射傳播法(Affinity Propagation, AP)[12]等。上述聚類算法雖然在位置指紋樣本的劃分上有較好的性能表現(xiàn)，但只是針對(duì)接收信號(hào)強(qiáng)度(Receive Signal Strength，RSS)的統(tǒng)計(jì)分布特性進(jìn)行聚類劃分，并沒有充分考慮到奇點(diǎn)問題[13]。因此，本文提出了一種基于類關(guān)系的K-Means(Class RelationshipK-Means，CRK-Means)算法，用以解決位置指紋數(shù)據(jù)庫(kù)聚類劃分過程中的奇點(diǎn)問題。對(duì)聚類劃分后的定位區(qū)域一般采用隨機(jī)森林(Random Forest，RF)算法進(jìn)行粗定位，以降低系統(tǒng)資源消耗，提升定位效率。但傳統(tǒng)RF算法中決策樹總數(shù)和參考點(diǎn)特征數(shù)的取值來自經(jīng)驗(yàn)數(shù)據(jù)[14]，并不具備普適性。對(duì)此，可以考慮將遺傳算法(Genetic Algorithm，GA)與RF算法相結(jié)合，通過GA算法的選擇、交叉和變異操作求解RF算法中決策樹總數(shù)和參考點(diǎn)特征數(shù)的最優(yōu)取值。實(shí)驗(yàn)結(jié)果表明:與其他幾類聚類算法相比，CRK-Means算法較好地解決了奇點(diǎn)問題，并在提升定位精度的同時(shí)，改善了實(shí)時(shí)定位的效率。而GA-RF算法對(duì)于RF算法中決策樹總數(shù)和參考點(diǎn)特征選擇數(shù)的取值有著更好的優(yōu)化效果，使得井下子區(qū)域的粗定位更加準(zhǔn)確。

1 CRK-Means算法

1.1 奇點(diǎn)問題

位置指紋數(shù)據(jù)庫(kù)聚類劃分的奇點(diǎn)問題主要是指經(jīng)聚類劃分的某些參考點(diǎn)雖然在RSS特征上屬于某一個(gè)聚類空間，但這些參考點(diǎn)所在實(shí)際物理位置卻不屬于該聚類空間對(duì)應(yīng)的物理空間。奇點(diǎn)問題會(huì)直接導(dǎo)致某些位置指紋子數(shù)據(jù)庫(kù)的RSS樣本缺失或誤歸類，最終影響人員定位的精確性。對(duì)于奇點(diǎn)問題，研究人員也給出了不同的解決方案，比如忽略這些奇點(diǎn)位置并刪除對(duì)應(yīng)位置上的參考點(diǎn)，或者人為調(diào)整奇點(diǎn)的所屬類別[15]。不過這些解決方案有可能會(huì)使已分類的聚類中心發(fā)生變化，從而影響定位性能。而且定位區(qū)域越大，這些解決方案的效果越差。為了解決上述問題，本文提出了CRK-Means算法。該算法在K均值的基礎(chǔ)上結(jié)合自組織迭代分析算法(Iterative Self-Organizing Data Analysis，ISODATA)[16]，并以Fisher準(zhǔn)則[17]、類內(nèi)離散度和類間離散度為限制條件，通過聚類融合和奇點(diǎn)分離過程，最終完成定位區(qū)域的合理劃分。

1.2 CRK-Means算法原理

(1)

(2)

根據(jù)類內(nèi)離散度和類間離散度的定義，則區(qū)域劃分的目標(biāo)函數(shù)為

(3)

式中Ce為第e個(gè)聚類類內(nèi)離散度與類間離散度的比值。

使式(3)最小化的聚類劃分就是理論上的區(qū)域劃分，不同子區(qū)域的劃分越明顯，則區(qū)域定位的判別特征越明顯。

采用經(jīng)典凸優(yōu)化方法求解式(3)有可能難以滿足區(qū)域參考點(diǎn)物理位置連續(xù)的限制條件，因此，可以采用含有聚合、分離過程的CRK-Means聚類算法求解式(3)，具體的實(shí)現(xiàn)步驟如下：

步驟1：對(duì)位置指紋數(shù)據(jù)庫(kù)進(jìn)行1/2劃分，即位置指紋數(shù)據(jù)庫(kù)中每2個(gè)位置最近的參考點(diǎn)分為一個(gè)單位聚類，每個(gè)單位聚類的類屬性用Ce表示：

(4)

式中K=N/2，N為參考點(diǎn)總數(shù)。如果N為奇數(shù)，則K=(N-1)/2，最后未分類的3個(gè)參考點(diǎn)分為一個(gè)聚類。

步驟2：預(yù)設(shè)聚類中心數(shù)(與目標(biāo)聚類數(shù)不同)并計(jì)算聚類中心點(diǎn)。以Ce為聚類特征，依次計(jì)算每2個(gè)聚類特征Ce的相似度，第e個(gè)聚類與其他聚類間Ce的平均相似度為

e,f=1,2,…,K且e≠f

(5)

e=1,2，…,K且e≠c1

(6)

第3個(gè)聚類中心點(diǎn)通過計(jì)算剩下所有聚類中與Cc1、Cc2相似度最小的聚類求得。

e=1,2，…,K且e≠c1,c2

(7)

依次類推，可以求解出預(yù)設(shè)數(shù)目下的初始聚類中心點(diǎn)。

步驟3：聚類融合。初始聚類中心點(diǎn)求解完成后，將K個(gè)單位聚類根據(jù)Ce的相似度分配至對(duì)應(yīng)的聚類中心。聚類融合后，融合的聚類對(duì)應(yīng)的參考點(diǎn)也進(jìn)行合并，且此時(shí)聚類數(shù)與目標(biāo)聚類數(shù)相同。

步驟4：奇點(diǎn)分離。為了保證各聚類內(nèi)參考點(diǎn)的連續(xù)性，給出聚類內(nèi)參考點(diǎn)之間位置關(guān)系的限制條件:

(8)

式中：(xi1,yi1)和(xi2,yi2)分別為同一聚類e中參考點(diǎn)RPi1和RPi2的位置坐標(biāo)，i1,i2=1,2，…,Ne；LLIM為聚類內(nèi)部參考點(diǎn)距離閾值，由井下巷道定位環(huán)境和參考點(diǎn)采樣密度決定。

步驟5：判斷聚類結(jié)果是否滿足收斂條件，如果滿足，則輸出聚類結(jié)果，否則返回步驟2繼續(xù)迭代執(zhí)行。

2 基于GA-RF算法的井下子區(qū)域定位

使用CRK-Means聚類算法將井下定位區(qū)域進(jìn)行劃分后，定位區(qū)域中所有參考點(diǎn)被人為附加上所屬類別的標(biāo)簽。該聚類劃分過程可以看作是一種集成學(xué)習(xí)過程，井下子區(qū)域的定位可以利用類別標(biāo)簽并采用集成學(xué)習(xí)的方法來實(shí)現(xiàn)。本文采用的RF算法[14]就屬于并行集成學(xué)習(xí)的一種。

2.1 RF算法

RF算法是指利用多棵決策樹對(duì)樣本進(jìn)行訓(xùn)練和預(yù)測(cè)的一種集成分類器，其決策過程同Bagging[18]和Boosting[19]方法類似，是通過對(duì)每棵決策樹的輸出投票獲得最終結(jié)果。與Bagging和Boosting方法不同之處在于RF算法會(huì)同時(shí)對(duì)樣本及樣本特征進(jìn)行采集，并且無需剪枝(Pruning)過程[20]。由于RF算法引入了對(duì)數(shù)據(jù)項(xiàng)行、列的隨機(jī)采樣，因此較好地解決了過擬合問題，且對(duì)高維數(shù)據(jù)處理有一定的性能優(yōu)勢(shì)，適用于位置指紋數(shù)據(jù)庫(kù)處理。

井下位置指紋定位問題中，使用RF算法實(shí)現(xiàn)子區(qū)域粗定位的主要步驟如下：

步驟1：初始化。假設(shè)子區(qū)域數(shù)量為K，定位區(qū)域參考點(diǎn)總數(shù)為N，AP(接入點(diǎn))信號(hào)總數(shù)為R(各參考點(diǎn)的特征數(shù)為R)，訓(xùn)練樣本集選取的參考點(diǎn)數(shù)為Ne(Ne≤N)，訓(xùn)練樣本集選取的參考點(diǎn)特征數(shù)為Re(Re≤R)，決策樹總數(shù)為D。

步驟2：對(duì)于第p棵決策樹，隨機(jī)選擇一組位置指紋數(shù)據(jù)庫(kù)的聚類(包含Ne個(gè)參考點(diǎn))，并記錄該聚類的類標(biāo)簽(類屬性)，同時(shí)記錄位置指紋數(shù)據(jù)庫(kù)中未被選中的剩余(N-Ne)個(gè)參考點(diǎn)用作訓(xùn)練測(cè)試集的誤差測(cè)評(píng)。

步驟3：對(duì)于第p棵決策樹中第q個(gè)節(jié)點(diǎn)，隨機(jī)選取對(duì)應(yīng)參考點(diǎn)的Re個(gè)RSS的特征向量，根據(jù)最優(yōu)劃分構(gòu)建判決標(biāo)準(zhǔn)。最優(yōu)劃分可以根據(jù)聚類信息增益進(jìn)行判斷。

步驟4：q加1，如果q>Ne，則跳至步驟5執(zhí)行，否則返回步驟3繼續(xù)執(zhí)行。

步驟5：p加1，如果p>D，則跳至步驟6執(zhí)行，否則返回步驟2繼續(xù)執(zhí)行。

步驟6：決策樹訓(xùn)練結(jié)束，集成分類器構(gòu)建完成，此時(shí)的構(gòu)建模型即為RF分類模型，可以用于井下子區(qū)域定位判別。RF分類模型的輸入為用戶隨身攜帶的移動(dòng)終端實(shí)時(shí)采集的來自所有AP信號(hào)的一組RSS序列(不在接收范圍內(nèi)的AP信號(hào)對(duì)應(yīng)的RSS默認(rèn)賦值為-80 dB·m)，通過對(duì)模型中所有決策樹的輸出以投票方式獲得最終的結(jié)果(目標(biāo)聚類類別)，即可判定用戶所處井下子區(qū)域。

RF算法的優(yōu)點(diǎn)：RF分類模型中的決策樹都是并行處理生成的，且不依賴于上一時(shí)刻的運(yùn)算結(jié)果，運(yùn)算效率較高。但在不同巷道環(huán)境的區(qū)域中，RF算法的部分參數(shù)需要優(yōu)化調(diào)整。對(duì)于不同巷道環(huán)境，應(yīng)該設(shè)定相應(yīng)的決策樹總數(shù)D和參考點(diǎn)特征選擇數(shù)Re，用以提升子區(qū)域定位的精度。

2.2 GA-RF算法

為了使RF算法具備一定的巷道環(huán)境自適應(yīng)性，可以考慮使用GA算法對(duì)RF算法的參數(shù)進(jìn)行自適應(yīng)調(diào)整。GA算法源自對(duì)生物遺傳進(jìn)化規(guī)律的學(xué)習(xí)與總結(jié)，通過種群中個(gè)體的優(yōu)勝劣汰機(jī)制保證種群始終具備更強(qiáng)的適應(yīng)性。GA算法的優(yōu)化過程主要包括選擇、交叉和變異3個(gè)操作[21]。選擇操作是在當(dāng)前代的個(gè)體中選取一定數(shù)目的最優(yōu)個(gè)體用于下一代種群的更新。交叉操作用于個(gè)體信息交換，從而提取和保留種群中個(gè)體的優(yōu)良基因。變異操作是對(duì)種群中的少量個(gè)體進(jìn)行基因突變，形成新的多樣性個(gè)體。對(duì)于RF算法，其適應(yīng)度函數(shù)為

(9)

式中δ為RF分類模型的誤分概率。

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

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)巷道環(huán)境平面圖如圖1所示，定位巷道中總共部署有10個(gè)礦用本安型無線交換機(jī)作為AP信號(hào)源，符號(hào)“+”代表預(yù)設(shè)參考點(diǎn)位置，參考點(diǎn)的設(shè)置密度按照巷道延伸方向上每隔1 m平均設(shè)置2個(gè)參考點(diǎn)，在巷道十字交叉位置處另外設(shè)置補(bǔ)償參考點(diǎn)。由于在線定位階段，位置指紋匹配過程使用的是參考點(diǎn)位置指紋樣本數(shù)據(jù)的統(tǒng)計(jì)均值，所以，在位置指紋數(shù)據(jù)庫(kù)的離線采集過程中，需要在每個(gè)參考點(diǎn)處采集1 000個(gè)位置指紋樣本，以確保各參考點(diǎn)位置指紋樣本的有效性。實(shí)驗(yàn)主要分為3組：

圖1 井下子區(qū)域粗定位實(shí)驗(yàn)巷道平面圖

實(shí)驗(yàn)1：完成K-Means算法、FCM算法和CRK-Means算法對(duì)定位區(qū)域聚類劃分的對(duì)比測(cè)試。

實(shí)驗(yàn)2：完成GA-RF算法和RF算法對(duì)于CRK-Means算法聚類劃分后的子區(qū)域粗定位的對(duì)比測(cè)試。

實(shí)驗(yàn)3：完成K-Means算法、FCM算法和CRK-Means算法定位精度的對(duì)比測(cè)試。

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

實(shí)驗(yàn)1分別使用K-Means算法、FCM算法和CRK-Means算法對(duì)井下定位區(qū)域進(jìn)行聚類劃分，并根據(jù)定位區(qū)域的結(jié)構(gòu)特征，設(shè)置聚類總數(shù)為5。圖2—圖4分別給出了使用K-Means算法、FCM算法和CRK-Means算法時(shí)井下區(qū)域的劃分結(jié)果，其中T1-T5表示劃分后的5個(gè)子區(qū)域。3種算法在5個(gè)子區(qū)域的劃分上區(qū)別很小，但K-Means算法和FCM算法的區(qū)域劃分結(jié)果中都存在奇點(diǎn)，使用CRK-Means算法則有效解決了奇點(diǎn)問題。

圖2 K-Means算法聚類劃分結(jié)果

圖3 FCM算法聚類劃分結(jié)果

實(shí)驗(yàn)2在實(shí)驗(yàn)1的基礎(chǔ)上，對(duì)CRK-Means算法聚類劃分后的區(qū)域分別使用RF算法和GA-RF算法進(jìn)行在線子區(qū)域粗定位，每組定位實(shí)驗(yàn)中在5個(gè)子區(qū)域中分別進(jìn)行200次子區(qū)域粗定位。為了保證粗定位的實(shí)驗(yàn)效率，每個(gè)子區(qū)域中的粗定位位置都盡量靠近劃分區(qū)域的區(qū)分處。子區(qū)域粗定位只對(duì)用戶所在子區(qū)域進(jìn)行判定，不對(duì)具體的位置進(jìn)行估計(jì)。表1給出了子區(qū)域粗定位結(jié)果。RF算法子區(qū)域粗定位的平均正確率為94.7%，而將GA算法與RF算法結(jié)合后，RF算法中的決策樹總數(shù)D和參考點(diǎn)特征選擇數(shù)Re經(jīng)過GA算法的自適應(yīng)調(diào)整機(jī)制與當(dāng)前的聚類劃分更匹配，子區(qū)域粗定位的平均正確率為97.9%，因此，GA-RF算法在用戶所處區(qū)域的實(shí)時(shí)判斷上有著更好的決策機(jī)制。

圖4 CRK-Means算法聚類劃分結(jié)果

表1 RF算法和GA-RF算法對(duì)CRK-Means聚類劃分區(qū)域粗定位結(jié)果

實(shí)驗(yàn)3對(duì)K-Means算法、FCM算法和CRK-Means算法聚類劃分后的定位區(qū)域各自使用GA-RF算法先進(jìn)行子區(qū)域粗定位，再使用WKNN(Weighted K-Nearest Neighbor)定位算法進(jìn)行位置指紋精確匹配，每種聚類算法分別進(jìn)行500次隨機(jī)位置的定位。圖5給出了3種聚類算法區(qū)域劃分后的定位精度對(duì)比。因?yàn)镃RK-Means算法有效地解決了奇點(diǎn)問題，使用GA-RF算法進(jìn)行粗定位的精度得到了提升，進(jìn)而使得位置指紋匹配更加精確。使用CRK-Means算法聚類劃分后的位置指紋數(shù)據(jù)庫(kù)進(jìn)行WLAN井下人員定位時(shí)，置信概率大于90%的最小定位誤差為3 m，而使用K-Means算法和FCM算法后的位置指紋數(shù)據(jù)庫(kù)的定位結(jié)果，在置信概率大于90%時(shí)的最小定位誤差為3.5 m。這說明CRK-Means算法在有效解決奇點(diǎn)問題的同時(shí)，對(duì)定位精度的提升也優(yōu)于傳統(tǒng)的聚類算法。

圖5 基于不同聚類算法的定位性能對(duì)比

4 結(jié)語

在井下人員定位應(yīng)用中，采用WLAN位置指紋定位技術(shù)一定會(huì)構(gòu)建數(shù)量龐大的位置指紋樣本。區(qū)域劃分技術(shù)不僅大幅度減少了定位過程中位置指紋匹配的計(jì)算量，并且能夠輔助提升定位的精度。CRK-Means算法的提出有效改善了傳統(tǒng)聚類算法可能出現(xiàn)奇點(diǎn)的問題，GA-RF算法則較好地解決了RF算法在子區(qū)域定位過程中決策樹總數(shù)和參考點(diǎn)特征數(shù)的最優(yōu)取值問題。實(shí)驗(yàn)結(jié)果表明：GA-RF算法的子區(qū)域粗定位正確率為97.9%，要優(yōu)于RF算法94.7%的子區(qū)域粗定位正確率。而使用CRK-Means算法聚類劃分后的位置指紋數(shù)據(jù)庫(kù)進(jìn)行WLAN井下人員定位時(shí)，置信概率大于90%時(shí)的最小定位誤差相比于K-Means算法和FCM算法提升了0.5 m，達(dá)到了3 m。CRK-Means算法在有效解決奇點(diǎn)問題的同時(shí)，對(duì)井下人員定位精度的提升也有一定的優(yōu)勢(shì)。