基于模擬退火和樽海鞘群優(yōu)化的DV-Hop定位算法*

張大龍，孫 頂，張立志，郭仕勇，韓剛濤

（鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450002）

0 引 言

無線傳感器網(wǎng)絡(luò)（WSNs）是由大量的傳感器節(jié)點(diǎn)以自組織和多跳的方式構(gòu)成，具有數(shù)據(jù)采集、處理和傳輸?shù)墓δ堋Ｆ渲校?jié)點(diǎn)定位技術(shù)［1］是WSNs 中最基礎(chǔ)也是最重要的技術(shù)之一。節(jié)點(diǎn)定位技術(shù)包括基于測(cè)距的定位技術(shù)和基于非測(cè)距的定位技術(shù)。后者對(duì)傳感器的硬件復(fù)雜度和算力要求不高，被大多數(shù)傳感器網(wǎng)絡(luò)所采用。DV-Hop算法是基于非測(cè)距定位算法中應(yīng)用最廣泛的一種，如何提高該算法的定位精度成為了近年來WSNs 領(lǐng)域中的熱門研究方向。文獻(xiàn)［2］利用節(jié)點(diǎn)間的接收信號(hào)強(qiáng)度指示（received signal strength indication，RSSI）值量化節(jié)點(diǎn)間的跳數(shù)，從而減小跳數(shù)誤差；文獻(xiàn)［3］則采用掃描全局信標(biāo)節(jié)點(diǎn)的信息的方法對(duì)跳距進(jìn)行修正，減小跳距帶來的誤差。考慮到DV-Hop算法未知節(jié)點(diǎn)估計(jì)過程可視為在全局范圍內(nèi)尋找最優(yōu)解的過程，因此許多研究者選擇將群智能優(yōu)化算法與WSNs 相結(jié)合，如文獻(xiàn)［4］采用改進(jìn)的鯨魚優(yōu)化算法代替最小二乘法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)；文獻(xiàn)［5］提出將Levy飛行策略與灰狼優(yōu)化算法相結(jié)合，從而進(jìn)一步提高未知節(jié)點(diǎn)估計(jì)精度；文獻(xiàn)［6］將灰狼優(yōu)化算法的狼群狩獵思想和綿羊優(yōu)化算法的羊群互動(dòng)思想相結(jié)合，改進(jìn)獅子群優(yōu)化算法并應(yīng)用于未知節(jié)點(diǎn)坐標(biāo)定位的優(yōu)化。

本文針對(duì)傳統(tǒng)DV-Hop 算法在計(jì)算跳數(shù)、跳距以及未知節(jié)點(diǎn)估計(jì)過程中存在的誤差，采用RSSI 值進(jìn)行跳數(shù)量化，引入修正因子對(duì)平均跳距進(jìn)行校正，在未知節(jié)點(diǎn)估計(jì)階段提出基于模擬退火和樽海鞘群［7］優(yōu)化的DV-Hop定位算法：通過改進(jìn)的Tent 混沌映射［8］優(yōu)化樽海鞘群初始位置，引入慣性權(quán)重策略改進(jìn)樽海鞘群的更新機(jī)制，再利用模擬退火算法［9］的概率突跳特性緩解群優(yōu)化算法容易陷入局部最優(yōu)的問題。仿真結(jié)果表明，本文提出的改進(jìn)算法能夠有效提高未知節(jié)點(diǎn)定位精度。

1 傳統(tǒng)DV-Hop算法原理

傳統(tǒng)DV-Hop算法可分為3 個(gè)階段：確定最小跳數(shù)、計(jì)算平均跳距以及未知節(jié)點(diǎn)估計(jì)。

第一階段：信標(biāo)節(jié)點(diǎn)將包含自身唯一標(biāo)識(shí)、位置信息和初始跳數(shù)為0的數(shù)據(jù)表以泛洪的方式廣播給通信范圍內(nèi)的其他節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)僅保存與周圍其他節(jié)點(diǎn)間的最小跳數(shù)值。

第二階段：多次泛洪后，信標(biāo)節(jié)點(diǎn)獲取到與周圍其他信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)和位置信息，根據(jù)式（1）計(jì)算出各自的平均跳距Hopsizei

式中 （xi，yi），（xj，yj）為信標(biāo)節(jié)點(diǎn)i和其他信標(biāo)節(jié)點(diǎn)j的位置坐標(biāo)；hij為信標(biāo)節(jié)點(diǎn)i和j之間的最小跳數(shù)。則未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的估計(jì)距離du，i可表示為

式中hu，i為未知節(jié)點(diǎn)u與信標(biāo)節(jié)點(diǎn)i的最小跳數(shù)。

第三階段：利用第二階段中計(jì)算出的未知節(jié)點(diǎn)與各個(gè)信標(biāo)節(jié)點(diǎn)間的估計(jì)距離，采用最小二乘法進(jìn)行三邊定位。假設(shè)未知節(jié)點(diǎn)坐標(biāo)U＝（x，y），根據(jù)式（2）得到各個(gè)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離方程組如式（3）所示

利用最小二乘法得到的解為

其中

式（4）中的U即為未知節(jié)點(diǎn)的坐標(biāo)估計(jì)位置。

2 改進(jìn)的DV-Hop算法

2.1 基于RSSI的跳數(shù)量化

不少研究者對(duì)于傳統(tǒng)DV-Hop算法最小跳數(shù)的優(yōu)化提出了多種方法，文獻(xiàn)［10］中采用二通信半徑策略計(jì)算最小跳數(shù)值；文獻(xiàn)［11］中引入Ochiai系數(shù)來逼近相鄰節(jié)點(diǎn)間的通信重疊面積，來改進(jìn)現(xiàn)有的連續(xù)跳數(shù)模型。鑒于目前大部分傳感器節(jié)點(diǎn)集成了RSSI 測(cè)量設(shè)備，因此，本文根據(jù)RSSI的對(duì)數(shù)-常態(tài)分布模型所計(jì)算出的接受信號(hào)強(qiáng)度，對(duì)信標(biāo)節(jié)點(diǎn)通信范圍內(nèi)的未知節(jié)點(diǎn)跳數(shù)進(jìn)行量化，RSSI的對(duì)數(shù)-常態(tài)分布模型如式（7）所示

式中d0為參考信號(hào)傳輸距離，m；P（d0）為接收信號(hào)強(qiáng)度，dB；一般情況下，d0＝1 m；n為射頻信道的衰減指數(shù)，一般取2～4；dij為節(jié)點(diǎn)間的歐氏距離；Xσ為均值為0、方差為σ的高斯隨機(jī)分布，σ的取值根據(jù)節(jié)點(diǎn)間的通信環(huán)境而定。

選取信標(biāo)節(jié)點(diǎn)通信半徑R作為理想單跳距離且將該位置的信號(hào)強(qiáng)度值作為單跳距離的基準(zhǔn)信號(hào)強(qiáng)度RSSIR，則第i＋1個(gè)節(jié)點(diǎn)接收到的第i個(gè)節(jié)點(diǎn)的信號(hào)強(qiáng)度值為RSSIi，i＋1，根據(jù)此值，第i＋1個(gè)節(jié)點(diǎn)的量化規(guī)則如式（8）所示

2.2 平均跳距校正

針對(duì)傳統(tǒng)DV-Hop 算法中計(jì)算平均跳距存在的誤差，文獻(xiàn)［3］根據(jù)全局信標(biāo)節(jié)點(diǎn)特性與未知節(jié)點(diǎn)局部信標(biāo)節(jié)點(diǎn)對(duì)定位精度的影響，提出HDCD算法；文獻(xiàn)［12］通過篩選參與平均跳距計(jì)算的信標(biāo)節(jié)點(diǎn)并對(duì)其進(jìn)行加權(quán)處理，從而減小引入的誤差。本文則通過引入修正因子［4］來對(duì)信標(biāo)節(jié)點(diǎn)的平均跳距進(jìn)行校正。假設(shè)2個(gè)信標(biāo)節(jié)點(diǎn)在泛洪過程中接收到了對(duì)方的位置信息，則兩信標(biāo)節(jié)點(diǎn)的實(shí)際距離d與估計(jì)距離＾di，j，如式（9）、式（10）所示

根據(jù)兩兩信標(biāo)節(jié)點(diǎn)之間平均每一跳的實(shí)際距離d與估計(jì)距離＾di，j的誤差，定義修正因子ei如式（11）所示

因此，校正后的平均跳距如式（12）所示

2.3 基于模擬退火和樽海鞘群優(yōu)化的未知節(jié)點(diǎn)估計(jì)

DV-Hop算法中未知節(jié)點(diǎn)估計(jì)問題可以看作在全局范圍內(nèi)搜索未知節(jié)點(diǎn)坐標(biāo)的最優(yōu)解問題。文獻(xiàn)［4］中利用改進(jìn)的鯨魚優(yōu)化算法代替最小二乘法，從而提高定位精度。文獻(xiàn)［13］引入數(shù)學(xué)優(yōu)化模型來限定人工蜂群算法的尋優(yōu)范圍，從而減少了定位階段的誤差和計(jì)算量。

同樣，受樽海鞘群聚行為的啟發(fā)，2017 年，Mirjalili S等人提出了一種全新的群智能優(yōu)化算法--樽海鞘群算法，該算法可以用來解決未知節(jié)點(diǎn)估計(jì)過程中定位誤差較大，全局信息利用率低的問題，但同時(shí)也存在尋優(yōu)過程中容易陷入局部最優(yōu)的缺點(diǎn)［7］。針對(duì)這一問題，本文提出基于模擬退火的樽海鞘群優(yōu)化算法，利用模擬退火算法的概率突跳特性［14］在解空間中隨機(jī)搜索最優(yōu)解，即在樽海鞘群算法陷入局部最優(yōu)解時(shí)能夠概率性地跳出并且最終得到全局最優(yōu)。

2.3.1 構(gòu)建適應(yīng)度函數(shù)

本文根據(jù)參與定位的信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間平均每一跳的距離與估計(jì)距離之差作為構(gòu)建適應(yīng)度函數(shù)fitness（x，y）的準(zhǔn)則，如式（13）所示

其中，（x，y）為未知節(jié)點(diǎn)坐標(biāo)，（xi，yi）為參與定位的信標(biāo)節(jié)點(diǎn)坐標(biāo)，＾dui為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的估計(jì)距離，N為參與定位的信標(biāo)節(jié)點(diǎn)個(gè)數(shù)，hui為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)。適應(yīng)度函數(shù)fitness（x，y）的值越小則說明未知節(jié)點(diǎn)（x，y）的坐標(biāo)越接近真實(shí)的未知節(jié)點(diǎn)坐標(biāo)，適應(yīng)度越高。

2.3.2 改進(jìn)的Tent混沌映射種群初始化

由于在群優(yōu)化算法中，種群的初始化位置將會(huì)影響整個(gè)算法的收斂速度，初始化的種群在空間內(nèi)分布越均勻，越有利于算法的尋優(yōu)效率和定位精度。Tent映射產(chǎn)生的混沌序列分布均勻，但會(huì)產(chǎn)生小周期以及不穩(wěn)定周期點(diǎn)。因此，本文采用一種改進(jìn)的Tent 映射［8］產(chǎn)生的混沌序列作為種群的初始化位置，映射關(guān)系如式（14）所示

其中，rt為區(qū)間（0，1）上的隨機(jī)數(shù)，NT為Tent混沌序列中的元素?cái)?shù)量。

根據(jù)式（14）產(chǎn)生混沌序列x后，樽海鞘群在搜索空間［lbj，ubj］內(nèi)的初始化位置如式（15）所示

2.3.3 樽海鞘群的位置更新

假設(shè)種群個(gè)數(shù)為N的樽海鞘群利用改進(jìn)的Tent 混沌映射初始化種群位置，計(jì)算每個(gè)個(gè)體的適應(yīng)度fitness（xi，yi），并將所有個(gè)體按照適應(yīng)度由高到低排序，選取其中適應(yīng)度函數(shù)值最小（適應(yīng)度最高）的個(gè)體mini∈［1，N］｛fitness（xi，yi）｝，即全局最優(yōu)位置，作為食物源Fj。然后將適應(yīng)度前50%數(shù)量的樽海鞘規(guī)定為領(lǐng)導(dǎo)者，進(jìn)行全局探索；其余部分為追隨者，充分進(jìn)行局部探索。領(lǐng)導(dǎo)者位置根據(jù)式（16）進(jìn)行更新

式中ubj，lbj為搜索空間的上限與下限；c2，c3分別控制下次移動(dòng)的長度和下次移動(dòng)的方向，取值皆為［0，1］之間的隨機(jī)數(shù)；c1的作用是平衡開發(fā)與勘探，定義如式（17）所示

式中l(wèi)為當(dāng)前迭代次數(shù)，Lmax為最大迭代次數(shù)。

追隨者的位置則根據(jù)牛頓運(yùn)動(dòng)定律進(jìn)行更新，如式（18）所示

重復(fù)上述步驟，每次迭代都會(huì)重新選出適應(yīng)度最高的位置作為食物源，直到達(dá)到迭代次數(shù)上限，此時(shí)的食物源即為樽海鞘群優(yōu)化算法的全局的最優(yōu)解。

2.3.4 慣性權(quán)重策略

上述式（16）和式（18）為原始樽海鞘群算法中領(lǐng)導(dǎo)者與追隨者的位置更新策略。對(duì)于種群中的追隨者來說，其位置更新策略受領(lǐng)導(dǎo)者的位置影響；對(duì)于第i只追隨者來說，其位置更新受第i-1 只追隨者的影響。為了平衡樽海鞘群優(yōu)化算法的全局搜索能力和局部搜索能力，本文引入基于非線性遞減函數(shù)的慣性權(quán)重因子來衡量樽海鞘個(gè)體之間的影響，改進(jìn)后的追隨者更新策略如式（19）所示

式中wini為初始慣性權(quán)重，wend為最終慣性權(quán)重。隨著迭代次數(shù)l的增加，慣性權(quán)重因子w（t）隨之減小，即第i只追隨者的位置受第i-1 只追隨者的影響隨著迭代次數(shù)的增加會(huì)逐漸減小，局部探索能力增強(qiáng)，從而使得樽海鞘群優(yōu)化算法的全局搜索能力和局部搜索能力得到平衡。

2.3.5 模擬退火流程

首先對(duì)模擬退火算法進(jìn)行初始化，初始溫度T為充分大。假設(shè)退火過程中能量從S1變化到S2，則能量變化量ΔC＝S2-S1。其中，S2表示樽海鞘更新狀態(tài)后的適應(yīng)度值，S1表示樽海鞘更新狀態(tài)前的適應(yīng)度值。根據(jù)Metropolis 算法［15］準(zhǔn)則，如式（20）所示，p表示當(dāng)前狀態(tài)接受更新后的樽海鞘位置的概率

對(duì)于ΔC＜0的樽海鞘，更新后的適應(yīng)度高于更新前的適應(yīng)度，即表示更新后的位置要優(yōu)于更新前的位置，則這種更新將會(huì)被接受；對(duì)于ΔC≥0 的樽海鞘，更新后的適應(yīng)度不如更新前的適應(yīng)度，即表示更新后的位置相比于原位置更加偏離實(shí)際位置，這種情況下，改進(jìn)算法不會(huì)立刻舍棄該更新位置，而是會(huì)在（0，1）區(qū)間內(nèi)生成一個(gè)均勻分布的隨機(jī)數(shù)ε，如果ε＜p，則此時(shí)的位置更新被接受，否則拒絕更新，樽海鞘保持更新前的位置

最后根據(jù)式（21）進(jìn)行退火操作，其中，λ為溫度下降速率，一般取值為0.8～0.99。重復(fù)上述位置更新策略以及模擬退火流程，當(dāng)最終溫度達(dá)到終止溫度水平，即算法到達(dá)設(shè)定的最大迭代次數(shù)；或者適應(yīng)度函數(shù)值到達(dá)所設(shè)定的適應(yīng)度門限要求時(shí)，停止迭代，將此時(shí)的食物源Fj，即全局最優(yōu)位置輸出作為未知節(jié)點(diǎn)的最終估計(jì)坐標(biāo)。

2.4 改進(jìn)的DV-Hop算法流程

1）根據(jù)RSSI值量化后的跳數(shù)與修正因子校正后的平均跳距計(jì)算出未知節(jié)點(diǎn)與周圍信標(biāo)節(jié)點(diǎn)的估計(jì)距離，并且利用式（13）構(gòu)建適應(yīng)度函數(shù)。

2）在搜索空間內(nèi)通過改進(jìn)的Tent 混沌映射得到分布均勻的初始化樽海鞘群，并初始化模擬退火算法。

3）計(jì)算種群中所有個(gè)體的適應(yīng)度函數(shù)值，確定食物源并劃分種群領(lǐng)導(dǎo)者與追隨者。

4）分別利用式（16）和式（19）計(jì)算更新后領(lǐng)導(dǎo)者與追隨者位置。

5）計(jì)算更新后的種群個(gè)體適應(yīng)度，通過模擬退火流程中的式（20）判斷是否接受更新后的樽海鞘個(gè)體位置。

6）根據(jù)式（21）進(jìn)行退火操作。

7）重復(fù)上述步驟（3）～步驟（6），直到達(dá)到最大迭代次數(shù)或者滿足適應(yīng)度門限要求，輸出此時(shí)食物源作為未知節(jié)點(diǎn)估計(jì)坐標(biāo)。

3 算法仿真與結(jié)果分析

采用仿真軟件MATLAB 2017a 作為仿真平臺(tái)進(jìn)行實(shí)驗(yàn)，將本文改進(jìn)算法與傳統(tǒng)DV-Hop、文獻(xiàn)［16］中提出的算法，記為SADV-Hop算法和文獻(xiàn)［17］的IGWODV-Hop 算法進(jìn)行對(duì)比仿真。如圖1 所示，仿真環(huán)境為100 m ×100 m 的矩形區(qū)域中隨機(jī)布設(shè)一定比例的信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)，網(wǎng)絡(luò)連通性如圖2所示，節(jié)點(diǎn)的分布和網(wǎng)絡(luò)連通性符合實(shí)際環(huán)境中的分布情況。對(duì)比算法中的適應(yīng)度函數(shù)均采用式（13）的形式，采用歸一化的相對(duì)定位誤差作為衡量算法定位精確度的標(biāo)準(zhǔn)

圖1 網(wǎng)絡(luò)連通性示意

圖2 節(jié)點(diǎn)連通性示意

其中，（xi，yi），（xreal，yreal）分別為未知節(jié)點(diǎn)估計(jì)坐標(biāo)與未知節(jié)點(diǎn)真實(shí)坐標(biāo)。N為未知節(jié)點(diǎn)數(shù)量，R為通信半徑。

3.1 信標(biāo)節(jié)點(diǎn)比例對(duì)定位精度的影響

設(shè)置通信半徑為30 m，節(jié)點(diǎn)總數(shù)為100 個(gè)，信標(biāo)節(jié)點(diǎn)比例由10%逐漸增加到40%，進(jìn)行100 次隨機(jī)實(shí)驗(yàn)，將得到的結(jié)果求均值。信標(biāo)節(jié)點(diǎn)比例與歸一化的相對(duì)定位誤差之間的關(guān)系如圖3（a）所示：隨著信標(biāo)節(jié)點(diǎn)的比例增加，4 種算法的定位誤差都隨之減小，原因是當(dāng)信標(biāo)節(jié)點(diǎn)比例較小時(shí)，未知節(jié)點(diǎn)周圍的信標(biāo)節(jié)點(diǎn)信息匱乏，定位精度較低，隨著信標(biāo)節(jié)點(diǎn)比例的增加，定位精度逐漸增高，但是當(dāng)信標(biāo)節(jié)點(diǎn)比例過大時(shí)，對(duì)定位精度的影響會(huì)逐漸變小。本文算法相比于傳統(tǒng)DV-Hop算法、SADV-Hop算法與IGWODV-Hop算法定位精度分別提升了36.7%，16.2%，9.1%。

圖3 性能測(cè)試結(jié)果

3.2 通信半徑對(duì)定位精度的影響

設(shè)置節(jié)點(diǎn)總數(shù)為100個(gè)，信標(biāo)節(jié)點(diǎn)比例為30%，通信半徑由15 m逐漸增加到50 m，進(jìn)行100次實(shí)驗(yàn)，將得到的結(jié)果求均值。則通信半徑與定位精度的關(guān)系如圖3（b）所示：當(dāng)通信半徑在15～30 m變化的過程中，4種算法的定位精度快速提升，之后再擴(kuò)大通信半徑則歸一化相對(duì)定位誤差曲線變化平緩甚至有所回升，原因是：通信半徑的增加使得網(wǎng)絡(luò)連通性增強(qiáng)，未知節(jié)點(diǎn)能夠利用的位置信息增多，但是在過大的通信半徑下，未知節(jié)點(diǎn)接收到的冗余信息也增多，不利于未知節(jié)點(diǎn)的定位。本文算法相比于傳統(tǒng)DV-Hop 算法、SADV-Hop算法與IGWODV-Hop算法定位誤差分別降低了43.6%，19.3%，7.5%。

3.3 總節(jié)點(diǎn)數(shù)量對(duì)定位精度的影響

設(shè)置通信半徑為30 m，信標(biāo)節(jié)點(diǎn)比例為30%，總節(jié)點(diǎn)數(shù)由100個(gè)逐漸增加至200 個(gè)，進(jìn)行100 次隨機(jī)實(shí)驗(yàn)，并將得到的定位結(jié)果求均值。則總節(jié)點(diǎn)個(gè)數(shù)與歸一化的相對(duì)定位誤差之間的關(guān)系如圖3（c）所示：在100 m×100 m的仿真環(huán)境下，增加總節(jié)點(diǎn)個(gè)數(shù)，則信標(biāo)節(jié)點(diǎn)的密度和整個(gè)網(wǎng)絡(luò)的連通度都會(huì)提升。同樣，當(dāng)總節(jié)點(diǎn)個(gè)數(shù)過多時(shí)，網(wǎng)絡(luò)中的冗余信息也會(huì)增加，因此當(dāng)總節(jié)點(diǎn)個(gè)數(shù)大到一定程度時(shí)，總節(jié)點(diǎn)個(gè)數(shù)對(duì)定位精度的影響會(huì)非常微小。本文算法相比于傳統(tǒng)DV-Hop算法、SADV-Hop算法與IGWODV-Hop算法定位精度分別提升了38.0%，13.2%，5.1%。

4 結(jié)束語

針對(duì)傳統(tǒng)DV-Hop算法定位精度較低等問題，本文對(duì)定位算法3 個(gè)階段提出改進(jìn)算法：基于RSSI 值的跳數(shù)量化機(jī)制、基于修正因子的平均跳距校正以及基于模擬退火的改進(jìn)樽海鞘群優(yōu)化算法。在經(jīng)典樽海鞘群優(yōu)化算法中采用改進(jìn)的Tent 混沌映射對(duì)種群的初始位置進(jìn)行優(yōu)化，并且在樽海鞘位置更新過程中引入慣性權(quán)重策略平衡樽海鞘群優(yōu)化算法的局部搜索能力和全局搜索能力，最后將其更新策略與模擬退火算法相結(jié)合，緩解樽海鞘群優(yōu)化算法易陷入局部最優(yōu)的缺點(diǎn)，該算法相比于其他的智能群優(yōu)化算法在定位精度上有著明顯提高，但是算法的復(fù)雜程度也略有提升，下一步的研究重點(diǎn)在于降低算法的復(fù)雜度。