基于巷道分區(qū)和雞群優(yōu)化的井下WSNs定位算法

吳雪敏,張繼榮

(西安郵電大學(xué) 通信與信息工程學(xué)院,陜西 西安 710061)

0 引 言

與地面上環(huán)境不同，巷道是狹長的且有較多分支，同時(shí)，井下環(huán)境高粉塵、高壓強(qiáng)，濕度大。井下的復(fù)雜環(huán)境對(duì)定位算法存在較大制約。傳統(tǒng)有線監(jiān)控系統(tǒng)的布設(shè)成本高、線路易受損且抗干擾能力差，無法滿足井下監(jiān)控的需求。無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)具有低成本、布設(shè)靈活及很強(qiáng)的擴(kuò)展性等特點(diǎn)，可以很好地彌補(bǔ)傳統(tǒng)監(jiān)控系統(tǒng)的缺點(diǎn)，實(shí)現(xiàn)井下環(huán)境的全覆蓋和實(shí)時(shí)監(jiān)測(cè)。目前，針對(duì)井下WSNs監(jiān)測(cè)系統(tǒng)的定位問題已有了一些經(jīng)典算法。如王慧[1]提出一種基于巷道模型和節(jié)點(diǎn)分布模型的定位算法，首先利用高斯消去法篩選用于定位的錨節(jié)點(diǎn)，然后采用最小二乘法估計(jì)待測(cè)節(jié)點(diǎn)的位置，實(shí)現(xiàn)井下精確定位。邢智鵬等人[2]利用LQI(link quality indicator)對(duì)接收信號(hào)強(qiáng)度指示(received signal strength indication,RSSI)數(shù)據(jù)濾波，并估計(jì)信道參數(shù)和環(huán)境參數(shù)，利用環(huán)境參數(shù)修正RSSI的測(cè)距結(jié)果，最后采用最小二乘法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。朱光[3]提出一種改進(jìn)RSSI加權(quán)質(zhì)心定位算法，該算法由RSSI測(cè)距和加權(quán)質(zhì)心定位兩部分組成，提高了算法對(duì)井下環(huán)境的適應(yīng)能力，但精度不夠。余修武等人[4]考慮到隨著時(shí)間的變化，傳感器節(jié)點(diǎn)電池能量越低，導(dǎo)致RSSI值變小，從而影響定位精度的問題，提出一種巷道分區(qū)策略，將巷道分成長度相等的區(qū)域，利用節(jié)點(diǎn)接收到的RSSI值判斷其所屬區(qū)域，并將該區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置，該算法雖實(shí)現(xiàn)簡(jiǎn)單，功耗低，但定位精度同樣較差。

針對(duì)上述情況，本文提出一種基于巷道分區(qū)和雞群優(yōu)化(chicken swarm optimization,CSO)的WSNs井下定位算法，該算法首先對(duì)巷道分區(qū)，根據(jù)未知節(jié)點(diǎn)所屬區(qū)域確定未知節(jié)點(diǎn)的粗略位置；然后，在未知節(jié)點(diǎn)所屬區(qū)域內(nèi)，利用改進(jìn)的CSO算法通過迭代尋優(yōu)以得到未知節(jié)點(diǎn)的精確位置。本文將定位問題轉(zhuǎn)換為優(yōu)化問題，利用群智能算法群體間良好的合作能力，確定未知節(jié)點(diǎn)的位置，以提高井下定位精度。

1 巷道分區(qū)

井下巷道長度一般可達(dá)數(shù)千米(km)，但寬度只有3～5 m，因此，相比于長度，巷道的寬度可以忽略。巷道中錨節(jié)點(diǎn)一般通過人工等距離布署，井下巷道分區(qū)模型如圖1所示。首先，將兩相鄰錨節(jié)點(diǎn)間區(qū)域根據(jù)其水平距離進(jìn)行等距分區(qū)，并將錨節(jié)點(diǎn)間的實(shí)際距離和信號(hào)強(qiáng)度作為已知條件，根據(jù)信號(hào)傳播損耗模型計(jì)算出錨節(jié)點(diǎn)的發(fā)射信號(hào)到達(dá)各個(gè)分區(qū)的接收信號(hào)強(qiáng)度值RSSI；然后，將RSSI值根據(jù)大小分為不同等級(jí)，利用RSSI等級(jí)劃分區(qū)域；最后，根據(jù)節(jié)點(diǎn)接收到的RSSI值所屬等級(jí)確定節(jié)點(diǎn)所在區(qū)域。

圖1 井下巷道分區(qū)模型

上圖為巷道分區(qū)模型，其中，A，B，C，D，E，F(xiàn)為錨節(jié)點(diǎn)，將相鄰錨節(jié)點(diǎn)按其水平距離等分。如圖中，a，b，c，d，e為相鄰錨節(jié)點(diǎn)的中點(diǎn)，假設(shè)任意兩個(gè)相鄰錨節(jié)點(diǎn)間的距離為L，則a點(diǎn)到錨節(jié)點(diǎn)A和B的水平距離均為L/2，a點(diǎn)到錨節(jié)點(diǎn)C的水平距離為3L/2，同理，可得其它各點(diǎn)間的距離。若未知節(jié)點(diǎn)收到來自錨節(jié)點(diǎn)的信號(hào)強(qiáng)度RSSI，則根據(jù)式(1)可得兩者間的距離d，如式(2)所示

RSSI(d)=RSSI(d0)-10δlg(d/d0)+N(0,σ)

(1)

d=10[RSSI(d0)-RSSI(d/d0)+N(0,σ)]/10δ

(2)

式中RSSI(d)為距錨節(jié)點(diǎn)dm處接收信號(hào)的強(qiáng)度值，d0為距離錨節(jié)點(diǎn)1 m，N(0,σ)為正態(tài)分布函數(shù)，δ為路徑衰減因子，它一般在2～6之間取值。

將式(1)簡(jiǎn)化可得

RSSI(d)=RSSI(d0)-10δlg(d)+N(0,σ)

(3)

假設(shè)錨節(jié)點(diǎn)C和未知節(jié)點(diǎn)g收到來自錨節(jié)點(diǎn)A的信號(hào)，則由式(3)可得，節(jié)點(diǎn)C和g的接收信號(hào)強(qiáng)度分別為

RSSI(dAC)=RSSI(d0)-10δlg(dAC)+N(0,σ1)

(4)

RSSI(dAg)=RSSI(d0)-10δlg(dAg)+N(0,σ2)

(5)

由式(4)和式(5)可得

RSSI(dAg)=RSSI(dAC)-10δlg(dAg/dAC)+N(0,σ)

(6)

由于N(0,σ)很小，可將其省略，簡(jiǎn)化后的公式為

RSSI(dAg)=RSSI(dAC)-10δlg(dAg/dAC)

(7)

由式(7)可得點(diǎn)a，B，b接收到節(jié)點(diǎn)A的信號(hào)強(qiáng)度為

(8)

式中 顯然a點(diǎn)的RSSI值最大，B點(diǎn)次之，b點(diǎn)最小。因此，可根據(jù)信號(hào)接收強(qiáng)度劃分區(qū)域，若未知節(jié)點(diǎn)g接收到來自錨節(jié)點(diǎn)A的信號(hào)強(qiáng)度RSSI(dAg)≥RSSI(dAa)，則記為一等強(qiáng)度A1；若RSSI(dAB)≤RSSI(dAg)≤RSSI(dAa)，則記為二等強(qiáng)度A2；若RSSI(dAb)≤RSSI(dAg)≤RSSI(dAB)，則記為三等強(qiáng)度A3，若小于RSSI(dAb)，不記。

根據(jù)上述方法，可對(duì)分區(qū)進(jìn)行等級(jí)編碼，如圖1中未知節(jié)點(diǎn)g，根據(jù)其接收到的信號(hào)強(qiáng)度，可對(duì)其位置區(qū)域編碼為A2B1C3。同理，可將巷道中其他分區(qū)編碼為A3B1C2，B2C1D3，B3C1D2等，不同編碼對(duì)應(yīng)不同的接收信號(hào)強(qiáng)度以及不同的區(qū)域。未知節(jié)點(diǎn)可根據(jù)自身接收到周圍錨節(jié)點(diǎn)的信號(hào)強(qiáng)度和對(duì)應(yīng)的編碼判斷其所屬區(qū)域。

2 CSO算法與改進(jìn)

2.1 CSO算法

CSO算法是Meng X等人根據(jù)雞群覓食行為提出的一種群智能優(yōu)化算法[5]。該算法根據(jù)雄雞個(gè)數(shù)將雞群劃分為若干子群，雌雞和小雞隨機(jī)加入各子群中。其中，雄雞有較好的適應(yīng)度值，可以在更大空間內(nèi)尋找食物；雌雞的適應(yīng)度值次之，雌雞追隨其所在子群中的雄雞尋找食物；小雞的適應(yīng)度值最差，小雞跟隨雞媽媽尋找食物，雞媽媽由子群中的雌雞個(gè)體中隨機(jī)產(chǎn)生并與小雞隨機(jī)組成母子關(guān)系，每只雞媽媽可以有多只小雞。進(jìn)化G代后，重新分配雞群的等級(jí)制度。雞群中不同等級(jí)個(gè)體的位置更新如下。

雄雞位置更新公式

(9)

雌雞位置更新公式

(10)

式中rand為[0,1]間的隨機(jī)數(shù)，r1為第i只雌雞所在子群中的雄雞個(gè)體，r2為除r1之外的整個(gè)雞群中雄雞和雌雞的任意個(gè)體。

小雞位置更新公式

(11)

式中m為雞媽媽，F(xiàn)L為跟隨系數(shù)，取值范圍為[0,2]。

2.2 基于行為反饋的雄雞位置更新

CSO中，雄雞相比于雌雞和小雞，具有最優(yōu)的適應(yīng)度值。在同一子群中，雌雞的位置更新受雄雞行為的影響，小雞的位置更新受雌雞行為的影響。由此可得，雄雞的行為影響著整個(gè)雞群的行為，一旦雄雞陷入局部最優(yōu)將使整個(gè)雞群易陷入局部最優(yōu)。因此，雄雞是否可以避免陷入局部最優(yōu)是整個(gè)優(yōu)化過程的關(guān)鍵。

分析式(9)可知，假如雄雞擁有更優(yōu)的適應(yīng)度值，則它的搜索范圍更大。然而，根據(jù)CSO優(yōu)化規(guī)則，當(dāng)個(gè)體的適應(yīng)度值更優(yōu)時(shí)，表明其距離食物更近，此時(shí)應(yīng)該在小范圍內(nèi)搜索才更可能找到食物。因此，擁有更優(yōu)適應(yīng)度值的雄雞，其搜索范圍應(yīng)該更小。同時(shí)，雄雞利用高斯隨機(jī)搜索策略更新自身位置，沒有考慮與其他個(gè)體的信息交換。在整個(gè)雞群中，一方面，由于雌雞的個(gè)數(shù)最多，在CSO的精度及尋優(yōu)速度方面有重要的作用[6]；另一方面，雌雞是連接雄雞和小雞的紐帶，在雞群中起承上啟下的作用[7]。因此，本文在雄雞的位置更新中加入雌雞行為的反饋信息，使其不易陷入局部最優(yōu)。改進(jìn)的雄雞位置更新公式如下

(12)

(13)

S=exp(fmean-fi)

(14)

式中S為反饋系數(shù)，fmean為跟隨該雄雞的所有雌雞個(gè)體適應(yīng)度值的均值，S越大表明雄雞與雌雞的適應(yīng)度值相差越大，即雄雞越偏離雌雞群體。

式(12)～式(14)表明雄雞的適應(yīng)度值越小，即雄雞具有更優(yōu)的適應(yīng)度值時(shí)，σ2越小，可以保證雄雞在小范圍內(nèi)快速找到食物。同理，當(dāng)雄雞適應(yīng)度值越大時(shí)，為了快速找到食物，其會(huì)在較大范圍內(nèi)搜索。同時(shí)，S≥1，當(dāng)雄雞越偏離雌雞群體時(shí)，S越大，此時(shí)會(huì)增大雄雞的搜索步長，當(dāng)雄雞越接近雌雞群體時(shí)，S的值趨于1，此時(shí)雄雞的局部搜索能力較強(qiáng)。

2.3 差分變異

CSO算法中雞群個(gè)體的多樣性會(huì)隨著算法不斷迭代而下降，導(dǎo)致算法容易過早收斂陷入局部最優(yōu)解。為改進(jìn)這一問題，引入了差分進(jìn)化(differential evolution，DE)算法中的差分變異思想，當(dāng)算法陷入停滯狀態(tài)時(shí)，在雞群中隨機(jī)選取20 %的個(gè)體進(jìn)行變異操作以達(dá)到增加種群多樣性的目的。變異公式如下

(15)

改進(jìn)CSO算法的具體實(shí)現(xiàn)流程圖如圖2。

圖2 改進(jìn)CSO算法流程圖

3 井下節(jié)點(diǎn)定位算法

3.1 適應(yīng)度函數(shù)設(shè)計(jì)

在WSNs定位系統(tǒng)中，假設(shè)未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)坐標(biāo)分別為(x,y)和(xi,yi)，i=1,2,3,…，n，則未知節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)間的距離di可表示為

(16)

因此，WSNs節(jié)點(diǎn)定位算法的適應(yīng)度函數(shù)可以定義為

(17)

通過上式將定位問題轉(zhuǎn)化為求解最小值問題，CSO算法將每個(gè)可能解看作雞群中個(gè)體的位置，計(jì)算每只個(gè)體的適應(yīng)度值，通過不斷迭代尋優(yōu)，最終獲得適應(yīng)度值最優(yōu)的個(gè)體，其位置即為未知節(jié)點(diǎn)坐標(biāo)。

3.2 節(jié)點(diǎn)定位

經(jīng)過巷道分區(qū)后可以確定未知節(jié)點(diǎn)所在區(qū)域，在該區(qū)域中，利用改進(jìn)的CSO進(jìn)行全局搜索，以實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的精確定位。通過計(jì)算節(jié)點(diǎn)的定位誤差error來評(píng)價(jià)本文算法的定位效果。公式如下

(18)

式中 (xi,yi)和(x′i,y′i)分別為未知節(jié)點(diǎn)i的實(shí)際坐標(biāo)和計(jì)算坐標(biāo)，N為未知節(jié)點(diǎn)總數(shù)。

井下節(jié)點(diǎn)定位的具體步驟為:1)在WSNs區(qū)域內(nèi)部署節(jié)點(diǎn)，并設(shè)定通信半徑R；2)按照本文第1節(jié)描述對(duì)巷道進(jìn)行分區(qū)；3)根據(jù)未知節(jié)點(diǎn)接收信號(hào)強(qiáng)度確定其所屬區(qū)域；4)利用本文改進(jìn)的CSO算法迭代尋優(yōu)，獲得未知節(jié)點(diǎn)的坐標(biāo)；5)利用式(18)計(jì)算本文定位算法的定位誤差error；6)輸出結(jié)果，算法結(jié)束。

3.3 仿真分析

通過MATLAB 2015b對(duì)本文算法與文獻(xiàn)[3]中改進(jìn)RSSI加權(quán)質(zhì)心定位算法以及文獻(xiàn)[4]中RSSP算法進(jìn)行仿真對(duì)比。假設(shè)實(shí)驗(yàn)在圖1所示巷道中進(jìn)行，未知節(jié)點(diǎn)為50個(gè)，節(jié)點(diǎn)通信半徑為40 m，雞群總數(shù)為50，最大迭代次數(shù)為100次。各算法取重復(fù)50次的均值作為最終結(jié)果。定位系統(tǒng)的節(jié)點(diǎn)分布如圖3所示。

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

1)三種算法定位誤差對(duì)比

為對(duì)比本文算法、RSSI加權(quán)質(zhì)心算法以及RSSP算法的定位誤差，對(duì)三種算法進(jìn)行仿真分析，結(jié)果如圖4所示。

圖4 三種算法定位誤差對(duì)比

由圖4可知，三種算法中，RSSP算法未知節(jié)點(diǎn)的最大定位誤差為5.643 m，改進(jìn)RSSI加權(quán)質(zhì)心算法的最大定位誤差為4.948 m，本文算法的最大定位誤差為 2.903 m，明顯小于另外兩種算法，并且文獻(xiàn)RSSP算法的定位誤差最大。表明本文算法相比其他兩種算法對(duì)未知節(jié)點(diǎn)的定位更準(zhǔn)確，具有更高的定位精度，更適用于井下環(huán)境。

2)錨節(jié)點(diǎn)間距對(duì)定位精度的影響

令錨節(jié)點(diǎn)間距分別為20,25,30,35,40 m，其他參數(shù)設(shè)置不變，RSSP算法、改進(jìn)RSSI加權(quán)質(zhì)心算法以及本文算法的定位誤差如圖5所示。

圖5 錨節(jié)點(diǎn)間距對(duì)定位精度的影響

分析三條曲線可知，當(dāng)錨節(jié)點(diǎn)間距從20 m增加到40 m時(shí)，三種算法的定位誤差分別從 2.236,1.523,0.622 m增加到了 5.213,2.587,1.043 m。這表明，錨節(jié)點(diǎn)間距對(duì)三種算法的定位精度有不同大小的影響，RSSP算法在不同的錨節(jié)點(diǎn)間距處定位誤差變化較大，且定位誤差隨著錨節(jié)點(diǎn)間距的增加而增大，相比而言，改進(jìn)的RSSI加權(quán)質(zhì)心算法和本文算法的定位誤差受錨節(jié)點(diǎn)間距的影響較小，在錨節(jié)點(diǎn)間距不同的情況下，定位誤差波動(dòng)不大。同時(shí)，對(duì)比錨節(jié)點(diǎn)間距相同情況下三種算法的定位誤差可得，本文算法的定位誤差始終最小，因此，本文算法不但對(duì)錨節(jié)點(diǎn)密度要求較小，且具有更高的定位精度，即本文算法實(shí)現(xiàn)井下定位具有更好的效果。

3)測(cè)距誤差對(duì)定位精度的影響

令RSSI測(cè)距公式中的正太分布函數(shù)標(biāo)準(zhǔn)差 的值分別等于1,1.5,2,2.5,3,3.5,4，其他參數(shù)不變，分別對(duì)三種算法進(jìn)行仿真，結(jié)果如圖6所示。

圖6 測(cè)距誤差對(duì)定位精度的影響

如圖6所示，隨著σ的增加，RSSP算法、改進(jìn)RSSI加權(quán)質(zhì)心算法以及本文算法的定位誤差變化都較小，這表明三種算法都在較好的程度上克服了測(cè)距不準(zhǔn)確對(duì)定位精度的影響。且總體來說，相比于RSSP算法和改進(jìn)RSSI加權(quán)質(zhì)心算法，本文算法具有更好的定位精度。

4 結(jié) 論

本文將定位問題轉(zhuǎn)化為尋優(yōu)問題，通過節(jié)點(diǎn)的RSSI值判斷其所屬區(qū)域，然后利用改進(jìn)的CSO算法實(shí)現(xiàn)節(jié)點(diǎn)定位，最后通過實(shí)驗(yàn)證明了本文算法的有效性和優(yōu)越性。