崔煥慶，張 娜，羅漢江

(山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)由大量傳感器節(jié)點(diǎn)組成，廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、智慧城市、災(zāi)害救援和目標(biāo)追蹤等領(lǐng)域。 確定傳感器節(jié)點(diǎn)的位置信息為許多位置感知協(xié)議和應(yīng)用程序提供了基礎(chǔ)支持，因此，節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一[1]。 由于成本因素，為每個(gè)節(jié)點(diǎn)配備全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite System，GNSS)進(jìn)行定位是不現(xiàn)實(shí)的。 目前常用的方法是先給部分節(jié)點(diǎn)配備GNSS 以獲取其自身位置并輔助其他節(jié)點(diǎn)進(jìn)行定位，將已知自身位置的節(jié)點(diǎn)稱為錨節(jié)點(diǎn)，其他節(jié)點(diǎn)稱為未知節(jié)點(diǎn)[2]。

目前定位算法可分為無(wú)需測(cè)距和基于測(cè)距兩類[3]。 前者根據(jù)節(jié)點(diǎn)間的連通信息估計(jì)距離，后者需要測(cè)量節(jié)點(diǎn)之間的距離或角度。 相比于無(wú)需測(cè)距的定位算法，基于測(cè)距的定位算法精度更高[4]。 獲得距離后，使用三邊測(cè)量、極大似然估計(jì)(Maximum Likelihood Estimation，MLE)等估計(jì)節(jié)點(diǎn)位置[5]。 相比于傳統(tǒng)的定位算法，智能優(yōu)化算法計(jì)算精確、計(jì)算復(fù)雜度低，被廣泛應(yīng)用于節(jié)點(diǎn)定位中。 ISSADVHop[6]算法通過(guò)修正DV-Hop 的平均跳距，并使用佳點(diǎn)集和Levy 飛行策略對(duì)麻雀搜索算法進(jìn)行改進(jìn)，改善了定位精度。 AWL-MC[7]算法采用非線性映射曲線距離分析對(duì)未知節(jié)點(diǎn)進(jìn)行粗略的相對(duì)坐標(biāo)定位，再通過(guò)線性變換將相對(duì)坐標(biāo)轉(zhuǎn)換成絕對(duì)坐標(biāo)，最后采用自適應(yīng)Levy 飛行優(yōu)化鯨魚算法，以提高定位精度。 OLSSO[8]算法先通過(guò)Bounding-box 方法得到未知節(jié)點(diǎn)可能存在的區(qū)域以初始化個(gè)體，后將加權(quán)中心反向?qū)W習(xí)策略與群居蜘蛛群優(yōu)化算法相結(jié)合，具有較高的定位精度和較快的收斂速度。

目前，鴿群算法(Pigeon Inspired Optimization，PIO)[9]已廣泛應(yīng)用于各個(gè)領(lǐng)域，PIO 相比于粒子群優(yōu)化(Particle Swarm Optimization，PSO)[10]、蝙蝠算法(Bat Algorithm，BA)[11]等，具有收斂速度快、參數(shù)較少和穩(wěn)健性強(qiáng)等優(yōu)點(diǎn)，但是容易陷入局部最優(yōu)[12]。 為此，本文提出了一種基于改進(jìn)鴿群優(yōu)化(Modified Pigeon Inspired Optimization，MPIO)的定位算法。 本文的主要貢獻(xiàn)有:①為了解決PIO 容易陷入局部最優(yōu)的問(wèn)題，設(shè)計(jì)了一種改進(jìn)鴿群算法即MPIO 算法，在保持快速收斂能力的同時(shí)，提高了PIO 的計(jì)算精度。 ②將MPIO 算法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位以提高性能。

本文組織如下。 第一部分介紹了網(wǎng)絡(luò)模型，第二部分介紹了標(biāo)準(zhǔn)鴿群算法，第三部分介紹了MPIO 算法及其在定位中的應(yīng)用，第四部分給出了仿真實(shí)驗(yàn)和結(jié)果分析，最后第五部分總結(jié)了全文。

1 網(wǎng)絡(luò)模型

假設(shè)WSN 由N個(gè)傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)在部署完后不再移動(dòng)。 錨節(jié)點(diǎn)數(shù)為M，第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)記為Ai＝(xai，yai)。 第j個(gè)未知節(jié)點(diǎn)的實(shí)際坐標(biāo)記為Uj＝(xuj，yuj)，估計(jì)坐標(biāo)記為＾Uj＝(＾xuj，＾yuj)。傳感器節(jié)點(diǎn)通信范圍是一個(gè)半徑為R的圓，錨節(jié)點(diǎn)向其通信范圍內(nèi)的節(jié)點(diǎn)廣播信息，所廣播的用于輔助未知節(jié)點(diǎn)定位的信息稱為信標(biāo)信息，包含錨節(jié)點(diǎn)坐標(biāo)和發(fā)送信號(hào)強(qiáng)度兩個(gè)字段。 傳感器節(jié)點(diǎn)使用接收信號(hào)強(qiáng)度(Received Signal Strength，RSS)測(cè)距，RSS 采用對(duì)數(shù)-常態(tài)分布無(wú)線信號(hào)傳播模型[13]，即:

式中:d0為參考距離，PL(d0)為傳播距離為d0時(shí)的接收信號(hào)功率。d為參考節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離，Prx為傳播距離為d時(shí)的信號(hào)接收功率。η為路徑損耗因子，Xσ為均值為0，標(biāo)準(zhǔn)差為σ的高斯變量。

在實(shí)際應(yīng)用中，由于多徑衰弱、信號(hào)傳播不穩(wěn)定和噪聲等因素，傳感器節(jié)點(diǎn)的通信范圍不是一個(gè)規(guī)則的圓，所以使用通信不規(guī)則度(Degree of Irregularity，DOI)進(jìn)行建模[14]。 DOI 值越高，通信范圍受環(huán)境影響越嚴(yán)重。 DOI 定義如下:

式中:Kθ表示第θ個(gè)方向上的不規(guī)則度，滿足｜K0-K359｜≤DOI，r∈[0，1]是一個(gè)服從均勻分布的隨機(jī)數(shù)。 使用DOI 后的信號(hào)傳播模型定義為:

設(shè)錨節(jié)點(diǎn)Ai和未知節(jié)點(diǎn)Uj的實(shí)際距離為dij，使用RSS 測(cè)得的距離為＾dij。 通過(guò)最小化dij與＾dij之差來(lái)達(dá)到估計(jì)未知節(jié)點(diǎn)位置的目的，所以使用智能優(yōu)化算法定位的適應(yīng)度函數(shù)定義如下:

式中:n為Uj通信范圍內(nèi)的錨節(jié)點(diǎn)數(shù)，X為智能優(yōu)化算法中的個(gè)體位置。

平均定位誤差(Average Localization Error，ALE)定義為全部未知節(jié)點(diǎn)估計(jì)坐標(biāo)與實(shí)際坐標(biāo)之間歐氏距離的均值，即:

2 標(biāo)準(zhǔn)鴿群算法

PIO 是模仿鴿子歸巢行為的一種智能優(yōu)化算法。 鴿子歸巢可分為兩個(gè)階段，在不同階段使用不同的導(dǎo)航工具。 在地圖和指南針?biāo)阕与A段，鴿子通過(guò)感知磁場(chǎng)生成地圖，把太陽(yáng)作為指南針調(diào)整飛行方向。 在飛向目的地的過(guò)程中，其對(duì)磁場(chǎng)和太陽(yáng)的依賴性減少。 在D維搜索空間中，第i只鴿子的位置Xi和速度Vi按照下式進(jìn)行更新:

式中:t為當(dāng)前迭代次數(shù)，α∈(0，1)為地圖和指南針因子，Gbest為全局最優(yōu)位置。 記T1max為該階段最大迭代次數(shù)，當(dāng)t＞T1max時(shí)，進(jìn)入下一階段。

在地標(biāo)算子階段，每次迭代時(shí)先根據(jù)適應(yīng)度值將鴿子排成非減序，保留前一半鴿子；然后在剩余鴿子中計(jì)算加權(quán)中心位置作為鴿子飛行的參考方向。鴿子位置更新如下:

式中:Np為鴿子總數(shù)，Xc為加權(quán)中心位置，f(·)為適應(yīng)度函數(shù)。 記T2max為該階段最大迭代次數(shù)，當(dāng)t＞T2max時(shí)，地標(biāo)算子停止工作。

3 改進(jìn)鴿群算法

3.1 地圖和指南針?biāo)阕与A段

在該階段，PIO 算法的全局搜索能力主要由指數(shù)權(quán)值W＝e-αt決定，使得鴿群在迭代過(guò)程中多樣性呈遞減趨勢(shì)并逐步向最優(yōu)解收斂[15]。 這種更新方式使算法快速收斂，但是全局搜索能力較差。 地圖和指南針因子α在很大程度上決定了算法全局搜索能力的優(yōu)劣。 圖1 展示了指數(shù)權(quán)值W在T1max＝50 時(shí)的變化情況。α＝0.3，t<15 時(shí)，W<0.75，種群多樣性快速減少；而t≥15 時(shí)，W≈0，種群多樣性喪失，算法主要在Gbest附近進(jìn)行局部搜索，失去了全局搜索能力，導(dǎo)致過(guò)早收斂。α＝0.02，t＝50 時(shí)，W＝0.38，算法不易收斂。 0.02<α<0.3 時(shí)，W呈指數(shù)遞減趨勢(shì)，種群多樣性快速減少，導(dǎo)致較差的全局搜索能力。

圖1 指數(shù)權(quán)值隨迭代次數(shù)變化圖

為平衡全局搜索與局部搜索，改進(jìn)式(6)為:

α＝0.3 時(shí)，改進(jìn)后的指數(shù)權(quán)值W′＝1-e-αt的變化情況如圖1 所示。t≤4 時(shí)，W′<0.6，僅在Gbest附近搜索，能夠更快地在Gbest處收斂；4

3.2 地標(biāo)算子階段

在該階段，MPIO 不刪除鴿子，而是按照適應(yīng)度值排序后將鴿子分為兩組種群，在不同種群中用不同方式進(jìn)行迭代更新。 定義:

前N′p只鴿子為一組，鴿子位置更新公式為:

式中:Xpi為第i只鴿子的局部最優(yōu)位置。

剩余Np-只鴿子分一組，使用隨機(jī)游走和捕食機(jī)制更新鴿子位置。 隨機(jī)游走是在最優(yōu)解附近產(chǎn)生局部新解，在一定程度上能夠使算法跳出局部最優(yōu)，即:

式中:β∈[-1，1]是一個(gè)隨機(jī)變量，E∈(0，1)為一個(gè)常數(shù)，為第i只鴿子在第t次迭代時(shí)的脈沖發(fā)射率。

捕食機(jī)制中，鴿子會(huì)減少響度Li，增大ri，擇優(yōu)選擇鴿子位置并更新Li和ri，即:

式中:ε∈[0，1]為常數(shù)，表示響度衰減系數(shù)；μ＞0 為常數(shù)，表示脈沖增強(qiáng)系數(shù)；＝0.7 表示第i只鴿子的初始脈沖發(fā)射率，設(shè)置每只鴿子的響度Li初始值為0.1。

3.3 基于MPIO 的定位算法

使用MPIO 進(jìn)行定位的基本思路是:錨節(jié)點(diǎn)廣播信標(biāo)信息后，未知節(jié)點(diǎn)使用RSS 測(cè)量與鄰居錨節(jié)點(diǎn)的距離。 在測(cè)得至少3 個(gè)相鄰錨節(jié)點(diǎn)的距離、位置后，便采用MPIO 算法進(jìn)行位置計(jì)算。 具體流程如算法1 所示。

輸入:未知節(jié)點(diǎn)U 及其相鄰錨節(jié)點(diǎn)集合A輸出:＾U＝(＾xu，＾yu)1. 初始化D，Np，T1max，T2max，α，E，ε，μ 2. 使用RSS 估算U 到每個(gè)錨節(jié)點(diǎn)的距離3. 隨機(jī)生成Np 只鴿子，第i 只鴿子坐標(biāo)為Xi(i ＝1，2，…，Np)4. 使用式(4)計(jì)算適應(yīng)度函數(shù)值5. Gbest←最佳位置6. for t←1 to T1max do 7. 所有鴿子根據(jù)式(11)和(7)更新位置8. 使用式(4)計(jì)算適應(yīng)度函數(shù)值9. 更新Xp 和Gbest 10. t←t+1 11. end for

12. for t←1 to T2max do 13. 根據(jù)適應(yīng)度函數(shù)值對(duì)鴿子進(jìn)行排序14. 根據(jù)式(12)和(13)更新N′p和Xc 15. 前N′p只鴿子根據(jù)式(14)更新位置16. 其余鴿子根據(jù)式(15)更新位置17. 使用式(4)計(jì)算適應(yīng)度函數(shù)值18. 更新Xp 和Gbest 19. t←t+1 20. end for 21. return Gbest

算法1 第1 行初始化必要參數(shù)，第2 行使用RSS 測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離，第3～5 行初始化鴿群，第6～11 行是地圖和指南針?biāo)阕与A段，第12～20 行是地標(biāo)算子階段，每階段使用不同的公式更新鴿子位置。 第21 行返回Gbest作為未知節(jié)點(diǎn)U的估計(jì)位置。

該算法的主體是兩個(gè)for 循環(huán)，每個(gè)for 循環(huán)都是根據(jù)上述公式對(duì)鴿子位置進(jìn)行更新，其中第2 個(gè)循環(huán)需要對(duì)鴿子進(jìn)行排序，因此其時(shí)間復(fù)雜度為O(NpT1max+NpT2maxlogNp)。

4 仿真實(shí)驗(yàn)

本文使用MATLAB R2016b 進(jìn)行仿真，所有算法運(yùn)行50 次并取均值作為實(shí)驗(yàn)結(jié)果。 在定位精度上將MPIO 與MLE、PSO、PIO、BA、GPIO[16]算法相比較。 各算法參數(shù)設(shè)置如表1 所示，其他實(shí)驗(yàn)參數(shù)設(shè)置如表2 所示。

表1 優(yōu)化算法的參數(shù)設(shè)置

表2 其他實(shí)驗(yàn)參數(shù)設(shè)置

4.1 定位精度對(duì)比

在錨節(jié)點(diǎn)數(shù)M＝50，通信半徑R＝20，25，30，35，40 時(shí)的結(jié)果如圖2 所示。 隨著R的增加，平均定位誤差A(yù)LE 隨之下降，原因在于R的增大使得孤立節(jié)點(diǎn)的數(shù)量大幅減少，距離測(cè)量更加準(zhǔn)確。 BA 算法的ALE 最大，因?yàn)槠湓谳^大的部署區(qū)域內(nèi)尋優(yōu)能力較差；其次是MLE，它計(jì)算簡(jiǎn)單，但是求解能力較差；其次是PIO 和PSO 算法，因?yàn)镻SO 和PIO 都有容易陷入局部最優(yōu)的局限性；GPIO 通過(guò)在距離較近的種群個(gè)體上添加高斯變異使種群個(gè)體隨機(jī)發(fā)散，并沒(méi)有有效解決算法陷入局部最優(yōu)。 MPIO 算法的定位精度始終優(yōu)于其他算法，GPIO、MPIO 相比于PIO 分別提高了30%、60%。 MPIO 算法具有更優(yōu)的求解能力，一方面是因?yàn)樘砑恿俗赃m應(yīng)調(diào)整機(jī)制，使種群個(gè)體快速尋找全局最優(yōu)并提高了種群在最優(yōu)解附近的局部搜索能力；另一方面是因?yàn)榉N群分組和隨機(jī)游走機(jī)制增加了種群多樣性，使算法能夠跳出局部最優(yōu)。

圖2 通信半徑對(duì)定位誤差的影響

在通信半徑R＝30，錨節(jié)點(diǎn)數(shù)M＝40，45，50，55，60 時(shí)的結(jié)果如圖3 所示。 隨著錨節(jié)點(diǎn)數(shù)量的增加，未知節(jié)點(diǎn)接收到的信標(biāo)信息更多，平均定位誤差A(yù)LE 會(huì)隨之下降。 BA 算法的ALE 最大，因?yàn)槠湓谳^大的部署區(qū)域內(nèi)尋優(yōu)能力較差；其次是MLE，它計(jì)算簡(jiǎn)單但是求解能力較差；其次是PIO 和PSO，因?yàn)镻SO 和PIO 都容易陷入局部最優(yōu)；GPIO 沒(méi)有有效改進(jìn)PIO 容易陷入局部最優(yōu)的缺陷。 MPIO 算法的定位精度始終優(yōu)于其他算法，GPIO、MPIO 相比于PIO 分別提高了33%、60%。 MPIO 算法的自適應(yīng)調(diào)整機(jī)制和隨機(jī)游走機(jī)制增加了種群多樣性，有效提高了PIO 算法的求解精度。 在相同條件下，MPIO算法所需的錨節(jié)點(diǎn)數(shù)量最少，能有效減少網(wǎng)絡(luò)成本。

圖3 錨節(jié)點(diǎn)數(shù)量對(duì)定位誤差的影響

在錨節(jié)點(diǎn)數(shù)M＝50，通信半徑R＝30，測(cè)距誤差σ＝2，4，6，8 時(shí)的結(jié)果如圖4 所示。 隨著σ的增加，平均定位誤差A(yù)LE 也隨之增大。 MLE 受測(cè)距誤差影響最大；其次是BA 算法，因?yàn)槠湓谳^大的部署區(qū)域內(nèi)尋優(yōu)能力較差；其次是PIO 和PSO，因?yàn)镻SO和PIO 都容易陷入局部最優(yōu)；GPIO 沒(méi)有有效改進(jìn)PIO 容易陷入局部最優(yōu)的缺陷。 MPIO 算法的定位精度始終優(yōu)于其他算法，GPIO、MPIO 相比于PIO 分別提高了27%、49%。 MPIO 算法的自適應(yīng)調(diào)整機(jī)制和隨機(jī)游走機(jī)制使算法跳出局部最優(yōu)，有效提高了PIO 算法的求解精度。 相同條件下，MPIO 算法受測(cè)距誤差的影響最小。

圖4 測(cè)距誤差對(duì)定位誤差的影響

在錨節(jié)點(diǎn)數(shù)M＝50，通信半徑R＝30，通信不規(guī)則度DOI＝0.05，0.1，0.15，0.2，0.25 時(shí)的結(jié)果如圖5所示。 DOI 越大，節(jié)點(diǎn)通信范圍越不規(guī)則，平均定位誤差A(yù)LE 也隨之增大。 BA 算法受DOI 影響使得ALE 最大，因?yàn)槠湓谳^大的部署區(qū)域內(nèi)求解能力較差；其次是MLE，它計(jì)算簡(jiǎn)單但是求解能力較差；其次是PIO 和PSO，因?yàn)镻SO 和PIO 都容易陷入局部最優(yōu)；GPIO 沒(méi)有有效改進(jìn)PIO 容易陷入局部最優(yōu)的缺陷。 MPIO 算法的定位精度始終優(yōu)于其他算法，各算法受DOI 影響定位誤差的波動(dòng)幅度分別為:MLE 0.79%、PSO 1.12%、BA 4.63%、PIO 1.32%、GPIO 1.34%、MPIO 0.91%。 MPIO 算法的自適應(yīng)調(diào)整機(jī)制和隨機(jī)游走機(jī)制有效改進(jìn)了PIO 算法容易陷入局部最優(yōu)的缺陷。 相同條件下，MPIO 算法受DOI 的影響變化幅度較小。

圖5 DOI 對(duì)定位誤差的影響

4.2 收斂速度對(duì)比

在錨節(jié)點(diǎn)數(shù)M＝50，通信半徑R＝30 時(shí)的收斂曲線如圖6 所示。 在算法迭代前期MPIO 算法的收斂最快，其次是GPIO、PIO、PSO 和BA。

圖6 不同算法收斂曲線

圖7 和表3 分別顯示了在錨節(jié)點(diǎn)數(shù)M＝40，45，50，55，60 時(shí)不同定位算法的定位時(shí)間和最優(yōu)適應(yīng)度值。 可以看出隨著錨節(jié)點(diǎn)數(shù)量的增加，定位時(shí)間也隨之增加，各定位算法平均定位時(shí)間依次為MLE 0.129 s、PIO 0.881 s、PSO 0.92 s、MPIO 0.95 s、BA 1.04 s、GPIO 1.09 s。 隨著錨節(jié)點(diǎn)數(shù)量的增加各優(yōu)化算法的適應(yīng)度值減小，各優(yōu)化算法的平均適應(yīng)度值依次為MPIO 0.023、GPIO 0.045、PSO 0.049、PIO 0.057、BA 0.323。 由于MLE 算法計(jì)算簡(jiǎn)單所以定位時(shí)間最短，但是由4.1 節(jié)分析可知MLE 算法定位精度較低；BA 具有較長(zhǎng)的定位時(shí)間和較高的最優(yōu)適應(yīng)度值；由于PIO 收斂速度較快所以定位時(shí)間較短，但是由于容易陷入局部最優(yōu)導(dǎo)致PIO 的最優(yōu)適應(yīng)度值高于MPIO；由于GPIO 頻繁使用高斯變異增加種群多樣性提高算法求解精度，使最優(yōu)適應(yīng)度值較低，但是定位時(shí)間最長(zhǎng)；由于MPIO 在PIO 的基礎(chǔ)上進(jìn)行改進(jìn)來(lái)使PIO 跳出局部最優(yōu)，所以定位時(shí)間較PIO 長(zhǎng)，但是具有最低的適應(yīng)度值，算法求解精度最高。

表3 各優(yōu)化算法的最優(yōu)適應(yīng)度值

圖7 錨節(jié)點(diǎn)數(shù)量對(duì)定位時(shí)間的影響

5 總結(jié)

本文針對(duì)PIO 算法容易陷入局部最優(yōu)的缺陷，提出了一種基于改進(jìn)鴿群算法(MPIO)的無(wú)線傳感網(wǎng)絡(luò)定位算法。 MPIO 的第一階段通過(guò)自適應(yīng)調(diào)整機(jī)制來(lái)平衡全局搜索與局部搜索能力，并同時(shí)保證較快收斂速度；第二階段保留全部鴿子并分組，使用隨機(jī)游走等機(jī)制增加種群多樣性，提高了算法的求解精度。 定位過(guò)程中首先使用RSS 進(jìn)行測(cè)距，然后使用MPIO 進(jìn)行定位。 仿真結(jié)果表明，MPIO 算法相比于傳統(tǒng)的定位算法和其他的優(yōu)化算法，具有較高的定位精度和較快的收斂速度。