基于改進(jìn)樽海鞘群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位*

田洪舟，陳思溢，黃輝先

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

0 引 言

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

2 基于改進(jìn)樽海鞘群算法的DV-Hop算法

2.1 樽海鞘群算法

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

(4)

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

(5)

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

而追隨者的位置采用以下公式(牛頓運(yùn)動(dòng)定律)更新

(6)

(7)

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

2.2 Cat混沌映射種群初始化

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

(8)

(9)

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

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

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

(10)

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

2.4 敗者淘汰策略

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

首先定義第g代種群中第i個(gè)個(gè)體的進(jìn)化程度δ為

(11)

(12)

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

2.5 改進(jìn)的DV-Hop算法流程

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

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

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

(13)

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

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

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

圖1 仿真實(shí)驗(yàn)結(jié)果

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

2)節(jié)點(diǎn)通信半徑對(duì)定位性能的影響：設(shè)置節(jié)點(diǎn)總數(shù)為100個(gè)，其中錨節(jié)點(diǎn)10個(gè)不變，通過(guò)改變節(jié)點(diǎn)通信半徑測(cè)試對(duì)定位性能的影響，仿真結(jié)果如圖1(b)所示。由圖可知隨通信半徑變大定位誤差會(huì)減少，但在大于35 m時(shí)，定位誤差出現(xiàn)了微小的上升。這是因?yàn)橥ㄐ虐霃皆龃蟮揭欢ㄏ薅群?，繼續(xù)增加會(huì)加大錨節(jié)點(diǎn)每跳距離的誤差，從而使定位誤差小幅上升。從圖1(b)中得出，本文算法比其他三種定位算法的誤差分別減少了約16.5 %，4 %，0.7 %。

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

4 結(jié)束語(yǔ)

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