基于全局人工魚群算法優(yōu)化的DV-Hop定位算法

余修武，秦曉坤，劉 永，余 昊

(南華大學(xué) 資源環(huán)境與安全工程學(xué)院，湖南 衡陽(yáng) 421001)

在無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor network, WSN）中，捕捉到有效的位置信息對(duì)于WSN的監(jiān)測(cè)行為至關(guān)重要。因此，定位技術(shù)對(duì)于WSN有著無(wú)可替代的地位。定位技術(shù)的實(shí)現(xiàn)往往依賴于定位算法，現(xiàn)階段的研究中，定位算法可以大致分為兩類：第1類是基于距離（range-bases）的定位算法，該類算法通常需要硬件技術(shù)支持且能耗相對(duì)較高；第2類則是距離無(wú)關(guān)（range-free）的定位算法，該類算法無(wú)需測(cè)量節(jié)點(diǎn)間的距離或者角度，減少了對(duì)使用硬件設(shè)施的依賴，能耗也有所降低。基于range-free的定位算法主要有質(zhì)心算法、Amorphous定位算法、APIT定位算法、DV-Hop定位算法。與基于range-bases的定位算法相比，基于range-free的定位算法在定位過(guò)程中往往會(huì)出現(xiàn)較大的誤差，因此許多學(xué)者對(duì)該類算法提出了改進(jìn)。

宋倩雯等利用行列式提供的幾何約束對(duì)信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的距離測(cè)量值進(jìn)行修正，雖然提升了定位精度但增加了算法的復(fù)雜度。程超等先使用誤差與距離的權(quán)值處理信標(biāo)節(jié)點(diǎn)的平均每跳距離，再選擇合適的跳段距離計(jì)算方法，最后使用改進(jìn)的遺傳算法優(yōu)化未知節(jié)點(diǎn)坐標(biāo)，但遺傳算法參數(shù)較多，很難確定合適的參數(shù)。李文軍等使用接收的信號(hào)強(qiáng)度指示(received signal strength indication，RSSI)測(cè)距技術(shù)測(cè)量DV-Hop定位算法中未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的1跳距離，定位精度提高的同時(shí)卻增加了硬件成本。Messous等提出同時(shí)使用 RSSI 技術(shù)和多項(xiàng)式近似來(lái)更好地估計(jì)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離的精度，雖提升了定位精度，但也增加了成本以及能耗。Mohamed等提出將位置估計(jì)轉(zhuǎn)化為求解最小化問(wèn)題，使用松鼠搜索算法進(jìn)行尋優(yōu)計(jì)算，但松鼠搜索算法結(jié)構(gòu)較復(fù)雜，自適應(yīng)參數(shù)較多，雖然提升了定位精度，但同時(shí)增加了算法復(fù)雜度。Rabhi等使用果蠅算法優(yōu)化DV-Hop算法（DV-Hop and the fruit fly meta-heuristic，DV-Hop (FOA)），計(jì)算未知節(jié)點(diǎn)位置，該算法收斂速度快，參數(shù)少，但尋優(yōu)精度不高。李娟等提出一種基于雙通信半徑的無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法，該算法僅僅優(yōu)化了最小跳數(shù)，定位精度提升不夠。林維維等提出CVLR（correction vector based distributed localization refinement algorithm）算法，構(gòu)建位置校正矢量，將求精過(guò)程轉(zhuǎn)換為最小化問(wèn)題，使用迭代搜索算法求解，提升了定位精度，但增加了算法復(fù)雜度及能耗。Wang等提出逆距離加權(quán)方法對(duì)平均距離改進(jìn)，并且用包容性檢查規(guī)則來(lái)選擇適當(dāng)?shù)腻^點(diǎn)，雖然一定程度上提升了定位精度且沒有增加算法復(fù)雜度，但定位精度提升不夠。

針對(duì)DV-Hop定位算法存在定位誤差問(wèn)題，基于上述文獻(xiàn)的研究，本文提出了一種基于全局人工魚群算法優(yōu)化的DV-Hop定位算法。該算法的主要思想是先對(duì)信標(biāo)節(jié)點(diǎn)分配雙通信半徑來(lái)廣播信息，利用最小均方誤差準(zhǔn)則計(jì)算出各信標(biāo)節(jié)點(diǎn)的平均每跳距離；之后，計(jì)算出實(shí)際距離與計(jì)算距離的誤差，并賦予權(quán)重，以此求得附近未知節(jié)點(diǎn)的平均每跳距離；然后，根據(jù)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的位置關(guān)系選擇合適的計(jì)算距離的公式；最后，使用全局人工魚群算法求得未知節(jié)點(diǎn)坐標(biāo)。相比于人工魚群算法，全局人工魚群算法更容易跳出局部最優(yōu)，提升算法收斂速度和尋優(yōu)精度，在不增加硬件成本的同時(shí)實(shí)現(xiàn)精準(zhǔn)定位。

1 DV-Hop定位算法及誤差分析

1.1 DV-Hop定位算法

DV-Hop定位算法可以分為3個(gè)步驟：

1）記錄信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間的最小跳數(shù)。所有的信標(biāo)節(jié)點(diǎn)向其通信半徑范圍內(nèi)的所有節(jié)點(diǎn)傳遞自身位置信息及初始跳數(shù)（初始跳數(shù)為0）的數(shù)據(jù)分組，接收節(jié)點(diǎn)記錄來(lái)自每個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)并比較跳數(shù)大小，只保留來(lái)自最小跳數(shù)的信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)分組，令跳數(shù)值加1并轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)。

2）獲取信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離。信標(biāo)節(jié)點(diǎn)利用步驟1）中得到的其他信標(biāo)節(jié)點(diǎn)的位置信息及最小跳數(shù)，計(jì)算出自身的平均每跳距離，并將該信息通過(guò)廣播的方式傳遞到網(wǎng)絡(luò)，未知節(jié)點(diǎn)接收并記錄第1個(gè)信標(biāo)節(jié)點(diǎn)傳來(lái)的平均每跳距離后，拒絕其他信標(biāo)節(jié)點(diǎn)傳來(lái)的此類信息。未知節(jié)點(diǎn)通過(guò)已有的跳數(shù)信息和平均每跳距離信息計(jì)算出到每個(gè)信標(biāo)節(jié)點(diǎn)的距離。

3）未知節(jié)點(diǎn)計(jì)算自身位置。未知節(jié)點(diǎn)通過(guò)已知到信標(biāo)節(jié)點(diǎn)的距離，利用3個(gè)或3個(gè)以上信標(biāo)節(jié)點(diǎn)坐標(biāo)計(jì)算自身位置。

1.2 DV-Hop算法誤差分析

從上述定位過(guò)程中可以看出，誤差的產(chǎn)生主要在步驟1）和步驟2）。信標(biāo)節(jié)點(diǎn)利用自身與信標(biāo)節(jié)點(diǎn)間的實(shí)際距離與最小跳數(shù)的比值求得平均每跳距離，即用直線距離來(lái)代替跳段距離。由于節(jié)點(diǎn)是隨機(jī)分布的，各跳段并不在一條直線上，所以跳數(shù)越大，所造成的誤差越大，導(dǎo)致定位出現(xiàn)誤差。

未知節(jié)點(diǎn)在計(jì)算與信標(biāo)節(jié)點(diǎn)距離時(shí)，僅僅采用與其最近的信標(biāo)節(jié)點(diǎn)的平均每跳距離，而單個(gè)信標(biāo)節(jié)點(diǎn)無(wú)法反映整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)部署信息，如果該信標(biāo)節(jié)點(diǎn)平均每跳距離誤差很大，則使得計(jì)算出的未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的距離也會(huì)存在很大誤差，從而導(dǎo)致定位誤差問(wèn)題。

為解決上述定位誤差問(wèn)題，本文對(duì)DV-Hop算法進(jìn)行了改進(jìn)。

2 DEWF-D定位算法

本文提出的DEWF-D定位算法。首先，改進(jìn)了最小跳數(shù)的獲取方式，將最小跳數(shù)進(jìn)行精確化處理；然后，改進(jìn)了未知節(jié)點(diǎn)平均每跳距離的計(jì)算方法，使得到的結(jié)果誤差更?。蛔詈?，使用全局人工魚群算法代替極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，使得到的結(jié)果更加精準(zhǔn)。算法流程如圖1所示。具體內(nèi)容由第2.1～2.3節(jié)詳細(xì)展開。

圖1 DEWF-D算法流程圖Fig. 1 Flow chart of DEWF-D algorithm

2.1 獲取最小跳數(shù)

在DV-Hop算法中，未知節(jié)點(diǎn)在獲取最小跳數(shù)時(shí)，無(wú)論距離信標(biāo)節(jié)點(diǎn)遠(yuǎn)近，只要位于信標(biāo)節(jié)點(diǎn)的感知范圍內(nèi)都會(huì)記為1跳，當(dāng)不同的未知節(jié)點(diǎn)在計(jì)算與信標(biāo)節(jié)點(diǎn)距離時(shí)采用相同的最小跳數(shù)，最終導(dǎo)致計(jì)算出的定位坐標(biāo)有很大的誤差。為此做出以下改進(jìn)：

改進(jìn)的跳數(shù)計(jì)算模型如圖2所示，節(jié)點(diǎn)

A

為信標(biāo)節(jié)點(diǎn)，其余為未知節(jié)點(diǎn)，

R

為通信半徑。首先，節(jié)點(diǎn)

A

第1次以

R

/2廣播信息，此時(shí)只有節(jié)點(diǎn)

B

可以接收到，節(jié)點(diǎn)

B

記錄跳數(shù)值為0.5；然后，節(jié)點(diǎn)

A

第2次以

R

廣播信息，節(jié)點(diǎn)

B

已經(jīng)接收到了節(jié)點(diǎn)

A

的第1次的信息，舍棄節(jié)點(diǎn)

A

的第2次的信息并將接收的信息和跳數(shù)值0.5轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，節(jié)點(diǎn)

C

接收節(jié)點(diǎn)

A

的此次信息，將跳數(shù)記為1并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。最后，節(jié)點(diǎn)

D

會(huì)接收到來(lái)自節(jié)點(diǎn)

B

、

C

的信息，因?yàn)楣?jié)點(diǎn)

B

跳數(shù)較小，所以只保留節(jié)點(diǎn)

B

傳來(lái)的信息，同時(shí)跳數(shù)加1，即節(jié)點(diǎn)

D

的跳數(shù)為1.5。

圖2 跳數(shù)計(jì)算模型Fig. 2 Hop count calculation model

2.2 計(jì)算未知節(jié)點(diǎn)平均每跳距離

在DV-Hop算法中，未知節(jié)點(diǎn)獲取平均每跳距離的方式是接收最近的信標(biāo)節(jié)點(diǎn)的平均每跳距離。而信標(biāo)節(jié)點(diǎn)計(jì)算的平均每跳距離會(huì)有很大誤差，而且單個(gè)信標(biāo)節(jié)點(diǎn)無(wú)法反映未知節(jié)點(diǎn)附近的節(jié)點(diǎn)部署信息。為此做出以下改進(jìn)：

首先，改進(jìn)信標(biāo)節(jié)點(diǎn)的平均每跳距離。

在一般情況下，測(cè)量誤差服從高斯分布，根據(jù)參數(shù)估計(jì)理論,均方誤差作為估計(jì)子誤差的代價(jià)函數(shù)比使用方差或誤差更為合理。因此，本文采用均方誤差作為誤差的代價(jià)函數(shù)來(lái)計(jì)算信標(biāo)節(jié)點(diǎn)的平均每跳距離。代價(jià)函數(shù)表達(dá)式為：

然后，計(jì)算信標(biāo)節(jié)點(diǎn)平均每跳距離的誤差及誤差權(quán)重。

通過(guò)式（4）計(jì)算出信標(biāo)節(jié)點(diǎn)平均每跳距離的誤差：

通過(guò)式（5）計(jì)算誤差權(quán)值：

由仿真計(jì)算得出未知節(jié)點(diǎn)在接收到最近的3個(gè)信標(biāo)節(jié)點(diǎn)發(fā)來(lái)的信息時(shí)，誤差最小，所以

m

的最佳取值為3。

最后，未知節(jié)點(diǎn)對(duì)來(lái)自3個(gè)最近的信標(biāo)節(jié)點(diǎn)的平均每跳距離進(jìn)行誤差歸一化加權(quán)處理，計(jì)算其平均每跳距離：

2.3 計(jì)算未知節(jié)點(diǎn)坐標(biāo)

在DV-Hop算法中,求解定位坐標(biāo)一般采用極大似然估計(jì)法，由于計(jì)算得出的未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離并不是準(zhǔn)確距離，采用該方法計(jì)算出的定位坐標(biāo)會(huì)有很大的誤差，為了減小誤差，本文將定位問(wèn)題轉(zhuǎn)化為優(yōu)化估算距離的問(wèn)題，計(jì)算過(guò)程采用全局人工魚群算法。

2.3.1 確定適應(yīng)度函數(shù)

適應(yīng)度函數(shù)表達(dá)式為：

2.3.2 確定適應(yīng)度函數(shù)的搜索區(qū)域

如圖3所示，節(jié)點(diǎn)

A

、

B

、

C

為距離未知節(jié)點(diǎn)最近的3個(gè)信標(biāo)節(jié)點(diǎn)，由式（8）求出這3個(gè)節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離，分別為

R

、

R

、

R

，以信標(biāo)節(jié)點(diǎn)為圓心，各自到未知節(jié)點(diǎn)的距離為半徑做圓，圓心分別用(

x

,

y

)、(

x

,

y

)、(

x

,

y

)表示。因?yàn)槭剑?）求出的距離往往會(huì)大于實(shí)際距離，所以未知節(jié)點(diǎn)必然會(huì)位于3個(gè)圓相交的公共區(qū)域。已知圓心坐標(biāo)和半徑，就可以求出3個(gè)圓的函數(shù)表達(dá)式：

圖3 搜索區(qū)域計(jì)算模型Fig. 3 Search area calculation model

通過(guò)式（9）求出3個(gè)圓的交點(diǎn)

D

、

E

、

F

的坐標(biāo)。以點(diǎn)

D

、

E

、

F

為頂點(diǎn)做三角形，設(shè)邊

EF

為三角形的最長(zhǎng)邊，線段

DG

為三角形的高。以邊

EF

為長(zhǎng)、

DG

為寬做出矩形，該矩形就是所要確定的搜索區(qū)域。

2.3.3 全局人工魚群算法求解適應(yīng)度函數(shù)

本文采用全局人工魚群算法求解適應(yīng)度函數(shù)。

每條人工魚被封裝為函數(shù)和變量?jī)蓚€(gè)部分：函數(shù)包括行為函數(shù)（人工魚進(jìn)行的各種行為，包括覓食、聚群、追尾、跳躍、吞食等）和目標(biāo)函數(shù)；變量包括人工魚總數(shù)

W

、狀態(tài)

X

、最大步長(zhǎng)

S

、視野

V

、嘗試次數(shù)

T

、擁擠度因子δ，以及個(gè)體之間的距離

R

。行為函數(shù)描述如下：

1）覓食行為

設(shè)人工魚的狀態(tài)為

X

，由式（10）選擇一個(gè)狀態(tài)

X

，

若不滿足，則繼續(xù)選擇。一直嘗試

T

次后，如果仍不滿足前進(jìn)條件，則更新：

2）聚群行為

否則，執(zhí)行覓食行為。

3）追尾行為

否則，執(zhí)行覓食行為。

4）跳躍行為

迭代了

I

次后，若最優(yōu)人工魚的適應(yīng)度值不滿足預(yù)期要求，就隨機(jī)選取一些人工魚，并隨機(jī)設(shè)定其參數(shù)為：

式中， β可以是一個(gè)參數(shù)，也可以是使人工魚的參數(shù)產(chǎn)生突變的函數(shù)。

5）吞食行為

算法迭代

I

/2次后，若某條人工魚的適應(yīng)度值總是高于預(yù)設(shè)值，則舍棄該魚，且人工魚的總數(shù)

W

減1。

全局人工魚群算法求解適應(yīng)度函數(shù)的步驟如下：

Step1：初始化參數(shù)，包括人工魚總數(shù)

W

、每條人工魚的初始位置、步長(zhǎng)

S

、視野

V

、嘗試次數(shù)

T

、迭代次數(shù)

I

、擁擠度因子δ、執(zhí)行吞食行為的閾值；

Step2：計(jì)算每條人工魚的適應(yīng)度值，并記錄全局最優(yōu)的人工魚狀態(tài)；

Step3：對(duì)每條人工魚進(jìn)行評(píng)價(jià)，對(duì)其要執(zhí)行的行為進(jìn)行選擇，包括覓食行為、聚群行為、追尾行為、吞食行為、跳躍行為；

Step4：執(zhí)行人工魚選擇的行為，基于全局信息和局部信息更新人工魚的位置信息；

Step5：更新全局最優(yōu)人工魚的狀態(tài)；

Step6：若滿足循環(huán)結(jié)束的條件則輸出結(jié)果，否則跳轉(zhuǎn)到Step2。

3 仿真實(shí)驗(yàn)結(jié)果與分析

用MATLAB（R2018b）軟件進(jìn)行仿真測(cè)試，測(cè)試使用的電腦配置為Intel(R) Core(TM) i5–7200U CPU@ 2.50 GHz，系統(tǒng)為Windows 10 家庭中文版。對(duì)比算法為DV-Hop算法、DV-Hop (FOA)算法和CVLR算法。主要給出了節(jié)點(diǎn)定位誤差，及信標(biāo)節(jié)點(diǎn)密度和通信半徑對(duì)定位精度的影響。仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)
Tab. 1 Simulation parameters

參數(shù)取值網(wǎng)絡(luò)區(qū)域面積Z/(m×m)100×100節(jié)點(diǎn)總數(shù)X100信標(biāo)節(jié)點(diǎn)數(shù)量M5、10、15、20、25、30通信半徑/m10、15、20、25、30人工魚總數(shù)W20迭代次數(shù)I100人工魚步長(zhǎng)S/m0.6視野V/m1.5嘗試次數(shù)T50 δ擁擠度因子0.1

評(píng)價(jià)算法的性能指標(biāo)選用歸一化平均定位誤差公式如下：

式中，(

x

,

y

)為節(jié)點(diǎn)

i

的真實(shí)坐標(biāo)，()為節(jié)點(diǎn)

i

的計(jì)算出來(lái)的坐標(biāo)，

N

為未知節(jié)點(diǎn)個(gè)數(shù)，

R

為通信半徑。

3.1 節(jié)點(diǎn)定位誤差

圖4是DEWF-D與DV-Hop算法定位節(jié)點(diǎn)坐標(biāo)的誤差對(duì)比。兩種算法參數(shù)統(tǒng)一，其中，信標(biāo)節(jié)點(diǎn)數(shù)量設(shè)為25，未知節(jié)點(diǎn)數(shù)量設(shè)為75，通信半徑設(shè)為30 m。

圖4 兩種算法節(jié)點(diǎn)定位誤差Fig. 4 Node positioning errors of two algorithms

從圖4中可以看出：DV-Hop算法定位誤差值在4～30 m，平均誤差為18.6 m；而DEWF-D算法定位誤差在2～15 m，平均誤差為6.5；DEWF-D算法定位誤差減少了12.1 m，說(shuō)明本文改進(jìn)的DEWF-D算法能有效提升傳統(tǒng)DV-Hop算法的定位精度。

3.2 信標(biāo)節(jié)點(diǎn)密度對(duì)定位的影響

采用DEWF-D、DV-Hop、CVLR和DV-Hop (FOA)算法，對(duì)比信標(biāo)節(jié)點(diǎn)密度對(duì)定位精度的影響如圖5所示。其中，節(jié)點(diǎn)數(shù)量總共為100，分別對(duì)信標(biāo)節(jié)點(diǎn)數(shù)量為5、10、15、20、25、30時(shí)進(jìn)行測(cè)試，每種情況測(cè)試70次，選用式（16）得到歸一化平均定位誤差，并取70次的平均值。

圖5 不同算法、信標(biāo)節(jié)點(diǎn)密度下的定位誤差Fig. 5 Positioning errors under different algorithms and beacon node densities

從圖5可以觀察出：隨著信標(biāo)節(jié)點(diǎn)的數(shù)量從5逐步增加至30，4種算法的定位誤差都在不同程度上減小，用DEWF-D算法算出的定位誤差總是比其余3種算法得到的定位誤差小。DEWF-D算法的平均定位誤差比DV-HOP算法、CVLR算法和DV-Hop (FOA)算法定位誤差分別減少了28.3%、6.9%、12.5%。說(shuō)明在不同信標(biāo)節(jié)點(diǎn)密度下，本文改進(jìn)的DEWF-D算法要優(yōu)于其他對(duì)比的定位算法。

3.3 通信半徑對(duì)定位的影響

采用DEWF-D、DV-Hop、CVLR和DV-Hop (FOA)算法，對(duì)比通信半徑對(duì)定位精度的影響如圖6所示。網(wǎng)絡(luò)區(qū)域內(nèi)設(shè)置100個(gè)節(jié)點(diǎn)，其中，信標(biāo)節(jié)點(diǎn)數(shù)量為25，未知節(jié)點(diǎn)數(shù)量為75。設(shè)置5組不同的通信半徑進(jìn)行測(cè)試，分別為10、15、20、25、30。每組測(cè)試50次，選用式（16）得到歸一化平均定位誤差公式，并取50次的平均值。

圖6 不同算法、通信半徑下的定位誤差Fig. 6 Positioning errors under different algorithms and communication radius

從圖6可以觀察出：隨著通信半徑逐步增大，4種算法的定位誤差都存在不同程度的減??；而DEWF-D算法的定位誤差明顯比其余3種算法的定位誤差??；DEWF-D算法的平均定位誤差比DV-HOP、CVLR和DV-Hop (FOA)算法的定位誤差分別減少了24.4%、7.6%、14.8%。說(shuō)明在不同通信半徑下，本文改進(jìn)的DEWF-D算法要優(yōu)于其他定位算法。

4 結(jié) 論

為解決DV-Hop定位算法存在較大定位誤差的問(wèn)題，本文在DV-Hop定位算法的基礎(chǔ)上做出改進(jìn)，提出了DEWF-D算法。首先，改進(jìn)了最小跳數(shù)的獲取方式，將最小跳數(shù)進(jìn)行精確化處理；然后，改進(jìn)了未知節(jié)點(diǎn)平均每跳距離的計(jì)算方法，使得到的結(jié)果誤差更小；最后，使用全局人工魚群算法代替極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，使得到的結(jié)果更加精準(zhǔn)。仿真實(shí)驗(yàn)表明：在無(wú)需增加成本的情況下，相比于DV-Hop定位算法、CVLR算法和DV-Hop (FOA)算法，DEWF-D定位算法可以有效提升定位精度。由于在改進(jìn)最小跳數(shù)時(shí)增加了信標(biāo)節(jié)點(diǎn)的通信次數(shù)，而且計(jì)算節(jié)點(diǎn)坐標(biāo)時(shí)使用了群智能算法，雖然提升了定位精度，但是使得節(jié)點(diǎn)能耗增加，因此如何降低節(jié)點(diǎn)的能耗將做進(jìn)一步研究。