田洪舟，陳思溢，黃輝先

(1.湘潭大學(xué) 自動化與電子信息學(xué)院,湖南 湘潭 411105；2.廣東科技學(xué)院 計算機學(xué)院,廣東 東莞 523000)

0 引 言

節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)中一種重要的基礎(chǔ)技術(shù)，如何提升節(jié)點定位的精度成是一個受人關(guān)注的問題。節(jié)點定位的常用方法主要分為基于測距的定位算法和基于非測距的定位算法兩種，其中,距離矢量—跳數(shù)(distance vector hop，DV-Hop)算法是基于非測距的定位算法中應(yīng)用最廣的一種，具有消耗資源少，需要信標(biāo)節(jié)點數(shù)少，實現(xiàn)簡單等優(yōu)點。

基本的DV-Hop算法在定位時受節(jié)點分布的影響較大，其結(jié)果并不十分準(zhǔn)確。研究人員提出了多種改進的方法，其中大部分文獻采用了在DV-Hop算法的前兩個階段精確跳數(shù)和平均跳距的方法達到減少定位誤差的目的[1～4]。也有學(xué)者提出了在定位階段用智能優(yōu)化算法代替最小二乘法來減小計算誤差。如文獻[5]提出用遺傳機制改進的粒子群算法優(yōu)化DV-Hop算法，定位的精度明顯高于原算法；文獻[6]融合了免疫算法與粒子群算法，改進了濃度機制，動態(tài)調(diào)整了疫苗范圍，提高了定位精度；文獻[7]引入數(shù)學(xué)優(yōu)化模型限定人工蜂群的尋優(yōu)范圍，降低了定位誤差且減少了計算量；文獻[8]利用了布谷鳥和差分進化雙種群搜索，動態(tài)調(diào)整了布谷鳥算法中發(fā)現(xiàn)入侵者的概率，并隨機縮放差分進化的變異算子，得到了較好的定位精度。但智能優(yōu)化算法具有收斂速度較慢，容易陷入局部最優(yōu)的缺點，如何改善這些缺點使其更好地優(yōu)化DV-Hop算法是一個值得關(guān)注的問題。

本文提出了用精英引導(dǎo)變異和敗者淘汰策略改進的樽海鞘群算法優(yōu)化DV-Hop算法中的定位誤差。由于本文所提算法只在DV-Hop算法的位置估計階段進行優(yōu)化，所以對傳感器的硬件要求沒有影響。

1 DV-Hop算法與改進目標(biāo)

DV-Hop算法可分為三個主要階段：1)信標(biāo)節(jié)點通過廣播自身信息，使網(wǎng)絡(luò)中所有節(jié)點記錄下各信標(biāo)節(jié)點的坐標(biāo)及相應(yīng)的最小跳數(shù)。2)信標(biāo)節(jié)點接收到其他信標(biāo)節(jié)點的消息后，按式(1)計算自身的平均跳距,每個未知節(jié)點用平均跳距和跳數(shù)相乘，就可估算出未知節(jié)點與各信標(biāo)節(jié)點之間的距離。3)當(dāng)未知節(jié)點計算出與各信標(biāo)節(jié)點的距離之后，利用最小二乘法便可求得未知節(jié)點的估計坐標(biāo)。式(1)計算如下

(1)

式中 (xi，yi)，(xj,yj)為錨節(jié)點i，j的坐標(biāo)，hi為它們之間的跳數(shù)。

DV-Hop算法的定位誤差與網(wǎng)絡(luò)中節(jié)點的分布均勻程度相關(guān)，且待定位節(jié)點采用最近的信標(biāo)節(jié)點的平均跳距作為自身的全局平均跳距也會引起較大定位誤差。因此，由第一第二階段得到的未知節(jié)(x,y)點與錨節(jié)點A1(x1,y1)，A2(x2,y2)，…,An(xn,yn)的距離d1,d2，…,dn是存在誤差的，如下式所示

(2)

式中ε1，ε2，…,εn為第一階段和第二階段產(chǎn)生的誤差。則總誤差如下

(3)

式中n為錨節(jié)點數(shù)量。因此，DV-Hop第三階段求解未知節(jié)點可以看作是求總誤差最小的非線性優(yōu)化問題，可以應(yīng)用智能優(yōu)化算法求解。

2 基于改進樽海鞘群算法的DV-Hop算法

2.1 樽海鞘群算法

2017年，樽海鞘群算法(salp swarm algorithm)作為一種結(jié)構(gòu)簡單，輸入?yún)?shù)少，易于實現(xiàn)的全新群體智能算法，由Mirjalili S等人提出[9]，受到了許多學(xué)者的關(guān)注并將其應(yīng)用于實際問題[10～13]。樽海鞘群初始位置隨機在搜索空間中產(chǎn)生，并定義一個適應(yīng)度最高的個體為食物源，稱為F，作為群體的目標(biāo)。然后將種群劃分為領(lǐng)導(dǎo)者和追隨者兩部分，采用以下公式更新領(lǐng)導(dǎo)者的位置

(4)

式中ubj和lbj為搜索空間的上下界。c2和c3為[0,1]間的隨機數(shù)，c2決定了向第j維空間的下一個位置移動的長度，c3則決定朝著正向或是負向移動，是方向控制參數(shù)。c1為平衡進化中搜索和開發(fā)能力的最主要參數(shù)，其定義如下

(5)

式中t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)。

而追隨者的位置采用以下公式(牛頓運動定律)更新

(6)

(7)

由以上可知，樽海鞘鏈的行為機制可由式(4)和式(7)模擬。

2.2 Cat混沌映射種群初始化

大部分群體智能算法采用的是隨機方法生成初始種群，但這就有可能使部分解遠離最優(yōu)位置，而混沌序列具有的不規(guī)律性，隨機性及遍歷性的特點使其可以產(chǎn)生分布均勻的種群。由文獻[14]可知，Cat映射的遍歷性好，且不易陷入小循環(huán)和不穩(wěn)定周期點，能生成更好的均勻序列，因此本文采用Cat映射生成種群的初始位置。Cat映射是可逆的二維混沌映射，其數(shù)學(xué)表達式如下

(8)

(9)

式中 [lbi,ubi]為搜索空間的范圍。

2.3 精英引導(dǎo)變異

由樽海鞘群算法的追隨者更新公式可知后一個體的位置更新主要依靠前一個個體，具有盲目性和不確定性，容易導(dǎo)致早熟收斂，陷入局部最優(yōu)。所以,為了提高追隨者對環(huán)境的探索能力，應(yīng)該在更新中加入環(huán)境和適應(yīng)度最好的個體即食物源的影響，本文提出了一種精英引導(dǎo)變異的方法，對式(7)進行改進，新的追隨者更新公式如下

(10)

式中i≥2,k=1/t2為自適應(yīng)系數(shù)，t為當(dāng)前迭代次數(shù)；(1+φr)為環(huán)境干擾算子，φ為干擾程度，一般取2；r為[-1，1]的隨機數(shù)。由式(10)可知，隨著迭代的進行，變異空間逐漸遞減，開始較大的變異空間可以搜索更多位置，而后期較小的變異空間有助于提高尋優(yōu)精度。

2.4 敗者淘汰策略

在種群的進化中，進化程度較慢的個體容易被淘汰。但它們可能在不同的地方發(fā)展和進化，減少面對的直接競爭，最終生存下來。在自然界和人類社會中，這種現(xiàn)象十分普遍，這是一種避免局部最優(yōu)和保持多樣性的方法。也就是說，淘汰掉失敗者后，重新生成一個進化程度較高的個體加入搜索，加大了尋找最優(yōu)解的機率。

首先定義第g代種群中第i個個體的進化程度δ為

(11)

(12)

將該個體加入種群中使種群向最優(yōu)位置進化。

2.5 改進的DV-Hop算法流程

1)在指定范圍內(nèi)隨機部署若干個錨節(jié)點和待定位節(jié)點，利用DV-Hop算法第一、第二階段估算錨節(jié)點和未知節(jié)點的距離。2)用Cat混沌映射初始化樽海鞘種群，按式(3)計算適應(yīng)度值。3)將個體按適應(yīng)度值排序，適應(yīng)度最好的個體位置選定為食物源位置。4)設(shè)定前50%適應(yīng)度高的樽海鞘個體為領(lǐng)導(dǎo)者，根據(jù)式(4)更新，后50%為追隨者，根據(jù)式(10)更新。5)敗者淘汰策略比較個體進化程度，并利用式(12)更新進化程度較低的樽海鞘個體。6)種群更新后，重新計算每個個體的適應(yīng)度值，并更新食物源位置。7)重復(fù)步驟(4)～步驟(6)，若達到規(guī)定的最大迭代次數(shù)，算法停止運行，并將食物源位置即未知節(jié)點估計位置輸出。

3 實驗與結(jié)果分析

采用在仿真軟件MATLAB(R2016a)上進行仿真實驗。選取實驗區(qū)域的大小為100 m×100 m，區(qū)域內(nèi)節(jié)點總數(shù)為100個，其中錨節(jié)點20個，節(jié)點的通信半徑為30m。選取PSO優(yōu)化的DV-Hop算法，文獻[15]提出的自適應(yīng)調(diào)整策略灰狼算法(記為IGWO)優(yōu)化的DV-Hop算法進行對比，所有算法的種群數(shù)量設(shè)置為20，迭代次數(shù)設(shè)為100次，算法的適應(yīng)度函數(shù)為式(3)。為減少偶然性，優(yōu)化結(jié)果取30次實驗的平均值。為了體現(xiàn)定位誤差的變化，采用歸一化的相對誤差來評價算法的定位性能。歸一化定位誤差的計算公式如下

(13)

表1 定位算法的歸一化平均誤差與標(biāo)準(zhǔn)差

從表1中可以看出，本文算法的歸一化平均誤差和標(biāo)準(zhǔn)差都小于其他算法，說明除了定位精度較高之外，定位的波動性也較小，具有更好的定位穩(wěn)定性。

錨節(jié)點比例、節(jié)點通信半徑、節(jié)點總數(shù)對定位性能影響仿真實驗結(jié)果如圖1所示。

圖1 仿真實驗結(jié)果

1)錨節(jié)點比例對定位性能的影響：設(shè)置節(jié)點總數(shù)為100個，節(jié)點通信半徑為30 m不變，通過改變錨節(jié)點比例測試對定位性能的影響，仿真結(jié)果如圖1(a)所示?？梢钥闯鲭S錨節(jié)點比例上升所有算法的定位誤差都在減小，其中本文算法的準(zhǔn)確度最高，本文算法的定位精度比三種對比算法分別高了約14.8 %，3.9 %，0.6 %。

2)節(jié)點通信半徑對定位性能的影響：設(shè)置節(jié)點總數(shù)為100個，其中錨節(jié)點10個不變，通過改變節(jié)點通信半徑測試對定位性能的影響，仿真結(jié)果如圖1(b)所示。由圖可知隨通信半徑變大定位誤差會減少，但在大于35 m時，定位誤差出現(xiàn)了微小的上升。這是因為通信半徑增大到一定限度后，繼續(xù)增加會加大錨節(jié)點每跳距離的誤差，從而使定位誤差小幅上升。從圖1(b)中得出，本文算法比其他三種定位算法的誤差分別減少了約16.5 %，4 %，0.7 %。

3)節(jié)點總數(shù)對定位性能的影響:設(shè)置錨節(jié)點比例為30 %，節(jié)點通信半徑為30 m，通過改變節(jié)點總數(shù)測試對定位性能的影響。仿真結(jié)果如圖1(c)所示。節(jié)點總數(shù)的增加使網(wǎng)絡(luò)連通度變大，節(jié)點之間的距離變短，DV-Hop算法第一、第二階段估計的跳數(shù)和平均跳距更準(zhǔn)確，定位的性能會越好，所以圖1(c)的三種優(yōu)化后的DV-Hop算法誤差都在減少。其中,節(jié)點總數(shù)為50時，平均跳距的誤差較大。本文算法的優(yōu)化效果比較顯著，誤差分別減少了8.3 %，4.4 %，2.8 %。節(jié)點總數(shù)為100以上時，平均跳距誤差變小，定位結(jié)果趨于收斂，本文算法的定位誤差比其他三種算法分別減少約14.4 %，2.8 %，0.1 %。

4 結(jié)束語

為了提高DV-Hop定位算法的準(zhǔn)確率，本文提出了改進的樽海鞘群算法，使用Cat混沌映射初始化種群，加入了精英引導(dǎo)變異和敗者淘汰策略，使算法加快了收斂速度，提高了尋優(yōu)能力。將改進的樽海鞘群算法應(yīng)用于DV-Hop算法第三階段，仿真結(jié)果表明：在不額外增加硬件和能量開銷的情況下，優(yōu)化后的DV-Hop算法準(zhǔn)確率明顯優(yōu)于傳統(tǒng)的DV-Hop算法，和其他智能優(yōu)化算法的對比中定位誤差也較小，具有更好的定位能力。