基于t分布變異的飛蛾加權(quán)質(zhì)心定位算法

毛永毅，張 旸，王曉甜

（1.西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安 710121；2.西安郵電大學(xué)科研處，陜西西安 710121）

0 引 言

無線傳感器網(wǎng)絡(luò)作為一種運用于目標(biāo)追蹤的全新的信息獲取和處理技術(shù)，在與定位相關(guān)的研究領(lǐng)域有著非常廣闊的發(fā)展應(yīng)用前景。在地理環(huán)境監(jiān)測、軍事偵察、智能醫(yī)療相關(guān)的技術(shù)領(lǐng)域中，無線傳感器網(wǎng)絡(luò)更是作為其主要的支撐技術(shù)[1]。

在無線傳感器網(wǎng)絡(luò)中，目前所提出的定位算法分為基于距離測量和無需距離測量的定位算法?；诰嚯x的定位算法是根據(jù)測量到的距離或者角度值的信息進(jìn)行定位，主要有到達(dá)時間（Time of Arrival，TOA）、到達(dá)時間差（Time Difference of Arrival，TDOA）、到達(dá)角度（Angel of Arrival，AOA）等方法。無需距離測量的定位算法是根據(jù)網(wǎng)絡(luò)連通性等信息實現(xiàn)節(jié)點定位，其主要方法有接收信號強度（Received Signal Strength Indication，RSSI）、質(zhì)心定位算法、DV-Hop 定位算法等。與基于距離的定位算法相比，無需距離測量的定位算法不需要測量節(jié)點之間的距離?；赗SSI 測距技術(shù)因低成本、不需要額外硬件支持而廣泛應(yīng)用于室內(nèi)的無線混合定位中[2-3]。

對于基于RSSI 的加權(quán)質(zhì)心的混合定位算法，許多學(xué)者為了提高定位精度在權(quán)值構(gòu)造上和引入優(yōu)化算法兩方面對整體定位算法進(jìn)行優(yōu)化。文獻(xiàn)[4]提出一種RR-WCL 算法，該算法較傳統(tǒng)加權(quán)質(zhì)心定位算法在權(quán)值構(gòu)造方面以未知節(jié)點到錨節(jié)點距離的比值作為權(quán)重來表示相應(yīng)錨節(jié)點對未知節(jié)點的影響程度。文獻(xiàn)[5]提出了一種基于PSO-GSA 優(yōu)化的加權(quán)質(zhì)心定位算法，利用PSO-GSA 優(yōu)化算法對未知節(jié)點的坐標(biāo)和定位模型參數(shù)進(jìn)行整體優(yōu)化。文獻(xiàn)[6]在采集RSSI 的優(yōu)化過程中采用卡爾曼濾波器，并在最后用錨節(jié)點的相關(guān)信息對四點質(zhì)心定位算法的結(jié)果進(jìn)行誤差補償。

本文提出一種基于t分布混合變異的飛蛾撲火的四點加權(quán)質(zhì)心定位算法，即tMFO-FWCL 算法。在加權(quán)定位計算過程中利用新的權(quán)值構(gòu)造策略初定位，然后利用這些初步定位坐標(biāo)通過t分布混合變異的飛蛾算法進(jìn)行優(yōu)化。仿真結(jié)果表明，該算法較傳統(tǒng)的加權(quán)質(zhì)心定位算法、文獻(xiàn)[4-5]和一般的飛蛾撲火定位算法在定位精度上有顯著提升。

1 加權(quán)質(zhì)心定位算法的改進(jìn)

1.1 RSSI 測距

RSSI 測距是基于測距定位的第一個步驟，利用未知節(jié)點接收到的錨節(jié)點的RSSI 通過相應(yīng)的信號傳播模型對距離作估算。由于信號的發(fā)送天線存在方向性的問題，使得不同傳輸路徑因環(huán)境不同進(jìn)而導(dǎo)致了信號傳播的不規(guī)則性[7]。信號的傳輸方式并非是理想的向四周擴散的圓形模型。目前主要的傳輸模型有RIM 模型、DOI 模型和Logarithmic Attenuation 模型。

Logarithmic Attenuation 模型是一種最典型的不規(guī)則信號傳播模型，具體表達(dá)式如下：

式中：PR(d)是距離發(fā)送節(jié)點dm 的位置接收到的信號強度的均值，單位為dBm；Xσ～N(0,σ2)是信號強度的衰減部分，是一個服從標(biāo)準(zhǔn)正態(tài)分布的隨機變量。

1.2 三角加權(quán)質(zhì)心定位算法

確定了進(jìn)行定位的節(jié)點坐標(biāo)后，就可以進(jìn)行加權(quán)定位。設(shè)三個圓心A，B，C的坐標(biāo)分別為(x1,y1)，(x2,y2)，(x3,y3)，對應(yīng)的加權(quán)權(quán)值分別為ω1，ω2，ω3，通過RSSI 所得到的三個圓心到未知節(jié)點的距離分別為d1，d2，d3。通常情況下，將錨節(jié)點到未知節(jié)點通過衰減模型所換算的距離的倒數(shù)作為權(quán)值，具體的加權(quán)質(zhì)心定位算法公式如下：

式中權(quán)值更加充分地利用節(jié)點測量信號強度和傳播模型的信息，并且完善了權(quán)值的決定權(quán)，防止了過度修正[8]。

1.3 改進(jìn)的四點加權(quán)質(zhì)心定位算法（FWCL）

傳統(tǒng)加權(quán)質(zhì)心定位算法由于權(quán)值構(gòu)造的不合理性往往使得定位誤差較大。本文在文獻(xiàn)[9]的基礎(chǔ)上對于質(zhì)心定位公式進(jìn)行了改進(jìn)。

在節(jié)點選擇中，將得到的RSSI值根據(jù)相應(yīng)的衰減模型計算出未知節(jié)點到各個錨節(jié)點的距離。按照距離值從大到小的順序篩選出該未知節(jié)點所接收到的RSSI 值最大的4 個值。對于不能找出最近的4 個錨節(jié)點的未知節(jié)點，暫不進(jìn)行定位。

對于上面能夠找出最近的4 個錨節(jié)點的未知節(jié)點，對這4 個錨節(jié)點通過進(jìn)行排列組合分成4 組，對于每組中的3 個錨節(jié)點利用改進(jìn)的加權(quán)質(zhì)心定位算法求出用于下一步定位的定位節(jié)點。改進(jìn)加權(quán)質(zhì)心定位公式如下：

式中：xi，yi為上步驟以排列組合后其中一組的3 個錨節(jié)點以錨節(jié)點坐標(biāo)為圓心，以通信半徑為半徑所畫出3個圓的交點的坐標(biāo)值，如圖1 所示。

圖1 加權(quán)質(zhì)心定位算法的模型圖Fig.1 Model diagram of weighted centroid localiazation algorithm

本文將權(quán)重ωi構(gòu)造為：

其中：

式中：l為對錨節(jié)點進(jìn)行分組的4 組中某一組的3 個錨節(jié)點距離未知節(jié)點的距離；n由文獻(xiàn)[9]的結(jié)論將權(quán)重修正系數(shù)設(shè)為4。

對每一個分組利用式（3）最終得到4 個初步定位坐標(biāo)值，再次利用這4 個初步定位坐標(biāo)值代入到傳統(tǒng)質(zhì)心定位算法，得到改進(jìn)的四組點加權(quán)質(zhì)心定位的坐標(biāo)值，完成第一輪定位。

在對區(qū)域內(nèi)可以進(jìn)行定位的未知節(jié)點完成了首輪估計后，將定位后的未知節(jié)點納入到錨節(jié)點中，對上面所提到的不能滿足質(zhì)心定位條件的未知節(jié)點重新定位，依次重復(fù)直到對該區(qū)域內(nèi)所有的節(jié)點都完成定位。

2 基于t 分布變異的飛蛾撲火算法

為了解決質(zhì)心定位算法的本身局限性和傳播模型中η值受環(huán)境因素的影響這兩個問題，本文在改進(jìn)加權(quán)質(zhì)心定位算法的權(quán)值構(gòu)造的基礎(chǔ)上，利用t分布混合變異的飛蛾撲火算法（tMFO）對定位結(jié)果坐標(biāo)和η值進(jìn)行優(yōu)化。

2.1 MFO算法

MFO算法是一種新型的仿生群智能優(yōu)化算法，該算法對飛蛾橫向定位的方式進(jìn)行模擬，并仿照飛蛾螺旋飛行的軌跡方式，利用螺旋函數(shù)模型對其進(jìn)行更新進(jìn)而對結(jié)果進(jìn)行優(yōu)化。由于其算法的易實施性和自身的魯棒性，MFO算法被廣泛應(yīng)用到實際的最優(yōu)化問題中[10]。

在MFO算法中，飛蛾作為候選解。飛蛾的位置矢量作為問題的變量。飛蛾通過改變位置矢量來實現(xiàn)在指定維數(shù)中的移動，其中飛蛾矩陣用M表示：

式中：n為飛蛾的數(shù)量；d為維數(shù)。相應(yīng)的適應(yīng)度矩陣為：

除了飛蛾矩陣，MFO算法中還需要有與飛蛾矩陣所對應(yīng)的火焰矩陣。火焰矩陣通常用F表示，具體表達(dá)式類比于飛蛾矩陣分別表示為F和OF。

飛蛾和火焰均為候選解，它們的區(qū)別在于每次迭代中位置的更新方式。在解空間中，飛蛾是移動的實際主體，火焰為目前獲得的最優(yōu)值，可以作為搜索完成的標(biāo)志。

完成初始化后，使用下面的公式來更新飛蛾的位置：

式中：Fj表示第j個火焰；M i表示第i個飛蛾；S是螺旋線函數(shù)，其表達(dá)式如下：

上述螺旋線模擬了飛蛾的飛行路徑，并確定了飛蛾相對于火焰的下一個位置。其中：Di表示第i個飛蛾到第j個火焰的距離；t為[?1，1]的隨機數(shù)；b為常數(shù)。Di的計算方法如下：

為了使算法以較快的速度收斂，利用自適應(yīng)火焰數(shù)量更新機制，在迭代的過程中自適應(yīng)地減少火焰數(shù)目。

式中：N為火焰數(shù)量的最大值；T為最大迭代次數(shù)；l為當(dāng)前迭代次數(shù)。

2.2 t分布混合變異

t分布的曲線具有左右對稱的特點，并受自由度參數(shù)n的影響。當(dāng)n=1 時，t分布的曲線與柯西分布曲線一致；當(dāng)n＞30 時，t分布曲線與正態(tài)分布開始重合；當(dāng)n趨于無窮時，t分布曲線和高斯分布曲線開始接近。

飛蛾算法搜索時采用螺旋線波動模擬搜索模式，其螺旋線的相位采用隨機游動的方式進(jìn)行更迭，但是這種搜索方式在靠近極值點的情況時易受極值點干擾，最終導(dǎo)致被極值點吸引進(jìn)而影響最終定位結(jié)果。而上述的t分布隨著自由度的變換可以在柯西分布和高斯分布之間切換，高斯分布具有很好的全局開發(fā)能力；柯西分布具有很好的局部開發(fā)能力[11]，因此可以利用t分布混合變異對飛蛾算法進(jìn)行改進(jìn)。本文對飛蛾的狀態(tài)進(jìn)行t分布變異：

式中：?為點乘；t(Iteration) 是以MFO算法迭代次數(shù)為自由度的t分布。式（13）表示在當(dāng)前飛蛾個體空間的位置上增加了t分布隨機干擾項M?t(Iteration) ，利用當(dāng)前種群的信息來進(jìn)行變異，并利用算法的迭代次數(shù)作為當(dāng)前變異的t分布的自由度。較一般的MFO算法，基于t分布混合變異的飛蛾撲火算法利用t分布的特點，通過自由度的調(diào)整很好地兼顧了高斯分布和柯西分布的優(yōu)點，進(jìn)而將算法的全局探索能力和局部探索能力進(jìn)行了很好的整合。

為了使算法的解進(jìn)一步優(yōu)化，這里對每一次迭代中飛蛾的最優(yōu)位置進(jìn)行高斯變異處理以提高解的質(zhì)量。

Φ是與M同階的高斯分布矩陣。因此，整體算法的變異策略就是在飛蛾算法的每一次迭代過程中，對于最優(yōu)飛蛾位置矩陣進(jìn)行高斯最優(yōu)變異，對于飛蛾最優(yōu)位置之外的其他飛蛾采用t分布變異，這樣有利于整個飛蛾的位置跳出局部最優(yōu)解進(jìn)行全局開發(fā)。

2.3 適應(yīng)度函數(shù)構(gòu)造

設(shè)未知節(jié)點的最終定位坐標(biāo)為(x,y)，定位后所得到的初步位置坐標(biāo)為(x′,y′)，τ為調(diào)節(jié)因子，則有：

這里為了增加求解效率，τ的取值為10。

為了便于下面優(yōu)化，將傳播損耗模型的表達(dá)式進(jìn)行簡化，設(shè)d0為1 m，PT-PL(d0)為b，是常量，10η為a。簡化后的公式如下：

最終，為了達(dá)到整體算法模型的自適應(yīng)效果進(jìn)而達(dá)到全局最優(yōu)，這里構(gòu)造適應(yīng)度函數(shù)為：

代入前面算法的初步定位坐標(biāo)，可將式（17）右邊改寫為：

2.4 TMFO-FWCL 算法流程

TMFO-FWCL 算法流程具體如下：

1）利用FWCL 算法得到未知節(jié)點的最初定位坐標(biāo)，作為飛蛾矩陣。

2）初始化飛蛾矩陣和火焰矩陣。

3）根據(jù)式（17）構(gòu)造出適應(yīng)度函數(shù)。

4）比較每只飛蛾的適應(yīng)度值，取最小值。

5）利用式（10）更新飛蛾的位置和火焰矩陣。

6）利用上述t分布混合變異策略對每次迭代過程中的最優(yōu)飛蛾和普通飛蛾分布進(jìn)行不同的變異。再次比較，取最優(yōu)位置賦給火焰矩陣。

7）判斷是否達(dá)到迭代次數(shù)，若達(dá)到，輸出最優(yōu)解，結(jié)束算法；否則，返回到步驟2）再次計算。

8）結(jié)束迭代，找出全局的最優(yōu)解、最優(yōu)位置和最優(yōu)參數(shù)。

9）計算平均定位誤差，具體方法如下：

式中：M為未知節(jié)點的個數(shù)為未知節(jié)點的估計位置；(x,y)為未知節(jié)點的實際位置；R為節(jié)點的通信半徑。

3 仿真分析

本實驗平臺采用Matlab 2015a，在100 m×100 m 的正方形區(qū)域內(nèi)隨機分布錨節(jié)點和未知節(jié)點的位置。該區(qū)域內(nèi)未知節(jié)點的數(shù)目固定為100 個。節(jié)點部署的參數(shù)設(shè)置中錨節(jié)點的GPS 誤差為0。其中，發(fā)送信號的功率為0 dBm，參考距離為1 m，距離參考節(jié)點處的信號功率為55 dBm，初始路徑損耗指數(shù)η為4，所附加的高斯白噪聲均值為0，方差為4。

在上述相同的仿真環(huán)境下，分別采用傳統(tǒng)的加權(quán)質(zhì)心定位算法、文獻(xiàn)[4]中的RR-WCL 定位算法、文獻(xiàn)[5]中基于PSO-GSA 的定位算法、結(jié)合飛蛾算法的MFO-FWCL算法和本文tMFO-FWCL 算法進(jìn)行比較，并對其定位結(jié)果進(jìn)行分析。

在MFO 的優(yōu)化算法中，飛蛾數(shù)量N=50，式（10）中，b=1，維度d=3，最大迭代次數(shù)為100。

3.1 不同的錨節(jié)點數(shù)

圖2 是隨著錨節(jié)點數(shù)量的增加，5 種定位算法的平均誤差變化曲線。

圖2 不同錨節(jié)點數(shù)的定位誤差曲線Fig.2 Positioning error curves from different numbers of anchor nodes

由圖2 可知，當(dāng)通信半徑一樣時，隨著錨節(jié)點數(shù)量的逐漸增加，5 種定位算法的平均定位誤差均逐漸減小，這是因為錨節(jié)點密度的增加使得可定位的未知節(jié)點數(shù)目增加所致。本文對于權(quán)值改進(jìn)的MFO-FWCL 算法的誤差低于文獻(xiàn)[5]的PSO-GSA 算法的誤差，再次改進(jìn)后，本文tMFO-FWCL 算法平均定位誤差在各個節(jié)點處均低于PSO-GSA 算法和MFO-FWCL 算法。平均誤差分別相對提高了26.33%和12.67%。

3.2 不同的通信半徑

當(dāng)錨節(jié)點個數(shù)一定時，隨著通信半徑的增加，繪制5 種定位算法的平均誤差曲線，如圖3 所示。

圖3 不同通信半徑的定位誤差曲線Fig.3 Positioning error curves at different communication radius

由圖3 可知，當(dāng)錨節(jié)點的數(shù)量不變時，5 種算法的平均定位誤差都是隨著通信半徑的增大而逐漸減小然后緩慢上升，這是由于起初隨著通信半徑增加會使整個定位環(huán)境的網(wǎng)絡(luò)連通度提升，因而定位誤差會減??；而后期過大的通信半徑又會使平均定位誤差增加。本文tMFO-FWCL 算法在任何半徑的條件下定位性能均優(yōu)于其他四種算法；經(jīng)比較本文的算法較文獻(xiàn)[4-5]的算法和MFO-FWCL 算法平均定位精度分別提高了39%，26.08%和13.67%。

4 結(jié) 語

為了解決質(zhì)心定位算法定位精度差和MFO算法本身局限性的問題，在改進(jìn)加權(quán)質(zhì)心定位算法的基礎(chǔ)上，采用基于t分布混合變異飛蛾撲火算法模型對定位坐標(biāo)值進(jìn)行優(yōu)化，提高了定位精度。結(jié)果表明，tMFO-FWCL算法與一般的RR-WCL 算法、PSO-GSA 算法以及改進(jìn)的MFO-FWCL 算法相比，能更有效地擺脫局部最優(yōu)解，進(jìn)而得到更高的定位精度。