摘 要 在無線傳感器網(wǎng)絡中，傳統(tǒng)DV-Hop（Distance Vector-Hop）算法因跳數(shù)和平均跳距計算存在較大偏差，從而對未知節(jié)點定位產(chǎn)生較大誤差. 針對該問題，設計了基于多通信半徑和改進麻雀搜索的DV-Hop定位算法. 首先采用多通信半徑修正節(jié)點間的跳數(shù)，使跳數(shù)值較真實反映兩個節(jié)點間的距離. 其次采用修正的跳數(shù)去修正信標節(jié)點的平均跳距，從而獲得未知節(jié)點到各信標節(jié)點修正后的距離. 最后采用麻雀搜索算法（Sparrow Search Algorithm，SSA）估算未知節(jié)點位置，將節(jié)點定位問題轉化為函數(shù)尋優(yōu)問題. 針對麻雀搜索算法前期容易陷入局部最優(yōu)解，后期尋優(yōu)精度不高的問題，提出將Levy飛行策略引入麻雀搜索算法中，提升算法的全局尋優(yōu)能力. 仿真結果表明，與傳統(tǒng)DV-Hop算法、SSA DV-Hop算法相比，改進SSA DV-Hop算法的定位精度明顯提高.

關鍵詞 無線傳感器網(wǎng)絡；節(jié)點定位；多通信半徑；麻雀搜索算法；Levy策略

中圖分類號 TP393.07 文獻標識碼 A

1 引 言

無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）的主要思路是利用各種傳感器節(jié)點協(xié)同對環(huán)境進行監(jiān)測，獲取環(huán)境實時信息，最后將環(huán)境信息和節(jié)點位置無線傳輸?shù)接脩舳? 無線傳感器網(wǎng)絡由傳感器節(jié)點（下文簡稱“節(jié)點”）、匯聚節(jié)點、Internet、管理節(jié)點四部分組成，傳感器節(jié)點分布在指定的監(jiān)測區(qū)域內(nèi)，采集目標環(huán)境實時信息，并將環(huán)境信息和節(jié)點自身位置經(jīng)過“多跳”發(fā)送到匯聚節(jié)點. 匯聚節(jié)點對傳感器節(jié)點傳輸過來的數(shù)據(jù)進行合成和處理，然后經(jīng)Internet等通訊網(wǎng)絡到達管理節(jié)點，用戶通過管理節(jié)點對整個WSN進行動態(tài)管理和資源訪問，如圖1所示.

傳感器節(jié)點是WSN中最活躍的成份，分為信標節(jié)點和未知節(jié)點兩類. 信標節(jié)點因裝有GPS裝置而獲得自身精確位置；未知節(jié)點因未裝GPS裝置，需要借助信標節(jié)點的位置信息來確定自身位置.

節(jié)點定位技術分為兩類：基于測距定位和無需測距定位[1]. 基于測距定位是通過實際測量節(jié)點間的距離來獲取目標節(jié)點位置. 其定位精度高，但硬件成本也高，常見算法有AOA、TOA、TDOA、RSSI等. 無需測距定位是通過相互通信和連通性來估計節(jié)點的位置. 優(yōu)點是無需額外添加硬件，缺點是定位精度低，常見算法有DV-Hop算法、質(zhì)心算法等.

DV-Hop算法因實現(xiàn)簡單、成本低廉，成為目前最流行的節(jié)點定位技術之一，其定位精度也成為廣大學者的關注熱點. 文獻[2]采用RSSI和誤差修正的方法改進DV-Hop算法，對未知節(jié)點的定位精度有一定程度的提高，但還不理想. 文獻[3]提出基于麻雀搜索的DV-Hop改進算法，其全局搜索能力強，收斂速度快，能有效獲取未知節(jié)點最佳位置，但前期容易陷入局部最優(yōu)解，后期尋優(yōu)精度不高. 本文提出一種基于Levy飛行策略的麻雀搜索算法（Improved Sparrow Search Algorithm，ISSA），有效避免搜索過程陷入局部最優(yōu)的情況，極大提高收斂速度和求解精度.

2 DV-Hop定位算法與誤差分析

2.1 傳統(tǒng)DV-Hop算法

DV-Hop定位算法分三個階段：

第一階段：距離矢量交換. 信標節(jié)點定期向鄰居節(jié)點廣播數(shù)據(jù)包，該數(shù)據(jù)包包含ID、節(jié)點坐標和初值為0的跳數(shù). 鄰居節(jié)點接收該數(shù)據(jù)包，把跳數(shù)值修改為1后轉發(fā)給下一個節(jié)點[4]. 若一個節(jié)點收到第二個ID相同的數(shù)據(jù)包時，首先對跳數(shù)加1，然后放棄跳數(shù)較大的數(shù)據(jù)包，僅保留和轉發(fā)跳數(shù)較小的數(shù)據(jù)包.

在第一階段結束時，每個信標節(jié)點獲得WSN中其余信標節(jié)點的坐標和跳數(shù)值.

第二階段：計算平均跳距. 每個信標節(jié)點i（xi，yi）利用其余信標節(jié)點j（xj，yj）的坐標和跳數(shù)值，計算自己的平均跳距：

其中hij為信標節(jié)點i與j之間的跳數(shù).

信標節(jié)點向WSN廣播其平均跳距. 未知節(jié)點選擇與自已最近的信標節(jié)點的平均跳距作為自已的平均跳距，并估算自己到各信標節(jié)點的距離. 假設未知節(jié)點V選擇的平均跳距為Hopsizei，則V與三個信標節(jié)點i、j、k的估算距離分別為：

第三階段：未知節(jié)點估算自身的坐標. 未知節(jié)點依據(jù)自己與3個及以上信標節(jié)點間的估算距離，利用極大似然估計法對自身坐標進行計算.

2.2 DV-Hop定位誤差分析

當WSN節(jié)點分布不均勻時，計算跳數(shù)和平均跳距偏差較大，從而對未知節(jié)點坐標的估算產(chǎn)生較大誤差.

（1） 跳段長短不一導致跳數(shù)的誤差.

在傳統(tǒng)DV-Hop第一階段中，只要兩節(jié)點的間距不大于通信半徑，就認為兩節(jié)點的跳數(shù)為1. 但在實際場景中，相鄰兩節(jié)點間的距離有長有短，簡單記1跳會引起定位誤差[5].

（2） 跳數(shù)誤差導致平均跳距估算的誤差.

在傳統(tǒng)DV-Hop第二階段中，未知節(jié)點估算自己到各信標節(jié)點的距離時，將離自己最近的信標節(jié)點平均跳距作為自已平均跳距. 如果平均跳距本身有誤差，就影響未知節(jié)點到各信標節(jié)點的距離估算.

（3） 未知節(jié)點到各信標節(jié)點的距離不是直線距離.

利用極大似然估計法估算未知節(jié)點坐標時，需要事先獲得未知節(jié)點到3個及以上信標節(jié)點的直線距離. 但在傳統(tǒng)DV-Hop第三階段中，未知節(jié)點到3個及以上信標節(jié)點的距離卻是第二階段獲得的估算距離，造成未知節(jié)點坐標計算的誤差.

3 麻雀搜索算法與改進

3.1 麻雀搜索算法的描述

麻雀搜索算法（SSA）是一種模擬麻雀覓食和反捕食行為，尋求最優(yōu)位置的群體智能優(yōu)化算法，具有尋優(yōu)能力強、收斂速度快、易于實現(xiàn)等特點，因此在不同的領域得到廣泛應用. 它將麻雀種群分為發(fā)現(xiàn)者、追隨者、預警者三類. 發(fā)現(xiàn)者能量較高，負責搜索食物，并為整個種群提供覓食區(qū)域和方向[6]，在種群中占比約為20%；追隨者則利用發(fā)現(xiàn)者來獲取食物，在種群中占比約為80%；在種群中隨機選擇10%-20%的個體，用于感應天敵則稱為預警者.

4 基于改進麻雀搜索的DV-Hop定位算法

針對DV-Hop節(jié)點定位誤差，本文在DV-Hop算法中融入ISSA，從節(jié)點間的跳數(shù)修正、平均跳距修正和坐標誤差修正幾個方面加以改進，將無線傳感器節(jié)點定位問題轉化為函數(shù)尋優(yōu)問題，以提高節(jié)點定位精度.

4.1 節(jié)點收到數(shù)據(jù)包時的跳數(shù)修正

在傳統(tǒng)DV-Hop算法中，采用單一通信半徑R，不管兩個相鄰節(jié)點相距多少，都標記為一跳[13]，如圖2所示，節(jié)點A分別與節(jié)點B、C、D、E間的跳數(shù)都記1，但AB、AC、AD、AE的距離相差甚大.

其中，M為信標節(jié)點的個數(shù)，dVi為未知節(jié)點V到信標節(jié)點i修正后的距離. 把（11）式嵌入ISSA算法中，便可求出每個未知節(jié)點的最優(yōu)適應度，最優(yōu)適應度對應的位置就是未知節(jié)點修正后的位置.

4.4 改進DV-Hop算法流程

基于多通信半徑和ISSA的DV-HOP節(jié)點定位算法如下：

（1） 信標節(jié)點i依次以通信半徑R/4、R/2、3R/4在網(wǎng)絡中廣播一個包含ID，（xi，yi），h′i（初值為0）的數(shù)據(jù)包，其中，h′i為跳數(shù)，R為最大通信半徑. 鄰居節(jié)點收到該數(shù)據(jù)包后，根據(jù)自己與信標節(jié)點i的距離分別將h′i修改為0.25、0.5、0.75.

（2） 信標節(jié)點i又以通信半徑R在網(wǎng)絡中廣播一個包含ID，（xi，yi），h′i（初值為0）的數(shù)據(jù)包，與信標節(jié)點i距離介于（R，R]的鄰居節(jié)點A接收該數(shù)據(jù)包，并把h′i修改為1后再分4種通信半徑轉發(fā)給下一個鄰居節(jié)點.

（3） 之后，節(jié)點A依次以通信半徑R/4、R/2、3R/4轉發(fā)信標節(jié)點i的數(shù)據(jù)包，節(jié)點A的鄰居節(jié)點收到該數(shù)據(jù)包后，首先提取該數(shù)據(jù)包中的h′i值，根據(jù)自己與節(jié)點A的距離分別在原來h′i值的基礎上加上0.25、0.5、0.75. 然后將該數(shù)據(jù)包的ID與已存儲的每個數(shù)據(jù)包ID進行比較，如果未找到相同的，則保留該數(shù)據(jù)包. 如果找到相同的，則將該數(shù)據(jù)包的跳數(shù)與相同ID的跳數(shù)比較，如果前者大于后者，則將該數(shù)據(jù)包丟掉；否則保留該數(shù)據(jù)包.

（4） 節(jié)點A又以通信半徑R轉發(fā)信標節(jié)點i的數(shù)據(jù)包，與節(jié)點A距離介于（R，R]的鄰居節(jié)點B接收該數(shù)據(jù)包后，首先提取該數(shù)據(jù)包中的h′i值并修改為：h′i＝h′i＋1，然后將該數(shù)據(jù)包的ID與已存儲的每個數(shù)據(jù)包ID進行比較，如果未找到相同的，則保留并分4種通信半徑轉發(fā)該數(shù)據(jù)包. 如果找到相同的，則將該數(shù)據(jù)包的跳數(shù)與相同ID的跳數(shù)比較，如果前者大于后者，則將該數(shù)據(jù)包丟掉；否則保留并分4種通信半徑轉發(fā)該數(shù)據(jù)包.

（5） 重復（3）、（4），直至信標節(jié)點i的數(shù)據(jù)包轉發(fā)給WSN中的每個節(jié)點.

（6） 重復（1） - （5），直至每個信標節(jié)點都向WSN發(fā)送數(shù)據(jù)包.

（7） 利用（9）式計算信標節(jié)點i，j，k的平均跳距.

（8） 利用（10）式計算未知節(jié)點V到信標節(jié)點i、j、k的估算距離.

（9） 把未知節(jié)點看成麻雀，按（11）式構建未知節(jié)點的適應度函數(shù).

（10） 根據(jù)本文提出的ISSA算法流程，求出每個未知節(jié)點的最優(yōu)適應度，最優(yōu)適應度對應的位置就是未知節(jié)點修正后的位置.

5 仿真實驗與結果分析

為了驗證本文設計的ISSA DV-Hop算法的定位精度，并與傳統(tǒng)DV-Hop算法、SSA DV-Hop算法進行對比，本文選擇MATLAB2022作為仿真平臺，在100 m×100 m的仿真區(qū)域中，隨機放置100個傳感器節(jié)點，所有節(jié)點的通信半徑為R. 在麻雀搜索算法中，迭代次數(shù)設為100，把未知節(jié)點看作麻雀，未知節(jié)點個數(shù)就是種群規(guī)模.

5.1 一次仿真實驗的絕對定位誤差對比

在100 m×100 m的仿真區(qū)域中，設置100個傳感器節(jié)點，其中信標節(jié)點20個，非信標節(jié)點80個，節(jié)點最大通信半徑為30 m，則采用傳統(tǒng)DV-Hop算法、SSA DV-Hop算法和本文改進算法，求得的每個未知節(jié)點的絕對定位誤差如圖3所示.

根據(jù)圖3可知，三種算法絕對定位誤差的最大值、最小值和平均值如表1所示. 本文改進算法與傳統(tǒng)DV-Hop算法、SSA DV-Hop算法相比，絕對定位誤差分別下降6.56 m、3.09 m，表明本文改進算法的定位精度明顯高于其他兩種算法.

下面通過改變最大通信半徑、信標節(jié)點數(shù)來評估三種算法的定位精度.

5.2 最大通信半徑對定位精度的影響

信標節(jié)點固定20個，節(jié)點最大通信半徑分別取25 m、30 m、35 m、40 m、45 m、50 m，實驗得到三種算法的相對定位誤差如圖4所示.

根據(jù)圖4可知，節(jié)點的最大通信半徑越大，三種算法的相對定位誤差越小. 因為通信半徑越大，通信區(qū)域內(nèi)信標節(jié)點數(shù)越多，未知節(jié)點越能準確獲得自身位置. 本文改進算法的誤差曲線在三條曲線中一直處于最下方，表明其具有最佳的節(jié)點定位精度. 例如，當最大通信半徑取50 m時，傳統(tǒng)DV-Hop算法、SSA DV-Hop算法、本文改進算法的相對定位誤差分別為25%、15.1%和5.3%，本文改進算法與傳統(tǒng)DV-Hop算法、SSA DV-Hop算法相比，定位誤差分別下降19.7%、9.8%.

5.3 信標節(jié)點數(shù)對未知節(jié)點定位精度的影響

最大通信半徑固定為30 m，信標節(jié)點數(shù)分別取5、10、15、20、25、30，實驗得到三種算法的相對定位誤差如圖5所示.

根據(jù)圖5可知，信標節(jié)點數(shù)越多，三種算法的相對定位誤差越小. 因為信標節(jié)點數(shù)越多，節(jié)點間的跳數(shù)更能反映網(wǎng)絡真實情況. 本文改進算法的誤差曲線在三條曲線中一直處于最下方，表明其具有最佳的節(jié)點定位精度. 例如，當信標節(jié)點數(shù)取30時，傳統(tǒng)DV-Hop算法、SSA DV-Hop算法、本文改進算法的相對定位誤差分別為29%、18%和8%，本文改進算法與傳統(tǒng)DV-Hop 算法、SSA DV-Hop算法相比，定位誤差分別下降21%、10%.

6 結束語

本文首先闡述了傳統(tǒng)DV-HOP算法定位誤差的原因；然后，分析了麻雀搜索算法的優(yōu)缺點，在麻雀搜索算法中引入Levy飛行策略，并設計了基于Levy飛行策略的麻雀搜索算法流程；接著，提出一種改進麻雀搜索的DV-Hop定位算法：一是采用多通信半徑修正節(jié)點間的跳數(shù)；二是采用修正后的跳數(shù)修正信標節(jié)點平均跳距；三是采用改進的麻雀搜索算法估算未知節(jié)點位置，將節(jié)點定位問題轉化為函數(shù)尋優(yōu)問題. 最后，通過仿真實驗，對傳統(tǒng)DV-Hop算法、SSA DV-Hop算法和本文改進算法進行比較，結果表明本文改進算法定位誤差最小，定位精度最高.

參考文獻

[1]" 李鳳超，高美鳳. 無線傳感器網(wǎng)絡中改進的DV-Hop定位算法[J]. 傳感器與微系統(tǒng)，2018，37（2）：124-126.

[2]" JIA Y，ZHANG K，ZHAO L. Improved DV-Hop location algorithm based on mobile anchor node and

modified hop count for wireless sensor network[J]. Journal of Electrical and Computer Engineering，2020，2020（4）：1-9.

[3]" XUE J K，SHEN B. A novel swarm intelligence optimization approach：sparrow search algorithm[J].

Systems Science ＆ Control Engineering an Open Access Journal，2020，8（1）：22-34.

[4]" ZHU P，XU B，LI J，et al. Joint utility optimization for wireless sensor networks with energy harvesting

and cooperation[J]. Science China Information Sciences，2020，63（2）：1-14.

[5]" 周凱，周培釗，付文涵，等. 無線傳感器網(wǎng)絡的改進DV-hop定位算法研究[J]. 東北師大學報（自然科學版），2021，53（4）：137-143.

[6]" 汪嘉寶. 基于改進麻雀搜索算法的無線傳感器網(wǎng)絡覆蓋優(yōu)化算法研究[D]. 贛州：江西理工大學，2022.

[7]nbsp; 馬衛(wèi)，朱嫻. 基于萊維飛行擾動策略的麻雀搜索算法[J]. 應用科學學報，2022，40（1）：116-130.

[8]" 顏慧超，曾子維，王剛. 融合跳距修正與麻雀搜索的改進DV-Hop算法[J]. 電子測量技術，2021，

44（21）：133-138.

[9]" 段中興，劉瑞興，劉沖. 多策略改進麻雀搜索算法優(yōu)化3DDV-Hop節(jié)點定位[J]. 吉林大學學報（工學版）：已接受.

[10]" 劉瑞興，段中興. 基于改進SSA的DV-Hop傳感器定位算法[J]. 兵器裝備工程學報，2022，43（10）：280-287.

[11]" 彭鐸，楊雅文，高玉蔚，等. 基于多通信半徑和麻雀搜索的節(jié)點定位算法[J]. 傳感技術學報，2021，34（11）：1523-1529.

[12]" 楊雅文. 基于多通信半徑的節(jié)點定位智能優(yōu)化算法[D]. 蘭州：蘭州理工大學，2022.

[13]" 余成成，徐巍，鐘宇超，等. 基于多通信半徑和改進遺傳算法的DV-Hop定位[J]. 儀表技術與傳感器，2023（2）：99-103+120.

[14]nbsp; LI T C，WANG C Z，NA Q. Research on DV-Hop improved algorithm based on dual communication

radius[J]. EURASIP，Journal on Wireless Communications and Networking，2020，113：1-10.

[15]" CHAI Q W，CHU S C，PAN J S，et al. A parallel WOA with two communication strategies applied

in DV-Hop localization method[J]. EURASIP Journal on Wireless Communications and Networking，2020，50：1-10.

Research on DV-HOP Node Location Based on Multi-Communication Radius and Improved Sparrow Search Algorithm

CHEN Mingzhong， JIANG Yongchi

（Shantou Polytechnic， Shantou 515078， Guangdong， China）

Abstract" Traditional DV-Hop algorithms have large errors in locating unknown nodes due to large deviations in hop count and average hop distance calculations in wireless sensor networks. A DV-Hop localization algorithm based on multiple communication radii and improved sparrow search was designed to address this issue. Firstly， multiple communication radii are used to correct the number of hops between nodes， so that the hop number values reflect the distance between two nodes more accurately. Secondly， the modified hop number is used to correct the average hop distance of the beacon nodes， in order to obtain the corrected distance from the unknown node to each beacon node. Finally， the sparrow search algorithm （SSA） is used to estimate the location of unknown nodes， and the node location problem is transformed into a function optimization problem. Aiming at the problem that Sparrow search algorithm is easy to fall into local optimal solution in the early stage and low optimization accuracy in the later stage， Levy flight strategy is introduced into Sparrow search algorithm to improve its global optimization ability. The simulation results show that compared with traditional DV-Hop algorithm and SSA DV-Hop algorithm， the improved SSA DV-Hop algorithm significantly improves the positioning accuracy.

Keywords" wireless sensor network; node positioning; multiple communication radius; Sparrow search algorithm; Levy strategy

收稿日期：2023 － 09 － 11

作者簡介：陳明忠（1968—），男，漢族，廣東汕頭人，碩士，副教授，研究方向：網(wǎng)絡工程amp;物聯(lián)網(wǎng)技術.

E-mail：cmzgjjx@163.com

基金項目：廣東省普通高校特色創(chuàng)新項目（2020KTSCX305）