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

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

中圖分類號：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? 引? 言

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4? 不同總節(jié)點數(shù)對定位精度的影響

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

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

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

4? 結? 論

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

未來的研究方向主要有：由于大規(guī)模無線傳感器網(wǎng)絡中定位環(huán)境的復雜性，在今后的實驗中會根據(jù)實際環(huán)境引入更多的參數(shù)，模擬出相對真實的實驗環(huán)境，以驗證算法的實際應用意義?？紤]到大規(guī)模無線傳感器網(wǎng)絡中節(jié)點能源受限的問題，未來將對算法的穩(wěn)定性、復雜度和能耗進行優(yōu)化。并在現(xiàn)實環(huán)境進行相關定位實驗，驗證本文所提出的改進算法對定位精度的實際改進效果。

參考文獻：

[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] 苗沛然.無線傳感器網(wǎng)絡研究現(xiàn)狀與應用 [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] 李江雯.無線傳感器網(wǎng)絡非測距定位算法研究 [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] 劉濤，龐博.基于遺傳算法的異構無線傳感器網(wǎng)絡分簇算法 [J].現(xiàn)代電子技術，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—），女，漢族，山東菏澤人，碩士在讀，研究方向：物聯(lián)網(wǎng)技術。