Levy飛行策略結合三維灰狼優(yōu)化的DV-hop定位算法

張 晶，郭一翰

1(昆明理工大學 信息工程與自動化學院，昆明 650500) 2(云南梟潤科技服務有限公司，昆明 650500) 3(昆明理工大學 云南省人工智能重點實驗室，昆明 650500) 4(昆明理工大學 云南省計算機技術應用重點實驗室，昆明 650500)

1 引 言

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)廣泛應用于邊緣計算[1]、森林防火、疾病預防等領域，在針對無線傳感器網(wǎng)絡節(jié)點的研究中，如何根據(jù)已知節(jié)點信息精確定位未知節(jié)點位置的研究已成為該領域的熱點[2].

現(xiàn)有的定位算法依據(jù)需要測距與否的標準，將定位算法分為兩種.第一種算法為測距式算法，一般是利用距離信息建立數(shù)學等式或是利用能量數(shù)據(jù)創(chuàng)建數(shù)學模型，通過測量所得到的數(shù)據(jù)信息的準確度就是關鍵信息所在.該算法雖然定位誤差較低，但對嵌入式設備有一定的要求;另一種定位算法不需測距，且節(jié)約成本，耗能低，此外對所需嵌入式裝備無過多要求，其代表為我們所熟知的傳統(tǒng)DV-hop算法.DV-hop算法思想來源于貝爾曼-福特路由所改進的分布式定位方法[3]，該方法依賴不同節(jié)點之間的數(shù)據(jù)信息交互與協(xié)調(diào)，具有實現(xiàn)方法簡單，定位誤差低等特點，但是由于實際的無線傳感器網(wǎng)絡節(jié)點部署具有隨機性，無法達到DV-hop算法的理想節(jié)點分布，導致在計算跳距以及跳數(shù)時不夠精準[5]，并且在利用極大似然值估計算法估算待定節(jié)點位置時無法更加精確地提高未知節(jié)點的定位.

針對以上問題，文獻[4]提出了一種距離修正結合灰狼算法對DV-Hop定位的改進算法，在經(jīng)典DV-Hop算法的基礎上，該算法引入灰狼算法優(yōu)化節(jié)點間的跳數(shù)，為修正待定節(jié)點的實際與預測位置采用極大似然估計算法，但若單純使用灰狼算法修正跳數(shù)，受到縮放因子和交叉概率的制約，不利于全局最優(yōu)，且由于二維空間的局限性，會導致定位精度減弱.文獻[5]提出了一種通過僅考慮最接近的錨節(jié)點來改進無線傳感器網(wǎng)絡中基于DV-Hop的定位算法，該算法為減少定位誤差，僅根據(jù)最近錨節(jié)點信息來預測待定節(jié)點位置，但若錨節(jié)點與未知節(jié)點距離較遠，會導致錨節(jié)點被忽略，也無法有效降低誤差值.文獻[6]提出了一種改進人工蜂群優(yōu)化的DV-Hop定位算法，該優(yōu)化算法在多邊定位階段使用改進的人工蜂群算法進行算法優(yōu)化，在此文獻中劉燕等在基本人工蜂群算法基礎上引入數(shù)學優(yōu)化模型，為該算法進行區(qū)域限定，以達到優(yōu)化多邊定位執(zhí)行的目的，但該算法未考慮WSN節(jié)點部署不均，且受到二維空間限制，定位精度也會降低.

因此本文針對不同節(jié)點之間計算跳距、跳數(shù)不夠精準及使用最小二乘法(Least sqaure method，LS)或極大似然值估計算法定位未知節(jié)點的精確度不高，而導致無法準確定位，誤差較大的情況，提出一種Levy飛行策略結合三維灰狼優(yōu)化的DV-hop 定位算法.該算法在計算平均跳距時，根據(jù)未知節(jié)點與信標節(jié)點之間的不同跳數(shù)引入權重因子，并且使用智能仿生三維灰狼算法，對每一個未知節(jié)點的位置進行仿生尋優(yōu)計算，在加入灰狼算法的同時引入Levy飛行算法，提高灰狼算法的全局尋優(yōu)能力，進而更好的提高算法精確度.

2 理論背景

2.1 傳統(tǒng)DV-hop算法

傳統(tǒng)DV-hop算法是利用貝爾曼-福特路由所引導出的定位算法，該算法的主要步驟主要分為3步：

1)信標節(jié)點(錨節(jié)點)通過傳統(tǒng)的貝爾曼-福特路由交換協(xié)議向節(jié)點播送自己的信息數(shù)據(jù)，以此獲得所有節(jié)點到每一個信標節(jié)點的最小跳數(shù)hopij以及位置信息.

2)每個信標節(jié)點利用其它錨節(jié)點的位置數(shù)據(jù)以及相隔的最小跳數(shù)hopij來求取平均跳距Ave_dis.如式(1)所示：

(1)

式(1)中，(xi，yi)、(xj，yj)分別是信標節(jié)點i，j在網(wǎng)絡坐標的已知位置，求出平均跳距Ave_dis后將其作為勘誤值播送到WSN中.

3)根據(jù)以上兩步所獲得的最小跳數(shù)hopij以及平均跳距Ave_dis使用最小二乘法(LS)或極大似然值估計算法求取待定位節(jié)點的位置[6].

設(xk，yk)表示一個未知節(jié)點K的位置，dki表示需定位節(jié)點K到信標節(jié)點ANi在空間上的估測距離，見公式(2)：

dki=Ave_disk×hopki

(2)

其中，hopki是K到ANi的最小跳數(shù)，Ave_disk表示K所保存的平均跳距.

根據(jù)信標節(jié)點的實際位置以及預估到未知節(jié)點的距離，可形成如公式(3)所示：

(3)

將方程組中的每一個方程等號兩邊開根號，所形成的新方程組轉(zhuǎn)換成矩陣CX=D，其中C，D和X如式(4)所示：

(4)

通過LS獲得該矩陣方程，可以確定未知節(jié)點K的預估位置：

X=(CTC)-1CTD

(5)

從以上算法的運行過程來看，計算的誤差主要來自于最小跳數(shù)和平均跳距計算精度以及多個位置節(jié)點目標定位的優(yōu)化.本文主要使用跳數(shù)加權對平均跳距進行改進以及使用飛行策略改進的三維狼群算法在多目標定位階段增加定位精度.

3 改進的傳統(tǒng)DV-hop算法

3.1 跳數(shù)加權改進

由文獻[7]可知在實際中，無線傳感器網(wǎng)絡節(jié)點是不均勻分布的，這就導致平均跳距以及最小跳數(shù)計算的不準確性.為減少這一誤差，本文在計算未知節(jié)點的Ave_dis時，根據(jù)未知節(jié)點K到其他信標節(jié)點的不同跳數(shù)引入權重因子，公式為：

(6)

式中，hopk表示是未知節(jié)點到各個信標節(jié)點的跳數(shù)，m代表所有信標節(jié)點個數(shù)，hopk越大，Wk的值就越小，因此，未知節(jié)點與信標節(jié)點跳數(shù)多的未知節(jié)點需要給予較小比重，跳數(shù)少的應當給予較大比重，改進后的平均跳距可以表示為：

(7)

3.2 灰狼算法

基本的灰狼算法(GWO)是由澳籍研究者Mirjalili等人[8]提出的一種仿生種群優(yōu)化算法.其具有較強的收斂性能，所用參數(shù)較少，容易實現(xiàn)等特點，近年來成為定位算法的研究熱點.

灰狼隸屬于犬科群居動物，處于食物鏈頂層的他們嚴格遵守著社會等級支配關系，如圖1所示.

圖1 灰狼等級圖Fig.1 Gray wolf hierarchy diagram

社會等級最高的灰狼稱為α，α灰狼具有最高統(tǒng)治地位，對其他的狼具有絕對的支配能力，社會等級第2與第3的灰狼稱為β狼和δ狼，社會等級最底層的狼稱為ω狼，ω狼需要服從其他層次的狼，ω狼的作用是為了防止狼群內(nèi)部的自相殘殺.GWO的具體步驟如下：

1)社會階級分層(Social Hierarchy)：在設計灰狼算法時，首先根據(jù)適應度函數(shù)，將適應度最好的3只狼分別標記為α狼、β狼和δ狼，剩下的灰狼則稱為ω狼.GWO優(yōu)化就是由迭代更新過程中最好的3個解α、β和δ來完成.

2)圍困獵物(Encircling prey)：灰狼群在搜尋獵物時，會逐漸形成一個包圍圈圍困獵物目標，該行徑數(shù)學模型如下：

(8)

式(8)中，t為此時的迭代次數(shù)；° 為哈達瑪乘積操作；Xp為優(yōu)化目標的位置；X(t)表示此時狼的定位向量；在迭代的開始到結束，a從2從線性降到0；r1和r2是0～1中的隨機向量；A和B是協(xié)同的系數(shù)向量值；Dis表示灰狼之間的距離.

3)狩獵(Venery)：灰狼擁有分辨潛在目標定位的天賦，搜索過程中主要由α、β和δ3匹高階灰狼來引領完成，但由于解空間特征的未知性，狼群確定不了最優(yōu)目標的完美定位，所以為更好地模擬灰狼的捕獵行為，假定α、β和δ具有很好的區(qū)分目標定位天賦，所以在每次迭代時保留灰狼群中的等級高層狼α、β和δ，再根據(jù)他們的位置數(shù)據(jù)來更新其他ω狼的位置，該行為的數(shù)學模型如下：

(9)

式中Xα、Xβ、Xδ分別是灰狼群中的α、β和δ的方位向量；X代表灰狼的位置；Disα、Disβ、Disδ分別代表當前的灰狼與灰狼α、β和δ間的距離；當|A|>1時，灰狼群成員之間分散在各區(qū)域并搜尋目標；當|A|<1時，灰狼群成員將集中在某特定區(qū)域搜索獵物目標.

由圖2可見，α、β和δ定義的隨機圓位置內(nèi)就是候選狼最終的位置所在.總而言之，ω灰狼在此時的α、β和δ3只高階灰狼預測出獵物目標的大體方位之后，在獵物周圍任意更新高階灰狼的位置.

圖2 狩獵時選狼ω移動方式圖Fig.2 Diagram of choose wolf movement when hunting

4)攻擊目標(Attacking target)：創(chuàng)建模型時，根據(jù)步驟2可知，a數(shù)值的降低也會改變A的值，A是[-a，a]區(qū)間的隨機向量.當A在區(qū)間[-1，1]上時，則此時灰狼與目標之間的位置就是代理搜索的下一刻位置.

5)尋找獵物(Look for prey)：主要依靠α、β和δ3只高階灰狼搜尋獵物，他們分散地去尋找獵物目標方位，然后集中攻擊.在分散模型中，當|A|>1時使得代理搜索遠離獵物，使得算法可以進行全局尋優(yōu).

GWO算法是一種模仿灰狼群體捕獵啟發(fā)的一種新型仿生群體智能算法，具有收斂性能較高，且易于實現(xiàn)等特點，可用于WSN節(jié)點定位，降低算法誤差，但與眾多仿生算法一樣，有著過早收斂，全局搜索能力較弱等問題，以至于所得到的最終解精度不高.

3.3 飛行策略改進灰狼算法

根據(jù)文獻[9，10]可知灰狼算法存在過早收斂以及全局尋優(yōu)能力不高的特性，因此為提高灰狼算法的全局尋優(yōu)能力且豐富灰狼算法的種群多樣性，本文利用Levy飛行算法的隨機游走性能，將Levy飛行算法[11]融合到灰狼算法中，進行WSN未知節(jié)點的位置計算.算法改進如下：

在α狼、β狼、δ狼和ω狼在每次迭代更新位置時，使用Levy飛行公式(11)執(zhí)行一次飛行優(yōu)化，公式如下：

(10)

(11)

3.4 改進的灰狼算法修正未知節(jié)點位置

在經(jīng)典DV-hop第3階段，使用極大似然值估計算法確定待求節(jié)點方位，由于該方法的局限性不能有效提高計算精度，因此使用三維狼群算法對最后未知節(jié)點的位置進行改進，改進如下：

1)首先初始化α、β和δ3只高階灰狼，使用Positions函數(shù)將灰狼算法中灰狼的位置維度改為3維，并且設定好最大迭代次數(shù)以及種群個數(shù).

2)根據(jù)式(10)適應度函數(shù)得到所有灰狼的初步適應度值Fw，式中，(xw，yw，zw)為待定位節(jié)點位置，也就是狼群算法中獵物位置，(xg，yg，zg)為信標節(jié)點節(jié)點位置，dwg為待定位節(jié)點到信標節(jié)點節(jié)點的位置，選擇最小適應值的3只狼分別將他們標記為α、β和δ.

(12)

3)灰狼群根據(jù)之前提到的式(8)和式(9)進行更新狼群位置信息X，如果α狼已達到最大迭代次數(shù)或者滿足迭代循環(huán)結束條件，則停止循環(huán)，輸出的α狼坐標信息即為未知節(jié)點最終改進位置.

4 算法仿真分析

4.1 仿真環(huán)境與參數(shù)設置

為驗證改進后的DV-hop算法與之前傳統(tǒng)的DV-hop算法相比定位更精確，分別將4種算法在Matlab2016a軟件上進行仿真實驗，通過4種算法對平均定位精確度數(shù)據(jù)Ave_er在不同的錨節(jié)點數(shù)，節(jié)點總數(shù)以及通訊半徑的不同數(shù)據(jù)條件下變化趨勢，判斷本文算法有效性.

在邊長為100的正方體三維立體空間中，任意投放400個WSN節(jié)點，如圖3所示.

圖3 三維節(jié)點隨機分布圖Fig.3 Three-dimensional random distribution of nodes

以全部未知節(jié)點的平均定位精確度數(shù)據(jù)作為實驗對照圖的縱坐標，以對比不同算法的精度，未知節(jié)點的平均定位精確度數(shù)據(jù)Ave_er計算見公式(13)：

(13)

式(13)中，xf′、yf′、zf′分別為未知節(jié)點f在三維坐標軸上的值，UNa是未知節(jié)點的個數(shù).

4.2 實驗仿真結果解析

實驗環(huán)境與參數(shù)設定：在Matlab2016a軟件[12]上進行實驗，將節(jié)點通訊半徑設為50，節(jié)點總數(shù)設為400，在不同的錨節(jié)點數(shù)量條件下，設定灰狼算法迭代次數(shù)為350次，狼群數(shù)量為100，Levy飛行策略中的α′設為1，統(tǒng)計原始DV-hop算法、三維加權DV-hop算法未使用飛行策略的灰狼算法以及本文算法的Ave_er，4種算法Ave_er隨錨節(jié)點數(shù)量的增加而發(fā)生變化的情況，如圖4所示.

圖4 不同錨節(jié)點數(shù)各算法誤差比較圖Fig.4 Error of each algorithm varies with different anchor nodes

由圖4可知，當錨節(jié)點個數(shù)為120時，本文改進的算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6342、0.2004、0.0222；當錨節(jié)點個數(shù)為180時，本文改進的算法與經(jīng)典DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6562、0.1741、0.0286；當錨節(jié)點個數(shù)為240時，本文改進的算法與經(jīng)典DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6675、0.1669、0.0176.

由此將實驗環(huán)境與參數(shù)設定：在Matlab2016a軟件上進行實驗，將錨節(jié)點數(shù)設為160，節(jié)點總數(shù)設為400，在不同通訊半徑條件下，設定灰狼算法迭代次數(shù)為350次，狼群數(shù)量為100，Levy飛行策略中的α′設為1，統(tǒng)計原始DV-hop算法、三維加權DV-hop算法未使用飛行策略的灰狼算法以及本文算法的Ave_er，4種算法Ave_er隨錨節(jié)點數(shù)量的增加而發(fā)生變化的情況，如圖5所示.

由圖5可知，當通訊半徑r為40時，本文改進的算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.7187、0.1502、0.0756；當r為55時，本文算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6588、0.2016、0.0488；當r為70時，本文改進的算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.4030、0.1388、0.0309.

圖5 不同通訊半徑各算法誤差比較圖Fig.5 Error comparison of different algorithms of different communication radius

由此將實驗環(huán)境與參數(shù)設定：在Matlab2016a軟件上進行實驗，將錨節(jié)點數(shù)設為總結點數(shù)的40%，通訊半徑設為50，在不同的節(jié)點總數(shù)條件下，設定灰狼算法迭代次數(shù)為350次，狼群數(shù)量為100，Levy飛行策略中的α′設為1，統(tǒng)計原始DV-hop算法、三維加權DV-hop算法未使用飛行策略的灰狼算法以及本文算法的Ave_er，4種算法Ave_er隨節(jié)點總數(shù)量的增加而發(fā)生變化的情況，如圖6所示.

由圖6可知，當節(jié)點總數(shù)設為100時，本文改進的算法與經(jīng)典DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.5684、0.1402、0.0533；當節(jié)點總數(shù)設為250時，本文改進的算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6580、0.1881、0.0478；當通訊半徑為400時，本文改進的算法與原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，Ave_er分別降低了0.6973、0.1974、0.0203.

圖6 不同節(jié)點總數(shù)各算法誤差比較圖Fig.6 Error comparison of the algorithms with different sum points

由實驗結果表明，4種算法對平均定位精確度數(shù)據(jù)Ave_er在不同的錨節(jié)點數(shù)，節(jié)點總數(shù)以及通訊半徑的不同數(shù)據(jù)條件下，本文算法的精確度明顯優(yōu)于原始DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法，并且在加入Levy飛行策略時相較未使用飛行策略的灰狼算法，定位誤差又降低了5%左右，相對于經(jīng)典DV-hop算法、三維加權DV-hop算法以及未使用飛行策略的灰狼算法相比，降低的未知節(jié)點定位誤差區(qū)間分別為40%～69%、13%～20%、1.7%～7.6%，表明了本文算法的精確性.

5 總 結

本文針對WSN DV-hop[13]定位算法的待定位節(jié)點定位精度不高的情況，提出一種Levy飛行策略結合三維灰狼優(yōu)化的DV-hop定位算法.算法仿真實驗結果表明Levy飛行策略[14]平衡了灰狼算法的全局與局部搜索能力，與原灰狼算法相比，本文算法提高了灰狼算法的全局搜索性能，規(guī)避該算法收斂過早的弊端，此外根據(jù)待定位節(jié)點與信標節(jié)點之間的不同跳數(shù)引入權重因子，避免待定位節(jié)點直接使用信標點的平均跳距，在相同的自變量計量下定位精度也有顯著提高.此外，由于每次仿真實驗的節(jié)點分布不同，會出現(xiàn)極少數(shù)未使用Levy飛行策略的原始狼群算法優(yōu)于本文算法，如何區(qū)分辨別這一小部分節(jié)點以獲得精確度更高的定位策略是今后的研究工作.