畢金英 王占剛

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

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

中圖分類號(hào)： TP212.9;TN929.5 ? ?文獻(xiàn)標(biāo)識(shí)碼： 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ā)展，傳感器、計(jì)算機(jī)、無(wú)線通信等技術(shù)相互融合形成了無(wú)線傳感器網(wǎng)絡(luò)（WSN）。WSN由大量的傳感器節(jié)點(diǎn)構(gòu)成，通過(guò)無(wú)線通信技術(shù)形成一個(gè)自組織網(wǎng)絡(luò)，具有快速展開(kāi)、抗損壞性強(qiáng)等特點(diǎn)，因此已廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療等領(lǐng)域[1]。在WSN的應(yīng)用中，節(jié)點(diǎn)的感知數(shù)據(jù)必須與位置信息相結(jié)合，才會(huì)使這些感知數(shù)據(jù)有意義，所以傳感器節(jié)點(diǎn)定位技術(shù)是WSN中的關(guān)鍵支撐技術(shù)之一[2]。

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

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

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

1 ?DV-Hop算法

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

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

5 ?結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

[5] 樓國(guó)紅， 張劍平. 粒子群算法修正測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J]. 吉林大學(xué)學(xué)報(bào)（理學(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é)報(bào)， 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] 劉三陽(yáng)， 胡亞靜， 張朝輝. 基于RSSI測(cè)距的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] 張曉莉， 王秦飛， 冀汶莉. 一種改進(jìn)的自適應(yīng)慣性權(quán)重的粒子群算法[J]. 微電子學(xué)與計(jì)算機(jī)， 2019， 36（03）： 66-70.

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

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