一種基于狼群優化的改進DV_Hop定位算法

宋 玲，黃達勝

(廣西大學計算機與電子信息學院，廣西 南寧 530004)

1 引言

無線傳感器網絡WSN(Wireless Sensor Network)研究涉及廣泛，是一種獲取、處理信息的全新技術，廣泛應用在國防、醫療、環境、目標跟蹤和入侵檢測等領域。在無線傳感器網絡中，傳感器節點所監測到的信息，如壓力、溫度、濕度等，如果沒有相對應的位置信息是毫無研究價值的，因此，位置信息對監測活動至關重要[1]，節點定位也成為WSN的研究熱點之一。

通常情況下，無線傳感器網絡節點定位技術可以分為2類：基于測距的定位技術和無需測距的定位技術[2]。在WSN節點定位中，最常用的是基于無需測距的定位方法，而DV_Hop(Distance Vector Hop)算法又是無需測距的方法中最常用的算法之一，其在WSN節點定位中的地位不言而喻。因為易實現、花費低，而且可以滿足大多數應用對于節點定位的要求，所以DV_Hop算法在無需測距的方法中得到了廣泛使用[3]，但其也有一些不足：在實際應用中，傳感器節點是隨機分布的，所以網絡節點平均每跳距離與實際的距離是有偏差的；傳感器節點的密度也會影響定位的精度；在最后的定位計算階段，最小二乘法雖然計算簡單，但是對誤差比較敏感[4]。

由于參數簡單，計算方便，在高密度的節點分布情況下有很好的定位準確度，所以從提出至今，DV_Hop算法都是無線傳感器網絡定位中最常采用的方法之一。但是，又因為第2階段平均跳數產生的距離誤差和第3階段的計算誤差，使得國內外學者一直在對其進行研究與改進。

DV_Hop算法是Dragos等人[5]于2003年提出的，是一種利用距離矢量路由和GPS定位思想提出的定位算法。文獻[6]將RSSI(Received Signal Strength Indicator)與DV_Hop算法相結合，改進了DV_Hop算法，提高了定位的精度，但其只優化了第1跳的距離，精度上并未提高許多。文獻[7]在DV_Hop算法中引入了閾值M，利用M跳數內錨節點的加權平均跳距計算未知節點的平均跳距，從而提高了定位精度。但是，有時遠的錨節點距離更接近實際距離，閾值將這些節點篩選掉了，所以精度并未得到很大提高。文獻[8]利用錨節點的移動形成多個虛擬錨節點,有效減少了錨節點的使用數量;并在原算法基礎上修正平均跳距,使其更接近真實值。但是，這種方法需要提前按照規定布置錨節點，且節點間的路徑是事先規劃好的，對能耗與覆蓋問題還欠考慮。文獻[9]將人工魚群算法引入DV_Hop算法，提高了定位精度，然而將魚群算法引入節點計算增加了復雜度，對能耗有一定的要求。文獻[10]運用加權質心方法改進DV_Hop算法并將其與GSO(Glowworm Swarm Optimization)算法相結合，提高了定位精度，但是僅采用經典粒子群優化PSO(Particle Swarm Optimization)算法，易陷入局部最優。文獻[11]在傳統DV-Hop算法中，融合人工蜂群算法和差分進化算法，提出了一種HDV-Hop算法。該算法優化了搜索過程,提高了定位精度,實現了對未知節點的定位，收斂速度有所提高，但仍有待進一步改進。文獻[12]通過將蟻群算法和粒子群優化算法相結合來改進DV-Hop算法，相比于基于遺傳算法優化的節點定位，定位精度又有所提高，但在未知節點數量超過200時，改進的定位精度和原始的定位精度相差不大，有時甚至更差，這一點有待改進。

狼群算法WCA(Wolf Colony Algorithm)是近些年來新出現的算法，與粒子群優化算法和遺傳算法相比，它具有更高的尋優精度且參數較少，將其用于節點位置的計算階段會得到更好的定位效果。但是，因為原始狼群算法易陷入局部最優，所以將模擬退火與混沌映射相結合對其進行改進。

為滿足對定位精度越來越高的要求，本文提出一種基于改進狼群算法的DV_Hop算法IWCADV_Hop(Improved Wolf Colony Algorithm DV_Hop)，以提升定位精度。與錨節點間跳數為1的節點距離直接利用RSSI計算，這樣能降低部分節點的距離誤差，在計算節點位置階段用改進的狼群算法代替原來的最小二乘法，進一步減小了計算誤差。

2 DV_Hop算法與狼群算法

2.1 DV_Hop算法

DV_Hop 算法的主要思想是用未知節點到錨節點的最小跳數乘以距離未知節點最近的錨節點的平均每跳距離，之后再計算未知節點與錨節點的距離，進而計算未知節點的位置，主要分為以下3個階段[4]：

第1階段：節點獲得與錨節點的最小跳數。錨節點向所有鄰居節點發送跳數信息，所有節點接受到信息之后再繼續轉發給自身的鄰居節點，并使跳數加1，直到所有節點都接收到所有錨節點發送的跳數信息，并取最小的跳數。

第2階段：計算錨節點與未知節點的距離。所有錨節點在第1階段中獲取到與其他錨節點的最小跳數，然后通過自身的定位功能可得知相互之間的距離，通過跳數和距離計算出平均每跳距離。計算公式如式(1)所示：

(1)

其中，Hope為平均跳距，(xai,yai)為第i個錨節點的坐標，(xaj,yaj)為第j個錨節點的坐標，hij為第i個錨節點到第j個錨節點的最小跳數。

第3階段：計算未知節點的位置。所有未知節點在第1階段中接收到了所有錨節點到自身的最小跳數，通過第2階段的平均每跳距離可計算出自身與所有錨節點的距離，通過距離可計算出未知節點的位置。距離計算公式如式(2)所示：

(2)

根據每個錨節點的坐標和與錨節點的距離，未知節點的坐標可由解方程(3)得出。

(3)

其中,(xa1,ya1)為第1個錨節點的位置;(xui,yui)為第i個未知節點的位置;(xaj,yaj)為第j個錨節點的位置，1≤j≤M,M是錨節點個數;dij為第i個未知節點到第j個錨節點的距離。

2.2 狼群算法

狼群算法(WCA)通過模擬自然界中狼群的行為來對目標函數進行尋優，求出最優解。WCA具有并行性，能同時對多個點進行尋優，與其他智能群算法相比，具有更高的尋優精度和更好的魯棒性。狼群算法分為探狼游走、頭狼召喚和猛狼圍攻3種行為，以及勝者為王、優勝劣汰2種規則。狼群中一共包含3種狼：頭狼、探狼和猛狼[13]。頭狼：適應度函數最優的狼，每次迭代對其他猛狼進行召喚，使猛狼向其移動。探狼：除頭狼外適應度函數最優的B匹狼，每次迭代過程中向自身h個方向進行游走，并向函數值優于當前位置的方向移動。猛狼，除頭狼與探狼外的所有狼，每次迭代受頭狼召喚，朝著頭狼奔走，當與頭狼距離小于圍攻距離時進行猛狼圍攻[14]。

狼群算法的主要步驟如下所示：

步驟1隨機生成N匹人工狼。

步驟2計算每匹狼的目標函數值，最優的作為頭狼，除頭狼外最優的B匹狼作為探狼，剩下的作為猛狼，跳到步驟3。當頭狼函數值達到要求或者滿足最大迭代次數，跳到步驟7。

步驟3探狼游走。每次迭代，每匹探狼朝自身h個方向游走，選出函數值最大的方向所對應的函數值，如果函數值優于當前函數值，則探狼朝該方向前進，所以第i匹探狼的位置如式(4)所示：

(4)

步驟4頭狼召喚。每次迭代，頭狼對所有猛狼進行召喚，每匹猛狼朝頭狼靠近，第i匹猛狼第t次迭代的位置計算如式(5)所示：

(5)

奔襲過程中，如果猛狼的函數值優于頭狼的函數值，則該猛狼晉升為頭狼，并在此后的迭代過程中進行召喚。

步驟5猛狼圍攻。若猛狼與頭狼的距離小于圍攻距離，猛狼進入圍攻階段，設頭狼位置為獵物所在位置，對獵物進行圍攻，第i匹猛狼第t次迭代圍攻的位置由式(6)計算得出。

(6)

步驟6依據“勝者為王”規則，按照每匹狼的適應度，即所求函數在每匹狼所在位置的函數值重新選出頭狼、探狼和猛狼；依據“優勝劣汰”規則淘汰掉函數值最差的c匹狼。跳到步驟2。

步驟7輸出頭狼的位置。

3 IWCADV_Hop算法設計

3.1 DV-Hop算法的不足及改進思路

DV_Hop產生誤差的原因主要有2點：(1)跳數帶來的誤差，這是因為節點分布不均勻造成的；(2)計算帶來的誤差，因為當方程數量過多時，最小二乘法的計算易使誤差加大。針對這2點對DV_Hop算法進行改進。首先對于與錨節點只有1跳的未知節點，直接使用RSSI來計算它與錨節點的距離，這樣能使一部分未知節點與錨節點的距離誤差減小，從而減小定位誤差。另一方面，在計算節點位置時，將模擬退火和混沌映射與WCA結合，以提高WCA跳出局部最優的能力，再利用狼群尋優精度高的優勢，用優化后的狼群算法替代最小二乘法，從而減小因最小二乘法計算帶來的誤差。

3.2 RSSI測距

對于與錨節點跳距為1的未知節點，計算它和錨節點之間的距離時，可以采用RSSI的測距方法，這樣會使得一部分節點與錨節點的距離更加準確[6]。RSSI測距如式(7)所示：

(7)

其中,dist為2節點間的距離;Pt(dist)是在經過距離dist后接收到的信號強度，即接收到的RSSI值;Pt(dist0)是在經過距離1 m后接收到的信號強度;dist0為單位距離，X0為噪聲變量，服從均值為零的高斯分布，取值在4 ～ 10;δ是路徑損耗衰減因子，取值在2～5。

3.3 狼群算法的優化

3.3.1 狼群算法的不足

狼群算法與粒子群優化算法、遺傳算法等相比，求解精度更高，收斂速度更快，控制參數更少。但是，探狼的游走行為采取的是貪婪式游走策略,始終朝著適應度函數更優的位置游走。 當探狼在游走范圍內沒有更優的位置時，容易陷入局部最優位置，從而無法繼續游走，降低了算法全局搜索能力[15]。本文將模擬退火算法和混沌映射算法與狼群算法結合，使狼群算法具有跳出局部最優的機會，提高算法的魯棒性。

3.3.2 基于模擬退火與混沌映射優化狼群算法

(1)IWCA算法步驟。

步驟1引用模擬退火算法的思想，給定一個初始概率P0，概率P隨著迭代次數的增加而減小[16]。當探狼嘗試k次游走但位置均未發生變化時，認為探狼陷入了局部最優，則根據概率P朝目標函數值較差的方向游走，P的變化公式如式(8)所示。

(8)

其中，t是當前迭代次數，T是最大迭代次數，P0為初始概率，Pl為最小概率。

步驟2探狼進行目標函數值較差的游走時，游走的方式為混沌映射。將探狼X=(x1,x2,…,xn)(xi是探狼第i維的位置)的每一維度的位置映射到混沌區間Y=(y1,y2,…,yn)[17]上(yi是探狼第i維映射到混沌區間上的位置)，映射公式如式(9)所示，混沌映射的模型如式(10)所示：

(9)

yt+1=0.9-1.9×|yt|

(10)

式(9)中，UB、LB為探狼在第i維參數上的取值上下界，xij為第i匹探狼在第j維度的位置，yij為第i匹探狼映射到混沌區間上第j維度的位置。式(10)中，yt+1表示第t+1次迭代時的混沌變量值，t=0,1,…,m。

將混沌變量Y=(y1,y2,…,yn)根據混沌模型迭代m次，迭代公式如式(10)所示，并將每次迭代后的混沌變量反映射回探狼游走區域中，反映射公式如式(11)所示，探狼在這m次反映射中，找到最優的位置并進行游走。

xij=LB+yij(UB-LB)

(11)

其中，xij為第i匹探狼經過反映射回到第j維度的位置，yij為第i匹探狼在混沌區間上第j維度的位置。

步驟3在猛狼圍攻階段，采用灰狼算法GWO(Grey Wolf Optimizer)[18]的奔走方式，這樣具有更高的游走精確度，圍攻公式如式(12)所示：

(12)

D1=2×D3×(δ-0.5)

(13)

(14)

(2)IWCA算法復雜度分析。

對于WCA，最大迭代次數為T，每次迭代中先計算N匹狼(一共N匹狼)的目標函數值，再對每一匹狼進行游走遍歷，而每匹探狼朝h個方向嘗試游走，所以WCA的時間復雜度為O(T*N*h),因為3個變量是同一個數量級，所以可化簡為O(N3)。對于本文的IWCA，探狼進行m次混沌映射與朝h個方向游走是相互獨立的，所以IWCA算法的時間復雜度為O(T*N*(h+m))，因為這4個變量是一個數量級，故化簡后的時間復雜度為O(N3)，即IWCA與WCA算法的時間復雜度一致。

3.4 IWCA仿真實驗與分析

3.4.1 實驗場景與參數

為了測試基于模擬退火與混沌映射的狼群算法(IWCA)的性能，本文選取了4個常見的適應度函數進行測試，函數如表1所示，每個函數的最優值均為0，對5種算法進行最優值和平均值的比較。實驗環境為：Intel Core i5，內存8 GB，Windows 10專業版64位操作系統，Matlab 2016a。

Table 1 Test functions

實驗進行50次，并記錄平均值和最優值。IWCA的各項參數如表2所示，WCA算法的參數依據文獻[19]選取，DWPA算法的參數依據文獻[20]選取，PSO算法的參數依據文獻[21]選取，MCGSO算法的參數依據文獻[22]選取。4個測試函數中，Sphere為單峰函數，即在定義域內只有一個極值，同時也是全局最優值。其余3個為多峰函數，即在定義域內有多個極值，其中的某個極值為全局最優值，多峰函數可以用來測試算法應對陷入局部最優的能力。

Table 2 Parameters of IWCA

若算法尋優結果滿足式(15)，則說明算法收斂:

|F-fbest|<10-6

(15)

其中，F表示測試函數的理論最優值，fbest表示算法對測試函數所求的最優值。

3.4.2 IWCA實驗結果與分析

各算法對于適應度函數的尋優結果如表3所示，其中Min表示最小值，Mean表示平均值。

由表3可看出，PSO對4個測試函數都不收斂，WCA對f4不收斂，而其他算法對于4個測試函數均收斂。在4個算法中，IWCA收斂效果最好，其次是DWPA，MCGSO雖然最小值的收斂程度也很高，但是平均值與最小值的差距過大，尋優效果不太穩定，不能以最小值來看待。原始的WCA因為容易陷入局部最優，所以在f2～f4上表現不太好，特別是對于f4并未達到收斂條件。不管是對于單峰函數f1還是對于另外3個多峰函數，相對于WCA，IWCA的精度都有很大的提升，且在處理多峰函數時，IWCA更加不容易陷入局部最優，所以能得到更好的求解值。這是因為引入模擬退火和混沌映射的探狼具備了跳出局部最優的能力，而圍攻階段引用灰狼算法的奔走方式，使得后期的尋優能夠更接近最優值。在以上5種智能群算法的比較中，顯然IWCA和DWPA的求解結果更好，而IWCA相比DWPA算法在處理多峰函數時，效果要好些，而處理單峰函數f1時，效果次于DWPA。因為對于單峰函數而言，局部最小值就是全局最小值，IWCA在跳出局部最小值時就錯過了全局最小值，所以對于單峰函數而言，IWCA尋優效果相比DWPA要差一些。

Table 3 Optimization results of each algorithm

3.5 IWCADV_Hop算法

3.5.1 適應度函數

在DV_Hop算法第2階段結束后，得到未知節點與所有錨節點的距離和所有錨節點的位置，未知節點與錨節點的距離誤差如式(16)所示：

(16)

其中(xui,yui)為第i個未知節點的位置，(xaj,yaj)為第j個錨節點的位置，dij為第i個未知節點到第j個錨節點的距離，M是錨節點總數。當距離誤差最小時，則未知節點的位置與實際位置誤差最小，將距離誤差設為適應度函數。則適應度函數如式(17)所示：

(17)

用IWCA來計算適應度函數，當適應度函數取最小值時，未知節點的定位誤差最小。

3.5.2 IWCADV_Hop算法步驟

IWCADV_Hop算法具體步驟如下所示：

步驟1錨節點向周圍節點廣播跳數信息，所有節點接收、記錄跳數信息后轉發給周圍節點，使每個節點獲得與每個錨節點之間最小跳數信息。

步驟2錨節點之間直接通過相互間的距離與跳數計算出平均跳距，并將平均跳距廣播給所有未知節點。

步驟3未知節點計算出自身到每個錨節點的距離。

步驟4根據未知節點和錨節點位置，以及未知節點到所有錨節點的距離列出適應度函數，用IWCA來對適應度函數進行尋優。

步驟5執行狼群算法，當滿足尋優條件或者達到最大迭代次數時停止尋優，輸出頭狼的位置，即所求未知節點的位置。

步驟6當求解完所有未知節點的位置時，算法結束。

IWCADV_Hop算法的流程圖如圖1所示。

Figure 1 Flow chart of IWCADV_Hop algorithm圖1 IWCADV_Hop算法的流程圖

3.5.3 IWCADV_Hop算法復雜度分析

對于DV_Hop算法而言，為使每個節點得到與錨節點的距離，先遍歷每個節點，再遍歷每個未知節點建立方程組，使用最小二乘法解方程組，得出未知節點位置。對于DV_Hop算法中建立的方程組，最小二乘法的時間復雜度為O(4n),n是待求解的方程數量，n與節點總數Ns和錨節點數M是同一個數量級，所以DV_Hop算法的時間復雜度為O(Ns+(Ns-M)*4n)，化簡，得出DV-Hop算法的時間復雜度為O(n2)。對于IWCADV_Hop而言，只是用優化狼群算法代替了最小二乘法，所以IWCADV_Hop的時間復雜度為O(Ns+(Ns-M)*N3)，3個變量是同一個數量級，故化簡可得O(N4)。故相對于DV_Hop而言,IWCADV_Hop增加了時間復雜度，在一定程度上增加了運行時間。

4 IWCADV_Hop仿真實驗與分析

4.1 實驗場景與評價指標

4.1.1 實驗場景

為了驗證IWCADV_Hop算法的定位性能，現將經典DV_Hop算法、RABC算法[23]、GWOAASDV_Hop算法[24]與本文算法進行定位誤差的比較。對比實驗在Matlab 2016a上進行，并以錨節點比例、節點通信半徑和節點總數作為變量來比較4種DV_Hop算法的定位誤差。實驗在100 m*100 m的區域內對無線傳感器網絡節點進行仿真。每個節點的位置隨機生成，且實驗結果取50次實驗結果的平均值。IWCA各參數如表4所示，因為此處的適應度函數比較簡單，且所需精度不需要精確到小數點后很多位，所以調整了狼群算法的參數，以得到更好的運行效果。

Table 4 Parameters of IWCA in IWCADV_Hop algorithm

4.1.2 評價指標

節點平均定位誤差的定義如式(18)所示：

(18)

其中，Ns為總節點數，M為錨節點數，(xie,yie)表示第i個未知節點的計算位置，(xit,yit)表示第i個未知節點的實際位置，R表示節點的通信半徑(本文假設所有節點通信半徑相同),平均誤差單位為%。錨節點數量M越大，計算未知節點到錨節點間的距離就越準確，則式(18)中分子部分的差就越小，從而平均誤差也會越小。

4.2 仿真實驗

4.2.1 以錨節點數量作為變量比較4種算法

仿真實驗中，錨節點的個數從20增加到50，遞增間隔為5，節點通信半徑為30 m，節點總數為100，其他參數不變，對4種算法進行定位誤差的對比，定位誤差如圖2所示，橫坐標表示錨節點數量，縱坐標表示平均定位誤差。隨著錨節點數量的增加，定位誤差逐漸減小，但變化的幅度并不大。這是因為當錨節點的數量增加時，更多未知節點能夠進入到錨節點的覆蓋范圍內，這時的計算錨節點與未知節點的距離更接近于真實值。但是，當錨節點過多時，容易造成錨節點與未知節點距離過近，實際距離遠小于計算距離，這又帶來了定位誤差，所以平均定位誤差隨著錨節點的增加浮動并不大。而對于其他3種算法而言，IWCADV_Hop算法的定位誤差最小，相對于其他3種算法的定位誤差平均降低了21.13%,11.03%,7.5%。

Figure 2 Comparison of location errors of four algorithms with different numbers of anchor nodes圖2 錨節點數量不同時4種算法定位誤差對比

4.2.2 以節點通信半徑作為變量比較4種算法

仿真實驗中，節點通信半徑從20 m增加到50 m，遞增間隔為5 m，錨節點的個數為30個，節點總數為100個，其他參數不變，對4種算法進行定位誤差的對比，定位誤差如圖3所示，橫坐標表示節點的通信半徑，縱坐標表示平均定位誤差?？梢钥闯?，通信半徑在20～35 m時，隨著半徑的增加，定位誤差逐漸較小，當半徑大于35 m時，誤差趨于平滑。這是因為當通信半徑較小時，2個節點之間往往需要進行多個節點轉發才能抵達，因為平均跳距存在一定誤差，而2個節點跳數越大，則2個節點間的計算距離誤差就越大，所以定位效果越差。當通信半徑增大時，節點間的跳距變小，則定位誤差減小。當通信半徑達到35 m時，區域內的2個節點的跳距都在3跳之內，所以隨著半徑的增大，定位誤差的浮動也趨于平滑。而對于其他3種算法而言，IWCADV_Hop算法的定位誤差也在大多數情況下是最小的，相對于其他3種算法的定位誤差平均降低了23.29%,13.13%,7.5%。

Figure 3 Comparison of location errors of four algorithms with different communication radius圖3 通信半徑不同時4種算法定位誤差對比

4.2.3 以節點總數作為變量比較4種算法

仿真實驗中，節點的通信半徑為30 m，錨節點的個數為30，節點總數從100增加到200，遞增間隔為20，對4種算法進行定位誤差的比較，對比結果如圖4所示，其中橫坐標表示區域內傳感器節點的總數，縱坐標表示平均定位誤差。由圖4可以看出，節點總數從100遞增到200對于定位的精度并沒有太大的影響，因為隨著節點總數的增加，平均跳距和計算距離的計算并不會受到明顯的影響，所以對定位誤差也沒有太大的影響。但是，對比4種算法，IWCADV_Hop算法仍然是定位誤差最小的算法，相對于其他3種算法的定位誤差平均降低了22.7%,13.3%,8.2%。

Figure 4 Comparison of location errors of four algorithms with different total numbers of nodes 圖4 節點總數不同時4種算法定位誤差對比

綜上，在3個仿真實驗中，不論是哪個變量對于定位誤差的影響，本文算法求出的定位誤差總是最小的，特別是隨著通信半徑的增加，本文算法的定位誤差能達到5%以下，這是因為一方面改進的狼群算法很大程度上減小了計算時產生的定位誤差，另一方面是因為采用了RSSI算法來計算1跳之內的未知節點與錨節點的距離，隨著通信半徑的增大，越來越多的未知節點都在錨節點的1跳范圍之內，所以距離產生的誤差也相對地減小了。

5 結束語

本文引用RSSI的思想優化1跳內的節點距離，并將優化的狼群算法與DV_Hop算法相結合，不僅改進了狼群算法，提高了狼群算法的魯棒性，還降低了DV_Hop算法的定位誤差。本文通過將模擬退火思想和混沌映射與狼群算法結合，再應用到DV_Hop算法中，提出了基于優化狼群算法的DV_Hop算法(IWCADV_Hop)。模擬實驗表明，在不增加硬件要求的情況下，該算法具有更好的定位表現。本文算法雖然具有更好的定位效果，但是因為狼群數量和狼群迭代次數的增加，導致定位時間也有所增加(時間復雜度為O(N4))，后期將考慮如何降低算法的時間復雜度，提高定位速度。