基于改進麻雀搜索算法優(yōu)化的DV-Hop定位算法?

印 雷顧 德劉 飛

(江南大學輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122)

隨著物聯(lián)網(wǎng)的發(fā)展，無線傳感器網(wǎng)絡(WSN)技術(shù)取得了前所未有的進步[1]，其中節(jié)點定位技術(shù)被廣泛應用于軍事偵察、環(huán)境監(jiān)測、森林消防、地震救援等領(lǐng)域中，成為了WSN技術(shù)中的研究熱點[2]。

節(jié)點定位技術(shù)通常分為兩類:基于測距的定位算法和無測距的定位算法[3]。第一類定位精度高，但硬件成本較高，目前該類型主要有TDOA、RSSI、TOA、AOA等。無測距的定位算法不需要添加額外的硬件，主要有APIT，CL，DV-Hop等，其缺點是定位精度較低[4－5]。其中，DV-Hop算法因其實現(xiàn)簡單、成本低廉等優(yōu)勢成為目前應用較為廣泛的一種定位技術(shù)。

DV-Hop算法是一種分布式定位算法，一般將傳感器節(jié)點劃分為錨節(jié)點和未知節(jié)點兩類。傳統(tǒng)DV-Hop算法定位精度較低，學者們的改進方法主要分為兩種方向:第一種是修正節(jié)點間的最小跳數(shù)和節(jié)點的平均跳距；第二種是采用群智能(SI)優(yōu)化算法估算未知節(jié)點的位置[6－7]。文獻[8]采用三通信半徑修正節(jié)點間的最小跳數(shù)，提高了定位精度，但錨節(jié)點需在網(wǎng)絡中廣播三次，信息傳輸量的增加加劇了傳感器的能量消耗；文獻[9]通過修正平均跳距，并在后期將粒子群算法(PSO)與人工魚算法(AFSA)相結(jié)合更新個體的位置，加快了收斂速度并提高了定位精度，但是增加了算法的復雜度；文獻[10]在人工蜂群算法(ABC)的初始階段采用區(qū)域限定策略，提升了算法的收斂速度，改善了定位精度，但由于只對蜂群初始階段進行了改進，定位精度的提升并不穩(wěn)定；文獻[11]將改進的灰狼算法(GWO)與DV-Hop算法相融合，并對GWO的控制參數(shù)采用自適應策略，加快了收斂速度，提高了精度，但是該算法僅僅針對DV-Hop的第三階段進行改進，提升空間較大。

上述文獻說明使用群智能算法優(yōu)化DV-Hop來提高節(jié)點的定位精度是有效的，但在其改進過程中，這些算法往往存在著復雜度高、控制參數(shù)多、能耗高、收斂速度不快等問題，而本文針對上述算法的優(yōu)缺點，提出采用魯棒性，收斂性以及準確性更好的麻雀搜索算法來對未知節(jié)點進行定位，并對該算法作出了改進，同時也對節(jié)點的平均跳距以及它們之間的最小跳數(shù)進行了修正。仿真結(jié)果表明，本文算法在不增加額外硬件的情況下，有效提升了傳統(tǒng)DVHop算法的定位精度。

1 相關(guān)理論

1.1 DV-Hop定位算法

DV-Hop算法主要由以下三個步驟組成[12]:

第一步 在經(jīng)典距離矢量路由協(xié)議下，每個錨節(jié)點通過泛洪向WSN網(wǎng)絡廣播包含自身位置和跳數(shù)(初始跳數(shù)設置為0)的數(shù)據(jù)包，接受到信息的節(jié)點會為其創(chuàng)建一個表，并在廣播過程中不斷變化。泛洪過程結(jié)束后，所有節(jié)點得到與錨節(jié)點的最小跳數(shù)。

第二步 錨節(jié)點在接收到其他錨節(jié)點的坐標和最小跳數(shù)數(shù)據(jù)信息之后，利用式(1)計算平均每跳距離:

式中:(xi，yi)和(xj，yj)為錨節(jié)點i和j的坐標；hij是錨節(jié)點i和j之間的最小跳數(shù)；HopSizei為錨節(jié)點i的平均跳距。

錨節(jié)點再次廣播其平均跳距，未知節(jié)點將接收到的第一個平均跳距作為自身平均跳距，并通過式(2)估算自己到所有錨節(jié)點的距離du，i

式中:HopSizeu表示未知節(jié)點的平均跳距，hu，i為未知節(jié)點u到錨節(jié)點i的最小跳數(shù)。

第三步 采用最小二乘法估算未知節(jié)點的位置。

1.2 DV-Hop算法定位誤差分析

DV-Hop算法誤差主要來自以下三方面:

①在分析DV-Hop算法的第一階段后，可以發(fā)現(xiàn)在計算節(jié)點之間的最小跳數(shù)時，把在與其通信半徑R內(nèi)的鄰居節(jié)點之間的跳數(shù)都記作了1跳，但在實際情況中，鄰居節(jié)點與節(jié)點的距離有遠有近，粗略的記作1跳會影響定位準確性。

②原算法將最先接受到的錨節(jié)點的平均跳距作為未知節(jié)點的平均跳距，但這忽略了其他錨節(jié)點的信息，在多跳網(wǎng)絡中，未知節(jié)點這種單一的選擇方式往往不能反映真實的跳距情況。

③最小二乘法估計未知節(jié)點的位置也帶來很大的累計誤差。

1.3 標準麻雀搜索算法

麻雀搜索算法(SSA)是由薛建凱等人在2020年提出的一種新型群智能優(yōu)化算法，它主要是受自然界中麻雀群體覓食和反捕食行為啟發(fā)[13－14]。

在SSA算法中，麻雀種群被分為兩部分:生產(chǎn)者和跟隨者。生產(chǎn)者在種群中所占比例一般為10%～20%，負責搜索食物，并為跟隨者提供方向和覓食區(qū)域。跟隨者會監(jiān)控生產(chǎn)者，與之競爭，成為新的生產(chǎn)者。另外，有一部分麻雀能夠意識到危險，發(fā)出預警并飛往更安全的區(qū)域。

假設種群由N只麻雀構(gòu)成的D維空間中覓食，第i只麻雀的位置為X i＝[xi1，xi2，…，xiD]，i∈[1，2，3，…，N]，則生產(chǎn)者的位置更新公式如下:

式中:為麻雀i在第t次迭代時第j維的位置，j∈[1，2，3…，D]；T為最大迭代次數(shù)；α∈(0，1]是一個均勻隨機數(shù)；R2∈[0，1]，是麻雀種群察覺有捕食者時所發(fā)出的報警值；ST∈[0.5，1]是種群的安全閾值，通常取0.8；Q是服從正態(tài)分布的隨機數(shù)，L為1×d的矩陣，元素均為1。當R2ST時，表示麻雀監(jiān)測到了捕食者，種群需要迅速移動到安全區(qū)域。

剩余的麻雀作為跟隨者，按式(4)更新位置:

式中:Xworst是麻雀種群的全局最差位置，XP是生產(chǎn)者所搜尋到的最優(yōu)位置；A是一個1×d的矩陣，元素隨機分配為1或者－1，A＋＝AT(AAT)－1，代表搜尋方向。當i>n/2時，表示該麻雀非常饑餓，需要快速飛往有豐富食物的區(qū)域，反之，它會在處于最佳位置的生產(chǎn)者周圍活動，并與之競爭。

能夠發(fā)出預警的麻雀占種群的比例為10%到20%，位置更新公式如下:

式中:Xbest表示當前全局最好位置，β是步長控制參數(shù)，為正態(tài)分布的隨機數(shù)，均值為0，方差為1。K∈[－1，1]是一個隨機數(shù)，表示搜索方向，fi是麻雀i的適應度值，fg和fw分別為全局最好和最差適應度值。ε是極小的常數(shù)，用來避免零矩陣。當fi>fg時，表示該麻雀處于種群的邊緣位置，它會飛往最安全的麻雀周圍活動；當fi＝fg時，表示麻雀位于種群中心，收到預警后會靠近其他麻雀。

2 本文的優(yōu)化算法

本文主要對節(jié)點間的最小跳數(shù)和節(jié)點平均跳距作出修正，并用改進的麻雀搜索算法代替最小二乘法估算未知節(jié)點的位置，提高了定位精度。

2.1 最小跳數(shù)修正

為了使節(jié)點之間的最小跳數(shù)更加接近網(wǎng)絡中的真實情況，本文采用雙通信半徑算法對最小跳數(shù)作出修正。該算法假設錨節(jié)點有兩種通信半徑，分別為R和0.5R。如圖1所示，錨節(jié)點A首先以通信半徑R/2在網(wǎng)絡中第一次廣播自身數(shù)據(jù)包，初始跳數(shù)設為0.5，接受到信息后的節(jié)點B最小跳數(shù)設置為0.5，但不轉(zhuǎn)發(fā)信息組，然后節(jié)點A再次以通信半徑R廣播，則未接受到第一次廣播信息的節(jié)點C的最小跳數(shù)被設置為1，并將保存的跳數(shù)加1之后轉(zhuǎn)發(fā)給鄰居節(jié)點。在不斷的轉(zhuǎn)播過程中，最終所有節(jié)點會保存與各錨節(jié)點的最小跳數(shù)信息。

圖1 雙通信半徑示意圖

由于泛洪廣播會極大的消耗節(jié)點的能量，減少網(wǎng)絡壽命，為了避免這種情況，錨節(jié)點在通信半徑為0.5R廣播信息時，接受到信息的節(jié)點無需轉(zhuǎn)發(fā)[8]。

2.2 節(jié)點的平均跳距修正

原始DV-Hop算法中，錨節(jié)點的平均跳距估算是利用式(1)進行估算，而文獻[15]采用最小均方差準則代替，通過仿真證明了采用前者能有效提高DV-Hop算法的定位精度。在最小均方差準則下，每個錨節(jié)點i的平均每跳距離HopSizei如式(6)所示:

在得到錨節(jié)點的平均跳距后，利用錨節(jié)點之間最小跳數(shù)就可以計算得出錨節(jié)點i到其他錨節(jié)點j的估計距離＾di，j為:

式中:(xi，yi)和(xj，yj)分別是錨節(jié)點i和j的坐標。則可根據(jù)式(8)計算出錨節(jié)點i的平均每跳誤差ξi:

式中:di，j是錨節(jié)點i和j的歐氏距離。

則錨節(jié)點新的平均跳距為:

在計算未知節(jié)點平均跳距時引入歸一化加權(quán)因子Wi，表示在未知節(jié)點通信半徑R范圍內(nèi)所接收到的各錨節(jié)點平均跳距的權(quán)重:

式中:hi為錨節(jié)點i與未知節(jié)點的跳數(shù)，hj為所有錨節(jié)點與未知節(jié)點的跳數(shù)。

在無線傳感網(wǎng)絡中，節(jié)點之間的跳數(shù)越大往往會增加估計距離的誤差，因此就應該減小其在定位中的影響，即減少相應的權(quán)重，則通過歸一化加權(quán)因子修正得到未知節(jié)點u的平均每跳距離:

2.3 麻雀算法的優(yōu)化

①佳點集種群初始化

在執(zhí)行群智能優(yōu)化算法時，必須要對種群進行初始化，初始種群分布的優(yōu)劣會直接影響算法的收斂性和解的質(zhì)量。在麻雀算法中，種群的初始化采用的是隨機分布，而這種方法生成的初始種群，無法充分覆蓋解的空間，很難遍歷解的各種可能情況，從而會因為過早收斂而影響最終解的質(zhì)量，而本文采用華羅庚等人[16]提出的佳點集進行種群初始化，可以避免這種問題。

假設種群規(guī)模為100，圖2和圖3是分別采用隨機分布和佳點集初始化的種群。兩圖對比之后，可以明顯看出后者的種群分布比前者更加均勻，充分覆蓋了解空間，增加了群體的多樣性，因此算法會有更好的遍歷性。

圖2 隨機分布初始化種群

圖3 佳點集初始化種群

②Levy飛行策略

Levy飛行策略[17]屬于馬爾可夫過程，是一種特殊的隨機游走策略。如圖4所示，它采用以短距離搜索為主，偶爾進行長距離搜索的隨機游走方法，在群智能算法中使用這種策略，可以使得個體在在大范圍尋找最優(yōu)解時廣泛分布在搜索空間，增加群體多樣性，提高全局尋優(yōu)能力，避免過早的陷入局部最優(yōu)。

圖4 Levy飛行策略仿真

Levy飛行策略服從萊維分布，通常采用一個冪律分布來表示:L(S)～｜S｜－1－β(0<β<2)。其中S是步長，L(S)是移動步長S時的概率。由于萊維分布的復雜性，通常采用Mantegna算法對其進行模擬[18]:

式中:θ和ω遵循正態(tài)分布:

式中:τ是一個標準伽馬函數(shù)，β通常取值1.5。

雖然該策略提高了算法的全局優(yōu)化能力，但是如果所有個體在每次迭代中都利用這種策略來更新位置，計算量勢必會大大增加，因此，該算法僅使用Levy飛行策略更新生產(chǎn)者的位置，這是因為生產(chǎn)者通常會引領(lǐng)其他麻雀位置的更新，起主導作用，間接對跟隨者產(chǎn)生了影響。綜上，將式(3)的生產(chǎn)者位置更新公式改為式(15):

式中:ξ是一個步長參數(shù)，如下式示:

式中:是生產(chǎn)者的當前位置，Xbest是當前迭代周期的最優(yōu)位置。

2.4 改進DV-Hop算法流程

本文采用式(17)的目標函數(shù)計算適應度值:

式中:fitness為麻雀個體的適應度值，(x，y)和(xi，yi)分別是未知節(jié)點和錨節(jié)點的坐標，di為未知節(jié)點到錨節(jié)點的實際距離。

利用改進麻雀搜索算法的DV-Hop算法(ISSADV-Hop)流程如下:

步驟1 在目標區(qū)域隨機部署若干個無線傳感器節(jié)點，在改進之后的第一階段和第二階段估算錨節(jié)點與未知節(jié)點的最小跳數(shù)以及各自的平均每跳距離。

步驟2 設定麻雀種群的數(shù)量，并在初始化中設置迭代次數(shù)，安全閾值(ST)，搜索范圍等各類參數(shù)以及種群的位置(2維)。

步驟3 根據(jù)目標函數(shù)計算種群中所有個體的fitness值并進行排序，記錄當前最好的和最差的個體位置。

步驟4 根據(jù)式(15)、式(4)、式(5)進行迭代，更新種群位置并計算新的適應度值，記錄更新之后最佳個體的適應度值和位置。

步驟5 重復步驟4直至到達最大迭代次數(shù)，得出麻雀種群中的全局最好位置，也就是未知節(jié)點的近似位置。

3 仿真實驗

本文采用MATLAB2016進行仿真模擬實驗，并與傳統(tǒng)DV-Hop，文獻[9]的IPSODV-Hop和文獻[11]的IGWODV-Hop三種算法相對比。將傳感器節(jié)點隨機部署在一個100 m×100 m的網(wǎng)絡區(qū)域中，每個節(jié)點具有相同的通信半徑R。在麻雀算法中，設置種群個體總數(shù)為100，迭代次數(shù)為200，安全閾值設為0.8，生產(chǎn)者比例為20%。該算法將從錨節(jié)點數(shù)、總節(jié)點數(shù)和通信半徑三方面采用歸一化相對誤差來評估定位精度，如式(18)所示，為了減小實驗中隨機誤差對結(jié)果的影響，最終結(jié)果取30次實驗的平均值:

式中:(xu，yu)是未知節(jié)點的實際坐標，(＾xu，＾yu)是估算坐標，M是未知節(jié)點的個數(shù)。

3.1 通信半徑對定位精度的影響

傳感網(wǎng)絡中總節(jié)點數(shù)設為100，錨節(jié)點個數(shù)為30，改變節(jié)點的通信半徑。仿真結(jié)果如圖5所示，四種算法的誤差曲線總體趨勢是隨著通信半徑的增加而減小，這是因為增加通信半徑提高了節(jié)點的鄰居節(jié)點個數(shù)，節(jié)點接受的信息更多，從而提高了定位精度。較之于前三種算法，本文算法的平均定位誤差分別降低了19.5%，11.95%和8.32%。

圖5 通信半徑對定位精度的影響

3.2 總節(jié)點數(shù)對定位精度的影響

保持節(jié)點通信半徑30 m不變，錨節(jié)點占比設為30%，調(diào)整網(wǎng)絡中的總節(jié)點數(shù)。從圖6可以看出，由于節(jié)點總數(shù)不斷增加，改善了指定區(qū)域內(nèi)網(wǎng)絡的連通性，四種算法的定位誤差總體隨著總節(jié)點個數(shù)的增加而相應的減小了。與前三種算法相比，本文算法的平均定位誤差分別降低了20.69%、10.42%和6.41%。

圖6 總節(jié)點個數(shù)對定位精度的影響

3.2 錨節(jié)點數(shù)對定位精度的影響

保持節(jié)點通信半徑30 m不變，總節(jié)點數(shù)設為100，調(diào)整網(wǎng)絡中的錨節(jié)點數(shù)。從圖7可以看出，錨節(jié)點總數(shù)不斷增加會使四種算法的定位誤差都隨之減小，這是由于錨節(jié)點數(shù)量的增加使得節(jié)點的最小跳數(shù)更加符合了網(wǎng)絡的真實情況。與前三種算法相比，本文算法的平均定位誤差分別降低了19.4%、14.58%和7.61%。

圖7 錨節(jié)點個數(shù)對定位精度的影響

4 總結(jié)

針對傳統(tǒng)DV-Hop定位精度誤差大的問題，本文提出了基于改進麻雀搜索算法優(yōu)化的DV-Hop定位算法。首先，錨節(jié)點利用雙通信半徑細化節(jié)點間的最小跳數(shù)，然后利用最小均方差準則以及歸一化加權(quán)因子分別對錨節(jié)點和未知節(jié)點的平均跳距進行了修正，最后針對最小二乘法在未知節(jié)點位置估算中誤差較大的問題，采用了麻雀搜索算法對其進行替代。為了進一步提高麻雀搜索算法在DV-Hop定位算法中的收斂速度，增強算法的全局和局部搜索能力，本文引入了佳點集來增強搜索遍歷性，并引入Levy飛行策略更新麻雀種群中生產(chǎn)者的位置，加強了算法跳出局部最優(yōu)的能力。仿真結(jié)果表明，相比于傳統(tǒng)DV-Hop，IPSODV-Hop，IGWODV-Hop這三種算法，本文算法有效提高了定位精度。