基于SAPSO算法和RSSI優(yōu)化的DV-Hop定位算法

畢金英 王占剛

摘 ?要： 針對DV-Hop算法在平均跳距估計時和采用最小二乘法估計未知節(jié)點坐標(biāo)存在較大的定位誤差，提出了利用RSSI測距技術(shù)和模擬退火粒子群算法（SAPSO）優(yōu)化改進的DV-Hop算法——SAPSOR-DV-Hop。該算法首先利用RSSI測距技術(shù)定義錨節(jié)點的平均跳距誤差，并利用該誤差修正未知節(jié)點與錨節(jié)點間的距離;其次采用SAPSO算法替代最小二乘法對未知節(jié)點定位進行優(yōu)化。仿真實驗結(jié)果表明，所提出的SAPSOR-DV-Hop算法與傳統(tǒng)的DV-Hop算法和其他兩種算法相比有較高的定位精度。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò);DV-Hop算法;模擬退火粒子群算法;RSSI測距技術(shù)

中圖分類號： TP212.9;TN929.5 ? ?文獻標(biāo)識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.08.024

本文著錄格式：畢金英，王占剛. 基于SAPSO算法和RSSI優(yōu)化的DV-Hop定位算法[J]. 軟件，2020，41（08）：83-86

【Abstract】： Aiming at the DV-Hop algorithms large positioning error when estimating the average hop distance and using the least squares method to estimate the coordinates of unknown nodes， an improved DV-Hop algorithm-SAPSOR-DV-Hop. The algorithm first uses the RSSI ranging technique to define the average hop distance error of the anchor node， and uses this error to correct the distance between the unknown node and the anchor node. Second， it uses SAPSO algorithm instead of the least square method to optimize the unknown node positioning. Simulation results show that the proposed SAPSOR-DV-Hop algorithm has higher position-ing accuracy than the traditional DV-Hop algorithm and the other two algorithms.

【Key words】： Wireless sensor network; DV-Hop algorithm; Simulated annealing particle swarm algorithm; RSSI ranging technology

0 ?引言

隨著科學(xué)技術(shù)的快速發(fā)展，傳感器、計算機、無線通信等技術(shù)相互融合形成了無線傳感器網(wǎng)絡(luò)（WSN）。WSN由大量的傳感器節(jié)點構(gòu)成，通過無線通信技術(shù)形成一個自組織網(wǎng)絡(luò)，具有快速展開、抗損壞性強等特點，因此已廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療等領(lǐng)域[1]。在WSN的應(yīng)用中，節(jié)點的感知數(shù)據(jù)必須與位置信息相結(jié)合，才會使這些感知數(shù)據(jù)有意義，所以傳感器節(jié)點定位技術(shù)是WSN中的關(guān)鍵支撐技術(shù)之一[2]。

WSN中的節(jié)點定位算法主要分為兩種：基于測距技術(shù)和基于無需測距技術(shù)，基于測距技術(shù)的定位算法主要有基于到達時間（TOA）、基于到達時間差（TDOA）、基于到達角度（AOA）、基于接收信號強度（RSSI）[3];基于無需測距技術(shù)的定位算法主要有質(zhì)心算法、APIT算法、凸規(guī)劃定位算法和DV-Hop算法等[4]。基于測距技術(shù)的定位算法定位精度高、對節(jié)點的硬件要求高且耗損量較大;基于無需測距技術(shù)的定位算法對節(jié)點硬件需求低且受實際環(huán)境影響小，但是定位誤差較高[5]，其中，DV-Hop是典型的無需測距定位算法，具有易實現(xiàn)易通信且計算量開銷小等特點，是目前應(yīng)用最為廣泛的定位算法之一[6]。

針對DV-Hop定位誤差較高，許多學(xué)者提出了多種不同改進的DV-Hop算法。文獻[7]對DV-Hop算法的改進通過引入平均跳距誤差修正進行加權(quán)處理減小跳距誤差，再用模擬退火算法替代最小二乘法對未知節(jié)點定位估計。文獻[8]是根據(jù)最大理想篩選信標(biāo)節(jié)點計算加權(quán)平均跳距，再用遺傳粒子群算法替代最小二乘法對未知節(jié)點定位估計。文獻[9]提出自適應(yīng)的平均跳距估計算法，再采用改進的差分進化位置估計模型對未知節(jié)點進行定位。文獻[10]是結(jié)合RSSI測距技術(shù)定義信標(biāo)節(jié)點的平均跳距的誤差，并利用該誤差對未知節(jié)點與信標(biāo)節(jié)點間的距離加權(quán)修正，該文獻對未知節(jié)點的定位估計還是采用的最小二乘法。前面三種文獻所提到的均對DV-Hop算法的第二階段和第三階段有不同的改進，都提高了定位精度，但是在一定程度上會增加計算量，文獻[10]只對第二階段進行了改進，還可以繼續(xù)在原基礎(chǔ)上對第三節(jié)階段進行改進優(yōu)化，提高定位精度。

本文提出基于SAPSOR-DV-Hop，首先利用RSSI測距引入修正誤差，再采用SAPSO算法替代最小二乘法優(yōu)化第三階段，實驗部分和傳統(tǒng)的DV-Hop定位算法、文獻[10]的RSSI加權(quán)修正定位算法、在文獻[10]的基礎(chǔ)上采用粒子群算法替代最小二乘法優(yōu)化第三階段改進的定位算法（PSOR-DV-Hop）進行對比實驗仿真。實驗結(jié)果表明，提出的SAPSOR-DV-Hop定位算法提高了定位精度且明顯高于其他兩種改進的定位算法。

1 ?DV-Hop算法

DV-Hop算法利用距離矢量路由和GPS定位的思想提出的分布式定位方法之一，具體由三個階段構(gòu)成[11]：

第一階段：跳數(shù)確定 ?網(wǎng)絡(luò)中所有節(jié)點部署完畢之后，信標(biāo)節(jié)點將ID、坐標(biāo)和初始化為0的跳數(shù)信息以廣播的形式發(fā)布到WSN中，鄰居節(jié)點獲取距離信標(biāo)節(jié)點的跳數(shù)信息并記錄到信標(biāo)節(jié)點的最小跳數(shù)信息。

5 ?結(jié)束語

本文在DV-Hop算法的基礎(chǔ)上，提出了一種改進的DV-Hop定位算法——SAPSOR-DV-Hop算法，首先利用RSSI測距引入修正誤差，再采用SAPSO算法替代最小二乘法優(yōu)化第三階段。通過仿真實驗可以驗證，SAPSOR-DV-Hop算法和傳統(tǒng)的DV-Hop算法相比，有明顯較高的定位精度，但是在無線傳感器定位中，節(jié)點的能耗影響著網(wǎng)絡(luò)的生存時間和定位的精度，所 ?以在無線傳感器網(wǎng)絡(luò)定位中節(jié)點的節(jié)能問題將有待于研究。

參考文獻

[1] 宗宇雷， 呂品品， 李珂， 趙逸. 混合參數(shù)方法下的室內(nèi)無線定位技術(shù)綜述[J]. 軟件， 2016， 37（03）： 62-66.

[2] 徐慧娟. 基于DV-Hop測距修正的遺傳模擬退火定位算法[J]. 傳感技術(shù)學(xué)報， 2018， 31（01）： 147-151.

[3] 王改云， 王磊楊， 路皓翔. 基于混合群智能算法優(yōu)化的RSSI質(zhì)心定位算法[J]. 計算機科學(xué)， 2019， 46（09）： 125-129.

[4] 汪明， 許亮， 何小敏. 無線傳感器網(wǎng)絡(luò)精度優(yōu)選RSSI協(xié)作定位算法[J]. 計算機應(yīng)用， 2018， 38（07）： 1981-1988.

[5] 樓國紅， 張劍平. 粒子群算法修正測距的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J]. 吉林大學(xué)學(xué)報（理學(xué)版）， 2018， 56（03）： 650- 656.

[6] Kumar S， Lobiyal D K. Novel DV-Hop localization algorithm for wireless sensor networks[J]. Telecommunication Systems， 2017， 64（3）： 509-524.

[7] Wang H， Zhang L. An Improved Simulated Annealing Localization Algorithm for WSN[C]//2018 IEEE 3rd International Conference on Communication and Information Systems （ICCIS）. IEEE， 2018： 93-96.

[8] 高美鳳， 李鳳超. 遺傳粒子群優(yōu)化的DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報， 2017， 30（07）： 1083-1088.

[9] Yang C， Qian Z， Ji G， et al. A Position-Correction Algorithm Based on Hop Distance of DV-Hop[C]// International Conference on Network & Information Systems for Computers. IEEE， 2016.

[10] 劉三陽， 胡亞靜， 張朝輝. 基于RSSI測距的DV-Hop算法[J]. 控制與決策， 2017， 32（10）： 1900-1904.

[11] Tomic S， Mezei I. Improvements of DV-Hop localization algorithm for wireless sensor networks[J]. Telecommunication Systems， 2016， 61（1）： 93-106.

[12] Yang X， Zhang W， Song Q. Improvement of DV-Hop Algorithm Based on RSSI Ratio Correction[J]. International Journal of Online Engineering （iJOE）， 2018， 14（05）.

[13] Li X， Chang J， Yu J， et al. A DW-SAPSO Localization Method based on Correctional RSSI Ranging Model[C]//IOP Conference Series： Earth and Environmental Science. IOP Publishing， 2019， 234（1）： 012104.

[14] 張曉莉， 王秦飛， 冀汶莉. 一種改進的自適應(yīng)慣性權(quán)重的粒子群算法[J]. 微電子學(xué)與計算機， 2019， 36（03）： 66-70.

[15] 趙乃剛. 一種新的基于模擬退火的粒子群算法[J]. 軟件， 2015（07）： 7-10.

[16] 薛永生， 吳立堯. 基于模擬退火的改進粒子群算法研究及應(yīng)用[J]. 海軍航空工程學(xué)院學(xué)報， 2018， 33（02）： 248-252.