劉 夏,莫樹培

(1.貴州工業(yè)職業(yè)技術(shù)學(xué)院電子與信息工程學(xué)院,貴陽 550000;2.中南大學(xué)信息科學(xué)與工程學(xué)院,長沙 410000)

為提高煤礦安全生產(chǎn)保障能力,國家強制要求全國煤礦都必須建立和完善安全避險六大系統(tǒng),其系統(tǒng)包括監(jiān)測監(jiān)控、人員定位、供水施救、壓風(fēng)自救、通信聯(lián)絡(luò)、緊急避險等。煤礦井下人員定位系統(tǒng)能夠及時、準(zhǔn)確的將井下各個區(qū)域人員的動態(tài)情況,使管理人員能夠隨時掌握井下人員運動軌跡。當(dāng)事故發(fā)生時,救援人員可根據(jù)井下人員定位系統(tǒng)所提供的數(shù)據(jù),迅速獲取有關(guān)人員的位置情況,提高應(yīng)急救援工作的效率。目前井下人員定位系統(tǒng)[1]主要采用RFID區(qū)域位置監(jiān)測技術(shù),只能將井下工作人員定位到一個區(qū)域,定位精度不高,無法滿足煤礦智能化對人員或設(shè)備定位的需求。

為解決煤礦井下人員定位技術(shù)難題,學(xué)者們研究用慣性導(dǎo)航、UWB、ZigBee和WIFI等技術(shù)進行井下人員定位,其中慣性導(dǎo)航[2]需要移動終端設(shè)備增加陀螺儀、加速度計和磁力計等傳感器才能進行定位;UWB技術(shù)[3]通信距離在10 m左右,不適合將長距離定位;ZigBee技術(shù)[4]傳輸效率慢,對信道帶寬要求較高,從而影響定位效果;WIFI技術(shù)[5]因帶寬高、傳輸速度快、價格便宜、部署方便等特點,近年來已經(jīng)成為研究熱點。WIFI定位技術(shù)通過獲取無線信號的相關(guān)信息估算出目標(biāo)位置數(shù)據(jù),目前主要有DV-Hop定位[6]、到達時間定位、質(zhì)心定位和指紋定位等方法,其中到達時間定位[7]需要精確測量信號的傳播時間,對無線設(shè)備硬件要求高;質(zhì)心定位[8]必須已知3個以上無線網(wǎng)絡(luò)傳感器或AP節(jié)點信息才能實現(xiàn)定位;指紋定位[9]一般分為離線采集階段和在線匹配階段,其關(guān)鍵點在于離線采集階段建立采集點密集分布的定位指紋庫[10],傳統(tǒng)方法是逐點采集信號,會耗費大量的人力和時間。針對此問題,郭紅成等[11]提出線性插值法構(gòu)建指紋庫,存在基點處不光滑,插值精度低;LI等[12]提出反距離加權(quán)插值法構(gòu)建指紋庫,未考慮數(shù)據(jù)在空間分布情況,會造成觀測點權(quán)值不對應(yīng)而造成估計結(jié)果產(chǎn)生偏差;王永星等[13]提出克里金插值算法構(gòu)建指紋庫,采用克里金插值算法進行估算預(yù)測點,但隨著距離h不斷增大,空間相關(guān)性不斷減弱,變異性不斷增強,從而會使樣本反映的統(tǒng)計特性偏離實際,導(dǎo)致插值準(zhǔn)確度降低。

本文在上述方法基礎(chǔ)上,提出利用模擬退火人工蜂群混合優(yōu)化算法對克里金插值算法中理論變異函數(shù)尋找全局最優(yōu)解,再利用少量觀測點的信號數(shù)據(jù),通過改進克里金插值算法估算出預(yù)測點的插值數(shù)據(jù),構(gòu)建完整井下指紋數(shù)據(jù)庫。實驗結(jié)果表明,該構(gòu)建方法進一步提高定位系統(tǒng)的穩(wěn)定性和定位精度,而人工采集指紋數(shù)據(jù)的工作量可減少50%。

1 普通克里金插值算法

克里金插值算法[14]是法國統(tǒng)計學(xué)家喬治斯·馬瑟倫(Georges Matheron)于1963年提出,其定義為對已知樣本加權(quán)平均,估計平面上的未知點,并使得估計值與真實值的數(shù)學(xué)期望相同且方差最小的地質(zhì)統(tǒng)計學(xué)過程。

克里金插值算法也稱空間局部插值,其建立在變異函數(shù)理論和結(jié)構(gòu)分析的基礎(chǔ)上,能夠?qū)^(qū)域變量進行線性無偏最優(yōu)估計。該算法已經(jīng)廣泛應(yīng)用在地質(zhì)學(xué)、環(huán)境科學(xué)、大氣科學(xué)等領(lǐng)域。

設(shè)預(yù)測點RSSI數(shù)據(jù)的估計值為z*(x0),第i個位置觀測值為z(x)i,其公式可表示為:

式中λi為第i位置觀測值的權(quán)重,m為用于估計待預(yù)測點的數(shù)量。

區(qū)域化變量是指在區(qū)域內(nèi)所在位置有關(guān)的隨機變量,在本文中是指在區(qū)域內(nèi)不同位置上的信號強度信息RSSI。設(shè)在空間中兩個不同的點x和x+h處的特征值z(x)和z(x)+h存在一定相關(guān)性,相關(guān)度與兩點間的距離h有關(guān)。

變異函數(shù)能夠反應(yīng)區(qū)域化變量的空間結(jié)構(gòu)特征,其計算公式可表示為

(2)

在區(qū)域內(nèi)滿足二階平穩(wěn)假設(shè)條件下,對任意兩點間的距離h,有E[z(x)]=E[z(x)+h],則變異函數(shù)可表示為:

如果γ(x,h)僅依賴于變量h,而于具體的位置x無關(guān),再根據(jù)實驗中已測得信號強度信息數(shù)據(jù)估計出變異函數(shù)稱為實驗變異函數(shù),可表示為:

式中M(h)為距離h時的點對數(shù)目。

在實驗中采集到樣本有限,對于實驗變異函數(shù)γ′(h)在整個區(qū)間上隨距離h變化需要通過理論模型來擬合。

理論模型有純塊金效應(yīng)模型、球狀模型、指數(shù)模型和高斯模型等模型,而利用定位區(qū)域中無線信息強度求解實驗變異函數(shù)是最接近球狀模型的變異函數(shù)。球狀模型公式,可表示為:

式中C0為塊金常數(shù),C為供高,C0+C為基臺值,a為變程。

由式(1)可知,要求出z*(x0)的信號強度就必須權(quán)值λi的值,λi的值是通過實驗變異函數(shù)在無偏性和最小方差條件下,計算得到;由此可以推到出普通克里金方程組為:

(6)

式中μ為Lagrange函數(shù)因子。

由式(1)中λi可以通過方程組形式表示為:

式中,γ(xi-xj)的值可以通過球狀模型的變異函數(shù)來獲得。式(7)方程組能夠簡寫為:

AW=Z

(8)

式中A,W和Z相應(yīng)表示式(7)中左、中右矩陣。

權(quán)值向量W能夠通過式(8)計算得出:

W=A-1Z

(9)

求解矩陣方程式(9)得到權(quán)值λi,待入式(1)可計算出z*(x0),即預(yù)測點RSSI的無偏估計插值。

用插值算法可以減少人工采集量指紋的工作量,考慮到井下無線信號強度的空間相關(guān)性,克里金插值算法通過整體空間球狀模型變異理論對預(yù)測點的作用,當(dāng)距離h較小時計算出的插值準(zhǔn)確度較高;但隨著距離h不斷增大,空間相關(guān)性不斷減弱,變異性不斷增強,從而會使樣本反映的統(tǒng)計特性偏離實際,導(dǎo)致插值準(zhǔn)確度降低。為此本文提出利用模擬退火人工蜂群混合優(yōu)化算法對理論變異函數(shù)球狀模型參數(shù)進行優(yōu)化,使之能達到全局最優(yōu),從而提高插值準(zhǔn)確度。

2 模擬退火人工蜂群混合優(yōu)化算法

人工蜂群算法是模仿蜜蜂行為提出的一種優(yōu)化方法,可解決多變量函數(shù)優(yōu)化問題,但易陷進局部最小值,且易出現(xiàn)適應(yīng)值更新停滯現(xiàn)象。為此本文提出利用模擬退火算法來改善人工蜂群算法,結(jié)合二種算法優(yōu)勢,使理論變異函數(shù)球狀模型參數(shù)能尋到全局最優(yōu)的解。

2.1 人工蜂群算法

人工蜂群[15-16]ABC(Artificial Bee Colony)算法是由蜂群采蜜行為啟發(fā)的算法,通過蜂個體的局部尋優(yōu)行為,最終在群體中突現(xiàn)全局最優(yōu)的值。算法中蜂群主要由引領(lǐng)蜂、偵察蜂和跟隨蜂組成,其中引領(lǐng)蜂和跟隨蜂各占整個峰群數(shù)量的一半,引領(lǐng)蜂與蜜源兩者之間一一對應(yīng),且兩者數(shù)量相等。每個蜜源的位置代表優(yōu)化問題的一個解,蜜源的蜜量對應(yīng)著算法適應(yīng)度,適應(yīng)度值的大小反映蜜源質(zhì)量,也就是優(yōu)化問題解的質(zhì)量,而尋找蜜源任務(wù)是由引領(lǐng)蜂和偵察蜂來完成。

人工蜂群算法初期是由引領(lǐng)蜂隨機選擇蜜源位置,并儲存蜜源位置信息,然后根據(jù)式(10)在領(lǐng)域內(nèi)搜索新的蜜源位置,并獲取該蜜源信息。其中式(10)可表示為:

υij=xij+φij(xij-xkj)

(10)

式中υij為新蜜源位置;xij為原來蜜源位置;φij為隨機數(shù),其范圍為[-1,1];j為第j個待優(yōu)化問題參數(shù)維度,j={1,2,…,D},其中D為總維度數(shù);k為隨機選擇的蜜源標(biāo)號且k≠i。

當(dāng)所有引領(lǐng)蜂搜索完蜜源后,會用搖擺舞方式將蜜源信息傳遞給跟隨蜂,跟隨蜂根據(jù)獲得的蜜源信息選擇蜜源,蜜源量越大被選中的概率也就越大。其概率Pi可表示為:

(11)

式中fiti表示蜜源i的適應(yīng)度值,N為蜜源的數(shù)量。

當(dāng)某一蜜源未更新的次數(shù)達到limit后,舍棄該蜜源,蜜源對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?并隨機產(chǎn)生一個新的蜜源位置Sij,產(chǎn)生的公式可表示為:

因為本文需要對克里金插值的理論變異函數(shù)進行優(yōu)化,所以采用的適應(yīng)度函數(shù)[17]為

式中γ′(h)為實驗變異函數(shù),γ(h)為理論變異函數(shù),M為分離距離個數(shù),hm為第m個分離距離。

2.2 模擬退火算法

模擬退火[18]SA(Simulated Annealing)算法是模擬固體退火過程,利用高溫時粒子的無序性,有效地跳出局部最優(yōu)的陷阱。

將模擬退火算法與人工蜂群算法進行融合,當(dāng)新蜜源適應(yīng)度值低于當(dāng)前蜜源時,按照一定的概率接受新蜜源,從而跳出局部最優(yōu)的陷阱。其概率PSA可表示為:

式中f(mot)為當(dāng)前蜜源的適應(yīng)度值,f′(dau)為新蜜源的適應(yīng)度值,Tk為當(dāng)前溫度。

設(shè)溫度下降函數(shù)為:

Tk=βTk-1

(15)

式中β為降溫系數(shù),β∈[0.75,0.99]。

2.3 模擬退火人工蜂群混合優(yōu)化算法

根據(jù)上述算法公式的建立,模擬退火人工蜂群混合優(yōu)化[19](SA-ABC)算法實施步驟如下:

步驟1初始化人工蜂群和模擬退火的參數(shù),如蜂群總數(shù)SN,蜜源的數(shù)量N,蜜源未更新次數(shù)limit,初始溫度T0,終止溫度Tmin,退火系數(shù)β,最大迭代數(shù)Kmax,迭代數(shù)k,收斂精度ε等,并把需要優(yōu)化參數(shù)映射到蜜源;

步驟2引領(lǐng)蜂隨機選擇一個蜜源,按式(13)計算當(dāng)前蜜源的適應(yīng)度值;

步驟3進入引領(lǐng)蜂階段,引領(lǐng)蜂按式(10)在領(lǐng)域內(nèi)搜索新蜜源位置,并按式(13)計算新蜜源的適應(yīng)度值。按照模擬退火機制選擇是否接受新蜜源:若新蜜源更優(yōu)即f(mot)?時接受新蜜源,否則保留當(dāng)前蜜源。

步驟4進入跟隨蜂階段,引領(lǐng)蜂用搖擺舞方式將蜜源信息傳遞給跟隨蜂,然后跟隨蜂按式(11)選擇蜜源,并在蜜源領(lǐng)域附近進行搜索新蜜源,并按式(13)計算兩個蜜源的適應(yīng)度值,按照模擬退火機制選擇是否接受新蜜源。

步驟5當(dāng)某個蜜源未更新的次數(shù)超過limit,則舍棄該蜜源,蜜源對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?并按式(12)產(chǎn)生一個新的蜜源,并按式(13)計算該蜜源的適應(yīng)度值。

步驟6記錄本次迭代的最優(yōu)解,模擬退火算法按式(15)進行降溫。

步驟7檢查是最優(yōu)蜜源適應(yīng)度是否滿足精度要求或迭代次數(shù)達到最大迭代次數(shù)或當(dāng)前溫度達到終止溫度,若滿足條件則算法結(jié)束,輸出最優(yōu)的解;否則k=k+1,跳轉(zhuǎn)到步驟2。

3 SA-ABC-Kriging插值算法流程

模擬退火人工蜂群混合算法優(yōu)化克里金SA-ABC-Kriging(Simulated Annealing and Artificial Bee Colony optimization Kriging)插值算法流程為:首先由井下采集少量指紋組成采集指紋庫,將該指紋庫信息數(shù)據(jù)結(jié)合Kriging插值構(gòu)建算法模型;其次對插值算法中的變異函數(shù)進行初步擬合,把理論變異函數(shù)球狀模型參數(shù)映射到模擬退火算法與人工蜂群算法中;再次由模擬退火算法與人工蜂群算法尋優(yōu),輸出全局最優(yōu)的參數(shù);最后完成建立SA-ABC-Kriging插值算法模型,具體流程如圖1所示。

圖1 插值算法流程圖

4 煤礦井下指紋庫構(gòu)建方法流程

煤礦井下指紋庫構(gòu)建方法流程需要經(jīng)過采集階段和插值階段,才能生成插值井下無線定位指紋庫,具體流程如圖2所示。

圖2 指紋庫構(gòu)建流程圖

從圖2中可看出,采集階段首先井下巷道中選取采集點,其次采集點通過無線采集設(shè)備掃描各個AP節(jié)點的RSSI值傳送回服務(wù)器,為保障采集數(shù)據(jù)準(zhǔn)確每個點采集20次,然后由服務(wù)器對采集點傳來20次RSSI值求其平均值與采集點的坐標(biāo)位置進行式(16)組合,最后存放到采集指紋數(shù)據(jù)庫中,完成采集過程。

采集點的信息數(shù)據(jù)是按組合的方式存放數(shù)據(jù)庫中,其組合可以表示為:

xi={Xi,Yi,Ri1,Ri2,…,RiP}

(16)

式中P為AP節(jié)點數(shù)目,RiP表示第i個采集點接收到第P個AP節(jié)點的RSSI值,Xi,Yi為第i個采集點坐標(biāo)位置。

插值階段首先根據(jù)采集指紋數(shù)據(jù)庫選取預(yù)測點,其次根據(jù)采集指紋數(shù)據(jù)庫生成SA-ABC-Kriging插值算法,再次調(diào)用所需觀測點的RSSI值,利用SA-ABC-Kriging插值算法對預(yù)測點RSSI值進行估算,并存放到插值指紋數(shù)據(jù)庫中,然后將采集指紋數(shù)據(jù)庫和插值指紋數(shù)據(jù)庫進行整合,最終生成插值井下無線定位指紋庫。

5 實驗結(jié)果分析

5.1 實驗條件及采集方法

實驗條件為貴州某煤礦井下500 m工業(yè)以太網(wǎng)已覆蓋的回風(fēng)巷中,巷道截面寬度在4 m左右,井下實驗區(qū)工程平面如圖3所示。

圖3 實驗區(qū)域工程平面圖

由圖3可看出,實驗區(qū)域為回風(fēng)巷,在回風(fēng)巷500 m區(qū)域范圍內(nèi)共放置6個AP終端,AP節(jié)點之間距離在80 m內(nèi),可實現(xiàn)實驗區(qū)域無線全覆蓋。

采集方法:考慮到煤礦井下特殊地理環(huán)境,且井下巷道為二維平面。井下回風(fēng)巷實驗區(qū)域長度500 m,井下截面寬度在4 m左右,為此把實驗區(qū)域分成為100個4 m×3 m小區(qū)域,小區(qū)域與小區(qū)域間距為1 m。在小區(qū)域內(nèi)共有20個點,具體如圖4所示。

圖4 小區(qū)域指紋采集圖

由圖4可知,在小區(qū)域內(nèi)選取10個點為采集點,10個點為插值估算預(yù)測點。由此可見整個實驗區(qū)域需要用到的采集點應(yīng)為1 000個點,插值估算預(yù)測點應(yīng)為1 000個點,建立完整井下定位指紋數(shù)據(jù)庫就需要2000個點的信息數(shù)據(jù)。

采樣階段:實驗人員佩戴自制無線采集設(shè)備到巷道中采集RSSI數(shù)據(jù)。其自制無線采集設(shè)備由主控芯片STC15W4K56S4、液晶顯示模塊LCD1602、無線芯片ESP8266EX和鋰電池供電模塊組成。該設(shè)備經(jīng)過防爆測試,完全到達井下設(shè)備本質(zhì)安全要求。自制無線采集設(shè)備工作原理:由主控芯片發(fā)送“AT+SCAN”(掃描AP)指令給無線模塊,無線模塊立即掃描當(dāng)前位置處各個AP節(jié)點返回信息數(shù)據(jù)(包括IP地址,MAC地址和接收的信號強度指示RSSI值),主控芯片對該信息數(shù)據(jù)進行處理后,通過無線網(wǎng)絡(luò)傳輸給服務(wù)器。

為檢驗SA-ABC-Kriging插值算法的性能,實驗人員按照式(16)存放方式和逐點采集方法,點與點之間距離1 m,把實驗區(qū)域可采集2 000個點的信息數(shù)據(jù)全部采集完成,并存放到原始井下無線定位指紋庫。再從該數(shù)據(jù)庫中按照小區(qū)域采集方法把1 000個采集點的信息數(shù)據(jù)提取出來,組成采集指紋庫。

在完成2 000個點的采集任務(wù)后,實驗人員又重新隨機采集100組測試數(shù)據(jù),存入測試數(shù)據(jù)庫,為檢驗性能提供數(shù)據(jù)支撐。

插值階段:首先根據(jù)100個小區(qū)域選取出1 000個預(yù)測點,其次根據(jù)采集指紋數(shù)據(jù)庫生成Kriging插值算法模型,對SA-ABC算法初始化,設(shè)置蜂群總數(shù)SN=60,蜜源的數(shù)量N=30,蜜源未更新次數(shù)limit=100,初始溫度T0=600,終止溫度Tmin=0,退火系數(shù)β=0.96,最大迭代數(shù)Kmax=800,迭代數(shù)k=0,收斂精度ε=0.01,然后根據(jù)SA-ABC-Kriging插值算法流程建立算法模型。

首先從采集指紋數(shù)據(jù)庫調(diào)用所需采集點的RSSI值。其次利用SA-ABC-Kriging插值算法對每個預(yù)測點RSSI值進行20次估算。再次用20次估算出的RSSI值,求出該預(yù)測點的RSSI平均值,已確保每個預(yù)測點的RSSI值更精確。然后再將預(yù)測點的RSSI平均值存放到插值指紋數(shù)據(jù)庫,并將采集指紋數(shù)據(jù)庫和插值指紋數(shù)據(jù)庫進行整合,最終生成插值井下無線定位指紋庫,完成插值過程。

5.2 性能分析

為檢驗樣子本文提出插值算法的插值精度,利用K最鄰近算法[20]KNN(K-nearest neighbor)和加權(quán)K最鄰近算法[21]WKNN(WeightedK-Nearest Neighbor)兩種算法驗證原始井下無線定位指紋庫和插值井下無線定位指紋庫的性能。

利用測試數(shù)據(jù)庫中信息數(shù)據(jù),帶到KNN和WKNN算法進行在線定位,其K設(shè)為3。經(jīng)過50次調(diào)用測試數(shù)據(jù)庫中100組測試數(shù)據(jù)定位運行,統(tǒng)計兩個井下定位指紋數(shù)據(jù)庫在2 m內(nèi)的定位誤差累計概率,其結(jié)果如表1所示。

表1 指紋庫2 m定位誤差累計概率對比單位:%

從表1可看出,原始井下無線定位指紋庫和插值井下無線定位指紋庫定位精度基本一樣。再利用KNN算法進行定位,設(shè)K為5。經(jīng)過50次調(diào)用測試數(shù)據(jù)庫中100組測試數(shù)據(jù)定位運行,統(tǒng)計兩個井下定位指紋數(shù)據(jù)庫在3 m內(nèi)的定位誤差累計概率,其結(jié)果如表2所示。

表2 指紋庫3 m定位誤差累計概率對比單位:%

圖5 3種指紋庫定位精度對比圖

從表2可看出,插值井下無線定位指紋庫可以達到原始井下無線定位指紋庫定位精度。由此可見采用本文的方法構(gòu)建井下指紋庫,可使人工采集信號強度的工作量減少50%,且指紋庫定位精度不變。

將文獻[12]的反距離加權(quán)插值法建立文獻[12]指紋庫、文獻[13]的克里金插值算法建立文獻[13]指紋庫、本文提出SA-ABC-Kriging插值算法建立插值井下無線定位指紋庫,三種插值指紋庫采用WKNN算法,設(shè)K為3。經(jīng)過100次調(diào)用測試數(shù)據(jù)庫中100組測試數(shù)據(jù)對三種指紋庫定位運行,得到其定位性能如圖5所示。

從圖5可以看出,文獻[12]指紋庫采用WKNN算法的定位誤差較大,定位精度函數(shù)收斂性差;文獻[13]指紋庫定位性能優(yōu)于文獻[12]指紋庫,但定位精度函數(shù)收斂較慢;而本文指紋庫采用WKNN算法定位精度最優(yōu),定位精度函數(shù)收斂最快。根據(jù)上述實驗結(jié)果,對比三種指紋庫定位誤差數(shù)據(jù),得到定位誤差對比如表3所示。

表3 3種指紋庫定位誤差對比表 單位:m

由表3可知,文獻[12]指紋庫定位平均誤差為3.16 m,文獻[13]指紋庫定位平均誤差為1.98 m,本文指紋庫定位平均誤差為1.59 m;所以本文提出SA-ABC-Kriging插值算法建立插值井下無線定位指紋庫比文獻[12]指紋庫定位精度提升49.68%,比文獻[13]指紋庫定位精度提升19.70%。

6 結(jié)論

本文針對煤礦井下無線指紋定位技術(shù)中離線采集階段構(gòu)建指紋庫,需要大量采集工作的問題,提出了一種采用SA-ABC-Kriging插值算法構(gòu)建井下指紋數(shù)據(jù)庫的方法。在實驗定位區(qū)域內(nèi)采集少量的指紋庫,利用采集指紋數(shù)據(jù)庫構(gòu)建Kriging插值算法模型,通過模擬退火人工蜂群混合優(yōu)化算法對理論變異函數(shù)搜索全局最優(yōu)解,從而建立SA-ABC-Kriging插值算法模型;再利用采集指紋數(shù)據(jù)庫中觀測點的信息數(shù)據(jù)通過插值算法模型估算出預(yù)測點的信息數(shù)據(jù),建立插值數(shù)據(jù)庫,最后將采集指紋數(shù)據(jù)庫和插值指紋數(shù)據(jù)庫生成插值井下無線定位指紋庫,該構(gòu)建方法提升未測量點的插值精度,大幅減少構(gòu)建指紋庫所要指紋的采集量。通過實驗表明,本文方法在插值精度和定位精度上都優(yōu)于傳統(tǒng)Kriging插值算法,在定位精度不變的情況下可將指紋庫采集工作量減少50%。

在接下來工作中,對SA-ABC-Kriging插值算法進行優(yōu)化,提升算法性能,進一步提高插值精度和定位精度。