基于[t]分布變異的飛蛾加權質心定位算法

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

關鍵詞： 無線傳感器網絡; 算法改進; 權值構造; 參數優化; [t]分布變異; 高斯變異

中圖分類號： TN911.1?34; TP212.9" " " " " " " " " 文獻標識碼： 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" 引" 言

無線傳感器網絡作為一種運用于目標追蹤的全新的信息獲取和處理技術，在與定位相關的研究領域有著非常廣闊的發展應用前景。在地理環境監測、軍事偵察、智能醫療相關的技術領域中，無線傳感器網絡更是作為其主要的支撐技術[1]。

在無線傳感器網絡中，目前所提出的定位算法分為基于距離測量和無需距離測量的定位算法。基于距離的定位算法是根據測量到的距離或者角度值的信息進行定位，主要有到達時間（Time of Arrival，TOA）、到達時間差（Time Difference of Arrival，TDOA）、到達角度（Angel of Arrival，AOA）等方法。無需距離測量的定位算法是根據網絡連通性等信息實現節點定位，其主要方法有接收信號強度（Received Signal Strength Indication，RSSI）、質心定位算法、DV?Hop定位算法等。與基于距離的定位算法相比，無需距離測量的定位算法不需要測量節點之間的距離。基于RSSI測距技術因低成本、不需要額外硬件支持而廣泛應用于室內的無線混合定位中[2?3]。

對于基于RSSI的加權質心的混合定位算法，許多學者為了提高定位精度在權值構造上和引入優化算法兩方面對整體定位算法進行優化。文獻[4]提出一種RR?WCL算法，該算法較傳統加權質心定位算法在權值構造方面以未知節點到錨節點距離的比值作為權重來表示相應錨節點對未知節點的影響程度。文獻[5]提出了一種基于PSO?GSA優化的加權質心定位算法，利用PSO?GSA優化算法對未知節點的坐標和定位模型參數進行整體優化。文獻[6]在采集RSSI的優化過程中采用卡爾曼濾波器，并在最后用錨節點的相關信息對四點質心定位算法的結果進行誤差補償。

本文提出一種基于[t]分布混合變異的飛蛾撲火的四點加權質心定位算法，即tMFO?FWCL算法。在加權定位計算過程中利用新的權值構造策略初定位，然后利用這些初步定位坐標通過[t]分布混合變異的飛蛾算法進行優化。仿真結果表明，該算法較傳統的加權質心定位算法、文獻[4?5]和一般的飛蛾撲火定位算法在定位精度上有顯著提升。

1" 加權質心定位算法的改進

1.1" RSSI測距

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

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

式中：[PRd]是距離發送節點[d] m的位置接收到的信號強度的均值，單位為dBm;[Xσ～N（0，σ2）]是信號強度的衰減部分，是一個服從標準正態分布的隨機變量。

1.2" 三角加權質心定位算法

確定了進行定位的節點坐標后，就可以進行加權定位。設三個圓心[A]，[B]，[C]的坐標分別為[（x1，y1）]，[（x2，y2）]，[（x3，y3）]，對應的加權權值分別為[ω1]，[ω2]，[ω3]，通過RSSI所得到的三個圓心到未知節點的距離分別為[d1]，[d2]，[d3]。通常情況下，將錨節點到未知節點通過衰減模型所換算的距離的倒數作為權值，具體的加權質心定位算法公式如下：

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

1.3" 改進的四點加權質心定位算法（FWCL）

傳統加權質心定位算法由于權值構造的不合理性往往使得定位誤差較大。本文在文獻[9]的基礎上對于質心定位公式進行了改進。

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

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

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

式中：[l]為對錨節點進行分組的4組中某一組的3個錨節點距離未知節點的距離;[n]由文獻[9]的結論將權重修正系數設為4。

對每一個分組利用式（3）最終得到4個初步定位坐標值，再次利用這4個初步定位坐標值代入到傳統質心定位算法，得到改進的四組點加權質心定位的坐標值，完成第一輪定位。

在對區域內可以進行定位的未知節點完成了首輪估計后，將定位后的未知節點納入到錨節點中，對上面所提到的不能滿足質心定位條件的未知節點重新定位，依次重復直到對該區域內所有的節點都完成定位。

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

為了解決質心定位算法的本身局限性和傳播模型中[η]值受環境因素的影響這兩個問題，本文在改進加權質心定位算法的權值構造的基礎上，利用[t]分布混合變異的飛蛾撲火算法（tMFO）對定位結果坐標和[η]值進行優化。

2.1" MFO算法

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

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

式中：[n]為飛蛾的數量;[d]為維數。相應的適應度矩陣為：

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

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

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

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

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

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

式中：[N]為火焰數量的最大值;[T]為最大迭代次數;[l]為當前迭代次數。

2.2" [t]分布混合變異

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

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

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

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

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

2.3" 適應度函數構造

設未知節點的最終定位坐標為[（x，y）]，定位后所得到的初步位置坐標為[（x，y）]，[τ]為調節因子，則有：

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

為了便于下面優化，將傳播損耗模型的表達式進行簡化，設[d0]為1 m，[PT-PLd0]為[b]，是常量，[10η]為[a]。簡化后的公式如下：

最終，為了達到整體算法模型的自適應效果進而達到全局最優，這里構造適應度函數為：

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

2.4" TMFO?FWCL算法流程

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

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

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

3） 根據式（17）構造出適應度函數。

4） 比較每只飛蛾的適應度值，取最小值。

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

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

7） 判斷是否達到迭代次數，若達到，輸出最優解，結束算法;否則，返回到步驟2）再次計算。

8） 結束迭代，找出全局的最優解、最優位置和最優參數。

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

式中：[M]為未知節點的個數;[（x′i，y′i）]為未知節點的估計位置;[（x，y）]為未知節點的實際位置;[R]為節點的通信半徑。

3" 仿真分析

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

在上述相同的仿真環境下，分別采用傳統的加權質心定位算法、文獻[4]中的RR?WCL定位算法、文獻[5]中基于PSO?GSA的定位算法、結合飛蛾算法的MFO?FWCL算法和本文tMFO?FWCL算法進行比較，并對其定位結果進行分析。

在MFO的優化算法中，飛蛾數量[N]=50，式（10）中，[b=1]，維度[d=]3，最大迭代次數為100。

3.1" 不同的錨節點數

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

3.2" 不同的通信半徑

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

由圖3可知，當錨節點的數量不變時，5種算法的平均定位誤差都是隨著通信半徑的增大而逐漸減小然后緩慢上升，這是由于起初隨著通信半徑增加會使整個定位環境的網絡連通度提升，因而定位誤差會減小;而后期過大的通信半徑又會使平均定位誤差增加。本文tMFO?FWCL算法在任何半徑的條件下定位性能均優于其他四種算法;經比較本文的算法較文獻[4?5]的算法和MFO?FWCL算法平均定位精度分別提高了39%，26.08%和13.67%。

4" 結" 語

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

參考文獻

[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].計算機工程與設計，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優化的井下加權質心人員定位算法[J].計算機應用研究，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] 潘琢金，劉玉龍，羅振，等.基于卡爾曼濾波的加權補償定位算法[J].計算機工程與設計，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].電測與儀表，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修正加權質心的定位算法[J].計算機系統應用，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.