[發(fā)明專利]一種基于SCE?PSO算法的無線傳感器網(wǎng)絡(luò)節(jié)點三維定位方法

在審

• 申請?zhí)枺?/td>: 201710989499.7
• 申請日: 2017-10-21
• 公開（公告）號: CN107734637A
• 公開（公告）日: 2018-02-23
• 發(fā)明（設(shè)計）人: 劉偉;李卓;楊曉斐;劉亞榮;楊麗燕
• 申請（專利權(quán)）人: 桂林理工大學(xué)
• 主分類號: H04W64/00
• 分類號: H04W64/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明屬于無線傳感器網(wǎng)絡(luò)中的節(jié)點定位領(lǐng)域。

背景技術(shù)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)節(jié)點的三維定位是當(dāng)前的研究熱點之一。根據(jù)是否需要測量節(jié)點之間的距離，無線傳感器網(wǎng)絡(luò)的節(jié)點定位方法可以劃分為基于測距和基于非測距的兩種方法。其中基于測距的方法，由于定位精度高在無線傳感器網(wǎng)絡(luò)節(jié)點定位中被廣泛采用。基于測距的定位方法首先要測量節(jié)點之間的距離或角度，常用的測量方法有接收信號強度指示 (Received Signal Strength Indicator，RSSI)、到達(dá)時間(Time of Arrival，TOA)、到達(dá)時間不同(Time Difference of Arrival，TDOA)和到達(dá)角度(Angle of Arrival， AOA)。

獲取節(jié)點之間的距離或角度信息后，基于測距的方法就可以采用一些定位方法對未知節(jié)點進(jìn)行定位，其中一類方法是把獲取的距離或角度信息看作約束條件，將其轉(zhuǎn)化為一個目標(biāo)函數(shù)，然后用各種優(yōu)化算法尋找該目標(biāo)函數(shù)的最小值，從而對未知節(jié)點進(jìn)行定位。優(yōu)化方法可分為傳統(tǒng)的優(yōu)化方法和生物啟發(fā)式優(yōu)化方法。

傳統(tǒng)的優(yōu)化方法基于確定的搜索策略，在滿足一定的限制條件下，利用優(yōu)化問題的導(dǎo)數(shù)、梯度等數(shù)學(xué)性質(zhì)進(jìn)行求解。該類方法的缺點是運算復(fù)雜度較高，并且隨著問題的維數(shù)的增大其復(fù)雜度以指數(shù)倍增加，生物啟發(fā)式優(yōu)化方法可以有效地避免這個問題，使計算更加有效，對優(yōu)化問題所對應(yīng)的函數(shù)形式不做任何假設(shè)，而且不要求目標(biāo)函數(shù)的連續(xù)性或可導(dǎo)性的假設(shè)，算法簡單，易于實現(xiàn)。

常見的生物啟發(fā)式優(yōu)化算法包括：模擬退火算法(Simulated Annealing，SA)、蟻群算法(Ant Colony Optimization，ACO)、遺傳算法(Genetic Algorithm，GA)、人工蜂群算法(Artificial Bee Colony，ABC)、細(xì)菌覓食算法(Bacterial Foraging Algorithm，BFA)、粒子群算法(Particle Swarm Optimization，PSO)。與其他生物啟發(fā)式優(yōu)化算法相比，粒子群算法具有容易執(zhí)行，收斂速度比較快的優(yōu)點。尤其是求解的問題維數(shù)越多，其優(yōu)勢越明顯。因此，粒子群算法非常適用于無線傳感器網(wǎng)絡(luò)節(jié)點的三維定位。但是，在運行過程中，粒子群算法可能會陷入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象。

發(fā)明內(nèi)容

針對無線傳感器網(wǎng)絡(luò)節(jié)點三維定位采用粒子群算法時，粒子在搜索過程中會陷入局部最優(yōu)，出現(xiàn)早熟收斂，從而導(dǎo)致節(jié)點定位精度較低的問題，本發(fā)明提出了一種改進(jìn)的粒子群算法SCE-PSO，該算法通過與SCE-UA(shuffling complex evolution-University of Arizona)算法相結(jié)合，增加了搜索過程中粒子的多樣性，從而減少了粒子陷入局部最優(yōu)的概率，提高了解的質(zhì)量。因此，與原始粒子群方法相比，該方法能夠提高定位精度，比較適合無線傳感器網(wǎng)絡(luò)節(jié)點三維定位。

具體實現(xiàn)過程如下：

1.粒子群算法

粒子群優(yōu)化算法的基本思想是：將優(yōu)化問題的每一個解看作一個微粒，每個微粒在多維搜索空間中以一定的速度飛行，通過目標(biāo)函數(shù)的適應(yīng)度值衡量微粒的優(yōu)劣，每個微粒能夠通過自己的飛行經(jīng)驗以及其他微粒的飛行經(jīng)驗，動態(tài)地調(diào)整自己的飛行速度，從而向群體中最好的微粒位置飛行，最終搜索到優(yōu)化問題的最優(yōu)解。假設(shè)求解的問題為n維，粒子群算法的求解步驟如下：

(1)初始化各參數(shù)，包括加速常數(shù)c₁和c₂，最大迭代次數(shù)T_max，粒子的速度范圍[v_min,v_max]，粒子的數(shù)目s和慣性權(quán)重的范圍[ω_min,ω_max]。

(2)將迭代次數(shù)設(shè)置為t＝1，隨機產(chǎn)生初始粒子的位置和粒子的初始速度i＝1,2,…,s。其中， d＝1,2,…,n。

(3)將作為每個粒子的最佳位置p_id，并計算每個粒子的最佳適應(yīng)度值h_i，將h_i中的最小值作為全局最佳適應(yīng)度值g，并記錄下具有g(shù)的粒子的位置g_d。