一種基于麻雀算法的優(yōu)化DV-Hop定位算法

陸 霞,張國(guó)華,葉 苗,孫國(guó)福

(南京師范大學(xué) 泰州學(xué)院 信息工程學(xué)院,江蘇 泰州 225300)

0 引言

無(wú)線傳感網(wǎng)(Wireless Sensor Network, WSN)是由大量傳感器節(jié)點(diǎn)構(gòu)成的自組織無(wú)線通信網(wǎng)絡(luò),在農(nóng)業(yè)、軍事、醫(yī)療等領(lǐng)域廣泛應(yīng)用[1]。目前,傳感器節(jié)點(diǎn)定位算法的研究主要集中在距離式定位和非距離式定位兩個(gè)方面[2],RSSI,AOA,TOA等屬于距離式定位算法[3];CL,APIT,DV-Hop等屬于非距離式算法。其中,DV-Hop算法簡(jiǎn)單,運(yùn)行開(kāi)銷低,當(dāng)節(jié)點(diǎn)獲取到3個(gè)及以上信標(biāo)節(jié)點(diǎn)位置信息后就可以實(shí)現(xiàn)定位,使用較為普遍,但是對(duì)未知節(jié)點(diǎn)位置判斷存在定位誤差大、時(shí)間開(kāi)銷大等問(wèn)題。

近年來(lái),種群智能優(yōu)化算法成為許多領(lǐng)域的研究熱點(diǎn),很多學(xué)者以此為契機(jī)針對(duì)DV-Hop算法提出了較多改進(jìn)措施。林鳳德等[4]在算法中引入遺傳變異算子在種群中進(jìn)行全局搜索,再使用蟻群算法進(jìn)一步搜索,保留最優(yōu)個(gè)體,算法提升了DV-Hop的定位精度,但仍有提升空間。石琴琴等[5]使用相似路徑搜索算法估算節(jié)點(diǎn)跳距,并使用灰狼算法進(jìn)一步修正跳距值,提升了DV-Hop算法的定位精度,但收斂性還有待進(jìn)一步提高。麻雀搜索算法(Sparrow Search Algrithm,SSA)是一種新型的種群智能優(yōu)化技術(shù),相比較其他群體智能優(yōu)化算法具有結(jié)構(gòu)簡(jiǎn)單、速度快、易于擴(kuò)充等優(yōu)勢(shì)[6]。本文提出的基于麻雀算法的DV-Hop優(yōu)化定位算法具備更強(qiáng)的搜索能力,更快的收斂速度,即使在節(jié)點(diǎn)分布不均的WSN中,也能優(yōu)化DV-Hop算法中未知節(jié)點(diǎn)坐標(biāo),進(jìn)而提升定位精度。

實(shí)驗(yàn)結(jié)果對(duì)比分析,通過(guò)改變信標(biāo)節(jié)點(diǎn)數(shù)量、通信半徑、種群數(shù)量和迭代次數(shù)等條件,本文提出的優(yōu)化算法相較于經(jīng)典DV-Hop算法,在定位精度和收斂性能上有了顯著提升。

1 DV-Hop算法分析

DV-Hop算法不使用直接測(cè)距的方法進(jìn)行定位,而是借鑒了計(jì)算機(jī)網(wǎng)絡(luò)中基于距離向量的路由機(jī)制,具體原理如圖1所示。DV-Hop算法主要包含3個(gè)步驟。

圖1 DV-Hop算法原理

(1)信標(biāo)節(jié)點(diǎn)將包含自身信息的分組(包含編號(hào)、位置、到其他節(jié)點(diǎn)的跳數(shù)等)向鄰居節(jié)點(diǎn)進(jìn)行廣播。通過(guò)廣播所有節(jié)點(diǎn)不僅可以獲取信標(biāo)節(jié)點(diǎn)的位置,還能確定和信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)。

(2)估算未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的距離。信標(biāo)節(jié)點(diǎn)利用第一階段中獲取到的最小跳數(shù),結(jié)合其他信標(biāo)節(jié)點(diǎn)的位置,估算自身每跳的距離Hopi,再將包含跳距的信息分組廣播轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn),未知節(jié)點(diǎn)將收到信標(biāo)節(jié)點(diǎn)的跳距乘以最小跳數(shù),估算到各個(gè)信標(biāo)節(jié)點(diǎn)之間的距離dij。

式中:(xi,yi)(xj,yj)是信標(biāo)節(jié)點(diǎn)i和j的坐標(biāo),M是信標(biāo)節(jié)點(diǎn)總數(shù),hij是信標(biāo)節(jié)點(diǎn)i與j(i≠j)之間的跳段數(shù)。

式中:Hopi是距離未知節(jié)點(diǎn)i最近的信標(biāo)節(jié)點(diǎn)每跳的距離,hij是未知節(jié)點(diǎn)i與信標(biāo)節(jié)點(diǎn)j之間的最小跳數(shù)。

(3)當(dāng)未知節(jié)點(diǎn)獲取到3個(gè)以上信標(biāo)節(jié)點(diǎn)的距離數(shù)據(jù),使用式(3)三邊測(cè)量法估算未知節(jié)點(diǎn)的位置坐標(biāo)[7]。

式中:(x,y)表示待估算的未知節(jié)點(diǎn)坐標(biāo),(xi,yi)表示信標(biāo)節(jié)點(diǎn)坐標(biāo)(i=1,2,…n),di表示未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的距離。

通過(guò)上述對(duì)DV-Hop算法的描述發(fā)現(xiàn),該算法實(shí)現(xiàn)容易、成本較低。但無(wú)線傳感網(wǎng)中,傳感器節(jié)點(diǎn)分布不均,且每個(gè)節(jié)點(diǎn)擁有的能量不等,DV-Hop算法也存在2個(gè)主要不足。

(1)算法實(shí)現(xiàn)過(guò)程中需要進(jìn)行2次洪泛廣播,第1次是未知節(jié)點(diǎn)從信標(biāo)節(jié)點(diǎn)獲取最小跳數(shù)和位置信息;第2次是信標(biāo)節(jié)點(diǎn)告知估算得到的自身跳距。每次洪泛廣播中,絕大部分節(jié)點(diǎn)都將參與其中,容易造成節(jié)點(diǎn)能量的浪費(fèi),增加無(wú)線傳感網(wǎng)的能耗開(kāi)銷。

(2)誤差的積累會(huì)造成未知傳感器節(jié)點(diǎn)定位精度的降低。誤差主要由2方面原因構(gòu)成:①使用Hopi估算信標(biāo)節(jié)點(diǎn)每跳的跳距,計(jì)算結(jié)果存在誤差,進(jìn)而使得求解未知節(jié)點(diǎn)距離信標(biāo)節(jié)點(diǎn)的距離dij也存在誤差。②在算法的第3個(gè)階段,未知節(jié)點(diǎn)至少收到3個(gè)信標(biāo)節(jié)點(diǎn)才能使用估算算法計(jì)算坐標(biāo),若信標(biāo)節(jié)點(diǎn)組合中存在3點(diǎn)共線或近似共線問(wèn)題,或者1個(gè)信標(biāo)節(jié)點(diǎn)距離未知節(jié)點(diǎn)遠(yuǎn),另外,2個(gè)信標(biāo)節(jié)點(diǎn)距離未知節(jié)點(diǎn)近,未知節(jié)點(diǎn)定位精度會(huì)受到很大影響甚至?xí)鲥e(cuò)[8]。

2 基于麻雀算法的DV-Hop優(yōu)化定位算法

DV-Hop算法中,根據(jù)第2階段估算得到的距離,可以得到未知節(jié)點(diǎn)位置和距離之間的滿足:

式中:δi表示誤差值(i=1,2,…n)。建立優(yōu)化算法的目標(biāo)是將δi降低到最小,那么優(yōu)化定位算法需要解決的問(wèn)題可以歸納為:

即求F(xi,yi)的最小值。

2.1 優(yōu)化定位算法數(shù)學(xué)模型

麻雀喜歡群居,圈養(yǎng)麻雀主要包含2種身份:發(fā)現(xiàn)者(Producer)和跟隨者(Scrounger)。其中,發(fā)現(xiàn)者負(fù)責(zé)尋找食物并為整個(gè)種群提供覓食的區(qū)域和方向,跟隨者則是利用發(fā)現(xiàn)者獲取食物[6]。麻雀覓食過(guò)程使用“發(fā)現(xiàn)者-跟隨者”模型,每只麻雀在種群中可以使用位置屬性進(jìn)行描述。

麻雀算法通過(guò)合適的迭代次數(shù)不斷更新搜索范圍,更新收斂最佳位置。麻雀覓食數(shù)學(xué)模型可以分為種群初始化、擴(kuò)大覓食搜索范圍和覓食位置定位3個(gè)過(guò)程。

2.1.1 種群初始化

種群中麻雀?jìng)€(gè)體數(shù)量為n,指定位置較好的m只麻雀為發(fā)現(xiàn)者,剩余的(n-m)只麻雀為追隨者,發(fā)現(xiàn)者數(shù)量變化范圍[ul,ur],確定最大迭代次數(shù)T。種群初始化位置公式為:

使用式(4)作為每只麻雀的適應(yīng)度函數(shù)。

2.1.2 擴(kuò)大覓食搜索范圍

發(fā)現(xiàn)者可以為種群覓食提供更大的搜索范圍,便于種群覓得更多的食物。每次迭代過(guò)程中,發(fā)現(xiàn)者位置更新公式為:

式中:t表示當(dāng)前迭代次數(shù),α表示[0,1]之間的隨機(jī)數(shù)。的更新參照式(7)計(jì)算。

2.1.3 覓食位置定位

覓食搜索過(guò)程中,跟隨者時(shí)刻監(jiān)視發(fā)現(xiàn)者動(dòng)向,當(dāng)它們察覺(jué)到發(fā)現(xiàn)者找到更好的食物,則立即前往食物所在位置,爭(zhēng)奪發(fā)現(xiàn)者的食物。跟隨者位置更新公式為:

式中:xworst表示第t次迭代時(shí)麻雀的最差位置,xp表示發(fā)現(xiàn)者目前最佳位置,表示發(fā)現(xiàn)者在t+1次迭代的最佳位置,A+表示每個(gè)元素隨機(jī)賦1或-1的1×d的矩陣。當(dāng)k＞時(shí),表示第i個(gè)跟隨者沒(méi)有獲得食物,覓食失敗;當(dāng)k≤時(shí),表示第k個(gè)跟隨者已經(jīng)到達(dá)最優(yōu)位置xp附近。的更新參照式(8)計(jì)算。

2.2 優(yōu)化定位算法描述

基于麻雀算法的DV-Hop優(yōu)化定位算法主要包含以下步驟:

步驟1:根據(jù)式(3)和式(4)使用經(jīng)典DV-Hop算法估算未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的跳距。

步驟2:初始化麻雀算法的基本參數(shù)(發(fā)現(xiàn)者數(shù)量及變化范圍、種群數(shù)量、初始位置等),將未知節(jié)點(diǎn)周圍已知的信標(biāo)節(jié)點(diǎn)坐標(biāo)作為初始麻雀的基本位置信息,根據(jù)式(6)將適應(yīng)度取值低的麻雀作為發(fā)現(xiàn)者。

步驟3:在既定的最大迭代次數(shù)范圍內(nèi),根據(jù)式(7)和式(8)不斷更新發(fā)現(xiàn)者和跟隨者的位置信息。

步驟4:在迭代過(guò)程中,若跟隨者位置連續(xù)多次無(wú)更新,需進(jìn)行種群個(gè)體變異,重新選擇新的發(fā)現(xiàn)者繼續(xù)進(jìn)行位置更新,否則轉(zhuǎn)步驟5。

步驟5:如果已達(dá)到最大迭代次數(shù),輸出最佳位置,最佳位置即為優(yōu)化后的未知節(jié)點(diǎn)坐標(biāo),算法結(jié)束,否則重復(fù)步驟3和步驟4。

改進(jìn)后的DV-Hop優(yōu)化定位算法流程如圖2所示。

圖2 DV-Hop優(yōu)化定位算法流程

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

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證改進(jìn)算法的定位精度,使用如表1所示的實(shí)驗(yàn)平臺(tái)提供運(yùn)行環(huán)境支持。假設(shè)所有傳感器節(jié)點(diǎn)結(jié)構(gòu)相同,且區(qū)域內(nèi)任意2個(gè)節(jié)點(diǎn)均可通信,仿真網(wǎng)絡(luò)環(huán)境參數(shù)設(shè)置如表2所示。以上述實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置為依據(jù),分別變換信標(biāo)節(jié)點(diǎn)數(shù)量、通信半徑、種群數(shù)量和迭代次數(shù),將DV-Hop算法、基于麻雀算法的DVHop算法(下文簡(jiǎn)稱SSA DV-Hop)進(jìn)行性能比對(duì)。采用平均相對(duì)定位誤差作為評(píng)定指標(biāo),計(jì)算公式為:

表1 實(shí)驗(yàn)平臺(tái)配置

表2 仿真網(wǎng)絡(luò)環(huán)境參數(shù)設(shè)置

式中:N表示節(jié)點(diǎn)總數(shù),M表示信標(biāo)節(jié)點(diǎn)個(gè)數(shù),(x,y)表示未知節(jié)點(diǎn)估算坐標(biāo)信息,(x′,y′)表示未知節(jié)點(diǎn)實(shí)際坐標(biāo)信息,R表示節(jié)點(diǎn)通信半徑。

3.2 定位精度對(duì)比

3.2.1 信標(biāo)節(jié)點(diǎn)數(shù)量對(duì)定位精度的影響

如圖3所示在通信半徑為15 m,迭代次數(shù)為30次,信標(biāo)節(jié)點(diǎn)數(shù)量由5個(gè)變化到30個(gè)的情況下,2種算法定位精度的表現(xiàn),結(jié)果表明:隨著信標(biāo)節(jié)點(diǎn)數(shù)量的增加,DV-Hop算法定位精度可以提高約34%,SSA DVHop算法定位精度提高約24%,SSA DV-Hop算法定位精度較高。

圖3 信標(biāo)節(jié)點(diǎn)數(shù)量變化對(duì)定位精度的影響

3.2.2 通信半徑變化對(duì)定位精度的影響

如圖4所示在信標(biāo)節(jié)點(diǎn)數(shù)量為15個(gè),迭代次數(shù)為30次,通信半徑由15 m變化到30 m的情況下,2種算法定位精度的表現(xiàn),結(jié)果表明:隨著通信半徑的增加,DV-Hop算法定位精度可以提高約23%,SSA DV-Hop算法定位精度提高約25%,SSA DV-Hop算法定位精度較高。

圖4 通信半徑變化對(duì)定位精度的影響

3.2.3 種群數(shù)量對(duì)定位精度的影響

如圖5所示在信標(biāo)節(jié)點(diǎn)數(shù)量為15個(gè),迭代次數(shù)為30次,通信半徑為15 m,種群數(shù)量由30個(gè)變化到80個(gè)的情況下進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明:隨著種群數(shù)量的增加,SSA DV-Hop算法定位誤差不斷降低,當(dāng)種群數(shù)量大約達(dá)到40個(gè)時(shí),SSA DV-Hop算法定位精度無(wú)顯著變化。

圖5 種群數(shù)量對(duì)定位精度的影響

3.2.4 迭代次數(shù)對(duì)定位精度的影響

如圖6所示結(jié)果表明:隨著迭代次數(shù)的增加,SSA DV-Hop算法定位誤差逐漸減低,迭代次數(shù)大約達(dá)到70次左右定位誤差無(wú)顯著變化,收斂速度較快。

圖6 迭代次數(shù)對(duì)定位精度的影響

4 結(jié)語(yǔ)

針對(duì)DV-Hop算法定位精度較低的不足,在分析麻雀算法原理的基礎(chǔ)上,將改進(jìn)后的優(yōu)化麻雀算法應(yīng)用到DV-Hop算法中,實(shí)現(xiàn)了信標(biāo)節(jié)點(diǎn)跳距的優(yōu)化。仿真結(jié)果表明,在不增加額外網(wǎng)絡(luò)開(kāi)銷的情況下,基于麻雀算法的優(yōu)化DV-Hop定位算法能有效提高節(jié)點(diǎn)的定位精度。