朱子行 陳輝

摘? 要：無線傳感器網(wǎng)絡(luò)具有感知和處理信息的能力，只有當(dāng)被測網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的位置已知時(shí)，節(jié)點(diǎn)傳遞給用戶的信息才有意義。針對(duì)DV-Hop定位中傳統(tǒng)最小二乘法不可避免的精度低的缺點(diǎn)，引入粒子群算法（PSO）和灰狼優(yōu)化器（GWO）來估計(jì)未知節(jié)點(diǎn)位置。粒子群算法具有個(gè)體記憶的特點(diǎn)，采用粒子位置更新代替灰狼個(gè)體位置更新，使灰狼算法在優(yōu)化上具有可記憶性。仿真數(shù)據(jù)表明，改進(jìn)后的算法可以有效降低節(jié)點(diǎn)定位誤差，實(shí)現(xiàn)更高的定位精度。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);DV-Hop;灰狼優(yōu)化器;粒子群算法

中圖分類號(hào)：TN934? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2096-4706（2022）03-0088-04

DV-Hop Positioning Algorithm Based on GWO and PSO Collaborative Optimization

ZHU Zihang， CHEN Hui

（Anhui University of Science & Technology， Huainan? 232001， China）

Abstract： Wireless sensor networks have the ability to sense and process information， and the information passed by the nodes to the user is meaningful only when the location of the nodes within the network under test is known. In view of the inevitable shortcoming of low precision of the traditional least squares method in DV-Hop （distance vector-hop） localization， the Particle Swarm optimization （PSO） and the Gray Wolf Optimizer （GWO） are introduced to estimate unknown node positions. The Particle Swarm optimization has the characteristics of individual memory， and the particle position update is used to replace the gray wolf individual position update， so that the gray wolf algorithm has memory in optimization. The simulation data show that the improved algorithm can effectively reduce the node positioning error and achieve higher positioning accuracy.

Keywords： wireless sensor network; DV-Hop; Grey Wolf Optimizer; Particle Swarm optimization

0? 引? 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）作為信息獲取的重要技術(shù)隨著網(wǎng)絡(luò)信息的快速發(fā)展得到了廣泛使用[1]。近些年來，WSN在城市建筑，路況交通，醫(yī)療軍事，森林農(nóng)田[2]等領(lǐng)域具有廣闊的應(yīng)用前景。識(shí)別網(wǎng)絡(luò)節(jié)點(diǎn)的位置是無線傳感器網(wǎng)絡(luò)中的一個(gè)重要步驟，在不知道節(jié)點(diǎn)位置的情況下收集的信息大多是無意義的。在應(yīng)用WSN時(shí)，傳感器節(jié)點(diǎn)通常采用隨機(jī)部署，特別是對(duì)于大規(guī)模網(wǎng)絡(luò)。因此，每個(gè)節(jié)點(diǎn)的位置信息是不可或缺的。一種解決方案是在每個(gè)節(jié)點(diǎn)上安裝一個(gè)GPS或北斗定位模塊來獲取它們的位置信息，這不僅成本高，而且不實(shí)用，因?yàn)閭鞲衅鞴?jié)點(diǎn)的功耗會(huì)大大增加，每個(gè)節(jié)點(diǎn)的生命周期顯著縮短。此外，在室內(nèi)或者密集環(huán)境中，定位模塊的性能會(huì)下降。另一種解決方案是使一部分節(jié)點(diǎn)裝有定位模塊（錨節(jié)點(diǎn)）和利用一些定位技術(shù)來估計(jì)未知節(jié)點(diǎn)的位置。

目前，WSN定位技術(shù)根據(jù)是否需要硬件輔助測量節(jié)點(diǎn)間的距離分為基于測距和非測距兩大類[3]?；跍y距的定位算法主要包括AOA、TOA、TDOA和RSSI等。非測距的經(jīng)典定位算法主要包括質(zhì)心定位、APIT、DV-Hop等。非測距算法對(duì)相鄰錨節(jié)點(diǎn)的最小數(shù)量有嚴(yán)格的要求，錨節(jié)點(diǎn)數(shù)目越多越容易獲得更高的定位精度[4]。DV-Hop（Distance Vector-Hop）由于它的算法實(shí)現(xiàn)簡單，不需要提供額外硬件設(shè)備，引起了國內(nèi)外眾多廠商、學(xué)者的關(guān)注。該算法的核心原理是通過平均跳距和最小跳數(shù)的乘積來近似傳感器節(jié)點(diǎn)之間的距離，因此難以達(dá)到某些應(yīng)用所要求的定位精度。本文提出一種改進(jìn)的DV-hop定位算法，引入粒子群協(xié)同灰狼算法代替最小二乘法對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行估計(jì)，實(shí)驗(yàn)結(jié)果證明可以有效降低定位誤差，提高定位穩(wěn)定性。

1? 傳統(tǒng)DV-Hop定位算法

1.1? 未知節(jié)點(diǎn)定位過程

DV-Hop定位是一種基于距離矢量路由機(jī)制的非測距定位算法[5]。該算法是由NICULESCU D.和NATH B在2003年提出的，根據(jù)節(jié)點(diǎn)間的距離選擇最佳路徑進(jìn)行定位。無線傳感器網(wǎng)絡(luò)包含兩種節(jié)點(diǎn)：信標(biāo)節(jié)點(diǎn)（Anchor Node， AN）和未知節(jié)點(diǎn)（Unknown Node， UN）。DV-Hop算法步驟為：

（1）求節(jié)點(diǎn)之間的最小跳數(shù)。每個(gè)節(jié)點(diǎn)通過距離矢量路由交換原理接收到從ANi發(fā)送的數(shù)據(jù)包。在數(shù)據(jù)包廣播過程中，鄰居節(jié)點(diǎn)收到數(shù)據(jù)包時(shí)，包內(nèi)跳數(shù)值增加1并轉(zhuǎn)發(fā)出去。如果節(jié)點(diǎn)接收到來自同一個(gè)信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包，保留較小跳數(shù)值的數(shù)據(jù)包。

（2）計(jì)算ANi的平均每跳距離：

（1）

式中hij是ANi和ANj之間的最小跳數(shù)值。（xi，yi），（xj，yj）分別是ANi，ANj的坐標(biāo)。AN依據(jù)公式（1）得到平均跳距后，把自身的平均跳距廣播給其他節(jié)點(diǎn)。鄰居節(jié)點(diǎn)接收信息后將跳數(shù)加1并繼續(xù)廣播（如果收到多個(gè)節(jié)點(diǎn)廣播的信息，只接收第一個(gè)到達(dá)的信息），然后通過公式（2）來計(jì)算出自身和AN之間的距離：

（2）

其中hui是ANi到UNu的最小跳數(shù)，Hopsizei為ANi所在路徑的平均跳距。

（3）求出UN和AN之間的距離后通過最小二乘法來估計(jì)未知節(jié)點(diǎn)的位置。設(shè)UNm的坐標(biāo)為（x，y），ANi的位置是（xi，yi），UNm到ANi的距離為di則：

（3）

為了使方程組線性化，將式（3）轉(zhuǎn)換為AX=B的方程。A，B，X由下式得出：

（4）

最后根據(jù)最小二乘法我們得到未知節(jié)點(diǎn)的位置為：

（5）

1.2? 誤差分析

1.2.1? 跳數(shù)不精確問題

根據(jù)DV-Hop跳數(shù)定義規(guī)則，將信標(biāo)節(jié)點(diǎn)與通信范圍內(nèi)其他節(jié)點(diǎn)之間視為1跳，這必然會(huì)導(dǎo)致較大的誤差。如圖1所示。信標(biāo)節(jié)點(diǎn)a發(fā)送數(shù)據(jù)包時(shí)，未知節(jié)點(diǎn)a1、b、c接收到數(shù)據(jù)包并都記錄為1跳。但明顯能看出三個(gè)未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)a之間的距離并不相等，因此這種方法計(jì)算跳數(shù)時(shí)會(huì)累積更多的誤差。

1.2.2? 未知節(jié)點(diǎn)坐標(biāo)的計(jì)算方法不合理

采用最小二乘法或最大似然估計(jì)求解矩陣形式的方程組，可能導(dǎo)致無解或逆矩陣的情況，影響定位結(jié)果。

2? 改進(jìn)算法

2.1? PSO算法

粒子群優(yōu)化算法是一種智能計(jì)算領(lǐng)域的群優(yōu)化算法，該算法通過模擬鳥群捕食過程中每只鳥的活動(dòng)來達(dá)到函數(shù)優(yōu)化的目的[6]。PSO算法的本質(zhì)是粒子在空間中不斷地向特定方向變速運(yùn)動(dòng)，并通過自身的記憶和群體通信找到下一個(gè)位置，從而找到最優(yōu)解。速度和位置的更新公式為：

vi（t+1）=vi（t）+c1×rand（）×（pbesti-xi（t））

+c2×rand（）×（gbestj-xi（t））（6）

xi（t+1）=xi（t）+vi（t+1）? （7）

2.2? GWO算法

灰狼優(yōu)化器（Grey Wolf Optimizer， GWO）模擬自然界中灰狼的領(lǐng)導(dǎo)水平和狩獵機(jī)制[7]?；依峭ǔ１环Q為頂級(jí)掠食者，也就意味著它們在食物鏈中處于首位。它們通常以5～12只成群生存，具有嚴(yán)格的社會(huì)等級(jí)地位。四種類型的灰狼α、β、δ、ω，在設(shè)計(jì)GWO時(shí)需要將狼的社會(huì)等級(jí)抽象為合適的數(shù)學(xué)模型。默認(rèn)第一等級(jí)（最優(yōu)解）為α，第二和第三等級(jí)分別為β和δ，剩余的候選解為ω。在GWO算法中，搜索時(shí)由（α，β，δ）引導(dǎo)，ω跟隨前三等級(jí)的狼?；依轻鳙C方法涉及三個(gè)階段，接近受害者、包圍受害者和攻擊受害者。A>1表示灰狼與獵物分離以確定最佳攻擊目標(biāo)。確定攻擊目標(biāo)后，狼群包圍獵物可表示為：

（8）

t為當(dāng)前迭代次數(shù)，X為狼的位置，Xp為獵物的位置，D為獵物與狼之間的距離，r1，r2∈[0，1]，a∈[0，2]。包圍獵物后，我們認(rèn)為（α，β，δ）是三種可能的解，它們的位置隨著獵物的移動(dòng)而變化。狼群追逐行為可以表示為：

（9）

2.3? 混合策略

單一的群體智能算法會(huì)受到自身搜索能力的限制，在處理一些復(fù)雜的問題時(shí)，會(huì)出現(xiàn)求解精度低，容易陷入局部最優(yōu)等問題[8]。而混合優(yōu)化算法可以通過不同種群之間的信息交換來達(dá)到提高算法性能的目的?，F(xiàn)有的混合算法大多數(shù)按照使用順序來優(yōu)化目標(biāo)，不能相互結(jié)合。因此，PSO-GWO更像是一種并行算法，同時(shí)工作和兼顧算法的收斂速度和準(zhǔn)確性。本文采用粒子群算法具有個(gè)體記憶的特點(diǎn)，采用粒子位置更新代替灰狼個(gè)體位置更新，使灰狼算法在優(yōu)化上具有可記憶性。通常調(diào)整慣性常數(shù)w來協(xié)調(diào)混合算法平衡全局搜索和局部開發(fā)能力，w的變化范圍為[0.5，1]。則上式（6）變成了（10）：

（10）

公式（9）中三個(gè)狼到獵物之間的距離變?yōu)椋?1）：

（11）

適應(yīng)度函數(shù)設(shè)置為：

（12）

其中，（x，y）為待測節(jié)點(diǎn)的坐標(biāo)，（xi，yi）為信標(biāo)節(jié)點(diǎn)i的坐標(biāo)，di為信標(biāo)節(jié)點(diǎn)i到未知節(jié)點(diǎn)的距離。

粒子群混合灰狼優(yōu)化算法的具體實(shí)現(xiàn)流程為：

（1）初始化a、A、C的值，設(shè)置灰狼種群大小為N;

（2）初始化種群個(gè)體，同時(shí)計(jì)算灰狼的適應(yīng)度;

（3）取適應(yīng)度值前三位的個(gè)體α、β、δ，其對(duì)應(yīng)的位置信息為Xα、Xβ、Xδ;

（4）使用公式（8）更新A和C的值，根據(jù)公式（10）更新灰狼個(gè)體位置，返回步驟2重新計(jì)算并更新α、β、δ;

（5）如果迭代次數(shù)t>tmax則認(rèn)為灰狼已經(jīng)找到最優(yōu)解的位置。否則返回第三步繼續(xù)尋找更好的位置。

3? 實(shí)驗(yàn)仿真

在本節(jié)中，我們使用仿真來評(píng)估改進(jìn)算法的性能。我們把無線傳感器網(wǎng)絡(luò)部署在正方形區(qū)域內(nèi)，每個(gè)傳感器節(jié)點(diǎn)的空間坐標(biāo)都是隨機(jī)選擇的。所有節(jié)點(diǎn)的定位誤差是整個(gè)仿真過程中唯一的判斷標(biāo)準(zhǔn)，從節(jié)點(diǎn)總數(shù)，錨節(jié)點(diǎn)的占總節(jié)點(diǎn)數(shù)的比例，節(jié)點(diǎn)傳輸半徑來分析算法的定位誤差。節(jié)點(diǎn)定位誤差公式為[9]：

（13）

其中（x，y）是未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，（xture，yture）是未知節(jié)點(diǎn)的真實(shí)坐標(biāo)。R為節(jié)點(diǎn)的通信半徑。仿真環(huán)境如表1所示。

如圖2、圖3、圖4所示，分別是傳統(tǒng)DV-Hop、基于PSO改進(jìn)的DV-Hop和基于PSO-GWO改進(jìn)的DV-Hop算法在100 m×100 m的正方形區(qū)域、通信半徑固定為30 m、信標(biāo)節(jié)點(diǎn)的比例為20%的環(huán)境下每個(gè)節(jié)點(diǎn)的誤差分析圖。從三幅圖上面能夠看出來本文改進(jìn)后的未知節(jié)點(diǎn)的定位誤差相比于其他三個(gè)算法都更加精確。

如圖5所示，是信標(biāo)節(jié)點(diǎn)不同比例的節(jié)點(diǎn)定位誤差示意圖。其中在網(wǎng)絡(luò)中設(shè)置了200個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)的傳輸半徑為30 m。x軸代表信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)，y軸表示節(jié)點(diǎn)的定位誤差。從圖中可以看出，當(dāng)信標(biāo)節(jié)點(diǎn)個(gè)數(shù)逐漸增加時(shí)，節(jié)點(diǎn)的定位精度也相應(yīng)提高。

如圖6所示，是改變節(jié)點(diǎn)傳輸半徑時(shí)的定位誤差示意圖。其中在網(wǎng)絡(luò)中設(shè)置了200個(gè)傳感器節(jié)點(diǎn)，設(shè)置信標(biāo)節(jié)點(diǎn)的比例為15%。當(dāng)節(jié)點(diǎn)的傳輸半徑增加時(shí)，節(jié)點(diǎn)的通信范圍擴(kuò)大，使得節(jié)點(diǎn)之間的最小跳數(shù)相對(duì)降低，迭代誤差也會(huì)相對(duì)降低，節(jié)點(diǎn)誤差率降低。

如圖7所示，是網(wǎng)絡(luò)節(jié)點(diǎn)增加時(shí)節(jié)點(diǎn)的定位誤差示意圖。設(shè)置節(jié)點(diǎn)的傳輸半徑為25 m，錨節(jié)點(diǎn)的比例保持20%。從圖中可以看出，隨著傳感器節(jié)點(diǎn)數(shù)目的增加，節(jié)點(diǎn)的定位精度也在不斷提高。

4? 結(jié)? 論

文章提出了一種改進(jìn)的DV-Hop方法，用于提高無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位精確度。該算法使用粒子群優(yōu)化算法和灰狼優(yōu)化器協(xié)同運(yùn)算估計(jì)節(jié)點(diǎn)位置，而不是傳統(tǒng)DV-Hop算法中使用最小二乘法來估計(jì)。兩種群優(yōu)化算法的協(xié)同處理增強(qiáng)了跳出局部最優(yōu)的能力，能夠更好地找到全局最優(yōu)解。實(shí)驗(yàn)結(jié)果證明能夠有效地降低節(jié)點(diǎn)定位誤差，而且不需要額外的硬件。但是雙優(yōu)化算法使得定位算法的速度有所降低，未來的工作將考慮提升定位速度。

參考文獻(xiàn)：

[1] FAN Z，CHU H，WANG F，et al.A New Non-Line-of-Sight Localization Algorithm for Wireless Sensor Network [C]//2020 IEEE 6th International Conference on Computer and Communications （ICCC）.Chengdu：IEEE，2020：858-862.

[2] 繆祎晟，趙春江，吳華瑞.信道與能耗感知的農(nóng)田WSN機(jī)會(huì)路由優(yōu)化方法 [J].重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2021，35（9）：1-7.

[3] 楊艷芳，王偉，王召巴.基于WSN室內(nèi)定位的路徑損耗模型參數(shù)算法研究 [J].電子測量技術(shù)，2021，44（13）：54-58.

[4] KANWAR V，KUMAR A.“Distance Vector Hop Based Range Free Localization in WSN using Genetic Algorithm” [C]//2019 6th International Conference on Computing for Sustainable Global Development （INDIACom）.New Delhi：IEEE，2019：724-728.

[5] NICULESCU D，NATH B.DV Based Positioning in Ad Hoc Networks [J]. Telecommunication Systems，2003，22（1-4）：267-280.

[6] AZAD J，KANWAR V，KUMAR A.Effect of Network Topologies on Localization using DV-Hop based PSO Algorithm [C]//2021 5th International Conference on Trends in Electronics and Informatics （ICOEI）.Tirunelveli：IEEE，2021：40-45.

[7] 石琴琴，徐強(qiáng)，張建平.基于距離修正及灰狼優(yōu)化算法對(duì)DV-Hop定位的改進(jìn) [J].傳感技術(shù)學(xué)報(bào)，2019，32（10）：1549-1555.

[8] 李真，王帆，王冉珺.一種結(jié)合灰狼算法的粒子群優(yōu)化算法 [J].計(jì)算機(jī)測量與控制，2021，29（10）：217-222.

[9] 吳之舟，張玲華.基于加權(quán)和RSSI測距的DV？Hop定位算法 [J].數(shù)據(jù)采集與處理，2021，36（6）：1217-1225.

作者簡介：朱子行（1998—），男，漢族，安徽淮北人，在讀碩士，研究方向：無線傳感器網(wǎng)絡(luò)定位方向;通訊作者：陳輝（1973—），男，漢族，安徽廬江人，副教授，碩士生導(dǎo)師，博士，研究方向：無線傳感器網(wǎng)絡(luò)，機(jī)器學(xué)習(xí)、物聯(lián)網(wǎng)技術(shù)及應(yīng)用。