混沌粒子群雞群融合優化的RSSI 質心定位算法

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

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

0 概述

物聯網被認為是繼計算機、互聯網后世界信息產業的第三次浪潮，其將傳感器技術應用于環境監測、智慧農業和智慧城市等領域［1-2］。在無線傳感網絡應用場景中，如果傳感節點不能獲知它們的位置信息，則這些傳感器所感知的數據也將沒有意義［3-5］。因此，研究無線傳感網絡的定位技術顯得尤為重要［6］。

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

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

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

1.1 標準粒子群算法

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

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

1.2 混沌粒子群算法

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

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

1.3 雞群算法

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

利用CSO 的多種群性對CPSO 優化的方法如下：

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

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

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

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

其 中，XBg是C 粒子對應的B 粒子的位置，FL 通 常取0.5。

2 CPSCSFO 優化的RSSI 質心定位算法

2.1 RSSI 質心定位算法

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

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

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

加權質心定位算法則只選取其中最近的3 個錨節點A、B、C作為參考，并將這三點所圍成的三角形的質心坐標作為最優解。當離未知節點最近的錨節點數小于3 時，則選取最近的已定位節點作為偽錨節點來進行輔助定位。其中，假設需定位節點到A、B、C3 個節點的距離用dA、dB、dC表示，那么所求節點的坐標則如式（9）所示：

若該方法中計算各節點的距離是通過RSSI 的測距模型來實現的，則稱該方法為基于RSSI 的加權質心定位算法。

2.2 適應度函數

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

結合由RSSI 測距模型測量出的該節點到3 個參考節點的距離（d1，d2，d3），即可構造出混沌粒子群雞群融合算法的適應度函數為：

2.3 CPSCSFO 優化算法步驟

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

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

CPSCSFO 算法步驟如下：

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

步驟2計算出各個粒子當前的適應度值，確定個體最優與全局最優。

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

步驟4對整個種群得到的適應度值進行排序，并以此為基礎確定種群的等級體系。

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

步驟6A、B 和C 類粒子根據其對應的雞群算法下的更新公式進行速度與位置的更新。

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

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

3 仿真結果與分析

3.1 仿真實驗

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

表1 實驗參數設置Table 1 Experimental parameter setting

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

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

圖2 節點分布Fig.2 Node distribution

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

3.2 結果分析

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

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

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

由于錨節點的價格比較昂貴，在實際應用中增加錨節點的數量相當于提高了系統成本。從圖3 可以看出，當λ大于0.25 后，CPSCSFO-RSSI 曲線下降不明顯，且與PSO-RSSI 曲線相差也較小。因此，本文選取λ=0.25 時改變另外一個影響定位精度的因素——R（最大通信半徑）的值，進一步評估這4 種算法的性能，結果如圖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的增大，未定位節點的鄰居節點也隨之增多，連通度增大；二是因為CPSCSFO 融入了混沌搜索的隨機性、可遍歷性的優點，從而有效改善了粒子群算法容易陷入局部最優的缺陷，同時利用雞群算法的多種群性，達到進一步提高搜索精度的效果。

表2 為4 種算法當λ=0.25 及R為190 m、200 m、210 m、220 m、230 m 時的平均定位誤差值。可以看出，本文算法的定位精度較高。其中，相比于原始質心定位和加權RSSI 質心定位算法，基于PSO-RSSI 質心定位算法的平均定位誤差分別降低了約22%與11%，而基于CPSCSFO-RSSI算法則分別降低了約31%與21%。為了更清晰直觀地表達PSO-RSSI 與CPSCSFO-RSSI算法的定位誤差效果，本文實驗選取λ=0.25、R=220 時1000 m×1000 m 范圍內的定位情況，定位誤差的效果對比如圖5 所示。其中，星號代表錨節點，圈號代表已經定位的節點，實際位置與利用算法定位得到的位置之間的距離用實線表示。可以看出，圖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 算法復雜度分析

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

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

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

4 結束語

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