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

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

中圖分類號(hào)：TP18? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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ú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是一種在一定監(jiān)測(cè)范圍內(nèi)隨機(jī)分布了眾多低成本、微小的傳感器節(jié)點(diǎn)的獨(dú)立的無(wú)線網(wǎng)絡(luò)，既攜帶了溫度、濕度、光照、壓力等不同類型的傳感器以滿足不同的檢測(cè)需求，同時(shí)整合了信息采集、資料處理和無(wú)線通訊等多種功能，在現(xiàn)代化工業(yè)、智能農(nóng)業(yè)、醫(yī)療、軍事、環(huán)境、智能家居等各種重要領(lǐng)域都得到廣泛應(yīng)用[1，2]。因此，節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)方向中非常有研究?jī)r(jià)值的關(guān)鍵技術(shù)，如何有效提高在復(fù)雜環(huán)境下無(wú)線傳感器網(wǎng)絡(luò)中定位的精確度和效率是研究和應(yīng)用的關(guān)鍵。

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

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

1? 基于改進(jìn)NSGA-III算法的DV-Hop三維定位算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4? 結(jié)? 論

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

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

參考文獻(xià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ú)線傳感器網(wǎng)絡(luò)研究現(xiàn)狀與應(yīng)用 [J].通信電源技術(shù)，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ú)線傳感器網(wǎng)絡(luò)非測(cè)距定位算法研究 [D].重慶：重慶大學(xué)，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] 劉濤，龐博.基于遺傳算法的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)分簇算法 [J].現(xiàn)代電子技術(shù)，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.

作者簡(jiǎn)介：黃琛晰（1997—），女，漢族，山東菏澤人，碩士在讀，研究方向：物聯(lián)網(wǎng)技術(shù)。