陸 霞,張國華,葉 苗,孫國福

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

0 引言

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

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

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

1 DV-Hop算法分析

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

圖1 DV-Hop算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 種群初始化

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

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

2.1.2 擴大覓食搜索范圍

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

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

2.1.3 覓食位置定位

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實驗環(huán)境

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

表1 實驗平臺配置

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

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

3.2 定位精度對比

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

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

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

3.2.2 通信半徑變化對定位精度的影響

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

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

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

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

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

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

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

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

4 結(jié)語

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