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

摘" 要： 針對現(xiàn)有無線傳感器網(wǎng)絡(luò)中基于RSSI定位算法受外部環(huán)境影響，在惡劣環(huán)境下定位精度低的問題，提出一種基于[t]分布混合變異飛蛾加權(quán)質(zhì)心定位算法。首先對接收到的信號值進(jìn)行RSSI測距，然后對RSSI測距的值利用改進(jìn)后的四點(diǎn)加權(quán)質(zhì)心定位算法得到預(yù)估計的坐標(biāo)值，最后利用[t]分布混合變異的飛蛾撲火算法對預(yù)估計坐標(biāo)的值和損耗模型參數(shù)進(jìn)行優(yōu)化并得到最終定位坐標(biāo)。仿真結(jié)果表明，該算法比傳統(tǒng)的RSSI定位算法、RR?WCL算法和PSO?GSA算法有更高的定位精度。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò); 算法改進(jìn); 權(quán)值構(gòu)造; 參數(shù)優(yōu)化; [t]分布變異; 高斯變異

中圖分類號： TN911.1?34; TP212.9" " " " " " " " " 文獻(xiàn)標(biāo)識碼： A" " " " " " " " " 文章編號： 1004?373X（2019）21?0001?05

Abstract： Since the localization algorithm based on RSSI （received signal strength indication） is vulnerable to the environment and its location accuracy is low under the condition of severe environment， a weighted centroid location algorithm with t distribution hybrid mutation based moth?flame optimization （tMFO） is proposed in this paper. The RSSI is calculated to get the distance， and then on the basis of RSSI ranging value， the estimated coordinate value is obtained by improved four points weighted centroid algorithm. The estimated coordinate value and loss model parameter are optimized by tMFO algorithm to get the final positioning coordinate. The simulation shows that this algorithm has higher positioning accuracy in comparison with the traditional RSSI algorithm， RR?WCL algorithm and PSO?GSA algorithm.

Keywords： wireless sensor network; algorithm improvement; weight construction; parameter optimization; [t] distribution mutation; Gauss mutation

0" 引" 言

無線傳感器網(wǎng)絡(luò)作為一種運(yùn)用于目標(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ò)連通性等信息實(shí)現(xiàn)節(jié)點(diǎn)定位，其主要方法有接收信號強(qiáng)度（Received Signal Strength Indication，RSSI）、質(zhì)心定位算法、DV?Hop定位算法等。與基于距離的定位算法相比，無需距離測量的定位算法不需要測量節(jié)點(diǎn)之間的距離?；赗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é)點(diǎn)到錨節(jié)點(diǎn)距離的比值作為權(quán)重來表示相應(yīng)錨節(jié)點(diǎn)對未知節(jié)點(diǎn)的影響程度。文獻(xiàn)[5]提出了一種基于PSO?GSA優(yōu)化的加權(quán)質(zhì)心定位算法，利用PSO?GSA優(yōu)化算法對未知節(jié)點(diǎn)的坐標(biāo)和定位模型參數(shù)進(jìn)行整體優(yōu)化。文獻(xiàn)[6]在采集RSSI的優(yōu)化過程中采用卡爾曼濾波器，并在最后用錨節(jié)點(diǎn)的相關(guān)信息對四點(diǎn)質(zhì)心定位算法的結(jié)果進(jìn)行誤差補(bǔ)償。

本文提出一種基于[t]分布混合變異的飛蛾撲火的四點(diǎn)加權(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é)點(diǎn)接收到的錨節(jié)點(diǎn)的RSSI通過相應(yīng)的信號傳播模型對距離作估算。由于信號的發(fā)送天線存在方向性的問題，使得不同傳輸路徑因環(huán)境不同進(jìn)而導(dǎo)致了信號傳播的不規(guī)則性[7]。信號的傳輸方式并非是理想的向四周擴(kuò)散的圓形模型。目前主要的傳輸模型有RIM模型、DOI模型和Logarithmic Attenuation模型。

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

式中：[PRd]是距離發(fā)送節(jié)點(diǎn)[d] m的位置接收到的信號強(qiáng)度的均值，單位為dBm;[Xσ～N（0，σ2）]是信號強(qiáng)度的衰減部分，是一個服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)變量。

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

確定了進(jìn)行定位的節(jié)點(diǎn)坐標(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é)點(diǎn)的距離分別為[d1]，[d2]，[d3]。通常情況下，將錨節(jié)點(diǎn)到未知節(jié)點(diǎn)通過衰減模型所換算的距離的倒數(shù)作為權(quán)值，具體的加權(quán)質(zhì)心定位算法公式如下：

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

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

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

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

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

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

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

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

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

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)化。由于其算法的易實(shí)施性和自身的魯棒性，MFO算法被廣泛應(yīng)用到實(shí)際的最優(yōu)化問題中[10]。

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

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

除了飛蛾矩陣，MFO算法中還需要有與飛蛾矩陣所對應(yīng)的火焰矩陣?；鹧婢仃囃ǔＳ肹F]表示，具體表達(dá)式類比于飛蛾矩陣分別表示為[F]和[OF]。

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

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

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

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

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

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

2.2" [t]分布混合變異

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

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

式中：[?]為點(diǎn)乘;[tIteration]是以MFO算法迭代次數(shù)為自由度的[t]分布。式（13）表示在當(dāng)前飛蛾個體空間的位置上增加了[t]分布隨機(jī)干擾項[M?tIteration]，利用當(dāng)前種群的信息來進(jìn)行變異，并利用算法的迭代次數(shù)作為當(dāng)前變異的[t]分布的自由度。較一般的MFO算法，基于[t]分布混合變異的飛蛾撲火算法利用[t]分布的特點(diǎn)，通過自由度的調(diào)整很好地兼顧了高斯分布和柯西分布的優(yōu)點(diǎn)，進(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é)點(diǎn)的最終定位坐標(biāo)為[（x，y）]，定位后所得到的初步位置坐標(biāo)為[（x，y）]，[τ]為調(diào)節(jié)因子，則有：

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

為了便于下面優(yōu)化，將傳播損耗模型的表達(dá)式進(jìn)行簡化，設(shè)[d0]為1 m，[PT-PLd0]為[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é)點(diǎn)的最初定位坐標(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é)點(diǎn)的個數(shù);[（x′i，y′i）]為未知節(jié)點(diǎn)的估計位置;[（x，y）]為未知節(jié)點(diǎn)的實(shí)際位置;[R]為節(jié)點(diǎn)的通信半徑。

3" 仿真分析

本實(shí)驗平臺采用Matlab 2015a，在100 m[×]100 m的正方形區(qū)域內(nèi)隨機(jī)分布錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的位置。該區(qū)域內(nèi)未知節(jié)點(diǎn)的數(shù)目固定為100個。節(jié)點(diǎn)部署的參數(shù)設(shè)置中錨節(jié)點(diǎn)的GPS誤差為0。其中，發(fā)送信號的功率為0 dBm，參考距離為1 m，距離參考節(jié)點(diǎn)處的信號功率為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é)點(diǎn)數(shù)

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

3.2" 不同的通信半徑

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

由圖3可知，當(dāng)錨節(jié)點(diǎn)的數(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)而得到更高的定位精度。

參考文獻(xiàn)

[1] WANG Z M， ZHENG Y. The study of the weighted centroid localization algorithm based on RSSI [C]// 2014 International Conference on Wireless Communication and Sensor Network. Wuhan： IEEE， 2014： 276?279.

[2] SHI H Y. A new weighted centroid localization algorithm based on RSSI [C]// 2012 IEEE International Conference on Information and Automation. Shenyang： IEEE， 2012： 137?141.

[3] SRETENOVI? J D， KOSTI? S M， SIMI? M I. Experimental analysis of weight?compensated weighted centroid localization algorithm based on RSSI [C]// 2015 12th International Confe?rence on Telecommunication in Modern Satellite， Cable and Broadcasting Services （TELSIKS）. Nis， Serbia： IEEE， 2015： 373?376.

[4] 王亞民，王海英，何佩倫.基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法[J].計算機(jī)工程與設(shè)計，2016，37（11）：2865?2868.

WANG Yamin， WANG Haiying， HE Peilun. Improved weigh?ted centroid localization algorithm based on RSSI [J]. Computer engineering and design， 2016， 37（11）： 2865?2868.

[5] 謝國民，劉葉，付華，等.基于PSO?GSA優(yōu)化的井下加權(quán)質(zhì)心人員定位算法[J].計算機(jī)應(yīng)用研究，2017，34（3）：710?713.

XIE Guomin， LIU Ye， FU Hua， et al. Improved downhole weighted centroid localization algorithm based on PSO?GSA [J]. Application research of computers， 2017， 34（3）： 710?713.

[6] 潘琢金，劉玉龍，羅振，等.基于卡爾曼濾波的加權(quán)補(bǔ)償定位算法[J].計算機(jī)工程與設(shè)計，2017，38（10）：2600?2604.

PAN Zhuojin， LIU Yulong， LUO Zhen， et al. Weighted compensation localization algorithm based on kalman filter [J]. Computer engineering and design， 2017， 38（10）： 2600?2604.

[7] MAGOWE K， GIORGETTI A， KANDEEPAN S， et al. Statistical distribution of position error in weighted centroid localization [C]// 2017 IEEE International Conference on Communications （ICC）. Paris： IEEE， 2017： 1?5.

[8] 王振朝，張琦，張峰.基于RSSI測距的改進(jìn)加權(quán)質(zhì)心定位算法[J].電測與儀表，2014，51（21）：63?66.

WANG Zhenchao， ZHANG Qi， ZHANG Feng. Improved weighted centroid positioning algorithm based on RSSI ranging [J]. Electrical measurement amp; instrumentation， 2014， 51（21）： 63?66.

[9] 白夢如，徐釗，鄭紅黨.基于RSSI修正加權(quán)質(zhì)心的定位算法[J].計算機(jī)系統(tǒng)應(yīng)用，2017，26（2）：124?128.

BAI Mengru， XU Zhao， ZHENG Hongdang. Location algorithm based on RSSI modified weighted centroid [J]. Computer system amp; applications， 2017， 26（2）： 124?128.

[10] MIRJALILI S. Moth?flame optimization algorithm： A novel nature?inspired heuristic paradigm [J]. Knowledge?based systems， 2015， 89： 228?249.

[11] TONG X， CHEN Q X， FAN J， et al. Adaptability verification and application of the t?distribution in short?term load forecasting error analysis [C]// International Conference on Power System Technology. Chengdu： IEEE， 2014： 145?150.