基于改進NSGA-III算法的DV-Hop三維定位算法

摘? 要：在三維空間節點定位算法中，DV-Hop算法憑借其原理簡單、成本低的優勢得到了大量學者的廣泛關注。針對DV-Hop算法中因計算誤差導致的定位精度較低的問題，研究NSGA-III算法的交叉和變異并進行自適應改進，使得子代個體的進化更加均勻，提高找到全局最優解的概率，減少陷入局部的解空間。最后結合蟻群算法提升了該算法在復雜網絡環境中的定位精度。仿真結果表明，與其他算法相比，文章提出的基于改進NSGA-III和蟻群算法的DV-Hop三維定位算法具有較好的定位精度。

關鍵詞：無線傳感器；DV-Hop；NSGA-III算法；自適應優化；定位精度

中圖分類號：TP18? 文獻標識碼：A? 文章編號：2096-4706（2023）18-0092-08

DV-Hop 3D Location Algorithm Based on Improved NSGA-III Algorithm

HUANG Chenxi

（College of Computer Science and Engineering， Northwest Normal University， Lanzhou? 730070， China）

Abstract： Among the 3D space node positioning algorithms， the DV-Hop algorithm has been widely concerned by a large number of scholars due to its advantages of simple principle and low cost. To solve the problem of low positioning accuracy caused by calculation errors in the DV-Hop algorithm， this paper researches the crossover and mutation of the NSGA-III algorithm and makes adaptive improvements to make the evolution of offspring individuals more uniform and increase the probability of finding the global optimal solution， to reduce the localized solution space. Finally， combined with the Ant Colony Optimization algorithm， the positioning accuracy of the algorithm in the complex network environment is improved. The simulation results show that compared with other algorithms， the DV-Hop 3D positioning algorithm based on improved NSGA-III and Ant Colony Optimization algorithm proposed in this paper has better positioning accuracy.

Keywords： wireless sensor; DV-Hop; NSGA-III algorithm; adaptive optimization; positioning accuracy

0? 引? 言

無線傳感器網絡（Wireless Sensor Network， WSN）是一種在一定監測范圍內隨機分布了眾多低成本、微小的傳感器節點的獨立的無線網絡，既攜帶了溫度、濕度、光照、壓力等不同類型的傳感器以滿足不同的檢測需求，同時整合了信息采集、資料處理和無線通訊等多種功能，在現代化工業、智能農業、醫療、軍事、環境、智能家居等各種重要領域都得到廣泛應用[1，2]。因此，節點定位是無線傳感器網絡方向中非常有研究價值的關鍵技術，如何有效提高在復雜環境下無線傳感器網絡中定位的精確度和效率是研究和應用的關鍵。

定位算法根據定位過程中是否需要測量未知節點與錨節點之間的空間位置關系可大體分為基于測距和非測距兩類。基于測距的定位算法中，常見的有基于到達時間（Time of Arrival， TOA）、基于到達時間差（Time Difference of Arrival， TDOA）、基于到達角度（Angle of Arrival， AOA）和基于接收信號強度值（Received Signal Strength Indicator， RSSI）四種[3，4]。基于非測距的算法中較為常見的有質心算法、DV-Hop定位算法等。由于非測距定位算法對硬件要求不高，在功耗和成本上更具備優勢，因此即使定位精度較低，在低成本、低功耗的無線傳感網絡中也有著廣泛的應用。其中，DV-Hop定位算法因其實現簡單、成本低廉等優勢成為目前應用較為廣泛的一種定位技術[5]。但傳統的DV-Hop定位算法不僅在通過已知節點計算未知節點的位置時存在較大誤差，算法的收斂性性能也較差，所有其算法精度和效率往往無法達到一些工程要求。針對DV-Hop算法定位精度較低的缺點，目前，許多學者已經進行了大量的改進研究。文獻[6]提出了一種基于雙通信半徑的改進DV-Hop定位算法，該算法通過增加通信半徑將距離信標節點較近的未知節點獲得的最小跳數更新為較小的跳數，降低了相同跳數的實際距離差異。文獻[7]提出了一種基于差分進化（DE）和改進的DV-Hop算法的增強型無線傳感器節點定位算法DEIDV-Hop，引入隨機個體的變異操作，增加種群的多樣性，增強DE算法的搜索停滯和早熟收斂性，將粒子群算法的社會學習部分嵌入到交叉操作中，加快了算法的收斂速度，同時也改善了平均每跳距離的潛在誤差問題。文獻[8]提出一種基于高斯-牛頓法的非線性方法改進最小二乘法等線性方法對于DV-Hop算法定位誤差較大的問題。

本文提出了一種基于DV-Hop優化的三維定位算法，將傳統的DV-Hop算法應用到三維空間中，在原始多目標非支配排序遺傳算法（NSGA-III）基礎上利用二進制交叉策略和多項式變異策略進行改進，提高了算法的自適應能力。利用改進的多目標NSGA-III算法局部優化初始估計的未知節點坐標，并和蟻群算法結合[9]，進一步提高算法的定位精度和計算能力，改進算法的性能。

1? 基于改進NSGA-III算法的DV-Hop三維定位算法

在IGD中，di表示A中第i個個體與O中個體的最小歐幾里德距離。隨著GD和IGD數值減小，算法求得的NSGA-III優化算法的解集越接近理論Pareto最優解集，則算法的收斂性和多樣性越好。

2.2? 不同錨節點比例對定位精度的影響

為了觀察錨節點比例和平均定位誤差的關系，在設定好的邊長100 m的無線傳感器網絡監測區域中，將節點通信半徑固定設置為50 m，并保持總節點數不變。通過改變該網絡中錨節點的比例，并使用上述四種方法進行定位仿真，以此來驗證不同的錨節點比例對于平均定位誤差的影響，從而驗證算法的性能，實驗結果如圖6所示。

如圖6，在三種網絡拓撲場景中上述四種定位的平均定位誤差隨著錨節點數量的增加而逐漸降低。相比于傳統的DV-Hop算法，N3-ACO-3DDV-Hop算法的定位精度明顯提升，在三種網絡拓撲場景中的平均定位誤差分別降低了22.1%、14.7%、18.9%。

在單峰和多峰隨機拓撲的場景中，由于早期錨節點比例不足，未知節點無法通過與錨節點之間的信息傳遞獲得更多的錨節點位置信息以進行自身的定位，因而誤差較大，本算法平均定位誤差相對較高。在錨節點比例25%到40%之間，各種算法對于定位誤差改善效果已經不再明顯，平均定位誤差的曲線趨于平緩，這是由于當無線傳感器網絡中錨節點對未知節點所發送的信息已經達到飽和時，錨節點比例的提高對誤差的影響很小。可以看出，在三種網絡拓撲場景中，錨節點比例在20%～40%之間均可以對未知節點實現一個較好的定位效果，而本算法對于錨節點個數的需求明顯低于其他算法，因此在實際應用中，可以取N3-ACO-3DDV-Hop算法錨節點比例為25%，達到一個較好的定位效果的同時，避免錨節點的過度使用，大幅降低了定位成本。

2.3? 不同通信半徑對定位精度的影響

為了驗證不同通信半徑對平均定位誤差的影響，在設定好的邊長100 m的無線傳感器網絡監測區域中，將錨節點比例固定為25%，改變節點通信半徑。使用上述四種方法進行定位仿真，通過對平均定位誤差變化對比分析驗證算法的性能，實驗結果如圖7所示。

如圖7所示，在三種網絡拓撲場景中，上述四種定位算法的平均定位誤差隨著網絡中通信半徑的增加而逐漸降低。傳統DV-Hop算法在少數情況下會出現定位精度高于其他算法的情況，但是在定位過程中存在著較大的不穩定性，而N3-ACO-3DDV-Hop相比于傳統DV-Hop算法，表現出了更好的定位效果，平均定位誤差始終最小，在三種網絡拓撲場景中的平均定位誤差分別降低了25.6%、14.6%、19.7%。

當通信半徑小于30 m時，無線傳感器網絡中的部分傳感器節點還沒有實現連接，可能會造成定位失敗，算法的定位效果較差；當通信半徑在55 m左右時本算法的誤差已經得到明顯降低，之后基本趨于不變；當通信半徑過大時可能會導致難以正確判斷節點之間的最小跳數值，帶來額外的誤差，所以通信半徑并不是越大越好，因此，選擇合適的通信半徑能有效提高定位精度。同時可以看出，本算法在通信范圍較大時也表現出了較好的定位效果，表明該算法可以應用于規模較大的復雜網絡環境中。

2.4? 不同總節點數對定位精度的影響

為了驗證不同總節點數對平均定位誤差的影響，在設定好的邊長100 m的無線傳感器網絡監測區域中，設置節點通信半徑固定為50 m，同時將錨節點比例固定為25%，總節點數從60增加到180，實驗結果如圖8所示。

如圖8所示，可以看出，在三個網絡拓撲場景中，上述四種定位算法的平均定位誤差隨著網絡中總節點數量的增加而逐漸降低。N3-ACO-3DDV-Hop在三種拓撲場景中都顯示出明顯的優勢，尤其是在隨機拓撲場景中，平均定位誤差較低且保持穩定，與傳統DV-Hop算法相比，在三種網絡拓撲場景中的平均定位誤差分別降低了45.3%、18%、29.1%。

在單峰隨機拓撲場景中，當節點數增加到80時，N3-ACO-3DDV-Hop算法顯然可以比其他算法獲得更好的定位效果；然而在多峰值隨機拓撲場景中，受總節點數的改變影響較小，當節點數達到120時才開始表現出明顯的定位優化效果，因為當總節點數較小時，未知節點無法通過通信獲得更多錨節點廣播的位置信息數據包，N3-ACO-3DDV-Hop算法容易陷入局部最優的情況，表明該算法的模型結構更適合復雜的網絡拓撲環境。總節點數較大時，其他三種算法在復雜的網絡拓撲環境中，定位誤差開始略有增大，而本算法依然表現出較好的定位優化效果，因為隨著總節點數的增加，錨節點也相應隨之增加，網絡連通度也得到提升，此時錨節點與未知節點之間得到的跳數和平均跳距也就更貼合真實距離，降低了因跳數和跳距不準確帶來的影響，提高了定位精度，但當總節點個數較多時，錨節點發送的位置參考信息達到飽和，對于提升定位誤差的效果就較小。

4? 結? 論

本文針對傳統DV-Hop算法在復雜三維空間中定位精度較低的問題，提出一種基于改進的NSGA-III算法和蟻群算法優化的DV-Hop三維定位算法。首先利用NSGA-III算法將DV-Hop算法從全局搜索范圍縮小到未知節點估算的局部范圍內進行尋優，降低了算法的復雜度。此外采用模擬二進制交叉和多項式變異針對NSGA-III算法種群的差異進行自適應交叉、變異操作，提高了算法的自適應性，使算法在各種復雜的網絡環境中保持較好的穩定性。最后結合蟻群算法進一步提高算法的定位精度和計算能力。仿真實驗表明，本文提出的N3-ACO-3DDV-Hop定位算法可以有效提高定位精度和收斂性，能耗更低

未來的研究方向主要有：由于大規模無線傳感器網絡中定位環境的復雜性，在今后的實驗中會根據實際環境引入更多的參數，模擬出相對真實的實驗環境，以驗證算法的實際應用意義。考慮到大規模無線傳感器網絡中節點能源受限的問題，未來將對算法的穩定性、復雜度和能耗進行優化。并在現實環境進行相關定位實驗，驗證本文所提出的改進算法對定位精度的實際改進效果。

參考文獻：

[1] KOCAKULAK M，BUTUN I. An overview of Wireless Sensor Networks towards internet of things [C]//2017 IEEE 7th Annual Computing and Communication Workshop and Conference （CCWC）.Las Vegas：IEEE，2017：1-6.

[2] 苗沛然.無線傳感器網絡研究現狀與應用 [J].通信電源技術，2020，37（3）：87-88.

[3] XIE Y. An optimized three-dimensional positioning algorithm for rssi-based wireless sensor network [C]//2021 3rd International Conference on Intelligent Control，Measurement and Signal Processing and Intelligent Oil Field （ICMSP）.Xi'an：IEEE，2021：30-33.

[4] 李江雯.無線傳感器網絡非測距定位算法研究 [D].重慶：重慶大學，2013.

[5] CUI X L，CHEN W B，HAO C. Research on DV-HOP Algorithm for Wireless Sensor Networks [C]//International Conference on Knowledge Management in Organizations.Cham：Springer，2017：534-546.

[6] LI T，WANG C，NA Q. Research on DV-Hop improved algorithm based on dual communication radius [J/OL].EURASIP Journal on Wireless Communications and Networking，2020，2020（1）：113（2020-06-05）.https：//link.springer.com/article/10.1186/s13638-020-01711-7.

[7] HAN D，YU Y，LI K C，et al. Enhancing the Sensor Node Localization Algorithm Based on Improved DV-Hop and DE Algorithms in Wireless Sensor Networks [J].Sensors，2020，20（2）：343.

[8] KAUR A，KUMAR P，GUPTA G P. A novel DV-Hop algorithm based on Gauss-Newton method[C]//2016 Fourth International Conference on Parallel，Distributed and Grid Computing （PDGC）.Waknaghat：IEEE，2016：625-629.

[9] WANG R，HE G，WU X，et al. Multicast Optimization and Node Fast Location Search Method for Wireless Sensor Networks Based on Ant Colony Algorithm [J].Journal of digital information management，2017，15（6）：303-311.

[10] DONG S，ZHANG X G，ZHOU W G. A Security Localization Algorithm Based on DV-Hop Against Sybil Attack in Wireless Sensor Networks [J].Journal of Electrical Engineering and Technology，2020，15（5）：919-926.

[11] KUMAR S K，LOBIYAL D K. Novel DV-Hop localization algorithm for wireless sensor networks [J].Telecommunication Systems，2017（64）：509-524.

[12] OUYANG A，Lu Y，Liu Y，et al. An Improved Adaptive Genetic Algorithm based on DV-Hop for Locating Nodes in Wireless Sensor Networks [J].Neurocomputing，2021，458：500-510.

[13] ISHIBUCHI H，IMADA R，Yu S，et al. Performance comparison of NSGA-II and NSGA-III on various many-objective test problems [C]//Evolutionary Computation. IEEE，2016：3045-3052.

[14] 劉濤，龐博.基于遺傳算法的異構無線傳感器網絡分簇算法 [J].現代電子技術，2022，45（5）：25-30.

[15] BI X，WANG C. An improved NSGA-III algorithm based on objective space decomposition for many-objective optimization [J].Soft computing：A fusion of foundations，methodologies and applications，2017，21（15）：4269-4296.

[16] LONG C，LIAO S，ZOU X，et al. An improved LEACH multi-hop routing protocol based on intelligent ant colony algorithm for wireless sensor networks [J].Journal of Information and Computational Science，2014，11（8）：2747-2757.

作者簡介：黃琛晰（1997—），女，漢族，山東菏澤人，碩士在讀，研究方向：物聯網技術。