基于改進(jìn)海洋捕食者算法的WSNs 定位

程忙忙，楊靖，2

（1 貴州大學(xué) 電氣工程學(xué)院，貴陽 550025；2 貴州省互聯(lián)網(wǎng)+協(xié)同智能制造重點(diǎn)實(shí)驗(yàn)室，貴陽 550025）

0 引言

DV-Hop 作為一種無測(cè)距定位算法，由于算法簡(jiǎn)單、覆蓋率高、可行性好，將節(jié)點(diǎn)之間的估計(jì)距離轉(zhuǎn)換為跳數(shù)值和每跳平均距離的乘積［1-3］，已成為一種經(jīng)濟(jì)、且至關(guān)重要的定位算法。算法包括3 個(gè)步驟：

（1）利用廣播使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)獲得其到錨節(jié)點(diǎn)的最小跳數(shù)。

（2）計(jì)算所有錨節(jié)點(diǎn)每一跳的平均距離，并通過將每跳的平均距離與最小跳數(shù)值相乘來獲得估計(jì)距離。

（3）利用與未知節(jié)點(diǎn)距離最近的3 個(gè)及以上的錨節(jié)點(diǎn)和彼此間的估計(jì)距離，使用最小二乘法來計(jì)算未知節(jié)點(diǎn)的位置，但最小二乘法容易陷入局部最優(yōu)。

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

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

1 MPA 算法改進(jìn)及性能分析

1.1 海洋捕食者算法

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

其中，Xmax和Xmin分別表示搜索區(qū)域的上、下邊界，rand表示［0，1］之間的隨機(jī)數(shù)。

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

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

其中，RB是一個(gè)基于非正態(tài)分布的隨機(jī)數(shù)向量，代表Brown 運(yùn)動(dòng)；“ ?”表示逐級(jí)乘法，RB與獵物的乘積模擬了獵物的運(yùn)動(dòng)；P是一個(gè)常數(shù)，P＝0.5；R是［0，1］中的均勻隨機(jī)數(shù)向量。

③《中華人民共和國侵權(quán)責(zé)任法》第五十八條患者有損害，因下列情形之一的，推定醫(yī)療機(jī)構(gòu)有過錯(cuò)：（一）違反法律、行政法規(guī)、規(guī)章以及其他有關(guān)診療規(guī)范的規(guī)定。

②階段2：在單位速度比中，捕食者和獵物以幾乎相同的速度移動(dòng)。由于捕食者和獵物以相同的速度移動(dòng)，捕食者的運(yùn)動(dòng)策略是Brown 與Levy 策略。因此，在這個(gè)階段一半的種群在做Brown 運(yùn)動(dòng)，一半的種群在做Levy 運(yùn)動(dòng)。故當(dāng)時(shí)，對(duì)于前一半的群體來說，建立數(shù)學(xué)模型如下：

其中，RL是一個(gè)基于Levy 分布的隨機(jī)數(shù)向量，代表Levy 運(yùn)動(dòng)。RL與Prey的乘積模擬Levy 方式下的動(dòng)物運(yùn)動(dòng)，并添加步長(zhǎng)到獵物的位置模擬獵物的運(yùn)動(dòng)。對(duì)于種群的后一半，推得的數(shù)學(xué)公式可寫為：

其中，CF表示控制捕食者移動(dòng)步長(zhǎng)的自適應(yīng)參數(shù)。RB和Elite的乘積模擬了布朗運(yùn)動(dòng)中捕食者的運(yùn)動(dòng)，而獵物則根據(jù)布朗運(yùn)動(dòng)中捕食者的運(yùn)動(dòng)來更新自己的位置。

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

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

其中，F(xiàn)ADs＝0.2是FADs對(duì)優(yōu)化過程的影響概率；U是包含0 和1 的二進(jìn)制向量，是通過在［0，1］中生成一個(gè)隨機(jī)向量來構(gòu)造的，如果數(shù)組小于0.2，則將其數(shù)組更改為0，如果數(shù)組大于0.2，則將其數(shù)組更改為1；r是［0，1］中的均勻隨機(jī)數(shù)；Xmin和Xmax是包含維數(shù)上界和下界的向量；r1和r2 表示獵物矩陣的隨機(jī)指標(biāo)。

1.2 改進(jìn)海洋捕食者算法（IMPA）

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

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

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

（2）引入柯西變異［12］和反向?qū)W習(xí)策略［13］對(duì)算法更新后位置進(jìn)行隨機(jī)擾動(dòng)，當(dāng)隨機(jī)數(shù)rand ＞0.5時(shí)，用柯西變異進(jìn)行擾動(dòng)，否則采用反向?qū)W習(xí)策略擾動(dòng)個(gè)體位置，這樣可以產(chǎn)生更多的解，有效地提高算法的多樣性。數(shù)學(xué)公式具體如下：

1.3 算法仿真分析

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

圖1 改進(jìn)算法與其他算法尋優(yōu)效果對(duì)比Fig.1 Comparison of the optimization effect between the improved algorithm and other algorithms

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

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

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

步驟1泛洪。通過泛洪過程得到節(jié)點(diǎn)間的最小跳數(shù)，尤其是未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)和錨節(jié)點(diǎn)間的最小跳數(shù)，為下一步計(jì)算做準(zhǔn)備。

步驟2通過錨點(diǎn)之間的距離計(jì)算出平均每跳的距離，并利用最小跳數(shù)計(jì)算未知節(jié)點(diǎn)u到錨節(jié)點(diǎn)i的估計(jì)距離du，i。

步驟3利用IMPA 來尋找適應(yīng)度函數(shù)的最優(yōu)解，即：

其中，（xu，yu）表示第u個(gè)未知節(jié)點(diǎn)的估計(jì)位置；（xi，yi）表示第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)；du，j表示未知節(jié)點(diǎn)u與錨節(jié)點(diǎn)j之間的估計(jì)距離；m表示錨節(jié)點(diǎn)的數(shù)量。

至此，運(yùn)算得到所有未知節(jié)點(diǎn)的估計(jì)位置。

3 仿真結(jié)果及分析

在1 000?1 000 m2的區(qū)域內(nèi)，隨機(jī)部署和均勻部署1 000個(gè)節(jié)點(diǎn)，其中錨節(jié)點(diǎn)200個(gè)，未知節(jié)點(diǎn)800個(gè)。分別利用原始DV-Hop 算法、基于粒子群的DV-Hop 算法（PSODV-Hop）以及本文提出的IMPA-DV-Hop算法進(jìn)行節(jié)點(diǎn)定位并進(jìn)行對(duì)比，群體智能算法的參數(shù)設(shè)置見表1。

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

圖2 節(jié)點(diǎn)分布圖Fig.2 Distribution map of nodes

圖3中，藍(lán)色短線表示未知節(jié)點(diǎn)的估計(jì)位置到真實(shí)未知的連線，連線越短，定位誤差越小，精度越高。

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

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

表2 定位誤差對(duì)比表Tab.2 Comparison of positioning error table

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

4 結(jié)束語

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