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

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

（鄭州大學網絡空間安全學院，河南 鄭州 450002）

0 引 言

無線傳感器網絡（WSNs）是由大量的傳感器節點以自組織和多跳的方式構成，具有數據采集、處理和傳輸的功能。其中，節點定位技術［1］是WSNs 中最基礎也是最重要的技術之一。節點定位技術包括基于測距的定位技術和基于非測距的定位技術。后者對傳感器的硬件復雜度和算力要求不高，被大多數傳感器網絡所采用。DV-Hop算法是基于非測距定位算法中應用最廣泛的一種，如何提高該算法的定位精度成為了近年來WSNs 領域中的熱門研究方向。文獻［2］利用節點間的接收信號強度指示（received signal strength indication，RSSI）值量化節點間的跳數，從而減小跳數誤差；文獻［3］則采用掃描全局信標節點的信息的方法對跳距進行修正，減小跳距帶來的誤差?？紤]到DV-Hop算法未知節點估計過程可視為在全局范圍內尋找最優解的過程，因此許多研究者選擇將群智能優化算法與WSNs 相結合，如文獻［4］采用改進的鯨魚優化算法代替最小二乘法計算未知節點的坐標；文獻［5］提出將Levy飛行策略與灰狼優化算法相結合，從而進一步提高未知節點估計精度；文獻［6］將灰狼優化算法的狼群狩獵思想和綿羊優化算法的羊群互動思想相結合，改進獅子群優化算法并應用于未知節點坐標定位的優化。

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

1 傳統DV-Hop算法原理

傳統DV-Hop算法可分為3 個階段：確定最小跳數、計算平均跳距以及未知節點估計。

第一階段：信標節點將包含自身唯一標識、位置信息和初始跳數為0的數據表以泛洪的方式廣播給通信范圍內的其他節點，每個節點僅保存與周圍其他節點間的最小跳數值。

第二階段：多次泛洪后，信標節點獲取到與周圍其他信標節點之間的最小跳數和位置信息，根據式（1）計算出各自的平均跳距Hopsizei

式中 （xi，yi），（xj，yj）為信標節點i和其他信標節點j的位置坐標；hij為信標節點i和j之間的最小跳數。則未知節點與信標節點間的估計距離du，i可表示為

式中hu，i為未知節點u與信標節點i的最小跳數。

第三階段：利用第二階段中計算出的未知節點與各個信標節點間的估計距離，采用最小二乘法進行三邊定位。假設未知節點坐標U＝（x，y），根據式（2）得到各個信標節點與未知節點的距離方程組如式（3）所示

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

其中

式（4）中的U即為未知節點的坐標估計位置。

2 改進的DV-Hop算法

2.1 基于RSSI的跳數量化

不少研究者對于傳統DV-Hop算法最小跳數的優化提出了多種方法，文獻［10］中采用二通信半徑策略計算最小跳數值；文獻［11］中引入Ochiai系數來逼近相鄰節點間的通信重疊面積，來改進現有的連續跳數模型。鑒于目前大部分傳感器節點集成了RSSI 測量設備，因此，本文根據RSSI的對數-常態分布模型所計算出的接受信號強度，對信標節點通信范圍內的未知節點跳數進行量化，RSSI的對數-常態分布模型如式（7）所示

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

選取信標節點通信半徑R作為理想單跳距離且將該位置的信號強度值作為單跳距離的基準信號強度RSSIR，則第i＋1個節點接收到的第i個節點的信號強度值為RSSIi，i＋1，根據此值，第i＋1個節點的量化規則如式（8）所示

2.2 平均跳距校正

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

根據兩兩信標節點之間平均每一跳的實際距離d與估計距離＾di，j的誤差，定義修正因子ei如式（11）所示

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

2.3 基于模擬退火和樽海鞘群優化的未知節點估計

DV-Hop算法中未知節點估計問題可以看作在全局范圍內搜索未知節點坐標的最優解問題。文獻［4］中利用改進的鯨魚優化算法代替最小二乘法，從而提高定位精度。文獻［13］引入數學優化模型來限定人工蜂群算法的尋優范圍，從而減少了定位階段的誤差和計算量。

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

2.3.1 構建適應度函數

本文根據參與定位的信標節點與未知節點間平均每一跳的距離與估計距離之差作為構建適應度函數fitness（x，y）的準則，如式（13）所示

其中，（x，y）為未知節點坐標，（xi，yi）為參與定位的信標節點坐標，＾dui為未知節點與信標節點間的估計距離，N為參與定位的信標節點個數，hui為未知節點與信標節點間的最小跳數。適應度函數fitness（x，y）的值越小則說明未知節點（x，y）的坐標越接近真實的未知節點坐標，適應度越高。

2.3.2 改進的Tent混沌映射種群初始化

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

其中，rt為區間（0，1）上的隨機數，NT為Tent混沌序列中的元素數量。

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

2.3.3 樽海鞘群的位置更新

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

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

式中l為當前迭代次數，Lmax為最大迭代次數。

追隨者的位置則根據牛頓運動定律進行更新，如式（18）所示

重復上述步驟，每次迭代都會重新選出適應度最高的位置作為食物源，直到達到迭代次數上限，此時的食物源即為樽海鞘群優化算法的全局的最優解。

2.3.4 慣性權重策略

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

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

2.3.5 模擬退火流程

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

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

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

2.4 改進的DV-Hop算法流程

1）根據RSSI值量化后的跳數與修正因子校正后的平均跳距計算出未知節點與周圍信標節點的估計距離，并且利用式（13）構建適應度函數。

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

3）計算種群中所有個體的適應度函數值，確定食物源并劃分種群領導者與追隨者。

4）分別利用式（16）和式（19）計算更新后領導者與追隨者位置。

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

6）根據式（21）進行退火操作。

7）重復上述步驟（3）～步驟（6），直到達到最大迭代次數或者滿足適應度門限要求，輸出此時食物源作為未知節點估計坐標。

3 算法仿真與結果分析

采用仿真軟件MATLAB 2017a 作為仿真平臺進行實驗，將本文改進算法與傳統DV-Hop、文獻［16］中提出的算法，記為SADV-Hop算法和文獻［17］的IGWODV-Hop 算法進行對比仿真。如圖1 所示，仿真環境為100 m ×100 m 的矩形區域中隨機布設一定比例的信標節點與未知節點，網絡連通性如圖2所示，節點的分布和網絡連通性符合實際環境中的分布情況。對比算法中的適應度函數均采用式（13）的形式，采用歸一化的相對定位誤差作為衡量算法定位精確度的標準

圖1 網絡連通性示意

圖2 節點連通性示意

其中，（xi，yi），（xreal，yreal）分別為未知節點估計坐標與未知節點真實坐標。N為未知節點數量，R為通信半徑。

3.1 信標節點比例對定位精度的影響

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

圖3 性能測試結果

3.2 通信半徑對定位精度的影響

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

3.3 總節點數量對定位精度的影響

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

4 結束語

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