混沌粒子群雞群融合優(yōu)化的RSSI 質(zhì)心定位算法

王改云，陸家卓，焦 傲，郭智超，張 琦

（桂林電子科技大學(xué)電子工程與自動化學(xué)院，廣西桂林 541004）

0 概述

物聯(lián)網(wǎng)被認(rèn)為是繼計算機、互聯(lián)網(wǎng)后世界信息產(chǎn)業(yè)的第三次浪潮，其將傳感器技術(shù)應(yīng)用于環(huán)境監(jiān)測、智慧農(nóng)業(yè)和智慧城市等領(lǐng)域［1-2］。在無線傳感網(wǎng)絡(luò)應(yīng)用場景中，如果傳感節(jié)點不能獲知它們的位置信息，則這些傳感器所感知的數(shù)據(jù)也將沒有意義［3-5］。因此，研究無線傳感網(wǎng)絡(luò)的定位技術(shù)顯得尤為重要［6］。

無線傳感網(wǎng)的定位方式分為測距定位和非測距定位兩種類型［7-8］。其中，TOA 算法［9］、三邊定位算法、RSSI 算法和TDOA［10］算法屬于常見的測距定位算法，而APIT 算法、質(zhì)心定位算法和DV-Hop 算法則屬于非測距定位算法［11］。為了解決基礎(chǔ)定位算法精度較差且實用性不高的問題，國內(nèi)外研究人員針對上述算法進(jìn)行了深入的研究。在國外，ZONG 等人分析了兩種環(huán)境擾動對RSSI 值的影響，利用卡爾曼濾波對RSSI 值進(jìn)行預(yù)處理，并提出一種三角中心定位算法。LOGANATHAN 等人［13］提出一種利用基于Zigbee 的接收信號強度指示器（RSSI）和數(shù)字測定儀來提高移動節(jié)點室內(nèi)定位的新技術(shù)。通過改進(jìn)路徑損耗傳播模型和凸搜索優(yōu)化每種定位技術(shù)的加權(quán)參數(shù)來更準(zhǔn)確地預(yù)測移動節(jié)點的坐標(biāo)，使得定位性能得到大幅提升。BYRNE 等人［14］在RSSI 的基礎(chǔ)上優(yōu)化了室內(nèi)定位算法，將其應(yīng)用于室內(nèi)定位并進(jìn)行優(yōu)化，結(jié)果表明，該算法在室內(nèi)應(yīng)用中具有更高的定位精度。國內(nèi)研究人員潘琢金等人［15］利用卡爾曼濾波器來優(yōu)化RSSI 的采集過程，并用錨節(jié)點的相關(guān)信息對四點質(zhì)心定位算法的結(jié)果進(jìn)行誤差補償。路澤忠等人［16］將對RSSI 值解算的距離值的倒數(shù)和作為權(quán)重，得出修正參數(shù)對精度進(jìn)行了修正。張鴻洋等人［17］分析了節(jié)點動態(tài)與距離的關(guān)系，主動刪除孤立節(jié)點并確定權(quán)重，進(jìn)一步提高定位精度。汪晨等人［18］利用信號識別強度得到的參考節(jié)點的距離和位置信息作為人工魚群算法的適應(yīng)度函數(shù)，達(dá)到優(yōu)化求解過程的目的，從而降低定位誤差。

不同定位算法在面對各種類型的應(yīng)用環(huán)境時，需要設(shè)計出不同的改進(jìn)方案。本文利用混沌搜索的隨機性、遍歷性和雞群算法（CSO）的多種群性，對粒子群優(yōu)化（PSO）算法求解過程進(jìn)行完善，結(jié)合RSSI測距的低成本、低功耗以及計算量小的優(yōu)點優(yōu)化傳統(tǒng)質(zhì)心定位算法，并提出基于混沌粒子群雞群融合算法的RSSI 質(zhì)心定位算法。

1 混沌粒子群雞群的融合算法

1.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法是一種原理簡單、搜索速度快的群體智能算法，其求解最優(yōu)值的優(yōu)化思想是模擬群鳥覓食的過程。假設(shè)在解空間對速度與位置的初始值都是隨機分配的M個粒子進(jìn)行空間維數(shù)為D的最優(yōu)搜索。粒子群算法的思路是通過個體極值pbest 與全局極值gbest 不斷地修正粒子的位置和速度，使得粒子不斷向最優(yōu)解靠攏。若迭代次數(shù)為K，則粒子的速度V與位置X的更新為：

其中，w為慣性權(quán)重，r1和r2為分布在［0，1］區(qū)間的隨機數(shù)，Pid為個體極值，Pgd為全局極值，c1、c2通常取2。當(dāng)種群最優(yōu)解達(dá)到預(yù)設(shè)范圍或K等于最大迭代次數(shù)時，則終止搜索。

1.2 混沌粒子群算法

現(xiàn)代非線性理論將混沌解釋為在確定體系中出現(xiàn)的一種非周期且無規(guī)則的運動。蟲口模型下的Logistic 方程是 一種典 型的混 沌系統(tǒng)［19］，方程可簡化為：

當(dāng)u取4 及xn為0～1 間的隨機數(shù)時，方程的輸出即可在0～1 間進(jìn)行無重復(fù)、類隨機的遍歷。因此，通過將混沌搜索與PSO 算法相結(jié)合，即可解決PSO 算法中由于粒子的初始化與進(jìn)化存在極強的隨機性而易陷入局部最優(yōu)的問題。其中，利用混沌對PSO 進(jìn)行優(yōu)化可分為以下兩點：一是對初始位置和初始速度使用混沌序列優(yōu)化，以提高種群的遍歷性與多樣性；二是對當(dāng)前種群的最優(yōu)解進(jìn)行混沌搜索，并使用搜索到的最優(yōu)結(jié)果代替當(dāng)前種群中任意一個粒子的位置，既可提高收斂速度，又避免易陷入局部最優(yōu)的缺陷。

1.3 雞群算法

雞群算法（CSO）是一種新的仿生學(xué)優(yōu)化算法，主要模擬雞群的等級制度和覓食行為。CSO 的思想是將雞群按照雞的類型進(jìn)行分組，即每一只公雞可帶領(lǐng)幾只母雞和小雞成為一組，組內(nèi)的母雞會在公雞的指引下進(jìn)行覓食，組內(nèi)的小雞則只能在對應(yīng)的母雞身邊覓食，且不同組間允許信息交流。需要注意的是，當(dāng)這種等級制度應(yīng)用在求解群體最優(yōu)值時，公雞、母雞、小雞的分類是根據(jù)適應(yīng)度從好到壞區(qū)分的，在每輪搜索中都會對組內(nèi)的公雞、母雞和小雞進(jìn)行重新選取。

利用CSO 的多種群性對CPSO 優(yōu)化的方法如下：

1）在首輪搜索時對種群的適應(yīng)度值從小到大進(jìn)行排序，然后按照排好的順序?qū)⒎N群中所有粒子按比例分為A 粒子（公雞）、B 粒子（母雞）、C 粒子（小雞）3 類，并按規(guī)則對應(yīng)分組，其余輪次則通過比較組內(nèi)的適應(yīng)度值來更新組內(nèi)的成員類型，無需變換組號的順序。

2）在每輪更新粒子的速度與位置時A 類粒子作為組內(nèi)優(yōu)秀的個體，更新公式與式（1）、式（2）相同。

B 類粒子在A 類粒子的指引下進(jìn)行搜索，同時也要吸收其他組的經(jīng)驗，其速度與位置的迭代公式可更改為：

其中，Pgd從式（1）的全局最優(yōu)變?yōu)榻M內(nèi)最優(yōu)，r3為0～1的隨機數(shù)，Xf是其他組的最優(yōu)位置，c3通常取2。而C 類粒子只能在B 類粒子附近搜索，其位置迭代公式為：

其 中，XBg是C 粒子對應(yīng)的B 粒子的位置，F(xiàn)L 通 常取0.5。

2 CPSCSFO 優(yōu)化的RSSI 質(zhì)心定位算法

2.1 RSSI 質(zhì)心定位算法

根據(jù)接收信號的強度指示來計算發(fā)送節(jié)點到接收節(jié)點的距離是RSSI 的測距原理。經(jīng)實驗證明，無線信號的傳播服從Shadowing 模型的概率分布。因此，本次實驗的無線電信號傳播隕耗模型可表示為［20］：

其中，Pr為信號接收強度指示值，Pt為發(fā)射節(jié)點發(fā)出的信號指示值，d0通常取1 m 作為參考距離，PP（Ld0）為參考距離為d0時的路徑隕耗功率，χ代表高斯分布因子，d為收發(fā)節(jié)點之間的距離。在節(jié)點發(fā)送數(shù)據(jù)幀時，利用該模型可得到未知節(jié)點到錨節(jié)點之間的距離。

若未定位節(jié)點有n個參考節(jié)點，坐標(biāo)分別用（x1，y1），（x2，y2），…，（xn，yn）表示，則原始質(zhì)心定位算法的計算方法如式（8）所示：

加權(quán)質(zhì)心定位算法則只選取其中最近的3 個錨節(jié)點A、B、C作為參考，并將這三點所圍成的三角形的質(zhì)心坐標(biāo)作為最優(yōu)解。當(dāng)離未知節(jié)點最近的錨節(jié)點數(shù)小于3 時，則選取最近的已定位節(jié)點作為偽錨節(jié)點來進(jìn)行輔助定位。其中，假設(shè)需定位節(jié)點到A、B、C3 個節(jié)點的距離用dA、dB、dC表示，那么所求節(jié)點的坐標(biāo)則如式（9）所示：

若該方法中計算各節(jié)點的距離是通過RSSI 的測距模型來實現(xiàn)的，則稱該方法為基于RSSI 的加權(quán)質(zhì)心定位算法。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是群智能算法用來判斷當(dāng)前粒子位置好壞的標(biāo)準(zhǔn)。在本次實驗中，為了修正種群粒子的位置，使其不斷向最優(yōu)解靠攏，需要構(gòu)造合適的適應(yīng)度函數(shù)來指引種群粒子的搜索方向。假設(shè)當(dāng)前未定位節(jié)點的3 個參考節(jié)點坐標(biāo)分別為（xa，ya）、（xb，yb）和（xc，yc），則該節(jié)點到3 個參考節(jié)點的距離可表示為：

結(jié)合由RSSI 測距模型測量出的該節(jié)點到3 個參考節(jié)點的距離（d1，d2，d3），即可構(gòu)造出混沌粒子群雞群融合算法的適應(yīng)度函數(shù)為：

2.3 CPSCSFO 優(yōu)化算法步驟

混沌粒子群雞群融合算法（CPSCSFO）優(yōu)化RSSI質(zhì)心定位的基本思路為：在利用RSSI 測距模型獲知參考節(jié)點與未定位節(jié)點的距離后，在求解最優(yōu)解時使用CPSCSFO 算法進(jìn)行空間搜索，并利用構(gòu)造好的適應(yīng)度函數(shù)判斷出粒子位置優(yōu)劣性，最后得到的最小適應(yīng)度值對應(yīng)的坐標(biāo)，就是所求定位節(jié)點的坐標(biāo)。CPSCSFO求解最優(yōu)值的算法流程如圖1 所示。

圖1 CPSCSFO 算法流程Fig.1 Procedure of CPSCSFO algorithm

CPSCSFO 算法步驟如下：

步驟1設(shè)置一個M個粒子的種群并定義相關(guān)變量，利用混沌序列初始化每個粒子的初始速度與初始位置。

步驟2計算出各個粒子當(dāng)前的適應(yīng)度值，確定個體最優(yōu)與全局最優(yōu)。

步驟3判斷是否需要重新建立粒子群的等級體系（即組內(nèi)重新分類），如果需要，則重新建立，否則執(zhí)行以下步驟。

步驟4對整個種群得到的適應(yīng)度值進(jìn)行排序，并以此為基礎(chǔ)確定種群的等級體系。

步驟5按照等級體系確定A 類粒子（公雞）與B 類粒子（母雞）之間的隸屬關(guān)系，確定B 類粒子（母雞）與C 類粒子的母子關(guān)系。

步驟6A、B 和C 類粒子根據(jù)其對應(yīng)的雞群算法下的更新公式進(jìn)行速度與位置的更新。

步驟7求解適應(yīng)度值，對最優(yōu)粒子利用混沌搜索進(jìn)行二次尋優(yōu)，若存在更優(yōu)值，則用該值對應(yīng)的粒子代替種群中的任意一個粒子，并更新個體最優(yōu)與全局最優(yōu)。

步驟8判斷是否到達(dá)設(shè)定最大迭代次數(shù)，若是則終止算法，否則跳回步驟3。

3 仿真結(jié)果與分析

3.1 仿真實驗

根據(jù)建立好的數(shù)學(xué)模型和適應(yīng)度函數(shù)，本文對傳統(tǒng)質(zhì)心定位算法、加權(quán)RSSI 質(zhì)心定位算法、PSO-RSSI質(zhì)心定位算法與CPSCSFO-RSSI 質(zhì)心定位算法進(jìn)行仿真實驗，并在求出不同λ（錨節(jié)點所占比例）、R（節(jié)點最大通信距離）下各種算法的平均定位誤差后，通過實驗對比驗證了本文算法在無線傳感網(wǎng)定位上具有更好的優(yōu)越性。具體的參數(shù)配置如表1 所示。

表1 實驗參數(shù)設(shè)置Table 1 Experimental parameter setting

此外，錨節(jié)點數(shù)量為ngps=λn，而未定位節(jié)點的數(shù)量為nunl=n?ngps。若錨節(jié)點以時間周期T向周圍發(fā)送數(shù)量N（st）=S的數(shù)據(jù)包，未定位節(jié)點在監(jiān)聽時間t=（S+1?ε）T（0<ε<<1）內(nèi)收到的數(shù)據(jù)包量為N（rt），則該未定位節(jié)點接收數(shù)據(jù)包的成功的概率SR 可用式（12）表示。這兩個收發(fā)節(jié)點互為鄰居節(jié)點的條件是SR>SRth。

圖2 是表1 參數(shù)下的節(jié)點分布，其中，*表示錨節(jié)點，圈號表示未定位節(jié)點。當(dāng)這些未定位節(jié)點利用各種算法求出對應(yīng)坐標(biāo)后，還需要計算出對應(yīng)算法下的平均定位誤差以比較不同算法的定位精確度。

圖2 節(jié)點分布Fig.2 Node distribution

假設(shè)（xi，y）i是未定位節(jié)點用各種算法求解后的坐標(biāo)值，（x，y）是該節(jié)點設(shè)定的實際坐標(biāo)值，則實驗平均定位誤差Lerr的求解公式為：

3.2 結(jié)果分析

為了保證實驗結(jié)果的精準(zhǔn)性，每個點選取的平均定位誤差值都是經(jīng)過20 次重復(fù)實驗后，將每次得出的結(jié)果進(jìn)行求和再取均值而得到值。圖3 是R=200 時，4 種算法隨著λ變化時平均定位誤差的比較曲線。

圖3 4 種算法的平均定位誤差與λ 變化曲線Fig.3 Curves of average positioning error and λ change of four algorithms

從圖3 可以看出，當(dāng)錨節(jié)點數(shù)隨著比例增大時，4 種算法的定位誤差都隨之下降。這是由于錨節(jié)點增加后，整個系統(tǒng)的定位參考點呈增大的趨勢，從而可以選擇更好的錨節(jié)點作為定位參考點。另外，在λ增大的整個過程中，相比于其他3 種算法，CPSCSFO-RSSI 質(zhì)心定位算法的平均定位誤差值較低，這說明本文算法擁有更高的定位精度。其中，CPSCSFO-RSSI 算法與PSO-RSSI 算法相比也有明顯的優(yōu)越性（特別是在λ<0.25 時）。這是因為引入的混沌搜素與雞群算法對PSO 起到了優(yōu)化的作用，能有效解決PSO 算法容易陷入局部最優(yōu)解的問題，從而進(jìn)一步提高了定位精度。

由于錨節(jié)點的價格比較昂貴，在實際應(yīng)用中增加錨節(jié)點的數(shù)量相當(dāng)于提高了系統(tǒng)成本。從圖3 可以看出，當(dāng)λ大于0.25 后，CPSCSFO-RSSI 曲線下降不明顯，且與PSO-RSSI 曲線相差也較小。因此，本文選取λ=0.25 時改變另外一個影響定位精度的因素——R（最大通信半徑）的值，進(jìn)一步評估這4 種算法的性能，結(jié)果如圖4 所示。

圖4 λ=0.25時4種算法的平均定位誤差-最大通信半徑變化曲線Fig.4 Average positioning error maximum communication radius curve of four algorithms when λ=0.25

從圖4 可以看出，隨著通信最大半徑的增大，4 種算法的平均定位誤差呈下降趨勢，且其中定位誤差最小的是CPSCSFO-RSSI 定位算法。其原因可分為以下兩點：一是因為隨著R的增大，未定位節(jié)點的鄰居節(jié)點也隨之增多，連通度增大；二是因為CPSCSFO 融入了混沌搜索的隨機性、可遍歷性的優(yōu)點，從而有效改善了粒子群算法容易陷入局部最優(yōu)的缺陷，同時利用雞群算法的多種群性，達(dá)到進(jìn)一步提高搜索精度的效果。

表2 為4 種算法當(dāng)λ=0.25 及R為190 m、200 m、210 m、220 m、230 m 時的平均定位誤差值?？梢钥闯觯疚乃惴ǖ亩ㄎ痪容^高。其中，相比于原始質(zhì)心定位和加權(quán)RSSI 質(zhì)心定位算法，基于PSO-RSSI 質(zhì)心定位算法的平均定位誤差分別降低了約22%與11%，而基于CPSCSFO-RSSI算法則分別降低了約31%與21%。為了更清晰直觀地表達(dá)PSO-RSSI 與CPSCSFO-RSSI算法的定位誤差效果，本文實驗選取λ=0.25、R=220 時1000 m×1000 m 范圍內(nèi)的定位情況，定位誤差的效果對比如圖5 所示。其中，星號代表錨節(jié)點，圈號代表已經(jīng)定位的節(jié)點，實際位置與利用算法定位得到的位置之間的距離用實線表示。可以看出，圖5 中CPSCSFO算法下的絕大部分線段，都比PSO 算法下的線段短。這是由于新算法融合了混沌搜索與雞群算法，從而具有比PSO 算法更高的搜索精度。

表2 λ=0.25 時4 種算法的平均定位誤差Table 2 Average positioning error of four algorithms when λ=0.25

圖5 PSO 與CPSCSFO 算法定位誤差對比Fig.5 Comparison of positioning error between PSO and CPSCSFO algorithm

3.3 算法復(fù)雜度分析

在PSO-RSSI 與CPSCSFO-RSSI 質(zhì)心定位算法的定位過程中，整個算法復(fù)雜度的主要開銷可分為兩個方面：一是利用RSSI 測距模型進(jìn)行測距；二是利用算法進(jìn)行最優(yōu)解的搜索。由于RSSI 測距的時間復(fù)雜度與錨節(jié)點數(shù)成正比關(guān)系，即O（ngps）；而本次選取的最優(yōu)比例降至λ=0.25 處，因此利用RSSI 測距時間復(fù)雜度也會隨之下降。而算法在搜索過程所產(chǎn)生的復(fù)雜度，主要與種群的數(shù)量M和最大迭代次數(shù)N的乘積成正比，即O（M×N）。

CPSCSFO 在PSO 基礎(chǔ)上引入的雞群算法只是改變了計算公式，并不會增加空間復(fù)雜度的開銷。它的額外開銷在于使用混沌搜索時所占用到的內(nèi)部存儲空間。但是空間復(fù)雜度和時間復(fù)雜度是互相影響 的，圖6 給出了 當(dāng)R=220 與λ=0.25 時PSO 與CPSCSFO 算法在求某個未知節(jié)點坐標(biāo)時的適應(yīng)度曲線。其中，PSO1 表示同樣在該點處，PSO 陷入局部最優(yōu)解的情況，PSO2 則是精準(zhǔn)定位時的情況。相比于PSO 算法，CPSCSFO 算法因融合了混沌序列與雞群算法的優(yōu)點，既可以避免出現(xiàn)類似于PSO1 曲線的情況，也提升了算法的收斂速度。在基于PSO 的質(zhì)心定位算法中，由于PSO 具有容易早熟的缺點，最大迭代次數(shù)N1的值若小于500 就無法保證解的精準(zhǔn)性，而CPSCSFO 由于經(jīng)過混沌序列的初始化，只需把N2的值設(shè)定為300 就可得到算法的最優(yōu)解。顯然CPSCSFO 質(zhì)心定位算法的時間復(fù)雜度O（M×N2）小于PSO 質(zhì)心定位算法的O（M×N1）。

圖6 2 種算法在R=220、λ=0.25 的某一點處適應(yīng)度-迭代次數(shù)曲線Fig.6 Fitness iteration degree curve of two algorithms at a point of R=220 and λ=0.25

4 結(jié)束語

傳感節(jié)點的定位技術(shù)是無線傳感網(wǎng)絡(luò)實際應(yīng)用中至關(guān)重要的部分。本文采用低成本、低功耗的RSSI 測距模型對傳感節(jié)點進(jìn)行測距，在無需增加外設(shè)的情況下引入了混沌粒子群雞群融合算法來進(jìn)行最優(yōu)搜索，從而達(dá)到既提高定位精度又不增加系統(tǒng)成本的目的。仿真實驗結(jié)果表明，混沌粒子群雞群融合算法的RSSI 質(zhì)心定位算法相比于原始質(zhì)心定位算法、加權(quán)RSSI 質(zhì)心定位算法和PSO-RSSI 質(zhì)心定位算法具有較高的定位精度、較快的收斂速度以及較強的實用性。但是在多樣的地理環(huán)境中，RSSI信號接收的強弱會受到各種不同的環(huán)境因素影響，因此下一步研究方向是提高RSSI 測距在特殊環(huán)境下的精準(zhǔn)性與泛用性。