基于改進海洋捕食者算法的WSNs 定位

程忙忙，楊靖，2

（1 貴州大學 電氣工程學院，貴陽 550025；2 貴州省互聯網+協同智能制造重點實驗室，貴陽 550025）

0 引言

DV-Hop 作為一種無測距定位算法，由于算法簡單、覆蓋率高、可行性好，將節點之間的估計距離轉換為跳數值和每跳平均距離的乘積［1-3］，已成為一種經濟、且至關重要的定位算法。算法包括3 個步驟：

（1）利用廣播使網絡中的所有節點獲得其到錨節點的最小跳數。

（2）計算所有錨節點每一跳的平均距離，并通過將每跳的平均距離與最小跳數值相乘來獲得估計距離。

（3）利用與未知節點距離最近的3 個及以上的錨節點和彼此間的估計距離，使用最小二乘法來計算未知節點的位置，但最小二乘法容易陷入局部最優。

然而，對于某些應用場景，DV-hop 定位法的定位精度不夠精確，改善其定位精度是研究的關鍵問題。Singh 等人［4］應用了一種改進的定位算法，使用粒子群優化算法來優化結果。Gumida 等人［5］提出了一種基于混合混沌策略的改進定位算法。Harikrishnan 等人［6］使用差分進化算法來最小化無線傳感器網絡中的定位誤差。文獻［7］提出一種改進的人工免疫算法（AIA）優化DV-Hop 未知節點坐標。Cui 等人［8］通過相鄰節點之間的公共單跳節點的值改進了跳數的值，并將離散的跳數值轉換成更精確的連續值。

本文中提出了一種基于改進海洋捕食者算法［9-10］（MPA）的DV-Hop 定位算法。利用改進的海洋捕食者算法較好的尋優能力，替代DV-Hop 算法中的最大似然估計法，在不增加網絡通訊量和硬件的情況下有效降低節點定位誤差，對此流程可重點表述為：首先，通過泛洪的方式，獲得節點間通訊的最小跳數；其次，通過錨點之間的距離，計算出平均每跳的估計距離，進而計算出未知節點到錨點之間的估計距離；最后，構建目標函數，利用改進海洋捕食者算法來搜索出節點的位置。

1 MPA 算法改進及性能分析

1.1 海洋捕食者算法

（1）初始化：首先初始化算法種群X。對此可表示為：

其中，Xmax和Xmin分別表示搜索區域的上、下邊界，rand表示［0，1］之間的隨機數。

（2）迭代優化：考慮獵物與捕食者不同的速度比，同時模擬捕食者和被捕食者的整個生命，MPA 優化過程分為3 個主要階段，對此擬做研究分述如下。

①階段1：在高速比下，獵物比捕食者移動得快。由于獵物比捕食者移動得快，捕食者的最佳運動策略是Brown 運動，因此當Iter ＜時（這里的Iter表示當前迭代次數，Max_Iter表示最大迭代次數），研究給出的運動數學模型如下；

其中，RB是一個基于非正態分布的隨機數向量，代表Brown 運動；“ ?”表示逐級乘法，RB與獵物的乘積模擬了獵物的運動；P是一個常數，P＝0.5；R是［0，1］中的均勻隨機數向量。

③《中華人民共和國侵權責任法》第五十八條患者有損害，因下列情形之一的，推定醫療機構有過錯：（一）違反法律、行政法規、規章以及其他有關診療規范的規定。

②階段2：在單位速度比中，捕食者和獵物以幾乎相同的速度移動。由于捕食者和獵物以相同的速度移動，捕食者的運動策略是Brown 與Levy 策略。因此，在這個階段一半的種群在做Brown 運動，一半的種群在做Levy 運動。故當時，對于前一半的群體來說，建立數學模型如下：

其中，RL是一個基于Levy 分布的隨機數向量，代表Levy 運動。RL與Prey的乘積模擬Levy 方式下的動物運動，并添加步長到獵物的位置模擬獵物的運動。對于種群的后一半，推得的數學公式可寫為：

其中，CF表示控制捕食者移動步長的自適應參數。RB和Elite的乘積模擬了布朗運動中捕食者的運動，而獵物則根據布朗運動中捕食者的運動來更新自己的位置。

其中，RL和Elite的乘法模擬了Levy 策略中捕食者的移動，在Elite位置中加入步長模擬了捕食者的移動，幫助更新獵物的位置。

通過3 個階段的優化，捕食者得到了最佳的位置。海洋中還有許多不可控因素干擾捕食者的運動，例如人工投放的裝置、渦流等，因此還要考慮這些因素的影響，故建立數學模型如下：

其中，FADs＝0.2是FADs對優化過程的影響概率；U是包含0 和1 的二進制向量，是通過在［0，1］中生成一個隨機向量來構造的，如果數組小于0.2，則將其數組更改為0，如果數組大于0.2，則將其數組更改為1；r是［0，1］中的均勻隨機數；Xmin和Xmax是包含維數上界和下界的向量；r1和r2 表示獵物矩陣的隨機指標。

1.2 改進海洋捕食者算法（IMPA）

（1）原MPA 算法采用的是隨機方式生成算法初始種群，rand函數是一種偽混沌的隨機方式，產生的初始種群多樣性低，因此引入Tent 混沌映射［11］初始化算法初始種群，提高算法的多樣性。Tent 混沌映射的數學公式見如下：

其中，Tent 映射的混沌區間為（0，1）。

Tent 混沌映射初始化種群如式（8）所示：

（2）引入柯西變異［12］和反向學習策略［13］對算法更新后位置進行隨機擾動，當隨機數rand ＞0.5時，用柯西變異進行擾動，否則采用反向學習策略擾動個體位置，這樣可以產生更多的解，有效地提高算法的多樣性。數學公式具體如下：

1.3 算法仿真分析

為體現出改進算法的性能，在23 個測試函數中分別選擇了3 個50 維單峰函數和3 個50 維多峰函數進行仿真。3 個單峰函數分別是：F1（Sphere）、F2（Schwefel）、F6（Quartic）測試函數，3 個多峰函數分別是F9（Sum Square）、F10（Rosenbrock）、F11（Zakharov）測試函數。并與原MPA、差分進化算法（DE）和粒子群優化算法［14］（PSO）做了對比，結果如圖1 所示。

圖1 改進算法與其他算法尋優效果對比Fig.1 Comparison of the optimization effect between the improved algorithm and other algorithms

由圖1 可以看出，無論是在單峰測試函數、還是多峰測試函數上，改進算法的尋優速度和尋優能力均高于原算法、差分進化算法和粒子群優化算法，說明了本文改進算法的優越性。

2 基于IMPA-DV-Hop 的定位算法

IMPA 算法擁有很好的優化性能，因此將IMPA引入DV-Hop 定位算法中，取代原始算法中最大似然估計部分，得到IMPA-DV-Hop 定位算法。算法步驟如下。

步驟1泛洪。通過泛洪過程得到節點間的最小跳數，尤其是未知節點到錨節點的最小跳數和錨節點間的最小跳數，為下一步計算做準備。

步驟2通過錨點之間的距離計算出平均每跳的距離，并利用最小跳數計算未知節點u到錨節點i的估計距離du，i。

步驟3利用IMPA 來尋找適應度函數的最優解，即：

其中，（xu，yu）表示第u個未知節點的估計位置；（xi，yi）表示第i個錨節點的坐標；du，j表示未知節點u與錨節點j之間的估計距離；m表示錨節點的數量。

至此，運算得到所有未知節點的估計位置。

3 仿真結果及分析

在1 000?1 000 m2的區域內，隨機部署和均勻部署1 000個節點，其中錨節點200個，未知節點800個。分別利用原始DV-Hop 算法、基于粒子群的DV-Hop 算法（PSODV-Hop）以及本文提出的IMPA-DV-Hop算法進行節點定位并進行對比，群體智能算法的參數設置見表1。

節點分布如圖2 所示。圖2中，藍色圓圈為未知節點，紅色“?”為錨節點的位置。分別采用原始的DV-Hop 算法、基于粒子群的DV-Hop 算法（PSODVHop）以及MPA-DV-Hop 算法對未知節點進行定位，得到定位誤差圖如圖3 所示。

圖2 節點分布圖Fig.2 Distribution map of nodes

圖3中，藍色短線表示未知節點的估計位置到真實未知的連線，連線越短，定位誤差越小，精度越高。

圖3（a）～（c）表示隨機部署情況下分別采用DV-Hop、PSODV-Hop 和MPA-DV-Hop 定位算法進行定位的定位誤差圖，圖3（d）～（f）表示均勻部署情況下分別采用DV-Hop、PSODV-Hop 和MPADV-Hop定位算法進行定位的定位誤差圖。通過對比，可以直觀地看到DV-Hop 算法的定位誤差最大，PSODV-Hop 將未知節點估計到了搜索區域外，效果也比較差，MPA-DV-Hop 的定位效果最好。為了克服偶然因素的影響，對每個算法運行30次，求定位誤差的平均值見表2。

圖3 定位誤差圖Fig.1 Distribution map of positioning error

表2 定位誤差對比表Tab.2 Comparison of positioning error table

從表2 可以得出，本文所提出的算法定位值是最小的，遠小于DV-hop 算法，隨機部署情況下，定位誤差相對于DV-Hop 算法減小了63%，相對于PSODV-Hop 定位誤差減小了7%；均勻部署情況下，定位誤差相對DV-Hop 算法減小了約83%，相對PSODV-Hop 減小了20%。因此，本文提出的定位算法有效地提高了定位精度。

4 結束語

首先，本文對海洋捕食者算法進行了改進，引入Tent 混沌映射初始化算法的種群，并運用柯西變異和反向學習對算法更新后的位置進行擾動，通過3個單峰測試函數和3 個多峰測試函數仿真對比證明，有效地提高了算法的尋優能力和尋優速度。然后，本文提出了IMPA-DV-Hop 定位算法，將其用到了無線傳感器網絡節點定位中，在2 種不同部署方式下進行了仿真，并將其與DV-Hop、PSODV-Hop算法進行了對比。仿真結果表明，提出的算法有效地提高了定位精度，相對于DV-Hop 定位算法，定位誤差得到了明顯的提升。但所改進的算法沒有在其它函數集上進行測試比較，提出的定位算法只在矩形部署環境中進行了驗證，下一步把該算法推廣到更多的場景中。